Description
Secure multi-party computing often enhances efficiency by leveraging correlated randomness. Recently, Boyle et al. showcased the effectiveness of pseudorandom correlation generators (PCGs) in producing substantial correlated (pseudo)randomness, specifically for two-party random oblivious linear evaluations (OLEs). This process involves minimal interactions and subsequent local computations, enabling secure two-party computation with silent pre-processing. The methodology is extendable to N-party through programmable PCGs. However, existing programmable PCGs for OLEs face limitations, as they generate OLEs exclusively over large fields and relying on a recent divisible ring-LPN assumption lacking a robust security foundation. In this talk, I'll introduce the Quasi-Abelian Syndrome Decoding Problem, a broader interpretation of the Quasi-Cyclic decoding problem. The hardness of this new problem enables constructing programmable PCGs for OLE correlation on any field Fq (with q>2). This instantiation is resilient to attacks on the linear test framework and allows a reduction in search to decision, addressing weaknesses in previous constructions. This work is based on a joint work with Maxime Bombar, Geoffroy Couteau and Alain Couvreur.
Next sessions
-
Dual attacks in code-based (and lattice-based) cryptography
Speaker : Charles Meyer-Hilfiger - Inria Rennes
The hardness of the decoding problem and its generalization, the learning with errors problem, are respectively at the heart of the security of the Post-Quantum code-based scheme HQC and the lattice-based scheme Kyber. Both schemes are to be/now NIST standards. These problems have been actively studied for decades, and the complexity of the state-of-the-art algorithms to solve them is crucially[…]-
Cryptography
-
-
Lie algebras and the security of cryptosystems based on classical varieties in disguise
Speaker : Mingjie Chen - KU Leuven
In 2006, de Graaf et al. proposed a strategy based on Lie algebras for finding a linear transformation in the projective linear group that connects two linearly equivalent projective varieties defined over the rational numbers. Their method succeeds for several families of “classical” varieties, such as Veronese varieties, which are known to have large automorphism groups. In this talk, we[…]-
Cryptography
-