Path: ...!eternal-september.org!feeder3.eternal-september.org!news.eternal-september.org!eternal-september.org!.POSTED!not-for-mail
From: IACR ePrint Archive <noreply@example.invalid>
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: <BdvezhQvI-b15TMlhdnFqMVlXRuguHkx@eprint.iacr.org.invalid>
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 ==========