International Association
for Cryptologic Research

Dear IACR members,

In-between a memorable Eurocrypt in Darmstadt and an exciting Crypto coming up in August, let me share some recent developments in the IACR.

Cryptology ePrint Archive

After four years of serving as one of two editors, Alexandra Boldyreva has stepped down. Approving the eprints according to minimal acceptance criteria is an important task that benefits everyone in the field. Speaking for IACR, I thank her for all the work with this and wish her a well-deserved break from the flood of submissions.

The Board has appointed Joppe Bos to new co-editor; he shares this position with Tancrède Lepoint.

Communications Secretary

A second change has taken place with the responsible for communications: Mike Rosulek has driven publicity for IACR during the last five years. On behalf of the organization, I thank him for all his efforts, his diligence, and many late-night shifts.

The Board has appointed Foteini Baldimtsi as new Communications Secretary; she oversees a growing team of multiple people who operate the online and communication services. Welcome to the Board!

Eurocrypt 2021 in Norway and Asiacrypt 2021 in Singapore

Eurocrypt will return to Norway in 2021 (after 1993 in Lofthus) and take place Trondheim, with Colin Boyd serving as General Chair. For Asiacrypt 2021 the IACR has selected a proposal from Singapore, organized by Guo Jian of the Nanyang Technological University.

We thank them and all other conference organizers for creating the leading conferences in the field. It is a multi-year effort to organize an event attended by several hundred people and means a great investment of time and energy. But organizing an event also provides the rewarding opportunity to leave lasting memories with all attendees. Bringing together everyone, including newcomers, students, senior researchers and everyone else with a common interest in cryptologic research, is an important aspect that goes beyond the scientific progress. In this sense I invite everyone who is in a position to do so, to think about contributing to IACR and potentially organize a future event -- just approach any Board member with your ideas.

The Board has discussed many further topics at the recent Eurocrypt meeting and also earlier at virtual meetings; you can find the meeting minutes online at https://www.iacr.org/docs/minutes/

Website renewal

A few days ago the web team has upgraded the IACR website with a completely new, responsive design. I invite you to check it out at https://iacr.org/. The new implementation renders the content nicely on any platform, from mobile phone to tablet and desktop.

On behalf of the IACR, I sincerely thank Kevin McCurley for the tremendous effort he has put into the upgrade. As a former IACR treasurer, president, and creator of the initial website, his contributions and dedication are exemplary!

I am looking forward to seeing many of you at CRYPTO in Santa Barbara! Please note that the early-registration deadline is on July 19th.

Christian Cachin
IACR President

After a long development cycle, the iacr.org website has been updated with a style that is better suited for use on both desktop and phones. Some outdated features were phased out, while others still require further development. We welcome feedback or suggestions for new features via email to webfeedback at iacr.org.

Event date: 24 February to 28 February 2020
Submission deadline: 20 September 2019
Notification: 15 November 2019

Event date: 6 November 2019

Event date: 31 March to 1 April 2020

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.

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.

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.

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.

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.

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.

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.

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.

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.

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.

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.

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.

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.

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.

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.