Technical Fiel5 d
[0001]
(Cross-Reference to Related Appl icat ion)
The present invent ion is based on the priori ty claimed for Japanese
Patent Appl icat ion No. 2013-091466 ( f i led on Apri l 24, 2013), the ent i re
10 content of which is herein incorporated by reference as i f ful ly set forth
herein.
The present invent ion relates to an encrypted text matching system,
method, and program.
Background Art
15 [0002]
Wi th the wide-spreading cloud comput ing, there has recent ly been a
rapid expansion of services based on the user data stored in computat ional
resources connected to networks . Such services more often involve
opportuni t ies to deal wi th sensi t ive user data . Therefore, i t is becoming
20 important to assure users that their data is securely managed . Under such
circumstances, research and development are act ively promoted for
techniques to manage data that remains encrypted in open network
environments and to perform searches, stat ist i cal processing, and the l ike
on the data wi thout decrypt ing i t .
25 [0003]
In addi t ion, crimes are more f requent ly occur ring that exploi t the
vulnerabi l i ty of personal authent icat ion using passwords or magnet ic
cards. Thus, more secure biomet ric authent icat i on techniques based on
2
biological features such as fingerprints or veins are drawing at tent ion .
Biomet ric authent icat ion requi res a template related to biomet ric
informat ion to be stored in a database in order to ver ify authent icat ion
informat ion. Biomet r ic informat ion such as fingerprints or veins is the
data that is basical ly unchanged through one's l ifet ime . Biomet ri5 c
informat ion requi res highest -level securi ty protect ion because serious
damages wi l l occur i f such informat ion is leaked . Thus, impersonat ion or
the l ike must be prevented even when the template is leaked.
[0004]
10 Accordingl y, i t is becoming important to have a template protect ion
type biometric authent icat ion technique which per forms authent icat ion
wi th the template informat ion concealed.
[0005]
For example, PTL 1 discloses a method for per forming biometric
15 authent icat ion by represent ing fingerprint data as points on a polynomial
expression, adding random points to the points to conceal the fingerprint
data, and using the concealed data as a template.
[0006]
However, the method of PTL 1 is known to be problemat ic
20 concerning whether the biomet ric informat ion st i l l remains protected wi th
adequate strength after biomet ric authent icat ion is repeated many t imes.
[0007]
NPL 1 discloses a method for protect ing biometr ic informat ion by
masking a template stored in a database wi th a random
25 Bose-Chaudhuri -Hocquenghem (BCH) code word. According to NPL 1,
biometr ic informat ion Z and secret informat ion S are used to generate a
template for biomet ric authent icat ion. Fig. 5 is a diagram based on Fig. 2
in NPL 1, wi th the feature extract ion, stat ist ical analysis, quant izat ion, and
the l ike shown in Fig. 2 in NPL 1 omi t ted. The enrol lment of the
3
template is performed as described below.
[0008]
(1) Input the secret informat ion S to an encoder (ENC) , per form
er ror cor rect ing coding (ECC) and generate a code word C. For ECC,
binary BCH codes wi th parameters (K, s, d) are used, where K denotes th5 e
length of the code words, s the number of informat ion symb ols, and d the
number of errors that can be corrected.
(2) Calculate an exclusive OR between C and Z, namely W2 = C (+)
Z (where (+) represents a bi twise exclusive OR operat ion (bi twise XOR)) .
10 (3) Input S to a cryptographic (one -way) hash funct ion H, such as
Secure Hash Algori thm (SHA) -1 and obtain a hash value H(S).
(4) Store W2 and H(S) as template informat ion in a database (DB).
[0009]
Veri ficat ion of whether the template generated through the above
15 steps (1) to (4) and another piece of biometr ic inf ormat ion Z' have been
obtained f rom the same person is performed as described below.
(1) Calculate an exclusive OR between Z' and W2, namely C' = W2
(+) Z' = C (+) (Z (+) Z').
(2) Input C' to a decoder (DEC) , per form error-correct ing decoding
20 of the BCH code and calculate S' .
(3) Input S' to a cryptographic (one -way) hash funct ion H, such as
SHA-1 and calculate a hash value H(S').
(4) Read H(S) f rom the DB and check whether H(S) = H(S') is
sat isfied. If H(S) = H(S') is sat isfied, i t is determined that the template
25 and the biomet ric informat ion Z' were taken f rom the same person . If
H(S) = H(S') is not sat isfied, i t is determined that the template and the
biometr ic informat ion Z' were taken f rom di fferent persons.
[0010]
The above-described method is not dependent on how the biomet ric
4
informat ion Z is obtained. Therefore, in general , the method can be
regarded as a method for checking whether an encrypted text has been
obtained by encrypt ing data that fal ls wi thin a certain Hamming distance
from the presented data, wi thout decrypt ing concealed (encrypted) data.
Citation Lis5 t
Patent Li terature
[0011]
PTL 1: Japanese Unexamined Patent Appl icat ion Publ icat ion No .
2006-158851
10 Non Patent Li terature
[0012]
NPL 1: Pim Tuyls, Anton H. M. Akkermans, Tom A. M. Kevenaar,
Geert -Jan Schri jen, Asker M. Bazen and Raimond N. J. Veldhuis,
"Pract ical Biometr ic Authent icat ion wi th Template Protect ion",
15 Proceedings of AVBPA 2005, Lecture Notes in Computer Science, Vol .
3546, Springer Ver lag, pp. 436–446, (2005)
Summary of Invention
Technical Problem
[0013]
20 Analyses of related arts are provided below.
[0014]
A problem of the above-described related arts is that informat ion
about a plaintext might be leaked during matching wi th an encrypted text
stored in a database to the administ rator or the l ike who per forms the
25 matching. The fol lowing describes the reasons.
[0015]
For example, wi th regard to PTL 1 above, such leaks might occur
due to insufficient conceal ing st rength on encrypted texts.
[0016]
5
Wi th regard to NPL 1 above, such leaks might occur because, in
order to make i t possible to check whether an encrypted text has been
obtained by encrypt ing data that fal ls wi thin a certain Hamming distance
from the presented data, informat ion about a plaintext needs to be
transmi t ted during the checking5 .
[0017]
As described above, informat ion about the original plaintext might
be leaked when the matching process is car ried out repeatedly. Thus,
sufficient securi ty cannot be assured if , for example, the database
10 administ rator or the l ike per forming the matching process has mal icious
intent . For example, in view of appl icat ions of biometric authent icat ion,
a leak of biomet ric informat ion from the data t ransmi t ted dur ing the
matching can be regarded as a problem as serious as a leak of biomet ric
informat ion from the registered data . Exist ing biometric authent icat ion
15 methods that protect templates only address the securi ty against leaks of
biometr ic informat ion f rom registered templates . However, in order to
pay at tent ion to the secur i ty of biomet ric authent icat ion i tself ,
considerat ion needs to be given to leaks of informat ion from the data
transmi t ted during the matching. In addi t ion, when the secur i ty of
20 authent icat ion is taken into considerat ion, i t is a problem that the dat a
transmi t ted during the matching can be used to generate the data judged as
ident ical to the t ransmi t ted data. For example, the method described in
NPL 1 al lows for the matching by obtaining and ret ransmi t t ing the value
Z'. From the viewpoint of biomet r ic authent icat ion, this conduct means
25 that i t is possible to impersonate a person by obtaining the data that was
transmi t ted from the person for his/her authent icat ion.
[0018]
Accordingl y, the present invent ion has been created in view of the
above problems, wi th an object of providing a system, method, and
6
program that can avoid leaks of informat ion about the original plaintext
and assure securi ty when per forming the matching of encrypted texts.
Solution to Problem
[0019]
An encrypted text matching system according to the presen5 t
invent ion is provided, and the encrypted text matching system includes:
means for generat ing fi rst auxi l iary data and second auxi l iary data,
respect ivel y, which are for veri ficat ion of matching between a first
encrypted text that is obtained by encrypt ing input data and is registered
10 wi th a storage device and a second encrypted text that is obtained by
encrypt ing input data to be matched, the verif icat ion being performed by
using a Hamming distance between plaintexts; and means for performing
one-way conversion on at least part of the second auxi l iary data,
performing one-way conversion on intermediate data that is generated
15 based on a di fference between the fi rst encrypted text and the second
encrypted text and on the fi rst auxi l i ary data, and determining, by using a
resul t of the one-way conversion performed on the intermediate data as
wel l as using the second auxi l iary data that underwent the one -way
conversion, whether a Hamming distance between plaintexts is equal to or
20 less than a predetermined certain value, the Hamming distance
corresponding to the difference between the fi rst encrypted text and the
second encrypted text . According to the present invent ion, a biometr ic
authent icat ion system including an encrypted text matchi ng system is
provided.
25 [0020]
In a method for matching encrypted texts according to the present
invent ion, the method includes: generat ing fi rst auxi l iary data and second
auxi l iary data, respect ivel y, which are for veri ficat ion of matching between
a first encrypted text that is obtained by encrypt ing input data and is
7
registered wi th a storage device and a second encrypted text that is
obtained by encrypt ing input data to be matched, the veri ficat ion being
performed by using a Hamming distance between plai ntexts; and
performing one-way conversion on at least part of the second auxi l iary
data, per forming one-way conversion on intermediate data that is generate5 d
based on a di fference between the fi rst encrypted text and the second
encrypted text and on the fi rst auxi l iary data, and determining, by using a
resul t of the one-way conversion performed on the intermediate data as
wel l as using the second auxi l iary data that underwent the one -way
10 conversion, whether a Hamming distance between plaintexts is equal to or
less than a predetermined certain value, the Hamming distance
corresponding to the difference between the fi rst encrypted text and the
second encrypted text .
[0021]
15 A program according to the present invent ion is provided, and the
program causes a computer to execute: a process which generates fi rst
auxi l iary data and second auxi l iary data, respect ivel y, which are for
verif icat ion of matching between a first encrypted text that is obtained by
encrypt ing input data and is registered wi th a storage device and a second
20 encrypted text that is obtained by encrypt ing input data to be matched, the
verif icat ion being performed by using a Hamming distance between
plaintexts; and a process which per forms one -way conversion on at least
part of the second auxi l iary data, per forms one-way conversion on
intermediate data that is generated based on a difference between the fi rst
25 encrypted text and the second encrypted text and on the fi rst auxi l iary data,
and determines, by using a resul t of the one -way conversion per formed on
the intermediate data as wel l as using the second auxi l iary data that
underwent the one-way conversion, whether a Hamming distance between
plaintexts is equal to or less than a predetermined cer tain value, the
8
Hamming distance cor responding to the difference between the fi rst
encrypted text and the second encrypted text . According to the present
invent ion, a computer- readable recording medium (magnet ic/opt ical
recording medium or semiconductor recording medium) that records the
program is provided5 .
Advantageous Ef fects of Invent ion
[0022]
According to the present invent ion, i t is made possible to avoid
leaks of informat ion about an original plaintext and assure securi ty during
10 matching of encrypted texts.
Brief Description of Drawings
[0023]
Fig. 1 is a diagram i l lustrat ing an example configurat ion according
to an exemplary embodiment 1 of the present invent ion.
15 Figs. 2 (A) and 2 (B) are explanatory diagrams describing a data
regist rat ion phase and an encrypted text matching phase, respect ivel y,
according to the exemplary embodiment 1 of the present invent ion.
Fig. 3 is a diagram i l lustrat ing an example configurat ion according
to an exemplary embodiment 2 of the present invent ion.
20 Fig. 4 is an explanatory diagram describing an encrypted text
matching phase according to the exemplary embodiment 2 of the present
invent ion.
Fig. 5 is a diagram i l lustrat ing an example method according to
NPL 1.
25 Fig. 6 is an explanatory diagram i l lust rat ing the invent ive concept .
Description of Embodiments
[0024]
Embodiments of the present invent ion wi l l be described . First ,
the basic concept of the present invent ion is described below. According
9
to one aspect of the present invent ion, the input data to be matched is
encrypted, whi le the registered data wi th which the input data wi l l be
matched has been encrypted. In addi t ion, a Hamming distance between
plaintexts is used as an indicator (indicator of ambigui ty) for determining
(veri fying) the matching (agreement ) between the encrypted input data an5 d
the registered encrypted data. In this way, not only the registered
encrypted data but also the input data for the matching is encrypted
through the use of an encrypt ion method having high conceal ing st rength .
When the same input data is used to perform the matching repeatedly,
10 informat ion about a key that is used for conceal ing the input data is
changed every t ime the matching is per formed . Thus, even when the
matching is performed repeatedly, the possibi l i ty to cause leaks of
informat ion about a plaintext can be red uced to a low level . As a resul t ,
the present invent ion contr ibutes to greater resistance to at tacks and
15 improved securi t y.
[0025]
Wi th reference to Fig. 6, an encrypted text matching system 10
(device) according to one aspect of the present invent ion in cludes at least :
an auxi l iary data generat ing means (uni t ) (14) which generates auxi l iary
20 data f rom an encrypted text ; and a matching determining means (uni t ) (15)
which makes a determinat ion f rom the encrypted texts and auxi l iary data
on the matching between the encrypted input data and the registered
encrypted data. The auxi l iary data is used for veri fying the matching of
encrypted texts by using a Hamming distance between plaintexts.
25 [0026]
The auxi l iary data generat ing means (uni t ) (14) generates auxi l iary
data 1 and auxi l iary data 2 on an encrypted text 1 that is produced by an
encrypt ing means (uni t) (11) which encrypts the input data and is
registered wi th a storage device (13) and on an encrypted text 2 that is
10
produced by an encrypt ing means (uni t ) (12) which encrypts the input data
to be matched, respect ivel y, the auxi l iary data 1 and 2 being required for
verifying the matching by using a Hamming distance between plaintexts .
The verificat ion of the matching may be, for example, verifying that the
Hamming distance between plaintexts of the encrypted text 1 and th5 e
encrypted text 2 is equal or less than a predetermined certain value.
[0027]
At least part of the auxi l iary data 2 is subjected to one -way
conversion per formed by a one -way convert ing means (14h) .
10 Furthermore, intermediate data that is generated based on a di fference
between the encrypted text 1 and encrypted text 2 and on the auxi l iary data
1 is subjected to one-way conversion performed by a one -way convert ing
means (15h).
[0028]
15 A matching determining means (uni t ) (15) determines whether the
Hamming distance between plaintexts, which cor responds to the di fference
between the encrypted text 1 and the encrypted text 2, is equal to or less
than a predetermined cer tain value, by using the resul t of one-way
conversion of the intermediate data per formed by the one -way conver t ing
20 means (15h) as wel l as using the auxi l iary data 2, part of which underwent
the one-way conversion performed by the one -way convert ing means (14h) .
Processes and funct ions of the individual means in the encrypted text
matching system 10 (device) may be implemented by a program to be
executed on a computer const i tut ing the encrypted text matching system 10
25 (device) .
[0029]
According to the present invent ion, an encrypt ed text is a resul t of
an exclusive OR operat ion between a code word, which is obtained by
encoding a key for encrypt ing the plaintext of the input data wi th an
11
er ror-cor rect ing code having l ineari t y, and the plaintext . The first and
second auxi l iary data related to the encrypted text registered wi th the
storage device and the encrypted text of the input data to be matched may
be respect ively calculated based on an exclusive OR between an inner
product of the key and a constant , and a cryptographic hash fu nct io5 n
appl ied to the encrypted text and a random number. A cryptographic hash
funct ion has a proper ty cal led pre -image resistance, which means given a
hash value h i t is di fficul t to find an original character string m such that h
= hash(m) (a one-way compression funct ion) .
10 [0030]
In addi t ion, in order to accompl ish the matching between two pieces
of encrypted data, which is not achieved by NPL 1 described above, the
present invent ion guarantees that , wi th respect to a hash funct ion for
determining a matching resul t , i t is possible to calculate a hash value of the
15 sum of two pieces of data f rom thei r hash values.
[0031]
As described above, according to the present invent ion, during the
matching process between encrypted texts, the data t ransmi t ted by the user
who is going to do the matching is also encrypted by an encrypt ion key that
20 is unknown to, for example, the database administ rator or the l ike who
performs matching operat ions . Consequent l y, leaks of informat ion about
the or iginal plaintext can be prevented during the matching process, even
when the matching is per formed repeatedly or when the database
administ rator or the l ike who per forms matching operat ions has mal icious
25 intent . Some exemplary embodiments wi l l be described below.
[0032]

Wi th reference to Fig. 1, a system according to an exemplary
embodiment 1 of the present invent ion includes a regist rat ion data
12
generat ing device 100, a storage device 200, a data conceal ing device 300,
and a speci fied data matching device 400. Note that these devices may be
configured to gather at a single si te or the l ike to form a single apparatus,
or may be configured to be distributed and connected to one another via a
communicat ion means5 .
[0033]
The regist rat ion data generat ing devi ce 100 includes an encrypt ing
uni t 101, a key generat ing uni t 102, and a registrat ion auxi l iary data
generat ing uni t 103.
10 [0034]
The encrypt ing uni t 101 receives:
- input data to be concealed; and
- a key for conceal ing the input data,
as inputs,
15 and outputs the encrypted data that is obtained by per forming a
conceal ing process on the input data wi th the key. The encrypted data in
the encrypt ing uni t 101 is input to the registrat ion auxi l iary data
generat ing uni t 103 as wel l as stored in the storage device 200 (encrypted
text storage uni t 202).
20 [0035]
The key generat ing uni t 102 generates a key to be used for the
encrypt ing uni t 101 to conceal the input data, and then outputs the
generated key to the encrypt ing uni t 101 and to the regist rat ion auxi l i ary
data generat ing uni t 103.
25 [0036]
The regist rat ion auxi l iary data generat ing uni t 103 receives:
- input data ( input data to be concealed);
- encrypted data output f rom the encrypt ing uni t 101; and
- a key output f rom the key generat ing uni t 102,
13
as inputs.
The regist rat ion auxi l iary data generat ing uni t 103 outputs the
auxi l iary data (regist rat ion auxi l iary data) for determining whether a
Hamming distance between the input data (input data to be matched)
corresponding to the encrypted data output f rom an encrypt ing uni t 301 i5 n
the data conceal ing device 300 and the input data in the encrypt ing uni t
101 is equal to or less than a predetermined cer tain value (wi thin a certain
numerical range).
[0037]
10 The encrypted text output f rom the encrypt ing uni t 101 in the
regist rat ion data generat ing device 100 sat isfies the fol lowing:
let c1 be the encrypted text obtained by encrypt ing the input data
m1 wi th the key k1; and
let c2 be the encrypted text obtained by encrypt ing the input data
15 m2 wi th the key k2; then
the sum of c1 and c2, c1 + c2, is the encrypted text obtained by
encrypt ing the input data m1 + m2 wi th the key k1 + k2.
[0038]
The storage device 200 includes an ident i fier managing uni t 201, an
20 encrypted text storage uni t 202, and an auxi l iary da ta storage uni t 203.
[0039]
The encrypted text storage uni t 202 and the auxi l iary data storage
uni t 203 respect ively receive and store the encrypted data and registrat ion
auxi l iary data output f rom the regist rat ion data generat ing device 100 .
25 The encrypted text storage uni t 202 and the auxi l iary data storage uni t 203
may be configured as databases (or may be comprised of fi les).
[0040]
During the matching of encrypted data, the encrypted text storage
uni t 202 and the auxi l iary data storage uni t 203 outpu t to the specified data
14
matching device 400, under the cont rol of the ident i fier managing uni t 201,
the encrypted data and auxi l iary data cor responding to an ident ifier input
from the specified data matching device 400.
[0041]
The ident ifier managing uni t 201 in the storage device 200 manage5 s
ident if iers that uniquely ident i fy encrypted data and auxi l iary data input
from the registrat ion data generat ing device 100.
[0042]
When input t ing an ident i fier f rom the specif ied data matching
10 device 400, the ident i fier managing uni t 201 outputs to the encrypted text
storage uni t 202 and to the auxi l iary data storage uni t 203 an instruct ion to
respect ively output the encrypted data and the auxi l iary data cor responding
to the input ident ifier.
[0043]
15 The encrypted text storage uni t 202 stores the encrypted data output
from the encrypt ing uni t 101 in the regist rat ion data generat ing device 100
and, when input t ing an inst ruct ion to output encrypted data from the
ident if ier managing uni t 201, the encrypted text storage uni t 202 outputs
the cor responding encrypted data.
20 [0044]
The auxi l iary data storage uni t 203 stores the auxi l iary data output
from the registrat ion auxi l iary data generat ing uni t 103 in the regist rat ion
data generat ing device 100 and, when input t ing an inst ruct ion to output
encrypted data f rom the ident ifier managing uni t 201, the auxi l iary data
25 storage uni t 203 outputs the cor responding auxi l iary data.
[0045]
The data conceal ing device 300 includes an encrypt ing uni t 301, a
key generat ing uni t 302, an auxi l iary data generat ing uni t 303, and a
one-way convert ing uni t 304.
15
[0046]
The encrypt ing uni t 301 receives:
- input data to be concealed (input data to be matched); and
- a key for conceal ing the input data,
as inputs5 ,
and outputs the encrypted data that is obtained by per forming a
conceal ing process on the input data wi th the key. The encrypted data
output from the encrypt ing uni t 301 is input to the auxi l iary data
generat ing uni t 303 and to the speci fied data matching device 400
10 (encrypted text subt ract ing uni t 402).
[0047]
The key generat ing uni t 302 generates a key to be used for the
encrypt ing uni t 101 to conceal the input data, and then outputs the
generated key to the encrypt ing uni t 301 and to the auxi l iary data
15 generat ing uni t 303.
[0048]
The auxi l iary data generat ing uni t 303 receives:
- the input data (input data to be matched) ;
- encrypted data output f rom the encrypt ing uni t 301; and
20 - a key output f rom the key generat ing uni t 302 to the encrypt ing
uni t 301,
as inputs. The auxi l iary data generat ing uni t 303 outputs the
auxi l iary data for determining whether a Hamming distance between the
input data (plaintext) cor responding to the encrypted data (registered
25 encrypted data) in the encrypt ing uni t 101 in the regist rat ion data
generat ing device 100 and the input data to be matched (plaintext) as input
to the encrypt ing uni t 301 is equal to or less than a predetermined certain
value (wi thin a certain numerical range) . The auxi l iary data in the
auxi l iary data generat ing uni t 303 is inp ut to the specif ied data matching
16
device 400 (matching determining uni t 403) .
[0049]
The one-way convert ing uni t 304 outputs the resul t of one -way
conversion per formed on par t or al l of the data (auxi l iary data) generated
by the auxi l iary data generat ing uni t 303. The auxi l iary data is auxi l iar5 y
informat ion used for determining that the registered encrypted data
matches the input data i f a Hamming distance between the input data
(plaintext) cor responding to the registered encrypted data and the input
data to be matched (plaintext ) as input to the encrypt ing uni t 301 is not
10 greater than (or is less than) a predetermined value, and for determining
that the registered encrypted data does not match (does not agree wi th) the
input data i f the Hamming distance i s greater than (or no smal ler than) a
predetermine value. The resul t of one-way conversion performed by the
one-way convert ing uni t 304 is input to the auxi l iary data generat ing uni t
15 303.
[0050]
The encrypted text output f rom the encrypt ing uni t 301 in t he data
conceal ing device 300 is calculated in the same way as in the encrypt ing
uni t 101. That is, the encrypted text sat isfies the fol lowing:
20 let c1 be the encrypted text obtained by encrypt ing the input data
m1 wi th the key k1; and
let c2 be the encrypted text obtained by encrypt ing the input data
m2 wi th the key k2; then
the sum of c1 and c2, c1 + c2, is the encrypted text obtained by
25 encrypt ing the input data m1 + m2 wi th the key k1 + k2.
[0051]
The speci fied data matching device 400 includes an i dent i fier
holding uni t 401, an encrypted text subt ract ing uni t 402, a matching
determining uni t 403, a cont rol uni t 404, and a one -way convert ing uni t
17
405.
[0052]
The ident ifier holding uni t 401 receives an ident i fier, as an input ,
and outputs an inst ruct ion to the ident i fier managing uni t 201 in the
storage device 200 to output the encrypted text data and the auxi l iary dat5 a
that cor respond to the ident if ier in the storage device 200.
[0053]
The encrypted text subtract ing uni t 402 receives:
- one piece of encrypted data ( registered encrypted data) stored in
10 the encrypted text storage uni t 202 in the storage device 200; and
- the encrypted data output f rom the encrypt ing uni t 301 in the data
conceal ing device 300,
as inputs, and outputs a di fference c1 - c2 between the two pieces of
input encrypted data c1 and c2.
15 [0054]
Owing to the propert ies of the encrypt ing uni ts 101 and 301, the
difference c1 - c2 is expressed as fol lows:
let c1 be the encrypted text obtained by encrypt ing the input data
m1 wi th the key k1; and
20 let c2 be the encrypted text obtained by encrypt ing the input data
m2 wi th the key k2; then
the di fference c1 - c2 between the two encrypted texts c1 and c2 is
the encrypted text obtained by encrypt ing the input data m1 - m2 wi th the
key k1 - k2.
25 [0055]
The matching determining uni t 403 receives:
- the auxi l iary data stored in the auxi l iary data storage uni t 203 in
the storage device 200;
- the auxi l iary data output f rom the auxi l iary data generat ing uni t
18
303 in the data conceal ing devic e 300; and
- the di fference between two pieces of encrypted data output f rom
the encrypted text subtract ing uni t 402,
as inputs.
[00565 ]
The matching determining uni t 403 t ransmi ts intermediate data
generated from the data that includes at least :
- the auxi l iary data stored in the auxi l iary data storage uni t 203 in
the storage device 200; and
10 - the di fference between the two pieces of encrypted data output
from the encrypted text subtract ing uni t 402
to the one-way convert ing uni t 405.
[0057]
The one-way convert ing uni t 405 returns the data that underwent
15 one-way conversion performed on the intermediate data to the matching
determining uni t 403.
[0058]
The matching determining uni t 403 determines , based on:
- the data generated through one -way conversion performed by the
20 one-way convert ing uni t 405 based on the intermediate data; and
- one piece of the auxi l iary data generated through one -way
conversion as output from the auxi l iary data generat ing uni t 303 in the data
conceal ing device 300
whether the Hamming distance between plaintexts m1 and m2 which
25 respect ively cor respond to the encrypted data c1 and c2 as input to the
encrypted text subt ract ing uni t 402 is equal to or less than a predetermined
certain value, and outputs the determinat ion resul t .
[0059]
The cont rol uni t 404 controls communicat ions and the l ike for
19
exchanging data between the data conceal ing device 300 and the specified
data matching device 400.
[0060]
Operat ions of the exemplary embodiment 1 wi l l be described wi th
reference to the flowchar t in Fig. 2. Operat ions of the encrypted tex5 t
matching system according to the exemplary embodiment 1 are broadly
divided into two phases: a data regist rat ion phase and an encrypted text
matching phase.
[0061]
10 In the data regist rat ion phase, i nput data is input to the registrat ion
data generat ing device 100, encrypted, and registered wi th the storage
device 200 along wi th auxi l iary data (Fig. 2 (A)) .
[0062]
In the encrypted text matching phase, the input data in the data
15 conceal ing device 300 is encrypted, and then i t is determined whether the
encrypted data and auxi l iary data, as generated in the encrypt ion process,
represent plaintexts that are close to the encrypted data and auxi l iary data
that are stored in the storage device and are speci fied by an ident i fier to be
separately input (Fig. 2 (B)) . Note that "plaintexts that are close to"
20 means that a Hamming distance is equal to or less than a predetermined
certain value.
[0063]
In the data registrat ion phase, fi rst , the input data to be co ncealed is
input to the encrypt ing uni t 101 in the registrat ion data generat ing device
25 100 (Step A1 in Fig. 2 (A)).
[0064]
Next , the key generat ing uni t 102 in the registrat ion data generat ing
device 100 generates a key to be used for conceal ing the input data and
outputs the key to the encrypt ing uni t 101 and to the regist rat ion auxi l iary
20
data generat ing uni t 103 (Step A2 in Fig. 2 (A)).
[0065]
Next , the encrypt ing uni t 101 in the regist rat ion data generat ing
device 100 calculates encrypted data that is obtained by encrypt ing the
input data using the input data and the key, and then stores the encrypte5 d
data into the encrypted text storage uni t 202 (Step A3 in Fig. 2 (A) ).
[0066]
Next , the input data in Step A1, the key generated in Step A2, and
the encrypted data generated in Step A3 are input to the registrat ion
10 auxi l iary data generat ing uni t 103, and then auxi l iary data ( registrat ion
auxi l iary data) is created in the registrat ion auxi l iary data generat ing uni t
103 (Step A4 in Fig. 2 (A)).
[0067]
The regist rat ion auxi l iary data generat ing uni t 103 stores the
15 created auxi l iary data (regist rat ion auxi l iary data) in to the auxi l iary data
storage uni t 203 in the storage device 200 (Step A5 in Fig. 2 (A)) .
[0068]
When the above operat ions are completed, th e input data in the
storage device 200 can be assigned a unique ident i fier by the ident if ier
20 managing uni t 201 and can be later retrieved ( read) wi th the assigned
ident if ier.
[0069]
In the encrypted text matching phase, fi rst , an ident i fier is input to
the ident i fier holding uni t 401 in the specif ied data matching device 400,
25 and then the encrypted data ( registered encrypted data) cor responding to
the input ident if ier is input to the encrypted text subt ract ing uni t 402 f rom
the encrypted text storage uni t 202 in the storage device 200. In addi t ion,
the auxi l iary data corresponding to the input ident i fier is input to the
matching determining uni t 403 f rom the auxi l iary data storage uni t 203
21
(Step B1 in Fig. 2 (B)) .
[0070]
Next , input data (data to be matched ) is input to the encrypt ing uni t
301 in the data conceal ing device 300 (Step B2 in Fig. 2 (B) ).
[00715 ]
Next , the key generat ing uni t 302 in the data conceal ing device 300
generates a key to be used for conceal ing the input data and outputs the
created key to the encrypt ing uni t 301 and to the auxi l iary data generat ing
uni t 303 (Step B3 in Fig. 2 (B) ).
10 [0072]
Next , the encrypt ing uni t 301 in the data conceal ing device 300
calculates encrypted data that is obtained by encrypt ing the input data
using the input data in Step B2 and the key in Step B3, and then inputs the
encrypted data into the encrypted text subtract ing uni t 402 in the specified
15 data matching device 400 (Step B4 in Fig. 2 (B) ).
[0073]
The auxi l iary data generat ing uni t 303 in the data concea l ing device
300 creates auxi l iary data based on the encrypted data f rom the encrypt ing
uni t 301 as wel l as on the key f rom the key generat ing uni t 302 . During
20 this process, at least part of the data is subjected to one -way conversion
performed by the one-way conver t ing uni t 304 to generate the auxi l iary
data (Step B5 in Fig. 2 (B) ).
[0074]
The speci fied data matching device 400 receives, as inputs, the
25 encrypted data f rom the encrypted text storage uni t 202 in the storage
device 200 and the encrypted data from the encrypt ing uni t 301 in the data
conceal ing device 300. The encrypted text subtract ing uni t 402 in the
speci fied data matching device 400 outputs the di fference between the two
input pieces of encrypted data to the matching determining uni t 403 ( Step
22
B6 in Fig. 2 (B)) . In addi t ion, the auxi l iary data f rom the auxi l iary data
storage uni t 203 and the auxi l iary data f rom the auxi l iary data generat ing
uni t 303 are input to the matching determining uni t 403, through
communicat ions in concert between t he auxi l iary data storage uni t 203 in
the storage device 200 and the auxi l iary data generat ing uni t 303 in th5 e
data conceal ing device 300 under the control of the cont rol uni t 404.
[0075]
The matching determining uni t 403 in the speci fied data matching
device 400 receives, as an input , the difference between the two pieces of
10 encrypted data output f rom the encrypted text subtract ing uni t 402 in the
speci fied data matching device 400 in Step B6 above, as wel l as receiving,
as inputs, the post -conversion auxi l iary data f rom the auxi l iary data
storage uni t 203 and the auxi l iary data f rom the auxi l iary data generat ing
uni t 303. The matching determining uni t 403 in the speci fied data
15 matching device 400 generates intermediate data from the di fference
between the two pieces of encrypted data and f rom the auxi l iary data, and
outputs the intermediate data to the one -way convert ing uni t 405 in the
speci fied data matching device 400 (Step B7 in Fig. 2 (B)) .
[0076]
20 The one-way convert ing uni t 405 in the speci fied dat a matching
device 400 creates post -conversion intermediate data produced through
one-way conversion performed on the intermediate data, and outputs the
post -conversion intermediate data to the matching determining uni t 403
(Step B8 in Fig. 2 (B)) .
25 [0077]
The matching determining uni t 403 in the speci fied data matching
device 400 determines, f rom the post -conversion intermediate data and the
auxi l iary data, whether the Hamming distance between:
- the plaintext of the registered encrypted data in the encrypted text
23
subt ract ing uni t 402 from the storage device 200 in Step B1; and
- the plaintext of the encrypted data in the encrypted text
subt ract ing uni t 402 in Step B4
is equal to or less than a predetermined certain value and outputs
the determinat ion resul t (Step B9 in Fig. 2 (B) 5 ).
[0078]
Note that the devices 100, 200, 300, and 400 shown in Fig. 1 may be
implemented on a single computer system, or may be configured as
individual devices . Al ternat ivel y, the uni ts in each of the devices 100,
10 200, 300, and 400 may be configured in the form of individual devices .
Processes handled by individual uni ts in individual devices shown in Fig. 1
may be implemented by a program to be executed by a computer.
According to the present invent ion, a recording medium ( semiconductor
memory or a magnet ic/opt ical disk) that records such program is provided.
15 [0079]
The exemplary embodiment 1 makes i t possible to prevent leaks of
the input data to be matched by applying one -way conversion to the
auxi l iary data that is relat ed to the input data to be matched.
[0080]
20
An exemplary embodiment 2 of the present invent ion wi l l be
described. In the encrypted text matching system according to the
above-described exemplary embodiment 1, input data and an ident ifier are
input to the system, and the input data is matched wi th the plaintext of the
25 encrypted data corresponding to the ident ifier. In cont rast , according to
the present exemplary embodiment , input data is only input to the system,
which outputs an ident ifier corresponding to the encrypted data to be
matched wi th the input data.
[0081]
24
Wi th reference to Fig. 3, the system according to the exemplary
embodiment 2 is composed of a regist rat ion data generat ing device 100, a
storage device 200, a data conceal ing device 300, and a data matching
device 500. Whi le the registrat ion data generat ing device 100, the
storage device 200, and the data conceal ing device 300 are configured i5 n
the same way as in the exemplary embodiment 1, the configurat ion of the
data matching device 500 is di fferent from that of the exemplary
embodiment 1. The fol lowing descript ion of the exemplary embodiment
2 focuses on the di fferences, omi t t ing por t ions common to the exemplary
10 embodiment 1 as may be appropr iate.
[0082]
The data matching device 500 includes an al l data request ing uni t
501, an encrypted text subtract ing uni t 502, a matching determining uni t
503, a cont rol uni t 504, an ident i fier output t ing uni t 505, and a one -way
15 convert ing uni t 506.
[0083]
In accordance wi th an instruct ion given by the ident i fier output t ing
uni t 505, the al l data request ing uni t 501 inputs into the ident i fier
managing uni t 201 an instruct ion for sequent ial ly reading every piece of
20 data stored in the storage device 200.
[0084]
The encrypted text subtract ing uni t 502 receives, as inputs, one
piece of the encrypted data stored in the encrypted text storage uni t 202 in
the storage device 200 and the encrypted data output from the encrypt ing
25 uni t in the data conceal ing device 300, and then outputs a di fference, c1 -
c2, between the two pieces of input encrypted data c1 and c2.
[0085]
Owing to the propert ies of the encrypt ing uni ts 101 and 301, the
difference c1 - c2 is expressed as fol lows:
25
let c1 be the encrypted text obtained by encrypt ing the input data
m1 wi th the key k1; and
let c2 be the encrypted text obtained by encrypt ing the input data
m2 wi th the key k2; then
the di fference c1 - c2 between the two encrypted texts c1 and c2 i5 s
the encrypted text obtained by encrypt ing the input data m1 - m2 wi th the
key k1 - k2.
[0086]
The matching determining uni t 503 receives:
10 - the auxi l iary data stored in the auxi l iary data storage uni t 203 in
the storage device 200;
- the auxi l iary data output f rom the auxi l iary data generat ing uni t
303 in the data conceal ing device 300; and
- the di fference between two pieces of encrypted data output f rom
15 the encrypted text subtract ing uni t 502,
as inputs.
[0087]
The matching determining uni t 503 t ransmi ts intermediate data
generated from the data that includes at least :
20 - the di fference between the two pieces of encrypted data output
from the encrypted text subtract ing uni t 502; and
- the auxi l iary data stored in the auxi l iary data storage uni t 203 in
the storage device 200
to the one-way convert ing uni t 506.
25 [0088]
The matching determining uni t 503 outputs a determinat ion, based
on:
- the data generated through one -way conversion performed by the
one-way convert ing uni t 506 based on the intermediate data; and
26
- one piece of the auxi l iary data generated throu gh one-way
conversion as output from the auxi l iary data generat ing uni t 303 in the data
conceal ing device 300 of whether the Hamming distance between
plaintexts m1 and m2, which respect ively cor respond to the encrypted data
c1 and c2, as input to the encrypted text subt ract ing uni t 502 is equal to o5 r
less than a predetermined certain value.
[0089]
The cont rol uni t 504 controls communicat ions for exchanging data
between the data conceal ing device 300 and the data matching device 500.
10 [0090]
The ident ifier output t ing uni t 505 receives:
- the ident i fier for which the ident i fier managing uni t 201 has
issued an instruct ion to the encrypted text storage uni t 202 and the
auxi l iary data storage uni t 203 to output the cor responding data; and
15 - the matching resul t output f rom the matching determining uni t
503,
as inputs,
and, i f the matching determining uni t 503 determines that there is a
match (agreement ), outputs the ident i fier that has been input f rom the
20 ident if ier managing uni t 201.
[0091]
Operat ions according to the exemplary embodiment 2 wi l l be
described wi th reference to the flowchar t in Fig. 4. The operat ions are
broadly divided into two phases: a data registrat ion phase and an encrypted
25 text matching phase. In the data registrat ion phase, input data is input to
the registrat ion data generat ing device 100, encrypted, and registered wi th
the storage device 200 along wi th auxi l iary data . In the encrypted text
matching phase, the input data to the data conceal ing device 300 is
encrypted and then an ident i fier is output , the ident i fier being
27
corresponding to the encrypted data stored in the storage device 200 that
represents a plaintext being close (whose Hamming distance is smal l) to
the encrypted data and the auxi l iary data generated in the encrypt ion
process.
[00925 ]
Operat ions in the data regist rat ion phase are the same as those
described for the exemplary embodiment 1 wi th reference to Fig. 2 (A),
and thus thei r descript ions are omi t ted here.
[0093]
10 In the encrypted text matching phase, f irst , the inp ut data is input to
the encrypt ing uni t in the data conceal ing device 300 (Step C1 in Fig. 4) .
[0094]
Next , the key generat ing uni t 302 in the data conceal ing device 300
generates a key to be used for conceal ing the input data and outputs the key
15 to the encrypt ing uni t 301 and to the auxi l iary data generat ing uni t 303
(Step C2 in Fig. 4).
[0095]
Then, the encrypt ing uni t 301 in the data conceal ing device 300
calculates encrypted data that is obtained by encrypt ing the input data
20 using the input data in St ep C1 and the key in Step C2, and then inputs the
encrypted data into the encrypted text subtract ing uni t 502 in the data
matching device 500 (Step C3 in Fig. 4) .
[0096]
Next , the auxi l iary data generat ing uni t 303 in the data conceal ing
25 device 300 inputs par t of the auxi l iary data (encrypted data) to the one -way
convert ing uni t 304 (Step C4 in Fig. 4) .
[0097]
Then, an ident ifier is input from the al l data request ing uni t 501 in
the data matching device 500 to the ident ifier managing uni t 201 . The
28
encrypted data corresponding to the input ident i fier is input f rom the
encrypted text storage uni t 202 in the storage device 200 to the encrypted
text subtract ing uni t 502 in the data matching device 500 . In addi t ion,
the auxi l iary data corresponding to the inp ut ident i fier is input f rom the
auxi l iary data storage uni t 203 to the matching determining uni t 503 in th5 e
data matching device 500 (Step C5 in Fig. 4) .
[0098]
The encrypted text subtract ing uni t 502 in the data matching device
500, after receiving encrypted texts as inputs f rom the encrypted text
10 storage uni t 202 in the storage device 200 and from the encrypt ing uni t 301
in the data conceal ing device 300, outputs the difference between the two
input pieces of encrypted data to the matching determining un i t 503 (Step
C5 in Fig. 4).
[0099]
15 Next , the auxi l iary data f rom the auxi l iary data storage uni t 203 and
the auxi l iary data f rom the auxi l iary data generat ing uni t 303 are input to
the matching determining uni t 503, through communicat ions in concert
between the auxi l iary data storage uni t 203 in the storage device 200 and
the auxi l iary data generat ing uni t 303 in the data conceal ing device 300
20 under the control of the cont rol uni t 504 in the data matching device 500
(Step C6 in Fig. 4).
[0100]
The matching determining uni t 503 in the data matching device 500,
which has received, as an input , the difference between two pieces of
25 encrypted data f rom the encrypted text subtract ing uni t 502 in the data
matching device 500 in Step C5, and has received, as inputs, the
post -conversion auxi l iary data f rom the auxi l iary data storage uni t 203 in
the storage device 200 and the auxi l iary data from the auxi l iary data
generat ing uni t 303 in the data conceal ing device 300 in Step C6, generates
29
intermediate data f rom the di fference between the two pieces of encrypted
data and from the auxi l iary data, and outputs the intermediate data to the
one-way convert ing uni t 506 (Step C7 in Fig. 4).
[0101]
The one-way convert ing uni t 506 in the data matching device 505 0
generates post -conversion intermediate data produced through one -way
conversion per formed on the intermediate data, and outputs the
post -conversion intermediate data to the matching determining uni t 503 in
the data matching device 500 (Step C8 in Fig. 4).
10 [0102]
The matching determining uni t 503 in the data matching device 500
determines, based on:
- the post -conversion intermediate data; and
- the auxi l iary data,
15 whether the Hamming distance between the plaintext of the
encrypted data that has been input to the encr ypted text subt ract ing uni t
502 in the data matching device 500 in Step C3 and the plaintext of the
encrypted data that has been input to the encrypted text subt ract ing uni t
502 in the data matching device 500 in Step C5 is equal to or less than a
20 predetermined certain value, and outputs the determinat ion resul t (Step C9
in Fig. 4).
[0103]
If the resul t confirms the matching in Step C9, the ident i fier
output t ing uni t 505 in the data matching device 500 outputs the ident i fier
25 that has been input to the ident i fier managing uni t 201 in the storage
device 200 in Step C4 (Step C10 in Fig. 4).
[0104]
The processes f rom Step C5 to Step C10 are repeated for every
ident if ier (corresponding to encrypted data and auxi l iary data) that is
30
stored in the storage device 200 and managed by the ident i fier managing
uni t 201 in the storage device 200.
[0105]
Note that the devices 100, 200, 300, and 500 shown in Fig. 3 may be
implemented on a single computer system, or may be configured a5 s
individual devices . Al ternat ivel y, the uni ts in each of the devices 100,
200, 300, and 500 may be configured in the form of individual devices .
Processes handled by individual uni ts in individual devices shown in Fig. 3
may be implemented by a program to be executed by a computer.
10 According to the present invent ion, a recording medium (semiconductor
memory or a magnet ic/opt ical disk) that records such program is provided .
The exemplary embodiments are further described below wi th reference to
more speci fic examples.
[0106]
15
An example 1 of the present invent ion wi l l be described in detai l
wi th reference to Fig. 1. The example 1 is a speci fic example of the
exemplary embodiment 1.
[0107]
20 In the data regist rat ion phase, first , an N-bi t binary st ring Z is input
to the encrypt ing uni t 101 in the regist rat ion data generat ing device 100.
[0108]
Then, the key generat ing uni t 102 in the registrat ion data generat ing
device 100 generates a key (a K-bi t random number ) S and outputs the key
25 to the encrypt ing uni t 101 and to the registrat i on auxi l iary data generat ing
uni t 103.
[0109]
Next , the encrypt ing uni t 101 calculates N-bi t encrypted data W1,
which is obtained by calculat ing an exclusive OR between an N-bi t code
31
word C obtained by encoding the input K-bi t key S wi th a binary BCH
code, and the N-bi t input data Z (the fol lowing equat ion (1) ), and then
stores the encrypted data into the encrypted text storage uni t 202 in the
storage device 200.
[01105 ]
W1 = C (+) Z ... (1)
[0111]
In the above equat ion, (+) represents a bi twise exclusive OR. It is
assumed that the binary BCH code used here is a code that inputs K-bi t
10 data and outputs N-bi t data (where N > K) and guarantees that a Hamming
distance between any di fferent code words is at least d.
[0112]
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 ing uni t 103, which in turn
15 calculates auxi l iary data W2 in accordance wi th the fol lowing equat ion (2) .
[0113]
W2 = (c, S) (+) h(W1, R) ... (2)
[0114]
In the above equat ion (2) ,
20 c is a K-bi t constant ;
R is an N-bi t random number (data less l ikely to be used
repeatedly) ;
(c, S) represents an inner product , that is, (A, B) represents an inner
product of A and B, where two pieces of K = (m * k) -bi t data A and B are
25 regarded as vectors into which A and B are divided in uni ts of k bi ts ( i t is
assumed that the calculat ion is performed on a Galois extension field GF
(2k ) );
(+) represents a bi twise exclusive OR; and
h is a cryptographic hash funct ion which generates k -bi t output data
32
(for example, SHA-256) .
[0115]
H(x, y, z) is defined here as a funct ion represented by the fol lowing
equat ion (3).
[01165 ]
H(x, y, z) = (c, x) (+) h( y, z) ... (3)
[0117]
H(x, y, z) sat isfies the fol lowing equat ion (4).
[0118]
10 H(a1, b1, c1) (+) H(a2, b2, c2) = H(a1 (+) a2, b1, c1) (+) h(b2, c2)
... (4)
[0119]
In addi t ion, for a random number r of (K - k) bi ts, let t ing C3 be the
code word data that is obtained through er ror -cor rect ing coding wi th a
15 BCH code appl ied to:
h(W1, N) | | r ... (5)
(where | | is an operat ion symbol represent ing concatenat ion of bi ts) ,
the regist rat ion auxi l iary data generat ing uni t 103 calculates auxi l iary data
W3 f rom C3 and N-bi t input data Z in accordance wi th the fol lowing
20 equat ion (6).
[0120]
W3 = C3 (+) Z ... (6)
[0121]
The regist rat ion auxi l iary data generat ing uni t 103 registers, as
25 auxi l iary data, the pair (W2, W3) as obtained in accordance wi th the above
equat ions (2) and (6) wi th the auxi l iary data storage uni t 203.
[0122]
When the above operat ions are completed, th e input data in the
storage device 200 can be assigned a unique ident i fier by the ident if ier
33
managing uni t 201 and can be later retrieved wi th the assigned ident i fier.
[0123]
The encrypted data W1, the auxi l iary data W2, and the auxi l iary
data W3, which are associated wi th an ident ifier i , are hereinaf ter denoted
as W1[ i] , W2[ i] , and W3[ i] , respect ivel 5 y.
[0124]
In the encrypted text matching phase, fi rst , an ident i fier i is input to
the ident i fier holding uni t 401 in the specif ied data matching device 400 .
The encrypted data W1[ i] cor responding to the input ident i fier i is read
10 from the encrypted text storage uni t 202 in the storage device 200 and is
input to the encrypted text subt ract ing uni t 402 in the speci fied data
matching device 400. In addi t ion, the auxi l iary data W2[ i] and the
auxi l iary data W3[ i] corresponding to input ident ifier i are read f rom the
auxi l iary data storage uni t 203 in the storage device 200 and are input to
15 the matching determining uni t 403 in the speci fied data matching device
400.
[0125]
Next , N-bi t binary st ring input data Z' (data to be matched) is input
to the encrypt ing uni t 301 in the data conceal ing device 300.
20 [0126]
Next , the key generat ing uni t 302 in the data conceal ing device 300
generates a key (a K-bi t random number ) S' to be used for conceal ing the
input data Z' , and outputs the key to the encrypt ing uni t 301 and to the
auxi l iary data generat ing uni t 303.
25 [0127]
The encrypt ing uni t 301 in the data conceal ing device 300
calculates encrypted data W1' , which is obta ined by calculat ing an
exclusive OR between the code word C' , which is obtained through
er ror-cor rect ing coding wi th a binary BCH code appl ied to the key S' as
34
input f rom the key generat ing uni t 302, and the input data Z' ( refer to the
fol lowing equat ion (7) ).
[0128]
W1' = C' (+) Z' ... (7)
[01295 ]
The encrypt ing uni t 301 in the data conceal ing device 300 inputs
the encrypted data W1' into the encrypted text subtract ing uni t 402 in the
speci fied data matching device 400.
[0130]
10 The encrypted text subtract ing uni t 402 in the speci fied data
matching device 400 receives, as inputs, the encrypted data W1' from the
encrypt ing uni t 301 in the data conceal ing device 300 and the encrypted
data W1[ i] corresponding to the ident i fier i from the encrypted text storage
uni t 202 in the storage device 200, and then calculates the di fference
15 (exclusive OR) between the two pieces of input encrypted data W1' and
W1[ i] (refer to the fol lowing expression (8)) .
[0131]
W1' (+) W[ i] ... (8)
[0132]
20 The encrypted text subtract ing uni t 402 in the speci fied data
matching device 400 suppl ies the di fference between the two pieces of
encrypted data W1' (+) W[ i] to the matching determining uni t 403.
[0133]
Next , for a random number ns and an element (generator) g of a
25 predetermined group G, the control uni t 404 in the speci fied data matching
device 400 calculates the fol lowing:
g_s = g**ns ... (9)
In the equat ion (9), g**ns represents the ns -th power of g on the
group G (** is an exponent iat ion operator) . Note that a group means a se t
35
wi th a binary operat ion  that abides by the fol lowing rules:
1. Associat ive law ( (a  b)  c = a  (b  c) for  a, b, c  G)
2. Existence of ident i ty element (a  e = e  a = a for  e G,  a 
G)
3. Existence of inverse element (  b  G, a  b = b  a = e for 5 a 
G)
The group G is a cycl ic group wi th respect to mul t ipl icat ion and is
const i tuted of a mul t ipl icat ive group Zp (= Z/pZ) of order p wi th a prime
number p, and a value of g**ns is given by a remainder (mod p) of modulo
10 a prime number p.
[0134]
The cont rol uni t 404 in the speci fied data matching device 400
outputs W3[ i] and g_s to the auxi l iary data generat ing uni t 303 in the data
conceal ing device 300.
15 [0135]
Next , the auxi l iary data generat ing uni t 303 in the data conceal ing
device 300 appl ies the decrypt ing process of the binary BCH code to the
value obtained by calculat ing an exclusive OR between W3[ i] and the input
data Z' (the fol lowing expression (10)) to obtain h', which is the decrypt ion
20 resul t .
[0136]
W3[ i] (+) Z' ... (10)
[0137]
The auxi l iary data generat ing uni t 303 in the data conceal ing device
25 300 calculates W2' and g_c, from the key S', the encrypted data W1' , the
decrypt ion resul t h' , and g, g_s in the equat ion (9), and the random number
nc, based on the fol lowing equat ions (11a) and (11b), and in cooperat ion
wi th the one-way convert ing uni t 304, and then outputs the calculated
values to the matching determining uni t 403 in the speci fied data matching
36
device 400.
[0138]
W2' = h(H(S' , W1' , g_s**nc) (+) h') ... (11a)
[0139]
g_c = g**nc ... (11b5 )
[0140]
Next , the matching determining uni t 403 in the speci fied data
matching device 400 appl ies the decrypt ing process of the binary BCH
code to the di fference between two pieces of encrypted input data W1' and
10 W[ i] (the fol lowing expression (12) ) to calculate T, which is a resul t of
decrypt ing the di fference between the two pieces of encrypted data W1'
and W[ i] .
[0141]
W1' (+) W[ i] ... (12)
15 [0142]
The one-way convert ing uni t 405 in the speci fied data matching
device 400 calculates a cryptographic hash funct ion, h, in accordance wi th
the expression (13) on the calculat ion resul t of an exclusive OR operat ion:
H(T, W1' , g_c**ns) (+) W2[ i]
20 between H(T, W1' , g_c**ns), which is a resul t of calculat ing H in the
equat ion (3) by using T, which is a resul t of decrypt ing the di fference
between two pieces of encrypted data W1' and W[ i] as calculated by the
matching determining uni t 403, W1' (the equat ion (7)) , and g_c**ns (where
g_c is the equat ion (11b) and ns is the random number in the equat ion (9) ),
25 and W2[ i] , which is read f rom the auxi l iary data storage uni t 203.
[0143]
h(H(T, W1' , g_c**ns) (+) W2[ i] ) ... (13)
[0144]
Then, the matching determining uni t 403 in the speci fied data
37
matching device 400 checks whether the hash value as calcul ated in
accordance wi th the above expression (13) is equal to the auxi l iary data
W2' , which has been input f rom the auxi l iary data generat ing uni t 303 in
the data conceal ing device 300; in other words i t checks whether the
fol lowing equat ion (14) is sat isf ied5 .
[0145]
W2' = h(H(T, W1, g_c**ns) (+) W2[ i] ) ... (14)
[0146]
The matching determining uni t 403 in the speci fied data matching
10 device 400 outputs a determinat ion resul t by determining that the Hamming
distance between the original input data (plaintex t ) Z of W1[ i] and the
input data to be matched (plaintext) Z' is equal to or less than d if the
equat ion (14) is sat isfied, or by determining that the Hamming distance
between the original input data (plaintext) Z of W1[ i] and the input data to
15 be matched (plaintext) Z' exceeds d i f the equat ion (14) is not sat isfied .
Note that the above-described BCH coding assumes that a Hamming
distance between any di fferent code words exceeds at least d.
[0147]
Both of the matching determining uni t 403 in the speci fie d data
20 matching device 400 and the auxi l iary data generat ing uni t 303 in the data
conceal ing device 300 may be configured to generate g_s**nc (=
(g**ns)**nc) (= R') in the auxi l iary data W2' = h(H(S' , W1' , g_s**nc) (+)
h') , which is generated by the auxi l ia ry data generat ing uni t 303 in the data
conceal ing device 300; and g_c**ns (= (g**nc)**ns) in the matching
25 determining uni t 403 in the specif ied data matching device 400, through
the use of, for example, the known Di ff ie -Hel lman key exchange method.
[0148]

An example 2 wi l l be described in detai l wi th reference to Fig. 3.
38
The example 2 is a speci fic example of the exemplary embodiment 2.
[0149]
In the data regist rat ion phase, first , an N-bi t binary st ring Z is input
to the encrypt ing uni t 101 in the regist rat ion data generat ing device 100.
[01505 ]
Then, the key generat ing uni t 102 in the registrat ion data generat ing
device 100 generates a K-bi t random number S and outputs the number to
the encrypt ing uni t 101 and to the regist rat ion auxi l iary data generat ing
uni t 103.
10 [0151]
Next , the encrypt ing uni t 101 calculates encrypted data W1, which
is obtained by calculat ing an exclusive OR between a code word C obtained
by encoding the input key S wi th a binary BCH code, and the input data Z,
and then stores the encrypted data into the encrypted text storage uni t 202.
15 It is assumed that the binary BCH code used here is a code that inputs K-bi t
data and outputs N-bi t data and guarantees that a Hamming distance
between any di fferent code words is at lea st d.
[0152]
Next , the input data Z, the key S, and the encrypted data W1 are
20 input to the regist rat ion auxi l iary data generat ing uni t 103 . The
regist rat ion auxi l iary data generat ing uni t 103 calculates W2 in accordance
wi th the fol lowing equat ion (15).
[0153]
W2 = (c, S) (+) h(W1, R) ... (15)
25 [0154]
In the above equat ion (15),
c is a K-bi t constant ;
R is a random number (data less l ikely to be used repeatedly) ;
(A, B) is an inner product of A and B, where two pieces of K = (m *
39
k)-bi t data A and B are regarded as vectors into which A and B are divided
in uni ts of k bi ts (i t is assumed that the calculat ion is performed on a
Galois extension field GF (2k )) ;
(+) represents a bi twise exclusive OR; and
h is a cryptographic hash funct ion which generates k-bi t output dat5 a
(for example, SHA-256) .
[0155]
H(x, y, z) is defined as a funct ion represented by the equat ion (16)
(the same as the equat ion (3) above).
10 [0156]
H(x, y, z) = (c, x) (+) h( y, z) ... (16)
[0157]
For a random number r of K - k bi ts, let t ing C3 be the code word
data that is obtained by encoding:
15 h(W1, N) | | r ... (17)
(where | | is an operat ion symbol represent ing concatenat ion of bi ts)
wi th a BCH code, the regist rat ion auxi l iary data generat ing uni t 103
calculates W3 f rom C3 and Z in accordance wi th the fol lowing equat ion:
W3 = C3 (+) Z ... (18)
20 [0158]
The regist rat ion auxi l iary data generat ing uni t 103 registers, as
auxi l iary data, the pair (W2, W3) as generated above wi th the auxi l iary
data storage uni t 203.
[0159]
25 When the above operat ions are completed, the input data in the
storage device 200 can be assigned a unique ident i fier by the ident if ier
managing uni t 201 and can be later retrieved wi th the assigned ident i fier .
W1, W2, and W3, which are associated wi th an ident i fier i , are hereinafter
denoted as W1[ i] , W2[ i] , and W3[ i] , respect ivel y.
40
[0160]
In the encrypted text matching phase, fi rst , the input data Z' (data
to be matched) is input to the encrypt ing uni t 301 in the data conceal ing
device 300.
[01615 ]
Next , the key generat ing uni t 302 in the data conceal ing device 300
generates a key S' (a K-bi t random number) to be used for conceal ing the
input data Z' , and outputs the key to the encrypt ing uni t 301 and to the
auxi l iary data generat ing uni t 303.
10 [0162]
The encrypt ing uni t 301 in the data conceal ing device 300
calculates encrypted data W1' (the fol lowing equat ion (19) ), which is
obtained by calculat ing an exclusive OR between a code word C', which is
obtained by encoding the input key S' wi th a binary BCH code, and the
15 input data Z' , and then stores the encrypted data in the encrypted text
subt ract ing uni t 502 in the data matching device 500.
[0163]
W1' = C' (+) Z' ... (19)
[0164]
20 Next , the al l data request ing uni t 501 in the data matching device
500 inputs an ident if ier i to the ident ifier managing uni t 201 in the storage
device 200. The encrypted data W1[ i] cor responding to the input
ident if ier i is read from the encrypted text storage uni t 202 in the storage
device 200 and is input to the encrypted text subtract ing uni t 5 02 in the
25 data matching device 500. In addi t ion, the auxi l iary data W2[ i] and the
auxi l iary data W3[ i] corresponding to the ident if ier i are read f rom the
auxi l iary data storage uni t 203 in the storage device 200, and th en input to
the matching determining uni t 503 in the data matching device 500.
[0165]
41
The encrypted text subtract ing uni t 502 in the data matching device
500 receives:
- the encrypted data W1[ i] from the encrypted text storage uni t 202
in the storage device 200; and
- the encrypted data W1' f rom the data conceal ing device 300, a5 s
inputs,
and outputs the di fference between the two pieces of the input
encrypted data W1' and W1[ i] (exclusive OR) (the fol lowing expression
(20) ) to the matching determining uni t 503.
10 [0166]
W1' (+) W1[ i] ... (20)
[0167]
Next , for a random number ns and an element g of a predetermined
group G, the control uni t 504 in the data matching device 500 calculates the
15 fol lowing:
g_s = g**ns ... (21)
and outputs the resul t to the auxi l iary data generat ing uni t 303.
[0168]
Next , the auxi l iary data generat ing uni t 303 in the data conceal ing
20 device 300 randomly selects S1' and S2', which sat isf y:
S' = S1' (+) S2' ... (22)
[0169]
In cooperat ion wi th the one-way conver t ing uni t 304, the auxi l iary
data generat ing uni t 303 in the data conceal ing device 300 calculates W2'
25 and g_c based on the fol lowing equat ions (23a) and (23b).
[0170]
W2' = h(H(S1' , W1', g_s**nc) ) ... (23a)
[0171]
g_c = g**nc ... (23b)
42
[0172]
Next , f rom C3, which is obtained through binary BCH
er ror-cor rect ing coding appl ied to the data conceal ing from concatenat ion
of bi ts on an inner product (c, S2') and a random number r ':
(c, S2') | | r ' ... (245 )
and f rom Z' , the auxi l iary data generat ing uni t 303 in the data
conceal ing device 300 calculates W3' in a ccordance wi th the fol lowing
equat ion:
W3' = C3 (+) Z' ... (25)
10 and outputs W1' , W2' , W3' and g_c to the matching determining
uni t 503 in the data matching device 500.
[0173]
Next , the matching determining uni t 503 in the data matching
device 500 appl ies the decrypt ing process of the binary BCH code to the
15 difference between two pieces of input encrypted data:
W1' (+) W1[ i] ... (26)
to calculate T, which is a resul t of decrypt ing the di fference between the
two pieces of encrypted data W1' and W1[ i] .
[0174]
20 In addi t ion, the matching determining uni t 503 in the data matching
device 500 appl ies the decrypt ing process of the binary BCH code to the
exclusive OR between W3[ i] and W3':
W3[ i] (+) W3' ... (27)
to calculate w3, which is a resul t of decrypt ing W3 [ i] (+) W3' .
25 [0175]
The matching determining uni t 503 in the data matching device 500
outputs to the one-way conver t ing uni t 506 the resul t H(T, W1', g_c**ns),
which is calculated in accordance wi th the equat ion (16) by using T, which
is a resul t of decrypt ing the di fference between two pieces of encrypted
43
data, and W1' and g_c**ns, as wel l as output t ing W2[ i] and w3 to the
one-way convert ing uni t 506.
[0176]
The one-way convert ing uni t 506 in the data matching device 500
calculates a hash value (the fol lowing expression (28) ) of the resul t of 5 a
bi twise exclusive OR among H(T, W1', g_c**ns), W2[ i] , and w3:
H(T, W1 ’ , g _ c* * n s ) ( + ) W2 [ i ] ( +) w3
as calculated on H(T, W1', g_c**ns), which is obtained through calculat ion
using T, which is a resul t of decrypt in g the di fference between two pieces
10 of encrypted data, and W1' and g_c**ns.
[0177]
h (H(T, W1 ’ , g _ c* * n s ) ( + ) W2 [ i ] ( +) w3 ) ... (28)
[0178]
The matching determining uni t 503 in the data matching device 500
15 checks whether the hash value calculated by the on e-way convert ing uni t
506 in accordance wi th the above expression (28) is equal to W2' ( equat ion
(23a)); in other words i t checks whether the equat ion (29) is sat isfied.
[0179]
W2 ’ = h (H(T, W1 ’ , g _ c* * n s ) ( +) W2 [ i ] ( + ) w3 ) ... (29)
20 [0180]
If the above equat ion (29) is sat isfied, the ident i fier output t ing uni t
505 in the data matching device 500 determines that the Hamming distance
between the original data of W1[ i] and Z' is equal to or less than d and
outputs the ident i fier i . If the above equat ion (29) is not sat isfied, the
25 ident if ier output t ing uni t 505 in the data matching device 500 determines
that the Hamming distance exceeds d and thus does not output the
ident if ier i .
[0181]
The above operat ions are repeated on every ident i fier i , which is
44
managed by the storage device, to output every ident if ier for any original
data whose Hamming distance to the input data Z' is equal to or less than d.
[0182]
Simi larly to the example 1, in the example 2, both of the matching
determining uni t 503 in the data mat ching device 500 and the auxi l iary dat5 a
generat ing uni t 303 in the data conceal ing device 300 may be configured to
generate g_s**nc (= (g**ns)**nc) in the auxi l iary data W2' = h(H(S1' ,
W1' , g_s**nc) ), which is generated by the auxi l iary data generat ing uni t
303 in the data conceal ing device 300 and g_c**ns (= (g**nc)**ns) in the
10 matching determining uni t 503 in the data matching device 500, through
the use of, for example, the known Di ff ie -Hel lman key exchange method.
[0183]
Example appl icat ions of the example 1 or 2 include authent icat ion
where biomet ric informat ion is protected . The fol lowing out l ines such
15 authent icat ion.
[0184]
The input data in the data registrat ion phase and the input data in
the encrypted text matching phase may be biometr ic informa t ion obtained
from fingerprints, veins, or the l ike . In this case, whi le the biomet ric
20 informat ion remains concealed (encrypted), i t can be determined whether
the encrypted biomet ric data stored in the storage device and the encrypted
biometr ic data t ransmi t ted f rom the data conceal ing device have been taken
from the same person, depending on whether the Hamming distance
between the two pieces of input data is equal to or less than a
25 predetermined certain value, thereby achieving authent icat ion.
Concerning biomet ric informat ion, the same data may not always be
obtained steadi ly. However, i t can be assumed that pieces of data
obtained f rom the same person are simi lar to one another (a Hamming
distance between two pieces of such data is smal l ) . Therefore, the
45
present invent ion is regarded as sui table for appl icat ion to, for example,
biometr ic authent icat ion (however, i t should be noted that the appl icat ion
is not l imi ted to biomet ric authent icat ion).
[0185]
The respect ive disclosures of the patent and non -patent l i terature5 s
described above are incorporated herein by reference . Modi f icat ions and
adjustments of exemplary embodiments and examples may be made wi thin
the bounds of the ent ire disclosure (including the scope of the claims) of
the present invent ion, and also based on fundamental technological
10 concepts thereof . Furthermore, various combinat ions and select ions of
various disclosed elements (including respect ive elements of the respect ive
claims, respect ive elements of the respect ive examples, respec t ive
elements of the respect ive drawings, and the l ike) are possible wi thin the
bounds of the claims of the present invent ion . That is, the present
15 invent ion clearly includes every type of t ransformat ion and modif icat ion
that a person ski l led in the art c an real ize according to the ent i re disclosure
of the present invent ion including the claims and to technological concepts
thereof.
Reference Signs List
20 [0186]
10 Encrypted text matching system (device)
11, 12 Encrypt ing means (uni t)
13 Storage device
14 Auxi l iary data generat ing means (uni t )
25 14h, 15h One-way convert ing means (uni t )
15 Matching determining means (uni t)
100 Registrat ion data generat ing device
101 Encrypt ing uni t
102 Key generat ing uni t
46
103 Registrat ion auxi l iary data generat ing uni t
104 One-way convert ing uni t
200 Storage device
201 Ident i fier managing uni t
202 Encrypted text storage uni 5 t
203 Auxi l iary data storage uni t
300 Data conceal ing device
301 Encrypt ing uni t
302 Key generat ing uni t
10 303 Auxi l iary data generat ing uni t
304 One-way conver t ing uni t
400 Specif ied data matching device
401 Ident i fier holding uni t
402 Encrypted text subt ract ing uni t
15 403 Matching determining uni t
404 Control uni t
405 One-way convert ing uni t
500 Data matching device
501 Al l data request ing uni t
20 502 Encrypted text subt ract ing uni t
503 Matching determining uni t
504 Control uni t
505 Ident i fier output t ing uni t
506 One-way convert ing uni t

CLAIMS
[Claim 1]
An encrypted text matching system comprising:
means for generat ing fi rst auxi l iary data and second auxi l iary dat a,
respect ivel y, which are for veri ficat ion of matching between a firs5 t
encrypted text that is obtained by encrypt ing input data and is registered
wi th a storage device and a second encrypted text that is obtained by
encrypt ing input data to be matched, th e verif icat ion being performed by
using a Hamming distance between plaintexts; and
10 means for per forming one-way conversion on at least part of the
second auxi l iary data, performing one-way conversion on intermediate data
that is generated based on a di ffe rence between the fi rst encrypted text and
the second encrypted text and on the fi rst auxi l iary data, and determining,
by using a resul t of the one-way conversion performed on the intermediate
15 data as wel l as using the second auxi l iary data that underwent the one-way
conversion, whether a Hamming distance between plaintexts is equal to or
less than a predetermined certain value, the Hamming distance
corresponding to the difference between the fi rst encrypted text and the
second encrypted text .
20 [Claim 2]
The encrypted text matching system according to claim 1,
wherein the encrypted text is a resul t of an exclusive OR operat ion
between a code word, which is obtained by encoding a key for encrypt ing
the plaintext of the input data wi th an er ror -cor rect ing code having
25 l ineari t y, and the plaintext ,
and wherein the system calculates each of the fi rst auxi l iary data
and the second auxi l iary data that are related to the encrypted text
registered wi th the storage device and the encrypted text of the input data
to be matched, respect ivel y, based on a resul t of one -way conversion on an
48
exclusive OR between an inner product of the corresponding key and a
constant , and an output of a cryptographic hash funct ion for a bi t string
that is based on the cor responding encrypt ed text .
[Claim 3]
The encrypted text matching system according to claim 15 ,
comprising:
a regist rat ion data generat ing device;
a storage device;
a data conceal ing device; and
10 a speci fied data matching device,
wherein the regist rat ion data generat ing device comprises:
a first encrypt ing uni t which receives fixed-length input data and a
key, as inputs, and outputs an encrypted text that is obtained by encrypt ing
the input data wi th the key,
15 the encrypted text sat isfying a relat ionship where the sum of an
encrypted text 1 obtained by encrypt ing a plaintext 1 wi th a key 1 and an
encrypted text 2 obtained by encrypt ing a plaintext 2 wi th a key 2 is equal
to an encrypted text obtained by encrypt ing the sum of the plaintext 1 and
the plaintext 2 wi th the sum of the key 1 and the key 2;
20 a fi rst key generat ing uni t which generates the key to be input to the
first encrypt ing uni t ; and
a regist rat ion auxi l iary data generat ing uni t which receives the
input data and the key generated by the fi rst key generat ing uni t , as inputs,
and outputs the fi rst auxi l iary data for verifying that a Hamming distance
25 between a plaintext of the f irst encrypted text output from the fi rst
encrypt ing uni t and a plaintext of the second encrypted text output from
the data conceal ing device is equal to or less than a predetermined certain
value,
and wherein the storage device comprises:
49
an encrypted text storage uni t which stores one or more of the
encrypted texts output f rom the fi rst encrypt ing uni t in the registrat ion data
generat ing device;
an auxi l iary data storage uni t which stores one or more pieces of the
auxi l iary data output f rom the regist rat ion auxi l iary data generat ing uni t i5 n
the registrat ion data generat ing device; and
an ident i fier managing uni t which receives an ident i fier, as an
input , from the speci fied data matching device and causes the encrypted
text storage uni t and the auxi l iary data storage uni t to output the encrypted
10 text and the first auxi l iary data that cor respond to the ident i fier,
respect ivel y,
and wherein the data conceal ing device compr ises:
a second encrypt ing uni t which receives f ixed-length input data and
a key, as inputs, and outputs an encrypted text that is obtained by
15 encrypt ing the input data wi th the key, the encrypted text sat isfying a
relat ionship where the sum of an encrypted text 1 obtained by encrypt ing a
plaintext 1 wi th a key 1 and an encrypted text 2 obtained by encrypt ing a
plaintext 2 wi th a key 2 is equal to an encrypted text obtained by
encrypt ing the sum of the plaintext 1 and the plaintext 2 wi th the sum of
20 the key 1 and the key 2;
a second key generat ing uni t which generates the key to be input t o
the second encrypt ing uni t ;
an auxi l iary data generat ing uni t which receives the input data and
the key generated by the second key generat ing uni t , as inputs, and outputs
25 the second auxi l iary data for veri fying that a Hamming distance between a
plaintext of the second encrypted text output from the second encrypt ing
uni t and a plaintext of the f irst encrypted text output from the fi rs t
encrypt ing uni t in the registrat ion data generat ing device is equal to or less
than a predetermined cer tain value; and
50
a one-way convert ing uni t which outputs data obtained through
one-way conversion on at least part of the second auxi l iary data output
from the auxi l iary data generat ing uni t ,
and wherein the specified data matching device comprises:
an ident i fier holding uni t which receives an ident i fier, as an input 5 ,
outputs the ident i fier to the ident i fier managing uni t in the storage device,
and instructs the ident ifier managing uni t to output the encrypted text and
the auxi l iary data that cor respond to the ident if ier;
an encrypted text subtract ing uni t which receives the second
10 encrypted text output f rom the second encrypt ing uni t in the data
conceal ing device and the encrypted text read f rom the encrypted text
storage uni t in the storage device, as inputs, and outputs a di fference
between the input two encrypted texts;
a matching determining uni t which receives:
15 the di fference between the first and second encrypted texts, the
difference being output from the encrypted text subt ract ing uni t ;
the fi rst auxi l iary data read from the auxi l iary data storage uni t in
the storage device; and
the second auxi l iary data output from the auxi l iary data genera t ing
20 uni t in the data conceal ing device,
as inputs,
transmi ts to a one-way conver t ing uni t intermediate data which is
generated based on the di fference between the fi rst and second encrypted
texts output f rom the encrypted text subtract ing uni t and on th e first
25 auxi l iary data read f rom the auxi l iary data storage uni t in the storage
device, and
determines whether a Hamming distance between plaintexts
corresponding to the difference between the fi rst and second encrypted
texts is equal to or less than a pr edetermined cer tain value, by determining
51
whether post -one-way conversion data generated by the one -way
convert ing uni t based on the intermediate data is equal to one piece of the
second auxi l iary data that underwent one -way conversion and is output
from the auxi l iary data generat ing uni t in the data conceal ing device;
the one-way convert ing uni t which receives, as an input , th5 e
intermediate data calculated by the matching determining uni t and outputs
a resul t of one-way conversion per formed on the intermediate data; and
a control uni t which controls data exchanges between the data
conceal ing device and the speci fied data matching device.
10 [Claim 4]
The encrypted text matching system according to claim 1,
comprising:
a regist rat ion data generat ing device;
a storage device;
15 a data conceal ing device; and
a data matching device,
wherein the regist rat ion data generat ing device comprises:
a first encrypt ing uni t which receives fixed-length input data and a
key, as inputs, and outputs an encrypted text that is obtained by encrypt ing
20 the input data wi th the key,
the encrypted text sat isfying a relat ionship where the sum of an
encrypted text 1 obtained by encrypt ing a plaintext 1 wi th a key 1 and an
encrypted text 2 obtained by encrypt ing a plaintext 2 wi th a key 2 is equal
to an encrypted text obtained by encrypt ing the sum of the plaintext 1 and
25 the plaintext 2 wi th the sum of the key 1 and the key 2;
a fi rst key generat ing uni t which generates the key to be input to the
first encrypt ing uni t ; and
a regist rat ion auxi l iary data generat ing uni t which receives the
input data and the key generated by the fi rst key generat ing uni t , as inputs,
52
and outputs the fi rst auxi l iary data for verifying that a Hamming distance
between a plaintext of the f irst encrypted tex t output from the fi rst
encrypt ing uni t and a plaintext of the second encrypted text output from
the data conceal ing device is equal to or less than a predetermined value,
and wherein the storage device comprises5 :
an encrypted text storage uni t which sto res one or more of the
encrypted texts output f rom the fi rst encrypt ing uni t in the registrat ion data
generat ing device;
an auxi l iary data storage uni t which stores one or more pieces of the
10 auxi l iary data output f rom the regist rat ion auxi l iary data gener at ing uni t in
the registrat ion data generat ing device; and
an ident i fier managing uni t which receives an ident i fier, as an
input , from the data matching device and causes the encrypted text storage
uni t and the auxi l iary data storage uni t to output an enc rypted text and
15 auxi l iary data that cor respond to the ident ifier, respect ivel y,
and wherein the data conceal ing device compr ises:
a second encrypt ing uni t which receives f ixed-length input data and
a key, as inputs, and outputs an encrypted text that is obtained by
encrypt ing the input data wi th the key,
20 the encrypted text sat isfying a relat ionship where the sum of an
encrypted text 1 obtained by encrypt ing a plaintext 1 wi th a key 1 and an
encrypted text 2 obtained by encrypt ing a plaintext 2 wi th a key 2 is equal
to an encrypted text obtained by encrypt ing the sum of the plaintext 1 and
the plaintext 2 wi th the sum of the key 1 and the key 2;
25 a second key generat ing uni t which generates the key to be input t o
the second encrypt ing uni t ;
an auxi l iary data generat ing uni t which receives the input data and
the key generated by the second key generat ing uni t , as inputs, and outputs
the second auxi l iary data for veri fying that a Hamming distance between a
53
plaintext of the second encrypted text output from t he second encrypt ing
uni t and a plaintext of the f irst encrypted text output from the fi rst
encrypt ing uni t in the registrat ion data generat ing device is equal to or less
than a predetermined cer tain value; and
a one-way convert ing uni t which outputs data obtained throug5 h
one-way conversion on at least part of the second auxi l iary data output
from the auxi l iary data generat ing uni t ,
and wherein the data matching device comprises:
an al l data request ing uni t which inputs into the ident if ier managing
10 uni t an inst ruct ion for sequent ial ly reading every piece of data stored in
the storage device, in accordance wi th an inst ruct ion from an ident if ier
output t ing uni t ;
an encrypted text subtract ing uni t which receives the second
encrypted text output f rom the second encrypt ing uni t in the data
15 conceal ing device and the fi rst encrypted text stored in the encrypted text
storage uni t in the storage device, as inputs, and outputs a di fference
between the input first and second encrypted texts;
a matching determining uni t which receives:
the di fference between the first and second encrypted texts, the
20 difference being output from the encrypted text subt ract ing uni t ;
the fi rst auxi l iary data read from the auxi l iary data storage uni t in
the storage device; and
the second auxi l iary data output from the auxi l iary data generat ing
uni t in the data conceal ing device,
25 as inputs,
transmi ts to a one-way conver t ing uni t intermediate data which is
generated based on the di fference between the fi rst and second encrypted
texts output f rom the encrypted text subtract ing uni t and on the first
auxi l iary data read f rom the auxi l iary data storage uni t in the storage
54
device, and
determines whether a Hamming distance between plaintexts
corresponding to the difference between the fi rst and second encrypted
texts is equal to or less than a predetermined cer tain value, by determining
whether post -one-way conversion data generated by the one -wa5 y
convert ing uni t based on the intermediate data is equal to one piece of the
second auxi l iary dat a that underwent one-way conversion and is output
from the auxi l iary data generat ing uni t in the data conceal ing device;
the one-way convert ing uni t which receives, as an input , the
10 intermediate data calculated by the matching determining uni t and outputs
a resul t of one-way conversion per formed on the intermediate data; and
the ident i fier output t ing uni t which receives, as inputs, an output of
a determinat ion resul t f rom the matching determining uni t and an output
from the ident i fier managing uni t and outputs an ident ifier cor responding
15 to the data for which the matching determining uni t determines that the
Hamming distance between plaintexts is equal to or less than a
predetermined certain value; and
a control uni t which controls data exchanges between the data
conceal ing device and the speci fied data matching device.
20 [Claim 5]
The encrypted text matching system according to claim 3 or 4,
wherein, for the key and the plaintext of the input data, each of the fi rst
and second encrypt ing uni ts encodes the key wi th an error-correct ing code
having l ineari ty and outputs, as the encrypted text , a resul t of calculat ing a
25 vectorial sum of a code word, which is an encoded resul t of
er ror-cor rect ing coding, and the plaintext .
[Claim 6]
The encrypted text matching system according to claim 3 or 4,
wherein the fi rst auxi l iary data output f rom the regist rat ion
55
auxi l iary data generat ing uni t in the registrat ion data generat ing device
comprises data that is calculated according to the fol lowing equat ion:
let t ing S be a key that is input to the f irst encrypt ing uni t in the
regist rat ion data generat ing device;
let t ing W1 be an encrypted text that is output f rom the f irs5 t
encrypt ing uni t ; and
let t ing R be data that is less l ikely to be repeatedly used,
(c, S) (+) h(W1, R)
(where c is a constant ; (x, y) represents an inner product of vectors
10 x and y, and (c, S) is an inner product of c and S; h is a cryptographic hash
funct ion; and (+) represents a bi twise exclusive OR) ,
and wherein the second auxi l iary data output from the auxi l iary
data generat ing uni t in the data conceal ing device comprises data that is
calculated according to the fol lowing equat ion:
15 let t ing S' be a key that is input to the second encrypt ing uni t in the
data conceal ing device;
let t ing W1' be an encrypted text that is output f rom the second
encrypt ing uni t ; and
let t ing R' be data that is less l ikely to be repeatedly used,
20 (c, S') (+) h(W1', R') .
[Claim 7]
The encrypted text matching system according to claim 6, wherein
the R' is generated by both of the matching determining uni t in the
speci fied data matching device or in the data matching device and the
25 auxi l iary data generat ing uni t in the data conceal ing device through the use
of a Di ffie-Hel lman key exchange method.
[Claim 8]
A biomet ric authent icat ion system comprising the encrypted text
matching system according to any one of claims 1 to 7, wherein biomet ric
56
authent icat ion is per formed by generat ing, based on biometr ic informat ion,
input data to be input to the regist rat ion data generat ing dev ice and to the
data conceal ing device, and by determining whether data input to the
speci fied data matching device or the data matching device via the data
conceal ing device matches data stored in the storage device5 .
[Claim 9]
A method for matching encrypted texts, compr ising:
generat ing fi rst auxi l iary data and second auxi l iary data,
respect ivel y, which are for veri ficat ion of matching between a first
10 encrypted text that is obtained by encrypt ing input data and is registered
wi th a storage device and a s econd encrypted text that is obtained by
encrypt ing input data to be matched, the verif icat ion being performed by
using a Hamming distance between plaintexts; and
performing one-way conversion on at least part of the second
15 auxi l iary data, performing one -way conversion on intermediate data that is
generated based on a di fference between the fi rst encrypted text and the
second encrypted text and on the fi rst auxi l iary data, and determining, by
using a resul t of the one -way conversion performed on the intermediate
data as wel l as using the second auxi l iary data that underwent the one -way
20 conversion, whether a Hamming distance between plaintexts is equal to or
less than a predetermined certain value, the Hamming distance
corresponding to the difference between the fi rst encrypted text and the
second encrypted text .
[Claim 10]
25 A program causing a computer to execute:
a process which generates f irst auxi l iary data and second auxi l iary
data, respect ivel y, which are for veri ficat ion of matching between a fi rst
encrypted text that is obtained by encrypt ing input data and is registered
wi th a storage device and a second encrypted text that is obtained by
57
encrypt ing input data to be matched, the verif icat ion being performed by
using a Hamming distance between plaintexts; and
a process which performs one -way conversion on at least part of the
second auxi l iary data, per forms one -way conversion on intermediate data
that is generated based on a di fference between the fi rst encrypted text an5 d
the second encrypted text and on the fi rst auxi l iary data, and determines,
by using a resul t of the one-way conversion performed on the intermediate
data as wel l as using the second auxi l iary data that underwent the one -way
conversion, whether a Hamming distance between plaintexts is equal to or
10 less than a predetermined certain value, the Hamming distance
corresponding to the difference between the fi rst encrypted text and the
second encrypted text