Path: ...!eternal-september.org!feeder3.eternal-september.org!news.eternal-september.org!.POSTED!not-for-mail From: IACR ePrint Archive Newsgroups: sci.crypt Subject: [digest] 2024 Week 31 Date: Mon, 05 Aug 2024 02:23:39 -0000 Organization: A noiseless patient Spider Lines: 954 Message-ID: MIME-Version: 1.0 Content-Type: text/plain; charset="utf-8" Content-Transfer-Encoding: quoted-printable Injection-Date: Mon, 05 Aug 2024 04:23:44 +0200 (CEST) Injection-Info: dont-email.me; posting-host="add127ca599e21b17a3644375e46632c"; logging-data="505146"; mail-complaints-to="abuse@eternal-september.org"; posting-account="U2FsdGVkX19o/qw/TWVwO6bgRbTqXzuHg+6y03cSm6g=" Cancel-Lock: sha1:WtXmhkbphIRzNJ+VGI7eKcs5oaw= Bytes: 51139 ## In this issue 1. [2024/1210] More Optimizations to Sum-Check Proving 2. [2024/1211] A Generic Framework for Side-Channel Attacks ... 3. [2024/1212] Efficient Layered Circuit for Verification of SHA3 ... 4. [2024/1213] Bounded-Collusion Streaming Functional Encryption ... 5. [2024/1214] Less Effort, More Success: Efficient Genetic ... 6. [2024/1215] Falsifiability, Composability, and Comparability of ... 7. [2024/1216] Delegatable Anonymous Credentials From Mercurial ... 8. [2024/1217] A Compact and Parallel Swap-Based Shuffler based on ... 9. [2024/1218] A Note on the use of the Double Boomerang ... 10. [2024/1219] Foldable, Recursive Proofs of Isogeny Computation ... 11. [2024/1220] Mova: Nova folding without committing to error terms 12. [2024/1221] Depth Optimized Quantum Circuits for HIGHT and LEA 13. [2024/1222] Quantum Implementation and Analysis of ARIA 14. [2024/1223] A short-list of pairing-friendly curves resistant ... 15. [2024/1224] Generic Construction of Secure Sketches from Groups 16. [2024/1225] SIGNITC: Supersingular Isogeny Graph Non- ... 17. [2024/1226] A Spectral Analysis of Noise: A Comprehensive, ... 18. [2024/1227] ZIPNet: Low-bandwidth anonymous broadcast from ... 19. [2024/1228] Automated Software Vulnerability Static Code ... 20. [2024/1229] Benchmarking Attacks on Learning with Errors 21. [2024/1230] Impossible Boomerang Attacks Revisited: ... 22. [2024/1231] A Constructive View of Homomorphic Encryption and ... 23. [2024/1232] Efficient and Privacy-Preserving Collective Remote ... 24. [2024/1233] Binding Security of Implicitly-Rejecting KEMs and ... 25. [2024/1234] EagleSignV3 : A new secure variant of EagleSign ... 26. [2024/1235] Blue fish, red fish, live fish, dead fish 27. [2024/1236] Optimizing Big Integer Multiplication on Bitcoin: ... 28. [2024/1237] Efficient Variants of TNT with BBB Security ## 2024/1210 * Title: More Optimizations to Sum-Check Proving * Authors: Quang Dao, Justin Thaler * [Permalink](https://eprint.iacr.org/2024/1210) * [Download](https://eprint.iacr.org/2024/1210.pdf) ### Abstract Many fast SNARKs apply the sum-check protocol to an $n$-variate polynomial of= the form $g(x) =3D \text{eq}(w,x) \cdot p(x)$, where $p$ is a product of mul= tilinear polynomials, $w \in \mathbb{F}^n$ is a random vector, and $\text{eq}= $ is the multilinear extension of the equality function. In this setting, we describe an optimization to the sum-check prover that sub= stantially reduces the cost coming from the $\text{eq}(w, x)$ factor. Our wor= k further improves on a prior optimization by Gruen (ePrint 2023), and in the= small-field case, can be combined with additional optimizations by Bagad, Do= mb, and Thaler (ePrint 2024), and Dao and Thaler (ePrint 2024). Over large prime-order fields, our optimization eliminates roughly $2^{n + 1}= $ field multiplications compared to a standard linear-time implementation of = the prover, and roughly $2^{n-1}$ field multiplications when considered on to= p of Gruen's optimization. These savings are about a 25% (respectively 10%) e= nd-to-end prover speedup in common use cases, and potentially even larger whe= n working over binary tower fields. ## 2024/1211 * Title: A Generic Framework for Side-Channel Attacks against LWE-based Crypt= osystems * Authors: Julius Hermelink, Silvan Streit, Erik M=C3=A5rtensson, Richard Pet= ri * [Permalink](https://eprint.iacr.org/2024/1211) * [Download](https://eprint.iacr.org/2024/1211.pdf) ### Abstract Lattice-based cryptography is in the process of being standardized. Several p= roposals to deal with side-channel information using lattice reduction exist.= However, it has been shown that algorithms based on Bayesian updating are of= ten more favorable in practice. In this work, we define distribution hints; a type of hint that allows modell= ing probabilistic information. These hints generalize most previously defined= hints and the information obtained in several attacks. We define two solvers for our hints; one is based on belief propagation and t= he other one uses a greedy approach. We prove that the latter is a computatio= nally less expensive approximation of the former and that previous algorithms= used for specific attacks may be seen as special cases of our solvers. There= by, we provide a systematization of previously obtained information and used = algorithms in real-world side-channel attacks. In contrast to lattice-based approaches, our framework is not limited to valu= e leakage. For example, it can deal with noisy Hamming weight leakage or part= ially incorrect information. Moreover, it improves upon the recovery of the s= ecret key from approximate hints in the form they arise in real-world attacks. =20 Our framework has several practical applications: We exemplarily show that a = recent attack can be improved; we reduce the number of traces and correspondi= ng ciphertexts and increase the noise resistance. Further, we explain how dis= tribution hints could be applied in the context of previous attacks and outli= ne a potential new attack. ## 2024/1212 * Title: Efficient Layered Circuit for Verification of SHA3 Merkle Tree * Authors: Changchang Ding, Zheming Fu * [Permalink](https://eprint.iacr.org/2024/1212) * [Download](https://eprint.iacr.org/2024/1212.pdf) ### Abstract We present an efficient layered circuit design for SHA3-256 Merkle tree verif= ication, suitable for a GKR proof system, that achieves logarithmic verificat= ion and proof size. We demonstrate how to compute the predicate functions for= our circuit in $O(\log n)$ time to ensure logarithmic verification and provi= de GKR benchmarks for our circuit. ## 2024/1213 * Title: Bounded-Collusion Streaming Functional Encryption from Minimal Assum= ptions * Authors: Kaartik Bhushan, Alexis Korb, Amit Sahai * [Permalink](https://eprint.iacr.org/2024/1213) * [Download](https://eprint.iacr.org/2024/1213.pdf) ### Abstract Streaming functional encryption (sFE), recently introduced by Guan, Korb, and= Sahai [Crypto 2023], is an extension of functional encryption (FE) tailored = for iterative computation on dynamic data streams. Unlike in regular FE, in a= n sFE scheme, users can encrypt and compute on the data as soon as it becomes= available and in time proportional to just the size of the newly arrived dat= a.=20 As sFE implies regular FE, all known constructions of sFE and FE for $\mathsf= {P/Poly}$ require strong cryptographic assumptions which are powerful enough = to build indistinguishability obfuscation. In contrast, bounded-collusion FE,= in which the adversary is restricted to making at most $Q$ function queries = for some polynomial $Q$ determined at setup, can be built from the minimal as= sumptions of public-key encryption (for public-key FE) [Sahai and Seyalioglu,= CCS 2010; Gorbunov, Vaikuntanathan, and Wee, CRYPTO 2012] and secret-key enc= ryption (for secret-key FE)[Ananth, Vaikuntanathan, TCC 2019]. In this paper, we introduce and build bounded-collusion streaming FE for any = polynomial bound $Q$ from the same minimal assumptions of public-key encrypti= on (for public-key sFE) and secret-key encryption (for secret-key sFE). Simil= arly to the original sFE paper of Guan, Korb, and Sahai, our scheme satisfies= semi-adaptive-function-selective security which is similar to standard adapt= ive indistinguishability-based security except that we require all functions = to be queried before any of the challenge messages.=20 Along the way, our work also replaces a key ingredient (called $\mathsf{One}\= text{-}\mathsf{sFE}$) from the original work of Guan, Korb, and Sahai with a = much simpler construction based on garbled circuits. ## 2024/1214 * Title: Less Effort, More Success: Efficient Genetic Algorithm-Based Framewo= rk for Side-channel Collision Attacks * Authors: Jiawei Zhang, Jiangshan Long, Changhai Ou, Kexin Qiao, Fan Zhang, = Shi Yan * [Permalink](https://eprint.iacr.org/2024/1214) * [Download](https://eprint.iacr.org/2024/1214.pdf) ### Abstract By introducing collision information, the existing side-channel Correlation-E= nhanced Collision Attacks (CECAs) performed collision-chain detection, and r= educed a given candidate space to a significantly smaller collision-chain spa= ce, leading to more efficient key recovery. However, they are still limited b= y low collision detection speed and low success rate of key recovery. To add= ress these issues, we first give a Collision Detection framework with Genetic= Algorithm (CDGA), which exploits Genetic Algorithm to detect the collision = chains and has a strong capability of global searching. Secondly, we theoreti= cally analyze the performance of CECA, and bound the searching depth of its o= utput candidate vectors with a confidence level using a rigorous hypothesis test, which is su= itable both for Gaussian and non-Gaussian leakages. This facilitates the=20 initialization of the population.=20 Thirdly, we design an innovative goal-directed mutation method to randomly se= lect new gene values for replacement, thus improving efficiency and adaptabil= ========== REMAINDER OF ARTICLE TRUNCATED ==========