[digest] 2024 Week 31

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

1. [2024/1210] More Optimizations to Sum-Check Proving
2. [2024/1211] A Generic Framework for Side-Channel Attacks ...
3. [2024/1212] Efficient Layered Circuit for Verification of SHA3 ...
4. [2024/1213] Bounded-Collusion Streaming Functional Encryption ...
5. [2024/1214] Less Effort, More Success: Efficient Genetic ...
6. [2024/1215] Falsifiability, Composability, and Comparability of ...
7. [2024/1216] Delegatable Anonymous Credentials From Mercurial ...
8. [2024/1217] A Compact and Parallel Swap-Based Shuffler based on ...
9. [2024/1218] A Note on the use of the Double Boomerang ...
10. [2024/1219] Foldable, Recursive Proofs of Isogeny Computation ...
11. [2024/1220] Mova: Nova folding without committing to error terms
12. [2024/1221] Depth Optimized Quantum Circuits for HIGHT and LEA
13. [2024/1222] Quantum Implementation and Analysis of ARIA
14. [2024/1223] A short-list of pairing-friendly curves resistant ...
15. [2024/1224] Generic Construction of Secure Sketches from Groups
16. [2024/1225] SIGNITC: Supersingular Isogeny Graph Non- ...
17. [2024/1226] A Spectral Analysis of Noise: A Comprehensive, ...
18. [2024/1227] ZIPNet: Low-bandwidth anonymous broadcast from ...
19. [2024/1228] Automated Software Vulnerability Static Code ...
20. [2024/1229] Benchmarking Attacks on Learning with Errors
21. [2024/1230] Impossible Boomerang Attacks Revisited: ...
22. [2024/1231] A Constructive View of Homomorphic Encryption and ...
23. [2024/1232] Efficient and Privacy-Preserving Collective Remote ...
24. [2024/1233] Binding Security of Implicitly-Rejecting KEMs and ...
25. [2024/1234] EagleSignV3 : A new secure variant of EagleSign ...
26. [2024/1235] Blue fish, red fish, live fish, dead fish
27. [2024/1236] Optimizing Big Integer Multiplication on Bitcoin: ...
28. [2024/1237] Efficient Variants of TNT with BBB Security

## 2024/1210

* Title: More Optimizations to Sum-Check Proving
* Authors: Quang Dao, Justin Thaler
* [Permalink](https://eprint.iacr.org/2024/1210)
* [Download](https://eprint.iacr.org/2024/1210.pdf)

### Abstract

Many fast SNARKs apply the sum-check protocol to an $n$-variate polynomial of the form $g(x) = \text{eq}(w,x) \cdot p(x)$, where $p$ is a product of multilinear polynomials, $w \in \mathbb{F}^n$ is a random vector, and $\text{eq}$ is the multilinear extension of the equality function.

In this setting, we describe an optimization to the sum-check prover that substantially reduces the cost coming from the $\text{eq}(w, x)$ factor. Our work further improves on a prior optimization by Gruen (ePrint 2023), and in the small-field case, can be combined with additional optimizations by Bagad, Domb, and Thaler (ePrint 2024), and Dao and Thaler (ePrint 2024).

Over large prime-order fields, our optimization eliminates roughly $2^{n + 1}$ field multiplications compared to a standard linear-time implementation of the prover, and roughly $2^{n-1}$ field multiplications when considered on top of Gruen's optimization. These savings are about a 25% (respectively 10%) end-to-end prover speedup in common use cases, and potentially even larger when working over binary tower fields.



## 2024/1211

* Title: A Generic Framework for Side-Channel Attacks against LWE-based Cryptosystems
* Authors: Julius Hermelink, Silvan Streit, Erik Mårtensson, Richard Petri
* [Permalink](https://eprint.iacr.org/2024/1211)
* [Download](https://eprint.iacr.org/2024/1211.pdf)

### Abstract

Lattice-based cryptography is in the process of being standardized. Several proposals to deal with side-channel information using lattice reduction exist. However, it has been shown that algorithms based on Bayesian updating are often more favorable in practice.

In this work, we define distribution hints; a type of hint that allows modelling probabilistic information. These hints generalize most previously defined hints and the information obtained in several attacks.

We define two solvers for our hints; one is based on belief propagation and the other one uses a greedy approach. We prove that the latter is a computationally less expensive approximation of the former and that previous algorithms used for specific attacks may be seen as special cases of our solvers. Thereby, we provide a systematization of previously obtained information and used algorithms in real-world side-channel attacks.

In contrast to lattice-based approaches, our framework is not limited to value leakage. For example, it can deal with noisy Hamming weight leakage or partially incorrect information. Moreover, it improves upon the recovery of the secret key from approximate hints in the form they arise in real-world attacks.
   
Our framework has several practical applications: We exemplarily show that a recent attack can be improved; we reduce the number of traces and corresponding ciphertexts and increase the noise resistance. Further, we explain how distribution hints could be applied in the context of previous attacks and outline a potential new attack.



## 2024/1212

* Title: Efficient Layered Circuit for Verification of SHA3 Merkle Tree
* Authors: Changchang Ding, Zheming Fu
* [Permalink](https://eprint.iacr.org/2024/1212)
* [Download](https://eprint.iacr.org/2024/1212.pdf)

### Abstract

We present an efficient layered circuit design for SHA3-256 Merkle tree verification, suitable for a GKR proof system, that achieves logarithmic verification and proof size. We demonstrate how to compute the predicate functions for our circuit in $O(\log n)$ time to ensure logarithmic verification and provide GKR benchmarks for our circuit.



## 2024/1213

* Title: Bounded-Collusion Streaming Functional Encryption from Minimal Assumptions
* Authors: Kaartik Bhushan, Alexis Korb, Amit Sahai
* [Permalink](https://eprint.iacr.org/2024/1213)
* [Download](https://eprint.iacr.org/2024/1213.pdf)

### Abstract

Streaming functional encryption (sFE), recently introduced by Guan, Korb, and Sahai [Crypto 2023], is an extension of functional encryption (FE) tailored for iterative computation on dynamic data streams. Unlike in regular FE, in an sFE scheme, users can encrypt and compute on the data as soon as it becomes available and in time proportional to just the size of the newly arrived data.

As sFE implies regular FE, all known constructions of sFE and FE for $\mathsf{P/Poly}$ require strong cryptographic assumptions which are powerful enough to build indistinguishability obfuscation. In contrast, bounded-collusion FE, in which the adversary is restricted to making at most $Q$ function queries for some polynomial $Q$ determined at setup, can be built from the minimal assumptions of public-key encryption (for public-key FE) [Sahai and Seyalioglu, CCS 2010; Gorbunov, Vaikuntanathan, and Wee, CRYPTO 2012] and secret-key encryption (for secret-key FE)[Ananth, Vaikuntanathan, TCC 2019].

In this paper, we introduce and build bounded-collusion streaming FE for any polynomial bound $Q$ from the same minimal assumptions of public-key encryption (for public-key sFE) and secret-key encryption (for secret-key sFE). Similarly to the original sFE paper of Guan, Korb, and Sahai, our scheme satisfies semi-adaptive-function-selective security which is similar to standard adaptive indistinguishability-based security except that we require all functions to be queried before any of the challenge messages.

Along the way, our work also replaces a key ingredient (called $\mathsf{One}\text{-}\mathsf{sFE}$) from the original work of Guan, Korb, and Sahai with a much simpler construction based on garbled circuits.



## 2024/1214

* Title: Less Effort, More Success: Efficient Genetic Algorithm-Based Framework for Side-channel Collision Attacks
* Authors: Jiawei Zhang, Jiangshan Long, Changhai Ou, Kexin Qiao, Fan Zhang, Shi Yan
* [Permalink](https://eprint.iacr.org/2024/1214)
* [Download](https://eprint.iacr.org/2024/1214.pdf)

### Abstract

By introducing collision information, the existing side-channel Correlation-Enhanced Collision Attacks (CECAs) performed collision-chain detection, and  reduced a given candidate space to a significantly smaller collision-chain space, leading to more efficient key recovery. However, they are still limited by low collision detection speed and low  success rate of key recovery. To address these issues, we first give a Collision Detection framework with Genetic Algorithm (CDGA), which exploits  Genetic Algorithm to detect the collision chains and has a strong capability of global searching. Secondly, we theoretically analyze the performance of CECA, and bound the searching depth of its output candidate
vectors with a confidence level using a rigorous hypothesis test, which is suitable both for Gaussian and non-Gaussian leakages. This facilitates the
 initialization of the population.
Thirdly, we design an innovative goal-directed mutation method to randomly select new gene values for replacement, thus improving efficiency and adaptability of the CDGA.  Finally, to optimize the evolutionary of CDGA,
we introduce roulette selection strategy to employ  a probability assignment based on individual fitness values to guarantee the preferential selection of superior genes. A single-point crossover strategy is also used to introduce novel gene segments into the chromosomes, thus enhancing the genetic diversity of the population. Experiments verify the superiority of our CDGA.



## 2024/1215

* Title: Falsifiability, Composability, and Comparability of Game-based Security Models for Key Exchange Protocols
* Authors: Chris Brzuska, Cas Cremers, Håkon Jacobsen, Douglas Stebila, Bogdan Warinschi
* [Permalink](https://eprint.iacr.org/2024/1215)
* [Download](https://eprint.iacr.org/2024/1215.pdf)

### Abstract

A security proof for a key exchange protocol requires writing down a security definition. Authors typically have a clear idea of the level of security they aim to achieve. Defining the model formally additionally requires making choices on games vs. simulation-based models, partnering, on having one or more Test queries and on adopting a style of avoiding trivial attacks: exclusion, penalizing or filtering. We elucidate the consequences, advantages and disadvantages of the different possible model choices. Concretely, we show that a model with multiple Test queries composes tightly with symmetric-key protocols while models with a single Test query require a hybrid argument that loses a factor in the number of sessions. To illustrate the usefulness of models with multiple Test queries, we prove the Naxos protocol security in said model and obtain a tighter bound than adding a hybrid argument on top of a proof in a single Test query model.

Our composition model exposes partnering information to the adversary, circumventing a previous result by Brzuska, Fischlin, Warinschi, and Williams (CCS 2011) showing that the protocol needs to provide public partnering. Moreover, our baseline theorem of key exchange partnering shows that partnering by key equality provides a joint baseline for most known partnering mechanisms, countering previous criticism by Li and Schäge (CCS 2017) that security in models with existential quantification over session identifiers is non-falsifiable.



## 2024/1216

* Title: Delegatable Anonymous Credentials From Mercurial Signatures With Stronger Privacy
* Authors: Scott Griffy, Anna Lysyanskaya, Omid Mir, Octavio Perez Kempner, Daniel Slamanig
* [Permalink](https://eprint.iacr.org/2024/1216)
* [Download](https://eprint.iacr.org/2024/1216.pdf)

### Abstract

Delegatable anonymous credentials (DACs) are anonymous credentials that allow a
root issuer to delegate their credential-issuing power to secondary issuers
who, in turn, can delegate further. This delegation, as well as credential
showing, is carried out in a privacy-preserving manner, so that credential
recipients and verifiers learn nothing about the issuers on the delegation
chain.  One particularly efficient approach to constructing DACs is due to
Crites and Lysyanskaya (CT-RSA'19), based on mercurial signatures, which is a
type of equivalence-class signatures. In contrast to previous approaches, this
design is conceptually simple and does not require extensive use of
non-interactive zero-knowledge proofs. Unfortunately, the ``CL-type'' DAC
schemes proposed so far have a privacy limitation: if an adversarial issuer
(even an honest-but-curious one) was part of an honest user's delegation chain,
the adversary will be able to detect this fact (and identify the specific
adversarial issuer) when an honest user shows its credential.  This is because
underlying mercurial signature schemes allow the owner of a secret key to
detect when his key was used in a delegation chain.

In this paper we show that it is possible to construct CL-type DACs that does
not suffer from this privacy issue.  We give a new mercurial signature scheme
that provides adversarial public key class hiding; i.e. even if an adversarial
signer participated in the delegation chain, the adversary won't be able to
identify this fact. This is achieved by introducing structured public
parameters which for each delegation level, enabling strong privacy features in
DAC. Since the setup of these parameters also produces trapdoors that are
problematic in privacy applications, we show how to overcome this problem by
using techniques from updatable structured reference string in zero-knowledge
proof systems (Groth et al. CRYPTO'18).

In addition, we propose a simple way to realize revocation for CL-type DACs via
the concept of revocation tokens. While we showcase this approach to revocation
using our DAC scheme, it is generic and can be applied to any CL-type DAC
system. Revocation is a feature that is largely unexplored and notoriously hard
to achieve for DACs. However as it is  a vital feature for any anonymous
credential system, this can help to make DAC schemes more attractive for
practical applications.



## 2024/1217

* Title: A Compact and Parallel Swap-Based Shuffler based on butterfly Network and its complexity against Side Channel Analysis
* Authors: Jong-Yeon Park, Wonil Lee, Bo Gyeong Kang, Il-jong Song, Jaekeun Oh, Kouichi Sakurai
* [Permalink](https://eprint.iacr.org/2024/1217)
* [Download](https://eprint.iacr.org/2024/1217.pdf)

### Abstract

A prominent countermeasure against side channel attacks, the hiding countermeasure, typically involves shuffling operations using a permutation algorithm. Especially in the era of Post-Quantum Cryptography, the importance of the hiding coun- termeasure is emphasized due to computational characteristics like those of lattice and code-based cryptography. In this context, swiftly and securely generating permutations has a critical impact on an algorithm’s security and efficiency. The widely adopted Fisher-Yates shuffle, because of its high security and ease of implementation, is prevalent. However, it has a limitation of complexity O(𝑁) due to its sequential nature. In response, we propose a time-area trade-off swap algorithm, FSS, based on the Butterfly Network with only log(𝑁) depth, log(𝑁) works and O(1) operation time in parallel. We will calculate the maximum gain that an attacker can achieve through butterfly operations with only log(𝑁) depth from side channel analysis perspective. In particular, we will show that it is possible to derive a generalized formula of the attack complexity with higher-order side channel attacks for arbitrary input sizes through a fractal structure of the butterfly network. Furthermore, our research highlights the possibility of generating efficient and secure permutations utilizing a minimal amount of randomness.



## 2024/1218

* Title: A Note on the use of the Double Boomerang Connectivity Table (DBCT) for Spotting Impossibilities
* Authors: Xavier Bonnetain, Virginie Lallemand
* [Permalink](https://eprint.iacr.org/2024/1218)
* [Download](https://eprint.iacr.org/2024/1218.pdf)

### Abstract

In this short note we examine one of the impossible boomerang distinguishers of Skinny-128-384 provided by Zhang, Wang and Tang at ToSC 2024 Issue 2 and disprove it.

The issue arises from the use of the Double Boomerang Connectivity Table (DBCT) as a tool to establish that a boomerang switch over 2 rounds has probability zero, whereas the DBCT only covers specific cases of difference propagation, missing a large set of events that might make the connection possible.

We study in details the specific instance provided by Zhang et al. and display one example of a returning quartet that contradicts the impossibility.



## 2024/1219

* Title: Foldable, Recursive Proofs of Isogeny Computation with Reduced Time Complexity
* Authors: Krystal Maughan, Joseph Near, Christelle Vincent
* [Permalink](https://eprint.iacr.org/2024/1219)
* [Download](https://eprint.iacr.org/2024/1219.pdf)

### Abstract

The security of certain post-quantum isogeny-based cryptographic schemes relies on the ability to provably and efficiently compute isogenies between supersingular elliptic curves without leaking information about the isogeny other than its domain and codomain. Earlier work in this direction give mathematical proofs of knowledge for the isogeny, and as a result when computing a chain of $n$ isogenies each proceeding node must verify the correctness of the proof of each preceding node, which is computationally linear in $n$.
  
  In this work, we empirically build a system to prove the execution of the circuit computing the isogeny rather than produce a proof of knowledge. This proof can then be used as part of the verifiable folding scheme Nova, which reduces the complexity of an isogeny proof of computation for a chain of $n$ isogenies from $O(n)$ to $O(1)$ by providing at each step a single proof that proves the whole preceding chain. To our knowledge, this is the first application of this type of solution to this problem.



## 2024/1220

* Title: Mova: Nova folding without committing to error terms
* Authors: Nikolaos Dimitriou, Albert Garreta, Ignacio Manzur, Ilia Vlasov
* [Permalink](https://eprint.iacr.org/2024/1220)
* [Download](https://eprint.iacr.org/2024/1220.pdf)

### Abstract

We present Mova, a folding scheme  for R1CS instances that does not require committing to error or cross terms, nor makes use of the sumcheck protocol. For reasonable parameter choices, Mova's Prover is about $5$ to $10$ times faster than Nova's Prover, and about $1.5$  times faster than Hypernova's Prover (applied to R1CS instances), assuming the R1CS witness vector contains only small elements. Mova's Verifier has a similar cost as Hypernova's Verifier, but Mova has the advantage of having only $4$ rounds of communication, while Hypernova has a logarithmic number of rounds.

Mova, which is based on the Nova folding scheme, manages to avoid committing to Nova's so-called error term $\mathbf{E}$ and cross term  $\mathbf{T}$ by replacing said commitments with evaluations of the Multilinear Extension (MLE) of $\mathbf{E}$ and $\mathbf{T}$ at a random point sampled by the Verifier. A key observation used in Mova's soundness proofs is that $\mathbf{E}$ is implicitly committed by a commitment to the input-witness vector $\mathbf{Z}$, since $\mathbf{E}=(A\cdot\mathbf{Z})\circ (B\cdot\mathbf{Z}) -u (C\cdot \mathbf{Z})$.



## 2024/1221

* Title: Depth Optimized Quantum Circuits for HIGHT and LEA
* Authors: Kyungbae Jang, Yujin Oh, Minwoo Lee, Dukyoung Kim, Hwajeong Seo
* [Permalink](https://eprint.iacr.org/2024/1221)
* [Download](https://eprint.iacr.org/2024/1221.pdf)

### Abstract

Quantum computers can model and solve several problems that have posed challenges for classical super computers, leveraging their natural quantum mechanical characteristics. A large-scale quantum computer is poised to significantly reduce security strength in cryptography. In this context, extensive research has been conducted on quantum cryptanalysis. In this paper, we present optimized quantum circuits for Korean block ciphers, HIGHT and LEA. Our quantum circuits for HIGHT and LEA demonstrate the lowest circuit depth compared to previous results. Specifically, we achieve depth reductions of 48% and 74% for HIGHT and LEA, respectively. We employ multiple novel techniques that effectively reduce the quantum circuit depth with a reasonable increase in qubit count. Based on our depth-optimized quantum circuits for HIGHT and LEA block ciphers, we estimate the lowest quantum attack complexity for Grover’s key search. Our quantum circuit can be utilized for other quantum algorithms, not only for Grover’s algorithm. Furthermore, the optimization methods gathered in this work can be adopted for generic quantum implementations in cryptography.



## 2024/1222

* Title: Quantum Implementation and Analysis of ARIA
* Authors: Yujin Oh, Kyungbae Jang, Yujin Yang, Hwajeong Seo
* [Permalink](https://eprint.iacr.org/2024/1222)
* [Download](https://eprint.iacr.org/2024/1222.pdf)

### Abstract

The progression of quantum computing is considered a potential threat to traditional cryptography system, highlighting the significance of post-quantum security in cryptographic systems. Regarding symmetric key encryption, the Grover algorithm can approximately halve the search complexity. Despite the absence of fully operational quantum computers at present, the necessity of assessing the security of symmetric key encryption against quantum computing continues to grow. In this paper, we implement the ARIA block cipher in a quantum circuit and compare it with previous research. Our implementation of the ARIA quantum circuit achieves over 92.5% improvement in full depth and over 98.7% improvement in Toffoli depth compared to the implementation proposed in Chauhan et al. Compared to Yang et al.’s implementation, our implementation is improved the full depth by 36.7% and the number of qubits by 8%. Additionally, we analyze the complexity of Grover’s search attack and compare it with NIST criteria. We confirm that ARIA achieves quantum security level 1, 3, and 5 (ARIA-128, 192, and 256, respectively).



## 2024/1223

* Title: A short-list of pairing-friendly curves resistant to the Special TNFS algorithm at the 192-bit security level
* Authors: Diego F. Aranha, Georgios Fotiadis, Aurore Guillevic
* [Permalink](https://eprint.iacr.org/2024/1223)
* [Download](https://eprint.iacr.org/2024/1223.pdf)

### Abstract

For more than two decades, pairings have been a fundamental tool for designing elegant cryptosystems, varying from digital signature schemes to more complex privacy-preserving constructions. However, the advancement of quantum computing threatens to undermine public-key cryptography. Concretely, it is widely accepted that a future large-scale quantum computer would be capable to break any public-key cryptosystem used today, rendering today's public-key cryptography obsolete and mandating the transition to quantum-safe cryptographic solutions. This necessity is enforced by numerous recognized government bodies around the world, including NIST which initiated the first open competition in standardizing post-quantum (PQ) cryptographic schemes, focusing primarily on digital signatures and key encapsulation/public-key encryption schemes. Despite the current efforts in standardizing PQ primitives, the landscape of complex, privacy-preserving cryptographic protocols, e.g., zkSNARKs/zkSTARKs, is at an early stage. Existing solutions suffer from various disadvantages in terms of efficiency and compactness and in addition, they need to undergo the required scrutiny to gain the necessary trust in the academic and industrial domains. Therefore, it is believed that the migration to purely  quantum-safe cryptography would require an intermediate step where current classically secure protocols and quantum-safe solutions will co-exist. This is enforced by the report of the Commercial National Security Algorithm Suite version 2.0, mandating transition to quantum-safe cryptographic algorithms by 2033 and suggesting to incorporate ECC at 192-bit security in the meantime. To this end, the present paper aims at providing a comprehensive study on pairings at 192-bit security level. We start with an exhaustive review in the literature to search for all possible recommendations of such pairing constructions, from which we extract the most promising candidates in terms of efficiency and security, with respect to the advanced Special TNFS attacks. Our analysis is focused, not only on the pairing computation itself, but on additional operations that are relevant in pairing-based applications, such as hashing to pairing groups, cofactor clearing and subgroup membership testing. We implement all functionalities of the most promising candidates within the RELIC cryptographic toolkit in order to identify the most efficient pairing implementation at 192-bit security and provide extensive experimental results.



## 2024/1224

* Title: Generic Construction of Secure Sketches from Groups
* Authors: Axel Durbet, Koray Karabina, Kevin Thiry-Atighehchi
* [Permalink](https://eprint.iacr.org/2024/1224)
* [Download](https://eprint.iacr.org/2024/1224.pdf)

### Abstract

Secure sketches are designed to facilitate the recovery of originally enrolled data from inputs that may vary slightly over time. This capability is important in applications where data consistency cannot be guaranteed due to natural variations, such as in biometric systems and hardware security. Traditionally, secure sketches are constructed using error-correcting codes to handle these variations effectively. Additionally, principles of information theory ensure the security of these sketches by managing the trade-off between data recoverability and confidentiality. In this paper, we show how to construct a new family of secure sketches generically from groups. The notion of groups with unique factorization property is first introduced, which is of independent interest and serves as a building block for our secure sketch construction. Next, an in-depth study of the underlying mathematical structures is provided, and some computational and decisional hardness assumptions are defined. As a result, it is argued that our secure sketches are efficient; can handle a linear fraction of errors with respect to the norm 1 distance; and that they are reusable and irreversible. To our knowledge, such generic group-based secure sketch construction is the first of its kind, and it offers a viable alternative to the currently known secure sketches.



## 2024/1225

* Title: SIGNITC: Supersingular Isogeny Graph Non-Interactive Timed Commitments
* Authors: Knud Ahrens
* [Permalink](https://eprint.iacr.org/2024/1225)
* [Download](https://eprint.iacr.org/2024/1225.pdf)

### Abstract

Non-Interactive Timed Commitment schemes (NITC) allow to open any commitment after a specified delay $t_{\mathrm{fd}}$ . This is useful for sealed bid auctions and as primitive for more complex protocols. We present the first NITC without repeated squaring or theoretical black box algorithms like NIZK proofs or one-way functions. It has fast verification, almost arbitrary delay and satisfies IND-CCA hiding and perfect binding. Additionally, it needs no trusted setup. Our protocol is based on isogenies between supersingular elliptic curves making it presumably quantum secure, and all algorithms have been implemented as part of SQISign or other well-known isogeny-based cryptosystems.



## 2024/1226

* Title: A Spectral Analysis of Noise: A Comprehensive, Automated, Formal Analysis of Diffie-Hellman Protocols
* Authors: Guillaume Girol, Lucca Hirschi, Ralf Sasse, Dennis Jackson, Cas Cremers, David Basin
* [Permalink](https://eprint.iacr.org/2024/1226)
* [Download](https://eprint.iacr.org/2024/1226.pdf)

### Abstract

The Noise specification describes how to systematically construct a large family of Diffie-Hellman based key exchange protocols, including the secure transports used by WhatsApp, Lightning, and WireGuard. As the specification only makes informal security claims, earlier work has explored which formal security properties may be enjoyed by protocols in the Noise framework, yet many important questions remain open.

In this work we provide the most comprehensive, systematic analysis of the Noise framework to date. We start from first principles and, using an automated analysis tool, compute the strongest threat model under which a protocol is secure, thus enabling formal comparison between protocols. Our results allow us to objectively and automatically associate each informal security level presented in the Noise specification with a formal security claim.

We also provide a fine-grained separation of Noise protocols that were previously described as offering similar security properties, revealing a subclass for which alternative Noise protocols exist that offer strictly better security guarantees. Our analysis also uncovers missing assumptions in the Noise specification and some surprising consequences, e.g. in some situations higher security levels yield strictly worse security.



## 2024/1227

* Title: ZIPNet: Low-bandwidth anonymous broadcast from (dis)Trusted Execution Environments
* Authors: Michael Rosenberg, Maurice Shih, Zhenyu Zhao, Rui Wang, Ian Miers, Fan Zhang
* [Permalink](https://eprint.iacr.org/2024/1227)
* [Download](https://eprint.iacr.org/2024/1227.pdf)

### Abstract

Anonymous Broadcast Channels (ABCs) allow a group of clients to announce messages without revealing the exact author. Modern ABCs operate in a client-server model, where anonymity depends on some threshold (e.g., 1 of 2) of servers being honest. ABCs are an important application in their own right, e.g., for activism and whistleblowing. Recent work on ABCs (Riposte, Blinder) has focused on minimizing the bandwidth cost to clients and servers when supporting large broadcast channels for such applications. But, particularly for low bandwidth settings, they impose large costs on servers, make cover traffic costly, and make volunteer operators unlikely.

In this paper, we describe the design, implementation, and evaluation of ZIPNet, an anonymous broadcast channel that 1) scales to hundreds of anytrust servers by minimizing the computational costs of each server, 2) substantially reduces the servers’ bandwidth costs by outsourcing the aggregation of client messages to untrusted (for privacy) infrastructure, and 3) supports cover traffic that is both cheap for clients to produce and for servers to handle.



## 2024/1228

* Title: Automated Software Vulnerability Static Code Analysis Using Generative Pre-Trained Transformer Models
* Authors: Elijah Pelofske, Vincent Urias, Lorie M. Liebrock
* [Permalink](https://eprint.iacr.org/2024/1228)
* [Download](https://eprint.iacr.org/2024/1228.pdf)

### Abstract

Generative Pre-Trained Transformer models have been shown to be surprisingly effective at a variety of natural language processing tasks -- including generating computer code. However, in general GPT models have been shown to not be incredibly effective at handling specific computational tasks (such as evaluating mathematical functions).
In this study, we evaluate the effectiveness of open source GPT models, with no fine-tuning, and with context introduced by the langchain and localGPT Large Language Model (LLM) framework, for the task of automatic identification of the presence of vulnerable code syntax (specifically targeting C and C++ source code). This task is evaluated on a selection of $36$ source code examples from the NIST SARD dataset, which are specifically curated to not contain natural English that indicates the presence, or lack thereof, of a particular vulnerability (including the removal of all source code comments). The NIST SARD source code dataset contains identified vulnerable lines of source code that are examples of one out of the $839$ distinct Common Weakness Enumerations (CWE), allowing for exact quantification of the GPT output classification error rate. A total of $5$ GPT models are evaluated, using $10$ different inference temperatures and $100$ repetitions at each setting, resulting in $5,000$ GPT queries per vulnerable source code analyzed.
Ultimately, we find that the open source GPT models that we evaluated are not suitable for fully automated vulnerability scanning because the false positive and false negative rates are too high to likely be useful in practice. However, we do find that the GPT models perform surprisingly well at automated vulnerability detection for some of the test cases, in particular surpassing random sampling (for some GPT models and inference temperatures), and being able to identify the exact lines of code that are vulnerable albeit at a low success rate. The best performing GPT model result found was Llama-2-70b-chat-hf with inference temperature of $0.1$ applied to NIST SARD test case 149165 (which is an example of a buffer overflow vulnerability), which had a binary classification recall score of $1.0$ and a precision of $1.0$ for correctly and uniquely identifying the vulnerable line of code and the correct CWE number..
Additionally, the GPT models are able to, with a rate quantifiably better than random sampling, identify the specific line of source that contains the identified CWE for many of the NIST SARD test cases.



## 2024/1229

* Title: Benchmarking Attacks on Learning with Errors
* Authors: Emily Wenger, Eshika Saxena, Mohamed Malhou, Ellie Thieu, Kristin Lauter
* [Permalink](https://eprint.iacr.org/2024/1229)
* [Download](https://eprint.iacr.org/2024/1229.pdf)

### Abstract

Lattice cryptography schemes based on the learning with errors (LWE) hardness assumption have been standardized by NIST for use as post-quantum cryptosystems, and by HomomorphicEncryption.org for encrypted compute on sensitive data.. Thus, understanding their concrete security is critical. Most work on LWE security focuses on theoretical estimates of attack performance, which is important but may overlook attack nuances arising in real-world implementations.  The sole existing concrete benchmarking effort, the Darmstadt Lattice Challenge, does not include benchmarks relevant to the standardized LWE parameter choices - such as small secret and small error distributions, and Ring-LWE (RLWE) and Module-LWE (MLWE) variants. To improve our understanding of concrete LWE security, we provide the first benchmarks for LWE secret recovery on standardized parameters, for small and low-weight (sparse) secrets.   We evaluate four LWE attacks in these settings to serve as a baseline: the Search-LWE attacks uSVP, SALSA, and Cool & Cruel, and the Decision-LWE attack:  Dual Hybrid Meet-in-the-Middle (MitM).  We extend the SALSA and Cool & Cruel attacks in significant ways, and implement and scale up MitM attacks for the first time.. For example, we recover hamming weight $9-11$ binomial secrets for KYBER ($\kappa=2$) parameters in $28-36$ hours with SALSA and Cool & Cruel, while we find that MitM can solve Decision-LWE instances for hamming weights up to $4$ in under an hour for Kyber parameters, while uSVP attacks do not recover any secrets after running for more than $1100$ hours.  We also compare concrete performance against theoretical estimates.  Finally, we open source the code to enable future research.



## 2024/1230

* Title: Impossible Boomerang Attacks Revisited: Applications to Deoxys-BC, Joltik-BC and SKINNY
* Authors: Jianing Zhang, Haoyang Wang, Deng Tang
* [Permalink](https://eprint.iacr.org/2024/1230)
* [Download](https://eprint.iacr.org/2024/1230.pdf)

### Abstract

The impossible boomerang (IB) attack was first introduced by Lu in his doctoral thesis and subsequently published at DCC in 2011. The IB attack is a variant of the impossible differential (ID) attack by incorporating the idea of the boomerang attack. In this paper, we revisit the IB attack, and introduce the incompatibility of two characteristics in boomerang to the construction of an IB distinguisher. With our methodology, all the constructions of IB distinguisher are represented in a unified manner. Moreover, we show that the related-(twea)key IB distinguishers possess more freedom than the ones of ID so that it can cover more rounds.
We also propose a new tool based on Mixed-Integer Quadratically-Constrained Programming (MIQCP) to search for IB attacks. To illustrate the power of the IB attack, we mount attacks against three tweakable block ciphers: Deoxys-BC, Joltik-BC and SKINNY. For Deoxys-BC, we propose a related-tweakey IB attack on 14-round Deoxys-BC-384, which improves the best previous related-tweakey ID attack by 2 rounds, and we improve the data complexity of the best previous related-tweakey ID attack on 10-round Deoxys-BC-256. For Joltik-BC, we propose the best attacks against 10-round Joltik-BC-128 and 14-round Joltik-BC-192 with related-tweakey IB attack. For SKINNY-n-3n, we propose a 27-round related-tweakey IB attack, which improves both the time and the memory complexities of the best previous ID attack. We also propose the first related-tweakey IB attack on 28 round SKINNY-n-3n, which improves the previous best ID attack by one round.



## 2024/1231

* Title: A Constructive View of Homomorphic Encryption and Authenticator
* Authors: Ganyuan Cao
* [Permalink](https://eprint.iacr.org/2024/1231)
* [Download](https://eprint.iacr.org/2024/1231.pdf)

### Abstract

Homomorphic Encryption (HE) is a cutting-edge cryptographic technique that enables computations on encrypted data to be mirrored on the original data. This has quickly attracted substantial interest from the research community due to its extensive practical applications, such as in cloud computing and privacy-preserving machine learning.

In addition to confidentiality, the importance of authenticity has emerged to ensure data integrity during transmission and evaluation. To address authenticity, various primitives have been developed including Homomorphic Authenticator (HA). Corresponding security notions have also been introduced by extending the existing notions to their homomorphic versions.

Despite these advancements, formalizing the security of HE and HA remains challenging due to the novelty of these primitives and complexity of application scenarios involving message evaluation. It is inclusive which definitions in this zoo of notions are insufficient or overly complex. Moreover, HE and HA are designed to be combined to construct a secure communication channel that ensures both confidentiality and authenticity. However, the security of such compositions is not always clear when game-based notions are used to formalize security.

To bridge this gap, we conduct a constructive analysis through the lens of com- posable security. This method enables us to examine the security properties of each primitive in isolation and to more effectively evaluate their security when integrated into a larger system. We introduce the concepts of a confidential channel and an au- thenticated channel to specify the security requirements for HE and HA, respectively. We make a comparison with existing game-based notions to determine whether they adequately capture the intended security objectives.

We then analyze whether the composition of HE and HA constructs a Homomorphic Authenticated Encryption (HAE) that provides both confidentiality and authenticity in presence of message evaluation. Specifically, we examine a serial composition of HE and HA, corresponding to Encrypt-then-MAC (EtM) composition for constructing classical AE.



## 2024/1232

* Title: Efficient and Privacy-Preserving Collective Remote Attestation for NFV
* Authors: Ghada Arfaoui, Thibaut Jacques, Cristina Onete
* [Permalink](https://eprint.iacr.org/2024/1232)
* [Download](https://eprint.iacr.org/2024/1232.pdf)

### Abstract

The virtualization of network functions is a promising technology, which can enable mobile network operators to provide more flexibility and better resilience for their infrastructure and services. Yet, virtualization comes with challenges, as 5G operators will require a means of verifying the state of the virtualized network components (e.g. Virtualized Network Functions (VNFs) or managing hypervisors) in order to fulfill security and privacy commitments. One such means is the use of attestation protocols. In this paper, we focus on Collective Remote Attestation (cRA), which is used to attest the state of a group of devices. Although cRA has been extensively studied in the context of IoT, it has not been used yet in virtualized mobile networks, a different use-case, with constraints of its own. 

In this paper, we propose the first protocol to efficiently and securely attest a group of Virtualized Network Functions which make up a VNF Forwarding Graph. Our protocol comes with strong and provable guarantees of: unforgeability of attestation, the linkability of attestations for related components, and the privacy of sensitive configuration details for the infrastructure provider. In particular, we are the first to formally define and analyze such properties for VNF-FG attestation. Finally, through our Proof-of-Concept implementation, we show that our construction is not only strongly secure, but also efficient.



## 2024/1233

* Title: Binding Security of Implicitly-Rejecting KEMs and Application to BIKE and HQC
* Authors: Juliane Krämer, Patrick Struck, Maximiliane Weishäupl
* [Permalink](https://eprint.iacr.org/2024/1233)
* [Download](https://eprint.iacr.org/2024/1233.pdf)

### Abstract

In this work, we continue the analysis of the binding properties of implicitly-rejecting key-encapsulation mechanisms (KEMs) obtained via the Fujisaki-Okamoto (FO) transform. These binding properties, in earlier literature known under the term robustness, thwart attacks that can arise when using KEMs in larger protocols. Recently, Cremers et al. (ePrint'24) introduced a framework for binding notions, encompassing previously existing but also new ones. While implicitly-rejecting KEMs have been analyzed with respect to multiple of these notions, there are still several gaps. We complete the picture by providing positive and negative results for the remaining notions. Further, we show how to apply our results to the code-based KEMs BIKE and HQC, which are among the round-4 candidates in NISTs PQC standardization process. Through this, we close a second gap as our results finish the analysis of the binding notions for the NIST round-4 KEMs.



## 2024/1234

* Title: EagleSignV3 : A  new  secure variant of EagleSign signature over lattices
* Authors: Abiodoun Clement Hounkpevi, Sidoine Djimnaibeye, Michel Seck, Djiby Sow
* [Permalink](https://eprint.iacr.org/2024/1234)
* [Download](https://eprint.iacr.org/2024/1234.pdf)

### Abstract

With the potential arrival of quantum computers, it is essential to build cryptosystems resistant to attackers with the computing power of a quantum computer. With Shor's algorithm, cryptosystems based on discrete logarithms and  factorization become obsolete. Reason why NIST has launching two competitions in 2016 and 2023 to standardize post-quantum  cryptosystems (such as KEM and signature ) based on problems supposed to resist attacks using quantum computers. EagleSign was prosed to NIT competition in Jun 2023 as an additional signature. An improvement called EagleSign-V2 was proposed in December 2023 but Tibouchi and Pells prove that these two variants don't hold the zero knowledge property.  In this document we present the family of lattices based post-quantum signatures   called EagleSignV3. They are secure and efficient successors of both EagleSign-V1 (NIST, June 2023) and EagleSign-V2 (NIST forum, December 2023). The public key of EagleSignV3 is  based on a mix of MLE (Module Learning with Error) and  MNTRU (module variant of the famous NTRU problem).  The instantiations EagleSignV3  are new variants of the EagleSign signatures family posted to NIST competition in June 2023 as additional signatures.   EagleSignV3  uses the rejection of Lyubashevsky-2012 to achieve the zero-knowledge property. The main difference between EagleSign and Dilithium is the public key.
We have two instantiations based either on ring or on module.  The sizes of the ring based variant of EagleSignV3 are close to  those of   Dilithium but the sizes of its module based instantiation is bigger than those of Dilithium.
NB:  The implementation of  EagleSign-V1 is  available on NIST website and those of EagleSign-V2 can be found on  Github at https://github.com/EagleSignteam/EagleSign_v2 and in NIST forum as a comment on improvements on EagleSign in December 2023. The implementation of  EagleSign-V3 can be deduced from those of EagleSignV2.



## 2024/1235

* Title: Blue fish, red fish, live fish, dead fish
* Authors: Victor Shoup
* [Permalink](https://eprint.iacr.org/2024/1235)
* [Download](https://eprint.iacr.org/2024/1235.pdf)

### Abstract

We show that the DAG-based consensus protocol Tusk [DKSS22] does not achieve liveness, at least under certain reasonable assumptions on the implementation that are consistent with its specification. In addition, we give a simple 2-round variation of Tusk with lower latency and strong liveness properties, but with suboptimal resilience. We also show that another 2-round protocol, GradedDAG [DZX+24], which has optimal resilience, also has liveness problems analogous to Tusk.



## 2024/1236

* Title: Optimizing Big Integer Multiplication on Bitcoin: Introducing w-windowed Approach
* Authors: Dmytro Zakharov, Oleksandr Kurbatov, Manish Bista, Belove Bist
* [Permalink](https://eprint.iacr.org/2024/1236)
* [Download](https://eprint.iacr.org/2024/1236.pdf)

### Abstract

A crucial component of any zero-knowledge system is operations with finite fields. This, in turn, leads to the implementation of the fundamental operation: multiplying two big integers. In the realm of Bitcoin, this problem gets revisited, as Bitcoin utilizes its own stack-based and not Turing-complete scripting system called Bitcoin Script. Inspired by Elliptic Curve scalar multiplication, this paper introduces the $w$-windowed method for multiplying two numbers. We outperform state-of-the-art approaches, including BitVM’s implementation. Finally, we also show how the windowed method can lead to optimizations not only in big integer arithmetic solely but in more general arithmetic problems.



## 2024/1237

* Title: Efficient Variants of TNT with BBB Security
* Authors: Ritam Bhaumik, Wonseok Choi, Avijit Dutta, Cuauhtemoc Mancillas López, Hrithik Nandi, Yaobin Shen
* [Permalink](https://eprint.iacr.org/2024/1237)
* [Download](https://eprint.iacr.org/2024/1237.pdf)

### Abstract

At EUROCRYPT'20, Bao et al. have shown that three-round cascading of $\textsf{LRW1}$ construction, which they dubbed as $\textsf{TNT}$, is a strong tweakable pseudorandom permutation that provably achieves $2n/3$-bit security bound.. Jha et al. showed a birthday bound distinguishing attack on $\textsf{TNT}$ and invalidated the proven security bound and proved a tight birthday bound security on the $\textsf{TNT}$ construction in EUROCRYPT'24.
   
    In a recent work, Datta et al. have shown that four round cascading of the $\textsf{LRW1}$ construction, which they dubbed as $\textsf{CLRW1}^4$ is a strong tweakable pseudorandom permutation that provably achieves $3n/4$-bit security. In this paper, we propose a variant of the $\textsf{TNT}$ construction, called $\textsf{b-TNT1}$, and proved its security up to $2^{3n/4}$ queries. However, unlike $\textsf{CLRW1}^4$, $\textsf{b-TNT1}$ requires three block cipher calls along with a field multiplication. Besides, we also propose another variant of the $\textsf{TNT}$ construction, called $\textsf{b-TNT2}$ and showed a similar security bound. Compared to $\textsf{b-TNT1}$, $\textsf{b-TNT2}$ requires four block cipher calls. Nevertheless, its execution of block cipher calls can be pipelined which makes it efficient over $\textsf{CLRW1}^4$. We have also experimentally verified that both $\textsf{b-TNT1}$ and $\textsf{b-TNT2}$ outperform $\textsf{CLRW1}^4$.

Date Sujet#  Auteur
5 Aug 24 o [digest] 2024 Week 311IACR ePrint Archive

Haut de la page

Les messages affichés proviennent d'usenet.

NewsPortal