Paper 2006/084

Cryptography from Anonymity

Yuval Ishai, Eyal Kushilevitz, Rafail Ostrovsky, and Amit Sahai


There is a vast body of work on {\em implementing} anonymous communication. In this paper, we study the possibility of using anonymous communication as a {\em building block}, and show that one can leverage on anonymity in a variety of cryptographic contexts. Our results go in two directions. \begin{itemize} \item{\bf Feasibility.} We show that anonymous communication over {\em insecure} channels can be used to implement unconditionally secure point-to-point channels, and hence general multi-party protocols with unconditional security in the presence of an honest majority. In contrast, anonymity cannot be generally used to obtain unconditional security when there is no honest majority. \item{\bf Efficiency.} We show that anonymous channels can yield substantial efficiency improvements for several natural secure computation tasks. In particular, we present the first solution to the problem of private information retrieval (PIR) which can handle multiple users while being close to optimal with respect to {\em both} communication and computation. A key observation that underlies these results is that {\em local randomization} of inputs, via secret-sharing, when combined with the {\em global mixing} of the shares, provided by anonymity, allows to carry out useful computations on the inputs while keeping the inputs private. \end{itemize}

Available format(s)
Publication info
Published elsewhere. FOCS 2006
Contact author(s)
yuvali @ cs technion ac il
2006-11-06: revised
2006-03-06: received
See all versions
Short URL
Creative Commons Attribution


      author = {Yuval Ishai and Eyal Kushilevitz and Rafail Ostrovsky and Amit Sahai},
      title = {Cryptography from Anonymity},
      howpublished = {Cryptology ePrint Archive, Paper 2006/084},
      year = {2006},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.