Many cryptographic primitives---such as pseudorandom generators, encryption schemes, and zero-knowledge proofs---center around the notion of \emph{approximability}. For instance, a pseudorandom generator is an expanding function which on a random seed, \emph{approximates} the uniform distribution. In this paper, we classify different notions of computational approximability in the literature, and provide several new types of approximability. More specifically, we identify two hierarchies of computational approximability: The first hierarchy ranges from \emph{strong} approximability---which is the most common type in the cryptography---to the \emph{weak} approximability---as defined by Dwork \emph{et al.} (FOCS 1999). We define semi-strong, mild, and semi-weak types as well. The second hierarchy, termed $K$-approximability, is inspired by the $\varepsilon$-approximability of Dwork \emph{et al.} (STOC 1998). $K$-approximability has the same levels as the first hierarchy, ranging from strong $K$-approximability to weak $K$-approximability. While both hierarchies are general and can be used to define various cryptographic constructs with different levels of security, they are best illustrated in the context of zero-knowledge protocols. Assuming the existence of (trapdoor) one-way permutations, and exploiting the random oracle model, we present a separation between two definitions of zero knowledge: one based on strong $K$-approximability, and the other based on semi-strong $K$-approximability. Especially, we present a protocol which is zero knowledge only in the latter sense. The protocol is interesting in its own right, and can be used for efficient identification. Next, we show that our model for zero knowledge was \emph{not} closed under sequential composition, and change the model to resolve this issue. After proving a composition theorem, we finally provide a version of the identification protocol which satisfies the requirements of the new model. Some techniques provided in this paper are of independent interest, such as proving a composition theorem in the presence of both simulator and knowledge extractor.

This paper deals with efficient non-malleable zero-knowledge proofs for NP, based on general assumptions. We construct a simulation-sound zero-knowledge protocol for NP, based only on the black-box use of one-way functions. Constructing such a proof system has been an open question ever since the original work of Dolev, Dwork, and Naor [DDN'91]. In addition to the feasibility result, our protocol has a constant number of rounds, which is asymptotically optimal. Traditionally, the term non-malleable zero-knowledge (NMZK) refers to the original definition of Dolev et al. Today, it is used loosely to also refer to simulation-soundness (SIM-SOUND) [Sahai'99], and simulation-extractability (SIM-EXT) [PR'05]. While the common perception is that SIM-EXT is the strongest of the three notions (e.g., SIM-EXT is known to imply NMZK), a formal study of the definitional relationship between these notions has never been done. In the second part of this work, we try to correct this situation by initiating such a study. We show that in the "static" case, if an NMZK protocol is also an argument-of-knowledge, then it is in fact SIM-EXT. Furthermore, in the most strict sense of the definition, SIM-SOUND does not necessarily follow from SIM-EXT. These results are somewhat surprising because they are opposite to the common perception that SIM-EXT is the strongest of the three notions.

We consider pseudorandom generators in which each output bit depends on a constant number of input bits. Such generators have appealingly simple structure: they can be described by a sparse input-output dependency graph and a small predicate that is applied at each output. Following the works of Cryan and Miltersen (MFCS'01) and by Mossel et al (STOC'03), we focus on the study of ``small-bias" generators (that fool linear distinguishers). We prove that for most graphs, all but a handful of ``degenerate'' predicates yield small-bias generators, $f\colon \bit^n \rightarrow \bit^m$, with output length $m = n^{1 + \eps}$ for some constant $\eps > 0$. Conversely, we show that for most graphs, ``degenerate'' predicates are not secure against linear distinguishers. Taken together, these results expose a dichotomy: every predicate is either very hard or very easy, in the sense that it either yields a small-bias generator for almost all graphs or fails to do so for almost all graphs. As a secondary contribution, we attempt to support the view that small-bias is a good measure of pseudorandomness for local functions with large stretch. We do so by demonstrating that resilience to linear distinguishers implies resilience to a larger class of attacks.

The principle of random selection and the principle of adding biased noise are new paradigms used in several recent papers for constructing lightweight RFID authentication protocols. The cryptographic power of adding biased noise can be characterized by the hardness of the intensively studied Learning Parity with Noise (LPN) Problem. In analogy to this, we identify a corresponding learning problem called RandomSelect for random selection and study its complexity. Given L secret linear functions f_1,...,f_L : {0,1}^n -> {0,1}^a, RandomSelect(L,n,a) denotes the problem of learning f_1,...,f_L from values (u,f_l(u)), where the secret indices l \in {1,...,L} and the inputs u \in {0,1}^n are randomly chosen by an oracle. We take an algebraic attack approach to design a nontrivial learning algorithm for this problem, where the running time is dominated by the time needed to solve full-rank systems of linear equations over O(n^L) unknowns. In addition to the mathematical findings relating correctness and average running time of the suggested algorithm, we also provide an experimental assessment of our results.

Yao's garbled-circuit approach enables constant-round secure two-party computation for any boolean circuit. In Yao's original construction, each gate in the circuit requires the parties to perform a constant number of encryptions/decryptions, and to send/receive a constant number of ciphertexts. Kolesnikov and Schneider (ICALP 2008) proposed an improvement that allows XOR gates in the circuit to be evaluated ``for free'', i.e., incurring no cryptographic operations and zero communication. Their ``free-XOR'' technique has proven very popular, and has been shown to improve performance of garbled-circuit protocols by up to a factor of~4. Kolesnikov and Schneider proved security of their approach in the random oracle model, and claimed that (an unspecified variant of) correlation robustness would suffice; this claim has been repeated in subsequent work, and similar ideas have since been used (with the same claim about correlation robustness) in other contexts. We show that, in fact, the free-XOR technique cannot be proven secure based on correlation robustness alone: somewhat surprisingly, some form of circular security is also required. We propose an appropriate notion of security for hash functions capturing the necessary requirements, and prove security of the free-XOR approach when instantiated with any hash function satisfying our definition. Our results do not impact the security of the free-XOR technique in practice, or imply an error in the free-XOR work, but instead pin down the assumptions needed to prove security.

Companies, organizations, and individuals often wish to share information to realize valuable social and economic goals. Unfortunately, privacy concerns often stand in the way of such information sharing and exchange. This paper proposes a novel cryptographic paradigm called Policy-Enhanced Private Set Intersection (PPSI), allowing two parties to share information while enforcing the desired privacy policies. Our constructions require minimal additional overhead over traditional Private Set Intersection (PSI) protocols, and yet we can handle rich policy semantics previously not possible with traditional PSI and Authorized Private Set Intersection (APSI) protocols. Our scheme involves running a standard PSI protocol over carefully crafted encodings of elements formed as part of a challenge-response mechanism. The structure of these encodings resembles techniques used for aggregating BLS signatures in bilinear groups. We prove that our scheme is secure in the malicious model, under the CBDH assumption, the random oracle model, and the assumption that the underlying PSI protocol is secure against malicious adversaries.

We propose a 2-party UC-secure protocol that can compute any function securely. The protocol requires only two messages, communication that is poly-logarithmic in the size of the circuit description of the function, and the workload for one of the parties is also only poly-logarithmic in the size of the circuit. This implies, for instance, delegatable computation that requires no expensive off-line phase and remains secure even if the server learns whether the client accepts its results. To achieve this, we define two new notions of extractable hash functions, propose an instantiation based on the knowledge of exponent in an RSA group, and build succinct zero-knowledge arguments in the CRS model.

We define a new notion of relatively-sound non-interactive zero-knowledge (NIZK) proofs, where a private verifier with access to a trapdoor continues to be sound even when the Adversary has access to simulated proofs and common reference strings. It is likely that this weaker notion of relative-soundness suffices in most applications which need simulation-soundness. We show that for certain languages which are diverse groups, and hence allow smooth projective hash functions, one can obtain more efficient single-theorem relatively-sound NIZKs as opposed to simulation-sound NIZKs. We also show that such relatively-sound NIZKs can be used to build rather efficient publicly-verifiable CCA2-encryption schemes. By employing this new publicly-verifiable encryption scheme along with an associated smooth projective-hash, we show that a recent PAK-model single-round password-based key exchange protocol of Katz and Vaikuntanathan, Proc. TCC 2011, can be made much more efficient. We also show a new single round UC-secure password-based key exchange protocol with only a constant number of group elements as communication cost, whereas the previous single round UC-protocol required $\Omega(k)$ group elements, where $k$ is the security parameter.

We present new candidates for quantum-resistant public-key cryptosystems based on the conjectured difficulty of finding isogenies between supersingular elliptic curves. The main technical idea in our scheme is that we transmit the images of torsion bases under the isogeny in order to allow the parties to construct a shared commutative square despite the noncommutativity of the endomorphism ring. Our work is motivated by the recent development of a subexponential-time quantum algorithm for constructing isogenies between ordinary elliptic curves. In the supersingular case, by contrast, the fastest known quantum attack remains exponential, since the noncommutativity of the endomorphism ring means that the approach used in the ordinary case does not apply. We give a precise formulation of the necessary computational assumptions along with a discussion of their validity, and prove the security of our protocols under these assumptions. In addition, we present implementation results showing that our protocols are multiple orders of magnitude faster than previous isogeny-based cryptosystems over ordinary curves. This paper is an extended version of~\cite{pqcrypto}. We add a new zero-knowledge identification scheme, and detailed security proofs for the protocols. We also present a new, asymptotically faster, algorithm for key generation, a thorough study of its optimization, and new experimental data.

Embedded implementations of cryptographic primitives need protection against Side Channel Analysis. Stochastic attacks, introduced by Schindler et al. at CHES 2005, are an example of such an analysis. They offer a pertinent alternative to template attacks which efficiency is optimal, and they can theoretically defeat any kind of countermeasure including masking. In both template and stochastic attacks, the adversary needs to be able to carry out a profiling stage on a perfect copy of the target device. This makes them interesting tools to study the resistance of implementations against such a powerful adversary, but it limits their pertinency in practice. It is indeed difficult to have an open access to a copy of the device under attack and, even when it is possible, it remains difficult to exploit templates acquired on one device to attack another one. In this paper, we propose a new attack technique which shares many similarities with stochastic attacks but does not require any profiling stage. As a consequence, no copy of the device is needed anymore. We conduct an in-depth analysis of this new attack to highlight its core foundations. Then, we apply it to widely used masking schemes and we illustrate its interest by a series of experiments on simulated and real curves.

Unlike the standard notion of pseudorandom functions (PRF), a non-adaptive PRF is only required to be indistinguishable from a random function in the eyes of a non-adaptive distinguisher (i.e., one that prepares its oracle calls in advance). A recent line of research has studied the possibility of a direct construction of adaptive PRFs from non-adaptive ones, where direct means that the constructed adaptive PRF uses only few (ideally, constant number of) calls to the underlying non-adaptive PRF. Unfortunately, this study has only yielded negative results, showing that ``natural" such constructions are unlikely to exist (e.g., Myers [EUROCRYPT '04], Pietrzak05 [CRYPTO '05, EUROCRYPT '06]). We give an affirmative answer to the above question, presenting a direct construction of adaptive PRFs from non-adaptive ones. The suggested construction is extremely simple, a composition of the non-adaptive PRF with an appropriate pairwise independent hash function.

We present a study on the algebraic degree of iterated permutations seen as multivari- ate polynomials. Our main result shows that this degree depends on the algebraic degree of the inverse of the permutation which is iterated. This result is also extended to non-injective balanced vectorial functions where the relevant quantity is the minimal degree of the inverse of a permutation expanding the function. This property has consequences in symmetric cryptography since several attacks or distinguishers exploit a low algebraic degree, like higher-order differential attacks, cube attacks and cube testers, or algebraic attacks. Here, we present some applications of this improved bound to a higher-degree variant of the block cipher KN , to the block cipher Rijndael-256 and to the inner permutations of the hash functions ECHO and JH.

The wild McEliece cryptosystem uses wild Goppa codes over finite fields to achieve smaller public key sizes compared to the original McEliece cryptosystem at the same level of security against all attacks known. However, the cryptosystem drops one of the confidence-inspiring shields built into the original McEliece cryptosystem, namely a large pool of Goppa polynomials to choose from. This paper shows how to achieve almost all of the same reduction in key size while preserving this shield. Even if support splitting could be (1) generalized to handle an unknown support set and (2) sped up by a square-root factor, polynomial-searching attacks in the new system will still be at least as hard as information-set decoding. Furthermore, this paper presents a set of concrete cryptanalytic challenges to encourage the cryptographic community to study the security of code-based cryptography. The challenges range through codes over F_2, F_3,..., F_32, and cover two different levels of how much the wildness is hidden.

We give new methods for generating and using ``strong trapdoors'' in cryptographic lattices, which are simultaneously simple, efficient, easy to implement (even in parallel), and asymptotically optimal with very small hidden constants. Our methods involve a new kind of trapdoor, and include specialized algorithms for inverting $\lwe$, randomly sampling $\sis$ preimages, and securely delegating trapdoors. These tasks were previously the main bottleneck for a wide range of cryptographic schemes, and our techniques substantially improve upon the prior ones, both in terms of practical performance and quality of the produced outputs. Moreover, the simple structure of the new trapdoor and associated algorithms can be exposed in applications, leading to further simplifications and efficiency improvements. We exemplify the applicability of our methods with new digital signature schemes and CCA-secure encryption schemes, which have better efficiency and security than the previously known lattice-based constructions.

SQUARE, an 8-round substitution-permutation block cipher, is considered as the predecessor of the AES. In this paper, inspired from the recent biclique attack on the AES by Bogdanov et al., we present the first single-key attack on full SQUARE. First, we introduce a biclique for 3 rounds of SQUARE using the independent related-key differentials. Then, we present an attack on the full round of this cipher with a data complexity of about 2^48 chosen plaintexts and a time complexity of about 2^126 encryptions.

This paper proposes a novel construction, called duplex, closely related to the sponge construction, that accepts message blocks to be hashed and, at no extra cost, provides digests on the input blocks received so far. It can be proven equivalent to a cascade of sponge functions and hence inherits its security against single-stage generic attacks. The main application proposed here is an authenticated encryption mode based on the duplex construction. This mode is efficient, namely, enciphering and authenticating together require only a single call to the underlying permutation per block, and is readily usable in, e.g., key wrapping. Furthermore, it is the first mode of this kind to be directly based on a permutation instead of a block cipher and to natively support intermediate tags. The duplex construction can be used to efficiently realize other modes, such as a reseedable pseudo-random bit sequence generators and a sponge variant that overwrites part of the state with the input block rather than to XOR it in.

Proxy signature schemes can be used in many business applications such as when the original signer is not present to sign important documents. Any proxy signature scheme has to meet the identifiability, undeniability, verifiability and unforgeability security requirements. In some conditions, it may be necessary to protect the proxy signer’s privacy from outsiders or third parties. Recently, several studies about proxy signature schemes have been conducted but only Yu et al.’ anonymous proxy signature scheme proposed in 2009 attempting to protect the proxy signer’s privacy from outsiders. They claimed their scheme can make the proxy signer anonymous. However, based on our research, we determined that this was not the case and the proxy signer’s privacy was not anonymous. Hence, in this paper, we propose a new anonymous proxy signature scheme that truly makes the proxy signer anonymous while making it more secure and efficient when compared with Yu et al.’s scheme in 2009. Our proxy signature scheme consists of two constructions. First, we mainly use random numbers and bilinear pairings to attain the anonymous property in our proxy. Secondly, we increase the security, integrity, and efficiency of our proxy through modifications.

Shape-memory alloys are metal pieces that "remember" their original cold-forged shapes and return to the pre-deformed shape after heating. In this work we construct a software analogous of shape-memory alloys: programs whose code resists obfuscation. We show how to pour arbitrary functions into protective envelops that allow recovering the functions' {\sl exact initial code} after obfuscation. We explicit the theoretical foundations of our method and provide a concrete implementation in Scheme.

We show that the Feistel construction with six rounds and random round functions is publicly indifferentiable from a random invertible permutation (a result that is not known to hold for full indifferentiability). Public indifferentiability (pub-indifferentiability for short) is a variant of indifferentiability introduced by Yoneyama et al. \cite{YoneyamaMO09} and Dodis et al. \cite{DodisRS09} where the simulator knows all queries made by the distinguisher to the primitive it tries to simulate, and is useful to argue the security of cryptosystems where all the queries to the ideal primitive are public (as e.g. in many digital signature schemes). To prove the result, we introduce a new and simpler variant of indifferentiability, that we call sequential indifferentiability (seq-indifferentiability for short) and show that this notion is in fact equivalent to pub-indifferentiability for stateless ideal primitives. We then prove that the 6-round Feistel construction is seq-indifferentiable from a random invertible permutation. We also observe that sequential indifferentiability implies correlation intractability, so that the Feistel construction with six rounds and random round functions yields a correlation intractable invertible permutation, a notion we define analogously to correlation intractable functions introduced by Canetti et al. \cite{CanettiGH98}.

We put forward the study of a new primitive that we call {\em Vector Commitment} (VC, for short). Informally, VCs allow to commit to an ordered sequence of $q$ values $(m_1, \ldots, m_q)$ in such a way that one can later open the commitment at specific positions (e.g., prove that $m_i$ is the $i$-th committed message). For security, Vector Commitments are required to satisfy a notion that we call \emph{position binding} which states that an adversary should not be able to open a commitment to two different values at the same position. Moreover, what makes our primitive interesting is that we require VCs to be {\em concise}, i.e. the size of the commitment string and of its openings has to be independent of the vector length. We show two realizations of VCs based on standard and well established assumptions, such as RSA, and Computational Diffie-Hellman (in bilinear groups). Next, we turn our attention to applications and we show that Vector Commitments are useful in a variety of contexts, as they allow for compact and efficient solutions which significantly improve previous works either in terms of efficiency of the resulting solutions, or in terms of "quality" of the underlying assumption, or both. These applications include: Verifiable Databases with Efficient Updates, Updatable Zero-Knowledge Databases, and Universal Dynamic Accumulators.

The problem of generating an RSA composite in a distributed manner without leaking its factorization is particularly challenging and useful in many cryptographic protocols. Our first contribution is the first non-generic fully simulatable protocol for distributively generating an RSA composite with security against malicious behavior. Our second contribution is complete Paillier [Pai99] threshold encryption scheme in the two-party setting with security against malicious behavior. Furthermore, we describe how to extend our protocols to the multiparty setting with dishonest majority. Our RSA key generation is comprised of the following: (i) a distributed protocol for generation of an RSA composite, and (ii) a biprimality test for verifying the validity of the generated composite. Our Paillier threshold encryption scheme uses the RSA composite as public key and is comprised of: (i) a distributed generation of the corresponding secret-key shares and, (ii) a distributed decryption protocol for decrypting according to Paillier.

We construct 3-round proofs and arguments with negligible soundness error satisfying two relaxed notions of {\em zero-knowledge}: {\em Weak ZK} and {\em witness hiding} (WH). At the heart of our constructions lie new techniques based on {\em point obfuscation with auxiliary input} (AIPO). It is known that such protocols cannot be proven secure using black-box reductions (or simulation). Our constructions circumvent these lower bounds, utilizing AIPO (and extensions) as the ``non-black-box component" in the security reduction. We also investigate the relation between AIPO and the assumptions previously used to achieve 3-round ZK.

We use ideas from game theory to define a new notion for an optimal threshold for the number of erroneous responses that occur during the rapid-bit exchange over noisy channels in a distance-bounding protocol. The optimal threshold will ensure that even if an intruder attempts to cause incorrect authentication, the expected loss the verifier suffers will still be lower than when the intruder does not attack. Any rational intruder, who always tries to maximise the verifier's loss, will not therefore have any incentive to attack the protocol. We then demonstrate how statistical analysis and binary search can be used to locate such a unique and optimal threshold accurately.

Quite recently, Yang et al. proposed an effective security architecture to achieve secure and privacy-preserving communication and precise reward for battery vehicles (BVs) in a vehicle-to-grid (V2G) network. In this letter, we will point out their scheme has a serious security flaw, and show that the scheme fails to achieve mutual authentication between the BV and aggregators.

In this paper, we explore a general methodology for converting composite order pairing-based cryptosystems into the prime order setting. We employ the dual pairing vector space approach initiated by Okamoto and Takashima and formulate versatile tools in this framework that can be used to translate composite order schemes for which the prior techniques of Freeman were insufficient. Our techniques are typically applicable for composite order schemes relying on the canceling property and proven secure from variants of the subgroup decision assumption, and will result in prime order schemes that are proven secure from the decisional linear assumption. As an instructive example, we obtain a translation of the Lewko-Waters composite order IBE scheme. This provides a close analog of the Boneh-Boyen IBE scheme that is proven fully secure from the decisional linear assumption. We also provide a translation of the Lewko-Waters unbounded HIBE scheme.

In this paper, we present new general techniques for practical security evaluation against differential and linear cryptanalysis for an extensive class of block ciphers similar to the cipher GOST. We obtain upper bounds of the average differential and linear characteristic probabilities for an arbitrary GOST-like cipher. The obtained bounds have similar form to the upper bounds of the average differential and linear characteristic probabilities known for some Markov Feistel ciphers. But, the expressions of our bounds contain new parameters (different from the classical differential and linear probabilities) of the cipher's $s$-boxes. These parameters are very natural for GOST-like ciphers, since they inherit the type of operation (key addition modulo $2^m$) used in these ciphers. The methods our proofs are based on are of independent interest and can be used for investigation both of a wider class of block ciphers and of a wider class of attacks. Application of our results to GOST shows that maximum values of the average differential and linear characteristic probabilities of this cipher (with 32 rounds and some $s$-boxes) are bounded by $2^{-59.57}$ and $2^{-42}$, respectively. The last two estimates of practical security of GOST against the differential and linear cryptanalysis are not quite impressive. But, as far as we know, they are the best of such estimates obtained by an accurate mathematical proof.

This paper studies a new notion of a hardware: physically unclonable verifiable object (PUVO). Such objects are usually used in authentications. In the context of cryptography, we study the relation of such objects to Bit Commitment (BC) and Oblivious Transfer (OT). Both possibility and impossibility results are found.

The notion of differential privacy has recently emerged as a gold standard in the field of database privacy. While this notion has the benefit of providing concrete theoretical privacy (compared to various previous ad-hoc approaches), the major drawback is that the mechanisms needs to inject some noise the output limiting its applicability in many settings. In this work, we initiate the study of a new notion of privacy called \emph{noiseless privacy}. The (very natural) idea we explore is to exploit the entropy already present in the database and substitute that in the place of external noise to the output. The privacy guarantee we provide is very similar to DP but where that guarantee ``comes from" is very different in the two cases. While differential privacy focuses on generality, we make assumptions about the database distribution, the auxiliary information which the adversary may have and the type of queries. This allows us to obtain ``privacy for free" whenever the underlying assumptions are satisfied. In this work, we first formalize the notion of noiseless privacy, introduce two definitions and show that they are equivalent. We then study certain types of boolean and real queries and show natural (and well understood) conditions under which noiseless privacy can be obtained with good parameters. We also study the issue of composability and introduce models under which it can be achieved in the noiseless privacy framework.

We revisit the topic of joint security for combined public key schemes, wherein a single keypair is used for both encryption and signature primitives in a secure manner. While breaking the principle of key separation, such schemes have attractive properties and are sometimes used in practice. We give a general construction for a combined public key scheme having joint security that uses IBE as a component and that works in the standard model. We provide a more efficient direct construction, also in the standard model. We then consider the problem of how to build signcryption schemes from jointly secure combined public key schemes. We provide a construction that uses any such scheme to produce a triple of schemes -- signature, encryption, and signcryption -- that are jointly secure in an appropriate and strong security model.

I continue the discussion initiated in part I of whether or not computer-assisted proofs are a promising approach to preventing errors in reductionist security arguments. I examine some recent papers that describe automated security proofs for hashed ElGamal encryption, Boneh-Franklin identity-based encryption, and OAEP.

We present the hash-based signature scheme XMSS. It is the first provably (forward) secure and practical signature scheme with minimal security requirements: a pseudorandom and a second preimage resistant (hash) function family. Its signature size is reduced to less than 25% compared to the best provably secure hash based signature scheme.

In \cite{BKT11} Baba, Kotyada and Teja introduced the FACTOR problem over non-abelian groups as base of an ElGamal-like cryptosystem. They conjectured that there is no better method than the naive one to solve the FACTOR problem in a general group. Shortly afterwards Stanek published an extension of the baby-step giant-step algorithm disproving this conjecture \cite{Sta11}. Since baby-step giant-step methods are limited in practice because of memory requirements we present a modification of Pollard's kangaroo algorithm that solves the FACTOR problem requiring only negligible memory.

Traditional approaches to secure computation begin by representing the function $f$ being computed as a circuit. For any function~$f$ that depends on each of its inputs, this implies a protocol with complexity at least linear in the input size. In fact, linear running time is inherent for secure computation of non-trivial functions, since each party must ``touch'' every bit of their input lest information about other party's input be leaked. This seems to rule out many interesting applications of secure computation in scenarios where at least one of the inputs is huge and sublinear-time algorithms can be utilized in the insecure setting; private database search is a prime example. We present an approach to secure two-party computation that yields sublinear-time protocols, in an amortized sense, for functions that can be computed in sublinear time on a random access machine~(RAM). Furthermore, a party whose input is ``small'' is required to maintain only small state. We provide a generic protocol that achieves the claimed complexity, based on any oblivious RAM and any protocol for secure two-party computation. We then present an optimized version of this protocol, where generic secure two-party computation is used only for evaluating a small number of simple operations.

In this paper we analyze a simple method for generating prime numbers with fewer random bits. Assuming the Extended Riemann Hypothesis, we can prove that our method generates primes according to a distribution that can be made arbitrarily close to uniform. This is unlike the PRIMEINC algorithm studied by Brandt and Damg\aa{a}rd and its many variants implemented in numerous software packages, which reduce the number of random bits used at the price of a distribution easily distinguished from uniform. Our new method is also no more computationally expensive than the ones in current use, and opens up interesting options for prime number generation in constrained environments.

The Subset Difference (SD) method proposed by Naor-Naor-Lotspeich is the most popular broadcast encryption (BE) scheme. It is suitable for real-time applications like Pay-TV. It has been suggested for use by the AACS standard for digital rights management in Blu-Ray and DVD discs. The SD method assumes the number of users to be a power of two. (1) We propose the Complete Tree Subset Difference (CSD) method that subsumes the SD method by allowing arbitrary number of users in the system. All the results obtained in this work for the CSD scheme hold good for the SD scheme by assuming the number of users to be the next power of two. (2) Given the importance of the SD scheme, its detailed combinatorial analysis is of practical interest. We find recurrences for the CSD scheme to count the number of possible ways $r$ users in the system of $n$ users can be revoked to result in a transmission overhead (header length) of $h$. The header length $h$ of a broadcast is an important efficiency parameter in BE. The usefulness of these recurrences is demonstrated by generating exhaustive data of the above count, obtaining bounds on the header length and various other interesting results some of which are difficult to prove without the recurrences. (3) An $O(r \log{n})$ time algorithm is proposed to compute the expected header length in the CSD scheme for $n$ users in the system, $r$ out of which are revoked. This algorithm is of practical interest in its own right, for efficiency and performance analysis of the CSD scheme. Using this algorithm, we show that for practical values of $n$ and $r$, the transmission efficiency of the CSD scheme is better than the SD scheme. For $n$ a power of two and a fixed $r \geq 2$, we obtain an upper bound on the expected header length and show that this bound is also the limit as $n \rightarrow \infty$.

We provide the first constructions of identity-based (injective) trapdoor functions. Furthermore, they are lossy. Constructions are given both with pairings (DLIN) and lattices (LWE). Our lossy identity-based trapdoor functions provide an automatic way to realize, in the identity-based setting, many functionalities previously known only in the public-key setting. In particular we obtain the first deterministic and efficiently searchable IBE schemes and the first hedged IBE schemes, which achieve best possible security in the face of bad randomness. Underlying our constructs is a new definition, of partial lossiness, that may be of broader interest.

Due to avoiding the key escrow problem in the identity-based cryptosystem, certificateless public key cryptosystem (CLPKC) has received a significant attention. As an important part of the CLPKC, the certificateless authenticated key agreement (CLAKA) scheme also received considerable attention. Most CLAKA schemes are built from bilinear mappings on elliptic curves which need costly operations. To improve the performance, several pairing-free CLAKA schemes have been proposed. In this paper we propose a new pairing-free CLAKA scheme. Compared with the related schemes our scheme has better performance. We also show our scheme is provably secure in a very strong security model, i.e. the extended Canetti-Krawczyk (eCK) model.

NTRU is a fast public key cryptosystem presented in 1996 by Hoffstein, Pipher and Silverman. It operates in the ring of truncated polynomials. In NTRU, a public key is a polynomial defined by the combination of two private polynomials. In this paper, we consider NTRU with two different public keys defined by different private keys. We present a lattice-based attack to recover the private keys assuming that the public keys share polynomials with a suitable number of common coefficients.

In this paper we consider anonymity in the context of Broadcast Encryption (BE). This issue has received very little attention so far and all but one of the currently available BE schemes fail to provide anonymity. Yet, we argue that it is intrinsically desirable to provide anonymity in standard applications of BE and that it can be achieved at a moderate cost. We provide a security definition for Anonymous Broadcast Encryption (ANOBE) and show that it is achievable assuming only the existence of IND-CCA secure public key encryption (PKE). Focusing on reducing the size of ciphertexts, we then give two generic constructions for ANOBE. The first is from any anonymous (key-private) IND-CCA secure PKE scheme, and the second is from any IBE scheme that satisfies a weak security notion in the multi-TA setting. Furthermore, we show how randomness re-use techniques can be deployed in the ANOBE context to reduce computational and communication costs, and how a new cryptographic primitive -- anonymous hint systems -- can be used to speed up the decryption process in our ANOBE constructions. Finally, we present a slightly modified version of the Kurosawa-Desmedt (KD) PKE scheme (establishing several results about this scheme that may be of independent interest) and use it to instantiate our first main construction, yielding the currently most efficient ANOBE scheme. All of our results are in the standard model, achieving fully collusion-resistant ANOBE schemes secure against adaptive IND-CCA adversaries.

One of the hardest problems in computer science is the problem of gate-eficient implementation. Such optimizations are particularly important in industrial hardware implementations of standard cryptographic algorithms. In this paper we focus on optimizing some small circuits such as S-boxes in cryptographic algorithms. We consider the notion of Multiplicative Complexity studied in 2008 by Boyar and Peralta and applied to find interesting optimizations for the S-box of the AES cipher. We applied this methodology to produce a compact implementation of several ciphers. In this short paper we report our results on PRESENT and GOST, two block ciphers known for their exceptionally low hardware cost. This kind of representation seems to be very promising in implementations aiming at preventing side channel attacks on cryptographic chips such as DPA. More importantly, we postulate that this kind of minimality is also an important and interesting tool in cryptanalysis.

At Eurocrypt 2010, Howgrave-Graham and Joux described an algorithm for solving hard knapsacks of density close to 1 in time O(2^0.337n) and memory O(2^0.256n), thereby improving a 30-year old algorithm by Shamir and Schroeppel. In this paper we extend the Howgrave-Graham Joux technique to get an algorithm with running time down to O(2^0.291n). An implementation shows the practicability of the technique. Another challenge is to reduce the memory requirement. We describe a constant memory algorithm based on cycle finding with running time O(2^0.72n); we also show a time-memory tradeoff.

In this paper, we propose a novel one-way function, which is equivalent to large integer factorization. From this new one-way function, we construct a novel verifiable delegation scheme for polynomial. Our contribution is twofold: in the practice aspect, our proposed polynomial delegation scheme is about 100 times faster than the existing solutions~\cite{PolyCommit,PolyDeleg} and has constant key size where the existing works require linear key size w.r.t. the degree of the delegated polynomial; in the theory part, our proposed scheme is provably secure under large integer factorization, which is a much weaker assumption than that of existing works. The efficient polynomial delegation scheme can be applied in constructing proofs of retrievability scheme, verifiable keyword search and verifiable dictionary data structure and so on. Furthermore, our new one-way function may have independent interests.

In this paper, we propose a forward secure ring signature scheme without random oracles. With forward security, if a secret key of a corresponding ring member is exposed, all previously signed signatures containing this member remain valid. Yet the one who has stolen the secret key cannot produce any valid signature belonged to the past time period. This is especially useful in the case of ring signature, as the exposure of a single secret key may result in the invalidity of thousands or even millions ring signatures which contain that particular user. The only one with this feature relies on random oracles to prove the security. We are the first to construct a forward secure ring signature scheme that can be proven secure without random oracles. Our scheme can be deployed in many applications, such as wireless sensor networks and smart grid system.

A key problem with the original implementation of the Gentry Fully Homomorphic Encryption scheme was the slow key generation process. Gentry and Halevi provided a fast technique for $2$-power cyclotomic fields. We present an extension of the Gentry--Halevi key generation technique for arbitrary cyclotomic fields. Our new method is roughly twice as efficient as the previous best methods. Our estimates are backed up with experimental data.

We propose an extension to the BRSIM/UC library of Backes, Pfitzmann and Waidner [1] with non-malleable public key encryption. We also investigate the requirement of “full randomization” of public key encryption primitives in [1], and show that additional randomization to attain word uniqueness is theoretically not justified.

The cryptographic algorithm called INCrypt32 is a MAC algorithm to authenticate participants, RFID cards and readers, in HID Global's iCLASS systems. HID's iCLASS cards are widely used contactless smart cards for physical access control. Although INCrypt32 is a heart of the security of HID's iCLASS systems, its security has not been evaluated yet since the specication has not been open to public. In this paper, we reveal the specication of INCrypt32 by reverse engineering an iCLASS card and investigate the security of INCrypt32. As a result, we show that the secret key of size 64 bits can be recovered using only $2^{18}$ MAC queries if the attacker can request MAC for chosen messages of arbitrary length. If the length of messages is limited to predetermined values by the authentication protocol, the required number of MAC queries grows to $2^{42}$ to recover the secret key.

This paper proposes new explicit formulae for the point doubling, tripling and addition on ordinary Weierstrass elliptic curves over finite fields of characteristic three. The cost of basic point operations is lower than that of all previously proposed ones. The new doubling, mixed addition and tripling formulae in projective coordinates require 3M+2C, 8M+1C+1D and 4M+4C+1D respectively, where M, C and D is the cost of a field multiplication, a cubing and a multiplication by a constant. We also provide the unified and complete group laws. Finally, we present several examples of ordinary elliptic curves in characteristic three for high security levels.

The Diophantine Equation Hard Problem (DEHP) is a potential cryptographic problem on a Diophantine equation. The DEHP has been in existence for ``worst case scenario" of the RSA, Diffie-Hellman and El-Gammal schemes. However, the DEHP emerges after the exponentiation and modular reduction process. The proposed scheme (known as the $AA_{\beta}$-cryptosystem) is an asymmetric cryptographic scheme that utilizes this concept (without any prior mathematical operation) together with the factorization problem of two large primes. Its encryption speed has a complexity order faster than the Diffie-Hellman Key Exchange, El-Gammal, RSA and ECC. It can encrypt large data sets than its key size. It has a simple mathematical structure. Thus, it would have low computational requirements and would enable communication devices with low computing power to deploy secure communication procedures efficiently.

KASUMI is a block cipher with eight Feistel rounds and a key of up to 128 bits. Proposed more than 10 years ago, the confidentiality and integrity of 3G mobile communications systems depend on the security of KASUMI. In the practically interesting single key setting that we are aiming for in this work, no attack is known. For the full 8-round KASUMI we show for the first time a wide variety of results with data complexities between $2^{32}$ chosen plaintexts and as few as 2 texts, while the speed-ups over brute force are between a factor 4 and 6. For use-cases of KASUMI in 2G networks, relying on a 64-bit master key, we describe key recovery methods with extremely low data complexity and speed-ups between a factor 2 and 3 for essentially any desired success probability. The latter results are the first of this type of cryptanalysis that could result in practically realizable cost and energy savings for key recovery efforts. By also analyzing an earlier version of the KASUMI-64 design that had a different mapping from the 64-bit master key to the 128-bit cipher key, we shed some light on a high-level key schedule design issue that may be of independent interest.

Barreto-Lynn-Scott (BLS) curves are a stand-out candidate for implementing high-security pairings. This paper shows that particular choices of the pairing-friendly search parameter give rise to four subfamilies of BLS curves, all of which offer highly efficient and implementation- friendly pairing instantiations. Curves from these particular subfamilies are defined over prime fields that support very efficient towering options for the full extension field. The coefficients for a specific curve and its correct twist are automat- ically determined without any computational effort. The choice of an extremely sparse search parameter is immediately reflected by a highly efficient optimal ate Miller loop and final exponentiation. As a resource for implementors, we give a list with examples of implementation-friendly BLS curves through several high-security levels.

Privacy-preserving set operations, and set intersection in particular, are a popular research topic. Despite a large body of literature, the great majority of the available solutions are two-party protocols and are not composable. In this work we design a comprehensive suite of secure multi-party protocols for set and multiset operations that are composable, do not assume any knowledge of the sets by the parties carrying out the secure computation, and can be used for secure outsourcing. All of our protocols have communication and computation complexity of $O(m \log m)$ for sets or multisets of size $m$, which compares favorably with prior work. Furthermore, we are not aware of any results that realize composable operations. Our protocols are secure in the information theoretic sense and are designed to minimize the round complexity. Practicality of our solutions is shown through experimental results.

A broadcast encryption system generally involves three kinds of entities: the group manager that deals with the membership, the encryptor that encrypts the data to the registered users according to a specific policy (the target set), and the users that decrypt the data if they are authorized by the policy. Public-key broadcast encryption can be seen as removing this special role of encryptor, by allowing anybody to send encrypted data. In this paper, we go a step further in the decentralization process, by removing the group manager: the initial setup of the group, as well as the addition of further members to the system, do not require any central authority. Our construction makes black-box use of well-known primitives and can be considered as an extension to the subset-cover framework. It allows for efficient concrete instantiations, with parameter sizes that match those of the subset-cover constructions, while at the same time achieving the highest security level in the standard model under the DDH assumption.

Today biometric data propagate more heavily into our lives. With more ubiquitous use of such data, computations over biometrics become more prevalent as well. While it is well understood that privacy of biometric data must be protected, often computations over biometric data involve untrusted participants or servers, let it be a cross check between different agencies who are not permitted to share the data or a researcher testing a new biometric matching algorithm on a large scale that forces the computation to be placed on a grid. Unarguably, it would be desirable to secure computation over sensitive biometric data in such environments. Currently, no secure techniques for outsourcing biometric comparisons or searching are readily available, and this work makes the first step at designing solutions for secure outsourcing iris identification to one or more untrusted servers. We develop new solutions for the single-server (i.e., non-interactive) and multiple-server settings that use significantly different techniques. Furthermore, we carry out extensive experimentation on a database of iris codes to both validate the findings and achieve efficiency improvements.

Pollard rho method and its parallelized variants are at present known as the best generic algorithms for computing elliptic curve discrete logarithms. We propose new iteration function for the rho method by exploiting the fact that point halving is more efficient than point addition for elliptic curves over binary fields. We present a careful analysis of the alternative rho method with new iteration function. Compared to the previous $r$-adding walk, generally the new method can achieve a significant speedup for computing elliptic curve discrete logarithms over binary fields. For instance, for certain NIST-recommended curves over binary fields, the new method is about 27\% faster than the previous best methods in single-instance Pollard rho method. When running several instances of Pollard rho method concurrently, and computing the inversions using the simultaneous inversion algorithm by Peter Montgomery, the new method is about 12-17\% faster than the previous best methods.

Canetti and Herzog have proposed a universally composable symbolic analysis (UCSA) of mutual authentication and key exchange protocols within universally composable security framework. It is fully automated and computationally sound symbolic analysis. Furthermore, Canetti and Gajek have analyzed Diffie-Hellman based key exchange protocols as an extension of their work. It deals with forward secrecy in case of fully adaptive party corruptions. However, their work only addresses two-party protocols that use public key encryptions, digital signatures and Diffie-Hellman exchange. We make the following contributions. First, we extend UCSA approach to analyze group key exchange protocols that use bilinear pairings exchange and digital signatures to resist insider attack under fully adaptive party corruptions with respect to forward secrecy. Specifically, we propose an formal algebra, and property of bilinear pairings in the execution of group key exchange protocol among arbitrary number of participants. This provides computationally sound and fully automated analysis. Second, we reduce the security of multiple group key exchange sessions among arbitrary number of participants to the security of a single group key exchange session among three participants. This improves the efficiency of security analysis.

In this paper we give a generic security proof for hashing modes that make use of an underlying fixed-length permutation. We formulate a set of five simple conditions, which are easy to implement and to verify, for such a hashing mode to be sound. These hashing modes include tree hashing modes and sequential hashing modes. We provide a proof that for any hashing mode satisfying the five conditions, the advantage in differentiating it from an ideal monolithic hash function is upper bounded by q^2/2^{n+1} with q the number of queries to the underlying permutation and n the length of the chaining values.

Lattice based cryptography is gaining more and more importance in the cryptographic community. It is a common approach to use a special class of lattices, so-called ideal lattices, as the basis of lattice based crypto systems. This speeds up computations and saves storage space for cryptographic keys. The most important underlying hard problem is the shortest vector problem. So far there is no algorithm known that solves the shortest vector problem in ideal lattices faster than in regular lattices. Therefore, crypto systems using ideal lattices are considered to be as secure as their regular counterparts. In this paper we present IdealListSieve, a variant of the ListSieve algorithm, that is a randomized, exponential time sieving algorithm solving the shortest vector problem in lattices. Our variant makes use of the special structure of ideal lattices. We show that it is indeed possible to find a shortest vector in ideal lattices faster than in regular lattices without special structure. The practical speedup of our algorithm is linear in the degree of the field polynomial. We also propose an ideal lattice variant of the heuristic GaussSieve algorithm that allows for the same speedup.

Two central notions of Zero Knowledge that provide very strong, yet seemingly incomparable security guarantees against malicious verifiers are those of Statistical Zero Knowledge and Resettable Zero Knowledge. The current state of the art includes several feasibility and impossibility results about the two notions separately. However, the challenging question of achieving Resettable Statistical Zero Knowledge (i.e., Resettable Zero Knowledge and Statistical Zero Knowledge simultaneously) for non-trivial languages is still open. In this paper, we show: - Resettable Statistical Zero Knowledge with efficient provers: Efficient-prover Resettable Sta-tistical Zero-Knowledge proof systems exist for all languages that admit hash proof systems (e.g., QNR, QR, DDH, DCR). Furthermore, for these languages, as an application of our technique, we also construct a two-round resettable statistical witness-indistinguishable argument system. - Resettable Statistical Zero Knowledge with unbounded provers: Under the assumption that sub-exponentially hard one-way functions exist, rSZK = SZK. In other words, every language that admits a Statistical Zero-Knowledge (SZK) proof system also admits a Resettable Statistical Zero-Knowledge (rSZK) proof system. (Further, the result can be re-stated unconditionally provided there exists a sub-exponentially hard language in SZK). Moreover, under the assumption that (standard) one-way functions exist, all languages L such that the complement of L is random self reducible, admit a rSZK, in other words: co-RSR \subseteq rSZK. The round complexity of all our proof systems is O(log n), where n is the security parameter, and all our simulators are black-box.

We present a designated verifier CS proof system for polynomial time computations. The proof system can only be verified by a designated verifier: one who has published a public-key for which it knows a matching secret key unknown to the prover. Whereas Micali's CS proofs require the existence of random oracles, we can base soundness on computational assumptions: the existence of leveled fully homomorphic encryption (FHE) schemes, the DDH assumption and a new knowledge of exponent assumption. Using our designated verifier CS proof system, we construct two schemes for delegating (polynomial-time) computation. In such schemes, a delegator outsources the computation of a function $F$ on input $x$ to a polynomial time worker, who computes the output $y=F(x)$ and proves to the delegator the correctness of the output. Let $T$ be the complexity of computing $F$ on inputs of length $n=\abs x $ and let $k$ be a security parameter. Our first scheme calls for an one-time off-line stage where the delegator sends a message to the worker, and a non-interactive on-line stage where the worker sends the output together with a certificate of correctness to the prover per input $x$. The total computational complexity of the delegator during off-line and on-line stages is $ \poly(k, n, \log T)$. Compared with previous constructions by Gennaro-Gentry-Parno and Chung-Kalai-Vadhan~\cite{GGP10, CKV10} based on FHE, their on-line stage consists of two messages and their off-line stage has (delegator's) complexity of $\poly(k,n, T)$. Thus, they achieve delegator complexity $\poly(k, n, \log T)$ only in an amortized sense. Compared with the construction of \cite{GKR08} based on poly-log PIR, our first construction can handle any polynomial-time computable $F$ rather than being restricted to $\NC$ computable $F$. Our second scheme requires no off-line stage and has a two-message ``on-line'' stage with complexity of $\poly(k, n, \log T)$. Most importantly, it achieves {\em robust soundness} that guarantees that it is infeasible for a cheating worker to convince the delegator of an invalid output even if the worker learns whether the delegator accepts or rejects previous outputs and proofs. Previously the only two-round protocol that achieves robust soundness under a computational assumption appeared in \cite{GKR08} and is restricted to only $\NC$ computations.

Hierarchical inner product encryption (HIPE) and spatial encryption (SE) are two important classes of functional encryption (FE) that have a large number of applications. Although HIPE and SE both involve some notion of linear algebra, the former works in vectors while the latter is based on (affine) spaces. Moreover, they currently possess different properties in terms of security, anonymity (payload/attribute-hiding) and ciphertext sizes, for example. In this paper, we formally study the relation between HIPE and SE. In our work, we discover some interesting and novel property-preserving transformation techniques that enable generic construction of an SE scheme from an HIPE scheme, and vice versa.

Cramer, Damgård, and Nielsen~\cite{CDN01} show how to construct an efficient secure multi-party computation scheme using a threshold homomorphic encryption scheme that has four properties i) a honest-verifier zero-knowledge proof of knowledge of encrypted values, ii) proving multiplications correct iii) threshold decryption and iv) trusted shared key setup. Naor and Nissim~\cite{NN01a} show how to construct secure multi-party protocols for a function $f$ whose communication is proportional to the communication required to evaluate $f$ without security, albeit at the cost of computation that might be exponential in the description of $f$. Gentry~\cite{Gen09a} shows how to combine both ideas with fully homomorphic encryption in order to construct secure multi-party protocol that allows evaluation of a function $f$ using communication that is {\bf independent of the circuit description of $f$} and computation that is polynomial in $|f|$. This paper addresses the major drawback's of Gentry's approach: we eliminate the use of non-black box methods that are inherent in Naor and Nissim's compiler. To do this we show how to modify the fully homomorphic encryption construction of van Dijk et al.~\cite{vDGHV10} to be threshold fully homomorphic encryption schemes. We directly construct (information theoretically) secure protocols for sharing the secret key for our threshold scheme (thereby removing the setup assumptions) and for jointly decrypting a bit. All of these constructions are constant round and we thoroughly analyze their complexity; they address requirements (iii) and (iv). The fact that the encryption scheme is fully homomorphic addresses requirement (ii). To address the need for an honest-verifier zero-knowledge proof of knowledge of encrypted values, we instead argue that a weaker solution suffices. We provide a 2-round blackbox protocol that allows us to prove knowledge of encrypted bits. Our protocol is not zero-knowledge, but it provably does not release any information about the bit being discussed, and this is sufficient to prove the correctness of a simulation in a method similar to Cramer et al. Altogether, \emph{we construct the first black-box secure multi-party computation protocol that allows evaluation of a function $f$ using communication that is independent of the circuit description of $f$}.

This paper presents a survey of practical complexity differential cryptanalysis of AES and compares this to attacks that have been proposed for differential fault analysis. Naturally, the attacks in each vein of research are applicable in the other but use different models. In this paper we draw from both topics to improve attacks proposed in the literature. We re-evaluate the so-called Square attack and the use of impossible differentials in terms of differential fault analysis using a weaker model than previously considered in the literature. Furthermore, we propose two new attacks applicable to both differential cryptanalysis and differential fault analysis. The first is a differential cryptanalysis of four-round AES based on a differential that occurs with a non-negligible probability. The second is an application of the Square attack to a five-round AES that requires $2^8$ ciphertexts and a time complexity equivalent to approximately $2^{37}$ AES encryptions.

In this paper we find the lower bound of second-order nonlinearity of Boolean function $f_{\lambda}(x) = Tr_{1}^{n}(\lambda x^{p})$ with $p = 2^{2r} + 2^{r} + 1$, $\lambda \in \mathbb{F}_{2^{r}}^{*}$ and $n = 5r$. It is also demonstrated that the lower bound obtained in this paper is much better than the lower bound obtained by Iwata-Kurosawa \cite{c14}, and Gangopadhyay et al. (Theorem 1, \cite{c12}).

In 2010, Yoon et al. proposed a robust biometrics- based multi-server authentication with key agreement scheme for smart cards on elliptic curve cryptosystem. In this letter, however, we show that Yoon et al.’s scheme is vulnerable to off-line password guessing attack and propose an improved scheme to prevent the attack.

In this paper we present an improved version of HF-hash [4] viz. R-hash : Hash Function Using Random Quadratic Polynomials Over GF(2). In case of HF-hash, the compression function consists of 32 polynomials with 64 variables which were taken from the first 32 polynomials of hidden field equations challenge-1 by forcing last 16 variables as 0. Merkle-Damg°ard mode operation was used in computation of HF-hash. In R-hash, we have randomly selected 32 quadratic non-homogeneous polynomials with 64 variables over GF(2) to improve the security of the compression function used in HF-hash. We have also changed the design principle of HF-hash because of the theoretical weakness found in the Merkle-Damg°ard construction. In this paper we will prove that R-hash is more secure and much more efficient than HF-hash.

Since Rijndael was chosen as the Advanced Encryption Standard, improving upon 7-round attacks on the 128-bit key variant or upon 8-round attacks on the 192/256-bit key variants has been one of the most difficult challenges in the cryptanalysis of block ciphers for more than a decade. In this paper we present a novel technique of block cipher cryptanalysis with bicliques, which leads to the following results: 1) The first key recovery attack on the full AES-128 with computational complexity 2126.1. 2) The first key recovery attack on the full AES-192 with computational complexity 2^189.7. 3) The first key recovery attack on the full AES-256 with computational complexity 2^254.4. 4) Attacks with lower complexity on the reduced-round versions of AES not considered before, including an attack on 8-round AES-128 with complexity 2^124.9. 5) Preimage attacks on compression functions based on the full AES versions. In contrast to most shortcut attacks on AES variants, we do not need to assume any related-keys. Most of our attacks only need a very small part of the codebook and have small memory requirements, and are practically verified to a large extent. As our attacks are of high computational complexity, they do not threaten the practical use of AES in any way.

RC4 has been the most popular stream cipher in the history of symmetric key cryptography. Its internal state contains a permutation over all possible bytes from 0 to 255, and it attempts to generate a pseudo-random sequence of bytes (called keystream) by extracting elements of this permutation. Over the last twenty years, numerous cryptanalytic results on RC4 stream cipher have been published, many of which are based on non-random (biased) events involving the secret key, the state variables, and the keystream of the cipher. Though biases based on the secret key is common in RC4 literature, none of the existing ones depends on the length of the secret key. In the first part of this paper, we investigate the effect of RC4 keylength on its keystream, and report significant biases involving the length of the secret key. In the process, we prove the two known empirical biases that were experimentally reported and used in recent attacks against WEP and WPA by Sepehrdad, Vaudenay and Vuagnoux in EUROCRYPT 2011. After our current work, there remains no bias in the literature of WEP and WPA attacks without a proof. In the second part of the paper, we present theoretical proofs of some significant initial-round empirical biases observed by Sepehrdad, Vaudenay and Vuagnoux in SAC 2010. In the third part, we present the derivation of the complete probability distribution of the first byte of RC4 keystream, a problem left open for a decade since the observation by Mironov in CRYPTO 2002. Further, the existence of positive biases towards zero for all the initial bytes 3 to 255 is proved and exploited towards a generalized broadcast attack on RC4. We also investigate for long-term non-randomness in the keystream, and prove a new long-term bias of RC4.

Currently, many individuals and organizations outsource their data to remote cloud service providers (CSPs) seeking to reduce the maintenance cost and the burden of large local data storage. The CSP offers paid storage space on its infrastructure to store customers' data. Replicating data on multiple servers across multiple data centers achieves a higher level of scalability, availability, and durability. The more copies the CSP is asked to store, the more fees the customers are charged. Therefore, customers need to be strongly convinced that the CSP is storing all data copies that are agreed upon in the service contract, and the data-update requests issued by the customers have been correctly executed on all remotely stored copies. In this paper we propose two dynamic multi-copy provable data possession schemes that achieve two main goals: i) they prevent the CSP from cheating and using less storage by maintaining fewer copies, and ii) they support dynamic behavior of data copies over cloud servers via operations such as block modification, insertion, deletion, and append. We prove the security of the proposed schemes against colluding servers. Through theoretical analysis and experimental results, we demonstrate the performance of these schemes. Additionally, we discuss how to identify corrupted copies by slightly modifying the proposed schemes.

Due to the popularity of online social networks (OSNs), various online surveys have been done over OSNs to help researchers extract information of human behaviors on various aspects, ranging from online purchasing to disease epidemic patterns. Since online surveys usually attempt to extract the statistical features over a large population, the more participants respond, the more accurate the results will be, and hence the greater the social utility of such survey will be. Despite the growing importance of online surveys in modern social life, people are generally reluctant to respond to an online survey due to the possible privacy leakage especially when the questionnaire in the survey is related to sensitive personal information such as the health related issues, or even if they choose to respond to the survey, people might deliberately twist their responses to protect their privacy. On the other hand, low response rate of online surveys will lead to biased or even unqualified results. How to find an effective way to increase the response rate while preserving responders' privacy to some extent is a challenging problem. In this paper, we design two privacy-preserving online survey protocols which enable the inquirer to extract two most important statistical data: the intersection and the union information of responders' choices. The intersection information implies the common choice selected by all the responders while the union information corresponds to the preference of each choice in the survey. We formally prove that the proposed schemes are secure. We have also carried out extensive study and shown that the proposed schemes are more efficient than the related works. Moreover, we also discuss how to make the two basic schemes accommodate dynamic group formation and extend our schemes without central key authority.

Friendships or social contacts represent an important attribute characterizing one's social position and significantly impact one's daily life. Over online social networks (OSNs), users may opt to hide their social circle, membership or connections to certain individuals or groups for privacy concern. On the other hand, this prohibits a major benefit of OSNs -- building social connections. In order to enable OSN users to search for contacts they interested and leverage friends-of-friends relationship to grow their social network, we study the following privacy-preserving profiles searching (PPPS) problem: user $P_1$ wants to seek for contacts possessing a certain set of attributes from the contacts of $P_2$, while the contacts of $P_2$ remain hidden from $P_1$ and the criteria of $P_1$ is unknown to $P_2$ unless $P_2$ indeed having such contacts. While the PPPS problem can be solved with the help of oblivious transfer with hidden access control (OT-HAC) which in turn can be built by anonymous identity-based encryption (IBE) with blind key extraction (BKE) protocol, the designs of existing systems are often complicated and the efficiency are not satisfactory. A simple and efficient approach is especially important for $P_2$ since he is playing a helping role in the protocol. In this paper, we propose efficient BKE protocols, for an anonymous IBE and an anonymous hierarchical IBE attributed to Ducas in CT-RSA '10. Our protocol for IBE is conceptually simpler and more efficient than an existing proposal by Camenisch $\etal$ in PKC '09. Our protocol for HIBE is the first of its kind in the literature to the best of our knowledge. When compared with the OT-HAC system proposed by Camenisch $\etal$ in PKC '11, our protocol is again conceptually simpler, supports predicates defined by vectors from a large-domain instead of bit-vectors, and allows retrieval of multiple items in one invocation. Finally, we demonstrate their practicality by our performance analysis on prototypes implementation.

Generalised Mersenne Numbers (GMNs) were defined by Solinas in 1999 and feature in the NIST Digital Signature Standard (FIPS 186-2) for use in elliptic curve cryptography. Their form is such that modular reduction is extremely efficient, thus making them an attractive choice for modular multiplication implementation. However, the issue of residue multiplication efficiency seems to have been overlooked. Asymptotically, using a cyclic rather than a linear convolution, residue multiplication modulo a Mersenne number is twice as fast as integer multiplication; this property does not hold for prime GMNs, unless they are of Mersenne's form. In this work we exploit an alternative generalisation of Mersenne numbers for which an analogue of the above property --- and hence the same efficiency ratio --- holds, even at bitlengths for which schoolbook multiplication is optimal, while also maintaining very efficient reduction. Moreover, our proposed primes are abundant at any bitlength, whereas GMNs are extremely rare. Our multiplication and reduction algorithms can also be easily parallelised, making our arithmetic particularly suitable for hardware implementation. Furthermore, the field representation we propose also naturally protects against side-channel attacks, including timing attacks, simple power analysis and differential power analysis, which is essential in many cryptographic scenarios, in constrast to GMNs.

The existence of succinct non-interactive arguments for NP (i.e., non-interactive computationally-sound proofs where the verifier's work is essentially independent of the complexity of the NP nondeterministic verifier) has been an intriguing question for the past two decades. Other than CS proofs in the random oracle model [Micali, FOCS '94], the only existing candidate construction is based on an elaborate assumption that is tailored to a specific protocol [Di Crescenzo and Lipmaa, CiE '08]. We formulate a general and relatively natural notion of an extractable collision-resistant hash function (ECRH) and show that, if ECRHs exist, then a modified version of Di Crescenzo and Lipmaa's protocol is a succinct non-interactive argument for NP. Furthermore, the modified protocol is actually a succinct non-interactive adaptive argument of knowledge (SNARK). We then propose several candidate constructions for ECRHs and relaxations thereof. We demonstrate the applicability of SNARKs to various forms of delegation of computation, to succinct non-interactive zero knowledge arguments, and to succinct two-party secure computation. Finally, we show that SNARKs essentially imply the existence of ECRHs, thus demonstrating the necessity of the assumption.

We examine a natural, but non-tight, reductionist security proof for deterministic message authentication code (MAC) schemes in the multi-user setting. If security parameters for the MAC scheme are selected without accounting for the non-tightness in the reduction, then the MAC scheme is shown to provide a level of security that is less than desirable in the multi-user setting. We find similar deficiencies in the security assurances provided by non-tight proofs when we analyze some protocols in the literature including ones for network authentication and aggregate MACs. Our observations call into question the practical value of non-tight reductionist security proofs. We also exhibit attacks on authenticated encryption and disk encryption schemes in the multi-user setting.

At Eurocrypt 2010 van Dijk {\sl et al.} described a fully homomorphic encryption scheme over the integers. The main appeal of this scheme (compared to Gentry's) is its conceptual simplicity. This simplicity comes at the expense of a public key size in ${\cal \tilde O}(\lambda^{10})$ which is too large for any practical system. In this paper we reduce the public key size to ${\cal \tilde O}(\lambda^{7})$ by encrypting with a quadratic form in the public key elements, instead of a linear form. We prove that the scheme remains semantically secure, based on a stronger variant of the approximate-GCD problem, already considered by van Dijk {\sl et al}. We also describe the first implementation of the resulting fully homomorphic scheme. Borrowing some optimizations from the recent Gentry-Halevi implementation of Gentry's scheme, we obtain roughly the same level of efficiency. This shows that fully homomorphic encryption can be implemented using simple arithmetic operations.

We describe a compression technique that reduces the public key size of van Dijk, Gentry, Halevi and Vaikuntanathan's (DGHV) fully homomorphic scheme over the integers from \lambda^7 to \lambda^5. Our variant remains semantically secure, but in the random oracle model. We obtain an implementation of the full scheme with a 10.1 MB public key instead of 802 MB using similar parameters as in \cite{cmnt2011}. Additionally we show how to extend the quadratic encryption technique of \cite{cmnt2011} to higher degrees, to obtain a shorter public-key for the basic scheme. This paper also describes a new modulus switching technique for the DGHV scheme that enables to use the new FHE framework without bootstrapping from Brakerski, Gentry and Vaikuntanathan with the DGHV scheme. Finally we describe an improved attack against the Approximate GCD Problem on which the DGHV scheme is based, with complexity 2^\rho instead of 2^{3\rho/2}.

An authenticated dictionary of size $N$ is said to be optimal when an update operation or proof computation requires at most $O(\log N)$ accesses to the data-structure, and the size of a proof is $O(1)$ with respect to $N$. In this note we show that an optimal authenticated dictionary (OAD) can be built using transitive signatures for directed graphs (DTS). As the existence of DTS and OAD are both still open, our result can be interpreted as following: if optimal authenticated dictionaries do not exist then transitive signatures for directed graphs do not exist either.

A transitive signature scheme allows to sign a graph in such a way that, given the signature of edges (a,b) and (b,c), it is possible to compute the signature for the edge (or path) (a,c) without the Signer's secret. Constructions for undirected graphs are known but the case of directed graphs remains open. A first solution for the easier case of directed trees (DTTS) was given by Yi at CT-RSA 2007. In Yi's construction, the signature for an edge is O(n (\log (n \log n))) bits long in the worst case. A year later, Neven designed a simpler scheme where the signature size is reduced to O(n \log n) bits. Although Neven's construction is more efficient, handling O(n \log n) still remains impractical for large n. In this work, we design a new $DTTS$ scheme where for any value \lambda \geq 1 and security parameter \kappa, we have: * A signature for an edge is only $O(\kappa \lambda)$ bits long. * Signing or verifying the signature for an edge requires O(\lambda) cryptographic operations. * Computing a signature for an edge requires \lambda n^{1/\lambda} cryptographic operations. To the best of our knowledge this is the first construction with such trade off. In particular, we achieve O(\kappa\log(n)) bits signatures, as well as O(\log(n)) time to generate edge signatures, verify or even compute edge signatures. Our construction relies on hashing with common-prefix proofs, a new variant of collision resistance hashing. A family \HashFam is collision resistant hashing with common-prefix proofs if for any H \in \HashFam, given two strings X and Y equal up to position i, a Combiner can convince a Verifier that X[1..i] is a prefix of Y by sending only H(X),H(Y), and a small proof. We believe that this new primitive will lead to other interesting applications.

We analyze the multivariate generalization of Howgrave-Graham's algorithm for the approximate common divisor problem. In the $m$-variable case with modulus $N$ and approximate common divisor of size $N^\beta$, this improves the size of the error tolerated from $N^{\beta^2}$ to $N^{\beta^{(m+1)/m}}$, under a commonly used heuristic assumption. This gives a more detailed analysis of the hardness assumption underlying the recent fully homomorphic cryptosystem of van Dijk, Gentry, Halevi, and Vaikuntanathan. While these results do not challenge the suggested parameters, a $2^{\sqrt{n}}$ approximation algorithm for lattice basis reduction in $n$ dimensions could be used to break these parameters. We have implemented our algorithm, and it performs better in practice than the theoretical analysis suggests. Our results fit into a broader context of analogies between cryptanalysis and coding theory. The multivariate approximate common divisor problem is the number-theoretic analogue of noisy multivariate polynomial interpolation, and we develop a corresponding lattice-based algorithm for the latter problem. In particular, it specializes to a lattice-based list decoding algorithm for Parvaresh-Vardy and Guruswami-Rudra codes, which are multivariate extensions of Reed-Solomon codes. This yields a new proof of the list decoding radii for these codes.

At EUROCRYPT '10, van Dijk, Gentry, Halevi and Vaikuntanathan presented simple fully-homomorphic encryption (FHE) schemes based on the hardness of approximate integer common divisors problems, which were introduced in 2001 by Howgrave-Graham. There are two versions for these problems: the partial version (PACD) and the general version (GACD). The seemingly easier problem PACD was recently used by Coron, Mandal, Naccache and Tibouchi at CRYPTO '11 to build a more efficient variant of the FHE scheme by van Dijk {\em et al.}. We present a new PACD algorithm whose running time is essentially the ``square root'' of that of exhaustive search, which was the best attack in practice. This allows us to experimentally break the FHE challenges proposed by Coron {\em et al.} Our PACD algorithm directly gives rise to a new GACD algorithm, which is exponentially faster than exhaustive search: namely, the running time is essentially the $3/4$-th root of that of exhaustive search. Interestingly, our main technique can also be applied to other settings, such as noisy factoring and attacking low-exponent RSA.

In recent work, Ishai, Prabhakaran and Sahai (CRYPTO 2008) presented a new compiler (hereafter the IPS compiler) for constructing protocols that are secure in the presence of malicious adversaries without an honest majority from protocols that are only secure in the presence of semi-honest adversaries. The IPS compiler has many important properties: it provides a radically different way of obtaining security in the presence of malicious adversaries with no honest majority, it is black-box in the underlying semi-honest protocol, and it has excellent asymptotic efficiency. In this paper, we study the IPS compiler from a number different angles. We present an efficiency improvement of the ``watchlist setup phase'' of the compiler that also facilitates a simpler and tighter analysis of the cheating probability. In addition, we present a conceptually simpler variant that uses protocols that are secure in the presence of covert adversaries as its basic building block. This variant can be used to achieve more efficient asymptotic security, as we show regarding black-box constructions of malicious oblivious transfer from semi-honest oblivious transfer. In addition, it deepens our understanding of the model of security in the presence of covert adversaries. Finally, we analyze the IPS compiler from a \emph{concrete efficiency} perspective and demonstrate that in some cases it can be competitive with the best efficient protocols currently known.

In this paper, we design an efficient protocol for \emph{oblivious DFA evaluation} between an input holder (client) and a DFA holder (server). The protocol runs in a single round, and only requires a small amount of computation by each party. The most efficient version of our protocol only requires $O(k)$ asymmetric operations by either party, where $k$ is the security parameter. Moreover, the client's total computation is only linear in his own input and independent of the size of the DFA. We prove the protocol fully-secure against a \emph{malicious client} and \emph{private} against a malicious server, using the standard \emph{simulation-based} security definitions for secure two-party computation. We show how to transform our construction in order to solve multiple variants of the \emph{secure pattern matching} problem without any computational overhead. The more challenging variant is when parties want to compute the number of occurrences of a pattern in a text (but nothing else). We observe that, for this variant, we need a protocol for counting the number of accepting states visited during the evaluation of a DFA on an input. We then introduce a novel modification to our original protocol in order to solve the counting variant, without any loss in efficiency or security. Finally, we fully implement our protocol and run a series of experiments on a client/server network environment. Our experimental results demonstrate the efficiency of our proposed protocol and, confirm the particularly low computation overhead of the client.

In collusion-free protocols, subliminal communication is impossible and parties are thus unable to communicate ``any information beyond what the protocol allows''. Collusion-free protocols are interesting for several reasons, but have specifically attracted attention because they can be used to reduce trust in game-theoretic mechanisms. Collusion-free protocols are impossible to achieve (in general) when all parties are connected by point-to-point channels, but exist under certain physical assumptions (Lepinksi et al., STOC~2005) or in specific network topologies (Alwen et al., Crypto~2008). We provide a ``clean-slate'' definition of the stronger notion of collusion preservation. Our goals in revisiting the definition are: -- To give a definition with respect to arbitrary communication resources (that includes as special cases the communication models from prior work). We can then, in particular, better understand what types of resources enable collusion-preserving protocols. -- To construct protocols that allow no additional subliminal communication in the case when parties can communicate (a bounded amount of information) via other means. (This property is not implied by collusion-freeness.) -- To provide a definition supporting \emph{composition}, so that protocols can be designed in a modular fashion using sub-protocols run among subsets of the parties. In addition to proposing the definition, we explore implications of our model and show a general feasibility result for collusion-preserving computation of arbitrary functionalities.

In response to needs of disk encryption standardization bodies, we provide the first tweakable ciphers that are proven to securely encipher their own keys. We provide both a narrowblock design StE and a wideblock design EtE. Our proofs assume only standard PRP-CCA security of the underlying tweakable ciphers.

Square is a multivariate quadratic encryption scheme proposed in 2009. It is a specialization of Hidden Field Equations by using only odd characteristic fields and also X^2 as its central map. In addition, it uses embedding to reduce the number of variables in the public key. However, the system was broken at Asiacrypt 2009 using a differential attack. At PQCrypto 2010 Clough and Ding proposed two new variants named Double-Layer Square and Square+. We show how to break Double-Layer Square using a refined MinRank attack in 2^45 field operations. A similar fate awaits Square+ as it will be broken in 2^32 field operations using a mixed MinRank attack over both the extension and the ground field. Both attacks recover the private key, given access to the public key. We also outline how possible variants such as Square- or multi-Square can be attacked.

Isogenies are the morphisms between elliptic curves, and are accordingly a topic of interest in the subject. As such, they have been well-studied, and have been used in several cryptographic applications. Velu’s formulas show how to explicitly evaluate an isogeny, given a specification of the kernel as a list of points. However, Velu’s formulas only work for elliptic curves specified by a Weierstrass equation. This paper presents formulas similar to Velu’s that can be used to evaluate isogenies on Edwards curves and Huff curves, which are normal forms of elliptic curves that provide an alternative to the traditional Weierstrass form. Our formulas are not simply compositions of Velu’s formulas with mappings to and from Weierstrass form. Our alternate derivation yields efficient formulas for isogenies with lower algebraic complexity than such compositions. In fact, these formulas have lower algebraic complexity than Velu’s formulas on Weierstrass curves.

Most of the multi-party computation frameworks can be viewed as oblivious databases where data is stored and processed in a secret-shared form. However, data manipulation in such databases can be slow and cumbersome without dedicated protocols for certain database operations. In this paper, we provide efficient protocols for oblivious selection, filtering and shuffle---essential tools in privacy-preserving data analysis. As the first contribution, we present a $1$-out-of-$n$ oblivious transfer protocol with $O(\log\log n)$ rounds, which achieves optimal communication and time complexity and works over any ring $Z_N$. Secondly, we show that the round complexity $\tau_{bd}$ of a bit decomposition protocol can be almost matched with oblivious transfer, and that there exists an oblivious transfer protocol with $O(\tau_{bd}\log^*n)$ rounds. Finally, we also show how to construct round-efficient shuffle protocols with optimal asymptotic computation complexity and provide several optimizations.

In this paper, we propose a method for snooping AES encryption key on Virtual Machine Monitor (VMM), and we present countermeasures against this attack. Recently, virtualization technology has rapidly emerged as a key technology for cloud computing. In general, the virtualization technology composes two software parts: one is virtual machine (VM) management software called Virtual Machine Monitor (VMM), and the other is its associated software. The virtualization technology at present does not provide methods for certifying dependability of the VMMs. In this situation, the following case is possible: when malicious service providers serve tampered VMMs and their users run their VMs on these VMMs, the users will suffer unintended information leakage. As one leakage case, in this paper, we propose a method for snooping AES encryption key on the VMM. In addition, we present countermeasures against this key snooping.

In this paper, we analyze the security of the KMOV public key cryptosystem. KMOV is based on elliptic curves over the ring $\mathbb{Z}_n$ where $n=pq$ is the product of two large unknown primes of equal bit-size. We consider KMOV with a public key $(n,e)$ where the exponent $e$ satisfies an equation $ex-(p+1)(q+1)y=z$, with unknown parameters $x$, $y$, $z$. Using Diophantine approximations and lattice reduction techniques, we show that KMOV is insecure when $x$, $y$, $z$ are suitably small.

EPC class 1 Generation 2(or in short term EPC-C1 G2) is one of the most important standards for RFID passive tags. However, the original protocol known to be insecure. To improve the security of this standard, several protocols have been proposed compliant to this standard. In this paper we analyze the improved Yeh \textit{et al. }'s protocol by Yoon which is conforming to EPC-C1 G2 standard and is one of the most recent proposed protocol in this field. We present several efficient attacks against this protocol. Our first attack is a passive attack that can retrieve all secret parameters of the tag on the cost of eavesdropping only one session of protocol between the tag and a legitimate reader (connected to the back-end database) and $O(2^{16})$ evaluations of $PRNG$-function in off-line . Although the extracted information are enough to mount other relevant attacks (e. g. such as traceability, tag impersonation, reader impersonation, and desynchronization attacks) and would be enough to rule out any security claim for this protocol, to highlight other weaknesses of the protocol we present another tag impersonation attack with the complexity of two runs of protocol and the success probability of ``1''. In addition, we show a straight forward way to trace the tag as long as it has not updated its secret values.

Higher-order side channel attacks is a class of powerful techniques against cryptographic implementations. Their complexity grows exponentially with the order, but for small orders (e.g. 2 and 3) recent studies have demonstrated that they pose a serious threat in practice. In this context, it is today of great importance to design software countermeasures enabling to counteract higher-order side channel attacks for any arbitrary chosen order. At CHES 2010, Rivain and Prouff have introduced such a countermeasure for the AES. It works for any arbitrary chosen order and benefits from a formal resistance proof. Until now, it was the single one with such assets. By generalizing at any order a countermeasure introduced at ACNS 2010 by Genelle et al. , we propose in this paper an alternative to Rivain and Prouff’s solution. The new scheme can also be proven secure at any order and has the advantage of being at least 2 times more efficient than the existing solutions for orders 2 and 3, while maintaining the RAM consumption lower than 200 bytes.

In this paper, we analyze the security of AZUMI protocol which is compliant with the EPC-Class-1 Generation-2 standard and recently has been proposed by Peris \textit{et al.} This protocol is an improvement to a protocol proposed by Chen and Deng which has been cryptanalysed by Peris \textit{et al.} and Kapoor and Piramuthu. However, our security analysis clearly shows that the designers were not successful in their attempt to improve the Chen and Deng protocol. More precisely, we present an efficient attack to disclose the tag and the reader secret parameters. In addition, we present a simple tag impersonation attack against this protocol. The success probability of all attacks are almost ``1'' and the cost of given attacks are at most eavesdropping two sessions of protocol. However, the given secrets disclosure attack also requires $O(2^{16}) $ off-line evaluation of a $PRNG$ function.

PRINTcipher is a recent lightweight block cipher designed by Knudsen et al. Some noteworthy characteristics are a burnt-in key, a key-dependent permutation layer and identical round keys. Independent work on PRINTcipher has identified weak key classes that allow for a key recovery --- the obvious countermeasure is to avoid these weak keys at the cost of a small loss of key entropy. This paper identifies several larger classes of weak keys. We show how to distinguish classes of keys and give a $28$-round linear attack applicable to half the keys. We show that there are several similar attacks, each focusing on a specific class of keys. We also observe how some specific properties of PRINTcipher allow us to collect several samples from each plaintext--ciphertext pair. We use this property to construct an attack on $29$-round PRINTcipher applicable to a fraction $2^{-5}$ of the keys.

ECHO-256 is a second-round candidate of the SHA-3 competition. It is an AES-based hash function that has attracted a lot of interest and analysis. Up to now, the best known attacks were a distinguisher on the full internal permutation and a collision on four rounds of its compression function. The latter was the best known analysis on the compression function as well as the one on the largest number of rounds so far. In this paper, we extend the compression function results to get a distinguisher on 7 out of 8 rounds using rebound techniques. We also present the first 5-round collision attack on the ECHO-256 hash function.

Attacks on cryptographic protocols are usually modeled by allowing an adversary to ask queries to an oracle. Security is then defined by requiring that as long as the queries satisfy some constraint, there is some problem the adversary cannot solve, such as compute a certain piece of information. Even if the protocol is quantum, the queries are typically classical, such as a choice of subset of players to corrupt. In this paper, we introduce a fundamentally new model of quantum attacks on protocols, where the adversary is allowed to ask several classical queries in quantum superposition. This is a strictly stronger attack than the standard one, and we consider the security of several primitives in this model. We show that a secret-sharing scheme that is secure with threshold $t$ in the standard model is secure against superposition attacks if and only if the threshold is lowered to $t/2$. This holds for all classical as well as a large class of quantum secret sharing schemes. We then consider zero-knowledge and first show that known protocols are not, in general, secure in our model by designing a superposition attack on the well-known zero-knowledge protocol for graph isomorphism. We then use our secret-sharing result to design zero-knowledge proofs for all of NP in the common reference string model. While our protocol is classical, it is sound against a cheating unbounded quantum prover and computational zero-knowledge even if the verifier is allowed a superposition attack. Finally, we consider multiparty computation and give a characterization of a class of protocols that can be shown secure, though not necessarily with efficient simulation. We show that this class contains non-trivial protocols that cannot be shown secure by running a classical simulator in superposition.

We analyze the internal permutations of Keccak, one of the NIST SHA-3 competition finalists, in regard to differential properties. By carefully studying the elements composing those permutations, we are able to derive most of the best known differential paths for up to 5 rounds. We use these differential paths in a rebound attack setting and adapt this powerful freedom degrees utilization in order to derive distinguishers for up to 8 rounds of the internal permutations of the submitted version of Keccak. The complexity of the 8 round distinguisher is $2^{491.47}$. Our results have been implemented and verified experimentally on a small version of Keccak. This is currently the best known differential attack against the internal permutations of Keccak.

Certificateless public key cryptography is an attractive paradigm for public key cryptography since it does not require certificates in traditional public key cryptography and, at the same time, solves the inherent key escrow problem in identity-based cryptography. Currently, certificateless short signature is receiving significant attention as it is particularly useful in low-bandwidth communication environments. However, most of the certificateless short signature schemes only support low-level security. Recently, Choi et al. presented a certificateless short signature scheme and claimed that it is provably secure against the super adversaries. Nevertheless, in this paper, we show that their scheme is insecure even against a strong Type I adversary. We also propose a new certificateless short signature scheme which is more efficient and more secure than Choi et al.'s scheme.

Recently, Radio Frequency Identification (RFID) technique has been widely deployed in many applications, such as medical drugs management in hospitals and missing children searching in amusement parks. The applications basically can be classified into two types: non-public key cryptosystem (PKC)-based and PKC-based. However, many of them have been found to be flawed in the aspect of privacy problem. Therefore, many researchers tried to resolve this problem. They mainly investigated on how low-cost RFID tags can be used in large-scale systems. However, after analyses, we found those studies have some problems, such as suffering physical attack or de-synch attack. Hence, in this paper, we try to design an efficient RFID scheme based on Elliptic Curve Cryptography (ECC) to avoid these problems. After analyses, we conclude that our scheme not only can resist various kinds of attacks but also outperforms the other ECC based RFID schemes in security requirements, with needing only little extra elliptic curve point multiplications.

IDEA is a 64-bit block cipher with 128-bit keys which is widely used due to its inclusion in several cryptographic packages such as PGP. After its introduction by Lai and Massey in 1991, it was subjected to an extensive cryptanalytic effort, but so far the largest variant on which there are any published attacks contains only 6 of its 8.5-rounds. The first 6-round attack, described in the conference version of this paper in 2007, was extremely marginal: It required essentially the entire codebook, and saved only a factor of 2 compared to the time complexity of exhaustive search. In 2009, Sun and Lai reduced the data complexity of the 6-round attack from 2^{64} to 2^{49} chosen plaintexts and simultaneously reduced the time complexity from 2^{127} to 2^{112.1} encryptions. In this revised version of our paper, we combine a highly optimized meet-in-the-middle attack with a keyless version of the Biryukov-Demirci relation to obtain new key recovery attacks on reduced-round IDEA, which dramatically reduce their data complexities and increase the number of rounds to which they are applicable. In the case of 6-round IDEA, we need only two known plaintexts (the minimal number of 64-bit messages required to determine a 128-bit key) to perform full key recovery in 2^{123.4} time. By increasing the number of known plaintexts to sixteen, we can reduce the time complexity to 2^{111.9}, which is slightly faster than the Sun and Lai data-intensive attack. By increasing the number of plaintexts to about one thousand, we can now attack 6.5 rounds of IDEA, which could not be attacked by any previously published technique. By pushing our techniques to extremes, we can attack 7.5 rounds using 2^{63} plaintexts and 2^{114} time, and by using an optimized version of a distributive attack, we can reduce the time complexity of exhaustive search on the full 8.5-round IDEA to 2^{126.8} encryptions using only 16 plaintexts.

We propose a new parallelization technique for Lanczos type algorithms for solving large sparse linear systems over finite fields on mesh cluster architecture. The algorithm computation time scales as $P^{-1}$ on $P processors, and the communcation times scales as $P^{-1/2}$ for reasonable choice of $P$.

In this paper we partially determine the access structures of algebraic geometric secret sharing schemes from one point algebraic geometric codes associated with a hyperelliptic curve of any genus. Our result includes the access structures of elliptic secret sharing schemes as a special case.