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

#### 18 July 2019

###### Ronald Cramer, Matthieu Rambaud, Chaoping Xing

ePrint Report
This paper deals with (1) asymptotics of ``strongly-multiplicative'' arithmetic secret sharing over an arbitrary fixed ring $R_\ell:=\mathbb{Z}/p^{\ell}\mathbb{Z}$ ($p>0$ prime, $\ell>0$ an integer) and supporting an unbounded number of players $n$, and with (2) its applications to communication complexity of arithmetic MPC over this ring.
For each integer $r>0$, let $R_\ell(r)$ be the degree-$r$ Galois-ring extension of $R_\ell$, with maximal ideal $p$, residue field $(R_\ell(r))/p=\mathbb{F}_{p^{r}}$, and $|R_\ell(r)|= p^{\ell r}$.

Using theory of AG-codes over finite fields and over rings, combined with nontrivial algebraic-geometric lifting techniques, we show that, for arbitrary fixed ring $R_\ell=\mathbb{Z}/p^{\ell}\mathbb{Z}$, there is a fixed integer $\hat{r}=\hat{r}(p)>0$ and a (dense) family of $R_\ell(\hat{r})$-linear codes $C$ of unbounded length such that:

-- Denoting the reduction of $C$ modulo $p$ (an $\mathbb{F}_{p^{\hat{r}}}$-linear code) by $\overline{C}$, each of $\overline{C}$, $(\overline{C})^{\bot}$ (dual), $(\overline{C})^{\ast 2}$ ("square under Schur-product'') is asymptotically good. -- Each of $C$, $C^{\bot}$, $C^{\ast 2}$ is free over $R_\ell(\hat{r})$, with the same dimension as its reduction. Therefore, each has the same minimum distance as its reduction. Particularly, each is asymptotically good.

-- All constructions are efficient.

This implies arithmetic secret sharing over the fixed ring $\mathbb{Z}/p^{\ell}\mathbb{Z}$ (rather, the constant-degree extension) with unbounded (dense) $n$, secret-space dimension $\Omega(n)$, share-space dimension $O(1)$, $t$-privacy $\Omega(n)$ with $t$-wise share-uniformity and $1/3 - t/n>0$ a constant arbitrarily close to 0, and, ---last-but-not-least---, ``multiplicativity-locality'' $n-t$. This extends Chen-Cramer (CRYPTO 2006), which only works over any (large enough) finite fields, significantly. Concrete parameters we show here are at least as large.

We also show a similar lifting result for asymptotically-good reverse multiplication-friendly embeddings (RFME) and we show how to get an asymptotically-good alternative for the functionality of "hyper-invertible matrices" (essential for efficient active-security MPC), as the latter are inherently asymptotically-bad.

Finally, we give two applications to general arithmetic MPC over $\mathbb{Z}/p^{\ell}\mathbb{Z}$ (in the BGW-model with active, perfect security) with communication complexity significantly better than the obvious approach based on combining MPC over $\mathbb{F}_p$ with added circuitry for emulation of the basic $\mathbb{Z}/p^{\ell}\mathbb{Z}$-operations over $\mathbb{F}_p$. Concretely, recent results by Cascudo-Cramer-Xing-Yuan on amortized complexity of MPC (CRYPTO 2018) are now achievable over these rings instead of finite fields, with the same asymptotic complexity and adversary rates.

Using theory of AG-codes over finite fields and over rings, combined with nontrivial algebraic-geometric lifting techniques, we show that, for arbitrary fixed ring $R_\ell=\mathbb{Z}/p^{\ell}\mathbb{Z}$, there is a fixed integer $\hat{r}=\hat{r}(p)>0$ and a (dense) family of $R_\ell(\hat{r})$-linear codes $C$ of unbounded length such that:

-- Denoting the reduction of $C$ modulo $p$ (an $\mathbb{F}_{p^{\hat{r}}}$-linear code) by $\overline{C}$, each of $\overline{C}$, $(\overline{C})^{\bot}$ (dual), $(\overline{C})^{\ast 2}$ ("square under Schur-product'') is asymptotically good. -- Each of $C$, $C^{\bot}$, $C^{\ast 2}$ is free over $R_\ell(\hat{r})$, with the same dimension as its reduction. Therefore, each has the same minimum distance as its reduction. Particularly, each is asymptotically good.

-- All constructions are efficient.

This implies arithmetic secret sharing over the fixed ring $\mathbb{Z}/p^{\ell}\mathbb{Z}$ (rather, the constant-degree extension) with unbounded (dense) $n$, secret-space dimension $\Omega(n)$, share-space dimension $O(1)$, $t$-privacy $\Omega(n)$ with $t$-wise share-uniformity and $1/3 - t/n>0$ a constant arbitrarily close to 0, and, ---last-but-not-least---, ``multiplicativity-locality'' $n-t$. This extends Chen-Cramer (CRYPTO 2006), which only works over any (large enough) finite fields, significantly. Concrete parameters we show here are at least as large.

We also show a similar lifting result for asymptotically-good reverse multiplication-friendly embeddings (RFME) and we show how to get an asymptotically-good alternative for the functionality of "hyper-invertible matrices" (essential for efficient active-security MPC), as the latter are inherently asymptotically-bad.

Finally, we give two applications to general arithmetic MPC over $\mathbb{Z}/p^{\ell}\mathbb{Z}$ (in the BGW-model with active, perfect security) with communication complexity significantly better than the obvious approach based on combining MPC over $\mathbb{F}_p$ with added circuitry for emulation of the basic $\mathbb{Z}/p^{\ell}\mathbb{Z}$-operations over $\mathbb{F}_p$. Concretely, recent results by Cascudo-Cramer-Xing-Yuan on amortized complexity of MPC (CRYPTO 2018) are now achievable over these rings instead of finite fields, with the same asymptotic complexity and adversary rates.

###### Cristian Hristea, Ferucio Laurentiu Tiplea

ePrint Report
There is a major interest in designing RFID schemes based on symmetric-key cryptography and ensuring efficient tag identification. These requirements taken together often lead to a decrease in the degree of privacy provided by the scheme.
This issue, as we know, has been treated in an ad-hoc manner so far.

In this paper, we introduce the class of stateful RFID schemes with constant tag identifiers, that ensure tag identification in no more than logarithmic time. In order to study their privacy, we propose an appropriate general model obtained by constraining Vaudenay's model. We then propose two symmetric-key cryptography based RFID schemes in this class that achieve weak and destructive privacy, respectively, in addition to mutual authentication. We also discuss on the degree of privacy provided by other schemes proposed in the literature, that fall in this class.

In this paper, we introduce the class of stateful RFID schemes with constant tag identifiers, that ensure tag identification in no more than logarithmic time. In order to study their privacy, we propose an appropriate general model obtained by constraining Vaudenay's model. We then propose two symmetric-key cryptography based RFID schemes in this class that achieve weak and destructive privacy, respectively, in addition to mutual authentication. We also discuss on the degree of privacy provided by other schemes proposed in the literature, that fall in this class.

###### Diego F. Aranha, Elena Pagnin

ePrint Report
We consider the problem of outsourcing computation on data authenticated by different users. Our aim is to describe and implement the simplest possible solution to provide data integrity in cloud-based scenarios. Concretely, our multi-key linearly homomorphic signature scheme (mklhs) allows users to upload signed data on a server, and at any later point in time any third party can query the server to compute a linear combination of data authenticated by different users and check the correctness of the returned result. Our construction generalizes Boneh et al.'s linearly homomorphic signature scheme (PKC'09) to the multi-key setting and relies on basic tools of pairing-based cryptography. Compared to existing multi-key homomorphic signature schemes, our mklhs is a conceptually simple and elegant direct construction, which trades-off privacy for efficiency. The simplicity of our approach leads us to a very efficient construction that enjoys significantly shorter signatures and higher performance than previous proposals. Finally, we implement mklhs using two different pairing-friendly curves at the 128-bit security level, a Barreto-Lynn-Scott curve and a Barreto-Naehrig curve. Our benchmarks illustrate interesting performance trade-offs between these parameters, involving the cost of exponentiation and hashing in pairing groups. We provide a discussion on such trade-offs that can be useful to other implementers of pairing-based protocols.

###### Billy Bob Brumley, Sohaib ul Hassan, Alex Shaindlin, Nicola Tuveri, Kide Vuojärvi

ePrint Report
Bitslicing is a programming technique that offers several attractive features,
such as timing attack resistance, high amortized performance in batch
computation, and architecture independence. On the symmetric crypto side, this
technique sees wide real-world deployment, in particular for block ciphers with
naturally parallel modes. However, the asymmetric side lags in application,
seemingly due to the rigidity of the batch computation requirement. In this
paper, we build on existing bitsliced binary field arithmetic results to develop
a tool that optimizes performance of binary fields at any size on a given
architecture. We then provide an ECC layer, with support for arbitrary binary
curves. Finally, we integrate into our novel dynamic OpenSSL engine,
transparently exposing the batch results to the OpenSSL library and linking
applications to achieve significant performance and security gains for key pair
generation, ECDSA signing, and (half of) ECDH across a wide range of curves,
both standardized and non-standard.

###### Cezary Glowacz, Vincent Grosso

ePrint Report
Collision side-channel attacks are efficient attacks against cryptographic implementations, however, optimal collision side-channel attacks and how to compute them efficiently is an open question. In this paper, we show that collision side-channel attacks can be derived using the maximum likelihood principle when the distribution of the values of the leakage function is known. This allows us to exhibit the optimal collision side-channel attack and its efficient computation. Finally, we are able to compute an upper bound for the success rate of the optimal post-processing strategy, and we show that our method and the optimal strategy have success rates close to each other. Attackers can benefit from our method as we present an efficient collision side-channel attack. Evaluators can benefit from our method as we present a tight upper bound for the success rate of the optimal strategy.

#### 17 July 2019

###### Zvi Schreiber

ePrint Report
Blockchains such as bitcoin rely on reaching global consensus for the distributed ledger, and suffer from a well know scalability problem. We propose an algorithm which can avoid double spending in the short term with just $O(\sqrt{n})$ messages, relying on the fact that the velocity of money in the real world has coins generally circulating through at most a few wallets per day. The algorithm should be practical to avoid double spending with arbitrarily high probability, while feasibly coping with all the commerce in the world. This k-root-n algorithm is less effective in the long term once money circulates through a significant proportion of the world’s wallets, and should therefore be used as a complement to a global consensus. Thus, global consensus can be reached periodically and with a considerable lag, while money can be safely spent with quick transactions in-between.

###### Erdinç Öztürk

ePrint Report
Modular multiplication is one of the most compute-intensive arithmetic operations. Most public-key cryptosytems utilize modular multiplications of integers of various lengths, depending on security requirements. Efficient algorithms and implementations are required to realize a practical public-key cryptosystem. Different parameters, such as area, power and time, can be optimized for different implementation requirements. Low latency was not as important as high throughput requirement for modular multiplication implementations before. However, with recent work on Verifiable Delay Functions (VDFs), a necessity for lowest possible latency for modular multiplication implementations emerged. VDFs are designed to take a prescribed time to realize the underlying computation that can be publicly verified. VDF constructions are required to utilize inherently sequential arithmetic operations. Efficient VDF constructions have been proposed recently, based on time-lock puzzles constructed by Rivest, Shamir and Wagner. An exponentiation operation in an RSA group needs to be realized for these VDF constructions. For these VDF constructions to be practical, low-latency modular multiplication algorithms and implementations are required. In this paper, a modular multiplication algorithm suitable for low-latency circuit implementations is proposed and an FPGA-optimized variant of this algorithm is presented.

###### Takanori Isobe, Kazuhiko Minematsu

ePrint Report
XTS is an encryption scheme for storage devices standardized by IEEE and NIST. It is based on Rogaway's XEX tweakable block cipher and is known to be secure up to the collisions between the blocks, thus up to around $2^{n/2}$ blocks for $n$-bit blocks. However this only implies that the theoretical indistinguishability notion is broken with $O(2^{n/2})$ queries and does not tell the practical risk against the plaintext recovery if XTS is targeted. We show several plaintext recovery attacks against XTS beyond collisions, and evaluate their practical impacts.

#### 16 July 2019

###### Behnaz Rezvani, William Diehl

ePrint Report
Security in the Internet of Things (IoT) is challenging. The need for lightweight yet robust cryptographic solutions suitable for the IoT calls for improved design and implementation of constructs such as Authenticated Encryption with Associated Data (AEAD) which can ensure confidentiality, integrity and authenticity of data in one algorithm. The U.S. National Institute of Standards and Technology (NIST) has embarked on a multi-year effort called the Lightweight Cryptography (LWC) Standardization Process to evaluate lightweight AEAD and optional hash algorithms for inclusion in U.S. federal standards. As candidates are evaluated for many characteristics including hardware resources and performance, obtaining results of hardware implementations as early as possible, i.e., even in round 1, is preferable. In this research, we implement three NIST LWC round 1 candidate ciphers, SpoC, Spook, and GIFT-COFB, in the Artix-7 FPGA. Implementations are compliant with the previously-validated CAESAR Hardware Applications Programming Interface (API) for Authenticated Ciphers, and are tested in actual hardware. Implementations show that GIFT-COFB has the highest Throughput-to-Area (TPA) ratio, by a 4.4 factor margin over Spook. Additionally, the results illustrate hardware implementation challenges associated with integrating multiple cryptographic primitives into one design, as well as complexities due to padding and truncation.

###### Jeffrey Champion, abhi shelat, Jonathan Ullman

ePrint Report
We design an efficient method for sampling a large batch of $d$ independent coins with a given bias $p \in [0,1]$. The folklore secure computation method for doing so requires $O(\lambda + \log d)$ communication an computation per coin to achieve sampling error $2^{-\lambda}$. We present an exponential improvement over the folklore method that uses just $O(\log(\lambda+\log d))$ gates per coin when sampling $d$ coins with total sampling error $2^{-\lambda}$. We present a variant of our work that also concretely beats the folklore method for $\lambda \leq 2^{-60}$ which are parameters that are often used in practice. Our new technique relies on using specially designed oblivious data structures to achieve biased coin samples that take an expected $2$ random bits to sample.

Using our new sampling technique, we present an implementation of the differentially private report-noisy-max mechanism (a more practical implementation of the celebrated exponential mechanism) as a secure multi-party computation. Our benchmarks show that one can run this mechanism on a domain of size $d=2^{12}$ in 6 seconds and up to $d=2^{19}$ in 14 minutes. As far as we know, this is the first complete distributed implementation of either of these mechanisms.

Using our new sampling technique, we present an implementation of the differentially private report-noisy-max mechanism (a more practical implementation of the celebrated exponential mechanism) as a secure multi-party computation. Our benchmarks show that one can run this mechanism on a domain of size $d=2^{12}$ in 6 seconds and up to $d=2^{19}$ in 14 minutes. As far as we know, this is the first complete distributed implementation of either of these mechanisms.

###### Ben Smyth

ePrint Report
We explore definitions of coercion resistance in the computational model of cryptography; discovering all but one are too weak (i.e., satisfiable by voting systems that are not coercion resistant) and the other is too strong (i.e., unsatisfiable by voting systems that are). Hence, we show that coercion resistance has not been adequately formalised. Our results cast doubt over the security of voting systems that have been proven secure with respect to those definitions; a new definition is necessary.

###### Eman Salem Alashwali, Pawel Szalachowski, Andrew Martin

ePrint Report
Forward Secrecy (FS) is a security property in key-exchange algorithms which guarantees that a compromise in the secrecy of a long-term private-key does not compromise the secrecy of past session keys. With a growing awareness of long-term mass surveillance programs by governments and others, FS has become widely regarded as a highly desirable property. This is particularly true in the TLS protocol, which is used to secure Internet communication. In this paper, we investigate FS in pre-TLS 1.3 protocols, which do not mandate FS, but still widely used today. We conduct an empirical analysis of over 10 million TLS servers from three different datasets using a novel heuristic approach. Using a modern TLS client handshake algorithms, our results show 5.37% of top domains, 7.51% of random domains, and 26.16% of random IPs do not select FS key-exchange algorithms. Surprisingly, 39.20% of the top domains, 24.40% of the random domains, and 14.46% of the random IPs that do not select FS, do support FS. In light of this analysis, we discuss possible paths toward forward secure Internet traffic. As an improvement of the current state, we propose a new client-side mechanism that we call "Best Effort Forward Secrecy" (BEFS), and an extension of it that we call "Best Effort Forward Secrecy and Authenticated Encryption" (BESAFE), which aims to guide (force) misconfigured servers to FS using a best effort approach. Finally, within our analysis, we introduce a novel adversarial model that we call "discriminatory" adversary, which is applicable to the TLS protocol.

###### Asma Aloufi, Peizhao Hu, Hang Liu, Sherman S. M. Chow

ePrint Report
Location data is an important piece of contextual information in location-driven features for geosocial and pervasive computing applications. In this paper, we propose to geo-hash locations using space-filling curves, which are dimension reduction techniques that preserve locality. The proposed location referencing method is agnostic to specific maps or precoded location models and can effectively preserve users’ location privacy based on user preferences. We employ post-quantum-secure encryption on location data and privacy preferences to minimize the risk of data leakage. We also design three algorithms to homomorphically compute geospatial queries on the encrypted location data without revealing either user locations or user preferences. One of the three proposed algorithms reduces the multiplicative depth by more than half; thus, significantly speeding up homomorphic computations. We then present a prototype of the proposed system and algorithms using a somewhat homomorphic encryption scheme and our optimization techniques. A systematic evaluation of the prototype demonstrates its utility in spatial cloaking.

###### Asma Aloufi, Peizhao Hu, Harry W. H. Wong, Sherman S. M. Chow

ePrint Report
Decision tree and its generalization of random forests are a simple yet powerful machine learning model for many classification and regression problems. Recent works propose how to privately evaluate a decision tree in a two-party setting where the feature vector of the client or the decision tree model (such as the threshold values of its nodes) is kept a secret from another party. However, these works cannot be extended trivially to support the outsourcing setting where a third-party who should not have access to the model or the query. Furthermore, their use of an interactive comparison protocol does not support branching program, hence requires interactions with the client to determine the comparison result before resuming the evaluation task.
In this paper, we propose the first secure protocol for collaborative evaluation of random forests contributed by multiple owners. They outsource evaluation tasks to a third-party evaluator. Upon receiving the client’s encrypted inputs, the cloud evaluates obliviously on individually encrypted random forest models and calculates the aggregated result. The system is based on our new secure comparison protocol, secure counting protocol, and a multi-key somewhat homomorphic encryption on top of symmetric-key encryption. This allows us to reduce communication overheads while achieving round complexity lower than existing work.

###### Debayan Das, Anupam Golder, Josef Danial, Santosh Ghosh, Arijit Raychowdhury, Shreyas Sen

ePrint Report
This article, for the first time, demonstrates Cross-device Deep Learning Side-Channel Attack (X-DeepSCA), achieving an accuracy of $>99.9\%$, even in presence of significantly higher inter-device variations compared to the inter-key variations. Augmenting traces captured from multiple devices for training and with proper choice of hyper-parameters, the proposed 256-class Deep Neural Network (DNN) learns accurately from the power side-channel leakage of an AES-128 target encryption engine, and an N-trace ($N\leq10$) X-DeepSCA attack breaks different target devices within seconds compared to a few minutes for a correlational power analysis (CPA) attack, thereby increasing the threat surface for embedded devices significantly. Even for low SNR scenarios, the proposed X-DeepSCA attack achieves $\sim10\times$ lower minimum traces to disclosure (MTD) compared to a traditional CPA.

###### Xiamen, China, 6 December - 9 December 2019

Event Calendar
Event date: 6 December to 9 December 2019

Submission deadline: 1 August 2019

Notification: 1 September 2019

Submission deadline: 1 August 2019

Notification: 1 September 2019

#### 14 July 2019

###### Tapas Pal, Ratna Dutta

ePrint Report
Non-zero inner product encryption (NIPE) allows a user to encrypt a message with its attribute vector and decryption is possible using a secret-key associated with a predicate vector if the inner product of the vectors is non-zero. The concept of NIPE was put forth by Katz, Sahai and Waters (EUROCRYPT 2008). Following that many NIPE constructions were proposed along with interesting applications. The security of all these works is based on hardness assumptions in pairing-friendly groups. Recently, Katsumata and Yamada (PKC 2019) built a NIPE relying on the Learning-with-Errors (LWE) problems, however, their system practically lags behind for providing only selective security with significantly large sizes of master public-key, secret-keys and ciphertexts. Despite its cryptographic importance, past history of NIPE is not convincing in terms of both security and practical efficiency as the schemes are either selectively secure or depend on bilinear maps.

In this paper, our goal is to construct adaptively secure efficient NIPEs. Firstly, we provide adaptively secure public-key NIPE under the standard Decision Diffie-Hellman (DDH) assumption that enables one to encrypt messages of sufficiently small length. To overcome this limitation we rely on the Decision Diffie-Hellman-f (DDH-f) and the Hard Subgroup Membership (HSM) assumptions proposed by Castagnos et al. in ASIACRYPT 2018. Consequently, we construct two pNIPEs, adaptively secure under the DDH-f and HSM assumptions respectively, both are capable of encrypting large messages with inner products over integers. We upgrade these two pNIPEs so that it can encrypt messages with unbounded inner products modulo an arbitrary large prime p. In addition, utilizing inner product functional encryptions we provide attribute-hiding public-key NIPEs depending on the DDH, DDH-f, HSM, LWE, Decision Composite Reciprocity assumptions and establish full-hiding private-key NIPEs based on the Decision linear and Symmetric External Diffie-Hellman assumptions.

In this paper, our goal is to construct adaptively secure efficient NIPEs. Firstly, we provide adaptively secure public-key NIPE under the standard Decision Diffie-Hellman (DDH) assumption that enables one to encrypt messages of sufficiently small length. To overcome this limitation we rely on the Decision Diffie-Hellman-f (DDH-f) and the Hard Subgroup Membership (HSM) assumptions proposed by Castagnos et al. in ASIACRYPT 2018. Consequently, we construct two pNIPEs, adaptively secure under the DDH-f and HSM assumptions respectively, both are capable of encrypting large messages with inner products over integers. We upgrade these two pNIPEs so that it can encrypt messages with unbounded inner products modulo an arbitrary large prime p. In addition, utilizing inner product functional encryptions we provide attribute-hiding public-key NIPEs depending on the DDH, DDH-f, HSM, LWE, Decision Composite Reciprocity assumptions and establish full-hiding private-key NIPEs based on the Decision linear and Symmetric External Diffie-Hellman assumptions.

###### Mirco Richter

ePrint Report
A framework for asynchronous, signature free, fully local and probabilistically converging total order algorithms is developed, that may survive in high entropy, unstructured Peer-to-Peer networks with near optimal communication efficiency. Regarding the natural boundaries of the CAP-theorem, the protocol chooses different compromises for consistency and availability, depending on the severity of the attack.

The family is parameterized by a few constants and external functions called voting-weight, incentivation and punishement, difficulty oracle and quorum-selector. These functions are necessary to fine tune the dynamics and very different long term behavior might appear, depending on any actual choice.

The family is parameterized by a few constants and external functions called voting-weight, incentivation and punishement, difficulty oracle and quorum-selector. These functions are necessary to fine tune the dynamics and very different long term behavior might appear, depending on any actual choice.

###### Selçuk Kayacan

ePrint Report
The basic Supersingular Isogeny Diffie-Hellman (SIDH) key agreement protocol is insecure due to an attack described by Galbraith, Petit, Shani and Ti. In this note we present two variants of SIDH that are immune to this attack.

###### Sean Bowe

ePrint Report
Pairing-friendly elliptic curve constructions provide two elliptic curve groups which are both of prime order $q$ and usually each have a nontrivial cofactor $h$. Due to the way these curves are typically constructed, endomorphisms can be applied to perform fast cofactor multiplication. However, cofactor multiplication is sometimes insufficient for dealing with cofactors, such as with malleability attacks.

In this brief note, we describe efficient techniques for checking that points exist within the correct $q$-order subgroups of the BLS12-381 elliptic curve construction, which is the focus of standardization for pairing-based protocols. Instead of multiplying by $q$ and comparing the point with the identity, we use endomorphisms to eliminate the $q$-torsion while modifying (but not killing) the $h$-torsion components. The result can then be compared against the identity.

In this brief note, we describe efficient techniques for checking that points exist within the correct $q$-order subgroups of the BLS12-381 elliptic curve construction, which is the focus of standardization for pairing-based protocols. Instead of multiplying by $q$ and comparing the point with the identity, we use endomorphisms to eliminate the $q$-torsion while modifying (but not killing) the $h$-torsion components. The result can then be compared against the identity.