International Association
for Cryptologic Research

This paper presents a unified information-theoretic framework for steganography that simultaneously addresses reliability, statistical undetectability, computational security, and robustness over noisy channels. Unlike prior work that treated these aspects separately under idealized assumptions, the framework formalizes them within a single model, providing definitions, capacity bounds, and impossibility results based on statistical distances. It also considers computationally bounded adversaries and trade-offs between payload, detectability, and error, offering a rigorous foundation for designing secure, robust, and efficient steganographic systems.

One-sided linear systems of the form ``$Ax=b$'' are well-known and extensively studied over the tropical (max-plus) semiring and wide classes of related idempotent semirings. The usual approach is to first find the greatest solution to such system in polynomial time and then to solve a much harder problem of finding all minimal solutions. We develop an extension of this approach to the same systems over two well-known extensions of the tropical semiring: symmetrized and supertropical, and discuss the implications of our findings for the tropical cryptography.

Mental Poker enables two players to play card games at a distance without having a physical deck of cards at hand, as long as they have reliable trapdoor permutations or access to Oblivious Transfer (OT). OT itself can be stored and extended using just a one-way function. We examine whether Mental Poker can be extended from initial hands of ordinary physical poker.

On the theoretical side, this work establishes OT amplification/extraction as a cryptographic primitive using asymmetrically-viewed fully-randomizing permutations. On the pragmatic, it is naturally related to ``card cryptography'' although in a very restricted sense: 52-card deck protocols using fully scrambling shuffles. While secret-key exchange protocols make strong use of full shuffles, full shuffles are avoided in 2PC/AND/Solitaire card settings because of detrimental over-randomization. Within those domains, this work explains decades-old impossibility conjectures in certain circumstances. More positively, we provide several practical and information-theoretically secure ways to establish base OTs from 5-Card Draw over ordinary decks at rates sufficient to establish a foothold for indefinite Mental Poker extension in just an afternoon of play.

Plaintext-awareness of AEAD schemes is one of the more obscure and easily misunderstood notions. Originally proposed by Andreeva et al., Mennink and Talnikar 2025 showed that the original definitions are vague and leave too much room for interpretation. They presented new definitions and analyzed the three main AEAD compositions relative to the new definitions. In particular, they showed that MAC-then-Encrypt (MtE) is not plaintext-aware. However, they showed that an SIV-style variant is indeed plaintext-aware. In this work, we first show that their analysis contains a gap, voiding their proof. We show this by showing several attacks; against their choice of extractor, with trivial complexity, and against any extractor, with birthday-bound complexity. Next, we re-establish their results by designing a new extractor that captures their intended goal and prove a tight PA1 security bound. We also show that the result is not dependent on the encryption scheme used, by showing that an extractor can also be designed for sMtE[ΘCB3], a variant where the encryption step is done by an ΘCB3-like scheme. Afterwards, we strengthen their results, by revisiting other compositions. In particular, we show that Encrypt-then- MAC (EtM) is in fact PA2-secure. Furthermore, we show that SIV-style MtE cannot be PA2-secure. Additionally, we also show that Encode-then-Encipher is PA2-secure, but not beyond the first successful forgery. More importantly, we show that up to some necessary assumptions, PA2 and RAE are equivalent.

Last but not least, we investigate the value of the notion of plaintext awareness. We look deeper into the relation between plaintext awareness and confidentiality. We show that the problem of confidentiality in the presence of release of unverified plaintext can be seen as a confidentiality-with-leakage problem in the simulatable leakage framework. In this regard, we start, by showing that PA1 security cannot imply confidentiality with leakage. Similarly, we compare our results to the AERUP notion of TOSC 2019. We show that a scheme can be AERUP secure but not secure against a somewhat straightforward left-or-right attack in the same model. This puts into question the meaning and relevance of the PA1 and AERUP security notions. These results can be seen as providing security in a two-phase game, where the adversary does not observe any leakage after the first challenge query, as we argue in the paper. On the positive side, we show that if a scheme achieves IND-CPA, INT-RUP and PA2, then it achieves confidentiality with leakage for the appropriate leakage function. This closes a gap in the literature on the relation between confidentiality with leakage and RUP notions.

Non-interactive zero-knowledge proofs (NIZKPs) used as components in advanced cryptographic protocols typically require straight-line extractability to enable security analysis. While the widely-used Fiat-Shamir transform produces efficient and compact NIZKPs from Sigma protocols, its security proofs rely on adversary rewinding, which prevents straight-line extractability. The Fischlin transform offers an alternative that produces straight-line extractable NIZKPs from Sigma protocols, but typically sacrifices compactness in the process. In the post-quantum setting, Group-action-based Sigma protocols have proven to be truly flexible for the design of advanced cryptosystems. These Sigma protocols have a small challenge space that requires tailored optimizations to improve compactness of the derived NIZKPs and signatures. Some specific techniques for Fiat-Shamir NIZKPs have been studied. Among the most established solutions, the fixed-weight technique leverages on the use of seed trees to encode the majority of the transcripts in the proof. However, the implementation of the same techniques within the Fischlin transform encounters significant obstructions. In particular, its impact is limited, and a closed analysis of its effectiveness appears to be intractable.

This work introduces the GAO (Group Action Oriented) transform, a new generic compiler that produces straight-line extractable NIZKPs from Sigma protocols while significantly simplifying the analysis of the fixed-weight framework. The GAO transform is then optimized in two different ways, defining a collision predicate (yielding the Coll-GAO transform) and adopting a technique (Stretch-and-Compress) that can be applied to improve both GAO and Coll-GAO (yielding the SC-GAO and SC-Coll-GAO transforms). The practical advantages of the SC-Coll-GAO transform are theoretically motivated and concretely tested on the LESS digital signature, a code-based candidate that recently advanced to the second round of the NIST standardization process specifically purposed for post-quantum signatures. Remarkably, when compared to the Fiat-Shamir LESS baseline, SC-Coll-GAO incurs a computational cost increase by 50-60%, while signature sizes grow by only 10-20%.

This work studies the security and constructions of correlation robust (CR) hash functions in secure multi-party computation (MPC). Existing definitions of CR hashing are all game-based (i.e., no simulator to achieve programmability or extractability), but MPC protocols are proven secure in the simulation-based models including both stand-alone and universal composability models. We found that for some MPC protocols, e.g., TinyOT-like authenticated-triple generation protocols and correlated oblivious transfer (COT) extension protocols, such a mismatch could lead to a gap in security proofs, even for the semi-honest adversary and stand-alone model.

To bridge the gap, we introduce a simulation-based security notion for CR hash functions to allow secure composition. Instead of building from scratch, we introduce such a simulator to a wide class of existing ideal-cipher-based CR hashing constructions, and derive the security bound from their original game-based CR security.This enables us to obtain an efficient CR hashing construction making just one call to a blockcipher, and is much more efficient than the construction from a random oracle used in previous TinyOT-like protocols. We showcase the utility of the new CR notion in easing security proofs and mitigating the risk of errors on two classes of protocols: (1) authenticated-triple generation protocols in the TinyOT family with a countermeasure; (2) COT extension protocols with bootstrapped iterations.

A random local function defined by a $d$-ary predicate $P$ is one where each output bit is computed by applying $P$ to $d$ randomly chosen bits of its input. These represent natural distributions of instances for constraint satisfaction problems. They were put forward by Goldreich as candidates for low-complexity one-way functions, and have subsequently been widely studied also as potential pseudo-random generators. We present a new search-to-decision reduction for random local functions defined by any predicate of constant arity. Given any efficient algorithm that can distinguish, with advantage $\epsilon$, the output of a random local function with $m$ outputs and $n$ inputs from random, our reduction produces an efficient algorithm that can invert such functions with $\tilde{O}(m(n/\epsilon)^2)$ outputs, succeeding with probability $\Omega(\epsilon)$. This implies that if a family of local functions is one-way, then a related family with shorter output length is family of pseudo-random generators. Prior to our work, all such reductions that were known required the predicate to have additional sensitivity properties, whereas our reduction works for any predicate. Our results also generalise to some super-constant values of the arity $d$, and to noisy predicates.

We propose Pool: a conceptually simple post-quantum (PQ) oblivious pseudorandom function (OPRF) protocol, that is round-optimal (with input-independent preprocessing), practically efficient, and has security based on the well-understood hardness of the learning with rounding (LWR) problem. Specifically, our design permits oblivious computation of the LWR-based pseudorandom function $F_{\mathsf{sk}}(x) = \lceil H(x)^{\top} \cdot \mathsf{sk} \rfloor_{q,p}$, for random oracle $H: \{0,1\}^* \mapsto \mathbb{Z}_q^n$ and uniformly chosen $\mathsf{sk} \in \{0,1\}^n$. For 128-bits of semi-honest security, the Pool OPRF has an online communication cost of 11.9~kB, and a computational runtime of less than 2~ms on a single thread (via an open-source software implementation). This is more efficient (in either online communication cost or runtime) than constructions from well-known PQ PRFs, and is competitive even with constructions that only conjecture PQ security on lesser-known assumptions. As a result, our design gives high-performance, post-quantum variants of established OPRF applications in multi-party computation and private set operation protocols.

A Private Simultaneous Messages (PSM) protocol is a secure multiparty computation protocol with a minimal interaction pattern, which allows input parties sharing common randomness to securely reveal the output of a function by sending messages only once to an external party. Since existing PSM protocols for arbitrary functions have exponentially large communication complexity in the number $n$ of parties, it is important to explore efficient protocols by focusing on special functions of practical use. In this paper, we study the communication efficiency of PSM protocols for symmetric functions, which provide many useful functionalities for real-world applications. We present a new $n$-party PSM protocol for symmetric functions with communication complexity $n^{2d/3+O(1)}$, where $d$ is the size of the input domain of each party. Our protocol improves the currently best known communication complexity of $n^{d+O(1)}$. As applications to other related models, we show that our novel protocol implies improved communication complexity of ad-hoc PSM, where only a subset of parties actually send messages, and also leads to a more communication-efficient robust PSM protocol, which is secure against collusion of the external party and input parties. The extension to ad-hoc PSM is not a straightforward application of the previous transformation but includes an optimization technique based on the symmetry of functions.

Proof-of-work (PoW)-based consensus mechanisms have long been criticized for their high resource (electricity, e-waste) consumption and reliance on hash puzzles, which have no utility beyond cryptocurrencies. Proof-of-Useful Work (PoUW) has emerged as an alternative whose mining objective is expected to provide societal utility. Despite numerous designs, PoUW lacks practical relevance and theoretical scrutiny. In this paper, we provide a systematization of knowledge (SoK) on PoUW, focusing on security-economic trade-offs. We build the taxonomy to discuss core principles (difficulty adjustment, verifiability, etc.), architecture, trade-offs, and economic incentives. We examine more than 50 PoUW constructions where we find recurring shortcomings. We introduce a formal economic model of PoUW for miner incentives, solution reusability, and external market value to the security budget. To validate our hypothesis, we employ a Toulmin-based evaluation of claims on the security and energy efficiency of these constructions. Our findings show that PoUW is actually not as useful as expected, since the economic and societal utility do not contribute to the security budget. Finally, we highlight design recommendations for PoUW that integrate verifiable computation, partial incentive allocation, and utility-aware difficulty adjustment.

In this work, we investigate whether the cost of two-party ECDSA signing can be brought within the realm of plain ECDSA signing. We answer the question in the affirmative for the case of communication complexity, by means of a new signing protocol. Our protocol consumes bandwidth linear in the security parameter, and hence the size of an ECDSA signature. Our scheme makes only blackbox use of generic tools---Oblivious Transfer during key generation, and any Pseudorandom Function when signing. While computation complexity is not asymptotically optimal, benchmarks of our protocol confirm that concrete costs are the lowest known for ECDSA signing. Our protocol is therefore the most concretely efficient in the literature on all fronts: bandwidth, computation, and rounds.

On a technical level, our protocol is enabled by a novel Pseudorandom Correlation Function (PCF) for the Vector Oblivious Linear Evaluation correlation over a large ring. The PCF relies on one-way functions alone, and may be of independent interest.

Our scheme supports standard extensions, such as pre-signing, and including backup servers for key shares in a $(2,n)$ configuration.

The hardness of finding isogenies of degree $d$ between supersingular elliptic curves is a fundamental assumption in isogeny-based cryptography. Let $E_1$ and $E_2$ be supersingular elliptic curves defined over $\mathbb{F}_{p^2}$, and let $d>p^{1/2}$ be smooth. At CRYPTO~2024, Benčina et al.\ proposed an algorithm with time complexity $\widetilde{O}(\max\{p^{1/2}, d/p^{5/8}\})$ in the classical setting and $\widetilde{O}(\max\{p^{1/4}, d^{1/2}/p^{1/4}\})$ in the quantum setting.

In this work, we first observe that their analysis omits a sub-exponential factor $\exp(O(\log^{3/4} p))$. We then improve their result to $\widetilde{O}(\max\{p^{1/2},\exp(O(\log^{4/5} p)) \cdot d/p^{2/3}\})$ classically and $\widetilde{O}(\max\{p^{1/4}, \exp(O(\log^{4/5} p)) \cdot d^{1/2}/p^{1/3}\})$ quantumly. Our approach relies on small-root bounds for Coppersmith’s method applied to a four-variable integer equation. To this end, we adapt the explicit asymptotic formulas for small-root bounds introduced by Feng et al.\ (CRYPTO~2025) in the modular setting to the integer setting. As an additional application, we strengthen the attack of Benčina et al.\ on a signature scheme introduced at ACNS~2024, reducing its security by 9 bits. We expect that these refined techniques for Coppersmith’s method will be valuable for further post-quantum cryptanalysis.

We present a simple range-proof mechanism for Pedersen commitments that avoids per- transaction heavy ZK verification and pairings. The idea is to commit once to a Merkleized range table of points {(U, aX·G)}X∈{1,...,2n} for a secret a ∈ Zq and a public anchor U = a·B. At transaction time, a prover shows set membership of the leaf (U, ax · G), proves via a Chaum–Pedersen DLEQ that logB U = logC C′ where C′ = a · C and C is the Pedersen commitment, and finally proves (Schnorr) that C′ − (ax·G) lies in the H-direction. These three checks enforce x to be the in-range value indexed by the Merkle leaf while preserving privacy. Verification costs a single Merkle proof plus a DLEQ and a Schnorr discrete-log proof over an elliptic curve group.

Garbled circuits with one-bit-per-gate communication were recently introduced by Liu et al. (BitGC, Eurocrypt 2025), Meyer et al. (Crypto 2025), and Ishai et al. (Crypto 2025). However, these works focus primarily on the theoretical communication complexity, leaving open questions about practical computational efficiency. In this paper, we present a set of optimizations that substantially improve its practical efficiency. First, we eliminate key barriers to enable SIMD support to BitGC, leading to a substantial speedup in its homomorphic operations. Second, we demonstrate that XOR gates can be garbled without any communication, improving both efficiency and simplicity. Finally, we present a computationally efficient garbling scheme that requires zero communication for XOR gates and only 5 bits per AND gate. When applied to an AES-128 circuit, our fastest garbling scheme generates a garbled circuit of just 4 KB in 3 minutes on a single CPU core.

Secret sharing is a foundational cryptographic primitive for sharing keys in distributed systems. In a classical $(n,t)$-threshold setting, it involves a dealer who has a secret, a set of $n$ users to whom shares of the secret are sent, and a threshold $t$ which is the minimum number of shares required to recover the secret. These schemes offer an \textit{all-or-nothing} security approach where less than $t$ shares reveal no information about the secret. But these guarantees are threatened by side-channel attacks which can leak partial information from each share. Initiated by Benhamouda et. al. (Crypto'18), the security of linear secret sharing schemes has been studied for bounded leakage models, which assume that the adversary can leak bounded functions of each share. However, this model does not translate into real-world attacks, as physical side-channels are inherently noisy. The $\delta$-noisy channel model, proposed by Prouff and Rivain (Eurocrypt’13), is a general leakage framework which captures the noisy behaviour of side-channels. But the security for this model has proven difficult to analyze even for $(n,n)$-threshold schemes. The best known guarantees due to Duc et. al. (Eurocrypt'14), show that the adversary has at most $(\delta \cdot\mathcal{O}(n) \cdot q)^{n}$ advantage compared to guessing blindly, where $\mathbb{F}_q$ is the underlying field. In this work, we study the security of linear secret sharing schemes with $\delta$-noisy leakage, and show bounds on the mutual information (MI) and statistical bias ($\Delta^{\mathrm{TV}}$) security metrics. Our results are based on the Fourier analytical framework, first used by Benhamouda et. al. (Crypto'18), adapted to the $\delta$-noisy model. Informally, for some security parameter $\eta\le \min{\{1,2\delta\}}$, the Poisson's summation formula enables us to bound the ratio between the observed leakage for some given secret, and leakage under independence as $(1\pm \eta^t)$. This is then used to show a) $(n,t \ge \tau (n+1))$-threshold schemes over $\mathbb{F}_q$ have at most $\mathcal{O}(q^{-t(\gamma+1-1/\tau)})$ leakage, given $\eta \le q^{-\gamma}$; and consequently b) for $(n,n)$-threshold schemes the guessing advantage is at most $(q-1) \cdot \eta^n = \mathcal{O}(q^{1/n} \cdot \delta)^n$. Our results for the first time remove the field-size loss in security guarantees for $(n,n)$-threshold schemes. Furthermore, for $(n,t)$-threshold schemes, our results imply that the known security barrier of $t \ge 0.5n$ is an artifact of the bounded leakage model. This work can be viewed as a next step towards closing the gap between theory and practice in leakage resilient cryptography.

Multivariate quadratic problem over a finite field, a NP-hard problem, is also considered as one of the hard problems for cryptanalytic-relevant quantum computers. It is the foundation of multivariate quadratic-based cryptography and several post-quantum digital signature schemes initially proposed in 1990s. Patarin’s unbalanced Oil-and-Vinegar (UOV) scheme is the oldest MQ signature algorithm that remain secure against large-scale cryptanalytic-relevant quantum computers. UOV has compact signature size and succinct verification time. However, it suffers from a very large public key size. Subsequently, UOV-based variants have focused on minimizing the size of central map. MAYO, a candidate advanced to NIST’s round 2 additional post-quantum digital signatures, is based off the UOV algorithm with whipped structure to reduce public key size. In this paper, we present a theoretical framework of the proposed cryptanalysis. It targets the construction of valid signatures during the signing phase. This attack allows efficient extraction of secret oil vectors from the public signatures, facilitating the complete recovery of the entire secret oil space O. Finally, we show that this attack is applicable to parameter sets of all three security level of all versions of MAYO.

Traceable Ring Signatures (TRS) were introduced by Fujisaki and Suzuki~[PKC'07], where a trace algorithm can publicly check if two signatures with the same event label were generated by the same signer (linkability). In addition, if the two signatures correspond to different messages, then the signer's identity is revealed (traceability). Following [PKC'07], most subsequent works adopt the same definitions and consider three security properties, anonymity, linkability, and exculpability. [PKC'07] proved that the latter two properties together imply unforgeability, a fundamental requirement for all signature-like primitives.

~~~~In this work, we identify a gap in the aforementioned proof, which arises from the insufficient consideration of linkability and exculpability in [PKC'07]. To address this, we revisit the syntax and security notions of TRS, and close this gap by defining extended linkability and extended exculpability. Building on these, we design a new framework of TRS from PseudoRandom Functions (PRF) and Zero-Knowledge Proofs of Knowledge (ZKPoK) that supports $O(1)$ tracing, provided that both two signatures are valid. This constitutes a substantial improvement over existing approaches---all of which require $O(n)$ tracing with $n$ the size of the ring---and elevates TRS to a level of practicality and efficiency comparable to Linkable Ring Signatures (LRS), which have already achieved widespread deployment in practice. Finally, we instantiate our generic framework from the DDH assumption and leverage the Bulletproofs [S\&P'18] to construct a TRS scheme with log-size signatures. The proposed scheme achieves highly optimized signature sizes in practice and remains compatible with most existing DLog-based systems. On Curve25519, the signature size is $(128 \cdot \log n + 736)$ bytes, which to our best knowledge is the shortest LRS scheme for a ring $n \ge 19$.

The protection of executable code in embedded systems requires efficient mechanisms that ensure confidentiality and integrity. Belkheyar et al. recently proposed the Authenticated Code Encryption (ACE) framework, with ChiLow-(32 + $\tau$) as the first instantiation of ACE2 at EUROCRYPT 2025. The design of ChiLow-(32 + $\tau$) is based on a 32-bit tweakable block cipher with a quadratic nonlinear layer, known as ChiChi (denoted by $\chi\!\!\chi$), and a nested tweak key schedule optimized for secure code execution under strict query limits.

In this work, we study the resistance of ChiLow to integral cryptanalysis. We identify new integral distinguishers in both the single-tweak and related-tweak models. Using these results and a nested strategy to recover all round tweaks, we present a key-recovery attack on 7 out of 8 rounds of ChiLow. The central contribution of our work is that it resolves the challenge of deriving the master key from the recovered round tweaks, an open problem highlighted by the designers and in a recent cryptanalysis by Peng et al. The attack on 7 rounds requires $2^{6.32}$ chosen ciphertexts, has a time complexity of about $2^{121.75}$ encryptions, and requires negligible memory.

Function Secret Sharing (FSS) schemes enable sharing efficiently secret functions. Schemes dedicated to point functions, referred to as Distributed Point Functions (DPFs), are the center of FSS literature thanks to their numerous applications including private information retrieval, anonymous communications, and machine learning. While two-party DPFs benefit from schemes with logarithmic key sizes, multi-party DPFs have seen limited advancements: $O(\sqrt{N})$ key sizes (with $N$, the function domain size) and/or exponential factors in the key size.

We propose a DDH-based technique reducing the key size of existing multi-party schemes. In particular, we build an honest-majority DPF with $O(\sqrt[3]{N})$ key size. Our benchmark highlights key sizes up to $10\times$ smaller (on realistic problem sizes) than state-of-the-art schemes. Finally, we extend our technique to schemes supporting comparison functions.

Multi-key fully homomorphic encryption (MK-FHE) enables secure computation over ciphertexts under different keys, but its practicality is hindered by inefficient bootstrapping.In this work, we propose HELIOS, a new MK-FHE scheme with highly efficient bootstrapping. Our bootstrapping framework improves upon the best-known complexity, reducing it from ${O}(dkn)$ to ${O}(kn)$, and further to ${O}(\sqrt{kn})$ under parallelization, where $d$ is the gadget length (typically scaling with the number of parties $k$) and $n$ is the LWE dimension.The framework consists of two main components: (i) a ciphertext conversion algorithm that transforms a multi-key LWE ciphertext into $k$ vectorized RLWE ciphertexts via $k$ optimized blind rotations and $dk$ key-switching operations, and (ii) a hybrid accumulator that aggregates these into a single multi-key RLWE ciphertext. We implemented HELIOS on both CPU and GPU platforms to demonstrate its practicality. For $k=16$, we achieve $3.3\times$ and $7.2\times$ improvements on CPU, compared to the state-of-the-art schemes by Kwak et al. (PKC 2024) and by Xiang et al. (ASIACRYPT 2024), respectively. We further achieve a $195\times$ GPU acceleration, compared to our CPU runtime. As a byproduct, we design a new distributed-decryption protocol, which allows us to obtain a ciphertext with a small noise bound, and thus does not blow up the parameters.