International Association
for Cryptologic Research

In this paper we describe the design components of the heterogenous multi-chain protocol Polkadot and explain how these components help Polkadot address some of the existing shortcomings of blockchain technologies. At present, a vast number of blockchain projects have been introduced and employed with various features that are not necessarily designed to work with each other. This makes it difficult for users to utilise a large number of applications on different blockchain projects. Moreover, with the increase in number of projects the security that each one is providing individually becomes weaker. Polkadot aims to provide a scalable and interoperable framework for multiple chains with pooled security that is achieved by the collection of components described in this paper.

Grover search algorithm reduces the security level of symmetric key cryptography with $n$-bit secret key to $O(2^{n/2})$. In order to evaluate the Grover search algorithm, the target block cipher should be implemented in quantum circuits. Recently, many research works evaluated required quantum resources of AES block ciphers by optimizing the expensive substitute layer. However, only few works devoted to ARX-based lightweight block ciphers, which are active research area. In this paper, we present optimized implementations of SPECK 32/64 and SPECK 64/128 block ciphers for quantum computers. To the best of our knowledge, this is the first implementation of SPECK in quantum circuits. Primitive operations, including addition, rotation, and exclusive-or, for SPECK block cipher are finely optimized to achieve the optimal quantum circuit, in terms of qubits, Toffoli gate, CNOT gate, and X gate. The proposed method can be applied to other ARX-based lightweight block ciphers, such as LEA, HIGHT and CHAM block ciphers.

An indistinguishability obfuscator is a probabilistic polynomial-time algorithm that takes a circuit as input and outputs a new circuit that has the same functionality as the input circuit, such that for any two circuits of the same size that compute the same function, the outputs of the indistinguishability obfuscator are computationally indistinguishable. Here, we study schemes for indistinguishability obfuscation for quantum circuits ($qi\mathcal{O}$), which consists in a procedure that takes as input a quantum circuit and outputs a quantum state, together with a quantum circuit, which together can be used to evaluate the original quantum circuit on any quantum input; the security guarantee being that for two quantum circuits of the same size that have the same input-output behaviour, the outputs of the obfuscator are computationally indistinguishable. Our main result provides a construction for $qi\mathcal{O}$, where the size of the output of the obfuscator is exponential in the number of non-Clifford (T gates), which means that the construction is efficient as long as the number of T gates is logarithmic in the circuit size.

We introduce a new primitive named Delay Encryption, and give an efficient instantation based on isogenies of supersingular curves and pairings. Delay Encryption is related to Time-lock Puzzles and Verifiable Delay Functions, and can be roughly described as "identity based encryption with slow derived private key issuance". It has several applications in distributed protocols, such as sealed bid Vickrey auctions and electronic voting.

We give an instantiation of Delay Encryption by modifying Boneh and Frankiln's IBE scheme, where we replace the master secret key by a long chain of isogenies, as in the isogeny VDF of De Feo, Masson, Petit and Sanso. Similarly to the isogeny-based VDF, our Delay Encryption requires a trusted setup before parameters can be safely used; our trusted setup is identical to that of the VDF, thus the same parameters can be generated once and shared for many executions of both protocols, with possibly different delay parameters.

We also discuss several topics around delay protocols based on isogenies that were left untreated by De Feo et al., namely: distributed trusted setup, watermarking, and implementation issues.

Flush based cache attacks like Flush+Reload and Flush+Flush are one of the highly effective cache attacks. In fact, the Flush+Flush attack is stealthy too. Most of the flush based attacks provide high accuracy in controlled environments where attacker and victim are the only two processes that are running on a system by sharing OS pages. However, we observe that these attacks lose their effectiveness (prone to low accuracy) on a noisy multi-core system where co-running applications run along with the attacker and the victim. Two root causes for the varying accuracy of flush based attacks are: (i) the dynamic nature of core frequencies that fluctuate depending on the system load, and (ii) the relative placement of victim and attacker threads in the processor (same logical core, same physical core, different physical cores). The variation in the processor frequencies and placement of threads affect one of the critical attack steps (the cache latency calibration step as the latency threshold set to distinguish a cache hit from a miss becomes inaccurate). We propose a set of refinements (DABANGG refinements) to make existing flush attacks resilient to frequency changes and thread placement in the processor, and therefore system noise. We propose refinements to pre-attack and attack steps and make it conscious about the latency change. We evaluate DABANGG-enabled Flush+Reload and Flush+Flush attacks (DABANGG+Flush+Reload and DABANGG+Flush+Flush, respectively) against the standard Flush+Reload and Flush+Flush attacks across four scenarios for eight different combinations of system noise capturing different levels of compute, memory, and I/O noise intensities: (i) a side-channel attack based on user input (single-character and multi-character key-logging), (ii) a side-channel on AES, (iii) a covert-channel, and a (iv) transient execution attack in the form the Spectre attack. For all the scenarios, DABANGG+Flush+Reload and DABANGG+Flush+Flush outperform the standard Flush+Reload and Flush+Flush attacks in terms of F1-score and accuracy.

Efficient multi-party protocols are commonly composed of different sub-protocols, combining techniques such as homomorphic encryption, secret or Boolean sharing, and garbled circuits. To ensure security of the composed protocol against malicious adversaries, one needs to prove in zero-knowledge that conversions between individual techniques are correct. However, efficient ZK proofs for conversion between fully homomorphic encryption and garbled circuits are still an open problem. In this paper, we design new efficient proofs and apply them to a new class of multi-party protocols which themselves are composed out of two-party protocols. We integrate both types of compositions, compositions of fully homomorphic encryption with garbled circuits and compositions of multi-party protocols from two-party protocols. As a result, we can construct communication-efficient protocols for special problems with malicious security. To show the usefulness of this approach, we give an example scheme for private set analytics, i.e., private set disjointness. This scheme enjoys lower communication complexity than a solution based on generic multi-party protocols and lower computation cost than fully homomorphic encryption. So, our design is more suitable for deployments in wide-area networks, such as the Internet, with many participants or problems with circuits of moderate or high multiplicative depth.

Oblivious Linear Evaluation (OLE) is a simple yet powerful cryptographic primitive which allows a sender, holding an affine function $f(x)=a+bx$ over a finite field, to let a receiver learn $f(w)$ for a $w$ of the receiver's choice. In terms of security, the sender remains oblivious of the receiver's input $w$, whereas the receiver learns nothing beyond $f(w)$ about $f$. In recent years, OLE has emerged as an essential building block to construct efficient, reusable and maliciously-secure two-party computation.

In this work, we present efficient two-round protocols for OLE based on the Learning with Errors (LWE) assumption. Our first protocol for OLE is secure against malicious unbounded receivers and semi-honest senders. The receiver's first message is reusable, meaning that it can be reused over several executions of the protocol, and it may carry information about a batch of inputs, and not just a single input. We then show how we can extend the above protocol to provide malicious security for both parties, albeit at the cost of reusability.

Implementing cryptographic functions securely in the presence of physical adversaries is still a challenge although a lion's share of research in the physical security domain has been put in development of countermeasures. Among several protection schemes, masking has absorbed the most attention of research in both academic and industrial communities, due to its theoretical foundation allowing to provide proofs or model the achieved security level. In return, masking schemes are difficult to implement as the implementation process often is manual, complex, and error-prone. This motivated the need for formal verification tools that allow the designers and engineers to analyze and verify the designs before manufacturing.

In this work, we present a new framework to analyze and verify masked implementations against various security notions using different security models as reference. In particular, our framework - which directly processes the resulting gate-level netlist of a hardware synthesis - particularly relies on Reduced Ordered Binary Decision Diagrams (ROBDDs) and the concept of statistical independence of probability distributions. Compared to existing tools, our framework captivates due to its simplicity, accuracy, and functionality while still having a reasonable efficiency for many applications and common use-cases.

SIDH is a post-quantum key exchange algorithm based on the presumed difficulty of computing isogenies between supersingular elliptic curves. However, the exact hardness assumption SIDH relies on is not the pure isogeny problem; attackers are also provided with the action of the secret isogeny restricted to a subgroup of the curve. Petit [21] leverages this information to break variants of SIDH in polynomial time, thus demonstrating that exploiting torsion-point information can lead to an attack in some cases. The contribution of this paper is twofold: First, we revisit and improve the techniques of [21] to span a broader range of parameters. Second, we construct SIDH variants designed to be weak against the resulting attacks; this includes weak choices of starting curve under moderately imbalanced parameters as well as weak choices of base field under balanced parameters. We stress that our results do not reveal any weakness in the NIST submission SIKE [19]. However, they do get closer than previous attacks in several ways and may have an impact on the security of SIDH-based group key exchange [2] and certain instantiations of B-SIDH [7].

Search for the right pairs of inputs in difference-based distinguishers is an important task for the experimental verification of the distinguishers in symmetric-key ciphers. In this paper, we develop an MILP-based approach to verify the possibility of difference-based distinguishers and extract the right pairs. We apply the proposed method to some presented difference-based trails (Related-Key Differentials (RKD), Rotational-XOR (RX)) of block ciphers \texttt{SIMECK}, and \texttt{SPECK}. As a result, we show that some of the reported RX-trails of \texttt{SIMECK} and \texttt{SPECK} are incompatible, i.e. there are no right pairs that follow the expected propagation of the differences for the trail. Also, for compatible trails, the proposed approach can efficiently speed up the search process of finding the exact value of a weak-key from the target weak-key space. For example, in one of the reported 14-round RX trails of \texttt{SPECK}, the probability of a key pair to be a weak-key is $2^{-94.91}$ when the whole key space is $2^{96}$; our method can find a key pair for it in a comparatively short time. It is worth noting that it was impossible to find this key pair using a traditional search. As another result, we apply the proposed method %and consider a search strategy for the framework of to \texttt{SPECK} block cipher, to construct longer related-key differential trails of \texttt{SPECK} which we could reach 15, 16, 17, and 19 rounds for \texttt{SPECK32/64}, \texttt{SPECK48/96}, \texttt{SPECK64/128}, and \texttt{SPECK128/256}, respectively. It should be compared with the best previous results which are 12, 15, 15, and 20 rounds, respectively, that both attacks work for a certain weak key class. It should be also considered as an improvement over the reported result of rotational XOR cryptanalysis on \texttt{SPECK}.

We consider the problem of recovering the entries of diagonal matrices $\{U_a\}_a$ for $a = 1,\ldots,t$ from multiple ``incomplete'' samples $\{W_a\}_a$ of the form $W_a=PU_aQ$, where $P$ and $Q$ are unknown matrices of low rank. We devise practical algorithms for this problem depending on the ranks of $P$ and $Q$. This problem finds its motivation in cryptanalysis: we show how to significantly improve previous algorithms for solving the approximate common divisor problem and breaking CLT13 cryptographic multilinear maps.

The COVID-19 pandemic is a severe threat to both lives and economics throughout the world. Advanced information technology can play an important role to win this war against this invisible enemy. The most effective way to fight COVID-19 is quarantining infected people and identifying their contacts. Recently, quite a few Bluetooth-based contact tracing proposals have been proposed to identify who has come into contact with infected people. The success of a contact tracing system depends on multiple factors, including security and privacy features, simplicity and user-friendliness etc. More importantly, it should help the health authority to effectively enforce contact tracing, so as to control spreading of the vital virus as soon as possible. However, current proposals are either susceptible to security and privacy attacks, or expensive in computation and/or communication costs.

In this paper, we propose ContactChaser, a simple but effective contact tracing scheme based on group signature, to achieve strong security and privacy protection for users. ContactChaser only requires a health authority to issue group private keys to users for only once, without frequently updating keys with the authority. It helps the authority to find out the close contacts of infected people, but just leaks the minimum information necessary for contact tracing to the health authority. Specially, the contact relationship is protect against the authority, which only knows the close contacts of infected people. ContactChaser is able to prevent most attacks, especially relay and replay attacks, so that it can effectively avoid false alerts and reduce unreported contacts. We give a detailed analysis of ContactChaser’s security and privacy properties as well as its performance. It is expected ContactChaser can contribute to the design and development of contact tracing schemes.

This paper formulates, and studies, the problem of property transference in dual-mode NIZKs. We say that a property P (such as soundness, ZK or WI) transfers, if, one of the modes having P allows us to prove that the other mode has the computational analogue of P, as a consequence of nothing but the indistinguishability of the CRSs in the two modes. Our most interesting finding is negative; we show by counter-example that the form of soundness that seems most important for applications fails to transfer. On the positive side, we develop a general framework that allows us to show that zero knowledge, witness indistinguishability, extractability and weaker forms of soundness do transfer. Our treatment covers conventional, designated-verifier and designated-prover NIZKs (single and dual-mode) in a unified way.

In this paper, we present a key exchange protocol in which Alice and Bob have secret keys given by quadric surfaces embedded in a large ambient space by means of the Veronese embedding and public keys given by hyperplanes containing the embedded quadrics. Both of them reconstruct the isomorphism class of the intersection which is a curve of genus 1, which is uniquely determined by the j-invariant. An eavesdropper, to find this j-invariant, has to solve problems which are conjecturally quantum resistant.

This paper will outline, for the first time, exactly how the ITM Attack (a linkability attack against shielded transactions) works against Zcash Protocol and how Hush is the first cryptocoin with a defensive mitigation against it, called ”Sietch ”. Sietch is already running live in production and undergoing rounds of improvement from expert feedback. This is not an academic paper about pipedreams. It describes production code and networks. We begin with a literature review of all known metadata attack methods that can be used against Zcash Protocol blockchains. This includes their estimated attack costs and threat model. This paper then describes the ”ITM Attack” which is a specific instance of a new class of metadata attacks against blockchains which the author describes as Metaverse Metadata Attacks . The paper then explains Sietch in detail, which was a response to these new attacks. We hope this new knowledge and theory helps cryptocoins increase their defenses against very well-funded adversaries including nation states and chain analysis companies. A few other new privacy issues and metadata attacks against Zcash Protocol coins will also be enumerated for the first time publicly. The ideas in this paper apply to all cryptocoins which utilize transaction graphs, which is to say just about all known coins. Specifically, the Metaverse Metadata class of attacks is applicable to all Bitcoin source code forks (including Dash, Verge, Zerocoin and their forks), CryptoNote Protocol coins (Monero and friends) and MimbleWimble Protocol (Grin, Beam, etc) coins but these will not be addressed here other than a high-level description of how to apply these methods to those chains.

In privacy zdust we trust. If dust can attack us, dust can protect us. – Sietch Mottos

Blockchains systems evolve in complex environments that mix classical patterns of faults (e.g crash faults, transient faults, Byzantine faults, churn) with selfish, rational or irrational behaviors typical to economical systems. In this paper we propose a game theoretical framework in order to formally characterize the robustness of blockchains systems in terms of resilience to rational deviations and immunity to Byzantine behaviors. Our framework includes necessary and sufficient conditions for checking the immunity and resilience of games and a new technique for composing games that preserves the robustness of individual games. We prove the practical interest of our formal framework by characterizing the robustness of three different protocols popular in blockchain systems: a HTLC-based payment scheme (a.k.a. Lightning Network), a side-chain protocol and a cross-chain swap protocol.

In this short note, we address a common misconception at the interface of probability theory and public-key cryptography.

We show it is possible to build an RSA-type cryptosystem by utilizing probable primes to base 2 numbers. Our modulus N is the product nm of such numbers (so here both prime and some composite, e.g. Carmichael or Fermat, numbers are acceptable) instead of prime numbers. Moreover, we require for n and m to be distinct only, not necessarily coprime, and so we don't have to worry about whether any of the numbers n,m is composite or not. The encryption and decryption processes are similar as those in the RSA. Hence, in this cryptosystem we may apply the above kind of numbers of arbitrary length being still sure that the system works well. The price for that is the size of words permitted by the new system: any message M, as a number, must be smaller than log (in base 2) of nm.

The IACR and PKC Steering Committee are pleased to announce the 2020 Test-of-Time award for papers published PKC.

PKC is the International Conference on Practice and Theory in Public Key Cryptography, which was founded in 1998 and became an official IACR event in 2003. The Test-of-Time award recognizes outstanding papers, published in PKC about 15 years ago, making a significant contribution to the theory and practice of public key cryptography, preferably with influence either on foundations or on the practice of the field.

The 2020 award will be given on Wednesday June 3rd at PKC in a virtual Award Ceremony, for papers published in the conference's initial years of early 2000s and late 1990s. In the first few years a number of papers from a few different initial years of PKC can be recognized. Thereafter, the award will typically recognize one year at a time with one or two papers.

The recipients of the 2020 award are:

• On the Security of ElGamal Based Encryption , by Yiannis Tsiounis, and Moti Yung, PKC 1998.
• A Generalisation, a Simplification and Some Applications of Paillier's Probabilistic Public-Key System, by Ivan Damgård, and Mads Jurik, PKC 2001.
• Threshold Signatures , Multisignatures and Blind Signatures based on the Gap-Diffie-Hellman-Group Signature Scheme, by Alexandra Boldyreva, PKC 2003.

Congratulations to these authors for their impactful work! More information about the award can be found at https://iacr.org/meetings/pkc/test_of_time_award/

Event date: 17 September to 19 September 2020
Submission deadline: 10 June 2020