Injective one-way trapdoor functions are one of the most fundamental cryptographic primitives. In this work we show how to derandomize lossy encryption (with long messages) to obtain lossy trapdoor functions, and hence injective one-way trapdoor functions. Bellare, Halevi, Sahai and Vadhan (CRYPTO '98) showed that if E is an IND-CPA secure cryptosystem, and $H$ is a random oracle, then $x \mapsto E(x,H(x))$ is an injective trapdoor function. In this work, we show that if E is a lossy encryption with messages at least 1-bit longer than randomness, and $h$ is a pairwise independent hash function, then $x \mapsto E(x,h(x))$ is a lossy trapdoor function, and hence also an injective trapdoor function. The works of Peikert, Vaikuntanathan and Waters and Hemenway, Libert, Ostrovsky and Vergnaud showed that statistically-hiding 2-round Oblivious Transfer (OT) is equivalent to Lossy Encryption. In their construction, if the sender randomness is shorter than the message in the OT, it will also be shorter than the message in the lossy encryption. This gives an alternate interpretation of our main result. In this language, we show that any 2-message statistically sender-private semi-honest oblivious transfer (OT) for strings longer than the sender randomness implies the existence of injective one-way trapdoor functions. This is in contrast to the black box separation of injective trapdoor functions from many common cryptographic protocols, e.g. IND-CCA encryption.

Several new services incentivize clients to compete in solving large computation tasks in exchange for financial rewards. This model of competitive distributed computation enables every user connected to the Internet to participate in a game in which he splits his computational power among a set of competing pools — the game is called a computational power splitting game. We formally model this game and show its utility in analyzing the security of pool protocols that dictate how financial rewards are shared among the members of a pool. As a case study, we analyze the Bitcoin cryptocurrency which attracts computing power roughly equivalent to billions of desk- top machines, over 70% of which is organized into public pools. We show that existing pool reward sharing protocols are insecure in our game-theoretic analysis under an attack strategy called the “block withholding attack”. This attack is a topic of debate, initially thought to be ill-incentivized in today’s pool protocols: i.e., causing a net loss to the attacker, and later argued to be always profitable. Our analysis shows that the attack is always well-incentivized in the long-run, but may not be so for a short duration. This implies that existing pool protocols are insecure, and if the attack is conducted systematically, Bitcoin pools could lose millions of dollars worth in months. The equilibrium state is a mixed strategy—that is—in equilibrium all clients are incentivized to probabilistically attack to maximize their payoffs rather than participate honestly. As a result, a part of the Bitcoin network is incentivized to waste resource competing for higher selfish reward.

We study the question of protecting arithmetic circuits against additive attacks, which can add an arbitrary fixed value to each wire in the circuit. This extends the notion of algebraic manipulation detection (AMD) codes, which protect information against additive attacks, to that of AMD circuits which protect computation. We present a construction of such AMD circuits: any arithmetic circuit $C$ over a finite field $F$ can be converted into a functionally-equivalent randomized arithmetic circuit $\widehat{C}$ of size $O(|C|)$ that is fault-tolerant in the following sense. For any additive attack on the wires of $\widehat{C}$, its effect on the output of $\widehat{C}$ can be simulated, up to $O(|C|/|F|)$ statistical distance, by an additive attack on just the input and output. Given a small tamper-proof encoder/decoder for AMD codes, the input and output can be protected as well. We also give an alternative construction, applicable to small fields (for example, to protect Boolean circuits against wire-toggling attacks). It uses a small tamper-proof decoder to ensure that, except with negligible failure probability, either the output is correct or tampering is detected. Our study of AMD circuits is motivated by simplifying and improving protocols for secure multiparty computation (MPC). Typically, securing MPC protocols against active adversaries is much more difficult than securing them against passive adversaries. We observe that in simple MPC protocols that were designed to protect circuit evaluation only against passive adversaries, the effect of any active adversary corresponds precisely to an additive attack on the original circuit's wires. Thus, to securely evaluate a circuit $C$ in the presence of active adversaries, it suffices to apply the passive-secure protocol to $\widehat{C}$. We use this methodology to simplify feasibility results and attain efficiency improvements in several standard MPC models.

Functional encryption (FE) enables fine-grained access control of encrypted data while promising simplified key management. In the past few years substantial progress has been made on functional encryption and a weaker variant called predicate encryption. Unfortunately, fundamental impossibility results have been demonstrated for constructing FE schemes for general functions satisfying a simulation-based definition of security. We show how to use \emph{hardware tokens} to overcome these impossibility results. In our envisioned scenario, an authority gives a hardware token and some cryptographic information to each authorized user; the user combines these to decrypt received ciphertexts. Our schemes rely on \emph{stateless} tokens that are \emph{identical} for all users. (Requiring a different token for each user trivializes the problem, and would be a barrier to practical deployment.) The tokens can implement relatively ``lightweight'' computation relative to the functions supported by the scheme. Our token-based approach can be extended to support hierarchal functional encryption, function privacy, and more.

The calculation of the Tate pairing on ordinary curves involves two major steps: the Miller Loop (ML) followed by the Final Exponentiation (FE). The first step for achieving a full pairing inversion would be to invert this FE, which in itself is a mathematically difficult problem. To our best knowledge, most fault attack schemes proposed against pairing algorithms have mainly focussed on the ML. They solved, if at all, the inversion of the FE in some special `easy' cases or even showed that the complexity of the FE is an intrinsic countermeasure against a successful full fault attack on the Tate pairing. In this paper, we present a fault attack on the FE whereby the inversion of the final exponentiation becomes feasible using $3$ independent faults.

A 25-gigabyte "point obfuscation" challenge "using security parameter 60" was announced at the Crypto 2015 rump session; "point obfuscation" is another name for password hashing. This paper shows that the particular matrix-multiplication hash function used in the challenge is much less secure than previous password-hashing functions are believed to be. This paper's attack algorithm broke the challenge in just 19 minutes using a cluster of 21 PCs.

Service providers collect and process more user data then ever, while users of these services remain oblivious to the actual processing and utility of the processed data to the service providers. This leads users to put less trust in service providers and be more reluctant to share data. Transparency logging is about service providers continuously logging descriptions of the data processing on their users' data, where each description is intended for a particular user. We propose Insynd, a new cryptographic scheme for privacy-preserving transparency logging. Insynd improves on prior work by (1) increasing the utility of all data sent through the scheme thanks to our publicly verifiable proofs: one can disclose selected events without having to disclose any long term secrets; and (2) enabling a stronger adversarial model: Inysnd can deal with an untrusted server (such as commodity cloud services) through the use of an authenticated data structure named Balloon. Finally, our publicly available prototype implementation shows greatly improved performance with respect to related work and competitive performance for more data-intensive settings like secure logging.

In this paper, we present universal forgery and key recovery attacks on the most popular hash-based MAC constructions, e.g., HMAC and NMAC, instantiated with an AES-like hash function Whirlpool. These attacks work with Whirlpool reduced to 6 out of 10 rounds in single-key setting. To the best of our knowledge, this is the first result on ``original'' key recovery for HMAC (previous works only succeeded in recovering the equivalent keys). Interestingly, the number of attacked rounds is comparable with that for collision and preimage attacks on Whirlpool hash function itself. Lastly, we present a distinguishing-H attack against the full HMAC- and NMAC-Whirlpool.

We present a side-channel attack based on remanence decay in volatile memory and show how it can be exploited effectively to launch a non-invasive cloning attack against SRAM PUFs --- an important class of PUFs typically proposed as lightweight security primitive with low overhead by using the existing memory of the underlying device. We validate our approach against two SRAM PUF implementations in 65~nm CMOS ASICs. We discuss countermeasures against our attack and propose the constructive use of remanence decay to improve the cloning-resistance of SRAM PUFs. Moreover, as a further contribution of independent interest, we show how to use our evaluation results to significantly improve the performance of the recently proposed TARDIS scheme, which is based on remanence decay in SRAM and used as a time-keeping mechanism for low-power clock-less devices.

Hardware and software of secured embedded systems are prone to physical attacks. In particular, fault injection attacks revealed vulnerabilities on the data and the control flow allowing an attacker to break cryptographic or secured algorithms implementations. While many research studies concentrated on successful attacks on the data flow, only a few targets the instruction flow. In this paper, we focus on electromagnetic fault injection (EMFI) on the control flow, especially on the instruction cache. We target the very widespread (smartphones, tablets, settop-boxes, health-industry monitors and sensors, etc.) ARMv7-M architecture. We describe a practical EMFI platform and present a methodology providing high control level and high reproducibility over fault injections. Indeed, we observe that a precise fault model occurs in up to 96\% of the cases. We then characterize and exhibit this practical fault model on the cache that is not yet considered in the literature. We comprehensively describe its effects and show how it can be used to reproduce well known fault attacks. Finally, we describe how it can benefits attackers to mount new powerful attacks or simplify existing ones.

Feistel structures are an extremely important and extensively researched type of cryptographic schemes. In this paper we describe improved attacks on Feistel structures with more than 4 rounds. We achieve this by a new attack that combines the main benefits of meet-in-the-middle attacks (which can reduce the time complexity by comparing only half blocks in the middle) and dissection attacks (which can reduce the memory complexity but have to guess full blocks in the middle in order to perform independent attacks above and below it). For example, for a 7-round Feistel structure on n-bit inputs with seven independent round keys of n/2 bits each), a MITM attack can use (2^1.5n ,2^1.5n) time and memory, while dissection requires (2^2n, 2^n) time and memory. Our new attack requires only (2^1.5n, 2^n) time and memory, using a few known plaintext/ciphertext pairs. When we are allowed to use more known plaintexts, we develop new techniques which rely on the existence of multicollisions and differential properties deep in the structure in order to further reduce the memory complexity. Our new attacks are not just theoretical generic constructions - in fact, we can use them to improve the best known attacks on several concrete cryptosystems such as CAST-128 (where we reduce the memory complexity from 2^111 to 2^64) and DEAL-256 (where we reduce the memory complexity from 2^200 to 2^144), without affecting their time and data complexities. An extension of our techniques applies even to some non-Feistel structures - for example, in the case of FOX, we reduce the memory complexity of all the best known attacks by a factor of 2^16.

In this paper we analyse the general class of functions underly- ing the Simon block cipher. In particular, we derive efficiently computable and easily implementable expressions for the exact differential and linear behaviour of Simon-like round functions. Following up on this, we use those expressions for a computer aided approach based on SAT/SMT solvers to find both optimal differential and linear characteristics for Simon. Furthermore, we are able to find all characteristics contributing to the probability of a differential for Simon32 and give better estimates for the probability for other variants. Finally, we investigate a large set of Simon variants using different rotation constants with respect to their resistance against differential and linear cryptanalysis. Interestingly, the default parameters seem to be not always optimal.

How does the security of the AES change when the S-box is replaced by a secret S-box, about which the adversary has no knowledge? Would it be safe to reduce the number of encryption rounds? In this paper, we demonstrate attacks based on integral cryptanalysis which allows to recover both the secret key and the secret S-box for respectively four, five, and six rounds of the AES. Despite the significantly larger amount of secret information which an adversary needs to recover, the attacks are very efficient with time/data complexities of $2^{17}/2^{16}$, $2^{38}/2^{40}$ and $2^{90}/2^{64}$, respectively. Another interesting aspect of our attack is that it works both as chosen plaintext and as chosen ciphertext attack. Surprisingly, the chosen ciphertext variant has a significantly lower time complexity in the attacks on four and five round, compared to the respective chosen plaintext attacks.

Computing discrete logarithms takes time. It takes time to develop new algorithms, choose the best algorithms, implement these algorithms correctly and efficiently, keep the system running for several months, and, finally, publish the results. In this paper, we present a highly performant architecture that can be used to compute discrete logarithms of Weierstrass curves defined over binary fields and Koblitz curves using FPGAs. We used the architecture to compute for the first time a discrete logarithm of the elliptic curve \texttt{sect113r1}, a previously standardized binary curve, using 10 Kintex-7 FPGAs. To achieve this result, we investigated different iteration functions, used a negation map, dealt with the fruitless cycle problem, built an efficient FPGA design that processes 900 million iterations per second, and we tended for several months the optimized implementations running on the FPGAs.

Choi et al. (TCC 2013) introduced the notion of multi-client verifiable computation (MVC) in which a set of clients outsource to an untrusted server the computation of a function f over their collective inputs in a sequence of time periods. In that work, the authors defined and realized multi-client verifiable computation satisfying soundness against a malicious server and privacy against the semi-honest corruption of a single client. Very recently, Goldwasser et al. (Eurocrypt 2014) provided an alternative solution relying on multi-input functional encryption. Here we conduct a systematic study of MVC, with the goal of satisfying stronger security requirements. We begin by introducing a simulation-based notion of security that provides a unified way of defining soundness and privacy, and automatically captures several attacks not addressed in previous work. We then explore the feasibility of achieving this notion of security. Assuming no collusion between the server and the clients, we demonstrate a protocol for multi-client verifiable computation that achieves strong security in several respects. When server-client collusion is possible, we show (somewhat surprisingly) that simulation-based security cannot be achieved in general, even assuming semi-honest behavior.

While some recent publications have shown some strong relations between impossible differential and zero-correlation distinguishers as well as between zero-correlation and integral distinguishers, we analyze in this paper some relation between the underlying key-recovery attacks against Type-II Feistel networks. The results of this paper are build on the relation presented at ACNS 2013. In particular, using a matrix representation of the round function, we show that we can not only find impossible, integral and multidimensional zero-correlation distinguishers but also find the key-words involved in the underlined key-recovery attacks. Based on this representation, for matrix-method-derived strongly-related zero-correlation and impossible distinguishers, we show that the key-words involved in the zero-correlation attack is a subset of the key-words involved in the impossible differential attack. Other relations between the key-words involved in zero-correlation, impossible and integral attacks are also extracted. Also we show that in this context the data complexity of the multidimensional zero-correlation attack is larger than that of the other two attacks.

It has been roughly two decades since the random oracle model for security reductions was introduced and one decade since we first discussed the controversy that had arisen concerning its use. In this retrospective we argue that there is no evidence that the need for the random oracle assumption in a proof indicates the presence of a real-world security weakness in the corresponding protocol. We give several examples of attempts to avoid random oracles that have led to protocols that have security weaknesses that were not present in the original ones whose proofs required random oracles. We also argue that the willingness to use random oracles gives one the flexibility to modify certain protocols so as to reduce dependence on potentially vulnerable pseudorandom bit generators. Finally, we discuss a modified version of ECDSA, which we call ECDSA+, that may have better real-world security than standard ECDSA, and compare it with a modified Schnorr signature. If one is willing to use the random oracle model (and the analogous generic group model), then various security reductions are known for these two schemes. If one shuns these models, then no provable security result is known for them.

In this work we have analyzed some password hashing schemes for performance under various settings of time and memory complexities. We have attempted to benchmark the said algorithms at similar levels of memory consumption. Given the wide variations in security margins of the algorithms and incompatibility of memory and time cost settings, we have attempted to be as fair as possible in choosing the various parameters while executing the benchmarks.

In 2014, Peikert presented an efficient and provably secure set of lower level primitives for practical post-quantum cryptography. These primitives also gave the first lattice-based scheme to provide perfect forward secrecy, and thus represent a major advancement in providing the same sort of security guarantees that are now expected for modern internet traffic protection. However, the presentation might have proved a bit daunting for the slightly less mathematical reader. Here we provide what we hope will be a clear and self-contained exposition of how the algorithm can be implemented, along with sample code and some initial analysis for potential parameter sizes. We focus on the simpler case, as chosen by Bos, Costello, Naehrig and Stebila in 2014, of cyclotomic rings whose degree is a power of two. We describe the necessary arithmetic setup and choices regarding error sampling, and give a possibly cleaner mechanism for reconciliation of the shared secrets. Then we present Peikert's Diffie-Hellman-like key exchange algorithms along with security, correctness and implementation analysis. We demonstrate parameter choices that outperform Bos et al by a factor of up to 13 for equivalent security.

Searchable encryption allows one to upload encrypted documents on a remote honest-but-curious server and query that data at the server itself without requiring the documents to be decrypted prior to searching. In this work, we propose a novel secure and efficient multi-keyword similarity searchable encryption (MKSim) that returns the matching data items in a ranked ordered manner. Unlike all previous schemes, our search complexity is sublinear to the total number of documents that contain the queried set of keywords. Our analysis demonstrates that proposed scheme is proved to be secure against adaptive chosen-keyword attacks. We show that our approach is highly efficient and ready to be deployed in the real-world cloud storage systems.

We present Lyra2, a password hashing scheme (PHS) based on cryptographic sponges. Lyra2 was designed to be strictly sequential (i.e., not easily parallelizable), providing strong security even against attackers that uses multiple processing cores (e.g., custom hardware or a powerful GPU). At the same time, it is very simple to implement in software and allows legitimate users to fine tune its memory and processing costs according to the desired level of security against brute force password-guessing. Lyra2 is an improvement of the recently proposed Lyra algorithm, providing an even higher security level against different attack venues and overcoming some limitations of this and other existing schemes.

We focus on generalizing constructions of Batch Single-Choice Cut-And-Choose Oblivious Transfer and Multi-sender k-out-of-n Oblivious Transfer, which are at the core of efficient secure computation constructions proposed by Lindell \textit{et al.} and the IPS compiler. Our approach consists in showing that such primitives can be based on a much weaker and simpler primitive called Verifiable Oblivious Transfer (VOT) with low overhead. As an intermediate step we construct Generalized Oblivious Transfer from VOT. Finally, we show that Verifiable Oblivious Transfer can be obtained from a structure preserving oblivious transfer protocol (SPOT) through an efficient transformation that uses Groth-Sahai proofs and structure preserving commitments.

We show that a distinguishing attack in the related key model on an Even-Mansour block cipher can readily be converted into an extremely efficient key recovery attack. Concerned ciphers include in particular all iterated Even-Mansour schemes with independent keys. We apply this observation to the Caesar candidate Prøst-OTR and are able to recover the whole key with a number of requests linear in its size. This improves on recent forgery attacks in a similar setting.

A number of databases around the world currently host a wealth of genomic data that is invaluable to researchers conducting a variety of genomic studies. However, patients who volunteer their genomic data run the risk of privacy invasion. In this work, we give a cryptographic solution to this problem: to maintain patient privacy, we propose encrypting all genomic data in the database. To allow meaningful computation on the encrypted data, we propose using a homomorphic encryption scheme. Specifically, we take basic genomic algorithms which are commonly used in genetic association studies and show how they can be made to work on encrypted genotype and phenotype data. In particular, we consider the Pearson Goodness-of-Fit test, the D' and r^2-measures of linkage disequilibrium, the Estimation Maximization (EM) algorithm for haplotyping, and the Cochran-Armitage Test for Trend. We also provide performance numbers for running these algorithms on encrypted data.

These days genomic sequence analysis provides a key way of understanding the biology of an organism. However, since these sequences contain much private information, it can be very dangerous to reveal any part of them. It is desirable to protect this sensitive information when performing sequence analysis in public. As a first step in this direction, we present a method to perform the edit distance algorithm on encrypted data to obtain an encrypted result. In our approach, the genomic data owner provides only the encrypted sequence, and the public commercial cloud can perform the sequence analysis without decryption. The result can be decrypted only by the data owner or designated representative holding the decryption key. In this paper, we describe how to calculate edit distance on encrypted data with a somewhat homomorphic encryption scheme and analyze its performance. More precisely, given two encrypted sequences of lengths n and m, we show that a somewhat homomorphic scheme of depth O((n + m) log log(n + m)) can evaluate the edit distance algorithm in O(nm log(n + m)) homomorphic computations. In the case of n = m, the depth can be brought down to O(n) using our optimization technique. Finally, we present the estimated performance of the edit distance algorithm and verify it by implementing it for short DNA sequences.

To be resistant against certain time-memory-data-tradeoff (TMDTO) attacks, a common rule of thumb says that the internal state size of a stream cipher should be at least twice the security parameter. As memory gates are usually the most area and power consuming components, this implies a sever limitation with respect to possible lightweight implementations. In this work, we revisit this rule. We argue that a simple shift in the established design paradigm, namely to involve the fixed secret key not only in the initialization process but in the keystream generation phase as well, enables stream ciphers with smaller area size for two reasons. First, it improves the resistance against the mentioned TMDTO attacks which allows to choose smaller state sizes. Second, one can make use of the fact that storing a fixed value (here: the key) requires less area size than realizing a register of the same length. We demonstrate the feasibility of this approach by describing and implementing a concrete stream cipher Sprout which uses significantly less area than comparable existing lightweight stream ciphers.

We ask whether it is possible to anonymously communicate a large amount of data using only public (non-anonymous) communication together with a small anonymous channel. We think this is a central question in the theory of anonymous communication and to the best of our knowledge this is the first formal study in this direction. To solve this problem, we introduce the concept of anonymous steganography: think of a leaker Lea who wants to leak a large document to Joe the journalist. Using anonymous steganography Lea can embed this document in innocent looking communication on some popular website (such as cat videos on YouTube or funny memes on 9GAG). Then Lea provides Joe with a short key k which, when applied to the entire website, recovers the document while hiding the identity of Lea among the large number of users of the website. Our contributions include: - Introducing and formally defining anonymous steganography, - A construction showing that anonymous steganography is possible (which uses recent results in circuits obfuscation), - A lower bound on the number of bits which are needed to bootstrap anonymous communication.

Non-malleable codes, introduced by Dziembowski, Pietrzak, and Wichs (ICS '10) provide the guarantee that if a codeword c of a message m, is modied by a tampering function f to c', then c' either decodes to m or to "something unrelated" to m. It is known that non-malleable codes cannot exist for the class of all tampering functions and hence a lot of work has focused on explicitly constructing such codes against a large and natural class of tampering functions. One such popular, but restricted, class is the so-called split-state model in which the tampering function operates on different parts of the codeword independently. In this work, we consider a stronger adversarial model called block-wise tampering model, in which we allow tampering to depend on more than one block: if a codeword consists of two blocks c = (c1; c2), then the first tampering function f1 could produce a tampered part c'1 = f1(c1) and the second tampering function f2 could produce c'2 = f2(c1; c2) depending on both c2 and c1. The notion similarly extends to multiple blocks where tampering of block ci could happen with the knowledge of all cj for j<=i. We argue this is a natural notion where, for example, the blocks are sent one by one and the adversary must send the tampered block before it gets the next block. A little thought reveals however that one cannot construct such codes that are non-malleable (in the standard sense) against such a powerful adversary: indeed, upon receiving the last block, an adversary could decode the entire codeword and then can tamper depending on the message. In light of this impossibility, we consider a natural relaxation called non-malleable codes with replacement which requires the adversary to produce not only related but also a valid codeword in order to succeed. Unfortunately, we show that even this relaxed difintion is not achievable in the information-theoretic setting (i.e., when the tampering functions can be unbounded) which implies that we must turn our attention towards computationally bounded adversaries. As our main result, we show how to construct block-wise non-malleable codes from sub-exponentially hard one-way permutations. Moreover, we provide an interesting connection between block-wise non-malleable codes and non-malleable commitments. We show that any block-wise nonmalleable code can be converted into a non-malleable (w.r.t. opening) commitment scheme. Our techniques, quite surprisingly, give rise to a non-malleable commitment scheme (secure against so-called synchronizing adversaries), in which only the committer sends messages. We believe this result to be of independent interest. In the other direction, we show that any non-interactive non-malleable (w.r.t. opening) commitment can be used to construct a block-wise non-malleable code only with 2 blocks. Unfortunately, such commitment scheme exists only under highly non-standard assumptions (adaptive one-way functions) and hence can not substitute our main construction.

A self-bilinear map is a bilinear map where the domain and target groups are identical. In this paper, we introduce a self-bilinear map with auxiliary information which is a weaker variant of a self-bilinear map, construct it based on indistinguishability obfuscation and prove that a useful hardness assumption holds with respect to our construction under the factoring assumption. From our construction, we obtain a multilinear map with interesting properties: the level of multilinearity is not bounded in the setup phase, and representations of group elements are compact, i.e., their size is independent of the level of multilinearity. This is the first construction of a multilinear map with these properties. Note, however, that to evaluate the multilinear map, auxiliary information is required. As applications of our multilinear map, we construct multiparty non-interactive key-exchange and distributed broadcast encryption schemes where the maximum number of users is not fixed in the setup phase. Besides direct applications of our self-bilinear map, we show that our technique can also be used for constructing somewhat homomorphic encryption based on indistinguishability obfuscation and the Phi-hiding assumption.

In this paper we present adaptive key recovery attacks on NTRU-based somewhat homomorphic encryption schemes. Among such schemes, we study the proposal by Bos et al [BLLN13] in 2013. Given access to a decryption oracle, the attack allows us to compute the private key for all parameter choices. Such attacks show that one must be very careful about the use of homomorphic encryption in practice. The existence of a key recovery attack means that the scheme is not CCA1-secure. Indeed, almost every somewhat homomorphic construction proposed till now in the literature is vulnerable to an attack of this type. Hence our result adds to a body of literature that shows that building CCA1-secure homomorphic schemes is not trivial.

We construct trapdoor permutations based on (sub-exponential) indistinguishability obfuscation and one-way functions, thereby providing the first candidate that is not based on the hardness of factoring. Our construction shows that even highly structured primitives, such as trapdoor permutations, can be potentially based on hardness assumptions with noisy structures such as those used in candidate constructions of indistinguishability obfuscation. It also suggest a possible way to construct trapdoor permutations that resist quantum attacks, and that their hardness may be based on problems outside the complexity class SZK - indeed, while factoring-based candidates do not possess such security, future constructions of indistinguishability obfuscation might. As a corollary, we eliminate the need to assume trapdoor permutations and injective one-way function in many recent constructions based on indistinguishability obfuscation.

We define the new notion of a multilinear pseudorandom function (PRF), and give a construction with a proof of security assuming the hardness of the decisional Diffie-Hellman problem. A direct application of our construction yields (non-multilinear) PRFs with aggregate security from the same assumption, resolving an open question of Cohen, Goldwasser, and Vaikuntanathan. Additionally, multilinear PRFs give a new way of viewing existing algebraic PRF constructions: our main theorem implies they too satisfy aggregate security.

Designers of secure hardware are required to harden their implementations against physical threats, such as power analysis attacks. In particular, cryptographic hardware circuits are required to decorrelate their current consumption from the information inferred by processing (secret) data. A common technique to achieve this goal is the use of special logic styles that aim at equalizing the current consumption at each single processing step. However, since all hiding techniques like Dual-Rail Precharge (DRP) were originally developed for ASICs, the deployment of such countermeasures on FPGA devices with fixed and predefined logic structure poses a particular challenge. In this work, we propose and practically evaluate a new DRP scheme (GliFreD) that has been exclusively designed for FPGA platforms. GliFreD overcomes the well-known early propagation issue, prevents glitches, uses an isolated dual-rail concept, and mitigates imbalanced routings. With all these features, GliFreD significantly exceeds the level of physical security achieved by any previously reported, related countermeasures for FPGAs.

We construct an identity-based encryption (IBE) scheme that is tightly secure in a very strong sense. Specifically, we consider a setting with many instances of the scheme and many encryptions per instance. In this setting, we reduce the security of our scheme to a variant of a simple assumption used for a similar purpose by Chen and Wee (Crypto 2013). The security loss of our reduction is O(k) (where k is the security parameter). Our scheme is the first IBE scheme to achieve this strong flavor of tightness under a simple assumption. Technically, our scheme is a variation of the IBE scheme by Chen and Wee. However, in order to “lift” their results to the multi-instance, multi-ciphertext case, we need to develop new ideas. In particular, while we build on (and extend) their high-level proof strategy, we deviate significantly in the low-level proof steps.

In IACR ePrint 2014/747, a method for constructing mixed-integer linear programming (MILP) models whose feasible regions are exactly the sets of all possible differential (or linear) characteristics for a wide range of block ciphers is presented. These models can be used to search for or enumerate differential and linear characteristics of a block cipher automatically. However, for the case of SIMON (a lightweight block cipher designed by the U.S. National Security Agency), the method proposed in IACR ePrint 2014/747 is not {\it exact} anymore. That is, the feasible region of the MILP model constructed for SIMON contains invalid differential characteristics due to the dependent input bits of the AND operations, and these invalid characteristics must be filtered out by other methods. This is a very inconvenient process and reduces the level of automation of the framework of MILP-based automatic differential analysis. In this paper, by using quadratic constraints or constraints from the H-representation of a specific convex hull, we give a method for constructing mixed-integer (non)linear programming models whose feasible regions are exactly the sets of all valid differential characteristics for SIMON. The technique presented in this paper may be also useful for other ciphers. How to construct an MILP model whose feasible region is exactly the set of all linear characteristics of SIMON is still an open problem.

This paper tackles the open problem whether an Oblivious RAM can be shared among multiple clients in the presence of a fully malicious server. Current ORAM constructions rely on clients knowing the ORAM state to not reveal information about their access patter. With multiple clients, a straightforward approach requires clients exchanging updated state to maintain security. However, clients on the internet usually cannot directly communicate with each other due to NAT and firewall settings. Storing state on the server is the only option, but a malicious server can arbitrarily tamper with that information. We first extend the classical square-root ORAM by Goldreich and the hierarchical one by Goldreich and Ostrovsky to add muti-client security. We accomplish this by separating the critical portions of the access, which depend on the state of the ORAM, from the non-critical parts (cache access) that can be executed securely in any state. Our second contribution is a secure multi-client variant of Path ORAM. To enable secure meta-data update during evictions in Path ORAM, we employ our first result, small multi-client secure classical ORAMs, as a building block. Depending on the block size, the communication complexity of our multi-client secure construction reaches a low $O(\log N)$ communication complexity per client, similar to state-of-the-art single-client ORAMs.

Modern FPGAs offer various new features for enhanced reconfigurability and better performance. One of such feature is a dynamically Reconfigurable LUT (RLUT) whose content can be updated internally, even during run-time. There are many scenarios like pattern matching where this feature has been shown to enhance the performance of the system. In this paper, we study RLUT in the context of secure applications. We describe the basic functionality of RLUT and discuss its potential applications for security. Next, we design several case-studies to exploit RLUT feature in security critical scenarios. The exploitation are studied from a perspective of a designer (e.g. designing countermeasures) as well as a hacker (inserting hardware Trojans).

We investigate the relationships between theoretical studies of leaking cryptographic devices and concrete security evaluations with standard side-channel attacks. Our contributions are in four parts. First, we connect the formal analysis of the masking countermeasure proposed by Duc et al. (Eurocrypt 2014) with the Eurocrypt 2009 evaluation framework for side-channel key recovery attacks. In particular, we re-state their main proof for the masking countermeasure based on a mutual information metric, which is frequently used in concrete physical security evaluations. Second, we discuss the tightness of the Eurocrypt 2014 bounds based on experimental case studies. This allows us to conjecture a simplified link between the mutual information metric and the success rate of a side-channel adversary, ignoring technical parameters and proof artifacts. Third, we introduce heuristic (yet well-motivated) tools for the evaluation of the masking countermeasure when its independent leakage assumption is not perfectly fulfilled, as it is frequently encountered in practice. Thanks to these tools, we argue that masking with non-independent leakages may provide improved security levels in certain scenarios. Eventually, we consider the tradeoff between the measurement complexity and the key enumeration time complexity in divide-and-conquer side-channel attacks, and show that these complexities can be lower bounded based on the mutual information metric, using simple and efficient algorithms. The combination of these observations enables significant reductions of the evaluation costs for certification bodies.

In this paper, we introduce and study a new cryptographic primitive that we call "puncturable key encapsulation mechanism" (PKEM), which is a special class of KEMs that satisfy some functional and security requirements that, combined together, imply chosen ciphertext security (CCA security). The purpose of introducing this primitive is to capture certain common patterns in the security proofs of the several existing CCA secure public key encryption (PKE) schemes and KEMs based on general cryptographic primitives which (explicitly or implicitly) use the ideas and techniques of the Dolev-Dwork-Naor (DDN) construction (STOC'91), and "break down" the proofs into smaller steps, so that each small step is easier to work with/verify/understand than directly tackling CCA security. To see the usefulness of PKEM, we show (1) how several existing constructions of CCA secure PKE/KEM constructed based on general cryptographic primitives can be captured as a PKEM, which enables us to understand these constructions via a unified framework, (2) its connection to detectable CCA security (Hohenberger et al. EUROCRYPT'12), and (3) a new security proof for a KEM-analogue of the DDN construction from a set of assumptions: "sender non-committing encryption" (SNCE) and non-interactive witness indistinguishable proofs. Then, as our main technical result, we show how to construct a PKEM satisfying our requirements (and thus a CCA secure KEM) from a new set of general cryptographic primitives: "SNCE" and "symmetric key encryption secure for key-dependent messages" (KDM secure SKE). Our construction realizes the "decrypt-then-re-encrypt"-style validity check of a ciphertext which is powerful but in general has a problem of the circularity between a plaintext and a randomness.We show how SNCE and KDM secure SKE can be used together to overcome the circularity. We believe that the connection among three seemingly unrelated notions of encryption primitives, i.e. CCA security, the sender non-committing property, and KDM security, to be of theoretical interest.

Hardcore lemmas are results in complexity theory which state that average-case hardness must have a very hard ``kernel'', that is a subset of instances where the given problem is extremely hard. They find important applications in hardness amplification. In this paper we revisit the following two fundamental results: \begin{enumerate}[(a)] \item The hardcore lemma for unpredictability, due to Impagliazzo (FOCS '95). It states that if a boolean function $f$ is ``moderately'' hard to predict on average, then there must be a set of noticeable size on which $f$ is ``extremely'' hard to predict. \item The hardcore lemma for indistinguishability, proved by Maurer and Tessaro (TCC'10), states that for two random variables $X$ and $Y$ which are $\epsilon$-computationally close, there are events $A$ and $B$ of probability $1-\epsilon$ such that the distributions of $X|A$ and $Y|B$ are ``computationally'' identical. \end{enumerate} Using only the standard min-max theorem and some basic facts about convex approximations in $L_p$ spaces, we provide alternative modular proofs and some generalizations of these results in the nonuniform setting, achieving best possible bounds for (a) and slightly improving the known bounds for (b). As an interesting application, we show a strengthening of the transformation between two most popular pseudoentropy variants: HILL and Metric Entropy, and apply it to show how to extract pseudorandomness from a sequence of metric-entropy sources of poor quality. In this case we significantly improve security parameters, comparing to the best known techniques.

This paper is devoted to the design of a 258-bit multiplier for computing pairings over Barreto-Naehrig (BN) curves at 128-bit security level. The proposed design is optimized for Xilinx &#64257;eld programmable gate array (FPGA). Each 258-bit integer is represented as a polynomial with &#64257;ve, 65 bit signed integer, coefficients. Exploiting this splitting we designed a pipelined 65-bit multiplier based on new Karatsuba- Ofman variant using non-standard splitting to &#64257;t to the Xilinx embedded digital signal processor (DSP) blocks. We prototype the coprocessor in two architectures pipelined and serial on a Xilinx Virtex-6 FPGA using around 17000 slices and 11 DSPs in the pipelined design and 7 DSPs in the serial. The pipelined 128-bit pairing is computed in 1. 8 ms running at 225MHz and the serial is performed in 2.2 ms running at 185MHz. To the best of our knowledge, this implementation outperforms all reported hardware designs in term of DSP use. Keywords-

Resource constraints in smart devices demand an efficient cryptosystem that allows for low power and memory consumption. This has led to popularity of comparatively efficient Elliptic curve cryptog-raphy (ECC). Prior to this paper, much of ECC is implemented on re-configurable hardware i.e. FPGAs, which are costly and unfavorable as low-cost solutions. We present comprehensive yet efficient implementations of ECC on fixed-point TMS54xx series of digital signal processors (DSP). 160-bit prime field GF(p) ECC is implemented over a wide range of coordinate choices. This paper also implements windowed recoding technique to provide better execution times. Stalls in the programming are mini-mized by utilization of loop unrolling and by avoiding data dependence. Complete scalar multiplication is achieved within 50 msec in coordinate implementations, which is further reduced till 25 msec for windowed-recoding method. These are the best known results for fixed-point low power digital signal processor to date.

We define ideal functionalities that are weaker than ideal functionalities traditionally used in realizing variable input length (VIL) random oracles (RO) in the indifferentiability or universal-Composability (UC) model. We also show realization of VIL-RO using these weaker ideal functionalities, with applications to proving Fugue and CubeHash hash functions to be VIL-RO. We argue that components of Fugue realize this weaker ideal functionality using techniques employed in proving resistance of Fugue to differential collision-attacks. This should be contrasted with other hash functions that are proven VIL-RO assuming the components are extremely ideal, e.g. random permutations.

In typical applications of homomorphic encryption, the first step consists for Alice to encrypt some plaintext m under Bob’s public key pk and to send the ciphertext c = HE_pk(m) to some third-party evaluator Charlie. This paper specifically considers that first step, i.e. the problem of transmitting c as efficiently as possible from Alice to Charlie. As previously noted, a form of compression is achieved using hybrid encryption. Given a symmetric encryption scheme E, Alice picks a random key k and sends a much smaller ciphertext c&#8242; = (HE_pk(k), E_k(m)) that Charlie decompresses homomorphically into the original c using a decryption circuit C_E^{&#8722;1}. In this paper, we revisit that paradigm in light of its concrete implementation constraints; in particular E is chosen to be an additive IV-based stream cipher. We investigate the performances offered in this context by Trivium, which belongs to the eSTREAM portfolio, and we also propose a variant with 128-bit security: Kreyvium. We show that Trivium, whose security has been firmly established for over a decade, and the new variant Kreyvium have an excellent performance.

In this paper, we introduce a new functionality for proxy re-encryption (PRE) that we call re-encryption verifiability. In a PRE scheme with re-encryption verifiability (which we simply call verifiable PRE, or VPRE), a receiver of a re-encrypted ciphertext can verify whether the received ciphertext is correctly transformed from an original ciphertext by a proxy, and thus can detect illegal activities of the proxy. We formalize the security model for a VPRE scheme, and show that the single-hop uni-directional PRE scheme by Hanaoka et al. (CT-RSA 2012) can be extended to a secure VPRE scheme.

This work extends the line of research on the hidden number problem. Motivated by studying bit security in finite fields, we define the multivariate hidden number problem. Here, the secret and the multiplier are vectors, and partial information about their dot product is given. Using tools from discrete Fourier analysis introduced by Akavia, Goldwasser and Safra, we show that if one can find the significant Fourier coefficients of some function, then one can solve the multivariate hidden number problem for that function. This allows us to generalise the work of Akavia on the hidden number problem with (non-adaptive) chosen multipliers to all finite fields. We give two further applications of our results, both of which generalise previous works to all (finite) extension fields. The first considers the general (random samples) hidden number problem in F_{p^m} and assumes an advice is given to the algorithm. The second considers a model that allows changing representations, where we show hardness of individual bits for elliptic curve and pairing based functions for elliptic curves over extension fields, as well as hardness of any bit of any component of the Diffie-Hellman secret in F_{p^m} (m>1).

In this paper we focus on designing authenticated key exchange protocols for practical scenarios where the party consists of a powerful but untrusted host (e.g., PC, mobile phone, etc) and a power-limited but trusted device (e.g., Trusted Platform Module, Mobile Trusted Module, Smart Card, etc). HMQV and (s,r)OAKE protocols are the state-of-the-art in the integrity of security and efficiency. However, we find that they are not suitable for the above scenarios as all (or part) of the online exponentiation computations must be performed in the power-limited trusted devices, which makes them inefficient for the deployment in practice. To overcome the above inefficiency, we propose a variant of HMQV protocol, denoted sHMQV, under some new design rationales which bring the following advantages: 1) eliminating the validation of the ephemeral public keys, which costs one exponentiation; 2) the power-limited trusted device only performs one exponentiation, which can be pre-computed offline; 3) all the online exponentiation computations can be performed in the powerful host. The above advantages make sHMQV enjoy better performance than HMQV and (s,r)OAKE, especially when deployed in the scenarios considered in this paper. We finally formally prove the security of sHMQV in the CK model.

Anonymous credential systems have to provide strong privacy protection. A user presenting anonymous credentials may prove his (chosen) attributes without leaking informations about his identity. In this paper we consider U-Prove -- one of the major commercial anonymous credential systems. We show that the efficient revocation mechanism designed for U-Prove enables a system provider to efficiently trace the users' activities. Namely, the Revocation Authority run the system provider may execute the U-Prove protocol in a malicious way so that: (a) the deviations from the protocol remain undetected, (b) the Revocation Authority becomes aware of each single authentication of a user in the whole system and can link them (regardless which attributes are disclosed by the user against the verifiers), (c) can link presentation tokens with the corresponding token issuing procedure (under some conditions). Thereby, the system described in the technical drafts of U-Prove does not protect privacy of a user unless one can unconditionally trust the system provider. In fact, a malicious system provider may convert the Revocation Authority into a ``Big Brother'' installation.

Dynamic Searchable Symmetric Encryption (DSSE) enables a client to perform keyword queries and update operations on the encrypted file collections. DSSE has several important applications such as privacy-preserving data outsourcing for computing clouds. In this paper, we developed a new DSSE scheme that achieves the highest privacy among all compared alternatives with low information leakage, non-interactive and efficient updates, compact client storage, low server storage for large file-keyword pairs with an easy design and implementation. Our scheme achieves these desirable properties with a very simple data structure (i.e., a bit matrix supported with two static hash tables) that enables efficient yet secure search/update operations on it. We prove that our scheme is secure (in random oracle model) and demonstrated that it is practical with large number of file-keyword pairs even with an implementation on simple hardware configurations.

The ring and polynomial learning with errors problems (Ring-LWE and Poly-LWE) have been proposed as hard problems to form the basis for cryptosystems, and various security reductions to hard lattice problems have been presented. So far these problems have been stated for general (number) rings but have only been closely examined for cyclotomic number rings. In this paper, we state and examine the Ring-LWE problem for general number rings and demonstrate provably weak instances of Ring-LWE. We construct an explicit family of number fields for which we have an efficient attack. We demonstrate the attack in both theory and practice, providing code and running times for the attack. The attack runs in time linear in q, where q is the modulus. Our attack is based on the attack on Poly-LWE which was presented in [EHL]. We extend the EHL-attack to apply to a larger class of number fields, and show how it applies to attack Ring-LWE for a heuristically large class of fields. Certain Ring-LWE instances can be transformed into Poly-LWE instances without distorting the error too much, and thus provide the first weak instances of the Ring-LWE problem. We also provide additional examples of fields which are vulnerable to our attacks on Poly-LWE, including power-of-2 cyclotomic fields, presented using the minimal polynomial of $\zeta_{2^n} \pm 1$.

Masking is a popular countermeasure against side channel attacks. Many practical works use Boolean masking because of its simplicity, ease of implementation and comparably low performance overhead. Some recent works have explored masking schemes with higher algebraic complexity and have shown that they provide more security than Boolean masking at the cost of higher overheads. In particular, masking based on the inner product was shown to be practical, albeit not efficient, for a small security parameter, and at the same time provable secure in the domain of leakage resilient cryptography for a large security parameter. In this work we explore a security versus efficiency tradeoff and provide an improved and tweaked inner product masking. Our practical security evaluation shows that it is less secure than the original inner product masking but more secure than Boolean masking. Our performance evaluation shows that our scheme is only four times slower than Boolean masking and more than two times faster than the original inner product masking. Besides the practical security analysis we prove the security of our scheme and its masked operations in the threshold probing model.

Recent results have shown the usefulness of tamper-proof hardware tokens as a setup assumption for building UC-secure two-party computation protocols, thus providing broad security guarantees and allowing the use of such protocols as buildings blocks in the modular design of complex cryptography protocols. All these works have in common that they assume the tokens to be completely isolated from their creator, but this is a strong assumption. In this work we investigate the feasibility of cryptographic protocols in the setting where the isolation of the hardware token is weakened. We consider two cases: (1) the token can relay messages to its creator, or (2) the creator can send messages to the token after it is sent to the receiver. We provide a detailed characterization for both settings, presenting both impossibilities and information-theoretically secure solutions.

In recent years, there has been great interest in Functional Encryption (FE), a generalization of traditional encryption where a token enables a user to learn a specific function of the encrypted data and nothing else. In this paper we put forward a new generalization of FE that we call Mergeable FE (mFE). In a mFE system, given a ciphertext $c_1$ encrypting $m_1$ and a ciphertext $c_2$ encrypting $m_2$, it is possible to produce in an oblivious way (i.e., given only the public-key and without knowledge of the messages, master secret-key or any other auxiliary information) a ciphertext encrypting the string $m_1||m_2$ under the security constraint that this new ciphertext does not leak more information about the original messages than what may be leaked from the new ciphertext using the tokens. For instance, suppose that the adversary is given the token for the function $f(\cdot)$ defined so that for strings $x\in\zu^n$, $f(x)=g(x)$ for some function $g:\zu^n\rightarrow\zu$ and for strings $y=(x_1||x_2)\in\zu^{2n}$, $f(x_1||x_2)=g(x_1) \vee g(x_2)$. Furthermore, suppose that the adversary gets a ciphertext $c$ encrypting $(x_1||x_2)$ that is the result of ``merging`` some ciphertexts $c_1$ and $c_2$ encrypting respectively $x_1$ and $x_2$, and suppose that the token for $f$ evaluates to $1$ on $c$. Then, the security of mFE guarantees that the adversary only learns the output $f(x_1,x_2) = g(x_1) OR g(x_2)=1$ and nothing else (e.g., the adversary should not learn whether $g(x_1)=1 or g(x_2)=1$). This primitive is in some sense FE with the ``best possible`` homomorphic properties and, besides being interesting in itself, it offers wide applications. For instance, it has as special case multi-inputs FE and thus indistinguishability obfuscation (iO) and extends the latter to support more efficiently homomorphic and re-randomizable properties. We construct mFE schemes supporting a single merging operation, one from indistinguishability obfuscation for Turing machines and one for messages of unbounded length from public-coin differing-inputs obfuscation. Finally, we discuss a construction supporting unbounded merging operations from new assumptions.

Authenticated encryption schemes guarantee both privacy and integrity, and have become the default level of encryption in modern protocols. One of the most popular authenticated encryption schemes today is AES-GCM due to its impressive speed. The current CAESAR competition is considering new modes for authenticated encryption that will improve on existing methods. One property of importance that is being considered more today -- due to multiple real-life cases of faulty sources of randomness -- is that repeating nonces and IVs can have disastrous effects on security. A (full) nonce misuse-resistant authenticated encryption scheme has the property that if the \emph{same} nonce is used to encrypt the \emph{same} message twice, then the same ciphertext is obtained and so the fact that the same message was encrypted is detected. Otherwise, \emph{full security} is obtained -- even if the same nonce is used for different messages. In this paper, we present a new fully nonce misuse-resistant authenticated encryption scheme that is based on carefully combining the GCM building blocks into the SIV paradigm of Rogaway and Shrimpton. We provide a full proof of security of our scheme, and an optimized implementation using the AES-NI and PCLMULQDQ instruction sets. We compare our performance to the highly optimized OpenSSL 1.0.2 implementation of GCM and show that our \emph{nonce misuse-resistant} scheme is only 14\% slower on Haswell architecture and 19\% slower on Broadwell architecture. On Broadwell, GCM-SIV encryption takes only {\em 0.92 cycles per byte}, and GCM-SIV decryption is exactly the same as GCM decryption taking only 0.77 cycles per byte. In addition, we compare to other optimized authenticated-encryption implementations carried out by Bogdanov et al., and conclude that our mode is very competitive. Beyond being very fast, our new mode of operation uses the same building blocks as GCM and so existing hardware and software can be utilized to easily deploy GCM-SIV. We conclude that GCM-SIV is a viable alternative to GCM, providing full nonce misuse-resistance at little cost.

At ASIACRYPT 1991, Even and Mansour introduced a block cipher construction based on a single permutation. Their construction has since been lauded for its simplicity, yet also criticized for not providing the same security as other block ciphers against generic attacks. In this paper, we prove that if a small number of plaintexts are encrypted under multiple independent keys, the Even-Mansour construction surprisingly offers similar security as an ideal block cipher with the same block and key size. Note that this multi-key setting is of high practical relevance, as real-world implementations often allow frequent rekeying. We hope that the results in this paper will further encourage the use of the Even-Mansour construction, especially when the secure and efficient implementation of a key schedule would result in a significant overhead.

Side channel attacks take advantage from the fact that the behavior of crypto implementations can be observed and provides hints that simplify revealing keys. The energy consumption of the chip that performs a cryptographic operation depends on its inputs, on the used cryptographic key and on the circuit that realizes the cryptographic algorithm. An attacker can experiment with different inputs and key candidates: he studies the influence of these parameters on the shape of measured traces with the goal to extract the key. The main assumption is here that the circuit of the attacked devices is constant. In this paper we investigated the influence of variable circuits on the shape of electromagnetic traces. We changed only a part of the cryptographic designs i.e. the partial multiplier of our ECC designs. This part calculates always the same function in a single clock cycle. The rest of the design was kept unchanged. So, we obtained designs with significantly different circuits: in our experiments the number of used FPGAs LUTs differs up to 15%. These differences in the circuits caused a big difference in the shape of electromagnetic traces even when the same data and the same key are processed. Our experiments show that the influence of different circuits on the shape of traces is comparable with the influence of different inputs. We assume that this fact can be used as a protection means against side channel attacks, especially if the cryptographic circuit can be changed before the cryptographic operation is executed or dynamically, i.e. while the cryptographic operation is processed.

Network firewalls are a standard security measure in computer networks that connect to the Internet. Often, ready-to-use firewall appliances are trusted to protect the network from malicious Internet traffic. However, because of their black-box nature, no one can be sure of their exact functionality. We address the possibility of actively compromised firewalls. That is, we consider the possibility that a network firewall might collaborate with an outside adversary to attack the network. To alleviate this threat, we suggest composing multiple firewalls from different suppliers to obtain a secure firewall architecture. We rigorously treat the composition of potentially malicious network firewalls in a formal model based on the Universal Composability framework. Our security assumption is trusted hardware. We show that a serial concatenation of firewalls is insecure even when trusted hardware ensures that no new packages are generated by the compromised firewall. Further, we show that the parallel composition of two firewalls is only secure when the order of packets is not considered. We prove that the parallel composition of three firewalls is insecure, unless a modified trusted hardware is used.

In view of the expiration or reveal of user's private credential (or private key) in a realistic scenario, identity-based encryption (IBE) schemes with an efficient key revocation mechanism, or for short, revocable identity-based encryption (RIBE) schemes, become prominently significant. In this paper, we present an RIBE scheme from lattices by combining two Agrawal et al.'s IBE schemes with the subset difference (SD) method. Our scheme is secure against adaptive identity-time attacks in the standard model under the learning with errors (LWE) assumption. In particular, our scheme serves as one solution to the challenge posed by Chen et al.(ACISP '12).

Revelations over the past couple of years highlight the importance of understanding malicious and surreptitious weakening of cryptographic systems. We provide an overview of this domain, using a number of historical examples to drive development of a weaknesses taxonomy. This allows comparing different approaches to sabotage. We categorize a broader set of potential avenues for weakening systems using this taxonomy, and discuss what future research is needed to provide sabotage-resilient cryptography.

Kuznyechik is an SPN block cipher that has been recently chosen to be standardized by the Russian federation as a new GOST cipher. The algorithm updates a 128-bit state for nine rounds using a 256-bit key. In this paper, we present a meet-in-the-middle attack on the 5-round reduced cipher. Our attack is based on the differential enumeration approach, where we propose a distinguisher for the middle rounds and match a sequence of state differences at its output. However, the application of the exact approach is not successful on Kuznyechik due to its optimal round diffusion properties. Accordingly, we adopt an equivalent representation for the last round where we can efficiently filter ciphertext pairs and launch the attack in the chosen ciphertext setting. We also utilize partial sequence matching which further reduces the memory and time complexities through relaxing the error probability. The adopted partial sequence matching approach enables successful key recovery by matching parts of the generated sequence instead of the full sequence matching used in the traditional settings of this attack. For the 5-round reduced cipher, the 256-bit master key is recovered with a time complexity of 2^{140.3}, a memory complexity of 2^{153.3}, and a data complexity of 2^{113}.

Rotational cryptanalysis is a probabilistic attack applicable to word oriented designs that use (almost) rotation-invariant constants. It is believed that the success probability of rotational cryptanalysis against ciphers and functions based on modular additions, rotations and XORs, can be computed only by counting the number of additions. We show that this simple formula is incorrect due to the invalid Markov cipher assumption used for computing the probability. More precisely, we show that chained modular additions used in ARX ciphers do not form a Markov chain with regards to rotational analysis, thus the rotational probability cannot be computed as a simple product of rotational probabilities of individual modular additions. We provide a precise value of the probability of such chains and give a new algorithm for computing the rotational probability of ARX ciphers. We use the algorithm to correct the rotational attacks on BLAKE2 and to provide valid rotational attacks against the simplified version of Skein.

This paper presents several methods for reducing the number of bit operations for multiplication of polynomials over the binary field. First, a modified Bernstein’s 3-way algorithm is introduced, followed by a new 5-way algorithm. Next, a new 3-way algorithm that improves asymptotic arithmetic complexity compared to Bernstein’s 3-way algorithm is introduced. This new algorithm uses three multiplications of one-third size polynomials over the binary field and one multiplication of one-third size polynomials over the finite field with four elements. Unlike Bernstein’s algorithm, which has a linear delay complexity with respect to input size, the delay complexity of the new algorithm is logarithmic. The number of bit operations for the multiplication of polynomials over the finite field with four elements is also computed. Finally, all these new results are combined to obtain improved complexities.

Linear and differential cryptanalysis and their generalizations are the most important tools in ststistical analysis of symmetric ciphers. These attacks make use of linear and differential properties of Sboxes and component functions of symmetric ciphers. In this article, we investigate generalized statistical properties for Sboxes. We justify the application of linear, differential and differential-linear cryptanalysis from the mathematical viewpoint. We verify some well-known Sboxes and vectotial Boolean functions by the proposed criteria and show that these functions have larger biases compared with previous criteria presentesd up to now.

Secure transmission of message was the concern of early men. Several techniques have been developed ever since to assure that the message is understandable only by the sender and the receiver while it would be meaningless to others. In this century, cryptography has gained much significance. This paper proposes a scheme to generate a Dynamic Key-dependent S-Box for the SubBytes Transformation used in Cryptographic Techniques.

We present a forgery attack on Prøst-OTR in a related-key setting. Prøst is a family of authenticated encryption algorithms proposed as candidates in the currently ongoing CAESAR competition, and Prøst-OTR is one of the three variants of the Prøst design. The attack exploits how the Prøst permutation is used in an Even-Mansour construction in the Feistel-based OTR mode of operation. Given the ciphertext and tag for any two messages under two related keys K and K + Delta with related nonces, we can forge the ciphertext and tag for a modified message under K. If we can query ciphertexts for chosen messages under K + Delta, we can achieve almost universal forgery for K. The computational complexity is negligible.

In this paper, we show structural cryptanalyses against two popular networks, i.e., the Feistel Network and the Substitute-Permutation Network (SPN). Our cryptanalyses are distinguishing attacks by an improved integral distinguisher. The integral distinguisher is one of the most powerful attacks against block ciphers, and it is usually constructed by evaluating the propagation characteristic of integral properties, e.g., the ALL or BALANCE property. However, the integral property does not derive useful distinguishers against block ciphers with non-bijective functions and bit-oriented structures. Moreover, since the integral property does not clearly exploit the algebraic degree of block ciphers, it tends not to construct useful distinguishers against block ciphers with low-degree functions. In this paper, we propose a new property called {\it the division property}, which is the generalization of the integral property. It can effectively construct the integral distinguisher even if the block cipher has non-bijective functions, bit-oriented structures, and low-degree functions. From viewpoints of the attackable number of rounds or chosen plaintexts, the division property can construct better distinguishers than previous methods. Although our attack is a generic attack, it can improve several integral distinguishers against specific cryptographic primitives. For instance, it can reduce the required number of chosen plaintexts for the 10-round distinguisher on Keccak-f from $2^{1025}$ to $2^{515}$. For the Feistel cipher, it theoretically proves that Simon 32, 48, 64, 96, and 128 have 9-, 11-, 11-, 13-, and 13-round integral distinguishers, respectively.

MAC striping has been suggested as a technique to authenticate encrypted payloads using short tags. For an idealized MAC scheme, the probability of a selective forgery has been estimated as $\binom{\ell+m}{m}^{-1}\cdot 2^{-m}$, when utilizing MAC striping with $\ell$-bit payloads and $m$-bit tags. We show that this estimate is too optimistic. For $m\le\ell$ and any payload, we achieve a selective forgery with probability $\ge \binom{\ell+m}{m}^{-1}$, and usually many orders of magnitude more than that.

The Open Smart Grid Protocol (OSGP) is currently deployed in various countries in large-scale Smart Metering projects. The protocol was developed by the OSGP Alliance and published as a standard by the European Telecommunications Standards Institute (ETSI). We identify several security issues in the OSG Protocol, primarily the use of a weak digest function and the way the protocol utilizes the RC4 algorithm for encryption. A straight-forward oracle attack triggers the leakage of key material of the digest function. We outline how an attacker can make use of the simple protocol structure to send maliciously altered messages with valid authentication tags to the meters.

Cryptographic accumulators allow to accumulate a finite set of values into a single succinct accumulator. For every accumulated value, one can efficiently compute a witness, which certifies its membership in the accumulator. However, it is computationally infeasible to find a witness for any non-accumulated value. Since their introduction, various accumulator schemes for numerous practical applications and with different features have been proposed. Unfortunately, to date there is no unifying model capturing all existing features. Such a model can turn out to be valuable as it allows to use accumulators in a black-box fashion. To this end, we propose a unified formal model for (randomized) cryptographic accumulators which covers static and dynamic accumulators, their universal features and includes the notions of undeniability and indistinguishability. Additionally, we provide an exhaustive classification of all existing schemes. In doing so, it turns out that most accumulators are distinguishable. Fortunately, a simple, light-weight generic transformation allows to make many existing dynamic accumulator schemes indistinguishable. As this transformation, however, comes at the cost of reduced collision freeness, we additionally propose the first indistinguishable scheme that does not suffer from this shortcoming. Finally, we employ our unified model for presenting a black-box construction of commitments from indistinguishable accumulators as well as a black-box construction of indistinguishable, undeniable universal accumulators from zero-knowledge sets. Latter yields the first universal accumulator construction that provides indistinguishability.

Compact e-cash schemes allow users to withdraw a wallet containing $K$ coins and to spend each coin unlinkably. We present the first compact e-cash scheme with arbitrary wallet size $k \leq K$ while the spending protocol is of constant time and space complexity. Known compact e-cash schemes are constructed from either verifiable random functions or bounded accumulators. We use both building blocks to construct the new scheme which is secure under the $q$-SDH, the $y$-DDHI and the SXDH assumptions in the random oracle model.

This paper investigates the effect of affine transformations of the Sbox on the maximal expected differential probability MEDP and linear potential MELP over two rounds of a substitution-permutation network, when the diffusion layer is linear over the finite field defined by the Sbox alphabet. It is mainly motivated by the fact that the 2-round MEDP and MELP of the AES both increase when the AES Sbox is replaced by the inversion in $GF(2^8)$. Most notably, we give new upper bounds on these two quantities which are not invariant under affine equivalence. Moreover, within a given equivalence class, these new bounds are maximal when the considered Sbox is an involution. These results point out that different Sboxes within the same affine equivalence class may lead to different two-round MEDP and MELP. In particular, we exhibit some examples where the basis chosen for defining the isomorphism between $GF(2)^m$ and $GF(2^m)$ affects these values. For Sboxes with some particular properties, including all Sboxes of the form $A(x^s)$ as in the AES, we also derive some lower and upper bounds for the 2-round MEDP and MELP which hold for any MDS linear layer.

Pairing-based cryptography (PBC) has many elegant properties. It is claimed that PBC can offer a desired security level with smaller parameters as the general elliptic curve cryptography (ECC). In the note, we remark that this view is misleading. Suppose that an elliptic curve E is defined over the field F_q. Then ECC is working with elements which are defined over F_q. But PBC is working with the functions and elements defined over F_{q^k}, where k is the embedding degree. The security of PBC depends directly on the intractable level of either elliptic curve discrete log problem (ECDLP) in the group E(F_q) or discrete log problem (DLP) in the group F_{q^k}^*. That means PBC protocols have to work in a running environment with parameters of 1024 bits so as to offer 80 bits security level. The shortcoming makes PBC lose its competitive advantages significantly.

A key recovery attack allows an attacker to recover the private key of an underlying encryption scheme when given a number of decryption oracle accesses. Previous research has shown that most existing Somewhat Homomorphic Encryption (SHE) schemes suffer from this attack. In this paper, we propose efficient key recovery attacks against two NTRU-based SHE schemes, which have not gained much attention in the literature. One is published by Lopez-Alt et al. at STOC conference 2012 and the other is published by Bos et al. at the IMACC conference 2013. Parallel to our work, Dahab, Galbraith and Morais have also proposed similar attacks but only for specific parameter settings at ICITS conference 2015. In comparison, our attacks apply to all parameter settings and are more efficient than theirs.

CryptDB has been proposed as a practical and secure middleware to protect databases deployed on semi-honest cloud servers. While CryptDB provides sufficient protection under Threat-1, here we demonstrate that when CryptDB is deployed to secure the cloud hosted database of a realistic web application, an attacker to database or a Malicious Database Administrator (mDBA) can easily steal information, and even escalate his privilege to become the administrator of the web application. Our attacks, fall under a restricted form of Threat-2 where we only assume that the attackers or the mDBA tampers with the CryptDB protected database and is opens an ordinary user account through the web application. Our attacks, are carried out assuming perfectly secure proxy and application servers. Therefore, the attacks work without recovering the master key residing on the proxy server. At the root of the attack lies the lack of any integrity checks for the data in the CryptDB database. We propose a number of practical countermeasures to mitigate attacks targeting the integrity of the CryptDB database. We also demonstrate that the data integrity is not sufficient to protect the databases, when query integrity and frequency attacks are considered.

We consider secure two-party computation in a multiple-execution setting, where two parties wish to securely evaluate the same circuit multiple times. We design efficient garbled-circuit-based two-party protocols secure against malicious adversaries. Recent works by Lindell (Crypto 2013) and Huang-Katz-Evans (Crypto 2013) have obtained optimal complexity for cut-and-choose performed over garbled circuits in the single execution setting. We show that it is possible to obtain much lower amortized overhead for cut-and-choose in the multiple-execution setting. Our efficiency improvements result from a novel way to combine a recent technique of Lindell (Crypto 2013) with LEGO-based cut-and-choose techniques (TCC 2009, Eurocrypt 2013). In concrete terms, for 40-bit statistical security we obtain a 2x improvement (per execution) in communication and computation for as few as 7 executions, and require only 8 garbled circuits (i.e., a 5x improvement) per execution for as low as 3500 executions. Our results suggest the exciting possibility that secure two-party computation in the malicious setting can be less than an order of magnitude more expensive than in the semi-honest setting.

In this paper, we study Password Authenticated Key Exchange (PAKE) in a group. First, we present a generic ``fairy-ring dance'' construction that transforms any secure two-party PAKE scheme to a group PAKE protocol while preserving the round efficiency in the optimal way. Based on this generic construction, we present two concrete instantiations based on using SPEKE and J-PAKE as the underlying PAKE primitives respectively. The first protocol, called SPEKE+, accomplishes authenticated key exchange in a group with explicit key confirmation in just two rounds. This is more round-efficient than any existing group PAKE protocols in the literature. The second protocol, called J-PAKE+, requires one more round than SPEKE+, but is computationally faster. Finally, we present full implementations of SPEKE+ and J-PAKE+ with detailed performance measurements. Our experiments suggest that both protocols are feasible for practical applications in which the group size may vary from three to several dozen. This makes them useful, as we believe, for a wide range of applications -- e.g., to bootstrap secure communication among a group of smart devices in the Internet of Things (IoT).

COPA is a block-cipher-based authenticated encryption mode with a provable birthday-bound security under the assumption that the underlying block cipher is a strong pseudorandom permutation, and its instantiation with the AES block cipher is called AES-COPA. Marble is an AES-based COPA-like authenticated encryption algorithm with a full security. In this paper, we analyse the security of COPA and Marble against universal forgery attacks. We present beyond-birthday-bound (almost) universal forgery attacks on the COPA when used with constant or variable associate data, and present (almost) universal forgery attacks on the Marble when used without associated data or with (variable) associate data. Our attacks on the COPA with variable associate data have a complexity very near the birthday bound, and their applications to AES-COPA show that the security claim of AES-COPA against tag guessing may be not correct; and our attacks on the (newest as well as initial version of) Marble with associate data show that Marble does not provide a full security that the designer claimed. Like many recently published cryptanalytic results on message authentication algorithms with a provable birthday-bound security, our attacks on COPA do not violate its security proofs, but provide a comprehensive understanding of its security against universal forgery attack, show that the success probability of a universal forgery on the COPA is larger than the ideal bound $2^{-n}$ of the standard forgery-resistance, and boil down to an existing open question: Should a message authentication algorithm with a weaker security claim than the standard forgery-resistance be regarded as a sound design?

Fully homomorphic is an encryption scheme that allows for data to be stored and processed in an encrypted format, which gives the cloud provider a solution to host and process data without even knowing what the message is. In previous identity-based homomorphic encryption scheme, computing efficiency is complicated and expensive. In this work, based on Regev’s work, we propose a sampling trapdoor one-way function in arbitrary cyclotomic rings . Then construct a leveled identity-based homomorphic encryption scheme from ring learning with errors, which has advantage in computational efficiency and key management, by using user’s identity as the unique public key. This scheme is proved IND-CPA secure in the random oracle model, relied to hardness of decision ring learning with errors problem.

Vectorial Boolean bent functions, which possess the maximal nonlinearity and the minimum differential uniformity, contribute to optimum resistance against linear cryptanalysis and differential cryptanalysis for the cryptographic algorithms that adopt them as nonlinear components. This paper is devoted to the new primary constructions of vectorial Boolean bent functions, including four types: vectorial monomial bent functions, vectorial Boolean bent functions with multiple trace terms, $\mathcal{H}$ vectorial functions and $\mathcal{H}$-like vectorial functions. For vectorial monomial bent functions, this paper answers one open problem proposed by E. Pasalic et al. and characterizes the vectorial monomial bent functions corresponding to the five known classes of bent exponents. For the vectorial Boolean bent functions with multiple trace terms, this paper answers one open problem proposed by A. Muratović-Ribić et al., presents six new infinite classes of explicit constructions and shows the nonexistence of the vectorial Boolean bent functions from $\mathbb{F}_{2^{n}}$ to $\mathbb{F}_{2^{k}}$ of the form $\sum_{i=1}^{2^{k-2}}Tr^{n}_{k}(ax^{(2i-1)(2^{k}-1)})$ with $n=2k$ and $a\in\mathbb{F}_{2^{k}}^{*}$. Moreover, $\mathcal{H}$ vectorial functions are further characterized. In addition, a new infinite class of vectorial Boolean bent function named as $\mathcal{H}$-like vectorial functions are derived, which includes $\mathcal{H}$ vectorial functions as a subclass.

Structure-preserving signatures are schemes in which public keys, messages, and signatures are all collections of source group elements of some bilinear groups. In this paper, we introduce fully structure-preserving signature schemes, with the additional requirement that even secret keys should be group elements. This new type of structure-preserving signatures allows for efficient non-interactive proofs of knowledge of the secret key and is useful in designing cryptographic protocols with strong security guarantees based on the simulation paradigm where the simulator has to extract the secret keys on-line. To gain efficiency, we construct shrinking structure-preserving trapdoor commitments. This is by itself an important primitive and of independent interest as it appears to contradict a known impossibility result. We argue that a relaxed binding property lets us circumvent the impossibility result while still retaining the usefulness of the primitive in important applications as mentioned above.

A main contribution of this paper is an improved analysis against HMAC instantiating with reduced Whirlpool. It recovers equivalent keys, which are often denoted as Kin and Kout, of HMAC with 7-round Whirlpool, while the previous best attack can work only for 6 rounds. Our approach is applying the meet-in-the-middle (MITM) attack on AES to recover MAC keys of Whirlpool. Several techniques are proposed to bypass different attack scenarios between a block cipher and a MAC, e.g., the chosen plaintext model of the MITM attacks on AES cannot be used for HMAC-Whirlpool. Besides, a larger state size and different key schedule designs of Whirlpool leave us a lot of room to study. As a result, equivalent keys of HMAC with 7-round Whirlpool are recovered with a complexity of (Data, Time, Memory) = (2^481.7, 2^482.3, 2^481).

Using EasyCrypt, we formalize a new modular security proof for one-round authenticated key exchange protocols in the random oracle model. Our proof improves earlier work by Kudla and Paterson (ASIACRYPT 2005) in three significant ways: we consider a stronger adversary model, we provide support tailored to protocols that utilize the Naxos trick, and we support proofs under the Computational DH assumption not relying on Gap oracles. Furthermore, our modular proof can be used to obtain concrete security proofs for protocols with or without adversarial key registration. We use this support to investigate, still using EasyCrypt, the connection between proofs without Gap assumptions and adversarial key registration. For the case of honestly generated keys, we obtain the first proofs of the Naxos and Nets protocols under the Computational DH assumption. For the case of adversarial key registration, we obtain machine-checked and modular variants of the well-known proofs for Naxos, Nets, and Naxos+.

Oblivious RAM (ORAM) is a cryptographic primitive that allows a trusted CPU to securely access untrusted memory, such that the access patterns reveal nothing about sensitive data. ORAM is known to have broad applications in secure processor design and secure multi-party computation for big data. Unfortunately, due to a logarithmic lower bound by Goldreich and Ostrovsky (Journal of the ACM, '96), ORAM is bound to incur a moderate cost in practice. In particular, with the latest developments in ORAM constructions, we are quickly approaching this limit, and the room for performance improvement is small. In this paper, we consider new models of computation in which the cost of obliviousness can be fundamentally reduced in comparison with the standard ORAM model. We propose the Oblivious Network RAM model of computation, where a CPU communicates with multiple memory banks, such that the adversary observes only which bank the CPU is communicating with, but not the address oset within each memory bank. In other words, obliviousness within each bank comes for free either because the architecture prevents a malicious party from observing the address accessed within a bank, or because another solution is used to obfuscate memory accesses within each bank and hence we only need to obfuscate communication patterns between the CPU and the memory banks. We present new constructions for obliviously simulating general or parallel programs in the Network RAM model. We describe applications of our new model in secure processor design and in distributed storage applications with a network adversary.

Often, in privacy-sensitive cryptographic protocols, a party commits to a secret message m and later needs to prove that $m$ belongs to a language L or that m does not belong to L (but this party does not want to reveal any further information). We present a method to prove in a non-interactive way that a committed value does not belong to a given language L. Our construction is generic and relies on the corresponding proof of membership to L. We present an efficient realization of our proof system by combining {smooth projective hash functions} and the Groth-Sahai proof system. In 2009, Kiayias and Zhou introduced {zero-knowledge proofs with witness elimination} which enable to prove that a committed message $m$ belongs to a language L (with a witness w) in such a way that the verifier accepts the interaction only if w does not belong to a set determined by a public relation Q and some private input w' of the verifier. We show that the protocol they proposed is flawed and that a dishonest prover can actually make a verifier accept a proof for any message m in L even if (w,w') in Q. Using our non-interactive proof of non-membership of committed values, we are able to fix their protocol and improve its efficiency. Our approach finds also efficient applications in other settings, e.g. in anonymous credential systems and privacy-preserving authenticated identification and key exchange protocols.

Boneh et al. showed at Crypto 99 that moduli of the form N=p^r q can be factored in polynomial time when r=log p. Their algorithm is based on Coppersmith's technique for finding small roots of polynomial equations. In this paper we show that N=p^r q^s can also be factored in polynomial time when r or s is at least (log p)^3; therefore we identify a new class of integers that can be efficiently factored. We also generalize our algorithm to moduli N with k prime factors; we show that a non-trivial factor of N can be extracted in polynomial-time if one of the k exponents is large enough.

In this paper we study the security of summing the outputs of two independent hash functions, in an effort to increase the security of the resulting design, or to hedge against the failure of one of the hash functions. The exclusive-or (XOR) combiner H1(M)+H2(M) is one of the two most classical combiners, together with the concatenation combiner H1(M)||H2(M). While the security of the concatenation of two hash functions is well understood since Joux's seminal work on multicollisions, the security of the sum of two hash functions has been much less studied. The XOR combiner is well known as a good PRF and MAC combiner, and is used in practice in TLS versions 1.0 and 1.1. In a hash function setting, Hoch and Shamir have shown that if the compression functions are modeled as random oracles, or even weak random oracles (i.e. they can easily be inverted -- in particular H1 and H2 offer no security), H1+H2 is indifferentiable from a random oracle up to the birthday bound. In this work, we focus on the preimage resistance of the sum of two narrow-pipe n-bit hash functions, following the Merkle-Damgård or HAIFA structure (the internal state size and the output size are both n bits). We show a rather surprising result: the sum of two such hash functions, e.g. SHA-512+Whirlpool, can never provide n-bit security for preimage resistance. More precisely, we present a generic preimage attack with a complexity of O(2^5n/6). While it is already known that the XOR combiner is not preserving for preimage resistance (i.e. there might be some instantiations where the hash functions are secure but the sum is not), our result is much stronger: for any narrow-pipe functions, the sum is not preimage resistant. Besides, we also provide concrete preimage attacks on the XOR combiner (and the concatenation combiner) when one or both of the compression functions are weak; this complements Hoch and Shamir's proof by showing its tightness for preimage resistance. Of independent interests, one of our main technical contributions is a novel structure to control simultaneously the behavior of independent hash computations which share the same input message. We hope that breaking the pairwise relationship between their internal states will have applications in related settings.

The iterated Even-Mansour cipher is a construction of a block cipher from $r$ public permutations $P_1,\ldots,P_r$ which abstracts in a generic way the structure of key-alternating ciphers. The indistinguishability of this construction from a truly random permutation by an adversary with oracle access to the inner permutations $P_1,\ldots,P_r$ has been investigated in a series of recent papers. This construction has also been shown to be (fully) indifferentiable from an ideal cipher for a sufficient number of rounds (five or twelve depending on the assumptions on the key-schedule). In this paper, we extend this line of work by considering the resistance of the iterated Even-Mansour cipher to xor-induced related-key attacks (i.e., related-key attacks where the adversary is allowed to xor any constant of its choice to the secret key) and to chosen-key attacks. For xor-induced related-key attacks, we first provide a distinguishing attack for two rounds, assuming the key-schedule is linear. We then prove that for a linear key-schedule, three rounds yield a cipher which is secure against xor-induced related-key attacks up to $O(2^{\frac{n}{2}})$ queries of the adversary, whereas for a nonlinear key-schedule, one round is sufficient to obtain a similar security bound. We also show that the iterated Even-Mansour cipher with four rounds offers some form of provable resistance to chosen-key attacks, which is the minimal number of rounds to achieve this property. The main technical tool that we use to prove this result is \emph{sequential indifferentiability}, a weakened variant of (full) indifferentiability introduced by Mandal \emph{et al.} (TCC~2010).

Invariant subspace attacks were introduced at CRYPTO 2011 to cryptanalyze PRINTcipher. The invariant subspaces for PRINTcipher were discovered in an ad hoc fashion, leaving a generic technique to discover invariant subspaces in other ciphers as an open problem. Here, based on a rather simple observation, we introduce a generic algorithm to detect invariant subspaces. We apply this algorithm to the CAESAR candidate iSCREAM, the closely related LS-design Robin, as well as the lightweight cipher Zorro. For all three candidates invariant subspaces were detected, and result in practical breaks of the ciphers. A closer analysis of independent interest reveals that these invariant subspaces are underpinned by a new type of self-similarity property. For all ciphers, our strongest attack shows the existence of a weak key set of density $2^{-32}$. These weak keys lead to a simple property on the plaintexts going through the whole encryption process with probability one. All our attacks have been practically verified on reference implementations of the ciphers.

We give a new proof of the existence of $O(n^{\epsilon})$-round public-coin concurrent zero-knowledge arguments for NP, where $\epsilon>0$ is an arbitrary constant. The security is proven in the plain model under the assumption that collision-resistant hash functions exist. (The existence of such concurrent zero-knowledge arguments was previously proven by Goyal (STOC'13) in the plain model under the same assumption.) In the proof, we use a new variant of the non-black-box simulation technique of Barak (FOCS'01). An important property of our simulation technique is that the simulator runs in a "straight-line" manner in the fully concurrent setting. Compared with the simulation technique of Goyal, which also has such a property, the analysis of our simulation technique is (arguably) simpler.

A common countermeasure to thwart side-channel analysis attacks is algorithmic masking. For this, algorithms that mix Boolean and arithmetic operations need to either apply two different masking schemes with secure conversions or use dedicated arithmetic units that can process Boolean masked values. Several proposals have been published that can realize these approaches securely and efficiently in software. But to the best of our knowledge, no hardware design exists that fulfills relevant properties such as efficiency and security at the same time. In this paper, we present two design strategies to realize a secure and efficient arithmetic adder for Boolean-masked values. First, we introduce an architecture based on the ripple-carry adder that targets low-cost applications. The second architecture is based on a pipelined Kogge-Stone adder and targets high-performance applications. In particular, all our implementations adopt the threshold implementation approach to improve their resistance against SCA attacks even in the presence of glitches. We evaluated the security of our designs practically against SCA using a non-specific statistical t-test. Based on our analysis, we show that our constructions not only achieve resistance against first- and (univariate) second-order attacks but also require fewer random bits per operation compared to any existing software-based approach.

We study the possibility of GOST block cipher modifcation in such way, that it would resist Isobe and Dinur-Dunkelman-Shamir attacks, and, at the same time, would be still lightweight-friendly.

Multi-party fair exchange (MFE) and fair secure multi-party computation (fair SMPC) are is under-studied field of research, with practical importance. In particular, we consider MFE scenarios where at the end of the protocol, either every participant receives every other participant’s item, or no participant receives anything. We analyze the case where a trusted third party (TTP) is optimistically available, although we emphasize that the trust put on the TTP is only regarding the fairness, and our protocols preserve the privacy of the exchanged items against the TTP. In the fair SMPC case, we prove that a malicious TTP can only harm fairness, but not security. We construct two asymptotically optimal multi-party fair exchange protocols that require a constant number of rounds (in comparison to linear) and O(n^2) messages (in comparison to cubic), where n is the number of participating parties. In one protocol, we enable the parties to efficiently exchange any item that can be efficiently put into a verifiable encryption (e.g., signatures on a contract). We show how to apply this protocol on top of any SMPC protocol to achieve fairness with very little overhead (independent of the circuit size), especially if the SMPC protocol works with arithmetic circuits. In our other protocol, we let the parties exchange any verifiable item, without the constraint that it must be efficiently put into a verifiable encryption (e.g., a file cannot be efficiently verifiably encrypted, but if its hash is known, once obtained, the file can be verified). We achieve this via the use of electronic payments, where if an item is not obtained, the payment of its owner will be obtained in return of the item that is sent. We then generalize our protocols to efficiently handle any exchange topology (participants exchange items with arbitrary other participants). Our protocols guarantee fairness in its strongest sense: even if all n-1 other participants are malicious and colluding with each other, the fairness is still guaranteed.

PKCS\#11 is a very popular cryptographic API: it is the standard used by many Hardware Security Modules, smartcards and software cryptographic tokens. Several attacks have been uncovered against PKCS\#11 at different levels: intrinsic logical flaws, cryptographic vulnerabilities or severe compliance issues. Since affected hardware remains widespread in computer infrastructures, we propose a user-centric and pragmatic approach for secure usage of vulnerable devices. We introduce \textit{Caml Crush}, a PKCS\#11 filtering proxy. Our solution allows to dynamically protect PKCS\#11 cryptographic tokens from state of the art attacks. This is the first approach that is immediately applicable to commercially available products. We provide a fully functional open source implementation with an extensible filter engine effectively shielding critical resources. This yields additional advantages to using \textit{Caml Crush} that go beyond classical PKCS\#11 weakness mitigations.

There is a growing need to develop lightweight cryptographic primitives suitable for resource-constrained devices permeating in increasing numbers into the fabric of life. Such devices are exemplified none more so than by batteryless radio frequency identification (RFID) tags in applications ranging from automatic identification and monitoring to anti-counterfeiting. Pandaka is a lightweight cipher together with a protocol proposed in INFOCOM 2014 for extremely resource limited RFID tags. It is designed to reduce the hardware cost (area of silicon) required for implementing the cipher by shifting the computationally intensive task of cryptographically secure random number generation to the reader. In this paper we evaluate Pandaka and demonstrate that the communication protocol contains flaws which completely break the security of the cipher and make Pandaka susceptible to de-synchronisation. Furthermore, we show that, even without the protocol flaws, we can use a guess and determine method to mount an attack on the cipher for the more challenging scenario of a known-plaintext attack with an expected complexity of only $2^{55}$. We conclude that Pandaka needs to be amended and highlight simple measures to prevent the above attacks.

Oblivious transfer (OT) is one of the most fundamental primitives in cryptography and is widely used in protocols for secure two-party and multi-party computation. As secure computation becomes more practical, the need for practical large scale oblivious transfer protocols is becoming more evident. Oblivious transfer extensions are protocols that enable a relatively small number of “base-OTs” to be utilized to compute a very large number of OTs at low cost. In the semi-honest setting, Ishai et al. (CRYPTO 2003) presented an OT extension protocol for which the cost of each OT (beyond the base-OTs) is just a few hash function operations. In the malicious setting, Nielsen et al. (CRYPTO 2012) presented an efficient OT extension protocol for the setting of active adversaries, that is secure in the random oracle model. In this work, we present an OT extension protocol for the setting of malicious adversaries that is more efficient and uses less communication than previous works. In addition, our protocol can be proven secure in both the random oracle model, and in the standard model with a type of correlation robustness. Given the importance of OT in many secure computation protocols, increasing the efficiency of OT extensions is another important step forward to making secure computation practical.

In this paper, we study the problem of automatically verifying higher-order masking countermeasures. This problem is important in practice (weaknesses have been discovered in schemes that were thought secure), but is inherently exponential: for $t$-order masking, it involves proving that every subset of $t$ intermediate variables is distributed independently of the secrets. Some type systems have been proposed to help cryptographers check their proofs, but many of these approaches are insufficient for higher-order implementations. We propose a new method, based on program verification techniques, to check the independence of sets of intermediate variables from some secrets. Our new language-based characterization of the problem also allows us to design and implement several algorithms that greatly reduce the number of sets of variables that need to be considered to prove this independence property on \emph{all} valid adversary observations. The result of these algorithms is either a proof of security or a set of observations on which the independence property cannot be proved. We focus on AES implementations to check the validity of our algorithms. We also confirm the tool's ability to give useful information when proofs fail, by rediscovering existing attacks and discovering new ones.

In recent years, a number of standardized symmetric encryption schemes have fallen foul of attacks exploiting the fact that in some real world scenarios ciphertexts can be delivered in a fragmented fashion. We initiate the first general and formal study of the security of symmetric encryption against such attacks. We extend the SSH-specific work of Paterson and Watson (Eurocrypt 2010) to develop security models for the fragmented setting. We also develop security models to formalize the additional desirable properties of ciphertext boundary hiding and robustness against Denial-of-Service (DoS) attacks for schemes in this setting. We illustrate the utility of each of our models via efficient constructions for schemes using only standard cryptographic components, including constructions that simultaneously achieve confidentiality, ciphertext boundary hiding and DoS robustness.

Multiparty computation can be used for privacy-friendly outsourcing of computations on private inputs of multiple parties. A computation is outsourced to several computation parties; if not too many are corrupted (e.g., no more than half), then they cannot determine the inputs or produce an incorrect output. However, in many cases, these guarantees are not enough: we need correctness even if /all/ computation parties may be corrupted; and we need that correctness can be verified even by parties that did not participate in the computation. Protocols satisfying these additional properties are called ``universally verifiable''. In this paper, we propose a new security model for universally verifiable multiparty computation, and we present a practical construction, based on a threshold homomorphic cryptosystem. We also develop a multiparty protocol for jointly producing non-interactive zero-knowledge proofs, which may be of independent interest.

In a cold boot attack a cryptosystem is compromised by analysing a noisy version of its internal state. For instance, if a computer is rebooted the memory contents are rarely fully reset; instead, after the reboot an adversary might recover a noisy image of the old memory contents and use it as a stepping stone for reconstructing secret keys. While such attacks were known for a long time, they recently experienced a revival in the academic literature. Here, typically either RSA-based schemes or blockciphers are targeted. We observe that essentially no work on cold boot attacks on schemes defined in the discrete logarithm setting (DL) and particularly for elliptic curve cryptography (ECC) has been conducted. In this paper we hence consider cold boot attacks on selected wide-spread implementations of DL-based cryptography. We first introduce a generic framework to analyse cold boot settings and construct corresponding key-recovery algorithms. We then study common in-memory encodings of secret keys (in particular those of the wNAF-based and comb-based ECC implementations used in OpenSSL and PolarSSL, respectively), identify how redundancies can be exploited to make cold boot attacks effective, and develop efficient dedicated key-recovery algorithms. We complete our work by providing theoretical bounds for the success probability of our attacks.

The Learning With Error problem (LWE) is becoming more and more used in cryptography, for instance, in the design of some fully homomorphic encryption schemes. It is thus of primordial importance to find the best algorithms that might solve this problem so that concrete parameters can be proposed. The BKW algorithm was proposed by Blum et al. as an algorithm to solve the Learning Parity with Noise problem (LPN), a subproblem of LWE. This algorithm was then adapted to LWE by Albrecht et al. In this paper, we improve the algorithm proposed by Albrecht et al. by using multidimensional Fourier transforms. Our algorithm is, to the best of our knowledge, the fastest LWE solving algorithm. Compared to the work of Albrecht et al. we greatly simplify the analysis, getting rid of integrals which were hard to evaluate in the final complexity. We also remove some heuristics on rounded Gaussians. Some of our results on rounded Gaussians might be of independent interest. Moreover, we also analyze algorithms solving LWE with discrete Gaussian noise. Finally, we apply the same algorithm to the Learning With Rounding problem (LWR) for prime q, a deterministic counterpart to LWE. This problem is getting more and more attention and is used, for instance, to design pseudorandom functions. To the best of our knowledge, our algorithm is the first algorithm applied directly to LWR. Furthermore, the analysis of LWR contains some technical results of independent interest.