JP2017201783A - Relation encryption of approximation relation based on identification of parity value under presence of noise - Google Patents

Abstract

PROBLEM TO BE SOLVED: To provide a method for biometric authentication using a relation linear encryption system and a non-temporary computer readable medium.SOLUTION: A method includes the steps of: receiving first and second linear cipher texts representing first and second biometric templates encrypted by using a relation linear encryption system (linear system) on the basis of learning of parity having noise; discovering linear relation between the first and second linear cipher texts; receiving first and second approximation hash values representing the first and second biometric templates encrypted by using a relation approximation hash system (approximation system) on the basis of the linear system and an error correction code; detecting approximation between the first and second approximation hash values at the point of view of Hamming distance; and verifying the sameness of a user on the basis of the approximation and the linear relation.SELECTED DRAWING: Figure 4

Description

[Related applications]
This application is a continuation-in-part of U.S. Patent Application No. 14 / 287,051 filed on May 25, 2014, and U.S. Patent Application No. 14 / 797,025 filed on Jul. 10, 2015. Partial continuation application.

[Technical field]
The embodiments discussed herein relate to relational encryption based on learning parity with noise (LPN) in the presence of noise.

  The form of user authentication may include biometric authentication. Biometric authentication typically includes measuring a user's biometric features that are unique to the user. The measured biometric features, or representations thereof, are then used as a basis for authenticating the identity of the user. The biometric features may include a user's fingerprint, iris, vein, DAN (deoxyribonucleic acid) section, and the like. Biometric authentication can have the advantage that it is not necessary to store a password and can authenticate the user. Since biometric features are invariant, privacy is important in biometric authentication systems. Furthermore, biometric data is very uneven.

  The subject matter claimed herein is not limited to embodiments that solve the above disadvantages or that operate only in environments such as those described above. Rather, this background is only provided to illustrate one example technology area where the embodiments described herein can be implemented.

  According to one aspect of an embodiment, the method includes receiving a first linear ciphertext. The first linear ciphertext may represent a first biometric template that is encrypted using a relational linear encryption scheme. The relational linear encryption scheme may be based on the learning parity with noise (LPN) in the presence of noise. The method may include receiving a second linear ciphertext. The second linear ciphertext may represent a second biometric template that is encrypted using a relational linear encryption scheme. The method may include finding a linear relationship between the first linear ciphertext and the second linear ciphertext using the linear relationship secret key. The method may include receiving a first approximate hash value. The first approximate hash value may represent a first biometric template that is encrypted using a relational approximate hash scheme. The relational approximate hashing scheme may be based on a relational linear encryption scheme and an error correction code (ECC). The method may include receiving a second approximate hash value. The second approximate hash value may represent a second biometric template that is encrypted using a relational approximate encryption scheme. The method may include detecting an approximation between the first approximate hash value and the second approximate hash value in terms of Hamming distance. The method may include authenticating user identity based on the approximation and linear relationship.

  The objects and advantages of the embodiments will be understood and at least achieved using the elements, features and combinations particularly pointed out in the claims.

  It is understood that both the foregoing general description and the following detailed description are exemplary and explanatory only and do not limit the scope of the invention.

Exemplary embodiments are described and explained with additional specificity and detail through the use of the accompanying drawings in which:
FIG. 6 is a block diagram of an exemplary operating environment in which some embodiments may be implemented. 1 is a block diagram of an exemplary biometric environment. 1 is a block diagram of a computing system configured for relationship encryption. FIG. 3 is a flow diagram of an exemplary method for biometric authentication. All figures are constructed in accordance with at least one embodiment described herein.

  The challenge of biometric authentication can be that the user cannot change the biometric feature used as the basis for authentication. For example, a user may register a biometric template that includes biometric data representing one or more unique features of the user, such as the user's fingerprint or the user's iris pattern. If the biometric template is compromised, the user cannot change the unique features represented by the biometric template. Thus, once at risk, another biometric template may be registered, or another biometric feature biometric template may be registered. For at least this reason, biometric authentication systems can enjoy the benefits of strong privacy guarantees.

  US patent application Ser. No. 14 / 287,051, filed May 25, 2014, which is incorporated herein by reference in its entirety, describes a cryptographic primitive called relational encryption. Relational encryption is a semantically secure public key encryption scheme that has only public key knowledge.

  Further, in relational encryption, a semi-trusted entity may be provided with a relational key. Using a relationship key, a semi-trusted entity can discover one or more relationships between ciphertexts, but cannot decrypt and recover the plaintext vector from which the ciphertext was generated. Relational encryption was developed in Application No. 14 / 287,051 to find a linear relationship between a bit vector and a p-ary vector. With relational encryption, relational encryption schemes can be used to detect approximations between ciphertexts in terms of Hamming distance. Relational encryption provides a strong privacy guarantee for biometric templates for biometric authentication while allowing semi-trusted servers to perform authentication.

  Application No. 14 / 287,051's relational encryption may be based on the assumption that the plaintext vector is substantially uniformly random. In fact, and for certain biometric information, this assumption that the plaintext vector is substantially uniformly random cannot be maintained. The relational encryption of application number 14 / 287,051 may be based on linear relational hash and error correction code.

  US patent application Ser. No. 14 / 797,025, filed Mar. 22, 2016, which is incorporated herein by reference in its entirety, describes an extension of relational encryption. Thus, the extension is secure beyond the further diversity and further practical distribution of biometric information. For example, the extension of relational encryption is based on the assumption that the plaintext vector has a high min entropy. The extension of relational encryption in application number 14 / 797,025 may be based on linear relational hashes, error correction codes, and extractors.

  Some embodiments described in this disclosure include another exemplary relationship encryption. The relational encryption scheme described herein is based on a cryptographically difficult learning parity with noise (LPN) problem in the presence of noise. The relational encryption scheme described in this disclosure is more secure than heterogeneous biometric data with high unpredictability. The relational encryption scheme described herein may be more efficient than the relational encryption described in application number 14 / 797,025 and application number 14 / 287,051. The relational encryption scheme described herein may be based on linear relational hashes and error correction codes, and may be based on the assumption that the plaintext vector has a high min entropy. Embodiments of the present invention will be described below with reference to the accompanying drawings.

  FIG. 1 shows a block diagram of an exemplary operating environment 100 arranged in accordance with at least one embodiment described herein. In the operating environment 100, relational encryption may be performed. Relationship encryption may include cryptographic primitives that allow the first entity 152 to determine one or more relationships between two or more ciphertexts provided by the second entity 150. In particular, relationship encryption causes the first entity 152 to find a linear relationship between two or more ciphertexts and to detect an approximation between the two or more ciphertexts. Furthermore, the relationship encryption causes the first entity 152 to restore the plaintext from the ciphertext or to construct an illegal ciphertext having a specific relationship with a specific genuine ciphertext.

  Relational encryption may be implemented in various environments. For example, relational encryption may be performed in a social environment where individuals want to keep their location private, but semi-reliable services may allow for the close detection of locations. Further, relational encryption may be performed in an image comparison environment. An approximation may be detected between images from the database to determine the similarity between the images. Image privacy may be maintained. The user may search for an image using relational encryption without touching the image in the database. Furthermore, relational encryption may be performed in a private data storage environment. The user may encrypt the data and communicate the encrypted data to the database. Analysis (eg, storage, clustering, etc.) can be performed on the encrypted data without the risk of the encrypted data being decrypted.

  For example, the user device 102 associated with the second entity 150 may receive one or more plaintext vectors 142. The plaintext vector 142 may comprise any data set such as a biometric template, location information, etc. The second entity 150 may communicate the first ciphertext or hash value including the encrypted version of the plaintext vector 142 to the authentication server 140 of the first entity 152. Later, the user device 102 may receive another plaintext vector 142. A second ciphertext that includes an encrypted version of the second plaintext vector 142 may be communicated to the authentication server 140 of the first entity 152. The first entity 152 may discover whether there is a linear relationship between the first ciphertext and the second ciphertext, and may detect an approximation between the first ciphertext and the second ciphertext. good. In some embodiments, the approximation may be in terms of a Hamming distance.

  However, relational encryption does not allow the first entity 152 to construct the plaintext vector 142 from the first and second ciphertext. Furthermore, relational encryption does not allow the first entity 152 to construct a third ciphertext that has a specific linear relationship and / or a specific approximation with the first ciphertext and / or the second ciphertext. FIG. 1 shows an embodiment having two plaintext vectors 142 and thus two ciphertexts. In some embodiments, more than two plaintext vectors 142, and thus more than two ciphertexts, may be communicated to the authentication server 140 included in the operating environment 100.

  Relational encryption may have one or more relational keys. The relationship key may be similar to the public and / or signing key and may be provided to or generated by the first entity 152. The relationship key may allow determination of the relationship between the ciphertexts but does not allow decryption of the ciphertext or restoration of the plaintext vector 142. Furthermore, the relationship key does not allow the construction of a ciphertext that has a specific relationship with a specific ciphertext.

In some embodiments, relationship encryption may be defined according to a relationship hashing scheme for relationships having a tuple of algorithms. The algorithm may include a key generation algorithm, a first encryption algorithm, a first decryption algorithm, a second encryption algorithm, a second decryption algorithm, and a verification algorithm. The relationship may be defined as a subset of three sets. Further, the relationships and algorithms may satisfy one or more accuracy conditions. For example, the relationship may satisfy the following exemplary accuracy condition:
R⊆XxYxZ
(Pkx, skx, pky, sky , skR) ← KeyGen (1 λ)
cx ← EncX (pkx, x)
cy ← EncY (pky, y)
b ← Verify (skR, cx, cy, z)
b≈R (x, y, z)
Under accuracy conditions, R represents the relationship. The operator ⊆ represents a subset operator. Parameters X, Y, and Z represent a set. The parameter x represents the first plaintext vector in the plaintext vector 142. The parameter y represents the second plaintext vector in the plaintext vector 142. KeyGen represents a key generation algorithm. EncX represents the first encryption algorithm. EncY represents the second encryption algorithm. Verify represents a verification algorithm. The operator ← represents an output operator. The parameter pkx represents the first public key. The parameter pky represents the second public key. The parameter skx represents the first secret key. The parameter sky represents the second secret key. The parameter skR represents the related secret key. The parameter cx represents the first ciphertext. The parameter cy represents the second ciphertext. The parameter b represents the output by the verification algorithm. The parameter λ represents a security parameter. The parameter z represents a specific value that can be selected by the verification entity. The operator ≒ represents a congruent operator. Under accuracy conditions, the output from the verification algorithm is consistent with a relationship with an overwhelming probability.

  The relational encryption scheme is secure in the sense that the relational key does not allow the construction of a ciphertext having a particular relationship with the particular ciphertext and does not allow the plaintext vector 142A to be restored from the particular ciphertext. possible. For example, a relational encryption scheme may be secure if the following equation is maintained:

1) An algorithm for performing KeyGen (1 ^λ ) is Kx (1 ^λ ), and an output (pkx, skx, pky, sky, skR) and an output (pkx, skx) are taken in. As a result, (Kx, EncX, DecX) is IND-CPA secure.

2) The algorithm for performing KeyGen (1 ^λ ) is Ky (1 ^λ ), and the output (pkx, skx, pky, sky, skR) and the output (pkx, skx) are taken in. As a result, (Ky, EncY, DecY) is IND-CPA secure.

3) An algorithm for performing KeyGen (1 ^λ ) is KR (1 ^λ ), and an output (pkx, skx, pky, sky, skR) and an output (pkx, skx, skR) are taken in. As a result, EncX (pkx, ·) and EncY (pky, ·) are unidirectional functions when skR is known.

  In the above formula, pkx, skx, pky, sky, skR, KeyGen, EncX () and EncY () are as described above. DecX represents the first decryption algorithm. DecY represents the second decryption algorithm. Kx (), Ky (), and KR () are as described in the above formula. The symbol “•” indicates an arbitrary value. The term “IND-CPA” stands for indistinguishability under chosen-plaintext attack. In some other embodiments, (Ky, EncY, DecY) and / or (Kx, EncX, DecX) is an IND-CCA (for example, IND-CCA1 or IND-CCA2) or It may be secure according to another computational security metric, such as any other suitable security metric.

Further, in some embodiments, the relational encryption scheme may comprise a relational linear encryption scheme. The relational linear encryption scheme may define the relation according to the following exemplary linear relational expression.
R = {(x, y, z) | x + y = z∧x, y, zεF ⁿ _p }
In the linear relational expression, R, x, y, and z are as described above. The operator ε represents a membership operator. The operator | represents an operator that “satisfies the condition of” (such that). The operator ∧ represents a logical combination operator. The parameter F represents a field. The subscript n usually represents the body dimension. The body dimension may have the length of one or more of the keys as discussed elsewhere herein. The subscript p represents the base number of the field (base-number). For example, at F ¹⁰ ₃ , the field has 10 dimensions and 3 basic numbers. A base number of 3 indicates that each element of the body is 0, 1, or 2.

Further, in some embodiments, the relational encryption scheme may include a relational approximate encryption scheme that defines a relationship according to the following exemplary approximation:
R _δ = {(x, y) | dist (x, y) ≦ δ∧x, y∈F ^k _p }
In the approximate expression, R, x, ∧, ∈, and y are as described above. The parameter δ represents the distance that defines the closeness. The operator dist represents the Hamming distance. As in the linear relationship, the parameter F represents the body. However, the body in the approximate expression may have a different dimension than the body in the linear relational expression. The field dimension in the approximation may be related to the linear error correction code.

  The relational encryption scheme discussed herein may be implemented in the operating environment 100 of FIG. The relationship encryption scheme allows the second entity 150 to communicate the encryption information to the first entity 152, where the first entity 152 discovers and / or encrypts the linear relationship between the encryption information. It may be possible to determine an approximation between the information.

  The operating environment 100 may include a user device 102 associated with the second entity 150 and an authentication server 140 associated with the first entity 152. User device 102 and authentication server 140 may be implemented in operating environment 100 to perform relationship encryption. The user device 102 and the authentication server 140 may be configured to communicate via the network 107. For example, one or more ciphertexts, authentication messages, and other data and information related to related encryption may be communicated between the user device 102 and the authentication server 140 via the network 107. Each of the user device 102, the authentication server 140, and the network 107 is briefly described below.

  The network 107 may be wired or wireless. The network 107 may have a number of configurations including a star configuration, a token ring configuration, or other configurations. Further, the network 107 may include a local area network (LAN), a wide area network (WAN) (eg, the Internet), and / or other interconnected data paths over which multiple devices can communicate. In some examples, the network 107 may comprise a peer to peer network. Network 107 may be coupled to or include a portion of a communication network that transmits data over a variety of different communication protocols. In some examples, the network 107 is a Bluetooth® communication network or SMS (short messaging service), MMS (multimedia messaging service), HTTP (hypertext transfer protocol), Wi-Fi, direct data connection, WAP (wireless). application protocol), a cellular communication network for sending and receiving data including via e-mail and the like.

  User device 102 is a processor, memory, and communication capability that enables the generation and communication of information and / or data (eg, ciphertext, keys, plaintext vector 142, etc.) related to related encryption over network 107 Any computing device may be included. Some examples of user equipment 102 are cell phones, scanning devices, smartphones, tablet computers, laptop computers, desktop computers, set-top boxes, or connected devices (eg, smart watches, smart glasses, smart pedometers, or any Other connected devices).

  The user device 102 may have a relationship encryption module 110. The relationship encryption module 110 may be configured to receive the plaintext vector 142 and perform one or more steps associated with encryption of the plaintext vector 142. For example, the relationship encryption module 110 may be configured to generate one or more keys used in encrypting the plaintext vector 142. Further, the relationship encryption module 110 may generate one or more ciphertexts based on the plaintext vector 142. The ciphertext generated by the relationship encryption module 110 may be communicated to the authentication server 140. Based on the relationship between the ciphertexts (eg, linear and approximate), the identity of the second entity 150 may or may not be authenticated.

  In particular, in the embodiment of FIG. 1, the relationship encryption module 110 may include a setting module 144, a linear encryption module 112, and an approximate encryption module 114.

  The configuration module 144 may be configured to perform one or more steps to generate one or more keys and / or one or more algorithms (eg, encryption algorithm, decryption algorithm, and verification algorithm). The key may be used in the relationship encryption module 110 and / or the relationship authentication module 108 of the authentication server 140. Some examples of keys that may be generated by the configuration module 144 may include a linear public key, a linear secret key, a relational linear key, an approximate public key, an approximate secret key, and an approximate relation secret key. Some additional details of the key are provided elsewhere in this disclosure.

  The key may be communicated via the network 107. For example, in the illustrated embodiment, the setting module 144 may be included in the user device 102. The configuration module 144 may generate a key and communicate some part of it to the authentication server 140. The authentication server 140 may or may not authenticate the identity of the second entity 150 using a key. For example, authentication may be based on approximations and linear relationships between ciphertexts in plaintext vector 142. In the above and other embodiments, the authentication server 140 may find a linear relationship between the linear ciphertexts of the plaintext vector 142 using the linear relationship secret key. Furthermore, the authentication server 140 may detect the approximation between the ciphertexts of the plaintext vector 142 using the approximate relationship secret key.

  Another portion of the key generated by the configuration module 144 may be used by the linear encryption module 112 and / or the approximate encryption module 114. For example, the linear encryption module 112 may generate a linear ciphertext of the plaintext vector 142 using a linear public key and a linear secret key. The linear public key and the linear secret key may be based on the IND_CCA secure public key encryption scheme with the implementation of the LPN based process.

  Additionally or alternatively, the approximate encryption module 114 may generate a hash value for the plaintext vector 142 based on one or more keys generated by the configuration module 144. For example, the hash value of the plaintext vector 142 may be generated based on a CPA (chosen-plaintext attack) public key, a CPA private key, a linear public key, a linear private key, or some combination thereof.

  In some embodiments, the configuration module 144 may be remotely located. For example, the setting module 144 may be disposed on a remote server (not shown). In the above and other embodiments, the configuration module 144 may generate a key that is communicated to the user device 102 and / or the authentication server 140.

  The linear encryption module 112 is configured to perform one or more steps associated with encrypting the plaintext vector 142 and / or decrypting the linear ciphertext to construct a linear ciphertext. Good. The linear encryption module 112 may perform encryption and decryption processes according to a relational linear encryption scheme. Relational linear encryption schemes may be based on LPN (learning parity with noise) and / or linear relation hashes that implement LPN features.

  The relational linear encryption scheme implemented by the linear encryption module 112 may generate one or more linear ciphertexts. For example, the linear encryption module 112 generates a first linear ciphertext based on the first plaintext vector of the plaintext vector 142 and a second linear ciphertext based on the second plaintext vector of the plaintext vector 142. Good. The linear ciphertext may be communicated to the authentication server 140. From the linear ciphertext, the authentication server 140 may find a linear relationship between the plaintext vectors 142 using the linear relationship secret key.

  The approximate encryption module 114 may be configured to perform one or more steps associated with encrypting the plaintext vector 142 to construct an approximate hash value. The approximate encryption module 114 may perform the process based on a relational approximate hash method. The relational approximate hashing scheme may be further based on a relational linear encryption scheme and an error correction code (ECC).

  For example, the approximate encryption module 114 generates a first approximate hash value based on the first plaintext vector of the plaintext vector 142 and a second approximate hash value based on the second plaintext vector of the plaintext vector 142. Good. The approximate hash value may be communicated to the authentication server 140. The authentication server 140 may detect the approximation between the approximate hash values in terms of the Hamming distance using the approximate relationship secret key.

  The authentication server 140 may include a computing device based on a hardware server or another processor configured to function as a server. The authentication server 140 may include a relationship authentication module 108 and a memory 122. The memory 122 may be substantially the same as the memory 308 described later. Some additional details of the memory 122 are provided elsewhere herein.

  The relationship authentication module 108 may be configured to receive linear ciphertext and / or approximate hash values, relationship secret keys, verification algorithms, or some combination thereof from the relationship encryption module 110 or another source. The relationship authentication module 108 may find a linear relationship between ciphertexts and / or detect an approximation between approximate hash values. The relationship authentication module 108 may use a relationship secret key and / or a verification algorithm to find a linear relationship between ciphertexts and detect an approximation.

  The relationship authentication module 108 may include a linear authentication module 132 and an approximate authentication module 128. Although not shown in FIG. 1, in some embodiments, a configuration module 144 or a module configured to perform one or more steps belonging to the configuration module 144 may be included in the relationship authentication module 108.

  The linear authentication module 132 may be configured to perform one or more steps associated with linear ciphertext. For example, the linear authentication module 132 may be configured to find a linear relationship between two or more of the linear ciphertexts.

  The finding of the linear relationship may be a function of the Hamming distance. For example, the linear authentication module 132 is applied to the third secret key and the first element of the first linear ciphertext, IND_CCA secure decryption algorithm (DecCPA) applied to the first element of the third secret key and the second linear ciphertext. And the sum of DecCPA and a random 2 progression sequence of size 1st integer × 2nd integer may be calculated. The linear authentication module 132 may then calculate the product of this sum and a specific value (“z” above) that can be selected by the verification entity. The linear authentication module 132 may then determine whether the Hamming distance of the product of the sum and the specified value is less than or equal to the product of the value of 2, the probability, and the first integer.

  The approximate authentication module 128 may be configured to perform one or more steps associated with the approximate hash value. For example, the approximate authentication module 128 may be configured to detect an approximation between two or more approximate hash values. In some embodiments, the approximate authentication module 128 may be performed in accordance with an approximate verification algorithm described elsewhere in this disclosure.

  The relationship encryption module 110, the linear encryption module 112, the approximate encryption module 114, the setting module 144, the relationship authentication module 108, the linear authentication module 132, and the approximate authentication module 128 may be collectively represented as a relationship module. .

  The relationship module uses hardware including a processor, a microprocessor, a field-programmable gate array (FPGA), or an application-specific integrated circuit (ASIC) (for example, executing or controlling the execution of one or more steps). Can be implemented. In some other examples, the relationship module can be implemented using a combination of hardware and software. A software implementation may include rapid activation and deactivation of one or more transistors or transistor elements as may be included in the hardware of a computing system (eg, user device 102 and authentication server 140). Additionally, software defined instructions may operate on information in the transistor element. Implementation of software instructions may at least temporarily reconfigure the electronic path and convert computing hardware.

  In the next part, LPN (learning parity with noise) is introduced. Following the introduction of LPN, a linear relation hashing scheme based on LPN is described. Following the linear relational hash, a relational linear encryption scheme that performs the linear relational hash is described. The relational linear encryption method may be determined according to a linear relation hash method and a public key encryption method. Following the relational linear encryption scheme, a relational approximate hash scheme is described. The relational approximate hash method is based on a relational linear encryption method and an error correction code (ECC).

<LPN (LEARNING PARITY WITH NOISE)>
The parity function in a Boolean algebra may output “1” if the input vector has an odd (1 ′s) odd number of 1. An example of a parity function is an “XOR” function that receives two input vectors. Parity learning is a problem that represents approximation in machine learning. Algorithms have been developed to solve the parity value identification problem. In the algorithm, the function is estimated based on several input samples and the assumption that the function calculates the parity of the bits at several locations. In identifying a parity value, an input sample has an input (eg, an independent value) and a function value applied to the input (eg, a dependent value calculated from the independent value). Input samples can be provided over a distribution of functions that can reduce the complexity of the algorithm.

  LPN is the identification of certain parity values found in encryption and other applications. In LPN, input samples may contain some errors (eg, noise). For example, in LPN, an input sample has an input (eg, an independent value) and another value (eg, a dependent value calculated from the independent value) that is close to a function applied to the input with some small probability. good.

In the embodiments described in this disclosure, the LPN may be defined according to the following LPN equation:

体の隣にある添え字「２」は、整数集合の基本数を表す。体の隣にある添え字「ｎ」は、整数集合の次元を表す。

において、整数集合はｑ×ｎの次元を有する。パラメータｓ、Ａ及びｒは、整数集合からサンプリングされ、ＬＰＮ式に従い関連付けられる。 In the LPN equation, the parameter τ represents the probability. The function Ber ^q _τ is a function that outputs the number of q bits where each entry is “1” with probability τ (also referred to as noise probability in this disclosure), or “0” in other cases. The following parameters represent an integer set.

The subscript “2” next to the field represents the base number of the integer set. The subscript “n” next to the field represents the dimension of the integer set.

The integer set has q × n dimensions. The parameters s, A and r are sampled from the integer set and related according to the LPN equation.

  The advantage of LPN is efficiency. In particular, LPN expressions can be implemented in terms of XOR gates and AND gates. Furthermore, LPT is secure even when s is sampled from a high min entropy distribution such as a biological sample. In some embodiments, the probability τ may be about ¼.

<Linear relation hash method>
The LPN expression may be implemented in the operating environment 100 to generate a hash value for the plaintext vector 142. The linear relation hash may include multiple functions that can be applied to the plaintext vector 142. The functions may include a Hash_KEYGEN function, a Hash ₁ (x) function, a Hash ₂ (y) function, and a Hash_Verify function. The Hash_KEYGEN function may be configured to generate a hash key. The Hash ₁ (x) function and Hash ₂ (y) function may be configured to hash one or more input vectors (eg, plaintext vector 142). The Hash_Verify function may be configured to verify the relationship between the input vectors.

The linear relationship hash may be applied in the operating environment 100 according to the following linear relationship hash expression.

In the linear relation hash expression, A, Ber ^q _τ ,

  Security in the linear relationship hash expression may be based on the LPN described above. Further, the linear relationship hash expression may be symmetric and substantially unidirectional. This further improves security.

が高ｍｉｎエントロピ分布から得られ、ｅ１←Ｂｅｒ^ｑ _τの場合；

任意の多項式時間（つまり実現可能な実行時間の）アルゴリズムがｘ又は任意のｘに近いｘ’を出力することが、計算的に不可能である。 For example, the unidirectionality of the linear relationship hash expression may be determined according to the following unidirectional expression.

Is obtained from a high min entropy distribution and e1 ← Ber ^q _τ ;

It is computationally impossible for an arbitrary polynomial time (ie realizable execution time) algorithm to output x or x ′ close to arbitrary x.

及びｈｘ_１は、上述の通りである。高ｍｉｎエントロピ分布は、バイオメトリックテンプレートのような分布を含む。 One-way equation, e1 ← Ber ^q _τ , x, Hash ₁ (x), A,

And hx ₁ are as described above. The high min entropy distribution includes a distribution such as a biometric template.

<Relational linear encryption method>
A linear key may be generated for security parameters. In general, the security parameter used herein may represent a key length. In some embodiments, the generation of the linear key may be performed according to the following exemplary linear bit vector key expression. An example of a linear bit vector key expression includes:
Given λ:
Generate integers m, n and real numbers τε [0,1];
Generate a random binary progression A of size m × n;
Determine any IND_CCA secure public key encryption scheme, including key generation algorithm (Keygen-CPA), encryption algorithm (EncCPA), and decryption algorithm (DecCPA);
Run Keygen-CPA three times to generate three sets of public / private key pairs;
(Pk_1, sk_1), (pk_2, sk_2), and (pk_3, sk_3);
Set the following:
pkxlin: = (A, τ, pk_1, pk_3); skxlin: = sk_1;
pkylin: = (A, τ, pk_2, pk_3); skylin: = sk_2;
skRlin: = (A, τ, pk — 3)
In the linear bit vector key expression, ← and λ are generally as described above. Further, in the linear bit vector key expression, pkxlin represents the first linear public key, skxlin represents the first linear private key, pkylin represents the second linear public key, skylin represents the second linear private key, and skRlin Represents a relational linear secret key. The parameter τ represents the noise probability. Further, the parameters pkxlin, skxlin, pkylin, skylin, and skRlin may represent at least one linear part of the output of the key generation algorithm (KeyGen) described above. In some embodiments, τ may be equal to ¼.

The linear encryption module 112 may encrypt the plaintext vector 142. The linear encryption module 112 may receive the plaintext vector 142. In some embodiments, the linear encryption module 112 may encrypt the plaintext vector 142 according to the following exemplary linear bit vector encryption formula:
m1 = <m1 _i > ⁿ _{i = 1} ∈F ⁿ ₂ ; m2 = <m2 _i > ⁿ _{i = 1} ∈F ⁿ ₂ ;
cx: = EncCPA (pk_3, A × m1 + e1), EncCPA (pk_1, m1);
cy: = EncCPA (pk_3, A, m2 + e2), EncCPA (pk_2, m2);
e1εF ^m ₂ , each element is 1 with probability τ, otherwise 0;
e2εF ^m ₂ , each element is 1 with probability τ, and 0 otherwise.

In the linear bit vector key expression, EncCPA represents an encryption algorithm of the above-mentioned IND_CCA secure public key encryption method. The operator + represents a bitwise XOR operator. The parameter cx represents the first linear ciphertext, and the parameter cy represents the second linear ciphertext. The parameter m1 represents an n-bit first message, such as a plaintext vector 142. The parameter m1 _i represents an element of the first plaintext vector in the plaintext vector 142. The parameter m2 represents the second plaintext vector in the plaintext vector 142. The parameter m2 _i represents an element of the second plaintext vector in the plaintext vector 142. The parameter F represents the body. The subscript 2 next to the first field represents the basic number of fields. The subscript n next to the first body represents the dimension of the vector containing the first body element. The parameter i represents an index variable. In a linear bit vector key expression, the index variable has a range from 1 to the first body dimension. The operator <> represents a simple notation. For example, <b _i > ⁿ _{i = 1} means that b ₁ , b ₂ ,. . . , B _n .

  The linear bit vector encryption formula may define the first encryption algorithm (EncX) and the second encryption algorithm (EncY) described above. For example, the first encryption algorithm may be determined as follows.

give: m1 and pkxlin,
Sampling random 2 progression A,
Configure cx as follows:
cx: = EncCPA (pk_3, A * m1 + e1), EncCPA (pk_1, m1)
Similarly, the second encryption algorithm may be defined as follows.
given m2 and pkylin,
Sampling random 2 progression A,
Construct cy as follows:
cy: = EncCPA (pk_3, A, m2 + e2), EncCPA (pk_2, m2)
The first linear ciphertext and the second linear ciphertext may be communicated to the linear authentication module 132. Additionally or alternatively, the first linear ciphertext and the second linear ciphertext may be communicated to the authentication server 140 via the network 107. The authentication server 140 may receive the first linear ciphertext and the second linear ciphertext and communicate the first linear ciphertext and the second linear ciphertext to the linear authentication module 132.

  In some embodiments, the first linear ciphertext may be communicated to the linear authentication module 132 prior to communication of the second linear ciphertext. The linear authentication module 132 may store the first linear ciphertext as the registered ciphertext 130 in the memory 122. After communicating the first linear ciphertext, the second linear ciphertext may be communicated to the linear authentication module 132. Further, the configuration module 144 may communicate the related linear secret key to the linear authentication module 132.

  In some embodiments where relational encryption is used for authentication, the first linear ciphertext may be stored as registered ciphertext 130. The registered ciphertext 130 may be used as a basis for comparison with the second linear ciphertext or any other subsequent linear ciphertext. In other embodiments that implement relational encryption, the first linear ciphertext may not be stored as the registered ciphertext 130. For example, the first linear ciphertext and the second linear ciphertext may be analyzed without storing them, or both may be stored.

The linear authentication module 132 may be configured to find a linear relationship between the first linear ciphertext and the second linear ciphertext. In some embodiments, the linear authentication module 132 finds a linear relationship between the first linear ciphertext and the second linear ciphertext according to the following exemplary linear bit vector verification equation.
z = <z _i > ⁿ _{i = 1} ∈ F ⁿ ₂ ;
cx — 0: = EncCPA (pk — 3, A × m1 + e1);
cy — 0: = EncCPA (pk — 3, A × m2 + e2);
dist (DecCPA (sk_3, cx_0) + DecCPA (sk_3, cy_0) + A × z) < ^? 2 × τ × m
In the linear bit vector verification formula, <>, i, n, A, F ⁿ ₂ , pk — 3, m1, e1, τ, m2, e2, and sk — 3 are as described above. In the linear bit vector verification formula, dist is a function that evaluates the Hamming weight of an m-bit vector. The parameter cx_0 represents the first component of the first linear ciphertext. The parameter cy_0 represents the first component of the second linear ciphertext. The parameter z represents a specific vector. The parameter z _i represents an element of the specific vector. The operator + represents a bitwise XOR operator.

The linear bit vector verification formula may define the verification algorithm (Verify) described above. Similarly, the verification algorithm may be defined as follows:
give cy, cx, z, skRlin: = (A, τ, sk — 3):
Check for the following inequality:
dist (DecCPA (sk_3, cx_0) + DecCPA (sk_3, cy_0) + A × z) < ^? 2 × τ × m
The linear bit vector decoding formula may define the first decoding algorithm (DecX) and the second decoding algorithm (DecY) described above. For example, the first decryption algorithm may be determined as follows.
give: cx and skxlin,
Configure the first plaintext vector 142 bit by bit according to the equation:
cx_1 = EncCPA (pk_1, m1);
m1 = DecCPA (skxlin, cx_1)
In the first decryption algorithm, skxlin, EncCPA, pk_1, m1, skxlin, and DecCPA are as described above. The parameter cx_1 represents the second component of the first linear ciphertext (for example, cx).

Similarly, the second decryption algorithm may be defined as follows.
give: cy and skylin,
Construct second plaintext vector 142B bit by bit according to the equation:
cy_1 = EncCPA (pk_2, m2)
m2 = DecCPA (skylin, cy_1)
In the second decryption algorithm, skylin, EncCPA, pk_2, m2, and DecCPA are as described above. The parameter cy_1 is the second component of the second linear ciphertext (for example, cy).

<Relational approximate hash method>
In the relational approximate hash method implemented in the embodiment described in the present disclosure, the ciphertext may not be decipherable. Therefore, the relational approximate hash method may be a relational approximate hash method instead of the relational approximate encryption method. A relational approximate hashing scheme may be used to determine the closeness between approximate hash values. In some embodiments, the approximation may be given in terms of a Hamming distance. In the relational approximate hash method, the setting module 144 generates a key. Using the key, the approximate encryption module 114 performs encryption and / or decryption of the plaintext vector 142. The approximate hash value may then be communicated to the approximate authentication module 128. In the approximate authentication module 128, an approximation between the approximate hash values may be detected.

  For example, the setting module 144 may generate the output of a CPA (chosen-plaintext attack) key generation algorithm and a linear key generation algorithm. For example, the configuration module 144 runs the linear key as described elsewhere in this specification. The CPA key generation algorithm may output a CPA public key and a CPA private key. The linear key generation algorithm may output pkxlin, skxlin, pkylin, skylin, and skRlin as described above.

  Furthermore, the setting module 144 may select an error correcting code (ECC). The ECC may be a linear error correction code method. The ECC may have a length, rank, and distance. In addition, the ECC may have an ECC encoding operator (ENCODE) and an ECC decoding operator (DECODE). The setting module 144 then generates a first approximate secret key, a second approximate secret key, a first approximate public key, a second approximate public key, and an approximate relationship secret key (collectively, “approximate keys”). Good. The approximate key is used to hash the plaintext vector 142 to generate an approximate hash value and to detect an approximation between the approximate hash values.

  The first approximate secret key may be determined based on the CPA secret key and the first linear secret key. The second approximate secret key may be determined based on the CPA secret key and the second linear secret key. The first approximate public key may be determined based on ENCODE, DECODE, CPA public key, and first linear public key. The second approximate public key may be determined based on ENCODE, DECODE, CPA public key, and second linear public key. The approximate relationship secret key may be determined based on the CPA secret key and the linear relationship secret key.

In some embodiments, the setting module 144 may generate an approximate key according to the following exemplary approximate key generation equation.
(PkCPA, skCPA) <-KeyGen-CPA;
(Pkxlin, pkylin, skxlin, skylin, skRlin) ← KeyGenLinear; X ← Z ^{n × k} ₂ ;
pkxprox: = (ENCODE, DECODE, pkCPA, pkxlin, X);
pkyprox: = (ENCODE, DECODE, pkCPA, pkylin, X);
skxprox: = (skCPA, skxlin);
skyprox: = (skCPA, skylin);
skRprox: = (skCPA, skRlin)
In the approximate key generation formula, pkxlin, pkylin, skxlin, skylin, skRlin, ENCODE, and DECODE are as described above. The operator ← represents a random sampling operator. The parameter pkCPA represents the CPA public key. The parameter skCPA represents the CPA private key. The parameter KeyGen-CPA represents a CPA key generation algorithm. The parameter k represents a rank. The parameter pkxprox represents the first approximate public key. The parameter pkyprox represents the second approximate public key. The parameter X represents a random matrix. The parameter skxprox represents the first approximate secret key. The parameter skyprox represents the second approximate secret key. The parameter skRprox represents the approximate relationship secret key. Further, the parameters pkxprox, skxprox, pkyprox, skyprox, and skRprox may represent at least one approximate part of the output of the key generation algorithm (KeyGen) described above.

  The first linear public key may be used by the approximate encryption module 114 to hash the first plaintext vector 142A to generate a first approximate hash value. The approximate encryption module 114 may receive the plaintext vector 142 and communicate the plaintext vector 142 to the approximate encryption module 114. The plaintext vector 142 may have the first or second body members described above.

  The approximate encryption module 114 may sample an approximate random number (hereinafter r) from the third body. The third body may have a base number and a dimension that may be an ECC rank. The approximate encryption module 114 may then construct a first approximate hash value and a second approximate hash value. Each of the first approximate hash value and the second approximate hash value may have two parts. The first portion of the first approximate hash value may include a CPA encryption algorithm that receives a CPA public key and the sum of the first plaintext vector 142A as an input, and an ENCODE that receives an approximate random number as an input. The second portion of the first approximate hash value may include a first linear encryption algorithm that receives the first linear public key and the approximate random number.

  The first portion of the second approximate hash value may include a CPA encryption algorithm that receives a CPA public key and the sum of the second plaintext vector 142B as input, and an ENCODE that receives an approximate random number as input. The second portion of the second approximate hash value may include a second linear encryption algorithm that receives the second linear public key and the approximate random number as inputs.

In some embodiments, the approximate hash value may be generated according to the following exemplary approximate encryption formula:
cxp1: = EncCPA (pkCPA, m1 + ENCODE (r));
cxp2: = EncXLinear (pkxlin, X ○ r);
cxp: = (cxp1, cxp2);
cyp1: = EncCPA (pkCPA, m2 + ENCODE (r));
cyp2: = EncXLinear (pkylin, Xr);
cyp: = (cyp1, cyp2)
In the approximate encryption equation, ENCODE, m1, m2, pkCPA, X, pkxlin, and pkylin are as described above. EncCPA represents a CPA encryption algorithm. The parameter r represents an approximate random number of k bits. The parameter cxp1 represents the first part of the first approximate hash value. The parameter cxp2 represents the second part of the first approximate hash value. The parameter cxp represents the first approximate hash value. The parameter cyp1 represents the first part of the second approximate hash value. The parameter cyp2 represents the second part of the second approximate hash value. The parameter cyp represents the second approximate hash value. The parameter EncXLinear represents the first linear encryption algorithm. The parameter EncYLinear represents the second linear encryption algorithm.

  The first approximate hash value may be communicated to the authentication server 140 and stored in the authentication server 140 as the registered ciphertext 130. The second approximate public key may be used by the approximate encryption module 114 to hash the second plaintext vector 142B to generate a second approximate hash value. The second approximate hash value may be communicated to the authentication server 140. The approximate relationship secret key may be used in the authentication server 140. In particular, the approximate relationship secret key may be used by the approximate authentication server 128 to detect an approximation between the second approximate hash value and the first approximate hash value. This approximation is stored as registered ciphertext 130.

  The approximate authentication module 128 may be configured to detect an approximation between the first approximate hash value and the second approximate hash value. To detect the approximation, the approximation authentication module 128 may access the DECODE that is available with the public key information. The approximate authentication module 128 may restore a randomness sum of the first approximate hash values. The sum of the randomness of the first approximate hash value may be defined as DECODE. DECODE receives as input the CPA decryption algorithm (DecCPA) that receives the CPA private key and the sum of the first part of the first approximate hash value as input, and the CPA private key and the first part of the second approximate hash value as input. CPA decoding algorithm to be received as input.

  If DECODE returns an error, the approximate authentication module 128 may return a rejection. Further, the approximate authentication module 128 may output a linear verification algorithm. The linear verification algorithm receives as input the linear relationship secret key, the first part of the second approximate hash value, the second part of the second approximate hash value, and the randomness.

Accordingly, the approximate verification algorithm may be defined to receive the first approximate hash value, the second approximate hash value, and the approximate secret key. The approximate verification algorithm may restore the randomness sum and output a rejection or linear verification algorithm. The linear verification algorithm receives as input the linear relationship secret key, the first part of the second approximate hash value, the second part of the second approximate hash value, and the randomness. For example, the approximate authentication module 128 may perform one or more operations according to the following exemplary approximate verification algorithm.
Z _rs : = DECODE (DecCPA (skcpa, cx_1 + DecCPA (skcpa, cy_1)));
Output {If DECODE returns ⊥, reject;
VerifyLinear (skRlin, cs_2, cy_2, Xz)}
In the approximate verification algorithm, skcpa, cx_1, cx_2, cy_1, cy_2, skRlin, X, z, DecCPA, and DECODE are as described above. The parameter Output indicates the output of the approximate authentication module 128. The parameter Z _rs represents the sum of randomness. Parameter ⊥ represents an error. VerifyLinear represents a linear verification algorithm.

  The relational approximate encryption scheme described herein can be secure if the following conditions are true:

ECC is an (n ′, k, 2δ) linear error correction scheme;
(KeyGenCPA, EncCPA, DecCPA) is an IND-CPA secure encryption scheme;
(KeyGenLinear, EncXLinear, DecXLinear, EncYLinear, EncYLinear, VerifyLinear) is a linear relational encryption method in F ⁿ ₂ .

  Among the conditions, KeyGenCPA, EncCPA, DecCPA, KeyGenLinear, EncXLinear, DecXLinear, EncYLinear, DecYLinear, VerifyLinear, and F are as described above. ECC represents ECC. The parameter n ′ represents the length of the code word. The parameter k represents the length of the message. The parameter 2δ represents the minimum distance.

  Changes, additions, or omissions may be made to the operating environment 100 without departing from the scope of the present disclosure. The present disclosure provides for an operating environment 100 having one or more user devices 102, one or more authentication servers 140, one or more second entities 150, one or more first entities 152, or any combination thereof. Can be applied.

  Further, the division of the various components in the embodiments described herein does not mean that the division occurs in all embodiments. It is understood that the components described may be combined into a single component or divided into multiple components, with the benefit of this disclosure.

  FIG. 2 shows a block diagram of a biometric system (biometric system) 200 configured in accordance with at least one embodiment described herein. The biometric authentication system 200 may be included in or include the exemplary operating environment 100 of FIG. 1 where authentication services are provided. In the biometric authentication system 200, the authentication of the user 206 may be executed by the authentication server 140. In the biometric authentication system 200, the relational encryption discussed with reference to FIG. 1 may be used to authenticate the identity of the user 206.

  The authentication service may include a registration process and an authentication process. The registration process may include obtaining information and data from the user 206 that can be used in the authentication process. The authentication process may occur later in time (eg, following the registration process). In the authentication process, the identity of the user 206 may be authenticated using one or more of the related encryption operations discussed with reference to FIG. In general, the identity of user 206 is determined by finding the linearity between the first linear ciphertext and the second linear ciphertext, and the first approximate hash value and the second approximation, as described herein. Authentication may be performed by detecting an approximation between the hash values. The first linear ciphertext and the first approximate hash value may be provided by the user 206 in the form of a first biometric template. The first biometric template may be included in the first plaintext vector of the plaintext vectors 142 of FIG. 1 and / or the registration input of FIG.

  User 206 and / or impersonator 222 (discussed below) may have an individual with one or more biometric features. A biometric feature may have one or more unique features. For example, the biometric feature may include a fingerprint of the user 206 that has a pattern of wrinkles and / or wrinkles. In some embodiments, the user 206 may be associated with the user device 102. For example, the user 206 may own or regularly operate the user device 102. In some embodiments, the user 206 may not be specifically associated with the user device 102. For example, user device 102 may be publicly accessible by multiple users, including user 206. In some embodiments, the impersonator 222 may have an entity that provides input that may represent a biometric feature.

  In some embodiments, the user device 102 may have a sensor 298. The sensor 298 may comprise a hardware device configured to measure or capture biometric features that are used, for example, to authenticate the user 206. Once the biometric features of user 206 are measured or captured, user device 102 may generate a biometric template. The biometric template may represent a biometric feature and may include at least some of the unique features of the user 206 biometric feature. The biometric template may include, for example, a graphical and / or algorithmic representation of biometric features.

  Some examples of sensors 298 are generated by a fingerprint scanner, a camera configured to capture an image of the iris, a device configured to measure DNA, a heart rate monitor configured to capture heart rate, and skeletal muscle Wearable myoelectric sensors configured to capture electrical activity, or any other sensor 298 configured to measure or capture biometric features.

  In the illustrated biometric authentication system 200, the sensor 298 is included in the user device 102. In other embodiments, sensor 298 may be communicatively coupled to user device 102 or a processor included therein. For example, sensor 298 may be configured to communicate signals to user device 102 via a network, such as network 107 in FIG. Although only one sensor 298 is shown in FIG. 2, in some embodiments, the user device 102 may have one or more sensors 298.

  The relation encryption module 110 may generate the first linear ciphertext and the first approximate hash value from the registration input 232. The relationship encryption module 110 may then communicate to the authentication server 140 using the first linear ciphertext and the first approximate hash value as registration data 234.

  The relationship authentication module 108 may store the first linear ciphertext and the first approximate hash value as the registered ciphertext 130. The registered ciphertext 130 may be associated with the user 206. For example, the user 206 may have an associated user identifier. In some embodiments, the registered ciphertext 130 may be stored in the memory 122.

  The relationship encryption module 110 may then receive a first challenge input 236A or a second challenge input 236B (generally challenge input 236). First challenge input 236A and second challenge input 236B may be an attempt by user 206 or impersonator 222 to authenticate their identity. The first challenge input 236A and / or the second challenge input 236B may include, for example, a second biometric template read by the sensor 298. The second biometric template may represent a unique feature of the biometric feature of user 206 or impersonator 222.

  The relation encryption module 110 may generate the second linear ciphertext and the first approximate hash value from the registration input 236. The relationship encryption module 110 may then communicate to the authentication server 140 using the second linear ciphertext and the second approximate hash value as registration data 238.

  The relationship authentication module 108 may receive the challenge data 238. The relationship authentication module 108 may then read the registered ciphertext 130 of the user 206.

  The relationship authentication module 108 may determine a linear relationship between the first linear ciphertext stored as the registered ciphertext 130 and the second linear ciphertext received from the user device 102. Furthermore, the relationship authentication module 108 may determine an approximate relationship between the first approximate hash value stored as the registered ciphertext 130 and the second approximate hash value received from the user device 102.

  In response to the first linear ciphertext having a linear relationship with the second linear ciphertext and there is a specific approximation between the first approximate hash value and the second approximate hash value, the authentication server 140 , It may be determined that there is an approximate similarity between the first biometric template and the second biometric template.

  Therefore, if the first challenge input 236A provided by the user 206 is the basis of the second linear ciphertext and the second approximate hash value, there is a linear relationship between the first linear ciphertext and the second linear ciphertext. There may be an approximation between the first approximate hash value and the second approximate hash value.

  However, if the second challenge input 236B provided by the fake 222 is the basis of the second linear ciphertext and the second approximate hash value, there is a linear relationship between the first linear ciphertext and the second linear ciphertext. It does not exist and no approximation exists between the first approximate hash value and the second approximate hash value.

  Based on the linear relationship and / or approximation, the relationship authentication module 108 can determine the authentication. For example, the relationship authentication module 108 may determine whether the challenge data 238 is due to the user 206 or the fake 222. The relationship authentication module 108 may communicate the authentication signal 242 based on finding a linear relationship and / or detecting an approximation. The relation encryption module 110 may receive the authentication signal 242.

  Changes, additions or omissions may be made to the biometric authentication system 200 without departing from the scope of the present disclosure. Specifically, the embodiment shown in FIG. 2 has one user 206, one user device 102, and one authentication server 140. However, the present disclosure applies to a biometric authentication system 200 that may have one or more users 206, one or more user devices 102, one or more authentication servers 140, or any combination thereof.

  Further, the division of the various components in the embodiments described herein does not mean that the division occurs in all embodiments. It is understood that the components described may be combined into a single component or divided into multiple components for the benefit of this disclosure. For example, in some embodiments, the relationship encryption module 110 and / or one or more functions belonging thereto may be performed by a module in the authentication server 140.

  FIG. 3 shows an exemplary computing system 300 configured for relationship encryption. The computing system 300 may be implemented, for example, in the operating environment 100 of FIG. An example computing system 300 may include the user device 102 or the authentication server 140. The computing system 300 may include one or more processors 304, a memory 308, a communication unit 302, a user interface device 314, and a data storage device 301. The data storage device 301 includes a relationship authentication module 108 and a relationship encryption module 110 (collectively, modules 108/110).

  The processor 304 may comprise any suitable special purpose or general purpose computer, computing entity, or various computer hardware or software modules to execute instructions stored on any suitable computer readable medium. It can be implemented using a processing device that can be configured. For example, the processor 304 may be a microprocessor, microcontroller, digital signal processor (DSP), ASIC, FPGA, or any other digital or configured to interpret and / or execute program instructions and / or process data. An analog circuit may be included.

  Although a single processor is shown in FIG. 3, the processor 304 is more generally any number configured to perform any number of steps described in this disclosure individually or jointly. There may be a processor. Further, one or more of the processors 304 may reside in one or more different electronic devices or computing systems. In some embodiments, processor 304 may interpret and / or execute program instructions and / or process memory 308, data storage device 301 or data stored in memory 308 and data storage device 301. . In some embodiments, processor 304 may fetch program instructions from data storage device 301 and load the program instructions into memory 308. After the program instructions are loaded into the memory 308, the processor 304 may execute the program instructions.

  Memory 308 and data storage device 301 may include computer-readable storage media that carry or store computer-executable instructions or data structures. The term computer readable media may refer to a single media or multiple media. Such computer-readable media can include any available media that can be accessed by a general purpose or special purpose computer such as processor 304. By way of example and not limitation, such computer readable storage media may be RAM, ROM, EEPROM, CD-ROM or other optical disk storage, magnetic disk storage or other magnetic storage, flash memory devices (eg, solid state A tangible or non-transitory computer readable storage medium including a memory element) or used to convey or store desired program code means in the form of computer-executable instructions or data structures and accessible by a general purpose or special purpose computer Other storage media may be included. Combinations of the above can also be included within the scope of computer-readable storage media. Computer-executable instructions may include, for example, instructions and data configured to cause processor 304 to perform a specific process or group of processes.

  Computer-executable instructions comprise, for example, instructions and data that cause a general purpose computer, special purpose computer or special purpose processing resource to perform a specific function or group of functions. Although the subject matter of the present invention has been described in language specific to structural features and / or methodological operations, it is understood that the subject matter of the present invention is not limited to the specific features or operations described above as defined in the claims. It should be. Rather, the specific features and acts described above are disclosed as example forms of implementing the claims.

  The communication unit 302 may include one or more pieces of hardware configured to receive and transmit communications. In some embodiments, the communication unit 302 may include one or more of antennas, wired ports, modulation / demodulation hardware, among other communication hardware devices. In particular, the communication unit 302 receives communications from outside the computing system 300 and presents the communications to the processor 304 or routes communications from the processor 304 to another device or network (eg, 107 in FIG. 1). It may be configured to transmit.

  The user interface device 314 may include one or more pieces of hardware configured to receive input from the user and / or provide output to the user. In some embodiments, the user interface device 314 may include one or more of a speaker, microphone, display, keyboard, touch screen, holographic projection, among other hardware devices.

  Module 108/110 may have program instructions stored in data storage device 301. The processor 304 may be configured to load the module 108/110 into the memory 308 and execute the module 108/110. Alternatively, processor 304 may execute modules 108/110 line by line from data storage device 301 without loading into memory 308. When executing module 108/110, processor 304 may be configured to perform relationship authentication as described elsewhere in this disclosure.

  Changes, additions, or omissions may be made to the computing system 300 without departing from the scope of the present disclosure. For example, in some embodiments, the computing system 300 may not have the user interface device 314. In some embodiments, the different components of computing system 300 may be physically separate and may be communicatively coupled by any suitable mechanism. For example, the data storage device 301 may be a portion of the storage device that is separate from a server that includes a processor 304, a memory 308, and a communication unit 302 that are communicatively coupled to the storage device.

  FIG. 4 is a flow diagram of an exemplary method 400 for biometric authentication configured in accordance with at least one embodiment described herein. The method 400 may be performed in a biometric authentication system, such as the biometric system 200 of FIG. 2, or in the operating environment 100 of FIG. The method 400 may be program-controlled and executed in some embodiments by the authentication server 140 described herein. The authentication server 140 encodes or stores program code or instructions executable by the processor to execute or control the execution of the method 400 (eg, the memory 122 of FIG. 1 or The memory 308) of FIG. 3 may be included or communicatively coupled thereto. Additionally or alternatively, the authentication server 140 may include a processor (eg, processor 304 of FIG. 3) configured to execute computer instructions to perform or control the execution of method 400. Although shown as separate blocks, depending on the desired implementation, the various blocks may be divided into further blocks, combined into fewer blocks, or removed.

  Method 400 may begin at block 402. At block 402, a first linear ciphertext may be received. The first linear ciphertext may be received by the authentication server. For example, referring to FIG. 1, the user device 102 may communicate the first linear ciphertext to the authentication server 140. The first linear ciphertext may represent a first biometric template that may be sampled from a high min entropy distribution.

  The first biometric template may be encrypted using a relational linear encryption scheme. A relational linear encryption scheme may be based on a linear relation hash based on LPN. Furthermore, the relational linear encryption scheme may be further based on the IND_CCA secure public key encryption scheme. The IND_CCA secure public key encryption scheme may include a key generation algorithm (Keygen-CPA), an encryption algorithm (EncCPA), and a decryption algorithm (DecCPA).

  At block 404, a first approximate hash value may be received. The first approximate hash value may be received by the authentication server. For example, referring to FIG. 1, the user device 102 may communicate the first approximate hash value to the authentication server 140. The first approximate hash value may represent a first biometric template encrypted using a relational approximate hash method. The relational approximate hashing scheme may be based on a relational linear encryption scheme and ECC.

  At block 406, the first linear ciphertext and / or the first approximate hash value may be stored as a registered ciphertext. For example, the first linear ciphertext and / or the first approximate hash value may be stored in a memory of an authentication server such as the memory 122 of the authentication server 140.

  At block 408, a second linear ciphertext may be received. The second linear ciphertext may represent a second biometric template that may be sampled from a high min entropy distribution. The second biometric template may be encrypted using a relational linear encryption scheme. The first linear ciphertext and / or the second linear ciphertext may be encrypted according to a linear bit vector encryption formula described elsewhere in this disclosure.

  At block 410, a second approximate hash value may be received. The second approximate hash value may represent a second biometric template that is encrypted using a relational approximate encryption scheme. In some embodiments, the first approximate hash value and / or the second approximate hash value is generated according to an approximate encryption formula described elsewhere in this disclosure.

  At block 412, a linear relationship between the first linear ciphertext and the second linear ciphertext may be discovered. A linear relationship may be discovered using a linear relationship key. In some embodiments, the discovery of the linear relationship may be performed according to a verification algorithm described elsewhere in this disclosure. Further, in some embodiments, discovery may be performed using only AND and OR gates.

  At block 414, an approximation between the first approximate hash value and the second approximate hash value may be detected. The approximation may be determined in terms of Hamming distance. In some embodiments, the approximation detection may be performed according to an approximation verification algorithm described elsewhere in this disclosure. Further, in some embodiments, discovery may be performed using only AND and OR gates. At block 418, user identity may be authenticated based on the approximate and linear relationships.

  Those skilled in the art will appreciate that in the other procedures and methods described above and disclosed herein, the functions performed by the processes and methods may be performed in a different order. Furthermore, the general steps and operations are provided merely as examples, and some steps and operations are optional, combined with fewer steps and operations, or additional steps and operations without departing from the disclosed embodiments. May be extended to work.

  As used herein, the terms “module”, “component”, and / or “engine” may refer to software objects or routines that execute on a computer system. Different components, modules, engines, and services than those described herein may be implemented as objects or processes that execute on a computing system (eg, as separate threads). While the systems and methods described herein are preferably implemented in software, hardware implementations or combinations of software and hardware are possible and envisioned. In this description, a “computer entity” may be a computing system or a module or combination of modules that executes on a computing system as defined earlier in this specification.

  All examples and conditional statements provided herein are for educational purposes to help the reader understand the principles of the present invention and the concepts devised by the inventor, and promote technology, It should be considered that they are not limited to these specifically described examples and conditions. Although embodiments of the present invention have been described in detail, it should be understood that various changes, substitutions and modifications can be made without departing from the spirit and scope of the invention.

In addition to the above embodiment, the following additional notes are disclosed.
(Supplementary Note 1) Receiving a first linear ciphertext representing a first biometric template that is encrypted using a relational linear encryption scheme based at least in part on LPN (learning parity with noise);
Receiving a second linear ciphertext representing a second biometric template that is encrypted using the relational linear encryption scheme;
Discovering a linear relationship between the first linear ciphertext and the second linear ciphertext using a linear relationship private key;
Receiving a first approximate hash value representing the first biometric template that is encrypted using a relational approximate hash scheme, wherein the relational approximate hash scheme includes the relational linear encryption scheme and an error correction code ( ECC), steps,
Receiving a second approximate hash value representing the second biometric template encrypted using the relational approximate hash scheme;
Detecting an approximation between the first approximate hash value and the second approximate hash value in terms of a Hamming distance;
Authenticating the identity of the user based on the approximation and the linear relationship;
Having a method.
(Supplementary note 2) The method according to supplementary note 1, wherein the relational linear encryption scheme is further based on an IND_CCA secure public key encryption scheme including a key generation algorithm, an encryption algorithm, and a decryption algorithm.
(Supplementary Note 3) The step of finding the linear relationship is performed according to the following verification algorithm:
skRlin: = (A, τ, sk — 3);
give cy, cx, z, skRlin:
Check for the following inequality:
dist (DecCPA (sk_3, cx_0) + DecCPA (sk_3, cy_0) + A × z) < ^? 2 × τ × m),
Here, cy represents the first linear ciphertext,
cx represents the second linear ciphertext,
skRlin represents a linear relationship private key,
z represents a specific value selected by the validation entity;
A represents a random binary progression having dimensions of 1st integer × 2nd integer;
τ represents the noise probability,
sk_3 represents a secret key of the IND_CCA secure public key encryption method,
cx_0 represents the first element of the first linear ciphertext,
cy_0 represents the first element of the second linear ciphertext,
DecCPA represents the decryption algorithm;
dist represents the Hamming distance operator;
m represents the first integer;
The method according to appendix 2.
(Supplementary Note 4) The first linear ciphertext is encrypted according to the following linear bit vector encryption formula,
m1 = <m1 _i > ⁿ _{i = 1} ∈ F ⁿ ₂ ;
cx: = EncCPA (pk — 3, A × m1 + e1), EncCPA (pk — 1, m1);
e1∈F ^m ₂ , each element is 1 with probability τ, and 0 in other cases,
m1 represents the first message of n bits,
pk_3 represents a public key of the IND_CCA secure public key encryption method,
pk_1 represents another public key of the IND_CCA secure public key encryption method,
i represents an index variable;
n represents the dimension of the first body,
EncCPA represents the encryption algorithm;
The + operator represents a bitwise XOR operator,
F ₂ represents a basic number 2 field,
The method according to attachment 3.
(Supplementary note 5) The method according to supplementary note 4, wherein the noise probability is equal to about 0.25.
(Supplementary note 6) The method according to supplementary note 1, wherein the first biometric template is sampled from a high-min entropy distribution.
(Supplementary Note 7) The step of detecting the approximation is executed according to the following approximation verification algorithm:
Z _rs : = DECODE (DecCPA (skcpa, cx_1 + DecCPA (skcpa, cy_1)));
Output = {Reject if DECODE returns ⊥; VerifyLinear (skRlin, cx_2, cy_2, X ○ Z)};
Here, Z _rs represents the sum of randomness,
DECODE represents an ECC decryption operator;
DecCPA represents the decryption algorithm of the IND_CCA secure public key encryption method,
cx_1 represents the second element of the first linear ciphertext,
cy_1 represents the second element of the second linear ciphertext,
cx_2 represents the third element of the first linear ciphertext,
cy_2 represents the third element of the second linear ciphertext,
skRlin represents a relational linear key;
X represents a random matrix,
skcpa represents a CPA private key generated by a key generation algorithm of the ND_CCA secure public key encryption method,
⊥ represents an error,
z represents a specific value selected by the validation entity;
VerifyLinear represents a linear verification algorithm,
The method according to appendix 1.
(Supplementary Note 8) The first approximate hash value is generated according to the following approximate encryption formula,
cxp1: = EncCPA (pkCPA, m1 + ENCODE (r));
cxp2: = EncXLinear (pkxlin, X ○ r);
cxp: = (cxp1, cxp2),
Here, cxp represents the first approximate hash value,
cxp1 represents the first part of the first approximate hash value;
cxp2 represents the second part of the first approximate hash value;
EncCPA represents the encryption algorithm of the IND_CCA secure public key encryption method,
m1 represents the first biometric template;
pkCPA represents a CPA public key generated by a key generation algorithm of the ND_CCA secure public key encryption method,
ENCODE represents an ECC encoding operator;
r represents an approximate random number;
X represents a random matrix,
EncXLinear represents the first linear encryption algorithm,
The method according to appendix 1.
(Supplementary note 9) The method according to supplementary note 1, wherein the discovering step and the detecting step are performed using only AND gates and OR gates.
(Supplementary note 10) The method according to supplementary note 1, further comprising: storing the first linear ciphertext and the first approximate ciphertext as registered ciphertext.
(Supplementary Note 11) A non-transitory computer readable medium having encoded programming code executable by a processor to perform or control the execution of the process, the process comprising:
Receiving a first linear ciphertext representing a first biometric template that is encrypted using a relational linear encryption scheme based at least in part on LPN (learning parity with noise);
Receiving a second linear ciphertext representing a second biometric template that is encrypted using the relational linear encryption scheme;
Discovering a linear relationship between the first linear ciphertext and the second linear ciphertext using a linear relationship private key;
Receiving a first approximate hash value representing the first biometric template that is encrypted using a relational approximate hash scheme, wherein the relational approximate hash scheme includes the relational linear encryption scheme and an error correction code ( ECC), steps,
Receiving a second approximate hash value representing the second biometric template encrypted using the relational approximate hash scheme;
Detecting an approximation between the first approximate hash value and the second approximate hash value in terms of a Hamming distance;
Authenticating the identity of the user based on the approximation and the linear relationship;
A non-transitory computer readable medium having:
(Supplementary note 12) The non-transitory computer-readable medium according to Supplementary note 11, wherein the relational linear encryption scheme is further based on an IND_CCA secure public key encryption scheme including a key generation algorithm, an encryption algorithm, and a decryption algorithm.
(Supplementary note 13) The step of finding the linear relationship is performed according to the following verification algorithm:
skRlin: = (A, τ, sk — 3);
give cy, cx, z, skRlin:
Check for the following inequality:
dist (DecCPA (sk_3, cx_0) + DecCPA (sk_3, cy_0) + A × z) < ^? 2 × τ × m),
Here, cy represents the first linear ciphertext,
cx represents the second linear ciphertext,
skRlin represents a linear relationship private key,
z represents a specific value selected by the validation entity;
A represents a random binary progression having dimensions of 1st integer × 2nd integer;
τ represents the noise probability,
sk_3 represents a secret key of the IND_CCA secure public key encryption method,
cx_0 represents the first element of the first linear ciphertext,
cy_0 represents the first element of the second linear ciphertext,
DecCPA represents the decryption algorithm;
dist represents the Hamming distance operator;
m represents the first integer;
The non-transitory computer-readable medium according to attachment 12.
(Supplementary note 14) The first linear ciphertext is encrypted according to the following linear bit vector encryption formula,
m1 = <m1 _i > ⁿ _{i = 1} ∈ F ⁿ ₂ ;
cx: = EncCPA (pk — 3, A × m1 + e1), EncCPA (pk — 1, m1);
e1εF ^m ₂ , where each element is 1 with probability τ, and 0 otherwise;
m1 represents the first message of n bits,
pk_3 represents a public key of the IND_CCA secure public key encryption method,
pk_1 represents another public key of the IND_CCA secure public key encryption method,
i represents an index variable;
n represents the dimension of the first body,
EncCPA represents the encryption algorithm;
The + operator represents a bitwise XOR operator,
F ₂ represents a basic number 2 field,
The non-transitory computer-readable medium according to attachment 13.
(Supplementary note 15) The noise probability is equal to about 0.25,
The non-transitory computer-readable medium according to appendix 14.
(Supplementary note 16) The non-transitory computer readable medium of supplementary note 11, wherein the first biometric template is sampled from a high min entropy distribution.
(Supplementary Note 17) The step of detecting the approximation is executed according to the following approximation verification algorithm:
Z _rs : = DECODE (DecCPA (skcpa, cx_1 + DecCPA (skcpa, cy_1)));
Output = {Reject if DECODE returns ⊥;
VerifyLinear (skRlin, cx_2, cy_2, X ○ Z)};
Here, Z _rs represents the sum of randomness,
DECODE represents an ECC decryption operator;
DecCPA represents the decryption algorithm of the IND_CCA secure public key encryption method,
cx_1 represents the second element of the first linear ciphertext,
cy_1 represents the second element of the second linear ciphertext,
cx_2 represents the third element of the first linear ciphertext,
cy_2 represents the third element of the second linear ciphertext,
skRlin represents a relational linear key;
X represents a random matrix,
skcpa represents a CPA private key generated by a key generation algorithm of the ND_CCA secure public key encryption method,
⊥ represents an error,
z represents a specific value selected by the validation entity;
VerifyLinear represents a linear verification algorithm,
The non-transitory computer-readable medium according to attachment 11.
(Supplementary Note 18) The first approximate hash value is generated according to the following approximate encryption formula,
cxp1: = EncCPA (pkCPA, m1 + ENCODE (r));
cxp2: = EncXLinear (pkxlin, X ○ r);
cxp: = (cxp1, cxp2),
Here, cxp represents the first approximate hash value,
cxp1 represents the first part of the first approximate hash value;
cxp2 represents the second part of the first approximate hash value;
EncCPA represents the encryption algorithm of the IND_CCA secure public key encryption method,
m1 represents the first biometric template;
pkCPA represents a CPA public key generated by a key generation algorithm of the ND_CCA secure public key encryption method,
ENCODE represents an ECC encoding operator;
r represents an approximate random number;
X represents a random matrix,
EncXLinear represents the first linear encryption algorithm,
The non-transitory computer-readable medium according to attachment 11.
(Supplementary note 19) The non-transitory computer-readable medium according to supplementary note 11, wherein the discovering step and the detecting step are performed using only AND gates and OR gates.
(Supplementary note 20) The non-transitory computer-readable medium according to Supplementary note 11, wherein the step further includes a step of storing the first linear ciphertext and the first approximate ciphertext as registered ciphertext.

DESCRIPTION OF SYMBOLS 100 Operating environment 102 User apparatus 107 Network 108 Relational authentication module 110 Relational encryption module 112 Linear encryption module 114 Approximate encryption module 122 Memory 128 Approximate authentication module 130 Registered ciphertext 132 Linear authentication module 140 Authentication server 142 Plain text vector 144 Setting module 150 Second entity 152 First entity

Claims (20)

Receiving a first linear ciphertext representing a first biometric template that is encrypted using a relational linear encryption scheme based at least in part on LPN (learning parity with noise);
Receiving a second linear ciphertext representing a second biometric template that is encrypted using the relational linear encryption scheme;
Discovering a linear relationship between the first linear ciphertext and the second linear ciphertext using a linear relationship private key;
Receiving a first approximate hash value representing the first biometric template that is encrypted using a relational approximate hash scheme, wherein the relational approximate hash scheme includes the relational linear encryption scheme and an error correction code ( ECC), steps,
Receiving a second approximate hash value representing the second biometric template encrypted using the relational approximate hash scheme;
Detecting an approximation between the first approximate hash value and the second approximate hash value in terms of a Hamming distance;
Authenticating the identity of the user based on the approximation and the linear relationship;
Having a method.   The method of claim 1, wherein the relational linear encryption scheme is further based on an IND_CCA secure public key encryption scheme that includes a key generation algorithm, an encryption algorithm, and a decryption algorithm. The step of finding the linear relationship is performed according to the following verification algorithm:
skRlin: = (A, τ, sk — 3);
give cy, cx, z, skRlin:
Check for the following inequality:
dist (DecCPA (sk_3, cx_0) + DecCPA (sk_3, cy_0) + A × z) < ^? 2 × τ × m),
Here, cy represents the first linear ciphertext,
cx represents the second linear ciphertext,
skRlin represents a linear relationship private key,
z represents a specific value selected by the validation entity;
A represents a random binary progression having dimensions of 1st integer × 2nd integer;
τ represents the noise probability,
sk_3 represents a secret key of the IND_CCA secure public key encryption method,
cx_0 represents the first element of the first linear ciphertext,
cy_0 represents the first element of the second linear ciphertext,
DecCPA represents the decryption algorithm;
dist represents the Hamming distance operator;
m represents the first integer;
The method of claim 2. The first linear ciphertext is encrypted according to the following linear bit vector encryption formula:
m1 = <m1 _i > ⁿ _{i = 1} ∈ F ⁿ ₂ ;
cx: = EncCPA (pk — 3, A × m1 + e1), EncCPA (pk — 1, m1);
e1∈F ^m ₂ , each element is 1 with probability τ, and 0 in other cases,
m1 represents the first message of n bits,
pk_3 represents a public key of the IND_CCA secure public key encryption method,
pk_1 represents another public key of the IND_CCA secure public key encryption method,
i represents an index variable;
n represents the dimension of the first body,
EncCPA represents the encryption algorithm;
The + operator represents a bitwise XOR operator,
F ₂ represents a basic number 2 field,
The method of claim 3.   The method of claim 4, wherein the noise probability is equal to about 0.25.   The method of claim 1, wherein the first biometric template is sampled from a high min entropy distribution. The step of detecting an approximation is performed according to the following approximate verification algorithm:
Z _rs : = DECODE (DecCPA (skcpa, cx_1 + DecCPA (skcpa, cy_1)));
Output = {Reject if DECODE returns ⊥; VerifyLinear (skRlin, cx_2, cy_2, X ○ Z)};
Here, Z _rs represents the sum of randomness,
DECODE represents an ECC decryption operator;
DecCPA represents the decryption algorithm of the IND_CCA secure public key encryption method,
cx_1 represents the second element of the first linear ciphertext,
cy_1 represents the second element of the second linear ciphertext,
cx_2 represents the third element of the first linear ciphertext,
cy_2 represents the third element of the second linear ciphertext,
skRlin represents a relational linear key;
X represents a random matrix,
skcpa represents a CPA private key generated by a key generation algorithm of the ND_CCA secure public key encryption method,
⊥ represents an error,
z represents a specific value selected by the validation entity;
VerifyLinear represents a linear verification algorithm,
The method of claim 1. The first approximate hash value is generated according to the following approximate encryption formula:
cxp1: = EncCPA (pkCPA, m1 + ENCODE (r));
cxp2: = EncXLinear (pkxlin, X ○ r);
cxp: = (cxp1, cxp2),
Here, cxp represents the first approximate hash value,
cxp1 represents the first part of the first approximate hash value;
cxp2 represents the second part of the first approximate hash value;
EncCPA represents the encryption algorithm of the IND_CCA secure public key encryption method,
m1 represents the first biometric template;
pkCPA represents a CPA public key generated by a key generation algorithm of the ND_CCA secure public key encryption method,
ENCODE represents an ECC encoding operator;
r represents an approximate random number;
X represents a random matrix,
EncXLinear represents the first linear encryption algorithm,
The method of claim 1.   The method of claim 1, wherein the discovering and detecting are performed using only AND gates and OR gates.   The method according to claim 1, further comprising storing the first linear ciphertext and the first approximate ciphertext as registered ciphertext. A non-transitory computer readable medium having encoded programming code executable by a processor to perform or control the execution of the process, the process comprising:
Receiving a first linear ciphertext representing a first biometric template that is encrypted using a relational linear encryption scheme based at least in part on LPN (learning parity with noise);
Receiving a second linear ciphertext representing a second biometric template that is encrypted using the relational linear encryption scheme;
Discovering a linear relationship between the first linear ciphertext and the second linear ciphertext using a linear relationship private key;
Receiving a first approximate hash value representing the first biometric template that is encrypted using a relational approximate hash scheme, wherein the relational approximate hash scheme includes the relational linear encryption scheme and an error correction code ( ECC), steps,
Receiving a second approximate hash value representing the second biometric template encrypted using the relational approximate hash scheme;
Detecting an approximation between the first approximate hash value and the second approximate hash value in terms of a Hamming distance;
Authenticating the identity of the user based on the approximation and the linear relationship;
A non-transitory computer readable medium having:   The non-transitory computer-readable medium of claim 11, wherein the relational linear encryption scheme is further based on an IND_CCA secure public key encryption scheme that includes a key generation algorithm, an encryption algorithm, and a decryption algorithm. The step of finding the linear relationship is performed according to the following verification algorithm:
skRlin: = (A, τ, sk — 3);
give cy, cx, z, skRlin:
Check for the following inequality:
dist (DecCPA (sk_3, cx_0) + DecCPA (sk_3, cy_0) + A × z) < ^? 2 × τ × m),
Here, cy represents the first linear ciphertext,
cx represents the second linear ciphertext,
skRlin represents a linear relationship private key,
z represents a specific value selected by the validation entity;
A represents a random binary progression having dimensions of 1st integer × 2nd integer;
τ represents the noise probability,
sk_3 represents a secret key of the IND_CCA secure public key encryption method,
cx_0 represents the first element of the first linear ciphertext,
cy_0 represents the first element of the second linear ciphertext,
DecCPA represents the decryption algorithm;
dist represents the Hamming distance operator;
m represents the first integer;
The non-transitory computer readable medium of claim 12. The first linear ciphertext is encrypted according to the following linear bit vector encryption formula:
m1 = <m1 _i > ⁿ _{i = 1} ∈ F ⁿ ₂ ;
cx: = EncCPA (pk — 3, A × m1 + e1), EncCPA (pk — 1, m1);
e1εF ^m ₂ , where each element is 1 with probability τ, and 0 otherwise;
m1 represents the first message of n bits,
pk_3 represents a public key of the IND_CCA secure public key encryption method,
pk_1 represents another public key of the IND_CCA secure public key encryption method,
i represents an index variable;
n represents the dimension of the first body,
EncCPA represents the encryption algorithm;
The + operator represents a bitwise XOR operator,
F ₂ represents a basic number 2 field,
The non-transitory computer readable medium of claim 13. The noise probability is equal to about 0.25;
The non-transitory computer readable medium of claim 14.   The non-transitory computer readable medium of claim 11, wherein the first biometric template is sampled from a high min entropy distribution. The step of detecting the approximation is performed according to the following approximation verification algorithm:
Z _rs : = DECODE (DecCPA (skcpa, cx_1 + DecCPA (skcpa, cy_1)));
Output = {Reject if DECODE returns ⊥;
VerifyLinear (skRlin, cx_2, cy_2, X ○ Z)};
Here, Z _rs represents the sum of randomness,
DECODE represents an ECC decryption operator;
DecCPA represents the decryption algorithm of the IND_CCA secure public key encryption method,
cx_1 represents the second element of the first linear ciphertext,
cy_1 represents the second element of the second linear ciphertext,
cx_2 represents the third element of the first linear ciphertext,
cy_2 represents the third element of the second linear ciphertext,
skRlin represents a relational linear key;
X represents a random matrix,
skcpa represents a CPA private key generated by a key generation algorithm of the ND_CCA secure public key encryption method,
⊥ represents an error,
z represents a specific value selected by the validation entity;
VerifyLinear represents a linear verification algorithm,
The non-transitory computer readable medium of claim 11. The first approximate hash value is generated according to the following approximate encryption formula:
cxp1: = EncCPA (pkCPA, m1 + ENCODE (r));
cxp2: = EncXLinear (pkxlin, X ○ r);
cxp: = (cxp1, cxp2),
Here, cxp represents the first approximate hash value,
cxp1 represents the first part of the first approximate hash value;
cxp2 represents the second part of the first approximate hash value;
EncCPA represents the encryption algorithm of the IND_CCA secure public key encryption method,
m1 represents the first biometric template;
pkCPA represents a CPA public key generated by a key generation algorithm of the ND_CCA secure public key encryption method,
ENCODE represents an ECC encoding operator;
r represents an approximate random number;
X represents a random matrix,
EncXLinear represents the first linear encryption algorithm,
The non-transitory computer readable medium of claim 11.   The non-transitory computer readable medium of claim 11, wherein the discovering and detecting are performed using only AND and OR gates. The non-transitory computer-readable medium of claim 11, wherein the step further comprises storing the first linear ciphertext and the first approximate ciphertext as registered ciphertext.

Images