[digest] 2024 Week 30

## In this issue

1. [2024/875] Succinctly-Committing Authenticated Encryption
2. [2024/1179] Inner Product Ring LWE Problem, Reduction, New ...
3. [2024/1180] Fast computation of 2-isogenies in dimension 4 and ...
4. [2024/1181] AQQUA: Augmenting Quisquis with Auditability
5. [2024/1182] Hyperion: Transparent End-to-End Verifiable Voting ...
6. [2024/1183] Updatable Private Set Intersection from Structured ...
7. [2024/1184] Sanitizable and Accountable Endorsement for Dynamic ...
8. [2024/1185] Erebor and Durian: Full Anonymous Ring Signatures ...
9. [2024/1186] MATTER: A Wide-Block Tweakable Block Cipher
10. [2024/1187] STORM — Small Table Oriented Redundancy-based SCA ...
11. [2024/1188] Lightweight Dynamic Linear Components for Symmetric ...
12. [2024/1189] The Espresso Sequencing Network: HotShot Consensus, ...
13. [2024/1190] Efficient Two-Party Secure Aggregation via ...
14. [2024/1191] A note on ``a novel authentication protocol for ...
15. [2024/1192] Towards ML-KEM & ML-DSA on OpenTitan
16. [2024/1193] The syzygy distinguisher
17. [2024/1194] Hardware Implementation and Security Analysis of ...
18. [2024/1195] Efficient Implementation of Super-optimal Pairings ...
19. [2024/1196] Client-Aided Privacy-Preserving Machine Learning
20. [2024/1197] Optimizing Rectangle and Boomerang Attacks: A ...
21. [2024/1198] ECO-CRYSTALS: Efficient Cryptography CRYSTALS on ...
22. [2024/1199] On degrees of carry and Scholz's conjecture
23. [2024/1200] Depth-Aware Arithmetization of Common Primitives in ...
24. [2024/1201] Designing a General-Purpose 8-bit (T)FHE Processor ...
25. [2024/1202] Prover - Toward More Efficient Formal Verification ...
26. [2024/1203] Preservation of Speculative Constant-time by ...
27. [2024/1204] A fast heuristic for mapping Boolean circuits to ...
28. [2024/1205] Analysis of One Scheme for User Authentication and ...
29. [2024/1206] Applying Post-Quantum Cryptography Algorithms to a ...
30. [2024/1207] What Have SNARGs Ever Done for FHE?
31. [2024/1208] Hᴇᴋᴀᴛᴏɴ: Horizontally-Scalable zkSNARKs via Proof ...
32. [2024/1209] Collaborative CP-NIZKs: Modular, Composable Proofs ...

## 2024/875

* Title: Succinctly-Committing Authenticated Encryption
* Authors: Mihir Bellare, Viet Tung Hoang
* [Permalink](https://eprint.iacr.org/2024/875)
* [Download](https://eprint.iacr.org/2024/875.pdf)

### Abstract

Recent attacks and applications have led to the need for symmetric encryption schemes that, in addition to providing the usual authenticity and privacy, are also committing. In response, many committing authenticated encryption schemes have been proposed. However, all known schemes, in order to provide s bits of committing security, suffer an expansion---this is the length of the ciphertext minus the length of the plaintext---of 2s bits. This incurs a cost in bandwidth or storage. (We typically want s=128, leading to 256-bit expansion.) However, it has been considered unavoidable due to birthday attacks. We show how to bypass this limitation. We give authenticated encryption (AE) schemes that provide s bits of committing security, yet suffer expansion only around s as long as messages are long enough, namely more than s bits. We call such schemes succinct. We do this via a generic, ciphertext-shortening transform called SC: given an AE scheme with 2s-bit expansion, SC returns an AE scheme with s-bit expansion while preserving committing security. SC is very efficient; an AES-based instantiation has overhead just two AES calls. As a tool, SC uses a collision-resistant invertible PRF called HtM, that we design, and whose analysis is technically difficult. To add the committing security that SC assumes to a base scheme, we also give a transform CTY that improves Chan and Rogaway's CTX. Our results hold in a general framework for authenticated encryption, called AE3, that includes both AE1 (also called AEAD) and AE2 (also called nonce-hiding AE) as special cases, so that we in particular obtain succinctly-committing AE schemes for both these settings.



## 2024/1179

* Title: Inner Product Ring LWE Problem, Reduction, New Trapdoor Algorithm for Inner Product Ring LWE Problem and Ring SIS Problem
* Authors: Zhuang Shan, Leyou Zhang, Qing Wu, Qiqi Lai
* [Permalink](https://eprint.iacr.org/2024/1179)
* [Download](https://eprint.iacr.org/2024/1179.pdf)

### Abstract

Lattice cryptography is currently a major research focus in public-key encryption, renowned for its ability to resist quantum attacks. The introduction of ideal lattices (ring lattices) has elevated the theoretical framework of lattice cryptography. Ideal lattice cryptography, compared to classical lattice cryptography, achieves more acceptable operational efficiency through fast Fourier transforms. However, to date, issues of impracticality or insecurity persist in ideal lattice problems. In order to provide a reasonable and secure trapdoor algorithm, this paper introduces the concept of "Inner Product Ring LWE" and establishes its quantum resistance and indistinguishability using knowledge of time complexity, fixed-point theory, and statistical distances. Inner product Ring LWE is easier to construct trapdoor algorithms compared to Ring LWE. Additionally, leveraging the properties of NTRU, we propose a more secure Ring SIS trapdoor algorithm.



## 2024/1180

* Title: Fast computation of 2-isogenies in dimension 4 and cryptographic applications
* Authors: Pierrick Dartois
* [Permalink](https://eprint.iacr.org/2024/1180)
* [Download](https://eprint.iacr.org/2024/1180.pdf)

### Abstract

Dimension 4 isogenies have first been introduced in cryptography for the cryptanalysis of Supersingular Isogeny Diffie-Hellman (SIDH) and have been used constructively in several schemes, including SQIsignHD, a derivative of SQIsign isogeny based signature scheme. Unlike in dimensions 2 and 3, we can no longer rely on the Jacobian model and its derivatives to compute isogenies. In dimension 4 (and higher), we can only use theta-models. Previous works by Romain Cosset, David Lubicz and Damien Robert have focused on the computation of $\ell$-isogenies in theta-models of level $n$ coprime to $\ell$ (which requires to use $n^g$ coordinates in dimension $g$). For cryptographic applications, we need to compute chains of $2$-isogenies, requiring to use $\geq 3^g$ coordinates in dimension $g$ with state of the art algorithms. 

In this paper, we present algorithms to compute chains of $2$-isogenies between abelian varieties of dimension $g\geq 1$ with theta-coordinates of level $n=2$, generalizing a previous work by Pierrick Dartois, Luciano Maino, Giacomo Pope and Damien Robert in dimension $g=2$. We propose an implementation of these algorithms in dimension $g=4$ to compute endomorphisms of elliptic curve products derived from Kani's lemma with applications to SQIsignHD and SIDH cryptanalysis. We are now able to run a complete key recovery attack on SIDH when the endomorphism ring of the starting curve is unknown within a few seconds on a laptop for all NIST SIKE parameters.



## 2024/1181

* Title: AQQUA: Augmenting Quisquis with Auditability
* Authors: George Papadoulis, Danai Balla, Panagiotis Grontas, Aris Pagourtzis
* [Permalink](https://eprint.iacr.org/2024/1181)
* [Download](https://eprint.iacr.org/2024/1181.pdf)

### Abstract

We propose AQQUA: a digital payment system that combines auditability and privacy. AQQUA extends Quisquis by adding two authorities; one for registration and one for auditing. These authorities do not intervene in the everyday transaction processing; as a consequence, the decentralized nature of the cryptocurrency is not disturbed. Our construction is account-based. An account consists of an updatable public key which functions as a cryptographically unlinkable pseudonym, and of commitments to the balance, the total amount of coins spent, and the total amount of coins received. In order to participate in the system a user creates an initial account with the registration authority. To protect their privacy, whenever the user wants to transact they create unlinkable new accounts by updating their public key and the total number of accounts they own (maintained in committed form). The audit authority may request an audit at will. The user must prove in zero-knowledge that all their accounts are compliant to  specific policies. We formally define a security model capturing the properties that a private and auditable digital payment system should possess and we analyze the security of AQQUA under this model.



## 2024/1182

* Title: Hyperion: Transparent End-to-End Verifiable Voting with Coercion Mitigation
* Authors: Aditya Damodaran, Simon Rastikian, Peter B. Rønne, Peter Y A Ryan
* [Permalink](https://eprint.iacr.org/2024/1182)
* [Download](https://eprint.iacr.org/2024/1182.pdf)

### Abstract

We present Hyperion, an end-to-end verifiable e-voting scheme that allows the voters to identify their votes in cleartext in the final tally. In contrast to schemes like Selene or sElect, identification is not via (private) tracker numbers but via cryptographic commitment terms. After publishing the tally, the Election Authority provides each voter with an individual dual key. Voters identify their votes by raising their dual key to their secret trapdoor key and finding the matching commitment term in the tally.
The dual keys are self-certifying in that, without the voter's trapdoor key, it is intractable to forge a dual key that, when raised to the trapdoor key, will match an alternative commitment. On the other hand, a voter can use their own trapdoor key to forge a dual key to fool any would-be coercer.
Additionally, we propose a variant of Hyperion that counters the tracker collision threat present in Selene. We introduce individual verifiable views: each voter gets their own independently shuffled view of the master Bulletin Board.
We provide new improved definitions of privacy and verifiability for e-voting schemes and prove the scheme secure against these, as well as proving security with respect to earlier definitions in the literature.
Finally, we provide a prototype implementation and provide measurements which demonstrate that our scheme is practical for large scale elections.



## 2024/1183

* Title: Updatable Private Set Intersection from Structured Encryption
* Authors: Archita Agarwal, David Cash, Marilyn George, Seny Kamara, Tarik Moataz, Jaspal Singh
* [Permalink](https://eprint.iacr.org/2024/1183)
* [Download](https://eprint.iacr.org/2024/1183.pdf)

### Abstract

Many efficient custom protocols have been developed for two-party private set intersection (PSI), that allow the parties to learn the intersection of their private sets. However, these approaches do not yield efficient solutions in the dynamic setting when the parties’ sets evolve and the intersection has to be computed repeatedly. In this work we propose a new framework for this problem of updatable PSI — with elements being inserted and deleted — in the semihonest model based on structured encryption. The framework reduces the problem of updatable PSI to a new variant of structured encryption (StE) for an updatable set datatype, which may be of independent interest. Our final construction is a constant round protocol with worst-case communication and computation complexity that grows linearly in the size of the updates and only poly-logarithmically with the size of the accumulated sets.. Our protocol is the first to support arbitrary inserts and deletes for updatable PSI.



## 2024/1184

* Title: Sanitizable and Accountable Endorsement for Dynamic Transactions in Fabric
* Authors: Zhaoman Liu, Jianting Ning, Huiying Hou, Yunlei Zhao
* [Permalink](https://eprint.iacr.org/2024/1184)
* [Download](https://eprint.iacr.org/2024/1184.pdf)

### Abstract

Hyperledger Fabric, an open-source, enterprise-grade consortium platform, employs an endorsement policy wherein a set of endorsers signs transaction proposals from clients to confirm their authenticity. The signatures from endorsers constitute the core component of endorsement. However, when dealing with dynamic transactions with high timeliness and frequent updates (e.g., stock trading, real-time ad delivery, news reporting, etc.), the current endorsement process somewhat slows down the transaction execution. Meanwhile, handling these continuously updated transactions consumes significant resources from endorsers, thereby  constraining overall application efficiency.

To address these issues, this paper devises a novel sanitizable and accountable endorsement scheme by proposing a sanitizable multi-signature (SMS) as the theoretical tool. Specifically, we introduce the novel concept of sanitizable  multi-signature and detail its instantiation. SMS combines the advantages of multi-signature and sanitizable signature, maintaining the compactness of the signature while allowing the sanitizer to adjust the initial endorsement result to fit the updated transaction content without interacting with the endorsers, so that both the authenticity and timeliness of transactions can be ensured. Additionally, SMS incorporates an innovative accountability mechanism to trace instances of improper data updates, thereby enhancing the security and reliability of the endorsement process.

We demonstrate the security of the proposed scheme through rigorous security analysis. Performance evaluations show that SMS can significantly reduce verification overhead and transaction size compared to the default ECDSA scheme in Fabric. Specifically, when verifying multiple endorsers' endorsements, our scheme exhibits a storage space reduction by approximately 30%-40% and a verification time reduction ranging from 9.2% to nearly 26.3%.



## 2024/1185

* Title: Erebor and Durian: Full Anonymous Ring Signatures from Quaternions and Isogenies
* Authors: Giacomo Borin, Yi-Fu Lai, Antonin Leroux
* [Permalink](https://eprint.iacr.org/2024/1185)
* [Download](https://eprint.iacr.org/2024/1185.pdf)

### Abstract

We construct two efficient post-quantum ring signatures with anonymity against full key exposure from isogenies, addressing limitations of existing isogeny-based ring signatures.
First, we present an efficient concrete distinguisher for the SQIsign simulator when the signing key is provided using one transcript. This shows that turning SQIsign into an efficient full anonymous ring signature requires some new ideas.
Second, we propose a variant of SQIsign that is resistant to the distinguisher attack with only a $\times 1.33$ increase in size and we render it to a ring signature, that we refer as $\mathsf{Erebor}$. This variant introduces a new zero-knowledge assumption that ensures full anonymity. The efficiency of $\mathsf{Erebor}$ remains comparable to that of SQIsign, with only a proportional increase due to the ring size. This results in a signature size of $0.68 \mathsf{KB}$ for 4 users and $1.35 \mathsf{KB}$ for 8 users, making it the most compact post-quantum ring signature for up to 31 users.
Third, we revisit the GPS signature scheme (Asiacrypt'17), developing efficient subroutines to make the scheme more efficient and significantly reduce the resulting signature size. By integrating our scheme with the paradigm by  Beullens, Katsumata, and Pintore (Asiacrypt'20), we achieve an efficient logarithmic ring signature, that we call $\mathsf{Durian}$, resulting in a signature size of $9.87 \mathsf{KB}$ for a ring of size 1024.



## 2024/1186

* Title: MATTER: A Wide-Block Tweakable Block Cipher
* Authors: Roberto Avanzi, Orr Dunkelman, Kazuhiko Minematsu
* [Permalink](https://eprint.iacr.org/2024/1186)
* [Download](https://eprint.iacr.org/2024/1186.pdf)

### Abstract

In this note, we introduce the MATTER Tweakable Block Cipher, designed principally for low latency in low-area hardware implementations, but that can also be implemented in an efficient and compact way in software.

MATTER is a 512-bit wide balanced Feistel network with three to six rounds, using the ASCON permutation as the round function.
The Feistel network defines a keyed, non-tweakable core, which is made tweakable by using the encryption of the tweak as its key.
Key and tweak are 320-bit inputs.

MATTER is particularly suitable for use in an OCB-like mode of operation, with an encrypted checksum for authentication.



## 2024/1187

* Title: STORM — Small Table Oriented Redundancy-based SCA Mitigation for AES
* Authors: Yaacov Belenky, Hennadii Chernyshchyk, Oleg Karavaev, Oleh Maksymenko, Valery Teper, Daria Ryzhkova, Itamar Levi, Osnat Keren, Yury Kreimer
* [Permalink](https://eprint.iacr.org/2024/1187)
* [Download](https://eprint.iacr.org/2024/1187.pdf)

### Abstract

Side-channel-analysis (SCA) resistance with cost optimization in AES hardware implementations remains a significant challenge. While traditional masking-based schemes offer provable security, they often incur substantial resource overheads (latency, area, randomness, performance, power consumption). Alternatively, the RAMBAM scheme introduced a redundancy-based approach to control the signal-to-noise ratio, and achieves exponential leakage reduction as redundancy increases. This method results in only a slight increase in area and in power consumption, and a significant decrease in the amount of randomness needed, without any increase in latency. However, it lacks a formal security proof.

In this study, we introduce a scheme, denoted STORM, that synergizes RAMBAM's methodology with the utilization of look-up-tables (LUTs) in memory (ROM/RAM) in a redundant domain. STORM, like RAMBAM, is as fast as a typical unprotected implementation and has the same latency, but has a significantly higher maximal clock frequency than RAMBAM, and consumes less than half the power. RAMBAM and STORM are code-based schemes in the sense that their set of representations is a code in the vector space $GF(2)^{8+d}$.   RAMBAM requires a richer structure of a ring on $GF(2)^{8+d}$ and a ring homomorphism whereas STORM utilizes a simple vector space. In code-based-masking (CBM), as in all masking schemes, non-interference based notions (t-S/NI) are fundamental for establishing provable security. RAMBAM and STORM diverge from this approach. While CBM employs codes in vector spaces over $GF(2^8)$ for AES protection,  RAMBAM and STORM use codes over $GF(2)$ without the need for t-S/NI-gadgets, leaving them both smaller and more efficient.

Independence in security proofs typically means that in each individual computation (in a clock-cycle), at least one share does not participate. This approach does not work for RAMBAM where several field multiplications are executed sequentially in a cycle. However, in STORM no multiplications are performed due to its memory based tables, leaving only (independent) bitwise-XORs. Therefore, the reasoning necessary for proving security is different and STORM, unlike RAMBAM, enjoys provable security. We consider two distinct scenarios, \emph{both with provable security}: (1) STORM1 --- ``leakage-free’’ memory reads, demonstrating (1,1,0)-robustness for LUTs with redundancy 2 in the 1-probe model and for LUTs with redundancy 6 in the 2-probe model, and (2) STORM2 --- leaky memory reads, where additional protection mechanisms and a notion of memory-read robustness are introduced.

STORM can be implemented not only in HW, but in SW as well. However, this paper and the proofs in it relate to STORM's HW implementations.



## 2024/1188

* Title: Lightweight Dynamic Linear Components for Symmetric Cryptography
* Authors: S. M. Dehnavi, M. R. Mirzaee Shamsabad
* [Permalink](https://eprint.iacr.org/2024/1188)
* [Download](https://eprint.iacr.org/2024/1188.pdf)

### Abstract

‎In this paper‎, ‎using the concept of equivalence of mappings we characterize all of the one-XOR matrices which are used in hardware applications and propose a family of lightweight linear mappings for software-oriented applications in symmetric cryptography‎. ‎Then‎, ‎we investigate interleaved linear mappings and based upon this study‎, ‎we present generalized dynamic primitive LFSRs along with dynamic linear components for construction of diffusion layers.
‎From the mathematical viewpoint‎, ‎this paper presents involutive sparse binary matrices as well as sparse binary matrices with sparse inverses‎. ‎Another interesting result of our investigation is that‎, ‎by our characterization of one-XOR matrices‎, ‎the search space for finding a $k$ such that $x^n+x^k+1$ is a primitive trinomial could be reduced‎.



## 2024/1189

* Title: The Espresso Sequencing Network: HotShot Consensus, Tiramisu Data-Availability, and Builder-Exchange
* Authors: Jeb Bearer, Benedikt Bünz, Philippe Camacho, Binyi Chen, Ellie Davidson, Ben Fisch, Brendon Fish, Gus Gutoski, Fernando Krell, Chengyu Lin, Dahlia Malkhi, Kartik Nayak, Keyao Shen, Alex Xiong, Nathan Yospe
* [Permalink](https://eprint.iacr.org/2024/1189)
* [Download](https://eprint.iacr.org/2024/1189.pdf)

### Abstract

Building a Consensus platform for shared sequencing can power an ecosystem of layer-2 solutions such as rollups which are crucial for scaling blockchains (e.g.,Ethereum). However, it drastically differs from conventional Consensus for blockchains in two key considerations:
• (No) Execution: A shared sequencing platform is not responsible for pre-validating blocks nor for processing state updates. Therefore, agreement is formed on a sequence of certificates of block data-availability (DA) without persisting them or obtaining blocks in full. At the same time, the platform must stream block data with very high efficiency to layer-2 entities for execution, or (in the case of rollups) for proof generation.
• Builder-Exchange: A shared sequencing platform delegates to external entities to build blocks and separates it from the role of a consensus proposer. This allows an ecosystem of specialized builders to pre-validate transactions for diversified rollups, languages, and MEV exploits. However, separating the task of block-building from proposing brings a new challenge. Builders want assurances that their blocks would commit in exchange for revealing their contents, whereas validators/proposers want assurance that the data in committed blocks will be available and fees paid. Neither one trusts the other, hence the shared sequencing platform should facilitate a “fair-exchange”  between builders and the sequencing network. The Espresso Sequencing Network is purpose-built to address these unique considerations.
Among the main novelties of the design are (i) a three-layered DA system called Tiramisu, coupled with (ii) a costless integration of the DA with the platform’s consensus core, and (iii) a Builder-Exchange mechanism between builders and the consensus core.
Note that this paper relies substantially on and can be seen as an extension of The Espresso Sequencer: HotShot Consensus and Tiramisu Data Availability [84].



## 2024/1190

* Title: Efficient Two-Party Secure Aggregation via Incremental Distributed Point Function
* Authors: Nan Cheng, Aikaterini Mitrokotsa, Feng Zhang, Frank Hartmann
* [Permalink](https://eprint.iacr.org/2024/1190)
* [Download](https://eprint.iacr.org/2024/1190.pdf)

### Abstract

Computing the maximum from a list of secret inputs is a widely-used functionality that is employed ei- ther indirectly as a building block in secure computation frameworks, such as ABY (NDSS’15) or directly used in multiple applications that solve optimisation problems, such as secure machine learning or secure aggregation statistics. Incremental distributed point function (I-DPF) is a powerful primitive (IEEE S&P’21) that significantly reduces the client- to-server communication and are employed to efficiently and securely compute aggregation statistics.
In this paper, we investigate whether I-DPF can be used to improve the efficiency of secure two-party computation (2PC) with an emphasis on computing the maximum value and the k-th (with k unknown to the computing parties) ranked value from a list of secret inputs. Our answer is affir- mative, and we propose novel secure 2PC protocols that use I-DPF as a building block, resulting in significant efficiency gains compared to the state-of-the-art. More precisely, our contributions are: (i) We present two new secure computa- tion frameworks that efficiently compute secure aggregation statistics bit-wisely or batch-wisely; (ii) we propose novel protocols to compute the maximum value, the k-th ranked value from a list of secret inputs; (iii) we provide variations of the proposed protocols that can perform batch computations and thus provide further efficiency improvements; and (iv) we provide an extensive performance evaluation for all proposed protocols.
Our protocols have a communication complexity that is independent of the number of secret inputs and linear to the length of the secret input domain. Our experimental re- sults show enhanced efficiency over state-of-the-art solutions, particularly notable when handling large-scale inputs. For instance, in scenarios involving an input set of five million elements with an input domain size of 31 bits, our protocol ΠMax achieves an 18% reduction in online execution time and a 67% decrease in communication volume compared to the most efficient existing solution.



## 2024/1191

* Title: A note on ``a novel authentication protocol for IoT-enabled devices''
* Authors: Zhengjun Cao, Lihua Liu
* [Permalink](https://eprint.iacr.org/2024/1191)
* [Download](https://eprint.iacr.org/2024/1191.pdf)

### Abstract

We show that the authentication protocol [IEEE Internet Things J., 2023, 10(1), 867-876] is not correctly specified, because the server cannot complete its computations. To revise, the embedded device needs to compute an extra point multiplication over the underlying elliptic curve. We also find the protocol  cannot provide anonymity, not as claimed. It can only provide pseudonymity.



## 2024/1192

* Title: Towards ML-KEM & ML-DSA on OpenTitan
* Authors: Amin Abdulrahman, Felix Oberhansl, Hoang Nguyen Hien Pham, Jade Philipoom, Peter Schwabe, Tobias Stelzer, Andreas Zankl
* [Permalink](https://eprint.iacr.org/2024/1192)
* [Download](https://eprint.iacr.org/2024/1192.pdf)

### Abstract

This paper presents extensions to the OpenTitan hardware root of trust that aim at enabling high-performance lattice-based cryptography. We start by carefully optimizing ML-KEM and ML-DSA - the two primary algorithms selected by NIST for standardization - in software targeting the OTBN accelerator. Based on profiling results of these implementations, we propose tightly integrated extensions to OTBN, specifically an interface from OTBN to OpenTitan's Keccak accelerator (KMAC core) and extensions to the OTBN ISA to support operations on 256-bit vectors. We implement these extensions in hardware and show that we achieve a speedup by a factor between 6 and 9 for different operations and parameter sets of ML-KEM and ML-DSA compared to our baseline implementation on unmodified OTBN. This speedup is achieved with an increase in cell count of less than 12% in OTBN, which corresponds to an increase of less than 2% for the full Earlgrey OpenTitan core.



## 2024/1193

* Title: The syzygy distinguisher
* Authors: Hugues RANDRIAMBOLOLONA
* [Permalink](https://eprint.iacr.org/2024/1193)
* [Download](https://eprint.iacr.org/2024/1193.pdf)

### Abstract

We present a new distinguisher for alternant and Goppa codes, whose complexity is subexponential in the error-correcting capability, hence better than that of generic decoding algorithms. Moreover it does not suffer from the strong regime limitations of the previous distinguishers or structure recovery algorithms: in particular, it applies to the codes used in the Classic McEliece candidate for postquantum cryptography standardization. The invariants that allow us to distinguish are graded Betti numbers of the homogeneous coordinate ring of a shortening of the dual code.

Since its introduction in 1978, this is the first time an analysis of the McEliece cryptosystem breaks the exponential barrier.



## 2024/1194

* Title: Hardware Implementation and Security Analysis of Local-Masked NTT for CRYSTALS-Kyber
* Authors: Rafael Carrera Rodriguez, Emanuele Valea, Florent Bruguier, Pascal Benoit
* [Permalink](https://eprint.iacr.org/2024/1194)
* [Download](https://eprint.iacr.org/2024/1194.pdf)

### Abstract

The rapid evolution of post-quantum cryptography, spurred by standardization efforts such as those led by NIST, has highlighted the prominence of lattice-based cryptography, notably exemplified by CRYSTALS-Kyber. However, concerns persist regarding the security of cryptographic implementations, particularly in the face of Side-Channel Attacks (SCA). The usage of operations like the Number Theoretic
Transform (NTT) in CRYSTALS-Kyber introduces vulnerabilities to SCA, especially single-trace ones, such as soft-analytical side-channel attacks. To address this threat, Ravi et al. proposed local masking as a countermeasure by randomizing the NTT’s twiddle factors, but its implementation and security implications require further investigation. This paper presents a hardware implementation of the NTT with local masking, evaluating its performance, area utilization, and security impacts. Additionally, it analyzes the vulnerabilities inherent in local masking and assesses its practical security effectiveness through non-specific t-tests, showing that there are configurations of local masking that are more prone to leakage than others.



## 2024/1195

* Title: Efficient Implementation of Super-optimal Pairings on Curves with Small Prime Fields at the 192-bit Security Level
* Authors: Jianming Lin, Chang-An Zhao, Yuhao Zheng
* [Permalink](https://eprint.iacr.org/2024/1195)
* [Download](https://eprint.iacr.org/2024/1195.pdf)

### Abstract

For many pairing-based cryptographic protocols such as  Direct Anonymous Attestation (DAA) schemes, the arithmetic  on the first pairing subgroup $\mathbb{G}_1$ is more fundamental. Such operations heavily depend on the sizes of prime fields. At the 192-bit security level, Gasnier and Guillevic presented a curve named GG22D7-457 with CM-discriminant $D = 7$ and embedding degree $k = 22$. Compared to other well-known pairing-friendly curves at the same security level, the curve GG22D7-457 has smaller  prime field size and $\rho$-value, which benefits from  the fast operations on  $\mathbb{G}_1$. However, the pairing computation on GG22D7-457 is not efficient.
        In this paper, we investigate to derive a higher performance for the pairing computation on GG22D7-457. We first propose novel formulas of the super-optimal pairing on this curve by utilizing a $2$-isogeny as GLV-endomorphism. Besides, this tool can be generalized to more generic families of pairing-friendly curves with $n$-isogenies as endomorphisms. In our paper, we provide the explicit formulas for the super-optimal pairings exploiting $2, 3$-isogenies. Finally, we make a concrete computational cost analysis and  implement the pairing computations on curve GG22D7-457  using our approaches. In terms of Miller function evaluation, employing the techniques in this paper obtain a  saving of  $24.44\% $  in  $\mathbb{F}_p$-multiplications  compared to the  optimal ate pairing.  As for the running time, the experimental results illustrate that the Miller loop on GG22D7-457 by utilizing our methods is $26.0\%$ faster than the state-of-the-art. Additionally, the performance of the super-optimal pairing on GG22D7-457 is competitive compared to  the well-known pairing-friendly curves at the 192-bit security level. These results show that GG22D7-457  becomes an attractive candidate for the pairing-based protocols.. Furthermore,  our techniques have the potential to enhance the applications of super-optimal pairings on more pairing-friendly curves.



## 2024/1196

* Title: Client-Aided Privacy-Preserving Machine Learning
* Authors: Peihan Miao, Xinyi Shi, Chao Wu, Ruofan Xu
* [Permalink](https://eprint.iacr.org/2024/1196)
* [Download](https://eprint.iacr.org/2024/1196.pdf)

### Abstract

Privacy-preserving machine learning (PPML) enables multiple distrusting parties to jointly train ML models on their private data without revealing any information beyond the final trained models. In this work, we study the client-aided two-server setting where two non-colluding servers jointly train an ML model on the data held by a large number of clients. By involving the clients in the training process, we develop efficient protocols for training algorithms including linear regression, logistic regression, and neural networks. In particular, we introduce novel approaches to securely computing inner product, sign check, activation functions (e.g., ReLU, logistic function), and division on secret shared values, leveraging lightweight computation on the client side. We present constructions that are secure against semi-honest clients and further enhance them to achieve security against malicious clients. We believe these new client-aided techniques may be of independent interest.

We implement our protocols and compare them with the two-server PPML protocols presented in SecureML (Mohassel and Zhang, S&P'17) across various settings and ABY2.0 (Patra et al., Usenix Security'21) theoretically. We demonstrate that with the assistance of untrusted clients in the training process, we can significantly improve both the communication and computational efficiency by orders of magnitude. Our protocols compare favorably in all the training algorithms on both LAN and WAN networks.



## 2024/1197

* Title: Optimizing Rectangle and Boomerang Attacks: A Unified and Generic Framework for Key Recovery
* Authors: Qianqian Yang, Ling Song, Nana Zhang, Danping Shi, Libo Wang, Jiahao Zhao, Lei Hu, Jian Weng
* [Permalink](https://eprint.iacr.org/2024/1197)
* [Download](https://eprint.iacr.org/2024/1197.pdf)

### Abstract

The rectangle attack has shown to be a very powerful form of cryptanalysis against block ciphers. Given a rectangle distinguisher, one expects to mount key recovery attacks as efficiently as possible. In the literature, there have been four algorithms for rectangle key recovery attacks. However, their performance varies from case to case. Besides, numerous are the applications where the attacks lack optimality. In this paper, we delve into the rectangle key recovery and propose a unified and generic key recovery algorithm, which supports any possible attacking parameters. Not only does it encompass the four existing rectangle key recovery algorithms, but it also reveals five new types of attacks that were previously overlooked. Further, we put forward a counterpart for boomerang key recovery attacks, which supports any possible attacking parameters as well. Along with these new key recovery algorithms, we propose a framework to automatically determine the best parameters for the attack. To demonstrate the efficiency of the new key recovery algorithms, we apply them to \serpent, \aes-192, \craft, \skinny, and \deoxysbc-256 based on existing distinguishers, yielding a series of improved attacks.



## 2024/1198

* Title: ECO-CRYSTALS: Efficient Cryptography CRYSTALS on Standard RISC-V ISA
* Authors: Xinyi Ji, Jiankuo Dong, Junhao Huang, Zhijian Yuan, Wangchen Dai, Fu Xiao, Jingqiang Lin
* [Permalink](https://eprint.iacr.org/2024/1198)
* [Download](https://eprint.iacr.org/2024/1198.pdf)

### Abstract

The field of post-quantum cryptography (PQC) is continuously evolving. Many researchers are exploring efficient PQC implementation on various platforms, including x86, ARM, FPGA, GPU, etc. In this paper, we present an Efficient CryptOgraphy CRYSTALS (ECO-CRYSTALS) implementation on standard 64-bit RISC-V Instruction Set Architecture (ISA). The target schemes are two winners of the National Institute of Standards and Technology (NIST) PQC competition: CRYSTALS-Kyber and CRYSTALS-Dilithium, where the two most time-consuming operations are Keccak and polynomial multiplication. Notably, this paper is the first to deploy Kyber and Dilithium on the 64-bit RISC-V ISA. Firstly, we propose a better scheduling strategy for Keccak, which is specifically tailored for the 64-bit dual-issue RISC-V architecture. Our 24-round Keccak permutation (Keccak-$p$[1600,24]) achieves a 59.18% speed-up compared to the reference implementation. Secondly, we apply two modular arithmetic (Montgomery arithmetic and Plantard arithmetic) in the polynomial multiplication of Kyber and Dilithium to get a better lazy reduction. Then, we propose a flexible dual-instruction-issue scheme of Number Theoretic Transform (NTT). As for the matrix-vector multiplication, we introduce a row-to-column processing methodology to minimize the expensive memory access operations. Compared to the reference implementation, we obtain a speedup of 53.85%$\thicksim$85.57% for NTT, matrix-vector multiplication, and INTT in our ECO-CRYSTALS. Finally, our ECO-CRYSTALS implementation for key generation, encapsulation, and decapsulation in Kyber achieves 399k, 448k, and 479k cycles respectively, achieving speedups of 60.82%, 63..93%, and 65.56% compared to the NIST reference implementation. Similarly, our ECO-CRYSTALS implementation for key generation, sign, and verify in Dilithium reaches 1,364k, 3,191k, and 1,369k cycles, showcasing speedups of 54.84%, 64.98%, and 57.20%, respectively.



## 2024/1199

* Title: On degrees of carry and Scholz's conjecture
* Authors: Theophilus Agama
* [Permalink](https://eprint.iacr.org/2024/1199)
* [Download](https://eprint.iacr.org/2024/1199.pdf)

### Abstract

Exploiting the notion of carries, we obtain improved upper bounds for the length of the shortest addition chains $\iota(2^n-1)$ producing $2^n-1$. Most notably, we show that if $2^n-1$ has carries of degree at most $$\kappa(2^n-1)=\frac{1}{2}(\iota(n)-\lfloor \frac{\log n}{\log 2}\rfloor+\sum \limits_{j=1}^{\lfloor \frac{\log n}{\log 2}\rfloor}\{\frac{n}{2^j}\})$$ then the inequality $$\iota(2^n-1)\leq n+1+\sum \limits_{j=1}^{\lfloor \frac{\log n}{\log 2}\rfloor}\bigg(\{\frac{n}{2^j}\}-\xi(n,j)\bigg)+\iota(n)$$ holds for all $n\in \mathbb{N}$ with $n\geq 4$, where $\iota(\cdot)$ denotes the length of the shortest addition chain producing $\cdot$, $\{\cdot\}$ denotes the fractional part of $\cdot$ and where $\xi(n,1):=\{\frac{n}{2}\}$ with $\xi(n,2)=\{\frac{1}{2}\lfloor \frac{n}{2}\rfloor\}$ and so on.



## 2024/1200

* Title: Depth-Aware Arithmetization of Common Primitives in Prime Fields
* Authors: Jelle Vos, Mauro Conti, Zekeriya Erkin
* [Permalink](https://eprint.iacr.org/2024/1200)
* [Download](https://eprint.iacr.org/2024/1200.pdf)

### Abstract

A common misconception is that the computational abilities of circuits composed of additions and multiplications are restricted to simple formulas only. Such arithmetic circuits over finite fields are actually capable of computing any function, including equality checks, comparisons, and other highly non-linear operations. While all those functions are computable, the challenge lies in computing them efficiently. We refer to this search problem as arithmetization. Arithmetization is a key problem in secure computation, as techniques like homomorphic encryption and secret sharing compute arithmetic circuits rather than the high-level programs that programmers are used to. The objective in arithmetization has typically been to minimize the number of multiplications (multiplicative size), as multiplications in most secure computation techniques are significantly more expensive to compute than additions. However, the multiplicative depth of a circuit arguably plays an even more important role in deciding the computational cost: For homomorphic encryption, it strongly affects the choice of cryptographic parameters and the number of bootstrapping operations required, which are orders of magnitude more expensive to compute than multiplications. In fact, if we can limit the multiplicative depth of a circuit such that we do not need to perform any bootstrapping, we can omit the large bootstrapping keys required to perform them all together. We argue that arithmetization should be treated as a multi-objective minimization problem, in which a trade-off can be made between a circuit's multiplicative size and depth. We present efficient depth-aware arithmetization methods for many primitive operations such as exponentiation, univariate functions, equality checks, comparisons, and ANDs and ORs, which take into account that squaring can be cheaper than arbitrary multiplications, and we study how to compose them.



## 2024/1201

* Title: Designing a General-Purpose 8-bit (T)FHE Processor Abstraction
* Authors: Daphné Trama, Pierre-Emmanuel Clet, Aymen Boudguiga, Renaud Sirdey
* [Permalink](https://eprint.iacr.org/2024/1201)
* [Download](https://eprint.iacr.org/2024/1201.pdf)

### Abstract

Making the most of TFHE programmable bootstrapping to evaluate functions or operators otherwise difficult to perform with only the native addition and multiplication of the scheme is a very active line of research. In this paper, we systematize this approach and apply it to build an 8-bit FHE processor abstraction, i.e., a software entity that works over FHE-encrypted 8-bits data and presents itself to the programmer by means of a conventional-looking assembly instruction set. In doing so, we provide several homomorphic LUT dereferencing operators based on variants on the tree-based method and show that they are the most efficient option for manipulating encryptions of 8-bit data (optimally represented as two base 16 digits). We then systematically apply this approach over a set of around 50 instructions, including, notably, conditional assignments, divisions, or fixed-point arithmetic operations. We then conclude the paper by testing the approach on several simple algorithms, including the execution of a neuron with a sigmoid activation function over 16-bit precision. Finally, this work reveals that a very limited set of functional bootstrapping patterns is versatile and efficient enough to achieve general-purpose FHE computations beyond the boolean circuit approach. As such, these patterns may be an appropriate target for further works on advanced software optimizations or hardware implementations.



## 2024/1202

* Title: Prover - Toward More Efficient Formal Verification of Masking in Probing Model
* Authors: Feng Zhou, Hua Chen, Limin Fan
* [Permalink](https://eprint.iacr.org/2024/1202)
* [Download](https://eprint.iacr.org/2024/1202.pdf)

### Abstract

In recent years, formal verification has emerged as a crucial method for assessing security against Side-Channel attacks of masked implementations, owing to its remarkable versatility and high degree of automation. However, formal verification still faces technical bottlenecks in balancing accuracy and efficiency, thereby limiting its scalability. Former efficient tools like \textsf{maskVerif} and CocoAlma are often inaccurate when verifying schemes utilizing properties of Boolean functions. Later, SILVER addressed the accuracy issue, albeit at the cost of significantly reduced speed and scalability compared to \textsf{maskVerif}. Consequently, there is a pressing need to develop formal verification tools that are both efficient and accurate for designing secure schemes and evaluating implementations.
    This paper's primary contribution lies in proposing several approaches to develop a more efficient and scalable formal verification tool called \textsf{Prover}, which is built upon SILVER.
    Firstly, inspired by the auxiliary data structures proposed by Eldib et al. and optimistic sampling rule of maskVerif, we introduce two reduction rules aimed at diminishing the size of observable sets and secret sets in statistical independence checks. These rules substantially decrease, or even eliminate, the need for repeated computation of probability distributions using Reduced Ordered Binary Decision Diagrams (ROBDDs), a time-intensive procedure in verification.
    Subsequently, we integrate one of these reduction rules into the uniformity check to mitigate its complexity.
    Secondly, we identify that variable ordering significantly impacts efficiency and optimize it for constructing ROBDDs, resulting in much smaller representations of investigated functions. Lastly, we present the algorithm of \textsf{Prover}, which efficiently verifies the security and uniformity of masked implementations in probing model with or without the presence of glitches.
    Experimental results demonstrate that our proposed tool
    \textsf{Prover} offers a superior balance between efficiency and accuracy compared to other state-of-the-art tools (CocoAlma, maskVerif, and SILVER). It successfully verifies a design that SILVER could not complete within the allocated time, whereas CocoAlma and maskVerif encounter issues with false positives.



## 2024/1203

* Title: Preservation of Speculative Constant-time by Compilation
* Authors: Santiago Arranz Olmos, Gilles Barthe, Lionel Blatter, Benjamin Grégoire, Vincent Laporte
* [Permalink](https://eprint.iacr.org/2024/1203)
* [Download](https://eprint.iacr.org/2024/1203.pdf)

### Abstract

Compilers often weaken or even discard software-based countermeasures commonly used to protect programs against side-channel attacks; worse, they may also introduce vulnerabilities that attackers can exploit. The solution to this problem is to develop compilers that preserve these countermeasures. Prior work establishes that (a mildly modified version of) the CompCert and Jasmin formally verified compilers preserve constant-time, an information flow policy that ensures that programs are protected against cache side-channel attacks. However, nothing is known about preservation of speculative constant-time, a strengthening of the constant-time policy that ensures that programs are protected against Spectre v1 attacks. We first show that preservation of speculative constant-time fails in practice by providing examples of secure programs whose compilation is not speculative constant-time using GCC (GCC -O0 and GCC -O1) and Jasmin. Then, we define a proof-of-concept compiler that distills some of the critical passes of the Jasmin compiler and use the Coq proof assistant to prove that it preserves speculative constant-time.  Finally, we patch the Jasmin speculative constant-time type checker and demonstrate that all cryptographic implementations written in Jasmin can be fixed with minimal impact.



## 2024/1204

* Title: A fast heuristic for mapping Boolean circuits to functional bootstrapping
* Authors: Sergiu Carpov
* [Permalink](https://eprint.iacr.org/2024/1204)
* [Download](https://eprint.iacr.org/2024/1204.pdf)

### Abstract

Functional bootstrapping in FHE schemes such as FHEW and TFHE allows the evaluation of a function on an encrypted message, in addition to noise reduction. Implementing programs that directly use functional bootstrapping is challenging and error-prone. In this paper, we propose a heuristic that automatically maps Boolean circuits to functional bootstrapping instructions. Unlike other approaches, our method does not limit the encrypted data plaintext space to a power-of-two size, allowing the instantiation of functional bootstrapping with smaller parameters. Furthermore, the negacyclic property of functional bootstrapping is exploited to extend the plaintext space. Despite the inherently greedy nature of the heuristic, experimental results show that the mapped circuits exhibit a significant reduction in evaluation time. Furthermore, our heuristic was able to achieve a $45\%$ improvement in evaluation time when applied to manually implemented Trivium and Kreyvium circuits.



## 2024/1205

* Title: Analysis of One Scheme for User Authentication and Session Key Agreement in Wireless Sensor Network Using Smart Card
* Authors: Zhengjun Cao, Lihua Liu
* [Permalink](https://eprint.iacr.org/2024/1205)
* [Download](https://eprint.iacr.org/2024/1205.pdf)

### Abstract

We show that the Chunka-Banerjee-Goswami authentication and
 key agreement scheme [Wirel. Pers. Commun., 117, 1361-1385, 2021] fails to keep user anonymity, not as claimed. It only keeps pseudonymity.  Anonymous actions are designed to be unlinkable to any entity, but pseudonymous actions can be traced back to a certain entity. We also find the scheme is insecure against offline dictionary attack.



## 2024/1206

* Title: Applying Post-Quantum Cryptography Algorithms to a DLT-Based CBDC Infrastructure: Comparative and Feasibility Analysis
* Authors: Daniel de Haro Moraes, Joao Paulo Aragao Pereira, Bruno Estolano Grossi, Gustavo Mirapalheta, George Marcel Monteiro Arcuri Smetana, Wesley Rodrigues, Courtnay Nery Guimarães Jr., Bruno Domingues, Fábio Saito, Marcos Simplício
* [Permalink](https://eprint.iacr.org/2024/1206)
* [Download](https://eprint.iacr.org/2024/1206.pdf)

### Abstract

This article presents an innovative project for a Central Bank Digital Currency (CBDC) infrastructure. Focusing on security and reliability, the proposed architecture: (1) employs post-quantum cryptography (PQC) algorithms for long-term security, even against attackers with access to cryptographically-relevant quantum computers; (2) can be integrated with a Trusted Execution Environment (TEE) to safeguard the confidentiality of transaction contents as they are processed by third-parties; and (3) uses Distributed Ledger Technology (DLT) to promote a high level of transparency and tamper resistance for all transactions registered in the system. Besides providing a theoretical discussion on the benefits of this architecture, we experimentally evaluate its components. Namely, as PQC algorithms, we consider three signature schemes being standardized by the National Institute of Standards and Technology (NIST), CRYSTALS-Dilithium, Falcon, and SPHINCS+. Those algorithms are integrated into the Hyperledger Besu (DLT) and executed both inside and outside an Intel SGX TEE environment. According to our results, CRYSTALS-Dilithium-2 combined with classical secp256k1 signatures leads to the shortest execution times when signing blocks in the DLT, reaching 1.68ms without the TEE, and 2.09ms with TEE. The same combination also displays the best results for signature verifications, achieving 0.5ms without a TEE and 1.98ms with a TEE. We also describe the main aspects of the evaluation methodology and the next steps in validating the proposed infrastructure. The conclusions drawn from our experiments is that the combination of PQC and TEE promises highly secure and effective DLT-based CBDC scenarios, ready to face the challenges of the digital financial future and potential quantum threats.



## 2024/1207

* Title: What Have SNARGs Ever Done for FHE?
* Authors: Michael Walter
* [Permalink](https://eprint.iacr.org/2024/1207)
* [Download](https://eprint.iacr.org/2024/1207.pdf)

### Abstract

In recent years, there have been several constructions combining FHE with SNARGs to add integrity guarantees to FHE schemes. Most of these works focused on improving efficiency, while the precise security model with regards to client side input privacy has remained understudied. Only recently it was shown by Manulis and Nguyen (Eurocrypt'24) that this combination does not yield IND-CCA1 security. So an interesting open question is: does the SNARG actually add any meaningful security to input privacy? We address this question in this note and give a security definition that meaningfully captures the security of the FHE plus SNARG construction.



## 2024/1208

* Title: Hᴇᴋᴀᴛᴏɴ: Horizontally-Scalable zkSNARKs via Proof Aggregation
* Authors: Michael Rosenberg, Tushar Mopuri, Hossein Hafezi, Ian Miers, Pratyush Mishra
* [Permalink](https://eprint.iacr.org/2024/1208)
* [Download](https://eprint.iacr.org/2024/1208.pdf)

### Abstract

Zero-knowledge Succinct Non-interactive ARguments of Knowledge (zkSNARKs) allow a prover to convince a verifier of the correct execution of a large computation in private and easily-verifiable manner.  These properties make zkSNARKs a powerful tool for adding accountability, scalability, and privacy to numerous systems such as blockchains and verifiable key directories. Unfortunately, existing zkSNARKs are unable to scale to large computations due to time and space complexity requirements for the prover algorithm. As a result, they cannot handle real-world instances of the aforementioned applications.
 
In this work, we introduce Hᴇᴋᴀᴛᴏɴ, a zkSNARK that overcomes these barriers and can efficiently handle arbitrarily large computations. We construct Hᴇᴋᴀᴛᴏɴ via a new "distribute-and-aggregate" framework that breaks up large computations into small chunks, proves these chunks in parallel in a distributed system, and then aggregates the resulting chunk proofs into a single succinct proof. Underlying this framework is a new technique for efficiently handling data that is shared between chunks that we believe could be of independent interest.
 
We implement a distributed prover for Hᴇᴋᴀᴛᴏɴ, and evaluate its performance on a compute cluster. Our experiments show that Hᴇᴋᴀᴛᴏɴ achieves strong horizontal scalability (proving time decreases linearly as we increase the number of nodes in the cluster), and is able to prove large computations quickly: it can prove computations of size $2^{35}$ gates in under an hour, which is much faster than prior work.

Finally, we also apply Hᴇᴋᴀᴛᴏɴ to two applications of real-world interest: proofs of batched insertion for a verifiable key directory and proving correctness of RAM computations. In both cases, Hᴇᴋᴀᴛᴏɴ is able to scale to handle realistic workloads with better efficiency than prior work.



## 2024/1209

* Title: Collaborative CP-NIZKs: Modular, Composable Proofs for Distributed Secrets
* Authors: Mohammed Alghazwi, Tariq Bontekoe, Leon Visscher, Fatih Turkmen
* [Permalink](https://eprint.iacr.org/2024/1209)
* [Download](https://eprint.iacr.org/2024/1209.pdf)

### Abstract

Non-interactive zero-knowledge (NIZK) proofs of knowledge have proven to be highly relevant for securely realizing a wide array of applications that rely on both privacy and correctness. They enable a prover to convince any party of the correctness of a public statement for a secret witness. However, most NIZKs do not natively support proving knowledge of a secret witness that is distributed over multiple provers. Previously, collaborative proofs [51] have been proposed to overcome this limitation. We investigate the notion of composability in this setting, following the Commit-and-Prove design of LegoSNARK [17]. Composability allows users to combine different, specialized NIZKs (e.g., one arithmetic circuit, one boolean circuit, and one for range proofs) with the aim of reducing the prove generation time. Moreover, it opens the door to efficient realizations of many applications in the collaborative setting such as mutually exclusive prover groups, combining collaborative and single-party proofs and efficiently implementing publicly auditable MPC (PA-MPC).

We present the first, general definition for collaborative commit-and-prove NIZK (CP-NIZK) proofs of knowledge and construct distributed protocols to enable their realization. We implement our protocols for two commonly used NIZKs, Groth16 and Bulletproofs, and evaluate their practicality in a variety of computational settings. Our findings indicate that composability adds only minor overhead, especially for large circuits. We experimented with our construction in an application setting, and when compared to prior works, our protocols reduce latency by 18–55× while requiring only a fraction (0.2%) of the communication.