Computationally Secure Oblivious Transfer

We describe new computationally secure protocols of 1-out-of-N oblivious transfer, k-out-of-N oblivious transfer, and oblivious transfer with adaptive queries. The protocols are very efficient compared with solutions based on generic two-party computation or on information-theoretic security. The 1-out-of-N oblivious transfer protocol requires only log N executions of a 1-out-of-2 oblivious transfer protocol. The k-out-of-N protocol is considerably more efficient than k repetitions of 1-out-of-N oblivious transfer, as is the construction for oblivious transfer with adaptive queries. The efficiency of the new oblivious transfer protocols makes them useful for many applications. A direct corollary of the 1-out-of-N oblivious transfer protocol is an efficient transformation of any Private Information Retrieval protocol to a Symmetric PIR protocol.     

Verifiable Distributed Oblivious Transfer and Mobile Agent Security

The mobile agent is a fundamental building block of the mobile computing paradigm. In mobile agent security, oblivious transfer (OT) from a trusted party can be used to protect the agent’s privacy and the hosts’ privacy. In this paper, we introduce a new cryptographic primitive called Verifiable Distributed Oblivious Transfer (VDOT), which allows us to replace a single trusted party with a group of threshold trusted servers. The design of VDOT uses a novel technique called consistency verification of encrypted secret shares. VDOT protects the privacy of both the sender and the receiver against malicious attacks of the servers. We also show the design of a system to apply VDOT to protect the privacy of mobile agents. Our design partitions an agent into the general portion and the security-sensitive portion. We also implement the key components of our system. As far as we know, this is the first effort to implement a system that protects the privacy of mobile agents. Our preliminary evaluation shows that protecting mobile agents not only is possible, but also can be implemented efficiently. This work was supported in part by the DoD University Research Initiative (URI) program administered by the Office of Naval Research under grant N00014-01-1-0795. Sheng Zhong was supported by ONR grant N00014-01-1-0795 and NSF grants ANI-0207399 and CCR-TC-0208972. Yang Richard Yang was supported in part by NSF grant ANI-0207399. A preliminary version of this paper was presented at the DialM-POMC Joint Workshop on Foundations of Mobile Computing in 2003. Sheng Zhong received his Ph.D. in computer science from Yale University in the year of 2004. He holds an assistant professor position at SUNY Buffalo and is currently on leave for postdoctoral research at the Center for Discrete Mathematics and Theoretical Computer Science (DIMACS). His research interests, on the practical side, are security and incentives in data mining, databases, and wireless networks. On the theoretical side, he is interested in cryptography and game theory. Yang Richard Yang is an Assistant Professor of Computer Science at Yale University. His research interests include computer networks, mobile computing, wireless networking, sensor networks, and network security. He leads the LAboratory of Networked Systems (LANS) at Yale. His recent awards include a Schlumberger Fellowship and a CAREER Award from the National Science Foundation. He received his B.E. degree from Tsinghua University (1993), and his M.S. and Ph.D. degrees from the University of Texas at Austin (1998 and 2001).     

Linking information reconciliation and privacy amplification

Information reconciliation allows two parties knowing correlated random variables, such as a noisy version of the partner's random bit string, to agree on a shared string. Privacy amplification allows two parties sharing a partially secret string about which an opponent has some partial information, to distill a shorter but almost completely secret key by communicating only over an insecure channel, as long as an upper bound on the opponent’s knowledge about the string is known. The relation between these two techniques has not been well understood. In particular, it is important to understand the effect of side-information, obtained by the opponent through an initial reconciliation step, on the size of the secret key that can be distilled safely by subsequent privacy amplification. The purpose of this paper is to provide the missing link between these techniques by presenting bounds on the reduction of the Rényi entropy of a random variable induced by side-information. We show that, except with negligible probability, each bit of side-information reduces the size of the key that can be safely distilled by at most two bits. Moreover, in the important special case of side-information and raw key data generated by many independent repetitions of a random experiment, each bit of side-information reduces the size of the secret key by only about one bit. The results have applications in unconditionally secure key agreement protocols and in quantum cryptography. This research was supported by the Swiss National Science Foundation. A preliminary version of this paper was presented at Eurocrypt '94, May 9–12, Perugia, Italy.