Standard symmetric encryption schemes, such as AES, other block ciphers and their modes, and stream ciphers, are highly effective and efficient for many standard scenarios. All of them have been derived from Shannon's 1948 seminal work on the communication theory of secrecy systems. Here we look at other settings where the situation is somewhat different from the standard one: \textit{e}.\textit{g}., while the encryption process may fail to update the ciphertext a limited number of times, or bits of the ciphertext are omitted: can the decryption process nevertheless recover the message in its entirety? Another situation is when encrypting a bulk of messages that must be packed together within the same dedicated ciphertext space (i.e., encryption done holographically on a clockchain space). Can a process compress the messages this way? Another issue is adding a further hiding layer to ciphertexts, like hiding the number of messages packed together, or even attempting to hide that encryption (rather than another cryptographic protocol) takes place? Can the new paradigm be based directly on a simple cryptographic (preferably post-quantum) tool? Note that the above scenarios, involving data compression and correction, are naturally derived from Shannon's other 1948 seminal work on Information Theory.   This paper introduces Encryption via Hash (EvH), a A new symmetric randomized cipher built upon a pseudorandom keyed cryptographic hash (i.e., Message Authentication Code, MAC functions), and Bloom Filters. EvH's core novelty lies in its prefix decryption capability. This unique property enables a paradigm in which encryption is tightly integrated with online compression and robust resilience to omission errors of the encryption process. By representing message prefixes in a Bloom filter, EvH allows a receiver to decrypt the initial part of a message even if subsequent data are lost, and to recover from some prefix omissions during encryption. At times, these built-in new properties may be significant (even beyond the above examples). Furthermore, this prefix-based approach facilitates simultaneous compression during the decryption phase by dynamically pruning invalid message continuations, using shared $\mu$-gram dictionaries or employing search via Large Language Models (LLMs). The result is a stateless and parallelizable cipher that, while computationally distinct from traditional ciphers, offers unique functional benefits for specific use cases, at the cost of correctness being ensured only probabilistically (as in compression processes), though the error can be well controlled and made significantly small.

We present the first systematic study on communication-efficient evaluation of the lightweight cipher family Ascon within secure multi-party computation (MPC). By leveraging Ascon’s parallel, bit-oriented structure, we adapt its design using Reverse Multiplication-Friendly Embeddings (RMFEs, introduced by Cascudo et al.\ in CRYPTO'18) in a single-circuit evaluation, enabling efficient packing of groups of bits into field elements. Our protocol, which uses relatively small RMFEs, achieves substantial reductions in communication cost compared to baseline MPC protocols. For example, in a medium-sized setting (with $n = 13$ MPC parties), our protocol reduces the communication cost for an Ascon permutation by roughly $38\%$. For large amounts of parties (e.g., $n=255$), the reduction can reach $50\%$. These improvements are achieved even though RMFEs only pack a few bits per field element, due to favorable amortization of both substitution and linear layers. We also provide a Boolean circuit implementation of Ascon in the MP-SPDZ framework, enabling straightforward benchmarking. Our findings are particularly beneficial for bandwidth-constrained environments where the use of lightweight ciphers, such as Ascon, is necessary due to the resource limitations of client devices, as in the case of transciphering data from IoT sensors. Since our optimizations target the Ascon permutation, they naturally extend to all cryptographic modes (encryption, decryption, hashing) defined for the standard.

Privacy-preserving machine learning (PPML) is a powerful tool for multiple parties to collaboratively train a model or perform model inference without exposing their private data in the context of Internet of things. A key challenge in PPML is the efficient evaluation of non-polynomial functions. In this work, we propose NASE, a neat and accurate secure exponentiation protocol for radius basis function (RBF) kernel evaluation. Leveraging the property of the RBF kernel, NASE enjoys a lightweight construction that reduces computation overhead by up to 1.65$\times$ and communication overhead by up to 3.97$\times$ compared to SIRNN, the prior SOTA framework for secure exponentiation published in IEEE S\&P 2021. Taking NASE as the foundation stone, we propose a privacy-preserving two-party kernel SVM training protocol. Based on BFV scheme and MPC technique, we introduce group-batch sampling for sampling in ciphertext and propose the partial rotation method tailored to our scenario to optimize dot product computation. Additionally, we propose an error-tolerant $DReLU$ protocol for secure sign evaluation of secret sharings over a prime field that reduces the communication cost by around $\frac{1}{3}$ compared to the existing method. Our protocol achieves model accuracy comparable to plaintext training according to experiments on real-world datasets, and an order-of-magnitude reduction in both communication and computation overhead is attained compared to the previous work.

Proving statements over integers is crucial in modern cryptographic protocols because certain computations, such as range proofs and Diophantine satisfiability, are more efficiently expressed over integers. Currently, the prevailing approach to achieve this is to convert the integer relations into statements tractable for proof systems over a finite field $\mathbb{Z}_p$. However, finding these corresponding tractable statements over $\mathbb{Z}_p$ is not always straightforward, and in practical schemes, the conversion often introduces computational overheads. Therefore, there is a growing interest in proving the statements directly over integers. Due to the significant applicability of inner-product arguments (IPA) in constructing succinct proof systems, in this work, we extend them to work natively in the integer setting. We introduce and construct inner-product commitment schemes over integers that allow a prover to open two committed integer vectors to a claimed inner product. The commitment size is constant and the verification proof size is logarithmic in the vector length. The construction significantly improves the slackness parameter of witness extraction, surpassing the existing state-of-the-art approach. Our construction is based on the folding techniques for Pedersen commitments defined originally over $\mathbb{Z}_p$. We develop general-purpose techniques to make it work properly over $\mathbb{Z}$, which may be of independent interest. Building upon our IPAs, we first present a novel batchable argument of knowledge of nonnegativity of exponents that can be used to further reduce the proof size of Dew-PCS (Arun et al., PKC 2023). Second, we present a construction for range proofs that allows for extremely efficient batch verification of a large number of range proofs over much larger intervals. We also provide a succinct zero-knowledge argument of knowledge with a logarithmic-size proof for more general arithmetic circuit satisfiability over integers.

Sigma protocols are fundamental cryptographic tools, serving as the foundation of many practical schemes—most notably, the Schnorr identification and signature schemes. To prove the security of Sigma protocols, one typically reduces breaking a Sigma protocol to solving a presumed hard problem (e.g., computing the discrete logarithm in a certain group). In many settings, however, these reductions are not tight: given an adversary that breaks a Sigma protocol with probability $\varepsilon$, the reduction only yields an adversary for the underlying problem with probability $\varepsilon^2$. This quadratic loss affects efficiency, as it forces choosing larger security parameters to reach a target security level. In this work, we show that this quadratic loss is inherent for two natural classes of reductions. For interactive protocols, we prove it for uniform-challenge, black-box reductions, which query the adversary using uniformly sampled challenges. For non-interactive protocols (i.e., in the random-oracle model), we prove it for weakly programmable, black-box reductions, which answer the adversary’s oracle queries with uniformly sampled outputs. Applying our bounds to the reductions from Schnorr identification and signatures to discrete logarithm yields lower bounds that match known positive results—namely, the classical worst-case reduction of Pointcheval and Stern (Journal of Cryptology, 2000) and the higher-moment reduction of Rotem and Segev (Journal of Cryptology, 2024). Our approach reduces the analysis of such reductions to the values of simple hitting games—combinatorial games that we introduce. Bounding these games is our main technical contribution, and we believe these bounds can enable more modular proofs of related results.

A major bottleneck in secure neural network inference using Fully Homomorphic Encryption (FHE) is the evaluation of non-linear activation functions like ReLU, which are inefficient to compute under FHE. State-of-the-art solutions approximate ReLU using high-degree polynomials, incurring significant computational overhead. We propose novel methods for functional bootstrapping with CKKS, and based on these methods we present RBOOT, an optimized framework that seamlessly integrates ReLU evaluation into CKKS bootstrapping, significantly reducing multiplication depth and boosting efficiency. Our key insight is that the EvalMod step in CKKS bootstrapping is composed of trigonometric functions, which can be transformed into various common non-linear functions. By co-optimizing these components, we can exploit such non-linearity to construct ReLU (and other non-linear functions) within the bootstrapping process itself, greatly reducing the computation overhead. Results on four widely used CNN models show that RBOOT achieves $2.77\times$ faster end-to-end inference and $81\%$ lower memory usage compared to previous polynomial approximation works, while maintaining comparable accuracy.

Mix networks (mix-nets) offer strong anonymity by routing client packets through intermediary hops, where they are shuffled with other packets to obscure their origins from a global adversary monitoring all communication exchanges. However, this anonymity is achieved at the expense of increased end-to-end latency, as packets traverse multiple hops (incurring routing delays) and experience additional delays at each hop for shuffling purposes. Consequently, the overall latency for delivering a message—comprising multiple packets—is determined by the packet with the highest combined routing and shuffling delay, which can significantly degrade the client experience, particularly in latency-sensitive applications. To address this issue, our work \textbf{first} derives the theoretical statistics of the total latency experienced by a message, revealing a clear correlation between latency and the number of packets. \textbf{Second}, we propose two approaches to reduce this total latency. First, we present a method to adjust the shuffling delays at each hop, offsetting potential anonymity loss by integrating client-generated noise, backed by differential privacy guarantees. Next, we introduce packet-aware routing techniques, offering two novel methods that prioritize messages with more packets, forwarding them through faster links. However, this may cause certain nodes to be overloaded with disproportionate traffic. To solve this, we \textbf{third} introduce an efficient load-balancing algorithm to redistribute traffic without compromising the packet-aware nature of the routing. \textbf{Finally}, through comprehensive analytical and simulation experiments, we validate our theoretical latency bounds and evaluate the efficacy of our latency management strategies. The results confirm both methods substantially reduce latency with minimal impact on anonymity, while the strategic routing method remains robust against advanced adversarial attacks. Note that this paper is an extended version of PARSAN-Mix (accepted and presented at ACNS 2025), mainly aimed at providing full proofs of the theorems together with additional empirical analysis.

This paper presents an efficient framework for private Transformer inference that combines Homomorphic Encryption (HE) and Secure Multi-party Computation (MPC) to protect data privacy. Existing methods often leverage HE for linear layers (e.g., matrix multiplications) and MPC for non-linear layers (e.g., Softmax activation functions), but the conversion between HE and MPC introduces significant communication costs. The proposed framework, dubbed BLB, overcomes this by breaking down layers into fine-grained operators and further fusing adjacent linear operators, reducing the need for HE/MPC conversions. To manage the increased ciphertext bit width from the fused linear operators, BLB proposes the first secure conversion protocol between CKKS and MPC and enables CKKS-based computation of the fused operators. Additionally, BLB proposes an efficient matrix multiplication protocol for fused computation in Transformers. Extensive evaluations on BERT-base, BERT-large, and GPT2-base show that BLB achieves a $21\times$ reduction in communication overhead compared to BOLT (S&P'24) and a $2\times$ reduction compared to Bumblebee (NDSS'25), along with latency reductions of $13\times$ and $1.8\times$, respectively, when leveraging GPU acceleration.

As an ISO/IEC standard, RIPEMD-160 has been extensively studied for (Semi-Free-Start) collision attacks. A significant breakthrough was achieved at FSE 2024 with the first 41-, 42-, and 43-step SFS collision attacks, which leveraged an automatic search model (EUROCRYPT 2023) and a message modification strategy (FSE 2020). However, these attacks are limited by reliance on heuristic objective functions and suboptimal message modification techniques. This paper enhances the existing framework from two perspectives. Firstly, we refine the automatic search model by incorporating a holistic objective function that considers all critical probability components, moving beyond simple Hamming weight. Secondly, we introduce two generic techniques to further improve (SFS) collision attacks: the first application of differential clustering and a dedicated message modification strategy. As a result, we present the first valid SFS collision attack on 44-step RIPEMD-160. Additionally, we significantly reduce the time complexities of existing attacks on 41-, 42-, and 43-step variants, making it feasible to find colliding message pairs for 41- and 42-step versions within practical time for the first time.

In this work, we propose a novel framework called PolySys for modeling and designing leakage attacks as constraint-solving algorithms over polynomial systems. PolySys formalizes the design of attacks using invertible encodings, structural and leakage equations, and efficient constraint-solving algorithms including SAT and constraint solvers. It is capable of modeling resolution, known-data, and inference attacks for common leakage patterns. To demonstrate the practicality of our framework, we implement a PolySys attack engine in Python and apply it to state-of-the-art query recovery, data resolution, and query inference attacks on point and range multi-maps. Our results show that PolySys outperforms all existing attacks under identical assumptions, achieving up to 60× higher recovery rates in some scenarios. While scalability remains a challenge for larger datasets, PolySys represents a promising step toward a general-purpose framework for designing leakage attacks. We believe future work can further enhance its efficiency to scale to larger and more complex workloads.

The CRO Trilemma formalizes the inherent incompatibility between confidentiality, reliability, and legal opposability in proof systems. This paper provides the complete Universal Composability (UC) security proof for the ZK-NR protocol, a layered architecture designed to approach this bound. We model each dialectical layer (Iron, Gold, Clay) as an ideal functionality with erasure semantics and prove indistinguishability between real and ideal executions under post-quantum assumptions. The results establish the composable security of ZK-NR and formally achieve a CRO index Γ_CRO < 0.4 + negl(λ) against adaptive contextual adversaries.

Many data types, such as video and audio, consist of sequential elements where both integrity and order are essential for authenticity. In practice, verifiers often access only partial sequences due to privacy or bandwidth constraints, motivating the use of vector commitments (VCs) for verifiable partial disclosure. However, VC construction requires a trusted committer, typically within a secure module on the device, and maintaining such commitments is challenging for resource-constrained hardware. For example, in CCTV pipelines, a trusted module processing continuous streams must store and update large VC structures, leading to prohibitive memory and computational overhead. This work addresses this deployment bottleneck by introducing an efficient pipeline for verifiable VC construction that offloads computation from constrained devices while preserving trust. The source device computes and signs a cumulative hash over the data stream, requiring only constant memory. Later, an untrusted prover reconstructs the VC from the raw data and produces a zero-knowledge proof that the construction is consistent with the signed hash chain. This design eliminates the need for trusted storage of intermediate VC state and enables verifiable partial disclosures from the reconstructed VC. A key challenge is the high cost of proving the full VC construction. We address this by designing a folding-based zkSNARKs system tailored to streaming workloads. We implement and evaluate the system on a constrained device (Raspberry Pi Zero) as the source and a consumer-grade prover (midrange laptop). Our results show that direct VC maintenance on the source device requires hundreds of megabytes of memory and is computationally infeasible on trusted platform standards for even moderate workloads (e.g., 30 minutes of video). In contrast, our approach reduces the trusted device's memory footprint to constant size, while the midrange laptop can generate the proof of full VC construction in approximately 2 minutes for the same workload. Furthermore, the proof size is around 10 KB regardless of the original size of data and verification time is sub-second. Our implementation is available open source at: https://github.com/zero-savvy/proven-view.

While consistency and liveness are the defining properties of ledger consensus, fair ordering has emerged as an independent consideration whose importance is underscored by the observation of real world transaction inclusion strategies that manipulate fairness such as Miner Extractable Value. Receiver-order fairness is a fine-grain notion of fairness that determines the order of any two submitted transactions based on the two sequences of reception timestamps for the two transactions across all nodes in the network. Given this information, ledger serialization can be viewed as the social choice problem of producing the most agreeable transaction order based on the "preferences" of the miners or validators. In this work, our contribution is three-fold: (i) We put forward a formal Universally Composable definition for order fairness that encompasses receiver order fairness as well as input causality. (ii) We design a novel ledger protocol that preserves input causality and receiver order fairness. (iii) We capture in our composable definition and construction the role that transaction fees play when dealing with fairness. Our protocol is based on a novel YOSO-style approach that allows encrypting transactions for a short period of time. Notably, the communication complexity required to decrypt the transactions is independent of the number of encrypted transactions. To the best our our knowledge, we are the first to provide a YOSO-style approach with such asymptotic complexity while relying on standard cryptographic assumptions.

We study a secondary construction of Boolean functions, which generalizes the direct sum and the indirect sum. We detail how these two classic secondary constructions are particular cases of this more general one, as well as two known generalizations of the indirect sum. This unifies the known secondary constructions of Boolean functions. We study very precisely the Walsh transform of the constructed functions. This leads us to an interesting observation on the Walsh transforms $W_g,W_{g'},W_{g''}$, and $W_{g\oplus g'\oplus g''}$ when $g,g',g''$ are Boolean functions such that $(g\oplus g')(g\oplus g'')$ equals the zero function.

Recent work showed that ML-based attacks on Learning with Errors (LWE), a hard problem used in post-quantum cryptography, outperform classical algebraic attacks in certain settings. Although promising, ML attacks struggle to scale to more complex LWE settings. Prior work connected this issue to the difficulty of training ML models to do modular arithmetic, a core feature of the LWE problem. To address this, we develop techniques that significantly boost the performance of ML models on modular arithmetic tasks—enabling the models to sum up to $N=128$ elements modulo $q \le 974269$. Our core innovation is the use of custom training data distributions and a carefully designed loss function that better represents the problem structure. We apply an initial proof of concept of our techniques to LWE specifically and find that they allow recovery of 2x harder secrets than prior work. Our techniques also help ML models learn other well-studied problems better, including copy, associative recall, and parity, motivating further study.

Cryptocurrencies, which have gained significant adoption in recent years, face ongoing challenges in scalability and privacy. Payment Channel Hubs (PCHs) constitute a solution to both issues by shifting transactions off the public ledger. Various PCH constructions have been proposed, offering different degrees of unlinkability, efficiency, and inter- operability. However, regulatory compliance remains a significant con- cern, particularly under emerging frameworks like the EU’s Markets in Crypto-Assets (MiCA) regulation and FATF Travel Rule requirements. This work addresses a gap in existing PCH constructions: the lack of regulatory-compliant auditability mechanisms. While concurrent work AuditPCH attempts to address this challenge, it suffers from fundamen- tal limitations, including reliance on channel closures for auditing, vul- nerability to unilateral de-anonymization by the hub, and lack of formal security guarantees for the auditing process. Our approach fundamen- tally differs by providing targeted, non-disruptive auditability that al- lows auditability for high-risk payments while preserving unlinkability for the rest. To achieve this, we present Verifiable Linkable Randomiz- able Puzzles (VLRP), a new cryptographic primitive that enables a party to commit to a secret using two distinct keys: a verifiability key (VK) and an auditability key (AK). This primitive provides (i) verifiability that the owner of the VK issued the commitment, (ii) the ability to ran- domize the commitment to ensure unlinkability, even for the owner of the VK, while still allowing traceability using the AK, and (iii) collaborative auditing that prevents unilateral de-anonymization. We then present Auditable Unlinkable Payment Channel Hubs, AUPCH, a PCH built on VLRP that offers auditability guarantees with stronger se- curity guarantees than existing approaches. AUPCH provides modular integration with existing PCH frameworks (A2L, BlindHub), operates without requiring channel closures, and ensures that auditing requires collaboration between hub and auditing agent, preventing abuse by ei- ther party alone. Crucially, our approach acts as a wrapper around exist- ing PCH implementations, requiring only replacing randomizable puzzle calls with VLRP calls, a minimal change that dramatically reduces de- ployment complexity compared to building new systems from scratch.

Information Set Decoding (ISD) refers to a class of algorithms designed to decode arbitrary linear codes over finite fields. It is among the state-of-the-art methods for solving the Syndrome Decoding Problem (SDP), which lies at the core of code-based cryptography. Since most cryptographic systems operate over the binary field, ISD algorithms are generally designed for this setting. However, emerging cryptographic systems, such as SDitH, that rely on the SDP over non-binary fields, make research into non-binary ISD increasingly relevant. While there have been numerous improvements to ISD algorithms for binary fields, generalizations of these improvements to non-binary fields have resulted in only modest runtime improvements. The only technique which applies specifically to non-binary fields was proposed only last year by Carrier, Hatey and Tillich and consists in solving the SDP over the projective space. In this paper we continue along this line of research and introduce a novel technique to perform ISD in non-binary fields. Our key idea consists in speeding-up the enumeration of low weight vectors by enumerating only the supports and not the actual values, since these can be recovered by solving a (small) linear system. This idea is at the core of LA-ISD, the first algorithm we propose in the paper. We further enhance it by exploiting a meet-in-the-middle search leading to MitM-LA, the second algorithm we propose in this paper. We analyze our algorithms in both the finite and asymptotic regimes and show that they compare well with competitive solutions. In particular, LA-ISD results in the best memory-less algorithm, while MitM-LA is (slightly) faster than the state-of-the-art algorithm by Carrier, Hatey and Tillich for many parameter-sets as well as asymptotically.

Abstract. Linear algebraic relations, such as inner products ⟨a, b⟩, underlie a wide range of cryp- tographic constructions, including zero-knowledge proofs, SNARKs, polynomial commitment schemes, and more. In this work, we consider group-scalar relations, i.e., statements of the form ⟨A, b⟩, where A is a vector of group elements and b is a vector of field elements. In many crypto- graphic settings, it is necessary to prove relationships between group elements like public keys, or other cryptographic objects without access to the underlying discrete logarithms. Our results are as follows: – At the protocol level, we introduce the first Inner Product Argument (IPA) that specifically fo- cuses on group-scalar relations in bilinear groups. It achieves constant-size proofs and constant- time verification, maintaining commitments and arguments entirely in the source group. Our techniques enable new applications and significantly improve efficiency compared to state-of- the-art IPAs such as Dory (TCC ’21) and GIPA (Asiacrypt ’21), which rely on recursive folding techniques and thus have logarithmic proofs and verification time. We prove security in the Algebraic Group Model under the q-DHE and q-DL assumptions. – At the primitive level, we present a new class of functional commitments for linear functions over group-scalar elements. It enables even more applications such as polynomial commit- ments for values hidden inside group exponentiations. – To showcase our contributions, we demonstrate new applications—most notably, we introduce the notion of dynamic threshold verifiable random functions, which we believe to be a valuable tool for distributed randomness generation. We further present dynamic threshold signatures without random oracles, polynomial commitments over group-encoded inputs, and their ap- plications to oblivious proofs. Our results provide modular and efficient tools to build cryptographic protocols without typical SNARK frameworks, simplifying real-world deployments. To demonstrate the practicality of our contributions, we provide an implementation and related benchmarks.

Subversion-resilient cryptography has garnered increasing attention in recent years due to growing concerns about cryptographic subversions in real-world applications. Among the existing countermeasures, the notion of cryptographic reverse firewalls (RFs), initially proposed by Mironov and Stephens-Davidowitz (EUROCRYPT 2015) and later extended by Chakraborty et al. (EUROCRYPT 2022) to the universally composable (UC) model, has proven to be a powerful tool for building subversion-resilient cryptographic protocols. In this work, we focus on designing subversion-resilient authenticated key exchange (AKE) protocols, which are critical components of secure Internet communication. We present the f irst generic framework for subversion-resilient UC-secure AKE protocols leveraging RFs. In spired by the state-of-the-art advancements by Chakraborty et al. (ASIACRYPT 2024), we address subversions: where a party’s implementation is covertly altered to exfiltrate secrets or behave unpredictably when triggered by adversarial inputs. A key contribution of our work is the introduction of a new AKE functionality which, for the first time, incorporates security against key control, an essential aspect of achieving subversion resilience. We also provide a concrete instantiation of our framework, demonstrating its feasibility in practice. Notably, the RFs in our proposed AKE protocol are transparent, an important property of RF as defined originally, which allows deployment of RF without all parties explicitly knowing about it and allows robust security. Achieving transparency for RFs has been widely regarded as challenging, particularly when addressing broader subversion attacks (e.g., input-trigger attacks) in the UC model. Our approach, thus, not only advances the state of AKE protocol design, but also offers insights into building other subversion-resilient protocols in the UC model using transparent RFs.

This paper introduces DAWN, a compact and efficient NTRU encryption utilizing double encoding, which is provably secure under the NTRU assumption and the Ring-LWE assumption. We propose a technique for NTRU encryption called the zero divisor encoding. Unlike the polynomial encoding technique proposed by Hoffstein and Silverman (2001) and the vector encoding technique proposed by Zhang, Feng, and Yan in NEV (Asiacrypt 2023), our zero divisor encoding technique leverages the algebraic structure of the ring used in NTRU, enabling greater ciphertext compression while maintaining negligible decryption failure. We further develop a paradigm for NTRU encryption called the double encoding paradigm to maximize the potential of the zero divisor encoding. This paradigm transforms optimizing an NTRU-based encryption into constructing a better encoding within the NTRU context, providing more concrete direction for scheme development. Several previous NTRU encryptions can be situated within this paradigm with different parameters, facilitating direct comparison. We instantiate this paradigm based on the provably IND-CPA secure NTRU variant by Stehlé and Steinfeld (Eurocrypt 2011) to achieve an IND-CPA secure PKE, and subsequently employ the Fujisaki-Okamoto transformation to achieve an IND-CCA secure KEM. We present two parameter settings of DAWN: DAWN-$\alpha$ minimizes ciphertext size, achieving lengths of 436 bytes under NIST-I security and 973 bytes under NIST-V security; DAWN-$\beta$ minimizes the combined size of the public key and ciphertext, attaining combined sizes of 964 bytes under NIST-I security and 2054 bytes under NIST-V security. DAWN achieves superior compactness and performance among current lattice-based KEMs without introducing additional security assumptions. Compared to NEV (Asiacrypt 2023), the previously leading NTRU-based KEM in balancing compactness and performance, DAWN demonstrates 20%-29% greater compactness at approximate security levels and decryption failure probabilities, while executing 1.1X-2.0X faster in a complete ephemeral key exchange process.

A Password-Authenticated Key Exchange (PAKE) protocol allows two parties to jointly establish a cryptographically strong key, in the setting where the only information shared in advance is a low-entropy "password". The two standard security definitions for PAKE are the game-based one by Bellare, Pointcheval and Rogaway (BPR-security, EUROCRYPT 2000) and the Universally Composable (UC) one by Canetti et al. (EUROCRYPT 2005). It is well-known that UC-security implies BPR-security; however, there are a large number of variants of both definitions, and the relation between them is not entirely clear. In this work, we thoroughly study a variant of BPR-security by Katz, Ostrovsky and Yung (KOY-security, JACM 2009): 1. We show, via a counterexample, that UC-security does \emph{not} imply KOY-security; 2. We then prove that a variant of UC-security, called implicit-only UC-security (Dupont et al., EUROCRYPT 2018), implies KOY-security. Interestingly, we make the observation that KOY- and implicit-only UC-security essentially strengthen their standard counterparts in the same manner. We also present detailed explanations of all four security notions.

The notion of indifferentiability was proposed by Maurer et al. to bound the distinguishing advantage of a construction built on a public primitive, from a public random function. In Indocrypt'10, Mandal et al. have shown that the sum of two independent permutations is indifferentiable from a public random function up to $2^{2n/3}$ queries. Later in ACNS'15, Mennink and Preneel identified an analytical flaw of Mandal et al's result and revised the security bound to $2^{2n/3}/n$. In Eurocrypt'18, Bhattacharya and Nandi have improved their indifferentiable bound to $2^n$ queries, which was again identified as incorrect in the analysis by Gunsing et al. In this paper, we study the indifferentiability of a few other PRF constructions, namely STH and EDM constructions. We will show that neither STH nor STH2 is indifferentiable, which led us to propose a generalized version called gSTH. We have shown that gSTH achieves a tight $l$-bit security bound, where $l$ denotes the size of the constants in terms of bits used in the construction. While we show that EDM achieves a tight $n/2$-bit indifferentiable bound with respect to our proposed simulator, single-keyed EDM is not indifferentiable from a public random function. We would like to mention that all the proofs and the attacks have been done in the sequential indifferentiability model.

Layer-2 protocols are pivotal in enhancing the scalability of blockchain systems, enabling faster off-chain transactions while maintaining security. These protocols can bridge consensus-based blockchain systems and advanced applications, such as Multiparty Computation (MPC) protocols, often defined within the Universal Composability (UC) Framework. However, despite the existence of some UC-defined protocols, there is currently no comprehensive UC definition for isomorphic multiparty state channels, in particular that are not dependent on the ledger model: account or UTxO based ledger. These protocols depend heavily on timelock mechanisms and the accurate representation of time, which are challenging to model within the UC Framework. Our work addresses this gap by proposing a UC-based definition, i.e., functionality, for isomorphic multi-party state channels that realistically model timely actions of honest users, a critical feature for the security of the channel protocol. Moreover our definition is agnostic with respect to the ledger model. Additionally, we introduce an extended timelock-aided global ledger functionality and demonstrate the security of existing protocols, namely Hydra proposed by Chakravarty et al. (FC'21), under the UC Framework and our proposed functionalities. This contribution provides a robust foundation for developing secure and scalable off-chain protocols in blockchain ecosystems. Finally, we concretely provide the construction of the extension of the Hydra Protocol, only outlined by the original work, and also prove it secure under our framework.

Asynchronous complete secret sharing (ACSS) and asynchronous dynamic proactive secret sharing (ADPSS) are fundamental primitives for secret sharing and resharing in modern threshold systems, such as multi-party computation, distributed key management, and blockchain. However, existing ACSS constructions that employ homomorphic commitments incur notable computational overhead, while the lightweight-computation constructions require quadratic per-secret communication, limiting scalability as the number of parties grows. ADPSS constructions inevitably inherit these inefficiencies due to their tight coupling to the commitment-based ACSS and requiring at least quadratic cross-committee communication. To break these bottlenecks, we design GoSSamer, a concretely and asymptotically efficient protocol suite, where both our ACSS and ADPSS achieve (1) lightweight computation with only hash function and symmetric encryption; (2) asymptotically optimal, linear per-secret communication; (3) optimal resilience in asynchronous networks; and (4) post-quantum security. In GoSSamer-ACSS, we propose an original-evaluation propagation paradigm for linear communication without commitment‑requiring interpolation, which further unlocks our lightweight bivariate-polynomial-based degree checking for share verification. Building on this foundation, GoSSamer‑ADPSS contributes two further techniques: a consistency verification technique that decouples the ADPSS framework from the commitment-based ACSS, and a dual-committee reconstruction technique that yields linear per-secret communication. When deployed in distributed AWS instances, GoSSamer-ACSS reduces the runtime by 95.6% compared to the linear-communication scheme hbACSS (NDSS'22) and 45.8% compared to lightweight SS24 (JoC'24). GoSSamer-ADPSS reduces the runtime by at least 67.7% compared to LongLive (Usenix Security'23). Moreover, when applied to practical distributed key management systems, the GoSSamer-ACSS-based distributed key generation is 7-11x faster than DXK+23 (Usenix Security'23), and GoSSamer-ADPSS-based key resharing reaches a throughput of 1994 keys/s across 10-node committees, compared to 85 keys/s in LongLive.

In recent years, federated learning has gained significant momentum as a collaborative machine learning approach, particularly in the field of medicine. While the decentralized nature of federated learning provides greater security guarantees compared to traditional machine learning methods, it is still susceptible to myriad attacks. Moreover, as federated learning becomes increasingly ubiquitous in medicine, its use for classification tasks is expected to increase; however, maintaining patient data confidentiality remains a significant challenge, especially for genetic data. While previous works focus on utilizing Single Nucleotide Polymorphisms or numerical data, recent advances in gene sequencing amplify the importance of inference from DNA sequences. In this work, we introduce a novel framework for secure federated inference on nucleotide-based genotype data and provide a gateway to private inference through fully homomorphic encryption. A federated model with five local clients was created and trained before being encrypted with the TFHE cryptosystem and placed for inference. We tested multiple different local and global model architectures, including a standard neural network, a support vector machine, and an LSTM (long-short-term memory), and compared their respective abilities across accuracy, precision, recall, and runtime metrics. These frameworks successfully identified promoter sequences encoded within given DNA sequences, as well as whether a given sequence was a coding sequence or an intergenomic sequence, showing their potential applications in secure genomic data analysis in a federated context. Our work represents a crucial step in privacy-preserving federated inference on nucleotide-based data.

We present the first algorithm for computing class groups and unit groups of arbitrary number fields that provably runs in probabilistic subexponential time, assuming the Extended Riemann Hypothesis (ERH). Previous subexponential algorithms were either restricted to imaginary quadratic fields, or relied on several heuristic assumptions that have long resisted rigorous analysis. The heart of our method is a new general strategy to provably solve a recurring computational problem in number theory (assuming ERH): given an ideal class $[\mathfrak a]$ of a number field $K$, sample an ideal $\mathfrak b \in [\mathfrak a]$ belonging to a particular family of ideals (e.g., the family of smooth ideals, or near-prime ideals). More precisely, let $\mathcal{S}$ be an arbitrary family of ideals, and $\mathcal{S}_B$ the family of $B$-smooth ideals. We describe an efficient algorithm that samples ideals $\mathfrak b \in [\mathfrak a]$ such that $\mathfrak b \in \mathcal{S}\cdot\mathcal{S}_B$ with probability proportional to the density of $\mathcal{S}$ within the set of all ideals. The case where $\mathcal{S}$ is the set of prime ideals yields the family $\mathcal{S}\cdot\mathcal{S}_B$ of near-prime ideals, of particular interest in that it constitutes a dense family of efficiently factorable ideals. The case of smooth ideals $\mathcal{S} = \mathcal{S}_B$ regularly comes up in index-calculus algorithms (notably to compute class groups and unit groups), where it has long constituted a theoretical obstacle overcome only by heuristic arguments.

Doctolib is a popular healthcare platform, used by over 90 million users across France, Italy, and Germany. One of its main features is the secure data exchange between patients and doctors, with 7 million documents shared per month. Doctolib claims to provide the "world's first end-to-end encryption platform built for health applications". The encryption protocol, described in a Whitepaper and Github repository, relies on envelope encryption and lets users upload ciphertexts for the secure data exchange. The ciphertexts are stored and retrieved through a distributed system, consisting of a data server and a key server. To access the data, recipients fetch the ciphertexts and decrypt them with their private key. However, the platform does not require end-users to maintain any cryptographic keys themselves and instead relies on a virtual device that leverages the two-server setting. The virtual device splits the user's private key over both servers, and uses password-based authentication for its retrieval. Overall, the goal of the protocol is to ensure confidentiality of the uploaded medical records as long as at most one server is corrupt. In this work, we analyze the security of Doctolib's distributed encryption protocol. First, we define a set of formal security models for such password-based distributed envelope encryption, that capture the optimal security properties under different corruption settings. We then analyze the protocol - abstracted from the available information - in our model, and show that it does not achieve the desired security guarantees. We finally propose a simple modification that strengthens the original protocol through the use of a distributed oblivious pseudorandom function that provably achieves all our security properties.

Asymmetric Password-Authenticated Key Exchange (aPAKE) enables secure key establishment between a client and a server using a pre-shared password, while providing security against offline attacks. However, aPAKE does not guarantee any precomputation resistance, and considers passwords to become immediately available upon server compromise. A recent work by Dayanikli and Lehmann (EuroS&P'24) observed that many existing aPAKE protocols provide stronger precomputation attack resistance than what is guaranteed through the aPAKE model: they often rely on salted password hashes, where a unique salt makes precomputation attacks more difficult. While these salts are sent in clear to the client during authentication, and thus trivial to obtain for an attacker, this makes a difference in multi-user settings with millions of user accounts per server. In order to run bulk precomputation attacks on all users' passwords, the attacker needs to start an authentication session on behalf of every user to obtain their salts. However, this protection is still limited as salts are static, and the attacker can gradually extract all salt values for precomputation attacks. In this work, we build upon the observation that many aPAKE protocols include salts for their password protection, and propose a new aPAKE variant that makes such bulk precomputation attacks practically infeasible. We propose updatable aPAKE which employs updatable salts. In updatable aPAKE, the salt is implicitly refreshed with each successful user authentication, forcing an attacker to rebuild their precomputation table after every honest user's login -- offering a level of precomputation resistance similar to that of strong aPAKE protocols. We formalize the security of updatable aPAKE in the Universal Composability framework and show how OKAPE-HMQV, the currently most efficient aPAKE protocol, can be lifted to the updatable aPAKE setting in a provably secure way. The core idea is that this salt update can be integrated through relying on the password-based server-side authentication, that is already guaranteed through aPAKE. We also observe that OKAPE-HMQV is very similar to SRP-6a, the currently most widely deployed aPAKE protocol, and explain how the same idea can be used to upgrade this legacy protocol to achieve strong bulk precomputation attack resistance with minimal overhead.

Transformer-based models like BERT and GPT have achieved state-of-the-art performance across a wide range of AI tasks but raise serious privacy concerns when deployed as cloud inference services. To address this, secure multi-party computation (MPC) is commonly employed, encrypting both user inputs and model parameters to enable inference without revealing any private information. However, existing MPC-based secure transformer inference protocols are predominantly designed under the semi-honest security model. Extending these protocols to support malicious security remains a significant challenge, primarily due to the substantial overhead introduced by securely evaluating complex non-linear functions required for adversarial resilience. We introduce Mosformer, the first maliciously secure three-party (3PC) inference framework that efficiently supports large transformers such as BERT and GPT. We first design constant-round comparison and lookup table protocols with malicious security, leveraging verifiable distributed point functions (VDPFs). Building on these, we develop a suite of 3PC protocols for efficient and secure evaluation of complex non-linear functions in transformers. Together with optimized modulus conversion, our approach substantially reduces the overhead of secure transformer inference while preserving model accuracy. Experimental results on the vanilla transformer block show that Mosformer achieves up to a $5.3\times$ speedup and a $4.3\times$ reduction in communication over prior maliciously secure protocols. Despite offering stronger security guarantees, Mosformer achieves comparable or even superior online performance to state-of-the-art semi-honest 2PC and 3PC frameworks, including BOLT (Oakland 2024), BumbleBee (NDSS 2025), SHAFT (NDSS 2025), and Ditto (ICML 2024), on full-scale models such as BERT and GPT-2.

At EUROCRYPT2012, Banerjee, Peikert, and Rosen introduced Ring Learning With Rounding (RLWR) problem and constructed lattice-based pseudorandom functions for the first time. Subsequently, Banerjee, Brenner, Leurent, Peikert, and Rosen named this family of lattice-based pseudorandom functions as SPRING, reanalyzed the security, and gave two practical instances. Building upon the SPRING family, Bouillaguet, Delaplace, Fouque, and Kirchner further extended it to a pseudorandom number generator called SPRING-RS. It is quite fast but still has a certain gap compared with the classical pseudorandom number generator based on symmetric cryptography, and the key size is large. In this work, we present LEAP, a lattice-based pseudorandom number generation scheme characterized by high performance, adaptable parameter selection, and extensive support for parallel processing. Unlike the RLWR problem used in public key cryptography, LEAP treats the public parameter in the RLWR problem as the key as well. Hiding the public parameters leads to larger lattice dimensions and higher standard deviations of error in the concrete security analysis compared to RLWR under identical parameters. These adjustments imply enhanced security, allowing smaller parameters while maintaining the same security level, thereby improving performance. Additionally, we introduce a novel framework that reuses multiple parameters, significantly enhancing overall performance. To mitigate the issue of increased key size caused by treating the public parameter as the key, we design a pseudorandom number generator leveraging the small key size characteristic of a variant of the NTRU assumption, which provides the key required for the high-performance pseudorandom number generator. Compared with the SPRING-RS, the LEAP can reduce the key size by 1.71X while improving performance by 3.30X at the same security level. Under the AVX2 and AVX512 implementations, the performance reaches 1.61 Cycles/byte and 1.14 Cycles/byte, and the throughput reaches 16.12 Gbps and 22.60 Gbps, respectively.

Traditional Secure Multi-Party Computation (MPC) requires parties to stay online through the whole computation, which compromises scalability when dealing with large-scale and complex tasks. The notion of fluid MPC, introduced by Choudhuri et al. (Crypto 2021), aims to address this challenge by presenting a dynamic participation model where parties have the flexibility to join and leave as needed. The best-known honest-majority MPC protocol by Bienstock et al. (Crypto 2023) in the fluid setting achieves linear communication complexity, but still incurs a substantially higher communication overhead than MPC in the classical setting. In this paper, we present two concretely efficient fluid MPC protocols in the honest-majority setting. The first, Velora, is an unconditionally secure maximal-fluid MPC protocol, which achieves the lowest communication cost among maximally fluid MPC protocols by introducing a new approach of transferring the output sharings held by the current committee to the next committee. To eliminate the inherent overhead of Velora, we also propose a separation-generation approach for random double sharings and integrate it into the second protocol as Ion. As a trade-off, Ion relaxes the fluidity requirement to the submaximal fluidity, allowing an extra internal communication round for each committee. Both protocols Velora and Ion enable us to extend the ATLAS technique from the classical setting to the fluid setting for further lowering communication overhead. Compared to the best-known fluid MPC protocol, our protocols reduce the communication cost per multiplication gate by a factor of 5.4 ∼ 7.5× (resp., 20.7 ∼ 28×) for semi-honest security (resp., malicious security). Compared to the state-of-the-art ATLAS protocol by Goyal et al. (Crypto 2021) in the classical setting, our semi-honest protocols only introduce a 1 ∼ 1.5× larger communication overhead for securely computing multiplication gates.

In this paper, we specifically review Xu et al.’s quantum blind signature scheme for distributed e-voting systems, which primarily focuses on simulating real-life e-voting. The scheme aims to ensure voter anonymity in an e-voting system. However, we found that it not only suffers from identity impersonation attacks but also lacks the blindness property essential to a blind quantum signature. To address these shortcomings, we propose a new quantum blind signature scheme that leverages quantum mechanical properties and a one-way hash function. Considering that a voting scheme naturally involves an election committee member blindly signing a ballot embedded with the name of the selected candidate, we use our quantum blind signature as the foundation to design a quantum voting system. This system effectively prevents the repudiation and counterfeiting issues present in Xu et al.’s scheme. Additionally, we provide relevant security analyses to support our theoretical framework. The results demonstrate that our scheme outperforms existing literature not only in terms of e-voting security properties—such as undeniability, anonymity, and untraceability—but also in conceptual simplicity and computational efficiency.

Quantum security most commonly encompasses only offline passive quantum attacks, where a quantum computer is used by an adversary to solve some computationally hard problem, e.g. factoring or discrete logarithm. However, we are witnessing major efforts for the development and deployment of quantum communication networks, and in this environment, cryptographic protocols may also be implemented in quantum devices. In this new setting, a wider range of online active attacks may become possible, for example against targets that may, either deliberately or inadvertently, run a cryptographic scheme in superposition. In this work, we demonstrate that authentication protocols whose security is based on the difficulty of learning linear functions subject to errors may be vulnerable to attacks where adversaries can make queries in superposition — that is, under the so-called “Q2” adversarial model. We do so by describing superposition attacks against a family of symmetric-key authentication protocols based on the LPN problem, a post-quantum cryptography assumption. Our attacks against the HB+ and HB# protocols, both of which have classical proofs of security against active attacks, are based on the Bernstein-Vazirani algorithm, and can efficiently recover the secret key. Despite being conceptually simple, we suggest that our attack techniques might be extended and adapted to also allow for superposition attacks against some modern lattice-based identification and post-quantum signature schemes.

The problem of finding a minimal circuit to implement a given function is one of the oldest in electronics. It is known to be NP-hard. Still, many tools exist to find sub-optimal circuits to implement a function. In electronics, such tools are known as synthesisers. However, these synthesisers aim to implement very large functions (a whole electronic chip). In cryptography, the focus is on small functions, hence the necessity for new dedicated tools for small functions. Several tools exist to implement small functions. They differ by their algorithmic approach (some are based on Depth-First-Search as introduced by Ullrich in 2011, some are based on SAT-solvers like the tool desgined by Stoffelen in 2016, some non-generic tools use subfield decomposition) and by their optimisation criteria (some optimise for circuit size, others for circuit depth, and some for side-channel-protected implementations). However, these tools are limited to functions operating on less than 5 bits, sometimes 6 bits for quadratic functions, or to very simple functions. The limitation lies in a high computing time. We propose a new tool to implement quadratic functions up to 9 bits within AND-depth 1, minimising the number of AND gates. This tool is more time-efficient than previous ones, allowing to explore larger implementations than others on 6 bits or less and allows to reach larger sizes, up to 9 bits.

Achieving (at least) a worst-case correctness error is essential for an underlying public-key encryption (PKE) scheme to which the Fujisaki-Okamoto (FO) transformation is applied. There are three average-case to worst-case (ACWC) transformations—denoted as $\mathsf{ACWC}_{0}$, $\mathsf{ACWC}_{1}$ (PKC 2023), and $\mathsf{ACWC}_{2}$ (TIFS 2023)-which generically convert a PKE scheme with an average-case correctness error into one with a worst-case correctness error. However, in these ACWC transformations the $\gamma$-spreadness, a critical factor in determining explicit rejection ($\mathsf{FO}^{\perp}$) or implicit rejection ($\mathsf{FO}^{\not\perp}$), has not been established with rigorous proofs. Existing analyses of $\gamma$-spreadness lack rigorous proofs, include analytical flaws, or fail to achieve the tightest possible bounds. In this work, we reprove the $\gamma$-spreadness of ACWC-transformed PKE schemes by leveraging two key facts: the random oracle is chosen at random and the encoding mechanism used in the ACWC framework is message-hiding. Our new proofs are applied to the previous NTRU-based PKE schemes, called $\mathsf{NTRU}\mbox{-}\mathsf{C}$, $\mathsf{NTRU}\mbox{-}\mathsf{B}$, and $\mathsf{NTRU+}$, giving the corrected $\gamma$-spreadness for those PKE schemes with concrete parameters.

Hashing to elliptic curve groups is a fundamental operation used in many cryptographic applications, including multiset hashing and BLS signatures. With the recent rise of zero-knowledge applications, they are increasingly used in constraint programming settings. For example, multiset hashing enables memory consistency checks in zkVMs, while BLS signatures are used in proof of stake protocols. In such cases, it becomes critical for hash-to-elliptic-curve-group constructions to be constraint-friendly such that one can efficiently generate succinct proofs of correctness. However, existing constructions rely on cryptographic hash functions that are expensive to represent in arithmetic constraint systems, resulting in high proving costs. We propose a constraint-efficient alternative: a map-to-elliptic-curve-group relation that bypasses the need for cryptographic hash functions and can serve as a drop-in replacement for hash-to-curve constructions in practical settings, including the aforementioned applications. Our relation naturally supports non-deterministic map-to-curve choices making them more efficient in constraint programming frameworks and enabling efficient integration into zero-knowledge proofs. We formally analyze the security of our approach in the elliptic curve generic group model (EC-GGM). Our implementation in Noir/Barretenberg demonstrates the efficiency of our construction in constraint programming: it achieves over $23\times$ fewer constraints than the best hash-to-elliptic-curve-group alternatives, and, enables $50$-$100\times$ faster proving times at scale.

Multiple authentication solutions are widely deployed, such as OTP/TOTP/HOTP codes, hardware tokens, PINs, or biometrics. However, in practice, one sometimes needs to authenticate not only the user but also their location. The current state-of-the-art secure localisation schemes are either unreliable or insecure, or require additional hardware to reliably prove the user's location. This paper proposes CARPOOL, a novel, secure, and reliable approach to affirm the location of the user by solely relying on location-bounded interactions with commercial off-the-shelf devices. Our solution does not require any additional hardware, leverages devices already present in a given environment, and can be integrated effortlessly with existing security components, such as identity and access control systems. To demonstrate the feasibility of our work and to show that it can be deployed in a realistic closed environment setting, we implemented a proof of concept realisation of CARPOOL on an Android phone and multiple Raspberry Pi boards and integrated CARPOOL with Amazon Web Services (AWS) Cognito.

We give a public key encryption scheme that is provably secure against poly-size adversaries, assuming $n^{\log^\alpha n}$ hardness of the standard planted clique conjecture, for any $\alpha \in (0,1)$, and a relatively mild hardness conjecture about noisy $k\mbox{-}\mathsf{LIN}$ over expanders that is not known to imply public-key encryption on its own. Both of our conjectures correspond to natural average-case variants of NP-complete problems and have been studied for multiple decades, with unconditional lower bounds supporting them in a variety of restricted models of computation. Our encryption scheme answers an open question in a seminal work by Applebaum, Barak, and Wigderson [STOC'10].

SNARKs enable compact proofs that an NP statement is true and that the prover knows a valid witness. They have become a key building block in modern smart contract applications, including rollups and privacy-focused cryptocurrencies. In the widely used Groth16 framework, however, long statements incur high costs. A common workaround is to pass the statement’s hash to the SNARK and move the statement into the witness. The smart contract then hashes the statement first, and the circuit that is proven additionally checks consistency of the hash and the statement. Unfortunately, virtually any hash function is expensive to call either in a smart contract (in terms of gas) or in the proven circuit (in terms of prover time). We demonstrate a novel solution to this dilemma, which we call hybrid compression. Our method allows us to use two different hash functions—one optimized for the proof circuit, and another optimized for on-chain verification—thereby combining the efficiency advantages of both. We define a clean and simple security property of the two hash functions to which our security reduces in the standard model, namely, joint UHF hardness. We then show the plausibility of this assumption in the random oracle model. Our benchmarks show that it achieves near-optimal performance in both gas usage and prover time. As an example, compressing an 8 KB statement with our approach results in a 10-second prover time and a smart contract spending 270K gas, whereas the existing approaches either need a much longer proof generation (290 seconds for SHA-256 hashing) or a much more expensive contract (5M gas for Poseidon hashing). Along the way, we develop a two-party protocol of independent interest in communication complexity: an efficient deterministic method for checking input equality when the two parties do not share the same hash function.

The threshold secret sharing scheme enables a dealer to distribute the share to every participant such that the secret is correctly recovered from a certain amount of shares. The traditional $(k, n)$ threshold secret sharing scheme requires that the number of participants $n$ is known in advance. In contrast, the evolving secret sharing scheme allows that $n$ can be uncertain and even ever-growing. In this paper, we consider the evolving secret sharing scenario. Based on the prefix codes, we propose a brand-new construction of evolving $k$-threshold secret sharing scheme for an $\ell$-bit secret over a polynomial ring, with correctness and perfect security. The proposed scheme is the first evolving $k$-threshold secret sharing scheme by generalizing Shamir's scheme onto a polynomial ring. Besides, the proposed scheme also establishes the connection between prefix codes and the evolving schemes for $k\geq2$. The analysis shows that the size of the $t$-th share is $(k-1)(\ell_t-1)+\ell$ bits, where $\ell_t$ denotes the length of a binary prefix code of encoding integer $t$. In particular, when $\delta$ code is chosen as the prefix code, the share size is $(k-1)\lfloor\lg t\rfloor+2(k-1)\lfloor\lg ({\lfloor\lg t\rfloor+1}) \rfloor+\ell$, which improves the prior best result $(k-1)\lg t+6k^4\ell\lg{\lg t}\cdot\lg{\lg {\lg t}}+ 7k^4\ell\lg k$, where $\lg$ denotes the binary logarithm. Specifically, when $k=2$, the proposal also provides a unified mathematical decryption for prior evolving $2$-threshold secret sharing schemes and also achieves the minimal share size for a single-bit secret, which is the same as the best-known scheme.

Motivated by LowMC cryptanalysis challenge, research in recent years focuses more on attacking LowMC in \PICNIC application setting, \ie an attacker can see only a single plaintext/ciphertext pair. It can be noted that in the security proof of \PICNIC, LowMC is required to be secure under two plaintexts, it is thus meaningful to investigate the security of LowMC in this direction. Pioneered by Liu, Isobe and Meier at Crypto 2021, they combined algebraic techniques with difference enumeration attack, which could attack all three 4-round LowMC instances adopting full S-Box layers in \PICNIC with only two chosen plaintexts. However, the research on cryptanalysis of LowMC using two plaintext/ciphertext pairs is yet far from complete. Previous works using a single known plaintext are better than those with two plaintexts in terms of attack complexity or attacked rounds when considering a comparable success probability. In this paper, to address such counter-intuitive gaps between existing attacks on LowMC with full S-box layers using a single and two plaintext/ciphertext pairs, we first develop an algebraic key-derived attack framework, where an algebraic property of the key-derived difference is utilized to build an equation system with lower algebraic degree. This directly contributes to less cost for solving equation system and naturally works under known-plaintext setting, which can be further enhanced with chosen-plaintext attack setting. We then present an improved difference enumeration attack framework. Instead of enumerating all possible differences in the second round, variables for part of S-boxes in the second and third rounds are introduced to derive cubic equations, which will lead to fewer variables for the last round. Finally, applying our new attack frameworks to LowMC, we propose \text{8-round} attacks on LowMC for the very first time, which remain under known-plaintext setting. Moreover, we give the first attacks on three LowMC instances, \ie 129-bit block size of 6 rounds and 129-/192-bit block size of 7 rounds, which cannot be obtained using previous attacking methods. Also, previous attacks on LowMC from 4 to 7 rounds could be improved for almost all three LowMC instances in this paper. All these results, we believe, could be a positive answer that given one more pair, more information indeed can be gained to improve attacks on LowMC when compared to those using only a single plaintext. As well as our newly proposed algebraic key-derived attack framework, we hope that, could provide more insights into the cryptanalysis of LowMC with low allowable data complexity.

We consider the question of whether worst-case hardness of the time-bounded Kolmogorov complexity problem, $\KpolyA$---that is, determining whether a string is time-bounded Kolmogorov random ($K^t$-random) or not---suffices to imply the existence of one-way functions (OWF). Roughly speaking, our main result shows that under a natural strengthening of standard-type derandomization assumptions, worst-case hardness of the \emph{boundary} version of this classic problem characterizes OWFs. In more detail, let $\bKtA$ denote the problem of, given an instance $x$, deciding whether (a) $K^{t_2}(x)\geq n-1$, or (b) $K^{t_1}(x) < n-1$ \emph{but} $K^{t_2}> n - \log n$; that is, deciding whether $x$ is $K^t$-random, or just ``near" $K^t$-random. We say that $\bKpolyA \notin \ioBPP$ if $\bKpolyA \notin \ioBPP$ for all polynomials $t_1,t_2$. We show that under a natural strengthening of standard derandomization assumptions (namely, there exists a constant $\varepsilon > 0$ such that $\E \not\subseteq {\sf ioNTIME}[2^{kn}] \slash 2^{\varepsilon n}$ for every $k \in \N$), OWF exist iff $\bKpolyA \notin \ioBPP$. Along the way, we also demonstrate that if we consider the probabilistic version of Kolmogorov complexity (referred to as $pK^t$) instead, then the characterization holds unconditionally. We finally observe that for most standard optimization problems, hardness ``along boundary" is equivalent to ``plain" worst-case hardness, indicating that assuming hardness along the boundary may be WLOG.

Plaintext-checking (PC) oracle attacks are among the most prominent types of attacks against NIST's recently standardized ML-KEM. Previous works have drastically reduced the number of queries needed to recover the secret key. Although this number is now close to the information-theoretic bound, current attacks have not yet been adapted to settings with increased noise and highly imperfect oracles. In attacks targeting real-world protected implementations, noisy leakage may lead to oracles that only provide a small advantage over guessing. This work shows how to efficiently exploit imperfect oracles arising from highly noisy side channels. We present several soft-analytic techniques that enable highly noise-tolerant parallel PC-oracle attacks. These techniques allow for successful attacks in relatively few traces from information that gives just a slight advantage over guessing. Additionally, we extend the generic framework for side-channel information from Eurocrypt 2025 and thereby relate our techniques to previous work. We then discuss several oracle instantiations that are based on the noisy Hamming weight model. These oracles rely on widely accepted assumptions, are easy to simulate, and allow for fair comparisons between different attacks. Furthermore, they allow countermeasures to be taken into account, and we evaluate the impact of masking. Our evaluations in these and previous models show that PC-oracle attacks are noise-tolerant on an entirely different scale compared to previous work. These improvements are of an algorithmic nature and orthogonal to the fact that the Fujisaki-Okamoto transform in ML-KEM offers a large attack surface. Finally, we discuss the implications of our findings for protected ML-KEM implementations.

We prove that $4r + 4$ rounds of an AES variant with independent and uniform random round keys are $\varepsilon$-close to pairwise independent with $\varepsilon = 2^{14}\, 2^{-40r}$. This result follows from a near-optimal bound for a two-norm version of pairwise independence for the Shark construction, depending on the third singular value of the difference-distribution table of the S-boxes. Our analysis combines insights from cryptanalysis — in particular, truncated differentials — and linear algebra over the reals.

Symmetric cryptography is confronting threats posed by quantum computing, including Grover's search algorithm and Simon's algorithm. In the fault-tolerant quantum computation, the limited qubit count, connectivity constraints, and error rates of quantum hardware impose stringent requirements on the implementation of cryptographic quantum circuits. Constructing low-resource quantum circuit models forms the foundation for evaluating algorithmic resistance to quantum threats. At CRYPTO 2019, Jaques et al. justified the adoption of depth-times-width cost (DW-cost) as a metric for quantum circuits by incorporating advancements in quantum computation and error correction. In this work, we address the fundamental limitations in in-place implementations of AES quantum circuits by proposing a set of in-place synthesis methods centered on DW-cost optimization. First, we prove that within the composite field arithmetic framework, intermediate circuit states can be utilized to uncompute S-box input states, and introduce a novel design pathway and circuit structure for in-place S-box quantum circuits. Second, we establish the necessary conditions for maximizing parallelization of Toffoli gates under minimal-width constraints in binary field multiplication. Through co-design and optimization of multiple nonlinear components, we construct a compact in-place S-box with a DW-cost of merely 276. Finally, building on this, we achieve quantum circuit implementations for AES-128, AES-192, and AES-256 via co-optimization of key expansion and round functions, reducing their DW-cost values to 65,280, 87,552, and 112,896 respectively. These results indicate a reduction of at least 46%, 45%, and 45% compared to existing state-of-the-art solutions. This study establishes new technical benchmarks for low-resource fault-tolerant implementations of symmetric cryptography in the post-quantum era. (This is a revised version containing Clifford+T resource estimates for both AES-128 Grover oracle and encryption oracle. Key revisions are highlighted in red.)

The efficiency of circuit implementations for cryptographic algorithms is crucial for their practical deployment. The implementation cost of the linear layer can be evaluated by the number of XOR operations, typically measured in generalized XOR (g-\xor) and serial XOR (s-XOR). Finding the minimal sequence of g-XOR operations constitutes the Shortest Linear Program (SLP) problem. Existing approaches generally address this problem through a two-stage framework: generating an initial sequence followed by local optimization, both stages essentially solving the SLP problem. The Boyar-Peralta (BP) algorithm serves as a foundational heuristic for addressing the SLP problem and has been extensively adopted in subsequent research; however, its computational inefficiency presents a significant limitation for practical applications, especially in large-scale problems. This paper proposes a novel implementation framework for the BP algorithm based on linear combinations, significantly enhancing its computational efficiency. We further introduce a new strategy for selecting subsequences during local optimization, replacing the random selection strategy employed in previous works. By analyzing the structural properties of the Advanced Encryption Standard (AES) linear layer matrix and applying our proposed methods, we achieve the first implementation requiring only 89 g-XOR operations, improving upon the previous best result of 91 g-XOR operations reported in prior literature.

We show the key ideas of the above-referenced work for lattice Gaussian sampling are not new; the same ideas have been proposed by Ling et al. in 2014.

A homomorphic secret sharing (HSS) scheme allows a client to delegate a computation to a group of untrusted servers while achieving input privacy as long as at least one server is honest. In recent years, many HSS schemes have been constructed that have, in turn, found numerous applications to cryptography. Prior work on HSS focuses on the setting where the servers are semi-honest. In this work we study HSS in the setting of malicious evaluators. We propose the notion of HSS with verifiable evaluation (ve-HSS) that guarantees correctness of output even when all the servers are corrupted. ve-HSS retains all the attractive features of HSS and adds the new feature of succinct public verification of output. We present black-box constructions of ve-HSS by devising generic transformations for semi-honest HSS schemes (with negligible error). This provides a new non-interactive method for verifiable and private outsourcing of computation.

FALCON is a NIST-selected post-quantum digital signature scheme whose performance bottleneck lies in the SamplerZ subroutine for discrete Gaussian sampling. We present a throughput-optimized, custom hardware implementation of SamplerZ that introduces several architectural and algorithmic innovations to significantly accelerate signature generation. Our design incorporates a datapath-aware floating-point arithmetic pipeline that strategically balances latency and resource utilization. Our novel algorithmic innovations include an Estrin's Scheme-based polynomial evaluator and a constant-latency BerExp routine using floating-point exponentiation IP to eliminate fixed-point decomposition critical paths. Additionally, we optimize rejection handling through parallel sampling loops and propose a speed-optimized flooring circuit. These advancements lower the sampling time by 55%-81% and overall FALCON signature generation time by 36%-53% compared to the state-of-the-art FPGA implementation. In a landmark result, our work is the first to demonstrate a Xilinx FPGA SamplerZ design that outperforms state-of-the-art software (by 15%) and ASIC (by 16%) designs, advancing the practical deployment of post-quantum signatures on reconfigurable hardware.

Rekeying is an effective technique for protecting symmetric ciphers against side-channel and key-search attacks. Since its introduction, numerous rekeying schemes have been developed. We introduce Post-Quantum Stateless Auditable Rekeying (PQ-STAR), a novel post-quantum secure stateless rekeying scheme with audit support. PQ-STAR is presented in three variants of increasing security guarantees: (i) Plain PQ-STAR lets an authorized auditor decrypt and verify selected ciphertexts; (ii) Commitment-based PQ-STAR with the additional binding guarantee from the commitments, preventing a malicious sender from potentially claiming a random or wrong session key. (iii) Zero-knowledge PQ-STAR equips each session key with a signature-based zero-knowledge proof (ZKP), which proves that the session key was derived honestly, without ever revealing the secret preimage. We formally prove that all variants achieve key-uniqueness, index-hiding, and forward-secrecy, even if a probabilistic polynomial-time (PPT) adversary arbitrarily learns many past session keys. PQ-STAR provides a formally verified, stateless, and audit-capable rekeying primitive that can be seamlessly integrated as a post-quantum upgrade for existing symmetric-key infrastructures.

Asynchronous byzantine agreement extension studies the message complexity of $L$-bit multivalued asynchronous byzantine agreement given access to a binary asynchronous Byzantine agreement protocol. We prove that asynchronous byzantine agreement extension can be solved with perfect security and optimal resilience in $O(nL+n^2 \log n)$ total communication (in bits) in addition to a single call to a binary asynchronous Byzantine agreement protocol. For $L = O(n \log n)$, this gives an asymptotically optimal protocol, resolving a question that remained open for nearly two decades. List decoding is a fundamental concept in theoretical computer science and cryptography, enabling error correction beyond the unique decoding radius and playing a critical role in constructing robust codes, hardness amplification, and secure cryptographic protocols. A key novelty of our perfectly secure and optimally resilient asynchronous byzantine agreement extension protocol is that it uses list decoding - making a striking new connection between list decoding and asynchronous Byzantine agreement.

SCALES (Small Clients And Larger Ephemeral Servers) (Acharya et al., TCC 2022, CRYPTO 2024) is a recently proposed model for MPC with several attractive features, including resilience to adaptive corruption. Known SCALES constructions, while offering reasonable asymptotics for large-scale MPC, incur high concrete costs both in computation and communication. As our primary contribution, we dramatically improve both asymptotic and concrete costs of SCALES for permutation branching programs (PBP), a well-motivated practical model of computation. We achieve linear cost in program length, input size, and the security parameter. Our instantiations of the building blocks may be of independent interest. Further, we present generic transformations to extend any semi-honestly secure SCALES protocol to achieve (1) guaranteed output delivery in the presence of mixed adversaries (that corrupt servers maliciously and clients semi-honestly) in the all-but-one corruption setting; and (2) protocols for computing general functionalities where each server's computation scales sub-linearly in the function~size.

Construction of efficient and provably-secure (T)PRPs and (fixed/variable input-length) PRFs has been one of the central open problem in modern symmetric-key cryptography. Many Feistel-based constructions has been proposed and analysed to solve this problem. Inspired by some recent works, in this paper, we revisit the problem of constructing provably secure Feistel constructions using permutations as the round functions. More specifically, following the idea of Naor and Reingold, we try to reduce the number of inner permutations used by replacing them with cheap hash functions, without sacrificing optimal security. We affirmatively show that with the use of a suitable hash function along with a four-round Feistel construction, which uses only three independent permutations, one can achieve optimally secure (T)PRPs and PRFs.

Bitcoin is a decentralized, permissionless network for digital payments. Bitcoin also supports a limited set of smart contracts, which restrict how bitcoin can be spent, through bitcoin script. In order to support more expressive scripting functionality, Robin Linus introduced the BitVM family of protocols. These implement a weaker form of ``optimistic" smart contracts, and for the first time allowed bitcoin to verify arbitrary computation. BitVM allows a challenger to publish a ``fraud proof" that the computation was carried out incorrectly which can be verified on chain, even when the entire computation cannot. Jermey Rubin introduced an alternative optimistic smart contract protocol called Delbrag. This protocol uses Garbled Circuits (GC) to replace the BitVM fraud proof with by simply revealing a secret. He also introduced the Grug technique for malicious security. We introduce a new formalization of GC based optimistic techniques called Garbled Locks or Glocks. Much like Delbrag, we use the GC to leak a secret and produce a signature as a fraud proof. We further propose the first concretely practical construction that does not require Grug. Like BitVM2 and Delbrag, Glock25 reduces verification of arbitrary bounded computation to verification of a SNARK. In Glock25, we use a designated verifier version of a modified of the SNARK Pari with smaller proof size. We make Glock25 maliciously secure using a combination of Cut-and-Choose, Verifiable Secret Sharing (VSS), and Adaptor Signatures. These techniques reduce the communication, computational, and on-chain complexity of the protocol compared to other approaches to construct a Glock, e.g. based on Groth16.

Payment channel networks (PCNs) are a promising technology that alleviates blockchain scalability by shifting the transaction load from the blockchain to the PCN. Nevertheless, the network topology has to be carefully designed to maximise the transaction throughput in PCNs. Additionally, users in PCNs also have to make optimal decisions on which transactions to forward and which to reject to prolong the lifetime of their channels. In this work, we consider an input sequence of transactions over $p$ parties. Each transaction consists of a transaction size, source, and target, and can be either accepted or rejected (entailing a cost). The goal is to design a PCN topology among the $p$ cooperating parties, along with the channel capacities, and then output a decision for each transaction in the sequence to minimise the cost of creating and augmenting channels, as well as the cost of rejecting transactions. Our main contribution is an $\mathcal{O}(p)$ approximation algorithm for the problem with $p$ parties. We further show that with some assumptions on the distribution of transactions, we can reduce the approximation ratio to $\mathcal{O}(\sqrt{p})$. We complement our theoretical analysis with an empirical study of our assumptions and approach in the context of the Lightning Network.

Conventional Byzantine fault-tolerant protocols focus on the workflow within a group of nodes. In recent years, many applications of consensus involve communication across groups. Examples include communication between infrastructures running replicated state machine, sharding-based protocols, and cross-chain bridges. Unfortunately, little efforts have been made to model the properties for communication across groups. In this work, we propose a new primitive called cross-consensus reliable broadcast (XRBC). The XRBC primitive models the security properties of communication between two groups, where at least one group executes a consensus protocol. We provide three constructions of XRBC under different assumptions and present three different applications for our XRBC protocols: a cross-shard coordination protocol via a case study of Reticulum (NDSS 2024), a protocol for cross-shard transactions via a case study of Chainspace (NDSS 2018), and a solution for cross-chain bridge. Our evaluation results show that our protocols are highly efficient and benefit different applications. For example, in our case study on Reticulum, our approach achieves 61.16% lower latency than the vanilla approach.

We discuss how Fully Homomorphic Encryption (FHE), and in particular the TFHE scheme, can be used to define an e-voting scheme for the Alternative Vote (AV) election system. This system has a more complex tallying phase than traditional First-Past-The-Post (FPTP) election variants. Previous work on e-voting schemes that used homomorphic encryption has focused on FPTP systems only, and utilized mainly linearly homomorphic encryption. We show, by using FHE, that more complex electoral systems such as AV can also be supported by homomorphic encryption. We show security of our protocol by considering it as a simple MPC functionality, and we also show practicality by presenting some experimental runtimes using the tfhe-rs library.

A Symmetric Key Encryption scheme using Camera Zooming is pre- sented using a familiar Paper-pencil cipher. The Camera can have a mag- nification/scaling up to some integer. The encrypter and decrypter are two hardware systems that are assumed to have the capability to zoom a given image with text from the resolution of a single character to a page by applying an appropriate scaling factor and an appropriate polynomial time zoom algorithm. Using the symmetric key, the Camera or a zooming algorithm implementation repeatedly zooms on different boxes in an im- age filled with cipher text and spurious redundant non-correlated pseudo- random data. Then, it decrypts the cipher using the Merkle-Hellman Knapsack Cryptosystem (MHKC) trapdoor algorithm or variants for ef- ficient encryption/decryption. As shown, the MHKC algorithm’s crypt- analysis vulnerability using Lattice-based LLL and other density attacks would not affect this scheme—as long as the key is private.

Kleptography was first proposed by Adam Young and Moti Yung in 1996, while algorithm substitution attack was introduced by Mi- hir Bellare et al. as a variation of kleptography in 2014 after the Dual EC incident with the confidential documents revelation by Edward Snowden. These two paradigms share a common goal: to enable attackers to embed covert capabilities into cryptographic implementations while maintaining the appearance of normal functionality. The goal of this paper is to con- solidate existing research on kleptographic attacks, integrate it into a uni- fied definition, and explore future directions for the research in this field. This paper begins by introducing and comparing the two major branches of kleptographic attacks: traditional kleptography and post-Snowden al- gorithm substitution attack, highlighting their theoretical distinctions, threat models, and historical development. Then, it analyzes the spe- cific goals that attackers aim to achieve through such subversions and propose a generalized definition of algorithm substitution attack that in- clude all the goals. The paper also presents practical examples framed within my definition and classify prior research works as either strong or weak attacks based on their structure and undetectability. Finally, it discusses the current landscape of research in kleptographic attacks, and then suggest future directions for the attack and defense perspectives.

Making 2-party computation scale up to big datasets is a long-cherished dream of our community. More than a decade ago, a line of work has implemented and optimized interactive RAM-model 2-party computation (2PC), achieving somewhat reasonable concrete performance on large datasets, but unfortunately suffering from $\widetilde{O}(T)$ roundtrips for a $T$-time computation. Garbled RAM promises to compress the number of roundtrips to $2$, and encouragingly, a line of recent work has designed concretely efficient Garbled RAM schemes whose asymptotic communication and computation costs almost match the best known interactive RAM-model 2PC, but still leaves $({\sf poly})\log\log$ gaps. We present ${\sf PicoGRAM}$, a practical garbled RAM (GRAM) scheme that not only asymptotically matches the prior best RAM-model 2PC, but also achieves an order of magnitude concrete improvement in online time relative to interactive RAM-model 2PC, on a dataset of size $8$GB. Moreover, our work also gives the first Garbled RAM whose total cost (including bandwidth and computation) achieves an optimal dependency on the database size (up to an arbitrarily small super-constant factor). Our work shows that for high-value real-life applications such as Signal, blockchains, and Meta that require oblivious accesses to large datasets, Garbled RAM is a promising direction towards eventually removing the trusted hardware assumption that exist in production implementations today. Our open source code is available at https://github.com/picogramimpl/picogram.

Threshold Schnorr signatures enable $t$-out-of-$n$ parties to collaboratively produce signatures that are indistinguishable from standard Schnorr signatures, ensuring compatibility with existing verification systems. While static-secure constructions are well understood and achieve optimal round complexity, obtaining full adaptive security - withstanding up to $t-1$ dynamic corruptions under standard assumptions has proven elusive: Recent impossibility results (CRYPTO’25) either rule out known proof techniques for widely deployed schemes or require speculative assumptions and idealized models, while positive examples achieving full adaptivity from falsifiable assumptions incur higher round complexity (EUROCRYPT’25, CRYPTO’25). We overcome these barriers with the first round-optimal threshold Schnorr signature scheme that, under a slightly relaxed security model, achieves full adaptive security from DDH in the random oracle model. Our model is relaxed in the sense that the adversary may adaptively corrupt parties at any time, but each signer must refresh part of their public key after a fixed number of signing queries. These updates are executed via lightweight, succinct, stateless tokens, preserving the aggregated signature format. Our construction is enabled by a new proof technique, equivocal deterministic nonce derivation, which may be of independent interest.

Threshold decryption schemes allow a group of decryptors, each holding a private key share, to jointly decrypt ciphertexts. Over the years, numerous threshold decryption schemes have been proposed for applications such as secure data storage, internet auctions, and voting, and recently as a tool to protect against miner-extractable value attacks in blockchain. Despite the importance and popularity of threshold decryption, many natural and practical threshold decryption schemes have only been proven secure against static adversaries. In this paper, we present two threshold decryption schemes that withstand malicious adaptive corruption. Our first scheme is based on the standard ElGamal encryption scheme and is secure against chosen plaintext attack~(CPA). Our second scheme, based on the chosen ciphertext attack~(CCA) secure Shoup-Gennaro encryption scheme, is also CCA secure. Both of our schemes have non-interactive decryption protocols and comparable efficiency to their static secure counterparts. Building on the technique introduced by Das and Ren (CRYPTO 2024), our threshold ElGamal decryption scheme relies on the hardness of Decisional Diffie-Hellman and the random oracle model.

The Regular Syndrome Decoding (RSD) problem, introduced nearly two decades ago, is a regular version of the Syndrome Decoding (SD) problem, where the noise vector is divided into consecutive, equally sized blocks, each containing exactly one noisy coordinate. Recently, RSD has gained renewed attention for its applications in Pseudorandom Correlation Generator (PCG) and more. Very recently, several works presented the improved algebraic approach (AGB for short) and ISD approach (including regular-ISD and regular-RP) to utilize the regular structure of noise vectors and provide a more precise security evaluation for the RSD problem. In this paper, we refine the AGB algorithm from a one-round process to a two-round process, and refer to the new algebraic algorithm as AGB 2.0. For each round, we guess a few noise-free positions, followed by a tailored partial XL algorithm. This interleaving strategy increases the probability of success by reducing the number of guessing noise-free positions and effectively lowers the problem's dimension in each round. By fine-tuning position guesses in each round and optimizing the aggregate running time, our AGB 2.0 algorithm reduces the concrete security of the RSD problem by up to $6$ bits for the parameter sets used in prior works, compared to the best-known attack. In particular, for a specific parameter set in Wolverine, the RSD security is $7$ bits below the $128$-bit target. We analyze the asymptotic complexity of algebraic attacks on the RSD problem over a finite field $\mathbb{F}$ with the field size $|\mathbb{F}|>2$, when the noise rate $\rho$ and code rate $R$ satisfy $\rho + R < 1$. If $n \rho R^2 = O(1)$ where $n$ is the noise length, the RSD problem over $\mathbb{F}$ can be solved in polynomial time, but it does not hold for the SD problem. We show that the ISD and its variants, including regular-ISD and regular-RP, are asymptotically less efficient than AGB for solving RSD problems with $R = o(1/\log(n))$ and $|\mathbb{F}| > e^{n\rho R}$.

The industry is moving away from passwords for authentication and authorization, with hardware devices for storing long-term cryptographic keys emerging as the leading alternative. However, these devices often have limited displays and remain vulnerable to theft, malware, or tricking users into signing malicious payloads. Current systems provide little fallback security in such cases. Any solution must also meet strict requirements: compatibility with industry standards, scalability to handle high request volumes, and high availability. We present a novel design for authentication and authorization that meets these demands. Our approach virtualizes the authenticating/authorizing party via a two-party signing protocol with a helper entity, ensuring that keys remain secure even if a device is compromised and that every signed message conforms to a security policy. We formalize the required properties for such protocols and show how they are met by existing schemes (e.g., FROST for Schnorr, Boneh–Haitner–Lindell-Segev'25 for ECDSA). Motivated by the widespread use of ECDSA (FIDO2/Passkeys, blockchains), we introduce a new, optimized two-party ECDSA protocol that is significantly more efficient than prior work. At its core is a new variant of exponent-VRF, improving on earlier constructions and of independent interest. We validate our design with a proof-of-concept virtual authenticator for the FIDO2 Passkeys framework.

An Authenticated Key Encapsulation Mechanism (AKEM) combines public-key encryption and digital signatures to provide confidentiality and authenticity. AKEMs build the core of Hybrid Public Key Encryption (RFC 9180) and serve as a useful abstraction for messaging applications like the Messaging Layer Security (MLS) protocol (RFC 9420) and Signal's X3DH protocol. To date, most existing AKEM constructions either rely on classical (non post-quantum) assumptions or on unoptimized black-box approaches leading to suboptimal efficiency. In this work, we choose a different abstraction level to combine KEMs and identification schemes more efficiently by leveraging randomness reuse. We construct a generic scheme and identify the necessary security requirements on the underlying KEM and identification scheme when reusing parts of their randomness. This allows for a concrete instantiation from isogenies based on the POKÉ KEM (EUROCRYPT'25) and the SQIsignHD identification scheme (EUROCRYPT'24). To be used in our black-box construction, the identification scheme requires the more advanced security property of response non-malleability. Hence, we further show that a slight modification of SQIsignHD satisfies this notion, which might be of independent interest. Putting everything together, our final scheme yields the most compact AKEM from PQ assumptions with public keys of 366 bytes and ciphertexts of 216 bytes while fulfilling the strongest confidentiality and authenticity notions.

The sumcheck protocol is a fundamental building block in the design of probabilistic proof systems, and has become a key component of recent work on efficient succinct arguments. We study time-space tradeoffs for the prover of the sumcheck protocol in the streaming model, and provide upper and lower bounds that tightly characterize the efficiency achievable by the prover. $\bullet{}$ For sumcheck claims about a single multilinear polynomial we demonstrate an algorithm that runs in time $O(kN)$ and uses space $O(N^{1/k})$ for any $k \geq 1$. For non-adaptive provers (a class which contains all known sumcheck prover algorithms) we show that this tradeoff is optimal. $\bullet{}$ For sumcheck claims about products of multilinear polynomials, we describe a prover algorithm that runs in time $O(N(\log \log N + k))$ and uses space $O(N^{1/k})$ for any $k \geq 1$. We show that, conditioned on the hardness of a natural problem about multiplication of multilinear polynomials, any ``natural'' prover algorithm that uses space $O(N^{1/2 - \varepsilon})$ for some $\varepsilon > 0$ must run in time $\Omega(N(\log \log N + \log \varepsilon))$. We implement and evaluate the prover algorithm for products of multilinear polynomials. We show that our algorithm consumes up to $120\times$ less memory compare to the linear-time prover algorithm, while incurring a time overhead of less than $2\times$. The foregoing algorithms and lower bounds apply in the interactive proof model. We show that in the polynomial interactive oracle proof model one can in fact design a new protocol that achieves a better time-space tradeoff of $O(N^{1/k})$ space and $O(N(\log^* N + k))$ time for any $k \geq 1$.

The Module Learning With Errors (M-LWE) problem has become a fundamental hardness assumption for lattice-based cryptography. It offers an attractive trade-off between strong robustness guarantees, sometimes directly based on worst-case lattice problems, and efficiency of the subsequent cryptographic primitives. Different flavors of M-LWE have then been introduced towards improving performance. Such variants look at different secret-error distributions and might allow for additional hints on the secret-error vector. Existing hardness results however only cover restricted classes of said distributions, or are tailored to specific leakage models. This lack of generality hinders the design of efficient and versatile cryptographic schemes, as each new distribution or leakage model requires a separate and nontrivial hardness evaluation. In this work, we address this limitation by establishing the hardness of MLWE under general distributions. As a first step, we show that MLWE remains hard when the error vector follows an arbitrary bounded distribution with sufficient entropy, with some restriction on the number of samples. Building on this, we then reduce to the Hermite Normal Form (HNF) where the secret-error vector follows said arbitrary distribution. Overall, our result shows the actual shape of the distribution does not matter, as long as it keeps sufficient entropy. To demonstrate the versatility of our framework, we further analyze a range of leakage scenarios. By examining the residual entropy given the leakage, we show that our results of M-LWE with general distributions encompass various types of leakage. More precisely, we cover exact and approximate linear hints which are widely used in recent cryptographic designs, as well as quadratic, and even non-algebraic forms, some of which were not yet covered by any theoretical hardness guarantees. The generality of our results aims at facilitating future cryptographic designs and security analyses.

In this article, we introduce a new post-quantum cryptosystem, NTWR Prime, which is based on the NTRU Prime and Learning With Rounding (LWR) problems. This scheme is inspired by the NTWE construction proposed by Joel Gartner in 2023. Unlike NTWE, our algorithm employs an irreducible, non-cyclotomic polynomial whose Galois group is isomorphic to the symmetric group. Additionally, the LWR problem is used in place of the LWE problem, offering potential advantages for structural security due to its deterministic nature. We conduct a security analysis demonstrating that solving the NTWR Prime problem requires solving both the underlying NTRU Prime and LWR problems. Consequently, given the absence of definitive post-quantum security proofs for these problems, our construction offers redundancy, which may fulfill the requirements of applications with exceptionally high security standards. Importantly, we show that there exists a set of parameters satisfying the hardness assumptions for both contributing problems.

Fuzzy-labeled private set intersection (PSI) outputs the corresponding label if there is a ``fuzzy'' match between two items, for example, when the Hamming distance is low between the two items. Such protocols can be applied in privacy-preserving biometric authentication, proximity testing, and so on. The only fuzzy-labeled PSI protocol designed for practical purposes is by Uzun et al. (USENIX’21), which is based on homomorphic encryption. This design puts constraints on the item size, label size, and communication cost since it is difficult for homomorphic encryption to support large plaintext space and it is well-known that the ciphertext-expansion factor is large. Our construction begins with a new primitive which we call vector ring-oblivious linear evaluation (vector ring-OLE). This primitive does not rely on existing instantiations of ring-OLE over the quotient ring, but leverages the more efficient vector-OLE. It is ideal for building unbalanced threshold-labeled PSI and is also of independent interest. Our main contribution, fuzzy-labeled PSI, is bootstrapped from our threshold-labeled PSI protocol. Through a prototype implementation, we demonstrate our communication cost is up to $4.6\times$ better than the prior state-of-the-art with comparable end-to-end latency while supporting a significantly higher label size.

The $k$LIN problem concerns solving noisy systems of random sparse linear equations mod 2. It gives rise to natural candidate hard CSP distributions and is a cornerstone of local cryptography. Recently, it was used in advanced cryptographic constructions, under the name 'sparse LPN'. For constant sparsity $k$ and inverse polynomial noise rate, both search and decision versions of $k$LIN are statistically possible and conjectured to be computationally hard for $n\ll m\ll n^{k/2}$, where $m$ is the number of $k$-sparse linear equations, and $n$ is the number of variables. We show an algorithm that given access to a distinguisher for $(k-1)$LIN with $m$ samples, solves search $k$LIN with roughly $O(nm)$ samples. Previously, it was only known how to reduce from search $k$LIN with $O(m^3)$ samples, yielding meaningful guarantees for decision $k$LIN only when $m \ll n^{k/6}$. The reduction succeeds even if the distinguisher has sub-constant advantage at a small additive cost in sample complexity. Our technique applies with some restrictions to Goldreich's function and $k$LIN with random coefficients over other finite fields.

We present a real-world deployment of secure multiparty computation to predict political preference from private web browsing data. To estimate aggregate preferences for the 2024 U.S. presidential election candidates, we collect and analyze secret-shared data from nearly 8000 users from August 2024 through February 2025, with over 2000 daily active users sustained throughout the bulk of the survey. The use of MPC allows us to compute over sensitive web browsing data that users would otherwise be more hesitant to provide. We collect data us- ing a custom-built Chrome browser extension and perform our analysis using the CrypTen MPC library. To our knowledge, we provide the first implementation under MPC of a model for the learning from label pro- portions (LLP) problem in machine learning, which allows us to train on unlabeled web browsing data using publicly available polling and elec- tion results as the ground truth. The client code is open source, and the remaining code will be open source in the future.

In this paper, we present an optimized construction of the Homomorphic Polynomial Public Key (HPPK) cryptosystem, a novel framework designed to provide enhanced security and efficiency in the post-quantum era. Our work introduces a layered cryptographic design that combines modular arithmetic permutations with an innovative additive random masking technique. This approach effectively obscures the underlying factorizable structure of the public key, thereby mitigating vulnerabilities to known lattice reduction attacks and other algebraic cryptanalyses. The security of our scheme is formally grounded in the computational hardness of three new problems: the Hidden Modulus Product Problem (HMPP), the HPPK Key Recovery Problem (HKRP), and the HPPK Secret Recovery Problem (HSRP). We demonstrate through rigorous analysis that the optimal attacks on our scheme are computationally infeasible for appropriately chosen parameters. Furthermore, we show that HPPK achieves remarkably compact key, ciphertext, and signature sizes, offering a significant advantage over leading NIST post-quantum finalists such as Kyber, Dilithium, and Falcon, particularly in bandwidth-constrained environments. The HPPK cryptosystem offers a compelling and mathematically-grounded solution for next-generation cryptography, delivering both provable security and practical efficiency.

Most adaptively secure identity-based encryption (IBE) constructions from lattices in the standard model follow the framework proposed by Agrawal et al. (EUROCRYPT 2010). However, this framework has an inherent restriction: the modulus is quadratic in the trapdoor norm. This leads to an unnecessarily large modulus, reducing the efficiency of the IBE scheme. In this paper, we propose a novel framework for adaptively secure lattice-based IBE in the standard model, that removes this quadratic restriction of modulus while keeping the dimensions of the master public key, secret keys, and ciphertexts unchanged. More specifically, our key observation is that the original framework has a \textit{natural} cross-multiplication structure of trapdoor. Building on this observation, we design two novel algorithms with non-spherical Gaussian outputs that fully utilize this structure and thus remove the restriction. Furthermore, we apply our framework to various IBE schemes with different partitioning functions in both integer and ring settings, demonstrating its significant improvements and broad applicability. Besides, compared to a concurrent work by Ji et al. (PKC 2025), our framework is significantly simpler in design, and enjoys a smaller modulus, a more compact master public key and shorter ciphertexts.

If the system of an honest user is corrupted, all of its security may be lost: The system may perform computations using different inputs, report different outputs or perform a different computation altogether, including the leakage of secrets to an adversary. In this paper, we present an approach that complements arbitrary computations to protect against the consequences of malicious systems. Tothis end, we adapt a well-known technique traditionally used to increase fault tolerance, namely redundant executions on different machines that are combined by a majority vote on the results. However, using this conceptually very simple technique for general computations is surprisingly difficult due to non-determinism on the hardware and software level that may cause the executions to deviate. The CoRReCt approach, short for Compute, Record, Replay, Compare, considers two synchronized executions on different machines. Only if both executions lead to the same result, this result is returned. Our realization uses virtual machines (VMs): On one VM, the software is executed and non-deterministic events are recorded. On a second VM, the software is executed in lockstep and non-deterministic events are replayed. The outputs of both VMs, which are hosted on different machines, are compared by a dedicated trusted entity and only allowed if they match. The following security guarantees can be proven: – Integrity: If at most one host is corrupted, then the computation is performed using the correct inputs and returns either the correct result or no result at all. – Privacy: If timing side-channels are not considered and at most one host is corrupted, the additional leakage introduced by our approach can be bounded by $\log_2(n)$ bits, where n is the number of messages sent. If timing side-channels are considered and the recording system is honest, the same leakage bound can be obtained. As VMs can be run on completely different host platforms, e.g. Windows on Intel x86-64 or OpenBSD on ARM, the assumption of at least one system being honest is very plausible. To prove our security guarantees, we provide a proof within a formal model. To demonstrate the viability of our approach, we provide a ready-to-use implementation that allows the execution of arbitrary (networked) x86-64 Linux programs and discuss different real-world applications.

Constructing MPC with ephemeral committees has gained a lot of attention since the seminal works on Fluid MPC and YOSO MPC (CRYPTO'21). However, most protocols in this setting focus on the extreme case of ephemeral committees who can only act for one round (i.e., the maximally fluid case). The Layered MPC model (CRYPTO'23) recasts this notion as a protocol execution against an adaptive rushing adversary over a layered interaction graph, where each committee sits on a layer and can only communicate with the immediate next committee. Although protocols with abort allow for linear communication complexity (CRYPTO'23, CiC'24), Perfect Layered MPC with guaranteed output delivery (GOD) and its statistically secure counterpart (TCC'24) suffer from $O(n^9)$ and $O(\kappa n^{18})$ communication complexity for $n$ parties per committee, respectively. In this work, we investigate communication complexity improvements gained in a relaxed Multi-Layered MPC model that allows for limited interaction among the parties in each committee, while still allowing only one round to communicate towards the immediate next committee. We construct Rumors MPC protocols, where the interaction among each committee's members is constant-round. Our protocols achieve GOD and optimal corruption threshold in the perfect (resp. statistical) security setting with committees acting for $\delta=5$ (resp. $\delta=13$) rounds and $O(n^6)$ (resp. $O(\kappa n^8)$) communication.

In this study, we revisit leakage-resilient circuits (LRCs) against $\mathsf{NC}^1$-leakage and propose new constructions that minimize the reliance on leak-free hardware. Specifically, we first present a stateless LRC scheme that is resilient to $\mathsf{NC}^1$-leakage, and then extend it to a leakage-tolerant circuit with auxiliary input (AI-LTC). By integrating this with a 2-adaptive leakage-resilient encoding scheme, we achieve a stateful LRC scheme that uses a secure hardware component. In comparison to the state-of-the-art constructions against $\mathsf{NC}^1$-leakage by Miles and Viola (STOC 2013), both the encoder during the leak-free phase in our stateless LRC and the secure hardware component in our stateful LRC are typically much smaller, as their sizes are independent of the original circuit size. Additionally, we provide a non-black-box instantiation of stateful LRC, resulting in a smaller compiled circuit. The security of all our constructions is based on the very mild worst-case assumption $\mathsf{NC}^1 \subsetneq \oplus\mathsf{L}/\mathsf{poly}$, which is strictly weaker than the assumption $\mathsf{NC}^1 \subsetneq \mathsf{L}$ used by Miles and Viola. Furthermore, we propose a generic conversion from AI-LTCs to non-interactive zero-knowledge proofs with offline simulation (oNIZK) for all $\mathsf{NP}$ in the fine-grained setting. Our instantiation derived from it has small common reference strings, perfect soundness, zero-knowledge against adversaries in $\mathsf{NC}^1$ under $\mathsf{NC}^1 \subsetneq \oplus\mathsf{L}/\mathsf{poly}$, and minimal verification complexity. Finally, we show that any fine-grained oNIZK cannot simultaneously achieve perfect soundness and verifiable common reference strings, thereby ruling out the possibility of constructing stateful LRCs without secure hardware by eliminating the trusted setup of our AI-LTC.

Finding the largest pair of consecutive $B$-smooth integers for a fixed value of $B$, also called a $B$-smooth twin, is computationally challenging. It has only been provably done for $B \leq 100$ and heuristically for $100 < B \leq 113$. We improve this by detailing a new algorithm to find such smooth twins. The core idea is to solve the shortest vector problem (SVP) in a well-constructed lattice. Using a heuristic about smooth numbers in short intervals, we give an estimate of the size of the largest smooth twin for a given $B$. We are able to significantly increase $B$ and notably report the heuristically largest twin with $B = 751$, which has $196$ bits. By slightly modifying the lattice, we are able to find even larger twins, but the resulting smoothness bound will not always be optimal. This notably includes a $213$-bit twin with $B = 997$, which is the largest twin found in this work.

Let f be an arbitrary positive integer valued function. The goal of this note is to show that one can construct a finitely generated group in which the discrete log problem is polynomially equivalent to computing the function f. In particular, we provide infinite, but finitely generated groups, in which the discrete logarithm problem is arbitrarily hard. As another application, we construct a family of two-generated groups that have polynomial time word problem and NP-complete discrete log problem. Additionally, using our framework, we propose a generic scheme of cryptographic protocols, which might be of independent interest.

Homomorphic encryption (HE) is a promising technique for privacy-preserving data analysis. Several HE schemes have been developed, with the CKKS and TFHE schemes being two of the most advanced. However, due to their differences, it is hard to compare their performance and suitability for a given application. We therefore conducted an empirical study of the performance of the two schemes in a comparable scenario. We benchmarked the commonly used operations addition, multiplication, division, square root, evaluation of a polynomial and a comparison function, each on a common pair of datasets with 65536 32-bit integers. Since the CKKS scheme is an approximate scheme, we set a requirement of at least 32 bits of precision to match that of the input data. Our results show that CKKS outperforms TFHE in most operations. TFHE’s only advantage is its fast bootstrapping. Even though TFHE performs bootstrapping after every operation, while CKKS typically performs bootstrapping only after a certain number of multiplications, CKKS’s bootstrapping still presents a bottleneck. This can be seen specifically with the comparison operation, where TFHE is much faster than CKKS in many settings, as it requires several bootstrapping operations in CKKS due to its multiplicative depth. Generally speaking, CKKS should be preferred in applications which can be parallelized. CKKS’s advantages decreases in applications with a large depth that require many bootstrapping operations.

Distributed social networking services (SNSs) recently received significant attention as an alternative to traditional, centralized SNSs, which have inherent limitations on user privacy and freedom. We provide the first in-depth security analysis of Nostr, an open-source, distributed SNS protocol developed in 2019 with more than 1.1 million registered users. We investigate the specification of Nostr and the client implementations and present a number of practical attacks allowing forgeries on various objects, such as encrypted direct messages (DMs), by a malicious user or a malicious server. Even more, we show a confidentiality attack against encrypted DMs by a malicious user exploiting a flaw in the link preview mechanism and the CBC malleability. Our attacks are due to cryptographic flaws in the protocol specification and client implementation, some of which in combination elevate the forgery attack to a violation of confidentiality. We verify the practicality of our attacks via Proof-of-Concept implementations and discuss how to mitigate them.

POKE (POint-based Key Exchange), proposed by Basso and Maino at Eurocrypt 2025, is currently the fastest known isogeny-based public-key encryption scheme. Although POKE is secure against currently known key-recovery attacks, there is no known reduction from key-recovery security to IND-CPA security. In this work, we propose INKE, a variant of POKE that replaces torsion points in the encryption process with intermediate elliptic curves. This modification enables a quantum reduction from key-recovery security to IND-CPA security in the algebraic isogeny model (AIM), while maintaining the practical performance. Although INKE is overall slower than POKE and has larger public-key and ciphertext sizes, it remains more efficient than other group-action-based key exchange protocols such as CSIDH and CORAL that admit reductions from key-recovery security to shared-secret security in algebraic group action model (AGAM). To illustrate the practical overhead of INKE compared to POKE, we provide an optimized C implementation together with detailed benchmark comparisons at each security level.

This paper presents a novel key-based access control technique for secure outsourcing key-value stores where values correspond to documents that are indexed and accessed using keys. The proposed approach adopts Shamir’s secret-sharing that offers unconditional or information-theoretic security. It supports keyword-based document retrieval while preventing leakage of the data, access rights of users, or the size (i.e., volume of the output that satisfies a query). The proposed approach allows servers to detect (and abort) malicious clients from gaining unauthorized access to data, and prevents malicious servers from altering data undetected while ensuring efficient access – it takes 231.5ms over 5,000 keywords across 500,000 files

A Proof of Work (PoW) is an important construction for spam-mitigation and distributed consensus protocols. Intuitively, a PoW is a short proof that is easy for the verifier to check but moderately expensive for a prover to generate. However, existing proofs of work are not egalitarian in the sense that the amortized cost to generate a PoW proof using customized hardware is often several orders of magnitude lower than the cost for an honest party to generate a proof on a personal computer. Because Memory-Hard Functions (MHFs) appear to be egalitarian, there have been multiple attempts to construct Memory-Hard Proofs of Work (MHPoW) which require memory-hard computation to generate, but are efficient to verify. Biryukov and Khovratovich (Usenix, 2016) developed a MHPoW candidate called Merkkle Tree Proofs using used the Argon2d MHF. However, they did not provide a formal security proof and Dinur and Nadler (Crypto, 2017) found an attack which exploited the data-dependencies of the underlying Argon2d graph. We revisit the security of the MTP framework and formally prove, in the parallel random oracle model, that the MTP framework is sound when instantiated with a suitable {\em data-independent} Memory-Hard function. We generically lower bound the cumulative memory cost (cmc) of any prover for the protocol by the pebbling cost of the ex-post facto graph. We also prove that as long as the underlying graph of the original iMHF is sufficiently depth-robust that, except with negligible probability, the ex-post facto will have high cumulative memory cost (cmc). In particular, if we instantiate the iMHF with DRSample then we obtain a MHPoW with the following properties: (1) An honest prover for the protocol can run in sequential time $O(N)$, (2) The proofs have size $\mathtt{polylog}(N)$ and can be verified in time $\mathtt{polylog}(N)$ (3) Any malicious prover who produces a valid proof must incur high cumulative memory complexity at least $\Omega\left(\frac{N^2}{\log N}\right)$. We also develop general pebbling attacks to which we use to show that (1) any iMHF based MHPoW using the MTP framework has proof size at least $\Omega\left(\log^2 N/\log \log N \right)$, and (2) at least $\tilde{\Omega}(N^{0.32})$ when the iMHF is instantiated with Argon2i, the data-independent version of Argon2.

Proof-of-work allows Bitcoin to boast security amidst arbitrary fluctuations in participation of miners throughout time, so long as, at any point in time, a majority of hash power is honest. In recent years, however, the pendulum has shifted in favor of proof-of-stake-based consensus protocols. There, the sleepy model is the most prominent model for handling fluctuating participation of nodes. However, to date, no protocol in the sleepy model rivals Bitcoin in its robustness to drastic fluctuations in participation levels, with state-of-the-art protocols making various restrictive assumptions. In this work, we present a new adversary model, called external adversary. Intuitively, in our model, corrupt nodes do not divulge information about their secret keys. In this model, we show that protocols in the sleepy model can meaningfully claim to remain secure against fully fluctuating participation, without compromising efficiency or corruption resilience. Our adversary model is quite natural, and arguably naturally captures the process via which malicious behavior arises in protocols, as opposed to traditional worst-case modeling. On top of which, the model is also theoretically appealing, circumventing a barrier established in a recent work of Malkhi, Momose, and Ren.

Designing cryptographic protocols and proving these rigorously secure is an arduous and challenging task. Among the methods commonly used to prove security of cryptographic protocols, formalizing it in Canneti's Universal Composability (UC) Framework offers several benefits: (1) Modular design, (2) demonstrating that security remains under arbitrary composition and concurrent execution, (3) the security against any computationally polynomially bound adversary. However, working within the UC Framework can be cumbersome, requires a long time commitment by the prover, and it is prone to errors. While utilization of proof assistants in Cryptography and IT Security is a prominent research area, proof assistants for UC are still in their infancy. Here we show our ongoing work to utilize model checking for verification of proofs in the UC Framework, which to the best of our knowledge is the first attempt to do so. In this work we (1) formally create a Markov Decision Process (MDP) encoding a given proof in the UC Framework, (2) define and proof notions of soundness and completeness for the constructed MDP, (3) implement a proof of concept and (4) demonstrate practical feasibility through experimental evaluation. In summary, in this work we lay out the formal foundations for model checking UC proofs and create a tool that can not only be used for proof verification but also as an assistant for developing proofs in the UC Framework.

Passwords remain the dominant form of authentication on the Internet. The rise of single sign-on (SSO) services has centralized password storage, increasing the devastating impact of potential attacks and underscoring the need for secure storage mechanisms. A decade ago, Facebook introduced a novel approach to password security, later formalized in Pythia by Everspaugh et al. (USENIX'15), which proposed the concept of password hardening. The primary motivation behind these advances is to achieve provable security against offline brute-force attacks. This work initiated significant follow-on research (CCS'16, USENIX'17), including Password-Hardened Encryption (PHE) (USENIX'18, CCS'20), which was introduced shortly thereafter. Virgil Security commercializes PHE as a software-as-a-service solution and integrates it into its messenger platform to enhance security. In this paper, we revisit PHE and provide both negative and positive contributions. First, we identify a critical weakness in the original design and present a practical cryptographic attack that enables offline brute-force attacks -- the very threat PHE was designed to mitigate. This weakness stems from a flawed security model that fails to account for real-world attack scenarios and the interaction of security properties with key rotation, a mechanism designed to enhance security by periodically updating keys. Our analysis shows how the independent treatment of security properties in the original model leaves PHE vulnerable. We demonstrate the feasibility of the attack by extracting passwords in seconds that were secured by the commercialized but open-source PHE provided by Virgil Security. On the positive side, we propose a novel, highly efficient construction that addresses these shortcomings, resulting in the first practical PHE scheme that achieves security in a realistic setting. We introduce a refined security model that accurately captures the challenges of practical deployments, and prove that our construction meets these requirements. Finally, we provide a comprehensive evaluation of the proposed scheme, demonstrating its robustness and performance.

Multivariate cryptography is one of the challenging candidates for post-quantum cryptography. There exists a huge variety of proposals, most of them have been broken substantially. Multivariate schemes are usually constructed by applying two secret affine invertible transformations $\mathcal S,\mathcal T$ to a set of multivariate polynomials $\mathcal{F}$ (often quadratic). The secret polynomials $\mathcal{F}$ possess a trapdoor that allows the legitimate user to find a solution of the corresponding system, while the public polynomials $\mathcal G=\mathcal S\circ\mathcal F\circ\mathcal T$ look like random polynomials. In [Calderini, M., Caminata, A., Villa, I. A New Multivariate Primitive from CCZ Equivalence. J. Cryptol. 38, 25 (2025)], the authors addressed the above challenge by presenting a promising new way of constructing a multivariate scheme by considering the CCZ equivalence, which has been introduced and studied in the context of vectorial Boolean functions. The resulting proposal is called Pesto with security parameters $s,t,m,n,q$, where $n$ is the number of variables, $s,t,m\leq n$ and $q$ the size of the finite base field $\mathbb{F}_q$. In this paper we present an attack against Pesto by constructing an equivalent secret key from the public key. This attack has a precomputation phase with a complexity of \[\textrm{max}\left\{{\mathcal{O}\left(n^{6}(m-t)\right),\mathcal{O}\left(\frac{(m-t)(n-t)^2(n-t-s)q^s}{\mathcal{P}(q,n-t-s)}\right)}\right\}\] base field operations on average and an online complexity of \[\mathcal{O}(q^s(m-t)(n-t-s) \cdot \min(m-t,n-t-s) + q^st (n-t)^2 + q^st^3)\] base field operations to decipher a message or forge a signature, where $\mathcal{P}(q,k) := \prod_{i=1}^k (1-1/q^i)$. Thus, our attack breaks Pesto for any practical choice of the security parameters $n,m,s,t,q$ and renders the concrete construction underlying Pesto insecure.

Vertical federated learning (VFL) enables a cohort of parties with vertically partitioned data to collaboratively train a machine learning (ML) model without requiring them to centralise their data. Each party feeds its data to its local model, with output fed to a global model. However, this configuration requires parties to share some intermediary results during training, which include the output and the gradients of the local models. These intermediary results can reveal insights into the parties' data, and can be protected by secret sharing them with secure multiparty computation (MPC). However, this increases the total number of communications and makes the VFL training significantly slower. In this work, we introduce MUSE-VFL to accelerate the computation of the local gradients by using homomorphic encryption on top of MPC for parties to directly complete this computation during backpropagation. We show theoretically that MUSE-VFL improves the complexity of the MPC baseline. Our experiments, conducted on four different ML tasks, show that the runtime needed to compute the gradients of the local models significantly outweighs the combined runtime of all other steps. This highlights the significance of MUSE-VFL, with experiments demonstrating a training runtime faster by 30% to 35% for LAN and 32% to 50% for WAN.

This work presents a provably-secure lattice-based multisignature scheme which requires only a single round of communication, whereas the existing works need two or three rounds. The reduction in the number of rounds for the proposed scheme is achieved by utilizing lattice trapdoors. In order to generate multisignatures securely, our scheme however requires an honest centralized server that maintains the trapdoor of a shared matrix used in the scheme.

We present a fully homomorphic encryption scheme which natively supports arithmetic and logical operations over large ``machine words'', namely plaintexts of the form $\mathbb{Z}_{2^n}$ (e.g.\ $n=64$). Our scheme builds on the well-known BGV framework, but deviates in the selection of number field and in the encoding of messages. This allows us to support large message spaces with only modest effect on the noise growth. Arithmetic operations (modulo $2^n$) are supported natively similarly to BGV-style FHE schemes, and we present an efficient bootstrapping procedure for our scheme. Our bootstrapping algorithm has the feature that along the way it decomposes our machine word into bits, so that during bootstrapping it is possible to perform logical operations (essentially addressing each bit in the message independently). This means that during a single bootstrapping cycle we can perform logical operations on $n$ bits. For example, a ``greater than'' operation (if $x> y$ output $1$, otherwise $0$), only requires a single subtraction and a single bootstrapping cycle. Along the way we present a number of new tools and techniques, such as a generalization of the BGV modulus switching technique to a setting where the plaintext and ciphertext moduli are ideals (and not numbers).

We study the approximate Hermite Shortest Vector Problem (HSVP) in ideal lattices in orders of quaternion algebras. For one- and two-sided ideals respectively, we show that for almost all ideals we may solve HSVP in a sublattice of dimension at most one half (respectively, one quarter) of the original lattice dimension, with only small losses in the approximation factor. For two-sided ideals in a cryptographically-relevant family of maximal orders, we obtain approximation factors independent of the algebraic norm of the ideal. For one-sided ideals, we obtain a similar result for a large and natural family of ideal lattices. Finally, we turn our mathematical results into algorithms, and give an unconditional quantum polynomial time algorithm to solve HSVP in ideals of maximal orders of quaternion algebras, given an oracle for HSVP in ideals of maximal orders of number fields, in lower dimension.

Privacy-preserving decision tree inference is a fundamental primitive in privacy-critical applications such as healthcare and finance, yet existing protocols rely heavily on secure selection, which accounts for more than half of the total cost. We introduce a new paradigm that eliminates this limitation by replacing multiple secure selections with a single permutation, whose cost is comparable to that of a single secure selection. Our scheme significantly reduces both computation and communication overhead compared to SOTA. Comprehensive benchmarks show an 86 % reduction in model evaluation versus the state-of-the-art FSS protocol by Ji et al., and a 99.9 % reduction versus the OT-based protocol of Ma et al. Overall, our benchmark shows that our protocol achieves a performance improvement of 20 tiems over Ma et al.’s scheme and 4.5 times over Ji et al.’s scheme.

The argument size of succinct non-interactive arguments (SNARG) is a crucial metric to minimize, especially when the SNARG is deployed within a bandwidth constrained environment. We present a non-recursive proof compression technique to reduce the size of hash-based succinct arguments. The technique is black-box in the underlying succinct arguments, requires no trusted setup, can be instantiated from standard assumptions (and even when $\mathsf{P} = \mathsf{NP}$!) and is concretely efficient. We implement and extensively benchmark our method on a number of concretely deployed succinct arguments, achieving compression across the board to as much as $60\%$ of the original proof size. We further detail non-black-box analogues of our methods to further reduce the argument size.

In recent years and with the emergence of the industrial revolution, the secure data sharing schemes have been developed in IoT platforms and have been recognized as a hot topic in industry and academia. These schemes enable IoT devices to securely share their sensed data in industrial environments with clients through an appropriate infrastructure and intermediary entities. The research conducted in this field shows the existence of various security challenges and solutions. Data privacy, data authentication, fairness and accountability are some of the most important security features presented. Recently, in paper [Sengupta-Ruj-Bit, TNSM 2023] proposed a secure sharing scheme and claimed that it covers all the mentioned security features even when entities collude with each other. In this paper, we investigate the security analysis of this scheme, and show that it does not cover the claimed fairness property. Therefore, the mentioned scheme is vulnerable and cannot be used as a valid scheme in real-world applications.

Transitioning secure information systems to post-quantum cryptography (PQC) comes with certain risks, such as the potential for switching to PQC schemes with as yet undiscovered vulnerabilities. Such risks can be mitigated by combining multiple schemes in such a way that the resulting hybrid scheme is secure provided at least one of the ingredient schemes is secure. In the case of key-encapsulation mechanisms (KEMs), this approach is already in use in practice, where the PQC scheme ML-KEM is combined with “traditional” X25519 key exchange. Combining multiple KEMs to construct a single hybrid KEM is largely straightforward, except for the crucial choice of how to derive the final shared secret key. A generic method for doing this in a manner that preserves IND-CCA security is to include the keys and ciphertexts of all ingredient KEMs in an appropriate key derivation step. In the specialized X-Wing construction, one instead relies on a special property of ML-KEM to avoid including its ciphertext in key derivation. In this work, we show that this optimization can be done in a more general setting. Specifically, when combining multiple KEMs one need not include the ciphertext of any KEM that satisfies ciphertext second preimage resistance (C2PRI)—provided the key combination step is performed using a split-key pseudorandom function. We also prove that any KEM constructed from a certain set of Fujisaki-Okamoto (FO) transforms satisfies C2PRI in the random oracle model. This applies to KEMs such as BIKE, Classic McEliece, HQC, and ML-KEM.

In Neural Cryptanalysis, a deep neural network is trained as a cryptographic distinguisher between pairs of ciphertexts $(F(X), F(X \oplus \delta))$, where $F$ is either a random permutation or a block cipher, $\delta$ is a fixed difference. The AutoND framework aims to se neural distinguishers that are treated as a generic tool and discourages cipher-specific optimizations. On the other hand, works such as $[\text{LLS}^+24]$ obtain superior distinguishers by adding dedicated features, such as selected parts of the difference in the previous rounds, to the input of the neural distinguishers. In this paper, we study $\text{Generic Partial Decryption}$ as a feature engineering technique and integrate it within a fully automated pipeline, where we evaluate its effect independently of the number of pairs per sample, with which feature engineering is often combined. We show that this technique matches state-of-the-art dedicated approaches on Simon and Simeck. Additionally, we apply it to Aradi, and present a practical neural-assisted key recovery for 5 rounds, as well as a 7-rounds key recovery with $2^{70}$ time complexity. Additionally, we derive useful information from the neural distinguishers and propose a non-neural version of our 5-round key recovery.

The shuffle model is a widely used abstraction for non-interactive anonymous communication. It allows $n$ parties holding private inputs $x_1,\dots,x_n$ to simultaneously send messages to an evaluator, so that the messages are received in a random order. The evaluator can then compute a joint function $f(x_1,\dots,x_n)$, ideally while learning nothing else about the private inputs. The model has become increasingly popular both in cryptography, as an alternative to non-interactive secure computation in trusted setup models, and even more so in differential privacy, as an intermediate between the high-privacy, little-utility local model and the little-privacy, high-utility central curator model. The main open question in this context is which functions $f$ can be computed in the shuffle model with statistical security. While general feasibility results were obtained using public-key cryptography, the question of statistical security has remained elusive. The common conjecture has been that even relatively simple functions cannot be computed with statistical security in the shuffle model. We refute this conjecture, showing that all functions can be computed in the shuffle model with statistical security. In particular, any differentially private mechanism in the central curator model can also be realized in the shuffle model with essentially the same utility, and while the evaluator learns nothing beyond the central model result. This feasibility result is obtained by constructing a statistically secure additive randomized encoding (ARE) for any function. An ARE randomly maps individual inputs to group elements whose sum only reveals the function output. Similarly to other types of randomized encoding of functions, our statistical ARE is efficient for functions in $NC^1$ or $NL$. Alternatively, we get computationally secure ARE for all polynomial-time functions using a one-way function. More generally, we can convert any (information-theoretic or computational) ``garbling scheme'' to an ARE with a constant-factor size overhead.

This paper proposes DIMSEPP, a decentralized identity management system that enhances privacy while preserving blockchain verifiability. The system cryptographically enforces data minimal disclosure principles by storing attribute commitments on-chain and validating them through zero-knowledge proofs, allowing users to demonstrate attribute validity without revealing sensitive values. The architecture maintains full compatibility with existing DID standards through standard document structures and verification methods. Security analysis demonstrates provable guarantees under standard cryptographic assumptions. Practical evaluation confirms the system's efficiency for resource-constrained environments, supporting deployment in applications where both privacy and verifiability are essential.

We design a fully homomorphic encryption for moduli of the form $b^k$ with small $b$. Our construction asymptotically improves upon Kim [TCHES'25]: for fixed $b$, the multiplication latency decreases from $O(k \log k)$ to $O(\log k)$ while preserving amortized latency. Our experiments show that our $64$-bit multiplication achieves $\approx 6 \times$ lower latency than Kim and slightly lower latency than TFHE-rs, while improving amortized latency by three orders of magnitude over TFHE-rs. The performance gap widens for larger precision. For instance, our $512$-bit multiplication achieves $\approx 49 \times$ lower latency and four orders of magnitude lower amortized latency than TFHE-rs. We also outperform Boneh and Kim [Crypto'25] with $4.70 \times$ lower latency and $75.3 \times$ lower amortized latency for $256$-bit multiplication.

The development of cryptographic schemes which remain secure in the post-quantum era is an urgent challenge, particularly in light of the growing ubiquity of low-power devices and the looming threat of quantum computing. Identity-Based Encryption (IBE) offers a compelling alternative to traditional Public Key Infrastructures by simplifying key management, but most classical IBE schemes rely on number-theoretic assumptions that are vulnerable to quantum attacks. In response, Koshiba and Takashima proposed a novel approach based on Isogenous Pairing Groups (IPGs) [ 12 ], claiming partial quantum resistance. In this work, we critically examine their construction and security claims and investigate upon the security in standard security notions. We show that the proposed scheme, despite its theoretical elegance, reduces to the Elliptic Curve Dis- crete Logarithm Problem (ECDLP) on supersingular curves, which can be broken in polynomial time by quantum algorithms in the IND-ID-CPA setting and in subexponential time classically in the authors security models. Our analysis reveals structural weaknesses inherent to the IPG framework, such as the use of explicit group elements in prime-order groups and exploitable isogeny homomorphisms, which undermine the post-quantum security of isogeny based cryptography. These findings suggest that IPG-based constructions, which use more than a single point per pairing group, are unlikely to provide robust post-quantum security. In Koshiba and Takashima’s proposed IBE system, we can directly observe this, when paying regards to not only the IBE’s Master Secret Key but also Users’ Secret Keys.