[digest] 2024 Week 49

## In this issue

1. [2024/879] Consistency-or-Die: Consistency for Key Transparency
2. [2024/886] A New Security Evaluation Method Based on Resultant ...
3. [2024/1948] ARK: Adaptive Rotation Key Management for Fully ...
4. [2024/1949] Avenger Ensemble: Genetic Algorithm-Driven Ensemble ...
5. [2024/1950] Two-Round 2PC ECDSA at the Cost of 1 OLE
6. [2024/1951] Vote&Check: Secure Postal Voting with Reduced Trust ...
7. [2024/1952] Worst-Case Lattice Sampler with Truncated Gadgets ...
8. [2024/1953] Truncation Untangled: Scaling Fixed-Point ...
9. [2024/1954] A Complete Characterization of One-More Assumptions ...
10. [2024/1955] Gold OPRF: Post-Quantum Oblivious Power Residue PRF
11. [2024/1956] MultiReg-FE: Registered FE for Unbounded Inner- ...
12. [2024/1957] NICE-PAKE: On the Security of KEM-Based PAKE ...
13. [2024/1958] M-Sel: A Message Selection Functional Encryption ...
14. [2024/1959] SoK: Privacy-Preserving Transactions in Blockchains
15. [2024/1960] Share the MAYO: thresholdizing MAYO
16. [2024/1961] On the (Im)possibility of Game-Theoretically Fair ...
17. [2024/1962] uKNIT: Breaking Round-alignment for Cipher Design ...
18. [2024/1963] Proof of Time: A Method for Verifiable Temporal ...
19. [2024/1964] Lova: Lattice-Based Folding Scheme from ...
20. [2024/1965] Onion Franking: Abuse Reports for Mix-Based Private ...
21. [2024/1966] Efficient Succinct Zero-Knowledge Arguments in the ...
22. [2024/1967] Analysis of REDOG: The Pad Thai Attack
23. [2024/1968] SoK: Pseudorandom Generation for Masked ...
24. [2024/1969] SoK: Security of the Ascon Modes
25. [2024/1970] Scribe: Low-memory SNARKs via Read-Write Streaming
26. [2024/1971] Further Connections Between Isogenies of ...
27. [2024/1972] RoK, Paper, SISsors – Toolkit for Lattice-based ...

## 2024/879

* Title: Consistency-or-Die: Consistency for Key Transparency
* Authors: Joakim Brorsson, Elena Pagnin, Bernardo David, Paul Stankovski Wagner
* [Permalink](https://eprint.iacr.org/2024/879)
* [Download](https://eprint.iacr.org/2024/879.pdf)

### Abstract

This paper proposes a new consistency protocol that protects a key transparency log against split-view attacks and - contrary to all previous work - does not to rely on small committees of known external auditors, or out-of-band channels, or blockchains (full broadcast systems).

Our approach is to use a mechanism for cryptographically selecting a small committee of random and initially undisclosed users, which are then tasked to endorse the current view of the log. The name of our protocol, Consistency-or-Die (CoD), reflects that users are guaranteed to know if they are in a consistent state or not, and upon spotting an inconsistency in the key transparency log, users stop using this resource and become inactive (die). CoD relies on well-established cryptographic building blocks, such as verifiable random functions and key-evolving signatures, for which lightweight constructions exist. We provide a novel statistical analysis for identifying optimal quorum sizes (minimal number of endorsers for a view) for various security levels and percentages of malicious users.

Our experiments support that CoD is practical and can run in the background on mid-tier smart phones, for large-scale systems with billions of users.



## 2024/886

* Title: A New Security Evaluation Method Based on Resultant for Arithmetic-Oriented Algorithms
* Authors: Hong-Sen Yang, Qun-Xiong Zheng, Jing Yang, Quan-feng Liu, Deng Tang
* [Permalink](https://eprint.iacr.org/2024/886)
* [Download](https://eprint.iacr.org/2024/886.pdf)

### Abstract

The rapid development of advanced cryptographic applications like multi-party computation (MPC), fully homomorphic encryption (FHE), and zero-knowledge (ZK) proofs have motivated the designs of the so-called arithmetic-oriented (AO) primitives. Efficient AO primitives typically build over large fields and use large S-boxes. Such design philosophy brings difficulties in the cryptanalysis of these primitives as classical cryptanalysis methods do not apply well.. The generally recognized attacks against these primitives are algebraic attacks, especially Groebner basis attacks. Thus, the numbers of security rounds are usually derived through the complexity of solving the system of algebraic equations using Groebner bases. In this paper, we propose a novel framework for algebraic attacks against AO primitives. Instead of using Groebner basis, we use resultants to solve a system of multivariate equations that can better exploit the algebraic structures of AO primitives. We employ several techniques to reduce the dimensions of the resultants and avoid rapid increases in degrees, including meet-in-the-middle modeling, variable substitutions, and fast Lagrange interpolation. We apply our attack to three mainstream AO cryptographic primitives: Rescue-Prime, Anemoi, and Jarvis. For Rescue-Prime, we theoretically prove that the final univariate equation has a degree of at most a specific power of three and practically attack five rounds for the first time. We attack the full-round of Anemoi with complexity 2^110.10, which has been claimed to provide 127 bits of security. We also give the first practical attack against eight rounds of Anemoi over a 55-bit prime field. For Jarvis, we improve the existing practical attack by a factor of 100. Therefore, we point out that our analysis framework can be used as a new evaluation method for AO designs.



## 2024/1948

* Title: ARK: Adaptive Rotation Key Management for Fully Homomorphic Encryption Targeting Memory Efficient Deep Learning Inference
* Authors: Jia-Lin Chan, Wai-Kong Lee, Denis C.-K Wong, Wun-She Yap, Bok-Min Goi
* [Permalink](https://eprint.iacr.org/2024/1948)
* [Download](https://eprint.iacr.org/2024/1948.pdf)

### Abstract

Advancements in deep learning (DL) not only revolutionized many aspects in our lives, but also introduced privacy concerns, because it processed vast amounts of information that was closely related to our daily life. Fully Homomorphic Encryption (FHE) is one of the promising solutions to this privacy issue, as it allows computations to be carried out directly on the encrypted data. However, FHE requires high computational cost, which is a huge barrier to its widespread adoption. Many prior works proposed techniques to enhance the speed performance of FHE in the past decade, but they often impose significant memory requirements, which may be up to hundreds of gigabytes. Recently, focus has shifted from purely improving speed performance to managing FHE’s memory consumption as a critical challenge. Rovida and Leporati introduced a technique to minimize rotation key memory by retaining only essential keys, yet this technique is limited to cases with symmetric numerical patterns (e.g., -2 -1 0 1 2), constraining its broader utility. In this paper, a new technique, Adaptive Rotation Key (ARK), is proposed that minimizes rotation key memory consumption by exhaustively analyzing numerical patterns to produce a minimal subset of shared rotation keys. ARK also provides a dual-configuration option, enabling users to prioritize memory efficiency or computational speed. In memory-prioritized mode, ARK reduces rotation key memory consumption by 41.17% with a 12.57% increase in execution time. For speed-prioritized mode, it achieves a 24.62% rotation key memory reduction with only a 0.21% impact on execution time. This flexibility positions ARK as an effective solution for optimizing FHE across varied use cases, marking a significant advancement in optimization strategies for FHE-based privacy-preserving systems.



## 2024/1949

* Title: Avenger Ensemble: Genetic Algorithm-Driven Ensemble Selection for Deep Learning-based Side-Channel Analysis
* Authors: Zhao Minghui, Trevor Yap
* [Permalink](https://eprint.iacr.org/2024/1949)
* [Download](https://eprint.iacr.org/2024/1949.pdf)

### Abstract

Side-Channel Analysis (SCA) exploits physical vulnerabilities in systems to reveal secret keys. With the rise of Internet-of-Things, evaluating SCA attacks has become crucial. Profiling attacks, enhanced by Deep Learning-based Side-Channel Analysis (DLSCA), have shown significant improvements over classical techniques. Recent works demonstrate that ensemble methods outperform single neural networks. However, almost every existing ensemble selection method in SCA only picks the top few best-performing neural networks for the ensemble, which we coined as Greedily-Selected Method (GSM), which may not be optimal.
This work proposes Evolutionary Avenger Initiative (EAI), a genetic algorithm-driven ensemble selection algorithm, to create effective ensembles for DLSCA.. We investigate two fitness functions and evaluate EAI across four datasets, including \AES and \ascon implementations. We show that EAI outperforms GSM, recovering secrets with the least number of traces. Notably, EAI successfully recovers secret keys for \ascon datasets where GSM fails, demonstrating its effectiveness.



## 2024/1950

* Title: Two-Round 2PC ECDSA at the Cost of 1 OLE
* Authors: Michael Adjedj, Constantin Blokh, Geoffroy Couteau, Antoine Joux, Nikolaos Makriyannis
* [Permalink](https://eprint.iacr.org/2024/1950)
* [Download](https://eprint.iacr.org/2024/1950.pdf)

### Abstract

We present a novel protocol for two-party ECDSA that achieves two rounds (a single back-and-forth communication) at the cost of a single oblivious linear function evaluation (OLE). In comparison, the previous work of [DKLs18] (S&P 2018) achieves two rounds at the cost of three OLEs, while [BHL24] (Manuscript 2024) requires expensive zero-knowledge proofs on top of the OLE. We demonstrate this by proving that in the generic group model, any adversary capable of generating forgeries for our protocol can be transformed into an adversary that finds preimages for the ECDSA message digest function (e.g., the SHA family). Interestingly, our analysis is closely related to, and has ramifications for, the `presignatures' mode of operation—[CGGMP20] (CCS 2020), [GroSho22] (EUROCRYPT 2022).

Motivated by applications to embedded cryptocurrency wallets, where a single server maintains distinct, shared public keys with separate clients (i.e., a star-shaped topology), and with the goal of minimizing communication, we instantiate our protocol using Paillier encryption and suitable zero-knowledge proofs. To reduce computational overhead, we thoroughly optimize all components of our protocol under sound cryptographic assumptions, specifically small-exponent variants of RSA-style assumptions. 

Finally, we implement our protocol and provide benchmarks. At the 128-bit security level, the signing phase requires approximately 50ms of computation time on a standard linux machine, and 2KB of bandwidth.



## 2024/1951

* Title: Vote&Check: Secure Postal Voting with Reduced Trust Assumptions
* Authors: Véronique Cortier, Alexandre Debant, Pierrick Gaudry, Léo Louistisserand
* [Permalink](https://eprint.iacr.org/2024/1951)
* [Download](https://eprint.iacr.org/2024/1951.pdf)

### Abstract

Postal voting is a frequently used alternative to on-site voting. Traditionally, its security relies on organizational measures, and voters have to trust many entities. In the recent years, several schemes have been proposed to add verifiability properties to postal voting, while preserving vote privacy.
Postal voting comes with specific constraints. We conduct a systematic analysis of this setting and we identify a list of generic attacks, highlighting that some attacks seem unavoidable. This study is applied to existing systems of the literature.
We then propose Vote&Check, a postal voting protocol which provides a high level of security, with a reduced number of authorities. Furthermore, it requires only basic cryptographic primitives, namely hash functions and signatures. The security properties are proven in a symbolic model, with the help of the ProVerif tool.



## 2024/1952

* Title: Worst-Case Lattice Sampler with Truncated Gadgets and Applications
* Authors: Corentin Jeudy, Olivier Sanders
* [Permalink](https://eprint.iacr.org/2024/1952)
* [Download](https://eprint.iacr.org/2024/1952.pdf)

### Abstract

Gadget-based samplers have proven to be a key component of several cryptographic primitives, in particular in the area of privacy-preserving mechanisms. Most constructions today follow the approach introduced by Micciancio and Peikert (MP) yielding preimages whose dimension linearly grows with that of the gadget. To improve performance, some papers have proposed to truncate the gadget but at the cost of an important feature of the MP sampler, namely the ability to invert arbitrary syndromes. Technically speaking, they replace the worst-case MP sampler by an average-case sampler that can only be used in specific contexts. Far from being a mere theoretical restriction, it prevents the main applications of gadget-based samplers from using truncated variants and thus from benefiting from the associated performance gains.
In this paper, we solve this problem by describing a worst-case sampler that still works with truncated gadgets. Its main strength is that it retains the main characteristics of the MP sampler while providing flexibility in the choice of the truncation parameter. As a consequence, it can be used as a plug-in replacement for all applications relying on the MP sampler so far, leading to performance improvements up to 30% as illustrated by several examples in this paper. Our sampler is supported by a thorough security analysis that addresses the hurdles met by previous works and its practicality is demonstrated by a concrete implementation.



## 2024/1953

* Title: Truncation Untangled: Scaling Fixed-Point Arithmetic for Privacy-Preserving Machine Learning to Large Models and Datasets
* Authors: Christopher Harth-Kitzerow, Georg Carle
* [Permalink](https://eprint.iacr.org/2024/1953)
* [Download](https://eprint.iacr.org/2024/1953.pdf)

### Abstract

Fixed point arithmetic (FPA) is essential to enable practical Privacy-Preserving Machine Learning. When multiplying two fixed-point numbers, truncation is required to ensure that the product maintains correct precision. While multiple truncation schemes based on Secure Multiparty Computation (MPC) have been proposed, which of the different schemes offers the best trade-off between accuracy and efficiency on common PPML datasets and models has remained underexplored.

In this work, we study several different stochastic and exact truncation approaches found in the MPC literature that require different slack sizes, i.e., additional bits required by each secret share to ensure correctness. We provide novel, improved construction for each truncation approach in the semi-honest 3-PC and malicious 4-PC settings, which reduce communication and round complexity up to three times. Moreover, we propose a truncation scheme that does not introduce any communication overhead in the online phase and exactly matches the accuracy of plaintext floating-point PyTorch inference of VGG-16 on the ImageNet dataset with over 80% accuracy using shares with a bitlength of only 32. This is the first time that high PPML accuracy is demonstrated on ImageNet.



## 2024/1954

* Title: A Complete Characterization of One-More Assumptions In the Algebraic Group Model
* Authors: Jake Januzelli, Jiayu Xu
* [Permalink](https://eprint.iacr.org/2024/1954)
* [Download](https://eprint.iacr.org/2024/1954.pdf)

### Abstract

One-more problems like One-More Discrete Logarithm (OMDL) and One-More Diffie--Hellman (OMDH) have found wide use in cryptography, due to their ability to naturally model security definitions for interactive primitives like blind signatures and oblivious PRF. Furthermore, a generalization of OMDH called Threshold OMDH (TOMDH) has proven useful for building threshold versions of interactive protocols. However, due to their complexity it is often unclear how hard such problems actually are, leading cryptographers to analyze them in idealized models like the Generic Group Model (GGM) and Algebraic Group Model (AGM). In this work we give a complete characterization of known group-based one-more problems in the AGM, using the $Q$-DL hierarchy of assumptions defined in the work of Bauer, Fuchsbauer and Loss (CRYPTO '20).

1. Regarding (T)OMDH, we show (T)OMDH is part of the $Q$-DL hierarchy in the AGM; in particular, $Q$-OMDH is equivalent to $Q$-DL. Along the way we find and repair a flaw in the original GGM hardness proof of TOMDH, thereby giving the first correct proof that TOMDH is hard in the GGM.

2. Regarding OMDL, we show the $Q$-OMDL problems constitute an infinite hierarchy of problems in the AGM incomparable to the $Q$-DL hierarchy; that is, $Q$-OMDL is separate from $Q'$-OMDL if $Q' \neq Q$, and also separate from $Q'$-DL unless $Q = Q' = 0$.



## 2024/1955

* Title: Gold OPRF: Post-Quantum Oblivious Power Residue PRF
* Authors: Yibin Yang, Fabrice Benhamouda, Shai Halevi, Hugo Krawczyk, Tal Rabin
* [Permalink](https://eprint.iacr.org/2024/1955)
* [Download](https://eprint.iacr.org/2024/1955.pdf)

### Abstract

We propose plausible post-quantum (PQ) oblivious pseudorandom functions (OPRFs) based on the Power Residue PRF (Damgård CRYPTO’88), a generalization of the Legendre PRF. For security parameter $\lambda$, we consider the PRF $\mathsf{Gold}_k(x)$ that maps an integer $x$ modulo a public prime $p = 2^\lambda\cdot g + 1$ to the element $(k + x)^g \bmod p$, where $g$ is public and $\log g \approx 2\lambda$.

At the core of our constructions are efficient novel methods for evaluating $\mathsf{Gold}$ within two-party computation ($\mathsf{2PC}\text{-}\mathsf{Gold}$), achieving different security requirements. Here, the server $\mathcal{P}_s$ holds the PRF key $k$ whereas the client $\mathcal{P}_c$ holds the PRF input $x$, and they jointly evaluate $\mathsf{Gold}$ in 2PC. $\mathsf{2PC}\text{-}\mathsf{Gold}$ uses standard Vector Oblivious Linear Evaluation (VOLE) correlations and is information-theoretic and constant-round in the (V)OLE-hybrid model. We show:

• For a semi-honest $\mathcal{P}_s$ and a malicious $\mathcal{P}_c$: a $\mathsf{2PC}\text{-}\mathsf{Gold}$ that just uses a single (V)OLE correlation, and has a communication complexity of $3$ field elements ($2$ field elements if we only require a uniformly sampled key) and a computational complexity of $\mathcal{O}(\lambda)$ field operations. We refer to this as half-malicious security.

• For malicious $\mathcal{P}_s$ and $\mathcal{P}_c$: a $\mathsf{2PC}\text{-}\mathsf{Gold}$ that just uses $\frac{\lambda}{4} + \mathcal{O}(1)$ VOLE correlations, and has a communication complexity of $\frac{\lambda}{4} + \mathcal{O}(1)$ field elements and a computational complexity of $\mathcal{O}(\lambda)$ field operations.

These constructions support additional features and extensions, e.g., batched evaluations with better amortized costs where $\mathcal{P}_c$ repeatedly evaluates the PRF under the same key.

Furthermore, we extend $\mathsf{2PC}\text{-}\mathsf{Gold}$ to Verifiable OPRFs and use the methodology from Beullens et al. (ePrint’24) to obtain strong OPRF security in the universally composable setting.

All the protocols are efficient in practice. We implemented $\mathsf{2PC}\text{-}\mathsf{Gold}$—with (PQ) VOLEs—and benchmarked them. For example, our half-malicious (resp. malicious) $n$-batched PQ OPRFs incur about $100$B (resp. $1.9$KB) of amortized communication for $\lambda = 128$ and large enough $n$.



## 2024/1956

* Title: MultiReg-FE: Registered FE for Unbounded Inner-Product and Attribute-Weighted Sums
* Authors: Qiuyan Du, Qiaohan Chu, Jie Chen, Man Ho Au, Debiao He
* [Permalink](https://eprint.iacr.org/2024/1956)
* [Download](https://eprint.iacr.org/2024/1956.pdf)

### Abstract

Recently, Francati et al. (Asiacrypt 2023) provided the first registered functional encryption (Reg-FE) beyond predicates. Reg-FE addresses the key escrow problem in functional encryption by allowing users to generate their own key pairs, effectively replacing the traditional private-key generator with a key curator. The key curator holds no secret information and runs deterministic algorithms to generate master public key for encryption and helper keys for decryption. However, existing Reg-FE schemes under standard assumptions require fixed data sizes, which limits their practicality in real-world applications.
In this work, we introduce Multi-Function Registered Functional Encryption for Inner-Product (MultiReg-FE for IP), a novel extension of Reg-FE. It enables users to register multiple functions under a single public key. With MultiReg-FE, we achieve both Reg-FE for Unbounded Inner-Product (Unbounded IP), which removes the need to predetermine vector lengths, and Reg-FE for Attribute-Weighted Sums with Inner-Product (AWSw/IP), allowing computations over arbitrary numbers of attribute-value pairs.
All our schemes achieve adaptive-IND-security. Specifically, we present:
-MultiReg-FE for Inner-Product, which supports unbounded number of function vectors from each user.
- Reg-FE for Unbounded Inner-Product, removing the need for preset vector lengths.
- The first Reg-FE for AWSw/IP in public-key settings.



## 2024/1957

* Title: NICE-PAKE: On the Security of KEM-Based PAKE Constructions without Ideal Ciphers
* Authors: Nouri Alnahawi, Jacob Alperin-Sheriff, Daniel Apon, Alexander Wiesmaier
* [Permalink](https://eprint.iacr.org/2024/1957)
* [Download](https://eprint.iacr.org/2024/1957.pdf)

### Abstract

The interest in realizing generic PQC KEM-based PAKEs has increased significantly in the last few years. One such PAKE is the CAKE protocol, proposed by Beguinet et al. (ACNS ’23). However, despite its simple design based on the well-studied PAKE protocol EKE by Bellovin and Merritt (IEEE S&P ’92), both CAKE and its variant OCAKE do not fully protect against quantum adversaries, as they rely on the Ideal Cipher (IC) model. Related and follow-up works, including Pan and Zeng (ASIACRYPT ’23), Dos Santos et al. (EUROCRYPT ’23), Alnahawi et al. (CANS ’24), and Arragia et al.. (IACR ’24/308) although touching on that issue, still rely on an IC.. Considering the lack of a quantum IC model and the difficulty of using the classical IC to achieve secure instantiations on public keys in general and PQC in particular, we set out to eliminate it from PAKE design. In this paper, we present the No IC Encryption (NICE)-PAKE, a (semi)-generic PAKE framework providing a quantum-safe alternative for the IC, utilizing simpler cryptographic components for the authentication step. To give a formal proof for our construction, we introduce the notions of A-Part-Secrecy (A-SEC-CCA), Splittable Collision Freeness (A-CFR-CCA) and Public Key Uniformity (SPLIT-PKU) for splittable LWE KEMs. We show the relation of the former to the Non-uniform LWE and the Weak Hint LWE assumptions, as well as its application to ring and module LWE. Notably, this side quest led to some surprising discoveries, as we concluded that the new notion is not directly interchangeable between the LWE variants, or at least not in a straightforward manner. Further, we show that our approach requires some tedious tweaking for the parameter choices in both FrodoKEM and CRYSTALS-Kyber to obtain a secure PAKE construction. We also address some fundamental issues with the common IC usage and identify differences between lattice KEMs regarding their suitability for generic PQC PAKEs, especially regarding the structure of their public keys. We believe that this work marks a further step towards achieving complete security against quantum adversaries in PQC PAKEs.



## 2024/1958

* Title: M-Sel: A Message Selection Functional Encryption from Simple Tool
* Authors: Ahmad Khoureich Ka
* [Permalink](https://eprint.iacr.org/2024/1958)
* [Download](https://eprint.iacr.org/2024/1958.pdf)

### Abstract

In this paper, we put forward a new practical application of Inner-Product Functional Encryption (IPFE) that we call Message Selection functional encryption (M-Sel) which allows users to decrypt selected portions of a ciphertext. In a message selection functional encryption scheme, the plaintext is partitioned into a set of messages M = {m1, . . . , mt}. The encryption of M consists in encrypting each of its elements using distinct encryption keys. A user with a functional decryption key skx derived from a selection vector x can access a subset of M from the encryption thereof and nothing more. Our construction is generic and combines a symmetric encryption scheme and an inner product functional encryption scheme, therefore, its security is tied to theirs. By instantiating our generic construction from a DDH-based IPFE we obtain a message selection FE with constant-size decryption keys suitable for key storage in lightweight devices in the context of Internet of Things (IoT).



## 2024/1959

* Title: SoK: Privacy-Preserving Transactions in Blockchains
* Authors: Foteini Baldimtsi, Kostas Kryptos Chalkias, Varun Madathil, Arnab Roy
* [Permalink](https://eprint.iacr.org/2024/1959)
* [Download](https://eprint.iacr.org/2024/1959.pdf)

### Abstract

Ensuring transaction privacy in blockchain systems is essential to safeguard user data and financial activity from exposure on public ledgers. This paper conducts a systematization of knowledge (SoK) on privacy-preserving techniques in cryptocurrencies with native privacy features. We define and compare privacy notions such as confidentiality, k-anonymity, full anonymity, and sender-receiver unlinkability, and categorize the cryptographic techniques employed to achieve these guarantees. Our analysis highlights the trade-offs between privacy guarantees, scalability, and regulatory compliance.  Finally, we evaluate the usability of the most popular private cryptocurrencies providing insights into their practical deployment and user interaction.

Through this analysis, we identify key gaps and challenges in current privacy solutions, highlighting areas where further research and development are needed to enhance privacy while maintaining scalability and security.



## 2024/1960

* Title: Share the MAYO: thresholdizing MAYO
* Authors: Sofia Celi, Daniel Escudero, Guilhem Niot
* [Permalink](https://eprint.iacr.org/2024/1960)
* [Download](https://eprint.iacr.org/2024/1960.pdf)

### Abstract

We present the first comprehensive study on thresholdizing practical OV-based signature schemes, specifically focusing on MAYO and UOV. Our approach begins by addressing the challenges associated with thresholdizing algorithms that sample solutions to linear equation systems of the form $Ax = y$, which are fundamental to OV-based signature schemes. Previous attempts have introduced levels of leakage that we deem insecure. We propose a novel minimum-leakage solution and assess its practicality. Furthermore, we explore the thresholdization of the entire functionality of these signature schemes, demonstrating their unique applications in networks and cryptographic protocols.



## 2024/1961

* Title: On the (Im)possibility of Game-Theoretically Fair Leader Election Protocols
* Authors: Ohad Klein, Ilan Komargodski, Chenzhi Zhu
* [Permalink](https://eprint.iacr.org/2024/1961)
* [Download](https://eprint.iacr.org/2024/1961.pdf)

### Abstract

We consider the problem of electing a leader among $n$ parties with the guarantee that each (honest) party has a reasonable probability of being elected, even in the presence of a coalition that controls a subset of parties, trying to bias the output. This notion is called ``game-theoretic fairness'' because such protocols  ensure that following the honest behavior is an equilibrium and also the best response for every party and coalition. In the two-party case, Blum's commit-and-reveal protocol (where if one party aborts, then the other is declared the leader) satisfies this notion and it is also known that one-way functions are necessary. Recent works study this problem in the multi-party setting. They show that composing Blum's 2-party protocol for $\log n$ rounds in a tournament-tree-style manner results with {perfect game-theoretic fairness}: each honest party has probability $\ge 1/n$ of being elected as leader, no matter how large the coalition is. Logarithmic round complexity is also shown to be necessary if we require perfect fairness against a coalition of size $n-1$.  Relaxing the above two requirements, i.e., settling for approximate game-theoretic fairness and guaranteeing fairness against only constant fraction size coalitions, it is known that there are $O(\log ^* n)$ round protocols.

This leaves many open problems, in particular, whether one can go below logarithmic round complexity by relaxing only one of the strong requirements from above. We manage to resolve this problem for commit-and-reveal style protocols, showing that
    - $\Omega(\log n/\log\log n)$ rounds are necessary if we settle for approximate fairness against very large (more than constant fraction) coalitions;
   - $\Omega(\log n)$ rounds are necessary if we settle for perfect fairness against $n^\epsilon$ size coalitions  (for any constant $\epsilon>0$).
These show that both relaxations made in prior works are necessary to go below logarithmic round complexity. Lastly, we provide several additional upper and lower bounds for the case of single-round commit-and-reveal style protocols.



## 2024/1962

* Title: uKNIT: Breaking Round-alignment for Cipher Design -- Featuring uKNIT-BC, an Ultra Low-Latency Block Cipher
* Authors: Kai Hu, Mustafa Khairallah, Thomas Peyrin, Quan Quan Tan
* [Permalink](https://eprint.iacr.org/2024/1962)
* [Download](https://eprint.iacr.org/2024/1962.pdf)

### Abstract

Automated cryptanalysis has seen a lot of attraction and success in the past decade, leading to new distinguishers or key-recovery attacks against various ciphers. We argue that the improved efficiency and usability of these new tools have been undervalued, especially for design processes. In this article, we break for the first time the classical iterative design paradigm for symmetric-key primitives, where constructions are built around the repetition of a round function. We propose instead a new design framework, so-called uKNIT, that allows a round-by-round optimization-led automated construction of the primitives and where each round can be entirely different from the others (the security/performance trade-off actually benefiting from this non-alignment).

This new design framework being non-trivial to instantiate, we further propose a method for SPN ciphers using a genetic algorithm and leveraging advances in automated cryptanalysis: given a pool of good cipher candidates on $x$ rounds, our algorithm automatically generates and selects $(x+1)$-round candidates by evaluating their security and performance. We emphasize that our design pipeline is also the first to propose a fully automated design process, with completely integrated implementation and security analysis.

We finally exemplify our new design strategy on the important use-case of low-latency cryptography, by proposing the uKNIT-BC block cipher, together with a complete security analysis and benchmarks. Compared to the state-of-the-art in low-latency ciphers (PRINCEv2), uKNIT-BC improves on all crucial security and performance directions at the same time, reducing latency by 10%, while increasing resistance against classical differential/linear cryptanalysis by more than 10%. It also reduces area by 17% and energy consumption by 44% when fixing the latency of both ciphers. As a contribution of independent interest, we discovered a generalization of the Superposition-Tweakey (STK) construction for key schedules, unlocking its application to bit-oriented ciphers.



## 2024/1963

* Title: Proof of Time: A Method for Verifiable Temporal Commitments Without Timestamp Disclosure
* Authors: Alexander John Lee
* [Permalink](https://eprint.iacr.org/2024/1963)
* [Download](https://eprint.iacr.org/2024/1963.pdf)

### Abstract

This paper introduces a cryptographic method that enables users to prove that an event occurred in the past and that a specified amount of time has since elapsed, without disclosing the exact timestamp of the event. The method leverages zero-knowledge proofs and an on-chain Incremental Merkle Tree to store hash commitments. By utilizing the Poseidon hash function and implementing zero-knowledge circuits in Noir, this approach ensures both the integrity and confidentiality of temporal information.



## 2024/1964

* Title: Lova: Lattice-Based Folding Scheme from Unstructured Lattices
* Authors: Giacomo Fenzi, Christian Knabenhans, Ngoc Khanh Nguyen, Duc Tu Pham
* [Permalink](https://eprint.iacr.org/2024/1964)
* [Download](https://eprint.iacr.org/2024/1964.pdf)

### Abstract

Folding schemes (Kothapalli et al., CRYPTO 2022) are a conceptually simple, yet powerful cryptographic primitive that can be used as a building block to realise incrementally verifiable computation (IVC) with low recursive overhead without general-purpose non-interactive succinct arguments of knowledge (SNARK).
Most folding schemes known rely on the hardness of the discrete logarithm problem, and thus are both not quantum-resistant and operate over large prime fields. Existing post-quantum folding schemes (Boneh, Chen, ePrint 2024/257) based on lattice assumptions instead are secure under structured lattice assumptions, such as the Module Short Integer Solution Assumption (MSIS), which also binds them to relatively complex arithmetic.
In contrast, we construct Lova, the first folding scheme whose security relies on the (unstructured) SIS assumption. We provide a Rust implementation of Lova, which makes only use of arithmetic in hardware-friendly power-of-two moduli. Crucially, this avoids the need of implementing and performing any finite field arithmetic. At the core of our results lies a new exact Euclidean norm proof which might be of independent interest.



## 2024/1965

* Title: Onion Franking: Abuse Reports for Mix-Based Private Messaging
* Authors: Matthew Gregoire, Margaret Pierce, Saba Eskandarian
* [Permalink](https://eprint.iacr.org/2024/1965)
* [Download](https://eprint.iacr.org/2024/1965.pdf)

### Abstract

The fast-paced development and deployment of private messaging applications demands mechanisms to protect against the concomitant potential for abuse. While widely used end-to-end encrypted (E2EE) messaging systems have deployed mechanisms for users to verifiably report abusive messages without compromising the privacy of unreported messages, abuse reporting schemes for systems that additionally protect message metadata are still in their infancy. Existing solutions either focus on a relatively small portion of the design space or incur much higher communication and computation costs than their E2EE brethren.

This paper introduces new abuse reporting mechanisms that work for any private messaging system based on onion encryption. This includes low-latency systems that employ heuristic or opportunistic mixing of user traffic, as well as schemes based on mixnets. Along the way, we show that design decisions and abstractions that are well-suited to the E2EE setting may actually impede security and performance improvements in the metadata-hiding setting. We also explore stronger threat models for abuse reporting and moderation not explored in prior work, showing where prior work falls short and how to strengthen both our scheme and others' -- including deployed E2EE messaging platforms -- to achieve higher levels of security.

We implement a prototype of our scheme and find that it outperforms the best known solutions in this setting by well over an order of magnitude for each step of the message delivery and reporting process, with overheads almost matching those of message franking techniques used by E2EE encrypted messaging apps today.



## 2024/1966

* Title: Efficient Succinct Zero-Knowledge Arguments in the CL Framework
* Authors: Agathe Beaugrand, Guilhem Castagnos, Fabien Laguillaumie
* [Permalink](https://eprint.iacr.org/2024/1966)
* [Download](https://eprint.iacr.org/2024/1966.pdf)

### Abstract

The CL cryptosystem, introduced by Castagnos and Laguillaumie in 2015, is a linearly homomorphic encryption scheme that has seen numerous developments and applications in recent years, particularly in the field of secure multiparty computation. Designing efficient zero-knowledge proofs for the CL framework is critical, especially for achieving adaptive security for such multiparty protocols. This is a challenging task due to the particularities of class groups of quadratic fields used to instantiate the groups of unknown order required in the CL framework.

In this work, we provide efficient proofs and arguments for statements involving a large number of ciphertexts. We propose a new batched proof for correctness of CL ciphertexts and new succinct arguments for correctness of a shuffle of these ciphertexts. Previous efficient proofs of shuffle for linearly homomorphic encryption were designed for Elgamal “in the exponent” which has only a limited homomorphic property. In the line of a recent work by Braun, Damgard and Orlandi (CRYPTO 2023), all the new proofs and arguments provide partial extractability, a property that we formally introduce here. Thanks to this notion, we show that bulletproof techniques, which are in general implemented with groups of known prime order, can be applied in the CL framework despite the use of unknown order groups, giving non interactive arguments of logarithmic sizes.

To prove the practicability of our approach we have implemented these protocols with the BICYCL library, showing that computation and communication costs are competitive. We also illustrate that the partial extractability of our proofs provide enough guarantees for complex applications by presenting a bipartite private set intersection sum protocol which achieves security against malicious adversaries using CL encryption, removing limitations of a solution proposed by Miao et al. (CRYPTO 2020).



## 2024/1967

* Title: Analysis of REDOG: The Pad Thai Attack
* Authors: Alex Pellegrini, Marc Vorstermans
* [Permalink](https://eprint.iacr.org/2024/1967)
* [Download](https://eprint.iacr.org/2024/1967.pdf)

### Abstract

This paper introduces the Pad Thai message recovery attack
on REDOG, a rank-metric code-based encryption scheme selected for the
second round of evaluation in the Korean Post-Quantum Cryptography
(KPQC) competition. The attack exploits the low rank weight of a portion of the ciphertext to construct multiple systems of linear equations,
one of which is noise-free and can be solved to recover the secret message.
The Pad Thai attack significantly undermines the security of REDOG,
revealing that its provided security is much lower than originally claimed.



## 2024/1968

* Title: SoK: Pseudorandom Generation for Masked Cryptographic Implementation
* Authors: Rei Ueno, Naofumi Homma, Akiko Inoue, Kazuhiko Minematsu
* [Permalink](https://eprint.iacr.org/2024/1968)
* [Download](https://eprint.iacr.org/2024/1968.pdf)

### Abstract

This paper investigates pseudorandom generation in the context of masked cryptographic implementation. Although masking and pseudorandom generators (PRGs) have been distinctly studied for a long time, little literature studies how the randomness in the masked implementation should be generated. The lack of analysis on mask-bits generators makes the practical security of masked cryptographic implementation unclear, and practitioners (e.g., designer, implementer, and evaluator) may be confused about how to realize it. This paper provides a novel viewpoint and comprehensive analyses by developing new three models, which correspond to respective practical scenarios of leakage assessment, quantitative evaluation of side-channel security (e.g., success rate), and practical deployment. We reveal what properties are required for each scenario. In particular, we support a long-held belief/folklore with a proof: for the output of PRG for masking, cryptographic security (i.e., randomness and unpredictability) is sufficient but not necessary, but only a statistical uniformity is necessary. In addition, we thoroughly investigate the SCA security of PRGs in the wild in the masking context. We conclude this paper with some recommendations for practitioners, with a proposal of leakage-resilient method of comparative performance.



## 2024/1969

* Title: SoK: Security of the Ascon Modes
* Authors: Charlotte Lefevre, Bart Mennink
* [Permalink](https://eprint.iacr.org/2024/1969)
* [Download](https://eprint.iacr.org/2024/1969.pdf)

### Abstract

The Ascon authenticated encryption scheme and hash function of Dobraunig et al (Journal of Cryptology 2021) were recently selected as winner of the NIST lightweight cryptography competition. The mode underlying Ascon authenticated encryption (Ascon-AE) resembles ideas of SpongeWrap, but not quite, and various works have investigated the generic security of Ascon-AE, all covering different attack scenarios and with different bounds. This work systemizes knowledge on the mode security of Ascon-AE, and fills gaps where needed. We consider six mainstream security models, all in the multi-user setting: (i) nonce-respecting security, reflecting on the existing bounds of Chakraborty et al (ASIACRYPT 2023, ACISP 2024) and Lefevre and Mennink (SAC 2024), (ii) nonce-misuse resistance, observing a non-fixable flaw in the proof of Chakraborty et al (ACISP 2024), (iii) nonce-misuse resilience, delivering missing security analysis, (iv) leakage resilience, delivering a new security analysis that supersedes the informal proof sketch (though in a different model) of Guo et al (ToSC 2020), (v) state-recovery security, expanding on the analysis of Lefevre and Mennink, and (vi) release of unverified plaintext, also delivering missing security analysis. We also match all bounds with tight attacks. As a bonus, we systemize the knowledge on Ascon-Hash and Ascon-PRF (but there are no technical novelties here).



## 2024/1970

* Title: Scribe: Low-memory SNARKs via Read-Write Streaming
* Authors: Anubhav Baweja, Pratyush Mishra, Tushar Mopuri, Karan Newatia, Steve Wang
* [Permalink](https://eprint.iacr.org/2024/1970)
* [Download](https://eprint.iacr.org/2024/1970.pdf)

### Abstract

Succinct non-interactive arguments of knowledge (SNARKs) enable a prover to produce a short and efficiently verifiable proof of the validity of an arbitrary NP statement. Recent constructions of efficient SNARKs have led to interest in using them for a wide range of applications, but unfortunately, deployment of SNARKs in these applications faces a key bottleneck: SNARK provers require a prohibitive amount of time and memory to generate proofs for even moderately large statements. While there has been progress in reducing prover time, prover memory remains an issue.
 
In this work, we describe Scribe, a new low-memory SNARK that can efficiently prove large statements even on cheap consumer devices such as smartphones by leveraging a plentiful, but heretofore unutilized, resource: disk storage. In more detail, instead of storing its (large) intermediate state in RAM, Scribe's prover instead stores it on disk. To ensure that accesses to state are efficient, we design Scribe's prover in a *read-write streaming* model of computation that allows the prover to read and modify its state only in a streaming manner.

We implement and evaluate Scribe's prover, and show that, on commodity hardware, it can easily scale to circuits of size $2^{28}$ gates while using only 2GB of memory and incurring only minimal proving latency overhead (10-35%) compared to a state-of-the-art memory-intensive baseline (HyperPlonk [EUROCRYPT 2023]) that requires much more memory. Our implementation minimizes overhead by leveraging the streaming access pattern to enable several systems optimizations that together mask I/O costs.



## 2024/1971

* Title: Further Connections Between Isogenies of Supersingular Curves and Bruhat-Tits Trees
* Authors: Steven Galbraith, Valerie Gilchrist, Shai Levin, Ari Markowitz
* [Permalink](https://eprint.iacr.org/2024/1971)
* [Download](https://eprint.iacr.org/2024/1971.pdf)

### Abstract

We further explore the explicit connections between supersingular curve isogenies and Bruhat-Tits trees. By identifying a supersingular elliptic curve $E$ over $\mathbb{F}_p$ as the root of the tree, and a basis for the Tate module $T_\ell(E)$; our main result is that given a vertex $M$ of the Bruhat-Tits tree one can write down a generator of the ideal $I \subseteq \text{End}(E)$ directly, using simple linear algebra, that defines an isogeny corresponding to the path in the Bruhat-Tits tree from the root to the vertex $M$. In contrast to previous methods to go from a vertex in the Bruhat-Tits tree to an ideal, once a basis for the Tate module is set up and an explicit map $\Phi : \text{End}(E) \otimes_{\mathbb{Z}_\ell} \to M_2( \mathbb{Z}_\ell )$ is constructed, our method does not require any computations involving elliptic curves, isogenies, or discrete logs. This idea leads to simplifications and potential speedups to algorithms for converting between isogenies and ideals.



## 2024/1972

* Title: RoK, Paper, SISsors – Toolkit for Lattice-based Succinct Arguments
* Authors: Michael Klooß, Russell W. F. Lai, Ngoc Khanh Nguyen, Michał Osadnik
* [Permalink](https://eprint.iacr.org/2024/1972)
* [Download](https://eprint.iacr.org/2024/1972.pdf)

### Abstract

Lattice-based succinct arguments allow to prove bounded-norm satisfiability of relations, such as $f(\vec{s}) = \vec{t} \bmod q$ and $\|\vec{s}\|\leq \beta$, over specific cyclotomic rings $\mathcal{O}_\mathcal{K}$, with proof size polylogarithmic in the witness size. However, state-of-the-art protocols require either 1) a super-polynomial size modulus $q$ due to a soundness gap in the security argument, or 2) a verifier which runs in time linear in the witness size. Furthermore, construction techniques often rely on specific choices of $\mathcal{K}$ which are not mutually compatible. In this work, we exhibit a diverse toolkit for constructing efficient lattice-based succinct arguments:

  (i) We identify new subtractive sets for general cyclotomic fields $\mathcal{K}$ and their maximal real subfields $\mathcal{K}^+$, which are useful as challenge sets, e.g. in arguments for exact norm bounds.
 (ii) We construct modular, verifier-succinct reductions of knowledge for the bounded-norm satisfiability of structured-linear/inner-product relations, without any soundness gap, under the vanishing SIS assumption, over any $\mathcal{K}$ which admits polynomial-size subtractive sets.
(iii) We propose a framework to use twisted trace maps, i.e. maps of the form $\tau(z) = \frac{1}{N} \cdot \mathsf{Trace}_{\mathcal{K}/\mathbb{Q}}( \alpha \cdot z )$, to embed $\mathbb{Z}$-inner-products as $\mathcal{R}$-inner-products for some structured subrings $\mathcal{R} \subseteq \mathcal{O}_\mathcal{K}$ whenever the conductor has a square-free odd part.
(iv) We present a simple extension of our reductions of knowledge for proving the consistency between the coefficient embedding and the Chinese Remainder Transform (CRT) encoding of $\vec{s}$ over any cyclotomic field $\mathcal{K}$ with a smooth conductor, based on a succinct decomposition of the CRT map into automorphisms, and a new, simple succinct argument for proving automorphism relations.

Combining all techniques, we obtain, for example, verifier-succinct arguments for proving that $\vec{s}$ satisfying $f(\vec{s}) = \vec{t} \bmod q$ has binary coefficients, without soundness gap and with polynomial-size modulus $q$.