Zero-Knowledge Protocols and Multiparty Computation

Research output: Book/anthology/dissertation/reportPh.D. thesis


  • Valerio Pastro, Denmark
This thesis presents results in two branches of cryptography.
In the first part we construct two general multiparty computation protocols that can evaluate
any arithmetic circuit over a finite field. Both are built in the preprocessing model and achieve
active security in the setting of a dishonest majority, in which all players but one are controlled
by the adversary. In Chapter 5 we present both the preprocessing and the online phase of
[DKL+ 13], while in Chapter 2 we describe only the preprocessing phase of [DPSZ12] since
the combination of this preprocessing phase with the online phase of [DKL+ 13] yields a more
efficient protocol than that originally proposed in [DPSZ12]. Our preprocessing phases make
use of a somewhat homomorphic encryption scheme, and significantly improve on the previous
state of the art, both asymptotically and in practice. The online phase we present relies on
information-theoretic message authentication codes, requires only a linear amount of data from
the preprocessing, and improves on the number of field multiplications needed to perform one
secure multiplication (linear, instead of quadratic as in earlier work). The preprocessing phase
in Chapter 5 comes in an actively secure flavour and in a covertly secure one, both of which
compare favourably to previous work in terms of efficiency and provable security. Moreover,
the covertly secure solution includes a key generation protocol that allows players to obtain a
public key and shares of a corresponding secret key. In previous work this task was assumed to
be performed by an ideal functionality.
In the second part we shift our focus to a task that is related to multiparty computation in
an indirect way: we propose a zero-knowledge protocol that allows a prover to show a verifier
that he holds a tuple of three values in a finite field, in which the third one is the product of
the first two. We extend this protocol in two ways: first we consider the case where the values
are integers, and then we consider tuples of values that satisfy more general algebraic relations.
Our basic scheme achieves optimal amortized communication complexity, while the construction
over the integers improves the state of the art both in terms of communication complexity and
in the security requirements (it requires factoring instead of the strong RSA assumption).
Original languageEnglish
PublisherDepartment of Computer Science, Aarhus University
Number of pages128
Publication statusPublished - 31 Jul 2013

See relations at Aarhus University Citationformats

Download statistics

No data available

ID: 55311878