IACR News Central

The early registration deadline for FSE 2019 is approaching soon (February 26). After that date, registration prices will increase!

You can register online at https://secure.iacr.org/conferences/fse2019/register/.

FSE 2019 will take place in Paris, France during March 25-28, 2019. For more information on the conference please visit https://fse.iacr.org/2019.

Frit is a new lightweight 384-bit cryptographic permutation proposed by Simon et al., which is designed for resisting fault injection and performs competitively in both hardware and software. Dobraunig et al. first studied Frit in EM construction, and left an open problem to explore the security of Frit in a sponge or duplex modes. In this paper, by introducing a new key-dependent cube attack method, we partially answer the open question by Dobraunig et al. and give some key-recovery attacks on the rounded-reduced Frit used in duplex authenticated encryption mode (Frit-AE). Our results cover all the versions of Frit-AE and include some practical key-recovery attacks that could recover the key within several minutes.

In this paper, we introduce updatable anonymous credential systems (UACS) and use them to construct a new privacy-preserving incentive system. In a UACS, a user holding a credential certifying some attributes can interact with the corresponding issuer to update his attributes. During this, the issuer knows which update function is run, but does not learn the user's previous attributes. Hence the update process preserves anonymity of the user. One example for a class of update functions are additive updates of integer attributes, where the issuer increments an unknown integer attribute value $v$ by some known value $k$. This kind of update is motivated by an application of UACS to incentive systems. Users in an incentive system can anonymously accumulate points, e.g. in a shop at checkout, and spend them later, e.g. for a discount.

In this paper, we (1) formally define UACS and their security, (2) give a generic construction for UACS supporting arbitrary update functions, and (3) construct a practically efficient incentive system using UACS.

Profiling side-channel attacks represent the most powerful category of side-channel attacks. There, we assume that the attacker has access to a clone device in order to profile the device. Additionally, we assume the attacker to be unbounded in power in an effort to give the worst-case security analysis. In this paper, we start from a different premise and consider an attacker in a restricted setting where he is able to profile only a limited number of measurements. To that end, we propose a new framework for profiling side-channel analysis that we call the Restricted Attacker framework. With it, we enforce the attackers to really conduct the most powerful attack possible but also we provide a setting that inherently allows a more fair analysis among attacks. Next, we discuss the ramifications of having the attacker with unbounded power when considering neural network-based attacks. There, we are able to prove that the Universal Approximation Theorem can result in neural network-based attacks being able to break implementations with only a single measurement. Those considerations further strengthen the need for the Restricted Attacker framework.

Many secure cache designs have been proposed in literature with the aim of mitigating different types of cache timing-based side-channel attacks. However, there has so far been no systematic analysis of how these secure cache designs can, or cannot, protect against different types of the timing-based attacks. To provide a means of analyzing the caches, this paper first presents a novel three-step modeling approach to exhaustively enumerate all the possible cache timing-based side-channel vulnerabilities. The model covers not only attacks that leverage cache accesses or flushes from the local processor core, but also attacks that leverage changes in the cache state due to the cache coherence protocol actions from remote cores. Moreover, both conventional attacks and speculative execution attacks are considered. With the list of all possible cache timing side-channel vulnerabilities derived from the three-step model, this work further analyzes each of the existing secure cache designs to show which types of timing-based side-channel vulnerabilities each secure cache can mitigate. Based on the security analysis of the existing secure cache designs, this paper further summaries different techniques gleaned from the secure cache designs and the technique’s ability help mitigate different types of cache timing-based side-channel vulnerabilities.

We present two new Verifiable Delay Functions (VDF) based on assumptions from elliptic curve cryptography. We discuss both the advantages and some drawbacks of our constructions, we study their security and we demonstrate their practicality with a proof-of-concept implementation.

Boldyreva et al. (Eurocrypt 2012) defined a fine-grained security model capturing ciphertext fragmentation attacks against symmetric encryption schemes. The model was extended by Albrecht et al. (CCS 2016) to include an integrity notion. The extended security model encompasses important security goals of SSH that go beyond confidentiality and integrity to include length hiding and denial-of-service resistance properties. Boldyreva et al. also defined and analysed the InterMAC scheme, while Albrecht et al. showed that InterMAC satisfies stronger security notions than all currently available SSH encryption schemes. In this work, we take the InterMAC scheme and make it fully ready for use in practice. This involves several steps. First, we modify the InterMAC scheme to support encryption of arbitrary length plaintexts and we replace the use of Encrypt-then-MAC in InterMAC with modern nonce-based authenticated encryption. Second, we describe a reference implementation of the modified InterMAC scheme in the form of the library libInterMAC. We give a performance analysis of libInterMAC. Third, to test the practical performance of libInterMAC, we implement several InterMAC-based encryption schemes in OpenSSH and carry out a performance analysis for the use-case of file transfer using SCP. We measure the data throughput and the data overhead of using InterMAC-based schemes compared to existing schemes in OpenSSH. Our analysis shows that, for some network set-ups, using InterMAC-based schemes in OpenSSH only moderately affects performance whilst providing stronger security guarantees compared to existing schemes.

Secure multiparty computation (MPC) allows a set of mutually distrustful parties to compute a public function on their private inputs without revealing anything beyond the output of the computation. In recent years, a large effort has undergone into designing and implementing MPC protocols that can be used in practice. This paper focuses on the specific case of three-party computation with an honest majority, which is among the most popular models for real-world applications of MPC. Somewhat surprisingly, despite its significant popularity, there are currently no practical solutions for evaluating arithmetic circuits over real-world CPU word sizes, like 32- and 64-bit words, that are secure against active adversaries that may arbitrarily deviate from the protocol description. Existing solutions are either only passively secure or require the computations to be performed over prime fields, which do not match real-world system architectures. This is unfortunate, since it requires application developers to redesign their applications for the models of computation that are provided by existing MPC frameworks, rather than the MPC frameworks matching the needs of the developers.

In this paper we present the first fully-fledged implementation of an MPC framework that can evaluate arithmetic circuits with arbitrary word sizes. Our framework is based on a new protocol, which improves the communication overhead of the best known previous solutions by a factor of two. We provide extensive benchmarks of our framework in a LAN and in different WAN settings, showing that the online overhead for achieving active security is less than two, when compared to the best solutions for the same setting with passive security. Concretely, for the case of 32- and 64-bit words, we show that our framework can evaluate $10^6$ multiplication gates per second.

Horizontal attacks are a suitable tool to evaluate the (nearly) worst-case side-channel security level of ECC implementations, due to the fact that they allow extracting a large amount of information from physical observations. Motivated by the difficulty of mounting such attacks and inspired by evaluation strategies for the security of symmetric cryptography implementations, we derive shortcut formulas to estimate the success rate of horizontal differential power analysis attacks against ECSM implementations, for efficient side-channel security evaluations. We then discuss the additional leakage assumptions that we exploit for this purpose, and provide experimental confirmation that the proposed tools lead to good predictions of the attacks' success.

We introduce a new variant of decentralised, trustless, permissionless proof-of-work blockchain. The main novelty of the new variant is a multi-stage proof of work which is analogous to multi-stage pipelining used in hardware architectures. Among the possible advantages of using a multi-stage proof-of-work blockchain are the following.

Reduction of the time for confirmation of a transaction and speeding up the overall rate of transactions processing without reducing the time for mining a block.

Encourage cooperative behaviour among the miners so that the reward for mining a block is shared by a number of miners.

Use of hardware incompatible hash functions for various stages so that it becomes very difficult for a single entity to attain major computational advantage over all the stages of the block mining.

Improve security by making 51\% attacks more difficult to achieve and by providing resilience to selfish mining attacks.

We believe that the new blockchain structure mitigates the problem of scalability without compromising security. By enforcing cooperative behaviour among the miners, reward for mining a block is more equitably distributed. This, in turn, will help in ensuring participation by a greater number of entities in the overall mining activity.

Password-based Key Derivation Functions (KDFs) are used to generate secure keys of arbitrary length implemented in many security-related systems. The strength of these KDFs is the ability to provide countermeasures against brute-force/dictionary attacks. One of the most implemented KDF is PBKDF2. In order to slow attackers down, PBKDF2 uses a salt and introduces computational intensive operations based on an iterated pseudo-random function. Since passwords are widely used to protect personal data and to authenticate users to access specific resources, if an application uses a small iteration count value, the strength of PBKDF2 against attacks performed on low-cost commodity hardware may be reduced. In this paper we introduce the cryptographic algorithms involved in the key derivation process, describing the optimization techniques used to speed up PBKDF2-HMAC-SHA1 in a GPU/CPU context. Finally, a testing activities has been executed on consumer-grade hardware and experimental results are reported.

Homomorphic encryption is a tool that enables computation on encrypted data and thus has applications in privacy-preserving cloud computing. Though conceptually amazing, implementation of homomorphic encryption is very challenging and typically software implementations on general purpose computers are extremely slow. In this paper we present our year long effort to design a domain specific architecture in a heterogeneous Arm+FPGA platform to accelerate homomorphic computing on encrypted data. We design a custom co-processor for the computationally expensive operations of the well-known Fan-Vercauteren (FV) homomorphic encryption scheme on the FPGA, and make the Arm processor a server for executing different homomorphic applications in the cloud, using this FPGA-based co-processor. We use the most recent arithmetic and algorithmic optimization techniques and perform designspace exploration on different levels of the implementation hierarchy. In particular we apply circuit-level and block-level pipeline strategies to boost the clock frequency and increase the throughput respectively. To reduce computation latency, we use parallel processing at all levels. Starting from the highly optimized building blocks, we gradually build our multi-core multi-processor architecture for computing. We implemented and tested our optimized domain specific programmable architecture on a single Xilinx Zynq UltraScale+ MPSoC ZCU102 Evaluation Kit. At 200 MHz FPGA-clock, our implementation achieves over 13x speedup with respect to a highly optimized software implementation of the FV homomorphic encryption scheme on an Intel i5 processor running at 1.8 GHz.

Two paradigms for secure MPC are synchronous and asynchronous protocols, which differ substantially in terms of the guarantees they provide. While synchronous protocols tolerate more corruptions and allow every party to give its input, they are very slow because the speed depends on the conservatively assumed worst-case delay $\Delta$ of the network. In contrast, asynchronous protocols are as fast as the actual network allows, i.e., run in time proportional to the actual maximal network delay $\delta$, but unavoidably parties with slow network connections cannot give input.

This paper proposes a new, composable model (of UC functionalities) capturing the best of both worlds. Each party obtains the output as fast as the network allows (a property called responsiveness), and it is guaranteed that all parties obtain the same output. We consider different corruption thresholds: correctness, privacy, and responsiveness are guaranteed for less than $T_C$, $T_P$, and $T_R$ corruptions, respectively, while termination is always guaranteed. We achieve a trade-off between correctness, privacy and responsiveness: For any $T_R\leq\frac{1}{3}n$, one can achieve $T_C = T_P=\min\{\frac{1}{2}n,n-2T_R\}$. In particular, setting $T_R = \frac{1}{4}n$ allows us to obtain $T_C = T_P = \frac{1}{2}n$, hence achieving substantial responsiveness, yet correctness and privacy much better than in an asynchronous protocol and as good as for a purely synchronous (slow) protocol.

This result is achieved by a black-box compiler for combining an asynchronous and a synchronous protocol, involving new protocol techniques that may have applications in other contexts, and by devising an asynchronous protocol with $T_C = T_P = n-2T_R$, improving the correctness and privacy of known protocols achieving $T_C=T_P=\frac{1}{3}n$.

We finally close the long-standing problem of constructing a noninteractive zero-knowledge (NIZK) proof system for any NP language with security based on the plain Learning With Errors (LWE) problem, and thereby on worst-case lattice problems. Our proof system instantiates the framework recently developed by Canetti et al. [EUROCRYPT'18], Holmgren and Lombardi [FOCS'18], and Canetti et al. [STOC'19] for soundly applying the Fiat--Shamir transform using a hash function family that is correlation intractable for a suitable class of relations. Previously, such hash families were based either on ``exotic'' assumptions (e.g., indistinguishability obfuscation or optimal hardness of certain LWE variants) or, more recently, on the existence of circularly secure fully homomorphic encryption (FHE). However, none of these assumptions are known to be implied by plain LWE or worst-case hardness.

Our main technical contribution is a hash family that is correlation intractable for arbitrary size-$S$ circuits, for any polynomially bounded $S$, based on plain LWE (with small polynomial approximation factors). The construction combines two novel ingredients: a correlation-intractable hash family for log-depth circuits based on LWE (or even the potentially harder Short Integer Solution problem), and a ``bootstrapping'' transform that uses (leveled) FHE to promote correlation intractability for the FHE decryption circuit to arbitrary (bounded) circuits. Our construction can be instantiated in two possible ``modes,'' yielding a NIZK that is either computationally sound and statistically zero knowledge in the common random string model, or vice-versa in the common reference string model.

In the implicit certification model, the process of verifying the validity of the signer's public key is combined with the verification of the signature itself. When compared to traditional, explicit certificates, the main advantage of the implicit approach lies in the shorter public key validation data. This property is particularly important in resource-constrained scenarios where public key validation is performed very often, which is common in vehicular communications (V2X) that employ pseudonym certificates. In this article, we propose a Schnorr-based implicit certification procedure that is more efficient than the state of the art. We then integrate the proposed solution with a popular V2X-oriented pseudonym certificate provisioning approach, the (unified) butterfly key expansion, showing the corresponding performance gains. As an additional contribution, we show that butterfly keys are vulnerable to existential forgery attacks under certain conditions, and also discuss how this issue can be fixed in an effective and efficient manner.

The importance of efficient MPC in today's world needs no retelling. An obvious barebones requirement to execute protocols for MPC is the ability of parties to communicate with each other. Traditionally, we solve this problem by assuming that every pair of parties in the network share a dedicated secure link that enables reliable message transmission. This assumption is clearly impractical as the number of nodes in the network grows, as it has today. In their seminal work, Dwork, Peleg, Pippenger and Upfal introduced the notion of almost-everywhere secure primitives in an effort to model the reality of large scale global networks and study the impact of limited connectivity on the properties of fundamental fault-tolerant distributed tasks. In this model, the underlying communication network is sparse and hence some nodes may not even be in a position to participate in the protocol (all their neighbors may be corrupt, for instance). A protocol for almost everywhere reliable message transmission, which would guarantee that a large subset of the network can transmit messages to each other reliably, implies a protocol for almost-everywhere agreement where nodes are required to agree on a value despite malicious or byzantine behavior of some subset of nodes, and an almost-everywhere agreement protocol implies a protocol almost-everywhere secure MPC that is unconditionally or information-theoretically secure. The parameters of interest are the degree $d$ of the network, the number $t$ of corrupted nodes that can be tolerated and the number $x$ of nodes that the protocol may give up. Prior work achieves $d = O(1)$ for $t = O(n/\log n)$ and $d = O(\log^{q}n)$ for $t = O(n)$ for some fixed constant $q > 1$.

In this work, we first derive message protocols which are efficient with respect to the total number of computations done across the network. We use this result to show an abundance of networks with $d = O(1)$ that are resilient to $t = O(n)$ random corruptions. This randomized result helps us build networks which are resistant to worst-case adversaries. In particular, we improve the state of the art in the almost everywhere reliable message transmission problem in the worst-case adversary model by showing the existence of an abundance of networks that satisfy $d = O(\log n)$ for $t = O(n)$, thus making progress on this question after nearly a decade. Finally, we define a new adversarial model of corruptions that is suitable for networks shared amongst a large group of corporations that: (1) do not trust each other, and (2) may collude, and construct optimal networks achieving $d = O(1)$ for $t = O(n)$ in this model.

Decryption failure is a common phenomenon in most lattice-based public-key schemes. To reduce the rate of decryption failure, application of error correction code can be helpful. However, the literature of error correcting codes typically addresses computational performances and error correcting capabilities of the codes; their security properties are yet to be investigated. Hence, direct porting of an error correcting code in a cryptographic scheme could open new avenues to the attacks. For example, a recent work has exploited non-constant-time execution of the BCH error correcting code to reduce the security of the lattice-based public-key scheme LAC.

In this work we analyze the decoding algorithm of the BCH code and design a constanttime version of the BCH decoding algorithm. To study the computational overhead of the countermeasures, we integrated our constant-time BCH code in the reference and optimized implementations of the LAC scheme and observed nearly 1.1 and 3.0 factor slowdown respectively for the CCA-secure primitives.

Smart contracts are envisioned to be one of the killer applications of decentralized cryptocurrencies. They enable self-enforcing payments between users depending on complex program logic. Unfortunately, Bitcoin – the largest and by far most widely used cryptocurrency – does not offer support for complex smart contracts. Moreover, simple contracts that can be executed on Bitcoin are often cumbersome to design and very costly to execute. In this work we present FastKitten, a practical framework for executing arbitrarily complex smart contracts at low costs over decentralized cryptocurrencies which are designed to only support simple transactions. To this end, FastKitten leverages the power of trusted computing environments (TEEs), in which contracts are run off-chain to enable efficient contract execution at low cost. We formally prove that FastKitten satisfies strong security properties when all but one party are malicious. Finally, we report on a prototype implementation which supports arbitrary contracts through a scripting engine, and evaluate performance through benchmarking a provably fair online poker game. Our implementation illustrates that FastKitten is practical for complex multi-round applications with a very small latency. Combining these features, FastKitten is the first truly practical framework for complex smart contract execution over Bitcoin.

Recently, Cramer et al. (CRYPTO 2018) presented a protocol, SPDZ2k, for actively secure multiparty computation for dishonest majority in the pre-processing model over the ring $Z_{2^k}$, instead of over a prime field $F_p$. Their technique used oblivious transfer for the pre-processing phase, more specifically the MASCOT protocol (Keller et al. CCS 2016). In this paper we describe a more efficient technique for secure multiparty computation over $Z_{2^k}$ based on somewhat homomorphic encryption. In particular we adapt the Overdrive approach (Keller et al. EUROCRYPT 2018) to obtain a protocol which is more like the original SPDZ protocol (Damg{\aa}rd et al. CRYPTO 2012).

To accomplish this we introduce a special packing technique for the BGV encryption scheme operating on the plaintext space defined by the SPDZ2k protocol, extending the ciphertext packing method used in SPDZ to the case of $Z_{2^k}$. We also present a more complete pre-processing phase for secure computation modulo $2^k$ by adding a new technique to produce shared random bits. These are needed in a number of online protocols and are quite expensive to generate using the MASCOT-based method given in the original SPDZ2k paper.

Our approach can be applied to both the Low-Gear and High-Gear variant of Overdrive, and it leads to a protocol whose overall efficiency is three to six times better than the OT-based methodology.

One of three tasks in a secure genome analysis competition called IDASH 2018 was to develop a solution for privacy-preserving GWAS computation based on homomorphic encryption. The scenario is that a data holder encrypts a number of individual records, each of which consists of several phenotype and genotype data, and provide the encrypted data to an untrusted server. Then, the server performs a GWAS algorithm based on homomorphic encryption without the decryption key and outputs the result in encrypted state so that there is no information leakage on the sensitive data to the server. We develop a privacy-preserving semi-parallel GWAS algorithm by applying an approximate homomorphic encryption scheme HEAAN. Fisher scoring and semi-parallel GWAS algorithms are modified to be efficiently computed over homomorphically encrypted data with several optimization methodologies; substitute matrix inversion by an adjoint matrix, avoid computing a superfluous matrix of super-large size, and transform the algorithm into an approximate version. Our modified semi-parallel GWAS algorithm based on homomorphic encryption which achieves 128-bit security takes $30$--$40$ minutes for $245$ samples containing $10,000$--$15,000$ SNPs. Compared to the true $p$-value from the original semi-parallel GWAS algorithm, the $F_1$ score of our $p$-value result is over $0.99$.

The problem of solving a system of quadratic equations in multiple variables---known as multivariate-quadratic or MQ problem---is the underlying hard problem of various cryptosystems. For efficiency reasons, a common instantiation is to consider quadratic equations over $\F_2$. The current state of the art in solving the \MQ problem over $\F_2$ for sizes commonly used in cryptosystems is enumeration, which runs in time $\Theta(2^n)$ for a system of $n$ variables. Grover's algorithm running on a large quantum computer is expected to reduce the time to $\Theta(2^{n/2})$. As a building block, Grover's algorithm requires an "oracle", which is used to evaluate the quadratic equations at a superposition of all possible inputs. In this paper, we describe two different quantum circuits that provide this oracle functionality. As a corollary, we show that even a relatively small quantum computer with as little as 92 logical qubits is sufficient to break MQ instances that have been proposed for 80-bit pre-quantum security.

This paper introduces a constant-time implementation for a quasi-cyclic moderate-density-parity-check (QC-MDPC) code based encryption scheme. At a $2^{80}$ security level, the software takes 14679937 Cortex-M4 and 1560072 Haswell cycles to decrypt a short message, while the previous records were 18416012 and 3104624 (non-constant-time) cycles. Such speed is achieved by combining two techniques: 1) performing each polynomial multiplication in $\mathbb{F}_2[x]/(x^r-1)$ and $\mathbb{Z}[x]/(x^r-1)$ using a sequence of ``constant-time rotations'' and 2) bitslicing.

Based on the identity-based encryption (IBE) from lattices by Agrawal et al. (Eurocrypt'10), Micciancio and Peikert (Eurocrypt'12) presented a CCA1-secure public-key encryption (PKE), which has the best known efficiency in the standard model and can be used to obtain a CCA2-secure PKE from lattices by using the generic BCHK transform (SIAM J. Comput., 2006) with a cost of introducing extra overheads to both computation and storage for the use of other primitives such as signatures and commitments. In this paper, we propose a more efficient standard model CCA2-secure PKE from lattices by carefully combining a different message encoding (which encodes the message into the most significant bits of the LWE's ``secret term'') with several nice algebraic properties of the tag-based lattice trapdoor and the LWE problem (such as unique witness and additive homomorphism). Compared to the best known lattice-based CCA1-secure PKE in the standard model due to Micciancio and Peikert (Eurocrypt'12), we not only directly achieve the CCA2-security without using any generic transform (and thus do not use signatures or commitments), but also reduce the noise parameter roughly by a factor of 3. This improvement makes our CCA2-secure PKE more efficient in terms of both computation and storage. In particular, when encrypting a 256-bit (resp., 512-bit) message at 128-bit (resp., 256-bit) security, the ciphertext size of our CCA2-secure PKE is even 33-44% (resp., 36-46%) smaller than that of their CCA1-secure PKE.

We investigate the minimal number of group elements and prover running time in a zk-SNARK when using only a symmetric ``linear'' knowledge assumption, like the $d$-Power Knowledge of Exponent assumption, rather than a ``quadratic'' one as implicitly happens in the most efficient known construction by Groth [Groth16]. The proofs of [Groth16] contain only 3 group elements. We present 4 element proofs for quadratic arithmetic programs/rank 1 constraint systems under the $d$-PKE with very similar prover running time to [Groth16]. Central to our construction is a simple lemma for ``batching'' knowledge checks, which allows us to save one proof element.

The KECCAK hash function is the winner of the SHA-3 competition (2008 -- 2012) and became the SHA-3 standard of NIST in 2015. In this paper, we focus on practical collision attacks against round-reduced SHA-3 and some KECCAK variants. Following the framework developed by Dinur et al. at FSE~2012 where 4-round collisions were found by combining 3-round differential trails and 1-round connectors, we extend the connectors to up to three rounds and hence achieve collision attacks for up to 6 rounds. The extension is possible thanks to the large degree of freedom of the wide internal state. By linearizing S-boxes of the first round, the problem of finding solutions of 2-round connectors is converted to that of solving a system of linear equations. When linearization is applied to the first two rounds, 3-round connectors become possible. However, due to the quick reduction in the degree of freedom caused by linearization, the connector succeeds only when the 3-round differential trails satisfy some additional conditions. We develop dedicated strategies for searching differential trails and find that such special differential trails indeed exist. To summarize, we obtain the first real collisions on six instances, including three round-reduced instances of SHA-3, namely 5-round SHAKE128, SHA3-224, and SHA3-256, and three instances of KECCAK contest, namely KECCAK[$1440,160,5,160$], KECCAK[$640,160,5,160$] and KECCAK[$1440,160,6,160$], improving the number of practically attacked rounds by two. It is remarked that the work here is still far from threatening the security of the full 24-round SHA-3 family.

Event date: 23 June to 26 June 2019
Submission deadline: 22 March 2019
Notification: 17 May 2019

Event date: 14 July to 17 July 2019
Submission deadline: 15 March 2019
Notification: 15 April 2019

Event date: 14 July to 17 July 2019
Submission deadline: 1 March 2019
Notification: 14 April 2019

Event date: 25 September to 27 September 2019
Submission deadline: 8 April 2019
Notification: 10 June 2019

Event date: 31 May to 2 June 2019
Submission deadline: 1 April 2019
Notification: 22 April 2019