While the round function of the AEGIS authenticated encryption algorithms is highly parallelizable, their mode of operation is not. We introduce two new modes to overcome that limitation: AEGIS-128X and AEGIS-256X, that require minimal changes to existing implementations and retain the security properties of AEGIS-128L and AEGIS-256.

We provide two improvements to Regev's quantum factoring algorithm (Journal of the ACM 2025), addressing its space efficiency and its noise-tolerance. Our first contribution is to improve the quantum space efficiency of Regev's algorithm while keeping the circuit size the same. Our main result constructs a quantum factoring circuit using $O(n \log n)$ qubits and $O(n^{3/2} \log n)$ gates. We achieve the best of Shor and Regev (upto a logarithmic factor in the space complexity): on the one hand, Regev's circuit requires $O(n^{3/2})$ qubits and $O(n^{3/2} \log n)$ gates, while Shor's circuit requires $O(n^2 \log n)$ gates but only $O(n \log n)$ qubits. As with Regev, to factor an $n$-bit integer $N$, we run our circuit independently $O(\sqrt{n})$ times and apply Regev's classical postprocessing procedure. Our optimization is achieved by implementing efficient and reversible exponentiation with Fibonacci numbers in the exponent, rather than the usual powers of 2, adapting work by Kaliski (arXiv:1711.02491) from the classical reversible setting to the quantum setting. This technique also allows us to perform quantum modular exponentiation that is efficient in both space and size without requiring significant precomputation, a result that may be useful for other quantum algorithms. A key ingredient of our exponentiation implementation is an efficient circuit for a function resembling \emph{in-place} quantum-quantum modular multiplication. This implementation works with only black-box access to any quantum circuit for \emph{out-of-place} modular multiplication, which we believe is yet another result of potentially broader interest. Our second contribution is to show that Regev's classical postprocessing procedure can be modified to tolerate a constant fraction of the quantum circuit runs being corrupted by errors. In contrast, Regev's analysis of his classical postprocessing procedure requires all $O(\sqrt{n})$ runs to be successful. In a nutshell, we achieve this using lattice reduction techniques to detect and filter out corrupt samples.

Reverse firewalls (RFs), introduced by Mironov and Stephens Davidowitz at Eurocrypt 2015, provide a defence mechanism for cryptographic protocols against subversion attacks. In a subversion setting, an adversary compromises the machines of honest parties, enabling the leakage of their secrets through the protocol transcript. Previous research in this area has established robust guarantees, including resistance against data exfiltration for an RF. In this work, we present a new perspective focused on the implementation specifics of RFs. The inherently untrusted nature of RFs exposes their real-world implementations to the risk of Trojan insertion — an especially pressing issue in today’s outsourced supply chain ecosystem. We argue how Trojan-affected RF implementations can compromise their core exfiltration resistance property, leading to a complete breakdown of the RF’s security guarantees. Building on this perspective, we propose an enhanced definition for ``Trojan-resilient Reverse Firewalls'' (Tr-RF), incorporating an additional Trojan resilience property. We then present concrete instantiations of Tr-RFs for Coin Tossing (CT) and Oblivious Transfer (OT) protocols, utilizing techniques from Private Circuit III (CCS'16) to convert legacy RFs into Tr-RFs. We also give simulation-based proofs to claim the enhanced security guarantees of our Tr-RF instantiations. Additionally, we offer concrete implementations of our Tr-RF based CT and OT protocols utilizing the Open-Portable Trusted Execution Environment (OP-TEE). Through OP-TEE, we practically realize assumptions made in Private Circuit III that are critical to ensuring Tr-RF security, bridging the gap between theoretical models and real-world applications. To the best of our knowledge, this provides the first practical implementation of reverse firewalls for any cryptographic functionality. Our work emphasizes the importance of evaluating protocol specifications within implementation-specific contexts.

Federated Learning (FL) allows clients to engage in learning without revealing their raw data. However, traditional FL focuses on developing a single global model for all clients, limiting their ability to have personalized models tailored to their specific needs. Personalized FL (PFL) enables clients to obtain their customized models, either with or without a central party. Current PFL research includes mechanisms to detect poisoning attacks, in which a couple of malicious nodes try to manipulate training convergence by submitting misleading data. However, these detection approaches often overlook privacy concerns, as they require clients to share their models with all other clients. This paper extends BALANCE, a personalized poisoning detection mechanism based on client models and their expectations. Our method enhances both security and privacy by ensuring clients are not required to share their model data with other clients. By leveraging server-assisted PFL and Fully Homomorphic Encryption (FHE), we enable a central party to identify unpoisoned clients from the perspective of individual clients and train personalized models securely. Additionally, we introduce an efficient personalized client selection algorithm that prevents redundant checks and ensures the inheritance of unpoisoned clients.

Authenticity-oriented (previously named as privacy-free) garbling schemes of Frederiksen et al. Eurocrypt ’15 are designed to satisfy only the authenticity criterion of Bellare et al. ACM CCS ’12, and to be more efficient compared to full-fledged garbling schemes. In this work, we improve the state-of-the-art authenticity-oriented version of half gates (HG) garbling of Zahur et al. Crypto ’15 by allowing it to be bandwidth-free if any of the input wires of an AND gate is freely settable by the garbler. Our full solution AuthOr then successfully combines the ideas from information-theoretical garbling of Kondi and Patra Crypto ’17 and the HG garbling-based scheme that we obtained. AuthOr has a lower communication cost (i.e. garbled circuit or GC size) than HG garbling without any further security assumption. Theoretically, AuthOr’s GC size reduction over HG garbling lies in the range between 0 to 100%, and the exact improvement depends on the circuit structure. We have implemented our scheme and conducted tests on various circuits that are constructed by independent researchers. Our experimental results show that in practice, the GC size gain may be up to roughly 98%.

A distributed OPRF enables a client to evaluate a pseudorandom function on a client-chosen input using a distributed key shared among multiple servers, ensuring that the servers learn nothing about the input or output, while the client learns nothing about the key. We present a post-quantum OPRF suitable for a distributed server setting, requiring only two rounds of communication between the client and servers, with server-to-server communication limited to a pre-computation phase. Our approach leverages the Legendre PRF, computed through a single MPC multiplication and opening during the online phase. We introduce a novel MPC technique that achieves multiplication and opening in one round using replicated secret sharing (RSS) in a malicious adversarial model. This allows for the quantum-secure, verifiable evaluation of the Legendre OPRF against malicious adversaries under a threshold assumption, without requiring inter-server communication. Beyond the Legendre PRF, this method is also of interest for general MPC operations. To our knowledge, our distributed OPRF (dOPRF) is the first post-quantum construction with these properties. We compare our approach to state-of-the-art MPC solutions and provide an implementation of our proposed dOPRF, benchmarking it against existing OPRF constructions. In practical settings, our results demonstrate superior efficiency.

We propose BLASter, a proof of concept LLL implementation that demonstrates the practicality of multiple theoretical improvements. The implementation uses the segmentation strategy from Neumaier–Stehlé (ISSAC 2016), parallelism and Seysen's reduction that was proposed by Kirchner–Espitau–Fouque (CRYPTO 2021) and implemented in OptLLL, and the BLAS library for linear algebra operations. It consists of only 1000 significant lines of C++ and Python code, and is made publicly available. For q-ary lattices that fplll can handle without multiprecision (dimension <180), BLASter is considerably faster than fplll, OptLLL and Ryan–Heninger's flatter (CRYPTO 2023), without degrading output reduction quality. Thanks to Seysen's reduction it can further handle larger dimension without resorting to multiprecision, making it more than 10x faster than flatter and OptLLL, and 100x faster than fplll in dimensions 256 to 1024. It further includes segmented BKZ and segmented deep-LLL variants. The latter provides bases as good as BKZ-15 and has a runtime that is only a couple of times more than our LLL baseline. This remains a proof of concept: the effective use of higher precision — which is needed to handle \(\textit{all}\) lattices — has further obstacles and is left for future work. Still, this work contains many lessons learned, and is meant to motivate and guide the development of a robust and modern lattice reduction library, which shall be much faster than fplll.

At CANS 2024, Zbudila et al. presented MaSTer, a maliciously secure multi-party computation protocol for truncation. It allows adversaries to manipulate outputs with a bounded additive error while avoiding detection with a certain probability. In this work, we analyse the broader implications of adversarial exploitation in probabilistic truncation protocols, specifically in relation to MaSTer. We propose three attack strategies aimed at inducing misclassification in deep neural network (DNN) inference. Our empirical evaluation across multiple datasets demonstrates that while adversarial influence remains negligible under realistic constraints, certain configurations and network architectures exhibit increased vulnerability. By improving the understanding of the risks associated with probabilistic truncation protocols in privacy-preserving machine learning, our work demonstrates that the MaSTer protocol is robust in realistic settings.

Threshold public-key encryption securely distributes private key shares among multiple participants, requiring a minimum number of them to decrypt messages. We introduce a quantum-resistant threshold public-key encryption scheme based on the code-based Niederreiter cryptosystem that achieves security against chosen ciphertext attacks. A previous attempt was made recently by Takahashi, Hashimoto, and Ogata (published at DCC in 2023) but we show that it contains a critical security flaw that allow adversaries to exploit malformed ciphertexts to gain information about the secret key. In this work, we formalize a generic conversion enhancing security of (classical) public-key encryption from one-wayness against passive attacks to indistinguishability against chosen-ciphertext attacks. The conversion uses a non-interactive zero-knowledge argument with strong security properties to ensure ciphertext well-formedness. We then provide an instantiation for Niederreiter encryption based on recent techniques introduced in the "MPC-in-the-head" paradigm. The publicly verifiable validity of ciphertexts makes this scheme suitable for threshold public-key encryption and prevents an attack similar to the one on Takahashi-Hashimoto-Ogata scheme. To improve the multi-party computation protocol for decryption (involving secure computations on polynomials), we introduce a field-switching technique that allows to significantly reduce the shared secret key size and computational overhead.

We present conceptually simple constructions of verifiable random functions (VRF) that fulfill strong notions of unbiasability recently introduced by Giunta and Stewart [EC:GS24]. VRFs with such strong properties were previously only known in the random oracle model or from the decisional Diffie–Hellman assumption with preprocessing. In contrast, our constructions are based on generic assumptions and are thus the first to be plausibly post-quantum secure. Moreover, our constructions fulfill several additional properties such as: • If the underlying VRF is aggregate, key-homomorphic or computable in \(\mathsf{NC}^1\), then so is our VRF. • For any verification key, the VRF output has almost the same min-entropy as the VRF input. Lastly, we outline a path towards a lattice-based VRF (without setup).

Distributed Point Function (DPF) provides a way for a dealer to split a point function $f_{\alpha, \beta}$ into multiple succinctly described function-shares, where the function $f_{\alpha, \beta}$ for a special input $\alpha$, returns a special output value $\beta$, and returns a fixed value $0$ otherwise. As the security requirement, any strict subset of the function-shares reveals nothing about the function $f_{\alpha,\beta}$. However, each function-share can be individually evaluated on the common input $x$, and these evaluation results can then be merged together to reconstruct the value $f_{\alpha, \beta}(x)$. Recently, Servan-Schreiber et al. (S&P 2023) investigate the access control problem for DPF; namely, the DPF evaluators can ensure that the DPF dealer is authorized to share the given function with privacy assurance. In this work, we revisit this problem, introducing a new notion called DPF with constraints; meanwhile, we identify that there exists a subtle flaw in their privacy definition as well as a soundness issue in one of their proposed schemes due to the lack of validation of the special output value $\beta$. Next, we show how to reduce both the storage size of the constraint representation and the server's computational overhead from $O(N)$ to $O(\log N)$, where $N$ is the number of authorized function sets. In addition, we show how to achieve fine-grained private access control, that is, the wildcard-style constraint for the choice of the special output $\beta$. Our benchmarks show that the amortized running time of our logarithmic storage scheme is $2\times$ - $3\times$ faster than the state-of-the-art when $N=2^{15}$. Furthermore, we provide the first impossibility and feasibility results of the DPF with constraints where the evaluators do not need to communicate with each other.

A certified-input mixnet introduced by Hébant et al. (PKC '20) employs homomorphically signed ciphertexts to reduce the complexity of shuffling arguments. However, the state-of-the-art construction relies on heavy Groth-Sahai proofs for key homormophism, and only achieves honest-user security, limiting broader applicability. This work proposes a novel certified-input mixnet achieving stronger security guarantees, alongside better efficiency. This is achieved by introducing a tailored signature scheme, two-party mercurial signatures on randomizable ciphertexts, that allows users and an authority to jointly sign ciphertexts supporting key, ciphertext, and signature randomization without compromising integrity and privacy. We compare our approach to previous works that employ structured ciphertexts, implement our protocols, and provide performance benchmarks. Our results show that verifying the mixing process for 50,000 ciphertexts takes just 135 seconds on a commodity laptop using ten mixers, underscoring the practicality and efficiency of our approach.

Generic Secure Multiparty Computation (Generic MPC) recently received much attraction in the blockchain realm as it allows mutually distrustful parties to jointly compute a global function using their private inputs while keeping them private; and more so; the expression of the function can be done in a programmable manner (hence `generic'); as opposed to the first rising star cryptographic technique Zero-Knowledge Proof (ZKP) which only allows computation on private input of a single party (via the `commit-and-prove' approach). While ZKP, by nature, allows public verifiability, Generic MPC is not so: Generic MPC mostly focuses on Malicious Security in which the computing result is verifiable only among the computing parties. Yet, in the blockchain realm, public verifiability is important, as the consensus protocol is not just among the computing parties but also external servers. A few works were done to bridge this gap (albeit not in the blockchain realm), i.e., Public Auditable MPC. Public Audtitability is a stronger property than Public Verifiability: the first one certifies the computation done in the MPC, while the latter certifies only the relation between the outputs and the inputs. However, they are non-constant round protocols and only for Secret-Sharing-based MPC, i.e., round complexity scales linearly with the circuit multiplicative depth, while round latency is an important cost metric in the blockchain domain. We address this problem by providing a Public Auditable Garbled Circuit protocol that is maliciously secure, publicly auditable, and constant-round. Our protocol is efficient, with only minimal overhead in terms of round, communication, and public transcript size.

Two-party computation has been an active area of research since Yao's breakthrough results on garbled circuits. We present secret key somewhat additive homomorphic schemes where the client has perfect privacy (server can be computationally unbounded). Our basic scheme is somewhat additive homomorphic and we extend it to support multiplication. The server handles circuit multiplication gates by returning the multiplicands to the client which updates the decryption key so that the original ciphertext vector includes the encrypted multiplication gate outputs. We give a 2-party computation (2PC) protocol that also incorporates server inputs where the client has perfect privacy. Server privacy holds against a computationally bounded adversary since it de- pends on the hardness of the subset sum problem. The 2PC protocol maintains circuit privacy except for leaking the number of multiplication gates to the client. Scaling the 2PC protocol via separate encryption parameters for smaller subcircuits allows the ciphertext size to remain constant as circuit size grows.

Differential Fault Attacks (DFAs) have recently emerged as a significant threat against stream ciphers specifically designed for Hybrid Homomorphic Encryption (HHE). In this work, we propose DFAs on the $\textsf{FRAST}$ cipher, which is a cipher specifically tailored for Torus-based Fully Homomorphic Encryption (TFHE). The round function of $\textsf{FRAST}$ employs random S-boxes to minimize the number of rounds, and can be efficiently evaluated in TFHE. With our specific key recovery strategy, we can mount the DFA with a few faults. Under the assumption of precise fault injection, our DFA can recover the key within one second using just 4 or 6 faults. When discarding the assumption and considering a more practical fault model, we can still achieve key recovery in a few minutes without increasing the number of faults. To the best of our knowledge, this is the first third-party cryptanalysis on $\textsf{FRAST}$. We also explored countermeasures to protect $\textsf{FRAST}$. Our analysis revealed that negacyclic S-boxes, a key component of TFHE-friendly ciphers, are unsuitable for incorporating linear structures to resist DFA. Consequently, we recommend removing the negacyclic restriction in the penultimate round of FRAST and introducing non-zero linear structures into the S-boxes of the last two rounds. We believe that our work will provide valuable insights for the design of TFHE-friendly ciphers.

Bilinear pairings constitute a cornerstone of public-key cryptography, where advancements in Tate pairings and their efficient variants have emerged as a critical research domain within cryptographic science. Currently, the computation of pairings can be effectively implemented through three distinct algorithmic approaches: Miller’s algorithm, the elliptic net algorithm (as developed by Stange), and cubical-based algorithms (as proposed by Damien Robert). Biextensions are the geometric object underlying the arithmetic of pairings, and all three approaches can be seen as a different way to represent biextension elements. In this paper, we revisit the biextension geometric point of view for pairing computation and investigate in more detail the cubical representation for pairing-based cryptography. Utilizing the twisting isomorphism, we derive explicit formulas and algorithmic frameworks for the ate pairing and optimal ate pairing computations. Additionally, we present detailed formulas and introduce an optimized shared cubical ladder algorithm for super-optimal ate pairings. Through concrete computational analyses, we compare the performance of our cubical-based methods with the Miller's algorithm on various well-known families of pairing-friendly elliptic curves. Our results demonstrate that the cubical-based algorithm outperforms the Miller's algorithm by bits in certain specific situations, establishing its potential as an alternative for pairing computation.

Homomorphic Encryption (HE) allows computations on encrypted data without decryption. It can be used where the users’ information are to be processed by an untrustful server, and has been a popular choice in privacy-preserving applica- tions. However, in order to obtain meaningful results, we have to assume an honest-but-curious server, i.e., it will faithfully follow what was asked to do. If the server is malicious, there is no guarantee that the computed result is correct. The notion of verifiable HE (vHE) is introduced to detect malicious server’s behaviors, but current vHE schemes are either more than four orders of magnitude slower than the underlying HE operations (Atapoor et. al, CIC 2024) or fast but incompatible with server- side private inputs (Chatel et. al, CCS 2024). In this work, we propose a vHE framework ZHE: effi- cient Zero-Knowledge Proofs (ZKPs) that prove the correct execution of HE evaluations while protecting the server’s private inputs. More precisely, we first design two new highly- efficient ZKPs for modulo operations and (Inverse) Number Theoretic Transforms (NTTs), two of the basic operations of HE evaluations. Then we build a customized ZKP for HE evaluations, which is scalable, enjoys a fast prover time and has a non-interactive online phase. Our ZKP is applicable to all Ring-LWE based HE schemes, such as BGV and CKKS. Finally, we implement our protocols for both BGV and CKKS and conduct extensive experiments on various HE workloads. Compared to the state-of-the-art works, both of our prover time and verifier time are improved; especially, our prover cost is only roughly 27-36× more expensive than the underlying HE operations, this is two to three orders of magnitude cheaper than state-of-the-arts.

We study the problem of how to find the inverse of shift invariant (SI) transformations proposed in Daemen's thesis. In particular, two of them have been used in practice: $y_i=x_i\oplus \overline{x_{i+1}}x_{i+2}$ and $y_i=x_i\oplus \overline{x_{i+1}}x_{i+2}x_{i+3}$. The first one is the well-known $\chi$ transformation used in \textsf{SHA-3}, \textsf{Subterranean 2.0} and \textsf{Rasta}, while the second one is used in a recently proposed ZK-friendly hash function called Monolith. While the concrete formula of the inverse of $\chi$ of arbitrary size has been given and proved by Liu et al. at JoC 2022, it remains unknown how to deduce such a formula and how to systematically study other SI transformations. In this work, we aim to provide a general method and flow to find the inverse of SI transformations, though it is still limited to some specific types and it may not work for all such transformations. However, such a general method does shed new insight on how to find their inverse, as we can apply this method to several different SI transformations, including the one used in Monolith. We expect that this method can be further generalized and applied to more SI transformations.

Lattices are the basis of most NIST-recommended post-quantum cryptography (PQC) schemes, required to thwart the threat posed by the eventual construction of large-scale quantum computers. At the same time, lattices enable more advanced cryptographic constructions, such as fully homomorphic encryption (FHE), which is increasingly used for privacy-preserving applications like machine learning. This work delves into the efficiency and trade-off assessment of polynomial multiplication algorithms and their applications to PQC, FHE, and other schemes. Such algorithms are at the core of lattice-based cryptography and may become a critical bottleneck when deploying PQC- and FHE-based solutions on resource-constrained devices. We propose a formal analysis of so-called incompleteness in the Number Theoretic Transform (NTT). Although this concept is not new, our systematization shows how to optimize polynomial multiplication in quotient rings, considering factors such as the degree of incompleteness, the associated prime moduli, constraints of the target platform, and target security level. Besides efficiency, we formally show that the systematized family of incomplete NTT variants supports a larger set of prime moduli. This property enables new trade-offs for algorithms like the FIPS-approved module-lattice-based key encapsulation mechanism (ML-KEM) and faster amortized bootstrapping in FHE schemes. Our results include shorter ciphertexts in ML-KEM with only a modest hit in performance and a 6-42% performance boost in the NTT computation of a state-of-the-art FHE solution.

In recent years, online anonymity has become increasingly important but is under threat due to the challenges of moderating anonymous spaces. A promising cryptographic solution, known as anonymous blocklisting, allows users to post anonymously while still enabling moderation. Moderation via anonymous blocklisting roughly works by requiring that when users post a message they attach a cryptographic proof that they did not author any posts on a “blocklist”. Existing anonymous blocklisting schemes are unfortunately still far from achieving practical performance for large blocklists. This is essentially due to all prior works requiring a user to (cryptographically) reprocess blocklist entries many times. Relatedly, prior works have relatively high verification times and proof sizes. In this work, we introduce ALPACA, the first anonymous blocklisting system with the property that a user only needs to do a constant amount of work per blocklist entry. Thus, our scheme has asymptotically optimal performance. Our scheme is also the first to have verification times and proof sizes that are independent of the number of blocklist entries. Our key technique is a new variant of incrementally verifiable computation (IVC), designed to ensure anonymity. Along the way, we introduce new definitions to formally establish security. On a mid-range laptop, ALPACA’s proof generation time is always 6.15 seconds and proof size is 25.6KBs. On a server, the verification time is always 400ms.

The Estonian i-voting experience is probably the richest to analyze; a country that is considered a pioneer in digitizing both the government and private sector since 2001, and hence digital voting in 2005, yet there are still some complaints submitted, critics and remarks to consider about the IVXV system. In this paper, we introduce a Systemization of Knowledge of the Estonian IVXV i-voting system and propose some added security enhancements. The presented SoK includes applications implemented by election observers in 2023 & 2024 elections, which, to our knowledge, has never been mentioned and/or analyzed in the academia before. The paper also updates the general knowledge about an extra right given to auditors (but not observers) in the June 2024 European election, recent improvements, and recent complaints. Finally, we discuss the current system status in 2024 EP elections, propose our own suggestions to some remaining vulnerabilities, then raise the inevitable question of the approaching quantum threat.

Zero-Knowledge Proof (ZKP) is a cornerstone technology in privacy-preserving computing, addressing critical challenges in domains such as finance and healthcare by ensuring data confidentiality during computation. However, the high computational overhead of ZKP, particularly in proof generation and verification, limits its scalability and usability in real-world applications. Existing efforts to accelerate ZKP primarily focus on specific components, such as polynomial commitment schemes or elliptic curve operations, but fail to deliver an integrated, flexible, and efficient end-to-end solution that includes witness generation. In this work, we present ZKPoG, a GPU-based ZKP acceleration platform that achieves full end-to-end optimization. ZKPoG addresses three key challenges: (1) designing a witness-generation-incorporated flow for Plonkish circuits, enabling seamless integration of frontend and backend with GPU acceleration; (2) optimizing memory usage to accommodate large-scale circuits on affordable GPUs with limited memory; and (3) introducing an automated compiler for custom gates, simplifying adaptation to diverse applications. Experimental results on an NVIDIA RTX 4090 GPU show on average $22.8\times$ end-to-end acceleration compared to state-of-the-art CPU implementations and on average $12.7\times$ speedup over existing GPU-based approaches.

Secret sharing is a fundamental primitive in cryptography, and it can be achieved even with perfect security. However, the distribution of shares requires computational assumptions, which can compromise the overall security of the protocol. While traditional Quantum Key Distribution (QKD) can maintain security, its widespread deployment in general networks would incur prohibitive costs. In this work, we present a quantum protocol for distributing additive secret sharing of 0, which we prove to be composably secure within the Abstract Cryptography framework. Moreover, our protocol targets the Qline, a recently proposed quantum network architecture designed to simplify and reduce the cost of quantum communication. Once the shares are distributed, they can be used to securely perform a wide range of cryptographic tasks, including standard additive secret sharing, anonymous veto, and symmetric key establishment.

Recent years have seen great improvements in zero-knowledge proofs (ZKPs). Among them, zero-knowledge SNARKs are notable for their compact and efficiently-verifiable proofs, but suffer from high prover costs. Wu et al. (Usenix Security 2018) proposed to distribute the proving task across multiple machines, and achieved significant improvements in proving time. However, existing distributed ZKP systems still have quasi-linear prover cost, and may incur a communication cost that is linear in circuit size. In this paper, we introduce $\mathsf{HyperPianist}$. Inspired by the state-of-the-art distributed ZKP system Pianist (Liu et al., S&P 2024) and the multivariate proof system HyperPlonk (Chen et al., EUROCRYPT 2023), we design a distributed multivariate polynomial interactive oracle proof (PIOP) system with a linear-time prover cost and logarithmic communication cost. Unlike Pianist, $\mathsf{HyperPianist}$ incurs no extra overhead in prover time or communication when applied to general (non-data-parallel) circuits. To instantiate the PIOP system, we adapt two additively-homomorphic multivariate polynomial commitment schemes, multivariate KZG (Papamanthou et al., TCC 2013) and Dory (Lee et al., TCC 2021), into the distributed setting, and get $\mathsf{HyperPianist^K}$ and $\mathsf{HyperPianist^D}$ respectively. Both systems have linear prover complexity and logarithmic communication cost; furthermore, $\mathsf{HyperPianist^D}$ requires no trusted setup. We also propose $\mathsf{HyperPianist+}$, incorporating an optimized lookup argument based on Lasso (Setty et al., EUROCRYPT 2024) with lower prover cost. Experiments demonstrate $\mathsf{HyperPianist^K}$ and $\mathsf{HyperPianist^D}$ achieve speedups of $63.1\times$ and $40.2\times$ over HyperPlonk with 32 distributed machines. Compared to Pianist, $\mathsf{HyperPianist^K}$ can be $2.9\times$ and $4.6\times$ as fast and $\mathsf{HyperPianist^D}$ can be $2.4\times$ and $3.8\times$ as fast, on vanilla gates and custom gates respectively. With layered circuits, $\mathsf{HyperPianist^K}$ is up to $5.9\times$ as fast on custom gates, and $\mathsf{HyperPianist^D}$ achieves a $4.7\times$ speedup.

As privacy concerns have arisen in machine learning, privacy-preserving machine learning (PPML) has received significant attention. Fully homomorphic encryption (FHE) and secure multi-party computation (MPC) are representative building blocks for PPML. However, in PPML protocols based on FHE and MPC, interaction between the client (who provides encrypted input data) and the evaluator (who performs the computation) is essential to obtain the final result in plaintext. Functional encryption (FE) is a promising candidate to remove this constraint, but existing FE-based PPML protocols are restricted to evaluating only simple ML models, such as one-layer neural networks, or they support partially encrypted PPML, which makes them vulnerable to information leakage beyond the inference results. In this paper, we propose a fully encrypted FE-based PPML protocol, which supports the evaluation of arbitrary functions over encrypted data with no information leakage during computation, for the first time. To achieve this, {we introduce a new functional encryption scheme for quadratic polynomials, in which the encryption algorithm is realized as a linear function with respect to a message. This structural property allows for the composition of the encryption algorithm with arbitrary quadratic functions, thereby enabling multiple compositions of quadratic polynomials to compute arbitrary complex functions in an encrypted manner. Our FE-based PPML protocol is secure in the malicious model, which means that an adversary cannot obtain any information about the input data even though they intentionally deviate from the protocol. We then show how to use our protocol to build a fully encrypted 2-layer neural network model with quadratic activation functions and present experimental results.

We propose a new method for retrieving the algebraic structure of a generic alternant code given an arbitrary generator matrix, provided certain conditions are met. We then discuss how this challenges the security of the McEliece cryptosystem instantiated with this family of codes. The central object of our work is the quadratic hull related to a linear code, defined as the intersection of all quadrics passing through the columns of a given generator or parity-check matrix, where the columns are considered as points in the affine or projective space. The geometric properties of this object reveal important information about the internal algebraic structure of the code. This is particularly evident in the case of generalized Reed-Solomon codes, whose quadratic hull is deeply linked to a well-known algebraic variety called the rational normal curve. By utilizing the concept of Weil restriction of affine varieties, we demonstrate that the quadratic hull of a generic dual alternant code inherits many interesting features from the rational normal curve, on account of the fact that alternant codes are subfield-subcodes of generalized Reed-Solomon codes. If the rate of the generic alternant code is sufficiently high, this allows us to construct a polynomial-time algorithm for retrieving the underlying generalized Reed-Solomon code from which the alternant code is defined, which leads to an efficient key-recovery attack against the McEliece cryptosystem when instantiated with this class of codes. Finally, we discuss the generalization of this approach to Algebraic-Geometry codes and Goppa codes.

Mix networks (mixnets) offer robust anonymity even against adversaries monitoring all network links; however, they impose high latency on communications. To address this, recent research has explored strategic low-latency routing within mixnets. While these strategies appear to reduce latency, their impact on mixnet anonymity has not been carefully assessed, raising concerns about potential deanonymization of clients. Tackling this challenge, this paper first quantifies the anonymity loss associated with low-latency routing techniques in mixnets. Building on these insights, second, we introduce a novel low-latency routing method that maintains mixnet anonymity while achieving significant latency reductions compared to the state-of-the-art solution LARMix (NDSS, 2024). Our approach also ensures a more balanced load distribution among mixnet nodes. Moreover, under adversarial conditions where parts of the mixnet are compromised, our method does not confer significant advantages to the adversary, unlike LARMix. Thus, our proposal emerges as the optimal choice for low-latency routing in mixnets. Furthermore, we note that this version expands on both the analytical and experimental results of the previously published paper in NCA 2024, specifically through investigating the anonymity of Loopix-like mixnets.

A central advantage of deploying cryptosystems is that the security of large high-sensitive data sets can be reduced to the security of a very small key, i.e., a master key. The most popular way to manage the master key is to use $(t,n)-$threshold secret sharing schemes: a user splits and distributes her/his key among $n$ key servers, and can recover the key with the aid of any $t$ of them. However, it is vulnerable to device destruction: if all key servers and users' devices break down, the key will be permanently lost. We propose a Destruction-Resistant Key Management scheme, dubbed DRKM, which ensures the key availability even if destruction occurs. In DRKM, a user utilizes her/his $n^{*}$ personal identification factors (PIFs) to derive a cryptographic key but can retrieve the key using any $t^{*}$ of the $n^{*}$ PIFs. As most PIFs can be retrieved by the user per se without requiring stateful devices, destruction resistance is achieved. With the integration of a $(t,n)-$threshold secret sharing scheme, DRKM achieves portable key access by invoking any $t$ key servers before destruction occurs. We prove the DRKM's security, implement its prototype, and conduct a comprehensive performance evaluation to demonstrate its high efficiency.

We continue the study of blockcipher-based (tweakable) correlation robust hash functions, which are central building blocks of circuit garbling and oblivious-transfer extension schemes. Motivated by Roy (CRYPTO 2022), we first enhance the multi-user tweakable correlation robust notion of Guo et al. (CRYPTO 2020) with a {\it key leaking oracle} that tells the adversary whether a certain user key satisfies the adversarially-chosen predicate. We then investigate the state-of-the-art hash construction of Guo et al. with respect to our new security definition, providing security proof as well as matching attacks. As an application, we exhibit an OT extension protocol with non-trivial multi-user security.

The nonlinear filter model is an old and well understood approach to the design of secure stream ciphers. Extensive research over several decades has shown how to attack stream ciphers based on this model and has identified the security properties required of the Boolean function used as the filtering function to resist such attacks. This led to the problem of constructing Boolean functions which provide adequate security and at the same time are efficient to implement. Unfortunately, over the last two decades no good solutions to this problem appeared in the literature. The lack of good solutions has effectively led to nonlinear filter model becoming more or less obsolete. This is a big loss to the cryptographic design toolkit, since the great advantages of the nonlinear filter model are its simplicity, well understood security and the potential to provide low cost solutions for hardware oriented stream ciphers. In this paper we construct balanced functions on an odd number $n\geq 5$ of variables with the following provable properties: linear bias equal to $2^{-\lfloor n/2\rfloor -1}$, algebraic degree equal to $2^{\lfloor \log_2\lfloor n/2\rfloor \rfloor}$, algebraic immunity at least $\lceil (n-1)/4\rceil$, fast algebraic immunity at least $1+\lceil (n-1)/4\rceil $, and can be implemented using $O(n)$ NAND gates. The functions are obtained from a simple modification of the well known class of Maiorana-McFarland bent functions. By appropriately choosing $n$ and the length $L$ of the linear feedback shift register, we show that it is possible to obtain examples of stream ciphers which are $\kappa$-bit secure against known types of attacks for various values of $\kappa$. We provide concrete proposals for $\kappa=80,128,160,192,224$ and $256$. For the $80$-bit, $128$-bit, and the $256$-bit security levels, the circuits for the corresponding stream ciphers require about 1743.5, 2771.5, and 5607.5 NAND gates respectively. For the $80$-bit and the $128$-bit security levels, the gate count estimates compare quite well to the famous ciphers Trivium and Grain-128a respectively, while for the $256$-bit security level, we do not know of any other stream cipher design which has such a low gate count.

While masking is a widely used defense against passive side-channel attacks, its secure implementation in hardware continues to be a manual, complex, and error-prone process. This paper introduces INDIANA, a comprehensive security verification methodology for hardware masking. Our results include a hardware verification tool, enabling a complete analysis of simulation-based security in the glitch-extended probing model and intra-cycle estimations for leakage probabilities in the random probing model. Notably, INDIANA is the first framework to analyze arbitrary masked circuits in both models, even at the scale of full SPN cipher rounds (e.g., AES), while delivering exact verification results. To achieve accurate and comprehensive verification, we propose a partitionable probing distinguisher that allows for fast validation of probe tuples, surpassing current methods that rely on statistical independence. Furthermore, our approach naturally supports extensions to the random probing model by utilizing Fast Fourier-Hadamard Transformations (FHTs). Benchmark results show that INDIANA competes effectively with leading probing model verification tools, such as ironMask, maskVerif, and VERICA. INDIANA is also the first tool that is capable to provide intra-cycle estimations of random probing leakage probabilities for large-scalemasked circuits.

In lattice-based cryptography, many attacks are performed by finding a short enough vector on a specific lattice. However, it is possible that length is not the only restriction on the vector to be found. A typical example is SVP with infinity norm: since most SVP solving algorithms only aim to find short vector under Euclidean norm, the infinity norm is in fact another restriction on the vector. In the literature, such problems are usually solved by performing exhaustive search on a list of short vectors generated from lattice sieving. However, the sieving list might either be too large or too small to pass the additional restriction, which makes the solving algorithm inefficient in some cases. Our contribution in this work is as follows: (1) We formally define a new lattice hard problem called restricted SVP, and show that it can be used to generalize many lattice hard problems, including SVP with non-Euclidean norm and Kannan's embedding on approximate CVP. (2) We extend the dimension for free technique and the enumerate-then-slice technique into approximate SVP where the goal is to output a list of short vectors with a certain size. (3) We give the heuristic algorithm for solving restricted SVP, and design a hardness estimator for this algorithm, which can be used to estimate the concrete hardness of signature forgery in Dilithium and other lattice-based signatures. Using this estimator, we present a concrete security analysis for Dilithium against signature forgery under the gate-count model for the first time. Our estimation matches well with the security estimation from core-SVP model in the document of Dilithium, and we also combine our estimator with the rescaling technique to generate a tighter estimation.

A group signature scheme enables users of a group to anonymously sign messages on behalf of the group, while a designated authority can revoke anonymity when needed to ensure user accountability. Among group signature schemes, fully dynamic ones are particularly desirable as they allow new users to join and misbehaved existing users to be revoked without requiring system-wide updates. This paper introduces DGSP, a post-quantum fully dynamic group signature scheme that addresses key limitations of existing schemes like DGMT and SPHINX-in-the-Head (SITH). Leveraging the properties of ${\rm SPHINCS}^+$, DGSP achieves a superior balance between scalability and efficiency by (i) supporting up to $2^{60}$ users, (ii) requiring negligible setup time, and (iii) featuring efficient algorithms with short signatures of constant-size. Notably, while DGMT is limited to $2^{15}$ users, DGSP extends this to $2^{60}$ while keeping signatures compact—only 3.03 to 4.93 times larger than those of DGMT, yet just 0.021 to 0.004 times the size of SITH signatures. This makes DGSP a compelling solution for applications requiring both large-scale user support and signature efficiency in the post-quantum setting. Moreover, DGSP strengthens managerial accountability compared to DGMT by (i) enabling users to verify their certificates generated by the manager and (ii) ensuring public verifiability of the manager's signature attribution. Although SITH claims to support $2^{60}$ users, our analysis reveals that its opening algorithm is highly inefficient, making it impractical to handle such a large number of users. Our security analysis shows that DGSP achieves unforgeability, anonymity, and traceability in the standard model. We also provide a complete implementation of DGSP. Our experimental study exhibits that DGSP is superior over existing schemes in terms of efficiency and scalability.

It is a widely accepted standard practice to implement cryptographic software so that secret inputs do not influence the cycle count. Software following this paradigm is often referred to as "constant-time" software and typically involves following three rules: 1) never branch on a secret-dependent condition, 2) never access memory at a secret-dependent location, and 3) avoid variable-time arithmetic operations on secret data. The third rule requires knowledge about such variable-time arithmetic instructions, or vice versa, which operations are safe to use on secret inputs. For a long time, this knowledge was based on either documentation or microbenchmarks, but critically, there were never any guarantees for future microarchitectures. This changed with the introduction of the data-operand-independent-timing (DOIT) mode on Intel CPUs and, to some extent, the data-independent-timing (DIT) mode on Arm CPUs. Both Intel and Arm document a subset of their respective instruction sets that are intended to leak no information about their inputs through timing, even on future microarchitectures if the CPU is set to run in a dedicated DOIT (or DIT) mode. In this paper, we present a principled solution that leverages DOIT to enable cryptographic software that is future-proof constant-time, in the sense that it ensures that only instructions from the DOIT subset are used to operate on secret data, even during speculative execution after a mispredicted branch or function return location. For this solution, we build on top of existing security type systems in the Jasmin framework for high-assurance cryptography. We then use our solution to evaluate the extent to which existing cryptographic software built to be "constant-time" is already secure in this stricter paradigm implied by DOIT and what the performance impact is to move from constant-time to future-proof constant-time.

Traceable ring signatures enhance ring signatures by adding an accountability layer. Specifically, if a party signs two different messages within the protocol, their identity is revealed. Another desirable feature is $\textit{extendability}$. In particular, $\textit{extendable threshold}$ ring signatures (ETRS) allow to $\textit{non-interactively}$ update already finalized signatures by enlarging the ring or the set of signers. Combining traceability and extendability in a single scheme is unexplored and would offer a new tool for privacy-preserving voting schemes in scenarios where the voters are not known in advance. In this paper, we show how to reconcile both properties by introducing and constructing a new cryptographic primitive called Tetris. Notably, our Tetris construction simultaneously achieves strong anonymity and linear-size signatures, which is the main technical challenge in existing techniques. To solve this challenge, we develop a new approach to traceability that leads to several conceptual and technical contributions. Among those, we introduce and construct, based on Groth-Sahai proofs, $\textit{extendable}$ shuffle arguments that can be $\textit{non-interactively}$ updated by several provers.

Password Authenticated Key Exchange (PAKE) establishes secure communication channels using relatively short, often human memorable, passwords for authentication. The currently standardized PAKEs however rely on classical asymmetric (public key) cryptography. Thus, these classical PAKEs may become insecure, should the expected quantum threat become a reality. Despite the growing interest in realizing quantum-safe PAKEs, they did not receive much attention from the ongoing Post-Quantum Cryptography (PQC) integration efforts. Thus, there is a significant gap in awareness compared to PQC primitives subject to the official governmental and institutional standardization processes. In this work, we provide a comprehensive overview of the existing PQC PAKEs focusing on their design rationales, authentication methods and asymmetric key agreement primitives. Further, we classify PQC PAKEs w.r.t. their properties and security assurances. Finally, we address PAKE designs that are still unexplored in the PQC realm and discuss the possibility of their adaptation. Thus, we offer a detailed reference for future work on PQC PAKEs.

AES-GCM has been the status quo for efficient symmetric encryption for decades. As technology and cryptographic applications evolved over time, AES-GCM has posed some challenges to certain use-cases due to its default 96-bit nonce size, 128-bit block size, and lack of key commitment. Nonce-derived schemes are one way of addressing these challenges: Such schemes derive multiple keys from nonce values, then apply standard AES-GCM with the derived keys (and possibly another 96-bit nonce). The approach overcomes the nonce length and data limit issues since each derived key is only used to encrypt a few messages. By itself, the use of nonce-derived keys does not address key commitment, however. Some schemes chose to include a built-in key commitment mechanism, while others left it out of scope. In this work, we explore efficient key commitment methods that can be added to any nonce-derived scheme in a black-box manner. Our focus is on options that use the underlying block cipher and no other primitive, are efficient, and only use standard primitives which are FIPS-approved. For concreteness we focus here specifically on adding key commitment to XAES-256-GCM, a nonce-scheme originally proposed by Filippo Valsorda, but these methods can be adapted to any other nonce-derived scheme. We propose an efficient CMAC-based key commitment solution, and prove its security in the ideal-cipher model. We argue that adding this solution yields a FIPS-compliant mode, quantify the data and message length limits of this mode and compare this combination to other nonce-derived modes. We also benchmark our key committing XAES-256-GCM performance.

This work builds approximate proximity searchable encryption. Secure biometric databases are the primary application. Prior work (Kuzu, Islam, and Kantarcioglu, ICDE 2012) combines locality-sensitive hashes, or LSHs, (Indyk, STOC ’98), and oblivious multimaps. The multimap associates LSH outputs as keywords to biometrics as values. When the desired result set is of size at most one, we show a new preprocessing technique and system called ProxCode that inserts shares of a linear secret sharing into the map instead of the full biometric. Instead of choosing shares independently, shares are correlated so exactly one share is associated with each keyword/LSH output. As a result, one can rely on a map instead of a multimap. Secure maps are easier to construct with low leakage than multimaps. For many parameters, this approach reduces the required number of LSHs for a fixed accuracy. Our scheme yields the most improvement when combining a high accuracy requirement with a biometric with large underlying noise. Our approach builds on any secure map. We evaluate the scheme accuracy for both iris data and random data.

Side-channel analysis recovers a secret by exploiting the key-dependent characteristics of the leakages. Practical techniques, such as Distance-of-Means analysis (DoM), Kolmogorov-Smirnov analysis (KSA) and Cramér-von Mises analysis (CvMA), provide valuable insights about the secret from the indirect perspectives of statistical moment and cumulative distribution function (CDF) respectively, circumventing the direct and costly estimation of leakage probability densities and therefore enabling wider applicability in practice. Though both the perspectives are informative, their relationships in the context of side-channel analysis remain unclear. In other words, the fundamental questions of "which one is better?'' and ``why and under what circumstances?" leave as open problems. In this paper, we introduce the probability-probability (PP) plot in statistics as a common framework for explaining the mathematical foundations of CDF-based techniques, which facilitates an intuitive understanding of different variant strategies. Then, inspired by the growth pattern of the PP curve, we propose a novel distinguisher based on the famous Mann-Kendall test, where measurements are managed with ordinality and nominality. This goodness-of-fit test checks whether a key-dependent binary sequence originates from a random binomial distribution, by efficiently searching potential label clusters. Finally, we explore the symmetry and dual counterpart of CDF in mathematics, introducing the quantile-quantile (QQ) plot and develop an interesting technique based on the inverse cumulative distribution function (ICDF). We present a general discussion of its bridging role, regarding detail capture as well as signal-to-noise ratio (SNR). On this basis, we establish the relationships among moment-based, ICDF-based, and CDF-based techniques, which additionally allows for bounding the security level of the CDF-based techniques using well-established metrics that are originally proposed for evaluating the traditional moment-based family. Experiments across various settings validate our theoretical findings and demonstrate the effectiveness of the two proposed distinguishers.

This paper presents a novel single-trace side-channel attack on FALCON, a lattice-based post-quantum digital signature protocol recently approved for standardization by NIST. We target the discrete Gaussian sampling operation within FALCON’s key generation scheme and demonstrate that a single power trace is sufficient to mount a successful attack. Notably, negating the results of a 63-bit right-shift operation on 64-bit secret values leaks critical information about the assignment of ‘-1’ versus ‘0’ to intermediate coefficients during sampling. These leaks enable full recovery of the secret key. We demonstrate a ground-up approach to the attack on an ARM Cortex-M4 microcontroller executing both the reference and optimized implementations from FALCON’s NIST round 3 software package. We successfully recovered all of the secret polynomials in FALCON. We further quantify the attacker’s success rate using a univariate Gaussian template model, providing generalizable guarantees. Statistical analysis with over 500,000 tests reveals a per-coefficient success rate of 99.9999999478% and a full-key recovery rate of 99.99994654% for FALCON-512. We verify that this vulnerability is present in all implementations included in FALCON’s NIST submission package. This highlights the vulnerability of current software implementations to single-trace attacks and underscores the urgent need for single-trace- resilient software in embedded systems.

The hardness of Kolmogorov complexity is intricately connected to the existence of one-way functions and derandomization. An important and elegant notion is Levin's version of Kolmogorov complexity, \(\mathsf{Kt}\), and its decisional variant, \(\mathsf{MKtP}\). The question whether \(\mathsf{MKtP}\) can be computed in polynomial time is particularly interesting because it is not subject to known technical barriers such as algebrization or natural proofs that would explain the lack of a proof for \(\mathsf{MKtP} \not\in \mathsf{P}\). We take a major step towards proving \(\mathsf{MKtP} \not\in \mathsf{P}\) by developing a novel yet simple diagonalization technique to show unconditionally that \(\mathsf{MKtP} \not \in \mathsf{DTIME}[O(n)]\), i.e., no deterministic linear-time algorithm can solve \(\mathsf{MKtP}\) on every instance. This allows us to affirm a conjecture by Ren and Santhanam [STACS:RS22] about a non-halting variant of \(\mathsf{Kt}\) complexity. Additionally, we give conditional lower bounds for \(\mathsf{MKtP}\) that tolerate either more runtime or one-sided error. If the underlying computational model has a linear-time universal simulation, e.g.\ random-access machines, then we obtain a quadratic lower bound, i.e., \(\mathsf{MKtP} \not\in \mathsf{DTIME}[O(n^2)]\).

We construct a pairing-based polynomial commitment scheme for multilinear polynomials of size $n$ where constructing an opening proof requires $O(n)$ field operations, and $2n+O(\sqrt n)$ scalar multiplications. Moreover, the opening proof consists of a constant number of field elements. This is a significant improvement over previous works which would require either 1. $O(n\log n)$ field operations; or 2. $O(\log n)$ size opening proof. The main technical component is a new method of verifiably folding a witness via univariate polynomial division. As opposed to previous methods, the proof size and prover time remain constant *regardless of the folding factor*.

In this paper, we introduce techniques that transform existing stateful hash based signatures (HBS), such as LMS [MCF19] or XMSS [HBG+18], into efficient threshold and distributed signature schemes. Our scheme includes a trusted dealer, a set of trustees, and an untrusted aggregator. Signing requires only a little more work from each trustee than is required of a single signer, and requires two round trip messages between the aggregator and each trustee involved in the signature. All communications are done point-to-point; there is no broadcast channel required. Each trustee needs to maintain only a small amount of key material and state, however the aggregator must have access to a fairly large (hundreds of MiB up to a few GiB) common reference string. Our scheme produces standard LMS or XMSS signatures, indistinguishable from signatures created from a single signer, and so requires no change in verification software. Our scheme is provably secure assuming the security of the underlying stateful HBS and security of a PRF used to derive shares by the ntrustees.

Proof-carrying data (PCD) is a powerful cryptographic primitive for computational integrity in a distributed setting. State-of-the-art constructions of PCD are based on accumulation schemes (and, closely related, folding schemes). We present WARP, the first accumulation scheme with linear prover time and logarithmic verifier time. Our scheme is hash-based (secure in the random oracle model), plausibly post-quantum secure, and supports unbounded accumulation depth. We achieve our result by constructing an interactive oracle reduction of proximity that works with any linear code over a sufficiently large field. We take a novel approach by constructing a straightline extractor that relies on erasure correction, rather than error-tolerant decoding like prior extractors. Along the way, we introduce a variant of straightline round-by-round knowledge soundness that is compatible with our extraction strategy.

This work addresses the hintless single-server Private Information Retrieval (PIR) from the perspective of high-level protocol design and introduces PIRCOR and PIRCOR$^{*}$ that outperform the state-of-the-art PIRANA (Liu et. al., IEEE S&P 2024) and YPIR (Menon and Wu, USENIX Security 2024) in terms of the query size and the query generation time. In PIRCOR, we construct an efficient Rotation-based Expanded Binary Code (REBC) to expand $\alpha$ primary codewords into $\beta$ expanded codewords by the Rotation-Mutual-Multiplication operation. By leveraging the innovative REBC, PIRCOR reduces the query size for single-query PIR by a factor of $\mathcal{O}\left(N^{\frac{\delta-1}{\delta}}\right)$ compared to PIRANA, while also avoiding the $\mathcal{O}(N +\frac{|\mathrm{DB}|}{N})$ linear scaling inherent in YPIR ($N$, $\delta$ and $|\mathrm{DB}|$ are the (R)LWE secret dimension, the number of codewords with a Hamming weight of $1$ and the number of database elements). Based on PIRCOR, we further present PIRCOR$^{*}$ by additionally introducing the Rotation-self-Multiplication operation, which achieves a $\mathbf{50\%}$ reduction in rotation operations and a smaller query size when $\delta = 2$. Building upon PIRCOR and PIRCOR$^{*}$, we further propose their optimized variants, PIRCOR-op and PIRCOR$^{*}$-op, to further reduce the online response time. Similar to YPIR that leverage pre-processing, PIRCOR-op and PIRCOR$^{*}$-op allow all rotations and part of multiplications to be carried out in an offline stage before receiving the query. Additionally, we also design FHE-operator acceleration with leveled optimization and implementation optimization of ciphertext rotation. For 8 KB element retrieval in an 8 GB database, PIRCOR achieves a $\mathbf{10.7\times}$ query size reduction compared to PIRANA. When benchmarked against YPIR, the improvements are even more striking: PIRCOR reduces the query size by $\mathbf{26.8\times}$ and accelerates query generation by a staggering $\mathbf{6,080\times}$. Notably, the enhanced PIRCOR$^{*}$ achieves a $\mathbf{53.6\times}$ reduction in query size compared to YPIR, while improving query generation time by an impressive $\mathbf{12,160\times}$.

Differential meet-in-the-middle (MITM) cryptanalysis, introduced by Boura et al. at CRYPTO 2023, has been demonstrated to be an effective technique for analyzing the security of block ciphers. In this paper, we introduce an improved parallel partitioning technique, and incorporate it into a new framework with a flexible key recovery strategy. This framework is applicable to both SPN and Feistel ciphers. We apply the new framework to SIMON and Piccolo-128 for demonstration. In particular, we also develop an MILP-based tool for searching full attacks on Piccolo-128. For SIMON48/96, we propose the best attack, reaching 26 rounds against 25 rounds previously. For other versions of SIMON, we extend the best previous differential attacks by one or two rounds. In the case of Piccolo-128, while no current differential attacks show promising results, our differential MITM attack reaches 15 rounds, matching the same number of rounds of the best impossible differential attack.

We show that the data aggregation scheme [IEEE TDSC, 2023, 20(3), 2011-2024] is flawed, because the signer only signs a part of data, not the whole data. An adversary can replace the unsigned component to cheat the verifier. To frustrate this attack, all components of the target data should be concatenated together and then be hashed and signed, so as to ensure that the signature verification can prove the whole message integrity.

We study the structure of theta structure on products of elliptic curves, detailing their construction through the symmetries induced by $4$-torsion points. In particular, we show how these symmetries allow the computation of theta structures projectively, thus avoiding the use of modular inversions. Furthermore, we explore the self-similarity of the matrix representation of theta structures, arising from the action of the canonical $2$-torsion point in the Kummer line. Combined with the sparsity of some $4$-torsion points, this structure leads to new formulae for computing gluing $(2,2)$ isogenies that require significantly fewer precomputations and arithmetic operations. These new equations also naturally support the evaluation of points on the quadratic twist at a negligible additional cost, without requiring operations in a field extension.

Let us assume that one of two trusted parties (administrator) manages the information system (IS) and another one (user) is going to use the resources of this IS during the certain time interval. So they need establish secure user’s access password to the IS resources of this system via selected authenticated key exchange protocol. So they need to communicate via insecure communication channel and secretly con-struct a cryptographically strong session key that can serve for the establishment of secure passwords in the form of tuples in certain alphabet during the certain time interval. Nowadays selected protocol has to be postquantum secure. We propose the implementation of this scheme in terms of Symbolic Computa-tions. The key exchange protocol is one of the key exchange algorithms of Noncommutative Cryptography with the platform of multivariate transformation of the affine space over selected finite commutative ring. The session key is a multivariate map on the affine space. Platforms and multivariate maps are construct-ed in terms of Algebraic Graph Theory.

We introduce an efficient SNARK for towers of binary fields. Adapting Brakedown (CRYPTO '23), we construct a multilinear polynomial commitment scheme suitable for polynomials over tiny fields, including that with just two elements. Our commitment scheme, unlike those of previous works, treats small-field polynomials with no embedding overhead. We further introduce binary-field adaptations of HyperPlonk (EUROCRYPT '23)'s product and permutation checks and of Lasso (EUROCRYPT '24)'s lookup. Our binary PLONKish variant captures standard hash functions—like Keccak-256 and Grøstl—extremely efficiently. With recourse to thorough performance benchmarks, we argue that our scheme can efficiently generate precisely those Keccak-256-proofs which critically underlie modern efforts to scale Ethereum.

Federated learning enables collaborative model training while preserving data privacy by keeping data local. To protect user privacy during model aggregation, secure aggregation (SA) protocols are widely adopted to mask models. However, existing SA protocols require at least three round trips per aggregation and lack mechanisms to verify aggregation results. Verifiable SA addresses the verification gap but incurs high communication costs. TEE-based SA minimizes round trips but faces computational bottlenecks due to TEE's limited physical memory, especially when handling larger models or numerous clients. In this work, we introduce OPSA, an efficient and verifiable one-pass SA protocol based on TEE. By handling client dropouts via server-side TEE, OPSA enables the server to aggregate masked models in a single pass, significantly reducing round trips. To mitigate TEE's limitations, OPSA offloads tasks like model aggregation and mask elimination outside TEE, with only shared keys processed within TEE. Building on this design, we propose KhPRF-OPSA (single masking) and POT-OPSA (double masking) protocols, both incorporating novel cryptographic primitives. Furthermore, OPSA integrates commitment and signature mechanisms to ensure result verifiability with only $O(1)$ additional communication overhead per client. Compared to state-of-the-art schemes, OPSA achieves a 2$\sim$10$\times$ speedup in multi-round aggregation while guaranteeing result verification.

Smart contracts are integral to decentralized systems like blockchains and enable the automation of processes through programmable conditions. However, their immutability, once deployed, poses challenges when addressing errors or bugs. Existing solutions, such as proxy contracts, facilitate upgrades while preserving application integrity. Yet, proxy contracts bring issues such as storage constraints and proxy selector clashes - along with complex inheritance management. This paper introduces a novel upgradeable smart contract framework with version control, named "decentraLized vErsion control and updAte manaGement in upgrAdeable smart coNtracts (LEAGAN)." LEAGAN is the first decentralized updatable smart contract framework that employs data separation with Incremental Hash (IH) and Revision Control System (RCS). It updates multiple contract versions without starting anew for each update, and reduces time complexity, and where RCS optimizes space utilization through differentiated version control. LEAGAN also introduces the first status contract in upgradeable smart contracts, and which reduces overhead while maintaining immutability. In Ethereum Virtual Machine (EVM) experiments, LEAGAN shows 40\% better space utilization, 30\% improved time complexity, and 25\% lower gas consumption compared to state-of-the-art models. It thus stands as a promising solution for enhancing blockchain system efficiency.

Range counting is the problem of preprocessing a set $P\subset R^d$ of $n$ points, such that given a query range $\gamma$ we can efficiently compute $|P\cap\gamma|$. In the more general range searching problem the goal is to compute $f(P\cap\gamma)$, for some function $f$. It was already shown (Kushnir et al. PETS'24) how to efficiently answer a range searching query under FHE using a technique they called Copy-and-Recurse to traverse partition trees. In the Range emptiness problem the goal is to compute only whether $P\cap\gamma =\emptyset$. This was shown (in plaintext) to be done more efficiently. Range emptiness is interesting on its own and also used as a building block in other algorithms. In this paper we improve and extend the results of Kushnir et al. First, for range searching we reduce the overhead term to the optimal $O(n)$, so for example if the ranges are halfspaces in $R^d$ bounded by hyperplanes then range searching can be done with a circuit of size $O(t\cdot n^{1-1/d+\varepsilon}+n)$, where $t$ is the size of the sub-circuit that checks whether a point lies under a hyperplane. Second, we introduce a variation of copy-and-recurse that we call leveled copy-and-recurse. With this variation we improve range searching in the 1-dimensional case as well as traversal of other trees (e.g., binary trees and B-trees). Third, we show how to answer range emptiness queries under FHE more efficiently than range counting. We implemented our algorithms and show that our techniques for range emptiness yield a solution that is $\times 3.6$ faster than the previous results for a database of $2^{25}$ points.

Secure rate-distortion-perception (RDP) trade-offs arise in critical applications, such as semantic compression and privacy-preserving generative coding, where preserving perceptual quality while minimizing distortion is vital. This paper studies a framework for secure RDP over noiseless and noisy broadcast channels under strong secrecy constraints. We first characterize the exact secure RDP region for noiseless transmission channels. We then develop an inner bound on the secure RDP region for a memoryless broadcast channel with correlated noise components at the receivers' observations and prove its tightness under a more capable broadcast channel assumption. Our results demonstrate how optimized binning schemes simultaneously achieve high perceptual quality, low distortion, and strong secrecy, illuminating fundamental information-theoretic limits for next-generation trustworthy computation systems.

Differential-linear cryptanalysis was introduced by Langford and Hellman in 1994 and has been extensively studied since then. In 2019, Bar-On et al. presented the Differential-Linear Connectivity Table (DLCT), which connects the differential part and the linear part, thus an attacked cipher is divided to 3 subciphers: the differential part, the DLCT part, and the linear part. In this paper, we firstly present an accurate mathematical formula which establishes a relation between differential-linear and truncated differential cryptanalysis. Using the formula, the bias estimate of a differential-linear distinguisher can be converted to the probability calculations of a series of truncated differentials. Then, we propose a novel and natural concept, the TDT, which can be used to accelerate the calculation of the probabilities of truncated differentials. Based on the formula and the TDT, we propose two novel approaches for estimating the bias of a differential-linear distinguisher. We demonstrate the accuracy and efficiency of our new approaches by applying them to 5 symmetric-key primitives: Ascon, Serpent, KNOT, AES, and CLEFIA. For Ascon and Serpent, we update the best known differential-linear distinguishers. For KNOT AES, and CLEFIA, for the first time we give the theoretical differential-linear biases for different rounds.

Quantum computers leverage qubits to solve certain computational problems significantly faster than classical computers. This capability poses a severe threat to traditional cryptographic algorithms, leading to the rise of post-quantum cryptography (PQC) designed to withstand quantum attacks. FALCON, a lattice-based signature algorithm, has been selected by the National Institute of Standards and Technology (NIST) as part of its post-quantum cryptography standardization process. However, due to the computational complexity of PQC, especially in cloud-based environments, throughput limitations during peak demand periods have become a bottleneck, particularly for FALCON. In this paper, we introduce GOLF (GPU-accelerated Optimization for Lattice-based FALCON), a novel GPU-based parallel acceleration framework for FALCON. GOLF includes algorithm porting to the GPU, compatibility modifications, multi-threaded parallelism with distinct data, single-thread optimization for single tasks, and specific enhancements to the Fast Fourier Transform (FFT) module within FALCON. Our approach achieves unprecedented performance in FALCON acceleration on GPUs. On the NVIDIA RTX 4090, GOLF reaches a signature generation throughput of 42.02 kops/s and a signature verification throughput of 10,311.04 kops/s. These results represent a 58.05$\times$ / 73.14$\times$ improvement over the reference FALCON implementation and a 7.17$\times$ / 3.79$\times$ improvement compared to the fastest known GPU implementation to date. GOLF demonstrates that GPU acceleration is not only feasible for post-quantum cryptography but also crucial for addressing throughput bottlenecks in real-world applications.

The Classic McEliece key encapsulation mechanism (KEM), a candidate in the fourth-round post-quantum cryptography (PQC) standardization process by the National Institute of Standards and Technology (NIST), stands out for its conservative design and robust security guarantees. Leveraging the code-based Niederreiter cryptosystem, Classic McEliece delivers high-performance encapsulation and decapsulation, making it well-suited for various applications. However, there has not been a systematic implementation of Classic McEliece on GPU platforms. This paper presents the first high-performance implementation of Classic McEliece on NVIDIA GPUs. Firstly, we present the first GPU-based implementation of Classic McEliece, utilizing a ``CPU-GPU'' heterogeneous approach and a kernel fusion strategy. We significantly reduce global memory accesses, optimizing memory access patterns. This results in encapsulation and decapsulation performance of 28,628,195 ops/s and 3,051,701 ops/s, respectively, for McEliece348864. Secondly, core operations like Additive Fast Fourier Transforms (AFFT), and Transpose AFFT (TAFFT) are optimized. We introduce the concept of the (T)AFFT stepping chain and propose two universal schemes: Memory Access Stepping Strategy (MASS) and Layer-Fused Memory Access Stepping Strategy (LFMASS), which achieve a speedup of 30.56% and 38.37%, respectively, compared to the native GPU-based McEliece6960119 implementation. Thirdly, extensive experiments on the NVIDIA RTX4090 show significant performance gains, achieving up to 344$\times$ higher encapsulation and 125$\times$ higher decapsulation compared to the official CPU-based AVX implementation, decisively outperforming existing ARM Cortex-M4 and FPGA implementations.

This work proposes an encrypted hybrid database framework that combines vectorized data search and relational data query over quantized fully homomorphic encryption (FHE). We observe that, due to the lack of efficient encrypted data ordering capabilities, most existing encrypted database (EDB) frameworks do not support hybrid queries involving both vectorized and relational data. To further enrich query expressiveness while retaining evaluation efficiency, we propose Engorgio, a hybrid EDB framework based on quantized data ordering techniques over FHE. Specifically, we design a new quantized data encoding scheme along with a set of novel comparison and permutation algorithms to accurately generate and apply orders between large-precision data items. Furthermore, we optimize specific query types, including full table scan, batched query, and Top-k query to enhance the practical performance of the proposed framework. In the experiment, we show that, compared to the state-of-the-art EDB frameworks, Engorgio is up to 28x--854x faster in homomorphic comparison, 65x--687x faster in homomorphic sorting and 15x--1,640x faster over a variety of end-to-end relational, vectorized, and hybrid SQL benchmarks. Using Engorgio, the amortized runtime for executing a relational and hybrid query on a 48-core processor is under 3 and 75 seconds, respectively, over a 10K-row hybrid database.

Bitcoin is based on the Blockchain, an open ledger containing information about each transaction in the Bitcoin network. Blockchain serves many purposes, but it allows anyone to track all transactions and activities of each Bitcoin address. The privacy of the network is being threatened by some organizations that track transactions. Tracking and subsequent filtering of coins lead to the loss of exchangeability of Bitcoin. Despite Bitcoin’s transparency, it is possible to increase user privacy using a variety of existing methods. One of these methods is called CoinJoin, was proposed by Bitcoin developer Greg Maxwell in 2013. This technology involves combining several users transactions to create a single transaction with multiple inputs and outputs, which makes transaction analysis more complicated. This work describes the CoinMaze, a privacy-focused CoinJoin protocol based on the keyed-verification anonymous credentials (KVAC).

This work introduces Zemlyanika, a post-quantum IND-CCA secure key encapsulation mechanism based on the Module-LWE problem. The high-level design of Zemlyanika follows a well-known approach where a passively secure public-key encryption scheme is transformed into an actively secure key encapsulation mechanism using the Fujisaki-Okamoto transform. Our scheme features three main elements: a power-of-two modulus, explicit rejection, and revised requirements for decapsulation error probability. The choice of a power-of-two modulus is atypical for Module-LWE based schemes due to the unavailability of Number Theoretic Transform (NTT). However, we argue that this option offers advantages that are often underestimated. We employ explicit rejection because it is more efficient than implicit rejection. Recent works show that both types of rejection are equally secure, so we do not reduce the security by this choice. Finally, we present compelling arguments that the probability of decapsulation failure may be higher than commonly accepted. This allows us to increase performance and security against attacks on the Module-LWE.

Liquid democracy is a transitive vote delegation mechanism over voting graphs. It enables each voter to delegate their vote(s) to another better-informed voter, with the goal of collectively making a better decision. The question of whether liquid democracy outperforms direct voting has been previously studied in the context of local delegation mechanisms (where voters can only delegate to someone in their neighbourhood) and binary decision problems. It has previously been shown that it is impossible for local delegation mechanisms to outperform direct voting in general graphs. This raises the question: for which classes of graphs do local delegation mechanisms yield good results? In this work, we analyse (1) properties of specific graphs and (2) properties of local delegation mechanisms on these graphs, determining where local delegation actually outperforms direct voting. We show that a critical graph property enabling liquid democracy is that the voting outcome of local delegation mechanisms preserves a sufficient amount of variance, thereby avoiding situations where delegation falls behind direct voting. These insights allow us to prove our main results, namely that there exist local delegation mechanisms that perform no worse and in fact quantitatively better than direct voting in natural graph topologies like complete, random $d$-regular, and bounded degree graphs, lending a more nuanced perspective to previous impossibility results.

We were deeply impressed by the paper by Ateniese et al., published in Crypto 2019. In it, they presented a black-box construction of matchmaking encryption (ME) based on functional encryption. In our work, we propose an ME scheme based on standard assumptions in the standard model. This scheme has been proven to be secure under the learning with error (LWE) assumption. Our ME scheme is achieved through a novel framework of bilateral-policy attribute-based encryption (BP-ABE) and a new intermediate primitive termed a perturbed pseudorandom generator (PPRG), which facilitates the implementation of authentication functionality by replacing non-interactive zero-knowledge proof functionality. In the scheme presented in this paper, the user's "public key" is generated using Hamming correlation robustness and user attributes. Note that the 'public key' is not public. In order to preserve the privacy of the two parties involved in matchmaking encryption, our BP-ABE scheme does not use the 'public key' directly to encrypt the plaintext. Instead, the message sender selects matching attributes and uses a Hamming correlation robustness and homomorphic pseudorandom function (HPRF) to generate temporary public keys and hide the public key and user attributes. When these temporary public keys satisfy the access policy, the receiver can decrypt the data using their private key. Regarding the authentication function of matchmaking encryption, this paper proposes a non-interactive privacy set intersection (PSI) scheme based on HPRF and PPRG. The message sender encrypts their 'public key' using the proposed PSI scheme as part of the ciphertext. The receiver also encrypts their 'public key' using the proposed PSI scheme and matches the attributes, thereby completing the message authentication function. We consider our approach to be a significant departure from existing constructions, despite its simplicity.

We present Bitcoin Thunderbolt, a novel off-chain protocol for asynchronous, secure transfer of Bitcoin UTXOs between uncoordinated users. Unlike prior solutions such as payment channels or the Lightning Network, Bitcoin Thunderbolt requires no prior trust, direct interaction, or continuous connectivity between sender and receiver. At its core, Bitcoin Thunderbolt employs a Byzantine fault-tolerant committee to manage threshold Schnorr signatures, enabling secure ownership delegation and on-chain finalization. Our design supports recursive, off-chain UTXO transfers using tweakable, verifiable signature components. The protocol tolerates up to $f$ malicious nodes in a $3f+1$ committee and ensures correctness, consistency, and one-time spendability under asynchronous network conditions. We formally verify Bitcoin Thunderbolt’s key security properties, namely, unforgeability, ownership soundness, and liveness—using the Tamarin prover. Our results demonstrate that Thunderbolt provides robust, scalable, and non-interactive off-chain Bitcoin transfers, significantly expanding the practical utility of Bitcoin for decentralized applications.

Let us assume that one of two trusted parties (administrator) manages the information system (IS) and another one (user) is going to use the resources of this IS during the certain time interval. So they need establish secure user’s access password to the IS resources of this system via selected authenticated key exchange protocol. So they need to communicate via insecure communication channel and secretly con-struct a cryptographically strong session key that can serve for the establishment of secure passwords in the form of tuples in certain alphabet during the certain time interval. Nowadays selected protocol has to be postquantum secure. We propose the implementation of this scheme in terms of Symbolic Computa-tions. The key exchange protocol is one of the key exchange algorithms of Noncommutative Cryptography with the platform of multivariate transformation of the affine space over selected finite commutative ring. The session key is a multivariate map on the affine space. Platforms and multivariate maps are construct-ed in terms of Algebraic Graph Theory.

As quantum computing matures, its impact on traditional cryptographic protocols becomes increasingly critical, especially for data-at-rest scenarios where large data sets remain encrypted for extended periods of time. This paper addresses the pressing need to transition away from pre-quantum algorithms by presenting an agile cryptosystem that securely and efficiently supports post-quantum Key Encapsulation Mechanisms (KEMs). The proposed solution is based on combining a CCA-secure KEM with a robust Authenticated Encryption scheme, allowing only the dynamic component - the symmetric key encapsulation - to be updated when migrating to new cryptographic algorithms. This approach eliminates the need to re-encrypt potentially massive data payloads, resulting in significant savings in computational overhead and bandwidth. We formalize the concept of cryptoagility through an agile-CCA security model, which requires that neither the original ciphertext nor any updated version reveals meaningful information to an attacker. A game-based proof shows that the overall construction remains agile-CCA secure if the underlying KEM and AE are individually CCA secure under a random oracle assumption. The result is a future-proof scheme that eases the transition to post-quantum standards, enabling enterprises and cloud storage providers to protect large amounts of data with minimal disruption while proactively mitigating emerging quantum threats.

As datasets grow, users increasingly rely on cloud services for data storage and processing. Consequently, concerns regarding data protection and the practical use of encrypted data have emerged as significant challenges. One promising solution is order-revealing encryption (ORE), which enables efficient operations on encrypted numerical data. To support distributed environments with different users, delegatable ORE (DORE) extends this functionality to multi-client settings, enabling order comparisons between ciphertexts encrypted under different secret keys. However, Hahn et al. proposed a token forgery attack against DORE with a threat model and introduced the secure DORE (SEDORE) scheme as a countermeasure. Despite this enhancement, we claim that SEDORE remains vulnerable under the same threat model. In this paper, we present a novel Universal Token Reusability Attack, which exposes a critical vulnerability in SEDORE with the identical threat model. To mitigate this, we introduce the concept of verifiable delegatable order-revealing encryption (VDORE), along with a formal definition of token unforgeability. Building on this, we design a new scheme, Token Unforgeable DORE ($\mathsf{TUDORE}$), which ensures token unforgeability. Moreover, $\mathsf{TUDORE}$ achieves 1.5× faster token generation than SEDORE with enhanced security.

In order for a client to securely connect to a server on the web, the client must trust certificate authorities (CAs) only to issue certificates to the legitimate operator of the server. If a certificate is miss-issued, it is possible for an attacker to impersonate the server to the client. The goal of Certificate Transparency (CT) is to log every certificate issued in a manner that allows anyone to audit the logs for miss-issuance. A client can even audit a CT log itself, but this would leak sensitive browsing data to the log operator. As a result, client-side audits are rare in practice. In this work, we revisit private CT auditing from a real-world perspective. Our study is motivated by recent changes to the CT ecosystem and advancements in Private Information Retrieval (PIR). First, we find that checking for inclusion of Signed Certificate Timestamps (SCTs) in a log — the audit performed by clients — is now possible with PIR in under a second and under 100kb of communication with minor adjustments to the protocol that have been proposed previously. Our results also show how to scale audits by using existing batching techniques and the algebraic structure of the PIR protocols, in particular to obtain certificate hashes by included in the log. Since PIR protocols are more performant with smaller databases, we also suggest a number of strategies to lower the size of the SCT database for audits. Our key observation is that the web will likely transition to a new model for certificate issuance. While this transition is primarily motivated by the need to adapt the PKI to larger, post-quantum signature schemes, it also removes the need for SCT audits in most cases. We present the first estimates of how this transition may impact SCT auditing, based on data gathered from public CT logs. We find that large scale deployment of the new issuance model may reduce the number of SCT audits needed by a factor of 1,000, making PIR-based auditing practical to deploy.

Oblivious pseudorandom functions (OPRFs) are an important primitive in privacy-preserving cryptographic protocols. The growing interest in OPRFs, both in theory and practice, has led to the development of numerous constructions and variations. However, most of these constructions rely on classical assumptions. Potential future quantum attacks may limit the practicality of those OPRFs for real-world applications. To close this gap, we introduce Leap, a novel OPRF based on heuristic lattice assumptions. Fundamentally, Leap builds upon the Spring [BBL+15] pseudorandom function (PRF), which relies on the learning with rounding assumption, and integrates techniques from multi-party computation, specifically Oblivious Transfer (OT) and Oblivious Linear Evaluation (OLE). With this combination of oblivious protocols, we construct an OPRF that evaluates in less than a millisecond on a modern computer. Efficiency-wise, our prototype implementation achieves computation times of just 11 microseconds for the client and 750 microseconds for the server, excluding some base OT preprocessing overhead. Moreover, Leap requires an online communication cost of 23 kB per evaluation, where the client only has to send around 380 bytes online. To demonstrate the practical applicability of Leap, we present an efficient private set intersection (PSI) protocol built on top of Leap. This application highlights the potential for the integration of Leap into various privacy-preserving applications: We can compute an unbalanced set intersection with set sizes of 2^24 and 2^15 in under a minute of online time and just over two minutes overall.

Sharding is a generic approach to enhance the scalability of distributed systems. In recent years, many efforts have been made to scale the consensus mechanism of blockchains from sharding. A crucial research question is how to achieve the sweet spot of having a relatively small shard size (to achieve decent performance) while achieving an overwhelming probability of correctness (so the system is safe and live). Many recent works fall into the two-layer design that uses some coordinating shards to monitor the correctness of other shards (CCS 2022, NDSS 2024, INFOCOM 2023). All of them involve expensive communication costs between the shards, significantly degrading performance. We present Otter, a scalable partially synchronous sharding-based Byzantine fault-tolerant atomic broadcast (ABC) protocol. We use coordinating shards in a completely new way. In particular, we randomly sample coordinating shards to directly participate in the consensus protocol. Such a random sampling mechanism makes it possible to analyze the correctness of the ABC protocol using a probabilistic model. In this way, we can significantly lower the shard size (informally, from over 1,200 in previous work to around 100) without lowering the probability of correctness. We also present a new notion called abortable fork detection (AFD) that might be of independent interest. Our evaluation results on Amazon EC2 using up to 1,000 replicas show that Otter achieves up to 4.38x the throughput of the state-of-the-art protocol.

SNAIL (Succinct, Non-interactive, Alon-compressed, Instant argument for Layered circuits) turns any depth-\(d\) arithmetic circuit into a non-interactive argument whose prover runs within \(1 + c(d,k,n)\) of plain circuit execution, where \(c(d,k,n) = \frac{3\,(k+n+1)}{k\,d + n + 1}\). For the representative choice \(k = n = 4\) and \(24 \le d \le 32\) this means only 21–28 % overhead. Core idea: A constant-round zerocheck based on a difference-driven Alon decomposition compresses all \(d\) layers into one multivariate identity. Fiat–Shamir in the random-oracle model yields a transparent argument whose hot loop uses only field additions and multiplications (no MSMs, FFTs, or Merkle trees). Cost summary: with \(k = n = 4\) and \(24 \le d \le 32\) \[ T_{\text{prov}}(S,d)=\Bigl(1+\frac{6.75}{d}\Bigr)S,\qquad |\pi|=(d^{2}+2d)(4d+1),\qquad \varepsilon_{\text{sound}}=\frac{4nd}{|\mathbb F|}. \] A 2.6-billion-gate trace at \(d = 32\) is proven in \(\approx 40\;\text{ms}\) on an RTX-4090 and verified on a smartphone in \(< 1\;\text{ms}\). Width scalability: Proof size depends only on depth, so widening to billions of parallel gates leaves the verifier unchanged—ideal for ultra-wide workloads such as live-audited VM traces. Security: The six-round interactive core is statistically sound; the Fiat–Shamir variant is computationally sound in the random-oracle model and needs no trusted setup. Implications: SNAIL shows that a prover can run near real-time on commodity GPUs while emitting proofs small enough for mobile light clients, enabling applications such as live-streamed provable gaming, pay-per-cycle cloud nodes, and always-on verifiable CPUs.

Multivariate public key cryptography (MPKC) is considered a promising candidate for post-quantum cryptography, with its security relying on the hardness of solving systems of multivariate quadratic equations. Among MPKC schemes, the unbalanced oil and vinegar (UOV) and its variants have been actively studied. Pébereau and Luyten showed that the Kipnis–Shamir attack and the singular point attack can be described within the same framework using the Jacobian matrix. In this study, we demonstrate that the rectangular MinRank attack can also be described within this framework. Furthermore, by leveraging this framework, we extend the feasible target ranks of the rectangular MinRank attack and use this extended attack to analyze the security of UOV and its variants. In conclusion, we confirm that the currently proposed parameters for UOV, MAYO, QR-UOV, and SNOVA are resistant to this attack.

In this work, we derive the first lifting theorems for establishing security in the quantum random permutation and ideal cipher models. These theorems relate the success probability of an arbitrary quantum adversary to that of a classical algorithm making only a small number of classical queries. By applying these lifting theorems, we improve previous results and obtain new quantum query complexity bounds and post-quantum security results. Notably, we derive tight bounds for the quantum hardness of the double-sided zero search game and establish the post-quantum security for the preimage resistance, one-wayness, and multi-collision resistance of constant-round sponge, as well as the collision resistance of the Davies-Meyer construction.

Scloud$^{+}$ is a next-generation post-quantum key encapsulation mechanism that combines unstructured-LWE and a ternary key encoding technique to achieve efficient lattice cryptographic operations while eliminating traditional ring structure constraints. Despite its rigorously formalized theoretical security, its practical deployment faces side-channel threats, notably Correlation Power Analysis (CPA) attacks. This paper systematically investigates the physical security of its core ciphertext-key matrix multiplication module by proposing a CPA framework that integrates instruction-level timing analysis. A SoST (Sum of Squared T-values) model, inspired by multi-group Welch's t-test, is used to analyze the Hamming weight leakage during ciphertext loading. At the same time, dynamic sampling windows, combined with processor pipeline modeling, are employed to pinpoint critical leakage intervals. Exploiting the characteristics of ternary keys, an iterative recovery strategy is devised: following a predefined scan order, the candidate set $\{-1, 0, 1\}$ and partial intermediate sums are used to construct a Hamming weight model for hypothesized leakage vectors. Pearson correlation analysis and trace-count stabilization are applied within each dynamic sampling window to determine the optimal estimate for each key element. Experiments targeting 4800 key elements, illustrated through a detailed analysis of the first 32 elements, demonstrate high recovery accuracy with no more than 15 traces per element, indicating high efficiency and stability that can extend to the full key reconstruction. To thwart such CPA attacks, we have further designed and implemented a first‐order arithmetic masking countermeasure that splits the original ternary secret key into two subkeys, thereby expanding the attacker's key hypothesis space and significantly enhancing side‐channel resilience. Our results demonstrate that Scloud$^{+}$ remains vulnerable to side‐channel exploits at the implementation level, highlighting the urgent need to integrate appropriate protections into its standardization process.

In this work, we focus on maliciously secure 3PC for binary circuits with honest majority. While the state-of-the-art (Boyle et al. CCS 2019) has already achieved the same amortized communication as the best-known semi-honest protocol (Araki et al. CCS 2016), they suffer from a large computation overhead: when comparing with the best-known implementation result (Furukawa et al. Eurocrypt 2017) which requires $9\times$ communication cost of Araki et al., the protocol by Boyle et al. is around $4.5\times$ slower than that of Furukawa et al. In this paper, we design a maliciously secure 3PC protocol that matches the same communication as Araki et al. with comparable concrete efficiency as Furukawa et al. To obtain our result, we manage to apply the distributed zero-knowledge proofs (Boneh et al. Crypto 2019) for verifying computations over $\mathbb{Z}_2$ by using \emph{prime} fields and explore the algebraic structure of prime fields to make the computation of our protocol friendly for native CPU computation. Experiment results show that our protocol is around $3.5\times$ faster for AES circuits than Boyle et al. We also applied our protocol to the binary part (e.g. comparison and truncation) of secure deep neural network inference, and results show that we could reduce the time cost of achieving malicious security in the binary part by more than $67\%$. Besides our main contribution, we also find a hidden security issue in many of the current probabilistic truncation protocols, which may be of independent interest.

Recent work on IOP-based succinct arguments has focused on developing IOPs that improve prover efficiency by relying on linear-time encodable codes. We present two new schemes for improving the efficiency of such succinct arguments: $\quad \bullet$ $\mathsf{FICS}$, an IOP of proximity for multilinear polynomial evaluation that, like prior work Blaze [EUROCRYPT 2025] achieves linear prover time, but additionally reduces the verifier oracle query complexity to $O(\lambda \log \log n + \log n)$ for codewords of length $n$. $\quad \bullet$ $\mathsf{FACS}$, an accumulation scheme for NP that achieves linear prover time and $O(\lambda)$ oracle queries per step of the accumulation. Both schemes support a large class of linear-time encodable codes, including systematic LDPC codes and tensor codes of linear-time encodable codes. We obtain our results by extending and formalizing the framework of Interactive Oracle Reductions (IORs) introduced by Ben-Sasson et al. [TCC 2019]. In particular, we develop new IORs for "codeswitching" tensor codes (Ron-Zewi and Rothblum [JACM 2024]), and also develop a new notion of knowledge soundness for IORs that allows us to easily compose IORs and to prove the security of our schemes in the non-interactive setting, even if the underlying codes are not known to be decodable in polynomial time.

We describe the design and implementation of MicroNova, a folding-based recursive argument for producing proofs of incremental computations of the form $y = F^{(\ell)}(x)$, where $F$ is a possibly non-deterministic computation (encoded using a constraint system such as R1CS), $x$ is the initial input, $y$ is the output, and $\ell > 0$. The proof of an $\ell$-step computation is produced step-by-step such that the proof size nor the time to verify it depends on $\ell$. The proof at the final iteration is then compressed, to achieve further succinctness in terms of proof size and verification time. Compared to prior folding-based arguments, a distinguishing aspect of MicroNova is the concrete efficiency of the verifier—even in a resource-constrained environment such as Ethereum’s blockchain. In particular, the compressed proof consists of $O(\log{N})$ group elements and it can be verified with $O(\log{N})$ group scalar multiplications and two pairing operations, where $N$ is the number of constraints for a single invocation of $F$. MicroNova requires a universal trusted setup and can employ any existing setup material created for the popular KZG univariate polynomial commitment scheme. Finally, we implement and experimentally evaluate MicroNova. We find that MicroNova’s proofs can be efficiently verified on the Ethereum blockchain with $\approx$2.2M gas. Furthermore, MicroNova’s prover incurs minimal overheads atop its baseline Nova’s prover.

Key blinding produces pseudonymous digital identities by rerandomizing public keys of a digital signature scheme. It provides privacy in decentralized networks. Current key blinding schemes are based on the discrete log assumption. Eaton, Stebila and Stracovsky (LATINCRYPT 2021) proposed the first post-quantum key blinding schemes from lattice assumptions. However, the large public keys and lack of QROM security means they are not ready to replace existing solutions. We present a general framework to build post-quantum signature schemes with key blinding based on the MPC-in-the-Head paradigm. This results in schemes that rely on well-studied symmetric cryptographic primitives and admit short public keys. We prove generic security results in the quantum random oracle model (QROM). We instantiate our framework with the recent AES-based Helium signature scheme (Kales and Zaverucha, 2022) to obtain an efficient post-quantum key blinding scheme with small keys. Both Helium and the aforementioned lattice-based key blinding schemes were only proven secure in the ROM. This makes our results the first QROM proof of Helium and the first fully quantum-safe public key blinding scheme.

Every computing paradigm involving communication requires new security protocols employing cryptography. For example, the Internet gave rise to TLS/SSL, and Mobile Computing gave rise to End to End Encryption protocols. In this paper, we address an emerging IoT paradigm involving beacons attached to things and security protocols associated with this new configuration. Specifically, we address the ``beacon notification problem,'' a critical IoT paradigm aims at providing secure and efficient real-time notifications from beacons to their owners. Since the beacon notification problem has not yet been formally defined, we begin by inspecting natural requirements based on the operational setting and establishing correctness, security, and privacy definitions through the use of cryptographic games. To resolve this problem, we propose a novel cryptographic tool we call XDHIES, which is a considerable extension of available Diffie-Hellman encryption schemes. We then show a new notification protocol built upon XDHIES and we prove that this cryptographic protocol is secure and private and successfully meets all the above problem's requirements.

Key Transparency (KT) systems have emerged as a critical technology for adding verifiability to the distribution of public keys used in end-to-end encrypted messaging services. Despite substantial academic interest, increased industry adoption, and IETF standardization efforts, KT systems lack a holistic and formalized security model, limiting their resilience to practical threats and constraining future development. In this paper, we survey the existing KT literature and present the first cryptographically sound formalization of KT as an ideal functionality. Our work clarifies the underlying assumptions, defines core security properties, and highlights potential vulnerabilities in deployed KT systems. We prove in the Universal Composability framework that our concrete protocol achieves KT security as defined by our formalism. Our KT protocol builds on the latest trends in KT design, guided by the formalization.

At CRYPTO 2019, A. Gohr introduced Neural Differential Cryptanalysis and used deep learning to improve the state-of-the-art cryptanalysis of 11-round SPECK32. As of February 2025, according to Google Scholar, Gohr’s article has been cited 229 times. The variety of targeted cryptographic primitives, techniques, settings, and evaluation methodologies that appear in these follow-up works grants a careful systematization of knowledge, which we provide in this paper. More specifically, we propose a taxonomy of these 229 publications and systematically review the 66 papers focusing on neural differential distinguishers, pointing out promising directions. We then highlight future challenges in the field, particularly the need for improved comparability of neural distinguishers and advancements in scaling.

Threshold encryption schemes provide a common tool to secure a public-key encryption scheme against single point of failure attacks. Despite the success of lattices in building fully-homomorphic and presumably quantum-resistant encryption schemes, the task of thresholdizing those schemes remains challenging. The major bottleneck in the standard approach is the use of statistical noise flooding, leading to a significant efficiency loss and the need of stronger hardness assumptions. Recent works have replaced the heavy statistical noise flooding by a lighter one using the Rényi divergence. The new Rényi noise flooding both improves the efficiency and allows to use weaker hardness assumptions. However, arguing semantic security of lattice-based threshold schemes in the presence of Rényi noise flooding showed to be challenging. Chowdhury et al. (IACR ePrint'22) argued in the fully-homomorphic case that the Rényi divergence directly applies for semantic security by making use of an existing framework called public sampleability. In this work, we argue that their public sampleability framework was neither sufficient nor correctly used. To address both issues, we strengthen the framework and thoroughly apply it to prove semantic security of generic lattice-based threshold encryption constructions. We distinguish between the plain public-key and the fully-homomorphic settings, as different security notions are achieved. As a byproduct, this shows that the proof detour via one-way security made by Boudgoust and Scholl (Asiacrypt'23) was superfluous, now leading to tighter proofs in the standard model.

Distributed randomness beacon protocols, which continuously generate publicly verifiable randomness values, are crucial for many applications. Recently, there have been many approaches, such as Hydrand (S\&P'20), SPURT (S\&P'22), OptRand (NDSS'23) and GRandLine (CCS'24), based on publicly verifiable secret sharing (PVSS) to implement beacon protocols. However, two key challenges remain unresolved: asynchrony and reconfiguration. In this paper, we propose the $\mathsf{AsyRand}$ beacon protocol to address these challenges. We incorporate a producer-consumer model to decouple the distribution and reconstruction of PVSS secrets. Parties continuously produce and distribute new PVSS commitments, which are the encrypted shares and the proofs. Meanwhile, all parties store received commitments using first-in-first-out queues and collectively consume each commitment to recover the corresponding secret for beacon generation. To achieve asynchronous consensus, we employ reliable broadcast for distribution and apply $t$-validated asynchronous Byzantine agreement for reconstruction. To achieve reconfiguration, honest parties can collectively remove a faulty party if his queue remains empty for an extended duration, and a new party can join the system using reliable broadcast. We also introduce a novel PVSS scheme based on Sigma protocol and Fiat-Shamir heuristic, which is of independent interest. Consequently, $\mathsf{AsyRand}$ maintains state-of-the-art complexity with $O(n^2)$ communication complexity, $O(n)$ computation complexity, and $O(n)$ verification complexity while achieving asynchrony and reconfiguration. Experimental results highlight the performance of $\mathsf{AsyRand}$ compared to existing works.

Delegation of quantum computation in a trustful way is one of the most fundamental challenges toward the realization of future quantum cloud computing. While considerable progress has been made, no known protocol provides a purely classical client with universal delegated quantum computation while simultaneously ensuring blindness (input privacy), verifiability (soundness), and robustness against quantum noise—a feat that must be achieved under stringent cryptographic assumptions and with low overhead. In this work, I introduce UVCQC, a new delegation framework that, for the first time, realizes a fully composable protocol for securely delegating quantum computations to an untrusted quantum server from a classical client. My scheme employs trap-based quantum authentication, post-quantum cryptographic commitments, and zero-knowledge proofs to provide full guarantees: the client remains purely classical; the server learns nothing about the computation; and any attempt to deviate from the specified circuit is detected with high probability. I rigorously prove completeness, soundness, and perfect blindness of the protocol and demonstrate its universal composability against unbounded quantum adversaries. Furthermore, I propose a thermodynamically inspired verification mechanism based on energy dissipation and entropy change, enabling physically testable verification independent of cryptographic assumptions. Beyond its core architecture, UVCQC is deeply intertwined with multidisciplinary frameworks: it admits a game-theoretic formulation where honesty is a Nash equilibrium, an information-theoretic treatment grounded in Holevo bounds, a categorical model via compact closed structures, and novel cryptographic enhancements based on isogeny-based primitives and topological invariants. This research offers a scalable and unified solution to the blind and verifiable delegation problem, pushing forward the theoretical and practical frontiers of secure quantum computation—and opening a tangible path toward trustable quantum cloud services for classical users.

The Learning Parity with Noise (LPN) problem and its regular noise variant are fundamental to many cryptographic primitives. While recent proposals extend these problems to larger fields to enhance cryptographic applications, the security implications of LPN over large fields remain understudied. This gap has facilitated more effective attacks, potentially compromising the security of LPN-based primitives over large fields. In this paper, we present an improved algorithm for solving LPN over large fields. Our method enhances the classical Gaussian elimination attack, specifically Prange's information set decoding algorithm, by iteratively applying Gaussian elimination to reduced-size matrices rather than the full-size matrix. We call this the ``Reduce and Prange (RP)" algorithm and demonstrate its effectiveness for both LPN and its variant with regular noise over large finite fields (e.g., $\mathbb{F}_{2^{128}}$). Building on the RP algorithm, we develop a modified algebraic algorithm for LPN with regular noise over $\mathbb{F}_q$ with $q \geq 2$, extending the work of Briaud and Øygard (Eurocrypt'23). Furthermore, we demonstrate that Scalable Multiparty Garbling (CCS'23) fails to meet their claimed security levels. For LPN over large fields (e.g., 128-bit field size), our algorithm reduces bit-security by up to 9 bits relative to Liu et al. (Eurocrypt'24). In the case of LPN with regular noise, our RP algorithm surpasses both Liu et al. and Briaud and Øygard (Eurocrypt'23) under specific parameter settings, achieving up to 16-bit reduction in security.

Safeguarding cryptographic implementations against the increasing threat of Side-Channel Analysis (SCA) attacks is essential. Masking, a countermeasure that randomizes intermediate values, is a cornerstone of such defenses. In particular, SCA-secure implementation of AES, the most-widely used encryption standard, can employ Boolean masking as well as multiplicative masking due to its underlying Galois field operations. However, multiplicative masking is susceptible to vulnerabilities, including the zero-value problem, which has been identified right after theintroduction of multiplicative masking. At CHES 2018, De Meyer et al. proposed a hardware-based approach to manage these challenges and implemented multiplicative masking for AES, incorporating a Kronecker delta function and randomness optimization. In this work, we evaluate their design using the PROLEAD evaluation tool under the glitch- and transition-extended probing model. Our findings reveal a critical vulnerability in their first- and second-order implementation of the Kronecker delta function, stemming from the employed randomness optimization. This leakage compromises the security of their presented masked AES Sbox. After pinpointing the source of such a leakage, we propose an alternative randomness optimization for the first-order design to address this issue, and demonstrate its effectiveness through rigorous evaluations by means of PROLEAD.

The parallel broadcast (PBC) problem generalizes the classic Byzantine broadcast problem to the setting where all $n$ nodes broadcast a message and deliver $O(n)$ messages. PBC arises naturally in many settings including multi-party computation. The state-of-the-art PBC protocol, TrustedPBC, is due to Tsimos, Loss, and Papamanthou (CRYPTO 2022), which is secure under an adaptive adversary assuming $f < (1 - \epsilon)n$, where $f$ is the number of Byzantine failures and $\epsilon \in (0,1)$. TrustedPBC focuses on single-bit inputs and achieves $\tilde{O}(n^2 \kappa^4)$ communication and $O(\kappa\log n)$ rounds. In this work, we propose three PBC protocols for $L$-bit messages, for any size $L$, that significantly improve TrustedPBC. First, we propose a new extension protocol that uses a $\kappa$-bit PBC as a black box and achieves i) communication complexity of $O(L n^2 + n^3\kappa+\mathcal{P}(\kappa))$, where $\mathcal{P}(\kappa)$ is the communication complexity of the $\kappa$-bit PBC, and ii) round complexity same as the $\kappa$-bit PBC. By comparison, the state-of-the-art extension protocol for regular broadcast (Nayak et al., DISC 2020) incurs $O(n)$ additional rounds of communication. Next, we propose a protocol that is secure against a static adversary, for $\kappa$-bit messages with $O(n^2 \kappa^{1+K} + n\kappa^3 + \kappa^4)$ communication and $O(\kappa)$ round complexity, where $K$ is an arbitrarily small constant such that $0<K<1$. Finally, we propose an adaptively-secure protocol for $\kappa$-bit messages with $\tilde{O}(n^2\kappa^2 + n\kappa^3)$ communication overhead and $O(\kappa \log{n})$ round complexity. Notably, our latter two protocols are $\tilde{O}(\kappa^{2 - K})$ and $O(\kappa^2)$ times more communication-efficient, respectively, than the state-of-the-art protocols while achieving the same round complexity.

The Leftover Hash Lemma (LHL) is a powerful tool for extracting randomness from an entropic distribution, with numerous applications in cryptography. LHLs for discrete Gaussians have been explored in both integer settings by Gentry et al. (GPV, STOC'08) and algebraic ring settings by Lyubashevsky et al. (LPR, Eurocrypt'13). However, the existing LHLs for discrete Gaussians have two main limitations: they require the Gaussian parameter to be larger than certain smoothing parameters, and they cannot handle cases where fixed and arbitrary information is leaked. In this work, we present new LHLs for discrete Gaussians in both integer and ring settings. Our results show that the Gaussian parameter can be improved by a factor of $\omega(\sqrt{\log\lambda}) $ and $ O(\sqrt{N}) $ compared to the regularity lemmas of GPV and LPR, respectively, under similar parameter choices such as the dimension and ring. Furthermore, our new LHLs can be applied to leaked discrete Gaussians, and the result can be used to establish asymptotic hardness of the extended MLWE assumptions, addressing an open question in recent works by Lyubashevsky et al. (LNP, Crypto'22). Our central techniques involve new fine-grained analyses of the min-entropy in discrete Gaussians modulo sublattices and should be of interest.

While one-way functions (OWFs) serve as the minimal assumption for computational cryptography in the classical setting, in quantum cryptography, we have even weaker cryptographic assumptions such as pseudo-random states, and EFI pairs, among others. Moreover, the minimal assumption for computational quantum cryptography remains an open question. Recently, it has been shown that pseudoentanglement is necessary for the existence of quantum cryptography (Goulão and Elkouss 2024), but no cryptographic construction has been built from it. In this work, we study the cryptographic usefulness of quantum pseudoresources —a pair of families of quantum states that exhibit a gap in their resource content yet remain computationally indistinguishable. We show that quantum pseudoresources imply a variant of EFI pairs, which we call EPFI pairs, and that these are equivalent to quantum commitments and thus EFI pairs. Our results suggest that, just as randomness is fundamental to classical cryptography, quantum resources may play a similarly crucial role in the quantum setting. Finally, we focus on the specific case of entanglement, analyzing different definitions of pseudoentanglement and their implications for constructing EPFI pairs. Moreover, we propose a new cryptographic functionality that is intrinsically dependent on entanglement as a resource.

We present Boomy, a multivariate polynomial commitment scheme enabling the proof of the evaluation of multiple points, i.e., batch opening. Boomy is the natural extension of two popular protocols: the univariate polynomial commitment scheme of Kate, Zaverucha and Goldberg~\cite{AC:KatZavGol10} and its multivariate counterpart from Papamanthou, Shi and Tamassia~\cite{papamanthou2013signatures}. Our construction is proven secure under the selective security model. In this paper, we present Boomy's complexity and the applications on which it can have a significant impact. In fact, Boomy is perfectly suited to tackling blockchain data availability problems, shrinking existing challenges. We also present special lower-complexity cases that occur frequently in practical situations.

Privacy and security have become critical priorities in many scenarios. Privacy-preserving computation (PPC) is a powerful solution that allows functions to be computed directly on encrypted data. Garbled circuit (GC) is a key PPC technology that enables secure, confidential computing. GC comes in two forms: Boolean GC supports all operations by expressing functions as logic circuits; arithmetic GC is a newer technique to efficiently compute a set of arithmetic operations like addition and multiplication. Mixed GC combines both Boolean and arithmetic GC, in an attempt to optimize performance by computing each function in its most natural form. However, this introduces additional costly conversions between the two forms and it remains unclear if and when the efficiency gains of arithmetic GC outweigh these conversion costs. In this paper, we present Arithmetic Boolean Logic Exchange for Garbled Circuit, the first real implementation of mixed GC. ABLE profiles the performance of Boolean and arithmetic GC operations along with their conversions. We assess not only communication but also computation latency, a crucial factor in evaluating the end-to-end runtime of GC. Based on these insights, we propose a method to determine whether it is more efficient to use general Boolean GC or mixed GC for a given application. Rather than implementing both approaches to identify the better solution for each unique case, our method enables users to select the most suitable GC realization early in the design process. This method evaluates whether the benefits of transitioning operations from Boolean to arithmetic GC offset the associated conversion costs. We apply this approach to a neural network task as a case study. We propose an optimization to reduce the number of primes in arithmetic GC, cutting communication and compute latency by up to 14.1% and 15.7%, respectively. Additionally, we optimize mixed GC conversions with a row reduction technique, achieving a 48.6%reduction in garbled table size for bit-decomposition and a 50%reduction for bit-composition operation. Our code is open-sourced for community use.

A cryptographic compiler introduced by Kalai, Lombardi, Vaikuntanathan, and Yang (STOC’23) converts any nonlocal game into an interactive protocol with a single computa- tionally bounded prover. Although the compiler is known to be sound in the case of classical provers and complete in the quantum case, quantum soundness has so far only been established for special classes of games. In this work, we establish a quantum soundness result for all compiled two-player nonlocal games. In particular, we prove that the quantum commuting operator value of the underlying nonlocal game is an upper bound on the quantum value of the compiled game. Our result employs techniques from operator algebras in a computational and cryptographic setting to establish information-theoretic objects in the asymptotic limit of the security parameter. It further relies on a sequential characterization of quantum commuting operator correlations, which may be of independent interest.

The sponge is a cryptographic construction that turns a public permutation into a hash function. When instantiated with the Keccak permutation, the sponge forms the NIST SHA-3 standard. SHA-3 is a core component of most post-quantum public-key cryptography schemes slated for worldwide adoption. While one can consider many security properties for the sponge, the ultimate one is \emph{indifferentiability from a random oracle}, or simply \emph{indifferentiability}. The sponge was proved indifferentiable against classical adversaries by Bertoni et al. in 2008. Despite significant efforts in the years since, little is known about sponge security against quantum adversaries, even for simple properties like preimage or collision resistance beyond a single round. This is primarily due to the lack of a satisfactory quantum analog of the lazy sampling technique for permutations. In this work, we develop a specialized technique that overcomes this barrier in the case of the sponge. We prove that the sponge is in fact indifferentiable from a random oracle against quantum adversaries. Our result establishes that the domain extension technique behind SHA-3 is secure in the post-quantum setting. Our indifferentiability bound for the sponge is a loose $O(\mathsf{poly}(q) 2^{-\min(r, c)/4})$, but we also give bounds on preimage and collision resistance that are tighter.

Recent breakthroughs in cryptography have positioned indistinguishability obfuscation as a ``central hub'' for almost all known cryptographic tasks, and as an extremely powerful building block for new cryptographic tasks resolving long-standing and foundational open problems. However, constructions based on indistinguishability obfuscation almost always rely on non-black-box techniques, and thus the extent to which it can be used as a building block has been completely unexplored so far. We present a framework for proving meaningful negative results on the power of indistinguishability obfuscation. By considering indistinguishability obfuscation for oracle-aided circuits, we capture the common techniques that have been used so far in constructions based on indistinguishability obfuscation. These include, in particular, non-black-box techniques such as the punctured programming approach of Sahai and Waters (STOC '14) and its variants, as well as sub-exponential security assumptions. Within our framework we prove the first negative results on the power of indistinguishability obfuscation and of the tightly related notion of functional encryption. Our results are as follows: -- There is no fully black-box construction of a collision-resistant function family from an indistinguishability obfuscator for oracle-aided circuits. -- There is no fully black-box construction of a key-agreement protocol with perfect completeness from a private-key functional encryption scheme for oracle-aided circuits. Specifically, we prove that any such potential constructions must suffer from an exponential security loss, and thus our results cannot be circumvented using sub-exponential security assumptions. Our framework captures constructions that may rely on a wide variety of primitives in a non-black-box manner (e.g., obfuscating or generating a functional key for a function that uses the evaluation circuit of a puncturable pseudorandom function), and we only assume that the underlying indistinguishability obfuscator or functional encryption scheme themselves are used in a black-box manner.

Pulsars exhibit signals with precise inter-arrival times that are on the order of milliseconds to seconds, depending on the individual pulsar. There are subtle variations in the timing of pulsar signals. We show that these variations can serve as a natural entropy source for the creation of Random Number Generators (RNGs). We also explore the effects of using randomness extractors to increase the entropy of random bits extracted from Pulsar timing data. To evaluate the quality of the Pulsar RNG, we model its entropy as a $k$-source and use well-known cryptographic results to show its closeness to a theoretically ideal uniformly random source. To remain consistent with prior work, we also show that the Pulsar RNG passes well-known statistical tests such as the NIST test suite.

At FSE 2020, a linear distinguishing attack is presented against the ZUC-256 stream cipher based on the $32$-bit word with a data/time complexity of about $2^{236.38}$. In this paper, we re-evaluate the complexity of this attack and discuss the applicability of such a distinguishing attack in 5G application scenarios, where each keystream frame is limited to $20000$, and up to $2^{32}$ bits. To assure a high success probability close to $1$, it is shown that the precise time complexity of the distinguishing attack is $2^{253.93}$ basic operations with a data complexity of $2^{241.38}$ bits keystream, which is far beyond the keystream length limit in 5G application settings in the single-frame setting. Besides, we also consider the multiple-frame scenario where a long keystream could be formed by concatenating many short keystream frames generated from different (Key, IV) pairs. We show that even in such a strong model of distinguishing attacks, the reported bias will not exist in 5G application scenarios and the linear distinguishing attack will not work due to the fact that the long linear combination relation derived from the polynomial multiple of the LFSR in ZUC-256 over $\mbox{GF}(2^{31}-1)$, which has been verified in experiments. It is concluded that the ZUC-256 stream cipher offers the full $256$-bit security in 5G application scenarios.

ZUC-256 is a stream cipher, together with AES-256 and SNOW-V, proposed as the core primitive in future set of 3GPP confidentiality and integrity algorithms for the upcoming 5G applications which offer the 256-bit security. \\ While the original initialization scheme of ZUC-256 can work with a 256-bit key and an IV of length up to 184 bits, we describe a new initialization scheme of ZUC-256 that supports an IV of the exact 128 bits in this paper. Compared to the original initialization scheme, this new key/IV setup algorithm avoids the division of the whole key/IV byte and provides a simple and natural-looking initialization scheme for ZUC-256.

Succinct Non-Interactive Arguments of Knowledge (SNARKs) provide a powerful cryptographic framework enabling short, quickly verifiable proofs for computational statements. Existing SNARKs primarily target computations represented as arithmetic circuits. However, they become inefficient when handling binary operations, as each gates operates on a few bits while still incurring the cost of multiple field operations per gate. This inefficiency stems, in part, from their inability to capture the word-level operations that are typical in real-world programs. To better reflect this computational pattern, we shift our attention to data-parallel boolean circuits, which serve as a natural abstraction of word-level operations by allowing parallel munipulation of multiple bits. To precisely characterize the prover's overheads in our scheme, we adopt the word RAM model, which aligns with the nature of modern programming languages. Under this model, we propose a novel approach to achieve SNARKs with only sub-linear prover overhead for proving boolean circuits. Specifically, we present an optimized GKR protocol for boolean circuits that captures the word-level operations. To achieve this, we pack multiple bits as a single univariate polynomial, and exploiting the binary nature of circuit values to enable precomputation to accelerate the sumcheck process. This optimization leads to a highly efficient prover requiring only sub-linear RAM operations. Furthermore, we introduce a sub-linear polynomial commitment scheme designed specifically for binary polynomials, which ensures efficient commitments with minimal computational overhead. Comprehensive evaluations reveal that our scheme achieves both theoretical efficiency and substantial practical performance gains. For instance, in proving randomly generated Boolean circuits with $2^{30}$ gates, proof generation with our optimized GKR protocol completes in just 5.38 seconds, yielding a $223\times$ speedup over LogUp (Haböck, ePrint 2022), the most efficient known scheme for lookup arguments. Furthermore, in an end-to-end benchmark over the Keccak-$f$ task, our scheme achieves a $106\times$ speedup compared to Binius (Diamond et al., EUROCRYPT 2025), the state-of-the-art work for boolean circuits.

Private information retrieval (PIR) enables a client to retrieve data from a server while preserving the confidentiality of the client's query. When PIR is instantiated with fully homomorphic encryption (FHE), the protocol becomes non-interactive, requiring only a query-answer exchange, and it achieves asymptotically optimal communication and computation complexity. Although several FHE-based PIR protocols have been practically implemented with the desired properties, there has been little detailed comparison among them. As a result, it remains unclear which protocol is most efficient in practice with respect to various aspects such as performance and scalability. In this paper, we revisit existing protocols by categorizing them into two different structures in order to analyze the advantages and disadvantages of each class in detail, with a focus on practical implementations. Furthermore, we introduce and compare various homomorphic algorithms that can be utilized for query optimization, discussing the strengths and limitations of each. Finally, with the goal of identifying the most efficient protocol in terms of computational cost and memory usage, based on database size. Additionally, we address common misconceptions that may lead to inefficient choices in real-world deployment scenarios and offer the best solutions. Consequently, our analysis and experimental results demonstrate that the less-explored design achieves a 90% reduction in communication cost and an 8× decrease in computational overhead compared to the other one, challenging the common misconception.

Compared to elliptic curve cryptography, a primary drawback of lattice-based schemes is the larger size of their public keys and ciphertexts. A common procedure for compressing these objects consists essentially of dropping some of their least significant bits. Albeit effective for compression, there is a limit to the number of bits to be dropped before we get a noticeable decryption failure rate (DFR), which is a security concern. To address this issue, this paper presents a family of error-correction codes that, by allowing an increased number of dropped bits while preserving a negligible DFR, can be used for both ciphertext and public-key compression in modern lattice-based schemes. To showcase the impact and practicality of our proposal, we use the highly optimized ML-KEM, a post-quantum lattice-based scheme recently standardized by NIST. We provide detailed procedures for tailoring our codes to ML-KEM's specific noise distributions, and show how to analyze the DFR without independence assumptions on the noise coefficients. Among our results, we achieve between 4% and 8% ciphertext compression for ML-KEM. Alternatively, we obtain 8% shorter public keys compared to the current standard. We also present isochronous implementations of the decoding procedure, achieving negligible performance impact in the full ML-KEM decapsulation even when considering optimized implementations for AVX2, Cortex-M4, and Cortex-A53.

Confidential Computing-as-a-Service has gained significant attention in recent years, driven by rapid advances in Trusted Execution Environment (TEE) technology. Among various architectures, confidential serverless computing has emerged as a promising model. A common approach to designing confidential serverless computing involves decoupling the client workload from the initial enclave image and dynamically provisioning the workload at runtime. This enables both offloading the costly enclave bootstrapping and maintaining a fixed reference measurement for attestation. This decoupling necessitates nested attestation, where the client’s workload is attested via a custom attestation module embedded in a platform-attested enclave established at boot time. The challenge in designing nested attestation, however, is to distinguish fresh enclaves from the used ones to prevent enclave reuse. Specifically, a previously used enclave may be compromised and its attestation module tampered with. If the enclave is reused for another workload, it could bypass runtime attestation, allowing unverified code to execute. In this paper, we present a novel approach to securing nested attestation for confidential serverless computing on Intel Software Guard Extensions (Intel SGX). Unlike prior works, our approach does not rely on intra-enclave isolation techniques to sandbox the client’s workload. Instead, we leverage the Key Separation and Sharing (KSS) feature of Intel SGX to track and prevent enclave reuse based on its immutable IDs. We develop a prototype system for confidential serverless computing for Python workloads, incorporating our nested attestation scheme, and present an empirical evaluation of its performance. We believe our scheme unveils a unique yet previously overlooked role of KSS---post-compromise identification, with broader implications beyond serverless computing. As a concrete example, we demonstrate how KSS can be leveraged to implement an enclave-binding TPM on Intel SGX, which is of independent interest.