[continued from previous message]

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).

--- SoupGate-Win32 v1.05
* Origin: fsxNet Usenet Gateway (21:1/5)