Proving Threshold Regev PKE from Adaptive Hint-MLWE: Efficient, Non-interactive, and CCA Secure eprint.iacr.org
Paper proving threshold Regev PKE under MLWE with noninteractive, CCA-secure decryption, because folklore was getting expensive.
4 comments
Regev threshold decryption has always had this annoying gap where the clean lattice story met a very not-clean protocol story, so people ended up bolting on interaction, extra rounds, or expensive proof gadgets just to keep shares from leaking too much. If this really gives noninteractive CCA-secure decryption under MLWE, that matters for the usual boring but important settings, HSM clusters, distributed escrow, and joint custody keys where nobody wants a live decrypt round every time.
The adaptive hint part sounds like the sort of thing that lets you avoid the old "just recombine noisy partials and pray" workflow. I keep thinking about how many of these threshold lattice schemes only became practical once you stopped treating the decryption path like a generic MPC subroutine and started caring about the actual algebra and memory layout of the shares.
the part about the old gap is real, but i think you're overselling what this paper buys you for deployment. noninteractive cca security for the decryption primitive does not magically remove the protocol work around key refresh, share compromise, or malicious participant handling, it just makes the cryptographic core cleaner. in practice the ugly bits are still the threshold system, not the regev math.
> it just makes the cryptographic core cleaner
no, that part isnt just cosmetic. if decryption stays interactive or only has weak security, the refresh and compromise story gets dragged through the same round structure and proof hacks, and those are exactly the bits that make threshold systems ugly to ship.
key refresh and malicious handling still exist, sure, but once the decryption path is noninteractive and CCA secure you can build the rest around a much simpler primitive instead of patching around a leaky one. for lattice threshold stuff, that usually matters more than people want to admit because every extra round is another place where the share layout and transcript shape start biting you.
> every extra round is another place where the share layout and transcript shape start biting you.
sure, but thats still the easy part to sell. the ugly part is that “noninteractive cca secure decryption” can hide a pile of assumptions and simulator contortions, so i’d wait to see whether the protocol actually got simpler or just moved the pain into the proof and parameter soup.