All anonymous identity-based encryption (IBE) schemes that are group homomorphic (to the best of our knowledge) require knowledge of the identity to compute the homomorphic operation. This paper is motivated by this open problem, namely to construct an anonymous group-homomorphic IBE scheme that does not sacrifice anonymity to perform homomorphic operations. Note that even when strong assumptions such as indistinguishability obfuscation (iO) are permitted, no schemes are known. We succeed in solving this open problem by assuming iO and the hardness of the DBDH problem over rings (specifically, $Z_{N^2}$ for RSA modulus $N$). We then use the existence of such a scheme to construct an IBE scheme with re-randomizable anonymous encryption keys, which we prove to be IND-ID-RCCA secure. Finally, we use our results to construct identity-based anonymous aggregation protocols.

Higher order differential properties constitute a very insightful tool at the hands of a cryptanalyst allowing for probing a cryptographic primitive from an algebraic perspective. In FSE 2017, Saha et al. reported SymSum (referred to as SymSum_Vec in this paper), a new distinguisher based on higher order vectorial Boolean derivatives of SHA-3, constituting one of the best distinguishers on the latest cryptographic hash standard. SymSum_Vec exploits the difference in the algebraic degree of highest degree monomials in the algebraic normal form of SHA-3 with regards to their dependence on round constants. Later in Africacrypt 2020, Suryawanshi et al. extended SymSum_Vec using linearization techniques and in SSS 2023 also applied it to NIST-LWC finalist Xoodyak. However, a major limitation of SymSum_Vec is the maximum attainable derivative (MAD) which is less than half of the widely studied ZeroSum distinguisher. This is attributed to SymSum_Vec being dependent on m−fold vectorial derivatives while ZeroSum relies on m−fold simple derivatives. In this work we overcome this limitation of SymSum_Vec by developing and validating the theory of computing SymSum_Vec with simple derivatives. This gives us a close to 100% improvement in the MAD that can be computed. The new distinguisher reported in this work can also be combined with one/two-round linearization to penetrate more rounds. Moreover, we identify an issue with the two-round linearization claim made by Suryawanshi et al. which renders it invalid and also furnish an algebraic fix at the cost of some additional constraints. Combining all results we report SymSum_Sim , a new variant of the SymSum_Vec distinguisher based on m−fold simple derivatives that outperforms ZeroSum by a factor of $2^{257}$, $2^{129}$ for 10-round SHA-3-384 and 9-round SHA-3-512 respectively while enjoying the same MAD as ZeroSum. For every other SHA-3 variant, SymSum_Sim maintains an advantage of factor 2. Combined with one/two-round linearization, SymSum_Sim improves upon all existing ZeroSum and SymSum_Vec distinguishers on both SHA-3 and Xoodyak. As regards Keccak-p, the internal permutation of SHA-3, we report the best 15-round distinguisher with a complexity of $2^{256}$ and the first better than birthday-bound 16-round distinguisher with a complexity of $2^{512}$ (improving upon the 15/16-round results by Guo et al. in Asiacrypt 2016). We also devise the best full-round distinguisher on the Xoodoo internal permutation of Xoodyak with a practically verifiable complexity of $2^{32}$ and furnish the first third-party distinguishers on the Belarushian hash function Bash. All distinguishers furnished in this work have been verified through implementations whenever practically viable. Overall, with the MAD barrier broken, SymSum_Sim emerges as a better distinguisher than ZeroSum on all fronts and adds to the state-of-the-art of cryptanalytic tools investigating non-randomness of crypto primitives.

This technical note presents limits on the security (as a function of the number of plaintext bytes encrypted and the number of forgery attempts made by an adversary) for the main Authenticated Encryption schemes available in TLS 1.2 and the draft of TLS 1.3. These limits are derived from security proofs for the considered schemes available in the literature. Our intention is to provide considered technical input to on-going discussions in the TLS Working Group of the IETF concerning, amongst other things, the necessity of adding a key update feature to the TLS 1.3 specification.

Zero-Knowledge Proofs (ZKPs), a cryptographic tool known for decades, have gained significant attention in recent years due to advancements that have made them practically applicable in real-world scenarios. ZKPs can provide unique attributes, such as succinctness, non-interactivity, and the ability to prove knowledge without revealing the information itself, making them an attractive solution for a range of applications. This paper aims to critically analyze the applicability of ZKPs in various scenarios. We categorize ZKPs into distinct types: SNARKs (Succinct Non-Interactive Arguments of Knowledge), Commit-then-Prove ZKPs, MPC-in-the-Head, and Sigma Protocols, each offering different trade-offs and benefits. We introduce a flowchart methodology to assist in determining the most suitable ZKP system, given a set of technical application requirements. Next, we conduct an in-depth investigation of three major use cases: Outsourcing Computation, Digital Self-Sovereign Identity, and ZKPs in networking. Additionally, we provide a high-level overview of other applications of ZKPs, exploring their broader implications and opportunities. This paper aims to demystify the decision-making process involved in choosing the right ZKP system, providing clarity on when and how these cryptographic tools can be effectively utilized in various domains — and when they are better to be avoided.

Side-channel analysis (SCA) based on machine learning, particularly neural networks, has gained considerable attention in recent years. However, previous works predominantly focus on establishing connections between labels and related profiled traces. These approaches primarily capture label-related features and often overlook the connections between traces of the same label, resulting in the loss of some valuable information. Besides, the attack traces also contain valuable information that can be used in the training process to assist model learning. In this paper, we propose a profiled SCA approach based on contrastive learning named CL-SCA to address these issues. This approach extracts features by emphasizing the similarities among traces, thereby improving the effectiveness of key recovery while maintaining the advantages of the original SCA approach. Through experiments of different datasets from different platforms, we demonstrate that CL-SCA significantly outperforms other approaches. Moreover, by incorporating attack traces into the training process using our approach, we can further enhance its performance. This extension can improve the effectiveness of key recovery, which is fully verified through experiments on different datasets.

Differential privacy is a fundamental concept for protecting individual privacy in databases while enabling data analysis. Conceptually, it is assumed that the adversary has no direct access to the database, and therefore, encryption is not necessary. However, with the emergence of cloud computing and the «on-cloud» storage of vast databases potentially contributed by multiple parties, it is becoming increasingly necessary to consider the possibility of the adversary having (at least partial) access to sensitive databases. A consequence is that, to protect the on-line database, it is now necessary to employ encryption. At PoPETs'19, it was the first time that the notion of differential privacy was considered for encrypted databases, but only for a limited type of query, namely histograms. Subsequently, a new type of query, summation, was considered at CODASPY'22. These works achieve statistical differential privacy, by still assuming that the adversary has no access to the encrypted database. In this paper, we argue that it is essential to assume that the adversary may eventually access the encrypted data, rendering statistical differential privacy inadequate. Therefore, the appropriate privacy notion for encrypted databases that we use is computational differential privacy, which was introduced by Beimel et al. at CRYPTO '08. In our work, we focus on the case of functional encryption, which is an extensively studied primitive permitting some authorized computation over encrypted data. Technically, we show that any randomized functional encryption scheme that satisfies simulation-based security and differential privacy of the output can achieve computational differential privacy for multiple queries to one database. Our work also extends the summation query to a much broader range of queries, specifically linear queries, by utilizing inner-product functional encryption. Hence, we provide an instantiation for inner-product functionalities by proving its simulation soundness and present a concrete randomized inner-product functional encryption with computational differential privacy against multiple queries. In term of efficiency, our protocol is almost as practical as the underlying inner product functional encryption scheme. As evidence, we provide a full benchmark, based on our concrete implementation for databases with up to 1 000 000 entries. Our work can be considered as a step towards achieving privacy-preserving encrypted databases for a wide range of query types and considering the involvement of multiple database owners.

ZK-SNARKs, a fundamental component of privacy-oriented payment systems, identity protocols, or anonymous voting systems, are advanced cryptographic protocols for verifiable computation: modern SNARKs allow to encode the invariants of a program, expressed as an arithmetic circuit, in an appropriate constraint language from which short, zero-knowledge proofs for correct computations can be constructed. One of the most important computations that is run through SNARK systems is the verification of Merkle tree (MT) opening proofs, which relies on the evaluation of a fixed-input-length (FIL) cryptographic compression function over binary MTs. As classical, bit-oriented hash functions like SHA-2 are not compactly representable in SNARK frameworks, Arithmetization-Oriented (AO) cryptographic designs have emerged as an alternative, efficient solution. Today, the majority of AO compression functions are built from the Sponge permutation-based hashing mode. While this approach allows cost savings, compared to blockcipher-based modes, as it does not require key-scheduling, AO blockcipher schedulers are often cheap to compute. Furthermore, classical bit-oriented cryptography has long studied how to construct provably secure compression functions from blockciphers, following the Preneel-Govaerts-Vandewalle (PGV) framework. The potential efficiency gains together with the strong provable security foundations in the classic setting, motivate the study of AO blockcipher-based compression functions. In this work, we propose PGV-LC and PGV-ELC, two AO blockcipher-based FIL compression modes inspired by and extending the classical PGV approach, offering flexible input and output sizes and coming with provable security guarantees in the AO setting. We prove the collision and preimage resistance in the ideal cipher model, and give bounds for collision and opening resistance over MTs of arbitrary arity. We compare experimentally the PGV-ELC mode over the HADES blockcipher with its popular and widely adopted Sponge instantiation, Poseidon, and its improved variant Poseidon2. Our resulting constructions are up to 3× faster than Poseidon and 2× faster than Poseidon2 in native x86 execution, up to 1.5× faster in the Groth16 SNARK framework, and up to 1.9× faster in the Plonky2 framework. Finally, we study the benefits of using MTs of arity wider than two, proposing a new strategy to obtain a compact R1CS constraint system in such case. In fact, by combining an efficient parametrization of the HADES blockcipher over the PGV-ELC mode, together with an optimal choice of the MT arity, we measured an improvement of up to 9× in native MT construction time, and up to 2.5× in proof generation time, compared to Poseidon over binary MTs.

The rapid digitization of aviation communication and its dependent critical operations demand secure protocols that address domain-specific security requirements within the unique functional constraints of the aviation industry. These secure protocols must provide sufficient security against current and possible future attackers, given the inherent nature of the aviation community, that is highly complex and averse to frequent upgrades as well as its high safety and cost considerations. In this work we propose a pair of quantum-secure hybrid key exchange protocols (PQAG-KEM and PQAG-SIG) to secure communication between aircrafts in-flight and ground stations. PQAG-KEM leverages post-quantum and classical Key Encapsulation Mechanisms (KEMs) to ensure the hybrid security of the protocol against classical as well as future quantum adversaries. PQAG-SIG, alternatively, uses quantum-safe digital signatures to achieve authentication security. We provide an implementation of both PQAG-KEM and PQAG-SIG, and compare favourably with current state-of- the-art secure avionic protocols. Finally, we provide a formal analysis of our new PQAG protocols in a strong hybrid key exchange framework.

Masking, an effective countermeasure against side-channel attacks, is commonly applied in modern cryptographic implementations. Considering cryptographic algorithms that utilize both Boolean and arithmetic masking, the conversion algorithm between arithmetic masking and Boolean masking is required. Conventional high-order arithmetic masking to Boolean masking conversion algorithms based on Boolean circuits suffer from performance overhead, especially in terms of hardware implementation. In this work, we analyze high latency for the conversion and propose an improved high-order A2B conversion algorithm. For the conversion of 16-bit variables, the hardware latency can be reduced by 47% in the best scenario. For the case study of second-order 32-bit conversion, the implementation results show that the improved scheme reduces the clock cycle latency by 42% in hardware and achieves a 30% speed performance improvement in software. Theoretically, a security proof of arbitrary order is provided for the proposed high-order A2B conversion. Experimental validations are performed to verify the second-order DPA resistance of second-order implementation. The Test Vector Leakage Assessment does not observe side-channel leakage for hardware and software implementations.

Garbling schemes allow to garble a circuit $C$ and an input $x$ such that $C(x)$ can be computed while hiding both $C$ and $x$. In the context of adaptive security, an adversary specifies the input to the circuit after seeing the garbled circuit, so that one can pre-process the garbling of $C$ and later only garble the input $x$ in the online phase. Since the online phase may be time-critical, it is an interesting question how much information needs to be transmitted in this phase and ideally, this should be close to $|x|$. Unfortunately, Applebaum, Ishai, Kushilevitz, and Waters (AIKW, CRYPTO 2013) show that for some circuits, specifically PRGs, achieving online complexity close to $|x|$ is impossible with simulation-based security, and Hubáček and Wichs (HW, ITCS 2015) show that online complexity of maliciously secure two-party computation needs to grow with the incompressibility entropy of the function. We thus seek to understand under which circumstances optimal online complexity is feasible despite these strong lower bounds. Our starting point is the observation that lower bounds (only) concern cryptographic circuits and that, when an embedded secret is not known to the adversary (distinguisher), then the lower bound techniques do not seem to apply. Our main contribution is distributional simulation-based security (DSIM), a framework for capturing weaker, yet meaningful simulation-based (adaptive) security which does not seem to suffer from impossibility results akin to AIKW. We show that DSIM can be used to prove security of a distributed symmetric encryption protocol built around garbling. We also establish a bootstrapping result from DSIM-security for $\text{NC}^0$ circuits to DSIM-security for arbitrary polynomial-size circuits while preserving their online complexity.

The issue of data and information security on the internet and social network has become more serious and pervasive in recent years. Cryptography is used to solve security problems. However, message encryption cannot merely meet the intended goals because access control over the encrypted messages is required in some applications. To achieve these requirements, attribute-based encryption (ABE) is used. This type of encryption provides both security and access structure for the network users simultaneously. Fuzzy Identity-Based Encryption (FIBE) is a special mode of ABE that provides a threshold access structure for the users. This threshold value is set by the authority for users, which is always fixed and cannot be changed. So, the sender (encryptor) will not play a role in determining the threshold value. The mentioned issue exists also in Key Policy Attribute Based Encryption (KP-ABE) schemes. In this paper, we present a FIBE scheme in addition to the authority, the sender also plays a role in determining the threshold value. Thus, the policy will be more flexible than previous FIBE schemes in that the threshold value is selected only by the authority. We can call the proposed scheme a dual-policy ABE. The proposed technique for flexibility of threshold value can be applied in most of the existing KP-ABE schemes. We use the (indistinguishable) selective security model for security proof. The hardness assumption that we use is the modified bilinear decision Diffie-Hellman problem.

In today's systems, privacy is often at odds with utility: users that reveal little information about themselves get restricted functionality, and service providers mistrust them. In practice, systems tip to either full anonymity (e.g. Monero), or full utility (e.g. Bitcoin). Well-known cryptographic primitives for bridging this gap exist: anonymous credentials (AC) let users disclose a subset of their credentials' attributes, revealing to service providers "just what they need"; group signatures (GS) allow users to authenticate anonymously, to be de-anonymized "just when deemed necessary". However, these primitives are hard to deploy. Current AC and GS variants reach specific points in the privacy-utility tradeoff, which we point as counter-productive engineering-wise, as it requires full and error-prone re-engineering to adjust the tradeoff. Also, so far, GS and AC have been studied separately by theoretical research. We take the first steps toward unifying and generalizing both domains, with the goal of bringing their benefits to practice, in a flexible way. We give a common model capturing their core properties, and use functional placeholders to subsume intermediate instantiations of the privacy-utility tradeoff under the same model. To prove its flexibility, we show how concrete variants of GS, AC (and others, like ring signatures) can be seen as special cases of our scheme – to which we refer as universal anonymous signatures (UAS). In practice, this means that instantiations following our construction can be configured to behave as variant X of a GS scheme, or as variant Y of an AC scheme, by tweaking a few functions.

Fully Homomorphic Encryption offers an effective solution for privacy-preserving computation, but its adoption is hindered by substantial computational and communication overheads. To address these, the Hybrid Homomorphic Encryption (HHE) protocol was developed, where the client encrypts data using a symmetric encryption scheme (SE), and the server homomorphically evaluates its decryption. Previous studies have demonstrated that the HHE protocol has no impact on the correctness of applications; however, in this work, we shift the focus to its security resilience when subjected to Differential Fault Analysis (DFA). While DFA has proven effective against standalone symmetric-key primitives, no DFA study has been proposed that exploits the HHE protocol as a whole. Furthermore, previous DFA approaches on SE rely on strong assumptions such as nonce reuse, which limits their applicability in real-world protocols or practical applications. In this work, we show that the structure of the HHE protocol itself exposes new avenues for fault exploitation. We introduce Sasta-DFA, which, to our knowledge, is the first DFA targeting the HHE protocol in its entirety. Our study demonstrates that an attacker can achieve complete key recovery with a single fault injection. A key feature of this attack is that it does not require nonce reuse, thus adhering to nonce-related specifications. We adapt the IND-CPAD threat model proposed by Li and Micciancio at Eurocrypt’21 for HHE in the context of fault attacks. We conduct the first DFA study on the emerging HHE-specific integer-based SE schemes- Rubato, Hera, Pasta, and Masta. Notably, our attack methodology is generalizable and applicable to a broader class of HHE-friendly SE schemes, including boolean schemes like Rasta and even the standard scheme AES. We also present the first experimental validation of fault analysis on the new HHE-enabling schemes using ATXmega128D4-AU microcontroller. Finally, we extend Sasta-DFA to Authenticated Transciphering protocols under a weaker threat model that removes any functional dependency.

We present ReSolveD, a new candidate post-quantum signature scheme under the regular syndrome decoding (RSD) assumption for random linear codes, which is a well-established variant of the well-known syndrome decoding (SD) assumption. Our signature scheme is obtained by designing a new zero-knowledge proof for proving knowledge of a solution to the RSD problem in the recent VOLE-in-the-head framework using a sketching scheme to verify that a vector has weight exactly one. We achieve a signature size of 3.99 KB with a signing time of 27.3 ms and a verification time of 23.1 ms on a single core of a standard desktop for a 128-bit security level. Compared to the state-of-the-art code-based signature schemes, our signature scheme achieves $1.5\times \sim 2\times$ improvement in terms of the common "signature size + public-key size" metric, while keeping the computational efficiency competitive.

X-Wing is a hybrid key-encapsulation mechanism based on X25519 and ML-KEM-768. It is designed to be the sensible choice for most applications. The concrete choice of X25519 and ML-KEM-768 allows X-Wing to achieve improved efficiency compared to using a generic KEM combiner. In this paper, we introduce the X-Wing hybrid KEM construction and provide a proof of security. We show (1) that X-Wing is a classically IND-CCA secure KEM if the strong Diffie-Hellman assumption holds in the X25519 nominal group, and (2) that X-Wing is a post-quantum IND-CCA secure KEM if ML-KEM-768 is itself an IND-CCA secure KEM and SHA3-256 is secure when used as a pseudorandom function. The first result is proved in the ROM, whereas the second one holds in the standard model. Loosely speaking, this means X-Wing is secure if either X25519 or ML-KEM-768 is secure. We stress that these security gaurantees and optimizations are only possible due to the concrete choices that were made, and it may not apply in the general case.

Multiscalar multiplication on elliptic curves is used in wide cryptographic domains such as digital signatures, zero knowledge proofs, and verifiable computation, where it enables efficient and secure cryptographic protocols. In this work, we present two methods for optimizing multi scalar multiplication over elliptic curves. The first method is used when $3^d - 1$ points of the target curve can be stored. The second method is suitable for large values of $d$, where storing $3^d - 1$ points becomes infeasible. Our first method achieves up to $24\%$ better performance on elliptic curves with efficient tripling, speeding up ECDSA signing by $2.88\times$ and verification by $1.67\times$. The second method achieves an efficiency improvement of $11.34\%$ compared to the similar existing approach. These improvements are supported by operation counts and practical benchmarks.

We use theta groups to study $2$-isogenies between Kummer lines, with a particular focus on the Montgomery model. This allows us to recover known formulas, along with more efficient forms for translated isogenies, which require only $2S+2m_0$ for evaluation. We leverage these translated isogenies to build a hybrid ladder for scalar multiplication on Montgomery curves with rational $2$-torsion, which cost $3M+6S+2m_0$ per bit, compared to $5M+4S+1m_0$ for the standard Montgomery ladder.

As the message recovery-based attack poses a serious threat to lattice-based schemes, we conducted a study on the side-channel secu- rity of parallel implementations of lattice-based key encapsulation mech- anisms. Initially, we developed a power model to describe the power leakage during message encoding. Utilizing this power model, we pro- pose a multi-ciphertext message recovery attack, which can retrieve the required messages for a chosen ciphertext attack through a suitable mes- sage recovery oracle. Building upon the successful message recovery, we further develop a key recovery method based on a ciphertext-choosing strategy that maximizes key recovery accuracy, as well as a lattice reduc- tion attack capable of solving the whole private key from the target LWE instance. To assess the effectiveness of the attack, we conducted experi- ments using Kyber768 implemented on a Xilinx FPGA board. The exper- imental results demonstrate that our attack could successfully recover the private key with 9600 power traces and a computational complexity of 100 bikz, which is a significant advantage over existing attacks. Notably, our attack remains effective despite countermeasures such as masking and shuffling being implemented. This study reveals that parallel im- plementations remain vulnerable to side-channel attacks, and highlights the necessity of additional analysis and countermeasures for lattice-based schemes implemented in parallel.

Secure Multi-Party Computation (MPC) constructions typically allow computation over a finite field or ring. While useful for many applications, certain real-world applications require the usage of decimal numbers. While it is possible to emulate floating-point operations in MPC, fixed-point computation has gained more traction in the practical space due to its simplicity and efficient realizations. Even so, current protocols for fixed-point MPC still require computing a secure truncation after each multiplication gate. In this paper, we show a new paradigm for realizing fixed-point MPC. Starting from an existing MPC protocol over arbitrary, large, finite fields or rings, we show how to realize MPC over a residue number system (RNS). This allows us to leverage certain mathematical structures to construct a secure algorithm for efficient approximate truncation by a static and public value. We then show how this can be used to realize highly efficient secure fixed-point computation. In contrast to previous approaches, our protocol does not require any multiplications of secret values in the underlying MPC scheme to realize truncation but instead relies on preprocessed pairs of correlated random values, which we show can be constructed very efficiently, when accepting a small amount of leakage and robustness in the strong, covert model. We proceed to implement our protocol, with SPDZ as the underlying MPC protocol, and achieve significantly faster fixed-point multiplication.

Class groups of imaginary quadratic fields (class groups for short) have seen a resurgence in cryptography as transparent groups of unknown order. They are a prime candidate for being a trustless alternative to RSA groups because class groups do not need a (distributed) trusted setup to sample a cryptographically secure group of unknown order. Class groups have recently found many applications in verifiable secret sharing, secure multiparty computation, transparent polynomial commitments, and perhaps most importantly, in time-based cryptography, i.e., verifiable delay functions, (homomorphic) time-lock puzzles, timed commitments, etc. However, there are various roadblocks to making class groups widespread in practical cryptographic deployments. We initiate the rigorous study of hashing into class groups. Specifically, we want to sample a uniformly distributed group element in a class group such that nobody knows its discrete logarithm with respect to any public parameter. We point out several flawed algorithms in numerous publicly available class group libraries. We further illustrate the insecurity of these hash functions by showing concrete attacks against cryptographic protocols, i.e., verifiable delay functions, if they were deployed with one of those broken hash-to-class group functions. We propose two families of cryptographically secure hash functions into class groups. We implement these constructions and evaluate their performance. We release our implementation as an open-source library.

Recently, Qiu et al. proposed a semi-quantum voting scheme based on the ring signature (International Journal of Theoretical Physics, 60: 1550–1555(2021)), in which the signer and verifier only need measure the received particles with Z-basis and perform some classical simple encryption/decryption operations on the classical message. Although their scheme is very efficient, it cannot resist against the eavesdropping attacks and forgery attack. In this paper, first, the eavesdropping attacks on Qiu et al.’s scheme are proposed. Second, we show the forgery attack on their scheme. To overcome the security drawbacks of Qiu et al.’s protocol, the eavesdropping check technology should be considered.

Fully Homomorphic Encryption (FHE) is a prevalent cryptographic primitive that allows for computation on encrypted data. In various cryptographic protocols, this enables outsourcing computation to a third party while retaining the privacy of the inputs to the computation. However, these schemes make an honest-but-curious assumption about the adversary. Previous work has tried to remove this assumption by combining FHE with Verifiable Computation (VC). Recent work has increased the flexibility of this approach by introducing integrity checks for homomorphic computations over rings. However, efficient FHE for circuits of large multiplicative depth also requires non-ring computations called maintenance operations, i.e. modswitching and keyswitching, which cannot be efficiently verified by existing constructions. We propose the first efficiently verifiable FHE scheme that allows for arbitrary depth homomorphic circuits by utilizing the double-CRT representation in which FHE schemes are typically computed, and using lattice-based SNARKs to prove components of this computation separately, including the maintenance operations. Therefore, our construction can theoretically handle bootstrapping operations. We also present the first implementation of a verifiable computation on encrypted data for a computation that contains multiple ciphertext-ciphertext multiplications. Concretely, we verify the homomorphic computation of an approximate neural network containing three layers and more than 100 ciphertexts in less than 1 second while maintaining reasonable prover costs.

Verifiable secret sharing (VSS) protocols enable parties to share secrets while guaranteeing security (in particular, that all parties hold valid and consistent shares) even if the dealer or some of the participants are malicious. Most work on VSS focuses on the honest majority case, primarily since it enables one to guarantee output delivery (e.g., a corrupted recipient cannot prevent an honest dealer from sharing their value). Feldman's VSS is a well known and popular protocol for this task and relies on the discrete log hardness assumption. In this paper, we present a variant of Feldman's VSS for the dishonest majority setting and formally prove its security. Beyond the basic VSS protocol, we present a publicly-verifiable version, as well as show how to securely add participants to the sharing and how to refresh an existing sharing (all secure in the presence of a dishonest majority). We prove that our protocols are UC secure, for appropriately defined ideal functionalities.

The Learning With Errors ($\mathsf{LWE}$) problem asks to find $\mathbf{s}$ from an input of the form $(\mathbf{A}, \mathbf{b} = \mathbf{A}\mathbf{s}+\mathbf{e}) \in (\mathbb{Z}/q\mathbb{Z})^{m \times n} \times (\mathbb{Z}/q\mathbb{Z})^{m}$, for a vector $\mathbf{e}$ that has small-magnitude entries. In this work, we do not focus on solving $\mathsf{LWE}$ but on the task of sampling instances. As these are extremely sparse in their range, it may seem plausible that the only way to proceed is to first create $\mathbf{s}$ and $\mathbf{e}$ and then set $\mathbf{b} = \mathbf{A}\mathbf{s}+\mathbf{e}$. In particular, such an instance sampler knows the solution. This raises the question whether it is possible to obliviously sample $(\mathbf{A}, \mathbf{A}\mathbf{s}+\mathbf{e})$, namely, without knowing the underlying $\mathbf{s}$. A variant of the assumption that oblivious $\mathsf{LWE}$ sampling is hard has been used in a series of works to analyze the security of candidate constructions of Succinct Non interactive Arguments of Knowledge (SNARKs). As the assumption is related to $\mathsf{LWE}$, these SNARKs have been conjectured to be secure in the presence of quantum adversaries. Our main result is a quantum polynomial-time algorithm that samples well-distributed $\mathsf{LWE}$ instances while provably not knowing the solution, under the assumption that $\mathsf{LWE}$ is hard. Moreover, the approach works for a vast range of $\mathsf{LWE}$ parametrizations, including those used in the above-mentioned SNARKs. This invalidates the assumptions used in their security analyses, although it does not yield attacks against the constructions themselves.

Anonymous proofs of account ownership (anonymous PAOs) enable a prover to convince a verifier that the prover owns a valid account at a server without revealing their identity. Importantly, no server-side changes are required - the server does not even learn that such a proof is taking place. This functionality is particularly valuable in sensitive applications such as whistleblowing, or in settings where infrastructural changes at the server are impractical. Anonymous PAOs were first introduced by Wang et al. (IEEE S&P 2019), who realized them in the email setting via secure channel injection (SCI), a technique that requires carefully engineered multi-party computation (MPC) protocols. In this work, we propose YouChoose, a new approach to anonymous PAO that avoids MPC entirely, relying instead on the verifier to selectively forward TLS records. Compared to SCI, YouChoose is simpler, faster, and more adaptable across services. We also provide the first formal security definition for anonymous PAOs, establishing a rigorous framework for analysis and future constructions. Finally, we present a prototype implementation of YouChoose, evaluate it in the context of email and other social media accounts, showing its better performance than SCI with minimal latency overhead in practice.

A functional commitment allows a user to commit to an input $\mathbf{x} \in \{0,1\}^\ell$ and later open up the commitment to a value $y = f(\mathbf{x})$ with respect to some function $f$. In this work, we focus on schemes that support fast verification. Specifically, after a preprocessing step that depends only on $f$, the verification time as well as the size of the commitment and opening should be sublinear in the input length $\ell$, We also consider the dual setting where the user commits to the function $f$ and later, opens up the commitment at an input $\mathbf{x}$. In this work, we develop two (non-interactive) functional commitments that support fast verification. The first construction supports openings to constant-degree polynomials and has a shorter CRS for a broad range of settings compared to previous constructions. Our second construction is a dual functional commitment for arbitrary bounded-depth Boolean circuits. Both schemes are lattice-based and avoid non-black-box use of cryptographic primitives or lattice sampling algorithms. Security of both constructions rely on the $\ell$-succinct short integer solutions (SIS) assumption, a falsifiable $q$-type generalization of the SIS assumption (Preprint 2023). In addition, we study the challenges of extending lattice-based functional commitments to extractable functional commitments, a notion that is equivalent to succinct non-interactive arguments (when considering openings to quadratic relations). We describe a general methodology that heuristically breaks the extractability of our construction and provides evidence for the implausibility of the knowledge $k$-$R$-$\mathsf{ISIS}$ assumption of Albrecht et al. (CRYPTO 2022) that was used in several constructions of lattice-based succinct arguments. If we additionally assume hardness of the standard inhomogeneous SIS assumption, we obtain a direct attack on a variant of the extractable linear functional commitment of Albrecht et al.

Vector commitments (VC) and their variants attract a lot of attention due to their wide range of usage in applications such as blockchain and accumulator. Mercurial vector commitment (MVC), as one of the important variants of VC, is the core technique for building more complicated cryptographic applications, such as the zero-knowledge set (ZKS) and zero-knowledge elementary database (ZK-EDB). However, to the best of our knowledge, the only post-quantum MVC construction is trivially implied by a generic framework proposed by Catalano and Fiore (PKC '13) with lattice-based components which causes $\textit{large}$ auxiliary information and $\textit{cannot satisfy}$ any additional advanced properties, that is, updatable and aggregatable. A major difficulty in constructing a $\textit{non-black-box}$ lattice-based MVC is that it is not trivial to construct a lattice-based VC that satisfies a critical property called ``mercurial hiding". In this paper, we identify some specific features of a new falsifiable family of basis-augmented SIS assumption ($\mathsf{BASIS}$) proposed by Wee and Wu (EUROCRYPT '23) that can be utilized to construct the mercurial vector commitment from lattice $\textit{satisfying}$ updatability and aggregatability with $\textit{smaller}$ auxiliary information. We $\textit{first}$ extend stateless update and differential update to the mercurial vector commitment and define a $\textit{new}$ property, named updatable mercurial hiding. Then, we show how to modify our constructions to obtain the updatable mercurial vector commitment that satisfies these properties. To aggregate the openings, our constructions perfectly inherit the ability to aggregate in the $\mathsf{BASIS}$ assumption, which can break the limitation of $\textit{weak}$ binding in the current aggregatable MVCs. In the end, we show that our constructions can be used to build the various kinds of lattice-based ZKS and ZK-EDB directly within the existing framework.

Basic encryption and signature on lattices have comparable efficiency to their classical counterparts in terms of speed and key size. However, Identity-based Encryption (IBE) on lattices is much less efficient in terms of compactness, even when instantiated on ideal lattices and in the Random Oracle Model (ROM). This is because the underlying preimage sampling algorithm used to extract the users' secret keys requires huge public parameters. In this work, we specify a compact IBE instantiation for practical use by introducing various optimizations. Specifically, we first propose a modified gadget to make it more suitable for the instantiation of practical IBE. Then, by incorporating our gadget and the non-spherical Gaussian technique, we provide an efficient preimage sampling algorithm, based on which, we give a specification of a compact IBE on ideal lattice. Finally, two parameter sets and a proof-of-concept implementation are presented. Given the importance of the preimage sampling algorithm in lattice-based cryptography, we believe that our technique can also be applied to the practical instantiation of other advanced cryptographic schemes.

Blockchains suffer from scalability limitations, both in terms of latency and throughput. Various approaches to alleviate this have been proposed, most prominent of which are payment and state channels, sidechains, commit-chains, rollups, and sharding. This work puts forth a novel commit-chain protocol, Bitcoin Clique. It is the first trustless commit-chain that is compatible with all major blockchains, including (an upcoming version of) Bitcoin. Clique enables a pool of users to pay each other off-chain, i.e., without interacting with the blockchain, thus sidestepping its bottlenecks. A user can directly send its coins to any other user in the Clique: In contrast to payment channels, its funds are not tied to a specific counterparty, avoiding the need for multi-hop payments. An untrusted operator facilitates payments by verifiably recording them. Furthermore, we define and construct a novel primitive, Two-Shot Adaptor Signatures, which is needed for Bitcoin Clique while being of independent interest. This primitive extends the functionality of normal Adaptor Signatures by allowing the extraction of the witness only after two signatures are published on the blockchain.

Threshold signature schemes have gained prominence in enhancing the security and flexibility of digital signatures, allowing a group of participants to collaboratively create signatures while maintaining a predefined threshold of participants for validity. However, conventional threshold signatures treat all participants equally, lacking the capability to accommodate hierarchical structures often seen in real-world applications. Hierarchical Threshold Signature Schemes (HTSS) naturally extend the concept of simple threshold signatures, offering a solution that aligns with hierarchical organizational structures. Our paper introduces a novel, efficient, and flexible HTSS that employs independent polynomials at each hierarchical level, removing limitations on threshold values. This adaptability enables us to tailor the scheme to diverse requirements, whether signing requires only top-level nodes or lower-level participants' involvement. Based on our analysis, our FlexHi integrated into the FROST scheme outperforms Tassa's hierarchical scheme on FROST and operates approximately 30% to 40% faster, depending on the number of participants and the chosen threshold values. This demonstrates that, in addition to flexibility, our scheme has practical benefits through improved performance.

The size of the authentication tag represents a significant overhead for applications that are limited by bandwidth or memory. Hence, some authenticated encryption designs have a smaller tag than the required privacy level, which was also suggested by the NIST lightweight cryptography standardization project. In the ToSC 2022, two papers have raised questions about the IND-CCA security of AEAD schemes in this situation. These papers show that (a) online AE cannot provide IND-CCA security beyond the tag length, and (b) it is possible to have IND-CCA security beyond the tag length in a restricted Encrypt-then-Encipher framework. In this paper, we address some of the remaining gaps in this area. Our main result is to show that, for a fixed stretch, Pseudo-Random Injection security implies IND-CCA security as long as the minimum ciphertext size is at least as large as the required IND-CCA security level. We also show that this bound is tight and that any AEAD scheme that allows empty plaintexts with a fixed stretch cannot achieve IND-CCA security beyond the tag length. Next, we look at the weaker notion of MRAE security, and show that two-pass schemes that achieve MRAE security do not achieve IND-CCA security beyond the tag size. This includes SIV and rugged PRPs.

Attribute-Based Signature (ABS), introduced by Maji et al. (CT-RSA'11), is an advanced privacy-preserving signature primitive that has gained a lot of attention. Research on ABS can be categorized into three main themes: expanding the expressiveness of signing policies, enabling new functionalities, and providing more diversity in terms of computational assumptions. We contribute to the development of ABS in all three dimensions, by providing a fully dynamic ABS scheme for arbitrary circuits from codes. The scheme is the first ABS from code-based assumptions and also the first ABS system offering the \texttt{full dynamicity} functionality (i.e., attributes can be enrolled and revoked simultaneously). Moreover, the scheme features much shorter signature size than a lattice-based counterpart proposed by El Kaafarani and Katsumata (PKC'18). In the construction process, we put forward a new theoretical abstraction of Stern-like zero-knowledge (ZK) protocols, which are the major tools for privacy-preserving cryptography from codes. Our main insight here actually lies in the questions we ask about the fundamental principles of Stern-like protocols that have remained unchallenged since their conception by Stern at CRYPTO'93. We demonstrate that these long-established principles are not essential, and then provide a refined framework generalizing existing Stern-like techniques and enabling enhanced constructions.

New ideas to build homomorphic encryption schemes based on rational functions have been recently proposed. The starting point is a private-key encryption scheme whose secret key is a rational function $\phi/\phi'$. By construction, such a scheme is not homomorphic. To get homomorphic properties, nonlinear homomorphic operators are derived from the secret key. In this paper, we adopt the same approach to build HE. We obtain a multivariate encryption scheme in the sense that the knowledge of the CPA attacker can be turned into an over-defined system of nonlinear equations (contrarily to LWE-based encryptions). The factoring assumption is introduced in order to make a large class of algebraic attacks (based on Groebner bases) irrelevant. We extensively analyze the security of our scheme against algebraic attacks. In particular, we exhibit the fundamental role played by symmetry in these attacks. We also formally show that some of these attacks are exponential-time. While we did not propose a formal security proof relying on a classical cryptographic assumption, we hopefully provide convincing evidence for security.

To provide users with anonymous access to the Internet, onion routing and mix networks were developed. Assuming a stronger adversary than Tor, Sphinx is a popular packet format choice for such networks due to its efficiency and strong protection. However, it was recently shown that Sphinx is susceptible to a tagging attack on the payload in some settings. The only known packet formats which prevent this attack rely on advanced cryptographic primitives and are highly inefficient, both in terms of packet sizes and computation overhead. In this paper, we provide the first packet format that protects against the tagging attack with an acceptable overhead. At the cost of doubling the payload size, we are able to build a provably private solution from basic cryptographic primitives. Our implementation demonstrates that our solution is as computationally efficient as Sphinx, beating previous schemes by a large margin. For our security proof, we first strengthen the state-of-the-art proof strategy, before applying it to our solution to demonstrate that not only the tagging attack is prevented, but our scheme is provably private.

This paper conducts a comprehensive benchmarking analysis of the performance of two innovative cryptographic schemes: Homomorphic Polynomial Public Key (HPPK)-Key Encapsulation Mechanism (KEM) and Digital Signature (DS), recently proposed by Kuang et al. These schemes represent a departure from traditional cryptographic paradigms, with HPPK leveraging the security of homomorphic symmetric encryption across two hidden rings without reliance on NP-hard problems. HPPK can be viewed as a specialized variant of Multivariate Public Key Cryptography (MPKC), intricately associated with two vector spaces: the polynomial vector space for the secret exchange and the multivariate vector space for randomized encapsulation. The unique integration of asymmetric, symmetric, and homomorphic cryptography within HPPK necessitates a careful examination of its performance metrics. This study focuses on the thorough benchmarking of HPPK KEM and DS across key cryptographic operations, encompassing key generation, encapsulation, decapsulation, signing, and verification. The results highlight the exceptional efficiency of HPPK, characterized by compact key sizes, cipher sizes, and signature sizes. The use of symmetric encryption in HPPK enhances its overall performance. Key findings underscore the outstanding performance of HPPK KEM and DS across various security levels, emphasizing their superiority in crucial cryptographic operations. This research positions HPPK as a promising and competitive solution for post-quantum cryptographic applications in a wide range of applications, including blockchain, digital currency, and Internet of Things (IoT) devices.

NIST published FIPS 205 based on the specification of Sphincs$^{+}$. A formula to determine the security strength of a given parameter set is listed in SPHINCSsubmission31. It is quite complex to use that formula to get the security degradation behavior based on different increases in the number of signatures (called $2^{m}$ in this paper) per signing key. The task would become even more complex when we need to compare the security degradation characteristics of many parameter sets. In this paper, we provide a simpler formula to determine the security strengths of a given parameter set at various numbers of signatures produced by one signing key. With this new formula, the task of comparing parameter sets, especially, their security degradation characteristics become easy and that allowed us to search for best parameter sets for users to consider to use and for standard bodies to consider for standardization.

Recently, PT-symmetric systems have garnered significant attention due to their unconventional properties. Despite the growing interest, there remains an ongoing debate about whether these systems can outperform their Hermitian counterparts in practical applications, and if so, by what metrics this performance should be measured. We developed a novel PT-symmetric approach for mapping N = 3 pure qubit states to address this, implemented it using the dilation method, and demonstrated it on a superconducting quantum processor from the IBM Quantum Experience. For the first time, we derived exact expressions for the population of the post-selected PT-symmetric subspace for both N = 2 and N = 3 states. When applied to the discrimination of N = 2 pure states, our algorithm provides an equivalent result to the conventional unambiguous quantum state discrimination. For N = 3 states, our approach introduces novel capabilities not available in traditional Hermitian systems, enabling the transformation of an arbitrary set of three quantum states into another, at the cost of introducing an inconclusive outcome. Our algorithm has the same error rate for the attack on the three-state QKD protocol as the conventional minimum error, maximum confidence, and maximum mutual information strategies. For post-selection quantum metrology, our results provide precise conditions where PT-symmetric quantum sensors outperform their Hermitian counterparts in terms of information-cost rate. Combined with punctuated unstructured quantum database search, our method significantly reduces the qubit readout requirements at the cost of adding an ancilla, while maintaining the same average number of oracle calls as the original punctuated Grover's algorithm. This provides significant advantages for NISQ-era computers. Our work opens new pathways for applying PT symmetry in quantum communications, computing, and cryptography.

In order to provide access control on encrypted data, Attribute-based encryption (ABE) defines each user using a set of attributes. Fuzzy identity-based encryption (FIBE) is a variant of ABE that allows for a threshold access structure for users. To address the potential threat posed by future quantum computers, this paper presents a post-quantum fuzzy IBE scheme based on lattices. However, current lattice-based ABE schemes face challenges related to computational complexity and the length of ciphertext and keys. This paper aims to improve the performance of an existing fuzzy IBE scheme by reducing key length and computational complexity during the encryption phase. While negative attributes are not utilized in our scheme, we prove its security under the learning with error (LWE) hard problem assumption in the selective security model. These improvements have significant implications for the field of ABE.

Through tremendous efforts, the communication cost of secure multi-party computation (MPC) in the honest-majority setting has been significantly improved. In particular, the state-of-the-art honest-majority MPC protocol by Escudero et al. (CCS'22) takes 12 field elements in total per multiplication gate for arithmetic circuits in the online phase. However, it still requires $12 \log(5n/4)$ bits of online communication per AND gate for Boolean circuits. That is, for Boolean circuits, no MPC protocol with constant online communication is known. In this paper, we present an unconditionally secure MPC protocol for Boolean circuits in the honest-majority setting, which has constant online communication complexity and the offline communication complexity linear to the number $n$ of parties. We first describe the semi-honest MPC protocol and then show how to extend it to achieve malicious security, where the maliciously secure protocol has the same communication cost as the semi-honest protocol. In particular, our protocol achieves the amortized communication cost $36$ bits per AND gate in the online phase, $18n+24$ bits per AND gate in the offline phase. For those circuit wires that require routing, each wire incurs a communication overhead of $15n$ bits in the offline phase.

An accountable subgroup multi-signature (ASM) is a multi-signature that allows any subgroup of potential signers to jointly sign a message such that the subgroup of co-signers are accountable for the resulting signature and their identities are identifiable to any verifier. In this paper, we pro- pose a novel lattice-based accountable subgroup multi-signature scheme, i.e., vMS2, by combining the group setup method of recently proposed vASM scheme and Damgard et al.’s lattice-based MS2 multi-signature scheme. Key generation, signature generation and verification phases of our proposed scheme are almost identical to the MS2 scheme. In the group setup phase, we generate membership keys which is used for signing a message on behalf of a group G of users. These membership keys are generated via a joint verifiable secret sharing (VSS) scheme in a way that they include a piece of information from the secret keys of all users in G so that any subgroup of users in G having a valid membership key can sign in an accountable fashion. We also present a comparison of the underlying MS2 scheme and our accountable subgroup multi-signature scheme vMS2 to show the cost of accountability. We see that lattice-based accountable subgroup multi-signature scheme can be achieved by adding a one-time one-round group setup whose cost is slightly higher than signature generation and verification of the underlying MS2 signature scheme.

We show that the authentication scheme [Comput. Networks, 225 (2023), 109664] is flawed. (1) Some parameters are not specified. (2) Some computations are inconsistent. (3) It falsely require the control gateway to share its private key with the medical expert. (4) The scheme fails to keep user anonymity, not as claimed.

IDentity-based Password Authentication and Key Establishment (ID-PAKE) is an interesting trade-off between the security and efficiency, specially due to the removal of costly Public Key Infrastructure (PKI). However, we observe that previous PAKE schemes such as Beguinet et al. (ACNS 2023), Pan et al. (ASIACRYPT 2023) , Abdallah et al. (CRYPTO 2020) etc. fail to achieve important security properties such as weak/strong Perfect Forward Secrecy (s-PFS), user authentication and resistance to replay attack. In addition, to the best of our knowledge, no previous (P)AKE (either ID- based or PKI-based (P)AKEs) could achieve s-PFS with two-rounds of communication. In this paper, we propose a highly efficient ID-PAKE scheme with s-PFS and KGC-FS using only two rounds of communication, where each party only performs a single pairing operation. We compare our work with previous single pairing-based schemes i.e. Tomida et al. (ESORICS 2019) and Lian et al. (ESORICS 2020) and show that they suffer either s-PFS, KGC-FS attack and replay attack. In order to achieve a privacy-preserving PAKE scheme, we give a fix to Lian et al. (ESORICS 2020) in terms of KGC-FS and user authentication. We prove the security of our scheme under standard assumptions such as Discrete Logarithms (DL) and q-strong Diffie-Hellman(q-sDH) assumption in ID-eCK model. Finally, we conduct a proof-of-concept implementation of our scheme vs. previous single pairing-based schemes and show that our scheme imposes the least computation cost and stands in the middle of previous scheme regarding communication cost.

A Distributed Oblivious RAM is a multi-party protocol that securely implements a RAM functionality on secret-shared inputs and outputs. This paper presents two DORAMs in the semi-honest honest-majority 3-party setting which are information-theoretically secure and whose communication costs are asymptotic improvements over previous work. Let $n$ be the number of memory locations and let $d$ be the bit-length of each location. The first, MetaDORAM1, is \emph{statistically} secure, with $n^{-\omega(1)}$ leakage. It has $O(\log_b(n) d + b \omega(1) \log(n) + \log^3(n)/\log(\log(n)))$ bits of communication per memory access. Here, $b \geq 2$ is a free parameter and $\omega(1)$ is any super-constant function (in $n$). The best prior work was that of Abraham et al (PKC 2017), which has cost $O(\log_b(n) d + b \omega(1) \log_b(n) \log^2(n))$. MetaDORAM1 is an asymptotic improvement over the work of Abraham et al whenever $d = O(\log^2(n))$. The second protocol, MetaDORAM2, achieves \emph{perfect} security, albeit at the cost of a computationally-expensive setup phase. It has communication cost $O(\log_b(n)d + b \log(n) + \log^3(n)/\log(\log(n)))$. The best prior work of Chan et al (ASIACRYPT 2018) has communication cost $O(\log(n) d + \log^3(n))$. When $b = \log(n)$, the communication cost of our protocol is $O(\log(n) d /\log(\log(n)) + \log^3(n)/\log(\log(n)))$, that is a $\Theta(\log(\log(n)))$ factor improvement over that of Chan et al. Our work is the first perfectly secure DORAM with sub-logarithmic communication overhead. This comes at the cost of a once-off (for any given $n$) setup phase which requires exponential (in $n$) computation. By a trivial transformation, these can be transformed, respectively, into statistically and perfectly secure active multi-server ORAM protocols with the same communication costs. These multi-server ORAM protocols are likewise asymptotic improvements over the state of the art.

Since the existing tropical cryptographic protocols are either susceptible to the Kotov-Ushakov attack and its generalization, or to attacks based on tropical matrix periodicity and predictive behaviour, several attempts have been made to propose protocols that resist such attacks. Despite these attempts, many of the proposed protocols remain vulnerable to attacks targeting the underlying hidden problems, one of which we call the tropical two-sided discrete logarithm with shift. An illustrative case is the tropical Stickel protocol, which, when formulated with a single monomial instead of a polynomial, becomes susceptible to attacks based on solutions of the above mentioned tropical version of discrete logarithm. In this paper we will formally introduce the tropical two-sided discrete logarithm with shift, discuss how it is solved, and subsequently demonstrate an attack on a key exchange protocol based on the tropical semiring of pairs. This particular protocol is compromised due to the existence of efficient (albeit heuristic) solution of the tropical two-sided logarithm problem, and this highlights the ongoing challenges in search of a "good" key exchange protocol in tropical cryptography.

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

In post-quantum cryptography, permutations are frequently employed to construct cryptographic primitives. Careful design and implementation of sampling random unbiased permutations is essential for efficiency and protection against side-channel attacks. Nevertheless, there is a lack of systematic research on this topic. Our work seeks to fill this gap by studying the most prominent permutation sampling algorithms and assessing their advantages and limitations. We combine theoretical and experimental comparisons and provide a C library with the implementations of the algorithms discussed. Furthermore, we introduce a new sampling algorithm tailored for cryptographic applications.

Universal thresholdizer (UT) was proposed by Boneh et al. in CRYPTO'18 as a general framework for thresholdizing non-threshold cryptographic primitives where a set of $N$ servers, each gets a share such that any set of $k$ servers, each produces a partial result, which can be combined to generate the final result. In many applications of threshold cryptography such as the protection of private keys in a digital wallet, the combining operation of partial results must be protected. In this paper, we extend the UT framework to include password authentication for such protection. We formalize the notion of password protected universal thresholdizer (PPUT) that requires the knowledge of a password to execute the protocol, propose a general construction of PPUT, and prove its security. Our construction uses threshold password authenticated key exchange (TPAKE) with simulation-based security as one of the main building blocks. We define simulation-based security of TPAKE in stand-alone model and give a construction using threshold fully-homomorphic encryption. As an application of PPUT, we propose a new primitive called password protected threshold signature. All the proposed constructions are secure in the standard model, and can be instantiated from lattices.

We explore the possibility of obtaining general-purpose obfuscation for all circuits by way of making only simple, local, functionality preserving random perturbations in the circuit structure. Towards this goal, we use the additional structure provided by reversible circuits, but no additional algebraic structure. We start by formulating a new (and relatively weak) obfuscation task regarding the ability to obfuscate random circuits of bounded length. We call such obfuscators random input & output (RIO) obfuscators. We then show how to construct indistinguishability obfuscators for all (unbounded length) circuits given only an RIO obfuscator --- under a new assumption regarding the pseudorandomness of sufficiently long random reversible circuits with known functionality, which in turn builds on a conjecture made by Gowers (Comb. Prob. Comp. '96) regarding the pseudorandomness of bounded-size random reversible circuits. Furthermore, the constructed obfuscators satisfy a new measure of security - called random output indistinguishability (ROI) obfuscation - which is significantly stronger than IO and may be of independent interest. We then investigate the possibility of constructing RIO obfuscators using local, functionality preserving perturbations. Our approach is rooted in statistical mechanics and can be thought of as locally ``thermalizing'' a circuit while preserving its functionality. We provide candidate constructions along with a pathway for analyzing the security of such strategies. Given the power of program obfuscation, viability of the proposed approach would provide an alternative route to realizing almost all cryptographic tasks under hardness assumptions that are very different from standard ones. Furthermore, our specific candidate obfuscators are relatively efficient: the obfuscated version of an n-wire, m-gate (reversible) circuit with security parameter k has n wires and poly(n,k)m gates. We hope that our initial exploration will motivate further study of this alternative path to cryptography.

We study a fundamental problem in Multi-Party Computation, which we call the Multiple Millionaires’ Problem (MMP). Given a set of private integer inputs, the problem is to identify the subset of inputs that equal the maximum (or minimum) of that set, without revealing any further information on the inputs beyond what is implied by the desired output. Such a problem is a natural extension of the Millionaires’ Problem, which is the very first Multi- Party Computation problem that was presented in Andrew Yao’s seminal work [30 ]. A closely related problem is MaxP, in which the value of the maximum is sought. We study these fundamental problems and describe several algorithmic approaches and protocols for their solution. In addition, we compare the performance of the protocols under several selected settings. As applications of privacy-preserving computation are more and more commonly implemented in industrial systems, MMP and MaxP become important building blocks in privacy-preserving statistics, machine learning, auctions and other domains. One of the prominent advantages of the protocols that we present here is their simplicity. As they solve fundamental problems that are essential building blocks in various application scenarios, we believe that the presented solutions to those problems, and the comparison between them, will serve well future researchers and practitioners of secure distributed computing.

In this work we revisit the problem of using general-purpose MPC schemes to emulate the trusted dataholder in differential privacy (DP), to achieve the same accuracy but without the need to trust one single dataholder. In particular, we consider the two-party model where two computational parties (or dataholders), each with their own dataset, wish to compute a canonical DP mechanism on their combined data and to do so with active security. We start by remarking that available definitions of computational DP (CDP) for protocols are somewhat ill-suited for such a use-case, due to them either poorly capturing some strong security guarantees commonly given by general-purpose MPC protocols, or having too strict requirements in the sense that they need significant adjustment in order to be satisfiable by using common DP and MPC techniques. With this in mind, we propose a new version of simulation-based CDP, called SIM$^*$-CDP, and prove it to be stronger than the IND-CDP and SIM-CDP and incomparable to SIM$^+$-CDP. We demonstrate the usability of the SIM$^*$-CDP definition by showing how to satisfy it by the use of an available distributed protocol for sampling truncated geometric noise. Further, we use the protocol to compute two-party inner-products with CDP and active security, and with accuracy equal to that of the central model, being the first to do so. Finally, we provide an open-sourced implementation and benchmark its practical performance. Our implementation generates a truncated geometric sample in between about 0.035 and 3.5 seconds (amortized), depending on network and parameter settings, comparing favourably to existing implementations.

We present a general method to simplify soundness proofs under certain conditions. Given an adversary $\mathcal{A}$ able to break a scheme $S$ with non-negligible probability $t$, we define the concept of $\textit{trace}$ of a $\textit{winning configuration}$, which is already implicitly used in soundness proofs. If a scheme can be constructed that (1) takes a random configuration $e$, being the inputs and execution environment of $\mathcal{A}$, (2) "guesses" a trace, (3) modifies $e$ based on its guess so that the modified configuration $e'$ is statistically indistinguishable from the original one, (4) is then able to execute $\mathcal{A}$ correctly under the condition that $e'$ is a winning configuration and that $B$'s guess of the trace was correct, and finally (5) that during its execution $\mathcal{A}$ is unable extract any information about $B$'s guess, then the probability of $B$ winning can be expressed as a simple function of $t$ and the bit-length of the trace, namely $\frac{t}{2^m}$. Soundness then results if $2^m$ is polynomial in the security parameter. To illustrate the concept, a concrete application of this method to a simple binary voting scheme is then described in detail.

Efficient polynomial multiplication routines are critical to the performance of lattice-based post-quantum cryptography (PQC). As PQC standards only recently started to emerge, CPUs still lack specialized instructions to accelerate such routines. Meanwhile, deep learning has grown immeasurably in importance. Its workloads call for teraflops-level of processing power for linear algebra operations, mainly matrix multiplication. Computer architects have responded by introducing ISA extensions, coprocessors and special-purpose cores to accelerate such operations. In particular, Apple ships an undocumented matrix-multiplication coprocessor, AMX, in hundreds of millions of mobile phones, tablets and personal computers. Our work repurposes AMX to implement polynomial multiplication and applies it to the NTRU cryptosystem, setting new speed records on the Apple M1 and M3 systems-on-chip (SoCs): polynomial multiplication, key generation, encapsulation and decapsulation are sped up by $1.54$-$3.07\times$, $1.08$-$1.33\times$, $1.11$-$1.50\times$ and $1.20$-$1.98\times$, respectively, over the previous state-of-the-art.

Let n stands for the length of digital signatures with quadratic multivariate public rule in n variables. We construct postquantum secure procedure to sign O(n^t), t ≥1 digital documents with the signature of size n in time O(n^{3+t}). It allows to sign O(n^t), t <1 in time O(n^4). The procedure is defined in terms of Algebraic Cryptography. Its security rests on the semigroup based protocol of Noncommutative Cryptography referring to complexity of the decomposition of the collision element into composition into given generators. The protocol uses the semigroup of Eulerian transformations of variety (K*)^n where K* is a nontrivial multiplicative group of the finite commutative ring K. Its execution complexity is O(n^3). Additionally we use this protocol to define asymmetric cryptosystem with the space of plaintexts and ciphertexts (K*)^n which allows users to encrypt and decrypt O(n^t) documents of size n in time O(n^{3+[t]}) where [x] stands for the flow function from x. Finally we suggest protocol based cryptosystem working with plaintext space (K*)^n and the space of ciphertext K^n which allows decryption of O(n^t), t>1 documents of size n in time O(n^{t+3}), t>1. The multivariate encryption map has linear degree O(n) and density O(n^4). We discuss the idea of public key with Eulerian transformations which allows to sign O(n^t), t≥0 documents in time O(n^{t+2}). The idea of delivery and usage of several Eulerian and quadratic transformations is also discussed.

Homomorphic encryption enables public computation over encrypted data. In the past few decades, homomorphic encryption has become a staple of both the theory and practice of cryptography. Nevertheless, while there is a general loose understanding of what it means for a scheme to be homomorphic, to date there is no single unifying minimal definition that captures all schemes. In this work, we propose a new definition, which we refer to as combinatorially homomorphic encryption, which attempts to give a broad base that captures the intuitive meaning of homomorphic encryption and draws a clear line between trivial and nontrivial homomorphism. Our notion relates the ability to accomplish some task when given a ciphertext, to accomplishing the same task without the ciphertext, in the context of communication complexity. Thus, we say that a scheme is combinatorially homomorphic if there exists a communication complexity problem $f(x,y)$ (where $x$ is Alice's input and $y$ is Bob's input) which requires communication $c$, but can be solved with communication less than $c$ when Alice is given in addition also an encryption $E_k(y)$ of Bob's input (using Bob's key $k$). We show that this definition indeed captures pre-existing notions of homomorphic encryption and (suitable variants are) sufficiently strong to derive prior known implications of homomorphic encryption in a conceptually appealing way. These include constructions of (lossy) public-key encryption from homomorphic private-key encryption, as well as collision-resistant hash functions and private information retrieval schemes.

The existence of "unstructured" hard languages in $\mathsf{NP} \,\cap\,\mathsf{coNP}$ is an intriguing open question. Bennett and Gill (SICOMP, 1981) asked whether $\mathsf{P}$ is separated from $\mathsf{NP} \cap \mathsf{coNP}$ relative to a random oracle, a question that remained open ever since. While a hard language in $\mathsf{NP} \,\cap\,\mathsf{coNP}$ can be constructed in a black-box way from a one-way permutation, for which only few (structured) candidates exist, Bitansky et al. (SICOMP, 2021) ruled out such a construction based on an injective one-way function, an unstructured primitive that is easy to instantiate heuristically. In fact, the latter holds even with a black-box use of indistinguishability obfuscation. We give the first evidence for the existence of unstructured hard languages in $\mathsf{NP} \,\cap\,\mathsf{coNP}$ by showing that if $\mathsf{UP} \not \subseteq \mathsf{RP}$, which follows from the existence of injective one-way functions, the answer to Bennett and Gill's question is affirmative: with probability 1 over a random oracle $\cal O$, we have that $\mathsf{P}^{\cal O} \neq \mathsf{NP}^{\cal O} \cap \mathsf{coNP}^{\cal O}$. Our proof gives a constructive non-black-box approach for obtaining candidate hard languages in $\mathsf{NP} \,\cap\,\mathsf{coNP}$ from cryptographic hash functions. The above conditional separation builds on a new construction of non-interactive zero-knowledge (NIZK) proofs, with a computationally unbounded prover, to convert a hard promise problem into a hard language. We obtain such NIZK proofs for $\mathsf{NP}$, with a uniformly random reference string, from a special kind of hash function which is implied by (an unstructured) random oracle. This should be contrasted with previous constructions of such NIZK proofs that are based on one-way permutations or other structured primitives, as well as with (computationally sound) NIZK arguments in the random oracle model.

M. Dyakonov [IEEE Spectrum, 2019] asked: what precision is required for manipulating a quantum gate, and what role is the notion of ENERGY playing in quantum computing theory. We answer the questions by investigating the Quantum Fourier Transformation (QFT). We show that the precision for a qubit operation is no less than $4.72694\times 10^{-36}$, in accordance with the energy of a free particle. Quantum entanglement is indispensable to quantum supremacy. The present quantum computers have failed to instantiate quantum entanglement up to our expectation, due to inexact qubit operations. Quantum transition incurred during the transition of space-time continuum covertly changes qubits and corrupts quantum supremacy.

We present a new construction of cryptographically significant Boolean functions defined over a large number of variables, with an emphasis on efficient circuit realizability. Our method is based on a variant of the well-known Maiorana-McFarland (MM) construction, adapted to enable circuit structures with less than $6n$ gates on the number of input bits $n$. We evaluate the circuit efficiency in terms of the total number of logic gates (for example AND, OR, NOT, and XOR, each with a maximum fan-in of two) required to implement a given function. While prior studies have explored cryptographic parameters of such functions in theory, they often overlooked circuit-level efficiency, especially in high-dimensional settings. In this work, we construct a class of balanced functions with high nonlinearity, low absolute autocorrelation and high algebraic degree, yet realizable using a small number of logic gates. Towards application, this work provides additional design directions for cryptographic primitives in domains such as fault-resistant cryptography and homomorphic encryption, where both security and circuit efficiency at scale are critical. Further investigations are required towards actual hardware implementation of our proposed functions as well as to exploit them in concrete cipher designs.

The popularity of cloud computing has made outsourced databases prevalent in real-world applications. To protect data security, numerous encrypted outsourced databases have been proposed for this paradigm. However, the maintenance of encrypted databases has scarcely been addressed. In this paper, we focus on a typical maintenance task --- functional dependency (FD) discovery. We develop novel FD protocols in encrypted databases while guaranteeing minimal leakages: nothing is revealed besides the database size and the actual discovered FDs. As far as we know, we are the first to formally define secure FD discovery with minimal leakage. We present two oblivious FD protocols and prove them secure in the presence of the persistent adversary (monitoring processes on the server). The first protocol leverages Oblivious RAM (ORAM) and is suitable for dynamic databases. The second protocol relies on oblivious sorting and is more practical in static databases due to high parallelism. We also present a thorough experimental evaluation of the proposed methods.

In the wake of recent progress on quantum computing hardware, the National Institute of Standards and Technology (NIST) is standardizing cryptographic protocols that are resistant to attacks by quantum adversaries. The primary digital signature scheme that NIST has chosen is CRYSTALS-Dilithium. The hardness of this scheme is based on the hardness of three computational problems: Module Learning with Errors (MLWE), Module Short Integer Solution (MSIS), and SelfTargetMSIS. MLWE and MSIS have been well-studied and are widely believed to be secure. However, SelfTargetMSIS is novel and, though classically as hard as MSIS, its quantum hardness is unclear. In this paper, we provide the first proof of the hardness of SelfTargetMSIS via a reduction from MLWE in the Quantum Random Oracle Model (QROM). Our proof uses recently developed techniques in quantum reprogramming and rewinding. A central part of our approach is a proof that a certain hash function, derived from the MSIS problem, is collapsing. From this approach, we deduce a new security proof for Dilithium under appropriate parameter settings. Compared to the previous work by Kiltz, Lyubashevsky, and Schaffner (EUROCRYPT 2018) that gave the only other rigorous security proof for a variant of Dilithium, our proof has the advantage of being applicable under the condition $q = 1 \text{ mod } 2n$, where $q$ denotes the modulus and $n$ the dimension of the underlying algebraic ring. This condition is part of the original Dilithium proposal and is crucial for the efficient implementation of the scheme. We provide new secure parameter sets for Dilithium under the condition $q = 1 \text{ mod } 2n$, finding that our public key size and signature size are about $2.9\times$ and $1.3\times$ larger, respectively, than those proposed by Kiltz et al. at the same security level.

A monotone policy batch $\mathsf{NP}$ language $\mathcal{L}_{\mathcal{R}, P}$ is parameterized by a monotone policy $P \colon \{0,1\}^k \to \{0,1\}$ and an $\mathsf{NP}$ relation $\mathcal{R}$. A statement $(x_1, \ldots, x_k)$ is a YES instance if there exists $w_1, \ldots, w_k$ where $P(\mathcal{R}(x_1, w_1), \ldots, \mathcal{R}(x_k, w_k)) = 1$. For example, we might say that an instance $(x_1, \ldots, x_k)$ is a YES instance if a majority of the statements are true. A monotone policy batch argument (BARG) for $\mathsf{NP}$ allows a prover to prove that $(x_1, \ldots, x_k) \in \mathcal{L}_{\mathcal{R}, P}$ with a proof of size $\mathsf{poly}(\lambda, |\mathcal{R}|, \log k)$, where $\lambda$ is the security parameter, $|\mathcal{R}|$ is the size of the Boolean circuit that computes $\mathcal{R}$, and $k$ is the number of instances. Recently, Brakerski, Brodsky, Kalai, Lombardi, and Paneth (CRYPTO 2023) gave the first monotone policy BARG for $\mathsf{NP}$ from the learning with errors (LWE) assumption. In this work, we describe a generic approach for constructing monotone policy BARGs from any BARG for $\mathsf{NP}$ together with an additively homomorphic encryption scheme. This yields the first constructions of monotone policy BARGs from the $k$-$\mathsf{Lin}$ assumption in prime-order pairing groups as well as the (subexponential) DDH assumption in pairing-free groups. Central to our construction is a notion of a zero-fixing hash function, which is a relaxed version of a predicate-extractable hash function from the work of Brakerski et al. Our relaxation enables a direct realization of zero-fixing hash functions from BARGs for $\mathsf{NP}$ and additively homomorphic encryption, whereas the previous notion relied on leveled homomorphic encryption, and by extension, the LWE assumption. As an application, we also show how to combine a monotone policy BARG with a puncturable signature scheme to obtain a monotone policy aggregate signature scheme. Our work yields the first (statically-secure) monotone policy aggregate signatures that supports general monotone Boolean circuits from standard pairing-based assumptions. Previously, this was only known from LWE.

We investigate proof systems where security holds against rational parties instead of malicious ones. Our starting point is the notion of rational arguments, a variant of rational proofs (Azar and Micali, STOC 2012) where security holds against rational adversaries that are also computationally bounded. Rational arguments are an interesting primitive because they generally allow for very efficient protocols, and in particular sublinear verification (i.e. where the Verifier does not have to read the entire input). In this paper we aim at narrowing the gap between literature on rational schemes and real world applications. Our contribution is two-fold. We provide the first construction of rational arguments for the class of polynomial computations that is practical (i.e., it can be applied to real-world computations on reasonably common hardware) and with logarithmic communication. Techniques-wise, we obtain this result through a compiler from information-theoretic protocols and rational proofs for polynomial evaluation. The latter could be of independent interest. As a second contribution, we propose a new notion of extractability for rational arguments. Through this notion we can obtain arguments where knowledge of a witness is incentivized (rather than incentivizing mere soundness). We show how our aforementioned compiler can also be applied to obtain efficient extractable rational arguments for $\mathsf{NP}$.

In this paper, we study the design of efficient signature and public-key encryption (PKE) schemes in the presence of both leakage and tampering attacks. Firstly, we formalize the strong leakage and tamper-resilient (sLTR) security model for signature, which provides strong existential unforgeability, and deals with bounded leakage and restricted tampering attacks, as a counterpart to the sLTR security introduced by Sun et al. (ACNS 2019) for PKE. Then, we present direct constructions of signature and chosen-ciphertext attack (CCA) secure PKE schemes in the sLTR model, based on the matrix decisional Diffie-Hellman (MDDH) assumptions (which covers the standard symmetric external DH (SXDH) and k-Linear assumptions) over asymmetric pairing groups. Our schemes avoid the use of heavy building blocks such as the true-simulation extractable non-interactive zero-knowledge proofs (tSE-NIZK) proposed by Dodis et al. (ASIACRYPT 2010), which are usually needed in constructing schemes with leakage and tamper-resilience. Especially, our SXDH-based signature and PKE schemes are more efficient than the existing schemes in the leakage and tamper-resilient setting: our signature scheme has only 4 group elements in the signature, which is about 5×~8× shorter, and our PKE scheme has only 6 group elements in the ciphertext, which is about 1.3×~3.3× shorter. Finally, we note that our signature scheme is the {\it first} one achieving strong existential unforgeability in the leakage and tamper-resilient setting, where strong existential unforgeability has important applications in building more complex primitives such as signcryption and authenticated key exchange.

The Lightning Network (LN) is a second layer solution built on top of Bitcoin, aimed to solve Bitcoin's long transaction waiting times and high transaction fees. Empirical and theoretical studies show that the LN is tending towards the hub and spoke network topology. In this topology most of the nodes, the spokes, open a single channel to one of the few well-connected nodes, the hubs. This topology is known to be prone to failures, attacks, and privacy issues. In this work we introduce the Maypoles protocol in which most nodes open two channels instead of one. We show that this protocol benefits the network significantly by enhancing its stability, privacy, and resilience to attacks. We also examine the economic incentives of nodes to take part in Maypoles.

We find an efficient method to solve the semidirect discrete logarithm problem (SDLP) over finite nonabelian groups of order $p^3$ and exponent $p^2$ for certain exponentially large parameters. This implies an attack on SPDH-Sign, a signature scheme based on the SDLP, for such parameters. We also take a step toward proving the quantum polynomial time equivalence of SDLP and SCDH.

We survey various mathematical tools used in software works multiplying polynomials in \[ \frac{\mathbb{Z}_q[x]}{\left\langle {x^n - \alpha x - \beta} \right\rangle}. \] In particular, we survey implementation works targeting polynomial multiplications in lattice-based cryptosystems Dilithium, Kyber, NTRU, NTRU Prime, and Saber with instruction set architectures/extensions Armv7-M, Armv7E-M, Armv8-A, and AVX2. There are three emphases in this paper: (i) modular arithmetic, (ii) homomorphisms, and (iii) vectorization. For modular arithmetic, we survey Montgomery, Barrett, and Plantard multiplications. For homomorphisms, we survey (a) various homomorphisms such as Cooley--Tukey FFT, Good--Thomas FFT, Bruun's FFT, Rader's FFT, Karatsuba, and Toom--Cook; (b) various algebraic techniques for adjoining nice properties to the coefficient rings, including localization, Schönhage's FFT, Nussbaumer's FFT, and coefficient ring switching; and (c) various algebraic techniques related to the polynomial moduli, including twisting, composed multiplication, evaluation at $\infty$, truncation, incomplete transformation, striding, and Toeplitz matrix-vector product. For vectorization, we survey the relations between homomorphisms and vector arithmetic. We then go through several case studies: We compare the implementations of modular multiplications used in Dilithium and Kyber, explain how the matrix-to-vector structure was exploited in Saber, and review the design choices of transformations for NTRU and NTRU Prime with vectorization. Finally, we outline several interesting implementation projects.

The Fiat-Shamir transform is a classical technique for turning any zero-knowledge $\Sigma$-protocol into a signature scheme. In essence, the idea underlying this transform is that deriving the challenge from the digest of the commitment suppresses simulatability and hence provides non-interactive proofs of interaction. It follows from that observation that if one wishes to preserve deniability the challenge size (per round) must be kept low. For instance in the original Fiat-Shamir protocol the authors recommend 18 bits but suggest that the challenge size can be made larger to reduce communication overhead, e.g. the value of 20 is proposed in \cite{micali}. We show that even with relatively small challenge sizes \textsl{practical} deniability can be destroyed by having the verifier artificially impose upon himself the use of slowed-down hash function or by resorting to a trusted agency proposing an on-line deniability enforcement service against the provers community's will.

This paper introduces two designs of Sphinx variants with corresponding im- plementations for use in post-quantum threat models with a specific focus on Mix networks. We introduce an obvious variant of Sphinx with CSIDH/CTIDH and we additionally introduce ’KEM Sphinx’, an enhanced version of the Sphinx packet format, designed to improve performance through modifications that increase packet header size. Unlike its predecessor, KEM Sphinx addresses performance limitations inherent in the original design, offering a solution that doubles processing speed. Our analysis extends to the adaptation of KEM Sphinx in a post-quantum cryptographic context, showing a transition with minimal performance degradation. The study concludes that the trade-off be- tween increased size and improved speed and security is justifiable, especially in scenarios demanding higher security. These findings suggest KEM Sphinx as a promising direction for efficient, secure communication protocols in an increas- ingly post-quantum cryptographic landscape.

Applying the pothole method on the factors of numbers of the form $2^n-1$, we prove that if $2^n-1$ has carries of degree at most $$\kappa(2^n-1)=\frac{1}{2(1+c)}\lfloor \frac{\log n}{\log 2}\rfloor-1$$ for $c>0$ fixed, then the inequality $$\iota(2^n-1)\leq n-1+(1+\frac{1}{1+c})\lfloor\frac{\log n}{\log 2}\rfloor$$ holds for all $n\in \mathbb{N}$ with $n\geq 4$, where $\iota(\cdot)$ denotes the length of the shortest addition chain producing $\cdot$. In general, we show that all numbers of the form $2^n-1$ with carries of degree $$\kappa(2^n-1):=(\frac{1}{1+f(n)})\lfloor \frac{\log n}{\log 2}\rfloor-1$$ with $f(n)=o(\log n)$ and $f(n)\longrightarrow \infty$ as $n\longrightarrow \infty$ for $n\geq 4$ then the inequality $$\iota(2^n-1)\leq n-1+(1+\frac{2}{1+f(n)})\lfloor\frac{\log n}{\log 2}\rfloor$$ holds.

Since 2015, there has been a significant decrease in the asymptotic complexity of computing discrete logarithms in finite fields. As a result, the key sizes of many mainstream pairing-friendly curves have to be updated to maintain the desired security level. In PKC'20, Guillevic conducted a comprehensive assessment of the security of a series of pairing-friendly curves with embedding degrees ranging from $9$ to $17$. In this paper, we focus on pairing-friendly curves with embedding degrees of 10 and 14. First, we extend the optimized formula of the optimal pairing on BW13-310, a 128-bit secure curve with a prime $p$ in 310 bits and embedding degree $13$, to our target curves. This generalization allows us to compute the optimal pairing in approximately $\log r/2\varphi(k)$ Miller iterations, where $r$ and $k$ are the order of pairing groups and the embedding degree respectively. Second, we develop optimized algorithms for cofactor multiplication for $\mathbb{G}_1$ and $\mathbb{G}_2$, as well as subgroup membership testing for $\mathbb{G}_2$ on these curves. Based on these theoretical results a new 128-bit secure curve emerges: BW14-351. Finally, we provide detailed performance comparisons between BW14-351 and other popular curves on a 64-bit platform in terms of pairing computation, hashing to $\mathbb{G}_1$ and $\mathbb{G}_2$, group exponentiations and subgroup membership testings. Our results demonstrate that BW14-351 is a strong candidate for building pairing-based cryptographic protocols.

In this paper, we show a new set of cryptographic primitives that generically leads to chosen ciphertext secure (CCA secure) public-key encryption (PKE). Specifically, we show how a (non-interactive, publicly verifiable) batch argument (BARG) for NP can be combined with a chosen plaintext secure (CPA secure) PKE scheme to achieve a CCA secure one. The requirement of the succinctness of the proof size of a BARG used as a building block is arguably very mild: We require it to be only at most $(1 - \frac{1}{p(\lambda, n)}) \cdot k + q(\lambda, n) \cdot k^{\epsilon}$ for some non-negative constant $\epsilon < 1$ and polynomials $p, q$, where $\lambda$ denotes the security parameter, $n$ denotes the statement size, and $k$ denotes the batch size (i.e. the number of statements whose correctness is simultaneously proved), and thus it can even be (slightly) linear in $k$. A BARG with such succinctness is so weak that it cannot be used in the recent constructions of a non-interactive zero-knowledge proof system for NP based on a BARG (and a one-way function) by Bitansky et al. (STOC 2024) and Bradley, Waters, and Wu (TCC 2024). Therefore, our result gives a new building block that can upgrade CPA security into CCA security.

In this paper we propose a new hash-and-sign digital signature scheme whose security against existential forgery under adaptive chosen message attack is based on the hardness of full-distance syndrome decoding. We propose parameter sets for three security levels (128-bits, 192-bits, and 256-bits) based on concrete estimations for hardness of the syndrome decoding problem and estimate the corresponding sizes of the keys and the signature for each level. The scheme has large public and private keys but very small signatures.

We optimize the number-theoretic transforms (NTTs) in Dilithium — a digital signature scheme recently standardized by the National Institute of Standards and Technology (NIST) — on Cortex-M3 and 8-bit AVR. The core novelty is the exploration of micro-architectural insights for modular multiplications. Recent work [Becker, Hwang, Kannwischer, Yang and Yang, Volume 2022 (1), Transactions on Cryptographic Hardware and Embedded Systems, 2022] found a correspondence between Montgomery and Barrett multiplications by relating modular reductions to integer approximations and demonstrated that Barrett multiplication is more favorable than Montgomery multiplication by absorbing the subtraction to the low multiplication. We first point out the benefit of Barrett multiplication when long and high multiplication instructions are unavailable, unusable, or slow. We then generalize the notion of integer approximations and improve the emulation of high multiplications used in Barrett multiplication. Compared to the state-of-the-art assembly-optimized implementations on Cortex-M3, our constant-time NTT/iNTT are 1.38−1.51 times faster and our variable-time NTT/iNTT are 1.10−1.21 times faster. On our 8-bit AVR, we outperform Montgomery-based C implementations of NTT/iNTT by 6.37−7.27 times by simply switching to the proposed Barrett-based implementation. We additionally implement Barrett-based NTT/iNTT in assembly and obtain 14.10− 14.42 times faster code. For the overall scheme, we provide speed-optimized implementations for Dilithium parameter sets dilithium2 and dilithium3 on Cortex-M3, and stack-optimized implementations for all parameter sets on Cortex-M3 and 8-bit AVR. We briefly compare the performance of speed-optimized dilithium3. Compared to the state-of-the-art assembly implementation on Cortex-M3, our assembly implementation reduces the key generation, signature generation, and signature verification cycles by 2.30%, 23.29%, and 0.69%. In the 8-bit AVR environment, our Barrett-based C implementation reduces the key generation, signature generation, and signature verification cycles by 45.09%, 56.80%, and 50.40%, respectively, and our assembly-optimized implementation reduces the cycles of each operation by 48.85%, 61.70%, and 55.08%, respectively.

In a recent ePrint, Brown and Monico propose new attacks on the tropical signature scheme of Chen, Grigoriev and Shpilrain. This note provides a new countermeasures against those attacks. Thereby, we (temporarily?) shift the fire from the signature algorithm to redirect attacks on the key and on tropical polynomial factorization.

The semidirect discrete logarithm problem (SDLP) is the following analogue of the standard discrete logarithm problem in the semidirect product semigroup $G\rtimes \mathrm{End}(G)$ for a finite semigroup $G$. Given $g\in G, \sigma\in \mathrm{End}(G)$, and $h=\prod_{i=0}^{t-1}\sigma^i(g)$ for some integer $t$, the SDLP$(G,\sigma)$, for $g$ and $h$, asks to determine $t$. As Shor's algorithm crucially depends on commutativity, it is believed not to be applicable to the SDLP. Previously, the best known algorithm for the SDLP was based on Kuperberg's subexponential time quantum algorithm. Still, the problem plays a central role in the security of certain proposed cryptosystems in the family of $\textit{semidirect product key exchange}$. This includes a recently proposed signature protocol called SPDH-Sign. In this paper, we show that the SDLP is even easier in some important special cases. Specifically, for a finite group $G$, we describe quantum algorithms for the SDLP in $G\rtimes \mathrm{Aut}(G)$ for the following two classes of instances: the first one is when $G$ is solvable and the second is when $G$ is a matrix group and a power of $\sigma$ with a polynomially small exponent is an inner automorphism of $G$. We further extend the results to groups composed of factors from these classes. A consequence is that SPDH-Sign and similar cryptosystems whose security assumption is based on the presumed hardness of the SDLP in the cases described above are insecure against quantum attacks. The quantum ingredients we rely on are not new: these are Shor's factoring and discrete logarithm algorithms and well-known generalizations.

This paper reviews common attacks in classical cryptography and plausible attacks in the post-quantum era targeted at CRYSTALS-Kyber. Kyber is a recently standardized post-quantum cryptography scheme that relies on the hardness of lattice problems. Although it has undergone rigorous testing by the National Institute of Standards and Technology (NIST), there have recently been studies that have successfully executed attacks against Kyber while showing their applicability outside of controlled settings. The attacks discussed in the paper include common attacks, side-channel attacks, SCA-assisted CCA, and fault injections. In the common attacks section, attacks on symmetric primitives, multi-target attacks, and attacks exploiting decryption failures can all be deemed inviable, while recent data on attacks on module-LWE questions Kyber's security level. In the side-channel attacks section, timing attacks are proven useless due to the constant-time nature of Kyber, but SASCA attacks are still viable, though easily defended against with minimal drawbacks. Attacks targeting message encoding and attacks using deep learning, however, both prove effective, even with high-order masking. LDPC has also been proposed as a new framework for attack, proving itself potent with room for growth. In the SCA-assisted CCA section, EM attacks and CPA attacks have also both shown potential while remaining difficult to defend against. In the fault injection section, Roulette and error-tolerant key recovery have both recently been proposed, with data demonstrating their effectiveness and difficulty to defend against. This paper aims to provide future researchers insight into what areas should be focused on to strengthen current as well as future cryptosystems.

While many modern cryptographic primitives have stood the test of time, attackers started to expand beyond classic cryptanalysis by targeting implementations. Subversion attacks, where the attacker replaces the implementation of the cryptographic primitive to leak sensitive information about the user during a protocol execution, are among the most dangerous of such attacks. The revelations of Snowden have shown that these attacks are deployed by intelligence services. A very promising countermeasure uses cryptographic reverse firewalls that actively remove the covert channel leaking the secret. Chakraborty et al. (EUROCRYPT’22) presented the first model of such firewalls in the universal composability (UC) framework. However, using such a firewall also provides a possible new target for the attacker and in the case that an honest party uses a corrupted firewall, they were not able to prove any security guarantees. Furthermore, their model is quite complex and does not fit into the plain UC model as they restrict the environment. Hence, the authors needed to reprove fundamental theorems such as the composition theorem as well as the security of the underlying protocol. In this paper, we consider a slightly different model of subversion attacks that replace the used randomness, inspired by Dodis et al. (CRYPTO’16), that captures all known subversion attacks. Considering these realistic attacks allows us to use existing UC-secure protocols without the need to reprove their security. We also introduce additional notions of firewall properties, allowing us to reason about corrupted firewalls while maintaining strong security guarantees. To show the versatility of our model, we apply it to commitments and oblivious transfer. This demonstrates the usefulness of our plain UC model, as the only known previous subversion-resilient OT, recently provided by Chakraborty et al. (ASIACRYPT’24), is much more complicated and involved, and was also in the non-plain UC model.

We design and implement GigaDORAM, a novel 3-server Distributed Oblivious Random Access Memory (DORAM) protocol. Oblivious RAM allows a client to read and write to memory on an untrusted server while ensuring the server itself learns nothing about the client's access pattern. Distributed Oblivious RAM (DORAM) allows a group of servers to efficiently access a secret-shared array at a secret-shared index. A recent generation of DORAM implementations (e.g. FLORAM, DuORAM) has focused on building DORAM protocols based on Function Secret-Sharing (FSS). These protocols have low communication complexity and low round complexity but linear computational complexity of the servers. Thus, they work for moderate-size databases, but at a certain size, these FSS-based protocols become computationally inefficient. In this work, we introduce GigaDORAM, a hierarchical-solution-based DORAM featuring poly-logarithmic computation and communication, but with an over $100\times$ reduction in rounds per query compared to previous hierarchical DORAM protocols. In our implementation, we show that for moderate to large databases where FSS-based solutions become computation-bound, our protocol is orders of magnitude more efficient than the best existing DORAM protocols. When $N = 2^{31}$, our DORAM is able to perform over 700 queries per second.

Homomorphic encryption (HE) enables computation on encrypted data, which in turn facilitates the outsourcing of computation on private data. However, HE offers no guarantee that the returned result was honestly computed by the cloud. In order to have such guarantee, it is necessary to add verifiable computation (VC) into the system. The most efficient recent works in VC over HE focus on verifying operations on the ciphertext space of the HE scheme, which usually lacks the algebraic structure that would make it compatible with existing VC systems. For example, multiplication of ciphertexts in the current most efficient HE schemes requires non-algebraic operations such as real division and rounding. Therefore, existing works for VC over HE have to either give up on those efficient HE schemes, or incur a large overhead (an amount of constraints proportional to the ciphertext ring's size) in order to emulate these non-algebraic operations. In this work, we move away from that paradigm by placing the verification checks in the plaintext space of HE, all while the prover remains computing on ciphertexts. We achieve this by introducing a general transformation for Interactive Oracle Proofs (IOPs) to work over HE, whose result we denote as HE-IOPs. We apply this same transformation to the FRI [Ben-Sasson et al., ICALP 2018] IOP of proximity and we show how to compile HE-Reed Solomon-encoded IOPs and HE-$\delta$-correlated-IOPs with HE-FRI into HE-IOPs. Furthermore, our construction is compatible with a prover that provides input in zero-knowledge, and only relies on building blocks that are plausibly quantum-safe. Aligning the security parameters of HE and FRI is a difficult task for which we introduce several optimizations. We demonstrate their efficiency with a proof-of-concept implementation and show that we can run FRI's commit phase for 4096 encrypted Reed Solomon codewords with degree bound $2^{11}$ in just 5.4 seconds (using 32 threads) on a c6i.metal instance using less than 4GB of memory. Verification takes just 12.3 milliseconds (single-threaded) for the same parameter set and can be reduced to just 5.6ms with parameters optimized for the verifier.

Anonymous Zether, proposed by Bunz et al. (FC, 2020) and subsequently improved by Diamond (IEEE S&P, 2021) is an account-based confidential payment mechanism that works by using a smart contract to achieve privacy (i.e. identity of receivers to transactions and payloads are hidden). In this work, we look at simplifying the existing protocol while also achieving batching of transactions for multiple receivers, while ensuring consensus and forward secrecy. To the best of our knowledge, this work is the first to formally study the notion of forward secrecy in the setting of blockchain, borrowing a very popular and useful idea from the world of secure messaging. Specifically, we introduce: - FUL-Zether, a forward-secure version of Zether (Bunz et al., FC, 2020). - PRIvate DEcentralized Confidental Transactions (PriDe CT), a much-simplified version of Anonymous Zether that achieves competitive performance and enables batching of transactions for multiple receivers. - PRIvate DEcentralized Forward-secure Until Last update Confidential Transactions (PriDeFUL CT), a forward-secure version of PriDe CT. We also present an open-source, Ethereum-based implementation of our system. PriDe CT uses linear homomorphic encryption as Anonymous Zether but with simpler zero-knowledge proofs. PriDeFUL CT uses an updatable public key encryption scheme to achieve forward secrecy by introducing a new DDH-based construction in the standard model. In terms of transaction sizes, Quisquis (Asiacrypt, 2019), which is the only cryptocurrency that supports batchability (albeit in the UTXO model), has 15 times more group elements than PriDe CT. Meanwhile, for a ring of $N$ receivers, Anonymous Zether requires $6\log N$ more terms even without accounting for the ability to batch in PriDe CT. Further, our implementation indicates that, for $N=32$, even if there were 7 intended receivers, PriDe CT outperforms Anonymous Zether in proving time and gas consumption.

Predicate encryption (PE) is a type of public-key encryption that captures many useful primitives such as attribute-based encryption (ABE). Although much progress has been made to generically achieve security against chosen-plaintext attacks (CPA) efficiently, in practice, we also require security against chosen-ciphertext attacks (CCA). Because achieving CCA-security on a case-by-case basis is a complicated task, several generic conversion methods have been proposed, which typically target different subclasses of PE such as ciphertext-policy ABE. As is common, such conversion methods may sacrifice some efficiency. Notably, for ciphertext-policy ABE, all proposed generic transformations incur a significant decryption overhead. Furthermore, depending on the setting in which PE is used, we may also want to require that messages are signed. To do this, predicate signature schemes can be used. However, such schemes provide a strong notion of privacy for the signer, which may be stronger than necessary for some practical settings at the cost of efficiency. In this work, we propose the notion of predicate extension, which transforms the predicate used in a PE scheme to include one additional attribute, in both the keys and the ciphertexts. Using predicate extension, we can generically obtain CCA-security and signatures from a CPA-secure PE scheme. For the CCA-security transform, we observe that predicate extension implies a two-step approach to achieving CCA-security. This insight broadens the applicability of existing transforms for specific subclasses of PE to cover all PE. We also propose a new transform that incurs slightly less overhead than existing transforms. Furthermore, we show that predicate extension allows us to create a new type of signatures, which we call PE-based signatures. PE-based signatures are weaker than typical predicate signatures in the sense that they do not provide privacy for the signer. Nevertheless, such signatures may be more suitable for some practical settings owing to their efficiency or reduced interactivity. Lastly, to show that predicate extensions may facilitate a more efficient way to achieve CCA-security generically than existing methods, we propose a novel predicate-extension transformation for a large class of pairing-based PE, covered by the pair and predicate encodings frameworks. In particular, this yields the most efficient generic CCA-conversion for ciphertext-policy ABE.

SNARKs let a verifier check an expensive computation via a succinct proof, without re-executing the computation. However, many applications still verify proofs individually, creating verifier load and high fees in replicated or constrained-verifier settings. Existing proof aggregation schemes largely follow the generalized inner product argument (GIPA) line, achieving $O(\log n)$ proof size and verifier work for aggregating $n$ proofs, but remaining costly in practice and operating in batch mode. Rather than batching until a full window is available, we present SNARKMux, a streaming SNARK aggregation scheme that maintains a constant-size aggregate and requires $O(1)$ online verifier work per window of size $n$. Motivated by incremental verifiability, SNARKMux directly folds the Groth16 and Plonk verification relations and composes these proof-system-specific folds with Nova's circuit-layer fold; this defers expensive target-verifier logic (e.g., pairings) to the final check while keeping constant aggregator state. As part of public-input aggregation, we propose a generic instance-delegation technique: the prover aggregates instances, and the verifier performs a simple binding preprocessing costing only $O(n)$ hashes per window, after which online verification is constant-cost. Notably, our Groth16 and Plonk instantiations cover both circuit-specific and universal-setup SNARKs, with preprocessing that makes Plonk challenges folding-compatible, leading to a 0.7 KB Groth16 aggregate with 18 ms verification and a 0.5 KB Plonk one with 2 ms verification for 256 proofs.

The Fiat-Shamir transformation is a general principle to turn any public-coin interactive proof into non-interactive one (with security then typically analyzed in the random oracle model). While initially used for 3-round protocols, many recent constructions use it for multi-round protocols. However, in general the soundness error of the Fiat-Shamir transformed protocol degrades exponentially in the number of rounds. On the positive side, it was shown that for the special class of $(k_1,\dots,k_\mu)$-special-sound $\Sigma$-protocols, which is a natural multi-round generalization of the well-known class of special-sound protocols, the loss is actually only linear in the number of random oracle queries, and independent of the number of rounds, which is optimal. A natural next question is whether this positive result extends to the Fiat-Shamir transformation of so-called $(\Gamma_1,\dots,\Gamma_\mu)$-special-sound protocols. This notion was recently defined and analyzed in the interactive case; it captures a larger class of protocols, namely where the special-soundness property is characterized by a general access structure, rather than a threshold. We show in this work that this is indeed the case. Concretely, we show that the Fiat-Shamir transformation of any $(\Gamma_1, \ldots, \Gamma_\mu)$-special-sound interactive proof is knowledge sound under the same condition on $\Gamma_1,\dots,\Gamma_\mu$ for which the original interactive proof is knowledge sound. Furthermore, also here the loss is linear in the number of random oracle queries and independent of the number of rounds. In light of the above, one might suspect that our argument follows as a straightforward combination of the above mentioned prior works. However, this is not the case. The approach used for $(k_1,\dots,k_\mu)$-special-sound protocols, which is based on an extractor that samples without replacement, does not (seem to) generalize; on the other hand, the other approach, which uses an extractor based on sampling with replacement, comes with an additional loss that would blow up in the recursive multi-round analysis. Thus, new techniques are necessary to handle the above complications.

At EUROCRYPT 2017, Grassi et al. proposed the multiple-of-8 property for 5-round AES, where the number $n$ of right pairs is a multiple of 8. At ToSC 2019, Boura et al. generalized the multiple-of property for a general SPN block cipher and applied it to block cipher SKINNY. In this paper, we present that $n$ is not only a multiple but also a fixed value for SKINNY. Unlike the previous proof of generalization of multiple-of property using equivalence class, we investigate the propagation of the set to compute the exact number $n$. We experimentally verified that presented property holds. We extend this property one round more using the lack of the whitening key on the SKINNY and use this property to construct 6-round distinguisher on SKINNY-64 and SKINNY-128. The probability of success of both distinguisher is almost 1 and the total complexities are $2^{16}$ and $2^{32}$ respectively. We verified that this property only holds for SKINNY, not for AES and MIDORI, and provide the conditions under which it exists for AES-like ciphers.

HALFLOOP-96 is a 96-bit tweakable block cipher used in high frequency radio to secure automatic link establishment messages. In this paper, we concentrate on its differential properties in the contexts of conventional, related-tweak, and related-key differential attacks. Using automatic techniques, we determine the minimum number of active S-boxes and the maximum differential probability in each of the three configurations. The resistance of HALFLOOP-96 to differential attacks in the conventional and related-tweak configurations is good, and the longest distinguishers in both configurations consist of five rounds. In contrast, the security of the cipher against differential attacks in the related-key configuration is inadequate. The most effective related-key distinguisher we can find spans eight rounds. The 8-round related-key differential distinguisher is then utilised to initiate a 9-round weak-key attack. With $2^{92.96}$ chosen-plaintexts, 38.77-bit equivalent information about the keys can be recovered. Even though the attack does not pose a significant security threat to HALFLOOP-96, its security margin in the related-key configuration is exceedingly narrow. Therefore, improper use must be avoided in the application.

We introduce the notion of traceable mixnets. In a traditional mixnet, multiple mix-servers jointly permute and decrypt a list of ciphertexts to produce a list of plaintexts, along with a proof of correctness, such that the association between individual ciphertexts and plaintexts remains completely hidden. However, in many applications, the privacy-utility tradeoff requires answering some specific queries about this association, without revealing any information beyond the query result. We consider queries of the following types: a) given a ciphertext in the mixnet input list, whether it encrypts one of a given subset of plaintexts in the output list, and b) given a plaintext in the mixnet output list, whether it is a decryption of one of a given subset of ciphertexts in the input list. Traceable mixnets allow the mix-servers to jointly prove answers to the above queries to a querier such that neither the querier nor a threshold number of mix-servers learn any information beyond the query result. Further, if the querier is not corrupted, the corrupted mix-servers do not even learn the query result. We first comprehensively formalise these security properties of traceable mixnets and then propose a construction of traceable mixnets using novel distributed zero-knowledge proofs (ZKPs) of set membership and of a statement we call reverse set membership. Although set membership has been studied in the single-prover setting, the main challenge in our distributed setting lies in making sure that none of the mix-servers learn the association between ciphertexts and plaintexts during the proof. We implement our distributed ZKPs and show that they are faster than state-of-the-art by at least one order of magnitude.

Fuzzy extractors derive stable keys from noisy sources non-interactively (Dodis et al., SIAM Journal of Computing 2008). Since their introduction, research has focused on two tasks: 1) showing security for as many distributions as possible and 2) providing stronger security guarantees including allowing one to enroll the same value multiple times (reusability), security against an active attacker (robustness), and preventing leakage about the enrolled value (privacy). Existing constructions of reusable fuzzy extractors are direct and do not support as many distributions as the best non-reusable constructions. Constructions of robust fuzzy extractors require strong assumptions even in the CRS model. Given the need for progress on the basic fuzzy extractor primitive, it is prudent to seek generic mechanisms to transform a fuzzy extractor into one that is robust, private, and reusable so that it can inherit further improvements. This work asks if one can generically upgrade fuzzy extractors to achieve robustness, privacy, and reusability. We show positive and negative results: we show upgrades for robustness and privacy, but we provide a negative result on reuse. 1. We upgrade (private) fuzzy extractors to be robust under weaker assumptions than previously known in the common reference string model. 2. We show a generic upgrade for a private fuzzy extractor using multi-bit compute and compare (MBCC) obfuscation (Wichs and Zirdelis, FOCS 2017) that requires less entropy than prior work. 3. We show one cannot arbitrarily compose private fuzzy extractors. It is known one cannot reuse an arbitrary fuzzy extractor; each enrollment can leak a constant fraction of the input entropy. We show that one cannot build a reusable private fuzzy extractor by considering other enrollments as auxiliary input. In particular, we show that assuming MBCC obfuscation and collision-resistant hash functions, there does not exist a private fuzzy extractor secure against unpredictable auxiliary inputs strengthening a negative result of Brzuska et al. (Crypto 2014).

The first contribution of this work is a generalisation of Stern's information set decoding (ISD) algorithm. Stern's algorithm, a variant of Stern's algorithm due to Dumer, as well as a recent generalisation of Stern's algorithm due to Bernstein and Chou are obtained as special cases of our generalisation. Our second contribution is to introduce the notion of a set of effective time/memory trade-off (TMTO) points for any ISD algorithm for given ranges of values of parameters of the algorithm. Such a set succinctly and uniquely captures the entire landscape of TMTO points with only a minor loss in precision. We further describe a method to compute a set of effective TMTO points. As an application, we compute sets of effective TMTO points for the five variants of the Classic McEliece cryptosystem corresponding to the new algorithm as well as for Stern's, Dumer's and Bernstein and Chou's algorithms. The results show that while Dumer's and Bernstein and Chou's algorithms do not provide any interesting TMTO points beyond what is achieved by Stern's algorithm, the new generalisation that we propose provide about twice the number of effective TMTO points that is obtained from Stern's algorithm. Consequences of the obtained TMTO points to the classification of the variants of Classic McEliece in appropriate NIST categories are discussed.

Artificial intelligence (AI) is a modern technology that allows plenty of advantages in daily life, such as predicting weather, finding directions, classifying images and videos, even automatically generating code, text, and videos. Other essential technologies such as blockchain and cybersecurity also benefit from AI. As a core component used in blockchain and cybersecurity, cryptography can benefit from AI in order to enhance the confidentiality and integrity of cyberspace. In this paper, we review the algorithms underlying four prominent cryptographic cryptosystems, namely the Advanced Encryption Standard, the Rivest--Shamir--Adleman, Learning With Errors, and the Ascon family of cryptographic algorithms for authenticated encryption. Where possible, we pinpoint areas where AI can be used to help improve their security.

Succinctness and zero-knowledge are two fundamental properties in the study of cryptographic proof systems. Several recent works have formalized the connections between these two notions by showing how to realize non-interactive zero-knowledge (NIZK) arguments from succinct non-interactive arguments. Specifically, Champion and Wu (CRYPTO 2023) as well as Bitansky, Kamath, Paneth, Rothblum, and Vasudevan (ePrint 2023) recently showed how to construct a NIZK argument for NP from a (somewhere-sound) non-interactive batch argument (BARG) and a dual-mode commitment scheme (and in the case of the Champion-Wu construction, a local pseudorandom generator). The main open question is whether a BARG suffices for a NIZK (just assuming one-way functions). In this work, we first show that an adaptively-sound BARG for NP together with an one-way function imply a computational NIZK argument for NP. We then show that the weaker notion of somewhere soundness achieved by existing BARGs from standard algebraic assumptions are also adaptively sound if we assume sub-exponential security. This transformation may also be of independent interest. Taken together, we obtain a NIZK argument for NP from one-way functions and a sub-exponentially-secure somewhere-sound BARG for NP. If we instead assume plain public-key encryption, we show that a standard polynomially-secure somewhere-sound batch argument for NP suffices for the same implication. As a corollary, this means a somewhere-sound BARG can be used to generically upgrade any semantically-secure public-key encryption scheme into one secure against chosen-ciphertext attacks. More broadly, our results demonstrate that constructing non-interactive batch arguments for NP is essentially no easier than constructing NIZK arguments for NP.

We study digital signatures with revocation capabilities and show two results. First, we define and construct digital signatures with revocable signing keys from the LWE assumption. In this primitive, the signing key is a quantum state which enables a user to sign many messages and yet, the quantum key is also revocable, i.e., it can be collapsed into a classical certificate which can later be verified. Once the key is successfully revoked, we require that the initial recipient of the key loses the ability to sign. We construct digital signatures with revocable signing keys from a newly introduced primitive which we call two-tier one-shot signatures, which may be of independent interest. This is a variant of one-shot signatures, where the verification of a signature for the message ``0'' is done publicly, whereas the verification for the message ``1'' is done in private. We give a construction of two-tier one-shot signatures from the LWE assumption. As a complementary result, we also construct digital signatures with quantum revocation from group actions, where the quantum signing key is simply ``returned'' and then verified as part of revocation. Second, we define and construct digital signatures with revocable signatures from OWFs. In this primitive, the signer can produce quantum signatures which can later be revoked. Here, the security property requires that, once revocation is successful, the initial recipient of the signature loses the ability to find accepting inputs to the signature verification algorithm. We construct this primitive using a newly introduced two-tier variant of tokenized signatures. For the construction, we show a new lemma which we call the adaptive hardcore bit property for OWFs, which may enable further applications.

This paper introduces LERNA, a new framework for single-server secure aggregation. Our protocols are tailored to the setting where multiple consecutive aggregation phases are performed with the same set of clients, a fraction of which can drop out in some of the phases. We rely on an initial secret sharing setup among the clients which is generated once-and-for-all, and reused in all following aggregation phases. Compared to prior works [Bonawitz et al. CCS’17, Bell et al. CCS’20], the reusable setup eliminates one round of communication between the server and clients per aggregation—i.e., we need two rounds for semi-honest security (instead of three), and three rounds (instead of four) in the malicious model. Our approach also significantly reduces the server’s computational costs by only requiring the reconstruction of a single secret-shared value (per aggregation). Prior work required reconstructing a secret-shared value for each client involved in the computation. We provide instantiations of LERNA based on both the Decisional Composite Residuosity (DCR) and (Ring) Learning with Rounding ((R)LWR) assumptions respectively and evaluate a version based on the latter assumption. In addition to savings in round-complexity (which result in reduced latency), our experiments show that the server computational costs are reduced by two orders of magnitude in comparison to the state-of-the-art. In settings with a large number of clients, we also reduce the computational costs up to twenty-fold for most clients, while a small set of “heavy clients” is subject to a workload that is still smaller than that of prior work.

The splitting field $F$ of the polynomial $Y^n-2$ is an extension over $\mathbb{Q}$ generated by $\zeta_n=\exp(2 \pi \sqrt{-1} /n)$ and $\sqrt[n]{2}$. In this paper, we lay the foundation for applying the Order-LWE in the integral ring $\mathcal{R}=\mathbb{Z}[\zeta_n, \sqrt[n]{2}]$ to cryptographic uses when $n$ is a power-of-two integer. We explicitly compute the Galois group $\text{Gal}\left(F/\mathbb{Q} \right)$ and the canonical embedding of $F$, based on which we study the properties of the trace pairings of the integral basis $\zeta_n^{k_0} \sqrt[n]{2}^{k_1}$. Then we discuss the security of the Order-LWE in $\mathcal{R}$, and show that it offers the same security level as the RLWE in $\mathbb{Z}[X]/\langle X^{n^2/4} + 1 \rangle$. Moreover, we design a Two-Variable Number Theoretic Transform (2NTT) algorithm for the quotient $\mathcal{R}_p=\mathcal{R}/p\mathcal{R}$, where $p$ is a prime number such that $Y^n \equiv 2 \bmod p$ has $n$ distinct solutions. Compared to the one-variable NTT in $\mathbb{Z}[X]/\langle X^{n^2/4} + 1 \rangle$, a crucial advantage of 2NTT is that it enjoys a quadratic saving of twiddle factors. Hence, we can leverage this quadratic saving to boost the performance of 2NTT in practical implementations. At last, we also look at the applications of the Order-LWE in $\mathcal{R}$. In particular, we construct a new variant of CKKS for $\mathcal{R}$ and study its new properties.

In 1982, Yao introduced the problem of comparing two private values, thereby launching the study of protocols for secure multi-party computation (MPC). Since then, comparison protocols have undergone extensive study and found widespread applications. We survey state-of-the-art comparison protocols for an arbitrary number of parties, decompose them into smaller primitives and analyse their communication complexity under the usual assumption that the underlying MPC protocol does preprocessing and computes linear operations without communication. We then develop two new comparison protocols and explain why they are faster than similar protocols, including those that are commonly used in practice: they reduce the number of online multiplications, without increasing preprocessing or round complexity. More concretely, online bandwidth is reduced by more than half for the standard comparison protocols whose round complexity is logarithmic in the bit-length, whereas for constant round comparison protocols the reduction is two-thirds.

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

In recent years, actively secure SPDZ-like protocols for dishonest majority, like SPD$\mathbb Z_{2^k}$, Overdrive2k, and MHz2k, over base rings $\mathbb Z_{2^k}$ have become more and more efficient. In this paper, we present a new actively secure MPC protocol Multipars that outperforms these state-of-the-art protocols over $\mathbb Z_{2^k}$ by more than a factor of 2 in the two-party setup in terms of communication. Multipars is the first actively secure N-party protocol over $\mathbb Z_{2^k}$ that is based on linear homomorphic encryption (LHE) in the offline phase (instead of oblivious transfer or somewhat homomorphic encryption in previous works). The strong performance of Multipars relies on a new adaptive packing for BGV ciphertexts that allows us to reduce the parameter size of the encryption scheme and the overall communication cost. Additionally, we use modulus switching for further size reduction, a new type of enhanced CPA security over $\mathbb Z_{2^k}$, a truncation protocol for Beaver triples, and a new LHE-based offline protocol without sacrificing over $\mathbb Z_{2^k}$. We have implemented Multipars and therewith provide the fastest preprocessing phase over $\mathbb Z_{2^k}$. Our evaluation shows that Multipars offers at least a factor of 8 lower communication costs and up to a factor of 15 faster runtime in the WAN setting compared to the currently best available actively secure MPC implementation over $\mathbb Z_{2^k}$.

We present a side-channel attack on CRYSTALS-Dilithium, a post-quantum secure digital signature scheme, with two variants of post-processing. The side-channel attack exploits information leakage in the secret key unpacking procedure of the signing algorithm to recover the coefficients of the polynomials in the secret key vectors ${\bf s}_1$ and ${\bf s}_2$ by profiled deep learning-assisted power analysis. In the first variant, one half of the coefficients of ${\bf s}_1$ and ${\bf s}_2$ is recovered by power analysis and the rest is derived by solving a system of linear equations based on ${\bf t} = {\bf A}{\bf s}_1 + {\bf s}_2$, where ${\bf A}$ and ${\bf t}$ are parts of the public key. This case assumes knowledge of the least significant bits of the vector ${\bf t}$, ${\bf t}_0$. The second variant waives this requirement. However, to succeed, it needs a larger portion of ${\bf s}_1$ to be recovered by power analysis. The remainder of ${\bf s}_1$ is obtained by lattice reduction. Once the full ${\bf s}_1$ is recovered, all the other information necessary for generating valid signatures can be trivially derived from the public key. We evaluate both variants on an ARM Cortex-M4 implementation of Dilithium-2. The profiling stage (trace capture and neural network training) takes less than 10 hours. In the attack assuming that ${\bf t}_0$ is known, the probability of successfully recovering the full vector ${\bf s}_1$ from a single trace captured from a different from profiling device is non-negligible (9%). The success rate approaches 100% if multiple traces are available for the attack. Our results demonstrate the necessity of protecting the secret key of CRYSTALS-Dilithium from single-trace attacks and call for a reassessment of the role of compression of the public key vector ${\bf t}$ in the security of CRYSTALS-Dilithium implementations.

This paper studies a multi-party private set union (mPSU), a fundamental cryptographic problem that allows multiple parties to compute the union of their respective datasets without revealing any additional information. We propose an efficient mPSU protocol which is secure in the presence of any number of colluding semi-honest participants. Our protocol avoids computationally expensive homomorphic operations or generic multi-party computation, thus providing an efficient solution for mPSU. The crux of our protocol lies in the utilization of new cryptographic tool, namely, Membership Oblivious Transfer (mOT) . We believe that the mOT and cOPRF may be of independent interest. We implement our mPSU protocol and evaluate their performance. Our protocol shows an improvement of up to $80.84\times$ in terms of running time and $405.73\times$ bandwidth cost compared to the existing state-of-the-art protocols. *Note: June 2024 - Fixed a bug in the original version and simplified the protocol by removing the OPRF.

We study the following broad question about cryptographic primitives: is it possible to achieve security against an arbitrary $\mathsf{poly}(n)$-time adversary with $O(\log n)$-size messages? It is common knowledge that the answer is ``no'' unless information-theoretic security is possible. In this work, we revisit this question by considering the setting of cryptography with public information and computational security. We obtain the following results, assuming variants of well-studied intractability assumptions: 1) A private simultaneous messages (PSM) protocol for every $f:[n]\times[n]\to\{0, 1\}$ requiring $(1+\epsilon)\log n$-bit messages for most functions and $(2+\epsilon)\log n$-bit messages for the remaining ones. We apply this towards non-interactive secure 3-party computation with similar message size in the preprocessing model, improving over previous 2-round protocols. 2) A secret-sharing scheme for any ``forbidden-graph'' access structure on $n$ nodes with $O(\log n)$ share size. 3) On the negative side, we show that computational threshold secret-sharing schemes with public information require share size $\Omega(\log \log n)$. For arbitrary access structures, we show that computational security does not help with 1-bit shares. The above positive results guarantee that any adversary of size $n^{o(\log n)}$ achieves an $n^{-\Omega(1)}$ distinguishing advantage. We show how to make the advantage negligible by slightly increasing the asymptotic message size, still improving over all known constructions. The security of our constructions is based on the conjectured hardness of variants of the planted clique problem, which was extensively studied in the algorithms, statistical inference, and complexity theory communities. Our work provides the first applications of such assumptions improving the efficiency of mainstream cryptographic primitives, gives evidence for the necessity of such assumptions, and suggests new questions in this domain that may be of independent interest.

Recently, a novel secure quantum bit commitment (QBC) protocol has been proposed [29]. However, the protocol requires Alice and Bob to share Bell states in advance, making the protocol lacking in practicality. In this paper, we propose two new unconditionally secure quantum bit commitment protocols that do not require pre-shared Bell states based on entangled and non-entangled states, respectively. Their security stems from quantum mechanical properties such as quantum superposition, quantum entanglement, no-cloning theorem, and no-communication theorem. Furthermore, by combining the proposed QBC with Yao's quantum oblivious transfer (QOT) model, we can obtain an unconditionally secure QOT protocol.

A file system provides secure deletion if, after a file is deleted, an attacker with physical possession of the storage device cannot recover any data from the deleted file. Unfortunately, secure deletion is not provided by commodity file systems. Even file systems which explicitly desire to provide secure deletion are challenged by the subtleties of hardware controllers on modern storage devices; those controllers obscure the mappings between logical blocks and physical blocks, silently duplicate physical blocks, and generally make it hard for host-level software to make reliable assumptions about how file data is kept on the device. State-of-the-art frameworks for secure deletion also have no crash consistency, meaning that an ill-timed power outage or software fault will desynchonize keys and the associated encrypted file data, corrupting the file system. In this paper, we present Holepunch, a new software-level approach for implementing secure deletion. Holepunch treats the storage device as a black box, providing secure deletion via cryptographic erasure. Holepunch uses per-file keys to transparently encrypt outgoing file writes and decrypt incoming file reads, ensuring that all physical data in the storage device is always encrypted. Holepunch uses puncturable pseudorandom functions (PPRFs) to quickly access file keys; upon the deletion of file $f$, Holepunch updates the PPRF so that, even if the PPRF is recovered, the PPRF cannot be used to generate $f$'s key. By using PPRFs instead of the key trees leveraged by prior work, Holepunch reduces both the memory pressure caused by key management and the number of disk IOs needed to access files. Holepunch stores its master key in secure TPM storage, and uses a novel journaling scheme to provide crash consistency between TPM state and on-disk state.