## In this issue

1. [2022/1336] One-Wayness in Quantum Cryptography
2. [2024/677] Asynchronous Consensus without Trusted Setup or ...
3. [2024/678] Quantum-Safe Account Recovery for WebAuthn
4. [2024/679] Isotropic Quadratic Forms, Diophantine Equations ...
5. [2024/680] Universal Vector Commitments
6. [2024/681] HRA-Secure Homomorphic Lattice-Based Proxy Re- ...
7. [2024/682] Approximate PSI with Near-Linear Communication
8. [2024/683] A note on ``a new password-authenticated module ...
9. [2024/684] A Plug-and-Play Long-Range Defense System for ...
10. [2024/685] Committing AVID with Partial Retrieval and Optimal ...
11. [2024/686] Unstructured Inversions of New Hope
12. [2024/687] Levin–Kolmogorov Complexity is not in Linear Time
13. [2024/688] Succinct Functional Commitments for Circuits from k-Lin
14. [2024/689] Automated Creation of Source Code Variants of a ...
15. [2024/690] LPN-based Attacks in the White-box Setting
16. [2024/691] White-box filtering attacks breaking SEL masking: ...
17. [2024/692] Blink: An Optimal Proof of Proof-of-Work
18. [2024/693] A Note of $\mathsf{Anemoi}$ Gröbner Bases
19. [2024/694] Lower-Bounds on Public-Key Operations in PIR
20. [2024/695] Beale Cipher 1 and Cipher 3: Numbers With No Messages
21. [2024/696] A Theoretical Take on a Practical Consensus Protocol
22. [2024/697] LINE: Cryptosystem based on linear equations for ...
23. [2024/698] Private Computations on Streaming Data
24. [2024/699] An Efficient All-to-All GCD Algorithm for Low ...
25. [2024/700] Sublinear Distributed Product Checks on Replicated ...
26. [2024/701] Quantum Unpredictability
27. [2024/702] Security Analysis of Signal's PQXDH Handshake
28. [2024/703] An Efficient and Extensible Zero-knowledge Proof ...
29. [2024/704] Fully Automated Selfish Mining Analysis in ...
30. [2024/705] Large-Scale MPC: Scaling Private Iris Code ...
31. [2024/706] Linicrypt in the Ideal Cipher Model
32. [2024/707] Towards a Polynomial Instruction Based Compiler for ...
33. [2024/708] Automated Generation of Fault-Resistant Circuits
34. [2024/709] Masked Computation the Floor Function and its ...
35. [2024/710] BUFFing FALCON without Increasing the Signature Size
36. [2024/711] Non-Transferable Anonymous Tokens by Secret Binding
37. [2024/712] Quantum NV Sieve on Grover for Solving Shortest ...
38. [2024/713] Analyzing Pump and jump BKZ algorithm using ...
39. [2024/714] Learning with Quantization, Polar Quantizer, and ...
40. [2024/715] A New Cryptographic Algorithm
41. [2024/716] Unclonable Secret Sharing
42. [2024/717] An Improved Threshold Homomorphic Cryptosystem ...
43. [2024/718] PAC-Private Algorithms
44. [2024/719] Client-Efficient Online-Offline Private Information ...
45. [2024/720] MQ maps are not binding - Revisiting Multivariate ...
46. [2024/721] Real-world Universal zkSNARKs are non-malleable
47. [2024/722] Ultrametric integral cryptanalysis
48. [2024/723] $\mathsf{OPA}$: One-shot Private Aggregation with ...

## 2022/1336

* Title: One-Wayness in Quantum Cryptography
* Authors: Tomoyuki Morimae, Takashi Yamakawa
* [Permalink](https://eprint.iacr.org/2022/1336)
* [Download](https://eprint.iacr.org/2022/1336.pdf)

### Abstract

The existence of one-way functions is one of the most fundamental assumptions in classical cryptography. In the quantum world, on the other hand, there are evidences that some cryptographic primitives can exist even if one-way functions do not exist [Morimae and Yamakawa, CRYPTO 2022; Ananth, Qian, and Yuen, CRYPTO 2022]. We therefore have the following important open problem in quantum cryptography: What is the most fundamental element in quantum cryptography? In this direction, Brakerski, Canetti, and Qian [arXiv:2209.04101] recently defined a notion called EFI pairs, which are pairs of efficiently generatable states that are statistically distinguishable but computationally indistinguishable, and showed its equivalence with some cryptographic primitives including commitments, oblivious transfer, and general multi-party computations. However, their work focuses on decision-type primitives and does not cover search-type primitives like quantum money and digital signatures. In this paper, we study properties of one-way state generators (OWSGs), which are a quantum analogue of one-way functions proposed by Morimae and Yamakawa. We first revisit the definition of OWSGs and generalize it by allowing mixed output states. Then we show the following results.

(1) We define a weaker version of OWSGs, which we call weak OWSGs, and show that they are equivalent to OWSGs. It is a quantum analogue of the amplification theorem for classical weak one-way functions.

(2) (Bounded-time-secure) quantum digital signatures with quantum public keys are equivalent to OWSGs.

(3) Private-key quantum money schemes (with pure money states) imply OWSGs.

(4) Quantum pseudo one-time pad schemes imply both OWSGs and EFI pairs. For EFI pairs, single-copy security suffices.

(5) We introduce an incomparable variant of OWSGs, which we call secretly-verifiable and statistically-invertible OWSGs, and show that they are equivalent to EFI pairs.

## 2024/677

* Title: Asynchronous Consensus without Trusted Setup or Public-Key Cryptography
* Authors: Sourav Das, Sisi Duan, Shengqi Liu, Atsuki Momose, Ling Ren, Victor Shoup
* [Permalink](https://eprint.iacr.org/2024/677)
* [Download](https://eprint.iacr.org/2024/677.pdf)

### Abstract

Byzantine consensus is a fundamental building block in distributed cryptographic problems. Despite decades of research, most existing asynchronous consensus protocols require a strong trusted setup and expensive public-key cryptography. In this paper, we study asynchronous Byzantine consensus protocols that do not rely on a trusted setup and do not use public-key cryptography such as digital signatures. We give an Asynchronous Common Subset (ACS) protocol whose security is only based on cryptographic hash functions modeled as a random oracle. Our protocol has $O(\kappa n^3)$ total communication and runs in expected $O(1)$ rounds. The fact that we use only cryptographic hash functions also means that our protocol is post-quantum secure. The minimal use of cryptography and the small number of rounds make our protocol practical. We implement our protocol and evaluate it in a geo-distributed setting with up to 128 machines. Our experimental evaluation shows that our protocol is more efficient than the only other setup-free consensus protocol that has been implemented to date. En route to our asynchronous consensus protocols, we also introduce new primitives called asynchronous secret key sharing and cover gather, which may be of independent interest.

## 2024/678

* Title: Quantum-Safe Account Recovery for WebAuthn
* Authors: Douglas Stebila, Spencer Wilson
* [Permalink](https://eprint.iacr.org/2024/678)
* [Download](https://eprint.iacr.org/2024/678.pdf)

### Abstract

WebAuthn is a passwordless authentication protocol which allows users to authenticate to online services using public-key cryptography. Users prove their identity by signing a challenge with a private key, which is stored on a device such as a cell phone or a USB security token. This approach avoids many of the common security problems with password-based authentication.

WebAuthn's reliance on proof-of-possession leads to a usability issue, however: a user who loses access to their authenticator device either loses access to their accounts or is required to fall back on a weaker authentication mechanism. To solve this problem, Yubico has proposed a protocol which allows a user to link two tokens in such a way that one (the primary authenticator) can generate public keys on behalf of the other (the backup authenticator). With this solution, users authenticate with a single token, only relying on their backup token if necessary for account recovery. However, Yubico's protocol relies on the hardness of the discrete logarithm problem for its security and hence is vulnerable to an attacker with a powerful enough quantum computer.

We present a WebAuthn recovery protocol which can be instantiated with quantum-safe primitives. We also critique the security model used in previous analysis of Yubico's protocol and propose a new framework which we use to evaluate the security of both the group-based and the quantum-safe protocol. This leads us to uncover a weakness in Yubico's proposal which escaped detection in prior work but was revealed by our model. In our security analysis, we require the cryptographic primitives underlying the protocols to satisfy a number of novel security properties such as KEM unlinkability, which we formalize. We prove that well-known quantum-safe algorithms, including CRYSTALS-Kyber, satisfy the properties required for analysis of our quantum-safe protocol.

## 2024/679

* Title: Isotropic Quadratic Forms, Diophantine Equations and Digital Signatures
* Authors: Martin Feussner, Igor Semaev
* [Permalink](https://eprint.iacr.org/2024/679)
* [Download](https://eprint.iacr.org/2024/679.pdf)

### Abstract

This work introduces DEFI - an efficient hash-and-sign digital signature scheme based on isotropic quadratic forms over a commutative ring of characteristic 0. The form is public, but the construction is a trapdoor that depends on the scheme's private key. For polynomial rings over integers and rings of integers of algebraic number fields, the cryptanalysis is reducible to solving a quadratic Diophantine equation over the ring or, equivalently, to solving a system of quadratic Diophantine equations over rational integers. It is still an open problem whether quantum computers will have any advantage in solving Diophantine problems.

## 2024/680

* Title: Universal Vector Commitments
* Authors: Ojaswi Acharya, Foteini Baldimtsi, Samuel Dov Gordon, Daniel McVicker, Aayush Yadav
* [Permalink](https://eprint.iacr.org/2024/680)
* [Download](https://eprint.iacr.org/2024/680.pdf)

### Abstract

We propose a new notion of vector commitment schemes with proofs of (non-)membership that we call universal vector commitments. We show how to build them directly from (i) Merkle commitments, and (ii) a universal accumulator and a plain vector commitment scheme. We also present a generic construction for universal accumulators over large domains from any vector commitment scheme, using cuckoo hashing. Leveraging the aforementioned generic constructions, we show that universal vector commitment schemes are implied by plain vector commitments and cuckoo hashing.

## 2024/681

* Title: HRA-Secure Homomorphic Lattice-Based Proxy Re-Encryption with Tight Security
* Authors: Aloni Cohen, David Bruce Cousins, Nicholas Genise, Erik Kline, Yuriy Polyakov, Saraswathy RV
* [Permalink](https://eprint.iacr.org/2024/681)
* [Download](https://eprint.iacr.org/2024/681.pdf)

### Abstract

We construct an efficient proxy re-encryption (PRE) scheme secure against honest re-encryption attacks (HRA-secure) with precise concrete security estimates. To get these precise concrete security estimates, we introduce the tight, fine-grained noise-flooding techniques of Li et al. (CRYPTO'22) to RLWE-based (homomorphic) PRE schemes, as well as a mixed statistical-computational security to HRA security analysis. Our solution also supports homomorphic operations on the ciphertexts. Such homomorphism allows for advanced applications, e.g., encrypted computation of network statistics across networks and unlimited hops, in the case of full homomorphism, i.e., bootstrapping.

We implement our PRE scheme in the OpenFHE software library and apply it to a problem of secure multi-hop data distribution in the context of 5G virtual network slices. We also experimentally evaluate the performance of our scheme, demonstrating that the implementation is practical.

In addition, we compare our PRE method with other lattice-based PRE schemes and approaches to achieve HRA security. These achieve HRA security, but not in a tight, practical scheme such as our work. Further, we present an attack on the PRE scheme proposed in Davidson et al.'s (ACISP'19), which was claimed to achieve HRA security without noise flooding.

## 2024/682

* Title: Approximate PSI with Near-Linear Communication
* Authors: Wutichai Chongchitmate, Steve Lu, Rafail Ostrovsky
* [Permalink](https://eprint.iacr.org/2024/682)
* [Download](https://eprint.iacr.org/2024/682.pdf)

### Abstract

Private Set Intersection (PSI) is a protocol where two parties with individually held confidential sets want to jointly learn (or secret-share) the intersection of these two sets and reveal nothing else to each other. In this paper, we introduce a natural extension of this notion to approximate matching. Specifically, given a distance metric between elements, an approximate PSI (Approx-PSI) allows to run PSI where ``close'' elements match. Assuming that elements are either ``close'' or sufficiently ``far apart'', we present an Approx-PSI protocol for Hamming distance that dramatically improves the overall efficiency compared to all existing approximate-PSI solutions. In particular, we achieve a near-linear $\tilde{O}(n)$ communication complexity, an improvement over the previously best-known $\tilde{O}(n^2)$. We also show Approx-PSI protocols for Edit distance (also known as Levenstein distance), Euclidean distance and angular distance by deploying results on low distortion embeddings to Hamming distance. The latter two results further imply secure Approx-PSI for other metrics such as cosine similarity metric. Our Approx-PSI for Hamming distance is up to 20x faster and communicating 30% less than best known protocols when (1) matching small binary vectors; or (2) matching large threshold; or (3) matching large input sets. We demonstrate that the protocol can be used to match similar images through spread spectrum of the images.

## 2024/683

* Title: A note on ``a new password-authenticated module learning with rounding-based key exchange protocol: Saber.PAKE''
* Authors: Zhengjun Cao, Lihua Liu
* [Permalink](https://eprint.iacr.org/2024/683)
* [Download](https://eprint.iacr.org/2024/683.pdf)

### Abstract

We show the Seyhan-Akleylek key exchange protocol [J. Supercomput., 2023, 79:17859-17896] cannot resist offline dictionary attack and impersonation attack, not as claimed.

## 2024/684

* Title: A Plug-and-Play Long-Range Defense System for Proof-of-Stake Blockchains
* Authors: Lucien K. L. Ng, Panagiotis Chatzigiannis, Duc V. Le, Mohsen Minaei, Ranjit Kumaresan, Mahdi Zamani
* [Permalink](https://eprint.iacr.org/2024/684)
* [Download](https://eprint.iacr.org/2024/684.pdf)

### Abstract

In recent years, many blockchain systems have progressively transitioned to proof-of-stake (PoS) con- sensus algorithms. These algorithms are not only more energy efficient than proof-of-work but are also well-studied and widely accepted within the community. However, PoS systems are susceptible to a particularly powerful "long-range" attack, where an adversary can corrupt the validator set retroactively and present forked versions of the blockchain. These versions would still be acceptable to clients, thereby creating the potential for double-spending. Several methods and research efforts have proposed counter- measures against such attacks. Still, they often necessitate modifications to the underlying blockchain, introduce heavy assumptions such as centralized entities, or prove inefficient for securely bootstrapping light clients.
In this work, we propose a method of defending against these attacks with the aid of external servers running our protocol. Our method does not require any soft or hard-forks on the underlying blockchain and operates under reasonable assumptions, specifically the requirement of at least one honest server.
Central to our approach is a new primitive called "Insertable Proof of Sequential Work" (InPoSW). Traditional PoSW ensures that a server performs computational tasks that cannot be parallelized and require a minimum execution time, effectively timestamping the input data. InPoSW additionally allows the prover to "insert" new data into an ongoing InPoSW instance. This primitive can be of independent interest for other timestamp applications. Compared to naively adopting prior PoSW schemes for In-PoSW, our construction achieves >22× storage reduction on the server side and >17900× communication cost reduction for each verification.

## 2024/685

* Title: Committing AVID with Partial Retrieval and Optimal Storage
* Authors: Nicolas Alhaddad, Leonid Reyzin, Mayank Varia
* [Permalink](https://eprint.iacr.org/2024/685)
* [Download](https://eprint.iacr.org/2024/685.pdf)

### Abstract

Asynchronous Verifiable Information Dispersal (AVID) allows a dealer to disperse a message $M$ across a collection of server replicas consistently and efficiently, such that any future client can reliably retrieve the message $M$ if some servers fail.
Since AVID was introduced by Cachin and Tessaro in 2005, several works improved the asymptotic communication complexity of AVID protocols.
However, recent gains in communication complexity have come at the expense of sub-optimal storage, which is the dominant cost in long-term archiving.
Moreover, recent works do not provide a mechanism to detect errors until the retrieval stage, which may result in completely wasted long-term storage if the dealer is malicious.

In this work, we contribute a new AVID construction that achieves optimal storage and guaranteed output delivery, without sacrificing on communication complexity during dispersal or retrieval.
First, we introduce a technique that bootstraps from dispersal of a message with sub-optimal storage to one with optimal storage.
Second, we define and construct an AVID protocol that is robust, meaning that all server replicas are guaranteed at dispersal time that their fragments will contribute toward retrieval of a valid message.
Third, we add the new possibility that some server replicas may lose their fragment in between dispersal and retrieval (as is likely in the long-term archiving scenario).
This allows us to rely on fewer available replicas for retrieval than are required for dispersal.

## 2024/686

* Title: Unstructured Inversions of New Hope
* Authors: Ian Malloy
* [Permalink](https://eprint.iacr.org/2024/686)
* [Download](https://eprint.iacr.org/2024/686.pdf)

### Abstract

Introduced as a new protocol implemented in “Chrome Canary” for the Google Inc. Chrome browser,
“New Hope” is engineered as a post-quantum key exchange for the TLS 1.2 protocol. The structure of
the exchange is revised lattice-based cryptography. New Hope incorporates the key-encapsulation
mechanism of Peikert which itself is a modified Ring-LWE scheme. The search space used to introduce
the closest-vector problem is generated by an intersection of a tesseract and hexadecachoron, or the ℓ∞-
ball and ℓ1-ball respectively. This intersection results in the 24-cell 𝒱 of lattice 𝒟̃4. With respect to the
density of the Voronoi cell 𝒱, the proposed mitigation against backdoor attacks proposed by the authors
of New Hope may not withstand such attempts if enabled by a quantum computer capable of
implementing Grover’s search algorithm.

## 2024/687

* Title: Levin–Kolmogorov Complexity is not in Linear Time
* Authors: Nicholas Brandt
* [Permalink](https://eprint.iacr.org/2024/687)
* [Download](https://eprint.iacr.org/2024/687.pdf)

### Abstract

Understanding the computational hardness of Kolmogorov complexity is a central open question in complexity theory.
An important notion is Levin's version of Kolmogorov complexity, Kt, and its decisional variant, MKtP,
due to its connections to universal search, derandomization, and oneway functions, among others.
The question whether MKtP can be computed in polynomial time is particularly interesting because it is not subject to known technical barriers such as algebrization or natural proofs that would explain the lack of a proof for MKtP not in P.

We take a significant step towards proving MKtP not in P by developing an algorithmic approach for showing unconditionally that MKtP not in DTIME[O(n)] cannot be decided in deterministic linear time in the worst-case.
This allows us to partially affirm a conjecture by Ren and Santhanam [STACS:RS22] about a non-halting variant of Kt complexity.
Additionally, we give conditional lower bounds for MKtP that tolerate either more runtime or one-sided error.

## 2024/688

* Title: Succinct Functional Commitments for Circuits from k-Lin
* Authors: Hoeteck Wee, David J. Wu
* [Permalink](https://eprint.iacr.org/2024/688)
* [Download](https://eprint.iacr.org/2024/688.pdf)

### Abstract

A functional commitment allows a user to commit to an input $\mathbf{x}$ and later, open the commitment to an arbitrary function $\mathbf{y} = f(\mathbf{x})$. The size of the commitment and the opening should be sublinear in $|\mathbf{x}|$ and $|f|$.

In this work, we give the first pairing-based functional commitment for arbitrary circuits where the size of the commitment and the size of the opening consist of a constant number of group elements. Security relies on the standard bilateral $k$-$\mathsf{Lin}$ assumption. This is the first scheme with this level of succinctness from falsifiable bilinear map assumptions (previous approaches required SNARKs for $\mathsf{NP}$). This is also the first functional commitment scheme for general circuits with $\mathsf{poly}(\lambda)$-size commitments and openings from any assumption that makes fully black-box use of cryptographic primitives and algorithms. As an immediate consequence, we also obtain a succinct non-interactive argument for arithmetic circuits (i.e., a SNARG for $\mathsf{P}/\mathsf{poly}$) with a universal setup and where the proofs consist of a constant number of group elements. In particular, the CRS in our SNARG only depends on the size of the arithmetic circuit $|C|$ rather than the circuit $C$ itself; the same CRS can be used to verify computations with respect to different circuits. Our construction relies on a new notion of projective chainable commitments which may be of independent interest.

## 2024/689

* Title: Automated Creation of Source Code Variants of a Cryptographic Hash Function Implementation Using Generative Pre-Trained Transformer Models
* Authors: Elijah Pelofske, Vincent Urias, Lorie M. Liebrock
* [Permalink](https://eprint.iacr.org/2024/689)
* [Download](https://eprint.iacr.org/2024/689.pdf)

### Abstract

Generative pre-trained transformers (GPT's) are a type of large language machine learning model that are unusually adept at producing novel, and coherent, natural language. Notably, these technologies have also been extended to computer programming languages with great success. However, GPT model outputs in general are stochastic and not always correct. For programming languages, the exact specification of the computer code, syntactically and algorithmically, is strictly required in order to ensure the security of computing systems and applications. Therefore, using GPT models to generate computer code poses an important security risk -- while at the same time allowing for potential innovation in how computer code is generated. In this study the ability of GPT models to generate novel and correct versions, and notably very insecure versions, of implementations of the cryptographic hash function SHA-1 is examined. The GPT models Llama-2-70b-chat-hf, Mistral-7B-Instruct-v0.1, and zephyr-7b-alpha are used. The GPT models are prompted to re-write each function using a modified version of the localGPT framework and langchain to provide word embedding context of the full source code and header files to the model, resulting in over $130,000$ function re-write GPT output text blocks (that are potentially correct source code), approximately $40,000$ of which were able to be parsed as C code and subsequently compiled. The generated code is analyzed for being compilable, correctness of the algorithm, memory leaks, compiler optimization stability, and character distance to the reference implementation. Remarkably, several generated function variants have a high implementation security risk of being correct for some test vectors, but incorrect for other test vectors. Additionally, many function implementations were not correct to the reference algorithm of SHA-1, but produced hashes that have some of the basic characteristics of hash functions. Many of the function re-writes contained serious flaws such as memory leaks, integer overflows, out of bounds accesses, use of uninitialised values, and compiler optimization instability. Compiler optimization settings and SHA-256 hash checksums of the compiled binaries are used to cluster implementations that are equivalent but may not have identical syntax - using this clustering over $100,000$ distinct, novel, and correct versions of the SHA-1 codebase were generated where each component C function of the reference implementation is different from the original code.

## 2024/690

* Title: LPN-based Attacks in the White-box Setting
* Authors: Alex Charlès, Aleksei Udovenko
* [Permalink](https://eprint.iacr.org/2024/690)
* [Download](https://eprint.iacr.org/2024/690.pdf)

### Abstract

In white-box cryptography, early protection techniques have fallen to the automated Differential Computation Analysis attack (DCA), leading to new countermeasures and attacks. A standard side-channel countermeasure, Ishai-Sahai-Wagner's masking scheme (ISW, CRYPTO 2003) prevents Differential Computation Analysis but was shown to be vulnerable in the white-box context to the Linear Decoding Analysis attack (LDA). However, recent quadratic and cubic masking schemes by Biryukov-Udovenko (ASIACRYPT 2018) and Seker-Eisenbarth-Liskiewicz (CHES 2021) prevent LDA and force to use its higher-degree generalizations with much higher complexity.

In this work, we study the relationship between the security of these and related schemes to the Learning Parity with Noise (LPN) problem and propose a new automated attack by applying an LPN-solving algorithm to white-box implementations. The attack effectively exploits strong linear approximations of the masking scheme and thus can be seen as a combination of the DCA and LDA techniques. Different from previous attacks, the complexity of this algorithm depends on the approximation error, henceforth allowing new practical attacks on masking schemes that previously resisted automated analysis. We demonstrate it theoretically and experimentally, exposing multiple cases where the LPN-based method significantly outperforms LDA and DCA methods, including their higher-order variants.

This work applies the LPN problem beyond its usual post-quantum cryptography boundary, strengthening its interest in the cryptographic community, while expanding the range of automated attacks by presenting a new direction for breaking masking schemes in the white-box model.

## 2024/691

* Title: White-box filtering attacks breaking SEL masking: from exponential to polynomial time
* Authors: Alex Charlès, Aleksei Udovenko
* [Permalink](https://eprint.iacr.org/2024/691)
* [Download](https://eprint.iacr.org/2024/691.pdf)

### Abstract

This work proposes a new white-box attack technique called filtering, which can be combined with any other trace-based attack method. The idea is to filter the traces based on the value of an intermediate variable in the implementation, aiming to fix a share of a sensitive value and degrade the security of an involved masking scheme.

Coupled with LDA (filtered LDA, FLDA), it leads to an attack defeating the state-of-the-art SEL masking scheme (CHES 2021) of arbitrary degree and number of linear shares with quartic complexity in the window size. In comparison, the current best attacks have exponential complexities in the degree (higher degree decoding analysis, HDDA), in the number of linear shares (higher-order differential computation analysis, HODCA), or the window size (white-box learning parity with noise, WBLPN).

The attack exploits the key idea of the SEL scheme - an efficient parallel combination of the nonlinear and linear masking schemes. We conclude that a proper composition of masking schemes is essential for security.

In addition, we propose several optimizations for linear algebraic attacks: redundant node removal (RNR), optimized parity check matrix usage, and chosen-plaintext filtering (CPF), significantly improving the performance of security evaluation of white-box implementations.

## 2024/692

* Title: Blink: An Optimal Proof of Proof-of-Work
* Authors: Lukas Aumayr, Zeta Avarikioti, Matteo Maffei, Giulia Scaffino, Dionysis Zindros
* [Permalink](https://eprint.iacr.org/2024/692)
* [Download](https://eprint.iacr.org/2024/692.pdf)

### Abstract

Designing light clients for Proof-of-Work blockchains has been a foundational problem since Nakamoto's SPV construction in the Bitcoin paper. Over the years, communication was reduced from O(C) down to O(polylog(C)) in the system's lifetime C. We present Blink, the first provably secure O(1) light client that does not require a trusted setup.

## 2024/693

* Title: A Note of $\mathsf{Anemoi}$ Gröbner Bases
* Authors: Pierre Briaud
* [Permalink](https://eprint.iacr.org/2024/693)
* [Download](https://eprint.iacr.org/2024/693.pdf)

### Abstract

Recently, [eprint/2024/250] and [eprint/2024/347] proposed two algebraic attacks on the $\mathsf{Anemoi}$ permutation [Crypto '23]. In this note, we construct a Gröbner basis for the ideal generated by the naive modeling of the $\mathsf{CICO}$ problem associated to $\mathsf{Anemoi}$, in odd and in even characteristics, for one and several branches. We also infer the degree of the ideal from this Gröbner basis, while previous works relied on upper bounds.

## 2024/694

* Title: Lower-Bounds on Public-Key Operations in PIR
* Authors: Jesko Dujmovic, Mohammad Hajiabadi
* [Permalink](https://eprint.iacr.org/2024/694)
* [Download](https://eprint.iacr.org/2024/694.pdf)

### Abstract

Private information retrieval (PIR) is a fundamental cryptographic primitive that allows a user to fetch a database entry without revealing to the server which database entry it learns. PIR becomes non-trivial if the server communication is less than the database size. We show that building (even) very weak forms of single-server PIR protocols, without pre-processing, requires the number of public-key operations to scale linearly in the database size. This holds irrespective of the number of symmetric-key operations performed by the parties.
We then use this bound to examine the related problem of communication efficient oblivious transfer (OT) extension.
Oblivious transfer is a crucial building block in secure multi-party computation (MPC). In most MPC protocols, OT invocations are the main bottleneck in terms of computation and communication. OT extension techniques allow one to minimize the number of public-key operations in MPC protocols. One drawback of all existing OT extension protocols is their communication overhead. In particular, the sender’s communication is roughly double what is information-theoretically optimal.
We show that OT extension with close to optimal sender communication is impossible, illustrating that the communication overhead is inherent. Our techniques go much further; we can show many lower bounds on communication-efficient MPC. E.g., we prove that to build high-rate string OT from generic groups, the sender needs to do linearly many group operations

## 2024/695

* Title: Beale Cipher 1 and Cipher 3: Numbers With No Messages
* Authors: Richard Wassmer
* [Permalink](https://eprint.iacr.org/2024/695)
* [Download](https://eprint.iacr.org/2024/695.pdf)

### Abstract

This paper's purpose is to give a new method of analyzing Beale Cipher 1 and Cipher 3 and to show that there is no key which will decipher them into sentences.
Previous research has largely used statistical methods to
either decipher them or prove they have no solution. Some
of these methods show that there is a high probability, but not certainty that they are unsolvable. Both ciphers remain unsolved.
The methods used in this paper are not statistical ones
based on thousands of samples. The evidence given here shows there is a high correlation between locations of certain numbers in the ciphers with locations in the written text that was given with these ciphers in the 1885 pamphlet called "The Beale Papers".
Evidence is correlated with a long monotonically increasing Gillogly String in Cipher 1, when translated with the Declaration of Independence given in the pamphlet.
The Beale Papers' writer was anonymous, and words in the three written letters in the 1885 pamphlet are compared with locations of numbers in the ciphers to show who the writer was.
Emphasis is on numbers which are controllable by the encipherer. Letter location sums are used when they are the most plausible ones found.
Evidence supports the statement that Cipher 1 and Cipher 3 are unintelligible. It also supports the statement that they were designed to have no intelligible sentences because they were part of a complex game made by the anonymous writer of The Beale Papers.

## 2024/696

* Title: A Theoretical Take on a Practical Consensus Protocol
* Authors: Victor Shoup
* [Permalink](https://eprint.iacr.org/2024/696)
* [Download](https://eprint.iacr.org/2024/696.pdf)

### Abstract

The Asynchronous Common Subset (ACS) problem is a fundamental problem in distributed computing. Very recently, Das et al. (2024) developed a new ACS protocol with several desirable properties: (i) it provides optimal resilience, tolerating up to $t < n/3$ corrupt parties out of $n$ parties in total, (ii) it does not rely on a trusted set up, (iii) it utilizes only "lighweight" cryptography, which can be instantiated using just a hash function, and (iv) it has expected round complexity $O(1)$ and expected communication complexity $O(\kappa n^3)$, where $\kappa$ is the output-length of the hash function. The purpose of this paper is to give a detailed, self-contained exposition and analysis of this protocol from the point of view of modern theoretcal cryptography, fleshing out a number of details of the definitions and proofs, providing a complete security analysis based on concrete security assumptions on the hash function (i.e., without relying on random oracles), and developing all of the underlying theory in the universal composability framework.

## 2024/697

* Title: LINE: Cryptosystem based on linear equations for logarithmic signatures
* Authors: Gennady Khalimov, Yevgen Kotukh, Maksym Kolisnyk, Svitlana Khalimova, Oleksandr Sievierinov
* [Permalink](https://eprint.iacr.org/2024/697)
* [Download](https://eprint.iacr.org/2024/697.pdf)

### Abstract

The discourse herein pertains to a directional encryption cryptosystem predicated upon logarithmic signatures interconnected via a system of linear equations (we call it LINE). A logarithmic signature serves as a foundational cryptographic primitive within the algorithm, characterized by distinct cryptographic attributes including nonlinearity, noncommutativity, unidirectionality, and factorizability by key. The confidentiality of the cryptosystem is contingent upon the presence of an incomplete system of equations and the substantial ambiguity inherent in the matrix transformations integral to the algorithm. Classical cryptanalysis endeavors are constrained by the potency of the secret matrix transformation and the indeterminacy surrounding solutions to the system of linear equations featuring logarithmic signatures. Such cryptanalysis methodologies, being exhaustive in nature, invariably exhibit exponential complexity. The absence of inherent group computations within the algorithm, and by extension, the inability to exploit group properties associated with the periodicity of group elements, serves to mitigate quantum cryptanalysis to Grover's search algorithm. LINE is predicated upon an incomplete system of linear equations embodies the security levels ranging from 1 to 5, as stipulated by the NIST, and thus presents a promising candidate for the construction of post-quantum cryptosystems.

## 2024/698

* Title: Private Computations on Streaming Data
* Authors: Vladimir Braverman, Kevin Garbe, Eli Jaffe, Rafail Ostrovsky
* [Permalink](https://eprint.iacr.org/2024/698)
* [Download](https://eprint.iacr.org/2024/698.pdf)

### Abstract

We present a framework for privacy-preserving streaming algorithms which combine the memory-efficiency of streaming algorithms with strong privacy guarantees. These algorithms enable some number of servers to compute aggregate statistics efficiently on large quantities of user data without learning the user's inputs. While there exists limited prior work that fits within our model, our work is the first to formally define a general framework, interpret existing methods within this general framework, and develop new tools broadly applicable to this model. To highlight our model, we designed and implemented a new privacy-preserving streaming algorithm to compute heavy hitters, which are the most frequent elements in a data stream. We provide a performance comparison between our system and Poplar, the only other private statistics algorithm which supports heavy hitters. We benchmarked ours and Poplar's systems and provided direct performance comparisons within the same hardware platform. Of note, Poplar requires linear space compared to our poly-logarithmic space, meaning our system is the first to compute heavy hitters within the privacy-preserving streaming model. A small memory footprint allows our algorithm (among other benefits) to run efficiently on a very large input sizes without running out of memory or crashing.

## 2024/699

* Title: An Efficient All-to-All GCD Algorithm for Low Entropy RSA Key Factorization
* Authors: Elijah Pelofske
* [Permalink](https://eprint.iacr.org/2024/699)
* [Download](https://eprint.iacr.org/2024/699.pdf)

### Abstract

RSA is an incredibly successful and useful asymmetric encryption algorithm. One of the types of implementation flaws in RSA is low entropy of the key generation, specifically the prime number creation stage. This can occur due to flawed usage of random prime number generator libraries, or on computers where there is a lack of a source of external entropy. These implementation flaws result in some RSA keys sharing prime factors, which means that the full factorization of the public modulus can be recovered incredibly efficiently by performing a computation GCD between the two public key moduli that share the prime factor. However, since one does not know which of the composite moduli share a prime factor a-priori, to determine if any such shared prime factors exist, an all-to-all GCD attack (also known as a batch GCD attack, or a bulk GCD attack) can be performed on the available public keys so as to recover any shared prime factors. This study describes a novel all-to-all batch GCD algorithm, which will be referred to as the binary tree batch GCD algorithm, that is more efficient than the current best batch GCD algorithm (the remainder tree batch GCD algorithm). A comparison against the best existing batch GCD method (which is a product tree followed by a remainder tree computation) is given using a dataset of random RSA moduli that are constructed such that some of the moduli share prime factors. This proposed binary tree batch GCD algorithm has better runtime than the existing remainder tree batch GCD algorithm, although asymptotically it has nearly identical scaling and its complexity is dependent on how many shared prime factors exist in the set of RSA keys. In practice, the implementation of the proposed binary tree batch GCD algorithm has a roughly 6x speedup compared to the standard remainder tree batch GCD approach.

## 2024/700

* Title: Sublinear Distributed Product Checks on Replicated Secret-Shared Data over $\mathbb{Z}_{2^k}$ without Ring Extensions
* Authors: Yun Li, Daniel Escudero, Yufei Duan, Zhicong Huang, Cheng Hong, Chao Zhang, Yifan Song
* [Permalink](https://eprint.iacr.org/2024/700)
* [Download](https://eprint.iacr.org/2024/700.pdf)

### Abstract

Multiple works have designed or used maliciously secure honest majority MPC protocols over $\mathbb{Z}_{2^k}$ using replicated secret sharing (e.g. Koti et al. USENIX’21, and the references therein). A recent trend in the design of such MPC protocols is to first execute a semi-honest protocol, and then use a check that verifies the correctness of the computation requiring only sublinear amount of communication in terms of the circuit size. The so-called Galois ring extensions are needed in order to execute such checks over $\mathbb{Z}_{2^k}$, but these rings incur incredibly high computation overheads, which completely undermine any potential benefits the ring $\mathbb{Z}_{2^k}$ had to begin with.
In this work we revisit the task of designing sublinear distributed product checks on replicated secret-shared data over $\mathbb{Z}_{2^k}$ among three parties with an honest majority. We present a novel technique for verifying the correctness of a set of multiplication (in fact, inner product) triples, involving a sublinear cost in terms of the amount of multiplications. Most importantly, unlike previous works, our tools entirely avoid Galois ring extensions, and only require computation over rings of the form $\mathbb{Z}_{2^l}$ . In terms of communication, our checks are 3∼5× lighter than existing checks using ring extensions, which is already quite remarkable. However, our most noticeable improvement is in terms of computation: avoiding extensions allows our checks to be 17.7∼44.2× better than previous approaches, for many parameter regimes of interest. Our experimental results show that checking a 10 million gate circuit with the 3PC protocol from (Boyle et al., CCS’19) takes about two minutes, while our approach takes only 2.82 seconds.
Finally, our techniques are not restricted to the three-party case, and we generalize them to replicated secret-sharing with an arbitrary number of parties n. Even though the share size in this scheme grows exponentially with n, prior works have used it for n = 4 or n = 5—or even general n for feasibility results—and our distributed checks also represent improvements in these contexts.

## 2024/701

* Title: Quantum Unpredictability
* Authors: Tomoyuki Morimae, Shogo Yamada, Takashi Yamakawa
* [Permalink](https://eprint.iacr.org/2024/701)
* [Download](https://eprint.iacr.org/2024/701.pdf)

### Abstract

Unpredictable functions (UPFs) play essential roles in classical cryptography, including message authentication codes (MACs) and digital signatures. In this paper, we introduce a quantum analog of UPFs, which we call unpredictable state generators (UPSGs). UPSGs are implied by pseudorandom function-like states generators (PRFSs), which are a quantum analog of pseudorandom functions (PRFs), and therefore UPSGs could exist even if one-way functions do not exist, similar to other recently introduced primitives like pseudorandom state generators (PRSGs), one-way state generators (OWSGs), and EFIs. In classical cryptography, UPFs are equivalent to PRFs, but in the quantum case, the equivalence is not clear, and UPSGs could be weaker than PRFSs. Despite this, we demonstrate that all known applications of PRFSs are also achievable with UPSGs. They include IND-CPA-secure secret-key encryption and EUF-CMA-secure MACs with unclonable tags. Our findings suggest that, for many applications, quantum unpredictability, rather than quantum pseudorandomness, is sufficient.

## 2024/702

* Title: Security Analysis of Signal's PQXDH Handshake
* Authors: Rune Fiedler, Felix Günther
* [Permalink](https://eprint.iacr.org/2024/702)
* [Download](https://eprint.iacr.org/2024/702.pdf)

### Abstract

Signal recently deployed a new handshake protocol named PQXDH to protect against "harvest-now-decrypt-later" attacks of a future quantum computer. To this end, PQXDH adds a post-quantum KEM to the Diffie-Hellman combinations of the prior X3DH handshake.

In this work, we give a reductionist security analysis of Signal's PQXDH handshake in a game-based security model that captures the targeted "maximum-exposure" security, allowing fine-grained compromise of user's long-term, semi-static, and ephemeral key material. We augment prior such models to capture not only the added KEM component but also the signing of public keys, which prior analyses did not capture but which adds an additional flavor of post-quantum security in PQXDH. We then establish a fully parameterized, concrete security bound for the session key security of PQXDH, in particular shedding light on a KEM binding property we require for PQXDH's security, and how to avoid it.

Our discussion of KEM binding complements the tool-based analysis of PQXDH by Bhargavan, Jacomme, Kiefer, and Schmidt, which pointed out a potential re-encapsulation attack if the KEM shared secret does not bind the public key. We show that both Kyber (used in PQXDH) and its current NIST draft standard ML-KEM (foreseen to replace Kyber once standardized) satisfy a novel binding notion we introduce and rely on for our PQXDH analysis, which may be of independent interest.

## 2024/703

* Title: An Efficient and Extensible Zero-knowledge Proof Framework for Neural Networks
* Authors: Tao Lu, Haoyu Wang, Wenjie Qu, Zonghui Wang, Jinye He, Tianyang Tao, Wenzhi Chen, Jiaheng Zhang
* [Permalink](https://eprint.iacr.org/2024/703)
* [Download](https://eprint.iacr.org/2024/703.pdf)

### Abstract

In recent years, cloud vendors have started to supply paid services for data analysis by providing interfaces of their well-trained neural network models. However, customers lack tools to verify whether outcomes supplied by cloud vendors are correct inferences from particular models, in the face of lazy or malicious vendors. The cryptographic primitive called zero-knowledge proof (ZKP) addresses this problem. It enables the outcomes to be verifiable without leaking information about the models. Unfortunately, existing ZKP schemes for neural networks have high computational overheads, especially for the non-linear layers in neural networks.

In this paper, we propose an efficient and extensible ZKP framework for neural networks. Our work improves the performance of the proofs for non-linear layers. Compared to previous works relying on the technology of bit decomposition, we convert complex non-linear relations into range and exponent relations, which significantly reduces the number of constraints required to prove non-linear layers. Moreover, we adopt a modular design to make our framework compatible with more neural networks. Specifically, we propose two enhanced range and lookup proofs as basic blocks. They are efficient in proving the satisfaction of range and exponent relations. Then, we constrain the correct calculation of primitive non-linear operations using a small number of range and exponent relations. Finally, we build our ZKP framework from the primitive operations to the entire neural networks, offering the flexibility for expansion to various neural networks.

We implement our ZKPs for convolutional and transformer neural networks. The evaluation results show that our work achieves over $168.6\times$ (up to $477..2\times$) speedup for separated non-linear layers and $41.4\times$ speedup for the entire ResNet-101 convolutional neural network, when compared with the state-of-the-art work, Mystique. In addition, our work can prove GPT-2, a transformer neural network with $117$ million parameters, in $287.1$ seconds, achieving $35.7\times$ speedup over ZKML, which is a state-of-the-art work supporting transformer neural networks.

## 2024/704

* Title: Fully Automated Selfish Mining Analysis in Efficient Proof Systems Blockchains
* Authors: Krishnendu Chatterjee, Amirali Ebrahim-Zadeh, Mehrdad Karrabi, Krzysztof Pietrzak, Michelle Yeo, Djordje Zikelic
* [Permalink](https://eprint.iacr.org/2024/704)
* [Download](https://eprint.iacr.org/2024/704.pdf)

### Abstract

We study selfish mining attacks in longest-chain blockchains like Bitcoin, but where the proof of work is replaced with efficient proof systems -- like proofs of stake or proofs of space -- and consider the problem of computing an optimal selfish mining attack which maximizes expected relative revenue of the adversary, thus minimizing the chain quality. To this end, we propose a novel selfish mining attack that aims to maximize this objective and formally model the attack as a Markov decision process (MDP). We then present a formal analysis procedure which computes an $\epsilon$-tight lower bound on the optimal expected relative revenue in the MDP and a strategy that achieves this $\epsilon$-tight lower bound, where $\epsilon>0$ may be any specified precision. Our analysis is fully automated and provides formal guarantees on the correctness. We evaluate our selfish mining attack and observe that it achieves superior expected relative revenue compared to two considered baselines.

In concurrent work [Sarenche FC'24] does an automated analysis on selfish mining in predictable longest-chain blockchains based on efficient proof systems.. Predictable means the randomness for the challenges is fixed for many blocks (as used e.g., in Ouroboros), while
we consider unpredictable (Bitcoin-like) chains where the challenge is derived from the previous block.

## 2024/705

* Title: Large-Scale MPC: Scaling Private Iris Code Uniqueness Checks to Millions of Users
* Authors: Remco Bloemen, Daniel Kales, Philipp Sippl, Roman Walch
* [Permalink](https://eprint.iacr.org/2024/705)
* [Download](https://eprint.iacr.org/2024/705.pdf)

### Abstract

In this work we tackle privacy concerns in biometric verification systems that typically require server-side processing of sensitive data (e.g., fingerprints and Iris Codes). Concretely, we design a solution that allows us to query whether a given Iris Code is similar to one contained in a given database, while all queries and datasets are being protected using secure multiparty computation (MPC). Addressing the substantial performance demands of operational systems like World ID and aid distributions by the Red Cross, we propose new protocols to improve performance by more than three orders of magnitude compared to the recent state-of-the-art system Janus (S&P 24). Our final protocol can achieve a throughput of over a million Iris Code comparisons per second on a single CPU core, while protecting the privacy of both the query and database Iris Codes. We additionally investigate GPU acceleration for some building blocks of our protocol, which results in further speedups of over 38x compared to the respective multi-threaded CPU implementation.

## 2024/706

* Title: Linicrypt in the Ideal Cipher Model
* Authors: Zahra Javar, Bruce M. Kapron
* [Permalink](https://eprint.iacr.org/2024/706)
* [Download](https://eprint.iacr.org/2024/706.pdf)

### Abstract

We extend the Linicrypt framework for characterizing hash function security as proposed by McQuoid, Swope, and Rosulek (TCC 2018) to support constructions in the ideal cipher model.
In this setting, we give a characterization of collision- and second-preimage-resistance in terms of a linear-algebraic condition on Linicrypt programs, and present an efficient algorithm for determining whether a program satisfies the condition. As an application, we consider the case of the block cipherbased hash functions proposed by Preneel, Govaerts, and Vandewall (Crypto 1993), and show that the semantic analysis of PGV given by Black et. al. (J. Crypto. 2010) can be captured as a special case of our characterization. In addition, We model hash functions constructed through the Merkle-Damgård transformation within the Linicrypt framework. Finally, we appy this model to an analysis of how various attacks on the underlying compression functions can compromise the collision resistance of the resulting hash function.

## 2024/707

* Title: Towards a Polynomial Instruction Based Compiler for Fully Homomorphic Encryption Accelerators
* Authors: Sejun Kim, Wen Wang, Duhyeong Kim, Adish Vartak, Michael Steiner, Rosario Cammarota
* [Permalink](https://eprint.iacr.org/2024/707)
* [Download](https://eprint.iacr.org/2024/707.pdf)

### Abstract

Fully Homomorphic Encryption (FHE) is a transformative technology that enables computations on encrypted data without requiring decryption, promising enhanced data privacy. However, its adoption has been limited due to significant performance overheads. Recent advances include the proposal of domain-specific, highly-parallel hardware accelerators designed to overcome these limitations.
This paper introduces PICA, a comprehensive compiler framework designed to simplify the programming of these specialized FHE accelerators and integration with existing FHE libraries. PICA leverages a novel polynomial Instruction Set Architecture (p-ISA), which abstracts polynomial rings and their arithmetic operations, serving as a fundamental data type for the creation of compact, efficient code embracing high-level operations on polynomial rings, referred to as kernels, e.g., encompassing FHE primitives like arithmetic and ciphertext management. We detail a kernel generation framework that translates high-level FHE operations into pseudo-code using p-ISA, and a subsequent tracing framework that incorporates p-ISA functionalities and kernels into established FHE libraries. Additionally, we introduce a mapper to coordinate multiple FHE kernels for optimal application performance on targeted hardware accelerators. Our evaluations demonstrate PICA's efficacy in creation of compact and efficient code, when compared with an x64 architecture. Particularly in managing complex FHE operations such as relinearization, where we observe a 25.24x instruction count reduction even when a large batch size (8192) is taken into account.

## 2024/708

* Title: Automated Generation of Fault-Resistant Circuits
* Authors: Nicolai Müller, Amir Moradi
* [Permalink](https://eprint.iacr.org/2024/708)
* [Download](https://eprint.iacr.org/2024/708.pdf)

### Abstract

Fault Injection (FI) attacks, which involve intentionally introducing faults into a system to cause it to behave in an unintended manner, are widely recognized and pose a significant threat to the security of cryptographic primitives implemented in hardware, making fault tolerance an increasingly critical concern. However, protecting cryptographic hardware primitives securely and efficiently, even with well-established and documented methods such as redundant computation, can be a time-consuming, error-prone, and expertise-demanding task.
In this research, we present a comprehensive and fully-automated software solution for the Automated Generation of Fault-Resistant Circuits (AGEFA). Our application employs a generic and extensively researched methodology for the secure integration of countermeasures based on Error-Correcting Codes (ECCs) into cryptographic hardware circuits. Our software tool allows designers without hardware security expertise to develop fault-tolerant hardware circuits with pre-defined correction capabilities under a comprehensive fault adversary model. Moreover, our tool applies to masked designs without violating the masking security requirements, in particular to designs generated by the tool AGEMA. We evaluate the effectiveness of our approach through experiments on various block ciphers and demonstrate its ability to produce fault-tolerant circuits. Additionally, we assess the security of examples generated by AGEFA against Side-Channel Analysis (SCA) and FI using state-of-the-art leakage and fault evaluation tools.

## 2024/709

* Title: Masked Computation the Floor Function and its Application to the FALCON Signature
* Authors: Justine Paillet, Pierre-Augustin Berthet, Cédric Tavernier
* [Permalink](https://eprint.iacr.org/2024/709)
* [Download](https://eprint.iacr.org/2024/709.pdf)

### Abstract

FALCON is candidate for standardization of the new Post Quantum Cryptography (PQC) primitives by the National Institute of Standards and Technology (NIST).. However, it remains a challenge to define efficient countermeasures against side-channel attacks (SCA) for this algorithm. FALCON is a lattice-based signature that relies on rational numbers which is unusual in the cryptography field. While recent work proposed a solution to mask the addition and the multiplication, some roadblocks remain, most noticeably how to protect the floor function. We propose in this work to complete the existing first trials of hardening FALCON against SCA. We perform the mathematical proofs of our methods as well as formal security proof in the probing model using the Non-Interference concepts.

## 2024/710

* Title: BUFFing FALCON without Increasing the Signature Size
* Authors: Samed Düzlü, Rune Fiedler, Marc Fischlin
* [Permalink](https://eprint.iacr.org/2024/710)
* [Download](https://eprint.iacr.org/2024/710.pdf)

### Abstract

This work shows how FALCON can achieve the Beyond UnForgeability Features (BUFF) introduced by Cremers et al. (S&P'21) more efficiently than by applying the generic BUFF transform. Specifically, we show that applying a transform of Pornin and Stern (ACNS'05), dubbed PS-3 transform, already suffices for FALCON to achieve BUFF security. For FALCON, this merely means to include the public key in the hashing step in signature generation and verification, instead of hashing only the nonce and the message; the other signature computation steps and the signature output remain untouched. In comparison to the BUFF transform, which appends a hash value to the final signature, the PS-3 transform therefore achieves shorter signature sizes, without incurring additional computations.

## 2024/711

* Title: Non-Transferable Anonymous Tokens by Secret Binding
* Authors: F. Betül Durak, Laurane Marco, Abdullah Talayhan, Serge Vaudenay
* [Permalink](https://eprint.iacr.org/2024/711)
* [Download](https://eprint.iacr.org/2024/711.pdf)

### Abstract

Non-transferability (NT) is a security notion which ensures that credentials are only used by their intended owners. Despite its importance, it has not been formally treated in the context of anonymous tokens (AT) which are lightweight anonymous credentials. In this work, we consider a client who "buys" access tokens which are forbidden to be transferred although anonymously redeemed. We extensively study the trade-offs between privacy (obtained through anonymity) and security in AT through the notion of non-transferability. We formalise new security notions, design a suite of protocols with various flavors of NT, prove their security, and implement the protocols to assess their efficiency. Finally, we study the existing anonymous credentials which offer NT, and show that they cannot automatically be used as AT without security and complexity implications.

## 2024/712

* Title: Quantum NV Sieve on Grover for Solving Shortest Vector Problem
* Authors: Hyunji Kim, Kyungbae Jang, Hyunjun Kim, Anubhab Baksi, Sumanta Chakraborty, Hwajeong Seo
* [Permalink](https://eprint.iacr.org/2024/712)
* [Download](https://eprint.iacr.org/2024/712.pdf)

### Abstract

Quantum computers can efficiently model and solve several challenging problems for classical computers, raising concerns about potential security reductions in cryptography. NIST is already considering potential quantum attacks in the development of post-quantum cryptography by estimating the quantum resources required for such quantum attacks. In this paper, we present quantum circuits for the NV sieve algorithm to solve the Shortest Vector Problem (SVP), which serves as the security foundation for lattice-based cryptography, achieving a quantum speedup of the square root. Although there has been extensive research on the application of quantum algorithms for lattice-based problems at the theoretical level, specific quantum circuit implementations for them have not been presented yet.

Notably, this work demonstrates that the required quantum complexity for the SVP in the lattice of rank 70 and dimension 70 is $2^{43}$ (a product of the total gate count and the total depth) with our optimized quantum implementation of the NV sieve algorithm.

This complexity is significantly lower than the NIST post-quantum security standard, where level 1 is $2^{157}$, corresponding to the complexity of Grover's key search for AES-128.

## 2024/713

* Title: Analyzing Pump and jump BKZ algorithm using dynamical systems
* Authors: Leizhang Wang
* [Permalink](https://eprint.iacr.org/2024/713)
* [Download](https://eprint.iacr.org/2024/713.pdf)

### Abstract

The analysis of the reduction effort of the lattice reduction algorithm is important in estimating the hardness of lattice-based cryptography schemes. Recently many lattice challenge records have been cracked by using the Pnj-BKZ algorithm which is the default lattice reduction algorithm used in G6K, such as the TU Darmstadt LWE and SVP Challenges. However, the previous estimations of the Pnj-BKZ algorithm are simulator algorithms rather than theoretical upper bound analyses. In this work, we present the first dynamic analysis of Pnj-BKZ algorithm. More precisely, our analysis results show that let $L$ is the lattice spanned by $(\mathbf{a}_i)_{i\leq d}$. The shortest vector $\mathbf{b}_1$ output by running $\Omega \left ( \frac{2Jd^2}{\beta(\beta-J)}\left ( \ln_{}{d} +\ln_{} \ln_{}{\max_{i}\frac{\left \| \mathbf{a}_i^{*} \right \| }{(\mathrm{det}L )^{1/d} } } \right ) \right ) $ tours reduction of pnj-BKZ$(\beta,J)$, $\mathbf{b}_1$ satisfied that \memo{$\left \| \mathbf{b}_1 \right \| \le {\gamma}_{\beta}^{\frac{d-1}{2(\beta-J)}+2 } \cdot \left ( \mathrm{det}L \right ) ^{\frac{1}{d} } $}.

## 2024/714

* Title: Learning with Quantization, Polar Quantizer, and Secure Source Coding
* Authors: Shanxiang Lyu, Ling Liu, Cong Ling
* [Permalink](https://eprint.iacr.org/2024/714)
* [Download](https://eprint.iacr.org/2024/714.pdf)

### Abstract

This paper presents a generalization of the Learning With Rounding (LWR) problem, initially introduced by Banerjee, Peikert, and Rosen, by applying the perspective of vector quantization. In LWR, noise is induced by rounding each coordinate to the nearest multiple of a fraction, a process inherently tied to scalar quantization. By considering a new variant termed Learning With Quantization (LWQ), we explore large-dimensional fast-decodable lattices with superior quantization properties, aiming to enhance the compression performance over conventional scalar quantization. We identify polar lattices as exemplary structures, effectively transforming LWQ into a problem akin to Learning With Errors (LWE), where the distribution of quantization noise is statistically close to discrete Gaussian. Furthermore, we develop a novel ``quancryption'' scheme for secure source coding. Notably, the scheme achieves near-optimal rate-distortion ratios for bounded rational signal sources, and can be implemented efficiently with quasi-linear time complexity. Python code of the polar-lattice quantizer is available at https://github.com/shx-lyu/PolarQuantizer.

## 2024/715

* Title: A New Cryptographic Algorithm
* Authors: Ali Mahdoum
* [Permalink](https://eprint.iacr.org/2024/715)
* [Download](https://eprint.iacr.org/2024/715.pdf)

### Abstract

The advent of quantum computing technology will compromise many of the current cryptographic algorithms, especially public-key cryptography, which is widely used to protect digital information. Most algorithms on which we depend are used worldwide in components of many different communications, processing, and storage systems. Once access to practical quantum computers becomes available, all public-key algorithms and associated protocols will be vulnerable to criminals, competitors, and other adversaries. It is critical to begin planning for the replacement of hardware, software, and services that use public-key algorithms now so that information is protected from future attacks.” [1].
For this purpose, we have developed a new algorithm that contributes to deal with the aforementioned problem. Instead to use a classical scheme of encoding / decoding methods (keys, prime numbers, etc.), our algorithm is rather based on a combination of functions. Because the cardinality of the set of functions is infinite, it would be impossible for a third party (e.g. a hacker) to decode the secret information transmitted by the sender (Bob) to the receiver (Alice).

## 2024/716

* Title: Unclonable Secret Sharing
* Authors: Prabhanjan Ananth, Vipul Goyal, Jiahui Liu, Qipeng Liu
* [Permalink](https://eprint.iacr.org/2024/716)
* [Download](https://eprint.iacr.org/2024/716.pdf)

### Abstract

Unclonable cryptography utilizes the principles of quantum mechanics to addresses cryptographic tasks that are impossible classically. We introduce a novel unclonable primitive in the context of secret sharing, called unclonable secret sharing (USS). In a USS scheme, there are $n$ shareholders, each holding a share of a classical secret represented as a quantum state. They can recover the secret once all parties (or at least $t$ parties) come together with their shares. Importantly, it should be infeasible to copy their own shares and send the copies to two non-communicating parties, enabling both of them to recover the secret.

Our work initiates a formal investigation into the realm of unclonable secret sharing, shedding light on its implications, constructions, and inherent limitations.
** Connections: We explore the connections between USS and other quantum cryptographic primitives such as unclonable encryption and position verification, showing the difficulties to achieve USS in different scenarios.

**Limited Entanglement: In the case where the adversarial shareholders do not share any entanglement or limited entanglement, we demonstrate information-theoretic constructions for USS.

**Large Entanglement: If we allow the adversarial shareholders to have unbounded entanglement resources (and unbounded computation), we prove that unclonable secret sharing is impossible. On the other hand, in the quantum random oracle model where the adversary can only make a bounded polynomial number of queries, we show a construction secure even with unbounded entanglement..

Furthermore, even when these adversaries possess only a polynomial amount of entanglement resources, we establish that any unclonable secret sharing scheme with a reconstruction function implementable using Cliffords and logarithmically many T-gates is also unattainable.

## 2024/717

* Title: An Improved Threshold Homomorphic Cryptosystem Based on Class Groups
* Authors: Lennart Braun, Guilhem Castagnos, Ivan Damgård, Fabien Laguillaumie, Kelsey Melissaris, Claudio Orlandi, Ida Tucker
* [Permalink](https://eprint.iacr.org/2024/717)
* [Download](https://eprint.iacr.org/2024/717.pdf)

### Abstract

We present distributed key generation and decryption protocols for an additively homomorphic cryptosystem based on class groups, improving on a similar system proposed by Braun, Damgård, and Orlandi at CRYPTO '23. Our key generation is similarly constant round but achieves lower communication complexity than the previous work. This improvement is in part the result of relaxing the reconstruction property required of the underlying integer verifiable secret sharing scheme. This eliminates the reliance on potentially costly proofs of knowledge in unknown order groups. We present a new method to batch zero-knowledge proofs in unknown order groups which strengthens these improvements.. We also present a protocol which is proven secure against adaptive adversaries in the single inconsistent player (SIP) model. Our protocols are secure in the universal composability (UC) framework and provide guaranteed output delivery. We demonstrate the relative efficiency of our techniques by presenting the running times and communication costs associated with our implementation of the statically secure protocol and provide a direct comparison with alternate state of the art constructions.

## 2024/718

* Title: PAC-Private Algorithms
* Authors: Mayuri Sridhar, Hanshen Xiao, Srinivas Devadas
* [Permalink](https://eprint.iacr.org/2024/718)
* [Download](https://eprint.iacr.org/2024/718.pdf)

### Abstract

Provable privacy typically requires involved analysis and is often associated with unacceptable accuracy loss. While many empirical verification or approximation methods, such as Membership Inference Attacks (MIA) and Differential Privacy Auditing (DPA), have been proposed, these do not offer rigorous privacy guarantees. In this paper, we apply recently-proposed Probably Approximately Correct (PAC) Privacy to give formal, mechanized, simulation-based proofs for a range of practical, black-box algorithms: K-Means, Support Vector Machines (SVM), Principal Component Analysis (PCA) and Random Forests. To provide these proofs, we present a new simulation algorithm that efficiently determines anisotropic noise perturbation required for any given level of privacy. We provide a proof of correctness for this algorithm and demonstrate that anisotropic noise has substantive benefits over isotropic noise.

Stable algorithms are easier to privatize, and we demonstrate privacy amplification resulting from introducing regularization in these algorithms; meaningful privacy guarantees are obtained with small losses in accuracy. We also propose new techniques in order to canonicalize algorithmic output and convert intractable geometric stability verification into efficient deterministic stability verification. Thorough experiments are included, and we validate our provable adversarial inference hardness against state-of-the-art empirical attacks.

## 2024/719

* Title: Client-Efficient Online-Offline Private Information Retrieval
* Authors: Hoang-Dung Nguyen, Jorge Guajardo, Thang Hoang
* [Permalink](https://eprint.iacr.org/2024/719)
* [Download](https://eprint.iacr.org/2024/719.pdf)

### Abstract

Private Information Retrieval (PIR) permits clients to query entries from a public database hosted on untrusted servers in a privacy-preserving manner. Traditional PIR model suffers from high computation and/or bandwidth cost due to entire database processing for privacy. Recently, Online-Offline PIR (OO-PIR) has been suggested to improve the practicality of PIR, where query-independent materials are precomputed beforehand to accelerate online access. While state-of-the-art OO-PIR schemes (e.g., S&P’24, CRYPTO’23) successfully reduce the online processing overhead to sublinear, they still impose sustainable bandwidth and storage burdens on the client, especially when operating on large databases.
In this paper, we propose Pirex, a new OO-PIR scheme with eminent client performance while maintaining the sublinear server processing efficiency. Specifically, Pirex offers clients with sublinear processing, minimal inbound bandwidth, and low storage requirements. Our Pirex design is fairly simple yet efficient, where the majority of operations are naturally low-cost and streamlined (e.g., XOR, PRF, modular arithmetic).
We have fully implemented Pirex and evaluated its real-world performance using commodity hardware. Our experimental results demonstrated that Pirex outperforms existing OO-PIR schemes by at least two orders of magnitude. Concretely, with a 1 TB database, Pirex only takes 0.8s to query a 256-KB entry, compared with 30-220s by the state-of-the-art.

## 2024/720

* Title: MQ maps are not binding - Revisiting Multivariate Blind Signatures
* Authors: Ward Beullens
* [Permalink](https://eprint.iacr.org/2024/720)
* [Download](https://eprint.iacr.org/2024/720.pdf)

### Abstract

In 2017, Petzoldt, Szepieniec, and Mohamed proposed a blind signature scheme, based on multivariate cryptography. This construction has been expanded on by several other works. This short paper shows that their construction is susceptible to an efficient polynomial-time attack. The problem is that the authors implicitly assumed that for a random multivariate quadratic map $\mathcal{R}:\mathbb{F}_q^m \rightarrow \mathbb{F}_q^m$ and a collision-resistant hash function $H: \{0,1\}^* \rightarrow \mathbb{F}_q^m$, the function $\mathsf{Com}(m;\mathbf{r}) := H(m) - \mathcal{R}(\mathbf{r})$ is a binding commitment. This paper shows that this is not the case. Given any pair of messages, one can efficiently produce a commitment that opens to both of them. We hope that by pointing out that multivariate quadratic maps are not binding, similar problems can be avoided in the future.

## 2024/721

* Title: Real-world Universal zkSNARKs are non-malleable
* Authors: Antonio Faonio, Dario Fiore, Luigi Russo
* [Permalink](https://eprint.iacr.org/2024/721)
* [Download](https://eprint.iacr.org/2024/721.pdf)

### Abstract

Simulation extractability is a strong security notion of zkSNARKs that guarantees that an attacker who produces a valid proof must know the corresponding witness, even if the attacker had prior access to proofs generated by other users. Notably, simulation extractability implies that proofs are non-malleable and is of fundamental importance for applications of zkSNARKs in distributed systems. In this work, we study sufficient and necessary conditions for constructing simulation-extractable universal zkSNARKs via the popular design approach based on compiling polynomial interactive oracle proofs (PIOP). Our main result is the first security proof that popular universal zkSNARKs, such as PLONK and Marlin, as deployed in the real world, are simulation-extractable.. Our result fills a gap left from previous work (Faonio et al. TCC’23, and Kohlweiss et al. TCC’23) which could only prove the simulation extractability of the “textbook” versions of these schemes and does not capture their optimized variants, with all the popular optimization tricks in place, that are eventually implemented and deployed in software libraries.

## 2024/722

* Title: Ultrametric integral cryptanalysis
* Authors: Tim Beyne, Michiel Verbauwhede
* [Permalink](https://eprint.iacr.org/2024/722)
* [Download](https://eprint.iacr.org/2024/722.pdf)

### Abstract

A systematic method to analyze \emph{divisibility properties} is proposed.
In integral cryptanalysis, divisibility properties interpolate between bits that sum to zero (divisibility by two) and saturated bits (divisibility by $2^{n - 1}$ for $2^n$ inputs).
From a theoretical point of view, we construct a new cryptanalytic technique that is a non-Archimedean multiplicative analogue of linear cryptanalysis. It lifts integral cryptanalysis to characteristic zero in the sense that, if all quantities are reduced modulo two, then one recovers the algebraic theory of integral cryptanalysis.
The new technique leads to a theory of trails. We develop a tool based on off-the-shelf solvers that automates the analysis of these trails and use it to show that many integral distinguishers on PRESENT and SIMON are stronger than expected.

## 2024/723

* Title: $\mathsf{OPA}$: One-shot Private Aggregation with Single Client Interaction and its Applications to Federated Learning
* Authors: Harish Karthikeyan, Antigoni Polychroniadou
* [Permalink](https://eprint.iacr.org/2024/723)
* [Download](https://eprint.iacr.org/2024/723.pdf)

### Abstract

Our work aims to minimize interaction in secure computation due to the high cost and challenges associated with communication rounds, particularly in scenarios with many clients. In this work, we revisit the problem of secure aggregation in the single-server setting where a single evaluation server can securely aggregate client-held individual inputs. Our key contribution is One-shot Private Aggregation ($\mathsf{OPA}$) where clients speak only once (or even choose not to speak) per aggregation evaluation. Since every client communicates just once per aggregation, this streamlines the management of dropouts and dynamic participation of clients, contrasting with multi-round state-of-the-art protocols for each aggregation.

We initiate the study of $\mathsf{OPA}$ in several ways. First, we formalize the model and present a security definition. Second, we construct $\mathsf{OPA}$ protocols based on class groups, DCR, and LWR assumptions. Third, we demonstrate $\mathsf{OPA}$ with two applications: private stream aggregation and privacy-preserving federated learning. Specifically, $\mathsf{OPA}$ can be used as a key building block to enable privacy-preserving federated learning and critically, where client speaks once. This is a sharp departure from prior multi-round protocols whose study was initiated by Bonawitz et al. (CCS, 2017). Moreover, unlike the YOSO (You Only Speak Once) model for general secure computation, $\mathsf{OPA}$ eliminates complex committee selection protocols to achieve adaptive security. Beyond asymptotic improvements, $\mathsf{OPA}$ is practical, outperforming state-of-the-art solutions. We leverage $\mathsf{OPA}$ to develop a streaming variant named $\mathsf{SOPA}$, serving as the building block for privacy-preserving federated learning. We utilize $\mathsf{SOPA}$ to construct logistic regression classifiers for two datasets.

A new distributed key homomorphic PRF is at the core of our construction of $\mathsf{OPA}$. This key component addresses shortcomings observed in previous works that relied on DDH and LWR in the work of Boneh et al. (CRYPTO, 2013), marking it as an independent contribution to our work. Moreover, we also present new distributed key homomorphic PRFs based on class groups or DCR or the LWR assumption.