^April May – 2009 ^June

We prove the equivalence, up to a small polynomial approximation factor sqrt(n/ log n), of the lattice problems uSVP (unique Shortest Vector Problem), BDD (Bounded Distance Decoding) and GapSVP (the decision version of the Shortest Vector Problem). This resolves a long-standing open problem about the relationship between uSVP and the more standard GapSVP, as well the BDD problem commonly used in coding theory. The main cryptographic application of our work is the proof that the Ajtai-Dwork and the Regev cryptosystems, which were previously only known to be based on the hardness of uSVP, can be equivalently based on the hardness of the more standard worst-case GapSVP. Also, in the case of uSVP and BDD, our connection is very tight, establishing the equivalence (within a small constant approximation factor) between the two most central problems used in lattice based public key cryptography and coding theory.

This is joint work with Daniele Micciancio and will appear at CRYPTO 2009

In the setting of secure computation, a set of parties wish to securely compute some function of their inputs, in the presence of an adversary. The adversary in question may be static (meaning that it controls a predetermined subset of the parties) or adaptive (meaning that it can choose to corrupt parties during the protocol execution and based on what it sees). In this talk, we study two fundamental questions relating to the basic zero-knowledge and oblivious transfer protocol problems: Adaptive zero-knowledge proofs: We ask whether it is possible to construct adaptive zero-knowledge proofs (with unconditional soundness). Beaver (STOC 1996) showed that known zero-knowledge proofs are not adaptively secure, and in addition showed how to construct zero-knowledge arguments (with computational soundness). Adaptively secure oblivious transfer: All known protocols for adaptively secure oblivious transfer rely on seemingly stronger hardness assumptions than for the case of static adversaries. We ask whether this is inherent, and in particular, whether it is possible to construct adaptively secure oblivious transfer from enhanced trapdoor permutations alone. We provide surprising answers to the above questions, showing that achieving adaptive security is sometimes harder than achieving static security, and sometimes not. First, we show that assuming the existence of one-way functions only, there exists adaptive zero-knowledge proofs for all languages in NP. In order to prove this, we overcome the problem that all adaptive zero-knowledge protocols known until now used equivocal commitments (which would enable an all-powerful prover to cheat). Second, we prove a black-box separation between adaptively secure oblivious transfer and enhanced trapdoor permutations. As a corollary, we derive a black-box separation between adaptively and statically securely oblivious transfer. This is the first black-box separation to relate to adaptive security and thus the first evidence that it is indeed harder to achieve security in the presence of adaptive adversaries than in the presence of static adversaries. A joint work with Yehuda Lindell

Frequent patterns are patterns that appear in a data set frequently. For example, a set of items, such as milk and bread, that appear together frequently in a transaction data set of shopping carts is a frequent itemset. Finding such patterns plays an essential role in mining correlations and other interesting relationships among data. Thus this topic has become an important data mining task and a focused theme in data mining research. The task of finding frequent patterns holds many challenges, such as huge data sets to mine and combinatorial number of frequent patterns to find. The two leading algorithms will be presented in our talk together with some other advanced issues such as mining frequent closed and maximal patterns, using generalizations to get interesting patterns, and more.

We revisit the question of secure multiparty computation (MPC) with two rounds of interaction. It was previously shown by Gennaro et al. (Crypto 2002) that three or more communication rounds are necessary for general MPC protocols which tolerate $tge 2$ corrupted parties, regardless of the total number of parties, and even if {em broadcast} messages are allowed in each round. We complement this negative result by presenting matching positive results. Our main result is that if only {em one} party can be corrupted, then $nge 5$ parties can securely compute any function of their inputs using only {em two} rounds of interaction over secure point-to-point channels (without broadcast or any additional setup). Our protocol provides computational security while making only a black-box use of a pseudorandom generator, or alternatively can provide unconditional security for ``computationally simple'' functions (e.g., functions in $NC^1$). We also prove a similar result in a client-server setting, where there are $mge 2$ clients who hold inputs and should receive outputs, and $n$ additional servers with no inputs and outputs. For this setting we obtain a general MPC protocol which requires a single message from each client to each server, followed by a single message from each server to each client. The protocol is secure against a single corrupted client and against coalitions of $t<n/3$ corrupted servers.