International Association
for Cryptologic Research

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.

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.

Proof-of-stake (PoS) has been shown to be a suitable replacement—in many respects—for the expensive proof-of-work mechanism introduced by the Bitcoin protocol. Nevertheless, one common and seemingly intrinsic shortcoming of all existing PoS blockchains in the permissionless “dynamic availability” setting introduced by Badertscher et al. [CCS 2018], where parties come and go without warning, is that they require explicit use of a common notion of time among the participants, i.e., a “global” clock that provides the correct time on demand.

We design and analyze a PoS blockchain protocol that we prove UC-secure without assuming access to a global time functionality. Central to our construction is a novel clock synchronization mechanism that enables joining parties to adjust their local clocks correctly, relying only on knowledge of the genesis block and the assumption that their local, initially desynchronized clocks advance at approximately the same speed. This is particularly challenging as we work in the dynamic availability setting which addresses optimal resilience under arbitrary and potential adversarial participation patterns. As a corollary of our construction, we obtain a permissionless PoS implementation of a global clock that may be used whenever access to global time is a requirement in a higher level protocol.

CSIDH is a recent quantum-resistant primitive based on the difficulty of finding isogeny paths between supersingular curves. Recently, two constant-time versions of CSIDH have been proposed: first by Meyer, Campos and Reith, and then by Onuki, Aikawa, Yamazaki and Takagi. While both offer protection against timing attacks and simple power consumption analysis, they are vulnerable to more powerful attacks such as fault injections. In this work, we identify and repair two oversights in these algorithms that compromised their constant-time character. By exploiting Edwards arithmetic and optimal addition chains, we produce the fastest constant-time version of CSIDH to date. We then consider the stronger attack scenario of fault injection, which is relevant for the security of CSIDH static keys in embedded hardware. We propose and evaluate a dummy-free CSIDH algorithm. While these CSIDH variants are slower, their performance is still within a small constant factor of less- protected variants. Finally, we discuss derandomized CSIDH algorithms.

We explore two main issues in the performance of Secure Two- Party Computation (2PC): (1) interaction of 2PC with the transport layer and (2) evaluation of 2PC implementations.

Transport layer: Although significantly improved, the performance of 2PC is still prohibitive for practical systems. Contrary to the common belief that bandwidth is the remaining bottleneck for 2PC implementation, we show that the network is under-utilised due to the use of standard TCP sockets. Nevertheless, using other sockets is a nontrivial task: the developers of secure computation need to integrate them into the operating systems, which is challenging even for systems experts. To resolve this issue, and break the efficiency barrier of 2PC, we design and develop a framework, we call Transputation, which automates the integration of transport layer sockets into 2PC implementations. The goal of Transputation is to enable developers of 2PC protocols to easily identify and use the optimal transport layer protocol for the given computation task and network conditions and hence to improve performance of secure computation.

We integrated selected transport layer protocols into Transputation and evaluated the performance for a number of computational tasks. As a highlight, even a general purpose transport layer protocol, such as SABUL, improves the run-time of 2PC over TCP on EU-Australia connection for circuits with $ > 10^6 $ Boolean gates by a factor of $ 8 $.

Evaluations of 2PC: Evaluations of 2PC implementations do not reflect performance in real networks since they are typically done on simulated environments and even more often on a single host. To address this issue, we provide a testbed platform for evaluation of 2PC implementations in real life settings on the Internet.

Smart contracts are programmable, decentralized and transparent financial applications. Because smart contract platforms typically support Turing-complete programming languages, such systems are often said to enable arbitrary applications. However, the current permissionless smart contract systems impose heavy restrictions on the types of computations that can be implemented. For example, the globally-replicated and sequential execution model of Ethereum requires gas limits that make many computations infeasible.

In this paper, we propose a novel system called ACE whose main goal is to enable more complex smart contracts on permissionless blockchains. ACE is based on an off-chain execution model where the contract issuers appoint a set of service providers to execute the contract code independent from the consensus layer. The primary advantage of ACE over previous solutions is that it allows one contract to safely call another contract that is executed by a different set of service providers. Thus, ACE is the first solution to enable off-chain execution of interactive smart contracts with flexible trust assumptions. Our evaluation shows that ACE enables several orders of magnitude more complex smart contracts than standard Ethereum.

Succinct non-interactive arguments (SNARGs) are highly efficient certificates of membership in non-deterministic languages. Constructions of SNARGs in the random oracle model are widely believed to be post-quantum secure, provided the oracle is instantiated with a suitable post-quantum hash function. No formal evidence, however, supports this belief.

In this work we provide the first such evidence by proving that the SNARG construction of Micali is unconditionally secure in the *quantum* random oracle model. We also prove that, analogously to the classical case, the SNARG inherits the zero knowledge and proof of knowledge properties of the PCP underlying the Micali construction. We thus obtain the first zero knowledge SNARG of knowledge (zkSNARK) that is secure in the quantum random oracle model.

Our main tool is a new lifting lemma that shows how, for a rich class of oracle games, we can *generically* deduce security against quantum attackers by bounding a natural classical property of these games. This means that in order to prove our theorem we only need to establish *classical* properties about the Micali construction. This approach not only lets us prove post-quantum security but also enables us to prove explicit bounds that are tight up to small factors.

We additionally use our techniques to prove that SNARGs based on interactive oracle proofs (IOPs) with round-by-round soundness are unconditionally secure in the quantum random oracle model. This result establishes the post-quantum security of many SNARGs of practical interest.

In this short report we present the shortest linear program for AES MixColumn circuit with 94 XOR gates.

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.