## IACR News

Updates on the COVID-19 situation are on the Announcement channel.

Here you can see all recent updates to the IACR webpage. These updates are also available:

#### 03 June 2020

###### Ignacio Cascudo, Bernardo David
ePrint Report
In this paper we present ALBATROSS, a family of multiparty randomness generation protocols with guaranteed output delivery and public verification that allows to trade off corruption tolerance for a much improved amortized computational complexity. Our basic stand alone protocol is based on publicly verifiable secret sharing (PVSS) and is secure under in the random oracle model under the decisional Diffie-Hellman (DDH) hardness assumption. We also address the important issue of constructing Universally Composable randomness beacons, showing two UC versions of Albatross: one based on simple UC NIZKs and another one based on novel efficient designated verifier'' homomorphic commitments. Interestingly this latter version can be instantiated from a global random oracle under the weaker Computational Diffie-Hellman (CDH) assumption. An execution of ALBATROSS with $n$ parties, out of which up to $t=(1/2-\epsilon)\cdot n$ are corrupt for a constant $\epsilon>0$, generates $\Theta(n^2)$ uniformly random values, requiring in the worst case an amortized cost per party of $\Theta(\log n)$ exponentiations per random value. We significantly improve on the SCRAPE protocol (Cascudo and David, ACNS 17), which required $\Theta(n^2)$ exponentiations per party to generate one uniformly random value. This is mainly achieved via two techniques: first, the use of packed Shamir secret sharing for the PVSS; second, the use of linear $t$-resilient functions (computed via a Fast Fourier Transform-based algorithm) to improve the randomness extraction.
ePrint Report
A blockchain is designed to be a self-sufficient decentralised ledger: a peer verifying the validity of past transactions only needs to download the blockchain (the ledger) and nothing else. However, it might be of interest to make two different blockchains interoperable, i.e., to allow one to transmit information from one blockchain to another blockchain. In this paper, we give a formalisation of this problem, and we prove that blockchain interoperability is impossible according to the classical definition of a blockchain. Under a weaker definition of blockchain, we demonstrate that two blockchains are interoperable is equivalent to creating a 2-in-1' blockchain containing both ledgers, thus limiting the theoretical interest of making interoperable blockchains in the first place. We also observe that all practical existing interoperable blockchain frameworks work indeed by exchanging already created tokens between two blockchains and not by offering the possibility to transfer tokens from one blockchain to another one, which implies a modification of the balance of total created tokens on both blockchains. It confirms that having interoperability is only possible by creating a 2-in-1' blockchain containing both ledgers.
###### Henri Aare, Peter Vitols
ePrint Report
The distributed ledger technology has been widely hailed as the break- through technology. It has realised a great number of application scenarios, and improved workflow of many domains. Nonetheless, there remain a few major concerns in adopting and deploying the distributed ledger technology at scale. In this white paper, we tackle two of them, namely the throughput scalability and confidentiality protection for transactions. We learn from the existing body of research, and build a scale-out blockchain plat- form that champions privacy called RVChain. RVChain takes advantage of trusted execution environment to offer confidentiality protection for transactions, and scale the throughput of the network in proportion with the number of network participants by supporting parallel shadow chains.
###### Jeff Burdges, Alfonso Cevallos, Peter Czaban, Rob Habermeier, Syed Hosseini, Fabio Lama, Handan Kilinc Alper, Ximin Luo , Fatemeh Shirazi, Alistair Stewart, Gavin Wood
ePrint Report
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.
###### Kyungbae Jang, Seungjoo Choi, Hyeokdong Kwon, Hwajeong Seo
ePrint Report
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.
###### Anne Broadbent, Raza Ali Kazmi
ePrint Report
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.
###### Jeffrey Burdges, Luca De Feo
ePrint Report
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.
ePrint Report
###### Erik-Oliver Blass, Florian Kerschbaum
ePrint Report
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.
###### Pedro Branco, Nico Döttling, Paulo Mateus
ePrint Report
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.
###### David Knichel, Pascal Sasdrich, Amir Moradi
ePrint Report
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.
###### Péter Kutas, Chloe Martindale, Lorenz Panny, Christophe Petit, Katherine E. Stange
ePrint Report
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].
ePrint Report
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}.
###### Jean-Sébastien Coron, Luca Notarnicola, Gabor Wiese
ePrint Report
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.
###### Zhiguo Wan, Xiaotong Liu
ePrint Report
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.
###### Vivek Arte, Mihir Bellare
ePrint Report
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.
###### Daniele Di Tullio, Manoj Gyawali
ePrint Report
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.
ePrint Report