Zero-Knowledge Arguments from Secure Multiparty Computation

This thesis aims to study zero-knowledge arguments, a cryptographic primitive that allows to prove a statement while yielding nothing beyond its truth (we may call it proof instead of argument depending on the security model). Specifically, we focus on a family of arguments whose construction is based on secure multiparty computation. It is well-known that, given any functionality, there exists a secure multiparty protocol computing it. Let us take a generic one-way function f, and a secure multiparty protocol computing f, then it has been shown quite recently that we can build a zero-knowledge argument for the NP-problem of finding a pre-image of f. This construction was considered only theoretical until a few years ago, and our work contributes to the emergence of new techniques as well as efficient applications in this paradigm. As an appetizer, we develop simple zero-knowledge protocols that significantly improve the state-of-the-art communication complexity for some well-known problems. Our first substantial contribution, with a desire to share small elements, is the introduction of a sharing over the integers that is securely embedded in our protocols with some artificial abortion. Applications are manifold, eventually in the post-quantum regime. In the line with our sharing over the integers, we propose a cryptographic string commitment scheme based on subset sum problems. In particular, it enables efficient arguments for circuit satisfiability. Then, we present a proof construction employing conversion between additive and multiplicative secret sharings, leading to efficient proofs of linear and multiplicative relations. The applications are again manifold when designing arguments and digital signatures. Finally, leaving aside protocols conception, we explore cryptography foundations with multi-prover zero-knowledge proofs, a framework for distributing the prover’s computation. To capture the full interest of this dispatching, we add to the literature a fundamental result for threshold zero-knowledge proofs for generic NP-statement.