International Association
for Cryptologic Research

We construct public-coin time- and space-efficient zero-knowledge arguments for $\mathbf{NP}$. For every time $T$ and space $S$ non-deterministic RAM computation, the prover runs in time $T \cdot \mathrm{polylog}(T)$ and space $S \cdot \mathrm{polylog}(T)$, and the verifier runs in time $n \cdot \mathrm{polylog}(T)$, where $n$ is the input length. Our protocol relies on hidden order groups, which can be instantiated, assuming a trusted setup, from the hardness of factoring (products of safe primes), or, without a trusted setup, using class groups. The argument-system can heuristically be made non-interactive using the Fiat-Shamir transform.

Our proof builds on DARK (Bünz et al., Eurocrypt 2020), a recent succinct and efficiently verifiable polynomial commitment scheme. We show how to implement a variant of DARK in a time- and space-efficient way. Along the way we:

1. Identify a significant gap in the proof of security of DARK. 2. Give a non-trivial modification of the DARK scheme that overcomes the aforementioned gap. The modified version also relies on significantly weaker cryptographic assumptions than those in the original DARK scheme. Our proof utilizes ideas from the theory of integer lattices in a novel way. 3. Generalize Pietrzak's (ITCS 2019) proof of exponentiation ($\mathsf{PoE}$) protocol to work with general groups of unknown order (without relying on any cryptographic assumption).

In proving these results, we develop general-purpose techniques for working with (hidden order) groups, which may be of independent interest.

The deep learning-based side-channel analysis represents an active research domain. While it is clear that deep learning enables powerful side-channel attacks, the variety of research scenarios often makes the results difficult to reproduce.

In this paper, we present AISY - a deep learning-based framework for profiling side-channel analysis. Our framework enables the users to run the analyses and report the results efficiently while maintaining the results' reproducible nature. The framework implements numerous features allowing state-of-the-art deep learning-based analysis. At the same time, the AISY framework allows easy add-ons of user-custom functionalities.

Constant advancements in quantum computing bring closer the reality of current public key encryption schemes becoming computationally feasible to be broken. Many developers working in the industry are just finding out about this and will be rapid to look into changing their web applications to be secure in the quantum era. This paper presents a tried and tested construction for a quantum-resistant, end-to-end encryption scheme which has been implemented in an online web application. The implementation is shown to work well without significant impact on the performance time in comparison to its pre-quantum counterpart.

CRYSTALS-Dilithium as a lattice-based digital signature scheme has been selected as a finalist in the PQC standardization process of NIST. As part of this selection, a variety of software implementations have been evaluated regarding their performance and memory requirements for platforms like x86 or ARM Cortex-M4. In this work, we present a first set of FPGA implementations for the low-end Xilinx Artix-7 platform, evaluating the peculiarities of the scheme in hardware, reflecting all available round-3 parameter sets. As a key component in our analysis, we present results for a specifically adapted NTT core for the Dilithium cryptosystem, optimizing this component for an optimal LUT and FF utilization by efficient use of special purpose DSPs. Presenting our results, we aim to shed further light on the performance of lattice-based cryptography in low-cost and high-throughput configurations and their respective potential use-cases in practice.

The MPC-in-the-head construction (Ishai et al., STOC'07) give zero-knowledge proofs from secure multiparty computation (MPC) protocols. This paper presents an efficient MPC protocol for permuting a vector of values, making use of the relaxed communication model that can be handled by the MPC-in-the-head construction. Our construction allows more efficient ZK proofs for relations expressed in the Random Access Machine (RAM) model. As a standalone application of our construction, we present batch anonymizable ring signatures.

In this work we construct for the first time a delegation scheme for arithmetic circuits with proof-size and verification complexity comparable to those of pairing based zk-SNARKS (e.g. Gennaro et al. at Eurocrypt 2013 or Groth at Eurocrypt 2016), but based on standard assumptions. Each proof comprises $O(1)$ group elements of a bilinear group and verification requires $O(1)$ pairings plus $n$ exponentiations, where $n$ is the number of inputs. Soundness can be proven under any Matrix Diffie-Hellman (MDDH) assumption of size $k\geq 2$. The size of the reference string as well as the prover's complexity is quadratic in the size of the circuit.

Our techniques combine the ideas for constructing delegation schemes of Paneth and Rothblum (TCC 2017), and then refined by Kalai et al. (STOC 2019), with the so called Quasi-Adaptive NIZK arguments for linear languages (Jutla and Roy at Asiacrypt 2014 and Crypto 2015, Libert et al. Eurocrypt 2015, Kiltz and Wee Eurocrypt 2015) and for quadratic languages (González et al. at Asiacrypt 2015 and 2019). We obtain a delegation scheme with asymptotically shorter proofs and verification.

Our construction can be turned into a NIZK argument for NP of size $n+O(1)$ group elements under the same assumptions and can be used to construct zk-SNARKs from quantitatively weaker assumptions than the state of the art. Additionally, the NIZK argument for NP yields a compact NIZK for NP with proof size linear in the size of the witness by using the same techniques and improving on Katsumata et al. (Crypto 2019 and Eurocrypt 2020) which has proof size linear in the size of the circuit.

Quantum computers are about to herald a new age of cryptography. As a fundamental building block in today’s digitalized world, Digital Signature Schemes (DSS) provide the ability to authenticate messages exchanged over untrusted channels. Unfortunately, virtually all currently used DSS are built upon mathematical problems that can efficiently be solved using quantum computers, thus rendering schemes such as RSA and ECC insecure. Due to its conservative security properties, the eXtended Merkle Signature Scheme (XMSS) is an outstanding candidate for a quantum-secure DSS which has already been standardized by NIST and IETF.

In this paper we present the first full hardware accelerator for XMSS whose generic design approach allows matching the requirements of several projected use-cases. In particular, we provide a full design exploration regarding the choice of parameters and hash functions to identify configurations for optimal performance and area utilization.

Dynamic group signature (DGS) allows a user to generate a signature on behalf of a group, while preserving anonymity. Although many existing DGS schemes have been proposed in the random oracle model for achieving efficiency, their security proofs require knowledge extractors that cause loose security reductions. In this paper, we first propose a new practical DGS scheme whose security can be proven without knowledge extractors in the random oracle model. Moreover, our scheme can also be proven in the strong security model where an adversary is allowed to generate group managers’ keys maliciously. The efficiency of our scheme is comparable to existing secure DGS schemes in the random oracle model using knowledge extractors. The security of our scheme is based on a new complexity assumption that is obtained by generalizing the Pointcheval-Sanders (PS) assumption. Although our generalized PS (GPS) assumption is interactive, we prove that, under the symmetric discrete logarithm (SDL) assumption, the new GPS assumption holds in the algebraic group model.

Schnorr's signature scheme provides an elegant method to derive signatures with security rooted in the hardness of the discrete logarithm problem, which is a well-studied assumption and conducive to efficient cryptography. However, unlike pairing-based schemes which allow arbitrarily many signatures to be aggregated to a single constant sized signature, achieving significant non-interactive compression for Schnorr signatures and their variants has remained elusive. This work shows how to compress a set of independent EdDSA/Schnorr signatures to roughly half their naive size. Our technique does not employ generic succinct proofs; it is agnostic to both the hash function as well as the specific representation of the group used to instantiate the signature scheme. We demonstrate via an implementation that our aggregation scheme is indeed practical. Additionally, we give strong evidence that achieving better compression would imply proving statements specific to the hash function in Schnorr's scheme, which would entail significant effort for standardized schemes such as SHA2 in EdDSA. Among the others, our solution has direct applications to compressing Ed25519-based blockchain blocks because transactions are independent and normally users do not interact with each other.

We study post-quantum zero-knowledge (classical) protocols that are sound against quantum resetting attacks. Our model is inspired by the classical model of resetting provers (Barak-Goldreich-Goldwasser-Lindell, FOCS `01), providing a malicious efficient prover with oracle access to the verifier's next-message-function, fixed to some initial random tape; thereby allowing it to effectively reset (or equivalently, rewind) the verifier. In our model, the prover has quantum access to the verifier's function, and in particular can query it in superposition. The motivation behind quantum resettable soundness is twofold: First, ensuring a strong security guarantee in scenarios where quantum resetting may be possible (e.g., smart cards, or virtual machines). Second, drawing intuition from the classical setting, we hope to improve our understanding of basic questions regarding post-quantum zero knowledge. We prove the following results: Black-Box Barriers: Quantum resetting exactly captures the power of black-box zero knowledge quantum simulators. Accordingly, resettable soundness cannot be achieved in conjunction with black-box zero knowledge, except for languages in $\BQP$. Leveraging this, we prove that constant-round public-coin, or three message, protocols cannot be black-box post-quantum zero-knowledge. For this, we show how to transform such protocols into quantumly resettably sound ones. The transformations are similar to classical ones, but their analysis is significantly more challenging due to the essential difference between classical and quantum resetting.

A Resettably-Sound Non-Black-Box Zero-Knowledge Protocol: Under the (quantum) Learning with Errors assumption and quantum fully-homomorphic encryption, we construct a post-quantum resettably-sound zero knowledge protocol for $\NP$. We rely on non-black-box simulation techniques, thus overcoming the black-box barrier for such protocols.

From Resettable Soundness to The Impossibility of Quantum Obfuscation: Assuming one-way functions, we prove that any quantumly-resettably-sound zero-knowledge protocol for $\NP$ implies the impossibility of quantum obfuscation. Combined with the above result, this gives an alternative proof to several recent results on quantum unobfuscatability.

This article discusses the decoding of Gabidulin codes and shows how to extend the usual decoder to any supercode of a Gabidulin code at the cost of a significant decrease of the decoding radius. Using this decoder, we provide polynomial time attacks on the rank–metric encryption schemes Ramesses and Liga.

In this paper, we improve the theoretical background of the attacks on the DSA schemes given in [1, 29], and we present some new more practical attacks.

We study the round complexity of secure multiparty computation (MPC) in the challenging model where full security, including guaranteed output delivery, should be achieved at the presence of an active rushing adversary who corrupts up to half of parties. It is known that 2 rounds are insufficient in this model (Gennaro et al., Crypto 2002), and that 3 round protocols can achieve computational security under public-key assumptions (Gordon et al., Crypto 2015; Ananth et al., Crypto 2018; and Badrinarayanan et al., ASIACRYPT 2020). However, despite much effort, it is unknown whether public-key assumptions are inherently needed for such protocols, and whether one can achieve similar results with security against computationally-unbounded adversaries.

In this paper, we use Minicrypt-type assumptions to realize 3-round MPC with full and active security at the presence of honest-majority. Our protocols come in two flavors: standard computational security and online-computational security with statistical everlasting security, i.e., the protocol is secure against adversaries that are computationally unlimited after the protocol execution. Specifically, we prove the following results:

- (Statistical everlasting security) Every NC1 functionality can be computed in 3 rounds given a hash function that is modeled as a random oracle. The random oracle can be replaced with a common reference string (CRS) and a family of hash functions for which it is hard to find inputs that are correlated under some explicit sparse algebraically-simple relation R. We can further relax the assumption on the hash function to standard collision-resistance if the adversary is only semi-rushing, i.e., in each round at least one, a-priory unknown, honest party speaks after the adversary.

- (Computational security) Every efficiently-computable function can be realized in 3 rounds assuming non-interactive commitments (NICOM) and R-intractable hash function. The former assumption follows from the existence of injective one-way functions, and the latter can be completely removed if the adversary is semi-rushing.

This paper presents Checklist, a system for private blocklist lookups. In Checklist, a client can determine whether a particular string appears on a server-held list of blocklisted strings, without leaking its string to the server. Checklist is the first blocklist-lookup system that (1) leaks no information about the client’s string to the server and (2) allows the server to respond to the client’s query in time sublinear in the blocklist size. To make this possible, we construct a new two-server private-information-retrieval protocol that is both asymptotically and concretely faster, in terms of server-side time, than those of prior work. We evaluate Checklist in the context of Google’s “Safe Browsing” blocklist, which all major browsers use to prevent web clients from visiting malware-hosting URLs. Today, lookups to this blocklist leak partial hashes of a subset of clients’ visited URLs to Google’s servers. We have modified Firefox to perform Safe-Browsing blocklist lookups via Checklist servers, which eliminate the leakage of partial URL hashes from the Firefox client to the blocklist servers. This privacy gain comes at the cost of increasing communication by a factor of 3.3×, and the server-side compute costs by 9.8×. Use of our new PIR protocol reduces server-side costs by 6.7×, compared to what would be possible prior state-of-the-art two-server PIR.

Single Secret Leader Election (SSLE) protocols allow a set of users to elect a leader among them so that the identity of the winner remains secret until she decides to reveal herself. This notion was formalized and implemented in a recent result by Boneh, et al. (ACM Advances on Financial Technology 2020) and finds important applications in the area of Proof of Stake blockchains. In this paper we propose new solutions to the problem that advance the state of the art both from a theoretical and a practical perspective. On the theoretical front, we propose a definition of SSLE in the universal composability framework. We believe this to be the right setting for highly concurrent contexts such as those of many blockchain-related applications. Next, we propose a UC-realization of SSLE from public key encryption with keyword search (PEKS) and based on the ability of distributing the PEKS key generation and encryption algorithms. Finally, we present an efficient MPC-friendly PEKS that allows us to efficiently instantiate the abstract scheme. Our concrete construction compares favorably with previous work (both in terms of computational costs and in terms of overall communication overhead) while guaranteeing much stronger composability guarantees.

One of the primary research challenges in Attribute-Based Encryption (ABE) is constructing and proving cryptosystems that are adaptively secure. To date the main paradigm for achieving adaptive security in ABE is dual system encryption. However, almost all such solutions in bilinear groups rely on (variants of) either the subgroup decision problem over composite order groups or the decision linear assumption. Both of these assumptions are decisional rather than search assumptions and the target of the assumption is a source or bilinear group element. This is in contrast to earlier selectively secure ABE systems which can be proven secure from either the decisional or search Bilinear Diffie-Hellman assumption. In this work we make progress on closing this gap by giving a new ABE construction for the subset functionality and prove security under the Search Bilinear Diffie-Hellman assumption.

We first provide a framework for proving adaptive security in Attribute-Based Encryption systems. We introduce a concept of ABE with deletable attributes where any party can take a ciphertext encrypted under the attribute string $x \in \{0, 1\}^n$ and modify it into a ciphertext encrypted under any string $x' \in \{0, 1, \bot\}^n$ where $x'$ is derived by replacing any bits of $x$ with $\bot$ symbols (i.e. ``deleting" attributes of $x$). The semantics of the system are that any private key for a circuit $C$ can be used to decrypt a ciphertext associated with $x'$ if none of the input bits read by circuit $C$ are $\bot$ symbols and $C(x') = 1$.

We show a pathway for combining ABE with deletable attributes with constrained psuedorandom functions to obtain adaptively secure ABE building upon the recent work of Tsabary. Our new ABE system will be adaptively secure and be a ciphertext-policy ABE that supports the same functionality as the underlying constrained PRF as long as the PRF is ``deletion conforming". Here we also provide a simple constrained PRF construction that gives subset functionality.

Our approach enables us to access a broader array of Attribute-Based Encryption schemes support deletion of attributes. For example, we show that both the Goyal~et al.~(GPSW) and Boyen ABE schemes can trivially handle a deletion operation. And, by using a hardcore bit variant of GPSW scheme we obtain an adaptively secure ABE scheme under the Search Bilinear Diffie-Hellman assumption in addition to pseudo random functions in NC1. This gives the first adaptively secure ABE from a search assumption as all prior work relied on decision assumptions over source group elements.

Decentralizing trust is a prominent principle in the design of end-to-end encryption and cryptocurrency systems. A common issue in these applications is that users possess critical secrets, and users can lose precious data or assets if these secrets are lost. This issue remains a pain-point in the adoption of these systems. Existing approaches to solve this issue such as backing up user secrets through a centralized service or distributing them across N mutually distrusting servers to preserve decentralized trust are either introducing a central point of attack or face usability issues by requiring users to authenticate N times---once to each of the N servers.

We present N-for-1 Auth, a system that enables a user to authenticate to N servers independently, with the work of only one authentication. N-for-1 Auth provides the same user experience in the distributed trust setting to the user experience in a typical centralized system.

While numerous physically unclonable functions (PUFs) were proposed in recent years, the conventional PUF-based authentication model is centralized by the data of challenge-response pairs (CRPs), particularly when $n$-party authentication is required. In this work, we propose a novel concept of clonable PUF (CPUF), wherein two or more PUFs having equivalent responses are manufactured to facilitate decentralized authentication. By design, cloning is only possible in the fabrication period and the responses are determined based on the variability induced during the fabrication. We establish the usage model and the circuit design of CPUFs. Numerical experiments using a circuit simulator show an ideal matching rate of responses between the CPUFs.

The ever-growing size of the Bitcoin UTXO state is a factor preventing nodes with limited storage capacity from validating transactions. Cryptographic accumulators, such as Merkle trees, offer a viable solution to the problem. Full nodes create a Merkle tree from the UTXO set, while stateless nodes merely store the root of the Merkle tree. When provided with a proof, stateless nodes can verify that a transaction's inputs belong to the UTXO set. In this work, we present a systematic study of Merkle tree based accumulators, with a focus on factors that reduce the proof size. Based on the observation that UTXOs typically have a short lifetime, we propose that recent UTXOs be co-located in the tree. When proofs for different transactions are batched, such a design reduces the per-transaction proof size. We provide details of our implementation of this idea, describing certain optimizations that further reduce the proof size in practice. On Bitcoin data before August 2019, we show that our design achieves a 4.6x reduction in proof size vis-a-vis UTREEXO [Dryja 2019], which is a different Merkle-tree based system designed to support stateless nodes.

We present a non-interactive publicly verifiable secret sharing scheme where a dealer can construct a Shamir secret sharing of a field element and confidentially yet verifiably distribute shares to multiple receivers. We also develop a non-interactive publicly verifiable resharing scheme where existing share holders of a Shamir secret sharing can create a new Shamir secret sharing of the same secret and distribute it to a set of receivers in a confidential, yet verifiable manner.

A public key may be associated with the secret being shared in the form of a group element raised to the secret field element. We use our verifiable secret sharing scheme to construct a non-interactive distributed key generation protocol that creates such a public key together with a secret sharing of the discrete logarithm. We also construct a non-interactive distributed resharing protocol that preserves the public key but creates a fresh secret sharing of the secret key and hands it to a set of receivers, which may or may not overlap with the original set of share holders.

Our protocols build on a new pairing-based CCA-secure public-key encryption scheme with forward secrecy. As a consequence our protocols can use static public keys for participants but still provide compromise protection. The scheme uses chunked encryption, which comes at a cost, but the cost is offset by a saving gained by our ciphertexts being comprised only of source group elements and no target group elements. A further efficiency saving is obtained in our protocols by extending our single-receiver encryption scheme to a multi-receiver encryption scheme, where the ciphertext is up to a factor 5 smaller than just having single-receiver ciphertexts.

The non-interactive key management protocols are deployed on the Internet Computer to facilitate the use of threshold BLS signatures. The protocols provide a simple interface to remotely create secret-shared keys to a set of receivers, to refresh the secret sharing whenever there is a change of key holders, and provide proactive security against mobile adversaries.