Interactive hashing against quantum adversaries

Abstract

Nous proposons l'étude des schémas de mise en gage post-quantiques de bit dont le camouflage est garanti au sens statistique, appelé mise en gage camouflante. Nous cherchons à établir l'hypothèse de calcul la plus faible qui garantit alors son caractère liant. Dans le monde classique, l'existence de fonctions à sens unique est nécessaire et suffisante pour y parvenir. Cependant au moment d'écrire ces lignes, l'hypothèse post-quantique la plus faible connue demande l'existence de fonctions de hachage à effondrement (collapsing hash functions). Cette hypothèse est plus forte que l’existence de fonctions à sens unique en ce sens qu'aucune réduction du type boîte noire ne peut transformer une fonction à sens unique en fonctions de hachage à effondrement. Le hachage interactif est une primitive introduite par Naor, Ostrovsky, Ventkatessen et Yung en 1998 [26] pour obtenir des mises en gage camouflantes à partir de n'importe quelle permutation à sens unique. Il s'agissait de la première étape d'une séquence de réductions qui permettent d'obtenir une mise en gage camouflante à partir de n'importe quelle fonction à sens unique, l'hypothèse la plus faible pour cette tâche. Le hachage interactif n'a toujours pas été montré sûr dans le monde post-quantique. Nous proposons une preuve presque complète qui une fois terminée permettrait de montrer qu’il est possible d'obtenir une mise en gage camouflante post-quantique à partir de n'importe quelle permutation à sens unique. L'existence de permutations à sens unique est une hypothèse post-quantique plus faible que l'existence de fonctions de hachage à effondrement. La preuve de sécurité du hachage interactif dans le monde classique utilise lourdement une technique difficile à appliquer dans le monde quantique: le rembobinage de l'adversaire. Nous comptons utiliser un résultat récent de Chiesa, Ma, Spooner et Zhandry [10] pour éviter certains problèmes dus au rembobinage des adversaires quantiques. Nous disons que la preuve est presque complète puisqu'il manque un dernier résultat qui ne semble pas être impossible à prouver dans un futur proche. We propose the study of post-quantum statistically hiding and computationally binding bit commitment schemes. We aim to establish the weakest computational hypothesis that ensures its binding property. In the classical world, the existence of one-way functions is both necessary and sufficient to achieve this. However, as of this writing, the weakest known post-quantum hypothesis requires the existence of collapsing hash functions. This hypothesis is stronger than the existence of one-way functions in that no black-box reduction can transform a one-way function into collapsing hash functions. Interactive hashing is a primitive introduced by Naor, Ostrovsky, Venkatesan, and Yung in 1998 [26] to obtain statistically hiding commitments from any one-way permutation. It was the first step in a sequence of reductions that allow obtaining a statistically hiding commitment from any one-way function, the weakest hypothesis for this task. Interactive hashing has not yet been shown to be secure in the post-quantum world. We propose an almost complete proof which, once finished, will enable us to show that it is possible to obtain a post-quantum statistically hiding commitment from any one-way permutation. The existence of one-way permutations is a weaker post-quantum hypothesis than the existence of collapsing hash functions. The security proof of interactive hashing in the classical world heavily relies on a technique that is difficult to apply in the quantum world: adversary rewinding. We plan to use a recent result by Chiesa, Ma, Spooner and Zhandry in [10] to address some of the issues arising from rewinding quantum adversaries. We say the proof is almost complete since a necessary result is yet unproven, but it does seem like proving this missing piece is achievable in the near future.