International Association
for Cryptologic Research

This paper presents Foxtail+, a new shared-key protocol to securely authenticate resource constrained devices, such as Internet of things (IoT) devices. Foxtail+ is based on a previously proposed protocol to authenticate unaided humans, called the Foxtail protocol, which we modify for authenticating resource constrained devices. It uses a computationally lightweight function, called the Foxtail function, which makes it ideal for IoT nodes with low memory, computational, and/or battery resources. We introduce a new family of functions based on the Foxtail function, analyze its security in terms of the number of samples required to obtain the secret, and demonstrate how it is connected with the learning with rounding (LWR) problem. We then build the Foxtail+ protocol from this function family, secure against active adversaries. Finally, we implement and experimentally evaluate the performance of Foxtail+ against a similar alternate protocol, i.e., the modified version of the Hopper and Blum protocol called HB+, and a block cipher based protocol instantiated with AES. The experiments are run on an IoT device connected to a LoRa network which is an IoT specific Low-Power Wide-Area Network (LPWAN). We show that Foxtail+ outperforms HB+ in terms of overall communication and energy cost, and its parallel implementation is comparable to the AES-based protocol in terms of time and energy consumption. To our knowledge, we provide the first implementation of any member of the HB+ family of protocols that directly compares its performance against an AES-based protocol in terms of time and power consumption. Our experiments shed new light on some of the limitations of identification protocols based on lightweight primitives, of which Foxtail+ is a member, over block cipher based protocols.

We present in this paper a blind signature and its partially blind variant based on lattices assumptions. Blind signature is a cornerstone in privacy-oriented cryptography and we propose the first lattice based scheme without restart. Compare to related work, the key idea of our construction is to provide a trapdoor to the signer in order to let him perform some gaussian pre-sampling during the signature generation process, preventing this way to restart from scratch the whole protocol. We prove the security of our scheme under the ring k-SIS assumption, in the random oracle model. We also explain security issues in the other existing lattice-based blind signature schemes. Finally, we propose a partially blind variant of our scheme, which is done with no supplementary cost, as the number of elements generated and exchanged during the signing protocol is exactly the same.

Two-source non-malleable extractors are pseudorandom objects which extract randomness even when an adversary is allowed to learn the behavior of the extractor on tamperings of the input weak sources, and they have found important applications in non-malleable coding and secret sharing. We begin by asking how hard it is to improve upon the best known constructions of such objects (Chattopadhyay, Goyal, Li, STOC 2016, and Li, STOC 2017). We show that even small improvements to these constructions lead to explicit low-error two-source extractors for very low linear min-entropy, a longstanding open problem in pseudorandomness.

Given the result above in the information-theoretic setting, we turn to studying two-source non-malleable extractors in the computational setting, namely in the CRS model first considered in (Garg, Kalai, Khurana, Eurocrypt 2020). We enforce that both the sampling process for the input sources and the tampering functions must be efficient, but we do not necessarily put such a constraint on the adversary distinguishing the output of the extractor from uniform. We obtain results about two-source non-malleable extractors in the CRS model under different types of hardness assumptions:

- Under standard assumptions, we show that small improvements upon state-of-the-art statistical two-source non-malleable extractors also yield explicit low-error two-source non-malleable extractors in the CRS model for low min-entropy against computationally unbounded distinguishers. Remarkably, all previous results on computational extractors require much stronger assumptions; - Under a quasi-polynomial hardness assumption, we give explicit constructions of low-error two-source non-malleable extractors in the CRS model with much lower min-entropy requirements than their best statistical counterparts, against a computationally bounded distinguisher; - Assuming the existence of nearly optimal collision-resistant hash functions, we give a simple explicit construction of a low-error two-source non-malleable extractors in the CRS model for very low min-entropy, against a computationally unbounded distinguisher.

We present new non-interactive zero-knowledge argument systems (NIZK), based on standard assumptions that were previously not known to imply it. In particular, we rely on the hardness of both the learning parity with noise (LPN) assumption, and the existence of trapdoor hash functions (TDH, defined by Döttling et al., Crypto 2019). Such TDH can be based on a number of standard assumptions, including DDH, QR, DCR, and LWE. We revisit the correlation intractability (CI) framework for converting $\Sigma$-protocols into NIZK, and present a different strategy for instantiating it by putting together two new components. First, while prior works considered the search-complexity of the relations for which CI is sought,we consider their probabilistic representation. Namely, a distribution over lower-complexity functions that bitwise-computes the target function with all but small (constant) probability. The second component is a new perspective for quantifying the class of relations for which CI is achieved. We show that it is instructive to consider CI for approximable relations (CI-Apx) which is quantified by a class of relations, but requires CI to hold against any approximation of any relation in this class. We show that CI-Apx for just constant-degree polynomials suffices for NIZK, if the under-lying $\Sigma$-protocol is implemented using a suitable commitment scheme. We show that such a commitment scheme can be constructed based on LPN. We then show how to construct CI-Apx for constant-degree polynomials from any suitable TDH (with an enhanced correctness property that is satisfied by all existing TDH constructions).

The problem of secret-key based authentication under privacy and storage constraints on the source sequence is considered. The identifier measurement channels during authentication are assumed to be controllable via a cost-constrained action sequence. Single-letter inner and outer bounds for the key-leakage-storage-cost regions are derived for a generalization of a classic two-terminal key agreement model with an eavesdropper that observes a sequence that is correlated with the sequences observed by the legitimate terminals. The additions to the model are that the encoder observes a noisy version of a remote source, and the noisy output and the remote source output together with an action sequence are given as inputs to the measurement channel at the decoder. Thus, correlation is introduced between the noise components on the encoder and decoder measurements. The model with a secret-key generated by an encoder is extended to the randomized models, where a secret-key is embedded to the encoder. The results are relevant for several user and device authentication scenarios including physical and biometric identifiers with multiple measurements that provide diversity and multiplexing gains. To illustrate the behavior of the rate region, achievable (secret-key rate, storage-rate, cost) tuples are given for binary identifiers and measurement channels that can be represented as a set of binary symmetric subchannels. The gains from using an action sequence such as a large secret-key rate at a significantly small hardware cost, are illustrated to motivate the use of low-complexity transform-coding algorithms with cost-constrained actions.

Dwork and Naor (FOCS '00) defined ZAPs as 2-message witness-indistinguishable proofs that are public-coin. We relax this to ``ZAPs with private randomness'' (ZAPRs), where the verifier can use private coins to sample the first message (independently of the statement being proved), but the proof must remain publicly verifiable given only the protocol transcript. In particular, ZAPRs are reusable, meaning that the first message can be reused for multiple proofs without compromising security.

Known constructions of ZAPs from trapdoor permutations or bilinear maps are only computationally WI (and statistically sound). Two recent results of Badrinarayanan-Fernando-Jain-Khurana-Sahai and Goyal-Jain-Jin-Malavolta [EUROCRYPT '20] construct the first statistical ZAP arguments, which are statistically WI (and computationally sound), from the quasi-polynomial LWE assumption. Here, we construct statistical ZAPR arguments from the quasi-polynomial decision-linear (DLIN) assumption on groups with a bilinear map. Our construction relies on a combination of several tools, including the Groth-Ostrovsky-Sahai NIZK and NIWI [EUROCRYPT '06, CRYPTO '06, JACM '12], ``sometimes-binding statistically hiding commitments'' [Kalai-Khurana-Sahai, EUROCRYPT '18] and the ``MPC-in-the-head'' technique [Ishai-Kushilevitz-Ostrovsky-Sahai, STOC '07].

To maintain the availability of industrial control systems (ICS), it is important to robustly detect malware infection that spreads within the ICS network. In ICS, a host often communicates with the determined hosts; for instance, a supervisory control host observes and controls the same devices routinely via the network. Therefore, a communication request to the unused internet protocol (IP) address space, i.e. darknet, in the ICS network is likely to be caused by malware in the compromised host in the network. That is, darknet monitoring may enable us to detect malware that tries to spread indiscriminately within the network. On the other hand, advanced malware, such as malware determining target hosts of infection with reference to host lists in the networks, infects the confined hosts in the networks, and consequently evades detection by security sensors or honeypots. In this paper, we propose novel deception techniques that lure such malware to our sensor, by embedding the sensor information continuously in the lists of hosts in the ICS networks. In addition, the feasibility of the proposed deception techniques is shown through our simplified implementation by using actual malware samples: WannaCry and Conficker.

The right of an individual to request the deletion of their personal data by an entity that might be storing it -- referred to as the right to be forgotten -- has been explicitly recognized, legislated, and exercised in several jurisdictions across the world, including the European Union, Argentina, and California. However, much of the discussion surrounding this right offers only an intuitive notion of what it means for it to be fulfilled -- of what it means for such personal data to be deleted. In this work, we provide a formal definitional framework for the right to be forgotten using tools and paradigms from cryptography. In particular, we provide a precise definition of what could be (or should be) expected from an entity that collects individuals' data when a request is made of it to delete some of this data. Our framework captures several, though not all, relevant aspects of typical systems involved in data processing. While it cannot be viewed as expressing the statements of current laws (especially since these are rather vague in this respect), our work offers technically precise definitions that represent possibilities for what the law could reasonably expect, and alternatives for what future versions of the law could explicitly require. Finally, with the goal of demonstrating the applicability of our framework and definitions, we consider various natural and simple scenarios where the right to be forgotten comes up. For each of these scenarios, we highlight the pitfalls that arise even in genuine attempts at implementing systems offering deletion guarantees, and also describe technological solutions that provably satisfy our definitions. These solutions bring together techniques built by various communities.

A two-party fair coin-tossing protocol is a coin-tossing protocol that guarantees output to the honest party even when the other party aborts during the protocol execution. Cleve (STOC--1986) demonstrated that, even when the parties are computationally bounded, a fail-stop adversary can alter the output distribution of the honest party by (roughly) $1/r$ (in the statistical distance) in an $r$-message coin-tossing protocol. An optimal fair coin-tossing protocol ensures that no adversary can alter the output distribution beyond $1/r$.

In a seminal result, Moran, Naor, and Segev (TCC--2009) constructed the first optimal fair coin-tossing protocol using oblivious transfer protocols. Whether the existence of oblivious transfer protocols is a necessary computational hardness assumption for optimal fair coin-tossing remains one of the most fundamental open problems in theoretical cryptography. Results of Impagliazzo and Luby (FOCS--1989) and Cleve and Impagliazzo (1993) together imply that the existence of one-way functions is necessary for optimal fair coin-tossing. However, the sufficiency of the existence of one-way functions is not known.

Towards this research endeavor, our work proves a black-box separation of optimal fair coin-tossing from the existence of one-way functions. That is, the black-box use of one-way functions is unlikely to enable optimal fair coin-tossing. Following the standard Impagliazzo and Rudich (STOC--1989) approach, our work considers any $r$-message fair coin-tossing protocol in the random oracle model where the parties have unbounded computational power. We demonstrate a fail-stop attack strategy for one of the parties to alter the output distribution of the honest party by $1/\sqrt{r}$. Our result, therefore, proves that the $r$-message coin-tossing protocol of Blum (COMPCON--1982) and Cleve (STOC--1986), which uses one-way functions in a black-box manner, is qualitatively the best possible protocol.

Several previous works, for example, Dachman--Soled, Lindell, Mahmoody, and Malkin (TCC--2011), Haitner, Omri, and Zarosim (TCC--2013), and Dachman--Soled, Mahmoody, and Malkin (TCC--2014), made partial progress on this research problem by proving this black-box separation assuming some restrictions on the coin-tossing protocol. Our work diverges significantly from these previous approaches to prove this black-box separation in its full generality. The starting point is the recently introduced potential-based inductive proof techniques for demonstrating large gaps in martingales in the information-theoretic plain model. Our technical contribution lies in identifying a global invariant that enables the extension of this technique to the random oracle model.

Network latency is a significant source of inefficiency in interactive protocols. This work contributes towards the possibility of reducing the round complexity and communication complexity of secure computation protocols to a minimum. We introduce the concept of secure non-interactive simulation of joint distributions.

Two parties begin with multiple independent samples from a correlated randomness source. Next, our objective is to investigate what forms of joint distributions can Alice and Bob securely simulate without any further communication. This offline preprocessing step fits perfectly within the offline-online paradigm of secure computation, which enables general secure computation even against parties with unbounded computational power.

One may interpret this concept as imbuing the notion of non-interactive simulation of joint distributions, which initiated from the seminal works of G\'acs and K\"orner (1972), and Wyner (1975), in information theory with cryptographic security. This concept is stronger than merely a secure version of non-interactive correlation distillation as introduced by Mossel, O’Donnell, Regev, Steif, and Sudakov (2004) because secure private keys alone do not suffice to facilitate general secure computation. Alternatively, secure non-interactive simulation is a natural restriction of performing cryptography with one-way communication introduced by Garg, Ishai, Kushilevitz, Ostrovsky, and Sahai (2015), which also serves as a naturally arising base case for inductively building cryptographic primitives with minimum communication complexity.

In this work, we study samples from (1) $\mathsf{BSS}(\epsilon)$, that is the joint distribution $(X,Y)$, where $X$ is a uniform random bit and $Y$ is correlated bit such that $X\neq Y$ with probability $\epsilon\in(0,1/2)$, and (2) $\mathsf{BES}(\epsilon)$, that is the joint distribution $(X,Y)$, where $X$ is a uniform random bit, and $Y=X$ with probability $(1-\epsilon)$; otherwise $Y=\perp$, where $\epsilon\in(0,1)$.

Note that the reverse hypercontractivity and hardness of cryptography with one-way messages both rule out the possibility of realizing any $\mathsf{BES}$ sample from $\mathsf{BSS}$ samples. This impossibility result carries over to our secure non-interactive simulation as well. Furthermore, we prove that it is also impossible to securely and non-interactively simulate samples of $\mathsf{BSS}$ from $\mathsf{BES}$ samples as well. Note that this impossibility result both in the setting of non-interactive simulation and cryptography with one-way communication remains open.

Next, we prove that we can simulate a sample of $\mathsf{BES}(\epsilon')$ from multiple samples of $\mathsf{BES}(\epsilon)$ if and only if $(1-\epsilon')=(1-\epsilon)^k,$ for some $k\in\mathbb{N}$. We proceed by proving that all secure constructions must be linear, and, after that, the rate of the simulation is at most $1/k$.

Finally, we show the existence of securely and non-interactively simulating a sample of $\mathsf{BSS}(\epsilon')$ from $\mathsf{BSS}(\epsilon)$ if and only if $(1-2\epsilon')=(1-2\epsilon)^k,$ for some $k\in\mathbb{N}$. Interestingly, there are linear as well as (comparatively inefficient) non-linear constructions.

We prove a lower bound on the communication complexity of perfect maliciously secure multiparty computation, in the standard model with $n=3t+1$ parties of which $t$ are corrupted. We show that for any $n$ and all large enough $g \in \mathbb{N}$ there exists a Boolean circuit $C$ with $g$ gates, where any perfectly secure protocol implementing $C$ must communicate $\Omega(n g)$ bits. The results easily extends to constructing similar circuits over any fixed finite field. Our results also extend to the case where the threshold $t$ is suboptimal. Namely if $n= 3t+s$ the bound is $\Omega(ng/s)$, which corresponds to known optimizations via packed secret-sharing. Using known techniques, we also show an upper bound that matches the lower bound up to a constant factor (existing upper bounds are a factor $\log n$ off for Boolean circuits).

As IoT applications are increasingly being deployed, there comes along an ever increasing need for the security and privacy of the involved data. Since cryptographic implementations are used to achieve these goals, it is important for embedded software developers to take into consideration hardware attacks. Side Channel Analysis (SCA) and Fault Attacks (FA) are the main classes of such attacks, which can either reduce or even eliminate the security levels of an em-bedded design. Therefore, cryptographic implementations must address both of them at the same time. To this end, multiple solutions have been proposed to address both attacks in one solution, such as Dual Pre-charge Logic (DPL) and Encoding countermeasures. In this work, we discuss the advantages and disadvantages of the state of the art, concurrent SCA and FA countermeasures. Additionally, we propose a software countermeasure in order to provide protection against both types of attacks. The proposed countermeasure is a general approach, applicable to any byte-sliced cipher and any modern MCUs (32- and 64-bit). The proposed countermeasure is ap-plied to an AES S-BOX implementation, for a 32-bit MCU (ARM Cortex-M3). The countermeasure has been experimen-tally evaluated against Correlation Power Analysis (CPA) attacks for both platforms while its fault detection capabilities are theoretically described.

CONFISCA is the first SIMD-based cipher implementation methodology which can concurrently resist against Side Channel Attack (SCA) and Fault Injection (FI). Its promising strength is presented in a PRESENT cipher case study. It has a considerably less performance and memory overhead in comparison to the previous concurrent countermeasures. By having one instance of the cipher, CONFISCA can on-the-fly switch between its two modes of operation: The High-Performance and High-Security. This gives us the flexibility to trade performance/power with security, based on the actual needs.

Anonymous Committed Broadcast is a functionality that extends DC-nets and allows a set of clients to privately commit a message to set of servers, which can then simultaneously open all committed messages in a random ordering. Anonymity holds since no one can learn the ordering or the content of the client’s committed message.

We present Blinder, the first system that provides a scalable and fully robust solution for anonymous committed broadcast. Blinder maintains both properties of security (anonymity) and robustness (aka. ‘guaranteed output delivery’ or ‘availability’) in the face of a global active (malicious) adversary. Moreover, Blinder is censorship resistant, meaning that a honest client cannot be blocked from participating. Blinder obtains its security and scalability by carefully combining classical and state-of-the-art techniques from the fields of anonymous communication and secure multiparty computation (MPC). In order to demonstrate scalability, we evaluate Blinder with up to 1 million clients, up to 100 servers and a message size of up to 10 kilobytes. In addition, we show that it is a perfect fit to be implemented on a GPU. A GPU based implementation of Blinder with 5 servers, which accepts 1 million clients, incurs a latency of less than 8 minutes; faster by a factor of > 100 than the 3-servers Riposte protocol (SOSP ’15), which is not robust and not censorship resistant; we get an even larger factor when comparing to AsynchroMix and PowerMix (CCS ’19), which are the only constructions that guarantee fairness (or robustness in the online phase).

In CRYPTO 2018, Russell et al. introduced the notion of crooked indifferentiability to analyze the security of a hash function when the underlying primitive is subverted. They showed that the $n$-bit to $n$-bit function implemented using enveloped XOR construction ($\mathsf{EXor}$) with $3n+1$ many $n$-bit functions and $3n^2$- bit random initial vectors (iv) can be proven secure asymptotically in the crooked indifferentiability setting.

-We identify several major issues and gaps in the proof by Russel et al. We show that their proof does not work when the adversary makes queries related to multiple messages or in the case of intricate function dependent subversion. -We formalize new technique to prove crooked indifferentiability for multiple messages. Our technique can handle function dependent subversion. We apply our technique to provide a concrete proof for the $\mathsf{EXor}$ construction.

-We analyze crooked indifferentiability of the classical sponge construction. We show, using a simple proof idea, the sponge construction is a crooked-indifferentiable hash function using only $n$-bit random iv.

Supersingular isogeny key encapsulation (SIKE) protocol delivers promising public and secret key sizes over other post-quantum candidates. However, the huge computations form the bottleneck and limit its practical applications. The modular multiplication operation, which is one of the most computationally demanding operations in the fundamental arithmetics, takes up a large part of the computations in the protocol. In this paper, we propose an improved unconventional-radix finite-field multiplication (IFFM) algorithm which reduces the computational complexity by about 20% compared to previous algorithms. We then devise a new high-speed modular multiplier architecture based on the IFFM. It is shown that the proposed architecture can be extensively pipelined to achieve a very high clock speed due to its complete feedforward scheme, which demonstrates significant advantages over conventional designs. The FPGA implementation results show the proposed multiplier has about 67 times faster throughput than the state-of-the-art designs and more than 12 times better area efficiency than previous works. Therefore, we think that these achievements will greatly contribute to the practicability of this protocol.

Designing an efficient public-key cryptosystem supporting additive homomorphism is not an easy job. At Eurocrypt 2013, Joye and Libert proposed a method for generalizing the Goldwasser-Micali cryptosystem. Their work basically addressed the issue of the ciphertext expansion, which is quite large in the Goldwasser-Micali cryptosystem. In this paper, we generalize the quadratic residue theory to the cases of higher-power residue. We also provide some new efficient methods for computing a type of higher-power residue symbols, which gives a generic tool for constructing practical cryptographic schemes, protocols and systems. To illustrate this point, we utilize it to generalize and improve the Joye-Libert cryptosystem. We also generalize some well-known results on quadratic residue and use them to instantiate the subgroup indistinguishability assumption, which can be utilized to construct key-dependent security and auxiliary-input security schemes.

The $k$-SIDH protocol is a static-static isogeny-based key agreement protocol. At Mathcrypt 2018, Jao and Urbanik introduced a variant of this protocol which uses non-scalar automorphisms of special elliptic curves to improve its efficiency. In this paper, we provide a new adaptive attack on Jao-Urbanik's protocol. The attack is a non-trivial adaptation of Galbraith-Petit-Shani-Ti's attack on SIDH (Asiacrypt 2016) and its extension to $k$-SIDH by Dobson-Galbraith-LeGrow-Ti-Zobernig (IACR eprint 2019). Our attack provides a speedup compared to a naïve application of Dobson et al.'s attack to Jao-Urbanik's scheme, exploiting its inherent structure. Estimating the security of $k$-SIDH and Jao-Urbanik's variant with respect to these attacks, $k$-SIDH provides better efficiency.

Hybrid Public Key Encryption (HPKE) is a cryptographic primitive being standardized by the Crypto Forum Research Group (CFRG) within the Internet Research Task Force (IRTF). HPKE schemes combine asymmetric and symmetric cryptographic primitives for efficient authenticated encryption of arbitrary-sized plaintexts under a given recipient public key. This document presents a mechanized cryptographic analysis done with CryptoVerif, of all four HPKE modes, instantiated with a prime-order-group Diffie-Hellman Key Encapsulation Mechanism (KEM).

With the location-based services booming, the volume of spatial data inevitably explodes. In order to reduce local storage and computational overhead, users tend to outsource data and initiate queries to the cloud. However, sensitive data or queries may be compromised if cloud server has access to raw data and plaintext token. To cope with this problem, searchable encryption for geometric range is applied. Geometric range search has wide applications in many scenarios, especially the circular range search.

In this paper, we propose a practical and secure circular range search scheme (PSCS) to support searching for spatial data in a circular range. With Our scheme, a semi-honest cloud server will return the data for a given circular range correctly without revealing index privacy or query privacy. We propose a polynomial split algorithm which can decompose the inner product calculation neatly. Then, We formally define the security of our scheme and theoretically prove that it is secure under same-closeness-pattern chosen-plaintext attacks (CLS-CPA). In addition, we demonstrate the efficiency and accuracy through analysis and experiments compared with existing schemes.