DIMACS Workshop on Cryptography and Intractability

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

Organizers:

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

1.

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 
invocations. 

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