David Chaum, Richard Carback, Jeremy Clark Aleks, Er Essex, Stefan Popoveniuc, Ronald L. Rivest, ...
We introduce Scantegrity II, a practical enhancement for optical scan voting systems that achieves increased election integrity through the novel use of confirmation codes printed on ballots in...
Abstract On Auditing Elections When Precincts Have Different Sizes (2009)
Javed A. Aslam, Raluca A. Popa, Ronald L. Rivest
We address the problem of auditing an election when precincts may have different sizes. Prior work in this field has emphasized the simpler case when all precincts have the same size. Using auditing...
[DB03] Datamation Benchmark. Sort Benchmark Home Page, hosted by Microsoft. (2008)
Acv Rajiv Wickremesinghe, Lars Arge, Jeff Chase, S. Vitter, ...
[AV88] ALOK AGGARWAL AND JEFFERY S. VITTER. The input/output complexity of sorting and related problems. Communications of the ACM, 1988.
Abstract On Auditing Elections When Precincts Have Different Sizes (2008)
Javed A. Aslam, Raluca A. Popa, Ronald L. Rivest
We address the problem of auditing an election when precincts may have different sizes. Prior work in this field has emphasized the simpler case when all precincts have the same size. Using auditing...
Piecemeal Graph Exploration by a Mobile Robot (2008)
Baruch Awerbuchy, Margrit Betke, Ronald L. Rivest, Mona Singh
Abstract We study how a mobile robot can piecemeal learn an unknown environment. The robot's goal is to learn a complete map of its environment, while satisfying the constraint that it must...
Programming G. Manacher Techniques Editor Expected Time Bounds for Selection (2008)
Robert W. Floyd, Ronald L. Rivest
A new selection algorithm is presented which is shown to be very efficient on the average, both theo-retically and practically. The number of comparisons used to select the ith smallest of n numbers...
(Extended Abstract) Abstract (2008)
Ronald L. Rivest, Robert Sloan L
We introduce a new model for inductive inference, by combining a Bayesian approach for representing the current state of knowledge with a simple model for the computational cost of making predictions...
Thomas H. Corman, Charles E. Leiserson, Ronald L. Rivest, Introduction To
asymptotic notation with several parameters – conditional asymptotic notation – amortized analysis – NPcompleteness – NP-hard – recurrence equations – solving recurrence equations –...
[13] Marshall Berman, All That is Solid Melts Into Air, (2008)
Patrick Ball, Paul Kobrak, Herbert F. Spirer, Henry Campbell Black, Joseph R. Nolan, ...
people/pagre/rre.html}
Processing Letters, 18(3):147–150, 1984. (2008)
Ab Sanjeev Arora, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein, Introduction Algorithms, ...
modern approach. Initial draft kindly placed by the authors on the web, 2006. [AGP94] W. R. Alford, A. Granville, and C. Pomerance. There are infinitely many Carmichael numbers. Annals of Mathematics,
Pseudonym Systems (Extended Abstract) (2008)
Anna Lysyanskaya, Ronald L. Rivest, Amit Sahai, Stefan Wolf
Abstract. Pseudonym systems allow users to interact with multiple organizations anonymously, using pseudonyms. The pseudonyms cannot be linked, but are formed in such a way that a user can prove to...
Permutation polynomials modulo 2 w (2008)
Wegive an exact characterization of permutation polynomials modulo n =2 w, w 2: a polynomial P (x) =a0 + a1x + + adx d with integral coe cients is a permutation polynomial modulo n if and only if a1...
Pseudonym Systems (Extended Abstract) (2008)
Anna Lysyanskaya, Ronald L. Rivest, Amit Sahai, Stefan Wolf
Anonymity and pseudonymity are fascinating and challenging, both technically--can we achieve them?--and socially--do we want them? We focus on technical feasibility, referring the reader in the...
Brian Borchers, Jan Korst, Simulated Annealing, Thomas L. Magnanti, As Noga Alon, ...
I've compiled this list of books on combinatorial optimization and integer programming as a source of additional reading and project ideas for students in my graduate course in combinatorial...
Pseudonym Systems (Extended Abstract) (2008)
Anna Lysyanskaya, Ronald L. Rivest, Amit Sahai, Stefan Wolf
Anonymity and pseudonymity are fascinating and challenging, both technically--can we achieve them?--and socially--do we want them? We focus on technical feasibility, referring the reader in the...
Pseudonym Systems (Extended Abstract) (2008)
Anna Lysyanskaya, Ronald L. Rivest, Amit Sahai, Stefan Wolf
Anonymity and pseudonymity are fascinating and challenging, both technically--can we achieve them?--and socially--do we want them? We focus on technical feasibility, referring the reader in the...
On auditing elections when precincts have different sizes (2008)
Javed A. Aslam, Raluca A. Popa, Ronald L. Rivest
We address the problem of auditing an election when precincts may have different sizes. Prior work in this field has emphasized the simpler case when all precincts have the same size. Using auditing...
The MD6 hash function A proposal to NIST for SHA-3 (2008)
Ronald L. Rivest, Benjamin Agre, Daniel V. Bailey, Christopher Crutchfield, Yevgeniy Dodis, Kermin Elliott, ...
This report describes and analyzes the MD6 hash function and is part of our submission package for MD6 as an entry in the NIST SHA-3 hash function competition 1. Significant features of MD6 include:...
A “sum of square roots” (SSR) pseudorandom sampling method for election audits (2008)
This note proposes a cute little heuristic method of generating a uniformly distributed pseudo-random number between 0 and 1 for each precinct in an election, for use in selecting a sample of...
Christopher Yale Crutchfield, Ronald L. Rivest, Terry P. Orlando, Christopher Yale Crutchfield
In recent years there have been a series of serious and alarming cryptanalytic attacks on several commonly-used hash functions, such as MD4, MD5, SHA-0, and SHA-1 [13, 38]. These culminated with the...
07311 Executive Summary -- Frontiers of Electronic Voting (2008)
Chaum, David, Kutylowski, Miroslaw, Rivest, Ronald L., Ryan, Peter Y. A.
This is a short report on Dagstuhl Seminar 07311 - Frontiers of Electronic Voting, 29.07.07 - 03.08.07, organized in The International Conference and Research Center for Computer Science (IBFI,...
07311 Abstracts Collection -- Frontiers of Electronic Voting (2008)
Chaum, David, Kutylowski, Miroslaw, Rivest, Ronald L., Ryan, Peter Y. A.
From July the 29th to August the 3th, 2007, the Dagstuhl Seminar 07311 ``Frontiers of Electronic Voting'' was held in the International Conference and Research Center (IBFI), Schloss Dagstuhl. During...
Piecemeal Graph Exploration byaMobile Robot (2007)
Baruchawerbuch Margrit Betke, Baruch Awerbuch, Margrit Betke, Ronald L. Rivest, Mona Singh
We study how a mobile robot can piecemeal learn an unknown environment. The robot's goal is to learn a complete map of its environment, while satisfying the constraint that it must return every...
Piecemeal Graph Exploration by a Mobile Robot (Extended Abstract) (2007)
Baruch Awerbuch, Margrit Betke, Ronald L. Rivest, Mona Singh
) Baruch Awerbuch y Margrit Betke Ronald L. Rivest Mona Singh Laboratory for Computer Science Massachusetts Institute of Technology Cambridge, MA 02139 Abstract We study the problem of learning a...
Hidden State and Short-Term Memory: A Bibliography (2007)
Michael C. Mozer, L. Christman, John N. Tsitsiklis, The Markov, ...
sium on Theory of Computing, pages 411--420, Seattle, Washington, May 1989. [ Ross, 1970 ] S. Ross. Applied Probability Models with Optimization Applications. Holden-Day, San Francisco, Calif., 1970....
Stephen A. Weis, Sanjay E. Sarma, Ronald L. Rivest, Daniel W. Engels
Abstract. Like many technologies, low-cost Radio Frequency Identification (RFID) systems will become pervasive in our daily lives when affixed to everyday consumer items as "smart...
Proactive Secret Sharing and Public Key (2007)
Stanislaw Jarecki, C Fls Jarecki, Ronald L. Rivest
by
Piecemeal Graph Exploration by aMobile Robot (2007)
Baruch Awerbuch, Margrit Betke, Ronald L. Rivest, Mona Singh
We study how a mobile robot can piecemeal learn an unknown environment. The robot's goal is to learn a complete map of its environment, while satisfying the constraint that it must return every...
Ronald L. Rivest, Javed Alexander Aslam, Javed Alexander Aslam
We consider the problem of developing robust algorithms which cope with noisy data. In the Probably Approximately Correct model of machine learning, we develop a general technique which allows nearly...
Laved Alexander Aslam, Ronald L. Rivest, R. Morgenthaler, Javed Alexander Aslam
We consider the problem of developing robust algorithms which cope with noisy data. In the Probably Approximately Correct model of machine learning, we develop a general technique which allows nearly...
Ronald L. Rivest, Frederic R. Morgenthaler, Mona Singh, Mona Singh
of Philosophy We consider three problems in machine learning: ffl concept learning in the PAC model ffl mobile robot environment learning ffl learning-based approaches to protein structure prediction...
Algorithms for Exploring an Unknown Graph (2007)
An Unknown Graph, Margrit Betke, Margrit Betke, Ronald L. Rivest
We consider the problem of exploring an unknown strongly connected directed graph. We use the exploration model introduced by Deng and Papadimitriou [DP90]. An explorer follows the edges of an...
Jorge Nakahara, Ronald L. Rivest
The purpose of this document is to give a statistical evaluation of the NESSIE submission RC6. For this evaluation, we follow the recommendations of the NESSIE statistical evaluation process for...
Ronald L. Rivest, Anna Lysyanskaya, Anna Lysyanskaya
Signature schemes are fundamental cryptographic primitives, useful as a stand-alone application, and as a building block in the design of secure protocols and other cryptographic objects. In this...
Certi cate Chain Discovery in SPKI/SDSI (2007)
Dwaine Clarke, Jean-emile Elien, Carl Ellison, Matt Fredette, Alexander Morcos, Ronald L. Rivest
SPKI/SDSI is a novel public-key infrastructure emphasizing naming, groups, ease-of-use, and exible authorization. To access a protected resource, a client must present to the server a proof that the...
Ronald L. Rivest, Robert Sloan
We introduce a model of inductive inference, or learning, that extends the conventional Bayesian approach by explicitly considering the computational cost of formulating predictions to be tested. We...
Block Cipher, Scott Contini, Ronald L. Rivest, Yiqun Lisa Yin
This report presents a preliminary analysis of the security offered by the RC6 TM block cipher. RC6 is an evolutionary improvement of RC5, designed to meet the requirements of the Advanced Encryption...
Ronald L. Rivest, Mojdeh Mohtashemi, Mojdeh Mohtashemi
Data-compression techniques such as Huffman coding are often used in conjunction with cryptographic schemes. By removing redundancy in the source document, they can significantly increase the...
Benjamin Adida, Ronald L. Rivest
There are few end-users today who make use of real security applications. These applications tend to be too complicated, exposing too much detail of the cryptographic process. Users need simple,...
Ronald L. Rivest, Arthur C. Smith, Jeffrey Burstein, Jeffrey Burstein
This thesis describes a prototype implementation of MicroMint, an Internet micropayment system designed to facilitate very small scale monetary transactions over the World Wide Web. By implementing a...
Scott Contini, Ronald L. Rivest, Yiqun Lisa Yin
Abstract. RC6 has been submitted as a candidate for the Advanced Encryption Standard (AES). Two important features of RC6 that were absent from its predecessor RC5 are a quadratic function and a...
Ronald L. Rivest, Robert E. Schapire
We present new procedures for inferring the structure of a finite-state automaton (FSA) from its input/output behavior, using access to the automaton to perform experiments. Our procedures use a new...
Block Cipher, Scott Contini, Ronald L. Rivest, Yiqun Lisa Yin
This report presents a preliminary analysis of the security offered by the RC6 TM block cipher. RC6 is an evolutionary improvement of RC5, designed to meet the requirements of the Advanced Encryption...
Permutation polynomials modulo 2 w (2007)
We give an exact characterization of permutation polynomials modulo n = 2 w
Making Maximum Entropy Computations Easier By Adding Extra Constraints (Extended Abstract) (2007)
Sally A. Goldman, Ronald L. Rivest
This paper presents a new way to compute the probability distribution with maximum entropy satisfying a set of constraints. Unlike previous approaches, our method is integrated with the planning of...
Picking the Best Expert from a Sequence (2007)
Ruth Bergman, Ronald L. Rivest
We examine the problem of finding a good expert from a sequence of experts. Each expert has an "error rate"; we wish to find an expert with a low error rate. However, each...
Ronald L. Rivest, Yiqun Lisa Yin
After more than a year of design and nearly two years of scrutiny, the process to choose the Advanced Encryption Standard is drawing to a close. We are now left with ve designs that would each be...
We address the problem of auditing an election when precincts may have different sizes, and suggest methods for picking a sample of precincts to audit that precinct size into account. One method...
Three Voting Protocols: ThreeBallot, VAV, and Twin (2007)
Ronald L. Rivest, Warren D. Smith
We present three new paper-based voting methods with interesting security properties. Our goal is to achieve the same security properties as recently proposed cryptographic voting protocols, but...
A simple rule of thumb for election audit size determination (2007)
This note proposes a very simple “Rule of Thumb ” for determining how many precincts to audit in a postelection audit. This rule says to audit
Three Voting Protocols: ThreeBallot, VAV, and Twin (2007)
Ronald L. Rivest, Warren D. Smith
We present three new paper-based voting methods with interesting security properties. Our goal is to achieve the same security properties as recently proposed cryptographic voting protocols, but...
How to leak a secret: Theory and applications of ring signatures (2006)
Ronald L. Rivest, Adi Shamir, Yael Tauman
Abstract. In this work we formalize the notion of a ring signature, which makes it possible to specify a set of possible signers without revealing which member actually produced the signature. Unlike...
On the notion of “software independence” in voting systems (2006)
Ronald L. Rivest, John P. Wack
Abstract. This paper defines and explores the notion of “software independence” in voting systems: A voting system is software-independent if an undetected change or error in its software cannot...
Lightweight Email Signatures (2006)
Ben Adida, David Chau, Susan Hohenberger, Ronald L. Rivest
We present Lightweight Email Signatures (LES), a simple cryptographic architecture for authenticating email. LES is an extension of DKIM, the recent IETF effort to standardize domain-based email...
Advances in Cryptographic Voting Systems (2006)
Ronald L. Rivest, Arthur C. Smith, Ben Adida, Ben Adida
depends on the proper administration of popular elections. Voters should receive assurance that their intent was correctly captured and that all eligible votes were correctly tallied. The election...
Cryptography, and Private Disjointness Testing (2006)
Stephen A. Weis, Ronald L. Rivest, Stephen A. Weis
This dissertation presents new constructions and security definitions related to three areas: authentication, cascadable and commutative crytpography, and private set operations. Existing works...
Abstract The ThreeBallot Voting System (2006)
We present a new paper-based voting method with interesting security properties. The attempt here is to see if one can achieve the same security properties of recently proposed cryptographic voting...
On estimating the size of a statistical audit (2006)
We develop a remarkably simple and easily-calculated estimate for the sample size necessary for determining whether a given set of n objects contains b or more “bad ” objects: n(1 −...
Lightweight email signatures (extended abstract (2006)
Ben Adida, David Chau, Susan Hohenberger, Ronald L. Rivest
Abstract. We present Lightweight Email Signatures (LES), a simple cryptographic architecture for authenticating email. LES is an extension of DKIM, the recent IETF effort to standardize domain-based...
Fourth factor authentication: Somebody you know (2006)
John Brainard, Michael Szydlo, Ari Juels, Moti Yung, Ronald L. Rivest
User authentication in computing systems traditionally depends on three factors: something you have (e.g., a hardware token), something you are (e.g., a fingerprint), and something you know (e.g., a...
Advances in Cryptographic Voting Systems (2006)
Ronald L. Rivest, Arthur C. Smith, Ben Adida, Ben Adida, Ben Adida
elections
On the Security of the EMV Secure Messaging API (2005)
Ben Adida, Mike Bond, Jolyon Clulow, Amerson Lin, Ross Anderson, Ronald L. Rivest
We present new attacks against the EMV financial transaction security system (known in Europe as “Chip and PIN”), specifically on the back-end API support for sending secure messages to EMV...
Fighting Phishing Attacks: A Lightweight Trust Architecture for Detecting Spoofed Emails (2005)
Ben Adida, Susan Hohenberger, Ronald L. Rivest
We present a novel key distribution architecture and a novel use of a particular identity-based digital signature scheme for making email trustworthy. Like typical digital signatures, our solution...
Automated analysis of security APIs (2005)
Amerson H. Lin, Ronald L. Rivest, Amerson H. Lin
Attacks on security systems within the past decade have revealed that security Application Programming Interfaces (APIs) expose a large and real attack surface but remain to be a relatively...
Robbing the bank with a theorem prover (2005)
C Paul Youn, Paul Youn, Paul Youn, Ben Adida, Ben Adida, Ben Adida, ...
Number 644
On Symbolic Analysis of Cryptographic Protocols. Master of engineering thesis (2005)
Ronald L. Rivest, Ran Canetti, Arthur C. Smith, Akshay Patil, Akshay Patil
Accepted by.............................................................. (2005)
Kevin E. Fu, M. Frans Kaashoek, Ronald L. Rivest, Arthur C. Smith, Kevin E. Fu
Integrity and access control in untrusted content distribution networks by
Certified by.......................................................... (2005)
Amerson H. Lin, Ronald L. Rivest, Amerson H. Lin
Attacks on security systems within the past decade have revealed that security Application Programming Interfaces (APIs) expose a large and real attack surface but remain to be a relatively...
Lightweight signatures for email (2005)
Ben Adida, David Chau, Susan Hohenberger, Ronald L. Rivest
We present the design and prototype implementation of a new public key infrastucture for email authentication. Our approach applies recent developments in identity-based cryptography and observations...
Joy Marie Forsythe, Ronald L. Rivest, Joy Marie Forsythe
Voters are now demanding the ability to verify that their votes are cast and counted as intended. Most existing cryptographic election protocols do not treat the voter as a computationally-limited...
Composability Framework (2005)
David A. Wilson, Ronald L. Rivest, David A. Wilson
This thesis introduces models for error-prone communication channels and functionalities for error-free communication in the Universal Composability framework. Realizing these functionalities enables...
Preliminary Voting — Prevoting (2005)
We introduce the notion of preliminary voting, or pre-voting, wherein a voter deposits—perhaps over the Internet—a preliminary vote or prevote with election authorities at some time before the...
Ben Adida, Susan Hohenberger, Ronald L. Rivest
Ad-hoc-group signatures enable an individual to sign on behalf of a group without requiring prior group membership setup. Such signatures are used to provide credibility – the signer must be one of...
Ben Adida, Susan Hohenberger, Ronald L. Rivest
Email phishing attacks are one of today’s most common and costly forms of digital identity theft, where an adversary tricks a user into revealing their personal information by impersonating an...
On the notion of pseudo-free groups (2004)
Abstract. We explore the notion of a pseudo-free group, first introduced by Hohenberger [Hoh03], and provide an alternative stronger definition. We show that if Z # n is a pseudo-free abelian group...
Peppercoin Micropayments (2004)
Ronald Rivest Computer, Ronald L. Rivest
We present the "Peppercoin" method for processing micropayments e#ciently. With this method, a fraction of the micropayments received are determined, via a procedure known as...
On the notion of pseudo-free groups (2004)
Abstract. We explore the notion of a pseudo-free group, first introduced by Hohenberger [Hoh03], and provide an alternative stronger definition. We show that if Z ∗ n is a pseudo-free abelian group...
Peppercoin micropayments (2004)
Abstract. We present the “Peppercoin ” method for processing micropayments efficiently. With this method, a fraction of the micropayments received are determined, via a procedure known as...
Peppercoin micropayments (2004)
Abstract. We present the “Peppercoin ” method for processing micropayments efficiently. With this method, a fraction of the micropayments received are determined, via a procedure known as...
Security and privacy aspects of low-cost radio frequency identification systems (2003)
Stephen A. Weis, Sanjay E. Sarma, Ronald L. Rivest, Daniel W. Engels
Abstract. Like many technologies, low-cost Radio Frequency Identification (RFID) systems will become pervasive in our daily lives when affixed to everyday consumer items as “smart labels”. While...
Security and privacy aspects of low-cost radio frequency identification systems (2003)
Stephen A. Weis, Sanjay E. Sarma, Ronald L. Rivest, Daniel W. Engels
Abstract. Like many technologies, low-cost Radio Frequency Identification (RFID) systems will become pervasive in our daily lives when affixed to everyday consumer items as “smart labels”. While...
Security and privacy aspects of low-cost radio frequency identification systems (2003)
Stephen A. Weis, Sanjay E. Sarma, Ronald L. Rivest, Daniel W. Engels
Abstract. Like many technologies, low-cost Radio Frequency Identification (RFID) systems will become pervasive in our daily lives when affixed to everyday consumer items as “smart labels”. While...
and Trusted Third-Party Encryption. A Report by an Ad Hoc Group of Cryptographers (2003)
Prepared Erik Wilde, Harold Abelson, Ross Anderson, Steven M. Bellovin, Josh Benaloh, Whitfield Diffie, ...
[7] Bernard Aboba and Pat R. Calhoun. RADIUS (Remote Authentication Dial In
The blocker tag: Selective blocking of RFID tags for consumer privacy (2003)
Ari Juels, Ronald L. Rivest, Michael Szydlo
Abstract. We propose the use of “selective blocking ” by “blocker tags ” as a way of protecting consumers from unwanted scanning of RFID tags attached to items they may be carrying or...
Security and privacy aspects of low-cost radio frequency identification systems (2003)
Stephen A. Weis, Sanjay E. Sarma, Ronald L. Rivest, Daniel W. Engels
Abstract. Like many technologies, low-cost Radio Frequency Identification (RFID) systems will become pervasive in our daily lives when affixed to everyday consumer items as “smart labels”. While...
Security and privacy in radio-frequency identification devices (2003)
Ronald L. Rivest, Stephen August Weis, Stephen August Weis
Radio Frequency Identification (RFID) systems are a common and useful tool in manufacturing, supply chain management and retail inventory control. Optical barcodes, another common automatic...
The cryptographic impact of groups with infeasible inversion (2003)
Ronald L. Rivest, Susan Rae Hohenberger, Susan Rae Hohenberger
Master of Science in Computer Science and Engineering Algebraic group structure is an important{and often overlooked{tool for constructing and comparing cryptographic applications. Our driving...
The blocker tag: Selective blocking of RFID tags for consumer privacy (2003)
Ari Juels, Ronald L. Rivest, Michael Szydlo
Abstract. We propose the use of “selective blocking ” by “blocker tags ” as a way of protecting consumers from unwanted scanning of RFID tags attached to items they may be carrying or...
Security and privacy in radio-frequency identification devices (2003)
Ronald L. Rivest, Arthur C. Smith, Stephen August Weis, Stephen August Weis
by
Making mix nets robust for electronic voting by randomized partial checking (2002)
Markus Jakobsson, Ari Juels, Ronald L. Rivest
Symposium
Tweakable block ciphers (2002)
Moses Liskov, Ronald L. Rivest, David Wagner
Abstract. We propose a new cryptographic primitive, the “tweakable block cipher. ” Such a cipher has not only the usual inputs—message and cryptographic key—but also a third input, the...
Making mix nets robust for electronic voting by randomized partial checking (2002)
Markus Jakobsson, Ari Juels, Ronald L. Rivest
We propose a new technique for making mix nets robust, called randomized partial checking (RPC). The basic idea is that rather than providing a proof of completely correct operation, each server...
Micropayments revisited (2002)
Silvio Micali, Ronald L. Rivest
Abstract. We present new micropayment schemes that are more e-cient and user friendly than previous ones. These schemes reduce bank processing costs by several orders of magnitude, while preserving a...
Tweakable block ciphers (2002)
Moses Liskov, Ronald L. Rivest
Abstract. We propose a new cryptographic primitive, the \tweakable block cipher. " Such a cipher has not only the usual inputs|message and cryptographic key|but also a third input, the...
Tweakable block ciphers (2002)
Moses Liskov, Ronald L. Rivest, David Wagner
Abstract. We propose a new cryptographic primitive, the \tweakable block cipher. " Such a cipher has not only the usual inputs|message and cryptographic key|but also a third input, the...
Detection and Recovery from the Oblivious Engineer Attack (2002)
Ronald L. Rivest, Jennifer Joyce Mulligan, Jennifer Joyce Mulligan
Master of Science in Computer Science and Engineering The weak security of the Border Gateway Protocol (BGP) has been a known issue and has had several solutions proposed. The leading solution of the...
Transitive signature schemes (2002)
Silvio Micali, Ronald L. Rivest
{ draft { We consider the problem of nding public-key digital signature schemes with a transitive-closure property for signing the vertices and edges of a (directed or undirected) nite graph. More...
Over the years, with varying degrees of success, inventors have repeatedly tried to adapt the latest technology to the cause of improved voting. For example, on June 1, 1869 Thomas A. Edison received...
Tweakable block ciphers (2002)
Moses Liskov, Ronald L. Rivest, David Wagner
Abstract. We propose a new cryptographic primitive, the “tweakable block cipher. ” Such a cipher has not only the usual inputs—message and cryptographic key—but also a third input, the...
Dijk, Cryptography in an Unbounded Computational Model (2002)
Ronald L. Rivest, David Paul Woodruff, David Paul Woodruff
and
Dijk, Cryptography in an Unbounded Computational Model (2002)
Ronald L. Rivest, David Paul Woodruff, David Paul Woodruff
and
Introduction to Algorithms, second edition (2001)
Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein
Ronald L. Rivest, Adi Shamir, Yael Tauman
Abstract. In this paper we formalize the notion of a ring signature, which makes it possible to specify a set of possible signers without revealing which member actually produced the signature....
Adaptive security in the threshold setting: From cryptosystems to signature schemes (2001)
Ronald L. Rivest, Christopher Jason Peikert, Christopher Jason Peikert
Cryptosystems to Signatures by
Certificate chain discovery in SPKI/SDSI (2001)
Dwaine Clarke, Jean-emile Elien, Carl Ellison, Matt Fredette, Alexander Morcos, Ronald L. Rivest
SPKI/SDSI is a novel public-key infrastructure emphasizing naming, groups, ease-of-use, and flexible authorization. To access a protected resource, a client must present to the server a proof that...
Research in Cryptography, Information Security and Algorithm Development (2001)
Shafi Goldwasser, Ronald L. Rivest, Michael Sipser
Recent NTT-sponsored research has focussed on both introducing new cryptographic primitives and designing secure cryptographic protocols with repsect to existing definitions. The emphasis of the...
Certificate Chain Discovery in SPKI/SDSI (2001)
Dwaine Clarke, Jean-Emile Elien, Carl Ellison, Matt Fredette, Alexander Morcos, Ronald L. Rivest
SPKI/SDSI is a novel public-key infrastructure emphasizing naming, groups, ease-of-use, and flexible authorization. To access a protected resource, a client must present to the server a proof that...
The Case for RC6 as the AES (2000)
Matt Robshaw, Ronald L. Rivest, Y. L. Yin
this document. The more wehavelooked at recent controversial issues, the more wehave found to question. Much is riding on the success of the AES. After such a long time and such an enormous e#ort,...
Textbooks: 1. Introduction to Automata Theory, Languages, and Computation (2000)
Prepared Lesson Plans, John E. Hopcroft, H. Cormen, Charles E. Leiserson, Ronald L. Rivest
Certificate Chain Discovery in SPKI/SDSI (1999)
Ronald L. Rivest, Arthur C. Smith, Dwaine E. Clarke, Dwaine E. Clarke
The issue of trust is of growing importance as our communities become increasingly interconnected. When resources are shared over an untrusted network, how are decisions on which principals are...
Ronald L. Rivest, Anna Lysyanskaya, Anna Lysyanskaya
in partial fulllment of the requirements for the degree of
Group sharing and random access in cryptographic storage file systems (1999)
Ronald L. Rivest, Kevin E. Fu, Kevin E. Fu
Traditional cryptographic storage uses encryption to ensure confidentiality of file data. However, encryption can prevent e#cient random access to file data. Moreover, no cryptographic storage file...
Group blind digital signatures: Theory and applications (1999)
Ronald L. Rivest, Zulfikar Amin Ramzan, Zulfikar Amin Ramzan
In this thesis we introduce a new cryptographic construct called a Group Blind Digital Signature. This construct combines the already existing notions of a Group Digital Signature and a Blind Digital...
Anna Lysyanskaya, Ronald L. Rivest, Amit Sahai
Pseudonym systems allow users to interact with multiple organizations anonymously, using pseudonyms. The pseudonyms cannot be linked, but are formed in such a way that a user can prove to one...
We present a new and very simple commitment scheme that does not depend on any assumptions about computational complexity; the Sender and Receiver may both be computationally unbounded. Instead, the...
Permutation Polynomials Modulo 2^w (1999)
We give an exact characterization of permutation polynomials modulo n = 2 w , w 2: a polynomial P (x) = a 0 + a 1 x + \Delta \Delta \Delta + a d x d with integral coefficients is a permutation...
We present a new and very simple commitment scheme that does not depend on any assumptions about computational complexity � the Sender and Receiver may both be computationally unbounded. Instead,...
Group blind digital signatures: Theory and applications (1999)
Ronald L. Rivest, Arthur C. Smith
Master of Science in Computer Science and Electrical Engineering In this thesis weintroduce a new cryptographic construct called a Group Blind Digital Signature. This construct combines the already...
Improved analysis of some simplified variants of RC6 (1999)
Scott Contini, Ronald L. Rivest, Yiqun Lisa Yin
Abstract. RC6 has been submitted as a candidate for the Advanced Encryption Standard (AES). Two important features of RC6 that were absent from its predecessor RC5 are a quadratic function and a...
Improved analysis of some simplified variants of RC6 (1999)
Scott Contini, Ronald L. Rivest, Yiqun Lisa Yin
Abstract. RC6 has been submitted as a candidate for the Advanced Encryption Standard (AES). Two important features of RC6 that were absent from its predecessor RC5 are a quadratic function and a...
The Security of the RC6 TM Block Cipher (1998)
Scott Contini, Ronald L. Rivest, Yiqun Lisa Yin
This report presents a preliminary analysis of the security o ered by the RC6 TM block cipher. RC6 is an evolutionary improvement ofRC5, designed to meet the requirements of the Advanced Encryption...
Can We Eliminate Certificate Revocation Lists (1998)
Abstract. We briefly consider certificate revocation lists (CRLs), and ask whether they could, and should, be eliminated, in favor of other mechanisms. In most cases, the answer seems to be...
Electronic Lottery Tickets as Micropayments (1998)
We present a new micropayment scheme based on the use of "electronic lottery tickets." This scheme is exceptionally efficient since the bank handles only winning tickets, instead of...
Ronald L. Rivest, R. Sidney, Y. L. Yin
We introduce the RC6 block cipher. RC6 is an evolutionary improvement of RC5, designed to meet the requirements of the Advanced Encryption Standard (AES). Like RC5, RC6 makes essential use of...
A Java Implementation of Simple Distributed Security Infrastructure (1998)
Ronald L. Rivest, Arthur C. Smith, Alexander Morcos, Alexander Morcos
Two Java packages have been written which contain classes to implement S-expressions and Version 2.0 of the Simple Distributed Security Infrastructure (SDSI) specification. Another package has been...
Self-Delegation with Controlled Propagation -- or -- What If You Lose Your Laptop (1998)
Oded Goldreich Birgit, Birgit Pfitzmann, Ronald L. Rivest
We introduce delegation schemes wherein a user may delegate certain rights to himself, but may not safely delegate these rights to others. In our motivating application, a user has a primary...
Self-Delegation with Controlled Propagation - or - What If You Lose Your Laptop (1998)
Oded Goldreich, Birgit Pfitzmann, Ronald L. Rivest
We introduce delegation schemes wherein a user may delegate certain rights to himself, but may not safely delegate these rights to others. In our motivating application, a user has a primary...
Self-Delegation with Controlled Propagation - or - What If You Lose Your Laptop (1998)
Oded Goldreich, Birgit Pfitzmann, Ronald L. Rivest
We introduce delegation schemes wherein a user may delegate rights to himself, i.e., to other public keys he owns, but may not safely delegate those rights to others, i.e., to their public keys. In...
Michael J. Wiener, Helena Handschuh, Pascal Paillier, Ronald L. Rivest, Eli Biham, Lars R. Knudsen, ...
This article
Self-Delegation with Controlled Propagation -- or -- What If You Lose Your Laptop (1998)
Oded Goldreich, Birgit Pfitzmann, Ronald L. Rivest
We introduce delegation schemes wherein a user may delegate rights to himself, i.e., to other public keys he owns, but may not safely delegate those rights to others, i.e., to their public keys. In...
On the Design and Security of RC2 (1998)
Lars Knudsen, Ronald L. Rivest
. The block cipher RC2 was designed in 1989 by Ron Rivest for RSA Data Security Inc. In this paper we describe both the cipher and preliminary attempts to use both differential and linear...
Block Cipher, Ronald L. Rivest, Y.L. Yin, R. Sidney
. We introduce the RC6 TM block cipher. RC6 is an evolutionary improvement of RC5, designed to meet the requirements of the Advanced Encryption Standard (AES). Like RC5, RC6 makes essential use of...
On the Design and Security of RC2 (1998)
Lars Knudsen, Ronald L. Rivest
. The block cipher RC2 was designed in 1989 by Ron Rivest for RSA Data Security Inc. In this paper we describe both the cipher and preliminary attempts to use both differential and linear...
On the Design and Security of RC2 (1998)
Lars Knudsen, Ronald L. Rivest
. The block cipher RC2 was designed in 1989 by Ron Rivest for RSA Data Security Inc. In this paper we describe both the cipher and preliminary attempts to use both differential and linear...
Can We Eliminate Certificate Revocation Lists (1998)
Abstract. We briefly consider certificate revocation lists (CRLs), and ask whether they could, and should, be eliminated, in favor of other mechanisms. In most cases, the answer seems to be “yes....
The RC6 TM Block Cipher (1998)
Ronald L. Rivest, R. Sidney, Y. L. Yin
Abstract. We introduce the RC6 TM block cipher. RC6 is an evolutionary improvement ofRC5, designed to meet the requirements of the Advanced Encryption Standard (AES). Like RC5, RC6 makes essential...
Certificate discovery using SPKI/SDSI 2.0 certificates (1998)
Jean-emile Elien, Ronald L. Rivest
In this thesis, a framework was designed to implement certificate discovery in SPKI/-SDSI. The process of discovering a valid certificate chain is shown to be analogous to a string re-writing problem...
Self-delegation with controlled propagation — or — what if you lose your laptop (1998)
Oded Goldreich, Birgit Pfitzmann, Ronald L. Rivest
We introduce delegation schemes wherein a user may delegate certain rights to himself, but may not safely delegate these rights to others. In our motivating application, a user has a primary...
On the design and security of RC2 (1998)
Lars R. Knudsen, Vincent Rijmen, Ronald L. Rivest
Abstract. The block cipher RC2 was designed in 1989 by Ron Rivest for RSA Data Security Inc. In this paper we describe both the cipher and preliminary attempts to use both di erential and linear...
Self-Delegation with Controlled Propagation- or- What If You Lose Your Laptop (1998)
Srael Ermany, Oded Goldreich, Birgit Pfitzmann, Ronald L. Rivest
\Lambda y z Keywords:
Self-Delegation with Controlled Propagation (1998)
Or What If, Oded Goldreich, Birgit Pfitzmann, Ronald L. Rivest
We introduce delegation schemes wherein a user may delegate certain rights to himself, but may not safely delegate these rights to others. In our motivating application, a user has a primary...
The RC6 TM Block Cipher (1998)
Ronald L. Rivest, R. Sidney, Y. L. Yin
Abstract. We introduce the RC6 TM block cipher. RC6 is an evolutionary improvement ofRC5, designed to meet the requirements of the Advanced Encryption Standard (AES). Like RC5, RC6 makes essential...
Electronic lottery tickets as micropayments (1997)
Abstract. We present a new micropayment scheme based on the use of "electronic lottery tickets. " This scheme is exceptionally efficient since the bank handles only winning tickets,...
Are 'strong' primes needed for RSA (1997)
Ronald L. Rivest, Robert D. Silverman
We review the arguments in favor of using so-called "strong primes " in the RSA public-key cryptosystem. There are two types of such arguments: those that say that strong primes are...
Making Maximum Entropy Computations Easier by Adding Extra Constraints (Extended Abstract) (1997)
Sally A. Goldman, Ronald L. Rivest
) Sally A. Goldman Ronald L. Rivest Laboratory for Computer Science Massachusetts Institute of Technology Cambridge, Massachusetts 02139 March 12, 1997 Abstract This paper presents a new way to...
Mihir Bellare, Ronald L. Rivest
We present an alternative to the controversial "key escrow" techniques for enabling lawenforcement and national security access to encrypted communications. Our proposal allows such access...
All-Or-Nothing Encryption and The Package Transform (1997)
We present a new mode of encryption for block ciphers, which we call all-or-nothing encryption. This mode has the interesting defining property that one must decrypt the entire ciphertext before one...
Geometric Cryptography: Identification by Angle Trisection (1997)
Mike Burmester, Surrey Tw Oex, Ronald L. Rivest, Adi Shamir
We propose the field of "geometric cryptography," where messages and ciphertexts may be represented by geometric quantities such as angles or intervals, and where computation is performed...
Making Maximum Entropy Computations Easier By Adding Extra Constraints (Extended Abstract) (1997)
Sally A. Goldman, Ronald L. Rivest
This paper presents a new way to compute the probability distribution with maximum entropy satisfying a set of constraints. Unlike previous approaches, our method is integrated with the planning of...
Electronic lottery tickets as micropayments (1997)
Abstract. We present a new micropayment scheme based on the use of “electronic lottery tickets. ” This scheme is exceptionally efficient since the bank handles only winning tickets, instead of...
Are 'strong' primes needed for RSA (1997)
We review the arguments in favor of using so-called \strong primes " in the RSA public-key cryptosystem. There are two types of such arguments: those that say that strong primes are needed...
Mihir Bellare, Ronald L. Rivest
We present an alternative to the controversial \key escrow " techniques for enabling lawenforcement and national security access to encrypted communications. Our proposal allows such access...
Time-lock puzzles and timed-release crypto (1996)
1 Introduction Our motivation is the notion of "timed-release crypto, " where the goal is to encrypt a message so that it can not be decrypted by anyone, not even the sender, until...
Mihir Bellare, Ronald L. Rivest
We present an alternative to the controversial \key escrow " techniques for enabling lawenforcement and national security access to encrypted communications. Our proposal allows such access...
PayWord and MicroMint: two simple micropayment schemes (1996)
1 Introduction We present two simple micropayment schemes, "PayWord " and "MicroMint, " for making small purchases over the Internet. We were inspired to work on...
PayWord and MicroMint: two simple micropayment schemes (1996)
We present two simple micropayment schemes, \PayWord " and \MicroMint, " for making small purchases over the Internet. We were inspired to work on this problem by DEC's...
Ronald L. Rivest, Butler Lampson
We propose a new distributed security infrastructure, called SDSI (pronounced \Sudsy"). SDSI combines a simple public-key infrastructure design with a means of de ning groups and issuing...
Mihir Bellare, Ronald L. Rivest
We present an alternative to the controversial \key escrow " techniques for enabling lawenforcement and national security access to encrypted communications. Our proposal allows such access...
Time-lock puzzles and timed-release crypto (1996)
Ronald L. Rivest, Adi Shamir, David A. Wagner
Our motivation is the notion of "timed-release crypto, " where the goal is to encrypt a message so that it can not be decrypted by anyone, not even the sender, until a...
Time-lock puzzles and timed-release crypto (1996)
Ronald L. Rivest, Adi Shamir, David A. Wagner
Our motivation is the notion of \timed-release crypto, " where the goal is to encrypt a message so that it can not be decrypted byanyone, not even the sender, until a pre-determined amount...
Mihir Bellare, Ronald L. Rivest
We present an alternative to the controversial "key escrow " techniques for enabling lawenforcement and national security access to encrypted communications. Our proposal allows...
Learning from Imperfect Data in Theory and Practice (1996)
Ronald L. Rivest, F. R. Morgenthaler, Donna Karen Slonim, Donna Karen Slonim
This thesis explores several problems of learning with noisy or incomplete data. Most machine learning applications need to infer correct conclusions from available information, although some data...
Mihir Bellare, Ronald L. Rivest
We present an alternative to the controversial "key escrow" techniques for enabling lawenforcement and national security access to encrypted communications. Our proposal allows such access...
Time-lock puzzles and timed-release Crypto (1996)
Ronald L. Rivest, Adi Shamir, David A. Wagner
Introduction Our motivation is the notion of "timed-release crypto," where the goal is to encrypt a message so that it can not be decrypted by anyone, not even the sender, until a...
SDSI - A Simple Distributed Security Infrastructure (1996)
Ronald L. Rivest, Butler Lampson
We propose a new distributed security infrastructure, called SDSI (pronounced "Sudsy"). SDSI combines a simple public-key infrastructure design with a means of defining groups and issuing...
Mihir Bellare Ronald, Ronald L. Rivest
We present an alternative to the controversial "key escrow" techniques for enabling lawenforcement and national security access to encrypted communications. Our proposal allows such access...
Mihir Bellare, Ronald L. Rivest
We present an alternative to the controversial "key escrow" techniques for enabling lawenforcement and national security access to encrypted communications. Our proposal allows such access...
SDSI - A Simple Distributed Security Infrastructure (1996)
Ronald Rivest Laboratory, Ronald L. Rivest, Butler Lampson
We propose a new distributed security infrastructure, called SDSI (pronounced "Sudsy"). SDSI combines a simple public-key infrastructure design with a means of defining groups and issuing...
Time-lock puzzles and timed-release crypto (1996)
Ronald L. Rivest, Adi Shamir, Davida. Wagner
Our motivation is the notion of \timed-release crypto, " where the goal is to encrypt a message so that it can not be decrypted byanyone, not even the sender, until a pre-determined amount...
Mihir Bellare, Ronald L. Rivest
We present an alternative to the controversial \key escrow " techniques for enabling lawenforcement and national security access to encrypted communications. Our proposal allows such access...
PayWord and MicroMint: two simple micropayment schemes (1996)
We present two simple micropayment schemes, “PayWord ” and “MicroMint, ” for making small purchases over the Internet. We were inspired to work on this problem by DEC’s “Millicent ”...
PayWord and MicroMint: two simple micropayment schemes (1996)
We present two simple micropayment schemes, \PayWord " and \MicroMint, " for making small purchases over the Internet. We were inspired to work on this problem by DEC's...
Noise Tolerant Algorithms for Learning and Searching (1995)
Javed Alexander Aslam, Ronald L. Rivest, Javed Alexander Aslam
The RC5 Encryption Algorithm (1995)
Abstract. This document describes the RC5 encryption algorithm, a fast symmetric block cipher suitable for hardware or software implementations. A novel feature of RC5 is the heavy use of...
Noise Tolerant Algorithms for Learning and Searching (1995)
Ronald L. Rivest, Javed Alexander Aslam, Javed Alexander Aslam
Certi ed by
Piecemeal graph exploration by a mobile robot (1995)
Baruch Awerbuch, Margrit Betke, Ronald L. Rivest, Mona Singh
We study how a mobile robot can piecemeal learn an unknown environment. The robot's goal is to learn a complete map of its environment, while satisfying the constraint that it must return every...
The RC5 Encryption Algorithm (1995)
Abstract. This document describes the RC5 encryption algorithm, a fast symmetric block cipher suitable for hardware or software implementations. A novel feature of RC5 is the heavy use of...
Piecemeal graph exploration by a mobile robot (1995)
Baruch Awerbuch, Margrit Betke, Ronald L. Rivest, Mona Singh
We study how a mobile robot can learn an unknown environment in a piecemeal manner. The robot's goal is to learn a complete map of its environment, while satisfying the constraint that it must...
The RC5 Encryption Algorithm (1995)
Abstract. This document describes the RC5 encryption algorithm, a fast symmetric block cipher suitable for hardware or software implementations. A novel feature of RC5 is the heavy use of...
The RC5 Encryption Algorithm (1995)
Abstract. This document describes the RC5 encryption algorithm. RC5 is a fast symmetric block cipher suitable for hardware or software implementations. A novel feature of RC5 is the heavy use of...
Piecemeal Learning of an Unknown Environment (1995)
Margrit Betke, Ronald L. Rivest, Mona Singh
We introduce a new learning problem: learning a graph by piecemeal search, in which the learner must return every so often to its starting point (for refueling, say). We present two linear-time...
The RC5 Encryption Algorithm (1995)
Ronald Rivest Mit, Ronald L. Rivest
. This document describes the RC5 encryption algorithm, a fast symmetric block cipher suitable for hardware or software implementations. A novel feature of RC5 is the heavy use of data-dependent...
The RC5 Encryption Algorithm (1995)
. This document describes the RC5 encryption algorithm, a fast symmetric block cipher suitable for hardware or software implementations. A novel feature of RC5 is the heavy use of data-dependent...
Multi-Grade Cryptography (1995)
This paper presents a new paradigm for secret-key cryptography that may be useful for export control (and perhaps also for law-enforcement). We call it multi-grade cryptography
Complete Variable-Length "Fix-Free" Codes (1995)
David Gillman, Ronald L. Rivest
A set of codewords is fix-free if it is both prefix-free and suffix-free: no codeword in the set is a prefix or a suffix of any other. A set of codewords fx 1 ; x 2 ; : : : ; x n g over a t-letter...
Picking the Best Expert from a Sequence (1995)
Ruth Bergman, Ronald L. Rivest
We examine the problem of finding a good expert from a sequence of experts. Each expert has an "error rate"; we wish to find an expert with a low error rate. However, each expert's...
Game Tree Searching by Min/Max Approximation (1995)
We present an iterative method for searching min/max game trees based on the idea of approximating the "min" and "max" operators by generalized mean-valued operators. This...
The RC5 Encryption Algorithm (1995)
Abstract. This document describes the RC5 encryption algorithm, a fast symmetric block cipher suitable for hardware or software implementations. A novel feature of RC5 is the heavy use of...
Piecemeal graph exploration by a mobile robot (1995)
Baruch Awerbuch, Margrit Betke, Ronald L. Rivest, Mona Singh
We study how a mobile robot can learn an unknown environment in a piecemeal manner. The robot's goal is to learn a complete map of its environment, while satisfying the constraint that it must...
The RC5 Encryption Algorithm (1995)
Abstract. This document describes the RC5 encryption algorithm, a fast symmetric block cipher suitable for hardware or software implementations. A novel feature of RC5 is the heavy use of...
Cryptography and machine learning (1993)
This paper gives a survey of the relationship between the elds of cryptography and machine learning, with an emphasis on how each eld has contributed ideas and techniques to the other. Some suggested...
Learning Binary Relations and Total Orders (1993)
Sally A. Goldman, Robert E. Schapire, Ronald L. Rivest
We study the problem of learning a binary relation between two sets of objects or between a set and itself. We represent a binary relation between a set of size n and a set of size m as an n m matrix...
Piecemeal learning of an unknown environment (1993)
Margrit Betke, Ronald L. Rivest, Mona Singh
This publication can be retrieved by anonymous ftp to publications.ai.mit.edu. We introduce a new learning problem: learning a graph by piecemeal search, inwhich the learner must return every so...
Piecemeal learning of an unknown environment (1993)
Ronald L. Rivest, Mona Singh, Sally Goldman
Abstract. We introduce a new learning problem: learning a graph by piecemeal search, in which the learner must return every so often to its starting point (for refueling, say). We present two...
Cryptography and machine learning (1993)
This paper gives a survey of the relationship between the fields of cryptography and machine learning, with an emphasis on how each field has contributed ideas and techniques to the other. Some...
Learning Binary Relations and Total Orders (1993)
Sally A. Goldman, Ronald L. Rivest, Robert E. Schapire
We study the problem of learning a binary relation between two sets of objects or between a set and itself. We represent a binary relation between a set of size n and a set of size m as an n \Theta m...
Learning Binary Relations and Total Orders (1993)
Sally A. Goldman, Robert E. Schapire, Ronald L. Rivest
We study the problem of learning a binary relation between two sets of objects or between a set and itself. We represent a binary relation between a set of size n and a set of size m as an n m matrix...
Ronald L. Rivest, Robert E. Schapire
We present new procedures for inferring the structure of a nite-state automaton (FSA) from its input/output behavior, using access to the automaton to perform experiments. Our procedures use a new...
Piecemeal learning of an unknown environment (1993)
Ronald L. Rivest, Mona Singh, Sally Goldman
Abstract. Weintroduce a new learning problem: learning a graph by piecemeal search, in which the learner must return every so often to its starting point (for refueling, say). We present two...
Training A 3-Node Neural Network Is NP-Complete (1992)
Avrim L. Blum, Ronald L. Rivest
: We consider a 2-layer, 3-node, n-input neural network whose nodes compute linear threshold functions of their inputs. We show that it is NP-complete to decide whether there exist weights and...
Finding four million large random primes (1991)
A number n is a (base two) pseudoprime if it is composite and satises the identity
Cryptology has advanced tremendously since 1976; this chapter provides a brief overview of the current state-of-the-art in the field. Several major themes predominate in the development. One such...
Game tree searching by min/max approximation (1988)
We present an iterative method for searching min/max game trees based on the idea of approximating the "min " and "max " operators by generalized mean-valued...
A knapsack type public key cryptosystem based on arithmetic in finite fields (1988)
Abstract { A new knapsack type public key cryptosystem is introduced. The system is based on a novel application of arithmetic in nite elds, following a construction by Bose and Chowla. By...
A digital signature scheme secure against adaptive chosen-message attacks (1988)
Sha Goldwasser, Silvio Micali, Ronald L. Rivest
We present a digital signature scheme based on the computational diculty of integer factorization. The scheme possesses the novel property of being robust against an adaptive chosen-message attack:...
Game tree searching by min/max approximation (1988)
We present an iterative method for searching min/max game trees based on the idea of approximating the \min " and \max " operators by generalized mean-valued operators. This...
A digital signature scheme secure against adaptive chosen-message attacks (1988)
Shafi Goldwasser, Silvio Micali, Ronald L. Rivest
We present a digital signature scheme based on the computational difficulty of integer factorization. The scheme possesses the novel property of being robust against an adaptive chosen-message...
Efficient methods for calculating maximum entropy distributions (1987)
Ronald L. Rivest, Sally A. Goldman, Sally A. Goldman, Sally A. Goldman
Certified by
Learning decision lists (1987)
This paper introduces a new representation for Boolean functions, called decision lists, and shows that they are eciently learnable from examples. More precisely, this result is established for \k-DL...
Learning decision lists (1987)
This paper introduces a new representation for Boolean functions, called decision lists, and shows that they are eciently learnable from examples. More precisely, this result is established for \k-DL...
Ronald L. Rivest, Adi Shamir, Yael Tauman
We introduce the notion of a ring signature: a digital signature that species a set of possible signers, such that the verier can't tell which member actually produced the signature. Unlike...
Ronald L. Rivest, Adi Shamir, Yael Tauman
Abstract. In this paper we formalize the notion of a ring signature, which makes it possible to specify a set of possible signers without revealing which member actually produced the signature....
Optimal arrangement of keys in a hash table (1978)
ABSTRACT When open addressing IS used to resolve collisions in a hash table, a given set of keys may be arranged in many ways, typically this depends on the order in which the keys are inserted It is...
This paper presents an analysis of a simple treestructured disjoint set Union-Find algorithm, and shows that this algorithm requires between n and 2n steps on the average to execute a sequence of n...
Making Mix Nets Robust for Electronic Voting by Randomized Partial Checking
Markus Jakobsson, Ari Juels, Ronald L. Rivest
We propose a new technique for making mix nets robust, called randomized partial checking (RPC). The basic idea is that rather than providing a proof of completely correct operation, each server...
Some Comments on the First Round AES Evaluation of RC6
Scott Contini, Ronald L. Rivest, Yiqun Lisa
this paper, the e#ect of increasing levels of parallelism is investigated for seven of the AES submissions, including RC6. There it is shown that for a limited increase in the amount of parallelism...
Picking the Best Expert from a Sequence
Ruth Bergman, Ronald L. Rivest
We examine the problem of finding a good expert from a sequence of experts. Each expert has an "error rate"; we wish to find an expert with a low error rate. However, each expert's...
Making Mix Nets Robust for Electronic Voting by Randomized Partial Checking
Markus Jakobsson, Ari Juels, Ronald L. Rivest
We propose a new technique for making mix nets robust, called randomized partial checking (RPC). The basic idea is that rather than providing a proof of completely correct operation, each server...