## CryptoDB

### Ignacio Cascudo

#### Affiliation: Aalborg University, Denmark

#### Publications

**Year**

**Venue**

**Title**

2019

ASIACRYPT

Efficient UC Commitment Extension with Homomorphism for Free (and Applications)
Abstract

Homomorphic universally composable (UC) commitments allow for the sender to reveal the result of additions and multiplications of values contained in commitments without revealing the values themselves while assuring the receiver of the correctness of such computation on committed values. In this work, we construct essentially optimal additively homomorphic UC commitments from any (not necessarily UC or homomorphic) extractable commitment, while the previous best constructions require oblivious transfer. We obtain amortized linear computational complexity in the length of the input messages and rate 1. Next, we show how to extend our scheme to also obtain multiplicative homomorphism at the cost of asymptotic optimality but retaining low concrete complexity for practical parameters. Moreover, our techniques yield public coin protocols, which are compatible with the Fiat-Shamir heuristic. These results come at the cost of realizing a restricted version of the homomorphic commitment functionality where the sender is allowed to perform any number of commitments and operations on committed messages but is only allowed to perform a single batch opening of a number of commitments. Although this functionality seems restrictive, we show that it can be used as a building block for more efficient instantiations of recent protocols for secure multiparty computation and zero knowledge non-interactive arguments of knowledge.

2018

CRYPTO

Amortized Complexity of Information-Theoretically Secure MPC Revisited
📺
Abstract

A fundamental and widely-applied paradigm due to Franklin and Yung (STOC 1992) on Shamir-secret-sharing based general n-player MPC shows how one may trade the adversary thresholdt against amortized communication complexity, by using a so-called packed version of Shamir’s scheme. For e.g. the BGW-protocol (with active security), this trade-off means that if
$$t + 2k -2 < n/3$$
t+2k-2<n/3, then kparallel evaluations of the same arithmetic circuit on different inputs can be performed at the overall cost corresponding to a single BGW-execution.In this paper we propose a novel paradigm for amortized MPC that offers a different trade-off, namely with the size of the field of the circuit which is securely computed, instead of the adversary threshold. Thus, unlike the Franklin-Yung paradigm, this leaves the adversary threshold unchanged. Therefore, for instance, this paradigm may yield constructions enjoying the maximal adversary threshold
$$\lfloor (n-1)/3 \rfloor $$
⌊(n-1)/3⌋ in the BGW-model (secure channels, perfect security, active adversary, synchronous communication).Our idea is to compile an MPC for a circuit over an extension field to a parallel MPC of the same circuit but with inputs defined over its base field and with the same adversary threshold. Key technical handles are our notion of reverse multiplication-friendly embeddings (RMFE) and our proof, by algebraic-geometric means, that these are constant-rate, as well as efficient auxiliary protocols for creating “subspace-randomness” with good amortized complexity. In the BGW-model, we show that the latter can be constructed by combining our tensored-up linear secret sharing with protocols based on hyper-invertible matrices á la Beerliova-Hirt (or variations thereof). Along the way, we suggest alternatives for hyper-invertible matrices with the same functionality but which can be defined over a large enough constant size field, which we believe is of independent interest.As a demonstration of the merits of the novel paradigm, we show that, in the BGW-model and with an optimal adversary threshold
$$\lfloor (n-1)/3 \rfloor $$
⌊(n-1)/3⌋, it is possible to securely compute a binary circuit with amortized complexity O(n) of bits per gate per instance. Known results would give
$$n \log n$$
nlogn bits instead. By combining our result with the Franklin-Yung paradigm, and assuming a sub-optimal adversary (i.e., an arbitrarily small
$$\epsilon >0$$
ϵ>0 fraction below 1/3), this is improved to O(1) bits instead of O(n).

2011

CRYPTO

#### Program Committees

- Eurocrypt 2018
- Asiacrypt 2015

#### Coauthors

- Hao Chen (2)
- Ronald Cramer (6)
- Ivan Damgård (5)
- Bernardo Machado David (1)
- Bernardo David (2)
- Nico Döttling (2)
- Rafael Dowsley (1)
- Oriol Farràs (1)
- Irene Giacomelli (2)
- Robbert de Haan (1)
- Felipe Lacerda (1)
- Diego Mirandola (1)
- Jesper Buus Nielsen (2)
- Samuel Ranellucci (2)
- Roberto Trifiletti (1)
- Chaoping Xing (4)
- Chen Yuan (1)
- Gilles Zémor (1)