Ronald L. Rivest: Publications and Talks
This page under continual construction...
List of Publications and Talks
-
Publications
list.
A more-or-less complete list of my publications.
Selected publications, many available on-line, are listed below.
Cryptography and Security
- A "Sum of Square Roots" (SSR) Pseudorandom Sampling Method for
Election Audits
by Ronald L. Rivest.
(April 25, 2008. Working paper; comments appreciated.)
- On the Notion of ``Software Independence'' in Voting Systems
by Ronald L. Rivest and John P. Wack.
(As submitted (3/28/2008)
to the Philosophical Transactions of the Royal Society, series A.)
An earlier version (7/28/2006) was posted on the NIST web site:
- On Auditing Elections When Precincts Have Different Sizes
by Javed Aslam, Raluca A. Popa, and Ronald L. Rivest.
Unpublished draft. Version 12/17/2007. Comments appreciated.
- A Simple Rule of Thumb for Election Audit Size Determination
by Ronald L. Rivest.
Unpublished draft. Version 10/31/2007. Comments appreciated.
- Voluntary Voting System Guidelines
Developed by
NIST
and the
TGDC
(which included me) and delivered
on September 4, 2007
to the
EAC
for consideration and public comment.
- Engaging Privacy and Information Technology in a Digital Age
Edited by James Waldo, Herbert S. Lin, and Lynette I. Millett.
(I served on the committee that produced this report.)
The National Academies Press, Washington, D.C., 2007
Also available here.
- ThreeVotingProtocols: ThreeBallot, VAV, and Twin
by Ronald L. Rivest and Warren D. Smith.
This version of this paper will appear in the Proceedings of
EVT'07
(Electronic Voting Technology Workshop, Boston, MA, August 6, 2007).
- pdf
- ppt
(Slides from
EVT'07
presentation).
- Amplifying Collision Resistance: A Complexity-Theoretic Treatment
by Ran Canetti, Ron Rivest, Madhu Sudan, Luca Trevisan, Salil Vadhan,
and Hoeteck Wee.
To appear in Proceedings CRYPTO 2007.
- On Estimating the Size and Confidence of a Statistical Audit
by Javed A. Aslam, Raluca A. Popa, and Ronald L. Rivest.
Version of June 30, 2007.
This version of this paper will appear in the Proceedings of
EVT'07
(Electronic Voting Technology Workshop, Boston, MA, August 6, 2007).
-
On Auditing Elections When Precincts Have Different Sizes
by Ronald L. Rivest.
Unpublished draft. Version 3/18/2007. Comments appreciated.
-
The ThreeBallot Voting System.
by Ronald L. Rivest.
Unpublished draft. Version 10/1/06. Comments appreciated.
(A revised version, with new co-author W.D. Smith, appears above,
and will be presented at EVT'07.)
-
On Estimating the Size of a Statistical Audit
by Ronald L. Rivest.
Unpublished draft. Version 11/14/06.
(Superseded by Aslam/Popa/Rivest paper, above.)
-
Scratch & Vote---Self-contained Paper-based Cryptographic Voting
by Ben Adida and Ronald L. Rivest.
Proceedings WPES '06 (Workshop on Privacy in the Electronic
Society 2006).
-
Perspectives on Financial Cryptography (Revisited)
by Ronald L. Rivest.
Financial Cryptography '06 Conference Keynote.
(Update of talk given for Financial Cryptography '97)
-
Preliminary Voting -- Prevoting
by Ronald L. Rivest
(Draft, to appear in larger report by CalTech/MIT Voting Technology Project.) August 6, 2005.
-
Abelian square-free dithering for iterated hash functions
by Ronald L. Rivest
(draft; to appear). August 2005.
-
Lightweight Encryption for Email
by Ben Adida, Susan Hohenberger, and Ronald L. Rivest
USENIX Steps to Reducing Unwanted Traffic on the Internet Workshop (SRUTI), July 2005.
-
Lightweight Email Signatures
by Ben Adida, David Chau, Susan Hohenberger, and Ronald L. Rivest
(Revised; a preliminary version was presented at the DIMACS Workshop on Theft in E-Commerce, April 2005.)
- pdf (early version)
- pdf (latest version 2/1/2006)
-
Ad-Hoc-Group Signatures from Hijacked Keypairs
by Ben Adida, Susan Hohenberger, and Ronald L. Rivest
(Revised; a preliminary version was presented at the DIMACS Workshop on Theft in E-Commerce, April 2005.)
-
Electronic Voting
by Ronald L. Rivest
Talk given at NSA, June 3, 2004.
-
Remarks on Electronic Voting
by Ronald L. Rivest
Text of remarks at the Harvard Kennedy School of Governmment Digital
Voting Symposium, June 1, 2004.
-
Some Thoughts on Electronic Voting
by Ronald L. Rivest
Talk given May 26, 2004 at DIMACS Workshop on Electronic Voting.
-
Peppercoin Micropayments
by Ronald L. Rivest
February 9, 2004. Proceedings Financial Cryptography '04.
(ed. Ari Juels)
Lecture Notes in Computer Science, Vol. 3110. (Springer, 2004), 2--8.
-
On Permutation Operations in Cipher Design
by Ruby B. Lee, Z. J. Shi, Y. L. Yin, Ronald L. Rivest, and M. J. B. Robshaw.
January 24, 2004. To appear in Proceedings ITCC 2004.
A version has appeared under the title
Permutation Operations in Block Ciphers
in: EMBEDDED CRYPTOGRAPHIC HARDWARE: - 2004 DESIGN AND SECURITY.
(Nova, 2004).
-
On The Notion of Pseudo-Free Groups
by Ronald L. Rivest.
Proceedings TCC 2004 (Copyright IACR.)
(Ed. Moni Naor) Springer-Verlag Lecture Notes in Computer Science No. 2951.
Pages 505--521.
-
RSA Problem
by Ronald L. Rivest and Burt Kaliski.
December 10, 2003.
(To appear in Encyclopedia of Cryptography and Security (Kluwer).)
-
2002 ACM A. M. Turing Award Lectures
by Leonard Adleman, Ronald L. Rivest, and Adi Shamir.
Given June 8, 2003 at FCRC in San Diego, California.
-
The Blocker Tag: Selective Blocking of RFID Tags for Consumer Privacy
by Ari Juels, Ronald L. Rivest, and Michael Szydlo.
May 16, 2003. (To appear in Proceedings 10th Annual ACM CCS 2003.)
-
Does Anyone Really Need Micropayments?
by Nicko van Someren, Andrew Odlyzko, Ronald L. Rivest, Tim Jones,
and Duncan Goldie-Scot.
in Proceedings Financial Cryptography 2003 (ed. Rebecca Wright)
Lecture Notes in Computer Science, Vol. 2742 (Springer 2003), 69--76.
-
Micropayments Revisited
by Silvio Micali and Ronald L. Rivest.
(Proceedings of the Cryptographer's Track at the RSA Conference 2002,
Bart Preneel (ed.), Springer Verlag CT-RSA 2002, LNCS 2271, pages 149--163.)
-
The Untrusted Computer Problem and Camera-Based Authentication,
by D. Clarke, B. Gassend, T. Kotwal, M. Burnside, M. van Dijk, S. Devadas,
and R. L. Rivest.
Lecture Notes in Computer Science 2414,
Proceedings of the International Conference on Pervasive Computing
(Pervasive2002), pages 114-124, August 2002.
-
Access-Controlled Resource Discovery for Pervasive Networks,
by S. Raman, D. Clarke, M. Burnside, S. Devadas and R. L. Rivest.
Proceedings of the 18th ACM Symposium on Applied Computing
(Security Track), March 2003.
(Also appeared in Concurrency and Computation: Practice and Experience
2004: 16: pages 1099--1120.)
-
Tweakable Block Ciphers
by Moses Liskov, Ronald L. Rivest, and David Wagner.
Proceedings CRYPTO 2002
(Springer-Verlag, Lecture Notes in Computer Science No. 2442,
Moti Yung(ed.), 2002), pages 31--46.
-
Making Mix Nets Robust for Electronic Voting by Randomized
Partial Checking
by Markus Jakobsson, Ari Juels, and Ronald L. Rivest.
In D. Boneh, ed., USENIX Security '02, pp. 339-353. 2002.
(Also available as IACR eprint 2002/025.)
-
Proxy-Based Security Protocols in Networked Mobile Devices
by M. Burnside, D. Clarke, T. Mills, A. Maywah, S. Devadas,
and R. Rivest.
Proceedings of the 17th ACM Symposium on Applied Computing
(Security Track),
pages 265-272, March 2002.
-
A Modular Voting Architecture (``Frogs'')
by Shuki Bruck, David Jefferson, and Ronald L. Rivest.
-
Voting---What is, What Could Be
(July 2001 Report of the CalTech-MIT Voting Technology Project)
-
How to Leak A Secret
by Ronald L. Rivest, Adi Shamir, and Yael Tauman.
ASIACRYPT 2001, pages 552--565.
Lecture Notes in Computer Science (ed. Colin Boyd),
Volume 2248 (Springer).
-
Testimony on Security Issues in Voting Technology
(Testimony given before the U.S. House Committee on Administration, May 24, 2001.)
-
Electronic Voting
(Slides for talk given for Cambridge Club at Harvard Faculty Club,
March 5, 2001.)
-
Electronic Voting
(Corresponds to my remarks at a panel discussion at Financial Cryptography '01, 2/19--2/22.)
(To appear in the Proceedings of Financial Cryptography '01.)
-
Issues in Cryptography
Short luncheon talk given March 7, 2001 at Computers, Freedom, and Privacy 2001 Conference.
-
Certificate Chain Discovery in SPKI/SDSI
by Dwaine Clarke, Jean-Emile Elien, Carl Ellison, Matt Fredette, Alexander Morcos, and Ronald L. Rivest.
(To appear in JCS.) Draft of September 13, 2001.
-
Two Signature Schemes
(Slides from talk given at Cambridge University October 17, 2000;
one scheme (a transitive signature scheme for undirected graphs) is
joint work with Silvio Micali, the other scheme (a prefix aggregation scheme)
is joint work with Suresh Chari and Tal Rabin.)
Here is the paper for the first scheme:
Transitive Signature Schemes
by Silvio Micali and Ronald L. Rivest.
(Proceedings of the Cryptographer's Track at the RSA Conference 2002,
Bart Preneel (ed.), Springer Verlag CT-RSA 2002, LNCS 2271, pages 236--243.)
Here is the current draft of the paper for the second scheme, by
Chari, Rabin, and Rivest:
An Efficient Signature Scheme for Route Aggregation
by Suresh Chari, Tal Rabin, and Ronald L. Rivest
(Draft of February 1, 2002.)
-
Are ``Strong'' Primes Needed for RSA?
by Ronald L. Rivest and Robert D. Silverman.
-
Pseudonym Systems
by Anna Lysyanskaya, Ronald L. Rivest, Amit Sahai, and Stefan Wolf.
Selected Areas in Cryptography '99 (Springer Verlag Lecture Notes in Computer
Science No. 1758; edited by H. Heys and C. Adams, 2000), pages 184--199.
-
Unconditionally Secure Commitment and Oblivious Transfer Schemes Using Private Channels and a Trusted Initializer
by Ronald L. Rivest.
Unpublished manuscript, 11/8/99.
-
Permutation Polynomials modulo 2^w
by Ronald L. Rivest.
October 6, 1999. Revised October 25, 1999.
In Finite Fields and their Applications Volume 7 (2001), pages 287--292.
-
The Beer Bottle Cipher
by Ronald L. Rivest.
Posted here June 30, 1999.
Published in CCE Quarterly Journal
(PricewaterhouseCoopers Cryptographic Center of Excellence),
Issue 3 (1999), 28--30.
The LCS35 Time Capsule Crypto-Puzzle (description, java code, and puzzle parameters)
by Ronald L. Rivest
Improved Analysis of Some Simplified Variants of RC6
by Scott Contini, Ronald L. Rivest, M.J.B. Robshaw, and Yiqun Lisa Yin.
in Proceedings Fast Software Encryption '99
(Springer Verlag, Lecture Notes in Computer Science No. 1636,
Lars Knudsen(ed.), 1999), pages 1--15.
Some Thoughts on Serial Numbers on Intel CPU's
by Ronald L. Rivest.
Unpublished note, drafted January 26, 1999; revised in minor ways on August 23, 1999 and posted here.
SPKI Certificate Theory
by C. Ellison, B. Frantz, B. Lampson, R. Rivest, B. Thomas,
and T. Ylonen.
Internet Network Working Group RFC2693, September 1999.
Simple Public Key Certificate
by C. Ellison, B. Frantz, B. Lampson, R. Rivest, B. Thomas,
and T. Ylonen.
Internet Draft, July 26, 1999.
SPKI Examples
by C. Ellison, B. Frantz, B. Lampson, R. Rivest, B. Thomas,
and T. Ylonen.
Internet Draft, March 10, 1998.
The Case against Regulating Encryption Technology
by Ronald L. Rivest.
Scientific American, October 1998, pages 116--117.
Self-Delegation with Controlled Propagation -- or -- What If You Lose Your Laptop
by Oded Goldreich and Birgit Pfitzmann and Ronald L. Rivest
Proceedings CRYPTO '98
(Springer-Verlag, Lecture Notes in Computer Science No. 1462, Hugo Krawczyk(ed), 1998), pages 153--168.
(Also Cryptology ePrint Archive 1997/012.)
The Security of the RC6 Block Cipher
by Scott Contini, Ronald L. Rivest, M.J.B. Robshaw, and Yiqun Lisa Yin.
Posted at RSA's RC6 page.
(August 20, 1998)
The RC6 Block Cipher
by Ronald L. Rivest, M.J.B. Robshaw, R. Sidney, and Y.L. Yin
Posted at RSA's RC6 page.
(Version 1.1; August 20, 1998).
Can We Eliminate Certificate Revocation Lists?
by Ronald L. Rivest
(Proceedings of Financial Cryptography '98; Springer Lecture Notes
in Computer Science No. 1465 (Rafael Hirschfeld, ed.), February 1998),
pages 178--183.
On the Design and Security of RC2
By Lars R. Knudsen,
Vincent Rijmen, Ronald L. Rivest, and M.J.B. Robshaw.
(Proceedings
Fifth Fast Software Encryption Workshop FSE '98, (Springer Lecture
Notes in Computer Science, No. 1372, March 1998, Serge Vaudenay
(ed.)), pages 206--221.
Chaffing and Winnowing: Confidentiality without Encryption
by Ronald L. Rivest.
CryptoBytes (RSA Laboratories), volume 4, number 1 (summer 1998), 12--17.
Cryptography as Duct Tape
by Ronald L. Rivest
(a short note written to the Senate Commerce and Judiciary Committees
in opposition to mandatory key recovery proposals).
The Risks of Key Recovery, Key Escrow, and Trusted Third Party
Encryption
By Hal Abelson, Ross Anderson, Steven M. Bellovin,
Josh Benaloh, Matt Blaze, Whitfield Diffie, John Gilmore, Peter G. Neumann,
Ronald L. Rivest, Jeffery I. Schiller, and Bruce Schneier.
May, 1997.
Electronic Lottery Tickets as Micropayments,
by Ronald L. Rivest.
Proceedings of Financial Cryptography '97 Conference,
Springer Lecture Notes in Computer Science #1318 (1997), 307--314.
Perspectives on Financial Cryptography
by Ronald L. Rivest.
Proceedings of Financial Cryptography '97 Conference,
Springer Lecture Notes in Computer Science #1318 (1997), 145--149.
SDSI---A Simple Distributed Security Infrastructure
(By Ronald L. Rivest and Butler Lampson).
(See also the SDSI Page)
- [Version 1.0]
- [Version 1.1]
- [Version 2.0]
All-Or-Nothing Encryption and The Package Transform
by Ronald L. Rivest.
Proceedings of the 1997 Fast Software Encryption Conference.
Springer Lecture Notes in Computer Science #1267 (1997), 210--218.
Minimal Key Lengths for Symmetric Ciphers to Provide Adequate Commercial Security
by Matt Blaze, Whitfield Diffie, Ronald L. Rivest, Bruce Schneier, Tsutomu
Shimomura, Eric Thompson, and Michael Wiener.
Translucent Cryptography---An Alternative to Key Escrow, and its Implementation
via Fractional Oblivious Transfer
by Mihir Bellare and Ronald L. Rivest.
MIT/LCS Technical Report 683 (18 Feb 1996):
Journal of Cryptology (vol. 12, no. 2, Spring 1999, pages 117--140):
Multi-grade cryptography
by Ronald L. Rivest
Unpublished manuscript.
Time-lock puzzles and timed-release Crypto
by Ronald L. Rivest, Adi Shamir, and David A. Wagner.
(This has appeared as LCS technical memo MIT/LCS/TR-684 (February 1996).)
Geometric Cryptography
by Mike Burmester, Ronald L. Rivest, and Adi Shamir.
Unpublished.
PayWord and MicroMint--Two Simple Micropayment Schemes
by Ronald L. Rivest and Adi Shamir.
CryptoBytes, volume 2, number 1 (RSA Laboratories, Spring 1996), 7--11.
Also in Proceedings of 1996 International Workshop on Security Protocols,
(ed. Mark Lomas), (Springer, 1997), Lecture Notes in Computer Science No. 1189, pages 69--87.
The RC5 Encryption Algorithm
by Ronald L. Rivest.
Proceedings of the 1994 Leuven Workshop on Fast Software Encryption
(Springer 1995), pages 86-96.
(Also see
The RC5 Encryption Algorithm (pdf)
in Dr. Dobbs Journal number 226 (January 1995), pages 146-148.)
The MD5 Message Digest Algorithm
by Ronald L. Rivest.
Internet RFC 1321 (April 1992).
The MD4 Message Digest Algorithm
by Ronald L. Rivest.
Internet RFC 1320 (April 1992).
Cryptography and Machine Learning
by Ronald L. Rivest.
Proceedings ASIACRYPT '91 (Springer 1993), 427--439.
Finding Four Million Large Random Primes
by Ronald L. Rivest.
Proc. CRYPTO 90 (Springer 1991), 625--626.
Cryptography
by Ronald L. Rivest.
Chapter 13 of Handbook of Theoretical Computer Science,
(ed. J. Van Leeuwen) vol. 1 (Elsevier, 1990), 717--755.
A Knapsack Type Cryptosystem Based on Arithmetic in Finite Fields
by Benny Chor and Ronald L. Rivest.
IEEE Trans. Information Theory 34,5 (Sep. 1988), 901--909.
(Also in CRYPTO 84.)
Is the Data Encryption Standard A Group?
by Burton S. Kaliski, Ronald L. Rivest, and Alan T. Sherman.
Journal of Cryptology 1,1 (1988),3--36.
A Digital Signature Scheme Secure Against Adaptive Chosen Message Attacks
by Shafi Goldwasser, Silvio Micali, and Ronald L. Rivest.
SIAM J. Computing 17,2 (April 1988), 281--308.
(Note: This does not include the figures that were published with the paper.)
Efficient Factoring Based on Partial Information
by Ronald L. Rivest and Adi Shamir
Proceedings EUROCRYPT '85, LNCS 219, ed. F. Pichler (Springer), 31--34.
Mental Poker
by Adi Shamir, Ronald L. Rivest, and Leonard M. Adleman.
in The Mathematical Gardner (ed. David A. Klarner),
(Prindle, Weber, and Schmidt, 1981), pages 37-43.
Testing Implementations of DES
by Ronald L. Rivest
(Unpublished, 2/85)
Remarks on a Proposed Cryptanalytic Attack on the
M.I.T. Public-Key Cryptosystem
Cryptologia 2,1 (January 1978), 62--65.
A Method for Obtaining Digital Signatures and Public-Key Cryptosystems
by Ronald L. Rivest, Adi Shamir, and Leonard M. Adleman.
Communications of the ACM 21,2 (Feb. 1978), 120--126.
Algorithms
-
Introduction to Algorithms (Second Edition)
by Cormen, Leiserson, Rivest, and Stein (MIT Press and McGraw-Hill, 2001).
-
Optimal Arrangements of Keys in a Hash Table
by Ronald L. Rivest.
Journal of the ACM 25,2 April 1978, 200--209.
-
On Recognizing Graph Properties from Adjacency Matrices
by Ronald L. Rivest and Jean Vuillemin.
Theoretical Computer Science 3 1976, 371--384.
-
Linear Expected Time Of A Simple Union-Find Algorithm
by Jon Doyle and Ronald L. Rivest.
Information Processing Letters 5,5 November 1976, 146--148.
-
Partial-Match Retrieval Algorithms
by Ronald L. Rivest.
Siam J. Computing 5,1 March 1976, 19--50.
-
Time Bounds for Selection
by Manual Blum, Robert W. Floyd, Vaughan Pratt, Ronald L. Rivest,
and Robert E. Tarjan.
Journal of Computer and System Sciences 7,4 August 1973,
448-460.
Machine Learning
-
Piecemeal Graph Exploration by a Mobile Robot
by Baruch Awerbuch, Margrit Betke, Ronald L. Rivest, and Mona Singh.
Information and Computation 152,2 (August 1999), 155--172.
-
Piecemeal Learning of an Unknown Environment
by Margrit Betke, Ronald L. Rivest, and Mona Singh.
Machine Learning 18:2-3 (February 1995), 231--254.
-
Being Taught Can be Faster than Asking Questions
by Ronald L. Rivest and Yiqun Lisa Yin
Proceedings 1995 COLT Conference (ACM, 1995), 144-151.
-
Picking the Best Expert from a Sequence
by Ruth Bergman and Ronald L. Rivest.
Proceedings of the Fifth
International Workshop on Artificial Intelligence and Statistics,
(Fort Lauerdale FL, January 1995). 219--228.
-
Learning Binary Relations and Total Orders
by Sally A. Goldman, Ronald L. Rivest, and Robert E. Schapire.
SIAM J. Computing 22,5 (October 1993), 1006-1034.
-
Diversity-Based Inference of Finite Automata
by Ronald L. Rivest and Robert E. Schapire.
Journal of the ACM 41, 3 (May 1994), 555--589.
-
Inference of Finite Automata Using Homing Sequences
by Ronald L. Rivest and Robert E. Schapire.
Information and Computation 103,2 (April 1993), 299--347.
-
Making Maximum Entropy Constraints Easier By Adding Extra Constraints (Extended Abstract)
by Sally Goldman and Ronald L. Rivest.
in Maximum--Entropy and Bayesian Methods in Science and Engineering
(Vol. 2), (Edited by G.J. Erickson and C.R. Smith) (Kluwer Academic
Publishers, 1988), 323--340.
-
Learning Decision Lists
by Ronald L. Rivest.
Machine Learning 2,3 (1987), 229--246.
Miscellaneous
-
Recollections of Stanford CS 1969--1973
by Ronald L. Rivest.
Talk given March 21, 2006 at Stanford Computer Science
Forum meeting celebrating the 40th anniverssary of the
Stanford CS Department.
-
Complete Variable-Length `FixFree' Codes
by David Gillman and Ronald L. Rivest.
Designs, Codes, and Cryptography 5,2 (March 1995), 109--114.
-
Game Tree Searching by Min/Max Approximation
by Ronald L. Rivest.
Artificial Intelligence 34,1 (Dec. 1987), 77-96.
-
How to Reuse a "Write-Once" Memory
by Ronald L. Rivest and Adi Shamir.
Information and Control 55,1-3 (October/November/December 1982),
1--19.
-
Minimum Edge-Length Decomposition of Rectilinear Polygons
by A. Lingas, R. Y. Pinter, R. L. Rivest, and A. Shamir.
Proc. 1982 Allerton Conference on Communications, Control, and Computing
(Oct. 1982), 53-63.
-
Constructing Optimal Binary Decision Trees is NP-Complete
by Laurent Hyafil and Ronald L. Rivest.
Information Processing Letters 5,1 (May 1976), 15--17.
Return to Ron Rivest's home page.