International Association
for Cryptologic Research

Many isogeny-based cryptosystems are believed to rely on the hardness of the Supersingular Decision Diffie-Hellman (SSDDH) problem. However, most cryptanalytic efforts have treated the hardness of this problem as being equivalent to the more generic supersingular $\ell^e$-isogeny problem --- an established hard problem in number theory.

In this work, we shine some light on the possibility that the combination of two additional pieces of information given in practical SSDDH instances --- the image of the torsion subgroup, and the starting curve's endomorphism ring --- can lead to better attacks cryptosystems relying on this assumption. We show that SIKE/SIDH are secure against our techniques. However, in certain settings, e.g., multi-party protocols, our results may suggest a larger gap between the security of these cryptosystems and the $\ell^e$-isogeny problem.

Our analysis relies on the ability to find many endomorphisms on the base curve that have special properties. To the best of our knowledge, this class of endomorphisms has never been studied in the literature. We informally discuss the parameter sets where these endomorphisms should exist. We also present an algorithm which may provide information about additional torsion points under the party's private isogeny, which is of independent interest. Finally, we present a minor variation of the SIKE protocol that avoids exposing a known endomorphism ring.

We propose the first auctioneer-free sealed-bid auction protocol with a linear computation and communication complexity $O(c)$, $c$ being the bit length of the bid price. Our protocol, called Self-Enforcing Auction Lot (SEAL), operates in a decentralized setting, where bidders jointly compute the maximum bid while preserving the privacy of losing bids. In our protocol, we do not require any secret channels between participants. All operations are publicly verifiable; everyone including third-party observers is able to verify the integrity of the auction outcome. Upon learning the highest bid, the winner comes forward with a proof to prove that she is the real winner. Based on the proof, everyone is able to check if there is only one winner or there is a tie. While our main protocol works with the first-price sealed-bid, it can be easily extended to support the second-price sealed-bid (also known as the Vickrey auction), revealing only the winner and the second highest bid, while keeping the highest bid and all other bids secret. To the best of our knowledge, this work establishes to date the best computation and communication complexity for sealed-bid auction schemes without involving any auctioneer.

In this work, we formulate and investigate a pragmatic question related to practical side-channel attacks complemented with key enumeration. In a real attack scenario, after an attacker has extracted side-channel information, it is possible that despite the entropy of the key has been signicantly reduced, she cannot yet achieve a direct key recovery. If the correct key lies within a sufficiently small set of most probable keys, it can then be recovered with a plaintext and the corresponding ciphertext, by performing enumeration. Our proposal relates to the following question: how does an attacker know when to stop acquiring side-channel observations and when to start enumerating with a given computational effort? Since key enumeration is an expensive (i.e. time-consuming) task, this is an important question from an adversarial viewpoint. To answer this question, we present an efficient (heuristic) way to perform key-less rank estimation, based on simple entropy estimations using histograms.

Selling digital commodities securely over the Internet is a challenging task when Seller and Buyer do not trust each other. With the advent of cryptocurrencies, one prominent solution for digital exchange is to rely on a smart contract as a trusted arbiter that fairly resolves disputes when Seller and Buyer disagree. Such protocols have an optimistic mode, where the digital exchange between the parties can be completed with only minimal interaction with the smart contract. In this work we present OptiSwap, a new smart contract based fair exchange protocol that significantly improves the optimistic case of smart contract based fair exchange protocols. In particular, OptiSwap has almost no overhead in communication complexity, and improves on the computational overheads of the parties compared to prior solutions. An additional feature of OptiSwap is a protection mechanism against so-called grieving attacks, where an adversary attempts to violate the financial fairness of the protocol by forcing the honest party to pay fees. We analyze OptiSwap's security in the UC model and provide benchmark results over Ethereum.

Elliptic curves play a prominent role in cryptography. For instance, the hardness of the elliptic curve discrete logarithm problem is a foundational assumption in public key cryptography. Drinfeld modules are positive characteristic function field analogues of elliptic curves. It is natural to ponder the existence/security of Drinfeld module analogues of elliptic curve cryptosystems. But the Drinfeld module discrete logarithm problem is easy even on a classical computer. Beyond discrete logarithms, elliptic curve isogeny based cryptosystems have have emerged as candidates for post-quantum cryptography, including supersingular isogeny Diffie-Hellman (SIDH) and commutative supersingular isogeny Diffie-Hellman (CSIDH) protocols. We formulate Drinfeld module analogues of these elliptic curve isogeny based cryptosystems and devise classical polynomial time algorithms to break these Drinfeld analogues catastrophically.

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).