Cryptography from Anonymity

Berkeley, California October 21-October 24

DOI Bookmark:

http://doi.ieeecomputersociety.org/10.1109/FOCS.2006.25

47th Annual IEEE Symposium on Foundat ...

	This Article
	PURCHASE ARTICLE: $19 PDF HTML IEEE Xplore Subscribers
	Share
	Email this Article to a friend
	Bibliographic References
	ASCII Text BibTex RefWorks Procite/RefMan/Endnote
	Add to:
	Digg Furl Spurl Blink Simpy Google Del.icio.us Y!MyWeb
	Search
	Similar Articles Articles by Yuval Ishai Articles by Eyal Kushilevitz Articles by Rafail Ostrovsky Articles by Amit Sahai

	ASCII Text	x
	Yuval Ishai, Eyal Kushilevitz, Rafail Ostrovsky, Amit Sahai, "Cryptography from Anonymity," Foundations of Computer Science, Annual IEEE Symposium on, pp. 239-248, 47th Annual IEEE Symposium on Foundations of Computer Science (FOCS'06), 2006.

	BibTex	x
	@article{ 10.1109/FOCS.2006.25, author = {Yuval Ishai and Eyal Kushilevitz and Rafail Ostrovsky and Amit Sahai}, title = {Cryptography from Anonymity}, journal ={Foundations of Computer Science, Annual IEEE Symposium on}, volume = {0}, year = {2006}, issn = {0272-5428}, pages = {239-248}, doi = {http://doi.ieeecomputersociety.org/10.1109/FOCS.2006.25}, publisher = {IEEE Computer Society}, address = {Los Alamitos, CA, USA}, }

	RefWorks Procite/RefMan/Endnote	x
	TY - CONF JO - Foundations of Computer Science, Annual IEEE Symposium on TI - Cryptography from Anonymity SN - 0272-5428 SP239 EP248 A1 - Yuval Ishai, A1 - Eyal Kushilevitz, A1 - Rafail Ostrovsky, A1 - Amit Sahai, PY - 2006 KW - null VL - 0 JA - Foundations of Computer Science, Annual IEEE Symposium on ER -

Yuval Ishai, Technion, Israel

Eyal Kushilevitz, Technion, Israel

Rafail Ostrovsky, UCLA, USA

Amit Sahai, UCLA, USA

There is a vast body of work on implementing anonymous communication. In this paper, we study the possibility of using anonymous communication as a building block, and show that one can leverage on anonymity in a variety of cryptographic contexts. Our results go in two directions.

--Feasibility. We show that anonymous communication over insecure channels can be used to implement unconditionally secure point-to-point channels, broadcast, and generalmulti-party protocols that remain unconditionally secure as long as less than half of the players are maliciously corrupted.

--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 both communication and computation.

Citation:

Yuval Ishai, Eyal Kushilevitz, Rafail Ostrovsky, Amit Sahai, "Cryptography from Anonymity," focs, pp.239-248, 47th Annual IEEE Symposium on Foundations of Computer Science (FOCS'06), 2006

Peer Review Notice | Give Us Feedback

Usage of this product signifies your acceptance of the Terms of Use.