[digest] 2025 Week 27

## In this issue

1. [2023/1524] SoK: Signatures With Randomizable Keys
2. [2025/372] KLPT²: Algebraic Pathfinding in Dimension Two and ...
3. [2025/1194] Private coins extension with verifiable encryption
4. [2025/1195] On symbolic computations and Post Quantum ...
5. [2025/1196] Limits on the Power of Private Constrained PRFs
6. [2025/1197] How to Copy-Protect All Puncturable Functionalities ...
7. [2025/1198] Brief Comments on Rijndael-256 and the Standard ...
8. [2025/1199] HypSCA: A Hyperbolic Embedding Method for Enhanced ...
9. [2025/1200] Tricycle: Private Transformer Inference with ...
10. [2025/1201] BitBatSPIR: Efficient Batch Symmetric Private ...
11. [2025/1202] t-Probing (In-)Security - Pitfalls on Noise Assumptions
12. [2025/1203] Breaking The Authenticated Encryption scheme HiAE
13. [2025/1204] A search to distinguish reduction for the ...
14. [2025/1205] Generic Construction of Threshold Ring Signatures ...
15. [2025/1206] New Upper and Lower Bounds for Perfectly Secure MPC
16. [2025/1207] Copy-Protection from UPO, Revisited
17. [2025/1208] End-to-End Encrypted Git Services
18. [2025/1209] RingSG: Optimal Secure Vertex-Centric Computation ...
19. [2025/1210] A Generalized Approach to Root-based Attacks ...
20. [2025/1211] May the Force $\textit{not}$ Be with you: Brute- ...
21. [2025/1212] All Proof of Work But No Proof of Play
22. [2025/1213] Tightly Secure Public-Key Encryption with Equality ...
23. [2025/1214] Hobbit: Space-Efficient zkSNARK with Optimal Prover ...
24. [2025/1215] Highly Scalable Searchable Symmetric Encryption for ...
25. [2025/1216] Ring-LWR based Commitments and ZK-PoKs with ...

## 2023/1524

* Title: SoK: Signatures With Randomizable Keys
* Authors: Sofía Celi, Scott Griffy, Lucjan Hanzlik, Octavio Perez Kempner, Daniel Slamanig
* [Permalink](https://eprint.iacr.org/2023/1524)
* [Download](https://eprint.iacr.org/2023/1524.pdf)

### Abstract

Digital signature schemes with specific properties have recently seen various real-world applications with a strong emphasis on privacy-enhancing technologies. They have been extensively used to develop anonymous credentials schemes and to achieve an even more comprehensive range of functionalities in the decentralized web.

Substantial work has been done to formalize different types of signatures where an allowable set of transformations can be applied to message-signature pairs to obtain new related pairs. Most of the previous work focused on transformations with respect to the message being signed, but little has been done to study what happens when transformations apply to the signing keys. A first attempt to thoroughly formalize such aspects was carried by Derler and Slamanig (ePrint'16, Designs, Codes and Cryptography'19), followed by the more recent efforts by Backes et al. (ASIACRYPT'18) and Eaton et al. (ePrint'23). However, the literature on the topic is vast and different terminology is used across contributions, which makes it difficult to compare related works and understand the range of applications covered by a given construction.

In this work, we present a unified view of signatures with randomizable keys and revisit their security properties. We focus on state-of-the-art constructions and related applications,identifying existing challenges. Our systematization allows us to highlight gaps, open questions and directions for future research on signatures with randomizable keys.



## 2025/372

* Title: KLPT²: Algebraic Pathfinding in Dimension Two and Applications
* Authors: Wouter Castryck, Thomas Decru, Péter Kutas, Abel Laval, Christophe Petit, Yan Bo Ti
* [Permalink](https://eprint.iacr.org/2025/372)
* [Download](https://eprint.iacr.org/2025/372.pdf)

### Abstract

Following Ibukiyama, Katsura and Oort, all  principally polarized superspecial abelian surfaces over $\overline{\mathbb{F}}_p$ can be represented by a certain type of $2 \times 2$ matrix $g$, having entries in the quaternion algebra $B_{p,\infty}$. We present a heuristic polynomial-time algorithm which, upon input of two such matrices $g_1, g_2$, finds a "connecting matrix" representing a polarized isogeny of smooth degree between the corresponding surfaces. Our algorithm should be thought of as a two-dimensional analog of the KLPT algorithm from 2014 due to Kohel, Lauter, Petit and Tignol for finding a connecting ideal of smooth norm between two given maximal orders in $B_{p, \infty}$.
 
The KLPT algorithm has proven to be a versatile tool in isogeny-based cryptography, and our analog has similar applications; we discuss two of them in detail. First, we show that it yields a polynomial-time solution to a two-dimensional analog of the so-called constructive Deuring correspondence: given a matrix $g$ representing a superspecial principally polarized abelian surface, realize the latter as the Jacobian of a genus-$2$ curve (or, exceptionally, as the product of two elliptic curves if it concerns a product polarization). Second, we show that, modulo a plausible assumption, Charles-Goren-Lauter style hash functions from superspecial principally polarized abelian surfaces require a trusted set-up. Concretely, if the matrix $g$ associated with the starting surface is known then collisions can be produced in polynomial time. We deem it plausible that all currently known methods for generating a starting surface indeed reveal the corresponding matrix. As an auxiliary tool, we present an efficient method for converting polarized isogenies of powersmooth degree into the corresponding connecting matrix, a step for which a previous approach by Chu required super-polynomial (but sub-exponential) time.



## 2025/1194

* Title: Private coins extension with verifiable encryption
* Authors: Oleg Fomenko
* [Permalink](https://eprint.iacr.org/2025/1194)
* [Download](https://eprint.iacr.org/2025/1194.pdf)

### Abstract

This paper introduces a protocol for verifiable encryption of values committed using Pedersen commitments. It enables a recipient to decrypt the hidden amount while proving its consistency with the original commitment, without revealing the value publicly. The construction combines symmetric encryption with zero-knowledge proofs and is made non-interactive via the Fiat-Shamir heuristic. The protocol is particularly useful in blockchain settings where confidential but verifiable value transfers are required.



## 2025/1195

* Title: On symbolic computations and Post Quantum Cryptography with Lie Geometries.
* Authors: Vasyl Ustimenko
* [Permalink](https://eprint.iacr.org/2025/1195)
* [Download](https://eprint.iacr.org/2025/1195.pdf)

### Abstract

Assume that the global density of multivariate map  over the commutative ring is the total number of its coefficients. In the case of finite commutative ring K with the multiplicative group  K* containing more than 2 elements we suggest multivariate public keys in n variables with the public rule of global density O(n) and degree O(1). Another public keys  use public rule of global density O(n) and degree O(n) together with the space of plaintexts (K*)^n and the space of ciphertext K^n . We consider examples of protocols of Noncommutative Cryptography implemented on the platform of  endomorphisms of which allow the con-version of mentioned above multivariate public keys into protocol based cryptosystems of El Gamal type. The cryptosystems and protocols are designed in terms of analogue of geometries of Chevalley groups over commutative rings  and their temporal versions.



## 2025/1196

* Title: Limits on the Power of Private Constrained PRFs
* Authors: Mengda Bi, Chenxin Dai, Yaohua Ma
* [Permalink](https://eprint.iacr.org/2025/1196)
* [Download](https://eprint.iacr.org/2025/1196.pdf)

### Abstract

Private constrained PRFs are constrained PRFs where the constrained key hides information about the predicate circuit. Although there are many constructions and applications of PCPRF, its relationship to basic cryptographic primitives, such as one-way functions and public-key encryptions, has been unclear. For example, we don't know whether one-way functions imply PCPRFs for general predicates, nor do we know whether 1-key secure PCPRF for all polynomial-sized predicates imply public-key primitives such as public-key encryption and secret-key agreement.
   
    In this work, we prove the black-box separation between a 1-key secure PCPRF for any predicate and a secret-key agreement, which is the first black-box separation result about PCPRF. Specifically, we prove that there exists an oracle relative to which 1-key secure PCPRFs exist while secret-key agreement does not. Our proof is based on the simulation-based technique proposed by Impagliazzo and Rudich (STOC 89). The main technical challenge in generalizing the simulation-based technique to PCPRF is the issue of \textit{unfaithfulness} of Eve's simulation to the real world because our oracle is more complicated than a random oracle. We introduce a new technique which we call the ``weighting" technique and show how to leverage it to circumvent the issue of unfaithfulness in the proof framework of Impagliazzo and Rudich.



## 2025/1197

* Title: How to Copy-Protect All Puncturable Functionalities Without Conjectures: A Unified Solution to Quantum Protection
* Authors: Alper Çakan, Vipul Goyal
* [Permalink](https://eprint.iacr.org/2025/1197)
* [Download](https://eprint.iacr.org/2025/1197.pdf)

### Abstract

Quantum copy-protection (Aaronson, CCC'09) is the problem of encoding a functionality/key into a quantum state to achieve an anti-piracy security notion that guarantees that the key cannot be split into two keys that both still work. Most works so far has focused on constructing copy-protection for specific functionalities. The only exceptions are the work of Aaronson, Liu, Liu, Zhandry, Zhang (CRYPTO'21) and Ananth and Behera (CRYPTO'24). The former constructs copy-protection for all functionalities in the classical oracle model and the latter constructs copy-protection for all circuits that can be punctured at a uniformly random point with negligible security, assuming a new unproven conjecture about simultaneous extraction from entangled quantum adversaries, on top of assuming subexponentially-secure indistinguishability obfuscation (iO) and hardness of Learning with Errors (LWE).

In this work, we show that the construction of Aaronson et al (CRYPTO'21), when the oracles are instantiated with iO, satisfies copy-protection security in the plain model for all cryptographically puncturable functionalities (instead of only puncturable circuits) with arbitrary success threshold (e.g. we get CPA-style security rather than unpredictability for encryption schemes), without any unproven conjectures, assuming only subexponentially secure iO and one-way functions (we do not assume LWE). Thus, our work resolves the five-year-old open question of Aaronson et al, and further, our work encompasses/supersedes and significantly improves upon all existing plain-model copy-protection results.

Since puncturability has a long history of being studied in cryptography, our result immediately allows us to obtain copy-protection schemes for a large set of advanced functionalities for which no previous copy-protection scheme existed. Further, even for any functionality F that has not already been considered, through our result, constructing copy-protection for F essentially becomes a classical cryptographer's problem.

Going further, we show that our scheme also satisfies secure leasing (Ananth and La Placa, EUROCRYPT'21), unbounded/LOCC leakage-resilience and intrusion-detection security (Cakan, Goyal, Liu-Zhang, Ribeiro, TCC'24), giving a unified solution to the problem of quantum protection.



## 2025/1198

* Title: Brief Comments on Rijndael-256 and the Standard RISC-V Cryptography Extensions
* Authors: Markku-Juhani O. Saarinen
* [Permalink](https://eprint.iacr.org/2025/1198)
* [Download](https://eprint.iacr.org/2025/1198.pdf)

### Abstract

We evaluate the implementation aspects of Rijndael-256 using the ratified  RISC-V Vector Cryptography extension Zvkn. A positive finding is that Rijndael-256 can be implemented in constant time with the existing RISC-V ISA as the critical AES and fixed crossbar permutation instructions are in the DIEL (data-independent execution latency) set. Furthermore, simple tricks can be used to expand the functionality of key expansion instructions to cover the additional round constants required. However, due to the required additional byte shuffle in each round, Rijndael-256 will be significantly slower than AES-256 in terms of throughput. Without additional ISA modifications, the instruction count will be increased by the required switching of the  EEW (``effective element width'') parameter in each round between 8 bits (byte shuffle) and 32 bits (AES round instructions). Instruction counts for 1-kilobyte encryption and decryption with Rijndael-256 are factor $2.66\times$ higher than with AES-256. The precise amount of throughput slowdown depends on the microarchitectural details of a particular RISC-V ISA hardware instantiation, but it may be substantial with some high-performance vector AES architectures due to the breakdown of AES pipelining and the relative slowness of crossbar permutation instructions.



## 2025/1199

* Title: HypSCA: A Hyperbolic Embedding Method for Enhanced Side-channel Attack
* Authors: Kaibin Li, Yihuai Liang, Zhengchun Zhou, Shui Yu
* [Permalink](https://eprint.iacr.org/2025/1199)
* [Download](https://eprint.iacr.org/2025/1199.pdf)

### Abstract

Deep learning-based side-channel attack (DLSCA) has become the dominant paradigm for extracting sensitive information from hardware implementations due to its ability to learn discriminative features directly from raw side-channel traces. A common design choice in DLSCA involves embedding traces in Euclidean space, where the underlying geometry supports conventional objectives such as classification or contrastive learning. However, Euclidean space is fundamentally limited in capturing the multi-level hierarchical structure of side-channel traces, which often exhibit both coarse-grained clustering patterns (e..g., Hamming weight similarities) and fine-grained distinctions (e.g., instruction-level variations). These limitations adversely affect the discriminability and generalization of learned representations, particularly across diverse datasets and leakage models. In this work, we propose HypSCA, a dual-space representation learning method that embeds traces in hyperbolic space to exploit its natural ability to model hierarchical relationships through exponential volume growth. In contrast to existing approaches, HypSCA jointly combines hyperbolic structure modeling with local discriminative learning in Euclidean space, enabling the preservation of global hierarchies while enhancing fine-grained feature separation. Extensive experiments on multiple public datasets demonstrate that HypSCA achieves up to 51.6% improvement in attack performance over state-of-the-art DLSCA methods, consistently enhancing generalization across diverse datasets and leakage models.



## 2025/1200

* Title: Tricycle: Private Transformer Inference with Tricyclic Encodings
* Authors: Lawrence Lim, Vikas Kalagi, Divyakant Agrawal, Amr El Abbadi
* [Permalink](https://eprint.iacr.org/2025/1200)
* [Download](https://eprint.iacr.org/2025/1200.pdf)

### Abstract

The growing adoption of Large Language Models in privacy-sensitive domains necessitates secure inference mechanisms that preserve data confidentiality. Homomorphic encryption offers a promising pathway by enabling computation on encrypted inputs, yet existing approaches struggle to scale efficiently to full transformer models due to limitations in packing schemes, which must efficiently support a wide range of operations, including matrix multiplications, row-wise nonlinear operations, and self-attention. In this work, we present Tricycle, a framework for private transformer inference built on our novel packing scheme, called tricyclic encodings, which are designed to efficiently support these core operations. Tricyclic encodings are a generalization of bicyclic encodings, enabling privacy-preserving batch matrix multiplications with optimal multiplicative depth in order to facilitate parallelized multi-head self-attention. We optimize our matrix multiplications by incorporating Baby-Step Giant-Step optimizations to reduce ciphertext rotations and presenting new ciphertext-plaintext matrix multiplication techniques that relax prior limitations. A further contribution of our work is a lightweight and effective approach for stabilizing the softmax function via statistical max estimation. Our end-to-end implementation on a BERT-Tiny model shows that Tricycle achieves a \(1.5 \times\) to \(3 \times\) speedup over previous approaches, marking a step toward practical and scalable private LLM inference without sacrificing model fidelity.



## 2025/1201

* Title: BitBatSPIR: Efficient Batch Symmetric Private Information Retrieval from PSI
* Authors: Shuaishuai Li, Liqiang Peng, Weiran Liu, Cong Zhang, Zhen Gu, Dongdai Lin
* [Permalink](https://eprint.iacr.org/2025/1201)
* [Download](https://eprint.iacr.org/2025/1201.pdf)

### Abstract

Private Information Retrieval (PIR) allows a client to retrieve an entry from a database held by a server without leaking which entry is being requested. Symmetric PIR (SPIR) is a stronger variant of PIR with database privacy so that the client knows nothing about the database other than the retrieved entry.

This work studies SPIR in the batch setting (BatchSPIR), where the client wants to retrieve multiple entries. In particular, we focus on the case of bit entries, which has important real-world applications. We set up the connection between bit-entry information retrieval and set operation, and propose a black-box construction of BatchSPIR from Private Set Intersection (PSI). By applying an efficient PSI protocol with asymmetric set sizes, we obtain our BatchSPIR protocol named $\mathsf{BitBatSPIR}$. We also introduce several optimizations for the underlying PSI. These optimizations improve the efficiency of our concrete BatchSPIR construction as well as the PSI protocol.

We implement $\mathsf{BitBatSPIR}$ and compare the performance with the state-of-the-art PIR protocol in the batch setting. Our experimental results show that $\mathsf{BitBatSPIR}$ not only achieves a stronger security guarantee (symmetric privacy) but also has a better performance for large databases, especially in the Wide Area Network (WAN) setting.



## 2025/1202

* Title: t-Probing (In-)Security - Pitfalls on Noise Assumptions
* Authors: Dina Hesse, Jakob Feldtkeller, Tim Güneysu, Julius Hermelink, Georg Land, Markus Krausz, Jan Richter-Brockmann
* [Permalink](https://eprint.iacr.org/2025/1202)
* [Download](https://eprint.iacr.org/2025/1202.pdf)

### Abstract

The ongoing transition to post-quantum cryptography has led to a surge of research in side-channel countermeasures tailored to these schemes. A prominent method to prove security in the context of side-channel analysis is the utilization of the well-established t-probing model. However, recent studies by Hermelink et al. at CCS 2024 demonstrate a simple and practical attack on a provably secure implementation of the Fujisaki-Okamoto transform that raises concerns regarding the practical security of t-probing secure schemes.

In this paper, we present an unsupervised single-trace side-channel attack on a tenth order  masked implementation of fixed-weight polynomial sampling, which has also been proven to be secure in the t-probing model.  Both attacks reveal a mismatch between the correct, well-understood theory of the t-probing model and its practical application, since the security proofs are valid, yet the attacks still succeed at high noise levels.  Therefore, we take a closer look at the underlying causes and the assumptions that are made for transferring t-probing security to practice. In particular, we investigate the amount of noise required for this transfer. We find that, depending on the design decisions made, this can be very high and difficult to achieve.

Consequently, we examine the factors impacting the required amount of noise and that should be considered for practically secure implementations.  In particular, non-uniformly distributed shares - a setting that is increasingly encountered in post-quantum cryptographic algorithms - could lead to an increased noise requirement, and thus it could reduce the security level of the masking scheme.  Our analysis then allows us to provide practical guidelines for implementation designers, thereby facilitating the development of practically secure designs.



## 2025/1203

* Title: Breaking The Authenticated Encryption scheme HiAE
* Authors: Xichao Hu, Lin Jiao, Dengguo Feng, Yonglin Hao, Senpeng Wang, Yongqiang Li, Xinxin Gong
* [Permalink](https://eprint.iacr.org/2025/1203)
* [Download](https://eprint.iacr.org/2025/1203.pdf)

### Abstract

HiAE is the fastest AEAD solution on ARM chips to date, utilizing AES round functions while also setting a new performance benchmark on the latest x86 processors. In this paper, we employ algebraic techniques to investigate the security of HiAE. Our findings reveal that HiAE is vulnerable. Firstly, we employ the meet-in-the-middle technique and guess-and-determine technique to recover the state and derive a key-related equation resulting from two layers of AES round functions. Secondly, by adopting an algebraic approach to study the properties of the round function, we decompose the equation into byte-level equations for divide-and-conquer. Finally, we utilize the guess-and-determine technique to recover the key. Collectively, these techniques enable us to present the first full key-recovery attack on HiAE. Our attack achieves a data complexity of $2^{130}$ and a time complexity of approximately $2^{209}$, leveraging both encryption and decryption oracles with a success probability of 1.. In a single-key and nonce-respecting scenario, the attack fully recovers the 256-bit key, breaking the claimed 256-bit security against key-recovery attacks.



## 2025/1204

* Title: A search to distinguish reduction for the isomorphism problem on direct sum lattices
* Authors: Daniël van Gent, Wessel van Woerden
* [Permalink](https://eprint.iacr.org/2025/1204)
* [Download](https://eprint.iacr.org/2025/1204.pdf)

### Abstract

At Eurocrypt 2003, Szydlo presented a search to distinguish reduction for the Lattice Isomorphism Problem (LIP) on the integer lattice $\mathbb{Z}^n$. Here the search problem asks to find an isometry between $\mathbb{Z}^n$ and an isomorphic lattice, while the distinguish variant asks to distinguish between a list of auxiliary lattices related to $\mathbb{Z}^n$.

In this work we generalize Szydlo's search to distinguish reduction in two ways. Firstly, we generalize the reduction to any lattice isomorphic to $\Gamma^n$, where $\Gamma$ is a fixed base lattice. Secondly, we allow $\Gamma$ to be a module lattice over any number field. Assuming the base lattice $\Gamma$ and the number field $K$ are fixed, our reduction is polynomial in $n$.

As a special case we consider the module lattice $\mathcal{O}_K^2$ used in the module-LIP based signature scheme HAWK, and we show that one can solve the search problem, leading to a full key recovery, with less than $2d^2$ distinguishing calls on two lattices each, where $d$ is the degree of the power-of-two cyclotomic number field and $\mathcal{O}_K$  its ring of integers.



## 2025/1205

* Title: Generic Construction of Threshold Ring Signatures and Lattice-based Instantiations
* Authors: Hao Lin, Mingqiang Wang, Weiqiang Wen, Shi-Feng Sun, Kaitai Liang
* [Permalink](https://eprint.iacr.org/2025/1205)
* [Download](https://eprint.iacr.org/2025/1205.pdf)

### Abstract

A t-out-of-n threshold ring signature allows $t$ parties to jointly sign a message on behalf of $n$ parties without revealing the identities of the signers. In this paper, we introduce a new generic construction for threshold ring signature, called GCTRS, which can be built on top of a selection on identification schemes, commitment schemes and a new primitive called t-out-of-n proof protocol which is a special type of zero-knowledge proof. In general, our design enables a group of $t$ signers to first generate an aggregated signature by interacting with each other; then they are able to compute a t-out-of-n proof to convince the verifier that the aggregated signature is indeed produced by $t$ individuals among a particular set. The signature is succinct, as it contains only one aggregated signature and one proof in the final signature.. We define all the properties required for the building blocks to capture the security of the GCTRS and provide a detailed security proof. Furthermore, we propose two lattice-based instantiations for the GCTRS, named LTRS and CTRS, respectively. Notably, the CTRS scheme is the first scheme that has a logarithmic signature size relative to the ring size. Additionally, during the instantiation process, we construct two t-out-of-n proof protocols, which may be of independent interest.



## 2025/1206

* Title: New Upper and Lower Bounds for Perfectly Secure MPC
* Authors: Ivan Damgård, Shravani Patil, Arpita Patra, Lawrence Roy
* [Permalink](https://eprint.iacr.org/2025/1206)
* [Download](https://eprint.iacr.org/2025/1206.pdf)

### Abstract

We consider perfectly secure MPC for $n$ players and $t$ malicious corruptions. We ask whether requiring only security with abort (rather than guaranteed output delivery, GOD) can help to achieve protocols with better resilience, communication complexity or round complexity. We show that for resilience and communication complexity, abort security does not help, one still needs $3t< n$ for a synchronous network and $4t< n$ in the asynchronous case. And, in both cases, a communication overhead of $O(n)$ bits per gate is necessary.

When $O(n)$ overhead is inevitable, one can explore if this overhead can be pushed to the preprocessing phase and the online phase can be achieved with $O(1)$ overhead. This result was recently achieved in the synchronous setting, in fact, with GOD guarantee. We show this same result in the asynchronous setting. This was previously open since the main standard approach to getting constant overhead in a synchronous on-line phase fails in the asynchronous setting. In particular, this shows that we do not need to settle for abort security to get an asynchronous perfectly secure protocol with overheads $O(n)$ and $O(1)$.

Lastly, in the synchronous setting, we show that perfect secure MPC with abort requires only 2 rounds, in contrast to protocols with GOD that require 4 rounds.



## 2025/1207

* Title: Copy-Protection from UPO, Revisited
* Authors: Prabhanjan Ananth, Amit Behera, Zikuan Huang
* [Permalink](https://eprint.iacr.org/2025/1207)
* [Download](https://eprint.iacr.org/2025/1207.pdf)

### Abstract

Quantum copy-protection is a foundational notion in quantum cryptography that leverages the governing principles of quantum mechanics to tackle the problem of software anti-piracy. Despite progress in recent years, precisely characterizing the class of functionalities that can be copy-protected is still not well understood.
Two recent works, by [Coladangelo and Gunn, STOC 2024] and [Ananth and Behera, CRYPTO 2024, showed that puncturable functionalities can be copy-protected. Both works have significant caveats with regard to the underlying cryptographic assumptions and additionally restrict the output length of the functionalities to be copy-protected. In this work, we make progress towards simultaneously addressing both caveats. We show the following:
- Revisiting Unclonable Puncturable Obfuscation (UPO): We revisit the notion of UPO introduced by [Ananth and Behera, CRYPTO 2024]. We present a new approach to construct UPO and a variant of UPO, called independent-secure UPO. Unlike UPO, we show how to base the latter notion on well-studied assumptions.
- Copy-Protection from Independent-secure UPO: Assuming independent-secure UPO, we show that any m-bit, for m ≥ 2, puncturable functionality can be copy-protected.
- Copy-Protection from UPO: Assuming UPO, we show that any 1-bit puncturable functionality can be copy-protected. The security of copy-protection holds against identical challenge distributions.



## 2025/1208

* Title: End-to-End Encrypted Git Services
* Authors: Ya-Nan Li, Yaqing Song, Qiang Tang, Moti Yung
* [Permalink](https://eprint.iacr.org/2025/1208)
* [Download](https://eprint.iacr.org/2025/1208.pdf)

### Abstract

Git services such as GitHub, have been widely used to manage projects and enable collaborations among multiple entities. Just as in messaging and cloud storage, where end-to-end security has been gaining increased attention, such a level of security is also demanded for Git services. Content in the repositories (and the data/code supply-chain facilitated by Git services) could be highly valuable, whereas the threat of system breaches has become routine nowadays. However, existing studies of Git security to date (mostly open source projects) suffer in two ways: they provide only very weak security, and they have a large overhead.

In this paper, we initiate the needed study of efficient end-to-end encrypted Git services. Specifically, we formally define the syntax and critical security properties, and then propose two constructions that provably meet those properties. Moreover, our constructions have the important property of platform-compatibility: They are compatible with current Git servers and reserve all basic Git operations, thus can be directly tested and deployed on top of existing platforms. Furthermore, the overhead we achieve is only proportional to the actual difference caused by each edit, instead of the whole file (or even the whole repository) as is the case with existing works. We implemented both constructions and tested them directly on several public GitHub repositories. Our evaluations show (1) the effectiveness of platform-compatibility, and (2) the significant efficiency improvement we got (while provably providing much stronger security than prior ad-hoc treatments).



## 2025/1209

* Title: RingSG: Optimal Secure Vertex-Centric Computation for Collaborative Graph Processing
* Authors: Zhenhua Zou, Zhuotao Liu, Jinyong Shan, Qi Li, Ke Xu, Mingwei Xu
* [Permalink](https://eprint.iacr.org/2025/1209)
* [Download](https://eprint.iacr.org/2025/1209.pdf)

### Abstract

Collaborative graph processing refers to the joint analysis of inter-connected graphs held by multiple graph owners. To honor data privacy and support various graph processing algorithms, existing approaches employ secure multi-party computation (MPC) protocols to express the vertex-centric abstraction. Yet, due to certain computation-intensive cryptography constructions, state-of-the-art (SOTA) approaches are asymptotically suboptimal, imposing significant overheads in terms of computation and communication. In this paper, we present RingSG, the first system to attain optimal communication/computation complexity within the MPC-based vertex-centric abstraction for collaborative graph processing. This optimal complexity is attributed to Ring-ScatterGather, a novel computation paradigm that can avoid exceedingly expensive cryptography operations (e.g., oblivious sort), and simultaneously ensure the overall workload can be optimally decomposed into parallelizable and mutually exclusive MPC tasks. Within Ring-ScatterGather, RingSG improves the concrete runtime efficiency by incorporating 3-party secure computation via share conversion, and optimizing the most cost-heavy part using a novel oblivious group aggregation protocol. Finally, unlike prior approaches, we instantiate RingSG into two end-to-end applications to effectively obtain application-specific results from the protocol outputs in a privacy-preserving manner. We developed a prototype of RingSG and extensively evaluated it across various graph collaboration settings, including different graph sizes, numbers of parties, and average vertex degrees. The results show RingSG reduces the system running time of SOTA approaches by up to 15.34× and per-party communication by up to 10.36×. Notably, RingSG excels in processing sparse global graphs collectively held by more parties, consistent with our theoretical cost analysis.



## 2025/1210

* Title: A Generalized Approach to Root-based Attacks against PLWE
* Authors: Iván Blanco Chacón, Raúl Durán Díaz, Rodrigo Martín Sanchez-Ledesma
* [Permalink](https://eprint.iacr.org/2025/1210)
* [Download](https://eprint.iacr.org/2025/1210.pdf)

### Abstract

The Polynomial Learning With Errors problem (PLWE) serves as the background of two of the three cryptosystems standardized in August 2024 by the National Institute of Standards and Technology to replace non-quantum resistant current primitives like those based on RSA, Diffie-Hellman or its elliptic curve analogue. Although PLWE is highly believed to be quantum resistant, this fact has not yet been established, contrariwise to other post-quantum proposals like multivariate and some code based ones. Moreover, several vulnerabilities have been encountered for a number of specific instances. In a search for more flexibility, it becomes fully relevant to study the robustness of PLWE based on other polynomials, not necessarily cyclotomic. In 2015, Elias et al found a good number of attacks based on different features of the roots of the polynomial. In the present work we present an overview of the approximations made against PLWE derived from this and subsequent works, along with several new attacks which refine those by Elias et al. exploiting the order of the trace of roots over finite extensions of the finite field under the three scenarios laid out by Elias et al., allowing to generalize the setting in which the attacks can be carried out.



## 2025/1211

* Title: May the Force $\textit{not}$ Be with you: Brute-Force Resistant Biometric Authentication and Key Reconstruction
* Authors: Alexandra Boldyreva, Deep Inder Mohan, Tianxin Tang
* [Permalink](https://eprint.iacr.org/2025/1211)
* [Download](https://eprint.iacr.org/2025/1211.pdf)

### Abstract

The use of biometric-based security protocols is on the steep rise. As
biometrics become more popular, we witness more attacks. For example, recent
BrutePrint/InfinityGauntlet attacks showed how to brute-force fingerprints
stored on an Android phone in about 40 minutes. The attacks are possible because biometrics, like passwords, do not have high entropy. But unlike passwords, brute-force attacks are much more damaging for biometrics, because one cannot easily change biometrics in case of compromise. In this work, we propose a novel provably secure Brute-Force Resistant Biometrics (BFRB) protocol for biometric-based authentication and key reconstruction that protects against brute-force attacks even when the server storing biometric-related data is compromised. Our protocol utilizes a verifiable partially oblivious pseudorandom function, an authenticated encryption scheme, a pseudorandom function, and a hash. We formally define security for a BFRB protocol and reduce the security of our protocol to the security of the building blocks. We implement the protocol and study its performance for the ND-0405 iris dataset.



## 2025/1212

* Title: All Proof of Work But No Proof of Play
* Authors: Hayder Tirmazi
* [Permalink](https://eprint.iacr.org/2025/1212)
* [Download](https://eprint.iacr.org/2025/1212.pdf)

### Abstract

Speedrunning is a competition that emerged from communities of early video
games such as Doom (1993). Speedrunners try to finish a game in minimal
time. Provably verifying the authenticity of submitted speedruns is an open
problem. Traditionally, best-effort speedrun verification is conducted by on-site
human observers, forensic audio analysis, or a rigorous mathematical analysis
of the game mechanics1. Such methods are tedious, fallible, and, perhaps worst
of all, not cryptographic. Motivated by naivety and the Dunning-Kruger effect,
we attempt to build a system that cryptographically proves the authenticity of
speedruns. This paper describes our attempted solutions and ways to circumvent
them. Through a narration of our failures, we attempt to demonstrate the difficulty
of authenticating live and interactive human input in untrusted environments, as
well as the limits of signature schemes, game integrity, and provable play.



## 2025/1213

* Title: Tightly Secure Public-Key Encryption with Equality Test Supporting Flexible Authorization in the Standard Model
* Authors: Yi-Fan Tseng, Yi-Jiin Lu, Tien-Lin Tsai, Zi-Yuan Liu
* [Permalink](https://eprint.iacr.org/2025/1213)
* [Download](https://eprint.iacr.org/2025/1213.pdf)

### Abstract

We introduce a novel Public Key Encryption with Equality Test supporting Flexible Authorization scheme offering User-Level, Ciphertext-Level, and User-Specific-Ciphertext-Level authorizations. Notably, our construction achieves security under the Decisional Diffie-Hellman assumption with a tight reduction, whereas the existing works are either not tightly secure or rely heavily on the random oracles. By relying solely on the standard DDH assumption, our scheme offers practical implementation without specialized cryptographic structures.



## 2025/1214

* Title: Hobbit: Space-Efficient zkSNARK with Optimal Prover Time
* Authors: Christodoulos Pappas, Dimitrios Papadopoulos
* [Permalink](https://eprint.iacr.org/2025/1214)
* [Download](https://eprint.iacr.org/2025/1214.pdf)

### Abstract

Zero-knowledge succinct non-interactive arguments (zkSNARKs) are notorious for their large prover space requirements, which almost prohibits their use for really large instances. Space-efficient zkSNARKs aim to address this by limiting the prover space usage, without critical sacrifices to its runtime. In this work, we introduce Hobbit, the only existing space-efficient zkSNARK that achieves optimal prover time $O(|C|)$ for an arithmetic circuit $C$. At the same time, Hobbit is the first transparent and plausibly post-quantum secure construction of its kind. Moreover, our experimental evaluation shows that Hobbit outperforms all prior general-purpose space-efficient zkSNARKs in the literature across four different applications (arbitrary arithmetic circuits,  inference of pruned Multi-Layer Perceptron,  batch AES128 evaluation, and select-and-aggregate SQL query) by $\times$8-$\times$$56$ in terms or prover time while requiring up to $\times$23 less total space.

At a technical level, we introduce two new building blocks that may be of independent interest: (i) the first sumcheck protocol for products of polynomials with optimal prover time in the streaming setting, and (ii) a novel multi-linear plausibly post-quantum polynomial commitment that outperforms all prior works in prover time (and can be tuned to work in a space-efficient manner). We build Hobbit by combining the above with a modified version of HyperPlonk, providing an explicit routine to stream access to the circuit evaluation.



## 2025/1215

* Title: Highly Scalable Searchable Symmetric Encryption for Boolean Queries from NTRU Lattice Trapdoors
* Authors: Debadrita Talapatra, Sikhar Patranabis, Debdeep Mukhopadhyay
* [Permalink](https://eprint.iacr.org/2025/1215)
* [Download](https://eprint.iacr.org/2025/1215.pdf)

### Abstract

Searchable symmetric encryption (SSE) enables query execution directly over sym-
metrically encrypted databases. To support realistic query executions over encrypted
document collections, one needs SSE schemes capable of supporting both conjunctive
and disjunctive keyword queries. Unfortunately, existing solutions are either practi-
cally inefficient (incur large storage overheads and/or high query processing latency)
or are quantum-unsafe.
In this paper, we present the first practically efficient SSE scheme with fast con-
junctive and disjunctive keyword searches, compact storage, and security based on the
(plausible) quantum-hardness of well-studied lattice-based assumptions. We present
NTRU-OQXT – a highly compact NTRU lattice-based conjunctive SSE scheme that
outperforms all existing conjunctive SSE schemes in terms of search latency. We then
present an extension of NTRU-OQXT that additionally supports disjunctive queries,
we call it NTRU-TWINSSE. Technically, both schemes rely on a novel oblivious search
protocol based on highly optimized Fast-Fourier trapdoor sampling algorithms over
NTRU lattices. While such techniques have been used to design other cryptographic
primitives (such as digital signatures), they have not been applied before in the context
of SSE.
We present prototype implementations of both schemes, and experimentally val-
idate their practical performance over a large real-world dataset. Our experiments
demonstrate that NTRU-OQXT achieves 2× faster conjunctive keyword searches as
compared to all other conjunctive SSE schemes (including the best quantum-unsafe
conjunctive SSE schemes), and substantially outperforms many of these schemes in
terms of storage requirements. These efficiency benefits also translate to NTRU-
TWINSSE, which is practically competitive with the best quantum-unsafe SSE schemes
capable of supporting both conjunctive and disjunctive queries.



## 2025/1216

* Title: Ring-LWR based Commitments and ZK-PoKs with Application to Verifiable Quantum-Safe Searchable Symmetric Encryption
* Authors: Debadrita Talapatra, Nimish Mishra, Debdeep Mukhopadhyay
* [Permalink](https://eprint.iacr.org/2025/1216)
* [Download](https://eprint.iacr.org/2025/1216.pdf)

### Abstract

Prior research on ensuring trust in delegated computation through lattice-based zero-knowledge proofs mostly rely on Learning-With-Errors (LWE) assumption.. In this work, we propose a zero-knowledge proof of knowledge using the Ring Learning with Rounding (RLWR) assumption for an interesting and useful class of statements: linear relations on polynomials. We begin by proposing, to the best of our knowledge, the first efficient commitment scheme in literature based on the hardness of RLWR assumption. We establish two properties on RLWR that aid in the construction of our commitments: (i) closure under addition with double rounding, and (ii) closure under multiplication with a short polynomial. Building upon our RLWR commitment scheme, we consequently design a RLWR based $\Sigma_2$ protocol for proving knowledge of a single committed message under linear relations with public polynomials.

As an use-case of our proposed $\Sigma_2$ protocol, we showcase a construction of a quantum-safe Searchable Symmetric Encryption (SSE) scheme by plugging a prior LWR based SSE scheme from (EuroS&P 2023) with our $\Sigma_2$ protocol.. Concretely, using our $\Sigma_2$ protocol for linear relations, we prove the correctness of an encrypted search result in a zero-knowledge manner. We implement our verifiable SSE framework and show that the overhead of an extra verification round is negligible ($0.0023$ seconds) and retains the asymptotic query execution time complexity of the original SSE scheme.

Our work establishes results on zero-knowledge proof systems that can be of independent interest. By shifting the setting from RLWE to RLWR, we gain significant (i) efficiency improvements in terms of communication complexity by $O(M)$ (since some prior works on RLWE require rejection sampling by a factor of $M$), as well as (ii) very short proof size ($8.4$ KB) and tighter parameters (since RLWR does not explicitly manipulate error polynomials like RLWE).