1
Cryptography miracles, secure auctions, matching problem verification
February 2014
Communications of the ACM: Volume 57 Issue 2, February 2014
Publisher: ACM
Bibliometrics:
Citation Count: 0
Downloads (6 Weeks): 16, Downloads (12 Months): 105, Downloads (Overall): 15,336
Full text available:
Html 
PDF
A solution to the persistent problem of preventing collusion in Vickrey auctions.
2
July 2012
ICALP'12: Proceedings of the 39th international colloquium conference on Automata, Languages, and Programming - Volume Part I
Publisher: Springer-Verlag
Zero Knowledge Proofs (ZKPs) are one of the most striking innovations in theoretical computer science. In practice, the prevalent ZKP methods are, at times, too complicated to be useful for real-life applications. In this paper we present a practically efficient method for ZKPs which has a wide range applications. Specifically, ...
3
Never too early to begin: computer science for high-school students
Michael O. Rabin
July 2012
ITiCSE '12: Proceedings of the 17th ACM annual conference on Innovation and technology in computer science education
Publisher: ACM
Bibliometrics:
Citation Count: 0
Downloads (6 Weeks): 6, Downloads (12 Months): 57, Downloads (Overall): 216
Full text available:
PDF
Computer science and technology innovated over the past sixty years, have revolutionized science, the economy and societal interactions. Inherently CS constitutes a new science combining mathematics, logic, information theory and electronics, on par with physics, chemistry and the life sciences. It is appropriate to educate students in the fundamentals of ...
Keywords:
high school education
4
Cryptographic Combinatorial Clock-Proxy Auctions
July 2009
Financial Cryptography and Data Security: 13th International Conference, FC 2009, Accra Beach, Barbados, February 23-26, 2009. Revised Selected Papers
Publisher: Springer-Verlag
We present a cryptographic protocol for conducting efficient, provably correct and secrecy-preserving combinatorial clock-proxy auctions. The "clock phase" functions as a trusted auction despite price discovery: bidders submit encrypted bids, and prove for themselves that they meet activity rules, and can compute total demand and thus verify price increases without ...
5
Practical secrecy-preserving, verifiably correct and trustworthy auctions
November 2008
Electronic Commerce Research and Applications: Volume 7 Issue 3, November, 2008
Publisher: Elsevier Science Publishers B. V.
We present a practical protocol based on homomorphic cryptography for conducting provably fair sealed-bid auctions. The system preserves the secrecy of the bids, even after the announcement of auction results, while also providing for public verifiability of the correctness and trustworthiness of the outcome. No party, including the auctioneer, receives ...
Keywords:
Cryptography, Electronic transactions, Auction theory, Auctions, Security, Cryptographic auctions, E-commerce, Homomorphic cryptography
6
Michael O. Rabin
September 2007
DISC '07: Proceedings of the 21st international symposium on Distributed Computing
Publisher: Springer-Verlag
Encryption is a fundamental building block for computer and communications technologies. Existing encryption methods depend for their security on unproven assumptions. We propose a new model, the Limited Access model for enabling a simple and practical provably unbreakable encryption scheme. A voluntary distributed network of thousands of computers each maintain ...
7
DISC 20th anniversary: invited talk provably unbreakable hyper-encryption using distributed systems
Michael O. Rabin
September 2007
DISC'07: Proceedings of the 21st international conference on Distributed Computing
Publisher: Springer-Verlag
Encryption is a fundamental building block for computer and communications technologies. Existing encryption methods depend for their security on unproven assumptions. We propose a new model, the Limited Access model for enabling a simple and practical provably unbreakable encryption scheme. A voluntary distributed network of thousands of computers each maintain ...
8
Highly Efficient Secrecy-Preserving Proofs of Correctness of Computations and Applications
July 2007
LICS '07: Proceedings of the 22nd Annual IEEE Symposium on Logic in Computer Science
Publisher: IEEE Computer Society
We present a highly efficient method for proving correctness of computations while preserving secrecy of the input values. This is done in an Evaluator-Prover model which can also be realized by a secure processor. We describe an application to secure auctions.
9
Complexity of computations
Michael O. Rabin
January 2007
ACM Turing award lectures
Publisher: ACM
Bibliometrics:
Citation Count: 0
Downloads (6 Weeks): 187, Downloads (12 Months): 871, Downloads (Overall): 1,598
Full text available:
PDF
The framework for research in the theory of complexity of computations is described, emphasizing the interrelation between seemingly diverse problems and methods. Illustrative examples of practical and theoretical significance are given. Directions for new research are discussed.
Keywords:
complexity theory, parsing, complexity of computations, intractable problems, probabilistic algorithms, algebraic complexity
10
Provably unbreakable hyper-encryption using distributed systems
Michael O. Rabin
September 2006
DISC'06: Proceedings of the 20th international conference on Distributed Computing
Publisher: Springer-Verlag
Encryption is a fundamental building block for computer and communications technologies. Existing encryption methods depend for their security on unproven assumptions. We propose a new model, the Limited Access model for enabling a simple and practical provably unbreakable encryption scheme. A voluntary distributed network of thousands of computers each maintain ...
11
Practical secrecy-preserving, verifiably correct and trustworthy auctions
August 2006
ICEC '06: Proceedings of the 8th international conference on Electronic commerce: The new e-commerce: innovations for conquering current barriers, obstacles and limitations to conducting successful business on the internet
Publisher: ACM
Bibliometrics:
Citation Count: 11
Downloads (6 Weeks): 3, Downloads (12 Months): 13, Downloads (Overall): 450
Full text available:
PDF
We present a practical system for conducting sealed-bid auctions that preserves the secrecy of the bids while providing for verifiable correctness and trustworthiness of the auction. The auctioneer must accept all bids submitted and follow the published rules of the auction. No party receives any useful information about bids before ...
12
September 2004
SCN'04: Proceedings of the 4th international conference on Security in Communication Networks
Publisher: Springer-Verlag
We introduce and define the notion of identity-based zero-knowledge , concentrating on the non-interactive setting. In this setting, our notion allows any prover to widely disseminate a proof of a statement while protecting the prover from plagiarism in the following sense: although proofs are transferable (i.e., publicly verifiable), they are ...
13
Zero-Knowledge Sets
October 2003
FOCS '03: Proceedings of the 44th Annual IEEE Symposium on Foundations of Computer Science
Publisher: IEEE Computer Society
We show how a polynomial-time prover can commit to an arbitrary finite set S of strings so that, later on, he can, for any string x, reveal with a proof whether x \in S or x \notin S, without revealing any knowledge beyond the verity of these membership assertions.Our method ...
14
Hyper encryption and everlasting secrets: a survey
Michael O. Rabin
May 2003
CIAC'03: Proceedings of the 5th Italian conference on Algorithms and complexity
Publisher: Springer-Verlag
15
Hyper-Encryption and Everlasting Security
Yan Zong Ding,
Michael O. Rabin
March 2002
STACS '02: Proceedings of the 19th Annual Symposium on Theoretical Aspects of Computer Science
Publisher: Springer-Verlag
We present substantial extensions of works [1], [2], and all previous works, on encryption in the bounded storage model introduced by Maurer in [25]. The major new result is that the sharedsecret key employed by the sender Alice and the receiver Bob can be re-used to send an exponential number ...
16
Linear-Consistency Testing
June 2001
Journal of Computer and System Sciences: Volume 62 Issue 4, June 2001
Publisher: Academic Press, Inc.
We extend the notion of linearity testing to the task of checking linear consistency of multiple functions. Informally, functions are “linear” if their graphs form straight lines on the plane. Two such functions are “consistent” if the lines have the same slope. We propose a variant of a test of ...
17
Michael A. Bender,
Michael O. Rabin
July 2000
SPAA '00: Proceedings of the twelfth annual ACM symposium on Parallel algorithms and architectures
Publisher: ACM
Bibliometrics:
Citation Count: 9
Downloads (6 Weeks): 5, Downloads (12 Months): 26, Downloads (Overall): 513
Full text available:
PDF
We study the problem of executing parallel programs, in particular Cilk programs, on a collection of processors of different speeds. We consider a model in which each processor maintains an estimate of its own speed, where communication between processors has a cost, and where all scheduling must be online. This ...
18
Verifiable Random Functions
October 1999
FOCS '99: Proceedings of the 40th Annual Symposium on Foundations of Computer Science
Publisher: IEEE Computer Society
We efficiently combine unpredictability and verifiability by extending the Goldreich-Goldwasser-Micali construction of pseudorandom functions fs from a secret seed s, so that knowledge of s not only enables one to evaluate fs at any point x, but also to provide an NP-proof that the value fs(x) is indeed correct without ...
Keywords:
pseudorandom functions, RSA, signature schemes
19
Information Theoretically Secure Communication in the Limited Storage Space Model
August 1999
CRYPTO '99: Proceedings of the 19th Annual International Cryptology Conference on Advances in Cryptology
Publisher: Springer-Verlag
We provide a simple secret-key two-party secure communication scheme, which is provably information-theoretically secure in the limited-storage-space model. The limited-storage-space model postulates an eavesdropper who can execute arbitrarily complex computations, and is only limited in the total amount of storage space (not computation space) available to him. The bound on ...
20
Linear Consistency Testing
August 1999
RANDOM-APPROX '99: Proceedings of the Third International Workshop on Approximation Algorithms for Combinatorial Optimization Problems: Randomization, Approximation, and Combinatorial Algorithms and Techniques
Publisher: Springer-Verlag
seas.harvard.edu
Author only
