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


[continued in next message]

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