[digest] 2024 Week 14

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

1. [2024/493] Reckle Trees: Updatable Merkle Batch Proofs with ...
2. [2024/494] HW-token-based Common Random String Setup
3. [2024/495] Reducing Signature Size of Matrix-code-based ...
4. [2024/496] Two-Round Threshold Signature from Algebraic One- ...
5. [2024/497] On the Security of Data Markets and Private ...
6. [2024/498] Number-Theoretic Transform Architecture for Fully ...
7. [2024/499] CCA Secure Updatable Encryption from Non-Mappable ...
8. [2024/500] Side Channel Resistant Sphincs+
9. [2024/501] Anonymous Revocable Identity-Based Encryption ...
10. [2024/502] Best of Two Worlds: Efficient, Usable and Auditable ...
11. [2024/503] Two Levels are Better than One: Dishonest Majority ...
12. [2024/504] Polylogarithmic Proofs for Multilinears over Binary ...
13. [2024/505] RSA-Based Dynamic Accumulator without Hashing into ...
14. [2024/506] A Decentralized Federated Learning using Reputation
15. [2024/507] An Efficient SNARK for Field-Programmable and RAM ...
16. [2024/508] Secure Multi-Party Linear Algebra with Perfect ...
17. [2024/509] Distribution of cycles in supersingular ...
18. [2024/510] DoS-resistant Oblivious Message Retrieval from ...
19. [2024/511] A Black-box Attack on Fixed-Unitary Quantum ...
20. [2024/512] Single Trace is All It Takes: Efficient Side- ...
21. [2024/513] Quantum Implementation and Analysis of SHA-2 and SHA-3
22. [2024/514] Zero-Knowledge Proof Vulnerability Analysis and ...
23. [2024/515] Inject Less, Recover More: Unlocking the Potential ...
24. [2024/516] Similar Data is Powerful: Enhancing Inference ...
25. [2024/517] Fast pairings via biextensions and cubical arithmetic
26. [2024/518] Software-Defined Cryptography: A Design Feature of ...
27. [2024/519] On implementation of Stickel's key exchange ...
28. [2024/520] A note on securing insertion-only Cuckoo filters
29. [2024/521] LIT-SiGamal: An efficient isogeny-based PKE based ...
30. [2024/522] Cryptanalysis of Secure and Lightweight Conditional ...
31. [2024/523] Unbindable Kemmy Schmidt: ML-KEM is neither MAL- ...
32. [2024/524] A Time-Space Tradeoff for the Sumcheck Prover
33. [2024/525] Privacy Preserving Biometric Authentication for ...
34. [2024/526] Optimizing and Implementing Fischlin's Transform ...
35. [2024/528] The solving degrees for computing Gröbner bases of ...
36. [2024/529] Fully Homomorphic Training and Inference on Binary ...
37. [2024/530] An efficient key generation algorithm for GR-NTRU ...
38. [2024/531] Avoiding Trusted Setup in Isogeny-based Commitments
39. [2024/532] Analysing Cryptography in the Wild - A Retrospective
40. [2024/533] HyCaMi: High-Level Synthesis for Cache Side-Channel ...
41. [2024/534] CryptoVampire: Automated Reasoning for the Complete ...
42. [2024/535] NodeGuard: A Highly Efficient Two-Party Computation ...
43. [2024/536] Highly-Effective Backdoors for Hash Functions and ...

## 2024/493

* Title: Reckle Trees: Updatable Merkle Batch Proofs with Applications
* Authors: Charalampos Papamanthou, Shravan Srinivasan, Nicolas Gailly, Ismael Hishon-Rezaizadeh, Andrus Salumets, Stjepan Golemac
* [Permalink](https://eprint.iacr.org/2024/493)
* [Download](https://eprint.iacr.org/2024/493.pdf)

### Abstract

We propose Reckle trees, a new vector commitment based on succinct RECursive arguments and MerKLE trees. Reckle trees' distinguishing feature is their support for succinct batch proofs that are updatable - enabling new applications in the blockchain setting where a proof needs to be computed and efficiently maintained over a moving stream of blocks. Our technical approach is based on embedding the computation of the batch hash inside the recursive Merkle verification via a hash-based accumulator called canonical hashing. Due to this embedding, our batch proofs can be updated in logarithmic time, whenever a Merkle leaf (belonging to the batch or not) changes, by maintaining a data structure that stores previously-computed recursive proofs. Assuming enough parallelism, our batch proofs are also computable in $O(\log n)$ parallel time - independent of the size of the batch. As a natural extension of Reckle trees, we also introduce Reckle+ trees. Reckle+ trees provide updatable and succinct proofs for certain types of Map/Reduce computations. In this setting, a prover can commit to a memory $\mathsf{M}$ and produce a succinct proof for a Map/Reduce computation over a subset $I$ of $\mathsf{M}$. The proof can be efficiently updated whenever $I$ or $\mathsf{M}$ changes.

We present and experimentally evaluate two applications of Reckle+ trees, dynamic digest translation and updatable BLS aggregation. In dynamic digest translation we are maintaining a proof of equivalence between Merkle digests computed with different hash functions, e.g., one with a SNARK-friendly Poseidon and the other with a SNARK-unfriendly Keccak. In updatable BLS aggregation we maintain a proof for the correct aggregation of a $t$-aggregate BLS key, derived from a $t$-subset of a Merkle-committed set of individual BLS keys. Our evaluation using Plonky2 shows that Reckle trees and Reckle+ trees have small memory footprint, significantly outperform previous approaches in terms of updates and verification time, enable applications that were not possible before due to huge costs involved (Reckle trees are up to 200 times faster), and have similar aggregation performance with previous implementations of batch proofs.



## 2024/494

* Title: HW-token-based Common Random String Setup
* Authors: István Vajda
* [Permalink](https://eprint.iacr.org/2024/494)
* [Download](https://eprint.iacr.org/2024/494.pdf)

### Abstract

In the common random string model, the parties executing a protocol have access to a uniformly random bit string. It is known that under standard intractability assumptions, we can realize any ideal functionality with universally composable (UC) security if a trusted common random string (CrS) setup is available. It was always a question of where this CrS should come from since the parties provably could not compute it themselves. Trust assumptions are required, so minimizing the level of such trust is a fundamentally important task. Our goal is to design a CrS setup protocol under a weakened trust assumption.. We present an HW-token-based CrS setup for 2-party cryptographic protocols using a single token only. Our protocol is a UC-secure realization of ideal common random string functionality FCrS. We show the multiple-session security of the protocol and we also consider the multi-party extension of it.



## 2024/495

* Title: Reducing Signature Size of Matrix-code-based Signature Schemes
* Authors: Tung Chou, Ruben Niederhagen, Lars Ran, Simona Samardjiska
* [Permalink](https://eprint.iacr.org/2024/495)
* [Download](https://eprint.iacr.org/2024/495.pdf)

### Abstract

This paper shows novel techniques to reduce the signature size of the code-based signature schemes MEDS and ALTEQ, by a large factor. For both schemes, the signature size is dominated by the responses for rounds with nonzero challenges, and we reduce the signature size by reducing the size of these responses. For MEDS, each of the responses consists of $m^2 + n^2$ field elements,while in our new protocol each response consists of only $2k$ ($k$ is usually chosen to be close to $m$ and $n$) field elements. For ALTEQ, each of the responses consists of $n^2$ field elements, while in our new protocol each response consists of about $\sqrt{2} n^{3/2}$ field elements. In both underlying $\Sigma$-protocols of the schemes, the prover generates a random isometry and sends the corresponding isometry to the verifier as the response. Instead of doing this, in our new protocols, the prover derives an isometry from some random code words and their presumed (full or partial) images. The prover sends the corresponding code words and images to the verifier as the response, so that the verifier can derive an isometry in the same way. Interestingly, it turns out that each response takes much fewer field elements to represent in this way.



## 2024/496

* Title: Two-Round Threshold Signature from Algebraic One-More Learning with Errors
* Authors: Thomas Espitau, Shuichi Katsumata, Kaoru Takemure
* [Permalink](https://eprint.iacr.org/2024/496)
* [Download](https://eprint.iacr.org/2024/496.pdf)

### Abstract

Threshold signatures have recently seen a renewed interest due to applications in cryptocurrency while NIST has released a call for multi-party threshold schemes, with a deadline for submission expected for the first half of 2025. So far, all lattice-based threshold signatures requiring less than two-rounds are based on heavy tools such as (fully) homomorphic encryption (FHE) and homomorphic trapdoor commitments (HTDC). This is not unexpected considering that most efficient two-round signatures from classical assumptions either rely on idealized model such as algebraic group models or on one-more type assumptions, none of which we have a nice analogue in the lattice world.

In this work, we construct the first efficient two-round lattice-based threshold signature without relying on FHE or HTDC. It has an offline-online feature where the first round can be preprocessed without knowing message or the signer sets, effectively making the signing phase non-interactive. The signature size is small and shows great scalability. For example, even for a threshold as large as 1024 signers, we achieve a signature size roughly 11 KB. At the heart of our construction is a new lattice-based assumption called the algebraic one-more learning with errors (AOMMLWE) assumption. We believe this to be a strong inclusion to our lattice toolkits with  an independent interest. We establish the selective security of AOMMLWE based on the standard MLWE and MSIS assumptions, and provide an in depth analysis of its adaptive security, which our threshold signature is based on.



## 2024/497

* Title: On the Security of Data Markets and Private Function Evaluation
* Authors: István Vajda
* [Permalink](https://eprint.iacr.org/2024/497)
* [Download](https://eprint.iacr.org/2024/497.pdf)

### Abstract

The income of companies working on data markets steadily grows year by year. Private function evaluation (PFE) is a valuable tool in solving corresponding security problems. The task of Controlled Private Function Evaluation and its relaxed version was introduced in [Horvath et.al., 2019]. In this article, we propose and examine several different approaches for such tasks with computational and information theoretical security against static corruption adversary. The latter level of security implies quantum-security. We also build known techniques and constructions into our solution where they fit into our tasks. The main cryptographic primitive, naturally related to the task is 1-out-of-n oblivious transfer. We use Secure Multiparty Computation techniques and in one of the constructions functional encryption primitive. The analysis of the computational complexity of the constructions shows that the considered tasks can efficiently be implemented, however it depends on the range of parameter values (e.g. size of database, size of the set of permitted function), the execution environment (e.g. concurrency) and of course on the level of security.



## 2024/498

* Title: Number-Theoretic Transform Architecture for Fully Homomorphic Encryption from Hypercube Topology
* Authors: Jingwei Hu, Yuhong Fang, Wangchen Dai
* [Permalink](https://eprint.iacr.org/2024/498)
* [Download](https://eprint.iacr.org/2024/498.pdf)

### Abstract

This paper introduces a high-performance and scalable hardware architecture designed for the Number-Theoretic Transform (NTT), a fundamental component extensively utilized in lattice-based encryption and fully homomorphic encryption schemes.

The underlying rationale behind this research is to harness the advantages of the hypercube topology. This topology serves to significantly diminish the volume of data exchanges required during each iteration of the NTT, reducing it to a complexity of $\Omega(\log N)$. Concurrently, it enables the parallelization of $N$ processing elements. This reduction in data exchange operations is of paramount importance. It not only facilitates the establishment of interconnections among the $N$ processing elements but also lays the foundation for the development of a high-performance NTT design. This is particularly valuable when dealing with large values of $N$.



## 2024/499

* Title: CCA Secure Updatable Encryption from Non-Mappable Group Actions
* Authors: Jonas Meers, Doreen Riepel
* [Permalink](https://eprint.iacr.org/2024/499)
* [Download](https://eprint.iacr.org/2024/499.pdf)

### Abstract

Ciphertext-independent updatable encryption (UE) allows to rotate encryption keys and update ciphertexts via a token without the need to first download the ciphertexts. Although, syntactically, UE is a symmetric-key primitive, ciphertext-independent UE with forward secrecy and post-compromise security is known to imply public-key encryption (Alamati, Montgomery and Patranabis, CRYPTO 2019).

Constructing post-quantum secure UE turns out to be a difficult task. While lattices offer the necessary homomorphic properties, the introduced noise allows only a bounded number of updates. Group actions have become an important alternative, however, their structure is limited. The only known UE scheme by Leroux and Roméas (IACR ePrint 2022/739) uses effective triple orbital group actions which uses additional algebraic structure of CSIDH. Using an ideal cipher, similar to the group-based scheme $\mathsf{SHINE}$ (Boyd et al., CRYPTO 2020), requires the group action to be mappable, a property that natural isogeny-based group actions do not satisfy. At the same time, other candidates based on non-commutative group actions suffer from linearity attacks.

For these reasons, we explicitly ask how to construct UE from group actions that are not mappable. As a warm-up, we present $\mathsf{BIN}\text{-}\mathsf{UE}$ which uses a bit-wise approach and is CPA secure based on the well-established assumption of weak pseudorandomness and in the standard model. We then construct the first actively secure UE scheme from post-quantum assumptions. Our scheme $\mathsf{COM}\text{-}\mathsf{UE}$ extends $\mathsf{BIN}\text{-}\mathsf{UE}$ via the Tag-then-Encrypt paradigm. We prove CCA security in the random oracle model based on a stronger computational assumption. We justify the hardness of our new assumption in the algebraic group action model.



## 2024/500

* Title: Side Channel Resistant Sphincs+
* Authors: Scott Fluhrer
* [Permalink](https://eprint.iacr.org/2024/500)
* [Download](https://eprint.iacr.org/2024/500.pdf)

### Abstract

Here is a potential way to create a SLH-DSA-like\cite{DraftFIPS205} key generation/signer that aspires to be resistant to DPA side channel attacks.
We say that it is “SLH-DSA-like”, because it does not follow the FIPS 205 method of generating signatures (in particular, it does not have the same mapping from private key, messages, opt\_rand to signatures), however it does generate public keys and signatures that are compatible with the standard signature verification method, and with the same security (with a small security loss against side channel attacks).  In our tests, this idea performed 1.7 times slower compared to an unprotected version.



## 2024/501

* Title: Anonymous Revocable Identity-Based Encryption Supporting Anonymous Revocation
* Authors: Kwangsu Lee
* [Permalink](https://eprint.iacr.org/2024/501)
* [Download](https://eprint.iacr.org/2024/501.pdf)

### Abstract

Anonymous identity-based encryption (AIBE) is an extension of identity-based encryption (IBE) that enhances the privacy of a ciphertext by providing ciphertext anonymity. In this paper, we introduce the concept of revocable IBE with anonymous revocation (RIBE-AR), which is capable of issuing an update key and hiding the revoked set of the update key that efficiently revokes private keys of AIBE. We first define the security models of RIBE-AR and propose an efficient RIBE-AR scheme in bilinear groups. Our RIBE-AR scheme is similar to the existing RIBE scheme in terms of efficiency, but is the first RIBE scheme to provide additional ciphertext anonymity and revocation privacy. We show that our RIBE-AR scheme provides the selective message privacy, selective identity privacy, and selective revocation privacy.



## 2024/502

* Title: Best of Two Worlds: Efficient, Usable and Auditable Biometric ABC on the Blockchain
* Authors: Neyire Deniz Sarier
* [Permalink](https://eprint.iacr.org/2024/502)
* [Download](https://eprint.iacr.org/2024/502.pdf)

### Abstract

In [1], two generic constructions for biometric-based non-transferable Attribute Based Credentials (biometric ABC) are presented, which offer different trade-offs between efficiency and trust assumptions. In this paper, we focus on the second scheme denoted as BioABC-ZK that tries to remove the strong (and unrealistic) trust assumption on the Reader R, and show that BioABC-ZK has a security flaw for a colluding R and Verifier V. Besides, BioABC-ZK lacks GDPR-compliance, which requires secure processing of biometrics, for instance in form of Fuzzy Extractors, as opposed to (i) storing the reference biometric template aBio in the user's mobile phone and (ii) processing of biometrics using an external untrusted R, whose foreign manufacturers are unlikely to adjust their products according to GDPR. The contributions of this paper are threefold. First, we review efficient biometric ABC schemes to identify the privacy-by-design criteria for them. In view of these principles, we propose a new architecture for biometric ABC of [2] by adapting the recently introduced core/helper setting of [3]. Briefly, a user in our modified setting is composed of a constrained core device (a SIM card) inside a helper device (a smart phone with dual SIM and face recognition feature), which -as opposed to [1]- does not need to store aBio. This way, the new design provides Identity Privacy without the need for an external R and/or a dedicated hardware per user such as a biometric smart card reader or a tamper proof smart card as in current hardware-bound credential systems. Besides, the new system maintains minimal hardware requirements on the SIM card -only responsible for storing ABC and helper data-, which results in easy adoption and usability without loosing efficiency, if recently introduced key derivation scheme of [4] and the modified ABC scheme of [2] are employed together. As a result, a total overhead of 500 milliseconds to a showing of a comparable non-biometric ABC is obtained instead of the 2.1 seconds in [1] apart from the removal of computationally expensive pairings. Finally, as different from [1], auditing is achieved via Blockchain instead of proving in zero-knowledge the actual biometric matching by the user to reveal malicious behavior of R and V.



## 2024/503

* Title: Two Levels are Better than One: Dishonest Majority MPC with $\widetilde{O}(|C|)$ Total Communication
* Authors: Alexander Bienstock, Kevin Yeo
* [Permalink](https://eprint.iacr.org/2024/503)
* [Download](https://eprint.iacr.org/2024/503.pdf)

### Abstract

In recent years, there has been tremendous progress in improving the communication complexity of dishonest majority MPC. In the sub-optimal corruption threshold setting, where $t<(1-\varepsilon)\cdot n$ for some constant $0<\varepsilon\leq 1/2$, the recent works Sharing Transformation (Goyal $\textit{et al.}$, CRYPTO'22) and SuperPack (Escudero $\textit{et al.}$, EUROCRYPT'23) presented protocols with information-theoretic online phases achieving $O(1)$ communication per multiplication gate, across all parties. However, the former assumes that their offline phase is instantiated by a trusted party, while the latter instantiates their offline phase with $\Omega(n)$ communication per multiplication gate assuming oblivious linear evaluation (OLE) correlations.

In this work, we present a dishonest majority MPC protocol for $t< (1-\varepsilon)\cdot n$ with $\widetilde{O}(1)$ total communication per multiplication gate across both the offline and online phases, or $\widetilde{O}(|C|)$ total communication for any arithmetic circuit $C$. To do so, we securely instantiate the offline phase of Sharing Transformation, assuming some OLE correlations. The major bottleneck in instantiating the offline phases of both Sharing Transformation and SuperPack is generating random packed beaver triples of the form $[\boldsymbol{a}], [\boldsymbol{b}], [\boldsymbol{c}]$, for random $\boldsymbol{a},\boldsymbol{b}\in\mathbb{F}^k$, and $\boldsymbol{c}=\boldsymbol{a}*\boldsymbol{b}\in\mathbb{F}^k$, where $k=\Omega(n)$ is the $\textit{packing parameter}$. We overcome this barrier by presenting a packed beaver triple protocol with $\widetilde{O}(n)$ total communication, or $\widetilde{O}(1)$ communication per underlying triple.

Our packed beaver triple protocol consists of two levels of randomness extraction. The first level uses a relaxation of super-invertible matrices that we introduce, called $\textit{weakly}$ super-invertible matrices, in which sub-matrices have sufficiently high (but not necessarily full) rank. This weakening enables  matrix constructions with only $O(n)$ non-zero entries, which is a primary reason for the efficiency of our protocol. Our second level of extraction is based on the $\textit{triple extraction}$ protocol of (Choudhury and Patra, Trans. Inform. Theory '17).



## 2024/504

* Title: Polylogarithmic Proofs for Multilinears over Binary Towers
* Authors: Benjamin E. Diamond, Jim Posen
* [Permalink](https://eprint.iacr.org/2024/504)
* [Download](https://eprint.iacr.org/2024/504.pdf)

### Abstract

We introduce a polylogarithmic-verifier polynomial commitment scheme for multilinears over towers of binary fields. To achieve this, we adapt an idea of Zeilberger, Chen and Fisch's BaseFold ('23) to the setting of binary towers, using FRI (ICALP '18)'s binary-field variant. In the process, we reinterpret Lin, Chung and Han (FOCS '14)'s novel polynomial basis so as to make apparent its compatibility with FRI. We moreover introduce a "packed" version of our protocol, which supports—with no embedding overhead during its commitment phase—multilinears over tiny fields (including that with just two elements). Our protocol leverages a new multilinear FRI-folding technique, and exploits the recent tensor proximity gap of Diamond and Posen (Commun. Cryptol. '24). We achieve concretely small proofs for enormous binary multilinears, shrinking the proofs of Diamond and Posen ('23) by an order of magnitude.



## 2024/505

* Title: RSA-Based Dynamic Accumulator without Hashing into Primes
* Authors: Victor Youdom Kemmoe, Anna Lysyanskaya
* [Permalink](https://eprint.iacr.org/2024/505)
* [Download](https://eprint.iacr.org/2024/505.pdf)

### Abstract

A cryptographic accumulator is a compact data structure for representing a set of elements coming from some domain. It allows for a compact proof of membership and, in the case of a universal accumulator, non-membership of an element x in the data structure. A dynamic accumulator, furthermore, allows elements to be added to and deleted from the accumulator.
Previously known RSA-based dynamic accumulators were too slow in practice because they required that an element in the domain be represented as a prime number. Accumulators based on settings other than RSA had other drawbacks such as requiring a prohibitively large common reference string or a trapdoor, or not permitting deletions.
In this paper, we construct RSA-based dynamic universal accumulators that do not require that the accumulated elements be represented as primes. We also show how to aggregate membership and non-membership witnesses and batch additions and deletions. We demonstrate that the efficiency gains compared to previously known RSA-based accumulators are substantial, and, for the first time, make cryptographic accumulators a viable candidate for a certificate revocation mechanism as part of a WebPKI-type system.



## 2024/506

* Title: A Decentralized Federated Learning using Reputation
* Authors: Olive Chakraborty, Aymen Boudguiga
* [Permalink](https://eprint.iacr.org/2024/506)
* [Download](https://eprint.iacr.org/2024/506.pdf)

### Abstract

Nowadays Federated learning (FL) is established as one of the best techniques for collaborative machine learning. It allows a set of clients to train a common model without disclosing their sensitive and private
dataset to a coordination server. The latter is in charge of the model aggregation. However, FL faces some problems, regarding the security of updates, integrity of computation and the availability of a server.
In this paper, we combine some new ideas like clients’ reputation with techniques like secure aggregation using Homomorphic Encryption and verifiable secret sharing using Multi-Party Computation techniques to design a decentralized FL system that addresses the issues of  incentives, security and availability amongst others. One of the original contributions of this work is the new leader election protocol which uses a secure shuffling and is based on a proof of reputation. Indeed, we propose to select an aggregator among the clients participating to
the FL training using their reputations. That is, we estimate the reputation of each client at every FL iteration and then we select the next round aggregator from the set of clients with the best reputations. As such, we remove misbehaving clients (e.g., byzantines) from the list of clients eligible for the role of aggregation server.



## 2024/507

* Title: An Efficient SNARK for Field-Programmable and RAM Circuits
* Authors: Jehyuk Jang, Jamie Judd
* [Permalink](https://eprint.iacr.org/2024/507)
* [Download](https://eprint.iacr.org/2024/507.pdf)

### Abstract

The advancement of succinct non-interactive argument of knowledge (SNARK) with constant proof size has significantly enhanced the efficiency and privacy of verifiable computation. Verifiable computation finds applications in distributed computing networks, particularly in scenarios where nodes cannot be generally trusted, such as blockchains. However, fully harnessing the efficiency of SNARK becomes challenging when the computing targets in the network change frequently, as the SNARK verification can involve some untrusted preprocess of the target, which is expected to be reproduced by other nodes. This problem can be addressed with two approaches: One relieves the reproduction overhead by reducing the dimensionality of preprocessing data; The other utilizes verifiable machine computation, which eliminates the dependency on preprocess at the cost of increased overhead to SNARK proving and verification. In this paper, we propose a new SNARK with constant proof size applicable to both approaches. The proposed SNARK combines the efficiency of Groth16 protocol, albeit lacking universality for new problems, and the universality of PlonK protocol, albeit with significantly larger preprocessing data dimensions. Consequently, we demonstrate that our proposed SNARK maintains the efficiency and the universality while significantly reducing the dimensionality of preprocessing data. Furthermore, our SNARK can be seamlessly applied to the verifiable machine computation, requiring a proof size smaller about four to ten times than other related works.



## 2024/508

* Title: Secure Multi-Party Linear Algebra with Perfect Correctness
* Authors: Jules Maire, Damien Vergnaud
* [Permalink](https://eprint.iacr.org/2024/508)
* [Download](https://eprint.iacr.org/2024/508.pdf)

### Abstract

We present new secure multi-party computation protocols for linear algebra over a finite field, which improve the state-of-the-art in terms of security. We look at the case of \emph{unconditional security with perfect correctness}, i.e., information-theoretic security without errors. We notably propose an expected constant-round protocol for solving systems of $m$ linear equations in $n$ variables over $\mathbb{F}_q$ with expected complexity $O(k(n^{2.5} + m^{2.5}+n^2m^{0.5}))$ where $k > m(m+n)+1$ (complexity is measured in terms of the number of secure multiplications required). The previous proposals were not error-free: known protocols can indeed fail and thus reveal information with probability $\Omega(\textsf{poly}(m)/q)$. 
Our protocols are simple and rely on existing computer-algebra techniques, notably the Preparata-Sarwate algorithm, a simple but poorly known ``baby-step giant-step'' method for computing the characteristic polynomial of a matrix, and techniques due to Mulmuley for error-free linear algebra in positive characteristic.



## 2024/509

* Title: Distribution of cycles in supersingular $\ell$-isogeny graphs
* Authors: Eli Orvis
* [Permalink](https://eprint.iacr.org/2024/509)
* [Download](https://eprint.iacr.org/2024/509.pdf)

### Abstract

Recent work by Arpin, Chen, Lauter, Scheidler, Stange, and Tran counted the number of cycles of length $r$ in supersingular $\ell$-isogeny graphs. In this paper, we extend this work to count the number of cycles that occur along the spine. We provide formulas for both the number of such cycles, and the average number as $p \to \infty$, with $\ell$ and $r$ fixed. In particular, we show that when $r$ is not a power of $2$, cycles of length $r$ are disproportionately likely to occur along the spine. We provide experimental evidence that this result holds in the case that $r$ is a power of $2$ as well.



## 2024/510

* Title: DoS-resistant Oblivious Message Retrieval from Snake-eye Resistant PKE
* Authors: Zeyu Liu, Katerina Sotiraki, Eran Tromer, Yunhao Wang
* [Permalink](https://eprint.iacr.org/2024/510)
* [Download](https://eprint.iacr.org/2024/510.pdf)

### Abstract

Oblivious message retrieval (OMR) allows messages resource-limited recipients to outsource the message retrieval process without revealing which messages are pertinent to which recipient. Its realizations in recent works leave an open problem: can an OMR scheme be both practical and provably secure against spamming attacks from malicious senders (i.e., DoS-resistant) under standard assumptions?
   
In this paper, we first prove that a prior construction OMRp2 is DoS-resistant under a standard LWE assumption, resolving an open conjecture of prior works. Then, we present DoS-PerfOMR: a provably DoS-resistant OMR construction that is 12x faster than OMRp2, and (almost) matches the performance of the state-of-the-art OMR scheme that is not DoS-resistant.
   
As a building block, we analyze the snake-eye resistance property for general PKE schemes. We construct a new lattice-based PKE scheme, LWEmongrass that is provably snake-eye resistant and has better efficiency than the PVW scheme underlying OMRp2. We also show that the natural candidates (e.g., RingLWE PKE) are not snake-eye resistant.

Of independent interest, we introduce two variants of LWE with side information, as components towards proving the properties of LWEmongrass, and reduce standard LWE to them for the parameters of interest.



## 2024/511

* Title: A Black-box Attack on Fixed-Unitary Quantum Encryption Schemes
* Authors: Cezary Pilaszewicz, Lea R. Muth, Marian Margraf
* [Permalink](https://eprint.iacr.org/2024/511)
* [Download](https://eprint.iacr.org/2024/511.pdf)

### Abstract

We show how fixed-unitary quantum encryption schemes can be attacked in a black-box setting. We use an efficient technique to invert a unitary transformation on a quantum computer to retrieve an encrypted secret quantum state $\ket{\psi}$. This attack has a success rate of 100% and can be executed in constant time. We name a vulnerable scheme and suggest how to improve it to invalidate this attack. The proposed attack highlights the importance of carefully designing quantum encryption schemes to ensure their security against quantum adversaries, even in a black-box setting.



## 2024/512

* Title: Single Trace is All It Takes: Efficient Side-channel Attack on Dilithium
* Authors: Zehua Qiao, Yuejun Liu, Yongbin Zhou, Yuhan Zhao, Shuyi Chen
* [Permalink](https://eprint.iacr.org/2024/512)
* [Download](https://eprint.iacr.org/2024/512.pdf)

### Abstract

As the National Institute of Standards and Technology (NIST) concludes its post-quantum cryptography (PQC) competition, the winning algorithm, Dilithium, enters the deployment phase in 2024. This phase underscores the importance of conducting thorough practical security evaluations. Our study offers an in-depth side-channel analysis of Dilithium, showcasing the ability to recover the complete private key, ${s}_1$, within ten minutes using just two signatures and achieving a 60 success rate with a single signature. We focus on analyzing the polynomial addition in Dilithium, $z=y+{cs}_1$, by breaking down the attack into two main phases: the recovery of $y$ and ${cs}_1$ through side-channel attacks, followed by the resolution of a system of error-prone equations related to ${cs}_1$. Employing Linear Regression-based profiled attacks enables the successful recovery of the full $y$ value with a 40% success rate without the necessity for initial filtering. The extraction of ${cs}_1$ is further improved using a CNN model, which boasts an average success rate of 75%. A significant innovation of our research is the development of a constrained optimization-based residual analysis technique. This method efficiently recovers ${s}_1$ from a large set of error-containing equations concerning ${cs}_1$, proving effective even when only 10% of the equations are accurate. We conduct a practical attack on the Dilithium2 implementation on an STM32F4 platform, demonstrating that typically two signatures are sufficient for complete private key recovery, with a single signature sufficing in optimal conditions.. Using a general-purpose PC, the full private key can be reconstructed in ten minutes.



## 2024/513

* Title: Quantum Implementation and Analysis of SHA-2 and SHA-3
* Authors: Kyungbae Jang, Sejin Lim, Yujin Oh, Anubhab Baksi, Sumanta Chakraborty, Hwajeong Seo
* [Permalink](https://eprint.iacr.org/2024/513)
* [Download](https://eprint.iacr.org/2024/513.pdf)

### Abstract

Quantum computers have the potential to solve hard problems that are nearly impossible to solve by classical computers, this has sparked a surge of research to apply quantum technology and algorithm against the cryptographic systems to evaluate for its quantum resistance. In the process of selecting post-quantum standards, NIST categorizes security levels based on the complexity that quantum computers would require to crack AES encryption (levels 1, 3, and 5) and SHA-2 or SHA-3 (levels 2 and 4).

In assessing the security strength of cryptographic algorithms against quantum threats, accurate predictions of quantum resources are crucial. Following the work of Jaques et al. in Eurocrypt 2020, NIST  estimated security levels 1, 3, and 5, corresponding to quantum circuit size for finding the key for AES-128, AES-192, and AES-256, respectively. This work has been recently followed-up by Huang et al. (Asiacrypt'22) and Liu et al. (Asiacrypt'23). However, for levels 2 and 4, which relate to the collision finding for the SHA-2 and SHA-3 hash functions, quantum attack complexities are probably not well-studied.

In this paper, we present novel techniques for optimizing the quantum circuit implementations for SHA-2 and SHA-3 algorithms in all the categories specified by NIST. After that, we evaluate the quantum circuits of target cryptographic hash functions for quantum collision search. Finally, we define the optimal quantum attack complexity for levels 2 and 4, and comment on the security strength of the extended level. We present new concepts to optimize the quantum circuits at the component level and the architecture level.



## 2024/514

* Title: Zero-Knowledge Proof Vulnerability Analysis and Security Auditing
* Authors: Xueyan Tang, Lingzhi Shi, Xun Wang, Kyle Charbonnet, Shixiang Tang, Shixiao Sun
* [Permalink](https://eprint.iacr.org/2024/514)
* [Download](https://eprint.iacr.org/2024/514.pdf)

### Abstract

Zero-Knowledge Proof (ZKP) technology marks a revolutionary advancement in the field of cryptography, enabling the verification of certain information ownership without revealing any specific details. This technology, with its paradoxical yet powerful characteristics, provides a solid foundation for a wide range of applications, especially in enhancing the privacy and security of blockchain technology and other cryptographic systems. As ZKP technology increasingly becomes a part of the blockchain infrastructure, its importance for security and integrity becomes more pronounced. However, the complexity of ZKP implementation and the rapid iteration of the technology introduce various vulnerabilities, challenging the privacy and security it aims to offer.

This study bases on the integrity, soundness, and zero-knowledge properties of ZKP to meticulously classify existing vulnerabilities and deeply explores multiple categories of vulnerabilities, including integrity issues, soundness problems, information leakage, and non-standardized cryptographic implementations. Furthermore, we propose a set of defense strategies that include a rigorous security audit process and a robust distributed network security ecosystem. This audit strategy employs a divide-and-conquer approach, segmenting the project into different levels, from the application layer to the platform-nature infrastructure layer, using threat modeling, linear code checking, and internal cross-review, among other means, aimed at comprehensively identifying vulnerabilities in ZKP circuits, revealing design flaws in ZKP applications, and accurately identifying inaccuracies in the integration process of ZKP primitives.



## 2024/515

* Title: Inject Less, Recover More: Unlocking the Potential of Document Recovery in Injection Attacks Against SSE
* Authors: Manning Zhang, Zeshun Shi, Huanhuan Chen, Kaitai Liang
* [Permalink](https://eprint.iacr.org/2024/515)
* [Download](https://eprint.iacr.org/2024/515.pdf)

### Abstract

Searchable symmetric encryption has been vulnerable to inference attacks that rely on uniqueness in leakage patterns. However, many keywords in datasets lack distinctive leakage patterns, limiting the effectiveness of such attacks. The file injection attacks, initially proposed by Cash et al. (CCS 2015), have shown impressive performance with 100% accuracy and no prior knowledge requirement. Nevertheless, this attack fails to recover queries with underlying keywords not present in the injected files. To address these limitations, our research introduces a novel attack strategy called LEAP-Hierarchical Fusion Attack (LHFA) that combines the strengths of both file injection attacks and inference attacks. Before initiating keyword injection, we introduce a new approach for inert/active keyword selection. In the phase of selecting injected keywords, we focus on keywords without unique leakage patterns and recover them, leveraging their presence for document recovery. Our goal is to achieve an amplified effect in query recovery. We demonstrate a minimum query recovery rate of 1.3 queries per injected keyword with a 10% data leakage of a real-life dataset, and initiate further research to overcome challenges associated with non-distinctive keywords.



## 2024/516

* Title: Similar Data is Powerful: Enhancing Inference Attacks on SSE with Volume Leakages
* Authors: Björn Ho, Huanhuan Chen, Zeshun Shi, Kaitai Liang
* [Permalink](https://eprint.iacr.org/2024/516)
* [Download](https://eprint.iacr.org/2024/516.pdf)

### Abstract

Searchable symmetric encryption (SSE) schemes provide users with the ability to perform keyword searches on encrypted databases without the need for decryption. While this functionality is advantageous, it introduces the potential for inadvertent information disclosure, thereby exposing SSE systems to various types of attacks. In this work, we introduce a new inference attack aimed at enhancing the query recovery accuracy of RefScore (presented at USENIX 2021). The proposed approach capitalizes on both similar data knowledge and an additional volume leakage as auxiliary information, facilitating the extraction of keyword matches from leaked data. Empirical evaluations conducted on multiple real-world datasets demonstrate a notable enhancement in query recovery accuracy, up to 19.5%. We also analyze the performance of the proposed attack in the presence of diverse countermeasures.



## 2024/517

* Title: Fast pairings via biextensions and cubical arithmetic
* Authors: Damien Robert
* [Permalink](https://eprint.iacr.org/2024/517)
* [Download](https://eprint.iacr.org/2024/517.pdf)

### Abstract

Biextensions associated to line bundles on abelian varieties allows to reinterpret the usual Weil, Tate, Ate, optimal Ate, \ldots, pairings as monodromy pairings. We introduce a cubical arithmetic, derived from the canonical cubical torsor structure of these line bundles, to obtain an efficient arithmetic of these biextensions.

This unifies and extends Miller's standard algorithm to compute pairings along with other algorithms like elliptic nets and theta functions, and allows to adapt these algorithms to pairings on any model of abelian varieties with a polarisation $\Phi_D$, as long as we have an explicit theorem of the square for $D$.

In particular, we give explicit formulas for the arithmetic of the biextension (and cubical torsor structure) associated to the divisor $D=2(0_E)$ on an elliptic curve. We derive very efficient pairing formulas on elliptic curves and Kummer lines. Notably for generic pairings on Montgomery curves, our cubical biextension ladder algorithm to compute pairings costs only $15M$ by bits, which as far as I know is faster than any pairing doubling formula in the literature.



## 2024/518

* Title: Software-Defined Cryptography: A Design Feature of Cryptographic Agility
* Authors: Jihoon Cho, Changhoon Lee, Eunkyung Kim, Jieun Lee, Beumjin Cho
* [Permalink](https://eprint.iacr.org/2024/518)
* [Download](https://eprint.iacr.org/2024/518.pdf)

### Abstract

Cryptographic agility, or crypto-agility, is a design feature that enables agile updates to new cryptographic algorithms and standards without the need to modify or replace the surrounding infrastructure. This paper examines the prerequisites for crypto-agility and proposes its desired design feature. More specifically, we investigate the design characteristics of widely deployed cybersecurity paradigms, i.e., zero trust, and apply its design feature to crypto-agility, achieving greater visibility and automation in cryptographic management.



## 2024/519

* Title: On implementation of Stickel's key exchange protocol over max-min and max-$T$ semirings
* Authors: Sulaiman Alhussaini, Serge˘ı Sergeev
* [Permalink](https://eprint.iacr.org/2024/519)
* [Download](https://eprint.iacr.org/2024/519.pdf)

### Abstract

Given that the tropical Stickel protocol and its variants are all vulnerable to the generalized Kotov-Ushakov attack, we suggest employing the max-min semiring and, more generally, max-$T$ semiring where the multiplication is based on a $T-$norm, as a framework to implement the Stickel protocol. While the Stickel protocol over max-min semiring or max-$T$ semiring remains susceptible to a form of Kotov-Ushakov attack, we demonstrate that it exhibits significantly increased resistance against this attack when compared to the tropical (max-plus) implementation.



## 2024/520

* Title: A note on securing insertion-only Cuckoo filters
* Authors: Fernando Virdia, Mia Filić
* [Permalink](https://eprint.iacr.org/2024/520)
* [Download](https://eprint.iacr.org/2024/520.pdf)

### Abstract

We describe a small tweak to Cuckoo filters that allows securing them under insertions using the techniques from Filić et al. (ACM CCS 2022), without the need for an outer PRF call.



## 2024/521

* Title: LIT-SiGamal: An efficient isogeny-based PKE based on a LIT diagram
* Authors: Tomoki Moriya
* [Permalink](https://eprint.iacr.org/2024/521)
* [Download](https://eprint.iacr.org/2024/521.pdf)

### Abstract

In this paper, we propose a novel isogeny-based public key encryption (PKE) scheme named LIT-SiGamal. This is based on a LIT diagram and SiGamal. SiGamal is an isogeny-based PKE scheme that uses a commutative diagram with an auxiliary point. LIT-SiGamal uses a LIT diagram which is a commutative diagram consisting of large-degree horizontal isogenies and relatively small-degree vertical isogenies, while the original SiGamal uses a CSIDH diagram.

A strength of LIT-SiGamal is efficient encryption and decryption. QFESTA is an isogeny-based PKE scheme proposed by Nakagawa and Onuki, which is a relatively efficient scheme in isogeny-based PKE schemes. In our experimentation with our proof-of-concept implementation, the computational time of the encryption of LIT-SiGamal is as efficient as that of QFESTA, and that of the decryption of LIT-SiGamal is about $5$x faster than that of QFESTA.



## 2024/522

* Title: Cryptanalysis of Secure and Lightweight Conditional Privacy-Preserving Authentication for Securing Traffic Emergency Messages in VANETs
* Authors: Mahender Kumar
* [Permalink](https://eprint.iacr.org/2024/522)
* [Download](https://eprint.iacr.org/2024/522.pdf)

### Abstract

In their paper, Wei et al. proposed a lightweight protocol for conditional privacy-preserving authentication in VANET. The protocol aims to achieve ultra-low transmission delay and efficient system secret key (SSK) updating. Their protocol uses a signature scheme with message recovery to authenticate messages. This scheme provides security against adaptively chosen message attacks. However, our analysis reveals a critical vulnerability in the scheme. It is susceptible to replay attacks, meaning a malicious vehicle can replay a message multiple times at different timestamps. This action undermines the overall effectiveness of conditional privacy. We suggest possible solutions to address these vulnerabilities and enhance the security of VANET communication.



## 2024/523

* Title: Unbindable Kemmy Schmidt: ML-KEM is neither MAL-BIND-K-CT nor MAL-BIND-K-PK
* Authors: Sophie Schmieg
* [Permalink](https://eprint.iacr.org/2024/523)
* [Download](https://eprint.iacr.org/2024/523.pdf)

### Abstract

In "Keeping up with the KEMs" Cremers et al. introduced various binding models for KEMs. The authors show that ML-KEM is LEAK-BIND-K-CT and LEAK-BIND-K-PK, i.e. binding the ciphertext and the public key in the case of an adversary having access, but not being able to manipulate the key material. They further conjecture that ML-KEM also has MAL-BIND-K-PK, but not MAL-BIND-K-CT, the binding of public key or ciphertext to the shared secret in the case of an attacker with the ability to manipulate the key material.
This short paper demonstrates that ML-KEM does neither have MALBIND-K-CT nor MAL-BIND-K-PK, due to the attacker being able to produce mal-formed private keys, giving concrete examples for both. We also suggest mitigations, and sketch a proof for binding both ciphertext and public key when the attacker is not able to manipulate the private key as liberally.



## 2024/524

* Title: A Time-Space Tradeoff for the Sumcheck Prover
* Authors: Alessandro Chiesa, Elisabetta Fedele, Giacomo Fenzi, Andrew Zitek-Estrada
* [Permalink](https://eprint.iacr.org/2024/524)
* [Download](https://eprint.iacr.org/2024/524.pdf)

### Abstract

The sumcheck protocol is an interactive protocol for verifying the sum of a low-degree polynomial over a hypercube. This protocol is widely used in practice, where an efficient implementation of the (honest) prover algorithm is paramount. Prior work contributes highly-efficient prover algorithms for the notable special case of multilinear polynomials (and related settings): [CTY11] uses logarithmic space but runs in superlinear time; in contrast, [VSBW13] runs in linear time but uses linear space.
In this short note, we present a family of prover algorithms for the multilinear sumcheck protocol that offer new time-space tradeoffs. In particular, we recover the aforementioned algorithms as special cases. Moreover, we provide an efficient implementation of the new algorithms, and our experiments show that the asymptotics translate into new concrete efficiency tradeoffs.



## 2024/525

* Title: Privacy Preserving Biometric Authentication for Fingerprints and Beyond
* Authors: Marina Blanton, Dennis Murphy
* [Permalink](https://eprint.iacr.org/2024/525)
* [Download](https://eprint.iacr.org/2024/525.pdf)

### Abstract

Biometric authentication eliminates the need for users to remember secrets and serves as a convenient mechanism for user authentication. Traditional implementations of biometric-based authentication store sensitive user biometry on the server and the server becomes an attractive target of attack and a source of large-scale unintended disclosure of biometric data. To mitigate the problem, we can resort to privacy-preserving computation and store only protected biometrics on the server. While a variety of secure computation techniques is available, our analysis of privacy-preserving biometric computation and biometric authentication constructions revealed that available solutions fall short of addressing the challenges of privacy-preserving biometric authentication. Thus, in this work we put forward new constructions to address the challenges.

Our solutions employ a helper server and use strong threat models, where a client is always assumed to be malicious, while the helper server can be semi-honest or malicious. We also determined that standard secure multi-party computation security definitions are insufficient to properly demonstrate security in the two-phase (enrollment and authentication) entity authentication application. We thus extend the model and formally show security in the multi-phase setting, where information can flow from one phase to another and the set of participants can change between the phases. We implement our constructions and show that they exhibit practical performance for authentication in real time.



## 2024/526

* Title: Optimizing and Implementing Fischlin's Transform for UC-Secure Zero-Knowledge
* Authors: Yi-Hsiu Chen, Yehuda Lindell
* [Permalink](https://eprint.iacr.org/2024/526)
* [Download](https://eprint.iacr.org/2024/526.pdf)

### Abstract

Fischlin's transform (CRYPTO 2005) is an alternative to the Fiat-Shamir transform that enables straight-line extraction when proving knowledge. In this work we focus on the problem of using the Fischlin transform to construct UC-secure zero-knowledge from Sigma protocols, since UC security -- that guarantees security under general concurrent composition -- requires straight-line (non-rewinding) simulators. We provide a slightly simplified transform that is much easier to understand, and present algorithmic and implementation optimizations that significantly improve the running time. It appears that the main obstacles to the use of Fischlin in practice is its computational cost and implementation complexity (with multiple parameters that need to be chosen). We provide clear guidelines and a simple methodology for choosing parameters, and show that with our optimizations the running-time is far lower than expected. For just one example, on a 2023 MacBook, the cost of proving the knowledge of discrete log with Fischlin is only 0.41ms (on a single core). We also extend the transform so that it can be applied to batch proofs, and show how this can be much more efficient than individually proving each statement. As a contribution of independent interest, we present a new algorithm for polynomial evaluation on any series of sequential points that does not require roots of unity. We hope that this paper will both encourage and help practitioners implement the Fischlin transform where relevant.



## 2024/528

* Title: The solving degrees for computing Gröbner bases of affine semi-regular polynomial sequences
* Authors: Momonari Kudo, Kazuhiro Yokoyama
* [Permalink](https://eprint.iacr.org/2024/528)
* [Download](https://eprint.iacr.org/2024/528.pdf)

### Abstract

Determining the complexity of computing Gröbner bases is an important problem both in theory and in practice, and for that the solving degree plays a key role. In this paper, we study the solving degrees of affine semi-regular sequences and their homogenized sequences. Some of our results are considered to give mathematically rigorous proofs of the correctness of methods for computing Gröbner bases of the ideal generated by an affine semi-regular sequence. This paper is a sequel of the authors’ previous work and gives additional results on the solving degrees and important behaviors of Gröbner basis computation.



## 2024/529

* Title: Fully Homomorphic Training and Inference on Binary Decision Tree and Random Forest
* Authors: Hojune Shin, Jina Choi, Dain Lee, Kyoungok Kim, Younho Lee
* [Permalink](https://eprint.iacr.org/2024/529)
* [Download](https://eprint.iacr.org/2024/529.pdf)

### Abstract

This paper introduces a new method for training decision trees and random forests using CKKS homomorphic encryption (HE) in cloud environments,  enhancing data privacy from multiple sources. The innovative Homomorphic Binary Decision Tree (HBDT) method utilizes a modified Gini Impurity index (MGI) for node splitting in encrypted data scenarios. Notably, the proposed training approach operates in a single cloud security domain without the need for decryption, addressing key challenges in privacy-preserving machine learning.
We also propose an efficient method for inference utilizing only addition for path evaluation even when both models and inputs are encrypted, achieving O(1) multiplicative depth.
Experiments demonstrate that this method surpasses the previous study by Akavia et al.'s by at least 3.7 times in the speed of inference. The study also expands to privacy-preserving random forests, with GPU acceleration ensuring feasibly efficient performance in both training and inference.



## 2024/530

* Title: An efficient key generation algorithm for GR-NTRU over dihedral group
* Authors: Vikas Kumar, Ali Raya, Aditi Kar Gangopadhyay
* [Permalink](https://eprint.iacr.org/2024/530)
* [Download](https://eprint.iacr.org/2024/530.pdf)

### Abstract

In this article, we focus on deriving an easily implementable and efficient
method of constructing units of the group ring of dihedral group. We provide
a necessary and sufficient condition that relates the units in the group ring
of dihedral group with the units in the group ring of cyclic group. Using this
relation and the methods available for inversion in the group ring of the cyclic
group, we introduce an algorithm to construct units efficiently and check its
performance experimentally.



## 2024/531

* Title: Avoiding Trusted Setup in Isogeny-based Commitments
* Authors: Gustave Tchoffo Saah, Tako Boris Fouotsa, Emmanuel Fouotsa, Célestin Nkuimi-Jugnia
* [Permalink](https://eprint.iacr.org/2024/531)
* [Download](https://eprint.iacr.org/2024/531.pdf)

### Abstract

In 2021, Sterner proposed a commitment scheme based on supersingular isogenies. For this scheme to be binding, one relies on a  trusted party to generate a starting supersingular elliptic curve of unknown endomorphism ring.  In fact, the knowledge of the endomorphism ring allows one to compute an endomorphism of degree a power of a given small prime. Such an endomorphism can then be split into two to obtain two different messages with the same commitment. This is the reason why one needs a curve of unknown endomorphism ring, and the only known way to generate such supersingular curves is to rely on a trusted party or on some expensive multiparty computation.  We observe that if the degree of the endomorphism in play is well chosen, then the knowledge of the endomorphism ring is not sufficient to efficiently compute such an endomorphism and in some particular cases, one can even prove that endomorphism of a certain degree do not exist. Leveraging these observations, we adapt Sterner's commitment scheme in such a way that the endomorphism ring of the starting curve can be known and public. This allows us to obtain isogeny-based commitment schemes which can be instantiated without  trusted setup requirements.



## 2024/532

* Title: Analysing Cryptography in the Wild - A Retrospective
* Authors: Martin R. Albrecht, Kenneth G. Paterson
* [Permalink](https://eprint.iacr.org/2024/532)
* [Download](https://eprint.iacr.org/2024/532.pdf)

### Abstract

We reflect on our experiences analysing cryptography deployed “in the wild” and give recommendations to fellow researchers about this process.



## 2024/533

* Title: HyCaMi: High-Level Synthesis for Cache Side-Channel Mitigation
* Authors: Heiko Mantel, Joachim Schmidt, Thomas Schneider, Maximilian Stillger, Tim Weißmantel, Hossein Yalame
* [Permalink](https://eprint.iacr.org/2024/533)
* [Download](https://eprint.iacr.org/2024/533.pdf)

### Abstract

Cache side-channels are a major threat to cryptographic implementations, particularly block ciphers. Traditional manual hardening methods transform block ciphers into Boolean circuits, a practice refined since the late 90s. The only existing automatic approach based on Boolean circuits achieves security but suffers from performance issues. This paper examines the use of Lookup Tables (LUTs) for automatic hardening of block ciphers against cache side-channel attacks. We present a novel method combining LUT-based synthesis with quantitative static analysis in our HyCaMi framework. Applied to seven block cipher implementations, HyCaMi shows significant improvement in efficiency, being 9.5$\times$ more efficient than previous methods, while effectively protecting against cache side-channel attacks. Additionally, for the first time, we explore balancing speed with security by adjusting LUT sizes, providing faster performance with slightly reduced leakage guarantees, suitable for scenarios where absolute security and speed must be balanced.



## 2024/534

* Title: CryptoVampire: Automated Reasoning for the Complete Symbolic Attacker Cryptographic Model
* Authors: Simon Jeanteur, Laura Kovács, Matteo Maffei, Michael Rawson
* [Permalink](https://eprint.iacr.org/2024/534)
* [Download](https://eprint.iacr.org/2024/534.pdf)

### Abstract

Cryptographic protocols are hard to design and prove correct, as witnessed by the ever-growing list of attacks even on protocol standards. Symbolic models of cryptography enable automated formal security proofs of such protocols against an idealized cryptographic model, which abstracts away from the algebraic properties of cryptographic schemes and thus misses attacks. Computational models of cryptography yield rigorous guarantees but support at present only interactive proofs and/or restricted classes of protocols (e.g., stateless ones). A promising approach is given by the computationally complete symbolic attacker (CCSA) model, formalized in the BC Logic, which aims at bridging and getting the best of the two worlds, obtaining cryptographic guarantees by symbolic protocol analysis. The BC Logic is supported by a recently developed interactive theorem prover, namely Squirrel, which enables machine-checked interactive security proofs, as opposed to automated ones, thus requiring expert knowledge both in the cryptographic space as well as on the reasoning side.

In this paper, we introduce the CryptoVampire cryptographic protocol verifier, which for the first time fully automates proofs of trace properties in the BC Logic. The key technical contribution is a first-order formalization of protocol properties with tailored handling of subterm relations. As such, we overcome the burden of interactive proving in higher-order logic and automatically establish soundness of cryptographic protocols using only first-order reasoning. Our first-order encoding of cryptographic protocols is challenging for various reasons. On the theoretical side, we restrict full first-order logic with cryptographic axioms to ensure that, by losing the expressivity of the higher-order BC Logic, we do not lose soundness of cryptographic protocols in our first-order encoding. On the practical side, CryptoVampire integrates dedicated proof techniques using first-order saturation algorithms and heuristics, which all together enable leveraging the state-of-the-art Vampire first-order automated theorem prover as the underlying proving engine of CryptoVampire. Our experimental results showcase the effectiveness of CryptoVampire as a standalone verifier as well as in terms of automation support for Squirrel.



## 2024/535

* Title: NodeGuard: A Highly Efficient Two-Party Computation Framework for Training Large-Scale Gradient Boosting Decision Tree
* Authors: Tianxiang Dai, Yufan Jiang, Yong Li, Fei Mei
* [Permalink](https://eprint.iacr.org/2024/535)
* [Download](https://eprint.iacr.org/2024/535.pdf)

### Abstract

The Gradient Boosting Decision Tree (GBDT) is a well-known machine learning algorithm, which achieves high performance and outstanding interpretability in real-world scenes such as fraud detection, online marketing and risk management. Meanwhile, two data owners can jointly train a GBDT model without disclosing their private dataset by executing secure Multi-Party Computation (MPC) protocols. In this work, we propose NodeGuard, a highly efficient two party computation (2PC) framework for large-scale GBDT training and inference. NodeGuard guarantees that no sensitive intermediate results are leaked in the training and inference. The efficiency advantage of NodeGuard is achieved by applying a novel keyed bucket aggregation protocol, which optimizes the communication and computation complexity globally in the training. Additionally, we introduce a probabilistic approximate division protocol with an optimization for re-scaling, when the divisor is publicly known. Finally, we compare NodeGuard to state-of-the-art frameworks, and we show that NodeGuard is extremely efficient. It can improve the privacy preserving GBDT training performance by a factor of 5.0 to 131 in LAN and 2.7 to 457 in WAN.



## 2024/536

* Title: Highly-Effective Backdoors for Hash Functions and Beyond
* Authors: Mihir Bellare, Doreen Riepel, Laura Shea
* [Permalink](https://eprint.iacr.org/2024/536)
* [Download](https://eprint.iacr.org/2024/536.pdf)

### Abstract

We study the possibility of schemes whose public parameters have been generated along with a backdoor. We consider the goal of the big-brother adversary to be two-fold: It desires utility (it can break the scheme) but also exclusivity (nobody else can). Starting with hash functions, we give new, strong definitions for these two goals, calling the combination high effectiveness. We then present a construction of a backdoored hash function that is highly effective, meaning provably meets our new definition. As an application, we investigate forgery of X.509 certificates that use this hash function. We then consider signatures, again giving a definition of high effectiveness, and showing that it can be achieved. But we also give some positive results, namely that for the Okamoto and Katz-Wang signature schemes, certain natural backdoor strategies are provably futile. Our backdoored constructions serve to warn that backdoors can be more powerful and damaging than previously conceived, and to help defenders and developers identify potential backdoors by illustrating how they might be built. Our positive results illustrate that some schemes do offer more backdoor resistance than others, which may make them preferable.

Date Sujet#  Auteur
8 Apr 24 o [digest] 2024 Week 141IACR ePrint Archive

Haut de la page

Les messages affichés proviennent d'usenet.

NewsPortal