JP2009111971A - Method of pre-processing biometric parameters before encoding and decoding - Google Patents

Abstract

<P>PROBLEM TO BE SOLVED: To provide a method of preprocessing biometric parameters acquired from human faces, voices, fingerprints, and irises to use them for user authentication and access control. <P>SOLUTION: Since the biometric parameters are continuous and vary from one reading to the next, syndrome codes are used to discriminate biometric syndrome vectors. The biometric syndrome vectors can be stored securely while the variability specific to the biometric data is permitted. The stored biometric syndrome vectors are decoded during user authentication using biometric parameters acquired at that time. The syndrome codes can also be used to encrypt and decrypt data. The biometric parameters can be pre-processed to form a binary representation having a set of predetermined statistical properties given under a set of binary logical conditions. <P>COPYRIGHT: (C)2009,JPO&INPIT

Description

Related Application This application is filed by U.S. Patent Application No. 11/11, filed on November 29, 2006, under the name “Biometric Based User Authentication and Data Encryption” by Draper et al. US patent application Ser. No. 11 / 564,638, which is a partially pending application of US Pat. No. 564,638, was also published by Martini et al. On September 1, 2005, “Biometric Based User Authentication and Data Encryption And US Patent Application No. 11 / 218,261 (US Publication 2006-0123241) filed under the name And US patent application Ser. No. 11 / 218,261, issued by Martinin et al. On December 7, 2004 under the name “Biometric Based User Authentication with Syndrome Codes”. This is a partially pending application of filed US patent application Ser. No. 11 / 006,308 (US Publication 2006-0123239).

  In general, the invention relates to the field of cryptography, and more particularly to obtaining, preprocessing, encoding, and storing biometric parameters for user authentication and data encryption.

  Traditional password-based security system

  Conventional password-based security systems typically include two phases. Specifically, during the registration phase, the user selects passwords, which are stored (stored) in an authentication device such as a server. During the authentication phase, to gain access to resources and data, users enter their passwords, which are verified against the stored version of the password. If the password is stored as plain text, an adversary gaining access to the system may be able to obtain any password. In this way, even a single successful attack can compromise the security of the entire system.

  As shown in FIG. 1, the conventional password-based security system 100 stores (stores) 1115 the encoded password 101 in the password database 120 during the registration phase 10. Specifically, if X is password 101 stored 115, system 100 actually stores f (X), where f (.) Is some encryption or hash function 110. During the authentication phase 20, the user enters the candidate password Y102, the system determines f (Y) 130, and when f (Y) matches the stored password f (X), the system accesses 150. Otherwise, access is denied 160.

  As an advantage, encrypted passwords are usually very difficult to invert (reverse, reverse), so without an encryption function, they are useless to an adversary.

  Conventional biometric based security system

  Biometric security systems measure physical biometric features to obtain biometric parameters often referred to as observations. Traditional biometric security systems have vulnerabilities similar to password-based systems that store unencrypted passwords. Specifically, if the database stores unencrypted biometric parameters, those parameters are subject to attack and misuse.

  For example, in a security system that uses a face recognition system or voice recognition, an adversary may be able to search for biometric parameters similar to the adversary. After the appropriate biometric parameters are found, the adversary may be able to change the parameters to match the appearance or voice of the adversary in order to gain unauthorized access. Similarly, in a security system that uses fingerprint or iris recognition, an adversary may be able to create a device that simulates a matching fingerprint or iris to gain unauthorized access. For example, such a device is a counterfeit finger or counterfeit eye.

  It is not always possible to encrypt biometric parameters not only due to the variability of basic biometric features, but also due to the variability in the way in which those features are measured. This variability or difference can be referred to as “noise”.

  Specifically, the biometric parameter X is input during the registration phase. For example, suppose parameter X is encrypted and stored using encryption or hashing function f (X). During the authentication phase, biometric parameters obtained from the same user may be different. For example, in a security system that uses face authentication, cameras used for registration and authentication can have different orientations, sensitivities and resolutions. Usually the lighting is quite different. Skin tone, hairstyle, and other facial features can be easily changed. In this way, if the newly observed parameter Y is passed through the same encryption function f during authentication, the result f (Y) will not match f (X) and will cause a rejection. I will. Similar problems exist with other biometric based user authentication such as iris and fingerprint patterns.

  Error correction code

The (N, K) error correction code (ECC) C on the alphabet Q includes a ^QK vector of length N. Linear (N, K) ECC can be explained by using a generator matrix G of N rows and K columns or a parity check matrix H of NK rows and N columns. The name “generator matrix” is obtained from the input row vector v of any length K by the codeword represented as the vector w by multiplying the vector v later by the matrix G (from the right), ie w = vG. Based on the fact that it can be generated. Similarly, to check whether vector w is a codeword, it may be checked whether Hw ^T = 0, where column vector w ^T is a transpose of row w.

  In standard usage of error correction codes, the input vector v is encoded (encoded) into a vector w and stored or transmitted. If a corrupted (incorrect) version of the vector w is received, the decoder uses redundancy in the code to correct the error. Intuitively, the error correction capability of the code depends on the amount of code redundancy.

  Slepian-Wolf, Winner Jib, and Syndrome Code

  In a sense, the Slepian-Wolf (SW) code is the reverse (antonym) of the error correction code. The error correction code adds redundancy to expand the data, while the SW code removes redundancy and compresses the data. Specifically, vectors x and y represent associated data. If the encoder wishes to convey vector x to a decoder that already has vector y, the encoder can compress the data taking into account the fact that the decoder has vector y.

  As an extreme example, if the vectors x and y differ by one bit, the encoder can achieve data compression by simply describing the vector x and the location of the difference. Of course, a more sophisticated code is required for a more realistic correlation model.

  The basic theory of SW coding and related WinZive (WZ) coding can be found in IEEE Transactions on Information Theory, Vol. 19, pages 471-480, "Noiseless coding of correlated information sources" published in July 1973, and described by Slepian and Wolf, as well as IEEE Transactions on InformationTol. . 22, “The rate-distortion function for source coding with side information at the decoder” published in January 1976 by Wyner and Ziv. More recently, Pradhan and Ramchandran have published “Distributed Sources CoSed USS” in IEEE Transactions on Information Theory, Vol. 49, pages 626-643, March 2003. ): Design nd Construction: In (distributed source coding using the syndromes Design and Configuration) ", describes practical commercialization of such codes.

  In essence, the syndrome code operates by using a parity check matrix H having NK rows and N columns. To compress the binary (binary) vector x of length N into a syndrome vector of length K, S = Hx is determined. Decoding often depends on the details of the specific syndrome code used. For example, if the syndrome code is based on trellis, it is well known to find the most promising source sequence X and sub-information sequence corresponding to the syndrome vector S, as described outside Pradhan. Various dynamic programming based search algorithms can be used, such as the Viterbi algorithm.

  Alternatively, if a low-density parity check syndrome code is used, Data Compression Conference (Data Compression Conference) published in March 2004, pages 282-291, “On some new applica- tions to practical Slipian-Wolf. Probability propagation decoding can be applied, as described by Coleman et al. in "compression inspired by channel coding" (some new approaches to practical Slepian-Wolf compression inspired by channel coding).

  Factor graph

  In the prior art, codes such as those described above are represented by a bipartite graph often referred to as a “factor graph”. F. R. Kschishchang, B.M. J. et al. Frey and H.C. A. Loeliger, “Factor Graphs and the Sum-Product Algorithm (factor graph and additive product algorithm)”, IEEE Transactions on Information Theory, vol. 47, pages 498-519, February 2001, and G.M. D. Forney, Jr. , “Codes on Graphs: Normal Realizations (Code for Graphs: Normal Realization”, IEEE Transactions on Information Theory, vol. 47, pages 520-549, February 2001, and RM Tanner, “A Recurp. Low-Complexity Codes ", IEEE Transactions on Information Theory, vol. 27, pages 533-547, September 1981, all of which are hereby incorporated by reference. Incorporated.

  Generally, a factor (element) graph is a bipartite graph and includes two types of nodes called “variable nodes” and “factor (element) nodes”. Variable nodes are only connected to factor nodes and vice versa. Factor nodes are conventionally drawn using rectangles, variable nodes are conventionally drawn using circles, and connections between variable nodes and factor nodes connect the corresponding circles and rectangles. Represented by a line. Sometimes a sign (symbol), or “+”, is drawn in a factor node to represent the type of constraint it enforces.

  Variable nodes represent codes used in codes, and factor nodes represent constraints on those codes. A variable node is connected to a factor node only if subject to the appropriate constraints.

  Conventional techniques for coding biometric parameters

  Prior art related to this invention falls into three categories. First of all, there are a number of prior art describing feature extraction, recording and use of biometric parameters that are not related to the secure storage of such biometric parameters. The details of this category of the prior art are omitted because the present invention is concerned with secure storage and is not primarily concerned with the details regarding how to obtain biometric parameters.

A second class of prior art related to this invention includes the following systems designed for secure storage and biometrics authentication. “Method and system for normalizing biometrics to authenticate users, authenticate users to the public database, and public data to certify biometrics to public authenticate. In US Patent 6,038,315; Proceedings of the IEEE Symposium on Security and Privacy, May 1998, Davida, G. et al. I. Frankel, Y .; Matt, B .; J. et al. “On enabling security applications through off-line biometric identification, enabling secure applications with offline biometric authentication”, Proceedings of the Society 2002, IEEE International Symposium. Sudan, M .; , "A Fuzzy Vault Scheme"; US patent application Ser. No. 09 / 994,476, filed Nov. 26, 2001, “Order invariant fuzzy commitment system”; Proc. ^{... 5 th ACM Conf on} Comp and Commun Security, New York, NY, in pgs.28-36,1999, "a fuzzy commitment scheme (fuzzy commitment scheme)" of Juels and Wattenberg;. Asilomar Conf on Signals, Systems , And Comp., Vol.1, pp.577-581, Nov. "Secure fuzzy vault based fingerprint system validation: a secure fuzzy vault based fingerprint system," S. Yang and I.M. -"Fuzzy fingerprint vault" by U. Uludag and A. Jain at August 16, August 2004.

  FIG. 2 shows some of the details of the basic method described in US Pat. No. 6,038,315. In the registration phase 210, biometric parameters are obtained 201 in the form of a sequence of bits represented by E. Next, a random codeword W202 is selected from the binary error correction code and is additively combined with the parameter E using an exclusive OR function 220 to generate a reference R 221. Optionally, the reference R can be further coded 230. In any case, the reference R is stored in the password database 240.

  In the authentication phase 220, the biometric parameter E'205 is presented for authentication. The method determines 250 XOR (exclusive OR) of R with E 'and subtracts these two to obtain 251 Z = R-E = W + E-E'. Next, this result is decoded 260 with an error correction code to generate 261 W ′. In step 270, if W 'matches W, access is allowed 271; otherwise, access is denied 272.

  The method essentially measures the Hamming distance, ie the number of bits that differ between the registered biometric E201 and the authentication biometric E'205. If the difference is less than some predetermined threshold, access is granted. This method is safe because it stores only the reference R, not the actual biometric parameter E.

  Davida et al. And Juels et al. Describe variations of the method shown in FIG. Specifically, both encode the biometric data with an error correction code during the registration phase followed by an operation to secure the resulting codeword. Outside David simply hides the codeword by sending a check bit, while outside Jewels adds some amount of noise called “chaff”.

  U.S. Pat. No. 6,363,485, entitled “Multifactor Biometric Authentication Device and Method”, provides biometric data and error correction codes and passwords, personal identification numbers (PINs), etc. to generate a secret key. It describes a method for combining confidential information. Error correction codes such as Goppa codes and BCH codes are used in various exclusive OR operations.

  In addition to the fixed database access control system illustrated in FIG. 2, the third class of prior art is data protection, specifically mobile devices including memory, such as laptops, PDAs, cell phones, and digital cameras. Using biometric authentication for data protection. Since mobile devices are easily lost or stolen, it is necessary to protect the data stored in the mobile device.

  Problems with the prior art

  FIG. 4 illustrates the problem with existing techniques for storing data D. In the encoding process 410, the biometric parameter P402 is obtained from the user and used as a key to encrypt 440 the data D and generate 441 a ciphertext C. Both biometric parameter P and ciphertext C are saved in the storage 450. When the user wants to decrypt 420 the data D, the biometric parameter P'460 is obtained from the user and compared with the stored biometric parameter P402. If P ′ matches P 470, the system allows access and uses P to decrypt 401 stored ciphertext C to generate data D, otherwise the data is not decrypted 471. .

  Such conventional systems are only effective as long as the storage medium is not compromised. However, if the adversary can access such media, the adversary gets P and decrypts the data.

  First, conventional bit-based methods provide only suspicious security. Furthermore, biometric parameters are often real or integer instead of binary (binary) values. In general, the prior art assumes that biometric parameters are composed of random (random) bits with a uniform distribution and that it is difficult to accurately distinguish these bits from the stored biometric. In practice, biometric parameters are often biased, which negatively impacts security. Also, even if only an approximate (approximate) version of the stored biometric is stored, the adversary's attack may cause significant harm. Conventional methods are not designed to prevent adversaries from estimating the actual biometric from the encoded version.

  For example, US Pat. No. 6,038,315 relies on the fact that the reference value R = W + E effectively encrypts biometric E by adding a random codeword W. By the way, the method achieves poor security. There are many ways to regenerate E from R. For example, if the vector E has only a few bits equal to 1, the Hamming distance between R and W is small. In this way, the error correction decoder may be able to easily regenerate W from R and hence E. Alternatively, for example, if the codeword distribution is poor, i.e., the code weight spectrum is small and many codewords all cluster around the zero vector, the adversary can get a good approximation from R to E. I may be able to do it.

  Second, in addition to questionable security, conventional methods have the practical disadvantage of increasing the amount of data stored. Because biometric databases often store data for a large number of individual users, the additional storage (storage) significantly increases the cost and complexity of the system.

  Third, many conventional methods require an error correction code or algorithm that has a high computational complexity. For example, the prior art Reed-Solomon and Reed-Muller decoding algorithms generally have a large quadratic computational complexity and are often coded In the biometric length, it becomes higher (larger).

  Fourth, there is a fundamental problem with the basic architecture for mobile security systems known in the prior art. A mobile security system such as that shown in FIG. 4 can only be effective if it is not compromised by itself. Returning to the example of a mobile security system on a laptop, security can only be effective if the adversary has no physical access to the media on which P and C are stored. If the adversary can access such media, for example, by removing the hard disk from the laptop, the adversary will immediately obtain the P that was the encryption key used to generate C. And C can be deciphered.

  The main difficulty with conventional mobile security systems is that a cryptographic key corresponding to the user's biometric parameters is stored on the device. In this way, if the device is stolen, the data can be decrypted using the stored parameters.

  Fifth, there are no good methods for error correction coding or syndrome code decoding for noise structures specific to biometrics (biometrics), or many considerations until modeling the noise structures Most of the prior art related to secure biometric systems is a memoryless noise model and other models that do not reflect the actual operating conditions by oversimplifying the nature of the noise. Is used. That is, conventional models do not accurately represent the dynamics of biometric features that vary with time and the process of acquisition and measurement. Instead, they assume that the noise is memoryless and has no spatial or temporal structure.

  Often, biometric features vary from one measurement to another. For example, in fingerprint biometric authentication, it is often used as a feature set in which a “minutiae” point is set. The relative location and orientation of the minutia points can vary considerably during registration and authentication. This complicates the authentication process. Most simple attempts to solve this problem use models that are impractical for practical use because they are so high-dimensional.

  It is therefore desirable to provide a model for biometric data that includes structured noise. In addition, it is desirable to pre-process biometric parameters using a channel code so that the pre-processed parameters have an optimal format for encoding and decoding.

  For example, biometric parameters obtained from human faces, voices, fingerprints, and irises can be used for user authentication and data access control. Biometric parameters are usually continuous and can be varied from one reading to the next for the same user, so they are hashed or encrypted as is done with passwords. Cannot be stored in the database in the format. For example, the sampled appearance of the face or fingerprint and the tone of the voice may change over time.

  In the first embodiment of the present invention, a syndrome code is used to protect a biometric data, for example, a syndrome code based on Winnerive or Slepian-Wolf coding. The output of the syndrome encoding we call the syndrome vector can be stored securely in the database while allowing the inherent variability of the raw biometric data.

  Specifically, the biometric syndrome vector according to the present invention has the following characteristics.

  First, the syndrome code effectively hides, or encrypts, information about the original biometric characteristics, and even if the syndrome database is compromised, the stored syndrome vector can be used to avoid system security. Make it almost useless.

  Second, even in the case of a measurement with a second noise for each biometric, the corresponding stored syndrome vector is decrypted to generate the original biometric parameter, and the original biometric parameter is encrypted. It is possible to decrypt the converted data.

  Third, the syndrome coding methodology can be used for user authentication.

  The second embodiment of the present invention is a biometric parameter that may vary due to variation (variation) in biometric characteristics over time, and further, the biometric parameter for modeling the measurement process is efficiently used. Describes how to model.

  With this method, the relationship between multiple readings of biometric features can be used computationally efficiently and accurately. In particular, the present method is much better than existing conventional methods and can successfully perform syndrome decoding of such biometric features.

  In Embodiment 1, the biometric parameters are preprocessed according to a set of logic conditions to form a binary (binary) representation having a set of predetermined statistical properties. It should be noted that statistical properties are the target properties we want to achieve.

Embodiment 1 FIG.
Embodiments of the invention include the following components:
Syndrome encoder and hashing method to securely store biometric parameters, syndrome code based encryption method to securely store data encrypted with biometric key, and the previous two methods To optimize the syndrome code used for complex biometric applications.

  Syndrome and hashing methods for secure biometric parameters

  FIG. 3 shows a biometric security system 300 based on syndrome and hashing according to the invention. The user's biometric features are measured to obtain biometric parameters (data or observations). The method according to the present invention compresses biometric parameters with a syndrome code to generate a compressed syndrome vector.

  Unlike conventional compression, the original biometric data cannot be reconstructed or approximated solely from the syndrome vector generated by the syndrome code. The syndrome vector and the hash of the original biometric parameter are stored in a biometric database.

  In order to authenticate the user, the biometric parameter is measured again. The biometric parameter is combined with the stored syndrome vector to decode the original biometric parameter. If the syndrome decoding fails, the original biometric parameters are not regenerated and the hash of the decoded parameters does not match the stored hash. Therefore, the user is denied access. If syndrome decoding is successful, the hash of the original biometric parameter matches the hash of the decoded parameter, which proves the authenticity of the user. The role of the hash is to provide user entry control and to ensure that the biometric parameters provided by the user are good enough that the original biometric parameters can be accurately reconstructed. Although both the syndrome encoder and the hash are many-to-one mapping, the syndrome code has a structure that is useful for reconstructing the original biometric parameters. On the other hand, the hash function may be, for example, a cryptographic hash, but it does not provide useful information for estimating the original biometric.

  Registration phase

  In the registration stage 310, biometric data about the physical (physical) characteristics of the user is obtained. For example, biometric data may be obtained from facial images, speech recordings, fingerprint images, or iris scans.

  Hereinafter, biometric data refers to raw biometric signals that are sensed, measured, or otherwise obtained from a user's physical characteristics. Features are extracted from biometric data. Features are arranged in d-dimensional feature vectors. The feature vector forms a registered biometric parameter 301. Methods for extracting features from various types of biometric data are well known in the art, as described above. The conversion of feature vectors into biometric parameters and the optimal syndrome code are detailed below.

  The biometric parameter E301 is encoded using the syndrome encoder 330 in order for the registered syndrome vector to generate S331. Next, a message authentication code or hash function is applied 340 to the biometric parameter E to generate a registered hash H341. The hash function may be a well-known MD5 cryptographic hash function described by Ron Rivest in RFC 1321, April 1992 “The MD5 Message Digest Algorithm”. The registered syndrome vector-hash pairs (S, H) 331 and 341 are stored in the biometric database 350.

  Any type of syndrome code, such as the SW code or WZ code described above, can be used. In the preferred embodiment of the present invention, the code derived from the so-called “repeat-accumulate code”, ie, the “product-accumulate code” and the “extended Hamming-accumulated (extended) code”. A code called “Hamming-accumulate) code” is used.

  We generally refer to these as serially concatenated cumulative (SCA) codes. See below for more information on the code of these classes in a general sense. J. et al. Li, K .; R. Narayanan, and C.I. N. Georghiades, “Product Accumulate Codes: A Class of Codes With Near-Capacity Performance and Low Decoding Complexity E”. 50, pp. 31-46, January 2004; Isaka and M.M. Fossorier, “High Rate Serially Coordinated with Extended Hammed Codes”, submitted to IEEE Communications Letters, 2004; Divsalaar and S.M. Dolinar, “Concatenation of Hamming Codes and Accumulator Codes with High Order Modulation for High Speed Decoding (Pro ss) , Feb. 15, 2004.

  Yedidia, et al. US patent application Ser. No. 10 / 928,448, filed Aug. 27, 2004, entitled “Compressing Signals Using Serially-Concatenated Accumulated Codes”. Which is incorporated herein by reference, which describes the operation of our preferred syndrome encoder based on the SCA code as used by the present invention.

  Our syndrome encoder 330 for biometric parameters 301 has many advantages. The syndrome encoder 330 can operate with an integer value input. In contrast, conventional encoders typically operate with a binary value input. The syndrome encoder has a very high compression ratio to minimize the storage requirements of the biometric database 350. The syndrome encoder can be designed to be rate adaptive and can operate in incremental fashion.

  Authentication phase

  In the authentication stage 320, biometric data is obtained again from the user. Features are extracted to obtain an authentication biometric parameter E'360. The database 350 is searched to find a matching registered syndrome vector S331 and registered hash H341.

This search can check every entry (SH pair) in the database 350, or heuristically ordered search can be used to speed up the process of finding matching entries. . Specifically, if the i-th syndrome vector-hash pair in the database is represented as (S _i , H _i ), the syndrome decoding is _first applied to E ′ and S ₁ by exhaustive search, and the syndrome decoder a hash of the output compared to the H _1. If access is denied, the same process is attempted at (S ₂ , H ₂ ) and then until all entries are attempted, such as (S ₃ , H ₃ ), or until access is also granted. Executed.

  Searches can be accelerated if other information such as registered user names are available. For example, a hash of the registered username (which should not be confused with the hash H of the biometric parameter) is stored with the pair S and H during the registration phase. Next, in the authentication stage, the user provides an authentication user name, and the system determines the hash of the authentication user name and stores the database for the SH pair with the hashed registered user name that matches. Search and attempt to authenticate E ′ with the resulting SH pair.

  Specifically, the syndrome decoder 370 is applied to the registered syndrome vector S, where the authentication parameter E ′ 360 serves as “sub” information. Syndrome decoders are generally known in the art. Typically, decoders using belief propagation or turbo codes have excellent error resiliency with low complexity. The output of the syndrome decoder 370 is a decoded registration parameter E ″ 371. The decoded value E ″ 371 is an estimate of the original biometric parameter E301 used to generate the syndrome vector S331. The hash function 340 is applied to E ″ 371 to generate an authentication hash H ′ 381.

  The registered value and the authentication values H341 and H'381 are compared 390 with each other. If the values do not match, access is denied 392. Otherwise, the value E ″ 381 substantially (substantially) matches the original biometric E301. In this case, the user can be granted access 391.

  Also, the decoded parameter E "381 and the authentication biometric parameter E'360 may be directly compared to authenticate the user. For example, E 'and E" correspond to the biometric parameter in the face recognition system. If so, a conventional algorithm for comparing the similarity between faces may be applied to the parameters E ′ and E ″.

  Data encryption based on syndrome

  FIG. 5 shows a method 500 for encoding 510 and decoding 520 data 501. In the encoding process 510, an initial biometric parameter P502 is obtained from the first user. The parameter is used to encrypt 540 the input data D501 to generate the ciphertext C541. Incidentally, in contrast to the prior art, the first biometric parameter P is never stored in memory. Instead, the syndrome encoder 530 encodes the first biometric parameter P to generate the syndrome vector S531, and the pair (S, C) is associated with each other and stored in the memory 550. In Embodiment 1 of the present invention, the input data is raw biometric data obtained from the user during the registration process.

  When a person wishes to decrypt 520 the ciphertext 541, the biometric parameter P'560 is obtained from the second user. The stored syndrome vector C531 is syndrome decoded using the second biometric parameter to generate a third biometric parameter P "571. The third biometric parameter P" Used to decrypt 580 the ciphertext 541 to generate D′ 509. Obviously, if the second or third biometric parameter does not match the first biometric parameter, the output data D'509 will not match the input data D501. The output data will match the input data only if the first user and the second user are exactly the same person.

  In the first embodiment of the present invention, the hash H of the biometric parameter can also be stored as described above. Check that the hashes match to confirm that the decryption was successful. Without the hash, security is maintained, but the decoder cannot confirm that the decryption was successful. For many types of source data, a hash is not necessary because the files resulting from inaccurate decryption do not correspond to anything useful.

  This method has the following advantages. Even if the adversary gains access to the syndrome vector and ciphertext (S, C), the data cannot be decrypted. This is because the encryption key, that is, the first biometric parameter P cannot be reproduced from the syndrome vector. In addition, even if the second biometric parameter P ′ is slightly different from the first biometric parameter P due to the error correction characteristics of the syndrome code, the appropriately designed syndrome decoder is used as the encryption key P502. The third biometric parameter P ″, which is exactly the same as the biometric parameter, can be successfully generated.

  Syndrome coding provides an effective way to securely store biometric parameters, and can also be applied to other methods for securely storing biometric information. It should be noted that feature vectors can be extracted from biometric data. Thus, any of the biometric parameters described above can be substituted with a corresponding feature vector.

  An additional advantage of storing biometric parameters in encrypted form is that this is a secure biometric storage application (applied to biometric storage) used in a biometric recognition application (applied to biometric recognition) It is possible to operate with a different feature vector than what has been done. For example, fingerprint recognition systems often use feature vectors based on so-called “minutiaes” extracted from fingerprint images. Similarly, an iris recognition system may use features extracted by passing an iris image through a row of Gabor filters.

  In many cases, the ideal feature vector for biometric recognition (eg, face authentication or fingerprint identification) may be different from the ideal feature vector for syndrome coding / decoding. In many cases, this trains a classifier for a recognition or identification system, eg, a Gaussian mixture model (GMM), or a neural network, or a classifier based on a hidden Markov model. The process for doing this is by generating a feature vector that is different from the process used to train the histogram used with the syndrome encoder and the probability propagation decoder of the decoder.

  FIG. 6 shows a method 600 for storing an encrypted version of the input biometric data 601. As described above, biometric data is obtained from raw signals that are used to measure or sense a user's biometric characteristics.

  In the registration step 610 of the access control system, for example, initial biometric data B601 is obtained from the user. Next, a feature vector of the first biometric parameter P602 is obtained from the first biometric data B601. The first biometric data B is encrypted 640 using the first biometric parameter P as an encryption key to generate ciphertext C641. Further, the first biometric parameter is syndrome coded to generate a syndrome vector S631. Then, the associated pair (S, C) is stored in the biometric database 650.

  In the authentication stage 620, second biometric data B'660 for authentication is obtained from the user. This second data is used to generate a feature vector for the second biometric parameter P'661. The syndrome decoder 670 then decrypts the first biometric parameter to generate a third biometric parameter P ″ 671. Next, the ciphertext C is generated using the third biometric parameter as a key. Decoding 680 generates third biometric data B ″ 681. The authenticated biometric data B ′ and the decrypted biometric data B ″ are then compared by the biometric recognition method 690 to determine 692 whether access to the specific function is permitted or denied. As such, access is permitted only if the first and third biometric data are exactly the same, i.e., if the first and next users are the same person.

  In another variation, the comparison step can use feature vectors extracted from biometric data. Their feature vectors need not be the same as the biometric parameters. Furthermore, since the verification step can use a completely different process, the two feature vectors being compared need only be (substantially) the same. In this way, the feature vector can tolerate a wider range of variation (variation) in biometric data that characterizes a particular user over time.

  We enumerate several advantages of the process shown in FIG. The authentication system can use a conventional recognition system at step 690. Also, the biometric parameters P and P ′ used by the syndrome encoder / decoder can be selected regardless of the parameters or feature vectors used by the biometric verification step 690. Moreover, syndrome coding is an effective way to store biometric parameters securely. By the way, the method shown in FIG. 6 can be applied to other methods for securely storing biometric parameters.

  Optimal syndrome code design for safe biometric parameters

  In general, there is a trade-off between security and accuracy when using syndrome codes to protect biometric parameters and biometric features. Specifically, the key parameter of any syndrome code is the number of bits in the syndrome vector. A syndrome vector with many bits conveys more information about the biometric data, making it easier to tolerate noise and fluctuations in the biometric data. In contrast, smaller syndrome vectors provide less information to the adversary, but tend to be more prone to errors.

  In some extreme cases, if the length of the syndrome vector is approximately the same as the length of the underlying biometric data, the original biometric data can be accurately reproduced from only the syndrome vector, allowing any amount of noise. it can. Of course, in this case, the adversary who obtains the syndrome vector can also reproduce the biometric data, thus jeopardizing the security of the system.

  In contrast, a syndrome vector with very few bits provides very good security in the sense that an adversary cannot reproduce biometric data from that syndrome vector. However, in this case, the allowable variation between the registered biometric data and the authentication biometric data is limited (small).

  Clearly, syndrome-based encoders and decoders should choose a length for the syndrome vector that balances security and tolerance for biometric variation. By the way, a carefully designed syndrome code can improve error resilience.

  As shown in FIG. 12, the following terms describe the design and operation of the syndrome code. The biometric data 1201 may be a face or fingerprint image, for example. A complete feature vector 1202 is extracted from the training biometric data. The complete feature vector 1202 is reduced to the syndrome feature vector 1203. The syndrome feature vector captures the portion of the complete feature vector that the designer deems appropriate for syndrome coding and decoding. A syndrome code is used to encode the syndrome vector 1204 from the syndrome feature vector. The syndrome feature vector 1203 plays the role of the biometric parameter E310 in FIG. 3, while the syndrome vector is S331.

  Biometric statistical model

  FIG. 13 shows a process 1300 for configuring syndrome code 1204 and corresponding decoder 1205 (ie, encoder and decoder) according to an embodiment of the invention. Training biometric data 1301 is acquired. The parameter 1302 of the selected feature model 1304 is determined 1310 from the training data. With respect to codecs, the feature model is essentially a “source” model. Similarly, the parameter 1303 of the selected measurement model 1305 is determined 1320. The measurement model is essentially a “channel” model. Parameters 1302-1303 and models 1304-1305 are then used to construct the syndrome code and corresponding decoder. It should be noted that the channel model is designed to deal with structured noise in the measurement process. This noise can be caused, for example, by changes in the characteristics of the biometric data as observed in different measurement instances, or by insertion and deletion of features between instances.

  Although many tools for machine learning can be useful in the design process described above, this problem is often encountered in machine learning because the resulting model has the appropriate “hard” feature vectors for syndrome coding. This is quite different from the modeling problem. The differences between “hard” and “soft” feature vectors are discussed in detail below.

  As shown in FIG. 12, the syndrome feature vector 1203 is typically reduced in size to facilitate handling of syndrome decoding. In order to construct a syndrome code, a density evolution can be applied to a degree distribution. The syndrome code takes into account features such as the finite block length of the syndrome feature vector 1203 or the need to use a variable rate code to match the syndrome vector 1204 to variations in biometric features across users. Further refined to get into.

  After the syndrome code is constructed and selected, an iterative probability propagation decoder is constructed as described below.

  Quantization

  Prior to elaborating the instance 700 of the process 1300 shown in FIG. 7, first the following terms are defined that distinguish between the use of biometric data during registration and during authentication. Use the term “hard” feature vector to refer to a quantized version of a feature vector, and the term “soft” feature vector to refer to a non-quantized feature vector or a version of a finely quantized feature vector Is used.

  Quantization is used because some biometric parameters can include integers and real numbers over a relatively large numerical range. Encryption, key issuance, and other authentication processes work best with integers over a small range.

  The reason for distinguishing the “hard” feature vector from the “soft” feature vector is that the syndrome vector is obtained from the “hard” feature vector. Thus, “hard” feature vectors are usually quantized. In contrast, during the authentication phase, the syndrome decoder may combine the “soft” feature vector with the syndrome vector to decode the “hard” feature vector. Thus, “soft” feature vectors need not be quantized, or can be quantized differently to reduce errors in the system. For example, the use of soft feature vectors allows the syndrome decoder to take each feature's likelihoods as an input, rather than the hardest possible choice of each feature.

  In general, there are multiple methods for extracting complete feature vectors from biometric data, and there are multiple methods for extracting “hard” and “soft” feature vectors from complete feature vectors. Accordingly, the process of FIG. 13 is applied to each possibility to select the syndrome feature vector 1304 that yields the best overall result during training.

  FIG. 7 shows details of an instance of process 1300 for constructing an optimal syndrome, where the statistical model for biometric feature 1304 represents a Markov relationship between biometric features. Training biometric data is acquired 800. The biometric data is used to generate an error histogram 890. The error histogram is used to select 900 the syndrome feature vector. In such a relationship, the term “perfect feature vector” 1202 (see FIG. 12) is used to represent all biometric parameters, and “syndrome feature” is used to represent a subset of the complete feature vector. The term “vector” 1203 is used. The syndrome feature vector can be transformed into an arbitrary feature space.

  After the syndrome feature vector 1203 is selected, we measure 1000 the correlation between the different coefficients of the syndrome feature vector. Next, by using error statistics for the syndrome feature vector and the correlation between the coefficients, density evolution 740 is applied to find the frequency distribution that yields the optimal syndrome code 1204 of a given length. After the syndrome feature vector and the syndrome code are selected, a probability propagation decoder that uses the correlation between coefficients is configured 1100.

  Configure error histogram

  FIG. 8 shows a process 800 for generating an error histogram 890. Initially, training biometric data is acquired 810 for a particular user taken on different occasions. Next, a pair of biometric parameters B and B ′ are selected 820 to determine a complete “soft” feature vector VS (B) 830 and a complete “hard” feature vector VH (B ′) 840. Then, for each feature or dimension i in the complete feature vector, the value of VH (B ′) at the corresponding feature i is estimated 845 from the VS (B) at position i, and the estimated value is It is determined 850 whether or not it is correct. If the estimate is not correct, increment the bin for the corresponding values of VH (B ′) and VS (B) at feature i in the error histogram 890. After completing this process for each feature i, check 860 whether all pairs of biometrics B and B 'have been processed. Otherwise, return to step 820 to select another pair of biometric parameters. If all pairs have already been processed, the error histogram is complete and the process ends 880.

  Syndrome feature vector selection

  FIG. 9 shows a process 900 for selecting syndrome feature vectors with the assistance of the error histogram of FIG. First, the error histogram is sorted from the most reliable feature to the lowest feature 920. Specifically, if E (i) is an average error in predicting the feature i of VH (B ′) from the feature i of VS (B), the feature i is E (i) <E (j ) Is considered to be more reliable than the feature j. After the error histogram is sorted, the next most reliable feature from the error histogram is included in the syndrome feature vector 930, the best syndrome code for the current syndrome feature vector is constructed 940, and including the latest feature is security or Test 950 whether to increase error resiliency. If security or error resilience increases, additional features continue to be added to the syndrome feature vector. Otherwise, remove the most recently added feature from the feature vector 960 and end the process 970.

  If it is desired to specify a level of security and optimize error resiliency, the following steps can be used for steps 940 and 950: First, in step 940, a new syndrome code of length N corresponding to the number of current features in the feature vector by generating a low density parity check (LDPC) code with k syndrome from a fixed frequency distribution. Is configured. In this case, the level of security is kept constant by fixing the quantity N−k and keeping it constant during the process. A random biometric sample of the biometric data is then selected from the database and mapped to a syndrome vector by applying a parity check matrix of the LDPC code, and the resulting syndrome vector is different from the same user. Decoded using probability propagation applied to random biometric samples. By repeating this many times, an estimated value of the error resilience of the syndrome code for the given feature vector is generated. Alternatively, if further computational complexity is acceptable in the design process, the density evolution process can be used to optimize the frequency distribution for the code and estimate the error probability more accurately. In this regard, T.W. J. et al. Richardson, M.C. A. Shorollahi, and R.A. L. Urbane, discused, “Design of capacity-apprachable irregular low-density parity-check codes”, IEEE Transactions, Vol. 47, Theory, Vol. 619-637, February 2001. This document is incorporated herein by reference.

  If it is desired to specify the level of error resiliency and obtain the highest security, the following steps can be used for steps 940 and 950: First, in step 940, a new syndrome code of length N corresponding to the number of current features in the feature vector is designed using density evolution. Specifically, a series of different rate codes is constructed using density evolution until the highest rate code that meets a certain level of error resiliency is found, as assessed by density evolution.

  The feature vector selected by this process is referred to as the “syndrome feature vector” because it is a feature vector specifically designed for the syndrome code. It should be noted that this feature vector can have different characteristics than other types of feature vectors configured for biometric recognition, such as face or object recognition.

  Measure correlation between coefficients

  After the syndrome feature vector is selected, the next step is to measure the correlation between the coefficients if the data are believed to be correlated with each other. Since the error histogram is generated for the complete feature vector 1202 according to FIG. 7, this information cannot be extracted from the error histogram. Step 900 selects only a subset of the features in the complete feature vector to generate a syndrome feature vector 1203.

  FIG. 10 shows a process 1000 for measuring first order correlations in binary (binary) syndrome feature vectors. This process can also be applied to non-binary feature vectors or higher order correlations. First, an element is selected from the biometric training data set, and a syndrome feature vector is extracted from that element. The counter variable i is then initialized 1010 to zero. Next, it is inspected whether the feature i is 0 or 1, and if it is the former (ie, 0), the process proceeds to step 1030, and if it is the latter (ie, 1), the process proceeds to step 1040. Thereafter, it is checked whether the feature i-1, that is, the previous feature was 0 or 1, and the appropriate bin in the histogram is incremented 1035. Intuitively, class p00 counts the appearance of a0 followed by a0, class p01 counts the appearance of a0 followed by a1, and so on. The counter i is then incremented 1050 to check 1060 for additional (unprocessed) features remaining in the syndrome feature vector and the process is repeated for the next feature. Otherwise, that is, if each feature has already been processed, the process ends 1070.

  After the process of FIG. 10 has been performed for each element of the biometric training set (biometric training set), the values of the classes p00, p01, p10, and p11 are used to measure the primary correlation of the syndrome feature vectors. Is divided by the size of the biometric training set.

  Use density evolution to construct optimal syndrome code

  After the syndrome feature vector 1203 is selected and the inter-coefficient correlation is measured, the syndrome code 1204 is designed using density evolution. Specifically, a frequency distribution for the syndrome code is designed for the LDPC syndrome code.

  In order to actually construct the optimality distribution, a density evolution technique is applied to generate several candidate frequency distributions.

  By the way, the conventional density evolution process as known in the art does not consider the correlation between coefficients. Thus, the candidate frequency distribution generated by density evolution may be appropriate for cases where there is no correlation between coefficients, but in general there is a different behavior when there is a correlation between coefficients. To do.

  In order to obtain the best frequency distribution for the syndrome code, the candidate frequency distributions obtained by density evolution in the biometric training data set are compared to select the frequency distribution that performs best. In an alternative embodiment, the conventional density evolution algorithm is modified to take into account the correlation between coefficients.

  Construct a probability propagation decoder for syndrome codes

  The final step in designing the syndrome code is to configure an associated probability propagation syndrome decoder 1205.

  FIG. 11A shows a high-level structure of the registration stage, where the encoder 330 uses the syndrome code 1102 to generate a syndrome vector 1204 from the syndrome feature vector 1203.

  FIG. 11B shows the structure for a complementary decoder 1107 used during the authentication phase. Again, a noisy observation of biometric data 1104 is obtained for a user attempting authentication. In order to decode 1107 and generate 1107 estimates of the original syndrome feature vector 1203, the biometric data 1104, along with its measurement model 1305 (and measurement model parameters 1303), is an iterative probability propagation network (factor graph). In conjunction with the syndrome vector 1204 and the feature model 1304 (and its feature model parameters 1302). If the decoding is successful, the estimated syndrome feature vector 1108 matches the original syndrome feature vector 1203.

  As shown in FIG. 11C, our probability propagation factor graph configuration 1100 includes a feature model 1304 (and model parameters 1302) in addition to a syndrome code 1102 and a check node (+) 1110 that identifies a variable node (=) 1120. Correlation node (C) 1130 that identifies). Specifically, correlation nodes are added between each pair of consecutive variable nodes. The method of distributing messages from variable nodes to adjacent check nodes is modified to include additional messages from each adjacent correlation factor node that are multiplied by other messages.

Specifically, using a notation outside Kschishchang, μ _y → f (x) is an input message for state x from check f to variable node y, and L (x) is from the left correlation node. If it is an input message, an output message from the variable node to the right correlation node is expressed by the following equation.
L (x) · Πμ _y → _f (x),
On the other hand, the output message to the left correlation node is expressed by the following equation.
R (x) · Πμ _y → _f (x),
Here, R (x) is an input message from the right correlation node.

A method for distributing (input / output) a message to / from the correlation node according to the embodiment of the present invention will also be described. Specifically, a processing procedure for determining the messages L (x) and R (x) will be described. If μ (0) is an input message to the left correlation node, an output message to the right side of the correlation node, that is, an input message to the variable node on the right side of the correlation node, is expressed by the following equation. Is done.
L (0) = p00 · μ (0) + p10 · μ (1) and L (1) = p10 · μ (0) + p11 · μ (1),
Here, the terms p00, p01, p10, and p11 are measured primary correlation values as shown in FIG.

  Similarly, an output message on the left side of the correlation node, that is, an input message to the variable node on the left side of the correlation node is expressed by the following expression.

  R (0) = p00 · μ (0) + p01 · μ (1) and R (1) = p01 · μ (0) + p11 · μ (1).

  Syndrome code design for iris biometric parameters

  Next, the application of processing procedure 700 to specific cases of iris biometric parameters will be described. The complete “hard” feature vector can be found in “How iris recognition works”, by J. Daugman in IEEE Transactions on Circuits and Systems for Video Technology, Volume 14, Issue 1, Jan. Selected to be a sequence of bits extracted from a set of Gabor filters, as described in 2004 pages 21-30. This document is incorporated herein by reference.

  The full “hard” feature vector is binary (binary), while the full “soft” feature vector is chosen to be quadrantary (quaternary). Specifically, the value of the complete “soft” feature vector of feature i is selected such that the feature is the best guess in the “hard” feature vector, and a bit indicating the confidence level (confidence) is added Is done. Specifically, a bit indicating whether or not there is confidence in the determination for the feature is added.

  For example, some features of a “hard” feature vector may be difficult to predict. This is because, for example, those features should be covered by eyelashes or eyelashes and receive a confidence value of “not confident”.

  Next, as described above for FIG. 8, the biometric training data is used to create an error histogram, and then the feature vector design method of FIG. 9 is applied. Although the complete feature vector has a length of about 10,000, we have found that many features 1202 are unreliable. For example, the feature vector component corresponding to the upper edge of the eye is often covered with eyelashes or eyelashes. After the least reliable features are discarded by the procedure of FIG. 9, approximately 2,000 most reliable features in the syndrome feature vector are left.

  Stopping at step 900 in FIG. 7, the resulting syndrome vector will not have an error resiliency that can tolerate natural variations in iris biometric parameters for a single user. . Specifically, the syndrome vector coded with the user's iris measurements taken on one day combined with measurements from the same iris taken on different days is about 12% decoding at that time. Fail. This justifies the need for the remaining steps in FIG.

  After measuring the first order correlation using the procedure of FIG. 10, we have the possibility (possibility) that a bit in the “hard” syndrome feature vector will take the same value as the neighboring bit, It was detected that it was about twice the likelihood (possibility) of taking a value. We then continued step 740 of FIG. 7 to construct an optimized syndrome code using density evolution to take advantage of the high correlation. Finally, a probability propagation decoder was configured according to step 1100 to take into account high first order correlation.

  By following these steps, we can generate a syndrome code that is more than an order of magnitude more reliable than our initial code, thus demonstrating the benefits of following the overall procedure of FIG.

  Syndrome code for fingerprint feature

  Procedure 1300 is applied to the fingerprint. Fingerprint based systems are generally based on patterns or on minutiae (features). Here, the latter is used. Extract feature vectors from fingerprint minutia. Although the general procedure 1300 can be applied to most biometric data, we describe the details of the procedure for fingerprint minutiae. Fingerprint minutia can vary in its characteristics over time and the measurement process is susceptible to structured noise.

  FIG. 14 shows an example fingerprint 1401 and extracted feature vectors 1402. The extracted feature vector 1402 is an example of the syndrome feature vector 1203. Features are only measured in the measurement field (observation window) 1403. For convenience, the minutiae is shown as a grid-like square. Each minutiae is mapped to a triplet, for example, (a, b, c) represents the spatial position coordinates (a, b) and the angle (c) of the minutiae. As described below, one minutiae can be designated as the “core” for alignment purposes.

  Since the plane on which the fingerprint 1401 is measured is quantized by a digital sensor having an array of pixels, the features are stored as a matrix. Each sensor pixel corresponds to a particular entry in matrix 1402. The presence (existence) of the minutiae is represented by “1”, but the absence (absence) of the detected minutiae is represented by “0” in the matrix 1402. In a more general representation, instead of “1” meaning the presence of a minutiae, the entry in the matrix would be the minutiae angle c.

The number, position, and angle of the minutiae vary from one measurement of the fingerprint to the next. For example, if a minutia exists at (74, 52, 36 ^o ) in one measurement, it may appear as (80, 45, 63 ^o ) or not at all in another measurement.

  For a variety of reasons, this variability of the minutia from one measurement to the next creates problems for many conventional methods for processing fingerprints.

  Variability of obvious biometric data

  As shown in the figure at 15A-15C, our model can handle variability in biometric data. In these figures, the dashed line 1500 indicates a local neighborhood. FIG. 15A shows the maneuver motion 1501 (pi, j). FIG. 15B shows the deletion pe 1502, and FIG. 15C shows the insertion ps.

  FIGS. 16A and 16B show high-level and low-level details, respectively, of a factor graph 1600 used to implement belief propagation decoding 1107 according to an embodiment of the invention.

  At a high level, the biometric data 1201 is used to generate a syndrome feature vector 1203 that is used to generate a syndrome vector 1204. However, the syndrome feature vector 1203 is not known by the decoder, but the syndrome vector 1204 is known. The syndrome vector 1204 and the syndrome feature vector 1203 are related by the code structure 1623. The decoder also obtains a noisy measurement of biometric data 1104. The noise structure is described by a statistical model 1305. Along with the syndrome vector 1203, the code structure 1623, observation 1104, and measurement model 1305 are used to perform decoding 1107 to generate an estimate 1108 of the original syndrome feature vector 1203.

  FIG. 16B shows a low-level structure of a factor graph 1600 that describes a statistical model of a syndrome feature vector, a syndrome vector, and a noisy observation.

  Each location t in the feature vector grid 1402 has a corresponding binary random variable x [t] node 1609 in the factor graph 1600. This random variable is a minutiae that exists at location t during registration and is zero otherwise.

  The association between the grid position of the feature vector and the label t can be arbitrary, for example, a raster scan order. The two-dimensional nature of feature sets is also taken into account in our model.

  For each grid position, there is a prior probability that a minutiae exists during registration. This prior probability, Pr [x [t] = 1], is represented by a factor node 1608.

  For each position of the variable node 1609 for that registered grid, there is a corresponding position node 1601 for the corresponding authentication grid. The presence of a minutiae at the grid position t during authentication is represented by a binary (binary) random variable y [t]. This variable is equal to 1 if a minutia is present in the probe, otherwise equal to zero. The goal of the factor graph is to represent the simultaneous distribution of the first fingerprint measurement during registration and the second measurement during authentication.

  In our model, each registered position has a probability that the maneuver at position t will move to a position near position t in the probe if x [t] = 1, or in the case of deletion. , Not measured.

  A variable 1604 represents a relative change in the position of the registered minutiae, and a factor node 1603 represents a prior probability distribution relating to the movement and probability of the inserted minutiae. In particular, for the one-dimensional movement model shown in FIG. 16B, z [t] = i indicates that the minutiae at position x [t + i] at the time of registration moves to position z [t] at the time of authentication. More generally, and in our implementation, we use a two-dimensional movement model.

  Such a domain (neighborhood) of the displacement (movement) {i} is a design parameter represented by a broken line 1500. If the variable z [t] = s, a false minutiae is inserted at the position t during authentication, and z [t] = * indicates that no minutiae exist at the time t during authentication. There is an exact correspondence between a variable z [t] such as z [t] = * and a variable y [t] such as y [t] = 0.

  To represent a constraint that a registered minutia at position t, ie x [t] = 1, can only account for at most one observed minutia in the vicinity of t, we include a factor node 1607. A random variable h [t] 1606 connected to these nodes is a binary variable representing deletion of x [t]. Deletions can result from minutiaes that have not been detected or extracted, or false minutiaes that have been detected at registration, or large movements. Node 1605 represents a prior distribution for each h [t].

  A factor node 1602 that connects each node y [t] to its corresponding node z [t] states that each authentication minutia y [t] must be non-zero only if the corresponding node z [t] is not *. Represents a concept.

  The constraints that arise from the syndrome code 1102 are added to this model. Each syndrome node s [i] 1611 satisfies the local code constraint 1610, which is equal to 1 if the value of the syndrome matches the feature vector x1, x2,. A characteristic function equal to zero.

  The direction of those minutiae can be added to the factor graph. To add orientation information, the registration node 1609 indicates both the position t and orientation for the minutiae. This information is reflected in the prior probability node 1608. In order to adapt the azimuth at the time of registration to the hard feature vector necessary for syndrome coding, the azimuth at the time of registration is quantized.

  The vector of syndrome bits 1611 is encoded in the same manner as above, but this time from the vector of registration variables 1609 representing the presence or absence of the minutiae and the orientation, if any. The prior probability of deletion 1605 remains unchanged, similar to the constraint 1607 regarding movement. The prior probabilities for move and insert 1604 also remain unchanged. The constraint node on the authentication node 1602 is changed to reflect the concept that there will be less change in orientation between the registration node 1609 and the authentication node 1601.

  Message passing rules and optimization

  Given the measurement and movement model represented by the factor graph 1600, message passing rules can be derived by using conventional techniques. The following describes some simplifications for passing messages to achieve complexity reduction.

  The first simplification is related to messages from constraint node 1602. We “remove excess” from the factor graph to remove unobserved minutiae. Specifically, according to the format of constraint 1602, if y [t] = 0, the only non-zero message from node 1602 to z [t] variable node 1604 is for state z [t] = *. is there.

  As a result, the only non-zero message z [t] sent to the adjacent node 1607 is for the * state. We can assume that this constant message is normalized to unity. For example, if y [t] = y [t + 2] = y [t + 4] = y [t + 5] = *, instead of using the complete factor graph of FIG. 16B, to derive the necessary message passing action: As shown in FIG. 17, a graph 1700 from which excess is removed is used. This leads to a significant reduction in the complexity of message calculations for node 1607.

  A second simplification is obtained by computing the messages going in and out of the factor node 1607. It is not necessary to use the complete message from the z [t] variable node. Instead, these messages can be reduced to binary messages that indicate whether the minutiae at x [t '] moves to the position corresponding to position z [t]. By using binary information for the node z [t], it is possible to reduce the amount of calculation considerably.

By calculating a set of intermediate quantities first and then reusing these intermediate quantities, a third simplification for various rules can be achieved. For example, the output message from variable node z [t] is the product of the input messages from all other nodes. If there are K connections to the variable node z [t], a simple implementation of this rule must combine messages from the other K-1 connections, so an operation proportional to K ² is performed. I need. To do this more efficiently, all messages coming into node z [t] are combined once in the process of calculating a marginal probability for node z [t]. Then, to obtain an output message for a particular connection, all messages are divided or subtracted by the input message from that connection in the log-likelihood domain.

  Also, similar reuse of intermediate quantities can be applied when calculating output messages from triangle nodes. In particular, let z '[t] represent a binary message from variable node z [t] to node 1607 at position t'. The quantity z ′ [t] indicates whether the minutiae moves from position t ′ to position t during authentication. A simple sum-product rule for node 1607 for these binary messages requires 1604 to accumulate over all possible combinations of variable nodes connected to node 1607 at position t ′. To do. For example, if node 1607 at location t ′ is connected to nodes z [1], z [2], z [3] and z [4], computing the message to z ′ [1] Requires integration over all possible combinations of z ′ [2], z ′ [3] and z ′ [4]. This method has exponential computational complexity with the number of variable nodes connected to each triangle node.

  By realizing that the constraint node 1607 allows at most one of the z '[t] nodes to be non-zero, this exponential complexity can be eliminated. In this way, each output message for node z ′ [t] is the same as the term corresponding to all other nodes z ′ [t] being zero and one node being zero. And terms corresponding to all nodes z ′ [t]. By precomputing these terms, the message passing rules for factor node 1607 can be reduced from exponential complexity in the number of connections to linear functional complexity in the number of connections.

  Collect statistics for biometric parameters

  FIG. 18 shows a process 1800 for setting the parameters 1303 of the factor graph 1600, ie the model according to the invention. Biometric training data 1301 is acquired. An unprocessed fingerprint F is selected 1802. An unprocessed pair of measurements B and B ′ of fingerprint F is selected 1803. Their respective minutiae M (B) and M (B ′) are determined 1804. The minutiae is compared 1805 to determine 1806 movement, rotation, insertion and deletion statistics. The statistics are used to revise 1807 the statistics in the factor graph. If there is a pair of measured values of fingerprint F that have not yet been processed 1808, the process returns to step 1803. Otherwise, if there is a fingerprint that has not been processed 1809, the process returns to step 1802. After all fingerprints and their minutiae pairs have been processed, statistics collection is complete at step 1810.

  Data alignment

  In biometric systems, registered biometric data is often misaligned with respect to authentication data. Different measurements of the same biometric data often fluctuate due to global transformations such as translation, rotation, scaling. Such variability is less of an issue with pattern-based biometric authentication, ie, authentication schemes that do not use syndrome coding.

  In contrast, in our system, only the registered biometric parameter syndrome vector 331 is available for comparison. Thus, searching across different alignments (sequences, arrangements) involves decoding for each possible alignment. The minutiae movement model can handle fine misalignment, but it is desirable to minimize the search space in order to minimize the computational cost of decoding.

  FIG. 19 shows each step of the fingerprint alignment process (alignment process) during registration or authentication according to the embodiment of the present invention. A fingerprint is acquired 1901 and the minutiae parameters are extracted 1902 along with the location and orientation of the core (center) point. The core point and orientation define an inertial reference frame for the fingerprint, where the location of the core point is the origin and the orientation functions as the Y axis. The position and orientation of the minutiae relative to the inertial reference frame associated with that core point is recalculated 1903. The result 1904 is a set of minutiae measured at the reference frame for the fingerprint.

  As an advantage, this procedure can eliminate most or all of the effects of translation and rotation. Typically, such preprocessing is combined with a computationally more powerful (intensive) local search (local search) where decoding is performed with a lesser set of translations and rotations. This pre-processing procedure can be used as part of the minutiae extraction routine.

  Revision after parameter alignment (revision)

  Each time the registration and authentication biometric features are displaced relative to each other prior to decoding, the parameters of the factor graph are changed to reflect this displacement. An example of this is when the registration and authentication function is transitioned by the alignment procedure 1900 or by a number of small displacements corresponding to a local search.

  Depending on the displacement and the relative size of the registration and authentication observation window 1403 (see FIG. 14), some registered feature positions may not be observed at all during authentication. Therefore, the factor graph is changed to reflect this by setting the probability of maneuver elimination to 1 for these unobserved positions. This is reflected in FIG. 16B by setting the erase probability at factor node 1605 equal to one. For minutia near the edge of the window 1403 that has some likelihood to be observed and some not to be observed, its prior probability 1605 is changed accordingly.

  Syndrome pretreatment

  In the biometric security system 300 of FIG. 3, the biometric parameters 301 are input directly to the syndrome encoder 330 during the registration phase. Similarly, in the authentication phase, the biometric parameter 360 is input directly to the syndrome decoder 370.

  FIG. 14 displays the position of the minutiae, which is often used as a biometric parameter for the fingerprint. There are several problems with using this display in a syndrome-based framework for biometric security systems such as those described in FIGS.

  First, the display is sparse and difficult to model. The model shown in FIG. 15 attempts to model movements, insertions and deletions specific to the minutiae. However, these models are complex.

  Second, the display is not well suited for conventional syndrome codes. Even though the representation is in the form of binary data, the data is skewed and does not have inherent statistical properties that provide high performance when conventional channel codes and corresponding decoding methods are applied to the data .

  Its performance can be improved by designing a new syndrome code that accounts for the biased nature of the source and the asymmetry of the measurement channel. This is an interesting and complex process.

  FIG. 20 shows a method for syndrome coding biometric parameters according to an embodiment of the present invention. The first biometric parameter 2010 is obtained from the user, for example during the registration phase 10 (see FIG. 1). First biometric parameter 2010 is syndrome preprocessed 2020 to generate a binary representation of biometric parameter 2030. Pre-processing 2020 applies a set (one or more) of binary logic conditions 2022 to the acquired biometric parameters 2010. A set of binary logic conditions 2022 forces or attempts to have the binary representation 2030 have a set (one or more) of desired predetermined statistical properties 2025. The set of predetermined statistical properties 2025 is further described below. The binary representation of the biometric parameter 2030 is syndrome encoded 2040 to generate a first syndrome 2050. It should be noted here that logic conditions can attempt to achieve the target statistical property. It should also be noted that the statistical properties can be adjusted dynamically during the process.

  The first syndrome can then be further processed to generate a registration hash by applying a hash function, and the generated registration hash is then used for later authentication of the user. Can be stored with the vector.

  We specifically design our encoder 2040 to be compatible with the binary representation 2030 and the desired statistical properties 2025. We believe that adapting the encoding to the binary representation and desirable statistical properties will improve the performance and reliability of our system.

  FIG. 21 shows details of the method of syndrome decoding according to the embodiment of the present invention. The biometric parameters are obtained again, for example during the authentication phase 20. Second biometric parameter 2110 is syndrome preprocessed 2020 to generate a binary representation of biometric parameter 2130. As described above, the binary representation 2130 has the same set of desirable predetermined statistical properties 2025 that are imposed during registration. The preprocessed binary representation 2130 is then used as an input to the syndrome decoding 2140 to produce a reconstructed biometric parameter 2145. As mentioned above, the decoder is compatible with binary representations that have desirable statistical properties. Improve the performance and reliability of our system by adapting the encoding and decoding to binary representations and desirable statistical properties.

  If the first and second biometric parameters are from the same person, even if the biometric parameters from the first and second parameters are different in detail, the reconstructed biometric parameters are Must be the same as the first biometric parameter.

  The syndrome pretreatment described herein is applicable to the methods shown in FIGS.

  Desired target statistical properties

  Syndrome pre-processing 2020 is used to transform biometric parameters into a binary representation or string with the desired statistical properties 2025. These properties are considered to be target properties because they may not always be obtained.

  The statistical nature ensures that the syndrome code can achieve optimal performance. Our pre-processing 2020 greatly reduces the complexity involved in modeling complex relationships between biometric parameters.

  A desirable set of statistical properties 2025 of the binary representation 2030/2130 is summarized as follows: each bit in the binary representation has an equal probability of being either zero or one; a different bit in the same binary representation Are independent of each other; binary representations from different users are independent of each other; binary representations for different reads of the same user are statistically dependent on each other.

  The technique embodied in these embodiments of the present invention can be compared with the embodiment of FIG. In the embodiment shown in FIG. 13, feature model 1304 and measurement model 1305 model the base structure of biometric data in a training set, and the biometric data is for a single user and multiple Model how it fluctuates among multiple readings across users. Nothing is done to adapt the encoding and decoding to those models.

  In contrast, the syndrome preprocessing approach as shown in FIG. 20 does not use a feature set obtained directly from biometric data as in FIG. Instead, the feature set of FIGS. 20-21, the binary representation, is designed to be compatible with the syndrome encoding and decoding procedures.

  We specifically design feature sets to be compatible with existing code design, syndrome coding and syndrome decoding procedures. For a particular set of features described herein with a given statistical property, channel codes for binary (binary) symmetric channels that fit the designed feature set can be used. Such channel code structures and their associated syndrome coding and decoding procedures are well-understood and deeply explored topics.

  22A-22C show a set of statistical properties corresponding to a set of binary representation bit strings each having 200 bits.

  FIG. 22A shows a histogram of the average number in the set of binary strings. The ideal distribution is centered around 100, which implies that half of the bits are 1.

  FIG. 22B illustrates a pair-wise entropy of bits in each string. Ideally, the average amount of information is 2 for all pairs if each pair of bits is independent. However, if there is some dependency in the bits, the average information amount will be less than 2. In the worst case, if a particular bit in the process biometric parameter can always be predicted from another bit and the other bits are zero or one with equal probability, the pair average information amount is one.

  FIG. 22C shows intra-user variations 2210 and inter-user variations 2220. Intra-user variation 2210 represents a normalized Hamming distance between bit strings (bit strings) corresponding to multiple samples of the same user. Inter-user variation 2220 represents the normalized Hamming distance between bit strings corresponding to different user samples. Ideally, intra-user and inter-user variations should not overlap and each should be distributed over a narrow range. Moreover, intra-user variation 2210 should be as low (small) as possible, for example, as shown, a distribution of about 0.1 indicates that each bit for the same user has a 10% probability of error. . On the other hand, the distribution for inter-user variation should be centered around 0.5, indicating that bit strings from different users are independent of each other.

  Performing syndrome preprocessing

FIG. 23 shows our syndrome pretreatment method. Syndrome preprocessing applies a set (one or more) of binary logic conditions, i.e., conditions that have a yes / no response with respect to a biometric parameter that yields a binary representation or binary string "00111000101110001 ..." Apply.

  In our method shown in FIG. 24, a set of binary logic conditions 2022 is applied to the biometric parameters. If the output resulting from the application is non-binary 2430, the output is binarized 4202 to provide the necessary binary representation.

  For example, the biometric parameter is the position of the minutiae point relative to the fingerprint. One binary (binary) condition determines whether the number of minutiae in a given two-dimensional (2D) region is greater than a threshold value M.

  Binary logic condition

  Several types of binary logic conditions can be applied to biometric parameters, as shown in FIGS. 25A-25C. The dots in FIGS. 25A-25C represent the coordinates (sample positions) of the fingerprint minutia. (X-position, y-position) coordinates in FIGS. 25A and 25B, or alternatively (x-position, y-position, orientation) coordinates (z) in FIG. 25C.

  In FIG. 25A, each condition is based on a line 2501 drawn through the sample. The binary logic condition is y-mx-n = 0. The line can have a random slope and y-intercept value. In the first embodiment of the present invention, the number of minutia points above the line (that is, located in a region satisfying the condition y−mx−n> 0) and the number of minutia points below the line (that is, the condition y−mx−n < The difference in the number of minutiae points (located in the region satisfying 0) is obtained. This results in a vector of values in the range [−M, M], where M is the maximum number of fingerprint minutiae points. If necessary, the vector can be binarized.

  In FIG. 25B, the condition is a set of rectangles 2502. Each rectangle is generated with an origin representing the upper left corner of the rectangle, along with a width and height. A set of rectangles can be generated with random values of these points or with a predetermined arrangement. In Embodiment 1 of the present invention, the condition is the number of minutia points in a given rectangle.

  In Embodiment 1 of the present invention, the condition is the number of minutiae points in a given rectangle that is greater than a certain threshold, where the threshold is for each rectangle its position and region, And / or may vary based on global statistics of user data samples.

  In another embodiment of the invention, the condition is the difference between the number of minutiae in one rectangle and the number of minutiae in the second rectangle.

  To include additional data about fingerprints, such as maneuver orientation, the rectangular condition can be extended to a cube or cuboid 2503, where the first two dimensions represent the minutia point location, as described above, and The third dimension (z) represents the minutiae orientation. In FIG. 25C, the condition includes a set of rectangular parallelepipeds. Each rectangular parallelepiped is generated at the origin indicating the upper left corner of the rectangular parallelepiped along with the width, height and depth. A set of cuboids can be generated with random values of these points or with a predetermined arrangement. In Embodiment 1 of the present invention, the condition is the number of minutiae points in a given rectangular parallelepiped. In the first embodiment of the present invention, the condition is the number of minutiae points in a given rectangular parallelepiped that is greater than a specific threshold, where the threshold is for each cuboid its position and volume. And / or may vary based on global statistics of user data samples. In yet another embodiment of the present invention, the condition is a difference between the number of minutiae in one rectangular parallelepiped and the number of minutiae in the second rectangular parallelepiped.

  The present invention is not limited to the specific logic conditions described herein. Depending on the biometric properties, various other conditions based on circles, spheres, and polygons can also be used.

  Furthermore, these methods are not limited to minutiae-based feature set transformation and binarization. Its purpose is to apply binary logic conditions to the biometric data to generate a binary representation with statistical information that is compatible with syndrome coding and decoding. For example, the invention can be applied to pattern-based data and frequency domain data, among other types of fingerprint data.

  Generally speaking, overlap between conditions affects the correlation in the resulting binary representation. Conditions can be designed with this effect in mind. For example, a limit could be imposed on the amount of allowable overlap between two rectangles. Syndrome encoding and decoding procedures can also be designed with such correlations in mind. However, an object of the present invention is to minimize the need for such adjustments to commercially available code designs and encoding and decoding procedures.

  Binarization

  FIG. 26 shows several types of binarization. In FIG. 26A, a threshold 2601 is applied to all values of vector 2602 to generate binary vector 2603. This threshold may be the same for all bit positions, or may vary for each bit position.

  In FIG. 26B, a random projection 2604 to an orthonormal basis is first applied to a non-binary vector 2602, where the random projection is the same for all users. The result of this projection is then subjected to a thresholding process to generate a binary vector 2603. Instead of random projection, to improve the separation of samples obtained from real users and fraudsters (fake), such as principal component analysis or linear discriminant analysis Other linear or non-linear transformations can be used.

  In FIG. 26C, the non-binary (non-binary) vector 2602 is first normalized 2605, then a set of random projections (RP) 2604 is applied for each user, followed by Thresholding 2601 is performed. This thresholding may be the same for each projection or may vary within those projections. Then, in order to generate a binary vector 2603, a connection 2607 is performed subsequently.

  Statistical analysis

  Statistical analysis can be performed on the binary representation as part of the design of the syndrome pre-processing to ensure and confirm that the desired target statistical properties are achieved. In this way, statistical analysis is performed on the final result of the syndrome preprocessing, and no feedback is performed on the operation of the syndrome preprocessing.

  Alternatively, during syndrome preprocessing, statistical analysis can also be performed on intermediate binary strings to guide the operation of syndrome preprocessing. In this way, clear feedback of statistical properties is provided during syndrome pre-processing.

  Security considerations for syndrome preprocessing

  The level of security is determined by the number of bits in the binary representation and the correlation between different samples of the same user. For example, if the binary string is 400 bits and the correlation is strong enough that only a 300-bit syndrome is needed to successfully decode the user, the level of security is 100 bits.

  Security comes from the syndrome coding stage. In fact, the syndrome pre-processing results in a binary string having a predetermined statistical correlation. In this case, the security estimate provided by the system is more accurate compared to when syndrome coding and decoding are performed using binary strings that are difficult to model for correlation. Conceivable.

  The invention's effect

  The present invention implements secure user authentication based on biometric parameters. The invention is safe because the syndrome vector is stored in place of the original biometric data or any feature vector. This prevents adversaries who gain access to the database by learning the underlying biometric data.

  By using conventional tools due to the well-known problem of multiple descriptions, the best possible estimate of the original biometric parameter E that an adversary can produce by using only the syndrome vector S It is possible to limit. For example, V.I. K. See Goyal, Multiple description coding: compression methods the network, IEEE Signal Processing Magazine, Volume: 18, pages 74-93, September 2001. In addition, these limits can be established regardless of whether the quality of the estimate is measured by absolute error, square error, weighted error method, or any arbitrary error function. . In contrast, all prior art methods are based on binary values. There, security depends on the Hamming distance.

  In essence, the security of the syndrome vector S is due to the fact that it is a compressed version of the original biometric parameter E. Moreover, this compressed representation corresponds to the “least significant bit” of E. Using tools well known from data compression theory, “If a high compression syndrome code is used, these least significant bits produce at best a poor (insufficient) estimate of the original parameter E. It is possible to prove that it is not possible. For example, Effros, "Distortion-rate bounds for fixed- and variable-rate multi-resolution source codes", IEEE Transactions on Information Theory, volume 45, pages1887-1910, September 1999, and "Steinberg and Merhav," On successive refinement for the Wyner-Ziv problem ", IEEE Transactions on Information Theory, volume 50, pages 1636-1654, August 2004.

  Second, the invention is secure because counterfeiting is at least as difficult as finding a collision in the underlying hash function 340. In particular, the system accepts the syndrome pair (S, H) in the authentication stage 390 only if the decrypted hash H ′ of the biometric E ″ matches the original hash H. For cryptographic hash functions such as MD5 It is generally considered impossible to find an element E ″ that has a hash that differs from E but matches the hash of E. Thus, if syndrome decryption succeeds in decrypting E ″ with the appropriate hash, the system can be confident that E ″ is effectively the same as E, and that all authentication decisions Is performed with the original biometric parameters.

  Third, the present invention compresses the original biometric parameter E when generating the syndrome vector S. Biometric databases for many users may require large amounts of storage, especially when biometric data queries require large amounts of data, such as facial images or audio signals. Thus, reducing the required storage capacity can provide dramatic improvements in both cost and error resiliency. In contrast, most prior art methods for secure storage of biometric data actually increase the size of the stored data due to encryption and error correction overhead, and are therefore insecure (secure). No) Requires more storage capacity than the system.

  Fourth, since the present invention is made by the syndrome code theory, an elaborate code structure and decoding algorithm can be applied. In particular, syndrome coding according to the present invention facilitates the use of soft decoding with the well-known Viterbi algorithm, probability propagation, and turbo decoding for both binary and multi-level coding structures. In contrast, since most prior art methods are based on binary code, Reed-Solomon code, and algebraic decoding, the biometric data is converted to real values, as opposed to binary values. Soft decoding cannot be effectively applied. For example, some methods specifically require calculating an exclusive OR (XOR) of biometric data with random codewords in the registration phase to generate a reference, and also in the authentication phase Require computing the exclusive OR of its references with biometric data in

  Fifth, most prior art related to secure biometrics uses error correction coding, but the present invention uses syndrome coding. Usually, the calculation complexity of error correction coding is super linear in input size. In contrast, by using syndrome codes based on various types of low density parity checks, a syndrome encoder is constructed in which the complexity (quantity) of syndrome encoding is only linear in input size (magnitude). It becomes easy.

  Sixth, US patent application Ser. No. 10 / 928,448 (incorporated herein by reference) entitled “Compressing Signals Using Serial Chain Accumulation Code” by using a syndrome coding framework. It is possible to use a powerful new embedded syndrome code such as the SCA code described by Yedidia et al. These codes encode just enough syndrome bits to allow the syndrome encoder to estimate the inherent variability of the biometric data during registration and allow for successful syndrome decoding. Is acceptable.

  Seventh, the syndrome code as described above can be used to encrypt the data. Moreover, a method is described that allows a design for an optimal syndrome code with a given level of performance and error resiliency.

  Eighth, the syndrome feature vector can be correctly decoded even if the measurement channel is subject to structured noise.

  Ninth, encoding and decoding can be designed to be compatible with desirable statistical properties imposed by binary logic conditions.

  Although the invention has been described by way of examples of preferred embodiments, it is to be understood that various other modifications and changes can be made within the spirit and scope of the invention. Accordingly, it is the object of the appended claims to cover all modifications and variations that fall within the spirit and scope of the present invention.

1 is a block diagram of a security system based on a prior art password. 1 is a block diagram of a prior art biometric based security system. FIG. It is a block diagram of the biometric security system by Embodiment 1 of this invention. 1 is a block diagram of a prior art security system for protecting data. FIG. 1 is a block diagram of a data security system according to an embodiment of the present invention. 1 is a block diagram of a security system according to an embodiment of the present invention. It is a block diagram of a process for constructing a syndrome code according to an embodiment of the present invention. FIG. 4 is a block diagram of a process for generating a histogram according to an embodiment of the invention. FIG. 5 is a block diagram of a process for selecting feature vectors according to an embodiment of the present invention. It is a block diagram for measuring the correlation between coefficients by embodiment of this invention. A block diagram of a biometric encoder for generating syndrome vectors according to embodiments of the present invention upon registration, and a complementary type for the encoder of FIG. 11A used during authentication according to embodiments of the present invention It is a block diagram of a decoder. It is a graph of the probability propagation factor which has a correlation node by embodiment of this invention. FIG. 4 is a block diagram illustrating dependencies between biometric features, complete feature vectors, syndrome feature vectors, and encoded syndrome vectors, according to embodiments of the invention. It is a block diagram of a process for constructing a syndrome code according to an embodiment of the present invention. It is a block diagram of fingerprint minutiae encoding according to an embodiment of the present invention. FIG. 4 is a block diagram of variability in measured biometric data according to an embodiment of the invention. FIG. 4 is a block diagram of variability in measured biometric data according to an embodiment of the invention. FIG. 4 is a block diagram of variability in measured biometric data according to an embodiment of the invention. FIG. 4 is a high level detail block diagram of a probability propagation factor graph according to an embodiment of the present invention. FIG. 4 is a low level detail block diagram of a probability propagation factor graph according to an embodiment of the present invention. It is a graph of the probability propagation factor which removed the excess by embodiment of this invention. FIG. 5 is a block diagram of a process for estimating fingerprint minutia movement and measurement model parameters according to an embodiment of the invention. It is a block diagram which performs the alignment of the minutiae by embodiment of this invention. FIG. 4 is a block diagram of a syndrome encoding process having syndrome preprocessing according to an embodiment of the present invention. FIG. 6 is a block diagram of a syndrome decoding process with syndrome preprocessing according to an embodiment of the present invention. It is a graph of the predetermined statistical property by embodiment of this invention. It is a graph of the predetermined statistical property by embodiment of this invention. It is a graph of the predetermined statistical property by embodiment of this invention. It is a block diagram of the syndrome pre-processing based on the binary logic condition by embodiment of this invention. FIG. 6 is a block diagram of binary logic conditions based on syndrome preprocessing according to another embodiment of the invention. It is a graph of a logic condition as a part of syndrome pre-process by embodiment of this invention. It is a graph of a logic condition as a part of syndrome pre-process by embodiment of this invention. It is a graph of a logic condition as a part of syndrome pre-process by embodiment of this invention. It is a graph of the binarization as a part of syndrome pre-process by embodiment of this invention. It is a graph of the binarization as a part of syndrome pre-process by embodiment of this invention. It is a graph of the binarization as a part of syndrome pre-process by embodiment of this invention.

Claims (21)

A computer-implemented pre-processing method for securely storing biometric parameters in a database, wherein a user's biometric parameters are obtained during a registration phase, comprising:
Applying a set of binary logic conditions to a user's registered biometric parameters to generate a binary display, wherein the binary display is a set of predetermined predetermineds imposed by the set of binary logic conditions; A step having statistical properties;
Encoding the binary representation using a syndrome encoder to generate a registered syndrome vector, wherein the coding is compatible with the binary representation and the set of predetermined statistical properties; ,
Applying a hash function to a registered biometric vector to generate a registered hash;
Storing the registered syndrome vector and the registered hash in a database;
Authenticating a user using said database, and a pre-processing method of biometric parameters before encoding and decoding performed by a computer. The method of claim 1, wherein the authentication step further comprises:
Obtaining a user's authentication biometric parameters;
Applying the set of binary logic conditions to the authentication biometric parameter to generate a binary representation of the authentication biometric parameter, the binary representation being imposed by the set of predetermined statistical properties; Having said set of binary logic conditions
Decoding a binary representation of the biometric parameter using a syndrome decoder to generate an authentication syndrome vector, the encoding comprising the binary representation of the biometric parameter and the set of predetermined statistical properties And steps that are compatible with
Applying a hash function to the authentication biometric vector to generate an authentication hash;
Accessing the database with the authentication syndrome vector and the authentication hash to verify a user.   2. The method of claim 1, wherein the set of statistical properties enforces equal probability that each bit in the binary representation is either zero or one.   The method of claim 1, wherein the set of statistical properties forces different bits in the binary representation to be independent of each other.   The method of claim 1, wherein the set of statistical properties forces binary representations from different users to be independent of each other.   The method of claim 1, wherein the set of statistical properties enforces that binary representations from the same user are statistically dependent on each other.   The method of claim 1, wherein the biometric parameter is a position of a minutiae point relative to a fingerprint.   8. The method of claim 7, wherein the set of binary logic conditions includes a condition for determining whether the number of minutia points in a given two-dimensional region is greater than a threshold value M.   8. The method of claim 7, wherein the set of binary logic conditions includes a condition based on a difference between the number of minutia points above a line and the number of minutia points below the line.   8. The method of claim 7, wherein the set of binary logic conditions is based on a difference between the number of minutia points in the first rectangular portion and the number of minutia points in the second rectangular portion.   The method of claim 1, wherein the biometric parameter is the position and orientation of a minutiae point relative to a fingerprint.   12. The method of claim 11, wherein the set of binary logic conditions includes a condition for determining whether the number of minutia points in a given three-dimensional region is greater than a threshold value M.   The method of claim 1, wherein the predetermined statistical property is compatible with pattern-based data.   2. The method of claim 1, wherein the predetermined statistical property is compatible with frequency domain data.   2. The method of claim 1, wherein the intermediate value is generated by applying a logical binary condition, and the method further comprises binarizing the intermediate value.   16. The method of claim 15, wherein the binarization further comprises thresholding an intermediate value.   17. The method of claim 16, wherein the binarization further comprises applying a transformation to the intermediate value prior to the thresholding.   The method of claim 17, wherein the binarization further comprises normalizing the intermediate value.   The method of claim 17, wherein the transformation is a random projection.   The method of claim 17, wherein the transformation is a principal component analysis.   The method of claim 1, comprising analyzing the binary representation to ensure and confirm that the set of statistical properties is imposed.

Images