Description
Secure multi-party computation (MPC) allows a set of $n$ players to securely compute an agreed function of their inputs, even when up to $t$ of the players are under complete adversarial control. We consider secure MPC in the information-theoretic model with broadcast channels (PKI setup) and present an efficient protocol with optimal resilience ($t< n/2$), using a new technique technique called dispute control: During the course of the protocol, the players keep track of disputes that arise among them, and the ongoing computation is adjusted such that known disputes cannot arise again. This prevents the faulty players from intervening too often, which again allows the honest players to reduce the frequency of expensive verifications. This way, we can securely (for some security parameter $\kappa$) compute a circuit with $m$ gates with communication complexity $O(m n^2 \kappa)$ bits (plus some overhead independent of $m$). This is to be compared with $\Omega(m n^{22} \kappa)$ -- the communication complexity of the best known protocol in the same model.
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[…] -
Yoyo tricks with a BEANIE
Speaker : Xavier Bonnetain - Inria
TBD-
Cryptography
-
Symmetrical primitive
-