Abstracts of talks for the Weizmann Workshop on Cryptography %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% Speaker: Amir Herzberg Title: Secure Payments over the Internet Electronic commerce is one of the exciting applications of the Internet. One of the prerequisites are secure payment mechanisms. In this talk we will review and compare some of the proposals for secure payments over the Internet. We will focus on two mechanisms: - Secure credit-card payments, such as the SET standard being defined by MasterCard and Visa. We will show the evolution from iKP (from IBM) and STT (Visa/Microsoft) to SET. - Secure Micro-Payments payments, where the amounts involved are too small to be efficiently handled by credit card protocols (e.g. 1 cent). We will present and demo the MiniPay mechanism, which is now being tested in alpha trials with several customers. Minipay features scalable, decentralized design, ease of use (click and pay), low overhead, and negligible delay. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% Title: Efficient and Secure Metering Speaker: Benny Pinkas We consider an environment in which many servers serve an even larger number of clients. It is required to meter the interaction between each server and the clients and in particular the number of clients that approached the server. An immediate application is to measure the popularity of web pages in order to decide on advertisement fees. The metering process should be efficient (even more efficient than micropayments) to all parties involved (clients, servers and the metering authority) and secure against fraud. We present several such metering systems. Joint work with Moni Naor. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% Title: Automatic Water marking, Dynamic Traitor Tracing and related Objects Speaker: Amos Fiat In this talk we'll describe a practical approach designed to combat television piracy in todays Internet environment. We will then also describe the relationship of these new piracy combating schemes to traitor tracing schemes, water marking of copyrighted material (including viewer identity imprinting), and new approaches to the water marking problem that allow one to watermark automatically even in a broadcast environment or by posting content on the Web. Joint work with Tamir Tassa and Dror Lapidot. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% Title: Hashing and Authentication in Software at Gbit/sec Speeds Speaker: Hugo Krawczyk Abstract: We describe a construction of almost universal hash functions suitable for very fast software implementation and applicable to the hashing of variable length data and fast cryptographic message authentication. Our scheme uses fast single precision arithmetic which is increasingly supported by modern processors due to the growing needs for fast arithmetic possed by multimedia processing. We report on hand-optimized assembly implementations on a 150 MHz PowerPC 604 and a 150 MHz Pentium-Pro, which achieve hashing speeds of 350 to 820 Mbit/second, depending on the desired level of security (or collision probability), and a rate of more than 1 Gbit/sec on a 200 MHz Pentium-Pro. This is a significant speed-up over current software implementations of universal hashing and other message authentication techniques (e.g., MD5-based). Moreover, our construction is specifically designed to take advantage of emerging microprocessor technologies (such as multimedia support, 64-bit architectures and others) and then best suited to accomodate the growing performance needs of hashing applications (e.g., search engines, authentication of real-time data, etc.). The construction is based on techniques due to Carter and Wegman for universal hashing using modular multilinear functions that we carefully modify to allow for fast software implementation. We prove the resultant construction to retain the necessary mathematical properties required for its use in hashing and message authentication. Joint work with Shai Halevi, MIT. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% Title: Visual Cryptography with Polarization Speaker: Eli Biham Visual cryptography traditionally use overlapping black and white (or color) pixels, which when put together, construct a secret picture. This technique causes white areas in the original secret picture to appear in some random combination of black and white pixels in the constructed picture. Thus, the contrast, i.e., the difference between the constructed black and the constructed white, becomes small, and reduces much the quality of the constructed picture. Furthermore, Naor and Shamir show that the contrast decreases exponentially with the number of shares. In this talk we show how to use light polarization for visual cryptography, and show reductions and equivalences between polarized secret sharing schemes and the schemes of Naor and Shamir. Finally, we show efficient $n$ out of $n$ schemes whose contrast is theoretically fixed for any $n$. Joint work with Ayal Itzkovitz %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% Speaker: Dan Boneh Title: Efficient generation of shared RSA keys We show how three or more parties can engage in an efficient distributed computation to generate an RSA modulus N=pq. At the end of the computation all parties know that N is a product of two primes, however no party knows the factorization of N. We show how the parties can then proceed to compute a public RSA encryption exponent and shares of the corresponding decryption exponent. These results eliminate the need for a trusted dealer in many cryptographic applications. Joint work with Matt Franklin. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% Title: Cryptanalytic Fault Attacks Speaker: Adi Shamir The talk will include an overview as well as new unpublished results. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% Title: A Public-Key Cryptosystem with Worst-Case/Average-Case Equivalence Speaker: Cynthia Dwork We present a probabilistic public key cryptosystem which is secure unless the worst case of the following lattice problem can be solved in polynomial time: ``Find the shortest nonzero vector in an $n$-dimensional lattice where the shortest vector $v$ is unique in the sense that any other vector whose length is at most $n^c \|v\|$ is parallel to $v$.'' This is joint work with Miki Ajtai. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% Title: The Brain can Compute Pseudo-Random Functions or Efficient Cryptographic Primitives Based on the Decisional Diffie-Hellman Assumption Speaker: Omer Reingold We describe efficient constructions for various cryptographic primitives (both in private-key and in public-key cryptography), based on the decisional version of the Diffie-Hellman assumption. Our major result is a new and efficient construction of pseudo-random functions. Computing the value of the function at any given point involves two multiple products (which is comparable with two exponentiations). In particular, the functions can be computed in TC^0 (the class of functions computable by constant depth circuits consisting of a polynomial number of threshold gates). Using the simple algebraic structure of the pseudo-random function, f_s, we show a zero-knowledge proof for statements of the form ``y=f_s(x)'' and ``y neq f_s(x)'' and additional features of the functions. Joint work with Moni Naor. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% Title: Computationally Private Information Retrieval Speaker: Niv Gilboa Private information retrieval (PIR) schemes enable a user to access $k$ replicated copies of a database ($k\geq 2$), and {\em privately} retrieve one of the $n$ bits of data stored in the databases. This means that the queries give each individual database no partial information (in the information theoretic sense) on the identity of the item retrieved by the user. Today, the best two database scheme ($k=2$) has communication complexity $O(n^{1/3})$, while for any constant number, $k$, the best $k$ database scheme has communication complexity $O(n^{1/(2k-1)})$. The motivation for the present work is the question whether this complexity can be reduced if one is willing to achieve {\em computational privacy}, rather than {\em information theoretic privacy}. (This means that privacy is guaranteed only with respect to databases that are restricted to polynomial time computations.) We answer this question affirmatively, and show that the computational approach leads to substantial savings. For every $\varepsilon>0$, we present a {\em two database} computational PIR scheme whose communication complexity is $O(n^\varepsilon)$. This improved efficiency is achieved by a combination of a novel balancing technique, together with careful application of pseudo random generators. Our schemes preserve some desired properties of previous solutions. In particular, all our schemes use only one round of communication, they are fairly simple, they are memoryless, and the database contents is stored in its plain form, without any encoding. Joint work with Benny Chor %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% Title: Fast Multiplication on Elliptic Curves over Small Fields of Characteristic Two Speaker: Volker Mueller I discuss a new algorithm for multiplying points on elliptic curves defined over small finite fields of characteristic two. This algorithm is an extension of previous results by Koblitz, Meier and Staffelbach. Experimental results show that the new methods can give a running time improvement of up to 50\% compared to the ordinary binary algorithm for multiplication. Finally, I discuss the usability of these elliptic curves for public key cryptosystems. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% Title: Chameleon Hashing and Signatures Speaker: Tal Rabin Undeniable signatures were introduced by Chaum and van Antwerpen in order to bridge between the contradictory requirements of controlled dissemination and non-repudiation of signatures. The basic paradigm behind this type of signatures is that verification or denial of a signature requires the collaboration of the signer. Due to the strong functionality requirements undeniable signatures are more expensive and complex than regular digital signatures. Here we introduce {\em chameleon signatures} that retain much of the properties of undeniable signatures but allow for significantly simpler and efficient realizations. Chameleon signatures are generated under the standard method of hash-then-sign. Yet, the hash functions which are used are {\em chameleon hash functions}. These hash functions are characterized by the non-standard property of being collision-resistant for the signer but collision tractable for the recipient. We present simple constructions of chameleon hashing and chameleon signatures. The former can be derived from {\em any} (non-interactive) trapdoor commitment scheme for which several practical constructions are known. We prove the unforgeability property of our signatures solely based on the unforgeability of the underlying digital signature in use. Our schemes are non-interactive and do not involve the design and complexity of zero-knowledge proofs, which form the basis of traditional undeniable signatures. Joint work with Hugo Krawczyk %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% Title: Merkle-Hellman revisited: a cryptanalysis of the Qu-Vanstone cryptosystem based on group factorizations Speaker: Jacques Stern Cryptosystems based on the knapsack problem were among the first public key systems to be invented and for a while were considered quite promising. Basically all knapsack cryptosystems that have been proposed so far have been broken, mainly by means of lattice reduction techniques. However, a few knapsack-like cryptosystems have withstood cryptanalysis, among which the Chor-Rivest scheme even if this is debatable, and the Qu-Vanstone scheme proposed at the Dagstuhl'93 workshop and later published. The Qu-Vanstone scheme is a public key scheme based on group factorizations in the additive group of integers modulo $n$ that generalizes Merkle-Hellman cryptosystems. In this paper, we present a novel use of lattice reduction, which is of independent interest, exploiting in a systematic manner the notion of an orthogonal lattice. Using the new technique, we successfully attack the Qu-Vanstone cryptosystem. Namely, we show how to recover the private key from the public key. The attack is based on a careful study of the so-called Merkle-Hellman transformation. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% Title: Pseudo Random Number Generators Within Cryptographic Algorithms Speaker: Shafi Goldwasser We totally break the DSS signature algorithm when used with several variants of the ``pseudo-random'' linear congruential generator (truncated etc). This is further indication of the danger of using weak pseudo random number generators within cryptographic algorithms. Joint work with Mihir Bellare and Daniel Micciancio.