In this paper, we propose a new post-quantum lattice-based IND-CCA2-secure key encapsulation mechanism (KEM) named Lore. The scheme is based on a variant of MLWR problem following LPR structure with two new technologies called variable modulus and CRT compression, which provide a balance of decryption failure probability and ciphertext size. We prove its security in ROM/QROM and provide concrete parameters as well as reference implementation to show that our scheme enjoys high efficiency, compact bandwidth and proper decryption failure rate(DFR) corresponding to its security levels compared with former results.

Zero-Knowledge Proofs (ZKPs) are a rapidly growing technique for privacy-preserving and verifiable computation. ZKPs enable one party (a prover: $\mathcal{P}$) to prove to another (a verifier: $\mathcal{V}$) that a statement is true or correct without revealing any additional information. This powerful capability has led to ZKPs being applied and proposed for application in blockchain technologies, verifiable machine learning, and electronic voting. However, ZKPs have yet to see widespread, ubiquitous adoption due to the exceptionally high computational complexity of the proving process. Naturally, there has been recent work to accelerate ZKP primitives and protocols using GPUs and ASICs. However, the protocols considered so far face one of two challenges: they require a trusted setup for each new application or generate large proofs with high verification costs, limiting their applicability in scenarios with numerous verifiers or strict verification time constraints. HyperPlonk is a state-of-the-art ZKP protocol that supports both one-time, universal setup and small proof sizes/verification costs expected by publicly verifiable, consensus-based systems (e.g., blockchain). While HyperPlonk's setup and verifier properties are highly desirable, the proving phase is costly. A HyperPlonk prover must compute on large bitwidths (e.g., 255-381b) and polynomials (e.g., of degree 2$^{24}$), employs computationally (e.g., MSM) and bandwidth (e.g., SumCheck) intensive kernels, and the complete protocol comprises many steps, each constituting distinct kernels. We present an accelerator, \emph{zkSpeed}, to address these challenges and effectively accelerate HyperPlonk. zkSpeed provides hardware support for all major primitives (e.g., SumCheck and Multi-Scalar Multiplications (MSMs)) and judiciously schedules each protocol phase onto the allocated hardware. We leverage high-level synthesis to thoroughly explore and optimize the hardware design tradeoffs of each unit. These are then input into a full-chip simulator for large-scale design space exploration to optimize all aspects of the architecture in unison. Our Pareto analysis demonstrates that with a 366mm$^2$ chip and 2 TB/s of off-chip bandwidth, zkSpeed is able to accelerate the entire proof generation by 801$\times$ (geomean) over a CPU baseline.

Anonymous credentials allow users to authenticate themselves in an anonymous and unlinkable fashion. By the end of 2026, EU member states will be required to issue digital identity wallets to their residents that enable authentication in this manner. In decentralized settings, we desire schemes with additional properties: schemes that allow multiple authorities to issue credentials, hide the identities of the issuers, and allow verifiers to dynamically choose their policies. We present the first construction of issuer-hiding anonymous credentials with constant-sized showing, threshold issuance, and no requirement of interactive setup. Silent (non-interactive) setup is crucial as the various issuers may be slow-moving, independent organizations that are unwilling to coordinate in a distributed key generation protocol beforehand. Our construction also supports dynamic verifier policies. This is useful if different verifiers disagree about which issuers they trust or what threshold they accept. At the heart of our scheme, we construct threshold structure-preserving signatures with silent setup and prove security in the generic group model. We also provide a NIZK for anonymous showing that is more efficient than a standard application of Groth-Sahai proofs. Finally, we provide an implementation of our scheme in Rust, along with concrete efficiency metrics.

Blockchain protocols based on the popular ``Proof-of-Work'' mechanism yield public transaction ledgers maintained by a group of distributed participants who solve computationally hard puzzles to earn the right to add a block. The success and widespread adoption of this mechanism has led to staggering energy consumption devoted to solving such (otherwise) ``useless'' puzzles. While the environmental impacts of the framework have been widely criticized, this has been the dominant distributed ledger paradigm for years. The Ofelimos ``Proof-of-Useful-Work'' protocol (Fitzi et al., CRYPTO 2022) addressed this by establishing that useful combinatorial problems could replace the conventional hashing puzzles, yielding a provably secure blockchain that meaningfully utilizes the computational work that underlies the protocol. The usefulness to wastefulness ratio of Ofelimos hinges on the properties of its underlying generic distributed local-search algorithm---Doubly Parallel Local Search (DPLS). We observe that this search procedure is particularly wasteful when exploring steep regions of the solution space. To address this issue, we introduce Frequently Rerandomized Local Search (FRLS), a new generic distributed local search algorithm that we show to be consistent with the Ofelimos architecture. While this algorithm retains ledger security, we show that it also provides compelling performance on benchmark problems arising in practice: Concretely, state-of-art local-search algorithms for cumulative scheduling and warehouse location can be directly adapted to FRLS and we experimentally demonstrate the efficiency of the resulting algorithms.

The advent of quantum computing necessitates a rigorous reassessment of classical cryptographic primitives, particularly lightweight block ciphers (LBCs) deployed in resource-constrained environments. This work presents a comprehensive quantum implementation and security analysis of the Feistel-based LBC MIBS against quantum cryptanalysis. Using the inherent reversibility of its structure, we develop a novel ancilla-free quantum circuit that optimizes qubit count and depth. For MIBS-64 and MIBS-80, our implementation achieves quantum costs of 23,371 and 24,363, requiring 128 and 144 qubits, respectively, with a depth of 4,768. We subsequently quantify the cipher's vulnerability to Grover’s key-search algorithm under the NIST PQC security constraint $\texttt{MAXDEPTH}$. By constructing Grover oracles using inner parallelization with multiple plaintext-ciphertext pairs to suppress false positives, we demonstrate total quantum attack costs of approximately $2^{94}$ for MIBS-64 and $2^{111}$ for MIBS-80. These values fall below NIST’s Level-1 security threshold ($2^{170}$), confirming the susceptibility of both MIBS variants to quantum key-recovery attacks despite their classical lightweight efficiency.

A recent work by Kate et al. [EPRINT 2025] proposes a community-based social recovery scheme (SKR), where key-owners can use a subset of other community members as guardians, and in exchange, they play guardians to support other participants' key recovery. Their construction relies on a new concept called bottom-up secret sharing (BUSS). However, they do not consider a crucial feature, called traceability, which ensures that if more than a threshold number of the guardians collude, at least some colluders' identities can be traced -- thereby deterring participants from colluding. In this paper, we incorporate traceability into the community social key recovery as an important feature. We first introduce the notion of traceable BUSS, which allows tracing colluders by accessing a reconstruction box. Then, extending the work of Boneh et al. [CRYPTO 2024], we propose the first traceable BUSS construction. Finally, we show how to generically use a traceable BUSS scheme to construct a traceable SKR in the aforementioned community setting. Overall, this is the first scheme combining decentralized key management with traceability, marrying BUSS’s scalability with the deterrence of traceable secret sharing.

Key Encapsulation Mechanisms (KEMs) are a critical building block for hybrid encryption and modern security protocols, notably in the post-quantum setting. Given the asymmetric public key of a recipient, the primitive establishes a shared secret key between sender and recipient. In recent years, a large number of abstract designs and concrete implementations of KEMs have been proposed, e.g., in the context of the NIST process for post-quantum primitives. In this work, we (i) establish stronger security notions for KEMs, and (ii) develop a symbolic analysis method to analyze security protocols that use KEMs. First, we generalize existing security notions for KEMs in the computational setting, introduce several stronger security notions, and prove their relations. Our new properties formalize in which sense outputs of the KEM uniquely determine, i.e., bind, other values. Our new binding properties can be used, e.g., to prove the absence of attacks that were not captured by prior security notions, such as re-encapsulation attacks. Second, we develop a family of fine-grained symbolic models that correspond to our hierarchy of computational security notions, and are suitable for the automated analysis of KEM-based security protocols. We encode our models as a library in the framework of the Tamarin prover. Given a KEM-based protocol, our approach can automatically derive the minimal binding properties required from the KEM; or, if also given a concrete KEM, can analyze if the protocols meets its security goals. In case studies, Tamarin automatically discovers, e.g., that the key exchange protocol proposed in the original Kyber paper requires stronger properties from the KEM than were proven in the paper.

Range proofs serve as a protocol for the prover to prove to the verifier that a committed number resides within a specified range, such as $[0,2^n)$, without disclosing the actual value. These proofs find extensive application in various domains, including anonymous cryptocurrencies, electronic voting, and auctions. However, the efficiency of many existing schemes diminishes significantly when confronted with batch proofs encompassing multiple elements. The pivotal challenge arises from their focus on the commitment to a singular element rather than a vector. Addressing this gap, our paper introduces MissileProof, a zero-knowledge, succinct, non-interactive argument of knowledge tailored for the range proof of a vector commitment. Our core contribution lies in reducing this argument to a bi-to-uni variate SumCheck problem and the bivariate polynomial ZeroTest problem, and design two polynomial interactive oracle proofs (PIOPs) for each problem. Our principal innovation involves the transformation of this argument into a bi-to-uni variate SumCheck problem and the bivariate polynomial ZeroTest problem. To tackle these challenges, we devise two Polynomial Interactive Oracle Proofs (PIOPs) for each problem. As far as we know, our scheme has the optimal proof size ($O(1)$), the optimal statement length ($O(1)$), and the optimal verification time ($O(1)$), at the expense of slightly sacrificing proof time ($O(l\log l\cdot n\log n)$ operations on the prime field for FFT and $O(ln)$ group exponentiations in $\mathbb{G}$). We prove the security of this scheme. Experimental data shows for a committed vector of length $l = 16384$ and $n=64$, our work has the best performance in terms of the statement length (0.03125KB), proof size (1.375KB) and verification time (0.01s) with a slightly increased proof time (614s).

Private Set Union (PSU) enables two parties to compute the union of their input sets without revealing anything else. Depending on set sizes, PSU is studied in balanced and unbalanced settings. Tu et al. (USENIX Security 2025) presented state-of-the-art enhanced PSU (ePSU) protocols under a unified framework in both settings, achieving enhanced security by preventing during-execution leakage. However, we observe that directly applying hash-to-bin on input sets within their framework introduces potential privacy risks. Moreover, the communication of their unbalanced ePSU still scales with the larger set size, rather than being linear in only the smaller set size. In this work, we address these open problems. We employ a combination of oblivious pseudorandom function (OPRF) and shuffling to mitigate the potential privacy leakage that arises when directly applying the hash-to-bin within the framework of Tu et al. (USENIX Security 2025). Building upon this, we further optimize their balanced ePSU protocol by leveraging a bidirectional oblivious key-value store (OKVS). Compared with the corrected version of Tu et al.'s balanced ePSU, ours achieves a $1.1-3.0\times$ shrinking in communication and a $1.2-1.6\times$ speedup in runtime. We design the first unbalanced ePSU whose communication is linear solely in the smaller set size. Since no hash-to-bin is used, it is inherently free from the associated privacy leakage. With the smaller set size fixed at $2^{10}$, ours reduces communication by $1.5-45.8\times$ compared with corrected version of Tu et al.'s unbalanced ePSU, while achieving $1.3-6.7\times$ runtime speedups.

Fuzzy Message Detection, or FMD, outsources detection of messages to an untrusted server, Beck et. al. CCS 2021. In this paper, we extend FMD to the multi-key setting: several servers are given different detection keys, all extracted from a single secret key. Multi-key FMD allows to combine tests from multiple servers locally by each receiver. This allows to set high false-positive rates on the servers, while attaining low rates on the receiver side. Striking this way a better balance between privacy and efficiency. We further formalize the notion of stealth public keys in the FMD setting. Last, we provide two constructions, one with short public keys.

We present a generic construction of adaptive trapdoor function (TDF) from the combination of any TDF and pseudorandom-ciphertext public-key encryption (PKE) scheme. As a direct corollary, we can obtain adaptive TDF from any trapdoor permutation (TDP) whose domain is both recognizable and sufficiently dense. In our construction, we can prove that the function's output is indistinguishable from uniform even when an adversary has access to the inversion oracle.

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.

Cryptographic proofs are a versatile primitive. They are useful in practice not only when used as a standalone tool (for example in verifiable computation), but also when applied $\textit{on top}$ of other cryptographic functionalities — hash functions, signature schemes, and even proofs themselves — to $\textit{enhance}$ their security guarantees (for example to provide succinctness). However, when the security of the other primitive is established in the Algebraic Group Model (AGM), the security of the resulting construction does not follow automatically. We introduce a general methodology of $\textit{provable security}$ for this setting. Our approach guarantees the security of $\Pi \circ X$, the composition of a cryptographic proof $\Pi$ with a functionality $X$, whenever the security of $X$ is analysed in the AGM. Our methodology has general applicability, with immediate relevance to IVC, proof aggregation, and aggregate signatures. We obtain: - $\textbf{IVC for unbounded depth from AGM-secure proofs.}$ Incrementally Verifiable Computation (IVC) is a canonical example of composing cryptographic proofs with one another. Achieving provable security for IVC beyond constant-depth computations has remained a central open challenge. Using our methodology, we obtain new IVC instantiations that remain secure for unbounded-depth computations, when built from proofs analysed in the AGM. This broadens the class of proofs systems usable in the canonical IVC constructions to include prominent systems such as Groth16 and Marlin – proof systems not covered by prior analyses (e.g., Chiesa et al., TCC 2024). - $\textbf{Succinct aggregation of AGM-secure signatures.}$ Applying our framework, we give the first provable security for the folklore proof-based construction of aggregate signatures from AGM-secure signatures. Prior analyses either exclude AGM-secure signatures or rely on heuristic assumptions. Establishing this result required resolving additional technical challenges beyond applying our framework – for example, reasoning about the security of proof systems in the presence of signing oracles.

Constructing a supersingular elliptic curve whose endomorphism ring is isomorphic to a given quaternion maximal order (one direction of the Deuring correspondence) is known to be polynomial-time assuming the generalized Riemann hypothesis [KLPT14; Wes21], but notoriously daunting in practice when not working over carefully selected base fields. In this work, we speed up the computation of the Deuring correspondence in general characteristic, i.e., without assuming any special form of the characteristic. Our algorithm follows the same overall strategy as earlier works, but we add simple (yet effective) optimizations to multiple subroutines to significantly improve the practical performance of the method. To demonstrate the impact of our improvements, we show that our implementation achieves highly practical running times even for examples of cryptographic size. One implication of these findings is that cryptographic security reductions based on KLPT-derived algorithms (such as [EHLMP18; Wes22]) have become tighter, and therefore more meaningful in practice. Another is the pure bliss of fast(er) computer algebra: We provide a Sage implementation which works for general primes and includes many necessary tools for computational number theorists' and cryptographers' needs when working with endomorphism rings of supersingular elliptic curves. This includes the KLPT algorithm, translation of ideals to isogenies, and finding supersingular elliptic curves with known endomorphism ring for general primes. Finally, the Deuring correspondence has recently received increased interest because of its role in the SQISign signature scheme [DeF+20]. We provide a short and self-contained summary of the state-of-the-art algorithms without going into any of the cryptographic intricacies of SQISign.

We study two-party secure computation in a \emph{distributed mediated} model with $D$ servers. We present \emph{information-theoretically secure} protocols for foundational primitives— $1$-out-of-$N$ and $k$-out-of-$N$ oblivious transfer (OT), Priced OT, Generalized OT, and Oblivious Multivariate Polynomial Evaluation (OMPE)—that (i) enforce receiver correctness, (ii) support an offline sender after setup, and (iii) achieve robustness against malicious receivers and malicious servers under honest-majority assumptions. Our approach reduces each primitive to a distributed scalar-product core combined with a \emph{distributed vector-validation} (DVV) mechanism that prevents unauthorized linear-combination leakage while preserving privacy. We prove unconditional privacy and robustness in the semi-honest setting and extend the guarantees to the malicious-server setting, tolerating up to $c < D/4$ or $c < D/3$ corrupt servers depending on the variant. The constructions are modular, require only lightweight client work (sharing and reconstruction), and allow the sender’s one-time upload to serve multiple, independent receivers without further interaction. We analyze the round and communication complexity of our protocols and provide empirical evidence of practical efficiency. The mediated setting naturally fits privacy-preserving services such as collaborative filtering, distributed constraint optimization, voting, and federated analytics. Collectively, our results show that distributed mediation yields simple, scalable, and unconditionally private realizations of core two-party MPC functionalities.

We develop new attacks against the Evasive LWE family of assumptions, in both the public and private-coin regime. To the best of our knowledge, ours are the first attacks against Evasive LWE in the public-coin regime, for any instantiation from the family. Our attacks are summarized below. Public-Coin Attacks. 1. The recent work by Hseih, Lin and Luo [HLL23] constructed the first Attribute Based Encryption (ABE) for unbounded depth circuits by relying on the "circular'' evasive LWE assumption. This assumption has been popularly considered as a safe, public-coin instance of Evasive LWE in contrast to its "private-coin'' cousins (for instance, see [CW25, DJM+25a]). We provide the first attack against this assumption, challenging the widely held belief that this is a public-coin assumption. 2. We demonstrate a counter-example against vanilla public-coin evasive LWE by Wee [Wee22] in an unnatural parameter regime. Our attack crucially relies on the error in the pre-condition being larger than the error in the post-condition, necessitating a refinement of the assumption. Private-Coin Attacks. 1. The recent work by Agrawal, Kumari and Yamada [AKY24a] constructed the first functional encryption scheme for pseudorandom functionalities (PRFE) and extended this to obfuscation for pseudorandom functionalities (PRIO) [AKY24c] by relying on private-coin evasive LWE. We provide a new attack against the assumption stated in the first posting of their work (subsequently refined to avoid these attacks). 2. The recent work by Branco et al. [BDJ+25] (concurrently to [AKY24c]) provides a construction of obfuscation for pseudorandom functionalities by relying on private-coin evasive LWE. We provide a new attack against their stated assumption. 3. Branco et al. [BDJ+25] showed that there exist contrived, "self-referential'' classes of pseudorandom functionalities for which pseudorandom obfuscation cannot exist. We extend their techniques to develop an analogous result for pseudorandom functional encryption. While Evasive LWE was developed to specifically avoid "zeroizing attacks'', our work shows that in certain settings, such attacks can still apply.

The potential of Attribute-Based Encryption (ABE) in the context of IoT has driven researchers to propose pairing-free ABE schemes that are suitable for resource-constrained devices. Unfortunately, many of these schemes turned out to be insecure. This fact seems to reinforce the point of view of some researchers according to which instantiating an Identity-Based Encryption (IBE) in plain Decisional Diffie-Hellman (DDH) groups is impossible. In this paper, we provide a generic Ciphertext-Policy ABE (CP-ABE) scheme with secret AND gate policy from Inner-Product Functional Encryption (IPFE). We also propose an instantiation of that generic CP-ABE scheme from the DDH assumption. From our generic CP-ABE scheme we derive an IBE scheme by introducing the concept of Clustered Identity-Based Encryption (CIBE). Our schemes show that it is possible to construct secure IBE and ABE schemes based on the classical DDH assumption. An implementation of our CIBE in Python using the Charm framework is available on GitHub.

Introduced by Halevi, Ishai, Kushilevitz, and Rabin (CRYPTO 2023), Additive randomized encodings (ARE) reduce the computation of a $k$-party function $f(x_1,\dots,x_k)$ to locally computing encodings $\hat x_i$ of each input $x_i$ and then adding them together over some Abelian group into an output encoding $\hat y = \sum \hat x_i$, which reveals nothing but the result. The appeal of ARE comes from the simplicity of the non-local computation, involving only addition. This gives rise for instance to non-interactive secure function evaluation in the shuffle model where messages from different parties are anonymously shuffled before reaching their destination. Halevi, Ishai, Kushilevitz, and Rabin constructed ARE based on Diffie-Hellman type assumptions in bilinear groups. We construct ARE assuming public-key encryption. The key insight behind our construction is that one-sided ARE, which only guarantees privacy for one of the parties, are relatively easy to construct, and yet can be lifted to full-fledged ARE. We also give a more efficient black-box construction from the CDH assumption.

This article develops a unified framework for analyzing and enhancing a family of multivariate signature schemes based on UOV. We conduct a comparative study of three recent UOV-like schemes—QR-UOV, MAYO, and SNOVA—and identify a common design principle: employing tensor product constructions to enlarge the dimension of the oil subspace. Building on this perspective, we propose a new multivariate signature scheme called TSUOV that synthesizes these insights to provide improved key and signature sizes without compromising security.

Probabilistically checkable proofs (PCPs) allow encoding a computation so that it can be quickly verified by only reading a few symbols. Inspired by tree codes (Schulman, STOC'93), we propose tree PCPs; these are PCPs that evolve as the computation progresses so that a proof for time $t$ is obtained by appending a short string to the end of an accepting proof for time $t-1$. At any given time, the tree PCP can be locally queried to verify the entire computation so far. We construct tree PCPs for non-deterministic space-$s$ computation, where at time step $t$, the proof only grows by an additional $\textnormal{poly}(s)\cdot t^\varepsilon$ bits, and the number of queries made by the verifier to the overall proof is $\textnormal{poly}(s)\cdot t^\varepsilon$, for an arbitrary constant $\varepsilon>0$. Tree PCPs are well-suited to proving correctness of ongoing computation that unfolds over time, in particular in a distributed setting where the computation is carried by mutually untrusting generations. They may be thought of as an information-theoretic analog of the cryptographic notion of incrementally verifiable computation (Valiant, TCC'08). To obtain tree PCPs, we present the first results establishing strong local testability and local correctability for tree codes, and construct a tree code that achieves both properties simultaneously.

The Enhanced ISW (E-ISW) masking scheme, recently proposed at DATE 2024, was introduced as a refinement to the classical ISW construction to restore provable security guarantees in hardware implementations affected by glitches. By enforcing input-complete gate evaluations through the use of artificial delays, E-ISW seeks to mitigate the glitch-induced leakage that compromises standard masking techniques. However, in this work, we demonstrate that this modification is fundamentally insufficient to ensure robust side-channel resistance in realistic hardware environments. We conduct a detailed analysis and present concrete examples where E-ISW fails to prevent information leakage, even when the prescribed countermeasures are correctly applied. These vulnerabilities arise due to deeper conceptual shortcomings in the design, particularly the absence of compositional reasoning about the interaction between glitches and masking. Our results show that the security claims of E-ISW do not hold in practice, and they expose critical limitations in relying on heuristic delay-based fixes without formal and compositional proofs of security. This study serves as a cautionary note for the cryptographic engineering community, emphasizing the necessity of rigorous validation when proposing enhancements to established secure computation techniques.

The emergence of Cryptographically Relevant Quantum Computers (CRQCs) threatens traditional cryptographic systems, necessitating a transition to Post-Quantum Cryptography (PQC). OpenSSL 3.0 introduced `Providers`, enabling modular cryptographic integration. This work presents the concept of a "shallow `Provider`", facilitating integration of external implementations, to achieve a higher degree of cryptographic agility. `aurora`, which we introduce as an instance of the "shallow `Provider`" methodology, integrates standardized PQC algorithms in TLS 1.3 for both key establishment and authentication, to support the PQC transition. It enhances cryptographic agility by allowing OpenSSL to dynamically adapt to evolving PQC standards and the rapidly evolving ecosystem of PQC implementations.

We propose a deterministic algorithm based on Coppersmith's method that employs a rank-3 lattice to address factoring-related problems. An interesting aspect of our approach is that we utilize the second vector in the LLL-reduced basis to avoid trivial collisions in the Baby-step Giant-step method, rather than the shortest vector as is commonly used in the literature. Our results are as follows: - Compared to the result by Harvey and Hittmeir (Math. Comp. 91 (2022), 1367–1379), who achieved a complexity of $O\left( \frac{N^{1/5} \log^{16/5} N}{(\log \log N)^{3/5}} \right)$ for factoring a semiprime $N = pq$, we demonstrate that in the balanced $p$ and $q$ case, the complexity can be improved to $O\left( \frac{N^{1/5} \log^{13/5} N}{(\log\log N)^{3/5}} \right).$ - For factoring sums and differences of powers, i.e., numbers of the form $N = a^n \pm b^n$, we improve Hittmeir's result (Math. Comp. 86 (2017), 2947–2954) from $O(N^{1/4} \log^{3/2} N)$ to $O\left( {N^{1/5} \log^{13/5} N} \right).$ - For the problem of finding $r$-power divisors, i.e., finding all integers $p$ such that $p^r \mid N$, Harvey and Hittmeir (Proceedings of ANTS XV, Res. Number Theory 8 (2022), no.4, Paper No. 94) recently directly applied Coppersmith's method and achieved a complexity of $O\left(\frac{N^{1/4r} \log^{10+\epsilon} N}{r^3}\right)$. By using faster LLL-type algorithm and sieving on small primes, we improve their result to $O\left(\frac{N^{1/4r} \log^{7+3\epsilon} N}{(\log\log N-\log 4r)r^{2+\epsilon}}\right)$. The worst case running time for their algorithm occurs when $N = p^r q$ with $q = \Theta(N^{1/2})$. By focusing on this case and employing our rank-3 lattice approach, we achieve a complexity of $O\left(r^{1/4} N^{1/4r} \log^{5/2} N \right)$. In conclusion, we offer a new perspective on these problems, which we hope will provide further insights.

Abstract. CROSS is a code-based signature based on the Restricted Syndrome Decoding Problem (R-SDP) that is currently among the fourteen candidates in the NIST standardization process. While CROSS enjoys a very competitive verification time, its primary drawback is its significantly large signature size. In this work, we introduce a new Multi-Party Computation in the Head (MPCitH) protocol for the R-SDP with the primary goal of reducing CROSS signature size. To do so, we design a publicly verifiable secret sharing scheme tailored for restricted vectors and a new multiplicative-to-additive conversion for it. These new cryptographic gadgets may be of independent interest as they can serve as building blocks for future research in multi-party computation, such as a threshold version of CROSS.

In NDSS 2024, Yu~et al. proposed AAKA, an Anonymous Authentication and Key Agreement scheme designed to protect users' privacy from mobile tracking by Mobile Network Operators (MNOs). AAKA aims to provide both anti-tracking privacy and traceability (lawful de-anonymization), allowing subscribers to access the network via anonymous proofs while enabling a Law Enforcement Agency (LEA) to trace the real identity if misbehaviors are detected. However, we identify that the AAKA scheme in NDSS 2024 is insecure since the subscriber's identity is exposed within the protocol, thereby failing to achieve the claimed privacy and traceability. Building on the repair of AAKA, we propose AAKA+, Anonymous Authentication and Key Agreement with Verifier-Local Revocation, a new mobile authentication scheme, to ensure privacy against mobile tracking. In addition to the privacy and traceability introduced in NDSS 2024, AAKA+ additionally allows the MNO to immediately assert whether the associated subscriber has been traced and revoked upon receiving an anonymous proof. We formally define the syntax and the security model of AAKA+ and propose two concrete schemes, AAKA+BB and AAKA+PS, based on the Boneh-Boyen signature and the Pointcheval-Sanders signature schemes, respectively. Both AAKA+BB and AAKA+PS are pairing-free on the user equipment side and compatible with existing cellular infrastructure. Experimental results show that our schemes are practical, with anonymous proof generation taking approximately 18 milliseconds for a constrained device.

Homomorphic Secret Sharing (CRYPTO 2016) allows a secret to be shared among two or more parties in such a way that the parties can locally evaluate a class of functions on their shares. Homomorphic secret sharing (HSS) schemes and their underlying techniques have facilitated a wide range of applications. To account for the fact that parties generating or evaluating the shares might act maliciously, variants of HSS schemes that allow detection of such malicious behavior have been introduced. However, all prior approaches of malicious HSS that capture the class of $\mathsf{NC}1$ circuits either crucially rely on a random oracle or require an non-reusable setup. In this work, we initiate the study of malicious public-key $2$-party HSS in the standard model with reusable setup, where any malicious behavior during share generation and share evaluation can be detected. Towards constructing malicious HSS, we introduce the notion of homomorphic secret sharing with robust linear reconstruction (RLR-HSS) and show that this notion readily implies malicious HSS. We outline challenges in instantiating RLR-HSS due to the error present in all current HSS constructions not relying on SHE/FHE, and show how to overcome these using derandomization techniques by Dwork et al. (EUROCRYPT 2004). Finally, we show applications of malicious HSS to compact designated verifier non-interactive zero knowledge arguments and maliciously secure $2$-party computation in the standard model (supporting the same function class as the underlying malicious HSS).

Blind signatures have received increased attention from researchers and practitioners. They allow users to obtain a signature under a message without revealing it to the signer. One of the most popular applications of blind signatures is to use them as one-time tokens, where the issuing is not linkable to the redeeming phase, and the signature under a random identifier forms a valid token. This concept is the backbone of the Privacy Pass system, which uses it to identify honest but anonymous users and protect content delivery networks from botnets. Non-interactive blind signatures for random messages were introduced by Hanzlik (Eurocrypt'23). They allow a signer to create a pre-signature with respect to a particular public key, while the corresponding secret key can later be used to finalize the signature. This non-interaction allows for more applications than in the case of blind signatures. In particular, the author suggested using regular PKI keys as the recipient public key, allowing for a distribution of one-time tokens to users outside the system, e.g., to public keys of GitHub users, similar to airdropping of cryptocurrencies. Unfortunately, despite introducing this concept, the paper fails to provide schemes that work with keys used in the wild. We solve this open problem. We introduce a generic construction of non-interactive blind signatures that relies on Yao's garbled circuit techniques and provide particular improvements to this generic setting. We replace oblivious transfer with their non-interactive variant and show how to construct them so that the recipient's public key, encoding the $\mathsf{OT}$ choice, is a standard RSA public key $(e,N)$. To improve the efficiency of the garbling, we show how to garble the signing algorithm of the pairing-based Pointcheval-Sanders (PS) signatures and the RSA-based signature scheme with efficient protocols by Camenisch and Lysyanskaya. Our technique also apply to the well-known BBS signatures. All our improvements are of independent interest and are central to our contribution.

One of the most fundamental problems in the field of hypothesis testing is the identity testing problem: whether samples from some unknown distribution $\mathcal{G}$ are actually from some explicit distribution $\mathcal{D}$. It is known that when the distribution $\mathcal{D}$ has support $[N]$, the optimal sample complexity for the identity testing problem is roughly $O(\sqrt{N})$. However, many distributions of interest, including those which can be sampled efficiently, have exponential support size, and therefore the optimal identity tester also requires exponential samples. In this paper, we bypass this lower bound by considering restricted settings. The above $O(\sqrt{N})$ sample complexity identity tester is constructed so that it is not fooled by any (even inefficiently-sampled) distributions. However, in most applications, the distributions under consideration are efficiently samplable, and therefore it is enough to consider only identity testers that are not fooled by efficiently-sampled distributions. In this setting we can hope to construct efficient identity testers. We investigate relations between efficient verification of classical/quantum distributions with classical/quantum cryptography, showing the following results: \begin{itemize} \item Classically efficiently samplable distributions are verifiable if and only if one-way functions do not exist. \item Quantumly efficiently samplable distributions are verifiable by $\mathbf{P}^\mathbf{PP}$ with a polynomial number of samples. \item Sampling-based quantum advantage can be verified quantumly (with a polynomial number of samples) if one-way puzzles do not exist. \item If QEFID pairs exist, then some quantumly efficiently samplable distributions are not verifiable. \end{itemize}

The security of block ciphers such as AES-128, AES-192, and AES-256 relies on the assumption that their ciphertext outputs are computationally indistinguishable from random permutations. While distinguishers have been proposed for reduced-round variants or under non-standard models such as known-key or chosen-key settings, no effective distinguisher has been demonstrated for the full-round AES ciphers in the standard secret-key model. This work introduces FESLA (Feature Enhanced Statistical Learning Attack), a hybrid statistical learning framework that integrates outputs from a suite of classical statistical tests with machine learning and deep learning classifiers to construct ciphertext-only distinguishers for AES-128, AES-192, and AES-256. In contrast to existing approaches based on handcrafted or bitwise features, FESLA aggregates intermediate statistical metrics as features, enabling the capture of persistent structural biases in ciphertext distributions. Experimental evaluation across multiple datasets demonstrates consistent 100% classification accuracy using Support Vector Machines, Random Forests, Multi-Layer Perceptron, Logistic Regression, and Naïve Bayes classifiers. Generalization and robustness are confirmed through k-fold cross-validation, including on previously unseen ciphertext samples. These results establish the first ciphertext-only distinguishers for full-round AES-128, AES-192, and AES-256 under the secret-key model, and underscore the potential of machine learning–augmented cryptanalysis based on principled statistical feature engineering.

Organizations increasingly need to collaborate by performing a computation on their combined dataset, while keeping their data hidden from each other. Certain kinds of collaboration, such as collaborative data analytics and AI, require a level of performance beyond what current cryptographic techniques for distributed trust can provide. This is because the organizations run software in different trust domains, which can require them to communicate over WANs or the public Internet. In this paper, we explore how to instead run such applications using fast datacenter-type LANs. We show that, by carefully redesigning distributed trust frameworks for LANs, we can achieve up to order-of-magnitude better performance than naïvely using a LAN. Then, we develop deployment models for Distributed But Proximate Trust (DBPT) that allow parties to use a LAN while remaining physically and logically distinct. These developments make secure collaborative data analytics and AI significantly more practical and set new research directions for developing systems and cryptographic theory for high-performance distributed trust.

Non-interactive publicly verifiable secret sharing (PVSS) schemes enable the decentralized (re-)sharing of secrets in adversarial environments, allowing anyone to verify the correctness of distributed shares. Such schemes are essential for large-scale decentralized applications, including committee-based systems that require both transparency and robustness. However, existing PVSS schemes rely on group-based cryptography, making them vulnerable to quantum attacks and limiting their suitability for post-quantum applications. In this work, we propose the first practical, fully lattice-based, non-interactive PVSS scheme, grounded on standard lattice assumptions for post-quantum security. At the heart of our design lies a generic framework that transforms vector commitments and linear encryption schemes into practical PVSS protocols. We enhance vector commitments by incorporating proof of smallness, ensuring that encrypted shares are both verifiable and privacy-preserving. Our construction introduces two tailored lattice-based encryption schemes, each supporting efficient proofs of decryption correctness. This framework provides strong verifiability guarantees while maintaining low proof sizes and computational efficiency.

As a case study in cryptographic binding, we present a formal-methods analysis of the cryptographic channel binding mechanisms in the Fast IDentity Online (FIDO) Universal Authentication Framework (UAF) authentication protocol, which seeks to reduce the use of traditional passwords in favor of authentication devices. First, we show that UAF's channel bindings fail to mitigate protocol interaction by a Dolev-Yao adversary, enabling the adversary to transfer the server's authentication challenge to alternate sessions of the protocol. As a result, in some contexts, the adversary can masquerade as a client and establish an authenticated session with a server (e.g., possibly a bank server). Second, we implement a proof-of-concept man-in-the-middle attack against eBay's open source FIDO UAF implementation. Third, we propose and formally verify improvements to UAF. The weakness we analyze is similar to the vulnerability discovered in the Needham-Schroeder protocol over 25 years ago. That this vulnerability appears in the FIDO UAF standard highlights the strong need for protocol designers to bind messages properly and to analyze their designs with formal-methods tools. To our knowledge, we are first to carry out a formal-methods analysis of channel binding in UAF and first to exhibit details of an attack on UAF that exploits the weaknesses of UAF's channel binding. Our case study illustrates the importance of cryptographically binding context to protocol messages to prevent an adversary from misusing messages out of context.