[Technical Field]
(Descript ion of related art 5 )
The present invent ion is based upon the benefi t of priori ty from
Japanese Patent Appl icat ion No. 2012 -157265 (fi led on July 13, 2012) , the
ent i re contents of which are incorporated herein by reference.
The present invent ion is related to a n encrypted data (ciphertext)
10 checking (veri fying) system, method, and program.
[Background Art ]
Recent ly, along wi th the popularizat ion of cloud comput ing, data of a
user is stored in a calculat ion resource that is connected to a network, and
service based on the data has been spreading rapidly. In such service, an
15 opportuni ty to deal wi th sensi t ive data of the user has been increased.
Therefore, it is important to guarantee the safe management of the data on
the user . Under such an envi ronment , research and development of a
technology, that enables to manage that data in encrypted state in an open
network envi ronment , and execute a search, a stat ist ics processing and the
20 l ike by using the data wi thout decrypt ion , has been per formed act ively.
In addi t ion, recent ly, a crime ,which exploi ts the vulnerabi l i ty of
personal authent icat ion such l ike using a password or a magnet ic card,
occurs f requent ly. Therefore, a biometr ic ident i ficat ion technology
having further high safety based on a biomet ric feature, such as a
25 fingerprint and vein, at t racts considerable at tent ion. In the biometr ic
ident if icat ion, in order to veri fy authent icat ion informat ion, i t is necessary
to store a template related to biological informat ion in a database (DB).
The biological informat ion such the fingerprint and vein is data that is
basical ly not changed through the l i fet ime. If the biological informat ion
3
is leaked, serious damage occurs by the leakage of the informat ion.
Therefore, the biological informat ion is informat ion for which the
confident ial i ty is required the most . Thus, i t is necessary to prevent
impersonat ion even i f the template is leaked.
Thus, a biomet ric ident if icat ion technology which protects templates ( 5 a
template protect ion type biometric ident i f icat ion technology) , in which the
authent icat ion is per formed whi le template informat ion remains concealed,
has become important .
For example, in Patent l i terature 1, a method is disclosed in which
10 biometr ic ident i ficat ion is performed using, as a template, data that is
obtained by represent ing fingerprint data as points on a polynomial
expression, adding random point s to the points, and conceal ing the
fingerprint data.
However , in the above-described method disclosed in Patent l i terature
15 1, i t is known that there is a problem whether or not the biological
informat ion is protected wi th suf ficient st rength when the biomet ric
ident if icat ion is repeated plural t imes.
In Non-Patent l i terature 1, a method is disclosed in which biological
informat ion is protected by masking a template that is stored in a DB
20 through a random Bose-Chaudhuri -Hocquenghem (BCH) code word. In
the technology disclosed in Non-Patent l i terature 1, a biomet ric
ident if icat ion template is generated using biological informat ion Z and
confident ial informat ion S. Fig. 5 is a diagram based on Fig. 2 of
Non-Patent l i terature 1, and the feature extract ion, stat ist ical analysis,
25 quant izat ion, and the l ike in Fig. 2 of Non-Patent l i terature 1 are omi t ted.
The enrol lment of a template is performed as fol lows .
(1) The confident ial informat ion S is input to an encoder (ENC). The
ENC per forms error correct ing coding (ECC) on the confident ial
informat ion S, and generates a code word C. A binary BCH code of
4
parameters (K, s, and d) is used as the ECC. "K" indicates the length of
the code word, and "s" indicates the number of informat ion symbols, and
"d" indicates the number of cor rectable er rors .
(2) An XOR (exclusive OR) between "C" and "Z", that is, "W2=C(+)Z" is
calculated (hereinafter , the symbol "(+)" indicates bi twise XOR5 ).
(3) "S" is input to a cryptographic (one-way) hash funct ion H, such as a
secure hash algori thm (SHA)-1 or the l ike, and the hash value H (S) is
calculated.
(4) "W2" and "H(S)" are stored in a DB as template informat ion.
10 The veri ficat ion of whether or not the template, that has been generated
as described in (1) to (4), and the other biological informat ion Z' , are
obtained f rom an ident ical person, is per formed as fol lows .
(1) The XOR between "Z'" and "W2", that is, "C'=W2(+)Z'=C(+) (Z(+)Z')"
is calculated.
15 (2) "C'" is input to a decoder (DEC) , and error -correct ing decoding of the
BCH code is performed to calculate "S'".
(3) "S'" is input to the cryptographic (one-way) hash funct ion H, such as
the SHA-1 or the l ike, to calculate a hash value H(S') .
(4) "H(S)" is read f rom the DB, and i t is veri fied whether or not
20 "H(S)=H(S')" is sat isfied. When "H(S)=H(S')" is sat isf ied, i t is
determined that the template and the biological informat ion Z' are obtained
from an ident ical person. When "H(S)=H(S')" is not sat isfied, i t is
determined that the template and the biological informat ion Z' are
respect ively obtained f rom di fferent persons .
25 The method i l lustrated in Fig. 5 does not depend on the obtaining
method of the biological informat ion Z. Therefore, general ly, the method
i l lust rated in Fig. 5 may be regarded as a method that veri fies whether or
not the encrypted data is generated by encrypt ing a plaintext of which
distance to presented data is in certain distance.
5
[Ci tation List]
[Patent Literature]
[PTL 1] Japanese Laid-open Patent Publ icat ion No. 2006-158851
5
[Non Patent Li terature]
[NPL 1] : Pim Tuyls, Anton H. M. Akkermans, Tom A. M. Kevenaar ,
Geert -Jan Schri jen, Asker M. Bazen and Raymond N. J. Veldhuis,
"Pract ical Biometr ic Authent icat ion wi th Templ ate Protect ion",
10 Proceedings of AVBPA 2005, Lecture Notes in Computer Science, Vol .
3546, Springer Verlag, pp. 436-446, (2005)
[Summary of Invent ion]
[Technical Problem]
15 The analysis of the related arts is described below.
As a problem of the above-described related ar ts, in the verif icat ion of
the encrypted data in the DB, i t is probable that informat ion about the
plaintext (decrypted data) is leaked to an administ rator or the l ike who
performs the veri ficat ion. The reason is as fol lows .
20 For example, in the above-described Patent l i terature 1, the degree of
confident ial i ty of the encrypted data is not sufficient .
In addi t ion, in the above-described Non-Patent l i terature 1, in order to
enable verificat ion of whether or not the encrypted data is obtained by data
that is wi thin a cer tain Hamming distance f rom the presented data, i t is
25 necessary that the plaintext informat ion is transmi t ted at the t ime of the
verif icat ion. As described above, when the veri ficat ion processing is
performed mul t iple t imes, i t is probable that the informat ion on the
original plaintext is leaked, and for example, the sufficient safety may not
be ensured when the data base administrator or the l ike who performs the
6
verif icat ion processing has a mal icious intent ion.
Thus, the present invent ion is made in view of the above problems . An
object of the present invent ion is to provide a system, a method, and a
program in which in verif icat ion of an encrypted data, leakage of
informat ion on the or iginal plaintext is able to be avoided, and the safety i5 s
able to be ensured.
[Solution to Problem]
In the present invent ion, there is provided an encrypted data verif icat ion
system that includes
10 means for generat ing fi rst and second auxi l iary data that are used to
verify, that a Hamming distance between a plaintext of a fi rst encrypted
data which is encrypted f rom input data and registered to a storage
apparatus , and a plaintext of a second encrypted data which is encrypted
from input data of a target to be veri fied, is a predetermined certain value
15 or less, for the f irst encrypted data and the second encrypted data
respect ively; and
means for obtaining a di fference between the fi rst encrypted data that
is registered to the storage apparatus and the second encrypted data that is
obtained by encrypt ing the input data of the target to be veri fied, and
20 determining whether or not the Hamming distance of the plaintexts, which
corresponds to the di fference between the fi rst encrypted data and the
second encrypted data, is the predetermined certain value or less , using the
first and second auxi l iary data.
In the present invent ion, there is provided a biometric ident ificat ion
25 system that includes the encrypted data veri ficat ion system.
In the present invent ion, there is provided an encrypted data verif icat ion
method that includes
generat ing fi rst and second auxi l iary data that are used to
verify, that a Hamming distance between a plaintext of a fi rst encrypted
7
data which is encrypted f rom input data and registered to a storage
apparatus , and a plaintext of a second encrypted data which is encrypted
from input data of a target to be veri fied, is a predetermined certain value
or less, for the f irst encrypted data and the second encrypted data
respect ively; an5 d
obtaining a di f ference between the f irst encrypted data that is
registered to the storage apparatus and the second encrypted data that is
obtained by encrypt ing the input data of the target to be veri fied, and
determining whether or not the Hamming distance of the plaintexts, which
10 corresponds to the di fference between the fi rst encrypted data and the
second encrypted data, is the predetermined certain value or less , using the
first and second auxi l iary data .
In the present invent ion, there is provided a program that causes a
computer to execute
15 a processing of generat ing fi rst and second auxi l iary data that are
used to ver ify, that a Hamming distance between a plaintext of a fi rst
encrypted data which is encrypted f rom input data and registered to a
storage apparatus , and a plaintext of a second encrypted data which is
encrypted f rom input data of a target to be veri fied, is a predetermined
20 certain value or less, for the f irst encrypted data and the second encrypted
data respect ively; and,
a processing of obtaining a di fference between the fi rst encrypted
data that is registered to the storage apparatus and the second encrypted
data that is obtained by encrypt ing the input data of the target to be
25 verif ied, and determining whether or not the Hamming distance of the
plaintexts, which cor responds to the dif ference between the fi rst encrypted
data and the second encrypted data, is the predetermined certain value or
less, using the fi rst and second auxi l iary data . In the present invent ion,
there is provided a computer readable recording medium (magnet ic/opt ical
8
recording medium or semiconductor recording medium) to which the
program is recorded.
[Advantageous Ef fects of Invention]
In the present invent ion, in veri ficat ion of an encrypted data,
informat ion leakage of the or iginal plaintext can be avoided, and the safet5 y
can be ensured.
[Brief Description of Drawings]
[Fig. 1] Fig. 1 is a diagram i l lust rat ing a configurat ion according to a
first exemplary embodiment of the present invent ion.
10 [Fig. 2] Fig. 2 is a diagram i l lust rat ing a configurat ion according to a
second exemplary embodiment of the present invent ion.
[Fig. 3] Figs. 3(A) and 3(B) are diagrams respect ively i l lust rat ing a data
regist rat ion phase and an encrypted data verif icat ion phase according to
the fi rst exemplary embodiment of the present invent ion.
15 [Fig. 4] Figs. 4(A) and 4(B) are diagrams respect ively i l lust rat ing a data
regist rat ion phase and an encrypted data verif icat ion phase according to
the second exemplary embodiment of the present invent ion.
[Fig. 5] Fig. 5 is a diagram i l lustrat ing a scheme in Non-Patent Li terature1.
20 [Description of Embodiments]
Exemplary embodiment s of the present invent ion are described below.
In the exemplary embodiment s of the present invent ion, input data of a
target to be checked is encrypted, and registrat ion data ( registered data)
that is used to perform veri ficat ion for the input data is encrypted, and a
25 Hamming distance of plaintext is used as an indicator of ambigui ty of
determinat ion of the verif icat ion (matching). Not only the encrypted
regist rat ion data, the input data for the verif icat ion is also encrypted
through an encrypt ing method having a high concealment strength. Even
when the verificat ion is per formed mul t iple t imes using ident ical input
9
data, key informat ion that is used to per form concealment of the data is
changed each t ime the veri ficat ion is performed. Therefore, even when
the veri ficat ion is performed mul t iple t imes , a possibi l i ty about leakage of
informat ion about the plaintext may be reduced, and the at tack resistance
is enhanced to contribute to the improvement of the securi ty5 .
In an exemplary embodiment , a system includes means (103 in Fig. 1
and 303 in Fig. 2) that generates first and second auxi l iary data, that are
described later . In addi t ion, the system further includes determinat ion
means (402 and 403 in Fig. 1, and 502 and 503 in Fig. 2) determines
10 whether or not a Hamming distance of plaintexts, which corresponds to a
dif ference between a fi rst encrypted data that is described later and a
second encrypted data that is also described later , is a predetermined
certain value or less.
Such a f irst encrypted data is obtained by encrypt ing input data and
15 is registered to a storage apparatus. Such a second encrypted data is is
obtained by encrypt ing input data of a target to be checked (veri fied) .
Such fi rst and second auxi l ia ry data are used to ver ify that the Hamming
distance of the plaintexts between the fi rst encrypted data and the second
encrypted data is the predetermined certain value or less .
20 In addi t ion, the above-described determinat ion means obtains the
dif ference between the above-described f irst encrypted data and the
above-described second encrypted data. The above-described
determinat ion means determines whether or not the Hamming distance of
the plaintexts, which cor responds to the difference between the
25 above-described fi rst encrypted data and the above-described second
encrypted data, is a predetermined certain value or less , by using the
above-described fi rst and second auxi l iary data.
In the exemplary embodiment , the system generates the above-described
encrypted data, f rom the calculat ion resul t of an XOR between a code word
10
that is obtained by encoding a key, that is used to perform encoding on the
plaintext of the above-described input data, through an er ror -cor rect ing
code having l ineari ty, and the above-described plaintext , . Then the
system calculates the above-described encrypted data, that is registered to
the above-described storage apparatus , and above-descr ibed fi rst an5 d
second auxi l iary data, that are respect ively related to the above -described
encrypted data of the above-described input data of a target to be veri fied,
based on an XOR between an inner product of the above-descr ibed key and
a constant , and a cryptographic (one-way) hash funct ion that is executed on
10 the above-described encrypted data and a random number . In addi t ion, in
the exemplary embodiment , in a hash funct ion that is used to determine the
verif icat ion resul t , the system guarantees that a hash value of the sum of
two pieces of data can be calculated from respect ive hash values of the two
pieces of data. As a resul t , the system enables verificat ion processing
15 between encrypted data, which is not able to be achieved in the
above-described Non-Patent l i terature 1.
As described above, in the ver ificat ion processing between encrypted
data, data that is t ransmi t ted by a user who per forms the veri ficat ion is also
encrypted wi th an encrypt ing key that is unknown to a database
20 administ rator or the l ike. Therefore, even when the veri ficat ion
processing is per formed mul t iple t imes , or when the database administrator
or the l ike, who executes the veri ficat ion processing, has a mal icious
intent ion, leakage of informat ion that is related to the original plaintext is
able to be avoided. Some exemplary embodiments are described below.
25
Refer ring to Fig. 1, a system according to a first exemplary embodiment
of the present invent ion includes a registrat ion data generat ion apparatus
100, a storage apparatus 200, a data concealment apparatus 300, and a
speci ficat ion dat a verif icat ion apparatus 400. It is noted that these
11
apparatuses may be configured to form a single apparatus in a single si te,
by integrat ing themselves, or may be configured so as to form dist ributed
ar rangement and to be connected to each other through a communicat ion
means.
The regist rat ion data generat ion apparatus 100 includes an encrypt in5 g
uni t 101, a key generat ion uni t 102, and a registrat ion auxi l iary data
generat ion uni t 103.
The encrypt ing uni t 101 accepts fol lowing data as inputs. That is , the
encrypt ing uni t 101 accepts input data that is to be concealed (concealment
10 target data) , and a key that is used to conceal the input data. The
encrypt ing uni t 101 outputs the encrypted data that is obtained by
execut ing concealment processing on the input data, by using the key.
The key generat ion uni t 102 generates the key that is used by the
encrypt ing uni t 101 to conceal the input data, and outputs the key to the
15 encrypt ing uni t 101 and to the regist rat ion auxi l iary data generat ion uni t
103.
The regist rat ion auxi l iary data generat ion uni t 103 accepts the fol lowing
data as inputs. That is, the registrat ion auxi l iary data generat ion uni t 103
accepts the input data, the encrypted data that is output f rom the
20 encrypt ing uni t 101, and the key that is output f rom the key generat ion uni t
102. The registrat ion auxi l iary data generat ion uni t 103 generates and
outputs the fol lowing data. That is, the registrat ion auxi l iary data
generat ion uni t 103 generates, input data that corresponds to encrypted
data that is output f rom an encrypt ing uni t 301 of the data concealment
25 apparatus 300, and data (auxi l iary data) that is used to determine that a
Hamming distance wi th the input data that has been input to the encrypt ing
uni t 101 is a predetermined certain value or less (wi thin a certain numeric
value).
The encrypted data that is output f rom the encrypt ing uni t 101 of the
12
regist rat ion data generat ion apparatus 100 sat isfies the fol lowing
relat ionship. That is, when an encrypted data that is obtained by
encrypting input data m1 by using a key k1 by the encrypt ing uni t 101 is
treated as "c1", and an encrypted data that is obtained by encrypt ing input
data m2 by using a key k2 by the encrypt ing uni t 101 is treated as "c2", th5 e
sum of "c1" and "c2", that is, "c1+c2" becomes an encrypted data that is
obtained by encrypt ing input data m1+m2 by using a key k1+k2.
The storage apparatus 200 includes an ident if ier management uni t 201,
an encrypted data storage uni t 202, and an auxi l iary data storage uni t 203.
10 The encrypted data storage uni t 202 and the auxi l iary data storage uni t 203
respect ively store the encrypted data and the regist rat ion auxi l iary data
that has been output from the registrat ion data generat ion apparatus 100.
The encrypted data storage uni t 202 and the auxi l iary data storage uni t 203
may be configured as DBs (or, may have fi le configurat ions).
15 The encrypted data storage uni t 202 and the auxi l iary data storage uni t
203 respect ively output encrypted data and auxi l iary data that cor respond
to an ident i fier that is input from the specificat ion data verificat ion
apparatus 400, under the cont rol of the ident i fier management uni t 201 ,
when encrypted data are veri fied.
20 The ident i fier management uni t 201 of the storage apparatus 200
manages an ident ifier that is used to uniquely ident ify encrypted data and
auxi l iary data that are input from the registrat ion data generat ion apparatus
100.
When an ident i fier is input f rom the specificat ion data veri f icat ion
25 apparatus 400, the ident i fier management uni t 201 issues an instruct ion of
output of encrypted data that corresponds to the input ident i f ier , to the
encrypted data storage uni t 202. In addi t ion, when the ident ifier is input
from the specificat ion data verificat ion apparatus 400, the ident ifier
management uni t 201 issues an inst ruct ion of output of auxi l iary data that
13
corresponds to the input ident i fier , to the auxi l iary data storage uni t 203 .
The encrypted data storage uni t 202 stores encrypted data that has been
output from the encrypt ing uni t 101 of the regist rat ion data generat ion
apparatus 100. When an instruct ion of output of encrypted data is input
from the ident i fier management uni t 201, the encrypted data storage uni 5 t
202 outputs the corresponding encrypted data.
The auxi l iary data storage uni t 203 stores auxi l iary data that has been
output from the registrat ion auxi l iary data generat ion uni t 103 of the
regist rat ion data generat ion apparatus 100. When an instruct ion of output
10 of encrypted data is input f rom the ident if ier management uni t 201, the
auxi l iary data storage uni t 203 output s the corresponding auxi l iary data.
The data concealment apparatus 300 includes an encrypt ing uni t 301, a
key generat ion uni t 302, and an auxi l iary data generat ion uni t 303.
The encrypt ing uni t 301 accepts fol lowing data as inputs. That is, the
15 encrypt ing uni t 301 accepts input data that is a concealment target (input
data of a target to be veri fied), and a key that is used to perform
concealment of the input data. The encrypt ing uni t 301 outputs encrypted
data that is obtained by execut ing the encrypt ing processing for the input
data using the key.
20 The key generat ion uni t 302 generates the key that is used to per form
concealment of the input data by the encrypt ing uni t 301. In addi t ion, the
key generat ion uni t 302 outputs the generated key to the encrypt ing uni t
301 and the auxi l iary data generat ion uni t 303 .
The auxi l iary data generat ion uni t 303 accepts fol lowing data as inputs.
25 That is the auxi l iary data generat ion uni t 303 accepts the input data, the
encrypted data that has been output f rom the encrypt ing uni t 301, and the
key that has been output from the key generat ion uni t 302. The auxi l iary
data generat ion uni t 303 outputs auxi l iary data based on such inputs.
Such auxi l iary data is used to determine whether or not a Hamming
14
distance between the input data (plaintext ) that cor responds to the
encrypted data that is output f rom the encrypt ing uni t 101 of the
regist rat ion data generat ion apparatus 100 (encrypted regist rat ion data),
and the data (plaintext ) that has been input to the encrypt ing uni t 301, is a
predetermined certain value or less (wi thin a certain numeric value). I5 n
other words, such auxi l iary data is auxi l iary informat ion that is used to
determine that the input data (plaintext ) that cor responds to the encrypted
regist rat ion data is matched wi th the data of the target to be
verif ied(plaintext ), which has been input to the encrypt ing uni t 301, when
10 the Hamming distance between the these data is the certain value or less
(or, less than the cer tain value). And also such auxi l iary data is auxi l iary
informat ion that is used to determine that the input data is not matched
wi th the data of the target to be veri fied when the Hamming distance
between the data exceeds the above-descr ibed certain value (or, the cer tain
15 value or more) .
The encrypted data that is output f rom the encrypt ing uni t 301 of the
data concealment apparatus 300 is calculated through the same method
(manner) as the encrypt ing uni t 101. That is, when the encrypted data
that is obtained by encrypt ing the input data m1 using the key k1 is t reated
20 as "c1", and the encrypted data that is obtained by encrypt ing the input
data m2 using the key k2 is treated as "c2", the sum of "c1" and "c2", that
is, "c1+c2" becomes the encrypted data that is obtained by encrypt ing the
input data m1+m2 by using the key k1+k2.
The speci ficat ion data veri ficat ion apparatus 400 includes an ident i fier
25 holding uni t 401, an encrypted data subt ract ion uni t 402, a match
determinat ion uni t 403, and a control uni t 404.
The ident i fier holding uni t 401 accepts an ident ifier as an input . The
ident if ier holding uni t 401 issues an inst ruct ion to output of encrypted data
data and auxi l iary data that correspond to the ident i fier that has been input
15
to the storage apparatus 200, for the ident ifier management uni t 201 of the
storage apparatus 200.
The encrypted data subtract ion uni t 402 accepts fol lowing data as inputs.
That is the encrypted data subtract ion uni t 402 accepts one piece of data
among encrypted data (encrypted regist rat ion data) that are stored in th5 e
encrypted data storage uni t 202 of the storage apparatus 200 , and the
encrypted data that is output f rom the encrypt ing uni t 301 of the data
concealment apparatus 300. The encrypted data subtract ion uni t 402
outputs a di f ference between the two pieces of input encrypted data c1 and
10 c2, that is c1-c2.
When the encrypted data that is obtained by encrypt ing the input data
m1 using the key k1 is treated as "c1", and the encrypted data that is
obtained by encrypt ing the input data m2 using the key k2 is treated as "c2",
due to the featureof the encrypt ing uni t 101 and the encrypt ing uni t 301,
15 the di fference c1-c2 between the two encrypted data c1 and c2 becomes an
encrypted data that is obtained by encrypting input data m1-m2 using a key
k1-k2.
The match determinat ion uni t 403 accepts the fol lowing data as inputs.
That is , match determinat ion uni t 403 accept one piece of data among
20 auxi l iary data that are stored in the auxi l iary data storage uni t 203 of the
storage apparatus 200, the auxi l iary data that is output f rom the auxi l iary
data generat ion uni t 303 of the data concealment apparatus 300 , and the
dif ference between the two pieces of encrypted data, which is output f rom
the encrypted data subtract ion uni t 402.
25 The match determinat ion uni t 403 outputs whether or not a
Hamming distance between the plaintexts m1 and m2 that respect ively
correspond to the two pieces of encrypted data c1 and c2 that has been
input to the encrypted data subt ract ion uni t 402, is the predetermined
certain value or less .
16
The control uni t 404 controls the communicat ion and the l ike when data
is transmi t ted and received between the data concealment apparatus 300
and the speci ficat ion data veri ficat ion apparatus 400.
Next , an operat ion in the first exemplary embodiment is described wi th
reference to the flow diagram i l lustrated in Fig. 3. The operat ion of th5 e
encrypted data verificat ion system according to the fi rst exemplary
embodiment is mainly divided into two phases of a data regist rat ion phase,
and an encrypted data veri ficat ion phase.
In the data regist rat ion phase, input data is input to the registrat ion data
10 generat ion apparatus 100, and such input data is encrypted , and registered
to the storage apparatus 200 wi th auxi l iary data.
In the encrypted data verificat ion phase, data that has been input to the
data concealment apparatus 300 is encrypted. In the encrypted data
verif icat ion phase, i t is determined whether or not the encrypted data and
15 auxi l iary data, that have been generated through the encrypt ing process,
correspond to plaintexts that are close (the Hamming distance of which is
the predetermined certain value or less ) to the plaintext that cor responds to
the the encrypted data and auxi l iary data in the storage apparatus, which
are specified by an ident ifier that is input separately.
20 In the data registrat ion phase, first , input data that is a target of
concealment (concealment target data) is input to the encrypt ing uni t 101
of the regist rat ion data generat ion apparatus 100 (step A1 in Fig. 3(A)).
Next , the key generat ion uni t 102 of the registrat ion data generat ion
apparatus 100 generates a key that is used to perform concealment of the
25 input data. After that , the key generat ion uni t 102 outputs the generated
key to the encrypt ing uni t 101 and the registrat ion auxi l iary data
generat ion uni t 103 (step A2 in Fig. 3(A)).
Next , the encrypt ing uni t 101 of the registrat ion data generat ion
apparatus 100 calculates encrypted data that is obtained by encrypt ing the
17
input data, based on the input data and the key. Af ter that , the encrypt ing
uni t 101 stores the calculated encrypted data in the encrypted data storage
uni t 202 (step A3 in Fig. 3(A)).
Next , fol lowing data are input to the registrat ion auxi l iary dat a
generat ion uni t 103. That is, the input data that has been input in the ste5 p
A1, the key that has been generated in the step A2, the encrypted data that
has been generated in the step A3 are input to the regist rat ion auxi l iary
data generat ion uni t 103. After that , auxi l iary data that has been output
from the registrat ion auxi l iary data generat ion uni t 103 is stored in the
10 auxi l iary data storage uni t 203 of the storage apparatus 200 (step A4 in Fig.
3(A)).
The ident i fier management uni t 201 assigns a unique ident i fier to the
data that has been input to the storage apparatus 200 , by the
above-described processing. By assigned ident i fier , the data that has
15 been input to the storage apparatus 200 can be refer red (read) .
In the encrypted data verificat ion phase, fi rst , an ident i fier is input to
the ident i fier holding uni t 401 of the specif icat ion data veri ficat ion
apparatus 400. Encrypted data (encrypted registrat ion data) that
corresponds to the input ident i fier is input f rom the encrypted data storage
20 uni t 202 of the storage apparatus 200 to the encrypted data subtract ion uni t
402. In addi t ion, auxi l iary data that cor responds to the input ident i fier is
input f rom the auxi l iary data storage uni t 203 to the match determinat ion
uni t 403 (step B1 in Fig. 3(B)).
Next , input data (data of a target to be checked) is input to the
25 encrypt ing uni t 301 of the data concealment apparatus 300 (step B2 in Fig.
3(B)).
Next , the key generat ion uni t 302 of the data concealment apparatus 300
generates a key that is used to per form concealment of the input data that
has been input in the step B2. After that , the key generat ion uni t 302
18
outputs the generated key to the encrypt ing uni t 301 and the auxi l iary data
generat ion uni t 303 (step B3 in Fig. 3(B)).
Next , the encrypt ing uni t 301 calculates encrypted data that is obtained
by encrypt ing the input data, based on the input data that has been input in
the step B2 and the key that has been input in the step B3. Af ter that , th5 e
encrypt ing uni t 301 inputs the calculated encrypted data to the encrypted
data subt ract ion uni t 402 of the specificat ion data veri ficat ion apparatus
400 (step B4 in Fig. 3(B)).
The encrypted data subt ract ion uni t 402, to which the encrypted data has
10 been respect ively input from the encrypted data storage uni t 202 of the
storage apparatus 200 and the encrypt ing uni t 301 of the data concealment
apparatus 300, outputs a di fference between the two pieces of the
encrypted data input , to the match determinat ion uni t 403 (step B5 in Fig.
3(B)).
15 Next , auxi l iary data are input to the match determinat ion uni t 403 f rom
the auxi l iary data storage uni t 203 of the storage apparatus 200 , and f rom
the auxi l iary data generat ion uni t 303 of the data concealment apparatus
300, that are cont rol led by the cont rol uni t 404, respect ively (step B6 in
Fig. 3(B)). In this case, the auxi l iary data storage uni t 203 and the
20 auxi l iary data generat ion uni t 303 may respect ively input the pieces of
auxi l iary data to the match determinat ion uni t 403 b y per forming the
communicat ion in cooperat ion.
As described above, to the match determinat ion uni t 403, the dif ference
between the two pieces of encrypted data is input f rom the encrypted data
25 subt ract ion uni t 402 in the step B5, and the auxi l iary data are respect ively
input f rom the auxi l iary data storage uni t 203 and the auxi l iary data
generat ion uni t 303 in the step B6. The match determinat ion uni t 403
determines whether or not a Hamming distance between the plaintext of the
encrypted data that has been input to the encrypted data subt ract ion uni t
19
402 in the step B1 and, the plaintext of the encrypted data that has been
input to the encrypted data subt ract ion uni t 402 in the step B4, is a
predetermined certain value or less , f rom these input data. The match
determinat ion uni t 403 outputs the determinat ion resul t ( step B7 in Fig.
3(B)5 ).
It is noted that the apparatuses 100, 200, 300, and 400 of Fig. 1 may be
integrated into a single computer system, or may be configured as
respect ive apparatuses. Al ternat ively, the uni ts in each of the
apparatuses 100, 200, 300, and 400 may be configured as the respect ive
10 apparatuses . Processing of each of the uni ts in each of the apparatuses
may be achieved by a program that is executed in a computer. In this
case, in the present invent ion, a recording medium (semiconductor memory
or magnet ic/opt ical disk) to which the program is recorded may be
provided.
15
A second exemplary embodiment of the present invent ion is described
below. In the above-described encrypted data verificat ion system
according to the first exemplary embodiment , input data and an ident i fier
are input to the system, and veri ficat ion is per formed between a plaintext
20 of encrypted data that cor responds to the ident ifier , and the input data.
On the contrary, in the second exemplary embodiment , merely input data is
input to the system, and the system outputs an ident if ier of encrypted data
that is matched wi th the input data.
In the above-described fi rst exemplary embodiment , the
25 verif icat ion cal led as "one-to-one veri ficat ion" can be achieved, and in the
second exemplary embodiment , "1-to-many verif icat ion" can be achieved.
Refer ring to Fig. 2, the system according to the second exemplary
embodiment includes a registrat ion data generat ion apparatus 100, a
storage apparatus 200, a data concealment apparatus 300, and a data
20
verif icat ion apparatus 500. A configurat ion of the regist rat ion data
generat ion apparatus 100, the storage apparatus 200, and the data
concealment apparatus 300 is simi lar to that of the above-described fi rst
exemplary embodiment . In the system according to second exemplary
embodiment , the configurat ion of the data veri ficat ion apparatus 500 i5 s
dif ferent f rom the above-described system according to first exemplary
embodiment .
The regist rat ion data generat ion apparatus 100 includes an encrypt ing
uni t 101, a key generat ion uni t 102, and a registrat ion auxi l iary data
10 generat ion uni t 103. The encrypt ing uni t 101 accepts input data that is a
concealment target (concealment target data) and a key that is used to
perform concealment of the input data , as inputs. In addi t ion, the
encrypt ing uni t 101 outputs encrypted data that is obtained by execut ing
the encrypt ing processing for the input data using the key.
15 The key generat ion uni t 102 generates the key that is used to
perform concealment of the input data by the encrypt ing uni t 101. After
that (key generat ion) , the key generat ion uni t 102 outputs the generated
key to the encrypt ing uni t 101 and the registrat ion auxi l iary data
generat ion uni t 103.
20 The registrat ion auxi l iary data generat ion uni t 103 accepts the input
data, the encrypted data that has been output from the encrypt ing uni t , and
the key that has been output f rom the key generat ion uni t 102, as inputs.
After that , the regist rat ion auxi l iary data generat ion uni t 103 outputs
data (auxi l iary data) that is used to determine that a Hamming distance,
25 between input data that cor responds to encrypted data that is output from
the encrypt ing uni t 301 of the data concealment appar atus 300 and the
input data that is input to the encrypt ing uni t 101, is wi thin a certain
numeric value, f rom the accepted inputs.
The encrypted data that is output f rom the encrypt ing uni t 101 of the
21
regist rat ion data generat ion apparatus 100 sat isfies the fol lowing
relat ionship. That is , the relat ionship includes that when the encrypt ing
uni t 101 treats an encrypted data that is obtained by encrypt ing input data
m1 using a key k1, as "c1", and t reats an encrypted data, that is obtained by
encrypt ing input data m2 using a key k2, as "c2", the sum of "c1" and "5 c2",
that is, "c1+c2" becomes an encrypted data that is obtained by encrypt ing
input data m1+m2 by using a key k1+k2.
The storage apparatus 200 includes an ident if ier management uni t 201,
an encrypted data storage uni t 202, and an auxi l iary data storage uni t 203.
10 The storage apparatus 200 stores encrypted data and registrat ion auxi l iary
data that is output f rom the registrat ion data generat ion apparatus . In
addi t ion, the storage apparatus 200 outputs encrypted data and auxi l iary
data that cor respond to an ident if ier that is input from the data veri ficat ion
apparatus 500, when the encrypted data is veri fied.
15 The ident i fier management uni t 201 manages an ident i fier that is used to
uniquely ident if y encrypted data and auxi l iary data that are input from the
regist rat ion data generat ion apparatus 100. After that , when the
ident if ier has been input f rom the data veri ficat ion apparatus 500, the
ident if ier management uni t 201 issues an instruct ion of output of encrypted
20 data and auxi l iary data that correspond to the input ident i fier , to the
encrypted data storage uni t 202 and the auxi l iary data storage uni t 203.
The encrypted data storage uni t 202 stores the encrypted data that has been
output from the encrypt ing uni t 101 of the regist rat ion data generat ion
apparatus 100. Af ter that , when the inst ruct ion of output of encrypted
25 data has been input f rom the ident i fier management uni t 201, the encrypted
data storage uni t 202 outputs the corresponding encrypted data. The
auxi l iary data storage uni t 203 stores the auxi l iary data that has been
output from the registrat ion auxi l iary data generat ion uni t 103 of the
regist rat ion data generat ion apparatus 100. After that , when the
22
instruct ion of output of encrypted data has been input f rom the ident if ier
management uni t 201, the auxi l iary data storage uni t 203 performs output s
the cor responding auxi l iary data.
The data concealment apparatus 300 includes an encrypt ing uni t 301, a
key generat ion uni t 302, and an auxi l iary data generat ion uni t 3035 .
The encrypt ing uni t 301 accepts input data that is a concealment target
(concealment target data) , and a key that is used to per form concealment of
the input data, as inputs. After that , the encrypt ing uni t 301 performs
output of encrypted data that is obtained by execut ing the encrypt ing
10 processing for the input data by using the key. The key generat ion uni t
302 generates a key that is used to perform concealment of the input data
by the encrypt ing uni t 301, and outputs the generated key to the encrypt ing
uni t 301 and the auxi l iary data generat ion uni t 303.
The auxi l iary data generat ion uni t 303 accepts the input data, the
15 encrypted data that has been output f rom the encrypt ing uni t , and the key
that has been output from the key generat ion uni t 302, as inputs. After
that , based on the input data, the auxi l iary data generat ion uni t 303 outputs
auxi l iary data that is used to determine that a Hamming distance, between
input data that cor responds to the encrypted data that is output f rom the
20 encrypt ing uni t 101 of the regist rat ion data generat ion apparatus 100 and
the input data that has been input to the encrypt ing uni t 301, is less than a
predetermined certain value.
The encrypted data that is output f rom the encrypt ing uni t 301 of
the data concealment apparatus 300 is calculated by the same method as
25 that of the encrypt ing uni t 101. That is , when the encrypt ing uni t 301
treats the encrypted data that is obtained by encrypt ing the input data m1
using the key k1, as "c1", and t reats the encrypted data that is obtained by
encrypt ing the input data m2 using the key k2, as "c2", the sum of "c1" and
"c2", that is, "c1+c2" becomes the encrypted data that is obtained by
23
encrypt ing the input data m1+m2 using the key k1+k2.
The data veri ficat ion apparatus 500 includes an ent ire-data request uni t
501, an encrypted data subt ract ion uni t 502, a match determinat ion uni t
503, a cont rol uni t 504, and an ident i fier output uni t 505.
The ent i re-data request uni t 501 inputs an instruct ion of sequent ial rea5 d
of al l data that are stored in the storage apparatus, to the ident ifier
management uni t 201, in response to an instruct ion f rom the ident ifier
output uni t 505.
The encrypted data subt ract ion uni t 502 accepts one piece of data among
10 encrypted data that are stored in the encrypted data storage uni t 202 of the
storage apparatus 200, and the encrypted data that is output f rom the
encrypt ing uni t of the data concealment apparatus 300, as inputs. After
that , the encrypted data subt ract ion uni t 502 per forms output of a
dif ference c1-c2 between the input encrypted data c1 and c2.
15 When the encrypted data that is obtained by encrypt ing the input data m1
using the key k1, is t reated as "c1", and the encrypted data that is obtained
by encrypt ing the input data m2 using the key k2, is t reated as "c2" due to
the feature of the encrypt ing uni t 101 and the encrypt ing uni t 301, a
dif ference c1-c2 between the two encrypted data c1 and c2 becomes the
20 encrypted data that is obtained by encrypt ing the input data m1-m2 using
the key k1-k2.
The match determinat ion uni t 503 accepts the fol lowing data, as
inputs. That is , the match determinat ion uni t 503 accepts one piece of
data among auxi l iary data that are stored in the auxi l iary data storage uni t
25 203 of the storage apparatus 200, the auxi l iary data that is output from the
auxi l iary data generat ion uni t 303 of the data concealment apparatus 300 ,
and the encrypted data that is output f rom the encrypted data subtract ion
uni t 402.
The encrypted data subtract ion uni t 502 outputs whether or not a
24
Hamming distance, between the plaintexts m1 and m2 that respect ively
correspond to the two pieces of encrypted data c1 and c2 that has been
input to the encrypted data subtract ion uni t 502, is a predetermined cer tain
value or less (or less than the certain value) , based on the accepted pieces
of input data5 .
The control uni t 504 controls the communicat ion when data is
transmi t ted and received between the data concealment apparatus 300 and
the data ver ificat ion apparatus 500.
The ident i fier output uni t 505 accepts , an ident i fier that has been used
10 by the ident i fier management uni t 201 to issue an inst ruct ion of output of
data to the encrypted data storage uni t 202 and the auxi l iary data storage
uni t 203, and a determinat ion resul t that has been output from the match
determinat ion uni t 503, as inputs. When the match determinat ion uni t
503 determines that the matching is per formed successful ly( that is, the
15 determinat ion resul t indicates that input plaintext matches plaintext of
registered data ) , the ident if ier output uni t 505 outputs the ident ifier that
has been input f rom the ident i fier management uni t 201.
An operat ion in the second exemplary embodiment is described below
wi th reference to the flow diagram illust rated in Fig. 4. The operat ion of
20 the encrypted data veri ficat ion system according to the second exemplary
embodiment is divided into two phases of a data regist rat ion phase, and an
encrypted data verificat ion phase.
In the data regist rat ion phase, input data is input to the registrat ion
data generat ion apparatus 100, and such input data is encrypted, and
25 registered to the storage apparatus 200 wi th auxi l iary data. In the
encrypted data verificat ion phase, data that has been input to the data
concealment apparatus 300 is encrypted. In addi t ion, in the encrypted
data veri ficat ion phase, the ident i fier, cor responds to the encrypted data,
stored in the the storage apparatus 200 is output . That is , the ident ifier,
25
corresponds to the encrypted data, to which the plaintext , that is close to
the encrypted data and the auxi l iary data (the Hamming distance between
the plaintext and plaintexts of those data is smal l ) that are generated
through encrypt ing of input data, is encrypted.
In the data registrat ion phase, first , input data that is a conceal target i5 s
input to the encrypt ing uni t 101 of the registrat ion data generat ion
apparatus 100 (step C1 in Fig. 4(A)).
Next , the key generat ion uni t 102 of the registrat ion data generat ion
apparatus 100 generates a key that is used to perform concealment of the
10 input data. After that , the key generat ion uni t 102 outputs the generated
key to the encrypt ing uni t 101 and the registrat ion auxi l iary data
generat ion uni t 103 (step C2 in Fig. 4(A)).
Next , the encrypting uni t 101 calculates encrypted data that is obtained
by encrypt ing the input data, f rom the input data and the key. After that ,
15 the encrypt ing uni t 101 stores the calculated encrypted data in the
encrypted data storage uni t 202 (step C3 in Fig. 4(A)).
Next , the input data that has been input in the step C1, the key that has
been generated in the step C2, and the encrypted data that has been
generated in the step C3 are input to the registrat ion auxi l iary data
20 generat ion uni t 103. After that , an output (auxi l iary data) of the
regist rat ion auxi l iary data generat ion uni t 103 is stored in the auxi l iary
data storage uni t 203 of the storage apparatus 200 (step C4 in Fig. 4(A)).
Through the above-described processing, a unique ident ifier is assigned
to data (encrypted data and auxi l iary data) that is stored in the storage
25 apparatus 200, in the ident i fier management uni t 201. The pieces of data
that are stored in the storage apparatus 200 can be referred( read) by the
assigned ident i fier .
In the encrypted data verificat ion phase, fi rst , input data is input to the
encrypt ing uni t of the data concealment apparatus 300 (step D1 in Fig.
26
4(B)).
Next , the key generat ion uni t 302 of the data concealment apparatus 300
generates a key that is used to per form concealment of the input data.
After that , the key generat ion uni t 302 outputs the generated key to the
encrypt ing uni t 301 and the auxi l iary data generat ion uni t 303 (step D2 i5 n
Fig. 4(B)).
Next , the encrypt ing uni t 301 calculates encrypted data that is obtained
by encrypt ing the input data, f rom the input data that has been input in the
step D1, and the key that has been input in the step D2. After that , the
10 encrypt ing uni t 301 inputs the calculated encrypted data to the encrypted
data subtract ion uni t 502 of the data verificat ion apparatus 500 (step D3 in
Fig. 4(B)).
Next , an ident i fier is input f rom the ent ire-data request uni t 501 to the
ident if ier management uni t 201. After that , the encrypted data that
15 corresponds to the input ident i fier is input f rom the encrypted data storage
uni t 202 of the storage apparatus 200 to the encrypted data subtract ion uni t
502. In addi t ion, auxi l iary data that cor responds to the input ident i fier is
input f rom the auxi l iary data storage uni t 203 to the match determinat ion
uni t 503 (step D4 in Fig. 4(B)).
20 The encrypted data subt ract ion uni t 502 to which the encrypted data has
been respect ively input from the encrypted data storage uni t 202 of the
storage apparatus 200 and the encrypt ing uni t 301 of the data concealment
apparatus 300, outputs a di fference between the two pieces of input
encrypted data, to the match determinat ion uni t 503 (step D5 in Fig. 4(B)).
25 Next , the pieces of auxi l iary data are respect ively input f rom the
auxi l iary data storage uni t 203 of the stor age apparatus 200 and the
auxi l iary data generat ion uni t 303 of the data concealment apparatus 300 ,
to the match determinat ion uni t 503 (step D6 in Fig. 4(B)). In this case,
the auxi l iary data storage uni t 203 and the auxi l iary data generat ion uni t
27
303, that are cont rol led by the cont rol uni t 504, respect ively input those
data to the match determinat ion uni t 503 by, communicat ing in
coordinat ion.
As described above, to the match determinat ion uni t 503, the dif ference
between the two pieces of encrypted data is input in the step D5, and th5 e
auxi l iary data is input in the step D6.
The match determinat ion uni t 503 determines whether or not a
Hamming distance between the plaintext of the encrypted data that has
been input to the encrypted data subt ract ion uni t 502 in the step D3, and
10 the plaintext of the encrypted data that has been input to the encrypted data
subt ract ion uni t 502 in the step D4, is a predetermined cer tain value or less ,
from these input data. In addi t ion, the match determinat ion uni t 503
outputs the determinat ion resul t ( step D7 in Fig. 4(B)).
When i t is determined that the matching is successful ly per formed in the
15 resul t of the step D7, that is, the determinat ion resul t indicates that input
plaintext matches plaintext of registered data, the ident if ier output uni t
505 per forms output of the ident ifier that has been input to the ident i fier
management uni t 201 in step D4 (step D8 in Fig. 4(B)).
The processing f rom the steps D4 to D8 is repeated for al l ident ifiers
20 (cor responding to al l of encrypted data and auxi l iary data) that are stored
in the storage apparatus 200, which are managed by the ident if ier
management uni t 201 of the storage apparatus 200 .
It is noted that the apparatuses 100, 200, 300, and 500 in Fig. 2 may be
integrated into a single computer system. In addi t ion, the apparatuses
25 may be configured as respect ive apparatuses. Al ternat ively, the uni ts in
each of the apparatuses 100, 200, 300, and 400 may be configured as
respect ive apparatuses. The processing of each of the uni ts in each of the
apparatuses in Fig. 1 may be achieved by a program that is executed by a
computer . In this case, in the present invent ion, a recording medium
28
(semiconductor memory or magnet ic/opt ical disk) to the program has been
recorded is provided. The above exemplary embodiment s are described
below wi th reference to a further speci fic example.

Next , a first example of the present invent ion is described in detai l wi 5 th
reference to Fig. 1. The fi rst example is a specif ic example of the
above-described fi rst exemplary embodiment .
In the data registrat ion phase, first , as input data, a binary
sequence(st ring) "Z" of "N" bi ts is input to the encrypt ing uni t 101 of the
10 regist rat ion data generat ion apparatus 100.
Next , the key generat ion uni t 102 of the registrat ion data generat ion
apparatus 100 generates a key (random number of "K" bi ts) "S", and
outputs the generated key to the encrypt ing uni t 101 and the registrat ion
auxi l iary data generat ion uni t 103.
15 Next , the encrypt ing uni t 101 calculates encrypted data "W1" of "N" bi ts,
which is obtained by calculat ing an XOR between a code word "C" of "N"
bi ts, which has been obtained by encoding the input key "S" of "K" bi ts
using a binary BCH code, and the input data "Z" of "N" bi ts (see, the
fol lowing Eqn. (1)). In addi t ion, the encrypt ing uni t 101 stores the
20 calculated encrypted data "W1" in the encrypted data storage uni t 202 of
the storage apparatus 200.
W1=C(+)Z … (1)
Here, calculat ion symbol "(+)" indicates a bi twise XOR. It is
assumed that the binary BCH code used herein is a code that outputs data
25 of "N"-bi ts from input data of "K"-bi ts ("N" > "K"). And, It is also
assumed that such BCH code is a code that guarantees that Hamming
distance between di f ferent code words is at least "d" or more.
Next , the input data "Z", the key "S", and the encrypted data "W1" are
input to the regist rat ion auxi l iary data generat ion uni t 103. The
29
regist rat ion auxi l iary data generat ion uni t 103 calculates auxi l iary data
"W2", based on the inputs, in accordance wi th the fol lowing Eqn. (2).
W2=(c,S) (+)h(W1,n) … (2)
Here, in the above-described Eqn. (2), the "c" is a constant of "K" bi ts.
The "n" is a random number of "k" bi ts ("k" is a securi ty parameter ). Th5 e
securi ty parameter is a parameter that indicates the st rength of the safety,
and is a predetermined value that has been defined by the system. The
"(c,S)" indicates an inner product . That is, "(A,B)" indicates an inner
product of "A" and "B", when regarding the pieces of data of "A" and "B"
10 (of which size respect ively is "K=(m*k) bi ts ") as ar ranged vectors into
which divided "A" and "B" is divided for each k bi ts (i t is assumed that the
calculat ion is per formed on the Galois field GF (2k) ). In addi t ion, "(+)"
indicates a bi twise XOR. In addi t ion, "h" is a cryptographic (one-way)
hash funct ion which generates the output data of "k" bi ts ( for example,
15 SHA-256 or the l ike) .
H (x,y,z) is defined as a funct ion that is represented by the fol lowing
Eqn. (3).
H (x,y,z)=(c,z) (+)h(y,z) … (3)
H (x,y,z) sat isfies the fol lowing Eqn. (4).
20 H (a1,b1,c1) (+)H(a2,b2,c2)=H(a1(+)a2,b1,c1) (+)h(b2,c2) … (4)
In addi t ion, for a random number "r" of "(K-k)" bi ts, a code word data
that is obtained by execut ing error -correct ing coding to the data
represented wi th fol lowing Eqn. (5) , by using the BCH code, is treated as
"C3" (here, "/ /" is a calculat ion symbol that indicates bi t concatenat ion) .
25 "h(W1,N) // r … ( 5 )"
And "W3" is calculated f rom "C3" and "Z" in accordance wi th the
fol lowing Eqn. (6).
W3=C3(+)Z … (6)
The regist rat ion auxi l iary data generat ion uni t 103 registers the set of
30
"(W2,W3)" that has been calculated in accordance wi th the
above-described Eqns. (2) and (6), to the auxi l iary data storage uni t 203, as
auxi l iary data.
In the above-descr ibed processing, to the data that has been input to the
storage apparatus 200, a unique ident i fier is assigned by the ident i fie5 r
management uni t 201. After that , the input data can be referred by using
the assigned ident ifier .
Hereinafter , encrypted data "W1", and pieces of auxi l iary data "W2" and
"W3" that are associated wi th an ident ifier "i" are respect ively represented
10 as "W1[ i]", "W2[ i] ", and "W3[ i]".
In the encrypted data verificat ion phase, fi rst , the ident i fier "i" is input
to the ident i fier holding uni t 401 of the speci ficat ion data ver ificat ion
apparatus 400. The encrypted data "W1[ i] " that cor responds to the input
ident if ier "i" is read (refer red) f rom the encrypted data storage uni t 202 of
15 the storage apparatus 200, and is input to the encrypted data subtract ion
uni t 402. In addi t ion, the pieces of auxi l iary data "W2[ i] " and "W3[ i] "
that cor respond to the input ident i fier "i" are read (refer red) f rom the
auxi l iary data storage uni t 203, and are input to the match determinat ion
uni t 403.
20 Next , binary sequence input data "Z'" of "N" bi ts (data to be veri fied) is
input to the encrypt ing uni t 301 of the data concealment apparatus 300 .
Next , the key generat ion uni t 302 of the data concealment apparatus 300
generates a key ( random number of "K" bi ts) "S'" that is used to per form
concealment of the input data "Z'", and outputs the generated key to the
25 encrypt ing uni t 301 and the auxi l iary data generat ion uni t 303 .
The encrypt ing uni t 301 of the data concealment apparatus 300
calculates the encrypted data "W1'" that is obtained by calculat ing an XOR
between the code word "C'" and the input data "Z'". Here, "C'" is obtained
by performing er ror -correct ing coding by using the binary BCH code on
31
the key "S'", that has been input f rom the key gene rat ion uni t 302. After
that , the encrypt ing uni t 301 inputs the calculated encrypted data "W1'", to
the encrypted data subtract ion uni t 402 of the speci ficat ion data
verif icat ion apparatus 400.
W1'=C'(+)Z' … (5 7)
To the encrypted data subt ract ion uni t 402, the encrypted data "W1'"
from the encrypt ing uni t 301 of the data concealment apparatus 300 , and
the encrypted data "W1[ i] " that corresponds to the ident i fier ”i ” f rom the
encrypted data storage uni t 202 of the storage apparatus 200 are input .
10 The encrypted data subtract ion uni t 402 calculates a dif ference (XOR)
between the two pieces of input encrypted data "W1'" and "W1[ i] ", that is,
calculated wi th fol lowing Eqn. (8).
"W1'(+)W[ i] … ( 8 )"
And the encrypted data subt ract ion uni t 402 outputs the calculated
15 dif ference to the match determinat ion uni t 403 .
Next , for a random number "ns" and an element (generator ) "g" of a
group "G" that has been defined beforehand (mul t ipl icat ive group "Zp"),
the cont rol uni t 404 calculates fol lowing Eqn. (9).
"g_s=g**ns" … (9)".
20 In the Eqn. (9), i t is assumed that "g**ns" indicates the ns-th power of
"g" on the group "G" (mul t ipl icat ive group "Zp") ("**" is an
exponent iat ion operator ). The group "G" is a cycl ic group for the
mul t ipl icat ive. The group "G" is const i tuted by a mul t ipl icat ive group
"Zp (=Z/pZ) " of a digi t number "p", using "p" as a prime number . And
25 the value of "g**ns" is given by a mod "p" using the prime number "p" as
modulo.
The control uni t 404 outputs "W3[ i] " and "g_s" to the auxi l iary data
generat ion uni t 303.
Next , the auxi l iary data generat ion uni t 303 of the data concealment
32
apparatus 300 appl ies decoding processing of the binary BCH code to a
value that is obtained by calculat ing an XOR between "W3[ i]" and the
input data "Z'", that is calculated wi th fol lowing Eqn. (10).
W3 [ i ] ( +) Z ' … ( 1 0 )
As the resul t of the calculat ion, the auxi l iary data generat ion uni 5 t
303 obtains "h'" that is the decrypt ion resul t .
The auxi l iary data generat ion uni t 303 calculates "W2'" and "g_c", f rom
the key "S'", the encrypted data "W1'", "h'", "g", and "g_s", and the random
number "nc", based on the fol lowing Eqns. (11a) and (11b), and outputs the
10 calculated "W2'" and "g_c" to the match determinat ion uni t 403 of the data
verif icat ion apparatus 400.
W2'=H(S',W1' ,g_s**nc) (+)h' … (11a)
g_c=g**nc … (11b)
In the above-descr ibed Eqn. (11a) , when "g" is t reated as a generator of
15 the mul t ipl icat ive group "Zp", "g" and "p" are publ ished, and two part ies
"X" and "Y" respect ively calculate "A=g**ns (=g**ns mod p)" and
"B=g**nc (=g**nc mod p) " using "ns" and "nc" (private keys) . "X"
transmi ts "A" to "Y", and "Y" transmi ts "B" to "X". "X" calculates
"B**ns=g**(ns*nc) (=g**(ns*nc)mod p) " using "ns" and "B" that has been
20 received f rom "Y". And "Y" calculates "A**nc=g** (ns*nc)
(=g**(ns*nc)mod p) " using "nc" and "A" that has been received f rom "X".
The calculated "g**(ns*nc)mod p" is used as a key of common key
encrypt ion by "X" and "Y" (Di ff ie-Hel lman key exchange). Even if a
third party obtains "A" and "B" by eavesdropping or the l ike, there is no
25 method of calculat ing "g** (ns*nc)mod p" f rom "A" and "B", so that i t is
dif ficul t to generate the key. In addi t ion, in the calculat ion of "g**ns", a
value, on which Di ffie-Hel lman key exchange has been per formed, is set as
a random number component (NONCE), so that for example, defense
against replay at tacks is achieved in the appl icat ion to biomet r ic
33
ident if icat ion, that is described later .
Next , the match determinat ion uni t 403 appl ies the decoding processing
of the binary BCH code, to the dif ference between the two pieces of input
encrypted data "W1'" and "W[ i]", that is calculated wi th fol lowing Eqn.
(12)5 .
W1'(+)W[ i] …(12)
And the match determinat ion uni t 403 calculates "T" that is the
decrypt ion resul t of the dif ference between the two pieces of encrypted
data "W1'" and "W[ i ]".
10 In addi t ion, the match determinat ion uni t 403 determines whether or not
a calculat ion resul t of an XOR between
"H(T,W1' ,g_c**ns) (=(g_c**ns,T)+h(W1' ,g_c**ns)) " and "W2'" is equal to
"W2[ i ]". The equat ion
"H(T,W1' ,g_c**ns) (=(g_c**ns,T)+h(W1' ,g_c**ns)) " is calculated using
15 the decrypt ion resul t "T" of the dif ference between the two pieces of
encrypted data "W1'" and "W[ i]", "W1'", and "g_c**ns". "W2'" is
calculated in accordance wi th the Eqn. (11a). In other words, the match
determinat ion uni t 403 checks (veri fies) whether or not the next Eqn. (13)
is sat isfied.
20 W2[ i]=H(T,W1',g_c**ns) (+)W2' … (13)
When the above-described Eqn. (13) is sat isf ied, the match
determinat ion uni t 403 determines that a Hamming distance between the
original data (plaintext ) of "W1[ i] " and the input data (plaintext ) "Z'" is
"d" or less. When the above-described Eqn. (13) is not sat isfied, the
25 match determinat ion uni t 403 determines that the Hamming distance
between the original data (plaintext ) of "W1[ i]" and the input data
(plaintext ) "Z'" exceeds "d". After that , the match determinat ion uni t 403
outputs the determinat ion resul t . It is noted that , in the above-described
BCH coding, a Hamming distance between given di fferent code words is
34
assumed to be a value that exceeds "d" at least .
Here, "g_s**nc(=(g**ns)**nc) " in the auxi l iary data
"W2'=H(S',W1' ,g_s**nc) (+)h'" that is generated by the auxi l iary data
generat ion uni t 303 of the data concealment apparatus 3 00, and
"g_c**ns(=(g**nc)**ns) " in the match determinat ion uni t 403 of th5 e
speci ficat ion data verif icat ion apparatus 400, may be generated, for
example, in both of the auxi l iary data generat ion uni t 303 an d the match
determinat ion uni t 403 through the known Di f fie-Hel lman key exchange
method.
10
Next , a second example is described in detai l wi th reference to Fig. 2.
The second example is a speci fic example of the above-described second
exemplary embodiment .
In the data registrat ion phase, first , as input data, a binary sequence "Z"
15 of "N" bi ts is input to the encrypt ing uni t 101 of the registrat ion data
generat ion apparatus 100.
Next , the key generat ion uni t 102 of the registrat ion data generat ion
apparatus 100 generates a random number "S" of "K" bi ts. In addi t ion,
the key generat ion uni t 102 outputs the generated random number "S" (key)
20 to the encrypt ing uni t 101 and the regist rat ion auxi l iary data generat ion
uni t 103.
Next , the encrypt ing uni t 101 calculates encrypted data "W1" that is
obtained by calculat ing an XOR between the code word "C" that is
obtained by coding the input key "S" through the binary BCH code, and the
25 input data "Z". In addi t ion, the encrypt ing uni t 101 stores the calculated
encrypted data "W1" in the encrypted data storage uni t 202. The binary
BCH code used herein is a code outputs data of "N"-bi ts from input data of
"K"-bi ts ("N" > "K") . And also, such BCH code is a code that guarantees
that Hamming distance between di fferent code words is at least "d" or
35
more.
Next , the input data "Z", the key "S", and the encrypted data "W1" are
input to the regist rat ion auxi l iary data generat ion uni t 103. The
regist rat ion auxi l iary data generat ion uni t 103 calculates "W2", based on
the inputs, in accordance wi th the fol lowing Eqn. (14)5 .
W2=(c,S) (+)h(W1,n) … (14)
Here, in the above-described Eqn. (14), "c" is a constant of "K" bi ts.
In addi t ion, "n" is a random number of "k" bi ts ("k" is a securi ty
parameter) . In addi t ion, "(A,B)" indicates an inner product of "A" and
10 "B" when each of the two pieces of data "A" and "B" of "K=(m*k)" bi ts is
regarded as a vector into which "A" and "B" is divided for each "k" bi ts (i t
is assumed that the calculat ion is per formed on the Galois field GF (2k) ).
The calculat ion symbol "(+)" indicates a bi twise XOR. The symbol "h" is
a cryptographic (one-way) hash funct ion in which the output cor responds
15 to k bi ts ( for example, SHA-256 or the l ike).
In addi t ion, "H(x,y,z)" is defined as a funct ion that is represented by the
Eqn. (15) (same as the above-described Eqn. (3)).
H(x,y,z)=(c,x)(+)h(y,z) … (15)
For the random number "r" of "(K-k)" bi ts, the code word data that is
20 obtained by encoding the data represented wi th fol lowing Eqn. (16), by
using the BCH code, is treated as "C3" (here, "//" is a symbol that indicates
bi t concatenat ion) .
h(W1,N) // r … (16)
And "W3" is calculated in accordance wi th the fol lowing Eqn. (17) ,
25 from "C3" and "Z".
W3=C3(+)Z … (17)
The regist rat ion auxi l iary data generat ion uni t 103 registers the set of
"(W2,W3)" that has been generated as described above, to the auxi l iary
data storage uni t 203, as auxi l iary data.
36
In the above-descr ibed processing, a unique ident ifier is assigned to the
data that has been input to the storage apparatus 200 by the ident i fier
management uni t 201. And after that , the data that is input to the storage
apparatus 200 can be referred by the assigned ident i fier . Hereinafter,
"W1", "W2", and "W3" that are associated wi th the ident i fier "i" ar5 e
respect ively represented as "W1[ i]", "W2[ i]", and "W3[ i]".
In the encrypted data verif icat ion phase, fi rst , input data "Z'" (data to be
checked) is input to the encrypt ing uni t 301 of the data concealment
apparatus 300.
10 Next , the key generat ion uni t 302 of the data concealment apparatus 300
generates a key "S'" (random number of "K" bi ts) that is used to per form
concealment of the input data "Z'". In addi t ion, the key generat ion uni t
302 outputs the generated key "S'" to the encrypt ing uni t 301 and the
auxi l iary data generat ion uni t 303.
15 The encrypt ing uni t 301 calculates encrypted data "W1'" that is obtained
by calculat ing an XOR between the code word "C'" that is obtained by
coding the input key "S'" through the binary BCH code, and the input data
"Z'". That is, "W1'" is calculated in accordance wi th fol lowing Eqn. (18).
W1'=C'(+)Z' … ( 1 8 )
20 In addi t ion, the encrypt ing uni t 301 inputs the calculated "W1'" to the
encrypted data subt ract ion uni t 502 of the data veri ficat ion apparatus 500.
Next , the ident i fier "i" is input from the ent i re-data request uni t 501 to
the ident i fier management uni t 201. The encrypt ion data "W1[ i]" that
corresponds to the input ident i fier "i" is read from the encrypted data
25 storage uni t 202 of the storage apparatus 200 , and is input to the encrypted
data subt ract ion uni t 502. In addi t ion, the pieces of auxi l iary data
"W2[ i]" and "W3[ i] " that correspond to the ident i fier "i" are read from the
auxi l iary data storage uni t , and are input to the match determinat ion uni t
503. The encrypted data subt ract ion uni t 502 accepts the encrypted data
37
"W1[ i]" from the encrypted data storage uni t 202 of the storage apparatus
200, and the encrypted data "W1'" f rom the data concealment apparatus
300, as inputs. After that , the encrypted data subt ract ion uni t 502 outputs
a dif ference (XOR) between the two pieces of input encrypted data "W1'"
and "W1[ i]", that is calculated in accordance wi th fol lowing Eqn. (19) , t5 o
the match determinat ion uni t 503.
W1'(+)W1[ i] … (19)
Next , the control uni t 504 calculates "g_s=g**ns … ( 2 0 )" for a random
number ns and an element (generator) "g" of a group (mul t ipl icat ive group
10 "Zp") "G" that is def ined beforehand, and outputs the calculated value to
the auxi l iary data generat ion uni t 303.
Next , the auxi l iary data generat ion uni t 303 of the da ta concealment
apparatus 300 randomly selects "S1'" and "S2'" that sat isfy fol lowing Eqn.
(21).
15 S'=S1' (+)S2' … (21)
The auxi l iary data generat ion uni t 303 of the data concealment
apparatus 300 calculates "W2'" and "g_c", based on the fol lowing Eqns.
(22a) and (22b).
W2'=H(S1' ,W1',g_s**nc) … (22a)
20 g_c=g**nc … (22b)
Next , the auxi l iary data generat ion uni t 303 of the data concealment
apparatus 300 calculates "W3'" from "C3" and "Z'". "C3" obtained by
performing the binary BCH er ror -cor rect ing coding on data that is obtained
by per forming bi t concatenat ion on an inner product "(c,S2')" and a random
25 number "r '". That is, the data is calculated in accordance wi th fol lowing
Eqn. (23).
(c,S2')// r ' … ( 2 3 )
"W3" is calculated in accordance wi th fol lowing Eqn. (24) .
W3'=C3(+)Z' … ( 2 4 )
38
In addi t ion, the auxi l iary data generat ion uni t 303 outputs "W1'", "W2'",
"W3'", and "g_c", to the match determinat ion uni t 503 of the data
verif icat ion apparatus 500.
Next , the match determinat ion uni t 503 appl ies the decoding processing
of the binary BCH code, to the dif ference between the pieces of inpu5 t
encrypted data, that i s calculated in accordance wi th fol lowing Eqn. (25).
W1'(+)W1[ i] … (25)
Then the match determinat ion uni t 503 calculates "T" that is the
decrypt ion resul t of the dif ference between the two pieces of encrypted
10 data "W1'" and "W1[ i]".
In addi t ion, the match determinat ion uni t 503 appl ies the decoding
processing of the binary BCH code , to an XOR between "W3[ i]" and "W3'",
that is calculated in accordance wi th fol lowing Eqn. (26)
W3[ i] (+)W3' … (26)
15 Then the match determinat ion uni t 503 calculates "w3" that is the
decrypt ion resul t of "W3[ i] (+)W3'".
The match determinat ion uni t 503 checks whether or not the resul t that
has been obtained by calculat ing a bi twise XOR between "W2'", "w3", and
"H(T,W1' ,g_c**ns) ", that has been calculated using the decrypt ion resul t
20 "T" of the di f ference between the two pieces of encrypted data "W1'" and
"g_c**ns", is equal to "W2[ i]". In other words, the match determinat ion
uni t 503 checks (veri fies) whether or not the Eqn. (27) is sat isf ied.
W2[ i]=H(T,W1',g_c**ns) (+)W2'(+)w3 … (27)
When the above-described Eqn. (27) is sat isf ied, the match
25 determinat ion uni t 503 determines that a Hamming distance between the
original data of "W1[ i]" and "Z'" is "d" or less. In this case, the ident i fier
output uni t 505 outputs the ident i fier "i". When the above-described Eqn.
(27) is not sat isfied, the match determinat ion uni t 503 determines that the
Hamming distance exceeds "d". In this case, the ident i fier output uni t
39
505 does not output the ident i fier "i".
The above-described operat ion is performed on al l ident i fiers "i" that
are managed by the storage apparatus, and the output of al l ident i fiers is
performed that include the or iginal data in which a Hamming distance wi th
the input data "Z'" becomes "d" or less5 .
In the second example, simi lar to the above-described fi rst example,
"g_s**nc(=(g**ns)**nc) " in the auxi l iary data
"W2'=H(S',W1' ,g_s**nc) (+)h' " that is generated in the auxi l iary data
generat ion uni t 303 of the data concealment apparatus 300 , and "g_c**ns
10 (=(g**nc)**ns)" in the match determinat ion uni t 503 of the data
verif icat ion apparatus 500 may be generated in both of the auxi l iary data
generat ion uni t 303 and the match determinat ion uni t 503, for example, by
the known Di f fie-Hel lman key exchange method.
As an appl icat ion example of the fi rst and second examples, there is
15 authent icat ion to protect biological informat ion. The out l ine of the
authent icat ion is des cribed below.
In this case, biological informat ion that is obtained f rom a f ingerprint ,
vein, or the l ike is t reated as input data in the data registrat ion phase and
input data in the encrypted data veri ficat ion phase.
20 In the above-described described system, i t can be determined
whether or not encrypted biometric data, that is stored in the storage
apparatus , and encrypted biomet ric data, that has been t ransmi t ted f rom the
data concealment apparatus , are obtained f rom an ident ical person, whi le
the biological informat ion remains concealed (encrypted) . In other words,
25 whether or not the pieces of biometr ic data are obtained f rom an ident ical
person can be determined depending on whether or not a Hamming distance
between these two pieces of input data is a predetermined certain value or
less. In addi t ion, in the above-described described system, the
authent icat ion can be performed based on such a determinat ion resul t .
40
Regarding biological informat ion, ident ical data may not be always
obtained stably. However , i t can be assumed that pieces of data that are
obtained f rom an ident ical person are simi lar to each other (pieces of data
of which the Hamming distance is smal l , may be obtained), so that the
authent icat ion is preferably appl ied to biomet ric ident i f icat ion. It i5 s
noted that in the biomet ric ident ificat ion appl icat ion, for example, each
value of parameters ("K", "s", "d") of the BCH may be obtained
experimental ly.
It is noted that each disclosure of the above-described Patent l i terature
10 and Non-Patent l i terature is assumed to be incorporated by reference
herein. Wi thin the ent i re disclosure of the present invent ion (including
claims), based on the basic technical concept , the exemplary embodiment s
and the examples can be modi fied and adjusted. In addi t ion, wi thin the
claims of the present invent ion, a variety of combinat ions or select ions can
15 be made f rom var ious disclosure element s (including element s in each of
claims, elements in each of the examples, elements in each of the drawings,
and the l ike) . In other words, the present invent ion includes various
changes and modi ficat ions that would be made by those ski l led in the art in
accordance wi th the ent i re disclosure including claims and the technical
20 idea, of course. In part icular , regarding the numerical range described
herein, i t should be understood that any number or sub-ranges contained
wi thin the claims is speci fical ly described even i f i t is not otherwise
stated.
[Reference signs List]
25 100 regist rat ion data generat ion apparatus
101 encrypt ing uni t
102 key generat ion uni t
103 regist rat ion auxi l iary data generat ion uni t
200 storage apparatus
41
201 ident if ier management uni t
202 encrypted data storage uni t
203 auxi l iary data storage uni t
300 data concealment apparatus
301 encrypt ing uni 5 t
302 key generat ion uni t
303 auxi l iary data generat ion uni t
400 speci ficat ion data verif icat ion apparatus
401 ident if ier holding uni t
10 402 encrypted data subt ract ion uni t
403 match determinat ion uni t
404 control uni t
500 data veri ficat ion apparatus
501 ent i re-data request uni t
15 502 encrypted data subt ract ion uni t
503 match determinat ion uni t
504 control uni t
505 ident if ier output uni t

WE CLAIMS:-
[Claim 1] An encrypted data veri ficat ion system comprising:
means for generat ing first and second auxi l iary data that are used to
verify, that a Hamming distance between a plaintext of a fi rst encrypted
data which is encrypted f rom input data and registered to a storag5 e
apparatus , and a plaintext of a second encrypted data which is encrypted
from input data of a target to be veri fied, is a predetermined certain value
or less, for the f irst encrypted data and the second encrypted data
respect ively; and
10 means for obtaining a dif ference between the f irst encrypted data
that is registered to the storage apparatus and the second encrypted data
that is obtained by encrypt ing the input data of the target to be veri fied,
and determining whether or not the Hamming distance of the plaintexts,
which cor responds to the di f ference between the first encrypted data and
15 the second encrypted data, is the predetermined certain value or less , using
the fi rst and second auxi l iary data.
[Claim 2] The encrypted data veri ficat ion system according to claim 1,
wherein
the system generates the encrypted data f rom calculat ion of an XOR
20 between a code word that is obtained by encrypt ing a key that is used to
encode the plaintext of the input data, through an er ror -cor rect ing code
having l ineari ty, and the plaintext , and
the system calculates each of the fi rst and second auxi l iary data that
are respect ively related to the fi rst encrypted data that is registered to the
25 storage apparatus and the second encrypted data that is obtained by
encrypt ing the input data of the target to be checked based on an XOR
between an inner product of the cor responding key and a constant , and an
output of a cryptographic hash funct ion for a bi t st ring based on the
corresponding encrypted data.
43
[Claim 3] The encrypted data veri ficat ion system according to claim 1
further comprising:
a regist rat ion data generat ion apparatus ;
a storage apparatus ;
a data concealment apparatus ; an5 d
a first data veri ficat ion apparatus , wherein
the registrat ion data generat ion apparatus includes:
a first encrypt ing uni t conf igured to accept input data of
fixed length and a key, as inputs, and output the fi rst encrypted
10 data that is obtained by encrypt ing the input data through the key,
that is, the fi rst encrypted data that sat isf ies a relat ionship that a
sum of an encrypted data 1 that is obtained by encrypt ing a
plaintext 1 through a key 1 and an encrypted data 2 that is obtained
by encrypt ing a plaintext 2 through a key 2 is equal to an encrypted
15 data that is obtained by encrypt ing a sum of the plaintext 1 and the
plaintext 2 through a sum of the key 1 and the key 2;
a first key generat ion uni t configured to generate the key
that is input to the fi rst encrypt ing uni t ; and
an registrat ion auxi l iary data generat ion uni t configured to
20 accept the input data and the key that is generated in the first key
generat ion uni t as inputs, and output the first auxi l iary data that is
used to ver ify that a Hamming distance of the plaintexts, which
corresponds to a dif ference between the f irst encrypted data that is
output from the fi rst encrypt ing uni t and the second encrypted data
25 that is output f rom the data concealment apparatus is a
predetermined certain value or less , and
the storage apparatus includes:
an encrypted data storage uni t configured to store the one or
more fi rst encrypted data that are output f rom the first encrypt ing
44
uni t of the regist rat ion data generat ion apparatus ;
an auxi l iary data storage uni t configured to store the one or
more pieces of fi rst auxi l iary data that are output from the
regist rat ion auxi l iary data generat ion uni t of the regist rat ion data
generat ion apparatus ; an5 d
an ident i fier management uni t configured to accept an
ident if ier from the fi rst data veri ficat ion apparatus , as an input , and
to al low the encrypted data storage uni t and the auxi l iary data
storage uni t to output the fi rst encrypted data and the fi rst auxi l iary
10 data that correspond to the ident i fier , respect ively, and
the data concealment apparatus includes:
a second encrypt ing uni t configured to accept input data of
fixed length, which is a veri ficat ion target , and a key, as inputs, and
output the second encrypted data that is obtained by encrypt ing the
15 input data of the target to be checked through the key, that is, the
second encrypted data that sat isfies a relat ionship that a sum of an
encrypted data 1 that is obtained by encrypting a plaintext 1
through a key 1 and an encrypted data 2 that is obtained by
encrypt ing a plaintext 2 through a key 2 is equal to an encrypted
20 data that is obtained by encrypt ing a sum of the plaintext 1 and the
plaintext 2 through a sum of the key 1 and th e key 2;
a second key generat ion uni t conf igured to generate the key
that is input to the second encrypt ing uni t ; and
an auxi l iary data generat ion uni t configured to accept the
25 input data of the target to be checked and the key that is generated
in the second key generat ion uni t , as inputs, and output the second
auxi l iary data that is used to veri fy that a Hamming distance of the
plaintexts, which cor responds to a dif ference between the second
encrypted data that is output f rom the second encrypt ing uni t and
45
the fi rst encrypted data that is output from the first encrypt ing uni t
of the regist rat ion data generat ion apparatus is a predetermined
certain value or less , and
the fi rst data verificat ion apparatus includes:
an ident i fier holding uni t configured to accept an ident i fie5 r
as an input , and output the ident i fier to the ident if ier management
uni t of the storage apparatus , and instructs the ident i fier
management uni t to perform output of the first encrypted data and
the fi rst auxi l iary data that correspond to the ident ifier;
10 an encrypted data subtract ion uni t configured to accept the
second encrypted data that is output f rom the second encrypt ing
uni t of the data concealment apparatus , and the fi rst encrypted data
that is stored in the encrypted data storage uni t of the storage
apparatus , as inputs, and output a di fference between the input two
15 encrypted data;
a match determinat ion uni t configured to accept the
dif ference between the encrypted data, which is output f rom the
encrypted data subt ract ion uni t , the f irst auxi l iary data that is
stored in the auxi l iary data storage uni t of the storage apparatus ,
20 and the second auxi l iary data that is output f rom the auxi l iary data
generat ion uni t of the data concealment apparatus , as inputs, and
determine whether or not a Hamming distance of the plaintext s,
which cor responds to the di f ference between the first and second
encrypted data is a predetermined certain value or less ; and
25 a control uni t configured to control t ransmission and
recept ion of data between the data concealment apparatus and the
first data veri ficat ion apparatus.
[Claim 4] The encrypted data checking system according to claim 1
further comprising:
46
a regist rat ion data generat ion apparatus ;
a storage apparatus ;
a data concealment apparatus ; and
a second data veri ficat ion apparatus, wherein
the registrat ion data generat ion apparatus includ5 e
a first encrypt ing uni t conf igured to accept input data of
fixed length and a key, as inputs, and output the fi rst encrypted data
that is obtained by encrypt ing the input data through the key, that is,
the fi rst encrypted data that sat isfies a relat ionship that a sum of an
10 encrypted data 1 that is obtained by encrypt ing a plaintext 1
through a key 1 and an encrypted data 2 that is obtained by
encrypt ing a plaintext 2 through a key 2 is equal to an encrypted
data that is obtained by encrypt ing a sum of the plaintext 1 and the
plaintext 2 through a sum of the key 1 and the key 2 ;
15 a first key generat ion uni t configured to generate the key
that is input to the fi rst encrypting uni t ; and
an registrat ion auxi l iary data generat ion uni t configured to
accept the input data and the key that is generated in the first key
generat ion uni t , as inputs, and output the first auxi l iary data that is
20 used to ver ify that a Hamming distance of the plaintexts, which
corresponds to a dif ference between the f irst encrypted data that is
output from the fi rst encrypt ing uni t and the second encrypted data
that is output f rom the data concealment apparatus is a
predetermined value or less , and
25 the storage apparatus includes:
an encrypted data storage uni t configured to store the one or
more fi rst encrypted data that are output f rom the first cipher
apparatus of the registrat ion data generat ion apparatus;
an auxi l iary data storage uni t configured to store the one or
47
more pieces of fi rst auxi l iary data that are output from the
regist rat ion auxi l iary data generat ion uni t of the regist rat ion data
generat ion apparatus ; and
an ident i fier management uni t configured to accept an
ident if ier from the second data verif icat ion apparatus, as an input 5 ,
and to al low the encrypted data storage uni t and the auxi l iary data
storage uni t to output fi rst encrypted data and the fi rst auxi l iary
data that correspond to the ident i fier , respect ively, and
the data concealment apparatus includes:
10 a second encrypt ing uni t configured to accept input data of
fixed length, which is a veri ficat ion target , and a key, as inputs, and
output the second encrypted data that is obtained by encrypt ing
the input data of the target to be checked through the key, that is,
the second encrypted data that sat isfies a relat ionship that a sum of
15 an encrypted data 1 that is obtained by encrypt ing a plaintext 1
through a key 1 and an encrypted data 2 that is obtained by
encrypt ing a plaintext 2 through a key 2 is equal to an encrypted
data that is obtained by encrypt ing a sum of the plaintext 1 and the
plaintext 2 through a sum of the key 1 and the key 2 ;
20 a second key generat ion uni t conf igured to generate the key
that is input to the second encrypt ing uni t ; and
an auxi l iary data generat ion uni t configured to accept the
input data, and the key that is generated in the second key
generat ion uni t , as inputs, and per forms output of the second
25 auxi l iary data that is used to veri fy that a Hamming distance of the
plaintexts, which cor responds to a dif ference between the second
encrypted data that is output f rom the second encrypt ing uni t and
the fi rst encrypted data that is output from the first encrypt ing uni t
of the regist rat ion data generat ion apparatus is a predetermined
48
certain value or less , and
the second data ver if icat ion apparatus includes:
an ent ire-data request uni t configured to inputs an
instruct ion of sequent ial read of al l of data that are stored in the
storage apparatus , to the ident ifier management uni t of the storag5 e
apparatus , in response to an inst ruct ion from an ident i fier output
uni t ;
an encrypted data subtract ion uni t configured to accept the
second encrypted data that is output f rom the second encrypt ing
10 uni t of the data concealment appar atus, and the fi rst encrypted data
that is stored in the encrypted data storage uni t in the storage
apparatus , as inputs, and output a di fference between the input two
encrypted data;
a match determinat ion uni t configured to accept the
15 dif ference between the encrypted data, which is output f rom the
encrypted data subt ract ion uni t , the f irst auxi l iary data that is
stored in the auxi l iary data storage uni t of the storage apparatus ,
and the second auxi l iary data that is output f rom the auxi l iary data
generat ion uni t of the data concealment apparatus , as inputs, and
20 determine whether or not a Hamming distance of the plaintext s,
which cor responds to the di f ference between the first and second
encrypted data is a predetermined certain value or less; and
the ident i fier output uni t configured to accept an output of
the determinat ion resul t from the match determinat ion uni t , and an
25 output of the ident ifier management uni t of the storage apparatus ,
as inputs, and output an ident i fier that corresponds data in which
the match determinat ion uni t determines that the Hamming distance
of plaintexts is the predetermined certain value or less ; and
a control apparatus configured to cont rol transmission and
49
recept ion of data between the data concealment apparatus and the
second data veri ficat ion apparatus .
[Claim 5] The encrypted data veri ficat ion system according to claim 3 or
4, wherein,
each of the fi rst and second encrypt ing uni ts encodes the ke5 y
through an error -cor rect ing code having l inear i ty, for the key and the
plaintext of the input data, and output a resul t that is obtained by
calculat ing a sum on a vector of a code word that is an error -cor rect ing
coding resul t and the plaintext , as the encrypted data.
10 [Claim 6] The encrypted data veri ficat ion system according to claim 3 or
4, wherein
the fi rst auxi l iary data, which is output f rom the registrat ion
auxi l iary data generat ion uni t of the storage apparatus , includes a key S
that is input to the fi rst encrypt ing uni t of the registrat ion data generat ion
15 apparatus , the fi rst encrypted data W1 that is output f rom the first
encrypt ing uni t , and data n that is less l ikely to be repeatedly used, and
data that is calculated by using "(c,S)(+)h(W1,n)" (where, "(x,y)" indicates
an inner product of vectors x and y, and "h" indicates a cryptographic
(one-way) hash funct ion, and "(+)" indicates a bi twise XOR), and
20 the second auxi l iary data, which is output f rom the auxi l iary data
generat ion uni t of the data concealment apparatus , includes a key S' that is
input to the second encrypt ing uni t of the data concealment apparatus , the
second encrypted data W1' that is output f rom the second encrypt ing uni t ,
and data n' that is less l ikely to be repeatedly used, and data that is
25 calculated by using "(c,S')(+)h(W1',n')".
[Claim 7] The encrypted data veri ficat ion system according to claim 6,
wherein
the n' is generated in both of , the first or second data veri ficat ion
apparatus , and the data concealment apparatus through a Di f fie-Hel lman
50
key exchange method.
[Claim 8] A biometric ident ificat ion system comprising:
the encrypted data veri ficat ion system according to any one of
claims 1 to 7, wherein
biometr ic ident i ficat ion is performed by generat ing input data tha5 t
are input to the registrat ion data generat ion apparatus and the data
concealment apparatus, based on biological informat ion, and determining
whether or not the data, that is input to the fi rst data veri ficat ion apparatus
or the data veri ficat ion apparatus through the data concealment apparatus ,
10 is matched wi th data that is stored in the storage apparatus .
[Claim 9] An encrypted data veri ficat ion method compr ising:
generat ing fi rst and second auxi l iary data that are used to ver ify,
that a Hamming distance between a plaintext of a first encrypted data
which is encrypted f rom input data and registered to a storage apparatus ,
15 and a plaintext of a second encrypted data which is encrypted f rom input
data of a target to be veri fied, is a predetermined cer tain value or less, for
the fi rst encrypted data and the second encrypted data respect ively; and
obtaining a dif ference between the fi rst encrypted data that is
registered to the storage apparatus and the second encrypted data that is
20 obtained by encrypt ing the input data of the target to be veri fied, and
determining whether or not the Hamming distance of the plaintexts, which
corresponds to the di fference between the fi rst encrypted data and the
second encrypted data, is the predetermined certain value or less , using the
first and second auxi l iary data .
25 [Claim 10] A program causing a computer to execute:
a processing of generat ing fi rst and second auxi l iary data that are
used to ver ify, that a Hamming distance between a plaintext of a fi rst
encrypted data which is encrypted f rom input data and registered to a
storage apparatus , and a plaintext of a second encrypted data which is
51
encrypted f rom input data of a target to be veri fied, is a predetermined
certain value or less, for the f irst encrypted data and the second encrypted
data respect ively; and,
a processing of obtaining a di fference between the fi rst encrypted
data that is registered to the storage apparatus and the second encrypte5 d
data that is obtained by encrypt ing the input data of the target to be
verif ied, and determining whether or not the Hamming distance of the
plaintexts, which cor responds to the dif ference between the fi rst encrypted
data and the second encrypted data, is the predetermined certain value or
10 less, using the fi rst and second auxi l iary data .