Abstract
Random linear codes are well known to be hard to decode, even with quantum computers, making them a strong alternative to lattice-based post-quantum cryptography, which has recently been standardised. However, traditional cryptography only secures data in transit, while a growing need is to compute on that data. If lattices also enable (fully) homomorphic encryption, this still requires heavy computations which may not be suitable for all use cases. In particular, when data is distributed among multiple users, secure Multi-Party Computation (MPC) offers a more practical alternative. However, its main bottleneck is often the cost of communication between parties. Fortunately, highly efficient online MPC protocols exist if all parties share a trusted source of correlated randomness, independent of the protocol’s inputs. The challenge then reduces to efficiently distributing this randomness. In this talk, I will present primitives known as Pseudorandom Correlation Generators which have recently been developed, leveraging the hardness of decoding random linear codes with a specific algebraic structures. These are now regarded as one of the most promising approaches for enabling practical MPC in the so-called "Correlated Randomness Model".
