## In this issue

1. [2024/1656] Asymptotically Optimal Early Termination for ...
2. [2025/279] Context-Dependent Threshold Decryption and its ...
3. [2025/328] Fully Asymmetric Anamorphic Homomorphic Encryption ...
4. [2025/380] A New Generalized Attack on RSA-like Cryptosystems
5. [2025/828] Bandwidth-Efficient Robust Threshold ECDSA in Three ...
6. [2025/829] Row Reduction Techniques for n-Party Garbling
7. [2025/830] Simple Power Analysis Attack on SQIsign
8. [2025/831] Worst-Case Time Analysis of Key Agreement Protocols ...
9. [2025/832] Constant-time Integer Arithmetic for SQIsign
10. [2025/833] A note on closed addition chains and complete numbers
11. [2025/834] A Note on ``CABC: A Cross-Domain Authentication ...
12. [2025/835] Universally Composable Interactive and Ordered ...
13. [2025/836] Registered Functional Encryption for Attribute- ...
14. [2025/837] Towards Optimal Differential Attacks on FLY and PIPO
15. [2025/839] Correlation power analysis of LESS and CROSS
16. [2025/840] T-Spoon: Tightly Secure Two-Round Multi-Signatures ...
17. [2025/841] Verifiable E-Voting with a Trustless Bulletin Board
18. [2025/842] Improvements on the schemes VOX and QR UOV When ...
19. [2025/843] Rerandomizable Garbling, Revisited
20. [2025/844] Post-Quantum PKE from Unstructured Noisy Linear ...
21. [2025/845] Walnut: A Generic Framework with Enhanced ...
22. [2025/846] Full-Authority Data Sharing Systems: Ciphertext- ...
23. [2025/847] Deterministic algorithms for class group actions
24. [2025/848] On Graphs of Incremental Proofs of Sequential Work
25. [2025/849] Unmasking TRaccoon: A Lattice-Based Threshold ...
26. [2025/850] Succinct Computational Secret Sharing for Monotone ...
27. [2025/851] V$\epsilon$rity: Verifiable Local Differential Privacy
28. [2025/852] Neural-Inspired Advances in Integral Cryptanalysis
29. [2025/853] Practical Deniable Post-Quantum X3DH: A Lightweight ...
30. [2025/854] ProbeNav - Fast, precise and repeatable positioning ...
31. [2025/855] Posterior Security: Anonymity and Message Hiding of ...
32. [2025/856] Testing the Tests - Opportunities for Corrections ...
33. [2025/857] Classify Directly: A Dynamic Time SPA ...
34. [2025/858] Encrypted Matrix-Vector Products from Secret Dual Codes
35. [2025/859] On the Provable Dual Attack for LWE by Modulus ...
36. [2025/860] sPAR: (Somewhat) Practical Anonymous Router
37. [2025/861] MOCHA: Mixnet Optimization Considering Honest ...
38. [2025/862] Distinguishing Full-Round AES-256 in a Ciphertext- ...
39. [2025/863] Fly Away: Lifting Fault Security through Canaries ...

## 2024/1656

* Title: Asymptotically Optimal Early Termination for Dishonest Majority Broadcast
* Authors: Giovanni Deligios, Ivana Klasovita, Chen-Da Liu-Zhang
* [Permalink](https://eprint.iacr.org/2024/1656)
* [Download](https://eprint.iacr.org/2024/1656.pdf)

### Abstract

Deterministic broadcast protocols among $n$ parties tolerating $t$ corruptions require $\min\{f+2, t+1\}$ rounds, where $f \le t$ is the actual number of corruptions in an execution of the protocol. We provide the first protocol which is optimally
resilient, adaptively secure, and asymptotically matches this lower bound for any $t<(1-\varepsilon)n$. By contrast, the best known algorithm in this regime by Loss and Nielsen (EUROCRYPT'24) always requires $O(\min\{f^2, t\})$ rounds. Our main technical
tool is a generalization of the notion of polarizer introduced by Loss and Nielsen, which allows parties to obtain transferable cryptographic evidence of missing messages with fewer rounds of interaction.



## 2025/279

* Title: Context-Dependent Threshold Decryption and its Applications
* Authors: Dan Boneh, Benedikt Bünz, Kartik Nayak, Lior Rotem, Victor Shoup
* [Permalink](https://eprint.iacr.org/2025/279)
* [Download](https://eprint.iacr.org/2025/279.pdf)

### Abstract

We initiate the study of high-threshold public-key decryption, along with an enhanced security feature called context-dependent decryption.
Our study includes definitions, constructions, security proofs, and applications.
The notion of high-threshold decryption has received almost no attention in the literature. The enhanced security feature of context-dependent encryption is entirely new, and plays an important role in many natural applications of threshold decryption.



## 2025/328

* Title: Fully Asymmetric Anamorphic Homomorphic Encryption from LWE
* Authors: Amit Deo, Benoît Libert
* [Permalink](https://eprint.iacr.org/2025/328)
* [Download](https://eprint.iacr.org/2025/328.pdf)

### Abstract

As introduced by Persiano {\it et al.} (Eurocrypt'22), anamorphic encryption (AE) is a primitive enabling private communications against a dictator that forces users to surrender their decryption keys. In its fully asymmetric flavor (defined by Catalano
{\it et al.}, Eurocrypt'24), anamorphic channels can work as hidden public-key mechanisms in the sense that anamorphic encryptors are not necessarily able to decrypt anamorphic ciphertexts. Unfortunately, fully asymmetric AE is hard to come by and even
impossible to obtain from ordinary public-key encryption via black-box constructions. So far, only three schemes are known to rely on well-established assumptions. In this paper, we exhibit constructions from the standard LWE assumption based on Regev'
s cryptosystem and its dual version. In both cases, we retain the additive homomorphism of the schemes. We additionally show that dual Regev is public-key anamorphic in the sense of Persiano {\it et al.} (Crypto'24). In the FHE setting, we show that the
dual GSW system provides fully asymmetric AE (while preserving its leveled homomorphism) when instantiated with binary/ternary secret keys. Along the way, we discuss the extent to which our schemes satisfy a generalization of Banfi {\it et al.}'s notion
of robustness (Eurocrypt'24) to the case of homomorphically evaluated ciphertexts.



## 2025/380

* Title: A New Generalized Attack on RSA-like Cryptosystems
* Authors: Michel Seck, Oumar Niang, Djiby Sow, Abderrahmane Nitaj, Mengce Zheng, Maher Boudabra
* [Permalink](https://eprint.iacr.org/2025/380)
* [Download](https://eprint.iacr.org/2025/380.pdf)

### Abstract

Rivest, Shamir, and Adleman published the RSA cryptosystem in 1978, which has been widely used over the last four decades. The security of RSA is based on the difficulty of factoring large integers $N = pq$, where $p$ and $q$ are prime numbers. The
public exponent $e$ and the private exponent $d$ are related by the equation $ed - k(p-1)(q-1) = 1$. Recently, Cotan and Teseleanu (NordSec 2023) introduced a variant of RSA, where the public exponent $e$ and the private exponent $d$ satisfy the equation
$ed - k(p^n-1)(q^n-1) = 1$ for some positive integer $n$. In this paper, we study the general equation $eu - (p^n - 1)(q^n - 1)v = w$ with positive integers $u$ and $v$, and $w\in \mathbb{Z}$. We show that, given the public parameters $N$ and $e$, one
can recover $u$ and $v$ and factor the modulus $N$ in polynomial time by combining continued fractions with Coppersmith's algorithm which relies on lattice reduction techniques, under specific conditions on $u$, $v$, and $w$. Furthermore, we show that if
the private exponent $d$ in an RSA-like cryptosystem is either small or too large, then $N$ can be factored in polynomial time. This attack applies to the standard RSA cryptosystem.



## 2025/828

* Title: Bandwidth-Efficient Robust Threshold ECDSA in Three Rounds
* Authors: Yingjie Lyu, Zengpeng Li, Hong-Sheng Zhou, Haiyang Xue, Mei Wang, Shuchao Wang, Mengling Liu
* [Permalink](https://eprint.iacr.org/2025/828)
* [Download](https://eprint.iacr.org/2025/828.pdf)

### Abstract

Threshold ECDSA schemes distribute the capability of issuing signatures to multiple parties. They have been used in practical MPC wallets holding cryptocurrencies. However, most prior protocols are not robust, wherein even one misbehaving or non-
responsive party would mandate an abort. Robust schemes have been proposed (Wong et al., NDSS ’23, ’24), but they do not match state-of-the-art number of rounds which is only three (Doerner et al., S&P ’24). In this work, we propose robust
threshold ECDSA schemes RompSig-Q and RompSig-L that each take three rounds (two of which are broadcasts). Building on the works of Wong et al. and
further optimized towards saving bandwidth, they respectively take each signer (1.0𝑡 + 1.6) KiB and 3.0 KiB outbound broadcast communication, and thus exhibit bandwidth efficiency that is competitive in practical scenarios where broadcasts are
natively handled. RompSig-Q preprocesses multiplications and features fast online signing; RompSig-L leverages threshold CL encryption for scalability and dynamic participation.



## 2025/829

* Title: Row Reduction Techniques for n-Party Garbling
* Authors: Kelong Cong, Emmanuela Orsini, Erik Pohle, Oliver Zajonc
* [Permalink](https://eprint.iacr.org/2025/829)
* [Download](https://eprint.iacr.org/2025/829.pdf)

### Abstract

Recent advancements in maliciously secure garbling have significantly improved the efficiency of constant-round multi-party computation. Research in the field has primarily focused on reducing communication complexity through row reduction techniques and
improvements to the preprocessing phase with the use of simpler correlations. In this work, we present two contributions to reduce the communication complexity of state of the art multi-party garbling with an arbitrary number of corruptions. First, we show how to achieve full row reduction for $n$-party garbled circuits in HSS17-
style protocols (Hazay et al., Asiacrypt'17 & JC'20) and authenticated garbling (Yang et al., CCS'20), reducing the size of the garbled circuit by 25% from $4n\kappa$ to $3n\kappa$ and from $(4n-6)\kappa$ to $3(n-1)\kappa$ bits per AND gate, respectively.
Achieving row reduction in multi-party garbling has been an open problem which was partly addressed by the work of Yang et al. for authenticated garbling. In our work, we show a full row reduction for both garbling approaches, thus addressing this open
problem completely.
Second, drawing inspiration from the work of Dittmer et al. (Crypto 2022), we propose a new preprocessing protocol to obtain the required materials for the garbling phase using large field triples that can be generated with sublinear communication. The
new preprocessing significantly reduces the communication overhead of garbled circuits. Our optimizations result in up to a $6\times$ reduction in communication compared to HSS17 and a $2.2\times$ reduction over the state of the art authenticated
garbling of Yang et al. for 3 parties in a circuit with 10 million AND gates.



## 2025/830

* Title: Simple Power Analysis Attack on SQIsign
* Authors: Anisha Mukherjee, Maciej Czuprynko, David Jacquemin, Péter Kutas, Sujoy Sinha Roy
* [Permalink](https://eprint.iacr.org/2025/830)
* [Download](https://eprint.iacr.org/2025/830.pdf)

### Abstract

The isogeny-based post-quantum digital signature algorithm SQIsign offers the most compact key and signature sizes among all candidates in the ongoing NIST call for additional post-quantum signature algorithms. To the best of our knowledge, we present
the first Simple Power Analysis (SPA) side-channel attack on SQIsign, demonstrating its feasibility for key recovery.
Our attack specifically targets secret-dependent computations within Cornacchia's algorithm, a fundamental component of SQIsign's quaternion module. At the core of this algorithm, a secret-derived yet ephemeral exponent is used in a modular
exponentiation subroutine. By performing SPA on the modular exponentiation, we successfully recover this ephemeral exponent. We then develop a method to show how this leaked exponent can be exploited to ultimately reconstruct the secret signing key of
SQIsign.
Our findings emphasize the critical need for side-channel-resistant implementations of SQIsign, highlighting previously unexplored vulnerabilities in its design.



## 2025/831

* Title: Worst-Case Time Analysis of Key Agreement Protocols in 10BASE-T1S Automotive Networks
* Authors: Teodora Ljubevska, Alexander Zeh, Donjete Elshani Rama, Ken Tindell * [Permalink](https://eprint.iacr.org/2025/831)
* [Download](https://eprint.iacr.org/2025/831.pdf)

### Abstract

With the rise of in-vehicle and car-to-x communication systems, ensuring robust security in automotive networks is becoming increasingly vital. As the industry shifts toward Ethernet-based architectures, the IEEE 802.1AE MACsec standard is gaining
prominence as a critical security solution for future in-vehicle networks (IVNs). MACsec utilizes the MACsec Key Agreement Protocol (MKA), defined in the IEEE 802.1X standard, to establish secure encryption keys for data transmission. However, when
applied to 10BASE-T1S Ethernet networks with multidrop topologies, MKA encounters a significant challenge known as the real-time paradox. This paradox arises from the competing demands of prioritizing key agreement messages and real-time control data,
which conflict with each other. Infineon addresses this challenge with its innovative In-Line Key Agreement (IKA) protocol. By embedding key agreement information directly within a standard data frame, IKA effectively resolves the real-time paradox and
enhances network performance. This paper establishes a theoretical worst-case delay bound for key agreement in multidrop 10BASE-T1S IVNs with more than two nodes, using Network Calculus techniques. The analysis compares the MKA and IKA protocols in terms
of performance. For a startup scenario involving a 16-node network with a 50 bytes MPDU size, the MKA protocol exhibits a worst-case delay that is 1080% higher than that of IKA. As the MPDU size increases to 1486 bytes, this performance gap narrows
significantly, reducing the delay difference to just 6.6%.



## 2025/832

* Title: Constant-time Integer Arithmetic for SQIsign
* Authors: Fatna Kouider, Anisha Mukherjee, David Jacquemin, Péter Kutas
* [Permalink](https://eprint.iacr.org/2025/832)
* [Download](https://eprint.iacr.org/2025/832.pdf)

### Abstract

SQIsign, the only isogeny-based signature scheme submitted to NIST’s additional signature standardization call, achieves the smallest public key and signature sizes among all post-quantum signature schemes. However, its existing implementation,
particularly in its quaternion arithmetic operations, relies on GMP’s big integer functions, which, while efficient, are often not designed for constant-time execution.
In this work, we take a step toward side-channel-protected SQIsign by implementing constant-time techniques for SQIsign’s big integer arithmetic, which forms the computational backbone of its quaternion module. For low-level fundamental functions
including Euclidean division, exponentiation and the function that computes integer square root, we either extend or tailor existing solutions according to SQIsign's requirements such as handling signed integers or scaling them for integers up to $\sim$
12,000 bits. Further, we propose a novel constant-time modular reduction technique designed to handle dynamically changing moduli.Our implementation is written in C without reliance on high-level libraries such as GMP and we evaluate the constant-time
properties of our implementation using Timecop with Valgrind that confirm the absence of timing-dependent execution paths. We provide experimental benchmarks across various SQIsign parameter sizes to demonstrate the performance of our constant-time
implementation.



## 2025/833

* Title: A note on closed addition chains and complete numbers
* Authors: Theophilus Agama
* [Permalink](https://eprint.iacr.org/2025/833)
* [Download](https://eprint.iacr.org/2025/833.pdf)

### Abstract

We introduce a new class of addition chains and show the numbers for which these chains are optimal satisfy the Scholz conjecture, precisely the inequality $$\iota(2^n-1)\leq n-1+\iota(n).$$



## 2025/834

* Title: A Note on ``CABC: A Cross-Domain Authentication Method Combining Blockchain with Certificateless Signature for IIoT''
* Authors: Zhengjun Cao, Lihua Liu
* [Permalink](https://eprint.iacr.org/2025/834)
* [Download](https://eprint.iacr.org/2025/834.pdf)

### Abstract

We show that the authentication method [Future Gener. Comput. Syst. 158: 516-529 (2024)] cannot be practically implemented, because the signature scheme is insecure against certificateless public key replacement forgery attack. The explicit dependency
between the certificateless public key and secret key is not properly used to construct some intractable problems, such as Elliptic Curve Discrete Logarithm (ECDL). An adversary can find an efficient signing algorithm functionally equivalent to the
valid signing algorithm. We also correct some typos in the original presentation.



## 2025/835

* Title: Universally Composable Interactive and Ordered Multi-Signatures
* Authors: Carsten Baum, Bernardo David, Elena Pagnin, Akira Takahashi
* [Permalink](https://eprint.iacr.org/2025/835)
* [Download](https://eprint.iacr.org/2025/835.pdf)

### Abstract

Multi-signatures allow a given set of parties to cooperate in order to create a digital signature whose size is independent of the number of signers. At the same time, no other set of parties can create such a signature. While non-interactive multi-
signatures are known (e.g. BLS from pairings), many popular multi-signature schemes such as MuSig2 (which are constructed from pairing-free discrete logarithm-style assumptions) require interaction. Such interactive multi-signatures have recently found
practical applications e.g. in the cryptocurrency space.

Motivated by classical and emerging use cases of such interactive multi-signatures, we introduce the first systematic treatment of interactive multi-signatures in the universal composability (UC) framework. Along the way, we revisit existing game-based
security notions and prove that constructions secure in the game-based setting can easily be made UC secure and vice versa.

In addition, we consider interactive multi-signatures where the signers must interact in a fixed pattern (so-called ordered multi-signatures). Here, we provide the first construction of ordered multi-signatures based on the one-more discrete logarithm
assumption, whereas the only other previously known construction required pairings. Our scheme achieves a stronger notion of unforgeability, guaranteeing that the adversary cannot obtain a signature altering the relative order of honest signers. We also
present the first formalization of ordered multi-signatures in the UC framework and again show that our stronger game-based definitions are equivalent to UC security.



## 2025/836

* Title: Registered Functional Encryption for Attribute-Weighted Sums with Access Control
* Authors: Tapas Pal, Robert Schädlich
* [Permalink](https://eprint.iacr.org/2025/836)
* [Download](https://eprint.iacr.org/2025/836.pdf)

### Abstract

In this work, we present Functional Encryption (FE) schemes for Attribute-Weighted Sums (AWS), introduced by Abdalla, Gong and Wee (Crypto 2020) in the registration-based setting (RFE). In such a setting, users sample their own public/private key pairs $(
\mathsf{pk}_i, \mathsf{sk}_i)$; a key curator registers user public keys along with their functions $h_i$; encryption takes as input $N$ attribute-value pairs $\{\vec x_\ell, \vec z_\ell\}_{\ell\in[N]}$ where $\vec x_\ell$ is public and $\vec z_\ell$ is
private; and decryption recovers the weighted sum $\sum_{\ell\in[N]}h_i(\vec x_\ell)^\mathsf{T}\vec z_\ell$ while leaking no additional information about $\vec z_\ell$. Recently, Agrawal, Tomida and Yadav (Crypto 2023) studied the attribute-based case of
AWS (AB-AWS) providing fine-grained access control, where the function is described by a tuple $(g_i, h_i)$, the input is extended to $(\vec y, \{\vec x_\ell, \vec z_\ell\}_{\ell \in [N]})$ and decryption recovers the weighted sum only if $g_i(\vec y) =
0$. Our main results are the following:

- We build the first RFE for (AB-)1AWS functionality, where $N=1$, that achieves adaptive indistinguishability-based security under the (bilateral) $k$-Lin assumption in prime-order pairing groups. Prior works achieve RFE for linear and quadratic
functions without access control in the standard model, or for attribute-based linear functions in the generic group model.

- We develop the first RFE for AB-AWS functionality, where $N$ is unbounded, that achieves very selective simulation-based security under the bilateral $k$-Lin assumption. Here, “very selective” means that the adversary declares challenge attribute
values, all registered functions and corrupted users upfront. Previously, SIM-secure RFEs were only constructed for linear and quadratic functions without access control in the same security model.

We devise a novel nested encoding mechanism that facilitates achieving attribute-based access control and unbounded inputs in the registration-based setting for AWS functionalities, proven secure in the standard model. In terms of efficiency, our
constructions feature short public parameters, secret keys independent of $N$, and compact ciphertexts unaffected by the length of public inputs. Moreover, as required by RFE properties, all objective sizes and algorithm costs scale poly-logarithmically
with the total number of registered users in the system.



## 2025/837

* Title: Towards Optimal Differential Attacks on FLY and PIPO
* Authors: Insung Kim, Seonggyeom Kim, Sunyeop Kim, Donggeun Kwon, Hanbeom Shin, Dongjae Lee, Deukjo Hong, Jaechul Sung, Seokhie Hong
* [Permalink](https://eprint.iacr.org/2025/837)
* [Download](https://eprint.iacr.org/2025/837.pdf)

### Abstract

Lightweight block ciphers such as PIPO and FLY are designed to operate efficiently and securely in constrained environments. While the differential attack on PIPO-64-128 has already been studied by the designers, no concrete differential attack had been
conducted for PIPO-64-256 and FLY. Motivated by this gap, we revisit the security of PIPO against differential attacks and generalize the analysis framework to make it applicable to structurally related ciphers. Based on this generalized framework, we
search for key-recovery-attack-friendly distinguishers and apply clustering techniques to enhance their effectiveness in key-recovery attacks. As a result, we improve the previously proposed differential attack on PIPO-64-128, reducing the time
complexity by a factor of $2^{31.7}$. Furthermore, we propose a 13-round differential attack on PIPO-64-256, which covers two more rounds than the previous result. We also apply the same methodology to FLY and present the first differential attack on 12-
round FLY, reaching one round beyond the best-known distinguisher. We believe this work improves the understanding of the structures of FLY and PIPO, and provides a basis for future research on advanced key-recovery attacks for related cipher designs.



## 2025/839

* Title: Correlation power analysis of LESS and CROSS
* Authors: Maciej Czuprynko, Anisha Mukherjee, Sujoy Sinha Roy
* [Permalink](https://eprint.iacr.org/2025/839)
* [Download](https://eprint.iacr.org/2025/839.pdf)

### Abstract

This paper presents a side-channel attack targeting the LESS and CROSS post-quantum digital signature schemes, resulting in full key recovery for both. These schemes have advanced to the second round of NIST’s call for additional signatures. By
leveraging correlation power analysis and horizontal attacks, we are able to recover the secret key by observing the power consumption during the multiplication of an ephemeral secret vector with a public matrix. The attack path is enabled by the
presence of a direct link between the secret key elements and the ephemeral secret, given correct responses. This attack targets version 1.2 of both schemes. In both settings we can recover the secret key in a single trace for the NIST’s security level
I parameter set. Additionally, we propose improvements to the existing horizontal attack on CROSS, reducing the required rounds that need to be observed by an order of magnitude for the same parameter sets.



## 2025/840

* Title: T-Spoon: Tightly Secure Two-Round Multi-Signatures with Key Aggregation
* Authors: Renas Bacho, Benedikt Wagner
* [Permalink](https://eprint.iacr.org/2025/840)
* [Download](https://eprint.iacr.org/2025/840.pdf)

### Abstract

Multi-signatures over pairing-free cyclic groups have seen significant advancements in recent years, including achieving two-round protocols and supporting key aggregation.
Key aggregation enables the combination of multiple public keys into a single succinct aggregate key for verification and has essentially evolved from an optional feature to a requirement.

To enhance the concrete security of two-round schemes, Pan and Wagner (Eurocrypt 2023, 2024) introduced the first tightly secure constructions in this setting.
However, their schemes do not support key aggregation, and their approach inherently precludes a single short aggregate public key.
This leaves the open problem of achieving tight security and key aggregation simultaneously.

In this work, we solve this open problem by presenting the first tightly secure two-round multi-signature scheme in pairing-free groups supporting key aggregation.
As for Pan and Wagner's schemes, our construction is based on the DDH assumption.
In contrast to theirs, it also has truly compact signatures, with signature size asymptotically independent of the number of signers.



## 2025/841

* Title: Verifiable E-Voting with a Trustless Bulletin Board
* Authors: Daniel Rausch, Nicolas Huber, Ralf Kuesters
* [Permalink](https://eprint.iacr.org/2025/841)
* [Download](https://eprint.iacr.org/2025/841.pdf)

### Abstract

Voter privacy and end-to-end (E2E) verifiability are critical features of electronic voting (e-voting) systems to safeguard elections. To achieve these properties commonly a perfect bulletin board (BB) is assumed that provides consistent, reliable, and
tamper-proof storage and transmission of voting data. However, in practice, BBs operate in asynchronous and unreliable networks, and hence, are susceptible to vulnerabilities such as equivocation attacks and dropped votes, which can compromise both
verifiability and privacy. Although prior research has weakened the perfect BB assumption, it still depends on trusting certain BB components.

In this work, we present and initiate a formal exploration of designing e-voting systems based on fully untrusted BBs. For this purpose, we leverage the notion of accountability and in particular use accountable BBs. Accountability ensures that if a
security breach occurs, then cryptographic evidence can identify malicious parties. Fully untrusted BBs running in asynchronous networks bring new challenges. Among others, we identify several types of attacks that a malicious but accountable BB might be
able to perform and propose a new E2E verifiability notion for this setting. Based on this notion and as a proof of concept, we construct the first e-voting system that is provably E2E verifiable and provides vote privacy even when the underlying BB is
fully malicious. This establishes an alternative to traditional e-voting architectures that rely on (threshold) trusted BB servers.



## 2025/842

* Title: Improvements on the schemes VOX and QR UOV When minus is a plus
* Authors: Pierre Varjabedian
* [Permalink](https://eprint.iacr.org/2025/842)
* [Download](https://eprint.iacr.org/2025/842.pdf)

### Abstract

In this article, we present an improvement for QR UOV and a reparation of VOX.
Thanks to the use of the perturbation minus we are able to fully exploit the parameters in order to reduce the public key. It also helps us to repair the scheme VOX. With QR UOV- we are able to significantly reduce the size of the public key at the
cost of a small increase of the signature size. While with VOX- we can obtain a public key as short as $6KB$. VOX- also maintains a very short signature size.
We also show that the use of minus perturbation is very useful with schemes that uses the QR (Quotient ring perturbation).



## 2025/843

* Title: Rerandomizable Garbling, Revisited
* Authors: Raphael Heitjohann, Jonas von der Heyden, Tibor Jager
* [Permalink](https://eprint.iacr.org/2025/843)
* [Download](https://eprint.iacr.org/2025/843.pdf)

### Abstract

In key-and-message homomorphic encryption (KMHE), the key space is a subset of the message space, allowing encryption of secret keys such that the same homomorphism can be applied to both the key and the message of a given ciphertext.
KMHE with suitable security properties is the main building block for constructing rerandomizable garbling schemes (RGS, Gentry et al., CRYPTO 2010), which enable advanced cryptographic applications like multi-hop homomorphic encryption, the YOSO-like
MPC protocol SCALES (Acharya et al., TCC 2022 and CRYPTO 2024), and more.

The BHHO scheme (Boneh et al., CRYPTO 2008) is currently the only known KMHE scheme suitable for constructing RGS. An encryption of a secret key consists of $\mathcal{O}(\lambda^{2})$ group elements, where $\lambda$ is the security parameter, which
incurs a significant bandwidth and computational overhead that makes the scheme itself, and the RGS protocols building upon it, impractical.

We present a new, more efficient KMHE scheme with linear-size ciphertexts. Despite using heavier cryptographic tools (pairings instead of plain DDH-hard groups), the concrete ciphertext size and computational costs are very significantly reduced. We are able to shrink the ciphertext by 97.83 % (from 16.68 MB to 360 kB) and
reduce the estimated computations for encryption by 99.996 % (from 4 minutes to 0.01 seconds) in comparison to BHHO.

Additionally, we introduce gate KMHE as a new tool to build more efficient RGS. Our RGS construction shrinks the size of a garbled gate by 98.99 % (from 133.43 MB to 1.35 MB) and decreases the estimated cost of garbling by 99.998 % (from 17 minutes to 0.
02 seconds per gate) in comparison to Acharya et al.

In summary, our work shows for the first time that RGS and the SCALES protocol (and hence YOSO-like MPC) are practically feasible for simple circuits.



## 2025/844

* Title: Post-Quantum PKE from Unstructured Noisy Linear Algebraic Assumptions: Beyond LWE and Alekhnovich's LPN
* Authors: Riddhi Ghosal, Aayush Jain, Paul Lou, Amit Sahai, Neekon Vafa
* [Permalink](https://eprint.iacr.org/2025/844)
* [Download](https://eprint.iacr.org/2025/844.pdf)

### Abstract

Noisy linear algebraic assumptions with respect to random matrices, in particular Learning with Errors ($\mathsf{LWE}$) and Alekhnovich Learning Parity with Noise (Alekhnovich $\mathsf{LPN}$), are among the most investigated assumptions that imply post-
quantum public-key encryption (PKE). They enjoy elegant mathematical structure. Indeed, efforts to build post-quantum PKE and advanced primitives such as homomorphic encryption and indistinguishability obfuscation have increasingly focused their
attention on these two assumptions and their variants.

Unfortunately, this increasing reliance on these two assumptions for building post-quantum cryptography leaves us vulnerable to potential quantum (and classical) attacks on Alekhnovich $\mathsf{LPN}$ and $\mathsf{LWE}$. Quantum algorithms is a rapidly
advancing area, and we must stay prepared for unexpected cryptanalytic breakthroughs. Just three decades ago, a short time frame in the development of our field, Shor's algorithm rendered most then-popular number theoretic and algebraic assumptions
quantumly broken. Furthermore, within the last several years, we have witnessed major classical and quantum

[continued in next message]

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