International Association
for Cryptologic Research

Fully homomorphic encryption (FHE) is one of the prospective tools for privacypreserving machine learning (PPML), and several PPML models have been proposed based on various FHE schemes and approaches. Although the FHE schemes are known as suitable tools to implement PPML models, previous PPML models on FHE encrypted data are limited to only simple and non-standard types of machine learning models. These non-standard machine learning models are not proven efficient and accurate with more practical and advanced datasets. Previous PPML schemes replace non-arithmetic activation functions with simple arithmetic functions instead of adopting approximation methods and do not use bootstrapping, which enables continuous homomorphic evaluations. Thus, they could not use standard activation functions and could not employ a large number of layers. The maximum classification accuracy of the existing PPML model with the FHE for the CIFAR-10 dataset was only 77% until now. In this work, we firstly implement the standard ResNet-20 model with the RNS-CKKS FHE with bootstrapping and verify the implemented model with the CIFAR-10 dataset and the plaintext model parameters. Instead of replacing the non-arithmetic functions with the simple arithmetic function, we use state-of-the-art approximation methods to evaluate these non-arithmetic functions, such as the ReLU, with sufficient precision [1]. Further, for the first time, we use the bootstrapping technique of the RNS-CKKS scheme in the proposed model, which enables us to evaluate a deep learning model on the encrypted data. We numerically verify that the proposed model with the CIFAR-10 dataset shows 98.67% identical results to the original ResNet-20 model with non-encrypted data. The classification accuracy of the proposed model is 90.67%, which is pretty close to that of the original ResNet-20 CNN model. It takes about 4 hours for inference on a dual Intel Xeon Platinum 8280 CPU (112 cores) with 512 GB memory. We think that it opens the possibility of applying the FHE to the advanced deep PPML model.

Because of the everlasting need of space to store even the headers of a blockchain, Ethereum requiring for example more than 4 GiB for such a task, superlight clients stood out as a necessity, for instance to enable deployment on wearable devices or smart contracts. Among them is FlyClient, whose main benefit was to be non-interactive. However, it is still to be shown how a such protocol can be deployed on an already existing chain, without contentious soft or hard forks. FlyClient suggests the use of velvet forks, a recently introduced mechanism for conflict-free deployment of blockchain consensus upgrades – yet the impact on the security of the light client protocol remains unclear. In this work, we provide a comprehensive analysis of the security of FlyClient under a velvet fork deployment. We discover that a naive velvet fork implementation exposes FlyClient to chain-sewing attacks, a novel type of attack, concurrently observed in similar superlight clients. Specifically, we show how an adversary subverting only a small fraction of the hash rate or consensus participants can not only execute doublespending attacks against velvet FlyClient nodes, but also print fake coins – with high probability of success. We then present three potential mitigations to this attack and prove their security both under velvet and, more traditional soft and hard fork deployment. In particular, our mitigations do not necessarily require a majority of honest, up-to-date miners.

As the Internet of Things (IoT) rolls out today to devices whose lifetime may well exceed a decade, conservative threat models should consider attackers with access to quantum computing power. The SUIT standard (specified by the IETF) defines a security architecture for IoT software updates, standardizing the metadata and the cryptographic tools---namely, digital signatures and hash functions---that guarantee the legitimacy of software updates. While the performance of SUIT has previously been evaluated in the pre-quantum context, it has not yet been studied in a post-quantum context. Taking the open-source implementation of SUIT available in RIOT as a case study, we overview post-quantum considerations, and quantum-resistant digital signatures in particular, focusing on low-power, microcontroller-based IoT devices which have stringent resource constraints in terms of memory, CPU, and energy consumption. We benchmark a selection of proposed post-quantum signature schemes (LMS, Falcon, and Dilithium) and compare them with current pre-quantum signature schemes (Ed25519 and ECDSA). Our benchmarks are carried out on a variety of IoT hardware including ARM Cortex-M, RISC-V, and Espressif (ESP32), which form the bulk of modern 32-bit microcontroller architectures. We interpret our benchmark results in the context of SUIT, and estimate the real-world impact of post-quantum alternatives for a range of typical software update categories.

Over the last few decades, the cost and difficulty of producing integrated circuits at ever shrinking node sizes has vastly increased, resulting in the manufacturing sector moving overseas. Using offshore foundries for chip fabrication, however, introduces new vulnerabilities into the design flow since there is little to no observability into the manufacturing process. At the same time, both design and optimization are becoming increasingly complex, particularly as SoC designs gain popularity. Common practices such as porting a design across node sizes and reusing cores at multiple area/performance tradeoffs further complicate assurance as layout specific features impede comparison. Methods have been developed for conducting integrated circuit decomposition on fabricated chips [1][2][16] to extract the as-fabricated design files such as the GDSII layout or gate-level netlist. While mature netlist equivalency checking tools are included with any design flow, there is a lack of tools for performing deeper analyses on the extracted designs for the purposes of hardware assurance or design recovery from obsolete parts. To this end, there is a need for a tool to extract functionality from netlists at a higher abstraction level to reconstruct behavioral Register Transfer Level (RTL) code.

While server-only authentication with certificates is the most widely used mode of operation for the Transport Layer Security (TLS) protocol on the world wide web, there are many applications where TLS is used in a different way or with different constraints. For example, embedded Internet-of-Things clients may have a server certificate pre-programmed and be highly constrained in terms of communication bandwidth or computation power. As post-quantum algorithms have a wider range of performance trade-offs, designs other than traditional ``signed-key-exchange'' may be worthwhile. The KEMTLS protocol, presented at ACM CCS 2020, uses key encapsulation mechanisms (KEMs) rather than signatures for authentication in the TLS 1.3 handshake, a benefit since most post-quantum KEMs are more efficient than PQ signatures. However, KEMTLS has some drawbacks, especially in the client authentication scenario which requires a full additional roundtrip.

We explore how the situation changes with pre-distributed public keys, which may be viable in many scenarios, for example pre-installed public keys in apps, on embedded devices, cached public keys, or keys distributed out of band. Our variant of KEMTLS with pre-distributed keys, called KEMTLS-PDK, is more efficient in terms of both bandwidth and computation compared to post-quantum signed-KEM TLS (even cached public keys), and has a smaller trusted code base. When client authentication is used, KEMTLS-PDK is more bandwidth efficient than KEMTLS yet can complete client authentication in one fewer round trips, and has stronger authentication properties. Interestingly, using pre-distributed keys in KEMTLS-PDK changes the landscape on suitability of PQ algorithms: schemes where public keys are larger than ciphertexts/signatures (such as Classic McEliece and Rainbow) can be viable, and the differences between some lattice-based schemes is reduced. We also discuss how using pre-distributed public keys provides privacy benefits compared to pre-shared symmetric keys in TLS.

Attribute-based encryption (ABE) schemes by lattices are likely to resist quantum attacks, and can be widely applied to many Internet of Thing or cloud scenarios. One of the most attractive feature for ABE is the ability of fine-grained access control which provides an effective way to ensure data security. In this work, we propose an efficient ciphertext policy attribute-based encryption scheme based on hardness assumption of LWE. Being different from other similar schemes, a user's secret key can only be generated once only and it can be used to decrypt ciphertext under different access policies by making combinations of secret key fragments. Specially, we propose a method for binding users' secret keys with their attributes and identities, which solves the collusion attack problem. The security of the scheme is proved to be selective secure under the LWE assumption.

In this paper, we introduce the problem of Asynchronous Data Dissemination (ADD). Intuitively, an ADD protocol replicates a message to all honest nodes in an asynchronous network, given that at least $t+1$ honest nodes initially hold the message where $t$ is the maximum number of malicious nodes. We design a simple yet efficient ADD protocol for $n$ parties that is information theoretically secure, tolerates up to one-third malicious nodes, and has a communication cost of $O(n|M|+n^2)$ for replicating a message $M$.

We then use our ADD protocol to improve many important primitives in cryptography and distributed computing. For reliable broadcast, assuming the existence of collision resistance hash functions, we present a protocol with communication cost $O(n|M| + \kappa n^2)$ where $\kappa$ is the size of the hash function output. This is an improvement over the best-known complexity of $O(n|M| + \kappa n^2 \log n)$ under the same setting. Next, we use our ADD protocol along with additional new techniques to improve the communication complexity of Asynchronous Verifiable Secret Sharing~(AVSS) and Asynchronous Complete Secret Sharing~(ACSS) with no trusted setup from $O(\kappa n^2 \log n)$ to $O(\kappa n^2)$. Furthermore, we use ADD and a publicly-verifiable secret sharing scheme to improve dual-threshold ACSS and Asynchronous Distributed Key Generation~(ADKG).

The proliferation of the Internet of Things (IoT) technology has made ubiquitous computing a reality by broadening Internet connectivity across diverse application domains, thus bridging billions of devices and human beings as well for information collection, data processing, and decision-making. In recent years, IoT technology and its applications in various industrial sectors have grown exponentially. Most existing industrial IoT (IIoT) implementations, however, are still relying on a centralized architecture, which is vulnerable to the single point of failure attack and requires a massive amount of computation at the central entity. The emerging blockchain technology is currently undergoing rapid development and has the full potential to revolutionize the IIoT platforms and applications. As a distributed and decentralized tamper-resistant ledger, blockchain maintains the consistency of data records at different locations and holds the potential to address the issues in traditional IIoT networks, such as heterogeneity, interoperability, and security. Integrating the blockchain technology into IIoT platforms requires to address several critical challenges that are inherent in IIoT and blockchain themselves, such as standardization, scalability, and interoperability. This paper provides a comprehensive review on the recent advances in architecture design and technology development towards tackling these challenges. We further provide several representative industrial use cases that can benefit from the integration of blockchain technology, and discuss the recent research trends and open issues in blockchain-enabled IIoT platforms.

The advent of blockchain protocols has reignited the interest in adaptively secure broadcast, as it is by now well known that broadcasting over a diffusion network allows an adaptive adversary to corrupt the sender depending on the message s/he attempts to send and change it. Hirt and Zikas [Eurocrypt '10] proved that this is an inherent limitation of broadcast in the simulation-based setting, i.e., that this task is impossible against an adaptive adversary corrupting a strict majority of the parties.

In this work, we show that, contrary to previous perception, the above limitation is not an artifact of simulation-based security, but that it also applies to the property-based broadcast definition adapted for adaptive adversaries. We then turn to the resource-restricting cryptography (RRC) paradigm, which was proven useful in circumventing strong impossibility results, and ask whether it also allows us to circumvent the above negative result. We answer this question in the affirmative, by showing that time-lock puzzles (TLPs)---which can be viewed as an instance of RRC---indeed allow for achieving the property-based definition and circumvent the impossibility of adaptively secure broadcast.

The natural question is then, do TLPs also allow for simulation-based adaptively secure broadcast against corrupted majorities? It turns out that they do not, which serves as yet another motivation for simulation-based security, especially when dealing with adaptive adversaries. Nonetheless, we show that a positive result can be achieved if we turn to what is essentially a non-committing version of TLPs, which uses access to a programmable random oracle.

HMAC and NMAC are the most basic and important constructions to convert Merkle-Damg{\aa}rd hash functions into message authentication codes (MACs) or pseudorandom functions (PRFs). In the quantum setting, at CRYPTO 2017, Song and Yun showed that HMAC and NMAC are quantum pseudorandom functions (qPRFs) under the standard assumption that the underlying compression function is a qPRF. Their proof guarantees security up to $O(2^{n/5})$ or $O(2^{n/8})$ quantum queries when the output length of HMAC and NMAC is $n$ bits. However, there is a gap between the provable security bound and a simple distinguishing attack that uses $O(2^{n/3})$ quantum queries. This paper settles the problem of closing the gap. We show that the tight bound of the number of quantum queries to distinguish HMAC or NMAC from a random function is $\Theta(2^{n/3})$ in the quantum random oracle model, where compression functions are modeled as quantum random oracles. To give the tight quantum bound, based on an alternative formalization of Zhandry's compressed oracle technique, we introduce a new proof technique focusing on the symmetry of quantum query records.

Merkle tree is applied in diverse applications, namely, Blockchain, smart grid, IoT, Biomedical, financial transactions, etc., to verify authenticity and integrity. Also, the Merkle tree is used in privacy-preserving computing. However, the Merkle tree is a computationally costly data structure. It uses cryptographic string hash functions to partially verify the data integrity and authenticity of a data block. However, the verification process creates unnecessary network traffic because it requires partial hash values to verify a particular block. Moreover, the performance of the Merkle tree also depends on the network latency. Therefore, it is not feasible for most of the applications. To address the above issue, we proposed an alternative model to replace the Merkle tree, called HEX-BLOOM, and it is implemented using hash, Exclusive-OR and Bloom Filter. Our proposed model does not depends on network latency for verification of data block's authenticity and integrity. HEX-BLOOM uses an approximation model, Bloom Filter. Moreover, it employs a deterministic model for final verification of the correctness. In this article, we show that our proposed model outperforms the state-of-the-art Merkle tree in every aspect.

Abstract—This paper proposes the first side-channel attack on FALCON—a NIST Round-3 finalist for the post-quantum digital signature standard. We demonstrate a known-plaintext attack that uses the electromagnetic measurements of the device to extract the secret signing keys, which then can be used to forge signatures on arbitrary messages. The proposed attack targets the unique floating-point multiplications within FALCON’s Fast Fourier Transform through a novel extend-and-prune strategy that extracts the sign, mantissa, and exponent variables without false positives. The extracted floating-point values are then mapped back to the secret key’s coefficients. Our attack, notably, does not require pre-characterizing the power profile of the target device or crafting special inputs. Instead, the statistical differences on obtained traces are sufficient to successfully execute our proposed differential electromagnetic analysis. The results on an ARM-Cortex-M4 running the FALCON NIST’s reference software show that approximately 10k measurements are sufficient to extract the entire key.

Secure aggregation is a critical component in federated learning, which enables the server to learn the aggregate model of the users without observing their local models. Conventionally, secure aggregation algorithms focus only on ensuring the privacy of individual users in a single training round. We contend that such designs can lead to significant privacy leakages over multiple training rounds, due to partial user selection/participation at each round of federated learning. In fact, we empirically show that the conventional random user selection strategies for federated learning lead to leaking users' individual models within number of rounds linear in the number of users. To address this challenge, we introduce a secure aggregation framework with multi-round privacy guarantees. In particular, we introduce a new metric to quantify the privacy guarantees of federated learning over multiple training rounds, and develop a structured user selection strategy that guarantees the long-term privacy of each user (over any number of training rounds). Our framework also carefully accounts for the fairness and the average number of participating users at each round. We perform several experiments on MNIST and CIFAR-10 datasets in the IID and the non-IID settings to demonstrate the performance improvement over the baseline algorithms, both in terms of privacy protection and test accuracy.

We extend two-party private set union for secure computation, by considering matching between records having multiple identifiers (or keys), for example email and phone. In the classical setting of this problem, two parties want to perform various downstream computations on the union of two datasets. The union is computed by joining two datasets with the help of a single agreed upon identifier, say email. By extending this to joining records with multiple identifiers, we bring it much closer to real world uses where the match rate and match quality can be greatly improved by considering multiple identifiers.

We introduce an extension to the Private-ID protocol [3] which outputs a full outer join (union) of two datasets by a match logic that can join rows containing multiple identifiers. We also introduce new techniques for privately sharding the protocol across multiple servers. Both constructions are based on Decisional Diffie–Hellman (DDH) assumptions.

The key exchange protocol that establishes initial shared secrets in the handshake of the Signal end-to-end encrypted messaging protocol has several important characteristics: (1) it runs asynchronously (without both parties needing to be simultaneously online), (2) it provides implicit mutual authentication while retaining deniability (transcripts cannot be used to prove either party participated in the protocol), and (3) it retains security even if some keys are compromised (forward secrecy and beyond). All of these properties emerge from clever use of the highly flexible Diffie--Hellman protocol.

While quantum-resistant key encapsulation mechanisms (KEMs) can replace Diffie--Hellman key exchange in some settings, there is no KEM-based replacement for the Signal handshake that achieves all three aforementioned properties, in part due to the inherent asymmetry of KEM operations. In this paper, we show how to construct asynchronous deniable key exchange by combining KEMs and designated verifier signature schemes. Furthermore, we show how designated verifier signatures can be built by using chameleon hash functions in both full-domain-hash and Fiat--Shamir-style signature schemes, enabling efficient post-quantum instantiations. This provides the first efficient post-quantum realization of the Signal handshake with the same asynchronicity and security properties as the original Signal protocol.

In the era of cloud computing and machine learning, data has become a highly valuable resource. Recent history has shown that the benefits brought forth by this data driven culture come at a cost of potential data leakage. Such breaches have a devastating impact on individuals and industry, and lead the community to seek privacy preserving solutions. A promising approach is to utilize Fully Homomorphic Encryption (FHE) to enable machine learning over encrypted data, thus providing resiliency against information leakage. However, computing over encrypted data incurs a high computational overhead, thus requiring the redesign of algorithms, in an ``FHE-friendly" manner, to maintain their practicality.

In this work we focus on the ever-popular tree based methods (e.g., boosting, random forests), and propose a new privacy-preserving solution to training and prediction for trees. Our solution employs a low-degree approximation for the step-function together with a lightweight interactive protocol, to replace components of the vanilla algorithm that are costly over encrypted data. Our protocols for decision trees achieve practical usability demonstrated on standard UCI datasets encrypted with fully homomorphic encryption. In addition, the communication complexity of our protocols is independent of the tree size and dataset size in prediction and training, respectively, which significantly improves on prior works.

White-box cryptography has been proposed as a software countermeasure technique for applications where limited or no hardware-based security is available. In recent years it has been crucial for enabling the security of mobile payment applications. In this paper we continue a recent line of research on device binding for white-box cryptography. Device binding ensures that a white-box program is only executable on one specific device and is unusable elsewhere. Building on this, we ask the following question: is it possible to design a global white-box program which is compiled once, but can be securely shared with multiple users and bound to each of their devices? Acknowledging this question, we provide two new types of provably-secure constructions for white-box programs.

First, we consider the use of Token-Based Obfuscation (TBO) and show that TBO can provide us a direct way to construct white-box programs with device-binding, as long as we can securely share a token generation key between the compiling entity and the device running the white-box program. This new feasibility result provides more general and efficient results than previously presented for white-box cryptography and demonstrates a new application of TBO not previously considered.

We then consider a stronger family of global white-boxes, where secrets don't need to be shared between users and providers. We show how to extend approaches used in practice based on message recoverable signatures and validate our proposed approach, by providing a construction based on puncturable PRFs and indistinguishability obfuscation.

Standardized Ethereum tokens, e.g., ERC-20 tokens, have become the norm in fundraising (through ICOs) and kicking off blockchain-based DeFi applications. However, they require the user’s wallet to hold both tokens and ether to pay the gas fee for making a transaction. This makes for a cumbersome and counterintuitive—at least for less tech-savvy users—user experience, especially when the token creator intends to switch to their own blockchain down the line, or wishes the flexibility of transferring the token to a different smart-contract enabled blockchain. We formalize, instantiate, and analyze in a composable manner a system that we call Etherless Ethereum Tokens (in short, EETs), which allows the token creator to allow its users to transact in a closed-economy manner, i.e., having only tokens on their wallet and paying any transaction fees in token units rather than gas. In the process, we devise a methodology for capturing Ethereum token-contracts in the Universal Composability (UC) framework, which can be of independent interest. We have implemented and benchmarked our system and compared it to another solution for obtaining similar functionality in Ethereum, i.e., the Gas Station Networks (GSN); in addition to being the first system with a rigorous security analysis, we demonstrate that EETs are not only far easier to deploy, but are also far less gas intensive than the GSN.

We study encrypted storage schemes where a client outsources data to an untrusted third-party server (such as a cloud storage provider) while maintaining the ability to privately query and dynamically update the stored data. We focus on encrypted multi-maps, a structured encryption (STE) scheme that stores pairs of label and value tuples that have several important applications (most notably, to searchable encryption and encrypted SQL databases). Encrypted multi-maps support queries for specific labels that return the associated value tuple. As responses are variable-length, encrypted multi-maps are subject to volume leakage attacks introduced by Kellaris et al. [CCS’16] with several follow-up works (including Grubbs et al. [CCS’18] and Lacharite et al. [S&P’18]). To prevent these attacks, volume-hiding encrypted multi-maps were introduced by Kamara and Moataz [Eurocrypt’19] that hide the volume of labels (i.e., the size of the associated value tuple).

As our main contribution, we present the first fully dynamic constructions of volume-hiding encrypted multi-maps that are both asymptotically and concretely efficient. Furthermore, our constructions simultaneously provide forward and backward privacy that are the de-facto standard security notions for dynamic STE schemes (Stefanov et al. [NDSS’14] and Bost [CCS’16]). Additionally, we implement our schemes to showcase their concrete efficiency. Our experimental evaluations show that our constructions are able to add dynamicity with minimal to no additional cost compared to the prior best static volume-hiding schemes of Patel et al. [CCS’20].

We consider the task of learning a function via oracle queries, where the queries and responses are monitored (and perhaps also modified) by an untrusted intermediary. Our goal is twofold: First, we would like to prevent the intermediary from gaining any information about either the function or the learner's intentions (e.g. the particular hypothesis class the learner is considering). Second, we would like to curb the intermediary's ability to meaningfully interfere with the learning process, even when it can modify the oracles' responses. Inspired by the works of Ishai et al. (Crypto 2019) and Goldwasser et al. (ITCS 2021), we formalize two new learning models, called Covert Learning and Covert Verifiable Learning, that capture these goals. Then, assuming hardness of the Learning Parity with Noise (LPN) problem, we show:

1. Covert Learning algorithms in the agnostic setting for parity functions and decision trees, where a polynomial time eavesdropping adversary that observes all queries and responses learns nothing about either the function, or the learned hypothesis. 2. Covert Verifiable Learning algorithms that provide similar learning and privacy guarantees, even in the presence of a polynomial-time adversarial intermediary that can modify all oracle responses. Here the learner is granted additional random examples and is allowed to abort whenever the oracles responses are modified.

Aside theoretical interest, our study is motivated by applications to the outsourcing of automated scientific discovery in drug design and molecular biology. It also uncovers limitations of current techniques for defending against model extraction attacks.