International Association
for Cryptologic Research

Proactive security is the notion of defending a distributed system against an attacker who compromises different devices through its lifetime, but no more than a threshold number of them at any given time. The emergence of threshold wallets for more secure cryptocurrency custody warrants an efficient proactivization protocol tailored to this setting. While many proactivization protocols have been devised and studied in the literature, none of them have communication patterns ideal for threshold wallets. In particular a $(t,n)$ threshold wallet is designed to have $t$ parties jointly sign a transaction (of which only one may be honest) whereas even the best current proactivization protocols require at least an additional $t$ honest parties to come online simultaneously to refresh the system.

In this work we formulate the notion of refresh with offline devices, where any $t$ parties (no honest majority) may proactivize the system at any time and the remaining $n-t$ offline parties can non-interactively ``catch up'' at their leisure. However due to the inherent unfairness of dishonest majority MPC, many subtle issues arise in realizing this pattern. We discuss these challenges, yet give a highly efficient protocol to upgrade a number of standard $(2,n)$ threshold signature schemes to proactive security with offline refresh. Our approach involves a threshold signature internal to the system itself, carefully interleaved with the larger threshold signing. We design our protocols so that they can augment existing implementations of threshold wallets for immediate use-- we show that proactivization does not have to interfere with their native mode of operation.

Our proactivization technique is compatible with Schnorr, EdDSA, and even sophisticated ECDSA protocols, while requiring no extra assumptions. By implementation we show that proactivizing two different recent $(2,n)$ ECDSA protocols incurs only 14% and 24% computational overhead respectively, less than 200 bytes, and no extra round of communication.

In this paper, we present a selfish mining attack on the multi-stage blockchain proposed by Palash Sarkar. We provide detailed analysis of computational wastage of honest miners and biased rewards achieved by the selfish pool. In our analysis, we introduce a spy inside an honest pool which is a trivial task. Our spy is responsible for leaking the information of the stage mining from the honest pool to the selfish pool. In our analysis, we consider all the possible configurations of mining namely sequential, parallel and pipelining. In all of these configurations, we show through our mathematical equations as to how a selfish miner can succeed in wasting the computation power of the honest miner and how he can influence the reward of mining. For completeness, we provide an algorithm for performing a selfish mining attack on all the scenarios on multi-stage blockchain. To thwart selfish mining on multi-stage blockchain we redesign the original verification algorithm by introducing a new parameter called the crypto-stamp. We present a new algorithm that uses crypto-stamp during the verification process of the mined stages or blocks and is able to detect with high probability whether the stages or blocks were kept private or not.

Authenticated encryption schemes are usually expected to offer confidentiality and authenticity. In case of release of unverified plaintext (RUP), an adversary gets separated access to the decryption and verification functionality, and has more power in breaking the scheme. Andreeva et al. (ASIACRYPT 2014) formalized RUP security using plaintext awareness, informally meaning that the decryption functionality gives no extra power in breaking confidentiality, and INT-RUP security, covering authenticity in case of RUP. We describe a single, unified model, called AERUP security, that ties together these notions: we prove that an authenticated encryption scheme is AERUP secure if and only if it is conventionally secure, plaintext aware, and INT-RUP secure. We next present ANYDAE, a generalization of SUNDAE of Banik et al. (ToSC 2018/3). ANYDAE is a lightweight deterministic scheme that is based on a block cipher with block size $n$ and arbitrary mixing functions that all operate on an $n$-bit state. It is particularly efficient for short messages, it does not rely on a nonce, and it provides maximal robustness to a lack of secure state. Whereas SUNDAE is not secure under release of unverified plaintext (a fairly simple attack can be mounted in constant time), ANYDAE is. We make handy use of the AERUP security model to prove that ANYDAE achieves both conventional security as RUP security, provided that certain modest conditions on the mixing functions are met. We describe two simple instances, called MONDAE and TUESDAE, that conform to these conditions and that are competitive with SUNDAE, in terms of efficiency and optimality.

Attribute-based proxy re-encryption~(ABPRE) allows a semi-trusted proxy to transform an encryption under an access-policy into an encryption under a new access policy, without revealing any information about the underlying message. Such a primitive facilitates fine-grained secure sharing of encrypted data in the cloud. In its key-policy flavor, the re-encryption key is associated with an access structure that specifies which type of ciphertexts can be re-encrypted. This paper proposes the first CCA secure key-policy attribute-based proxy re-encryption~(KP-ABPRE) scheme allowing monotonic access structures with constant ciphertext size for both the original and re-encrypted ciphertexts. Prior to our work, only two attempts were made towards the construction of an RCCA secure and a CCA secure KP-ABPRE scheme in the literature. We show that both the systems are vulnerable to replayable chosen-ciphertext and chosen-ciphertext attack respectively.

When a user shares his data by delegating decryption towards an access-policy, the proxy can collude with a malicious delegatee to attempt to obtain the private keys of the delegator during the delegation period. If the private keys are exposed, the security of the delegator's data is completely compromised. The proxy or the delegatee can obtain all confidential data of the delegator at will at any time, even after the delegation period is over. Hence, achieving collusion resistance is indispensable to real-world applications. In this paper, we show that our construction satisfies collusion resistance. Our scheme is proven CCA secure in the random oracle model, based on Bilinear Diffie-Hellman exponent assumptions.

Event date: 19 January to 22 January 2020
Submission deadline: 1 December 2019
Notification: 15 December 2019

Event date: 13 March 2020
Submission deadline: 2 December 2019
Notification: 13 January 2020

Event date: 16 August to 20 August 2020
Submission deadline: 11 February 2020
Notification: 8 May 2020

\textsf{HCTR}, proposed by Wang et al., is one of the most efficient candidates of tweakable enciphering schemes that turns an $n$-bit block cipher into a variable input length tweakable block cipher. Wang et al. have shown that \textsf{HCTR} offers a cubic security bound against all adaptive chosen plaintext and chosen ciphertext adversaries. Later in FSE 2008, Chakraborty and Nandi have improved its bound to $O(\sigma^2 / 2^n)$, where $\sigma$ is the total number of blocks queried and $n$ is the block size of the block cipher. In this paper, we propose \textbf{tweakable \textsf{HCTR}} that turns an $n$-bit tweakable block cipher to a variable input length tweakable block cipher by replacing all the block cipher calls of \textsf{HCTR} with tweakable block cipher. We show that when there is no repetition of the tweak, tweakable \textsf{HCTR} enjoys the optimal security against all adaptive chosen plaintext and chosen ciphertext adversaries. However, if the repetition of the tweak is limited, then the security of the construction remains close to the security bound in no repetition of the tweak case. Hence, it gives a graceful security degradation with the maximum number of repetition of tweaks.

Knowledge extraction, typically studied in the classical setting, is at the heart of several cryptographic protocols. The prospect of quantum computers forces us to revisit the concept of knowledge extraction in the quantum setting.

We introduce the notion of secure quantum extraction protocols. A secure quantum extraction protocol for an NP relation R is a classical interactive protocol between a sender and a receiver, where the sender gets the instance z, witness w while the receiver only gets the instance z. For any efficient quantum adversarial sender (who follows the protocol but can choose its own randomness), there exists a quantum extractor that can extract a witness w' such that (z,w') in R while a malicious receiver should not be able to output any valid witness. We study and construct two types of secure quantum extraction protocols.

- Quantum extraction protocols secure against quantum malicious receivers based on quantum fully homomorphic encryption satisfying some mild properties and quantum hardness of learning with errors. In this construction, we introduce a non black box technique in the quantum setting. All previous extraction techniques in the quantum setting were solely based on quantum rewinding.

- Quantum extraction protocols secure against classical malicious receivers based on quantum hardness of learning with errors. Moreover, our construction has the property that a malicious receiver cannot later, long after the protocol has been executed, use a quantum computer to extract a valid witness from the transcript of the protocol.

Both of our protocols have constant number of rounds. As an application, based on the quantum hardness of learning with errors, we present a construction of constant round quantum zero-knowledge argument systems for NP that guarantee security even against quantum malicious verifiers; however, our soundness only holds against classical probabilistic polynomial time adversaries. Prior to our work, such protocols were known based, additionally, on the assumptions of decisional Diffie-Hellman (or other cryptographic assumptions that do not hold against polynomial time quantum algorithms).

Blockchain protocols for cryptocurrencies offer secure payment transactions, yet their throughput pales in comparison to centralized payment systems such as VISA. Moreover, transactions incur fees that relatively hinder the adoption of cryptocurrencies for simple daily payments. Micropayment channels are second layer protocols that allow efficient and nearly unlimited number of payments between parties at the cost of only two transactions, one to initiate it and the other one to close it. Typically, the de-facto approach for micropayment channels on Ethereum is to utilize digital signatures which incur a constant gas cost but still relatively high due to expensive elliptic curve operations. Recently, ElSheikh et al. have proposed a protocol that utilizes hash chain which scales linearly with the channel capacity and has a lower cost compared to the digital signature based channel up to a capacity of 1000 micropayments. In this paper, we improve even more and propose a protocol that scales logarithmically with the channel capacity. Furthermore, by utilizing a variant of Merkle tree, our protocol does not require the payer to lock the entire balance at the channel creation which is an intrinsic limitation with the current alternatives. To assess the efficiency of our protocol, we carried out a number of experiments, and the results prove a positive efficiency and an overall low cost. Finally, we release the source code for prototype on GitHub.

This is an informal tutorial on the supersingular isogeny Diffie-Hellman protocol aimed at non-isogenists.

A reliable source of randomness is a critical element in many cryptographic systems. A public randomness beacon is a randomness source generated in a distributed manner that satisfies the following requirements: Liveness, Unpredictability, Unbiasability and Public Verifiability. In this work we introduce HERB: a new randomness beacon protocol based on additively homomorphic encryption. We show that this protocol meets the requirements listed above and additionaly provides Guaranteed Output Delivery. HERB has a modular structure with two replaceable modules: an homomorphic cryptosystem and a consensus algorithm. In our analysis we instantiate HERB using ElGamal encryption and a public blockchain. We implemented a prototype using Cosmos SDK to demonstrate the simplicity and efficiency of our approach. HERB allows splitting all protocol participants into two groups that can relate in any way. This property can be used for building more complex participation and reward systems based on the HERB solution.

Linear cryptanalysis is an important evaluation method for cryptographic primitives against key recovery attack. In this paper, we revisit the Walsh transformation for linear correlation calculation of modular addition, and an efficient algorithm is proposed to construct the input-output mask space of specified correlation weight. By filtering out the impossible large correlation weights in the first round, the search space of the first round can be substantially reduced. We introduce a concept of combinational linear approximation table (cLAT) for modular addition with two inputs. When one input mask is fixed, another input mask and the output mask can be obtained by the \textit{Spliting-Lookup-Recombination} approach. We first split the $n$-bit fixed input mask into several sub-vectors, then, to find the corresponding bits of other masks, and in the recombination phase, pruning conditions can be used. By this approach, a large number of search branches in the middle rounds can be pruned. With the combination of the optimization strategies and the branch-and-bound search algorithm, we can improve the search efficiency for linear characteristics on ARX ciphers. The linear hulls for SPECK32/48/64 with higher average linear potential ($ALP$) than existing results have been obtained. For SPARX variants, a 11-round linear trail and a 10-round linear hull have been found for SPARX-64, a 10-round linear trail and a 9-round linear hull are obtained for SPARX-128. For Chaskey, a 5-round linear trail with correlation of $2^{-61}$ have been obtained. For CHAM-64, the 34/35-round optimal linear characteristics with correlation of $2^{-31}$/$2^{-33}$ are found.

Motivated by the algorithm of differential probability calculation of Lipmaa and Moriai, we revisit the differential properties of modular addition. We propose an efficient approach to generate the input-output difference tuples with non-zero probabilities. A novel concept of combinational DDT and the corresponding construction algorithm are introduced to make it possible to obtain all valid output differences for fixed input differences. According to the upper bound of differential probability of modular addition, combining the optimization strategies with branch and bound search algorithm, we can reduce the search space of the first round and prune the invalid difference branches of the middle rounds. Applying this tool, the provable optimal differential trails covering more rounds for SPECK32/48/64 with tight probabilities can be found, and the differentials with larger probabilities are also obtained. In addition, the optimal differential trails cover more rounds than exisiting results for SPARX variants are obtained. A 12-round differential with a probability of $2^{-54.83}$ for SPARX-64, and a 11-round differential trail with a probability of $2^{-53}$ for SPARX-128 are found. For CHAM-64/128 and CHAM-128/*, the 39/63-round differential characteristics we find cover 3/18 rounds more than the known results respectively.

Reverse firewalls were introduced at Eurocrypt 2015 by Mironov and Stephens-Davidowitz, as a method for protecting cryptographic protocols against attacks on the devices of the honest parties. In a nutshell: a reverse firewall is placed outside of a device and its goal is to ``sanitize'' the messages sent by it, in such a way that a malicious device cannot leak its secrets to the outside world. It is typically assumed that the cryptographic devices are attacked in a ``functionality-preserving way'' (i.e. informally speaking, the functionality of the protocol remains unchanged under this attacks). In their paper, Mironov and Stephens-Davidowitz construct a protocol for passively-secure two-party computations with firewalls, leaving extension of this result to stronger models as an open question.

In this paper, we address this problem by constructing a protocol for secure computation with firewalls that has two main advantages over the original protocol from Eurocrypt 2015. Firstly, it is a multiparty computation protocol (i.e. it works for an arbitrary number $n$ of the parties, and not just for $2$). Secondly, it is secure in much stronger corruption settings, namely in the actively corruption model. More precisely: we consider an adversary that can fully corrupt up to $n-1$ parties, while the remaining parties are corrupt in a functionality-preserving way.

Our core techniques are: malleable commitments and malleable non-interactive zero-knowledge, which in particular allow us to create a novel protocol for multiparty augmented coin-tossing into the well with reverse firewalls (that is based on a protocol of Lindell from Crypto 2001).

In this work, we explore the problem of secure and efficient scalar multiplication on binary field using Kummer lines. Gaudry and Lubicz first introduced the idea of Kummer line in [12]. We investigate the possibilities of speedups using Kummer lines compared to binary Edwards curve and Weierstrass curves. Firstly, we propose a binary Kummer line $\mathsf{BKL}251$ on binary field $\mathbb{F}_{2^{251}}$ where the associated elliptic curve satisfies the required security conditions and offers 124.5-bit security which is same as the $\mathsf{BBE251}$ and $\mathsf{CURVE2251}$. $\mathsf{BKL}251$ also has small parameter and small base point. We implement the software of $\mathsf{BKL}251$ using the instruction ${\tt PCLMULQDQ}$ of modern Intel processors. For fair comparison, we also implement the software $\mathsf{BEd}251$ for binary Edwards curve introduced in [4] using the same field arithmetic library of the $\mathsf{BKL}251$ and thus this work also complements the works of [7,4]. In both the implementations, scalar multiplications take constant time which use Montgomery ladder. Binary Kummer line requires $4[\mathsf{M}]+5[\mathsf{S}]+1[\mathsf{C}]+1[\mathsf{B}]$ field operations for each ladder step where ladder step of binary Edwards curve requires $4[\mathsf{M}]+4[\mathsf{S}]+2[\mathsf{C}]+1[\mathsf{B}]$. Our experimental results show that fixed-base scalar multiplication of $\mathsf{BKL}251$ is $8.36\%-9.33\%$ faster than that of $\mathsf{BEd}251$. On the other hand, variable-base scalar multiplications take almost same time for both the curves (variable-base scalar multiplication of $\mathsf{BKL}251$ is $0.25\%-1.55\%$ faster than that of $\mathsf{BEd}251$).

Machine learning has started to be deployed in fields such as healthcare and finance, which involves dealing with a lot of sensitive data. This propelled the need for and growth of privacy-preserving machine learning (PPML). We propose an actively secure four-party protocol (4PC), and a framework for PPML, showcasing its applications on four of the most widely-known machine learning algorithms -- Linear Regression, Logistic Regression, Neural Networks, and Convolutional Neural Networks.

Our 4PC protocol tolerating at most one malicious corruption is practically efficient as compared to Gordon et al. (ASIACRYPT 2018) as the 4th party in our protocol is not active in the online phase, except input sharing and output reconstruction stages. Concretely, we reduce the online communication as compared to them by 1 ring element. We use the protocol to build an efficient mixed-world framework (Trident) to switch between the Arithmetic, Boolean, and Garbled worlds. Our framework operates in the offline-online paradigm over rings and is instantiated in an outsourced setting for machine learning, where the data is secretly shared among the servers. Also, we propose conversions especially relevant to privacy-preserving machine learning. With the privilege of having an extra honest party, we outperform the current state-of-the-art ABY3 (for three parties), in terms of both rounds as well as communication complexity.

The highlights of our framework include using a minimal number of expensive circuits overall as compared to ABY3. This can be seen in our technique for truncation, which does not affect the online cost of multiplication and removes the need for any circuits in the offline phase. Our B2A conversion has an improvement of $\mathbf{7} \times$ in rounds and $\mathbf{18} \times$ in the communication complexity. In addition to these, all of the special conversions for machine learning, e.g. Secure Comparison, achieve constant round complexity.

The practicality of our framework is argued through improvements in the benchmarking of the aforementioned algorithms when compared with ABY3. All the protocols are implemented over a 64-bit ring in both LAN and WAN settings. Our improvements go up to $\mathbf{187} \times$ for the training phase and $\mathbf{158} \times$ for the prediction phase when observed over LAN and WAN.

Searchable encryption can provide secure search over encrypted cloud-based data without infringing data confidentiality and data searcher privacy. In this work, we focus on a secure search service providing fine-grained and expressive search functionality, which can be seen as a general extension of searchable encryption and called attribute-based multi-keyword search (ABMKS). In most of the existing ABMKS schemes, the ciphertext size of keyword index (encrypted index) grows linearly with the number of the keyword associated with a file, so that the computation and communication complexity of keyword index is limited to O(m) , where m is the number of the keyword. To address this shortage, we propose the first ABMKS scheme through utilizing keyword dictionary tree and the subset cover, in such a way that the ciphertext size of keyword index is not dependent on the number of underlying keyword in a file. In our design, the complexity of computation and the complexity of the keyword index are at most O ( 2· log (n/2) ) for the worst case, but O(1) for the best case, where n is the number of keyword in a keyword dictionary. We also present the security and the performance analysis to demonstrate that our scheme is both secure and efficient in practice.

We consider the problem of amplifying two-party coin-tossing protocols: given a protocol where it is possible to bias the common output by at most $\rho$, we aim to obtain a new protocol where the output can be biased by at most $\rho^\star<\rho$. We rule out the existence of a natural type of amplifiers called oblivious amplifiers for every $\rho^\star<\rho$. Such amplifiers ignore the way that the underlying $\rho$-bias protocol works and can only invoke an oracle that provides $\rho$-bias bits.

We provide two proofs of this impossibility. The first is by a reduction to the impossibility of deterministic randomness extraction from Santha-Vazirani sources. The second is a direct proof that is more general and also rules outs certain types of asymmetric amplification. In addition, it gives yet another proof for the Santha-Vazirani impossibility.

Historically, fault diagnosis for integrated circuits has singularly dealt with reliability concerns. In contrast, a cryptographic circuit needs to be primarily evaluated concerning information leakage in the presence of maliciously crafted faults. While Differential Fault Attacks (DFAs) on symmetric ciphers have been known for over 20 years, recent developments have tried to structurally classify the attackers’ capabilities as well as the properties of countermeasures. Correct realization of countermeasures should still be manually verified, which is error-prone and infeasible for even moderate-size real-world designs. Here, we introduce the concept of Cryptographic Fault Diagnosis, which revises and shapes the notions of fault diagnosis in reliability testing to the needs of evaluating cryptographic implementations. Additionally, we present VerFI, which materializes the idea of Cryptographic Fault Diagnosis. It is a fully automated, open-source fault detection tool processing the gate-level representation of arbitrary cryptographic implementations. By adjusting the bounds of the underlying adversary model, VerFI allows us to rapidly examine the desired fault detection/correction capabilities of the given implementation. Among several case studies, we demonstrate its application on an implementation of LED cipher with combined countermeasures against side-channel analysis and fault-injection attacks (published at CRYPTO 2016). This experiment revealed general implementation flaws and undetectable faults leading to successful DFA on the protected design with full-key recovery.