[digest] 2024 Week 22

Liste des GroupesRevenir à s crypt 
Sujet : [digest] 2024 Week 22
De : noreply (at) *nospam* example.invalid (IACR ePrint Archive)
Groupes : sci.crypt
Date : 03. Jun 2024, 03:22:42
Autres entêtes
Organisation : A noiseless patient Spider
Message-ID : <JbQx8nGmQMGHvOiqrsy7C4PBUB5i6oxj@eprint.iacr.org.invalid>
## In this issue

1. [2023/1381] Sometimes You Can’t Distribute Random-Oracle-Based ...
2. [2023/1542] Don’t Forget Pairing-Friendly Curves with Odd Prime ...
3. [2024/347] The Algebraic Freelunch: Efficient Gröbner Basis ...
4. [2024/358] Stateless Deterministic Multi-Party EdDSA ...
5. [2024/747] Scaling Lattice Sieves across Multiple Machines
6. [2024/757] Formal Definition and Verification for Combined ...
7. [2024/767] Bootstrapping Bits with CKKS
8. [2024/825] KHAN Encryption Algorithm: Leveraging Full Reptend ...
9. [2024/826] Securing Lightning Channels against Rational Miners
10. [2024/827] Multivariate Multi-Polynomial Commitment and its ...
11. [2024/828] Post-quantum XML and SAML Single Sign-On
12. [2024/829] Multi-Server Doubly Efficient PIR
13. [2024/830] How (not) to Build Quantum PKE in Minicrypt
14. [2024/831] Tight Characterizations for Preprocessing against ...
15. [2024/832] Hamming Weight Proofs of Proximity with One-Sided Error
16. [2024/833] INDIANA - Verifying (Random) Probing Security ...
17. [2024/834] Fine-Grained Non-Interactive Key Exchange, Revisited
18. [2024/835] Provable security against decryption failure ...
19. [2024/836] The Round Complexity of Proofs in the Bounded ...
20. [2024/837] Fully Secure MPC and zk-FLIOP Over Rings: New ...
21. [2024/838] Verifiable Secret Sharing from Symmetric Key ...
22. [2024/839] Almost optimal succinct arguments for Boolean ...
23. [2024/840] Batching-Efficient RAM using Updatable Lookup Arguments
24. [2024/841] Two generalizations of almost perfect nonlinearity
25. [2024/842] Computation Efficient Structure Aware PSI From ...
26. [2024/843] Formally verifying Kyber Episode V: Machine-checked ...
27. [2024/844] Finding Dense Submodules with Algebraic Lattice ...
28. [2024/845] PathGES: An Efficient and Secure Graph Encryption ...
29. [2024/846] Distributed Asynchronous Remote Key Generation
30. [2024/847] More Efficient Approximate $k$-wise Independent ...
31. [2024/848] How (Not) to Simulate PLONK
32. [2024/849] Fast, Lagre Scale Dimensionality Reduction Schemes ...
33. [2024/850] Constant-Round Arguments for Batch-Verification and ...
34. [2024/851] On the parallelization of square-root Vélu's formulas
35. [2024/852] Breaking Indistinguishability with Transfer ...
36. [2024/853] Practical q-IND-CPA-D-Secure Approximate ...
37. [2024/854] Simulation-Extractable KZG Polynomial Commitments ...
38. [2024/855] Securing the Future of GenAI: Policy and Technology
39. [2024/856] Indistinguishability Obfuscation from Bilinear Maps ...
40. [2024/857] Speeding up Preimage and Key-Recovery Attacks with ...
41. [2024/858] Ascon-Keccak AEAD Algorithm

## 2023/1381

* Title: Sometimes You Can’t Distribute Random-Oracle-Based Proofs
* Authors: Jack Doerner, Yashvanth Kondi, Leah Namisa Rosenbloom
* [Permalink](https://eprint.iacr.org/2023/1381)
* [Download](https://eprint.iacr.org/2023/1381.pdf)

### Abstract

We investigate the conditions under which straight-line extractable NIZKs in the random oracle model (i.e. without a CRS) permit multiparty realizations that are black-box in the same random oracle. We show that even in the semi-honest setting, any MPC protocol to compute such a NIZK cannot make black-box use of the random oracle or a hash function instantiating it if security against all-but-one corruptions is desired, unless the number of queries made by the verifier to the oracle grows linearly with the number of parties. This presents a fundamental barrier to constructing efficient protocols to securely distribute the computation of NIZKs (and signatures) based on MPC-in-the-head, PCPs/IOPs, and sigma protocols compiled with transformations due to Fischlin, Pass, or Unruh.

When the adversary is restricted to corrupt only a constant fraction of parties, we give a positive result by means of a tailored construction, which demonstrates that our impossibility does not extend to weaker corruption models in general.



## 2023/1542

* Title: Don’t Forget Pairing-Friendly Curves with Odd Prime Embedding Degrees
* Authors: Yu Dai, Fangguo Zhang, Chang-an Zhao
* [Permalink](https://eprint.iacr.org/2023/1542)
* [Download](https://eprint.iacr.org/2023/1542.pdf)

### Abstract

Pairing-friendly curves with odd prime embedding degrees
at the 128-bit security level, such as BW13-310 and BW19-286, sparked
interest in the field of public-key cryptography as small sizes of the prime
fields. However, compared to mainstream pairing-friendly curves at the
same security level, i.e., BN446 and BLS12-446, the performance of pairing computations on BW13-310 and BW19-286 is usually considered
ineffcient. In this paper we investigate high performance software implementations of pairing computation on BW13-310 and corresponding
building blocks used in pairing-based protocols, including hashing, group
exponentiations and membership testings. Firstly, we propose effcient
explicit formulas for pairing computation on this curve. Moreover, we
also exploit the state-of-art techniques to implement hashing in G1 and
G2, group exponentiations and membership testings. In particular, for
exponentiations in G2 and GT , we present new optimizations to speed
up computational effciency. Our implementation results on a 64-bit processor show that the gap in the performance of pairing computation between BW13-310 and BN446 (resp. BLS12-446) is only up to 4.9% (resp.
26%). More importantly, compared to BN446 and BLS12-446, BW13-
310 is about 109.1% − 227.3%, 100% − 192.6%, 24.5% − 108.5% and
68.2% − 145.5% faster in terms of hashing to G1, exponentiations in G1
and GT , and membership testing for GT , respectively. These results reveal that BW13-310 would be an interesting candidate in pairing-based
cryptographic protocols.



## 2024/347

* Title: The Algebraic Freelunch: Efficient Gröbner Basis Attacks Against Arithmetization-Oriented Primitives
* Authors: Augustin Bariant, Aurélien Boeuf, Axel Lemoine, Irati Manterola Ayala, Morten Øygarden, Léo Perrin, Håvard Raddum
* [Permalink](https://eprint.iacr.org/2024/347)
* [Download](https://eprint.iacr.org/2024/347.pdf)

### Abstract

In this paper, we present a new type of algebraic attack that applies to many recent arithmetization-oriented families of permutations, such as those used in Griffin, Anemoi, ArionHash, and XHash8, whose security relies on the hardness of the constrained-input constrained-output (CICO) problem. We introduce the FreeLunch approach: the monomial ordering is chosen so that the natural polynomial system encoding the CICO problem already is a Gröbner basis. In addition, we present a new dedicated resolution algorithm for FreeLunch systems of complexity lower than applicable state-of-the-art FGLM algorithms.
We show that the FreeLunch approach challenges the security of fullround instances of Anemoi, Arion and Griffin. We confirm these theoretical results with experimental results on those three permutations. In particular, using the FreeLunch attack combined with a new technique to bypass 3 rounds of Griffin, we recover a CICO solution for 7 out of 10 rounds of Griffin in less than four hours on one core of AMD EPYC 7352 (2.3GHz).



## 2024/358

* Title: Stateless Deterministic Multi-Party EdDSA Signatures with Low Communication
* Authors: Qi Feng, Kang Yang, Kaiyi Zhang, Xiao Wang, Yu Yu, Xiang Xie, Debiao He
* [Permalink](https://eprint.iacr.org/2024/358)
* [Download](https://eprint.iacr.org/2024/358.pdf)

### Abstract

EdDSA, standardized by both IRTF and NIST, is a variant of the well-known Schnorr signature scheme based on Edwards curves, benefitting from stateless and deterministic derivation of nonces (i.e., it does not require a reliable source of randomness or state continuity). Recently, NIST called for multi-party threshold EdDSA signatures in one mode of verifying such nonce derivation via zero-knowledge (ZK) proofs.  However, it is challenging to translate the stateless and deterministic benefits of EdDSA to the multi-party threshold setting, as no fresh randomness is available for signing the same message. In this paper, we present a new stateless and deterministic multi-party EdDSA protocol in the full-threshold setting, tolerating all-but-one malicious corruptions. Compared to the state-of-the-art multi-party EdDSA protocol by Garillot et al. (Crypto'21), we improve the communication cost by a factor of 56x and have the same three rounds, at the cost of increasing the computational cost by about 2.25x. We adopt information-theoretic message authenticated codes (IT-MACs) in the multi-verifier setting to authenticate values, and convert them from a Boolean domain to an arithmetic domain by refining multi-verifier extended doubly-authenticated bits (\edabits). We adopt pseudorandom correlation function (\PCF) to generate IT-MACs statelessly and deterministically. Together, we design a multi-verifier zero-knowledge (MVZK) protocol to derive nonces statelessly and deterministically.



## 2024/747

* Title: Scaling Lattice Sieves across Multiple Machines
* Authors: Martin R. Albrecht, Joe Rowell
* [Permalink](https://eprint.iacr.org/2024/747)
* [Download](https://eprint.iacr.org/2024/747.pdf)

### Abstract

Lattice sieves are algorithms for finding short vectors in lattices. We present an implementation of two such sieves – known as “BGJ1” and “BDGL” in the literature – that scales across multiple servers (with varying success). This class of algorithms requires exponential memory which had put into question their ability to scale across sieving nodes. We discuss our architecture and optimisations and report experimental evidence of the efficiency of our approach.



## 2024/757

* Title: Formal Definition and Verification for Combined Random Fault and Random Probing Security
* Authors: Sonia Belaid, Jakob Feldtkeller, Tim Güneysu, Anna Guinet, Jan Richter-Brockmann, Matthieu Rivain, Pascal Sasdrich, Abdul Rahman Taleb
* [Permalink](https://eprint.iacr.org/2024/757)
* [Download](https://eprint.iacr.org/2024/757.pdf)

### Abstract

In our highly digitalized world, an adversary is not constrained to purely digital attacks but can monitor or influence the physical execution environment of a target computing device. Such side-channel or fault-injection analysis poses a significant threat to otherwise secure cryptographic implementations. Hence, it is important to consider additional adversarial capabilities when analyzing the security of cryptographic implementations besides the default black-box model. For side-channel analysis, this is done by providing the adversary with knowledge of some internal values, while for fault-injection analysis the capabilities of the adversaries include manipulation of some internal values.

In this work, we extend probabilistic security models for physical attacks, by introducing a general random probing model and a general random fault model to capture arbitrary leakage and fault distributions, as well as the combination of these models.  Our aim is to enable a more accurate modeling of low-level physical effects. We then analyze important properties, such as the impact of adversarial knowledge on faults and compositions, and provide tool-based formal verification methods that allow the security assessment of design components. These methods are introduced as extension of previous tools VERICA and IronMask which are implemented, evaluated and compared.



## 2024/767

* Title: Bootstrapping Bits with CKKS
* Authors: Youngjin Bae, Jung Hee Cheon, Jaehyung Kim, Damien Stehlé
* [Permalink](https://eprint.iacr.org/2024/767)
* [Download](https://eprint.iacr.org/2024/767.pdf)

### Abstract

The Cheon-Kim-Kim-Song (CKKS) fully homomorphic encryption scheme is designed to efficiently perform computations on real numbers in an encrypted state. Recently, Drucker et al. [J. Cryptol.] proposed an efficient  strategy to use CKKS in a black-box manner to perform computations on binary data.

In this work, we introduce several CKKS bootstrapping algorithms designed specifically for ciphertexts encoding binary data. Crucially, the new CKKS bootstrapping algorithms enable to bootstrap ciphertexts containing the binary data in the most significant bits. First, this allows to decrease the moduli used in bootstrapping, saving a larger share of the modulus budget for non-bootstrapping operations.

In particular, we obtain full-slot bootstrapping in ring degree $2^{14}$ for the first time. Second, the ciphertext format is compatible with the one used in the DM/CGGI fully homomorphic encryption schemes. Interestingly, we may combine our CKKS bootstrapping algorithms for bits with the fast ring packing technique from Bae et al. [CRYPTO'23]. This leads to a new bootstrapping algorithm for DM/CGGI that outperforms the state-of-the-art approaches when the number of bootstraps to be performed simultaneously is in the low hundreds.



## 2024/825

* Title: KHAN Encryption Algorithm: Leveraging Full Reptend Primes
* Authors: Ayaz Khan
* [Permalink](https://eprint.iacr.org/2024/825)
* [Download](https://eprint.iacr.org/2024/825.pdf)

### Abstract

The Keyed Hashing and Asymmetric Nonce (KHAN) encryption algorithm is a novel cryptographic scheme that utilizes the unique properties of full reptend prime numbers. This paper details the algorithm, its theoretical foundations, and the rigorous proofs of its security properties. By leveraging the characteristics of cyclic sequences derived from full reptend primes, KHAN provides robust encryption with high resistance to cryptanalytic attacks.



## 2024/826

* Title: Securing Lightning Channels against Rational Miners
* Authors: Lukas Aumayr, Zeta Avarikioti, Matteo Maffei, Subhra Mazumdar
* [Permalink](https://eprint.iacr.org/2024/826)
* [Download](https://eprint.iacr.org/2024/826.pdf)

### Abstract

Payment channel networks (e.g., the Lightning Network in Bitcoin) constitute one of the most popular scalability solutions for blockchains. Their safety relies on parties being online to detect fraud attempts on-chain and being able to timely react by publishing certain transactions on-chain. However, a cheating party may bribe miners in order to censor those transactions, resulting in loss of funds for the cheated party: these attacks are known in the literature as timelock-bribing attacks. In this work, we present the first channel construction that does not require parties to be online and, at the same time, is resistant to time-lock bribing attacks.

We start by proving for the first time that Lightning channels are secure against timelock bribing attacks in the presence of rational channel parties under the assumption that these parties constantly monitor the mempool and never deplete the channel in one direction. The latter underscores the importance of keeping a coin reserve in each channel as implemented in the Lightning Network, albeit for different reasons.
We show, however, that the security of the Lightning Network against Byzantine channel parties does not carry over to a setting in which miners are rational and accept timelock bribes.

Next, we introduce CRAB, the first Lightning-compatible channel construction that provides security against Byzantine channel parties and rational miners. CRAB leverages miners' incentives to safeguard the channel, thereby also forgoing the unrealistic assumption of channel parties constantly monitoring the mempool.

Finally, we show how our construction can be refined to eliminate the major assumption behind payment channels, i.e., the need for online participation. To that end, we present Sleepy CRAB the first provably secure channel construction under rational miners that enables participants to go offline indefinitely. We also provide a proof-of-concept implementation of Sleepy CRAB and evaluate its cost in Bitcoin, thereby demonstrating its practicality.



## 2024/827

* Title: Multivariate Multi-Polynomial Commitment and its Applications
* Authors: Xiao Yang, Chengru Zhang, Mark Ryan, Gao Meng
* [Permalink](https://eprint.iacr.org/2024/827)
* [Download](https://eprint.iacr.org/2024/827.pdf)

### Abstract

We introduce and formally define Multivariate Multi-Polynomial (MMP) commitment, a commitment scheme on multiple multivariate polynomials, and illustrate the concept with an efficient construction, which enjoys constant commitment size and logarithmic proof size. We further enhance our MMP scheme to achieve the zero-knowledge property.

Additionally, combined with a novel zero-knowledge range proof for Pedersen subvector commitment, we present a Zero-Knowledge Range Proof (ZKRP) for MMP commitment.

We present two sample applications. Firstly, our MMP commitment can be used for efficient aggregation of SNARK based on multivariate polynomial commitments. As a showcase,  we apply MMP commitment to HyperPlonk and refer to this variant of HyperPlonk as aHyperPlonk.  For $k$ instances, each with circuit size $n$, the communication and verification complexity is reduced from $O(k \cdot  \log n)$ to $O(\log k + \log n)$, while the prover complexity remains the same. Secondly,  we propose a novel zero-knowledge proof for vehicle GPS traces based on  ZKRP for MMP, which allows vehicle owners to prove if a vehicle has/hasn't passed through some location during a specific time interval.



## 2024/828

* Title: Post-quantum XML and SAML Single Sign-On
* Authors: Johannes Müller, Jan Oupický
* [Permalink](https://eprint.iacr.org/2024/828)
* [Download](https://eprint.iacr.org/2024/828.pdf)

### Abstract

Extensible Markup Language (XML) is one of the most popular serialization languages. Since many security protocols are built using XML, it also provides cryptographic functionality. A central framework in this area is the Security Assertion Markup Language (SAML). This standard is one of the most widely used options for implementing Single Sign-On (SSO), which allows users to authenticate to different service providers using the credentials from a single identity provider. Like all other security protocols currently in use, the security and privacy of XML-based frameworks such as SAML is threatened by the development of increasingly powerful quantum computers. In fact, future attackers with access to scalable quantum computers will be able to break the currently used cryptographic building blocks and thus undermine the security of the SAML SSO to illegally access sensitive private information. Post-quantum cryptography algorithms have been developed to protect against such quantum attackers. While many security protocols have been migrated into the quantum age by using post-quantum cryptography, no such solutions for XML and the security protocols based on it have been developed, let alone tested. We make the following contributions to fill this gap. We have designed post-quantum solutions for the cryptographic building blocks in XML and integrated them into the SAML SSO protocol. We implemented our solutions in the OpenSAML, Apache Santuario, and BouncyCastle libraries and extensively tested their performance for various post-quantum instantiations. As a result, we have created a comprehensive and solid foundation for post-quantum XML and post-quantum SAML SSO migration.



## 2024/829

* Title: Multi-Server Doubly Efficient PIR
* Authors: Arthur Lazzaretti, Zeyu Liu, Ben Fisch, Charalampos Papamanthou
* [Permalink](https://eprint.iacr.org/2024/829)
* [Download](https://eprint.iacr.org/2024/829.pdf)

### Abstract

Doubly Efficient Private Information Retrieval (DEPIR) pertains to a Private Information Retrieval (PIR) scheme with both near-linear server-side preprocessing time and sublinear query time. Very recently, Lin et al. (STOC '23) devised the first single-server DEPIR scheme from standard assumptions. However, their work left one major question open: can we build a DEPIR scheme in the multi-server setting, without relying on heavy cryptographic machinery?
   
In this work, we propose the first doubly efficient information-theoretic PIR scheme, in the multi-server setting. For a database of size $N$, our scheme allows servers to answer an infinite number of client queries in $N^{o(1)}$ time, after a single preprocessing phase which takes $N^{1+o(1)}$ time. Our result is only a $N^{o(1)}$ factor from the lower bound proven by Persiano and Yeo (SODA '22) for this setting.
   
In addition, we devise a second information-theoretic PIR scheme which pushes the state of the art for the setting where the number of servers is more constrained. It achieves equally fast query times as our first scheme above, and a preprocessing time of $N^{2+o(1)}$.



## 2024/830

* Title: How (not) to Build Quantum PKE in Minicrypt
* Authors: Longcheng Li, Qian Li, Xingjian Li, Qipeng Liu
* [Permalink](https://eprint.iacr.org/2024/830)
* [Download](https://eprint.iacr.org/2024/830.pdf)

### Abstract

The seminal work by Impagliazzo and Rudich (STOC'89) demonstrated the impossibility of constructing classical public key encryption (PKE) from one-way functions (OWF) in a black-box manner. However, the question remains: can quantum PKE (QPKE) be constructed from quantumly secure OWF?

A recent line of work has shown that it is indeed possible to build QPKE from OWF, but with one caveat --- they rely on quantum public keys, which cannot be authenticated and reused. In this work, we re-examine the possibility of perfect complete QPKE in the quantum random oracle model (QROM), where OWF exists.

Our first main result: QPKE with classical public keys, secret keys and ciphertext, does not exist in the QROM, if the key generation only makes classical queries.
Therefore, a necessary condition for constructing such QPKE from OWF is to have the key generation classically ``un-simulatable’’. Previous discussions (Austrin~et al. CRYPTO'22) on the impossibility of QPKE from OWF rely on a seemingly strong conjecture. Our work makes a significant step towards a complete and unconditional quantization of Impagliazzo and Rudich’s results.

Our second main result extends to QPKE with quantum public keys.
The second main result: QPKE with quantum public keys, classical secret keys and ciphertext, does not exist in the QROM, if the key generation only makes classical queries and the quantum public key is either pure or ``efficiently clonable''.
The result is tight due to all existing QPKEs constructions. Our result further gives evidence on why existing QPKEs lose reusability.

To achieve these results, we use a novel argument based on conditional mutual information and quantum Markov chain by Fawzi and Renner (Communications in Mathematical Physics). We believe the techniques used in the work will find other usefulness in separations in quantum cryptography/complexity.



## 2024/831

* Title: Tight Characterizations for Preprocessing against Cryptographic Salting
* Authors: Fangqi Dong, Qipeng Liu, Kewen Wu
* [Permalink](https://eprint.iacr.org/2024/831)
* [Download](https://eprint.iacr.org/2024/831.pdf)

### Abstract

Cryptography often considers the strongest yet plausible attacks in the real world. Preprocessing (a.k.a. non-uniform attack) plays an important role in both theory and practice: an efficient online attacker can take advantage of advice prepared by a time-consuming preprocessing stage.

Salting is a heuristic strategy to counter preprocessing attacks by feeding a small amount of randomness to the cryptographic primitive.
We present general and tight characterizations of preprocessing against cryptographic salting, with upper bounds matching the advantages of the most intuitive attack.
Our result quantitatively strengthens the previous work by Coretti, Dodis, Guo, and Steinberger (EUROCRYPT'18).
Our proof exploits a novel connection between the non-uniform security of salted games and direct product theorems for memoryless algorithms.

For quantum adversaries, we give similar characterizations for property finding games, resolving an open problem of the quantum non-uniform security of salted collision resistant hash by Chung, Guo, Liu, and Qian (FOCS'20).
Our proof extends the compressed oracle framework of Zhandry (CRYPTO'19) to prove quantum strong direct product theorems for property finding games in the average-case hardness.



## 2024/832

* Title: Hamming Weight Proofs of Proximity with One-Sided Error
* Authors: Gal Arnon, Shany Ben-David, Eylon Yogev
* [Permalink](https://eprint.iacr.org/2024/832)
* [Download](https://eprint.iacr.org/2024/832.pdf)

### Abstract

We provide a wide systematic study of proximity proofs with one-sided error for the Hamming weight problem $\mathsf{Ham}_{\alpha}$ (the language of bit vectors with Hamming weight at least $\alpha$), surpassing previously known results for this problem. We demonstrate the usefulness of the one-sided error property in applications: no malicious party can frame an honest prover as cheating by presenting verifier randomness that leads to a rejection.

We show proofs of proximity for $\mathsf{Ham}_{\alpha}$ with one-sided error and sublinear proof length in three models (MA, PCP, IOP), where stronger models allow for smaller query complexity. For $n$-bit input vectors, highlighting input query complexity, our MA has $O(\mathrm{log} n)$ query complexity, the PCP makes $O(\mathrm{loglog} n)$ queries, and the IOP makes a single input query. The prover in all of our applications runs in expected quasi-linear time.  Additionally, we show that any perfectly complete IP of proximity for $\mathsf{Ham}_{\alpha}$ with input query complexity $n^{1-\epsilon}$ has proof length $\Omega(\mathrm{log} n)$.

Furthermore, we study PCPs of proximity where the verifier is restricted to making a single input query (SIQ). We show that any SIQ-PCP for $\mathsf{Ham}_{\alpha}$ must have a linear proof length, and complement this by presenting a SIQ-PCP with proof length $n+o(n)$.

As an application, we provide new methods that transform PCPs (and IOPs) for arbitrary languages with nonzero completeness error into PCPs (and IOPs) that exhibit perfect completeness. These transformations achieve parameters previously unattained.



## 2024/833

* Title: INDIANA - Verifying (Random) Probing Security through Indistinguishability Analysis
* Authors: Christof Beierle, Jakob Feldtkeller, Anna Guinet, Tim Güneysu, Gregor Leander, Jan Richter-Brockmann, Pascal Sasdrich
* [Permalink](https://eprint.iacr.org/2024/833)
* [Download](https://eprint.iacr.org/2024/833.pdf)

### Abstract

Despite masking being a prevalent protection against passive side-channel attacks, implementing it securely in hardware remains a manual, challenging,  and error-prone process.

This paper introduces INDIANA, a comprehensive security verification tool for hardware masking. It provides a hardware verification framework, enabling a complete analysis of simulation-based security in the glitch-extended probing model, with cycle-accurate estimations for leakage probabilities in the random probing model.
Notably, INDIANA is the first framework to analyze arbitrary masked circuits in both models, even at the scale of full SPN cipher rounds (e.g., AES), while delivering exact verification results.

To attain precise and extensive verifiability, we introduce a partitionable probing distinguisher that enables rapid verification of probe tuples, outperforming state-of-the-art methods based on statistical independence. Most interestingly, our approach inherently facilitates extensions to the random probing model by leveraging Fast Fourier-Hadamard Transformations (FFTs).

Benchmark results show that INDIANA competes effectively with leading probing model verification tools, such as maskVerif and VERICA. Notably, INDIANA the first tool that is capable to provide cycle-accurate estimations of random probing leakage probabilities for large-scale masked circuits.



## 2024/834

* Title: Fine-Grained Non-Interactive Key Exchange, Revisited
* Authors: Balthazar Bauer, Geoffroy Couteau, Elahe Sadeghi
* [Permalink](https://eprint.iacr.org/2024/834)
* [Download](https://eprint.iacr.org/2024/834.pdf)

### Abstract

We revisit the construction of multiparty non-interactive key-exchange protocols with fine-grained security, which was recently studied in (Afshar et al., Eurocrypt 2023). Their work introduced a 4-party non-interactive key exchange with quadratic hardness, and proved it secure in Shoup's generic group model. This positive result was complemented with a proof that $n$-party non-interactive key exchange with superquadratic security cannot exist in Maurer's generic group model, for any $n\geq 3$. Because Shoup's model is stronger than Maurer's model, this leaves a gap between the positive and the negative result, and their work left as an open question the goal of closing this gap, and of obtaining fine-grained non-interactive key exchange without relying on idealized models.

    In this work, we make significant progress on both questions. We obtain two main results:

 A 4-party non-interactive key exchange protocol with quadratic security gap, assuming the existence of exponentially secure injective pseudorandom generators, and the subexponential hardness of the computational Diffie-Hellman assumption. In addition, our scheme is conceptually simpler, and can be generalized to other settings (with more parties or from other assumptions).

Assuming the existence of non-uniformly secure injective pseudorandom generators with exponential hardness, we further show that our protocol is secure in Maurer's model, albeit with a smaller hardness gap (up to $N^{1.6}$), making progress on filling the gap between the positive and the negative result of (Afshar et al., Eurocrypt 2023). Somewhat intriguingly, proving the security of our scheme in Maurer's idealized model turns out to be significantly harder than proving its security in the standard model.



## 2024/835

* Title: Provable security against decryption failure attacks from LWE
* Authors: Christian Majenz, Fabrizio Sisinni
* [Permalink](https://eprint.iacr.org/2024/835)
* [Download](https://eprint.iacr.org/2024/835.pdf)

### Abstract

In a recent work, Hövelmanns, Hülsing and Majenz introduced a new security proof for the Fujisaki-Okamoto transform in the quantum-accessible random oracle model (QROM) used in post-quantum key encapsulation mechanisms. While having a smaller security loss due to decryption failures present in many constructions, it requires two new security properties of the underlying public-key encryption scheme (PKE).
In this work, we show that one of the properties, Find Failing Plaintexts - Non Generic (FFP-NG) security, is achievable using a relatively efficient LWE-based PKE that does not have perfect correctness. In particular, we show that LWE reduces to breaking FFP-NG security of the PVW scheme, when all LWE errors are discrete Gaussian distributed. The reduction has an arbitrarily small constant multiplicative loss in LWE error size. For the proof, we make use of techniques by Genise, Micciancio, Peikert and Walter to analyze marginal and conditional distributions of sums of discrete Gaussians.



## 2024/836

* Title: The Round Complexity of Proofs in the Bounded Quantum Storage Model
* Authors: Alex B. Grilo, Philippe Lamontagne
* [Permalink](https://eprint.iacr.org/2024/836)
* [Download](https://eprint.iacr.org/2024/836.pdf)

### Abstract

The round complexity of interactive proof systems is a key question of practical and theoretical relevance in complexity theory and cryptography. Moreover, results such as QIP = QIP(3) (STOC'00) show that quantum resources significantly help in such a task.

In this work, we initiate the study of round compression of protocols in the bounded quantum storage model (BQSM). In this model, the malicious parties have a bounded quantum memory and they cannot store the all the qubits that are transmitted in the protocol.

Our main results in this setting are the following:
1. There is a non-interactive (statistical) witness indistinguishable proof for any language in NP (and even QMA) in BQSM in the plain model. We notice that in this protocol, only the memory of the verifier is bounded.
2. Any classical proof system can be compressed in a two-message quantum proof system in BQSM. Moreover, if the original proof system is zero-knowledge, the quantum protocol is zero-knowledge too. In this result, we assume that the prover has bounded memory.

Finally, we give evidence towards the "tightness" of our results. First, we show that NIZK in the plain model against BQS adversaries is unlikely with standard techniques. Second, we prove that without the BQS model there is no 2-message zero-knowledge quantum interactive proof, even under computational assumptions.



## 2024/837

* Title: Fully Secure MPC and zk-FLIOP Over Rings: New Constructions, Improvements and Extensions
* Authors: Anders Dalskov, Daniel Escudero, Ariel Nof
* [Permalink](https://eprint.iacr.org/2024/837)
* [Download](https://eprint.iacr.org/2024/837.pdf)

### Abstract

We revisit the question of the overhead to achieve full security (i.e., guaranteed output delivery) in secure multiparty computation (MPC). Recent works have closed the gap between full security and semi-honest security, by introducing protocols where the parties first compute the circuit using a semi-honest protocol and then run a verification step with sublinear communication in the circuit size. However, in these works the number of interaction rounds in the verification step is also sublinear in the circuit's size. Unlike communication, the round complexity of the semi-honest execution typically grows with the circuit's depth and not its size. Hence, for large but shallow circuits, this additional number of rounds incurs a significant overhead. Motivated by this gap, we make the following contributions:

1. We present a new MPC framework to obtain full security, compatible with effectively any ring, that has an additive communication overhead of only $O(\log |C|)$, where $|C|$ is the number of multiplication gates in the circuit, and a constant number of additional rounds beyond the underlying semi-honest protocol. Our framework works with any linear secret sharing scheme and relies on a new to utilize the machinery of zero-knowledge fully linear interactive oracle proofs (zk-FLIOP) in a black-box way. We present several instantiations to the building blocks of our compiler, from which we derive concretely efficient protocols in different settings.

2. We present extensions to the zk-FLIOP primitive for very general settings. The first one is for proving statements over potentially non-commutative rings, where the only requirement is that the ring has a large enough set where (1) every element in the set commutes with every element in the ring, and (2) the difference between any two distinct elements is invertible. Our second zk-FLIOP extension is for proving statements over Galois Rings. For these rings, we present concrete improvements on the current state-of-the-art for the case of constant-round proofs, by making use of Reverse Multiplication Friendly Embeddings (RMFEs).



## 2024/838

* Title: Verifiable Secret Sharing from Symmetric Key Cryptography with Improved Optimistic Complexity
* Authors: Ignacio Cascudo, Daniele Cozzo, Emanuele Giunta
* [Permalink](https://eprint.iacr.org/2024/838)
* [Download](https://eprint.iacr.org/2024/838.pdf)

### Abstract

In this paper we propose verifiable secret sharing (VSS) schemes
secure for any honest majority in the synchronous model, and that only use symmetric-key cryptographic tools, therefore having plausibly post-quantum security. Compared to the state-of-the-art scheme with these features (Atapoor et al., Asiacrypt `23), our main improvement lies on the complexity of the ``optimistic'' scenario where the dealer and all but a small number of receivers behave honestly in the sharing phase: in this case, the running time and download complexity (amount of information read) of each honest verifier is polylogarithmic and the total amount of broadcast information by the dealer is logarithmic; all these complexities were linear in the aforementioned work by Atapoor et al. At the same time, we preserve these complexities with respect to the previous work for the ``pessimistic'' case where the dealer or $O(n)$ receivers cheat actively.
The new VSS protocol is of interest in multiparty computations where each party runs one VSS as a dealer, such as distributed key generation protocols.

Our main technical handle is a distributed zero-knowledge proof of low degreeness of a polynomial, in the model of Boneh et al. (Crypto `19) where the statement (in this case the evaluations of the witness polynomial) is distributed among several verifiers, each knowing one evaluation. Using folding techniques similar to FRI (Ben-Sasson et al., ICALP `18) we construct such a proof where each verifier receives polylogarithmic information and runs in polylogarithmic time.



## 2024/839

* Title: Almost optimal succinct arguments for Boolean circuit on RAM
* Authors: Tiancheng Xie, Tianyi Liu
* [Permalink](https://eprint.iacr.org/2024/839)
* [Download](https://eprint.iacr.org/2024/839.pdf)

### Abstract

The significance of succinct zero-knowledge proofs has increased considerably in recent times. However, one of the major challenges that hinder the prover's efficiency is when dealing with Boolean circuits. In particular, the conversion of each bit into a finite field element incurs a blow-up of more than 100x in terms of both memory usage and computation time.

This work focuses on data-parallel Boolean circuits that contain numerous identical sub-circuits. These circuits are widely used in real-world applications, such as proving a large number of hash-preimages in zkEVM and zkBridge. We develop a method for constructing succinct arguments with $2^{-\lambda}$ soundness error and $O(\omega(1)\frac{N}{\log{N}} \log{\log{N}})$ RAM operations, or $O(\frac{N}{\log{N}}\log\log N)$ finite field additions, along with a negligible number of finite field multiplications.

Our approach is based on using the GKR protocol to obtain the succinct argument.



## 2024/840

* Title: Batching-Efficient RAM using Updatable Lookup Arguments
* Authors: Moumita Dutta, Chaya Ganesh, Sikhar Patranabis, Shubh Prakash, Nitin Singh
* [Permalink](https://eprint.iacr.org/2024/840)
* [Download](https://eprint.iacr.org/2024/840.pdf)

### Abstract

RAM (random access memory) is an important primitive in verifiable computation. In this paper, we focus on realizing RAM with efficient batching property, i.e, proving a batch of $m$ updates on a RAM of size $N$ while incurring a cost that is sublinear in $N$. Classical approaches based on Merkle-trees or address ordered transcripts to model RAM correctness are either concretely inefficient, or incur linear overhead in the size of the RAM. Recent works explore cryptographic accumulators based on unknown-order groups (RSA, class-groups) to model the RAM state. While recent RSA accumulator based approaches offer significant improvement over classical methods, they incur linear overhead in the size of the accumulated set to compute witnesses, as well as prohibitive constant overheads.

We realize a batching-efficient RAM with superior asymptotic and concrete costs as compared to existing approaches. Towards this: (i) we build on recent constructions of lookup arguments to allow efficient lookups even in presence of table updates, and (ii) we realize a variant of sub-vector relation addressed in prior works, which we call committed index lookup. We combine the two building blocks to realize batching-efficient RAM with sublinear dependence on size of the RAM. Our construction incurs an amortized proving cost of $\tilde{O}(m\log m + \sqrt{mN})$ for a batch of $m$ updates on a RAM of size $N$. Our results also benefit the recent arguments for sub-vector relation, by enabling them to be efficient in presence of updates to the table. We believe that this is a contribution of independent interest.

We implement our solution to evaluate its concrete efficiency. Our experiments show that it offers significant improvement over existing works on batching-efficient accumulators/RAMs, with a substantially reduced resource barrier.



## 2024/841

* Title: Two generalizations of almost perfect nonlinearity
* Authors: Claude Carlet
* [Permalink](https://eprint.iacr.org/2024/841)
* [Download](https://eprint.iacr.org/2024/841.pdf)

### Abstract

Almost perfect nonlinear (in brief, APN) functions are (so-called vectorial) functions $F: F_2^n\to F_2^n$ playing roles in several domains of information protection, at the intersection of computer science and mathematics. Their definition comes from cryptography and is also related to coding theory.
The cryptographic motivation for studying APN functions is that, when they are used as substitution boxes (S-boxes), ensuring nonlinearity in block ciphers, they contribute optimally to the resistance against differential attacks. Their study has been very active since the 90's, and has posed interesting and difficult mathematical questions, that are still unanswered. \Since the introduction of differential attacks, more recent types of cryptanalyses have been designed, such as integral attacks. No notion about S-boxes has been identified which would play a similar role with respect to integral attacks. In this paper, we introduce and study two generalizations of almost perfect nonlinearity, that directly extend classical characterizations  of APN functions, and are also related to the integral attack. The two resulting notions are significantly different (and behave differently) from differential uniformity, which is a well-known generalization of APNness; they also behave differently from each other, despite the apparent similarity between their definitions. We study the different ways to define them, and on the example of Kasami functions, how difficult they are to achieve. We prove their satisfiability, their monotonicity, their invariance under classical equivalence relations and we characterize them by the Walsh transform.
We begin a study of the multiplicative inverse function (used as a substitution box in the Advanced Encryption Standard and other block ciphers) from the viewpoint of these two notions. In particular, we find a simple expression of the sum of the values taken by this function over affine subspaces of $\mathbb F_{2^n}$ that are not vector subspaces. This formula shows that, in such case, the sum never vanishes (which is a remarkable property of the inverse function).



## 2024/842

* Title: Computation Efficient Structure Aware PSI From Incremental Function Secret Sharing
* Authors: Gayathri Garimella, Benjamin Goff, Peihan Miao
* [Permalink](https://eprint.iacr.org/2024/842)
* [Download](https://eprint.iacr.org/2024/842.pdf)

### Abstract

Structure-Aware Private Set Intersection (sa-PSI), recently introduced by Garimella et al. (Crypto'22), is a PSI variant where Alice's input set $S_A$ has a publicly known structure (for example, interval, ball or union of balls) and Bob's input $S_B$ is an unstructured set of elements. Prior work achieves sa-PSI where the communication cost only scales with the description size of $S_A$ instead of the set cardinality. However, the computation cost remains linear in the cardinality of $S_A$, which could be prohibitively large.

In this work, we present a new semi-honest sa-PSI framework where both computation and communication costs only scale with the description size of $S_A$. Our main building block is a new primitive that we introduce called Incremental Boolean Function Secret Sharing (ibFSS), which is a generalization of FSS that additionally allows for evaluation on input prefixes. We formalize definitions and construct a weak ibFSS for a $d$-dimensional ball with $\ell_\infty$ norm, which may be of independent interest. Independently, we improve spatial hashing techniques (from prior work) when $S_A$ has structure union of $d$-dimensional balls in $(\{0,1\}^u)^d$, each of diameter $\delta$, from $O(u \cdot d \cdot (\log \delta)^d)$ to $O(\log \delta \cdot d)$ in terms of both computation and communication. Finally, we resolve the following open questions from prior work with communication and computation scaling with the description size of the structured set.
- Our PSI framework can handle a union of overlapping structures, while prior work strictly requires a disjoint union.
- We have a new construction that enables Bob with unstructured input $S_B$ to learn the intersection.
- We extend to a richer class of functionalities like structure-aware PSI Cardinality and PSI-Sum of associated values.



## 2024/843

* Title: Formally verifying Kyber Episode V: Machine-checked IND-CCA security and correctness of ML-KEM in EasyCrypt
* Authors: José Bacelar Almeida, Santiago Arranz Olmos, Manuel Barbosa, Gilles Barthe, François Dupressoir, Benjamin Grégoire, Vincent Laporte, Jean-Christophe Léchenet, Cameron Low, Tiago Oliveira, Hugo Pacheco, Miguel Quaresma, Peter Schwabe, Pierre-Yves Strub
* [Permalink](https://eprint.iacr.org/2024/843)
* [Download](https://eprint.iacr.org/2024/843.pdf)

### Abstract

We present a formally verified proof of the correctness and IND-CCA security of ML-KEM, the Kyber-based Key Encapsulation Mechanism (KEM) undergoing standardization by NIST.
The proof is machine-checked in EasyCrypt and it includes:
1) A formalization of the correctness (decryption failure probability) and IND-CPA security  of the Kyber base public-key encryption scheme, following Bos et al. at Euro S&P 2018;
2) A formalization of the relevant variant of the Fujisaki-Okamoto transform in the Random Oracle Model (ROM), which follows closely (but not exactly) Hofheinz, Hovelmanns and Kiltz at TCC 2017;
3) A proof that the IND-CCA security of the ML-KEM specification and its correctness as a KEM follows from the previous results;
4) Two formally verified implementations of ML-KEM written in Jasmin that are provably constant-time, functionally equivalent to the ML-KEM specification and, for this reason, inherit the provable security guarantees established in the previous points.
The top-level theorems give self-contained concrete bounds for the correctness and security of MLKEM down to (a variant of) Module-LWE. We discuss how they are built modularly by leveraging various EasyCrypt features.



## 2024/844

* Title: Finding Dense Submodules with Algebraic Lattice Reduction
* Authors: Alexander Karenin, Elena Kirshanova
* [Permalink](https://eprint.iacr.org/2024/844)
* [Download](https://eprint.iacr.org/2024/844.pdf)

### Abstract

We prove an algebraic analogue of Pataki-Tural lemma (Pataki-Tural, arXiv:0804.4014, 2008) -- the main tool in analysing the so-called overstretched regime of NTRU.
    Our result generalizes this lemma from Euclidean lattices to modules over any number field enabling us to look at NTRU as rank-2 module over cyclotomic number fields with a rank-1 dense submodule generated by the NTRU secret key.
   
    For Euclidean lattices, this overstretched regime occurs for large moduli $q$ and enables to detect a dense sublattice in NTRU lattices leading to faster NTRU key recovery. We formulate an algebraic version of this event, the so-called Dense Submodule Discovery (DSD) event, and heuristically predict under which conditions this event happens. For that, we formulate an algebraic version of the Geometric Series Assumption -- an heuristic tool that describes the behaviour of algebraic lattice reduction algorithms. We verify this assumption by implementing an algebraic LLL -- an analog of classical LLL lattice reduction that operates on the module level. Our experiments verify the introduced heuristic, enabling us to predict the algebraic DSD event.



## 2024/845

* Title: PathGES: An Efficient and Secure Graph Encryption Scheme for Shortest Path Queries
* Authors: Francesca Falzon, Esha Ghosh, Kenneth G. Paterson, Roberto Tamassia
* [Permalink](https://eprint.iacr.org/2024/845)
* [Download](https://eprint.iacr.org/2024/845.pdf)

### Abstract

The increasing importance of graph databases and cloud storage services prompts the study of private queries on graphs. We propose PathGES, a graph encryption scheme (GES) for single-pair shortest path queries. PathGES is efficient and mitigates the state-of-the-art attack by Falzon and Paterson (2022) on the GES by Ghosh, Kamara, and Tamassia (2021), while only incurring an additional logarithmic factor in storage overhead. PathGES leverages a novel data structure that minimizes leakage and server computation.


We generalize what it means for one leakage function to leak less than another by defining a relation with respect to a family of query sequences and show that our scheme provably leaks less than the GKT scheme when all queries have been issued. We complement our security proof with a cryptanalysis that demonstrates an information-theoretic gap in the size of the query reconstruction space of our scheme as compared to the GKT scheme and provide concrete examples of the gap for several graph families. Our prototype implementation of PathGES is efficient in practice for real-world social network and geographic data sets. In comparison with the GKT scheme, PathGES has on average the same response size and up to 1.5$\times$ faster round-trip query time.



## 2024/846

* Title: Distributed Asynchronous Remote Key Generation
* Authors: Mark Manulis, Hugo Nartz
* [Permalink](https://eprint.iacr.org/2024/846)
* [Download](https://eprint.iacr.org/2024/846.pdf)

### Abstract

Asynchronous Remote Key Generation (ARKG) is a primitive introduced by Frymann et al. at ACM CCS 2020. It enables a sender to generate a new public key $pk'$ for a receiver ensuring only it can, at a later time, compute the corresponding private key sk'. These key pairs are indistinguishable from freshly generated ones and can be used in various public-key cryptosystems such as digital signatures and public-key encryption. ARKG has been explored for applications in WebAuthn credential backup and delegation, as well as for enhancing receiver privacy via stealth addresses.

In this paper, we introduce distributed ARKG (dARKG) aiming to provide similar security properties in a distributed setting. Here, a sender generates $pk'$ for a group of $n$ receivers and the corresponding $sk'$ can only be computed by any sub-group of size $t\leq n$. This introduces threshold-based access protection for $sk'$, enabling for instance a set of proxies to jointly access a WebAuthn account or claim blockchain funds.

We construct dARKG using one-round publicly verifiable asymmetric key agreement, called 1PVAKA, a new primitive formalized in this work.
Unlike traditional distributed key generation protocols where users interact with one another, 1PVAKA is asynchronous and allows a third party to verify and generate a public key from users' outputs.

We discuss 1PVAKA and dARKG instantiations tailored for use with bilinear groups and demonstrate practicality with implementation and performance analysis for the BLS12-381 curve.



## 2024/847

* Title: More Efficient Approximate $k$-wise Independent Permutations from Random Reversible Circuits via log-Sobolev Inequalities
* Authors: Lucas Gretta, William He, Angelos Pelecanos
* [Permalink](https://eprint.iacr.org/2024/847)
* [Download](https://eprint.iacr.org/2024/847.pdf)

### Abstract

We prove that the permutation computed by a reversible circuit with $\widetilde{O}(nk\cdot \log(1/\epsilon))$ random $3$-bit gates is $\epsilon$-approximately $k$-wise independent. Our bound improves on currently known bounds in the regime when the approximation error $\epsilon$ is not too small. We obtain our results by analyzing the log-Sobolev constants of appropriate Markov chains rather than their spectral gaps.



## 2024/848

* Title: How (Not) to Simulate PLONK
* Authors: Marek Sefranek
* [Permalink](https://eprint.iacr.org/2024/848)
* [Download](https://eprint.iacr.org/2024/848.pdf)

### Abstract

PLONK is a zk-SNARK system by Gabizon, Williamson, and Ciobotaru with proofs of constant size (0.5 KB) and sublinear verification time. Its setup is circuit-independent supporting proofs of arbitrary statements up to a certain size bound.

Although deployed in several real-world applications, PLONK's zero-knowledge property had only been argued informally. Consequently, we were able to find and fix a vulnerability in its original specification, leading to an update of PLONK in eprint version 20220629:105924.

In this work, we construct a simulator for the patched version of PLONK and prove that it achieves statistical zero knowledge. Furthermore, we give an attack on the previous version of PLONK showing that it does not even satisfy the weaker notion of (statistical) witness indistinguishability.



## 2024/849

* Title: Fast, Lagre Scale Dimensionality Reduction Schemes Based on CKKS
* Authors: Haonan Yuan, Wenyuan Wu, Jingwei Chen
* [Permalink](https://eprint.iacr.org/2024/849)
* [Download](https://eprint.iacr.org/2024/849.pdf)

### Abstract

The proliferation of artificial intelligence and big data has resulted in a surge in data demand and increased data dimensionality. This escalation has consequently heightened the costs associated with storage and processing. Concurrently, the confidential nature of data collected by various institutions, which cannot be disclosed due to personal privacy concerns, has exacerbated the challenges associated with data analysis and machine learning model training. Therefore, designing a secure and efficient high-dimensional data reduction method that supports multi-party joint participation becomes critical to solving these problems.

This paper proposes a novel homomorphic encryption dimensionality reduction scheme (HE-DR) based on CKKS, which modifies the Rank-Revealing (RR) method to make it more applicable to fully homomorphic encryption, thereby achieving fast and secure dimension reduction for high-dimensional data. Compared to traditional homomorphic encryption dimensionality reduction schemes, our approach does not transmit the user’s original data to other participants in any format (Ciphertext or Plaintext). Moreover, our method's computational efficiency is nearly $60-200$ times faster than similar algorithms, and the communication overhead is only $1/3$ of theirs. Finally, we have shown that our proposed scheme can preserve its computational efficiency and accuracy even when dealing with high-dimensional data. As dimensionality escalates, the ratio of ciphertext to plaintext computational efficiency plateaus at approximately 5 times, while the computational error (distance between subspaces) remains around $1e^{-11}$



## 2024/850

* Title: Constant-Round Arguments for Batch-Verification and Bounded-Space Computations from One-Way Functions
* Authors: Noga Amit, Guy N. Rothblum
* [Permalink](https://eprint.iacr.org/2024/850)
* [Download](https://eprint.iacr.org/2024/850.pdf)

### Abstract

What are the minimal cryptographic assumptions that suffice for constructing efficient argument systems, and for which tasks? Recently, Amit and Rothblum [STOC 2023] showed that one-way functions suffice for constructing constant-round arguments for bounded-depth computations. In this work we ask: what other tasks have efficient argument systems based only on one-way functions? We show two positive results:

First, we construct a new argument system for batch-verification of $k$ $UP$ statements ($NP$ statements with a unique witness) for witness relations that are verifiable in depth $D$. 
Taking $M$ to be the length of a single witness, the communication complexity is $O(\log k) \cdot  (M + k \cdot D \cdot n^{\sigma})$, where $\sigma > 0$ is an arbitrarily small constant. In particular, the communication is quasi-linear in the length of a single witness, so long as ${k < M / (D \cdot n^{\sigma})}$.
The number of rounds is constant and the honest prover runs in polynomial time given witnesses for all $k$ inputs' membership in the language.

Our second result is a constant-round doubly-efficient argument system for languages in $P$ that are computable by bounded-space Turing machines. For this class of computations, we obtain an exponential improvement in the trade-off between the number of rounds and the (exponent of the) communication complexity, compared to known unconditionally sound protocols [Reingold, Rothblum and Rothblum, STOC 2016].



## 2024/851

* Title: On the parallelization of square-root Vélu's formulas
* Authors: Jorge Chávez-Saab, Odalis Ortega, Amalia Pizarro-Madariaga
* [Permalink](https://eprint.iacr.org/2024/851)
* [Download](https://eprint.iacr.org/2024/851.pdf)

### Abstract

A primary challenge in isogeny-based cryptography lies in the substantial computational cost associated to computing and evaluating prime-degree isogenies.. This computation traditionally relied on Vélu's formulas, an approach with time complexity linear in the degree but which was further enhanced by Bernstein, De Feo, Leroux, and Smith to a square-root complexity. The improved square-root Vélu's formulas exhibit a degree of parallelizability that has not been exploited in major implementations. In this study, we introduce a theoretical framework for parallelizing isogeny computations and provide a proof-of-concept implementation in C with OpenMP. While the parallelization effectiveness exhibits diminishing returns with the number of cores, we still obtain strong results when using a small number of cores. Concretely, our implementation shows that for large degrees it is easy to achieve speedup factors of up to $1.74$, $2.54$, and $3.44$ for two, four, and eight cores, respectively.



## 2024/852

* Title: Breaking Indistinguishability with Transfer Learning: A First Look at SPECK32/64 Lightweight Block Ciphers
* Authors: Jimmy Dani, Kalyan Nakka, Nitesh Saxena
* [Permalink](https://eprint.iacr.org/2024/852)
* [Download](https://eprint.iacr.org/2024/852.pdf)

### Abstract

In this research, we introduce MIND-Crypt, a novel attack framework that uses deep learning (DL) and transfer learning (TL) to challenge the indistinguishability of block ciphers, specifically SPECK32/64 encryption algorithm in CBC mode (Cipher Block Chaining) against Known Plaintext Attacks (KPA). Our methodology includes training a DL model with ciphertexts of two messages encrypted using the same key. The selected messages have the same byte-length and differ by only one bit at the binary level. This DL model employs a residual network architecture. For the TL, we use the trained DL model as a feature extractor, and these features are then used to train a shallow machine learning, such as XGBoost. This dual strategy aims to distinguish ciphertexts of two encrypted messages, addressing traditional cryptanalysis challenges.

Our findings demonstrate that the deep learning model achieves an accuracy of approximately 99% under consistent cryptographic conditions (Same Key or Rounds) with the SPECK32/64 cipher. However, performance degrades to random guessing levels (50%) when tested with ciphertext generated from different keys or different encryption rounds of SPECK32/64. To enhance the results, the DL model requires retraining with different keys or encryption rounds using larger datasets ($10^{7}$ samples). To overcome this limitation, we implement TL, achieving an accuracy of about 53% with just 10,000 samples, which is better than random guessing. Further training with 580,000 samples increases accuracy to nearly 99%, showing a substantial reduction in data requirements by over 94%. This shows that an attacker can utilize machine learning models to break indistinguishability by accessing pairs of plaintexts and their corresponding ciphertexts encrypted with the same key, without directly interacting with the communicating parties.



## 2024/853

* Title: Practical q-IND-CPA-D-Secure Approximate Homomorphic Encryption
* Authors: Jean-Philippe Bossuat, Anamaria Costache, Christian Mouchet, Lea Nürnberger, Juan Ramón Troncoso-Pastoriza
* [Permalink](https://eprint.iacr.org/2024/853)
* [Download](https://eprint.iacr.org/2024/853.pdf)

### Abstract

At Eurocrypt $2021$, Li and Micciancio demonstrated that the IND-CPA notion of security is not sufficient to cover the passive security of approximate homomorphic encryption schemes, by outlining a key recovery attack against the CKKS scheme (Cheon, Kim, Kim, Seong, Asiacrypt $2017$). They proposed the notion of $q$-IND-CPA-D security, which allows an adversary to make $q$ calls to a restricted decryption oracle. Li and Micciancio left achieving $q$-IND-CPA-D security as an open problem, but proposed two approaches: noise flooding and an exact version of CKKS.
The first approach was addressed by Li, Micciancio, Schultz and Sorrell (Crypto 2022), but leads to substantial efficiency loss.

In this work, we look at the second approach.
We define $(\delta, r)$-exact CKKS, a version of CKKS that returns exact results on all except the least $r$ significant bits with (high) probability $\delta$, based on bounds on the noise. We prove that the advantage of a $q$-IND-CPA-D attacker against $(\delta, r)$-exact CKKS is determined by the failure probability of those bounds. We conduct a tight average-case and implementation-specific noise analysis of all elementary operations in CKKS, as implemented in the Lattigo library, including the bootstrapping operation. We propose bounds that have small enough failure probability for the advantage of a $q$-IND-CPA-D attacker against $(\delta,r)$-exact CKKS to become smaller than $2^{-128}$, while the parameter sets needed remain practical. We furthermore present an estimator tool that combines the bounds on basic operations and returns tight noise estimates, even for large circuits. We validate our bounds by showcasing experimental results on different iterative algorithms, homomorphic encoding, decoding and bootstrapping.



## 2024/854

* Title: Simulation-Extractable KZG Polynomial Commitments and Applications to HyperPlonk
* Authors: Benoit Libert
* [Permalink](https://eprint.iacr.org/2024/854)
* [Download](https://eprint.iacr.org/2024/854.pdf)

### Abstract

HyperPlonk is a recent SNARK proposal  (Eurocrypt'23) that features a linear-time prover and  supports custom gates of larger degree than Plonk.  For the time being,  its instantiations are only proven to be knowledge-sound (meaning that soundness is only guaranteed when the prover runs in isolation) while many applications motivate the stronger notion of simulation-extractability (SE). Unfortunately, the most efficient SE compilers are not immediately applicable to multivariate polynomial interactive oracle proofs.  To address this problem, we provide an instantiation of HyperPlonk for which we can prove simulation-extractability in a strong sense. As a crucial building block, we describe  KZG-based commitments to multivariate polynomials that also provide    simulation-extractability while remaining as efficient as  malleable ones.  Our proofs stand  in the combined algebraic group and random oracle model and ensure straight-line extractability (i.e., without rewinding).



## 2024/855

* Title: Securing the Future of GenAI: Policy and Technology
* Authors: Mihai Christodorescu, Ryan Craven, Soheil Feizi, Neil Gong, Mia Hoffmann, Somesh Jha, Zhengyuan Jiang, Mehrdad Saberi Kamarposhti, John Mitchell, Jessica Newman, Emelia Probasco, Yanjun Qi, Khawaja Shams, Matthew Turek
* [Permalink](https://eprint.iacr.org/2024/855)
* [Download](https://eprint.iacr.org/2024/855.pdf)

### Abstract

The rise of Generative AI (GenAI) brings about transformative potential across sectors, but its dual-use nature also amplifies risks. Governments globally are grappling with the challenge of regulating GenAI, balancing innovation against safety. China, the United States (US), and the European Union (EU) are at the forefront with initiatives like the Management of Algorithmic Recommendations, the Executive Order, and the AI Act, respectively. However, the rapid evolution of GenAI capabilities often outpaces the development of comprehensive safety measures, creating a gap between regulatory needs and technical advancements.

A workshop co-organized by Google, University of Wisconsin, Madison (UW-Madison), and Stanford University aimed to bridge this gap between GenAI policy and technology. The diverse stakeholders of the GenAI space—from the public and governments to academia and industry—make any safety measures under consideration more complex, as both technical feasibility and regulatory guidance must be realized. This paper summarizes the discussions during the workshop which addressed questions, such as: How regulation can be designed without hindering technological progress? How technology can evolve to meet regulatory standards? The interplay between legislation and technology is a very vast topic, and we don’t claim that this paper is a comprehensive treatment on this topic. This paper is meant to capture findings based on the workshop, and hopefully, can guide discussion on this topic.



## 2024/856

* Title: Indistinguishability Obfuscation from Bilinear Maps and LPN Variants
* Authors: Seyoon Ragavan, Neekon Vafa, Vinod Vaikuntanathan
* [Permalink](https://eprint.iacr.org/2024/856)
* [Download](https://eprint.iacr.org/2024/856.pdf)

### Abstract

We construct an indistinguishability obfuscation (IO) scheme from the sub-exponential hardness of the decisional linear problem on bilinear groups together with two variants of the learning parity with noise (LPN) problem, namely large-field LPN and (binary-field) sparse LPN. This removes the need to assume the existence pseudorandom generators (PRGs) in $\mathsf{NC}^0$ with polynomial stretch from the state-of-the-art construction of IO (Jain, Lin, and Sahai, EUROCRYPT 2022). As an intermediate step in our construction, we abstract away a notion of structured-seed polynomial-stretch PRGs in $\mathsf{NC}^0$ which suffices for IO and is implied by both sparse LPN and the existence of polynomial-stretch PRGs in $\mathsf{NC}^0$.

As immediate applications, from the sub-exponential hardness of the decisional linear assumption on bilinear groups, large-field LPN, and sparse LPN, we get alternative constructions of (a) fully homomorphic encryption (FHE) without lattices or circular security assumptions (Canetti, Lin, Tessaro, and Vaikuntanathan, TCC 2015), and (b) perfect zero-knowledge adaptively-sound succinct non-interactive arguments (SNARGs) for NP (Waters and Wu, STOC 2024).



## 2024/857

* Title: Speeding up Preimage and Key-Recovery Attacks with Highly Biased Differential-Linear Approximations
* Authors: Zhongfeng Niu, Kai Hu, Siwei Sun, Zhiyu Zhang, Meiqin Wang
* [Permalink](https://eprint.iacr.org/2024/857)
* [Download](https://eprint.iacr.org/2024/857.pdf)

### Abstract

We present a framework for speeding up the search for preimages of candidate one-way functions based on highly biased differential-linear distinguishers. It is naturally applicable to preimage attacks on hash functions. Further, a variant of this framework applied to keyed functions leads to accelerated key-recovery attacks. Interestingly, our technique is able to exploit related-key differential-linear distinguishers in the single-key model without querying the target  encryption oracle with unknown but related keys. This is in essence similar to how we speed up the key search based on the well known complementation property of DES, which calls for caution from the designers in building primitives meant to be secure in the single-key setting without a thorough cryptanalysis in the related-key model. We apply the method to sponge-based hash function Ascon-HASH, XOFs XOEsch/Ascon-XOF and AEAD Schwaemm, etc. Accelerated preimage or key-recovery attacks are obtained. Note that all the differential-linear distinguishers employed in this work are highly biased and thus can be experimentally verified.



## 2024/858

* Title: Ascon-Keccak AEAD Algorithm
* Authors: Stephan Müller
* [Permalink](https://eprint.iacr.org/2024/858)
* [Download](https://eprint.iacr.org/2024/858.pdf)

### Abstract

The Ascon specification defines among others an encryption scheme offering authenticated encryption with associated data (AEAD) which is based on a duplex mode of a sponge. With that it is the first of such algorithm selected and about to be standardized by NIST.
The sponge size is comparatively small, 320 bits, as expected for lightweight cryptography. With that, the strength of the defined AEAD algorithm is limited to 128 bits. Albeit, the definition of the Ascon AEAD algorithm integrates with the associated sponge, it is mathematically not bound to exactly this sponge function. Thus, the Ascon AEAD specification can be used with a different sponge and still operate as defined by the Ascon authors.
This specification defines the Ascon-Keccak AEAD algorithm which replaces the Ascon sponge with the Keccak sponge, leaving the Ascon AEAD algorithm unchanged. The selected parameters for Ascon-Keccak AEAD offer two algorithm strengths: Ascon-Keccak 256 with a classic security strength of 256 bits and a quantum security strength of 128 bits. In addition, Ascon-Keccak 512 provides an algorithm with 512 bit classic security strength and 256 bit quantum security strength. The selected parameters for Ascon-Keccak 256 offer a significant higher performance on 64-bit architectures than Ascon-128 and Ascon-128a. The performance of Ascon-Keccak 512 is in league with Ascon-128. Yet, with the Keccak sponge size of 1600 bits, Ascon-Keccak cannot be considered a lightweight cryptographic algorithm any more. A reference implementation of the algorithm is provided as referenced in the document.

Date Sujet#  Auteur
3 Jun 24 o [digest] 2024 Week 221IACR ePrint Archive

Haut de la page

Les messages affichés proviennent d'usenet.

NewsPortal