Lightnews — Scholar-powered news

Chris Peikert @chrispeikert.bsky.social · 2h

Our protocol is simple & modular: it works in the "Arithmetic Black Box" model, and inherits the security properties of the ABB instantiation (passive/active, static/adaptive, etc.).

Using SPDℤ₂𝑘 for ABB, we get about 20,000x and 37x better throughput and latency than SoTA for dishonest majority.

Chris Peikert @chrispeikert.bsky.social · 2h

Several prior threshold decryption protocols use "noise flooding" for security, but this has a high cost in parameters and efficiency.

Instead, we give an efficient MPC "rounding" protocol. It prepares special "gates" offline, and has quite low communication and computation in the online phase.

1

Chris Peikert @chrispeikert.bsky.social · 2h

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

1 3

Chris Peikert @chrispeikert.bsky.social · 1d

Prior work used fairly simple weights. We define much "smoother" ones (e.g., Gaussian or Laplacian), and use Fourier analysis on a certain lattice to show that these weights have large enough "correlation" with any nearby codeword.

Check it out!: web.eecs.umich.edu/~cpeikert/pu...

web.eecs.umich.edu

1

Chris Peikert @chrispeikert.bsky.social · 1d

The key technique (as in our prior work with Ethan Mook on decoding in the ℓ₂ metric) is to use the Guruswami--Sudan 𝒔𝒐𝒇𝒕-𝒅𝒆𝒄𝒊𝒔𝒊𝒐𝒏 list decoder.

For this we need to transform the received word into "weights" that specify, for each coordinate, a "confidence level" for each potential codeword symbol.

1

Chris Peikert @chrispeikert.bsky.social · 1d

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

1

Chris Peikert @chrispeikert.bsky.social · 1d

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

1 5

Chris Peikert @chrispeikert.bsky.social · 3d

This was an hour ago!

Chris Hayes @chrislhayes.bsky.social · 3d

This game is deranged.

1 1

Reposted by Chris Peikert

Jameel Jaffer @jameeljaffer.bsky.social · 4d

MIT's response to the Trump admin's proposed "compact" is excellent and should be a model for other universities. orgchart.mit.edu/letters/rega...

9 220 570

Chris Peikert @chrispeikert.bsky.social · 5d

FHE everywhere

1 1

Reposted by Chris Peikert

ePrint Updates @eprint.ing.bot · 6d

FrodoKEM: A CCA-Secure Learning With Errors Key Encapsulation Mechanism (Lewis Glabush, Patrick Longa, Michael Naehrig, Chris Peikert, Douglas Stebila, Fernando Virdia) ia.cr/2025/1861

Abstract. Large-scale quantum computers capable of implementing Shor’s algorithm pose a significant threat to the security of the most widely used public-key cryptographic schemes. This risk has motivated substantial efforts by standards bodies and government agencies to identify and standardize quantum-safe cryptographic systems. Among the proposed solutions, lattice-based cryptography has emerged as the foundation for some of the most promising protocols. This paper describes FrodoKEM, a family of conservative key-encapsulation mechanisms (KEMs) whose security is based on generic, “unstructured” lattices. FrodoKEM is proposed as an alternative to the more efficient lattice schemes that utilize algebraically structured lattices, such as the recently standardized ML-KEM scheme. By relying on generic lattices, FrodoKEM minimizes the potential for future attacks that exploit algebraic structures while enabling simple and compact implementations. Our plain C implementations demonstrate that, despite its conservative design and parameterization, FrodoKEM remains practical. For instance, the full protocol at NIST security level 1 runs in approximately 0.97 ms on a server-class processor, and 4.98 ms on a smartphone-class processor. FrodoKEM obtains (single-target) IND-CCA security using a variant of the Fujisaki-Okamoto transform, applied to an underlying public-key encryption scheme called FrodoPKE. In addition, using a new tool called the Salted Fujisaki-Okamoto (SFO) transform, FrodoKEM is also shown to tightly achieve multi-target security, without increasing the FrodoPKE message length and with a negligible performance impact, based on the multi-target IND-CPA security of FrodoPKE.

2 4

Reposted by Chris Peikert

Judd Legum @juddlegum.bsky.social · 8d

1. Federal agents from ICE and other agencies are wrongly detaining U.S. citizens, sometimes detaining them for days, on suspicion that they are undocumented immigrants.

The raids are done without search warrants or other procedures designed to protect civil liberties.

How federal agents are terrorizing American citizens

Last week, hundreds of heavily armed federal agents descended on an apartment complex in Chicago, arriving in Black Hawk helicopters and moving trucks.

popular.info

54 820 1.6K

Reposted by Chris Peikert

Kristina Cooke @kristinacooke.bsky.social · 10d

I spoke to a Venezuelan woman who was arrested in this raid and later released with her 4yo son. She said agents broke down their door, pointed guns at them and made sexualized remarks about Venezuelan women. When she returned to her apartment it was boarded up and all her possessions were gone.

Ted Hesson @tedhesson.bsky.social · 10d

US Border Patrol raid sweeps in citizens, families as Chicago crackdown intensifies, w/ @reneehickman.bsky.social @kristinacooke.bsky.social www.reuters.com/world/us/us-...

US Border Patrol raid sweeps in citizens, families as Chicago crackdown intensifies

U.S. Border Patrol agents deployed to Chicago led a late-night raid on an apartment building this week, rappelling from helicopters onto rooftops and breaking down doors in an operation authorities said targeted gang members but which swept up U.S. citizens and families.

www.reuters.com

240 3.3K 5.6K

Reposted by Chris Peikert

Governor JB Pritzker @govpritzker.illinois.gov · 10d

This morning, the Trump Administration’s Department of War gave me an ultimatum: call up your troops, or we will. It is absolutely outrageous and un-American to demand a Governor send military troops within our own borders and against our will.

1.5K 7.4K 24K

Reposted by Chris Peikert

Governor JB Pritzker @govpritzker.illinois.gov · 10d

Yesterday, Kristi Noem’s and Greg Bovino’s masked agents threw chemical agents near an elementary school, arrested elected officials exercising their First Amendment rights, and raided a Wal-Mart.

74 1.1K 4.5K

Reposted by Chris Peikert

ePrint Updates @eprint.ing.bot · 11d

High-Throughput Universally Composable Threshold FHE Decryption (Guy Zyskind, Doron Zarchy, Max Leibovich, Chris Peikert) ia.cr/2025/1781

Abstract. 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,000× better throughput, and up to a 37× improvement in latency.

1 3

Reposted by Chris Peikert

Chris Peikert @chrispeikert.bsky.social · 11d

We will Make this deadline, very strongly, because we are WINNERS—but Europe and the Rest of the world will have to pay up BIGLY with the strongest and Most polished Best Paper awards! That is the least these low IQ individuals can do to Pay back what we Americans so richly deserve!

2 6

Chris Peikert @chrispeikert.bsky.social · 11d

We will Make this deadline, very strongly, because we are WINNERS—but Europe and the Rest of the world will have to pay up BIGLY with the strongest and Most polished Best Paper awards! That is the least these low IQ individuals can do to Pay back what we Americans so richly deserve!

2 6

Chris Peikert @chrispeikert.bsky.social · 11d

💯

3

Chris Peikert @chrispeikert.bsky.social · 11d

Other countries in Europe are LAUGHING at us, with their “Midnight Anywhere on Earth” conference submission Deadlines!!

They’re finishing their papers and taking off for the Weekend at 2pm Friday, while we Americans have to pull ALL-NIGHTERS!

Not on my (your favorite PC chair) watch—MAGTBAARHA!

2 1 5

Reposted by Chris Peikert

Soren Spicknall @sorenspicknall.bsky.social · 12d

"Rodrick Johnson, 67, is one of many residents who were detained by federal agents during the South Shore raid. A U.S. citizen, he said agents broke through his door and dragged him out in zip ties."

Massive immigration raid on Chicago apartment building leaves residents reeling: 'I feel defeated'

The Department of Homeland Security said federal agents with Border Patrol, the FBI and the Bureau of Alcohol, Tobacco, Firearms and Explosives arrested 37 people in the raid.

chicago.suntimes.com

43 510 770

Reposted by Chris Peikert

ePrint Updates @eprint.ing.bot · 15d

Vive Galois! Part 1: Optimal SIMD Packing and Packed Bootstrapping for FHE (Chris Peikert, Zachary Pepin) ia.cr/2025/1760

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.

Toward this end, this (two-part) work makes the following main technical contributions, all of which are catalyzed by Galois theory:

– For sampling and decoding errors in encryption and decryption (respectively), we construct geometrically short, structured bases for the number rings of arbitrary subfields of prime-power cyclotomics (and hence their composites as well).

– For fast ring arithmetic, we define and establish analogous structural properties for Chinese Remainder Theorem (CRT) bases in abelian number rings, and give specialized fast transforms that map between CRT bases and any similarly structured bases.

– For packed bootstrapping and homomorphic linear algebra, we give a general framework for homomorphic evaluation of structured linear transforms in abelian number rings, and show that CRT transforms can be evaluated using relatively few homomorphic operations.

1 1

Chris Peikert @chrispeikert.bsky.social · 18d

We think these tools will have many more benefits and applications in FHE and beyond, like homomorphic linear algebra, proof systems, etc.

(And in any case, the underlying math is beautiful! 🤓)

Check it out here: web.eecs.umich.edu/~cpeikert/pu...

web.eecs.umich.edu

3

Chris Peikert @chrispeikert.bsky.social · 18d

Most notably, we get 𝙤𝙥𝙩𝙞𝙢𝙖𝙡 SIMD plaintext packing for 𝘢𝘯𝘺 desired finite-field slot type, and efficient 𝙥𝙖𝙘𝙠𝙚𝙙 𝙗𝙤𝙤𝙩𝙨𝙩𝙧𝙖𝙥𝙥𝙞𝙣𝙜 that exploits this parallelism.

Key tools: 𝘴𝘵𝘳𝘶𝘤𝘵𝘶𝘳𝘦𝘥 (short & CRT) ring bases, and efficient 𝘊𝘙𝘛 𝘵𝘳𝘢𝘯𝘴𝘧𝘰𝘳𝘮𝘴—both "in the clear," and homomorphically using automorphisms.

1 1

Chris Peikert @chrispeikert.bsky.social · 18d

This is our starting point.

We adopt the very general setting of 𝙖𝙗𝙚𝙡𝙞𝙖𝙣 (Galois) number fields—which by Kronecker–Weber are equivalent to cyclotomic subfields—and give a broad collection of tools for doing lattice-based crypto and FHE in them.

1 1