We study the problem of searching on data that is encrypted using a public key system. Consider user Bob who sends email to user Alice encrypted under Alice's public key. An email gateway wants to test whether the email contains the keyword `urgent' so that it could route the email accordingly. Alice, on the other hand does not wish to give the gateway the ability to decrypt all her messages. We define and construct a mechanism that enables Alice to provide a key to the gateway that enables the gateway to test whether the word `urgent' is a keyword in the email without learning anything else about the email. We refer to this mechanism as <I>Public Key Encryption with keyword Search</I>. As another example, consider a mail server that stores various messages publicly encrypted for Alice by others. Using our mechanism Alice can send the mail server a key that will enable the server to identify all messages containing some specific keyword, but learn nothing else. We define the concept of public key encryption with keyword search and give several constructions.

At Eurocrypt'91, Chaum and van Heyst introduced the concept of group signature. In such a scheme, each group member is allowed to sign messages on behalf of a group anonymously. However, in case of later disputes, a designated group manager can open a group signature and identify the signer. In recent years, researchers have proposed a number of new group signature schemes and improvements with different levels of security. In this paper, we present a security analysis of five group signature schemes proposed in [25,27,18,30,10]. By using the same method, we successfully identify several universally forging attacks on these schemes. In our attacks, anyone (not necessarily a group member) can forge valid group signatures on any messages such that the forged signatures cannot be opened by the group manager. We also discuss the linkability of these schemes, and further explain why and how we find the attacks.

Universal Designated-Verifier Signature (UDVS) schemes are digital signature schemes with additional functionality which allows any holder of a signature to designate the signature to any desired designated-verifier such that the designated-verifier can verify that the message was signed by the signer, but is unable to convince anyone else of this fact. Since UDVS schemes reduce to standard signatures when no verifier designation is performed, it is natural to ask how to extend the classical Schnorr or RSA signature schemes into UDVS schemes, so that the existing key generation and signing implementation infrastructure for these schemes can be used without modification. We show how this can be efficiently achieved, and provide proofs of security for our schemes in the random oracle model.

Motivated by privacy issues associated with dissemination of signed digital certificates, we define a new type of signature scheme called a ‘Universal Designated-Verifier Signature’ (UDVS). A UDVS scheme can function as a standard publicly-verifiable digital signature but has additional functionality which allows any holder of a signature (not necessarily the signer) to designate the signature to any desired designated-verifier (using the verifier’s public key). Given the designated-signature, the designated-verifier can verify that the message was signed by the signer, but is unable to convince anyone else of this fact. We propose an efficient deterministic UDVS scheme constructed using any bilinear group-pair. Our UDVS scheme functions as a standard Boneh-Lynn-Shacham (BLS) signature when no verifier-designation is performed, and is therefore compatible with the key-generation, signing and verifying algorithms of the BLS scheme. We prove that our UDVS scheme is secure in the sense of our unforgeability and privacy notions for UDVS schemes, under the Bilinear Diffie-Hellman (BDH) assumption for the underlying group-pair, in the random-oracle model. We also demonstrate a general constructive equivalence between a class of unforgeable and unconditionally-private UDVS schemes having unique signatures (which includes the deterministic UDVS schemes) and a class of ID-Based Encryption (IBE) schemes which contains the Boneh-Franklin IBE scheme but not the Cocks IBE scheme.

Denoting by $$ the elliptic-curve double-and-add multiplication of a public base point $$ by a secret $$, we show that allowing an adversary access to the projective representation of $$ results in information being revealed about $$. Such access might be granted to an adversary by a poor software implementation that does not erase the $$ coordinate of $$ from the computer's memory or by a computationally-constrained secure token that sub-contracts the affine conversion of $$ to the external world. From a wider perspective, our result proves that the choice of representation of elliptic curve points {\sl can reveal} information about their underlying discrete logarithms, hence casting potential doubt on the appropriateness of blindly modelling elliptic-curves as generic groups. As a conclusion, our result underlines the necessity to sanitize $$ after the affine conversion or, alternatively, randomize $$ before releasing it out.

We present a secure unauthenticated as well as an authenticated multi party key agreement protocol. The authenticated version of our protocol uses ternary trees and is based on bilinear maps and Joux's three party protocol. The number of rounds, computation/communication complexity of our protocol compares favourably with previously known protocols. The authenticated version of our protocol also uses ternary trees and is based on public IDs and Key Generation Centres. The authenticated version of our protocol is more efficient than all previously known authenticated key agreement protocols.

Ma and Chen proposed a new authenticated encryption scheme with public verifiability. This scheme requires less computational costs and communication overheads than the conventional signature-then-encryption approaches. In this letter, we show that the Ma-Chen scheme does not satisfy three security properties: unforgeability, confidentiality and non-repudiation.

Forward-secure signatures are used to defeat signature forgeries in cases of key exposure. In this model, the signature key evolves with time and it is computationally infeasible for an adversary to forge a signature for some time-period prior to the key’s exposure. In this paper a new forward-secure digital signature scheme is presented, which is based on the use of bilinear maps recently advocated by Boneh and Franklin [9]. This scheme is efficiently constructed and can be used with a large number of time periods with a log magnitude complexity. The signing and key-update operations are very efficient when compared with other previously available schemes. A formal definition, as well as a detailed analysis of the security performance or this scheme, is presented. The security proof for this scheme is based on the Computational Diffie-Hellman assumption, which leads to a unique approach to proving security in the random oracle model. Furthermore, within the proof both the hash oracle and the signing oracle are constructed in an innovative manner.

This paper introduces new notions of asymptotic proofs, PT(polynomial-time)-extensions, PTM(polynomial-time Turing machine)-$$-consistency, etc. on formal theories of arithmetic including PA (Peano Arithmetic). An asymptotic proof is a set of infinitely many formal proofs, which is introduced to define and characterize a property, PTM-$$-consistency, of a formal theory. Informally speaking, PTM-$$-consistency is a {\it polynomial-time bounded} version (in asymptotic proofs) of $$-consistency, and characterized in two manners: (1) (in the light of the {\it extension of PTM to TM}) the resource {\it unbounded} version of PTM-$$-consistency is equivalent to $$-consistency, and (2) (in the light of {\it asymptotic proofs by PTM}) a PTM-$$-{\it inconsistent} theory includes an axiom that only a super-polynomial-time Turing machine can prove asymptotically over PA, under some assumptions. This paper shows that {\it P$$NP (more generally, any super-polynomial-time lower bound in PSPACE) is unprovable in a PTM-$$-consistent theory $$}, where $$ is a consistent PT-extension of PA (although this paper does not show that P$$NP is unprovable in PA, since PA has not been proven to be PTM-$$-consistent). This result implies that to prove P$$NP by any technique requires a PTM-$$-{\it inconsistent} theory, which should include an axiom that only a super-polynomial-time machine can prove asymptotically over PA (or implies a super-polynomial-time computational upper bound) under some assumptions. This result is a kind of generalization of the result of ``Natural Proofs'' by Razborov and Rudich, who showed that to prove ``P$$NP'' by a class of techniques called ``Natural Proofs'' implies a super-polynomial-time (e.g., sub-exponential-time) algorithm that can break a typical cryptographic primitive, a pseudo-random generator. Our result also implies that any relativizable proof of P$$NP requires the {\it resource unbounded version} of \PTM-$$-{\it inconsistent} theory, $$-{\it inconsistent} theory, which suggests another negative result by Baker, Gill and Solovay that no relativizable proof can prove ``P$$NP'' in PA, which is a $$-consistent theory. Therefore, our result gives a unified view to the existing two major negative results on proving P$$NP, Natural Proofs and relativizable proofs, through the two manners of characterization of PTM-$$-consistency. We also show that the PTM-$$-consistency of $$ cannot be proven in any PTM-$$-consistent theory $$, where $$ is a consistent PT-extension of $$. That is, to prove the independence of P vs NP from $$ by proving the PTM-$$-consistency of $$ requires a PTM-$$-{\it inconsistent} theory, or implies a super-polynomial-time computational upper bound under some assumptions. This seems to be related to the results of Ben-David and Halevi and Kurz, O'Donnell and Royer, who showed that to prove the independence of P vs NP from PA using any currently known mathematical paradigm implies an extremely-close-to-polynomial-time (but still super-polynomial-time) algorithm that can solve NP-complete problems. Based on this result, we show that {\it the security of any computational cryptographic scheme is unprovable} in the setting where adversaries and provers are modeled as polynomial-time Turing machines and only a PTM-$$-consistent theory is allowed to prove the security.

A number $$ is a safe prime if both $$ and $$ are prime. This note describes a method of generating safe primes that is considerably faster than repeatedly generating random primes $$ until $$ is also prime.

The VMPC Stream Cipher is a simple encryption algorithm, designed as a proposed practical application of the VMPC one-way function. The general structure of the Cipher is based on an internal 256-element permutation. The VMPC Cipher, together with its Key Scheduling Algorithm, were designed in particular to eliminate some of the known weaknesses characteristic of the alleged RC4 keystream generator.

DES is not only very widely implemented and used today, but triple DES and other derived schemes will probably still be around in ten or twenty years from now. We suggest that, if an algorithm is so widely used, its security should still be under scrutiny, and not taken for granted. In this paper we study the S-boxes of DES. Many properties of these are already known, yet usually they concern one particular S-box. This comes from the known design criteria on DES, that strongly suggest that S-boxes have been chosen independently of each other. On the contrary, we are interested in properties of DES S-boxes that concern a subset of two or more DES S-boxes. For example we study the properties related to Davies-Murphy attacks on DES, recall the known uniformity criteria to resist this attack, and discuss a stronger criterion. More generally we study many different properties, in particular related to linear cryptanalysis and algebraic attacks. The interesting question is to know if there are any interesting properties that hold for subsets of S-boxes bigger than 2. Such a property has already been shown by Shamir at Crypto'85 (and independently discovered by Franklin), but Coppersmith et al. explained that it was rather due to the known S-box design criteria. Our simulations confirm this, but not totally. We also present several new properties of similar flavour. These properties come from a new type of algebraic attack on block ciphers that we introduce. What we find is not easily explained by the known S-box design criteria, and the question should be asked if the S-boxes of DES are related to each other, or if they follow some yet unknown criteria. Similarly, we also found that the s5DES S-boxes have an unexpected common structure that can be exploited in a certain type of generalised linear attack. This fact substantially decreases the credibility of s5DES as a DES replacement. This paper has probably no implications whatsoever on the security of DES.

We introduce the notion of certificate-based encryption. In this model, a certificate -- or, more generally, a signature -- acts not only as a certificate but also as a decryption key. To decrypt a message, a keyholder needs both its secret key and an up-to-date certificate from its CA (or a signature from an authorizer). Certificate-based encryption combines the best aspects of identity-based encryption (implicit certification) and public key encryption (no escrow). We demonstrate how certificate-based encryption can be used to construct an efficient PKI requiring less infrastructure than previous proposals, including Micali's Novomodo, Naor-Nissim and Aiello-Lodha-Ostrovsky.

We show how to construct a CCA-secure public-key encryption scheme from any CPA-secure identity-based encryption (IBE) scheme. Our conversion from IBE to a CCA-secure scheme is simple, efficient, and provably secure in the standard model (i.e., security of the resulting scheme does not rely on the random oracle model). In addition, the resulting scheme achieves CCA security even if the underlying IBE scheme satisfies only a ``weak'' notion of security which is known to be achievable in the standard model based on the bilinear Diffie-Hellman assumption. Thus, our results yield a new construction of CCA-secure public-key encryption in the standard model. Interestingly, the resulting scheme avoids any non-interactive proofs of ``well-formedness'' which were shown to underlie all previously-known constructions. We also extend our technique to obtain a simple and reasonably efficient method for securing any BTE scheme against adaptive chosen-ciphertext attacks. This, in turn, yields more efficient constructions of CCA-secure (hierarchical) identity-based and forward-secure encryption schemes in the standard model. Our results --- building on previous black-box separations --- rule out black-box constructions of IBE from CPA-secure public-key encryption.

In a practical system, a message is often encrypted more than once by different encryptions, here called multiple encryption, to enhance its security. Additionally, new features may be achieved by multiple encrypting a message for a scheme, such as the key-insulated cryptosystems \cite{DKXY02} and anonymous channels \cite{Cha81}. Intuitively, a multiple encryption should remain ``secure'', whenever there is one component cipher unbreakable in it. In NESSIE's latest Portfolio of recommended cryptographic primitives (Feb. 2003), it is suggested to use multiple encryption with component ciphers based on different assumptions to acquire long term security. However, in this paper we show this needs careful discussion. Especially, this may \emph{not} be true according to (adaptive) chosen ciphertext attack ({\sf CCA}), even with all component ciphers {\sf CCA} secure. We define an extended version of {\sf CCA} called \emph{chosen ciphertext attack for multiple encryption} ({\sf ME-CCA}) to emulate real world partial breaking of assumptions, and give constructions of multiple encryption satisfying {\sf ME-CCA} security. Since {\sf CCA} security seems so stringent, we further relax it by introducing \emph{weak} {\sf ME-CCA} ({\sf ME-wCCA}), and prove {\sf IND-ME-wCCA} secure multiple encryption can be acquired from {\sf IND-gCCA} secure component ciphers. We also study the relation of various security notions for multiple encryption. We then apply these results to key-insulated cryptosystem. It is only previously known in \cite{DKXY02} that a generic construction exists provably secure against {\sf CPA} attack, however, we prove that this generic construction is in fact secure against {\sf ME-wCCA} by choosing all components {\sf IND-CCA} secure. We also give an efficient generic construction of key-insulated cryptosystem, which is so far the \emph{first} generic construction provably secure against {\sf CCA} (in the random oracle model).

One of the recent thrust areas in research on hyperelliptic curve cryptography has been to obtain explicit formulae for performing arithmetic in the Jacobian of such curves. We continue this line of research by obtaining parallel versions of such formulae. Our first contribution is to develop a general methodology for obtaining parallel algorithm of any explicit formula. Any parallel algorithm obtained using our methodology is provably optimal in the number of multiplication rounds. We next apply this methodology to Lange's explicit formula for arithmetic in genus 2 hyperelliptic curve -- both for the affine coordinate and inversion free arithmetic versions. Since encapsulated add-and-double algorithm is an important countermeasure against side channel attacks, we develop parallel algorithms for encapsulated add-and-double for both of Lange's versions of explicit formula. For the case of inversion free arithmetic, we present parallel algorithms using 4, 8 and 12 multipliers. All parallel algorithms described in this paper are optimal in the number of parallel rounds. One of the conclusions from our work is the fact that the parallel version of inversion free arithmetic is more efficient than the parallel version of arithmetic using affine coordinates.

The VMPC function is a combination of two basic operations: permutation composition and integer addition. The function resulting from this combination shows to have very high resistance to inverting. Computational effort of about 2^260 operations is estimated to be required to invert the VMPC function. The value of the function can be computed with 3 elementary computer processor instructions per byte. An open question is whether the function's simplicity raises a realistic chance that the lower bound on the complexity of inverting it might be proved.

In PODC 2003, Park et al. \cite{PCSR} first introduce a connection between fair exchange and sequential two-party multi-signature scheme and provide a novel method of constructing fair exchange protocol by distributing the computation of RSA signature. This approach avoids the design of verifiable encryption scheme at the expense of having co-signer store a piece of prime signer's secret key. Dodis and Reyzin \cite{DR} showed that the protocol in \cite{PCSR} is totally breakable in the registration phase, then presented a remedy scheme which is provably secure in the random oracle model, by utilizing Boldyreva non-interactive two-party multi-signature scheme \cite{Bo}. Security in the random oracle model does not imply security in the real world. In this paper, we provide the first two efficient committed signatures which are provably secure in the standard complexity model from strong RSA assumption. Then we construct efficient optimistic fair exchange protocols from those new primitives.

We describe several notions of ``cryptographic transforms,'' symmetric schemes designed to meet a variety of privacy and authenticity goals. We consider goals, such as replay-avoidance and in-order packet delivery, that have not been fully addressed in previous works in this area. We then provide an analysis of possible ways to combine standard encryption and message authentication schemes in order to provably meet these goals. Our results further narrow the gap between the provable-security results from the theoretical community and the needs of developers who implement real systems.

In 1983, Patterson and Wiedemann constructed Boolean functions on $$ input variables having nonlinearity strictly greater than $$. Construction of Boolean functions on odd number of variables with such high nonlinearity was not known earlier and also till date no other construction method of such functions are known. We note that the Patterson-Wiedemann construction can be understood in terms of interleaved sequences as introduced by Gong in 1995 and subsequently these functions can be described as repetitions of a particular binary string. As example we elaborate the cases for $$. Under this framework, we map the problem of finding Patterson-Wiedemann functions into a problem of solving a system of linear inequalities over the set of integers and provide proper reasoning about the choice of the orbits. This, in turn, reduces the search space. Similar analysis also reduces the complexity of calculating autocorrelation and generalized nonlinearity for such functions. In an attempt to understand the above construction from the group theoretic view point, we characterize the group of all $$-linear transformations of $$ which acts on $$.

Safe primes are prime numbers of the form $$ where $$ is prime. This note introduces a simple method for doubling the speed of safe prime generation. The method is particularly suited to settings where a large number of RSA moduli must be generated.

Security against adaptive chosen ciphertext attacks (or, CCA security) has been accepted as the standard requirement from encryption schemes that need to withstand active attacks. In particular, it is regarded as the appropriate security notion for encryption schemes used as components within general protocols and applications. Indeed, CCA security was shown to suffice in a large variety of contexts. However, CCA security often appears to be somewhat {\em too strong:} there exist encryption schemes (some of which come up naturally in practice) that are not CCA secure, but seem sufficiently secure ``for most practical purposes.'' We propose a relaxed variant of CCA security, called {\sf Replayable CCA (RCCA)} security. RCCA security accepts as secure the non-CCA (yet arguably secure) schemes mentioned above; furthermore, it suffices for most existing applications of CCA security. We provide three formulations of RCCA security. The first one follows the spirit of semantic security and is formulated via an ideal functionality in the universally composable security framework. The other two are formulated following the indistinguishability and non-malleability approaches, respectively. We show that the three formulations are equivalent in most interesting cases.

We study the problem of securely extending the domain of a collision resistant compression function. A new construction based on directed acyclic graphs is described. This generalizes the usual iterated hashing constructions. Our main contribution is to introduce a new technique for hashing arbitrary length strings. Combined with DAG based hashing, this technique gives a new hashing algorithm. The amount of padding and the number of invocations of the compression function required by the new algorithm is smaller than the general \MD algorithm. Lastly, we describe the design of a new parallel hash algorithm.

We consider the impact of the possibility of decryption failures in proofs of security for padding schemes, where these failures are both message and key dependent. We explain that an average case failure analysis is not necessarily sufficient to achieve provable security with existing CCA2-secure schemes. On a positive note, we introduce NAEP, an efficient padding scheme similar to PSS-E designed especially for the NTRU one-way function. We show that with this padding scheme we can prove security in the presence of decryption failures, under certain explicitly stated assumptions. We also discuss the applicability of proofs of security to instantiated cryptosystems in general, introducing a more practical notion of cost to describe the power of an adversary.

We consider the fundamental problem of authenticated group key exchange among $$ parties within a larger and insecure public network. A number of solutions to this problem have been proposed; however, all provably-secure solutions thus far are not scalable and, in particular, require $$ rounds. Our main contribution is the first {\em scalable} protocol for this problem along with a rigorous proof of security in the standard model under the DDH assumption; our protocol uses a constant number of rounds and requires only $$ ``full'' modular exponentiations per user. Toward this goal and of independent interest, we first present a scalable compiler that transforms any group key-exchange protocol secure against a passive eavesdropper to an \emph{authenticated} protocol which is secure against an active adversary who controls all communication in the network. This compiler adds only one round and $$ communication (per user) to the original scheme. We then prove secure --- against a passive adversary --- a variant of the two-round group key-exchange protocol of Burmester and Desmedt. Applying our compiler to this protocol results in a provably-secure three-round protocol for \emph{authenticated} group key exchange which also achieves forward secrecy.

In this paper, we introduce HAshed Random Preloaded Subset (HARPS) key distribution, a scalable key predistribution scheme employing only symmetric crypto primitives. HARPS is ideally suited for resource constrained nodes that need to operate without a trusted authority (TA) for extended periods (as is the case for nodes forming mobile ad hoc networks (MANETs)). The performance of HARPS is compared with that of two other key predistribution schemes. The first, RPS, is a based on random intersection of keys preloaded in nodes. The second, is (a slight modification to) a scheme proposed by Leighton and Micali (LM). HARPS is a generalization of both RPS and LM. All the three schemes, rely on some degree of resistance to hardware tampering, and have probabilistic measures for the ``merit'' of the system. The merit of the schemes is a function of the probability that an attacker who has compromised N nodes (or has access to keys buried in N nodes) can ``eavesdrop'' on a conversation between R nodes (R=2 for unicast communications). We analyze and compare the performance of the three schemes for unicast and multicast communications. We show that HARPS has significant performance advantage over SIMS and LM.

Stream ciphers are often used in applications where high speed and low delay are a requirement. The Solitaire stream cipher was developed by B. Schneier as a paper-and-pencil cipher. Solitaire gets its security from the inherent randomness in a shuffled deck of cards. In this paper we investigate semigroups and groups properties of the Solitaire stream cipher and its regular modifications.

When data or the processing on the data have some uncertainty, discretization of those data can lead to significantly different output. For example, in certain graphical password schemes, a slight uncertainty in the clicking places can produce a different password. We present a discretization method, called robust discretization, which gives stable outputs in the presence of uncertainties. Robust discretization enables us to implement graphical password schemes that are much more flexible and versatile than previously know ones.

Chameleon signatures are non-interactive signatures based on a hash-and-sign para\-digm, and similar in efficiency to regular signatures. The distinguishing characteristic of chameleon signatures is that their are non-transferable, with only the designated recipient capable of asserting its validity. In this paper, we introduce the first identity-based chameleon hash function. The general advantages of identity-based cryptography over conventional schemes relative to key distribution are even more pronounced in a chameleon hashing scheme, because the owner of a public key does not necessarily need to retrieve the associated secret key. We use the identity-based chameleon hashing scheme to build the id-based chameleon signature and a novel sealed-bid auction scheme that is robust, communication efficient (bidders send a single message), and secure under a particular trust model.

Let $$ be an elliptic curve defined over a prime finite field $$ by a Weierstrass equation. In this paper we introduce a new partition of $$ into classes which are generally larger than $$. We give an effective procedure to compute representatives of such classes. So one can iterate the pseudorandom function, related to a discrete logarithm problem in $$, on the set of representatives of classes and get probably some speed up in computing discrete logarithms. The underlying idea how to enlarge known classes on anomalous binary elliptic curves is given.

In extension of the bit commitment task and following work initiated by Crepeau and Kilian, we introduce and solve the problem of characterising the optimal rate at which a discrete memoryless channel can be used for bit commitment. It turns out that the answer is very intuitive: it is the maximum equivocation of the channel (after removing trivial redundancy), even when unlimited noiseless bidirectional side communication is allowed. By a well-known reduction, this result provides a lower bound on the channel's capacity for implementing coin tossing, which we conjecture to be an equality. The method of proving this relates the problem to Wyner's wire--tap channel in an amusing way. We also discuss extensions to quantum channels.

In this paper, we examine issues related to the construction of identity-based threshold decryption schemes and argue that it is important in practice to design an identity-based threshold decryption scheme in which a private key associated with an identity is shared. A major contribution of this paper is to construct the first identity-based threshold decryption scheme secure against chosen ciphertext attack. A formal proof of security of the scheme is provided in the random oracle model, assuming the Bilinear Diffie-Hellman problem is computationally hard. Another contribution of this paper is, by extending the proposed identity-based threshold decryption scheme, to construct a mediated identity-based encryption scheme secure against more powerful attacks than those considered previously.

A combined Identity-Based Signature/Encryption system with multiple security properties is presented. The scheme allows Alice to sign a message and encrypt it for Bob ("confidentiality") in such a way that the ciphertext does not reveal anything about their identities ("anonymity"); upon receipt, Bob is convinced that he is Alice's intended addressee ("authentication") but is unable to prove this to a third party ("unlinkability"); nevertheless, the decrypted message bears a signature by Alice that anyone can verify ("non-repudiation"). The construction is based on the Bilinear Diffie-Hellman assumption, and proved secure in the random oracle model.

The SecurID hash function is used for authenticating users to a corporate computer infrastructure. We analyse an alleged implementation of this hash function. The block cipher at the heart of the function can be broken in few milliseconds on a PC with 70 adaptively chosen plaintexts. The 64-bit secret key of 10$$ of the cards can be discovered given two months of token outputs and $$ analysis steps. A larger fraction of cards can be covered given more observation time.

The goals of this paper are three-fold. First we introduce and motivate a generalization of the fundamental concept of the indistinguishability of two systems, called indifferentiability. This immediately leads to a generalization of the related notion of reducibility of one system to another. Second, we prove that indifferentiability is the necessary and sufficient condition on two systems S and T such that the security of any cryptosystem using T as a component is not affected when T is substituted by S. In contrast to indistinguishability, indifferentiability is applicable in settings where a possible adversary is assumed to have access to additional information about the internal state of the involved systems, for instance the public parameter selecting a member from a family of hash functions. Third, we state an easily verifiable criterion for a system U not to be reducible (according to our generalized definition) to another system V and, as an application, prove that a random oracle is not reducible to a weaker primitive, called asynchronous beacon, and also that an asynchronous beacon is not reducible to a finite-length random string. Each of these irreducibility results alone implies the main theorem of Canetti, Goldreich and Halevi stating that there exist cryptosystems that are secure in the random oracle model but for which replacing the random oracle by any implementation leads to an insecure cryptosystem.

In 2002 the new genre of digital signature scheme TTS (Tame Transformation Signatures) is introduced along with a sample scheme TTS/2. TTS is from the family of multivariate cryptographic schemes to which the NESSIE primitive {SFLASH} also belongs. It is a realization of Moh's theory for digital signatures, based on Tame Transformations or Tame Maps. Properties of multivariate cryptosystems are determined mainly by their central maps. TTS uses Tame Maps as their central portion for even greater speed than $$-related schemes (using monomials in a large field for the central portion), previously usually acknowledged as fastest. We show a small flaw in TTS/2 and present an improved TTS implementation which we call TTS/4. We will examine in some detail how well TTS/4 performs, how it stands up to previously known attacks, and why it represents an advance over TTS/2. Based on this topical assessment, we consider TTS in general and TTS/4 in particular to be competitive or superior in several aspects to other schemes, partly because the theoretical roots of TTS induce many good traits. One specific area in which TTS/4 should excel is in low-cost smartcards. It seems that the genre has great potential for practical deployment and deserves further attention by the cryptological community.

We describe an efficient combination of two variants of RSA cryptosystem (MPrime and Rebalanced RSA) analysed by Boneh and Schacham. The decryption process resultant is (for 2048-bits moduli) about 8 times faster than that presented by Quisquater and Couvreur and about 27 times faster than original cryptosystem.

Here, we present how one can extend domain of a given Hash Family. We will give a sufficient condition for UOWHF-preserving domain extension (the extended Hash Family is UOWHF whenever the base Hash Family is UOWHF). We present also a binary tree based parallel algorithm for extending the domain of a UOWHF whose key-length expansion is optimum in a sub-class of binary tree based domain extension algorithm. We will show the optimality under an assumption.

In this paper, we study some RSA-based semantically secure encryption schemes (IND-CPA) in the standard model. We first derive the exactly tight one-wayness of Rabin-Paillier encryption scheme which assumes that factoring Blum integers is hard. We next propose the first IND-CPA scheme whose one-wayness is equivalent to factoring {\it general} $$ (not factoring Blum integers). Our reductions of one-wayness are very tight because they require only one decryption-oracle query.

We construct \emph{efficient} public key steganographic schemes, without resort to any peculiar existence assumption such as unbiased functions. This is the first time such a construction is obtained. Not only our constructions are \emph{secure}, but also are essentially optimal and have \emph{no error} decoding. We achieve this by designing a new primitive called $$-codes.

Following from the remarkable works of Cramer and Shoup \cite{CS}, three trapdoor hash signature variations have been presented in the literature: the first variation was presented in CJE'01 by Zhu \cite{Zhu}, the second variation was presented in SCN'02 by Camenisch and Lysyanskaya \cite{CL} and the third variation was presented in PKC'03 by Fischlin \cite{Fis}. All three mentioned trapdoor hash signature schemes have similar structure and the security of the last two modifications is rigorously proved. We point out that the distribution of variables derived from Zhu's signing oracle is different from that generated by Zhu's signing algorithm since the signing oracle in Zhu's simulator is defined over $$, instead of $$. Consequently the proof of security of Zhu's signature scheme should be studied more precisely. We also aware that the proof of Zhu's signature scheme is not a trivial work which is stated below: \begin{itemize} \item the technique presented by Cramer and Shoup \cite{CS} cannot be applied directly to prove the security of Zhu's signature scheme since the structure of Cramer-Shoup's trap-door hash scheme is double deck that is easy to simulate a signing query as the order of subgroup $$ is a public parameter; \item the technique presented by Camenisch and Lysyanskaya \cite{CL} cannot be applied directly since there are extra security parameters $$ and $$ guide the statistical closeness of the simulated distributions to the actual distribution; \item the technique presented by Fischlin cannot be applied directly to Zhu's signature scheme as the security proof of Fischlin's signature relies on a set of pairs $$ while the security proof of Zhu's signature should rely on a set of pairs $$. \end{itemize} In this report, we provide an interesting random argument technique to show that Zhu's signature scheme immune to adaptive chosen-message attack under the assumptions of the strong RSA problem as well as the existence of collision free hash functions.

We describe a new method for authenticated encryption, which uses information from the internal state of the cipher to provide the authentication. This methodology has a number of benefits. The encryption has properties similar to CBC mode, yet the encipherment and authentication mechanisms can be parallelized and/or pipelined. The authentication overhead is minimal, so the computational cost of the authenticated encryption is very nearly that of the encryption process. Also, the authentication process remains resistant against some IV reuse. We present a class of encryption algorithms that are based on cryptographic hash functions. Because of the hash function construction, the MTC4 class of methods supports variable encryption block sizes up to twice the hash output block length and trivially supports variable key lengths. We also provide a more general construction for using the internal state of any round-based block cipher as an authenticator. We give a concrete example of the general construction that uses AES as the encryption primitive. We provide performance measurements for all of our constructions.

In [KK], a new identification scheme based on the Gap Diffie-Hellman problem was proposed at SCIS 2002, and it is shown that the scheme is secure against active attacks under the Gap Diffie-Hellman Intractability Assumption. Paradoxically,this identification scheme is totally breakable under passive attacks. In this paper, we show that any adversary holding only public parameters of the scheme can convince a verifier with probability 1.

A classical model is used for the power consumption of cryptographic devices. It is based on the Hamming distance of the data handled with regard to an unknown but constant reference state. Once validated experimentally it allows an optimal attack to be derived called Correlation Power Analysis. It also explains the defects of former approaches such as Differential Power Analysis.

One of the main open problems in secret sharing is the characterization of the ideal access structures. This problem has been studied for several families of access structures with similar results. Namely, in all these families, the ideal access structures coincide with the vector space ones and, besides, the optimal information rate of a non-ideal access structure is at most $$. A first approach to the solution of that problem for the family of the $$-homogeneous access structures is made in this paper. First, we present an ideal $$-homogeneous access structure that is not vector space. Afterwards, we prove that the $$-homogeneous access structures that can be realized by a $$-vector space secret sharing scheme are {\em sparse\/}, that is, any subset of four participants contains at most two minimal qualified subsets. Finally, we solve the characterization problem for the family of the sparse $$-homogeneous access structures. Specifically, we completely characterize the ideal access structures in this family, we prove that they coincide with the $$-vector space ones and, besides, we demonstrate that there is no structure in this family having optimal information rate between $$ and $$. That is, we establish that the properties that were previously proved for several families also hold for the family of the sparse $$-homogeneous access structures.

In earlier work, we described a ``pathological'' example of a signature scheme that is secure in the random-oracle model, but for which no secure implementation exists. For that example, however, it was crucial that the scheme is able to sign "long messages" (i.e., messages whose length is not a-priori bounded). This left open the possibility that the Random Oracle Methodology is sound with respect to signature schemes that sign only "short" messages (i.e., messages of a-priori bounded length, smaller than the length of the keys in use), and are "memoryless" (i.e., the only thing kept between different signature generations is the initial signing-key). In this work, we extend our negative result to address such signature schemes. A key ingredient in our proof is a new type of interactive proof systems, which may be of independent interest.

We present a forward-secure hierarchical identity-based encryption (FHIBE) scheme, which is based on the hierarchical identity-based encryption (HIBE) scheme by Gentry and Silverberg. Canetti, Halevi and Katz presented a forward-secure public key encryption scheme based on HIBE scheme. They give the formal definition of Binary Encryption Tree (BET), which is a relaxed version of HIBE and is essential to their forward-secure encryption.We unify their idea with HIBE scheme, and present a forward-secure hierarchical identity-based encryption scheme. In the FHIBE scheme, secret keys of each entity on the hierarchy are updated at regular intervals throughout the lifetime of the system; furthermore, exposure of an entity's secret key corresponding to a given interval does not enable an adversary to break the ancestors of the entity for any prior time period. Entities can join in the hierarchy at any time and at any position, and are able to update their secret keys on their own once they are initialized by their parent entities. These features are important in the distributed settings. The forward-secure hierarchical identity-based encryption scheme can be generalized into a collusion resistant multiple hierarchical identity-based encryption (MHIBE) scheme, where a message can be encrypted under multiple identities of a user.

We describe a block-cipher mode of operation, CMC, that turns an n-bit block cipher into a tweakable enciphering scheme that acts on strings of mn bits, where m>=2. When the underlying block cipher is secure in the sense of a strong pseudorandom permutation (PRP), our scheme is secure in the sense of tweakable, strong PRP. Such an object can be used to encipher the sectors of a disk, in-place, offering security as good as can be obtained in this setting. CMC makes a pass of CBC encryption, xors in a mask, and then makes a pass of CBC decryption; no universal hashing, nor any other non-trivial operation beyond the block-cipher calls, is employed. Besides proving the security of CMC we initiate a more general investigation of tweakable enciphering schemes, considering issues like the non-malleability of these objects.

We describe a block-cipher mode of operation, EME, that turns an n-bit block cipher into a tweakable enciphering scheme that acts on strings of mn bits, where m \in [1..n]. The mode is parallelizable, but as serial-efficient as the non-parallelizable mode CMC. EME can be used to solve the disk-sector encryption problem. The algorithm entails two layers of ECB encryption and a "lightweight mixing" in between. We prove EME secure, in the reduction-based sense of modern cryptography. We motivate some of the design choices in EME by showing that a few simple modifications of this mode are insecure.

In PODC 2003, Park, Chong, Siegel and Ray [PCSR03] proposed an optimistic protocol for fair exchange, based on RSA signatures. We show that their protocol is *totally breakable* already in the registration phase: the honest-but-curious arbitrator can easily determine the signer's secret key. On a positive note, the authors of [PCSR03] informally introduced a connection between fair exchange and "sequential two-party multisignature schemes" (which we call two-signatures), but used an insecure two-signature scheme in their actual construction. Nonetheless, we show that this connection *can* be properly formalized to imply *provably secure* fair exchange protocols. By utilizing the state-of-the-art non-interactive two-signature of Boldyreva (PKC 2003), we obtain an efficient and provably secure (in the random oracle model) fair exchange protocol, which is based on GDH signatures of Boneh, Lynn and Shacham (Asiacrypt 2001). Of independent interest, we introduce a unified model for non-interactive fair exchange protocols, which results in a new primitive we call *verifiably committed signatures*. Verifiably committed signatures generalize (non-interactive) verifiably encrypted signatures and two-signatures, both of which are sufficient for fair exchange.

Proofs of security protocols typically employ simple abstractions of cryptographic operations, so that large parts of such proofs are independent of cryptographic details. The typical abstraction is the Dolev-Yao model, which treats cryptographic operations as a specific term algebra. However, there is no cryptographic semantics, i.e., no theorem that says what a proof with the Dolev-Yao abstraction implies for the real protocol, even if provably secure cryptographic primitives are used. Recently we introduced an extension to the Dolev-Yao model for which such a cryptographic semantics exists, i.e., where security is preserved if the abstractions are instantiated with provably secure cryptographic primitives. Only asymmetric operations (digital signatures and public-key encryption) are considered so far. Here we extend this model to include a first symmetric primitive, message authentication, and prove that the extended model still has all desired properties. The proof is a combination of a probabilistic, imperfect bisimulation with cryptographic reductions and static information-flow analysis. Considering symmetric primitives adds a major complication to the original model: we must deal with the exchange of secret keys, which might happen any time before or after the keys have been used for the first time. Without symmetric primitives only public keys need to be exchanged.

This paper proposes a new identity based tripartite key agreement protocol which is more efficient than the existing ID-based tripartite protocol. This protocol is based on the Joux's protocol for key agreement, and introduces signature along with key agreement to overcome man-in-the-middle attacks and to provide authentication. The new protocol resists existential forgeries against adaptively chosen message attacks under the random oracle model.

We give a method for constructing ordinary elliptic curves over finite prime field $$ with small security parameter $$ with respect to a prime $$ dividing the group order $$ such that $$.

We present a new binary tree based parallel algorithm for extending the domain of a UOWHF. The key length expansion is m(t+O(log*(t))) bits. In particular, the key length expansion is 2m bits for t=2; m(t+1) bits for 3\leq t\leq 6 and m(t+2) bits for 7\leq t\leq 134, where m is the length of the message digest and t\geq 2 is the height of the binary tree. The previously best known binary tree algorithm required a key length expansion of m(t+[log_2 (t-1)]) bits. We also give a sufficient condition for valid domain extension in sequental domain extension.

\emph{Concurrent general composition} relates to a setting where a secure protocol is run in a network concurrently with other, arbitrary protocols. Clearly, security in such a setting is what is desired, or even needed, in modern computer networks where many different protocols are executed concurrently. Canetti (FOCS 2001) introduced the notion of \emph{universal composability}, and showed that security under this definition is sufficient for achieving concurrent general composition. However, it is not known whether or not the opposite direction also holds. Our main result is a proof that security under concurrent general composition, when interpreted in the natural way under the simulation paradigm, is equivalent to a variant of universal composability, where the only difference relates to the order of quantifiers in the definition. (In newer versions of universal composability, these variants are equivalent.) An important corollary of this theorem is that existing impossibility results for universal composability (for all its variants) are inherent for definitions that imply security under concurrent general composition, as formulated here. In particular, there are large classes of two-party functionalities for which \emph{it is impossible} to obtain protocols (in the plain model) that remain secure under concurrent general composition. We stress that the impossibility results obtained are not "black-box", and apply even to non-black-box simulation. Our main result also demonstrates that the definition of universal composability is somewhat "minimal", in that the composition guarantee provided by universal composability implies the definition itself. This indicates that the security definition of universal composability is not overly restrictive.

While bringing considerable flexibility and extending the horizons of mobile computing, mobile code raises major security issues. Hence, mobile code, such as Java applets, needs to be analyzed before execution. The byte-code verifier checks low-level security properties that ensure that the downloaded code cannot bypass the virtual machine's security mechanisms. One of the statically ensured properties is {\sl type safety}. The type-inference phase is the overwhelming resource-consuming part of the verification process. This paper addresses the RAM bottleneck met while verifying mobile code in memory-constrained environments such as smart-cards. We propose to modify classic type-inference in a way that significantly reduces the memory consumption in the memory-constrained device at the detriment of its distrusted memory-rich environment. The outline of our idea is the following, throughout execution, the memory frames used by the verifier are MAC-ed and exported to the terminal and then retrieved upon request. Hence a distrusted memory-rich terminal can be safely used for convincing the embedded device that the downloaded code is secure. The proposed protocol was implemented on JCOP20 and JCOP30 Java cards using IBM's JCOP development tool.

In their paper, G.Gong and S.Q.Jiang construct a new pseudo-random sequence generator by using two ternary linear feedback shift registers (LFSR). The new generator is called an editing generator which a combined model of the clock-controlled generator and the shrinking generator. For a special case (Both the base sequence and the control sequence are mm-sequence of degree $$), the period, linear complexity, symbol distribution and security analysis are discussed in the same article. In this paper, we expand the randomness results of the edited sequence for general cases, we do not restrict the base sequence and the control sequence has the same length. For four special cases of this generator, the randomness of the edited sequence is discussed in detail. It is shown that for all four cases the editing generator has good properties, such as large periods, high linear complexities, large ratio of linear complexity per symbol, and small un-bias of occurrences of symbol. All these properties make it a suitable crypto-generator for stream cipher applications.

A permutation $$ is a \emph{fast forward permutation} if for each $$ the computational complexity of evaluating $$ is small independently of $$ and $$. Naor and Reingold constructed fast forward pseudorandom cycluses and involutions. By studying the evolution of permutation graphs, we prove that the number of queries needed to distinguish a random cyclus from a random permutation in $$ is $$ if one does not use queries of the form $$, but is only $$ if one is allowed to make such queries. We construct fast forward permutations which are indistinguishable from random permutations even when queries of the form $$ are allowed. This is done by introducing an efficient method to sample the cycle structure of a random permutation, which in turn solves an open problem of Naor and Reingold.

A birthday surprise is the event that, given $$ uniformly random samples from a sample space of size $$, at least two of them are identical. We show that Bernoulli numbers can be used to derive arbitrarily exact bounds on the probability of a birthday surprise. This result can be used in arbitrary precision calculators, and it can be applied to better understand some questions in communication security and pseudorandom number generation.

We introduce and analyze an efficient family of linear feedback shift registers (LFSR's) with maximal period. This family is word-oriented and is suitable for implementation in software, thus provides a solution to a recent challenge \cite{FSE94}. The classical theory of LFSR's is extended to provide efficient algorithms for generation of irreducible and primitive LFSR's of this new type.

Camellia is the final winner of 128-bit block cipher in NESSIE. In this paper, we construct some efficient distinguishers between 4-round Camellia and a random permutation of the blocks space. By using collision-searching techniques, the distinguishers are used to attack on 6,7,8 and 9 rounds of Camellia with 128-bit key and 8,9 and 10 rounds of Camellia with 192/256-bit key. The 128-bit key of 6 rounds Camellia can be recovered with $$ chosen plaintexts and $$ encryptions. The 128-bit key of 7 rounds Camellia can be recovered with $$ chosen plaintexts and $$ encryptions. The 128-bit key of 8 rounds Camellia can be recovered with $$ chosen plaintexts and $$ encryptions. The 128-bit key of 9 rounds Camellia can be recovered with $$ chosen plaintexts and $$ encryptions. The 192/256-bit key of 8 rounds Camellia can be recovered with $$ chosen plaintexts and $$ encryptions. The 192/256-bit key of 9 rounds Camellia can be recovered with $$ chosen plaintexts and $$ encryptions.The 256-bit key of 10 rounds Camellia can be recovered with $$ chosen plaintexts and $$ encryptions.

Prof. Claude Carlet has pointed out an error in Theorem 1 of the paper. The error could not be recovered for the time being. Thus the statement presented in the title of the paper is not proved.

In this paper we study the minimum distance between the set of bent functions and the set of 1-resilient Boolean functions and present a lower bound on that. The bound is proved to be tight for functions up to $$ input variables. As a consequence, we present a strategy to modify the bent functions, by toggling some of its outputs, in getting a large class of $$-resilient functions with very good nonlinearity and autocorrelation. In particular, the technique is applied upto $$-variable functions and we show that the construction provides a large class of $$-resilient functions reaching currently best known nonlinearity and achieving very low autocorrelation values which were not known earlier. The technique is sound enough to theoretically solve some of the mysteries of $$-variable, $$-resilient functions with maximum possible nonlinearity. However, the situation becomes complicated from $$ variables and above, where we need to go for complicated combinatorial analysis with trial and error using computational facility.

A major problem in using iterative number generators of the form $$ is that they can enter unexpectedly short cycles. This is hard to analyze when the generator is designed, hard to detect in real time when the generator is used, and can have devastating cryptanalytic implications. In this paper we define a measure of security, called \emph{sequence diversity}, which generalizes the notion of cycle-length for non-iterative generators. We then introduce the class of counter assisted generators, and show how to turn any iterative generator (even a bad one designed or seeded by an adversary) into a counter assisted generator with a provably high diversity, without reducing the quality of generators which are already cryptographically strong.

We describe the group structure underlying several popular homomorphic public-key systems and the problems they are based on. We prove several well-known security results using only the group structure and assumptions about the related problems. Then we provide examples of two new instances of this group structure and analyse their security.

KASUMI is a block cipher which has been adopted as a standard of 3GPP. In this paper, we study the pseudorandomness of idealized KASUMI type permutations for adaptive adversaries. We show that the four round version is pseudorandom and the six round version is super-pseudorandom.

At the fourth ACM conference on electronic commerce (EC'03), S. Han, K.Y. Yeung and J. Wang proposed an ID-based confirmer signature scheme using pairings (actually, this is an ID-based undeniable signature scheme). However, in this paper, we will show that this signature scheme is not secure. The signer can deny any signature, even this signature is his valid signature and any one can forge a valid confirmer signature of a signer with identity ID on an arbitrary message and confirm this signature to the verifier.

We demonstrate that some finite fields, including GF(2^210) are weak for elliptic curve cryptography in the sense that any instance of the elliptic curve discrete logarithm problem for any elliptic curve over these fields can be solved in significantly less time than it takes Pollard's rho method to solve the hardest instances. We discuss the implications of our observations to elliptic curve cryptography, and list some open problems.

We address the problem of detecting deviations of binary sequence from randomness,which is very important for random number (RNG) and pseudorandom number generators (PRNG). Namely, we consider a null hypothesis $$ that a given bit sequence is generated by Bernoulli source with equal probabilities of 0 and 1 and the alternative hypothesis $$ that the sequence is generated by a stationary and ergodic source which differs from the source under $$. We show that data compression methods can be used as a basis for such testing and describe two new tests for randomness, which are based on ideas of universal coding. Known statistical tests and suggested ones are applied for testing PRNGs, which are practically used. Those experiments show that the power of the new tests is greater than of many known algorithms.

This paper introduces the concept of 'certificateless public key cryptography' (CL-PKC). In contrast to traditional public key cryptographic systems, CL-PKC does not require the use of certificates to guarantee the authenticity of public keys. It does rely on the use of a trusted third party (TTP) who is in possession of a master key. In these respects, CL-PKC is similar to identity-based public key cryptography (ID-PKC). On the other hand, CL-PKC does not suffer from the key escrow property that seems to be inherent in ID-PKC. Thus CL-PKC can be seen as a model for the use of public key cryptography that is intermediate between traditional certificated PKC and ID-PKC. We make concrete the concept of CL-PKC by introducing certificateless public key encryption (CL-PKE), signature and key exchange schemes. We also demonstrate how hierarchical CL-PKC can be supported. The schemes are all derived from pairings on elliptic curves. The lack of certificates and the desire to prove the schemes secure in the presence of an adversary who has access to the master key requires the careful development of new security models. For reasons of brevity, the focus in this paper is on the security of CL-PKE. We prove that our CL-PKE scheme is secure in a fully adaptive adversarial model, provided that an underlying problem closely related to the Bilinear Diffie-Hellman Problem is hard.

Algebraic attacks on stream ciphers proposed by Courtois et al. recover the key by solving an overdefined system of multivariate equations. Such attacks can break several interesting cases of LFSR-based stream ciphers, when the output is obtained by a Boolean function. As suggested independently by Courtois and Armknecht, this approach can be successfully extended also to combiners with memory, provided the number of memory bits is small. At Crypto 2003, Krause and Armknecht show that, for ciphers built with LFSRs and an arbitrary combiner using a subset of k LFSR state bits, and with l memory bits, a polynomial attack always do exist when k and l are fixed. Yet this attack becomes very quickly impractical: already when k and l exceed about 4. In this paper we give a much simpler proof of this result and prove a more general theorem. We show that much faster algebraic attacks exist for any cipher that (in order to be fast) outputs several bits at a time. In practice our results substantially reduce the complexity of the best attack known on four well known constructions of stream ciphers when the number of outputs is increased. We present attacks on modified versions of Snow, E0, LILI-128, Turing, and some other ciphers.

In 2001, Nyberg proved three important correlation theorems and applied them to several cryptanalytic contexts. We continue the work of Nyberg in a more theoretical direction. We consider a general functional form and obtain its Walsh transform. Two of Nyberg's correlation theorems are seen to be special cases of our general functional form. S-box look-up, addition modulo $$ and X-OR are three frequently occuring operations in the design of symmetric ciphers. We consider two methods of combining these operations and in each apply our main result to obtain the Walsh transform.

One of the possible generalizations of the discrete logarithm problem to arbitrary groups is the so-called conjugacy search problem. The computational difficulty of this problem in some particular groups has been used in several group based cryptosystems. Recently, a few preprints have been in circulation that suggest various heuristic attacks on the conjugacy search problem. The goal of the present survey is to stress a (probably well known) fact that these heuristic attacks alone are not a threat to the security of a cryptosystem, and, more importantly, to suggest a more credible approach to assessing security of group based cryptosystems. Such an approach should be necessarily based on the concept of the average case complexity (or expected running time) of an algorithm. These arguments support the following conclusion: although it is generally feasible to base the security of a cryptosystem on the difficulty of the conjugacy search problem, the group itself (the ``platform") has to be chosen very carefully. In particular, experimental as well as theoretical evidence collected so far makes it appear likely that braid groups are not a good choice for the platform. We also reflect on possible replacements.

Recently, Al-Riyami and Paterson proposed four authenticated tripartite key agreement protocols which make use of Weil pairing. In this paper, we show that the protocols are insecure against the man-in-the middle attack, key compromise impersonation attack and several known-key attacks.

We present the first cryptographically sound security proof of the well-known Needham-Schroeder-Lowe public-key protocol. More precisely, we show that the protocol is secure against arbitrary active attacks if it is implemented using provably secure cryptographic primitives. Although we achieve security under cryptographic definitions, our proof does not have to deal with probabilistic aspects of cryptography and is hence in the scope of current proof tools. The reason is that we exploit a recently proposed ideal cryptographic library, which has a provably secure cryptographic implementation. Besides establishing the cryptographic security of the Needham-Schroeder-Lowe protocol, our result also exemplifies the potential of this cryptographic library and paves the way for cryptographically sound verification of security protocols by means of formal proof tools.

Complexity-theoretic cryptography considers only abstract notions of computation, and hence cannot protect against attacks that exploit the information leakage (via electromagnetic fields, power consumption, etc.) inherent in the physical execution of any cryptographic algorithm. Such "physical observation attacks" bypass the impressive barrier of mathematical security erected so far, and successfully break mathematically impregnable systems. The great practicality and the inherent availability of physical attacks threaten the very relevance of complexity-theoretic security. To respond to the present crisis, we put forward physically observable cryptography: a powerful, comprehensive, and precise model for defining and delivering cryptographic security against an adversary that has access to information leaked from the physical execution of cryptographic algorithms. Our general model allows for a variety of adversaries. In this paper, however, we focus on the strongest possible adversary, so as to capture what is cryptographically possible in the worst possible, physically observable setting. In particular, we -- consider an adversary that has full (and indeed adaptive) access to any leaked information; -- show that some of the basic theorems and intuitions of traditional cryptography no longer hold in a physically observable setting; and -- construct pseudorandom generators that are provably secure against all physical-observation attacks. Our model makes it easy to meaningfully restrict the power of our general physically observing adversary. Such restrictions may enable schemes that are more efficient or rely on weaker assumptions, while retaining security against meaningful physical observations attacks.

The use of FPGAs for cryptographic applications is highly attractive for a variety of reasons but at the same time there are many open issues related to the general security of FPGAs. This contribution attempts to provide a state-of-the-art description of this topic. First, the advantages of reconfigurable hardware for cryptographic applications are discussed from a systems perspective. Second, potential security problems of FPGAs are described in detail, followed by a proposal of a some countermeasure. Third, a list of open research problems is provided. Even though there have been many contributions dealing with the algorithmic aspects of cryptographic schemes implemented on FPGAs, this contribution appears to be the first comprehensive treatment of system and security aspects.

In this paper we describe a low-tech and user friendly solution for secure two-way communication between two parties over a network of untrusted devices. We present a solution in which displays play a central role. Our approach guarantees privacy and allows to check the authenticity of information presented on displays. Furthermore, we provide the user with a secure return channel. To this end we propose to provide every user with a small decryption display which is, for example, integrated in a credit card and requires very limited computing power. The authentication and security are based on visual cryptography which was first introduced by Naor and Shamir in 1994. We solve some practical shortcomings of traditional visual cryptography and develop protocols for two-way authentication and privacy in untrusted environments.

At the conference Asiacrypt 2001, Rivest, Shamir and Tauman firstly addressed the concept of ring signature. In this paper we propose an identity-based ring signature scheme from bilinear pairings. As compared with the Zhang-Kim scheme (presented at the conference Asiacrypt 2002), our scheme is more efficient in computation and requires fewer pairing operations.

We argue that traditional ID-based systems from pairings seem unsuitable for designing group signature schemes due to the problem of key escrow. In this paper we propose new ID-based public key systems without trustful KGC from bilinear pairings. In our new ID-based systems, if dishonest KGC impersonates an honest user to communicate with others, the user can provide a proof of treachery of the KGC afterwards, which is similar to CA-based systems. Furthermore, we propose a group signature scheme under the new systems, the security and performance of which rely on the new systems. The size of the group public key and the length of the signature are independent on the numbers of the group.

In this paper, we show that the Nalla-Reddy's one round ID-based tripartite authenticated key agreement protocols are still insecure against the man-in-the-middle attacks. We also break the Nalla's ID-based tripartite authenticated key agreement protocol with signatures.

The cryptographic concept of simulatability has become a salient technique for faithfully analyzing and proving security properties of arbitrary cryptographic protocols. We investigate the relationship between simulatability in synchronous and asynchronous frameworks by means of the formal models of Pfitzmann et. al., which are seminal in using this concept in order to bridge the gap between the formal-methods and the cryptographic community. We show that the synchronous model can be seen as a special case of the asynchronous one with respect to simulatability, i.e., we present an embedding between both models that we show to preserve simulatability. We show that this result allows for carrying over lemmas and theorems that rely on simulatability from the asynchronous model to its synchronous counterpart without any additional work. Hence future work can concentrate on the more general asynchronous case, without having to neglect the analysis of synchronous protocols.

Recently, Shim proposed a tripartite authenticated key agreement protocol from Weil pairing to overcome the security flaw in Joux's protocol. Later, Shim also proposed an ID-based authenticated key agreement protocol which is an improvement of Smart's protocol in order to provide the forward secrecy. In this paper, we show that these two protocols are insecure against the key-compromise impersonation attack and the man-in-the-middle attack respectively.

Constructing practical and provably secure group signature schemes has been a very active research topic in recent years. A group signature can be viewed as a digital signature with certain extra properties. Notably, anyone can verify that a signature is generated by a legitimate group member, while the actual signer can only be identified (and linked) by a designated entity called a group manager. Currently, the most efficient group signature scheme available is due to Camenisch and Lysyanskaya \cite{CL02}. It is obtained by integrating a novel dynamic accumulator with the scheme by Ateniese, et al. \cite{ACJT00}. In this paper, we construct a dynamic accumulator that accumulates \emph{composites}, as opposed to previous accumulators that accumulated \emph{primes}. We also present an efficient method for proving knowledge of factorization of a committed value. Based on these (and other) techniques we design a novel provably secure group signature scheme. It operates in the \emph{common auxiliary string} model and offers two important benefits: 1) the {\sf Join} process is very efficient: a new member computes only a single exponentiation, and 2) the (unoptimized) cost of generating a group signature is 17 exponentiations which is appreciably less than the state-of-the-art.

Proxy signature is a signature that an original signer delegates his or her signing capability to a proxy signer, and then the proxy signer creates a signature on behalf of the original signer. However, Sun et al.[7] showed that the proxy and multi-proxy signatures of Lee et al.[3], and the strong proxy signature scheme with proxy signer privacy protection of Shum et al.[6] are not against the original signer's forgery attack, so these schemes do not process the property of unforgeability. In this paper, we present an extensive forgery method on these schemes, which makes the forgery method of Sun et al.be a special case of ours.

Biometric personal authentication systems have a common problem --- the biological information can easily be stolen by other individuals. In line with the process of the activities for the international standardization of the biometric system, this paper proposes a typical way to embed biological information, whatever its kind, into cryptographic keys as a measure for privacy protection and against unauthorized use. We believe that our proposal presents the following advantages: the improvement of protecting the privacy of biological information, economical effectiveness resulting from the practical use of the infrastructure of Public Key Infrastructure (PKI) as a biological information database, and humanity given to a man-machine interface by embedding an individual's biological information into a public key, an important element of the system. This paper also proposes how to build up a practical personal authentication system through the method proposed.

This paper presents several multiset and boomerang attacks on SAFER++ up to 5.5 out of its 7 rounds. These are the best known attacks for this cipher and significantly improve the previously known results. The attacks in the paper are practical up to 4 rounds. The methods developed to attack SAFER++ can be applied to other substitution-permutation networks with incomplete diffusion.

Rijndael, or the Advanced Encryption Standard, is an interesting cipher from a designer's viewpoint. Over the last few decades, the most notable, and successful attacks against the best block ciphers were linear and differential cryptanalysis. On the other hand, Rijndael is designed from the ground up to resist these attacks, as well as many others, by employing special algebraic properties of its primitive operations. The byte inversion operation over finite field $$ was chosen by its designer to thwart all possibly useful linear and difference invariances, the basic ingredients of linear and differential cryptanalysis. However, by using simple algebraic operations with known properties, the combinations of them may possess many interesting, and unexpected, algebraic properties that were not known at design time. This paper presents such new unknown properties on the combinations of primitive operations of AES.

At Crypto'99, Fujisaki and Okamoto~\cite{FO99} presented a nice generic transformation from weak asymmetric and symmetric schemes into an IND-CCA hybrid encryption scheme in the Random Oracle Model. From this transformation, two specific candidates to standardization were designed: EPOC-2~\cite{EPOC} and PSEC-2~\cite{PSEC}, based on Okamoto-Uchiyama and El Gamal primitives, respectively. Since then, several cryptanalysis of EPOC have been published, one in the Chosen Ciphertext Attack game and others making use of a poor implementation that is vulnerable to reject timing attacks. The aim of this work is to avoid these attacks from the generic transformation, identifying the properties that an asymmetric scheme must hold to obtain a secure hybrid scheme. To achieve this, some ambiguities in the proof of the generic transformation~\cite{FO99} are described, which can lead to false claims. As a result the original conversion is modified and the range of asymmetric primitives that can be used is shortened. In second place, the concept of {\it Easy Verifiable Primitive} is formalized, showing its connection with the Gap problems. Making use of these ideas, a {\it new} security proof for the modified transformation is given. The good news is that the reduction is {\it tight}, improving the concrete security claimed in the original work for the Easy Verifiable Primitives. For the rest of primitives the concrete security is improved at the cost of stronger assumptions. Finally, the resistance of the new conversion against reject timing attacks is addressed.

We introduce CWC, a new block cipher mode of operation for protecting both the privacy and the authenticity of encapsulated data. CWC is currently the only such mode having all five of the following properties: provable security, parallelizability, high performance in hardware, high performance in software, and no intellectual property concerns. We believe that having all five of these properties makes CWC a powerful tool for use in many performance-critical cryptographic applications. CWC is also the only appropriate solution for some applications; e.g., standardization bodies like the IETF and NIST prefer patent-free modes, and CWC is the only such mode capable of processing data at 10Gbps in hardware, which will be important for future IPsec (and other) network devices. As part of our design, we also introduce a new parallelizable universal hash function optimized for performance in both hardware and software.

We show how to construct practical honest-verifier statistical zero-knowledge \emph{Diophantine} arguments of knowledge (HVSZK AoK) that a committed tuple of integers belongs to an arbitrary language in bounded arithmetic. While doing this, we propose a new algorithm for computing the Lagrange representation of nonnegative integers and a new efficient representing polynomial for the exponential relation. We apply our results by constructing the most efficient known HVSZK AoK for non-negativity and the first constant-round practical HVSZK AoK for exponential relation. Finally, we propose the outsourcing model for cryptographic protocols and design communication-efficient versions of the Damgård-Jurik multi-candidate voting scheme and of the Lipmaa-Asokan-Niemi $$st-price auction scheme that work in this model.

Proxy signatures are very useful tools when one needs to delegate his/her signing capability to other party. After Mambo $$'s first scheme was announced, many proxy signature schemes and various types of proxy signature schemes have been proposed. Due to the various applications of the bilinear pairings in cryptography, there are many ID-based signature schemes have been proposed. In this paper, we address that it is easy to design proxy signature and proxy blind signature from the conventional ID-based signature schemes using bilinear pairings, and give some concrete schemes based on existed ID-based signature schemes. At the same time, we introduce a new type of proxy signature -- proxy ring signature, and propose the first proxy ring signature scheme based on an existed ID-based ring signature scheme.

In this paper we propose security analysis on passive attack for Nalla-Reddy's ID-AK-2 and ID-AK-3 protocols.

In this note, we describe a probabilistic attack on public key cryptosystems based on the word/conjugacy problems for finitely presented groups of the type proposed recently by Anshel, Anshel and Goldfeld. In such a scheme, one makes use of the property that in the given group the word problem has a polynomial time solution, while the conjugacy problem has no known polynomial solution. An example is the braid group from topology in which the word problem is solvable in polynomial time while the only known solutions to the conjugacy problem are exponential. The attack in this paper is based on having a canonical representative of each string relative to which a length function may be computed. Hence the term length attack. Such canonical representatives are known to exist for the braid group.

Out of the public key ($$) we recover a polynomial of the same shape as the private polynomial. Then we give an algorithm for solving such a special-form polynomial. This fact puts an eavesdropper in the same position with a legitimate user in decryption. An upper bound for the complexity of that all is $$ bit operations for $$ the degree of the field extension.

Until recently, most research on the topic of secure computation focused on the stand-alone model, where a single protocol execution takes place. In this paper, we construct protocols for the setting of {\em bounded-concurrent self composition}, where a (single) secure protocol is run many times concurrently, and there is a predetermined bound on the number of concurrent executions. In short, we show that {\em any} two-party functionality can be securely computed under bounded-concurrent self composition, in the {\sf plain model} (where the only setup assumption made is that the parties communicate via authenticated channels). Our protocol provides the first feasibility result for general two-party computation in the plain model, {\em for any model of concurrency}. All previous protocols assumed a trusted setup phase in order to obtain a common reference string. On the downside, the number of rounds of communication in our protocol is super-linear in the bound on the number of concurrent executions. However, we believe that our constructions will lead to more efficient protocols for this task.

Braid Groups have recently been considered for use in Public-Key Cryptographic Systems. The most notable of these system has been the Birman-Ko-Lee system presented at Crypto 2000. This article gives a brief introduction into braid groups and the hard problems on which public key systems have been defined. It suggests a canonical form max run form using the Artin generators and supplies some supporting algorithms necessary for cryptographic operations.

Vaudenay has shown in [5] that a CBC encryption mode ([2], [9]) combined with the PKCS#5 padding [3] scheme allows an attacker to invert the underlying block cipher, provided she has access to a valid-padding oracle which for each input ciphertext tells her whether the corresponding plaintext has a valid padding or not. Having on mind the countermeasures against this attack, different padding schemes have been studied in [1]. The best one is referred to as the ABYT-PAD. It is designed for byte-oriented messages. It removes the valid-padding oracle, thereby defeating Vaudenay's attack, since all deciphered plaintexts are valid in this padding scheme. In this paper, we try to combine the well-known cryptographic message syntax standard PKCS#7 [8] with the use of ABYT-PAD instead of PKCS#5. Let us assume that we have access to a PKCS#7CONF oracle that tells us for a given ciphertext (encapsulated in the PKCS#7 structure) whether the deciphered plaintext is correct or not according to the PKCS#7 (v1.6) syntax. This is probably a very natural assumption, because applications usually have to reflect this situation in its behavior. It could be a message for the user, an API error message, an entry in the log file, different timing behavior, etc. We show that access to such an oracle again enables an attacker to invert the underlying block cipher. The attack requires single captured ciphertext and approximately 128 oracle calls per one ciphertext byte. It shows that we cannot hope to fully solve problems with side channel attacks on the CBC encryption mode by using a “magic” padding method or an obscure message-encoding format. Strong cryptographic integrity checks of ciphertexts should be incorporated instead.

It is widely believed that genus four hyperelliptic curve cryptosystems (HECC) are not attractive for practical applications because of their complexity compared to systems based on lower genera, especially elliptic curves. Our contribution shows that for low cost security applications genus-4 hyperelliptic curves (HEC) can outperform genus-2 HEC and that we can achieve a performance similar to genus-3 HEC. Furthermore our implementation results show that a genus-4 HECC is an alternative cryptosystem to systems based on elliptic curves. In the work at hand we present for the first time explicit formulae for genus-4 HEC, resulting in a 60% speed-up compared to the best published results. In addition we implemented genus-4 HECC on a Pentium4 and an ARM microprocessor. Our implementations on the ARM show that for genus four HECC are only a factor of 1.66 slower than genus-2 curves considering group order ~2^{190}. For the same group order ECC and genus-3 HECC are about a factor of 2 faster than genus-4 curves on the ARM. The two most surprising results are: 1) for low cost security application, namely considering an underlying group of order 2^{128}, HECC with genus 4 outperform genus-2 curves by a factor of 1.46 and has similar performance to genus-3 curves on the ARM and 2) when compared to genus-2 and genus-3, genus-4 HECC are better suited to embedded microprocessors than to general purpose processors.

A proxy signature scheme permits an entity to delegate its signing rights to another entity. These schemes have been suggested for use in numerous applications, particularly in distributed computing. But to date, no proxy signature schemes with guaranteed security have been proposed; no precise definitions or proofs of security have been provided for such schemes. In this paper, we formalize a notion of security for proxy signature schemes and present provably-secure schemes. We analyze the security of the well-known delegation-by-certificate scheme and show that after some slight but important modifications, the resulting scheme is secure, assuming the underlying standard signature scheme is secure. We then show that employment of the recently introduced aggregate signature schemes permits bandwidth and computational savings. Finally, we analyze the proxy signature scheme of Kim, Park and Won, which offers important performance benefits. We propose modifications to this scheme that preserve its efficiency, and yield a proxy signature scheme that is provably secure in the random-oracle model, under the discrete-logarithm assumption.