International Association
for Cryptologic Research

Revocable hierarchical identity-based encryption (RHIBE) is an extension of HIBE that provides the efficient key revocation function by broadcasting an update key per each time period. Many RHIBE schemes have been proposed by combining an HIBE scheme and the tree-based revocation method, but a generic method for constructing an RHIBE scheme has not been proposed. In this paper, we show for the first time that it is possible to construct RHIBE schemes by generically combining underlying cryptographic primitives and tree-based revocation methods. We first generically construct an RHIBE-CS scheme by combining HIBE scheme and the complete subtree (CS) method, and prove the adaptive security of this scheme by using the adaptive security of the HIBE schemes. Next, we generically construct an RHIBE-SD scheme by combining HIBE and hierarchical single revocation encryption (HSRE) schemes, and the subset difference (SD) method to reduce the size of an update key. Finally, we generically construct an RHIBE-CS scheme with shorter ciphertexts by combining HIBE schemes with constant-size ciphertext and the CS method.

Cryptocurrencies have received a lot of research attention in recent years following the release of the first cryptocurrency Bitcoin. With the rise in cryptocurrency transactions, the need for smart contracts has also increased. Smart contracts, in a nutshell, are digitally executed contracts wherein some parties execute a common goal. The main problem with most of the current smart contracts is that there is no privacy for a party's input to the contract from either the blockchain or the other parties. Our research builds on the Hawk project that provides transaction privacy along with support for smart contracts. However, Hawk relies on a special trusted party known as a manager, which must be trusted not to leak each party's input to the smart contract. In this paper, we present a practical private smart contract protocol that replaces the manager with an MPC protocol such that the function to be executed by the MPC protocol is relatively lightweight, involving little overhead added to the smart contract function, and uses practical sigma protocols and homomorphic commitments to prove to the blockchain that the sum of the incoming balances to the smart contract matches the sum of the outgoing balances.

Running secure multiparty computation (MPC) protocols with hundreds or thousands of players would allow leveraging large volunteer networks (such as blockchains and Tor) and help justify honest majority assumptions. However, most existing protocols have at least a linear (multiplicative)dependence on the number of players, making scaling difficult. Known protocols with asymptotic efficiency independent of the number of parties (excluding additive factors) require expensive circuit transformations that induce large overheads.

We observe that the circuits used in many important applications of MPC such as training algorithms used to create machine learning models have a highly repetitive structure. We formalize this class of circuits and propose an MPC protocol that achieves O(|C|) total complexity for this class. We implement our protocol and show that it is practical and outperforms O(n|C|) protocols for modest numbers of players.

The recent work of Garg et al. from TCC'18 introduced the notion of registration based encryption (RBE). The principal motivation behind RBE is to remove the key escrow problem of identity based encryption (IBE), where the IBE authority is trusted to generate private keys for all the users in the system. Although RBE has excellent asymptotic properties, it is currently impractical. In our estimate, ciphertext size would be about 11 terabytes in an RBE deployment supporting 2 billion users. Motivated by this observation, our work attempts to reduce the concrete communication and computation cost of the current state-of-the-art construction. Our contribution is two-fold. First, we replace Merkle trees with crit-bit trees, a form of PATRICIA trie, without relaxing any of the original RBE efficiency requirements introduced by Garg et al. This change reduces the ciphertext size by 15% and the computation cost of decryption by 30%. Second, we observe that increasing RBE's public parameters by a few hundred kilobytes could reduce the ciphertext size by an additional 50%. Overall, our work decreases the ciphertext size by 57.5%.

The secure multi-device instant messaging ecosystem is diverse, varied, and underrepresented in academia. We create a systematization of knowledge which focuses on the challenges of multi-device messaging in a secure context and give an overview of the current situation in the multi-device setting. For that, we analyze messenger documentation, white papers, and research that deals with multi-device messaging. This includes a detailed description of different patterns for data transfer between devices as well as device management, i.e. how clients are cryptographically linked or unlinked to or from an account and how the initial setup can be implemented. We then evaluate different instant messengers with regard to relevant criteria, e.g. whether they achieve specific security, usability, and privacy goals. In the end, we outline interesting areas for future research.

Side-channel attacks that leak sensitive information through a computing device’s interaction with its physical environment have proven to be a severe threat to devices’ security, particularly when adversaries have unfettered physical access to the device. Traditional approaches for leakage detection measure the physical properties of the device. Hence, they cannot be used during the design process and fail to provide root cause analysis. An alternative approach that is gaining traction is to automate leakage detection by modeling the device. The demand to understand the scope, benefits, and limitations of the proposed tools intensifies with the increase in the number of proposals.

In this SoK, we classify approaches to automated leakage detection based on the model’s source of truth. We classify the existing tools on two main parameters: whether the model includes measurements from a concrete device and the abstraction level of the device specification used for constructing the model. We survey the proposed tools to determine the current knowledge level across the domain and identify open problems. In particular, we highlight the absence of evaluation methodologies and metrics that would compare proposals’ effectiveness from across the domain. We believe that our results help practitioners who want to use automated leakage detection and researchers interested in advancing the knowledge and improving automated leakage detection.

In a prior paper we introduced a new symmetric key encryption scheme called Short Key Random Encryption Machine (SKREM), for which we claimed excellent security guarantees. In this paper we present and briefly discuss some of its applications outside conventional data encryption. These are Secure Coin Flipping, Cryptographic Hashing, Zero-Leaked-Knowledge Authentication and Authorization and a Digital Signature scheme which can be employed on a block-chain. We also briefly recap SKREM-like ciphers and the assumptions on which their security are based. The above applications are novel because they do not involve public key cryptography. Furthermore, the security of SKREM-like ciphers is not based on hardness of some algebraic operations, thus not opening them up to specific quantum computing attacks.

It has long been known that cryptographic schemes offering provably unbreakable security exist - namely the One Time Pad (OTP). The OTP, however, comes at the cost of a very long secret key - as long as the plain-text itself. In this paper we propose an encryption scheme which we (boldly) claim offers the same level of security as the OTP, while allowing for much shorter keys, of size polylogarithmic in the computing power available to the adversary. The Scheme requires a large sequence of truly random words, of length polynomial in the both plain-text size and the logarithm of the computing power the adversary has. We claim that it ensures such an attacker cannot discern the cipher output from random data, except with small probability. We also show how it can be adapted to allow for several plain-texts to be encrypted in the same cipher output, with almost independent keys. Also, we describe how it can be used in lieu of a One Way Function.

Key-oblivious encryption (KOE) is a newly developed cryptographic primitive that randomizes the public keys of an encryption scheme in an oblivious manner. It has applications in designing accountable tracing signature (ATS) that facilitates the group manager to revoke the anonymity of traceable users in a group signature while preserving the anonymity of non-traceable users. Despite of its importance and strong application, KOE has not received much attention in the literature.

In this work, we introduce the first isogeny-based KOE scheme. Isogeny is a fairly young post-quantum cryptographic field with sophisticated algebraic structures and unique security properties. Our KOE scheme is resistant to quantum attacks and derives its security from Commutative Supersingular Decisional Diffie-Hellman (CSSDDH), which is an isogeny based hard problem. More concretely, we have shown that our construction exhibits key randomizability, plaintext indistinguishability under key randomization and key privacy under key randomization in the standard model adapting the security framework of [KM15]. Furthermore, we have manifested instantiation of our scheme from cryptosystem based on Commutative Supersingular Isogeny Diffie-Hellman (CSIDH-512) [BKV19]. Additionally, we demonstrate the utility of our KOE scheme by leveraging it to construct an isogeny-based ATS scheme preserving anonymity under tracing, traceability, non-frameability, anonymity with accountability and trace obliviousness in the random oracle model following the security framework of [LNWX19].

BIKE is a key encapsulation mechanism that entered the third round of the NIST post-quantum cryptography standardization process. This paper presents two constant-time implementations for BIKE, one tailored for the Intel Haswell and one tailored for the ARM Cortex-M4. Our Haswell implementation is much faster than the avx2 implementation written by the BIKE team: for bikel1, the level-1 parameter set, we achieve a 1.39x speedup for decapsulation (which is the slowest operation) and a 1.33x speedup for the sum of all operations. For bikel3, the level-3 parameter set, we achieve a 1.5x speedup for decapsulation and a 1.46x speedup for the sum of all operations. Our M4 implementation is more than two times faster than the non-constant-time implementation portable written by the BIKE team. The speedups are achieved by both algorithm-level and instruction-level optimizations.

This paper presents a constant-time implementation of Classic McEliece for ARM Cortex-M4. Specifically, our target platform is stm32f4-Discovery, a development board on which the amount of SRAM is not even large enough to hold the public key of the smallest parameter sets of Classic McEliece. Fortunately, the flash memory is large enough, so we use it to store the public key. For the level-1 parameter sets mceliece348864 and mceliece348864f, our implementation takes 582 199 cycles for encapsulation and 2 706 681 cycles for decapsulation. Compared to the level-1 parameter set of FrodoKEM, our encapsulation time is more than 80 times faster, and our decapsulation time is more than 17 times faster. For the level-3 parameter sets mceliece460896 and mceliece460896f, our implementation takes 1 081 335 cycles for encapsulation and 6 535 186 cycles for decapsulation. In addition, our implementation is also able to carry out key generation for the level-1 parameter sets and decapsulation for level-5 parameter sets on the board.

In most verifiable electronic voting schemes, one key step is the tally phase, where the election result is computed from the encrypted ballots. A generic technique consists in first applying (verifiable) mixnets to the ballots and then revealing all the votes in the clear. This however discloses much more information than the result of the election itself (that is, the winners) and may offer the possibility to coerce voters. In this paper, we present a collection of building blocks for designing tally-hiding schemes based on multi-party computations. As an application, we propose the first tally-hiding schemes with no leakage for four important counting functions: D'Hondt, Condorcet, STV, and Majority Judgment. We also unveil unknown flaws or leakage in several previously proposed tally-hiding schemes.

Fully homomorphic encryption (FHE) allows us to perform computations directly over encrypted data and can be widely used in some highly regulated industries. Gentry's bootstrapping procedure is used to refresh noisy ciphertexts and is the only way to achieve the goal of FHE up to now. In this paper, we optimize the LWE-based GSW-type bootstrapping procedure. Our optimization decreases the lattice approximation factor for the underlying worst-case lattice assumption from $\tilde{O}(N^{2.5})$ to $\tilde{O}(N^{2})$, and is time-efficient by a $O(\lambda)$ factor. Our scheme can also achieve the best factor in prior works on bootstrapping of standard lattice-based FHE by taking a larger lattice dimension, which makes our scheme as secure as the standard lattice-based PKE. Furthermore, in this work we present a technique to perform more operations per bootstrapping in the LWE-based FHE scheme. Although there have been studies to evaluate large FHE gates using schemes over ideal lattices, (i.e. using FHEW or TFHE), we are the first to study how to perform complex functions homomorphically over standard lattices.

Event date: 16 September 2021
Submission deadline: 1 June 2021
Notification: 14 July 2021

Dynamic searchable symmetric encryption (DSSE) has been widely recognized as a promising technique to delegate update and search queries over an outsourced database to an untrusted server while guaranteeing the privacy of data. Many efforts on DSSE have been devoted to obtaining a good tradeoff between security and performance. However, it appears that all existing DSSE works miss studying on what will happen if the DSSE client issues irrational update queries carelessly, such as duplicate update queries and delete queries to remove non-existent entries (that have been considered by many popular database system in the setting of plaintext). In this scenario, we find that (1) most prior works lose their claimed correctness or security, and (2) no single approach can achieve correctness, forward and backward security, and practical performance at the same time. To address this problem, we study for the first time the notion of robustness of DSSE. Generally, we say that a DSSE scheme is robust if it can keep the same correctness and security even in the case of misoperations. Then, we introduce a new cryptographic primitive named key-updatable pseudo-random function and apply this primitive to constructing ROSE, a robust DSSE scheme with forward and backward security. Finally, we demonstrate the efficiency of ROSE by analyzing its computation and communication complexities and testing its search performance. The experimental results show that ROSE has a very efficient search performance over a large dataset.

In an electronic voting procedure, mixing networks are used to ensure anonymity of the casted votes. Each node of the network re-encrypts the input list of ciphertexts and randomly permutes it in a process named shuffle, and must prove (in zero-knowledge) that the process was applied honestly. To maintain security of such a process in a post-quantum scenario, new proofs are based on different mathematical assumptions, such as lattice-based problems. Nonetheless, the best lattice-based protocols to ensure verifiable shuffling have linear communication complexity on $N$, the number of shuffled ciphertexts.

In this paper we propose the first sub-linear (on $N$) post-quantum zero-knowledge argument for the correctness of a shuffle, for which we have mainly used two ideas: arithmetic circuit satisfiability results from Baum \textit{et al.} (CRYPTO'2018) and Bene$\check{\text{s}}$ networks to model a permutation of $N$ elements. The achieved communication complexity of our protocol with respect to $N$ is $\mathcal{O}(\sqrt{N}\log^2(N))$, but we will also highlight its dependency on other important parameters of the underlying lattice ingredients.

Xifrat was a cryptosystem proposed about half a month ago. This paper demonstrate an attack that computes the mixing function without knowing its key.

In the wake of the global COVID-19 pandemic, video conference systems have become essential for not only business purposes, but also private, academic, and educational uses. Among the various systems, Zoom is the most widely deployed video conference system. In October 2020, Zoom Video Communications rolled out their end-to-end encryption (E2EE) to protect conversations in a meeting from even insiders, namely, the service provider Zoom. In this study, we conduct thorough security evaluations of the E2EE of Zoom (version 2.3.1) by analyzing their cryptographic protocols. We discover several attacks more powerful than those expected by Zoom according to their whitepaper. Specifically, if insiders collude with meeting participants, they can impersonate any Zoom user in target meetings, whereas Zoom indicates that they can impersonate only the current meeting participants. Besides, even without relying on malicious participants, insiders can impersonate any Zoom user in target meetings though they cannot decrypt meeting streams. In addition, we demonstrate several impersonation attacks by meeting participants or insiders colluding with meeting participants. Although these attacks may be beyond the scope of the security claims made by Zoom or may be already mentioned in the whitepaper, we reveal the details of the attack procedures and their feasibility in the real-world setting and propose effective countermeasures in this paper. Our findings are not an immediate threat to the E2EE of Zoom; however, we believe that these security evaluations are of value for deeply understanding the security of E2EE of Zoom.

Polynomial multiplication is one of the most time-consuming operations utilized in lattice-based post-quantum cryptography (PQC) schemes. CRYSTALS-KYBER is a lattice-based key encapsulation mechanism (KEM) and it was recently announced as one of the four finalists at round three in NIST's PQC Standardization. Therefore, efficient implementations of polynomial multiplication operation are crucial for high-performance CRYSTALS-KYBER applications. In this paper, we propose three different hardware architectures (lightweight, balanced, high-performance) that implement the NTT, Inverse NTT (INTT) and polynomial multiplication operations for the CRYSTALS-KYBER scheme. The proposed architectures include a unified butterfly structure for optimizing polynomial multiplication and can be utilized for accelerating the key generation, encryption and decryption operations of CRYSTALS-KYBER. Our high-performance hardware with 16 butterfly units shows up to 112×, 132× and 109× improved performance for NTT, INTT and polynomial multiplication, respectively, compared to the high-speed software implementations on Cortex-M4.

In this paper, we present a concretely efficient protocol for private set intersection (PSI) in the multi-party setting using oblivious pseudorandom function (OPRF). In fact, we generalize the approach used in the work of Chase and Miao [CRYPTO 2020] towards deploying a lightweight multi-point OPRF construction for two-party PSI. Our protocol only includes oblivious transfer (OT) extension and garbled Bloom filter as its main ingredients and avoids computationally expensive operations. From a communication pattern perspective, our protocol consists of two types of interactions. The first type is performed over a star-like communication graph in which one designated party interacts with all other parties via performing OTs as the sender. Besides, parties communicate through a path-like communication graph that involves sending a garbled Bloom filter from the first party to its neighboring party following the last one. This design makes our protocol to be highly scalable due to the independence of each party's complexity from the number of participating parties and thus causes a communication and computation complexities of $O(n\lambda k)$ where $n$ is the set size, $k$ is the number of hash functions, and $\lambda$ is the security parameter. Moreover, the asymptotic complexity of the designated party is $O(tn\lambda)$ which linearly scales with the number of parties. We prove the security of our protocol against semi-honest adversaries.