[digest] 2024 Week 18

## In this issue

1. [2024/215] Batch PIR and Labeled PSI with Oblivious Ciphertext ...
2. [2024/337] Solving the Tensor Isomorphism Problem for special ...
3. [2024/553] Efficient Linkable Ring Signatures: New Framework ...
4. [2024/653] Ipotane: Achieving the Best of All Worlds in ...
5. [2024/654] Monchi: Multi-scheme Optimization For Collaborative ...
6. [2024/655] Implementation and Performance Analysis of ...
7. [2024/656] Cryptanalytic Audit of the XHash Sponge Function ...
8. [2024/657] Cryptographic Accumulators: New Definitions, ...
9. [2024/658] Information-theoretic security with asymmetries
10. [2024/659] Secure Latent Dirichlet Allocation
11. [2024/660] FE[r]Chain: Enforcing Fairness in Blockchain Data ...
12. [2024/661] On amortization techniques for FRI-based SNARKs
13. [2024/662] Faster Private Decision Tree Evaluation for Batched ...
14. [2024/663] Xproofs: New Aggregatable and Maintainable Matrix ...
15. [2024/664] Pando: Extremely Scalable BFT Based on Committee ...
16. [2024/665] Homomorphic Evaluation of LWR-based PRFs and ...
17. [2024/666] Private Analytics via Streaming, Sketching, and ...
18. [2024/667] Agile, Post-quantum Secure Cryptography in Avionics
19. [2024/668] Blockchain Price vs. Quantity Controls
20. [2024/669] Mempool Privacy via Batched Threshold Encryption: ...
21. [2024/670] Secure Implementation of SRAM PUF for Private Key ...
22. [2024/671] Exploiting Internal Randomness for Privacy in ...
23. [2024/672] Secure Coded Distributed Computing
24. [2024/673] Chocobo: Creating Homomorphic Circuit Operating ...
25. [2024/674] SigmaSuite: How to Minimize Foreign Arithmetic in ...
26. [2024/675] Olympic Privacy-Preserving Blueprints: Faster ...
27. [2024/676] Composing Timed Cryptographic Protocols: ...

## 2024/215

* Title: Batch PIR and Labeled PSI with Oblivious Ciphertext Compression
* Authors: Alexander Bienstock, Sarvar Patel, Joon Young Seo, Kevin Yeo
* [Permalink](https://eprint.iacr.org/2024/215)
* [Download](https://eprint.iacr.org/2024/215.pdf)

### Abstract

In this paper, we study two problems: oblivious compression and decompression of ciphertexts. In oblivious compression, a server holds a set of ciphertexts with a subset of encryptions of zeroes whose positions are only known to the client. The goal is for the server to effectively compress the ciphertexts obliviously, while preserving the non-zero plaintexts and without learning the plaintext values. For oblivious decompression, the client, instead, succinctly encodes a sequence of plaintexts such that the server may decode encryptions of all plaintexts value, but the zeroes may be replaced with arbitrary values. We present solutions to both problems that construct lossless compressions only 5% more than the optimal minimum using only additive homomorphism. The crux of both algorithms involve embedding ciphertexts as random linear systems that are efficiently solvable.

Using our compression schemes, we obtain state-of-the-art schemes for batch private information retrieval (PIR) where a client wishes to privately retrieve multiple entries from a server-held database in one query. We show that our compression schemes may be used to reduce communication by up to 30% for batch PIR in both the single- and two-server settings.

Additionally, we study labeled private set intersection (PSI) in the unbalanced setting where one party's set is significantly smaller than the other party's set and each entry has associated data. By utilizing our novel compression algorithm, we present a protocol with 65-88% reduction in communication with comparable computation compared to prior works.



## 2024/337

* Title: Solving the Tensor Isomorphism Problem for special orbits with low rank points:  Cryptanalysis and repair of an Asiacrypt 2023 commitment scheme
* Authors: Valerie Gilchrist, Laurane Marco, Christophe Petit, Gang Tang
* [Permalink](https://eprint.iacr.org/2024/337)
* [Download](https://eprint.iacr.org/2024/337.pdf)

### Abstract

The Tensor Isomorphism Problem (TIP) has been shown to be equivalent to the matrix code equivalence problem, making it an interesting candidate on which to build post-quantum cryptographic primitives. These hard problems have already been used in protocol development. One of these, MEDS, is currently in Round 1 of NIST's call for additional post-quantum digital signatures.
    In this work, we consider the TIP for a special class of tensors. The hardness of the decisional version of this problem is the foundation of a commitment scheme proposed by D'Alconzo, Flamini, and Gangemi (Asiacrypt 2023). We present polynomial-time algorithms for the decisional and computational versions of TIP for special orbits, which implies that the commitment scheme is not secure. The key observations of these algorithms are that these special tensors contain some low-rank points, and their stabilizer groups are not trivial.
    With these new developments in the security of TIP in mind, we give a new commitment scheme based on the general TIP that is non-interactive, post-quantum, and statistically binding, making no new assumptions. Such a commitment scheme does not currently exist in the literature.



## 2024/553

* Title: Efficient Linkable Ring Signatures: New Framework and Post-Quantum Instantiations
* Authors: Yuxi Xue, Xingye Lu, Man Ho Au, Chengru Zhang
* [Permalink](https://eprint.iacr.org/2024/553)
* [Download](https://eprint.iacr.org/2024/553.pdf)

### Abstract

In this paper, we introduce a new framework for constructing linkable ring signatures (LRS). Our framework is based purely on signatures of knowledge (SoK) which allows one to issue signatures on behalf of any NP-statement using the corresponding witness. Our framework enjoys the following advantages: (1) the security of the resulting LRS depends only on the security of the underlying SoK; (2) the resulting LRS naturally supports online/offline signing (resp.. verification), where the output of the offline signing (resp. verification) can be re-used across signatures of the same ring. For a ring size $n$, our framework requires an SoK of the NP statement with size $\log n$.

To instantiate our framework, we adapt the well-known post-quantum secure non-interactive argument of knowledge (NIAoK), ethSTARK, into an SoK. This SoK is inherently post-quantum secure and has a signature size poly-logarithmic in the size of the NP statement. Thus, our resulting LRS has a signature size of $O(\text{polylog}(\log n))$. By comparison, existing post-quantum ring signatures, regardless of linkability considerations, have signature sizes of $O(\log n)$ at best. Furthermore, leveraging online/offline verification, part of the verification of signatures on the same ring can be shared, resulting in a state-of-the-art amortized verification cost of $O(\text{polylog}(\log n))$.

Our LRS also performs favourably against existing schemes in practical scenarios. Concretely, our scheme has the smallest signature size among all post-quantum linkable ring signatures with non-slanderability for ring size larger than $32$. In our experiment, at $128$-bit security and ring size of $1024$, our LRS has a size of $29$KB, and an amortized verification cost of $0.3$ ms, surpassing the state-of-the-art by a significant margin. Even without considering amortization, the verification time for a single signature is $128$ ms, comparable to those featuring linear signature size. A similar performance advantage can also be seen at signing. Furthermore, our LRS has extremely short public keys ($32$ bytes), while public keys of existing constructions are in the order of kilobytes.



## 2024/653

* Title: Ipotane: Achieving the Best of All Worlds in Asynchronous BFT
* Authors: Xiaohai Dai, Chaozheng Ding, Hai Jin, Julian Loss, Ling Ren
* [Permalink](https://eprint.iacr.org/2024/653)
* [Download](https://eprint.iacr.org/2024/653.pdf)

### Abstract

State-of-the-art asynchronous Byzantine Fault Tolerance (BFT) protocols integrate a partially-synchronous optimistic path. The holy grail in this paradigm is to match the performance of a partially-synchronous protocol in favorable situations and match the performance of a purely asynchronous protocol in unfavorable situations. Several prior works have made progress toward this goal by matching the efficiency of a partially-synchronous protocol in favorable conditions. However, their performance compared to purely asynchronous protocols is reduced when network conditions are unfavorable. To address these shortcomings, a recent work, Abraxas (CCS'23), presents the first optimistic asynchronous BFT protocol that retains stable throughput in all situations. However, Abraxas still incurs very high worst-case latency in unfavorable situations because it is slow at detecting the failure of its optimistic path. Another recent work, ParBFT (CCS'23) guarantees good latency in all situations, but suffers from reduced throughput in unfavorable situations due to its use of extra Asynchronous Binary Agreement (ABA) instances.

To approach our holy grail, we propose Ipotane, which delivers performance comparable to partially-synchronous protocols in favorable situations, and attains performance on par with purely asynchronous protocols in unfavorable situations—in both throughput and latency. Ipotane also runs the two paths simultaneously. It adopts two-chain HotStuff as the optimistic path, thus achieving high performance in favorable situations. As for the pessimistic path, we introduce a new primitive Dual-functional Byzantine Agreement (DBA), which packs the functionalities of biased ABA and Validated Asynchronous Byzantine Agreement (VABA). Ipotane runs DBA instances continuously as the pessimistic path. DBA’s ABA functionality quickly detects the optimistic path’s failure, ensuring Ipotane’s low latency in unfavorable situations. Meanwhile, the VABA functionality continuously produces blocks, maintaining Ipotane’s high throughput. Additionally, the biased property ensures that blocks committed via the optimistic path are respected by DBA instances, guaranteeing consistency across two paths. We conduct extensive experiments to demonstrate that Ipotane achieves high throughput and low latency in all situations.



## 2024/654

* Title: Monchi: Multi-scheme Optimization For Collaborative Homomorphic Identification
* Authors: Alberto Ibarrondo, Ismet Kerenciler, Hervé Chabanne, Vincent Despiegel, Melek Önen
* [Permalink](https://eprint.iacr.org/2024/654)
* [Download](https://eprint.iacr.org/2024/654.pdf)

### Abstract

This paper introduces a novel protocol for privacy-preserving biometric identification, named Monchi, that combines the use of homomorphic encryption for the computation of the identification score with function secret sharing to obliviously compare this score with a given threshold and finally output the binary result. Given the cost of homomorphic encryption, BFV in this solution, we study and evaluate the integration of two packing solutions that enable the regrouping of multiple templates in one ciphertext to improve efficiency meaningfully. We propose an end-to-end protocol, prove it secure and implement it. Our experimental results attest to Monchi's applicability to the real-life use case of an airplane boarding scenario with 1000 passengers,taking less than one second to authorize/deny access to the plane to each passenger via biometric identification while maintaining the privacy of all passengers.



## 2024/655

* Title: Implementation and Performance Analysis of Homomorphic Signature Schemes
* Authors: Davide Carnemolla, Dario Catalano, Mario Di Raimondo, Federico Savasta
* [Permalink](https://eprint.iacr.org/2024/655)
* [Download](https://eprint.iacr.org/2024/655.pdf)

### Abstract

Homomorphic signatures allow to validate computation on signed data. Alice, holding a dataset, $\{m_1 , \ldots , m_t \}$ uses her secret key $\sf sk$ to sign these data and stores the authenticated dataset on a remote server. The server can later (publicly) compute $m = f(m_1,...,m_t)$ together with a signature $\sigma$ certifying that $m$ is indeed the correct output of the computation $f$. Over the last fifteen years, the problem of realizing homomorphic signatures has been the focus of numerous research works, with constructions now ranging from very efficient ones supporting linear functions to very expressive ones supporting (up to) arbitrary circuits. In this work we tackle the question of assessing the practicality of schemes belonging to this latter class. Specifically, we implement the GVW lattice based scheme for circuits from STOC 2015 and two, recently proposed, pairings based constructions building from functional commitments. Our experiments show that (both) pairings based schemes outperform GVW on all fronts.



## 2024/656

* Title: Cryptanalytic Audit of the XHash Sponge Function and its Components
* Authors: Vincent Rijmen
* [Permalink](https://eprint.iacr.org/2024/656)
* [Download](https://eprint.iacr.org/2024/656.pdf)

### Abstract

In this audit we started from the security analysis provided in the design
documentation of XHash8/12. We extended the analysis in several directions and
confirmed the security claims that were made by the designers.



## 2024/657

* Title: Cryptographic Accumulators: New Definitions, Enhanced Security, and Delegatable Proofs
* Authors: Anaïs Barthoulot, Olivier Blazy, Sébastien Canard
* [Permalink](https://eprint.iacr.org/2024/657)
* [Download](https://eprint.iacr.org/2024/657.pdf)

### Abstract

Cryptographic accumulators, introduced in 1993 by Benaloh and De
Mare, represent a set with a concise value and offer proofs of (non-)membership. Accumulators have evolved, becoming essential in anonymous credentials, e-cash, and blockchain applications. Various properties like dynamic and universal emerged for specific needs, leading to multiple accumulator definitions. In 2015, Derler, Hanser, and Slamanig proposed a unified model, but new properties, including zero-knowledge security, have arisen since. We offer a new definition of accumulators, based on Derler et al.’s, that is suitable for all properties. We also introduce a new security property, unforgeability of private evaluation, to protect accumulator from forgery and we verify this property in Barthoulot, Blazy, and Canard’s recent accumulator. Finally we provide discussions on security properties of accumulators and on the delegatable (non-)membership proofs property.



## 2024/658

* Title: Information-theoretic security with asymmetries
* Authors: Tim Beyne, Yu Long Chen
* [Permalink](https://eprint.iacr.org/2024/658)
* [Download](https://eprint.iacr.org/2024/658.pdf)

### Abstract

In this paper, we study the problem of lower bounding any
given cost function depending on the false positive and false negative
probabilities of adversaries against indistinguishability security notions in symmetric-key cryptography. We take the cost model as an input, so that this becomes a purely information-theoretical question.

We propose power bounds as an easy-to-use alternative for advantage bounds in the context of indistinguishability with asymmetric cost functions. We show that standard proof techniques such as hybrid arguments and the H-coefficient method can be generalized to the power model, and apply these techniques to the PRP-PRF switching lemma, the Even-Mansour (EM) construction, and the sum-of-permutations (SoP) construction.

As the final and perhaps most useful contribution, we provide two methods to convert single-user power bounds into multi-user power bounds, and investigate their relation to the point-wise proximity method of Hoang and Tessaro (Crypto 2016). These method are applied to obtain tight multi-user power bounds for EM and SoP.



## 2024/659

* Title: Secure Latent Dirichlet Allocation
* Authors: Thijs Veugen, Vincent Dunning, Michiel Marcus, Bart Kamphorst
* [Permalink](https://eprint.iacr.org/2024/659)
* [Download](https://eprint.iacr.org/2024/659.pdf)

### Abstract

Topic modelling refers to a popular set of techniques used to discover hidden topics that occur in a collection of documents. These topics can, for example, be used to categorize documents or label text for further processing. One popular topic modelling technique is Latent Dirichlet Allocation (LDA). In topic modelling scenarios, the documents are often assumed to be in one, centralized dataset. However, sometimes documents are held by different parties, and contain privacy- or commercially-sensitive information that cannot be shared.
We present a novel, decentralized approach to train an LDA model securely without having to share any information about the content of the documents with the other parties. We preserve the privacy of the individual parties using a combination of privacy enhancing technologies.
We show that our decentralized, privacy preserving LDA solution has a similar accuracy compared to an (insecure) centralised approach. With $1024$-bit Paillier keys, a topic model with $5$ topics and $3000$ words can be trained in around $16$ hours. Furthermore, we show that the solution scales linearly in the total number of words and the number of topics.



## 2024/660

* Title: FE[r]Chain: Enforcing Fairness in Blockchain Data Exchanges Through Verifiable Functional Encryption
* Authors: Camille Nuoskala, Reyhaneh Rabbaninejad, Tassos Dimitriou, Antonis Michalas
* [Permalink](https://eprint.iacr.org/2024/660)
* [Download](https://eprint.iacr.org/2024/660.pdf)

### Abstract

Functional Encryption (FE) allows users to extract specific function-related information from encrypted data while preserving the privacy of the underlying plaintext. Though significant research has been devoted to developing secure and efficient Multi-Input Functional Encryption schemes supporting diverse functions, there remains a noticeable research gap in the development of verifiable FE schemes. Functionality and performance have received considerable attention, however, the crucial aspect of verifiability in FE has been relatively understudied. Another important aspect that prior research in FE with outsourced decryption has not adequately addressed is the fairness of the data-for-money exchange between a curator and an analyst. This paper focuses on addressing these gaps by proposing a verifiable FE scheme for inner product computation. The scheme not only supports the multi-client setting but also extends its functionality to accommodate multiple users -- an essential feature in modern privacy-respecting services. Additionally, it demonstrates how this FE scheme can be effectively utilized to ensure fairness and atomicity in a payment protocol, further enhancing the trustworthiness of data exchanges.



## 2024/661

* Title: On amortization techniques for FRI-based SNARKs
* Authors: Albert Garreta, Hayk Hovhanissyan, Aram Jivanyan, Ignacio Manzur, Isaac Villalobos, Michał Zając
* [Permalink](https://eprint.iacr.org/2024/661)
* [Download](https://eprint.iacr.org/2024/661.pdf)

### Abstract

We present two techniques to improve the computational and/or communication costs of STARK proofs: packing and modular split-and-pack.
 
Packing allows to generate a single proof of the satisfiability of several constraints. We achieve this by packing the evaluations of all relevant polynomials in the same Merkle leaves, and combining all DEEP FRI functions into a single randomized validity function. Our  benchmarks show that packing  reduces the verification time and proof size compared to individually proving the satisfiability of each witness, while only increasing the prover time moderately.
   
Modular split-and-pack is a proof acceleration technique where the prover divides a witness  into smaller sub-witnesses. It then uses packing to prove the simultaneous satisfiability of each sub-witness. Compared to producing a proof of the original witness, splitting improves the prover time and memory usage, while increasing the verifier time and proof size. Ideas similar to modular split-and-pack seem to be used throughout the industry, but 1) generally execution traces are split by choosing the first $k$ rows, then the next $k$ rows, and so on; and 2) full recursion is used to prove the simultaneous satisfiability of the sub-witnesses, usually combined with a final wrapper proof (typically a Groth16 proof). We present a different way to split the witness that allows for an efficient re-writing of Plonkish-type constraints. Based on our benchmarks, we believe this approach (together with a wrapper proof)  can improve upon existing splitting methods, resulting in a faster prover at essentially no cost in proof size and verification time.

Both techniques apply to popular FRI-based proof systems such as ethSTARK, Plonky2/3, RISC Zero, and Boojum.



## 2024/662

* Title: Faster Private Decision Tree Evaluation for Batched Input from Homomorphic Encryption
* Authors: Kelong Cong, Jiayi Kang, Georgio Nicolas, Jeongeun Park
* [Permalink](https://eprint.iacr.org/2024/662)
* [Download](https://eprint.iacr.org/2024/662.pdf)

### Abstract

Privacy-preserving decision tree evaluation (PDTE) allows a client that holds feature vectors to perform inferences against a decision tree model on the server side without revealing feature vectors to the server. Our work focuses on the non-interactive batched setting where the client sends a batch of encrypted feature vectors and then obtains classifications, without any additional interaction. This is useful in privacy-preserving credit scoring, biometric authentication, and many more applications.

In this paper, we propose two novel non-interactive batched PDTE protocols, BPDTE_RCC and BPDTE_CW, based on two new ciphertext-plaintext comparison algorithms, the improved range cover comparison (RCC) comparator and the constant-weight (CW) piece-wise comparator, respectively. Compared to the current state-of-the-art Level Up (CCS'23), our comparison algorithms are up to $72\times$ faster for batched inputs of 16 bits. Moreover, we introduced a new tree traversal method called Adapted SumPath, to achieve $\mathcal{O}(1)$ complexity of the server's response, whereas Level Up has $\mathcal{O}(2^d)$ for a depth-$d$ tree where the client needs to look up classification values in a table.. Overall, our PDTE protocols attain the optimal server-to-client communication complexity and are up to $17\times$ faster than Level Up in batch size 16384.



## 2024/663

* Title: Xproofs: New Aggregatable and Maintainable Matrix Commitment with Optimal Proof Size
* Authors: Xinwei Yong, Jiaojiao Wu, Jianfeng Wang
* [Permalink](https://eprint.iacr.org/2024/663)
* [Download](https://eprint.iacr.org/2024/663.pdf)

### Abstract

Vector Commitment (VC) enables one to commit to a vector, and then the element at a specific position can be opened, with proof of consistency to the initial commitment. VC is a powerful primitive with various applications, including stateless cryptocurrencies. Recently, matrix commitment Matproofs (Liu and Zhang CCS 2022), as an extension of VC, has been proposed to reduce the communication and computation complexity of VC-based cryptocurrencies. However, Matproofs requires linear-sized public parameters, and the aggregated proof size may also increase linearly with the number of individual proofs aggregated.. Additionally, the proof updating process involves the third party, known as Proof-Serving Nodes (PSNs), which leads to extra storage and communication overhead. In this paper, we first propose a multi-dimensional variant of matrix commitment and construct a new matrix commitment scheme for two-dimensional matrix, called 2D-Xproofs, which achieves optimal aggregated proof size without using PSNs. Furthermore, we present a highly maintainable three-dimensional scheme, 3D-Xproofs, which updates all proofs within time sublinear in the size of the committed matrix without PSNs' assistance. More generally, we could further increase the matrix dimensionality to achieve more efficient proof updates. Finally, we demonstrate the security of our schemes, showing that both schemes are position binding. We also implement both schemes, and the results indicate that our schemes enjoy constant-sized aggregated proofs and sublinear-sized public parameters, and the proof update time in 3D-Xproofs is $2..5\times$ faster than Matproofs.



## 2024/664

* Title: Pando: Extremely Scalable BFT Based on Committee Sampling
* Authors: Xin Wang, Haochen Wang, Haibin Zhang, Sisi Duan
* [Permalink](https://eprint.iacr.org/2024/664)
* [Download](https://eprint.iacr.org/2024/664.pdf)

### Abstract

Byzantine fault-tolerant (BFT) protocols are known to suffer from the scalability issue. Indeed, their performance degrades drastically as the number of replicas $n$ grows. While a long line of work has attempted to achieve the scalability goal, these works can only scale to roughly a hundred replicas.

In this paper, we develop BFT protocols from the so-called committee sampling approach that selects a small committee for consensus and conveys the results to all replicas. Such an approach, however, has been focused on the Byzantine agreement (BA) problem (considering replicas only) instead of the BFT problem (in the client-replica model); also, the approach is mainly of theoretical interest only, as concretely, it works for impractically large $n$.

We build an extremely efficient, scalable, and adaptively secure BFT protocol called Pando in partially synchronous environments based on the committee sampling approach. In particular, we devise novel BFT building blocks targeting scalability, including communication-efficient and computation-efficient consistent broadcast and atomic broadcast protocols.

Pando inherits some inherent issues of committee sampling-based protocols: Pando can only achieve near-optimal resilience (i.e., $f<(1/3-\epsilon)n$, where $f$ is the number of faulty replicas and $\epsilon$ is a small constant), and Pando attains safety and liveness only probabilistically. Interestingly, to make $\epsilon$ come close to 0 (near-optimal resilience), $n$ needs to be sufficiently large but not impractically large, e.g., $n>500$---just what we need for scalable BFT.

Our evaluation on  Amazon EC2 shows that in contrast to existing protocols, Pando can easily scale to a thousand replicas in the WAN environment, achieving a throughput of 62.57 ktx/sec.



## 2024/665

* Title: Homomorphic Evaluation of LWR-based PRFs and Application to Transciphering
* Authors: Amit Deo, Marc Joye, Benoit Libert, Benjamin R. Curtis, Mayeul de Bellabre
* [Permalink](https://eprint.iacr.org/2024/665)
* [Download](https://eprint.iacr.org/2024/665.pdf)

### Abstract

Certain applications such as FHE transciphering require randomness while operating over encrypted data. This randomness has to be obliviously generated in the encrypted domain and remain encrypted throughout the computation. Moreover, it should be guaranteed that independent-looking random coins can be obliviously generated for different computations.

In this work, we consider the homomorphic evaluation of pseudorandom functions (PRFs) with a focus on practical lattice-based candidates. In the homomorphic PRF evaluation setting, given a fully homomorphic encryption of the PRF secret key $\vec{s}$, it should be possible to homomorphically compute encryptions of PRF evaluations $\{ \text{PRF}_{\vec{s}}(x_i) \}_{i=1}^M$ for public inputs $\{ x_i\}_{i=1}^M$.  We consider this problem for PRF families based on the hardness of the Learning-With-Rounding (LWR) problem introduced by Banerjee, Peikert and Rosen (Eurocrypt '12). We build on the random-oracle variant of a PRF construction suggested by Banerjee et al. and demonstrate that it can be evaluated using only two sequential programmable bootstraps in the TFHE homomorphic encryption scheme. We also describe several modifications of this PRF---which we prove as secure as the original function---that support homomorphic evaluations using only one programmable bootstrap per slot. 

Numerical experiments were conducted using practically relevant FHE parameter sets from the TFHE-rs library.  Our benchmarks show that a throughput of about $1000$ encrypted pseudorandom bits per second (resp. $900$ encrypted pseudorandom bits per second) can be achieved on an AWS hpc7a.96xlarge machine (resp. on a standard laptop with an Apple M2 chip), on a single thread. The PRF evaluation keys in our experiments have sizes roughly $40\%$ and $60\%$ of a bootstrapping key. Applying our solution to transciphering enables important bandwidth savings, typically trading $64$-bit values for $4$-bit values per transmitted ciphertext.



## 2024/666

* Title: Private Analytics via Streaming, Sketching, and Silently Verifiable Proofs
* Authors: Mayank Rathee, Yuwen Zhang, Henry Corrigan-Gibbs, Raluca Ada Popa
* [Permalink](https://eprint.iacr.org/2024/666)
* [Download](https://eprint.iacr.org/2024/666.pdf)

### Abstract

We present Whisper, a system for privacy-preserving collection of aggregate statistics. Like prior systems, a Whisper deployment consists of a small set of non-colluding servers; these servers compute aggregate statistics over data from a large number of users without learning the data of any individual user. Whisper’s main contribution is that its server- to-server communication cost and its server-side storage costs scale sublinearly with the total number of users. In particular, prior systems required the servers to exchange a few bits of information to verify the well-formedness of each client submission. In contrast, Whisper uses silently verifiable proofs, a new type of proof system on secret-shared data that allows the servers to verify an arbitrarily large batch of proofs by exchanging a single 128-bit string. This improvement comes with increased client-to-server communication, which, in cloud computing, is typically cheaper (or even free) than the cost of egress for server-to-server communication. To reduce server storage, Whisper approximates certain statistics using small-space sketching data structures. Applying randomized sketches in an environment with adversarial clients requires a careful and novel security analysis. In a deployment with two servers and 100,000 clients of which 1% are malicious, Whisper can improve server-to-server communication for vector sum by three orders of magnitude while each client’s communication increases by only 10%.



## 2024/667

* Title: Agile, Post-quantum Secure Cryptography in Avionics
* Authors: Karolin Varner, Wanja Zaeske, Sven Friedrich, Aaron Kaiser, Alice Bowman
* [Permalink](https://eprint.iacr.org/2024/667)
* [Download](https://eprint.iacr.org/2024/667.pdf)

### Abstract

To introduce a post-quantum-secure encryption scheme specifically for use in flight-computers, we used avionics’ module-isolation methods to wrap a recent encryption standard (HPKE – Hybrid Public Key Encryption) within a software partition. This solution proposes an upgrade to HPKE, using quantum-resistant ciphers (Kyber/ML-KEM and Dilithium/ML-DSA) redundantly alongside well-established ciphers, to achieve post-quantum security.

Because cryptographic technology can suddenly become obsolete as attacks become more sophisticated, "crypto-agility" -– the ability to swiftly replace ciphers – represents the key challenge to deployment of software like ours. Partitioning is a crucial method for establishing such agility, as it enables the replacement of compromised software without affecting software on other partitions, greatly simplifying the certification process necessary in an avionics environment.

Our performance measurements constitute initial evidence that both the memory and performance characteristics of this approach are suitable for deployment in flight-computers currently in use. Prior to optimisation, performance measurements show a modest memory requirement of under 400 KB of RAM, but employ a more substantial stack usage of just under 200 KB. Our most advanced redundant post-quantum cipher is five times slower than its non-redundant, pre-quantum counterpart.



## 2024/668

* Title: Blockchain Price vs. Quantity Controls
* Authors: Abdoulaye Ndiaye
* [Permalink](https://eprint.iacr.org/2024/668)
* [Download](https://eprint.iacr.org/2024/668.pdf)

### Abstract

This paper studies the optimal transaction fee mechanisms for blockchains, focusing on the distinction between price-based ($\mathcal{P}$) and quantity-based ($\mathcal{Q}$) controls. By analyzing factors such as demand uncertainty, validator costs, cryptocurrency price fluctuations, price elasticity of demand, and levels of decentralization, we establish criteria that determine the selection of transaction fee mechanisms. We present a model framed around a Nash bargaining game, exploring how blockchain designers and validators negotiate fee structures to balance network welfare with profitability. Our findings suggest that the choice between $\mathcal{P}$ and $\mathcal{Q}$ mechanisms depends critically on the blockchain’s specific technical and economic features. The study concludes that no single mechanism suits all contexts and highlights the potential for hybrid approaches that adaptively combine features of both $\mathcal{P}$ and $\mathcal{Q}$ to meet varying demands and market conditions.



## 2024/669

* Title: Mempool Privacy via Batched Threshold Encryption: Attacks and Defenses
* Authors: Arka Rai Choudhuri, Sanjam Garg, Julien Piet, Guru-Vamsi Policharla
* [Permalink](https://eprint.iacr.org/2024/669)
* [Download](https://eprint.iacr.org/2024/669.pdf)

### Abstract

With the rising popularity of DeFi applications it is important to implement protections for regular users of these DeFi platforms against large parties with massive amounts of resources allowing them to engage in market manipulation strategies such as frontrunning/backrunning. Moreover, there are many situations (such as recovery of funds from vulnerable smart contracts) where a user may not want to reveal their transaction until it has been executed. As such, it is clear that preserving the privacy of transactions in the mempool is an important goal.

In this work we focus on achieving mempool transaction privacy through a new primitive that we term batched-threshold encryption, which is a variant of threshold encryption with strict efficiency requirements to better model the needs of resource constrained environments such as blockchains. Unlike the naive use of threshold encryption, which requires communication proportional to $O(nB)$ to decrypt $B$ transactions with a committee of $n$ parties, our batched-threshold encryption scheme only needs $O(n)$ communication. We additionally discuss pitfalls in prior approaches that use (vanilla) threshold encryption for mempool privacy.

To show that our scheme is concretely efficient, we implement our scheme and find that transactions can be encrypted in under 6 ms, independent of committee size, and the communication required to decrypt an entire batch of $B$ transactions is 80 bytes per party, independent of the number of transactions $B$, making it an attractive choice when communication is very expensive. If deployed on Ethereum, which processes close to 500 transaction per block, it takes close to 2.8 s for each committee member to compute a partial decryption and under 3.5 s to decrypt all transactions for a block in single-threaded mode.



## 2024/670

* Title: Secure Implementation of SRAM PUF for Private Key Generation
* Authors: Raja Adhithan Radhakrishnan
* [Permalink](https://eprint.iacr.org/2024/670)
* [Download](https://eprint.iacr.org/2024/670.pdf)

### Abstract

This paper endeavors to securely implement a Physical Unclonable
Function (PUF) for private data generation within Field-Programmable
Gate Arrays (FPGAs). SRAM PUFs are commonly utilized due to their
use of memory devices for generating secret data, particularly in resource constrained devices. However, their reliance on memory access poses side-channel threats such as data remanence decay and memory-based attacks, and the time required to generate secret data is significant. To address these issues, we propose implementing n cross-coupled inverters in Verilog to generate n secret bits, followed by syndrome for error correction hardcoded in the hardware itself. This approach improves side channel security and reduces time consumption, albeit at the expense of additional area utilization



## 2024/671

* Title: Exploiting Internal Randomness for Privacy in Vertical Federated Learning
* Authors: Yulian Sun, Li Duan, Ricardo Mendes, Derui Zhu, Yue Xia, Yong Li, Asja Fischer
* [Permalink](https://eprint.iacr.org/2024/671)
* [Download](https://eprint.iacr.org/2024/671.pdf)

### Abstract

Vertical Federated Learning (VFL) is becoming a standard collaborative learning paradigm with various practical applications. Randomness is essential to enhancing privacy in VFL, but introducing too much external randomness often leads to an intolerable performance loss. Instead, as it was demonstrated for other federated learning settings, leveraging internal randomness —as provided by variational autoencoders (VAEs) —can be beneficial. However, the resulting privacy has never been quantified so far nor has the approach been investigated for VFL.
We therefore propose a novel differential privacy estimate, denoted as distance-based empirical local differential privacy (dELDP). It allows to empirically bound DP parameters of concrete components, quantifying the internal randomness with appropriate distance and sensitivity metrics. We apply dELDP to investigate the DP of VAEs and observe values up to ε ≈ 6.4 and δ = 2−32. Moreover, to link the dELDP parameters to the privacy of full VAE-including VFL systems in practice, we conduct comprehensive experiments on the robustness against state-of-the-art privacy attacks. The results illustrate that the VAE system is effective against feature reconstruction attacks and outperforms other privacy-enhancing methods for VFL, especially when the adversary holds 75% of features in label inference attack.



## 2024/672

* Title: Secure Coded Distributed Computing
* Authors: Shanuja Sasi, Onur Gunlu
* [Permalink](https://eprint.iacr.org/2024/672)
* [Download](https://eprint.iacr.org/2024/672.pdf)

### Abstract

In this paper, we consider two critical aspects of security in the distributed computing (DC) model: secure data shuffling and secure coded computing. It is imperative that any external entity overhearing the transmissions does not gain any information about the intermediate values (IVs) exchanged during the shuffling phase of the DC model. Our approach ensures IV confidentiality during data shuffling. Moreover, each node in the system must be able to recover the IVs necessary for computing its output functions but must also remain oblivious to the IVs associated with output functions not assigned to it. We design secure DC methods and establish achievable limits on the tradeoffs between the communication and computation loads to contribute to the advancement of secure data processing in distributed systems.



## 2024/673

* Title: Chocobo: Creating Homomorphic Circuit Operating with Functional Bootstrapping in basis B
* Authors: Pierre-Emmanuel Clet, Aymen Boudguiga, Renaud Sirdey
* [Permalink](https://eprint.iacr.org/2024/673)
* [Download](https://eprint.iacr.org/2024/673.pdf)

### Abstract

The TFHE cryptosystem only supports small plaintext space, up to 5 bits with usual parameters. However, one solution to circumvent this limitation is to decompose input messages into a basis B over multiple ciphertexts. In this work, we introduce B-gates, an extension of logic gates to non binary bases, to compute base B logic circuit. The flexibility introduced by our approach improves the speed performance over previous approaches such as the so called tree-based method which requires an exponential amount of operations in the number of inputs. We provide experimental results using sorting as a benchmark application and, additionally, we obtain a speed-up of ×3 in latency compared to state of the art BGV techniques for this application. As an additional result, we introduce a keyswitching key specific to packing TLWE ciphertexts into TRLWE ciphertexts with redundancy, which is of interest in many functional bootstrapping scenarios.



## 2024/674

* Title: SigmaSuite: How to Minimize Foreign Arithmetic in ZKP Circuits While Keeping Succinct Final Verification.
* Authors: Wyatt Benno
* [Permalink](https://eprint.iacr.org/2024/674)
* [Download](https://eprint.iacr.org/2024/674.pdf)

### Abstract

Foreign field arithmetic often creates significant additional overheads in zero-knowledge proof circuits. Previous work has offloaded foreign arithmetic from proof circuits by using effective and often simple primitives such as Sigma protocols. While these successfully move the foreign field work outside of the circuit, the costs for the Sigma protocol’s verifier still remains high. In use cases where the verifier is constrained computationally this poses a major challenge. One such use case would be in proof composition where foreign arithmetic causes a blowup in the costs for the verifier circuit. In this work we show that by using folding scheme with Sigmabus and other such uniform verifier offloading techniques, we can remove foreign field arithmetic from zero-knowledge proof circuits while achieving succinct final verification. We do this by applying prior techniques iteratively and accumulate the resulting verifier work into one folding proof of size O(|F|) group elements, where F is the size of a single Sigma verifier’s computation. Then by using an existing zkSNARK we can further compress to a proof size of O(log |F|) which can be checked succinctly by a computationally constrained verifier.



## 2024/675

* Title: Olympic Privacy-Preserving Blueprints: Faster Communication, Highly Functional, Stronger Security
* Authors: Scott Griffy, Markulf Kohlweiss, Anna Lysyanskaya, Meghna Sengupta
* [Permalink](https://eprint.iacr.org/2024/675)
* [Download](https://eprint.iacr.org/2024/675.pdf)

### Abstract

Introduced by Kohlweiss, Lysyanskaya, and Nguyen (Eurocrypt'23), an $f$-privacy-preserving blueprint (PPB) system allows an auditor with secret input $x$ to create a public encoding of the function $f(x,\cdot)$ that verifiably corresponds to a commitment $C_x$ to $x$.  The auditor will then be able to derive $f(x,y)$ from an escrow $Z$ computed by a user on input the user's private data $y$ corresponding to a commitment $C_y$.  $Z$ verifiably corresponds to the commitment $C_y$ and reveals no other information about $y$.
PPBs provide an abuse-resistant escrow mechanism: for example, if $f$ is the watchlist function where $f(x,y)$ outputs $y$ only in the event that $y$ is on the list $x$, then an $f$-PPB allows the auditor to trace watchlisted users in an otherwise anonymous system.  Yet, the auditor's $x$ must correspond to a publicly available (and potentially authorized by a transparent, lawful process) $C_x$, and the auditor will learn nothing except $f(x,y)$.
In this paper, we build on the original PPB results in three ways: (1) We define and satisfy a stronger notion of security where a malicious auditor cannot frame a user in a transaction to which this user was not a party. (2) We provide efficient schemes for a bigger class of functions $f$; for example, for the first time, we show how to realize $f$ that would allow the auditor to trace e-cash transactions of a criminal suspect. (3) For the watchlist and related functions, we reduce the size of the escrow $Z$ from linear in the size of the auditor's input $x$, to logarithmic.



## 2024/676

* Title: Composing Timed Cryptographic Protocols: Foundations and Applications
* Authors: Karim Eldefrawy, Benjamin Terner, Moti Yung
* [Permalink](https://eprint.iacr.org/2024/676)
* [Download](https://eprint.iacr.org/2024/676.pdf)

### Abstract

Time-lock puzzles are unique cryptographic primitives that use computational complexity to keep information secret for some period of time, after which security expires. Unfortunately, current analysis techniques of time-lock primitives provide no sound mechanism to build multi-party cryptographic protocols which use expiring security as a building block. We explain in this paper that all other attempts at this subtle problem lack either composability, a fully consistent analysis, or functionality. The subtle flaws in the existing frameworks reduce to an impossibility by Mahmoody et al., who showed that time-lock puzzles with super-polynomial gaps (between committer and solver) cannot be constructed from random oracles alone; yet still the analyses of algebraic puzzles today treat the solving process as if each step is a generic or random oracle.

This paper presents a new complexity theoretic based framework and new structural theorems to analyze timed primitives with full generality and in composition (which is the central modular protocol design tool). The framework includes a model of security based on fine-grained circuit complexity which we call residual complexity, which accounts for possible leakage on timed primitives as they expire. Our definitions for multi-party computation protocols generalize the literature standards by accounting for fine-grained polynomial circuit depth to model computational hardness which expires in feasible time. Our composition theorems incur degradation of (fine-grained) security as items are composed. In our framework, simulators are given a polynomial “budget” for how much time they spend, and in composition these polynomials interact.

Finally, we demonstrate via a prototypical auction application how to  apply our framework and theorems. For the first time, we show that it is possible to prove – in a way that is fully consistent, with falsifiable assumptions – properties of multi-party applications based on leaky, temporarily secure components.