[digest] 2024 Week 47

## In this issue

1. [2023/1727] A Formal Treatment of Envelope Encryption
2. [2024/1586] WHIR: Reed–Solomon Proximity Testing with Super- ...
3. [2024/1879] Practical Zero-Knowledge PIOP for Public Key and ...
4. [2024/1880] Cryptography Experiments In Lean 4: SHA-3 ...
5. [2024/1881] THOR: Secure Transformer Inference with Homomorphic ...
6. [2024/1882] Single Trace Side-Channel Attack on the MPC-in-the- ...
7. [2024/1883] A Fault Analysis on SNOVA
8. [2024/1884] Age-aware Fairness in Blockchain Transaction ...
9. [2024/1885] Improved PIR Schemes using Matching Vectors and ...
10. [2024/1886] Impossibility Results for Post-Compromise Security ...
11. [2024/1887] Differential MITM attacks on SLIM and LBCIoT
12. [2024/1888] Chosen-Prefix Collisions on AES-like Hashing
13. [2024/1889] IO-Optimized Design-Time Configurable Negacyclic ...
14. [2024/1890] Efficient Modular Multiplication Hardware for ...
15. [2024/1891] Shifting our knowledge of MQ-Sign security
16. [2024/1892] A Comprehensive Survey on Hardware-Software co- ...
17. [2024/1893] High Speed High Assurance implementations of ...
18. [2024/1894] A non-comparison oblivious sort and its application ...
19. [2024/1895] A Tool for Fast and Secure LWE Parameter Selection: ...
20. [2024/1896] Shardora: Towards Scaling Blockchain Sharding via ...
21. [2024/1897] On Threshold Signatures from MPC-in-the-Head
22. [2024/1898] NTRU-based Bootstrapping for MK-FHEs without using ...
23. [2024/1899] Fast Multiplication and the PLWE-RLWE Equivalence ...
24. [2024/1900] Opening the Blackbox: Collision Attacks on Round- ...
25. [2024/1901] On the Insecurity of Bloom Filter-Based Private Set ...
26. [2024/1902] ZK-SNARKs for Ballot Validity: A Feasibility Study
27. [2024/1903] Trustworthy Approaches to RSA: Efficient ...
28. [2024/1904] An Open Source Ecosystem for Implementation ...
29. [2024/1905] OPL4GPT: An Application Space Exploration of ...
30. [2024/1906] On Efficient Computations of Koblitz Curves over ...
31. [2024/1907] Towards Optimal Garbled Circuits in the Standard Model
32. [2024/1908] Generalized Impossible Differential Attacks on ...
33. [2024/1909] NewtonPIR: Communication Efficient Single-Server PIR
34. [2024/1910] Stealth Software Trojan: Amplifying Hidden RF Side- ...
35. [2024/1911] Deletions and Dishonesty: Probabilistic Data ...

## 2023/1727

* Title: A Formal Treatment of Envelope Encryption
* Authors: Shoichi Hirose, Kazuhiko Minematsu
* [Permalink](https://eprint.iacr.org/2023/1727)
* [Download](https://eprint.iacr.org/2023/1727.pdf)

### Abstract

Envelope encryption is a method to encrypt data with two distinct keys in its basic form.  Data is first encrypted with a data-encryption key, and then the data-encryption key is encrypted with a key-encryption key.  Despite its deployment in major cloud services, as far as we know, envelope encryption has not received any formal treatment.  To address this issue, we first formalize the syntax and security requirements of envelope encryption in the symmetric-key setting.  Then, we show that it can be constructed by combining encryptment and authenticated encryption with associated data (AEAD).  Encryptment is one-time AEAD satisfying that a small part of a ciphertext works as a commitment to the corresponding secret key, message, and associated data.  Finally, we show that the security of the generic construction is reduced to the security of the underlying encryptment and AEAD.



## 2024/1586

* Title: WHIR: Reed–Solomon Proximity Testing with Super-Fast Verification
* Authors: Gal Arnon, Alessandro Chiesa, Giacomo Fenzi, Eylon Yogev
* [Permalink](https://eprint.iacr.org/2024/1586)
* [Download](https://eprint.iacr.org/2024/1586.pdf)

### Abstract

We introduce WHIR, a new IOP of proximity that offers small query complexity and exceptionally fast verification time. The WHIR verifier typically runs in a few hundred microseconds, whereas other verifiers in the literature require several milliseconds (if not much more). This significantly improves the state of the art in verifier time for hash-based SNARGs (and beyond).
Crucially, WHIR is an IOP of proximity for constrained Reed–Solomon codes, which can express a rich class of queries to multilinear polynomials and to univariate polynomials. In particular, WHIR serves as a direct replacement for protocols like FRI, STIR, BaseFold, and others. Leveraging the rich queries supported by WHIR and a new compiler for multilinear polynomial IOPs, we obtain a highly efficient SNARG for generalized R1CS.
As a comparison point, our techniques also yield state-of-the-art constructions of hash-based (non-interactive) polynomial commitment schemes for both univariate and multivariate polynomials (since sumcheck queries naturally express polynomial evaluations). For example, if we use WHIR to construct a polynomial commitment scheme for degree 222, with 100 bits of security, then the time to commit and open is 1.2 seconds, the sender communicates 63 KiB to the receiver, and the opening verification time is 360 microseconds.



## 2024/1879

* Title: Practical Zero-Knowledge PIOP for Public Key and Ciphertext Generation in (Multi-Group) Homomorphic Encryption
* Authors: Intak Hwang, Hyeonbum Lee, Jinyeong Seo, Yongsoo Song
* [Permalink](https://eprint.iacr.org/2024/1879)
* [Download](https://eprint.iacr.org/2024/1879.pdf)

### Abstract

Homomorphic encryption (HE) is a foundational technology in privacy-enhancing cryptography, enabling non-interactive computation over encrypted data. Recently, generalized HE primitives designed for multi-party applications, such as multi-group HE (MGHE), have gained significant research interest.
While constructing secure multi-party protocols from (MG)HE in the semi-honest model is straightforward, zero-knowledge techniques are essential for ensuring security against malicious adversaries.

In this work, we design practical proof systems for MGHE to guarantee the well-formedness of public keys and ciphertexts. Specifically, we develop and optimize a polynomial interactive oracle proof (PIOP) for MGHE, which can be compiled into zk-SNARKs using a polynomial commitment scheme (PCS).

We compile our PIOP using a lattice-based PCS, and our implementation achieves a 5.5x reduction in proof size, a 70x speed-up in proof generation, and a 343x improvement in verification time compared to the previous state-of-the-art construction, PELTA (ACM CCS 2023). Additionally, our PIOPs are modular, enabling the use of alternative PCSs to optimize other aspects, such as further reducing proof sizes.



## 2024/1880

* Title: Cryptography Experiments In Lean 4: SHA-3 Implementation
* Authors: Gérald Doussot
* [Permalink](https://eprint.iacr.org/2024/1880)
* [Download](https://eprint.iacr.org/2024/1880.pdf)

### Abstract

In this paper we explain how we implemented the Secure Hash Algorithm-3 (SHA-3) family of functions in Lean 4, a functional programming language and theorem prover. We describe how we used several Lean facilities including type classes, dependent types, macros, and formal verification, and then refined the design to provide a simple one-shot and streaming API for hashing, and Extendable-output functions (XOFs), to reduce potential for misuse by users, and formally prove properties about the implementation.



## 2024/1881

* Title: THOR: Secure Transformer Inference with Homomorphic Encryption
* Authors: Jungho Moon, Dongwoo Yoo, Xiaoqian Jiang, Miran Kim
* [Permalink](https://eprint.iacr.org/2024/1881)
* [Download](https://eprint.iacr.org/2024/1881.pdf)

### Abstract

As language models are increasingly deployed in cloud environments, privacy concerns have become a significant issue. To address this, we design THOR, a secure inference framework for transformer models on encrypted data. Specifically, we first propose new fast matrix multiplication algorithms based on diagonal-major order encoding and extend them to parallel matrix computation through the compact ciphertext packing technique. Second, we design efficient protocols for secure computations of four non-linear functions such as softmax, LayerNorm, GELU, and Tanh, by integrating advanced underlying approximation methods with tailored optimizations. Our matrix multiplication algorithms reduce the number of key-switching operations in the linear layers of the attention block in the BERT-base model by up to 14.5x, compared to the state-of-the-art HE-based secure inference protocol (Park et al., Preprint). Combined with cryptographic optimizations, our experimental results demonstrate that THOR provides secure inference for the BERT-base model with a latency of 10.43 minutes on a single GPU, while maintaining comparable inference accuracy on the MRPC dataset.



## 2024/1882

* Title: Single Trace Side-Channel Attack on the MPC-in-the-Head Framework
* Authors: Julie Godard, Nicolas Aragon, Philippe Gaborit, Antoine Loiseau, Julien Maillard
* [Permalink](https://eprint.iacr.org/2024/1882)
* [Download](https://eprint.iacr.org/2024/1882.pdf)

### Abstract

In this paper, we present the first single trace side-channel attack that targets the MPC-in-the-Head (MPCitH) framework based on threshold secret sharing, also known as Threshold Computation in the Head (TCitH) in its original version. This MPCitH framework can be found in 5 of the 14 digital signatures schemes in the recent second round of the National Institute of Standards and Technology (NIST) call for digital signatures. In this work, we start by highlighting a side-channel vulnerability of the TCitH framework and show an exploitation of it on the SDitH algorithm, which is part of this NIST call. Specifically, we exploit the leakage of a multiplication function in the Galois field to make predictions about intermediate values, and we use the structure of the algorithm to combine information efficiently. This allows us to build an attack that is both the first Soft Analytical Side-Channel Attack (SASCA) targeting the MPCitH framework, as well as the first attack on SDitH. More specifically, we build a SASCA based on Belief Propagation (BP) on the evaluation of polynomials in the signature using the threshold variant structure to reconstruct the secret key. We perform simulated attacks under the Hamming Weight (HW) leakage model, enabling us to evaluate the resistance of the scheme against SASCA. We then perform our attacks in a real case scenario, more specifically on the STM32F407, and recover the secret key for all the security levels. We end this paper by discussing the various shuffling countermeasures we could use to mitigate our attacks.



## 2024/1883

* Title: A Fault Analysis on SNOVA
* Authors: Gustavo Banegas, Ricardo Villanueva-Polanco
* [Permalink](https://eprint.iacr.org/2024/1883)
* [Download](https://eprint.iacr.org/2024/1883.pdf)

### Abstract

SNOVA is a post-quantum cryptographic signature scheme known for its efficiency and compact key sizes, making it a second-round candidate in the NIST post-quantum cryptography standardization process. This paper presents a comprehensive fault analysis of SNOVA, focusing on both permanent and transient faults during signature generation. We introduce several fault injection strategies that exploit SNOVA's structure to recover partial or complete secret keys with limited faulty signatures. Our analysis reveals that as few as $22$ to $68$ faulty signatures, depending on the security level, can suffice for key recovery. We propose a novel fault-assisted reconciliation attack, demonstrating its effectiveness in extracting the secret key space via solving a quadratic polynomial system. Simulations show transient faults in key signature generation steps can significantly compromise SNOVA’s security. To address these vulnerabilities, we propose a lightweight countermeasure to reduce the success of fault attacks without adding significant overhead. Our results highlight the importance of fault-resistant mechanisms in post-quantum cryptographic schemes like SNOVA to ensure robustness.



## 2024/1884

* Title: Age-aware Fairness in Blockchain Transaction Ordering for Reducing Tail Latency
* Authors: Yaakov Sokolik, Mohammad Nassar, Ori Rottenstriech
* [Permalink](https://eprint.iacr.org/2024/1884)
* [Download](https://eprint.iacr.org/2024/1884.pdf)

### Abstract

In blockchain networks, transaction latency is crucial for determining the quality of service (QoS). The latency of a transaction is measured as the time between its issuance and its inclusion in a block in the chain. A block proposer often prioritizes transactions with higher fees or transactions from accounts it is associated with, to minimize their latencies. To maintain fairness among transactions, a block proposer is expected to select the included transactions randomly. The random selection might cause some transactions to experience high latency following the variance in the time a transaction waits until it is selected. We suggest an alternative, age-aware approach towards fairness so that transaction priority is increased upon observing a large waiting time. We explain that a challenge with this approach is that the age of a transaction is not absolute due to transaction propagation. Moreover, a node might present its transactions as older to obtain priority. We describe a new technique to enforce a fair block selection while prioritizing transactions that observed high latency.  The technique is based on various declaration schemes in which a node declares its pending transactions, providing the ability to validate transaction age. By evaluating the solutions on Ethereum data and synthetic data of various scenarios, we demonstrate the advantages of the approach under realistic conditions and understand its potential impact to maintain fairness and reduce tail latency.



## 2024/1885

* Title: Improved PIR Schemes using Matching Vectors and Derivatives
* Authors: Fatemeh Ghasemi, Swastik Kopparty, Madhu Sudan
* [Permalink](https://eprint.iacr.org/2024/1885)
* [Download](https://eprint.iacr.org/2024/1885.pdf)

### Abstract

In this paper, we construct new t-server Private Information Retrieval (PIR) schemes with communication complexity subpolynomial in the previously best known, for all but finitely many t. Our results are
based on combining derivatives (in the spirit of Woodruff-Yekhanin) with the Matching Vector based PIRs of Yekhanin and Efremenko. Previously such a combination was achieved in an ingenious way by Dvir and Gopi, using polynomials and derivatives over certain exotic rings, en route to their fundamental result giving the first 2-server PIR with subpolynomial communication.

Our improved PIRs are based on two ingredients:

• We develop a new and direct approach to combine derivatives with Matching Vector based PIRs.
This approach is much simpler than that of Dvir-Gopi: it works over the same field as the original PIRs, and only uses elementary properties of polynomials and derivatives.

• A key subproblem that arises in the above approach is a higher-order polynomial interpolation problem. We show how “sparse S-decoding polynomials”, a powerful tool from the original constructions of Matching Vector PIRs, can be used to solve this higher-order polynomial interpolation problem using surprisingly few higer-order evaluations.

Using the known sparse S-decoding polynomials in combination with our
ideas leads to our improved PIRs. Notably, we get a 3-server PIR scheme with communication $2^{O^\sim( (\log n)^{1/3}) }$, improving upon the previously best known communication of $2^{O^\sim( \sqrt{\log n})}$ due to Efremenko.



## 2024/1886

* Title: Impossibility Results for Post-Compromise Security in Real-World Communication Systems
* Authors: Cas Cremers, Niklas Medinger, Aurora Naska
* [Permalink](https://eprint.iacr.org/2024/1886)
* [Download](https://eprint.iacr.org/2024/1886.pdf)

### Abstract

Modern secure communication systems, such as iMessage, WhatsApp, and Signal include intricate mechanisms that aim to achieve very strong security properties. These mechanisms typically involve continuously merging in new fresh secrets into the keying material, which is used to encrypt messages during communications. In the literature, these mechanisms have been proven to achieve forms of Post Compromise Security (PCS): the ability to provide communication security even if the full state of a party was compromised some time in the past. However, recent work has shown these proofs do not transfer to the end-user level, possibly because of usability concerns. This has raised the question of whether end-users can actually obtain PCS or not, and under which conditions.

Here we show and formally prove that communication systems that need to be resilient against certain types of state loss (which can occur in practice) fundamentally cannot achieve full PCS for end-users.  Whereas previous work showed that the Signal messenger did not achieve this with its current session-management layer,  we isolate the exact conditions that cause this failure, and why this cannot be simply solved  in communication systems by implementing a different session-management layer or an entirely different protocol. Moreover, we clarify the trade-off of the maximum number of sessions between two users (40 in Signal) in terms of failure-resilience versus security.

Our results have direct consequences for the design of future secure communication systems, and could motivate either the simplification of redundant mechanisms, or the improvement of session-management designs to provide better security trade-offs with respect to state loss/failure tolerance.



## 2024/1887

* Title: Differential MITM attacks on SLIM and LBCIoT
* Authors: Peter Grochal, Martin Stanek
* [Permalink](https://eprint.iacr.org/2024/1887)
* [Download](https://eprint.iacr.org/2024/1887.pdf)

### Abstract

SLIM and LBCIoT are lightweight block ciphers proposed for IoT applications. We present differential meet-in-the-middle attacks on these ciphers and discuss several implementation variants and possible improvements of these attacks.. Experimental validation also shows some results that may be of independent interest in the cryptanalysis of other ciphers. Namely, the problems with low-probability differentials and the questionable accuracy of standard complexity estimates of using filters.



## 2024/1888

* Title: Chosen-Prefix Collisions on AES-like Hashing
* Authors: Shiyao Chen, Xiaoyang Dong, Jian Guo, Tianyu Zhang
* [Permalink](https://eprint.iacr.org/2024/1888)
* [Download](https://eprint.iacr.org/2024/1888.pdf)

### Abstract

Chosen-prefix collision (CPC) attack was first presented by Stevens, Lenstra and de Weger on MD5 at Eurocrypt 2007. A CPC attack finds a collision for any two chosen prefixes, which is a stronger variant of collision attack. CPCs are naturally harder to construct but have larger practical impact than (identical-prefix) collisions, as seen from the series of previous works on MD5 by Stevens et al. and SHA-1 by Leurent and Peyrin. Despite its significance, the resistance of CPC attacks has not been studied on AES-like hashing.
In this work, we explore CPC attacks on AES-like hashing following the framework practiced on MD5 and SHA-1. Instead of the message modification technique developed for MD-SHA family, we opt for related-key rebound attack to construct collisions for AES-like hashing in view of its effectiveness. We also note that the CPC attack framework can be exploited to convert a specific class of one-block free-start collisions into two-block collisions, which sheds light on the importance of free-start collisions. As a result, we present the first CPC attacks on reduced Whirlpool, Saturnin-hash and AES-MMO/MP in classic and quantum settings, and extend the collision attack on Saturnin-hash from 5 to 6 rounds in the classic setting. As an independent contribution, we improve the memoryless algorithm of solving 3-round inbound phase by Hosoyamada and Sasaki at Eurocrpyt 2020, which leads to improved quantum attacks on Whirlpool. Notably, we find the first 6-round memoryless quantum collision attack on Whirlpool better than generic CNS collision finding algorithm when exponential-size qRAM is not available but exponential-size classic memory is available.



## 2024/1889

* Title: IO-Optimized Design-Time Configurable Negacyclic Seven-Step NTT Architecture for FHE Applications
* Authors: Emre Koçer, Selim Kırbıyık, Tolun Tosun, Ersin Alaybeyoğlu, Erkay Savaş
* [Permalink](https://eprint.iacr.org/2024/1889)
* [Download](https://eprint.iacr.org/2024/1889.pdf)

### Abstract

FHE enables computations on encrypted data, making it essential for privacy-preserving applications. However, it involves computationally demanding tasks, such as polynomial multiplication, while NTT is the state-of-the-art solution to perform this task. Most FHE schemes operate over the negacyclic ring of polynomials. We introduce a novel formulation of the hierarchical Four-Step NTT approach for the negacyclic ring, eliminating the need for pre- and post-processing steps found in the existing methods. To accelerate NTT operations, the FPGAs offer flexible and powerful computing platforms. We propose an FPGA-based, parametric and fully pipelined architecture that implements the improved Seven-Step NTT algorithm (which builds upon the four-step). Our design supports a wide range of parameters, including ring sizes up to $2^{16}$ and modulus sizes up to $64$-bit. We focus on achieving configurable throughput, as constrained by the bandwidth of HBM bandwidth, and aim to maximize throughput through an IO parametric design on the Alveo U280 FPGA. The implementation results demonstrate a reduction in the area-time-product by $2.08\times$ and a speed-up of $10.32\times$ for a ring size of $2^{16}$ and a 32-bit width compared to the current state-of-the-art designs.



## 2024/1890

* Title: Efficient Modular Multiplication Hardware for Number Theoretic Transform on FPGA
* Authors: Tolun Tosun, Selim Kırbıyık, Emre Koçer, Erkay Savaş, Ersin Alaybeyoğlu
* [Permalink](https://eprint.iacr.org/2024/1890)
* [Download](https://eprint.iacr.org/2024/1890.pdf)

### Abstract

In this paper, we present a comprehensive analysis of various modular multiplication methods for Number Theoretic Transform (NTT) on FPGA. NTT is a critical and time-intensive component of Fully Homomorphic Encryption (FHE) applications while modular multiplication consumes a significant portion of the design resources in an NTT implementation. We study the existing modular reduction approaches from the literature, and implement particular methods on FPGA. Specifically Word-Level Montgomery (WLM)) for NTT friendly primes [1] and K2RED [2]. For improvements, we explore the trade-offs between the number of available primes in special forms and hardware cost of the reduction methods. We develop a DSP multiplication-optimized version of WLM, which we call WLM-Mixed. We also introduce a subclass of Proth primes, referred to as Proth-l primes, characterized by a low and fixed signed Hamming Weight. This special class of primes allows us to design multiplication-free shift-add versions of K2RED and naive Montgomery reduction [3], referred to as K2RED-Shift and Montgomery-Shift. We provide in-depth evaluations of these five reduction methods in an NTT architecture on FPGA. Our results indicate that WLM-Mixed is highly resource-efficient, utilizing only 3 DSP multiplications for 64-bit coefficient moduli. On the other hand, K2RED-Shift and Montgomery-Shift offer DSP-free alternatives, which can be beneficial in specific scenarios



## 2024/1891

* Title: Shifting our knowledge of MQ-Sign security
* Authors: Lars Ran, Monika Trimoska
* [Permalink](https://eprint.iacr.org/2024/1891)
* [Download](https://eprint.iacr.org/2024/1891.pdf)

### Abstract

Unbalanced Oil and Vinegar (UOV) is one of the oldest, simplest, and most studied ad-hoc multivariate signature schemes. UOV signature schemes are attractive because they have very small signatures and fast verification. On the downside, they have large public and secret keys. As a result, variations of the traditional UOV scheme are usually developed with the goal to reduce the key sizes. Seven variants of UOV were submitted to the additional call for digital signatures by NIST, prior to which, a variant named MQ-Sign was submitted to the (South) Korean post-quantum cryptography competition (KpqC). MQ-Sign is currently competing in the second round of KpqC with two variants. One of the variants corresponds to the classic description of UOV with certain implementation and parameter choices. In the other variant, called MQ-Sign-LR, a part of the central map is constructed from row shifts of a single matrix. This design makes for smaller secret keys, and in the case where the equivalent keys optimization is used, it also leads to smaller public keys. However, we show in this work that the polynomial systems arising from an algebraic attack have a specific structure that can be exploited. Specifically, we are able to find preimages for $d$-periodic targets under the public map with a probability of $63\%$ for all security levels. The complexity of finding these preimages, as well as the fraction of $d$-periodic target increases with $d$ and hence provides a trade-off. We show that for all security levels one can choose $d=\frac{v}{2}$, for $v$ the number of vinegar variables, and reduce the security claim. Our experiments show practical running times for lower $d$ ranging from 0.06 seconds to 32 hours.



## 2024/1892

* Title: A Comprehensive Survey on Hardware-Software co-Protection against Invasive, Non-Invasive and Interactive Security Threats
* Authors: Md Habibur Rahman
* [Permalink](https://eprint.iacr.org/2024/1892)
* [Download](https://eprint.iacr.org/2024/1892.pdf)

### Abstract

In the face of escalating security threats in modern
computing systems, there is an urgent need for comprehensive
defense mechanisms that can effectively mitigate invasive, noninvasive and interactive security vulnerabilities in hardware
and software domains. Individually, hardware and software
weaknesses and probable remedies have been practiced but
protecting a combined system has not yet been discussed in
detail. This survey paper provides a comprehensive overview of
the emerging field of Hardware-Software co-Protection against
Invasive and Non-Invasive Security Threats. We systematically
review state-of-the-art research and developments in hardware
and software security techniques, focusing on their integration to
create synergistic defense mechanisms. The survey covers a wide
range of security threats, including physical attacks, side-channel
attacks, and malware exploits, and explores the diverse strategies
employed to counter them. Our survey meticulously examines the
landscape of security vulnerabilities, encompassing both physical
and software-based attack vectors, and explores the intricate
interplay between hardware and software defenses in mitigating
these threats. Furthermore, we discuss the challenges and opportunities associated with Hardware-Software co-Protection and
identify future research directions to advance the field. Through
this survey, we aim to provide researchers, practitioners, and
policymakers with valuable insights into the latest advancements
and best practices for defending against complex security threats
in modern computing environments.



## 2024/1893

* Title: High Speed High Assurance implementations of Multivariate Quadratic based Signatures
* Authors: Samyuktha M, Pallavi Borkar, Chester Rebeiro
* [Permalink](https://eprint.iacr.org/2024/1893)
* [Download](https://eprint.iacr.org/2024/1893.pdf)

### Abstract

In this poster, we present a Jasmin implementation of Mayo2, a multivariate quadratic(MQ) based signature scheme. Mayo overcomes the disadvantage of the Unbalanced oil and vinegar(UOV) scheme by whipping the UOV map to produce public keys of sizes comparable to ML-DSA. Our Jasmin implementation of Mayo2 takes 930 μs for keygen, 3206 μs for sign, 480 μs for verify based on the average of 1,00,000 runs of the implementation on a 2.25GHz x86 64 processor with 256 GB RAM. To this end, we have a multivariate quadratic based signature implementation that is amenable for verification of constant-time, correctness, proof of equivalence properties using Easycrypt. Subsequently, the results of this endeavor can be extended for other MQ based schemes including UOV.



## 2024/1894

* Title: A non-comparison oblivious sort and its application to private k-NN
* Authors: Sofiane Azogagh, Marc-Olivier Killijian, Félix Larose-Gervais
* [Permalink](https://eprint.iacr.org/2024/1894)
* [Download](https://eprint.iacr.org/2024/1894.pdf)

### Abstract

This paper introduces a novel adaptation of counting sort that enables sorting of encrypted data using Fully Homomorphic Encryption (FHE). Our approach represents the first known sorting algorithm for encrypted data that does not rely on comparisons. The implementation leverages some basic operations on TFHE's Look-Up-Tables (LUT). We have integrated these operations into RevoLUT, a comprehensive open-source library built upon tfhe-rs, which can be of independent interest for oblivious algorithms. We demonstrate the effectiveness of our Blind Counting Sort algorithm by developing a top-$k$ selection algorithm and applying it to privacy-preserving $k$-Nearest Neighbors classification. This proves to be approximately 5x faster than current state-of-the-art methods.



## 2024/1895

* Title: A Tool for Fast and Secure LWE Parameter Selection: the FHE case
* Authors: Beatrice Biasioli, Elena Kirshanova, Chiara Marcolla, Sergi Rovira
* [Permalink](https://eprint.iacr.org/2024/1895)
* [Download](https://eprint.iacr.org/2024/1895.pdf)

### Abstract

The field of fully homomorphic encryption (FHE) has seen many theoretical and computational advances in recent years, bringing the technology closer to practicality than ever before. For this reason, practitioners in related fields, such as machine learning, are increasingly interested in using FHE to provide privacy to their applications.

Despite this progress, selecting secure and efficient parameters for FHE remains a complex and challenging task due to the intricate interdependencies between parameters. In this work, we address this issue by providing a rigorous theoretical foundation for parameter selection for any LWE-based schemes, with a specific focus on FHE. Our approach starts with an in-depth analysis of lattice attacks on the LWE problem, deriving precise expressions for the most effective ones. Building on this, we introduce closed-form formulas that establish the relationships among the LWE parameters.

In addition, we introduce a numerical method to enable the accurate selection of any configurable parameter to meet a desired security level.
Finally, we use our results to build a practical and efficient tool for researchers and practitioners deploying FHE in real-world applications, ensuring that our approach is both rigorous and accessible.



## 2024/1896

* Title: Shardora: Towards Scaling Blockchain Sharding via Unleashing Parallelism
* Authors: Yu Tao, Lu Zhou, Lei Xie, Dongming Zhang, Xinyu Lei, Fei Xu, Zhe Liu
* [Permalink](https://eprint.iacr.org/2024/1896)
* [Download](https://eprint.iacr.org/2024/1896.pdf)

### Abstract

Sharding emerges as a promising solution to enhance blockchain scalability. However, it faces two critical limitations during shard reconfiguration: (1) the TPS-Degradation issue, arising from ledger synchronization conflicts during transaction processing, and (2) the Zero-TPS issue, caused by disruptions in transaction processing due to key negotiation. To this end, we propose Shardora, a blockchain sharding system for scaling blockchain by unleashing parallelism. In Shardora, we implement two essential mechanisms: (1) A parallelized dual committee framework with a reputation mechanism to mitigate the TPS-Degradation issue while ensuring system security. (2) A parallelized key pre-negotiation mechanism with a secret-reuse strategy to avoid the Zero-TPS issue while maintaining a continuously high TPS. We prove that Shardora offers theory-guaranteed security. We implement a prototype of Shardora and deploy it on Alibaba Cloud. Experimental results demonstrate that Shardora addresses the limitations by significantly reducing the overhead of both ledger synchronization and key negotiation, which outperforms state-of-the-art sharding schemes by at least 90%. In addition, Shardora shows its superior performance in terms of throughput and latency, achieving a peak throughput of 8300 TPS on a single shard with 600 nodes under LAN conditions. The code of Shardora is publicly available on GitHub.



## 2024/1897

* Title: On Threshold Signatures from MPC-in-the-Head
* Authors: Eliana Carozza, Geoffroy Couteau
* [Permalink](https://eprint.iacr.org/2024/1897)
* [Download](https://eprint.iacr.org/2024/1897.pdf)

### Abstract

We investigate the feasibility of constructing threshold signature schemes from the MPC-in-the-head paradigm. Our work addresses the significant challenge posed by recent impossibility results (Doerner et al., Crypto’24), which establish inherent barriers to efficient thresholdization of such schemes without compromising their security or significantly increasing the signature size.
- We introduce a general methodology to adapt any MPC-in-the-head signature into a threshold-friendly scheme, ensuring that the dependency on the number of users $n$ grows as $\lambda^2n + O(1)$. This represents a substantial improvement over the naive concatenation of independent signatures.
- We present a threshold signature scheme on top of the scheme of (Carozza, Couteau and Joux, EUROCRYPT’23). Our security analysis introduces the notion of Corruptible Existential Unforgeability under Chosen Message Attacks (CEUF-CMA), which formalizes resilience against adversarial control over parts of the randomness.
Our results provide a new perspective on the trade-offs between efficiency and security in threshold settings, opening pathways for future improvements in post-quantum threshold cryptography.



## 2024/1898

* Title: NTRU-based Bootstrapping for MK-FHEs without using Overstretched Parameters
* Authors: Binwu Xiang, Jiang Zhang, Kaixing Wang, Yi Deng, Dengguo Feng
* [Permalink](https://eprint.iacr.org/2024/1898)
* [Download](https://eprint.iacr.org/2024/1898.pdf)

### Abstract

Recent attacks on NTRU lattices given by Ducas and van Woerden (ASIACRYPT 2021) showed that for moduli $q$ larger than the so-called fatigue point $n^{2.484+o(1)}$,  the security of NTRU is noticeably less than that of (ring)-LWE. Unlike
NTRU-based PKE with $q$ typically lying in the secure regime of NTRU lattices (i.e., $q<n^{2.484+o(1)}$),  the security of existing NTRU-based multi-key FHEs (MK-FHEs) requiring $q=O(n^k)$ for $k$ keys could be significantly affected by those attacks.

In this paper, we first propose a (matrix) NTRU-based MK-FHE
for super-constant number $k$ of keys without using overstretched NTRU parameters. Our scheme is essentially a combination of two components following the two-layer framework of TFHE/FHEW:
- a simple first-layer matrix NTRU-based encryption that naturally supports multi-key NAND operations
with moduli $q=O(k\cdot n^{1.5})$ only linear in the number $k$ of keys;
-and a crucial second-layer NTRU-based encryption that supports an efficient hybrid product between a single-key ciphertext and a multi-key ciphertext for gate bootstrapping.

Then, by replacing the first-layer with a more efficient LWE-based multi-key encryption, we obtain an improved MK-FHE scheme with better performance. We also employ a light key-switching technique to reduce the key-switching key size from the previous $O(n^2)$ bits to $O(n)$ bits.
 
A proof-of-concept implementation shows that our two MK-FHE schemes outperform the state-of-the-art TFHE-like MK-FHE schemes in both computation efficiency and bootstrapping key size. Concretely, for $k=8$ at the same 100-bit security level, our improved MK-FHE scheme can bootstrap a ciphertext in {0.54s} on a laptop and only has a bootstrapping key of size {13.89}MB,which are respectively 2.2 times faster and 7.4 times smaller than the MK-FHE scheme  (which relies on a second-layer encryption from the ring-LWE assumption) due to Chen, Chillotti and Song (ASIACRYPT 2019).



## 2024/1899

* Title: Fast Multiplication and the PLWE-RLWE Equivalence for an Infinite Family of Cyclotomic Subextensions
* Authors: Joonas Ahola, Iván Blanco-Chacón, Wilmar Bolaños, Antti Haavikko, Camilla Hollanti, Rodrigo M. Sánchez-Ledesma
* [Permalink](https://eprint.iacr.org/2024/1899)
* [Download](https://eprint.iacr.org/2024/1899.pdf)

### Abstract

We prove the equivalence between the Ring Learning With Errors (RLWE) and the Polynomial Learning With Errors (PLWE) problems for the maximal totally real subfield of the $2^r 3^s$-th cyclotomic field for $r \geq 3$ and $s \geq 1$. Moreover, we describe a fast algorithm for computing the product of two elements in the ring of integers of these subfields. This multiplication algorithm has quasilinear complexity in the dimension of the field, as it makes use of the fast Discrete Cosine Transform (DCT). Our approach assumes that the two input polynomials are given in a basis of Chebyshev-like polynomials, in contrast to the customary power basis. To validate this assumption, we prove that the change of basis from the power basis to the Chebyshev-like basis can be computed with $\mathcal{O}(n \log n)$ arithmetic operations, where $n$ is the problem dimension. Finally, we provide a heuristic and theoretical comparison of the vulnerability to some attacks for the $p$-th cyclotomic field versus the maximal totally real subextension of the $4p$-th cyclotomic field for a reasonable set of parameters of cryptographic size.



## 2024/1900

* Title: Opening the Blackbox: Collision Attacks on Round-Reduced Tip5, Tip4, Tip4' and Monolith
* Authors: Fukang Liu, Katharina Koschatko, Lorenzo Grassi, Hailun Yan, Shiyao Chen, Subhadeep Banik, Willi Meier
* [Permalink](https://eprint.iacr.org/2024/1900)
* [Download](https://eprint.iacr.org/2024/1900.pdf)

### Abstract

A new design strategy for ZK-friendly hash functions has emerged since the proposal of $\mathsf{Reinforced Concrete}$ at CCS 2022, which is based on the hybrid use of two types of nonlinear transforms: the composition of some small-scale lookup tables (e.g., 7-bit or 8-bit permutations) and simple power maps over $\mathbb{F}_p$. Following such a design strategy, some new ZK-friendly hash functions have been recently proposed, e.g., $\mathsf{Tip5}$, $\mathsf{Tip4}$, $\mathsf{Tip4}'$ and the $\mathsf{Monolith}$ family. All these hash functions have a small number of rounds, i.e., $5$ rounds for $\mathsf{Tip5}$, $\mathsf{Tip4}$, and $\mathsf{Tip4}'$, and $6$ rounds for $\mathsf{Monolith}$ (recently published at ToSC 2024/3). Using the composition of some small-scale lookup tables to build a large-scale permutation over $\mathbb{F}_p$ - which we call S-box - is a main feature in such designs, which can somehow enhance the resistance against the Gröbner basis attack because this large-scale permutation will correspond to a complex and high-degree polynomial representation over $\mathbb{F}_p$.
   
As the first technical contribution, we propose a novel and efficient algorithm to study the differential property of this S-box and to find a conforming input pair for a randomly given input and output difference. For comparison, a trivial method based on the use of the differential distribution table (DDT) for solving this problem will require time complexity $\mathcal{O}(p^2)$.
   
For the second contribution, we also propose new frameworks to devise efficient collision attacks on such hash functions. Based on the differential properties of these S-boxes and the new attack frameworks, we propose the first collision attacks on $3$-round $\mathsf{Tip5}$, $\mathsf{Tip4}$, and $\mathsf{Tip4}'$, as well as $2$-round $\mathsf{Monolith}$-$31$ and $\mathsf{Monolith}$-$64$, where the $2$-round attacks on $\mathsf{Monolith}$ are practical. In the semi-free-start (SFS) collision attack setting, we achieve practical SFS collision attacks on $3$-round $\mathsf{Tip5}$, $\mathsf{Tip4}$, and $\mathsf{Tip4}'$. Moreover, the SFS collision attacks can reach up to $4$-round $\mathsf{Tip4}$ and $3$-round $\mathsf{Monolith}$-$64$. As far as we know, this is the first third-party cryptanalysis of these hash functions, which improves the initial analysis given by the designers.



## 2024/1901

* Title: On the Insecurity of Bloom Filter-Based Private Set Intersections
* Authors: Jelle Vos, Jorrit van Assen, Tjitske Koster, Evangelia Anna Markatou, Zekeriya Erkin
* [Permalink](https://eprint.iacr.org/2024/1901)
* [Download](https://eprint.iacr.org/2024/1901.pdf)

### Abstract

Private set intersections are cryptographic protocols that compute the intersection of multiple parties' private sets without revealing elements that are not in the intersection. These protocols become less efficient when the number of parties grows, or the size of the sets increases. For this reason, many protocols are based on Bloom filters, which speed up the protocol by approximating the intersections, introducing false positives with a small but non-negligible probability. These false positives are caused by hash collisions in the hash functions that parties use to encode their sets as Bloom filters. In this work, we show that these false positives are more than an inaccuracy: an adversary in the augmented semi-honest model can use them to learn information about elements that are not in the intersection. First, we show that existing security proofs for Bloom filter-based private set intersections are flawed. Second, we show that even in the most optimistic setting, Bloom filter-based private set intersections cannot securely realize an approximate private set intersection unless the parameters are so large that false positives only occur with negligible probability. Third, we propose a practical attack that allows a party to learn if an element is contained in a victim's private set, showing that the problem with Bloom filters is not just theoretical. We conclude that the efficiency gain of using Bloom filters as an approximation in existing protocols vanishes when accounting for this security problem. We propose three mitigations besides choosing larger parameters: One can use oblivious pseudo-random functions instead of hash functions to reduce the success rate of our attack significantly, or replace them with password-based key derivation functions to significantly slow down attackers. A third option is to let a third party authorize the input sets before proceeding with the protocol.



## 2024/1902

* Title: ZK-SNARKs for Ballot Validity: A Feasibility Study
* Authors: Nicolas Huber, Ralf Kuesters, Julian Liedtke, Daniel Rausch
* [Permalink](https://eprint.iacr.org/2024/1902)
* [Download](https://eprint.iacr.org/2024/1902.pdf)

### Abstract

Electronic voting (e-voting) systems have become more prevalent in recent years, but security concerns have also increased, especially regarding the privacy and verifiability of votes. As an essential ingredient for constructing secure e-voting systems, designers often employ zero-knowledge proofs (ZKPs), allowing voters to prove their votes are valid without revealing them. Invalid votes can then be discarded to protect verifiability without compromising the privacy of valid votes.

General purpose zero-knowledge proofs (GPZKPs) such as ZK-SNARKs can be used to prove arbitrary statements, including ballot validity. While a specialized ZKP that is constructed only for a specific election type/voting method, ballot format, and encryption/commitment scheme can be more efficient than a GPZKP, the flexibility offered by GPZKPs would allow for quickly constructing e-voting systems for new voting methods and new ballot formats. So far, however, the viability of GPZKPs for showing ballot validity for various ballot formats, in particular, whether and in how far they are practical for voters to compute, has only recently been investigated for ballots that are computed as Pedersen vector commitments in an ACM CCS 2022 paper by Huber et al.

Here, we continue this line of research by performing a feasibility study of GPZKPs for the more common case of ballots encrypted via Exponential ElGamal encryption. Specifically, building on the work by Huber et al., we describe how the Groth16 ZK-SNARK can be instantiated to show ballot validity for arbitrary election types and ballot formats encrypted via Exponential ElGamal. As our main contribution, we implement, benchmark, and compare several such instances for a wide range of voting methods and ballot formats. Our benchmarks not only establish a basis for protocol designers to make an educated choice for or against such a GPZKP, but also show that GPZKPs are actually viable for showing ballot validity in voting systems using Exponential ElGamal.



## 2024/1903

* Title: Trustworthy Approaches to RSA: Efficient Exploitation Strategies Based on Common Modulus
* Authors: Mahdi Mahdavi, Navid Abapour, Zahra Ahmadian
* [Permalink](https://eprint.iacr.org/2024/1903)
* [Download](https://eprint.iacr.org/2024/1903.pdf)

### Abstract

With the increasing integration of crowd computing, new vulnerabilities emerge in widely used cryptographic systems like the RSA cryptosystem, whose security is based on the factoring problem. It is strongly advised to avoid using the same modulus to produce two pairs of public-private keys, as the cryptosystem would be rendered vulnerable to common modulus attacks. Such attacks can take two forms: one that aims to factorize the common modulus based on one key pair and the other that aims to decrypt certain ciphertexts generated by two public keys if the keys are co-prime. This paper introduces a new type of common modulus attack on the RSA cryptosystem. In our proposed attack, given one public-private key pair, an attacker can obtain the private key corresponding to a given public key in RSA decryption. This allows the adversary to decrypt any ciphertext generated using this public key. It is worth noting that the proposed attack can be used in the CRT model of RSA. In addition, we propose a parallelizable factoring algorithm with an order equivalent to a cyclic attack in the worst-case scenario.



## 2024/1904

* Title: An Open Source Ecosystem for Implementation Security Testing
* Authors: Aydin Aysu, Fatemeh Ganji, Trey Marcantonio, Patrick Schaumont
* [Permalink](https://eprint.iacr.org/2024/1904)
* [Download](https://eprint.iacr.org/2024/1904.pdf)

### Abstract

Implementation-security vulnerabilities such as the
power-based side-channel leakage and fault-injection sensitivity
of a secure chip are hard to verify because of the sophistication
of the measurement setup, as well as the need to generalize the
adversary into a test procedure. While the literature has proposed
a wide range of vulnerability metrics to test the correctness of a
secure implementation, it is still up to the subject-matter expert to
map these concepts into a working and reliable test procedure.
Recently, we investigated the benefits of using an open-source
implementation security testing environment called Chipwhisperer.
The open-source and low-cost nature of the Chipwhisperer
hardware and software has resulted in the adoption of thousands
of testing kits throughout academia and industry, turning the
testkit into a baseline for implementation security testing. We
investigate the use cases for the Chipwhisperer hardware and
software, and we evaluate the feasibility of an open-source
ecosystem for implementation security testing. In addition to the
open-source hardware and firmware, an ecosystem also considers
broader community benefits such as re-usability, sustainability,
and governance.



## 2024/1905

* Title: OPL4GPT: An Application Space Exploration of Optimal Programming Language for Hardware Design by LLM
* Authors: Kimia Tasnia, Sazadur Rahman
* [Permalink](https://eprint.iacr.org/2024/1905)
* [Download](https://eprint.iacr.org/2024/1905.pdf)

### Abstract

Despite the emergence of Large Language Models (LLMs) as potential tools for automating hardware design, the optimal programming language to describe hardware functions remains unknown. Prior works extensively explored optimizing Verilog-based HDL design, which often overlooked the potential capabilities of alternative programming languages for hardware designs. This paper investigates the efficacy of C++ and Verilog as input languages in extensive application space exploration, tasking an LLM to generate implementations for various System-on-chip functional blocks. We proposed an automated Optimal Programming Language (OPL) framework that leverages OpenAI's GPT-4o LLM to translate natural language specifications into hardware descriptions using both high-level and low-level programming paradigms. The OPL4GPT demonstration initially employs a novel prompt engineering approach that decomposes design specifications into manageable submodules, presented to the LLM to generate code in both C++ and Verilog. A closed-loop feedback mechanism automatically incorporates error logs from the LLM's outputs, encompassing both syntax and functionality.. Finally, functionally correct outputs are synthesized using either RTL (Register-Transfer Level) for Verilog or High-Level Synthesis for C++ to assess area, power, and performance. Our findings illuminate the strengths and weaknesses of each language across various application domains, empowering hardware designers to select the most effective approach.



## 2024/1906

* Title: On Efficient Computations of Koblitz Curves over Prime Fields
* Authors: Guangwu Xu, Ke Han, Yunxiao Tian
* [Permalink](https://eprint.iacr.org/2024/1906)
* [Download](https://eprint.iacr.org/2024/1906.pdf)

### Abstract

The family of Koblitz curves $E_b: y^2=x^3+b/\mathbb{F}_p$ over primes fields has close connections to the ring $\mathbb{Z}[\omega]$ of Eisenstein integers. Utilizing nice facts from the theory of cubic residues,  this paper derives an efficient formula for a (complex) scalar multiplication by $\tau=1-\omega$. This enables us to develop a window $\tau$-NAF method for Koblitz curves over prime fields. This probably is the first window $\tau$-NAF method to be designed for curves over fields with  large characteristic. Besides its theoretical interest, a higher performance is also achieved due to the facts that (1) the operation $\tau^2$ can be done more efficiently that makes  the average cost of $\tau$ to be close to $2.5\mathbf{S}+3\mathbf{M}$ ( $\mathbf{S}$ and $\mathbf{M}$ denote the costs for field squaring and multiplication, respectively); (2) the pre-computation for the  window $\tau$-NAF method is surprisingly simple in that only one-third of the coefficients need to be processed.  The overall improvement over the best current method  is more than $11\%$. The paper also suggests a simplified modular reduction for  Eisenstein integers where the division operations are  eliminated. The efficient formula of $\tau P$ can be further used to speed up the computation of  $3P$,  compared to $10\mathbf{S}+5\mathbf{M}$ , our new formula just costs $4\mathbf{S}+6\mathbf{M}$. As a main ingredient for double base chain method for scalar multiplication, the $3P$ formula will contribute to a greater efficiency.



## 2024/1907

* Title: Towards Optimal Garbled Circuits in the Standard Model
* Authors: Ruiyang Li, Chun Guo, Xiao Wang
* [Permalink](https://eprint.iacr.org/2024/1907)
* [Download](https://eprint.iacr.org/2024/1907.pdf)

### Abstract

State-of-the-art garbling schemes for boolean circuits roughly consist of two families, i.e., ideal model garbling that combines linear operations and ideal blockciphers (aiming at maximizing performance), and PRF-based garbling that insists on using theoretically sound assumptions. In the linear garbling framework introduced by Zahur, Rosulek, and Evans (Eurocrypt 2015), it was established that garbling an AND gate requires at least $2(\kappa +1)$ bits of ciphertext, with $\kappa$ as the security parameter. Recent contributions from Lei Fan et al. and Chunghun Baek et al. have provided a detailed model showing that, under the free-XOR setting, which relies on a non-standard assumption, garbling an AND gate requires at least $1.5\kappa + O(1)$ bits. In contrast, regarding PRF-based garbling, the general model and efficiency bounds remain open questions.

In this paper, we present a comprehensive model for PRF-based garbled circuits and establish both the communication and computation lower bound. Specifically, we demonstrate that garbling an AND gate requires at least $2\kappa + 2$ bits communication and 6 PRF calls, while an XOR gate requires a minimum of $\kappa$ bits communication and 4 PRF calls. Notably, the state-of-the-art garbling scheme (GLNP scheme) under the PRF assumption, introduced by Shay, Yehuda, Ariel, and Benny (JOC 2018), uses $2\kappa + 4$ bits and 8 PRF calls for an AND gate, which exceeds our established lower bound. We finally introduce an optimal garbling scheme showing that our communication and computation lower bounds are tight.



## 2024/1908

* Title: Generalized Impossible Differential Attacks on Block Ciphers: Application to SKINNY and ForkSKINNY
* Authors: Ling Song, Qinggan Fu, Qianqian Yang, Yin Lv, Lei Hu
* [Permalink](https://eprint.iacr.org/2024/1908)
* [Download](https://eprint.iacr.org/2024/1908.pdf)

### Abstract

Impossible differential cryptanalysis is a crucial cryptanalytical method for symmetric ciphers. Given an impossible differential, the key recovery attack typically proceeds in two steps: generating pairs of data and then identifying wrong keys using the guess-and-filtering method. At CRYPTO 2023, Boura \etal first proposed a new key recovery technique - the differential meet-in-the-middle attack, which recovers the key in a meet-in-the-middle manner. Inspired by this technique, we incorporate the meet-in-the-middle technique into impossible cryptanalysis and propose a generic impossible differential meet-in-the-middle attack (\idma) framework. We apply \idma to block ciphers \skinny, \skinnye-v2, and \forkskinny and achieve remarkably efficient attacks. We improve the impossible differential attack on \skinny-$n$-$3n$ by 2 rounds in the single-tweakey setting and 1 round in the related-tweakey setting. For \skinnye-v2, the impossible differential attacks now can cover 2 more rounds in the related-tweakey setting and the first 23/24/25-round attacks in the single-tweakey model are given. For \forkskinny-$n$-$3n$, we improve the attacks by 2 rounds in the limited setting specified by the designers and 1 round in relaxed settings.
These results confirm that the meet-in-the-middle technique can result in more efficient key recovery, reaching beyond what traditional methods can achieve on certain ciphers.



## 2024/1909

* Title: NewtonPIR: Communication Efficient Single-Server PIR
* Authors: Pengfei Lu, Hongyuan Qu
* [Permalink](https://eprint.iacr.org/2024/1909)
* [Download](https://eprint.iacr.org/2024/1909.pdf)

### Abstract

Private information retrieval (PIR) is a key component of many privacy-preserving systems. Although numerous PIR protocols have been proposed, designing a PIR scheme with communication overhead independent of the database size $N$ and computational cost practical for real-world applications remains a challenge. In this paper, we propose the NewtonPIR protocol, a communication efficient single-server PIR scheme. NewtonPIR can directly generate query values for the entire index without splitting the index and sending multiple query ciphertexts. Specifically, NewtonPIR achieves communication overhead that is 7.5$\times$ better than the state-of-the-art PIR protocol and 35.9$\sim$75$\times$ better than the other protocols. In experiments, when the database size and entry size increase, the communication overhead of NewtonPIR remains stable.. By utilizing the single-ciphertext fully homomorphic encryption (FHE) scheme and the simple Newton interpolation polynomial, along with precomputing coefficients in the offline phase, we reduce the computational overhead of NewtonPIR from hours in previous schemes to seconds. To the best of our knowledge, NewtonPIR is the first protocol to achieve communication cost independent of $N$ along with computational overhead comparable to ring learning with errors (RLWE)-based PIR schemes. Additionally, we extend and introduce a private set intersection (PSI) protocol that balances computational and communication overhead more effectively.



## 2024/1910

* Title: Stealth Software Trojan: Amplifying Hidden RF Side-Channels with Ultra High SNR and Data-Rate
* Authors: Gal Cohen, Itamar Levy
* [Permalink](https://eprint.iacr.org/2024/1910)
* [Download](https://eprint.iacr.org/2024/1910.pdf)

### Abstract

Interconnected devices enhance daily life but introduce security
vulnerabilities, new technologies enable malicious activities
such as information theft. This article combines radio frequency (RF) side-channel attacks with software Trojans to create a hard-to-detect, stealthy method for extracting kilobytes of secret information per millisecond over record distances with a single measurement in the RF spectrum. The technique exploits Trojan-induced electrical disturbances in RF components originating from peripherals, buses, memories and CPUs to achieve high SNR data leakage schemes.. Experimental results show negligible acquisition time and stealth. The research introduces optimized modulation, demodulation schemes, and specialized synchronization symbols to minimize error rates and maximize data rates. It highlights the need for advanced detection and defense mechanisms to ensure the security and privacy of interconnected devices.



## 2024/1911

* Title: Deletions and Dishonesty: Probabilistic Data Structures in Adversarial Settings
* Authors: Mia Filić, Keran Kocher, Ella Kummer, Anupama Unnikrishnan
* [Permalink](https://eprint.iacr.org/2024/1911)
* [Download](https://eprint.iacr.org/2024/1911.pdf)

### Abstract

Probabilistic data structures (PDS) are compact representations of high-volume data that provide approximate answers to queries about the data. They are commonplace in today's computing systems, finding use in databases, networking and more. While PDS are designed to perform well under benign inputs, they are frequently used in applications where inputs may be adversarially chosen. This may lead to a violation of their expected behaviour, for example an increase in false positive rate.

In this work, we focus on PDS that handle approximate membership queries (AMQ). We consider adversarial users with the capability of making adaptive insertions, deletions and membership queries to AMQ-PDS, and analyse the performance of AMQ-PDS under such adversarial inputs.

We argue that deletions significantly empower adversaries, presenting a challenge to enforcing honest behaviour when compared to insertion-only AMQ-PDS. To address this, we introduce a new concept of an honest setting for AMQ-PDS with deletions. By leveraging simulation-based security definitions, we then quantify how much harm can be caused by adversarial users to the functionality of AMQ-PDS. Our resulting bounds only require calculating the maximal false positive probability and insertion failure probability achievable in our novel honest setting.

We apply our results to Cuckoo filters and Counting filters. We show how to protect these AMQ-PDS at low cost, by replacing or composing the hash functions with keyed pseudorandom functions in their construction. This strategy involves establishing practical bounds for the probabilities mentioned above. Using our new techniques, we demonstrate that achieving security against adversarial users making both insertions and deletions remains practical.