International Association
for Cryptologic Research

Blocking microarchitectural (digital) side channels is one of the most pressing challenges in hardware security today. Recently, there has been a surge of effort that attempts to block these leakages by writing programs data obliviously. In this model, programs are written to avoid placing sensitive data-dependent pressure on shared resources. Despite recent efforts, however, running data oblivious programs on modern machines today is insecure and low performance. First, writing programs obliviously assumes certain instructions in today's ISAs will not leak privacy, whereas today's ISAs and hardware provide no such guarantees. Second, writing programs to avoid data-dependent behavior is inherently high performance overhead.

This paper tackles both the security and performance aspects of this problem by proposing a Data Oblivious ISA extension. On the security side, we present ISA design principles to block microarchitectural side channels, and embody these ideas in a concrete ISA capable of safely executing existing data oblivious programs. On the performance side, we design our ISA with support for efficient memory oblivious computation, and with safety features that allow modern hardware optimizations, e.g., out-of-order speculative execution, to remain enabled in the common case.

We provide a complete hardware prototype of our ideas, built on top of the RISC-V out-of-order, speculative BOOM processor, and prove that the ISA can provide the advertised security through formal analysis of an abstract BOOM-style machine. We evaluate area overhead of hardware mechanisms needed to support our prototype, and provide performance experiments showing how the ISA speeds up a variety of existing data oblivious codes (including "constant time" cryptography and memory oblivious data structures), in addition to improving their security and portability.

In this paper we study cryptanalysis with non-linear polynomials cf. Eurocrypt’95 (adapted to Feistel ciphers at Crypto 2004). Previously researchers had serious difficulties in making such attacks work. Even though this is less general than a general space partitioning attack (FSE’97), a polynomial algebraic approach has enormous advantages. Properties are more intelligible and algebraic computational methods can be applied in order to discover or construct the suitable properties. In this paper we show how round invariants can be found for more or less any block cipher, by solving a certain surprisingly simple single algebraic equation (or two). Then if our equation has solutions, which is far from being obvious, it will guarantee that some polynomial invariant will work for an arbitrarily large number of encryption rounds. This paper is a proof of concept showing that it IS possible, for at least one specific quite complex real-life cipher to construct in a systematic way, a non-linear component and a variety of non-linear polynomial invariants holding with probability 1 for any number of rounds and any key/IV. Thus we are able to weaken a block cipher in a permanent and pervasive way. An example of a layered attack with two stages is also shown. Moreover we show that sometimes our equation reduces to zero, and this leads to yet stronger invariants, which work for any Boolean function including the original historical one used in 1970-1990.

Recently the CAESAR competition has announced several finalists among the submitted authenticated encryption algorithms, after an open selection process during the last 5 years. Applications using these algorithms are rapidly increasing today. Devices implementing these applications are enormously susceptible to physical attacks, which are able to retrieve secret data through side-channel information such as the power consumption or the electromagnetic radiations. In this work we present a Side-Channel Analysis resistant hardware implementation of the whole family of authenticated encryption schemes KETJE. By changing just one parameter, any of the KETJE designs can be obtained, and tailored for different applications, either lightweight or high throughput. We introduce a new protected KECCAK implementation, as well as unprotected and protected KETJE implementations, which allow both encryption and decryption modes in the same module. In order to secure these implementations we make use of the masking scheme known as Threshold Implementations and complement it with the technique of “Changing of the Guards”, achieving a first-order Side-Channel Analysis protected implementation with zero extra randomness needed. This way, no dedicated PRNG needs to be additionally implemented, avoiding issues such as the security of the PRNG itself or the quality of the randomness.

This paper presents a lightweight, sponge-based authenticated encryption (AE) family called Beetle. When instantiated with the PHOTON permutation from CRYPTO 2011, Beetle achieves the smallest footprint - consuming only a few more than 600 LUTs on FPGA while maintaining 64-bit security. This figure is significantly smaller than all known lightweight AE candidates which consume more than 1,000 LUTs, including the latest COFB-AES from CHES~2017. In order to realize such small hardware implementation, we equip Beetle with an ``extremely tight'' bound of security. The trick is to use combined feedback to create a difference between the cipher text block and the rate part of the next feedback (in traditional sponge these two values are the same). Then we are able to show that Beetle is provably secure up to $\min \{c-\log r, {b/2}, r\}$ bits, where $b$ is the permutation size and $r$ and $c$ are parameters called rate and capacity, respectively. The tight security bound allows us to select the smallest security parameters, which in turn result in the smallest footprint.

SUM-ECBC (Yasuda, CT-RSA 2010) is the first beyond birthday bound (BBB) secure block cipher based deterministic MAC. After this work, some more BBB secure deterministic MACs have been proposed, namely PMAC_Plus (Yasuda, CRYPTO 2011), 3kf9 (Zhang et al., ASIACRYPT 2012) and LightMAC_Plus (Naito, ASIACRYPT 2017). In this paper, we have abstracted out the inherent design principle of all these BBB secure MACs and present a generic design paradigm to construct a BBB secure pseudo random function, namely Double-block Hash-then-Sum or in short (DbHtS). A DbHtS construction, as the name implies, computes a double block hash on the message and then sum the encrypted output of the two hash blocks. Our result renders that if the underlying hash function meets certain security requirements (namely cover-free and block-wise universal advantage is low), DbHtS construction provides $2n/3$-bit security. We demonstrate the applicability of our result by instantiating all the existing beyond birthday secure deterministic MACs (e.g., SUM-ECBC, PMAC_Plus, 3kf9, LightMAC_Plus) as well as a simple two-keyed variant for each of them and some algebraic hash based constructions.

Decentralized blockchains offer attractive advantages over traditional payments such as the ability to operate without a trusted authority and increased user privacy. However, the verification of blockchain payments requires the user to download and process the entire chain which can be infeasible for resource-constrained devices, such as mobile phones. To address such concerns, most major blockchain systems support lightweight clients that outsource most of the computational and storage burden to full blockchain nodes. However, such payment verification methods leak considerable information about the underlying clients, thus defeating user privacy that is considered one of the main goals of decentralized cryptocurrencies.

In this paper, we propose a new approach to protect the privacy of lightweight clients in blockchain systems like Bitcoin. Our main idea is to leverage commonly available trusted execution capabilities, such as SGX enclaves. We design and implement a system called BITEwhere enclaves on full nodes serve privacy-preserving requests from lightweight clients. As we will show, naive serving of client requests from within SGX enclaves still leaks user information. BITE therefore integrates several privacy preservation measures that address external leakage as well as SGX side-channels.

We show that the resulting solution provides strong privacy protection and at the same time improves the performance of current lightweight clients.

Event date: 18 September to 20 September 2018

Event date: 8 December 2018
Submission deadline: 8 October 2018
Notification: 1 November 2018

The significant advancements in the field of homomorphic encryption have led to a grown interest in securely outsourcing data and computation for privacy critical applications. In this paper, we focus on the problem of performing secure predictive analysis, such as principal component analysis (PCA) and linear regression, through exact arithmetic over encrypted data. We improve the plaintext structure of Lu et al.'s protocols (from NDSS 2017), by switching over from linear array arrangement to a two-dimensional hypercube. This enables us to utilize the SIMD (Single Instruction Multiple Data) operations to a larger extent, which results in improving the space and time complexity by a factor of matrix dimension. We implement both Lu et al.'s method and ours for PCA and linear regression over HElib, a software library that implements the Brakerski-Gentry-Vaikuntanathan (BGV) homomorphic encryption scheme. In particular, we show how to choose optimal parameters of the BGV scheme for both methods. For example, our experiments show that our method takes 45 seconds to train a linear regression model over a dataset with 32k records and 6 numerical attributes, while Lu et al.'s method takes 206 seconds.

The consensus protocol underlying Bitcoin (the blockchain) works remarkably well in practice. However proving its security in a formal setting has been an elusive goal. A recent analytical result by Pass, Seeman and shelat indicates that an idealized blockchain is indeed secure against attacks in an asynchronous network where messages are maliciously delayed by at most $\Delta\ll1/np$, with $n$ being the number of miners and $p$ the mining hardness. This paper improves upon the result by showing that if appropriate inconsistency tolerance is allowed the blockchain can withstand even more powerful external attacks in the honest miner setting. Specifically we prove that the blockchain is secure against long delay attacks with $\Delta\geq1/np$ in an asynchronous network.

In this paper, we present an alternative method to choose ordinary cube variables for Keccak-MAC. Firstly, we choose some good candidates for ordinary cube variables with key-independent conditions. Then, we construct inequalities of these candidates by considering their relations after one round. In this way, we can greatly reduce the number of inequalities and therefore can solve them without a solver. Moreover, based on our method, the property of the constructed inequalities can be considered, while it is not clear by using a solver in previous work. As a straight result, we can prove why only 30 ordinary cube variables without key-dependent bit conditions can be found by a solver in Ling Song et al's work. Besides, we can find more than 63 ordinary cube variables without key-dependent bit conditions for Keccak-MAC-384 as well. Based on our new way to recover the 128-bit key, the key-recovery attack on 7-round Keccak-MAC-128/256/384 is improved to $2^{71}$.

We discuss how to recover a secret bitstring given partial information obtained during a computation over that string, assuming the computation is a deterministic algorithm processing the secret bits sequentially. That abstract situation models certain types of side-channel attacks against discrete logarithm and RSA-based cryptosystems, where the adversary obtains information not on the secret exponent directly, but instead on the group or ring element that varies at each step of the exponentiation algorithm.

Our main result shows that for a leakage of a single bit per iteration, under suitable statistical independence assumptions, one can recover the whole secret bitstring in polynomial time. We also discuss how to cope with imperfect leakage, extend the model to $k$-bit leaks, and show how our algorithm yields attacks on popular cryptosystems such as (EC)DSA.

In this paper, we generalize and bridge Shor's groundbreaking works on computing orders and general discrete logarithms, our earlier works on computing short discrete logarithms with tradeoffs and Seifert's work on computing orders with tradeoffs.

In particular, we demonstrate how the idea of enabling tradeoffs may be extended to the case of computing general discrete logarithms.

This yields a reduction by up to a factor of two in the number of group operations that need to be computed in each run of the quantum algorithm at the expense of having to run the algorithm multiple times.

Combined with our earlier works this implies that the number of group operations that need to be computed in each run of the quantum algorithm equals the number of bits in the logarithm times a small constant factor that depends on the tradeoff factor.

We comprehensively analyze the probability distribution induced by our quantum algorithm, describe how the algorithm may be simulated, and estimate the number of runs required to compute logarithms with a given minimum success probability for different tradeoff factors.

Our algorithm does not require the group order to be known. If the order is unknown, it may be computed at no additional quantum cost from the same set of outputs as is used to compute the logarithm.

In the present paper we introduce some sufficient conditions and a procedure for checking whether, for a given function, CCZ-equivalence is more general than EA-equivalence together with taking inverses of permutations. It is known from Budaghyan, Carlet and Pott (2006) and Budaghyan, Carlet and Leander (2009) that for quadratic APN functions (both monomial and polynomial cases) CCZ-equivalence is more general. We prove hereby that for non-quadratic APN functions CCZ-equivalence can be more general (by studying the only known APN function which is CCZ-inequivalent to both power functions and quadratics). On the contrary, we prove that for pawer no-Gold APN functions, CCZ equivalence coincides with EA-equivalence and inverse transformation for $n\le 8$. We conjecture that this is true for any $n$.

We provide a new approach to the elliptic curve discrete logarithm problem (ECDLP). First, we construct Elliptic Codes (EC codes) from the ECDLP. Then we propose an algorithm of finding the minimum weight codewords for algebraic geometry codes, especially for the elliptic code, via list decoding. Finally, with the minimum weight codewords, we show how to solve ECDLP. This work may provide a potential approach to speeding up the computation of ECDLP

Can Bob give Alice his decryption secret and be convinced that she will not give it to someone else? This is achieved by a proxy re-encryption scheme where Alice does not have Bob’s secret but instead she can transform ciphertexts in order to decrypt them with her own key. In this article, we answer this question in a different perspective, relying on a property that can be found in the well-known modified NTRU encryption scheme. We show how parties can collaborate to one-way-glue their secret-keys together, giving Alice’s secret-key the additional ability to decrypt Bob’s ciphertexts. The main advantage is that the proto cols we propose can be plugged directly to the modified NTRU scheme with no post-key-generation space or time costs, nor any modification of ciphertexts. In addition, this property translates to the NTRU-based multikey homomorphic scheme, allowing to equip a hierarchic chain of users with automatic re-encryption of messages and supporting homomorphic operations of ciphertexts. To achieve this, we propose two-party computation protocols in cyclotomic polynomial rings. We base the security in presence of various types of adversaries on the RLWE and DSPR assumptions, and on two new problems in the modified NTRU ring.

This article presents universal forgery and multiple forgeries against MergeMAC that has been recently proposed to fit scenarios where bandwidth is limited and where strict time constraints apply. MergeMAC divides an input message into two parts, $m\|\tilde{m}$, and its tag is computed by $\mathcal{F}( \mathcal{P}_1(m) \oplus \mathcal{P}_2(\tilde{m}) )$, where $\mathcal{P}_1$ and $\mathcal{P}_2$ are PRFs and $\mathcal{F}$ is a public function. The tag size is 64 bits. The designers claim $64$-bit security and imply a risk of accepting beyond-birthday-bound queries.

This paper first shows that it is inevitable to limit the number of queries up to the birthday bound, because a generic universal forgery against CBC-like MAC can be adopted to MergeMAC.

Afterwards another attack is presented that works with a very few number of queries, 3 queries and $2^{58.6}$ computations of $\mathcal{F}$, by applying a preimage attack against weak $\mathcal{F}$, which breaks the claimed security.

The analysis is then generalized to a MergeMAC variant where $\mathcal{F}$ is replaced with a one-way function $\mathcal{H}$.

Finally, multiple forgeries are discussed in which the attacker's goal is to improve the ratio of the number of queries to the number of forged tags. It is shown that the attacker obtains tags of $q^2$ messages only by making $2q-1$ queries in the sense of existential forgery, and this is tight when $q^2$ messages have a particular structure. For universal forgery, tags for $3q$ arbitrary chosen messages can be obtained by making $5q$ queries.

We show how to implement the Montgomery reduction algorithm for isogeny based cryptography such that it can utilize the "unsigned multiply accumulate accumulate long" instruction present on modern ARM architectures. This results in a practical speed-up of a factor 1.34 compared to the approach used by SIKE: the supersingular isogeny based submission to the ongoing post-quantum standardization effort.

Moreover, motivated by the recent work of Costello and Hisil (ASIACRYPT 2017), which shows that there is only a moderate degradation in performance when evaluating large odd degree isogenies, we search for more general supersingular isogeny friendly moduli. Using graphics processing units to accelerate this search we find many such moduli which allow for faster implementations on embedded devices. By combining these two approaches we manage to make the modular reduction 1.5 times as fast on a 32-bit ARM platform.

Functional encryption is a modern public-key cryptographic primitive allowing an encryptor to finely control the information revealed to recipients from a given ciphertext. Abdalla, Bourse, De Caro, and Pointcheval (PKC 2015) were the first to consider functional encryption restricted to the class of linear functions, i.e. inner products. Though their schemes are only secure in the selective model, Agrawal, Libert, and Stehlé (CRYPTO 16) soon provided adaptively secure schemes for the same functionality. These constructions, which rely on standard assumptions such as the Decision Diffie-Hellman (DDH), the Learning-with-Errors (LWE), and Paillier's Decision Composite Residuosity (DCR) problems, do however suffer of various practical drawbacks. Namely, the DCR based scheme only computes inner products modulo an RSA integer which is oversized for many practical applications, while the computation of inner products modulo a prime $p$ either requires, for their (DDH) based scheme, that the inner product be contained in a sufficiently small interval for decryption to be efficient, or, as in the LWE based scheme, suffers of poor efficiency due to impractical parameters.

In this paper, we provide adaptively secure functional encryption schemes for the inner product functionality which are both efficient and allow for the evaluation of unbounded inner products modulo a prime $p$. Our constructions rely on new natural cryptographic assumptions in a cyclic group containing a subgroup where the discrete logarithm (DL) problem is easy which extend Castagnos and Laguillaumie's assumption (RSA 2015) of a DDH group with an easy DL subgroup. Instantiating our generic construction using class groups of imaginary quadratic fields gives rise to the most efficient functional encryption for inner products modulo an arbitrary large prime $p$. One of our schemes outperforms the DCR variant of Agrawal et al.'s protocols in terms of size of keys and ciphertexts by factors varying between 2 and 20 for a 112-bit security.

Double-authentication preventing signatures (DAPS) are a variant of digital signatures which have received considerable attention recently (Derler et al. EuroS&P 2018, Poettering AfricaCrypt 2018). They are unforgeable signatures in the usual sense and sign messages that are composed of an address and a payload. Their distinguishing feature is the property that signing two different payloads with respect to the same address allows to publicly extract the secret signing key from two such signatures.

DAPS are known in the factoring, the discrete logarithm and the lattice setting. The majority of the constructions are ad-hoc. Only recently, Derler et al. (EuroS&P 2018) presented the first generic construction that allows to extend any discrete logarithm based secure signatures scheme to DAPS. However, their scheme has the drawback that the number of potential addresses (the address space) used for signing is polynomially bounded (and in fact small) as the size of secret and the public keys of the resulting DAPS are linear in the address space. In this paper we overcome this limitation and present a generic construction of DAPS with constant size keys and signatures. Our techniques are not tailored to a specific algebraic setting and in particular allow us to construct the first DAPS without structured hardness assumptions, i.e., from symmetric key primitives, yielding a candidate for post-quantum secure DAPS.