International Association
for Cryptologic Research

We present advancements for interactive arguments with Hydra, a novel verifiable computation system. Hydra introduces two new disjoint interactive argument scheme protocols geared towards the efficient pipelining of circuit verification. The first is specific to subcircuits, where a deep circuit is broken up into smaller parts and proven concurrently. The second is a more general scheme where all layers of the circuit can be proven in parallel, removing the dependency on the layer-wise synchronous execution of the protocol. Compared to non-interactive SNARKs which rely on knowledge type assumptions (or the Random Oracle model) and theoretical non-interactive arguments based on standard assumptions that are not useful in practice, Hydra achieves a sweet spot with a practical approach. From standard assumptions, Hydra collapses the round complexity to polylogarithmic to the width of the circuit, but only incurs polylogarithmic blowup in bandwidth and verifier time complexity. We implement the full verification flow, including both protocols and a logic parser used to convert traditional logic circuit compilation outputs into provable layered arithmetic representations. We perform experimental evaluations of our proposals and demonstrate protocol time efficiency improvements of up to 34.8 times and 4.3 times respectively compared to traditional approaches on parallel hardware.

Using passwords for authentication has been proven vulnerable in countless security incidents. Hardware authentication tokens effectively prevent most password-related security issues and improve security indisputably. However, we would like to highlight that there are new threats from attackers with physical access which need to be discussed. Supply chain adversaries may manipulate devices on a large scale and install backdoors before they even reach end users. In evil maid scenarios, specific devices may even be attacked while already in use. Hence, we thoroughly investigate the security and trustworthiness of eight commercially available open source authentication tokens, including devices from the two market leaders: SoloKeys and Nitrokey. Unfortunately, we identify and practically verify significant vulnerabilities in all eight examined tokens. Some of them based on severe, previously undiscovered, vulnerabilities of three major microcontroller products which are used at a large scale in various products. Our findings clearly emphasize the significant threat from supply chain and evil maid scenarios since the attacks are practical and only require moderate attacker efforts. Fortunately, we are able to describe software-based countermeasures as effective improvements to retrofit the examined devices. To improve the security and trustworthiness of future authentication tokens, we also derive important general design recommendations.

Digital signatures have been widely used as building blocks for constructing complex cryptosystems. To facilitate the security analysis of a complex system, we expect the underlying building blocks to achieve desirable composability. Notably, Canetti (FOCS 2001) and then Maurer et al (TCC 2004) propose analysis frameworks, the Universal Composability framework for cryptographic protocols, and the indifferentiability framework for cryptographic objects.

In this paper, we develop a “lifting strategy”, which allows us to compile multiple existing practical signature schemes using cyclic group (e.g., Schnorr, Boneh-Boyen), to achieve a very stringent security guarantee, in an idealized model of the generic (bilinear) group, without introducing much extra efficiency loss. What's more interesting is that, in our design, even the involved idealized model does not exist, our compiled construction will still be able to achieve the classical notion of unforgeability.

To achieve both indifferentiability and good efficiency, we develop new techniques in generic (bilinear) group model.

Cryptographic accumulators are a crucial building block for a variety of applications where you need to represent a set of elements in a compact format while still being able to provide proofs of (non)membership. In this work, we give a number of accumulator constructions for the bilinear pairing setting in the trapdoor-based scenario, where a trusted manager maintains the accumulator. Using modular accumulator techniques, we first present the first optimally efficient (in terms of communication cost) dynamic, positive accumulators in the pairing setting. Additionally, we present a novel modular approach to construct universal accumulators that avoid costly non-membership proofs. We instantiate our generic construction and present the first universal accumulator in the bilinear pairing setting, that achieves constant parameter size, constant cost for element additions/deletions and witness generation by the manager, constant witness updates by the users and constant (non)membership verification. We finally show how our proposed universal accumulator construction can give rise to efficient ZK accumulators with constant non-membership witness updates.

In this work we challenge the common misconception that information-theoretic (IT) privacy is too impractical to be used in the real-world: we propose to build simple and $\textit{reusable}$ IT-encryption solutions whose only efficiency penalty (compared to computationally-secure schemes) comes from a large secret key size, which is often a rather minor inconvenience, as storage is cheap. In particular, our solutions are $\textit{stateless}$ and $\textit{locally computable at the optimal rate}$, meaning that honest parties do not maintain state and read only (optimally) small portions of their large keys with every use.

Moreover, we also propose a novel architecture for outsourcing the storage of these long keys to a network of semi-trusted servers, trading the need to store large secrets with the assumption that it is hard to simultaneously compromise too many publicly accessible ad-hoc servers. Our architecture supports $\textit{everlasting privacy}$ and $\textit{post-application security}$ of the derived one-time keys, resolving two major limitations of a related model for outsourcing key storage, called bounded storage model.

Both of these results come from nearly optimal constructions of so called $\textit{doubly-affine extractors}$: locally-computable, seeded extractors $\textbf{Ext}$(X,S) which are linear functions of X (for any fixed seed S), and protect against bounded affine leakage on X. This holds unconditionally, even if (a) affine leakage may $\textit{adaptively depend}$ on the extracted key R = $\textbf{Ext}$(X, S); and (b) the seed S is only $\textit{computationally}$ secure. Neither of properties are possible with general-leakage extractors.

The private simultaneous messages (PSM) model is a non-interactive version of the multiparty secure computation (MPC), which has been intensively studied to examine the communication cost of the secure computation. We consider its quantum counterpart, the private simultaneous quantum messages (PSQM) model, and examine the advantages of quantum communication and prior entanglement of this model.

In the PSQM model, $k$ parties $P_1,\ldots,P_k$ initially share a common random string (or entangled states in a stronger setting), and they have private classical inputs $x_1,\ldots, x_k$. Every $P_i$ generates a quantum message from the private input $x_i$ and the shared random string (entangled states), and then sends it to the referee $R$. Receiving the messages from the $k$ parties, $R$ computes $F(x_1,\ldots,x_k)$ from the messages. Then, $R$ learns nothing except for $F(x_1,\ldots,x_k)$ as the privacy condition.

We obtain the following results for this PSQM model. ($i$) We demonstrate that the privacy condition inevitably increases the communication cost in the two-party PSQM model as well as in the classical case presented by Applebaum, Holenstein, Mishra, and Shayevitz [Journal of Cryptology 33(3), 916--953 (2020)]. In particular, we prove a lower bound $(3-o(1))n$ of the communication complexity in PSQM protocols with a shared random string for random Boolean functions of $2n$-bit input, which is larger than the trivial upper bound $2n$ of the communication complexity without the privacy condition. ($ii$) We demonstrate a factor two gap between the communication complexity of PSQM protocols with shared entangled states and with shared random strings by designing a multiparty PSQM protocol with shared entangled states for a total function that extends the two-party equality function. ($iii$) We demonstrate an exponential gap between the communication complexity of PSQM protocols with shared entangled states and with shared random strings for a two-party partial function.

Symmetric-key cryptography is used widely due to its capability to provide a strong defense against diverse attacks; however, it is prone to cryptanalysis attacks. Therefore, we propose a novel and highly secure symmetric-key cryptography, symKrypt for short, to defend against diverse attacks and provide absolute security. Our proposed algorithm changes private keys in each block of communication, i.e., symKrypt uses multiple private keys to encrypt a single block of a message. Moreover, symKrypt keeps secret the bit mixing of the original message with the private keys. Also, the number of private keys is kept secret. In addition, the private keys are generated dynamically based on the initial inputs using a pseudo-random number generator which is highly unpredictable and secure. In this article, we theoretically analyze the capabilities of symKrypt and provide experimental demonstration using millions of private keys to prove its correctness. Furthermore, we demonstrate the proposed pseudo-random number generator algorithm experimentally in NIST SP 800-22 statistical test suite. Our propose pseudo-random number generator passes all 15 tests in the said test suite. symKrypt is the first model to use multiple private keys in encryption yet lightweight and powerful.

Unlike traditional and/or standardized ciphers, TFHE offers much space for the setup of its parameters. Not only the parameter choice affects the plaintext space size and security, it also greatly impacts the performance of TFHE, in particular, its bootstrapping. In this paper, we provide an exhaustive description of TFHE, including its foundations, (functional) bootstrapping and error propagation during all operations. In addition, we outline a bootstrapping scenario without the key switching step. Based on our thorough summary, we suggest an approach for the setup of TFHE parameters with particular respect to bootstrapping efficiency. Finally, we propose twelve setups of real-world TFHE parameters for six different scenarios with and without key switching, respectively, and we compare their performance. N.b.: This is a technical paper, which is mainly intended for researchers interested in TFHE. However, due to its self-containment, it shall be accessible also for readers with a basic knowledge of TFHE.

This paper introduces a new key space for CSIDH and a new algorithm for constant-time evaluation of the CSIDH group action. The key space is not useful with previous algorithms, and the algorithm is not useful with previous key spaces, but combining the new key space with the new algorithm produces speed records for constant-time CSIDH. For example, for CSIDH-512 with a 256-bit key space, the best previous constant-time results used 789000 multiplications and more than 200 million Skylake cycles; this paper uses 438006 multiplications and 125.53 million cycles.

We present the Internet Computer Consensus (ICC) family of protocols for atomic broadcast (a.k.a., consensus), which underpin the Byzantine fault-tolerant replicated state machines of the Internet Computer. The ICC protocols are leader-based protocols that assume partial synchrony, and that are fully integrated with a blockchain. The leader changes probabilistically in every round. These protocols are extremely simple and robust: in any round where the leader is corrupt (which itself happens with probability less than $1/3$), each ICC protocol will effectively allow another party to take over as leader for that round, with very little fuss, to move the protocol forward to the next round in a timely fashion. Unlike in many other protocols, there are no complicated subprotocols (such as "view change'' in PBFT) or unspecified subprotocols (such as "pacemaker'' in HotStuff). Moreover, unlike in many other protocols (such as PBFT and HotStuff), the task of reliably disseminating the blocks to all parties is an integral part the protocol, and not left to some other unspecified subprotocol. An additional property enjoyed by the ICC protocols (just like PBFT and HotStuff, and unlike others, such as Tendermint) is optimistic responsiveness, which means that when the leader is honest, the protocol will proceed at the pace of the actual network delay, rather than some upper bound on the network delay. We present three different protocols (along with various minor variations on each). One of these protocols (ICC1) is designed to be integrated with a peer-to-peer gossip sub-layer, which reduces the bottleneck created at the leader for disseminating large blocks, a problem that all leader-based protocols, like PBFT and HotStuff, must address, but typically do not. Our Protocol ICC2 addresses the same problem by substituting a low-communication reliable broadcast subprotocol (which may be of independent interest) for the gossip sub-layer.

Decentralized token exchanges allow for secure trading of tokens without a trusted third party. However, decentralization is mostly achieved at the expense of transaction privacy. For a fair exchange, transactions must remain private to hide the participants and volumes while maintaining the possibility for non-interactive execution of trades. In this paper we present a swap confidential transaction system (SwapCT) which is related to ring confidential transactions (e.g. used in Monero) but supports multiple token types to trade among and enables secure, partial transactions for non-interactive swaps. We prove that SwapCT is secure in a strict, formal model and present its efficient performance in a prototype implementation with logarithmic signature sizes for large anonymity sets. For our construction we design an aggregatable signature scheme which might be of independent interest. Our SwapCT system thereby enables a secure and private exchange for tokens without a trusted third party.

We consider threshold public-key encryption, where the decryption servers distributively hold the private key shares, and we need a threshold of these servers to decrypt the message (while the system remains secure when less than the threshold is corrupt). We investigate the notion of chosen-ciphertext secure threshold systems which has been historically hard to achieve. We further require the systems to be, both, adaptively secure (i.e., secure against a strong adversary making corruption decisions dynamically during the protocol), and non-interactive (i.e., where decryption servers do not interact amongst themselves but rather efficiently contribute, each, a single message). To date, only pairing-based implementations were known to achieve security in the standard security model without relaxation (i.e., without assuming the random oracle idealization) under the above stringent requirements. Here, we investigate how to achieve the above using other assumptions (in order to understand what other algebraic building blocks and mathematical assumptions are needed to extend the domain of encryption methods achieving the above). Specifically, we show realizations under the Decision Composite Residuosity (DCR) and Learning-With-Errors (LWE) assumptions.

Blockchain is a disruptive technology that promises a multitude of benefits such as transparency, traceability, and immutability. However, this unique bundle of key characteristics rapidly proved to be a double-edged sword that can put user privacy at risk. Unlike traditional systems, Bitcoin transactions are publicly and permanently recorded, and anyone can access the full history of the records. Despite using pseudonymous identities, an adversary can undermine the financial privacy of users and reveal their actual identities using advanced heuristics and techniques to identify eventual links between transactions, senders, receivers, and consumed services (e.g., online purchases). In this regard, a multitude of approaches has been proposed in an attempt to overcome financial transparency and enhance user anonymity. These techniques range from using mixing services to off-chain transactions and address different privacy issues. In this survey, we particularly focus on comparing and evaluating mixing techniques in the Bitcoin blockchain, present their limitations, and highlight the new challenges.

Byzantine fault tolerant (BFT) consensus protocols are traditionally developed to support reliable distributed computing. For applications where the protocol participants are economic agents, recent works highlighted the importance of accountability: the ability to identify participants who provably violate the protocol. We propose to evaluate the security of an accountable protocol in terms of its liveness resilience, the minimum number of Byzantine nodes when liveness is violated, and its accountable safety resilience, the minimum number of accountable Byzantine nodes when safety is violated. We characterize the optimal tradeoffs between these two resiliences in different network environments, and identify an availability-accountability dilemma: in an environment with dynamic participation, no protocol can simultaneously be accountably-safe and live. We provide a resolution to this dilemma by constructing an optimally-resilient accountability gadget to checkpoint a longest chain protocol, such that the full ledger is live under dynamic participation and the checkpointed prefix ledger is accountable. Our accountability gadget construction is black-box and can use any BFT protocol which is accountable under static participation. Using HotStuff as the black box, we implemented our construction as a protocol for the Ethereum 2.0 beacon chain, and our Internet-scale experiments with more than 4000 nodes show that the protocol can achieve the required scalability and has better latency than the current solution Gasper, while having the advantage of being provably secure. To contrast, we demonstrate a new attack on Gasper.

Verifiable registries allow clients to securely access a key-value mapping maintained by an untrusted server. Applications include distribution of public keys, routing information or software binaries. Existing proposals for verifiable registries rely on global invariants being audited whenever the registry is updated. Clients typically rely on trusted third-party auditors, as large registries become expensive to audit.

We propose several new protocols for client-auditable registries that enable efficient verification of many updates to the registry, removing the need for third-party auditors. Our solutions use incrementally-verifiable computation (IVC) and/or RSA accumulators. Our evaluation shows that our constructions meet practical throughput requirements ($60$ updates / second), which is $100\times$ faster than naive solutions using IVC. Clients save $100$--$10^4\times$ bandwidth and computation costs over prior solutions requiring auditing every update.

In response to ongoing discussions about data usage by companies and governments, and its implications for privacy, there is a growing demand for secure communication techniques. While during their advent, most messenger apps focused on features rather than security, this has changed in the recent years: Since then, many have adapted end-to-end encryption as a standard feature. One of the most popular solutions is the Signal messenger, which aims to guarantee forward secrecy (i.e. security of previous communications in case of leakage of long-term secrets) and future secrecy (i.e. security of future communications in case of leakage of short-term secrets). If every user uses exactly one device, it is known that Signal achieves forward secrecy and even post-compromise security (i.e. security of future communications in case of leakage of long-term secrets). But the Signal protocol also allows for the use of multiple devices via the Sesame protocol. This multi-device setting is typically ignored in the security analysis of Signal.

In this work, we discuss the security of the Signal messenger in this multi-device setting. We show that the current implementation of the device registration allows an attacker to register an own, malicious device, which gives them unrestricted access to all future communication of their victim, and even allows full impersonation. This directly shows that the current Signal implementation does not guarantee post-compromise security. We discuss several countermeasures, both simple ones aiming to increase detectability of our attack, as well as a broader approach that seeks to solve the root issue, namely the weak device registration flow.

Plactic key agreement is a new key agreement scheme that uses Knuth’s multiplication of semistandard tableaus from combinatorial algebra. The security of plactic key agreement relies on the difficulty of some computational problems, such as division of semistandard tableaus.

Division by erosion uses backtracking to divide tableaus. Division by erosion is estimated to be infeasible against public keys of 768 or more bytes. If division by erosion is the best attack against plactic key agreement, then secure plactic key agreement could be practical.

Correlated random variables are a key tool in cryptographic applications like secure multi-party computation. We investigate the power of a class of correlations that we term group correlations: A group correlation is a uniform distribution over pairs $(x,y) \in G^2$ such that $x+y\in S$, where $G$ is a (possibly non-abelian) group and $S$ is a subset of $G$. We also introduce bi-affine correlations and show how they relate to group correlations. We present several structural results, new protocols, and applications of these correlations. The new applications include a completeness result for black-box group computation, perfectly secure protocols for evaluating a broad class of black box ``mixed-groups'' circuits with bi-affine homomorphism, and new information-theoretic results. Finally, we uncover a striking structure underlying OLE: In particular, we show that OLE over $\mathrm{GF}(2^n)$, is isomorphic to a group correlation over $\mathbb{Z}_4^n$.

Blockchains maintain two types of data: Application data and consensus data. Towards long-term blockchain scalability, both of these must be pruned. While a large body of literature has explored the pruning of application data (UTXOs, account balances, and contract state), little has been said about the permanent pruning of consensus data (block headers). We present a protocol which allows pruning the blockchain by garbage collecting old blocks as they become unnecessary. These blocks can simply be discarded and are no longer stored by any miner. We show that all miners can be light miners with no harm to security. Our protocol is based on the notion of superblocks, blocks that have achieved an unusually high difficulty. We leverage them to represent underlying proof-of-work without ever illustrating it, storing it, or transmitting it. After our pruning is applied, the storage and communication requirements for consensus data is reduced exponentially.

We develop new probabilistic mathematical methods to analyze our protocol in the random oracle model. We prove our protocol is both secure and succinct under an uninterrupted honest majority assumption for $1/3$ adversaries. Our protocol is the first to achieve always secure, always succinct, and online Non-Interactive Proofs of Proof-of-Work, all necessary components for a logarithmic space mining scheme. Our work has applications beyond mining and also constitutes an improvement in state-of-the-art superlight clients and cross-chain bridges.

Symmetric key cryptography is applied in almost all secure communications to protect all sensitive information from attackers, for instance, banking, and thus, it requires extra attention due to diverse applications. Moreover, it is vulnerable to various attacks, for example, cryptanalysis attacks. Cryptanalysis attacks are possible due to a single-keyed encryption system. The state-of-the-art symmetric communication protocol uses a single secret key to encrypt/decrypt the entire communication to exchange data/message that poses security threats. Therefore, in this paper, we present a new secure communication protocol based on Diffie-Hellman cryptographic algorithms, called Stealth. It is a symmetric-key cryptographic protocol to enhance the security of modern communication with truly random numbers. Additionally, it applies a pseudo-random number generator. Initially, Stealth uses the Diffie-Hellman algorithm to compute four shared secret keys. These shared secret keys are used to generate four different private keys to encrypt for the first block of the message for symmetric communication. Stealth changes its private keys in each communication, making it very hard to break the security protocol. Moreover, the four shared secret keys create additional complexity for the adversary to overcome, and hence, it can provide highly tight security in communications. Stealth neither replaces the existing protocol nor authentication mechanism, but it creates another security layer to the existing protocol to ensure the security measurement's tightness.