## In this issue

1. [2024/556] Menhir: An Oblivious Database with Protection ...
2. [2024/557] Permutation-Based Hash Chains with Application to ...
3. [2024/769] Time-Based Cryptography From Weaker Assumptions: ...
4. [2024/776] Instance-Hiding Interactive Proofs
5. [2024/777] Measure-Rewind-Extract: Tighter Proofs of One-Way ...
6. [2024/778] Ideal-to-isogeny algorithm using 2-dimensional ...
7. [2024/779] Elliptic Curve Cryptography for the masses: Simple ...
8. [2024/780] Information-theoretic Multi-server Private ...
9. [2024/781] Doubly-Efficient Batch Verification in Statistical ...
10. [2024/782] Relating Code Equivalence to Other Isomorphism Problems
11. [2024/783] Differential Cryptanalysis on Quantum Computers
12. [2024/784] Universal Blockchain Assets
13. [2024/785] SmartBean: Transparent, Concretely Efficient, ...
14. [2024/786] Modelling Ciphers with Overdefined Systems of ...
15. [2024/787] A new attack against search-LWE using Diophantine ...
16. [2024/788] A Fault-Resistant NTT by Polynomial Evaluation and ...
17. [2024/789] FairSec: Fair and Maliciously Secure Circuit-PSI ...
18. [2024/790] Physical Ring Signature
19. [2024/791] Minimize the Randomness in Rasta-Like Designs: How ...
20. [2024/792] Stickel's Key Agreement Algebraic Variation
21. [2024/793] Hide-and-Seek and the Non-Resignability of the BUFF ...
22. [2024/794] Detecting Rogue Decryption in (Threshold) ...
23. [2024/795] New Limits of Provable Security and Applications to ...
24. [2024/796] Weak Consistency mode in Key Transparency: OPTIKS
25. [2024/797] Nonadaptive One-Way to Hiding Implies Adaptive ...
26. [2024/798] Incompressible Functional Encryption
27. [2024/799] Symmetric Signcryption and E2EE Group Messaging in ...
28. [2024/800] A Note on Zero-Knowledge for NP and One-Way Functions
29. [2024/801] Algebraic Structure of the Iterates of $\chi$
30. [2024/802] On Maximum Size Simultaneous Linear Approximations ...
31. [2024/803] Can We Beat Three Halves Lower Bound?: ...
32. [2024/804] Analysis on Sliced Garbling via Algebraic Approach
33. [2024/805] DiTRU: A Resurrection of NTRU over Dihedral Group
34. [2024/806] Resettable Statistical Zero-Knowledge for NP
35. [2024/807] Optimal Consensus in the Presence of Overlapping ...
36. [2024/808] Arma: Byzantine Fault Tolerant Consensus with ...
37. [2024/809] Reducing Overdefined Systems of Polynomial ...
38. [2024/810] The Perils of Limited Key Reuse: Adaptive and ...
39. [2024/811] Traceable Secret Sharing Based on the Chinese ...
40. [2024/812] Relations among new CCA security notions for ...
41. [2024/813] How to Redact the Bitcoin Backbone Protocol
42. [2024/814] Succinct Homomorphic Secret Sharing
43. [2024/815] Faster verifications and smaller signatures: Trade- ...
44. [2024/816] Zero-knowledge IOPs Approaching Witness Length
45. [2024/817] DVA: Dangerous Variations of ALTEQ
46. [2024/818] The Brave New World of Global Generic Groups and ...
47. [2024/819] A new stand-alone MAC construct called SMAC
48. [2024/820] Rate-1 Arithmetic Garbling from Homomorphic Secret- ...
49. [2024/821] A General Framework for Lattice-Based ABE Using ...
50. [2024/822] Early Stopping Byzantine Agreement in ...
51. [2024/823] Batched Distributed Point Function from Sparse LPN ...
52. [2024/824] Improved Meet-LWE Attack via Ternary Trees

## 2024/556

* Title: Menhir: An Oblivious Database with Protection against Access and Volume Pattern Leakage
* Authors: Leonie Reichert, Gowri R Chandran, Phillipp Schoppmann, Thomas Schneider, Björn Scheuermann
* [Permalink](https://eprint.iacr.org/2024/556)
* [Download](https://eprint.iacr.org/2024/556.pdf)

### Abstract

Analyzing user data while protecting the privacy of individuals remains a big challenge. Trusted execution environments (TEEs) are a possible solution as they protect processes and Virtual Machines (VMs) against malicious hosts. However, TEEs can leak access patterns to code and to the data being processed. Furthermore, when data is stored in a TEE database, the data volume required to answer a query is another unwanted side channel that contains sensitive information. Both types of information leaks, access patterns and volume patterns, allow for database reconstruction attacks.

In this paper, we present Menhir, an oblivious TEE database that hides access patterns with ORAM guarantees and volume patterns through differential privacy. The database allows range and point queries with SQL-like WHERE-clauses. It builds on the state-of-the-art oblivious AVL tree construction Oblix (S&P'18), which by itself does not protect against volume leakage. We show how volume leakage can be exploited in range queries and improve the construction to mitigate this type of attack. We prove the correctness and obliviousness of Menhir. Our evaluation shows that our approach is feasible and scales well with the number of rows and columns in the database.

## 2024/557

* Title: Permutation-Based Hash Chains with Application to Password Hashing
* Authors: Charlotte Lefevre, Bart Mennink
* [Permalink](https://eprint.iacr.org/2024/557)
* [Download](https://eprint.iacr.org/2024/557.pdf)

### Abstract

Hash chain based password systems are a useful way to guarantee authentication with one-time passwords. The core idea is specified in RFC 1760 as S/Key. At CCS 2017, Kogan et al. introduced T/Key, an improved password system where one-time passwords are only valid for a limited time period. They proved security of their construction in the random oracle model under a basic modeling of the adversary. In this work, we make various advances in the analysis and instantiation of hash chain based password systems. Firstly, we describe a slight generalization called U/Key that allows for more flexibility in the instantiation and analysis, and we develop a security model that refines the adversarial strength into offline and online complexity, that can be used beyond the random oracle model, and that allows to argue multi-user security directly. Secondly, we derive a new security proof of U/Key in the random oracle model, as well as dedicated and tighter security proofs of U/Key instantiated with a sponge construction and a truncated permutation. These dedicated security proofs, in turn, solve a problem of understanding the preimage resistance of a cascaded evaluation of the sponge construction. When applied to T/Key, these results improve significantly over the earlier results: whereas the originally suggested instantiation using SHA-256 uses a compression function that maps 768 bits into 256 bits, with a truncated permutation construction one can generically achieve 128 bits of security already with a permutation of size 256 bits.

## 2024/769

* Title: Time-Based Cryptography From Weaker Assumptions: Randomness Beacons, Delay Functions and More
* Authors: Damiano Abram, Lawrence Roy, Mark Simkin
* [Permalink](https://eprint.iacr.org/2024/769)
* [Download](https://eprint.iacr.org/2024/769.pdf)

### Abstract

The assumption that certain computations inherently require some sequential time has established itself as a powerful tool for cryptography. It allows for security and liveness guarantees in distributed protocols that are impossible to achieve with classical hardness assumptions. Unfortunately, many constructions from the realm of time-based cryptography are based on new and poorly understood hardness assumptions, which tend not to stand the test of time (cf.. Leurent et al. 2023, Peikert & Tang 2023).
In this work, we make progress on several fronts. We formally define the concept of a delay function and present a construction thereof from minimal assumptions. We show that these functions, in combination with classical cryptographic objects that satisfy certain efficiency criteria, would allow for constructing delay encryption, which is otherwise only known to exist based on a new hardness assumption about isogenies. We formally define randomness beacons as they are used in the context of blockchains, and we show that (linearly homomorphic) time-lock puzzles allow for efficiently constructing them.
Our work puts time-based cryptography on a firmer theoretical footing, provides new constructions from simpler assumptions, and opens new avenues for constructing delay encryption.

## 2024/776

* Title: Instance-Hiding Interactive Proofs
* Authors: Changrui Mu, Prashant Nalini Vasudevan
* [Permalink](https://eprint.iacr.org/2024/776)
* [Download](https://eprint.iacr.org/2024/776.pdf)

### Abstract

In an Instance-Hiding Interactive Proof (IHIP) [Beaver et al. CRYPTO 90], an efficient verifier with a _private_ input x interacts with an unbounded prover to determine whether x is contained in a language L. In addition to completeness and soundness, the instance-hiding property requires that the prover should not learn anything about x in the course of the interaction. Such proof systems capture natural privacy properties, and may be seen as a generalization of the influential concept of Randomized Encodings [Ishai et al. FOCS 00, Applebaum et al. FOCS 04, Agrawal et al. ICALP 15], and as a counterpart to Zero-Knowledge proofs [Goldwasser et al. STOC 89].

We investigate the properties and power of such instance-hiding proofs, and show the following:
1. Any language with an IHIP is contained in AM/poly and coAM/poly.
2. If an average-case hard language has an IHIP, then One-Way Functions exist.
3. There is an oracle with respect to which there is a language that has an IHIP but not an SZK proof.
4. IHIP's are closed under composition with any efficiently computable function.

We further study a stronger version of IHIP (that we call Strong IHIP) where the view of the honest prover can be efficiently simulated. For these, we obtain stronger versions of some of the above:
5. Any language with a Strong IHIP is contained in AM and coAM.
6. If a _worst-case_ hard language has a Strong IHIP, then One-Way Functions exist.

## 2024/777

* Title: Measure-Rewind-Extract: Tighter Proofs of One-Way to Hiding and CCA Security in the Quantum Random Oracle Model
* Authors: Jiangxia Ge, Heming Liao, Rui Xue
* [Permalink](https://eprint.iacr.org/2024/777)
* [Download](https://eprint.iacr.org/2024/777.pdf)

### Abstract

The One-Way to Hiding (O2H) theorem, first given by Unruh (J ACM 2015) and then restated by Ambainis et al. (CRYPTO 2019), is a crucial technique for solving the reprogramming problem in the quantum random oracle model (QROM). It provides an upper bound $d\cdot\sqrt{\epsilon}$ for the distinguisher's advantage, where $d$ is the query depth and $\epsilon$ denotes the advantage of a one-wayness attacker. Later, in order to obtain a tighter upper bound, Kuchta et al. (EUROCRYPT 2020) proposed the Measure-Rewind-Measure (MRM) technique and then proved the Measure-Rewind-Measure O2H (MRM-O2H) theorem, which provides the upper bound $d\cdot\epsilon$. They also proposed an open question: Can we combine their MRM technique with Ambainis et al.'s semi-classical oracle technique (CRYPTO 2019) or Zhandry's compressed oracle technique (CRYPTO 2019) to prove a new O2H theorem with an upper bound even tighter than $d\cdot\epsilon$?

In this paper, we give an affirmative answer for the above question. We propose a new technique named Measure-Rewind-Extract (MRE) by combining the MRM technique with the semi-classical oracle technique. By using MRE technique, we prove the Measure-Rewind-Extract O2H (MRE-O2H) theorem, which provides the upper bound $\sqrt{d}\cdot\epsilon$.

As an important application of our MRE-O2H theorem, for the $FO^{\cancel{\bot}}$, $FO_m^{\cancel{\bot}}$, $FO^{\bot}$ and $FO_m^\bot$ proposed by Hofheinz et al. (TCC 2017), i.e., the key encapsulation mechanism (KEM) variants of the Fujisaki-Okamoto transformation, we prove the following results in the QROM:

Their IND-CCA security can be reduced to the IND-CPA security of the underlying public key encryption (PKE) scheme without the square-root advantage loss. In particular, compared with the IND-CCA proof of $FO^{\cancel{\bot}}$ given by Kuchta et al. (EUROCRYPT 2020), ours removes the injectivity assumption and has a tighter security bound.

Under the assumption that the underlying PKE scheme is unique randomness recoverable, we for the first time prove that their IND-CCA security can be reduced to the OW-CPA security of the underlying PKE scheme without the square-root advantage loss.

## 2024/778

* Title: Ideal-to-isogeny algorithm using 2-dimensional isogenies and its application to SQIsign
* Authors: Hiroshi Onuki, Kohei Nakagawa
* [Permalink](https://eprint.iacr.org/2024/778)
* [Download](https://eprint.iacr.org/2024/778.pdf)

### Abstract

The Deuring correspondence is a correspondence between supersingular elliptic curves and quaternion orders. Under this correspondence, an isogeny between elliptic curves corresponds to a quaternion ideal. This correspondence plays an important role in isogeny-based cryptography and several algorithms to compute an isogeny corresponding to a quaternion ideal (ideal-to-isogeny algorithms) have been proposed. In particular, SQIsign is a signature scheme based on the Deuring correspondence and uses an ideal-to-isogeny algorithm. In this paper, we propose a novel ideal-to-isogeny algorithm using isogenies of dimension $2$. Our algorithm is based on Kani's reducibility theorem, which gives a connection between isogenies of dimension $1$ and $2$. By using the characteristic $p$ of the base field of the form $2^fg - 1$ for a small odd integer $g$, our algorithm works by only $2$-isogenies and $(2, 2)$-isogenies in the operations in $\mathbb{F}_{p^2}$. We apply our algorithm to SQIsign and compare the efficiency of the new algorithm with the existing one. Our analysis shows that the key generation and the signing in our algorithm are at least twice as fast as those in the existing algorithm at the NIST security level 1. This advantage becomes more significant at higher security levels. In addition, our algorithm also improves the efficiency of the verification in SQIsign.

## 2024/779

* Title: Elliptic Curve Cryptography for the masses: Simple and fast finite field arithmetic
* Authors: Michael Scott
* [Permalink](https://eprint.iacr.org/2024/779)
* [Download](https://eprint.iacr.org/2024/779.pdf)

### Abstract

Shaped prime moduli are often considered for use in elliptic curve and isogeny-based cryptography to allow for faster modular reduction. Here we focus on the most common choices for shaped primes that have been suggested, that is pseudo-Mersenne, generalized Mersenne and Montgomery-friendly primes. We consider how best to to exploit these shapes for maximum efficiency, and provide an open source tool to automatically generate, test and time working high-level language finite-field code. Next we consider the advantage to be gained from implementations that are written in assembly language and which exploit special instructions, SIMD hardware if present, and the particularities of the algorithm being implemented.

## 2024/780

* Title: Information-theoretic Multi-server Private Information Retrieval with Client Preprocessing
* Authors: Jaspal Singh, Yu Wei, Vassilis Zikas
* [Permalink](https://eprint.iacr.org/2024/780)
* [Download](https://eprint.iacr.org/2024/780.pdf)

### Abstract

A private information retrieval (PIR) protocol allows a client to fetch any entry from single or multiple servers who hold a public database (of size $n$) while ensuring no server learns any information about the client's query. Initial works on PIR were focused on reducing the communication complexity of PIR schemes. However, standard PIR protocols are often impractical to use in applications involving large databases, due to its inherent large server-side computation complexity, that's at least linear in the database size. Hence, a line of research has focused on considering alternative PIR models that can achieve improved server complexity.

The model of private information retrieval with client prepossessing has received a lot of interest beginning with the work due to Corrigan-Gibbs and Kogan (Eurocrypt 2020). In this model, the client interacts with two servers in an offline phase and it stores a local state, which it uses in the online phase to perform PIR queries. Constructions in this model achieve online client/server computation and bandwidth that's sublinear in the database size, at the cost of a one-time expensive offline phase. Till date all known constructions in this model are based on symmetric key primitives or on stronger public key assumptions like Decisional Diffie-Hellman (DDH) and Learning with Error (LWE). This work initiates the study of unconditional PIR with client prepossessing - where we avoid using any cryptographic assumptions. We present a new PIR protocol for $2t$ servers (where $t \in [2,\log_2n/2]$) with threshold 1, where client and server online computation is $\widetilde{O}(\sqrt{n})$ (the $\widetilde{O}(.)$ notation hides $\textsf{poly}\log$ factors) - matching the computation costs of other works based on cryptographic assumptions. The client storage and online communication complexity are $\widetilde{O}(n^{0.5+1/2t})$ and $\widetilde{O}(n^{1/2})$ respectively. Compared to previous works our PIR with client preprocessing protocol also has a very concretely efficient client/server online computation phase - which is dominated by xor operations, compared to cryptographic operations that are orders of magnitude slower. As a building block for our construction, we introduce a new information-theoretic primitive called \textit{privately multi-puncturable random set }(\pprs), which might be of independent interest. This new primitive can be viewed as as a generalization of privately puncturable pseudo-random set, which is the key cryptographic building block used in previous works on PIR with client preprocessing.

## 2024/781

* Title: Doubly-Efficient Batch Verification in Statistical Zero-Knowledge
* Authors: Or Keret, Ron D. Rothblum, Prashant Nalini Vasudevan
* [Permalink](https://eprint.iacr.org/2024/781)
* [Download](https://eprint.iacr.org/2024/781.pdf)

### Abstract

A sequence of recent works, concluding with Mu et al. (Eurocrypt, 2024) has shown that every problem $\Pi$ admitting a non-interactive statistical zero-knowledge proof (NISZK) has an efficient zero-knowledge batch verification protocol. Namely, an NISZK protocol for proving that $x_1,\dots,x_k \in \Pi$ with communication that only scales poly-logarithmically with $k$. A caveat of this line of work is that the prover runs in exponential-time, whereas for NP problems it is natural to hope to obtain a doubly-efficient proof - that is, a prover that runs in polynomial-time given the $k$ NP witnesses.

In this work we show that every problem in $NISZK \cap UP$ has a doubly-efficient interactive statistical zero-knowledge proof with communication $poly(n,\log(k))$ and $poly(\log(k),\log(n))$ rounds. The prover runs in time $poly(n,k)$ given access to the $k$ UP witnesses. Here $n$ denotes the length of each individual input, and UP is the subclass of NP relations in which YES instances have unique witnesses.

This result yields doubly-efficient statistical zero-knowledge batch verification protocols for a variety of concrete and central cryptographic problems from the literature.

## 2024/782

* Title: Relating Code Equivalence to Other Isomorphism Problems
* Authors: Huck Bennett, Kaung Myat Htay Win
* [Permalink](https://eprint.iacr.org/2024/782)
* [Download](https://eprint.iacr.org/2024/782.pdf)

### Abstract

We study the complexity of the Code Equivalence Problem on linear error-correcting codes by relating its variants to isomorphism problems on other discrete structures---graphs, lattices, and matroids. Our main results are a fine-grained reduction from the Graph Isomorphism Problem to the Linear Code Equivalence Problem over any field $\mathbb{F}$, and a reduction from the Linear Code Equivalence Problem over any field $\mathbb{F}_p$ of prime, polynomially bounded order $p$ to the Lattice Isomorphism Problem. Both of these reductions are simple and natural. We also give reductions between variants of the Code Equivalence Problem, and study the relationship between isomorphism problems on codes and linear matroids.

## 2024/783

* Title: Differential Cryptanalysis on Quantum Computers
* Authors: Kyungbae Jang, Yujin Oh, Hwajeong Seo
* [Permalink](https://eprint.iacr.org/2024/783)
* [Download](https://eprint.iacr.org/2024/783.pdf)

### Abstract

As quantum computing progresses, extensive research has been conducted to find quantum advantages in the field of cryptography. Combining quantum algorithms with classical cryptographic analysis methods, such as differential cryptanalysis and linear cryptanalysis, has the potential to reduce complexity.

In this paper, we present a quantum differential finding circuit for differential cryptanalysis. In our quantum circuit, both plaintext and input difference are in a superposition state. Actually, while our method cannot achieve a direct speedup with quantum computing, it offers a different perspective by relying on quantum probability in a superposition state.

For the quantum simulation, given the limited number of qubits, we simulate our quantum circuit by implementing the Toy-ASCON quantum circuit.

## 2024/784

* Title: Universal Blockchain Assets
* Authors: Owen Vaughan
* [Permalink](https://eprint.iacr.org/2024/784)
* [Download](https://eprint.iacr.org/2024/784.pdf)

### Abstract

We present a novel protocol for issuing and transferring tokens across blockchains without the need of a trusted third party or cross-chain bridge. In our scheme, the blockchain is used for double-spend protection only, while the authorisation of token transfers is performed off-chain. Due to the universality of our approach, it works in almost all blockchain settings. It can be implemented immediately on UTXO blockchains such as Bitcoin without modification, and on account-based blockchains such as Ethereum by introducing a smart contract that mimics the properties of a UTXO. We provide a proof-of-concept implementation of an NFT that is issued on Bitcoin, transferred to Ethereum, and then transferred back to Bitcoin. Our new approach means that users no longer need to be locked into one blockchain when issuing and transferring tokens.

## 2024/785

* Title: SmartBean: Transparent, Concretely Efficient, Polynomial Commitment Scheme with Logarithmic Verification and Communication Costs that Runs on Any Group
* Authors: Frank Y.C. Lu
* [Permalink](https://eprint.iacr.org/2024/785)
* [Download](https://eprint.iacr.org/2024/785.pdf)

### Abstract

We introduce a new, concretely efficient, transparent polynomial commitment scheme with logarithmic verification time and communication cost that can run on any group. Existing group-based polynomial commitment schemes must use less efficient groups, such as class groups of unknown order or pairing-based groups to achieve transparency (no trusted setup), making them expensive to adopt in practice. 

We offer the first group-based polynomial commitment scheme that can run on any group s.t. it does not rely on expensive pairing operations or require class groups of unknown order to achieve transparency while still providing logarithmic verifier time and communication cost. 

The prover work of our work is dominated by $4n \,\mathbb{G}$ multi-exponentiations, the verifier work is dominated by 4 log $n \, \mathbb{G}$ exponentiations, and the communication cost is 4 log $n \, \mathbb{G}$. Since our protocol can run on fast groups such as Curve25519, we can easily accelerate the multi-exponentiations with Pippenger's algorithm. The concrete performance of our work shows a significant improvement over the current state of the art in almost every aspect.

## 2024/786

* Title: Modelling Ciphers with Overdefined Systems of Quadratic Equations: Application to Friday, Vision, RAIN and Biscuit
* Authors: Fukang Liu, Mohammad Mahzoun, Willi Meier
* [Permalink](https://eprint.iacr.org/2024/786)
* [Download](https://eprint.iacr.org/2024/786.pdf)

### Abstract

It is well-known that a system of equations becomes easier to solve when it is overdefined. In this work, we study how to overdefine the system of equations to describe the arithmetic oriented (AO) ciphers Friday, Vision, and RAIN, as well as a special system of quadratic equations over $\mathbb F_{2^{\ell}}$ used in the post-quantum signature scheme Biscuit. Our method is inspired by Courtois-Pieprzyk's and Murphy-Robshaw's methods to model AES with overdefined systems of quadratic equations over $\mathbb F_2$ and $\mathbb F_{2^8}$, respectively. However, our method is more refined and much simplified compared with Murphy-Robshaw's method, since it can take full advantage of the low-degree $\mathbb F_2$-linearized affine polynomials used in Friday and Vision, and the overdefined system of equations over $\mathbb F_{2^{\ell}}$ can be described in a clean way with our method. For RAIN, we instead consider quadratic Boolean equations rather than equations over large finite fields $\mathbb F_{2^{\ell}}$. Specifically, we demonstrate that the special structure of RAIN allows us to set up much more linearly independent quadratic Boolean equations than those obtained only with Courtois-Pieprzyk's method. Moreover, we further demonstrate that the underlying key-recovery problem in Biscuit (NIST PQC Round 1 Additional Signatures) can also be described by solving a much overdefined system of quadratic equations over $\mathbb F_{2^{\ell}}$. On the downside, the constructed systems of quadratic equations for these ciphers cannot be viewed as semi-regular, which makes it challenging to upper bound the complexity of the Gröbner basis attack. However, such a new modelling method can significantly improve the lower bound of the complexity of the Gröbner basis attacks on these ciphers, i.e., we view the complexity of solving a random system of quadratic equations of the same scale as the lower bound. How to better estimate the upper and lower bounds of the Gröbner basis attacks on these ciphers based on our modelling method is left as an open problem.

## 2024/787

* Title: A new attack against search-LWE using Diophantine approximations
* Authors: Robin Frot, Daniel Zentai
* [Permalink](https://eprint.iacr.org/2024/787)
* [Download](https://eprint.iacr.org/2024/787.pdf)

### Abstract

In this paper, we present a new attack against search-LWE instances with a small secret key. The method consists of lifting the public key to $\mathbb Z$ and finding a good Diophantine approximation of the public key divided by the modulus $a$. This is done using lattice reduction algorithms. The lattice considered, and the approximation quality needed is similar to known decision-LWE attacks for small keys. However, we do not require an in-depth analysis of the reduction algorithm (any reduction algorithm giving small enough vectors is enough for us), and our method solves the search problem directly, which is harder than the decision problem.

## 2024/788

* Title: A Fault-Resistant NTT by Polynomial Evaluation and Interpolation
* Authors: Sven Bauer, Fabrizio De Santis, Kristjane Koleci, Anita Aghaie
* [Permalink](https://eprint.iacr.org/2024/788)
* [Download](https://eprint.iacr.org/2024/788.pdf)

### Abstract

In computer arithmetic operations, the Number Theoretic
Transform (NTT) plays a significant role in the efficient implementation
of cyclic and nega-cyclic convolutions with the application of multiplying
large integers and large degree polynomials. Multiplying polynomials is
a common operation in lattice-based cryptography. Hence, the NTT is a
core component of several lattice-based cryptographic algorithms. Two
well-known examples are the key encapsulation mechanism Kyber and
the digital signature algorithm Dilithium. In this work, we introduce a
novel and efficient method for safeguarding the NTT against fault attacks.
This new countermeasure is based on polynomial evaluation and
interpolation. We prove its error detection capability, calculate the required
additional computational effort, and show how to concretely use
it to secure the NTT in Kyber and Dilithium against fault injection
attacks. Finally, we provide concrete implementation results of the proposed
novel technique on a resource-constrained ARM Cortex-M4 microcontroller,
e.g., the technique exhibits a 72% relative overhead, when
applied to Dilithium.

## 2024/789

* Title: FairSec: Fair and Maliciously Secure Circuit-PSI via SPDZ-Compatible Oblivious PRF
* Authors: Yaxi Yang, Xiaojian Liang, Xiangfu Song, Linting Huang, Hongyu Ren, Changyu Dong, Jianying Zhou
* [Permalink](https://eprint.iacr.org/2024/789)
* [Download](https://eprint.iacr.org/2024/789.pdf)

### Abstract

Private Set Intersection (PSI) allows two parties to compute the intersection of their input sets without revealing more information than the computation results. PSI and its variants have numerous applications in practice. Circuit-PSI is a famous variant and aims to compute any functionality $f$ on items in the intersection set. However, the existing circuit-PSI protocols only provide security against \emph{semi-honest} adversaries. One straightforward solution is to extend a pure garbled-circuit-based PSI (NDSS'12) to a maliciously secure circuit-PSI, but it will result in non-concrete complexity. Another is converting state-of-the-art semi-honest circuit-PSI protocols (EUROCRYPT'21; PoPETS'22) to be secure in the malicious setting. However, it will come across \emph{the consistency issue} since parties can not guarantee the inputs of functionality $f$ stay unchanged as obtained from the last step.

This paper addresses the aforementioned issue by introducing FairSec, the first malicious circuit-PSI protocol. The central building block of FairSec, called Distributed Dual-key Oblivious PRF (DDOPRF), provides an oblivious evaluation of secret-shared inputs with dual keys. Additionally, we ensure the compatibility of DDOPRF with SPDZ, enhancing the versatility of our circuit-PSI protocol. Notably, our construction allows us to guarantee fairness within circuit-PSI effortlessly. Importantly, FairSec also achieves linear computation and communication complexities.

## 2024/790

* Title: Physical Ring Signature
* Authors: Xavier Bultel
* [Permalink](https://eprint.iacr.org/2024/790)
* [Download](https://eprint.iacr.org/2024/790.pdf)

### Abstract

Ring signatures allow members of a group (called "ring") to sign a message anonymously within the group, which is chosen ad hoc at the time of signing (the members do not need to have interacted before). In this paper, we propose a physical version of ring signatures. Our signature is based on one-out-of-many signatures, a method used in many real cryptographic ring signatures. It consists of boxes containing coins locked with padlocks that can only be opened by a particular group member. To sign a message, a group member shakes the boxes of the other members of the group so that the coins are in a random state ("heads" or "tails", corresponding to bits $0$ and $1$), and opens their box to arrange the coins so that the exclusive "or" of the coins corresponds to the bits of the message they wish to sign. We present a prototype that can be used with coins, or with dice for messages encoded in larger (non-binary) alphabets. We suggest that this system can be used to explain ring signatures to the general public in a fun way. Finally, we propose a semi-formal analysis of the security of our signature based on real cryptographic security proofs.

## 2024/791

* Title: Minimize the Randomness in Rasta-Like Designs: How Far Can We Go?
* Authors: Lorenzo Grassi, Fukang Liu, Christian Rechberger, Fabian Schmid, Roman Walch, Qingju Wang
* [Permalink](https://eprint.iacr.org/2024/791)
* [Download](https://eprint.iacr.org/2024/791.pdf)

### Abstract

The Rasta design strategy allows building low-round ciphers due to its efficient prevention of statistical attacks and algebraic attacks by randomizing the cipher, which makes it especially suitable for hybrid homomorphic encryption (HHE), also known as transciphering. Such randomization is obtained by pseudorandomly sampling new invertible matrices for each round of each new cipher evaluation. However, naively sampling a random invertible matrix for each round significantly impacts the plain evaluation runtime, though it does not impact the homomorphic evaluation cost. To address this issue, Dasta was proposed at ToSC 2020 to reduce the cost of generating the random matrices.

In this work, we address this problem from a different perspective: How far can the randomness in Rasta-like designs be reduced in order to minimize the plain evaluation runtime without sacrificing the security? To answer this question, we carefully studied the main threats to Rasta-like ciphers and the role of random matrices in ensuring security. We apply our results to the recently proposed cipher $\text{PASTA}$, proposing a modified version called $\text{PASTA}_\text{v2}$ instantiated with one initial random matrix and fixed linear layers - obtained by combining two MDS matrices with the Kronecker product - for the other rounds.

Compared with $\text{PASTA}$, the state-of-the-art cipher for BGV- and BFV-style HHE, our evaluation shows that $\text{PASTA}_\text{v2}$ is up to 100% faster in plain while having the same homomorphic runtime in the SEAL homomorphic encryption library and up to 30% faster evaluation time in HElib, respectively.

## 2024/792

* Title: Stickel's Key Agreement Algebraic Variation
* Authors: Daniel Nager
* [Permalink](https://eprint.iacr.org/2024/792)
* [Download](https://eprint.iacr.org/2024/792.pdf)

### Abstract

In this document we present a further development of non-commutative algebra based key agreement due to E. Stickel and a way to deal with the algebraic break due to V. Sphilrain.

## 2024/793

* Title: Hide-and-Seek and the Non-Resignability of the BUFF Transform
* Authors: Jelle Don, Serge Fehr, Yu-Hsuan Huang, Jyun-Jie Liao, Patrick Struck
* [Permalink](https://eprint.iacr.org/2024/793)
* [Download](https://eprint.iacr.org/2024/793.pdf)

### Abstract

The BUFF transform, due to Cremers et al. (S&P'21), is a generic transformation for digital signature scheme, with the purpose of obtaining additional security guarantees beyond unforgeability: exclusive ownership, message-bound signatures, and non-resignability. Non-resignability (which essentially challenges an adversary to re-sign an unknown message for which it only obtains the signature) turned out to be a delicate matter, as recently Don et al. (CRYPTO'24) showed that the initial definition is essentially unachievable; in particular, it is not achieved by the BUFF transform. This led to the introduction of new, weakened versions of non-resignability, which are (potentially) achievable. In particular, it was shown that a salted variant of the BUFF transform does achieves some weakened version of non-resignability. However, the salting requires additional randomness and leads to slightly larger signatures. Whether the original BUFF transform also achieves some meaningful notion of non-resignability remained a natural open question.

In this work, we answer this question in the affirmative. We show that the BUFF transform satisfies the (almost) strongest notions of non-resignability one can hope for, facing the known impossibility results. Our results cover both the statistical and the computational case, and both the classical and the quantum setting. At the core of our analysis lies a new security game for random oracles that we call Hide-and-Seek. While seemingly innocent at first glance, it turns out to be surprisingly challenging to rigorously analyze.

## 2024/794

* Title: Detecting Rogue Decryption in (Threshold) Encryption via Self-Incriminating Proofs
* Authors: James Hsin-yu Chiang, Bernardo David, Tore Kasper Frederiksen, Arup Mondal, Esra Yeniaras
* [Permalink](https://eprint.iacr.org/2024/794)
* [Download](https://eprint.iacr.org/2024/794.pdf)

### Abstract

Keeping decrypting parties accountable in public key encryption is notoriously hard since the secret key owner can decrypt any arbitrary ciphertext. Threshold encryption aims to solve this issue by distributing the power to decrypt among a set of parties, who must interact via a decryption protocol. However, such parties can employ cryptographic tools such as Multiparty Computation (MPC) to decrypt arbitrary ciphertexts without being detected. We introduce the notion of (threshold) encryption with Self-Incriminating Proofs, where parties must produce a self-incriminating proof of decryption when decrypting every ciphertext. In the standard public key encryption case, the adversary could destroy these proofs, so we strengthen our notion to guarantee that the proofs are published when decryption succeeds. This creates a decryption audit trail, which is useful in scenarios where decryption power is held by a single trusted party (e.g., a Trusted Execution Environment) who must be kept accountable. In the threshold case, we ensure that at least one of the parties who execute the decryption protocol will learn a self-incriminating proof, even if they employ advanced tools such as MPC. The fact that a party learns the proof and may leak it at any moment functions as a deterrent for parties who do not wish to be identified as malicious decryptors (e.g., a commercial operator of a service based on threshold encryption). We investigate the (im)possibility and applications of our notions while providing matching constructions under appropriate assumptions. In the threshold case, we build on recent results on Individual Cryptography (CRYPTO 2023).

## 2024/795

* Title: New Limits of Provable Security and Applications to ElGamal Encryption
* Authors: Sven Schäge
* [Permalink](https://eprint.iacr.org/2024/795)
* [Download](https://eprint.iacr.org/2024/795.pdf)

### Abstract

We provide new results showing that ElGamal encryption cannot be proven CCA1-secure – a long-standing open problem in cryptography. Our result follows from a very broad, meta-reduction-based impossibility result on random self-reducible relations with efficiently re-randomizable witnesses. The techniques that we develop allow, for the first time, to provide impossibility results for very weak security notions where the challenger outputs fresh challenge statements at the end of the security game. This can be used to finally tackle encryption-type definitions that have remained elusive in the past. We show that our results have broad applicability by casting several known cryptographic setups as instances of random self-reducible and re-randomizable relations. These setups include general semi-homomorphic PKE and the large class of certified homomorphic one-way bijections. As a result, we also obtain new impossibility results for the IND-CCA1 security of the PKEs of Paillier and Damg ̊ard–Jurik, and many one-more inversion assumptions like the one-more DLOG or the one-more RSA assumption.

## 2024/796

* Title: Weak Consistency mode in Key Transparency: OPTIKS
* Authors: Esha Ghosh, Melissa Chase
* [Permalink](https://eprint.iacr.org/2024/796)
* [Download](https://eprint.iacr.org/2024/796.pdf)

### Abstract

The need for third-party auditors in privacy-preserving Key Transparency (KT) systems presents a deployment challenge. In this short note, we take a simple privacy-preserving KT system that provides strong security guarantees in the presence of an honest auditor (OPTIKS) and show how to add a auditor-free mode to it. The auditor-free mode offers slightly weaker security. We formalize this security property and prove that our proposed protocol satisfies our security definition.

## 2024/797

* Title: Nonadaptive One-Way to Hiding Implies Adaptive Quantum Reprogramming
* Authors: Joseph Jaeger
* [Permalink](https://eprint.iacr.org/2024/797)
* [Download](https://eprint.iacr.org/2024/797.pdf)

### Abstract

An important proof technique in the random oracle model involves reprogramming it on hard to predict inputs and arguing that an attacker cannot detect that this occurred. In the quantum setting, a particularly challenging version of this considers adaptive reprogramming wherein the points to be reprogrammed (or output values they should be programmed to) are dependent on choices made by the adversary. Frameworks for analyzing adaptive reprogramming were given by, e.g., by Unruh (CRYPTO 2014), Grilo-Hövelmanns-Hülsing-Majenz (ASIACRYPT 2021), and Pan-Zeng (PKC 2024).

We show, counterintuitively, that these adaptive results follow directly from the non-adaptive one-way to hiding theorem of Ambainis-Hamburg-Unruh (CRYPTO 2019). These implications contradict beliefs (whether stated explicitly or implicitly) that some properties of the adaptive frameworks cannot be provided by the Ambainis-Hamburg-Unruh result.

## 2024/798

* Title: Incompressible Functional Encryption
* Authors: Rishab Goyal, Venkata Koppula, Mahesh Sreekumar Rajasree, Aman Verma
* [Permalink](https://eprint.iacr.org/2024/798)
* [Download](https://eprint.iacr.org/2024/798.pdf)

### Abstract

Incompressible encryption (Dziembowski, Crypto'06; Guan, Wichs, Zhandry, Eurocrypt'22) protects from attackers that learn the entire decryption key, but cannot store the full ciphertext. In incompressible encryption, the attacker must try to compress a ciphertext within pre-specified memory bound $S$ before receiving the secret key.

In this work, we generalize the notion of incompressibility to functional encryption. In incompressible functional encryption, the adversary can corrupt non-distinguishing keys at any point, but receives the distinguishing keys only after compressing the ciphertext to within $S$ bits. An important efficiency measure for incompressible encryption is the ciphertext-rate ( i.e., $\mathsf{rate} = \frac{|m|}{|\mathsf{ct}|}\;$). We give many new results for incompressible functional encryption:

1. Incompressible attribute-based encryption for circuits from standard assumptions, with $\mathsf{ct}$-rate-$\frac{1}{2}$ and short secret keys,
2. Incompressible functional encryption for circuits from (non-incompressible) functional encryption, with
(a) $\mathsf{ct}$-rate-$\frac{1}{2}$ and short secret keys,
(b) $\mathsf{ct}$-rate-$1$ and large secret keys.

Our results achieve optimal efficiency, as incompressible attribute-based/functional encryption with $\mathsf{ct}$-rate-$1$ as well as short secret keys has strong implausibility barriers. Moreover, our assumptions are minimal as incompressible attribute-based/functional encryption are strictly stronger than their non-incompressible counterparts.

## 2024/799

* Title: Symmetric Signcryption and E2EE Group Messaging in Keybase
* Authors: Joseph Jaeger, Akshaya Kumar, Igors Stepanovs
* [Permalink](https://eprint.iacr.org/2024/799)
* [Download](https://eprint.iacr.org/2024/799.pdf)

### Abstract

We introduce a new cryptographic primitive called symmetric signcryption, which differs from traditional signcryption because the sender and recipient share a secret key. We prove that a natural composition of symmetric encryption and signatures achieves strong notions of security against attackers that can learn and control many keys. We then identify that the core encryption algorithm of the Keybase encrypted messaging protocol can be modeled as a symmetric signcryption scheme. We prove the security of this algorithm, though our proof requires assuming non-standard, brittle security properties of the underlying primitives.

## 2024/800

* Title: A Note on Zero-Knowledge for NP and One-Way Functions
* Authors: Yanyi Liu, Noam Mazor, Rafael Pass
* [Permalink](https://eprint.iacr.org/2024/800)
* [Download](https://eprint.iacr.org/2024/800.pdf)

### Abstract

We present a simple alternative exposition of the the recent result of Hirahara and Nanashima (STOC’24) showing that one-way functions exist if (1) every language in NP has a zero-knowledge proof/argument and (2) ZKA contains non-trivial languages. Our presentation does not rely on meta-complexity and we hope it may be useful for didactic purposes.

## 2024/801

* Title: Algebraic Structure of the Iterates of $\chi$
* Authors: Björn Kriepke, Gohar Kyureghyan
* [Permalink](https://eprint.iacr.org/2024/801)
* [Download](https://eprint.iacr.org/2024/801.pdf)

### Abstract

We consider the map $\chi:\mathbb{F}_2^n\to\mathbb{F}_2^n$ for $n$ odd given by $y=\chi(x)$ with $y_i=x_i+x_{i+2}(1+x_{i+1})$, where the indices are computed modulo $n$. We suggest a generalization of the map $\chi$ which we call generalized $\chi$-maps. We show that these maps form an Abelian group which is isomorphic to the group of units in $\mathbb{F}_2[X]/(X^{(n+1)/2})$. Using this isomorphism we easily obtain closed-form expressions for iterates of $\chi$ and explain their properties.

## 2024/802

* Title: On Maximum Size Simultaneous Linear Approximations in Ascon and Keccak and Related Translation and Differential Properties
* Authors: Nicolas T. Courtois, Frédéric Amiel, Alexandre Bonnard de Fonvillars
* [Permalink](https://eprint.iacr.org/2024/802)
* [Download](https://eprint.iacr.org/2024/802.pdf)

### Abstract

In this paper we study the S-box known as Chi or \chi initially proposed by Daemen in 1995 and very widely used ever since in Keccak, Ascon, and many other. This type of ciphers is typically analyzed [in recent research] in terms of subspace trail attacks [TeDi19] and vector space invariants. An interesting question is then, when different spaces are mapped to each other by translations with a constant.
In this paper we relax this fundamental question and we consider arbitrary sets of points and their translations. We generalize previous S-box partial linearization results on Keccak and Ascon from Eurocrypt 2017. We basically introduce new ways to linearize the Ascon S-box to the maximum possible extent. On this basis we show further remarkable properties and some surprising connections between [simultaneous] linear and [prominent] differential properties.. We exhibit a new family of maximum size and optimal approximation properties with 11 points, beyond the maximum size of any set in the DDT table.
We prove a theorem which guarantees that this type of properties are stable by arbitrary input-side translations which holds for all quadratic permutations. All this will be placed in the context of previous work on classification of 5-bit quadratic permutations.

## 2024/803

* Title: Can We Beat Three Halves Lower Bound?: (Im)Possibility of Reducing Communication Cost for Garbled Circuits
* Authors: Chunghun Baek, Taechan Kim
* [Permalink](https://eprint.iacr.org/2024/803)
* [Download](https://eprint.iacr.org/2024/803.pdf)

### Abstract

Recent improvements to garbled circuits are mainly focused on reducing their size.
The state-of-the-art construction of Rosulek and Roy (Crypto 2021) requires $1.5\kappa$ bits for garbling AND gates in the free-XOR setting.
This is below the previously proven lower bound $2\kappa$ in the linear garbling model of Zahur, Rosulek, and Evans (Eurocrypt 2015).
Whether their construction is optimal in a more inclusive model than the linear garbling model still remains open.

This paper begins by providing a comprehensive model for a large class of practical garbling schemes
and proves the lower bound for the size of the garbled AND gates in our model.
We show that garbled AND gates require at least $1.5\kappa$ bits in our new model with the free-XOR setting.

It is remarkable to see that the construction by Rosulek and Roy is already optimal
despite the fact that our model possibly captures any potential extension of their construction.

## 2024/804

* Title: Analysis on Sliced Garbling via Algebraic Approach
* Authors: Taechan Kim
* [Permalink](https://eprint.iacr.org/2024/804)
* [Download](https://eprint.iacr.org/2024/804.pdf)

### Abstract

Recent improvements to garbled circuits are mainly focused on reducing their size.
The state-of-the-art construction of Rosulek and Roy~(Crypto~2021) requires $1.5\kappa$ bits for garbling AND gates in the free-XOR setting.
This is below the previously proven lower bound $2\kappa$ in the linear garbling model of Zahur, Rosulek, and Evans~(Eurocrypt~2015).

Recently, Ashur, Hazay, and Satish~(eprint 2024/389) proposed a scheme that requires $4/3\kappa + O(1)$ bits for garbling AND gates.
Precisely they extended the idea of \emph{slicing} introduced by Rosulek and Roy to garble 3-input gates of the form $g(u,v,w) := u(v+w)$.
By setting $w = 0$, it can be used to garble AND gates with the improved communication costs.

However, in this paper, we observe that the scheme proposed by Ashur, Hazy, and Satish leaks information on the permute bits,
thereby allowing the evaluator to reveal information on the private inputs.
To be precise, we show that in their garbling scheme, the evaluator can compute the bits $\alpha$ and $\beta + \gamma$,
where $\alpha$, $\beta$, and $\gamma$ are the private permute bits of the input labels $A$, $B$, and $C$, respectively.

## 2024/805

* Title: DiTRU: A Resurrection of NTRU over Dihedral Group
* Authors: Ali Raya, Vikas Kumar, Sugata Gangopadhyay
* [Permalink](https://eprint.iacr.org/2024/805)
* [Download](https://eprint.iacr.org/2024/805.pdf)

### Abstract

NTRU-like cryptosystems are among the most studied lattice-based post-quantum candidates. While most NTRU proposals have been introduced over a commutative ring of quotient polynomials, other rings can be used. Noncommutative algebra has been endorsed as a direction to build new variants of NTRU a long time ago. The first attempt to construct a noncommutative variant was due to Hoffstein and Silverman motivated by more resistance to lattice attack. The scheme has been built over the group ring of a dihedral group. However, their design differed from standard NTRU and soon was found vulnerable to algebraic attacks. In this work, we revive the group ring NTRU over the dihedral group as an instance of the GR-NTRU framework.
Unlike many proposals of noncommutative variants in the literature, our work focuses on putting the scheme into practice. We clear all the aspects that make our scheme implementable by proposing an efficient inversion algorithm over the new setting of the noncommutative ring, describing the decryption failure model, and analyzing the lattice associated with our instantiation. Finally, we discuss the best-known attacks against our scheme and provide an implementation targeting 128-bit, 192-bit, and 256-bit levels of security as proof of its practicality.

## 2024/806

* Title: Resettable Statistical Zero-Knowledge for NP
* Authors: Susumu Kiyoshima
* [Permalink](https://eprint.iacr.org/2024/806)
* [Download](https://eprint.iacr.org/2024/806.pdf)

### Abstract

Resettable statistical zero-knowledge [Garg--Ostrovsky--Visconti--Wadia, TCC 2012] is a strong privacy notion that guarantees statistical zero-knowledge even when the prover uses the same randomness in multiple proofs.

In this paper, we show an equivalence of resettable statistical zero-knowledge arguments for $NP$ and witness encryption schemes for $NP$.
- Positive result: For any $NP$ language $L$, a resettable statistical zero-knowledge argument for $L$ can be constructed from a witness encryption scheme for $L$ under the assumption of the existence of one-way functions.
- Negative result: The existence of even resettable statistical witness-indistinguishable arguments for $NP$ imply the existence of witness encryption schemes for $NP$ under the assumption of the existence of one-way functions.
The positive result is obtained by naturally extending existing techniques (and is likely to be already well-known among experts). The negative result is our main technical contribution.

To explore workarounds for the negative result, we also consider resettable security in a model where the honest party's randomness is only reused with fixed inputs. We show that resettable statistically hiding commitment schemes are impossible even in this model.

## 2024/807

* Title: Optimal Consensus in the Presence of Overlapping Faults and Total Omission
* Authors: Julian Loss, Kecheng Shi, Gilad Stern
* [Permalink](https://eprint.iacr.org/2024/807)
* [Download](https://eprint.iacr.org/2024/807.pdf)

### Abstract

Understanding the fault tolerance of Byzantine Agreement protocols is an important question in distributed computing. While the setting of Byzantine faults has been thoroughly explored in the literature, the (arguably more realistic) omission fault setting is far less studied. In this paper, we revisit the recent work of Loss and Stern who gave the first protocol in the mixed fault model tolerating $t$ Byzantine faults, $s$ send faults, and $r$ receive faults, when $2t+r+s<n$ and omission faults do not overlap. We observe that their protocol makes no guarantees when omission faults can overlap, i.e., when parties can simultaneously have send and receive faults. We give the first protocol that overcomes this limitation and tolerates the same number of potentially overlapping faults. We then study, for the first time, the total omission setting where all parties can become omission faulty. This setting is motivated by real-world scenarios where every party may experience connectivity issues from time to time, yet agreement should still hold for the parties who manage to output values. We show the first agreement protocol in this setting with parameters $s<n$ and $s+r=n$. On the other hand, we prove that there is no consensus protocol for the total omission setting which tolerates even a single overlapping omission fault, i.e., where $s+r=n+1$ and $s>2$, or a broadcast protocol for $s+r=n$ and $s>1$ even without overlapping faults.

## 2024/808

* Title: Arma: Byzantine Fault Tolerant Consensus with Horizontal Scalability
* Authors: Yacov Manevich, Hagar Meir, Kaoutar Elkhiyaoui, Yoav Tock, May Buzaglo
* [Permalink](https://eprint.iacr.org/2024/808)
* [Download](https://eprint.iacr.org/2024/808.pdf)

### Abstract

Arma is a Byzantine Fault Tolerant (BFT) consensus system designed to
achieve horizontal scalability across all hardware resources: network
bandwidth, CPU, and disk I/O. As opposed to preceding BFT protocols, Arma separates the dissemination and validation of client transactions from the consensus process, restricting the latter to totally ordering only metadata of batches of transactions. This separation enables each party to distribute compute and storage resources for transaction validation, dissemination and disk I/O among multiple machines, resulting in horizontal scalability.
Additionally, Arma ensures censorship resistance by imposing a maximum
time limit on the inclusion of client transactions. We built and evaluated two Arma prototypes. The first is an independent system handling over 200,000 transactions per second, the second integrated into Hyperledger Fabric, speeding its consensus by an order of magnitude.

## 2024/809

* Title: Reducing Overdefined Systems of Polynomial Equations Derived from Small Scale Variants of the AES via Data Mining Methods
* Authors: Jana Berušková, Martin Jureček, Olha Jurečková
* [Permalink](https://eprint.iacr.org/2024/809)
* [Download](https://eprint.iacr.org/2024/809.pdf)

### Abstract

This paper deals with reducing the secret key computation time of small scale variants of the AES cipher using algebraic cryptanalysis, which is accelerated by data mining methods. This work is based on the known plaintext attack and aims to speed up the calculation of the secret key by processing the polynomial equations extracted from plaintext-ciphertext pairs. Specifically, we propose to transform the overdefined system of polynomial equations over GF(2) into a new system so that the computation of the Gröbner basis using the F4 algorithm takes less time than in the case of the original system. The main idea is to group similar polynomials into clusters, and for each cluster, sum the two most similar polynomials, resulting in simpler polynomials. We compare different data mining techniques for finding similar polynomials, such as clustering or locality-sensitive hashing (LSH). Experimental results show that using the LSH technique, we get a system of equations for which we can calculate the Gröbner basis the fastest compared to the other methods that we consider in this work. Experimental results also show that the time to calculate the Gröbner basis for the transformed system of equations is significantly reduced compared to the case when the Gröbner basis was calculated from the original non-transformed system. This paper demonstrates that reducing an overdefined system of equations reduces the computation time for finding a secret key.

## 2024/810

* Title: The Perils of Limited Key Reuse: Adaptive and Parallel Mismatch Attacks with Post-processing Against Kyber
* Authors: Qian Guo, Erik Mårtensson, Adrian Åström
* [Permalink](https://eprint.iacr.org/2024/810)
* [Download](https://eprint.iacr.org/2024/810.pdf)

### Abstract

In this paper, we study the robustness of Kyber, the Learning With Errors (LWE)-based Key Encapsulation Mechanism (KEM) chosen for standardization by NIST, against key mismatch attacks. We demonstrate that Kyber's security levels can be compromised with a few mismatch queries by striking a balance between the parallelization level and the cost of lattice reduction for post-processing. This highlights the imperative need to strictly prohibit key reuse in CPA-secure Kyber.

We further propose an adaptive method to enhance parallel mismatch
attacks, initially proposed by Shao et al. at AsiaCCS 2024, thereby significantly reducing query complexity. This method combines the adaptive attack with post-processing via lattice reduction to retrieve the final secret key entries. Our method proves its efficacy by reducing query complexity by 14.6 % for Kyber512 and 7.5 % for Kyber768/Kyber1024.

Furthermore, this approach has the potential to substantially improve
multi-value Plaintext-Checking (PC) oracle-based side-channel attacks against the CCA-secure version of Kyber KEM.

## 2024/811

* Title: Traceable Secret Sharing Based on the Chinese Remainder Theorem
* Authors: Charlotte Hoffmann
* [Permalink](https://eprint.iacr.org/2024/811)
* [Download](https://eprint.iacr.org/2024/811.pdf)

### Abstract

Traceable threshold secret sharing schemes, introduced by Goyal, Song and Srinivasan (CRYPTO'21), allow to provably trace leaked shares to the parties that leaked them. The authors give the first definition and construction of traceable secret sharing schemes. However, the size of the shares in their construction are quadratic in the size of the secret. Boneh, Partap and Rotem (CRYPTO'24) recently proposed a new definition of traceable secret sharing and the first practical constructions. In their definition, one considers a reconstruction box $R$ that contains $f$ leaked shares and, on input $t-f$ additional shares, outputs the secret $s$. A scheme is traceable if one can find out the leaked shares inside the box $R$ by only getting black-box access to $R$. Boneh, Partap and Rotem give constructions from Shamir's secret sharing and Blakely's secret sharing. The constructions are efficient as the size of the secret shares is only twice the size of the secret.

In this work we present the first traceable secret sharing scheme based on the Chinese remainder theorem. This was stated as an open problem by Boneh, Partap and Rotem, as it gives rise to traceable secret sharing with weighted threshold access structures. The scheme is based on Mignotte's secret sharing and increases the size of the shares of the standard Mignotte secret sharing scheme by a factor of $2$.

## 2024/812

* Title: Relations among new CCA security notions for approximate FHE
* Authors: Sébastien Canard, Caroline Fontaine, Duong Hieu Phan, David Pointcheval, Marc Renard, Renaud Sirdey
* [Permalink](https://eprint.iacr.org/2024/812)
* [Download](https://eprint.iacr.org/2024/812.pdf)

### Abstract

In a recent Eurocrypt'24 paper, Manulis and Nguyen have proposed a new CCA security notion, vCCA, and associated construction blueprints to leverage both CPA-secure and correct FHE beyond the CCA1 security barrier. However, because their approach is only valid under the correctness assumption, it leaves a large part of the FHE spectrum uncovered as many FHE schemes used in practice turn out to be approximate and, as such, do not satisfy the correctness assumption. In this paper, we improve their work by defining and investigating a variant of their security notion which is suitable for a more general case where approximate FHE are included. As the passive security of approximate FHE schemes is more appropriately captured by CPAD rather than CPA security, we start from the former notion to define our vCCAD new security notion. Although, we show that vCCA and vCCAD are equivalent when the correctness assumption holds, we establish that vCCAD security is strictly stronger than vCCA security in the general case. In doing so, we interestingly establish several new separation results between variants of CPAD security of increasing strength. This allows us to clarify the relationship between vCCA security and CPAD security, and to reveal that the security notions landscape is much simpler for exact FHE than when approximate ones are included --- in which case, for example, we establish that multiple challenges security notions are strictly stronger than single-challenge ones for both CPAD and vCCAD security. Lastly, we also give concrete construction blueprints, showing how to leverage some of the blueprints proposed by Manulis and Nguyen to achieve vCCAD security. As a result, vCCAD security is the strongest CCA security notion so far known to be achievable by both correct and approximate FHE schemes.

## 2024/813

* Title: How to Redact the Bitcoin Backbone Protocol
* Authors: Mehmet Sabir Kiraz, Enrique Larraia, Owen Vaughan
* [Permalink](https://eprint.iacr.org/2024/813)
* [Download](https://eprint.iacr.org/2024/813.pdf)

### Abstract

We explain how to extend the Bitcoin backbone model of Garay et al. (Eurocrypt, 2015) to accommodate for redactable blockchains. Our extension captures fluid blockchain-based databases (with mutability requirements) and compliance with existing legislation, such as the GDPR right to be forgotten, or the need to erase offending data from nodes’ databases that would otherwise provoke legal shutdowns. Our redactable backbone protocol retains the essential properties of blockchains. Leveraging zero-knowledge proofs, old data can be erased without requiring trusted third parties or heuristics about past chain validation. Our solution can be implemented on Bitcoin immediately without hard-forks, and it is scalable. It allows the redaction of data from UTXOs or unconfirmed transactions that have not yet flooded the network, while guaranteeing invariance of the Bitcoin state. Thus, offending data does not need to persist in the system, not even temporarily.

## 2024/814

* Title: Succinct Homomorphic Secret Sharing
* Authors: Damiano Abram, Lawrence Roy, Peter Scholl
* [Permalink](https://eprint.iacr.org/2024/814)
* [Download](https://eprint.iacr.org/2024/814.pdf)

### Abstract

This work introduces homomorphic secret sharing (HSS) with succinct share size. In HSS, private inputs are shared between parties, who can then homomorphically evaluate a function on their shares, obtaining a share of the function output. In succinct HSS, a portion of the inputs can be distributed using shares whose size is sublinear in the number of such inputs. The parties can then locally evaluate a function $f$ on the shares, with the restriction that $f$ must be linear in the succinctly shared inputs.

We construct succinct, two-party HSS for branching programs, based on either the decisional composite residuosity assumption, a DDH-like assumption in class groups, or learning with errors with a superpolynomial modulus-to-noise ratio. We then give several applications of succinct HSS, which were only previously known using fully homomorphic encryption, or stronger tools:

- Succinct vector oblivious linear evaluation (VOLE): Two parties can obtain secret shares of a long, arbitrary vector $\vec x$, multiplied by a scalar $\Delta$, with communication sublinear in the size of the vector.
- Batch, multi-party distributed point functions: A protocol for distributing a batch of secret, random point functions among $N$ parties, for any polynomial $N$, with communication sublinear in the number of DPFs.
- Sublinear MPC for any number of parties: Two new constructions of MPC with sublinear communication complexity, with $N$ parties for any polynomial $N$: (1) For general layered Boolean circuits of size $s$, with communication $O(N s/\log\log s)$, and (2) For layered, sufficiently wide Boolean circuits, with communication $O(N s/\log s)$.

## 2024/815

* Title: Faster verifications and smaller signatures: Trade-offs for ALTEQ using rejections
* Authors: Arnaud Sipasseuth
* [Permalink](https://eprint.iacr.org/2024/815)
* [Download](https://eprint.iacr.org/2024/815.pdf)

### Abstract

In this paper, we introduce a new probability function parameter in the instantiations of the Goldreich-Micali-Wigderson with Fiat-Shamir and unbalanced challenges used in ALTEQ, a recent NIST PQC candidate in the call for additional signatures. This probability set at 100% does not bring any changes in the scheme, but modifies the public challenge generation process when below 100%, by injecting potential rejections in otherwise completely valid inputs.
From a theoretical point of view, this does not improve the asymptotical hardness of the scheme and negatively affects the efficiency of the signatory, and might itself seem trivial. However, from a practical point of view, implementation-wise and performance-wise, this triviality allows an extra degree of freedom in optimizing parameters, as the heuristic security level is also increased against forgers: previously valid combinations now can be deemed invalid. This allows us to make trade-offs to reduce the computational load in verifiers, accelerating verifications, marginally reduce the signature size, at the cost of making signatures slower and unlikely to be constant-time.
In particular, this extra degree of freedom allows to make implementation choices that enable smoother and faster executions of the aforementioned protocols, especially in the context of parallelization using vectorized instructions. We also demonstrate the usefulness of our proposal to ALTEQ for other options, when slowing down the signing process is not an issue: significantly smaller signatures but longer verifications, or lower public key sizes.
The ideas presented apply to any primitive, and can be used beyond ALTEQ.

## 2024/816

* Title: Zero-knowledge IOPs Approaching Witness Length
* Authors: Noga Ron-Zewi, Mor Weiss
* [Permalink](https://eprint.iacr.org/2024/816)
* [Download](https://eprint.iacr.org/2024/816.pdf)

### Abstract

Interactive Oracle Proofs (IOPs) allow a probabilistic verifier interacting with a prover to verify the validity of an NP statement while reading only few bits from the prover messages. IOPs generalize standard Probabilistically-Checkable Proofs (PCPs) to the interactive setting, and in the few years since their introduction have already exhibited major improvements in main parameters of interest (such as the proof length and prover and verifier running times), which in turn led to significant improvements in constructions of succinct arguments. Zero-Knowledge (ZK) IOPs additionally guarantee that the view of any query-bounded (possibly malicious) verifier can be efficiently simulated.. ZK-IOPs are the main building block of succinct ZK arguments which use the underlying cryptographic object (e.g., a collision-resistant hash function) as a black box.

In this work, we construct the first ZK-IOPs approaching the witness length for a natural NP problem. More specifically, we design constant-query and constant-round IOPs for 3SAT in which the total communication is $(1+\gamma)m$, where $m$ is the number of variables and $\gamma>0$ is an arbitrarily small constant, and ZK holds against verifiers querying $m^\beta$ bits from the prover's messages, for a constant $\beta>0$. This gives a ZK variant of a recent result of Ron-Zewi and Rothblum (FOCS `20), who construct (non-ZK) IOPs approaching the witness length for a large class of NP languages. Previous constructions of ZK-IOPs incurred an (unspecified) large constant multiplicative overhead in the proof length, even when restricting to ZK against the honest verifier.

We obtain our ZK-IOPs by improving the two main building blocks underlying most ZK-IOP constructions, namely ZK codes and ZK-IOPs for sumcheck. More specifically, we give the first ZK-IOPs for sumcheck that achieve both sublinear communication for sumchecking a general tensor code, and a ZK guarantee. We also show a strong ZK preservation property for tensors of ZK codes, which extends a recent result of Bootle, Chiesa, and Liu (EC `22). Given the central role of these objects in designing ZK-IOPs, these results might be of independent interest.

## 2024/817

* Title: DVA: Dangerous Variations of ALTEQ
* Authors: Arnaud Sipasseuth
* [Permalink](https://eprint.iacr.org/2024/817)
* [Download](https://eprint.iacr.org/2024/817.pdf)

### Abstract

In this paper, we present three types of variations of the ALTEQ cryptosystem, a recent submission to the NIST's additional call for signatures. We name these Dangerous Variations of ALTEQ (DVA), as there is always a certain danger in stepping out of usual constructions, although we attempt to maintain heuristic security.
First, we present DVA-GG (Graph Generalization), that can be seen as a more abstract point-of-view on the operations done in ALTEQ and encourages more research on the algebraic variants. In particular, we show this approach can lead to a patch counter to Beullens' recent seed collision attack on ALTEQ that only depends on the primitive, and showcase some fancy usages of the primitive for experimental protocols.
Second, we present DVA-PC (Precomputations) which is ``likely'' as secure as ALTEQ in the random oracle model, and allow to drastically reduce the intermediate memory requirements within both the signature and verification process through an easily parallelizable extra operation. In particular, this facilitates precomputation variants with online phases that only depends on the complexity of basic matrix operations. We can then choose between either a tiny offline memory per signature, or get one of the fastest online signing speed for post-quantum cryptography.
Third, we present DVA-DM (Distinct Matrices), some cryptanalytic targets that deviates from ALTEQ's original algebraic structure. Those structures can serve as plain computational acceleration or just compress data sizes,
and provide good options to motivate the study of specialized
cryptanalysis for ALTEQ: if those are safe, then ALTEQ gain safe variants, and otherwise, we gain further understanding of the problems.
In particular, the ideas can be applied beyond ALTEQ and beyond, and hopefully extend to MEDS, LESS, and group-action-based cryptography.

## 2024/818

* Title: The Brave New World of Global Generic Groups and UC-Secure Zero-Overhead SNARKs
* Authors: Jan Bobolz, Pooya Farshim, Markulf Kohlweiss, Akira Takahashi
* [Permalink](https://eprint.iacr.org/2024/818)
* [Download](https://eprint.iacr.org/2024/818.pdf)

### Abstract

The universal composability (UC) model provides strong security guarantees for protocols used in arbitrary contexts. While these guarantees are highly desirable, in practice, schemes with a standalone proof of security, such as the Groth16 proof system, are preferred. This is because UC security typically comes with undesirable overhead, sometimes making UC-secure schemes significantly less efficient than their standalone counterparts. We establish the UC security of Groth16 without any significant overhead. In the spirit of global random oracles, we design a global (restricted) observable generic group functionality that models a natural notion of observability: computations that trace back to group elements derived from generators of other sessions are observable. This notion turns out to be surprisingly subtle to formalize. We provide a general framework for proving protocols secure in the presence of global generic groups, which we then apply to Groth16.

## 2024/819

* Title: A new stand-alone MAC construct called SMAC
* Authors: Dachao Wang, Alexander Maximov, Patrik Ekdahl, Thomas Johansson
* [Permalink](https://eprint.iacr.org/2024/819)
* [Download](https://eprint.iacr.org/2024/819.pdf)

### Abstract

In this paper, we present a new efficient stand-alone MAC construct based on processing using the FSM part of the stream cipher family SNOW, which in turn uses the AES round function. It offers a combination of very high speed in software and hardware with a truncatable tag. Two concrete versions of SMAC are proposed with different security levels, although other use cases are also possible. For example, SMAC can be combined with an external ciphering engine in AEAD mode. Every design choice is justified and supported by the results of our analysis and simulations. A novelty of the proposal is that it meets future performance requirements but is still not directly vulnerable to attacks using repeated nonce when the tag size is short, as is the case for other very fast MACs (MACs based on polynomial hashing). This can be an important aspect in practical applications.

## 2024/820

* Title: Rate-1 Arithmetic Garbling from Homomorphic Secret-Sharing
* Authors: Pierre Meyer, Claudio Orlandi, Lawrence Roy, Peter Scholl
* [Permalink](https://eprint.iacr.org/2024/820)
* [Download](https://eprint.iacr.org/2024/820.pdf)

### Abstract

We present a new approach to garbling arithmetic circuits using techniques from homomorphic secret sharing, obtaining constructions with high rate that support free addition gates. In particular, we build upon non-interactive protocols for computing distributed discrete logarithms in groups with an easy discrete-log subgroup, further demonstrating the versatility of tools from homomorphic secret sharing. Relying on distributed discrete log for the Damgård-Jurik cryptosystem (Roy and Singh, Crypto `21), whose security follows from the decisional composite residuosity assumption (DCR), we get the following main results:

[**Two ciphertexts per multiplication, from IND-CPA security of Damgård-Jurik.**]
Assuming the Damgård-Jurik cryptosystem is semantically secure (which follows from DCR), there is a garbling scheme for circuits with $B$-bounded integer arithmetic using only two ciphertexts per multiplication. The total bit-size of the resulting garbled circuit is:
$$(n + 2s_\times+2D_\times)\cdot (\zeta + 1) \cdot \log N$$
where $n$ is the number of inputs, $s_\times$ is the number of multiplications, $D_\times$ is the multiplicative depth of the circuit, $N$ is an RSA modulus and $N^{\zeta-1}$ is a rough bound on the magnitude of wire values in the computation.

[**One ciphertext per multiplication, from KDM security of Damgård-Jurik..**]
Assuming the Damgård-Jurik encryption scheme remains secure given encryption of the key and its inverse, the construction achieves rate-$1$. The total bit-size of the resulting garbled circuit is:
$$(n + s_\times + 1) \cdot (\zeta + 1) \cdot \log N$$
where the parameters are as above, except $N^{\zeta-2}$ is the magnitude bound.

As a side result, we show that our scheme based on IND-CPA security achieves rate $3/5$ for levelled circuits.

## 2024/821

* Title: A General Framework for Lattice-Based ABE Using Evasive Inner-Product Functional Encryption
* Authors: Yao-Ching Hsieh, Huijia Lin, Ji Luo
* [Permalink](https://eprint.iacr.org/2024/821)
* [Download](https://eprint.iacr.org/2024/821.pdf)

### Abstract

We present a general framework for constructing attribute-based encryption (ABE) schemes for arbitrary function class based on lattices from two ingredients, i) a noisy linear secret sharing scheme for the class and ii) a new type of inner-product functional encryption (IPFE) scheme, termed *evasive* IPFE, which we introduce in this work. We propose lattice-based evasive IPFE schemes and establish their security under simple conditions based on variants of evasive learning with errors (LWE) assumption recently proposed by Wee [EUROCRYPT ’22] and Tsabary [CRYPTO ’22].

Our general framework is modular and conceptually simple, reducing the task of constructing ABE to that of constructing noisy linear secret sharing schemes, a more lightweight primitive. The versatility of our framework is demonstrated by three new ABE schemes based on variants of the evasive LWE assumption.

- We obtain two ciphertext-policy ABE schemes for all polynomial-size circuits with a predetermined depth bound. One of these schemes has *succinct* ciphertexts and secret keys, of size polynomial in the depth bound, rather than the circuit size. This eliminates the need for tensor LWE, another new assumption, from the previous state-of-the-art construction by Wee [EUROCRYPT ’22].

- We develop ciphertext-policy and key-policy ABE schemes for deterministic finite automata (DFA) and logspace Turing machines ($\mathsf{L}$). They are the first lattice-based public-key ABE schemes supporting uniform models of computation. Previous lattice-based schemes for uniform computation were limited to the secret-key setting or offered only weaker security against bounded collusion.

Lastly, the new primitive of evasive IPFE serves as the lattice-based counterpart of pairing-based IPFE, enabling the application of techniques developed in pairing-based ABE constructions to lattice-based constructions. We believe it is of independent interest and may find other applications.

## 2024/822

* Title: Early Stopping Byzantine Agreement in $(1+\epsilon)\cdot f$ Rounds
* Authors: Fatima Elsheimy, Julian Loss, Charalampos Papamanthou
* [Permalink](https://eprint.iacr.org/2024/822)
* [Download](https://eprint.iacr.org/2024/822.pdf)

### Abstract

In this paper, we present two early stopping Byzantine agreement protocols in the authenticated setting against a corrupt minority $t < n/2$, where $t$ represents the maximum number of malicious parties. Early stopping protocols ensure termination within a number of rounds determined solely by the actual number of malicious nodes $f$ present during execution, irrespective of $t$.

Our first protocol is deterministic and ensures early stopping termination in $ (d+5) \cdot (\lfloor f/d \rfloor +3)$ rounds, where $d$ is a fixed constant. For example, for all $d\ge 6$, our protocol runs in at most $(1+\epsilon )\cdot f$ rounds (where $0<\epsilon<1$), improving (for large $f$) upon the best previous early stopping deterministic broadcast protocol by Perry and Toueg~\cite{Perry}, which terminates in $min(2f+4,2t+2)$ rounds. Additionally, our second protocol is randomized, ensuring termination in an expected constant number of rounds and achieving early stopping in $(d+9) \cdot (\lfloor f/d \rfloor +2)$ rounds in the worst case. This marks a significant improvement over a similar result by Goldreich and Petrank[GOLDREICH1990], which always requires an expected constant number of rounds and $O(t)$ rounds in the worst case, i.e., does not have the early stopping property.

## 2024/823

* Title: Batched Distributed Point Function from Sparse LPN and Homomorphic Secret Sharing
* Authors: Lucas Piske, Jaspal Singh, Ni Trieu
* [Permalink](https://eprint.iacr.org/2024/823)
* [Download](https://eprint.iacr.org/2024/823.pdf)

### Abstract

A function secret sharing (FSS) scheme ($\mathsf{gen},\mathsf{eval}$) for a class of programs $\mathcal{F}$ allows a dealer to secret share any function $f \in \mathcal{F}$, such that each function share hides the function, and the shares can be used to non-interactively compute additive shares of $f(x)$ for any input $x$. All FSS related applications often requires the dealer to generate and share secret sharings for a batch of functions.
We initiate the study of batched function secret sharing - where the objective is to secret share a set of functions from the class $\mathcal{F}$ while minimizing the size of the collection of FSS keys.

We use standard homomorphic secret sharing (HSS) schemes, variant of the Learning with Parity Noise assumption and the Quadratic Residuosity assumption to construct batched FSS schemes for point functions with single-bit and multi-bit output. Our scheme is asymptotically superior than naively batching state of the art FSS schemes for point functions. Concretely our batch key sizes are smaller by a factor of $3-80\times$ as batch size is increased from $2^{13}$ to $2^{19}$. Although our protocol relies on public key operations, it exhibits inefficiency in a LAN setting. However, it demonstrates up to a 120-fold improvement in a WAN setting with slow network bandwidth.

As a building block in our protocols, we introduce a new HSS ciphertext compression algorithm, that can decompress a short compressed ciphertext to give low noise ciphertexts of array of input message bits. This primitive might be of independent interest for other HSS related applications.

## 2024/824

* Title: Improved Meet-LWE Attack via Ternary Trees
* Authors: Eunmin Lee, Joohee Lee, Yuntao Wang
* [Permalink](https://eprint.iacr.org/2024/824)
* [Download](https://eprint.iacr.org/2024/824.pdf)

### Abstract

The Learning with Errors (LWE) problem with its variants over structured lattices has been widely exploited in efficient post-quantum cryptosystems. Recently, May suggests the Meet-LWE attack, which poses a significant advancement in the line of work on the Meet-in-the-Middle approach to analyze LWE with ternary secrets.

In this work, we generalize and extend the idea of Meet-LWE by introducing ternary trees, which result in diverse representations of the secrets. More precisely, we split the secrets into three pieces with the same dimension and expand them into a ternary tree to leverage the increased representations to improve the overall attack complexity. We carefully analyze and optimize the time and memory costs of our attack algorithm exploiting ternary trees, and compare them to those of the Meet-LWE attack. With asymptotic and non-asymptotic comparisons, we observe that our attack provides improved estimations for all parameter settings, including those of the practical post-quantum schemes, compared to the Meet-LWE attack. We also evaluate the security of the Round 2 candidates of the KpqC competition which aims to standardize post-quantum public key cryptosystems in the Republic of Korea, and report that the estimated complexities for our attack applied to SMAUG-T are lower than the claimed for some of the recommended parameters.