Secret data matching device, secret data matching method, and recording medium

Patent metadata

Field	Value
Publication number	US-9455984-B2
Application number	US-201414317241-A
Country	US
Kind code	B2
Filing date	Jun 27, 2014
Priority date	Jul 11, 2013
Publication date	Sep 27, 2016
Grant date	Sep 27, 2016

Abstract

A secret data matching device includes: a memory; and a processor coupled to the memory. The processor executes a process including: storing a first secret vector obtained by concealing first data and key data based on a first random number and a first linear combination of row vectors of a determination matrix which is different for each system including the secret data matching device and which is generated by attaching a random number vector as a last column to a matrix including diagonal components including a threshold value to determine whether the first data and second data are approximate to each other and a threshold value related to the key data; acquiring a second secret vector obtained by concealing the second data based on a second linear combination of row vectors of the determination matrix and a second random number.

First claim

What is claimed is:

1. A secret data matching device comprising:
a memory; and
a processor coupled to the memory, wherein the processor executes a process including:
storing a first secret vector provided by a first terminal device, wherein the first terminal device obtains the first secret vector concealing first data and key data based on a first random number and a first linear combination of row vectors, wherein the first linear combination is provided for the first terminal device by the secret data matching device and the row vectors are of a determination matrix wherein the determination matrix is generated by attaching a random number vector as a last column to a matrix including diagonal components including a threshold value to determine whether the first data and second data are approximate to each other and a threshold value related to the key data and generated differently for a plurality of systems each including the secret data matching device;
acquiring a second secret vector from a second terminal device, wherein the second terminal device obtains the second secret vector concealing the second data based on a second linear combination of row vectors of the determination matrix and a second random number, the second linear combination being provided for the second terminal device by the secret data matching device;
calculating a residual vector that is a residue when the determination matrix is used as a modulus into a difference between the first secret vector stored at the storing and the second secret vector acquired at the acquiring;
determining whether or not the first data and the second data are approximate to each other based on the residual vector calculated at the calculating; and
extracting the key data from the residual vector when it is determined that the first data and the second data are approximate to each other as a result of a determination at the determining, and providing the extracted key data to the second terminal device.

2. The secret data matching device according to claim 1 , wherein the acquiring includes acquiring the second secret vector that is obtained by the second terminal device based on the second linear combination different from the first linear combination used when the first secret vector is obtained and the second random number.

3. A non-transitory computer-readable recording medium having stored therein a program that causes a computer to execute a secret data matching process comprising:
registering in a storage a first secret vector provided by a first terminal device, wherein the first terminal device obtains the first secret vector concealing first data and key data based on a first random number and a first linear combination of row vectors, wherein the first linear combination is provided for the first terminal device by the computer and the row vectors are of a determination matrix wherein the determination matrix is generated by attaching a random number vector as a last column to a matrix including diagonal components including a threshold value to determine whether the first data and second data are approximate to each other and a threshold value related to the key data and generated differently for a plurality of systems each including the computer;
acquiring a second secret vector from a second terminal device, wherein the second terminal device obtains the second secret vector concealing the second data based on a second linear combination of row vectors of the determination matrix and a second random number, the second linear combination being provided for the second terminal device by the computer;
calculating a residual vector that is a residue when the determination matrix is used as a modulus into a difference between the first secret vector stored in the storage and the second secret vector acquired by the acquiring process;
determining whether or not the first data and the second data are approximate to each other based on the residual vector calculated by the calculating process; and
extracting the key data from the residual vector when it is determined that the first data and the second data are approximate to each other as a result of a determination by the determining process, and providing the extracted key data to the second terminal device.

4. A secret data matching method comprising:
registering in a storage, by a processor included in a computer, a first secret vector provided by a first terminal device, wherein the first terminal device obtains the first secret vector concealing first data and key data based on a first random number and a first linear combination of row vectors, wherein the first linear combination is provided for the first terminal device by the processor and the row vectors are of a determination matrix wherein the determination matrix is generated by attaching a random number vector as a last column to a matrix including diagonal components including a threshold value to determine whether the first data and second data are approximate to each other and a threshold value related to the key data and generated differently for a plurality of systems each including the computer;
acquiring, by the processor, a second secret vector from a second terminal device, wherein the second terminal device obtains the second secret vector concealing the second data based on a second linear combination of row vectors of the determination matrix and a second random number, the second linear combination being provided for the second terminal device by the processor;
calculating, by the processor, a residual vector that is a residue when the determination matrix is used as a modulus into a difference between the first secret vector stored in the storage and the acquired second secret vector;
determining, by the processor, whether or not the first data and the second data are approximate to each other based on the calculated residual vector; and
extracting, by the processor, the key data from the residual vector when it is determined that the first data and the second data are approximate to each other as a result of a determination at the determining, and providing the extracted key data to the second terminal device.

Assignees

• Fujitsu Ltd

Inventors

• Jo Yuka
• Yasuda Masaya

Classifications

• G06F21/32 Primary

  using biometric data, e.g. fingerprints, iris scans or voiceprints · CPC title

• G06K9/00885

  Physics · mapped topic

• G06K2009/00953

  Physics · mapped topic

• H04L63/061

  for key exchange, e.g. in peer-to-peer networks (cryptographic mechanisms or cryptographic arrangements for key agreement H04L9/0838) · CPC title

• H04L63/0861 Primary

  using biometrical features, e.g. fingerprint, retina-scan (cryptographic mechanisms or cryptographic arrangements for entity authentication using biological data H04L9/3231) · CPC title