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
-
Schéma de signature à clé publique : Frobénius-UOV
Speaker : Gilles Macario-Rat - Orange
L'exposé présente un schéma de signature à clé publique post-quantique inspiré du schéma UOV et introduisant un nouvel outil : les formes de Frobénius. L'accent est mis sur le rôle et les propriétés des formes de Frobénius dans ce nouveau schéma : la simplicité de description, la facilité de mise en oeuvre et le gain inédit sur les tailles de signature et de clé qui bat RSA-2048 au niveau de[…]