Research output: Book/anthology/dissertation/report › Ph.D. thesis

- Ph.D. Dissertation Valerio Pastro
Submitted manuscript, 1.05 MB, PDF document

- 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).

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 language | English |
---|

Publisher | Department of Computer Science, Aarhus University |
---|---|

Number of pages | 128 |

Publication status | Published - 31 Jul 2013 |

See relations at Aarhus University Citationformats

No data available

ID: 55311878