Polar codes are a new class of error correcting linear block codes, whose generator matrix is specified by the knowledge of transmission channel parameters, code length and code dimension. Moreover, regarding computational security, it is assumed that an attacker with a restricted processing power has unlimited access to the transmission media. Therefore, the attacker can construct the generator matrix of polar codes, especially in the case of Binary Erasure Channels, on which this matrix can be easily constructed. In this paper, we introduce a novel method to keep the generator matrix of polar codes in secret in a way that the attacker cannot access the required information to decode the intended polar code. With the help of this method, a secret key cryptosystem is proposed based on non-systematic polar codes. In fact, the main objective of this study is to achieve an acceptable level of security and reliability through taking advantage of the special properties of polar codes. The analyses revealed that our scheme resists the typical attacks on the secret key cryptosystems based on linear block codes. In addition, by employing some efficient methods, the key length of the proposed scheme is decreased compared to that of the previous cryptosystems. Moreover, this scheme enjoys other advantages including high code rate, and proper error performance as well.

Chosen Distribution Attacks (CDA) were introduced by Bellare et al. (Asiacrypt '09) to model attacks where an adversary can control the distribution of both messages and random coins used in an encryption scheme. One important restriction in their definition is that the distributions chosen by the adversary cannot depend on the public key being attacked, and they show that some restriction of this form is necessary (for the same reasons that secure deterministic encryption is impossible if we allow arbitrary dependence between the plaintext distributions and the public key). Subsequently Raghunathan et al. (Eurocrypt '13) showed how to relax this restriction by allowing the message/randomness distributions to depend on the public key as long as the distributions belong to a family of bounded size fixed before the public key is known. We extend the definition further to what we call Strong Chosen Distribution Attacks where the message/randomness distributions may depend on the public key as long as certain entropy conditions are satisfied. Our security model comes from a natural model of attack where an adversary infiltrates the encryption system and installs a trojan program prior to knowing the public key, and subsequently is allowed limited communication with the trojan program. We present secure constructions in the standard and random oracle models both with and without decryption oracles (corresponding to CPA or CCA security). We also prove that our definition simultaneously generalizes previous definitions in this line of work.

We present a construction of a CCA2-secure encryption scheme from a plaintext aware, weakly simulatable public key encryption scheme. The notion of plaintext aware, weakly simulatable public key encryption has been considered previously by Myers, Sergi and shelat (SCN, 2012) and natural encryption schemes such as the Damgård Elgamal Scheme (Damgård, Crypto, 1991) and the Cramer-Shoup Lite Scheme (Cramer and Shoup, SIAM J. Comput., 2003) were shown to satisfy these properties. Recently, Myers, Sergi and shelat (SCN, 2012) defined an extension of non-malleable CCA1 security, called cNM-CCA1, and showed how to construct a cNM-CCA1-secure encryption scheme from a plaintext aware and weakly simulatable public key encryption scheme. Our work extends and improves on this result by showing that a full CCA2-secure encryption scheme can be constructed from the same assumptions.

Fault attacks against embedded circuits enabled to define many new attack paths against secure circuits. Every attack path relies on a specific fault model which defines the type of faults that the attacker can perform. On embedded processors, a fault model consisting in an assembly instruction skip can be very useful for an attacker and has been obtained by using several fault injection means. To avoid this threat, some countermeasure schemes which rely on temporal redundancy have been proposed. Nevertheless, double fault injection in a long enough time interval is practical and can bypass those countermeasure schemes. Some fine-grained countermeasure schemes have also been proposed for specific instructions. However, to the best of our knowledge, no approach that enables to secure a generic assembly program in order to make it fault-tolerant to instruction skip attacks has been formally proven yet. In this paper, we provide a fault-tolerant replacement sequence for almost all the instructions of the Thumb-2 instruction set and provide a formal verification for this fault tolerance. This simple transformation enables to add a reasonably good security level to an embedded program and makes practical fault injection attacks much harder to achieve.

In this paper, we propose efficient protocols to obliviously execute non-deterministic and deterministic finite automata (NFA and DFA) in the arithmetic black box (ABB) model. In contrast to previous approaches, our protocols do not use expensive public-key operations, relying instead only on computation with secret-shared values. Additionally, the complexity of our protocols is largely offline. In particular, if the DFA is available during the precomputation phase, then the online complexity of evaluating it on an input string requires a small constant number of operations per character. This makes our protocols highly suitable for certain outsourcing applications.

Related key attacks (RKAs) are powerful cryptanalytic attacks where an adversary can change the secret key and observe the effect of such changes at the output. The state of the art in RKA security protects against an a-priori unbounded number of certain algebraic induced key relations, e.g., affine functions or polynomials of bounded degree. In this work, we show that it is possible to go beyond the algebraic barrier and achieve security against arbitrary key relations, by restricting the number of tampering queries the adversary is allowed to ask for. The latter restriction is necessary in case of arbitrary key relations, as otherwise a generic attack of Gennaro et al. (TCC 2004) shows how to recover the key of almost any cryptographic primitive. We describe our contributions in more detail below. 1) We show that standard ID and signature schemes constructed from a large class of $\Sigma$-protocols (including the Okamoto scheme, for instance) are secure even if the adversary can arbitrarily tamper with the prover’s state a bounded number of times and obtain some bounded amount of leakage. Interestingly, for the Okamoto scheme we can allow also independent tampering with the public parameters. 2) We show a bounded tamper and leakage resilient CCA secure public key cryptosystem based on the DDH assumption. We first define a weaker CPA-like security notion that we can instantiate based on DDH, and then we give a general compiler that yields CCA-security with tamper and leakage resilience. This requires a public tamper-proof common reference string. 3) Finally, we explain how to boost bounded tampering and leakage resilience (as in 1. and 2. above) to continuous tampering and leakage resilience, in the so-called floppy model where each user has a personal hardware token (containing leak- and tamper-free information) which can be used to refresh the secret key. We believe that bounded tampering is a meaningful and interesting alternative to avoid known impossibility results and can provide important insights into the security of existing standard cryptographic schemes.

We propose two systematic methods to describe the differential property of an S-box with linear inequalities based on logical condition modelling and computational geometry respectively. In one method, inequalities are generated according to some conditional differential properties of the S-box; in the other method, inequalities are extracted from the H-representation of the convex hull of all possible differential patterns of the S-box. For the second method, we develop a greedy algorithm for selecting a given number of inequalities from the convex hull. Using these inequalities combined with Mixed-integer Linear Programming (MILP) technique, we propose an automatic method for evaluating the security of bit-oriented block ciphers against the (related-key) differential attack, and several techniques for obtaining tighter security bounds. We successfully prove that the 24-round PRESENT-80 is secure enough to resist against standard related-key differential attacks based on differential characteristic, and the probability of the best related-key differential characteristic of the full LBlock is upper bounded by $2^{-60}$. These are the tightest security bounds with respect to the related-key differential attack published so far for PRESENT-80 and LBlock. ~~~~Moreover, we present a new tool for finding (related-key) differential characteristics automatically for bit-oriented block ciphers. Using this tool, we obtain new single-key or related-key differential characteristics for SIMON48, LBlock, DESL and PRESENT-128, which cover larger number of rounds or have larger probability than all previously known results. The methodology presented in this paper is generic, automatic and applicable to many bit-oriented block ciphers.

The MMB block cipher (Modular Multiplication-based Block cipher) is an iterative block cipher designed by Daemen, Govaerts, and Vandewalle in 1993 as an improvement of the PES and IPES ciphers. In this paper we present several new related-key differential characteristics of MMB. These characteristics can be used to form several related-key boomerangs to attack the full MMB. Using 2^{20} adaptive chosen plaintexts and ciphertexts we recover all key bits in 2^{35} time for the full MMB. Our attack was experimentally verified, and it takes less than 15 minutes on a standard Intel i5 machine to recover the full MMB key. After showing this practical attack on the full key of the full MMB, we present partial attacks on extended versions of MMB with up to 9 rounds (which is three more rounds than in the full MMB). We recover 62 out of the 128-bit key in time of 2^{29.2} for 7-round MMB, using 2^{20} adaptive chosen plaintexts and ciphertexts encrypted under 4 related-keys, and time of 2^{29} for 8-round MMB using 2^{20} adaptive chosen plaintexts and ciphertexts, encrypted under 6 related-keys. We show how an adversary can recover 31 out of the 128-bit key for the 9-round MMB in time of 2^{27.8} using 2^{19} adaptive chosen plaintexts and ciphertexts, encrypted under only 2 related-keys. We also show how the time complexity of all attacks can be reduced by partially precomputing the difference distribution table of MMB's components.

The iterated Even-Mansour (EM) scheme is a generalization of the original 1-round construction proposed in 1991, and can use one key, two keys, or completely independent keys. In this paper, we methodically analyze the security of all the possible iterated Even-Mansour schemes with two $n$-bit keys and up to four rounds, and show that none of them provides more than $n$-bit security. Our attacks are based on a new cryptanalytic technique called \emph{multibridge} which splits the cipher to different parts in a novel way, such that they can be analyzed independently, exploiting its self-similarity properties. After the analysis of the parts, the key suggestions are efficiently joined using a meet-in-the-middle procedure. As a demonstration of the multibridge technique, we devise a new attack on 4 steps of the LED-128 block cipher, reducing the time complexity of the best known attack on this scheme from $2^{96}$ to $2^{64}$. Furthermore, we show that our technique can be used as a generic key-recovery tool, when combined with some statistical distinguishers (like those recently constructed in reflection cryptanalysis of GOST and PRINCE).

In the recent breakthrough paper by Barbulescu, Gaudry, Joux and Thomë, a quasi-polynomial time algorithm (QPA) is proposed for the discrete logarithm problem over finite fields of small characteristic. The time complexity analysis of the algorithm is based on several heuristics presented in their paper. We show that some of the heuristics are problematic in their original forms, in particular, when the field is not a Kummer extension. We believe that the basic idea behind the new approach should still work, and propose a fix to the algorithm in non-Kummer cases, without altering the quasi-polynomial time complexity. The modified algorithm is also heuristic. Further study is required in order to fully understand the effectiveness of the new approach.

The first step in elliptic curve scalar multiplication algorithms based on scalar decompositions using efficient endomorphisms---including Gallant--Lambert--Vanstone (GLV) and Galbraith--Lin--Scott (GLS) multiplication, as well as higher-dimensional and higher-genus constructions---is to produce a short basis of a certain integer lattice involving the eigenvalues of the endomorphisms. The shorter the basis vectors, the shorter the decomposed scalar coefficients, and the faster the resulting scalar multiplication. Typically, knowledge of the eigenvalues allows us to write down a long basis, which we then reduce using the Euclidean algorithm, Gauss reduction, LLL, or even a more specialized algorithm. In this work, we use elementary facts about quadratic rings to immediately write down a short basis of the lattice for the GLV, GLS, GLV+GLS, and Q-curve constructions on elliptic curves, and for genus 2 real multiplication constructions. We do not pretend that this represents a significant optimization in scalar multiplication, since the lattice reduction step is always an offline precomputation---but it does give a better insight into the structure of scalar decompositions. In any case, it is always more convenient to use a ready-made short basis than it is to compute a new one.

Let $G:\bits^n\to\bits^m$ be a pseudorandom generator. We say that a circuit implementation of $G$ is {\em $(k,q)$-robust} if for every set $S$ of at most $k$ wires anywhere in the circuit, there is a set $T$ of at most $q|S|$ outputs, such that conditioned on the values of $S$ and $T$ the remaining outputs are pseudorandom. We initiate the study of robust PRGs, presenting explicit and non-explicit constructions in which $k$ is close to $n$, $q$ is constant, and $m>>n$. These include unconditional constructions of robust $r$-wise independent PRGs and small-bias PRGs, as well as conditional constructions of robust cryptographic PRGs. In addition to their general usefulness as a more resilient form of PRGs, our study of robust PRGs is motivated by cryptographic applications in which an adversary has a local view of a large source of secret randomness. We apply robust $r$-wise independent PRGs towards reducing the randomness complexity of private circuits and protocols for secure multiparty computation, as well as improving the ``black-box complexity'' of constant-round secure two-party computation.

We state a switching lemma for tests on adversarial inputs involving bilinear pairings in hard groups, where the tester can effectively switch the randomness used in the test from being given to the adversary at the outset to being chosen after the adversary commits its input. The switching lemma can be based on any $k$-linear hardness assumptions on one of the groups. In particular, this enables convenient information theoretic arguments in the construction of sequence of games proving security of cryptographic schemes, mimicking proofs and constructions in the random oracle model. As an immediate application, we show that the quasi-adaptive NIZK proofs of Jutla and Roy [AsiaCrypt 2013] for linear subspaces can be further shortened to \emph{constant}-size proofs, independent of the number of witnesses and equations. In particular, under the XDH assumption, a length $n$ vector of group elements can be proven to belong to a subspace of rank $t$ with a quasi-adaptive NIZK proof consisting of just a single group element. Similar quasi-adaptive aggregation of proofs is also shown for Groth-Sahai NIZK proofs of linear multi-scalar multiplication equations, as well as linear pairing-product equations (equations without any quadratic terms).

We present an Attribute Based Encryption system where access policies are expressed as polynomial size arithmetic circuits. We prove security against arbitrary collusions of users based on the learning with errors problem on integer lattices. The system has two additional useful properties: first, it naturally handles arithmetic circuits with arbitrary fan-in (and fan-out) gates. Second, secret keys are much shorter than in previous schemes: secret key size is proportional to the depth of the circuit where as in previous constructions the key size was proportional to the number of gates or wires in the circuit. The system is well suited for environments where access policies are naturally expressed as arithmetic circuits as is the case when policies capture statistical properties of the data or depend on arithmetic transformations of the data. The system also provides complete key delegation capabilities.

An evasive circuit family is a collection of circuits C such that for every input x, a random circuit from C outputs 0 on x with overwhelming probability. We provide a combination of definitional, constructive, and impossibility results regarding obfuscation for evasive functions: - The (average case variants of the) notions of virtual black box obfuscation (Barak et al, CRYPTO '01) and virtual gray box obfuscation (Bitansky and Canetti, CRYPTO '10) coincide for evasive function families. We also define the notion of input-hiding obfuscation for evasive function families, stipulating that for a random c \in C it is hard to find, given O(c), a value outside the preimage of 0. Interestingly, this natural definition, also motivated by applications, is likely not implied by the seemingly stronger notion of average-case virtual black-box obfuscation. - If there exist average-case virtual gray box obfuscators for all evasive function families, then there exist (quantitatively weaker) average-case virtual gray obfuscators for all function families. - There does not exist a worst-case virtual black box obfuscator even for evasive circuits, nor is there an average-case virtual gray box obfuscator for evasive Turing machine families. - Let C be an evasive circuit family consisting of functions that test if a low-degree polynomial (represented by an efficient arithmetic circuit) evaluates to zero modulo some large prime p. Then under a natural analog of the discrete logarithm assumption in a group supporting multilinear maps, there exists an input-hiding obfuscator O for C. Under a new perfectly-hiding multilinear encoding assumption, there is an average-case virtual black box obfuscator for the family C.

This note describes a Diffie-Hellman oracle, constructed using standard Trusted Platform Module (TPM) signature APIs. The oracle allows one to compute the exponentiation of an arbitrary group element to a specified TPM-protected private key. By employing the oracle, the security provided by a group of order p is reduced by log k bits, provided k oracle queries are made and p +/- 1 is divisible by k. The security reduction follows from a straightforward application of results from Brown and Gallant (IACR ePrint 2004/306) and Cheon (Eurocrypt 2006) on the strong Diffie-Hellman problem. On a more positive note, the oracle may allow a wider range of cryptographic protocols to make use of the TPM.

Despite all the research efforts made so far, the design of protocols for password-authenticated key exchange (PAKE) still remains a non-trivial task. One of the major challenges in designing such protocols is to protect low-entropy passwords from the notorious dictionary attacks. In this work, we revisit Abdalla and Pointcheval's three-party PAKE protocol presented in Financial Cryptography 2005, and demonstrate that the protocol is vulnerable to an off-line dictionary attack whereby a malicious client can find out the passwords of other clients.

We show that indistinguishability obfuscation implies that all functions with sufficient ``pseudo-entropy'' cannot be obfuscated under a virtual black box definition with a universal simulator. Let ${\cal F}=\{f_s\}$ be a circuit family with super-polynomial pseudo-entropy, and suppose ${\cal O}$ is a candidate obfuscator with universal simulator $\Sim$. We demonstrate the existence of an adversary $\Adv$ that, given the obfuscation ${\cal O}(f_s)$, learns a predicate the simulator $\Sim$ cannot learn from the code of $\Adv$ and black-box access to $f_s$. Furthermore, this is true in a strong sense: for \emph{any} secret predicate $P$ that is not learnable from black-box access to $f_s$, there exists an adversary that given ${\cal O}(f_s)$ efficiently recovers $P(s)$, whereas given oracle access to $f_s$ and given the code of the adversary, it is computationally hard to recover $P(s)$. We obtain this result by exploiting a connection between obfuscation with a universal simulator and obfuscation with auxiliary inputs, and by showing new impossibility results for obfuscation with auxiliary inputs.

The anonymous communication protocol Tor constitutes the most widely deployed technology for providing anonymity for user communication over the Internet. Several frameworks have been proposed that show strong anonymity guarantees; none of these, however, are capable of modeling the class of traffic-related timing attacks against Tor, such as traffic correlation and website fingerprinting. In this work, we present TUC: the first framework that allows for establishing strong anonymity guarantees in the presence of time-sensitive adversaries that mount traffic-related timing attacks. TUC incorporates a comprehensive notion of time in an asynchronous communication model with sequential activation, while offering strong compositionality properties for security proofs. We apply TUC to evaluate a novel countermeasure for Tor against website fingerprinting attacks. Our analysis relies on a formalization of the onion routing protocol that underlies Tor and proves rigorous anonymity guarantees in the presence of traffic-related timing attacks.

SIMON is a family of lightweight block ciphers that was proposed by U.S National Security Agency (NSA). A cipher in this family with $K$-bit key and $N$-bit block is called SIMON ${N}/{K}$. In this paper we analyze the security of SIMON against linear cryptanalysis. We present several linear characteristics for all variants of SIMON with reduced number of rounds. Our best linear characteristic covers SIMON 32/64 reduced to 13 rounds out of 32 rounds with the bias of $2^{-16}$. In addition, we describe a connection between linear and differential characteristics for SIMON. This connection is then exploited by using the differential characteristics of the previous work of Abed \textit{et al.} to construct linear characteristics presented in this work. Our attacks extend to all variants of SIMON covering more number of rounds compared to the previous results on linear cryptanalysis. We have implemented our attacks for small scale variants of SIMON and our experiments confirm the theoretical bias of various characteristics presented in this work. %We also verified the results for SIMON32/64 experimentally to see whether implementation confirms theory. So far, our results are the best known with respect to linear cryptanalysis for any variant of SIMON.

Groth-Sahai proofs are efficient non-interactive zero-knowledge proofs that have found widespread use in pairing-based cryptography. We propose efficiency improvements of Groth-Sahai proofs in the SXDH setting, which is the one that yields the most efficient non-interactive zero-knowledge proofs. - We replace some of the commitments with ElGamal encryptions, which reduces the prover's computation and for some types of equations reduces the proof size. - Groth-Sahai proofs are zero-knowledge when no public elements are paired to each other. We observe that they are also zero-knowledge when base elements for the groups are paired to public constants. - The prover's computation can be reduced by letting her pick her own common reference string. By giving a proof she has picked a valid common reference string this does not compromise soundness. - We define a type-based commit-and-prove scheme, which allows commitments to be reused in many different proofs.

While multiparty computations are becoming more and more efficient, their performance has not yet reached the level needed to be widely deployed for many applications. Nevertheless, the heterogeneous environment of modern computing needs this functionality in order to provide users their right to privacy. For a wide range of applications there is no need for complex computations; operations such as multiplication or addition might be sufficient. In this work we introduce a new multiparty computation protocol (MPC) for multi-round summation whose security is based on DDH in the semihonest model. We also introduce the concept of an anonymous aggregation system that combines MPC with ``blinded'' aggregation so that the aggregate values may remain hidden from the aggregator, and show how to achieve this with our MPC protocol. We give results on the performance of our solution and discuss suitable applications.

Let $E_p$ be an elliptic curve over a prime finite field $\Fp$, $p\ge5$, and $P_p,Q_p\in E_p(\Fp)$. The elliptic curve discrete logarithm problem, ECDLP, on $E_p$ is to find $m_p\in\mathbb{F}_p^{\times}$ such that $Q_p=m_p P_p$ if $Q_p\in\langle P_p\rangle$. We propose an algorithm to attack the ECDLP relying on a Hasse principle detecting linear dependence in Mordell-Weil groups of elliptic curves via a finite number of reductions.

In order to protect the proxy signers’ privacy, many anonymous proxy signature schemes which are also called proxy ring signatures, have been proposed. Although the provable security in the random oracle model has received a lot of criticism, there is no provable secure anonymous proxy signature scheme without random oracles. In this paper, we propose the first provable secure anonymous proxy signature scheme without random oracles which is the combination of proxy signature and ring signa-ture. For the security analysis, we categorize the adversaries into three types accord-ing to different resources they can get and prove in the standard model that, our pro-posal is anonymous against full key exposure and existential unforgeable against all kinds of adversaries with the computational Diffie–Hellman and the subgroup hiding assumptions in bilinear groups.

The authentication encryption (AE) scheme based on the duplex construction can no be paralellized at the algorithmic level. To be competitive with some block cipher based modes like OCB (Offset CodeBook) or GCM (Galois Counter Mode), a scheme should allow parallel processing. In this note we show how parallel AE can be realized within the framework provided by the duplex construction. The first variant, pointed by the duplex designers, is a tree-like structure. Then we simplify the scheme replacing the final node by the bitwise xor operation and show that such a scheme has the same security level.

An asymmetric pairing over groups of composite order is a bilinear map $e: G_1 \times G_2 \to G_T$ for groups $G_1$ and $G_2$ of composite order $N=pq$. We observe that a recent construction of pairing-friendly elliptic curves in this setting by Boneh, Rubin, and Silverberg exhibits surprising and unprecedented structure: projecting an element of the order-$N^2$ group $G_1 \oplus G_2$ onto the bilinear groups $G_1$ and $G_2$ requires knowledge of a trapdoor. This trapdoor, the square root of a certain number modulo $N$, seems strictly weaker than the trapdoors previously used in composite-order bilinear cryptography. In this paper, we describe, characterize, and exploit this surprising structure. It is our thesis that the additional structure available in these curves will give rise to novel cryptographic constructions, and we initiate the study of such constructions. Both the subgroup hiding and SXDH assumptions appear to hold in the new setting; in addition, we introduce custom-tailored assumptions designed to capture the trapdoor nature of the projection maps into $G_1$ and $G_2$. Using the old and new assumptions, we describe an extended variant of the Boneh-Goh-Nissim cryptosystem that allows a user, at the time of encryption, to restrict the homomorphic operations that may be performed. We also present a variant of the Groth-Ostrovsky-Sahai NIZK, and new anonymous IBE, signature, and encryption schemes.

Physical Unclonable Functions (PUFs) are increasingly becoming a well-known security primitive for secure key storage and anti-counterfeiting. For both applications it is imperative that PUFs provide enough entropy. The aim of this paper is to propose a new model for binary-output PUFs such as SRAM, DFF, Latch and Buskeeper PUFs, and a method to accurately estimate their entropy. In our model the measurable property of a PUF is its set of cell biases. We determine an upper bound on the ‘extractable entropy’, i.e. the number of key bits that can be robustly extracted, by calculating the mutual information between the bias measurements done at enrollment and reconstruction. In previously known methods only uniqueness was studied using information-theoretic measures, while robustness was typically expressed in terms of error probabilities or distances. It is not always straightforward to use a combination of these two metrics in order to make an informed decision about the performance of different PUF types. Our new approach has the advantage that it simultaneously captures both of properties that are vital for key storage: uniqueness and robustness. Therefore it will be possible to fairly compare performance of PUF implementations using our new method. Statistical validation of the new methodology shows that it clearly captures both of these properties of PUFs. In other words: if one of these aspects (either uniqueness or robustness) is less than optimal, the extractable entropy decreases. Analysis on a large database of PUF measurement data shows very high entropy for SRAM PUFs, but rather poor results for all other memory-based PUFs in this database.

The problem of fair and privacy-preserving ordered set reconciliation arises in a variety of applications like auctions, e-voting, and appointment reconciliation. While several multi-party protocols have been proposed that solve this problem in the semi-honest model, there are no multi-party protocols that are secure in the malicious model so far. In this paper, we close this gap. Our newly proposed protocols are shown to be secure in the malicious model based on a variety of novel non-interactive zero-knowledge-proofs. We describe the implementation of our protocols and evaluate their performance in comparison to protocols solving the problem in the semi-honest case.

We present a new generic construction of a public-key encryption (PKE) scheme secure against leakage-resilient chosen-ciphertext attacks (LR-CCA), from any Hash Proof System (HPS) and any one-time lossy filter (OT-LF). Efficient constructions of HPSs and OT-LFs from the DDH and DCR assumptions suggest that our construction is a practical approach to LR-CCA security. Most of practical PKEs with LR-CCA security, like variants of Cramer-Shoup scheme, rooted from Hash Proof Systems, but with leakage rates at most $1/4-o(1)$ (defined as the ratio of leakage amount to secret-key size). The instantiations of our construction from the DDH and DCR assumptions result in LR-CCA secure PKEs with leakage rate of $1/2-o(1)$. On the other hand, our construction also creates a new approach for constructing IND-CCA secure (leakage-free) PKE schemes, which may be of independent interest.

We construct secret-key encryption (SKE) schemes that are secure against related-key attacks and in the presence of key-dependent messages (RKA-KDM secure). We emphasize that RKA-KDM security is not merely the conjunction of individual security properties, but covers attacks in which ciphertexts of key-dependent messages under related keys are available. Besides being interesting in their own right, RKA-KDM secure schemes allow to garble circuits with XORs very efficiently (Applebaum, TCC 2013). Until now, the only known RKA-KDM secure SKE scheme (due to Applebaum) is based on the LPN assumption. Our schemes are based on various other computational assumptions, namely DDH, LWE, QR, and DCR. We abstract from Applebaum’s construction and proof, and formalize three generic technical properties that imply RKA-KDM security: one property is IND-CPA security, and the other two are the existence of suitable oracles that produce ciphertexts under related keys, resp. of key-dependent messages. We then give simple SKE schemes that achieve these properties. Our constructions are variants of known KDM-secure public-key encryption schemes. To additionally achieve RKA security, we isolate suitable homomorphic properties of the underlying schemes in order to simulate ciphertexts under related keys in the security proof. From a conceptual point of view, our work provides a generic and extensible way to construct encryption schemes with multiple special security properties.

This paper describes several new improvements of modular arithmetic and how to exploit them in order to gain more efficient implementations of commonly used algorithms, especially in cryptographic applications. We further present a new record for modular multiplications per second on a single desktop computer as well as a new record for the ECM factoring algorithm. This new results allow building personal computers which can handle more than 3 billion modular multiplications per second for a 192 bit module at moderate costs using modern graphic cards.

Boldyreva et al. introduced the notion of multiple forking (MF) as an extension of (general) forking to accommodate nested oracle replay attacks. The primary objective of a (multiple) forking algorithm is to separate out the oracle replay attack from the actual simulation of protocol to the adversary, and this is achieved through the intermediary of a so-called wrapper algorithm. Multiple forking has turned out to be a useful tool in the security argument of several cryptographic protocols. However, a reduction employing the MF Algorithm incurs a significant degradation of O(q^2n), where q denotes the upper bound on the underlying random oracle calls and n, the number of forking. In this work we take a closer look at the reasons for the degradation with a tighter security bound in mind. We nail down the exact set of conditions for the success of the MF Algorithm. A careful analysis of the protocols (and corresponding security argument) employing multiple forking allow us to relax the overly restrictive conditions of the original MF Algorithm. To achieve this, we club two consecutive invocations of the underlying wrapper into a single logical unit of wrapper Z. We then use Z to formulate the notion of "dependence" and "independence" among different rounds of the wrapper in the MF Algorithm. The (in)dependence conditions lead to a general framework for multiple forking and significantly better bound for the MF Algorithm. Leveraging (in)dependence to the full reduces the degradation from O(q^2n) to O(q^n). By implication, the cost of a forking involving two random oracles (augmented forking) matches that involving a single random oracle (elementary forking). Finally, we study the effect of these observations on the security of the existing schemes. We conclude that by careful design of the protocol (and the wrapper in the security reduction) it is possible to harness our observations to the full extent.

We initiate the study of {\em extractability obfuscation}, a notion first suggested by Barak et al. (JACM 2012): An extractability obfuscator eO for a class of algorithms M guarantees that if an efficient attacker A can distinguish between obfuscations eO(M_1), eO(M_2) of two algorithms M_1,M_2 \in M, then A can efficiently recover (given M_1 and M_2) an input on which M_1 and M_2 provide different outputs. - We rely on the recent candidate virtual black-box obfuscation constructions to provide candidate constructions of extractability obfuscators for NC^1; next, following the blueprint of Garg et~al. (FOCS 2013), we show how to bootstrap the obfuscator for NC^1 to an obfuscator for all non-uniform polynomial-time Turing machines. In contrast to the construction of Garg et al., which relies on indistinguishability obfuscation for NC^1, our construction enables succinctly obfuscating non-uniform {\em Turing machines} (as opposed to circuits), without turning running-time into description size. - We introduce a new notion of {\em functional witness encryption}, which enables encrypting a message m with respect to an instance x, language L, and function f, such that anyone (and only those) who holds a witness w for x\in L can compute f(m,w) on the message and particular known witness. We show that functional witness encryption is, in fact, equivalent to extractability obfuscation. - We demonstrate other applications of extractability extraction, including the first construction of fully (adaptive-message) indistinguishability-secure functional encryption for an unbounded number of key queries and unbounded message spaces. - We finally relate indistinguishability obfuscation and extractability obfuscation and show special cases when indistinguishability obfuscation can be turned into extractability obfuscation.

A PAKR (Password-Authenticated Key Retrieval) protocol and its multi-server system allow one party (say, client), who has a rememberable password, to retrieve a long-term static key in an exchange of messages with at least one other party (say, server) that has a private key associated with the password. In this paper, we analyze the only one PAKR (named as PKRS-1) standardized in IEEE 1363.2 [9] and its multi-server system (also, [11]) by showing that any passive/active attacker can find out the client's password and the static key with off-line dictionary attacks. This result is contrary to the security statement of PKRS-1 (see Chapter 10.2 of IEEE 1363.2 [9]).

In January 2013, the Stribog hash function officially replaced GOST R 34.11-94 as the new Russian cryptographic hash standard GOST R 34.11-2012. Stribog is an AES-based primitive and is considered as an asymmetric reply to the new SHA-3 selected by NIST. In this paper we investigate the structural integral properties of reduced version of the Stribog compression function and its internal permutation. Specifically, we present a forward and backward higher order integrals that can be used to distinguish 4 and 3.5 rounds, respectively. Moreover, using the start from the middle approach, we combine the two proposed integrals to get 6.5-round and 7.5-round distinguishers for the internal permutation and 6-round and 7-round distinguishers for the compression function.

In this note we describe some general-purpose, high-efficiency elliptic curves tailored for security levels beyond $2^{128}$. For completeness, we also include legacy-level curves at standard security levels. The choice of curves was made to facilitate state-of-the-art implementation techniques.

We present a new technique to realize attribute-based encryption (ABE) schemes secure in the standard model against chosen-ciphertext attacks (CCA-secure). Our approach is to extend certain concrete chosen-plaintext secure (CPA-secure) ABE schemes to achieve more efficient constructions than the known generic constructions of CCA-secure ABE schemes. We restrict ourselves to the construction of attribute-based key encapsulation mechanisms (KEMs) and present two concrete CCA-secure schemes: a key-policy attribute-based KEM that is based on Goyal's key-policy ABE and a ciphertext-policy attribute-based KEM that is based on Waters' ciphertext-policy ABE. To achieve our goals, we use an appropriate hash function and need to extend the public parameters and the ciphertexts of the underlying CPA-secure encryption schemes only by a single group element. Moreover, we use the same hardness assumptions as the underlying CPA-secure encryption schemes.

With increasing popularity of cloud storage, efficiently proving the integrity of data stored at an untrusted server has become significant. Authenticated Skip Lists and Rank-based Authenticated Skip Lists (RBASL) have been used to provide support for provable data update operations in cloud storage. However, in a dynamic file scenario, an RBASL falls short when updates are not proportional to a fixed block size; such an update to the file, even if small, may result in O(n) block updates to the RBASL, for a file with n blocks. To overcome this problem, we introduce FlexList: Flexible Length-Based Authenticated Skip List. FlexList translates variable-size updates to O(u/B) insertions, removals, or modifications, where u is the size of the update, and B is the (average) block size. We further present various optimizations on the four types of skip lists (regular, authenticated, rank-based authenticated, and FlexList). We build such a structure in O(n) time, and parallelize this operation for the first time. We compute one single proof to answer multiple (non-)membership queries and obtain efficiency gains of 35%, 35% and 40% in terms of proof time, energy, and size, respectively. We propose a method of handling multiple updates at once, achieving efficiency gains of up to 60% at the server side and 90% at the client side. We also deployed our implementation of FlexDPDP (DPDP with FlexList instead of RBASL) on the PlanetLab, demonstrating that FlexDPDP performs comparable to the most efficient static storage scheme (PDP), while providing dynamic data support.

Motivated by the advantages of using elliptic curves for discrete logarithm-based public-key cryptography, there is an active research area investigating the potential of using hyperelliptic curves of genus 2. For both types of curves, the best known algorithms to solve the discrete logarithm problem are generic attacks such as Pollard rho, for which it is well-known that the algorithm can be sped up when the target curve comes equipped with an efficiently computable automorphism. In this paper we incorporate all of the known optimizations (including those relating to the automorphism group) in order to perform a systematic security assessment of two elliptic curves and two hyperelliptic curves of genus 2. We use our software framework to give concrete estimates on the number of core years required to solve the discrete logarithm problem on four curves that target the 128-bit security level: on the standardized NIST CurveP-256, on a popular curve from the Barreto-Naehrig family, and on their respective analogues in genus 2.

We show that if $\NP \neq co-RP$ then the existence of efficient indistinguishability obfuscation (\iO) implies the existence of one-way functions. Thus, if we live in ``Pessiland", where $\NP$ problems are hard on the average but one-way functions do not exist, or even in ``Heuristica", where $\NP$ problems are hard in the worst case but easy on average, then \iO is impossible. Our result makes it redundant to explicitly assume the existence of one-way functions in most ``cryptographically interesting" applications of \iO.

In this work, we show how to use indistinguishability obfuscation (iO) to build multiparty key exchange, efficient broadcast encryption, and efficient traitor tracing. Our schemes enjoy several interesting properties that have not been achievable before: - Our multiparty non-interactive key exchange protocol does not require a trusted setup. Moreover, the size of the published value from each user is independent of the total number of users. - Our broadcast encryption schemes support distributed setup, where users choose their own secret keys rather than be given secret keys by a trusted entity. The broadcast ciphertext size is independent of the number of users. - Our traitor tracing system is fully collusion resistant with short ciphertexts, secret keys, and public key. Ciphertext size is logarithmic in the number of users and secret key size is independent of the number of users. Our public key size is polylogarithmic in the number of users. The recent functional encryption system of Garg, Gentry, Halevi, Raykova, Sahai, and Waters also leads to a traitor tracing scheme with similar ciphertext and secret key size, but the construction in this paper is simpler and more direct. These constructions resolve an open problem relating to differential privacy. - Generalizing our traitor tracing system gives a private broadcast encryption scheme (where broadcast ciphertexts reveal minimal information about the recipient set) with optimal size ciphertext. Several of our proofs of security introduce new tools for proving security using indistinguishability obfuscation.

We show that if there exist indistinguishability obfuscators for all circuits then there do not exist auxiliary-input extractable one-way functions. In particular, the knowledge of exponent assumption with respect to adversaries with auxiliary input is false in any group where computing discrete logarithms is intractable. The proof uses the “punctured programs” technique of [Sahai-Waters 2013].

A multiparty computation (MPC) protocol allows a set of players to compute a function of their inputs while keeping the inputs private and at the same time securing the correctness of the output. Most MPC protocols assume that the adversary can corrupt up to a fixed fraction of the number of players. Hirt and Maurer initiated the study of MPC under more general corruption patterns, in which the adversary is allowed to corrupt any set of players in some pre-defined collection of sets [6]. In this paper we consider this important direction of research and present significantly improved communication complexity of MPC protocols for general adversary structures. More specifically, ours is the first unconditionally secure protocol that achieves linear communication in the size of Monotone Span Program representing the adversary structure in the malicious setting against any Q2 adversary structure, whereas all previous protocols were at least cubic.

Block ciphers use Substitution boxes (S-boxes) to create confusion into the cryptosystems. Functions used as S-boxes should have low differential uniformity, high nonlinearity and algebraic degree larger than 3 (preferably strictly larger). They should be fastly computable; from this viewpoint, it is better when they are in even number of variables. In addition, the functions should be bijections in a Substitution-Permutation Network. Almost perfect nonlinear (APN) functions have the lowest differential uniformity 2 and the existence of APN bijections over $\F_{2^n}$ for even $n\ge 8$ is a big open problem. In the present paper, we focus on constructing differentially 4-uniform bijections suitable for designing S-boxes for block ciphers. Based on the idea of permuting the inverse function, we design a construction providing a large number of differentially 4-uniform bijections with maximum algebraic degree and high nonlinearity. For every even $n\ge 12$, we mathematically prove that the functions in a subclass of the constructed class are CCZ-inequivalent to known differentially 4-uniform power functions and to quadratic functions. This is the first mathematical proof that an infinite class of differentially 4-uniform bijections is CCZ-inequivalent to known differentially 4-uniform power functions and to quadratic functions. We also get a general lower bound on the nonlinearity of our functions, which can be very high in some cases, and obtain three improved lower bounds on the nonlinearity for three special subcases of functions which are extremely large.

We present an adaptively secure functional encryption (FE) scheme based on deterministic finite automata (DFA). The construction uses composite-order bilinear pairings and is built upon the selectively secure DFA-based FE scheme of Waters (Crypto 2012). The scheme is proven secure using the dual system methodology under static subgroup decision assumptions. A dual system proof requires generating of semi-functional components from the instance. In addition, these components must be shown to be properly distributed in an attacker's view. This can be ensured by imposing a restriction on the automata and strings over which the scheme is built i.e., every symbol can appear at most once in a string and in the set of transition tuples of an automata. First a basic construction with the restrictions is obtained and proved to be adaptively secure. We then show how to extend this basic scheme to a full scheme where the restrictions can be relaxed by placing a bound on the number of occurrences of any symbol in a string and in the set of transitions. With the relaxed restrictions, our system supports functionality defined by a larger class of regular languages.

We investigate the problem of algebraic manipulation detection (AMD) over a communication channel that partially leaks information to an adversary. We assume the adversary is computationally unbounded and there is no shared key or correlated randomness between the sender and the receiver. We introduce leakage-resilient (LR)-AMD codes to detect algebraic manipulation in this model. We consider two leakage models. The first model, called \emph{linear leakage}, requires the adversary's uncertainty (entropy) about the message (or encoding randomness) to be a constant fraction of its length. This model can be seen as an extension of the original AMD study by Cramer et al. \cite{CDFPW08} to when some leakage to the adversary is allowed. We study \emph{randomized strong} and \emph{deterministic weak} constructions of linear (L)LR-AMD codes. We derive lower and upper bounds on the redundancy of these codes and show that known optimal (in rate) AMD code constructions can serve as optimal LLR-AMD codes. In the second model, called \emph{block leakage}, the message consists of a sequence of blocks and at least one block remains with uncertainty that is a constant fraction of the block length. We focus on deterministic block (B)LR-AMD codes. We observe that designing optimal such codes is more challenging: LLR-AMD constructions cannot function optimally under block leakage. We thus introduce a new optimal BLR-AMD code construction and prove its security in the model. We show an application of LR-AMD codes to tampering detection over wiretap channels. We next show how to compose our BLR-AMD construction, with a few other keyless primitives, to provide both integrity and confidentiality in transmission of messages/keys over such channels. This is the best known solution in terms of randomness and code redundancy. We discuss our results and suggest directions for future research.

Side-Channel Analysis (SCA) is commonly used to recover secret keys involved in the implementation of publicly known cryptographic algorithms. On the other hand, Side-Channel Analysis for Reverse Engineering (SCARE) considers an adversary who aims at recovering the secret design of some cryptographic algorithm from its implementation. Most of previously published SCARE attacks enable the recovery of some secret parts of a cipher design --{\it e.g.} the substitution box(es)-- assuming that the rest of the cipher is known. Moreover, these attacks are often based on idealized leakage assumption where the adversary recovers noise-free side-channel information. In this paper, we address these limitations and describe a generic SCARE attack that can recover the full secret design of any iterated block cipher with common structure. Specifically we consider the family of Substitution-Permutation Networks with either a classical structure (as the AES) or with a Feistel structure. Based on a simple and usual assumption on the side-channel leakage we show how to recover all parts of the design of such ciphers. We then relax our assumption and describe a practical SCARE attack that deals with noisy side-channel leakages.

The relation between cryptographic key lengths and security depends on the cryptosystem used. This leads to confusion and to insecure parameter choices. In this note a universal security measure is proposed that puts all cryptographic primitives on the same footing, thereby making it easier to get comparable security across the board.

In this paper, we describe new techniques in meet-in-the-middle attacks. Our basic technique is called a \emph{linear key sieve} since it exploits as filtering conditions linear dependencies between key bits that are guessed from both sides of the attack. This should be contrasted with related previous attacks, which only exploited a \emph{linear state sieve} (i.e., linear dependencies between state bits that are computed from both sides of the attack). We apply these techniques to the lightweight block cipher LED-64, and improve some of the best known attacks on step-reduced variants of this cipher in all attack models. As a first application of the linear key sieve, we describe a chosen plaintext attack on 2-step LED-64, which reduces the time complexity of the best previously published attack on this variant from $2^{56}$ to $2^{48}$. Then, we present the first attack on 2-step LED-64 in the \emph{known plaintext model}. In this attack, we show for the first time that the splice-and-cut technique (which inherently requires chosen messages) can also be applied in the known plaintext model, and we use the linear key sieve in order to obtain an attack with the same time complexity as our chosen plaintext attack. Finally, we describe a related-key attack on 3-step LED-64 which improves the best previously published attack (presented at Asiacrypt 2012) in all the complexity parameters of time/data/memory from $2^{60}$ to $2^{49}$. As our first two single-key attacks, the related-key attack is also based on the linear key sieve, but it uses additional techniques in differential meet-in-the-middle which are interesting in their own right.

Cryptographic applications, such as hashing, block ciphers and stream ciphers, make use of functions which are simple by some criteria (such as circuit implementations), yet hard to invert almost everywhere. A necessary condition for the latter property is to be ``sufficiently distant'' from linear, and cryptographers have proposed several measures for this distance. In this paper, we show that four common measures, {\em nonlinearity, algebraic degree, annihilator immunity}, and {\em multiplicative complexity}, are incomparable in the sense that for each pair of measures, $\mu_1,\mu_2$, there exist functions $f_1,f_2$ with $\mu_1(f_1)> \mu_1(f_2)$ but $\mu_2(f_1)< \mu_2(f_2)$. We also present new connections between two of these measures. Additionally, we give a lower bound on the multiplicative complexity of collision-free functions.

Physical Unclonable Functions (PUFs) have established themselves in the scientific literature, and are also gaining ground in commercial applications. Recently, however, several attacks on PUF core properties have been reported. They concern their physical and digital unclonability, as well as their assumed resilience against invasive or side channel attacks. In this paper, we join some of these techniques in order to further improve their effectiveness. The combination of machine-learning based modeling techniques with side channel information allows us to attack so-called XOR Arbiter PUFs and Lightweight PUFs up to a size and complexity that was previously out of reach. For Lightweight PUFs, for example, we report successful attacks for bitlengths of 64, 128 and 256, and for up to nine single Arbiter PUFs whose output is XORed. Previous work at CCS 2010 and IEEE TIFS 2013, which provides the currently most efficient modeling results, had only been able to attack this structure for up to five XORs and bitlength 64. Our attack employs the first power side channel (PSC) for Strong PUFs in the literature. This PSC tells the attacker the number of single Arbiter PUF within an XOR Arbiter PUF or Lightweight PUF architecture that are zero or one. This PSC is of little value if taken by itself, but strongly improves an attacker’s capacity if suitably combined with modeling techniques. At the end of the paper, we discuss efficient and simple countermeasures against this PSC, which could be used to secure future PUF generations.

Recently, Garg, Gentry, Halevi, Raykova, Sahai, and Waters (FOCS 2013) constructed a general-purpose obfuscating compiler for NC1 circuits. We describe a simplified variant of this compiler, and prove that it is a virtual black box obfuscator in a generic multilinear map model. This improves on Brakerski and Rothblum (eprint 2013) who gave such a result under a strengthening of the Exponential Time Hypothesis. We remove this assumption, and thus resolve an open question of Garg et al. As shown by Garg et al., a compiler for NC1 circuits can be bootstrapped to a compiler for all polynomial-sized circuits under the learning with errors (LWE) hardness assumption. Our result shows that there is a candidate obfuscator that cannot be broken by algebraic attacks, hence reducing the task of creating secure obfuscators in the plain model to obtaining sufficiently strong security guarantees on candidate instantiations of multilinear maps.

We revisit the estimation of parameters for use in applications of the BGV homomorphic encryption system, which generally require high dimensional lattices. In particular, we utilize the BKZ-2.0 simulator of Chen and Nguyen to identify the best lattice attack that can be mounted using BKZ in a given dimension at a given security level. Using this technique, we show that it should be possible to work with lattices of smaller dimensions than previous methods have recommended, while still maintaining reasonable levels of security. As example applications we look at the evaluation of AES via FHE operations presented at Crypto 2012, and the parameters for the SHE variant of BGV used in the SPDZ protocol from Crypto 2012.

We consider applications involving a number of servers in the cloud that go through a sequence of online periods where the servers communicate, separated by offline periods where the servers are idle. During the offline periods, we assume that the servers need to securely store sensitive information such as cryptographic keys. Applications like this include many cases where secure multiparty computation is outsourced to the cloud, and in particular a number of online auctions and benchmark computations with confidential inputs. We consider fully autonomous servers that switch between online and offline periods without communicating with anyone from outside the cloud, and semi-autonomous servers that need a limited kind of assistance from outside the cloud when doing the transition. We study the levels of security one can - and cannot - obtain in this model, propose light-weight protocols achieving maximal security, and report on their practical performance.

This paper proposes a new scheme for authenticated encryption (AE) which is typically realized as a blockcipher mode of operation. The proposed scheme has attractive features for fast and compact operation. When it is realized with a blockcipher, it requires one blockcipher call to process one input block (i.e. rate-1), and uses the encryption function of the blockcipher for both encryption and decryption. Moreover, the scheme enables one-pass, parallel operation under two-block partition. The proposed scheme thus attains similar characteristics as the seminal OCB mode, without using the inverse blockcipher. The key idea of our proposal is a novel usage of two-round Feistel permutation, where the round functions are derived from the theory of tweakable blockcipher. We also provide basic software results, and describe some ideas on using a non-invertible primitive, such as a keyed hash function.

For securing databases outsourced to the cloud, it is important to allow cloud users to verify that their queries to the cloud-hosted databases are correctly executed by the cloud. Existing solutions on this issue suffer from a high communication cost, a heavy storage overhead or an overwhelming computational cost on clients. Besides, only simple SQL queries (e.g., selection query, projection query, weighted sum query, etc) are supported in existing solutions. For practical considerations, it is desirable to design a client-verifiable (or publicly verifiable) aggregation query scheme that supports more flexible queries with affordable storage overhead, communication and computational cost for users. This paper investigates this challenging problem and proposes an efficient publicly verifiable aggregation query scheme for databases outsourced to the cloud. By designing a renewable polynomial-based authentication tag, our scheme supports a wide range of practical SQL queries including polynomial queries of any degrees, variance query and many other linear queries. Remarkably, our proposed scheme only introduces constant communication and computational cost to cloud users. Our scheme is provably secure under the Static Diffie-Hellman problem, the t-Strong Diffie-Hellman problem and the Computational Diffie-Hellman problem. We show the efficiency and scalability of our scheme through extensive numerical analysis.

The block cipher used in the Chinese Wireless LAN Standard (WAPI), SMS4, was recently renamed as SM4, and became the block cipher standard issued by the Chinese government. This paper improves the previous linear cryptanalysis of SMS4 by giving the first 19-round one-dimensional approximations. The 19-round approximations hold with bias 2^{&#8722;62.27}; we use one of them to leverage a linear attack on 23-round SMS4. Our attack improves the previous 23-round attacks by reducing the time complexity. Furthermore, the data complexity of our attack is further improved by the multidimensional linear approach.

Security analytics is a catchall term for vulnerability assessment in large organizations capturing a new emerging approach to intrusion detection. It leverages a combination of automated and manual analysis of security logs and alerts which originate from a wide and varying array of sources and are often aggregated into a massive data repository. Such log and alert sources include firewalls, VPNs, and endpoint instrumentation, such as intrusion-detection systems, syslog or other alerting host facilities, that we generically call Security Analytics Sources (SASs). Security analytics are only as good as the data being analyzed. Yet nearly all security analytics systems today suffer from a lack of even basic protections on data collection. By merely monitoring network traffic, an adversary can eavesdrop on SAS outputs to discover sensitive SAS instrumentation and security-alerting behaviors. Moreover, by using advance malware, an adversary can undetectably suppress or tamper with SAS messages to conceal attack evidence and disrupt intrusion detection. We introduce PillarBox, a tool for securely relaying SAS data in a security analytics system. PillarBox enforces integrity: It secures SAS data against tampering, even when such data is buffered on a compromised host within an adversarially controlled network. Additionally, PillarBox (optionally) offers stealth: It can conceal SAS data, alert-generation activity, and potentially even alerting rules on a compromised host, thus hiding select SAS alerting actions from an adversary. We present an implementation of PillarBox and show experimentally that it can secure messages against attacker suppression, tampering or discovery even in the most challenging environments where SASs generate real-time security alerts related to a host compromise directly targeting to diminish their alerting power. We also show, based on data from a large enterprise and on-host performance measurements, that PillarBox has minimal overhead and is practical for real-world security analytics systems.

This paper proposes a new hardware architecture of Integer-FFT multiplier for super-size integer multiplications. Firstly, a basic hardware archi-tecture, with the feature of low hardware cost, of the Integer-FFT multiplication algorithm using the serial FFT architecture, is proposed. Next, a modified hardware architecture with a shorter multiplication latency than the basic archi-tecture is presented. Thirdly, both architectures are implemented, verified and compared on the Xilinx Virtex-7 FPGA platform using 256, 512, 1024, 2048 and 8192 point Integer-FFT algorithm respectively with multiplication operands ranging from bits to bits in size. Experimental results show that the hardware cost of the proposed architecture is no more than 1/10 of the prior FPGA solution, and is perfectly within the implementable range of the Xilinx Virtex-7 FPGA platform, and outperforms the software implementations of the same bit-length operand multiplication on the Core-2 Q6600 and Core-i7 870 platforms. Finally, the proposed implementations are employed to evaluate the super-size multiplication in an encryption primitive of fully homomorphic en-cryption (FHE) over the integers. The analysis shows that the speed improve-ment factor is up to 26.2 compared to the corresponding integer-based FHE software implementation on the Core-2 Duo E8400 platform.

Everyone is concerned about Internet security, yet most traffic is not cryptographically protected. Typical justification is that most attackers are off-path and cannot intercept traffic; hence, intuitively, challenge-response defenses should suffice to ensure authenticity. Often, the challenges re-use existing header fields to protect widelydeployed protocols such as TCP and DNS. We argue that this practice may often give an illusion of security. We review recent off-path TCP injection and DNS poisoning attacks, enabling attackers to circumvent existing challenge-response defenses. Both TCP and DNS attacks are non-trivial, yet practical. The attacks foil widely deployed security mechanisms, and allow a wide range of exploits, such as long-term caching of malicious objects and scripts. We hope that this review article will help improve defenses against off-path attackers. In particular, we hope to motivate, when feasible, adoption of cryptographic mechanisms such as SSL/TLS, IPsec and DNSSEC, providing security even against stronger Man-in-the-Middle attackers.

Anonymous credentials provide a powerful tool for making assertions about identity while maintaining privacy. However, a limitation of today's anonymous credential systems is the need for a trusted credential issuer --- which is both a single point of failure and a target for compromise. Furthermore, the need for such a trusted issuer can make it challenging to deploy credential systems in practice, particularly in the ad hoc network setting (e.g., anonymous peer-to-peer networks) where no single party can be trusted with this responsibility. In this work we propose a novel anonymous credential scheme that eliminates the need for a trusted credential issuer. Our approach builds on recent results in the area of electronic cash and uses techniques --- such as the calculation of a distributed transaction ledger --- that are currently in widespread deployment in the Bitcoin payment system. Using this decentralized ledger and standard cryptographic primitives, we propose and provide a proof of security for a basic anonymous credential system that allows users to make flexible identity assertions with strong privacy guarantees. Finally, we discuss a number of practical applications for our techniques, including resource management in ad hoc networks and prevention of Sybil attacks. We implement our scheme and measure its efficiency.

We present a password-authenticated group key exchange protocol where each user has his/her own password. Advantage of such protocol is in short passwords, which can be easily memorized. On the other hand these protocols face the low password entropy. In the first part we define security model based on models of Abdalla, Fouque and Pointcheval and Bellare, Pointcheval, Rogaway. We construct MLHL (Multi-LHL) protocol, which is based on LHL protocol proposed by Lee, Hwang and Lee. However, LHL protocol is flawed as pointed by Abdalla, Bresson, Chevassut and Choo, Raymond. We prove that our protocol is secure authenticated key exchange protocol with forward secrecy property and that the protocol is resistant against attacks on LHL protocol.

The increasing penetration of Online Social Networks (OSNs) prompts the need for effectively accessing and utilizing social networking information. In numerous applications, users need to make trust and/or access control decisions involving other (possibly stranger) users, and one important factor is often the existence of common social relationships. This motivates the need for secure and privacy-preserving techniques allowing users to assess whether or not they have mutual friends. This paper introduces the Common Friends service, a framework for finding common friends which protects privacy of non-mutual friends and guarantees authenticity of friendships. First, we present a generic construction that reduces to secure computation of set intersection, while ensuring authenticity of announced friends via bearer capabilities. Then, we propose an efficient instantiation, based on Bloom filters, that only incurs a constant number of public-key operations and appreciably low communication overhead. Our software is designed so that developers can easily integrate Common Friends into their applications, e.g., to enforce access control based on users' social proximity in a privacy-preserving manner. Finally, we showcase our techniques in the context of an existing application for sharing (tethered) Internet access, whereby users decide to share access depending on the existence of common friends. A comprehensive experimental evaluation attests to the practicality of proposed techniques.

Physically Unclonable Functions (PUFs) are emerging as hardware security primitives. So-called strong PUFs provide a mechanism to authenticate chips which is inherently unique for every manufactured sample. To prevent cloning, modeling of the challenge-response pair (CRP) behavior should be infeasible. Machine learning (ML) algorithms are a well-known threat. Recently, repeatability imperfections of PUF responses have been identied as another threat. CMOS device noise renders a signicant fraction of the CRPs unstable, hereby providing a side channel for modeling attacks. In previous work, 65nm arbiter PUFs have been modeled as such with accuracies exceeding 97%. However, more PUF evaluations were required than for state-of-the-art ML approaches. In this work, we accelerate repeatability attacks by increasing the fraction of unstable CRPs. Response evaluation faults are triggered via environmental changes hereby. The attack speed, which is proportional to the fraction of unstable CRPs, increases with a factor 2.4 for both arbiter and ring oscillator (RO) sum PUFs. Data originates from a 65nm silicon chip and hence not from simulations.

In this paper we introduce a model for studying meet-in-the-middle attacks on block ciphers, and a simple block cipher construction provably resistant to such attacks in this model. A side-result of this is a proper formalization for an unproven alternative to DESX proposed by Kilian and Rogaway; this construction can now be shown to be sound in our model. Meet-in-the-middle attacks exploit weaknesses in key schedule algorithms, and building constructions resistant to such attacks is an important issue for improving the security of block ciphers. Our construction is generic so that it can be used on top of any block cipher, and it does not require to increase the key-length. We use an exposure resilient function (or ERF) as a building block and we propose a concrete and efficient instantiation strategy based on compression functions.

The global avalanche characteristics criteria was first introduced by Zhou et al. (Inform. Sci. 180(2) (2010) 256-265). This article is concerned with some new bounds on global avalanche characteristics of two $q$-ary functions. Based on the above result we obtain a bound on $\sigma_{f}$ of $f \in \cB_{n, q}$ in terms of $\sigma_{f_{\ell}}'$s of the restricted functions on $\BBZ_{n-1}^q$, and construct a class of $q$-ary bent functions from $1$-plateaued functions having dijoint Walsh spectra.

A fully homomorphic encryption (FHE) scheme is envisioned as being a key cryptographic tool in building a secure and reliable cloud computing environment, as it allows arbitrarily evaluation of a ciphertext without revealing the plaintext. However, existing FHE implementations remain impractical due to their very high time and resource costs. Of the proposed schemes that can perform FHE to date, a scheme known as FHE over the integers has the ad-vantage of comparatively simpler theory, as well as the employment of a much shorter public key making its implementation somewhat more practical than other competing schemes. To the author’s knowledge, this paper presents the first hardware implemen-tations of encryption primitives for FHE over the integers using FPGA technol-ogy. First of all, a super-size hardware multiplier architecture utilising the Inte-ger-FFT multiplication algorithm is proposed, and a super-size hardware Barrett modular reduction module is designed incorporating the proposed multiplier. Next, two encryption primitives that are used in two schemes of FHE over the integers are designed employing the proposed super-size multiplier and modular reduction modules. Finally, the proposed designs are implemented and verified on the Xilinx Virtex-7 FPGA platform. Experimental results show that the speed improvement factors of up to 44.72 and 54.42 are available for the two FHE encryption schemes implemented in FPGA when compared to the corresponding software implementations. Meanwhile, the performance analysis shows that further improvement is speed of these FHE encryption primitives may still be possible.

One of the most challenging aspects in computer-supported voting is to combine the apparently conflicting requirements of privacy and verifiability. On the one hand, privacy requires that a vote cannot be traced back from the result to a voter, while on the other hand, verifiability states that a voter can trace the effect of her vote on the result. This can be addressed using various privacy-enabling cryptographic primitives which also offer verifiability. As more and more refined voting systems were proposed, understanding of first privacy and later verifiability in voting increased, and notions of privacy as well as notions of verifiability in voting became increasingly more refined. This has culminated in a variety of verifiable systems that use cryptographic primitives to ensure specific kinds of privacy. However, the corresponding privacy and verifiability claims are not often verified independently. When they are investigated, claims have been invalidated sufficiently often to warrant a cautious approach to them. The multitude of notions, primitives and proposed solutions that claim to achieve both privacy and verifiability form an interesting but complex landscape. The purpose of this paper is to survey this landscape by providing an overview of the methods, developments and current trends regarding privacy and verifiability in voting systems.

Proof-of-retrievability schemes have been a topic of considerable recent interest. In these schemes, a client gives a file M to a server with the understanding that the server will securely store M. A suitable challenge-response protocol is invoked by the client in order for the client to gain confidence that M is indeed being correctly stored by the server. The definition of proof-of-retrievability schemes is based on the notion of an extractor that can recover the file once the challenge-response protocol is executed a sufficient number of times. In this paper, we propose a new type of scheme that we term a proof-of-data-observability scheme. Our definition tries to capture the stronger requirement that the server must have an actual copy of M in its memory space while it executes the challenge-response protocol. We give some examples of schemes that satisfy this new security definition. As well, we analyze the efficiency and security of the protocols we present, and we prove some necessary conditions for the existence of these kinds of protocols.

Naturally occurring and maliciously injected faults reduce the reliability of cryptographic hardware and may leak confidential information. We develop a concurrent error detection (CED) technique called Recomputing with Permuted Operands (REPO). We show that it is cost effective in Advanced Encryption Standard (AES) and a secure hash function Grøstl. We provide experimental results and formal proofs to show that REPO detects all single-bit and single-byte faults. Experimental results show that REPO achieves close to 100% fault coverage for multiple byte faults. The hardware and throughput overheads are compared with those of previously reported CED techinques on two Xilinx Virtex FPGAs. The hardware overhead is 12.4-27.3%, and the throughput is 1.2-23Gbps, depending on the AES architecture, FPGA family, and detection latency. The performance overhead ranges from 10% to 100% depending on the security level. Moreover, the proposed technique can be integrated into various block cipher modes of operation. We also discuss the limitation of REPO and its potential vulnerabilities.

Ring signatures allow a signer to anonymously sign a message on behalf of a set of arbitrarily chosen signers called a ``ring''. Blind signatures, on the other hand, allow a user to obtain a signature on a message while maintaining the privacy of the message. Blind ring signatures combine properties of both primitives and hence provide a strong notion of anonymity where the privacy of both the identity of the signer and the message is preserved. Blind ring signatures find applications in various systems; including multi-authority e-voting and distributed e-cash systems. In this paper we provide the first provably secure blind ring signature construction that does not rely on random oracles, which solves an open problem raised by Herranz and Laguillaumie at ISC 2006. We present different instantiations all of which are round-optimal (i.e.\ have a two-move signing protocol), yield sub-linear size signatures, and meet strong security requirements. In order to realize our constructions efficiently, we construct a sub-linear size set membership proof which works in the different bilinear group settings, which may be of independent interest. As a secondary contribution, we show how to generically combine our set membership proof with any secure signature scheme meeting some conditions to obtain ring signatures whose security does not rely on random oracles. All our constructions work over the efficient prime-order bilinear group setting and yield signatures of sub-linear size. In addition, our constructions meet strong security requirements: namely, anonymity holds under full key exposure and unforgeability holds against insider-corruption. Finally, we provide some example instantiations of the generic construction.

In this article, we investigate the use of limited-birthday distinguishers to the context of hash functions. We first provide a proper understanding of the limited-birthday problem and demonstrate its soundness by using a new security notion Differential Target Collision Resistance (dTCR) that is related to the classical Target Collision Resistance (TCR) notion. We then solve an open problem and close the existing security gap by proving that the best known generic attack proposed at FSE 2010 for the limited-birthday problem is indeed the best possible method. Moreover, we show that almost all known collision attacks are in fact more than just a collision finding algorithm, since the difference mask for the message input is usually fixed. A direct and surprising corollary is that these collision attacks are interesting for cryptanalysis even when their complexity goes beyond the $2^{n/2}$ birthday bound and up to the $2^{n}$ preimage bound, and can be used to derive distinguishers using the limited-birthday problem. Interestingly, cryptanalysts can now search for collision attacks beyond the $2^{n/2}$ birthday bound. Finally, we describe a generic algorithm that turns a semi-free-start collision attack on a compression function (even if its complexity is beyond the birthday bound) into a distinguisher on the whole hash function when its internal state is not too wide. To the best of our knowledge, this is the first result that exploits classical semi-free-start collisions on the compression function to exhibit a weakness on the whole hash function. As an application of our findings, we provide distinguishers on reduced or full version of several hash functions, such as RIPEMD-128, SHA-256, Whirlpool, etc.

Physically Unclonable Functions (PUFs) are security primitives that exploit the unique manufacturing variations of an integrated circuit (IC). They are mainly used to generate secret keys. Ring oscillator (RO) PUFs are among the most widely researched PUFs. In this work, we claim various RO PUF constructions to be vulnerable against manipulation of their public helper data. Partial/full key-recovery is a threat for the following constructions, in chronological order. (1) Temperature-aware cooperative RO PUFs, proposed at HOST 2009. (2) The sequential pairing algorithm, proposed at HOST 2010. (3) Group-based RO PUFs, proposed at DATE 2013. (4) Or more general, all entropy distiller constructions proposed at DAC 2013.

In this work, elliptic curve cryptography (ECC) is used to make an efficient implementation of a public-key cryptography algorithm on the ARM Cortex-M0+. The goal of this implementation is to make not only a fast, but also a very low-power software implementation. To aid in the elliptic curve parameter selection, the energy consumption of different instructions on the ARM Cortex-M0+ was measured and it was found that there is a variation of up to 22.5% between different instructions. The instruction set architecture (ISA) and energy measurements were used to make a simulation of both a binary curve and a prime curve implementation, and the former was found to have a slightly faster execution time with a lower power consumption. Binary curve arithmetic use instructions which requires less energy than prime curve arithmetic on the target platform. A new field multiplication algorithm is proposed, called Lopez-Dahab with fixed registers, which is an optimization of the Lopez-Dahab (LD) algorithm. The proposed algorithm has a performance improvement of 15\% over the LD with rotating registers algorithm (which is the current fastest optimization of the LD algorithm). A software implementation that uses the proposed algorithm was made in C and assembly, and on average our implementation of a random point multiplication requires 34.16uJ, whereas our fixed point multiplication requires 20.63uJ. The energy consumption of our implementation beats all known software implementations on embedded platforms, of a point multiplication, on the same equivalent security level by a factor of 7.4.

Under the assumption that one has a reference device identical or similar to the target device, and thus be well capable of characterizing power leakages of the target device, Template Attacks are widely accepted to be the most powerful side-channel attacks. However, the question of whether Template Attacks are really optimal in terms of the leakage exploitation rate is still unclear. In this paper, we present a negative answer to this crucial question by introducing a normalization process into classical Template Attacks. Specifically, our contributions are two folds. On the theoretical side, we prove that Normalized Template Attacks are better in terms of the leakage exploitation rate than Template Attacks; on the practical side, we evaluate the key-recovery efficiency of Normalized Template Attacks and Template Attacks in the same attacking scenario. Evaluation results show that, compared with Template Attacks, Normalized Template Attacks are more effective. We note that, the computational price of the normalization process is of extremely low, and thus it is very easy-to-implement in practice. Therefore, the normalization process should be integrated into Template Attacks as a necessary step, so that one can better understand practical threats of Template Attacks.

In this article we propose a new cryptanalysis method for double-branch hash functions that we apply on the standard RIPEMD-128, greatly improving over know results. Namely, we were able to build a very good differential path by placing one non-linear differential part in each computation branch of the RIPEMD-128 compression function, but not necessarily in the early steps. In order to handle the low differential probability induced by the non-linear part located in later steps, we propose a new method for using the freedom degrees, by attacking each branch separately and then merging them with free message blocks. Overall, we present the first collision attack on the full RIPEMD-128 compression function as well as the first distinguisher on the full RIPEMD-128 hash function. Experiments on reduced number of rounds were conducted, confirming our reasoning and complexity analysis. Our results show that 16 years old RIPEMD-128, one of the last unbroken primitives belonging to the MD-SHA family, might not be as secure as originally thought.

Timed-release encryption is a kind of encryption scheme that a recipient can decrypt only after a specified amount of time T (assuming that we have a moderately precise estimate of his computing power). A revocable timed-release encryption is one where, before the time T is over, the sender can "give back" the timed-release encryption, provably loosing all access to the data. We show that revocable timed-release encryption without trusted parties is possible using quantum cryptography (while trivially impossible classically). Along the way, we develop two proof techniques in the quantum random oracle model that we believe may have applications also for other protocols. Finally, we also develop another new primitive, unknown recipient encryption, which allows us to send a message to an unknown/unspecified recipient over an insecure network in such a way that at most one recipient will get the message.

In this paper, we present a new class of public key cryptosystems by modifying K(XII)SE(1)PKC[1], referred to as K(XIII)SE(1)PKC, and a particular class of K(XIII)SE(1)PKC, Kp(XIII)SE(1)PKC. We show that K(XIII)SE(1)PKC would improve both the coding rate and the security, compared with K(XII)SE(1)PKC. We also show that Kp(XIII)SE(1)PKC realizes the coding rate of exactly 1.0. In a sharp contrast with the conventional code based PKC (CB&#65381;PKC) that uses Goppa code, in K(XII)SE(1)PKC, K(XIII)SE(1)PKC and Kp(XIII)SE(1)PKC, we do not care for the security of the primitive polynominal that generates the Reed-Solomon code.

The notion of time plays an important role in many practically deployed cryptographic protocols, ranging from One-Time-Password (OTP) tokens to the Kerberos protocol. However, time is difficult to model in a Turing machine environment. We propose the first such model, where time is modelled as a global counter T . We argue that this model closely matches several implementations of time in computer environments. The usefulness of the model is shown by giving complexity-theoretic security proofs for OTP protocols, HMQV-like one-round AKE protocols, and a variant of the basic Kerberos building block.

Naturally occurring and maliciously injected faults reduce the reliability of Advanced Encryption Standard (AES) and may leak confidential information. We developed an invariance-based concurrent error detection (CED) scheme which is independent of the implementation of AES encryption/decryption. Additionally, we improve the security of our scheme with Randomized CED Round Insertion and adaptive checking. Experimental results show that the invariance-based CED scheme detects all single-bit, all single-byte fault, and 99.99999997% of burst faults. The area and delay overheads of this scheme are compared with those of previously reported CED schemes on two Xilinx Virtex FPGAs. The hardware overhead is in the 13.2-27.3% range and the throughput is between 1.8-42.2Gbps depending on the AES architecture, FPGA family, and the detection latency. One can im- plement our scheme in many ways; designers can trade off performance, reliability, and security according to the available resources.

We present a study of the concrete complexity of solving instances of the unique shortest vector problem (uSVP). In particular, we study the complexity of solving the Learning with Errors (LWE) problem by reducing the Bounded-Distance Decoding (BDD) problem to uSVP and attempting to solve such instances using the ‘embedding’ approach. We experimentally derive a model for the success of the approach, compare to alternative methods and demonstrate that for the LWE instances considered in this work, reducing to uSVP and solving via embedding compares favorably to other approaches.

One fundamental complexity measure of an MPC protocol is its {\em round complexity}. Asharov et al. recently constructed the first three-round protocol for general MPC in the CRS model. Here, we show how to achieve this result with only two rounds. We obtain UC security with abort against static malicious adversaries, and fairness if there is an honest majority. Additionally the communication in our protocol is only proportional to the input and output size of the function being evaluated and independent of its circuit size. Our main tool is indistinguishability obfuscation, for which a candidate construction was recently proposed by Garg et al. The technical tools that we develop in this work also imply virtual black box obfuscation of a new primitive that we call a \emph{dynamic point function}. This primitive may be of independent interest.

In this article, we propose an improved cryptanalysis of the double-branch hash function standard RIPEMD-160. Using a carefully designed non-linear path search tool, we study the potential differential paths that can be constructed from a difference in a single message word and show that some of these message words can lead to very good differential path candidates. Leveraging the recent freedom degree utilization technique from Landelle and Peyrin to merge two branch instances, we eventually manage to obtain a semi-free-start collision attack for 42 steps of the RIPEMD-160 compression function, while the previously best know result reached 36 steps. In addition, we also describe a 36-step semi-free-start collision attack which starts from the first step.

An attacker can efficiently factor at least 184 distinct 1024-bit RSA keys from Taiwan's national "Citizen Digital Certificate" database. The big story here is that these keys were generated by government-issued smart cards that were certified secure. The certificates had all the usual buzzwords: FIPS certification from NIST (U.S. government) and CSE (Canadian government), and Common Criteria certification from BSI (German government). These 184 keys include 103 keys that share primes and that are efficiently factored by a batch-GCD computation. This is the same type of computation that was used last year by two independent teams (USENIX Security 2012: Heninger, Durumeric, Wustrow, Halderman; Crypto 2012: Lenstra, Hughes, Augier, Bos, Kleinjung, Wachter) to factor tens of thousands of cryptographic keys on the Internet. The remaining 81 keys do not share primes. Factoring these 81 keys requires taking deeper advantage of randomness-generation failures: first using the shared primes as a springboard to characterize the failures, and then using Coppersmith-type partial-key-recovery attacks. This is the first successful public application of Coppersmith-type attacks to keys found in the wild.

We examine the widespread SimonsVoss digital locking system 3060 G2 that relies on an undisclosed, proprietary protocol to mutually authenticate transponders and locks. For assessing the security of the system, several tasks have to be performed: By decapsulating the used microcontrollers with acid and circumventing their read-out protection with UV-C light, the complete program code and data contained in door lock and transponder are extracted. As a second major step, the multi-pass challenge-response protocol and corresponding cryptographic primitives are recovered via low-level reverse-engineering. The primitives turn out to be based on DES in combination with a proprietary construction. Our analysis pinpoints various security vulnerabilities that enable practical key-recovery attacks. We present two different approaches for unauthorizedly gaining access to installations. Firstly, an attacker having physical access to a door lock can extract a master key, allowing to mimic transponders, in altogether 30 minutes. A second, purely logical attack exploits an implementation flaw in the protocol and works solely via the wireless interface. As the only prerequisite, a valid ID of a transponder needs to be known (or guessed). After executing a few (partial) protocol runs in the vicinity of a door lock, and some seconds of computation, an adversary obtains all of the transponder’s access rights.

This paper proposes the computation of the Tate pairing, Ate pairing and its variations on the special Jacobi quartic elliptic curve Y^2 = dX^4 +Z^4. We improve the doubling and addition steps in Miller's algorithm to compute the Tate pairing. We use the birational equivalence between Jacobi quartic curves and Weierstrass curves, together with a specific point representation to obtain the best result to date among curves with quartic twists. For the doubling and addition steps in Miller's algorithm for the computation of the Tate pairing, we obtain a theoretical gain up to 27% and 39%, depending on the embedding degree and the extension field arithmetic, with respect to Weierstrass curves [2] and previous results on Jacobi quartic curves [3]. Furthermore and for the first time, we compute and implement Ate, twisted Ate and optimal pairings on the Jacobi quartic curves. Our results are up to 27% more efficient, comparatively to the case of Weierstrass curves with quartic twists [2].

At ASIACRYPT 2012, Petit and Quisquater suggested that there may be a subexponential-time index-calculus type algorithm for the Elliptic Curve Discrete Logarithm Problem (ECDLP) in characteristic two fields. This algorithm uses Semaev polynomials and Weil Descent to create a system of polynomial equations that subsequently is to be solved with Gröbner basis methods. Its analysis is based on heuristic assumptions on the performance of Gröbner basis methods in this particular setting. While the subexponential behaviour would manifest itself only far beyond the cryptographically interesting range, this result, if correct, would still be extremely remarkable. We examined some aspects of the work by Petit and Quisquater experimentally.

The certificate authority model for authenticating public keys of websites has been attacked in recent years, and several proposals have been made to reinforce it. We develop and extend "certificate transparency}", a proposal in this direction, so that it efficiently handles certificate revocation. We show how this extension can be used to build a secure end-to-end email or messaging system using PKI with no requirement to trust certificate authorities, or to rely on complex peer-to-peer key-signing arrangements such as PGP. This makes end-to-end encrypted mail possible, with apparently few additional usability issues compared to unencrypted mail (specifically, users do not need to understand or concern themselves with keys or certificates). Underlying these ideas is a new attacker model appropriate for cloud computing, which we call "malicious-but-cautious".

We construct an innovative SVP(CVP) solver for ideal lattices in case of any relative extension of number fields L/K of degree n where L is real(contained in R). The solver, by exploiting the relationships between the so-called local and global number fields, reduces solving SVP(CVP) of the input ideal A in field L to solving a set of (at most n) SVP(CVP) of the ideals Ai in field Li with relative degree 1&#8804;ni<n and &#8721;ini=n, and the solution to the original problem can be efficiently reconstructed from the solutions to the sub-problems. The solver’s space-complexity is polynomial and its time-complexity’s explicit dependence on the dimension (relative extension degree n) is also polynomial. More precisely, our solver’s time-complexity is poly(n,|S|, NPG, NPT, Nd, Nl) where |S| is bit-size of the input data and NPG, NPT, Nd, Nl are the number of calls to some oracles for some relatively simpler problems (some of which are decisional). This feature implies that if such oracles can be implemented by efficient algorithms (with time-complexity polynomial in n), which is really possible in some situations, our solver will perform in this case with time-complexity polynomial in n. Even there is no efficient implementations for these oracles, this solver’s time-complexity may still be significantly lower than those for general lattices.

Adaptive security is a strong security notion that captures additional security threats that are not addressed by static corruptions. For instance, it captures real-world scenarios where ``hackers'' actively break into computers, possibly while they are executing secure protocols. Studying this setting is interesting from both theoretical and practical points of view. A primary building block in designing adaptively secure protocols is a non-committing encryption (NCE) that implements secure communication channels in the presence of adaptive corruptions. Current constructions require a number of public key operations that grows linearly with the length of the message. Furthermore, general two-party protocols require a number of NCE calls that dependents both on the circuit size and the security parameter. In this paper we study the two-party setting in which at most one of the parties is adaptively corrupted, and demonstrate the feasibility of ({\bf 1}) NCE with constant number of public key operations for large message spaces. ({\bf 2}) Oblivious transfer with constant number of public key operations for large sender's input spaces, and ({\bf 3}) constant round secure computation protocols with an overall number of public key operations that is linear in the circuit size. Our study demonstrates that such primitives indeed exist in the presence of single corruptions without erasures, while this is not known for fully adaptive security under standard assumptions (where both parties may get corrupted). Our results are shown in the UC setting with a CRS setup.

In 2009 and 2011, Toorani and Falahati introduced two variants of the classical Hill Cipher, together with protocols for the exchange of encrypted messages. The designers claim that the new systems overcome the weaknesses of the original Hill Cipher, and are resistant to any ciphertext-only, known-plaintext, chosen-plaintext, or chosen-ciphertext attack. However, we describe a chosen-plaintext attack that easily breaks both Toorani-Falahati Hill Ciphers, and we present computational results that confirm the effectiveness of our attack.

Cryptanalytic time memory tradeoff is a tool for inverting one-way functions, and the rainbow table method, the best-known tradeoff algorithm, is widely used to recover passwords. Even though extensive research has been performed on the rainbow tradeoff, the algorithm actually used in practice differs from the well-studied original algorithm. This work provides a full analysis of the rainbow tradeoff algorithm that is used in practice. Unlike existing works on the rainbow tradeoff, the analysis is done in the external memory model, so that the practically important issue of table loading time is taken into account. As a result, we are able to provide tradeoff parameters that optimize the wall-clock time.

We introduce EyeDecrypt, a novel technology for privacy-preserving human-computer interaction. EyeDecrypt allows only authorized users to decipher data shown on a display, such as an electronic screen or plain printed material; in the former case, the authorized user can then interact with the system (e.g., by pressing buttons on the screen), without revealing the details of the interaction to others who may be watching or to the system itself. The user views the decrypted data on a closely-held personal device, such as a pair of smart glasses with a camera and heads-up display, or a smartphone. The data is displayed as an image overlay on the personal device, which we assume cannot be viewed by the adversary. The overlay is a form of augmented reality that not only allows the user to view the protected data, but also to securely enter input into the system by randomizing the input interface. EyeDecrypt consists of three main components: a visualizable encryption scheme; a dataglyph-based visual encoding scheme for the ciphertexts generated by the encryption scheme; and a randomized input and augmented reality scheme that protects user inputs without harming usability. We describe all aspects of EyeDecrypt, from security definitions, constructions and analysis, to implementation details of a prototype developed on a smartphone.

MASH-1 is modular arithmetic based hash function. It is presented in Part 4 of ISO/IEC 10118 standard for one and a half decade. Cryptographic strength of MASH-1 hash function is based on factorization problem of an RSA modulus along with redundancy in the input blocks of compression functions. Despite of this, we are able to introduce two large classes of moduli which allow practical time collision finding algorithm for MASH-1. In one case even multicollisions of arbitrary length can be constructed.

In 2009, Abdalla et al. proposed a reasonably practical password-authenticated key exchange (PAKE) secure against adaptive adversaries in the universal composability (UC) framework. It exploited the Canetti-Fischlin methodology for commitments and the Cramer-Shoup smooth projective hash functions (SPHFs), following the Gennaro-Lindell approach for PAKE. In this paper, we revisit the notion of non-interactive commitments, with a new formalism that implies UC security. In addition, we provide a quite efficient instantiation. We then extend our formalism to SPHF-friendly commitments. We thereafter show that it allows a blackbox application to one-round PAKE and oblivious transfer (OT), still secure in the UC framework against adaptive adversaries, assuming reliable erasures and a single global common reference string, even for multiple sessions. Our instantiations are more efficient than the Abdalla et al. PAKE in Crypto 2009 and the recent OT protocol proposed by Choi~et al. in PKC 2013. Furthermore, the new PAKE instantiation is the first one-round scheme achieving UC security against adaptive adversaries.

Data outsourcing is a growing business model offering services to individuals and enterprises for processing and storing a huge amount of data. It is not only economical but also promises higher availability, scalability, and more effective quality of service than in-house solutions. Despite all its benefits, data outsourcing raises serious security concerns for preserving data confidentiality. There are solutions for preserving confidentiality of data while supporting search on the data stored in outsourced environments. However, such solutions do not support access policies to regulate access to a particular subset of the stored data. For complex user management, large enterprises employ Role-Based Access Controls (RBAC) models for making access decisions based on the role in which a user is active in. However, RBAC models cannot be deployed in outsourced environments as they rely on trusted infrastructure in order to regulate access to the data. The deployment of RBAC models may reveal private information about sensitive data they aim to protect. In this paper, we aim at filling this gap by proposing ESPOON ERBAC for enforcing RBAC policies in outsourced environments. ESPOON ERBAC enforces RBAC policies in an encrypted manner where a curious service provider may learn a very limited information about RBAC policies. We have implemented ESPOON ERBAC and provided its performance evaluation showing a limited overhead, thus confirming viability of our approach.

Related-key and chosen IV attacks are well known cryptanalytic tools in cryptanalysis of stream ciphers. Though the related-key model is considered to be much more unrealistic scenario than the chosen IV model we show that under certain circumstances the attack assumptions may become equivalent. We show that the key differentiation method induces a generic attack in a related-key model whose time complexity in the on-line phase is less than the exhaustive key search. The case of formal equivalency between the two scenarios arises when so-called {\em differentiable polynomials} with respect to some subset of key variables are a part of the state bit expressions (from which the output keystream bits are built). Then the differentiation over a key cube has the same effect as the differentiation over the corresponding IV cube, so that a generic nature of a related-key model is transferred into a more practical chosen IV model. The existence of such polynomials is confirmed for the reduced round stream cipher TRIVIUM up to some 710 rounds and an algorithm for their detection is proposed. The key differentiation method induces a time/related-key trade-off (TRKTO) attack which (assuming the existence of differentiable polynomials) can be run in a chosen IV model. The resulting trade-off curve of our TMDTO attack is given by $T^2M^2D^2=(KV)^2$ ($V$ denoting the IV space), which is a significant improvement over the currently best known trade-off $TM^2D^2=(KV)^2$ \cite{IVDunkel08}.

The trace inverse function $\Tr(\lambda x^{-1})$ over the finite field $\mathbb{F}_{2^n}$ is a class of very important Boolean functions and has be used in many stream ciphers, for example, SFINKS, RAKAPOSHI, the simple counter stream cipher presented by W. Si and C.S. Ding, etc. In order to evaluate the security of those algorithms in assistance to (fast) algebraic attacks, it is essential to algebraic properties of $\Tr(\lambda x^{-1})$. However, currently only some bounds on algebraic immunity of $\Tr(\lambda x^{-1})$ are given in public literature. In this work we give the exact value of $\Tr(\lambda x^{-1})$ over finite fields $\mathbb{F}_{2^n}$, that is, $\AI(\Tr(\lambda x^{-1}))=\floor{\sqrt{n}}+\ceil{\frac{n}{\floor{\sqrt{n}}}}-2=\ceil{2\sqrt{n}}-2$, where $n\ge2$, $\lambda\in \mathbb{F}_{2^n}$ and $\lambda\ne0$, which is just the upper bound given by Y. Nawaz et al. And at the same time our result shows that D.K. Dalai' conjecture on the algebraic immunity of $\Tr(\lambda x^{-1})$ is correct. What is more, we further demonstrate some weak properties of $\Tr(\lambda x^{-1})$ in resistance to fast algebraic attacks.

GOST R is the hash function standard of Russia. This paper presents some cryptanalytic results on GOST R. Using the rebound attack technique, we achieve collision attacks on the reduced round compression function. Result on up to 9.5 rounds is proposed, the time complexity is 2^{176} and the memory requirement is 2^{128} bytes. Based on the 9.5-round collision result, a limited birthday distinguisher is presented. More over, a method to construct k collisions on 512-bit version of GOST R is given which show the weakness of the structure used in GOST R. To the best of our knowledge, these are the first results on GOST R.

Polynomial selection is one important step in the number field sieve. A good polynomial can reduce the factorization time. In this paper, we propose a new model for the polynomial selection in an elementary geometric view. With this model, many existing requirements on polynomial selection can be taken into consideration simultaneously. With this model, the criterion for a polynomial to be ideal is that its leading coefficient should be as small as possible, all coefficients be skewed uniformly, the signs of even degree coefficients should alternate, and the signs of odd degree coefficients should alternate too. From the ideal criterion, two practical criteria are drawn. The first is that the leading coefficient should be as small as possible. The second is that the signs of coefficients of degree $d-2$ for polynomials of degree $d$ should be negative. These two criteria are confirmed by lots of experiments and adopted by Cado-NFS project.