Thesis: post-quantum zero-knowledge authentication

Quantum computing is expected to break the cryptography that protects authentication today somewhere between 2028 and 2035. At the same time, users usually hand over more information than they should just to prove who they are, and lose control of their data.

Left unsolved, the risk is twofold: identity theft and leaks of sensitive personal information.

Thesis written in a pair. Both of us contribute to every part, but each one leads a different area.

My contributions

• Lead the Learning with Errors (LWE) mathematical component, including the choice of its variant and parameters.
• Co-design the authentication protocol and its prototype.

Team contributions

My partner leads the zero-knowledge proof (ZKP) part.

Decisions

• Options

  An interactive or a non-interactive protocol; and, for LWE, the binary, Ring-LWE, Module-LWE or rounding (Learning with Rounding) variant.

  Choice

  A non-interactive protocol based on Module-LWE.

  Why

  Both can be tuned easily to reach a given security target, are lightweight and run on low-end devices.

Changes of direction

• The first version of the prototype could leak the user’s secret, so it was redesigned: instead of sending the commitment over the network, it now sends only its high bits, which the verifier reconstructs.

• Network traffic went from megabytes down to a few kilobytes.
• Runtime went from several seconds to under half a second.
• The theoretical framework is complete; benchmarks for runtime, memory, network traffic and security in bits are still in progress.

Lessons learned

• Would add someone with an electronic engineering background to the team, to take the NTT (number-theoretic transform) from theory to a real implementation.