International Association for Cryptologic Research

International Association
for Cryptologic Research

CryptoDB

Moni Naor

Publications

Year
Venue
Title
2019
JOFC
Hardness-Preserving Reductions via Cuckoo Hashing
The focus of this work is hardness-preserving transformations of somewhat limited pseudorandom functions families (PRFs) into ones with more versatile characteristics. Consider the problem of domain extension of pseudorandom functions: given a PRF that takes as input elements of some domain $$\mathcal {U}$$U, we would like to come up with a PRF over a larger domain. Can we do it with little work and without significantly impacting the security of the system? One approach is to first hash the larger domain into the smaller one and then apply the original PRF. Such a reduction, however, is vulnerable to a “birthday attack”: after $$\sqrt{\left| \mathcal {U}\right| }$$U queries to the resulting PRF, a collision (i.e., two distinct inputs having the same hash value) is very likely to occur. As a consequence, the resulting PRF is insecure against an attacker making this number of queries. In this work, we show how to go beyond the aforementioned birthday attack barrier by replacing the above simple hashing approach with a variant of cuckoo hashing, a hashing paradigm that resolves collisions in a table by using two hash functions and two tables, cleverly assigning each element to one of the two tables. We use this approach to obtain: (i) a domain extension method that requires just two calls to the original PRF can withstand as many queries as the original domain size, and has a distinguishing probability that is exponentially small in the amount of non-cryptographic work; and (ii) a security-preserving reduction from non-adaptive to adaptive PRFs.
2019
TCC
Incrementally Verifiable Computation via Incremental PCPs
If I commission a long computation, how can I check that the result is correct without re-doing the computation myself? This is the question that efficient verifiable computation deals with. In this work, we address the issue of verifying the computation as it unfolds. That is, at any intermediate point in the computation, I would like to see a proof that the current state is correct. Ideally, these proofs should be short, non-interactive, and easy to verify. In addition, the proof at each step should be generated efficiently by updating the previous proof, without recomputing the entire proof from scratch. This notion, known as incrementally verifiable computation, was introduced by Valiant [TCC 08] about a decade ago. Existing solutions follow the approach of recursive proof composition and can be based on strong and non-falsifiable cryptographic assumptions (so-called “knowledge assumptions”).In this work, we present a new framework for constructing incrementally verifiable computation schemes in both the publicly verifiable and designated-verifier settings. Our designated-verifier scheme is based on somewhat homomorphic encryption (which can be based on Learning with Errors) and our publicly verifiable scheme is based on the notion of zero-testable homomorphic encryption, which can be constructed from ideal multi-linear maps [Paneth and Rothblum, TCC 17].Our framework is anchored around the new notion of a probabilistically checkable proof (PCP) with incremental local updates. An incrementally updatable PCP proves the correctness of an ongoing computation, where after each computation step, the value of every symbol can be updated locally without reading any other symbol. This update results in a new PCP for the correctness of the next step in the computation. Our primary technical contribution is constructing such an incrementally updatable PCP. We show how to combine updatable PCPs with recently suggested (ordinary) verifiable computation to obtain our results.
2018
EUROCRYPT
2018
TCC
2018
TCC
The Security of Lazy Users in Out-of-Band Authentication
Moni Naor Lior Rotem Gil Segev
Faced with the threats posed by man-in-the-middle attacks, messaging platforms rely on “out-of-band” authentication, assuming that users have access to an external channel for authenticating one short value. For example, assuming that users recognizing each other’s voice can authenticate a short value, Telegram and WhatApp ask their users to compare 288-bit and 200-bit values, respectively. The existing protocols, however, do not take into account the plausible behavior of users who may be “lazy” and only compare parts of these values (rather than their entirety).Motivated by such a security-critical user behavior, we study the security of lazy users in out-of-band authentication. We start by showing that both the protocol implemented by WhatsApp and the statistically-optimal protocol of Naor, Segev and Smith (CRYPTO ’06) are completely vulnerable to man-in-the-middle attacks when the users consider only a half of the out-of-band authenticated value. In this light, we put forward a framework that captures the behavior and security of lazy users. Our notions of security consider both statistical security and computational security, and for each flavor we derive a lower bound on the tradeoff between the number of positions that are considered by the lazy users and the adversary’s forgery probability.Within our framework we then provide two authentication protocols. First, in the statistical setting, we present a transformation that converts any out-of-band authentication protocol into one that is secure even when executed by lazy users. Instantiating our transformation with a new refinement of the protocol of Naor et al. results in a protocol whose tradeoff essentially matches our lower bound in the statistical setting. Then, in the computational setting, we show that the computationally-optimal protocol of Vaudenay (CRYPTO ’05) is secure even when executed by lazy users – and its tradeoff matches our lower bound in the computational setting.
2017
JOFC
2016
CRYPTO
2016
CRYPTO
2016
TCC
2016
JOFC
2015
TCC
2015
TCC
2015
CRYPTO
2015
ASIACRYPT
2014
CRYPTO
2014
ASIACRYPT
2013
TCC
2010
EUROCRYPT
2009
TCC
2009
TCC
2009
ASIACRYPT
2009
CRYPTO
2008
TCC
2006
CRYPTO
2006
CRYPTO
2006
EUROCRYPT
2006
EUROCRYPT
2006
JOFC
2005
CRYPTO
2005
EUROCRYPT
2005
TCC
2005
JOFC
2004
EUROCRYPT
2003
CRYPTO
2003
CRYPTO
2002
CRYPTO
2002
JOFC
2001
CRYPTO
2000
ASIACRYPT
2000
CRYPTO
1999
CRYPTO
1999
EUROCRYPT
1999
JOFC
1998
CRYPTO
1998
CRYPTO
1998
EUROCRYPT
1998
EUROCRYPT
1998
JOFC
1998
JOFC
1997
CRYPTO
1997
CRYPTO
1996
JOFC
1994
CRYPTO
1994
CRYPTO
1994
EUROCRYPT
1993
CRYPTO
1993
CRYPTO
1992
CRYPTO
1992
CRYPTO
1992
CRYPTO
1991
JOFC
1989
CRYPTO
1988
CRYPTO

Program Committees

TCC 2015
TCC 2008
Eurocrypt 2007 (Program chair)
Crypto 2006
Crypto 2005
TCC 2004 (Program chair)
Eurocrypt 2003
PKC 2003
Asiacrypt 2000
Eurocrypt 2000
Crypto 1997
Crypto 1995
Crypto 1991