## 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


[continued in next message]

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