Leonid Reyzin's Research Papers by Topic

Leonid Reyzin's Research Papers (And a Few Talks and Implementations) by Topic

(click here to get them sorted chronologically instead)

Protocols

Can a Public Blockchain Keep a Secret? by Fabrice Benhamouda, Craig Gentry, Sergey Gorbunov, Shai Halevi, Hugo Krawczyk, Tal Rabin, and Leonid Reyzin. Appears in TCC 2020.
Turning HATE Into LOVE: Homomorphic Ad Hoc Threshold Encryption for Scalable MPC by Leonid Reyzin, Adam Smith, and Sophia Yakoubov. To appear in CSCML 2021.
A Comparative Evaluation of Order-Preserving and Order-Revealing Schemes and Protocols by Dmytro Bogatov, George Kollios, and Leonid Reyzin. Appears in VLDB 2019 (winner of the Reproducibility Award). Implementation Available
Efficient Noninteractive Certification of RSA Moduli and Beyond by Sharon Goldberg, Leonid Reyzin, Omar Sagga, and Foteini Baldimtsi. Appears in Asiacrypt 2019.

Authenticated Data Structures, DNSSEC, Accumulators
- Aardvark: A Concurrent Authenticated Dictionary with Short Proofs by Derek Leung, Yossi Gilad, Sergey Gorbunov, Leonid Reyzin, and Nickolai Zeldovich
- Pointproofs: Aggregating Proofs for Multiple Vector Commitments by Sergey Gorbunov, Leonid Reyzin, Hoeteck Wee, and Zhenfei Zhang. Appears in ACM CCS 2020. Implementation available. Talk at zkSummit 6.
- Accumulators with Applications to Anonymity-Preserving Revocation by Foteini Baldimtsi, Jan Camenisch, Maria Dubovitskaya, Anna Lysyanskaya, Leonid Reyzin, Kai Samelin, and Sophia Yakoubov. Appears in EuroS&P 2017.
- Improving Authenticated Dynamic Dictionaries, with Applications to Cryptocurrencies by Leonid Reyzin, Dmitry Meshkov, Alexander Chepurnoy, and Sasha Ivanov. Appears in Financial Cryptography 2017. Slides and video of my talk at Real World Crypto 2017. Implementation Available.
- Efficient Asynchronous Accumulators for Distributed PKI by Leonid Reyzin and Sophia Yakoubov. Appears in SCN 2016.
- NSEC5 Project:
  - Making NSEC5 practical for DNSSEC by Dimitrios Papadopoulos and Duane Wessels and Shumon Huque and Moni Naor and Jan Včelák and Leonid Reyzin and Sharon Goldberg.
  - VRF internet draft based on the above paper
  - reference implementation
  - more secure implementation
  - NSEC5: Provably Preventing DNSSEC Zone Enumeration by Sharon Goldberg, Moni Naor, Dimitrios Papadopoulos, Leonid Reyzin, Sachin Vasant, and Asaf Ziv. Appears in NDSS 2015.
- Authenticated Index Structures for Aggregation Queries, by Feifei Li, Marios Hadjieleftheriou, George Kollios, and Leonid Reyzin. ACM Transactions on Information and System Security (TISSEC) 13(4), 2010. Implementation available.
- Dynamic Authenticated Index Structures for Outsourced Databases, by Feifei Li, Marios Hadjieleftheriou, George Kollios, and Leonid Reyzin. Appears in SIGMOD 2006. Implementation available.
- Mercurial Commitments with Applications to Zero-Knowledge Sets by Melissa Chase, Alexander Healy, Anna Lysyanskaya, Tal Malkin, and Leonid Reyzin. Appears in Eurocrypt 2005 and Journal of Cryptology 2013.

Memory-Hard Functions and Proofs of Space
- Beyond Hellman's Time-Memory Trade-Offs with Applications to Proofs of Space by Hamza Abusalah, Joël Alwen, Bram Cohen, Danylo Khilko, Krzysztof Pietrzak, and Leonid Reyzin. Appears in Asiacrypt 2017.
- Scrypt is Maximally Memory-Hard by Joël Alwen, Binyi Chen, Krzysztof Pietrzak, Leonid Reyzin, and Stefano Tessaro. Appears in Eurocrypt 2017 (Best Paper Award winner). My talk given at Charles River Crypto Day (Dec. 2016)
- On the Memory-Hardness of Data-Independent Password-Hashing Functions by Joël Alwen, Peter Gaži, Chethan Kamath, Karen Klein, Georg Osang, Krzysztof Pietrzak, Leonid Reyzin, Michal Rolínek, and Michal Rybár. Appears in AsiaCCS 2018

Fuzzy Extractors, Privacy Amplification, Information Reconciliation, and Fuzzy PAKE
- Tutorial on information reconciliation and privacy amplification at IISc-IACR School on Cryptology (has slides and videos)
- Fuzzy Password-Authenticated Key Exchange by Pierre-Alain Dupont, Julia Hesse, David Pointcheval, Leonid Reyzin, and Sophia Yakoubov. Appears in Eurocrypt 2018.
- Wyner's Wire-Tap Channel, Forty Years Later, invited talk I gave at TCC 2015 that provides the historical context for fuzzy extractors and also explains the two papers below.
- When are Fuzzy Extractors Possible by Benjamin Fuller, Leonid Reyzin, and Adam Smith. Appears in IEEE Transactions on Information Theory 66(8): 5282-5298 (2020) (preliminary version in Asiacrypt 2016). See also this talk.
- Reusable Fuzzy Extractors for Low-Entropy Distributions by Ran Canetti, Benjamin Fuller, Omer Paneth, Leonid Reyzin, and Adam Smith. Appears in Journal of Cryptology 34(1) (2021) (preliminary version in Eurocrypt 2016). See also this talk.
- Amplifying Privacy in Privacy Amplification by Divesh Aggarwal, Yevgeniy Dodis, Zahra Jafargholi, Eric Miles, and Leonid Reyzin. Appears in CRYPTO 2014.
- Computational Fuzzy Extractors by Benjamin Fuller, Xianrui Meng, and Leonid Reyzin. Appears Information and Computation 275 (2020) (preliminary version in ASIACRYPT 2013).
- Privacy amplification with asymptotically optimal entropy loss, by Nishanth Chandran, Bhavana Kanukurthi, Rafail Ostrovsky, and Leonid Reyzin. Journal of the ACM 61(5), 2014 (preliminary version in STOC 2010). © by the authors.
- Key Agreement from Close Secrets over Unsecured Channels by Bhavana Kanukurthi and Leonid Reyzin. Appears in Eurocrypt 2009. © by the authors.
- Fuzzy Extractors: A Brief Survey of Results from 2004 to 2006 by Yevgeniy Dodis, Leonid Reyzin, and Adam Smith. Appears as a chapter in Security with Noisy Data.
- Robust Fuzzy Extractors and Authenticated Key Agreement from Close Secrets, by Yevgeniy Dodis, Bhavana Kanukurthi, Jonathan Katz, Leonid Reyzin, and Adam Smith. Appears in IEEE Transactions on Information Theory 2012, merging results from Crypto 2006 and SCN 2008 papers. © by the authors.
- Fuzzy Extractors: How to Generate Strong Keys from Biometrics and Other Noisy Data by Yevgeniy Dodis, Rafail Ostrovsky, Leonid Reyzin, and Adam Smith. In SIAM Journal on Computing, 2008. Preliminary version appears in Eurocrypt 2004 (Test-of-Time Award winner). Implementation available. You may also want to see the related survey.

Correlation-Intractability and Fiat-Shamir Transform
- Fiat-Shamir and Correlation Intractability from Strong KDM-Secure Encryption by Ran Canetti, Yilei Chen, Leonid Reyzin, and Ron D. Rothblum. Appears in Eurocrypt 2018.
- On the Correlation Intractability of Obfuscated Pseudorandom Functions by Ran Canetti, Yilei Chen, and Leonid Reyzin. Appears in TCC 2016-A.

RPKI
- From the Consent of the Routed: Improving the Transparency of the RPKI by Ethan Heilman, Danny Cooper, Leonid Reyzin, and Sharon Goldberg. Appears in SIGCOMM 2014. Implementation available.
- On the Risk of Misbehaving RPKI Authorities by Danny Cooper, Ethan Heilman, Kyle Brogle, Leonid Reyzin, and Sharon Goldberg. Appears in HotNets-XII

Entropy
- A Unified Approach to Deterministic Encryption: New Constructions and a Connection to Computational Entropy by Benjamin Fuller, Adam O'Neill, and Leonid Reyzin. Appears in Journal of Cryptology (preliminary version in TCC 2012). © by the authors. More details of the computational entropy part are in this paper by Benjamin Fuller and Leonid Reyzin.
- Some Notions of Entropy for Cryptography, a short survey paper and invited talk (slides available) at ICITS 2011.
- Conditional Computational Entropy, or Toward Separating Pseudoentropy from Compressibility by Chun-Yuan Hsiao, Chi-Jen Lu, and Leonid Reyzin. Appears in Eurocrypt 2007.

Digital Signatures
- Compact Certificates of Collective Knowledge by Silvio Micali, Leonid Reyzin, Georgios Vlachos, Riad S. Wahby, and Nickolai Zeldovich. To appear in IEEE S&P 2021.
- A Unified Framework for Trapdoor-Permutation-Based Sequential Aggregate Signatures by Craig Gentry, Adam O'Neill, and Leonid Reyzin. Appears in PKC 2018. Talk slides: pptx pdf.
- Sequential Aggregate Signatures with Lazy Verification for S-BGP by Kyle Brogle, Sharon Goldberg, and Leonid Reyzin (includes an implementation). Appears in Information and Computation (preliminary version in ASIACRYPT 2012). © by the authors.
- Sequential Aggregate Signatures from Trapdoor Permutations by Anna Lysyanskaya, Silvio Micali, Leonid Reyzin, and Hovav Shacham. Appears in Eurocrypt 2004.
- Forward-Secure Signatures with Fast Key Update by Anton Kozlov and Leonid Reyzin. Appears in SCN 2002.
- On the Power of Claw-Free Permutations by Yevgeniy Dodis and Leonid Reyzin. Appears in SCN 2002.
- SiBIR: Signer-Base Intrusion-Resilient Signatures by Gene Itkis and Leonid Reyzin. Appears in Crypto 2002.
- Better than Biba: Short One-Time Signatures with Fast Signing and Verifying by Leonid Reyzin and Natan Reyzin. Appears in ACISP 2002.
- Accountable-Subgroup Multisignatures by Silvio Micali, Kazuo Ohta, and Leonid Reyzin. Appears in ACM CCS 2001.
- Forward-Secure Signatures with Optimal Signing and Verifying by Gene Itkis and Leonid Reyzin. Appears in Crypto 2001.
- A New Forward-Secure Digital Signature Scheme by Michel Abdalla and Leonid Reyzin. Appears in Asiacrypt 2000.
- Improving the Exact Security of Digital Signature Schemes by Silvio Micali and Leonid Reyzin. Appears in Journal of Cryptology, 2002 (prior version appears in CQRE [Secure] '99).
- Signing with Partially Adversarial Hashing by Silvio Micali and Leonid Reyzin. Appears as MIT/LCS/TM-575, 1998.

Leakage-Resilient Cryptography and Other Non-Black-Box Attack Models
- A Survey of Leakage-Resilient Cryptography by Yael Tauman Kalai and Leonid Reyzin. Appears in Providing Sound Foundations for Cryptography: On the work of Shafi Goldwasser and Silvio Micali, a volume edited by Oded Goldreich.
- Protecting Circuits from Computationally Bounded and Noisy Leakage by Sebastian Faust, Tal Rabin, Leonid Reyzin, Eran Tromer, and Vinod Vaikuntanathan. SIAM Journal on Computing 43(5), 2014 (preliminary version in Eurocrypt 2010). © by the authors.
- Physically Observable Cryptography by Silvio Micali and Leonid Reyzin. Appears in TCC 2004 (Test-of-Time Award winner).
- On the Round Security of Symmetric-Key Cryptographic Primitives by Zulfikar Ramzan and Leonid Reyzin. Appears in Crypto 2000.
Hash Functions
- Indifferentiability of Permutation-Based Compression Functions and Tree-Based Modes of Operation, with Applications to MD6 by Yevgeniy Dodis, Leonid Reyzin, Ronald L. Rivest, and Emily Shen. Appears in FSE 2009.
- Finding Collisions on a Public Road, or Do Secure Hash Functions Need Secret Coins by Chun-Yuan Hsiao and Leonid Reyzin. Appears in Crypto 2004.

Pseudorandom Generators
- Saving Private Randomness in One-Way Functions and Pseudorandom Generators by Nenad Dedić, Danny Harnik, and Leonid Reyzin. Appears in TCC 2008.
- An Improved Pseudorandom Generator Based on Hardness of Factoring by Nenad Dedić, Leonid Reyzin, and Salil Vadhan. Appears in SCN 2002.
Resettable Zero-Knowledge
- Zero-Knowledge with Public Keys. My MIT Ph.D. thesis, 2001. It mostly consists of the results in the following two papers:
  - Soundness in the Public-Key Model by Silvio Micali and Leonid Reyzin. Appears in Crypto 2001.
  - Min-Round Resettable Zero-Knowledge in the Public-Key Model by Silvio Micali and Leonid Reyzin. Appears in Eurocrypt 2001.

Steganography
- Upper and Lower Bounds on Black-Box Steganography by Nenad Dedić, Gene Itkis, Leonid Reyzin, and Scott Russell. Appears in Journal of Cryptology; preliminary version appears in TCC 2005.

Miscellaneous
- A Note On the Statistical Difference of Small Direct Products by Leonid Reyzin. Appears as BUCS-TR-2004-032, 2004.
- Breaking and Repairing Optimistic Fair Exchange from PODC 2003 by Yevgeniy Dodis and Leonid Reyzin. Appears in DRM 2003.
- Mutually Independent Commitments by Moses Liskov, Anna Lysyanskaya, Silvio Micali, Leonid Reyzin, and Adam Smith. Appears in Asiacrypt 2001.
- Verifying Membership in NP-languages, or How to Avoid Reading Long Proofs. My Harvard honors senior thesis, 1996.