[continued from previous message]

* Title: TEEMS: A Trusted Execution Environment based Metadata-protected Messaging System
* Authors: Sajin Sasy, Aaron Johnson, Ian Goldberg
* [Permalink](https://eprint.iacr.org/2025/1102)
* [Download](https://eprint.iacr.org/2025/1102.pdf)

### Abstract

Ensuring privacy of online messaging remains a challenge. While the contents or data of online communications are often protected by end-to-end encryption, the metadata of communications are not. Metadata such as who is communicating with whom, how
much, and how often, are leaked by popular messaging systems today.

In the last four decades we have witnessed a rich literature of designs towards metadata-protecting communications systems (MPCS). While recent MPCS works often target metadata-protected messaging systems, no existing construction simultaneously attains
four desirable properties for messaging systems, namely (i) low latency, (ii) high throughput, (iii) horizontal scalability, and (iv) asynchronicity. Existing designs often capture disjoint subsets of these properties. For example, PIR-based approaches
achieve low latency and asynchronicity but have low throughput and lack horizontal scalability, mixnet-based approaches achieve high throughput and horizontal scalability but lack asynchronicity, and approaches based on trusted execution environments (
TEEs) achieve high throughput and asynchronicity but lack horizontal scalability.

In this work, we present TEEMS, the first MPCS designed for metadata-protected messaging that simultaneously achieves all four desirable properties. Our distributed TEE-based system uses an oblivious mailbox design to provide metadata-protected messaging.
TEEMS presents novel oblivious routing protocols that adapt prior work on oblivious distributed sorting. Moreover, we introduce the notion of ID and token channels to circumvent shortcomings of prior designs. We empirically demonstrate TEEMS' ability
to support $2^{20}$ clients engaged in metadata-protected conversations in under 1 s, with 205 cores, achieving an 18× improvement over prior work for latency and throughput, while supporting significantly better scalability and asynchronicity
properties.



## 2025/1103

* Title: Universally Composable Succinct Vector Commitments and Applications
* Authors: Ran Canetti, Megan Chen
* [Permalink](https://eprint.iacr.org/2025/1103)
* [Download](https://eprint.iacr.org/2025/1103.pdf)

### Abstract

We develop a toolbox for modular construction and analysis of succinct, non-interactive commitments and vector commitments in the random oracle model, while guaranteeing universally composable security. To demonstrate its power, we use the toolbox to
construct and analyze a modular variant of the Kilian-Micali ZK-SNARK. Along the way we also propose a new UC formulation of a global random oracle, that avoids a weakness in existing formulations and also enables expressing more nuanced, session-
specific abstractions. We hope that this toolbox will be useful for building secure applications in settings where both succinctness and non-interactivity are key.



## 2025/1104

* Title: Better GBFV Bootstrapping and Faster Encrypted Edit Distance Computation
* Authors: Robin Geelen, Frederik Vercauteren
* [Permalink](https://eprint.iacr.org/2025/1104)
* [Download](https://eprint.iacr.org/2025/1104.pdf)

### Abstract

We propose a new iterative method to convert a ciphertext from the Generalized BFV (GBFV) to the regular BFV scheme. In particular, our conversion starts from an encrypted plaintext that lives in a large cyclotomic ring modulo a small-norm polynomial $t(
x)$, and gradually changes the encoding to a smaller cyclotomic ring modulo a larger integer $p$. Previously, only a trivial conversion method was known, which did not change the underlying cyclotomic ring.

Using our improved conversion algorithm, we can bootstrap the GBFV scheme almost natively, in the sense that only a very small fraction of the operations is computed inside regular BFV. Specifically, we evaluate (an adapted version of) the slot-to-
coefficient transformation entirely in the GBFV scheme, whereas the previous best method used the BFV scheme for that transformation. This insight allows us to bootstrap either with less noise growth, or much faster than the state-of-the-art.

We implement our new bootstrapping in Microsoft SEAL. Our experiments show that, for the same remaining noise budget, our bootstrapping runs in only 800 ms when working with ciphertexts containing 1024 slots over $\mathbb{F}_{p}$ with $p = 2^{16}+1$.
This is $1.6\times$ faster than the state-of-the-art.

Finally, we use our improved GBFV bootstrapping in an application that computes an encrypted edit distance. Compared to the recent TFHE-based Leuvenshtein algorithm, our GBFV version is almost two orders of magnitude faster in the amortized sense.



## 2025/1105

* Title: Low-cost anonymous reputation update for IoT applications
* Authors: Alex Shafarenko
* [Permalink](https://eprint.iacr.org/2025/1105)
* [Download](https://eprint.iacr.org/2025/1105.pdf)

### Abstract

This paper presents a novel approach to zero-trust anonymous reputation update in crowd sensing IoT applications. We use a suite of cryptographic functions to achieve anonymity, including unlinkability of sensing reports to the principals that submit
them and to one another, while enabling the infrastructure to reliably quantify the degree of trust expressed as a reputation level. The protocol is low-cost for the anonymous participant due to the use of cheap standard algorithms: low-exponent modular
exponentia- tion and cryptographic hashing, which makes it quite suitable for IoT.



## 2025/1106

* Title: b4M: Holistic Benchmarking for MPC
* Authors: Karl W. Koch, Dragos Rotaru, Christian Rechberger
* [Permalink](https://eprint.iacr.org/2025/1106)
* [Download](https://eprint.iacr.org/2025/1106.pdf)

### Abstract

Secure Multi-Party Computation (MPC) is becoming more and more usable in practice. The practicality origins primarily from well-established general-purpose MPC frameworks, such as MP-SPDZ. However, to evaluate the practicality of an MPC program in the
envisioned environments, still many benchmarks need to be done. We identified three challenges in the context of performance evaluations within the MPC domain: first, the cumbersome process to holistically benchmark MPC programs; second, the difficulty
to find the best-possible MPC setting for a given task and envisioned environment; and third, to have consistent evaluations of the same task or problem area across projects and papers. In this work, we address the gap of tedious and complex benchmarking
of MPC. Related works so far mostly provide a comparison for certain programs with different engines.

To the best of our knowledge, for the first time the whole benchmarking pipeline is automated; provided by our open-sourced framework Holistic Benchmarking for MPC (b4M). b4M is easy to configure using TOML files, outputs ready-to-use graphs, and
provides even the MPC engine itself as own benchmark dimension. Furthermore it takes three relatively easy steps to add further engines: first, integrate engine-specific commands into b4M’s runner class; second, output performance metrics in b4M’s
format; third, provide a Docker container for the engine’s parties.

To showcase b4M, we provide an exemplary evaluation for the computation of the dot product and logistic regression using a real-world dataset. With this work, we move towards fully-automated evaluations of MPC programs, protocols, and engines, which
smoothens the setup process and viewing various trade-offs. Hence, b4M advances MPC development by improving the benchmarking usability aspect of it.



## 2025/1107

* Title: Early Stopping is Cheap
* Authors: Fatima Elsheimy, Simon Holmgaard Kamp, Julian Loss
* [Permalink](https://eprint.iacr.org/2025/1107)
* [Download](https://eprint.iacr.org/2025/1107.pdf)

### Abstract

Minimizing both the round and communication complexity of Byzantine agreement (BA) is fundamental question in distributed computing. A long line of works has focused on early-stopping deterministic protocols that can terminate within a number of
synchronous rounds that is proportional to $f$, where $f$ is the \emph{actual number} of corruptions in an execution, as opposed to an upper bound $t$. This can lead to major benefits when $f\ll t$. A very different style of randomized protocol has
focused on \emph{player replaceable} BA protocols with communication complexity linear in the number of parties $n$ and adaptive security, which rely on only a small and rotating subcommittee of parties to ever speak in the protocol. One downside of
existing player-replaceable protocols is that they require $O(r)$ rounds to terminate with overwhelming probability $1-2^r$.
For applications demanding high security guarantees, this can easily become the bottleneck of a player replaceable protocol. Motivated by this gap in the literature, we give the first protocol that is simultaneously player-replaceable \emph{and}
early stopping (with overwhelming probability). Let $1>\alpha>0$ and $1>\epsilon>0$ be constants and let $\lambda$ and $\kappa$ denote suitable security parameters. Our protocol is secure against up to $t<(1-\alpha)\cdot n/2$ adaptive Byzantine
corruptions and terminates in $(1+\epsilon)\cdot f$ many rounds with probability $1-2^\lambda$, given $f\leq t$ corruptions. Moreover, our protocol has constant expected round complexity and communication bounded by $O(n\cdot \lambda^3 \cdot \kappa ).$



## 2025/1108

* Title: Laconic PSI on Authenticated Inputs and Applications
* Authors: James Bartusek, Sanjam Garg, Abhishek Jain, Guru-Vamsi Policharla
* [Permalink](https://eprint.iacr.org/2025/1108)
* [Download](https://eprint.iacr.org/2025/1108.pdf)

### Abstract

A common issue with using secure computation in practice is that its security does not place any restrictions on what an adversary can use as input in the protocol. In this work, we focus on the practically-motivated setting of (two-message, labeled)
private set intersection (PSI), and advocate for a clean and versatile solution to this problem: PSI on authenticated inputs.

Our central contributions are summarized as follows.
- We formulate a novel definition of PSI on authenticated inputs that has the potential for use in several applications, from content moderation in end-to-end encrypted systems to watchlists in anonymous e-cash systems.
- We design a concretely-efficient and laconic (i.e., the size of the receiver's message is independent of its set size) protocol for PSI on authenticated inputs.
- We build on our PSI protocol to obtain the first laconic set pre-constrained group signature scheme, improving on that of Bartusek et al. (Eurocrypt 23).

We also explore various optimizations to our basic protocol, including reducing the receiver's concrete run time, and a tradeoff between crs size and message size.



## 2025/1109

* Title: Kahrobaei--Koupparis DSS: universal forgery
* Authors: Alexander Ushakov
* [Permalink](https://eprint.iacr.org/2025/1109)
* [Download](https://eprint.iacr.org/2025/1109.pdf)

### Abstract

Regardless of the choice of parameters, knowledge of a single signed message, i.e., a pair message/signature, produced by Kahrobaei-Koupparis digital signature scheme is sufficient to forge a valid signature for any other message.



## 2025/1110

* Title: A Framework for Compiling Custom Languages as Efficiently Verifiable Virtual Machines
* Authors: Assimakis A. Kattis, Brian Klatt, Philip Quirk, Logan Allen
* [Permalink](https://eprint.iacr.org/2025/1110)
* [Download](https://eprint.iacr.org/2025/1110.pdf)

### Abstract

In this work, we develop a framework for compiling languages into efficient Interactive Oracle Proofs (IOPs, or ‘circuits’), motivated by applications in verifiable Virtual Machine (zkVM) design. We provide a set of sufficient conditions on a
language under which it can be compiled into an efficient IOP, alongside corresponding performance costs. We identify a subclass of languages, which we denote as traversable, and demonstrate how traversable languages can be efficiently compiled as
circuits using established techniques.

To demonstrate the efficacy of our compilation framework, we develop a zkVM for the Nock programming language by (1) formalizing the existing Nock specification, and (2) applying our techniques to design an efficient IOP representation for the Nock VM.
The resulting circuit is small, on par with existing state-of-the-art zkVM designs and can be generated for any traversable language in a generic way.



## 2025/1111

* Title: SEAF: Secure Evaluation on Activation Functions with Dynamic Precision for Secure Two-Party Inference
* Authors: Hao Guo, Zhaoqian Liu, Ximing Fu, Zhusen Liu
* [Permalink](https://eprint.iacr.org/2025/1111)
* [Download](https://eprint.iacr.org/2025/1111.pdf)

### Abstract

Secure evaluation of non-linear functions is one of the most expensive operations in secure two-party computation, particularly for activation functions in privacy preserving machine learning (PPML). This work introduces SEAF, a novel framework for
efficient Secure Evaluation on Activation Functions. SEAF is based on the linear approximation approach, but enhances it by introducing two key innovations: Trun-Eq based interval test protocols and linear approximation with dynamic precision, which have
the potential for broader applicability. Furthermore, we classify common activation functions into several categories, and present specialized methods to evaluate them using our enhanced techniques. Our implementation of SEAF demonstrates $3.5 \times$ to
$5.9 \times$ speedup on activation functions $\mathsf{Tanh}$ and $\mathsf{Sigmoid}$ compared to SirNN (S\&P'21). When applied on $\mathsf{GELU}$, SEAF outperforms Iron (NeurIPS'22) by more than $10 \times$ and Bolt (S\&P'24) by up to $3.4 \times$. For
end-to-end secure inference on BERT, the original $\mathsf{GELU}$ accounts for $31.3 \%$ and $22.5 \%$ of the total runtime in Iron and Bolt, respectively. In contrast, our optimized $\mathsf{GELU}$ reduces these proportions to $4.3 \%$ and $9.8 \%$,
eliminating $\mathsf{GELU}$ as a bottleneck in secure inference.



## 2025/1112

* Title: Hydrangea: Optimistic Two-Round Partial Synchrony with One-Third Fault Resilience
* Authors: Nibesh Shrestha, Aniket Kate, Kartik Nayak
* [Permalink](https://eprint.iacr.org/2025/1112)
* [Download](https://eprint.iacr.org/2025/1112.pdf)

### Abstract

We present Hydrangea, a partially synchronous Byzantine fault-tolerant state machine replication protocol that achieves a latency of two rounds optimistically while maintaining high adversarial resilience. In particular, for a system of $n = 3f + 3p + 1$
parties, if up to $p$ parties are faulty, then the protocol can obtain a latency of two rounds. Otherwise, the protocol can obtain a latency of three rounds while tolerating $f$ Byzantine faults and $p$ crash faults {\em simultaneously}.



## 2025/1113

* Title: Computational Attestations of Polynomial Integrity Towards Verifiable Back-Propagation
* Authors: Dustin Ray, Caroline El Jazmi
* [Permalink](https://eprint.iacr.org/2025/1113)
* [Download](https://eprint.iacr.org/2025/1113.pdf)

### Abstract

Recent advancements in machine learning accuracy and utility have been driven by the effective combination of sophisticated models with high-performance computational scaling. As the development of large-scale models shifts away from commodity hardware
to outsourced computation, it becomes paramount to ensure that the training process is executed with integrity and transparency. This encompasses verifying that adequate computational resources were expended and that the resulting model is accurate,
rather than the product of skipped steps or resource-saving shortcuts by the external provider. Building on our previous efforts, which demonstrated the computational feasibility of using this system to argue correctness for differentially-private linear
regression, we extend those results to achieve fully provable back-propagation—a cornerstone operation in modern machine learning training. Our system achieves complete zero-knowledge, revealing nothing about the input data during training, and ensures
quantum security by relying on no weak cryptographic primitives. Efficiency is substantially increased through the use of a fixed-point decimal representation, reducing the computational overhead typically associated with floating-point arithmetic.
Notably, our solution is doubly efficient, achieving a logarithmic-time verifier and a linear-time prover. Implemented entirely in Rust without reliance on external machine learning libraries, and executed within a cryptographically secure virtual
machine, this work represents a significant advancement toward verifiable, secure, and efficient outsourced machine learning computations.

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