About

Leonid Reyzin is a professor of Computer Science at Boston University in the College of Arts and Sciences. His primary research interest is cryptography, and he is an active member of the BU Security Group. He is also recognized as a Fellow of the International Association for Cryptologic Research (IACR). Throughout his career, Professor Reyzin has contributed to various aspects of cryptography, including verifiable random functions, vector commitments, finite-field arithmetic, polynomial interpolation, authenticated data structures, and privacy-enhancing technologies. He has developed multiple implementations in Rust and Java related to cryptographic protocols and data structures, demonstrating a strong focus on both theoretical and practical aspects of cryptography. In addition to his research, Professor Reyzin is deeply involved in teaching advanced cryptography courses and has delivered numerous tutorials and survey talks on topics such as information reconciliation, privacy amplification, computational entropy, and pseudorandomness. He has also played significant roles in organizing and chairing major cryptography conferences, including serving as co-chair of the Crypto 2024 Program Committee and general chair of Eurocrypt 2019. His academic mentorship includes supervising Ph.D. students and postdoctoral researchers, contributing to the development of the next generation of cryptographers.

Research topics

• Computer Science
• Computer Security
• Artificial Intelligence
• Thermodynamics
• Physics
• Statistics
• Mathematics

Selected publications

• Approximate Lower Bound Arguments

  Lecture notes in computer science · 2024-01-01 · 2 citations

  book-chapterOpen access
  PublisherOA PDFDOI

• Proofs of Space with Maximal Hardness

  2024-10-27 · 1 citations

  article1st authorCorresponding

  In a proof of space, a prover performs a complex computation with a large output. A verifier periodically checks that the prover still holds the output. The security goal for a proof of space construction is to ensure that a prover who erases even a portion of the output has to redo a large portion of the complex computation in order to satisfy the verifier. In existing constructions of proofs of space, the computation that a cheating prover is forced to redo is a small fraction (van-ishing or small constant) of the original complex computation. The only exception is a construction of Pietrzak (ITCS 2019) that requires extremely depth-robust graphs, which result in impractically high complexity of the initialization process. We present the first proof of space of reasonable complexity that ensures that the prover has to redo almost the entire computation (fraction arbitrarily close to 1) when trying to save even an arbitrarily small constant fraction of the space. Our construction is a generalization of an existing construction called SDR (Fisch, Eurocrypt 2019) deployed on the Filecoin blockchain. Our improvements, while general, also demonstrate that the already deployed construction has considerably better security than previously shown. Technically, our construction can be viewed as amplifying predecessor-robust graphs. These are directed acyclic graphs in which every sufficiently large set of nodes contains a large subset of nodes whose induced sub graph has just one sink. We take a predecessor-robust graph with constant-fraction parameters for the sizes of the set and subset, and build a bigger predecessor-robust graph with a near-optimal set of parameters and additional guarantees on sink placement, while increasing the degree only by a small additive constant.

  PublisherDOI

• Approximate lower bound arguments

  OpenBU (Boston University) · 2024-05-26

  other1st authorCorresponding

  Accepted manuscript

  Publisher

• Verifiable Random Functions (VRFs)

  2023-08-01 · 29 citations

  reportOpen access

  A Verifiable Random Function (VRF) is the public-key version of a
\n keyed cryptographic hash. Only the holder of the private key can
\n compute the hash, but anyone with public key can verify the
\n correctness of the hash. VRFs are useful for preventing enumeration
\n of hash-based data structures. This document specifies several VRF
\n constructions that are secure in the cryptographic random oracle
\n model. One VRF uses RSA and the other VRF uses Eliptic Curves (EC).

  PublisherOA PDFDOI

• Turning HATE into LOVE: Compact Homomorphic Ad Hoc Threshold Encryption for Scalable MPC

  Lecture notes in computer science · 2021-01-01 · 11 citations

  book-chapter1st author
  PublisherDOI

• Compact Certificates of Collective Knowledge

  2021-05-01 · 19 citations

  article

  We introduce compact certificate schemes, which allow any party to take a large number of signatures on a message M, by many signers of different weights, and compress them to a much shorter certificate. This certificate convinces the verifiers that signers with sufficient total weight signed M, even though the verifier will not see—let alone verify—all of the signatures. Thus, for example, a compact certificate can be used to prove that parties who jointly have a sufficient total account balance have attested to a given block in a blockchain.After defining compact certificates, we demonstrate an effi-cient compact certificate scheme. We then show how to implement such a scheme in a decentralized setting over an unreliable network and in the presence of adversarial parties who wish to disrupt certificate creation. Our evaluation shows that compact certificates are 50–280× smaller and 300–4000 cheaper to verify than a natural baseline approach.

  PublisherDOI

• Can a Blockchain Keep a Secret

  IACR Cryptology ePrint Archive · 2020-01-01 · 5 citations

  preprintSenior author
  Publisher

• Compact Certificates of Collective Knowledge.

  DSpace@MIT (Massachusetts Institute of Technology) · 2020-01-01

  preprintOpen access

  We introduce compact certificate schemes, which allow any party to take a large number of signatures on a message M, by many signers of different weights, and compress them to a much shorter certificate. This certificate convinces the verifiers that signers with sufficient total weight signed M, even though the verifier will not see—let alone verify—all of the signatures. Thus, for example, a compact certificate can be used to prove that parties who jointly have a sufficient total account balance have attested to a given block in a blockchain.After defining compact certificates, we demonstrate an effi-cient compact certificate scheme. We then show how to implement such a scheme in a decentralized setting over an unreliable network and in the presence of adversarial parties who wish to disrupt certificate creation. Our evaluation shows that compact certificates are 50–280× smaller and 300–4000 cheaper to verify than a natural baseline approach.

  PublisherOA PDF

• Can a Public Blockchain Keep a Secret?

  Lecture notes in computer science · 2020 · 87 citations

  Senior authorCorresponding
  • Computer Science
  • Computer Science
  • Computer Security
  PublisherDOI

• Pointproofs: Aggregating Proofs for Multiple Vector Commitments

  2020-10-30 · 5 citations

  preprint

  Vector commitments enable a user to commit to a sequence of values and provably reveal one or many values at specific posi- tions at a later time. In this work, we construct Pointproofs? a new vector commitment scheme that supports non-interactive aggregation of proofs across multiple commitments. Our construction enables any third party to aggregate a collection of proofs with respect to different, independently computed commitments into a single proof represented by an elliptic curve point of 48-bytes. In addition, our scheme is hiding: a commitment and proofs for some values reveal no information about the remaining values. We build Pointproofs and demonstrate how to apply them to blockchain smart contracts. In our example application, Pointproofs reduce bandwidth overheads for propagating a block of transactions by at least 60% compared to prior state- of-art vector commitments. Pointproofs are also efficient: on a single-thread, it takes 0.08 seconds to generate a proof for 8 values with respect to one commitment, 0.25 seconds to aggregate 4000 such proofs across multiple commitments into one proof, and 23 seconds (0.7 ms per value proven) to verify the aggregated proof.

  PublisherDOI

Recent grants

• CAREER: Cryptography Outside the Box

  NSF · $419k · 2006–2012

• TWC: Small: Noisy Secrets as Alternatives to Passwords and PKI

  NSF · $500k · 2014–2019

• Collaborative Research: Rigorous Cryptography from Biometrics and Other Noisy Data

  NSF · $100k · 2005–2008

Frequent coauthors

• Yevgeniy Dodis

  17 shared

• Adam Smith

  17 shared

• Sharon Goldberg

  16 shared

• Silvio Micali

  16 shared

• Nenad Dedić

  16 shared

• Benjamin Fuller

  University of Connecticut

  15 shared

• Bhavana Kanukurthi

  Indian Institute of Science Bangalore

  11 shared

• Anna Lysyanskaya

  John Brown University

  10 shared

Labs

• Data Mining & Data ManagementPI

Education

• Ph.D.

  MIT

Awards & honors

• NSF CAREER Award
• Boston University’s Neu Family Award for Excellence in Teach…