Nowadays, there exists a manifold variety of cryptographic applications: from low level embedded crypto implementations up to high end cryptographic engines for servers. The latter require a flexible implementation of a variety of cryptographic primitives in order to be capable of communicating with several clients. On the other hand, on the client it only requires an implementation of one specific algorithm with fixed parameters such as a fixed field size or fixed curve parameters if using ECC/ HECC. In particular for embedded environments like PDAs or mobile communication devices, fixing these parameters can be crucial regarding speed and power consumption. In this contribution, we propose a highly efficient algorithm for a hyperelliptic curve cryptosystem of genus two, well suited for these constraint devices. In recent years, a lot of effort was made to speed up arithmetic on genus-2 HEC. This work is based on the work of Lange and presents a major improvement of HECC arithmetic for curves defined over fields of characteristic two. We optimized the group doubling operation for certain types of genus-2 curves and we were able to reduce the number of required multiplications to a total of 9 multiplications. The saving in multiplications is 47% for the cost of one additional squaring. Thus, the efficiency of the whole cryptosystem was drastically increased.

SFLASH-v2 is one of the three asymmetric signature schemes recommended by the European consortium for low-cost smart cards. The latest implementation report published at PKC 2003 shows that SFLASH-v2 is the fastest signature scheme known. This is a detailed specification of SFLASH-v3 produced in 2003 for fear of v2 being broken. HOWEVER after detailed analysis by Chen Courtois and Yang [ICICS04], Sflash-v2 is not broken and we still recommend the previous version Sflash-v2, already recommended by Nessie, instead of this version.

In this paper we try to shed a new insight on Verifiable Secret Sharing Schemes (VSS). We first define a new ``metric" (with slightly different properties than the standard Hamming metric). Using this metric we define a very particular class of codes that we call {\it error-set correcting codes}, based on a set of forbidden distances which is a monotone decreasing set. Next we redefine the packing problem for the new settings and generalize the notion of error-correcting capability of the error-set correcting codes accordingly (taking into account the new metric and the new packing). Then we consider burst-error interleaving codes proposing an efficient burst-error correcting technique, which is in fact the well known VSS and Distributed Commitments (DC) pair-wise checking protocol and we prove the error-correcting capability of the error-set correcting interleaving codes. Using the known relationship, due to Van Dijk, between a Monotone Span Program (MSP) and a generator matrix of the code generated by the suitable set of vectors, we prove that the error-set correcting codes in fact has the allowed (opposite to forbidden) distances of the dual access structure of the access structure that the MSP computes. We give an efficient construction for them based on this relation and as a consequence we establish a link between Secret Sharing Schemes (SSS) and the error-set correcting codes. Further we give a necessary and sufficient condition for the existence of linear SSS (LSSS), to be secure against $$-adversary expressed in terms of an error-set correcting code. Finally, we present necessary and sufficient conditions for the existence of a VSS scheme, based on an error-set correcting code, secure against $$-adversary. Our approach is general and covers all known linear VSS/DC. It allows us to establish the minimal conditions for security of VSSs. Our main theorem states that the security of a scheme is equivalent to a pure geometrical (coding) condition on the linear mappings describing the scheme. Hence the security of all known schemes, e.g. all known bounds for existence of unconditionally secure VSS/DC including the recent result of Fehr and Maurer, can be expressed as certain (geometrical) coding conditions.

In this paper, we present a modification of the Augot-Finiasz cryptosystem presented at EUROCRYPT 2003. Coron managed to design an attack against the original cryptosystem enabling an attacker to decrypt any intercepted ciphertext efficiently. We introduce here a modification of the scheme which appears to resist to this attack. We furthermore propose parameters thwarting the state of the art attacks.

Chameleon hash function is a trapdoor one-way hash function. The ID-based chameleon hash function was first introduced by Ateniese and Medeiros \cite{AM03}. As discussed by \cite{AM03}, the general advantages of ID-based cryptography over conventional cryptography with respect 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. In this paper, we propose two new ID-based Chameleon hashing schemes from bilinear pairings. Also we analyze their security and efficiency. Based on these ID-based chameleon hashes, ID-based chameleon signature schemes can be designed.

In resent years, Popescu proposed several group signature schemes based on the Okamoto-Shiraishi assumption in [8-11], and claimed his schemes are secure. However, this paper demonstrates that all these schemes are insecure by identifying some security flaws. Exploiting these flaws, an attacker without any secret can mount universally forging attacks. That is, anybody (not necessarily a group member) can forge valid group signatures on arbitrary messages of his/her choice.

In this paper, we give a first example of identity based undeniable signature using pairings over elliptic curves. We extend to the identity based setting the security model for the notions of invisibility and anonymity given by Galbraith and Mao in 2003 and we prove that our scheme is existentially unforgeable under the Bilinear Diffie-Hellman assumption in the random oracle model. We also prove that it has the invisibility property under the Decisional Bilinear Diffie-Hellman assumption and we discuss about the efficiency of the scheme.

SecurID is a widely used hardware token for strengthening authentication in a corporate environment. Recently, Biryukov, Lano, and Preneel presented an attack on the alleged SecurID hash function~\cite{BLP}. They showed that {\it vanishing differentials} -- collisions of the hash function -- occur quite frequently, and that such differentials allow an attacker to recover the secret key in the token much faster than exhaustive search. Based on simulation results, they estimated that given a single 2-bit vanishing differential, the running time of their attack would be about $$ full hash operations. In this paper, we first give a more detailed analysis of the attack in~\cite{BLP} and present several techniques to improve it significantly. Our theoretical analysis and implementation experiments show that the running time of our improved attack is about $$ hash operations, though special cases involving $$ 4-bit differentials (which happen about one third of the time) reduce the time further. We then investigate into the use of extra information that an attacker would typically have: multiple vanishing differentials or knowledge that other vanishing differentials do not occur in a nearby time period. When using the extra information, it appears that key recovery can always be accomplished within about $$ hash operations.

In this paper, we generalize the composition construction of Khoo et al. for highly nonlinear Boolean functions. We utilize general quadratic forms instead of the trace map in the construction. The construction composes an n-variable Boolean function and an m-variable quadratic form over field with characteristic 2 to get an nm-variable Boolean function with beautiful spectrum property and a doubled algebraic degree. Especially, the method is suitable to construct functions with 3-valued spectra (bent-like functions) or ones with better spectra (near-bent functions). Our proof technique is based on classification of quadratic forms over finite fields and enumeration of solutions of quadratic equations. We also prove the p-ary analogy of these results for odd prime p.

It has recently been reported that the performance of hyperelliptic curve cryptosystems (HECC) is competitive to that of elliptic curve cryptosystems (ECC). However, it is expected that HECC still can be improved due to their mathematically rich structure. We consider here the application of degenerate divisors of HECC to scalar multiplication. We investigate the operations of the degenerate divisors in the Harley algorithm and the Cantor algorithm of genus 2. The timings of these operations are reported. We then present a novel efficient scalar multiplication method using the degenerate divisors. This method is applicable to cryptosystems with fixed base point, e.g., ElGamal-type encryption, sender of Diffie-Hellman, and DSA. Using a Xeon processor, we found that the double-and-add-always method using the degenerate base point can achieve about a 20% increase in speed for a 160-bit HECC. However, we mounted an timing attack using the time difference to designate the degenerate divisors. The attack assumes that the secret key is fixed and the base point can be freely chosen by the attacker. Therefore, the attack is applicable to ElGamal-type decryption and single-pass Diffie-Hellman — SSL using a hyperelliptic curve could be vulnerable to the proposed attack. Our experimental results show that one bit of the secret key for a 160-bit HECC can be recovered by calling the decryption oracle 500 times.

A compact mesh architecture for supporting the relation collection step of the number field sieve is described. Differing from TWIRL, only isolated chips without inter-chip communication are used. According to a preliminary analysis for 768-bit numbers, with a 130 nm process one mesh-based device fits on a single chip of ca. (4.9 cm)^2 - the largest proposed chips in the TWIRL cluster for 768-bit occupy ca. (6.7 cm)^2. A 300 mm silicon wafer filled with the mesh-based devices is about 6.3 times slower than a wafer with TWIRL clusters, but due to the moderate chip size, lack of inter-chip communication, and the comparatively regular structure, from a practical point of view the mesh-based approach might be as attractive as TWIRL.

In this letter, we show that structured ElGamal-type multisignature scheme due to Burmester et al. is not secure if the adversary attacks key generation.

Blind signature is the concept to ensure anonymity of e-cion. Untracebility and unlinkability are two main properties of real coin, which require mimicking electronically. Proxy signature schemes allow a proxy signer to generate a proxy signature on behalf of an original signer.All the previous proxy signature schemes are based on ElGamal-type schemes.In this paper, we propose a new proxy blind signature scheme based on an ID-based signature scheme, which uses bilinear pairings of elliptic curves or hyperelliptic curves.

We present a cryptanalysis of a MAC proposal at CRYPTO 2003 due to Cary and Venkatesan. Our attacks find collisions for the MAC and yield MAC forgeries, both faster than a straightforward application of the birthday paradox would suggest.

We consider the problem of constructing perfect nonlinear multi-output Boolean functions satisfying higher order strict avalanche criteria (SAC). Our first construction is an infinite family of 2-ouput perfect nonlinear functions satisfying higher order SAC. This construction is achieved using the theory of bilinear forms and symplectic matrices. Next we build on a known connection between 1-factorization of a complete graph and SAC to construct more examples of 2 and 3-output perfect nonlinear functions. In certain cases, the constructed S-boxes have optimal trade-off between the following parameters: numbers of input and output variables, nonlinearity and order of SAC. In case the number of input variables is odd, we modify the construction for perfect nonlinear S-boxes to obtain a construction for maximally nonlinear S-boxes satisfying higher order SAC. Our constructions present the first examples of perfect nonlinear and maximally nonlinear multioutput S-boxes satisfying higher order SAC. Lastly, we present a simple method for improving the degree of the constructed functions with a small trade-off in nonlinearity and the SAC property. This yields functions which have possible applications in the design of block ciphers.

In a proxy signature scheme, a potential signer delegates his capabilities to a proxy signer, who can sign documents on behalf of him. The recipient of the signature verifies both identities: that of the delegator and that of the proxy signer. There are many proposals of proxy signature schemes, but security of them has not been considered in a formal way until the appearance of the work by Boldyreva et al. If the entities which take part in a proxy signature scheme are formed by sets of participants, then we refer to it as a fully distributed proxy signature scheme. In this work, we extend the security definitions introduced by Boldyreva et al. to the scenario of fully distributed proxy signature schemes, and we propose a specific scheme which is secure in this new model.

A proxy signature scheme allows an entity to delegate his/her signing capability to another entity in such a way that the latter can sign messages on behalf of the former. Such schemes have been suggested for use in a number of applications, particularly in distributed computing where delegation of rights is quite common. Followed by the first schemes introduced by Mambo, Usuda and Okamoto in 1996, a number of new schemes and improvements have been proposed. In this paper, we present a security analysis of four such schemes newly proposed in [15,16]. By successfully identifying several interesting forgery attacks, we show that all the four schemes are insecure. Consequently, the fully distributed proxy scheme in [11] is also insecure since it is based on the (insecure) LKK scheme [14,15]. In addition, we point out the reasons why the security proofs provided in [15] are invalid.

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.