[digest] 2024 Week 50

## In this issue

1. [2024/750] Speeding Up Multi-Scalar Multiplications for ...
2. [2024/1587] Fully Homomorphic Encryption for Cyclotomic Prime ...
3. [2024/1974] Efficient and Practical Multi-party Private Set ...
4. [2024/1975] Quadratic Modelings of Syndrome Decoding
5. [2024/1976] HI-CKKS: Is High-Throughput Neglected? Reimagining ...
6. [2024/1977] Bounded CCA Secure Proxy Re-encryption Based on Kyber
7. [2024/1978] µLAM: A LLM-Powered Assistant for Real-Time Micro- ...
8. [2024/1979] On the Security of LWE-based KEMs under Various ...
9. [2024/1980] Sonikku: Gotta Speed, Keed! A Family of Fast and ...
10. [2024/1981] Shutter Network: Private Transactions from ...
11. [2024/1982] New Results in Quantum Analysis of LED: Featuring ...
12. [2024/1983] UTRA: Universe Token Reusability Attack and ...
13. [2024/1984] Low Communication Threshold Fully Homomorphic ...
14. [2024/1985] Endomorphisms for Faster Cryptography on Elliptic ...
15. [2024/1986] Improved Quantum Analysis of ARIA
16. [2024/1987] Side-Channel Attack on ARADI
17. [2024/1988] Garbled Circuits with 1 Bit per Gate
18. [2024/1989] Revisiting OKVS-based OPRF and PSI: Cryptanalysis ...
19. [2024/1990] How To Scale Multi-Party Computation
20. [2024/1991] CHLOE: Loop Transformation over Fully Homomorphic ...
21. [2024/1992] Improved Quantum Linear Attacks and Application to CAST
22. [2024/1993] BOIL: Proof-Carrying Data from Accumulation of ...
23. [2024/1994] Token-Based Key Exchange - Non-Interactive Key ...
24. [2024/1995] BitVM: Quasi-Turing Complete Computation on Bitcoin
25. [2024/1996] A Framework for Generating S-Box Circuits with ...
26. [2024/1997] On format preserving encryption with nonce
27. [2024/1998] Impossible Differential Automation: Model ...
28. [2024/1999] Multivariate Encryptions with LL’ perturbations - ...
29. [2024/2000] Evasive LWE Assumptions: Definitions, Classes, and ...
30. [2024/2001] Xiezhi: Toward Succinct Proofs of Solvency
31. [2024/2002] Improving Differential-Neural Distinguisher For ...
32. [2024/2003] Exploring the Optimal Differential Characteristics ...
33. [2024/2004] Regev's attack on hyperelliptic cryptosystems
34. [2024/2005] Post-Quantum Secure Channel Protocols for eSIMs
35. [2024/2006] Data Decryption and Analysis of Note-Taking ...
36. [2024/2007] A Combinatorial Attack on Ternary Sparse Learning ...
37. [2024/2008] PrivCirNet: Efficient Private Inference via Block ...
38. [2024/2009] The Mis/Dis-information Problem is Hard to Solve
39. [2024/2010] Anonymous credentials from ECDSA
40. [2024/2011] Honest-Majority Threshold ECDSA with Batch ...
41. [2024/2012] GraSS: Graph-based Similarity Search on Encrypted Query
42. [2024/2013] Crescent: Stronger Privacy for Existing Credentials
43. [2024/2014] On the Traceability of Group Signatures: ...
44. [2024/2015] Universal SNARGs for NP from Proofs of Correctness
45. [2024/2016] The Existence of Quantum One-Way Functions
46. [2024/2017] Byzantine Consensus in Wireless Networks
47. [2024/2018] On the BUFF Security of ECDSA with Key Recovery
48. [2024/2019] Key-Insulated and Privacy-Preserving Signature ...
49. [2024/2020] Ring Ring! Who's There? A Privacy Preserving Mobile ...
50. [2024/2021] PrivQuant: Communication-Efficient Private ...
51. [2024/2022] The Revisited Hidden Weight Bit Function
52. [2024/2023] An Abstract Multi-Forking Lemma
53. [2024/2024] Hash-Prune-Invert: Improved Differentially Private ...
54. [2024/2025] Mira: Efficient Folding for Pairing-based Arguments
55. [2024/2026] Orbweaver: Succinct Linear Functional Commitments ...
56. [2024/2027] Impact Tracing: Identifying the Culprit of ...
57. [2024/2028] Qubit Optimized Quantum Implementation of SLIM
58. [2024/2029] NLAT: the NonLinear Distribution Table of Vectorial ...
59. [2024/2030] Security Analysis of ASCON Cipher under Persistent ...

## 2024/750

* Title: Speeding Up Multi-Scalar Multiplications for Pairing-Based zkSNARKs
* Authors: Xinxin Fan, Veronika Kuchta, Francesco Sica, Lei Xu
* [Permalink](https://eprint.iacr.org/2024/750)
* [Download](https://eprint.iacr.org/2024/750.pdf)

### Abstract

Multi-scalar multiplication (MSM) is one of the core components of many zero-knowledge proof systems, and a primary performance bottleneck for proof generation in these schemes.  One major strategy to accelerate MSM is utilizing precomputation.  Several algorithms (e.g., Pippenger and BGMW) and their variants have been proposed in this direction. In this paper, we revisit the recent precomputation-based MSM calculation method proposed by Luo, Fu and Gong at CHES 2023 and generalize their approach. In particular, we presented a general construction of optimal buckets. This improvement leads to significant performance improvements, which are verified by both theoretical analysis and experiments.



## 2024/1587

* Title: Fully Homomorphic Encryption for Cyclotomic Prime Moduli
* Authors: Robin Geelen, Frederik Vercauteren
* [Permalink](https://eprint.iacr.org/2024/1587)
* [Download](https://eprint.iacr.org/2024/1587.pdf)

### Abstract

This paper presents a Generalized BFV (GBFV) fully homomorphic encryption scheme that encrypts plaintext spaces of the form $\mathbb{Z}[x]/(\Phi_m(x), t(x))$ with $\Phi_m(x)$ the $m$-th cyclotomic polynomial and $t(x)$ an arbitrary polynomial.  GBFV encompasses both BFV where $t(x) = p$ is a constant, and the CLPX scheme (CT-RSA 2018) where $m = 2^k$ and $t(x) = x-b$ is a linear polynomial. The latter can encrypt a single huge integer modulo $\Phi_m(b)$, has much lower noise growth than BFV (linear in $m$ instead of exponential), but cannot be bootstrapped.

We show that by a clever choice of $m$ and higher degree polynomial $t(x)$, our scheme combines the SIMD capabilities of BFV with the low noise growth of CLPX, whilst still being efficiently bootstrappable. Moreover, we present parameter families that natively accommodate packed plaintext spaces defined by a large cyclotomic prime, such as the Fermat prime $\Phi_2(2^{16}) = 2^{16} + 1$ and the Goldilocks prime $\Phi_6(2^{32}) = 2^{64} - 2^{32} + 1$.  These primes are often used in homomorphic encryption applications and zero-knowledge proof systems.

Due to the lower noise growth, e.g. for the Goldilocks prime, GBFV can evaluate circuits whose multiplicative depth is more than $5$ times larger than native BFV.  As a result, we can evaluate either larger circuits or work with much smaller ring dimensions. In particular, we can natively bootstrap GBFV at 128-bit security for a large prime, already at ring dimension $2^{14}$, which was impossible before.  We implemented the GBFV scheme on top of the SEAL library and achieve a latency of only $2$ seconds to bootstrap a ciphertext encrypting up to $8192$ elements modulo $2^{16}+1$.



## 2024/1974

* Title: Efficient and Practical Multi-party Private Set Intersection Cardinality Protocol
* Authors: Shengzhe Meng, Xiaodong Wang, Zijie Lu, Bei Liang
* [Permalink](https://eprint.iacr.org/2024/1974)
* [Download](https://eprint.iacr.org/2024/1974.pdf)

### Abstract

We present an efficient and simple multi-party private set intersection cardinality (PSI-CA) protocol that allows several parties to learn the intersection size of their private sets without revealing any other information. Our protocol is highly efficient because it only utilizes the Oblivious Key-Value Store and zero-sharing techniques, without incorporating components such as OPPRF (Oblivious Programmable Pseudorandom Function) which is the main building block of multi-party PSI-CA protocol by Gao et al. (PoPETs 2024). Our protocol exhibits better communication and computational overhead than the state-of-the-art.

To compute the intersection between 16 parties with a set size of $2^{20}$ each, our PSI-CA protocol only takes 5.84 seconds and 326.6 MiB of total communication, which yields a reduction in communication by a factor of up to 2.4× compared to the state-of-the-art multi-party PSI-CA protocol of Gao et al. (PoPETs 2024).
We prove that our protocol is secure in the presence of a semi-honest adversary who may passively corrupt any $(t-2)$-out-of-$t$ parties once two specific participants are non-colluding.



## 2024/1975

* Title: Quadratic Modelings of Syndrome Decoding
* Authors: Alessio Caminata, Ryann Cartor, Alessio Meneghetti, Rocco Mora, Alex Pellegrini
* [Permalink](https://eprint.iacr.org/2024/1975)
* [Download](https://eprint.iacr.org/2024/1975.pdf)

### Abstract

This paper presents enhanced reductions of the bounded-weight and exact-weight Syndrome Decoding Problem (SDP) to a system of quadratic equations. Over $\mathbb{F}_2$, we improve on a previous work and study the degree of regularity of the modeling of the exact weight SDP.  Additionally, we introduce a novel technique that transforms SDP instances over $\mathbb{F}_q$ into systems of polynomial equations and thoroughly investigate the dimension of their varieties. Experimental results are provided to evaluate the complexity of solving SDP instances using our models through Gröbner bases techniques.



## 2024/1976

* Title: HI-CKKS: Is High-Throughput Neglected? Reimagining CKKS Efficiency with Parallelism
* Authors: Fuyuan Chen, Jiankuo Dong, Xiaoyu Hu, Zhenjiang Dong, Wangchen Dai, Jingqiang Lin, Fu Xiao
* [Permalink](https://eprint.iacr.org/2024/1976)
* [Download](https://eprint.iacr.org/2024/1976.pdf)

### Abstract

The proliferation of data outsourcing and cloud services has heightened privacy vulnerabilities. CKKS, among the most prominent homomorphic encryption schemes, allows computations on encrypted data, serving as a critical privacy safeguard. However, performance remains a central bottleneck, hindering widespread adoption. Existing optimization efforts often prioritize latency reduction over throughput performance. This paper presents HI-CKKS, a throughput-oriented High-performance Implementation of CKKS homomorphic encryption, addressing these challenges. Our HI-CKKS introduces a batch-supporting asynchronous execution scheme, effectively mitigating frequent data interactions and high waiting delays between hosts and servers in service-oriented scenarios. We analyze the fundamental (I)NTT primitive, which is critical in CKKS, and develop a hierarchical, hybrid high-throughput implementation. This includes efficient arithmetic module instruction set implementations, unified kernel fusion, and hybrid memory optimization strategies that significantly improve memory access efficiency and the performance of (I)NTT operations. Additionally, we propose a multi-dimensional parallel homomorphic multiplication scheme aimed at maximizing throughput and enhancing the performance of (I)NTT and homomorphic multiplication. In conclusion, our implementation is deployed on the RTX 4090, where we conduct a thorough throughput performance evaluation of HI-CKKS, enabling us to pinpoint the most effective parallel parameter settings. Compared to the CPU implementation, our system achieves throughput increases of $175.08\times$, $191.27\times$, and $679.57\times$ for NTT, INTT, and HMult, respectively. And our throughput performance still demonstrates a significant improvement, ranging from $1.54\times$ to $693.17\times$ compared to the latest GPU-based works.



## 2024/1977

* Title: Bounded CCA Secure Proxy Re-encryption Based on Kyber
* Authors: Shingo Sato, Junji Shikata
* [Permalink](https://eprint.iacr.org/2024/1977)
* [Download](https://eprint.iacr.org/2024/1977.pdf)

### Abstract

Proxy re-encryption (PRE) allows semi-honest party (called proxy) to convert a ciphertext under a public key into a ciphertext under another public key. Due to this functionality, there are various applications such as  encrypted email forwarding, key escrow, and securing distributed file systems. Meanwhile, post-quantum cryptography (PQC) is one of the most important research areas because development of quantum computers has been advanced recently. In particular, there are many researches on public key encryption (PKE) algorithms selected/submitted in the NIST (National Institute of Standards and Technology) PQC standardization. However, there is no post-quantum PRE scheme secure against adaptive chosen ciphertext attacks (denoted by CCA security) while many (post-quantum) PRE schemes have been proposed so far. In this paper, we propose a bounded CCA secure PRE scheme based on CRYSTALS-Kyber which is a selected algorithm in the NIST PQC competition. To this end, we present generic constructions of bounded CCA secure PRE. Our generic constructions start from PRE secure against chosen plaintext attacks (denoted by CPA security). In order to instantiate our generic constructions, we present a CPA secure PRE scheme based on CRYSTALS-Kyber.



## 2024/1978

* Title: µLAM: A LLM-Powered Assistant for Real-Time Micro-architectural Attack Detection and Mitigation
* Authors: Upasana Mandal, Shubhi Shukla, Ayushi Rastogi, Sarani Bhattacharya, Debdeep Mukhopadhyay
* [Permalink](https://eprint.iacr.org/2024/1978)
* [Download](https://eprint.iacr.org/2024/1978.pdf)

### Abstract

The rise of microarchitectural attacks has necessitated robust detection and mitigation strategies to secure computing systems. Traditional tools, such as static and dynamic code analyzers and attack detectors, often fall short due to their reliance on predefined patterns and heuristics that lack the flexibility to adapt to new or evolving attack vectors. In this paper, we introduce for the first time a microarchitecture security assistant, built on OpenAI's GPT-3.5, which we refer to as µLAM. This assistant surpasses conventional tools by not only identifying vulnerable code segments but also providing context-aware mitigations, tailored to specific system specifications and existing security measures. Additionally, µLAM leverages real-time data from dynamic Hardware Performance Counters (HPCs) and system specifications to detect ongoing attacks, offering a level of adaptability and responsiveness that static and dynamic analyzers cannot match.


For fine-tuning µLAM, we utilize a comprehensive dataset that includes system configurations, mitigations already in place for different generations of systems, dynamic HPC values, and both vulnerable and non-vulnerable source codes. This rich dataset enables µLAM to harness its advanced LLM natural language processing capabilities to understand and interpret complex code patterns and system behaviors, learning continuously from new data to improve its predictive accuracy and respond effectively in real time to both known and novel threats, making it an indispensable tool against microarchitectural threats. In this paper, we demonstrate the capabilities of µLAM by fine-tuning and testing it on code utilizing well-known cryptographic libraries such as OpenSSL, Libgcrypt, and NaCl, thereby illustrating its effectiveness in securing critical and complex software environments.



## 2024/1979

* Title: On the Security of LWE-based KEMs under Various Distributions: A Case Study of Kyber
* Authors: Mingyao Shao, Yuejun Liu, Yongbin Zhou, Yan Shao
* [Permalink](https://eprint.iacr.org/2024/1979)
* [Download](https://eprint.iacr.org/2024/1979.pdf)

### Abstract

Evaluating the security of LWE-based KEMs involves two crucial metrics: the hardness of the underlying LWE problem and resistance to decryption failure attacks, both significantly influenced by the secret key and error distributions. To mitigate the complexity and timing vulnerabilities of Gaussian sampling, modern LWE-based schemes often adopt either the uniform or centered binomial distribution (CBD).

This work focuses on Kyber to evaluate its security under both distributions. Compared with the CBD, the uniform distribution over the same range enhances the LWE hardness but also increases the decryption failure probability, amplifying the risk of decryption failure attacks. We introduce a majority-voting-based key recovery method, and carry out a practical decryption failure attack on Kyber512 in this scenario with a complexity of $2^{37}$.

Building on this analysis, we propose uKyber, a variant of Kyber that employs the uniform distribution and parameter adjustments under the asymmetric module-LWE assumption. Compared with Kyber, uKyber maintains comparable hardness and decryption failure probability while reducing ciphertext sizes. Furthermore, we propose a multi-value sampling technique to enhance the efficiency of rejection sampling under the uniform distribution. These properties make uKyber a practical and efficient alternative to Kyber for a wide range of cryptographic applications.



## 2024/1980

* Title: Sonikku: Gotta Speed, Keed! A Family of Fast and Secure MACs
* Authors: Amit Singh Bhati, Elena Andreeva, Simon Müller, Damian Vizar
* [Permalink](https://eprint.iacr.org/2024/1980)
* [Download](https://eprint.iacr.org/2024/1980.pdf)

### Abstract

A message authentication code (MAC) is a symmetric-key cryptographic function used to authenticate a message by assigning it a tag. This tag is a short string that is difficult to reproduce without knowing the key. The tag ensures both the authenticity and integrity of the message, enabling the detection of any modifications.

A significant number of existing message authentication codes (MACs) are based on block ciphers (BCs) and tweakable block ciphers (TBCs). These MACs offer various trade-offs in properties, such as data processing rate per primitive call, use of single or multiple keys, security levels, pre- or post-processing, parallelizability, state size, and optimization for short/long queries.

In this work, we propose the $\mathsf{Sonikku}$ family of expanding primitive based MACs, consisting of three instances: $\mathsf{BabySonic}$, $\mathsf{DarkSonic}$, and $\mathsf{SuperSonic}$. The $\mathsf{Sonikku}$ MACs are -- 1) faster than the state-of-the-art TBC-based MACs; 2) secure beyond the birthday bound in the input block size; 3) smaller in state size compared to state-of-the-art MACs; and 4) optimized with diverse trade-offs such as pre/post-processing-free execution, parallelization, small footprint, and suitability for both short and long queries. These attributes make them favorable for common applications as well as ``IoT'' and embedded devices where processing power is limited.

On a Cortex-M4 32-bit microcontroller, $\mathsf{BabySonic}$ with $\mathsf{ForkSkinny}$ achieves a speed-up of at least 2.11x (up to 4.36x) compared to state-of-the-art ZMAC with $\mathsf{SKINNY}$ for 128-bit block sizes and queries of 95B or smaller. $\mathsf{DarkSonic}$ and $\mathsf{SuperSonic}$ with $\mathsf{ForkSkinny}$ achieve a speed-up of at least 1.93x for small queries of 95B or smaller and 1.48x for large queries up to 64KB, respectively, against ZMAC with $\mathsf{SKINNY}$ for both 64- and 128-bit block sizes.

Similar to ZMAC and PMAC2x, we then demonstrate the potential of our MAC family by using $\mathsf{SuperSonic}$ to construct a highly efficient, beyond-birthday secure, stateless, and deterministic authenticated encryption scheme, which we call SonicAE.



## 2024/1981

* Title: Shutter Network: Private Transactions from Threshold Cryptography
* Authors: Stefan Dziembowski, Sebastian Faust, Jannik Luhn
* [Permalink](https://eprint.iacr.org/2024/1981)
* [Download](https://eprint.iacr.org/2024/1981.pdf)

### Abstract

With the emergence of DeFi, attacks based on re-ordering transactions have become an essential problem for public blockchains. Such attacks include front-running or sandwiching transactions, where the adversary places transactions at a particular place within a block to influence a financial asset’s market price. In the Ethereum space, the value extracted by such attacks is often referred to as miner/maximal extractable value (MEV), which to date is estimated to have reached a value of more than USD 1.3B. A promising approach to protect against MEV is to hide the transaction data so block proposers cannot choose the order in which transactions are executed based on the transactions’ content. This paper describes the cryptographic protocol underlying the Shutter network. Shutter has been available as an open-source project since the end of 2021 and has been running in production since Oct. 2022.



## 2024/1982

* Title: New Results in Quantum Analysis of LED: Featuring One and Two Oracle Attacks
* Authors: Siyi Wang, Kyungbae Jang, Anubhab Baksi, Sumanta Chakraborty, Bryan Lee, Anupam Chattopadhyay, Hwajeong Seo
* [Permalink](https://eprint.iacr.org/2024/1982)
* [Download](https://eprint.iacr.org/2024/1982.pdf)

### Abstract

Quantum computing has attracted substantial attention from researchers across various fields. In case of the symmetric key cryptography, the main problem is posed by the application of Grover's search. In this work, we focus on quantum analysis of the lightweight block cipher LED.

This paper proposes an optimized quantum circuit for LED, minimizing the required number of qubits, quantum gates, and circuit depth. Furthermore, we conduct Grover's attack and Search with Two Oracles (STO) attack on the proposed LED cipher, estimating the quantum resources required for the corresponding attack oracles. The STO attack outperforms the usual Grover's search when the state size is less than the key size.  Beyond analyzing the cipher itself (i.e., the ECB mode), this work also evaluates the effectiveness of quantum attacks on LED across different modes of operation.



## 2024/1983

* Title: UTRA: Universe Token Reusability Attack and Verifiable Delegatable Order-Revealing Encryption
* Authors: Jaehwan Park, Hyeonbum Lee, Junbeom Hur, Jae Hong Seo, Doowon Kim
* [Permalink](https://eprint.iacr.org/2024/1983)
* [Download](https://eprint.iacr.org/2024/1983.pdf)

### Abstract

As dataset sizes continue to grow, users face increasing difficulties in performing processing tasks on their local machines. From this, privacy concerns about data leakage have led data owners to upload encrypted data and utilize secure range queries to cloud servers.
To address these challenges, order-revealing encryption (ORE) has emerged as a promising solution for large numerical datasets. Building on this, delegatable order-revealing encryption (DORE) was introduced, allowing operations between encrypted datasets with different secret keys in multi-client ORE environments. DORE operates through authorization tokens issued by the data owner. However, security concerns had arisen about unauthorized users exploiting data without permission, leading to the development of a secure order-revealing encryption scheme (SEDORE). These attacks can result in unauthorized data access and significant financial losses in modern cloud service providers (CSPs) utilizing pay-per-query systems. In addition, efficient delegatable order-revealing encryption (EDORE), which improves speed and storage compared to SEDORE with identical security levels, was also introduced.
Although both SEDORE and EDORE were designed to be robust against these attacks, we have identified that they still retain the same vulnerabilities within the same threat model. To address these issues, we propose Verifiable Delegatable Order-Revealing Encryption (VDORE), which protects against attacks by using the Schnorr Signature Scheme to verify the validity of the token that users send. We propose a precise definition and robust proof to improve the unclear definition and insufficient proof regarding token unforgeability in the SEDORE.
Furthermore, the token generation algorithm in VDORE provides about a $1.5\times$ speed-up compared to SEDORE.



## 2024/1984

* Title: Low Communication Threshold Fully Homomorphic Encryption
* Authors: Alain Passelègue, Damien Stehlé
* [Permalink](https://eprint.iacr.org/2024/1984)
* [Download](https://eprint.iacr.org/2024/1984.pdf)

### Abstract

This work investigates constructions of threshold fully homomorphic encryption with low communication, i.e., with small ciphertexts and small decryption shares. In this context, we discuss in detail the technicalities for achieving full-fledged threshold FHE, and put forward limitations regarding prior works, including an attack against the recent construction of Boudgoust and Scholl [ASIACRYPT 2023]. In light of our observations, we generalize the definition of threshold fully homomorphic encryption by adding an algorithm which allows to introduce additional randomness in ciphertexts before they are decrypted by parties. In this setting, we are able to propose a construction which offers small ciphertexts and small decryption shares.



## 2024/1985

* Title: Endomorphisms for Faster Cryptography on Elliptic Curves of Moderate CM Discriminants
* Authors: Dimitri Koshelev, Antonio Sanso
* [Permalink](https://eprint.iacr.org/2024/1985)
* [Download](https://eprint.iacr.org/2024/1985.pdf)

### Abstract

This article generalizes the widely-used GLV decomposition for scalar multiplication to a broader range of elliptic curves with moderate CM discriminant \( D < 0 \) (up to a few thousand in absolute value). Previously, it was commonly believed that this technique could only be applied efficiently for small \( D \) values (e.g., up to \( 100 \)). In practice, curves with \( j \)-invariant \( 0 \) are most frequently employed, as they have the smallest possible \( D = -3 \). This article participates in the decade-long development of numerous real-world curves with moderate \( D \) in the context of ZK-SNARKs.. Such curves are typically derived from others, which limits the ability to generate them while controlling the magnitude of \( D \). The most notable example is so-called "lollipop" curves demanded, among others, in the Mina protocol.

Additionally, the new results are relevant to one of the "classical" curves (with \( D = -619 \)) from the Russian ECC standard. This curve was likely found using the CM method (with overwhelming probability), though this is not explicitly stated in the standard. Its developers seemingly sought to avoid curves with small \( D \) values, aiming to mitigate potential DLP attacks on such curves, and hoped these attacks would not extend effectively to \( D = -619 \). One goal of the present article is to address the perceived disparity between the \( D = -3 \) curves and the Russian curve. Specifically, the Russian curve should either be excluded from the standard for potential security reasons or local software should begin leveraging the advantages of the GLV decomposition.



## 2024/1986

* Title: Improved Quantum Analysis of ARIA
* Authors: Yujin Oh, Kyungbae Jang, Hwajeong Seo
* [Permalink](https://eprint.iacr.org/2024/1986)
* [Download](https://eprint.iacr.org/2024/1986.pdf)

### Abstract

As advancements in quantum computing present potential threats to current cryptographic systems, it is necessary to reconsider and adapt existing cryptographic frameworks. Among these, Grover's algorithm reduces the attack complexity of symmetric-key encryption, making it crucial to evaluate the security strength of traditional symmetric-key systems.
In this paper, we implement an efficient quantum circuit for the ARIA symmetric-key encryption and estimate the required quantum resources. Our approach achieves a reduction of over 61\% in full depth and over 65.5\% in qubit usage compared to the most optimized previous research. Additionally, we estimate the cost of a Grover attack on ARIA and evaluate its post-quantum security strength.



## 2024/1987

* Title: Side-Channel Attack on ARADI
* Authors: Donggeun Kwon, Seokhie Hong
* [Permalink](https://eprint.iacr.org/2024/1987)
* [Download](https://eprint.iacr.org/2024/1987.pdf)

### Abstract

In this study, we present the first side-channel attack on the ARADI block cipher, exposing its vulnerabilities to physical attacks in non-profiled scenarios. We propose a novel bitwise divide-and-conquer methodology tailored for ARADI, enabling key recovery. Furthermore, based on our attack approach, we present a stepwise method for recovering the full 256-bit master key. Through experiments on power consumption traces from an ARM processor, we demonstrate successful recovery of target key bits, validating the effectiveness of our proposed method. Our findings highlight critical weaknesses in physical security of ARADI and underscore the necessity of implementing effective countermeasures to address side-channel vulnerabilities.



## 2024/1988

* Title: Garbled Circuits with 1 Bit per Gate
* Authors: Hanlin Liu, Xiao Wang, Kang Yang, Yu Yu
* [Permalink](https://eprint.iacr.org/2024/1988)
* [Download](https://eprint.iacr.org/2024/1988.pdf)

### Abstract

We present a garbling scheme for Boolean circuits with 1 bit per gate communication based on either ring learning with errors (RLWE) or NTRU assumption, with key-dependent message security. The garbling consists of  1) a homomorphically encrypted seed that can be expanded to encryption of many pseudo-random bits and  2) one-bit stitching information per gate to reconstruct garbled tables from the expanded ciphertexts. By using low-complexity PRGs, both the garbling and evaluation of each gate require only O(1) homomorphic addition/multiplication operations without bootstrapping.



## 2024/1989

* Title: Revisiting OKVS-based OPRF and PSI: Cryptanalysis and Better Construction
* Authors: Kyoohyung Han, Seongkwang Kim, Byeonghak Lee, Yongha Son
* [Permalink](https://eprint.iacr.org/2024/1989)
* [Download](https://eprint.iacr.org/2024/1989.pdf)

### Abstract

Oblivious pseudorandom function (OPRF) is a two-party cryptographic protocol that allows the receiver to input $x$ and learn $F(x)$ for some PRF $F$, only known to the sender. For private set intersection (PSI) applications, OPRF protocols have evolved to enhance efficiency, primarily using symmetric key cryptography. Current state-of-the-art protocols, such as those by Rindal and Schoppmann (Eurocrypt '21), leverage vector oblivious linear evaluation (VOLE) and oblivious key-value store (OKVS) constructions.

In this work, we identify a flaw in an existing security proof, and present practical attacks in the malicious model, which results in additional PRF evaluations than the previous works' claim. In particular, the attack for malicious model is related to the concept of OKVS overfitting, whose hardness is conjectured in previous works. Our attack is the first one to discuss the concrete hardness of OKVS overfitting problem.

As another flavour of contribution, we generalize OKVS-based OPRF constructions, suggesting new instantiations using a VOLE protocol with only Minicrypt assumptions. Our generalized construction shows improved performance in high-speed network environments, narrowing the efficiency gap between the OPRF constructions over Cryptomania and Minicrypt.



## 2024/1990

* Title: How To Scale Multi-Party Computation
* Authors: Marcel Keller
* [Permalink](https://eprint.iacr.org/2024/1990)
* [Download](https://eprint.iacr.org/2024/1990.pdf)

### Abstract

We propose a solution for optimized scaling of multi-party computation using the MP-SPDZ framework (CCS’20). It does not use manual optimization but extends the compiler and the virtual machine of the framework, thus providing an improvement for any user. We found that our solution improves timings four-fold for a simple example in MP-SPDZ, and it improves an order of magnitude on every framework using secret sharing considered by Hastings et al. (S&P’19) either in terms of time or RAM usage. The core of our approach is finding a balance between communication round optimization and memory usage.



## 2024/1991

* Title: CHLOE: Loop Transformation over Fully Homomorphic Encryption via Multi-Level Vectorization and Control-Path Reduction
* Authors: Song Bian, Zian Zhao, Ruiyu Shen, Zhou Zhang, Ran Mao, Dawei Li, Yizhong Liu, Masaki Waga, Kohei Suenaga, Zhenyu Guan, Jiafeng Hua, Yier Jin, Jianwei Liu
* [Permalink](https://eprint.iacr.org/2024/1991)
* [Download](https://eprint.iacr.org/2024/1991.pdf)

### Abstract

This work proposes a multi-level compiler framework to transform programs with loop structures to efficient algorithms over fully homomorphic encryption (FHE). We observe that, when loops operate over ciphertexts, it becomes extremely challenging to effectively interpret the control structures within the loop and construct operator cost models for the main body of the loop. Consequently, most existing compiler frameworks have inadequate support for programs involving non-trivial loops, undermining the expressiveness of programming over FHE. To achieve both efficient and general program execution over FHE,  we propose CHLOE, a new compiler framework with multi-level control-flow analysis for the effective optimization of compound repetition control structures. We observe that loops over FHE can be classified into two categories depending on whether the loop condition is encrypted, namely, the transparent loops and the oblivious loops. For transparent loops, we can directly inspect the control
structures and build operator cost models to apply FHE-specific loop segmentation and vectorization in a fine-grained manner. Meanwhile, for oblivious loops, we derive closed-form expressions and static analysis techniques to reduce the number of potential loop paths and conditional branches. In the experiment, we show that \NAME can compile programs with complex loop structures into efficient executable codes over FHE, where the performance improvement ranges from $1.5\times$ to $54\times$ (up to $10^{5}\times$ for programs containing oblivious loops) when compared to programs produced by the-state-of-the-art FHE compilers.



## 2024/1992

* Title: Improved Quantum Linear Attacks and Application to CAST
* Authors: Kaveh Bashiri, Xavier Bonnetain, Akinori Hosoyamada, Nathalie Lang, André Schrottenloher
* [Permalink](https://eprint.iacr.org/2024/1992)
* [Download](https://eprint.iacr.org/2024/1992.pdf)

### Abstract

This paper studies quantum linear key-recovery attacks on block ciphers.
The first such attacks were last-rounds attacks proposed by Kaplan et al. (ToSC 2016), which combine a linear distinguisher with a guess of a partial key. However, the most efficient classical attacks use the framework proposed by Collard et al. (ICISC 2007), which computes experimental correlations using the Fast Walsh-Hadamard Transform. Recently, Schrottenloher (CRYPTO 2023) proposed a quantum version of this technique, in which one uses the available data to create a quantum \emph{correlation state}, which is a superposition of subkey candidates where the amplitudes are the corresponding correlations. A limitation is that the good subkey is not marked in this state, and cannot be found easily.

In this paper, we combine the correlation state with another distinguisher. From here, we can use Amplitude Amplification to recover the right key. We apply this idea to Feistel ciphers and exemplify different attack strategies on LOKI91 before applying our idea on the CAST-128 and CAST-256 ciphers. We demonstrate the approach with two kinds of distinguishers, quantum distinguishers based on Simon's algorithm and linear distinguishers. The resulting attacks outperform the previous Grover-meet-Simon attacks.



## 2024/1993

* Title: BOIL: Proof-Carrying Data from Accumulation of Correlated Holographic IOPs
* Authors: Tohru Kohrita, Maksim Nikolaev, Javier Silva
* [Permalink](https://eprint.iacr.org/2024/1993)
* [Download](https://eprint.iacr.org/2024/1993.pdf)

### Abstract

In this paper, we present a batching technique for oracles corresponding to codewords of a Reed–Solomon code. This protocol is inspired by the round function of the STIR protocol (CRYPTO 2024). Using this oracle batching protocol, we propose a construction of a practically efficient accumulation scheme, which we call BOIL. Our accumulation scheme can be initiated with an arbitrary correlated holographic IOP, leading to a new class of PCD constructions. The results of this paper were originally given as a presentation at zkSummit12.



## 2024/1994

* Title: Token-Based Key Exchange - Non-Interactive Key Exchange meets Attribute-Based Encryption
* Authors: Elsie Mestl Fondevik, Kristian Gjøsteen
* [Permalink](https://eprint.iacr.org/2024/1994)
* [Download](https://eprint.iacr.org/2024/1994.pdf)

### Abstract

In this paper we define the novel concept token-based key exchange (TBKE), which can be considered a cross between non-interactive key exchange (NIKE) and attribute-based encryption (ABE). TBKE is a scheme that allows users within an organization to generate shared keys for a subgroup of users through the use of personal tokens and secret key. The shared key generation is performed locally and no interaction between users or with a server is needed.

The personal tokens are derived from a set of universal tokens and a master secret key which are generated and stored on a trusted central server. Users are only required to interact with the server during setup or if new tokens are provided. To reduce key escrow issues the server can be erased after all users have received their secret keys. Alternatively, if the server is kept available TBKE can additionally provide token revocation, addition and update.
 
We propose a very simple TBKE protocol using bilinear pairings.
The protocol is secure against user coalitions based upon a novel hidden matrix problem. The problems requires an adversary to compute  where the  adversary must compute a matrix product in the exponent, where some components are given in the clear and others are hidden as unknown exponents. We argue that the hidden matrix problem is as hard as dLog in the bilinear group model.



## 2024/1995

* Title: BitVM: Quasi-Turing Complete Computation on Bitcoin
* Authors: Lukas Aumayr, Zeta Avarikioti, Robin Linus, Matteo Maffei, Andrea Pelosi, Christos Stefo, Alexei Zamyatin
* [Permalink](https://eprint.iacr.org/2024/1995)
* [Download](https://eprint.iacr.org/2024/1995.pdf)

### Abstract

A long-standing question in the blockchain community is which class of computations are efficiently expressible in cryptocurrencies with limited scripting languages, such as Bitcoin Script. Such languages expose a reduced trusted computing base, thereby being less prone to hacks and vulnerabilities, but have long been believed to support only limited classes of payments.

In this work, we confute this long-standing belief by showing for the first time that arbitrary computations can be encoded in today's Bitcoin Script, without introducing any language modification or additional security assumptions, such as trusted hardware, trusted parties, or committees with secure majority. In particular, we present $\mathsf{BitVM}$, a two-party protocol realizing a generic virtual machine by a combination of cryptographic and incentive mechanisms. We conduct a formal analysis of $\mathsf{BitVM}$, characterizing its functionality, system assumptions, and security properties. We further demonstrate the practicality of our approach:  in the optimistic case (i.e., in the absence of disputes between parties), our protocol requires just three on-chain transactions, whereas in the pessimistic case, the number of transactions grows logarithmically with the size of the virtual machine.  This work not only solves a long-standing theoretical problem, but it also promises a strong practical impact, enabling the development of complex applications in Bitcoin.



## 2024/1996

* Title: A Framework for Generating S-Box Circuits with Boyer-Peralta Algorithm-Based Heuristics, and Its Applications to AES, SNOW3G, and Saturnin
* Authors: Yongjin Jeon, Seungjun Baek, Giyoon Kim, Jongsung Kim
* [Permalink](https://eprint.iacr.org/2024/1996)
* [Download](https://eprint.iacr.org/2024/1996.pdf)

### Abstract

In many lightweight cryptography applications, low area and latency are required for efficient implementation. The gate count in the cipher and the circuit depth must be low to minimize these two metrics. Many optimization strategies have been developed for the linear layer, led by the Boyer-Peralta (BP) algorithm. The Advanced Encryption Standard (AES) has been a focus of extensive research in this area. However, while the linear layer uses only XOR gates, the S-box, which is an essential nonlinear component in symmetric cryptography, uses various gate types, making optimization challenging, particularly as the bit size increases.

In this paper, we propose a new framework for a heuristic search to optimize the circuit depth or XOR gate count of S-box circuits. Existing S-box circuit optimization studies have divided the nonlinear and linear layers of the S-box, optimizing each separately, but limitations still exist in optimizing large S-box circuits. To extend the optimization target from individual internal components to the entire S-box circuit, we extract the XOR information of each node in the target circuit and reconstruct the nodes based on nonlinear gates. Next, we extend the BP algorithm-based heuristics to address nonlinear gates and incorporate this into the framework. It is noteworthy that the effects of our framework occur while maintaining the AND gate count and AND depth without any increase.

To demonstrate the effectiveness of the proposed framework, we apply it to the AES, SNOW3G, and Saturnin S-box circuits. Our results include depth improvements by about 40% and 11% compared to the existing AES S-box [BP10] and Saturnin super S-box [CDL+20] circuits, respectively. We implement a new circuit for the SNOW3G S-box, which has not previously been developed, and apply our framework to reduce its depth. We expect the proposed framework to contribute to the design and implementation of various symmetric-key cryptography solutions.



## 2024/1997

* Title: On format preserving encryption with nonce
* Authors: Alexander Maximov, Jukka Ylitalo
* [Permalink](https://eprint.iacr.org/2024/1997)
* [Download](https://eprint.iacr.org/2024/1997.pdf)

### Abstract

In this short paper we consider a format preserving encryption when a nonce is available. The encryption itself mimics a stream cipher where the keystream is of a (non-binary) radix $R$. We give a few practical and efficient ways to generate such a keystream from a binary keystream generator.



## 2024/1998

* Title: Impossible Differential Automation: Model Generation and New Techniques
* Authors: Emanuele Bellini, Paul Huynh, David Gerault, Andrea Visconti, Alessandro De Piccoli, Simone Pelizzola
* [Permalink](https://eprint.iacr.org/2024/1998)
* [Download](https://eprint.iacr.org/2024/1998.pdf)

### Abstract

In this paper, we aim to enhance and automate advanced techniques for impossible differential attacks. To demonstrate these advancements, we present improved attacks on the LBlock and HIGHT block ciphers. More precisely, we
(a) introduce a methodology to automatically invert symmetric ciphers when represented as directed acyclic graphs, a fundamental step in the search for impossible differential trails and in key recovery techniques;
(b) automate the search for impossible differential distinguishers, reproducing recent techniques and results;
(c) present a new hybrid model combining cell-wise properties and bit-wise granularity;
(d) integrate these techniques in the automated tool CLAASP;
(e) demonstrate the effectiveness of the tool by
reproducing a state-of-the-art 16-round impossible differential for LBlock previously obtained using a different technique and
exhibiting a new 18-round improbable trail;
(f) improve the state-of-the-art single-key recovery of HIGHT for 27 rounds, by automating the use of hash tables to current state-of-the-art results.



## 2024/1999

* Title: Multivariate Encryptions with LL’ perturbations - Is it possible to repair HFE in encryption? -
* Authors: Jacques Patarin, Pierre Varjabedian
* [Permalink](https://eprint.iacr.org/2024/1999)
* [Download](https://eprint.iacr.org/2024/1999.pdf)

### Abstract

We will present here new multivariate encryption algorithms. This is interesting since few multivariate encryption scheme currently exist, while their exist many more multivariate signature schemes. Our algorithms will combine several ideas, in particular the idea of the LL’ perturbation originally introduced, but only for signature, in [GP06]. In this paper, the LL’ perturbation will be used for encryption and will greatly differ from [GP06].. As we will see, our algorithms resists to all known attacks (in particular Gröbner attacks and MinRank attacks) and have reasonable computation time.



## 2024/2000

* Title: Evasive LWE Assumptions: Definitions, Classes, and Counterexamples
* Authors: Chris Brzuska, Akin Ünal, Ivy K. Y. Woo
* [Permalink](https://eprint.iacr.org/2024/2000)
* [Download](https://eprint.iacr.org/2024/2000.pdf)

### Abstract

The evasive LWE assumption, proposed by Wee [Eurocrypt'22 Wee] for constructing a lattice-based optimal broadcast encryption, has shown to be a powerful assumption, adopted by subsequent works to construct advanced primitives ranging from ABE variants to obfuscation for null circuits. However, a closer look reveals significant differences among the precise assumption statements involved in different works, leading to the fundamental question of how these assumptions compare to each other. In this work, we initiate a more systematic study on evasive LWE assumptions:
(i) Based on the standard LWE assumption, we construct simple counterexamples against three private-coin evasive LWE variants, used in [Crypto'22 Tsabary, Asiacrypt'22 VWW, Crypto'23 ARYY] respectively, showing that these assumptions are unlikely to hold.
(ii) Based on existing evasive LWE variants and our counterexamples, we propose and define three classes of plausible evasive LWE assumptions, suitably capturing all existing variants for which we are not aware of non-obfuscation-based counterexamples.
(iii) We show that under our assumption formulations, the security proofs of [Asiacrypt'22 VWW] and [Crypto'23 ARYY] can be recovered, and we reason why the security proof of [Crypto'22 Tsabary] is also plausibly repairable using an appropriate evasive LWE assumption.



## 2024/2001

* Title: Xiezhi: Toward Succinct Proofs of Solvency
* Authors: Youwei Deng, Jeremy Clark
* [Permalink](https://eprint.iacr.org/2024/2001)
* [Download](https://eprint.iacr.org/2024/2001.pdf)

### Abstract

A proof of solvency (or proof of reserves) is a zero-knowledge proof conducted by centralized cryptocurrency exchange to offer evidence that the exchange owns enough cryptocurrency to settle each of its users' balances. The proof seeks to reveal nothing about the finances of the exchange or its users, only the fact that it is solvent. The literature has already started to explore how to make proof size and verifier time independent of the number of (i) users on the exchange, and (ii) addresses used by the exchange. We argue there are a few areas of improvement. First, we propose and implement a full end-to-end argument that is fast for the exchange to prove (minutes), small in size (KBs), and fast to verify (seconds). Second, we deal with the natural conflict between Bitcoin and Ethereum's cryptographic setting (secp256k1) and more ideal settings for succinctness (e.g., pairing-based cryptography) with a novel mapping approach. Finally, we discuss how to adapt the protocol to the concrete parameters of bls12-381 (which is relevant because the bit-decomposition of all user balances will exceed the largest root of unity of the curve for even moderately-sized exchanges).



## 2024/2002

* Title: Improving Differential-Neural Distinguisher For Simeck Family
* Authors: Xue Yuan, Qichun Wang
* [Permalink](https://eprint.iacr.org/2024/2002)
* [Download](https://eprint.iacr.org/2024/2002.pdf)

### Abstract

In CRYPTO 2019, Gohr introduced the method of differential neural cryptanalysis, utilizing neural networks as the underlying distinguishers to achieve distinguishers for (5-8)-round of the Speck32/64 cipher and subsequently recovering keys for 11 and 12 rounds. Inspired by this work, we  propose an enhanced neural cryptanalysis framework that combines the Efficient Channel Attention (ECA) module with residual networks. By introducing the channel attention mechanism to emphasize key features and leveraging residual networks to facilitate efficient feature extraction and gradient flow, we achieve improved performance. Additionally, we employ a new data format that combines the ciphertext and the penultimate round ciphertext as input samples, providing the distinguisher with more useful features. Compared with the known results, our work enhance the accuracy of the neural distinguishers for Simeck32/64 (10-12)-round and achieve a new 13-round distinguisher. We also improve the accuracy of the Simeck48/96 (10-11)-round distinguishers and develop new (12-16)-round neural distinguishers. Moreover, we enhance the accuracy of the Simeck64/128 (14-18)-round distinguishers and obtain a new 19-round neural distinguisher. As a result, we achieve the highest accuracy and the longest rounds distinguishers for Simeck32/64, Simeck48/96, and Simeck64/128.



## 2024/2003

* Title: Exploring the Optimal  Differential Characteristics of SM4 (Full Version): Improving Automatic Search by Including Human Insights
* Authors: Bingqing Li, Ling Sun
* [Permalink](https://eprint.iacr.org/2024/2003)
* [Download](https://eprint.iacr.org/2024/2003.pdf)

### Abstract

This study aims to determine the complete and precise differential properties of SM4, which have remained unknown for over twenty years after the cipher was initially released. A Boolean Satisfiability Problem (SAT) based automatic search approach is employed to achieve the objective. To improve the limited efficiency of the search focused on differential probabilities, we want to investigate the feasibility of integrating human expertise into an automatic approach to enhance the search speed. This study presents the construction of four new SAT models that describe the human-identified specific properties of short differential characteristics. All of these models are integrated into the fundamental model, and the SAT solver is implemented to assess the acceleration capabilities of the new models. The experimental results indicate that including three new models effectively decreases the overall execution time of the SAT solver. Using the novel models, we obtain the first precise minimal values for the number of active S-boxes of SM4 under single-key (complete rounds) and related-key (1-round to 19-round) settings. The first precise upper bound for differential probabilities of SM4 (1-round to 20-round) is also determined. In addition, we present the first publicly revealed optimal 19-round differential characteristic of SM4.



## 2024/2004

* Title: Regev's attack on hyperelliptic cryptosystems
* Authors: Razvan Barbulescu, Gaetan Bisson
* [Permalink](https://eprint.iacr.org/2024/2004)
* [Download](https://eprint.iacr.org/2024/2004.pdf)

### Abstract

Hyperelliptic curve cryptography (HECC) is a candidate to standardization which is a competitive alternative to elliptic curve cryptography (ECC). We extend Regev's algorithm to this setting. For genus-two curves relevant to cryptography, this yields a quantum attack up to nine times faster than the state-of-the-art. This implies that HECC is slightly weaker than ECC. In a more theoretical direction, we show that Regev's  algorithm obtains its full speedup with respect to Shor's when the genus is high, a setting which is already known to be inadequate for cryptography.



## 2024/2005

* Title: Post-Quantum Secure Channel Protocols for eSIMs
* Authors: Luk Bettale, Emmanuelle Dottax, Laurent Grémy
* [Permalink](https://eprint.iacr.org/2024/2005)
* [Download](https://eprint.iacr.org/2024/2005.pdf)

### Abstract

The transition to Post-Quantum (PQ) cryptography is increasingly mandated by national agencies and organizations, often involving a phase where classical and PQ primitives are combined into hybrid solutions. In this context, existing protocols must be adapted to ensure quantum resistance while maintaining their security goals. These adaptations can significantly impact performance, particularly on embedded devices.
In this article, we focus on standardized protocols which support application management on eSIMs across different modes. This is a complex use-case, involving constrained devices with stringent security requirements. We present PQ adaptations, including both hybrid and fully PQ versions, for all modes. Using ProVerif, we provide automated proofs that verify the security of these PQ variants. Additionally, we analyze the performance impact of implementing PQ protocols on devices, measuring runtime and bandwidth consumption. Our findings highlight the resource overhead associated with achieving post-quantum security for eSIM management.



## 2024/2006

* Title: Data Decryption and Analysis of Note-Taking Applications
* Authors: Seyoung Yoon, Myungseo Park, Kyungbae Jang, Hwajeong Seo
* [Permalink](https://eprint.iacr.org/2024/2006)
* [Download](https://eprint.iacr.org/2024/2006.pdf)

### Abstract

As smartphone usage continues to grow, the demand for note-taking applications, including memo and diary apps, is rapidly increasing. These applications often contain sensitive information such as user schedules, thoughts, and activities, making them key targets for analysis in digital forensics. Each year, new note-taking applications are released, most of which include lock features to protect user data. However, these security features can create challenges for authorized investigators attempting to access and analyze application data. This paper aims to support investigators by conducting a static analysis of Android-based note-taking applications. It identifies how and where data is stored and explains methods for extracting and decrypting encrypted data. Based on the analysis, the paper concludes by proposing future research directions in the field of digital forensics.



## 2024/2007

* Title: A Combinatorial Attack on Ternary Sparse Learning with Errors (sLWE)
* Authors: Abul Kalam, Santanu Sarkar, Willi Meier
* [Permalink](https://eprint.iacr.org/2024/2007)
* [Download](https://eprint.iacr.org/2024/2007.pdf)

### Abstract

Sparse Learning With Errors (sLWE) is a novel problem introduced at Crypto 2024 by Jain et al., designed to enhance security in lattice-based cryptography against quantum attacks while maintaining computational efficiency. This paper presents the first third-party analysis of the ternary variant of sLWE, where both the secret and error vectors are constrained to ternary values. We introduce a combinatorial attack that employs a subsystem extraction technique followed by a Meet-in-the-Middle approach, effectively recovering the ternary secret vector. Our comprehensive analysis explores the attack's performance across various sparsity and modulus settings, revealing critical security limitations inherent in ternary sLWE.

Our analysis does not claim to present any attack on the proposal of Jain et al.; rather, it supports their assertion that sparse LWE is vulnerable for small secrets, particularly for ternary secrets and ternary errors. Notably, our findings indicate that the recommended parameters, which the developers claim provide security equivalent to LWE with a dimension of 1024, may not hold true for the ternary variant of sLWE.
Our research highlights that, particularly with a modulus of $2^{64}$, the secret key can be recovered in a practical timeframe, supporting the developers' claim of vulnerability in this case. Additionally, for configurations with moduli of $2^{32}$ and $2^{16}$, we observe a significant reduction in the security margin. This suggests that the actual security level may be significantly weaker than intended. Overall, our work contributes crucial insights into the cryptographic robustness of ternary sLWE, emphasizing the need for further strengthening to protect against potential attacks and setting the stage for future research in this area.



## 2024/2008

* Title: PrivCirNet: Efficient Private Inference via Block Circulant Transformation
* Authors: Tianshi Xu, Lemeng Wu, Runsheng Wang, Meng Li
* [Permalink](https://eprint.iacr.org/2024/2008)
* [Download](https://eprint.iacr.org/2024/2008.pdf)

### Abstract

Homomorphic encryption (HE)-based deep neural network (DNN) inference protects data and model privacy but suffers from significant computation overhead. We observe transforming the DNN weights into circulant matrices converts general matrix-vector multiplications into HE-friendly 1-dimensional convolutions, drastically reducing the HE computation cost. Hence, in this paper, we propose PrivCirNet, a protocol/network co-optimization framework based on block circulant transformation. At the protocol level, PrivCirNet customizes the HE encoding algorithm that is fully compatible with the block circulant transformation and reduces the computation latency in proportion to the block size. At the network level, we propose a latency-aware formulation to search for the layer-wise block size assignment based on second-order information. PrivCirNet also leverages layer fusion to further reduce the inference cost. We compare PrivCirNet with the state-of-the-art HE-based framework Bolt (IEEE S&P 2024) and HE-friendly pruning method SpENCNN (ICML 2023). For ResNet-18 and Vision Transformer (ViT) on Tiny ImageNet, PrivCirNet reduces latency by $5.0\times$ and $1.3\times$ with iso-accuracy over Bolt, respectively, and improves accuracy by $4.1\%$ and $12\%$ over SpENCNN, respectively. For MobileNetV2 on ImageNet, PrivCirNet achieves $1.7\times$ lower latency and $4.2\%$ better accuracy over Bolt and SpENCNN, respectively.
    Our code and checkpoints are available at https://github.com/Tianshi-Xu/PrivCirNet.



## 2024/2009

* Title: The Mis/Dis-information Problem is  Hard to Solve
* Authors: Gregory Hagen, Reihaneh Safavi-Naini, Moti Yung
* [Permalink](https://eprint.iacr.org/2024/2009)
* [Download](https://eprint.iacr.org/2024/2009.pdf)

### Abstract

Securing information communication dates back thousands of years ago. The meaning of information security, however, has evolved over time and today covers a very wide variety of goals, including identifying the source of information, the reliability of information, and ultimately whether the information is trustworthy.
In this paper, we will look at the evolution of the information security problem and the approaches that have been developed for providing
information protection. We argue that the more recent problem of misinformation and disinformation has shifted the content integrity problem from the protection of message syntax to the protection of message semantics. This shift, in the age of advanced AI systems, a technology that can be used to mimic human-generated content as well as to create bots that mimic human behaviour on the Internet, poses fundamental technological challenges that evade existing technologies. It leaves social elements, including public education and a suitable legal framework, as increasingly the main pillars of effective protection, at least in the short run. It also poses an intriguing challenge to the scientific community: to design effective solutions that employ cryptography and AI, together with incentivization to engage the global community, to ensure the safety of the information ecosystem.



## 2024/2010

* Title: Anonymous credentials from ECDSA
* Authors: Matteo Frigo, abhi shelat
* [Permalink](https://eprint.iacr.org/2024/2010)
* [Download](https://eprint.iacr.org/2024/2010.pdf)

### Abstract

Anonymous digital credentials allow a user to prove possession of an attribute that has been asserted by an identity issuer without revealing any extra information about themselves.  For example, a user who has received a digital passport credential can prove their “age is $>18$” without revealing any other attributes such as their name or date of birth.

    Despite inherent value for privacy-preserving authentication, anonymous credential schemes have been difficult to deploy at scale.  Part of the difficulty arises because schemes in the literature, such as BBS+, use new cryptographic assumptions that require system-wide changes to existing issuer infrastructure.  In addition,  issuers often require digital identity credentials to be *device-bound* by incorporating the device’s secure element into the presentation flow.  As a result, schemes like BBS+ require updates to the hardware secure elements and OS on every user's device.
   
    In this paper, we propose a new anonymous credential scheme for the popular and legacy-deployed Elliptic Curve Digital Signature Algorithm (ECDSA) signature scheme.  By adding efficient zk arguments for statements about SHA256 and document parsing for ISO-standardized identity formats, our anonymous credential scheme is that first one that can be deployed *without* changing any issuer processes, *without* requiring changes to mobile devices, and *without* requiring non-standard cryptographic assumptions.

    Producing ZK proofs about ECDSA signatures has been a bottleneck for other ZK proof systems because standardized curves such as P256 use finite fields which do not support efficient number theoretic transforms.  We overcome this bottleneck by designing a ZK proof system around sumcheck and the Ligero argument system, by designing efficient methods for Reed-Solomon encoding over the required fields, and by designing specialized circuits for ECDSA.
       
    Our proofs for ECDSA can be generated in 60ms.  When incorporated into a fully standardized identity protocol such as the ISO MDOC standard, we can generate a zero-knowledge proof for the MDOC presentation flow in 1.2 seconds on mobile devices depending on the credential size. These advantages make our scheme a promising candidate for privacy-preserving digital identity applications.



## 2024/2011

* Title: Honest-Majority Threshold ECDSA with Batch Generation of Key-Independent Presignatures
* Authors: Jonathan Katz, Antoine Urban
* [Permalink](https://eprint.iacr.org/2024/2011)
* [Download](https://eprint.iacr.org/2024/2011.pdf)

### Abstract

Several protocols have been proposed recently for threshold ECDSA signatures, mostly in the dishonest-majority setting. Yet in so-called key-management networks, where a fixed set of servers share a large number of keys on behalf of multiple users, it may be reasonable to assume that a majority of the servers remain uncompromised, and in that case there may be several advantages to using an honest-majority protocol.

With this in mind, we describe an efficient protocol for honest-majority threshold ECDSA supporting batch generation of key-independent presignatures that allow for "non-interactive'" online signing; these properties are not available in existing dishonest-majority protocols. Our protocol offers low latency and high throughput, and runs at an amortized rate of roughly 1.3 ms/presignature.



## 2024/2012

* Title: GraSS: Graph-based Similarity Search on Encrypted Query
* Authors: Duhyeong Kim, Yujin Nam, Wen Wang, Huijing Gong, Ishwar Bhati, Rosario Cammarota, Tajana S. Rosing, Mariano Tepper, Theodore L. Willke
* [Permalink](https://eprint.iacr.org/2024/2012)
* [Download](https://eprint.iacr.org/2024/2012.pdf)

### Abstract

Similarity search, i.e., retrieving vectors in a database that are similar to a query, is the backbone of many applications. Especially, graph-based methods show state-of-the-art performance. For sensitive applications, it is critical to ensure the privacy of the query and the dataset.

In this work, we introduce GraSS, a secure protocol between client (query owner) and server (dataset owner) for graph-based similarity search based on fully homomorphic encryption (FHE).  Both the client-input privacy against the server and the server-input privacy against the client are achievable based on underlying security assumptions on FHE.

We first propose an FHE-friendly graph structure with a novel index encoding method that makes our protocol highly scalable in terms of data size, reducing the computational complexity of neighborhood retrieval process from $O(n^2)$ to $\tilde{O}(n)$ for the total number of nodes $n$. We also propose several core FHE algorithms to perform graph operations under the new graph structure. Finally, we introduce GraSS, an end-to-end solution of secure graph-based similarity search based on FHE. To the best of our knowledge, it is the first FHE-based solution for secure graph-based database search.

We implemented GraSS with an open-source FHE library and estimated the performance on a million-scale dataset. GraSS identifies (approximate) top-16 in about $83$ hours achieving search accuracy of $0.918$, making it over $28\times$ faster than the previous best-known FHE-based solution.



## 2024/2013

* Title: Crescent: Stronger Privacy for Existing Credentials
* Authors: Christian Paquin, Guru-Vamsi Policharla, Greg Zaverucha
* [Permalink](https://eprint.iacr.org/2024/2013)
* [Download](https://eprint.iacr.org/2024/2013.pdf)

### Abstract

We describe Crescent, a construction and implementation of privacy-preserving credentials. The system works by upgrading the privacy features of existing credentials, such as JSON Web Tokens (JWTs) and Mobile Driver’s License (mDL) and as such does not require a new party to issue credentials. By using zero-knowledge proofs of possession of these credentials, we can add privacy features such as selective disclosure and unlinkability, without help from credential issuers. The system has practical performance, offering fast proof generation and verification times (tens of milliseconds) after a once-per-credential setup phase. We give demos for two practical scenarios, proof of employment for benefits eligibility (based on an employer-issued JWT), and online age verification (based on an mDL). We provide an open-source implementation to enable further research and experimentation.

This paper is an early draft describing our work, aiming to include enough material to describe the functionality, and some details of the internals of our new library, available at https://github.com/microsoft/crescent-credentials.



## 2024/2014

* Title: On the Traceability of Group Signatures: Uncorrupted User Must Exist
* Authors: Keita Emura
* [Permalink](https://eprint.iacr.org/2024/2014)
* [Download](https://eprint.iacr.org/2024/2014.pdf)

### Abstract

Group signature (GS) is a well-known cryptographic primitive providing anonymity and traceability. Several implication results have been given by mainly focusing on the several security levels of anonymity, e.g., fully anonymous GS implies public key encryption (PKE) and selfless anonymous GS can be constructed from one-way functions and non-interactive zero knowledge poofs, and so on. In this paper, we explore an winning condition of full traceability: an adversary is required to produce a valid group signature whose opening result is an uncorrupted user.  We demonstrate a generic construction of GS secure in the Bellare-Micciancio-Warinschi (BMW) model except the above condition from PKE only. We emphasize that the proposed construction is quite artificial and meaningless in practice because the verification algorithm always outputs 1 regardless of the input. This result suggests us the winning condition is essential in full traceability, i.e., an uncorrupted user must exist. We also explore a public verifiability of GS-based PKE scheme and introduce a new formal security definition of public verifiability by following BUFF (Beyond UnForgeability Features) security. Our definition guarantees that the decryption result of a valid cyphertext is in the message space specified by the public key. We show that the GS-based PKE scheme is publicly verifiable if the underlying GS scheme is fully traceable.



## 2024/2015

* Title: Universal SNARGs for NP from Proofs of Correctness
* Authors: Zhengzhong Jin, Yael Tauman Kalai, Alex Lombardi, Surya Mathialagan
* [Permalink](https://eprint.iacr.org/2024/2015)
* [Download](https://eprint.iacr.org/2024/2015.pdf)

### Abstract

We give new constructions of succinct non-interactive arguments ($\mathsf{SNARG}$s) for $\mathsf{NP}$ in the settings of both non-adaptive and adaptive soundness.

Our construction of non-adaptive $\mathsf{SNARG}$ is universal assuming the security of a (leveled or unleveled) fully homomorphic encryption ($\mathsf{FHE}$) scheme as well as a batch argument ($\mathsf{BARG}$) scheme. Specifically, for any choice of parameters $\ell$ and $L$, we construct a candidate $\mathsf{SNARG}$ scheme for any $\mathsf{NP}$ language $\mathcal{L}$ with the following properties:

    - the proof length is $\ell\cdot \mathsf{poly}(\lambda)$,
    - the common reference string $\mathsf{crs}$ has length $L\cdot \mathsf{poly}(\lambda)$, and
   - the setup is transparent (no private randomness).

We prove that this $\mathsf{SNARG}$ has non-adaptive soundness assuming the existence of any $\mathsf{SNARG}$ where the proof size is $\ell$, the $\mathsf{crs}$ size is  $L$, and there is a size $L$ Extended Frege ($\mathcal{EF}$) proof of completeness for the $\mathsf{SNARG}$.

Moreover, we can relax the underlying $\mathsf{SNARG}$ to be any 2-message privately verifiable argument where the first message is of length $L$ and the second message is of length $\ell$. This yields new $\mathsf{SNARG}$ constructions based on any ``$\mathcal{EF}$-friendly'' designated-verifier $\mathsf{SNARG}$ or witness encryption scheme. We emphasize that our $\mathsf{SNARG}$ is universal in the sense that it does not depend on the argument system.

We show several new implications of this construction that do not reference proof complexity:

    - a non-adaptive $\mathsf{SNARG}$ for $\mathsf{NP}$ with transparent $\mathsf{crs}$ from evasive $\mathsf{LWE}$ and $\mathsf{LWE}$. This gives a candidate lattice-based $\mathsf{SNARG}$ for $\mathsf{NP}$.
   - a non-adaptive $\mathsf{SNARG}$ for $\mathsf{NP}$ with transparent $\mathsf{crs}$ assuming the (non-explicit) existence of any $\mathsf{iO}$ and $\mathsf{LWE}$.
    - a non-adaptive $\mathsf{SNARG}$ for $\mathsf{NP}$ with a short and transparent (i.e., uniform) $\mathsf{crs}$ assuming $\mathsf{LWE}$, $\mathsf{FHE}$ and the (non-explicit) existence of any hash function that makes Micali's $\mathsf{SNARG}$ construction sound.
    - a non-adaptive $\mathsf{SNARG}$ for languages such as $\mathsf{QR}$ and $\overline{\mathsf{DCR}}$ assuming only $\mathsf{LWE}$.

In the setting of adaptive soundness, we show how to convert any designated verifier $\mathsf{SNARG}$ into publicly verifiable $\mathsf{SNARG}$, assuming the underlying designated verifier $\mathsf{SNARG}$ has an $\mathcal{EF}$ proof of completeness. As a corollary, we construct an adaptive $\mathsf{SNARG}$ for $\mathsf{UP}$ with a transparent $\mathsf{crs}$ assuming subexponential $\mathsf{LWE}$ and evasive $\mathsf{LWE}$.

We prove our results by extending the encrypt-hash-and-$\mathsf{BARG}$ paradigm of [Jin-Kalai-Lombardi-Vaikuntanathan, STOC '24].



## 2024/2016

* Title: The Existence of Quantum One-Way Functions
* Authors: Ping Wang, Yikang Lei, Zishen Shen, Fangguo Zhang
* [Permalink](https://eprint.iacr.org/2024/2016)
* [Download](https://eprint.iacr.org/2024/2016.pdf)

### Abstract

One-way functions are essential tools for cryptography. However, the existence of one-way functions is still an open conjecture. By constructing a function with classical bits as input and quantum states as output, we prove for the first time the existence of quantum one-way functions. It provides theoretical guarantees for the security of many quantum cryptographic protocols.



## 2024/2017

* Title: Byzantine Consensus in Wireless Networks
* Authors: Hao Lu, Jian Liu, Kui Ren
* [Permalink](https://eprint.iacr.org/2024/2017)
* [Download](https://eprint.iacr.org/2024/2017.pdf)

### Abstract

A Byzantine consensus protocol is essential in decentralized systems as the protocol ensures system consistency despite node failures.
Research on consensus in wireless networks receives relatively less attention, while significant advancements in wired networks.
However, consensus in wireless networks has equal significance as in wired networks.

In this paper, we propose a new reliable broadcast protocol that can achieve reliability with high fault tolerance over than the SOTA (PODC '05). With the new protocol, we further develop the first wireless network Byzantine consensus protocol under the assumption of partial synchrony. Notably, this consensus protocol removes the requirement of leaders and fail-over mechanism in prior works. We formally prove the correctness of both our new broadcast protocol and consensus protocol.



## 2024/2018

* Title: On the BUFF Security of ECDSA with Key Recovery
* Authors: Keita Emura
* [Permalink](https://eprint.iacr.org/2024/2018)
* [Download](https://eprint.iacr.org/2024/2018.pdf)

### Abstract

In the usual syntax of digital signatures, the verification algorithm takes a verification key in addition to a signature and a message, whereas in ECDSA with key recovery, which is used in Ethereum,  no verification key is input to the verification algorithm. Instead, a verification key is recovered from a signature and a message. In this paper, we explore BUFF security of ECDSA with key recovery (KR-ECDSA), where BUFF stands for Beyond UnForgeability Features (Cremers et al., IEEE S&P 2021).  As a result, we show that KR-ECDSA provides BUFF security, except weak non-resignability (wNR). We pay attention to that the verification algorithm of KR-ECDSA takes an Ethereum address addr as input, which is defined as the rightmost 160-bits of the Keccak-256 hash of the corresponding ECDSA verification key, and checks the hash value of the recovered verification key is equal to addr.  Our security analysis shows that this procedure is mandatory to provide BUFF security. We also discuss whether wNR is mandatory in Ethereum or not.  To clarify the above equality check is mandatory to provide BUFF security in KR-ECDSA, we show that the original ECDSA does not provide any BUFF security. As a by-product of the analysis, we show that one of our BUFF attacks also works against the Aumayr et al.'s ECDSA-based adaptor signature scheme (ASIACRYPT 2021). We emphasize that the attack is positioned outside of their security model.



## 2024/2019

* Title: Key-Insulated and Privacy-Preserving Signature Scheme with Publicly Derived Public Key, Revisited: Consistency, Outsider Strong Unforgeability, and Generic Construction
* Authors: Keita Emura
* [Permalink](https://eprint.iacr.org/2024/2019)
* [Download](https://eprint.iacr.org/2024/2019.pdf)

### Abstract

Liu et al. (EuroS&P 2019) introduced Key-Insulated and Privacy-Preserving Signature Scheme with Publicly Derived Public Key (PDPKS) to enhance the security of stealth address and deterministic wallet. In this paper, we point out that the current security notions are insufficient in practice, and introduce a new security notion which we call consistency. Moreover, we explore the unforgeability to provide strong unforgeability for outsider which captures the situation that nobody, except the payer and the payee, can produce a valid signature. From the viewpoint of cryptocurrency functionality, it allows us to implement a refund functionality. Finally, we propose a generic construction of PDPKS that provides consistency and outsider strong unforgeability. The design is conceptually much simpler than known PDPKS constructions. It is particularly note that the underlying strongly unforgeable signature scheme is required to provide the strong conservative exclusive ownership (S-CEO) security (Cremers et al., IEEE S&P 2021). Since we explicitly require the underlying signature scheme to be S-CEO secure, our security proof introduces a new insight of exclusive ownership security which may be of independent interest. As instantiations, we can obtain a pairing-based PDPKS scheme in the standard model, a discrete-logarithm based pairing-free PDPKS scheme in the random oracle model, and a lattice-based PDPKS scheme in the random oracle model, and so on.



## 2024/2020

* Title: Ring Ring! Who's There? A Privacy Preserving Mobile Number Search
* Authors: Akshit Aggarwal
* [Permalink](https://eprint.iacr.org/2024/2020)
* [Download](https://eprint.iacr.org/2024/2020.pdf)

### Abstract

Private set intersection (PSI) allows any two parties (say client and server) to jointly compute the intersection of their sets without revealing anything else. Fully homomorphic encryption (FHE)-based PSI is a cryptographic solution to implement PSI-based protocols. Most FHE-based PSI protocols implement hash function approach and oblivious transfer approach. The main limitations of their protocols are 1) high communication complexity, that is, $O(xlogy)$ (where $x$ is total number of elements on client side, and $y$ is total number of elements on server side), and 2) high memory usage due to SIMD packing for encrypting large digit numbers. In this work, we design a novel tree-based approach to store the large digit numbers that achieves less communication complexity, that is, $O(|d|^{2})$ (where $d$ is digits of a mobile number). Later we implement our protocol using Tenseal library. Our designed protocol opens the door to find the common elements with less communication complexity and less memory usage.



## 2024/2021

* Title: PrivQuant: Communication-Efficient Private Inference with Quantized Network/Protocol Co-Optimization
* Authors: Tianshi Xu, Shuzhang Zhong, Wenxuan Zeng, Runsheng Wang, Meng Li
* [Permalink](https://eprint.iacr.org/2024/2021)
* [Download](https://eprint.iacr.org/2024/2021.pdf)

### Abstract

Private deep neural network (DNN) inference based on secure two-party computation (2PC) enables secure privacy protection for both the server and the client. However, existing secure 2PC frameworks suffer from a high inference latency due to enormous communication. As the communication of both linear and non-linear DNN layers reduces with the bit widths of weight and activation, in this paper, we propose PrivQuant, a framework that jointly optimizes the 2PC-based quantized inference protocols and the network quantization algorithm, enabling communication-efficient private inference. PrivQuant proposes DNN architecture-aware optimizations for the 2PC protocols for communication-intensive quantized operators and conducts graph-level operator fusion for communication reduction. Moreover, PrivQuant also develops a communication-aware mixed precision quantization algorithm to improve the inference efficiency while maintaining high accuracy. The network/protocol co-optimization enables PrivQuant to outperform prior-art 2PC frameworks. With extensive experiments, we demonstrate PrivQuant reduces communication by $11\times, 2.5\times \mathrm{and}~  2.8\times$, which results in $8.7\times, 1.8\times ~ \mathrm{and}~ 2.4\times$ latency reduction compared with SiRNN, COINN, and CoPriv, respectively.



## 2024/2022

* Title: The Revisited Hidden Weight Bit Function
* Authors: Pierrick Méaux, Tim Seuré, Deng Tang
* [Permalink](https://eprint.iacr.org/2024/2022)
* [Download](https://eprint.iacr.org/2024/2022.pdf)

### Abstract

The Hidden Weight Bit Function (HWBF) has drawn considerable attention for its simplicity and cryptographic potential. Despite its ease of implementation and favorable algebraic properties, its low nonlinearity limits its direct application in modern cryptographic designs. In this work, we revisit the HWBF and propose a new weightwise quadratic variant obtained by combining the HWBF with a bent function. This construction offers improved cryptographic properties while remaining computationally efficient. We analyze the balancedness, nonlinearity, and other criteria of this function, presenting theoretical bounds and experimental results to highlight its advantages over existing functions in similar use cases. The different techniques we introduce to study the nonlinearity of this function also enable us to bound the nonlinearity of a broad family of weightwise quadratic functions, both theoretically and practically. We believe these methods are of independent interest.



## 2024/2023

* Title: An Abstract Multi-Forking Lemma
* Authors: Charanjit S Jutla
* [Permalink](https://eprint.iacr.org/2024/2023)
* [Download](https://eprint.iacr.org/2024/2023.pdf)

### Abstract

In this work we state and prove an abstract version of the multi-forking lemma of Pointcheval and Stern from EUROCRYPT'96. Earlier, Bellare and Neven had given an abstract version of forking lemma for two-collisions (CCS'06). While the original purpose of the forking lemma was to prove security of signature schemes in the random oracle methodology, the abstract forking lemma can be used to obtain security proofs for multi-signatures, group signatures, and compilation of interactive protocols under the Fiat-Shamir random-oracle methodology.



## 2024/2024

* Title: Hash-Prune-Invert: Improved Differentially Private Heavy-Hitter Detection in the Two-Server Model
* Authors: Borja Balle, James Bell, Albert Cheu, Adria Gascon, Jonathan Katz, Mariana Raykova, Phillipp Schoppmann, Thomas Steinke
* [Permalink](https://eprint.iacr.org/2024/2024)
* [Download](https://eprint.iacr.org/2024/2024.pdf)

### Abstract

Differentially private (DP) heavy-hitter detection is an important primitive for  data analysis. Given a threshold $t$ and a dataset of $n$ items from a domain of size $d$, such detection algorithms ignore items occurring fewer than $t$ times while identifying items occurring more than $t+\Delta$ times; we call $\Delta$ the error margin. In the central model where a curator holds the entire dataset, $(\varepsilon,\delta)$-DP algorithms can achieve error margin $\Theta(\frac 1 \varepsilon \log \frac 1 \delta)$, which is optimal when $d \gg 1/\delta$.
   
    Several works, e.g., Poplar (S&P 2021), have proposed protocols in which two or more non-colluding servers jointly compute the heavy hitters from inputs held by $n$ clients. Unfortunately, existing protocols suffer from an undesirable dependence on $\log d$ in terms of both server efficiency (computation, communication, and round complexity) and accuracy (i.e., error margin), making them unsuitable for large domains (e.g., when items are kB-long strings, $\log d \approx 10^4$).
   
    We present hash-prune-invert (HPI), a technique for compiling any heavy-hitter protocol with the $\log d$ dependencies mentioned above into a new protocol with improvements across the board: computation, communication, and round complexity depend (roughly) on $\log n$ rather than $\log d$, and the error margin is independent of $d$. Our transformation preserves privacy against an active adversary corrupting at most one of the servers and any number of clients. We apply HPI to an improved version of Poplar, also introduced in this work, that improves Poplar's error margin by roughly a factor of $\sqrt{n}$ (regardless of $d$). Our experiments confirm that the resulting protocol improves efficiency and accuracy for large $d$.



## 2024/2025

* Title: Mira: Efficient Folding for Pairing-based Arguments
* Authors: Josh Beal, Ben Fisch
* [Permalink](https://eprint.iacr.org/2024/2025)
* [Download](https://eprint.iacr.org/2024/2025.pdf)

### Abstract

Pairing-based arguments offer remarkably small proofs and space-efficient provers, but aggregating such proofs remains costly. Groth16 SNARKs and KZG polynomial commitments are prominent examples of this class of arguments. These arguments are widely deployed in decentralized systems, with millions of proofs generated per day. Recent folding schemes have greatly reduced the cost of proving incremental computations, such as batch proof verification. However, existing constructions require encoding pairing operations in generic constraint systems, leading to high prover overhead. In this work, we introduce Mira, a folding scheme that directly supports pairing-based arguments. We construct this folding scheme by generalizing the framework in Protostar to support a broader class of special-sound protocols. We demonstrate the versatility and efficiency of this framework through two key applications: Groth16 proof aggregation and verifiable ML inference. Mira achieves 5.8x faster prover time and 9.7x lower memory usage than the state-of-the-art proof aggregation system while maintaining a constant-size proof. To improve the efficiency of verifiable ML inference, we provide a new lincheck protocol with a verifier degree that is independent of the matrix order. We show that Mira scales effectively to larger models, overcoming the memory bottlenecks of current schemes.



## 2024/2026

* Title: Orbweaver: Succinct Linear Functional Commitments from Lattices
* Authors: Ben Fisch, Zeyu Liu, Psi Vesely
* [Permalink](https://eprint.iacr.org/2024/2026)
* [Download](https://eprint.iacr.org/2024/2026.pdf)

### Abstract

We present Orbweaver, a plausibly post-quantum functional commitment for linear relations that achieves quasilinear prover time together with $O(\log n)$ proof size and polylogarithmic verifier time. Orbweaver enables evaluation of linear functions on committed vectors over cyclotomic rings and the integers.. It is extractable, preprocessing, non-interactive, structure-preserving, and supports compact public proof aggregation. The security of our scheme is based on the $k$-$R$-ISIS assumption (and its knowledge counterpart), whereby we require a trusted setup to generate a universal structured reference string.. We use Orbweaver to construct succinct univariate and multilinear polynomial commitments.

     Concretely, our scheme has smaller proofs than most other succinct post-quantum arguments for large statements. For binary vectors of length $2^{30}$ we achieve $302$KiB linear map evaluation proofs with evaluation binding, and $1$MiB proofs when extractability is required; for $32$-bit integers these sizes are $494$KiB and $1.6$MiB, respectively.



## 2024/2027

* Title: Impact Tracing: Identifying the Culprit of  Misinformation in Encrypted Messaging Systems
* Authors: Zhongming Wang, Tao Xiang, Xiaoguo Li, Biwen Chen, Guomin Yang, Chuan Ma, Robert H. Deng
* [Permalink](https://eprint.iacr.org/2024/2027)
* [Download](https://eprint.iacr.org/2024/2027.pdf)

### Abstract

Encrypted messaging systems obstruct content moderation, although they provide end-to-end security. As a result, misinformation proliferates in these systems, thereby exacerbating online hate and harassment. The paradigm of ``Reporting-then-Tracing" shows great potential in mitigating the spread of misinformation. For instance, message traceback (CCS'19) traces all the dissemination paths of a message, while source tracing (CCS'21) traces its originator. However, message traceback lacks privacy preservation for non-influential users (e.g., users who only receive the message once), while source tracing maintains privacy but only provides limited traceability.

In this paper, we initiate the study of impact tracing. Intuitively, impact tracing traces influential spreaders central to disseminating misinformation while providing privacy protection for non-influential users. We introduce noises to hide non-influential users and demonstrate that these noises do not hinder the identification of influential spreaders. Then, we formally prove our scheme's security and show it achieves differential privacy protection for non-influential users. Additionally, we define three metrics to evaluate its traceability, correctness, and privacy using real-world datasets. The experimental results show that our scheme identifies the most influential spreaders with accuracy from 82% to 99% as the amount of noise varies. Meanwhile, our scheme requires only a 6-byte platform storage overhead for each message while maintaining a low messaging latency (< 0.25ms).



## 2024/2028

* Title: Qubit Optimized Quantum Implementation of SLIM
* Authors: Hasan Ozgur Cildiroglu, Oguz Yayla
* [Permalink](https://eprint.iacr.org/2024/2028)
* [Download](https://eprint.iacr.org/2024/2028.pdf)

### Abstract

The advent of quantum computing has profound implications for current technologies, offering advancements in optimization while posing significant threats to cryptographic algorithms. Public-key cryptosystems relying on prime factorization or discrete logarithms are particularly vulnerable, whereas block ciphers (BCs) remain secure through increased key lengths. In this study, we introduce a novel quantum implementation of SLIM, a lightweight block cipher optimized for 32-bit plaintext and an 80-bit key, based on a Feistel structure. This implementation distinguishes itself from other BC quantum implementations in its class (64–128-bit) by utilizing a minimal number of qubits while maintaining robust cryptographic strength and efficiency. By employing an innovative design that minimizes qubit usage, this work highlights SLIM’s potential as a resource-efficient and secure candidate for quantum-resistant encryption protocols.



## 2024/2029

* Title: NLAT: the NonLinear Distribution Table of Vectorial Boolean Mappings
* Authors: Jorge Nakahara Jr
* [Permalink](https://eprint.iacr.org/2024/2029)
* [Download](https://eprint.iacr.org/2024/2029.pdf)

### Abstract

This paper studies an extension of the Linear Approximation Table (LAT) of vectorial Boolean mappings (also known as Substitution boxes) used in Linear Cryptanalysis (LC). This extended table is called NonLinear Approximation Table (NLAT).



## 2024/2030

* Title: Security Analysis of ASCON Cipher under Persistent Faults
* Authors: Madhurima Das, Bodhisatwa Mazumdar
* [Permalink](https://eprint.iacr.org/2024/2030)
* [Download](https://eprint.iacr.org/2024/2030.pdf)

### Abstract

This work investigates persistent fault analysis on ASCON
cipher that has been recently standardized by NIST USA for lightweight
cryptography applications. In persistent fault, the fault once injected
through RowHammer injection techniques, exists in the system during
the entire encryption phase. In this work, we propose a model to mount
persistent fault analysis (PFA) on ASCON cipher. In the finalization
round of the ASCON cipher, we identify that the fault-injected S-Box
operation in the permutation round, $p^{12}$, is vulnerable to leaking infor-
mation about the secret key. The model can exist in two variants, a single
instance of fault-injected S-Box out of 64 parallel S-Box invocations, and
the same faulty S-Box iterated 64 times. The attack model demonstrates
that any Spongent construction operating with authenticated encryption
with associated data (AEAD) mode is vulnerable to persistent faults. In
this work, we demonstrate the scenario of a single fault wherein the fault,
once injected is persistent until the device is powered off. Using the pro-
posed method, we successfully retrieve the 128-bit key in ASCON. Our
experiments show that the minimum number and the maximum num-
ber of queries required are 63 plaintexts and 451 plaintexts, respectively.
Moreover, we observe that the number of queries required to mount the
attack depends on fault location in the S-box LUT as observed from the
plots reporting the minimum number of queries and average number of
queries for 100 key values.