International Association
for Cryptologic Research

We resolve the Correlated Agreement (CA) problem for Reed-Solomon codes up to the information-theoretic capacity limit by introducing a fundamental change of basis: from the traditional evaluation domain to the syndrome space. Viewed through this “Syndrome-Space Lens,” the problem of proximity testing transforms into a transparent question of linear-algebraic geometry: a single affine line of syndromes traversing a family of low-dimensional subspaces. This new perspective makes a sharp phase transition at the capacity boundary visible, allowing for a complete characterization of the problem's behavior across all parameter regimes, yielding short, self-contained proofs.

Classification. We establish a precise trichotomy organized by the rank margin $\Delta := t-d$. At the capacity boundary ($\Delta=0$), the CA premise is information-theoretically vacuous, and we prove that no rigidity can be concluded without imposing additional structure. One step beyond capacity ($\Delta=1$), the problem enters a “knife-edge” regime where unconditional rigidity does not hold; soundness is recovered either through a combinatorial witness (such as a repeated error support or a small union of supports) or by adding protocol-level structure (such as independent two-fold MCA checks, DEEP/STIR out-of-domain sampling, or a global error locator). For stricter gaps ($\Delta\ge 2$), unconditional rigidity holds under a simple algebraic condition ($(r{+}1)k
MCA and Practical Implications. Below capacity ($\delta<1-\rho$), the strengthened mutual correlated agreement (MCA) problem reduces to ordinary correlated agreement. MCA holds under the same hypotheses as CA. When folds are generated with independent challenges (e.g., via domain-separated Fiat-Shamir), the per-round security margins add. The model-scoped soundness law is $\Pr[\mathrm{FA}] \le q^{-(\sum \Delta_i) s}$, providing a clear and complete rulebook for selecting safe and efficient parameters in FRI/STARK systems. This work bypasses the complex machinery of list-decoding algorithms entirely and resolves the long-standing open problem concerning the gap between the Johnson bound and capacity.

This work introduces a new configuration of the GSW fully homomorphic encryption (FHE) (Gentry, Sahai, Waters~Crypto 2013), with a squared gadget ,batching and scale-based homomorphic operation. This configuration offers improved efficiency compared to existing approaches. By utilizing our proposed method as the underlying building block, we can accelerate FHEW-like bootstrapping implementations, including the libraries of FHEW and TFHE. We conduct comprehensive experiments to evaluate the concrete performance of our method, demonstrating improvements of more than 2 times faster. For example, the current ring GSW under OpenFHE takes 84 ms and TFHE takes 11.4 ms, while our approach achieves 26.2 ms and 4.8 ms, respectively. These improvements have significant implications for the practical aspects of FHE, enhancing real-world usability.

Broadcast, though often used as a black box in cryptographic protocols, is expensive to realize in terms of rounds and communication complexity. We investigate the minimal use of broadcast in round-optimal information-theoretic MPC, with statistical security. For information-theoretic MPC with guaranteed output delivery, four rounds of communication are necessary and sufficient (Applebaum, Kachlon and Patra, FOCS 2020; Applebaum, Kachlon and Patra, STOC 2023). We show that broadcast is unavoidable in the second and third rounds of statistical MPC protocols. To complement our lower bounds, we modify the protocol of Applebaum, Kachlon and Patra (STOC 2023) to make use of broadcast only in the second and third round. Along the way, we show that the sharing phase of any three-round information-theoretic VSS protocol must also make use of broadcast in the second and third rounds.

zkVot is a client side trustless distributed computation protocol that utilizes zero knowledge proving technology. It is designed to achieve anonymous and censorship resistant voting while ensuring scalability. The protocol is created as an example of how modular and distributed computation can improve both the decentralization and the scalability of the internet. A complete and working implementation of this paper is available on https://github.com/node101-io/zkvot. It is important to emphasize that zkVot is one of the first complete implementations of a fully censorship resistant anonymous voting application that can scale up to a meaningful number of voters.

This manuscript introduces Semantic Holder (SH), the opposability primitive within the Chaotic Affine Secure Hash (CASH) toolkit, completing the framework’s implementation of the Q2CSI philosophy. SH enables legally opposable interpretations through algebraic extraction from polynomial iteration traces, working in concert with CEE (confidentiality) and AOW (reliability). Building upon the Affine Iterated Inversion Problem (AIIP) foundation, SH provides mathematically verifiable legal interpretations with guaranteed minimum opposability bounds. We establish that SH maintains an opposability score Ω ≥ 0.60 through rigorous entropy preservation, institutional explainability, and legal contestability guarantees. The primitive features efficient STARK-proof verifiable computation, cross-jurisdictional compatibility, and quantum resistance through its reduction to AIIP hardness. We demonstrate practical applications in legal smart contracts, regulatory compliance auditing, and digital evidence authentication, providing concrete parameter recommendations for standard security levels. SH represents a significant advancement in cryptographic systems that must operate within legal constraints, enabling transparent and verifiable legal opposability without compromising security or performance.

Despite several known idiosyncrasies separating the synchronous and the asynchronous models, asynchronous secure multi-party computation (MPC) protocols demonstrate high-level similarities to synchronous MPC, both in design philosophy and abstract structure. As such, a coveted, albeit elusive, desideratum is to devise automatic translators (e.g., protocol compilers) of feasibility and efficiency results from one model to the other.

In this work, we demonstrate new challenges associated with this goal. Specifically, we study the case of parallel composition in the asynchronous setting. We provide formal definitions of this composition operation in the UC framework, which, somewhat surprisingly, have been missing from the literature. Using these definitions, we then turn to charting the feasibility landscape of asynchronous parallel composition.

We first prove strong impossibility results for composition operators that do not assume knowledge of the functions and/or the protocols that are being composed. These results draw a grim feasibility picture, which is in sharp contrast with the synchronous model, and highlight the question:

Is asynchronous parallel composition even a realistic goal?

To answer the above (in the affirmative), we provide conditions on the composed protocols that enable a useful form of asynchronous parallel composition, as it turns out to be common in existing constructions.

In 1997, Kani proved Kani's lemma, which asserts that a commutative diagram of four $g$‑dimensional abelian varieties induces an isogeny between product abelian varieties of dimension $2g$, in counting the number of genus-$2$ curves admitting two distinct elliptic subcovers. In these years, Kani’s lemma plays a fundamental role in isogeny-based cryptography: Kani’s lemma has found numerous cryptographic applications, including both cryptanalysis and protocol construction. However, direct investigation into the lemma itself remains scarce.

In this work, we propose a generalization of Kani’s lemma. We present a novel formulation that, given a commutative diagram of $2^{n+1}$ abelian varieties of dimension $g$, yields an isogeny of dimension $2^{n}g$. We further establish a connection between this generalized lemma and the theory of Clifford algebras, using the latter as a foundational tool in our construction. To exemplify our framework, we explicitly construct the resulting $2^{n}g$‑dimensional isogenies for the cases $n=1,2,3$. The cases of $n=2,3$ provide nontrivial generalizations of the original Kani's lemma. This generalization is expected to have novel applications in the fields of both mathematics and cryptography.

The current standardization calls for threshold signatures have highlighted the need for appropriate security notions providing security guarantees strong enough for broad application. To address this, Bellare et al. [Crypto'22] put forward a hierarchy of unforgeability notions for threshold signatures. Recently, Navot and Tessaro [Asiacrypt'24] introduced a new game-based definition of strong (one-more) unforgeability for threshold signatures, which however does not achieve Bellare's strongest level of security.

Navot and Tessaro analyzed several existing schemes w.r.t. their strong unforgeability security notion, but all positive results rely on idealized models. This is in contrast to the weaker security notion of (standard) unforgeability, for which standard-model constructions exist. This leaves open a fundamental question: is getting strong unforgeability fundamentally harder than standard unforgeability for threshold signatures?

In this paper we bridge this gap, by showing a generic construction lifting any unforgeable threshold signature scheme to strong unforgeability. The building blocks of our construction can be instantiated in the standard model under standard assumptions. The achieved notion of strong unforgeability extends the definition of Navot and Tessaro to achieve the strongest level of security according to the hierarchy of Bellare et al. (following a recent classification of security notions for (blind) threshold signatures by Lehmann, Nazarian, and Özbay [Eurocrypt'25]).

The starting point for our transformation is an existing construction for single-user signatures from chameleon hash functions by Steinfeld, Pieprzyk and Wang [RSA'07]. We first simplify their construction by relying on a stronger security notion for chameleon hash functions. The bulk of our technical contribution is then to translate this framework into the threshold setting. Towards this goal, we introduce a game-based definition for threshold chameleon hash functions (TCHF) and provide a construction of TCHF that is secure under DLOG in the standard model. We believe that our new notion of TCHF might also be of independent interest.

We propose a new data anonymisation method based on the concept of a quantum feature map. The main advantage of the proposed solution is that a high degree of security is combined with the ability to perform classification tasks directly on the anonymised (encrypted) data resulting in the same or even higher accuracy compared to that obtained when working with the original plain text data. This enables important usecases in medicine and finance where anonymised datasets from different organisations can be combined to facilitate improved machine learning outcomes utilising the combined dataset. Examples include combining medical diagnostic imaging results across hospitals, or combining fraud detection datasets across financial institutions. We use the Wisconsin Breast Cancer dataset to obtain results on Rigetti's quantum simulator and Ankaa-3 quantum processor. We compare the results with classical benchmarks and with those obtained from an alternative anonymisation approach using a Restricted Boltzmann Machine to generate synthetic datasets. Finally, we introduce concepts from the theory of quantum magic to optimise the circuit ansatz and hyperparameters used within the quantum feature map.

Updatable Signature (US) schemes allow updating signatures so that they can be verified using a new key. This updating feature is useful for key rotation in practice. Cini et al. (PKC'21) first formalised this primitive. However, their post-quantum-secure US scheme does not satisfy their security definition, i.e., without unlinkability and only bounded unforgeability. This paper aims to solve this problem by providing a new fully secure construction. First, we simplify the definition of unlinkability by a hybrid argument, and reduce the update oracle of the unforgeability experiment by assuming unlinkability. Then, we construct our US scheme from verifiable encryption and the SIS assumption. This scheme is fully unlinkable and unforgeable, but also a unique signature scheme in each epoch, allowing only one signature for each message during one epoch and rendering a stateful signer/proxy. This is sufficient for many applications.

Event date: 7 September to 11 September 2026

Event date: 14 April to 16 April 2026
Submission deadline: 31 October 2025
Notification: 12 January 2026