International Association
for Cryptologic Research

We describe a highly optimized protocol for general-purpose secure two-party computation (2PC) in the presence of malicious adversaries. Our starting point is a protocol of Kolesnikov \etal (TCC 2015). We adapt that protocol to the online/offline setting, where two parties repeatedly evaluate the same function (on possibly different inputs each time) and perform as much of the computation as possible in an offline preprocessing phase before their inputs are known. Along the way we develop several significant simplifications and optimizations to the protocol.

We have implemented a prototype of our protocol and report on its performance. When two parties on Amazon servers in the same region use our implementation to securely evaluate the AES circuit 1024 times, the amortized cost per evaluation is \emph{5.1ms offline + 1.3ms online}. The total offline+online cost of our protocol is in fact less than the \emph{online} cost of any reported protocol with malicious security. For comparison, our protocol's closest competitor (Lindell \& Riva, CCS 2015) uses 74ms offline + 7ms online in an identical setup.

Our protocol can be further tuned to trade performance for leakage. As an example, the performance in the above scenario improves to \emph{2.4ms offline + 1.0ms online} if we allow an adversary to learn a single bit about the honest party's input with probability $2^{-20}$ (but not violate any other security property, e.g. correctness).

KLEIN is a family of lightweight block ciphers which proposed at RFIDSec 2011 by Gong et al. It has a 64-bit state and 64, 80 or 96-bit key size which introduce its version. It uses 16 same 4-bit Sboxes combined with two AES's MixColumn transformations for each round. This approach allows compact implementations of KLEIN in both low-end software and hardware. Such an innovative combination attracts the attention of cryptanalysts, and several security analyses have been published. The most successful one was represented in FSE'15 which was a truncated differential attack. They could attack up to 12, 13 and 14 rounds out of total number of 12, 16 and 20 rounds for KLEIN-64, -80 and -96, respectively. In this paper, by finding more efficient truncated differential paths and a slight improving in key recovery method we present two new truncated differential attacks on KLEIN, which recover the full secret key with better time and data complexities for the previously analyzed number of rounds. Also by using these truncated differential paths we are able to attack up to 14 and 15 rounds for KLEIN-80 and -96, respectively, which are the highest rounds ever analyzed.

Masking requires splitting sensitive variables into at least d + 1 shares to provide security against DPA attacks at order d. To this date, this minimal number has only been deployed in software implementations of cryptographic algorithms and in the linear parts of their hardware counterparts. So far there is no hardware construction that achieves this lower bound if the function is nonlinear and the underlying logic gates can glitch. In this paper, we give practical implementations of the AES using d + 1 shares aiming at first- and second-order security even in the presence of glitches. To achieve this, we follow the conditions presented by Reparaz et al. at CRYPTO 2015 to allow hardware masking schemes, like Threshold Implementations, to provide theoretical higher-order security with d + 1 shares. The decrease in number of shares has a direct impact in the area requirements: our second-order DPA resistant core is the smallest in area so far, and its S-box is 50% smaller than the current smallest Threshold Implementation of the AES S-box with similar security and attacker model. We assess the security of our masked cores by practical side-channel evaluations. The security guarantees are met with 100 million traces.

Lightweight ciphers become indispensable and inevitable in the ubiquitous smart devices. However, the security of ciphers is often subverted by various types of attacks, especially, implementation attacks such as side-channel attacks. These attacks emphasise the necessity of providing efficient countermeasures. In this paper, our contribution is threefold: First, we observe and resolve the inaccuracy in the well-known and widely used formula for estimation of the number of gate equivalents (GE) in shared implementation. Then we present the first quantitative study on the efficacy of Transparency Order (TO) of decomposed S-Boxes in thwarting a side-channel attack. Using PRINCE S-Box we observe that TO-based decomposed implementation has better DPA resistivity than the naive implementation. To benchmark the DPA resistivity of TO(decomposed S-Box) implementation we arrive at an efficient threshold implementation of PRINCE, which itself merits to be an interesting contribution.

In light of security challenges that have emerged in a world with complex networks and cloud computing, the notion of functional encryption has recently emerged. In this work, we show that in several applications of functional encryption (even those cited in the earliest works on functional encryption), the formal notion of functional encryption is actually \emph{not} sufficient to guarantee security. This is essentially because the case of a malicious authority and/or encryptor is not considered. To address this concern, we put forth the concept of \emph{verifiable functional encryption}, which captures the basic requirement of output correctness: even if the ciphertext is maliciously generated (and even if the setup and key generation is malicious), the decryptor is still guaranteed a meaningful notion of correctness which we show is crucial in several applications.

We formalize the notion of verifiable function encryption and, following prior work in the area, put forth a simulation-based and an indistinguishability-based notion of security. We show that simulation-based verifiable functional encryption is unconditionally impossible even in the most basic setting where there may only be a single key and a single ciphertext. We then give general positive results for the indistinguishability setting: a general compiler from any functional encryption scheme into a verifiable functional encryption scheme with the only additional assumption being the Decision Linear Assumption over Bilinear Groups (DLIN). We also give a generic compiler in the secret-key setting for functional encryption which maintains both message privacy and function privacy. Our positive results are general and also apply to other simpler settings such as Identity-Based Encryption, Attribute-Based Encryption and Predicate Encryption. We also give an application of verifiable functional encryption to the recently introduced primitive of functional commitments.

Finally, in the context of indistinguishability obfuscation, there is a fundamental question of whether the correct program was obfuscated. In particular, the recipient of the obfuscated program needs a guarantee that the program indeed does what it was intended to do. This question turns out to be closely related to verifiable functional encryption. We initiate the study of verifiable obfuscation with a formal definition and construction of verifiable indistinguishability obfuscation.

This paper presents a security bound in the standard security model for the Magma cipher CTR encryption mode and the «CryptoPro Key Meshing» (CPKM) re-keying method that was previously used with the GOST 28147-89 cipher. We enumerate the main requirements that should be followed during the development of re-keying methods, then we propose a modified method and justify its advantages over CPKM. We also obtain certain results about the operational features of the Kuznyechik cipher CTR encryption mode with several re-keying methods.

Identity Theft is the fastest rising crime in the United States with about 7% of US adult population victimized annually. This frightening scope warrants a bold government intervention. Here is a detailed proposal. "Cyber Passport" addresses itself to the main threat: a breach of a merchant, bank, or government department resulting in theft of identities of millions of citizens, which for a long time live in fear of residual violations. The solution is based on two principles: (i) online transactions may require a randomized, readily replaceable, short lived code (cyber passport); (ii) the cyber passport will be comprised of a working code, and of an un-stored code which is known only to the issuing agency and to the individual recipient. When implemented these two principles will prevent a massive violation - the biggest plague today. The un-stored code cannot be stolen from any business database because it is not stored there. Hackers will still be able to steal everything but they will have to go retail, no more wholesale theft. Cyber-Passport is not a panacea, but it brings the threat down to size. The program will be optional for citizens, and voluntary for participating establishments facing the public. It will require some legislation, a non-trivial administration, and the use of modern cryptographic technology. Albeit, an organic growth implementation plan is presented herewith.

In this paper, we define the CAESAR hardware Application Programming Interface (API) for authenticated ciphers. In particular, our API is intended to meet the requirements of all algorithms submitted to the CAESAR competition. The major parts of our specification include: minimum compliance criteria, interface, communication protocol, and timing characteristics supported by the core. All of them have been defined with the goals of guaranteeing (a) compatibility among implementations of the same algorithm by different designers, and (b) fair benchmarking of authenticated ciphers in hardware.

SIMON is a lightweight block cipher designed by NSA in 2013. NSA presented the specification and the implementation efficiency, but they did not provide detailed security analysis nor the design rationale. The original SIMON has rotation constants of $(1,8,2)$, and K\"{o}lbl {\it et al}.~regarded the constants as a parameter $(a,b,c)$, and analyzed the security of SIMON block cipher variants against differential and linear attacks for all the choices of $(a,b,c)$. This paper complements the result of K\"{o}lbl {\it et al}.~by considering integral and impossible differential attacks. First, we search the number of rounds of integral distinguishers by using a supercomputer. Our search algorithm follows the previous approach by Wang {\it et al}., however, we introduce a new choice of the set of plaintexts satisfying the integral property. We show that the new choice indeed extends the number of rounds for several parameters. We also search the number of rounds of impossible differential characteristics based on the miss-in-the-middle approach. Finally, we make a comparison of all parameters from our results and the observations by K\"{o}lbl {\it et al}. Interesting observations are obtained, for instance we find that the optimal parameters with respect to the resistance against differential attacks are not stronger than the original parameter with respect to integral and impossible differential attacks. We also obtain a parameter that is better than the original parameter with respect to security against these four attacks.

We exemplify and evaluate the use of the equational framework of Micciancio and Tessaro (ITCS 2013) by analyzeing a number of concrete Oblivious Transfer protocols: a classic OT transformation to increase the message size, and the recent (so called ``simplest'') OT protocol in the random oracle model of Chou and Orlandi (Latincrypt 2015), together with some simple variants. Our analysis uncovers subtle timing bugs or shortcomings in both protocols, or the OT definition typically employed when using them. In the case of the OT length extension transformation, we show that the protocol can be formally proved secure using a revised OT definition and a simple protocol modification. In the case of the ``simplest'' OT protocol, we show that it cannot be proved secure according to either the original or revised OT definition, in the sense that for any candidate simulator (expressible in the equational framework) there is an environment that distinguishes the real from the ideal system.

This work exploits internal differentials within a cipher in the context of Differential Fault Analysis (DFA). This in turn overcomes the nonce barrier which acts as a natural counter-measure against DFA. We introduce the concept of internal differential fault analysis which requires only one faulty ciphertext. In particular, the analysis is applicable to parallelizable ciphers that use the counter-mode. As a proof of concept we develop an internal differential fault attack called EnCounter on PAEQ which is an AES based parallelizable authenticated cipher presently in the second round of on-going CAESAR competition. The attack is able to uniquely retrieve the key of three versions of full-round PAEQ of key-sizes 64, 80 and 128 bits with complexities of about $2^{16}$, $2^{16}$ and $2^{50}$ respectively. Finally, this work addresses in detail the instance of fault analysis with varying amounts of partial state information and also presents the first analysis of PAEQ.

Multi-input functional encryption is a paradigm that allows an authorized user to compute a certain function ---and nothing more--- over multiple plaintexts given only their encryption. The particular case of two-input functional encryption has very exciting applications like comparing the relative order of two plaintexts from their encrypted form, making range queries over an encrypted database, testing if two encrypted databases share common entries, and more.

While being extensively studied, multi-input functional encryption is not ready for a practical deployment, mainly for two reasons. First, known constructions rely on heavy cryptographic tools such as multilinear maps. Second, their security is still very uncertain, as revealed by recent devastating attacks.

This paper investigates a simpler approach. Rather than addressing multi-input functional encryption in its full generality, we target specific functions and relax the security notions. As a result, we obtain several practical realizations of multi-input encryption for specialized applications, including an efficient construction of order-revealing encryption with limited leakage, under the standard DLin assumption.

The round complexity of non-malleable commitments and non-malleable zero knowledge arguments has been an open question for long time. Very recent results of Pass [TCC 2013] and of Goyal et al. [FOCS 2014, STOC 2016], gave almost definitive answers.

In this work we show how to construct round-efficient non-malleable protocols via compilers. Starting from protocols enjoying limited non-malleability features, our compilers obtain full-fledged non-malleability without penalizing the round complexity.

By instantiating our compilers with known candidate constructions, the resulting schemes improve the current state of the art in light of subtleties that revisit the analysis of previous work. Additionally, our compilers give a non-malleable zero-knowledge argument of knowledge that features delayed-input completeness. This property is satisfied by the proof of knowledge of Lapidot and Shamir [CRYPTO 1990] and has recently been used to improve the round complexity of several cryptographic protocols.

The Cryptography and Security group of Aarhus University has an opening for a PhD student in the area of cryptographic protocols (secure two/multi party computation, zero-knowledge, advanced encryption schemes, etc.) under the supervision of Associate Professor Claudio Orlandi. The PhD position is financed by a \"Sapere Aude\" starting grant (Danish Council for Independent Research).

Applicants with (or about to complete) a master in computer science, computer engineering, or math are welcome to apply by contacting me asap.

All applications will be processed by the Graduate School of Science and Technology of Aarhus University (follow the link for more information).

The next deadlines for application are

- August 1st (start after November 1st).

- November 1st (start after February 1st).

Closing date for applications: 1 November 2016

Contact: Claudio Orlandi, orlandi AT cs au dk

More information: http://talent.au.dk/phd/scienceandtechnology/

A vast amount of data belonging to companies and individuals is currently stored \emph{in the cloud} in encrypted form by trustworthy service providers such as Microsoft, Amazon, and Google. Unfortunately, the only way for the cloud to use the data in computations is to first decrypt it, then compute on it, and finally re-encrypt it, resulting in a problematic trade-off between value/utility and security. At a high level, our goal in this paper is to present a general and practical cryptographic solution to this dilemma.

More precisely, we describe a scenario that we call \emph{Secure Data Exchange} (SDE), where several data owners are storing private encrypted data in a semi-honest non-colluding cloud, and an evaluator (a third party) wishes to engage in a secure function evaluation on the data belonging to some subset of the data owners. We require that none of the parties involved learns anything beyond what they already know and what is revealed by the function, even when the parties (except the cloud) are active malicious. We also recognize the ubiquity of scenarios where the lack of an efficient SDE protocol prevents for example business transactions, research collaborations, or mutually beneficial computations on aggregated private data from taking place, and discuss several such scenarios in detail.

Our main result is an efficient and practical protocol for enabling SDE using \emph{Secure Multi-Party Computation}~(MPC) in a novel adaptation of the server-aided setting. We also present the details of an implementation along with performance numbers.

Secure multilinear maps (mmaps) have been shown to have remarkable applications in cryptography, such as program obfuscation and multi-input functional encryption (MIFE). To date, there has been little evaluation of the performance of these applications. In this paper we initiate a systematic study of mmap-based constructions. We build a general framework, called 5Gen, to experiment with these applications. At the top layer we develop an optimizing compiler that takes in a high-level program and compiles it to an optimized matrix branching program needed for the applications we consider. Next, we optimize and experiment with several obfuscators and MIFE constructions and evaluate their performance. The 5Gen framework is modular and can easily accommodate new mmap constructions as well as new obfuscators and MIFE constructions. 5Gen is an open-source tool that can be used by other research groups to experiment with a variety of mmap-based constructions.

Rowhammer attacks have exposed a serious vulnerability in modern DRAM chips to induce bit flips in data which is stored in memory. In this paper, we develop a methodology to combine timing analysis to perform the hammering in a controlled manner to create bit flips in cryptographic keys which are stored in memory. The attack would require only user level privilege for Linux kernel versions before 4.0 and is unaware of the memory location of the key. An intelligent combination of timing Prime + Probe attack and row-buffer collision is shown to induce bit flip faults in a 1024 bit RSA key on modern processors using realistic number of hammering attempts. This demonstrates the feasibility of fault analysis of ciphers using purely software means on commercial x86 architectures, which to the best of our knowledge has not been reported earlier. The attack is also relevant for the newest Linux kernel in a Cross-VM environment where the VMs having root privilege are not denied to access the pagemap.

This work considers a theoretic problem of merging the digests of two ordered lists “homomorphically.” This theoretic problem has potential applications to efficient and verifiable data outsourcing, which is especially desirable in the public cloud computing where the cloud is not trustworthy. We consider the case of merge-sort as it is fundamental to many cloud-side operations, such as database join [6], data maintenance [3], among others. Informally, a merge-homomorphic digest enables that the digest of an ordered list, merged from two sublists, is computable from the digests of the two sublists. We present the formal definition of a merge-homomorphic digest (§ 2).

We then examine the feasibility of using Merkle hash tree or MHT [5] to construct the merge-homomorphic digest (§ 3). Our theoretic result is that we proved the impossibility of merge- homomorphism for MHT (§ 3.1) by contradiction to the definition of collision-resistant hashes.

This negative result is useful to understanding the limitations for designing a merge-homomorphic digest and might shed lights for a correct construction in the future.

Since the first demonstration of fault attacks by Boneh et al. on RSA, a multitude of fault attack techniques on various cryptosystems have been proposed. Most of these techniques, like Differential Fault Analysis, Safe Error Attack, and Collision Fault Analysis have the requirement to process two inputs that are either identical or related, in order to generate pairs of correct/faulty ciphertexts. In practice, this requirement is usually precluded by the uniqueness of the nonce used in most authenticated encryption schemes.

In this work, we present the first practical fault attacks on several nonce-based authenticated encryption modes for AES. This includes attacks on the ISO/IEC standards GCM, CCM, EAX, and OCB, as well as several second-round candidates of the ongoing CAESAR competition. All attacks are based on statistical fault attacks by Fuhr et al. that use a biased fault model and just operate on collections of faulty ciphertexts. Hereby, we put effort in reducing the assumptions made regarding the capabilities of an attacker as much as possible. In the attacks, we only assume that one is able to influence some byte (or a larger structure) of the internal AES state before the last application of MixColumns, so that the value of this byte is afterwards non-uniformly distributed.

In order to show the practical relevance of statistical fault attacks and for evaluating our assumptions on the capabilities of an attacker, we perform several fault-injection experiments targeting real hardware. For instance, laser fault injections targeting an AES co-processor of a smartcard microcontroller, which is used to implement modes like GCM or CCM, show that 4 bytes (resp. all 16 bytes) of the last round key can be revealed with a small number of faulty ciphertexts. To our knowledge this is the first work showing the practicability of statistical fault attacks.

Universally composable protocols provide security even in highly complex environments like the Internet. Without setup assumptions, however, UC-secure realizations of cryptographic tasks are impossible. To achieve efficient protocols, practical setup assumptions are needed. Tamper-proof hardware tokens, e.g. smart cards and USB tokens, can be used for this purpose. Apart from the fact that they are widely available, they are also cheap to manufacture and well understood.

However, currently considered protocols based on tamper-proof hardware require a protocol-specific functionality of the hardware which cannot be reused for other protocols. For this to become possible, in addition to a versatile functionality, the hardware has to be modeled as a global setup.

We propose the first formalization of tamper-proof hardware as an untrusted global setup assumption. Based on this setup, we construct protocols for both UC-secure two-party computation and UC-secure non-interactive secure computation. The token functionality that we choose is a simple signature functionality, i.e. our protocols can be realized with currently available signature cards.