Many efficient data structures use randomness, allowing them to improve upon deterministic ones. Usually, their efficiency and correctness are analyzed using probabilistic tools under the assumption that the inputs and queries are independent of the internal randomness of the data structure. In this work, we consider data structures in a more robust model, which we call the adversarial model. Roughly speaking, this model allows an adversary to choose inputs and queries adaptively according to previous responses. Specifically, we consider a data structure known as "Bloom filter" and prove a tight connection between Bloom filters in this model and cryptography. A Bloom filter represents a set $S$ of elements approximately, by using fewer bits than a precise representation. The price for succinctness is allowing some errors: for any $x \in S$ it should always answer `Yes', and for any $x \notin S$ it should answer `Yes' only with small probability. In the adversarial model, we consider both efficient adversaries (that run in polynomial time) and computationally unbounded adversaries that are only bounded in the number of queries they can make. For computationally bounded adversaries, we show that non-trivial (memory-wise) Bloom filters exist if and only if one-way functions exist. For unbounded adversaries we show that there exists a Bloom filter for sets of size $n$ and error $\varepsilon$, that is secure against $t$ queries and uses only $O(n \log{\frac{1}{\varepsilon}}+t)$ bits of memory. In comparison, $n\log{\frac{1}{\varepsilon}}$ is the best possible under a non-adaptive adversary.

A side-channel analysis of multiplication in GF(2^{128}) has recently been published by Belaïd, Fouque and Gérard at Asiacrypt 2014, with an application to AES-GCM. Using the least significant bit of the Hamming weight of the multiplication result, the authors have shown how to recover the secret multiplier efficiently. However such least significant bit is very sensitive to noise measurement; this implies that without averaging their attack can only work for high signal-to-noise ratios (SNR > 128). In this paper we describe a new side-channel attack against the multiplication in GF(2^{128}) that uses the most significant bits of the Hamming weight. We show that much higher values of noise can be then tolerated. For instance with an SNR equal to 8, the key can be recovered using 2^{20} consumption traces with time and memory complexities respectively equal to 2^{51.68} and 2^{36}. We moreover show that the new method can be extended to attack the fresh re-keying countermeasure proposed by Medwed, Standaert, Großschädl and Regazzoni at Africacrypt 2010.

We provide a security analysis for full-state keyed Sponge and full-state Duplex constructions. Our results can be used for making a large class of Sponge-based authenticated encryption schemes more efficient by concurrent absorption of associated data and message blocks. In particular, we introduce and analyze a new variant of SpongeWrap with almost free authentication of associated data. The idea of using full-state message absorption for higher efficiency was first made explicit in the Donkey Sponge MAC construction, but without any formal security proof. Recently, Gaži, Pietrzak and Tessaro (CRYPTO 2015) have provided a proof for the fixed-output-length variant of Donkey Sponge. Yasuda and Sasaki (CT-RSA 2015) have considered partially full-state Sponge-based authenticated encryption schemes for efficient incorporation of associated data. In this work, we unify, simplify, and generalize these results about the security and applicability of full-state keyed Sponge and Duplex constructions; in particular, for designing more efficient authenticated encryption schemes. Compared to the proof of Gaži et al., our analysis directly targets the original Donkey Sponge construction as an arbitrary-output-length function. Our treatment is also more general than that of Yasuda and Sasaki, while yielding a more efficient authenticated encryption mode for the case that associated data might be longer than messages.

In this paper we are proposing an ultra lightweight, a very compact block cipher ‘PICO’. PICO is a substitution and permutation based network, which operates on a 64 bit plain text and supports a key length of 128 bits. It has a VERY compact structure that requires GEs for a 128 bit key length. The PICO cipher uses strong bit permutation layer which only needs wires for implementation this reduces overall gate count. Its unique design helps to generate a large number of active S - boxes in fewer rounds which thwart the linear and differential attacks on the cipher. PICO shows good performance on both the hardware and the software platforms. PICO consumes only 2504 bytes of Flash memory which is less than ultra lightweight cipher PRESENT. PICO has a very strong Substitution layer(S- box) which not only makes the design robust but also introduces a great avalanche effect. PICO has strong and compact key scheduling which is motivated from latest NSA designed cipher SPECK. PICO consumes 28mW of dynamic power which is less than the PRESENT cipher (31mW). In this paper we have presented the security analysis of PICO and its performance as an ultra lightweight compact cipher. PICO resists linear, differential, biclique, zero correlation, meet in the middle and key related attacks.

We study how to construct efficient tweakable block ciphers in the Random Permutation model, where all parties have access to public random permutation oracles. We propose a construction that combines, more efficiently than by mere black-box composition, the CLRW construction (which turns a traditional block cipher into a tweakable block cipher) of Landecker et al. (CRYPTO 2012) and the iterated Even-Mansour construction (which turns a tuple of public permutations into a traditional block cipher) that has received considerable attention since the work of Bogdanov et al. (EUROCRYPT 2012). More concretely, we introduce the (one-round) tweakable Even-Mansour (TEM) cipher, constructed from a single $n$-bit permutation $P$ and a uniform and almost XOR-universal family of hash functions $(H_k)$ from some tweak space to $\{0,1\}^n$, and defined as $(k,t,x)\mapsto H_k(t)\oplus P(H_k(t)\oplus x)$, where $k$ is the key, $t$ is the tweak, and $x$ is the $n$-bit message, as well as its generalization obtained by cascading $r$ independently keyed rounds of this construction. Our main result is a security bound up to approximately $2^{2n/3}$ adversarial queries against adaptive chosen-plaintext and ciphertext distinguishers for the two-round TEM construction, using Patarin's H-coefficients technique. We also provide an analysis based on the coupling technique showing that asymptotically, as the number of rounds $r$ grows, the security provided by the $r$-round TEM construction approaches the information-theoretic bound of $2^n$ adversarial queries.

In Wireless Sensor Networks(WSNs), a group of users communicating on an unreliable wireless channel can use a group secret. For each session, group manager broadcasts a message containing some keying material, from which only the group members authorized in that session can extract the session key. If a member misses a broadcast message for key, it uses self healing to recover missing session key using most recent broadcast message. However, only self healing does not help if node needs to get most recent session key and have missed the corresponding broadcast. Through mutual healing, a node can request recent broadcast information from a neighboring node and then recover the required key using self-healing. In this paper, we propose a bi-linear pairing based self-healing scheme that reduces communication, storage and computation overhead in comparison to existing bi-linear pairing based self-healing schemes. Then, we discuss the mutual healing scheme that provides mutual authentication and key confirmation without disclosing the node locations to the adversary. The analysis with respect to active adversary shows a significant performance improvement for resource constrained sensor nodes along with the security features such as forward and backward secrecy, resilience against node collusion, node revocation and resistance to impersonation.

Side-channel attacks generally rely on the availability of good leakage models to extract sensitive information from cryptographic implementations. The recently introduced leakage certification tests aim to guarantee that this condition is fulfilled based on sound statistical arguments. They are important ingredients in the evaluation of leaking devices since they allow a good separation between engineering challenges (how to produce clean measurements) and cryptographic ones (how to exploit these measurements). In this paper, we propose an alternative leakage certification test that is significantly simpler to implement than the previous proposal from Eurocrypt 2014. This gain admittedly comes at the cost of a couple of heuristic (yet reasonable) assumptions on the leakage distribution. To confirm its relevance, we first show that it allows confirming previous results of leakage certification. We then put forward that it leads to additional and useful intuitions regarding the information losses caused by incorrect assumptions in leakage modeling.

Leakage detection usually refers to the task of identifying data-dependent information in side-channel measurements, independent of whether this information can be exploited. Detecting Points-Of-Interest (POIs) in leakage traces is a complementary task that is a necessary first step in most side-channel attacks, where the adversary wants to turn this information into (e.g.) a key recovery. In this paper, we discuss the differences between these tasks, by investigating a popular solution to leakage detection based on a t-test, and an alternative method exploiting Pearson's correlation coefficient. We first show that the simpler t-test has better sampling complexity, and that its gain over the correlation-based test can be predicted by looking at the Signal-to-Noise Ratio (SNR) of the leakage partitions used in these tests. This implies that the sampling complexity of both tests relates more to their implicit leakage assumptions than to the actual statistics exploited. We also put forward that this gain comes at the cost of some intuition loss regarding the localization of the exploitable leakage samples in the traces, and their informativeness. Next, and more importantly, we highlight that our reasoning based on the SNR allows defining an improved t-test with significantly faster detection speed (with approximately 5 times less measurements in our experiments), which is therefore highly relevant for evaluation laboratories. We finally conclude that whereas t-tests are the method of choice for leakage detection only, correlation-based tests exploiting larger partitions are preferable for detecting POIs. We confirm this intuition by improving automated tools for the detection of POIs in the leakage measurements of a masked implementation, in a black box manner and without key knowledge, thanks to a correlation-based leakage detection test.

We describe three contributions regarding the Soft Analytical Side-Channel Attacks (SASCA) introduced at Asiacrypt 2014. First, we compare them with Algebraic Side-Channel Attacks (ASCA) in a noise-free simulated setting. We observe that SASCA allow more efficient key recoveries than ASCA, even in this context (favorable to the latter). Second, we describe the first working experiments of SASCA against an actual AES implementation. Doing so, we analyse their profiling requirements, put forward the significant gains they provide over profiled Differential Power Analysis (DPA) in terms of number of traces needed for key recoveries, and discuss the specificities of such concrete attacks compared to simulated ones. Third, we evaluate the distance between SASCA and DPA enhanced with computational power to perform enumeration, and show that the gap between both attacks can be quite reduced in this case. Therefore, our results bring interesting feedback for evaluation laboratories. They suggest that in several relevant scenarios (e.g. attacks exploiting many known plaintexts), taking a small margin over the security level indicated by standard DPA with enumeration should be sufficient to prevent more elaborate attacks such as SASCA. By contrast, SASCA may remain the only option in more extreme scenarios (e.g. attacks with unknown plaintexts/ciphertexts or against leakage-resilient primitives). We conclude by recalling the algorithmic dependency of the latter attacks, and therefore that our conclusions are specific to the AES.

A detailed overview of the problems, solutions and experience of the first international student's Olympiad in cryptography, NSUCRYPTO'2014, is given. We start with rules of participation and description of rounds. All 15 problems of the Olympiad and their solutions are considered in detail. There are discussed solutions of the mathematical problems related to cipher constructing such as studying of differential characteristics of S-boxes, S-box masking, determining of relations between cyclic rotation and additions modulo $2$ and $2^n$, constructing of special linear subspaces in $\mathbb{F}_2^n$; problems about the number of solutions of the equation $F(x)+F(x+a)=b$ over the finite field $\mathbb{F}_{2^n}$ and APN functions. Some unsolved problems in symmetric cryptography are also considered.

\textit{Khudra} is a block cipher proposed in the SPACE'2014 conference, whose main design goal is to achieve suitability for the increasingly popular Field Programmable Gate Array (FPGA) implementation. It is an 18-round lightweight cipher based on recursive Feistel structure, with a 64-bit block size and 80-bit key size. In this paper, we compute the minimum number of active $F$-functions in differential characteristics in the related-key setting, and give a more accurate measurement of the resistance of \textit{Khudra} against related-key differential cryptanalysis. We construct a related-key boomerang quartet with probability $2^{-48}$ for the 14-round \textit{Khudra}, which is better than the highest probability related-key boomerang quartet of the 14-round \textit{Khudra} of probability at most $2^{-72}$ claimed by the designers. Then we propose a related-key rectangle attack on the 16-round \textit{Khudra} without whitening key by constructing a related-key rectangle distinguisher for 12-round \textit{Khudra} with a probability of $2^{-23.82}$. The attack has time complexity of $2^{78.68}$ memory accesses and data complexity of $2^{57.82}$ chosen plaintexts, and requires only four related keys. This is the best known attack on the round-reduced \textit{Khudra}.

We give generic constructions of several fundamental cryptographic primitives based on a new encryption primitive that combines circular security for bit encryption with the so-called reproducibility property (Bellare et al. PKC 2003). At the heart of our constructions is a novel technique which gives a way of de-randomizing reproducible public-key bit-encryption schemes and also a way of reducing one-wayness conditions of a constructed trapdoor-function family (TDF) to circular security of the base scheme. The main primitives that we build from our encryption primitive include k-wise one- way TDFs (Rosen and Segev TCC 2009), CCA2-secure encryption and deterministic encryption. Our results demonstrate a new set of applications of circularly-secure encryption beyond fully-homomorphic encryption and symbolic soundness. Finally, we show the plausibility of our assumptions by showing that the DDH-based circularly-secure scheme of Boneh et al. (Crypto 2008) and the subgroup indistinguishability based scheme of Brakerski and Goldwasser (Crypto 2010) are both reproducible.

In this paper we analyze the security of the compression function of SHA-1 against collision attacks, or equivalently free-start collisions on the hash function. While a lot of work has been dedicated to the analysis of SHA-1 in the past decade, this is the first time that free-start collisions have been considered for this function. We exploit the additional freedom provided by this model by using a new start-from-the-middle approach in combination with improvements on the cryptanalysis tools that have been developed for SHA-1 in the recent years. This results in particular in better differential paths than the ones used for hash function collisions so far. Overall, our attack requires about $2^{50}$ evaluations of the compression function in order to compute a one-block free-start collision for a 76-step reduced version, which is so far the highest number of steps reached for a collision on the SHA-1 compression function. We have developed an efficient GPU framework for the highly branching code typical of a cryptanalytic collision attack and used it in an optimized implementation of our attack on recent GTX-970 GPUs. We report that a single cheap US$350 GTX-970 is sufficient to find the collision in less than 5 days. This showcases how recent mainstream GPUs seem to be a good platform for expensive and even highly-branching cryptanalysis computations. Finally, our work should be taken as a reminder that cryptanalysis on SHA-1 continues to improve. This is yet another proof that the industry should quickly move away from using this function.

IEEE 802.15.4 is a wireless standard used by a variety of higher-level protocols, including many used in the Internet of Things (IoT). A number of system on a chip (SoC) devices that combine a radio transceiver with a microcontroller are available for use in IEEE 802.15.4 networks. IEEE 802.15.4 supports the use of AES-CCM* for encryption and authentication of messages, and a SoC normally includes an AES accelerator for this purpose. This work measures the leakage characteristics of the AES accelerator on the Atmel ATMega128RFA1, and then demonstrates how this allows recovery of the encryption key from nodes running an IEEE 802.15.4 stack. While this work demonstrates the attack on a specific SoC, the results are also applicable to similar wireless nodes and to protocols built on top of IEEE 802.15.4.

Bitcoin has become the most successful cryptocurrency ever deployed, and its most distinctive feature is that it is decentralized. Its underlying protocol (Nakamoto consensus) achieves this by using proof of work, which has the drawback that it causes the consumption of vast amounts of energy to maintain the ledger. Moreover, Bitcoin mining dynamics have become less distributed over time. Towards addressing these issues, we propose SpaceMint, a cryptocurrency based on proofs of space instead of proofs of work. Miners in SpaceMint dedicate disk space rather than computation. We argue that SpaceMint's design solves or alleviates several of Bitcoin's issues: most notably, its large energy consumption. SpaceMint also rewards smaller miners fairly according to their contribution to the network, thus incentivizing more distributed participation. This paper adapts proof of space to enable its use in cryptocurrency, studies the attacks that can arise against a Bitcoin-like blockchain that uses proof of space, and proposes a new blockchain format and transaction types to address these attacks. Our prototype shows that initializing 1 TB for mining takes about a day (a one-off setup cost), and miners spend on average just a fraction of a second per block mined. Finally, we provide a game-theoretic analysis modeling SpaceMint as an extensive game (the canonical game-theoretic notion for games that take place over time) and show that this stylized game satisfies a strong equilibrium notion, thereby arguing for SpaceMint's stability and consensus.

Profiled side-channel attacks are understood to be powerful when applicable: in the best case when an adversary can comprehensively characterise the leakage, the resulting model leads to attacks requiring a minimal number of leakage traces for success. Such `complete' leakage models are designed to capture the scale, location and shape of the profiling traces, so that any deviation between these and the attack traces potentially produces a mismatch which renders the model unfit for purpose. This severely limits the applicability of profiled attacks in practice and so poses an interesting research challenge: how can we design profiled distinguishers that can tolerate (some) differences between profiling and attack traces? This submission is the first to tackle the problem head on: we propose distinguishers (utilising unsupervised machine learning methods, but also a `down-to-earth' method combining mean traces and PCA) and evaluate their behaviour across an extensive set of distortions that we apply to representative trace data. Our results show that the profiled distinguishers are effective and robust to distortions to a surprising extent.

We propose new generic key recovery attacks on Feistel-type block ciphers. The proposed attack is based on the all subkeys recovery approach presented in SAC 2012, which determines all subkeys instead of the master key. This enables us to construct a key recovery attack without taking into account a key scheduling function. With our advanced techniques, we apply several key recovery attacks to Feistel-type block ciphers. For instance, we show 8-, 9- and 11-round key recovery attacks on n-bit Feistel ciphers with 2n-bit key employing random keyed F-functions, random F-functions, and SP-type F-functions, respectively. Moreover, thanks to the meet-in-the-middle approach, our attack leads to low-data complexity. To demonstrate the usefulness of our approach, we show a key recovery attack on the 8-round reduced CAST-128, which is the best attack with respect to the number of attacked rounds. Since our approach derives the lower bounds on the numbers of rounds to be secure under the single secret key setting, it can be considered that we unveil the limitation of designing an efficient block cipher by a Feistel scheme such as a low-latency cipher.

Digital signature is a fundamental primitive with numerous applications. Following the development of pairing-based cryptography, several taking advantage of this setting have been proposed. Among them, the Camenisch-Lysyanskaya (CL) signature scheme is one of the most flexible and has been used as a building block for many other protocols. Unfortunately, this scheme suffers from a linear size in the number of messages to be signed which limits its use in many situations. In this paper, we propose a new signature scheme with the same features as CL-signatures but without the linear-size drawback: our signature consists of only two elements, whatever the message length, and our algorithms are more efficient. This construction takes advantage of using type 3 pairings, that are already widely used for security and efficiency reasons. We prove the security of our scheme without random oracles but in the generic group model. Finally, we show that protocols using CL-signatures can easily be instantiated with ours, leading to much more efficient constructions.

Securely sharing the same secret key among multiple parties is the main concern in symmetric cryptography that is the workhorse of modern cryptography due to its simplicity and fast speed. Typically asymmetric cryptography is used to set up a shared secret between parties, after which the switch to symmetric cryptography can be made. In this paper, we introduce a novel key exchange protocol based on physical hardware implementation to establish a shared secret between parties rather than relying on mathematical implementation of asymmetric cryptography. In particular, the key exchange is dependent on a new security concept named as virtual proof of reality or simply virtual proof (VP) that enables proof of a physical statement over untrusted digital communication channels between two parties (a prover and a verifier) residing in two separate local systems. We firstly exploit the VP to secure key exchange and further prove it by using experimental data. The key transferred in this protocol is only seen by the prover and hidden from not only the adversary but also the verifier. While only the verifier can successfully discover it.

Recently, there has been huge progress in the field of concretely efficient secure computation, even while providing security in the presence of \emph{malicious adversaries}. This is especially the case in the two-party setting, where constant-round protocols exist that remain fast even over slow networks. However, in the multi-party setting, all concretely efficient fully-secure protocols, such as SPDZ, require many rounds of communication. In this paper, we present an MPC protocol that is fully-secure in the presence of malicious adversaries and for any number of corrupted parties. Our construction is based on the constant-round BMR protocol of Beaver et al., and is the first version of that protocol that is \emph{concretely} efficient for the dishonest majority case. Our protocol includes an online phase that is extremely fast and mainly consists of each party locally evaluating a garbled circuit. For the offline phase we present both a generic construction (using any underlying MPC protocol), and a highly efficient instantiation based on the SPDZ protocol. Our estimates show the protocol to be considerably more efficient than previous fully-secure multi-party protocols.

We give a simple heuristic sieving algorithm for the $m$-dimensional exact shortest vector problem (SVP) which runs in time $2^{0.3112m +o(m)}$. Unlike previous time-memory trade-offs, we do not increase the memory, which stays at its bare minimum $2^{0.2075m +o(m)}$. To achieve this complexity, we borrow a recent tool from coding theory, known as nearest neighbor search for binary code words. We simplify its analysis, and show that it can be adapted to solve this variant of the fixed-radius nearest neighbor search problem: Given a list of exponentially many unit vectors of $\mR^m$, and an angle $\gamma\pi$, find all pairs of vectors whose angle $\leq\gamma\pi$. The complexity is sub-quadratic which leads to the improvement for lattice sieves.

We present a new, decentralized, efficient, and secure digital cryptocurrency, in which the ordinary users themselves keep turns to ensure that the systems works well.

In this paper, we present a single round two-party {\em attribute-based authenticated key exchange} (ABAKE) protocol in the framework of ciphertext-policy attribute-based systems. Since pairing is a costly operation and the composite order groups must be very large to ensure security, we focus on pairing free protocols in prime order groups. The proposed protocol is pairing free, working in prime order group and having tight reduction to Strong Diffie Hellman (SDH) problem under the attribute-based Canetti Krawzyck (CK) model which is a natural extension of the CK model (which is for the PKI-based authenticated key exchange) for the attribute-based setting. The security proof is given in the random oracle model. Our ABAKE protocol does not depend on any underlying attribute-based encryption or signature schemes unlike the previous solutions for ABAKE. Ours is the \textit{first} scheme that removes this restriction. Thus, the first major advantage is that smaller key sizes are sufficient to achieve comparable security. Another notable feature of our construction is that it involves only constant number of exponentiations per party unlike the state-of-the-art ABAKE protocols where the number of exponentiations performed by each party depends on the size of the linear secret sharing matrix. We achieve this by doing appropriate precomputation of the secret share generation. Ours is the \textit{first} construction that achieves this property. Our scheme has several other advantages. The major one being the capability to handle active adversaries. Most of the previous ABAKE protocols can offer security only under passive adversaries. Our protocol recognizes the corruption by an active adversary and aborts the process. In addition to this property, our scheme satisfies other security properties that are not covered by CK model such as forward secrecy, key compromise impersonation attacks and ephemeral key compromise impersonation attacks.

Recently, IACR ePrint archive posted two fully homomorphic encryption schemes without bootstrapping. In this note, we show that these schemes are trivially insecure. Furthermore, we also show that the encryption schemes of Liu and Wang in CCS 2012 and the encryption scheme of Liu, Bertino, and Xun in ASIACCS 2014 are insecure either.

Although adopted by many cryptocurrencies, the Bitcoin mining protocol is not incentive-compatible, as the selfish mining strategy enables a miner to gain unfair mining rewards. Existing defenses either demand fundamental changes to block validity rules or have little effect on an attacker with more than one third of the total mining power. This paper proposes an effective defense mechanism against resourceful selfish miners. Our defense requires miners to publish intermediate blocks, the by-products of the mining process, then build on each other's work. By adding transparency to the mining process, block forks are resolved by comparing the amount of work of each branch. Moreover, this mechanism has the advantages of backward compatibility, low communication and computational costs, accelerating block propagation, and mitigating double-spending attacks on fast payments. To evaluate our design, we computed the most profitable mining strategy within our defense with analysis and simulation. Our simulation showed that within our defense, a selfish miner with almost half of the total mining power can only gain marginal unfair block rewards.

We provide a formal treatment of security of digital signatures against subversion attacks (SAs). Our model of subversion generalizes previous work in several directions, and is inspired by the proliferation of software attacks (e.g., malware and buffer overflow attacks), and by the recent revelations of Edward Snowden about intelligence agencies trying to surreptitiously sabotage cryptographic algorithms. The main security requirement we put forward demands that a signature scheme should remain unforgeable even in the presence of an attacker applying SAs (within a certain class of allowed attacks) in a fully-adaptive and continuous fashion. Previous notions---e.g., the notion of security against algorithm-substitution attacks introduced by Bellare et al. (CRYPTO '14) for symmetric encryption---were non-adaptive and non-continuous. In this vein, we show both positive and negative results for the goal of constructing subversion-resilient signature schemes. Negative results. As our main negative result, we show that a broad class of randomized signature schemes is unavoidably insecure against SAs, even if using just a single bit of randomness. This improves upon earlier work that was only able to attack schemes with larger randomness space. When designing our new attack we consider undetectability as an explicit adversarial goal, meaning that the end-users (even the ones knowing the signing key) should not be able to detect that the signature scheme was subverted. Positive results. We complement the above negative results by showing that signature schemes with unique signatures are subversion-resilient against all attacks that meet a basic undetectability requirement. A similar result was shown by Bellare et al. for symmetric encryption, who proved the necessity to rely on stateful schemes; in contrast unique signatures are stateless, and in fact they are among the fastest and most established digital signatures available. As our second positive result, we show how to construct subversion-resilient identification schemes from subversion-resilient signature schemes. We finally show that it is possible to devise signature schemes secure against arbitrary tampering with the computation, by making use of an un-tamperable cryptographic reverse firewall (Mironov and Stephens-Davidowitz, EUROCRYPT '15), i.e., an algorithm that "sanitizes" any signature given as input (using only public information). The firewall we design allows to successfully protect so-called re-randomizable signature schemes (which include unique signatures as special case). As an additional contribution, we extend our model to consider multiple users and show implications and separations among the various notions we introduced. While our study is mainly theoretical, due to its strong practical motivation, we believe that our results have important implications in practice and might influence the way digital signature schemes are selected or adopted in standards and protocols.

The ASASA construction is a new design scheme introduced at Asiacrypt 2014 by Biryukov, Bouillaguet and Khovratovich. Its versatility was illustrated by building two public-key encryption schemes, a secret-key scheme, as well as super S-box subcomponents of a white-box scheme. However one of the two public-key cryptosystems was recently broken at Crypto 2015 by Gilbert, Plût and Treger. As our main contribution, we propose a new algebraic key-recovery attack able to break at once the secret-key scheme as well as the remaining public-key scheme, in time complexity 2^63 and 2^39 respectively (the security parameter is 128 bits in both cases). Furthermore, we present a second attack of independent interest on the same public-key scheme, which heuristically reduces the problem of breaking the scheme to an LPN instance with tractable parameters. This allows key recovery in time complexity 2^56. Finally, as a side result, we outline a very efficient heuristic attack on the white- box scheme, which breaks instances claiming 64 bits of security under one minute on a laptop computer.

At CRYPTO 2012, Knellwolf and Khovratovich presented a differential formulation of advanced meet-in-the-middle techniques for preimage attacks on hash functions. They demonstrated the usefulness of their approach by significantly improving the previously best known attacks on SHA-1 from CRYPTO~2009, increasing the number of attacked rounds from a 48-round one-block pseudo-preimage without padding and a 48-round two-block preimage without padding to a 57-round one-block preimage without padding and a 57-round two-block preimage with padding, out of 80 rounds for the full function. In this work, we exploit further the differential view of meet-in-the-middle techniques and generalize it to higher-order differentials. Despite being an important technique dating from the mid-90's, this is the first time higher-order differentials have been applied to meet-in-the-middle preimages. We show that doing so may lead to significant improvements to preimage attacks on hash functions with a simple linear message expansion. We extend the number of attacked rounds on SHA-1 to give a 62-round one-block preimage without padding, a 56-round one-block preimage with padding, and a 62-round two-block preimage with padding. We also apply our framework to the more recent SHA-3 finalist BLAKE and its newer variant BLAKE2, and give an attack for a 2.75-round preimage with padding, and a 7.5-round pseudo-preimage on the compression function.

Time-lock puzzles, introduced by May, Rivest, Shamir and Wagner, is a mechanism for sending messages ``to the future''. A sender can quickly generate a puzzle with a solution $s$ that remains hidden until a moderately large amount of time $t$ has elapsed. The solution $s$ should be hidden from any adversary that runs in time significantly less than $t$, including resourceful parallel adversaries with polynomially many processors. While the notion of time-lock puzzles has been around for 22 years, there has only been a *single* candidate proposed. Fifteen years ago, Rivest, Shamir and Wagner suggested a beautiful candidate time-lock puzzle based on the assumption that exponentiation modulo an RSA integer is an ``inherently sequential'' computation. We show that various flavors of {\em randomized encodings} give rise to time-lock puzzles of varying strengths, whose security can be shown assuming *the existence* of non-parallelizing languages, which are languages that require circuits of depth at least $t$ to decide, in the worst-case. The existence of such languages is necessary for the existence of time-lock puzzles. We instantiate the construction with different randomized encodings from the literature, where increasingly better efficiency is obtained based on increasingly stronger cryptographic assumptions, ranging from one-way functions to indistinguishability obfuscation. We also observe that time-lock puzzles imply one-way functions, and thus the reliance on some cryptographic assumption is necessary. Finally, generalizing the above, we construct other types of puzzles such as *proofs of work* from randomized encodings and a suitable worst-case hardness assumption (that is necessary for such puzzles to exist).

The Number Field Sieve (NFS) algorithm is the best known method to compute discrete logarithms (DL) in finite fields $\mathbb{F}_{p^n}$, with $p$ medium to large and $n \geq 1$ small. This algorithm comprises four steps: polynomial selection, relation collection, linear algebra and finally, individual logarithm computation. The first step outputs two polynomials defining two number fields, and a map from the polynomial ring over the integers modulo each of these polynomials to $\mathbb{F}_{p^n}$. After the relation collection and linear algebra phases, the (virtual) logarithm of a subset of elements in each number field is known. Given the target element in $\mathbb{F}_{p^n}$, the fourth step computes a preimage in one number field. If one can write the target preimage as a product of elements of known (virtual) logarithm, then one can deduce the discrete logarithm of the target. As recently shown by the Logjam attack, this final step can be critical when it can be computed very quickly. But we realized that computing an individual DL is much slower in medium- and large-characteristic non-prime fields $\mathbb{F}_{p^n}$ with $n \geq 3$, compared to prime fields and quadratic fields $\mathbb{F}_{p^2}$. We optimize the first part of individual DL: the \emph{booting step}, by reducing dramatically the size of the preimage norm. Its smoothness probability is higher, hence the running-time of the booting step is much improved. Our method is very efficient for small extension fields with $2 \leq n \leq 6$ and applies to any $n > 1$, in medium and large characteristic.

In this paper we detail techniques that can be used to analyze and attack an AES implementation on an FPGA from the primary (i.e., external) side of a switched-mode power supply. Our attack only requires measurements of the duty cycle of the power supply, and then increases the signal-to-noise ratio (SNR) though averaging, deconvolution and wavelet based detrending. The result is an exploitable source of leakage that allows a secret key to be determined from low-frequency power measurements. The techniques and procedures provide a general approach to performing differential power analysis (DPA) from a single point of information for any single hypothesized intermediate value, suggesting their potential for improving other types of side-channel analysis.

Side channel collision attacks are a powerful method to exploit side channel leakage. Otherwise than a few exceptions, collision attacks usually combine leakage from distinct points in time, making them inherently bivariate. This work introduces the notion of near collisions to exploit the fact that values depending on the same sub-key can have similar while not identical leakage. We show how such knowledge can be exploited to mount a key recovery attack. The presented approach has several desirable features when compared to other state-of-the-art collision attacks: Near collision attacks are truly univariate. They have low requirements on the leakage functions, since they work well for leakages that are linear in the bits of the targeted intermediate state. They are applicable in the presence of masking countermeasures if there exist distinguishable leakages, as in the case of leakage squeezing. Results are backed up by a broad range of simulations for unprotected and masked implementations, as well as an analysis of the measurement set provided by DPA Contest v4.

Plaintext is mixed with AI-generated dis-information which binds the cryptanalyst to an irreducible set of mutually exclusive plausible plaintext candidates. As impractical as Vernam "One Time Pad" cipher has been, it's security strategy: equivocation is fundamentally superior to the prevailing strategy: intractability. Intractability erodes, equivocation endures. Alas, Vernam was an overkill. Equivocation works even if only a few plaintext candidates are left as an irreducible set, which is what Equivoe-T offers. The AI engine builds decoys off the plaintext such that each decoy has a counter-meaning, or at least an off-meaning per the guarded plaintext, while claiming at least threshold plausibility to “pump” entropy into the irreducible field of plaintext candidates. Equivoe-T uses a complete transposition algorithm that guarantees the existence of a key that matches any two arbitrarily selected permutations of the n transposed elements. Therefore every decoy qualifies as a plaintext. The transposed elements may be words, letters, a mix, or otherwise. n can be selected to add intractability to the built-in equivocation since the key space grows fast (|Ktransposition| = n!).

An alleged theorem of Neven, Smart and Warinschi (NSW) about the security of Schnorr signatures seems to have a flaw described in this report. Schnorr signatures require representation of an element in a discrete logarithm group as a hashable bit string. This report describes a defective bit string representation of elliptic curve points. Schnorr signatures are insecure when used with this defective representation. Nevertheless, the defective representation meets all the conditions of the NSW theorem. Of course, a natural representation of an elliptic curve group element would not suffer from this major defect. So, the NSW theorem can probably be fixed.

Differential Fault Attack (DFA) has received serious attention in cryptographic literature and very recently such attacks have been mounted against several popular stream ciphers for example Grain v1, MICKEY 2.0 and Trivium, that are parts of the eStream hardware profile. The basic idea of the fault attacks consider injection of faults and the most general set-up should consider faults at random location and random time. Then one should identify the exact location and the exact timing of the fault (as well as multi bit faults) with the help of fault signatures. In this paper we consider this most general set-up and solve the problem of fault attack under a general framework, where probabilistic signatures are exploited. Our ideas subsume all the existing DFAs against the Grain family, MICKEY 2.0 and Trivium. In the process we provide improved fault attacks for all the versions of Grain family and also for MICKEY 2.0 (the attacks against Trivium are already quite optimal and thus there is not much scope to improve). Our generalized method can also take care of the cases where certain parts of the keystream bits are missing for authentication purpose. In particular, we show that the unsolved problem of identifying the faults in random time for Grain 128a can be solved in this manner. Our techniques can easily be applied to mount fault attack on any stream cipher of similar kind.

We consider the problem of recovering the internal specification of a general SP-network consisting of three linear layers (A) interleaved with two Sbox layers (S) (denoted by ASASA for short), given only black-box access to the scheme. The decomposition of such general ASASA schemes was first considered at ASIACRYPT 2014 by Biryukov et al. which used the alleged difficulty of this problem to propose several concrete block cipher designs as candidates for white-box cryptography. In this paper, we present several attacks on general ASASA schemes that significantly outperform the analysis of Biryukov et al. As a result, we are able to break all the proposed concrete ASASA constructions with practical complexity. For example, we can decompose an ASASA structure that was supposed to provide $64$-bit security in roughly $2^{28}$ steps, and break the scheme that supposedly provides $128$-bit security in about $2^{41}$ time. Whenever possible, our findings are backed up with experimental verifications.

Differential power analysis (DPA) is a side-channel attack in which an adversary retrieves cryptographic material by measuring and analyzing the power consumption of the device on which the cryptographic algorithm under attack executes. An effective countermeasure against DPA is to mask secrets by probabilistically encoding them over a set of shares, and to run masked algorithms that compute on these encodings. Masked algorithms are often expected to provide, at least, a certain level of probing security. Leveraging the deep connections between probabilistic information flow and probing security, we develop a precise, scalable, and fully automated methodology to verify the probing security of masked algorithms, and generate them from unprotected descriptions of the algorithm. Our methodology relies on several contributions of independent interest, including a stronger notion of probing security that supports compositional reasoning, and a type system for enforcing an expressive class of probing policies. Finally, we validate our methodology on examples that go significantly beyond the state-of-the-art.

The security of pairing-based crypto-systems relies on the difficulty to compute discrete logarithms in finite fields GF(p^n) where n is a small integer larger than 1. The state-of-art algorithm is the number field sieve (NFS) together with its many variants. When p has a special form (SNFS), as in many pairings constructions, NFS has a faster variant due to Joux and Pierrot. We present a new NFS variant for SNFS computations, which is better for some cryptographically relevant cases, according to a precise comparison of norm sizes. The new algorithm is an adaptation of Schirokauer's variant of NFS based on tower extensions, for which we give a middlebrow presentation.

We introduce and study the iterated random permutation problem, which asks how hard it is to distinguish, in a black-box way, the r-th power of a random permutation from a uniformly random permutation of a set of size N. We show that this requires Omega(N) queries (even for a two-sided, adaptive adversary). As a direct application of this result, we show that cascading a block cipher with the same key cannot degrade its security (as a pseudorandom permutation) more than negligibly.

The Norwegian government ran trials of internet remote voting during the 2011 municipal elections and the 2013 parliamentary elections. From a simplified version of the voting protocol used there, the essential cryptographic operations of the voting protocol has been put together into a cryptosystem in which one can build the voting protocol on top of. This paper proposes a new instantiation of the underlying cryp- tosystem, improving our confidence in the security of the cryptosys- tem. The new instantiation is mostly similar to a previously defined instantiation, but allows parts of the security proof to be significantly improved.

Current cryptocurrencies, starting with Bitcoin, build a decentralized blockchain based transaction ledger, maintained through proofs-of-work that also serve to generate a monetary supply. Such decentralization has benefits, such as independence from national political control, but also significant limitations in terms of computational costs and scalability. We introduce RSCoin, a cryptocurrency framework in which central banks maintain complete control over the monetary supply, but rely on a distributed set of authorities, or mintettes, to prevent double-spending. While monetary policy is centralized, RSCoin still provides strong transparency and auditability guarantees. We demonstrate, both theoretically and experimentally, the benefits of a modest degree of centralization, such as the elimination of wasteful hashing and a scalable system for avoiding double-spending attacks.

We reconsider the concept of two-prover (and more generally: multi-prover) commitments, as introduced in the late eighties in the seminal work by Ben-Or et al. As was recently shown by Crëpeau et al., the security of known two-prover commitment schemes not only relies on the explicit assumption that the two provers cannot communicate, but also depends on what their information processing capabilities are. For instance, there exist schemes that are secure against classical provers but insecure if the provers have quantum information processing capabilities, and there are schemes that resist such quantum attacks but become insecure when considering general so-called non-signaling provers, which are restricted solely by the requirement that no communication takes place. This poses the natural question whether there exists a two-prover commitment scheme that is secure under the sole assumption that no communication takes place, and that does not rely on any further restriction of the information processing capabilities of the dishonest provers; no such scheme is known. In this work, we give strong evidence for a negative answer: we show that any single-round two-prover commitment scheme can be broken by a non-signaling attack. Our negative result is as bad as it can get: for any candidate scheme that is (almost) perfectly hiding, there exists a strategy that allows the dishonest provers to open a commitment to an arbitrary bit (almost) as successfully as the honest provers can open an honestly prepared commitment, i.e., with probability (almost) $1$ in case of a perfectly sound scheme. In the case of multi-round schemes, our impossibility result is restricted to perfectly hiding schemes. On the positive side, we show that the impossibility result can be circumvented by considering {\em three} provers instead: there exists a three-prover commitment scheme that is secure against arbitrary non-signaling attacks.

Fault injection has become over the years one of the most dangerous threats for embedded devices such as smartcards. It is thus mandatory for any embedded system to implement efficient protections against this hazard. Among the various countermeasures suggested so far, the idea of infective computation seems fascinating, probably due to its aggressive strategy. Originally conceived to protect asymmetric cryptosystems, infective computation has been recently adapted to symmetric systems. This paper investigates the security of a new symmetric infective countermeasure suggested at CHES 2014. By noticing that the number of executed rounds is not protected, we develop four different attacks allowing one to efficiently recover the secret key of the underlying cryptosystem by using any of the three most popular fault models used in literature.

We describe a new technique for conducting ``partitioning arguments''. Partitioning arguments are a popular way to prove the security of a cryptographic scheme. For instance, to prove the security of a signature scheme, a partitioning argument could divide the set of messages into ``signable'' messages for which a signature can be simulated during the proof, and ``unsignable'' ones for which any signature would allow to solve a computational problem. During the security proof, we would then hope that an adversary only requests signatures for signable messages, and later forges a signature for an unsignable one. In this work, we develop a new class of partitioning arguments from simple assumptions. Unlike previous partitioning strategies, ours is based upon an algebraic property of the partitioned elements (e.g., the signed messages), and not on their bit structure. This allows to perform the partitioning efficiently in a ``hidden'' way, such that already a single ``slot'' for a partitioning operation in the scheme can be used to implement many different partitionings sequentially, one after the other. As a consequence, we can construct complex partitionings out of simple basic (but algebraic) partitionings in a very space-efficient way. As a demonstration of our technique, we provide the first signature and public-key encryption schemes that achieve the following properties simultaneously: they are (almost) tightly secure under a simple assumption, and they are fully compact (in the sense that parameters, keys, and signatures, resp.~ciphertexts only comprise a constant number of group elements).

By selecting the largest possible value of k∈(n/2,2n/3], we further reduce the AND and XOR gate complexities of the CRT-based hybrid parallel GF(2^n) polynomial basis multipliers for the irreducible trinomial f = u^n + u^k + 1 over GF(2): they are always less than those of the current fastest parallel multipliers – quadratic multipliers, i.e., n^2 AND gates and n^2-1 XOR gates. Our experimental results show that among the 539 values of n∈[5,999] such that f is irreducible for some k∈[2,n-2], there are 317 values of n such that k∈(n/2,2n/3]. For these irreducible trinomials, the AND and XOR gate complexities of the CRT-based hybrid multipliers are reduced by 15.3% on average. Especially, for the 124 values of such n, the two kinds of multipliers have the same time complexity, but the space complexities are reduced by 15.5% on average. As a comparison, the previous CRT-based multipliers consider the case k∈[2,n/2], and the improvement rate is only 8.4% on average.

We describe a zero-knowledge proof system in which a prover holds a large dataset $M$ and can repeatedly prove NP relations about that dataset. That is, for any (public) relation $R$ and $x$, the prover can prove that $\exists w: R(M,x,w)=1$. After an initial setup phase (which depends only on $M$), each proof requires only a constant number of rounds and has communication/computation cost proportional to that of a {\em random-access machine (RAM)} implementation of $R$, up to polylogarithmic factors. In particular, the cost per proof in many applications is sublinear in $|M|$. Additionally, the storage requirement between proofs for the verifier is constant.

Large-scale datasets of consumer behavior might revolutionize the way we gain competitive advantages and increase our knowledge in the respective domains. At the same time, valuable datasets pose potential privacy risks that are difficult to foresee. In this paper we study the impact that the prices from consumers’ purchase histories have on the consumers’ location privacy. We show that using a small set of low-priced product prices from the consumers’ purchase histories, an adversary can determine the country, city, and local retail store where the transaction occurred with high confidence. Our paper demonstrates that even when the product category, precise time of purchase, and currency are removed from the consumers’ purchase history (e.g., for privacy reasons), information about the consumers’ location is leaked. The results are based on three independent datasets containing thousands of low-priced and frequently-bought consumer products. In addition, we show how to identify the local currency, given only the total price of a consumer purchase in a global currency (e.g., in Bitcoin). The results show the existence of location privacy risks when releasing consumer purchase histories. As such, the results highlight the need for systems that hide transaction details in consumer purchase histories.

In this paper we investigate univariate algebraic attacks on filter generators over extension fields $F_q=F_{2^n}$ with focus on the Welch-Gong (WG) family of stream ciphers. Our main contribution is to break WG-5, WG-7, WG-8 and WG-16 by combining results on the so-called spectral immunity (minimum distance of certain cyclic codes) with properties of the WG type stream cipher construction. The spectral immunity is the univariate analog of algebraic immunity and instead of measuring degree of multiples of a multivariate polynomial, it measures the minimum number of nonzero coefficients of a multiple of a univariate polynomial. Based on the structure of the general WG-construction, we deduce better bounds for the spectral immunity and the univariate analog of algebraic attacks.

In this paper, we study the security of two hash function families LSH and SHA-V. We find that the wide-pipe MD structural LSH hash functions do not apply the traditional feeding forward operation. This structural feature enables us to launch free-start collision and pseudo-preimage attacks on full-round LSH hash functions with negligible complexities. We think the existence of these attacks is inappropriate for LSH although they does not challenge its overall security levels. We also evaluate the strength of the LSH round function by launching 14-round boomerang attacks on LSH-512 and LSH-256 hash functions with complexities $2^{308}$ and $2^{242}$ respectively. We verify the correctness of our boomerang attacks by giving practical 11-round boomerang quartets. These boomerang results indicate that the round functions of LSH are well designed. Based on our analysis, we recommend LSH to adopt the feeding forward operation regardless of its well designed round function. The PMD structural SHA-V parallelizes two SHA-1-like streams and each stream processes independent 512-bit message blocks. This structure enable us to utilize the divide-and-conquer strategy to find preimages and collisions. Our preimage attack can be applied to full-round SHA-V with time \& memory complexities $O(2^{80})$. Our trivial collision attacks also requires $O(2^{80})$ complexities but, utilizing existing results on SHA-1, we can find a SHA-V collision with a time complexity $O(2^{61})$ and a negligible memory complexity. These results indicate that there are weaknesses in both the structure and the round function of SHA-V.

Infective countermeasures have been a promising class of fault attack countermeasures. However, they have been subjected to several attacks owing to lack of formal proofs of security and improper implementations. In this paper, we first provide a formal information theoretic proof of security for one of the most recently proposed infective countermeasures against DFA, under the assumption that the adversary does not change the flow sequence or skip any instruction. Subsequently, we identify weaknesses in the infection mechanism of the countermeasure that could be exploited by attacks which change the flow sequence. We propose suitable randomizations to reduce the success probabilities of such attacks. Furthermore, we develop a fault tolerant implementation of the countermeasure using the x86 instruction set to make such attacks which attempt to change the control flow of the algorithm practically infeasible. All the claims have been validated by supporting simulations and real life experiments on a SASEBO-W platform. We also compare the performance and security provided by the proposed countermeasure against that provided by the existing scheme.

In this paper, we evaluate the performances of state-of-the-art higher-order masking schemes for the AES. Doing so, we pay a particular attention to the comparison between specialized solutions introduced exclusively as countermeasures against side-channel analysis, and a recent proposal by Roche and Prouff exploiting MultiParty Computation (MPC) techniques. We show that the additional security features this latter scheme provides (e.g. its glitch-freeness) comes at the cost of large performance overheads. We then study how exploiting standard optimization techniques from the MPC literature can be used to reduce this gap. In particular, we show that ``packed secret sharing" based on a modified multiplication algorithm can speed up MPC-based masking when the order of the masking scheme increases. Eventually, we discuss the randomness requirements of masked implementations. For this purpose, we first show with information theoretic arguments that the security guarantees of masking are only preserved if this randomness is uniform, and analyze the consequences of a deviation from this requirement. We then conclude the paper by including the cost of randomness generation in our performance evaluations. These results should help actual designers to choose a masking scheme based on security and performance~constraints.

In this work we define multiple relaxations to the definition of correctness in secure obfuscation. While still remaining meaningful, these relaxations provide ways to obfuscate many primitives in a more direct and efficient way. In particular, we first show how to construct a secure obfuscator for the re-encryption primitive from the Decisional Learning with Errors (DLWE) assumption, without going through fully homomorphic encryption. This can be viewed as a meaningful way to trade correctness for efficiency. Next, we show how our tools can be used to construct secure obfuscators for the functional re-encryption and multi-hop unidirectional re-encryption primitives. In the former case, we improve upon the efficiency of the only previously known construction that satisfies the stronger notion of collusion-resistant obfuscation (due to Chandran et al. - TCC 2012) and obtain a construction with input ciphertexts of constant length. In the latter case, we provide the first known obfuscation-based definition and construction; additionally, our scheme is the first scheme where the size of the ciphertexts does not grow with every hop.

In 2012, Wen and Li proposed a secure and robust dynamic identity based remote user authentication scheme with key agreement using smart cards. They claimed that their scheme is efficient and secure. But in this paper, we demonstrate that their scheme is completely insecure and vulnerable to various known attacks like offline and online password guessing attack, impersonation attack, server masquerading attack, denial of service attack and an insider attack. Also we point out that there are loopholes in password change phase and online secret renew phase which leads to the desynchronization between user and the server and even the legitimate user is rejected by the server. In addition, an adversary can easily generate the common session key of further transmission between user and the server. Thus the entire system collapses and authors claims are proven to be wrong and their scheme will not be secure and efficient for practical purpose.

We describe the design, implementation, and evaluation of Popcorn, a media delivery system that hides clients' consumption (even from the content distributor). Popcorn relies on a powerful cryptographic primitive: private information retrieval (PIR). With novel refinements that leverage the properties of PIR protocols and media streaming, Popcorn scales to the size of Netflix's library (8000 movies) and respects current controls on media dissemination. The dollar cost to serve a media object in Popcorn is 3.87 times that of a non-private system.

In this work, we study the intrinsic complexity of black-box Universally Composable (UC) secure computation based on general assumptions. We present a thorough study in various corruption modelings while focusing on achieving security in the common reference string (CRS) model. Our results involve the following: 1. Static UC secure computation. Designing the first static UC oblivious transfer protocol based on public-key encryption and stand-alone semi-honest oblivious transfer. As a corollary we obtain the first black-box constructions of UC secure computation assuming only two-round semi-honest oblivious transfer. 2. One-sided UC secure computation. Designing adaptive UC two-party computation with single corruptions assuming public-key encryption with oblivious ciphertext generation. 3. Adaptive UC secure computation. Designing adaptively secure UC commitment scheme assuming only public-key encryption with oblivious ciphertext generation. As a corollary we obtain the first black-box constructions of adaptive UC secure computation assuming only (trapdoor) simulatable public-key encryption (as well as a variety of concrete assumptions). We remark that such a result was not known even under non-black-box constructions.

This paper addresses the fundamental question of whether or not different, exciting primitives now being considered actually exist. We show that we, unfortunately, cannot have them all. We provide results of the form not(A) OR not(B), meaning one of the primitives A,B cannot exist. (But we don't know which.) Specifically, we show that: (1) VGBO (Virtual Grey Box Obfuscation) for all circuits, which has been conjectured to be achieved by candidate constructions, cannot co-exist with Canetti's 1997 AI-DHI (auxiliary input DH inversion) assumption, which has been used to achieve many goals including point-function obfuscation (2) iO (indistinguishability obfuscation) for all circuits cannot co-exist with KM-LR-SE (key-message leakage-resilient symmetric encryption) (3) iO cannot co-exist with hash functions that are UCE secure for computationally unpredictable split sources.

We present DECIM, an approach to solve the challenge of detecting endpoint compromise in messaging. DECIM manages and refreshes encryption/decryption keys in an automatic and transparent way: it makes it necessary for uses of the key to be inserted in an append-only log, which the device owner can interrogate in order to detect misuse. We propose a multi-device messaging protocol that exploits our concept to allow users to detect unauthorised usage of their device keys. It is co-designed with a formal model, and we verify its core security property using the Tamarin prover. We present a proof-of-concept implementation providing the main features required for deployment. We find that DECIM messaging is efficient even for millions of users. The methods we introduce are not intended to replace existing methods used to keep keys safe (such as hardware devices, careful procedures, or key refreshment techniques). Rather, our methods provide a useful and effective additional layer of security.

CAESAR has caused a heated discussion regarding the merits of one-pass encryption and online ciphers. The latter is a keyed, length preserving function which outputs ciphertext blocks as soon as the respective plaintext block is available as input. The immediacy of an online cipher affords a clear performance advantage, but it comes at a price: ciphertext blocks cannot depend on later plaintext blocks, limiting diffusion and hence security. We show how one can attain the best of both worlds by providing provably secure constructions, achieving full cipher security, based on applications of an online cipher around blockwise reordering layers. Explicitly, we show that with just two calls to the online cipher, prp security up to the birthday bound is both attainable and maximal. Moreover, we demonstrate that three calls to the online cipher suffice to obtain beyond birthday bound security. We provide a full proof of this for a prp construction, and, in the ±prp setting, security against adversaries who make queries of any single length. As part of our investigation, we extend an observation by Rogaway and Zhang by further highlighting the close relationship between online ciphers and tweakable blockciphers with variable-length tweaks.

This paper focuses on a surprising class of cryptanalysis results for symmetric-key primitives: when the number of rounds of the primitive is increased, the complexity of the cryptanalysis result decreases. Our primary target will be primitives that consist of identical round functions, such as PBKDF1, the Unix password hashing algorithm, and the Chaskey MAC function. However, some of our results also apply to constructions with non-identical rounds, such as the PRIDE block cipher. First, we construct distinguishers for which the data complexity decreases when the number of rounds is increased. They are based on two well-known observations: iterating a random permutation increases the expected number of fixed points, and iterating a random function decreases the expected number of image points. We explain that these effects also apply to components of cryptographic primitives, such as a round of a block cipher. Second, we introduce a class of key-recovery and preimage-finding techniques that correspond to exhaustive search, however on a smaller part (e.g. one round) of the primitive. As the time complexity of a cryptanalysis result is usually measured by the number of full-round evaluations of the primitive, increasing the number of rounds will lower the time complexity. None of the observations in this paper result in more than a small speed-up over exhaustive search. Therefore, for lightweight applications, implementation advantages may outweigh the presence of these observations.

The Rényi divergence is a measure of closeness of two probability distributions. We show that it can often be used as an alternative to the statistical distance in security proofs for lattice-based cryptography. Using the Rényi divergence is particularly suited for security proofs of primitives in which the attacker is required to solve a search problem (e.g., forging a signature). We show that it may also be used in the case of distinguishing problems (e.g., semantic security of encryption schemes), when they enjoy a public sampleability property. The techniques lead to security proofs for schemes with smaller parameters, and sometimes to simpler security proofs than the existing ones.

Time-lock encryption is a method to encrypt a message such that it can only be decrypted after a certain deadline has passed. We propose a novel time-lock encryption scheme, whose main advantage over prior constructions is that even receivers with relatively weak computational resources should immediately be able to decrypt after the deadline, without any interaction with the sender, other receivers, or a trusted third party. We build our time-lock encryption on top of the new concept of computational reference clocks and an extractable witness encryption scheme. We explain how to construct a computational reference clock based on Bitcoin. We show how to achieve constant level of multilinearity for witness encryption by using SNARKs. We propose a new construction of a witness encryption scheme which is of independent interest: our scheme, based on Subset-Sum, achieves extractable security without relying on obfuscation. The scheme employs multilinear maps of arbitrary order and is independent of the implementations of multilinear maps.

Lightweight cryptography is a rapidly evolving area of research and it has great impact especially on the new computing environment called the Internet of Things (IoT) or the Smart Object networks (Holler et al., 2014), where lots of constrained devices are connected on the Internet and exchange information on a daily basis. Every year there are many new submissions of cryptographic primitives which are optimized towards both software and hardware implementation so that they can operate in devices which have limited resources of hardware and are subject to both power and energy consumption constraints. In 2013, two families of ultra-lightweight block ciphers were proposed, SIMON and SPECK, which come in a variety of block and key sizes and were designed to be optimized in hardware and software implementation respectively (Beaulieu et al., 2013). In this paper, we study the security of the 64-bit SIMON with 128-bit key against advanced forms of differential cryptanalysis using truncated differentials (Knudsen, 1995; Courtois et al., 2014a). We follow similar method as the one proposed in SECRYPT 2013 (Courtois and Mourouzis, 2013) in order to heuristically discover sets of differences that propagate with sufficiently good probability and allow us to combine them efficiently in order to construct large-round statistical distinguishers. We present a 22-round distinguisher which we use it in a depth-first key search approach to develop an attack against 24 and 26 rounds with complexity 2^{124.5} and 2^{126} SIMON encryptions respectively. Our methodology provides a framework for extending distinguishers to attacks to a larger number of rounds assuming truncated differential properties of relatively high probability were discovered.

Verifiable computation allows a client to outsource computations to a worker with a cryptographic proof of correctness of the result that can be verified faster than performing the computation. Recently, the Pinocchio system achieved faster verification than computation in practice for the first time. Unfortunately, Pinocchio and other efficient verifiable computation systems require the client to disclose the inputs to the worker, which is undesirable for sensitive inputs. To solve this problem, we propose Trinocchio: a system that distributes Pinocchio to three (or more) workers, that each individually do not learn which inputs they are computing on. We fully exploit the almost linear structure of Pinochhio proofs, letting each worker essentially perform the work for a single Pinocchio proof; verification by the client remains the same. Moreover, we extend Trinocchio to enable joint computation with multiple mutually distrusting inputters and outputters and still very fast verification. We show the feasibility of our approach by analysing the performance of an implementation in a case study.

We solve an open question in code-based cryptography by introducing the first provably secure group signature scheme from code-based assumptions. Specifically, the scheme satisfies the CPA-anonymity and traceability requirements in the random oracle model, assuming the hardness of the McEliece problem, the Learning Parity with Noise problem, and a variant of the Syndrome Decoding problem. Our construction produces smaller key and signature sizes than the existing post-quantum group signature schemes from lattices, as long as the cardinality of the underlying group does not exceed the population of the Netherlands ($\approx 2^{24}$ users). The feasibility of the scheme is supported by implementation results. Additionally, the techniques introduced in this work might be of independent interest: a new verifiable encryption protocol for the randomized McEliece encryption and a new approach to design formal security reductions from the Syndrome Decoding problem.

This paper was merged with a work by Jia Liu, Saqib A. Kakvi, and Bogdan Warinschi. See https://eprint.iacr.org/2015/482.

GCM is used in a vast amount of security protocols and is quickly becoming the de facto mode of operation for block ciphers due to its exceptional performance. In this paper we analyze the NIST stan- dardized version (SP 800-38D) of GCM, and in particular the use of short tag lengths. We show that feedback of successful or unsuccessful forgery attempt is almost always possible, contradicting the NIST assumptions for short tags. We also provide a complexity estimation of Ferguson’s authentication key recovery method on short tags, and suggest several novel improvements to Fergusons’s attacks that significantly reduce the security level for short tags. We show that for many truncated tag sizes; the security levels are far below, not only the current NIST requirement of 112-bit security, but also the old NIST requirement of 80-bit security. We therefore strongly recommend NIST to revise SP 800-38D.

We present XPX, a tweakable blockcipher based on a single permutation P. On input of a tweak (t_{11},t_{12},t_{21},t_{22}) in T and a message m, it outputs ciphertext c=P(m xor Delta_1) xor Delta_2, where Delta_1=t_{11}k xor t_{12}P(k) and Delta_2=t_{21}k xor t_{22}P(k). Here, the tweak space T is required to satisfy a certain set of trivial conditions (such as (0,0,0,0) not in T). We prove that XPX with any such tweak space is a strong tweakable pseudorandom permutation. Next, we consider the security of XPX under related-key attacks, where the adversary can freely select a key-deriving function upon every evaluation. We prove that XPX achieves various levels of related-key security, depending on the set of key-deriving functions and the properties of T. For instance, if t_{12},t_{22} neq 0 and (t_{21},t_{22}) neq (0,1) for all tweaks, XPX is XOR-related-key secure. XPX generalizes Even-Mansour (EM), but also Rogaway's XEX based on EM, and various other tweakable blockciphers. As such, XPX finds a wide range of applications. We show how our results on XPX directly imply related-key security of the authenticated encryption schemes Prøst-COPA and Minalpher, and how a straightforward adjustment to the MAC function Chaskey and to keyed Sponges makes them provably related-key secure.

A covering system of congruences can be defined as a set of congruence relations of the form: $\{r_1 \pmod{m_1}, r_2 \pmod{m_2}, \dots, r_t \pmod{m_t}\}$ for $m_1, \dots, m_t \in \N$ satisfying the property that for every integer $k$ in $\Z$, there exists at least an index $i \in \{1, \dots, t\}$ such that $k \equiv r_i \pmod{m_i}$. First, we show that most existing scalar multiplication algorithms can be formulated in terms of covering systems of congruences. Then, using a special form of covering systems called exact $n$-covers, we present a novel uniformly randomized scalar multiplication algorithm that may be used to counter differential side-channel attacks, and more generally physical attacks that require multiple executions of the algorithm. This algorithm can be an alternative to Coron's scalar blinding technique for elliptic curves, in particular when the choice of a particular finite field tailored for speed compels to use a large random factor.

Gentry’s bootstrapping technique is the most famous method of obtaining fully homomorphic encryption. In this paper I propose a new fully homomorphic encryption scheme on non-associative octonion ring over finite field without bootstrapping technique. The security of the proposed fully homomorphic encryption scheme is based on computational difficulty to solve the multivariate algebraic equations of high degree while the almost all multivariate cryptosystems proposed until now are based on the quadratic equations avoiding the explosion of the coefficients. Because proposed fully homomorphic encryption scheme is based on multivariate algebraic equations with high degree or too many variables, it is against the Gröbner basis attack, the differential attack, rank attack and so on. The key size of this system and complexity for enciphering/deciphering become to be small enough to handle.

Block cipher is in vogue due to its requirement for integrity, confidentiality and authentication. Differential and Linear cryptanalysis are the basic techniques on block cipher and till today many cryptanalytic attacks are developed based on these. Each variant of these have different methods to find distinguisher and based on the distinguisher, the method to recover key. This paper illustrates the steps to find distinguisher and steps to recover key of all variants of differential and linear attacks developed till today. This is advantageous to cryptanalyst and cryptographer to apply various attacks simultaneously on any crypto algorithm.

We present a unified view of the two-party and multi-party computation protocols based on oblivious transfer first outlined in Nielsen \emph{et al.} (CRYPTO 2012) and Larraia et al. (CRYPTO 2014). We present a number of modifications and improvements to these earlier presentations, as well as full proofs of the entire protocol. Improvements include a unified pre-processing and online MAC methodology, mechanisms to pass between different MAC variants, and fixing a minor bug in the protocol of Larraia \emph{et al.}~in relation to a selective failure attack. It also fixes a minor bug in Nielsen \emph{et al.} resulting from using Jensen's inequality in the wrong direction in an analysis.

Physical Unclonable Functions (PUFs), as novel lightweight hardware security primitives, provide a higher level security with lower power and area overhead in comparison with traditional cryptographic solutions. However, it has been demonstrated that PUFs are vulnerable to model building attacks, especially those using linear additive functions such as Arbiter PUF (APUF) and k-sum PUF as building units. Nevertheless, both APUFs and k-sum PUFs are highly desirable security primitives, especially for authentication, because they are capable of producing a huge number of challenge response pairs (CRPs) and can be easily integrated into silicon. In this paper, we actually rely on the demonstrated vulnerability of PUFs to model building attacks as well as the relative ease with which this can be achieved to develop a new parameter-based authentication protocol based on obfuscating challenges sent to PUFs and their subsequent recovery. We show, using statistical analysis and model building attacks using published approaches, that constructing a model using machine learning techniques are infeasible when our proposed method is employed. Finally, we also demonstrate that our challenge obfuscation and recovery method can be successfully used for secure key exchange between two parties.

In the public-key setting, known constructions of function-private functional encryption (FPFE) were limited to very restricted classes of functionalities like inner-product [Agrawal et al. - PKC 2015]. Moreover, its power has not been well investigated. In this paper, we construct FPFE for general functions and explore its powerful applications (both for general functions and for specific efficient instantiations). As warmup, we construct from FPFE a natural generalization of a signature scheme endowed with functional properties, that we call functional anonymous signature (FAS) scheme. In a FAS, Alice can sign a circuit $C$ chosen from some distribution $D$ to get a signature $\sigma$ and can publish a verification key that allows anybody holding a message $m$ to verify that (1) $\sigma$ is a valid signature of Alice for some (possibly unknown to him) circuit $C$ and (2) $C(m)=1$. Beyond unforgeability the security of FAS guarantees that the signature $\sigma$ hide as much information as possible about $C$ except what can be inferred from knowledge of $D$. Then, we show that FPFE can be used to construct in a black-box way functional encryption schemes for randomized functionalities (RFE). Previous constructions of (public-key) RFE relied on iO [Goyal et al. - TCC 2015]. As further application, we show that efficient instantiations of FPFE can be used to achieve adaptively-secure CNF/DNF encryption for bounded degree formulae (BoolEnc). Though it was known how to implement BoolEnc from inner-product encryption [Katz et al. - EUROCRYPT 2008], as already observed by Katz et al. this reduction only works for selective security and completely breaks down for adaptive security. For this application we only need weak assumptions and the resulting adaptively-secure BoolEnc scheme is efficient. Finally, we present a general picture of the relations among all these related primitives. One key observation is that Attribute-based Encryption with function privacy implies FE, a notable fact that sheds light on the importance of the function privacy property for FE.

We describe a new methodology that enables the di- rect execution of multi-threaded applications inside of Shadow, an existing parallel discrete-event network sim- ulation framework. Our methodology utilizes function interposition and an application-layer thread library to emulate the ordinary thread interface to the application. Using this methodology, we implement a new Shadow plug-in that directly executes the Bitcoin reference client software. We describe optimizations that enable scalable execution of thousands of Bitcoin nodes on a single ma- chine, and discuss how to model the Bitcoin network for experimental purposes. Finally, we present novel denial- of-service attacks against the Bitcoin software, which exploit low-level implementation artifacts in the Bitcoin reference client. We demonstrate these attacks using our methodology, tools, and models.

We present a new fully homomorphic encryption (FHE) scheme that is efficient for practical applications. The main feature of our scheme is that noise reduction considered essential in current FHE schemes, such as boot strapping and modulus switching, is not needed in our scheme, because it allows arbitrarily large noises in its ciphertexts. A ciphertext in our scheme is a vector with its dimension specified as a security parameter of the encryption key. The dimension of ciphertexts does not change with homomorphic operations and all ciphertext elements are in a finite domain, so our scheme is compact. In addition, our scheme can directly encrypt big integers, rather than only bit messages. We proved the hardness of recovering encryption keys from any number of ciphertexts with chosen plaintexts and then the semantic security of our scheme. The hardness of recovering keys from ciphertexts is based on the approximate greatest common divisors problem. We implemented a prototype of our scheme and evaluated its concrete performance extensively from the aspects of encryption, decryption, homomorphic operations, and bitwise operators over ciphertexts. The efficiency of our scheme is confirmed by the evaluation result.

We present an oblivious machine, a concrete notion for a multiparty random access machine (RAM) computation and a toolchain to allow the efficient execution of general programs written in a subset of C that allows RAM-model computation over the integers. The machine only leaks the list of possible instructions and the running time. Our work is based on the oblivious array for secret-sharing-based multiparty computation by Keller and Scholl (Asiacrypt `14). This means that we only incur a polylogarithmic overhead over the execution on a CPU. We describe an implementation of our construction using the Clang compiler from the LLVM project and the SPDZ protocol by Damgård et al. (Crypto `12). The latter provides active security against a dishonest majority and works in the preprocessing model. The online phase clock rate of the resulting machine is 41 Hz for a memory size of 1024 64-bit integers and 2.2 Hz for a memory of 2^20 integers. Both timings have been taken for two parties in a local network. Similar work by other authors has only been in the semi-honest setting. To further showcase our toolchain, we implemented and benchmarked private regular expression matching. Matching a string of length 1024 against a regular expression with 69270 transitions as a finite state machine takes seven hours online time, of which more than six hours are devoted to loading the reusable program.

Fully homomorphic encryption (FHE) has important applications in cloud computing. However, almost all fully homomorphic encryption schemes share two common flaws that they all use large-scale secret keys and some operations inefficient. In this paper, the “special b” variant of the Learning With Errors problem (bLWE) is presented, and helps us construct the first circularly secure key switching process which can replace the key switching process and similar re-linearization process used by the existing FHE schemes. Then, we present an efficient FHE. Compared with Brakerski’s scheme, our scheme reduces L secret keys to one and is more efficient. Finally, we prove the chosen-plaintext attack (CPA) security of the fully homomorphic scheme and the circular security of key switching process in standard model under the learning with errors problem (LWE) assumption.

Advanced modern processors support Single Instruction Multiple Data (SIMD) instructions (e.g. Intel-AVX, ARM-NEON) and a massive body of research on vector-parallel implementations of modular arithmetic, which are crucial components for modern public-key cryptography ranging from RSA, ElGamal, DSA and ECC, have been conducted. In this paper, we introduce a novel Double Operand Scanning (DOS) method to speed-up multi-precision squaring with non-redundant representations on SIMD architecture. The DOS technique partly doubles the operands and computes the squaring operation without Read-After-Write (RAW) dependencies between source and destination variables. Furthermore, we presented Karatsuba Cascade Operand Scanning (KCOS) multiplication and Karatsuba Double Operand Scanning (KDOS) squaring by adopting additive and subtractive Karatsuba's methods, respectively. The proposed multiplication and squaring methods are compatible with separated Montgomery algorithms and these are highly efficient for RSA crypto system. Finally, our proposed multiplication/squaring, separated Montgomery multiplication/squaring and RSA encryption outperform the best-known results by 22/41\%, 25/33\% and 30\% on the Cortex-A15 platform.

Besides attracting a billion dollar economy, Bitcoin revolutionized the field of digital currencies and influenced many adjacent areas. This also induced significant scientific interest. In this survey, we unroll and structure the manyfold results and research directions. We start by introducing the Bitcoin protocol and its building blocks. From there we continue to explore the design space by discussing existing contributions and results. In the process, we deduce the fundamental structures and insights at the core of the Bitcoin protocol and its applications. As we show and discuss, many key ideas are likewise applicable in various other fields, so that their impact reaches far beyond Bitcoin itself.

Garg, Gentry and Halevi (GGH) described the first candidate multilinear maps using ideal lattices. However, Hu and Jia presented an efficient attack on GGH map, which breaks the GGH-based applications of multipartite key exchange (MPKE) and witness encryption (WE) based on the hardness of 3-exact cover problem. We describe a new construction of multilinear map using random matrix, which supports the applications for public tools of encoding in the origin GGH, such as MPKE and WE. The security of our construction depends upon new hardness assumption. Furthermore, our construction removes the special structure of the ring element in the principal ideal lattice problem, and avoids potential attacks generated by algorithm of solving short principal ideal lattice generator.

In this work we focus on tailoring and optimizing the computational Private Information Retrieval (cPIR) scheme proposed in WAHC 2014 for efficient execution on graphics processing units (GPUs). Exploiting the mass parallelism in GPUs is a commonly used approach in speeding up cPIRs. Our goal is to eliminate the efficiency bottleneck of the Doröz et al construction which would allow us to take advantage of its excellent bandwidth performance. To this end, we develop custom code to support polynomial ring operations and extend them to realize the evaluation functions in an optimized manner on high end GPUs. Specifically, we develop optimized CUDA code to support large degree/large coefficient polynomial arithmetic operations such as modular multiplication/reduction, and modulus switching. Moreover, we choose same prime numbers for both the CRT domain representation of the polynomials and for the modulus switching implementation of the somewhat homomorphic encryption scheme. This allows us to combine two arithmetic domains, which reduces the number of domain conversions and permits us to perform faster arithmetic. Our implementation achieves 14-34 times speedup for index comparison and 4-18 times speedup for data aggregation compared to a pure CPU software implementation. tion compared to a pure CPU software implementation.

In this paper, we propose approximate lattice algorithms for solving the shortest vector problem (SVP) and the closest vector problem (CVP) on an $n$-dimensional Euclidean integral lattice L. Our algorithms run in polynomial time of the dimension and determinant of lattices and improve on the LLL algorithm when the determinant of a lattice is less than 2^{n^2/4}. More precisely, our approximate SVP algorithm gives a lattice vector of size \le 2^{\sqrt{\log\det L}} and our approximate CVP algorithm gives a lattice vector, the distance of which to a target vector is 2^{\sqrt{\log\det L}} times the distance from the target vector to the lattice. One interesting feature of our algorithms is that their output sizes are independent of dimension and become smaller as the determinant of L becomes smaller. For example, if \det L=2^{n \sqrt n}, a short vector outputted from our approximate SVP algorithm is of size 2^{n^{3/4}}, which is asymptotically smaller than the size 2^{n/4+\sqrt n} of the outputted short vectors of the LLL algorithm. It is similar to our approximate CVP algorithm.

This paper describes a smart contract programming lab conducted in our undergraduate security class at the University of Maryland. Through our experiences, we have gained various insights on why it is difficult to create a safe smart contract. This lab also led to new insights for cybersecurity education.

Feistel structure is among the most popular choices for designing ciphers. Recently, 3-round/5-round integral distinguishers for Feistel structures with non-bijective/bijective round functions are presented. At EUROCRYPT 2015, Todo proposed the Division Property to effectively construct integral distinguishers for both Feistel and SPN structures. In this paper, firstly, it is proved that if X, which is a subset of F_2^n, has the division property D_k^n, the number of elements in X is at least 2^k, based on which we can conclude that if a multi-set X has the division property D_n^n, it is in some sense equivalent to either F_2^n or the empty set. Secondly, let d be the algebraic degree of the round function of a Feistel structure. If d\le n-1, the corresponding integral distinguishers are improved as follows: there exists a 3-round integral distinguisher with at most 2^n chosen plaintexts and a 4-round integral distinguisher with at most 2^{2n-2} chosen plaintexts. These results can give new insights to both the division property and Feistel structures.

In order to keep privacy and to maintain security of a data; it was necessary to keep the data in hidden manner or in a crypt format. The proposed work describes the encryption and data hiding techniques for an H.264/ AVC video in a cloud environment. And it clearly specifies how the integrity of the data should be relevant enough in an unsecured and constrained communication medium. The proposed scheme is based on the stream cipher, RC4 encryption; while encrypting a data, it is necessary to transfer the encryption keys in a secure manner for that the public key cryptosystem is proposed for the efficient key transferring. It also explains about the data embedding via compound mapping method in order secure the original video content, and then generating the hash value for the embedded data which may contain the encrypted video content, in order to check the integrity of the data. And at the receiver end, the processes; the verification of the hash value, the decryption and extraction of the video content may be done in an efficient manner. The results may clearly shows the size of the video is strictly preserved even after the encryption and the embedding techniques.

In 2004, Canetti-Halevi-Katz and later Boneh-Katz showed generic CCA-secure PKE constructions from a CPA-secure IBE. Goyal et al. in 2006 further extended the aforementioned idea implicitly to provide a specific CCA-secure KP-ABE with policies represented by monotone access trees. Later, Yamada et al. in 2011 generalized the CPA to CCA conversion to all those ABE, where the policies are represented by either monotone access trees (MAT) or monotone span programs (MSP), but not the others like sets of minimal sets. Moreover, the underlying CPA-secure constructions must satisfy one of the two features called key-delegation and verifiability. Along with ABE, many other different encryptions schemes, such as inner-product, hidden vector, spatial encryption schemes etc. can be studied under an unified framework, called functional encryption (FE), as introduced by Boneh-Sahai-Waters in 2011. The generic conversions, due to Yamada et al., can not be applied to all these functional encryption schemes. On the other hand, to the best of our knowledge, there is no known CCA-secure construction beyond ABE over MSP and MAT. This paper provides different ways of obtaining CCA-secure functional encryptions of almost all categories. In particular, we provide a generic conversion from a CPA-secure functional encryption into a CCA-secure functional encryption provided the underlying CPA-secure encryption scheme has either restricted delegation or verifiability feature. We observe that almost all functional encryption schemes have this feature. The KP-FE schemes of Waters (proposed in 2012) and Attrapadung (proposed in 2014) for regular languages do not possess the usual delegation property. However, they can be converted into corresponding CCA-secure schemes as they satisfy the restricted delegation.

Establishing friendship relationships on Facebook often entails information sharing which is based on the social trust and implicit contract between users and their friends. In this context, Facebook offers applications (Apps) developed by third-party application providers (AppPs), which may grant access to users' personal data via Apps installed by their friends. Such access takes place outside the circle of social trust with the user not being aware whether a friend has installed an App collecting her data. In some cases, one or more AppPs may cluster several Apps and thus gain access to a collection of personal data. As a consequence privacy risks emerge. Previous research has mentioned the need to quantify privacy risks on Online Social Networks (OSNs). Nevertheless, most of the existing works do not focus on the personal data disclosure via Apps. Moreover, the problem of personal data clustering from AppPs has not been studied. In this work, we perform a general analysis of the privacy threats stemming from the personal data requested by Apps installed by the user’s friends from a technical and legal point of view. In order to assist users, we propose a model and a privacy scoring formula to calculate the amount of personal data that may be exposed to AppPs. Moreover, we propose algorithms that based on clustering, computes the visibility of each personal data to the AppPs.

Encrypting data on client-side before uploading it to a cloud storage is essential for protecting users' privacy. However client-side encryption is at odds with the standard practice of deduplication. Reconciling client-side encryption with cross-user deduplication is an active research topic. We present the first secure cross-user deduplication scheme that supports client-side encryption {\em without requiring any additional independent servers}. Interestingly, the scheme is based on using a PAKE (password authenticated key exchange) protocol. We demonstrate that {\em our scheme provides better security guarantees than previous efforts}. We show both the effectiveness and the efficiency of our scheme, via simulations using realistic datasets and an implementation.

Smart objects are devices with computational and communication capabilities connected to the Internet forming the so called Internet of Things (IoT). The IoT enables many applications, for instance outdoor lighting control, smart energy and water management, or environmental sensing in a smart city environment. Security in such scenarios remains an open challenge due to the resource-constrained nature of devices and networks or the multiple ways in which opponents can attack the system during the lifecycle of a smart object.This paper firstly reviews security and operational goals in an IoT scenario inspired in a smart city environment. Then, we present a comprehensive and lightweight security architecture to secure the IoT throughout the lifecycle of a device. Our solution relies on the lightweight HIMMO scheme as the building stone and shows how HIMMO is not only efficient resource-wise, but that it enables advanced IoT protocols and deployments. Our design and analysis show that our HIMMO-based security architecture can be easily integrated in existing communication protocols such as IEEE 802.15.4 or OMA LWM2M providing a number of advantages that existing solutions cannot provide both performance and operation-wise.

As a modified version of GGH map, Gu map-1 was successful in constructing multi-party key exchange (MPKE). In this short paper we present a result about the parameter setting of Gu map-1, therefore we can reduce a key parameter $\tau$ from original $O(n^{2})$ down to $O(\lambda n)$ (in theoretically secure case, where $\lambda$ is the security parameter), and even down to $O(2n)$ (in computationally secure case). Such optimization greatly reduces the size of the map.

Higher-order side-channel attacks are able to break the security of cryptographic implementations even if they are protected with masking countermeasures. In this paper, we derive the best possible distinguishers (High-Order Optimal Distinguishers or HOOD) against masking schemes under the assumption that the attacker can profile. Our exact derivation admits simple approximate expressions for high and low noise and shows to which extent the optimal distinguishers reduce to known attacks in the case where no profiling is possible. From these results, we can explain theoretically the empirical outcome of recent works on second-order distinguishers. In addition, we extend our analysis to any order and to the application to masked tables precomputation. Our results give some insight on which distinguishers have to be considered in the security analysis of cryptographic devices.

In the literature, few constructions of $n$-variable rotation symmetric bent functions have been presented, which either have restriction on $n$ or have algebraic degree no more than $4$. In this paper, for any even integer $n=2m\ge2$, a first systemic construction of $n$-variable rotation symmetric bent functions, with any possible algebraic degrees ranging from $2$ to $m$, is proposed.

Adaptive security is a strong corruption model that captures ``hacking'' attacks where an external attacker breaks into parties' machines in the midst of a protocol execution. There are two types of adaptively-secure protocols: adaptive with erasures and adaptive without erasures. Achieving adaptivity without erasures is preferable, since secure erasures are not always trivial. However, it seems far harder. We introduce a new model of adaptive security called adaptive security with partial erasures that allows erasures, but only assumes them in a minimal sense. Specifically, if all parties are corrupted then security holds as long as any single party successfully erases. In addition, security holds if any proper subset of the parties is corrupted without erasures. We initiate a theoretical study of this new notion and demonstrate that secure computation in this setting is as efficient as static secure computation. In addition, we study the relations between semi-adaptive security~\cite{GarayWZ09}, adaptive security with partial erasures, and adaptive security without any erasures. We prove that the existence of semi-adaptive OT implies secure computation in all these settings.

Many modern block ciphers use maximum distance separate (MDS) matrices as their diffusion layers. In this paper, we propose a new method to verify a sort of MDS diffusion block matrices whose blocks are all polynomials in a certain primitive block over the finite field $\mathbb F_2$. And then we discover a new kind of transformations that can retain MDS property of diffusion matrices and generate a series of new MDS matrices from a given one. Moreover, we get an equivalence relation from this kind of transformation. And MDS property is an invariant with respect to this equivalence relation which can greatly reduce the amount of computation when we search for MDS matrices. The minimal polynomials of matrices play an important role in our strategy. To avoid being too theoretical, we list a series of MDS diffusion matrices obtained from our method for some specific parameters. Furthermore, we talk about MDS recursive diffusion layers with our method and extend the corresponding work of M. Sajadieh et al. published on FSE 2012 and the work of S. Wu published on SAC 2012.

Gu map-1 is a modified version of GGH map. It uses same ideal lattices for constructing the trapdoors, while the novelty is that no encodings of zero are given. In this short paper we show that Gu map-1 cannot be used for the instance of witness encryption (WE) based on the hardness of 3-exact cover problem. That is, if Gu map-1 is used for such instance, we can break it by solving a combined 3-exact cover problem. The reason is just that no encodings of zero are given.

Side-channel cube attacks are a class of leakage attacks on block ciphers in which the attacker is assumed to have access to some leaked information on the internal state of the cipher as well as the plaintext/ciphertext pairs. The known Dinur-Shamir model and its variants require error-free data for at least part of the measurements. In this paper, we consider a new and more realistic model which can deal with the case when \textit{all} the leaked bits are noisy. In this model, the key recovery problem is converted to the problem of decoding a binary linear code over a binary symmetric channel with the crossover probability which is determined by the measurement quality and the cube size. We use the maximum likelihood decoding method to recover the key. As a case study, we demonstrate efficient key recovery attacks on PRESENT. We show that the full $80$-bit key can be restored with $2^{10.2}$ measurements with an error probability of $19.4\%$ for each measurement.

We propose a general technique that allows improving the complexity of zero-knowledge protocols for a large class of problems where previously the best known solution was a simple cut-and-choose style protocol, i.e., where the size of a proof for problem instance $x$ and error probability $2^{-n}$ was $O(|x| n)$ bits. By using our technique to prove $n$ instances simultaneously, we can bring down the proof size per instance to $O(|x| + n)$ bits for the same error probability while using no computational assumptions. Examples where our technique applies include proofs for quadratic residuosity, proofs of subgroup membership and knowledge of discrete logarithms in groups of unknown order, interval proofs of the latter, and proofs of plaintext knowledge for various types of homomorphic encryption schemes. We first propose our protocols as $\Sigma$-protocols and extend them later to zero-knowledge proofs of knowledge.

In FSE 2007, Ristenpart and Rogaway had described a generic method XLS to construct a length-preserving strong pseudorandom per- mutation (SPRP) over bit-strings of size at least n. It requires a length-preserving permutation E over all bits of size multiple of n and a blockcipher E with block size n. The SPRP security of XLS was proved from the SPRP assumptions of both E and E. In this paper we disprove the claim by demonstrating a SPRP distinguisher of XLS which makes only three queries and has distinguishing advantage about 1/2. XLS uses a multi-permutation linear function, called mix2. In this paper, we also show that if we replace mix2 by any invertible linear functions, the construction XLS still remains insecure. Thus the mode has inherit weakness.

Ristenpart and Rogaway proposed XLS in 2007 which is a generic method to encrypt messages with incomplete last blocks. Later Andreeva et al., in 2013 proposed an authenticated encryption COPA which uses XLS while processing incomplete message blocks. Following the design of COPA, several other CAESAR candidates used the similar approach. Surprisingly in 2014, Nandi showed a three-query distinguisher against XLS which violates the security claim of XLS and puts a question mark on all schemes using XLS. However, due to the interleaved nature of encryption and decryption queries of the distinguisher, it was not clear whether the security claims of COPA remains true or not. This paper revisits XLS and COPA both in the direction of cryptanalysis and provable security. Our contribution of the paper can be summarized into following two parts: 1. Cryptanalysis: We describe two attacks - (i) a new distinguisher against XLS and extending this attack to obtain (ii) a forging algo- rithm with query complexity about 2^n/3 against COPA where n is the block size of the underlying blockcipher. 2. Security Proof: Due to the above attacks the main claims of XLS (already known before) and COPA are wrong. So we revise the security analysis of both and show that (i) both XLS and COPA are pseudorandom function or PRF up to 2^n/2 queries and (ii) COPA is integrity-secure up to 2^n/3 queries (matching the query complexity of our forging algorithm).

The Bistable Ring (BR) Physical Unclonable Function (PUF) is a newly proposed hardware security primitive in the PUF family. In this work, we comprehensively evaluate its resilience against Machine Learning (ML) modeling attacks. Based on the success of ML attacks, we propose XOR strategies to enhance the security of BR PUFs. Our results show that the XOR BR PUF with more than four parallel BR PUFs is able to resist the ML modeling methods in this work. We also evaluate the other PUF metrics of reliability, uniqueness and uniformity, and find that the XOR function is also effective in improving the uniformity of BR PUFs.