Learning With Errors
Ring- or Module-LWE-specific hardness questions.
| Status | Statement | Tags |
|---|---|---|
|
CPA PKE, Quantumly Broken The first item in the source’s Open Problems section. It builds counterexamples for PRFs, CPA-secure symmetric-key encryption, MACs, signatures and CCA-2-secure public-key encryption, all classically secure under LWE via black-box reductions and all quantumly broken with two or three classical queries. CPA-secure public-key encryption is the case its technique cannot reach, and it says why. 4 open |
Black Box SeparationsLearning With ErrorsQuantum Cryptographyseparation | |
|
1+1 adaptively secure lattice threshold signature Resolved. Oriole (Jiang, Wee, Zhu, ePrint 2026/793, posted April 2026, a month after Tweed) gives a lattice-based threshold signature with exactly this shape – two rounds, only the second message-dependent, adaptive security against T-1 corruptions with no erasures, from MSIS and MLWE in the ROM – verified here directly against the paper’s PDF (Definition of adp-TS-sUF-4 in its Figure 4, and the Theorem 2 + Theorem 3 reduction chain to MSIS), not just its abstract. The proof is human-written and published, but not yet independently re-verified line-by-line by this site, nor formalized in Lean. |
Learning With ErrorsThreshold SignaturesTight Reductionsromseparationresearch-solved | |
|
Ring-LWE error parity Open: whether recovering the Ring-LWE error modulo two is as hard as recovering the error itself. The easy direction is trivial; the source states it has no formal reduction for this one and relies on two heuristics instead, one of which changes the error distribution. 6 open |
Learning With Errorsequivalence | |
|
Single-session lattice Chevallier-Mames tightness Open: whether the one-session lattice translation of the Chevallier-Mames signature has a tight SUF-CMA reduction to search Module-LWE, or whether the paper’s two-fold parallel repetition (which doubles signature size and signing time) is inherent to a tight proof of this shape. 4 open |
Learning With ErrorsSignature SchemesTight Reductionsromtight-bound |
No matching items