Sécurité polynomiale en cryptographie

Abstract

Dans ce mémoire, nous proposons des protocoles cryptographiques d'échange de clef, de mise en gage, et de transfert équivoque. Un premier protocole de transfert équivoque, primitive cryptographique universelle pour le calcul multi-parties, s'inspire du protocole d'échange de clef par puzzle de Merkle, et améliore les résultats existants. Puis, nous montrons qu'il est possible de construire ces mêmes primitives cryptographiques sans l'hypothèse des fonctions à sens unique, mais avec le problème 3SUM. Ce problème simple ---dans une liste de n entiers, en trouver trois dont la somme a une certaine valeur--- a une borne inférieure conjecturée de Omega(n^2).

In this work, we propose cryptographic protocols for key exchange, bit commitment and oblivious transfer. Our oblivious transfer protocol, universal cryptographic primitive for multipartie computation, is inspired from Merkle's key exchange protocol with puzzles, and improves on existing results. Then, we show that it's possible to build those same cryptographic primitives without the hypothesis of one-way functions, but with the 3SUM problem. This simple problem ---in a list of n integers, find three that sum is a desired value--- has a conjectured lower bound of Omega(n^2).