International Association
for Cryptologic Research

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.

It is convenient and common for schemes in the random oracle model to assume access to multiple random oracles (ROs), leaving to implementations the task (we call it oracle cloning) of constructing them from a single RO. The first part of the paper is a case study of oracle cloning in KEM submissions to the NIST Post-Quantum Cryptography standardization process. We give key-recovery attacks on some submissions arising from mistakes in oracle cloning, and find other submissions using oracle cloning methods whose validity is unclear. Motivated by this, the second part of the paper gives a theoretical treatment of oracle cloning. We give a definition of what is an "oracle cloning method" and what it means for such a method to "work," in a framework we call read-only indifferentiability, a simple variant of classical indifferentiability that yields security not only for usage in single-stage games but also in multi-stage ones. We formalize domain separation, and specify and study many oracle cloning methods, including common domain-separating ones, giving some general results to justify (prove read-only indifferentiability of) certain classes of methods. We are not only able to validate the oracle cloning methods used in many of the unbroken NIST PQC KEMs, but also able to specify and validate oracle cloning methods that may be useful beyond that.

Massively Parallel Computation (MPC) is a model of computation widely believed to best capture realistic parallel computing architectures such as large-scale MapReduce and Hadoop clusters. Motivated by the fact that many data analytics tasks performed on these platforms involve sensitive user data, we initiate the theoretical exploration of how to leverage MPC architectures to enable efficient, privacy-preserving computation over massive data. Clearly if a computation task does not lend itself to an efficient implementation on MPC even without security, then we cannot hope to compute it efficiently on MPC with security. We show, on the other hand, that any task that can be efficiently computed on MPC can also be securely computed with comparable efficiency. Specifically, we show the following results: • any MPC algorithm can be compiled to a communication-oblivious counterpart while asymp- totically preserving its round and space complexity, where communication-obliviousness ensures that any network intermediary observing the communication patterns learn no information about the secret inputs; • assuming the existence of Fully Homomorphic Encryption with a suitable notion of compact- ness and other standard cryptographic assumptions, any MPC algorithm can be compiled to a secure counterpart that defends against an adversary who controls not only intermediate network routers but additionally up to 1/3 − η fraction of machines (for an arbitrarily small constant η) — moreover, this compilation preserves the round complexity tightly, and preserves the space complexity upto a multiplicative security parameter related blowup. As an initial exploration of this important direction, our work suggests new definitions and proposes novel protocols that blend algorithmic and cryptographic techniques.

Viktoria hash is a compression function that generates a set of 512 bits from an arbitrary size input (limit of 2^480-1 bytes). This hash function contains some internal routines clearly inspired by AES and RC4 symmetric algorithms [14]. The new paradigm presents two major innovations: a fast preprocessing that initiates an internal state of 256!^2 permutations and a post-processing that guarantees a minimum number of executed rounds of 2^13. The pre-processing allows to differentiate very similar messages in the first runs of the algorithm. In the post-processing we have a safety barrier provided by a large number of rounds through a different structure of the main processing. The Viktoria algorithm seems to inaugurate a new design model in the construction of robust hash functions for some reasons, among them we highlight: the customization of the internal state according to each message, the elegance and efficiency of its main function and also a supposed high margin of safety provided by its post-processing function. Viktoria hash can also process bit oriented messages (whose last byte size is not complete) and generate larger hashes (1024, 1536, 2048 or larger) always as multiples of 512.