## IACR News

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

There is currently a problem with the jobs channel, and new jobs listings are not appearing here. Please see the jobs page.

#### 23 July 2019

###### Karl Wüst, Loris Diana, Kari Kostiainen, Ghassan Karame, Sinisa Matetic, Srdjan Capkun

ePrint Report
In contrast to traditional contracts, cryptocurrency-based smart contracts can provide improved business automation and more transparency. However, not all cryptocurrencies support expressive contracts. For example, Bitcoin only supports a restricted scripting language that is not expressive enough to realize many contracts. Ethereum supports a Turing-complete programming language, but the types of contracts that can be implemented are still severely constrained due to gas limits. Recent research has explored ways to add contract support to legacy currencies like Bitcoin or enable more complex contracts on systems like Ethereum, but such previous solutions have significant security and functional limitations.

In this paper we propose Bitcontracts, a novel solution to enable generic and expressive smart contracts on legacy cryptocurrencies. The starting point of our solution is a common off-chain execution model, where the contract's issuers appoints a set of service providers to execute the contract's code; the contract's execution results are accepted if a quorum of service providers reports the same result; and clients are free to choose which such contracts they trust and use. The main technical challenge of this paper is how to realize such a trust model securely and efficiently without modifying the underlying blockchain. Bitcontracts achieves this using two main techniques. First, the state of each contract is stored on the chain which avoids the need to run expensive consensus protocols between the service providers. Second, the validity of each execution result is bound to the latest state of the chain to prevent double-spending attacks. Bitcontracts can be used to retrofit contracts to currencies like Bitcoin or to extend the contract execution capabilities of systems like Ethereum. We also identify a set of generic properties that a blockchain system must support so that expressive smart contracts can be added safely and efficiently, and analyze existing blockchains based on these criteria.

In this paper we propose Bitcontracts, a novel solution to enable generic and expressive smart contracts on legacy cryptocurrencies. The starting point of our solution is a common off-chain execution model, where the contract's issuers appoints a set of service providers to execute the contract's code; the contract's execution results are accepted if a quorum of service providers reports the same result; and clients are free to choose which such contracts they trust and use. The main technical challenge of this paper is how to realize such a trust model securely and efficiently without modifying the underlying blockchain. Bitcontracts achieves this using two main techniques. First, the state of each contract is stored on the chain which avoids the need to run expensive consensus protocols between the service providers. Second, the validity of each execution result is bound to the latest state of the chain to prevent double-spending attacks. Bitcontracts can be used to retrofit contracts to currencies like Bitcoin or to extend the contract execution capabilities of systems like Ethereum. We also identify a set of generic properties that a blockchain system must support so that expressive smart contracts can be added safely and efficiently, and analyze existing blockchains based on these criteria.

###### Subhadeep Banik, Yuki Funabiki, Takanori Isobe

ePrint Report
At the FSE conference of ToSC 2018, Kranz et al. presented their results on shortest linear programs for the linear layers of
several well known block ciphers in literature. Shortest linear programs are essentially the minimum number of 2-input xor gates required to completely describe a linear system of equations. In the above paper the authors showed that the commonly used metrics like d-xor/s-xor count that are used to judge the ``lightweightedness'' do not represent the minimum number of xor gates required to describe a given MDS matrix. In fact they used heuristic based algorithms of Boyar/Peralta and Paar to find implementations of MDS matrices with even fewer xor gates than was previously known. They proved that the AES mixcolumn matrix can be implemented with as little as 97 xor gates. In this paper we show that the values reported in the above paper
are not optimal. By suitably including random bits in the instances of the above algorithms we can achieve implementations of almost all matrices with lesser number of gates than were reported in the above paper. As a result we report an implementation of the AES mixcolumn matrix that uses only 95 xor gates.

In the second part of the paper, we observe that most standard cell libraries contain both 2 and 3-input xor gates, with the silicon area of the 3-input xor gate being smaller than the sum of the areas of two 2-input xor gates. Hence when linear circuits are synthesized by logic compilers (with specific instructions to optimize for area), most of them would return a solution circuit containing both 2 and 3-input xor gates. Thus from a practical point of view, reducing circuit size in presence of these gates is no longer equivalent to solving the shortest linear program. In this paper we show that by adopting a graph based heuristic it is possible to convert a circuit constructed with 2-input xor gates to another functionally equivalent circuit that utilizes both 2 and 3-input xor gates and occupies less hardware area. As a result we obtain more lightweight implementations of all the matrices listed in the ToSC paper.

In the second part of the paper, we observe that most standard cell libraries contain both 2 and 3-input xor gates, with the silicon area of the 3-input xor gate being smaller than the sum of the areas of two 2-input xor gates. Hence when linear circuits are synthesized by logic compilers (with specific instructions to optimize for area), most of them would return a solution circuit containing both 2 and 3-input xor gates. Thus from a practical point of view, reducing circuit size in presence of these gates is no longer equivalent to solving the shortest linear program. In this paper we show that by adopting a graph based heuristic it is possible to convert a circuit constructed with 2-input xor gates to another functionally equivalent circuit that utilizes both 2 and 3-input xor gates and occupies less hardware area. As a result we obtain more lightweight implementations of all the matrices listed in the ToSC paper.

###### Dominic Dams, Jeff Lataille, John Wade

ePrint Report
We introduce the WIDESEAS protocol for
lattice-based Private Information Retrieval (PIR),
and we give performance numbers for its
recent implementation in the EncryptedQuery
open-source PIR software.
This protocol uses the fully homomorphic
Brakerski--Fan--Vercauteren (BFV) encryption scheme,
as opposed to the Paillier scheme, which
is used in all earlier versions of EncryptedQuery.
We show that the homomorphic capabilities
of BFV result in smaller query sizes
(due to a query-shrinking technique
based on batching and ciphertext multiplication),
higher response generation rates
(due to using relinearization to keep
ciphertexts small;
due to caching certain products of query elements
in the NTT domain;
due to using the distributive law to achieve a
quadratic reduction in the total
number of ciphertext multiplications;
due to using lazy reduction to speed up modular
multiplies;
and,
due to exploiting properties of inverse NTTs
over periodic data, and forward NTTs over sparse
data, for the purpose of accelerating plain multiplications),
and
comparable response sizes
(due to using modulus switching to discard redundant
ciphertext information prior to transmitting
the response).
For instance, running a single thread
(with Turbo Boost disabled) on a MacBook Pro
equipped with a 2.8 GHz Intel core i7,
and using a $20$-bit hash and a $2^{15}$-byte
data chunk size (which allows us to search
for a single targeted selector),
our implementation can
(i) generate a query of size $64\ \mathrm{MiB}$ in around $0.41\ {\rm seconds,}$
(ii) process a query against a $1\ \mathrm{TiB}$ database
(comprised of $2^{20}$-many $1\ \mathrm{MiB}$ records)
at a rate of $23.67\ \mathrm{MiB/s}$
(which is at least two orders of magnitude
faster than the Paillier-based version
of EncryptedQuery),
and
(iii) generate a response of size $4\ \mathrm{MiB}$
in around $0.51\ \mathrm{days}{\rm .}$
We expect a speed up on server class machines.
Our implementation uses the Microsoft SEAL
library along with a small amount of custom code.

###### Brandon Langenberg, Hai Pham, Rainer Steinwandt

ePrint Report
To quantify security levels in a post-quantum scenario, it is common to use the quantum resources needed to attack AES as a reference value. Specifically, in NIST’s ongoing post-quantum standardization effort, different security categories are defined that reflect the quantum resources needed to attack AES-128, AES-192, and AES-256.
This paper presents a quantum circuit to implement the S-box of AES. Leveraging also an improved implementation of the key expansion, we identify new quantum circuits for all three AES key lengths. For AES-128, the number of Toffoli gates can be reduced by more than 88% compared to Almazrooie et al.'s and Grassl et al.'s estimates, while simultaneously reducing the number of qubits. Our circuits can be used to simplify a Grover-based key search for AES.

###### Ashley Fraser, Elizabeth A. Quaglia, Ben Smyth

ePrint Report
We analyse three game-based definitions of receipt-freeness; uncovering soundness issues with two of the definitions and completeness issues with all three. Hence, two of the definitions are too weak, i.e., satisfiable by voting schemes that are not intuitively receipt-free. More precisely, those schemes need not even satisfy ballot secrecy. Consequently, the definitions are satisfiable by schemes that reveal how voters' vote. Moreover, we find that each definition is limited in scope. Beyond soundness and completeness issues, we show that each definition captures a different attacker model and we examine some of those differences.

###### Lorenzo Grassi, Gregor Leander, Christian Rechberger, Cihangir Tezcan, Friedrich Wiemer

ePrint Report
Invariant subspaces (Crypto'11) and subspace trails (FSE'17) are two related recent cryptanalytic approaches that led to new results on, e. g. PRINTCipher and AES. We extend the invariant subspace approach to allow for different subspaces in every round, something that so far only the subspace trail approach and a generalization for invariant subspace and invariant set attacks (Asiacrypt'18) were able to do. For an easier detection, we provide an algorithm which finds these weak-key subspace trails.

Using this framework, we perform an extensive analysis of weak-key distinguishers (in the single-key setting) for AES with several key schedule variants. Among others, we show that for the new key-schedule proposed at ToSC/FSE'18 - which is faster than the standard key schedule and ensures a higher number of active S-Boxes - it is possible to set up an invariant subspace distinguisher for any number of rounds. Finally, we describe a property for full AES-128 and AES-256 in the chosen-key setting with complexity 2^64 without requiring related keys. These chosen-key distinguishers are set up by exploiting the multiple-of-n property introduced at Eurocrypt'17, adapted to the case of AES instantiated with weak-keys.

Using this framework, we perform an extensive analysis of weak-key distinguishers (in the single-key setting) for AES with several key schedule variants. Among others, we show that for the new key-schedule proposed at ToSC/FSE'18 - which is faster than the standard key schedule and ensures a higher number of active S-Boxes - it is possible to set up an invariant subspace distinguisher for any number of rounds. Finally, we describe a property for full AES-128 and AES-256 in the chosen-key setting with complexity 2^64 without requiring related keys. These chosen-key distinguishers are set up by exploiting the multiple-of-n property introduced at Eurocrypt'17, adapted to the case of AES instantiated with weak-keys.

#### 22 July 2019

###### Munich, Germany, 14 November - 15 November 2019

Event Calendar
Event date: 14 November to 15 November 2019

Submission deadline: 25 August 2019

Submission deadline: 25 August 2019

###### Masoumeh Safkhani, Ygal Bendavid, Samad Rostampour, Nasour Bagheri

ePrint Report
Recently, in IEEE Transactions on Industrial Informatics, Fan et al. proposed a lightweight RFID protocol which has been suggested to be employed for protecting the Medical Privacy in an IoT system. However, the protocol has trivial flaws, as it is shown recently by Aghili et al., in Future Generation Computer Systems. Aghili \textit{et al.} also proposed an improved version of the protocol, based on the similar designing paradigm, called SecLAP. Although the protocol's designers claimed full security against all attacks in the context, we show that the proposed protocol has serious security flaws, by presenting traceability and passive secret disclosure attacks against this protocol. More precisely, we present passive partial secret disclosure attack with the complexity of eavesdropping one session of the protocol and success probability of `1'. The disclosed parameters can be used to trace the tag/reader in any later session which compromises the tag/reader privacy. In addition, we present a passive full secret disclosure attack against SecLAP which can disclose $2n$-bit secret key, $n$-bit $TID$ and $n$-bit $RID$ with the computational complexity of $27n^7$. In addition, we show that, as it is expected, Fan et al.'s protocol has the worse possible security in random oracle model, where the adversary's advantage after $q$ queries to distinguish the protocol from a random oracle is $1- 2^{-q} $. We also evaluate the security of SecLAP in the random oracle model and show that it is as insecure as its predecessor.

###### Morteza Adeli, Nasour Bagheri

ePrint Report
Internet of Things (IoT) has various applications such as healthcare, supply chain, agriculture, etc. Using the Internet of Vehicles(IoV) to control traffic of the cities is one of the IoT applications to construct smart cities. Recently Fan et al. proposed an authentication protocol to provide security of the IoV networks. They claimed that their scheme is secure and can resist against various known attacks. In this paper, we analyze more deeply the proposed scheme and show that their scheme is vulnerable against disclosure and desynchronization attacks. In disclosure attack, we disclose unique identification of the tag $ID$, secret key $S$, encryption matrix $M_2$ and half rows of encryption matrix $M_1$. Furthermore, we proposed an improved authentication scheme based on Maximum Distance Separable(MDS) matrices that is resistance against various attacks while maintaining low computational cost.

###### Ambili K N, Jimmy Jose

ePrint Report
IoT systems are vulnerable to various cyber attacks as they form a subset of the In-
ternet. Insider attacks find more significance since many devices are configured to access the
Internet without intrusion detection systems or firewalls in place. The current work focuses on
three insider attacks, namely, blackhole attack, sinkhole attack and wormhole attack. A distrib -
uted trust based intrusion detection system is proposed to detect these attacks. The trust scores
are compared with those existing in immutable distributed ledger and used to arrive at a deci-
sion to include or exclude a node.

###### Anne Canteaut, Lukas Kölsch, Friedrich Wiemer

ePrint Report
Recently Bar-On et al. proposed the DLCT for a tighter analysis of probabilities for differential-linear distinguishers. We extend the analysis of the DLCT, and gain new insights about this notion.

The DLCT entries correspond to the autocorrelation spectrum of the component functions and thus the DLCT is nothing else as the ACT. We note that the ACT spectrum is invariant under some equivalence relations. Interestingly the ACT spectrum is not invariant under inversion (and thus not under CCZ equivalence), implying that it might be beneficial to look at the decryption for a differential-linear cryptanalysis.

Furthermore, while for Boolean functions a lower bound for the maximal absolute autocorrelation, the absolute indicator, is not known, the case for vectorial Boolean functions is different. Here, we prove that for any vectorial Boolean function, its absolute indicator is lower bounded by $2^{n/2}$. Eventually, for APN functions we show a connection of the absolute indicator to the linearity of balanced Boolean functions, and exhibit APN permutations with absolute indicator bounded by $2^{(n+1)/2}$.

The DLCT entries correspond to the autocorrelation spectrum of the component functions and thus the DLCT is nothing else as the ACT. We note that the ACT spectrum is invariant under some equivalence relations. Interestingly the ACT spectrum is not invariant under inversion (and thus not under CCZ equivalence), implying that it might be beneficial to look at the decryption for a differential-linear cryptanalysis.

Furthermore, while for Boolean functions a lower bound for the maximal absolute autocorrelation, the absolute indicator, is not known, the case for vectorial Boolean functions is different. Here, we prove that for any vectorial Boolean function, its absolute indicator is lower bounded by $2^{n/2}$. Eventually, for APN functions we show a connection of the absolute indicator to the linearity of balanced Boolean functions, and exhibit APN permutations with absolute indicator bounded by $2^{(n+1)/2}$.

###### Quan Quan Tan, Thomas Peyrin

ePrint Report
In this article, we propose new heuristics for minimizing the amount of XOR gates required to compute a system of linear equations in GF(2). We first revisit the well known Boyar-Peralta strategy and argue that a proper randomization process during the selection phases can lead to great improvements. We then propose new selection criteria and explain their rationale. Our new methods outperform state-of-the-art algorithms such as Paar or Boyar-Peralta (or open synthesis tools such as Yosys) when tested on random matrices with various densities. They can be applied on matrices of reasonable sizes (up to about 32 x 32). Notably, we provide a new implementation record for the matrix underlying the MixColumns function of the AES block cipher, requiring only 94 XORs.

###### Yuechen Chen, Linru Zhang, Siu-Ming Yiu

ePrint Report
Functional encryption (FE) that bases on user attributes has many useful practical applications. For example, a company may only authorize department heads of other sections to query the average sale figures of the sales department from the encrypted sales amounts of all sales. However, FE schemes that can solve this problem are based on new, but not well-studied assumptions (such as indistinguishable obfuscation or multilinear maps). It is not clear if these FE schemes are secure. In this paper, we develop the first functional encryption scheme (ABFE) from simple and well-studied assumptions that can authorize a user base on the user's attributes to obtain a functional value of the encrypted data.

#### 19 July 2019

###### Simona Samardjiska, Paolo Santini, Edoardo Persichetti, Gustavo Banegas

ePrint Report
Rank metric is a very promising research direction for code-based cryptography. In fact, thanks to the high complexity of generic decoding attacks against codes in this metric, it is possible to easily select parameters that yield very small data sizes. In this paper we analyze cryptosystems based on Low-Rank Parity-Check (LRPC) codes, one of the classes of codes that are efficiently decodable in the rank metric. We show how to exploit the decoding failure rate, which is an inherent feature
of these codes, to devise a reaction attack aimed at recovering the private key. As a case study, we cryptanalyze the recent McNie submission to NIST’s Post-Quantum Standardization process. Additionally, we provide details of a simple implementation to validate our approach.

###### Matthias J. Kannwischer, Joost Rijneveld, Peter Schwabe, Ko Stoffelen

ePrint Report
This paper presents pqm4 – a testing and benchmarking framework for the ARM Cortex-M4. It makes use of a widely available discovery board with 196 KiB of memory and 1 MiB flash ROM. It currently includes 10 key encapsulation mechanisms and 5 signature schemes of the NIST PQC competition. For the remaining 11 schemes, the available implementations do require more than the available memory or they depend on external libraries which makes them arguably unsuitable for embedded devices.

###### Tomoki Moriya, Hiroshi Onuki, Tsuyoshi Takagi

ePrint Report
CSIDH is an isogeny-based key exchange protocol proposed by Castryck, Lange, Martindale, Panny, and Renes in 2018. CSIDH is based on the ideal class group action on $\mathbb{F}_p$-isomorphic classes of Montgomery curves. In order to calculate the class group action, we need to take points defined over $\mathbb{F}_{p^2}$. The original CSIDH algorithm requires a calculation over $\mathbb{F}_p$ by representing points as $x$-coordinate over Montgomery curves. Meyer and Reith proposed a faster CSIDH algorithm in 2018 which calculates isogenies on Edwards curves by using a birational map between a Montgomery curve and an Edwards curve. If we try to calculate the class group action on Edwards curves in a similar way on Montgomery curves, we have to consider points defined over $\mathbb{F}_{p^4}$. Therefore, it is not a trivial task to calculate the class group action on Edwards curves over $\mathbb{F}_p$.

In this paper, we prove a number of theorems on the properties of Edwards curves. By using these theorems, we devise a new CSIDH algorithm that uses only Edwards curves while calculating over $\mathbb{F}_p$. This algorithm is as fast as (or a little bit faster than) the algorithm proposed by Meyer and Reith.

In this paper, we prove a number of theorems on the properties of Edwards curves. By using these theorems, we devise a new CSIDH algorithm that uses only Edwards curves while calculating over $\mathbb{F}_p$. This algorithm is as fast as (or a little bit faster than) the algorithm proposed by Meyer and Reith.

###### Sreyosi Bhattacharyya, Palash Sarkar

ePrint Report
Poly1305 is a polynomial hash function designed by Bernstein in 2005. Presently, it is part of several major platforms including the Transport Layer Security protocol. Vectorised implementation of Poly1305 has been proposed by Goll and Gueron in 2015. We provide some simple algorithmic improvements to the Goll-Gueron vectorisation strategy. Implementation of the modified strategy on modern Intel processors shows marked improvements in speed for short messages.

###### Daniel Smith-Tone

ePrint Report
Recently, an article by Felke appeared in Cryptography and Communications discussing the security of biquadratic C* and a further generalization, k-ary C*. The article derives lower bounds for the complexity of an algebraic attack, directly inverting the public key, under an assumption that the first-fall degree is a good approximation of the solving degree, an assumption that the paper notes requires ``greater justification and clarification."

In this work, we provide a practical attack breaking all k-ary C* schemes. The attack is based on differential techniques and requires nothing but the ability to evaluate the public key and solve linear systems. In particular, the attack breaks the parameters provided in CryptoChallenge11 by constructing and solving linear systems of moderate size in a few minutes.

In this work, we provide a practical attack breaking all k-ary C* schemes. The attack is based on differential techniques and requires nothing but the ability to evaluate the public key and solve linear systems. In particular, the attack breaks the parameters provided in CryptoChallenge11 by constructing and solving linear systems of moderate size in a few minutes.

###### Yuhei Watanabe, Hideki Yamamoto, Hirotaka Yoshida

ePrint Report
The Tire Pressure Monitoring System (TPMS) is used to monitor the pressure of the tires and to inform the driver of it. This equipment is mandatory for vehicles in US and EU. To ensure the security of TPMS, it is important to reduce the cost of the cryptographic mechanisms implemented in resourced-constrained devices. To address this problem, previous work has proposed countermeasures employing lightweight block ciphers such as PRESENT, SPECK, or KATAN. However, it is not clear to us that any of these works have addressed the issues of software optimization that considers TPMS-packet protection as well as session key updates for architectures consisting of the vehicle TPMS ECU and four low-cost TPM sensors equipped with the tires. In this paper, we propose to application of the ISO/IEC 29192-5 lightweight hash function Lesamnta-LW to address this issue. Our approach is to apply the known method of converting Lesamnta-LW to multiple independent pseudo-random functions (PRFs) in TPMS. In our case, we generate five PRFs this way and then use one PRF for MAC-generation and four for key derivation. Although we follow the NIST SP 800-108 framework of converting PRFs to key derivation functions, we confirm the significant advantage of Lesamnta-LW-based PRFs over HMAC-SHA-256 by evaluating the performance on AVR 8-bit micro-controllers, on which we consider simulating TPMS sensors. We expect that our method to achieve multiple-purposes with a single cryptographic primitive will help to reduce the total implementation cost required for TPMS security.

###### Abhishek Jain, Zhengzhong Jin

ePrint Report
We give the first construction of statistical Zaps. Our construction satisfies computational soundness and relies on the quasi-polynomial hardness of learning with errors assumption.