We present a new protocol for maliciously secure two-party computation based on cut-and-choose of garbled circuits using the recent idea of “forge-and-loose”, which eliminates around a factor 3 of garbled circuits that needs to be constructed and evaluated. Our protocol introduces a new way to realize the “forge-and-loose” approach, which avoids an auxiliary secure two-party computation protocol, does not rely on any number theoretic assumptions and parallelizes well in a same instruction, multiple data (SIMD) framework. With this approach we prove our protocol universally composable secure against a malicious adversary assuming access to oblivious transfer, commitment and coin-tossing functionalities in the random oracle model. Finally, we construct, and benchmark, a SIMD implementation of this protocol using a GPU as a massive SIMD device. The findings compare favorably with all previous implementations of maliciously secure, two-party computation.

In this paper, we show two new constructions of chosen ciphertext secure (CCA secure) public key encryption (PKE) from general assumptions. The key ingredient in our constructions is an obfuscator for point functions with multi-bit output (MBPF obfuscators, for short), that satisfies some (average-case) indistinguishability-based security, which we call AIND security, in the presence of hard-to-invert auxiliary input. Specifically, our first construction is based on a chosen plaintext secure PKE scheme and an MBPF obfuscator satisfying the AIND security in the presence of computationally hard-to-invert auxiliary input. Our second construction is based on a lossy encryption scheme and an MBPF obfuscator satisfying the AIND security in the presence of statistically hard-to-invert auxiliary input. To clarify the relative strength of AIND security, we show the relations among security notions for MBPF obfuscators, and show that AIND security with computationally (resp. statistically) hard-to-invert auxiliary input is implied by the average-case virtual black-box (resp. virtual grey-box) property with the same type of auxiliary input. Finally, we show that a lossy encryption scheme can be constructed from an obfuscator for point functions (point obfuscator) that satisfies re-randomizability and a weak form of composability in the worst-case virtual grey-box sense. This result, combined with our second generic construction and several previous results on point obfuscators and MBPF obfuscators, yields a CCA secure PKE scheme that is constructed \emph{solely} from a re-randomizable and composable point obfuscator. We believe that our results make an interesting bridge that connects CCA secure PKE and program obfuscators, two seemingly isolated but important cryptographic primitives in the area of cryptography.

In this paper, a new bit-parallel Montgomery multiplier for $GF(2^m)$ is presented, where the field is generated with an irreducible trinomial. We first present a slightly generalized version of a newly proposed divide and conquer approach. Then, by combining this approach and a carefully chosen Montgomery factor, the Montgomery multiplication can be transformed into a composition of small polynomial multiplications and Montgomery squarings, which are simpler and more efficient. Explicit complexity formulae in terms of gate counts and time delay of our architecture are investigated. As a result, the proposed multiplier has generally 25\% lower space complexity than the fastest multipliers, with time complexity as good as or better than previous Karatsuba-based multipliers for the same class of fields. Among the five irreducible polynomials recommended by NIST for the ECDSA (Elliptic Curve Digital Signature Algorithm), there are two trinomials which are available for our architecture. We show that our proposal outperforms the previous best known results if the space and time complexity are both considered.

In 2013, the US National Security Agency proposed two new families of lightweight block ciphers: SIMON and SPECK. Currently, linear and differential cryptanalytic results for SIMON are available in the literature but no fault attacks have been reported so far on these two cipher families. In this paper, we show that these families of ciphers are vulnerable to differential fault attacks. Specifically, we demonstrate two fault attacks on SIMON and one fault attack on SPECK. The first attack on SIMON assumes a bit-flip fault model and recovers the n-bit last round key of SIMON using n/2 bit faults. The second attack on SIMON uses a more practical, random byte fault model and requires n/8 faults on average to retrieve the last round key. The attack presented on SPECK also assumes a bit-flip fault model and recovers the n-bit last round key of SPECK using n/3 bit faults on average.

This paper introduces our dedicated authenticated encryption scheme ICEPOLE. ICEPOLE is a high-speed hardware-oriented scheme, suitable for high-throughput network nodes or generally any environment where specialized hardware (such as FPGAs or ASICs) can be used to provide high data processing rates. ICEPOLE-128 (the primary ICEPOLE variant) is very fast. On the modern FPGA device Virtex 6, a basic iterative architecture of ICEPOLE reaches 41 Gbits/s, which is over 10 times faster than the equivalent implementation of AES-128-GCM. The throughput-to-area ratio is also substantially better when compared to AES-128-GCM. We have carefully examined the security of the algorithm through a range of cryptanalytic techniques and our findings indicate that ICEPOLE offers high security level.

We introduce the notion of *dual system groups*. - We show how to derive compact HIBE by instantiating the dual system framework in Waters (Crypto '09) and Lewko and Waters (TCC '10) with dual system groups. Our construction provides a unified treatment of the prior compact HIBE schemes from static assumptions. - We show how to instantiate dual system groups under the decisional subgroup assumption in composite-order groups and the decisional linear assumption ($d$-LIN) in prime-order groups. Along the way, we provide new tools for simulating properties of composite-order bilinear groups in prime-order groups. In particular, we present new randomization and parameter-hiding techniques in prime-order groups. Combining the two, we obtain a number of new encryption schemes, notably - a new construction of IBE in prime-order groups with shorter parameters; - a new construction of compact HIBE in prime-order groups whose structure closely mirrors the selectively secure HIBE scheme of Boneh, Boyen and Goh (Eurocrypt '05); - a new construction of compact spatial encryption in prime-order groups.

Security models for two-party authenticated key exchange (AKE) protocols have developed over time to provide security even when the adversary learns certain secret keys. In this work, we advance the modelling of AKE protocols by considering more granular, continuous leakage of long-term secrets of protocol participants: the adversary can adaptively request arbitrary leakage of long-term secrets even after the test session is activated, with limits on the amount of leakage per query but no bounds on the total leakage. We present a security model supporting continuous leakage even when the adversary learns certain ephemeral secrets or session keys, and give a generic construction of a two-pass leakage-resilient key exchange protocol that is secure in the model; our protocol achieves continuous, after-the-fact leakage resilience with not much more cost than a previous protocol with only bounded, non-after-the-fact leakage.

Scan chains, a design for testability (DFT) feature, are included in most modern-day ICs. But, it opens a side channel for attacking cryptographic chips. We propose a methodology by which we can recover internal states of any stream cipher using scan chains without knowledge of its design. We consider conven- tional scan-chain design which is normally not scram- bled or protected in any other way. In this scenario the challenge of the adversary is to obtain the corre- spondence of output of the scan chain and the internal state registers of the stream cipher. We present a math- ematical model of the attack and the correspondence between the scan chain-outputs and the internal state bits have been proved under this model. We propose an algorithm that through o-line and on-line simulation forms bijection between the above mentioned sets and thus nds the required correspondence. We also give an estimate of the number of o-line simulations necessary for nding the correspondence. The proposed strategy is successfully applied to eS- tream hardware based nalists MICKEY-128 2.0, Triv- ium and Grain-128. To the best of our knowledge, this is the rst scan based attack against full round Grain-128 and only the fourth reported cryptanalysis. This attack on Trivium is better than that of the published scan- attack on Trivium. This scan-based attack is also the rst reported scan based cryptanalysis against MICKEY- 128 2.0.

This paper presents differential fault analysis of the MICKEY family of stream ciphers, one of the winners of eStream project. The current attacks are of the best performance among all the attacks against MICKEY ciphers reported till date. The number of faults required with respect to state size is about 1.5 times the state size. We obtain linear equations to determine state bits. The fault model required is reasonable. The fault model is further relaxed without reproducing the faults and allowing multiple bit faults. In this scenario, more faults are required when reproduction is not allowed whereas, it has been shown that the number of faults remains same for multiple bit faults.

In this paper, we present fault attack on Grain family of stream ciphers, an eStream finalist. The earlier fault attacks on Grain work on LFSR whereas our target for fault induction is the NFSR. Our attack requires a small number of faults to be injected; 150 only for Grain v1 and only 312 and 384 for Grain-128 and Grain-128a, respectively. The number of faults are much lesser than the earlier reported fault attacks; 1587 for Grain-128 and 1831 for Grain-128a.

Locally decodable codes (LDC)~\cite{BFLS91,KT00} are error correcting codes that allow decoding (any) individual symbol of the message, by reading only few symbols of the codeword. Consider an application such as storage solutions for large data, where errors may occur in the disks (or some disks may just crush). In such an application, it is often desirable to recover only small portions of the data (have random access). Thus, in such applications, using LDC provides enormous efficiency gains over standard error correcting codes (ECCs), that need to read the entire encoded message to learn even a single bit of information. Typically, LDC's, as well as standard ECC's decode the encoded messaged if upto some bounded fraction of the symbols had been modified. This corresponds to decoding strings of bounded Hamming distance from a valid codeword. An often more realistic metric is the edit distance, measuring the shortest sequence of insertions and deletions (indel.) of symbols leading from one word to another. For example, (few) indel. modifications is a more realistic model for mutations occurring in a genome. Even more commonly, communication over the web may sustain deletions (lost packets) and insertions (noise).\footnote{Edit distance is indeed "more expressive" then Hamming distance in the sense that $dist_E(x,y)\leq 2dist_H(x,y)$ always holds, while edit distance 2 may translate to Hamming distance $n$. For instance, consider $x=1010\ldots 10,y=0101\ldots 1$. } Standard ECC's for edit distance have been previously considered~\cite{SZ97}. Furthermore,~\cite{SZ97} devised codes with rate and distance (error tolerance) optimal upto constants. LDC's, originally considered in the setting of PCP's~\cite{BFLS91}, have found many additional applications, and generated a lot of fascinating work (see~\cite{Yek11} and references within). However, combining these two useful settings of LDC, and robustness against indel. errors has never been considered. In this work, we study the question of constructing LDC's for edit distance. We demonstrate a strong positive result - LDC's for edit distance can be achieved, with similar parameters to LDC's for Hamming distance. More precisely, we devise a generic transformation from LDC for Hamming distance to LDC for edit distance with related parameters.

In this paper we mount the cube attack on the Keccak sponge function. The cube attack, formally introduced in 2008, is an algebraic technique applicable to cryptographic primitives whose output can be described as a low-degree polynomial in the input. Our results show that 5- and 6-round Keccak sponge function is vulnerable to this technique. All the presented attacks have practical complexities and were verified on a desktop PC.

FASER is a family of authenticated ciphers submitted to the CAESAR competition, which contains two parent ciphers: FASER128 and FASER256. In this work we only focus on FASER128 and present a key recovery attack to FASER128, which needs at most 64 key words and is realtime in a PC. The result shows that FASER128 is very insecure. What's more, our attack can be easily applied to FASER256 and break it entirely.

Handycipher is a low-tech, randomized, symmetric-key, stream cipher, simple enough to permit pen-and-paper encrypting and decrypting of messages, while providing a significantly high level of security. It combines a simple 31-character substitution cipher with a 3,045-token nondeterministic homophonic substitution cipher, and employs the insertion of randomly chosen decoy characters at random locations in the ciphertext. A deniable encryption scheme based on the cipher is described, as well as a way of extending the cipher by using randomly generated session keys.

Abstract. With the advent of networking applications collecting user data on a massive scale, the privacy of individual users appears to be a major concern. The main challenge is the design of a solution that allows the data analyzer to compute global statistics over the set of individual inputs that are protected by some confidentiality mechanism. Joye et al. [7] recently suggested a solution that allows a centralized party to compute the sum of encrypted inputs collected through a smart metering network. The main shortcomings of this solution are its reliance on a trusted dealer for key distribution and the need for frequent key updates. In this paper we introduce a secure protocol for aggregation of time series data that is based on the Joye et al. [7] scheme and in which the main shortcomings of the latter, namely, the requirement for key updates and for the trusted dealer are eliminated. Moreover our scheme supports a dynamic group management, whereby as opposed to Joye et al. [7] leave and join operations do not trigger a key update at the users.

Digital signature schemes are a foundational cryptographic building block in certification and the projection of trust. Based on a signature scheme on committed graphs, we propose a toolkit of certification and proof methods to sign committed topology graphs and to prove properties of their certificates in zero-knowledge. This toolkit allows an issuer, such as an auditor, to sign the topology representation of an infrastructure. The prover, such as an infrastructure provider, can then convince a verifier of topology properties, such as partitions, connectivity or isolation, without disclosing the structure of the topology itself. By that, we can achieve the certification of the structure of critical systems, such as infrastructure clouds or outsourced systems, while still maintaining confidentiality. We offer zero-knowledge proofs of knowledge for a general specification language of security goals for virtualized infrastructures, such that high-level security goalscan be proven over the topology certificate. Our method builds upon the Camenisch-Lysyanskaya signature scheme, is based on honest-verifier proofs and the strong RSA assumption.

The recent Bimodal Lattice Signature Scheme (BLISS) showed that lattice-based constructions have evolved to practical alternatives to RSA or ECC. It offers small signatures of 5600 bits for a 128-bit level of security, and proved to be very fast in software. However, due to the complex sampling of Gaussian noise with high precision, it is not clear whether this scheme can be mapped efficiently to embedded devices. Even though the authors of BLISS also proposed a new sampling algorithm using Bernoulli variables this approach is more complex than previous methods using large precomputed tables. The clear disadvantage of using large tables for high performance is that they cannot be used on constrained computing environments, such as FPGAs, with limited memory. In this work we thus present techniques for an efficient Cumulative Distribution Table (CDT) based Gaussian sampler on reconfigurable hardware involving Peikert's convolution lemma and the Kullback-Leibler divergence. Based on our enhanced sampler design, we provide a scalable implementation of BLISS signing and verification on a Xilinx Spartan-6 FPGA supporting either 128-bit, 160-bit, or 192-bit security. For high speed we integrate fast FFT/NTT-based polynomial multiplication, parallel sparse multiplication, Huffman compression of signatures, and Keccak as hash function. Additionally, we compare the CDT with the Bernoulli approach and show that for the particular BLISS-I parameter set the improved CDT approach is faster with lower area consumption. Our BLISS-I core uses 2,291 slices, 5.5 BRAMs, and 5 DSPs and performs a signing operation in 114.1 us on average. Verification is even faster with a latency of 61.2 us and 17,101 supported verification operations per second.

With the increasing popularity of cloud-based data services, data owners are highly motivated to store their huge amount of (potentially sensitive) personal data files on remote servers in encrypted form. Clients later can query over the encrypted database to retrieve files of interest while preventing database servers from learning private information about the contents of files and queries. In this paper, we investigate new and novel SSE designs which meet all practical properties, including one-round multi-keyword query, comprehensive and practical privacy protection, sublinear search time, and efficient dynamic data operation support. Moreover, our solutions can well support parallel search and run for very large-scale cloud databases. Compared to the existing SSE solutions, our solution is highly compact, efficient and flexible. Its performance and security are carefully characterized by rigorous analysis. Experimental evaluations conducted over large representative real-word data sets demonstrate that compared with the state-of-the-art our solution indeed achieves desirable properties for large-scale encrypted database systems.

RSA–CRT is the most widely used implementation for RSA signatures. However, deterministic and many probabilistic RSA signatures based on CRT are vulnerable to fault attacks. Nevertheless, Coron and Mandal (Asiacrypt 2009) show that the randomized PSS padding protects RSA signatures against random faults. In contrast, Fouque et al. (CHES 2012) show that PSS padding does not protect against certain non-random faults that can be injected in widely used implementations based on the Montgomery modular multiplication. In this article, we prove the security of an infective countermeasure against a large class of non-random faults; the proof extends Coron and Mandal’s result to a strong model where the adversary can force the faulty signatures to be a multiple of one of the prime factors of the RSA modulus. Such non-random faults induce more complex probability distributions than in the original proof, which we analyze using careful estimates of exponential sums attached to suitable rational functions. The security proof is formally verified using appropriate extensions of EasyCrypt, and provides the first application of formal verification to provable (i.e. reductionist) security in the context of fault attacks.

We present attacks against CMCC that invalidate the claimed security of integrity protection and misuse resistance. We exploit the fact zero-padding is used on both the message and authenticated data and demonstrate how one may generate a forgery with a single call to the encryption oracle. From this we calculate the ciphertext of the chosen message, yielding a forgery and so breaking INT-CTXT. In the nonce-reuse setting, existence of a forgery leads directly to a 2-query distinguisher.

The fully homomorphic symmetric encryption scheme \emph{MORE} encrypts keys by conjugation with a random invertible matrix over an RSA modulus. We provide a two known-ciphertexts cryptanalysis recovering a linear dependence among the two encrypted keys.

Basing on the original Cube attack, this paper proposes an improved method of Cube attack on stream ciphers, which makes improvement on the pre-processing phase of the original attack. The new method can induce maxterms of higher-order from those of lower-order by the trade-off between time and space, thus recovering more key bits and reducing the search complexity on higher-dimension. In this paper, the improved attack is applied to Lili-128 algorithm and reduced variants of Trivium algorithm. We can recover 88 key bits of Lili-128 algorithm within time complexity of 2^14 and 48 key bits of Trivium algorithm can be recovered by cubes with dimension no larger than 8 when the initialization round is 576, the results are much better than those of the original attacks.

This work exposes further vulnerabilities in virtualized cloud servers by mounting Cross-VM cache attacks in Xen and VMware VMs targeting AES running in the victim VM. Even though there exists a rich literature on cache attacks on AES, so far only a single work, demonstrating a working attack on an ARM platform running a L4Re virtualization layer has been published. Here we show that AES in a number popular cryptographic libraries including OpenSSL, PolarSSL and Libgcrypt are vulnerable to Bernstein’s correlation attack when run in Xen and VMware (bare metal version) VMs, the most popular VMs used by cloud service providers (CSP) such as Amazon and Rackspace. We also show that the vulnerability persists even if the VMs are placed on different cores in the same machine. The results of this study shows that there is a great security risk to AES and (data encrypted under AES) on popular cloud services.

A threshold password-authenticated key exchange (T-PAKE) protocol allows a set of n servers to collectively authenticate a client with a human-memorizable password such that any subset of size greater than a threshold t can authenticate the client, while smaller subsets of servers learn no information about the password. With its protection against offline dictionary attacks, T-PAKE provides a practical solution for an important real-life problem with password authentication. However, the proposed T-PAKE constructions cannot tolerate any misbehavior---not even a crash---by a participating server during a protocol execution; the protocol has to be re-executed until all participating servers behave correctly. This not only presents a fault management challenge for the servers, but more importantly also can leave the clients frustrated for being denied access even after entering a correct password. In this work, we present a novel T-PAKE protocol which solves the above fault management problem by employing a batched and offline phase of distributed key generation (DKG). Our protocol is secure against any malicious behavior from up to any t < n servers under the decisional Diffie-Hellman assumption in the random oracle model, and it ensures protocol completion for t < n/2. Moreover, it is efficient (16n + 7 exponentiations per client, 20n + 14 per server), performs explicit authentication in three communication rounds, and requires a significantly lesser number of broadcast rounds compared to previous secure T-PAKE constructions. We have implemented our protocol, and have verified its efficiency using micro-benchmark experiments. Our experimental results show that the protocol only introduces a computation overhead of few milliseconds at both the client and the server ends, and it is practical for use in real-life authentication scenarios.

Identity-based signature (IBS) is a specific type of public-key signature (PKS) where any identity string $ID$ can be used for the public key of a user. Although an IBS scheme can be constructed from any PKS scheme by using the certificate paradigm, it is still important to construct an efficient IBS scheme with short signature under the standard assumption without relying on random oracles. Recently, Kwon proposed an IBS scheme and claimed its strong unforgeability under the computational Diffie-Hellman (CDH) assumption. In this paper, we show that the security proof of Kwon is seriously flawed. To show the flaws, we first show that there exists a distinguisher that can distinguish the distribution of simulated signature from that of real signatures. Next, we also show that the simulator of Kwon's security argument cannot extract the solution of the CDH assumption even if there exists an adversary that forges the signature. Therefore, the security of the Kwon's IBS scheme is not related to the hardness of the CDH assumption.

Sablier is an authenticated encryption cipher submitted to the CAESAR competition, which is composed of the encryption Sablier v1 and the authentication \textup{Au}. In this work we present a state recovery attack against the encryption Sablier v1 with time complexity about $2^{44}$ operations and data complexity about 24 of 16-bit keywords. Our attack is practical in the workstation. It is noticed that the update of the internal state of Sablier v1 is invertible, thus our attack can further deduce a key recovery attack and a forgery attack against the authenticated encryption Sablier. The result shows that Sablier v1 is far from the goal of its security design (80-bit level).

The sweeping success of the original (2008) bitcoin protocol proves that digital currency has arrived. The mounting opposition from the financial establishment indicates an overshoot. We propose to tame bitcoin into bitcoin.BitMint: keeping the bitcoin excitement -- fitted into real world security, stability and fraud concerns. The basic idea is to excise the bitcoin money generation formula, and otherwise apply bitcoin essentially “as is” over digital coins which are redeemable by the mint that minted them. This will preserve the bitcoin assured anonymity. The new bitcoin.BitMint solution will benefit from bitcoin’s double-spending prevention, and would otherwise enjoy all the benefits associated with money in a digital form. bitcoin.BitMint will allow traders to invest in US$, gold, or any other commodity while practicing their trade in cyberspace, anonymously, securely, and non-speculatively. This “mint-in-the-middle” protocol will allow law enforcement authorities to execute a proper court order to enforce the disclosure of a suspected fraudster, but the community of honest traders will trade with robust privacy as offered by the original bitcoin protocol. We envision interlinked bitcoin.BitMint trading environments, integrated via an InterMint protocol: a framework for the evolution of a cascaded super currency – global and highly stable.

Fuzzy extractors (Dodis et al., Eurocrypt 2004) convert repeated noisy readings of a secret into the same uniformly distributed key. To eliminate noise, they require an initial enrollment phase that takes the first noisy reading of the secret and produces a nonsecret helper string to be used in subsequent readings. Reusable fuzzy extractors (Boyen, CCS 2004) remain secure even when this initial enrollment phase is repeated multiple times with noisy versions of the same secret, producing multiple helper strings (for example, when a single person's biometric is enrolled with multiple unrelated organizations). We construct the first reusable fuzzy extractor that makes no assumptions about how multiple readings of the source are correlated (the only prior construction assumed a very specific, unrealistic class of correlations). The extractor works for binary strings with Hamming noise; it achieves computational security under assumptions on the security of hash functions or in the random oracle model. It is simple and efficient and tolerates near-linear error rates. Our reusable extractor is secure for source distributions of linear min-entropy rate. The construction is also secure for sources with much lower entropy rates--lower than those supported by prior (nonreusable) constructions--assuming that the distribution has some additional structure, namely, that random subsequences of the source have sufficient minentropy. We show that such structural assumptions are necessary to support low entropy rates. We then explore further how different structural properties of a noisy source can be used to construct fuzzy extractors when the error rates are high, providing a computationally secure and an information-theoretically secure construction for large-alphabet sources.

Zero-Knowledge Password Policy Checks (ZKPPC), introduced in this work, enable blind registration of client passwords at remote servers, i.e., client passwords are never transmitted to the servers. This eliminates the need for trusting servers to securely process and store client passwords. A ZKPPC protocol, executed as part of the registration procedure, allows clients to further prove compliance of chosen passwords with respect to password policies defined by the servers. The main benefit of ZKPPC-based password registration is that it guarantees that registered passwords never appear in clear on the server side. At the end of the registration phase the server only receives and stores some verification information that can later be used for authentication in a suitable Verifier-based Password Authenticated Key Exchange (VPAKE) protocol. We give general and concrete constructions of ZKPPC protocols and suitable VPAKE protocols for ASCII-based passwords and policies that are commonly used on the web. To this end we introduce a reversible mapping of ASCII characters to integers that can be used to preserve the structure of the password string and a new randomized password hashing scheme for ASCII-based passwords.

UKS (unknown key-share) attacks are common attacks on Authenticated Key Exchange (AKE) protocols. We summarize two popular countermeasures against UKS attacks on implicitly authenticated key exchange protocols. The first one forces the CA to check the possession of private keys during registration, which is impractical for the CA. The second one adds identities in the derivation of the session key, which requires modifying the protocol which might have already been deployed in practice. By leveraging the key protection capability of hardware security chips such as TPM or TCM, we propose a new way to prevent UKS attacks that requires no check of possession of private keys and no addition of identities during the derivation of the session key. We modify the CK model to adapt protocols using hardware security chips. We then implement the KEA protocol once used in NSA, which is subject to UKS attacks, using TCM chips. Our implementation, called tKEA, is secure under our security model. To show the generality, we demonstrate that our new way can prevent UKS attacks on the MQV protocol.

We describe an automatic analysis to check secure multiparty computation protocols against privacy leaks. The analysis is sound --- a protocol that is deemed private does not leak anything about its private inputs, even if active attacks are performed against it. Privacy against active adversaries is an essential ingredient in constructions aiming to provide security (privacy + correctness) in adversarial models of intermediate (between passive and active) strength. Using our analysis we are able to show that the protocols used by the Sharemind secure multiparty computation platform are actively private.

In recent years, studies about the SATisfiability Problem (short for SAT) were more and more numerous because of its conceptual simplicity and ability to express a large set of various problems. Within a practical framework, works highlighting SAT impli- cations in real world problems had grown significantly. In this way, a new field called logical cryptanalysis appears in the 2000s and consists in an algebraic cryptanalysis in a binary context thanks to SAT solving. This paper deals with this concept applied to cryptographic hash functions. We first present the logical cryptanalysis principle, and provide details about our encoding approach. In a second part, we put the stress on the contribution of SAT to analyze the generated problem thanks to the discover of logical inferences and so simplifications in order to reduce the computational complexity of the SAT solving. This is mainly realized thanks to the use as a preprocessor of learning and pruning techniques from the community. Third, thanks to a probabilistic reasoning applied on the formulas, we present a weakness based on the use of round constants to detect probabilistic relations as implications or equivalences between certain vari- ables. Finally, we present a practical framework to exploit these weaknesses through the inversions of reduced-step versions of MD4, MD5, SHA-0 and SHA-1 and open some prospects.

We develop new theoretical tools for proving lower-bounds on the (amortized) complexity of functions in a parallel setting. We demonstrate their use by constructing the first provably secure Memory-hard functions (MHF); a class of functions recently gaining acceptance in practice as an effective means to counter brute-force attacks on security relevant functions. Pebbling games over graphs have proven to be a powerful abstraction for a wide variety of computational models. A dominant application of such games is proving complexity lower-bounds using ``pebbling reductions''. These bound the complexity of a given function $f_G$ in some computational model $\M$ of interest in terms of the pebbling complexity of a related graph $G$, where the pebbling complexity is defined via a pebbling game $\G$. In particular, finding a function with high complexity in $\M$ is reduced to (the hopefully simpler task of) finding graphs with high pebbling complexity in $\G$. We introduce a very simple and natural pebbling game $\G_p$ for abstracting parallel computation models. As an important conceptual contribution we also define a natural measure of pebbling complexity called \emph{cumulative complexity} (CC) and show how it overcomes a crucial shortcoming in the parallel setting exhibited by more traditional complexity measures used in past reductions. Next (analogous to the results of Tarjan et. al.~\cite{PTC77,LT82} for sequential pebbling games) we demonstrates, via a novel and non-tibial proof, an explicit construction of a constant in-degree family of graphs whose CC in $\G_p$ approaches maximality to within a polylogarithmic factor for any graph of equal size. To demonstrate the use of these theoretical tools we give an example in the field of cryptography, by constructing the first provably secure Memory-hard function (MHF). Introduced by Percival~\cite{Per09}, an MHF can be computed efficiently on a sequential machine but further requires the same amount of memory (or much greater time) amortized per evaluation on a parallel machine. Thus, while a say an ASIC or FPGA may be faster than a CPU, the increased cost of working memory negates this advantage. In particular MHFs crucially underly the ASIC/FPGA-resistant proofs-of-work of the crypto-currency Litecoin\cite{Litecoin}, the brute-force resistant key-derivation function {\tt scrypt}~\cite{Per09} and can be used to increase the cost to an adversary of recovering passwords from a compromised login server. To place these applications on more sound theoretic footing we first provide a new formal definition (in the Random Oracle Model) and an accompanying notion of amortized memory hardness to capture the intuitive property of an MHF (thereby remedying an important issue with the original definition of~\cite{Per09}). Next we define a mapping from a graph $G$ to a related function $f_G$. Finally we prove a pebbling reduction bounding the amortized memory hardness per evaluation of $f_G$ in terms of the CC of $G$ in the game $\G_p$. Together with the construction above, this gives rise to the first provably secure example of an MHF.

While AES is extensively in use in a number of applications, its area cost limits its deployment in resource constrained platforms. In this paper, we have implemented SIMON, a recent promising low-cost alternative of AES on reconfigurable platforms. The Feistel network, the construction of the round function and the key generation of SIMON, enables bit-serial hardware architectures which can significantly reduce the cost. Moreover, encryption and decryption can be done using the same hardware. The results show that with an equivalent security level, SIMON is 86\% smaller than AES, 70\% smaller than PRESENT (a standardized low-cost AES alternative), and its smallest hardware architecture only costs 36 slices (72 LUTs, 30 registers). To our best knowledge, this work sets the new area records as we propose the hardware architecture of the smallest block cipher ever published on FPGAs at 128-bit level of security. Therefore, SIMON is a strong alternative to AES for low-cost FPGA based applications.

Achterbahn stream cipher is proposed as a candidate for ECRYPT eSTREAM project which deals with key of length 80-bit. The linear distinguishing attack,which aims at distinguishing the keystream from purely random keystream,is employed to Achterbahn stream cipher. A linear distinguishing attack is based on linear sequential circuit approximation technique which distinguishes statistical bias in the keystream. In order to build the distinguisher, linear approximations of both non-linear feedback shift register (NLFSR) and the non-linear Boolean combining function R:F_2^8&#8594;F_2 are used. The keystream sequence generated by this algorithm consist a distinguisher with its probability bias&#12310; 2&#12311;^(-1809). Thus, to distinguish the Achterbahn, we only need 1/&#949;^2 =&#12310;&#12310;(2&#12311;^1809)&#12311;^2=2^3618 keystream bits and the time complexity is about 10/&#949;^2 =2^3621.3 which is much higher than the exhaustive key search O(2^80).

We study the problem of efficient (sub-linear) fuzzy search on encrypted outsourced data, in the symmetric-key setting. In particular, a user who stores encrypted data on a remote untrusted server forms queries that enable the server to efficiently locate the records containing the requested keywords, even though the user may misspell keywords or provide noisy data in the query. We define an appropriate primitive for a general \emph{closeness} function on the message space that we call \emph{efficiently fuzzy-searchable encryption} (\emph{EFSE}). Next we identify an optimal security notion for EFSE. We demonstrate that existing schemes do not meet our security definition and propose a new scheme that we prove secure under basic assumptions. Unfortunately, the scheme requires large ciphertext length, but we show that, in a sense, this space-inefficiency is unavoidable for a general, optimally-secure scheme. Seeking the right balance between efficiency and security, we then show how to construct schemes that are more efficient and satisfy a weaker security notion that we propose. To illustrate, we present and analyze a more space-efficient scheme for supporting fuzzy search on biometric data that achieves the weaker notion.

Oblivious RAM (ORAM) is an established technique to hide the access pattern to an untrusted storage system. With ORAM, a curious adversary cannot tell what data address the user is accessing when observing the bits moving between the user and the storage system. All existing ORAM schemes achieve obliviousness by adding redundancy to the storage system, i.e., each access is turned into multiple random accesses. Such redundancy incurs a large performance overhead. Though traditional data prefetching techniques successfully hide memory latency in DRAM based systems, it turns out that they do not work well for ORAM. In this paper, we exploit ORAM locality by taking advantage of the ORAM internal structures. Though it might seem apparent that obliviousness and locality are two contradictory concepts, we challenge this intuition by exploiting data locality in ORAM without sacrificing provable security. In particular, we propose an ORAM prefetching technique called dynamic super block scheme and comprehensively explore its design space. The dynamic super block scheme detects data locality in the program's working set at runtime, and exploits the locality in a data-independent way. % based on the key observation that position map ORAMs have better locality than the data ORAM. Our simulation results show that with dynamic super block scheme, ORAM performance without super blocks can be significantly improved. After adding timing protection to ORAM, the average performance gain is 25.5\% (up to 49.4\%) over the baseline ORAM and 16.6\% (up to 30.1\%) over the best ORAM prefetching technique proposed previously.

We present the homomorphic evaluation of the Prince block cipher. Our leveled implementation is based on a generalization of NTRU. We are motivated by the drastic bandwidth savings that may be achieved by scheme conversion. To unlock this advantage we turn to lightweight ciphers such as Prince. These ciphers were designed from scratch to yield fast and compact implementations on resource constrained embedded platforms. We show that some of these ciphers have the potential to enable near practical homomorphic evaluation of block ciphers. Indeed, our analysis shows that Prince can be implemented using only a 24 level deep circuit. Using an NTRU based implementation we achieve an evaluation time of 3.3 seconds per Prince block – one and two orders of magnitude improvement over homomorphic AES implementations achieved using NTRU, and BGV-style homomorphic encryption libraries, respectively.

We present a private information retrieval (PIR) scheme based on a somewhat homomorphic encryption (SWHE). In particular, we customize an NTRU-based SWHE scheme in order to evaluate a specific class of fixed depth circuits relevant for PIR implementation, thus achieving a more practical implementation. In practice, a SWHE that can evaluate a depth 5 circuit is sufficient to construct a PIR capable of retrieving data from a database containing 4 billion rows. We leverage this property in order to produce a more practical PIR scheme. Com- pared to previous results, our implementation achieves a significantly lower bandwidth cost (more than 1000 times smaller). The computational cost of our implementation is higher than previous proposals for databases containing a small number of bits in each row. However, this cost is amortized as database rows become wider.

Cloud storage is very popular since it has many advantages, but there is a new threat to cloud storage that was not considered before. {\it Self-updatable encryption} that updates a past ciphertext to a future ciphertext by using a public key is a new cryptographic primitive introduced by Lee, Choi, Lee, Park, and Yung (Asiacrypt 2013) to defeat this threat such that an adversary who obtained a past-time private key can still decrypt a (previously unread) past-time ciphertext stored in cloud storage. Additionally, an SUE scheme can be combined with an attribute-based encryption (ABE) scheme to construct a powerful revocable-storage ABE (RS-ABE) scheme introduced by Sahai, Seyalioglu, and Waters (Crypto 2012) that provides the key revocation and ciphertext updating functionality for cloud storage. In this paper, we propose an efficient SUE scheme and its extended schemes. First, we propose an SUE scheme with short public parameters in prime-order bilinear groups and prove its security under a $q$-type assumption. Next, we extend our SUE scheme to a time-interval SUE (TI-SUE) scheme that supports a time interval in ciphertexts. Our TI-SUE scheme has short public parameters and also secure under the $q$-type assumption. Finally, we propose the first large universe RS-ABE scheme with short public parameters in prime-order bilinear groups and prove its security in the selective revocation list model under a $q$-type assumption.

An isogeny graph is a graph whose vertices are principally polarizable abelian varieties and whose edges are isogenies between these varieties. In his thesis, Kohel describes the structure of isogeny graphs for elliptic curves and shows that one may compute the endomorphism ring of an elliptic curve defined over a finite field by using a depth-first search (DFS) algorithm in the graph. In dimension 2, the structure of isogeny graphs is less understood and existing algorithms for computing endomorphism rings are very expensive. In this article, we show that, under certain circumstances, the problem of determining the endomorphism ring can also be solved in genus 2 with a DFS-based algorithm. We consider the case of genus-2 Jacobians with complex multiplication, with the assumptions that the real multiplication subring is maximal and has class number one. We describe the isogeny graphs in that case, locally at prime numbers which split in the real multiplication subfield. The resulting algorithm is implemented over finite fields, and examples are provided. To the best of our knowledge, this is the first DFS-based algorithm in genus 2.

The ZigBee specification is an emerging wireless technology designed to address the specific needs of low-cost, low-power wireless sensor networks and is built upon the physical and medium access control layers defined in IEEE 802.15.4 standard for wireless personal area networks (WPANs). A key component for the wide-spread success and applicability of ZigBee-based networking solutions will be its ability to provide enhanced security mechanisms that can scale to hundreds of nodes. Currently, however, an area of concern is the ZigBee key management scheme, which uses a centralized approach that introduces well-known issues of limited scalability and a single point of vulnerability. Moreover, ZigBee key management uses a public key infrastructure. Due to these limitations, we suggest replacing ZigBee key management with a better candidate scheme that is decentralized, symmetric, and scalable while addressing security requirements. In this work, we investigate the feasibility of implementing Localized Encryption and Authentication Protocol (LEAP+), a distributed symmetric based key management. LEAP+ is designed to support multiple types of keys based on the message type that is being exchanged. In this paper, we first conduct a qualitative security analysis of LEAP+ and the current ZigBee key management scheme. Using the QualNet 5.0.2 simulator, we implement LEAP+ on the ZigBee platform for the very first time. Experimental results show that a distributed key management scheme such as LEAP+ provides improved security and offers good scalability.

Design of SP networks in which the non-linear layer is applied to only a part of the state in each round was suggested by Gérard et al.~at CHES 2013. Besides performance advantage on certain platforms, such a design allows for more efficient masking techniques that can mitigate side-channel attacks with a small performance overhead. In this paper we present generic techniques for differential and linear cryptanalysis of SP networks with partial non-linear layers, including an automated characteristic search tool and dedicated key-recovery algorithms. Our techniques can be used both for cryptanalysis of such schemes and for proving their security with respect to basic differential and linear cryptanalysis, succeeding where previous automated analysis tools seem to fail. We first apply our techniques to the block cipher Zorro (designed by Gérard et al.~following their methodology), obtaining practical attacks on the cipher which where fully simulated on a single desktop PC in a few days. Then, we propose a mild change to Zorro, and formally prove its security against basic differential and linear cryptanalysis. We conclude that there is no inherent flaw in the design strategy of Gérard et al., and it can be used in future designs, where our tools should prove useful.

Mission critical applications on homogenous mobile wireless sensor networks (HMWSNs) mandate new sets of security appliances to be friendly with existing resource constrained hardware platforms. To deliver a promising security, particularly in military deployments, mechanisms have to build upon an efficient key management that compensates HMWSNs constraints. Cluster-based key establishment is being the prime focus among the recent works in key establishment due to its significant improvement on network efficiency, security, scalability and flexibility. Therefore, we propose a Cluster-based framework to support pre-distribution key establishment schemes for HMWSNs. The proposed framework is compatible with most of pre-distribution schemes, and two instantiations are provided in this work to support our claim that the proposed framework improves security and scalability of the adopted schemes. We develop analytical models and conduct extensive simulations to evaluate the security and performance of the proposed framework, and the network connectivity under different scenarios.

We evaluate the security of the recently proposed authenticated encryption scheme POET with regard to weak keys when its universal hash functions are instantiated with finite field multiplications. We give explicit constructions for weak key classes not covered by POET's weak key testing strategy, and demonstrate how to leverage them to obtain universal forgeries.

In this paper, we present Functional Encryption (FE) schemes for finite languages from standard static assumption, viz., \textit{Decisional Linear} (DLIN) assumption. These finite languages are described by deterministic finite automata. Our first scheme is ciphertext-policy functional encryption (CP-FE), where a key $\sk_w$ is labeled with a string $w$ over a fixed alphabet $\Sigma$ and a ciphertext $\cipher_\amn$ is associated with a deterministic finite Automaton (DFA) $\amn$ over the same alphabet $\Sigma$. The key $\sk_w$ can extract the message from the ciphertext $\cipher_\amn$ if the DFA $\amn$ accepts the string $w$. This CP-FE scheme is constructed based on attribute-based encryption (ABE) structure of Okamoto-Takashima in Asiacrypt, 2012. To achieve the adaptive security, we put bounds on number of occurrences of any symbol in a string and in the set of transition tuples of a DFA. Due to this restriction, the size of key space (where the keys are indexed with strings) is reduced to finite. Hence, the functional scope of any DFA in our system can capture only finite language. Similarly, we obtain our second adaptively secure FE scheme in key-policy flavor from DLIN assumption. Both the schemes are shown to be secure in the standard model.

Garbled circuits offer a powerful primitive for computation on a user’s personal data while keeping that data private. Despite recent improvements, constructing and evaluating circuits of any useful size remains expensive on the limited hardware resources of a smartphone, the primary computational device available to most users around the world. In this work, we develop a new technique for securely outsourcing the generation of garbled circuits to a Cloud provider. By outsourcing the circuit generation, we are able to eliminate the most costly operations from the mobile device, including oblivious transfers. After proving the security of our techniques in the malicious model, we experimentally demonstrate that our new protocol, built on this role reversal, decreases execution time by 98% and reduces network costs by as much as 92% compared to previous outsourcing protocols. In so doing, we demonstrate that the use of garbled circuits on mobile devices can be made nearly as practical as it is becoming for server-class machines.

In this paper, we investigate the properties of iterative non-injective functions and the security of primitives where they are used. First, we introduce the Collision Probability Spectrum (CPS) parameter to quantify how far from a permutation a function is. In particular, we show that the output size decreases linearly with the number of iterations whereas the collision trees grow quadratically. Secondly, we investigate the T-sponge construction and show how certain CPS and rate values lead to an improved preimage attack on long messages. As an example, we find collisions for the GLUON-64 internal function, approximate its CPS, and show an attack that violates the security claims. For instance, if a message ends with a sequence of 1~Mb (respectively 1~Gb) of zeros, then our preimage search takes time $2^{115.3}$ (respectively $2^{105.3}$) instead of $2^{128}$.

In this work, we seek to optimize the efficiency of secure general-purpose obfuscation schemes. We focus on the problem of optimizing the obfuscation of Boolean formulas and branching programs -- this corresponds to optimizing the "core obfuscator" from the work of Garg, Gentry, Halevi, Raykova, Sahai, and Waters (FOCS 2013), and all subsequent works constructing general-purpose obfuscators. This core obfuscator builds upon approximate multilinear maps, where efficiency in proposed instantiations is closely tied to the maximum number of "levels" of multilinearity required. The most efficient previous construction of a core obfuscator, due to Barak, Garg, Kalai, Paneth, and Sahai (Eurocrypt 2014), required the maximum number of levels of multilinearity to be O(\ell s^{3.64}), where 's' is the size of the Boolean formula to be obfuscated, and \ell is the number of input bits to the formula. In contrast, our construction only requires the maximum number of levels of multilinearity to be roughly \ell s, or only s when considering a keyed family of formulas, namely a class of functions of the form f_z(x)=\phi(z,x) where \phi is a formula of size s. This results in significant improvements in both the total size of the obfuscation and the running time of evaluating an obfuscated formula. Our efficiency improvement is obtained by generalizing the class of branching programs that can be directly obfuscated. This generalization allows us to achieve a simple simulation of formulas by branching programs while avoiding the use of Barrington's theorem, on which all previous constructions relied. Furthermore, the ability to directly obfuscate general branching programs (without bootstrapping) allows us to efficiently apply our construction to natural function classes that are not known to have polynomial-size formulas.

This paper develops a new hybrid model of floating point numbers suitable for operations in secure multi-party computations. The basic idea is to consider the significand of the floating point number as a fixed point number and implement elementary function applications separately of the significand. This gives the greatest performance gain for the power functions (e.g. inverse and square root), with computation speeds improving up to 18 times in certain configurations. Also other functions (like exponent and Gaussian error function) allow for the corresponding optimisation. We have proposed new polynomials for approximation, and implemented and benchmarked all our algorithms on the Sharemind secure multi-party computation framework.

An AES-like lightweight block cipher, namely Zorro, was proposed in CHES 2013. While it has a 16-byte state, it uses only 4 S-Boxes per round. This weak nonlinearity was widely criticized, insofar as it has been directly exploited in all the attacks on Zorro reported by now, including the weak key, reduced round, and even full round attacks. In this paper, using some properties discovered by Wang et al., we present new differential and linear attacks on Zorro, both of which recover the full secret key with practical complexities. These attacks are based on very efficient distinguishers that have only two active S-Boxes per four rounds. The time complexity of our differential and linear attacks are $2^{56.76}$ and $2^{45.50}$ and the data complexity are $2^{56.73}$ chosen plaintexts and $2^{45.44}$ known plaintexts, respectively. The results clearly show that the block cipher Zorro does not have enough security against differential and linear attacks.

Dynamic Searchable Symmetric Encryption allows a client to store a dynamic collection of encrypted documents with a server, and later quickly carry out keyword searches on these encrypted documents, while revealing minimal information to the server. In this paper we present a new dynamic SSE scheme that is simpler and more efficient than existing schemes while revealing less information to the server than prior schemes, achieving fully adaptive security against honest-but-curious servers. We implemented a prototype of our scheme and demonstrated its efficiency on datasets from prior work. Apart from its concrete efficiency, our scheme is also simpler: in particular, it does not require the server to support any operation other than upload and download of data. Thus the server in our scheme can be based solely on a cloud storage service, rather than a cloud computation service as well, as in prior work. In building our dynamic SSE scheme, we introduce a new primitive called Blind Storage, which allows a client to store a set of files on a remote server in such a way that the server does not learn how many files are stored, or the lengths of the individual files; as each file is retrieved, the server learns about its existence (and can notice the same file being downloaded subsequently), but the file’s name and contents are not revealed. This is a primitive with several applications other than SSE, and is of independent interest.

\paes~is an authenticated encryption scheme designed by Ye {\it et al.}, and submitted to the CAESAR competition. The designers claim that \paese, which is one of the designs of the \paes-family, provides 128-bit security in the nonce misuse model. In this note, we show our forgery attack against \paese. Our attack works in the nonce misuse model. The attack exploits the slow propagation of message differences. The attack is very close to the universal forgery attack. As long as the target message is not too short, {\it e.g.} more than 10 blocks (160 bytes), a tag is forged only with $2^{11}$ encryption oracle calls, $2^{11}$ computational cost, and negligible memory.

\panda~is an authenticated encryption scheme designed by Ye {\it et al.}, and submitted to the CAESAR competition. The designers claim that \pandas, which is one of the designs of the \panda-family, provides 128-bit security in the nonce misuse model. In this note, we describe our forgery attack against \pandas. Our attack works in the nonce misuse model. It exploits the fact that the message processing function and the finalization function are identical, and thus a variant of the length-extension attack can be applied. We can find a tag for a pre-specified formatted message with 2 encryption oracle calls, $2^{64}$ computational cost, and negligible memory.

The Partial Sum Attack is one of the most powerful attacks, independent of the key schedule, developed in the last 15 years against reduced-round versions of AES. In this paper, we introduce a slight improvement to the basic attack which lowers the number of chosen plaintexts needed to successfully mount it. Our version of the attack on 6-round AES can be carried out completely in practice, as we demonstrate providing a full implementation. We also detail the structure of our implementation, showing the performances we achieve.

In 2000 Ko gave potential hard problem is proposed called the Markov problem. We give an algorithm, for certain parameters, for solution of the Markov problem. The Markov problem is related to the knot recognition problem. Hence we also a new algorithm the knot recognition problem. This knot recognition algorithm may be used for previously proposed cryptosystem that uses knots.

Increasing amounts of information that needs to be protecting put in claims specific requirements for information security systems. The main goal of this paper is to find ways to increase performance of cryptographic transformation with public key by increasing performance of integers squaring. Authors use delayed carry mechanism and approaches of effective parallelization for Comba multiplication algorithm, which was previously proposing by authors. They use the idea of carries accumulation by addition products of multiplying the relevant machine words in columns. As a result, it became possible to perform addition of such products in the column independently of each other. However, independent accumulation of products and carries require correction of the intermediate results to account for the accumulated carries. Due to the independence of accumulation in the columns, it became possible to parallelize the process of products accumulation that allowed formulating several approaches. In this paper received theoretical estimates of the computational complexity for proposed squaring algorithms. Software implementations of algorithms in C++ allowed receiving practical results of the performance, which are not contrary to theoretical estimates. The authors first proposed applying the method of delayed carry and parallelization techniques for squaring algorithms, which was previously proposing for integer multiplication.

A computational secret-sharing scheme is a method that enables a dealer, that has a secret, to distribute this secret among a set of parties such that a "qualified" subset of parties can efficiently reconstruct the secret while any "unqualified" subset of parties cannot efficiently learn anything about the secret. The collection of "qualified" subsets is defined by a Boolean function. It has been a major open problem to understand which (monotone) functions can be realized by a computational secret-sharing schemes. Yao suggested a method for secret-sharing for any function that has a polynomial-size monotone circuit (a class which is strictly smaller than the class of monotone functions in P). Around 1990 Rudich raised the possibility of obtaining secret-sharing for all monotone functions in NP: In order to reconstruct the secret a set of parties must be "qualified" and provide a witness attesting to this fact. Recently, Garg et al. (STOC 2013) put forward the concept of witness encryption, where the goal is to encrypt a message relative to a statement "x in L" for a language L in NP such that anyone holding a witness to the statement can decrypt the message, however, if x is not in L, then it is computationally hard to decrypt. Garg et al. showed how to construct several cryptographic primitives from witness encryption and gave a candidate construction. One can show that computational secret-sharing implies witness encryption for the same language. Our main result is the converse: we give a construction of a computational secret-sharing scheme for any monotone function in NP assuming witness encryption for NP and one-way functions. As a consequence we get a completeness theorem for secret-sharing: computational secret-sharing scheme for any single monotone NP-complete function implies a computational secret-sharing scheme for every monotone function in NP.

We clarify and generalize a cube root algorithm in $\mathbb F_q$ proposed by Pocklington, and later rediscovered by Padró and Sáez. We correct some mistakes in the result of Padró and Sáez and give a full generalization of their result. We also give the comparison of the implementation of our proposed algorithm with two most popular cube root algorithms, namely the Adleman-Manders-Miller algorithm and the Cipolla-Lehmer algorithm. To the authors' knowledge, our comparison is the first one which compares three fundamental algorithms together.

The first output bit of TRIVIUM can be considered to be a boolean function of 80 key and 80 IV variables. Choose $n$ ($n\leq 30$) of the key variables and set the other variables to constant values. This gives an $n$-variable boolean function. In this work, we experimentally find examples of such boolean functions which deviate from a uniform random $n$-variable boolean function in a statistically significant manner. This improves upon the previously reported experimental `non-randomness' result using the cube testing methodology by Aumasson et al in 2009 for TRIVIUM restricted to 885 rounds. In contrast, we work with full TRIVIUM and instead of using the cube methodology we directly find the algebraic normal form of the restricted version of the first output bit of TRIVIUM. We note, however, that our work does not indicate any weakness of TRIVIUM. On the other hand, the kind of experiments that we conduct for TRIVIUM can also be conducted for other ciphers.

A very popular trend in code-based cryptography is to decrease the public-key size by focusing on subclasses of alternant/Goppa codes which admit a very compact public matrix, typically quasi-cyclic (QC), quasi-dyadic (QD), or quasi-monoidic (QM) matrices. We show that the very same reason which allows to construct a compact public-key makes the key-recovery problem intrinsically much easier. The gain on the public-key size induces an important security drop, which is as large as the compression factor $p$ on the public-key. The fundamental remark is that from the $k\times n$ public generator matrix of a compact McEliece, one can construct a $k/p \times n/p$ generator matrix which is -- from an attacker point of view -- as good as the initial public-key. We call this new smaller code the {\it folded code}. Any key-recovery attack can be deployed equivalently on this smaller generator matrix. To mount the key-recovery in practice, we also improve the algebraic technique of Faugère, Otmani, Perret and Tillich (FOPT). In particular, we introduce new algebraic equations allowing to include codes defined over any prime field in the scope of our attack. We describe a so-called ``structural elimination'' which is a new algebraic manipulation which simplifies the key-recovery system. As a proof of concept, we report successful attacks on many cryptographic parameters available in the literature. All the parameters of CFS-signatures based on QD/QM codes that have been proposed can be broken by this approach. In most cases, our attack takes few seconds (the harder case requires less than $2$ hours). In the encryption case, the algebraic systems are harder to solve in practice. Still, our attack succeeds against r cryptographic challenges proposed for QD and QM encryption schemes, but there are still some parameters that have been proposed which are out of reach of the methods given here. However, regardless of the key-recovery attack used against the folded code, there is an inherent weakness arising from Goppa codes with QM or QD symmetries. It is possible to derive from the public key a much smaller public key corresponding to the folding of the original QM or QD code, where the reduction factor of the code length is precisely the order of the QM or QD group used for reducing the key size. To summarize, the security of such schemes are not relying on the bigger compact public matrix but on the small folded code which can be efficiently broken in practice with an algebraic attack for a large set of parameters.

Secure multiparty computation (MPC) as a service is becoming a tangible reality. In such a service, a population of clients wish to utilize a set of servers to delegate privately and reliably a given computation on their inputs. MPC protocols have a number of desired properties including tolerating active misbehavior by some of the servers and guaranteed output delivery. A fundamental result is that in order to achieve the above, an honest majority among servers is necessary. There are settings, however, where this condition might be overly restrictive, making it important to investigate models where this impossibility result can be circumvented, allowing secure computation to be performed even when the number of malicious participants outweighs the number of honest participants. To this end, we introduce the two-tier model for MPC, where a set of $m$ parties that are guaranteed to be honest (the first tier) remains "hidden" within a set of $n-m$ servers which are of dubious trustworthiness (the second tier), and where the objective is to perform MPC withstanding a number of active misbehaviors that is larger than $m/2$. Indeed, assuming $\alpha n$ of the second-tier servers are dishonest (where $\alpha\in (0,1)$), we present an MPC protocol that can withstand up to $(1-\epsilon)(1-\alpha)n/2$ additional faults, for any $\epsilon>0$ and $m = \omega(\log n)$. Somewhat surprisingly, this allows the total number of faulty parties to exceed $n/2$ across both tiers. We demonstrate that the two-tier model naturally arises in various settings, as in the case, for example, of a resource-constrained service provider wishing to utilize a pre-existing set of servers.

The design of secure and efficient smart-card-based password authentication schemes remains a challenging problem today despite two decades of intensive research in the security community, and the current crux lies in how to achieve truly two-factor security even if the smart cards can be tampered. In this paper, we analyze two recent proposals in this area, namely, Hsieh-Leu's scheme and Wang's PSCAV scheme. We demonstrate that, under their non-tamper-resistance assumption of the smart cards, both schemes are still prone to offline dictionary attack, in which an attacker can obtain the victim's password when getting temporary access to the victim's smart card. This indicates that compromising a single factor (i.e., the smart card) of these two schemes leads to the downfall of both factors (i.e., both the smart card and the password), thereby invalidating their claim of preserving two-factor security. Remarkably, our attack on the latter protocol, which is not captured in Wang's original protocol security model, reveals a new and realistic attacking scenario and gives rise to the strongest adversary model so far (Note that Wang's PSCAV scheme is secure within its own but weak security model). In addition, we make the first attempt to explain why smart cards, instead of common cheap storage devices (e.g., USB sticks), are preferred in most two-factor authentication schemes for security-critical applications.

We propose a key-policy attribute-based encryption (KP-ABE) scheme with constant-size ciphertexts, whose semi-adaptive security is proven under the decisional linear (DLIN) assumption in the standard model. The access structure is expressive, that is given by non-monotone span programs. It also has fast decryption, i.e., a decryption includes only a constant number of pairing operations. As an application of our KP-ABE construction, we also propose a fully secure attribute-based signatures with constant-size secret (signing) keys from the DLIN. For achieving the above results, we extend the sparse matrix technique on dual pairing vector spaces. In particular, several algebraic properties of an elaborately chosen sparse matrix group are applied to the dual system security proofs.

In the context of authenticated encryption (AE), generic composition has referred to the construction of an AE scheme by gluing together a conventional (privacy-only) encryption scheme and a MAC. Since the work of Bellare and Namprempre (2000) and then Krawczyk (2001), the conventional wisdom has become that there are three forms of generic composition, with Encrypt-then-MAC the only one that generically works. However, many caveats to this understanding have surfaced over the years. Here we explore this issue further, showing how this understanding oversimplifies the situation because it ignores the results’ sensitivity to definitional choices. When encryption is formalized differently, making it either IV-based or nonce-based, rather than probabilistic, and when the AE goal is likewise changed to take in a nonce, qualitatively different results emerge. We explore these alternatives versions of the generic-composition story. We also evidence the overreaching understanding of prior generic-composition results by pointing out that the Encrypt-then-MAC mechanism of ISO 19772 is completely wrong.

Oblivious RAM (ORAM) is a cryptographic primitive that hides memory access patterns to untrusted storage. ORAM may be used in secure processors for encrypted computation and/or software protection. While recursive Path ORAM is currently the most practical ORAM for secure processors, it still incurs large performance and energy overhead and is the performance bottleneck of recently proposed secure processors. In this paper, we propose two optimizations to recursive Path ORAM. First, we identify a type of program locality in its operations to improve performance. Second, we use pseudorandom function to compress the position map. But applying these two techniques in recursive Path ORAM breaks ORAM security. To securely take advantage of the two ideas, we propose unified ORAM. Unified ORAM improves performance both asymptotically and empirically. Empirically, our experiments show that unified ORAM reduces data movement from ORAM by half and improves benchmark performance by 61% as compared to recursive Path ORAM.

This paper introduces a complete side channel analysis toolbox, inclusive of the analog capture hardware, target device, capture software, and analysis software. The highly modular design allows use of the hardware and software with a variety of existing systems. The hardware uses a synchronous capture method which greatly reduces the required sample rate, while also reducing the data storage requirement, and improving synchronization of traces. The synchronous nature of the hardware lends itself to fault injection, and a module to generate glitches of programmable width is also provided. The entire design (hardware and software) is open-source, and maintained in a publicly available repository. Several long example capture traces are provided for researchers looking to evaluate standard cryptographic implementations.

In an implicit authentication system, a user profile is used as an additional factor to strengthen the authentication of mobile users. The profile consists of features that are constructed using the history of user actions on her mobile device over time. The profile is stored on the server and is used to authenticate an access request originated from the device at a later time. An access request will include a vector of recent measurements of the features on the device, that will be subsequently matched against the features stored at the server, to accept or reject the request. The features however include private information such as user location or web sites that have been visited. We propose a privacy-preserving implicit authentication system that achieves implicit authentication without revealing information about the usage profiles of the users to the server. We propose an architecture, give a formal security model and a construction with provable security in two settings where: (i) the device follows the protocol, and (ii) the device is captured and behaves maliciously.

We study the task of efficient verifiable delegation of computation on encrypted data. First, we improve previous definitions in order to tolerate adversaries that learn whether or not clients accept the result of a delegated computation. Then, in this strong model, we show a scheme for arbitrary computations, and we propose highly efficient schemes for delegation of various classes of functions, such as linear combinations, high-degree univariate polynomials, and multivariate quadratic polynomials. Notably, the latter class includes many useful statistics. Using our solution, a client can store a large encrypted dataset with a server, query statistics over this data, and receive encrypted results that can be efficiently verified and decrypted. As a key contribution for the efficiency of our schemes, we develop a novel homomorphic hashing technique that allows us to efficiently authenticate computations, at the same cost as if the data were in the clear, avoiding a $10^4$ overhead, which would occur with a naive approach. We confirm our theoretical analysis with extensive implementation tests that show the practical feasibility of our schemes.

Secure multiparty computation systems are commonly built form a small set of primitive components. Composability of security notions has a central role in the analysis of such systems, since it allows us to deduce security properties of complex protocols from the properties of its components. We show that the standard notions of universally composable security are overly restrictive in this context and can lead to protocols with sub-optimal performance. As a remedy, we introduce a weaker notion of privacy that is satisfied by simpler protocols and is preserved by composition. After that we fix a passive security model and show how to convert a private protocol into a universally composable protocol. As a result, we obtain modular security proofs without performance penalties.

Performance of secure computation is still often an obstacle to its practical adaption. There are different protocols for secure computation that compete for the best performance. In this paper we propose automatic protocol selection which selects a protocol for each operation resulting in a mix with the best performance so far. Based on an elaborate performance model, we propose an optimization algorithm and an efficient heuristic for this selection problem. We show that our mixed protocols achieve the best performance on a set of use cases. Furthermore, our results underpin that the selection problem is so complicated and large in size, that a programmer is unlikely to manually make the optimal selection. Our proposed algorithms nevertheless can be integrated into a compiler in order to yield the best (or near-optimal) performance.

Functional encryption is an emerging paradigm for public-key encryption which enables fine-grained control of access to encrypted data. Doubly-spatial encryption (DSE) captures all functionalities that we know how to realize via pairings-based assumptions, including (H)IBE, IPE, NIPE, CP-ABE and KP-ABE. In this paper, we propose a construction of DSE from the decisional bilinear Diffie-Hellman (DBDH) assumption. This also yields the first non-zero inner product encryption (NIPE) scheme based on DBDH. Quite surprisingly, we know how to realize NIPE and DSE from stronger assumptions in bilinear groups but not from the basic DBDH assumption. Along the way, we present a novel algebraic characterization of *NO* instances for the DSE functionality, which we use crucially in the proof of security.

This paper presents a fast implementation to compute the scalar multiplication of elliptic curve points based on a ``General-Purpose computing on Graphics Processing Units'' (GPGPU) approach. A GPU implementation using Dan Bernstein's Curve25519, an elliptic curve over a 255-bit prime field complying with the new 128-bit security level, computes the scalar multiplication in less than a microsecond on AMD's R9 290X GPU. The presented methods and implementation considerations can be applied to any parallel architecture.

In this short article, we describe a very practical and simple attack on the authentication part of POET authenticated encryption mode proposed at FSE 2014. POET is a provably secure scheme that was designed to resist various attacks where the adversary is allowed to repeat the nonce, or even when the message is output before verifying the validity of the tag when querying the decryption oracle. However, we demonstrate that using only a single encryption query and a negligible amount of computations, even without any special misuse from the attacker, it is possible to generate many valid ciphertext/tag pairs for POET. Our work shows that one should not use POET for any application where authentication property is required. Furthermore, we propose a possible patch to overcome this particular issue, yet without backing up this patch with a security proof.

This paper is structured on securing of storage, transmission and the traceability of digital images. It consists in the design of the cryptographic algorithms appropriate to the case of fixed and moving images. In this sense, we have introduced two approaches that is different in the synthesis of confusion and diffusion on using the principles of substitu-tion and/or transposition to secure JPEG and MPEG format.

We use multilinear maps to provide a solution to the long-standing problem of public-key broadcast encryption where all parameters in the system are small. In our constructions, ciphertext overhead, private key size, and public key size are all poly-logarithmic in the total number of users. The systems are fully collusion-resistant against any number of colluders. All our systems are based on an O(log N)-way multilinear map to support a broadcast system for N users. We present three constructions based on different types of multilinear maps and providing different security guarantees. Our systems naturally give identity-based broadcast systems with short parameters.

In this work we consider two protocols for performing cryptanalysis and security enhancement. The first one by Jiang et al., is a password-based authentication scheme which does not use smart cards. We note that this scheme is an improvement over Chen et al.'s scheme shown vulnerable to the off-line dictionary attack by Jiang et al. We perform a cryptanalysis on Jiang at al.'s improved protocol and observe that it is prone to the clogging attack, a kind of denial of service (DoS) attack. We then suggest an improvement on the protocol to prevent the clogging attack. The other protocol we consider for analysis is by Wang et al. This is a smart card based authentication protocol. We again perform the clogging (DoS) attack on this protocol via replay. We observe that all smart card based authentication protocols which precede the one by Wang et al., and require the server to compute the computationally intensive modular exponentiation are prone to the clogging attack. We suggest (another) improvement on the protocol to prevent the clogging attack, which also applies to the protocol by Jiang et. al.

In this paper JHAE, an authenticated encryption (AE) mode, was presented based on the JH hash mode. JHAE is an on-line and single-pass dedicated AE mode based on permutation that supports optional associated data (AD). It was proved that this mode, based on ideal permutation, achieved privacy and integrity up to O(2n=2) queries where the length of the used permutation was 2n. To decrypt, JHAE did not require the inverse of its underlying permutation and therefore saved area space. JHAE has been used by Artemia, one of the CAESAR candidates.

This paper studies the task of two-sources randomness extractors for elliptic curves defined over finite fields $K$, where $K$ can be a prime or a binary field. In fact, we introduce new constructions of functions over elliptic curves which take in input two random points from two differents subgroups. In other words, for a ginven elliptic curve $E$ defined over a finite field $\mathbb{F}_q$ and two random points $P \in \mathcal{P}$ and $Q\in \mathcal{Q}$, where $\mathcal{P}$ and $\mathcal{Q}$ are two subgroups of $E(\mathbb{F}_q)$, our function extracts the least significant bits of the abscissa of the point $P\oplus Q$ when $q$ is a large prime, and the $k$-first $\mathbb{F}_p$ coefficients of the asbcissa of the point $P\oplus Q$ when $q = p^n$, where $p$ is a prime greater than $5$. We show that the extracted bits are close to uniform. Our construction extends some interesting randomness extractors for elliptic curves, namely those defined in \cite{op} and \cite{ciss1,ciss2}, when $\mathcal{P} = \mathcal{Q}$. The proposed constructions can be used in any cryptographic schemes which require extraction of random bits from two sources over elliptic curves, namely in key exchange protole, design of strong pseudo-random number generators, etc.

We present a new side-channel attack path threatening state-of-the-art protected implementations of elliptic curves embedded scalar multiplications. Regular algorithms such as the double-and-add-always and the Montgomery ladder are commonly used to protect the scalar multiplication from simple side-channel analysis. Combining such algorithms with scalar and/or point blinding countermeasures lead to scalar multiplications protected from all known attacks. Scalar randomization, which consists in adding a random multiple of the group order to the scalar value, is a popular countermeasure due to its efficiency. Amongst the several curves defined for usage in elliptic curves products, the most used are those standardized by the NIST. As observed in several previous publications, the modulus, hence the orders, of these curves are sparse, primarily for efficiency reasons. In this paper, we take advantage of this specificity to present new attack paths which combine vertical and horizontal side-channel attacks to recover the entire secret scalar in state-of-the-art protected elliptic curve implementations

In this paper, we present practical results of data leakages of CMOS devices via the temperature side channel---a side channel that has been widely cited in literature but not well characterized yet. We investigate the leakage of processed data by passively measuring the dissipated heat of the devices. The temperature leakage is thereby linearly correlated with the power leakage model but is limited by the physical properties of thermal conductivity and capacitance. We further present heating faults by operating the devices beyond their specified temperature ratings. The efficiency of this kind of attack is shown by a practical attack on an RSA implementation. Finally, we introduce data remanence attacks on AVR microcontrollers that exploit the Negative Bias Temperature Instability (NBTI) property of internal SRAM cells. We show how to recover parts of the internal memory and present first results on an ATmega162. The work encourages the awareness of temperature-based attacks that are known for years now but not well described in literature. It also serves as a starting point for further research investigations.

Sealed-Bid auction is an efficient and rational method to establish the price in open market. However sealed-bid auctions are sub- ject to bid-rigging attack. Receipt-free mechanisms were proposed to prevent bid-rigging. The prior receipt-free mechanisms are based on two assumptions; firstly, existence of untappable channel between bidders and auction authorities. Secondly, mechanisms assume the authorities to be honest (not colluding). Moreover the bandwidth required to com- municate the receipt-free bids is huge. This paper presents a sealed-bid auction mechanism to resist bid-rigging. The proposed method does not assume untappable channel nor consider the authorities to be necessarily honest. The proposed mechanism also manages the bandwidth efficiently, and improves the performance of the system.

Fischlin’s transformation is an alternative to the standard Fiat-Shamir transform to turn a certain class of public key identification schemes into digital signatures (in the random oracle model). We show that signatures obtained via Fischlin’s transformation are existentially unforgeable even in case the adversary is allowed to get arbitrary (yet bounded) information on the entire state of the signer (including the signing key and the random coins used to generate signatures). A similar fact was already known for the Fiat-Shamir transform, however, Fischlin’s transformation allows for a significantly higher leakage parameter than Fiat-Shamir. Moreover, in contrast to signatures obtained via Fiat-Shamir, signatures obtained via Fischlin enjoy a tight reduction to the underlying hard problem. We use this observation to show (via simulations) that Fischlin’s transformation, usually considered less efficient, outperforms the Fiat-Shamir transform in verification time for a reasonable choice of parameters. In terms of signing Fiat-Shamir is faster for equal signature sizes. Nonetheless, our experiments show that the signing time of Fischlin’s transformation becomes, e.g., 22% of the one via Fiat-Shamir if one allows the signature size to be doubled.

The integral attack is one of the most powerful attack against block ciphers. In this paper, we propose two new techniques for the integral attack, the FFT technique and the key concealment technique. The FFT technique is useful for the integral attack with enormous chosen plaintexts. As the previous result using FFT, Collard et al. showed a new technique which reduces the complexity for the linear attack. In this paper, we review the result of Collard et al. to estimate the complexity in detail, and we show the complexity can be estimated from the number of times using the addition of integers. Moreover, we show that attacks using FFT can be applied to the integral attack. As applications, we show integral attacks against AES and CLEFIA. For AES, we show that 6-round AES can be attacked with about $2^{51.7} additions. For CLEFIA, we show that 12-round CLEFIA can be attacked with about $2^{86.9}$ additions.

Authenticated encryption (AE) has recently gained renewed interest due to the ongoing CAESAR competition. This paper deals with the performance of block cipher modes of operation for AE in parallel software. We consider the example of the AES on Intel's new Haswell microarchitecture that has improved instructions for AES and finite field multiplication. As opposed to most previous high-performance software implementations of operation modes -- that have considered the encryption of single messages -- we propose to process multiple messages in parallel. We demonstrate that this message scheduling is of significant advantage for most modes. As a baseline for longer messages, the performance of AES-CBC encryption on a single core increases by factor 6.8 when adopting this approach. For the first time, we report optimized AES-NI implementations of the novel AE modes OTR, CLOC, COBRA, SILC, McOE-G, POET and Julius -- both with single and multiple messages. For almost all AE modes considered, we obtain a consistent speed-up when processing multiple messages in parallel. Notably, among the nonce-based modes, CCM, CLOC and SILC get by factor 3.7 faster, achieving a performance comparable to GCM (the latter, however, possessing classes of weak keys), with OCB3 still performing at only 0.77 cpb. Among the nonce-misuse resistant modes, McOE-G receives a speed-up by more than factor 4 with a performance of about 1.62 cpb, with COPA consistently performing best at 1.45 cpb.

Oblivious RAMs (ORAMs) have traditionally been measured by their bandwidth overhead and client storage. We observe that when using ORAMs to build secure computation protocols for RAM programs, the size of the ORAM circuits is more relevant to the performance. We therefore embark on a study of the circuit-complexity of several recently proposed ORAM constructions. Our careful implementation and experiments show that asymptotic analysis is not indicative of the true performance of ORAM in secure computation protocols with practical data sizes. We then present SCORAM, a heuristic compact ORAM design optimized for secure computation protocols. Our new design is almost 10x smaller in circuit size and also faster than all other designs we have tested for realistic settings (i.e., memory sizes between 4MB and 2GB, constrained by 2^{-80} failure probability). SCORAM makes it feasible to perform secure computations on gigabyte-sized data sets.

Secret sharing schemes divide a secret among multiple participants so that only authorized subsets of parties can reconstruct it. We show that SETUP (Secretly Embedded Trapdoor with Universal Protection) attack can be embedded in secret sharing schemes that employ enough randomness to give the attacker an overwhelming advantage to access the secret. In case of ideal schemes, a coalition of a few participants (within at least one is the attacker) can succeed the attack, while in case of non-ideal schemes the attacker's knowledge can be enough to reveal the secret. We exemplify the attack against Shamir's threshold scheme, which is the most well-known and used secret sharing scheme. Finally, we consider some prevention techniques against the proposed attack.

ANSI X9.24-1:2009 specifies the key check value, which is used to verify the integrity of the blockcipher key. This value is defined as the most significant bits of the ciphertext of the zero block, and is assumed to be publicly known data for verification. ISO/IEC 9797-1:2011 illustrates a total of ten CBC MACs, where one of these MACs, the basic CBC MAC, is widely known to be insecure. In this paper, we consider the remaining nine CBC MACs and derive the quantitative security impact of using the key check value. We first show attacks against five MACs by taking advantage of the knowledge of the key check value. We then prove that the analysis is tight, in a concrete security paradigm. For the remaining four MACs, we prove that the standard birthday bound still holds even with the presence of the key check value. As a result, we obtain a complete characterization of the impact of using ANSI X9.24-1 key check value with the ISO/IEC 9797-1 MACs.

The TLS Internet Standard features a mixed bag of cryptographic algorithms and constructions, letting clients and servers negotiate their use for each run of the handshake. Although many ciphersuites are now well-understood in isolation, their composition remains problematic, and yet it is critical to obtain practical security guarantees for TLS. We experimentally confirm that all mainstream implementations of TLS share key materials between different algorithms, some of them of dubious strength. We outline attacks in their handling of resumption and renegotiation, stressing the need to model multiple related instances of the handshake. We study the provable security of the TLS handshake, as it is implemented and deployed. To capture the details of the standard and its main extensions, we rely on miTLS, a verified reference implementation of the protocol. miTLS inter-operates with mainstream browsers and servers for many protocol versions, configurations, and ciphersuites; and it provides application-level, provable security for some. We propose new agile security definitions and assumptions for the signatures, key encapsulation mechanisms (KEM), and key derivation algorithms used by the TLS handshake. By necessity, our definitions are stronger than those expected with simple modern protocols. To validate our model of key encapsulation, we prove that both RSA and Diffie-Hellman ciphersuites satisfy our definition for the KEM. In particular, we formalize the use of PKCS#1v1.5 encryption in TLS, including recommended countermeasures against Bleichenbacher attacks, and build a 3,000-line EasyCrypt proof of the security of the resulting master secret KEM against replayable chosen-ciphertext attacks under the assumption that ciphertexts are hard to re-randomize. Based on our new agile definitions, we construct a modular proof of security for the miTLS reference implementation of the handshake, including ciphersuite negotiation, key exchange, renegotiation, and resumption, treated as a detailed 3,600-line executable model. We present our main definitions, constructions, and proofs for an abstract model of the protocol, featuring series of related runs of the handshake with different ciphersuites. We also describe its refinement to account for the whole reference implementation, based on automated verification tools.

In this paper, we propose new non-monotonic attribute-based encryption schemes with compact parameters. The first three schemes are key-policy attribute-based encryption (KP-ABE) and the fourth scheme is ciphertext-policy attribute-based encryption (CP-ABE) scheme. \begin{itemize} \item Our first scheme has very compact ciphertexts. The ciphertext overhead only consists of two group elements and this is the shortest in the literature. Compared to the scheme by Attrapadung et al. (PKC2011), which is the best scheme in terms of the ciphertext overhead, our scheme shortens ciphertext overhead by $33\%$. The scheme also reduces the size of the master public key to about half. \item Our second scheme is proven secure under the decisional bilinear Diffie-Hellman (DBDH) assumption, which is one of the most standard assumptions in bilinear groups. Compared to the non-monotonic KP-ABE scheme from the same assumption by Ostrovsky et al. (ACM-CCS'07), our scheme achieves more compact parameters. The master public key and the ciphertext size is about the half that of their scheme. \item Our third scheme is the first non-monotonic KP-ABE scheme that can deal with unbounded size of set and access policies. That is, there is no restriction on the size of attribute sets and the number of allowed repetition of the same attributes which appear in an access policy. The master public key of our scheme is very compact: it consists of only constant number of group elements. \item Our fourth scheme is the first non-monotonic CP-ABE scheme that can deal with unbounded size of set and access policies. The master public key of the scheme consists of only constant number of group elements. \end{itemize} We construct our KP-ABE schemes in a modular manner. We first introduce special type of predicate encryption that we call two-mode identity based broadcast encryption (TIBBE). Then, we show that any TIBBE scheme that satisfies certain condition can be generically converted into non-monotonic KP-ABE scheme. Finally, we construct efficient TIBBE schemes and apply this conversion to obtain the above new non-monotonic KP-ABE schemes.

RC4 is the most widely used stream cipher around. So, it is important that it runs cost effectively, with minimum encryption time. In other words, it should give higher throughput. In this paper, a mechanism is proposed to improve the throughput of RC4 algorithm in multicore processors using multithreading. The proposed mechanism does not parallelize RC4, instead it introduces a way that multithreading can be used in encryption when the plaintext is in the form of a text file. In this particular research, the source codes were written in Java (JDK version: 1.6.0_21) in Windows environments. Experiments to analyze the throughput were done separately in an Intel® P4 machine (O/S: Windows XP), Core 2 Duo machine (O/S: Windows XP) and Core i3 machine (O/S: Windows 7). Outcome of the research: Higher throughput of RC4 algorithm can be achieved in multicores when using the proposed mechanism in this research. Effective use of multithreading in encryption can be achieved in multicores using this technique.

We study a method for key predistribution in a network of $n$ users where pairwise keys are computed by hashing users' IDs along with secret information that has been (pre)distributed to the network users by a trusted entity. A communication graph $G$ can be specified to indicate which pairs of users should be able to compute keys. We determine necessary and sufficient conditions for schemes of this type to be secure. We also consider the problem of minimizing the storage requirements of such a scheme; we are interested in the total storage as well as the maximum storage required by any user. Minimizing the total storage is NP-hard, whereas minimizing the maximum storage required by a user can be computed in polynomial time.

We initiate the study of the following problem: Suppose Alice and Bob would like to outsource their encrypted private data sets to the cloud, and they also want to conduct the set intersection operation on their plaintext data sets. The straightforward solution for them is to download their outsourced ciphertexts, decrypt the ciphertexts locally, and then execute a commodity two-party set intersection protocol. Unfortunately, this solution is not practical. We therefore motivate and introduce the novel notion of {\em Verifiable Delegated Set Intersection on outsourced encrypted data} (VDSI). The basic idea is to delegate the set intersection operation to the cloud, while (i) not giving the decryption capability to the cloud, and (ii) being able to hold the misbehaving cloud accountable. We formalize security properties of VDSI and present a construction. In our solution, the computational and communication costs on the users are linear to the size of the intersection set, meaning that the efficiency is optimal up to a constant factor.

Simple side-channel attacks trade off data complexity (i.e. the number of side-channel observations needed for a successful attack) with computational complexity (i.e. the number of operations applied to the side-channel traces). In the specific example of Simple Power Analysis (SPA) attacks on the Advanced Encryption Standard (AES), two approaches can be found in the literature, one which is a pragmatic approach that involves basic techniques such as efficient enumeration of key candidates, and one that is seemingly more elegant and uses algebraic techniques. Both of these different techniques have been used in complementary settings: the pragmatic attacks were solely applied to the key schedule whereas the more elegant methods were only applied to the encryption rounds. In this article, we investigate how these methods compare in what we consider to be a more practical setting in which adversaries gain access to erroneous information about both key schedule and encryption rounds. We conclude that the pragmatic enumeration technique better copes with erroneous information which makes it more interesting in practice.

In this work, we explore the connection between witness indistinguishability (WI) and indistinguishability obfuscation (iO). We construct a one-round witness indistinguishable protocol for all of NP based on the the existence of indistinguishability obfuscator (the first candidate construction of indistinguishability obfuscator was recently put forward by Garg et.al. in 2013). Based on our one-round WI, we also construct a two-round oblivious transfer (OT) protocol and by a slight modification of our OT protocol, we get a noninteractive bit commitment scheme.

In open literature there is a lack of focus on Shannon's secrecy of ciphers as a security measurement of symmetric key encryption, hence in this research, Shannon's theories on secrecy of ciphers were used to calculate the average secrecy of each symmetric cipher used in this research. All secrecy and performance analysis were done using a newly created tool. Analysis is done based on the secrecy level and performance of the algorithm. This paper presents an analysis of some of the widely used symmetric key algorithms which fall under the categories of block and stream ciphers together with the two combined algorithms. [DES, TripleDES, AES, RC2, RC4, Hybrid1(TripleDES+RC4) and Hybrid2 (AES+RC4) are used]. Analysis is pivoted around on two measurement criteria under two circumstances which are described later in this paper. All the algorithms are implemented in Core Java using classes available in JAVA package javax.crypto. Separate classes are written to calculate the secrecy of ciphers and the encryption time. And also the tool is created using Core Java with the help of Netbeans IDE. As far as the outcome of the research is concerned, the performances of all stream ciphers are higher than that of block ciphers and the combined algorithms have similar performance level to block ciphers. Secrecy levels of block ciphers are comparatively higher than that of stream ciphers as the history says, it is further proved by Shannon's theories in this research. The combined algorithms have more stable secrecy levels.

In this paper, analysis of a simply modified RC4 algorithm is presented. RC4 is the most widely used stream cipher and it is not considered as a cipher that is strong in security. Many alternatives have been proposed to improve RC4 key generation and pseudo random number generation but the thoughts behind this work is to try out a simple modification of RC4’s PRGA, where we can mention like this: Output = M XOR GeneratedKey XOR j After having done the modification the modified algorithm is tested for its secrecy and performance and analyzed over the variable key length with respect to those of the original RC4. The results show that the modified algorithm is better than the original RC4 in the aspects of secrecy and performance.

Non-malleable codes are a natural relaxation of error correcting/detecting codes that have useful applications in the context of tamper resilient cryptography. Informally, a code is non-malleable if an adversary trying to tamper with an encoding of a given message can only leave it unchanged or modify it to the encoding of a completely unrelated value. This paper introduces an extension of the standard non-malleability security notion – so-called continuous non-malleability – where we allow the adversary to tamper continuously with an encoding. This is in contrast to the standard notion of non-malleable codes where the adversary only is allowed to tamper a single time with an encoding. We show how to construct continuous non-malleable codes in the common split-state model where an encoding consist of two parts and the tampering can be arbitrary but has to be independent with both parts. Our main contributions are outlined below: 1. We propose a new uniqueness requirement of split-state codes which states that it is computationally hard to find two codewords C = (X0;X1) and C0 = (X0;X1') such that both codewords are valid, but X0 is the same in both C and C0. A simple attack shows that uniqueness is necessary to achieve continuous non-malleability in the split-state model. Moreover, we illustrate that none of the existing constructions satisfies our uniqueness property and hence is not secure in the continuous setting. 2. We construct a split-state code satisfying continuous non-malleability. Our scheme is based on the inner product function, collision-resistant hashing and non-interactive zero-knowledge proofs of knowledge and requires an untamperable common reference string. 3. We apply continuous non-malleable codes to protect arbitrary cryptographic primitives against tampering attacks. Previous applications of non-malleable codes in this setting required to perfectly erase the entire memory after each execution and and required the adversary to be restricted in memory. We show that continuous non-malleable codes avoid these restrictions.

We present a novel PUF-based scheme.

RC4 is the most widely used stream cipher around. A lot of modifications of RC4 cipher can be seen in open literature. Most of them enhance the secrecy of the cipher and the security levels have been analyzed theoretically by using mathematics. In this paper, a new effective RC4 cipher is proposed and the security analysis has been done using Shannon’s Secrecy theories where numerical values are obtained to depict the secrecy. The proposed cipher is a combination of Improved RC4 cipher proposed by Jian Xie et al and modified RC4 cipher proposed by T.D.B Weerasinghe, which were published prior to this work. Combination is done in such a way that the concept used in the modified RC4 algorithm is used in the Improved RC4 cipher by Jian Xie et al. Importantly, an immense improvement of performance and secrecy are obtained by this combination. Hence this particular modification of RC4 cipher can be used in software applications where there is a need to improve the throughput as well as secrecy.