[digest] 2024 Week 33

## In this issue

1. [2024/1267] Chrysalis Cipher Suite
2. [2024/1268] Improved YOSO Randomness Generation with Worst-Case ...
3. [2024/1269] Cryptographic Security through Kleene’s Theorem and ...
4. [2024/1270] Meet-in-the-Middle Attack on 4+4 Rounds of SCARF ...
5. [2024/1271] AES-based CCR Hash with High Security and Its ...
6. [2024/1272] An Improved Algorithm for Code Equivalence
7. [2024/1273] HyperPianist: Pianist with Linear-Time Prover via ...
8. [2024/1274] Generation of Authenticated Secret-Shared Scaled ...
9. [2024/1275] MIFARE Classic: exposing the static encrypted nonce ...
10. [2024/1276] A bound on the quantum value of all compiled ...
11. [2024/1277] Robust but Relaxed Probing Model
12. [2024/1278] Quantum Key Recovery Attacks on 4-round Iterated ...
13. [2024/1279] Improved Polynomial Division in Cryptography
14. [2024/1280] A Survey on SoC Security Verification Methods at ...
15. [2024/1281] Stackproofs: Private proofs of stack and contract ...
16. [2024/1282] $\mathsf{NTRU}\mathsf{+}\mathsf{PKE}$: Efficient ...
17. [2024/1283] Password-authenticated Cryptography from Consumable ...
18. [2024/1284] Plaintext-Ciphertext Matrix Multiplication and FHE ...
19. [2024/1285] Robust Multiparty Computation from Threshold ...
20. [2024/1286] Towards a Tightly Secure Signature in Multi-User ...
21. [2024/1287] Basic Lattice Cryptography: The concepts behind ...

## 2024/1267

* Title: Chrysalis Cipher Suite
* Authors: Ian Malloy, Dennis Hollenbeck
* [Permalink](https://eprint.iacr.org/2024/1267)
* [Download](https://eprint.iacr.org/2024/1267.pdf)

### Abstract

The formal verification of architectural strength in terms of computational complexity is achieved through reduction of the Non-Commutative Grothendieck problem in the form of a quadratic lattice. This multivariate form relies on equivalences derived from a k-clique problem within a multigraph. The proposed scheme reduces the k-clique problem as an input function, resulting in the generation of a quadratic used as parameters for the lattice. By Grothendieck’s inequality, the satisfiability of lattice constraints in terms of NP-Hard and NP-Complete bounds is provably congruent to a closest vector problem in the lattice. The base vectors of the resulting lattice are treated as a holomorphic vector bundle. From the resulting bilinear matrices, the tight hardness reduction of the closest vector problem as the shortest vector problem is introduced within the system. The derivation of the closest vector problem requires that the lattice is necessarily generated by a <0|1>-Matrix expressed as a quadratic. This vector bundle is denoted as
the unit ball with congruent topology to the Riemann sphere, symbolized as 𝒪. For the Grothendieck constraints, the relative vector norms necessarily result in satisfaction of NP-Hard requirements for shortest vector problems in the lattice.



## 2024/1268

* Title: Improved YOSO Randomness Generation with Worst-Case Corruptions
* Authors: Chen-Da Liu-Zhang, Elisaweta Masserova, João Ribeiro, Pratik Soni, Sri AravindaKrishnan Thyagarajan
* [Permalink](https://eprint.iacr.org/2024/1268)
* [Download](https://eprint.iacr.org/2024/1268.pdf)

### Abstract

We study the problem of generating public unbiased randomness in a distributed manner within the recent You Only Speak Once (YOSO) framework for stateless multiparty computation, introduced by Gentry et al. in CRYPTO 2021. Such protocols are resilient to adaptive denial-of-service attacks and are, by their stateless nature, especially attractive in permissionless environments. While most works in the YOSO setting focus on independent random corruptions, we consider YOSO protocols with worst-case corruptions, a model introduced by Nielsen et al. in CRYPTO 2022.

Prior work on YOSO public randomness generation with worst-case corruptions designed information-theoretic protocols for $t$ corruptions with either $n=6t+1$ or $n=5t$ roles, depending on the adversarial network model. However, a major drawback of these protocols is that their communication and computational complexities scale exponentially with $t$. In this work, we complement prior inefficient results by presenting and analyzing simple and efficient protocols for YOSO public randomness generation secure against worst-case corruptions in the computational setting. Our first protocol is based on publicly verifiable secret sharing and uses $n=3t+2$ roles. Since this first protocol requires setup and somewhat heavy cryptographic machinery, we also provide a second lighter protocol based on ElGamal commitments and verifiable secret sharing which uses $n=5t+4$ or $n=4t+4$ roles depending on the underlying network model. We demonstrate the practicality of our second protocol by showing experimental evaluations, significantly improving over prior proposed solutions for worst-case corruptions, especially in terms of transmitted data size.



## 2024/1269

* Title: Cryptographic Security through Kleene’s Theorem and Automata Theory
* Authors: Mike Wa Nkongolo
* [Permalink](https://eprint.iacr.org/2024/1269)
* [Download](https://eprint.iacr.org/2024/1269.pdf)

### Abstract

This study addresses the challenge of strengthening cryptographic security measures in the face of evolving cyber threats. The aim is to apply Kleene's Theorem and automata theory to improve the modeling and analysis of cybersecurity scenarios, focusing on the CyberMoraba game. Representing the game's strategic moves as regular expressions and mapping them onto finite automata provides a solid framework for understanding the interactions between attackers and defenders. This approach helps in identifying optimal strategies and predicting potential outcomes, which contributes to the development of stronger cryptographic security protocols. The research advances the theoretical use of automata theory in cybersecurity while offering practical insights into enhancing defense mechanisms against complex cyber attacks. This work connects theoretical computer science with practical cybersecurity, demonstrating the importance of automata theory in cryptology.



## 2024/1270

* Title: Meet-in-the-Middle Attack on 4+4 Rounds of SCARF under Single-Tweak Setting
* Authors: Siwei Chen, Kai Hu, Guozhen Liu, Zhongfeng Niu, Quan Quan Tan, Shichang Wang
* [Permalink](https://eprint.iacr.org/2024/1270)
* [Download](https://eprint.iacr.org/2024/1270.pdf)

### Abstract

\scarf, an ultra low-latency tweakable block cipher, is the first cipher designed for cache randomization.
The block cipher design is significantly different from the other common tweakable block ciphers; with a block size of only 10 bits, and yet the input key size is a whopping $240$ bits. Notably, the majority of the round key in its round function is absorbed into the data path through AND operations, rather than the typical XOR operations.
In this paper, we present a key-recovery attack on a round-reduced version of SCARF with 4 + 4 rounds under the single-tweak setting. Our attack is essentially a Meet-in-the-Middle (MitM) attack, where the matching phase is represented by a system of linear equations. Unlike the cryptanalysis conducted by the designers, our attack is effective under both security requirements they have outlined. The data complexity of our attack is $2^{10}$ plaintexts, with a time complexity of approximately $2^{60.63}$ 4-round of SCARF encryptions. It is important to note that our attack does not threaten the overall security of SCARF.



## 2024/1271

* Title: AES-based CCR Hash with High Security and Its Application to Zero-Knowledge Proofs
* Authors: Hongrui Cui, Chun Guo, Xiao Wang, Chenkai Weng, Kang Yang, Yu Yu
* [Permalink](https://eprint.iacr.org/2024/1271)
* [Download](https://eprint.iacr.org/2024/1271.pdf)

### Abstract

The recent VOLE-based interactive zero-knowledge (VOLE-ZK) protocols along with non-interactive zero-knowledge (NIZK) proofs based on MPC-in-the-Head (MPCitH) and VOLE-in-the-Head (VOLEitH) extensively utilize the commitment schemes, which adopt a circular correlation robust (CCR) hash function as the core primitive. Nevertheless, the state-of-the-art CCR hash construction by Guo et al. (S&P'20), building from random permutations, can only provide 128-bit security, when it is instantiated from AES. This brings about a gap between AES-based CCR hash function and high security (beyond 128-bit security).
   
In this paper, we fill this gap by constructing a new CCR hash function from AES, supporting three security levels (i.e., 128, 192 and 256). Using the AES-based CCR hash function, we present an all-but-one vector commitment (AVC) scheme, which constitutes a computationally intensive part of the NIZK proofs from MPCitH and VOLEitH, where these NIZK proofs can in turn be transformed into the promising post-quantum signature candidates. Furthermore, we obtain an efficient VOLE-ZK protocol with security levels higher than 128 from the CCR hash function. Our benchmark results show that the AES-based CCR hash function has a comparable performance with CCR hash functions based on Rijndael with larger block sizes, which is not standardized and has a limited application range. In the AVC context, the expensive commitment component instantiated with our AES-based CCR hash function improves the running time by a factor of $7 \sim 30 \times$, compared to the SHA3-based instantiation used in the recent post-quantum signature algorithm FAEST.



## 2024/1272

* Title: An Improved Algorithm for Code Equivalence
* Authors: Julian Nowakowski
* [Permalink](https://eprint.iacr.org/2024/1272)
* [Download](https://eprint.iacr.org/2024/1272.pdf)

### Abstract

We study the linear code equivalence problem (LEP) for linear $[n,k]$-codes over finite fields $\mathbb{F}_q$. Recently, Chou, Persichetti and Santini gave an elegant heuristic algorithm that solves LEP over large finite fields (with $q = \Omega(n)$) in time $2^{\frac{1}{2}\operatorname{H}\left(\frac{k}{n}\right)n}$, where $\operatorname{H}(\cdot)$ denotes the binary entropy function. However, for small finite fields, their algorithm can be significantly slower. In particular, for fields of constant size $q = \mathcal{O}(1)$, its runtime increases by an exponential factor $2^{\Theta(n)}$.
We present an improved and provably correct version of their algorithm, which achieves the desired runtime of $2^{\frac{1}{2}\operatorname{H}\left(\frac{k}{n}\right)n}$ for all finite fields of size $q \geq 7$. For a wide range of parameters, this improves over the runtime of all previously known algorithms by an exponential factor.



## 2024/1273

* Title: HyperPianist: Pianist with Linear-Time Prover via Fully Distributed HyperPlonk
* Authors: Chongrong Li, Yun Li, Pengfei Zhu, Wenjie Qu, Jiaheng Zhang
* [Permalink](https://eprint.iacr.org/2024/1273)
* [Download](https://eprint.iacr.org/2024/1273.pdf)

### Abstract

Zero-knowledge proofs allow one party to prove the truth of a statement without disclosing any extra information. Recent years have seen great improvements in zero-knowledge proofs. Among them, zero-knowledge SNARKs are notable for their compact and efficiently-verifiable proofs but face challenges with high prover costs for large-scale applications. To accelerate proof generation, Pianist (Liu et al., S&P 2024) proposes to distribute the proof generation process across multiple machines, and achieves a significant reduction in overall prover time. However, Pianist inherits the quasi-linear computational complexity from its underlying SNARK proof system Plonk, limiting its scalability and efficiency with large circuits.

In this paper, we introduce HyperPianist, a fully distributed proof system with linear-time prover complexity and logarithmic communication cost among distributed machines. Starting from deVirgo (Xie et al., CCS 2022), we study their distributed multivariate SumCheck protocol and achieve logarithmic communication cost by using an additively homomorphic multivariate polynomial commitment scheme in the distributed setting. Given the distributed SumCheck protocol, we then adapt HyperPlonk (Chen et al., EuroptCrypt 2023), a proof system based on multivariate polynomials, to the distributed setting without extra overhead for witness re-distribution. In addition, we propose a more efficient construction of lookup arguments based on Lasso (Setty et al., Eurocrypt 2024), and adapt it to the distributed setting to enhance HyperPianist and obtain HyperPianist+.



## 2024/1274

* Title: Generation of Authenticated Secret-Shared Scaled Unit Vectors for Beaver Triples
* Authors: Vincent Rieder
* [Permalink](https://eprint.iacr.org/2024/1274)
* [Download](https://eprint.iacr.org/2024/1274.pdf)

### Abstract

For secure multi-party computation in the line of the secret-sharing based
SPDZ protocol, actively secure multiplications consume correlated randomness
in the form of authenticated Beaver triples, which need to be generated in advance.
Although it is a well-studied problem, the generation of Beaver triples is
still a bottleneck in practice. In the two-party setting, the best solution with low
communication overhead is the protocol by Boyle et al. (Crypto 2020), which
is derived from the recent primitive of Pseudorandom Correlation Generators
(PCGs) (Crypto 2019). Their protocol requires less than 2 MB of communication
to generate about 100 MB of Beaver triples (per party). In this work, we
improve their protocol in terms of communication (7%), computation (20% for
its interactive phase), and the amount of correlated randomness consumed by
internal secure two-party computations (11% storage). To achieve our improvements,
we propose a novel actively secure protocol for the efficient generation of
(authenticated) secret-shared scaled unit vectors, which in general are the main
building blocks of current PCG protocols.



## 2024/1275

* Title: MIFARE Classic: exposing the static encrypted nonce variant
* Authors: Philippe Teuwen
* [Permalink](https://eprint.iacr.org/2024/1275)
* [Download](https://eprint.iacr.org/2024/1275.pdf)

### Abstract

MIFARE Classic smart cards, developed and licensed by NXP, are widely used but have been subjected to numerous attacks over the years. Despite the introduction of new versions, these cards have remained vulnerable, even in card-only scenarios. In 2020, the FM11RF08S, a new variant of MIFARE Classic, was released by the leading Chinese manufacturer of unlicensed "MIFARE compatible" chips. This variant features specific countermeasures designed to thwart all known card-only attacks and is gradually gaining market share worldwide.
In this paper, we present several attacks and unexpected findings regarding the FM11RF08S. Through empirical research, we discovered a hardware backdoor and successfully cracked its key. This backdoor enables any entity with knowledge of it to compromise all user-defined keys on these cards without prior knowledge, simply by accessing the card for a few minutes.
Additionally, our investigation into older cards uncovered another hardware backdoor key that was common to several manufacturers.



## 2024/1276

* Title: A bound on the quantum value of all compiled nonlocal games
* Authors: Alexander Kulpe, Giulio Malavolta, Connor Paddock, Simon Schmidt, Michael Walter
* [Permalink](https://eprint.iacr.org/2024/1276)
* [Download](https://eprint.iacr.org/2024/1276.pdf)

### Abstract

A compiler introduced by Kalai et al. (STOC'23) converts any nonlocal game into an interactive protocol with a single computationally-bounded prover. Although the compiler is known to be sound in the case of classical provers, as well as complete in the quantum case, quantum soundness has so far only been established for special classes of games. In this work, we establish a quantum soundness result for all compiled two-player nonlocal games. In particular, we prove that the quantum commuting operator value of the underlying nonlocal game is an upper bound on the quantum value of the compiled game. Our result employs techniques from operator algebras in a computational and cryptographic setting to establish information-theoretic objects in the asymptotic limit of the security parameter. It further relies on a sequential characterization of quantum commuting operator correlations which may be of independent interest.



## 2024/1277

* Title: Robust but Relaxed Probing Model
* Authors: Nicolai Müller, Amir Moradi
* [Permalink](https://eprint.iacr.org/2024/1277)
* [Download](https://eprint.iacr.org/2024/1277.pdf)

### Abstract

Masking has become a widely applied and heavily researched method to protect cryptographic implementations against SCA attacks. The success of masking is primarily attributed to its strong theoretical foundation enabling it to formally prove security by modeling physical properties through so-called probing models. Specifically, the robust $d$-probing model enables us to prove the security for arbitrarily masked hardware circuits, manually or with the assistance of automated tools, even when considering the imperfect nature of physical hardware, including the occurrence of physical defaults such as glitches. However, the generic strategy employed by the robust $d$-probing model comes with a downside: It tends to over-conservatively model the information leakage caused by glitches meaning that the robust $d$-probing model considers glitches that can never occur in practice. This implies that in theory, an adversary could gain more information than she would obtain in practice. From a designer's perspective, this entails that (1) securely designed hardware circuits may need to be withdrawn due to potential insecurity under the robust $d$-probing model and (2) designs that satisfy the security requirements of the robust $d$-probing model may incur unnecessary overhead, such as increased circuit size or latency.
In this work, we refine the formal treatment of glitches within the robust $d$-probing model to address glitches more accurately within a formal adversary model. Unlike the robust $d$-probing model, our approach considers glitches based on the operations performed and the data processed, ensuring that only manifesting glitches are accounted for. As a result, we introduce the RR $d$-probing model, a formal adversary model maintaining the same level of security as the robust $d$-probing model but without the overly conservative treatment of glitches. Leveraging our new model, we prove the security of \ac{LMDPL} gadgets, a class of physically secure gadgets reported as insecure based on the robust $d$-probing model. We provide manual proofs and automated security evaluations employing an updated version of PROLEAD capable of verifying the security of masked circuits under our new model.



## 2024/1278

* Title: Quantum Key Recovery Attacks on 4-round Iterated Even-Mansour with Two Keys
* Authors: Ravi Anand, Shibam Ghosh, Takanori Isobe, Rentaro Shiba
* [Permalink](https://eprint.iacr.org/2024/1278)
* [Download](https://eprint.iacr.org/2024/1278.pdf)

### Abstract

In this paper, we propose quantum key recovery attacks on 4-round iterated Even-Mansour (IEM) with a key schedule that applies two keys alternately.
We first show that a conditional periodic function such that one of the secret keys appears as a period conditionally can be constructed using the encryption function and internal permutations.
By applying the offline Simon's algorithm to this function, we construct a key recovery attack with a complexity of $O(\sqrt{N} \log N)$ for $N = 2^n$, where $n$ is the block size and one secret key size.
Using quantum queries, this attack outperforms the generic quantum attack, i.e., Grover's search which takes the time complexity of $O(N)$.  
Moreover, we propose the quantum version of the multibridge attack proposed by Dinur et al. in ASIACRYPT 2014 to analyze the 4-round IEM. As a result, we show that the quantum multibridge attack can achieve the optimal complexity of $O(N)$ even if we have only $O(1)$ data without quantum queries, while the classical attack requires $O(N)$ data to achieve the same time complexity.
Furthermore, we show that the quantum multibridge attack slightly outperforms Grover's search when considering the quantum circuit depth for these attacks.



## 2024/1279

* Title: Improved Polynomial Division in Cryptography
* Authors: Kostas Kryptos Chalkias, Charanjit Jutla, Jonas Lindstrom, Varun Madathil, Arnab Roy
* [Permalink](https://eprint.iacr.org/2024/1279)
* [Download](https://eprint.iacr.org/2024/1279.pdf)

### Abstract

Several cryptographic primitives, especially succinct proofs of various forms, transform the satisfaction of high-level properties to the existence of a polynomial quotient between a polynomial that interpolates a set of values with a cleverly arranged divisor. Some examples are SNARKs, like Groth16, and polynomial commitments, such as KZG. Such a polynomial division naively takes $O(n \log n)$ time with Fast Fourier Transforms, and is usually the asymptotic bottleneck for these computations.

Several works have targeted specific constructions to optimize these computations and trade-off one-time setup costs with faster online computation times. In this paper, we present a unified approach to polynomial division related computations for a diverse set of schemes. We show how our approach provides a common abstract lens which recasts and improves existing approaches. Additionally, we present benchmarks for the Groth16 and the KZG systems, illustrating the significant practical benefits of our approach in terms of speed, memory, and parallelizability. We get a speedup of $2\times$ over the state-of-the-art in computing all openings for KZG commitments and a speed-up of about $2-3\%$ for Groth16 proofs when compared against the Rust Arkworks implementation. Although our Groth16 speedup is modest, our approach supports twice the number of gates as Arkworks and SnarkJS as it avoids computations at higher roots of unity. Conversely this reduces the need for employing larger groups for bigger circuits.

Our core technical contributions are novel conjugate representations and compositions of the derivative operator and point-wise division under the Discrete Fourier Transform. These allow us to  leverage l'Hôpital's rule to efficiently compute polynomial division, where in the evaluation basis such divisions maybe of the form $0/0$. As a concrete example, our technique allows applying a Toeplitz-matrix transform to a vector of elliptic curve group elements using only $n\log{n}$ elliptic-curve scalar multiplcations, whereas earlier techniques can at best achieve
$\frac{3}{2}n\log{n}$ complexity. Our techniques are generic with potential applicability to many existing protocols.



## 2024/1280

* Title: A Survey on SoC Security Verification Methods at the Pre-silicon Stage
* Authors: Rasheed Kibria, Farimah Farahmandi, Mark Tehranipoor
* [Permalink](https://eprint.iacr.org/2024/1280)
* [Download](https://eprint.iacr.org/2024/1280.pdf)

### Abstract

This paper presents a survey of the state-of-the-art pre-silicon security verification techniques for System-on-Chip (SoC) designs, focusing on ensuring that designs, implemented in hardware description languages (HDLs) and synthesized circuits, meet security requirements before fabrication in semiconductor foundries. Due to several factors, pre-silicon security verification has become an essential yet challenging aspect of the SoC hardware lifecycle. The modern SoC design process often adheres to a design reuse philosophy, integrating multiple functional blocks or Intellectual Property (IP) cores sourced from various vendors onto a single chip. While beneficial for reducing costs and accelerating time-to-market, this approach introduces numerous untrustworthy third-party entities into the supply chain. It increases the potential for introducing security vulnerabilities significantly. Additionally, hardware fabrication, assembly, and testing are frequently outsourced to third-party entities, further exacerbating security risks. Moreover, the growing complexity of SoC designs leads to unanticipated interactions between hardware and software layers, creating potential gateways for attackers to exploit and steal confidential information from devices. In response to these challenges, recent years have seen a surge in the development of innovative SoC security verification techniques. This survey provides an overview of these methods, their high-level working principles, strengths, and weaknesses. By understanding these techniques, designers can better evaluate their effectiveness and select the most appropriate methods aligned with the specific security objectives for their SoC designs.



## 2024/1281

* Title: Stackproofs: Private proofs of stack and contract execution using Protogalaxy
* Authors: Liam Eagen, Ariel Gabizon, Marek Sefranek, Patrick Towa, Zachary J.. Williamson
* [Permalink](https://eprint.iacr.org/2024/1281)
* [Download](https://eprint.iacr.org/2024/1281.pdf)

### Abstract

The goal of this note is to describe and analyze a simplified variant of the zk-SNARK construction used in the Aztec protocol.
Taking inspiration from the popular notion of Incrementally Verifiable Computation[Val09] (IVC)
we define a related notion of $\textrm{Repeated Computation with Global state}$ (RCG). As opposed to IVC, in RCG we assume the computation terminates before proving starts, and in addition to the local transitions some global consistency checks of the whole computation are allowed. However, we require the space efficiency of the prover to be close to that of an IVC prover not required to prove this global consistency.
We show how RCG is useful for designing a proof system for a private smart contract system like Aztec.



## 2024/1282

* Title: $\mathsf{NTRU}\mathsf{+}\mathsf{PKE}$: Efficient Public-Key Encryption Schemes from the NTRU Problem
* Authors: Jonghyun Kim, Jong Hwan Park
* [Permalink](https://eprint.iacr.org/2024/1282)
* [Download](https://eprint.iacr.org/2024/1282.pdf)

### Abstract

We propose a new NTRU-based Public-Key Encryption (PKE) scheme called $\mathsf{NTRU+}\mathsf{PKE}$, which effectively incorporates the Fujisaki-Okamoto transformation for PKE (denoted as $\mathsf{FO}_{\mathsf{PKE}}$) to achieve chosen-ciphertext security in the Quantum Random Oracle Model (QROM). While $\mathsf{NTRUEncrypt}$, a first-round candidate in the NIST PQC standardization process, was proven to be chosen-ciphertext secure in the Random Oracle Model (ROM), it lacked corresponding security proofs for QROM. Our work extends the capabilities of the recent $\mathsf{ACWC}_{2}$ transformation, proposed by Kim and Park in 2023, by demonstrating that an $\mathsf{ACWC}_{2}$-transformed scheme can serve as a sufficient foundation for applying $\mathsf{FO}_\mathsf{PKE}$. Specifically, we show that the $\mathsf{ACWC}_{2}$-transformed scheme achieves (weak) $\gamma$-spreadness, an essential property for constructing an IND-CCA secure PKE scheme. Moreover, we provide the first proof of the security of $\mathsf{FO}_\mathsf{PKE}$ in the QROM. Finally, we show that $\mathsf{FO}_\mathsf{PKE}$ can be further optimized into a more efficient transformation, $\overline{\mathsf{FO}}_\mathsf{PKE}$, which eliminates the need for re-encryption during decryption. By instantiating an $\mathsf{ACWC}_{2}$-transformed scheme with appropriate parameterizations, we construct $\mathsf{NTRU+}\mathsf{PKE}$, which supports 256-bit message encryption. Our implementation results demonstrate that at approximately a classical 180-bit security level, $\mathsf{NTRU+}\mathsf{PKE}$ is about 1.8 times faster than \textsc{Kyber} + AES-256-GCM in AVX2 mode.



## 2024/1283

* Title: Password-authenticated Cryptography from Consumable Tokens
* Authors: Ghada Almashaqbeh
* [Permalink](https://eprint.iacr.org/2024/1283)
* [Download](https://eprint.iacr.org/2024/1283.pdf)

### Abstract

Passwords are widely adopted for user authentication in practice, which led to the question of whether we can bootstrap a strongly-secure setting based on them. Historically, this has been extensively studied for key exchange; bootstrap from a low-entropy password to a high entropy key securing the communication. Other instances include digital lockers, signatures, secret sharing, and encryption.

Motivated by a recent work on consumable tokens (Almashaqbeh et al., Eurocrypt 2022), we extend these efforts and investigate the unified notion of password-authenticated cryptography in which knowing a password allows executing cryptographic functionalities. Our model is resistant to exhaustive search attacks due to the self-destruction and unclonability properties of consumable tokens. We study two directions; the first is password-authenticated delegation of cryptographic capabilities in which a party can delegate her, e.g., signing or encryption/decryption, rights to another such that exercising the delegation requires knowing a password. The second direction is password-authenticated MPC, in which only participants who share the correct password can execute the MPC protocol. In both cases, an adversary who does not know the password can try a few guesses after which the functionality self-destructs.

We formally define the notions above and build constructions realizing them. Our primary goal in this work is examining the power of consumable tokens in building password-authenticated cryptography in terms of viable constructions and supported adversary models, and thus, outlining open problems and potential future work directions.



## 2024/1284

* Title: Plaintext-Ciphertext Matrix Multiplication and FHE Bootstrapping: Fast and Fused
* Authors: Youngjin Bae, Jung Hee Cheon, Guillaume Hanrot, Jai Hyun Park, Damien Stehlé
* [Permalink](https://eprint.iacr.org/2024/1284)
* [Download](https://eprint.iacr.org/2024/1284.pdf)

### Abstract

Homomorphically multiplying a plaintext matrix with a ciphertext matrix (PC-MM) is a central task for the private evaluation of transformers, commonly used for large language models. We provide several RLWE-based algorithms for PC-MM that consist of multiplications of plaintext matrices (PC-MM) and comparatively cheap pre-processing and post-processing steps: for small and large dimensions compared to the RLWE ring degree, and with and without precomputation.. For the algorithms with precomputation, we show how to perform a PC-MM with a single floating-point PP-MM of the same dimensions. This is particularly meaningful for practical purposes as a floating-point PC-MM can be implemented using high-performance BLAS libraries.

The algorithms rely on the multi-secret variant of RLWE, which allows to represent multiple ciphertexts more compactly. We give algorithms to convert from usual shared-secret RLWE ciphertexts to multi-secret ciphertexts and back. Further, we show that this format is compatible with homomorphic addition, plaintext-ciphertext multiplication, and key-switching. This in turn allows us to accelerate the slots-to-coeffs and coeffs-to-slots steps of CKKS bootstrapping when several ciphertexts are bootstrapped at once. Combining batch-bootstrapping with efficient PC-MM results in MaMBo (Matrix Multiplication Bootstrapping), a bootstrapping algorithm that can perform a PC-MM for a limited overhead.



## 2024/1285

* Title: Robust Multiparty Computation from Threshold Encryption Based on RLWE
* Authors: Antoine Urban, Matthieu Rambaud
* [Permalink](https://eprint.iacr.org/2024/1285)
* [Download](https://eprint.iacr.org/2024/1285.pdf)

### Abstract

We consider protocols for secure multi-party computation (MPC) built from FHE under honest majority, i.e., for $n=2t+1$ players of which $t$ are corrupt, that is robust. Surprisingly there exists no robust threshold FHE scheme based on BFV to design an MPC protocol. Precisely, all existing methods for generating a common relinearization key can abort as soon as one player deviates.. We solve this issue, with a new relinearization key (adapted from [CDKS19, CCS'19]) which we show how to securely generate in parallel of the threshold encryption key, in the same broadcast. We thus obtain the first robust threshold BFV scheme, moreover using only one broadcast for the generation of keys instead of two previously.

Of independent interest, as an optional alternative, we propose the first threshold FHE decryption enabling simultaneously:
(i) robustness over asynchronous channels with honest majority; (ii) tolerating a power-of-small-prime ciphertext modulus, e.g., $2^e$; and (iii) secret shares of sizes quasi-independent of $n$.



## 2024/1286

* Title: Towards a Tightly Secure Signature in Multi-User Setting with Corruptions Based on Search Assumptions
* Authors: Hirofumi Yoshioka, Wakaha Ogata, Keitaro Hashimoto
* [Permalink](https://eprint.iacr.org/2024/1286)
* [Download](https://eprint.iacr.org/2024/1286.pdf)

### Abstract

This paper is a report on how we tackled constructing a digital signature scheme whose multi-user security with corruption can be tightly reduced to search assumptions. We fail to (dis)prove the statement but obtain the following new results:

- We reveal two new properties of signature schemes whose security cannot be tightly reduced to standard assumptions.

- We construct a new signature scheme. Its multi-user security with corruption is reduced to the CDH assumption (in the ROM), and its reduction loss is independent of the number of users but depends on the number of RO queries.



## 2024/1287

* Title: Basic Lattice Cryptography: The concepts behind Kyber (ML-KEM) and Dilithium (ML-DSA)
* Authors: Vadim Lyubashevsky
* [Permalink](https://eprint.iacr.org/2024/1287)
* [Download](https://eprint.iacr.org/2024/1287.pdf)

### Abstract

This tutorial focuses on describing the fundamental mathematical concepts and design decisions used in the two ``main'' lattice schemes standardized by NIST and included in the CNSA 2.0 algorithmic suite.  They are the KEM / encryption scheme CRYSTALS-Kyber (ML-KEM)  and the signature scheme CRYSTALS-Dilithium (ML-DSA) . In addition, we will also give the main ideas behind other lattice-based KEMs like Frodo and NTRU.