PC & Mobile

Quand l'apprentissage automatique rencontre la cryptographie

Quand l'apprentissage automatique rencontre la cryptographie


Imaginez que les clés secrètes de R et T sont en fait les mêmes s= (1,0,1,0). Maintenant R envoie un vecteur binaire aléatoire une (par exemple. une= (1,0,1,1)) à T et attend T pour y répondre le produit scalaire b=, lequel est

dans cet exemple. Nous appelons cela une une défi. Rappelez-vous, nous traitons ici de l'arithmétique des bits, donc le «+» est, en fait, un XOR. La multiplication est la même que dans les nombres réels. Ou pour les mathématiciens: on calcule dans le champ GF (2) ou 𝔽₂, le champ à 2 éléments.

XOR est comme l'addition normale pour les entiers, juste que 1 + 1 = 0.

R peut calculer le produit scalaire lui-même (il sait une et s) et chèques TRéponse de. Si TEst la même, R peut être un peu plus confiant que T a en effet la même clé secrète. Pour augmenter la confiance, ce jeu est répété plusieurs fois.

Par exemple, si T n'a pas la bonne clé, il serait très peu probable qu'elle réussisse après un nombre suffisant de tours, car une seule réponse ne serait correcte qu'avec une probabilité de 0,5. Par conséquent, après 10 tours, par exemple, les chances de réussite de l'authentification ne sont que de 1/1024, moins de 0,1%.

Cela semble beaucoup mieux, non? T ne révèle pas son secret en une seule fois maintenant, au lieu de cela, il donne des informations à R en répondant aux défis. Mais malheureusement, cela est également complètement précaire. Un attaquant pourrait encore noter la communication complète entre R et T puis résoudre facilement un système d'équations linéaires pour récupérer s. Cela se fait de la manière suivante: Imaginez que l'attaquant a écrit ce qui suit pour les paires défi / réponse:

L'attaquant sait aussi que

UNE est la matrice contenant le aᵢ'S sous forme de lignes et b le bᵢ’S. Dans notre cas:

Le système d'équations linéaires que l'attaquant doit résoudre.

Donc, résoudre ce système pour s donne le secret. Cela peut également être fait facilement via l'élimination gaussienne si s est beaucoup plus grande, c'est-à-dire 1024 bits de long. La solution est
s= (1,0,1,0) au fait. :)

Il y en a un très petit mais ajustement extrêmement important pour sécuriser cela contre notre attaquant: T ajoute juste un peu de bruit Bernoulli aléatoire à ses réponses. Au lieu d'envoyer retour à R, il lance une pièce e qui est 1 avec probabilité p et 0 sinon et renvoie + e au lecteur. En d'autres termes, avec une probabilité de 1 à 1p le tag envoie retour à R et avec probabilité p il retourne le bit de réponse de 0 à 1 ou de 1 à 0. Nous supposons que p <0,5.

Cela ne ne pas empêcher l'attaquant de renifler la communication entre R et T et prendre des notes, bien sûr, mais ils doivent résoudre le problème suivant maintenant:

Cette notation indique que chaque équation du système d'équations n'est correcte qu'avec la probabilité 1-p. Plus formellement, vous pouvez l'écrire sous la forme Comme + e = b, e est le vecteur de bruit avec chaque composante (indépendamment) étant 1 avec probabilité p et 0 avec probabilité 1-p.

Ainsi, l'attaquant doit résoudre un système d'équations bruyant sur GF (2). Pour un taux d'erreur constant p, ce problème - le problème de la parité d'apprentissage avec le bruit (LPN) - est conjecturé comme étant impossible à résoudre pour une longueur suffisamment grande de la clé secrète. Cela est également vrai si l'attaquant peut obtenir arbitrairement de nombreuses équations.

Même avec ces erreurs ajoutées, R peut faire son travail de déterminer si T sait s ou pas. Si T a le bon s, une fraction d'environ 1 à 1p les réponses seront correctes. Cela signifie que si p= 0,25, le protocole HB fonctionne pendant 1000 itérations, T devrait donner environ 750 réponses correctes.

Si T n'a pas le bon s, il donnera une fraction d'environ 0,5 bonnes réponses, c'est-à-dire 500 sur 1000 exécution du protocole des tours. Ceci permet R décider si T a le bon secret ou non et ce protocole a toujours du sens pour notre cas d'utilisation.

Résolution du LPN via l'apprentissage automatique

Passons maintenant à la partie amusante. Nous avons établi que la résolution du problème LPN signifie, étant donné une matrice binaire aléatoire UNE et un vecteur binaire b = As + e, récupérer s.

L'observation importante: Nous pouvons traiter chaque ligne aᵢ de matrice UNE maintenant comme échantillon et la valeur correspondante bᵢ =+ eᵢ dans le vecteur b comme étiquette.

En utilisant un exemple avec une longueur secrète de 4 et six communications capturées, nous pouvons voir que chaque ligne de la matrice A se compose de quatre caractéristiques et l'entrée en b est l'étiquette correspondante. Notre jeu de données a une taille de six.

Comme dans les jeux de données normaux utilisés dans l'apprentissage automatique, une étiquette bᵢ ressemble en fait au produit scalaire du vecteur caractéristique aᵢ et un vecteur secret fixe s (une vérité fondamentale), mais avec un terme d'erreur ajouté. Mais comment pouvons-nous obtenir le secret s quand on lance un algorithme d'apprentissage automatique pour prédire les étiquettes dessus?

Eh bien, si nous pouvions apprendre le problème raisonnablement bien, nous pourrions générer de bonnes prédictions pour les étiquettes (les produits scalaires; la vérité du sol) pour chaque vecteur caractéristique aᵢ nous aimons. Si on jette le vecteur une= (1,0,0,0), nous recevrions alors une bonne estimation de

le premier morceau de s! Faites de même avec les vecteurs (0, 1, 0, 0), (0, 0, 1, 0) et
(0, 0, 0, 1) et nous avons tous les bits de la clé secrète.

Ainsi, nous pouvons résoudre le problème LPN en utilisant l'apprentissage automatique.

Remarques

Le problème LPN est un problème très polyvalent que vous pouvez également utiliser pour créer cryptage, cryptage basé sur l'identité, authentification des utilisateurs, transfert inconscient, codes d'authentification des messages, et probablement plus de constructions. De plus, contrairement au problème de factorisation, le problème LPN ne peut pas être facilement résolu en utilisant des ordinateurs quantiques. Associé à sa légèreté, il est un bon candidat pour la construction d'algorithmes sécurisés post-quantiques. Donc, pas de soucis, si RSA, qui est basé sur la factorisation de grands nombres, meurt en présence d'ordinateurs quantiques. ;)

Pour plus d'informations et une meilleure définition mathématique du problème LPN, veuillez vous référer à ma thèse [2].

Définissons d'abord un LPN oracle, c'est à dire. une classe que nous pouvons nourrir avec une clé secrète et un niveau d'erreur p lors de l'instanciation, ce qui nous donne autant d'échantillons que nous voulons.

Cela peut facilement être fait en utilisant le code suivant:

importation engourdi comme np
classe LPNOracle:
def __init __ (auto, secret, taux d'erreur):
self.secret = secret
self.dimension = len (secret)
self.error_rate = error_rate
def échantillon (self, n_amount):
# Créez une matrice aléatoire.
A = np.random.randint (0, 2, taille = (n_amount, self.dimension))
# Ajouter des erreurs Bernoulli.
e = np.random.binomial (1, self.error_rate, n_amount)
# Calculez les étiquettes.
b = np.mod (A @ self.secret + e, 2)
revenir Un B

Nous pouvons maintenant instancier cet oracle avec un secret aléatoire de longueur 16 et p= 0,125.

p = 0,125
dim = 16
s = np.random.randint (0, 2, dim)
lpn = LPNOracle (s, p)

Nous pouvons maintenant échantillonner lpn :

lpn.sample (3)ma sortie: (tableau ([[1, 1, 1, 1, 0, 0, 0, 0, 1, 0, 1, 0, 0, 1, 1, 1],
[1, 1, 0, 0, 1, 0, 0, 1, 1, 0, 0, 0, 1, 0, 1, 0],
[1, 0, 1, 1, 0, 0, 1, 0, 1, 1, 1, 0, 1, 0, 0, 0]]),
tableau ([1, 1, 1], dtype = int32))

Ici, nous avons échantillonné 3 points de données. Maintenant, essayons de trouver s à l'aide d'un arbre de décision. Pourquoi? Tout simplement parce que c'est rapide et la régression logistique et Bernoulli Naive Bayes n'a pas fonctionné pour moi.

de sklearn.tree importation DecisionTreeClassifierdt = DecisionTreeClassifier ()# Obtenez 100000 échantillons.
A, b = lpn.sample (100000)
# Ajustez l'arbre.
dt.fit (A, b)
# Prédire tous les vecteurs d'unités canoniques (1, 0, 0, ..., 0), (0, 1, 0, 0, ..., 0), ..., (0, 0, ..., 0 , 1).
s_candidate = dt.predict (np.eye (dim))
# Vérifiez si la solution candidate est correcte.
si np.mod (A @ s_candidate + b, 2) .sum () <14000:
imprimer (s_candidate, s)
autre:
impression(«Mauvais candidat. Réessayer!')

L'algorithme d'apprentissage peut ne pas capturer la vérité du terrain et apprendre une autre fonction. Dans ce cas, le soi-disant Poids de Hamming du vecteur est assez élevé (environ 50000 pour notre vecteur de longueur 100000). Cela correspond au cas où la balise T a la mauvaise clé et peut répondre correctement à environ la moitié des défis. Si s_candidate = s, le poids de Hamming sera d'environ 0,125 * 100000 = 12500.

Avoir un seuil de 14000 dans cet exemple est un bon compromis entre reconnaître le bon secret et ne pas sortir un mauvais candidat comme solution. Vous pouvez trouver comment obtenir ce lien dans [2, page 23].

Nous avons défini le problème LPN et vu comment il se pose en essayant de briser le protocole cryptographique HB. Ensuite, nous avons résolu une petite instance en utilisant un simple arbre de décision.

Mais le voyage commence juste ici: Nous pouvons utiliser d'autres / meilleurs algorithmes (apprentissage en profondeur, n'importe qui?) Ou des astuces intelligentes pour

  • obtenir des taux de réussite plus élevés,
  • en utilisant moins d'échantillons et
  • être capable de résoudre des problèmes avec des dimensions plus élevées.
Afficher plus

SupportIvy

SupportIvy.com : Un lieu pour partager le savoir et mieux comprendre le monde. Meilleure plate-forme de support gratuit pour vous, Documentation &Tutoriels par les experts.

Articles similaires

Laisser un commentaire

Votre adresse de messagerie ne sera pas publiée. Les champs obligatoires sont indiqués avec *

Bouton retour en haut de la page
Fermer