International Association
for Cryptologic Research

Event date: 1 November to 5 November 2020
Submission deadline: 28 June 2020

Event date: 18 May to 22 May 2020

Since their introduction over two decades ago, physical side-channel attacks have presented a serious security threat. While many ciphers' implementations employ masking techniques to protect against such attacks, they often leak secret information due to unintended interactions in the hardware. We present Rosita, a code rewrite engine that uses a leakage emulator which we amended to correctly emulate the microarchitecture of a target system. We use Rosita to automatically protect a masked implementation of AES and show the absence of exploitable leakage at only a 11% penalty to the performance.

Blocks in proof-of-work (PoW) blockchains satisfy the PoW equation $H(B) \leq T$. If additionally a block satisfies $H(B) \leq T2^{-\mu}$, it is called a $\mu$-superblock. Superblocks play an important role in the construction of compact blockchain proofs which allows the compression of PoW blockchains into so-called Non-Interactive Proofs of Proof-of-Work (NIPoPoWs). These certificates are essential for the construction of superlight clients, which are blockchain wallets that can synchronize exponentially faster than traditional SPV clients.

In this work, we measure the distribution of superblocks in the Bitcoin blockchain. We find that the superblock distribution within the blockchain follows expectation, hence we empirically verify that the distribution of superblocks within the Bitcoin blockchain has not been adversarially biased. NIPoPoWs require that each block in a blockchain points to a sample of previous blocks in the blockchain. These pointers form a data structure called the interlink. We give efficient ways to store the interlink data structure. Repeated superblock references within an interlink can be omitted with no harm to security. Hence, it is more efficient to store a set of superblocks rather than a list. We show that, in honest executions, this simple observation reduces the number of superblock references by approximately a half in expectation. We then verify our theoretical result by measuring the improvement over existing blockchains in terms of the interlink sizes (which we improve by $79\%$) and the sizes of succinct NIPoPoWs (which we improve by $25\%$). As such, we show that deduplication allows superlight clients to synchronize $25\%$ faster.

CAS-Lock (cascaded locking) is a SAT-resilient locking technique, which can simultaneously thwart SAT and bypass attack, while maintaining non-trivial output corruptibility. Despite all of its theoretical guarantees, in this report we expose a serious flaw in its design that can be exploited to break CAS-Lock. Further, this attack neither requires access to a reverse-engineered netlist, nor it requires a working oracle with the correct key loaded onto the chip's memory. We demonstrate that we can activate any CAS-Locked IC without knowing the secret key.

Efficient user revocation has always been a challenging problem in identity-based encryption (IBE). Boldyreva et al. (CCS 2008) first proposed and formalized the notion of revocable IBE (RIBE) based on a tree-based revocation method. In their scheme, each user is required to store a number of long-term secret keys and all non-revoked users have to communicate with the key generation center periodically to update its decryption key. To reduce the workload on the user side, Qin et al. (ESORICS 2015) proposed a new system model, server-aided revocable IBE (SR-IBE). In SR-IBE model, each user is required to keep only one private key $\prid$ and unnecessary to communicate with the key generation center or the server during key updating. However, in their security model, the challenge identity $\starid$ must be revoked once the private key $\mathsf{Priv}_{\starid}$ was revealed to the adversary. This is too restrictive since decrypting a ciphertext requires both the private key $\prid$ and the long-term transformation key $\skid$. In this paper, we first revisit Qin et al.'s security model and propose a stronger one called SSR-sID-CPA security. Specifically, $\starid$ is revoked only when both $\sskid$ and $\sprid$ are revealed and the adversary is allowed to access short-term transformation keys oracle. We also prove that Qin et al.'s scheme is insecure under our new security model. Second, we construct a lattice-based SR-IBE scheme based on Katsumata's RIBE scheme (PKC 19), and show that our lattice-based SR-IBE scheme is SSR-sID-CPA secure. Finally, we propose a generic construction of SR-IBE scheme by combining a RIBE and a 2-level HIBE scheme. The security of the generic SR-IBE scheme inherits those of the underlying building blocks.

Characterizing the decoding failure rate of iteratively decoded Low- and Moderate-Density Parity Check (LDPC/MDPC) codes is paramount to build cryptosystems based on them, able to achieve indistinguishability under adaptive chosen ciphertext attacks. In this paper, we provide a statistical worst-case analysis of our proposed iterative decoder obtained through a simple modification of the classic in-place bit-flipping decoder. This worst case analysis allows both to derive the worst-case behavior of an LDPC/MDPC code picked among the family with the same length, rate and number of parity checks, and a code-specific bound on the decoding failure rate. The former result allows us to build a code-based cryptosystem enjoying the $\delta$-correctness property required by IND-CCA2 constructions, while the latter result allows us to discard code instances which may have a decoding failure rate significantly different from the average one (i.e., representing weak keys), should they be picked during the key generation procedure.

Winkle protects any validator-based byzantine fault tolerant consensus mechanisms, such as those used in modern Proof-of-Stake blockchains, against long-range attacks where old validators’ signature keys get compromised. Winkle is a decentralized secondary layer of client-based validation, where a client includes a single additional field into a transaction that they sign: a hash of the previously sequenced block. The block that gets a threshold of signatures (confirmations) weighted by clients’ coins is called a “confirmed” checkpoint. We show that under plausible and flexible security assumptions about clients the confirmed checkpoints can not be equivocated. We discuss how client key rotation increases security, how to accommodate for coins’ minting and how delegation allows for faster checkpoints. We evaluate checkpoint latency experimentally using Bitcoin and Ethereum transaction graphs, with and without delegation of stake.

Event date: 18 May to 20 May 2020

Proxy re-encryption(PRE) is a primitive that is used to facilitate secure access delegation in the cloud. Proxy re-encryption allows a proxy server to transform ciphertexts encrypted under one user's public key to that under another user's public key without learning anything about the underlying message or the secret key. Over the years proxy re-encryption schemes have been proposed in different settings. In this paper we restrict our analysis to certificate based proxy re-encryption. The first CCA secure certificate based PRE without bilinear pairings was proposed by Lu and Li in Future Generation Computer Systems, 2016. In this paper we present a concrete attack on their scheme and prove that it is not CCA secure.

In this paper, we propose an automatic tool to search for optimal differential and linear trails in ARX ciphers. It's shown that a modulo addition can be divided into sequential small modulo additions with carry bit, which turns an ARX cipher into an S-box-like cipher. From this insight, we introduce the concepts of carry-bit-dependent difference distribution table (CDDT) and carry-bit-dependent linear approximation table (CLAT). Based on them, we give efficient methods to trace all possible output differences and linear masks of a big modulo addition, with returning their differential probabilities and linear correlations simultaneously. Then an adapted Matsui's algorithm is introduced, which can find the optimal differential and linear trails in ARX ciphers. Besides, the superiority of our tool's potency is also confirmed by experimental results for round-reduced versions of HIGHT and SPECK. More specifically, we find the optimal differential trails for up to 10 rounds of HIGHT, reported for the first time. We also find the optimal differential trails for 10, 12, 16, 8 and 8 rounds of SPECK32/48/64/96/128, and report the provably optimal differential trails for SPECK48 and SPECK64 for the first time. The optimal linear trails for up to 9 rounds of HIGHT are reported for the first time, and the optimal linear trails for 22, 13, 15, 9 and 9 rounds of SPECK32/48/64/96/128 are also found respectively. These results evaluate the security of HIGHT and SPECK against differential and linear cryptanalysis. Also, our tool is useful to estimate the security in the design of ARX ciphers.

Ciphertext-policy attribute-based encryption (CP-ABE) is a cryptographic technique known for ensuring fine-grained access control on encrypted data. However, one of the main drawbacks of CP-ABE is that the time required to decrypt the ciphertext is considerably expensive, since it grows with the complexity of access policy. Outsourcing partial decryption operations to the cloud eliminates the overheads for users, but it also inevitably increases the computational burden of the cloud. When millions of users are enjoying cloud computing services, it may cause huge congestion and latency.

In this paper, we propose a heuristic primitive called reverse outsourcing. Specifically, users outsource part of the decryption work to the cloud, which splits it up and dispatches each to different idle users. Idle users are those whos has some smart devices connected to the internet and not in use. It's like, the cloud employs many idle users to accomplish its own computing tasks. Then, we proposed a reverse outsourced CP-ABE scheme which provable secure under the BDBH assumptions.

We introduce a framework generalizing lattice reduction algorithms to module lattices in order to practically and efficiently solve the $\gamma$-Hermite Module-SVP problem over arbitrary cyclotomic fields. The core idea is to exploit the structure of the subfields for designing a doubly-recursive strategy of reduction: both recursive in the rank of the module and in the field we are working in. Besides, we demonstrate how to leverage the inherent symplectic geometry existing in the tower of fields to provide a significant speed-up of the reduction for rank two modules. The recursive strategy over the rank can also be applied to the reduction of Euclidean lattices, and we can perform a reduction in asymptotically almost the same time as matrix multiplication. As a byproduct of the design of these fast reductions, we also generalize to all cyclotomic fields and provide speedups for many previous number theoretical algorithms.

Quantitatively, we show that a module of rank 2 over a cyclotomic field of degree $n$ can be heuristically reduced within approximation factor $2^{\tilde{O}(n)}$ in time $\tilde{O}(n^2B)$, where $B$ is the bitlength of the entries. For $B$ large enough, this complexity shrinks to $\tilde{O}(n^{\log_2 3}B)$. This last result is particularly striking as it goes below the estimate of $n^2B$ swaps given by the classical analysis of the LLL algorithm using the so-called potential.

Finally, all this framework is fully parallelizable, and we provide a full implementation. We apply it to break multilinear cryptographic candidates on concrete proposed parameters. We were able to reduce matrices of dimension 4096 with 6675-bit integers in 4 days, which is more than a million times faster than previous state-of-the-art implementations. Eventually, we demonstrate a quasicubic time for the Gentry-Szydlo algorithm which finds a generator given the relative norm and a basis of an ideal. This algorithm is important in cryptanalysis and requires efficient ideal multiplications and lattice reductions; as such we can practically use it in dimension 1024.

This paper proposes a solution for implementing Confidential Assets on MimbleWimble, which allows users to issue and transfer multiple assets on a blockchain without showing transaction addresses, amounts, and asset types. We first introduce the basic principles of MimbleWimble and then describe the implementation in detail.

McEliece-like code-based key exchange mechanisms using QC-MDPC codes can reach IND-CPA security under hardness assumptions from coding theory, namely quasi-cyclic syndrome decoding and quasi-cyclic codeword finding. To reach higher security requirements, like IND-CCA security, it is necessary in addition to prove that the decoding failure rate (DFR) is negligible, for some decoding algorithm and a proper choice of parameters. Getting a formal proof of a low DFR is a difficult task. Instead, we propose to ensure this low DFR under some additional security assumption on the decoder. This assumption relates to the asymptotic behavior of the decoder and is supported by several other works. We define a new decoder, Backflip, which features a low DFR. We evaluate the Backflip decoder by simulation and extrapolate its DFR under the decoder security assumption. We also measure the accuracy of our simulation data, in the form of confidence intervals, using standard techniques from communication systems.

Maintaining privacy on the Internet with the presence of powerful adversaries such as nation-state attackers is a challenging topic, and the Tor project is currently the most important tool to protect against this threat. The circuit construction protocol (CCP) negotiates cryptographic keys for Tor circuits, which overlay TCP/IP by routing Tor cells over n onion routers. The current circuit construction protocol provides strong security guarantees such as forward secrecy by exchanging O(n^2) messages.

For several years it has been an open question if the same strong security guarantees could be achieved with less message overhead, which is desirable because of the inherent latency in overlay networks. Several publications described CCPs which require only O(n) message exchanges, but significantly reduce the security of the resulting Tor circuit. It was even conjectured that it is impossible to achieve both message complexity O(n) and forward secrecy immediately after circuit construction (so-called immediate forward secrecy).

Inspired by the latest advancements in zero round-trip time key exchange (0-RTT), we present a new CCP protocol Tor 0-RTT (T0RTT). Using modern cryptographic primitives such as puncturable encryption allow to achieve immediate forward secrecy using only O(n) messages. We implemented these new primitives to give a first indication of possible problems and how to overcome them in order to build practical CCPs with O(n) messages and immediate forward secrecy in the future.

We present a generalization of Maurer's unified zero-knowledge (UZK) protocol, namely a unified generic zero-knowledge (UGZK) construction. We prove the security of our UGZK protocol and discuss special cases. Compared to UZK, the new protocol allows to prove knowledge of a vector of secrets instead of only one secret. We also provide the reader with a hash variant of UGZK and the corresponding security analysis. Last but not least, we extend Cogliani \emph{et al.}'s lightweight authentication protocol by describing a new distributed unified authentication scheme suitable for wireless sensor networks and, more generally, the Internet of Things.

The functioning of blockchain networks can be analyzed and abstracted into simple properties that allow for their usage as blackboxes in cryptographic protocols. One such abstraction is that of the growth of the blockchain over time. In this work, we build on the analysis of Garay et al. to develop an interface of functions that allow us to predict which block a submitted transaction will be added by. For cross-chain applications, we develop similar prediction functions for submitting related transactions to multiple independent networks in parallel. We then define a general ``receipt functionality'' for blockchains that provides a proof, in the form of a short string, that a particular transaction was added to the blockchain. We use these tools to obtain an efficient solution to the Train-and-Hotel Problem, which asks for a cross-chain booking protocol that allows a user to atomically book a train ticket on one blockchain and a hotel room on another. We formally prove that our protocol satisfies atomicity and liveness. We further highlight the versatility of blockchain receipts by discussing their applicability to general cross-chain communication and multi-party computation. We then detail a construction of ``Proof-of-Work receipts'' for Proof-of-Work blockchains using efficient and compact zero-knowledge proofs for arithmetic circuits.

We initiate the systematic study of probabilistic proofs in relativized worlds. The goal is to understand, for a given oracle, if there exist "non-trivial" probabilistic proofs for checking deterministic or nondeterministic computations that make queries to the oracle.

This question is intimately related to a recent line of work that builds cryptographic primitives (e.g., hash functions) via constructions that are "friendly" to known probabilistic proofs. This improves the efficiency of probabilistic proofs for computations calling these primitives.

We prove that "non-trivial" probabilistic proofs relative to several natural oracles do not exist. Our results provide strong complexity-theoretic evidence that certain functionalities cannot be treated as black boxes, and thus investing effort to instantiate these functionalities via constructions tailored to known probabilistic proofs may be inherent.

In this paper we prove that embedding parity bits and other function outputs in share string enables us to construct a secret sharing scheme (over binary alphabet) robust against a resource bounded adversary. Constructing schemes robust against adversaries in higher complexity classes requires an increase in the share size and increased storage. By connecting secret sharing with the randomized decision tree of a Boolean function we construct a scheme which is robust against an infinitely powerful adversary while keeping the constructions in a very low complexity class, viz. $AC^0$. As an application, we construct a robust secret sharing scheme in $AC^0$ that can accommodate new participants (dynamically) over time. Our construction requires a new redistribution of secret shares and can accommodate a bounded number of new participants.