Chiffrement et cryptographie

Le plus simple pour montrer que c'est faisable est le petit test de Quisquater et Guillou.

• Deux pièces, A et B, sont séparées par une porte codée. Pour passer d'une pièce à l'autre, il faut connaitre le code. La porte est initialement ouverte.
• Alice entre et choisit d'aller dans la pièce A ou B. La porte codée se ferme. Par exemple Alice va dans la pièce A.
• Alice doit prouver à Bob, dehors, qu'elle connait le code, mais sans lui révéler le code.
• Bob lui dit alors de sortir par la porte B: Alice sera donc forcée de taper le code pour sortir côté B.
• Mais Bob aurait pu demander la porte A, et Alice aurait eu de la chance: rien à faire.
• Donc on recommence du début, et le fait 20 fois de suite (par exemple).
• Une chance sur 2 qu'Alice soit déjà dans la bonne pièce. La probabilité qu'Alice ne franchisse jamais la porte codée devient alors extrêmement faible (2^-20).

Finalement, Alice a prouvé à Bob qu'elle connait le code (avec une probabilité très élevée), sans jamais avoir révélé ledit code.

Ceci peut être très commode pour prouver son identité sans devoir la donner (ce qui est surprenant, non ?). Et donc protéger sa vie privée et ça l'État aimera moins.

Pas mal de propositions de protocoles existent, c'est un sujet à part entière. Basiquement, il existe deux méthodes :

1. la première se dénomme sigma-protocols et ressemble à ce qui vient d'être décrit : il y a un commitment suivi d'un challenge-response
2. la seconde est non-interactive ZK où on envoie directement la preuve, mais qui requiert des éléments spéciaux.

Autrement dit, le domaine est assez compliqué, parce qu'en plus on peut transformer la première méthode vers la seconde.

A noter: il existe des propositions de protocoles ZK post-quantique, car évidemment, ces techniques se font attaquer par les ordinateurs quantiques. C'est pour ça que j'en parle.