Path: ...!eternal-september.org!feeder3.eternal-september.org!news.eternal-september.org!eternal-september.org!.POSTED!not-for-mail From: IACR ePrint Archive Newsgroups: sci.crypt Subject: [digest] 2025 Week 10 Date: Mon, 10 Mar 2025 02:23:20 -0000 Organization: A noiseless patient Spider Lines: 1641 Message-ID: MIME-Version: 1.0 Content-Type: text/plain; charset="utf-8" Content-Transfer-Encoding: quoted-printable Injection-Date: Mon, 10 Mar 2025 03:23:24 +0100 (CET) Injection-Info: dont-email.me; posting-host="ef01649f51671dcaff820830aa683f9d"; logging-data="1092187"; mail-complaints-to="abuse@eternal-september.org"; posting-account="U2FsdGVkX1/m/UqQFeb8p/hIamKKKXRM2zSV1atpwgc=" Cancel-Lock: sha1:v79sXFjj6hfOGafp/Pk8e6dobgs= Bytes: 87142 ## In this issue 1. [2024/1589] A Systematic Study of Sparse LWE 2. [2025/196] Endomorphisms for Faster Cryptography on Elliptic ... 3. [2025/374] Simple and General Counterexamples for Private-Coin ... 4. [2025/385] MERCURY: A multilinear Polynomial Commitment Scheme ... 5. [2025/395] Provably Secure Approximate Computation Protocols ... 6. [2025/396] Trail-Estimator: An Automated Verifier for ... 7. [2025/397] Blind Signatures from Cryptographic Group Actions 8. [2025/398] Tight Adaptive Simulation Security for Identity- ... 9. [2025/399] Computational Quantum Anamorphic Encryption and ... 10. [2025/400] Re-Randomize and Extract: A Novel Commitment ... 11. [2025/401] PEGASIS: Practical Effective Class Group Action ... 12. [2025/402] Related-Key Differential and Boomerang ... 13. [2025/403] Periodic Table of Cryptanalysis: Geometric Approach ... 14. [2025/404] SNARKs for Stateful Computations on Authenticated Data 15. [2025/405] Withdrawable signatures in Fiat-Shamir with aborts ... 16. [2025/406] AsyRand: fast asynchronous distributed randomness ... 17. [2025/407] Delegatable ABE with Full Security from Witness ... 18. [2025/408] Hybrid Obfuscated Key Exchange and KEMs 19. [2025/409] Low Communication Threshold FHE from Standard ... 20. [2025/410] TreeKEM: A Modular Machine-Checked Symbolic ... 21. [2025/411] Security of the Ascon Authenticated Encryption Mode ... 22. [2025/412] Multi-Authority Functional Encryption: Corrupt ... 23. [2025/413] Garblet: Multi-party Computation for Protecting ... 24. [2025/414] Deimos Cipher: A High-Entropy, Secure Encryption ... 25. [2025/415] On the Soundness of Algebraic Attacks against Code- ... 26. [2025/416] Trapdoor Hash Functions and PIR from Low-Noise LPN 27. [2025/417] Evaluation of Privacy-aware Support Vector Machine ... 28. [2025/418] ProofFrog: A Tool For Verifying Game-Hopping Proofs 29. [2025/419] Samaritan: Linear-time Prover SNARK from New ... 30. [2025/420] Non-Interactive Verifiable Aggregation 31. [2025/421] A Note on Obfuscation-based Attacks on Private-coin ... 32. [2025/422] Private Computation on Common Fuzzy Records 33. [2025/423] Multi-Client Attribute-Based Unbounded Inner ... 34. [2025/424] Matchmaker: Fast Secure Inference across Deployment ... 35. [2025/425] A Note on the Blindness of the Scheme from ePrint ... 36. [2025/426] Exploring How to Authenticate Application Messages ... 37. [2025/427] BUFFing Threshold Signature Schemes 38. [2025/428] On Improved Cryptanalytic Results against ChaCha ... 39. [2025/429] Enhanced CKKS Bootstrapping with Generalized ... 40. [2025/430] Non-interactive Anonymous Tokens with Private ... 41. [2025/431] Commitment Schemes Based on Module-LIP 42. [2025/432] Black-Box (and Fast) Non-Malleable Zero Knowledge 43. [2025/433] MIDAS: an End-to-end CAD Framework for Automating ... 44. [2025/434] Fine-Grained Verifier NIZK and Its Applications 45. [2025/435] Constant-Time Code: The Pessimist Case 46. [2025/436] The Algebraic One-More MISIS Problem and ... 47. [2025/437] Improved Cryptanalysis of ChaCha: Beating PNBs with ... ## 2024/1589 * Title: A Systematic Study of Sparse LWE * Authors: Aayush Jain, Huijia Lin, Sagnik Saha * [Permalink](https://eprint.iacr.org/2024/1589) * [Download](https://eprint.iacr.org/2024/1589.pdf) ### Abstract In this work, we introduce the sparse LWE assumption, an assumption that draw= s inspiration from both Learning with Errors (Regev JACM 10) and Sparse Learn= ing Parity with Noise (Alekhnovich FOCS 02). Exactly like LWE, this assumptio= n posits indistinguishability of $(\mathbf{A}, \mathbf{s}\mathbf{A}+\mathbf{e= } \mod p)$ from $(\mathbf{A}, \mathbf{u})$ for a random $\mathbf{u}$ where th= e secret $\mathbf{s}$, and the error vector $\mathbf{e}$ is generated exactly= as in LWE. However, the coefficient matrix $\mathbf{A}$ in sparse LPN is cho= sen randomly from $\mathbb{Z}^{n\times m}_{p}$ so that each column has Hammin= g weight exactly $k$ for some small $k$. We study the problem in the regime = where $k$ is a constant or polylogarithmic. The primary motivation for propos= ing this assumption is efficiency. Compared to LWE, the samples can be comput= ed and stored with roughly $O(n/k)$ factor improvement in efficiency. Our res= ults can be summarized as: Foundations:=20 We show several properties of sparse LWE samples, including: 1) The hardness = of LWE/LPN with dimension $k$ implies the hardness of sparse LWE/LPN with spa= rsity $k$ and arbitrary dimension $n \ge k$. 2) When the number of samples $= m=3D\Omega(n \log p)$, length of the shortest vector of a lattice spanned by = rows of a random sparse matrix is large, close to that of a random dense matr= ix of the same dimension (up to a small constant factor). 3) Trapdoors with s= mall polynomial norm exist for random sparse matrices with dimension $n \time= s m =3D O(n \log p)$. 4) Efficient algorithms for sampling such matrices tog= ether with trapdoors exist when the dimension is $n \times m =3D \widetilde{\= mathcal{O}}(n^2)$. Cryptanalysis: We examine the suite of algorithms that have been used to break LWE and spars= e LPN. While naively many of the attacks that apply to LWE do not exploit spa= rsity, we consider natural extensions that make use of sparsity. We propose a= model to capture all these attacks. Using this model we suggest heuristics o= n how to identify concrete parameters. Our initial cryptanalysis suggests tha= t concretely sparse LWE with a modest $k$ and slightly bigger dimension than = LWE will satisfy similar level of security as LWE with similar parameters. Applications:=20 We show that the hardness of sparse LWE implies very efficient homomorphic en= cryption schemes for low degree computations. We obtain the first secret key= Linearly Homomorphic Encryption (LHE) schemes with slightly super-constant, = or even constant, overhead, which further has applications to private informa= tion retrieval, private set intersection, etc. We also obtain secret key hom= omorphic encryption for arbitrary constant-degree polynomials with slightly s= uper-constant, or constant, overhead.=20 We stress that our results are preliminary. However, our results make a stron= g case for further investigation of sparse LWE. ## 2025/196 * Title: Endomorphisms for Faster Cryptography on Elliptic Curves of Moderate= CM Discriminants, II * Authors: Dimitri Koshelev, Antonio Sanso * [Permalink](https://eprint.iacr.org/2025/196) * [Download](https://eprint.iacr.org/2025/196.pdf) ### Abstract The present article is a natural extension of the previous one about the GLV = method of accelerating a (multi-)scalar multiplication on elliptic curves of = moderate CM discriminants $D < 0$. In comparison with the first article, much= greater magnitudes of $D$ (in absolute value) are achieved, although the bas= e finite fields of the curves have to be pretty large. This becomes feasible = by resorting to quite powerful algorithmic tools developed primarily in the c= ontext of lattice-based and isogeny-based cryptography. Curiously, pre-quantu= m cryptography borrows research outcomes obtained when seeking conversely qua= ntum-resistant solutions or attacks on them.=20 For instance, some $2$-cycle of pairing-friendly MNT curves (with $-D \approx= 100{,}000{,}000$, i.e., $\log_2(-D) \approx 26.5$) is relevant for the resul= t of the current article. The given $2$-cycle was generated at one time by Gu= illevic to provide $\approx 128$ security bits, hence it was close to applica= tion in real-world zk-SNARKs. Another more performant MNT $2$-cycle (with sli= ghtly smaller security level, but with much larger $D$) was really employed i= n the protocol Coda (now Mina) until zero-knowledge proof systems on signific= antly faster pairing-free (or half-pairing) $2$-cycles were invented. It is a= lso shown in the given work that more lollipop curves, recently proposed by C= ostello and Korpal to replace MNT ones, are now covered by the GLV technique. ## 2025/374 * Title: Simple and General Counterexamples for Private-Coin Evasive LWE * Authors: Nico D=C3=B6ttling, Abhishek Jain, Giulio Malavolta, Surya Mathial= agan, Vinod Vaikuntanathan * [Permalink](https://eprint.iacr.org/2025/374) * [Download](https://eprint.iacr.org/2025/374.pdf) ### Abstract We present a simple counterexample to all known variants of the private-coin = evasive learning with errors (LWE) assumption. Unlike prior works, our counte= rexample is direct, it does not use heavy cryptographic machinery (such as ob= fuscation or witness encryption), and it applies to all variants of the assum= ption. Our counterexample can be seen as a "zeroizing" attack against evasive= LWE, calling into question the soundness of the underlying design philosophy. ## 2025/385 * Title: MERCURY: A multilinear Polynomial Commitment Scheme with constant pr= oof size and no prover FFTs * Authors: Liam Eagen, Ariel Gabizon * [Permalink](https://eprint.iacr.org/2025/385) * [Download](https://eprint.iacr.org/2025/385.pdf) ### Abstract We construct a pairing-based polynomial commitment scheme for multilinear pol= ynomials of size $n$ where constructing an opening proof requires $O(n)$ field operations, and $2n+O(\s= qrt n)$ scalar multiplications. Moreover, the opening proof consists of a constant number of field elements. This is a significant improvement over previous works which would require eit= her 1. $O(n\log n)$ field operations; or 2. $O(\log n)$ size opening proof. The main technical component is a new method of verifiably folding a witness = via univariate polynomial division. As opposed to previous methods, the proof size and prover time remain constan= ========== REMAINDER OF ARTICLE TRUNCATED ==========