Noisy Public Keys

Context

Quantum computers are expected to break traditional cryptographic systems like RSA and ECC. In response, Learning with Errors (LWE) has emerged as a game-changing mathematical foundation for quantum-resistant security.

What is LWE? LWE involves solving noisy linear equations, a problem that sounds simple but becomes incredibly challenging due to the "noise." It introduces a small noise vector (e) to linear equations, transforming a simple linear system (A⋅s = b) into a computationally hard problem (A⋅s+e = b). While solving noiseless systems is straightforward, the addition of noise makes recovering the secret vector (s) computationally infeasible, even for quantum computers.

This problem is connected to hard lattice problems, which are resistant to both classical and quantum attacks. Imagine a grid (lattice) where a "noisy" point is slightly off the grid. The task is to find the nearest lattice point, a problem known as the Closest Vector Problem (CVP). This seemingly simple concept underpins the complexity and security of LWE-based systems. LWE is a critical building block for secure systems in the quantum era, ensuring long-term data protection.

Solutions

work in this area is excellent: https://research.ibm.com/publications/lattice-based-blind-signatures-short-efficient-and-round-optimal

there is new work with a three-round approach: https://eprint.iacr.org/2020/769.pdf

References

Other Material

• See also wiki page on Random ID
• See also wiki page on Lattice Cryptography