DIMACS Workshop on Cryptography and Intractability

March 20 - 22, 2000
DIMACS Center, CoRE Building, Busch Campus, Rutgers University, Piscataway, NJ

Moni Naor, Weizmann Institute of Science, naor@wisdom.weizmann.ac.il
Joe Kilian, NEC Research Institute, joe@research.nj.nec.com
Shafi Goldwasser, MIT and Weizmann Institute of Science, shafi@theory.lcs.mit.edu
Presented under the auspices of the DIMACS Special Year on Computational Intractability and the DIMACS Special Year on Networks.



Speaker: Ran Canetti, IBM Watson
Title: Resettable Zero Knowledge

We introduce the notion of Resettable Zero Knowledge (rZK),
a new security measure for cryptographic protocols
which strengthens the classical notion of zero-knowledge.
In essence, an rZK protocol is one that remains zero knowledge
even if an adversary can interact with the prover many times, each
time resetting the prover to its initial state and forcing it to
use the same random tape.

All known examples of zero-knowledge proofs and arguments
are trivially breakable in this setting. Moreover, by definition, 
all zero-knowledge proofs of knowledge are breakable in this setting.
Thus, a valid question is whether rZK protocols for non-trivial
languages exist altogether. We answer this question in the affirmative.
Under general complexity assumptions, which hold for example if the 
Discrete Logarithm Problem is hard, we construct rZK and rWI (resettable
Witness Indistinguishable) proof-systems for NP in various models.

In addition to shedding new light on what makes zero knowledge possible 
(by constructing ZK protocols that use randomness in a dramatically 
weaker way than before), rZK has great relevance to applications.
Firstly, rZK protocols are closed under parallel and concurrent
execution and thus are guaranteed to be secure when implemented in 
fully asynchronous networks, even if an adversary schedules the arrival 
of every message sent so as to foil security. Secondly, rZK protocols
enlarge the range of physical ways in which provers of ZK protocols
can be securely implemented, including devices (such as smart cards)
which cannot reliably toss coins on line, nor keep state between 

Joint work with Oded Goldreich, Shafi Goldwasser and Silvio Micali.

2. Speaker: Yevgeniy Dodis, MIT Title: A Cryptographic Solution to a Game Theoretic Problem Although Game Theory and Cryptography seem to have some similar scenarios in common, it is very rare to find instances where tools from one area are applied in the other. In this work we use cryptography to solve a game theoretic problem. The problem that we discuss arises naturally in the game theory area of two-party strategic games. In these games there are two players. Each player decides on a ``move'' (according to some strategy), and then the players execute the game, i.e. the two players make their moves simultaneously. Once these moves are played each player receives a payoff, which depends on both moves. Each player only cares to maximize its payoff. In the game theory literature it was shown that higher payoffs can be achieved by the players if they use correlated strategies. This is enabled through the introduction of a trusted third party (a ``mediator''), who assists the players in choosing their move. Though now the property of the game being a {\em two player} game is lost. It is natural to ask whether a game can exist which would be a two player game yet maintain the high payoffs which the mediator aided strategy offered. We answer this question affirmatively. We extend the game by adding an initial step in which the two players communicate and then they proceed to execute the game as usual. For this extended game we can prove (informally speaking) the following: any correlated strategy for 2-player games can be achieved, provided that the players are computationally bounded and can communicate before playing the game. We obtain an efficient solution to the above game-theoretic problem, by providing a cryptographic protocol to the following {\em Correlated Element Selection} problem. Both Alice and Bob know a list of pairs $(a_1,b_1)\ldots (a_n,b_n)$ (possibly with repetitions), and they want to pick a {\em random} index $i$ such that Alice learns only $a_i$ and Bob learns only $b_i$. We believe that this problem has other applications, beyond our application to game theory. Our solution is quite efficient: it has constant number of rounds, negligible error probability, and uses only very simple zero-knowledge proofs.
3. Speaker: Cynthia Dwork, IBM Almaden Title: Zaps and Apps A zap is a a two-round (i.e one message from the verifier and a response from the prover) witness-indistinguishable protocol, where the verifier's message can be fixed ``once-and-for-all" and applied to any instance. We present a zap for every language in NP, based on the existence of non-interactive zero-knowledge proofs in the shared random string model. The zap is in the standard model, and requires *no* common random string. We use zaps to construct 3-round concurrent zero-knowledge interactive proofs for any NP language in the timing model of Dwork, Naor and Sahai (STOC'98). Joint work with Moni Naor.
4. Speaker: J. Feigenbaum (AT&T Labs) Title: Sharing the Cost of Multicast Transmissions We investigate cost-sharing algorithms for multicast transmission. Game-theoretic considerations point to two distinct mechanisms, marginal cost and Shapley value, as the two solutions most appropriate in this context. We prove that the former has a natural algorithm that uses only two messages per link of the multicast tree, while we give evidence that the latter requires a quadratic total number of messages. We also show that the welfare value achieved by an optimal multicast tree is NP-hard to approximate within any constant factor, even for bounded-degree networks. The lower-bound proof for the Shapley value uses a novel algebraic technique for bounding from below the number of messages exchanged in a distributed computation; this technique may prove useful in other contexts as well. These preliminary results suggest many possible research directions in the overlap of game theory and distributed algorithms. The talk will concentrate on open problems. This is joint work with C. Papadimitriou and S. Shenker.
5. Speaker: Yuval Ishai, DIMACS Title: Compressing Cryptographic Resources A private-key cryptosystem may be viewed as a means by which a trusted dealer privately conveys a large, shared pseudo-random object to a pair of players, using little communication. Alternatively, the messages distributed by the dealer may be viewed as a secure {\em compression} of a pair of large identical random pads (or random functions) into a shorter shared ``key'' or ``seed''. We address the question of extending this compression problem to more general correlation patterns among {\em several} players. Unlike the simple case of identical pads, where the main security concern is with respect to external eavesdroppers, in the case of general correlations players also have to be protected from each other. We show how to use pseudo-randomness in a black box manner for compressing some useful correlation patterns. The talk is based on joint work with Niv Gilboa.
6. Speaker: Michael Kearns, AT&T Labs Title: Computational Learning Theory and Cryptography: A Survey The relationship between machine learning and cryptography has been a rich and varied topic of research for over a decade now, since the introduction of Valiant's PAC learning framework and the seminal paper of Goldreich, Goldwasser and Micali on pseudorandom functions. I will provide a survey of this line of work, emphasizing the many interesting methods and problems encountered in its pursuit. In addition to many of the familiar weapons of public-key cryptography, these include Fourier methods using the parity basis, learning in the presence of noise, statistical query learning, distribution learning, and compression.
7. Speaker: Joe Kilian, NECI Title: More General Completeness Theorems for Secure Two-Party Computation We consider the power of cryptographic primitives, denoted $f$-cryptogates, defined as follows: Alice and Bob have inputs $x$ and $y$, respectively. Given a possibly probabilistic function, $f(x,y)$, the $f$-cryptogate computes $z\leftarrow f(x,y)$ and either broadcasts $z$ to both parties (the symmetric case) or sends $z$ exclusively to Bob (the asymmetric case); neither party learns more than what is provided by the $f$-cryptogate. We say that an $f$-cryptogate is complete if, using information-theoretic notions of reductions, security and privacy, one can use the cryptogate to perform secure two-party computation. We give a number of characterizations of the complete $f$-cryptogates, depending on the adversary model, whether the output of $f$ is probabilistic or deterministic, and whether the cryptogate is symmetric or asymmetric. For active adversaries, who may violate the protocol, we characterize the complete asymmetric $f$-cryptogates for deterministic $f$. For passive adversaries, who always follow the protocol, we characterize the complete symmetric and asymmetric $f$-cryptogates for all deterministic and probabilistic $f$. Our characterizations for asymmetric cryptogates generalizes a recent theorem of Beimel, Malkin and Micali.
8. Speaker: Tal Malkin, AT&T Title: The All-or-Nothing Nature of Two-Party Secure Computation A function $f$ is computationally securely computable if two computationally-bounded parties, Alice, having a secret input $x$, and Bob, having a secret input $y$, can talk back and forth so that (even if one of them is malicious) (1) Bob learns essentially only $f(x,y)$ while (2) Alice learns essentially nothing. We prove that, if {\em any} non-trivial function can be so computed, then so can {\em every} function. Consequently, the complexity assumptions sufficient and/or required for computationally securely computing $f$ are the same for every non-trivial function $f$. Joint work with Amos Beimel and Silvio Micali.
9. Speaker: Moni Naor, Weizmann Institute Title: Why We Need a Complexity Theory of Moderately-Hard Functions Functions that are moderately hard to compute have an important role in the design of cryptographic protocols. However they are usually neglected. This talk surveys various applications of moderately-hard functions and their desired properties.
10. Speaker: Rafail Ostrovsky, Telcordia Technologies Title: Recent Results on Single Database Private Information Retrieval We consider a setting where a user wishes to retrieve an item from a database, without letting the database administrator know which item is being retrieved. Of course, a trivial (but expensive) solution is for the user to request contents of the entire database, thus concealing from the database administrator which item is of interest to the user. Can this be done with less communication? In 1997, Kushilevitz and Ostrovsky shown that this is indeed possible with total communication complexity strictly less then the size of the database, under some standard cryptographic assumptions. Since then much progress has been achieved on this problem. In this work, I will show several recent results, among them a proof that any such non-trivial scheme (i.e. one where total communication is less then the total size of the database, even by one bit) implies Oblivious Transfer (joint work with Di Crescenzo and Malkin); and a way to construct a non-trivial such scheme based on any one-way trapdoor permutation (joint work with Kushilevitz). The talk will be self contained.
11. Speaker: Omer Reingold, AT&T Research Title: Magic Functions We show that three fundamental problems in distributed computing, cryptography, and complexity theory, are essentially the same problem. These problems are: (1) The selective decommitment problem. An adversary is given commitments to a collection of messages and is allowed to ask for some subset of the commitments to be opened. The question is whether seeing the decommitments to these open plaintexts allows the adversary to learn something unexpected about the plaintexts that are still hidden. (2) The power of 3-round weak zero-knowledge arguments. The question is what can be proved in (a possibly weakened form of) zero-knowledge in a 3-round argument. In particular, is there a language outside of BPP that has a 3-round public-coin weak zero-knowledge argument? (3) The Fiat-Shamir methodology. This is a method for converting a 3-round public-coin argument (viewed as an identification scheme) to a 1-round signature scheme. The method requires what we call a ``magic function'' that the signer applies to the first-round message of the argument to obtain a second-round message (queries from the verifier). An open question here is whether every 3-round public-coin argument for a language outside of BPP has a magic function. We define a hierarchy of definitions of zero-knowledge, starting with well-known definitions at the top and proceeding down through a series of weakenings. We show that if there is a gap in this hierarchy (a place where two adjacent levels differ) exhibited by a public-coin interactive argument, then the question in (3) has a negative answer (there is no magic function for this interactive proof). We also give a partial converse to this: informally, if there is no gap, then some form of magic is possible for every public-coin 3-round argument for a language outside of BPP. Finally, we relate the selective decommitment problem to public-coin proof systems and arguments at an intermediate level of the hierarchy, and obtain several positive security results for selective decommitment. Joint work with Cynthia Dwork, Moni Naor and Larry Stockmeyer
12. Speaker: Steven Rudich, CMU Title: Things You Can't Do With A Random Function Many fundamental cryptographic protocols can be constructed from a public, random function. This talk will summarize known results on the limits of what we can provably do based on such a function. This gives evidence for negative results such the statement that you can't base public-key cryptography on a one-way function.
13. Speaker: Dan Simon, Microsoft Title: The Cryptographic Uses of Oracle Separations Oracle separation can be a valuable tool for understanding the strength of the cryptographic assumptions necessary to achieve particular kinds of cryptographic functionality or efficiency. This talk will discuss some techniques for proving oracle separations, using as main examples the oracle results separating one-way permutations from both collision-intractable hash functions and very efficient universal one-way hash functions.
14. Speaker: Jacques Stern, Ecole Normale Sup'erieure Title: Twenty Years of Lattice Reduction in Cryptology Lattices are discrete subgroups of some $m$-dimensional space. Their study has been initiated in the 19th century. Lattice reduction tries to find nice representations of lattices: a celebrated algorithm due to Lenstra, Lenstra and Lov\'asz (LLL) computes a so-called {\em reduced basis} of a lattice. The relevance of lattice reduction to cryptology was immediately understood and LLL was used to break schemes based on the so-called knapsack problem. This success at breaking cryptographic schemes seemed to suggest that lattice reduction was an easy problem. In 1996 Ajtai discovered a fascinating connection between the worst-case complexity and the average-case complexity of some well-known lattice problems. He further proved the NP-hardness (under randomized reductions) of so-called shortest vector problem (SVP). Those complexity results suggested that lattice reduction might be a difficult problem after all, opening the door to positive applications in cryptology. Indeed, several cryptographic schemes based on the hardness of lattice problems were proposed shortly after Ajtai's discoveries. Some have been broken, while others seem to resist state-of-the-art attacks.
15. Speaker: Rebecca Wright, AT&T Title: Secure Multiparty Computation of Approximations Abstract: Multiparty approximations can sometimes be used to obtain efficient solutions where no efficient exact solution is known. In this paper, we consider secure multiparty approximate computations. For several specific real-valued functions f, we present protocols to compute an approximation f' in such a way that no party learns anything not implied by her own input and output. In general, cryptographic applications need to be both secure and efficient. Unfortunately, if f is inefficient, then a secure computation of f is (very) inefficient. Also, a secure computation of f' is not necessarily as private as a secure computation of f, because the output of f' may reveal more information about an input than the output of f does. We present definitions and protocols for secure multiparty approximations that realize most of the cost savings available by using f' instead of f without losing the privacy of a secure computation of f. joint work with Joan Feigenbaum, Jessica Fong, and Martin Strauss.
Other Workshops
DIMACS Homepage
Contacting the Center
Document last modified on March 15, 2000.