[Resource Topic] 2006/084: Cryptography from Anonymity

Welcome to the resource topic for 2006/084

Cryptography from Anonymity

Authors: Yuval Ishai, Eyal Kushilevitz, Rafail Ostrovsky, 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.
\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.

ePrint: https://eprint.iacr.org/2006/084

See all topics related to this paper.

Feel free to post resources that are related to this paper below.

Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.

For more information, see the rules for Resource Topics .