Chris Peikert

@chrispeikert.bsky.social

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

A house finch nest with three little eggs tucked into the corner of an open office window.

The Vince McMahon meme listing Rosulek's "most opinionated choices" in the book's presentation:

1. all security definitions are distinguishing games;
2. the b=0 and b=1 branches are two separate games (rather than having the adversary guess a hidden bit b);
3. we don't write explicit reduction algorithms when adjacent hybrids are indistinguishable due to a cryptographic assumption.

Cover of “The Joy of Cryptography” by Mike Rosulek

Spelling Bee choice of CODOMAIN: “not in word list”

Title: High-Throughput Universally Composable Threshold FHE Decryption

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

$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.$

$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).$