Les réseaux euclidiens - Historique des versions

Bruhl : /* Application en cryptologie */

2018-11-26T00:25:39Z

Application en cryptologie

← Version précédente		Version du 26 novembre 2018 à 00:25
Ligne 129 :		Ligne 129 :

	[[Fichier:Réseau_euclidien_chiffrage.png\|left\|700px\|Chiffrage]]		[[Fichier:Réseau_euclidien_chiffrage.png\|left\|700px\|Chiffrage]]































	=== Le déchiffrement===		=== Le déchiffrement===

Bruhl : /* Conclusion */

2018-11-26T00:25:04Z

Conclusion

← Version précédente		Version du 26 novembre 2018 à 00:25
Ligne 260 :		Ligne 260 :
	En effet, alors que la taille des clés de chiffrement de la méthode RSA se situe entre 128 à 512 octets, celle des clés du cryptage par réseaux euclidiens représente plusieurs méga-octets et reste donc beaucoup trop lourde aujourd'hui pour être viable.		En effet, alors que la taille des clés de chiffrement de la méthode RSA se situe entre 128 à 512 octets, celle des clés du cryptage par réseaux euclidiens représente plusieurs méga-octets et reste donc beaucoup trop lourde aujourd'hui pour être viable.

	De plus, il faut savoir que l'addition et la multiplication homomorphe sont 1000 fois plus ~~longs~~ que les opérations classiques.		De plus, il faut savoir que l'addition et la multiplication homomorphe sont 1000 fois plus longues que les opérations classiques.

	Ces deux inconvénients, bien qu'ils paraissent insignifiant, constituent aujourd'hui le problème majeur du chiffrement. De nombreux chercheurs dont Craig Gentry, le premier à avoir écrit une thèse sur cette méthode de chiffrement en 2009, travaille sur la réduction de la taille des clés ainsi que sur la performance pour effectuer les opérations homomorphes.		Ces deux inconvénients, bien qu'ils paraissent insignifiant, constituent aujourd'hui le problème majeur du chiffrement. De nombreux chercheurs dont Craig Gentry, le premier à avoir écrit une thèse sur cette méthode de chiffrement en 2009, travaille sur la réduction de la taille des clés ainsi que sur la performance pour effectuer les opérations homomorphes.

Bruhl : /* Chiffrement homomorphe */

2018-11-26T00:18:39Z

Chiffrement homomorphe

← Version précédente		Version du 26 novembre 2018 à 00:18
Ligne 225 :		Ligne 225 :

	Le chiffrement homomorphe permet d'effectuer une ou plusieurs opérations sans la nécessité d'accéder aux données sensibles en les déchiffrant.		Le chiffrement homomorphe permet d'effectuer une ou plusieurs opérations sans la nécessité d'accéder aux données sensibles en les déchiffrant.
	Pour toutes opérations Op et pour tous messages m1 et m2, effectuer l'opération sur les messages cryptés par la méthode C et ensuite ~~déchiffrés~~ par D est équivalent au résultat de l'opération sur les deux messages clairs :		Pour toutes opérations Op et pour tous messages m1 et m2, effectuer l'opération sur les messages cryptés par la méthode C et ensuite déchiffés par D est équivalent au résultat de l'opération sur les deux messages clairs :
	<br/>		<br/>
	<br/>		<br/>
Ligne 231 :		Ligne 231 :
	<br/>		<br/>
	<br/>		<br/>
	Prenons l'exemple d'Alice. Alice souhaite pouvoir effectuer des opérations sur deux données sensibles mais elle ne possède pas la puissance de calcul nécessaire pour l'effectuer. Elle souhaite donc demander à un organisme tiers de procéder aux calculs sur ses données. Cependant, les données à traiter sont sensibles et Alice ne fait pas confiance en cet organisme. Elle va donc ~~une~~ utiliser un chiffrement homomorphe et envoyer des données ~~chiffrés~~ à l'organisme qui pourra ainsi calculer et renvoyer le résultat, encore chiffré, à Alice. Alice pourra alors déchiffrer le message pour obtenir le résultat de l'opération sur ses données sensibles grâce aux propriétés du chiffrement homomorphe.		Prenons l'exemple d'Alice. Alice souhaite pouvoir effectuer des opérations sur deux données sensibles mais elle ne possède pas la puissance de calcul nécessaire pour l'effectuer. Elle souhaite donc demander à un organisme tiers de procéder aux calculs sur ses données. Cependant, les données à traiter sont sensibles et Alice ne fait pas confiance en cet organisme. Elle va donc utiliser un chiffrement homomorphe et envoyer des données chiffrées à l'organisme qui pourra ainsi calculer et renvoyer le résultat, encore chiffré, à Alice. Alice pourra alors déchiffrer le message pour obtenir le résultat de l'opération sur ses données sensibles grâce aux propriétés du chiffrement homomorphe.

	[[File:alice.png\|center\|800px\|Exemple Alice]]		[[File:alice.png\|center\|800px\|Exemple Alice]]

Bruhl : /* Chiffrement homomorphe */

2018-11-26T00:14:16Z

Chiffrement homomorphe

← Version précédente		Version du 26 novembre 2018 à 00:14
Ligne 225 :		Ligne 225 :

	Le chiffrement homomorphe permet d'effectuer une ou plusieurs opérations sans la nécessité d'accéder aux données sensibles en les déchiffrant.		Le chiffrement homomorphe permet d'effectuer une ou plusieurs opérations sans la nécessité d'accéder aux données sensibles en les déchiffrant.
	Pour ~~toute~~ ~~opération~~ Op et pour ~~tout~~ ~~message~~ m1 et m2, effectuer l'opération sur les messages cryptés par la méthode C et ensuite déchiffrés par D est équivalent au résultat de l'opération sur les deux messages clairs :		Pour toutes opérations Op et pour tous messages m1 et m2, effectuer l'opération sur les messages cryptés par la méthode C et ensuite déchiffrés par D est équivalent au résultat de l'opération sur les deux messages clairs :
	<br/>		<br/>
	<br/>		<br/>

Bruhl : /* Chiffrement homomorphe */

2018-11-26T00:12:51Z

Chiffrement homomorphe

← Version précédente		Version du 26 novembre 2018 à 00:12
Ligne 224 :		Ligne 224 :
	== Chiffrement homomorphe==		== Chiffrement homomorphe==

	Le chiffrement homomorphe permet d'effectuer une ou plusieurs opérations sans ~~nécessité~~ de d'accéder aux données sensibles en les déchiffrant.		Le chiffrement homomorphe permet d'effectuer une ou plusieurs opérations sans la nécessité d'accéder aux données sensibles en les déchiffrant.
	Pour toute opération Op et pour tout message m1 et m2, effectuer l'opération sur les messages cryptés par la méthode C et ensuite déchiffrés par D est équivalent au résultat de l'opération sur les deux messages clairs :		Pour toute opération Op et pour tout message m1 et m2, effectuer l'opération sur les messages cryptés par la méthode C et ensuite déchiffrés par D est équivalent au résultat de l'opération sur les deux messages clairs :
	<br/>		<br/>

Bruhl : /* Robustesse */

2018-11-26T00:09:15Z

Robustesse

← Version précédente		Version du 26 novembre 2018 à 00:09
Ligne 204 :		Ligne 204 :
	== Robustesse ==		== Robustesse ==

	La cryptologie sur les réseaux euclidiens ~~sont~~ basé sur des problèmes ''NP-~~complet~~''. Ce sont des problèmes impossible à résoudre pour les calculateurs classiques ou quantiques de manière efficace.		La cryptologie sur les réseaux euclidiens est basé sur des problèmes ''NP-complets''. Ce sont des problèmes impossible à résoudre pour les calculateurs classiques ou quantiques de manière efficace.
	De plus, se baser sur des problèmes NP-~~Complet~~ est d'autant plus intéressant puisqu'il est sûr et certain qu'aucun algorithme quantique ne pourra en venir à bout de manière efficace.		De plus, se baser sur des problèmes NP-Complets est d'autant plus intéressant puisqu'il est sûr et certain qu'aucun algorithme quantique ne pourra en venir à bout de manière efficace.
	En effet, on sait que les algorithmes ~~quantique~~ sont limités à la classe [https://fr.wikipedia.org/wiki/BQP BQP] et résoudre ce type de problème ne permet pas de résoudre les ~~problème~~ NP-~~complet~~.		En effet, on sait que les algorithmes quantiques sont limités à la classe [https://fr.wikipedia.org/wiki/BQP BQP] et résoudre ce type de problème ne permet pas de résoudre les problèmes NP-complets.

	Il y a plusieurs problèmes algorithmiques dans les réseaux :		Il y a plusieurs problèmes algorithmiques dans les réseaux :
Ligne 215 :		Ligne 215 :
	Pour réduire un réseau euclidien de dimension 2, il existe une méthode simple et efficace très similaire à l'algorithme d'Euclide pour calculer le PGCD de deux entiers. Comme avec l'algorithme euclidien, la méthode est itérative, à chaque étape, le plus grand des deux vecteurs est réduit en ajoutant ou en soustrayant un multiple entier du plus petit vecteur.		Pour réduire un réseau euclidien de dimension 2, il existe une méthode simple et efficace très similaire à l'algorithme d'Euclide pour calculer le PGCD de deux entiers. Comme avec l'algorithme euclidien, la méthode est itérative, à chaque étape, le plus grand des deux vecteurs est réduit en ajoutant ou en soustrayant un multiple entier du plus petit vecteur.

	Cependant le temps croît de manière exponentielle quand le nombre de ~~dimension~~ augmente. A partir de 80 dimensions, un effort considérable est déjà requis. Les records sur clusters atteignent avec ~~difficulté~~, 130 dimensions. On considère qu'avec 200 ou 250 dimensions les réseaux euclidiens sont assez ~~robuste~~ puisque l'on estime le temps de calculs en milliards d'années.		Cependant le temps croît de manière exponentielle quand le nombre de dimensions augmente. A partir de 80 dimensions, un effort considérable est déjà requis. Les records sur clusters atteignent avec difficultés, 130 dimensions. On considère qu'avec 200 ou 250 dimensions les réseaux euclidiens sont assez robustes puisque l'on estime le temps de calculs en milliards d'années.

	== Un jeu sur les reseaux euclidiens : Cryptris==		== Un jeu sur les reseaux euclidiens : Cryptris==

Bruhl : /* Robustesse */

2018-11-25T23:58:24Z

Robustesse

← Version précédente		Version du 25 novembre 2018 à 23:58
Ligne 203 :		Ligne 203 :

	== Robustesse ==		== Robustesse ==

	Bien entendu un réseau euclidien en dimension 2, n'est pas assez robuste, cependant le temps pour réduire un réseau euclidien, c'est à dire trouver une bonne base d'un réseau, croît de manière exponentielle, plus le nombre de dimensions augmente. A partir de 80 dimensions, il faut déjà mettre un certain effort pour arriver à ses fins. Les records sur clusters atteignent non sans mal, 130 dimensions actuellement. On considère qu'avec 200 ou 250 dimensions les réseaux euclidiens sont assez robuste puisque l'on estime le temps de calculs en milliards d'années pour déchiffrer le message chiffré.

	La cryptologie sur les réseaux euclidiens sont basé sur des problèmes ''NP-complet''. Ce sont des problèmes impossible à résoudre pour les calculateurs classiques ou quantiques de manière efficace.		La cryptologie sur les réseaux euclidiens sont basé sur des problèmes ''NP-complet''. Ce sont des problèmes impossible à résoudre pour les calculateurs classiques ou quantiques de manière efficace.

Bruhl : /* Robustesse */

2018-11-25T23:49:43Z

Robustesse

← Version précédente		Version du 25 novembre 2018 à 23:49
Ligne 204 :		Ligne 204 :
	== Robustesse ==		== Robustesse ==

	Bien entendu un réseau euclidien en dimension 2, n'est pas assez robuste, cependant le temps pour réduire un réseau euclidien, c'est à dire trouver une bonne base d'un réseau, croît de manière exponentielle, plus le nombre de ~~dimension~~ augmente. A partir de 80 dimensions, il faut déjà mettre un certain effort pour arriver à ses fins. Les records sur clusters atteignent non sans mal, 130 dimensions actuellement. On considère qu'avec 200 ou 250 dimensions les réseaux euclidiens sont assez robuste puisque l'on estime le temps de calculs en milliards d'années pour déchiffrer le message chiffré.		Bien entendu un réseau euclidien en dimension 2, n'est pas assez robuste, cependant le temps pour réduire un réseau euclidien, c'est à dire trouver une bonne base d'un réseau, croît de manière exponentielle, plus le nombre de dimensions augmente. A partir de 80 dimensions, il faut déjà mettre un certain effort pour arriver à ses fins. Les records sur clusters atteignent non sans mal, 130 dimensions actuellement. On considère qu'avec 200 ou 250 dimensions les réseaux euclidiens sont assez robuste puisque l'on estime le temps de calculs en milliards d'années pour déchiffrer le message chiffré.

	La cryptologie sur les réseaux euclidiens sont basé sur des problèmes ''NP-complet''. Ce sont des problèmes impossible à résoudre pour les calculateurs classiques ou quantiques de manière efficace.		La cryptologie sur les réseaux euclidiens sont basé sur des problèmes ''NP-complet''. Ce sont des problèmes impossible à résoudre pour les calculateurs classiques ou quantiques de manière efficace.

Bruhl : /* Le déchiffrement */

2018-11-25T23:29:24Z

Le déchiffrement

← Version précédente		Version du 25 novembre 2018 à 23:29
Ligne 132 :		Ligne 132 :
	=== Le déchiffrement===		=== Le déchiffrement===
	Pour le déchiffrement, il suffit de retrouver le point représenté par le vecteur d grâce à notre clé privée. Pour cela on utilise l'algorithme de Babai qui va paver l'espace avec au centre de chaque pavé un point du réseau. Et ensuite permettre de retrouver le point du pavé (le point du réseau représenté par le vecteur d) où se trouve notre vecteur message chiffré.		Pour le déchiffrement, il suffit de retrouver le point représenté par le vecteur d grâce à notre clé privée. Pour cela on utilise l'algorithme de Babai qui va paver l'espace avec au centre de chaque pavé un point du réseau. Et ensuite permettre de retrouver le point du pavé (le point du réseau représenté par le vecteur d) où se trouve notre vecteur message chiffré.
	Un fois le vecteur d retrouvé on le soustrait au vecteur message-chiffré.		Un fois le vecteur d retrouvé on le soustrait au vecteur message chiffré.

	def dechiffre(Secret, m_chiffré):		def dechiffre(Secret, m_chiffré):
Ligne 138 :		Ligne 138 :
	m = m_chiffré - d		m = m_chiffré - d
	return m		return m


	=== Algorithme de Babai===		=== Algorithme de Babai===

Bruhl : /* Le chiffrement */

2018-11-25T23:27:05Z

Le chiffrement

← Version précédente		Version du 25 novembre 2018 à 23:27
Ligne 124 :		Ligne 124 :
	<br/>		<br/>
	Message chiffré :		Message chiffré :
	<math>\begin{pmatrix}14 \\ 6\end{pmatrix}</math>.		<math>\begin{pmatrix}13 \\ 7\end{pmatrix}</math>.
	<br/>		<br/>
	<br/>		<br/>

Les réseaux euclidiens - Historique des versions

Bruhl : /* Application en cryptologie */

Bruhl : /* Conclusion */

Bruhl : /* Chiffrement homomorphe */

Bruhl : /* Chiffrement homomorphe */

Bruhl : /* Chiffrement homomorphe */

Bruhl : /* Robustesse */

Bruhl : /* Robustesse */

Bruhl : /* Robustesse */

Bruhl : /* Le déchiffrement */

Bruhl : /* Le chiffrement */

Bruhl : /* Application en cryptologie */

Bruhl : /* Conclusion */

Bruhl : /* Chiffrement homomorphe */

Bruhl : /* Chiffrement homomorphe */

Bruhl : /* Chiffrement homomorphe */

Bruhl : /* Robustesse */

Bruhl : /* Robustesse */

Bruhl : /* Robustesse */

Bruhl : /* Le déchiffrement */

Bruhl : /* Le chiffrement */