1 Introduction I am between the first and second year of my Masters leading to a PhD program at UCLA. The area of my research interest is Cryptography. An interesting part of my Summer Internship at SRC was that my host gave me the flexibility to define a project/problem for myself to work on. This gave me a lot of time to talk to the researchers at SRC for the first few weeks. I spent the 2-3 weeks studying the problem of designing an Uncensorable Bulletin Board with Mark Lillibridge and prototyping a spam resistant mailing system with Mark Manasse (my host). However, we didn't implement either of these ideas. I had the opportunity to work on two independent problems during the
rest of the summer which I summarize in the next two sections. 2 On Existence of Incompressible functions Dwork, Lotspeich, Naor ([2]) proposed a scheme for protecting Digital content from illegal distribution using a novel concept of "Digital Signets: Self Enforcing Protection of Digital Information". The main idea of the scheme was to make the decryption key to some encrypted digital information as large as the actual data, itself. A user is given a signet which is associated with his credit card number and using the pair the user can compute a decryption key to the encrypted digital data available publicly. Thus, a cheating user has two options: either part with his credit card number, or transmit a decryption key as large as the data itself! This claim, however, is not proved. Dwork et. al. conjectured that the security of their scheme is based on the incompressiblity of the function:  An incompressible function can be defined as follows. Consider two communicating parties. One party knows a short x and wants to communicate to another party the long value of ƒ(x) without revealing x. Roughly speaking, ƒ is incompressible if no feasible computable short message from the sender to the receiver simultaneously achieves both goals of enabling the receiver to compute ƒ(x), and hiding x. The principal open problem suggested by [2] was to prove the existence/inexistence of incompressible functions based on standard cryptographic assumptions. Working with Cynthia, I proved that Diffie-Hellman series is incompressible, under the Decisional Diffie-Hellman assumption. The main idea behind the proof is that if there exists polynomial time computable algorithm A for compressing the value of the series and polynomial time algorithm A' for retrieving the value of the series using this compressed value then there exists a polynomial time algorithm that can distinguish between a Diffie-Hellman Triplet and a triplet selected uniformly from the set of triplets in group Gp. The heart of the proof involved generating randomized Diffie-Hellman Series (or any series) using the ideas of Naor & Reingold, [1] from a Diffie-Hellman triplet (or a random triplet). Although we made some progress it still remains an open problem to
prove that the Signet Scheme is secure if the Diffie-Hellman series is
incompressible. Another is to design an incompressible function that
doesn't require a large publicly known data. A working manuscript of the
proof may be available upon request from the authors (i.e., Cynthia &
myself). 3 Resilient Deniable Authentication I kept myself busy attending a workshop on Algorithmic Number Theory and CRYPTO-2000 for a couple of weeks and then we sought for a new problem to work on. In a joint work with Cynthia and Moni Naor (at Stanford) we studied Deniable Authentication protocols under Intrusive Adversaries. The motivation behind this work can be found while trying to construct a protocol for "Stock Brokering Without Trust" or "Private Retrieval of Medical Database". The resiliency of an authentication protocol is defined with respect to the VIEW of an adversary. For example, an adversary having the read access to the communication channel between the prover and the verifier is more powerful and has a larger VIEW compared to an adversary who would just believe a verifier based on the Transcript that the verifier gives to the prover. We classify that an adversary could be: 1. Online/Offline: An adversary is called Online if it concurrently interacts with the verifier while he gets some message m authenticated from the prover. If the adversary behaves in an "assign & collect" fashion he is called an Offline Adversary. 4 References [1] M. Naor, O. Reingold Number Theoritic Construction of Pseudorandom Generators, FOCS'97. [2] Digital Signets: Self Enforcing Protection of Digital Information, STOC'96. |