## 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:

#### 07 January 2020

###### Kenneth Koon-Ho Wong, Harry Bartlett, Leonie Simpson, Ed Dawson

ePrint Report
This document contains supplementary material to the paper with the same title available from the proceedings of the International Conference on Information Security and Cryptology (ICISC) 2019. In this supplementary material, we demonstrate that the random fault attack strategy described in the full paper can be applied to ciphers in the MORUS family, resulting in partial state recovery for these ciphers.

###### Daniel Cervantes-Vázquez, Eduardo Ochoa-Jiménez, Francisco Rodríguez-Henríquez

ePrint Report
The Supersingular Isogeny-based Diffie-Hellman key exchange protocol (SIDH) was introduced by Jao an De Feo in 2011. SIDH operates on supersingular elliptic curves defined over quadratic extension fields of the form GF($p^2$), where $p$ is a large prime number of the form $p = 4^{e_A} 3^{e_B} - 1,$ where $e_A, e_B$ are positive integers such that $4^{e_A} \approx 3^{e_B}.$ In this paper, a variant of the SIDH protocol that we dubbed extended SIDH (eSIDH) is presented. The eSIDH variant makes use of primes of the form, $p = 4^{e_A} \ell_B^{e_B}\ell_C^{e_C} f - 1.$ Here $\ell_B, \ell_C $ are two small prime numbers; $f$ is a cofactor; and $e_A, e_B$ and $e_C$ are positive integers such that $4^{e_A} \approx \ell_B^{e_B}\ell_C^{e_C}.$ We show that for many relevant instantiations of the SIDH protocol, this new family of primes enjoys a faster field arithmetic than the one associated to traditional SIDH primes. Furthermore, the proposed eSIDH protocol preserves the length and format of SIDH private/public keys, and its richer opportunities for parallelism yields a noticeable speedup factor when implemented on multi-core platforms. Using a single-core SIDH $p_{751}$ implementation as a baseline, a parallel eSIDH $p_{765}$ instantiation yields an acceleration factor of $1.05, 1.30$ and $1.41,$ when implemented on $k = \{1, 2, 3\}$-core processors.

###### Shangqi Lai, Xingliang Yuan, Shi-Feng Sun, Joseph K. Liu, Ron Steinfeld, Amin Sakzad, Dongxi Liu

ePrint Report
Network Function Virtualisation (NFV) advances the development of composable software middleboxes. Accordingly, cloud data centres become major NFV vendors for enterprise traffic processing. Due to the privacy concern of traffic redirection to the cloud, secure middlebox systems (e.g., BlindBox) draw much attention; they can process encrypted packets against encrypted rules directly. However, most of the existing systems supporting pattern matching based network functions require tokenisation of packet payloads via sliding windows at the enterprise gateway. Such tokenisation introduces a considerable communication overhead, which can be over 100× to the packet size. To overcome the above bottleneck, in this paper, we propose the first bandwidth-efficient encrypted pattern matching protocols for secure middleboxes. We start from a primitive called symmetric hidden vector encryption (SHVE), and propose a variant of it, aka SHVE+, to enable encrypted pattern matching with constant, moderate communication overhead. To speed up, we devise encrypted filters to further reduce the number of accesses to SHVE+ during matching. We formalise the security of our proposed protocols, and implement a prototype and conduct comprehensive evaluations over real-world rulesets and traffic dumps. The results show that our design can inspect a packet over 20k rules within 100 $\mu$s. Compared to prior work, it brings a saving of 94% in bandwidth consumption.

###### Suhyeon Lee, Seungjoo Kim

ePrint Report
There have been several 51% attacks on Proof-of-Work (PoW) blockchains recently, including Verge and GameCredits, but the most noteworthy has been the attack that saw hackers make off with up to $18 million after a successful double spend was executed on the Bitcoin Gold network. For this reason, the Proof-of-Stake (PoS) algorithm, which already has advantages of energy efficiency and throughput, is attracting attention as an alternative to the PoW algorithm. With a PoS, the attacker needs to obtain 51% of the cryptocurrency to carry out a 51% attack. But unlike PoW, attacker in a PoS system is highly discouraged from launching 51% attack because he would have to risk losing his entire stake amount to do so. Moreover, even if a 51% attack succeeds, the value of PoS-based cryptocurrency will fall, and the attacker with the most stake will eventually lose the most. In this paper, we try to derive the results that go against these conventional myths. Despite of the significant depreciation of cryptocurrency, our method can make a profit from a 51% attack on the PoS blockchains using the traditional stock market's short selling (or shorting) concept. Our findings are an example to show that the conventional myth that "a destructive attack that destroys the blockchain ecosystem totally will not occur because it is fundamentally unprofitable to the attacker itself" may be wrong.

###### Sarang Noether, Brandon Goodell

ePrint Report
Ring signatures are a common construction used to provide signer ambiguity among a non-interactive set of public keys specified at the time of signing. Unlike early approaches where signature size is linear in the size of the signer anonymity set, current optimal solutions either require centralized trusted setups or produce signatures logarithmic in size. However, few also provide linkability, a property used to determine whether the signer of a message has signed any previous message, possibly with restrictions on the anonymity set choice. Here we introduce Triptych, a family of linkable ring signatures without trusted setup that is based on generalizations of zero-knowledge proofs of knowledge of commitment openings to zero. We demonstrate applications of Triptych in signer-ambiguous transaction protocols by extending the construction to openings of parallel commitments in independent anonymity sets. Signatures are logarithmic in the anonymity set size and, while verification complexity is linear, collections of proofs can be efficiently verified in batches. We show that for anonymity set sizes practical for use in distributed protocols, Triptych offers competitive performance with a straightforward construction.

###### Daniel Gardham, Mark Manulis, Constantin Cătălin Drăgan

ePrint Report
We introduce Biometric-Authenticated Keyword Search (BAKS), a novel searchable encryption scheme that relieves clients from managing cryptographic keys and relies purely on client’s biometric data for authenticated outsourcing and retrieval of files indexed by encrypted keywords.
BAKS utilises distributed trust across two servers and the liveness assumption which models physical presence of the client; in particular, BAKS security is guaranteed even if clients’ biometric data, which often has low entropy, becomes public. We formalise two security properties, Authentication and Indistinguishability against Chosen Keyword Attacks, which ensure that only a client with a biometric input sufficiently close to the registered template is considered legitimate and that neither of the two servers involved can learn any information about the encrypted keywords.
Our BAKS construction further supports outsourcing and retrieval of files using multiple keywords and flexible search queries (e.g., conjunction, disjunction and subset-type queries). An additional update mechanism allows clients to replace their registered biometrics without requiring re-encryption of outsourced keywords, which enables smooth user migration across devices supporting different types of biometrics.

###### Jan Camenisch, Manu Drijvers, Anja Lehmann, Gregory Neven, Patrick Towa

ePrint Report
Traditional group signatures feature a single issuer who can add users to the group of signers and a single opening authority who can reveal the identity of the group member who computed a signature. Interestingly, despite being designed for privacy-preserving applications, they require strong trust in these central authorities who constitute single points of failure for critical security properties. To reduce the trust placed on authorities, we introduce dynamic group signatures which distribute the role of issuer and opener over several entities, and support t_I-out-of-n_I issuance and t_O-out-of-n_O opening. We first define threshold dynamic group signatures and formalize their security. We then give an efficient construction relying on the pairing-based Pointcheval–Sanders (PS) signature scheme (CT-RSA 2018), which yields very short group signatures of two first-group elements and three exponents. We also give a simpler variant of our scheme in which issuance requires the participation of all n_I issuers, but still supports t_O-out-of-n_O opening. It is based on a new multi-signature variant of the PS scheme which allows for efficient proofs of knowledge and is a result of independent inter- est. We prove our schemes secure in the random-oracle model under a non-interactive q-type of assumption.

###### Hao Chen, Wei Dai, Miran Kim, Yongsoo Song

ePrint Report
In the past few years, significant progresses on homomorphic encryption (HE) have been made toward both theory and practice. The most promising HE schemes are based on the hardness of the Learning With Errors (LWE) problem or its ring variant (RLWE).
In this work, we present new conversion algorithms which switch between different (R)LWE-based HE schemes to take advantages of them.
Specifically, we present and combine three ideas to improve the key-switching procedure between LWE ciphertexts, transformation from LWE to RLWE, as well as packing of multiple LWE ciphertexts in a single RLWE encryption.
Finally, we demonstrate an application of building a secure channel between a client and a cloud server with lightweight encryption, low communication cost, and capability of homomorphic computation.

##### SHA-1 is a Shambles - First Chosen-Prefix Collision on SHA-1 and Application to the PGP Web of Trust

###### Gaëtan Leurent, Thomas Peyrin

ePrint Report
The SHA-1 hash function was designed in 1995 and has been widely used during two decades. A theoretical collision attack was first proposed in 2004 [WYY05], but due to its high complexity it was only implemented in practice in 2017, using a large GPU cluster [SBK+17]. More recently, an almost practical chosen-prefix collision attack against SHA-1 has been proposed [LP19]. This more powerful attack allows to build colliding messages with two arbitrary prefixes, which is much more
threatening for real protocols.

In this paper, we report the first practical implementation of this attack, and its impact on real-world security with a PGP/GnuPG impersonation attack. We managed to significantly reduce the complexity of collisions attack against SHA-1: on an Nvidia GTX 970, identical-prefix collisions can now be computed with a complexity of $2^{61.2}$ rather than $2^{64.7}$, and chosen-prefix collisions with a complexity of $2^{63.4}$ rather than $2^{67.1}$. When renting cheap GPUs, this translates to a cost of 11k US\$ for a collision, and 45k US\$ for a chosen-prefix collision, within the means of academic researchers. Our actual attack required two months of computations using 900 Nvidia GTX 1060 GPUs (we paid 75k US\$ because GPU prices were higher, and we wasted some time preparing the attack).

Therefore, the same attacks that have been practical on MD5 since 2009 are now practical on SHA-1. In particular, chosen-prefix collisions can break signature schemes and handshake security in secure channel protocols (TLS, SSH). We strongly advise to remove SHA-1 from those type of applications as soon as possible. We exemplify our cryptanalysis by creating a pair of PGP/GnuPG keys with different identities, but colliding SHA-1 certificates. A SHA-1 certification of the first key can therefore be transferred to the second key, leading to a forgery. This proves that SHA-1 signatures now offers virtually no security in practice. The legacy branch of GnuPG still uses SHA-1 by default for identity certifications, but after notifying the authors, the modern branch now rejects SHA-1 signatures (the issue is tracked as CVE-2019-14855).

In this paper, we report the first practical implementation of this attack, and its impact on real-world security with a PGP/GnuPG impersonation attack. We managed to significantly reduce the complexity of collisions attack against SHA-1: on an Nvidia GTX 970, identical-prefix collisions can now be computed with a complexity of $2^{61.2}$ rather than $2^{64.7}$, and chosen-prefix collisions with a complexity of $2^{63.4}$ rather than $2^{67.1}$. When renting cheap GPUs, this translates to a cost of 11k US\$ for a collision, and 45k US\$ for a chosen-prefix collision, within the means of academic researchers. Our actual attack required two months of computations using 900 Nvidia GTX 1060 GPUs (we paid 75k US\$ because GPU prices were higher, and we wasted some time preparing the attack).

Therefore, the same attacks that have been practical on MD5 since 2009 are now practical on SHA-1. In particular, chosen-prefix collisions can break signature schemes and handshake security in secure channel protocols (TLS, SSH). We strongly advise to remove SHA-1 from those type of applications as soon as possible. We exemplify our cryptanalysis by creating a pair of PGP/GnuPG keys with different identities, but colliding SHA-1 certificates. A SHA-1 certification of the first key can therefore be transferred to the second key, leading to a forgery. This proves that SHA-1 signatures now offers virtually no security in practice. The legacy branch of GnuPG still uses SHA-1 by default for identity certifications, but after notifying the authors, the modern branch now rejects SHA-1 signatures (the issue is tracked as CVE-2019-14855).

#### 06 January 2020

###### Nir Bitansky, Idan Gerichter

ePrint Report
We show new hardness results for the class of Polynomial Local Search problems ($\mathsf{PLS}$):

* Hardness of $\mathsf{PLS}$ based on a falsifiable assumption on bilinear groups introduced by Kalai, Paneth, and Yang (STOC 2019), and the Exponential Time Hypothesis for randomized algorithms. Previous standard model constructions relied on non-falsifiable and non-standard assumptions.

* Hardness of $\mathsf{PLS}$ relative to random oracles. The construction is essentially different than previous constructions, and in particular is unconditionally secure. The construction also demonstrates the hardness of parallelizing local search.

The core observation behind the results is that the unique proofs property of incrementally-verifiable computations previously used to demonstrate hardness in $\mathsf{PLS}$ can be traded with a simple incremental completeness property.

* Hardness of $\mathsf{PLS}$ based on a falsifiable assumption on bilinear groups introduced by Kalai, Paneth, and Yang (STOC 2019), and the Exponential Time Hypothesis for randomized algorithms. Previous standard model constructions relied on non-falsifiable and non-standard assumptions.

* Hardness of $\mathsf{PLS}$ relative to random oracles. The construction is essentially different than previous constructions, and in particular is unconditionally secure. The construction also demonstrates the hardness of parallelizing local search.

The core observation behind the results is that the unique proofs property of incrementally-verifiable computations previously used to demonstrate hardness in $\mathsf{PLS}$ can be traded with a simple incremental completeness property.

###### Erdem Alkim, Yusuf Alper Bilgin, Murat Cenk, François Gérard

ePrint Report
This paper proposes various optimizations for lattice-based key-encapsulation mechanisms (KEM) using the Number Theoretic Transform (NTT) on the popular ARM Cortex-M4 microcontroller. Improvements come in the form of a faster code using more efficient modular reductions, small polynomial multiplications and more aggressive layer merging in the NTT but also reduced stack usage. We test those optimizations in software implementations of Kyber and NewHope, both round 2 candidates in the NIST post-quantum project and also NewHope-Compact, a recently proposed derivative of NewHope with smaller parameters. Our software is the first implementation of NewHope-Compact on Cortex-M4 and shows speed improvements over previous high-speed implementations on the same platform for Kyber and NewHope . Moreover, it gives a common framework to compare those algorithms with the same level of optimization. Our results show that NewHope-Compact is the faster algorithm, followed by Kyber and finally NewHope that seems to suffer from its large modulus and error distribution for small dimensions.

###### Ming Li, Jian Weng, Jia-Nan Liu, Xiaodong Lin, Charlie Obimbo

ePrint Report
With the increasing number of traffic accidents and terrorist attacks by modern vehicles, vehicular digital forensics (VDF) has gained significant attention in identifying and determining evidences from the related digital devices. Ensuring the law enforcement agency to accurately integrate various kinds of data is a crucial point to determine the facts. However, malicious attackers or semi-honest participants may undermine the digital forensic procedures. Enabling accountability and privacy preservation while providing secure fine-grained data access control in VDF is a non-trivial challenge.
To mitigate this issue, in this paper, we propose a blockchain-based scheme for VDF named BB-VDF, in which the accountable protocols and privacy preservation methods are constructed. The desirable security properties and fine-grained data access control are achieved based on the customized smart contracts and cryptographic constructions.
Specifically, we design novel smart contracts that model the forensics procedures as a finite state machine, which guarantees accountability that each participant performs auditable cooperation under tamper-resistant and traceable transactions. Furthermore, we design a distributed key-policy attribute based encryption scheme with partially hidden access structures to realize the secure fine-grained forensics data access control. Systematic security analysis and extensive experimental results show the feasibility and practicability of the proposed BB-VDF scheme.

###### Dmitrii Koshelev

ePrint Report
The article provides a new double point compression method (to $2\log_2(q) + 4$ bits) for an elliptic $\mathbb{F}_{\!q}$-curve $E\!: y^2 = x^3 + b$ of $j$-invariant $0$ over a finite field $\mathbb{F}_{\!q}$ such that $q \equiv 1 \ (\mathrm{mod} \ 3)$. More precisely, we obtain explicit simple formulas transforming the coordinates $x_0,y_0,x_1,y_1$ of two points $P_0, P_1 \in E(\mathbb{F}_{\!q})$ to some two elements $t, s \in \mathbb{F}_{\!q}$ with four auxiliary bits. To recover (in the decompression stage) the points $P_0, P_1$ it is proposed to extract a sixth root $\sqrt[6]{w} \in \mathbb{F}_{\!q}$ of some element $w \in \mathbb{F}_{\!q}$. It is easily seen that for $q \equiv 3 \ (\mathrm{mod} \ 4)$, $q \not\equiv 1 \ (\mathrm{mod} \ 27)$ this can be implemented by means of just one exponentiation in $\mathbb{F}_{\!q}$. Therefore the new compression method seems to be much faster than the classical one with the coordinates $x_0, x_1$, whose decompression stage requires two exponentiations in $\mathbb{F}_{\!q}$.

###### Thomas Pornin

ePrint Report
In order to obtain an efficient elliptic curve with 128-bit security and
a prime order, we explore the use of finite fields $GF(p^n)$, with $p$
a small modulus (less than $2^{16}$) and $n$ a prime. Such finite fields
allow for an efficient inversion algorithm due to Itoh and Tsujii, which
we can leverage to make computations on an ordinary curve (short
Weierstraß equation) in affine coordinates. We describe a very efficient
variant of Montgomery reduction for computations modulo $p$, and choose
$p = 9767$ and $n = 19$ to better map the abilities of small
microcontrollers of the ARM Cortex-M0+ class. Inversion cost is only six
times the cost of multiplication. Our fully constant-time implementation
of curve point multiplication runs in about 4.5 million cycles (only
1.29 times slower than the best reported Curve25519 implementations); it
also allows for efficient key pair generation (about 1.9 million cycles)
and Schnorr signature verification (about 5.6 million cycles). Moreover,
we describe variants of the Itoh-Tsujii algorithms that allow fast
computations of square roots and cube roots (in less than twenty times
the cost of a multiplication), leading to efficient point compression
and constant-time hash-to-curve operations with Icart's map.

###### Oriol Farràs

ePrint Report
A secret sharing scheme is ideal if the size of each share is equal to the size of the secret. Brickell and Davenport showed that the access structure of an ideal secret sharing scheme is determined by a matroid. Namely, the minimal authorized subsets of an ideal secret sharing scheme are in correspondence with the circuits of a matroid containing a fixed point. In this case, we say that the access structure is a matroid port. It is known that, for an access structure, being a matroid port is not a sufficient condition to admit an ideal secret sharing scheme.

In this work we present a linear secret sharing scheme construction for ports of matroids of rank 3 in which the size of each share is at most $n$ times the size of the secret. Using the previously known secret sharing constructions, the size of each share was $O(n^2/\log n)$ the size of the secret.

Our construction is extended to ports of matroids of any rank $k\geq 2$, obtaining secret sharing schemes in which the size of each share is at most $n^{k-2}$ times the size of the secret. This work is complemented by presenting lower bounds: There exist matroid ports that require $(F_q,\ell)$-linear secret schemes with total information ratio $\Omega(2^{n/2}/\ell n^{3/4}\sqrt{\log q})$.

In this work we present a linear secret sharing scheme construction for ports of matroids of rank 3 in which the size of each share is at most $n$ times the size of the secret. Using the previously known secret sharing constructions, the size of each share was $O(n^2/\log n)$ the size of the secret.

Our construction is extended to ports of matroids of any rank $k\geq 2$, obtaining secret sharing schemes in which the size of each share is at most $n^{k-2}$ times the size of the secret. This work is complemented by presenting lower bounds: There exist matroid ports that require $(F_q,\ell)$-linear secret schemes with total information ratio $\Omega(2^{n/2}/\ell n^{3/4}\sqrt{\log q})$.

#### 05 January 2020

###### Shanghai Jiao Tong University, Shanghai, China

Job Posting
The Crypto-System Laboratory (CSL) at the Department of Computer Science, Shanghai Jiao Tong University is looking for candidates for 2 postdoctoral positions and 2 research fellows/associates on cryptography, including but not limited to the following:

- privacy-preserving computation (MPC, FHE, ZKP, etc.)
- lattice-based cryptography
- side-channel attacks and leakage-resilient cryptography
- blockchain technologies (consensus, security and integration with IoT)
- cryptographic implementations and optimizations

**Closing date for applications:**

**Contact:** Dr. Yu Yu ( yyuu@sjtu.edu.cn )

**More information:** https://crypto.sjtu.edu.cn/lab/

###### University of Strathclyde, Glasgow, Scotland

Job Posting
The Department of Electronic and Electrical Engineering, Institute of Sensors, Signals and Communications seeks to appoint a Research Associate in the area of cyber security simulation platform for the H2020 Advanced cyber-security simulation platform for preparedness training in Aviation, Naval and Power-grid environments (FORESIGHT) project. The FORESIGHT project will develop a federated cyber-range solution to enhance the preparedness of cyber-security professionals at all levels and advance their skills towards preventing, detecting, reacting and mitigating sophisticated cyber-attacks thus providing a holistic approach to cyber-threat management and cultivate a strong security culture. In particular, you will be responsible to provide an ecosystem of networked realistic training and simulation platforms from the aviation, smart grid and naval domains. The creation of complex cross-domain/hybrid scenarios will extend the capabilities of existing solutions with an emphasis on realistic and dynamic scenarios based on cyber-attacks and vulnerabilities gathered from the dark web.

A full description can be foud here:

https://academicpositions.com/ad/university-of-strathclyde/2019/research-associate-in-cyber-security-simulation-platforms-h2020-foresight-258336/137449

A full description can be foud here:

https://academicpositions.com/ad/university-of-strathclyde/2019/research-associate-in-cyber-security-simulation-platforms-h2020-foresight-258336/137449

**Closing date for applications:**

**Contact:** Please contact Dr Xavier Bellekens ** before ** applying with a CV at xavier.bellekens@strath.ac.uk

**More information:** https://academicpositions.com/ad/university-of-strathclyde/2019/research-associate-in-cyber-security-simulation-platform

#### 03 January 2020

###### Putrajaya, Malaysia, 9 June - 11 June 2020

Event Calendar
Event date: 9 June to 11 June 2020

Submission deadline: 14 March 2020

Notification: 15 May 2020

Submission deadline: 14 March 2020

Notification: 15 May 2020

###### Cairo, Egypt, 22 July 2020

Event Calendar
Event date: 22 July 2020

Submission deadline: 1 February 2020

Notification: 30 April 2020

Submission deadline: 1 February 2020

Notification: 30 April 2020

###### Zagreb, Croatia, 10 May 2020

Event Calendar
Event date: 10 May 2020

Submission deadline: 20 March 2020

Notification: 10 April 2020

Submission deadline: 20 March 2020

Notification: 10 April 2020