WO2018124869A1 - Un efficace cryptosysteme entierement homomorphe a base des quaternions. - Google Patents
Un efficace cryptosysteme entierement homomorphe a base des quaternions. Download PDFInfo
- Publication number
- WO2018124869A1 WO2018124869A1 PCT/MA2018/050005 MA2018050005W WO2018124869A1 WO 2018124869 A1 WO2018124869 A1 WO 2018124869A1 MA 2018050005 W MA2018050005 W MA 2018050005W WO 2018124869 A1 WO2018124869 A1 WO 2018124869A1
- Authority
- WO
- WIPO (PCT)
- Prior art keywords
- matrix
- cryptosystem
- quaternion
- transform
- homomorphic
- Prior art date
- Legal status (The legal status is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the status listed.)
- Ceased
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
Definitions
- the present invention relates to a fully homomorphous (EH) and probabilistic symmetric cryptosystem based on the use of quaternions, more particularly the use of the Lipschitz integer ring.
- This cryptosystem uses a homomorphic transformation between the Z / 2Z ring (the clear space) and the Lipschitz integer ring (the space of the encrypted messages) to transform a binary number ⁇ 0,1 ⁇ into a quaternion of Lipschitz before encrypting it.
- Homomorphic encryption is a great solution for this problem, its idea is very simple: do the calculation on encrypted data. If a cryptosystem allows a limited number of operations on the encrypted data, it is said to be partially homomorphic. If necessary a cryptosystem, to evaluate any treatment on the encrypted data, is said to be entirely homomorphic.
- An EH cryptosystem is defined, in general, as being a quadruplet of algorithms (Gen, Enc, Dec, Eval), executing in polynomial time, such as:
- Enc (m, pk) is an encryption algorithm, takes as input a clear message m and a so-called public key pk and outputs a cryptogram c.
- Dec (c, sk) is a decryption algorithm, takes as input a cryptogram c and a so-called secret key sk and outputs the clear message.
- Eval (C, c 1 , ..., c n ): is an evaluation algorithm, takes as input a circuit C and cryptograms c 1; . . , c n and check
- Gentry After having withstood nearly three decades, the conjecture of Rivest et al was finally resolved in 2009 by Craig Gentry. This invention has been the subject of US20110110525. Indeed, Gentry gave a renaissance to homomorphic cryptography research by designing an EH encryption scheme considered semantically safe. Gentry's design can be summarized in three main steps: • Somewhat Homomorphic Encryption Scheme (SWHE): Gentry starts from a schema called SWHE or simply homomorphic which supports a limited number of homomorphic multiplication.
- SWHE Homomorphic Encryption Scheme
- Bootstrapping The bootstrap procedure invented by Gentry consists of the evaluation of the decryption circuit plus the NAND to obtain a so-called 'leveled' FHE scheme which makes it possible to evaluate any circuit with a depth of the circuit initially defined.
- This first scheme is based on the addition of noise to clear to obtain rhomomorphic cryptosystem.
- the major disadvantage of noisy schemes is the growth of noise after each manipulation of the cryptogram (addition and / or multiplication). Indeed, in order to keep the decryption capacity we must control and reduce the noise generated after each treatment. Noise control in this type of diagram increases their spatial and temporal complexity, which results in a slowness of calculations (especially during bootstrapping) and a greed for the storage space required for storing the results (noise amplification).
- the MORE cryptosystem is a symmetric cryptosystem based on modular arithmetic whose homomorphism derives from the usual matrix operations, its multiplication and addition are matrix multiplication and addition.
- the clear space is the ring Z / nZ (ring of the integer residuals modulo n) where n is a modulo chosen as in the famous RSA algorithm whereas the space of the cryptograms is the ring modular matrices M 2 (Z / nZ).
- the secret key of this cryptosystem is an invertible matrix K 6 M 2 (Z / nZ) chosen randomly by the client and kept confidential with its inverse K ⁇ .
- the MORE cryptosystem is not resistant to IND-CPA attacks (Indistinguishability under Chosen Plaintext Attack) and IND-KPA (Indistinguishability under Known Plaintext Attack). Indeed, if a third party of bad faith has access to only one clear and its cryptogram it will be able to decrypt any message encrypted thereafter without having found the secret key.
- the cryptosystem MORE has been cryptanalyzed several times [http://eprint.iacr.org/2014/250.pdf, https://www.academia.edu/26297806/].
- a noiseless construction that uses raster operations as described in the MORE framework.
- This construction has the advantage of being very simple, easy to implement and provides very fast operations for any processing on cryptograms.
- the major disadvantage of this construction lies in the safety of the schemes designed so far.
- the schemas based on the MORE framework have been attacked by IND-CPA and IND-KPA.
- a second disadvantage resulting from the cryptosystem MORE is that it is just partially homomorphic even if its authors declare its complete homomorphism in the patent WO2014016795A2. Indeed, this scheme is unable to handle any type of processing on cryptograms.
- a first objective of the present invention is to improve the execution time of EH cryptosystems. For this reason we will adopt the MORE framework as a build basis instead of the Gentry framework which requires a very slow bootstrap step. Our second goal is to overcome the overwhelming obstruction of security in earlier cryptosystems. We offer a safer EH cryptosystem than its predecessors and resistant to IND-CPA and IND-KPA attacks. Finally we aim that our cryptosystem is completely homomorphic, that is to say it allows to execute any type of processing on messages encrypted antipodes MORE scheme. Therefore, the choice of a well adapted space of clear is essential to concretize the whole homomorphy of our cryptosystem.
- Figure 1 represents, in general, the operation of a cryptosystem EH. It explains how the Eval algorithm can be used in an encrypted data context.
- FIG. 2 shows the two encryption and decryption strings for our EH cryptosystem.
- Figure 3 shows how we can use our cryptosystem in a computing delegation situation in a cloud.
- a quaternion is a number in a generalized sense. Quaternions encompass real and complex numbers in a system of numbers where multiplication is no longer a commutative law.
- the quaternion is the conjugate of f
- a quaternion q is invertible if and only if its module is non-zero, and we have
- the set of quatemions defines as follows:
- a modular Lipschitz quatemion is invertible if and only if its module is
- the set of matrices describes the matrices with four inputs (two rows and two columns) which are quatemions of This set has a non ring structure
- the Hamiltonian product is defined as for all matrices with coefficients in a ring (not necessarily commutative). For example :
- the octonionic product does not respect the order of the factors: on the main diagonal, there is switching of the second products and on the second diagonal there is switching of the first products.
- Any associative ring, a matrix is said to be invertible if such
- the Schur complement method is a very powerful tool for calculating inverses of matrices in rings.
- M 6 Jl nxn be a matrix per block verifying:
- bitToQuatern transform represents the bitToQuatern transform whose arrival set is for an integer n that will be defined.
- any permutation ⁇ of the triplet generates a transformed bitToQuatern who has the same properties as the transformed bitToQuatern.
- the inverse transform for bitToQuatern has remained unchangeable.
- the secret key is (K, K -1 ).
- patient data such as the biometric identifier, the social security number, the age and the state of health are personal data.
- the use of these data for medical research and pharmacovigilance raises the question of confidentiality of this type of data, with the rules of ethics and respect for privacy.
- our encryption scheme allows for processing on medical data and providing the requested results while preserving data privacy and patient privacy.
- Private Information Retrieval In cryptography, Private Information Retrieval (RIP) is a protocol that allows a user to retrieve an item from a database without revealing to the server which item has been retrieved. Homomorphic encryption makes it easy to perform such protocols. Our cryptosystem has the homomorphic property that allows it to easily perform the RIP protocol.
- Multi-part calculation in multi-part calculation systems, several parties are interested in calculating a common function, without being able to disclose their private data.
- the function to be calculated is publicly known, while the individual entries of the different users must remain unknown for the other parts of the system. This problem comes from the problem of computation with the encrypted data, from where the utility of the use of the homomorphic cryptography.
- the asymmetric version of our cryptosystem allows to implement multiparty calculations.
- the electronic voting is a special case of calculation delegation to a third party able to calculate the result of the elections without disclosing the identities of the different candidates.
- homomorphic encryption allows the electoral authorities to count the votes and present the final results without going through the process of deciphering the votes and counting them afterwards.
- voters are just allowed to increment a counted count of 1 (indicating a vote for the candidate) where 0 (indicating the case of non-voting).
- voters change the encrypted scores by adding an i-bit vector, where exactly one entry is 1 and the rest are all 0. And they are unable to modify the counters. in any other way.
- the asymmetric version of our cryptosystem allows to implement a secure electronic voting system.
Landscapes
- Engineering & Computer Science (AREA)
- Computer Security & Cryptography (AREA)
- Computer Networks & Wireless Communication (AREA)
- Signal Processing (AREA)
- Information Retrieval, Db Structures And Fs Structures Therefor (AREA)
- Storage Device Security (AREA)
Abstract
La présente invention concerne un cryptosystème entièrement homomorphe efficace basé sur une nouvelle transformée homomorphe et probabiliste entre l'anneau ℤ⁄2ℤ (anneau des entiers résidus modulo 2) et l'anneau des entiers de Lipschitz modulaire. Notre cryptosystème est apte à traiter des messages clairs sous forme de bits en entrée et fournir des cryptogrammes sous forme de matrices de quaternions de Lipschitz modulo un grand nombre entier naturel pair n d'une manière non déterministe. La sécurité dudit cryptosystème est basée sur la difficulté de résoudre un système d'équations polynomiales multi variées dans un anneau non commutatif. Ce cryptosystème permet de réduire davantage le temps de calcul des multiplications chez les algorithmes de cryptage entièrement homomorphe (EH), comme il permet de minimiser la taille d'une clé secrète et de réduire l'expansion des cryptogrammes.
Description
Titre : UN EFFICACE CRYPTOSYSTEME ENTIEREMENT HOMOMORPHE A BASE DES
QUATERIONS,
Description :
Domaine technique
La présente invention concerne un cryptosystème symétrique entièrement homomorphe (EH) et probabiliste basé sur l'utilisation des quaternions, plus particulièrement l'utilisation de l'anneau des entiers de Lipschitz. Ce cryptosystème utilise une transformation homomorphe entre l'anneau Z/2Z (L'espace des clairs) et l'anneau des entiers de Lipschitz (l'espace des messages chiffrés) pour transformer un nombre binaire {0,1} en un quaternion de Lipschitz avant de le chiffrer.
Etat antérieur
Après la conjecture de Rivest et al [R. Rivest, L. Adleman, and M. Dertouzos. "on data banks and privacy homomorphisms", Foundations of Secure Computation, pp 169-180, 1978], la conception d'un schéma de cryptage EH restait l'ambition de chaque cryptologue. L'apparition du cloud Computing dans la dernière décennie a excité les efforts des chercheurs pour réaliser ce rêve. En effet, le cloud permet de mutualiser les structures de conservation et de traitement des données. Le traitement des données est considéré comme une force majeure du cloud car ce dernier dispose de puissances de calcul illimitées. Pour bénéficier de ces privilèges on arrive souvent à déléguer aux serveurs du cloud d'effectuer des calculs complexes sur des données privées. Avec le cryptage usuel, le fournisseur du cloud doit décrypter les données avant de faire les calculs demandés. Cependant, l'un des inconvénients de ceci est la préservation de la confidentialité entre le client et le fournisseur. Le cryptage homomorphe est une solution géniale pour ce problème, son idée est très simple : faire le calcul sur des données chiffrées. Si un cryptosystème permet un nombre limité d'opérations sur les données chiffrées, il est dit partiellement homomorphe. Le cas échéant un cryptosystème, permettant d'évaluer n'importe quel traitement sur les données chiffrées, est dit entièrement homomorphe.
Un cryptosystème EH est définit, en général, comme étant un quadruplet d'algorithmes (Gen, Enc, Dec, Eval), s'exécutant en temps polynomial, tels que :
• Gen(X) : est un algorithme de génération de clés, prend en entrée un paramètre de sécurité λ et donne en sortie un pair de clés (sk, pk).
• Enc(m, pk): est un algorithme de cryptage, prend en entrée un message clair m et une clé dite publique pk et donne en sortie un cryptogramme c.
• Dec(c, sk): est un algorithme de décryptage, prend en entrée un cryptogramme c et une clé dite secrète sk et donne en sortie le message clair.
• Eval(C , c1, . . , cn): est un algorithme d'évaluation, prend en entrée un circuit C et des cryptogrammes c1; . . , cn et vérifie
Après avoir résisté à peu près trois décennies, la conjecture de Rivest et al a été enfin résolue en 2009 par Craig Gentry. Cette invention a fait l'objet du brevet US20110110525. En effet, Gentry a donné une renaissance aux recherches de la cryptographie homomorphe par la conception d'un schéma de cryptage EH considéré sémantiquement sûr. La conception de Gentry peut être récapitulée en trois grandes étapes principales :
• Somewhat Homomorphic Encryption Scheme (SWHE) : Gentry part d'un schéma dit SWHE ou simplement homomorphe qui supporte un nombre limité de multiplication homomorphe.
• Squashing du circuit de décryptage : Gentry réduit la complexité du circuit de déchiffrement en publiant un ensemble de vecteurs dont la somme d'une partie d'entre eux est égale à la clé secrète. Ce schéma dit 'squashé' peut évaluer, en plus de ses capacités SWHE, une porte NAND.
• Bootstrapping : la procédure du bootstrap inventée par Gentry consiste en l'avaluation du circuit de décryptage plus le NAND pour obtenir un schéma dit 'leveled' FHE qui permet d'évaluer n'importe quel circuit avec une profondeur du circuit définit au départ.
Ce premier schéma est basé sur l'ajout de bruit au clair pour obtenir rhomomorphie du cryptosystème. L'inconvénient majeur des schémas bruités est la croissance du bruit après chaque manipulation du cryptogramme (addition et/ou multiplication). En effet, afin de garder la capacité de décryptage on doit contrôler et réduire le bruit généré après chaque traitement. Le contrôle du bruit dans ce type schémas augmente leur complexité spatiale et temporelle ce qui se traduit par une lenteur des calculs (surtout pendant le bootstrapping) et une gourmandise de l'espace mémoire demandé pour le stockage des résultats (amplification de bruit). Une chose qui influence la pratique et l'application du chiffrement EH à la vie quotidienne. Toutes ces causes ont encouragé les chercheurs de trouver d'autres frameworks de conception de schémas de cryptage EH afin de rendre applicable le chiffrement EH.
Parmi les tentatives les plus éminentes de simplification des schémas de cryptage EH, on trouve le cryptosystème MORE. Ce dernier a fait l'objet du brevet WO2014016795A2. C'est un cryptosystème symétrique basé sur l'arithmétique modulaire dont l'homomorphie découle des opérations matricielles usuelles, sa multiplication et son addition sont la multiplication et l'addition matricielles. Dans le schéma de cryptage MORE, l'espace des clairs est l'anneau Z/nZ (anneau des entiers résidus modulo n) où n est un modulo choisi comme dans le célèbre algorithme RSA alors que l'espace des cryptogrammes est l'anneau des matrices modulaires M2 (Z/nZ). La clé secrète de ce cryptosystème est une matrice inversible K 6 M2 (Z/nZ) choisie aléatoirement par le client et conservée confidentielle avec son inverse K~ .
Toutefois, le cryptosystème MORE ne résiste pas aux attaques de types IND-CPA(Indistinguishability under Chosen Plaintext Attack) et IND-KPA(Indistinguishability under Known Plaintext Attack). En effet, si un tiers de mauvaise foi ait accès à un seul clair et à son cryptogramme il pourra déchiffrer tout message chiffré par la suite sans avoir trouvé la clé secrète. Le cryptosystème MORE a été cryptanalysé plusieurs fois [http://eprint.iacr.org/2014/250.pdf, https://www.academia.edu/26297806/].
Une seconde tentative, pour pallier les failles de sécurité du schéma MORE et construire un cryptosystème EH, est récemment due à Wang et Li [http://eprint.iacr.org/2015/641.pdfj . Les deux auteurs ont gardé presque la même conception de MORE sauf qu'ils ont proposé de changer l'anneau Z/nZ par un anneau R non commutatif et ils ont utilisé des matrices carrées d'ordre 3 au lieu des matrices d'ordre 2. Malgré l'utilisation d'un anneau non commutatif R, les messages clairs restent toujours des nombres qui commutent avec les éléments de R.
Par conséquent une attaque du schéma de Wang et Li est donné par Kristian Gjosteen et Martin Strand dans [http://eprint.iacr.org/2016/105.pdfj . En effet, d'après ces auteurs: pour attaquer le cryptosystème de Wang-Li, nous avons seulement besoin de distinguer les cryptages de 0 à partir d'un cryptage aléatoire.
Les deux auteurs ont observé que la diagonale de la matrice cryptogramme détermine complètement l'inversibilité de ladite matrice, car un cryptogramme de "0" ne peut être inversible. Donc, avec une grande probabilité, on peut distinguer les éléments inversibles de l'anneau R des éléments non- inversibles. Si l'anneau R est à division, alors il n'y a pas d'autres éléments non-inversibles que "0". Enfin, en utilisant une variante de la décomposition LU adaptée aux anneaux non commutatifs on peut calculer efficacement la matrice clé secrète de l'algorithme.
D'après ce qui est venu avant, on peut signaler qu'il existe deux types de construction de cryptosystèmes EH :
4- Une construction à base de bruit qui utilise la technique du bootstrap comme elle est décrite dans le framework de Gentry. L'avantage de cette construction est sa sûreté, vu que les schémas conçu jusqu'à présent (à partir de cette démarche) sont basés sur des problèmes mathématiques issus de la théorie des réseaux euclidiens, qui demeure quand même une théorie immune et complexe. Alors que son inconvénient majeur réside dans la lenteur de ses opérations (surtout le bootstrap) et la complexité de ses algorithmes.
Une construction sans bruit qui utilise les opérations matricielles comme il est décrit dans le framework MORE. Cette construction a l'avantage d'être très simple, facile à implémenter et fournit des opérations très rapides pour tout traitement sur les cryptogrammes. L'inconvénient capital de cette construction réside dans la sûreté des schémas conçus jusqu'à présent. Les schémas conçus à base du framework MORE ont fait l'objet des attaques de type IND-CPA et IND-KPA. Un second désavantage issu du cryptosystème MORE c'est qu'il est juste partiellement homomorphe même si ses auteurs déclarent son entière homomorphie dans le brevet WO2014016795A2. En effet, ce schéma est incapable de manipuler tout type de traitement sur les cryptogrammes. Prenons à titre d'exemple le cryptogramme C = MORE (m) du message clair m = N— 1, où N est le modulo utilisé dans ce cryptosystème, si on calcule C = C2 et on décrypte le résultat on obtient m' = 1≠ m2 = N— l)2, car les opérations sont effectuées modulo N.
Un premier objectif de la présente invention est d'améliorer le temps d'exécution des cryptosystèmes EH. Pour cette raison nous allons adopter le framework MORE comme base de construction au lieu du framework de Gentry qui exige une étape de bootstrap très lente. Notre second objectif est de franchir l'entrave saisissante de la sécurité dans les cryptosystèmes antérieurs. Nous proposons un cryptosystème EH plus sûr que ses précédents et résistant aux attaques IND-CPA et IND-KPA. Finalement nous visons que notre cryptosystème soit entièrement homomorphe, c'est-à-dire il permet d'exécuter tout type de traitement sur les messages chiffrés aux antipodes du schéma MORE. Par conséquent, le choix d'un espace de clairs bien adapté est primordial pour concrétiser l'entière homomorphie de notre cryptosystème. Nous envisageons utiliser l'espace binaire, sanctionné par les deux opérations XOR et AND, (c'est l'anneau Z/2Z) comme espace de clairs pour notre schéma de cryptage. En plus de çà, nous utilisons une transformée homomorphe qui convertit un bit en un quaternion de Lipschitz. Cela permet de randomiser les bits afin de garantir que la diagonale ne donne aucune information utile sur le clair (éviter l'attaque du cryptosystème de Li-Wang).
Notre cryptosystème résiste aux attaques IND-CPA et IND-KPA par la non-commutativité de l'anneau des quaternions de Lipschitz et par l'utilisation d'un espace de clair plus réduit (l'anneau Z/2Z). Il hérite son homomorphie d'une part des opérations matricielles et d'autre part d'une nouvelle transformation homomorphe, entre l'anneau Z/2Z et l'anneau des entiers de Lipschitz, que nous avons inventée. Son entière homomorphie est obtenue par la manipulation de ces entiers de Lipschitz à l'aide d'un modulo pair (n = 2. p. q).
Description des figures
La figure 1 représente, en général, le fonctionnement d'un cryptosystème EH. Elle explique comment on peut utiliser l'algorithme Eval dans un contexte de calcul à données chiffrées.
La figure 2 représente les deux chaînes de cryptage et de décryptage pour notre cryptosystème EH.
La figure 3 représente comment on peut utiliser notre cryptosystème dans une situation de délégation de calcul chez un cloud.
Le corps des quaternions
Un quaternion est un nombre dans un sens généralisé. Les quaternions englobent les nombres réels et complexes dans un système de nombres où la multiplication n'est plus une loi commutative.
Les quaternions furent introduits par le mathématicien irlandais William Rowan Hamilton en 1843. Ils trouvent aujourd'hui des applications en mathématiques, en physique, en informatique et en sciences de l'ingénieur.
Mathématiquement, l'ensemble des quaternions
est une algèbre associative non-commutative sur le corps des nombres réels
engendrée par trois éléments
satisfaisant les relations:
Concrètement, tout quaternion q s'écrit de manière unique sous la forme :
sont des nombres réels.
Les opérations d'addition et de multiplication par un scalaire réel se font termes à termes, alors que La multiplication entre deux quaternions se fait termes à termes en respectant la non-commutativité et les règles propres à
Ainsi pour
on a
Le quaternion
est le conjugué de
f
module de q. La partie réelle de et la partie imaginaire est
Un quaternion q est inversible si et seulement si son module est non nulle, et on a
Forme réduite d'un quaternion :
On peut représenter un quaternion d'une manière plus économique, ce qui allège considérablement les calculs et met en valeur des résultats intéressants. En effet, il est aisé de voir que
vectoriel de dimension 4, dont
constitue une base orthonormale directe. On peut donc séparer la composante réelle des composantes pures, et on a pour vecteur de
On a donc pour
Anneau des entiers de Lipschitz
L'ensemble des quatemions définit comme suit :
possède une structure d'anneau appelé anneau des entiers de Lipschitz. est trivialement non-
commutatif.
Pour n 6 N*, l'ensemble des quatemions:
possède une structure d'anneau non-commutatif.
Un quatemion modulaire de Lipschitz est inversible si et seulement si son module est
premier avec n, c'est-à-dire \q \2 A n = 1.
Matrices quaternioniques de
L'ensemble des matrices
décrit les matrices à quatre entrées (deux lignes et deux colonnes) qui sont des quatemions de Cet ensemble possède une structure d'anneau non
commutatif.
Il existe deux manières de multiplier les matrices quaternioniques : le produit hamiltonien, qui respecte l'ordre des facteurs, et le produit octonionique, qui ne le respecte pas.
• Le produit hamiltonien est défini comme pour toutes les matrices à coefficients dans un anneau (non nécessairement commutatif). Par exemple :
• Le produit octonionique ne respecte pas l'ordre des facteurs : sur la diagonale principale, il y a commutation des deuxièmes produits et sur la deuxième diagonale il y a commutation des premiers produits.
Dans notre rapport nous allons adopter le produit hamiltonien comme opération de multiplication des matrices quaternioniques.
Complément de Schur et inversibilité des matrices quaternioniques
Soit un anneau associatif quelconque, une matrice est dite inversible si tel
que MN = NM = In où N est nécessairement unique.
La méthode du complément de Schur est un outil très puissant pour le calcul des inverses des matrices dans des anneaux. Soit M 6 Jlnxn une matrice par bloc vérifiant :
Supposant A est inversible, on a :
le complément de Schur de A dans M.
L' inversibilité de A assure que la matrice M est inversible si est seulement si As l'est. L'inverse de M eSt
inversible ainsi que son complément de Schur as = d— ca-1b on a est inversible et:
Donc pour générer aléatoirement une matrice quaternionique inversible, il suffit de : (***)
• Choisir aléatoirement trois quaternions a, b et c dont a est inversible.
• Sélectionner aléatoirement le quatrième quaternion d de telle sorte que le complément de Schur as = d— ca~xb de a dans M soit inversible.
Description de la transformée et du cryptosystème
Transformée homomorphe entre
Tout bit σ 6 Ί./2Ί. = {0,1} peut être transformé en un quaternion de Lipschitz selon une transformée homomorphe dont les opérations sur les quaternions conservent celles sur les bits. On peut donner cette transformée comme suit :
bitToQuatern:
sont des entiers relatifs choisis aléatoirement respectant les deux conditions:
La transformée inverse qui sera nommée quaternToBit est donnée par :
On peut vérifier facilement rhomomorphie de la transformée bitToQuatern:
• pour l'addition on a bien :
• Pour la multiplication, en passant à la notation réduite des quaternions, on a
Le fait que la réduction modulo un nombre pair d'un entier relatif conserve sa parité (c'est-à-dire
permet de changer l'ensemble d'arrivée
de la transformée bitToQuatern par l'ensemble
en conservant son homomorphie et en obtenant les mêmes propriétés. Dans le reste de ce rapport la transformée bitToQuatern représente la transformée bitToQuatern dont l'ensemble d'arrivée est
pour un entier n qui sera définit.
Remarque : toute permutation σ du triplet
engendre une transformée bitToQuaterna ayant les même propriétés que la transformée bitToQuatern. La transformée inverse pour bitToQuaterna reste inchangeable.
Cryptosystème entièrement homomorphe et efficace
On se place dans un contexte où Bob veut stocker des données confidentielles dans un cloud très puissant mais non confiant. Bob aura besoin plus tard de faire des traitements complexes, sur ses données, dont il ne dispose pas des puissances de calcul nécessaires pour les effectuer. A ce niveau il pense, à priori, au chiffrement de ses données sensibles pour éviter toute action frauduleuse. Mais le chiffrement usuel, qu'il connaisse, ne permet pas au cloud de traiter ses requêtes de calcul sans avoir déchiffré les données stockées au préalable, ce qui met en cause leur confidentialité. Bob demande s'il
existe un type de chiffrement pratique et efficace permettant de traiter ses données sans les révéler au cloud. La réponse à la demande de Bob est favorable, en effet depuis 2009 il existe des cryptosystèmes dits entièrement homomorphes, dont le principe est assez simple : faire les calculs sur les données chiffrées sans penser à aucun préalable déchiffrement.
Pour être entièrement homomorphe, il suffit qu'un cryptosystème permette de réaliser les deux opérations d'addition et de multiplication une multitude de fois sur les cryptogrammes. Depuis leur première apparition en 2009, les cryptosystèmes EH permettent de réaliser facilement les additions alors que la multiplication reste très coûteuse en terme du temps de calcul et épuisante en terme du bruit généré. Réellement, en moyen, une addition double le bruit d'un message chiffré alors qu'une multiplication l'enlève au carré.
Afin de bénéficier agréablement de l'avancée technologique du cloud et extemaliser ses calculs lourds confortablement, Bob a besoin d'un cryptosystème EH robuste en termes de sécurité, dont les opérations d'addition et de multiplication se font en un temps judicieux et dont le bruit généré lors d'un traitement est maîtrisable.
Pour aider Bob à profiter pleinement des puissances du cloud, nous avons inventé un cryptosystème symétrique probabiliste EH sans bruit. Les opérations d'addition et de multiplication ne génèrent aucun bruit. La multiplication est très rapide et se fait en moins d'une milliseconde. La sécurité du cryptosystème est basée sur la difficulté de résoudre un système d'équations multi-variées dans un anneau non commutatif.
On peut décrire notre cryptosystème comme suit :
Génération de clé :
-Bob génère aléatoirement deux grands nombres premiers p et q.
-puis, il calcule n = 2. p. q.
dans (***).
-Bob calcule l'inverse de K, qui sera noté K- , comme il est décrit dans (**).
-la clé secrète est (K, K-1).
Chiffrement :
Soit σ 6 Z/2Z = {0,1} un message clair. Pour chiffrer σ Bob procède comme suit :
-A l'aide de la transformée bitToQuatern , décrite dans (*), Bob transforme σ en un quaternion
aléatoirement.
-Le cryptogramme de
Soit un cryptogramme
Pour déchiffrer C, Bob procède comme suit : -Il calcule
-Puis il prend la première entrée de la matrice
-Enfin il retrouve son message clair en calculant
Addition et multiplication :
Soient deux messages clairs et leurs cryptogrammes
respectivement.
On peut vérifier facilement, grâce à la transformée bitToQuatern, que :
Pour notre cryptosystème, la réduction de quaternions modulo un grand nombre n a l'avantage de donner un cryptosystème sans expansion de bruit. Mais si on utilise un modulo impair, l'entière homomorphie peut être mise en cause. En effet, un modulo impair ne préserve pas, en général, la parité des entiers après un traitement (additions et/ou multiplications) ce qui donne un cryptosystème partiellement homomorphe alors qu'un modulo pair préserve toujours la parité des entiers et donne un schéma entièrement homomorphe.
Version asymétrique :
Notre cryptosystème admet une version asymétrique en lui appliquant la transformation de Rothblum [https://www.iacr.org/archive/tcc2011/65970216/65970216.pdf].
Utilité de l'invention
Le champ d'application de notre cryptosystème est très vaste. Son utilité dans le domaine du cloud Computing est évidente. Parmi les applications de notre cryptosystème on trouve:
1. En général, la délégation de calculs complexes sur des données sensibles à un cloud puissant mais non confiant. En effet, l'externalisation de calcul devient une solution efficace pour ceux qui possèdent des données gigantesques hébergées chez un sous-traitant. Ces données sont confidentielles dans la majorité des cas et nécessitent une manipulation particulière. Grâce aux alternatives de calcul qu'offre notre cryptosystème, les clients peuvent stocker leurs données chiffrées et demander aux sous-traitants de faire des calculs sur ces données à la demande. En particulier ce cryptosystème peut être très utile, en délégation de calcul, dans les deux cas suivants: ❖ Chiffrer des données d'un opérateur bancaire avant leur stockage dans un cloud. Assurément, le secteur bancaire est réputée pour le volume et la vitesse des données qu'il produit, transporte et stocke. La nature des données d'une banque telle que les numéros des comptes bancaires des clients, les sommes d'argent et les transactions effectuées sont d'une grande sensibilité alors que les fournisseurs du cloud ne fournissent aucune garantie sur la protection de la vie privée et sur la confidentialité de ce type de données. Le stockage des masses de données dans un cloud est d'un gain très important pour une banque. La possibilité de faire des traitements sur ces données, sans les divulguer, en un temps pratique en épuisant moins de
ressources est très utile. Notre cryptosystème est une solution adéquate à cette problématique. Il permet, pour une banque, de stocker ses données chiffrées dans un cloud avec la possibilité d'effectuer n'importe quel traitement sans procéder à leur déchiffrement.
❖ Chiffrer des données médicales des patients avant leur stockage dans un cloud. En effet dans un cloud médical, les données des patients tels que l'identifiant biométrique, le numéro de la sécurité sociale, l'âge et l'état de santé sont des données à caractère personnel. L'exploitation de ces données à des fins de recherches médicales et en pharmacovigilance lève la question de confidentialité de ce type de données, avec les règles de déontologie et de respect de la vie privée. Dans ce contexte, on n'est intéressé que par les résultats des traitements qu'on peut effectuer sur ces données. Notre schéma de cryptage permet de faire des traitements sur les données médicales et fournir les résultats demandés tout en préservant la confidentialité des données et la vie privée des patients.
Le retrait d'information privé : En cryptographie, le retrait d'informations privé (RIP) est un protocole qui permet à un utilisateur de récupérer un élément d'une base de données sans révéler au serveur quel élément a été récupéré. Le cryptage homomorphe permet facilement de réaliser tels protocoles. Notre cryptosystème possède la propriété homomorphique qui lui permet de réaliser facilement le protocole RIP.
Le calcul multi -parties : dans les systèmes de calcul multi -parties, plusieurs parties sont intéressées à calculer une fonction commune, sans arriver à divulguer leurs données privées. La fonction qui doit être calculée est publiquement connue alors que les entrées individuelles des différents utilisateurs doivent rester inconnues pour les autres parties du système. Ce problème provient du problème de calcul avec les données chiffrées, d'où l'utilité de l'usage de la cryptographie homomorphe. La version asymétrique de notre cryptosystème permet de mettre en œuvre les calculs multipartis.
Le vote électronique : Le vote électronique est un cas spécial de délégation de calcul à un tiers capable de calculer le résultat des élections sans divulguer les identités des différents candidats. Dans cette situation le cryptage homomorphe permet aux autorités électorales de compter les votes et présenter les résultats définitifs sans passer par le processus du déchiffrement des votes et les compter après. Dans un système de vote basé sur le cryptage homomorphe les électeurs sont autorisés juste à incrémenter un décompte chiffré par 1 (indiquant un vote pour le candidat) où 0 (indiquant le cas du non vote). Lors des élections où chaque électeur vote pour un des candidats parmi i candidats, les électeurs modifient les pointages cryptés en ajoutant un vecteur i bits, où exactement une entrée est 1 et le reste sont tous des 0. Et ils sont incapables de modifier les compteurs de toute autre manière. La version asymétrique de notre cryptosystème permet de mettre en œuvre un système de vote électronique sécurisé.
Claims
Revendications
Une méthode de chiffrement symétrique probabiliste entièrement homomorphe et rapide dont l'espace des clairs est {0, 1 } muni des opérations XOR et AND alors que les cryptogrammes sont des matrices de quaternions de Lipschitz modulo un grand nombre entier naturel pair n caractérisée en ce que dans un mode de réalisation les messages en clair sont codés par une transformée homomorphe inversible bitToQuatern entre (Z 2Z,XOR,AND) et (Η(Ζ4ιΖ),+,x), ladite transformée permet de conserver les deux opérations de XOR et AND sur les bits et de les remplacer par les opérations d'addition et de multiplication sur les quaternions de Lipschitz modulaires H(Z4iZ), pour coder un bit σ par un quaternion de Lipschitz modulaire on procède comme suit :
-Choisir aléatoirement un entier
-Choisir aléatoirement un entier
-Choisir aléatoirement deux entiers
-On a bitTo
Ladite transformée se réalise, autrement, par toute permutation du triplet (21,p,q) et garde les mêmes propriétés d'homomorphie.
La méthode selon la revendication (1) se caractérise en ce que dans un mode de réalisation la transformée inverse quaternToBit permettant de retrouver un bit σ, randomisé à partir de la transformée bitToQuatern ou résultat d'un traitement (additions et/ou multiplications) de plusieurs bits randomisés à partir de la transformée bitToQuatern , la transformée inverse est calculée comme suit : o=quaternToBit(q)=Re(q)[2], Où q est un quaternion de Lipschitz obtenu selon la revendication (1) et Re est sa partie réelle.
La méthode selon la revendication (1) se caractérise en ce que dans un mode de réalisation, le chiffrement d'un binaire (0 où 1) qui représente le message en clair se fait en la transformation de ce binaire en un quaternion en utilisant la transformée bitToQuatern, le résultat de cette transformation est inséré à la première entrée d'une matrice quatemionique triangulaire supérieure d'ordre deux dont les deux entrées restantes sont des quaternions choisies aléatoirement (c'est la matrice M), la continuation du chiffrement se fait en multipliant à gauche la matrice M par une matrice
quatemionique inversible K choisie aléatoirement et par son inverse Κ^(-1) à droite (les matrices K et Κ^(-1) sont utilisées comme clé secrète pour le chiffrement et le déchiffrement). La matrice résultante du produit ΚΜΚ^(-1) constitue le message chiffré.
La méthode selon les revendications précédentes se caractérise en ce que dans un mode de réalisation, le déchiffrement d'un cryptogramme C (qui est une matrice quatemionique) se fait en multipliant la matrice C par la matrice Κ^(-1) à gauche et par la matrice K à droite, la continuation du déchiffrement se fait en prenant la première entrée de la matrice résultante du produit Κ^(-1) CK et en lui appliquant la transformé inverse selon la revendication (2), le résultat de ces opérations constitue le message clair après déchiffrement.
La méthode selon les revendications précédente se caractérise en ce que dans un mode de réalisation la méthode de multiplication des cryptogrammes prend en entrée deux matrices C_l et C_2 cryptogrammes de deux messages clairs σ_1 et σ_2 selon la revendication (3), fait une multiplication matricielle C_l [ .C] _2 et donne en sortie une matrice quatemionique cryptogramme du clair
σ=σ_1.σ_2, ledit produit matriciel peut se faire dans n'importe quel ordre (c'est-à-dire on peut calculer C_l [ .C] _2 comme on peut calculer C_2 [ .C] _1).
La méthode selon les revendications précédente se caractérise en ce que dans un mode de réalisation la méthode d'addition des cryptogrammes prend en entrée deux matrices C_l et C_2 cryptogrammes de deux messages clairs σ_1 et σ_2 selon la revendication (3), fait une addition matricielle C_l [+C] _2 et donne en sortie une matrice quaternionique cryptogramme du clair o=(o_l+o_2)mod 2.
Applications Claiming Priority (2)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| MA39664 | 2016-12-30 | ||
| MA39664A MA39664B1 (fr) | 2016-12-30 | 2016-12-30 | Une méthode pratique de cryptage entièrement homomorphe et vérifiable. |
Publications (1)
| Publication Number | Publication Date |
|---|---|
| WO2018124869A1 true WO2018124869A1 (fr) | 2018-07-05 |
Family
ID=61972184
Family Applications (1)
| Application Number | Title | Priority Date | Filing Date |
|---|---|---|---|
| PCT/MA2018/050005 Ceased WO2018124869A1 (fr) | 2016-12-30 | 2018-02-28 | Un efficace cryptosysteme entierement homomorphe a base des quaternions. |
Country Status (2)
| Country | Link |
|---|---|
| MA (1) | MA39664B1 (fr) |
| WO (1) | WO2018124869A1 (fr) |
Cited By (6)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| CN109164702A (zh) * | 2018-07-26 | 2019-01-08 | 西北工业大学 | 一种自适应多变量广义超螺旋方法 |
| CN110418028A (zh) * | 2019-06-21 | 2019-11-05 | 首都师范大学 | 基于级联变换的图像加密方法及装置 |
| CN110991620A (zh) * | 2019-12-11 | 2020-04-10 | 上海交通大学 | 一种具有隐私保护作用的新型神经网络模块 |
| CN111064558A (zh) * | 2020-01-09 | 2020-04-24 | 浙江理工大学 | 一种基于云计算的同态加密矩阵连乘安全外包方法 |
| US11032061B2 (en) * | 2018-04-27 | 2021-06-08 | Microsoft Technology Licensing, Llc | Enabling constant plaintext space in bootstrapping in fully homomorphic encryption |
| EP3840282A1 (fr) * | 2019-12-20 | 2021-06-23 | IDEMIA France | Procédé de traitement cryptographique, dispositif électronique et programme d'ordinateur associés |
Citations (2)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| US20110110525A1 (en) | 2009-11-10 | 2011-05-12 | International Business Machines Corporation | Fully homomorphic encryption method based on a bootstrappable encryption scheme, computer program and apparatus |
| WO2014016795A2 (fr) | 2012-07-26 | 2014-01-30 | Nds Limited | Procédé et système de randomisation homomorphe d'une entrée |
-
2016
- 2016-12-30 MA MA39664A patent/MA39664B1/fr unknown
-
2018
- 2018-02-28 WO PCT/MA2018/050005 patent/WO2018124869A1/fr not_active Ceased
Patent Citations (2)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| US20110110525A1 (en) | 2009-11-10 | 2011-05-12 | International Business Machines Corporation | Fully homomorphic encryption method based on a bootstrappable encryption scheme, computer program and apparatus |
| WO2014016795A2 (fr) | 2012-07-26 | 2014-01-30 | Nds Limited | Procédé et système de randomisation homomorphe d'une entrée |
Non-Patent Citations (4)
| Title |
|---|
| EL-YAHYAOUI AHMED ET AL: "A new cryptographic method for cloud computing", 2017 3RD INTERNATIONAL CONFERENCE OF CLOUD COMPUTING TECHNOLOGIES AND APPLICATIONS (CLOUDTECH), IEEE, 24 October 2017 (2017-10-24), pages 1 - 8, XP033318263, DOI: 10.1109/CLOUDTECH.2017.8284705 * |
| MASAHIRO YAGISAWA: "Fully Homomorphic Encryption without bootstrapping", INTERNATIONAL ASSOCIATION FOR CRYPTOLOGIC RESEARCH,, vol. 20150621:055416, 21 June 2015 (2015-06-21), pages 1 - 40, XP061018739 * |
| R. RIVEST; L. ADLEMAN; M. DERTOUZOS: "on data banks and privacy homomorphisms", FOUNDA IONS OF SECURE COMPUTATION, 1978, pages 169 - 180 |
| YONGGE WANG: "Octonion Algebra and Noise-Free Fully Homomorphic Encryption (FHE) Schemes", INTERNATIONAL ASSOCIATION FOR CRYPTOLOGIC RESEARCH,, vol. 20160128:165429, 28 January 2016 (2016-01-28), pages 1 - 40, XP061020053 * |
Cited By (10)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| US11032061B2 (en) * | 2018-04-27 | 2021-06-08 | Microsoft Technology Licensing, Llc | Enabling constant plaintext space in bootstrapping in fully homomorphic encryption |
| CN109164702A (zh) * | 2018-07-26 | 2019-01-08 | 西北工业大学 | 一种自适应多变量广义超螺旋方法 |
| CN109164702B (zh) * | 2018-07-26 | 2021-09-14 | 西北工业大学 | 一种自适应多变量广义超螺旋方法 |
| CN110418028A (zh) * | 2019-06-21 | 2019-11-05 | 首都师范大学 | 基于级联变换的图像加密方法及装置 |
| CN110418028B (zh) * | 2019-06-21 | 2021-03-30 | 首都师范大学 | 基于级联变换的图像加密方法及装置 |
| CN110991620A (zh) * | 2019-12-11 | 2020-04-10 | 上海交通大学 | 一种具有隐私保护作用的新型神经网络模块 |
| EP3840282A1 (fr) * | 2019-12-20 | 2021-06-23 | IDEMIA France | Procédé de traitement cryptographique, dispositif électronique et programme d'ordinateur associés |
| FR3105684A1 (fr) * | 2019-12-20 | 2021-06-25 | Idemia France | Procede de traitement cryptographique, dispositif electronique et programme d'ordinateur associes |
| CN111064558A (zh) * | 2020-01-09 | 2020-04-24 | 浙江理工大学 | 一种基于云计算的同态加密矩阵连乘安全外包方法 |
| CN111064558B (zh) * | 2020-01-09 | 2023-04-07 | 浙江理工大学 | 一种基于云计算的同态加密矩阵连乘安全外包方法 |
Also Published As
| Publication number | Publication date |
|---|---|
| MA39664B1 (fr) | 2018-09-28 |
Similar Documents
| Publication | Publication Date | Title |
|---|---|---|
| WO2018124869A1 (fr) | Un efficace cryptosysteme entierement homomorphe a base des quaternions. | |
| WO2018210895A1 (fr) | Agrégation de flux privé sécurisé post-quantique | |
| EP2415199B1 (fr) | Procede pour effectuer une tache cryptographique dans un composant electronique | |
| EP2158720B1 (fr) | Procédé d'authentification utilisant un décodage de code correcteur d'erreurs à partir d'une matrice publique | |
| EP3861670A1 (fr) | Methode de transchiffrement a faible latence de calcul appliquee au chiffrement homomorphe | |
| WO2012152607A1 (fr) | Dispositif et procede de generation de cles a securite renforcee pour algorithme de chiffrement pleinement homomorphique | |
| Hart et al. | A practical cryptanalysis of WalnutDSA TM | |
| Sharma | Fully homomorphic encryption scheme with symmetric keys | |
| Mittal et al. | Research perspectives on fully homomorphic encryption models for cloud sector | |
| EP2940922B1 (fr) | Cryptosystèmes symétriques avec clé publique basé sur l'utilisation du groupe symétrique | |
| Agrawal et al. | On architecting fully homomorphic encryption-based computing systems | |
| WO2018084691A2 (fr) | Un efficace cryptosysteme entierement homomorphe a base des quaternions | |
| EP2983083B1 (fr) | Procede de cryptographie sur courbe elliptique comprenant une detection d'erreur | |
| Hoffstein | Integer factorization and RSA | |
| WO2013024230A2 (fr) | Dispositif et procédé de compression de clés publiques pour algorithme de chiffrement pleinement homomorphique | |
| EP1438804B1 (fr) | Procede cryptographique a cle publique base sur les groupes de tresses | |
| Mittal et al. | Preserving privacy in clouds using fully homomorphic encryption | |
| Rabah | Digital cryptoeconomics powered by digital cryptocurrency | |
| EP2936302B1 (fr) | Generateur de sequences chaotiques | |
| FR2888690A1 (fr) | Procede cryptographique pour la mise en oeuvre securisee d'une exponentiation et composant associe | |
| EP2274869B1 (fr) | Protection en boîte-blanche d'algorithmes cryptographiques comprenant le calcul d'une forme quadratique | |
| FR3135854A1 (fr) | Fourniture sécurisée de clefs pour un cryptage totalement homomorphe | |
| Barelli | On the security of short McEliece keys from algebraic and algebraic geometry codes with automorphisms | |
| Barelli | Étude de la sécurité de certaines clés compactes pour le schéma de McEliece utilisant des codes géométriques | |
| Assouline | Computing with private information: Techniques from Cryptology |
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: 18717718 Country of ref document: EP Kind code of ref document: A1 |
|
| NENP | Non-entry into the national phase |
Ref country code: DE |
|
| 122 | Ep: pct application non-entry in european phase |
Ref document number: 18717718 Country of ref document: EP Kind code of ref document: A1 |