Cache attacks on implementations of cryptographic algorithms have turned out to be very powerful. Progress in processor design, e.g., like hyperthreading, requires to adapt models for tampering or side-channel attacks to cover cache attacks as well. Hence, in this paper we present a rather general model for cache attacks. Our model is stronger than recently used ones. We introduce the notions of information leakage and so called resistance to analyze the security of several implementations of AES. Furthermore, we analyze how to use random permutations to protect against cache attacks. By providing a successful attack on an AES implementation protected by random permutations we show that random permutations used in a straightforward manner are not enough to protect against cache attacks. Hence, to improve upon the security provided by random permutations, we describe the property a permutation must have in order to prevent the leakage of some key bits through cache attacks. Using a permutation having this property forces an adversary to consider several rounds of the cipher. This increases the complexity of any cache attack considerably. We also describe how to implement our countermeasure efficiently. The method to do so is of independent interest, since it alone can also be used to protect against cache attacks. Moreover, combining both countermeasures allows for a trade-off between security and efficiency.

In this short paper we propose a pseudorandom number generator over EC based on Pollard-like method. In contrast to the well known Elliptic Curve Random Number Generator (see e.g. ANSI and NIST draft standards) the generator is based on a random walk over the group of EC-points like in the original Pollard’s rho algorithm and only resembles a little bit the linear congruential generator over elliptic curve. Compared to other approaches, the method allows to decrease the cost of generating pseudorandom numbers. This generator could be used in resource constrained devices like smart cards which have already been equipped with EC-based tools for other cryptographic purposes.

A system of algebraic equations over a finite field is called sparse if each equation depends on a small number of variables. Finding efficiently solutions to the system is an underlying hard problem in the cryptanalysis of modern ciphers. In this paper deterministic Agreeing-Gluing algorithm introduced earlier by Raddum and Semaev for solving such equations is studied. Its expected running time on uniformly random instances of the problem is rigorously estimated. This estimate is at present the best theoretical bound on the complexity of solving average instances of the above problem. In particular, it significantly overcomes our previous results. In characteristic 2 we observe an exciting difference with the worst case complexity provided by SAT solving algorithms.

We propose a new general primitive called lossy trapdoor functions (lossy TDFs), and realize it under a variety of different number theoretic assumptions, including hardness of the decisional Diffie-Hellman (DDH) problem and the worst-case hardness of standard lattice problems. Using lossy TDFs, we develop a new approach for constructing many important cryptographic primitives, including standard trapdoor functions, CCA-secure cryptosystems, collision-resistant hash functions, and more. All of our constructions are simple, efficient, and black-box. Taken all together, these results resolve some long-standing open problems in cryptography. They give the first known (injective) trapdoor functions based on problems not directly related to integer factorization, and provide the first known CCA-secure cryptosystem based solely on worst-case lattice assumptions.

Since the seminal works of Merkle and Damgard on the iteration of compression functions, hash functions were built from compression functions using the Merkle-Damgard construction. Recently, several flaws in this construction were identified, allowing for pre-image attacks and second pre-image attacks on such hash functions even when the underlying compression functions are secure. In this paper we propose the HAsh Iterative FrAmework (HAIFA). Our framework can fix many of the flaws while supporting several additional properties such as defining families of hash functions and supporting variable hash size. HAIFA allows for an online computation of the hash function in one pass with a fixed amount of memory independently of the size of the message. Besides our proposal, the recent attacks initiated research on the way compression functions are to be iterated. We show that most recent proposals such as randomized hashing, the enveloped Merkle-Damgard, and the RMC and ROX modes can be all be instantiated as part of the HAsh Iterative FrAmework (HAIFA).

We apply new cryptanalytical techniques to perform the generic multi-block multicollision, second preimage and herding attacks on the Damgård-Merkle hash functions with linear-XOR/additive checksums. The computational work required to perform these attacks on the Damgård-Merkle hash functions with linear-XOR/additive checksum of message blocks (GOST), intermediate states (\textbf{3C}, MAELSTROM-0, F-Hash) or both is only a little more than what is required on the Damgård-Merkle hash functions. Our generic attacks on GOST answers the open question of Hoch and Shamir at FSE 2006 on the security of the iterated hash functions with the linear mixing of message blocks.

Let C be a code of length n over an alphabet of size q. A word d is a descendant of a pair of codewords x,y if d_i lies in \{x_i ,y_i \} for 1 <= i <= n. A code C is an identifiable parent property (IPP) code if the following property holds. Whenever we are given C and a descendant d of a pair of codewords in C, it is possible to determine at least one of these codewords. The paper introduces the notion of a prolific IPP code. An IPP code is prolific if all q^n words are descendants. It is shown that linear prolific IPP codes fall into three infinite (`trivial') families, together with a single sporadic example which is ternary of length 4. There are no known examples of prolific IPP codes which are not equivalent to a linear example: the paper shows that for most parameters there are no prolific IPP codes, leaving a relatively small number of parameters unsolved. In the process the paper obtains upper bounds on the size of a (not necessarily prolific) IPP code which are better than previously known bounds.

Some families of binary sequences are constructed from elliptic curves. Such sequences are shown to be of strong pseudorandom properties with `small' well-distribution measure and `small' correlation measure of `small' order, both of which were introduced by Mauduit and S$\acute{a}$rközy to analyze the pseudo-randomness of binary sequences.

Recently, proxy re-encryption scheme received much attention. In this paper, we propose a proxy re-encryption used for divert ciphertext from one group to another. The scheme is bidirectional and any member can independently decrypt the ciphertexts encrypted to its group. We discuss the security of the proposed scheme and show that our scheme withstands chosen ciphertext attack in standard model.

We show how the Fiat-Shamir transform can be used to convert three-move identification protocols into two-tier signature schemes (a primitive we define) with a proof of security that makes a standard assumption on the hash function rather than modeling it as a random oracle. The result requires security of the starting protocol against concurrent attacks. We can show that numerous protocols have the required properties and so obtain numerous efficient two-tier schemes. Our first application is an efficient transform of any unforgeable signature scheme into a strongly unforgeable one, which uses as a tool any two-tier scheme. (This extends work of Boneh, Shen and Waters whose transform only applies to a limited class of schemes.) The second application is new one-time signature schemes that, compared to one-way function based ones of the same computational cost, have smaller key and signature sizes.

A simple method for constructing collisions for Shpilrain’s polynomial-based hash function from ICISC 2006 is presented. The attack relies on elementary linear algebra and can be considered as practical: For the parameters suggested, we give a specific collision, computed by means of a computer algebra system.

In the dedicated-key setting, one starts with a compression function f:{0,1}^k x {0,1}^{n+d} -> {0,1}^n and builds a family of hash functions H^f:K x M -> {0,1}^n indexed by a key space K. This is different from the more traditional design approach used to build hash functions such as MD5 or SHA-1, in which compression functions and hash functions do not have dedicated key inputs. We explore the benefits and drawbacks of building hash functions in the dedicated-key setting (as compared to the more traditional approach), highlighting several unique features of the former. Should one choose to build hash functions in the dedicated-key setting, we suggest utilizing multi-property-preserving (MPP) domain extension transforms. We analyze seven existing dedicated-key transforms with regard to the MPP goal and propose two simple new MPP transforms.

This paper describes in detail a voting scheme which allows voters to be sure that whatever they see in the booth will be included correctly in the outcome. It presents a rigorous and understandable model of requirements for election systems, states formally the properties of the system, and proves them. As a step towards understanding the full 2D voting system, it also presents a simpler 1D system.

We present a detailed comparison of the Prêt-à-Voter and Punchscan protocols for booth voting. We also describe a simpler variation that keeps the ballot layout of Prêt-à-Voter but borrows the cryptography from Punchscan, which is based on any commitment scheme. By using unconditionally hiding commitments we obtain a conceptually very simple voting protocol with unconditional privacy.

This paper presents a new approach to precompute all odd points $[3]P, [5]P,\ldots, [2k-1]P$, $k \geq 2$ on an elliptic curve over $\mathbb{F}_p$. Those points are required for the efficient evaluation of a scalar multiplication, the most important operation in elliptic curve cryptography. The proposed method precomputes the points in affine coordinates and needs only one single field inversion for the computation. The new method is superior to all known methods that also use one field inversion. Compared to methods that require several field inversions for the precomputation, the proposed method is faster for a broad range of ratios of field inversions and field multiplications. The proposed method benefits especially from ratios as they occur on smart cards. %Scalar multiplications are the basic operations in elliptic curve cryptosystems. The evaluation of a scalar multiplication can be sped up by using signed representations of the scalar. In exchange for the speed up, the precomputation of a series of points is required. While a lot of research has been done in the direction of signed representations, little attention has been paid to efficient methods to precompute the required points. Such methods are important since costly field inversions are involved in the precomputation. This paper presents a new method for the precomputation that requires only one single field inversion, independent of the number of points to precompute. The points to precompute are all odd points $[3]P, [5]P,\ldots, [2k-1]P$, $k \geq 2$ on an elliptic curve over $\mathbb{F}_p$. The proposed method benefits especially from a large ratios between inversions and multiplications as they occur on smart cards.

This paper presents CRUST, a stackable file system layer designed to provide secure file sharing over remote untrusted storage systems. CRUST is intended to be layered over insecure network file systems without changing the existing systems. In our approach, data at rest is kept encrypted, and data integrity and access control are provided by cryptographic means. Our design completely avoids public-key cryptography operations and uses more efficient symmetric-key alternatives to achieve improved performance. As a generic and self-contained system, CRUST includes its own in-band key distribution mechanism and does not rely on any special capabilities of the server or the clients. We have implemented CRUST as a Linux file system and shown that it performs comparably with typical underlying file systems, while providing significantly stronger security.

Cryptography is an important tool in the design and implementation of electronic voting schemes for it provides the property of verifiability, which is not provided in the traditional voting. But in the real life, neither can most voters understand the profound theory of cryptographic e-voting nor can they perform the complicated cryptographic computation. An e-voting system is presented in this paper to leverage the use of cryptography between theory and practice. It combines the advantages of Moran-Naor's voting scheme and voting schemes based on homomorphic encryption. It makes use of cryptographic techniques, but it hides the details of cryptographic computation from voters. Voters can be convinced that the ballot is cast as intended. The tally can be verified in public. Compared with Moran-Naor's voting scheme, the new system has three advantages: the ballots can be recovered when the voting machine breaks down, the costly cut-and-choose zero-knowledge proofs for shuffling votes made by the voting machine are avoided and the partial tally result in each voting machine is kept secret.

We show, unconditionally, that if a language $L$ has a 4-round, black-box, computational zero-knowledge proof system with negligible soundness error, then $\bar L \in MA$. Assuming the polynomial hierarchy does not collapse, this means, in particular, that $NP$-complete languages do not have 4-round zero-knowledge proofs (at least with respect to black-box simulation).

Multiparty signature protocols need protection against rogue-key attacks, made possible whenever an adversary can choose its public key(s) arbitrarily. For many schemes, provable security has only been established under the knowledge of secret key (KOSK) assumption where the adversary is required to reveal the secret keys it utilizes. In practice, certifying authorities rarely require the strong proofs of knowledge of secret keys required to substantiate the KOSK assumption. Instead, proofs of possession (POPs) are required and can be as simple as just a signature over the certificate request message. We propose a general registered key model, within which we can model both the KOSK assumption and in-use POP protocols. We show that simple POP protocols yield provable security of Boldyreva's multisignature scheme [11], the LOSSW multisignature scheme [28], and a 2-user ring signature scheme due to Bender, Katz, and Morselli [10]. Our results are the first to provide formal evidence that POPs can stop rogue-key attacks.

The NTRU encryption scheme is an interesting alternative to well-established encryption schemes such as RSA, ElGamal, and ECIES. The security of NTRU relies on the hardness of computing short lattice vectors and thus is a promising candidate for being quantum computer resistant. There has been extensive research on efficient implementation of the NTRU encryption scheme. In this paper, we present a new algorithm for enhancing the performance of NTRU. The proposed method is between $11$\% and $23$\% faster on average than the best previously known method. We also present a highly efficient implementation of NTRU within the Java Cryptography Architecture.

Recently, Au et al. pointed out a seemingly neglected security concern for certificateless public key encryption (CL-PKE) scheme, where a malicious key generation center (KGC) can compromise the confidentiality of the messages by embedding extra trapdoors in the system parameter. Although some schemes are secure against such an attack, they require random oracles to prove the security. In this paper, we first show that two existing CL-PKE schemes without random oracles are not secure against malicious KGC, we then propose the first CL-PKE scheme secure against malicious KGC attack, with proof in the standard model.

Consider the permutation $S$ in RC4. Roos pointed out in 1995 that after the Key Scheduling Algorithm (KSA) of RC4, each of the initial bytes of the permutation, i.e., $S[y]$ for small values of $y$, is biased towards some linear combination of the secret key bytes. In this paper, for the first time we show that the bias can be observed in $S[S[y]]$ too. Based on this new form of permutation bias after the KSA and other related results, a complete framework is presented to show that many keystream output bytes of RC4 are significantly biased towards several linear combinations of the secret key bytes. The results do not assume any condition on the secret key. We find new biases in the initial as well as in the 256-th and 257-th keystream output bytes. For the first time biases at such later stages are discovered without any knowledge of the secret key bytes. We also identify that these biases propagate further, once the information for the index $j$ is revealed.

A signer in a Nominative Signature (NS) scheme can arbitrarily choose a nominee, then jointly generate a signature in such a way that the signature can only be verified with the nominee's consent. NS is particularly useful in user certification systems. Currently, the only secure NS scheme available requires multi-round communications between the nominator and the nominee during signature generation. This implies that an NS-based user certification system requires a certification issuer to interact with a user using a complicated multi-round protocol for certificate issuance. It remains an open problem to construct an efficient and non-interactive NS scheme. In this paper, we solve this problem by proposing the first efficient one-move (i.e. non-interactive) NS scheme. In addition, we propose an enhanced security requirement called Strong Invisibility, and prove that our scheme satisfies this strong security requirement.

Algebraic immunity of Boolean functions is a very important concept in recently introduced algebraic attacks of stream cipher. For a $n$-variable Boolean function $f$, the algebraic immunity $AI_n(f)$ takes values in $\{0,1,\ldots,\lceil\frac{n}{2}\rceil\}$. For every $k$ in this range, denote $B_{n,k}$ the set of all $n$-variable Boolean functions with algebraic immunity $k$, and we know that $B_{n,k}$ is always non-empty. According to the algebraic immunity, we can form a hierarchy of Boolean functions. Trivially, $|B_{n,0}|=2$. In general, about this integer sequence $|B_{n,k}|,\quad k=0,1,\ldots,\lceil\frac{n}{2}\rceil,$ very few results are known. In this paper, we show an explicit formula for $|B_{n,1}|$. That is, we obtain an exact formula for the number of Boolean functions with algebraic immunity one. This is the first exact formula for the terms in the above integer sequence. We also give a tight upper bound for nonlinearity of Boolean functions with algebraic immunity one.

In order to overcome proprietary algorithms with respect to the system manufacturers, a free cryptographic module, the Universal Immobilizer Crypto Engine (UICE), will be proposed. This UICE algorithm is tailored to 8-bit microprocessor architectures and is therefore very fast in software and hardware. The dedicated hardware implementation leads to a small gate count, because the registers for input and output are shared. The important non-linear function, here an 8 x 8 S-Box, may be built as a gate array or small ROM with the advantage of flexibility. Several tests – statistical and random-number tests - have been performed in order to analyze the strength properties of the algorithm. So far no weakness was found after ten rounds of encryption. Although this cryptographic module was intentionally developed for Radio-Frequency Identification (RFID) systems, it is a proper choice for all systems needing embedded cryptography such as SoC with bus encryption or firmware to be secured. RFID-Systems have become commonplace in access control and security applications, the usage and importance of cryptographic co-processors in RFID transponder devices has grown significantly. Improved vehicle security systems, also known as immobilizers, are required due to increased vehicle theft worldwide. Such devices provide high security at low cost and low power.

This paper enhances the security of Abdalla and Reyzin's forward-secure signature scheme with backward-secure detection. In the proposed scheme, we embeded the hash-chain into the forward-secure signature scheme. It achieves not only forward-secure but also backward-secure for the digital signature.

We discuss some applications of the pairing inversion problem and outline some potential approaches for solving it. Our analysis of these approaches gives further evidence that pairing inversion is a hard problem.

In this paper, we present an efficient signature scheme without random oracles using Waters private key construction. Our scheme has shorter public parameter size when compared to Kenny and Schuldt signature, the signature space of our basic scheme consists of three group elements, we further show that the signature space can be reduced to two group elements. The security of our signature scheme is proved in the standard model under adaptive identity security notion.

In a proxy re-encryption scheme, a semi-trusted proxy, with some additional information, can transform a ciphertext under Alice's public key into a new ciphertext under Bob's public key on the same message, but cannot learn any information about the messages encrypted under the public key of either Alice or Bob. In this paper, we propose two new unidirectional proxy re-encryption schemes, where a proxy can transform a ciphertext for Alice into a new ciphertext for Bob, but not vice versa. Note that, unidirectional proxy re-encryption is more powerful than bidirectional one, since a bidirectional scheme can always be implemented by an unidirectional one. Furthermore, these two schemes can be proved \emph{in the standard model}, chosen-ciphertext secure based on Decisional Bilinear Inverse Diffie-Hellman assumption and master key secure based on Extended Discrete Logarithm assumption. To our best knowledge, our proposals are the first fully secure (CCA-secure and master key secure) proxy re-encryption schemes in the standard model.

We give an elementary way to distinguish between the twists of an ordinary elliptic curve $E$ over $\Fp$ in order to identify the one with $p+1-2U$ points, when $p=U^2+\d V^2$ with $2U, 2V\in \Z$ and $E$ is constructed using the CM method for finding elliptic curves with a prescribed number of points. Our algorithms consist in most cases of reading off simple congruence conditions on $U$ and $V$ modulo $4$.

Farnel is a voting system proposed in 2001 in which each voter signs a ballot. It uses two ballot boxes to avoid the association between a voter and a vote. In this paper we first point out a flaw in the ThreeBallot system proposed by Rivest that seems to have gone unnoticed so far: it reveals statistical information about who is winning the election. Then, trying to resolve this and other flaws, we present a new, voter-verifiable version of the Farnel voting system in which voters retain copies of ballot IDs as receipts.

Some cryptographic tasks, such as contract signing and other related tasks, need to ensure complex, branching time security properties. When defining such properties one needs to deal with subtle problems regarding the scheduling of non-deterministic decisions, the delivery of messages sent on resilient (non-adversarially controlled) channels, fair executions (executions where no party, both honest and dishonest, is unreasonably precluded to perform its actions), and defining strategies of adversaries against all possible non-deterministic choices of parties and arbitrary delivery of messages via resilient channels. These problems are typically not addressed in cryptographic models and these models therefore do not suffice to formalize branching time properties, such as those required of contract signing protocols. In this paper, we develop a cryptographic model that deals with all of the above problems. One central feature of our model is a general definition of fair scheduling which not only formalizes fair scheduling of resilient channels but also fair scheduling of actions of honest and dishonest principals. Based on this model and the notion of fair scheduling, we provide a definition of a prominent branching time property of contract signing protocols, namely balance, and give the first \emph{cryptographic} proof that the Asokan-Shoup-Waidner two-party contract signing protocol is balanced.

In this paper, we present a certificateless signature (CLS) scheme that is proved to be secure in the random oracle model under the hardness assumptions of k-CAA and Inv-CDHP. Our scheme upholds all desirable properties of previous CLS schemes, and requires general cryptographic hash functions instead of the MapToPoint hash function which is inefficient and probabilistic. Furthermore, our scheme requires less computation cost and significantly more efficient than all known CLS schemes, and the size of signatures generated by our scheme is approximate 160 bits, which is the shortest certificateless signatures so far. So it can be used widely, especially in low-bandwidth communication environments.

Randomness extraction is of fundamental importance for information-theoretic cryptography. It allows to transform a raw key about which an attacker has some limited knowledge into a fully secure random key, on which the attacker has essentially no information. We show a new randomness-extraction technique which works also in case where the attacker has quantum information on the raw key. Randomness extraction is done by XORing a so-called delta-biased mask to the raw key. Up to date, only very few techniques are known to work against a quantum attacker, much in contrast to the classical (non-quantum) setting, which is much better understood and for which a vast amount of different techniques for randomness extraction are known. We show two applications of the new result. We first show how to encrypt a long message with a short key, information-theoretically secure against a quantum attacker, provided that the attacker has enough quantum uncertainty on the message. This generalizes the concept of entropically-secure encryption to the case of a quantum attacker. As a second application, we show how the new randomness-extraction technique allows to do error-correction without leaking partial information to a quantum attacker. Such a technique is useful in settings where the raw key may contain errors, since standard error-correction techniques may provide the attacker with information on, say, a secret key that was used to obtain the raw key.

We describe a new simple but more powerful form of linear cryptanalysis. It appears to break AES (and undoubtably other cryptosystems too, e.g. SKIPJACK). The break is ``nonconstructive,'' i.e. we make it plausible (e.g. prove it in certain approximate probabilistic models) that a small algorithm for quickly determining AES-256 keys from plaintext-ciphertext pairs exists -- but without constructing the algorithm. The attack's runtime is comparable to performing $64^w$ encryptions where $w$ is the (unknown) minimum Hamming weight in certain binary linear error-correcting codes (BLECCs) associated with AES-256. If $w < 43$ then our attack is faster than exhaustive key search; probably $w < 10$. (Also there should be ciphertext-only attacks if the plaintext is natural English.) Even if this break breaks due to the underlying models inadequately approximating the real world, we explain how AES still could contain ``trapdoors'' which would make cryptanalysis unexpectedly easy for anybody who knew the trapdoor. If AES's designers had inserted such a trapdoor, it could be very easy for them to convince us of that. But if none exist, then it is probably infeasibly difficult for them to convince us of \emph{that}. We then discuss how to use the theory of BLECCs to build cryptosystems provably 1. not containing trapdoors of this sort, 2. secure against our strengthened form of linear cryptanalysis, 3. secure against ``differential'' cryptanalysis, 4. secure against D.J.Bernstein's timing attack. Using this technique we prove a fundamental theorem: it is possible to thus-encrypt $n$ bits with security $2^{cn}$, via an circuit $Q_n$ containing $\le c n$ two-input logic gates and operating in $\le c \log n$ gate-delays, where the three $c$s denote (possibly different) positive constants and $Q_n$ is constructible in polynomial$(n)$ time. At the end we give tables of useful binary codes.

The Ate pairing has been suggested since it can be computed efficiently on ordinary elliptic curves with small values of the traces of Frobenius $t$. However, not all pairing-friendly elliptic curves have this property. In this paper, we generalize the Ate pairing and find a series of variations of the Ate pairing. We show that the shortest Miller loop of the variations of the Ate pairing can possibly be as small as $r^{1/\varphi(k)}$ on more pairing-friendly curves generated by the method of complex multiplications, and hence speed up the pairing computation significantly.

Secure initial pairing of electronic gadgets is a challenging problem, especially considering lack of any common security infrastructure. The main security issue is the threat of so-called Man-in-the-Middle (MiTM) attacks, whereby an attacker inserts itself into the pairing protocol by impersonating one of the legitimate parties. A number of interesting techniques have been proposed, all of which involve the user in the pairing process. However, they are inapplicable to many common scenarios where devices to-be-paired do not possess required interfaces, such as displays, speakers, cameras or microphones. In this paper, we introduce BEDA (Button-Enabled Device Association), a protocol suite for secure pairing devices with minimal user interfaces. The most common and minimal interface available on wide variety of devices is a single button. BEDA protocols can accommodate pairing scenarios where one (or even both) devices only have a single button as their "user interface". Our usability study demonstrates that BEDA protocols involve very little human burden and are quite suitable for ordinary users.

The problem of key management in access hierarchies is how to assign keys to users and classes such that each user, after receiving her secret key(s), is able to {\em independently} compute access keys for (and thus obtain access to) the resources at her class and all descendant classes in the hierarchy. If user privileges additionally are time-based (which is likely to be the case for all of the applications listed above), the key(s) a user receives should permit access to the resources only at the appropriate times. This paper present a new, provably secure, and efficient solution that can be used to add time-based capabilities to existing hierarchical schemes. It achieves the following performance bounds: (i) to be able to obtain access to an arbitrary contiguous set of time intervals, a user is required to store at most 3 keys; (ii) the keys for a user can be computed by the system in constant time; (iii) key derivation by the user within the authorized time intervals involves a small constant number of inexpensive cryptographic operations; and (iv) if the total number of time intervals in the system is $n$, then the increase of the public storage space at the server due to our solution is only by a small asymptotic factor, e.g., $O(\log^* n \log\log n)$ with a small constant.

The threat of relay attacks on authentication protocols is often well recognized, especially for contactless applications like RFID chips. It is, therefore, a bit surprising to meet an implementation that actually encourages rather than eliminates these attacks. We present our experimental observations concerning Czech e-passports. These show clearly an inherent weakness rooted in lower layers of ISO 14443. As the behavior is unavoidable, it induces a question on whether the e-passport should not have used a different communication protocol or authentication scheme.

In this paper, we define and explore the notion of a _proof of retrievability_ (POR). A POR enables an archive or back-up service (prover) to demonstrate to a user (verifier) that it has ``possession'' of a file F, that is, that the archive retains data sufficient for the user to retrieve F in its entirety. A POR may be viewed as a kind of cryptographic proof of knowledge (POK), but one specially designed to handle a _large_ file (or bitstring) F. We explore POR protocols here in which the communication costs, number of memory accesses for the prover, and storage requirements of the user (verifier) are small parameters essentially independent of the length of $F$. In addition, in a POR, unlike a POK, neither the prover nor the verifier need actually have knowledge of F. PORs give rise to a new and unusual security definition. We view PORs as an important tool for the management of semi-trusted online archives. Existing cryptographic tools help users ensure the privacy and integrity of their files once they are retrieved. It is also natural, however, for users to want to verify that archives do not delete or modify files while they are stored. The goal of a POR is to accomplish these checks {\em without users having to download the files themselves}. A POR can also provide quality-of-service guarantees, i.e., show that a file is retrievable within a certain time bound.

In this paper, we present the time-memory-data (TMD) trade-off attack on stream ciphers filtered by Maiorana-McFarland functions. This can be considered as a generalization of the time-memory-data trade-off attack of Mihaljevic and Imai on Toyocrypt. First, we substitute the filter function in Toyocrypt (which has the same size as the LFSR) with a general Maiorana-McFarland function. This allows us to apply the attack to a wider class of stream ciphers. Second, we highlight how the choice of different Maiorana-McFarland functions can affect the effectiveness of our attack. Third, we show that the attack can be modified to apply on filter functions which are smaller than the LFSR and on filter-combiner stream ciphers. This allows us to cryptanalyze other configurations commonly found in practice. Finally, filter functions with vector output are sometimes used in stream ciphers to improve the throughput. Therefore the case when the Maiorana-McFarland functions have vector output is investigated. We found that the extra speed comes at the price of additional weaknesses which make the attacks easier.

In real life, one requires signatures to be from people who fulfill certain criteria, implying that they should possess specific attributes. For example, Alice might want a signature from an employee in Bob’s company who is a member in the IT staff, a senior manager within the biometrics team or at least a junior manager in the cryptography team. In such a case an Attribute Based Group Signature scheme (ABGS) could be applied. Group signature schemes are those where each member of a group can sign on behalf of the others. An ABGS scheme is a type of group signature scheme, where the signing member has to have certain attributes. In[12], the authors introduced the first ABGS but it lacked the ability to revoke. In this paper, we introduce a new scheme that will enable us to remove a member from a group or remove some of his attributes, when needed.

Cryptographic hash algorithms are important building blocks in cryptographic protocols, providing authentication and assurance of integrity. While many different hash algorithms are available including MD5, Tiger, and HAVAL, it is difficult to compare them since they do not necessarily use the same techniques to achieve their security goals. This work informally describes a framework in four parts which allows different hash algorithms to be compared based on their strengths and weaknesses. By breaking down cryptographic hash algorithms into their preprocessing, postprocessing, compression function, and internal structure components, weaknesses in existing algorithms can be mitigated and new algorithms can take advantage of strong individual components.

We explore the idea of creating a hash function that produces an $s$-bit digest from a compression function with an $n$-bit output, where $s > n$. % where $s\le 2^{n/2}n$.This is accomplished by truncating a hash function with a digest size of $\ell n$-bits. Our work answers the question of how large $\ell$ can be while creating a digest of $sn$-bits securely. We prove that our construction is secure with respect to preimage resistance and collision resistance for $s \le 2^{n/2}n$.

New collision-finding attacks on widely used cryptographic hash functions raise questions about systems that depend on certain properties of these functions for their security. Even after new and presumably better hash functions are deployed, users may have digital signatures and digital time-stamp certificates that were computed with recently deprecated hash functions. Is there any way to use a new and currently unassailable hash function to buttress the security of an old signature or time-stamp certificate? The main purpose of this note is to remind the technical community of a simple solution to this problem that was published more than a decade ago.

We consider a key distribution scheme for securing node-to-node communication in sensor networks. While most schemes in use are based on random predistribution, we consider a system of dynamic pairwise keys based on design due to Ren, Tanmoy and Zhou. We design and analyze a variation of this scheme, in which capturing a node does not lead to security threats for the past communication. Instead of bit-flipping, we use a cryptographic one-way function. While this immediately guarantees forward-security, it is not clear whether the pseudorandom transformation of the keys does not lead to subtle security risks due to a specific distribution of reachable keys, such as existence of small attractor subspaces. (This problem does not occur for the design of Ren, Tanmoy and Zhou.) We show, in a rigid mathematical way, that this is not the case: after a small number of steps probability distribution of keys leaves no room for potential attacks.

Ring signature scheme is a cryptographic construct that enables a signer to sign on behalf of a group of $n$ different people such that the verifier can only ensure someone in the group signed, but not exactly whom. Ring signatures are utilized in many security applications. It is tricky to deploy multi-user cryptographic construct due to the complexity involved by certificates. Specifically, ring signatures working under traditional public key infrastructure requires the transfer and verification of $n$ certificates, making the scheme both space and time inefficient. On the other hand, the key-escrow problem of identity-based solution makes the authenticity of the ring signature in question. This paper studies ring signature in certificateless cryptography, one with neither certificate nor key-escrow. Designing a certificateless ring signature scheme is not entirely trivial. Many certificateless signatures require public key validity checking. In the context of ring signatures, this means both the signer and the verifier need to deal with the complexity in the verification of $n$ public keys. We propose the first certificateless ring signature scheme, without such public key validity checking.

In an identity-based encryption (IBE) scheme, there is a {\em key extraction} protocol where a user submits an identity string to a master authority who then returns the corresponding secret key for that identity. In this work, we describe how this protocol can be performed efficiently and in a {\em blind} fashion for several known IBE schemes; that is, a user can obtain a secret key for an identity without the master authority learning anything about this identity. We formalize this notion as {\em blind IBE} and discuss the many practical applications of such a scheme. In particular, we build upon the recent work of Camenisch, Neven, and shelat in Eurocrypt 2007 to construct oblivious transfer (OT) schemes which achieve full simulatability for both sender and receiver. OT constructions with comparable efficiency prior to Camenisch et al.\ were proven secure in the weaker half-simulation model. Our OT schemes can be constructed generically from any blind IBE, and thus require only static complexity assumptions (e.g., DBDH) whereas prior comparable schemes require dynamic complexity assumptions (e.g., $q$-PDDH).

Kerberos is a widely deployed network authentication protocol currently being considered for standardization. Many works have analyzed its security, identifying flaws and often suggesting fixes, thus promoting the protocol's evolution. Several recent results present successful, formal methods-based verifications of a significant portion of the current version, v.5, and some even imply security in the computational setting. For these results to hold, encryption in Kerberos should satisfy strong cryptographic security notions. However, prior to our work, none of the encryption schemes currently deployed as part of Kerberos, nor their proposed revisions, were known to provably satisfy such notions. We take a close look at Kerberos' encryption, and we confirm that most of the options in the current version provably provide privacy and authenticity, though some require slight modifications which we suggest. Our results complement the formal methods-based analysis of Kerberos that justifies its current design.

The abstraction of cryptographic operations by term algebras, called Dolev-Yao models or symbolic cryptography, is essential in almost all tool-supported methods for proving security protocols. Recently significant progress was made -- using two conceptually different approaches -- in proving that Dolev-Yao models can be sound with respect to actual cryptographic realizations and security definitions. One such approach is grounded on the notion of simulatability, which constitutes a salient technique of Modern Cryptography with a longstanding history for a variety of different tasks. The other approach strives for the so-called mapping soundness -- a more recent technique that is tailored to the soundness of specific security properties in Dolev-Yao models, and that can be established using more compact proofs. Typically, both notions of soundness for similar Dolev-Yao models are established separately in independent papers. In this paper, the two approaches are related for the first time. Our main result is that simulatability soundness entails mapping soundness provided that both approaches use the same cryptographic implementation. Interestingly, this result does not dependent on details of the simulator, which translates between cryptographic implementations and their Dolev-Yao abstractions in simulatability soundness. Hence, future research may well concentrate on simulatability soundness whenever applicable, and resort to mapping soundness in those cases where simulatability soundness is too strong a notion.

For all current adaptive chosen ciphertext(CCA) secure public key encryption schemes in standard model there are two operations in the decryption algorithm, ``validity check" and decryption. The decryption algorithm returns the corresponding plaintext if the ciphertext is valid otherwise it returns a rejection symbol $\perp$. We call this paradigm ``invalid ciphertext rejection". However the ``validity check" is not necessary for an encryption scheme. Also in this case the adversary will get the information that the ciphertext is "invalid" which he may not know before the decryption query. We propose a new paradigm for constructing CCA secure public key encryption schemes which combines ``validity check" and decryption together. The decryption algorithm will execute the same operation regardless of the ciphertext's validity. We call this new paradigm ``uniform decryption". Compared with the "invalid ciphertext rejection" paradigm, the decryption oracle of schemes in the new paradigm will reveal less information. The attacker even can not get whether the queried ciphertext is ``valid" or not. Moreover the combination of ``validity check" and the decryption will yield more efficient schemes. Using the new paradigm we construct an efficient public key encryption scheme. Our scheme is more efficient than CS98 in both computation and bandwidth. Compered with KD04 and HK07 the new scheme is more efficient in bandwidth and the same efficient in computation. The new scheme is as efficient as Kiltz07 both in computation and bandwidth. However the new scheme is CCA secure based on DDH assumption which is more flexible than GHDH assumption that Kiltz07 based on. Kurosawa and Desmedt proposed an efficient hybrid scheme named as KD04\cite{Kurosawa2004}. Although the key encapsulation part of KD04(KD04-KEM) is not CCA secure \cite{Hofheinz2006}, the whole scheme can be proved to be CCA secure. We show that if the key derivation function(KDF) of KD04-KEM is a non-malleable hash function it will be a CCA secure KEM in the new paradigm.

The k-Means Clustering problem is one of the most-explored problems in data mining to date. With the advent of protocols that have proven to be successful in performing single database clustering, the focus has changed in recent years to the question of how to extend the single database protocols to a multiple database setting. To date there have been numerous attempts to create specific multiparty k-means clustering protocols that protect the privacy of each database, but according to the standard cryptographic definitions of ``privacy-protection,'' so far all such attempts have fallen short of providing adequate privacy. In this paper we describe a Two-Party k-Means Clustering Protocol that guarantees privacy, and is more efficient than utilizing a general multiparty ``compiler'' to achieve the same task. In particular, a main contribution of our result is a way to compute efficiently multiple iterations of k-means clustering without revealing the intermediate values. To achieve this, we use novel techniques to perform two-party division and sample uniformly at random from an unknown domain size. Our techniques are quite general and can be realized based on the existence of any semantically secure homomorphic encryption scheme. For concreteness, we describe our protocol based on Paillier Homomorphic Encryption scheme (see [Pa]). We will also demonstrate that our protocol is efficient in terms of communication, remaining competitive with existing protocols (such as [JW]) that fail to protect privacy.

The stream ciphers Py, Py6 designed by Biham and Seberry were promising candidates in the ECRYPT-eSTREAM project because of their impressive speed. Since their publication in April 2005, a number of cryptanalytic weaknesses of the ciphers have been discovered. As a result, a strengthened version Pypy was developed to repair these weaknesses; it was included in the category of `Focus ciphers' of the Phase II of the eSTREAM competition. However, even the new cipher Pypy was not free from flaws, resulting in a second redesign. This led to the generation of three new ciphers TPypy, TPy and TPy6. The designers claimed that TPy would be secure with a key size up to 256 bytes, i.e., 2048 bits. In February 2007, Sekar \emph{et al.\ }published an attack on TPy with $2^{281}$ data and comparable time. This paper shows how to build a distinguisher with $2^{268.6}$ key/IVs and one outputword for each key (i.e., the distinguisher can be constructed within the design specifications); it uses a different set of weak states of the TPy. Our results show that distinguishing attacks with complexity lower than the brute force exist if the key size of TPy is longer than 268 bits. Therefore, for longer keys, our attack constitutes an academic break of the cipher. Furthermore, we discover a large number of similar bias-producing states of TPy and provide a general framework to compute them. The attacks on TPy are also shown to be effective on Py.

A public random function is a random function that is accessible by all parties, including the adversary. For example, a (public) random oracle is a public random function $\{0,1\}^{*} \to \{0,1\}^n$. The natural problem of constructing a public random oracle from a public random function $\{0,1\}^{m} \to \{0,1\}^n$ (for some $m > n$) was first considered at Crypto 2005 by Coron et al.\ who proved the security of variants of the Merkle-Damgård construction against adversaries issuing up to $O(2^{n/2})$ queries to the construction and to the underlying compression function. This bound is less than the square root of $n2^m$, the number of random bits contained in the underlying random function. In this paper, we investigate domain extenders for public random functions approaching optimal security. In particular, for all $\epsilon \in (0,1)$ and all functions $m$ and $\ell$ (polynomial in $n$), we provide a construction $\mathbf{C}_{\epsilon,m,\ell}(\cdot)$ which extends a public random function $\mathbf{R}: \{0,1\}^{n} \to \{0,1\}^n$ to a function $\mathbf{C}_{\epsilon,m,\ell}(\R): \{0,1\}^{m(n)} \to \{0,1\}^{\ell(n)}$ with time-complexity polynomial in $n$ and $1/\epsilon$ and which is secure against adversaries which make up to $\Theta(2^{n(1-\epsilon)})$ queries. A central tool for achieving high security are special classes of unbalanced bipartite expander graphs with small degree. The achievability of practical (as opposed to complexity-theoretic) efficiency is proved by a non-constructive existence proof. Combined with the iterated constructions of Coron et al., our result leads to the first iterated construction of a hash function $\{0,1\}^{*} \to \{0,1\}^n$ from a component function $\{0,1\}^{n} \to \{0,1\}^n$ that withstands all recently proposed generic attacks against iterated hash functions, like Joux's multi-collision attack, Kelsey and Schneier's second-preimage attack, and Kelsey and Kohno's herding attacks.

Montgomery multiplication is one of the fundamental operations used in cryptographic algorithms, such as RSA and Elliptic Curve Cryptosystems. At CHES 1999, Tenca and Koc introduced a now-classical architecture for implementing Montgomery multiplication in hardware. With parameters optimized for minimum latency, this architecture performs a single Montgomery multiplication in approximately 2n clock cycles, where n is the size of operands in bits. In this paper we propose and discuss an optimized hardware architecture performing the same operation in approximately n clock cycles. Our architecture is based on pre-computing partial results using two possible assumptions regarding the most significant bit of the previous word, and is only marginally more demanding in terms of the circuit area. The new radix-2 architecture can be extended for the case of radix-4, while preserving a factor of two speed-up over the corresponding radix-4 design by Tenca, Todorov, and Koc from CHES 2001. Our architecture has been verified by modeling it in Verilog-HDL, implementing it using Xilinx Virtex-II 6000 FPGA, and experimentally testing it using SRC-6 reconfigurable computer.

This paper presents the Cryptanalytic Channel Model (CCM). The model treats statistical key recovery as communication over a low capacity channel, where the channel and the encoding are determined by the cipher and the specific attack. A new attack, related-key recovery -- the use of $n$ related keys generated from $k$ independent ones -- is defined for all ciphers vulnerable to single-key recovery. It is shown to correspond to the use of a concatenated code over the channel, where the relationship among the keys determines the outer code, and the cipher and the attack the inner code. It is shown that there exists a relationship among keys for which the communication complexity per bit of independent key is finite, for any probability of key recovery error. This may be compared to the unbounded communication complexity per bit of the single-key-recovery attack. The practical implications of this result are demonstrated through experiments on reduced-round DES.

Ristenpart and Rogaway defined "mix" functions, which are used to mix inputs from two sets of equal size, and produce outputs from the same two sets, in an optimal way. These functions have a cryptographic application in the context of extending the domain of a block cipher. It was observed that mix functions could be constructed from orthogonal latin squares. In this paper, we give a simple, scalable construction for mix functions. We also consider a generalization of mix functions, in which the two sets need not be of equal size. These generalized mix functions turn out to be equivalent to an interesting type of combinatorial design which has not previously been studied. We term these "orthogonal equitable rectangles" and we construct them for all possible parameter situations, with a small number of exceptions and possible exceptions.

Restrictive partially blind signature (RPBS) plays an important role in designing secure electronic cash system. Very recently, Wang, Tang and Li proposed a new ID-based restrictive partially blind signature (ID-RPBS) and gave the security proof. In this paper, we present a cryptanalysis of the scheme and show that the signature scheme does not satisfy the property of {\bf unforgeability} as claimed. More precisely, a user can forge a valid message-signature pair $(ID, msg, {\bf info'}, \sigma')$ instead of the original one $(ID, msg, {\bf info}, \sigma)$, where {\bf info} is the original common agreed information and ${\bf info}'\neq {\bf info}$. Therefore, it will be much dangerous if Wang-Tang-Li's ID-RPBS scheme is applied to the off-line electronic cash system. For example, a bank is supposed to issue an electronic coin (or bill) of \$100 to a user, while the user can change the denomination of the coin (bill) to any value, say \$100, 000, 000, at his will.

In 2004, Ari Juels [1] proposed a Yoking-Proofs protocol for RFID systems. The aim is to permit tags to generate a proof which is verifiable off-line by a trusted entity even when the readers are potentially untrusted. However, we find that their protocol not only doesn’t possess the anonymity property but also suffers from both of the off-line and replay attacks. In 2006, Kirk H.M. Wong et al. [3] proposed an authentication scheme on RFID passive tags, attempting to as a standard for apparel products. Yet, to our view, their protocol suffers from the known-plaintext attack. In this paper, we first point out the weaknesses in the two above mentioned protocols. Then, we propose a novel efficient scheme which not only can achieve the mutual authentication between the server and tag but also possess the anonymity property needed in a RFID system.

Fix a small, non-empty set of blockcipher keys $K$. We say a blockcipher-based hash function is highly-efficient if it makes exactly one blockcipher call for each message block hashed, and all blockcipher calls use a key from $K$. Although a few highly-efficient constructions have been proposed, no one has been able to prove their security. In this paper we prove, in the ideal-cipher model, that it is impossible to construct a highly-efficient iterated blockcipher-based hash function that is provably secure. Our result implies, in particular, that the Tweakable Chain Hash (TCH) construction suggested by Liskov, Rivest, and Wagner is not correct under an instantiation suggested for this construction, nor can TCH be correctly instantiated by any other efficient means.

This paper considers a recently introduced framework for the analysis of physically observable cryptographic devices. It exploits a model of computation that allows quantifying the effect of practically relevant leakage functions with a combination of security and information theoretic metrics. As a result of these metrics, a unified evaluation methodology for side-channel attacks was derived that we illustrate by applying it to an exemplary block cipher implementation. We first consider a Hamming weight leakage function and evaluate the efficiency of two commonly investigated countermeasures, namely noise addition and masking. Then, we show that the proposed methodology allows capturing certain non-trivial intuitions about the respective effectiveness of these countermeasures Finally, we justify the need of combined metrics for the evaluation, comparison and understanding of side-channel attacks.

In this paper, we introduce a new primitive called identity-based encryption with wildcard key derivation (WKD-IBE, or "wicked IBE") that enhances the concept of hierarchical identity-based encryption (HIBE) by allowing more general key delegation patterns. A secret key is derived for a vector of identity strings, where entries can be left blank using a wildcard. This key can then be used to derive keys for any pattern that replaces wildcards with concrete identity strings. For example, one may want to allow the university's head system administrator to derive secret keys (and hence the ability to decrypt) for all departmental sysadmin email addresses sysadmin@*.univ.edu, where * is a wildcard that can be replaced with any string. We provide appropriate security notions and provably secure instantiations with different tradeoffs in terms of ciphertext size and efficiency. We also present a generic construction of identity-based broadcast encryption (IBBE) from any WKD-IBE scheme. One of our instantiation yields an IBBE scheme with constant ciphertext size.

The session initiation protocol (SIP) is considered as the dominant signaling protocol for calls over the internet. However, SIP authentication typically uses HTTP digest authentication, which is vulnerable to many forms of known attacks. This paper proposes a new secure authentication and key agreement mechanism based on certificateless public-key cryptography, named as SAKA, between two previously unknown parties, which provides stronger security assurances for SIP authentication and media stream, and is provably secure in the CK security model. Due to using certificateless public key cryptography, SAKA effectively avoids the requirement of a large Public Key Infrastructure and conquers the key escrow problem in previous schemes.

SIP is playing a key role in the IP based services and has been chosen as the protocol for multimedia application in 3G mobile networks by the Third-Generation Partnership Project. The authentication mechanism proposed in SIP specification is HTTP digest based authentication, which allows malicious parties to impersonate other parties or to charge calls to other parties, furthermore, other security problems, such as off-line password guessing attacks and server spoofing, are also needed to be solved. This paper proposes a new authenticated key exchange protocol NAKE, which can solve the existed problems in the original proposal. The NAKE protocol is provably secure in CK security model, thus it inherits the corresponding security attributes in CK security model.

In this paper we present a general framework for the application of the ideas of differential cryptanalysis to stream ciphers. We demonstrate that some differences in the key (or the initial state or the plaintext) are likely to cause predicted differences in the key stream or in the internal state. These stream differences can then be used to analyze the internal state of the cipher and retrieve it efficiently. We apply our proposed ideas to stream ciphers of various designs, e.g., regularly clocked LFSRs, irregularly clocked LFSRs such as A5/1, and permutation-based stream ciphers such as RC4.

Broadcast encryption schemes enable senders to efficiently broadcast ciphertexts to a large set of receivers in a way that only non-revoked receivers can decrypt them. Identity-based encryption schemes are public key encryption schemes that can use arbitrary strings as public keys. We propose the first public key broadcast encryption scheme that can use any string as a public key of each receiver. That is, identity-based broadcast encryption scheme. Our scheme has many desirable properties. The scheme is fully collusion resistant, and the size of ciphertexts and that of private key are small constants. The size of public key is proportional to only the maximum number of receiver sets to each of which the ciphertext is sent. Note that its size remains to be so although the number of potential receivers is super-polynomial size. Besides these properties, the achieving the first practical identity-based broadcast encryption scheme itself is the most interesting point of this paper. The security of our scheme is proved in the generic bilinear group model.

We present an efficient divisible digital cash scheme which is unlinkable and does not require Trusted Third Party. The size of the coin is proportional to the size of the primes we use, i.e., hundreds of bytes. The computational and communication complexity of the protocol is proportional to a polynomial of the size of the primes and polylogarithm of the maximum number of pieces to which a coin can be subdivided.

At Crypto 2003 Ishai et al. gave a protocol which given a small number of (possibly extremely inefficient) oblivious transfers implements an essentially unbounded number of oblivious transfers for an additional overhead, per oblivious transfer, of computing and sending only two hash values. This highly efficient protocol is however only passive secure. To get active security, except with probability $2^{-m}$, the protocol had to suffer an additional overhead of a factor $1+m$. We introduce a new approach to adding robustness. For practical security parameters this approach allows to add robustness while suffering only a small constant overhead over the passive secure protocol. As an example we can generate one million oblivious transfers with security $2^{-42}$ with an amortized cost of just $9$ hash values per oblivious transfer.

The new symmetric cipher S-box construction based on matrix power function is presented. The matrix consisting of plain data bit strings is combined with three round key matrices using arithmetical addition and exponent operations. The matrix power means the matrix powered by other matrix. The left and right side matrix powers are introduced. This operation is linked with two sound one-way functions: the discrete logarithm problem and decomposition problem. The latter is used in the infinite non-commutative group based public key cryptosystems. It is shown that generic S-box equations are not transferable to the multivariate polynomial equations in respect of input and key variables and hence the algebraic attack to determine the key variables cannot be applied in this case. The mathematical description of proposed S-box in its nature possesses a good ``confusion and diffusion'' properties and contains variables ``of a complex type'' as was formulated by Shannon. Some comparative simulation results are presented.

We formalize a generic method of constructing efficient group signatures, specifically, we define new notions of unlinkable randomizable signature, indirectly signable signature and $\Sigma$-protocol friendly signature. We conclude that designing efficient secure group signatures can be boiled down to designing ordinary signatures satisfying the above three properties, which is supported by observations that almost all currently known secure efficient group signatures have alternative constructions in this line without deteriorating the efficiency.

In this work we present a new way to construct $3$-resilient Boolean functions of $9$ variables with nonlinearity $240$. Such function have been discovered very recently by heuristic search. We find these functions by exhaustive search in the class of functions symmetric under cyclic shifts of the first seven variables. The exhaustive search was reduced significantly by using of special techniques and algorithms which can be helpful in other similar problems. Also we construct some new functions that attain the upper bound on nonlinearity of higher number of variables.

Kallahalla et al. presented a RSA-based Forward Key Rotation mechanism in secure storage scheme PLUTUS to ensure that the key used for encrypting updated files is related to the keys for all files in the file group. The encryption scheme based on Forward Key Rotation is such a scheme that only the authorized person is allowed access to the designated files and the previous versions. In this paper, we present a Forward Key Rotation storage scheme based on discrete logarithm and prove its security under random oracle model. Moreover, we propose another improved Forward Key storage scheme from pairing on elliptic curves. Compared to the scheme presented by Kallahalla et al., our scheme uses relatively short keys to provide equivalent security. In addition, the re-generated keys can be verified to ensure that the keys are valid in the improved scheme.

Kurosawa and Matsuo\cite{Kurosawa20042} showed that MAC can be removed from DHIES while the underlying symmetric-key encryption(SKE) scheme is secure against adaptive chosen ciphertext attacks(IND-CCA). We construct a variant of DHIES which eliminate the MAC while the SKE scheme is secure against passive attacks(IND-PA). Since IND-PA is the basic requirement of SKE schemes, the new scheme is more flexible than \cite{Kurosawa20042}. Our new scheme can be seen as a combination of a tag-KEM \cite{Abe2005} and a DEM. Our construction offers the first tag-KEM with single element. When the hash function $H$ in the ODH assumption is a non-malleable hash function we can prove that the new scheme is IND-CCA secure under the ODH assumption.

Unknown Key-Share (UKS) resilience is a basic security attribute in authenticated key agreement protocols, whereby two entities A and B should not be able to be coerced into sharing a key between them when in fact either A or B thinks that s/he is sharing the key with another entity C. In this paper we revisit some definitions of this attribute, the existing UKS attacks and the method of proving this attribute in the Bellare-Rogaway (BR) model in the literature. We propose a new UKS attack, which coerces two entities A and B into sharing a key with each other but in fact A thinks that she is sharing the key with another entity C and B thinks that he is sharing the key with another entity D, where C and D might or might not be the same entity. We call this attack a Bilateral Unknown Key-Share(BUKS) attack and refer to the existing UKS attacks, which are against one entity only, as a Unilateral UKS (UUKS) attack. We demonstrate that a few well-known authenticated key agreement protocols, some of which have been proved holding the UUKS resilience property, are vulnerable to the BUKS attack. We then explore a gap between the traditional BR-type proof of UUKS resilience and a BUKS adversary's behaviour, and extend the BR model to cover the BUKS resilience attribute. Finally we provide a simple countermeasure to prevent a key agreement protocol from BUKS attacks.

A theoretical analysis of the RC4 Key Scheduling Algorithm (KSA) is presented in this paper, where the nonlinear operation is swapping among the permutation bytes. Explicit formulae are provided for the probabilities with which the permutation bytes at any stage of the KSA are biased to the secret key. Theoretical proofs of these formulae have been left open since Roos' work (1995). Next, a generalization of the RC4 KSA is analyzed corresponding to a class of update functions of the indices involved in the swaps. This reveals an inherent weakness of shuffle-exchange kind of key scheduling. We additionally show that each byte of $S_N$ actually reveals secret key information. Looking at all the elements of the final permutation $S_N$ and its inverse $S^{-1}_N$, the value of the hidden index $j$ in each round of the KSA can be estimated from a ``pair of values" in $0, \ldots, N-1$ with a constant probability of success $\pi = \frac{N-2}{N}\cdot(\frac{N-1}{N})^{N-1} + \frac{2}{N}$ (we get $\pi \approx 0.37$, for $N = 256$), which is significantly higher than the random association. Using the values of two consecutive $j$'s, we estimate the $y$-th key byte from at most a ``quadruple of values" in $0, \ldots, N-1$ with a probability $> 0.12$. As a secret key of $l$ bytes is repeated at least $\lfloor \frac{N}{l}\rfloor$ times in RC4, these many quadruples can be accumulated to get each byte of the secret key with very high probability (e.g., 0.8 to close to 1) from a small set of values. Based on our analysis of the key scheduling, we show that the secret key of RC4 can be recovered from the state information in a time much less than the exhaustive search with good probability.

We investigate the security of $n$-bit to $m$-bit vectorial Boolean functions in stream ciphers. Such stream ciphers have higher throughput than those using single-bit output Boolean functions. However, as shown by Zhang and Chan at Crypto 2000, linear approximations based on composing the vector output with any Boolean functions have higher bias than those based on the usual correlation attack. In this paper, we introduce a new approach for analyzing vector Boolean functions called generalized correlation analysis. It is based on approximate equations which are linear in the input $x$ but of free degree in the output $z=F(x)$. The complexity for computing the generalized nonlinearity for this new attack is reduced from $2^{2^m \times n+n}$ to $2^{2n}$. Based on experimental results, we show that the new generalized correlation attack gives linear approximation with much higher bias than the Zhang-Chan and usual correlation attack. We confirm this with a theoretical upper bound for generalized nonlinearity, which is much lower than for the unrestricted nonlinearity (for Zhang-Chan's attack) and {\em a fortiori} for usual nonlinearity. We also prove a lower bound for generalized nonlinearity which allows us to construct vector Boolean functions with high generalized nonlinearity from bent and almost bent functions. We derive the generalized nonlinearity of some known secondary constructions for secure vector Boolean functions. Finally, we prove that if a vector Boolean function has high nonlinearity or even a high unrestricted nonlinearity, it cannot ensure that it will have high generalized nonlinearity.

In 2004, Wang et al. obtained breakthrough collision attacks on the main hash functions from the MD4 family. The attacks are differential attacks in which one closely follows the inner steps of the underlying compression function, based on a so-called differential path. It is generally assumed that such differential paths were found ``by hand''. In this paper, we present an algorithm which automatically finds suitable differential paths, in the case of MD4. As a first application, we obtain new differential paths for MD4, which improve upon previously known MD4 differential paths. This algorithm could be used to find new differential paths, and to build new attacks against MD4.

We describe how we reached a new factoring milestone by completing the first special number field sieve factorization of a number having more than 1024 bits, namely the Mersenne number $2^{1039}-1$. Although this factorization is orders of magnitude `easier' than a factorization of a 1024-bit RSA modulus is believed to be, the methods we used to obtain our result shed new light on the feasibility of the latter computation.

Sensor networks offer economically viable monitoring solutions for a wide variety of applications. In order to combat the security threats that sensor networks are exposed to, a cryptography protocol is implemented at sensor nodes for point-to-point encryption between nodes. Disclosure, disruption and deception threats can be defeated by authenticating data sources as well as encrypting data in transmission. Given that nodes have limited resources, symmetric cryptography that is proven to be efficient for low power devices is implemented. Data protection is integrated into a sensor's packet by the means of symmetric encryption with the Dragon stream cipher and incorporating the newly designed Dragon-MAC Message Authentication Code. The proposed algorithm was designed to employ some of the data already computed by the underlying Dragon stream cipher for the purpose of minimizing the computational cost of the operations required by the MAC algorithm. In view that Dragon is a word based stream cipher with a fast key stream generation, it is very suitable for a constrained environment. Our protocol regarded the entity authentication and message authentication through the implementation of authenticated encryption scheme in Telos B wireless sensor nodes.

In this paper, we show that the claims in the original Kipnis-Shamir's attack on the HFE cryptosystems and the improved attack by Courtois that the complexity of the attacks is polynomial in terms of the number of variables are invalid. We present computer experiments and a theoretical argument using basic algebraic geometry to explain why it is so. Furthermore we show that even with the help of the powerful new Gröbner basis algorithm like $F_4$, the Kipnis-Shamir's attack still should be exponential not polynomial. This again is supported by our theoretical argument.

We introduce a model for {\em provable data possession} ($\pdp$) that allows a client that has stored data at an untrusted server to verify that the server possesses the original data without retrieving it. The model generates probabilistic proofs of possession by sampling random sets of blocks from the server, which drastically reduces I/O costs. The client maintains a constant amount of metadata to verify the proof. The challenge/response protocol transmits a small, constant amount of data, which minimizes network communication. Thus, the $\pdp$ model for remote data checking supports large data sets in widely-distributed storage systems. Previous work offers guarantees weaker than data possession, or requires prohibitive overhead at the server. We present two provably-secure $\pdp$ schemes that are more efficient than previous solutions, even when compared with schemes that achieve weaker guarantees. In particular, the overhead at the server is low (or even constant), as opposed to linear in the size of the data. Experiments using our implementation verify the practicality of $\pdp$ and reveal that the performance of $\pdp$ is bounded by disk I/O and not by cryptographic computation.

At Eurocrypt 2005, Boneh, Boyen, and Goh presented a hierarchical IBE for which they claimed a novel property, called limited delegation: it is possible to give an entity a private key that restricts it from generating descendant private keys beyond some depth d; in particular, with d equal to the entity's depth, such a key allows decryption only. In this paper, we argue that this claim is nonobvious and requires proof, provide a precise model for arguing about limited delegation, and prove that the Boneh-Boyen-Goh system does, in fact, have limited delegation. Whereas Boneh, Boyen, and Goh prove their system semantically secure under the BDHI assumption, our proof of limited delegation requires the stronger BDHE assumption.

The notion of Signer-Base Intrusion-Resilient (SiBIR) signatures was introduced in [IR02] as a scheme that can withstand an arbitrary number of key-exposures, as long as both of its modules are not compromised simultaneously. This was achieved by dividing time into predefined time periods, each corresponding to a different time-evolving secret key, while maintaining a constant public key. The two modules of this scheme consist of a signer that can generate signatures on its own, and a base that is used to update the signer's key as it evolves through time. The purpose of this paper is to provide a model for multi-signer, multi-base intrusion-resilient signatures. This proactive SiBIR scheme essentially breaks the preexisting notions of signer and base, to an arbitrary number of signer and base modules. This tends to implementations where multiple parties need to agree for a document to be signed. An attacker needs to break into all the signers at the same time in order to forge a signature for that period. Moreover, he needs to break into all the bases as well, at that same time period, in order to "break" the scheme and generate future signatures. Thereby, by assuming a large number of bases, the risk of our scheme being compromised becomes arbitrarily small. We provide an implementation that's provably secure in the random oracle model, based on the strong RSA assumption. We also yield a modest improvement in the upperbound of our scheme's insecurity function, as opposed to the one presented in [IR02].

Information security is nowadays an important issue. Its essential ingredient is cryptography. A common way to present security proofs is to structure them as sequences of games. The main contribution of this paper is a framework which refines this approach. We make explicit important theorems used implicitly by cryptographers but never explicitly stated. Our aim is to have a framework in which proofs are precise enough to be mechanically checked, and readable enough to be humanly checked. We illustrate the use of our framework by proving in a systematic way the so-called semantic security of the encryption scheme ElGamal and its hashed version. All proofs have been mechanically checked in the proof assistant Coq.

In this paper, we develop an information theoretic differential side-channel attack. An embedded device containing a secret key is modeled as a black box with a leakage function whose output is captured by an adversary through the noisy measurement of a physical observable e.g. the power consumed by the device. We assume only that the measured values depend somehow on the leakage and thus on the word being processed by the device. Without any knowledge on the particular dependency, this fact is exploited to mount a side-channel attack. We build a distinguisher which uses the Mutual Information between the observed and the leaked values as a statistical test. The Mutual Information is maximal when the hypothetical key guessed by the attacker equals the key in the device. Our approach is confirmed by experimental results. We perform power analysis on an embedded device using our Mutual Information based distinguisher and show that the correct key is clearly distinguishable. Finally, our approach allows to compute a good estimate of the minimal number of traces required to perform a successful attack and gives an upper bound on the information leakage in a single observation.

We initiate a study of on-line ciphers. These are ciphers that can take input plaintexts of large and varying lengths and will output the i-th block of the ciphertext after having processed only the first i blocks of the plaintext. Such ciphers permit length-preserving encryption of a data stream with only a single pass through the data. We provide security definitions for this primitive and study its basic properties. We then provide attacks on some possible candidates, including CBC with fixed IV. We then provide two constructions, HCBC1 and HCBC2, based on a given block cipher E and a family of computationally AXU functions. HCBC1 is proven secure against chosen-plaintext attacks assuming that E is a PRP secure against chosen-plaintext attacks, while HCBC2 is proven secure against chosen-ciphertext attacks assuming that E is a PRP secure against chosen-ciphertext attacks.

In this paper we present a certificateless signature (CLS) scheme secure in the Random Oracle Model. This scheme requires no pairing computations for signature generation and only two for signature verification. As far as we know, this is the only CLS scheme to require less than four pairing computations on signature verification.

Statistical zero-knowledge (SZK) properties play an important role in designing cryptographic protocols that enforce honest behavior while maintaining privacy. This paper presents a novel approach for verifying SZK properties, using recently developed techniques based on approximate simulation relations. We formulate statistical indistinguishability as an implementation relation in the Task-PIOA framework, which allows us to express computational restrictions. The implementation relation is then proven using approximate simulation relations. This technique separates proof obligations into two categories: those requiring probabilistic reasoning, as well as those that do not. The latter is a good candidate for mechanization. We illustrate the general method by verifying the SZK property of the well-known identification protocol of Girault, Poupard and Stern.

Direct Anonymous Attestation (DAA) is a scheme that enables the remote authentication of a Trusted Platform Module (TPM) while preserving the user's privacy. A TPM can prove to a remote party that it is a valid TPM without revealing its identity and without linkability. In the DAA scheme, a TPM can be revoked only if the DAA private key in the hardware has been extracted and published widely so that verifiers obtain the corrupted private key. If the unlinkability requirement is relaxed, a TPM suspected of being compromised can be revoked even if the private key is not known. However, with the full unlinkability requirement intact, if a TPM has been compromised but its private key has not been distributed to verifiers, the TPM cannot be revoked. Furthermore, a TPM cannot be revoked from the issuer, if the TPM is found to be compromised after the DAA issuing has occurred. In this paper, we present a new DAA scheme called Enhanced Privacy ID (EPID) scheme that addresses the above limitations. While still providing unlinkability, our scheme provides a method to revoke a TPM even if the TPM private key is unknown. This expanded revocation property makes the scheme useful for other applications such as for driver's license. Our EPID scheme is efficient and provably secure in the same security model as DAA, i.e. in the random oracle model under the strong RSA assumption and the decisional Diffie-Hellman assumption.

The problem of generalization of (single) designated verifier schemes to several designated verifiers was proposed by Desmedt in 2003. The paper proposes eight new Identity Based Strong Bi-Designated Verifier Signature Schemes in which the two designated verifiers may not know each other. The security and the computational efficiency of the schemes are also analyzed.

The irreducible polynomials recommended for use by multiple standards documents are in fact far from optimal on many platforms. Specifically they are suboptimal in terms of performance, for the computation of field square roots and in the application of the ``almost inverse'' field inversion algorithm. In this paper we question the need for the standardisation of irreducible polynomials in the first place, and derive the ``best'' polynomials to use depending on the underlying processor architecture. Surprisingly it turns out that a trinomial polynomial is in many cases not necessarily the best choice. Finally we make some specific recommendations for some particular types of architecture.

In this work, we develop a family of protocols for deniable Internet Key-Exchange (IKE) with the following properties: 1. item Highly practical efficiency, and conceptual simplicity and clarity. 2. Forward and concurrent (non-malleable) deniability against adversaries with arbitrary auxiliary inputs, and better privacy protection of players' roles. 3. Provable security in the Canetti-Krawczyk post-specified-peer model, and maintenance of essential security properties not captured by the Canetti-Krawczyk security model. 4. Compatibility with the widely deployed and standardized SIGMA (i.e., the basis of IKEv2) and (H)MQV protocols, when parties possess DL public-keys. Our protocols could potentially serve, in part, as either the underlying basis or a useful alternative for the next generation of IKE (i.e., IKEv3) of IPsec (in particular, when deniability is desired). In view of the wide deployment and use of IKE and increasing awareness of privacy protection (especially for E-commerce over Internet), this work is naturally of practical interest.

In applications of public-key encryption schemes, anonymity(key-privacy) as well as security(data-privacy) is useful and widely desired. In this paper some new and general concepts in public-key encryption, i.e., “master-key anonymity”, “relevant master-key anonymity” and “key-integrity”, are introduced(the former two are defined for IBE schemes and the latter one is for any public-key encryption scheme). By the concept of master-key anonymity, we prove that chosen-plaintext master-key anonymity is a sufficient condition for chosen-ciphertext anonymity in the recent elegant Canetti-Halevi-Katz and Boneh-Katz construction. By the concept of key-integrity, we prove it is(together with chosen-plaintext anonymity)a sufficient/necessary condition for chosen-ciphertext anonymity. In addition to these general consequences, some practical examples are also investigated to show such concepts’ easy-to-use in practice.

A tripartite authenticated key agreement protocol is generally designed to accommodate the need of three specific entities in communicating over an open network with a shared secret key, which is used to preserve confidentiality and data integrity. Since Joux initiates the development of tripartite key agreement protocol, many prominent tripartite schemes have been proposed subsequently. In 2005, Tso et al. have proposed an ID-based non-interactive tripartite key agreement scheme with k-resilience. Based on this scheme, they have further proposed another one-round tripartite application scheme. Although they claimed that both schemes are efficient and secure, we discover that both schemes are in fact breakable. In this paper, we impose several impersonation attacks on Tso et al.'s schemes in order to highlight their flaws. Subsequently, we propose an enhanced scheme which will not only conquer their defects, but also preserve the desired security attributes of a key agreement protocol.

Although the Yahalom protocol, proposed by Burrows, Abadi, and Needham in 1990, is one of the most prominent key establishment protocols analyzed by researchers from the computer security community (using automated proof tools), a simplified version of the protocol is only recently proven secure by Backes and Pfitzmann (2006) in their \textit{cryptographic library} framework. We present a protocol for key establishment that is closely based on the Yahalom protocol. We then present a security proof in the Bellare and Rogaway (1993) model and the random oracle model. We also observe that no partnering mechanism is specified within the Yahalom protocol. We then present a brief discussion on the role and the possible construct of session identifiers as a form of partnering mechanism, which allows the right session key to be identified in concurrent protocol executions. We then recommend that session identifiers should be included within protocol specification rather than consider session identifiers as artefacts in protocol proof.

Demand in the consumer market for graphics hardware that accelerates rendering of 3D images has resulted in commodity devices capable of astonishing levels of performance. These results were achieved by specifically tailoring the hardware for the target domain. As graphics accelerators become increasingly programmable this performance makes them an attractive target for other domains. Specifically, they have motivated the transformation of costly algorithms from a general purpose computational model into a form that executes on said graphics hardware. We investigate the implementation and performance of modular exponentiation using a graphics accelerator, with the view of using it to execute operations required in the RSA public key cryptosystem.

We construct a new group signature scheme using bilinear groups. The group signature scheme is practical, both keys and group signatures consist of a constant number of group elements, and the scheme permits dynamic enrollment of new members. The scheme satisfies strong security requirements, in particular providing protection against key exposures and not relying on random oracles in the security proof.

The hash function FORK-256 was published at the ¯rst NIST hash workshop and FSE 2006. It consists of simple operations so that its performance is better than that of SHA-256. However, recent papers show some weaknesses of FORK-256. In this paper, we propose newly modi¯ed FORK-256 which has no microcoliisions and so is resistant against existing attacks. Furthermore, it is faster than the old one.

A password-based tripartite key agreement protocol is presented in this paper. The three entities involved in this protocol can negotiate a common session key via a shared password over insecure networks. Proofs are given to show that the proposed protocol is secure against forging and chosen message attacks in the case of without actually running a dictionary attack.

In ciphertext policy attribute-based encryption (CP-ABE), every secret key is associated with a set of attributes, and every ciphertext is associated with an access structure on attributes. Decryption is enabled if and only if the user's attribute set satisfies the ciphertext access structure. This provides fine-grained access control on shared data in many practical settings, including secure databases and secure multicast. In this paper, we study CP-ABE schemes in which access structures are AND gates on positive and negative attributes. Our basic scheme is proven to be chosen plaintext (CPA) secure under the decisional bilinear Diffie-Hellman (DBDH) assumption. We then apply the Canetti-Halevi-Katz technique to obtain a chosen ciphertext (CCA) secure extension using one-time signatures. The security proof is a reduction to the DBDH assumption and the strong existential unforgeability of the signature primitive. In addition, we introduce hierarchical attributes to optimize our basic scheme, reducing both ciphertext size and encryption/decryption time while maintaining CPA security. Finally, we propose an extension in which access policies are arbitrary threshold trees, and we conclude with a discussion of practical applications of CP-ABE.