International Association
for Cryptologic Research

Event date: 22 March to 26 March 2020
Submission deadline: 1 September 2019
Notification: 1 November 2019

Event date: 22 March to 26 March 2020
Submission deadline: 1 June 2019
Notification: 1 August 2019

Event date: 22 March to 26 March 2020

In this work, we examine the efficiency of protocols for secure evaluation of basic mathematical functions ($\mathtt{sqrt}, \mathtt{sin}, \mathtt{arcsin}$, amongst others), essential to various application domains. e.g., Artificial Intelligence. Furthermore, we have incorporated our code in state-of-the-art Multiparty Computation (MPC) software, so we can focus on the algorithms to be used as opposed to the underlying MPC system. We make use of practical approaches that, although, some of them, theoretically can be regarded as less efficient, can, nonetheless, be implemented in such software libraries without further adaptation. We focus on basic scientific operations, and introduce a series of data-oblivious protocols based on fixed point representation techniques. Our protocols do not reveal intermediate values and do not need special adaptations from the underlying MPC protocols. We include extensive computational experimentation under various settings and MPC protocols.

At ASIACRYPT 2018, Castryck, Lange, Martindale, Panny and Renes proposed CSIDH, which is a key-exchange protocol based on isogenies between elliptic curves, and a candidate for post-quantum cryptography. However, the implementation by Castryck et al. is not constant-time. Specifically, a part of the secret key could be recovered by the side-channel Attacks. Recently, Meyer, Campos and Reith proposed a constant-time implementation of CSIDH by introducing dummy isogenies and taking secret exponents only from intervals of non-negative integers. Their non-negative intervals make the calculation cost of their implementation of CSIDH twice that of the worst case of the standard (variable-time) implementation of CSIDH. In this paper, we propose a more efficient constant-time algorithm that takes secret exponents from intervals symmetric with respect to the zero. For using these intervals, we need to keep two torsion points in an elliptic curve and calculation for these points. We evaluate the costs of our implementation and that of Meyer et al. in terms of the number of operations on a finite prime field. Our evaluation shows that our constant-time implementation of CSIDH reduces the calculation cost by 28.23% compared with the implementation by Mayer et al. We also implemented our algorithm by extending the implementation in C of Meyer et al. (originally from Castryck et al.). Then our implementation achieved 172.4 million clock cycles, which is about 27.35% faster than that of Meyer et al. and confirms the above reduction ratio in our cost evaluation.

Blockchain based systems, in particular cryptocurrencies, face a serious limitation: scalability. This holds, especially, in terms of number of transactions per second. Several alternatives are currently being pursued by both the research and practitioner communities. One venue for exploration is on protocols that do not constantly add transactions on the blockchain and therefore do not consume the blockchain's resources. This is done using off-chain transactions, i.e., protocols that minimize the interaction with the blockchain, also commonly known as Layer-2 approaches. This work relates several existing off-chain channel methods, also known as payment and state channels, channel network constructions methods, and other components as channel and network management protocols, e.g., routing nodes. All these components are crucial to keep the usability of the channel, and are often overlooked. For the best of our knowledge, this work is the first to propose a taxonomy for all the components of the Layer-2. We provide an extensive coverage on the state-of-art protocols available. We also outline their respective approaches, and discuss their advantages and disadvantages.

Currently, the Simple Password-Based Encrypted Key Exchange (SPAKE2) protocol of Abdalla and Pointcheval (CT-RSA 2005) is being considered by the IETF for standardization and integration in TLS 1.3. Although it has been proven secure in the Find-then-Guess model of Bellare, Pointcheval and Rogaway (EUROCRYPT 2000), whether it satisfies some notion of forward secrecy remains an open question.

In this work, we prove that the SPAKE2 protocol satisfies the so-called weak forward secrecy introduced by Krawczyk (CRYPTO 2005). Furthermore, we demonstrate that the incorporation of key-confirmation codes in SPAKE2 results in a protocol that provably satisfies the stronger notion of perfect forward secrecy. As forward secrecy is an explicit requirement for cipher suites supported in the TLS handshake, we believe this work could fill the gap in the literature and facilitate the adoption of SPAKE2 in the recently approved TLS 1.3.

Homomorphic encryption (HE)---the ability to perform computation on encrypted data---is an attractive remedy to increasing concerns about data privacy in deep learning (DL). However, building DL models that operate on ciphertext is currently labor-intensive and requires simultaneous expertise in DL, cryptography, and software engineering. DL frameworks and recent advances in graph compilers have greatly accelerated the training and deployment of DL models to various computing platforms. We introduce nGraph-HE, an extension of nGraph, Intel's DL graph compiler, which enables deployment of trained models with popular frameworks such as TensorFlow while simply treating HE as another hardware target. Our graph-compiler approach enables HE-aware optimizations-- implemented at compile-time, such as constant folding and HE-SIMD packing, and at run-time, such as special value plaintext bypass. Furthermore, nGraph-HE integrates with DL frameworks such as TensorFlow, enabling data scientists to benchmark DL models with minimal overhead.

The effort in reducing the area of AES implementations has largely been focused on Application-Specific Integrated Circuits (ASICs) in which a tower field construction leads to a small design of the AES S-box. In contrast, a naive implementation of the AES S-box has been the status-quo on Field-Programmable Gate Arrays (FPGAs). A similar discrepancy holds for masking schemes - a well-known side-channel analysis countermeasure - which are commonly optimized to achieve minimal area in ASICs. In this paper we demonstrate a representation of the AES S-box exploiting rotational symmetry which leads to a 50% reduction of the area footprint on FPGA devices. We present new AES implementations which improve on the state of the art and explore various trade-offs between area and latency. For instance, at the cost of increasing 4.5 times the latency, one of our design variants requires 25% less look-up tables (LUTs) than the smallest known AES on Xilinx FPGAs by Sasdrich and Güneysu at ASAP 2016. We further explore the protection of such implementations against side-channel attacks. We introduce a generic methodology for masking any n-bit Boolean functions of degree t with protection order d. The methodology is exact for first-order and heuristic for higher orders. Its application to our new construction of the AES S-box allows us to improve previous results and introduce the smallest first-order masked AES implementation on Xilinx FPGAs, to-date.

A universal circuit (UC) can be programmed to simulate any circuit up to a given size n by specifying its program inputs. It provides elegant solutions in various application scenarios, e.g., for private function evaluation (PFE) and for improving the flexibility of attribute-based encryption (ABE) schemes. The asymptotic lower bound for the size of a UC is $\Omega(n \log n)$ and Valiant (STOC'76) provided two theoretical constructions, the so-called 2-way and 4-way UCs (i.e., recursive constructions with 2 and 4 substructures), with asymptotic sizes $5n \log_2n$ and $4.75n \log_2n$, respectively.

In this article, we present and extend our results published in (Kiss and Schneider, EUROCRYPT'16) and (Günther et al., ASIACRYPT'17). We validate the practicality of Valiant's UCs, by realizing the 2-way and 4-way UCs in our modular open-source implementations. We also provide an example implementation for PFE using these size-optimized UCs. We propose a 2/4-hybrid approach that combines the 2-way with the 4-way UC in order to minimize the size of the resulting UC. We realize that the bottleneck in universal circuit generation and programming becomes the memory consumption of the program since the whole structure of size $\mathcal{O}(n \log n)$ is handled by the algorithms in memory.

In this work, we overcome this by designing novel scalable algorithms for the UC generation and programming. We show that the generation, which involves topological ordering of the UC as well, can be designed to be performed block by block from top to bottom, while the programming can be performed subcircuit by subcircuit. Both algorithms use only $\mathcal{O}(n)$ memory at any point in time. We prove the practicality of our scalable design with a scalable proof-of-concept implementation for generating Valiant's 4-way UC. We note that this can be extended to work with optimized building blocks analogously. Moreover, we substantially improve the size of our UCs by including and implementing the recent optimization of Zhao et al. (ePrint 2018/943) that reduces the asymptotic size of the 4-way UC to $4.5n\log_2n$. Furthermore, we include their optimization in the implementation of our 2/4-hybrid UC which yields the smallest UC construction known so far.

TLS 1.3 allows two parties to establish a shared session key from an out-of-band agreed Pre Shared Key (PSK) is used to mutually authenticate the parties, under the assumption that it is not shared with others. This allows the parties to skip the certificate verification steps, saving bandwidth, communication rounds, and latency.

We identify a security vulnerability in this TLS 1.3 path, by showing a new reflection attack that we call ``Selfie''. The Selfie attack breaks the mutual authentication. It leverages the fact that TLS does not mandate explicit authentication of the server and the client in every message.

The paper explains the root cause of this TLS 1.3 vulnerability, demonstrates the Selfie attack on the TLS implementation of OpenSSL and proposes appropriate mitigation.

The attack is surprising because it breaks some assumptions and uncovers an interesting gap in the existing TLS security proofs. We explain the gap in the model assumptions and subsequently in the security proofs. We also provide an enhanced Multi-Stage Key Exchange (MSKE) model that captures the additional required assumptions of TLS 1.3 in its current state. The resulting security claims in the case of external PSKs are accordingly different.

SM3, the Chinese standard hash algorithm inspired from SHA2, can be attacker by similar means than SHA2 up to an adaptation to its differences. But this kind of attack is based on targeting point of interest of different kinds, some are end of computation results, that are stored when others are in intermediate computational data. The leakage effectiveness of the later could be subject to implementation choices, device type or device type of leakage. In this paper, we propose a new approach that targets only the first kind of intermediate data that are more susceptible to appear. As an example, we targeted the HMAC construction using SM3, where our method allows to recover the first half of the secret information. reducing the security of the HMAC protocol.

Second-order analyses have shown a great interest to defeat first level of masking protections. Their practical realization remains tedious in a lot of cases. This is partly due to the difficulties of achieving a fine alignment of two areas that are combined together afterward. Classical protections makes therefore use of random jitter or shuffling to make the alignment difficult or even impossible. This paper extends Scatter attack to high-order analyses. Processing the jointdistribution of two selection of points, it becomes possible to retrieve the secret key even when traces are not fully aligned. The results presented in this paper are validated through practical experimentation and compared with existing window-based techniques, such as the FFT. Scatter shows the best results when misalignment is significant. This illustrates that Scatter offers an alternative to existing high-order attacks and can target all kinds of cryptography implementations, regardless they are executed in hardware or software. With the ability to exploit several leakage points, it may be valuable also when applying a second-order attack on aligned traces.

We present attacks on the cryptography formerly used in the IOTA blockchain, including under certain conditions the ability to forge signatures. We developed practical attacks on IOTA's cryptographic hash function Curl-P-27, allowing us to quickly generate short colliding messages. These collisions work even for messages of the same length. Exploiting these weaknesses in Curl-P-27, we broke the EU-CMA security of the former IOTA Signature Scheme (ISS). Finally, we show that in a chosen-message setting we could forge signatures and multi-signatures of valid spending transactions (called bundles in IOTA).

Considering AES sub-steps that can be attacked with a small guess space, the most practicable is to target SubBytes of extremal rounds. For its contrast between candidates (non-linearity) and that the search space is reduced to 28 -sized blocks. But when such point of interests are not available, MixColumns may be considered but involve search spaces of 2^32 -sized blocks. This number of attacks to run being often considered as unrealistic to reach, published papers propose to attack using chosen inputs in order to reduce back search space to 2^8 -sized blocks. Several sets of chosen inputs acquisition will then be required to succeed an attack. Our contribution consists in an optimization of usage of gained information that allows to drastically reduce the number of set needed to realize such an attack, even to only one set in some configurations.

As an append-only distributed database, blockchain is utilized in a vast variety of applications including the cryptocurrency and Internet-of-Things (IoT). The existing blockchain solutions have downsides in communication and storage efficiency, convergence to centralization, and consistency problems. In this paper, we propose LightChain, which is the first blockchain architecture that operates over a Distributed Hash Table (DHT) of participating peers. LightChain is a permissionless blockchain that provides addressable blocks and transactions within the network, which makes them efficiently accessible by all the peers. Each block and transaction is replicated within the DHT of peers and is retrieved in an on-demand manner. Hence, peers in LightChain are not required to retrieve or keep the entire blockchain. LightChain is fair as all of the participating peers have a uniform chance of being involved in the consensus regardless of their influence such as hashing power or stake. LightChain provides a deterministic fork-resolving strategy as well as a blacklisting mechanism, and it is secure against colluding adversarial peers attacking the availability and integrity of the system. We provide mathematical analysis and experimental results on scenarios involving 10K nodes to demonstrate the security and fairness of LightChain.

Coin mixing is a prevalent privacy-enhancing technology for cryptocurrency users. In this paper, we present MixEth, which is a trustless coin mixing service for Turing-complete blockchains. MixEth does not rely on a trusted setup and is more efficient than any proposed trustless coin tumbler. It requires only 3 on-chain transactions at most per user and 1 off-chain message. It achieves strong notions of anonymity and is able to resist denial-of-service attacks. Furthermore the underlying protocol can also be used to efficiently shuffle ballots, ciphertexts in a trustless and decentralized manner.

Concerning the side-channel attacks on Advanced Encryp- tion Standard, it seems that majority of studies focus on the lowest size: AES-128. Even when adaptable to higher sizes (AES-192 and AES-256), lots of state-of-the-art attacks see their complexity substantially raised. Indeed, it often requires to perform two consecutive dependent attacks. The first is similar to the one applied on AES-128, but a part of the key remains unknown and must be retrieved through a second attack directly dependent on the success of the first. This configuration may substantially raise the complexity for the at- tacker, especially if new signal acquisitions with specific input, built using the first key part recovered, must be performed. Any error/uncertainty in the first attack raise the key recovery complexity. Our contribution is to show that this complexity can be lowered to two independent attacks by the mean of attacking separately first and last round keys. We show that the information is enough to recover the main key (or a very small list of candidates) in a negligible exploratory effort.

Using a small block length is a common strategy in designing lightweight block cipher. So far, many $64$-bit primitives have been proposed. However, if we use such a $64$-bit primitive for an authenticated encryption with birthday-bound security, it has only $32$-bit plaintext complexity which is subject to a practical attack. To take advantage of a short block length without losing security, we propose a lightweight AEAD mode $\mathsf{FBAE}$ that achieves beyond-birthday-bound security. For the purpose, we extend the idea of $\mathsf{iCOFB}$, originally defined with a tweakable random function, with tweakable block cipher. More specifically, we fix the tweak length which was variable in $\mathsf{iCOFB}$, and further generalize the feedback function. Moreover, we improve its security bound. We evaluate the concrete hardware performances of $\mathsf{FBAE}$. $\mathsf{FBAE}$ benefits from the small block length and shows the particularly good performances in threshold implementation.

We show that garbled circuits are a practical choice for secure evaluation of neural network classifiers. At the protocol level, we start with the garbling scheme of Ball, Malkin & Rosulek (ACM CCS 2016) for arithmetic circuits and introduce new optimizations for modern neural network activation functions. We develop fancy-garbling, the first implementation of the BMR16 garbling scheme along with our new optimizations, as part of heavily optimized garbled-circuits tool that is driven by a TensorFlow classifier description.

We evaluate our constructions on a wide range of neural networks. We find that our approach is up to 100x more efficient than straight-forward boolean garbling (depending on the neural network). Our approach is also roughly 40% more efficient than DeepSecure (Rouhani et al., DAC 2018), the only previous garbled-circuit-based approach for secure neural network evaluation, which incorporates significant optimization techniques for boolean circuits. Furthermore, our approach is competitive with other non-garbled-circuit approaches for secure neural network evaluation.