International Association
for Cryptologic Research

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.

In this paper, we present three design flaws in the 802.11 standard that underpins Wi-Fi. One design flaw is in the frame aggregation functionality, and another two are in the frame fragmentation functionality. These design flaws enable an adversary to forge encrypted frames in various ways, which in turn enables exfiltration of sensitive data. We also discovered common implementation flaws related to aggregation and fragmentation, which further worsen the impact of our attacks. Our results affect all protected Wi-Fi networks, ranging from WEP all the way to WPA3, meaning the discovered flaws have been part of Wi-Fi since its release in 1997. In our experiments, all devices were vulnerable to one or more of our attacks, confirming that all Wi-Fi devices are likely affected. Finally, we present a tool to test whether devices are affected by any of the vulnerabilities, and we discuss countermeasures to prevent our attacks.

Designing Boolean functions with fast output to compute and meeting all the criteria necessary for allowing the stream ciphers in which they are used as nonlinear components to resist all major attacks has been an open problem since the beginning of this century, when the algebraic attacks were invented (in 2003). Functions allowing good resistance are known since 2008, but their output is too slow and complex to compute. Functions with a fast and simple to compute output are known, such as majority functions and the so-called hidden weight bit (HWB) functions, but they all have a cryptographic weakness: their too small nonlinearity. \\In the present paper, we introduce a generalization of the HWB function into a construction of $n$-variable balanced functions $f$ from $(n-1)$-variable Boolean functions $g$ having some property held by a large number of functions. Function $f$ is defined by its support, equal to the image set of a vectorial function depending on $g$. This makes the function complex enough for allowing good cryptographic parameters, while its output is light to compute. The HWB function is what we obtain with $f$ when the initial function $g$ equals 1. Other well chosen functions $g$ provide functions $f$ having good cryptographic parameters. We analyze the constructed functions $f$, we provide a fast way to compute their output, we determine their algebraic normal forms and we show that, most often, their algebraic degree is optimal. We study their Walsh transform and their nonlinearity and algebraic immunity. We observe with computer investigations that this generalization of the HWB function allows to keep its quality of being fast to compute and having good enough algebraic immunity, while significantly improving its nonlinearity. The functions already obtained in the investigations provide a quite good (and never reached before) trade-off between speed and security. Further (probably difficult) work should allow obtaining, among such generalized HWB functions whose number is huge, still better filter functions to be used in stream ciphers.

Despite intensive research on Boolean functions for cryptography for over thirty years, there are very few known general constructions allowing to satisfy all the necessary criteria for ensuring the resistance against all the main known attacks on the stream ciphers using them. In this paper, we investigate the general construction of Boolean functions $f$ from vectorial functions, in which the support of $f$ equals the image set of an injective vectorial function $F$, that we call a parameterization of $f$. Any Boolean function whose Hamming weight is a power of 2, and in particular, every balanced Boolean function, can be obtained this way. We study five illustrations of this general construction. The three first correspond to known classes of functions (Maiorana-McFarland, majority functions and balanced functions in odd numbers of variables with optimal algebraic immunity). The two last correspond to new classes of Boolean functions: - sums of indicators of disjoint graphs of $(k,n-k$)-functions, - functions parameterized by highly nonlinear injective vectorial $(n-1,n)$-functions derived from functions due to Beelen and Leander. We study the cryptographic parameters (corresponding to the main criteria) of balanced Boolean functions, according to those of their parameterizations: the algebraic degree of $f$, that we relate to the algebraic degrees of $F$ and of its graph indicator, the nonlinearity of $f$, that we relate by a bound to the nonlinearity of $F$, and the algebraic immunity (AI), whose optimality is related to a natural question in linear algebra, and which may be handled (in two ways) by means of the graph indicator of $F$. We show how the algebraic degree and the nonlinearity of the parameterized function can be controlled. We revisit each of the five classes for each criterion. We show that the fourth class is very promising, thanks to a lower bound on the nonlinearity by means of the nonlinearity of the chosen $(k,n-k$)-functions. Its sub-class made of the sums of indicators of affine functions, for which we prove an upper bound on the nonlinearity, seems also interesting. The fifth class includes functions with optimal algebraic degree, good nonlinearity and good AI. We leave for future works the determination of simple effective sufficient conditions on $F$ ensuring that $f$ has a good AI, the completion of the study of the fourth class, the mathematical study of the AI and fast algebraic immunity of the functions in the fifth class, and the introduction and study of a class of parameterized functions having good parameters and whose output is fast to compute.

Event date: 2 December to 4 December 2021
Submission deadline: 31 August 2021
Notification: 31 October 2021