+

WO2014118257A1 - Procede de chiffrement homomorphe pour le ou exclusif et calcul securise d'une distance de hamming - Google Patents

Procede de chiffrement homomorphe pour le ou exclusif et calcul securise d'une distance de hamming Download PDF

Info

Publication number
WO2014118257A1
WO2014118257A1 PCT/EP2014/051759 EP2014051759W WO2014118257A1 WO 2014118257 A1 WO2014118257 A1 WO 2014118257A1 EP 2014051759 W EP2014051759 W EP 2014051759W WO 2014118257 A1 WO2014118257 A1 WO 2014118257A1
Authority
WO
WIPO (PCT)
Prior art keywords
data
indexed
elements
individual
binary
Prior art date
Application number
PCT/EP2014/051759
Other languages
English (en)
Inventor
Alain PATEY
Hervé Chabanne
Gérard Cohen
Original Assignee
Morpho
Institut Mines Telecom
Priority date (The priority date is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the date listed.)
Filing date
Publication date
Application filed by Morpho, Institut Mines Telecom filed Critical Morpho
Priority to EP14701769.3A priority Critical patent/EP2951944A1/fr
Priority to US14/764,955 priority patent/US20150365229A1/en
Publication of WO2014118257A1 publication Critical patent/WO2014118257A1/fr

Links

Classifications

    • H—ELECTRICITY
    • H04—ELECTRIC COMMUNICATION TECHNIQUE
    • H04L—TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION
    • H04L9/00—Cryptographic mechanisms or cryptographic arrangements for secret or secure communications; Network security protocols
    • H04L9/008—Cryptographic mechanisms or cryptographic arrangements for secret or secure communications; Network security protocols involving homomorphic encryption
    • H—ELECTRICITY
    • H04—ELECTRIC COMMUNICATION TECHNIQUE
    • H04L—TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION
    • H04L9/00—Cryptographic mechanisms or cryptographic arrangements for secret or secure communications; Network security protocols
    • H04L9/08—Key distribution or management, e.g. generation, sharing or updating, of cryptographic keys or passwords
    • H04L9/0861—Generation of secret information including derivation or calculation of cryptographic keys or passwords
    • H04L9/0869—Generation of secret information including derivation or calculation of cryptographic keys or passwords involving random numbers or seeds
    • H—ELECTRICITY
    • H04—ELECTRIC COMMUNICATION TECHNIQUE
    • H04L—TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION
    • H04L9/00—Cryptographic mechanisms or cryptographic arrangements for secret or secure communications; Network security protocols
    • H04L9/30—Public key, i.e. encryption algorithm being computationally infeasible to invert or user's encryption keys not requiring secrecy
    • H04L9/304—Public key, i.e. encryption algorithm being computationally infeasible to invert or user's encryption keys not requiring secrecy based on error correction codes, e.g. McEliece
    • H—ELECTRICITY
    • H04—ELECTRIC COMMUNICATION TECHNIQUE
    • H04L—TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION
    • H04L9/00—Cryptographic mechanisms or cryptographic arrangements for secret or secure communications; Network security protocols
    • H04L9/32—Cryptographic mechanisms or cryptographic arrangements for secret or secure communications; Network security protocols including means for verifying the identity or authority of a user of the system or for message authentication, e.g. authorization, entity authentication, data integrity or data verification, non-repudiation, key authentication or verification of credentials
    • H04L9/3226—Cryptographic mechanisms or cryptographic arrangements for secret or secure communications; Network security protocols including means for verifying the identity or authority of a user of the system or for message authentication, e.g. authorization, entity authentication, data integrity or data verification, non-repudiation, key authentication or verification of credentials using a predetermined code, e.g. password, passphrase or PIN
    • H04L9/3231—Biological data, e.g. fingerprint, voice or retina

Definitions

  • the invention generally relates to methods for encrypting binary data, and their application for the secure calculation of Hamming distances between two data.
  • the invention finds applications in particular in the field of identification or biometric authentication. STATE OF THE ART
  • the data of the individual or of the object, acquired by the control server is compared with the set of data of the database in order to identify whether at least one datum of the database corresponds to the datum acquired, and thus identify the individual or object as an individual or an object listed in the database.
  • the database includes private information to which the control server must not be able to access, and vice versa the management server must not obtain information on the individual, and in particular must not have access to the biometric data. which is exploited.
  • the object of the invention is to overcome the shortcomings of the prior art, by proposing a method of data encryption and secure calculation of Hamming distance on integer data, and no longer bit by bit.
  • Another object of the invention is to propose a method of identification or secure authentication of an individual.
  • the subject of the invention is a method for encrypting a binary data item, characterized in that it comprises the steps of:
  • the public key being a hollow matrix comprising m rows and n columns, m being greater than the number I of bits of the binary data item, I being an integer strictly greater than 1, and the private key being a set of I indexed sets of integers between 1 and m such that for each set, the sum of the elements of the rows of the hollow matrix indexed by the elements of a set is zero, and
  • e is a random binary noise vector
  • y is a linear encoding of the data c.
  • the encryption method according to the invention may further comprise at least one of the following characteristics: the elements of the random noise vector e are Bernoulli variables. the encoding y of the data c is configured so that a partial knowledge of the coded data y is not decodable.
  • the generation of the public key and the private key includes:
  • the generation of the public key and the private key includes:
  • each set includes q elements
  • the invention also proposes a method for decrypting an encrypted data obtained by applying to a binary data item the encryption method described above, the decryption method comprising:
  • An application proposed by the invention is a method of secure calculation of the operation "or exclusive" between two binary data encrypted by the implementation of the encryption method described above, comprising the steps of determining, from the encrypted data, a sequence of bits corresponding to the encryption, by said encryption method, of the result of the "exclusive" operation between the two binary data, and deciphering the bit sequence obtained by the implementation the decryption method.
  • Another application proposed by the invention is a method of secure calculation of a Hamming distance between two binary data encrypted by the implementation of the encryption method described above, the method comprising the steps of:
  • step b deciphering the bit sequence obtained in step b), and determining the Hamming weight of the data obtained.
  • the method of secure calculation of a Hamming distance proposed by the invention may further comprise at least one of the following characteristics:
  • the method is implemented jointly by two processing units each holding one of the two binary data and a public key, a processing unit also holding the associated secret key, and in which:
  • each processing unit encrypts the data it holds from the public key, the unit holding the secret key transmitting its encrypted data to the second unit,
  • the second unit implements steps a) and b) and transfers the result to the first unit
  • the method is implemented jointly by a server unit holding the two encrypted data and the public key, and a client unit holding the public key and the associated private key, and wherein: o ⁇ server-unit implements steps a) and b) and transfers the result to the client unit, and
  • the invention also proposes a method for authenticating or identifying an individual, comprising comparing a binary data item acquired on the individual with one or more reference binary data acquired on listed individuals, each comparison comprising the calculating the Hamming distance between the data of the individual and a datum of the database, said calculation being carried out by implementing the method of secure calculation of a Hamming distance described above.
  • the data of the individual and the data or data of the database are biometric data obtained by encoding the same biometric trait on the individual and the individual (s) listed.
  • the invention finally proposes a system for identifying or authenticating an individual, comprising at least one control server of an individual to identify or authenticate, and at least one management server of a reference database. of listed individuals, the control server being adapted to carry out the acquisition of a biometric binary data of an individual, the control server and the management server being adapted to:
  • FIG. 1 represents the main steps implemented for encryption and decryption of data
  • FIG. 2 represents the main steps implemented for the secure calculation of a Hamming distance
  • Figures 3a and 3b show two alternative embodiments of the calculation of a Hamming distance between two data.
  • the operations are carried out on binary data, that is to say that the calculations must be made in base 2 count.
  • the nullity of a value corresponds to the nullity in base 2 of said value, i.e. the value must be congruent to 0 modulo 2.
  • a matrix d-hollow where d is an integer, is a matrix comprising, on each line, non-zero elements, the rest of the matrix comprising only 0.
  • the encryption method is an asymmetric encryption method, based on the use of a public key p k accessible to all and allowing the encryption of data, and a secret key s k accessible only to the recipient of the data, and necessary to achieve the decryption of the data.
  • the method therefore comprises a first step 100 of generating a public key p k and a secret key s k .
  • the public key p k is a hollow matrix M e ⁇ 0, l) mxn , that is to say that the matrix comprises m rows and n columns, m and n being integers, and that it comprises on each line of elements equal to 1, the remainder of the matrix including only 0. d is therefore less than n.
  • the generation of the public key and the secret key can be implemented in different ways, of which two preferential modes of implementation are described below.
  • this step 100 comprises the generation of indexed matrices H j chosen uniformly among the matrices comprising q rows and n columns, and where each row of the matrix contains exactly three 1s and each column contains zero or two 1.
  • a matrix M 3-hollow is generated comprising m rows and n columns, m being greater than q, the lines of M being chosen according to a uniform distribution law.
  • k 0 for ⁇ k.
  • the public key p k is M
  • the private key sk is the set of S j
  • each column of H j comprises only 0 or 2 elements equal to 1. The summation of these lines is therefore zero (that is to say congruent to 0 modulo 2).
  • the step 100 of generating the public key p k and the private key s k comprises the generation, during a step 1 10 ', of I matrices d- indexed hollow H j , j between 1 and I, d being an even integer greater than 3, and the elements of said matrices being chosen according to a uniform distribution law, each comprising q lines and q / 3 columns, where q is strictly lower to m.
  • a d-hollow matrix M is generated comprising m rows and n columns.
  • I randomly generates I second sets T j , j between 1 and I, integers between 1 and n, such that each set T j comprises q / 3 elements.
  • a line j of M indexed by an element of U j which is the sum of the lines of M indexed by the elements of a subset W j of U j , and we switches that line with the j th line of M.
  • this line is in view of the properties of matrices and sets generated in previous steps.
  • the public key p k obtained is the matrix M and the private key s k is
  • the encryption method includes the encoding 200 of the binary data c to obtain an encoded data y.
  • the encoding is performed by means of a linear coding which advantageously makes it possible to solve the so-called "wire-tap channel” problem, which is described in the article Wyner, AD: The wire-tap channel, The Bell System Technical Journal 54 (8), 1355-1387.
  • the problem presented in this article is to propose a linear coding that allows to encode a data item A, to obtain an encoded data item B such that, if B reaches a recipient via a non-noisy listening line, that is that is to say that B reaches its destination without having undergone modifications, the recipient can decode it to obtain the data A.
  • This type of coding makes it possible to ensure that even a partial knowledge of the encoded data B does not make it possible to obtain the decoded data A.
  • the encoding step 200 of the binary data item c is advantageously performed by means of a linear coding of the type by lateral classes.
  • This type of encoding uses a linear code C of parameters [n, k, d] with a control matrix H of dimensions (nk) * k.
  • y is a vector of ⁇ 0,1) 'randomly selected from among the set of vectors satisfying H.
  • y c, where c is the binary data item to be encrypted, and H is a dimension control matrix r * 1 of the linear code on which the lateral class coding is based.
  • the elements of the noise vector e are Bernoulli variables, that is to say that they follow a Bernoulli law of parameter ⁇ : the elements of e thus have the value 1 with a probability ⁇ .
  • ⁇ is a very small value of the order of n ⁇ 0-2 .
  • the role of this noise vector is to make it difficult to find it from b.
  • the encryption method implemented has a high level of security, notably thanks to the encoding of the data c by a coding checking the properties of the "wire-tap channel".
  • this coding allows a third party who would obtain a partial knowledge of the encoded data y would not be able to decode it.
  • the encrypted data b obtained thus comprises m bits.
  • the sum of the bits of b indexed by the elements of S j for each j between 1 and I is calculated, which corresponds to a bit y j of the encoded data y.
  • the summation of the elements of Mx indexed by the elements of S j is zero, because of the choice of S j .
  • the summation of the elements of b indexed by S j will thus give j , added to a negligible error term. Consequently, the bits obtained by the summation of the elements of b, indexed by the sets S j , are the bits of y, with the noise near.
  • the proposed encryption method has the advantage of being homomorphic for operation "XOR” (exclusive OR) symbolized by the operator®, that is to say that for two messages Ci and c 2 of I bits to to encrypt, one can obtain the c c c 2 cipher from bi and b 2 , the data obtained respectively by the cipher of Ci and c 2 .
  • the exclusive-or bi and b 2 is a possible encrypted c t (c 2 by the encryption process 1000, that is to say that the implementation of the XOR operation between bi and b 2 corresponds to the encryption of c 1 ®c 2 by the same encryption method 1000 with the same parameters.
  • This property is derived from the linear character of the code by lateral classes used.
  • the encryption and decryption method described above makes it possible to implement a secure calculation 3000 of Hamming distances between two binary data Ci and c 2 , this calculation being implemented jointly by two processing units Ui and U 2 .
  • the method then comprises the permutation 3200 of the first I bits of the result obtained in the preceding step, by the implementation of a permutation ⁇ chosen randomly.
  • the result obtained corresponds to the encryption of the permutation of the result of the operation "exclusive OR" between the two data c, not encrypted, that is to say £ , (a (c 1 ⁇ c 2 )). But the permutation does not modify the Hamming weight of a sequence of bits.
  • the message a (c 1 ⁇ c 2 ) has the same Hamming weight as c 1 (c 2 , this Hamming weight corresponding to the Hamming distance between Ci and c 2 .
  • processing units Ui and U 2 are possible.
  • each processing unit Ui and U 2 respectively have a binary data Ci, c 2 and a public key p k of the type used in the method described above. before.
  • the corresponding secret key s k is held by only one of the two units, for example Ui.
  • each processing unit encrypts the data it holds by implementing the encryption method 1000 described above.
  • the unit Ui holding the secret key then transfers its encrypted data E (ci) to the other unit U 2 in a step 3020.
  • the unit U 2 implements the exclusive OR operation 3100 between the two encrypted data, chooses and performs the permutation ⁇ 3200 of the first I bits of the result obtained to obtain '(a (c 1 c c 2 )) .
  • the unit U 2 transfers this result to the unit Ui during a step 3210 and the unit Ui decrypts the result, by implementing the decryption method 2000, thanks to the secret key s k it holds, to obtain oc 1 @c 2 ) and counts its Hamming weight, to obtain the Hamming distance between Ci and c 2 .
  • the result of the Hamming distance between the data can be communicated by the unit Ui to the unit U 2 .
  • the processing unit Ui initially has the two already encrypted data E (ci) and E (c 2 ) and the public key p k .
  • the processing unit U 2 has the public key p k and the private key s k .
  • the unit Ui that performs the exclusive OR operation 3100 between the two encrypted data, which chooses and applies 3200 the permutation ⁇ of the first I bits of the result obtained. Then, during a step 3210, the unit Ui transfers E (a (c 1 @c 2 j) obtained in step 3200 to the unit U 2 .
  • the unit U 2 decrypts, by application of the method 2000, thanks to the secret key that it holds, the data received from the unit U 2 to obtain the data item a (c 1 ⁇ c 2 ), counts its Hamming weight and thus obtains the Hamming distance between Ci and c 2 .
  • the unit U 2 can also transfer the Hamming distance between the data q to the unit Ui.
  • This method 3000 for calculating a Hamming distance is advantageously applied to the identification (comparison of an individual to a plurality of candidate individuals to detect a correspondence between the individual and one of the candidates) or the authentication (comparison an individual with a candidate individual to detect a biometric match of an individual.
  • a biometric datum of an individual is then compared to one (in the case of authentication) or several (in the case of identification) data of individuals listed, each comparison being made by calculating the Hamming distance between the data.
  • Biometric data are digital encodings of biometric traits of individuals. They must correspond to the same biometric feature in order to be comparable: this feature may be one or two irises, one or more fingerprints, the shape of the face, the shape of the venous network, the DNA, the palm prints, etc.
  • a biometric identification or authentication system 1 of an individual adapted for the implementation of the method 3000 advantageously comprises a control server SC of an individual to be identified and a management server SG of a biometric database , said base comprising at least one reference biometric datum c, acquired on a listed individual.
  • the control server SC advantageously comprises means for acquiring a biometric data item b on an individual to identify or authenticate. This may be for example a fingerprint reader or a biometric identity document, or a camera.
  • the SC control and management servers SG are advantageously configured to implement one or other of the implementation variants of the method 3000 described above.
  • the processing unit U1 advantageously corresponds to the control server SC which acquires data b on an individual to identify and compares said data with one or more data c held by the management server. to obtain, for each Q, the Hamming distance between the data b and the data c ,.
  • a Hamming distance between b and one of the data c is less than a predetermined threshold, a correspondence is detected between the individual on whom the data b was acquired and the reference individual on whom the data was acquired.
  • the processing unit U 2 advantageously corresponds to the control server SC.
  • the reference data stored in the database is already encrypted, so that the management server SG can access only the encrypted data, and the control server encrypts the data b acquired on the individual before the transmit to the management server.
  • the control server obtains the Hamming distance between the data item b and one or more data Q of the database, and can similarly detect a correspondence between the individual and one or more listed individuals.
  • an encryption method has been presented that makes it possible to calculate a Hamming distance over integer data in a secure manner, and no longer bit by bit, this calculation can also be applied to the identification or the biometric authentication.

Landscapes

  • Engineering & Computer Science (AREA)
  • Computer Security & Cryptography (AREA)
  • Computer Networks & Wireless Communication (AREA)
  • Signal Processing (AREA)
  • Computing Systems (AREA)
  • Theoretical Computer Science (AREA)
  • Storage Device Security (AREA)

Abstract

L'invention concerne un procédé de chiffrement d'une donnée binaire caractérisé en ce qu'il comprend les étapes consistant à : - générer une clé publique et une clé privée, la clé publique étant une matrice creuse comprenant m lignes et n colonnes, m étant supérieur au nombre I de bits de la donnée binaire, I étant un entier strictement supérieur à 1, et la clé privée étant un ensemble de I ensembles indexés d'entiers compris entre 1 et m tels que pour chaque ensemble, la somme des éléments des lignes de la matrice creuse indexées par les éléments d'un ensemble est nulle, et - générer une séquence binaire b comprenant m bits, telle que b=Mx+e+y où o x est un vecteur binaire aléatoire, o e est un vecteur de bruit binaire aléatoire, et o y est un encodage linéaire de la donnée c. L'invention concerne également un procédé de calcul d'une distance de Hamming sur des données chiffrées par le procédé de chiffrement.

Description

PROCEDE DE CHIFFREMENT HOMOMORPHE POUR LE OU EXCLUSIF ET CALCUL SECURISE D'UNE DISTANCE DE HAMMING
DOMAINE DE L'INVENTION
L'invention concerne de manière générale des procédés de chiffrement de données binaires, et leur application pour le calcul sécurisé de distances de Hamming entre deux données.
L'invention trouve des applications notamment dans le domaine de l'identification ou de l'authentification biométrique. ETAT DE LA TECHNIQUE
De nombreuses techniques d'identification ou d'authentification biométrique sont déjà connues. Généralement, elles sont mises en œuvre conjointement par un serveur de contrôle d'un individu ou d'un objet, qui peut procéder à l'acquisition d'une donnée biométrique sur un individu ou d'un objet, et par un serveur de gestion d'une base comprenant N données biométriques de même nature.
La donnée de l'individu ou de l'objet, acquise par le serveur de contrôle, est comparée à l'ensemble des données de la base afin d'identifier si au moins une donnée de la base correspond à la donnée acquise, et ainsi identifier l'individu ou l'objet comme un individu ou un objet répertorié dans la base.
Pour ce faire, il est courant de calculer la distance de Hamming entre la donnée de l'individu et une ou plusieurs données de la base, c'est-à-dire le nombre de bits différents d'une donnée à l'autre. Ce nombre peut classiquement être calculé en réalisant l'opération « OU exclusif » (connu en anglais sous l'acronyme XOR pour « exclusive OR ») entre les deux données, puis en comptant le poids de Hamming, c'est-à-dire le nombre de bits à 1 du résultat obtenu.
Une problématique majeure dans ce contexte est d'assurer la confidentialité des données utilisées. En effet, la base de données comporte des informations privées auxquelles le serveur de contrôle ne doit pas pouvoir accéder, et inversement le serveur de gestion ne doit pas obtenir d'informations sur l'individu, et notamment ne doit pas avoir accès la donnée biométrique qui est exploitée.
Pour répondre à cette problématique, des techniques de calcul sécurisé ont été développées, qui permettent à des serveurs de réaliser des calculs sur des données chiffrées, de manière à obtenir le résultat des calculs sans déchiffrer les données ou y avoir accès.
Notamment, une technique de chiffrement de données et de calcul sécurisé sur les données chiffrées par cette technique a été développée pour réaliser l'opération « OU exclusif » entre deux données.
Cette technique est décrite dans la publication de S. Goldwasser et S. Micali, Probabilistic encryption and how to play mental poker keeping secret ail partial information, in H.R. Lewis, B.B Simons, W.A. Burkhard, L.H. Landweber (eds.) STOC, pp. 365-377. ACM (1982).
L'inconvénient principal de cette méthode est qu'elle ne permet que de chiffrer les données bit à bit, ce qui allonge considérablement le temps de calcul nécessaire à sa mise en œuvre.
Il existe donc un besoin pour le développement d'une méthode de chiffrement de données permettant le calcul sécurisé d'une distance de Hamming plus rapide.
PRESENTATION DE L'INVENTION
L'invention a pour but de pallier les insuffisances de l'art antérieur, en proposant un procédé de chiffrement de données et de calcul sécurisé de distance de Hamming sur des données entières, et non plus bit à bit.
Un autre but de l'invention est de proposer un procédé d'identification ou d'authentification sécurisé d'un individu. A cet égard, l'invention a pour objet un procédé de chiffrement d'une donnée binaire caractérisé en ce qu'il comprend les étapes consistant à :
générer une clé publique et une clé privée, la clé publique étant une matrice creuse comprenant m lignes et n colonnes, m étant supérieur au nombre I de bits de la donnée binaire, I étant un entier strictement supérieur à 1 , et la clé privée étant un ensemble de I ensembles indexés d'entiers compris entre 1 et m tels que pour chaque ensemble, la somme des éléments des lignes de la matrice creuse indexées par les éléments d'un ensemble est nulle, et
générer une séquence binaire b comprenant m bits, telle que b=Mx+e+y où x est un vecteur binaire aléatoire,
e est un vecteur de bruit binaire aléatoire, et
y est un encodage linéaire de la donnée c.
Avantageusement, mais facultativement, le procédé de chiffrement selon l'invention peut en outre comprendre au moins l'une des caractéristiques suivantes : les éléments du vecteur e de bruit aléatoire sont des variables de Bernoulli. l'encodage y de la donnée c est configuré pour qu'une connaissance partielle de la donnée codée y ne soit pas décodable.
l'encodage y de la donnée c est un encodage linéaire par classes latérales, c'est-à-dire que y est un élément sélectionné au hasard parmi les éléments vérifiant la relation H'y=c, où H est une matrice de contrôle d'un code linéaire.
la génération de la clé publique et de la clé privée comprend :
o la génération de I matrices indexées de q lignes et n colonnes, où q est strictement inférieur à m, les lignes de chaque matrice comprenant chacune trois 1 et les colonnes de chaque matrice comprenant chacune zéro ou deux 1 ,
o la génération d'une matrice creuse M comprenant m lignes et n colonnes,
o la génération aléatoire de I ensembles indexés d'entiers compris entre 1 et m tels que chaque ensemble comprend q éléments dont son index et tels que deux ensembles distincts ne comprennent aucun élément commun, et
o pour chaque ensemble indexé, le remplacement des lignes de la matrice creuse M indexées par les éléments de l'ensemble, par les lignes de la matrice indexée correspondante,
la génération de la clé publique et de la clé privée comprend :
o la génération de I matrices d-creuses indexées Hj, où d est un entier pair supérieur à 3, comprenant chacune q lignes et q/3 colonnes, où q est strictement inférieur à m, chaque ligne d'une matrice comprenant d 1 ,
o la génération d'une matrice d-creuse M comprenant m lignes et n colonnes, o la génération aléatoire de I premiers ensembles indexés Uj, j compris entre 1 et I, d'entiers compris entre 1+1 et m tels que :
■ chaque ensemble comprend q éléments, et
■ deux ensembles distincts ne comprennent aucun élément commun,
o la génération aléatoire de I seconds ensembles Tj, j compris entre 1 et I, d'entiers compris entre 1 et n, tels que chaque ensemble Tj comprend q/3 éléments,
o pour tout j compris entre 1 et I,
■ le remplacement des éléments de M tel que :
" MUkit = Hj k q pour tout uk e Uj, tq e 7}, et
Figure imgf000006_0001
■ la permutation de la jeme ligne de M avec une ligne de M indexée par un élément de Uj qui est la somme des lignes de M indexées par les éléments d'un sous-ensemble Wj de Uj, o la clé publique obtenue étant la matrice creuse M et la clé privée étant l'ensemble, pour j compris entre 1 et I, des unions des ensembles Wj avec le singleton j. L'invention propose également un procédé de déchiffrement d'une donnée chiffrée obtenue par l'application à une donnée binaire du procédé de chiffrement décrit précédemment, le procédé de déchiffrement comprenant :
pour chaque ensemble d'entiers indexés Sj, la sommation binaire des bits de la donnée chiffrée indexés par les éléments de Sj, chaque bit obtenu correspondant au bit indexé par j de la donnée binaire encodée, et l'ensemble des bits indexés obtenus formant la donnée binaire encodée, et le décodage de la donnée obtenue, la donnée décodée formant la donnée binaire déchiffrée.
Une application proposée par l'invention est un procédé de calcul sécurisé de l'opération « ou exclusif » entre deux données binaires chiffrées par la mise en œuvre du procédé de chiffrement décrit ci-avant, comprenant les étapes consistant déterminer, à partir des données chiffrées, une séquence de bits correspondant au chiffrement, par ledit procédé de chiffrement, du résultat de l'opération « ou exclusif » entre les deux données binaires, et déchiffrer la séquence de bits obtenue par la mise en œuvre du procédé de déchiffrement.
Une autre application proposée par l'invention est un procédé de calcul sécurisé d'une distance de Hamming entre deux données binaires chiffrées par la mise en œuvre du procédé de chiffrement décrit ci-avant, le procédé comprenant les étapes consistant à :
a) déterminer, à partir des données chiffrées, le résultat correspondant au chiffrement par le procédé de chiffrement, du résultat de l'opération « ou exclusif » entre les deux données non chiffrées,
b) appliquer une permutation σ aux I premiers bits du résultat obtenu à l'étape a), et
c) déchiffrer la séquence de bits obtenue à l'étape b), et déterminer le poids de Hamming de la donnée obtenue.
Avantageusement, mais facultativement, le procédé de calcul sécurisé d'une distance de Hamming proposé par l'invention peut en outre comprendre au moins l'une des caractéristiques suivantes :
- le procédé est mis en œuvre conjointement par deux unités de traitement détenant chacune une des deux données binaires et une clé publique, une unité de traitement détenant en outre la clé secrète associée, et dans lequel :
o chaque unité de traitement chiffre la donnée qu'elle détient à partir de la clé publique, l'unité détenant la clé secrète transmettant sa donnée chiffrée à la seconde unité,
o la seconde unité met en œuvre les étapes a) et b) et transfère le résultat à la première unité, et
o la première unité met en œuvre l'étape c).
le procédé est mis en œuvre conjointement par une unité-serveur détenant les deux données chiffrées et la clé publique, et une unité-client détenant la clé publique et la clé privée associée, et dans lequel : o Γ unité-serveur met en œuvre les étapes a) et b) et transfère le résultat à l'unité client, et
o l'unité-client met en œuvre l'étape c). L'invention propose encore un procédé d'authentification ou d'identification d'un individu, comprenant la comparaison d'une donnée binaire acquise sur l'individu à une ou plusieurs données binaire de référence acquises sur des individus répertoriés, chaque comparaison comprenant le calcul de la distance de Hamming entre la donnée de l'individu et une donnée de la base, ledit calcul étant réalisé par la mise en œuvre du procédé de calcul sécurisé d'une distance de Hamming décrit ci-avant..
Avantageusement, mais facultativement, dans le procédé d'authentification ou d'identification d'un individu, la donnée de l'individu et la ou les données de la base sont des données biométriques obtenues par encodage d'un même trait biométrique sur l'individu et le ou les individus répertoriés.
L'invention propose enfin un système d'identification ou d'authentification d'un individu, comportant au moins un serveur de contrôle d'un individu à identifier ou authentifier, et au moins un serveur de gestion d'une base de données de référence d'individus répertoriés, le serveur de contrôle étant adapté pour procéder à l'acquisition d'une donnée binaire biométrique d'un individu, le serveur de contrôle et le serveur de gestion étant adaptés pour :
calculer au moins une distance de Hamming entre la donnée de l'individu et au moins une donnée de la base, par la mise en œuvre du procédé de calcul sécurisé de distance de Hamming décrit ci-avant, et
déterminer, à partir de la ou des distances de Hamming calculées, une ou plusieurs données de la base présentant des similarités avec la donnée de l'individu excédant un seuil prédéterminé.
DESCRIPTION DES FIGURES
D'autres caractéristiques, buts et avantages de la présente invention apparaîtront à la lecture de la description détaillée qui va suivre, au regard des figures annexées, données à titre d'exemples non limitatifs et sur lesquelles : La figure 1 représente les principales étapes mises en œuvre pour le chiffrement et le déchiffrement de données,
La figure 2 représente les principales étapes mises en œuvre pour le calcul sécurisé d'une distance de Hamming,
Les figures 3a et 3b représentent deux variantes de réalisation du calcul d'une distance de Hamming entre deux données.
DESCRIPTION DETAILLEE D'AU MOINS UN MODE DE MISE EN ŒUVRE DE L'INVENTION
Contexte et formalisme
Dans toute la suite, les opérations sont réalisées sur des données binaires, c'est-à-dire que les calculs doivent être réalisés en numération en base 2. Ainsi notamment, la nullité d'une valeur correspond à la nullité en base 2 de ladite valeur, c'est-à-dire que la valeur doit être congrue à 0 modulo 2.
On note également pour la suite la définition suivante : une matrice d-creuse, où d est un entier, est une matrice comprenant, sur chaque ligne, d éléments non- nuls, le reste de la matrice ne comprenant que des 0.
De plus, on introduit la fonction de chiffrement homomorphe pour une opération ° si, avec deux données chiffrées Ci et c2 obtenues par ledit chiffrement respectivement de données m-i et m2, il est possible de déterminer le chiffré c3 d'une donnée m3=m1 °m2 en connaissant uniquement la clé publique (et pas la clé secrète) du chiffrement employé.
Procédé de chiffrement et de déchiffrement de données
En référence à la figure 1 , on a représenté les principales étapes d'un procédé de chiffrement 1000 et de déchiffrement 2000 de données binaires comprenant chacune I bits, I étant strictement supérieur à 1.
Le procédé de chiffrement est un procédé de chiffrement asymétrique, reposant sur l'utilisation d'une clé publique pk accessible à tous et permettant le chiffrement de données, et d'une clé secrète sk accessible seulement au destinataire des données, et nécessaire pour réaliser le déchiffrement des données.
Le procédé comporte donc une première étape 100 de génération d'une clé publique pk et d'une clé secrète sk. La clé publique pk est une matrice d-creuse M e {0,l)mxn, c'est-à-dire que la matrice comprend m lignes et n colonnes, m et n étant des entiers, et qu'elle comprend sur chaque ligne d éléments égaux à 1 , le reste de la matrice ne comprenant que des 0. d est donc inférieur à n.
La clé secrète sk est un ensemble de I ensembles indexés (Sj)j= 1 . c, tels que pour tout j compris entre 1 et \, j e Sj et∑i£S] Mi = 0, où M, est la ième ligne de M.
La génération de la clé publique et de la clé secrète peut être mise en œuvre de différentes manières, dont deux modes de mise en œuvre préférentiels sont décrits ci-après.
Selon un premier mode de mise en œuvre, cette étape 100 comprend la génération 1 10 de I matrices indexées Hj choisies uniformément parmi les matrices comprenant q lignes et n colonnes, et où chaque ligne de la matrice contient exactement trois 1 et chaque colonne contient zéro ou deux 1 .
Au cours d'une étape 120, on génère une matrice M 3-creuse comprenant m lignes et n colonnes, m étant supérieur à q, les lignes de M étant choisies suivant une loi de distribution uniforme.
Au cours d'une étape 130, on génère de façon aléatoire I ensembles indexés Sj, j compris entre 1 et I, comprenant chacun q éléments entiers compris entre 1 et m, et tels que pour tout j, e Sj et Sj n Sk = 0 pour ≠ k.
Puis, au cours d'une étape 140, on remplace, pour tout j compris entre 1 et I, les lignes de M indexées par les éléments de Sj par les lignes de Hj.
La clé publique pk est donc M, et la clé privée sk est l'ensemble des Sj
¾eii,.,0-
On obtient bien par ce procédé les caractéristiques de la clé publique et de la clé secrète décrites ci-avant, et notamment le fait que chaque somme des lignes de la matrice M indexées par les éléments d'un Sj est nulle.
En effet, pour chaque j, on remplace q lignes de M par les q lignes de la matrice Hj correspondante. Or, chaque colonne de Hj ne comprend que 0 ou 2 éléments égaux à 1 . La sommation de ces lignes est donc nulle (c'est-à-dire congrue à 0 modulo 2).
Alternativement, l'étape 100 de génération de la clé publique pk et de la clé privée sk comprend la génération, au cours d'une étape 1 10', de I matrices d- creuses indexées Hj, j compris entre 1 et I, d étant un entier pair supérieur à 3, et les éléments desdites matrices étant choisis selon une loi de distribution uniforme, comprenant chacune q lignes et q/3 colonnes, où q est strictement inférieur à m.
Au cours d'une étape 120', on génère une matrice d-creuse M comprenant m lignes et n colonnes.
Au cours d'une étape 130', on génère de façon aléatoire I premiers ensembles indexés Uj c {Z + 1, ... , m), j compris entre 1 et I, comprenant chacun q éléments, et tels que deux ensembles distincts Uj et Uk ne comprennent aucun élément commun : Uj
Figure imgf000011_0001
Uk = 0.
Au cours d'une étape 140', on génère de façon aléatoire I seconds ensembles Tj, j compris entre 1 et I, d'entiers compris entre 1 et n, tels que chaque ensemble Tj comprend q/3 éléments.
Puis, au cours d'une étape 150', on remplace des éléments de M par des éléments de chaque matrice Hj, j compris entre 1 et I, de la façon suivante : MUk q = Hjk q pour tout uk e Uj, tq e Tj, et MUk q = 0 si tq ί Tj .
Au cours d'une étape 160', on identifie une ligne j, de M indexée par un élément de Uj qui est la somme des lignes de M indexées par les éléments d'un sous-ensemble Wj de Uj, et on permute cette ligne avec la jeme ligne de M. Cette ligne existe compte-tenu des propriétés des matrices et des ensembles générés au cours des étapes précédentes.
La clé publique pk obtenue est la matrice M et la clé privée sk est
Figure imgf000011_0002
Le fait que la somme des lignes de M indexées par les éléments des Sj soit nulle provient du fait que la jeme ligne de M est égale à la somme des lignes de Wj et que les additions sont réalisées en binaire.
Suite à l'étape 100 de génération de la clé publique et de la clé privée, le procédé de chiffrement comprend l'encodage 200 de la donnée binaire c pour obtenir une donnée encodée y.
L'encodage est réalisé au moyen d'un codage linéaire permettant avantageusement de résoudre le problème dit du « wire-tap channel » (pouvant être traduit par « canal à jarretière »), exposé, présenté dans l'article Wyner, A.D. : The wire-tap channel, The Bell System Technical Journal 54(8), 1355-1387. Le problème exposé dans cet article est de proposer un codage linéaire qui permette d'encoder une donnée A, pour obtenir une donnée encodée B telle que, si B parvient à un destinataire via une ligne d'écoute non-bruitée, c'est-à-dire que B parvient à son destinataire sans avoir subi de modifications, le destinataire peut la décoder pour obtenir la donnée A.
En revanche, si B parvient à son destinataire via une ligne d'écoute bruitée, c'est-à-dire que le tiers ne dispose que d'une donnée B partielle, ce qui est typiquement le cas d'une attaque par un tiers, il est impossible de la décoder pour obtenir la donnée A.
Ce type de codage permet d'assurer que même une connaissance partielle de la donnée encodée B ne permet pas d'obtenir la donnée décodée A.
Un codage vérifiant ces propriétés est par exemple le codage du type dit « par classes latérales » (appelé en anglais « coset coding »), également présenté dans l'article.
De retour au procédé de chiffrement, l'étape d'encodage 200 de la donnée binaire c est avantageusement réalisée au moyen d'un codage linéaire du type par classes latérales.
Ce type d'encodage exploite un code linéaire C de paramètres [n,k,d] avec une matrice de contrôle H de dimensions (n-k)*k.
L'encodage d'une donnée m est une donnée x telle que H'x=m. Pour décoder la donnée encodée x, on réalise l'opération m=H'x.
Dans le cas du procédé de chiffrement décrit en référence à la figure 1 , y est un vecteur de {0,1)' sélectionné aléatoirement parmi l'ensemble des vecteurs vérifiant H. y = c, où c est la donnée binaire à chiffrer, et H est une matrice de contrôle de dimension r*l du code linéaire sur lequel est basé le codage par classes latérales.
Au cours d'une étape 300, on génère une donnée chiffrée b telle que b = M. x + e + (y1( ... , y;, 0, ... ,0), où M est la matrice publique, c'est-à-dire la matrice creuse obtenue à l'étape 100, x est un vecteur en colonne binaire généré aléatoirement, de taille n, e est un vecteur en ligne de bruit binaire généré aléatoirement, de taille m, et les I premiers bits du terme (y1( ... , y;, 0, ... ,0) sont les éléments de l'encodage y de la donnée c, et les m-l derniers bits sont des 0. Avantageusement, les éléments du vecteur de bruit e sont des variables de Bernoulli, c'est-à-dire qu'ils suivent une loi de Bernoulli de paramètre ε : les éléments de e présentent donc la valeur 1 avec une probabilité ε. On note e -
RBer™.
De préférence, ε est une valeur très faible, de l'ordre de n~0-2 .Le rôle de ce vecteur de bruit est de rendre difficile la recherche de y à partir de b.
Le procédé de chiffrement mis en œuvre présente un niveau de sécurité élevé, notamment grâce à l'encodage de la donnée c par un codage vérifiant les propriétés du « wire-tap channel ».
En effet, comme indiqué précédemment, ce codage permet qu'un tiers qui obtiendrait une connaissance partielle de la donnée encodée y ne parviendrait pas à la décoder.
En l'espèce, un tiers qui obtiendrait la donnée chiffrée b ne pourrait donc pas parvenir à la déchiffrer car, même s'il obtient des informations partielles sur y, celles-ci ne lui donnent aucune information sur la donnée c. La donnée chiffrée b obtenue comprend donc m bits.
On va maintenant décrire le déchiffrement 2000 d'une donnée b, comprenant m bits, obtenue par la mise en œuvre du procédé décrit ci-avant. Pour ce faire, il est nécessaire de disposer de la clé secrète sk, c'est-à-dire de l'ensemble des ensembles indexés Sj.
On calcule alors, au cours d'une étape 2100, la somme des bits de b indexés par les éléments de Sj, pour chaque j compris entre 1 et I, ce qui correspond à un bit yj de la donnée encodée y. La séquence des yj constitue la donnée encodée y= ( i yc).
En effet, la sommation des éléments de M.x indexés par les éléments de Sj est nulle, du fait du choix des Sj. La sommation des éléments de b indexés par Sj donnera donc yj, additionné à un terme d'erreur négligeable. Par conséquent, les bits obtenus par la sommation des éléments de b, indexés par les ensembles Sj, sont les bits de y, au bruit près.
Au cours d'une étape 2200, on décode la donnée y obtenue en appliquant le décodage du code linéaire de type par classes latérales, c'est-à-dire c=H.y, où c est la donnée binaire déchiffrée. Le procédé de chiffrement proposé présente l'avantage d'être homomorphe pour l'opération « XOR » (OU exclusif) symbolisée par l'opérateur®, c'est-à-dire que pour deux messages Ci et c2 de I bits à chiffrer, on peut obtenir le chiffré de c ®c2 à partir de bi et b2, les données obtenues respectivement par le chiffrement de Ci et c2.
En l'occurrence, le ou-exclusif de bi et b2 est un chiffré possible de ct( c2 par le procédé de chiffrement 1000, c'est-à-dire que la mise en œuvre de l'opération ou exclusif entre bi et b2 correspond au chiffrement de c1®c2 par le même procédé de chiffrement 1000 avec les mêmes paramètres.
Cette propriété découle du caractère linéaire du code par classes latérales employé.
Procédé de calcul sécurisé de distance de Hamming
Le procédé de chiffrement et de déchiffrement décrit ci-avant permet la mise en œuvre d'un calcul sécurisé 3000 de distances de Hamming entre deux données binaires Ci et c2, ce calcul étant mis en œuvre conjointement par deux unités de traitement Ui et U2.
La notion de calcul « sécurisé » indique que le résultat du calcul doit être obtenu sans que chaque unité de traitement puisse avoir accès aux données détenues par l'autre.
Ce calcul peut être mis en œuvre selon deux variantes représentées respectivement en figures 3a et 3b, les étapes communes auxdites variantes étant représentées en figure 2.
En référence à la figure 2, le calcul sécurisé d'une distance de Hamming entre deux données binaires Ci et c2 est mis en œuvre entre les chiffrés bi et b2 correspondant auxdites données, obtenus par la mise en œuvre du procédé de chiffrement décrit ci-avant. On notera par la suite bi=E(q) pour indiquer qu'une donnée b, est le chiffré d'une donnée q par ce procédé de chiffrement.
Le procédé de calcul comprend l'obtention 3100 du chiffré du résultat de l'opération OU exclusif entre les données binaires non chiffrées E(c1©c2), ce résultat étant obtenu par la mise en œuvre de l'opération « OU exclusif » entre les chiffrés :b1@b2 = Ε^ε^φΕ^), d'après les propriétés homomorphes du procédé de chiffrement pour l'opération OU exclusif décrites ci-avant. Le procédé comprend ensuite la permutation 3200 des I premiers bits du résultat obtenu à l'étape précédente, par la mise en œuvre d'une permutation σ choisie aléatoirement. Le résultat obtenu correspond au chiffré de la permutation du résultat de l'opération « OU exclusif » entre les deux données c, non chiffrées, c'est- à-dire £,(a(c1©c2)). Or la permutation ne modifie pas le poids de Hamming d'une séquence de bits.
Donc le message a(c1©c2) présente le même poids de Hamming que c1( c2 , ce poids de Hamming correspondant donc à la distance de Hamming entre Ci et c2.
Il suffit donc, au cours d'une étape 3300 de déchiffrer le message E{O(C1@C2)) et déterminer le poids de Hamming du résultat obtenu pour obtenir la distance de Hamming entre Ci et c2.
Comme indiqué ci-avant, plusieurs implémentations de ce procédé par des unités de traitement Ui et U2 sont possibles.
Selon un premier mode de mise en œuvre, illustré en figure 3a, chaque unité de traitement Ui et U2 dispose respectivement d'une donnée binaire Ci , c2 et d'une clé publique pk du type employé dans le procédé décrit ci-avant. La clé secrète correspondante sk est détenue par une seule des deux unités, par exemple Ui.
Au cours d'une première étape 3010, chaque unité de traitement chiffre la donnée qu'elle détient par la mise en œuvre du procédé de chiffrement 1000 décrit ci-avant. L'unité Ui détenant la clé secrète transfère ensuite sa donnée chiffrée E(ci) à l'autre unité U2 au cours d'une étape 3020.
Puis, l'unité U2 met en œuvre l'opération OU exclusif 3100 entre les deux données chiffrées, choisit et effectue la permutation σ 3200 des I premiers bits du résultat obtenu pour obtenir£'(a(c1©c2)). L'unité U2 transfère ce résultat à l'unité Ui au cours d'une étape 3210 et l'unité Ui déchiffre le résultat, par la mise en œuvre du procédé de déchiffrement 2000, grâce à la clé secrète sk qu'elle détient, pour obtenir o c1@c2) et compte son poids de Hamming, pour obtenir la distance de Hamming entre Ci et c2.
Optionnellement, le résultat de la distance de Hamming entre les données peut être communiqué par l'unité Ui à l'unité U2. Selon un mode de mise en œuvre alternatif, représenté en figure 3b, l'unité de traitement Ui dispose à l'origine des deux données déjà chiffrées E(ci) et E(c2) et de la clé publique pk. L'unité de traitement U2 dispose quant à elle de la clé publique pk et de la clé privée sk.
Cette situation s'applique notamment au cas du traitement dématérialisé de données (en anglais, « cloud Computing »), où l'unité Ui est un serveur distant qui stocke des données confidentielles d'individus et ne doit pas y avoir accès.
Dans cette situation, c'est l'unité Ui qui effectue l'opération OU exclusif 3100 entre les deux données chiffrées, qui choisit et qui applique 3200 la permutation σ des I premiers bits du résultat obtenu. Puis, au cours d'une étape 3210, l'unité Ui transfère E(a(c1@c2j) obtenu à l'étape 3200 à l'unité U2.
Au cours d'une étape 3300, l'unité U2 déchiffre, par application du procédé 2000, grâce à la clé secrète qu'elle détient, la donnée reçue de l'unité U2 pour obtenir la donnée a(c1©c2), compte son poids de Hamming et obtient ainsi la distance de Hamming entre Ci et c2.
Optionnellement, l'unité U2 peut également transférer la distance de Hamming entre les données q à l'unité Ui.
Application à l'identification ou à l'authentification sécurisée
Cette méthode 3000 de calcul d'une distance de Hamming est avantageusement appliquée à l'identification (comparaison d'un individu à une pluralité d'individus candidats pour détecter une correspondance entre l'individu et un des candidats) ou l'authentification (comparaison d'un individu avec un individu candidat pour détecter une correspondance) biométrique d'un individu.
On compare alors une donnée biométrique d'un individu à une (dans le cas de l'authentification) ou plusieurs (dans le cas de l'identification) données d'individus répertoriés, chaque comparaison étant réalisée par calcul de la distance de Hamming entre les données.
Les données biométriques sont des encodages numériques de traits biométriques d'individus. Elles doivent correspondre à un même trait biométrique pour pouvoir être comparables : ce trait peut être un ou deux iris, une ou plusieurs empreintes digitales, la forme du visage, la forme du réseau veineux, l'ADN, les empreintes palmaires, etc. Un système d'identification ou d'authentification biométrique 1 d'un individu adapté pour la mise en œuvre du procédé 3000 comprend avantageusement un serveur de contrôle SC d'un individu à identifier et un serveur de gestion SG d'une base de données biométriques, ladite base comprenant au moins une donnée biométrique de référence c, acquise sur un individu répertorié.
Le serveur de contrôle SC comporte avantageusement des moyens pour acquérir une donnée biométrique b sur un individu à identifier ou authentifier. Il peut s'agir par exemple d'un lecteur d'empreintes digitales ou de document d'identité biométrique, ou d'un appareil photo.
Les serveurs de contrôle SC et de gestion SG sont avantageusement configurés pour mettre en œuvre l'une ou l'autre des variantes de mise en œuvre du procédé 3000 décrit ci-avant.
Dans la mise en œuvre représentée en figure 3a, l'unité de traitement U1 correspond avantageusement au serveur de contrôle SC qui acquière une donnée b sur un individu à identifier et compare ladite donnée à une ou plusieurs données c, détenues par le serveur de gestion pour obtenir, pour chaque Q, la distance de Hamming entre la donnée b et la donnée c,.
Typiquement, si une distance de Hamming entre b et une des données c, est inférieure à un seuil prédéterminé, une correspondance est détectée entre l'individu sur qui a été acquise la donnée b et l'individu de référence sur qui a été acquise la donnée Q.
Dans la mise en œuvre représentée en figure 3b, l'unité de traitement U2 correspond avantageusement au serveur de contrôle SC. Dans ce cas, les données de référence stockées dans la base sont déjà chiffrées, de sorte que le serveur de gestion SG ne puisse accéder qu'aux données chiffrées, et le serveur de contrôle chiffre la donnée b acquise sur l'individu avant de la transmettre au serveur de gestion.
Au terme du procédé 3000, le serveur de contrôle obtient la distance de Hamming entre la donnée b et une ou plusieurs données Q de la base, et peut de la même manière détecter une correspondance entre l'individu et un ou plusieurs individus répertoriés. On a donc présenté un procédé de chiffrement permettant de calculer de manière sécurisée une distance de Hamming sur des données entières, et non plus bit à bit, ce calcul pouvant en outre être appliqué à l'identification ou l'authentification biométrique.

Claims

REVENDICATIONS
1 . Procédé de chiffrement d'une donnée binaire (c) caractérisé en ce qu'il comprend les étapes consistant à :
générer une clé publique (pk) et une clé privée (sk), la clé publique étant une matrice (M) creuse comprenant m lignes et n colonnes, m étant supérieur au nombre I de bits de la donnée binaire, I étant un entier strictement supérieur à 1 , et la clé privée étant un ensemble de I ensembles indexés (Sj) d'entiers compris entre 1 et m tels que pour chaque ensemble, la somme des éléments des lignes de la matrice creuse indexées par les éléments d'un ensemble est nulle, et générer une séquence binaire b comprenant m bits, telle que b=Mx+e+y où
o x est un vecteur binaire aléatoire,
o e est un vecteur de bruit binaire aléatoire, et
o y est un encodage linéaire de la donnée c.
2. Procédé de chiffrement d'une donnée binaire selon la revendication précédente, dans lequel les éléments du vecteur e de bruit aléatoire sont des variables de Bernoulli.
3. Procédé de chiffrement d'une donnée binaire selon l'une des revendications 1 ou 2, dans lequel l'encodage y de la donnée c est configuré pour qu'une connaissance partielle de la donnée codée y ne soit pas décodable.
4. Procédé de chiffrement d'une donnée binaire selon l'une des revendications 1 à 3, dans lequel l'encodage y de la donnée c est un encodage linéaire par classes latérales, c'est-à-dire que y est un élément sélectionné au hasard parmi les éléments vérifiant la relation H'y=c, où H est une matrice de contrôle d'un code linéaire.
5. Procédé de chiffrement selon l'une des revendications 1 à 4, dans lequel la génération de la clé publique et de la clé privée comprend : la génération de I matrices indexées (Hj) de q lignes et n colonnes, où q est strictement inférieur à m, les lignes de chaque matrice comprenant chacune trois 1 et les colonnes de chaque matrice comprenant chacune zéro ou deux 1 ,
la génération d'une matrice creuse M comprenant m lignes et n colonnes,
la génération aléatoire de I ensembles indexés (Sj) d'entiers compris entre 1 et m tels que chaque ensemble comprend q éléments dont son index et tels que deux ensembles distincts ne comprennent aucun élément commun, et
pour chaque ensemble indexé, le remplacement des lignes de la matrice creuse M indexées par les éléments de l'ensemble, par les lignes de la matrice indexée correspondante.
6. Procédé de chiffrement selon l'une des revendications 1 à 4 dans lequel la génération de la clé publique et de la clé privée comprend :
la génération de I matrices d-creuses indexées Hj, où d est un entier pair supérieur à 3, comprenant chacune q lignes et q/3 colonnes, où q est strictement inférieur à m, chaque ligne d'une matrice comprenant d 1 , - la génération d'une matrice d-creuse M comprenant m lignes et n colonnes,
la génération aléatoire de I premiers ensembles indexés Uj, j compris entre 1 et I, d'entiers compris entre 1+1 et m tels que :
o chaque ensemble comprend q éléments, et
o deux ensembles distincts ne comprennent aucun élément commun,
la génération aléatoire de I seconds ensembles Tj, j compris entre 1 et I, d'entiers compris entre 1 et n, tels que chaque ensemble Tj comprend q/3 éléments,
- pour tout j compris entre 1 et I,
o le remplacement des éléments de M tel que :
" MUkitq = Hjk q pour tout uk e Uj, tq e 7}, et
■ MUk>q = 0 si q £ 7} o la permutation de la jeme ligne de M avec une ligne de M indexée par un élément de Uj qui est la somme des lignes de M indexées par les éléments d'un sous-ensemble Wj de II,, - la clé publique obtenue étant la matrice creuse M et la clé privée étant l'ensemble, pour j compris entre 1 et I, des unions des ensembles Wj avec le singleton j.
7. Procédé de déchiffrement d'une donnée chiffrée obtenue par l'application à une donnée binaire du procédé selon l'une des revendications précédentes, le procédé comprenant :
pour chaque ensemble d'entiers indexés Sj, la sommation binaire des bits de la donnée chiffrée indexés par les éléments de Sj, chaque bit obtenu correspondant au bit indexé par j de la donnée binaire encodée, et l'ensemble des bits indexés obtenus formant la donnée binaire encodée, et
le décodage de la donnée obtenue, la donnée décodée formant la donnée binaire déchiffrée.
8. Procédé de calcul sécurisé de l'opération « ou exclusif » entre deux données binaires chiffrées par la mise en œuvre du procédé selon l'une des revendications 1 à 6, comprenant les étapes consistant à :
déterminer, à partir des données chiffrées, une séquence de bits correspondant au chiffrement, par ledit procédé de chiffrement, du résultat de l'opération « ou exclusif » entre les deux données binaires, et - déchiffrer la séquence de bits obtenue par la mise en œuvre du procédé selon la revendication 7.
9. Procédé de calcul sécurisé d'une distance de Hamming entre deux données binaires chiffrées par la mise en œuvre du procédé selon l'une des revendications 1 à 6, le procédé comprenant les étapes consistant à :
d) déterminer, à partir des données chiffrées, le résultat correspondant au chiffrement par le procédé selon l'une des revendications 1 à 6, du résultat de l'opération « ou exclusif » entre les deux données non chiffrées, e) appliquer une permutation σ aux I premiers bits du résultat obtenu à l'étape a), et
f) déchiffrer la séquence de bits obtenue à l'étape b), et déterminer le poids de Hamming de la donnée obtenue.
10. Procédé de calcul sécurisé d'une distance de Hamming selon la revendication précédente, le procédé étant mis en œuvre conjointement par deux unités de traitement détenant chacune une des deux données binaires et une clé publique, une unité de traitement détenant en outre la clé secrète associée, et dans lequel :
chaque unité de traitement chiffre la donnée qu'elle détient à partir de la clé publique, l'unité détenant la clé secrète transmettant sa donnée chiffrée à la seconde unité,
la seconde unité met en œuvre les étapes a) et b) et transfère le résultat à la première unité, et
la première unité met en œuvre l'étape c).
1 1 . Procédé de calcul sécurisé d'une distance de Hamming selon la revendication 9, le procédé étant mis en œuvre conjointement par une unité-serveur détenant les deux données chiffrées et la clé publique, et une unité-client détenant la clé publique et la clé privée associée, et dans lequel :
l'unité-serveur met en œuvre les étapes a) et b) et transfère le résultat à l'unité client, et
l'unité-client met en œuvre l'étape c).
12. Procédé d'authentification ou d'identification d'un individu I, comprenant la comparaison d'une donnée binaire acquise sur l'individu à une ou plusieurs données binaire de référence acquises sur des individus répertoriés,
caractérisé en ce que chaque comparaison comprend le calcul de la distance de Hamming entre la donnée de l'individu et une donnée de la base, ledit calcul étant réalisé par la mise en œuvre du procédé selon l'une des revendications 9 à 1 1 .
13. Procédé selon la revendication 12, dans lequel la donnée de l'individu et la ou les données de la base sont des données biométriques obtenues par encodage d'un même trait biométrique sur l'individu et le ou les individus répertoriés.
14. Système d'identification ou d'authentification d'un individu, comportant au moins un serveur de contrôle d'un individu à identifier ou authentifier, et au moins un serveur de gestion d'une base de données de référence d'individus répertoriés, le serveur de contrôle étant adapté pour procéder à l'acquisition d'une donnée binaire biométrique d'un individu,
le système étant caractérisé en ce que le serveur de contrôle et le serveur de gestion sont adaptés pour :
calculer au moins une distance de Hamming entre la donnée de l'individu et au moins une donnée de la base, par la mise en œuvre du procédé selon l'une des revendications 9 à 1 1 , et
déterminer, à partir de la ou des distances de Hamming calculées, une ou plusieurs données de la base présentant des similarités avec la donnée de l'individu excédant un seuil prédéterminé.
PCT/EP2014/051759 2013-02-01 2014-01-30 Procede de chiffrement homomorphe pour le ou exclusif et calcul securise d'une distance de hamming WO2014118257A1 (fr)

Priority Applications (2)

Application Number Priority Date Filing Date Title
EP14701769.3A EP2951944A1 (fr) 2013-02-01 2014-01-30 Procede de chiffrement homomorphe pour le ou exclusif et calcul securise d'une distance de hamming
US14/764,955 US20150365229A1 (en) 2013-02-01 2014-01-30 Method of xor homomorphic encryption and secure calculation of a hamming distance

Applications Claiming Priority (2)

Application Number Priority Date Filing Date Title
FR1350904 2013-02-01
FR1350904A FR3001848B1 (fr) 2013-02-01 2013-02-01 Procede de chiffrement homomorphe pour le ou exclusif et calcul securise d'une distance de hamming

Publications (1)

Publication Number Publication Date
WO2014118257A1 true WO2014118257A1 (fr) 2014-08-07

Family

ID=49209453

Family Applications (1)

Application Number Title Priority Date Filing Date
PCT/EP2014/051759 WO2014118257A1 (fr) 2013-02-01 2014-01-30 Procede de chiffrement homomorphe pour le ou exclusif et calcul securise d'une distance de hamming

Country Status (4)

Country Link
US (1) US20150365229A1 (fr)
EP (1) EP2951944A1 (fr)
FR (1) FR3001848B1 (fr)
WO (1) WO2014118257A1 (fr)

Cited By (1)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
US11100082B2 (en) * 2017-03-10 2021-08-24 Symphony Communication Services Holdings Llc Secure information retrieval and update

Families Citing this family (27)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
SG11201608601TA (en) * 2014-04-23 2016-11-29 Agency Science Tech & Res Method and system for generating / decrypting ciphertext, and method and system for searching ciphertexts in a database
EP3270321B1 (fr) * 2016-07-14 2020-02-19 Kontron Modular Computers SAS Technique de mise en oeuvre d'une opération de manière sécurisée dans un environnement iot
US10812252B2 (en) 2017-01-09 2020-10-20 Microsoft Technology Licensing, Llc String matching in encrypted data
WO2018174063A1 (fr) * 2017-03-21 2018-09-27 日本電気株式会社 Système, procédé, dispositif et programme de classement
US11196539B2 (en) 2017-06-22 2021-12-07 Microsoft Technology Licensing, Llc Multiplication operations on homomorphic encrypted data
US10541805B2 (en) * 2017-06-26 2020-01-21 Microsoft Technology Licensing, Llc Variable relinearization in homomorphic encryption
US10749665B2 (en) 2017-06-29 2020-08-18 Microsoft Technology Licensing, Llc High-precision rational number arithmetic in homomorphic encryption
US11637694B2 (en) 2018-07-16 2023-04-25 Winkk, Inc. Secret material exchange and authentication cryptography operations
US10936703B2 (en) * 2018-08-02 2021-03-02 International Business Machines Corporation Obfuscating programs using matrix tensor products
ES2876926T3 (es) * 2018-11-07 2021-11-15 Advanced New Technologies Co Ltd Protección de datos de cadena de bloques utilizando cifrado homomórfico
US12153678B2 (en) 2019-12-10 2024-11-26 Winkk, Inc. Analytics with shared traits
US11588794B2 (en) 2019-12-10 2023-02-21 Winkk, Inc. Method and apparatus for secure application framework and platform
US11652815B2 (en) 2019-12-10 2023-05-16 Winkk, Inc. Security platform architecture
US12073378B2 (en) 2019-12-10 2024-08-27 Winkk, Inc. Method and apparatus for electronic transactions using personal computing devices and proxy services
US11553337B2 (en) 2019-12-10 2023-01-10 Winkk, Inc. Method and apparatus for encryption key exchange with enhanced security through opti-encryption channel
US11928193B2 (en) 2019-12-10 2024-03-12 Winkk, Inc. Multi-factor authentication using behavior and machine learning
US12143419B2 (en) 2019-12-10 2024-11-12 Winkk, Inc. Aggregated trust framework
US11574045B2 (en) 2019-12-10 2023-02-07 Winkk, Inc. Automated ID proofing using a random multitude of real-time behavioral biometric samplings
US11657140B2 (en) 2019-12-10 2023-05-23 Winkk, Inc. Device handoff identification proofing using behavioral analytics
US12132763B2 (en) 2019-12-10 2024-10-29 Winkk, Inc. Bus for aggregated trust framework
US11936787B2 (en) 2019-12-10 2024-03-19 Winkk, Inc. User identification proofing using a combination of user responses to system turing tests using biometric methods
US11328042B2 (en) 2019-12-10 2022-05-10 Winkk, Inc. Automated transparent login without saved credentials or passwords
US11843943B2 (en) 2021-06-04 2023-12-12 Winkk, Inc. Dynamic key exchange for moving target
US12095751B2 (en) 2021-06-04 2024-09-17 Winkk, Inc. Encryption for one-way data stream
US11824999B2 (en) * 2021-08-13 2023-11-21 Winkk, Inc. Chosen-plaintext secure cryptosystem and authentication
US20230084574A1 (en) * 2021-09-16 2023-03-16 UncommonX Inc. Bit sequence storage method and system
CN118034492B (zh) * 2023-12-29 2024-07-16 辉塔信息技术咨询(上海)有限公司 一种数字化多模态人机交互座舱模拟控制系统

Citations (2)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
FR2871910A1 (fr) * 2004-06-22 2005-12-23 Sagem Procede de codage de donnees biometriques, procede de controle d'identite et dispositifs pour la mise en oeuvre des procedes
WO2011010068A1 (fr) * 2009-07-23 2011-01-27 France Telecom Procede de conversion d'un premier chiffre en un deuxieme chiffre

Family Cites Families (4)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
US5295188A (en) * 1991-04-04 1994-03-15 Wilson William J Public key encryption and decryption circuitry and method
US20110047377A1 (en) * 2009-08-19 2011-02-24 Harris Corporation Secure digital communications via biometric key generation
US8310922B2 (en) * 2010-04-15 2012-11-13 International Business Machines Corporation Summarizing internet traffic patterns
US20120308089A1 (en) * 2011-06-03 2012-12-06 Korea Basic Science Institute Method of biometric authentication by using pupil border and apparatus using the method

Patent Citations (2)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
FR2871910A1 (fr) * 2004-06-22 2005-12-23 Sagem Procede de codage de donnees biometriques, procede de controle d'identite et dispositifs pour la mise en oeuvre des procedes
WO2011010068A1 (fr) * 2009-07-23 2011-01-27 France Telecom Procede de conversion d'un premier chiffre en un deuxieme chiffre

Non-Patent Citations (4)

* Cited by examiner, † Cited by third party
Title
RYO NOJIMA ET AL: "Semantic security for the McEliece cryptosystem without random oracles", DESIGNS, CODES AND CRYPTOGRAPHY, KLUWER ACADEMIC PUBLISHERS, BO, vol. 49, no. 1-3, 6 March 2008 (2008-03-06), pages 289 - 305, XP019602834, ISSN: 1573-7586 *
S. GOLDWASSER; S. MICALI: "Probabilistic encryption and how to play mental poker keepinq secret all partial information", 1982, ACM, pages: 365 - 377
SHIGENORI YAMAKAWA ET AL: "On the Key-Privacy Issue of McEliece Public-Key Encryption", 16 December 2007, APPLIED ALGEBRA, ALGEBRAIC ALGORITHMS AND ERROR-CORRECTING CODES; [LECTURE NOTES IN COMPUTER SCIENCE], SPRINGER BERLIN HEIDELBERG, BERLIN, HEIDELBERG, PAGE(S) 168 - 177, ISBN: 978-3-540-77223-1, XP019085340 *
WYNER, A.D.: "The wire-tap channel", THE BELL SYSTEM TECHNICAL JOURNAL, vol. 54, no. 8, pages 1355 - 1387, XP011631496, DOI: doi:10.1002/j.1538-7305.1975.tb02040.x

Cited By (3)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
US11100082B2 (en) * 2017-03-10 2021-08-24 Symphony Communication Services Holdings Llc Secure information retrieval and update
US20220012228A1 (en) * 2017-03-10 2022-01-13 Symphony Communication Services Holdings Llc Secure information retrieval and update
US11966380B2 (en) * 2017-03-10 2024-04-23 Symphony Communication Services Holdings Llc Secure information retrieval and update

Also Published As

Publication number Publication date
EP2951944A1 (fr) 2015-12-09
US20150365229A1 (en) 2015-12-17
FR3001848B1 (fr) 2015-01-09
FR3001848A1 (fr) 2014-08-08

Similar Documents

Publication Publication Date Title
WO2014118257A1 (fr) Procede de chiffrement homomorphe pour le ou exclusif et calcul securise d'une distance de hamming
EP2323306B1 (fr) Procédé de transmission de données sécurisé et système de chiffrement et de déchiffrement permettant une telle transmission
EP2819052B1 (fr) Procédé et serveur de traitement d'une requête d'accès d'un terminal à une ressource informatique
FR3054905B1 (fr) Procede de generation de cle et procede de controle d'acces
WO2020169542A1 (fr) Méthode cryptographique de vérification des données
WO2012093216A1 (fr) Dispositif et procède de stockage en ligne, dispositif et procède d'émission, dispositif et procède de réception
EP2909963B1 (fr) Procédé de signature électronique à signature ephémère
CN103093411A (zh) 基于随机二态图像的加密-解密方法
WO2011083232A1 (fr) Procede de chiffrement et de dechiffrement
EP4227832A1 (fr) Schema d'authentification post-quantique optimise sans signature, procedes et dispositifs
EP2568406B1 (fr) Procédé de mise en oeuvre, a partir d'un terminal, de données cryptographiques d'un utilisateur stockées dans une base de données
EP3769461A1 (fr) Procede d'emission de donnees depuis un vehicule automobile et procede de reception desdites donnees par un autre vehicule, a travers un canal de communication radio
CA2613884C (fr) Procede pour disposer d'un lien de communication securise entre un utilisateur et une entite
WO2023046557A1 (fr) Système et méthode de génération de clé secrète sûre
EP2659615A1 (fr) Procede et systeme permettant de tester une integrite cryptographique d'une donnee tolerante aux erreurs
FR3117718A1 (fr) Méthode de divulgation sélective de données via une chaine de blocs
FR2925730A1 (fr) Procede et systeme pour authentifier des individus a partir de donnees biometriques
WO2024125942A1 (fr) Procedes de distribution quantique et dispositifs de telecommunication associes
FR3038759A1 (fr) Cryptage avec geolocalisation embarquee
WO2021156078A1 (fr) Procédé et dispositif d'évaluation de correspondance d'ensembles de données structurées protégées par le chiffrement
EP4099614A1 (fr) Procédés d'enrolement de données pour vérifier l'authenticité d'une donnée de sécurité ou de verification de l'authenticité d'une donnée de securité
WO2021165625A1 (fr) Procede de calcul d'une cle de session, procede de recuperation d'une telle cle de session
FR3143148A1 (fr) Procédés d’authentification mutuelle, dispositif électronique, système et programmes d’ordinateur associés.
WO2007101966A1 (fr) Authentification d'un dispositif informatique au niveau utilisateur

Legal Events

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

Ref document number: 14701769

Country of ref document: EP

Kind code of ref document: A1

WWE Wipo information: entry into national phase

Ref document number: 14764955

Country of ref document: US

NENP Non-entry into the national phase

Ref country code: DE

WWE Wipo information: entry into national phase

Ref document number: 2014701769

Country of ref document: EP

点击 这是indexloc提供的php浏览器服务，不要输入任何密码和下载