Person: Rabin, Michael
Loading...
Email Address
AA Acceptance Date
Birth Date
Research Projects
Organizational Units
Job Title
Last Name
Rabin
First Name
Michael
Name
Rabin, Michael
6 results
Search Results
Now showing 1 - 6 of 6
Publication Selecting Closest Vectors Through Randomization(2000) Bosley, Carl; Rabin, MichaelWe consider the problem of finding the closest vectors to a given vector in a large set of vectors, and propose a randomized solution. The method has applications in Automatic Target Recognition (ATR), Web Information Retrieval, and Data Mining.Publication Time-Lapse Cryptography(2006) Rabin, Michael; Thorpe, Christopher AndrewThe notion of “sending a secret message to the future” has been around for over a decade. Despite this, no solution to this problem is in common use, or even attained widespread acceptance as a fundamental cryptographic primitive. We name, construct and specify an implementation for this new cryptographic primitive, “Time-Lapse Cryptography”, with which a sender can encrypt a message so that it is guaranteed to be revealed at an exact moment in the future, even if this revelation turns out to be undesirable to the sender. Our solution combines new ideas with Pedersen distributed key generation, Feldman verifiable threshold secret sharing, and ElGamal encryption, all of which rest upon the single, broadly accepted Decisional Diffie-Hellman assumption. We develop a Time-Lapse Cryptography Service (“the Service”) based on a network of parties who jointly perform the service. The protocol is practical and secure: at a given time T the Service publishes a public key so that anyone can use it, even anonymously. Senders encrypt their messages with this public key whose private key is not known to anyone – not even a trusted third party – until a predefined and specific future time T + δ, at which point the private key is constructed and published. At or after that time, anyone can decrypt the ciphertext using this private key. The Service is envisioned as a public utility publishing a continuous stream of encryption keys and subsequent corresponding time-lapse decryption keys. We complement our theoretical foundation with descriptions of specific attacks and defenses, and describe important applications of our service in sealed bid auctions, insider stock sales, clinical trials, and electronic voting.Publication Cryptographic Combinatorial Clock-Proxy Auctions(Springer Verlag, 2009) Parkes, David; Rabin, Michael; Thorpe, Christopher AndrewWe 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 revealing any information about individual demands. In the sealed-bid "proxy phase", all bids are revealed the auctioneer via time-lapse cryptography and a branch-and-bound algorithm is used to solve the winner-determination problem. Homomorphic encryption is used to prove the correctness of the solution, and establishes the correctness of the solution to any interested party. Still an NP-hard optimization problem, the use of homomorphic encryption imposes additional computational time on winner-determination that is linear in the size of the branch-and-bound search tree, and thus roughly linear in the original (search-based) computational time. The result is a solution that avoids, in the usual case, the exponential complexity of previous cryptographically-secure combinatorial auctions.Publication Verifiable Random Functions(IEEE Computer Society Press, 1999) Micali, Silvio; Rabin, Michael; Vadhan, SalilWe efficiently combine unpredictability and verifiability by extending the Goldreich-Goldwasser-Micali notion of pseudorandom functions \(f_s\) from a secret seed s, so that knowledge of \(s\) not only enables one to evaluate \(f_s\) at any point x, but also to provide an NP-proof that the value \(f{_s}(x)\) is indeed correct without compromising the unpredictability of \(f_s\) at any other point for which no such a proof was provided.Publication Practical secrecy-preserving, verifiably correct and trustworthy auctions(Elsevier, 2008) Parkes, David; Rabin, Michael; Shieber, Stuart; Thorpe, ChristopherWe 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 any information about bids before the auction closes, and no bidder is able to change or repudiate any bid. The system is illustrated through application to first-price, uniform-price and second-price auctions, including multi-item auctions. Empirical results based on an analysis of a prototype demonstrate the practicality of our protocol for real-world applications.Publication Practical secrecy-preserving, verifiably correct and trustworthy auctions.(Association for Computing Machinery, 2006) Parkes, David; Rabin, Michael; Goodridge, Andrew; Thorpe, ChristopherWe 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 the auction closes and no bidder is able to change or repudiate her bid. Our solution uses Paillier's homomorphic encryption scheme [25] for zero knowledge proofs of correctness. Only minimal cryptographic technology is required of bidders; instead of employing complex interactive protocols or multi-party computation, the single auctioneer computes optimal auction results and publishes proofs of the results' correctness. Any party can check these proofs of correctness via publicly verifiable computations on encrypted bids. The system is illustrated through application to first-price, uniform-price and second-price auctions, including multi-item auctions. Our empirical results demonstrate the practicality of our method: auctions with hundreds of bidders are within reach of a single PC, while a modest distributed computing network can accommodate auctions with thousands of bids.