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