Cryptography from Anonymity
- 1 January 2006
- conference paper
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- Vol. 2006, 239-248
- https://doi.org/10.1109/focs.2006.25
Abstract
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. middot Feasibility. We show that anonymous communication over insecure channels can be used to implement unconditionally secure point-to-point channels, broadcast, and general multi-party protocols that remain unconditionally secure as long as less than half of the players are maliciously corrupted. middot 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 computationKeywords
This publication has 29 references indexed in Scilit:
- Completeness in Two-Party Secure Computation: A Computational ViewJournal of Cryptology, 2006
- Explicit capacity-achieving list-decodable codesPublished by Association for Computing Machinery (ACM) ,2006
- Correcting Errors Beyond the Guruswami-Sudan Radius in Polynomial TimePublished by Institute of Electrical and Electronics Engineers (IEEE) ,2005
- Basing Cryptographic Protocols on Tamper-Evident SealsLecture Notes in Computer Science, 2005
- Foundations of CryptographyPublished by Cambridge University Press (CUP) ,2004
- Replication is not needed: single database, computationally-private information retrievalPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2002
- Secure Games with Polynomial ExpressionsLecture Notes in Computer Science, 2001
- Reducibility and Completeness in Private ComputationsSIAM Journal on Computing, 2000
- Efficient Cryptographic Schemes Provably as Secure as Subset SumJournal of Cryptology, 1996
- Secret key agreement by public discussion from common informationIEEE Transactions on Information Theory, 1993