International Association for Cryptologic Research

International Association
for Cryptologic Research


Mario Di Raimondo


Mon$\mathbb {Z}_{2^{k}}$a: Fast Maliciously Secure Two Party Computation on $\mathbb {Z}_{2^{k}}$ 📺
In this paper we present a new 2-party protocol for secure computation over rings of the form $$mathbb {Z}_{2^k}$$ . As many recent efficient MPC protocols supporting dishonest majority, our protocol consists of a heavier (input-independent) pre-processing phase and a very efficient online stage. Our offline phase is similar to BeDOZa (Bendlin et al. Eurocrypt 2011) but employs Joye-Libert (JL, Eurocrypt 2013) as underlying homomorphic cryptosystem and, notably, it can be proven secure without resorting to the expensive sacrifice step. JL turns out to be particularly well suited for the ring setting as it naturally supports $$mathbb {Z}_{2^k}$$ as underlying message space. Moreover, it enjoys several additional properties (such as valid ciphertext-verifiability and efficiency) that make it a very good fit for MPC in general. As a main technical contribution we show how to take advantage of all these properties (and of more properties that we introduce in this work, such as a ZK proof of correct multiplication) in order to design a two-party protocol that is efficient, fast and easy to implement in practice. Our solution is particularly well suited for relatively large choices of k ( e.g. $$k=128$$ ), but compares favorably with the state of the art solution of SPD $$mathbb {Z}_{2^k}$$ (Cramer et al. Crypto 2018) already for the practically very relevant case of $$mathbb {Z}_{2^{64}}$$ .
Deniable Authentication and Key Exchange
Mario Di Raimondo Rosario Gennaro Hugo Krawczyk
We extend the definitional work of Dwork, Naor and Sahai from deniable authentication to deniable key-exchange protocols. We then use these definitions to prove the deniability features of SKEME and SIGMA, two natural and efficient protocols which serve as basis for the Internet Key Exchange (IKE) protocol. The two protocols require distinct approaches to their deniability analysis, hence highlighting important definitional issues as well as necessitating different tools in the analysis. SKEME is an encryption-based protocol for which we prove full deniability based on the plaintext awareness of the underlying encryption scheme. Interestingly SKEME's deniability is possibly the first ``natural'' application which essentially requires plaintext awareness (until now this notion has been mainly used as a tool for proving chosen-ciphertext security); in particular this use of plaintext awareness is not tied to the random oracle model. SIGMA, on the other hand, uses non-repudiable signatures for authentication and hence cannot be proven to be fully deniable. Yet we are able to prove a weaker, but meaningful, ``partial deniability" property: a party may not be able to deny that it was ``alive" at some point in time but can fully deny the contents of its communications and the identity of its interlocutors. We remark that the deniability of SKEME and SIGMA holds in a concurrent setting and does not essentially rely on the random oracle model.
Secure Multiplication of Shared Secrets in the Exponent
Mario Di Raimondo Rosario Gennaro
We present a new protocol for the following task. Given tow secrets a,b shared among n players, compute the value g^{ab}. The protocol uses the generic BGW approach for multiplication of shared secrets, but we show that if one is computing ``multiplications in the exponent'' the polynomial randomization step can be avoided (assuming the Decisional Diffie-Hellman Assumption holds). This results in a non-interactive and more efficient protocol.

Program Committees

PKC 2011