International Association
for Cryptologic Research

Despite the notable advances in the development of high-assurance, verified implementations of cryptographic protocols, such implementations typically face significant performance overheads, particularly due to the penalties induced by formal verification and automated extraction of executable code. In this paper, we address some core performance challenges facing computer-aided cryptography by presenting a formal treatment for accelerating such verified implementations based on multiple generic optimizations covering parallelism and memory access. We illustrate our techniques for addressing such performance bottlenecks using the Line-Point Zero-Knowledge (LPZK) protocol as a case study. Our starting point is a new verified implementation of LPZK that we formalize and synthesize using EasyCrypt; our first implementation is developed to reduce the proof effort and without considering the performance of the extracted executable code. We then show how such (automatically) extracted code can be optimized in three different ways to obtain a 3000x speedup and thus matching the performance of the manual implementation of LPZK. We obtain such performance gains by first modifying the algorithmic specifications, then by adopting a provably secure parallel execution model, and finally by optimizing the memory access structures. All optimizations are first formally verified inside EasyCrypt, and then executable code is automatically synthesized from each step of the formalization. For each optimization, we analyze performance gains resulting from it and also address challenges facing the computer-aided security proofs thereof, and challenges facing automated synthesis of executable code with such an optimization.

We propose two generic constructions of public-key encryption (PKE) with tight simulation-based selective-opening security against chosen-ciphertext attacks (SIM-SO-CCA) in the random oracle model. Our constructions can be instantiated with a small constant number of elements in the ciphertext, ignoring smaller contributions from symmetric-key encryption. That is, they have compact ciphertexts. Furthermore, three of our instantiations have compact public keys as well. Known (almost) tightly SIM-SO-CCA secure PKE schemes are due to the work of Lyu et al. (PKC 2018) and Libert et al. (Crypto 2017). They have either linear-size ciphertexts or linear-size public keys. Moreover, they only achieve almost tightness, namely, with security loss depending on the security parameter. In contrast to them, our schemes are the first ones achieving both tight SIM-SO-CCA security and compactness. More precisely, our two generic constructions are: - From Pseudorandom KEM: Our first generic construction is from a key encapsulation mechanism (KEM) with pseudorandom ciphertexts against plaintext-checking attacks. Such a KEM can be constructed directly from the Strong Diffie-Hellman (StDH), Computational DH (CDH), and Decisional DH assumptions. Both their ciphertexts and public keys are compact. Their security loss is a small constant. Interestingly, our CDH-based construction is the first scheme achieving all these advantages based on a weak search assumption. Furthermore, we also give a generic construction of such a KEM, which yields an efficient tightly SIM-SO-CCA PKE from lattices. - From Lossy Encryption: Our second scheme is the well-known Fujisaki-Okamoto transformation. We show that it can turn a lossy encryption scheme into a tightly SIM-SO-CCA secure PKE. This transformation preserves both tightness and compactness of the underlying lossy encryption, which is in contrast to the non-tight proof of Heuer et al. (PKC 2015).

Machine learning is a widely-used tool for analysing large datasets, but increasing public demand for privacy preservation and the corresponding introduction of privacy regulations have severely limited what data can be analysed, even when this analysis is for societal benefit. Homomorphic encryption, which allows computation on encrypted data, is a natural solution to this dilemma, allowing data to be analysed without sacrificing privacy. Because homomorphic encryption is computationally expensive, however, current solutions are mainly restricted to use it for inference and not training.

In this work, we present a practically viable approach to privacy-preserving machine learning training using fully homomorphic encryption. Our method achieves fast training speeds, taking less than 45 seconds to train a binary classifier over thousands of samples on a single mid-range computer, significantly outperforming state-of-the-art results.

In this paper, we show that it is impossible to construct a public key encryption scheme (PKE) from a ring signature scheme in a black-box fashion in the standard model. Such an impossibility is highly non-trivial because, to the best of our knowledge, known generic constructions of ring signature scheme are based on public key cryptosystems or in the random oracle model. Technically, we introduce a new cryptographic primitive named indistinguishable multi-designated verifiers signature (IMDVS), and prove that (i) IMDVS is equivalent to PKE, and (ii) it is impossible to construct IMDVS from a ring signature scheme in a generic way. Our result suggests an essential gap between ring signature and group signature, as it is known that group signature implies PKE.

Much recent work has developed efficient protocols for threshold signatures, where $n$ parties share a signing key and some threshold $t$ of those parties must interact to produce a signature. Yet efficient threshold signatures with post-quantum security have been elusive, with the state-of-the-art being a two-round scheme by Damgård et al. based on lattices that support only the full threshold case (i.e., $t=n$).

We show here a two-round threshold signature scheme based on standard lattice assumptions that support arbitrary thresholds $t\leq n$. Estimates of our scheme's performance at the $128$-bit security level with a trusted setup show that in the $3$-out-of-$5$ case, we obtain signatures of size $11.5$ KB and public keys of size $13.6$ KB, with an execution of the signing protocol using roughly $1.5$ MB of communication per party. We achieve improved parameters if only a small bounded number of signatures are ever issued with the same key.

As an essential building block and independent contribution, we construct a maliciously secure threshold (linearly) homomorphic encryption scheme that supports arbitrary thresholds $t \leq n$.

Cryptocurrency exchange platforms such as Coinbase, Binance, enable users to purchase and sell cryptocurrencies conveniently just like trading stocks/commodities. However, because of the nature of blockchain, when a user withdraws coins (i.e., transfers coins to an external on-chain account), all future transactions can be learned by the platform. This is in sharp contrast to conventional stock exchange where all external activities of users are always hidden from the platform. Since the platform knows highly sensitive user private information such as passport number, and bank information, linking all (on-chain) transactions raises a serious privacy concern about the potential disastrous data breach in those cryptocurrency exchange platforms.

In this paper, we propose a cryptocurrency exchange that restores user anonymity for the first time. To our surprise, the seemingly well-studied privacy/anonymity problem has several new challenges in this setting. Since the public blockchain and internal transaction activities naturally provide many non-trivial leakages to the platform, internal privacy is not only useful in the usual sense but also becomes necessary for regaining the basic anonymity of user transactions. We also ensure that the user cannot double spend, and the user has to properly report accumulated profit for tax purposes, even in the private setting. We give a careful modeling and efficient construction of the system that achieves constant computation and communication overhead (with only simple cryptographic tools and rigorous security analysis); we also implement our system and evaluate its practical performance.

Broadcast protocols enable a set of $n$ parties to agree on the input of a designated sender, even facing attacks by malicious parties. In the honest-majority setting, a fruitful line of work harnessed randomization and cryptography to achieve low-communication broadcast protocols with sub-quadratic total communication and with "balanced" sub-linear communication cost per party.

However, comparatively little is known in the dishonest-majority setting. Here, the most communication-efficient constructions are based on the protocol of Dolev and Strong (SICOMP '83), and sub-quadratic broadcast has not been achieved even using randomization and cryptography. On the other hand, the only nontrivial $\omega(n)$ communication lower bounds are restricted to deterministic protocols, or against strong adaptive adversaries that can perform "after the fact" removal of messages.

We provide new communication lower bounds in this space, which hold against arbitrary cryptography and setup assumptions, as well as a simple protocol showing near tightness of our first bound.

1) We demonstrate a tradeoff between resiliency and communication for randomized protocols secure against $n-o(n)$ static corruptions. For example, $\Omega(n\cdot {\sf polylog}(n))$ messages are needed when the number of honest parties is $n/{\sf polylog}(n)$; $\Omega(n\sqrt{n})$ messages are needed for $O(\sqrt{n})$ honest parties; and $\Omega(n^2)$ messages are needed for $O(1)$ honest parties.

Complementarily, we demonstrate broadcast with $O(n\cdot{\sf polylog}(n))$ total communication facing any constant fraction of static corruptions.

2) Our second bound considers $n/2 + k$ corruptions and a weakly adaptive adversary that cannot remove messages "after the fact." We show that any broadcast protocol within this setting can be attacked to force an arbitrary party to send messages to $k$ other parties. Our bound rules out, for example, broadcast facing $51\%$ corruptions, in which all non-sender parties have sublinear communication locality.

The scalability and interoperability challenges in current cryptocurrencies have motivated the design of cryptographic protocols that enable efficient applications on top and across widely used cryptocurrencies such as Bitcoin or Ethereum. Examples of such protocols include (virtual) payment channels, atomic swaps, oracle-based contracts, deterministic wallets, and coin mixing services. Many of these protocols are built upon minimal core functionalities supported by a wide range of cryptocurrencies. Most prominently, adaptor signatures (AS) have emerged as a powerful tool for constructing blockchain protocols that are (mostly) agnostic to the specific logic of the underlying cryptocurrency. Even though AS-based protocols are built upon the same cryptographic principles, there exists no modular and faithful way for reasoning about their security. Instead, all the works analyzing such protocols focus on reproving how adaptor signatures are used to cryptographically link transactions while considering highly simplified blockchain models that do not capture security-relevant aspects of transaction execution in blockchain-based consensus.

To help this, we present LedgerLocks, a framework for the secure design of AS-based blockchain applications in the presence of a realistic blockchain. LedgerLocks defines the concept of AS-locked transactions, transactions whose publication is bound to the knowledge of a cryptographic secret. We argue that AS-locked transactions are the common building block of AS-based blockchain protocols and we define $\mathcal{G}_{\mathsf{LedgerLocks}}$, a realistic ledger model in the Universal Composability framework with built-in support for AS-locked transactions. As LedgerLocks abstracts from the cryptographic realization of AS-locked transactions, it allows protocol designers to focus on the blockchain-specific security considerations instead.

HALFLOOP is a family of tweakable block ciphers that are used for encrypting automatic link establishment (ALE) messages in high-frequency radio, a technology commonly used by the military, other government agencies, and industries that require high robustness in long-distance communications. Recently, it was shown in [DDLS22] that the smallest version of the cipher, HALFLOOP-24, can be attacked within a practical time and memory complexity. However, in the real-word ALE setting, it turns out that this attack requires waiting more than 500 years to collect the necessary amount of plaintext-tweak-ciphertext pairs fulfilling the conditions of the attack. In this paper, we present real-world practical attacks against HALFLOOP-24 which are based on a probability-one differential distinguisher. In our attacks, we significantly reduce the data complexity to three differential pairs in the chosen-plaintext (CPA) setting which is optimal in the sense that even a brute force attack needs at least six plaintext-tweak-ciphertext pairs to uniquely identify the correct key. Considering the same ALE setting as [DDLS22], this translates to a reduction from 541 years to 2 hours worth of intercepted traffic. Besides, we provide the first, non generic, public cryptanalysis of HALFLOOP-48 and HALFLOOP-96. More precisely, we present Demirci-Selçuk meet-in-the-middle attacks against full-round HALFLOOP-48 and round-reduced HALFLOOP-96 to recover the complete master key in a CPA setting. However, unlike the attacks on HALFLOOP-24, our attacks on the larger versions are only theoretical. Moreover, for HALFLOOP-96 the known generic time-memory trade-off attack, based on a flawed tweak handling, remains the strongest attack vector. In conclusion, we iterate what was already stated in [DDLS22]: HALFLOOP does not provide adequate protection and should not be used.

For $n = pq$ a product of two safe primes, we construct and prove security of a cryptographic hash function $H$ mapping into the square residues $QR_n \subset (\mathbb{Z}/n\mathbb{Z})^*$, by squaring the output of an ordinary cryptographic hash function $H$ of sufficiently long output.

Threshold ECDSA receives interest lately due to its widespread adoption in blockchain applications. A common building block of all leading constructions involves a secure conversion of multiplicative shares into additive ones, which is called the multiplicative-to-additive (MtA) function. MtA dominates the overall complexity of all existing threshold ECDSA constructions. Specifically, $O(n^2)$ invocations of MtA are required in the case of $n$ active signers. Hence, improvement of MtA leads directly to significant improvements for all state-of-the-art threshold ECDSA schemes.

In this paper, we design a novel MtA by revisiting the Joye-Libert (JL) cryptosystem. Specifically, we revisit JL encryption and propose a JL-based commitment, then give efficient zero-knowledge proofs for JL cryptosystem which are the first to have standard soundness. Our new MtA offers the best time-space complexity trade-off among all existing MtA constructions. It outperforms state-of-the-art constructions from Paillier by a factor of $1.85$ to $2$ in bandwidth and $1.2$ to $1.7$ in computation. It is $7\times$ faster than those based on Castagnos-Laguillaumie encryption only at the cost of $2\times$ more bandwidth. While our MtA is slower than OT-based constructions, it saves $18.7\times$ in bandwidth requirement. In addition, we also design a batch version of MtA to further reduce the amotised time and space cost by another $25$%.

This work formally analyzes the anonymity guarantees of continuous stop-and-go mixnets and attempts to answer the above question. Existing mixnet based anonymous communication protocols that aim to provide provable anonymity guarantees rely on round-based communication models --- which requires synchronization among all the nodes and clients, and difficult to achieve in practice. Continuous stop-and-go mixnets (e.g., Loopix and Nym) provide a nice alternative by adding a random delay for each message on every hop independent of all other hops and all other messages. The core anonymization technique of continuous mixnets combined with the fact that the messages are sent by the clients to the mixnet at different times makes it a difficult problem to formally prove security for such mixnet protocols; all existing analyses for such designs provide only experimental evaluations for anonymity.

We are the first to close that gap and provide a formal analysis. We provide two indistinguishability based definitions (of sender anonymity), namely pairwise unlinkability and user unlinkability, tuned specifically for continuous stop-and-go mixnets. We derive the adversarial advantage as a function of the protocol parameters for the two definitions. We show that there is a fundamental lower bound on the adversarial advantage $\delta$ for pairwise unlinkability; however, strong user unlinkability (negligible adversarial advantage) can be achieved if the users message rate ($\lambda_u$) is proportional to message processing rate ($\lambda$) on the nodes.

Fully Homomorphic Encryption (FHE) is a widely used cryptographic primitive for performing arbitrary computations on encrypted data. However, FHE incorporates a computationally intensive mechanism known as "bootstrapping", that resets the noise in the ciphertext to a lower level allowing the computation on circuits of arbitrary depth. This process can take significant time, ranging from several minutes to hours. To address the above issue, in this work, we propose an Electronic Design Automation (EDA) framework FHEDA that generates efficient Boolean representations of circuits compatible with the Torus-FHE (ASIACRYPT 2020) scheme. To the best of our knowledge, this is the first work in the EDA domain of FHE. We integrate logic synthesis tricks and gate optimization techniques into our FHEDA framework for reducing the total number of bootstrapping operations in a Boolean circuit, which leads to a significant (up to 50%) reduction in homomorphic computation time. Our FHEDA is built upon the observation that in Torus-FHE at most one Boolean gate over fresh encryptions does not require bootstrapping. By integrating this observation with logic replacement techniques into FHEDA, we could reduce the total number of bootstrapping operations along with the circuit depth. This eventually reduces the homomorphic evaluation time of Boolean circuits. In order to verify the efficacy of our approach, we assess the performance of the proposed EDA flow on a diverse set of representative benchmarks including privacy-preserving machine learning and different symmetric key block ciphers.

Key-policy attribute-based encryption scheme (KP-ABE) uses a set of attributes as public keys for encryption. It allows homomorphic evaluation of ciphertext into another ciphertext of the same message, which can be decrypted if a certain access policy based on the attributes is satisfied. A lattice-based KP-ABE scheme is reported in several works in the literature, and its software implementation is available in an open-source library called PALISADE. However, as the cryptographic primitives in KP-ABE are overly involved, non-trivial hardware acceleration is needed for its adoption in practical applications.

In this work, we provide GPU-based algorithms for accelerating KP-ABE encryption and homomorphic evaluation functions seamlessly integrated into the open-source library with minor additional build changes needed to run the GPU kernels. Using GPU algorithms, we perform both homomorphic encryption and homomorphic evaluation operations 2.1× and 13.2× faster than the CPU implementations reported in the literature on an Intel i9, respectively. Furthermore, our implementation supports up to 128 attributes for encryption and homomorphic evaluation with fixed and changing access policies. Unlike the reported GPU-based homomorphic operations in the literature, which support only up to 32 attributes and give estimations for a higher number of attributes. We also propose a GPU-based KP-ABE scheme for publish/subscribe messaging applications, in which end-to-end security of the messages is guaranteed. Here, while the exchanged messages are encrypted with as many as 128 attributes by publishers, fewer attributes are needed for homomorphic evaluation. Our fast and memory-efficient GPU implementations of KP-ABE encryption and homomorphic evaluation operations demonstrate that the KP-ABE scheme can be used for practicable publish/subscribe messaging applications.

Clouds have replaced local backup systems due to their stronger reliability and availability guarantees compared to local machines, which are prone to hardware/software failure or can be stolen or lost, especially in the case of portable devices

In recent years, some digital assets are managed solely through the knowledge of cryptographic secrets (e.g., cryptocurrency, encrypted datasets), whose loss results in the permanent loss of the digital asset. Since the security of such systems relies on the assumption that the cryptographic key remains secret, a secret owner Alice cannot simply store a backup copy of such secret on the cloud, since this corresponds to giving away her ownership over the digital assets. Thus Alice must rely on her personal machines to maintain these secrets.

Is it possible to obtain the best of the two worlds, where Alice benefits from the convenience of storing a backup copy of her cryptographic secrets on the cloud such that she can recover them even when she loses her devices and forgets all credentials, while at the same time retaining full ownership of her secrets?

In this paper, we show that this is indeed possible, by revisiting and expanding the concept of Break-glass Encryption pioneered by Scafuro [PKC19].

We provide a secret-recovery mechanism where confidentiality is always guaranteed when Alice has not lost her credentials, even in the presence of a malicious cloud and users ([PKC19] only guarantees that a violation of confidentiality will be {\em detected}, not prevented). Recoverability is achieved in most circumstances.

We design and prove security of a credential-less authentication mechanism, that enables Alice to access her secret, without remembering any credentials. This tool was assumed in [PKC19] but not implemented. We redesign the storage mechanism on the cloud side so that the cloud needs to perform no operations during the storage phase. This is in contrast with [PKC19] where the cloud must re-encrypt the stored file continuously with the help of a secure enclave (regardless of whether a recovery procedure will happen).

Our protocols are proved secure in the Universal Composition framework.

Decision tree evaluation is extensively used in machine learning to construct accurate classification models. Often in the cloud-assisted communication paradigm cloud servers execute remote evaluations of classification models using clients’ data. In this setting, the need for private decision tree evaluation (PDTE) has emerged to guarantee no leakage of information for the client’s input nor the service provider’s trained model i.e., decision tree. In this paper, we propose a private decision tree evaluation protocol based on the three-party replicated secret sharing (RSS) scheme. This enables us to securely classify inputs without any leakage of the provided input or the trained decision tree model. Our protocol only requires constant rounds of communication among servers, which is useful in a network with longer delays.

Ma et al. (NDSS 2021) presented a lightweight PDTE protocol with sublinear communication cost with linear round complexity in the size of the input data. This protocol works well in the low latency network such as LAN while its total execution time is unfavourably increased in the WAN setting. In contrast, Tsuchida et al. (ProvSec 2020) constructed a constant round PDTE protocol at the cost of communication complexity, which works well in the WAN setting. Although their construction still requires 25 rounds, it showed a possible direction on how to make constant round PDTE protocols. Ji et al. (IEEE Transactions on Dependable and Secure Computing) presented a simplified PDTE with constant rounds using the function secret sharing (FSS) at the cost of communication complexity.

Our proposed protocol only requires five rounds among the employed three servers executing secret sharing schemes, which is comparable to previously proposed protocols that are based on garbled circuits and homomorphic encryption. To further demonstrate the efficiency of our protocol, we evaluated it using real-world classification datasets. The evaluation results indicate that our protocol provides better concrete performance in the WAN setting that has a large network delay.

Quantum attacks using superposition queries are known to break many classically secure modes of operation. While these attacks do not necessarily threaten the security of the modes themselves, since they rely on a strong adversary model, they help us to draw limits on the provable security of these modes.

Typically these attacks use the structure of the mode (stream cipher, MAC or authenticated encryption scheme) to embed a period-finding problem, which can be solved with a dedicated quantum algorithm. The hidden period can be recovered with a few superposition queries (e.g., $O(n)$ for Simon's algorithm), leading to state or key-recovery attacks. However, this strategy breaks down if the period changes at each query, e.g., if it depends on a nonce.

In this paper, we focus on this case and give dedicated state-recovery attacks on the authenticated encryption schemes Rocca, Rocca-S, Tiaoxin-346 and AEGIS-128L. These attacks rely on a procedure to find a Boolean hidden shift with a single superposition query, which overcomes the change of nonce at each query. As they crucially depend on such queries, we stress that they do not break any security claim of the authors, and do not threaten the schemes if the adversary only makes classical queries.

Various message authentication codes (MACs), including HMAC-Streebog and Streebog-K, are based on the keyless hash function Streebog. Under the assumption that the compression function of Streebog is resistant to the related key attacks, the security proofs of these algorithms were recently presented at CTCrypt 2022.

We carefully detail the resources of the adversary in the related key settings, revisit the proof, and obtain tight security bounds. Let $n$ be the bit length of the hash function state. If the amount of processed data is less than about $2^{n-k}$ blocks, then for HMAC-Streebog-512 and Streebog-K, the only effective method of forgery (or distinguishing) is guessing the $k$-bit secret key or the tag if it is shorter than the key. So, we can speak about ``$k$-bit security'' without specifying the amount of material, if the key length is no longer than half of a state. The bound for HMAC-Streebog-256 is worse and equal to $2^{\frac{n}{2}-k}$ blocks.

BGV and BFV are among the most widely used fully homomorphic encryption (FHE) schemes. Both schemes have a common plaintext space, with a rich algebraic structure. Our main contribution is to show how this structure can be exploited to more efficiently homomorphically evaluate polynomials. Namely, using Galois automorphisms, we present an algorithm to homomorphically evaluate a polynomial of degree $d$ in only $3\log(d)$ (in some cases only $2\log(d)$) many ciphertext-ciphertext multiplications and automorphism evaluations, where $d$ is bounded by the ring degree. In other words, as long as the degree of the polynomial is bounded, we achieve an exponential speedup compared to the state of the art. In particular, the approach also improves on the theoretical lower bound of $2\sqrt{d}$ many ciphertext-ciphertext multiplications, which would apply if automorphisms were not available.

We investigate how to apply our improved polynomial evaluation to the bootstrapping procedure for BFV, and show that we are able to significantly improve its performance. We demonstrate this by providing an implementation of our improved BFV bootstrapping using the Microsoft SEAL library. More concretely, we obtain a $1.6\times$ speed up compared to the prior implementation given by Chen and Han (Eurocrypt 2018). The techniques are independent of, and can be combined with, the more recent optimisations presented by Geelen \textit{et al}. (Eurocrypt 2023).

As an additional contribution, we show how the bootstrapping approach used in schemes such as FHEW and TFHE can be applied in the BFV context. In particular, we demonstrate that programmable bootstrapping can be achieved for BFV. Moreover, we show how this bootstrapping approach can be improved in the BFV context to make better use of the Galois structure. However, we estimate that its complexity is around three orders of magnitude slower than the classical approach to BFV bootstrapping.

Using the provable security approach, we analyze CRISP – a standardized Russian cryptographic protocol that aims to ensure confidentiality, integrity of transmitted messages, as well as protection against replay attacks. The protocol is considered as a specific mode of authenticated encryption with associated data (AEAD). We take into account that one key can be used by many protocol's participants and in different cipher suites. We impose requirements for the set of the cipher suites used in the protocol and show that the existing ones meet them. Estimates of the maximum allowable amount of data processed using a single key are also given.