In this paper, we present a variant of Waters' Identity-Based Encryption scheme with a much smaller public-key size (only a few kilobytes). We show that this variant is semantically secure against passive adversaries in the standard model.\smallskip In essence, the new scheme divides Waters' public key size by a factor $$ at the cost of (negligibly) reducing security by $$ bits. Therefore, our construction settles an open question asked by Waters and constitutes the first fully secure {\sl practical} Identity-Based Encryption scheme.

We introduce new methods for detecting control-flow side channel attacks, transforming C source code to eliminate such attacks, and checking that the transformed code is free of control-flow side channels. We model control-flow side channels with a program counter transcript, in which the value of the program counter at each step is leaked to an adversary. The program counter transcript model captures a class of side channel attacks that includes timing attacks and error disclosure attacks. We further show that the model formalizes previous ad hoc approaches to preventing side channel attacks. We then give a dynamic testing procedure for finding code fragments that may reveal sensitive information by key-dependent behavior, and we show our method finds side channel vulnerabilities in real implementations of IDEA and RC5, in binary modular exponentiation, and in the lsh implementation of the ssh protocol. Further, we propose a generic source-to-source transformation that produces programs provably secure against control-flow side channel attacks. We implemented this transform for C together with a static checker that conservatively checks x86 assembly for violations of program counter security; our checker allows us to compile with optimizations while retaining assurance the resulting code is secure. We then measured our technique's effect on the performance of binary modular exponentiation and real-world implementations in C of RC5 and IDEA: we found it has a performance overhead of at most 5X and a stack space overhead of at most 2X. Our approach to side channel security is practical, generally applicable, and provably secure against an interesting class of side channel attacks.

To solve the problem of searching on encrypted data, many keyword search schemes have been proposed in recent years. The goal of such schemes is to enable a user to give an untrusted storage server the ability only to test whether an encrypted document contains a few keywords without learning anything else about the document. In this paper, we are concerned with decrypting the searched results as well as searching for desired documents. In the previously proposed schemes, except for the work by Waters et al.[WBDS04], a user decrypts searched documents using his private key, $$, or a symmetric key. Our another goal is to enable a user to give a proxy the ability to decrypt only the ciphertexts containing desired keywords, but not other ciphertexts. We propose a new mechanism, Searchable Keyword-Based Encryption (SKBE) which satisfies both the above goals. As a result of adding the delegation of decryption ability, our mechanism works more securely and efficiently in several applications, such as email gateways, secure audit logs, and decryption key delegation systems, than any of the previously proposed schemes. We formalize this mechanism, define its security model and propose an efficient construction whose security is proved in a random oracle model under the Bilinear Diffie-Hellman Inversion assumption. The scheme is constructed based on the Public Key Encryption with Conjunctive Field Keyword Search scheme in [PKL04] by using a hybrid encryption technique.

In this paper we propose two compilers which are designed to transform a group key exchange protocol secure against any passive adversary into an authenticated group key exchange protocol with key confirmation which is secure against any passive adversary, active adversary, or malicious insider. We show that the first proposed compiler gives protocols that are more efficient than those produced by the compiler of Katz and Yung. The second proposed compiler further reduces the computational complexity of the output protocols by using a Trusted Third Party (TTP). We moreover show that, although the protocols produced by the novel compilers have lower computational complexity than the protocols produced by the Katz-Yung compiler, the protocols nevertheless achieve key confirmation, unlike the protocols output by the Katz-Yung compiler.

We give two applications of Nisan--Wigderson-type ("non-cryptographic") pseudorandom generators in cryptography. Specifically, assuming the existence of an appropriate NW-type generator, we construct: A one-message witness-indistinguishable proof system for every language in NP, based on any trapdoor permutation. This proof system does not assume a shared random string or any setup assumption, so it is actually an "NP proof system." A noninteractive bit commitment scheme based on any one-way function. The specific NW-type generator we need is a hitting set generator fooling nondeterministic circuits. It is known how to construct such a generator if ETIME = DTIME(2^O(n)) has a function of nondeterministic circuit complexity 2^\Omega(n) (Miltersen and Vinodchandran, FOCS `99). Our witness-indistinguishable proofs are obtained by using the NW-type generator to derandomize the ZAPs of Dwork and Naor (FOCS `00). To our knowledge, this is the first construction of an NP proof system achieving a secrecy property. Our commitment scheme is obtained by derandomizing the interactive commitment scheme of Naor (J. Cryptology, 1991). Previous constructions of noninteractive commitment schemes were only known under incomparable assumptions.

In this paper, we study the opacity property of verifiably encrypted signatures (VES) of Boneh et al. (proposed in Eurocrypt 2003). Informally, opacity implies that although some given aggregate signatures can verified, no useful information about the individual signatures is leaked. However, the very fact that an aggregate signature can be verified leaks certain information - that the individual signature is indeed well-formed. Apart from this, is there any other information leaked? In this paper, we show that there is absolutely no other information leaked about the individual signatures when the aggregation contains only two signatures. In more formal terms, we show that VES are Zero-Knowledge (ZK). We then extend the ZK property of VES to propose efficient Additive Non-Interactive Witness-Indistinguishable (A-NIWI) proofs. Intuitively an A-NIWI proof can be considered as a Proof of Knowledge (PoK) of another A-NIWI proof.

Motivated by the needs of the {\it pairing based cryptography\/}, Miyaji, Nakabayashi and Takano have suggested a construction of so-called MNT elliptic curves with low embedding degree. We give some heuristic arguments which suggest that there are only about $$ of MNT curves with complex multiplication discriminant up to $$. We also show that there are very few finite fields over which elliptic curves with small embedding degree and small complex multiplication discriminant may exist (regardless of the way they are constructed).

In a recent letter, Cui, Duan and Chan propose a generalisation of the Scott-Barreto method to build a larger family of MNT curves, and they claim that their proposal is also applicable to other curve construction methods. Here we show that the Cui-Duan-Chan technique is irrecoverably flawed.

Boolean functions on $$ which satisfy the Strict Avalanche Criterion ($$) play an important role in the art of information security. In this paper, we extend the conception $$ to finite fields $$. A necessary and sufficient condition is given by using spectral analysis. Also, based on an interesting permutation polynomial theorem, we prove various facts about ($$)-th order $$ functions on $$. We also construct many such functions.

A tree-based key transport protocol is presented which can be seen as a generalizing variant of the star- and tree-based protocols proposed by Burmester and Desmedt at EUROCRYPT '94. Our scheme does not rely on the availability of globally verifiable signatures or arbitrary point-to-point connections, and its security against active adversaries is proven in the standard model under the Decision Diffie Hellman assumption.

We exhibit an infinite class of almost perfect nonlinear quadratic polynomials from $$ to $$ ($$, $$ divisible by 3 but not by 9). We prove that these functions are EA-inequivalent to any power function. In the forthcoming version of the present paper we will proof that these functions are CCZ-inequivalent to any Gold function and to any Kasami function, in particular for $$, they are therefore CCZ-inequivalent to power functions.

In this paper, we propose a new normal basis multiplication algorithm for GF(2n). This algorithm can be used to design not only fast software algorithms but also low complexity bit-parallel multipliers in some GF(2n)s. Especially, for some values of n that no Gaussian normal basis exists in GF(2n), i.e., 8|n, this algorithm provides an alternative way to construct low complexity normal basis multipliers. Two improvements on a recently proposed software normal basis multiplication algorithm are also presented. Time and memory complexities of these normal basis multiplication algorithms are compared with respect to software performance. It is shown that they have some specific behavior in different applications. For example, GF(2571) is one of the five binary fields recommended by NIST for ECDSA (Elliptic Curve Digital Signature Algorithm) applications. In this field, our experiments show that the new algorithm is even faster than the polynomial basis Montgomery multiplication algorithm: 525 us v. 819 us.

Recently, a number of ID-based two-party authenticated key agreement protocols which make of bilinear pairings have been proposed \cite {CJL,MB,Sh,S,X}. In this paper, we show that the Xie's protocol \cite {X} does not provide implicit key authentication and key-compromise impersonation resilience. Also, we point out the vulnerability of the Choi {\it et al}'s protocol \cite {CJL} against signature forgery attacks.

In Year 2005, Internet users were twice more likely to receive unsolicited electronic messages, known as spams, than regular emails. Proof of work protocols are designed to deter such phenomena and other denial-of-service attacks by requiring computed stamps based on hard-to-solve problems with easy-to-verify solutions. As cpu-intensive computations are badly hit over time by Moore's law, memory-bound computations have been suggested to deal with heterogeneous hardware. We introduce new practical, optimal, proven and possibly memory-bound functions suitable to these protocols, in which the client-side work to compute the response is intrinsically exponential with respect to the server-side work needed to set or check the challenge. One-way non-interactive solution-verification variants are also presented. Although simple implementations of such functions are bound by memory latency, optimized versions are shown to be bound by memory bandwidth instead.

ID-based encryption allows for a sender to encrypt a message to an identity without access to a public key certificate. Based on the bilinear pairing, Boneh and Franklin proposed the first practical ID-based encryption scheme and used the padding technique of Fujisaki-Okamto to extend it to be a chosen ciphertext secure version. In this letter, we would like to use another padding technique to propose a new ID-based encryption scheme secure against chosen ciphertext attacks. The security of our scheme is based on the Gap bilinear Diffie-Hellman assumption in the random oracle model.

To achieve secure data communications, two parties should be authenticated by each other and agree on a secret session key by exchanging messages over an insecure channel. In this paper, based on the bilinear pairing, we present a new two-party authenticated key agreement protocol, and use the techniques from provable security to examine the security of our protocol within Bellare-Rogaway model.

As a special digital signature, a group signature scheme al- lows a group member to sign message on behalf of the group in an anony-mous and unlinkability way, In case of a dispute, the group manager can reveal the actual identity of signer. Anonymity and unlinkability are basic properties of group signature, which distinguish other signature scheme. Recently, based on the work of Camenisch and Lysyanskaya, which is known to be the most e±cient scheme so far, E.Y.Choi et.al propose an e±cient group signature scheme with member revocation at TrustBus 2005. Unfortunately, in this work we show that the scheme has linkability, Namely, any one can distinguish whether two di®erent group signatures are produced by the same signer, and that the revo- cation manager cannot trace the actual identity of a signer by a group signature. Finally, we give the corresponding attack to the scheme.

In this paper we propose a definition and construction of a new family of one-way candidate functions $$, where $$ is an alphabet with $$ elements. Special instances of these functions can have the additional property to be permutations (i.e. one-way permutations). These one-way functions have the property that for achieving the security level of $$ computations in order to invert them, only $$ bits of input are needed. The construction is based on quasigroup string transformations. Since quasigroups in general do not have algebraic properties such as associativity, commutativity, neutral elements, inverting these functions seems to require exponentially many readings from the lookup table that defines them (a Latin Square) in order to check the satisfiability for the initial conditions, thus making them natural candidates for one-way functions.

Proofs are invaluable tools in assuring protocol implementers about the security properties of protocols. However, several instances of undetected flaws in the proofs of protocols (resulting in flawed protocols) undermine the credibility of provably-secure protocols. In this work, we examine several protocols with claimed proofs of security by Boyd & Gonzalez Nieto (2003), Jakobsson & Pointcheval (2001), and Wong & Chan (2001), and an authenticator by Bellare, Canetti, & Krawczyk (1998). Using these protocols as case studies, we reveal previously unpublished flaws in these protocols and their proofs. We hope our analysis will enable similar mistakes to be avoided in the future.

We argue that if the message expansion code of SHA-1 is replaced by a linear code with a better minimum distance, then the resulting hash function is collision resistant. To support this argument, we characterize the disturbance vectors which are used to build local collision attacks as a linear code. This linear code is the xor-sum of two codes, the message expansion code and a linear code representing the underlying block cipher in SHA-1. We also show that the following constraint satisfaction problem is $$-hard. The constraints are restricted to being XOR constraints, or Majority constraints on at most three variables each. The instances are further restricted by requiring that the constraints can be listed in a sequence C_1, C_2,...,C_m, such that for every constraint C_i, two of the variables in it occur only in constraints C_j, with |j-i|< 48. This problem is similar to the problem modeling the one-way function property of SHA-1.

We study unconditionally secure 1-out-of-2 Oblivious Transfer (1-2 OT). We first point out that a standard security requirement for 1-2 OT of bits, namely that the receiver only learns one of the bits sent, holds if and only if the receiver has no information on the XOR of the two bits. We then generalize this to 1-2 OT of strings and show that the security can be characterized in terms of binary linear functions. More precisely, we show that the receiver learns only one of the two strings sent if and only if he has no information on the result of applying any binary linear function (which non-trivially depends on both inputs) to the two strings. We then argue that this result not only gives new insight into the nature of 1-2 OT, but it in particular provides a very powerful tool for analyzing 1-2 OT protocols. We demonstrate this by showing that with our characterization at hand, the reduceability of 1-2 OT (of strings) to a wide range of weaker primitives follows by a very simple argument. This is in sharp contrast to previous literature, where reductions of 1-2 OT to weaker flavors have rather complicated and sometimes even incorrect proofs.

Certificateless public-key encryption has recently been proposed as an attractive alternative to certificate-based and identity-based encryption schemes. The attraction of certificateless PKE is that it combines the implicit public key authentication of an identity-based scheme with the escrow-free property of a certificate-based scheme. However, all the certificateless schemes that have been thusfar presented have either had the security proved in a reduced security model, or have relied on the random oracle model. Indeed, some authors have gone as far as suggesting that it is impossible to prove the full security of a certificateless scheme in the standard model. This paper examines this claim and comes to the conclusion that, while some provable security techniques may be denied to us, there is no reason why the security of a certificateless scheme cannot be proven in the standard model.

Diffie-Hellman problems have been widely involved in the design of various cryptographic protocols. Its general family is based on the discrete logarithm over a finite field. Since 2000, its another family which is based on elliptic curve discrete logarithm as well as bilinear pairing, e.g. Weil or Tate pairing, has been attracted significant studies. Thereafter, various cryptographic protocols have been proposed using Diffie-Hellman problem associated with bilinear pairings. This paper we will present a new family of Diffie-Hellman problem by utilizing subset sum problem. It is named as Knapsack Diffie-Hellman Problems with bilinear pairings. We will propose a number of definitions on the family and then analyze their relationships.

Bid opening in e-auction is efficient when a homomorphic secret sharing function is employed to seal the bids and homomorphic secret reconstruction is employed to open the bids. However, this high efficiency is based on an assumption: the bids are valid (e.g. within a special range). An undetected invalid bid can compromise correctness and fairness of the auction. Unfortunately, validity verification of the bids is ignored in the auction schemes employing homomorphic secret sharing (called homomorphic auction in this paper). In this paper, an attack against the homomorphic auction in the absence of bid validity check is presented and a necessary bid validity check mechanism is proposed. Then a batch cryptographic technique is introduced and applied to improve the efficiency of bid validity check.

A group signature is a basic privacy mechanism. The group joining operation is a critical component of such a scheme. To date all secure group signature schemes either employed a trusted-party aided join operation or a complex joining protocol requiring many interactions between the prospective user and the Group Manager (GM). In addition no efficient scheme employed a join protocol proven secure against adversaries that have the capability to dynamically initiate multiple concurrent join sessions during an attack. This work presents the first efficient group signature scheme with a simple Joining protocol that is based on a ``single message and signature response'' interaction between the prospective user and the GM. This single-message and signature-response registration paradigm where no other actions are taken, is the most efficient possible join interaction and was originally alluded to in 1997 by Camenisch and Stadler, but its efficient instantiation remained open till now. The fact that joining has two short communication flows and does not require secure channels is highly advantageous: for example, it allows users to easily join by a proxy (i.e., a security officer of a company can send a file with all registration requests in his company and get back their certificates for distribution back to members of the company). It further allows an easy and non-interactive global system re-keying operation as well as straightforward treatment of multi-group signatures. We present a strong security model for group signatures (the first explicitly taking into account concurrent join attacks) and an efficient scheme with a single-message and signature-response join protocol. The present manuscript is a full version containing proofs, minor corrections as well as a more flexible and efficient protocol construction compared to the proceedings version.

In [2], Stanislav Bulygin presents a chosen-ciphertext attack against certain instances of noncommutative polly cracker-type cryptosystems which were proposed in [7] and [9]. In this article, we present generalized versions of this attack, which can be used against virtually all polly cracker-type cryptosystems. We then present a simple but effective techique to counter these attacks. We also present a technique to counter an adaptive chosen-ciphertext attack which was first described by Neil Koblitz in [8].

Identification protocols based on the Computational Diffie Hellman Problem (CDHP) generally assume the intractability of the underlying Decisional Diffie Hellman Problem (DDHP). Due to this, the security of all such schemes in a pairing based scenario is doubtful. In this paper, we propose a two-round zero-knowledge identification protocol using bilinear pairings. Our proposed protocol has two contrasting features to traditional identification schemes: (1) The scheme requires the verifier to toss his coins before the prover. (2) The coin tosses of the verifier are secret while the coin tosses of the prover are not. As a consequence, we obtain a \emph{blind} identification scheme with complete zero knowledge. Traditionally in an identification scheme, a passive adversary watching the communication gains information intended only for the verifier. For instance, from watching the transcript in the Fiat-Shamir zero knowledge identification scheme, an adversary also learns the outcome of the protocol (i.e. whether the identification succeeds or not). The blinding property of our scheme eliminates this disadvantage while still ensuring zero knowledge. Finally, as a natural extension of our scheme, we present the concept of `all or none' group identification protocol that can be used to authenticate together an arbitrary number of users in a batch such that if the identification fails, it is impossible for the users to know which one cheated. We also prove the security of our scheme and give some interesting applications including anonymous seller credit card payments. The cryptographic primitives can be efficiently encapsulated in smart cards designed for Elliptic Curve Cryptography (ECC). The private key must be included in a tamperproof device inside the smart card.

Constructing non-supersingular elliptic curves for pairing-based cryptosystems have attracted much attention in recent years. The best previous technique builds curves with p = lg(q)/lg(r) = 1 (k = 12) and p = lg(q)/lg(r) = 1.25 (k = 24). When k > 12, most of the previous works address the question by representing r(x) as a cyclotomic polynomial. In this paper, we propose a new method to find more pairing-friendly elliptic curves with arbitrary embedding degree k by certain special polynomial families. The new method generates curves with lg(q)/lg(r) = 1 (k > 48) by random forms of r(x). Different representations of r(x) allow us to obtain many new families of pairing-friendly elliptic curves. In addition, we propose a equation to illustrate how to obtain small values of p by choosing appropriate forms of discriminant D and trace t. Numerous parameters of certain pairing-friendly elliptic curves are presented with support for the theoretical conclusions.

We propose a scheme for electronic cash based on symmetric primitives. The scheme is secure in the framework for universal composability assuming the existence of a symmetric CCA2-secure encryption scheme, a CMA-secure signature scheme, and a family of one-way, collision-free hash functions. In particular, the security proof is not in the random-oracle model. Due to its high efficiency, the scheme is well-suited for devices such as smart-cards and mobile phones. We also show how the proposed scheme can be used as a group signature scheme with one-time keys.

Since the publication of Differential Power Analysis (DPA) in 1998, many countermeasures have been published to counteract this very efficient kind of attacks. All these countermeasures follow the same approach : they try to make sensitive operations uncorrelated with the input. Such a method is very costly in terms of both timing and memory space. In this paper, we suggest a new approach where block ciphers are designed to inherently thwart DPA attacks. The idea we develop in this paper is based on a theoretical analysis of DPA attacks and it essentially consists in embedding existing iterated block ciphers in a secure layer. We analyse the security of our proposal and we show that it induces very small overheads.

In most of the existing identity-based key agreement schemes, it is usually assumed that either the communicated parties know each other's identifier before the protocol starts or their identifiers are transferred along with the protocol messages. However, these schemes are not suitable for use in many real-world applications aimed to achieve unilateral identity privacy, which means that one communicating party does not want to expose his identifier to an outsider while his partner cannot know his identifier in advance. In this paper, we propose an efficient identity-based two-party key agreement scheme with unilateral identity privacy using pairing, and formally analyze its security in a modified Bellare-Rogaway key agreement security model.

This paper presents an improved simple power analysis attack against the key schedule of Camellia. While the original attack required an exact determination of the Hamming weight of intermediate data values based on power measurements, in this paper, two variants of the simple power analysis attack are presented and shown to be tolerant of errors that might occur in the Hamming weight determinations. In practical applications of the attack such errors are likely to occur due to noise and distortion in the power measurements and their mapping to the Hamming weights of the data. Further, we propose a practical method to evaluate the susceptibility of other block ciphers to simple power analysis attacks. To resist these attacks, the required design rationale of key schedules and several practical countermeasures are suggested.

With respect to a special class of access structures based on connectivity of graphs, we start from a linear secret sharing scheme and turn it into a secret sharing scheme with perfect security and exponentially small error probability by randomizing the reconstruction algorithm through random walks on graphs. It reduces the polynomial work space to logarithmic. Then we build the corresponding statistical multiparty computation protocol by using the secret sharing scheme. The results of this paper also imply the inherent connections and influences among secret sharing, randomized algorithms, and secure multi-party computation.

We propose four different public-key identification schemes that make use of bilinear pairings, and prove their security under certain computational assumptions. Each of the schemes is more efficient and/or more secure than any known pairing-based identification scheme.

In this paper, we describe a new cryptographic primitive called \emph{(One-Way) Signature Chaining}. Signature chaining is essentially a method of generating a chain of signatures on the same message by different users. Each signature acts as a ``link'' of the chain. The \emph{one-way}-ness implies that the chaining process is one-way in the sense that more links can be easily added to the chain. However, it is computationally infeasible to remove any intermediate links without removing all the links. The signatures so created are called chain signatures. We give precise definitions of chain signatures and discuss some applications in trust transfer. We also present a practical construction of a CS scheme that is secure under the Computational Diffie-Hellman (CDH) assumption in bilinear maps.

We consider the problem of efficient key management and user revocation in cryptographic file systems that allow shared access to files. A performance-efficient solution to user revocation in such systems is lazy revocation, a method that delays the re-encryption of a file until the next write to that file. We formalize the notion of key-updating schemes for lazy revocation, an abstraction to manage cryptographic keys in file systems with lazy revocation, and give a security definition for such schemes. We give two composition methods that combine two secure key-updating schemes into a new secure scheme that permits a larger number of user revocations. We prove the security of two slightly modified existing constructions and propose a novel binary tree construction that is also provable secure in our model. Finally, we give a systematic analysis of the computational and communication complexity of the three constructions and show that the novel construction improves the previously known constructions.

We propose a formalization of the security of transparent harddisk-encryption using the universal composability framework. We point out that several commercially available schemes for transparent hard disk encryption are built on principles that limit security, and we propose schemes for disk encryption with passive and active security, respectively. As for the efficiency of the schemes, security against active attacks can be obtained with a constant factor overhead in space and a logarithmic overhead in time. Finally, we also also sketch an actively secure scheme that provides some amount of security, even if the adversary is given temporary access to the internal state of the encryption device used.

Carlet and Charpin classified in \cite{CC04} the set of cubic $$-resilient Boolean functions into four different types with respect to the Walsh spectrum and the dimension of the linear space. Based on the classification of $$, we completed the classification of the cubic $$-resilient Boolean function by deriving the corresponding ANF and autocorrelation spectrum for each of the four types. In the same time, we solved an open problem of \cite{CC04} by proving that all plateaued cubic $$-resilient Boolean functions have dimension of the linear space equal either to $$ or $$.

In 1999, Juels and Wattenberg introduce an effective construction of Fuzzy Sketch, i.e. a way of handling errors into string verification. This allows them to consider data varying into time, such as, for instance, answers to a list of subjective questions. To this end, they utilize an Error Correcting Code. We here show how to embed a trapdoor into Fuzzy Sketches, reducing to authorized people the ability to correct errors and thus to verify the fuzzy equality to the Fuzzy Sketch.

The $$ pairing is an efficient computation technique based on a generalization of the Duursma Lee method for calculating the Tate pairing. The pairing can be computed very efficiently on genus 2 hyperelliptic curves. In this paper it is demonstrated that this pairing operation is well suited to a dedicated parallel hardware implementation. An $$ pairing processor is described in detail and the architectures required for such a system are discussed. Prototype implementation results are presented over a base field of $$ and the advantages of implementing the pairing on the dedicated processor are discussed.

This is a survey of mechanisms to control or prevent spam, with emphsis on cryptographic protocols. We also present a new cryptographic protocol, Secure Automated Resolution Protocol, which can be used to penalize spammers (and for other applications).

A fundamental result in cryptography is that a digital signature scheme can be constructed from an arbitrary one-way function. A proof of this somewhat surprising statement follows from two results: first, Naor and Yung defined the notion of universal one-way hash functions and showed that the existence of such hash functions implies the existence of secure digital signature schemes. Subsequently, Rompel showed that universal one-way hash functions could be constructed from arbitrary one-way functions. Unfortunately, despite the importance of the result, a complete proof of the latter claim has never been published. In fact, a careful reading of Rompel's original conference publication reveals a number of errors in many of his arguments which have (seemingly) never been addressed. We provide here what is --- as far as we know --- the first complete write-up of Rompel's proof that universal one-way hash functions can be constructed from arbitrary one-way functions.

MD4 is a cryptographic hash function introduced in 1990 by Rivest. After MD4 was proposed, several hash functions such as MD5, HAVAL, RIPEMD, RIPEMD-160, SHA-1 and SHA-256 were designed based on the MD4 structure. In this paper, we cryptanalyze the compression functions of MD4, MD5 and 4-, 5-pass HAVAL in encryption modes. We exploit the recently proposed related-key rectangle and boomerang techniques to show non-randomness of MD4, MD5 and 4-, 5-pass HAVAL and to distinguish them from a randomly chosen cipher. The attacks are highly practical and have been confirmed by our experiments.

Since the introduction of Identity-based (ID-based) cryptography by Shamir in 1984, numerous ID-based signature schemes have been proposed. In 2001, Rivest et al. introduced ring signature that provides irrevocable signer anonymity and spontaneous group formation. In recent years, ID-based ring signature schemes have been proposed and all of them are based on bilinear pairings. In this paper, we propose the first ID-based threshold ring signature scheme that is not based on bilinear pairings. We also propose the first ID-based threshold `linkable' ring signature scheme. We emphasize that the anonymity of the actual signers is maintained even against the private key generator (PKG) of the ID-based system. Finally we show how to add identity escrow to the two schemes. Due to the different levels of signer anonymity they support, the schemes proposed in this paper actually form a suite of ID-based threshold ring signature schemes which is applicable to many real-world applications with varied anonymity requirements.

This paper presents an effective method to integrate the revocation mechanism into some group signature schemes that are based on the strong RSA assumption. The mechanism enables the group manager to either update a group member's certificates, or revoke a group member. More specifically, a generic method has been proposed for the protocols of sign, verify, and revocation. We demonstrate the effectiveness of the method by applying it to a well known group signature scheme. The new construction has better performance while enjoying an efficient revocation mechanism.

In the classic Diffie-Hellman protocol based on a generic group $$, Alice and Bob agree on a common secret $$ (master secret) which is indistinguishable from another element of $$ but not from a random bits-string of the same length. In this paper, we present a new deterministic method to extract bits from $$ when $$ is an elliptic curve defined over a quadratic extension of a finite field. In the last section, we show that it is also possible to extract a few bits when $$ is an elliptic curve defined over a prime field.

To help motivate the Weil pairing, we discuss it in the context of elliptic curves over the field of complex numbers.

In order to design bent functions, evolutionary algorithm based on truth table, algebraic normal form or Walsh spectra are already known. Evolutionary algorithm based on trace function form is not known to authors' knowledge. In this paper, we give an evolutionary algorithm based on the trace representation of boolean function. With the algorithm, we constructed many bent functions and made some analysis work. First we observe that all 4 affinely inequivalent bent classes in 6-variable can be written as the linear sum of 2 or 3 monomial trace functions. We make a conclusion that affine transform can be used to change the linear span, which lead to a method constructing perfect nonlinear s-box of non-Niho type; Second, we find that some exponents take more chances to construct bent functions while some exponents take less. By this observation, we give each exponent a cost function, which make our algorithm more efficient than exhaustive searching algorithm or random algorithm. This is also the advantage over the algorithms based on the algebraic normal form, truth table, or Walsh spectra because we don't know what kinds of algebraic normal form, truth table, Walsh spectra are more possible to be used to construct bent functions; Third, we classify the obtained bent functions into affinely inequivalent classes and the number of classes is reported.

Provable security of a block cipher against differential~/ linear cryptanalysis is based on the \emph{maximum expected differential~/ linear probability} (MEDP~/ MELP) over $$ core rounds. Over the past few years, several results have provided increasingly tight upper and lower bounds in the case $$ for the Advanced Encryption Standard (AES). We show that the \emph{exact} value of the 2-round MEDP~/ MELP for the AES is equal to the best known lower bound: $$~/ $$. This immediately yields an improved upper bound on the AES MEDP~/ MELP for $$, namely $$~/ $$.

In a famous paper of Crypto'01, Boneh and Franklin proposed the first identity-based encryption scheme (IBE), around fifteen years after the concept was introduced by Shamir. Their scheme security (more precisely, the notion of resistance against an IND-ID-CCA attacker) relies in the random oracle model. However, the reduction is far from being tight, and notably depends on the number of extractions queries. In this paper, we present an efficient modification to the Boneh-Franklin scheme that provides a tight reduction. Our scheme is basically an IBE under two keys, one of which is (randomly) detained by the recipient. It can be viewed as a continuation of an idea introduced by Katz and Wang; we will however show how our construction improves this last scheme. Our scheme features a tight reduction to the list bilinear Diffie-Hellman (LBDH) problem, which can be itself reduced tightly either to the gap bilinear Diffie-Hellman (GBDH) or the decisional bilinear Diffie-Hellman (DBDH) problems. Furthermore, for a relaxed notion of tightness (called weak-tightness) that we introduce and discuss in our paper, we show that there is a weakly tight reduction from our scheme to the computational bilinear Diffie-Hellman (CBDH) problem. Our scheme is very efficient, as one can precompute most of the quantity involved in the encryption process. Furthermore, the ciphertext size is very short: for proposed parameters, they are |M|+330 bits long.

Restrictive blind signatures allow a recipient to receive a blind signature on a message not known to the signer but the choice of message is restricted and must conform to certain rules. Partially blind signatures allow a signer to explicitly include necessary information (expiration date, collateral conditions, or whatever) in the resulting signatures under some agreement with receiver. Restrictive partially blind signatures incorporate the advantages of these two blind signatures. The existing restrictive partially blind signature scheme was constructed under certificate-based (CA-based) public key systems. In this paper we follow Brand's construction to propose the first identity-based (ID-based) restrictive blind signature scheme from bilinear pairings. Furthermore, we first propose an ID-based restrictive partially blind signature scheme, which is provably secure in the random oracle model. As an application, we use the proposed signature scheme to build an untraceable off-line electronic cash system followed Brand's construction.

We analyze a generic birthday attack where distinct inputs to some function $$ are selected until two of the inputs map through $$ to the same output, meaning that the attack has succeeded. We give tight bounds on the probability of attack success after a given number of inputs are selected as well as tight bounds on the expected number of inputs that must be selected for the attack to succeed. The types of functions considered include random functions with uniformly random outputs, random functions whose outputs have some arbitrary (biased) probability distribution, concrete functions that are balanced (all outputs have the same number of pre-images), and arbitrary concrete functions. In each case the bounds are given in terms of the probability ($$) that a pair of inputs give the same output, which is different for each type of function. The expected number of steps required to complete a birthday attack in all cases is between $$ and $$. In some cases tighter bounds than this are given. Compared to previous work in this area, the analysis here gives tighter bounds and is more applicable to the most efficient practical methods used to carry out birthday attacks, such as a generalization of Pollard's rho-method and parallel collision search. However, significant challenges remain in proving bounds for these methods.

Since the formalization of ring signature by Rivest, Shamir and Tauman in 2001, there are lots of variations appeared in the literature. Almost all of the variations rely on the random oracle model for security proof. In this paper, we propose a ring signature scheme based on bilinear pairings, which is proven to be secure against chosen message attack without using the random oracle model. It is one of the first in the literature to achieve this security level.

Public-key cryptosystem (PKC) is one of inevitable key technologies in order to accomplish fruitful security applications in ubiquitous computing systems. The ubiquitous computer only has scarce computational resources (like Smart cards, RFID, Sensor Network), however, so that the light weight PKC is necessary for those miniaturized low-power devices. Recently, XTR is considered as one of good candidates for more energy efficient cryptosystems. Among XTR exponentiation algorithms, the most efficient one is the Improved XTR Single Exponentiation (XTR-ISE) proposed by Stam-Lenstra. Thus among the family of XTR algorithms, XTR-ISE is the most efficient one suitable for ubiquitous computer. Even though the security of such devices against side channel attacks is very dangerous, there are few works on side channel attacks against XTR-ISE. In this paper we propose a new collision attack on XTR-ISE, derived from the structural properties of XTR-ISE. The analysis complexity of the proposed one is about 2^{40} where the key size is 160-bit, which is 55% improvement from the previously best known analysis of Page-Stam. We also propose a novel countermeasure using a fixed pattern which is secure against SPA. We deploy a variant of Euclidean algorithm whose one of the registers is a monotone decreasing function with odd value. From our estimation of the efficiency of the proposed method, XTR exponentiation, computing Tr(g^n) with Tr(g) and n, takes 11.2log_2n multiplications in F_{p^2}. In the sense of both efficiency and security the proposed countermeasure is the best one among the previous countermeasures- it is about 30% faster.

The ability to link two different sightings of the same Radio Frequency Identification (RFID) tag enables invasions of privacy. The problem is aggravated when an item, and the tag attached to it, changes hands during the course of its lifetime. After such an ownership transfer, the new owner should be able to read the tag but the old owner should not. We address these issues through an RFID pseudonym protocol. Each time it is queried, the RFID tag emits a different pseudonym using a pseudo-random function. Without consent of a special Trusted Center that shares secrets with the tag, it is infeasible to map the pseudonym to the tag's real identity. We present a scheme for RFID pseudonyms that works with legacy, untrusted readers, requires only one message from tag to reader, and is scalable: decoding tag pseudonyms takes work logarithmic in the number of tags. Our scheme further allows for time-limited delegation, so that we can give an RFID reader the power to disambiguate a limited number of pseudonyms without further help from the Trusted Center. We show how RFID pseudonyms facilitate the transfer of ownership of RFID tags between mutually distrustful parties. Our scheme requires only limited cryptographic functionality from the tag: we need a pseudo-random function (PRF) and the ability to update tag state or to generate random numbers. Tag storage and communication requirements are modest: we give example parameters for a deployment of one million tags in which each tag stores only $$ bits, makes $$ PRF evaluations, and sends $$ bits each time it is read.

In 1986, D. V. Chudnovsky and G. V. Chudnovsky proposed to use formulae coming from Theta functions for the arithmetic in Jacobians of genus 2 curves. We follow this idea and derive fast formulae for the scalar multiplication in the Kummer surface associated to a genus 2 curve, using a Montgomery ladder. Our formulae can be used to design very efficient genus 2 cryptosystems that should be faster than elliptic curve cryptosystems in some hardware configurations.

Aggregate signatures are a useful primitive which allows to aggregate into a single and constant-length signature many signatures on different messages computed by different users. Specific proposals of aggregate signature schemes exist only for PKI-based scenarios. For identity-based scenarios, where public keys of the users are directly derived from their identities, the signature schemes proposed up to now do not seem to allow constant-length aggregation. We provide an intermediate solution to this problem, by designing a new identity-based signature scheme which allows aggregation when the signatures to be aggregated come all from the same signer. The new scheme is deterministic and enjoys some better properties than the previous proposals. We formally prove that the scheme is unforgeable, in the random oracle model, assuming that the Computational co-Diffie-Hellman problem is hard to solve.

The security of many recently proposed cryptosystems is based on the difficulty of solving large systems of quadratic multivariate polynomial equations. The classical algorithm for solving such a system is Buchberger's algorithm for constructing Gröbner bases. Another algorithm for solving such a system is XL algorithm. For sparse system, Buchberger's algorithm benefits from sparsity of the system, but its complexity is impractical and hard to determine. XL could not make a good use of sparse structure of the system, since XL has no good strategy of choosing the multiply monomials. In this paper, based on Extended Dixon Resultants, a new algorithm DR is proposed to solve systems of multivariate polynomial equations. The basic idea of DR is to apply Extended Dixon Resultants method to system of multivariate polynomial equations, by taking $$ as variables and $$ as parameter. The time complexity of DR technique is evaluated, it seems to be polynomial when the system is sparse and $$ and mixed volume is polynomial. As far as we know, it is the first algorithm which has better behavior than exhaustive search for some sparse systems over large field. Moreover, DR technique is compared with Buchberger's algorithm and XL technique in this paper. It is shown that DR is far more efficient than Buchberger's algorithm and XL when $$. DR is a quite efficient algorithm, it makes a good use of the sparsity of the sparse system. Besides its efficiency, another advantage of DR is that its complexity is easy to determine.

Cryptographic devices are vulnerable against the now well-known side channel leakage analysis. Secret data, such as keys, can be revealed by attacks like DPA, DEMA, CPA. However, this kind of attacks also exhibits wrong keys, this phenomenon being known as the "ghost peaks" problem and has been briefly explained in CPA. We give here a comprehension and analysis of the ghost peak problem that occurs in differential analysis regarding to different power consumption model and various weighting techniques.

In this paper, we propose a new concept ``Meta Ring Signature''. Suppose that a signature text work as a public key, we may achive a new digital signature ``Meta Signature'' such that, the signer of a signature text, in this paper we call basic signature, can sign on to another message by using the basic signature text as the public key of Meta signature scheme. First, we present a concept of Meta Ring Signature such that both basic signature and meta signature are Ring Signature.

Recently Eun-Kyung Ryu, Eun-Jun Yoon, and Kee-Young Yoo proposed an efficient ID-based authenticated key agreement with paring.They argued that it is secure and efficient. In this paper, we show this protocol is doesn't satisfy the Key-Compromise Impersonate property and it is not secure against key reveal attack. Then we propose our protocol from this protocol and shim's protocol, its security and efficiency was analyzed.

A new type of signature is presented in this paper, named adaptable group-oriented signature. In contrast with traditional group-oriented signature, the new one laid a strong emphasis on how to improve the signer¡¯s efficiency. In fact, this new type of group-oriented signature can be seen as a type of designated verifier signature. In contrast with the ordinary designated verifier signature, it does not designate one member but several members to independently verify the signature. The designated members, who can independently verify the signature, come into a group. This scheme can ensure the anonymity of the verifiers. This type of signature can be used in such system that the compute resource is limited, such as the broadcast protocols of the mobile telephone in the mobile networks.

The theoretical equivalence between the DLP and DHP problems was shown by Maurer in 1994. His work was then reexamined by Muzereau et al. for the special case of elliptic curves used in practical cryptographic applications. This paper improves on the latter and tries to get the tightest possible reduction in terms of computational equivalence, using Maurer's method.

In Sept.1990, the present authors firstly discussed DLP over composite number and presented an ID-based Key Sharing Scheme referred to as MK1. In 1991, Maurer and Yacobi presented a scheme, referred to as MY, which is similar to our scheme, MK1. Unfortunately the schemes MK1 and MY are not secure. In Dec.1990, the present authors presented a secure ID-based key sharing scheme referred to as MK2. With a rapid progress of computer power for the last 15 years, our proposed scheme would have more chance to be applied practically. Regrettably, it has not been widely known that (i) the schemes MY and MK1 are not secure, (ii) there exists a secure scheme, MK2. In this paper, we shall review MK2 and clarify the difference between MK2 and other schemes from the standpoint of security.

The goal of steganography is to pass secret messages by disguising them as innocent-looking covertexts. Real world stegosystems are often broken because they make invalid assumptions about the system's ability to sample covertexts. We examine whether it is possible to weaken this assumption. By modeling the covertext distribution as a stateful Markov process, we create a sliding scale between real world and provably secure stegosystems. We also show that insufficient knowledge of past states can have catastrophic results.

Ring signatures, first introduced by Rivest, Shamir, and Tauman, enable a user to sign a message so that a ring of possible signers (of which the user is a member) is identified, without revealing exactly which member of that ring actually generated the signature. In contrast to group signatures, ring signatures are completely ``ad-hoc'' and do not require any central authority or coordination among the various users (indeed, users do not even need to be aware of each other); furthermore, ring signature schemes grant users fine-grained control over the level of anonymity associated with any particular signature. This paper has two main areas of focus. First, we examine previous definitions of security for ring signature schemes and suggest that most of these prior definitions are too weak, in the sense that they do not take into account certain realistic attacks. We propose new definitions of anonymity and unforgeability which address these threats, and give separation results proving that our new notions are strictly stronger than previous ones. Second, we show the first constructions of ring signature schemes in the standard model. One scheme is based on generic assumptions and satisfies our strongest definitions of security. Two additional schemes are more efficient, but achieve weaker security guarantees and more limited functionality.

The Plutus file system introduced the notion of key rotation as a means to derive a sequence of temporally-related keys from the most recent key. In this paper we show that, despite natural intuition to the contrary, key rotation schemes cannot generically be used to key other cryptographic objects; in fact, keying an encryption scheme with the output of a key rotation scheme can yield a composite system that is insecure. To address these shortcomings, we introduce a new cryptographic object called a key regression scheme, and we propose three constructions that are provably secure under standard cryptographic assumptions. We implement key regression in a secure file system and empirically show that key regression can significantly reduce the bandwidth requirements of a content publisher under realistic workloads using lazy revocation. Our experiments also serve as the first empirical evaluation of either a key rotation or key regression scheme.

In this paper we address the question of representing the discriminant of an imaginary quadratic field with respect to the basis of a cyclotomic field. This representation allows us to parameterize new families of ordinary elliptic curves over finite prime fields suitable for pairing applications. In particular these curves have small discriminants greater than four and arbitrary embedding degree. Computational results are presented which support the theoretical findings.

Encryption algorithms are becoming more necessary to ensure the securely transmitted data over insecure communication channels. MICKEY-128 is a recently developed stream cipher with two major advantages: (i) the low hardware complexity, which results in small area and (ii) the high level of security. FPGA device was used for the performance demonstration. Some of the first results of implementing the stream cipher on an FPGA are reported. A maximum throughput equal to 170 Mbps can be achieved, with a clock frequency of 170 MHz.

We first present a new security 2-AK protocol, which is more secure and more efficient than previously proposed ones. Meanwhile, we point that Xie's ID-2-AK protocol modified from McCullagh-Barreto in CT-RSA 2005 doesn't provide protection against KCI attack likewise, and finally utilize the modular arithmetic, first proposed in MQV and also used in Kim, to get a modified new ID-2-AK protocol. On second thoughts, we give another ID-2-AK protocol utilizing the operation of addition in finite field like our forenamed 2-AK protocol. The two ID-2-AK protocols are in possession of all the desired security attributes. We also compare our new protocols with others in terms of computational cost and security properties.

In the paper we present the results which enable to calculate the nonlinearity of round functions with quite large dimensions e.g. 32x32 bits, which are used in some block ciphers. This can be applied to improve the resistance of these ciphers against linear cryptanalysis. The involved method of calculating the nonlinearity is rested on the notion of multi-dimensional Walsh transform. At the end we give the application to linear cryptanalysis of the TGR block cipher.

We consider the problem of overcoming (Distributed) Denial of Service (DoS) attacks by realistic adversaries that have knowledge of their attack's successfulness, e.g., by observing service performance degradation, or by eavesdropping on messages or parts thereof. A solution for this problem in a high-speed network environment necessitates lightweight mechanisms for differentiating between valid traffic and the attacker's packets. The main challenge in presenting such a solution is to exploit existing packet filtering mechanisms in a way that allows fast processing of packets, but is complex enough so that the attacker cannot efficiently craft packets that pass the filters. We show a protocol that mitigates DoS attacks by adversaries that can eavesdrop and (with some delay) adapt their attacks accordingly. The protocol uses only available, efficient packet filtering mechanisms based mainly on (addresses and) port numbers. Our protocol avoids the use of fixed ports, and instead performs `pseudo-random port hopping'. We model the underlying packet-filtering services and define measures for the capabilities of the adversary and for the success rate of the protocol. Using these, we provide a novel rigorous analysis of the impact of DoS on an end-to-end protocol, and show that our protocol provides effective DoS prevention for realistic attack and deployment scenarios.

Database outsourcing is an important emerging trend which involves data owners delegating their data management needs to an external service provider. In this model, a service provider hosts clients' databases and offers mechanisms to create, store, update and access (query) outsourced databases. Since a service provider is almost never fully trusted, security and privacy of outsourced data are important concerns. A core security requirement is the integrity and authenticity of outsourced databases. Whenever someone queries a hosted database, the results must be demonstrably authentic (with respect to the actual data owner) to ensure that the data has not been tampered with. Furthermore, the results must carry a proof of completeness which will allow the querier to verify that the server has not omitted any valid tuples that match the query predicate. Notable prior research (\cite{DpGmMcSs00, McNgDpGmKwSs02, PanTan04}) focused on so-called \textit{Authenticated Data Structures}. Another prior approach involved the use of special digital signature schemes. In this paper, we extend the state-of-the-art to provide both authenticity and completeness guarantees of query replies. Our work also analyzes the new approach for various base query types and compares the new approach with Authenticated Data Structures.\footnote{We also point out some possible security flaws in the approach suggested in the recent work of \cite{PanTan04}.}

A most critical and complex issue with regard to constrained devices in the ubiquitous and pervasive computing setting is secure key exchange. The restrictions motivate the investigation and discussion of alternative solutions. We suggest a low hardware-complexity solution for authenticated symmetric key exchange, using a Tree Parity Machine Rekeying Architecture. An authenticated key exchange is formulated from within the tree parity machine interaction concept and requires only few transmissions. It averts a Man-In-The-Middle attack and the currently known attacks on the non-numbertheoretic on principle. A key exchange can be performed within a few milliseconds, given typical limited bandwidth wireless communication channels. A flexible rekeying functionality enables the exploitation of the achievable key exchange rates. Characteristics of a standard-cell ASIC design realization as IP-core in 0.18 micron CMOS-technology are evaluated.

In this paper we propose a variant of RSA public key scheme, called ``Hidden Exponent RSA''. Based on this new scheme, we devised an efficient key distribution/management scheme for secure communication among devices in the context of pervasive computing, with emphasis on the simplicity and efficiency of the protocol. We show the new scheme is secure under the strong RSA assumption.

Simulatability constitutes the cryptographic notion of a secure refinement and has asserted its position as one of the fundamental concepts of modern cryptography. Although simulatability carefully captures that a distributed protocol does not behave any worse than an ideal specification, it however does not capture any form of liveness guarantees, i.e., that something good eventually happens in the protocol. We show how one can extend the notion of simulatability to comprise liveness guarantees by imposing specific fairness constraints on the adversary. As the common notion of fairness based on infinite runs and eventual message delivery is not suited for reasoning about polynomial-time, cryptographic systems, we propose a new definition of fairness that enforces the delivery of messages after a polynomial number of steps. We provide strengthened variants of this definition by granting the protocol parties explicit guarantees on the maximum delay of messages. The variants thus capture fairness with explicit timeout signals, and we further distinguish between fairness with local timeouts and fairness with global timeouts. We compare the resulting notions of fair simulatability, and provide separating examples that help to classify the strengths of the definitions and that show that the different definitions of fairness imply different variants of simulatability.

In this note, we describe how to achieve a simple yet substantial speed up of Miller's algorithm, when not using denominator elimination, and working over quadratic extension fields.

FOX is a new family of block ciphers presented recently, which is based upon some results on proven security and has high performances on various platforms. In this paper, we construct some distinguishers between 3-round FOX and a random permutation of the blocks space. By using integral attack and collision-searching techniques, the distinguishers are used to attack on 4, 5, 6 and 7-round of FOX64, 4 and 5-round FOX128. The attack is more efficient than previous integral attack on FOX. The complexity of improved integral attack is $$ on 4-round FOX128, $$ against 5-round FOX128 respectively. For FOX64, the complexity of improved integral attack is $$ on 4-round FOX64, $$ against 5-round FOX64, $$ against 6-round FOX64, $$ against 7-round FOX64 respectively. Therefore, 4-round FOX64/64, 5-round FOX64/128, 6-round FOX64/192, 7-round FOX64/256 and 5-round FOX128/256 are not immune to the attack in this paper.

We initiate the study of two-party cryptographic primitives with unconditional security, assuming that the adversary's {\em quantum}memory is of bounded size. We show that oblivious transfer and bit commitment can be implemented in this model using protocols where honest parties need no quantum memory, whereas an adversarial player needs quantum memory of size at least $$ in order to break the protocol, where $$ is the number of qubits transmitted. This is in sharp contrast to the classical bounded-memory model, where we can only tolerate adversaries with memory of size quadratic in honest players' memory size. Our protocols are efficient, non-interactive and can be implemented using today's technology. On the technical side, a new entropic uncertainty relation involving min-entropy is established.

Non-interactive zero-knowledge (NIZK) systems are fundamental cryptographic primitives used in many constructions, including CCA2-secure cryptosystems, digital signatures, and various cryptographic protocols. What makes them especially attractive, is that they work equally well in a concurrent setting, which is notoriously hard for interactive zero-knowledge protocols. However, while for interactive zero-knowledge we know how to construct statistical zero-knowledge argument systems for all NP languages, for non-interactive zero-knowledge, this problem remained open since the inception of NIZK in the late 1980's. Here we resolve two problems regarding NIZK: - we construct the first perfect NIZK argument system for any NP language. - we construct the first UC-secure NIZK protocols for any NP language in the presence of a dynamic/adaptive adversary. While it was already known how to construct efficient prover computational NIZK proofs for any NP language, the known techniques yield large common reference strings and large NIZK proofs. As an additional implication of our techniques, we considerably reduce both the size of the common reference string and the size of the proofs.

The emphasis of this paper is to focus on key agreement. To this aim, we address a self-contained, up-to-date presentation of key agreement protocols at high level. We have attempted to provide a brief but fairly complete survey of all these schemes.

We describe a new encryption technique that is secure in the standard model against adaptive chosen ciphertext (CCA2) attacks. We base our method on two very efficient Identity-Based Encryption (IBE) schemes without random oracles due to Boneh and Boyen, and Waters. Unlike previous CCA2-secure cryptosystems that use IBE as a black box, our approach is endogenous, very simple, and compact. It makes direct use of the underlying IBE structure, and requires no cryptographic primitive other than the IBE scheme itself. This conveys several advantages. We achieve shorter ciphertext size than the best known instantiations of the other methods, and our technique is as efficient as the Boneh and Katz method (and more so than that of Canetti, Halevi, and Katz). Further, our method operates nicely on hierarchical IBE, and since it allows the validity of ciphertexts to be checked publicly, it can be used to construct systems with non-interactive threshold decryption. In this paper we describe two main constructions: a full encryption system based on the Waters adaptive-ID secure IBE, and a KEM based on the Boneh-Boyen selective-ID secure IBE. Both systems are shown CCA2-secure in the standard model, the latter with a tight reduction. We discuss several uses and extensions of our approach, and draw comparisons with other schemes that are provably secure in the standard model.

Certificateless public key cryptography was introduced to overcome the key escrow limitation of the identity-based cryptography. It combines the advantages of the identity-based cryptography and the traditional PKI. Recently, Dae Hyun Yum1 and Pil Joong Lee have proposed a generic series construction model of certificateless public key encryption (CL-PKE) which is built from generic primitives: identity-based encryption and public key encryption. However, this model pays much attention on the generic construction and neglects the nice properties of the bilinear pairings. In this paper, we propose an efficient CL-PKE scheme which is based on the nice algebraic properties of Weil pairing. The scheme works in a kind of parallel model and it is more efficient on computation or published public key information than the existing schemes.

We provide unconditional constructions of concurrent statistical zero-knowledge proofs for a variety of non-trivial problems (not known to have probabilistic polynomial-time algorithms). The problems include Graph Isomorphism, Graph Nonisomorphism, Quadratic Residuosity, Quadratic Nonresiduosity, a restricted version of Statistical Difference, and approximate versions of the (coNP forms of the) Shortest Vector Problem and Closest Vector Problem in lattices. For some of the problems, such as Graph Isomorphism and Quadratic Residuosity, the proof systems have provers that can be implemented in polynomial time (given an NP witness) and have \tilde{O}(log n) rounds, which is known to be essentially optimal for black-box simulation. To our best of knowledge, these are the first constructions of concurrent zero-knowledge protocols in the asynchronous model (without timing assumptions) that do not require complexity assumptions (such as the existence of one-way functions).

In this paper, for given $$ with $$ and $$ different primes and a unimodular polynomial with coefficients in $$ mod $$, we give a public key cryptosystem. When the degree of the polynomial is $$, the system is just the famous RSA system. And when the degree bigger than $$, the system is usually more secure than the original RSA systems. Some part-correct systems are introduced so that the period of any message in these systems under the Simmons attack are bigger than that of any message in the RSA system.

Imagine there is certain content we want to maintain private until some particular event occurs, when we want to have it automatically disclosed. Suppose furthermore, that we want this done in a (possibly) malicious host. Say, the confidential content is a piece of code belonging to a computer program that should remain ciphered and then ``be triggered'' (i.e., deciphered and executed) when the underlying system satisfies a preselected condition which must remain secret after code inspection. In this work we present different solutions for problems of this sort, using different ``declassification'' criteria, based on a primitive we call {\em secure triggers}. We establish the notion of secure triggers in the universally-composable security framework of [Canetti~2001] and introduce several examples. Our examples demonstrate that a new sort of obfuscation is possible. Finally, we motivate its use with applications in realistic scenarios.

Secure, anonymous and unobservable communication is becoming increasingly important due to the gradual erosion of privacy in many aspects of everyday life. This prompts the need for various anonymity- and privacy-enhancing techniques, e.g., group signatures, anonymous e-cash and secret handshakes. In this paper, we investigate an interesting and practical cryptographic construct Oblivious Signature-Based Envelopes (OS-BEs) recently introduced in [15]. OSBEs are very useful in anonymous communication since they allow a sender to communicate information to a receiver such that the receiver s rights (or roles) are unknown to the sender. At the same time, a receiver can obtain the information only if it is authorized to access it. This makes OSBEs a natural fit for anonymity-oriented and privacy-preserving applications, such as Automated Trust Negotiation and Oblivious Subscriptions. Previous results yielded three OSBE constructs: one based on RSA and two based on Identity-Based Encryption (IBE). Our work focuses on the ElGamal signature family: we succeed in constructing practical and secure OSBE schemes for several well-known signature schemes, including: Schnorr, Nyberg-Rueppel, ElGamal and DSA. As experiments with the prototype implementation il-lustrate, our schemes are more efficient than previous techniques. Furthermore, we show that some OSBE schemes, despite offering affiliation privacy for the receiver, introduce no additional cost over schemes that do not offer this feature.

We introduce a new cryptographic primitive called the blind coupon mechanism (BCM). In effect, the BCM is an authenticated bit-commitment, which is AND-homomorphic. It has not been known how to construct such commitments before. We show that the BCM has natural and important applications. In particular, we use it to construct a mechanism for transmitting alerts undetectably in a message-passing system of n nodes. Our algorithms allow an alert to quickly propagate to all nodes without its source or existence being detected by an adversary, who controls all message traffic. Our proofs of security are based on a new subgroup escape problem, which seems hard on certain groups with bilinear pairings and on elliptic curves over the ring Zn.

In this paper, we develop a new attack on Damgård-Merkle hash functions, called the \emph{herding attack}, in which an attacker who can find many collisions on the hash function by brute force can first provide the hash of a message, and later ``herd'' any given starting part of a message to that hash value by the choice of an appropriate suffix. We introduce a new property which hash functions should have--Chosen Target Forced Prefix (CTFP) preimage resistance--and show the distinction between Damgård-Merkle construction hashes and random oracles with respect to this property. We describe a number of ways that violation of this property can be used in arguably practical attacks on real-world applications of hash functions. An important lesson from these results is that hash functions susceptible to collision-finding attacks, especially brute-force collision-finding attacks, cannot in general be used to prove knowledge of a secret value

Recent research has produced a number of viable side-channel attack methods based on the data-dependant behaviour of microprocessor cache memory. Most proposed defence mechanisms are software based and mainly act to increase the attackers workload rather than obviate the attack entirely. In this paper we investigate the use of a configurable cache architecture to provide hardware assisted defence. By exposing the cache to the processor and allowing it to be dynamically configured to match the needs of a given application, we provide opportunity for higher performance as well as security.

We first present a protocol which reduces 1-out-of-$$ oblivious transfer OT$$ to 1-out-of-$$ oblivious transfer OT$$ for $$ in random oracle model, and show that the protocol is secure against malicious sender and semi-honest receiver. Then, by employing a cut-and-choose technique, we obtain a variant of the basic protocol which is secure against a malicious receiver.

Public key cryptography has been invented to overcome some key management problems in open networks. Although nearly all aspects of public key cryptography rely on the existence of trapdoor one-way functions, only a very few candidates of this primitive have been observed yet. In this paper, we introduce a new trapdoor one-way permutation based on the hardness of factoring integers of $$-type. We also propose a variant of this function with a different domain that provides some advantages for practical applications. To confirm this statement, we develop a simple hybrid encryption scheme based on our proposed trapdoor permutation that is CCA-secure in the random oracle model.

In this paper, we show explicitly the classes of elliptic and hyperelliptic curves of low genera defined over extension fields, which have weak coverings, i.e. their Weil restrictions can be attacked by either index calculus attacks to hyperelliptic curves or Diem's recent attack to non-hyperelliptic curves. In particular, we show how to construct such coverings from these curves and analyze density of the curves for them such construction is possible.

Modular exponentiation in an abelian group is one of the most frequently used mathematical primitives in modern cryptography. {\em Batch verification} is to verify many exponentiations simultaneously. We propose two fast batch verification algorithms. The first one makes use of exponents with small weight, called {\em sparse exponents}, which is asymptotically 10 times faster than the individual verification and twice faster than the previous works without security loss. The second one is applied only to elliptic curves defined over small finite fields. Using sparse Frobenius expansion with small integer coefficients, we propose a complex exponent test which is four times faster than the previous works. For example, each exponentiation in one batch requires asymptotically 9 elliptic curve additions in some elliptic curves for $$ security.

$$ is a $$-ary code of length $$. A word $$ is called a descendant of a coalition of codewords $$ of $$ if at each position $$, $$, $$ inherits a symbol from one of its parents, that is $$. A $$-secure frameproof code ($$-SFPC) ensures that any two disjoint coalitions of size at most $$ have no common descendant. Several probabilistic methods prove the existance of codes but there are not many explicit constructions. Indeed, it is an open problem in [J. Staddon et al., IEEE Trans. on Information Theory, 47 (2001), pp. 1042--1049] to construct explicitly $$-ary 2-secure frameproof code for arbitrary $$. In this paper, we present several explicit constructions of $$-ary 2-SFPCs. These constructions are generalisation of the binary inner code of the secure code in [V.D. To et al., Proceeding of IndoCrypt'02, LNCS 2551, pp. 149--162, 2002]. The length of our new code is logarithmically small compared to its size.

The original presentation of the NTRUSign signature scheme gave a set of parameters that were claimed to give 80 bits of security, but did not give a general recipe for generating parameter sets to a specific level of security. In line with recent research on NTRUEncrypt, this paper presents an outline of such a recipe for NTRUSign. We also present certain technical advances upon which we intend to build in subsequent papers.

This paper discusses cryptography based on the property of chaotic synchronization. Specifically, it is about Round III of such a cryptographic method. Round I showed the feasibility of using chaotic synchronization for cryptography. Round II consisted of a method to counter attack. This paper is Round III and shows how to counter the counter attacks. First, we show numerical evidence that synchronization is possible between two Lorenz systems if one system sends information about $$ at a slower rate. The second system evolves on its own, except that when it receives a signal from the first system, it replaces its own value of $$ by the received $$. We have found that the two systems eventually synchronize, but often after a long time. Therefore, we have devised a technique to speed-up this synchronization. Once this is done, it is possible for the authorized receiver (with the possession of the initial super-key) to keep synchronizing with slowly sampled inputs, whereas the known methods of Round II do not help an eavesdropper.

A mobile agent is a mobile program capable of maintaining its execution states as it migrates between different execution platforms. A key security problem in the mobile agent paradigm is that of trust: How to ensure that the past itinerary (of execution platforms) claimed by the agent is correct. This is necessary in order to establish a reasonable level of trust for the agent before granting execution privileges. In this paper we describe a protocol using bilinear pairings that enables trust relationships to be formed between agent platforms in an ad-hoc manner without actively involving any trusted third party. This protocol can be used to authenticate agents before granting execution privileges. The main idea behind our approach is the concept of `one-way' chaining. Our scheme has chosen ciphertext security assuming the hardness of the Bilinear Diffie Hellman Problem (BDHP).

We describe several software side-channel attacks based on inter-process leakage through the state of the CPU's memory cache. This leakage reveals memory access patterns, which can be used for cryptanalysis of cryptographic primitives that employ data-dependent table lookups. The attacks allow an unprivileged process to attack other processes running in parallel on the same processor, despite partitioning methods such as memory protection, sandboxing and virtualization. Some of our methods require only the ability to trigger services that perform encryption or MAC using the unknown key, such as encrypted disk partitions or secure network links. Moreover, we demonstrate an extremely strong type of attack, which requires knowledge of neither the specific plaintexts nor ciphertexts, and works by merely monitoring the effect of the cryptographic process on the cache. We discuss in detail several such attacks on AES, and experimentally demonstrate their applicability to real systems, such as OpenSSL and Linux's dm-crypt encrypted partitions (in the latter case, the full key can be recovered after just 800 writes to the partition, taking 65 milliseconds). Finally, we describe several countermeasures which can be used to mitigate such attacks.

We examine various indistinguishability-based proof models for key establishment protocols, namely the Bellare & Rogaway (1993, 1995), the Bellare, Pointcheval, & Rogaway (2000), and the Canetti & Krawczyk (2001) proof models. We then consider several variants of these proof models, identify several subtle differences between these variants and models, and compare the relative strengths of the notions of security between the models. For each of the pair of relations between the models (either an implication or a non-implication), we provide proofs or counter-examples to support the observed relations. We also reveal a drawback with the original formulation of the Bellare, Pointcheval, & Rogaway (2000) model, whereby the Corrupt query is not allowed. As a case study, we use the Abdalla & Pointcheval (2005) three-party password-based key exchange protocol (3PAKE), which carries a proof of security in the Bellare, Pointcheval, & Rogaway (2000) model. We reveal a previously unpublished flaw in the protocol, and demonstrate that this attack would not be captured in the model due to the omission of the Corrupt query.