## In this issue

1. [2023/808] Generic-Group Lower Bounds via Reductions Between ...
2. [2023/1525] Committing AE from Sponges: Security Analysis of ...
3. [2024/272] Deep Learning Based Analysis of Key Scheduling ...
4. [2024/273] Information-Theoretic Homomorphic Encryption and ...
5. [2024/274] Amortized Large Look-up Table Evaluation with ...
6. [2024/275] The Multi-user Constrained PRF Security of ...
7. [2024/276] Reduce and Prange: Revisiting Prange's Information ...
8. [2024/277] Fault Attacks on UOV and Rainbow
9. [2024/278] Circle STARKs
10. [2024/279] Polynomial-Time Key-Recovery Attack on the ${\tt ...
11. [2024/280] HARTS: High-Threshold, Adaptively Secure, and ...
12. [2024/281] Polynomial Commitments from Lattices: Post-Quantum ...
13. [2024/282] A Concrete Analysis of Wagner's $k$-List Algorithm ...
14. [2024/283] Toward Malicious Constant-Rate 2PC via Arithmetic ...
15. [2024/284] Practical Improvements to Statistical Ineffective ...
16. [2024/285] Mirrored Commitment: Fixing ``Randomized Partial ...
17. [2024/286] Efficient Zero-Knowledge Arguments and Digital ...
18. [2024/287] CAPABARA: A Combined Attack on CAPA
19. [2024/288] A generic algorithm for efficient key recovery in ...
20. [2024/289] SoK: Parameterization of Fault Adversary Models - ...
21. [2024/290] Secure Integrated Sensing and Communication under ...
22. [2024/291] Quantum Pseudorandomness Cannot Be Shrunk In a ...
23. [2024/292] IDEA-DAC: Integrity-Driven Editing for Accountable ...
24. [2024/293] Registered Attribute-Based Signature
25. [2024/294] Multiplex: TBC-based Authenticated Encryption with ...
26. [2024/295] An Efficient Hash Function for Imaginary Class Groups
27. [2024/296] Attacking ECDSA with Nonce Leakage by Lattice ...
28. [2024/297] Accelerating Training and Enhancing Security ...
29. [2024/298] New Models for the Cryptanalysis of ASCON
30. [2024/299] Divide and Surrender: Exploiting Variable Division ...
31. [2024/300] Diving Deep into the Preimage Security of AES-like ...
32. [2024/301] Recommendations for the Design and Validation of a ...
33. [2024/302] Pseudorandom unitaries with non-adaptive security
34. [2024/303] Single Pass Client-Preprocessing Private ...
35. [2024/304] A Two-Layer Blockchain Sharding Protocol Leveraging ...
36. [2024/305] Single-Input Functionality against a Dishonest ...
37. [2024/306] Concretely Efficient Lattice-based Polynomial ...
38. [2024/307] SweetPAKE: Key exchange with decoy passwords
39. [2024/308] C'est très CHIC: A compact password-authenticated ...
40. [2024/309] NiLoPher: Breaking a Modern SAT-Hardened Logic- ...
41. [2024/310] A Zero-Dimensional Gröbner Basis for Poseidon
42. [2024/311] Aggregating Falcon Signatures with LaBRADOR
43. [2024/312] Trapdoor Memory-Hard Functions
44. [2024/313] The Complexity of Algebraic Algorithms for LWE
45. [2024/314] Exploring the Advantages and Challenges of Fermat ...
46. [2024/315] Alternative Key Schedules for the AES
47. [2024/316] Threshold Garbled Circuits with Low Overhead
48. [2024/317] Closing the Efficiency Gap between Synchronous and ...
49. [2024/318] Plinko: Single-Server PIR with Efficient Updates ...
50. [2024/319] On the cryptosystems based on two Eulerian ...
51. [2024/320] POPSTAR: Lightweight Threshold Reporting with ...
52. [2024/321] Formal Verification of Emulated Floating-Point ...
53. [2024/322] Theoretical Explanation and Improvement of Deep ...
54. [2024/323] Circuit Bootstrapping: Faster and Smaller
55. [2024/324] Under What Conditions Is Encrypted Key Exchange ...
56. [2024/325] Proofs for Deep Thought: Accumulation for large ...

## 2023/808

* Title: Generic-Group Lower Bounds via Reductions Between Geometric-Search Problems: With and Without Preprocessing
* Authors: Benedikt Auerbach, Charlotte Hoffmann, Guillermo Pascual-Perez
* [Permalink](https://eprint.iacr.org/2023/808)
* [Download](https://eprint.iacr.org/2023/808.pdf)

### Abstract

The generic-group model (GGM) aims to capture algorithms working over groups of prime order that only rely on the group operation, but do not exploit any additional structure given by the concrete implementation of the group. In it, it is possible to
prove information-theoretic lower bounds on the hardness of problems like the discrete logarithm (DL) or computational Diffie-Hellman (CDH). Thus, since its introduction, it has served as a valuable tool to assess the concrete security provided by
cryptographic schemes based on such problems. A work on the related algebraic-group model (AGM) introduced a method, used by many subsequent works, to adapt GGM lower bounds for one problem to another, by means of conceptually simple reductions.

In this work, we propose an alternative approach to extend GGM bounds from one problem to another. Following an idea by Yun (Eurocrypt '15), we show that, in the GGM, the security of a large class of problems can be reduced to that of geometric search-
problems. By reducing the security of the resulting geometric-search problems to variants of the search-by-hypersurface problem, for which information theoretic lower bounds exist, we give alternative proofs of several results that used the AGM approach.

The main advantage of our approach is that our reduction from geometric search-problems works, as well, for the GGM with preprocessing (more precisely the bit-fixing GGM introduced by Coretti, Dodis and Guo (Crypto '18)). As a consequence, this opens up
the possibility of transferring preprocessing GGM bounds from one problem to another, also by means of simple reductions. Concretely, we prove novel preprocessing bounds on the hardness of the d-strong discrete logarithm, the d-strong Diffie-Hellman
inversion, and multi-instance CDH problems, as well as a large class of Uber assumptions. Additionally, our approach applies to Shoup's GGM without additional restrictions on the query behavior of the adversary, while the recent works of Zhang, Zhou, and
Katz (Asiacrypt '22) and Zhandry (Crypto '22) highlight that this is not the case for the AGM approach.



## 2023/1525

* Title: Committing AE from Sponges: Security Analysis of the NIST LWC Finalists
* Authors: Juliane Krämer, Patrick Struck, Maximiliane Weishäupl
* [Permalink](https://eprint.iacr.org/2023/1525)
* [Download](https://eprint.iacr.org/2023/1525.pdf)

### Abstract

Committing security has gained considerable attention in the field of authenticated encryption (AE). This can be traced back to a line of recent attacks, which entail that AE schemes used in practice should not only provide confidentiality and
authenticity, but also committing security. Roughly speaking, a committing AE scheme guarantees that ciphertexts will decrypt only for one key. Despite the recent research effort in this area, the finalists of the NIST lightweight cryptography
standardization process have not been put under consideration yet. We close this gap by providing an analysis of these schemes with respect to their committing security. Despite the structural similarities the finalists exhibit, our results are of a
quite heterogeneous nature: We break four of the schemes with effectively no costs, while for two schemes our attacks are costlier, yet still efficient. For the remaining three schemes ISAP, Ascon, and (a slightly modified version of) Schwaemm, we give
formal security proofs. Our analysis reveals that sponges—due to their large states—are more favorable for committing security compared to block-ciphers.



## 2024/272

* Title: Deep Learning Based Analysis of Key Scheduling Algorithm of Advanced Ciphers
* Authors: Narendra Kumar Patel, Hemraj Shobharam Lamkuche
* [Permalink](https://eprint.iacr.org/2024/272)
* [Download](https://eprint.iacr.org/2024/272.pdf)

### Abstract

The advancements in information technology have made the Advanced Encryption Standard (AES) and the PRESENT cipher indispensable in ensuring data security and facilitating private transactions. AES is renowned for its flexibility and widespread use in
various fields, while the PRESENT cipher excels in lightweight cryptographic situations. This paper delves into a dual examination of the Key Scheduling Algorithms (KSAs) of AES and the PRESENT cipher, which play a crucial role in generating round keys
for their respective encryption techniques. By implementing deep learning methods, particularly a Neural Network model, our study aims to unravel the complexities of these KSAs and shed light on their inner workings.



## 2024/273

* Title: Information-Theoretic Homomorphic Encryption and 2-Party Computation
* Authors: Jonathan Trostle
* [Permalink](https://eprint.iacr.org/2024/273)
* [Download](https://eprint.iacr.org/2024/273.pdf)

### Abstract

Homomorphic encryption has been an active area of research since Gentry's breakthrough results on fully homomorphic encryption.
We present secret key somewhat homomorphic schemes where client privacy is information-theoretic (server can be computationally unbounded). As the group order in our schemes gets larger, entropy approaches max-
imal entropy (perfect security). Our basic scheme is additive somewhat homomorphic. In one scheme, the server handles circuit multiplication gates by returning the mulitiplicands to the client which does the
multiplication and sends back the encrypted product. We give a 2-party protocol that also incorporates server inputs where the client privacy is information-theoretic. Server privacy is not information-theoretic, but rather depends on hardness of the
subset sum problem. Correctness for the server in the malicious model can be verified by a 3rd party where the client and server privacy are information-theoretically protected from
the verifier. Scaling the 2PC protocol via separate encryption parameters for smaller subcircuits allows the ciphertext size to grow logarithmically as circuit size grows.



## 2024/274

* Title: Amortized Large Look-up Table Evaluation with Multivariate Polynomials for Homomorphic Encryption
* Authors: Heewon Chung, Hyojun Kim, Young-Sik Kim, Yongwoo Lee
* [Permalink](https://eprint.iacr.org/2024/274)
* [Download](https://eprint.iacr.org/2024/274.pdf)

### Abstract

We present a new method for efficient look-up table (LUT) evaluation in homomorphic encryption (HE), based on Ring-LWE-based HE schemes, including both integer-message schemes such as Brakerski-Gentry-Vaikuntanathan (BGV) and Brakerski/Fan-Vercauteren (
BFV), and complex-number-message schemes like the Cheon-Kim-Kim-Song (CKKS) scheme. Our approach encodes bit streams into codewords and translates LUTs into low-degree multivariate polynomials, allowing for the simultaneous evaluation of multiple
independent LUTs with minimal overhead. To mitigate noise accumulation in the CKKS scheme, we propose a novel noise-reduction technique, accompanied by proof demonstrating its effectiveness in asymptotically decreasing noise levels.
We demonstrate our algorithm's effectiveness through a proof-of-concept implementation, showcasing significant efficiency gains, including a 0.029ms per slot evaluation for 8-input, 8-output LUTs and a 280ms amortized decryption time for AES-128 using
CKKS on a single GPU. This work not only advances LUT evaluation in HE but also introduces a transciphering method for the CKKS scheme utilizing standard symmetric-key encryption, bridging the gap between discrete bit strings and numerical data.



## 2024/275

* Title: The Multi-user Constrained PRF Security of Generalized GGM Trees for MPC and Hierarchical Wallets
* Authors: Chun Guo, Xiao Wang, Xiang Xie, Yu Yu
* [Permalink](https://eprint.iacr.org/2024/275)
* [Download](https://eprint.iacr.org/2024/275.pdf)

### Abstract

Multi-user (mu) security considers large-scale attackers that, given access to a number of cryptosystem instances, attempt to compromise at least one of them. We initiate the study of mu security of the so-called GGMtree that stems from the PRG-to-PRF
transformation of Goldreich, Goldwasser, and Micali, with a goal to provide references for its recently popularized use in applied cryptography. We propose a generalized model for GGM trees and analyze its mu prefix-constrained PRF security in the random
oracle model. Our model allows to derive concrete bounds and improvements for various protocols, and we showcase on the Bitcoin-Improvement-Proposal standard Bip32 hierarchical wallets and function secret sharing (FSS) protocols. In both scenarios, we
propose improvements with better performance and concrete security bounds at the same time. Compared with the state-of-the-art designs, our SHACAL3- and KeccaK-𝑝-based Bip32 variants reduce the communication cost of MPC-based implementations by 73.3%�
�93.8%, while our AES-based FSS substantially improves mu security while reducing computations by 50%.



## 2024/276

* Title: Reduce and Prange: Revisiting Prange's Information Set Decoding for LPN and RSD
* Authors: Jiseung Kim, Changmin Lee
* [Permalink](https://eprint.iacr.org/2024/276)
* [Download](https://eprint.iacr.org/2024/276.pdf)

### Abstract

The learning parity with noise (LPN) problem has been widely utilized in classical cryptography to construct cryptographic primitives. Various variants of LPN have been proposed, including LPN over large fields and LPN with regular noise, depending on
the underlying space and the noise regularity. These LPN variants have proven to be useful in constructing cryptographic primitives.

We propose an improvement to the Gaussian elimination attack, which is also known as Prange's information set decoding algorithm, for solving the LPN problem. Contrary to prevailing knowledge, we find that the Gaussian elimination attack is highly
competitive and currently the best method for solving LPN over large fields. Our improvement involves applying partial Gaussian elimination repeatedly, rather than the whole Gaussian algorithm, which we have named the ``Reduce and Prange's algorithm".

Moreover, we provide two applications of Reduce and Prange algorithms:
One is the hybrid algorithm of ours and Berstein, Lange and Peters's algorithm at PQCrypto'08, and the other one is Reduce and Prange algorithm for LPN with regular noise.

Last, we provide a concrete estimation of the bit-security of LPN variants using our Reduce and Prange's frameworks. Our results show that the bit-security of LPN over $\mathbb{F}_q$ is reduced by 5-11 bits when $\log q = 128$ compared to previous
analysis by Liu et al. (will appear at Eurocrypt'24). Furthermore, we show that our algorithm outperforms recent work by Briaud and Øygard (Eurocrypt'23) and Liu et al. for certain parameters. It reduces the bit-security of LPN with regular noise by 5-
28 bits.



## 2024/277

* Title: Fault Attacks on UOV and Rainbow
* Authors: Juliane Krämer, Mirjam Loiero
* [Permalink](https://eprint.iacr.org/2024/277)
* [Download](https://eprint.iacr.org/2024/277.pdf)

### Abstract

Multivariate cryptography is one of the main candidates for
creating post-quantum public key cryptosystems. Especially in the area of digital signatures, there exist many practical and secure multivariate schemes. The signature schemes UOV and Rainbow are two of the most promising and best studied multivariate
schemes which have proven secure
for more than a decade. However, so far the security of multivariate signature schemes towards physical attacks has not been appropriately assessed. Towards a better understanding of the physical security of multivariate
signature schemes, this paper presents fault attacks against SingleField schemes, especially UOV and Rainbow. Our analysis shows that although promising attack vectors exist, multivariate signature schemes inherently offer a good protection against fault
attacks.



## 2024/278

* Title: Circle STARKs
* Authors: Ulrich Haböck, David Levit, Shahar Papini
* [Permalink](https://eprint.iacr.org/2024/278)
* [Download](https://eprint.iacr.org/2024/278.pdf)

### Abstract

Traditional STARKs require a cyclic group of a smooth order in the field. This allows efficient interpolation of points using the FFT algorithm, and writing constraints that involve neighboring rows. The Elliptic Curve FFT (ECFFT, Part I and II)
introduced a way to make efficient STARKs for any finite field, by using a cyclic group of an elliptic curve. We show a simpler construction in the lines of ECFFT over the circle curve $x^2 + y^2 = 1$. When $p + 1$ is divisible by a large power of $2$,
this construction is as efficient as traditional STARKs and ECFFT. Applied to the Mersenne prime $p = 2^{31} − 1$, which has been recently advertised in the IACR eprint 2023:824, our preliminary benchmarks indicate a speed-up by a factor of $1.4$
compared to a traditional STARK using the Babybear prime $p = 2^{31} − 2^{27} + 1$.



## 2024/279

* Title: Polynomial-Time Key-Recovery Attack on the ${\tt NIST}$ Specification of ${\tt PROV}$
* Authors: River Moreira Ferreira, Ludovic Perret
* [Permalink](https://eprint.iacr.org/2024/279)
* [Download](https://eprint.iacr.org/2024/279.pdf)

### Abstract

In this paper, we present an efficient attack against ${\tt PROV}$, a recent variant of the popular Unbalanced Oil and Vinegar (${\tt UOV}$) multivariate signature scheme, that has been submitted to the ongoing ${\tt NIST}$ standardization process for
additional post-quantum signature schemes. A notable feature of ${\tt PROV}$ is its proof of security, namely, existential unforgeability under a chosen-message attack (${\tt EUF-CMA}$), assuming the hardness of solving the system formed by the public-
key non-linear equations.
We present a polynomial-time key-recovery attack against the first specification of ${\tt PROV}$ (v$1.0$). To do so, we remark that a small fraction of the ${\tt PROV}$ secret-key is leaked during the signature process. Adapting and extending previous
works on basic ${\tt UOV}$, we show that the entire secret-key can be then recovered from such a small fraction in polynomial-time. This leads to an efficient attack against ${\tt PROV}$ that we validated in practice. For all the security parameters
suggested in by the authors of ${\tt PROV}$, our attack recovers the secret-key in at most $8$ seconds. We conclude the paper by discussing the apparent mismatch between such a practical attack and the theoretical security claimed by ${\tt PROV}$
designers. Our attack is not structural but exploits that the current specification of ${\tt PROV}$ differs from the required security model.
A simple countermeasure makes ${\tt PROV}$ immune against the attack presented here and led the designers to update the specification of ${\tt PROV}$ (v$1.1$).



## 2024/280

* Title: HARTS: High-Threshold, Adaptively Secure, and Robust Threshold Schnorr Signatures
* Authors: Renas Bacho, Julian Loss, Gilad Stern, Benedikt Wagner
* [Permalink](https://eprint.iacr.org/2024/280)
* [Download](https://eprint.iacr.org/2024/280.pdf)

### Abstract

Threshold variants of the Schnorr signature scheme have recently been at the center of attention due to their applications to Bitcoin, Ethereum, and other cryptocurrencies. However, existing constructions for threshold Schnorr signatures among a set of $
n$ parties with corruption threshold $t_c$ suffer from at least one of the following drawbacks: (i) security only against static (i.e., non-adaptive) adversaries, (ii) cubic or higher communication cost to generate a single signature, (iii) strong
synchrony assumptions on the network, or (iv) $t_c+1$ are sufficient to generate a signature, i.e., the corruption threshold of the scheme equals its reconstruction threshold. Especially (iv) turns out to be a severe limitation for many asynchronous real-
world applications where $t_c < n/3$ is necessary to maintain liveness, but a higher signing threshold of $n-t_c$ is needed. A recent scheme, ROAST, proposed by Ruffing et al. (ACM CCS `22) addresses (iii) and (iv), but still falls short of obtaining
subcubic complexity and adaptive security.

In this work, we present HARTS, the first threshold Schnorr signature scheme to incorporate all these desiderata. More concretely:

- HARTS is adaptively secure and remains fully secure and operational even under asynchronous network conditions in the presence of up to $t_c < n/3$ malicious parties. This is optimal.

- HARTS outputs a Schnorr signature of size $\lambda$ with a near-optimal amortized communication cost of $O(\lambda n^2 \log{n})$ bits and $O(1)$ rounds per signature.

- HARTS is a high-threshold scheme: no fewer than $t_r+1$ signature shares can be combined to yield a full signature, where $t_r\geq 2n/3 > 2t_c$. This is optimal.

We prove our result in a modular fashion in the algebraic group model. At the core of our construction, we design a new simple, and adaptively secure high-threshold AVSS scheme which may be of independent interest.



## 2024/281

* Title: Polynomial Commitments from Lattices: Post-Quantum Security, Fast Verification and Transparent Setup
* Authors: Valerio Cini, Giulio Malavolta, Ngoc Khanh Nguyen, Hoeteck Wee
* [Permalink](https://eprint.iacr.org/2024/281)
* [Download](https://eprint.iacr.org/2024/281.pdf)

### Abstract

Polynomial commitment scheme allows a prover to commit to a polynomial $f \in \mathcal{R}[X]$ of degree $L$, and later prove that the committed function was correctly evaluated at a specified point $x$; in other words $f(x)=u$ for public $x,u \in\mathcal{
R}$. Most applications of polynomial commitments, e.g. succinct non-interactive arguments of knowledge (SNARKs), require that (i) both the commitment and evaluation proof are succinct (i.e., polylogarithmic in the degree $L$) - with the latter being
efficiently verifiable, and (ii) no pre-processing step is allowed.

Surprisingly, as far as plausibly quantum-safe polynomial commitments are concerned, the currently most efficient constructions only rely on weak cryptographic assumptions, such as security of hash functions. Indeed, despite making use of the underlying
algebraic structure, prior lattice-based polynomial commitments still seem to be much behind the hash-based ones. Moreover, security of the aforementioned lattice constructions against quantum adversaries was never formally discussed.

In this work, we bridge the gap and propose the first (asymptotically and concretely) efficient lattice-based polynomial commitment with transparent setup and post-quantum security. Our interactive variant relies on the standard (Module-)SIS problem, and
can be made non-interactive in the random oracle model using Fiat-Shamir transformation. In addition, we equip the scheme with a knowledge soundness proof against quantum adversaries which can be of independent interest. In terms of concrete efficiency,
for $L=2^{20}$ our scheme yields proofs of size $2$X smaller than the hash-based \textsf{FRI} commitment (Block et al., Asiacrypt 2023), and $70$X smaller than the very recent lattice-based construction by Albrecht et al. (Eurocrypt 2024).



## 2024/282

* Title: A Concrete Analysis of Wagner's $k$-List Algorithm over $\mathbb{Z}_p$ * Authors: Antoine Joux, Hunter Kippen, Julian Loss
* [Permalink](https://eprint.iacr.org/2024/282)
* [Download](https://eprint.iacr.org/2024/282.pdf)

### Abstract

Since its introduction by Wagner (CRYPTO `02), the $k$-list algorithm has found significant utility in cryptanalysis. One important application thereof is in computing forgeries on several interactive signature schemes that implicitly rely on the
hardness of the ROS problem formulated by Schnorr (ICICS `01). The current best attack strategy for these schemes relies the conjectured runtime of the $k$-list algorithm over $\mathbb{Z}_p$. The tightest known analysis of Wagner's algorithm over $\
mathbb{Z}_p$ is due to Shallue (ANTS `08). However, it hides large polynomial factors and leaves a gap with respect to desirable concrete parameters for the attack. In this work, we develop a degraded version of the $k$-list algorithm which provably
enforces the heuristic invariants in Wagner's original. In the process, we devise and analyze a new list merge procedure that we dub the interval merge. We give a thorough analysis of the runtime and success probability of our degraded algorithm, and
show that it beats the projected runtime of the analysis by Shallue for parameters relevant to the generalized ROS attack of Benhamouda et al. (EUROCRYPT `21). For a $256$-bit prime $p$, and $k = 8$, our degraded $k$-list algorithm runs in time $\approx
2^{70.4}$, while Shallue's analysis states that the Wagner's original algorithm runs in time $\approx 2^{98.3}$.



## 2024/283

* Title: Toward Malicious Constant-Rate 2PC via Arithmetic Garbling
* Authors: Carmit Hazay, Yibin Yang
* [Permalink](https://eprint.iacr.org/2024/283)
* [Download](https://eprint.iacr.org/2024/283.pdf)

### Abstract

A recent work by Ball, Li, Lin, and Liu [Eurocrypt'23] presented a new instantiation of the arithmetic garbling paradigm introduced by Applebaum, Ishai, and Kushilevitz [FOCS'11]. In particular, Ball et al.'s garbling scheme is the first constant-rate
garbled circuit over large enough bounded integer computations, inferring the first constant-round constant-rate secure two-party computation (2PC) over bounded integer computations in the presence of semi-honest adversaries.

The main source of difficulty in lifting the security of garbling schemes-based protocols to the malicious setting lies in proving the correctness of the underlying garbling scheme. In this work, we analyze the security of Ball et al.'s scheme in the
presence of malicious attacks.

- We demonstrate an overflow attack, which is inevitable in this computational model, even if the garbled circuit is fully correct. Our attack follows by defining an adversary, corrupting either the garbler or the evaluator, that chooses a bad input and
causes the computation to overflow, thus leaking information about the honest party's input. By utilizing overflow attacks, we show that $1$-bit leakage is necessary for achieving security against a malicious garbler, discarding the possibility of
achieving full malicious security in this model. We further demonstrate a wider range of overflow attacks against a malicious evaluator with more than $1$ bit of leakage.

- We boost the security level of Ball et al.'s scheme by utilizing two variants of Vector Oblivious Linear Evaluation, denoted by VOLEc and aVOLE. We present the first constant-round constant-rate 2PC protocol over bounded integer computations, in the
presence of a malicious garbler with $1$-bit leakage and a semi-honest evaluator, in the {VOLEc,aVOLE}-hybrid model and being black-box in the underlying group and ring. Compared to the semi-honest variant, our protocol incurs only a constant factor
overhead, both in computation and communication. The constant-round and constant-rate properties hold even in the plain model.



## 2024/284

* Title: Practical Improvements to Statistical Ineffective Fault Attacks
* Authors: Barış Ege, Bob Swinkels, Dilara Toprakhisar, Praveen Kumar Vadnala * [Permalink](https://eprint.iacr.org/2024/284)
* [Download](https://eprint.iacr.org/2024/284.pdf)

### Abstract

Statistical Fault Attacks (SFA), introduced by Fuhr et al., exploit the statistical bias resulting from injected faults. Unlike prior fault analysis attacks, which require both faulty and correct ciphertexts under the same key, SFA leverages only faulty
ciphertexts. In CHES 2018, more powerful attacks called Statistical Ineffective Fault Attacks (SIFA) have been proposed. In contrast to the previous fault attacks that utilize faulty ciphertexts, SIFA exploits the distribution of the intermediate values
leading to fault-free ciphertexts. As a result, the SIFA attacks were shown to be effective even in the presence of widely used fault injection countermeasures based on detection and infection. In this work, we build upon the core idea of SIFA, and
provide two main practical improvements over the previously proposed analysis methods. Firstly, we show how to perform SIFA from the input side, which in contrast to the original SIFA, requires injecting faults in the earlier rounds of an encryption or
decryption operation. If we consider the start of the operation as the trigger for fault injection, the cumulative jitter in the first few rounds of a cipher is much lower than the last rounds. Hence, performing the attack in the first or second round
requires a narrower parameter range for fault injection and hence less fault injection attempts to recover the secret key. Secondly, in comparison to the straightforward SIFA approach of guessing 32-bits at a time, we propose a chosen input approach that
reduces the guessing effort to 16-bits at a time. This decreases the key search space for full key recovery of an AES-128 implementation from $2^{34}$ to $2^{19}$.



## 2024/285

* Title: Mirrored Commitment: Fixing ``Randomized Partial Checking'' and Applications
* Authors: Paweł Lorek, Moti Yung, Filip Zagórski
* [Permalink](https://eprint.iacr.org/2024/285)
* [Download](https://eprint.iacr.org/2024/285.pdf)

### Abstract

Randomized Partial Checking (RPC} was proposed by Jakobsson, Juels, and Rivest and attracted attention as an efficient method of verifying the correctness of the mixing process in numerous applied scenarios. In fact,
RPC is a building block for many electronic voting schemes, including Prêt à Voter, Civitas, Scantegrity II as well as voting-systems used in real-world elections (e.g., in Australia). Mixing is also used in anonymous transfers of cryptocurrencies.

It turned out, however, that a series of works showed, however,
subtle issues with analyses behind RPC. First, that the actual
security level of the RPC protocol is way off the claimed bounds. The probability of successful manipulation of $k$ votes is $(\frac{3}{4})^k$ instead of the claimed $\frac{1}{2^k}$ (this difference, in turn, negatively affects actual implementations of
the notion within existing election systems. This is so since concrete implemented procedures of a given length were directly based on this parameter).

Further, privacy guarantees that a constant number of mix-servers is enough turned out to also not be correct. We can conclude from the above that these analyses of the processes of mixing are not trivial.

In this paper, we review the relevant attacks, and we present Mirrored-RPC -- a fix to RPC based on ``mirrored commitment'' which makes it optimally secure; namely, having a probability of successful manipulation of $k$ votes $\frac{1}{2^k}$.

Then, we present an analysis of the privacy level of both RPC and mRPC. We show that for $n$ messages, the number of mix-servers (rounds) needed to be $\varepsilon$-close to the uniform distribution in total variation distance is lower bounded by:
\[
r(n, \varepsilon) \geq \log_{2}{n \choose 2}/\varepsilon.
\]

This proof of privacy, in turn, gives insights into the anonymity of various cryptocurrencies (e.g., Zerocash) using anonymizing pools. If a random fraction $q$ of $n$ existing coins is mixed (in each block), then to achieve full anonymity, the number of
blocks one needs to run the protocol for, is:
\[
rb(n, q, \varepsilon) \geq - \frac{\log n + \log (n-1) - \log (2\varepsilon)}{ {\log({1-q^2}})}.
\]



## 2024/286

* Title: Efficient Zero-Knowledge Arguments and Digital Signatures via Sharing Conversion in the Head
* Authors: Jules Maire, Damien Vergnaud
* [Permalink](https://eprint.iacr.org/2024/286)
* [Download](https://eprint.iacr.org/2024/286.pdf)

### Abstract

We present a novel technique within the MPC-in-the-Head framework, aiming to design efficient zero-knowledge protocols and digital signature schemes. The technique allows for the simultaneous use of additive and multiplicative sharings of secret
information, enabling efficient proofs of linear and multiplicative relations.

[continued in next message]

--- SoupGate-Win32 v1.05
* Origin: fsxNet Usenet Gateway (21:1/5)