International Association
for Cryptologic Research

In recent years, unmanned aerial vehicles (UAVs) have shown great potential in logistics delivery due to their ability to bypass traffic congestion and adapt to complex terrains. Their high efficiency, low cost, and wide coverage make them a valuable supplement to last-mile logistics. However, third-party UAV systems operating in open environments are vulnerable to eavesdropping, tampering, and other cyber-attacks, which poses risks of sensitive information leakage. Meanwhile, warehouse nodes for sanitizing private information are widely deployed in logistics systems and need to be dynamically adjusted according to demand, which poses a challenges for the management of sanitization permissions. To address these issues, we propose a dynamic sanitizable signature with multiple sanitizers, enabling each sanitizer to independently sanitize sensitive information in signed messages, thus preserving logistics data privacy. Our scheme is applicable to UAV logistics scenarios and supports the addition and revocation of sanitizers without modifying existing keys, thereby enabling flexible and efficient permissions management. Security analysis shows that the proposed scheme ensures unforgeability, privacy preservation, and other security properties. A implementation on AmovLab Prometheus 600 UAVs demonstrates lower computational and communication overhead than existing privacy-preserving schemes, confirming its efficiency and practicality in UAV logistics systems.

It is well-known that evaluating a Boolean polynomial $f$ of any degree $d$ in $n$ variables over the full space $\mathbb F_2^n$ takes $n\cdot 2^n$ bit operations and $2^n$ bits of memory with standard Mobius transform. When $d$ is relatively small, Bouillaguet et al. proposed at CHES 2010 the fast exhaustive search (FES) algorithm. In this algorithm, by using Gray code to enumerate all elements in $\mathbb F_2^n$, evaluating $f$ on all inputs in $\mathbb F_2^n$ takes $\big(\sum_{i=0}^{d}\binom{n}{i}\big)^2+d\cdot 2^n=\binom{n}{\leq d}^2+d\cdot 2^n$ bit operations and $\binom{n}{\leq d}$ bits of memory. The term $\binom{n}{\leq d}^2$ represents the cost of the initialization phase. This problem has received new attention in recent years, which was studied by Dinur at EUROCRYPT 2021, by Furue and Takagi at PQCrypto 2023, and by Bouillaguet at TOMS 2024. All these algorithms work on the full space, and have a similar additional phase such as the initialization phase in the FES algorithm, which takes much more than $\binom{n}{\leq d}$ bit operations. In this work, we propose a simple yet efficient algorithm to evaluate $f$ over the structured space $P_{n_s}^{w_s}\times \cdots \times P_{n_1}^{w_1}\subseteq \mathbb F_2^n$ where $\sum_{i=1}^{s}n_i=n$ and $P_{n_i}^{w_i}$ denotes the set of $n_i$-bit binary strings with Hamming weight not larger than $w_i$. Our algorithm is inspired by the FES algorithm and Furue-Takagi's algorithm. However, our algorithm can work on a more general space, and is also distinguished by an efficient additional phase, which is simply reading all coefficients of $f$ and thus takes only $\binom{n}{\leq d}$ bit operations. For complexity, our algorithm takes $\binom{n}{\leq d}+d\cdot \Pi_{i=1}^{s}\binom{n_i}{\leq w_i}$ bit operations and consumes $(d+1)\cdot \binom{n}{\leq d}$ bits of memory. For applications, we prove that it is either infeasible or nontrivial to adapt the FES algorithm with monotone Gray code, which somehow answers a question raised by Dinur at EUROCRYPT 2021. Moreover, our algorithm provides a proven method to solve a critical step in Dinur's algorithm for the polynomial method, without affecting its time complexity. In particular, we also address the open problem proposed at TOMS 2024, and improve the polynomial evaluation algorithms even over the full space.

We develop a new method for the computation of $(3,3)$-isogenies between principally polarized abelian surfaces. The idea is to work with models in $\mathbb P^8$ induced by a symmetric level-$3$ theta structure. In this setting, the action of three-torsion points is linear, and the isogeny formulas can be described in a simple way as the composition of easy-to-evaluate maps. In the description of these formulas, the relation with the Burkhardt quartic threefold plays an important role. Furthermore, we discuss generalizations of the idea to higher dimensions as well as different isogeny degrees.

Secure multi-party computation (MPC) provides a promising approach for privacy-preserving machine learning (ML). Existing solutions generally fall into two categories but face scalability and efficiency limitations. Protocols based on Shamir secret sharing (SS) incur high communication costs, while those relying on packed Shamir secret sharing (PS) remain largely theoretical and often require costly secret routing, especially for complex ML tasks.

In this work, we propose a mixed secret sharing strategy that leverages PS sharing for non-linear layers with repeated and independent operations, and SS sharing for linear layers such as matrix multiplications. To efficiently support alternating linear and non-linear computations, we design generic conversions between SS and PS sharings and further integrate them into the corresponding ML protocols, thereby eliminating additional communication and computation overhead. Moreover, we develop efficient PS sharing-based protocols for primitive non-linear building blocks, which enable multiple non-linear operations to be executed with essentially the same communication cost as a single operation.

We implement our framework for secure multi-party ML inference and conduct extensive experiments. Compared to the SOTA work LXY24 (USENIX Security '24), our approach reduces communication by $3.6$-$6.1 \times$, while achieving $1.5$-$4.3 \times$ runtime improvement in the WAN setting and comparable or up to $2.3 \times$ better performance in the LAN setting.

Boolean functions having only one Walsh zero (or equivalently up to a translation, balanced functions whose sums with non-constant affine Boolean functions are all unbalanced) have been constructed for every n ≥ 10, by Mesnager and the first author, twenty years ago. This same paper had checked (partly mathematically and partly thanks to computer investigations) that no such function exists for n ≤ 6 but left open the question of constructing them for 7 ≤ n ≤ 9. Since then, functions in 7, 8 and 9 variables having one Walsh zero have been found by Lou and Wang, thanks to ad hoc methods combined with computer searches, but not as elements in infinite classes of functions having this property. In the present paper, we provide such infinite classes for n ≥ 8. For n = 7, we provide one more function (found by a computer investigation thanks to an algorithm) but we leave open the possibility of finding an infinite class valid for n ≥ 7. We also provide a secondary construction of functions with one Walsh zero in n + 2 variables from such functions in n variables, which does not need particular conditions on the latter for being successful (and which provides then a systematic way to obtain functions in n + 2 variables from functions in n variables). We investigate mathematical proofs of non-existence of such functions in n ≤ 6 variables.

With the advent of quantum computing, which threatens the very foundations of classical cryptography, several authenticated key exchange (AKE) protocols have been proposed, combining classical and post-quantum cryptographic algorithms, and a quantum key distribution (QKD) sub-protocol. The goal being to associate the claimed information theoretic security of QKD, and the security based upon computational assumptions of classical and post-quantum cryptography. To our knowledge, in existing security proofs of such hybrid AKE protocols, the QKD phase is treated as a black box and the impact of establishing the output quantum key appears similar as setting a symmetric key beforehand at the two communicating parties. In this paper, we describe an hybrid AKE protocol and a security model that captures multiple security properties. Our security analysis integrates the security loss induced by the QKD phase as well as that of implied by the classical and post-quantum cryptographic algorithms involved in the protocol.

This paper presents the first construction of adaptively secure non-interactive key exchange (NIKE) for an unbounded number of parties in the standard model. While prior unbounded protocols were restricted to static security or required random oracles, this work achieves adaptive security in the standard model. The proposed scheme supports an unbounded number of honest and malicious users, as well as unbounded party sizes, while tolerating a bounded number of dynamic user corruptions. The construction is based on sub-exponential indistinguishability obfuscation and sub-exponential fully-homomorphic encryption. A key technical contribution is a new application of what we call a function-extractable hash function. This is a variant of a function binding hash function that enables resilient extraction of properties from maliciously hashed digests.

Overhead costs associated with post quantum (PQ) algorithms, especially digital signatures, create a significant barrier to incorporation and adoption of post quantum cryptographic protocols in various settings. To counter this, the working group for the Messaging Layer Security (MLS) protocol under the Internet Engineering Task Force has proposed an approach where traditional and PQ sessions of the protocol are strategically combined in such a way as to amortize PQ-associated overhead, i.e., an Amortized Post Quantum (APQ) combiner. In this work, we implement and benchmark APQ using standardized NIST algorithms (ML-KEM and ML-DSA) integrated into OpenMLS with native Rust cryptographic libraries, presenting the first comprehensive performance evaluation of APQ to include PQ authenticity. Our evaluation encompasses execution run-time, message size, and memory consumption a cross various security levels and amortization ratios to compare and contrast MLS with traditional-only, APQ confidentiality-only, APQ confidentiality+authenticity, and an alternative hybrid ciphersuite. We demonstrate that APQ achieves exponential improvements in message size and memory efficiency as amortization traditional:PQ ratios decrease from 1:1 to 1:100, with optimal performance observed around 1:50 ratios. These findings establish APQ as a practical solution for deploying post quantum security in resource constrained settings.

Several works explored the use of discrete-logarithm-based zero-knowledge proof systems in order to prove the validity of Ring LWE ciphertexts and/or FHE ciphertexts. A technique suggested by del Pino {\it et al.} (PKC'19) notably enables proofs of $1$KB for the task of proving the validity of NewHope ciphertext using a variant of BulletProofs. A recent work of Libert (PKC'24) described a pairing-based adaptation of del Pino {\it et al.}'s approach with proofs of $3$ or $6$ group elements. While space-efficient, the latter solution is rather expensive in terms of proving time. In this work, we provide new NIZK arguments for the Ring-LWE-based public-key scheme proposed by Joye (CT-RSA'24), which is used in a variant of TFHE. The new schemes feature slightly longer proofs than in earlier pairing-based constructions with short proofs, but the prover is much faster. The number of exponentiations is reduced by a factor $\approx 7$ and the common reference string is compressed by a factor $\approx 9$ (and reduced to $1.5$MB for practically relevant parameters). We provide implementation results that confirm these estimations.

We introduce the Algebraic Isogeny Model (AIM): an algebraic model, akin to the Algebraic Group Model in the group setting, for isogenies and supersingular elliptic curves. This model is significantly more general than previous ones, such as the Algebraic Group Action Model: the AIM works with arbitrary isogenies over $\mathbb{F}_{p^2}$, rather than being limited to oriented ones, which gives considerably more power to the adversary. Within this model, we obtain three results. First, we show that any result in the AGAM can be lifted to the AIM, strengthening previous results against more powerful adversaries. Then, we prove that the SQIsign identification protocol is ID-sound: in turn, this implies that SQIsign is EUF-CMA secure in the Quantum Random Oracle Model, resolving (in the AIM) a long-standing open problem. Lastly, we establish the equivalence of the DLOG and CDH problems for all SIDH-derived key exchanges, such as M-SIDH, binSIDH, and terSIDH.

We study t-out-of-n threshold fully homomorphic encryption (ThFHE) in the synchronous setting, i.e., when the set of t decryptors is known at the outset of the decryption protocol. It has been observed in various works that the synchronous setting assumption enables to efficiently circumvent one of the major difficulties of ThFHE, namely hiding noise terms whose gigantic magnitude is incurred by the reconstruction coefficients of Shamir secret sharing. Yet, prior to this work, ThFHE in the synchronous setting had not even been properly defined. As a first contribution, we provide a clear syntax for ThFHE in the synchronous setting, as well as two security models: a weak model in which designating the set of decryptors is only viewed as an enabler of efficient decryption and it is fine for non-designated parties to be able to decrypt as long as there are sufficiently many of them; and a much stronger model where a set of decryptors which does not exactly match the designated set should not learn anything. Then, we show that the main existing schemes (Mouchet et al., Journal of Cryptology, 2023; Mouchet et al., ACM CCS, 2024) are insecure, even in the weak model, by describing efficient key-recovery attacks. Finally, we propose a simple and efficient construction which achieves security in the strong security model, by masking the partial decryption shares with pseudorandom functions.

Incremental preprocessing in private information retrieval (PIR) schemes refers to handle insertions, modifications, and deletions to the database without requiring complete preprocessing after each update. This broadens the applicability of PIR in practical scenarios. However, two major issues remain: the concept of incremental preprocessing for the single-server PIR is still not established, and the row-level update strategy (iSimplePIR (Row-level)) introduces excessive unnecessary overhead. This paper aims to efficiently extend incremental preprocessing to the single-server setting. To our knowledge, we are the first to propose the formal definition of single-server incremental PIR. Besides, we construct an entry-level incremental scheme (iSimplePIR (Entry-level)) based on SimplePIR (USENIX ’23). iSimplePIR (Entry-level) supports real-time updates of individual entries, as well as optimization of communication for scenarios with certain update cycles by incorporating a row aggregation mechanism. For a 1\% column-major update in a 1GB database, iSimplePIR (Entry-level) achieves a 224$\times$ reduction in preprocessing computation overhead and a 4.2$\times$ reduction in both communication and monetary costs compared to iSimplePIR (Row-level). When applied to password breach detection with completely random entry updates, iSimplePIR (Entry-level) reduces preprocessing time by 86$\times$. Our technique can be applied to reduce the preprocessing cost of any protocol in the SimplePIR family, such as DoublePIR, authenticated PIR (based on the LWE assumption), VeriSimplePIR, and YPIR.

Unbalanced private computation on set intersection (uPCSI) enables two parties to securely compute fine-grained functions over $X\cap Y$, where $|Y|\ll |X|$. Existing works proposed a uPCSI framework based on fully homomorphic encryption (FHE)-based private set intersection (PSI) protocols. However, their solutions face efficiency limitations, as they introduce an additional comparison procedure with a complexity of $\mathcal{O}(|Y|\log|X|)$.

In this paper, we present a lightweight uPCSI framework with semi-honest security. First, we propose a permuted multi-query private membership test (pmqPMT) protocol and its labeled variant from the FHE-based PSI, thereby avoiding the costly comparison procedure. Upon our pmqPMT, we propose an optimized uPCSI framework for computing arbitrary functions over the intersection, along with several specific optimizations for better efficiency. Besides, our framework can be extended to support more comprehensive labeled uPCSI requirements, covering both single-labeled and double-labeled cases. Compared to the state-of-the-art uPCSI protocols, we achieve over a $4.7\times$ online speedup and reduce communication costs by 15% on average.

Single Sign-On (SSO) protocols allow an identity provider to authenticate users and report the outcome by issuing identity attestations. Recent attacks show that breaching the identity provider infrastructure enables adversaries to issue arbitrary identity attestations and impersonate users. Survivable SSO protocols limit the risks of similar intrusions, but they have only been defined for password-based authentication, inheriting their limitations against powerful attacks such as credential phishing. While phishing-resistant passwordless authentication protocols have been standardized, they are not designed to guarantee intrusion tolerance. We initiate the research for Survivable Passwordless SSO (SPS) and propose a modular approach which includes the novel definition of Survivable Passwordless Challenge-response (SPC) protocols for authentication as a sub-routine of SSO. We give the first frameworks and game-based security definitions both for SPC and SPS which capture both novel attack classes, such as session injection attacks in a decentralized setting, and existing but not yet formalized attack classes, such as detection of cloned authenticators. The design of the models includes novel strategies to capture proactive security in survivable protocols within security definitions and to compose authentication and SSO through a modular approach. Our strategies and models may also be applied with minor modifications to non-survivable protocols, possibly providing a novel approach to assess the security of existing SSO protocols.

Fully Homomorphic Encryption (FHE) enables computations to be performed directly on encrypted data, without ever requiring decryption. This capability is particularly crucial for privacy-preserving outsourced computation in sensitive fields such as healthcare and finance. While FHE ensures data confidentiality under the honest-but-curious adversarial model, achieving full malicious security, encompassing both integrity and privacy, requires an additional layer of verifiability.

To address this, a growing body of research has explored combining FHE with techniques from verifiable computation, leading to the notion of verifiable FHE (vFHE). However, the integration of these two paradigms often results in substantial computational overhead, making existing approaches largely impractical for real-world deployment.

In this work, rather than targeting general-purpose verifiable FHE, we design a novel and practical verifiable homomorphic encryption scheme tailored for an important and widely used operation: matrix–vector multiplication. We provide an open-source implementation and our experimental results demonstrate that the proposed scheme achieves high efficiency, making it ready for practical adoption.

Masking is a principal countermeasure against side-channel attacks, yet its practical application is often hindered by its high randomness cost. While randomness reuse is a common efficiency strategy, securely managing the resulting algebraic dependencies without significant overhead has been a central challenge. Previous approaches have either resorted to injecting costly extra randomness to ensure compositional security in hardware, or remained confined to theoretical proposals with impractical latency costs. Critically, a systematic methodology to resolve randomness dependencies and achieve provable security at a practical cost has been lacking. This paper addresses the challenge by introducing the Unique Randomness Guard (URG) property as a foundational principle for secure masked circuit design. Building upon this property, we formally establish conditions under which the randomness in a circuit remains uniform and independent throughout its computation. Based on these results, we construct a general framework that provides a systematic methodology for randomness reuse, defined through a set of formally verified rules for both parallel and serial compositions. The security of these rules is guaranteed by the URG-based theoretical results, ensuring constructions that are first-order secure under the robust probing model. We also present a first-order masked implementation of the AES. To the best of our knowledge, this hardware implementation is the first to be proven first-order secure in the robust probing model while using only the randomness required for input encoding, all while maintaining a competitive hardware area. This work ultimately validate that randomness reuse can be fully realized without compromising rigorous verifiability, establishing a new framework that directly addresses the central challenge of randomness cost in masked implementations.

In many unbalanced private set intersection (uPSI) applications of the client-server setting, the server needs to perform uPSI with multiple clients. Cong \textit{et al.} (ACM CCS'21) proposed a state-of-the-art (SOTA) uPSI protocol based on fully homomorphic encryption (FHE), achieving malicious security by employing an oblivious pseudorandom function (OPRF) in the pre-processing phase. However, re-executing existing uPSI protocols with each client imposes significant computational overhead for the server. In this paper, we present JAGUAR, a maliciously secure and efficient uPSI protocol designed for this setting. JAGUAR reduces online computation through a Divide-and-Combine optimization, requiring only $\mathcal{O}(\sqrt{|X|})$ homomorphic multiplications. Furthermore, it employs a novel fixed VOLE-based OPRF that enables reusable and lightweight pre-processing across multiple clients. Experimental results demonstrate that JAGUAR achieves up to $2.7\times$ improvement in online runtime compared to the SOTA protocol in LAN. In multi-client scenarios, JAGUAR further outperforms existing protocols by a wide margin in terms of scalability and overall performance.

In this work, we present a new lightweight two-party Private Set Intersection (PSI) paradigm in both the semi-honest and malicious models. It requires only a small number of base Oblivious Transfers (OTs), along with a single Oblivious Key-Value Store (OKVS) encoding and a number of decodings equal to the sender input size. All computations (except for the base OTs) can be implemented using efficient hash and bitwise operations. Furthermore, we extend the proposed PSI protocol to circuit PSI and, subsequently, to several PSI variants, including PSI-cardinality, PSI-sum, and Private Join and Compute (PJC). All proposed protocols are evaluated under both LAN and WAN settings, with performance compared against existing works. Experimental results demonstrate that the proposed PSI achieves about $1.5 \times$ faster runtime than the most efficient Vector Oblivious Linear Evaluation (VOLE)-based PSI, while maintaining consistently lower communication overhead under identical settings. For circuit PSI, it is up to $3.6\times$ faster and reduces communication by a factor of $1.5$ compared to VOLE-based circuit PSI constructions. In the cases of PSI-cardinality and PSI-sum, they achieve speedups of up to $12.2\times$ and $10\times$, respectively, while incurring only moderate communication overhead. For PJC, the proposed protocol outperforms prior work by $731\times$ in runtime and achieves a $3.2\times$ reduction in communication, maintaining high efficiency even under a low-bandwidth condition. The performance under the unbalanced setting is also evaluated, showing that our PSI achieves at most two orders of magnitude improvement in the LAN setting compared with existing unbalanced PSI protocols, and gradually gains superiority under the WAN setting as the receiver set size increases.

Elliptic curve-based cryptographic systems have established themselves as fundamental components of modern cryptography, providing both efficiency and security guarantees. In this paper, we propose EHDSA (Elliptic Curve Homomorphic Digital Signature Algorithm), which addresses the privacy limitations inherent in classical ECDSA by introducing a novel isomorphism $\phi$ from the elliptic curve group $E(\mathbb{F}_p)$ to the integer ring $\mathbb{Z}_n$. Our approach utilizes a secret parameter $t \in \mathbb{Z}_n^*$ to define a scalar mapping that effectively obfuscates ephemeral public key components while maintaining the algebraic and homomorphic properties essential for signature verification. This transformation provides enhanced unlinkability and signature indistinguishability while preserving the computational efficiency of ECDSA. We provide formal security proofs under standard cryptographic assumptions, demonstrate correctness, and analyze computational complexity, showing that EHDSA achieves security levels equivalent to ECDSA with minimal computational overhead.

Attribute-based signatures (ABS) provide fine-grained control over who can generate digital signatures and have many real-world applications. This paper presents a pair of fast ABS schemes: one for Key-Policy ABS (KP-ABS) and another for Signature-Policy ABS (SP-ABS). Both schemes support expressive policies using Monotone Span Programs (MSP), and offer practical features such as large universe, arbitrary attributes, and adaptive security. Most notably, we provide the first implementation of MSP-based ABS schemes and demonstrate that our schemes achieve the best-known asymptotic and concrete performance in this domain. Asymptotically, key generation, signing and verification time scale linearly with the number of attributes; verification requires only two pairing operations. In concrete terms, for 100 attributes, our KP-ABS scheme performs key generation, signing, and verification in 0.16s, 0.10s, and 0.13s, respectively; our SP-ABS scheme achieves times of 0.082s, 0.26s, and 0.21s for the same operations.