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.

This paper addresses the security of optimistic fair exchange in a multi-user setting. While the security of public key encryption and public key signature schemes in a single-user setting guarantees the security in a multi-user setting, we show that the situation is different in the optimistic fair exchange. First, we show how to break, in the multi-user setting, an optimistic fair exchange scheme provably secure in the single-user setting. This example separates the security of optimistic fair exchange between the single-user setting and the multi-user setting. We then define the formal security model of optimistic fair exchange in the multi-user setting, which is the first complete security model of optimistic fair exchange in the multi-user setting. We prove the existence of a generic construction meeting our multi-user security based on one-way functions in the random oracle model and trapdoor one-way permutations in the standard model. Finally, we revisit two well-known methodologies of optimistic fair exchange, which are based on the verifiably encrypted signature and the sequential two-party multisignature, respectively. Our result shows that these paradigms remain valid in the multi-user setting.

Now, It is believed that the best costs of a point doubling and addition on elliptic curves over binary fields are 4M+5S(namely, four finite field multiplications and five field squarings) and 8M+5S, respectively. In this paper we reduce the costs to less than 3M+3S and 8M+1S, respectively, by using a new projective coordinates we call PL-coordinates and rewriting the point doubling formula. Combining some programming skills, the method can speed up a elliptic curve scalar multiplication by about 15～20 percent in practice.

In 1997, Ruppe R. et al [17] first proposed a Near-Term Digital Radio (NTDR) network system which is a cluster-based ad hoc network intended to be used efficiently for military missions. In the same year, Zavgren J. [18] proposed a management protocol for the NTDR network system. But they both lack the security considerations. In 2003, Varadharajan et al [4] proposed a secure cluster-based ad hoc network protocol using public key infrastructure (PKI). However, in 2005, Chang et al pointed out that using PKI would be a heavy burden for the computation of each mobile node. Hence, they proposed a protocol [5] based on Diffie-Hellman method for securing network, in the same year, Liaw et al. proposed a secured key exchange protocol [20] for securing nodes communication in mobile ad hoc networks (MANETs). In 2006, also for security purpose, Chang and Lee [6] proposed the other scheme by using nodes’ identities. But after our analysis, we find that both of their protocols have some mistakes. Accordingly, we propose a new protocol based on ID-based bilinear pairing to get rid of nowadays unsolved security problem in NTDR network. After our analysis, we conclude that our scheme is not only secure but also very efficient.

In previous works on ECC(Elliptic Curve Cryptography), the case of characteristic three has been considered relatively less than cases of fields of even characteristic and large prime fields. To the best of our knowledge, for point multiplication on ordinary elliptic curves over fields of characteristic three the most efficient way is known as one shown by N.P. Smart et al.(cf. [2]). In first portion of this paper we propose new fast algorithms for arithmetic on Hessian elliptic curves over finite field of characteristic three, which reduce costs of a doubling and a mixed point addition from 3M+3C and 10M (cf. [2]) to 3M+2C and 9M+1C, respectively. These algorithms can realize fast point multiplication nearly comparable with the case of even characteristic, on ordinary elliptic curves over finite field of characteristic three. In next portion we propose a kind of projective coordinates we call ML coordinates and new algorithms for arithmetic on Weierstrass elliptic curve in it, which reduce costs of a tripling and a mixed point addition from 7M+4C and 10M+2C (cf. [2]) to 6M+6C and 8M+2C, respectively. In conclusion, we can say that ternary elliptic curves are another alternative to existing technology for elliptic curve cryptosystems.

We propose a new trust metric for a network of public key certificates, e.g. as in PKI, which allows a user to buy insurance at a fair price on the possibility of failure of the certifications provided while transacting with an arbitrary party in the network. Our metric builds on a metric and model of insurance provided by Reiter and Stubblebine~\cite{RS}, while addressing various limitations and drawbacks of the latter. It conserves all the beneficial properties of the latter over other schemes, including protecting the user from unintentional or malicious dependencies in the network of certifications. Our metric is built on top of a simple and intuitive model of trust and risk based on ``utility sampling'', which maybe of interest for non-monetary applications as well.

Identity Based Encryption (IBE) systems are often constructed using bilinear maps (a.k.a. pairings) on elliptic curves. One exception is an elegant system due to Cocks which builds an IBE based on the quadratic residuosity problem modulo an RSA composite N. The Cocks system, however, produces long ciphertexts. Since the introduction of the Cocks system in 2001 it has been an open problem to construct a space efficient IBE system without pairings. In this paper we present an IBE system in which ciphertext size is short: an encryption of an L-bit message consists of a single element in Z_N plus L+1 additional bits. Security, as in the Cocks system, relies on the quadratic residuosity problem. The system is based on the theory of ternary quadratic forms and as a result, encryption and decryption are slower than in the Cocks system.

Nearly all modern hash functions are constructed by iterating a compression function. At FSE'04, Rogaway and Shrimpton [RS04] formalized seven security notions for hash functions: collision resistance (Coll) and three variants of second-preimage resistance (Sec, aSec, eSec) and preimage resistance (Pre, aPre, ePre). The main contribution of this paper is in determining, by proof or counterexample, which of these seven notions is preserved by each of eleven existing iterations. Our study points out that none of them preserves more than three notions from [RSh04]. In particular, only a single iteration preserves Pre, and none preserves Sec, aSec, or aPre. The latter two notions are particularly relevant for practice, because they do not rely on the problematic assumption that practical compression functions be chosen uniformly from a family. In view of this poor state of affairs, even the mere existence of seven-property-preserving iterations seems uncertain. As a second contribution, we propose the new Random-Oracle XOR(ROX) iteration that is the first to provably preserve all seven notions, but that, quite controversially, uses a random oracle in the iteration. The compression function itself is not modeled as a random oracle though. Rather, ROX uses an auxiliary small-input random oracle (typically 170 bits) that is called only a logarithmic number of times.

Consider the Jacobian of a genus two curve defined over a finite field and with complex multiplication. In this paper we show that if the l-Sylow subgroup of the Jacobian is not cyclic, then the embedding degree of the Jacobian with respect to l is one.

Let $k=\mathbb{F}_q$ be a finite field of odd characteristic. We find a closed formula for the number of $k$-isomorphism classes of pointed, and non-pointed, hyperelliptic curves of genus $g$ over $k$, admitting a Koblitz model. These numbers are expressed as a polynomial in $q$ with integer coefficients (for pointed curves) and rational coefficients (for non-pointed curves). The coefficients depend on $g$ and the set of divisors of $q-1$ and $q+1$. These formulas show that the number of hyperelliptic curves of genus $g$ suitable (in principle) of cryptographic applications is asymptotically $(1-e^{-1})2q^{2g-1}$, and not $2q^{2g-1}$ as it was believed. The curves of genus $g=2$ and $g=3$ are more resistant to the attacks to the DLP; for these values of $g$ the number of curves is respectively $(91/72)q^3+O(q^2)$ and $(3641/2880)q^5+O(q^4)$.

Generalized signcryption which proposed by Han is a new cryptographic primitive which can work as an encryption scheme, a signature scheme or a signcryption scheme[5]. However,the security proof in their paper is not very formal.our contribution are as following:First we give security notions for this new primitive.Secnond,we give an attack to [4]which is the first vision of [5] and propose an improved generalized signcryption scheme. Third, we give new very formal proofs for this new scheme.

With computer networks spreading into a variety of new environments, the need to authenticate and secure communication grows. Many of these new environments have particular requirements on the applicable cryptographic primitives. For instance, several applications require that communication overhead be small and that many messages be processed at the same time. In this paper we consider the suitability of public key signatures in the latter scenario. That is, we consider signatures that are 1) short and 2) where many signatures from (possibly) different signers on (possibly) different messages can be verified quickly. Prior work focused almost exclusively on batching signatures from the same signer. We propose the first batch verifier for messages from many (certified) signers without random oracles and with a verification time where the dominant operation is independent of the number of signatures to verify. We further propose a new signature scheme with very short signatures, for which batch verification for many signers is also highly efficient. Combining our new signatures with the best known techniques for batching certificates from the same authority, we get a fast batch verifier for certificates and messages combined. Although our new signature scheme has some restrictions, it is very efficient and still practical for some communication applications.

In a proxy re-encryption (PRE) scheme, a proxy is given special information that allows it to translate a ciphertext under one key into a ciphertext of the same message under a different key. The proxy cannot, however, learn anything about the messages encrypted under either key. PRE schemes have many practical applications, including distributed storage, email, and DRM. Previously proposed re-encryption schemes achieved only semantic security; in contrast, applications often require security against chosen ciphertext attacks. We propose a definition of security against chosen ciphertext attacks for PRE schemes, and present a scheme that satisfies the definition. Our construction is efficient and based only on the Decisional Bilinear Diffie-Hellman assumption in the standard model. We also formally capture CCA security for PRE schemes via both a game-based definition and simulation-based definitions that guarantee universally composable security. We note that, simultaneously with our work, Green and Ateniese proposed a CCA-secure PRE, discussed herein.

With Radio Frequency Identification (RFID) tags being used to secure contactless credit cards, great benefits but also serious security and information privacy issues have arisen. Recently many attempts have been made to resolve these issues. In particular, attempts have been made to provide a means for authentication between tag and reader. However, none have yet have been able to provide resistance to cloning attacks. Furthermore, authentication on lowest range of low-cost RFID tags, also remains a challenge. We propose a clone resistant, mutual authentication scheme that requires only 32 bits of read write memory, 90 bits of read only memory and can be deployed using as few as 300 logic gates. We also propose a stream cipher with the same memory constraints and magnitude of logic gates. These systems may also be scaled to provide a high level of security, using relatively little computational resources, on larger hardware platforms.

We investigate the security of protocols with logarithmic communication complexity. We show that for the security definitions with environment, i.e., Reactive Simulatability and Universal Composability, computational security of logarithmic protocols implies statistical security. The same holds for advantage-based security definitions as commonly used for individual primitives. While this matches the folklore that logarithmic protocols cannot be computationally secure unless they are already statistically secure, we show that under realistic complexity assumptions, this folklore does surprisingly not hold for the stand-alone model without auxiliary input, i.e., there are logarithmic protocols that are statistically insecure but computationally secure in this model. The proof is conducted by showing how to transform an instance of an NP-complete problem into a protocol with two properties: There exists an adversary such that the protocol is statistically insecure in the stand-alone model, and given such an adversary we can find a witness for the problem instance, hence yielding a computationally secure protocol assuming the hardness of finding a witness. The proof relies on a novel technique that establishes a link between cryptographic definitions and foundations of computational geometry, which we consider of independent interest.

We introduce a variant of the random oracle model where oracle-dependent auxiliary input is allowed. In this setting, the adversary gets an auxiliary input that can contain information about the random oracle. Using simple examples we show that this model should be preferred over the classical variant where the auxiliary input is independent of the random oracle. In the presence of oracle-dependent auxiliary input, the most important proof technique in the random oracle model - lazy sampling - does not apply directly. We present a theorem and a variant of the lazy sampling technique that allows one to perform proofs in the new model almost as easily as in the old one. As an application of our approach and to illustrate how existing proofs can be adapted, we prove that RSA-OAEP is IND-CCA2 secure in the random oracle model with oracle-dependent auxiliary input.

In this paper we propose two public key BE schemes that have efficient complexity measures. The first scheme, called the PBE-PI scheme, has $O(r)$ header size, $O(1)$ public keys and $O(\log N)$ private keys per user, where $r$ is the number of revoked users. This is the first public key BE scheme that has both public and private keys under $O(\log N)$ while the header size is $O(r)$. These complexity measures match those of efficient secret key BE schemes. \par Our second scheme, called the PBE-SD-PI scheme, has $O(r)$ header size, $O(1)$ public key and $O(\log N)$ private keys per user also. However, its decryption time is remarkably $O(1)$. This is the first public key BE scheme that has $O(1)$ decryption time while other complexity measures are kept low. Overall, this is the most efficient public key BE scheme up to now. \par Our basic schemes are one-way secure against {\em full collusion of revoked users} in the random oracle model under the BDH assumption. We modify our schemes to have indistinguishably security against adaptive chosen ciphertext attacks.

Group key exchange protocols allow a group of parties communicating over a public network to come up with a common secret key called a session key. Due to their critical role in building secure multicast channels, a number of group key exchange protocols have been suggested over the years for a variety of settings. Among these is the so-called EKE-M protocol proposed by Byun and Lee for password-based group key exchange in the different password authentication model, where group members are assumed to hold an individual password rather than a common password. While the announcement of the EKE-M protocol was essential in the light of the practical significance of the different password authentication model, Tang and Chen showed that the EKE-M protocol itself suffers from an undetectable on-line dictionary attack. Given Tang and Chen's attack, Byun et al.~have recently suggested a modification to the EKE-M protocol and claimed that their modification makes EKE-M resistant to the attack. However, the claim turned out to be untrue. In the current paper, we demonstrate this by showing that Byun et al.'s modified EKE-M is still vulnerable to an undetectable on-line dictionary attack. Besides reporting our attack, we also figure out what has gone wrong with Byun et al.'s modification and how to fix it.

We investigate inductive methods for proving secrecy properties of network protocols, in a ``computational" setting applying a probabilistic polynomial-time adversary. As in cryptographic studies, our secrecy properties assert that no probabilistic polynomial-time distinguisher can win a suitable game presented by a challenger. Our method for establishing secrecy properties uses inductive proofs of computational trace-based properties, and axioms and inference rules for relating trace-based properties to non-trace-based properties. We illustrate the method, which is formalized in a logical setting that does not require explicit reasoning about computational complexity, probability, or the possible actions of the attacker, by giving a modular proof of computational authentication and secrecy properties of the Kerberos V5 protocol.

MicroArchitectural Attacks (MA), which can be considered as a special form of Side-Channel Analysis, exploit microarchitectural functionalities of processor implementations and can compromise the security of computational environments even in the presence of sophisticated protection mechanisms like virtualization and sandboxing. This newly evolving research area has attracted significant interest due to the broad application range and the potentials of these attacks. Cache Analysis and Branch Prediction Analysis were the only types of MA that had been known publicly. In this paper, we introduce Instruction Cache (I-Cache) as yet another source of MA and present our experimental results which clearly prove the practicality and danger of I-Cache Attacks.

In 2003, Boyd et al. have proposed two deniable authenticated key establishment protocols for Internet Key Exchange (IKE). However, both schemes have been broken by Chou et al. in 2005 due to their susceptibility to key-compromise impersonation (KCI) attack. In this paper, we put forward the improved variants of both Boyd et al.'s schemes in order to defeat the KCI attack. On top of justifying our improvements, we further present a detailed security analysis to ensure that the desired security attributes: deniability and authenticity remain preserved.

It is debatable if current direct-recording electronic voting machines can sufficiently be trusted for a use in elections. Reports about malfunctions and possible ways of manipulation abound. Voting schemes have to fulfill seemingly contradictory requirements: On one hand the election process should be verifiable to prevent electoral fraud and on the other hand each vote should be deniable to avoid coercion and vote buying. This work presents a new verifiable and coercion-free voting scheme Bingo Voting, which is based on a trusted random number generator. As a motivation for the new scheme two coercion/vote buying attacks on voting schemes are presented which show that it can be dangerous to let the voter contribute randomness to the voting scheme. A proof-of-concept implementation of the scheme shows the practicality of the scheme: all costly computations can be moved to a non time critical pre-voting phase.

This paper illustrates the use of ciphertext-policy attribute-based encryption (CP-ABE), a recently proposed primitive, in the setting of group key management. Specifically, we use the CP-ABE scheme of Bethencourt, Sahai and Waters to implement flat table group key management. Unlike past implementations of flat table, our proposal is resistant to collusion attacks. We also provide efficient mechanisms to refresh user secret keys (for perfect forward secrecy) and to delegate managerial duties to subgroup controllers (for scalability). Finally, we discuss performance issues and directions for future research.

Recently, Tanaka proposed an identity based non-interactive key sharing scheme and its corresponding identity based encryption scheme based on the intractability of integer factorization and discrete logarithm. The proposed identity based non-interactive key sharing scheme is similar to the well-known Maurer-Yacobi public key distribution scheme but the computational complexity for private key generation can be significantly reduced. It is also claimed that the proposed identity based non-interactive key sharing scheme is "collusion-attack free", i.e., secure against collusion attacks. In this paper, we analyze the security of the "collusion-attack free" identity based non-interactive key sharing scheme. First, we show that, without colluding with other users, a single user can recover some of the secret information of the private key generator. Then we show that a small group of users can collude to recover all of the secret information held by the private key generator. Thus, the "collusion-attack free" identity based non-interactive key sharing scheme can be completely compromised by collusion attacks.

An Attribute Based Group Signature (ABGS) allows a verifier to request a signature from a member of a group who possesses certain attributes. Therefore, a signature should authenticate a person in a group and prove ownership of certain properties. The major difference between our scheme and previous group signatures, is that the verifier can determine the role of the actual signer within the group. In this paper we define the first ABGS scheme, and security notions such as anonymity and traceability. We then construct the scheme and prove it secure.

In Crypto 2001, Bellare {\em et al.} introduced {\em online cipher} (or online permutation) and proposed two Hash-CBC mode constructions, namely {\bf HCBC} and {\bf HPCBC} along with security proofs. We observe that, the security proofs in their paper are {\em wrong} and it may not be fixed easily. In this paper, we provide a {\em simple} security analysis of these online ciphers. Moreover, we propose two variants of HPCBC, namely {\bf MHCBC-1} and {\bf MHCBC-2}. The first variant, MHCBC-1, is a slight modification of HPCBC so that it is more efficient in performance as well as in memory compare to HPCBC. The other one, MHCBC-2 requires only {\em one-key} (note that, HCBC and HPCBC require at least two and three keys respectively) and does not require any $\varepsilon$-$\mathrm{\Delta}$Universal Hash Family (which is costly in general).

We present an experimental block cipher, ConSum, based on a hitherto unstudied design element: the Conway transformation. ConSum features an extremely simple design and the ability to operate with arbitrary key lengths, block sizes and round numbers. We study it empirically and statistically so as to illustrate how it might be secure.

This paper is concerned about relating formal and computational models of cryptography in case of active adversaries when formal security analysis is done with first order logic. We first present a criticism of the way Datta et al. defined computational semantics to their Protocol Composition Logic, concluding that problems arise from focusing on occurrences of bit-strings on individual traces instead of occurrences of probability distributions of bit-strings across the distribution of traces. We therefore introduce a new, fully probabilistic method to assign computational semantics to the syntax. We present this via considering a simple example of such a formal model, the Basic Protocol Logic of K. Hasebe and M. Okada, but the technique is suitable for extensions to more complex situations such as PCL. The idea is to make use of the usual mathematical treatment of stochastic processes, hence be able to treat arbitrary probability distributions, non-negligible probability of collision, causal dependence or independence.

Non-interactive zero-knowledge proofs and non-interactive witness-indistinguishable proofs have played a significant role in the theory of cryptography. However, lack of efficiency has prevented them from being used in practice. One of the roots of this inefficiency is that non-interactive zero-knowledge proofs have been constructed for general NP-complete languages such as Circuit Satisfiability, causing an expensive blowup in the size of the statement when reducing it to a circuit. The contribution of this paper is a general methodology for constructing very simple and efficient non-interactive zero-knowledge proofs and non-interactive witness-indistinguishable proofs that work directly for groups with a bilinear map, without needing a reduction to Circuit Satisfiability. Groups with bilinear maps have enjoyed tremendous success in the field of cryptography in recent years and have been used to construct a plethora of protocols. This paper provides non-interactive witness-indistinguishable proofs and non-interactive zero-knowledge proofs that can be used in connection with these protocols. Our goal is to spread the use of non-interactive cryptographic proofs from mainly theoretical purposes to the large class of practical cryptographic protocols based on bilinear groups.

We have designed three fast implementations of recently proposed family of hash functions Edon--${\cal R}$. They produce message digests of length 256, 384 and 512 bits. We have defined huge quasigroups of orders $2^{256}$, $2^{384}$ and $2^{512}$ by using only bitwise operations on 32 bit values (additions modulo $2^{32}$, XORs and left rotations) and achieved processing speeds of the Reference C code of 16.18 cycles/byte, 24.37 cycles/byte and 32.18 cycles/byte on x86 (Intel and AMD microprocessors). In this paper we give their full description, as well as an initial security analysis.

We investigate the decoding problem of Reed-Solomon (RS) Codes, also known as the Polynomial Reconstruction Problem (PR), from a cryptographic hardness perspective. Namely, we deal with PR instances with parameter choices for which decoding is not known to be feasibly solvable and where part of the solution polynomial is the hidden input. We put forth a natural decisional intractability assumption that relates to this decoding problem: distinguishing between a single randomly chosen error-location and a single randomly chosen non-error location for a given corrupted RS codeword with random noise. We prove that under this assumption, PR-instances are entirely pseudorandom, i.e., they are indistinguishable from random vectors over the underlying finite field. Moreover, under the same assumption we show that it is hard to extract any partial information related to the hidden input encoded by the corrupted PR-instance, i.e., PR-instances hide their message polynomial solution in the semantic security sense. The above results lay a framework for the exploitation of PR as an intractability assumption for provable security of cryptographic primitives. Based on this framework, we present provably secure cryptographic constructions for (i) a pseudorandom extender, (ii) a semantically secure version of the Oblivious Polynomial Evaluation Protocol, and (iii) a stateful cipher with a set of interesting properties that include: semantic security, forward secrecy, error-correcting decryption and an array of random self-reducibility properties with respect to the plaintext choice, key choice and partial domain choice.

The cipher CTC (Courtois Toy Cipher) has been designed to demonstrate that it is possible to break on a PC a block cipher with good diffusion and very small number of known (or chosen) plaintexts. It has however never been designed to withstand all known attacks on block ciphers and Dunkelman and Keller have shown that a few bits of the key can be recovered by Linear Cryptanalysis (LC) - which cannot however compromise the security of a large key. This weakness can easily be avoided: in this paper we give a specification of CTC2, a tweaked version of CTC. The new cipher is MUCH more secure than CTC against LC and the key scheduling of CTC has been extended to use any key size, independently from the block size. Otherwise, there is little difference between CTC and CTC2. We will show that up to 10 rounds of CTC2 can be broken by simple algebraic attacks.

Motivated by the challenging task of designing ``secure'' vote storage mechanisms, we study information storage mechanisms that operate in extremely hostile environments. In such environments, the majority of existing techniques for information storage and for security are susceptible to powerful adversarial attacks. We propose a mechanism for storing a set of at most $K$ elements from a large universe of size $N$ on write-once memories in a manner that does not reveal the insertion order of the elements. We consider a standard model for write-once memories, in which the memory is initialized to the all $0$'s state, and the only operation allowed is flipping bits from $0$ to $1$. Whereas previously known constructions were either inefficient (required $\Theta(K^2)$ memory), randomized, or employed cryptographic techniques which are unlikely to be available in hostile environments, we eliminate each of these undesirable properties. The total amount of memory used by the mechanism is linear in the number of stored elements and poly-logarithmic in the size of the universe of elements. We also demonstrate a connection between secure vote storage mechanisms and one of the classical distributed computing problems: conflict resolution in multiple-access channels. By establishing a tight connection with the basic building block of our mechanism, we construct the first deterministic and non-adaptive conflict resolution algorithm whose running time is optimal up to poly-logarithmic factors.

This paper provides a probabilistic algorithm to determine generators of the m-torsion subgroup of the Jacobian of a hyperelliptic curve of genus two.

Braid cryptosystem was proposed in CRYPTO 2000 as an alternate public-key cryptosystem. The security of this system is based upon the conjugacy problem in braid groups. Since then, there have been several attempts to break the braid cryptosystem by solving the conjugacy problem in braid groups. In this paper, we first survey all the major attacks on the braid cryptosystem and conclude that the attacks were successful because the current ways of random key generation almost always result in weaker instances of the conjugacy problem. We then propose several alternate ways of generating hard instances of the conjugacy problem for use braid cryptography.

Compact e-cash schemes allow a user to withdraw a wallet containing $k$ coins in a single operation, each of which the user can spend unlinkably. One big open problem for compact e-cash is to allow multiple denominations of coins to be spent efficiently without executing the spend protocol a number of times. In this paper, we give a (\emph{partial}) solution to this open problem by introducing two additional protocols, namely, compact spending and batch spending. Compact spending allows spending all the $k$ coins in one operation while batch spending allows spending any number of coins in the wallet in a single execution. We modify the security model of compact e-cash to accommodate these added protocols and present a generic construction. While the spending and compact spending protocol are of constant time and space complexities, complexities of batch spending is linear in the number of coins to be spent together. Thus, we regard our solution to the open problem as {\it partial}. We provide two instantiations under the $q$-SDH assumption and the LRSW assumption respectively and present security arguments for both instantiations in the random oracle model.

There are several public key establishment protocols as well as complete public key cryptosystems based on allegedly hard problems from combinatorial (semi)group theory known by now. Most of these problems are search problems, i.e., they are of the following nature: given a property P and the information that there are objects with the property P, find at least one particular object with the property P. So far, no cryptographic protocol based on a search problem in a non-commutative (semi)group has been recognized as secure enough to be a viable alternative to established protocols (such as RSA) based on commutative (semi)groups, although most of these protocols are more efficient than RSA is. In this paper, we suggest to use decision problems from combinatorial group theory as the core of a public key establishment protocol or a public key cryptosystem. By using a popular decision problem, the word problem, we design a cryptosystem with the following features: (1) Bob transmits to Alice an encrypted binary sequence which Alice decrypts correctly with probability "very close" to 1; (2) the adversary, Eve, who is granted arbitrarily high (but fixed) computational speed, cannot positively identify (at least, in theory), by using a "brute force attack", the "1" or "0" bits in Bob's binary sequence. In other words: no matter what computational speed we grant Eve at the outset, there is no guarantee that her "brute force attack" program will give a conclusive answer (or an answer which is correct with overwhelming probability) about any bit in Bob's sequence.

Time Capsule Signature, first formalized by Dodis and Yum in Financial Cryptography 2005, is a digital signature scheme which allows a signature to bear a (future) time t so that the signature will only be valid at time t or later, when a trusted third party called time server releases time-dependent information for checking the validity of a time capsule signature. Also, the actual signer of a time capsule signature has the privilege to make the signature valid before time t. In this paper, we provide a new security model of time capsule signature such that time server is not required to be fully trusted. Moreover, we provide two e±cient constructions in random oracle model and standard model. Our improved security model and proven secure constructions have the potential to build some new E-Commerce applications.

We study the round complexity of various cryptographic protocols. Our main result is a tight lower bound on the round complexity of any fully-black-box construction of a statistically-hiding commitment scheme from one-way permutations, and even from trapdoor permutations. This lower bound matches the round complexity of the statistically-hiding commitment scheme due to Naor, Ostrovsky, Venkatesan and Yung (CRYPTO '92). As a corollary, we derive similar tight lower bounds for several other cryptographic protocols, such as single-server private information retrieval, interactive hashing, and oblivious transfer that guarantees statistical security for one of the parties. Our techniques extend the collision-finding oracle due to Simon (EUROCRYPT '98) to the setting of interactive protocols (our extension also implies an alternative proof for the main property of the original oracle). In addition, we substantially extend the reconstruction paradigm of Gennaro and Trevisan (FOCS '00). In both cases, our extensions are quite delicate and may be found useful in proving additional black-box separation results.

We will review the past history of the attacks and defenses of TTM. The main tool of the past attacks is linear algebra, while the defenses rely on algebraic geometry and commutative algebra. It is hard for attackers to completely succeed against the formidable castle of modern mathematics. It is out of the common sense that problems of algebraic geometry can always be solved by linear algebra. It repeatly happens that the attackers find some points which could be exploited by linear algebra using complicated computations, usually the attackers overexaggerate the power of linear algebra and illusional believe that they succeed totally, then the points are disappearing by a simple twist in algebraic geometry and commutative algebra. All attacks in the past simply strengthen the structures of TTM. For these facts we are very grateful to the attackers. Last year there is a paper entitled "{\it Breaking a New Instance of TTM Cryptosystem}" by Xuyun Nie, Lei Hu, Jianyu Li, Crystal Updegrove and Jintai Ding [11] claiming a successive attack on the scheme of TTM presented in [7]. In our previous article [8], we show that their claim is a {\bf misunderstanding}. The discussions of [11] and [8] center on if in [11] the authors really just use the {\it public keys}. Right aft er we post [8], to settle the discrepancy of [11] and [8], we have sent the public keys of a new example (which is attached as the {\bf Appendix I} of this article) to the authors of [11] to test their claim in the {\it abstract} of [11], i.e., they will be able to crack TTM using only the public keys (in 20 minutes as stated in the abstract of [11]). After two weeks, Mr Nie asks the private keys of the new example for his {\it theoretical analysis} and we will consider his request only if he concedes that he is unable to crack the new example by the method of [11]. Since there is no definite answer from them after 4 months, we will publish the example in this article to give other people chances to attack. Furthermore, we publish a second example as {\bf Appendix II}.

We introduce an offline precomputation technique for mix-nets that drastically reduces the amount of online computation needed. Our method can be based on any additively homomorphic cryptosystem and is applicable when the number of senders and the maximal bit-size of messages are relatively small.

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 data confidentiality and integrity. Since Joux proposed the first pairing-based one-round tripartite key agreement protocol in 2000, numerous authenticated protocols have been proposed after then. However, most of them have turned out to be flawed due to their inability in achieving some desirable security attributes. In 2005, Lin-Li had identified the weaknesses of Shim's protocol and subsequently proposed their improved scheme by introducing an extra verification process. In this paper, we prove that Lin-Li's improved scheme remains insecure due to its susceptibility to the insider impersonation attack. Based on this, we propose an enhanced scheme which will not only conquer their defects, but also preserves the desired security attributes of a key agreement protocol.

In this paper, we present a practical attack on the signature scheme SFLASH proposed by Patarin, Goubin and Courtois in 2001 following a design they had introduced in 1998. The attack only needs the public key and requires about one second to forge a signature for any message, after a one-time computation of several minutes. It can be applied to both SFLASHv2 which was accepted by NESSIE, as well as to SFLASHv3 which is a higher security version.

This paper introduces Hidden Identity-based Signatures (Hidden-IBS), a type of digital signatures that provide mediated signer-anonymity on top of Shamir's Identity-based signatures. The motivation of our new signature primitive is to resolve an important issue with the kind of anonymity offered by ``group signatures'' where it is required that either the group membership list is {\em public} or that the opening authority is {\em dependent} on the group manager for its operation. Contrary to this, Hidden-IBS do not require the maintenance of a group membership list and they enable an opening authority that is totally independent of the group manager. As we argue this makes Hidden-IBS much more attractive than group signatures for a number of applications. In this paper, we provide a formal model of Hidden-IBS as well as two efficient constructions that realize the new primitive. Our elliptic curve construction that is based on the SDH/DLDH assumptions produces signatures that are merely half a Kbyte long and can be implemented very efficiently. To demonstrate the power of the new primitive, we apply it to solve a problem of current onion-routing systems focusing on the Tor system in particular. Posting through Tor is currently blocked by sites such as Wikipedia due to the real concern that anonymous channels can be used to vandalize online content. By injecting a Hidden-IBS inside the header of an HTTP POST request and requiring the exit-policy of Tor to forward only properly signed POST requests, we demonstrate how sites like Wikipedia may allow anonymous posting while being ensured that the recovery of (say) the IP address of a vandal would be still possible through a dispute resolution system. Using our new Hidden-IBS primitive in this scenario allows to keep the listing of identities (e.g., IP addresses) of Tor users computationally hidden while maintaining an independent Opening Authority which would not have been possible with previous approaches.

Evidences of delivery are essential for resolving (and avoiding) disputes on delivery of messages, in classical as well as electronic commerce. We present the first rigorous specifications and provably-secure implementation, for a communication layer providing time-stamped evidences for the message delivery process. This improves on existing standards for evidences (‘non-repudiation’) services, based on informal specifications and unproven designs. Our work also improves on the large body of analytical works on tasks related to evidences of delivery, such as certified mail/delivery protocols and fair exchange (of signatures). We improve by addressing practical needs and scenarios, using realistic synchronization and communication assumptions, supporting time-outs and failures, and providing well-defined interface to the higher-layer protocols (application). Furthermore, we use the layered specifications framework, allowing provably-secure use of our protocol, with lower and higher layer protocols, with complete re-use of our analysis (theorems).

In this paper, a method for the efficient computation of Tate pairings on curves which is a generalization of Barreto, etc.'s method [2] is presented. It can reduce the number of loops in the computation of the Tate pairing. The method can be applied not only to supersingular curves but to non-supersingular curves. An example shows the cost of the algorithm in this paper can be reduced by 18% than the best known algorithm in some elliptic curves.

We propose the idea of building a secure hash using quadratic or higher degree multivariate polynomials over a finite field as the compression function, whose security relies on simple hard questions. We analyze some security properties and potential feasibility, where the compression functions are randomly chosen high-degree polynomials. Next, we propose to improve on the efficiency of the system by using some specially designed polynomials using composition of maps and certain sparsity property, where the security of the system would then relies on stronger assumptions.

In this paper we propose a new class of Fair Exchange Signature Scheme(FESS) that allows two players to exchange digital signatures in a fair way. Our signature scheme is a general idea and has various implementations on most of the existing signature schemes, thus it may also be considered as an interesting extension of concurrent signature presented in EUROCRYPT 2004 that is constructed from ring signatures. In our scheme, two unwakened signatures signed separately by two participants can be verified easily by the other player, but it would not go into effect until an extra piece of commitment keystone is released by one of the players. Once the keystone revealed, two signatures are both aroused and become effective. A key feature of the proposed scheme is that two players can exchange digital signatures simultaneously through a secret commitment keystone without involvement of any Trusted Third Party. Moreover, the efficiency of our signature scheme is higher than that of concurrent signature.

In this paper, we introduce the exact concept of ID-based signature without trusted Private Key Generator (PKG), which solves the key escrow problem through binding two partially public keys with a same identity. In this scheme, PKG is prevented from forging a legal user’s signature because he only generates the partially private key. Using Gap Diffie-Hellman (GDH) groups, we construct an efficient ID-based signature scheme without trusted PKG, which security relies on the hardness of the Computation Diffie-Hellman Problem (CDHP). More precisely, under the random oracle model, our scheme is proved to be secure against existential forgery on adaptively chosen message and ID attack, which is a natural ID-based version of the standard adaptively chosen message attack, assuming CDHP is intractable. Our scheme not only eliminates the inherent key escrow problem but also has a higher efficiency than the existing schemes.

The threshold voltage VT of EEPROM cells is a very important technological parameter for storing data and keys in a cryptographic device like smartcards. Furthermore, main objective of this paper is to check whether it is possible to get the key stored in the EEPROM cell through measuring the current consumption of the cryptographic device during read key command for encryption before and after baking at a certain temperature. This stress (baking) of the charge in the floating gate of the cells shifts the threshold voltage. Especially this effect will be considered whether the unknown key in the EEPROM cells can be estimated by using the charge shift in the floating gate. The test labs might need to check during an evaluation procedure of the smartcards if parts or whole key can be estimated successfully by stressing the threshold parameter VT. The result of this evaluation is (will be) an input for countermeasures against possible attacks. It is also an additional input for further design structures in order to avoid information gain after baking the EEPROM cells at a certain temperature.

We construct two simple families of two-message $(n,1)$-oblivious transfer protocols based on degree-$t$ homomorphic cryptosystems with the communication of respectively $1+\lceil n/t \rceil$ and $3+\lceil n/(t+1) \rceil$ ciphertexts. The construction of both families relies on efficient cryptocomputable conditional disclosure of secret protocols; the way this is done may be of independent interest. The currently most interesting case $t=2$ can be based on the Boneh-Goh-Nissim cryptosystem. As an important application, we show how to reduce the communication of virtually any existing oblivious transfer protocols by proposing a new related communication-efficient generic transformation from computationally-private information retrieval protocols to oblivious transfer protocols.

We study the design of practical blind signatures in the universal composability (UC) setting against adaptive adversaries. We introduce a new property for blind signature schemes that is fundamental for managing adaptive adversaries: an {\em equivocal blind signature} is a blind signature protocol where a simulator can construct the internal state of the client so that it matches a simulated transcript even after a signature was released. % We present a general construction methodology for building practical adaptively secure blind signatures: the starting point is a 2-move ``lite blind signature'', a lightweight 2-party signature protocol that we formalize and implement both generically as well as number theoretically: formalizing a primitive as ``lite'' means that the adversary is required to show all private tapes of adversarially controlled parties; this enables us to conveniently separate zero-knowledge (ZK) related security requirements from the remaining security properties in the primitive's design methodology. % We then focus on the exact ZK requirements for building blind signatures. To this effect, we formalize two special ZK ideal functionalities, single-verifier-ZK (SVZK) and single-prover-ZK (SPZK) and we investigate the requirements for realizing them in a commit-and-prove fashion as building blocks for adaptively secure UC blind signatures. SVZK can be realized without relying on a multi-session UC commitment; as a result, we realize SVZK in a very efficient manner using number theoretic mixed commitments while employing a constant size common reference string and without the need to satisfy non-malleability. Regarding SPZK we find the rather surprising result that realizing it only for static adversaries is sufficient to obtain adaptive security for UC blind signatures. This important observation simplifies blind signature design substantially as one can realize SPZK very efficiently in a commit-and-prove fashion using merely an extractable commitment. We instantiate all the building blocks of our design methodology efficiently thus presenting the first practical UC blind signature that is secure against adaptive adversaries in the common reference string model. In particular, we present (1) a lite equivocal blind signature protocol that is based on elliptic curves and the 2SDH assumption of Okamoto, (2) efficient implementations of SPZK, SVZK for the required relations. % Our construction also takes advantage of a round optimization method we discuss and it results in a protocol that has an overall communication overhead of as little as 3Kbytes, employing six communication moves and a constant length common reference string. We also present alternative implementations for our equivocal lite blind signature thus demonstrating the generality of our approach. Finally we count the exact cost of realizing blind signatures with our protocol design by presenting the distance between the $\Fbsig$-hybrid world and the $\Fcrs$-hybrid world as a function of environment parameters. The distance calculation is facilitated by a basic lemma we prove about structuring UC proofs that may be of independent interest.

We present a new non-interactive message authentication protocol in manual channel model (NIMAP, for short) using the weakest assumption on the manual channel (i.e. assuming the strongest adversary). Our protocol uses enhanced target collision resistant (eTCR) hash family and is provably secure in the standard model. We compare our protocol with protocols with similar properties and show that the new NIMAP has the same security level as the best previously known NIMAP whilst it is more practical. In particular, to authenticate a message such as a 1024-bit public key, we require an eTCR hash family that can be constructed from any off-the-shelf Merkle-Damgård hash function using randomized hashing mode. The underlying compression function must be {\em evaluated second preimage resistant} (eSPR), which is a strictly weaker security property than collision resistance. We also revisit some closely related security notions for hash functions and study their relationships to help understanding our protocol.

Anonymity(key-privacy) as well as security(data-privacy) are all important features in public-key encryption applications. In this paper two new and general concepts, named “relevant anonymity” and “relevant security”, are defined. Based-upon these concepts some general results on anonymity in public-key encryption are proved, which fall in three categories. The first results are two general relationships between anonymity and security; the second are a sufficient and necessary condition for chosen-plaintext anonymity in Fujisaki-Okamoto hybrid construction and a sufficient condition for its chosen-ciphertext anonymity; the third is a sufficient condition for chosen-ciphertext anonymity in Okamoto-Pointcheval hybrid construction (REACT). All these conditions are also easy-to-use criteria in practice. By examples such general consequences are applied to some specific schemes and as a result anonymity of some well-known schemes are re-established in a simpler way. Furthermore, NISSIE scheme PSEC-/1/2/3’s chosen-ciphertext anonymity are proved.

Trivium is a stream cipher candidate of the eStream project. It has successfully moved into phase three of the selection process under the hardware category. No attacks faster than the exhaustive search have so far been reported on Trivium. Bivium-A and Bivium-B are simplified versions of Trivium that are built on the same design principles but with two registers. The simplified design is useful in investigating Trivium type ciphers with a reduced complexity and provides insight into effective attacks which could be extended to Trivium. This paper focuses on an algebraic analysis which uses the boolean satisfiability problem in propositional logic. For reduced variants of the cipher, this analysis recovers the internal state with a minimal amount of keystream observations.

We present a new mechanized prover for showing correspondence assertions for cryptographic protocols in the computational model. Correspondence assertions are useful in particular for establishing authentication. Our technique produces proofs by sequences of games, as standard in cryptography. These proofs are valid for a number of sessions polynomial in the security parameter, in the presence of an active adversary. Our technique can handle a wide variety of cryptographic primitives, including shared- and public-key encryption, signatures, message authentication codes, and hash functions. It has been implemented in the tool CryptoVerif and successfully tested on examples from the literature.

In a threshold broadcast encryption scheme, a sender chooses (ad-hoc) a set of $n$ receivers and a threshold $t$, and then encrypts a message by using the public keys of all the receivers, in such a way that the original plaintext can be recovered only if at least $t$ receivers cooperate. Previously proposed threshold broadcast encryption schemes have ciphertexts whose length is $\O(n)$. In this paper, we propose new schemes, for both PKI and identity-based scenarios, where the ciphertexts' length is $\O(n-t)$. The construction uses secret sharing techniques and the Canetti-Halevi-Katz transformation to achieve chosen-ciphertext security. The security of our schemes is formally proved under the Decisional Bilinear Diffie-Hellman (DBDH) Assumption.

We propose an interesting efficient member ID-based group signatures, i.e., verification of output from algorithm OPEN run by the group manager does not have to refer to a registration table (acting as certification list). The proposal is free of GM-frameability, i.e., secret key of member is not escrowed to GM, which is unique among all known member ID-based group signatures as far as we know. The proposal also has two distinguished extra features, one is that the group manager does not have to maintain a registration table to obtain the real identity of the signer in contrast to other schemes, another is that it provides an alternative countermeasure against tampered registration table to applying integrity techniques to the table in case registration table is maintained.

At Eurocrypt 2006, Paterson and Yau demonstrated how flaws in the Linux implementation of IPsec could be exploited to break encryption-only configurations of ESP, the IPsec encryption protocol. Their work highlighted the dangers of not using authenticated encryption in fielded systems, but did not constitute an attack on the actual IPsec standards themselves; in fact, the attacks of Paterson and Yau should be prevented by any standards-compliant IPsec implementation. In contrast, this paper describes new attacks which break any RFC-compliant implementation of IPsec making use of encryption-only ESP. The new attacks are both efficient and realistic: they are ciphertext-only and need only the capability to eavesdrop on ESP-encrypted traffic and to inject traffic into the network. The paper also reports our experiences in applying the attacks to a variety of implementations of IPsec, and reflects on what these experiences tell us about how security standards should be written so as to simplify the task of software developers.

VEST is a set of four stream cipher families targeted to semiconductor applications. All VEST family members support efficient encryption, single pass authenticated encryption, and collision resistant hashing in the one low area module. VEST was submitted by Synaptic Laboratories to the ECRYPT NoE eSTREAM project in 2005. Recently, a single digit typographical error was identified in the VEST counter diffuser description. Shortly afterwards Antoine Joux and Jean-René Reinhard published collisions in the counter-diffuser based upon the erroneous description. By extending these collisions across the entire cipher state, they were able to explore various attack scenarios. We prove that the correction of the typographical error removes all the exploitable collisions in the counter diffuser during key and IV loading operations; thereby establishing that the Joux-Reinhard attacks are an artefact of the erroneous description. Complete test vectors are included.

LaMacchia, Lauter and Mityagin recently presented a strong security definition for authenticated key agreement strengthening the well-known Canetti-Krawczyk definition. They also described a protocol, called NAXOS, that enjoys a simple security proof in the new model. Compared to MQV and HMQV, NAXOS is less efficient and cannot be readily modified to obtain a one-pass protocol. On the other hand MQV does not have a security proof, and the HMQV security proof is extremely complicated. This paper proposes a new authenticated key agreement protocol, called CMQV (`Combined' MQV), which incorporates design principles from MQV, HMQV and NAXOS. The new protocol achieves the efficiency of HMQV and admits a natural one-pass variant. Moreover, we present a simple and intuitive proof that CMQV is secure in the LaMacchia-Lauter-Mityagin model.

In this paper we investigate the security properties of three versions of the WAI protocol in Chinese WLAN implementation plan. We first revisit the security analysis that has been done to the version 1 and 2. we show that the security proof given by Li, Moon, and Ma is incorrect and the alternative protocol EWAP of Zhang and Ma is insecure. We further analyse the third version of the WAI protocol and prove its security in the Canetti-Krawczyk model. In addition, we also provide some practical security analysis of this version.

This paper presents the first constructions for certificateless encryption (CLE) schemes that are provably secure against strong adversaries in the standard model. It includes both a generic construction for a strongly secure CLE scheme from any passively secure scheme as well as a concrete construction based on the Waters identity-based encryption scheme.

We demonstrate an active attack on the WEP protocol that is able to recover a 104-bit WEP key using less than 40.000 frames in 50% of all cases. The IV of these packets can be randomly chosen. This is an improvement in the number of required frames by more than an order of magnitude over the best known key-recovery attacks for WEP. On a IEEE 802.11g network, the number of frames required can be obtained by re-injection in less than a minute. The required computational effort is approximately 2^{20} RC4 key setups, which on current desktop and laptop CPUs is neglegible.

We give the first perfectly rerandomizable, Replayable-CCA (RCCA) secure encryption scheme, positively answering an open problem of Canetti et al. [CRYPTO 2003]. Our encryption scheme, which we call the Double-strand Cramer-Shoup scheme, is a non-trivial extension of the popular Cramer-Shoup encryption. Its security is based on the standard DDH assumption. To justify our definitions, we define a powerful "Replayable Message Posting" functionality in the Universally Composable (UC) framework, and show that any encryption scheme that satisfies our definitions of rerandomizability and RCCA security is a UC-secure implementation of this functionality. Finally, we enhance the notion of rerandomizable RCCA security by adding a receiver-anonymity (or key-privacy) requirement, and show that it results in a correspondingly enhanced UC functionality. We leave open the problem of constructing a scheme that achieves this enhancement.

We present a general framework for constructing two-message oblivious transfer protocols using a modification of Cramer and Shoup's notion of smooth projective hashing (2002). This framework is an abstraction of the two-message oblivious transfer protocols of Naor and Pinkas (2001) and Aiello et al. (2001), whose security is based on the Decisional Diffie Hellman Assumption. In particular, we give two new oblivious transfer protocols. The security of one is based on the Quadratic Residuosity Assumption, and the security of the other is based on the $N$'th Residuosity Assumption. Compared to other applications of smooth projective hashing, in our context we must deal also with maliciously chosen parameters, which raises new technical difficulties. We also improve on prior constructions of factoring-based smooth universal hashing, in that our constructions *do not require that the underlying RSA modulus is a product of safe primes*. (This holds for the schemes based on the Quadratic Residuosity Assumption as well as the ones based on the $N$'th Residuosity Assumption.) In fact, we observe that the safe-prime requirement is unnecessary for many prior constructions. In particular, the factoring-based CCA secure encryption schemes due to Cramer-Shoup, Gennaro-Lindell, and Camenisch-Shoup remain secure even if the underlying RSA modulus is not a product of safe primes.

The recent algebraic attacks have received a lot of attention in cryptographic literature. The algebraic immunity of a Boolean function quantifies its resistance to the standard algebraic attacks of the pseudo-random generators using it as a nonlinear filtering or combining function. Very few results have been found concerning its relation with the other cryptographic parameters or with the $r$-th order nonlinearity. As recalled by Carlet at Crypto'06, many papers have illustrated the importance of the $r$th-order nonlinearity profile (which includes the first-order nonlinearity). The role of this parameter relatively to the currently known attacks has been also shown for block ciphers. Recently, two lower bounds involving the algebraic immunity on the $r$th-order nonlinearity have been shown by Carlet et \emph{al}. None of them improves upon the other one in all situations. In this paper, we prove a new lower bound on the $r$th-order nonlinearity profile of Boolean functions, given their algebraic immunity, that improves significantly upon one of these lower bounds for all orders and upon the other one for low orders.

In this paper, we propose a zero-knowledge authenticated key agreement protocol with key confirmation (AKC) in asymmetric setting. The protocol has several desirable security attributes like some classical AKCs such as STS and MQV. One highlight of our protocol is its zero-knowledge property, which enables succinct proofs of the claimed security attributes, while the overhead in communication and computation resulting from the special design to achieve zero-knowledge is insignificant.

We introduce a new infinite family of multiterm functions that are APN on $GF(2^{2k})$ for odd $k$.

We introduce a new kind of word-oriented linear feedback shift register called $\sigma-$LFSR which is constructed with the instructions of the modern processor and have fast software implementation. We offer an algorithm to search for good primitive $\sigma-$LFSR. In particular, we give two examples HHZ-1 and HHZ-2 and compare their efficiency and security with those of the LFSRs appearing in stream ciphers such as SNOW, SOBER and Turing. Our results show that replacing the LFSRs in SNOW, SOBER and Turing with HHZ-1 will improve security and the efficiency of fast software implementation.

Deniability is defined as a privacy property which enables protocol principals to deny their involvement after they had taken part in a particular protocol run. Lately, Chou et al. had proposed their ID-based deniable authentication protocol after proving the vulnerability to Key-Compromise Impersonation (KCI) attack in Cao et al.'s protocol. In addition, they claimed that their protocol is not only secure, but also able to achieve both authenticity and deniability properties. However, in this paper, we demonstrate that Chou et al.'s protocol is not flawless as it remains insecure due to its susceptibility to the KCI attack. Based on this, we propose an enhanced scheme which will in fact preserves the authenticity, the deniability and the resistance against the KCI attack.

We study the solution of the discrete logarithm problem for the Jacobian of a curve of genus g defined over an extension field Fqn, by decomposed attack, considering a external elements B0 given by points of the curve whose x-coordinates are defined in Fq. In the decomposed attack, an element of the group which is written by a sum of some elements of external elements is called (potentially) decomposed and the set of the terms, that appear in the sum, is called decomposed factor. In order for the running of the decomposed attack, a test for the (potential) decomposeness and the computation of the decomposed factor are needed. Here, we show that the test to determine if an element of the Jacobian (i.e., reduced divisor) is written by an ng sum of the elements of the external elements and the computation of decomposed factor are reduced to the problem of solving some multivariable polynomial system of equations by using the Riemann-Roch theorem. In particular, in the case of a hyperelliptic curve, we construct a concrete system of equations, which satisfies these properties and consists of (n2¡n)g quadratic equations. Moreover, in the case of (g; n) = (1; 3); (2; 2) and (3; 2), we give examples of the concrete computation of the decomposed factors by using the computer algebra system Magma.

With the growing demand of databases outsourcing and its security concerns, we investigate privacy-preserving set intersection in a distributed scenario. We propose a one-round protocol for privacy-preserving set intersection based on a combination of secret sharing scheme and homomorphic encryption. We then show that, with an extra permutation performed by each of contacted servers, the cardinality of set intersection can be computed efficiently. All protocols constructed in this paper are provably secure against a semi-honest adversary under the Decisional Diffie-Hellman assumption.

We explain a method of finding the polynomials representing $\sqrt{-D}$ and $\zeta_k$ over the field containing $\sqrt{-D}$ and $\zeta_k$ and how to construct a pairing friendly elliptic curves over the cyclotomic fields containing ${\mathbb Q} (\zeta_k, \sqrt{-D})$ for arbitrary $k$ and $D$ by CP method. By using the factorization of the cyclotomic polynomial combined some polynomial, we extend the construction over cyclotomic fields to the construction over some extensions of the cyclotomic fields containing ${\mathbb Q} (\zeta_k, \sqrt{-D})$. We explain the limitation of finding more families of pairing friendly elliptic curves with embedding degree 10. For all computation, we use the PARI-GP \cite{GP}.

Given (deterministic) ciphers $\calE$ and~$E$ that can encipher messages of $\el$ and $n$ bits, respectively, we construct a cipher~$\calE^*=XLS[\calE,E]$ that can encipher messages of $\el+s$ bits for any $s<n$. Enciphering such a string will take one call to~$\calE$ and two calls to~$E$. We prove that~$\calE^*$ is a strong pseudorandom permutation as long as~$\calE$ and~$E$ are. Our construction works even in the tweakable and VIL (variable-input-length) settings. It makes use of a multipermutation (a pair of orthogonal Latin squares), a combinatorial object not previously used to get a provable-security result.

Dragon stream cipher is one of the focus ciphers which have reached Phase 2 of the eSTREAM project. In this paper, we present a new method of building a linear distinguisher for Dragon. The distinguisher is constructed by exploiting the biases of two S-boxes and the modular addition which are basic components of the nonlinear function $F$. The bias of the distinguisher is estimated to be around $2^{-75.32}$ which is better than the bias of the distinguisher presented by Englund and Maximov. We have shown that Dragon is distinguishable from a random cipher by using around $2^{150.6}$ keystream words and $2^{59}$ memory. In addition, we present a very efficient algorithm for computing the bias of linear approximation of modular addition.

The realization of the quantum computer will enable to break public-key cryptosystems based on factoring problem and discrete logarithm problem. It is considered that even the quantum computer can not solve NP-hard problem in a polynomial time. The subset sum problem is known to be NP-hard. Merkle and Hellman proposed a knapsack cryptosystem using the subset sum problem. However, it was broken by Shamir or Adleman because there exist the linearity of the modular transformation and the specialty in the secret keys. It is also broken with the low-density attack because the density is not sufficiently high. In this paper, we propose a new class of knapsack scheme without modular transformation. The specialty and the linearity can be avoidable by using the Chinese remainder theorem as the trapdoor. The proposed scheme has a high density and a large dimension to be sufficiently secure against a practical low-density attack.

Extensive studies have been made of the Secret Sharing Scheme(SSS). In this paper new classes of SSS, referred to as K-SSS, $\rm{K_I}$-SSS, $\rm{K_{I\hspace{-.1em}I}}$-SSS and $\tilde{{\rm K}}$-SSS are presented on the basis of recovering algorithm, K-RA. As an application, we shall also present a method for the recovering of secret informations learned only by heart, based on a particular class of K-SSS, $\rm{K_I}$-SSS.

We define a new notion of a reduced lattice, based on a quantity introduced in the LLL paper. We show that lattices reduced in this sense are simultaneously reduced in both their primal and dual. We show that the definition applies naturally to blocks, and therefore gives a new hierarchy of polynomial time algorithms for lattice reduction with fixed blocksize. We compare this hierarchy of algorithms to previous ones. We then explore algorithms to provably minimize the associated measure, and also some more efficient heuristics. Finally we comment on the initial investigations of applying our technique to the NTRU family of lattices.

At DRM 2002, Chow et al. presented a method for implementing the DES block cipher such that it becomes hard to extract the embedded secret key in a white-box attack context. In such a context, an attacker has full access to the implementation and its execution environment. In order to provide an extra level of security, an implementation shielded with external encodings was introduced by Chow et al. and improved by Link and Neumann. In this paper, we present an algorithm to extract the secret key from such white-box DES implementations. The cryptanalysis is a differential attack on obfuscated rounds, and works regardless of the shielding external encodings that are applied. The cryptanalysis has a average time complexity of $2^{14}$ and a negligible space complexity.

We discuss irreducible polynomials that can be used to speed up square root extraction in fields of characteristic two. We call such polynomials \textit{square root friendly}. The obvious applications are to point halving methods for elliptic curves and divisor halving methods for hyperelliptic curves. We note the existence of square root friendly trinomials of a given degree when we already know that an irreducible trinomial of the same degree exists, and formulate a conjecture on the degrees of the terms of square root friendly polynomials. We also give a partial result that goes in the direction of the conjecture. Irreducible polynomials $p(X)$ such that the square root $\zeta$ of a zero $x$ of $p(X)$ is a sparse polynomial are considered and those for which $\zeta$ has minimal degree are characterized. In doing this we discover a surprising connection these polynomials and those defining polynomial bases with an extremal number of trace one elements. We also show how to improve the speed of solving quadratic equations and that the increase in the time required to perform modular reduction is marginal and does not affect performance adversely. Experimental results confirm that the new polynomials mantain their promises; These results generalize work by Fong et al.\ to polynomials other than trinomials. Point halving gets a speed-up of $20\%$ and the performance of scalar multiplication based on point halving is improved by at least $11\%$.