## In this issue

1. [2024/90] Starlit: Privacy-Preserving Federated Learning to ...
2. [2024/91] On historical Multivariate Cryptosystems and their ...
3. [2024/92] Call Me By My Name: Simple, Practical Private ...
4. [2024/93] Short Code-based One-out-of-Many Proofs and ...
5. [2024/94] Chosen-Ciphertext Secure Dual-Receiver Encryption ...
6. [2024/95] ConvKyber: Unleashing the Power of AI Accelerators ...
7. [2024/96] Revisiting the security analysis of SNOVA
8. [2024/97] Improved All-but-One Vector Commitment with ...
9. [2024/98] Theoretical differential fault attacks on FLIP and ...
10. [2024/99] Snarktor: A Decentralized Protocol for Scaling ...
11. [2024/100] FiveEyes: Cryptographic Biometric Authentication ...
12. [2024/101] Unconditional Security using (Random) Anonymous ...
13. [2024/102] Laconic Branching Programs from the Diffie-Hellman ...
14. [2024/103] ChaCha related 64 bit oriented ARX cipher
15. [2024/104] AnonPSI: An Anonymity Assessment Framework for PSI
16. [2024/105] Differential cryptanalysis with SAT, SMT, MILP, and ...
17. [2024/106] A Trust-based Recommender System over Arbitrarily ...
18. [2024/107] ELEKTRA: Efficient Lightweight multi-dEvice Key ...
19. [2024/108] Some Improvements for the PIOP for ZeroCheck
20. [2024/109] Simpler and Faster BFV Bootstrapping for Arbitrary ...
21. [2024/110] Cryptanalysis of the SNOVA signature scheme
22. [2024/111] A Novel Power Analysis Attack against CRYSTALS- ...
23. [2024/112] pqm4: Benchmarking NIST Additional Post-Quantum ...
24. [2024/113] Improved Linear Key Recovery Attacks on PRESENT

## 2024/90

* Title: Starlit: Privacy-Preserving Federated Learning to Enhance Financial Fraud Detection
* Authors: Aydin Abadi, Bradley Doyle, Francesco Gini, Kieron Guinamard, Sasi Kumar Murakonda, Jack Liddell, Paul Mellor, Steven J. Murdoch, Mohammad Naseri, Hector Page, George Theodorakopoulos, Suzanne Weller
* [Permalink](https://eprint.iacr.org/2024/090)
* [Download](https://eprint.iacr.org/2024/090.pdf)

### Abstract

Federated Learning (FL) is a data-minimization approach enabling collaborative model training across diverse clients with local data, avoiding direct data exchange. However, state-of-the-art FL solutions to identify fraudulent financial transactions
exhibit a subset of the following limitations. They (1) lack a formal security definition and proof, (2) assume prior freezing of suspicious customers’ accounts by financial institutions (limiting the solutions’ adoption), (3) scale poorly, involving
either $O(n^2)$ computationally expensive modular exponentiation (where $n$ is the total number of financial institutions) or highly inefficient fully homomorphic encryption, (4) assume the parties have already completed the identity alignment phase,
hence excluding it from the implementation, performance evaluation, and security analysis, and (5) struggle to resist clients’ dropouts. This work introduces Starlit, a novel scalable privacy-preserving FL mechanism that overcomes these limitations. It
has various applications, such as enhancing financial fraud detection, mitigating terrorism, and enhancing digital health. We implemented Starlit and conducted a thorough performance analysis using synthetic data from a key player in global financial
transactions. The evaluation indicates Starlit’s scalability, efficiency, and accuracy.



## 2024/91

* Title: On historical Multivariate Cryptosystems and their restorations as instruments of Post-Quantum Cryptography
* Authors: Vasyl Ustimenko
* [Permalink](https://eprint.iacr.org/2024/091)
* [Download](https://eprint.iacr.org/2024/091.pdf)

### Abstract

The paper presents a short survey of the History of Multivariate Cryptography together with the usage of old broken multivariate digital signatures in the new protocol based cryptosystems constructed in terms of Noncommutative Cryptography. The general
schemes of New cryptosystems is a combinations of Eulerian maps and quadratic maps with their trapdoor accelerators, which are pieces of information such than the knowledge of them allow to compute the reimages in a polynomial time. These schemes are
illustrated by historical examples of Imai – Matsumoto multivariate digital signatures schemes and Unbalanced Oil and Vinegar Cryptosystems.



## 2024/92

* Title: Call Me By My Name: Simple, Practical Private Information Retrieval for Keyword Queries
* Authors: Sofía Celi, Alex Davidson
* [Permalink](https://eprint.iacr.org/2024/092)
* [Download](https://eprint.iacr.org/2024/092.pdf)

### Abstract

We introduce $\mathsf{ChalametPIR}$: a single-server Private Information Retrieval (PIR) scheme supporting fast, low-bandwidth keyword queries, with a conceptually very simple design. In particular, we develop a generic framework for converting PIR
schemes for index queries over flat arrays (based on the Learning With Errors problem) into keyword PIR. This involves representing a key-value map using any probabilistic filter that permits reconstruction of elements from inclusion queries (e.g. Cuckoo
filters). In particular, we make use of recently developed Binary Fuse filters to construct $\mathsf{ChalametPIR}$, with minimal efficiency blow-up compared with state-of-the-art index-based schemes (all costs bounded by a factor of \(\leq 1.08\)).
Furthermore, we show that $\mathsf{ChalametPIR}$ achieves runtimes and financial costs that are factors of between \(6\times\)-\(11\times\) and \(3.75\times\)-\(11.4\times\) more efficient, respectively, than state-of-the-art keyword PIR approaches, for
varying database configurations. Bandwidth costs are additionally reduced or remain competitive, depending on the configuration. Finally, we believe that our application of Binary Fuse filters in the cryptography setting may bring immediate independent
value towards developing efficient variants of other related primitives that benefit from using such filters.



## 2024/93

* Title: Short Code-based One-out-of-Many Proofs and Applications
* Authors: Xindong Liu, Li-Ping Wang
* [Permalink](https://eprint.iacr.org/2024/093)
* [Download](https://eprint.iacr.org/2024/093.pdf)

### Abstract

In this work, we propose two novel succinct one-out-of-many proofs from coding theory, which can be seen as extensions of the Stern's framework and Veron's framework from proving knowledge of a preimage to proving knowledge of a preimage for one
element in a set, respectively. The size of each proof is short and scales better with the size of the public set than the code-based accumulator in \cite{nguyen2019new}. Based on our new constructions, we further present a logarithmic-size ring
signature scheme and a logarithmic-size group signature scheme. Our schemes feature a short signature size, especially our group signature. To our best knowledge, it is the most compact code-based group signature scheme so far. At 128-bit security level,
our group signature size is about 144 KB for a group with $2^{20}$ members while the group signature size of the previously most compact code-based group signature constructed by the above accumulator exceeds 3200 KB.



## 2024/94

* Title: Chosen-Ciphertext Secure Dual-Receiver Encryption in the Standard Model Based on Post-Quantum Assumptions
* Authors: Laurin Benz, Wasilij Beskorovajnov, Sarai Eilebrecht, Roland Gröll, Maximilian Müller, Jörn Müller-Quade
* [Permalink](https://eprint.iacr.org/2024/094)
* [Download](https://eprint.iacr.org/2024/094.pdf)

### Abstract

Dual-receiver encryption (DRE) is a special form of public key encryption (PKE) that allows a sender to encrypt a message for two recipients. Without further properties, the difference between DRE and PKE is only syntactical. One such important property
is soundness, which requires that no ciphertext can be constructed such that the recipients decrypt to different plaintexts. Many applications rely on this property in order to realize more complex protocols or primitives. In addition, many of these
applications explicitly avoid the usage of the random oracle, which poses an additional requirement on a DRE construction. We show that all of the IND-CCA2 secure standard model DRE constructions based on post-quantum assumptions fall short of augmenting
the constructions with soundness and describe attacks thereon.
We then give an overview over all applications of IND-CCA2 secure DRE, group them into generic (i. e., applications using DRE as black-box) and non-generic applications and demonstrate that all generic ones require either soundness or public
verifiability.
Conclusively, we identify the gap of sound and IND-CCA2 secure DRE constructions based on post-quantum assumptions in the standard Model.
In order to fill this gap we provide two IND-CCA2 secure DRE constructions based on the standard post-quantum assumptions, Normal Form Learning With Errors (NLWE) and Learning Parity with Noise (LPN).



## 2024/95

* Title: ConvKyber: Unleashing the Power of AI Accelerators for Faster Kyber with Novel Iteration-based Approaches
* Authors: Tian Zhou, Fangyu Zheng, Guang Fan, Lipeng Wan, Wenxu Tang, Yixuan Song, Yi Bian, Jingqiang Lin
* [Permalink](https://eprint.iacr.org/2024/095)
* [Download](https://eprint.iacr.org/2024/095.pdf)

### Abstract

The remarkable performance capabilities of AI accelerators offer promising opportunities for accelerating cryptographic algorithms, particularly in the context of lattice-based cryptography. However, current approaches to leveraging AI accelerators often
remain at a rudimentary level of implementation, overlooking the intricate internal mechanisms of these devices. Consequently, a significant number of computational resources is underutilized.

In this paper, we present a comprehensive exploration of NVIDIA Tensor Cores and introduce a novel framework tailored specifically for Kyber. Firstly, we propose two innovative approaches that efficiently break down Kyber's NTT into iterative matrix
multiplications, resulting in approximately a 75% reduction in costs compared to the state-of-the-art scanning-based methods.Secondly, by reversing the internal mechanisms, we precisely manipulate the internal resources of Tensor Cores using assembly-
level code instead of inefficient standard interfaces, eliminating memory accesses and redundant function calls. Finally, building upon our highly optimized NTT, we provide a complete implementation for all parameter sets of Kyber. Our implementation
surpasses the state-of-the-art Tensor Core based work, achieving remarkable speed-ups of 1.93x, 1.65x, 1.22x and 3.55x for polyvec_ntt, KeyGen, Enc and Dec in Kyber-1024, respectively. Even when considering execution latency, our throughput-oriented full
Kyber implementation maintains an acceptable execution latency. For instance, the execution latency ranges from 1.02 to 5.68 milliseconds for Kyber-1024 on R3080 when achieving the peak throughput.



## 2024/96

* Title: Revisiting the security analysis of SNOVA
* Authors: Yasuhiko Ikematsu, Rika Akiyama
* [Permalink](https://eprint.iacr.org/2024/096)
* [Download](https://eprint.iacr.org/2024/096.pdf)

### Abstract

SNOVA is a multivariate signature scheme submitted to the ad- ditional NIST PQC standardization project started in 2022. SNOVA is con- structed by incorporating the structure of the matrix ring over a finite field into the UOV signature scheme, and the
core part of its public key is the UOV public key whose coefficients consist of matrices. As a result, SNOVA dramatically reduces the public key size compared to UOV. In this paper, we recall the construction of SNOVA, and reconsider its security
analysis. In particular, we investigate key recovery attacks applied to the core part of the public key of SNOVA in detail. Due to our analysis, we show that some pa- rameters of SNOVA submitted in the additional NIST PQC standardization do not satisfy
the claimed security levels.



## 2024/97

* Title: Improved All-but-One Vector Commitment with Applications to Post-Quantum Signatures
* Authors: Dung Bui, Kelong Cong, Cyprien Delpech de Saint Guilhem
* [Permalink](https://eprint.iacr.org/2024/097)
* [Download](https://eprint.iacr.org/2024/097.pdf)

### Abstract

Post-quantum digital signature schemes have recently received increased attention due to the NIST standardization project for additional signatures. MPC-in-the-Head and VOLE-in-the-Head are general techniques for constructing such signatures from zero-
knowledge proof systems. A common theme between the two is an all-but-one vector commitment scheme which internally uses GGM trees. This primitive is responsible for a significant part of the computational time during signing and verification.

A more efficient technique for constructing GGM trees is the half-tree technique, introduced by Guo et al. (Eurocrypt 2023). Our work builds an all-but-one vector commitment scheme from the half-tree technique, and further generalizes it to an all-but-\(\
tau\) vector commitment scheme. Crucially, our work avoids the use of the random oracle assumption in an important step, which means our binding proof is non-trivial and instead relies on the random permutation oracle. Since this oracle can be
instantiated using fixed-key AES which has hardware support, we achieve faster signing and verification times.

We integrate our vector commitment scheme into FAEST (faest.info), a round one candidate in the NIST standardization process, and demonstrates its performance with a prototype implementation. For \(\lambda = 128\), our experimental results show a nearly \
(3.5\)-fold improvement in signing and verification times.



## 2024/98

* Title: Theoretical differential fault attacks on FLIP and FiLIP
* Authors: Pierrick Méaux, Dibyendu Roy
* [Permalink](https://eprint.iacr.org/2024/098)
* [Download](https://eprint.iacr.org/2024/098.pdf)

### Abstract

In this article, we examine Differential Fault Attacks (DFA) targeting two stream ciphers, FLIP and FiLIP. We explore the fault model where an adversary flips a single bit of the key at an unknown position. Our analysis involves establishing complexity
bounds for these attacks, contingent upon the cryptographic parameters of the Boolean functions employed as filters and the key size.
Initially, we demonstrate how the concept of sensitivity enables the detection of the fault position using only a few keystream bits. This represents an enhancement over previous DFA methodologies applied to these ciphers. Subsequently, we leverage the
properties of the filter's derivatives to execute attacks. This approach is universally applicable to any filter, and we delineate specific attack strategies for the two function families previously implemented in these ciphers.



## 2024/99

* Title: Snarktor: A Decentralized Protocol for Scaling SNARKs Verification in Blockchains
* Authors: Alberto Garoffolo, Dmytro Kaidalov, Roman Oliynykov
* [Permalink](https://eprint.iacr.org/2024/099)
* [Download](https://eprint.iacr.org/2024/099.pdf)

### Abstract

The use of zero-knowledge Succinct Non-Interactive Arguments of Knowledge (zk-SNARK) and similar types of proofs has become increasingly popular as a solution for improving scalability, privacy, and interoperability of blockchain systems. However, even
with the most advanced proving systems, verifying a single SNARK proof can require a significant amount of computational resources making it expensive to be performed on-chain. This becomes a noticeable bottleneck in scaling SNARK-based applications.

Further efficiency improvement to avoid this bottleneck lies in utilizing distributed recursive proof composition to aggregate multiple existing proofs into one that verifies all underlying proofs.

Building upon this concept, we present a new protocol for decentralized recursive proof aggregation allowing one unique proof to aggregate many input proofs to be efficiently verified on-chain, increasing the throughput and cost efficiency of SNARK-based
blockchains. The protocol is designed for decentralized environments where independent actors (provers) can join and contribute to the proof generation process. We also present an incentive scheme for such actors. The protocol is abstract enough to be
used with a variety of proving systems that support recursive aggregation.



## 2024/100

* Title: FiveEyes: Cryptographic Biometric Authentication from the Iris
* Authors: Luke Demarest, Sohaib Ahmad, Sixia Chen, Benjamin Fuller, Alexander Russell
* [Permalink](https://eprint.iacr.org/2024/100)
* [Download](https://eprint.iacr.org/2024/100.pdf)

### Abstract

Despite decades of effort, a stubborn chasm exists between the theory and practice of device-level biometric authentication. Deployed authentication algorithms rely on data that leaks private information about the biometric; thus systems rely on
externalized security measures such as trusted execution environments. In particular, the authentication algorithms themselves provide no cryptographic security guarantees.

This is particularly frustrating given the long line of research that has developed theoretical tools---known as fuzzy extractors---that enable secure, privacy preserving biometric authentication with public enrollment data. Unfortunately, the best known
constructions involving these rigorous tools can only provide substantial true accept rates with an estimated security of $32$ bits for the iris (Simhadri et al., ISC 2019) and 45 bits for the face (Zhang, Cui, and Yu, ePrint 2021/1559).

This work introduces FiveEyes, an iris key derivation system that integrates an improved feature extractor with a fuzzy extractor that leverages a new mechanism, which we formally analyze, for selecting verification subsets based on statistics of the
iris. (These statistics are computed from a class disjoint dataset from our test set.) We present various parameter regimes in order to highlight different true accept rates:
1. $65$ bits of security (equivalent to $87$ bits with a password) at $12\%$ true accept rate, and
2. $50$ bits of security (equivalent to $72$ bits with a password) at $45\%$ true accept rate.
We remark that powerful techniques are known that amplify true accept rates (Davida et al., IEEE S&P 1998); in particular, for the first time these results indicate practical viability of biometric authentication with strongcryptographic security.



## 2024/101

* Title: Unconditional Security using (Random) Anonymous Bulletin Board
* Authors: Albert Yu, Hai H. Nguyen, Aniket Kate, Hemanta K. Maji
* [Permalink](https://eprint.iacr.org/2024/101)
* [Download](https://eprint.iacr.org/2024/101.pdf)

### Abstract

In a seminal work, Ishai et al. (FOCS–2006) studied the viability of designing unconditionally secure protocols for key agreement and secure multi-party computation (MPC) using an anonymous bulletin board (ABB) as a building block. While their results
establish the feasibility of key agreement and honest-majority MPC in the ABB model, the optimality of protocols with respect to their round and communication complexity is not studied. This paper enriches this study of unconditional security in the ABB
model in multiple ways.

- We present a key agreement protocol with a novel combinatorial insight to offer a 200% throughput over the (FOCS–2006) study; i.e., using the same number of messages, we can (almost) double the bit-length of the agreed key. We also prove the near
optimality of our approach.

- We offer unconditionally secure protocols for the (random) string oblivious transfer functionalities. We present a $1$-round chosen message random string oblivious transfer and show how to extend it to a non-interactive (random) string oblivious
transfer protocol and a $2$-round chosen message string oblivious transfer.

- We prove a $1$-round lower bound for BEC under certain conditions.

Central to our technical contributions is the abstraction of a distributional variant of the random ABB functionality. Investigating the concrete efficiency of founding MPC from this primitive leads to fascinating new mathematical challenges in well-
established MPC models, which will be of broader interest to the community.



## 2024/102

* Title: Laconic Branching Programs from the Diffie-Hellman Assumption
* Authors: Sanjam Garg, Mohammad Hajiabadi, Peihan Miao, Alice Murphy
* [Permalink](https://eprint.iacr.org/2024/102)
* [Download](https://eprint.iacr.org/2024/102.pdf)

### Abstract

Laconic cryptography enables secure two-party computation (2PC) on unbalanced inputs with asymptotically-optimal communication in just two rounds of communication. In particular, the receiver (who sends the first-round message) holds a long input and the
sender (who sends the second-round message) holds a short input, and the size of their communication to securely compute a function on their joint inputs only grows with the size of the sender's input and is independent of the receiver's input size.
The work on laconic oblivious transfer (OT) [Cho et al. CRYPTO 2017] and laconic private set intersection (PSI) [Alamati et al. TCC 2021] shows how to achieve secure laconic computation for OT and PSI from the Diffie-Hellman assumption.

In this work, we push the limits further and achieve laconic branching programs from the Diffie-Hellman assumption. In particular, the receiver holds a large branching program $P$ and the sender holds a short input $x$. We present a two-round 2PC
protocol that allows the receiver to learn $x$ iff $P(x) =1$, and nothing else. The communication only grows with the size of $x$ and the depth of $P$, and does not further depend on the size of $P$.



## 2024/103

* Title: ChaCha related 64 bit oriented ARX cipher
* Authors: Daniel Nager
* [Permalink](https://eprint.iacr.org/2024/103)
* [Download](https://eprint.iacr.org/2024/103.pdf)

### Abstract

A cipher scheme related to ChaCha with the variation of using 64 bit operations instead of 32 bits, and the same 512 bit state size, is presented. We will provide strong argumentation to assert that the same security of ChaCha can be obtained with half
number of instructions for the same number of 20 rounds. Also, an strategy to implement this cipher on SIMD extensions is presented, with a maximal throughput of about 3.37 bytes per cycle on a 256 bit SIMD extension with at least 11 vector registers.



## 2024/104

* Title: AnonPSI: An Anonymity Assessment Framework for PSI
* Authors: Bo Jiang, Jian Du, Qiang Yan
* [Permalink](https://eprint.iacr.org/2024/104)
* [Download](https://eprint.iacr.org/2024/104.pdf)

### Abstract

Private Set Intersection (PSI) is a widely used protocol that enables two parties to securely compute a function over the intersected part of their shared datasets and has been a significant research focus over the years. However, recent studies have
highlighted its vulnerability to Set Membership Inference Attacks (SMIA), where an adversary might deduce an individual's membership by invoking multiple PSI protocols. This presents a considerable risk, even in the most stringent versions of PSI, which
only return the cardinality of the intersection. This paper explores the evaluation of anonymity within the PSI context.
Initially, we highlight the reasons why existing works fall short in measuring privacy leakage, and subsequently propose two attack strategies that address these deficiencies. Furthermore, we provide theoretical guarantees on the performance of our
proposed methods.
In addition to these, we illustrate how the integration of auxiliary information, such as the sum of payloads associated with members of the intersection (PSI-SUM), can enhance attack efficiency.
We conducted a comprehensive performance evaluation of various attack strategies proposed utilizing two real datasets. Our findings indicate that the methods we propose markedly enhance attack efficiency when contrasted with previous research endeavors.
The effective attacking implies that depending solely on existing PSI protocols may not provide an adequate level of privacy assurance. It is recommended to combine privacy-enhancing technologies synergistically to enhance privacy protection even
further.



## 2024/105

* Title: Differential cryptanalysis with SAT, SMT, MILP, and CP: a detailed comparison for bit-oriented primitives
* Authors: Emanuele Bellini, Alessandro De Piccoli, Mattia Formenti, David Gerault, Paul Huynh, Simone Pelizzola, Sergio Polese, Andrea Visconti
* [Permalink](https://eprint.iacr.org/2024/105)
* [Download](https://eprint.iacr.org/2024/105.pdf)

### Abstract

SAT, SMT, MILP, and CP, have become prominent in the differential cryptanalysis of cryptographic primitives.
In this paper, we review the techniques for constructing differential characteristic search models in these four formalisms.
Additionally, we perform a systematic comparison encompassing over 20 cryptographic primitives and 16 solvers, on both easy and hard instances of
optimisation, enumeration and differential probability estimation problems.



## 2024/106

* Title: A Trust-based Recommender System over Arbitrarily Partitioned Data with Privacy
* Authors: Ibrahim Yakut, Huseyin Polat
* [Permalink](https://eprint.iacr.org/2024/106)
* [Download](https://eprint.iacr.org/2024/106.pdf)

### Abstract

Recommender systems are effective mechanisms for recommendations about what to watch, read, or taste based on user ratings about experienced products or services. To achieve higher quality recommendations, e-commerce parties may prefer to collaborate
over partitioned data. Due to privacy issues, they might hesitate to work in pairs
and some solutions motivate them to collaborate. This study examines how to estimate trust-based predictions on arbitrarily partitioned data in which two parties have ratings for similar sets of customers and items. A privacy-
preserving scheme is proposed, and it is justified that it efficiently offers trust-based predictions on partitioned data while preserving privacy.



## 2024/107

* Title: ELEKTRA: Efficient Lightweight multi-dEvice Key TRAnsparency
* Authors: Julia Len, Melissa Chase, Esha Ghosh, Daniel Jost, Balachandar Kesavan, Antonio Marcedone
* [Permalink](https://eprint.iacr.org/2024/107)
* [Download](https://eprint.iacr.org/2024/107.pdf)

### Abstract

Key Transparency (KT) systems enable service providers of end-to-end encrypted communication (E2EE) platforms to maintain a Verifiable Key Directory (VKD) that maps each user's identifier, such as a username or email address, to their identity public key(
s). Users periodically monitor the directory to ensure their own identifier maps to the correct keys, thus detecting any attempt to register a fake key on their behalf to Meddler-in-the-Middle (MitM) their communications.
We introduce and formalize a new primitive called Multi-Device Verifiable Key Directory (MVKD), which strengthens both the security, privacy, and usability guarantees of VKD by leveraging the multi-device setting.
We formalize three properties for a MVKD (completeness, extraction-based soundness, and privacy), striking a non-trivial balance between strong guarantees and the limitations imposed by a truly practical system.
We then present a new MVKD system called ELEKTRA. This system combines the core of the Keybase KT system (running in production since 2014) with ideas from SEEMless (Chase et. al., 2019) and RZKS (Chen et. al., 2022).
Our construction is the first to achieve the above multi-device guarantees while having formal security and privacy proofs. Finally, we implement ELEKTRA and present benchmarks demonstrating its practicality.



## 2024/108

* Title: Some Improvements for the PIOP for ZeroCheck
* Authors: Angus Gruen
* [Permalink](https://eprint.iacr.org/2024/108)
* [Download](https://eprint.iacr.org/2024/108.pdf)

### Abstract

Most multivariate proof systems require, at some point, an algebraic check against the rows of the trace. One popular protocol for this is known as zerocheck which is a sumcheck based protocol which proves a constraint function is zero over the $n$-
dimensional Boolean hypercube. One of the drawbacks of running zerocheck over a small field, is that it usually involves a large number of evaluations of the constraint polynomial over a cryptographically large extension field $\mathbb{G}$.

We describe several improvements to the zerocheck protocol over a small field $\mathbb{F}$ which both reduce the number of constraint evaluations the prover needs to perform and shifts some computation from the extension field back into the base field $
\mathbb{F}$. Specifically, for a table of length $2^n$, integer parameter $1\leq k \leq n$ and constraint function $C$ of degree $d$ with evaluation costs $C_{\mathbb{F}}, C_{\mathbb{G}}$ we show the protocol can be performed with prover cost roughly
\[
2^n\left(1 + \frac{C_{\mathbb{G}}}{2^k C_{\mathbb{F}}}\right)(d - 1)C_{\mathbb{F}}.
\]

To check the proof, the verifier needs to perform a single interpolation of degree $2^kd$ and $n$ interpolations of degree $d$. Thus varying $k$ allows for a tradeoff between prover and verifier cost.



## 2024/109

* Title: Simpler and Faster BFV Bootstrapping for Arbitrary Plaintext Modulus from CKKS
* Authors: Jaehyung Kim, Jinyeong Seo, Yongsoo Song
* [Permalink](https://eprint.iacr.org/2024/109)
* [Download](https://eprint.iacr.org/2024/109.pdf)

### Abstract

Bootstrapping is a key operation in fully homomorphic encryption schemes that enables the evaluation of arbitrary multiplicative depth circuits.
In the BFV scheme, bootstrapping corresponds to reducing the size of accumulated noise in lower bits while preserving the plaintext in the upper bits.
The previous instantiation of BFV bootstrapping is achieved through the digit extraction procedure.
However, its performance is highly dependent on the plaintext modulus, so only a limited form of the plaintext modulus, a power of a small prime number, was used for the efficiency of bootstrapping.

In this paper, we present a novel approach to instantiate BFV bootstrapping, distinct from the previous digit extraction-based method.
The core idea of our bootstrapping is to utilize CKKS bootstrapping as a subroutine, so the performance of our method mainly depends on the underlying CKKS bootstrapping rather than the plaintext modulus.

We implement our method at a proof-of-concept level to provide concrete benchmark results.
When performing the bootstrapping operation for a 51-bits plaintext modulus, our method improves the previous digit extraction-based method by a factor of 37.9 in latency and 29.4 in throughput.
Additionally, we achieve viable bootstrapping performance for large plaintext moduli, such as 144-bits and 234-bits, which has never been measured before.



## 2024/110

* Title: Cryptanalysis of the SNOVA signature scheme
* Authors: Peigen Li, Jintai Ding
* [Permalink](https://eprint.iacr.org/2024/110)
* [Download](https://eprint.iacr.org/2024/110.pdf)

### Abstract

SNOVA is a variant of a UOV-type signature scheme over a noncommutative ring. In this article, we demonstrate that certain
parameters provided by authors in SNOVA fail to meet the NIST security level, and the complexities are lower than those claimed by SNOVA.



## 2024/111

* Title: A Novel Power Analysis Attack against CRYSTALS-Dilithium Implementation
* Authors: Yong Liu, Yuejun Liu, Yongbin Zhou, Yiwen Gao, Zehua Qiao, Huaxin Wang
* [Permalink](https://eprint.iacr.org/2024/111)
* [Download](https://eprint.iacr.org/2024/111.pdf)

### Abstract


[continued in next message]

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