Lightnews — Scholar-powered news

Chris Peikert

@chrispeikert.bsky.social

Cryptographer (lattices/post-quantum), Professor at U-Michigan Computer Science and Engineering , Head of Cryptography Research at Algorand, PhD from MIT CSAIL. Previously faculty at Georgia Tech School of CS. Here I speak for myself.

Posts Replies Media Videos

Chris Peikert

@chrispeikert.bsky.social

⚡New paper⚡, with Guy Zyskind, Doron Zarchy, and Max Leibovich of Fhenix, presented today at ACM CCS.

We give an efficient 𝒕𝒉𝒓𝒆𝒔𝒉𝒐𝒍𝒅 𝒅𝒆𝒄𝒓𝒚𝒑𝒕𝒊𝒐𝒏 protocol for FHE/LWE with: no "noise flooding" or parameter loss, simulation (UC) security, and high throughput.

web.eecs.umich.edu/~cpeikert/pu...

Title: High-Throughput Universally Composable Threshold FHE Decryption

by Guy Zyskind, Doron Zarchy, Max Leibovich, and Chris Peikert

Threshold Fully Homomorphic Encryption (FHE) enables arbitrary computation on encrypted data, while distributing the decryption capability across multiple parties.
A primary application of interest is low-communication multi-party computation (MPC), which benefits from a fast and secure threshold FHE decryption protocol.

Several works have addressed this problem, but all existing solutions rely on "noise flooding" for security.
This incurs significant overhead and necessitates large parameters in practice, making it unsuitable for many real-world deployments.
Some constructions have somewhat better efficiency, but at the cost of weaker, non-simulation-based security definitions, which limits their usability and composability.

In this work, we propose a novel threshold FHE decryption protocol that avoids "noise flooding" altogether, and provides simulation-based security.
Rather than masking the underlying ciphertext noise, our technique securely removes it via an efficient MPC rounding procedure.
The cost of this MPC is mitigated by an offline/online design that preprocesses special gates for secure comparisons in the offline phase, and has low communication and computation in the online phase.
This approach is of independent interest, and should also benefit other MPC protocols (e.g., secure machine learning) that make heavy use of non-linear comparison operations.

We prove our protocol secure in the Universal Composability (UC) framework, and it can be generally instantiated for a variety of adversary models (e.g., security-with-abort against a dishonest majority, or guaranteed output delivery with honest majority).
Compared to the state of the art, our protocol offers significant gains both in the adversary model (i.e., dishonest vs. honest majority) and practical performance: empirically, our online phase obtains approximately 20,000x better throughput, and up to a 37x improvement in latency.

October 14, 2025 at 3:40 PM

Chris Peikert

@chrispeikert.bsky.social

Most notably: compared to prior work, our algorithm can decode to 𝒂𝒓𝒃𝒊𝒕𝒓𝒂𝒓𝒊𝒍𝒚 𝒍𝒂𝒓𝒈𝒆 distances, for correspondingly small rates. Moreover, we show that our algorithm is a 𝒖𝒏𝒊𝒒𝒖𝒆 decoder for many parameters of interest.

Here are some plots of the distance-rate tradeoffs and the uniqueness thresholds.

$Plots of the distance-rate tradeoffs of our (list-)decoding algorithm as compared with previous ones for Reed--Solomon codes in the $\ell_2$ and $\ell_1$ metrics.$

October 13, 2025 at 2:53 PM

Chris Peikert

@chrispeikert.bsky.social

⚡New paper⚡, with Alexandra Veliche Hostetler!

We give a list-decoding algorithm for Reed-Solomon codes, where the error is measured in the Euclidean (ℓ₂) or Lee (ℓ₁) metrics, rather than the Hamming metric (as is more typical).

web.eecs.umich.edu/~cpeikert/pu...

$Title: List Decoding Reed--Solomon Codes in the Lee, Euclidean, and Other Metrics Abstract: Reed--Solomon error-correcting codes are ubiquitous across computer science and information theory, with applications in cryptography, computational complexity, communication and storage systems, and more. Most works on efficient error correction for these codes, like the celebrated Berlekamp--Welch unique decoder and the (Guruswami--)Sudan list decoders, are focused on measuring error in the Hamming metric, which simply counts the number of corrupted codeword symbols. However, for some applications, other metrics that depend on the specific values of the errors may be more appropriate. This work gives a polynomial-time algorithm that list decodes (generalized) Reed--Solomon codes over prime fields in $\ell_p$ (semi)metrics, for any $0 < p \leq 2$. Compared to prior algorithms for the Lee ($\ell_1$) and Euclidean ($\ell_2$) metrics, ours decodes to arbitrarily large distances (for correspondingly small rates), and has better distance-rate tradeoffs for all decoding distances above some moderate thresholds. We also prove lower bounds on the $\ell_{1}$ and $\ell_{2}$ minimum distances of a certain natural subclass of GRS codes, which establishes that our list decoder is actually a unique decoder for many parameters of interest. Finally, we analyze our algorithm's performance under *random* Laplacian and Gaussian errors, and show that it supports even larger rates than for corresponding amounts of worst-case error in $\ell_{1}$ and $\ell_{2}$ (respectively).$

October 13, 2025 at 2:53 PM

Chris Peikert

@chrispeikert.bsky.social

Thrilled to finally share this ⚡𝙣𝙚𝙬 𝙥𝙖𝙥𝙚𝙧⚡ with my (now-graduated!) student Zachary Pepin, which will appear at TCC 2025.

We tackle a frequent inconvenience in BGV/BFV-style homomorphic encryption: getting the desired kind of "SIMD slots" for plaintext packing. 🧵

web.eecs.umich.edu/~cpeikert/pu...

Screenshot of the title and abstract of the paper "Vive Galois! Part 1: Optimal SIMD Packing and Packed Bootstrapping for FHE", by Chris Peikert and Zachary Pepin.

Abridged abstract:

The vast majority of work on the efficiency of lattice-based cryptography, including fully homomorphic encryption (FHE), has relied on cyclotomic number fields and rings.
This is because cyclotomics offer a wide variety of benefits, including good geometrical properties, fast ring arithmetic, and rich homomorphic operations like vectorized (SIMD) operations on "packed" plaintexts, automorphisms, and ring-switching.
However, selecting a suitable cyclotomic that has the desired number and type of plaintext "slots," while also balancing security and efficiency, is a highly constrained problem that often lacks an ideal solution, resulting in wasted SIMD capacity and lost efficiency.

This work provides a suite of tools for instantiating ring-based lattice cryptography to work over *subfields* of cyclotomics, which provide more flexibility and better-fitting parameters for applications.
A particular focus is on realizing FHE with *optimal plaintext packing* and homomorphic SIMD parallelism for *any* plaintext characteristic, along with efficient packed bootstrapping that fully exploits this parallelism.

September 26, 2025 at 2:28 PM

Chris Peikert

@chrispeikert.bsky.social

This is Ted Chiang erasure, Spelling Bee.

A Spelling Bee entry of the (pangram) word HEPTAPOD, which is the name of the aliens in Ted Chiang’s story “Story of Your Life”

September 14, 2025 at 12:26 PM

Chris Peikert

@chrispeikert.bsky.social

CAVE CANEM (beware of dog)

August 13, 2025 at 8:24 PM

Chris Peikert

@chrispeikert.bsky.social

Two cats cuddled up with each other on a blue chair and multi-colored pillow

Two kittens cuddled up with a dog on a bean-bag chair

July 14, 2025 at 9:58 PM

Chris Peikert

@chrispeikert.bsky.social

This is a great and moving story.

Last 4th of July in Seattle I came across a huge naturalization ceremony—hundreds of people from all over the world officially becoming Americans. More of this!