WO2021070838A1 - 秘匿認証方法および秘匿認証システム - Google Patents

秘匿認証方法および秘匿認証システム Download PDF

Info

Publication number
WO2021070838A1
WO2021070838A1 PCT/JP2020/037925 JP2020037925W WO2021070838A1 WO 2021070838 A1 WO2021070838 A1 WO 2021070838A1 JP 2020037925 W JP2020037925 W JP 2020037925W WO 2021070838 A1 WO2021070838 A1 WO 2021070838A1
Authority
WO
WIPO (PCT)
Prior art keywords
decentralized
feature amount
user
lsh
secret
Prior art date
Legal status (The legal status is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the status listed.)
Ceased
Application number
PCT/JP2020/037925
Other languages
English (en)
French (fr)
Inventor
直央 西田
達海 大庭
勇二 海上
唯紀 照屋
ナッタポン アッタラパドゥン
花岡　悟一郎
Current Assignee (The listed assignees may be inaccurate. Google has not performed a legal analysis and makes no representation or warranty as to the accuracy of the list.)
Panasonic Intellectual Property Corp of America
Original Assignee
Panasonic Intellectual Property Corp of America
Priority date (The priority date is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the date listed.)
Filing date
Publication date
Application filed by Panasonic Intellectual Property Corp of America filed Critical Panasonic Intellectual Property Corp of America
Priority to JP2021551675A priority Critical patent/JP7524205B2/ja
Priority to EP20873984.7A priority patent/EP4044157A4/en
Publication of WO2021070838A1 publication Critical patent/WO2021070838A1/ja
Priority to US17/546,606 priority patent/US11995211B2/en
Anticipated expiration legal-status Critical
Ceased legal-status Critical Current

Links

Images

Classifications

    • G—PHYSICS
    • G06—COMPUTING OR CALCULATING; COUNTING
    • G06F—ELECTRIC DIGITAL DATA PROCESSING
    • G06F21/00—Security arrangements for protecting computers, components thereof, programs or data against unauthorised activity
    • G06F21/60—Protecting data
    • G06F21/62—Protecting access to data via a platform, e.g. using keys or access control rules
    • G06F21/6218—Protecting access to data via a platform, e.g. using keys or access control rules to a system of files or objects, e.g. local or distributed file system or database
    • G06F21/6245—Protecting personal data, e.g. for financial or medical purposes
    • G—PHYSICS
    • G06—COMPUTING OR CALCULATING; COUNTING
    • G06F—ELECTRIC DIGITAL DATA PROCESSING
    • G06F21/00—Security arrangements for protecting computers, components thereof, programs or data against unauthorised activity
    • G06F21/30—Authentication, i.e. establishing the identity or authorisation of security principals
    • G06F21/31—User authentication
    • G—PHYSICS
    • G06—COMPUTING OR CALCULATING; COUNTING
    • G06F—ELECTRIC DIGITAL DATA PROCESSING
    • G06F21/00—Security arrangements for protecting computers, components thereof, programs or data against unauthorised activity
    • G06F21/30—Authentication, i.e. establishing the identity or authorisation of security principals
    • G06F21/31—User authentication
    • G06F21/32—User authentication using biometric data, e.g. fingerprints, iris scans or voiceprints
    • G—PHYSICS
    • G06—COMPUTING OR CALCULATING; COUNTING
    • G06F—ELECTRIC DIGITAL DATA PROCESSING
    • G06F21/00—Security arrangements for protecting computers, components thereof, programs or data against unauthorised activity
    • G06F21/60—Protecting data
    • G06F21/602—Providing cryptographic facilities or services
    • G—PHYSICS
    • G09—EDUCATION; CRYPTOGRAPHY; DISPLAY; ADVERTISING; SEALS
    • G09C—CIPHERING OR DECIPHERING APPARATUS FOR CRYPTOGRAPHIC OR OTHER PURPOSES INVOLVING THE NEED FOR SECRECY
    • G09C1/00—Apparatus or methods whereby a given sequence of signs, e.g. an intelligible text, is transformed into an unintelligible sequence of signs by transposing the signs or groups of signs or by replacing them by others according to a predetermined system
    • H—ELECTRICITY
    • H04—ELECTRIC COMMUNICATION TECHNIQUE
    • H04L—TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION
    • H04L9/00—Cryptographic mechanisms or cryptographic arrangements for secret or secure communications; Network security protocols
    • H04L9/08—Key distribution or management, e.g. generation, sharing or updating, of cryptographic keys or passwords
    • H04L9/0816—Key establishment, i.e. cryptographic processes or cryptographic protocols whereby a shared secret becomes available to two or more parties, for subsequent use
    • H04L9/085—Secret sharing or secret splitting, e.g. threshold schemes
    • H—ELECTRICITY
    • H04—ELECTRIC COMMUNICATION TECHNIQUE
    • H04L—TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION
    • H04L9/00—Cryptographic mechanisms or cryptographic arrangements for secret or secure communications; Network security protocols
    • H04L9/32—Cryptographic mechanisms or cryptographic arrangements for secret or secure communications; Network security protocols including means for verifying the identity or authority of a user of the system or for message authentication, e.g. authorization, entity authentication, data integrity or data verification, non-repudiation, key authentication or verification of credentials
    • H04L9/3226—Cryptographic mechanisms or cryptographic arrangements for secret or secure communications; Network security protocols including means for verifying the identity or authority of a user of the system or for message authentication, e.g. authorization, entity authentication, data integrity or data verification, non-repudiation, key authentication or verification of credentials using a predetermined code, e.g. password, passphrase or PIN
    • H04L9/3231—Biological data, e.g. fingerprint, voice or retina
    • G—PHYSICS
    • G06—COMPUTING OR CALCULATING; COUNTING
    • G06F—ELECTRIC DIGITAL DATA PROCESSING
    • G06F2221/00—Indexing scheme relating to security arrangements for protecting computers, components thereof, programs or data against unauthorised activity
    • G06F2221/03—Indexing scheme relating to G06F21/50, monitoring users, programs or devices to maintain the integrity of platforms
    • G06F2221/031—Protect user input by software means
    • H—ELECTRICITY
    • H04—ELECTRIC COMMUNICATION TECHNIQUE
    • H04L—TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION
    • H04L2209/00—Additional information or applications relating to cryptographic mechanisms or cryptographic arrangements for secret or secure communication H04L9/00
    • H04L2209/46—Secure multiparty computation, e.g. millionaire problem
    • H—ELECTRICITY
    • H04—ELECTRIC COMMUNICATION TECHNIQUE
    • H04L—TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION
    • H04L2209/00—Additional information or applications relating to cryptographic mechanisms or cryptographic arrangements for secret or secure communication H04L9/00
    • H04L2209/50—Oblivious transfer

Definitions

  • This disclosure relates to a secret authentication method and a secret authentication system that authenticates a user while keeping the user information and information related to the user information secret.
  • biometric authentication With the improvement of image recognition performance using deep neural networks, the accuracy of authentication using, for example, a user's face image (so-called biometric authentication) has improved.
  • biometric authentication such as face authentication is used for payment at convenience stores or authentication at the time of admission to an amusement facility or an event venue.
  • the user In order for the user to use such an authentication service, the user needs to transmit the user's own information (that is, user information) or the feature amount obtained from the information to the server.
  • user information such as a face image is privacy information itself, it must be protected.
  • an attack that estimates the original user information from the feature amount of the user information is known, not only the user information but also the feature amount must be protected.
  • Non-Patent Document 1 encrypts the LSH (Locality Sensitive Hashing) value derived by the user terminal device and the feature amount of the user information and transmits the user information and the information related to the user information to the server. It discloses a technology that authenticates users while keeping it secret. Further, for example, in Non-Patent Document 2, the LSH value is calculated a plurality of times while keeping the input data (for example, the feature amount of the user information and the LSH parameter) concealed, and the inner product of the obtained vector and the random number vector is calculated in the hash table. The technology used as an index is disclosed.
  • LSH Location Sensitive Hashing
  • Non-Patent Document 1 cannot completely conceal the user information and the information related to the user information, so that the user information may be inferred. Further, in the technique described in Non-Patent Document 2, since it is necessary to execute LSH a plurality of times, the amount of calculation is enormous and the efficiency is low.
  • the present disclosure provides a secret authentication method and a secret authentication system that improve the confidentiality of user information and information related to the user information and improve the processing speed.
  • the uniform state of the secret authentication method of the present disclosure is a secret authentication method that performs an authentication process while keeping the input secret, and is a feature amount distributed by the secret sharing method, and user information about the user.
  • the first decentralized feature amount, which is the feature amount of, and the decentralized LSH parameter, which is a decentralized parameter of LSH (Locality Sensitive Hashing), are input, and the LSH process is executed while keeping the input concealed.
  • the decentralized LSH value which is the distributed LSH value
  • the derivated LSH value and the distributed key which is the key for executing the processing of the one-way function, are used.
  • a decentralized hash value which is a distributed hash value, is derived and derived by using a secret one-way function that executes the processing of the one-way function while keeping the input secret as an input with a certain distributed key.
  • a table in which a plurality of sets of a hash value as an index and a decentralized feature amount as a data string are stored in advance by decoding the decentralized hash value into a hash value de-distributed by the secret sharing method.
  • a set including a hash value matching the decoded hash value is selected from the plurality of sets, and the decentralized feature amount included in the selected set and the first
  • the similarity with the decentralized feature amount is calculated while being concealed, the authentication result of the user is derived while being concealed based on the calculated similarity, and the derived authentication result is output.
  • the uniform state of the secret authentication system of the present disclosure is a secret authentication system that performs authentication processing while keeping the input secret, and is a feature quantity distributed by the secret sharing method, which relates to a user.
  • a secret LSH that executes the LSH process while keeping the input secret is used.
  • the decentralized LSH value derivation unit for deriving the decentralized LSH value, which is the decentralized LSH value, the decentralized LSH value derived by the decentralized LSH value derivation unit, and the processing of the unidirectional function are executed.
  • a decentralized hash value derivation unit that derives a decentralized hash value, and a decoding unit that decodes the decentralized hash value derived by the decentralized hash value derivation unit into a hash value that has been de-distributed by the secret distribution method.
  • a secret hash table storage unit that stores a secret hash table, which is a table in which a plurality of sets of a hash value as an index and a distributed feature amount as a data column are stored in advance, and the secret hash table are used.
  • the decentralized authentication result derivation unit that calculates while concealing and derives the user's authentication result while concealing it based on the calculated similarity, and the authentication result derived by the decentralized authentication result derivation unit. It includes an output unit for output.
  • the confidential authentication method and the confidential authentication system of the present disclosure it is possible to improve the confidentiality of the user information and the information related to the user information, and improve the processing speed.
  • FIG. 1 is a diagram showing an example of the overall configuration of the confidential authentication system according to the embodiment.
  • FIG. 2 is a diagram showing an example of the configuration of the user terminal device according to the embodiment.
  • FIG. 3 is a diagram showing an example of the configuration of the data providing device according to the embodiment.
  • FIG. 4 is a diagram showing an example of the configuration of the data arithmetic unit according to the embodiment.
  • FIG. 5 is a diagram showing an example of the configuration of the authentication result utilization device according to the embodiment.
  • FIG. 6 is a sequence diagram showing an example of the operation of the initialization phase of the secret authentication system according to the embodiment.
  • FIG. 7 is a sequence diagram showing an example of the operation of the registration phase of the confidential authentication system according to the embodiment.
  • FIG. 1 is a diagram showing an example of the overall configuration of the confidential authentication system according to the embodiment.
  • FIG. 2 is a diagram showing an example of the configuration of the user terminal device according to the embodiment.
  • FIG. 3 is a diagram showing an example of
  • FIG. 8 is a sequence diagram showing an example of detailed processing in step S205 of FIG. 7.
  • FIG. 9 is a sequence diagram showing an example of the operation of the authentication phase of the confidential authentication system according to the embodiment.
  • FIG. 10 is a sequence diagram showing an example of detailed processing in step S405 of FIG.
  • FIG. 11 is a diagram showing an example of LSH parameters in the embodiment.
  • FIG. 12 is a diagram showing an example of the LSH value in the embodiment.
  • FIG. 13 is a diagram showing an example of a hash table.
  • FIG. 14 is a diagram showing an example of the decentralized feature amount in the embodiment.
  • FIG. 15 is a diagram showing an example of a secret hash table according to the embodiment.
  • FIG. 16 is a flowchart showing an example of the confidential authentication method according to the present embodiment.
  • biometric authentication includes not only a user's face image but also information on a user's physical characteristics such as a fingerprint image or an iris image, information on a user's behavioral characteristics such as a step or behavior history, or a user. It also includes certification using information about the characteristics of the property, such as document information possessed by.
  • One-to-one authentication refers to a user by reading the ID of the person to be collated from, for example, an ID card, and determining the identity between the user information registered in association with the ID and the sensed user information. This is a method of authentication.
  • 1-to-N authentication the sensed user information is linked to which ID from a database (for example, a table) that stores IDs of a plurality of users and user information associated with each of those IDs. It is a method of authenticating a user by determining whether or not it corresponds to the attached user information, or by determining whether or not it corresponds to any user information stored in the database.
  • one-to-N authentication which requires comparison with all user information registered in advance in the database, has a larger amount of processing. There are many cases, and the difficulty of the authentication process is high, but it is excellent in convenience because the user does not need to carry and present an ID card or the like.
  • the nearest neighbor search As a method of efficiently realizing 1-to-N authentication.
  • the feature amount of information about a plurality of users (so-called user information) registered in advance in a database or the like and the feature amount of user information sensed by a sensor such as a camera, a scanner, or a microphone for authentication.
  • the degree of similarity with the feature amount of the user information for authentication is calculated, and the feature amount closest to (that is, the most similar) to the feature amount of the user information for authentication is searched from the database. If the similarity between the nearest feature amount and the feature amount of the user information for authentication is equal to or less than the threshold value, the authentication fails, and if it is higher than the threshold value, the authentication is successful.
  • LSH Locality Sensitive Hashing
  • LSH is a technology that maps close input values to the same hash value.
  • LSH value the same hash value (hereinafter referred to as LSH value) is output when the feature amount of similar user information is input to LSH, so it is similar to the user information sensed for authentication. It is possible to efficiently retrieve the feature amount group of the user information from the database. Then, by calculating the degree of similarity between all the feature amounts included in the extracted feature amount group and the feature amount of the user information sensed for authentication, the feature amount of the user information for authentication and the nearest vicinity are calculated. The feature amount can be obtained.
  • the user In order for the user to use such an authentication service, the user needs to transmit the user's own information (that is, user information) or the feature amount obtained from the information to the server.
  • user information such as a face image is privacy information itself, it must be protected.
  • an attack that estimates the original user information from the feature amount of the user information is known, not only the user information but also the information related to the user information such as the feature amount must be protected.
  • Non-Patent Document 4 Takashi Nishide, one outside person "Multiparty computation for interval, equality, and comparison without bitdecomposition protocol.” (Https: // www A method of performing authentication processing using .iacr.org/archive/pkc2007/44500343/44500343.pdf)) is being considered.
  • Confidential calculation is a technology that can conceal the calculation process and the result from the entity that stores the data.
  • data can be stored in a server managed by a third party such as a cloud server, and all operations can be executed on the stored data. Since the input data, the calculation process, and the calculation result are not known to a third party, it is possible to outsource the analysis process for sensitive information such as personal information.
  • Non-Patent Document 1 As a method of authenticating the user while keeping the input data secret, for example, in Non-Patent Document 1, the LSH value derived by the user terminal device and the feature amount of the user information are encrypted and transmitted to the server. , Discloses a technology for authenticating a user while keeping the user information and information related to the user information secret. However, since this method cannot completely conceal the user information and the information related to the user information, the user information may be inferred.
  • Non-Patent Document 2 calculates the LSH value while keeping the input data (for example, the feature amount of the user information and the LSH parameter) secret. It discloses a technique that is performed multiple times and uses the inner product of the obtained vector and the random number vector as an index of a hash table. However, this method is not practical because the amount of calculation is enormous.
  • the present inventors have used LSH and the secret sharing method, and further, by processing the LSH value obtained by the calculation of LSH with a one-way function while keeping it secret, the user.
  • LSH the secret sharing method
  • the confidentiality of the user information and the information related to the user information can be improved, and the processing speed can be improved.
  • the secret authentication method is a secret authentication method that performs authentication processing while keeping the input secret, is a feature amount distributed by the secret sharing method, and is a feature amount of user information about a user.
  • Decentralized feature amount and encrypted LSH parameter which is an encrypted parameter of LSH (Locality Sensitive Hashing) are used as inputs, and encryption is performed using a secret LSH that executes the LSH process while keeping the input secret.
  • a decentralized LSH value which is a decentralized and decentralized LSH value, is derived, and the derivated LSH value and the derivated LSH value are the keys for executing the processing of the unidirectional function, and are encrypted and.
  • the decentralized hash value is derived, and the derived decentralized hash value is decoded into a hash value that is de-distributed by the secret sharing method, and the hash value as an index and the decentralized feature amount as a data string are decoded.
  • a secret hash table which is a table in which a plurality of pairs of and are stored in advance, a pair including a hash value that matches the decrypted hash value is selected from the plurality of pairs, and the selected pair is selected.
  • the degree of similarity between the decentralized feature amount contained in the first decentralized feature amount and the first decentralized feature amount is calculated while being concealed, and the authentication result of the user is derived and derived while concealing the authentication result of the user based on the calculated similarity.
  • the authentication result is output.
  • the secret authentication method information other than the hash value is distributed by the secret sharing method, so that information that can estimate the original user information such as information related to the user information such as the LSH value and the feature amount can be obtained. It will not be published at all. Therefore, in the confidential authentication method, the confidentiality of the user information and the information related to the user information is improved. Further, since the secret hash table is referred to using the hash value, the authentication process can be performed at a low calculation cost. Therefore, according to the confidential authentication method, the confidentiality of the user information and the information related to the user information can be improved, and the processing speed can be improved.
  • the confidential authentication method has the highest degree of similarity to the first decentralized feature amount among the decentralized feature amounts included in the selected set in the derivation of the authentication result of the user.
  • a high decentralized feature amount is extracted as a second decentralized feature amount, and it is determined whether or not the degree of similarity between the extracted second decentralized feature amount and the first decentralized feature amount is higher than the threshold value.
  • a decentralized numerical value indicating that the user's authentication is successful is output as the authentication result, and it is determined that the similarity is equal to or less than the threshold. In this case, a decentralized numerical value indicating that the user's authentication has failed may be output as the authentication result.
  • the decentralized feature amount having the highest degree of similarity with the first decentralized feature amount which is the feature amount of the user information for authentication, can be extracted, so that the calculation amount is reduced.
  • the confidential authentication method since it is determined whether or not the user is the user based on the threshold value, even if an error occurs in the feature amount due to, for example, sensing conditions, the feature amount of the user himself / herself registered in advance is used. It can be determined that they are the same.
  • the feature amount is possessed by the physical feature amount related to the physical feature of the user, the behavioral feature amount related to the behavioral feature of the user, and the user. It is one of the possession features related to the features of the possession, and the physical features are retinal images, iris images, fingerprint images, vein images, audio information, ear shape information, DNA (deoxyribonucleic acid) information, and ,
  • the feature amount of information of at least one of the palm images, the behavioral feature includes the feature amount of at least one of the handwriting, the keystroke, the gait, and the action history, and the possession.
  • the feature amount may include the feature amount of the document information, the memory, and the information of at least one of the possessions held by the user.
  • the feature amount used for authentication can be appropriately selected according to the design.
  • the first decentralized feature amount and the decentralized feature amount each include a plurality of types of dispersed feature amounts, and the decentralized features included in the selected set.
  • the similarity degree of each of the plurality of types of feature amounts may be calculated.
  • the decentralized hash value may have randomness.
  • the data string may further include a decentralized user ID which is a decentralized user ID.
  • the secret authentication method it is possible to confirm the user ID as well as the user authentication, so that the versatility is improved.
  • the confidential authentication method is at least the derived authentication result, the decentralized feature amount included in the selected data string of the set, and the user ID. One may be output.
  • the secret authentication method can use various information about the user when using the authentication result, so that it is possible to provide a more advanced service such as displaying the user ID together with the authentication result.
  • the user terminal of the user calculates the feature amount from the user information obtained by sensing, and the calculated feature amount is used as a cryptographic lower limb and a secret sharing method.
  • the first dispersive feature amount may be derived by dispersing by.
  • the user can obtain the feature amount of the user information by using the user terminal device, so that it is not necessary to transmit the user information which is the privacy information itself such as the face image to the outside. Therefore, according to the secret authentication method, the security of user information is improved.
  • the user terminal device of the user transmits the user information obtained by sensing to a reliable server where the information is not leaked, and the server uses the user information as the feature.
  • the first decentralized feature quantity may be derived by deriving the quantity and dispersing the feature quantity by the secret sharing method.
  • the processing performed by the user terminal device can be reduced, so that the resources required for the user terminal device can be reduced.
  • the first decentralized feature quantity is derived by an arithmetic unit that derives the authentication result of the user, and the user terminal device of the user is the user obtained by sensing.
  • the decentralized user information in which the information is distributed by the secret sharing method may be transmitted to the arithmetic unit, and the arithmetic unit may derive the first decentralized feature amount from the decentralized user information.
  • the decentralized LSH parameter is transmitted to an arithmetic unit that derives the authentication result of the user, and the arithmetic unit uses the first decentralized feature amount and the decentralized feature amount.
  • the distributed LSH value may be derived by using the secret LSH with the LSH parameter as an input.
  • the LSH may be SimHash.
  • the LSH may be MinHash.
  • the one-way function may be AES (Advanced Encryption Standard).
  • the one-way function may be SHA (Secure Hash Algorithm) or MD5 (Message Digist 5).
  • the one-way function may be ElGamal encryption, RSA (Rivest-Shamir-Adleman) encryption, or elliptic curve cryptography.
  • the secret authentication system is a secret authentication system that performs authentication processing while keeping the input secret, is a feature amount distributed by the secret sharing method, and is a feature amount of user information about a user.
  • the decentralized feature amount and the encrypted LSH parameter, which is an encrypted parameter of the LSH, are used as inputs, and the secret LSH that executes the LSH process while keeping the input secret is used to encrypt and To execute the processing of the decentralized LSH value derivation unit for deriving the decentralized LSH value, which is the distributed LSH value, the decentralized LSH value derived by the decentralized LSH value derivation unit, and the unidirectional function.
  • the key is encrypted, and the distributed key, which is a distributed key, is used as an input, and the input is encrypted using a secret unidirectional function that executes the processing of the unidirectional function while keeping it secret.
  • the decentralized hash value derivation unit that derives the decentralized hash value, which is the distributed hash value, and the decentralized hash value derived by the decentralized hash value derivation unit are released from the distribution by the secret distribution method.
  • a secret hash table storage unit that stores a secret hash table that is a table in which a plurality of sets of a decryption unit that decodes to the hash value obtained, a hash value as an index, and a decentralized feature amount as a data string are stored in advance.
  • a set including a hash value matching the decoded hash value is selected from the plurality of sets, and the decentralized feature amount included in the selected set and the said A decentralized authentication result derivation unit that calculates while concealing the similarity with the first decentralized feature amount and derives the user's authentication result while concealing it based on the calculated similarity, and the decentralized authentication result. It includes an output unit that outputs the authentication result derived by the derivation unit.
  • the secret authentication system information other than the hash value is distributed by the secret sharing method, so that information that can estimate the original user information such as information related to the user information such as the LSH value and the feature amount can be obtained. It will not be published at all. Therefore, in the confidential authentication system, the confidentiality of the user information and the information related to the user information is improved. Further, since the secret hash table is referred to using the hash value, the authentication process can be performed at a low calculation cost. Therefore, according to the confidential authentication system, the confidentiality of the user information and the information related to the user information can be improved, and the processing speed can be improved.
  • the confidential authentication system is a system for performing user authentication processing while keeping user information confidential. More specifically, the confidential authentication system uses LSH (Locality Sensitive Hashing), which is one of the approximate nearest neighbor search methods, while keeping the user information confidential, and a plurality of user information registered in advance in the hash table. This is a system for extracting user information having the same hash value as the user information to be authenticated and performing user authentication processing based on the degree of similarity between the extracted user information and the user information to be authenticated.
  • LSH Location Sensitive Hashing
  • concealment or concealment means that it is distributed by the secret sharing method, and is also hereinafter also referred to as decentralization or decentralization.
  • encryption or encryption means that it is encrypted by some encryption technology other than the secret sharing method.
  • the encryption technique used is not particularly limited.
  • FIG. 1 is a diagram showing an example of the overall configuration of the confidential authentication system according to the present embodiment.
  • the confidential authentication system 500 includes, for example, a user terminal device 100, a data providing device 200, three data calculation devices 300, 310, 320, and an authentication result utilization device 400.
  • the communication between the devices may be any of a wired Internet line, wireless communication, dedicated communication, and the like.
  • the user terminal device 100 is a terminal device owned by the user to be authenticated.
  • the data providing device 200 is a device owned by a company or an organization that provides a confidential authentication service.
  • the data calculation devices 300, 310, and 320 acquire the feature amount of the user information transmitted from the user terminal device 100 and the information such as parameters required for the calculation transmitted from the data providing device 200, and the acquired information. It is a device that performs arithmetic processing to derive the authentication result while keeping the information secret.
  • the data arithmetic units 300, 310, and 320 are, respectively, one cloud server or a device included in one cloud server.
  • the authentication result utilization device 400 is a device owned by a company or an organization that uses the authentication result of the user.
  • the authentication result utilization device 400 is installed, for example, at a reception desk of a facility used by a user.
  • the data providing device 200 uses the LSH parameter, the key required to calculate the one-way function, and the user authentication process (more specifically, the authentication result derivation process).
  • the threshold to be used is transmitted to three cloud servers, that is, data calculation devices 300, 310, and 320.
  • the data providing device 200 conceals the above key and transmits it to the data computing devices 300, 310, and 320.
  • the above LSH parameters and thresholds are distributed and transmitted by the secret sharing method.
  • the user terminal device 100 conceals the feature amount of the user information and is three cloud servers, the data calculation devices 300, 310, 320. It is sent to (hereinafter, also referred to as three cloud servers).
  • the three cloud servers derive the authentication result while keeping the data secret while each cloud server uses the data obtained by the other cloud server. Then, each of the three cloud servers transmits the obtained authentication result to the authentication result utilization device 400 while keeping it secret.
  • the user terminal device 100 may be one or more, the data providing device 200 may be one or more, and the authentication result utilization device 400 may be one or more.
  • the confidential authentication system 500 includes three data arithmetic units, but at least two data arithmetic units may be provided.
  • the secret sharing method used in the present embodiment the data before the distributed data is decentralized by the secret sharing method and distributed by the secret sharing method (that is, the original data). At least two of the distributed data are required to be decrypted. That is, in the secret sharing method, the original data cannot be decoded from one distributed data. Therefore, if the secret authentication system 500 is provided with at least two data arithmetic units, the decentralization by the secret sharing method can be released.
  • the processing performed by each data calculation device is also performed while keeping the data concealed.
  • the authentication result derived from is also in a state of being concealed by the secret sharing method. Therefore, in order to obtain the decrypted authentication result, two or more secret authentication results are required.
  • the communication between the devices constituting the confidential authentication system 500 does not have to be real-time communication.
  • the user terminal device 100 may collect the sensed user information or the request command for the confidential authentication process to some extent and transmit it to the three data calculation devices 300, 310, and 320 at one time.
  • FIG. 2 is a diagram showing an example of the configuration of the user terminal device 100 according to the present embodiment.
  • the user terminal device 100 includes, for example, a sensing unit 101, a feature amount calculation unit 102, a feature amount distribution unit 103, and a communication unit 104.
  • the user terminal device 100 is, for example, a terminal device owned by a user to be authenticated.
  • the user terminal device 100 is implemented in, for example, a computer or a mobile terminal including a processor (microprocessor), a memory, a sensor, a communication interface, and the like.
  • the user terminal device 100 senses user information about a user, calculates a feature amount of the sensed user information, distributes the calculated feature amount by a secret sharing method, and distributes the feature amount (so-called distribution).
  • (Characteristic feature amount) is transmitted to the data calculation devices 300, 310, 320.
  • the sensing unit 101 senses the user information
  • the feature amount calculation unit 102 calculates the feature amount of the sensed user information
  • the feature amount distribution unit 103 distributes the calculated feature amount by the secret sharing method.
  • the communication unit 104 transmits the distributed features to the data calculation devices 300, 310, and 320.
  • the user terminal device 100 requests the data calculation devices 300, 310, 320 for the authentication result corresponding to the calculated feature amount, obtains the concealed authentication result from the data calculation devices 300, 310, 320, and conceals the data calculation device 300, 310, 320. It may be used for the service in the authentication system 500. At this time, the user terminal device 100 decodes and uses the acquired authentication result.
  • the sensing unit 101 includes one or more measuring devices that are sensors for sensing information necessary for authenticating a user.
  • the information required to authenticate the user is, in other words, information for identifying the user from other users, for example, information regarding the characteristics of the user itself or the characteristics of the user's behavior (hereinafter, also referred to as user information). ).
  • the information sensed by the sensing unit 101 is used to authenticate the user.
  • the information about the characteristics of the user itself is the information about the physical characteristics of the user.
  • Information on the physical characteristics of the user is, for example, information on a part of the body such as the face, ears, or palm, or information on the body such as veins, voice prints, fingerprints, retina, iris, or DNA (deoxyribonucleic acid). It may be information about elements similar to the department. These pieces of information are image data, audio data, or character string data such as numerical values.
  • the information regarding the physical characteristics of the user is a face image, a retinal image, an iris image, a fingerprint image, a vein image, a voice information, an ear shape information, a DNA information, an image of a palm, or the like.
  • the information sensed by the sensing unit 101 may be information related to the characteristics of the user's behavior (hereinafter referred to as behavioral characteristics).
  • the information on the behavioral characteristics of the user is information on the user's habits such as handwriting, keystrokes, or gait, or information on the behavior history.
  • the information related to the action history is, for example, location information obtained by GPS (Global Positioning System), log information showing the history of the user operating an electric device or a moving object such as a vehicle, or purchase history of a product or the like by the user. It may be information or the like.
  • the log information is, for example, various information acquired or measured in connection with steering operation, accelerator operation, brake operation, transmission gear operation, etc. when the user operates the vehicle.
  • the displacement amount of the movement of the vehicle. , Speed, acceleration, etc. may be information associated with the operation time.
  • the information sensed by the sensing unit 101 may be, for example, privacy data, which is a personal matter that the user does not want others to know.
  • privacy data may be document information, memory, or information about possessions held by the user.
  • the feature amount calculation unit 102 calculates the feature amount from the user information (hereinafter, also referred to as user information) acquired by the sensing unit 101.
  • the feature amount calculated by the feature amount calculation unit 102 can be represented by a vector including a plurality of components.
  • the feature amount is, for example, a feature amount calculated from information on the physical characteristics of the user (hereinafter, also referred to as a physical feature amount), and a feature amount calculated from information on the behavioral characteristics of the user (hereinafter, behavioral feature amount). (Also also referred to as) or a feature amount calculated from information on the characteristics of the possession held by the user (hereinafter, also referred to as a possession feature amount).
  • the physical feature amount includes the feature amount of at least one of retinal image, iris image, fingerprint image, vein image, audio information, ear shape information, DNA information, and palm image.
  • the behavioral feature amount includes the feature amount of at least one of the handwriting, the keystroke, the gait, and the action history, and the possession feature amount is the document information held by the user. Includes features of memory and information of at least one of possessions.
  • the feature amount is, for example, the main component of the characteristic parameter in the face image when the user information is the face image of the user.
  • the feature amount may be represented by, for example, a vector including characteristic parameters related to the position, area, width, and the like of a certain area of the user's face image.
  • the feature amount is a component of the tendency of the element corresponding to the time axis (for example, the coefficient of each term when expressed by a polynomial) from the history information. It may be represented by a vector containing as.
  • the feature amount itself extracted from the user information acquired by the sensing unit 101 can also be privacy data.
  • the feature quantity is a vector having d elements for any d (here, d is a natural number), and is data such as ⁇ 1, 2, 3, 4, 5 ⁇ .
  • the feature amount distribution unit 103 disperses and conceals the feature amount calculated by the feature amount calculation unit 102 by a predetermined method.
  • Non-Patent Document 5 Adi Shamir, "How to Share a Secret” (http://cs.jhu.edu/ ⁇ sdoshi/crypto/papers/shamirturing.pdf)
  • a distributed feature amount (hereinafter, also referred to as a distributed feature amount) is created.
  • the secret sharing method is a technology that generates multiple distributed information from confidential information.
  • the distributed information is created so that the confidential information can be restored from a predetermined combination, but the confidential information cannot be restored from other combinations.
  • Various structures can be taken in the predetermined combination, and the structure is called an access structure.
  • the threshold type access structure is represented by two parameters, the number n of distributed information generated and the threshold t (t ⁇ n). Confidential information can be restored from t or more distributed information, but confidential information cannot be restored from less than t distributed information.
  • the secret sharing method having a threshold type access structure includes, for example, the above-mentioned Shamir (2, 3) threshold secret sharing method, which is a distribution process for generating three distributed information by inputting secret information and two. It includes a restoration process for restoring confidential information from the above distributed information.
  • FIG. 14 is a diagram showing an example of the decentralized feature amount in the present embodiment.
  • the communication unit 104 communicates with a plurality of (for example, three) data arithmetic units 300, 310, 320.
  • the communication unit 104 transmits the distributed feature amount (so-called distributed feature amount) created by the feature amount distribution unit 103 to the data arithmetic units 300, 310, and 320, respectively.
  • a plurality of (for example, three) data arithmetic units 300, 310, 320 use these decentralized features in a concealed state for pre-registration processing and pre-registration processing. Execute the authentication process. Details will be described later.
  • the data providing device 200 is a device owned by a company or an organization that provides a confidential authentication service.
  • the data providing device 200 is a device for providing, for example, an LSH parameter, a threshold value used for user authentication processing, and a key necessary for calculating a one-way function to the data calculation devices 300, 310, and 320. Is.
  • FIG. 3 is a diagram showing an example of the configuration of the data providing device 200 according to the present embodiment.
  • the data providing device 200 includes, for example, an LSH parameter generation unit 201, a key generation unit 202, a key distribution unit 203, a threshold value setting unit 204, and a communication unit 205.
  • the data providing device 200 creates LSH parameters for accurately authenticating the user, distributes the created LSH parameters by the secret sharing method, and transmits the created LSH parameters to the three data calculation devices 300, 310, and 320.
  • the LSH parameter is set so that the same LSH value is derived from the feature amount of the same person's face image using, for example, LSH.
  • the data providing device 200 generates a key for executing the processing of the one-way function so that the user information is not leaked, and the generated key is distributed by the secret sharing method to obtain a distributed encryption key (a distributed encryption key ().
  • a distributed key a distributed encryption key ().
  • a distributed key is transmitted to the three data calculation devices 300, 310, and 320, respectively.
  • the LSH parameter generation unit 201 generates LSH parameters necessary for performing authentication using LSH and transmits them to the communication unit 205.
  • FIG. 11 is a diagram showing an example of LSH parameters in the present embodiment.
  • FIG. 12 shows an example of an LSH value calculation formula using SimHash and an LSH value in the present embodiment.
  • the LSH value of the feature quantity is calculated as the inner product with any n vectors, and the inner product value of each is 0 or more. Check if there is. If the inner product value is 0 or more, it is set to 1, and if it is less than 0, it is set to 0, so that m ⁇ 0, 1 ⁇ , that is, m-bit values can be obtained. Let this m-bit value be the LSH value.
  • the LSH parameter shown in FIG. 11 is a vector in LSH using SimHash when m is 3.
  • the key generation unit 202 generates a key used to execute the processing of the one-way function.
  • AES Advanced Encryption Standard
  • Non-Patent Document 6 Joan Daemen, Vincent Rijmen, "AES Proposal: Rijndael” (https://csrc.nist.gov/csrc/media/projects/cryptographic- When using standards-and-guidelines / documents / aes-development / rijndael-ammended.pdf)
  • the key generator 202 uses a 128-bit, 192-bit or 256-bit value as the encryption key in order to safely satisfy one-way. Generate.
  • the key distribution unit 203 distributes the encryption key created by the key generation unit 202 by the secret sharing method and transmits it to the communication unit 205.
  • the threshold value setting unit 204 sets a threshold value to be used for the user authentication process, distributes the set threshold value by the secret sharing method, and transmits the set threshold value to the communication unit 205.
  • the data calculation devices 300, 310, and 320 perform user authentication processing, the most similarity between the feature amount of user information (first decentralized feature amount) and the decentralized feature amount registered in advance in the server. If the degree of similarity with the distributed feature amount is greater than or equal to the threshold set by the threshold setting unit 204, it is determined that the user is a pre-registered user, the user is authenticated, and the similarity is equal to or less than the threshold. For example, it is determined that the user is not a pre-registered user, and the user is denied.
  • the communication unit 205 communicates with the data arithmetic units 300, 310, 320.
  • the communication unit 205 has a plurality of decentralized LSH parameters created by the LSH parameter generation unit 201, a decentralized key created by the key distribution unit 203, and a plurality of decentralized threshold values set by the threshold value setting unit 204 (here, 3).
  • the data is transmitted to the data arithmetic units 300, 310, and 320 of (1).
  • the data arithmetic units 300, 310, and 320 are, for example, cloud servers. In the confidential authentication system 500, two or more data arithmetic units 300 may be provided.
  • the three data arithmetic units 300, 310, and 320 communicate with each other to perform the authentication process while keeping the input secret, and transmit the authentication result to the authentication result utilization device 400.
  • the data calculation devices 300, 310, and 320 input the first decentralized feature amount, which is a feature amount of user information, and the decentralized LSH parameter, which is a decentralized LSH parameter, as inputs.
  • the decentralized LSH value is calculated using the concealed LSH that executes the LSH process while concealing.
  • the data calculation devices 300, 310, and 320 use a concealed one-way function that takes the decentralized LSH value and the decentralized key as inputs and executes the processing of the unidirectional function while keeping the input concealed, and uses the decentralized hash value. Is calculated, and the decentralized hash value is decoded into a hash value that has been de-distributed by the secret sharing method.
  • the data arithmetic units 300, 310, and 320 refer to the secret hash table stored in the secret hash table storage unit 306 using the obtained hash value as an index.
  • the secret hash table a plurality of sets of a hash value as an index and a distributed feature amount as a data string are stored in advance.
  • the obtained hash value is used as an index, and the decentralized feature amount transmitted from the user terminal device 100 to the data string of the secret hash table. To store.
  • the data calculation device 300, 310, 320 when the data calculation device 300, 310, 320 performs the user authentication process, the data calculation device 300, 310, 320 selects a set including a hash value that matches the decrypted hash value among the plurality of sets stored in the secret hash table.
  • the degree of similarity between the decentralized feature amount included in the selected set and the decentralized feature amount of the user transmitted from the user terminal device 100 is calculated and calculated. Based on the degree of similarity, the user's authentication result is derived while keeping it secret.
  • the data arithmetic units 300, 310, and 320 extract the decentralized feature amount having the highest degree of similarity to the first decentralized feature amount as the second decentralized feature amount.
  • the data arithmetic units 300, 310, and 320 determine whether or not the similarity between the extracted second decentralized feature amount and the first decentralized feature amount is higher than the threshold value, and the similarity is higher than the threshold value. For example, it authenticates that the user is the pre-registered user, and rejects that the user is not the pre-registered user if the similarity is below the threshold value.
  • FIG. 4 is a diagram showing an example of the configuration of the data arithmetic unit 300.
  • the data calculation device 300 includes a distributed key storage unit 301, an LSH parameter storage unit 302, a decentralized LSH value derivation unit 303, a threshold storage unit 304, a decentralized hash value derivation unit 305, and a secret hash table storage unit 306.
  • a decentralized authentication result derivation unit 307, a communication unit 308, and a decentralized hash value decoding unit 309 are provided.
  • the data arithmetic units 310 and 320 have the same configuration as the data arithmetic unit 300.
  • the distributed key storage unit 301 receives and stores the distributed key distributed by the secret sharing method transmitted from the data providing device 200.
  • the LSH parameter storage unit 302 receives and stores the decentralized LSH parameters transmitted from the data providing device 200.
  • the decentralized LSH value derivation unit 303 uses the decentralized feature amount transmitted from the user terminal device 100 and the decentralized LSH parameter stored in the LSH parameter storage unit 302 without decoding the decentralized feature amount.
  • the LSH value of the decentralized feature amount that is, the decentralized LSH value is derived by using the secret LSH that executes the LSH process.
  • the decentralized LSH value derivation unit 303 transmits the derived decentralized LSH value to the decentralized hash value derivation unit 305.
  • SimHash As a calculation method of LSH, SimHash (Non-Patent Document 7: Moses S. Charikar, "Similarity Estimation Techniques from Rounding Algorithms.” (Https://www.cs.princeton.edu/courses/archive/spring04/cos598B/bib) /CharikarEstim.pdf)) or MinHash (Non-Patent Document 8: Ping Li, 1 person outside, "b-Bit Minwise Hashing" (https://arxiv.org/pdf/0910.3349.pdf)) Good.
  • SimHash n vectors having the same number of dimensions as the feature amount and random values are created as LSH parameters. The inner product of these n vectors and the feature amount is calculated, and it is determined whether or not the inner product value is 0 or more. The n ⁇ 0,1 ⁇ obtained by this are used as the LSH value.
  • the threshold value storage unit 304 receives and stores the threshold value used in the user authentication process transmitted from the data providing device 200.
  • the decentralized hash value derivation unit 305 uses the decentralized LSH value derived by the decentralized LSH value derivation unit 303 and the decentralized key stored in the decentralized key storage unit 301 in one direction while keeping the LSH value concealed. Derivate the decentralized hash value using a concealed one-way function that executes the processing of the sex function.
  • the decentralized hash value derivation unit 305 transmits the decentralized hash value derived to the decentralized hash value decoding unit 309. It is decrypted, the decrypted hash value is output, and it is transmitted to the secret hash table storage unit 306.
  • Non-Patent Document 9 Chao Ning, one outside person, "Constant-Rounds, Linear Multi-party Computation” For Exponentiation and Modulo Reduction with Perfect Security ”(https://eprint.iacr.org/2011/069.pdf), or AES, or public key cryptography such as ElGamal encryption, RSA encryption, or elliptic curve cryptography. You may.
  • SHA Secure Hash Algorithm
  • a power function Non-Patent Document 9: Chao Ning, one outside person, "Constant-Rounds, Linear Multi-party Computation” For Exponentiation and Modulo Reduction with Perfect Security ”(https://eprint.iacr.org/2011/069.pdf)
  • AES or public key cryptography such as ElGamal encryption, RSA encryption, or elliptic curve cryptography. You may.
  • y k ⁇ x modp is calculated when the distributed key is k, the distributed LSH value is x, and the output hash value is y.
  • p may have a value different from that of the secret sharing method, but the same value is more efficient.
  • the distributed key refers to the AES key distributed by the secret sharing method. If a method that does not require key input is used as a one-way function, the distributed key may be empty.
  • the decentralized hash value decoding unit 309 decodes the decentralized hash value derived by the decentralized hash value derivation unit 305 into a hash value decentralized by the secret sharing method, and stores the decoded hash value in a secret hash table. It is transmitted to the unit 306.
  • the secret hash table storage unit 306 stores the secret hash table.
  • the secret hash table is a table in which a set of a hash value using the hash value as an index and a distributed feature amount as a data string is stored in advance.
  • the secret hash table storage unit 306 refers to the secret hash table using the hash value decoded by the distributed hash value decoding unit 309, and the distribution transmitted from the user terminal device 100. Stores the feature quantity.
  • the secret hash table storage unit 306 may store the decentralized feature amount transmitted from the user terminal device 100 in the secret hash table in the data string indexed by the same hash value as the decrypted hash value.
  • the secret hash table storage unit 306 may store the decrypted hash value and the decentralized feature amount transmitted from the user terminal device 100 in the secret hash table as a set, that is, in association with each other. Good.
  • the secret hash table storage unit 306 refers to the secret hash table using the hash value decrypted by the decentralized hash value decoding unit 309 during the user authentication process, and indexes the same hash value as the decrypted hash value. All the decentralized feature quantities stored in the line are read out and transmitted to the decentralized authentication result derivation unit 307.
  • the secret hash table storage unit 306 selects and selects a set including a hash value that matches the hash value decoded by the distributed hash value decoding unit 309 from the secret hash table during the user authentication process.
  • the set may be transmitted to the decentralized authentication result derivation unit 307, or all the decentralized feature quantities included in the selected set may be transmitted to the decentralization authentication result derivation unit 307.
  • FIG. 13 is a diagram showing an example of a hash table
  • FIG. 15 is a diagram showing an example of a secret hash table according to the present embodiment. In this example, information on three users is pre-registered.
  • the hash table shown in FIG. 13 is a plaintext hash table, and the LSH value as an index and the feature amount as a data string are stored in association with each other.
  • the plaintext hash table is not preferable from the viewpoint of the security of the user information because the original user information can be derived from the LSH value. Therefore, as shown in FIG. 15, in the present embodiment, a decentralized hash value, which is a hash value of the decentralized LSH value, is derived using a concealed one-way function, and the derived decentralized hash value is decoded. By using the hash value obtained in this way as an index, the security is improved. Further, in the present embodiment, the hidden hash table stores the hash value as an index and the decentralized feature amount as a data string in association with each other.
  • the secret sharing method p is, for example, 65519.
  • the decentralized authentication result derivation unit 307 receives, for example, the decentralized feature amount transmitted from the secret hash table storage unit 306, and the decentralized feature amount received and the decentralized feature amount of the user to be authenticated (first decentralized feature amount).
  • the user's authentication result is derived based on the similarity with the quantity).
  • the decentralized authentication result derivation unit 307 is most similar to the first decentralized feature amount transmitted from the user terminal device 100 among the decentralized feature amounts included in the selected set in the derivation of the user authentication result.
  • a highly decentralized feature amount is extracted as a second decentralized feature amount, and it is determined whether or not the degree of similarity between the extracted second decentralized feature amount and the first decentralized feature amount is higher than the threshold value.
  • the decentralized authentication result derivation unit 307 may obtain the similarity in plain text, or the dispersion value of the similarity distributed by the secret sharing method (also referred to as decentralized similarity). ) May be obtained.
  • the decentralized authentication result derivation unit 307 authenticates the user if the calculated similarity is higher than the threshold value, and denies the user if it is lower than the threshold value.
  • the Euclidean similarity of the two features here, the first dispersed feature and the second dispersed feature
  • the squared Euclidean similarity may be used as the similarity, or the cosine similarity. May be the degree of similarity.
  • the authentication result may be a plaintext authentication result or a distributed value (also referred to as a decentralized authentication result) of the authentication result distributed by the secret sharing method.
  • the decentralized authentication result derivation unit 307 transmits the derived authentication result to the communication unit 308.
  • the transmitted authentication result is finally transmitted to the authentication result utilization device 400.
  • the authentication result may be transmitted to the user terminal device 100.
  • the communication unit 308 communicates with the user terminal device 100 and the data providing device 200.
  • the communication unit 308 receives the decentralized LSH parameter from the data providing device 200, the decentralized threshold used in the authentication process, and the key distributed by the secret sharing method, and stores the decentralized LSH parameter in the LSH parameter storage unit 302.
  • the decentralized threshold is transmitted to the threshold storage unit 304, and the decentralized key is transmitted to the decentralized key storage unit 301.
  • the communication unit 308 receives the feature amount distributed by the secret sharing method (so-called decentralized feature amount) from the user terminal device 100, and causes the decentralized LSH value derivation unit 303 and the decentralized authentication result derivation unit 307. Send.
  • the authentication result utilization device 400 is, for example, a terminal installed at a reception desk such as an event venue, and is mounted on a computer or a mobile terminal provided with a processor (microprocessor), a memory, a sensor, a communication interface, and the like. In the secret authentication system 500, one or more authentication result utilization devices 400 may be provided.
  • the authentication result utilization device 400 receives the distributed authentication results (also referred to as decentralized authentication results) from the three data arithmetic units 300, 310, and 320, releases the decentralization by the secret sharing method, and plaintext. Decrypt to the authentication result of.
  • the decentralized authentication result may be used, for example, to present information on the authentication result to the receptionist or the user, or to unlock the entrance / exit gate to the event venue.
  • FIG. 5 is a diagram showing an example of the configuration of the authentication result utilization device 400.
  • the authentication result utilization device 400 includes a decentralized authentication result decoding unit 401, an authentication result utilization unit 402, and a communication unit 403.
  • the decentralized authentication result decoding unit 401 decodes the decentralized authentication result transmitted from the data arithmetic units 300, 310, 320. For example, the decentralized authentication result decoding unit 401 may release the decentralization of the decentralized authentication result by the secret sharing method and decrypt the decentralized authentication result into the authentication result. The decentralized authentication result decoding unit 401 transmits the decrypted authentication result to the authentication result utilization unit 402.
  • the authentication result utilization unit 402 uses the decentralized authentication result decrypted by the decentralized authentication result decoding unit 401.
  • the decentralized authentication result is used, for example, to present information about the authentication result to a receptionist or a user.
  • the authentication result utilization unit 402 may be implemented including, for example, a display, an audio output device, and other user interfaces.
  • the information regarding the authentication result may be, for example, information indicating that the user has been authenticated, such as "OK” or "authenticated” when the user is authenticated.
  • it may include user information about the user, such as the user's ID.
  • the information regarding the authentication result may be, for example, information indicating that the user has been denied, such as "NG” or "Not authenticated” when the user is denied.
  • the decentralized authentication result may be used, for example, to unlock the entrance / exit gate to the event venue.
  • the authentication result utilization device 400 may be connected to, for example, an entrance / exit gate to an event venue or the like.
  • the authentication result utilization unit 402 that receives the authentication result (so-called authentication result) decrypted by the decentralized authentication result decoding unit 401 controls operations such as opening the entrance / exit gate if the user is authenticated. You may.
  • the communication unit 403 communicates with the data arithmetic units 300, 310, and 320.
  • the communication unit 403 receives the authentication result (so-called decentralized authentication result) distributed by the secret sharing method from the data arithmetic units 300, 310, 320, and transmits the decentralized authentication result decoding unit 401.
  • the operation of the secret authentication system 500 is as follows: (1) The data providing device 200 sets the key distributed by the secret sharing method (so-called distributed key), the distributed LSH parameter, and the threshold used for the user authentication process as a data calculation device. Using the initialization phase to be transmitted to 300, 310, 320, (2) the registration phase in which the user registers the feature amount of his / her own information (that is, user information), and (3) the user information currently acquired by the user. Includes an authentication phase for performing authentication.
  • FIG. 6 is a sequence diagram showing an example of the operation of the initialization phase of the confidential authentication system 500 according to the present embodiment.
  • the data providing device 200 In the initialization phase, first, the data providing device 200 generates the LSH parameter in the LSH parameter generation unit 201, and sets the threshold value to be used for authentication in the threshold value setting unit 204 (S101).
  • the data providing device 200 transmits the LSH parameter and the threshold value to the data calculation devices 300, 310, and 320 (S102).
  • the data arithmetic units 300, 310, and 320 receive the LSH parameter and the threshold value transmitted from the data providing device 200, store the received LSH parameter in the LSH parameter storage unit 302, and store the threshold value in the threshold value storage unit 304.
  • the data providing device 200 generates a key to be used for processing the one-way function in the key generation unit 202 (S104).
  • the data providing device 200 distributes the key generated in the process of step S104 by the key distribution unit 203 by the secret sharing method (S105).
  • the data providing device 200 transmits the keys distributed in the process of step S105 (so-called distributed keys) to the data arithmetic units 300, 310, and 320 (S106).
  • the data arithmetic units 300, 310, and 320 receive the distributed key transmitted from the data providing device 200, and store the received distributed key in the distributed key storage unit 301 (S107).
  • the data providing device 200 generates the LSH parameter used in the processing of the LSH, sets the distribution key used in the processing of the one-way function, and performs data calculation on the LSH parameter and the distribution key. It transmits to devices 300, 310, 320.
  • the data arithmetic units 300, 310, and 320 receive the decentralized feature amount when the decentralized feature amount is transmitted from the user terminal device 100, and perform the user registration process (operation of the following registration phase).
  • User authentication processing (operation of the following authentication phase) can be performed.
  • FIG. 7 is a sequence diagram showing an example of the operation of the registration phase of the confidential authentication system 500 according to the present embodiment.
  • the user terminal device 100 senses user information in the sensing unit 101 (S201).
  • step S201 for example, when registering a face image for face authentication, the sensing unit 101 captures the user's face image.
  • the user terminal device 100 calculates the feature amount from the user information sensed in step S201 by the feature amount calculation unit 102 (S202).
  • the method for calculating the feature amount is determined in advance by the service provider and shared by all the user terminal devices 100.
  • the user terminal device 100 distributes the feature amount calculated in step S202 by the secret sharing method (S203) in the feature amount distribution unit 103, and disperses the distributed feature amount (so-called decentralized feature amount). It is transmitted to the data calculation devices 300, 310, and 320 (S204).
  • the data arithmetic units 300, 310, and 320 perform the user registration process when the decentralized feature amount is acquired from the user terminal device 100 (S205).
  • FIG. 8 is a sequence diagram showing an example of detailed processing in step S205 of FIG. 7.
  • the data arithmetic units 300, 310, and 320 derive the decentralized LSH value of the feature amount by the decentralized LSH value derivation unit 303 (S301). More specifically, the data calculation devices 300, 310, and 320 each input the decentralized feature amount acquired from the user terminal device 100 and the LSH parameter (distributed parameter) stored in the LSH parameter storage unit 302, respectively. , The decentralized LSH value derivation unit 303 derives the decentralized LSH value of the feature amount by using the concealed LSH that executes the LSH process while concealing the input. As a result, the data arithmetic units 300, 310, and 320 can derive the decentralized LSH value without releasing the decentralization of the obtained decentralized feature amount by the secret sharing method.
  • the data arithmetic units 300, 310, and 320 derive the decentralized hash value of the LSH value (S302). More specifically, the data calculation devices 300, 310, and 320 are input to the decentralized LSH value derived in step S301 and the decentralized key stored in the decentralized key storage unit 301, and are decentralized hash value derivation units.
  • the decentralized hash value of the LSH value is derived by using the secret one-way function that executes the processing of the one-way function while keeping the input secret.
  • the data arithmetic units 300, 310, and 320 can derive the decentralized hash value of the LSH value without releasing the decentralization of the decentralized LSH value by the secret sharing method.
  • the data arithmetic units 300, 310, and 320 decode the decentralized hash value (S303). More specifically, the data arithmetic units 300, 310, and 320 convert the decentralized hash value derived in step S302 into a hash value whose decentralization by the secret sharing method is released by the decentralized hash value decoding unit 309. Decrypt.
  • the data arithmetic units 300, 310, and 320 add the decentralized feature amount acquired from the user terminal device 100 to the secret hash table using the hash value obtained in step S303 as an index (S304).
  • the secret hash table is a table in which a set of a hash value as an index and a distributed feature amount as a data string is stored in advance.
  • the data calculation devices 300, 310, and 320 refer to the secret hash table using the hash value obtained in step S303 as an index in the secret hash table storage unit 306, for example, and display the user in the data column of the row indicated by the hash value.
  • the decentralized feature amount transmitted from the terminal device 100 is added.
  • the data calculation devices 300, 310, and 320 each derive the hash value of the LSH value of the decentralized feature amount transmitted from the user terminal device 100 without releasing the decentralization by the secret sharing method. Then, the user registration process is performed by adding the decentralized feature amount transmitted from the user terminal device 100 to the data column of the row indicated by the derived hash value (that is, the decentralized hash value).
  • FIG. 9 is a sequence diagram showing an example of the operation of the authentication phase of the confidential authentication system 500 according to the present embodiment.
  • the user terminal device 100 senses user information in the sensing unit 101 (S401).
  • step S401 for example, when a face image for face authentication is registered in step S201 of the registration phase, the sensing unit 101 takes a face image of the user.
  • the user terminal device 100 calculates the feature amount from the user information sensed in step S401 by the feature amount calculation unit 102 (S402).
  • the method of calculating the feature amount is determined in advance by the service provider and is shared by all the user terminal devices 100.
  • the user terminal device 100 distributes the feature amount calculated in step S402 by the secret sharing method (S403) in the feature amount distribution unit 103, and disperses the distributed feature amount (so-called decentralized feature amount). It is transmitted to the data calculation devices 300, 310, and 320 (S404).
  • the data arithmetic units 300, 310, and 320 acquire the decentralized feature amount (hereinafter, referred to as the first decentralized feature amount in the authentication phase) from the user terminal device 100, and perform the user authentication process (S405). .. The details of the user authentication process will be described later.
  • the data arithmetic units 300, 310, and 320 transmit the decentralized authentication result obtained in the user authentication process in step S405 to the authentication result utilization device 400 (S406).
  • the authentication result utilization device 400 decodes the decentralized authentication result acquired from the data arithmetic units 300, 310, 320 (S407). More specifically, when the authentication result utilization device 400 acquires the decentralized authentication result transmitted from the data calculation devices 300, 310, and 320, the decentralized authentication result decoding unit 401 uses a secret sharing method for the decentralized authentication result. Decentralize by and decrypt to the plain text authentication result.
  • the authentication result utilization device 400 uses the authentication result decrypted in step S407 in the authentication result utilization unit 402 (S408).
  • the authentication result utilization unit 402 may use the authentication result to present information on the authentication result to the receptionist or the user, or may use it to host an entrance / exit gate to the event venue. .. Not only the entrance / exit gate of the event venue, but also the door of a building or a room, for example.
  • FIG. 10 is a sequence diagram showing an example of detailed processing in step S405 of FIG.
  • the data arithmetic units 300, 310, and 320 derive the decentralized LSH value of the feature amount by the decentralized LSH value derivation unit 303 (S501). More specifically, the data calculation devices 300, 310, and 320 each have a decentralized feature amount acquired from the user terminal device 100 and an LSH parameter stored in the LSH parameter storage unit 302 (so-called decentralized LSH parameter). With the above as an input, the decentralized LSH value derivation unit 303 derives the decentralized LSH value of the feature amount by using the concealed LSH that executes the LSH process while keeping the input concealed. As a result, the data arithmetic units 300, 310, and 320 can derive the decentralized LSH value without releasing the decentralization of the obtained decentralized feature amount by the secret sharing method.
  • the data arithmetic units 300, 310, and 320 derive the decentralized hash value of the LSH value (S502). More specifically, the data calculation devices 300, 310, and 320 are input to the decentralized LSH value derived in step S501 and the decentralized key stored in the decentralized key storage unit 301, and are decentralized hash value derivation units.
  • the decentralized hash value of the LSH value is derived by using the secret one-way function that executes the processing of the one-way function while keeping the input secret.
  • the data arithmetic units 300, 310, and 320 can derive the decentralized hash value of the LSH value without releasing the decentralization of the decentralized LSH value by the secret sharing method.
  • the data arithmetic units 300, 310, and 320 decode the decentralized hash value (S503). More specifically, the data arithmetic units 300, 310, and 320 convert the decentralized hash value derived in step S502 into a hash value whose decentralization by the secret sharing method is released by the decentralized hash value decoding unit 309. Decrypt.
  • the data arithmetic units 300, 310, and 320 refer to the secret hash table using the hash value obtained in step S503 as an index in the decentralized authentication result derivation unit 307, and set the data column in the row indicated by the hash value.
  • the stored decentralized feature quantity group is taken out (S504).
  • the decentralized feature group is, for example, a list containing 0 or more decentralized features.
  • the secret hash table may be a table in which a plurality of sets of a hash value as an index and a distributed feature amount as a data string are stored in advance.
  • the data arithmetic units 300, 310, and 320 are the hash values decoded by the decentralized hash value decoding unit 309 of the plurality of sets using the concealed hash table in the decentralized authentication result derivation unit 307. You may choose a pair that contains a hash value that matches.
  • the data calculation devices 300, 310, and 320 are transmitted from the user terminal device 100 in step S404 and all the decentralized feature amounts included in the decentralized feature amount group fetched from the secret hash table in step S504.
  • the decentralized similarity (hereinafter referred to as “similarity”) with the decentralized feature amount for authentication (so-called first decentralized feature amount) is calculated (S505).
  • the decentralized authentication result derivation unit 307 determines the degree of similarity between the decentralized feature amount included in the set selected from the concealed hash table and the first decentralized feature amount. You may calculate it in secret.
  • the data arithmetic units 300, 310, and 320 derive the user authentication result based on the similarity calculated in step S505.
  • the data calculation devices 300, 310, and 320 have the most decentralized feature amount for authentication (that is, the first decentralized feature amount) in the decentralized feature amount group in the decentralized authentication result derivation unit 307.
  • a dispersed feature with a high degree of similarity is extracted as a second dispersed feature, and it is determined whether or not the similarity between the extracted second dispersed feature and the first dispersed feature is higher than the threshold value.
  • the authentication result is derived (S506).
  • step S506 for example, when the decentralized authentication result derivation unit 307 determines that the similarity is higher than the threshold value in the data arithmetic units 300, 310, 320, it is a numerical value indicating that the user authentication is successful.
  • the variance value is output as the authentication result, and when it is determined that the similarity is less than or equal to the threshold value, the variance value of a numerical value indicating that the user's authentication has failed (that is, the user has been denied) is output as the authentication result. ..
  • the numerical value indicating that the user authentication was successful and the numerical value indicating that the user authentication was unsuccessful are different numerical values, and may be any numerical value as long as it is determined by the system.
  • the numerical value indicating that the user has been successfully authenticated may be 1, and the numerical value indicating that the user has been denied may be 0.
  • the data calculation devices 300, 310, and 320 use the secret LSH and the secret one-way function to send the user information for authentication by the user and the secret hash table by the user in advance. Authentication processing is performed while keeping the registered user information confidential.
  • the data calculation devices 300, 310, and 320 extract the decentralized feature amount having the highest degree of similarity to the decentralized feature amount for authentication (so-called first decentralized feature amount) as the second decentralized feature amount. By doing so, it is possible to efficiently search for user information having the highest degree of similarity to the user information to be authenticated.
  • the data arithmetic units 300, 310, and 320 determine whether or not the similarity between the extracted second decentralized feature amount and the first decentralized feature amount is higher than the threshold value, and determine whether or not the authentication is successful.
  • the distributed value of the numerical value indicating the above is output as the authentication result.
  • the confidential authentication system 500 may be a system having at least the following configurations.
  • the confidential authentication system 500 includes, for example, a decentralized LSH value derivation unit 303 (see FIG. 4), a decentralized hash value derivation unit 305 (see FIG. 4), a decentralized hash value decoding unit 309 (see FIG. 4), and the like. It is preferable to include a secret hash table storage unit 306 (see FIG. 4), a decentralized authentication result derivation unit 307 (see FIG. 4), and an output unit (corresponding to the communication unit 308 in FIG. 4). Since each part has been described above, the description thereof will be omitted here.
  • the confidential authentication method may be a method including at least the following processing flow.
  • FIG. 16 is a flowchart showing an example of the confidential authentication method according to the present embodiment.
  • the secret authentication method executed by the secret authentication system 500 is, for example, a feature amount that is encrypted and distributed by the secret sharing method, and is a feature amount of user information about a user. Encrypted and distributed using a secret LSH that executes LSH processing while keeping the input secret, using the first decentralized feature amount and the encrypted LSH parameter, which is an encrypted parameter of the LSH, as inputs.
  • the decentralized LSH value which is the obtained LSH value, is derived (S601), and the derived decentralized LSH value and the key for executing the processing of the unidirectional function are encrypted and distributed.
  • a decentralized hash value that is an encrypted and distributed hash value using a concealed unidirectional function that executes the processing of the unidirectional function while keeping the input concealed with the decentralized key that is the key as input.
  • the derived decentralized hash value is decoded into a hash value that is de-distributed by the secret sharing method (S603), and the hash value as an index and the decentralized feature amount as a data string
  • a secret hash table which is a table in which a plurality of sets of the above are stored in advance
  • a set containing a hash value that matches the decrypted hash value is selected from the plurality of sets (S604), and the selected set is selected.
  • the similarity between the included decentralized feature amount and the first decentralized feature amount is calculated while concealing (S605), and the user authentication result is derived while concealing based on the calculated similarity (S606).
  • the derived authentication result is output (S607).
  • the user is authenticated by using, for example, the feature amount of the face image as the feature amount of the user information, but the retinal image, the iris image, the fingerprint image, the vein image, the voice information, and the ear.
  • Shape information, DNA information, or features of the user's physical features such as an image of the palm, features of the user's behavioral features such as handwriting, keystrokes, steps, or behavior history, or owned by the user.
  • the feature amount related to the characteristics of the user's property such as the document information, the user's memory, or the thing (property) possessed by the user may be used for the user authentication.
  • the user is authenticated using only a single feature amount (for example, the first decentralized feature amount).
  • a single feature amount for example, the first decentralized feature amount.
  • a plurality of types of feature amounts shown in (1) above are used. May be combined to authenticate the user.
  • the user may be authenticated using the fingerprint image and the iris image. In this case, even if the authentication of the user using the fingerprint image is successful, if the authentication of the user using the iris image fails, the user is denied.
  • the user terminal device 100 calculates the feature amount from the user information, but the data calculation devices 300, 310, and 320 calculate the feature amount from the user information. You may.
  • the data arithmetic units 300, 310, and 320 calculate the decentralized feature amount from the decentralized user information.
  • the user terminal device 100 transmits the decentralized user information in which the user information is distributed to the data calculation devices 300, 310, and 320.
  • the data calculation devices 300, 310, and 320 acquire the decentralized user information, they calculate the feature amount while keeping the user information secret, that is, calculate the decentralized feature amount from the decentralized user information.
  • the user terminal device 100 transmits the decentralized feature amount to the data calculation devices 300, 310, 320, but the data calculation devices 300, 310, 320 are the user terminals.
  • the decentralized feature amount may be calculated from the decentralized user information transmitted from the device 100.
  • any calculation method may be used as long as the feature quantity calculation method is the same.
  • the user terminal device 100 calculates the feature amount from the user information.
  • a feature amount calculation device for calculating the feature amount is prepared and the feature amount is calculated.
  • the feature amount of the user information may be calculated by the calculation device.
  • the user terminal device 100 may transmit the decentralized user information in which the user information is distributed to the feature amount calculation device, and the feature amount calculation device may calculate the feature amount while keeping the user information secret. Further, the user terminal device 100 may transmit the user information to the feature amount calculation device, and the feature amount calculation device may calculate the feature amount from the user information.
  • the feature amount calculation device When transmitting encrypted user information to the feature amount calculation device, it is required that the feature amount calculation device is a reliable device and that the user information is not leaked from the feature amount calculation device.
  • the data string of the secret hash table contains only the decentralized feature amount, but may further include decentralized user information such as the decentralized user ID.
  • the user information stored in the secret hash table is not limited to this, and any data may be used as long as the data column of the secret hash table includes the distributed feature amount.
  • the data arithmetic units 300, 310, and 320 may output the user information stored in the secret hash table in addition to the numerical value indicating whether or not the authentication is successful as the authentication result.
  • the decentralized features having the highest degree of similarity to the decentralized feature amount for authentication (first decentralized feature amount).
  • the variance value of the numerical value indicating whether or not the authentication was successful is output as the authentication result by comparing the similarity with the quantity (second decentralized feature quantity) and the threshold value, but it is selected from the concealed hash table.
  • the decentralized feature amount and the decentralized user information such as the corresponding decentralized user ID may be output to the authentication result utilization device 400.
  • the user information to be authenticated and the data calculation are performed by the authentication result utilization device 400 that has received the decentralized feature amount, the decentralized user ID, or other decentralized user information from the data calculation devices 300, 310, and 320.
  • the user may be authenticated by comparing the user information transmitted from the devices 300, 310, and 320.
  • the data calculation devices 300, 310, and 320 transmit the decentralized authentication result to the authentication result utilization device 400, but the data calculation devices 300, 310, and 320 authenticate the decentralized authentication result. After decoding the result, the authentication result may be transmitted to the authentication result utilization device 400. As a result, the authentication result utilization device 400 does not need to decrypt the decentralized authentication result into the plaintext authentication result, so that the received authentication result can be used as it is.
  • the data calculation devices 300, 310, and 320 transmit the decentralized authentication result to the authentication result utilization device 400, but the decentralized authentication result may be transmitted to the user terminal device 100.
  • the user terminal device 100 includes, for example, a decentralized authentication result decoding unit 401 and an authentication result utilization unit 402, and the acquired decentralized authentication result may be decoded and used.
  • the data calculation devices 300, 310, and 320 transmit the decentralized authentication result to the authentication result utilization device 400, but are decentralized to both the authentication result utilization device 400 and the user terminal device 100.
  • the authentication result may be sent.
  • any function can be used as long as the input cannot be obtained from the output.
  • a power function a cryptographic hash function such as SHA or MD5, etc.
  • SHA or MD5 a cryptographic hash function
  • AES is used as the one-way function, but public key cryptography such as ElGamal encryption, RSA encryption, and elliptic curve cryptography may be used.
  • public key cryptography such as ElGamal encryption, RSA encryption, and elliptic curve cryptography may be used.
  • public key cryptography one-wayness can be strengthened compared to AES by deleting the public key after creating the key pair.
  • the AES encryption key is mentioned as an example of the key used in the one-way function, but in order to calculate the one-way function, a plurality of data other than the input data are required. In that case, they may be collectively used as a key. Further, when the key represents a plurality of information, the key distribution unit 203 of the data providing device 200 does not need to distribute all the information, and the range in which the information related to the input cannot be obtained from the output of the one-way function. Then, a part of the information may be transmitted in plain text to the data arithmetic units 300, 310, 320.
  • each data is concealed by using the secret sharing method, but homomorphic encryption (Non-Patent Document 10: Pascal Paillier, “Public-Key Cryptosystems Based on Composite Degree Reduosity Classes” (https) //rd.springer.com/chapter/10.1007%2F3-540-48910-X_16)), fully homomorphic encryption (Non-patent Document 11: Jung Hee Cheon, 3 outsiders, “Hommorphic Encryption for Arithmetic of Approximate Numbers.” (Https://eprint.iacr.org/2016/421.pdf), Non-Patent Document 12: Junfeng Fan, 1 person outside, “Somewhat Practical Fully Homomorphic Encryption.” (Https://eprint.iacr.org/ 2012/144.pdf)) or Garbled Crypt (Non-Patent Document 13: Andrew Chi-Chih Yao, "How to generate and exchange secrets.” (Https
  • the calculation of the degree of similarity between the distributed feature amount included in the set selected from the concealed Hamming table and the first distributed feature amount is the Euclidean distance, the square value of the Euclidean distance, and Manhattan. Distance, Hamming distance, Levenshtein distance, cosine similarity, or Pearson's correlation coefficient may be used.
  • high similarity means that the Euclidean distance, the square value of the Euclidean distance, the Manhattan distance, the Hamming distance, or the Levenshtein distance is small, or the Cosine similarity, or the Pearson correlation coefficient is high. Means that.
  • Each device in the above embodiment is specifically a computer composed of a microprocessor, a ROM (Read Only Memory), a RAM (Random Access Memory), a hard disk unit, a display unit, a keyboard, a mouse, and the like. It is a system. Computer programs are recorded in the RAM or hard disk unit. When the microprocessor operates according to the above computer program, each device achieves its function.
  • a computer program is configured by combining a plurality of instruction codes indicating commands to a computer in order to achieve a predetermined function.
  • Each device in the above embodiment may be composed of a part or all of the constituent elements of one system LSI (Large Scale Integration: large-scale integrated circuit).
  • a system LSI is an ultra-multifunctional LSI manufactured by integrating a plurality of components on a single chip, and specifically, is a computer system including a microprocessor, a ROM, a RAM, and the like. ..
  • a computer program is recorded in the RAM. The system LSI achieves its function by operating the microprocessor according to the computer program.
  • each part of the component components constituting each of the above devices may be individually integrated into one chip, or may be integrated into one chip so as to include a part or all of them.
  • a system LSI it may be referred to as an IC (Integrated circuit), an LSI, a super LSI, or an ultra LSI due to the difference in the degree of integration.
  • the method of making an integrated circuit is not limited to LSI, and may be realized by a dedicated circuit or a general-purpose processor. After manufacturing the LSI, an FPGA (Field Programmable Gate Array) that can be programmed, or a reconfigurable processor that can reconfigure the connection or setting of the circuit cells inside the LSI may be used.
  • FPGA Field Programmable Gate Array
  • each of the above devices may be composed of an IC card or a single module that can be attached to and detached from each device.
  • the IC card or the module is a computer system composed of a microprocessor, ROM, RAM, and the like.
  • the IC card or the module may include the above-mentioned super multifunctional LSI.
  • the microprocessor operates according to a computer program, the IC card or the module achieves its function. This IC card or this module may have tamper resistance.
  • the present disclosure may be the method shown above. Further, it may be a computer program that realizes these methods by a computer, or it may be a digital signal composed of the above computer program.
  • the present disclosure describes the computer program or a recording medium capable of reading the digital signal by a computer, for example, a flexible disk, a hard disk, a CD-ROM, an MO (Magnet-Optical disc), a DVD, a DVD-ROM, a DVD-RAM. It may be recorded on a BD (Blu-ray (registered trademark) Disc), a semiconductor memory, or the like. Further, it may be the digital signal recorded on these recording media.
  • BD Blu-ray (registered trademark) Disc
  • semiconductor memory or the like.
  • the computer program or the digital signal may be transmitted via a telecommunication line, a wireless or wired communication line, a network typified by the Internet, data broadcasting, or the like.
  • the present disclosure is a computer system including a microprocessor and a memory, in which the memory records the above-mentioned computer program, and the microprocessor may operate according to the computer program.
  • This disclosure can be applied to a system or the like that protects privacy without handling sensitive information of a user in plain text in a data arithmetic unit.

Landscapes

  • Engineering & Computer Science (AREA)
  • Theoretical Computer Science (AREA)
  • Computer Security & Cryptography (AREA)
  • General Physics & Mathematics (AREA)
  • Physics & Mathematics (AREA)
  • Software Systems (AREA)
  • Health & Medical Sciences (AREA)
  • Computer Hardware Design (AREA)
  • General Engineering & Computer Science (AREA)
  • General Health & Medical Sciences (AREA)
  • Bioethics (AREA)
  • Computer Networks & Wireless Communication (AREA)
  • Signal Processing (AREA)
  • Medical Informatics (AREA)
  • Databases & Information Systems (AREA)
  • Biodiversity & Conservation Biology (AREA)
  • Biomedical Technology (AREA)
  • Life Sciences & Earth Sciences (AREA)
  • Collating Specific Patterns (AREA)

Abstract

秘匿認証方法は、秘密分散法により分散されたユーザ情報の特徴量である第１分散化特徴量と暗号化ＬＳＨパラメータとを入力として、秘匿ＬＳＨを用いて分散化ＬＳＨ値を導出し（Ｓ６０１）、分散化ＬＳＨ値と、一方向性関数の処理を実行するための分散鍵とを入力として、秘匿一方向性関数を用いて、分散化ハッシュ値を導出し（Ｓ６０２）、分散化ハッシュ値の分散を解除してハッシュ値に復号し（Ｓ６０３）、インデックスとしてのハッシュ値と、データ列としての分散化特徴量との複数の組が予め格納された秘匿ハッシュテーブルから、復号されたハッシュ値と一致するハッシュ値を含む組を選択し（Ｓ６０４）、選択された組に含まれる分散化特徴量と第１分散化特徴量との類似度を秘匿したまま計算し（Ｓ６０５）、計算された類似度に基づいてユーザの認証結果を秘匿したまま導出し（Ｓ６０６）、導出された認証結果を出力する（Ｓ６０７）。

Description

秘匿認証方法および秘匿認証システム
　本開示は、ユーザ情報およびユーザ情報に関連する情報を秘匿したままユーザの認証を行う秘匿認証方法および秘匿認証システムに関する。
　ディープニューラルネットワークを用いた画像認識性能の向上に伴い、例えばユーザの顔画像などを利用した認証（いわゆる、生体認証）の精度が向上している。近年、機械学習を用いた認証が多くの場面で活用されるようになっている。例えばコンビニエンスストアにおける決済、または、アミューズメント施設もしくはイベント会場への入場時の認証などに顔認証などの生体認証が用いられている。
　このような認証サービスをユーザが利用するためには、ユーザは、サーバに対してユーザ自身の情報（つまり、ユーザ情報）または当該情報から得られる特徴量を送信する必要がある。しかしながら、顔画像などのユーザ情報はプライバシ情報そのものであるため、保護されなければならない。また、ユーザ情報の特徴量から元のユーザ情報を推定する攻撃が知られているため、ユーザ情報だけでなく、特徴量も保護されなければならない。
　そのため、ユーザ情報およびユーザ情報に関連する情報（例えば、特徴量など）を秘匿したまま、ユーザの認証を行う技術が求められている。
　例えば、非特許文献１は、ユーザ端末装置で導出されたＬＳＨ（Ｌｏｃａｌｉｔｙ　Ｓｅｎｓｉｔｉｖｅ　Ｈａｓｈｉｎｇ）値とユーザ情報の特徴量とを暗号化してサーバへ送信することにより、ユーザ情報およびユーザ情報に関連する情報を秘匿したままユーザの認証を行う技術を開示している。また、例えば、非特許文献２は、入力データ（例えば、ユーザ情報の特徴量およびＬＳＨパラメータ）を秘匿したままＬＳＨ値の計算を複数回行い、得られるベクトルと乱数ベクトルとの内積をハッシュテーブルのインデックスとして利用する技術を開示している。
M. Sadegh Riazi、外４名、「Sub-Linear Privacy-Preserving Near-Neighbor Search with Untrusted Server on Large-Scale Datasets」（https://arxiv.org/abs/1612.01835） Alexander J. Titus、外８名、「SIG-DB: leveraging homomorphic encryption to Securely Interrogate privately held Genomic DataBases」（https://arxiv.org/abs/1612.01835）
　しかしながら、非特許文献１に記載の技術では、ユーザ情報およびユーザ情報に関連する情報を完全には秘匿できていないため、ユーザ情報が推測される可能性がある。また、非特許文献２に記載の技術では、ＬＳＨを複数回実行する必要があるため、計算量が膨大であり、効率が悪い。
　そこで、本開示では、ユーザ情報およびユーザ情報に関連する情報の秘匿性を向上させ、かつ、処理速度を向上させる秘匿認証方法および秘匿認証システムを提供する。
　上記課題を解決するため、本開示の秘匿認証方法の一様態は、入力を秘匿したまま認証処理を行う秘匿認証方法であって、秘密分散法により分散された特徴量であり、ユーザに関するユーザ情報の特徴量である第１分散化特徴量と、ＬＳＨ（Ｌｏｃａｌｉｔｙ　Ｓｅｎｓｉｔｉｖｅ　Ｈａｓｈｉｎｇ）の分散化されたパラメータである分散化ＬＳＨパラメータとを入力として、前記入力を秘匿したまま前記ＬＳＨの処理を実行する秘匿ＬＳＨを用いて、分散されたＬＳＨ値である分散化ＬＳＨ値を導出し、導出された前記分散化ＬＳＨ値と、一方向性関数の処理を実行するための鍵であって分散された鍵である分散鍵とを入力として、前記入力を秘匿のまま前記一方向性関数の処理を実行する秘匿一方向性関数を用いて、分散されたハッシュ値である分散化ハッシュ値を導出し、導出された前記分散化ハッシュ値を、秘密分散法による分散が解除されたハッシュ値に復号し、インデックスとしてのハッシュ値と、データ列としての分散化特徴量との複数の組が予め格納されたテーブルである秘匿ハッシュテーブルを用いて、前記複数の組のうち、復号された前記ハッシュ値と一致するハッシュ値を含む組を選択し、選択された前記組に含まれる分散化特徴量と、前記第１分散化特徴量との類似度を秘匿したまま計算し、計算された前記類似度に基づいて前記ユーザの認証結果を秘匿したまま導出し、導出された前記認証結果を出力する。
　また、上記課題を解決するため、本開示の秘匿認証システムの一様態は、入力を秘匿したまま認証処理を行う秘匿認証システムであって、秘密分散法により分散された特徴量であり、ユーザに関するユーザ情報の特徴量である第１分散化特徴量と、ＬＳＨの分散化されたパラメータである分散化ＬＳＨパラメータとを入力として、前記入力を秘匿したまま前記ＬＳＨの処理を実行する秘匿ＬＳＨを用いて、分散されたＬＳＨ値である分散化ＬＳＨ値を導出する分散化ＬＳＨ値導出部と、前記分散化ＬＳＨ値導出部により導出された前記分散化ＬＳＨ値と、一方向性関数の処理を実行するための鍵であって分散された鍵である分散鍵とを入力として、前記入力を秘匿のまま一方向性関数の処理を実行する秘匿一方向性関数を用いて分散されたハッシュ値である分散化ハッシュ値を導出する分散化ハッシュ値導出部と、前記分散化ハッシュ値導出部により導出された前記分散化ハッシュ値を、秘密分散法による分散が解除されたハッシュ値に復号する復号部と、インデックスとしてのハッシュ値と、データ列としての分散化特徴量との複数の組が予め格納されたテーブルである秘匿ハッシュテーブルを格納する秘匿ハッシュテーブル格納部と、前記秘匿ハッシュテーブルを用いて、前記複数の組のうち、復号された前記ハッシュ値と一致するハッシュ値を含む組を選択し、選択された前記組に含まれる分散化特徴量と、前記第１分散化特徴量との類似度を秘匿したまま計算し、計算された前記類似度に基づいて前記ユーザの認証結果を秘匿したまま導出する分散化認証結果導出部と、前記分散化認証結果導出部により導出された前記認証結果を出力する出力部と、を備える。
　本開示の秘匿認証方法および秘匿認証システムによれば、ユーザ情報およびユーザ情報に関連する情報の秘匿性を向上させ、かつ、処理速度を向上させることができる。
図１は、実施の形態に係る秘匿認証システムの全体構成の一例を示す図である。 図２は、実施の形態におけるユーザ端末装置の構成の一例を示す図である。 図３は、実施の形態におけるデータ提供装置の構成の一例を示す図である。 図４は、実施の形態におけるデータ演算装置の構成の一例を示す図である。 図５は、実施の形態における認証結果利用装置の構成一例を示す図である。 図６は、実施の形態に係る秘匿認証システムの初期化フェーズの動作の一例を示すシーケンス図である。 図７は、実施の形態に係る秘匿認証システムの登録フェーズの動作の一例を示すシーケンス図である。 図８は、図７のステップＳ２０５における詳細な処理の一例を示すシーケンス図である。 図９は、実施の形態に係る秘匿認証システムの認証フェーズの動作の一例を示すシーケンス図である。 図１０は、図９のステップＳ４０５における詳細な処理の一例を示すシーケンス図である。 図１１は、実施の形態におけるＬＳＨパラメータの一例を示す図である。 図１２は、実施の形態におけるＬＳＨ値の一例を示す図である。 図１３は、ハッシュテーブルの一例を示す図である。 図１４は、実施の形態における分散化特徴量の一例を示す図である。 図１５は、実施の形態における秘匿ハッシュテーブルの一例を示す図である。 図１６は、本実施の形態に係る秘匿認証方法の一例を示すフローチャートである。
　（本開示に至った知見）
　近年、機械学習を用いたユーザの認証（例えば、生体認証）が多くの場面で活用されるようになっている。例えば、生体認証には、ユーザの顔画像だけでなく、指紋画像、もしくは、虹彩画像などのユーザの身体的特徴に関する情報、歩容もしくは行動履歴などのユーザの行動的特徴に関する情報、または、ユーザが所持している文書情報などの所有物の特徴に関する情報を用いた認証をも含まれる。
　ユーザの認証には、１対１認証と１対Ｎ認証との２種類の認証方法が存在する。１対１認証とは、照合する本人のＩＤを例えばＩＤカードなどから読み出し、そのＩＤに紐づけられて登録されたユーザ情報と、センシングされたユーザ情報との同一性を判断することによりユーザを認証する方法である。一方、１対Ｎ認証は、複数のユーザのＩＤとそれらのＩＤのそれぞれに紐づけられたユーザ情報とを格納したデータベース（例えば、テーブル）の中から、センシングされたユーザ情報がどのＩＤに紐づけられたユーザ情報に対応するかを判定することにより、または、データベースに格納されたいずれのユーザ情報とも対応しないかを判定することにより、ユーザを認証する方法である。
　１つのユーザ情報との同一性のみを判定すれば良い１対１認証と比較して、データベースに予め登録された全てのユーザ情報との比較を行う必要がある１対Ｎ認証の方が処理量も多く、認証処理の難易度は高くなるが、ユーザがＩＤカード等を携帯および提示する必要がないため利便性に優れている。
　１対Ｎ認証を効率的に実現する方法として、最近傍探索を用いる方法がある。この方法では、事前にデータベースなどに登録された複数のユーザに関する情報（いわゆる、ユーザ情報）の特徴量と、認証用にカメラ、スキャナ、または、マイクなどのセンサでセンシングされたユーザ情報の特徴量（認証用のユーザ情報の特徴量ともいう）との類似度を計算し、認証用のユーザ情報の特徴量と最近傍の（つまり、最も類似している）特徴量をデータベースから探索する。この最近傍の特徴量と認証用のユーザ情報の特徴量との類似度が閾値以下であれば認証失敗とし、閾値より高ければ認証成功とする。
　最近傍探索手法として、Ｌｏｃａｌｉｔｙ　Ｓｅｎｓｉｔｉｖｅ　Ｈａｓｈｉｎｇ（ＬＳＨ）（非特許文献３：Piotr Indyk、外１名、「Approximate nearest neighbors: Towards removing the curse of dimensionality.」（https://www.cs.princeton.edu/courses/archive/spr04/cos598B/bib/IndykM-curse.pdf））と呼ばれる技術が用いられる。
　ＬＳＨは、近い入力値を同一のハッシュ値にマッピングする技術である。１対Ｎ認証でＬＳＨを用いると、似ているユーザ情報の特徴量をＬＳＨに入力すると同じハッシュ値（以下、ＬＳＨ値と呼ぶ）が出力されるため、認証用にセンシングされたユーザ情報に似ているユーザ情報の特徴量群をデータベースから効率的に取り出すことができる。そして、取り出された特徴量群に含まれる全ての特徴量と、認証用にセンシングされたユーザ情報の特徴量との類似度を計算することにより、認証用のユーザ情報の特徴量と最近傍の特徴量を求めることが出来る。
　このような認証サービスをユーザが利用するためには、ユーザは、サーバに対してユーザ自身の情報（つまり、ユーザ情報）または当該情報から得られる特徴量を送信する必要がある。しかしながら、顔画像などのユーザ情報はプライバシ情報そのものであるため、保護されなければならない。また、ユーザ情報の特徴量から元のユーザ情報を推定する攻撃が知られているため、ユーザ情報だけでなく、特徴量などのユーザ情報に関連する情報も保護されなければならない。
　そのため、ユーザがユーザ情報およびユーザ情報に関連する情報を秘匿したまま、効率良くユーザの認証を行う技術が求められている。
　データを秘匿したまま計算を行うことが可能な手法として、秘密計算（非特許文献４：Takashi Nishide、外１名「Multiparty computation for interval, equality, and comparison without bitdecomposition protocol.」（https://www.iacr.org/archive/pkc2007/44500343/44500343.pdf））を用いて、認証処理を行う方法が考えられている。秘密計算は、データを保管する主体に対して計算過程と結果とを秘匿することができる技術である。
　秘密計算を用いると、例えば、クラウドサーバのような第三者が管理するサーバにデータを保管し、その保管しているデータに対してあらゆる演算を実行することができる。第三者には、入力データ、計算過程、および、計算結果を知られることがないため、個人情報のような機微な情報に対する分析処理をアウトソースすることができる。
　また、入力データを秘匿したままユーザの認証を行う方式として、例えば、非特許文献１は、ユーザ端末装置で導出されたＬＳＨ値とユーザ情報の特徴量とを暗号化してサーバへ送信することにより、ユーザ情報およびユーザ情報に関連する情報を秘匿したままユーザの認証を行う技術を開示している。しかしながら、この方法ではユーザ情報およびユーザ情報に関連する情報を完全には秘匿できていないため、ユーザ情報が推測される可能性がある。
　また、入力データを秘匿したままＬＳＨを計算しデータベース検索を行う方式として、例えば、非特許文献２は、入力データ（例えば、ユーザ情報の特徴量およびＬＳＨパラメータ）を秘匿したままＬＳＨ値の計算を複数回行い、得られるベクトルと乱数ベクトルとの内積をハッシュテーブルのインデックスとして利用する技術を開示している。しかしながら、この方法では、計算量が膨大であるため実用的ではない。
　そこで本発明者らは、上記課題を鑑み鋭意検討した結果、ＬＳＨと秘密分散法とを用い、さらに、ＬＳＨの計算により得られるＬＳＨ値を秘匿したまま一方向性関数で処理することにより、ユーザ情報の秘匿性を向上させ、かつ、処理速度を向上させることができることを見出した。これにより、ＬＳＨ値を一方向性関数で処理したハッシュ値が漏洩しても、ハッシュ値から元のユーザ情報を推定することができない。また、ＬＳＨを用いることにより、１対Ｎ認証における計算量が低減される。さらに、秘密分散法を用いることにより、秘匿性および処理効率が向上される。
　したがって、本開示の秘匿認証方法および秘匿認証システムによれば、ユーザ情報およびユーザ情報に関連する情報の秘匿性を向上させ、かつ、処理速度を向上させることができる。
　本開示の一態様は以下の通りである。
　本開示の一様態に係る秘匿認証方法は、入力を秘匿したまま認証処理を行う秘匿認証方法であって、秘密分散法により分散された特徴量であり、ユーザに関するユーザ情報の特徴量である第１分散化特徴量と、ＬＳＨ（Ｌｏｃａｌｉｔｙ　Ｓｅｎｓｉｔｉｖｅ　Ｈａｓｈｉｎｇ）の暗号化されたパラメータである暗号化ＬＳＨパラメータとを入力として、前記入力を秘匿したまま前記ＬＳＨの処理を実行する秘匿ＬＳＨを用いて、暗号化され、かつ、分散されたＬＳＨ値である分散化ＬＳＨ値を導出し、導出された前記分散化ＬＳＨ値と、一方向性関数の処理を実行するための鍵であって暗号化され、かつ、分散された鍵である分散鍵とを入力として、前記入力を秘匿のまま前記一方向性関数の処理を実行する秘匿一方向性関数を用いて、暗号化され、かつ、分散されたハッシュ値である分散化ハッシュ値を導出し、導出された前記分散化ハッシュ値を、秘密分散法による分散が解除されたハッシュ値に復号し、インデックスとしてのハッシュ値と、データ列としての分散化特徴量との複数の組が予め格納されたテーブルである秘匿ハッシュテーブルを用いて、前記複数の組のうち、復号された前記ハッシュ値と一致するハッシュ値を含む組を選択し、選択された前記組に含まれる分散化特徴量と、前記第１分散化特徴量との類似度を秘匿したまま計算し、計算された前記類似度に基づいて前記ユーザの認証結果を秘匿したまま導出し、導出された前記認証結果を出力する。
　これにより、秘匿認証方法では、ハッシュ値以外の情報は秘密分散法により分散されているため、例えばＬＳＨ値および特徴量などのユーザ情報に関連する情報などの元のユーザ情報を推定可能な情報が一切公開されない。そのため、秘匿認証方法では、ユーザ情報およびユーザ情報に関連する情報の秘匿性が向上される。また、ハッシュ値を用いて秘匿ハッシュテーブルを参照することから、少ない計算コストで認証処理を行うことができる。したがって、秘匿認証方法によれば、ユーザ情報およびユーザ情報に関連する情報の秘匿性を向上させ、かつ、処理速度を向上させることができる。
　本開示の一様態に係る秘匿認証方法は、前記ユーザの前記認証結果の導出において、選択された前記組に含まれる前記分散化特徴量のうち、前記第１分散化特徴量と最も類似度の高い分散化特徴量を第２分散化特徴量として抽出し、抽出された前記第２分散化特徴量と前記第１分散化特徴量と類似度が閾値よりも高いか否かを判定し、前記類似度が前記閾値よりも高いと判定された場合、前記ユーザの認証が成功したことを表す分散化された数値を前記認証結果として出力し、前記類似度が前記閾値以下であると判定された場合、前記ユーザの認証が失敗したことを表す分散化された数値を前記認証結果として出力してもよい。
　これにより、秘匿認証方法では、認証用のユーザ情報の特徴量である第１分散化特徴量と最も類似度の高い分散化特徴量を抽出することができるため、計算量が削減される。また、秘匿認証方法では、閾値に基づいてユーザ本人であるか否かを判定するため、例えば、センシングの条件などにより特徴量に誤差が生じた場合でも、事前登録されたユーザ本人の特徴量と同じものであると判定することができる。
　本開示の一様態に係る秘匿認証方法では、前記特徴量は、前記ユーザの身体的特徴に関する身体的特徴量、前記ユーザの行動的特徴に関する行動的特徴量、および、前記ユーザが保有している保有物の特徴に関する保有物特徴量のいずれかであり、前記身体的特徴量は、網膜画像、虹彩画像、指紋画像、静脈画像、音声情報、耳の形状情報、ＤＮＡ（ｄｅｏｘｙｒｉｂｏｎｕｃｌｅｉｃ　ａｃｉｄ）情報、および、手のひらの画像のうちの少なくとも１つの情報の特徴量を含み、前記行動的特徴は、筆跡、キーストローク、歩容、および、行動履歴のうちの少なくとも１つの情報の特徴量を含み、前記保有物特徴量は、前記ユーザが保有している文書情報、記憶、および、所有物のうちの少なくとも１つの情報の特徴量を含んでもよい。
　これにより、秘匿認証方法では、設計に応じて、認証に使用される特徴量を適宜選択することができる。
　本開示の一様態に係る秘匿認証方法では、前記第１分散化特徴量および前記分散化特徴量は、それぞれ、分散された複数種類の特徴量を含み、選択された前記組に含まれる分散化特徴量と、前記第１分散化特徴量との前記類似度の計算において、前記複数種類の特徴量のそれぞれの類似度を計算してもよい。
　これにより、より高い精度で、かつ、応用性の高い認証が可能となる。
　本開示の一様態に係る秘匿認証方法では、前記分散化ハッシュ値は、ランダム性を有してもよい。
　ＬＳＨの取りうる値の範囲が小さい場合、全ての値のハッシュ値を計算することは容易であるため、出力から入力ランダム性を持たせることで、ハッシュ値から元のＬＳＨ値を計算するのが困難になる。そのため、秘匿認証方法によれば、ＬＳＨ値およびユーザ情報の秘匿性（安全性ともいう）が向上する。
　本開示の一様態に係る秘匿認証方法では、前記データ列は、さらに、分散化されたユーザＩＤである分散化ユーザＩＤを含んでもよい。
　これにより、秘匿認証方法では、ユーザの認証とともにユーザＩＤの確認も可能となるため、汎用性が向上する。
　本開示の一様態に係る秘匿認証方法は、前記認証結果の出力において、導出された前記認証結果と、選択された前記組の前記データ列に含まれる前記分散化特徴量および前記ユーザＩＤの少なくとも１つを出力してもよい。
　これにより、秘匿認証方法は、認証結果を利用する際に、ユーザに関する様々な情報を用いることが出来るため、認証結果とともにユーザＩＤを表示するなどより高度なサービスの提供が可能になる。
　本開示の一様態に係る秘匿認証方法では、前記ユーザのユーザ端末は、センシングによって得られた前記ユーザ情報から前記特徴量を算出し、算出された前記特徴量を暗号下肢、かつ、秘密分散法により分散することにより、前記第１分散化特徴量を導出してもよい。
　これにより、秘匿認証方法では、ユーザがユーザ端末装置を用いてユーザ情報の特徴量を求めることができるため、例えば顔画像などのプライバシ情報そのものであるユーザ情報を外部に送信する必要がなくなる。そのため、秘匿認証方法によれば、ユーザ情報の安全性が向上する。
　本開示の一様態に係る秘匿認証方法では、前記ユーザのユーザ端末装置は、センシングによって得られた前記ユーザ情報を情報が漏洩しない信頼できるサーバに送信し、前記サーバは、前記ユーザ情報から前記特徴量を導出し、前記特徴量を秘密分散法により分散することにより前記第１分散化特徴量を導出してもよい。
　これにより、秘匿認証方法では、ユーザ端末装置が行う処理を削減することができるため、ユーザ端末装置に必要なリソースが少なくて済む。
　本開示の一様態に係る秘匿認証方法では、前記第１分散化特徴量は、前記ユーザの認証結果を導出する演算装置で導出され、前記ユーザのユーザ端末装置は、センシングによって得られた前記ユーザ情報を秘密分散法により分散した分散化ユーザ情報を前記演算装置に送信し、前記演算装置は、前記分散化ユーザ情報から前記第１分散化特徴量を導出してもよい。
　これにより、秘匿認証方法では、信頼できるサーバを用意する必要がなく、また、信頼できるサーバから情報が漏洩する危険性もないため、安全に特徴量を計算することが可能となる。
　本開示の一様態に係る秘匿認証方法では、前記分散化ＬＳＨパラメータは、前記ユーザの認証結果を導出する演算装置に送信され、前記演算装置は、前記第１分散化特徴量と、前記分散化ＬＳＨパラメータとを入力として、前記秘匿ＬＳＨを用いて前記分散化ＬＳＨ値を導出してもよい。
　これにより、サービス提供者（例えば、データ提供装置を有する企業など）の資産であるＬＳＨパラメータの漏洩も防ぐことが出来る。
　本開示の一様態に係る秘匿認証方法では、前記ＬＳＨは、ＳｉｍＨａｓｈであってもよい。
　本開示の一様態に係る秘匿認証方法では、前記ＬＳＨは、ＭｉｎＨａｓｈであってもよい。
　本開示の一様態に係る秘匿認証方法では、前記一方向性関数は、ＡＥＳ（Ａｄｖａｎｃｅｄ　Ｅｎｃｒｙｐｔｉｏｎ　Ｓｔａｎｄａｒｄ）であってもよい。
　本開示の一様態に係る秘匿認証方法では、前記一方向性関数は、ＳＨＡ（Ｓｅｃｕｒｅ　Ｈａｓｈ　Ａｌｇｏｒｉｔｈｍ）またはＭＤ５（Ｍｅｓｓａｇｅ　Ｄｉｇｅｓｔ　５）であってもよい。
　本開示の一様態に係る秘匿認証方法では、前記一方向性関数は、ＥｌＧａｍａｌ暗号またはＲＳＡ（Ｒｉｖｅｓｔ－Ｓｈａｍｉｒ－Ａｄｌｅｍａｎ）暗号または楕円曲線暗号であってもよい。
　本開示の一様態に係る秘匿認証システムは、入力を秘匿したまま認証処理を行う秘匿認証システムであって、秘密分散法により分散された特徴量であり、ユーザに関するユーザ情報の特徴量である第１分散化特徴量と、ＬＳＨの暗号化されたパラメータである暗号化ＬＳＨパラメータとを入力として、前記入力を秘匿したまま前記ＬＳＨの処理を実行する秘匿ＬＳＨを用いて、暗号化され、かつ、分散されたＬＳＨ値である分散化ＬＳＨ値を導出する分散化ＬＳＨ値導出部と、前記分散化ＬＳＨ値導出部により導出された前記分散化ＬＳＨ値と、一方向性関数の処理を実行するための鍵であって暗号化され、かつ、分散された鍵である分散鍵とを入力として、前記入力を秘匿のまま一方向性関数の処理を実行する秘匿一方向性関数を用いて暗号化され、かつ、分散されたハッシュ値である分散化ハッシュ値を導出する分散化ハッシュ値導出部と、前記分散化ハッシュ値導出部により導出された前記分散化ハッシュ値を、秘密分散法による分散が解除されたハッシュ値に復号する復号部と、インデックスとしてのハッシュ値と、データ列としての分散化特徴量との複数の組が予め格納されたテーブルである秘匿ハッシュテーブルを格納する秘匿ハッシュテーブル格納部と、前記秘匿ハッシュテーブルを用いて、前記複数の組のうち、復号された前記ハッシュ値と一致するハッシュ値を含む組を選択し、選択された前記組に含まれる分散化特徴量と、前記第１分散化特徴量との類似度を秘匿したまま計算し、計算された前記類似度に基づいて前記ユーザの認証結果を秘匿したまま導出する分散化認証結果導出部と、前記分散化認証結果導出部により導出された前記認証結果を出力する出力部と、を備える。
　これにより、秘匿認証システムでは、ハッシュ値以外の情報は秘密分散法により分散されているため、例えばＬＳＨ値および特徴量などのユーザ情報に関連する情報などの元のユーザ情報を推定可能な情報が一切公開されない。そのため、秘匿認証システムでは、ユーザ情報およびユーザ情報に関連する情報の秘匿性が向上される。また、ハッシュ値を用いて秘匿ハッシュテーブルを参照することから、少ない計算コストで認証処理を行うことができる。したがって、秘匿認証システムによれば、ユーザ情報およびユーザ情報に関連する情報の秘匿性を向上させ、かつ、処理速度を向上させることができる。
　なお、以下で説明する実施の形態は、いずれも本開示の一具体例を示すものである。以下の実施の形態で示される数値、形状、構成要素、ステップ、ステップの順序などは、一例であり、本開示を限定する主旨ではない。また、以下の実施の形態における構成要素のうち、最上位概念を示す独立請求項に記載されていない構成要素については、任意の構成要素として説明される。また、各図は、必ずしも厳密に図示したものではない。各図において、実質的に同一の構成については同一の符号を付し、重複する説明は省略または簡略化することがある。
　また、本開示の主旨を逸脱しない限り、当業者が思いつく各種変形を実施の形態に施したものや、全ての実施の形態において、各々の実施の形態における一部の構成要素を組み合わせて構築される別の形態も、本開示の範囲に含まれる。
　（実施の形態）
　以下、本実施の形態に係る秘匿認証方法および秘匿認証システムについて図面を用いて説明する。
　［１．秘匿認証システムの概要］
　まず、本実施の形態に係る秘匿認証システムの概要について説明する。本実施の形態に係る秘匿認証システムは、ユーザ情報を秘匿したままユーザの認証処理を行うためのシステムである。より具体的には、秘匿認証システムは、ユーザ情報を秘匿したまま、近似最近傍探索手法の１つであるＬＳＨ（Ｌｏｃａｌｉｔｙ　Ｓｅｎｓｉｔｉｖｅ　Ｈａｓｈｉｎｇ）を用いて、ハッシュテーブルに事前に登録された複数のユーザ情報の中から、認証対象のユーザ情報と同じハッシュ値のユーザ情報を抽出し、抽出されたユーザ情報と認証対象のユーザ情報との類似度に基づいてユーザの認証処理を行うためのシステムである。ここでは、秘匿または秘匿化とは、秘密分散法により分散されることをいい、以下、分散または分散化とも称する。また、暗号または暗号化とは、秘密分散法以外の何らかの暗号化技術により暗号化されることをいう。使用される暗号化技術は、特に限定されない。
　［１．１　秘匿認証システムの構成］
　続いて、本実施の形態に係る秘匿認証システムの構成について図１を参照しながら説明する。
　図１は、本実施の形態に係る秘匿認証システムの全体構成の一例を示す図である。図１に示されるように、秘匿認証システム５００は、例えば、ユーザ端末装置１００と、データ提供装置２００と、３つのデータ演算装置３００、３１０、３２０と、認証結果利用装置４００と、を備える。各装置間の通信は、有線のインターネット線、無線通信、専用通信等のいずれかであればよい。
　ユーザ端末装置１００は、認証対象であるユーザが所有する端末装置である。データ提供装置２００は、秘匿認証サービスを提供する企業または団体が所有する装置である。データ演算装置３００、３１０、３２０は、ユーザ端末装置１００から送信されたユーザ情報の特徴量と、データ提供装置２００から送信された演算に必要なパラメータなどの情報とを取得して、取得した情報を秘匿したまま認証結果を導出するための演算処理を行う装置である。ここでは、データ演算装置３００、３１０、３２０はそれぞれ、１つのクラウドサーバ、または、１つのクラウドサーバに含まれる装置である。認証結果利用装置４００は、ユーザの認証結果を利用する企業または団体が所有する装置である。認証結果利用装置４００は、例えば、ユーザが利用する施設の受付などに設置される。
　秘匿認証システム５００では、例えば、データ提供装置２００は、ＬＳＨパラメータと、一方向性関数を計算するために必要な鍵と、ユーザの認証処理（より具体的には、認証結果の導出処理）で用いる閾値とを、３つのクラウドサーバ、すなわち、データ演算装置３００、３１０、３２０に送信する。なお、データ提供装置２００は、上記の鍵を秘匿化してデータ演算装置３００、３１０、３２０に送信する。上記のＬＳＨパラメータおよび閾値は、秘密分散法により分散されて送信される。
　また、秘匿認証システム５００では、例えば、ユーザ端末装置１００は、ユーザが秘匿認証サービスを利用する際に、ユーザ情報の特徴量を秘匿して３つのクラウドサーバであるデータ演算装置３００、３１０、３２０（以下、３つのクラウドサーバとも呼ぶ）に送信する。
　３つのクラウドサーバは互いに通信を行うことにより、それぞれのクラウドサーバが他のクラウドサーバで得られたデータを利用しながら、データを秘匿したまま認証結果を導出する。そして、３つのクラウドサーバはそれぞれ得られた認証結果を秘匿したまま認証結果利用装置４００に送信する。
　なお、ユーザ端末装置１００は１つ以上であってもよいし、データ提供装置２００も１つ以上であってもよいし、認証結果利用装置４００も１つ以上であってもよい。
　さらに、図１に示す例では、秘匿認証システム５００は、データ演算装置を３つ備えているが、データ演算装置を少なくとも２つ備えていればよい。理由を簡単に説明すると、本実施の形態で用いられる秘密分散法では、分散されたデータの秘密分散法による分散を解除して秘密分散法により分散される前のデータ（つまり、元のデータ）に復号するために、分散されたデータのうち少なくとも２つの分散されたデータが必要となる。つまり、秘密分散法では、１つの分散されたデータから元のデータを復号することができない。したがって、秘匿認証システム５００は、データ演算装置を少なくとも２つ備えていれば、秘密分散法による分散を解除することができる。
　上述のように、秘密分散法により分散されたデータは、１つの分散されたデータだけでは元のデータを復号できないため、各データ演算装置で行われる処理もデータを秘匿したまま行われ、当該処理により導出された認証結果もまた、秘密分散法により秘匿された状態である。したがって、復号された認証結果を得るために、２つ以上の秘匿された認証結果が必要となる。
　なお、秘匿認証システム５００を構成する各装置間の通信は、リアルタイムの通信でなくてもよい。例えば、ユーザ端末装置１００はセンシングしたユーザ情報または秘匿認証処理の要求コマンドをある程度集めて、一時に、３つのデータ演算装置３００、３１０、３２０に送信してもよい。
　以下、秘匿認証システム５００の各構成について説明するが、図１に示される秘匿認証システム５００は一例であって、本開示の秘匿認証システムは、これに限定されない。
　［１．２　ユーザ端末装置］
　図２は、本実施の形態におけるユーザ端末装置１００の構成の一例を示す図である。ユーザ端末装置１００は、例えば、センシング部１０１と、特徴量算出部１０２と、特徴量分散部１０３と、通信部１０４とを備える。ユーザ端末装置１００は、例えば、認証対象であるユーザが所有する端末装置である。ユーザ端末装置１００は、例えば、プロセッサ（マイクロプロセッサ）、メモリ、センサ、および、通信インタフェース等を備えるコンピュータまたは携帯端末に実装される。
　ユーザ端末装置１００は、例えば、ユーザに関するユーザ情報をセンシングし、センシングされたユーザ情報の特徴量を算出し、算出された特徴量を秘密分散法により分散し、分散された特徴量（いわゆる、分散化特徴量）をデータ演算装置３００、３１０、３２０に送信する。例えば、センシング部１０１は、ユーザ情報をセンシングし、特徴量算出部１０２は、センシングされたユーザ情報の特徴量を算出し、特徴量分散部１０３は、算出された特徴量を秘密分散法により分散し、通信部１０４は、分散された特徴量をデータ演算装置３００、３１０、３２０へ送信する。
　そして、ユーザ端末装置１００は、算出された特徴量に対応する認証結果をデータ演算装置３００、３１０、３２０に要求し、秘匿された認証結果をデータ演算装置３００、３１０、３２０から得て、秘匿認証システム５００におけるサービスに利用してもよい。このとき、ユーザ端末装置１００は、取得した認証結果を復号して利用する。
　［１．２．１　センシング部］
　センシング部１０１は、ユーザを認証するために必要な情報をセンシングするためのセンサである測定装置を、１つ以上含んで構成される。ユーザを認証するために必要な情報は、言い換えると、ユーザを他のユーザから識別するための情報であり、例えば、ユーザそのものが有する特徴またはユーザの行動の特徴に関する情報（以下、ユーザの情報ともいう）である。
　センシング部１０１がセンシングする情報は、ユーザを認証するために用いられる。例えば、ユーザそのものが有する特徴に関する情報は、ユーザの身体的特徴に関する情報である。ユーザの身体的特徴に関する情報は、例えば、顔、耳、もしくは、手のひらなど身体の一部に関する情報、または、静脈、声紋、指紋、網膜、虹彩、もしくは、ＤＮＡ（deoxyribonucleic acid）などの身体に一部に準ずる要素に関する情報でもよい。これらの情報は、画像データ、音声データ、または、数値などの文字列データである。例えば、ユーザの身体的特徴に関する情報は、顔画像、網膜画像、虹彩画像、指紋画像、静脈画像、音声情報、耳の形状情報、ＤＮＡ情報、または、手のひらの画像などである。
　また、センシング部１０１がセンシングする情報は、ユーザの行動の特徴（以下、行動的特徴という）に関する情報であってもよい。例えば、ユーザの行動的特徴に関する情報は、筆跡、キーストローク、もしくは、歩容などのユーザの癖に関する情報、または、行動履歴に関する情報である。行動履歴に関する情報は、例えば、ＧＰＳ（Global Positioning System）で得られる位置情報、ユーザが電気機器、もしくは、車両等の移動体を操作した履歴を示すログ情報、または、ユーザによる商品等の購入履歴情報等でもよい。
　ログ情報は、例えば、ユーザが車両を操作した場合、ステアリング操作、アクセル操作、ブレーキ操作、変速ギアの操作等に関連して取得または測定される各種情報であり、例えば、車両の移動の変位量、速度、または、加速度等を操作時刻と対応付けた情報であってもよい。
　なお、センシング部１０１がセンシングする情報は、例えばユーザが他人に知られたくない個人的な事柄であるプライバシデータであってもよい。例えば、プライバシデータは、ユーザが保有している文書情報、記憶、または、所有物に関する情報であってもよい。
　［１．２．２　特徴量算出部］
　特徴量算出部１０２は、センシング部１０１で取得したユーザの情報（以下、ユーザ情報ともいう）から特徴量を算出する。特徴量算出部１０２によって算出される特徴量は、複数の成分を含むベクトルで表され得る。
　特徴量は、例えば、ユーザの身体的特徴に関する情報から算出される特徴量（以下、身体的特徴量ともいう）、ユーザの行動的特徴に関する情報から算出される特徴量（以下、行動的特徴量ともいう）、および、ユーザが保有している保有物の特徴に関する情報から算出される特徴量（以下、保有物特徴量ともいう）のいずれかである。
　例えば、身体的特徴量は、網膜画像、虹彩画像、指紋画像、静脈画像、音声情報、耳の形状情報、ＤＮＡ情報、および、手のひらの画像のうちの少なくとも１つの情報の特徴量を含む。また、例えば、行動的特徴量は、筆跡、キーストローク、歩容、および、行動履歴のうちの少なくとも１つの情報の特徴量を含み、保有物特徴量は、ユーザが保有している文書情報、記憶、および、所有物のうちの少なくとも１つの情報の特徴量を含む。
　なお、特徴量は、例えば、ユーザ情報がユーザの顔画像である場合、顔画像における特徴的なパラメータの主成分である。当該特徴量は、例えば、ユーザの顔画像のある領域の位置、面積、または、幅等に関する特徴的なパラメータを含むベクトルで表されてもよい。また、特徴量は、例えば、ユーザ情報がユーザの行動履歴に関する情報である場合、当該履歴情報から、時間軸に対応した要素の傾向を（例えば多項式で表現した場合の各項の係数を）成分として含むベクトルで表されてもよい。
　なお、センシング部１０１で取得したユーザ情報から抽出された特徴量自体も、プライバシデータであり得る。特徴量は任意のｄ（ここで、ｄは自然数）に対して、ｄ個の要素を持つベクトルであり、例えば｛１，２，３，４，５｝のようなデータである。
　［１．２．３　特徴量分散部］
　特徴量分散部１０３は、特徴量算出部１０２により算出された特徴量を、あらかじめ定められた方法により分散して秘匿する。特徴量分散部１０３では、データ演算装置３００、３１０、３２０において特徴量を分散された状態のまま使用して予測処理を行うことが可能な方法、例えば、Ｓｈａｍｉｒ（２，３）閾値秘密分散法（非特許文献５：Adi Shamir、「How to Share a Secret」（http://cs.jhu.edu/~sdoshi/crypto/papers/shamirturing.pdf））を用いて特徴量を分散させることにより、分散された特徴量（以下、分散化特徴量ともいう）を作成する。
　秘密分散法とは、秘密情報から複数の分散情報を生成する技術である。分散情報は予め定められた組み合わせからは秘密情報を復元できるが、それ以外の組み合わせからは秘密情報が復元できないように作られる。予め定められた組み合わせには様々な構造を取ることができ、その構造は、アクセス構造と呼ばれる。
　様々なアクセス構造があるが、代表的なアクセス構造として、ここでは閾値型アクセス構造について簡単に説明する。閾値型アクセス構造は、生成される分散情報の数ｎと、閾値ｔ（ｔ≦ｎ）の２つのパラメータで表される。ｔ個以上の分散情報からは秘密情報が復元できるが、ｔ個未満の分散情報からは秘密情報が復元できない。
　閾値型アクセス構造を有する秘密分散法には、例えば、上記のＳｈａｍｉｒ（２，３）閾値秘密分散法があり、秘密情報を入力として３個の分散情報を生成するための分散処理と、２個以上の分散情報から秘密情報を復元する復元処理とを含む。
　分散処理に用いる法ｐは、あらかじめシステムで決定され、特徴量分散部１０３で保持される。図１４は、本実施の形態における分散化特徴量の一例を示す図である。
　［１．２．４　通信部］
　通信部１０４は、複数（例えば、３つ）のデータ演算装置３００、３１０、３２０と通信を行う。通信部１０４は、特徴量分散部１０３で作成された分散された特徴量（いわゆる、分散化特徴量）をそれぞれデータ演算装置３００、３１０、３２０に送信する。
　複数（例えば、３つ）のデータ演算装置３００、３１０、３２０は、これらの分散化特徴量を受信した後、これらの分散化特徴量を秘匿された状態のまま使用して、事前登録処理および認証処理を実行する。詳細は、後述する。
　［１．３　データ提供装置］
　続いて、データ提供装置２００について説明する。データ提供装置２００は、秘匿認証サービスを提供する企業または団体が所有する装置である。データ提供装置２００は、例えば、ＬＳＨパラメータと、ユーザの認証処理に用いる閾値と、一方向性関数を計算するために必要な鍵とを、データ演算装置３００、３１０、３２０に提供するための装置である。
　図３は、本実施の形態におけるデータ提供装置２００の構成の一例を示す図である。データ提供装置２００は、例えば、ＬＳＨパラメータ生成部２０１と、鍵生成部２０２と、鍵分散部２０３と、閾値設定部２０４、通信部２０５と、を備える。
　データ提供装置２００は、精度よくユーザの認証を行うためのＬＳＨパラメータを作成し、作成したＬＳＨパラメータを秘密分散法により分散して３つのデータ演算装置３００、３１０、３２０に送信する。ＬＳＨパラメータは、例えば、ＬＳＨを用いて同じ人の顔画像の特徴量から同じＬＳＨ値が導出されるように設定される。また、データ提供装置２００は、ユーザ情報が漏洩しないような、一方向性関数の処理を実行するための鍵を生成し、生成した鍵を秘密分散法により分散させて、分散された暗号鍵（以下、分散鍵という）をそれぞれ３つのデータ演算装置３００、３１０、３２０に送信する。
　［１．３．１　ＬＳＨパラメータ生成部］
　ＬＳＨパラメータ生成部２０１は、ＬＳＨを用いた認証を行うために必要なＬＳＨパラメータを生成し、通信部２０５に送信する。
　図１１は、本実施の形態におけるＬＳＨパラメータの一例を示す図である。図１２は、本実施の形態におけるＳｉｍＨａｓｈを用いたＬＳＨ値の計算式、およびＬＳＨ値の一例である。図１２に示されるように、例えば、ＳｉｍＨａｓｈと呼ばれるハッシュ関数を利用するＬＳＨの場合、特徴量のＬＳＨ値は、任意のｎ個のベクトルとの内積を計算し、それぞれの内積値が０以上であるかを確認する。内積値が０以上であれば１とし、０未満であれば０とすることで、ｍ個の｛０、１｝つまりｍビットの値が得られる。このｍビットの値をＬＳＨ値とする。図１１に示されるＬＳＨパラメータは、ｍを３としたときの、ＳｉｍＨａｓｈを利用するＬＳＨにおけるベクトルである。
　［１．３．２　鍵生成部］
　鍵生成部２０２では、一方向性関数の処理を実行するために用いられる鍵を生成する。例えば、一方向性関数としてＡｄｖａｎｃｅｄ　Ｅｎｃｒｙｐｔｉｏｎ　Ｓｔａｎｄａｒｄ（ＡＥＳ）（非特許文献６：Joan Daemen、Vincent Rijmen、「AES Proposal: Rijndael」（https://csrc.nist.gov/csrc/media/projects/cryptographic-standards-and-guidelines/documents/aes-development/rijndael-ammended.pdf））を用いる場合、鍵生成部２０２は、一方向性を安全に満たすために、１２８ｂｉｔ、１９２ｂｉｔまたは２５６ｂｉｔの値を暗号鍵として生成する。
　［１．３．３　鍵分散部］
　鍵分散部２０３は、鍵生成部２０２で作成した暗号鍵を秘密分散法により分散し、通信部２０５へ送信する。
　［１．３．４　閾値設定部］
　閾値設定部２０４では、ユーザの認証処理に用いる閾値を設定し、設定した閾値を秘密分散法により分散し、通信部２０５へ送信する。データ演算装置３００、３１０、３２０がユーザの認証処理を行う際は、ユーザ情報の特徴量（第１分散化特徴量）と、サーバに事前に登録済みの分散化特徴量のうち、最も類似度が高い分散化特徴量との類似度が、閾値設定部２０４で設定した閾値以上であれば、事前に登録されたユーザであると判定して、ユーザを認証し、類似度が閾値以下であれば、事前に登録されたユーザではないと判定して、ユーザを否認する。
　［１．３．５　通信部］
　通信部２０５は、データ演算装置３００、３１０、３２０と通信を行う。通信部２０５は、ＬＳＨパラメータ生成部２０１で作成された分散化ＬＳＨパラメータと、鍵分散部２０３で作成された分散鍵と、閾値設定部２０４で設定された分散化閾値を複数（ここでは、３つ）のデータ演算装置３００、３１０、３２０に送信する。
　［１．４　データ演算装置］
　続いて、データ演算装置について説明する。データ演算装置３００、３１０、３２０は、例えば、クラウドサーバである。秘匿認証システム５００では、データ演算装置３００は、２つ以上備えられていればよい。
　本実施の形態では、３つのデータ演算装置３００、３１０、３２０はそれぞれ、互いに通信を行うことで、入力を秘匿したまま認証処理を行い、認証結果利用装置４００へ送信する。
　より具体的には、データ演算装置３００、３１０、３２０は、ユーザ情報の特徴量である第１分散化特徴量と、分散化されたＬＳＨのパラメータである分散化ＬＳＨパラメータとを入力として、入力を秘匿したままＬＳＨの処理を実行する秘匿ＬＳＨを用いて分散化ＬＳＨ値を計算する。
　さらにデータ演算装置３００、３１０、３２０は、分散化ＬＳＨ値と分散鍵とを入力として、入力を秘匿のまま一方向性関数の処理を実行する秘匿一方向性関数を用いて、分散化ハッシュ値を計算し、分散化ハッシュ値を、秘密分散法による分散を解除されたハッシュ値に復号する。
　その後、データ演算装置３００、３１０、３２０は、得られたハッシュ値をインデックスとして、秘匿ハッシュテーブル格納部３０６に格納されている秘匿ハッシュテーブルを参照する。秘匿ハッシュテーブルには、インデックスとしてのハッシュ値と、データ列としての分散化特徴量との複数の組が予め格納されている。
　データ演算装置３００、３１０、３２０は、ユーザ情報の事前登録処理を行う際には、得られたハッシュ値をインデックスとして、秘匿ハッシュテーブルのデータ列にユーザ端末装置１００から送信された分散化特徴量を格納する。
　また、データ演算装置３００、３１０、３２０は、ユーザの認証処理を行う際には、秘匿ハッシュテーブルに格納されている複数の組のうち、復号されたハッシュ値と一致するハッシュ値を含む組を選択し、選択された組に含まれる分散化特徴量と、ユーザ端末装置１００から送信されたユーザの分散化特徴量（いわゆる、第１分散化特徴量）との類似度を計算し、計算された類似度に基づいてユーザの認証結果を秘匿したまま導出する。例えば、データ演算装置３００、３１０、３２０は、第１分散化特徴量との類似度が最も高い分散化特徴量を第２分散化特徴量として抽出する。そして、データ演算装置３００、３１０、３２０は、抽出された第２分散化特徴量と第１分散化特徴量との類似度が閾値よりも高いか否かを判定し、類似度が閾値より高ければ事前登録されたユーザ本人であると認証し、類似度が閾値以下であれば事前登録されたユーザ本人ではないと拒否する。
　図４は、データ演算装置３００の構成の一例を示す図である。データ演算装置３００は、分散鍵格納部３０１と、ＬＳＨパラメータ格納部３０２と、分散化ＬＳＨ値導出部３０３と、閾値格納部３０４と、分散化ハッシュ値導出部３０５と、秘匿ハッシュテーブル格納部３０６と、分散化認証結果導出部３０７と、通信部３０８と、分散化ハッシュ値復号部３０９と、を備える。
　データ演算装置３１０、３２０も、データ演算装置３００と同じ構成である。
　［１．４．１　分散鍵格納部］
　分散鍵格納部３０１は、データ提供装置２００から送信された、秘密分散法により分散された分散鍵を受け取り格納する。
　［１．４．２　ＬＳＨパラメータ格納部］
　ＬＳＨパラメータ格納部３０２は、データ提供装置２００から送信された分散化ＬＳＨパラメータを受け取り格納する。
　［１．４．３　分散化ＬＳＨ値導出部］
　分散化ＬＳＨ値導出部３０３は、ユーザ端末装置１００から送信された分散化特徴量と、ＬＳＨパラメータ格納部３０２に格納された分散化ＬＳＨパラメータとを用いて、分散化特徴量を復号することなくＬＳＨの処理を実行する秘匿ＬＳＨを用いて分散化特徴量のＬＳＨ値、つまり、分散化ＬＳＨ値を導出する。分散化ＬＳＨ値導出部３０３は、導出した分散化ＬＳＨ値を分散化ハッシュ値導出部３０５に送信する。
　ＬＳＨの計算方法としては、ＳｉｍＨａｓｈ（非特許文献７：Moses S. Charikar、「Similarity Estimation Techniques from Rounding Algorithms.」（https://www.cs.princeton.edu/courses/archive/spring04/cos598B/bib/CharikarEstim.pdf））、または、ＭｉｎＨａｓｈ（非特許文献８：Ping Li、外１名、「b-Bit Minwise Hashing」（https://arxiv.org/pdf/0910.3349.pdf））を用いてもよい。上述したように、ＳｉｍＨａｓｈでは、ＬＳＨパラメータとして特徴量と同じ次元数の、値がランダムなベクトルをｎ個作成しておく。このｎ個のベクトルと特徴量との内積を計算し、内積値が０以上か否かを判定する。これによって得られたｎ個の｛０，１｝をＬＳＨ値として用いる。
　［１．４．４　閾値格納部］
　閾値格納部３０４は、データ提供装置２００から送信された、ユーザの認証処理で用いられる閾値を受け取り格納する。
　［１．４．５　分散化ハッシュ値導出部］
　分散化ハッシュ値導出部３０５は、分散化ＬＳＨ値導出部３０３で導出された分散化ＬＳＨ値と、分散鍵格納部３０１に格納された分散鍵とを用いて、ＬＳＨ値を秘匿したまま一方向性関数の処理を実行する秘匿一方向性関数を用いて分散化ハッシュ値を導出する。分散化ハッシュ値導出部３０５は、導出した分散化ハッシュ値を分散化ハッシュ値復号部３０９に送信する。復号し、復号されたハッシュ値を出力、秘匿ハッシュテーブル格納部３０６に送信する。
　一方向性関数としては、ＭＤ５、もしくは、Ｓｅｃｕｒｅ　Ｈａｓｈ　Ａｌｇｏｒｉｔｈｍ（ＳＨＡ）などの暗号学的ハッシュ関数、べき乗関数（非特許文献９：Chao Ning、外１名、「Constant-Rounds, Linear Multi-party Computation for Exponentiation and Modulo Reduction with Perfect Security」（https://eprint.iacr.org/2011/069.pdf））、または、ＡＥＳ、または、ＥｌＧａｍａｌ暗号、ＲＳＡ暗号、楕円曲線暗号などの公開鍵暗号を用いてもよい。
　例えば、一方向性関数として、べき乗関数を用いる場合は、分散鍵をｋ、分散化ＬＳＨ値をｘ、出力のハッシュ値をｙとしたとき、ｙ＝ｋ＾ｘ　ｍｏｄ ｐを計算する。なお、ｐは秘密分散法における法と異なる値でも良いが、同じ値の方が、効率が良い。
　一方向性関数として、ＡＥＳを用いる場合には、分散鍵は秘密分散法により分散されたＡＥＳ鍵のことをさす。一方向性関数として、鍵の入力を必要としない方法を用いる場合には、分散鍵は空としてもよい。
　［１．４．６　分散化ハッシュ値復号部］
　分散化ハッシュ値復号部３０９は、分散化ハッシュ値導出部３０５で導出した分散化ハッシュ値を、秘密分散法による分散が解除されたハッシュ値に復号し、復号されたハッシュ値を秘匿ハッシュテーブル格納部３０６に送信する。
　［１．４．７　秘匿ハッシュテーブル格納部］
　秘匿ハッシュテーブル格納部３０６は、秘匿ハッシュテーブルを格納している。秘匿ハッシュテーブルは、ハッシュ値をインデックスとしてのハッシュ値と、データ列としての分散化特徴量との組が予め格納されたテーブルである。
　秘匿ハッシュテーブル格納部３０６は、ユーザ情報の事前登録処理の際には、分散化ハッシュ値復号部３０９で復号したハッシュ値を用いて秘匿ハッシュテーブルを参照し、ユーザ端末装置１００から送信された分散化特徴量を格納する。例えば、秘匿ハッシュテーブル格納部３０６は、復号されたハッシュ値と同じハッシュ値をインデックスとするデータ列に、ユーザ端末装置１００から送信された分散化特徴量を秘匿ハッシュテーブルに格納してもよい。また、例えば、秘匿ハッシュテーブル格納部３０６は、復号されたハッシュ値と、ユーザ端末装置１００から送信された分散化特徴量とを紐づけて、つまり、組として、秘匿ハッシュテーブルに格納してもよい。
　秘匿ハッシュテーブル格納部３０６は、ユーザの認証処理の際には、分散化ハッシュ値復号部３０９で復号したハッシュ値を用いて秘匿ハッシュテーブルを参照し、復号されたハッシュ値と同じハッシュ値をインデックスとする行に格納されている分散化特徴量を全て読み出し、分散化認証結果導出部３０７に送信する。
　また、例えば、秘匿ハッシュテーブル格納部３０６は、ユーザの認証処理の際には、分散化ハッシュ値復号部３０９で復号したハッシュ値と一致するハッシュ値を含む組を秘匿ハッシュテーブルから選択し、選択された組を分散化認証結果導出部３０７に送信してもよいし、選択された組に含まれる分散化特徴量を全て分散化認証結果導出部３０７に送信してもよい。
　ここで、ハッシュテーブルについて具体的に説明する。図１３はハッシュテーブルの一例を示す図であり、図１５は本実施の形態における秘匿ハッシュテーブルの一例を示す図である。この例では、３人のユーザ情報が事前登録されている。
　図１３に示されるハッシュテーブルは、平文のハッシュテーブルであり、インデックスとしてのＬＳＨ値と、データ列としての特徴量とが紐づけられて格納されている。平文のハッシュテーブルは、ＬＳＨ値から元のユーザ情報を導出することができるため、ユーザ情報の安全性の観点から好ましくない。そこで、図１５に示されるように、本実施の形態では、秘匿一方向性関数を用いて分散化ＬＳＨ値のハッシュ値である分散化ハッシュ値を導出し、導出された分散化ハッシュ値を復号して得られたハッシュ値をインデックスとすることにより、安全性を高めている。また、本実施の形態では、秘匿ハッシュテーブルには、インデックスとしてのハッシュ値にデータ列としての分散化特徴量が紐づけられて格納されている。図１５では、秘密分散法の法ｐは、例えば、６５５１９である。
　［１．４．８　分散化認証結果導出部］
　分散化認証結果導出部３０７は、例えば、秘匿ハッシュテーブル格納部３０６から送信された分散化特徴量を受け取り、受け取った分散化特徴量と認証対象のユーザの分散化特徴量（第１分散化特徴量）との類似度に基づいてユーザの認証結果を導出する。
　例えば、分散化認証結果導出部３０７は、ユーザの認証結果の導出において、選択された組に含まれる分散化特徴量のうち、ユーザ端末装置１００から送信された第１分散化特徴量と最も類似度の高い分散化特徴量を第２分散化特徴量として抽出し、抽出された第２分散化特徴量と第１分散化特徴量との類似度が閾値よりも高いか否かを判定する。なお、分散化認証結果導出部３０７は、類似度を計算する際には、平文の類似度を求めてもよいし、秘密分散法により分散された類似度の分散値（分散化類似度ともいう）を求めてもよい。
　最後に、分散化認証結果導出部３０７は、計算された類似度が閾値よりも高ければ、ユーザを認証し、閾値よりも低ければユーザを否認する。
　類似度としては、２つの特徴量（ここでは、第１分散化特徴量と第２分散化特徴量）のユークリッド類似度、または、２乗ユークリッド類似度を類似度としてもよいし、コサイン類似度を類似度としてもよい。
　認証結果は、平文の認証結果であってもよいし、秘密分散法により分散された認証結果の分散値（分散化認証結果ともいう）であってもよい。
　分散化認証結果導出部３０７は、導出した認証結果を通信部３０８に送信する。送信された認証結果は、最終的に認証結果利用装置４００に送信される。なお、認証結果はユーザ端末装置１００に送信されてもよい。
　［１．４．９　通信部］
　通信部３０８は、ユーザ端末装置１００、および、データ提供装置２００と通信を行う。例えば、通信部３０８は、データ提供装置２００から分散化ＬＳＨパラメータと、認証処理で用いられる分散化閾値と、秘密分散法により分散された鍵とを受け取り、分散化ＬＳＨパラメータをＬＳＨパラメータ格納部３０２に、分散化閾値を閾値格納部３０４に、分散鍵を分散鍵格納部３０１に送信する。
　また、通信部３０８は、ユーザ端末装置１００から秘密分散法により分散された特徴量（いわゆる、分散化特徴量）を受け取り、分散化ＬＳＨ値導出部３０３、および、分散化認証結果導出部３０７に送信する。
　［１．５　認証結果利用装置］
　続いて、認証結果利用装置について説明する。認証結果利用装置４００は、例えば、イベント会場等の受付に設置されている端末であり、プロセッサ（マイクロプロセッサ）、メモリ、センサ、通信インタフェース等を備えるコンピュータまたは携帯端末に実装される。秘匿認証システム５００では、認証結果利用装置４００は、１つ以上備えられてもよい。
　本実施の形態では、認証結果利用装置４００は、３つのデータ演算装置３００、３１０、３２０から分散された認証結果（分散化認証結果ともいう）を受け取り、秘密分散法による分散を解除して平文の認証結果に復号する。
　分散化認証結果は、例えば、受付担当者またはユーザに認証結果に関する情報を提示するために利用されてもよく、イベント会場への入退場ゲートを開錠するために利用されてもよい。
　図５は、認証結果利用装置４００の構成の一例を示す図である。認証結果利用装置４００は、分散化認証結果復号部４０１と、認証結果利用部４０２と、通信部４０３と、を備える。
　［１．５．１　分散化認証結果復号部］
　分散化認証結果復号部４０１は、データ演算装置３００、３１０、３２０から送信された分散化認証結果を復号する。例えば、分散化認証結果復号部４０１は、分散化認証結果の秘密分散法による分散を解除して、認証結果に復号してもよい。分散化認証結果復号部４０１は、復号された認証結果を認証結果利用部４０２に送信する。
　［１．５．２　認証結果利用部］
　認証結果利用部４０２は、分散化認証結果復号部４０１で復号した分散化認証結果を利用する。分散化認証結果は、例えば、受付担当者またはユーザに認証結果に関する情報を提示するために利用される。認証結果利用部４０２は、例えばディスプレイ、音声出力装置、その他のユーザインタフェースを含んで実装されうる。
　認証結果の提示の例としては、例えば、認証結果利用装置４００のディスプレイに認証結果に関する情報を表示すること等が挙げられる。認証結果に関する情報は、例えば、ユーザ本人であると認証された場合、「ＯＫ」、または、「認証されました」などのユーザが認証されたことを示す情報であってもよく、当該情報に加え、ユーザのＩＤなどのユーザに関するユーザ情報を含んでもよい。また、認証結果に関する情報は、例えば、ユーザが否認された場合、「ＮＧ」、または、「認証されませんでした」などの否認されたことを示す情報であってもよい。
　また、分散化認証結果は、例えば、イベント会場への入退場ゲートを開錠するために利用されてもよい。認証結果利用装置４００は、例えば、イベント会場等への入退場ゲートと接続されていてもよい。その場合、分散化認証結果復号部４０１で復号された認証結果（いわゆる、認証結果）を受け取った認証結果利用部４０２は、ユーザが認証されていたら入退場ゲートを開ける等の操作に関する制御を行ってもよい。
　［１．５．３　通信部］
　通信部４０３は、データ演算装置３００、３１０、３２０と通信を行う。通信部４０３は、データ演算装置３００、３１０、３２０から秘密分散法で分散された認証結果（いわゆる、分散化認証結果）を受け取り、分散化認証結果復号部４０１へ送信する。
　［２．　秘匿認証システムの動作（秘匿認証方法）］
　続いて、本実施の形態に係る秘匿認証システム５００の動作の一例について説明する。秘匿認証システム５００の動作は、（１）データ提供装置２００が秘密分散法により分散された鍵（いわゆる、分散鍵）と、分散化ＬＳＨパラメータと、ユーザの認証処理に用いられる閾値をデータ演算装置３００、３１０、３２０に送信する初期化フェーズと、（２）ユーザが自身の情報（つまり、ユーザ情報）の特徴量を登録する登録フェーズと、（３）ユーザが現在取得したユーザ情報を用いて認証を行う認証フェーズと、を含む。
　［２．１　初期化フェーズ］
　まず、秘匿認証システム５００の初期化フェーズの動作について説明する。図６は、本実施の形態に係る秘匿認証システム５００の初期化フェーズの動作の一例を示すシーケンス図である。
　初期化フェーズでは、まず、データ提供装置２００は、ＬＳＨパラメータ生成部２０１でＬＳＨパラメータを生成し、閾値設定部２０４で認証に用いる閾値を設定する（Ｓ１０１）。
　続いて、データ提供装置２００は、データ演算装置３００、３１０、３２０にＬＳＨパラメータと閾値とを送信する（Ｓ１０２）。
　続いて、データ演算装置３００、３１０、３２０は、データ提供装置２００から送信されたＬＳＨパラメータと閾値とを受け取り、受け取ったＬＳＨパラメータをＬＳＨパラメータ格納部３０２に格納し、閾値を閾値格納部３０４に格納する（Ｓ１０３）。
　続いて、データ提供装置２００は、鍵生成部２０２で一方向性関数の処理に用いる鍵を生成する（Ｓ１０４）。
　続いて、データ提供装置２００は、ステップＳ１０４の処理で生成された鍵を鍵分散部２０３で秘密分散法により分散する（Ｓ１０５）。
　続いて、データ提供装置２００は、ステップＳ１０５の処理で分散された鍵（いわゆる、分散鍵）をデータ演算装置３００、３１０、３２０に送信する（Ｓ１０６）。
　続いては、データ演算装置３００、３１０、３２０は、データ提供装置２００から送信された分散鍵を受け取り、受け取った分散鍵を分散鍵格納部３０１に格納する（Ｓ１０７）。
　以上により、初期化フェーズでは、データ提供装置２００は、ＬＳＨの処理で用いられるＬＳＨパラメータを生成し、一方向性関数の処理で用いられる分散鍵を設定して、ＬＳＨパラメータおよび分散鍵をデータ演算装置３００、３１０、３２０に送信する。これにより、データ演算装置３００、３１０、３２０は、ユーザ端末装置１００から分散化特徴量が送信された場合に、当該分散化特徴量を受け取り、ユーザの登録処理（以下の登録フェーズの動作）およびユーザの認証処理（以下の認証フェーズの動作）を行うことができる。
　［２．２　登録フェーズ］
　次に、秘匿認証システム５００の登録フェーズの動作について説明する。図７は、本実施の形態に係る秘匿認証システム５００の登録フェーズの動作の一例を示すシーケンス図である。
　登録フェーズでは、まず、ユーザ端末装置１００は、センシング部１０１でユーザ情報をセンシングする（Ｓ２０１）。ステップＳ２０１では、例えば、顔認証のための顔画像を登録する場合、センシング部１０１はユーザの顔画像を撮影する。
　続いて、ユーザ端末装置１００は、特徴量算出部１０２にて、ステップＳ２０１でセンシングされたユーザ情報から特徴量を算出する（Ｓ２０２）。ここで、特徴量を算出する方法は、サービス提供者により事前に決定され、全てのユーザ端末装置１００に共有されているものとする。
　続いて、ユーザ端末装置１００は、特徴量分散部１０３にて、ステップＳ２０２で算出された特徴量を秘密分散法によって分散し（Ｓ２０３）、分散された特徴量（いわゆる、分散化特徴量）をデータ演算装置３００、３１０、３２０に送信する（Ｓ２０４）。
　続いて、データ演算装置３００、３１０、３２０は、ユーザ端末装置１００から分散化特徴量を取得すると、ユーザの登録処理を行う（Ｓ２０５）。
　以下、ユーザの登録処理について図８を参照しながらより具体的に説明する。図８は、図７のステップＳ２０５における詳細な処理の一例を示すシーケンス図である。
　ステップＳ２０５の処理では、データ演算装置３００、３１０、３２０は、分散化ＬＳＨ値導出部３０３で特徴量の分散化ＬＳＨ値を導出する（Ｓ３０１）。より具体的には、データ演算装置３００、３１０、３２０は、それぞれ、ユーザ端末装置１００から取得した分散化特徴量と、ＬＳＨパラメータ格納部３０２に格納されたＬＳＨパラメータ（分散化パラメータ）と入力として、分散化ＬＳＨ値導出部３０３にて、入力を秘匿したままＬＳＨの処理を実行する秘匿ＬＳＨを用いて、特徴量の分散化ＬＳＨ値を導出する。これにより、データ演算装置３００、３１０、３２０は、得られた分散化特徴量の秘密分散法による分散を解除することなく、分散化ＬＳＨ値を導出することができる。
　続いて、データ演算装置３００、３１０、３２０は、ＬＳＨ値の分散化ハッシュ値を導出する（Ｓ３０２）。より具体的には、データ演算装置３００、３１０、３２０は、ステップＳ３０１で導出された分散化ＬＳＨ値と、分散鍵格納部３０１に格納された分散鍵とを入力として、分散化ハッシュ値導出部３０５にて、入力を秘匿のまま一方向性関数の処理を実行する秘匿一方向性関数を用いて、ＬＳＨ値の分散化ハッシュ値を導出する。これにより、データ演算装置３００、３１０、３２０は、分散化ＬＳＨ値の秘密分散法による分散を解除することなく、ＬＳＨ値の分散化ハッシュ値を導出することができる。
　続いて、データ演算装置３００、３１０、３２０は、分散化ハッシュ値を復号する（Ｓ３０３）。より具体的には、データ演算装置３００、３１０、３２０は、ステップＳ３０２で導出された分散化ハッシュ値を、分散化ハッシュ値復号部３０９にて、秘密分散法による分散が解除されたハッシュ値に復号する。
　続いて、データ演算装置３００、３１０、３２０は、ステップＳ３０３で得られたハッシュ値をインデックスとして、ユーザ端末装置１００から取得した分散化特徴量を秘匿ハッシュテーブルに追加する（Ｓ３０４）。上述したように、秘匿ハッシュテーブルは、インデックスとしてのハッシュ値と、データ列としての分散化特徴量との組が予め格納されたテーブルである。データ演算装置３００、３１０、３２０は、例えば、秘匿ハッシュテーブル格納部３０６にて、ステップＳ３０３で得られたハッシュ値をインデックスとして秘匿ハッシュテーブルを参照し、ハッシュ値が示す行のデータ列に、ユーザ端末装置１００から送信された分散化特徴量を追加する。
　以上により、登録フェーズでは、データ演算装置３００、３１０、３２０は、それぞれ、ユーザ端末装置１００から送信された分散化特徴量のＬＳＨ値のハッシュ値を、秘密分散法による分散を解除せずに導出し、導出されたハッシュ値（つまり、分散化ハッシュ値）が示す行のデータ列にユーザ端末装置１００から送信された分散化特徴量を追加することでユーザ登録処理を行う。
　［２．３　認証フェーズ］
　次に、秘匿認証システム５００の認証フェーズの動作について説明する。図９は、本実施の形態に係る秘匿認証システム５００の認証フェーズの動作の一例を示すシーケンス図である。
　認証フェーズでは、まず、ユーザ端末装置１００は、センシング部１０１でユーザ情報をセンシングする（Ｓ４０１）。ステップＳ４０１では、例えば、登録フェーズのステップＳ２０１において顔認証のための顔画像を登録した場合、センシング部１０１はユーザの顔画像を撮影する。
　続いて、ユーザ端末装置１００は、特徴量算出部１０２にて、ステップＳ４０１でセンシングされたユーザ情報から特徴量を算出する（Ｓ４０２）。なお、ステップＳ２０２と同様に、特徴量を算出する方法はサービス提供者により事前に決定され、全てのユーザ端末装置１００に共有されているものとする。
　続いて、ユーザ端末装置１００は、特徴量分散部１０３にて、ステップＳ４０２で算出された特徴量を秘密分散法によって分散し（Ｓ４０３）、分散された特徴量（いわゆる、分散化特徴量）をデータ演算装置３００、３１０、３２０に送信する（Ｓ４０４）。
　続いて、データ演算装置３００、３１０、３２０は、ユーザ端末装置１００から分散化特徴量（以下、認証フェーズにおいて、第１分散化特徴量という）を取得すると、ユーザの認証処理を行う（Ｓ４０５）。ユーザの認証処理の詳細については、後述する。
　続いて、データ演算装置３００、３１０、３２０は、ステップＳ４０５のユーザの認証処理で得られた分散化認証結果を認証結果利用装置４００に送信する（Ｓ４０６）。
　続いて、認証結果利用装置４００は、データ演算装置３００、３１０、３２０から取得した分散化認証結果を復号する（Ｓ４０７）。より具体的には、認証結果利用装置４００は、データ演算装置３００、３１０、３２０から送信された分散化認証結果を取得すると、分散化認証結果復号部４０１にて分散化認証結果の秘密分散法による分散を解除して、平文の認証結果に復号する。
　続いて、認証結果利用装置４００は、ステップＳ４０７で復号された認証結果を認証結果利用部４０２にて利用する（Ｓ４０８）。例えば、認証結果利用部４０２は、認証結果を受付担当者またはユーザに認証結果に関する情報を提示するために利用してもよく、イベント会場への入退場ゲートを会場するために利用してもよい。イベント会場の入退場ゲートだけでなく、例えば、建物または部屋などのドアであってもよい。
　以下、ユーザの認証処理について図１０を参照しながらより具体的に説明する。図１０は、図９のステップＳ４０５における詳細な処理の一例を示すシーケンス図である。
　ステップＳ４０５の処理では、データ演算装置３００、３１０、３２０は、分散化ＬＳＨ値導出部３０３で特徴量の分散化ＬＳＨ値を導出する（Ｓ５０１）。より具体的には、データ演算装置３００、３１０、３２０は、それぞれ、ユーザ端末装置１００から取得した分散化特徴量と、ＬＳＨパラメータ格納部３０２に格納されたＬＳＨパラメータ（いわゆる、分散化ＬＳＨパラメータ）とを入力として、分散化ＬＳＨ値導出部３０３にて、入力を秘匿したままＬＳＨの処理を実行する秘匿ＬＳＨを用いて、特徴量の分散化ＬＳＨ値を導出する。これにより、データ演算装置３００、３１０、３２０は、得られた分散化特徴量の秘密分散法による分散を解除することなく、分散化ＬＳＨ値を導出することができる。
　続いて、データ演算装置３００、３１０、３２０は、ＬＳＨ値の分散化ハッシュ値を導出する（Ｓ５０２）。より具体的には、データ演算装置３００、３１０、３２０は、ステップＳ５０１で導出された分散化ＬＳＨ値と、分散鍵格納部３０１に格納された分散鍵とを入力として、分散化ハッシュ値導出部３０５にて、入力を秘匿のまま一方向性関数の処理を実行する秘匿一方向性関数を用いて、ＬＳＨ値の分散化ハッシュ値を導出する。これにより、データ演算装置３００、３１０、３２０は、分散化ＬＳＨ値の秘密分散法による分散を解除することなく、ＬＳＨ値の分散化ハッシュ値を導出することができる。
　続いて、データ演算装置３００、３１０、３２０は、分散化ハッシュ値を復号する（Ｓ５０３）。より具体的には、データ演算装置３００、３１０、３２０は、ステップＳ５０２で導出された分散化ハッシュ値を、分散化ハッシュ値復号部３０９にて、秘密分散法による分散が解除されたハッシュ値に復号する。
　続いて、データ演算装置３００、３１０、３２０は、分散化認証結果導出部３０７にて、ステップＳ５０３で得られたハッシュ値をインデックスとして秘匿ハッシュテーブルを参照し、ハッシュ値が示す行のデータ列に格納されている分散化特徴量群を取り出す（Ｓ５０４）。分散化特徴量群は、例えば、０個以上の分散化特徴量を含むリストである。なお、秘匿ハッシュテーブルは、インデックスとしてのハッシュ値と、データ列としての分散化特徴量との複数の組が予め格納されたテーブルであってもよい。この場合、データ演算装置３００、３１０、３２０は、分散化認証結果導出部３０７にて、当該秘匿ハッシュテーブルを用いて、複数の組のうち、分散化ハッシュ値復号部３０９により復号されたハッシュ値と一致するハッシュ値を含む組を選択してもよい。
　続いて、データ演算装置３００、３１０、３２０は、ステップＳ５０４で秘匿ハッシュテーブルから取り出された分散化特徴量群に含まれるすべての分散化特徴量と、ステップＳ４０４でユーザ端末装置１００から送信された認証用の分散化特徴量（いわゆる、第１分散化特徴量）との分散化類似度（以下、類似度という）を計算する（Ｓ５０５）。例えば、データ演算装置３００、３１０、３２０は、分散化認証結果導出部３０７にて、秘匿ハッシュテーブルから選択された組に含まれる分散化特徴量と、第１分散化特徴量との類似度を秘匿のまま計算してもよい。
　続いて、データ演算装置３００、３１０、３２０は、ステップＳ５０５にて計算された類似度に基づいてユーザの認証結果を導出する。例えば、データ演算装置３００、３１０、３２０は、分散化認証結果導出部３０７にて、分散化特徴量群の中で、認証用の分散化特徴量（つまり、第１分散化特徴量）と最も類似度の高い分散化特徴量を第２分散化特徴量として抽出し、抽出された第２分散化特徴量と第１分散化特徴量との類似度が閾値よりも高いか否かを判定し、認証結果を導出する（Ｓ５０６）。
　ステップＳ５０６では、例えば、データ演算装置３００、３１０、３２０は、分散化認証結果導出部３０７にて、類似度が閾値よりも高いと判定された場合、ユーザの認証が成功したことを表す数値の分散値を認証結果として出力し、類似度が閾値以下であると判定された場合、ユーザの認証が失敗したこと（つまり、ユーザを否認したこと）を表す数値の分散値を認証結果として出力する。
　ユーザの認証が成功したことを表す数値と、ユーザの認証が失敗したことを表す数値とは、異なる数値であり、システムで決定されていればどのような数値であってもよい。例えば、ユーザの認証が成功したことを表す数値は１であり、ユーザを否認したことを表す数値は０であってもよい。
　以上により、認証フェーズでは、データ演算装置３００、３１０、３２０は、秘匿ＬＳＨと秘匿一方向性関数とを用いて、ユーザが認証用に送信したユーザ情報、および、ユーザにより秘匿ハッシュテーブルに事前に登録されたユーザ情報を秘匿にしたまま、認証処理を行う。認証処理では、データ演算装置３００、３１０、３２０は、認証用の分散化特徴量（いわゆる、第１分散化特徴量）と最も類似度の高い分散化特徴量を第２分散化特徴量として抽出することにより認証対象のユーザ情報と最も類似度の高いユーザ情報を効率的に検索することができる。そして、データ演算装置３００、３１０、３２０は、抽出された第２分散化特徴量と第１分散化特徴量との類似度が閾値よりも高いか否かを判定し、認証が成功したか否かを表す数値の分散値を認証結果として出力する。
　以上、秘匿認証システム５００の一例について説明したが、秘匿認証システム５００は、少なくとも以下の構成を備えるシステムであってもよい。
　秘匿認証システム５００は、例えば、分散化ＬＳＨ値導出部３０３（図４参照）と、分散化ハッシュ値導出部３０５（図４参照）と、分散化ハッシュ値復号部３０９（図４参照）と、秘匿ハッシュテーブル格納部３０６（図４参照）と、分散化認証結果導出部３０７（図４参照）と、出力部（図４の通信部３０８に対応）と、を備えているとよい。各部については上述したためここでの説明を省略する。
　また、秘匿認証方法は、少なくとも以下の処理フローを含む方法であってもよい。図１６は、本実施の形態に係る秘匿認証方法の一例を示すフローチャートである。図１６に示されるように、秘匿認証システム５００により実行される秘匿認証方法は、例えば、暗号化され、かつ、秘密分散法により分散された特徴量であり、ユーザに関するユーザ情報の特徴量である第１分散化特徴量と、ＬＳＨの暗号化されたパラメータである暗号化ＬＳＨパラメータとを入力として、入力を秘匿したままＬＳＨの処理を実行する秘匿ＬＳＨを用いて、暗号化され、かつ、分散されたＬＳＨ値である分散化ＬＳＨ値を導出し（Ｓ６０１）、導出された分散化ＬＳＨ値と、一方向性関数の処理を実行するための鍵であって暗号化され、かつ、分散された鍵である分散鍵とを入力として、入力を秘匿のまま一方向性関数の処理を実行する秘匿一方向性関数を用いて、暗号化され、かつ、分散されたハッシュ値である分散化ハッシュ値を導出し（Ｓ６０２）、導出された分散化ハッシュ値を、秘密分散法による分散が解除されたハッシュ値に復号し（Ｓ６０３）、インデックスとしてのハッシュ値と、データ列としての分散化特徴量との複数の組が予め格納されたテーブルである秘匿ハッシュテーブルを用いて、複数の組のうち、復号されたハッシュ値と一致するハッシュ値を含む組を選択し（Ｓ６０４）、選択された組に含まれる分散化特徴量と、第１分散化特徴量との類似度を秘匿したまま計算し（Ｓ６０５）、計算された類似度に基づいてユーザの認証結果を秘匿したまま導出し（Ｓ６０６）、導出された認証結果を出力する（Ｓ６０７）。
　（他の実施の形態）
　以上、本開示に係る秘匿認証システム、および、秘匿認証方法について、実施の形態に基づいて説明したが、本開示は、上記の実施の形態に限定されるものではない。本開示の主旨を逸脱しない限り、当業者が思いつく各種変形を実施の形態に施したものや、実施の形態における一部の構成要素を組み合わせて構築される別の形態も、本開示の範囲に含まれる。例えば、以下のような場合も本開示に含まれる。
　（１）上記実施の形態では、ユーザ情報の特徴量として例えば顔画像の特徴量を利用してユーザの認証を行っているが、網膜画像、虹彩画像、指紋画像、静脈画像、音声情報、耳の形状情報、ＤＮＡ情報、もしくは、手のひらの画像といったユーザの身体的特徴の特徴量、筆跡、キーストローク、歩容、もしくは、行動履歴などのユーザの行動的特徴の特徴量、または、ユーザが所有している文書情報、ユーザの記憶、もしくは、ユーザが所持しているもの（所有物）などのユーザの所有物の特徴に関する特徴量をユーザの認証に利用してもよい。
　（２）上記実施の形態では、単一の特徴量（例えば、第１分散化特徴量）のみを用いてユーザの認証を行っているが、例えば上記（１）に示される複数種類の特徴量を組み合わせてユーザの認証を行ってもよい。例えば、指紋画像と虹彩画像とを用いてユーザの認証を行ってもよい。この場合、指紋画像を用いたユーザの認証が成功しても、虹彩画像を用いたユーザの認証が失敗した場合、ユーザは否認される。
　（３）上記実施の形態では、ユーザ端末装置１００がユーザ情報から特徴量を算出しているが、データ演算装置３００、３１０、３２０がユーザ情報から特徴量を算出ユーザ情報から特徴量を算出してもよい。この場合、データ演算装置３００、３１０、３２０は、分散化ユーザ情報から分散化特徴量を算出する。例えば、ユーザ端末装置１００は、ユーザ情報を分散した分散化ユーザ情報をデータ演算装置３００、３１０、３２０に送信する。データ演算装置３００、３１０、３２０は、分散化ユーザ情報を取得すると、ユーザ情報を秘匿したまま特徴量を算出する、つまり、分散化ユーザ情報から分散化特徴量を算出する。
　上記の実施の形態では、登録フェーズおよび認証フェーズで、ユーザ端末装置１００が分散化特徴量をデータ演算装置３００、３１０、３２０に送信しているが、データ演算装置３００、３１０、３２０がユーザ端末装置１００から送信された分散化ユーザ情報から分散化特徴量を算出してもよい。なお、登録フェーズおよび認証フェーズでは、特徴量の算出方法が同じであればよく、どのような算出方法を使ってもよい。
　（４）上記実施の形態では、ユーザ端末装置１００がユーザ情報から特徴量を算出しているが、ユーザ端末装置１００とは別に、特徴量の算出を行う特徴量算出装置を用意し、特徴量算出装置でユーザ情報の特徴量を算出してもよい。
　この場合、ユーザ端末装置１００はユーザ情報を分散した分散化ユーザ情報を特徴量算出装置に送信し、特徴量算出装置がユーザ情報を秘匿したまま特徴量を算出してもよい。また、ユーザ端末装置１００はユーザ情報を特徴量算出装置に送信し、特徴量算出装置がユーザ情報から特徴量を算出してもよい。
　なお、暗号化ユーザ情報を特徴量算出装置に送信する場合は、特徴量算出装置が信頼のおける装置であり、特徴量算出装置からユーザ情報が漏洩しないことが求められる。
　（５）上記実施の形態では、秘匿ハッシュテーブルのデータ列には分散化特徴量のみを含んでいるが、さらに、分散化ユーザＩＤなどの分散化されたユーザ情報を含んでもよい。秘匿ハッシュテーブルに格納されるユーザ情報はこれに限定されず、秘匿ハッシュテーブルのデータ列に分散化特徴量が含まれていればいかなるデータでも良い。この場合、データ演算装置３００、３１０、３２０は、認証結果として認証が成功したか否かを表す数値に加え、秘匿ハッシュテーブルに格納されているユーザ情報を出力してもよい。
　（６）上記実施の形態では、データ演算装置３００、３１０、３２０は、認証処理を行う際に、認証用の分散化特徴量（第１分散化特徴量）と最も類似度の高い分散化特徴量（第２分散化特徴量）との類似度と閾値とを比較して認証が成功したか否かを表す数値の分散値を認証結果として出力しているが、秘匿ハッシュテーブルから選択された分散化特徴量、および、それに対応する分散化ユーザＩＤなどの分散化ユーザ情報を認証結果利用装置４００に出力してもよい。この場合、データ演算装置３００、３１０、３２０から分散化特徴量、分散化ユーザＩＤ、または、その他の分散化ユーザ情報を受け取った認証結果利用装置４００にて、認証対象のユーザ情報と、データ演算装置３００、３１０、３２０から送信されたユーザ情報とを比較することでユーザの認証を行ってもよい。
　（７）上記実施の形態では、データ演算装置３００、３１０、３２０は分散化認証結果を認証結果利用装置４００に送信しているが、データ演算装置３００、３１０、３２０が分散化認証結果を認証結果に復号してから認証結果を認証結果利用装置４００に送信してもよい。これにより、認証結果利用装置４００は分散化認証結果を平文の認証結果に復号する必要がないため、受け取った認証結果をそのまま利用することができる。
　（８）上記実施の形態では、データ演算装置３００、３１０、３２０は分散化認証結果を認証結果利用装置４００に送信しているが、分散化認証結果をユーザ端末装置１００に送信してもよい。この場合、ユーザ端末装置１００は、例えば、分散化認証結果復号部４０１および認証結果利用部４０２を備えており、取得した分散化認証結果を復号して利用してもよい。
　（９）上記実施の形態では、データ演算装置３００、３１０、３２０は認証結果利用装置４００に分散化認証結果を送信しているが、認証結果利用装置４００およびユーザ端末装置１００の両方に分散化認証結果を送信してもよい。
　（１０）上記実施の形態では、一方向性関数としてＡＥＳを用いた例を説明したが、一方向性関数として、出力から入力を求められない関数であればいかなる関数を用いても良い。
　（１１）上記（１０）では、一方向性関数として、出力から入力を求められない関数であればいかなる関数でもよいとしているが、べき乗関数、または、ＳＨＡもしくはＭＤ５などの暗号学的ハッシュ関数等、一方向性関数の計算にランダムな値を用いることで出力にランダム性を持たせることができる関数を用いることとしてもよい。
　このような関数を用いない場合、ＬＳＨ値の取り得る全ての値を入力として一方向性関数の計算を実行することにより、入力と出力との対応表を作成することが可能となる。そのため、特にＬＳＨ値の取りうる値が少ない場合には、上記の対応表を容易に作成することができるため、対応表を用いて一方向性関数に入力したＬＳＨ値を容易に求めることができる。ＬＳＨ値からユーザ情報を特定することができるため、ユーザ情報の安全性の観点で問題になる。しかしながら、（１１）に例示した関数を用いることで、上記の対応表を作成することができなくなるため、一方向性関数の出力から入力を求めることが困難になる。そのため、ユーザ情報の安全性が向上される。
　（１２）上記実施の形態では、一方向性関数としてＡＥＳを用いているが、ＥｌＧａｍａｌ暗号やＲＳＡ暗号、楕円曲線暗号等の公開鍵暗号を用いてもよい。公開鍵暗号を用いる場合、鍵ペアを作成後に公開鍵を削除することで、ＡＥＳよりも一方向性を強固にすることができる。
　（１３）上記実施の形態では、一方向性関数で用いる鍵の一例としてＡＥＳの暗号鍵について言及しているが、一方向性関数を計算するために、入力データ以外に複数のデータが必要な場合は、それらをまとめて鍵としてもよい。また、鍵が複数の情報を表す場合、データ提供装置２００の鍵分散部２０３は、それらすべての情報を分散する必要はなく、一方向性関数の出力から入力に関する情報を求めることが出来ない範囲で、それらの情報の一部を平文でデータ演算装置３００、３１０、３２０へ送信してもよい。
　（１４）上記実施の形態では、秘密分散法を用いて各データを秘匿しているが、準同型暗号（非特許文献１０：Pascal Paillier、「Public-Key Cryptosystems Based on Composite Degree Residuosity Classes」（https://rd.springer.com/chapter/10.1007%2F3-540-48910-X_16））、完全準同型暗号（非特許文献１１：Jung Hee Cheon、外３名、「Hommorphic Encryption for Arithmetic of Approximate Numbers.」（https://eprint.iacr.org/2016/421.pdf）、非特許文献１２：Junfeng Fan、外１名、「Somewhat Practical Fully Homomorphic Encryption.」（https://eprint.iacr.org/2012/144.pdf））、または、ＧａｒｂｌｅｄＣｉｒｃｕｉｔ（非特許文献１３：Andrew Chi-Chih Yao、「How to generate and exchange secrets.」（https://ieeexplore.ieee.org/document/4568207?arnumber=4568207））を用いてもよい。
　（１５）上記実施の形態では、ＬＳＨのハッシュ関数としてＳｉｍＨａｓｈを用いているが、ＭｉｎＨａｓｈを用いてもよい。
　（１６）上記実施の形態において、秘匿ハッシュテーブルから選択された組に含まれる分散化特徴量と第１分散化特徴量との類似度の計算は、ユークリッド距離、ユークリッド距離の２乗値、マンハッタン距離、ハミング距離、レーベンシュタイン距離、コサイン類似度、または、ピアソンの相関係数などを用いてもよい。ここで、類似度が高いとは、ユークリッド距離、ユークリッド距離の２乗値、マンハッタン距離、ハミング距離、もしくは、レーベンシュタイン距離が小さいこと、または、コサイン類似度、もしくは、ピアソンの相関係数が高いことを意味する。
　（１７）上記の実施の形態における各装置は、具体的には、マイクロプロセッサ、ＲＯＭ（Ｒｅａｄ　Ｏｎｌｙ　Ｍｅｍｏｒｙ）、ＲＡＭ（Ｒａｎｄｏｍ　Ａｃｃｅｓｓ　Ｍｅｍｏｒｙ）、ハードディスクユニット、ディスプレイユニット、キーボード、マウスなどから構成されるコンピュータシステムである。ＲＡＭまたはハードディスクユニットには、コンピュータプログラムが記録されている。マイクロプロセッサが、上記コンピュータプログラムに従って動作することにより、各装置は、その機能を達成する。ここでコンピュータプログラムは、所定の機能を達成するために、コンピュータに対する指令を示す命令コードが複数個組み合わされて構成されたものである。
　（１８）上記の実施の形態における各装置は、構成する構成要素の一部または全部は、１個のシステムＬＳＩ（Ｌａｒｇｅ　Ｓｃａｌｅ　Ｉｎｔｅｇｒａｔｉｏｎ：大規模集積回路）から構成されていてもよい。システムＬＳＩは、複数の構成部を１個のチップ上に集積して製造された超多機能ＬＳＩであり、具体的には、マイクロプロセッサ、ＲＯＭ、ＲＡＭなどを含んで構成されるコンピュータシステムである。ＲＡＭには、コンピュータプログラムが記録されている。マイクロプロセッサが、コンピュータプログラムに従って動作することにより、システムＬＳＩは、その機能を達成する。
　また、上記の各装置を構成する構成要素の各部は、個別に１チップ化されていても良いし、一部または全てを含むように１チップ化されてもよい。
　また、ここでは、システムＬＳＩとしたが、集積度の違いにより、ＩＣ（Ｉｎｔｅｇｒａｔｅｄ　ｃｉｒｃｕｉｔ）、ＬＳＩ、スーパーＬＳＩ、ウルトラＬＳＩと呼称されることもある。また、集積回路化の手法はＬＳＩに限るものではなく、専用回路または汎用プロセッサで実現してもよい。ＬＳＩ製造後に、プログラムすることが可能なＦＰＧＡ（Ｆｉｅｌｄ　Ｐｒｏｇｒａｍｍａｂｌｅ　Ｇａｔｅ　Ａｒｒａｙ）、ＬＳＩ内部の回路セルの接続または設定を再構成可能なリコンフィギュラブル・プロセッサを利用してもよい。
　さらには、半導体技術の進歩または派生する別技術によりＬＳＩに置き換わる集積回路化の技術が登場すれば、当然、その技術を用いて機能ブロックの集積化を行ってもよい。バイオ技術の適用等が可能性としてありえる。
　（１９）上記の各装置を構成する構成要素の一部または全部は、各装置に脱着可能なＩＣカードまたは単体のモジュールから構成されているとしてもよい。ＩＣカードまたは前記モジュールは、マイクロプロセッサ、ＲＯＭ、ＲＡＭなどから構成されるコンピュータシステムである。ＩＣカードまたは前記モジュールは、上記の超多機能ＬＳＩを含んでいてもよい。マイクロプロセッサが、コンピュータプログラムに従って動作することにより、前記ＩＣカードまたは前記モジュールは、その機能を達成する。このＩＣカードまたはこのモジュールは、耐タンパ性を有してもよい。
　（２０）本開示は、上記に示す方法であるとしてもよい。また、これらの方法をコンピュータにより実現するコンピュータプログラムであるとしてもよいし、上記コンピュータプログラムからなるデジタル信号であるとしてもよい。
　また、本開示は、上記コンピュータプログラムまたは上記デジタル信号をコンピュータ読み取り可能な記録媒体、例えば、フレキシブルディスク、ハードディスク、ＣＤ－ＲＯＭ、ＭＯ（Ｍａｇｎｅｔｏ－Ｏｐｔｉｃａｌ　ｄｉｓｃ）、ＤＶＤ、ＤＶＤ－ＲＯＭ、ＤＶＤ－ＲＡＭ、ＢＤ（Ｂｌｕ－ｒａｙ（登録商標）Ｄｉｓｃ）、半導体メモリなどに記録したものとしてもよい。また、これらの記録媒体に記録されている上記デジタル信号であるとしてもよい。
　また、本開示は、上記コンピュータプログラムまたは上記デジタル信号を、電気通信回線、無線または有線通信回線、インターネットを代表とするネットワーク、データ放送等を経由して伝送するものとしてもよい。
　また、本開示は、マイクロプロセッサとメモリを備えたコンピュータシステムであって、メモリは、上記コンピュータプログラムを記録しており、マイクロプロセッサは、コンピュータプログラムに従って動作するとしてもよい。
　また、プログラムまたはデジタル信号を記録媒体に記録して移送することにより、または、プログラムもしくは上記デジタル信号を、ネットワーク等を経由して移送することにより、独立した他のコンピュータシステムにより実施するとしてもよい。
　（２１）上記実施の形態および上記変形例をそれぞれ組み合わせるとしてもよい。
　本開示は、ユーザの機微情報をデータ演算装置において平文で扱わず、プライバシを保護するシステム等に適用され得る。
　１００　ユーザ端末装置
　１０１　センシング部
　１０２　特徴量算出部
　１０３　特徴量分散部
　１０４　通信部
　２００　データ提供装置
　２０１　ＬＳＨパラメータ生成部
　２０２　鍵生成部
　２０３　鍵分散部
　２０４　閾値設定部
　２０５　通信部
　３００、３１０、３２０　データ演算装置
　３０１　分散鍵格納部
　３０２　ＬＳＨパラメータ格納部
　３０３　分散化ＬＳＨ値導出部
　３０４　閾値格納部
　３０５　分散化ハッシュ値導出部
　３０６　秘匿ハッシュテーブル格納部
　３０７　分散化認証結果導出部
　３０８　通信部
　３０９　分散化ハッシュ値復号部
　４００　認証結果利用装置
　４０１　分散化認証結果復号部
　４０２　認証結果利用部
　４０３　通信部
　５００　秘匿認証システム

Claims (17)

  1. 　入力を秘匿したまま認証処理を行う秘匿認証方法であって、
    　秘密分散法により分散された特徴量であり、ユーザに関するユーザ情報の特徴量である第１分散化特徴量と、ＬＳＨ（Ｌｏｃａｌｉｔｙ　Ｓｅｎｓｉｔｉｖｅ　Ｈａｓｈｉｎｇ）の秘密分散法により分散されたパラメータである分散化ＬＳＨパラメータとを入力として、前記入力を秘匿したまま前記ＬＳＨの処理を実行する秘匿ＬＳＨを用いて、分散されたＬＳＨ値である分散化ＬＳＨ値を導出し、
    　導出された前記分散化ＬＳＨ値と、一方向性関数の処理を実行するための鍵であって分散された鍵である分散鍵とを入力として、前記入力を秘匿のまま前記一方向性関数の処理を実行する秘匿一方向性関数を用いて、分散されたハッシュ値である分散化ハッシュ値を導出し、
    　導出された前記分散化ハッシュ値を、秘密分散法による分散が解除されたハッシュ値に復号し、
    　インデックスとしてのハッシュ値と、データ列としての分散化特徴量との複数の組が予め格納されたテーブルである秘匿ハッシュテーブルを用いて、前記複数の組のうち、復号された前記ハッシュ値と一致するハッシュ値を含む組を選択し、
    　選択された前記組に含まれる分散化特徴量と、前記第１分散化特徴量との類似度を秘匿したまま計算し、
    　計算された前記類似度に基づいて前記ユーザの認証結果を秘匿したまま導出し、
    　導出された前記認証結果を出力する、
    　秘匿認証方法。
  2. 　前記ユーザの前記認証結果の導出において、
    　選択された前記組に含まれる前記分散化特徴量のうち、前記第１分散化特徴量と最も類似度の高い分散化特徴量を第２分散化特徴量として抽出し、
    　抽出された前記第２分散化特徴量と前記第１分散化特徴量との類似度が閾値よりも高いか否かを判定し、
    　前記類似度が前記閾値よりも高いと判定された場合、前記ユーザの認証が成功したことを表す分散化された数値を前記認証結果として出力し、
    　前記類似度が前記閾値以下であると判定された場合、前記ユーザの認証が失敗したことを表す分散化された数値を前記認証結果として出力する、
    　請求項１に記載の秘匿認証方法。
  3. 　前記特徴量は、前記ユーザの身体的特徴に関する身体的特徴量、前記ユーザの行動的特徴に関する行動的特徴量、および、前記ユーザが保有している保有物の特徴に関する保有物特徴量のいずれかであり、
    　前記身体的特徴量は、網膜画像、虹彩画像、指紋画像、静脈画像、音声情報、耳の形状情報、ＤＮＡ（ｄｅｏｘｙｒｉｂｏｎｕｃｌｅｉｃ　ａｃｉｄ）情報、および、手のひらの画像のうちの少なくとも１つの情報の特徴量を含み、
    　前記行動的特徴量は、筆跡、キーストローク、歩容、および、行動履歴のうちの少なくとも１つの情報の特徴量を含み、
    　前記保有物特徴量は、前記ユーザが保有している文書情報、記憶、および、所有物のうちの少なくとも１つの情報の特徴量を含む
    　請求項１または２に記載の秘匿認証方法。
  4. 　前記第１分散化特徴量および前記分散化特徴量は、それぞれ、分散された複数種類の特徴量を含み、
    　選択された前記組に含まれる分散化特徴量と、前記第１分散化特徴量との前記類似度の計算において、前記複数種類の特徴量のそれぞれの類似度を計算する、
    　請求項１～３の何れか１項に記載の秘匿認証方法。
  5. 　前記分散化ハッシュ値は、ランダム性を有する、
    　請求項１～４の何れか１項に記載の秘匿認証方法。
  6. 　前記データ列は、さらに、分散されたユーザＩＤである分散化ユーザＩＤを含む、
    　請求項１～５の何れか１項に記載の秘匿認証方法。
  7. 　前記認証結果の出力において、導出された前記認証結果と、選択された前記組の前記データ列に含まれる前記分散化特徴量および前記ユーザＩＤの少なくとも１つと、を出力する、
    　請求項６に記載の秘匿認証方法。
  8. 　前記ユーザのユーザ端末装置は、センシングによって得られた前記ユーザ情報から前記特徴量を算出し、算出された前記特徴量を秘密分散法により分散することにより、前記第１分散化特徴量を導出する、
    　請求項１～７の何れか１項に記載の秘匿認証方法。
  9. 　前記ユーザのユーザ端末装置は、センシングによって得られた前記ユーザ情報を情報が漏洩しない信頼できるサーバに送信し、
    　前記サーバは、前記ユーザ情報から前記特徴量を導出し、前記特徴量を秘密分散法により分散することにより前記第１分散化特徴量を導出する、
    　請求項１～７の何れか１項に記載の秘匿認証方法。
  10. 　前記第１分散化特徴量は、前記ユーザの認証結果を導出する演算装置で導出され、
    　前記ユーザのユーザ端末装置は、センシングによって得られた前記ユーザ情報を秘密分散法により分散した分散化ユーザ情報を前記演算装置に送信し、
    　前記演算装置は、前記分散化ユーザ情報から前記第１分散化特徴量を導出する、
    　請求項１～７の何れか１項に記載の秘匿認証方法。
  11. 　前記分散化ＬＳＨパラメータは、前記ユーザの認証結果を導出する演算装置に送信され、
    　前記演算装置は、前記第１分散化特徴量と、前記分散化ＬＳＨパラメータとを入力として、前記秘匿ＬＳＨを用いて前記分散化ＬＳＨ値を導出する、
    　請求項１～１０の何れか１項に記載の秘匿認証方法。
  12. 　前記ＬＳＨは、ＳｉｍＨａｓｈである、
    　請求項１～１１の何れか１項に記載の秘匿認証方法。
  13. 　前記ＬＳＨは、ＭｉｎＨａｓｈである、
    　請求項１～１１の何れか１項に記載の秘匿認証方法。
  14. 　前記一方向性関数は、ＡＥＳ（Advanced Encryption Standard）である、
    　請求項１～１３の何れか１項に記載の秘匿認証方法。
  15. 　前記一方向性関数は、ＳＨＡ（Ｓｅｃｕｒｅ　Ｈａｓｈ　Ａｌｇｏｒｉｔｈｍ）またはＭＤ５（Ｍｅｓｓａｇｅ　Ｄｉｇｅｓｔ　５）である、
    　請求項１～１３の何れか１項に記載の秘匿認証方法。
  16. 　前記一方向性関数は、ＥｌＧａｍａｌ暗号またはＲＳＡ（Ｒｉｖｅｓｔ－Ｓｈａｍｉｒ－Ａｄｌｅｍａｎ）暗号または楕円曲線暗号である、
    　請求項１～１３の何れか１項に記載の秘匿認証方法。
  17. 　入力を秘匿したまま認証処理を行う秘匿認証システムであって、
    　暗号化され、かつ、秘密分散法により分散された特徴量であり、ユーザに関するユーザ情報の特徴量である第１分散化特徴量と、ＬＳＨの暗号化されたパラメータである暗号化ＬＳＨパラメータとを入力として、前記入力を秘匿したまま前記ＬＳＨの処理を実行する秘匿ＬＳＨを用いて、暗号化され、かつ、分散されたＬＳＨ値である分散化ＬＳＨ値を導出する分散化ＬＳＨ値導出部と、
    　前記分散化ＬＳＨ値導出部により導出された前記分散化ＬＳＨ値と、一方向性関数の処理を実行するための鍵であって暗号化され、かつ、分散された鍵である分散鍵とを入力として、前記入力を秘匿のまま一方向性関数の処理を実行する秘匿一方向性関数を用いて暗号化され、かつ、分散されたハッシュ値である分散化ハッシュ値を導出する分散化ハッシュ値導出部と、
    　前記分散化ハッシュ値導出部により導出された前記分散化ハッシュ値を、秘密分散法による分散が解除されたハッシュ値に復号する復号部と、
    　インデックスとしてのハッシュ値と、データ列としての分散化特徴量との複数の組が予め格納されたテーブルである秘匿ハッシュテーブルを格納する秘匿ハッシュテーブル格納部と、
    　前記秘匿ハッシュテーブルを用いて、前記複数の組のうち、復号された前記ハッシュ値と一致するハッシュ値を含む組を選択し、選択された前記組に含まれる分散化特徴量と、前記第１分散化特徴量との類似度を秘匿したまま計算し、計算された前記類似度に基づいて前記ユーザの認証結果を秘匿したまま導出する分散化認証結果導出部と、
    　前記分散化認証結果導出部により導出された前記認証結果を出力する出力部と、
    　を備える、
    　秘匿認証システム。
PCT/JP2020/037925 2019-10-11 2020-10-06 秘匿認証方法および秘匿認証システム Ceased WO2021070838A1 (ja)

Priority Applications (3)

Application Number Priority Date Filing Date Title
JP2021551675A JP7524205B2 (ja) 2019-10-11 2020-10-06 秘匿認証方法および秘匿認証システム
EP20873984.7A EP4044157A4 (en) 2019-10-11 2020-10-06 SECRET AUTHENTICATION METHOD AND SECRET AUTHENTICATION SYSTEM
US17/546,606 US11995211B2 (en) 2019-10-11 2021-12-09 Secure authentication method and secure authentication system

Applications Claiming Priority (2)

Application Number Priority Date Filing Date Title
JP2019-187888 2019-10-11
JP2019187888 2019-10-11

Related Child Applications (1)

Application Number Title Priority Date Filing Date
US17/546,606 Continuation US11995211B2 (en) 2019-10-11 2021-12-09 Secure authentication method and secure authentication system

Publications (1)

Publication Number Publication Date
WO2021070838A1 true WO2021070838A1 (ja) 2021-04-15

Family

ID=75437419

Family Applications (1)

Application Number Title Priority Date Filing Date
PCT/JP2020/037925 Ceased WO2021070838A1 (ja) 2019-10-11 2020-10-06 秘匿認証方法および秘匿認証システム

Country Status (4)

Country Link
US (1) US11995211B2 (ja)
EP (1) EP4044157A4 (ja)
JP (1) JP7524205B2 (ja)
WO (1) WO2021070838A1 (ja)

Cited By (2)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
JP2024060344A (ja) * 2022-10-19 2024-05-02 ソフトバンク株式会社 認証システム及び認証方法
JP7672469B1 (ja) 2023-11-07 2025-05-07 ソフトバンク株式会社 システム、通信装置、プログラム、及び情報処理方法

Families Citing this family (2)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
JP2023504569A (ja) * 2019-12-09 2023-02-03 バッジ インコーポレイテッド プライバシ保存バイオメトリック認証
US12476943B2 (en) * 2022-11-23 2025-11-18 International Business Machines Corporation Recommendation engine using fully homomorphic encryption

Citations (3)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
US20100281269A1 (en) * 2007-12-21 2010-11-04 Morpho Identification Based on Encrypted Biometric Data
JP2016071639A (ja) * 2014-09-30 2016-05-09 日本電信電話株式会社 監視情報共有システム、照合装置、監視装置及びプログラム
JP2019121344A (ja) * 2017-12-28 2019-07-22 株式会社ノルミー 個人認証方法及び個人認証装置

Family Cites Families (10)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
US8094821B2 (en) * 2004-08-06 2012-01-10 Qualcomm Incorporated Key generation in a communication system
US7730309B2 (en) * 2005-07-27 2010-06-01 Zimmermann Philip R Method and system for key management in voice over internet protocol
US20080209227A1 (en) * 2007-02-28 2008-08-28 Microsoft Corporation User Authentication Via Biometric Hashing
WO2010010430A2 (en) * 2008-07-25 2010-01-28 Lee Kok-Wah Methods and systems to create big memorizable secrets and their applications in information engineering
US8839357B2 (en) * 2010-12-22 2014-09-16 Canon U.S.A., Inc. Method, system, and computer-readable storage medium for authenticating a computing device
US9678976B2 (en) * 2014-07-21 2017-06-13 Red Hat, Inc. Distributed deduplication using locality sensitive hashing
US9935948B2 (en) * 2015-09-18 2018-04-03 Case Wallet, Inc. Biometric data hashing, verification and security
JP6497747B2 (ja) * 2016-04-19 2019-04-10 日本電信電話株式会社 鍵交換方法、鍵交換システム
US9774578B1 (en) * 2016-05-23 2017-09-26 Accenture Global Solutions Limited Distributed key secret for rewritable blockchain
CN114521319B (zh) * 2019-09-26 2023-12-05 维萨国际服务协会 具有均匀秘密的基于格的签名

Patent Citations (3)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
US20100281269A1 (en) * 2007-12-21 2010-11-04 Morpho Identification Based on Encrypted Biometric Data
JP2016071639A (ja) * 2014-09-30 2016-05-09 日本電信電話株式会社 監視情報共有システム、照合装置、監視装置及びプログラム
JP2019121344A (ja) * 2017-12-28 2019-07-22 株式会社ノルミー 個人認証方法及び個人認証装置

Non-Patent Citations (14)

* Cited by examiner, † Cited by third party
Title
ADI SHAMIR, HOW TO SHARE A SECRET, Retrieved from the Internet <URL:http://cs.jhu.edu/-sdoshi/crypto/papers/shamirturing.pdf>
ALEXANDER J. TITUS ET AL., SIG-DB: LEVERAGING HOMOMORPHIC ENCRYPTION TO SECURELY INTERROGATE PRIVATELY HELD GENOMIC DATABASES, Retrieved from the Internet <URL:https://arxiv.org/abs/1612.01835>
ANDREW CHI-CHIH YAO, HOW TO GENERATE AND EXCHANGE SECRETS, Retrieved from the Internet <URL:https://ieeexplore.ieee.org/document/4568207?arnumber=4568207>
CHAO NING ET AL., CONSTANT-ROUNDS, LINEAR MULTIPARTY COMPUTATION FOR EXPONENTIATION AND MODULO REDUCTION WITH PERFECT SECURITY, Retrieved from the Internet <URL:https://eprint.iacr.org/2011/069.pdf>
JUNFENG FAN ET AL., SOMEWHAT PRACTICAL FULLY HOMOMORPHIC ENCRYPTION, Retrieved from the Internet <URL:https://eprint.iacr.org/2012/144.pdf>
JUNG HEE CHEON ET AL., HOMMORPHIC ENCRYPTION FOR ARITHMETIC OF APPROXIMATE NUMBERS, Retrieved from the Internet <URL:https://eprint.iacr.org/2016/421.pdf>
M. SADEGH RIAZI ET AL., SUB-LINEAR PRIVACY-PRESERVING NEAR-NEIGHBOR SEARCH WITH UNTRUSTED SERVER ON LARGE-SCALE DATASETS, Retrieved from the Internet <URL:https://arxiv.org/abs/1612.01835>
MOSES S. CHARIKAR, SIMILARITY ESTIMATION TECHNIQUES FROM ROUNDING ALGORITHMS, Retrieved from the Internet <URL:https://www.cs.princeton.edu/courses/archive/spring04/cos598B/bib/CharikarEstim.pdf>
NISHIDA, NAOHISA; OBA, TATSUMI; UNAGAMI, YUJI; TERUYA, TADANORI; ATTRAPADUNG, NUTTAPONG; HANAOKA, GOICHIRO: "Face Recognition Using Secret Face Image", PROCEEDINGS OF THE 2019 COMPUTER SECURITY SYMPOSIUM, 21-24 OCTOBER, 14 October 2019 (2019-10-14) - 24 October 2019 (2019-10-24), JP, pages 1250 - 1256, XP009531518 *
PASCAL PAILLIER, PUBLIC-KEY CRYPTOSYSTEMS BASED ON COMPOSITE DEGREE RESIDUOSITY CLASSES, Retrieved from the Internet <URL:https://rd.springer.com/chapter/10.1007%2F3-540-48910-X_16>
PING LI ET AL., B-BIT MINWISE HASHING, Retrieved from the Internet <URL:https://arxiv.org/pdf/0910.3349.pdf>
PIOTR INDYK ET AL., APPROXIMATE NEAREST NEIGHBORS: TOWARDS REMOVING THE CURSE OF DIMENSIONALITY, Retrieved from the Internet <URL:https://www.cs.princeton.edu/courses/archive/spr04/cos598B/bib/IndykM-curse.pdf>
See also references of EP4044157A4
TAKASHI NISHIDE ET AL., MULTIPARTY COMPUTATION FOR INTERVAL, EQUALITY, AND COMPARISON WITHOUT BITDECOMPOSITION PROTOCOL, Retrieved from the Internet <URL:https://www.iacr.org/archive/pkc2007/44500343/44500343.pdf>

Cited By (4)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
JP2024060344A (ja) * 2022-10-19 2024-05-02 ソフトバンク株式会社 認証システム及び認証方法
JP7502390B2 (ja) 2022-10-19 2024-06-18 ソフトバンク株式会社 認証システム及び認証方法
JP7672469B1 (ja) 2023-11-07 2025-05-07 ソフトバンク株式会社 システム、通信装置、プログラム、及び情報処理方法
JP2025077896A (ja) * 2023-11-07 2025-05-19 ソフトバンク株式会社 システム、通信装置、プログラム、及び情報処理方法

Also Published As

Publication number Publication date
EP4044157A1 (en) 2022-08-17
US11995211B2 (en) 2024-05-28
JP7524205B2 (ja) 2024-07-29
JPWO2021070838A1 (ja) 2021-04-15
US20220100897A1 (en) 2022-03-31
EP4044157A4 (en) 2022-11-30

Similar Documents

Publication Publication Date Title
CN111639361B (zh) 一种区块链密钥管理方法、多人共同签名方法及电子装置
Wei et al. Privacy-preserving implicit authentication protocol using cosine similarity for Internet of Things
Wei et al. An intelligent terminal based privacy-preserving multi-modal implicit authentication protocol for internet of connected vehicles
Choi et al. Security improvement on biometric based authentication scheme for wireless sensor networks using fuzzy extraction
JP6037366B2 (ja) 暗号化したものに対応するユーザーを認証する方法及びバイオメトリックデータに対応するユーザーを認証するシステム
JP5300983B2 (ja) データ処理装置
Al-Saggaf et al. Lightweight two-factor-based user authentication protocol for iot-enabled healthcare ecosystem in quantum computing
EP1815637B1 (en) Securely computing a similarity measure
US11063941B2 (en) Authentication system, authentication method, and program
CN103124269B (zh) 云环境下基于动态口令与生物特征的双向身份认证方法
JP7524205B2 (ja) 秘匿認証方法および秘匿認証システム
JP5586795B2 (ja) データ処理装置及びデータ処理方法及びプログラム
CN114065169B (zh) 一种隐私保护生物认证方法和装置、电子设备
JP2014126865A (ja) 暗号処理装置および方法
CN103380591A (zh) 类似度计算系统、类似度计算装置、计算机程序以及类似度计算方法
KR102008101B1 (ko) 함수 암호를 이용한 안전한 바이오 인증 방법
Kuznetsov et al. Deep learning-based biometric cryptographic key generation with post-quantum security
JP7323004B2 (ja) データ抽出システム、データ抽出方法、登録装置及びプログラム
US9715595B2 (en) Methods, systems, and devices for securing distributed storage
Zhang et al. Two-factor remote authentication protocol with user anonymity based on elliptic curve cryptography
Ye et al. Anonymous biometric access control
Sarkar et al. A multi-instance cancelable fingerprint biometric based secure session key agreement protocol employing elliptic curve cryptography and a double hash function
Yue et al. A face authentication-based searchable encryption scheme for mobile device: X. Yue et al.
US11831759B1 (en) Optimized authentication system for a multiuser device
Liu et al. A biometric‐based implicit authentication protocol with privacy protection for ubiquitous communication environments

Legal Events

Date Code Title Description
121 Ep: the epo has been informed by wipo that ep was designated in this application

Ref document number: 20873984

Country of ref document: EP

Kind code of ref document: A1

ENP Entry into the national phase

Ref document number: 2021551675

Country of ref document: JP

Kind code of ref document: A

NENP Non-entry into the national phase

Ref country code: DE

ENP Entry into the national phase

Ref document number: 2020873984

Country of ref document: EP

Effective date: 20220511