A (public key) Trace and Revoke Scheme combines the functionality of broadcast encryption with the capability of traitor tracing. Specifically, (1) a trusted center publishes a single public key and distributes individual secret keys to the users of the system; (2) anybody can encrypt a message so that all but a specified subset of ``revoked'' users can decrypt the resulting ciphertext; and (3) if a (small) group of users combine their secret keys to produce a ``pirate decoder'', the center can trace at least one of the ``traitors'' given access to this decoder. We construct the first chosen ciphertext (CCA2) secure Trace and Revoke Scheme based on the DDH assumption. Our scheme is also the first adaptively secure scheme, allowing the adversary to corrupt players at any point during execution, while prior works (e.g., [NP00,TT01]) only achieves a very weak form of non-adaptive security even against chosen plaintext attacks. In fact, no CCA2 scheme was known even in the symmetric setting. Of independent interest, we present a slightly simpler construction that shows a ``natural separation'' between the classical notion of CCA2 security and the recently proposed [Sho01,ADR02] relaxed notion of gCCA2 security.

We present a kind of group suitable for cryptographic applications: the trace zero subvariety. The construction is based on Weil descent from curves of genus two over extension fields $$, $$. On the Jacobian of the curve the group can be seen as a prime order subgroup, however, considering the construction as Weil descent we can argue that the security is equivalent to that of groups based on low-genus hyperelliptic curves over prime fields. The advantage is that the complexity to compute scalar multiples is lower, as one can make use of the Frobenius endomorphism of the initial curve. Thus the trace zero subvariety can be used efficiently in protocols based on the discrete logarithm problem.

We put forward the first secret-key steganographic construction that is both black-box (i.e., the sender need not have knowledge of the channel beyond the ability to sample from it) and stateless (i.e., the sender and the recipient need not maintain synchronized state when sending multiple bits). Both of these properties are important: the first because in many settings it is unrealistic to assume detailed knowledge of the underlying channel distribution, and the second because maintaining synchronized state between the sender and the recipient is particularly problematic in steganography, where communication to resynchronize will alert the adversary. For channels of sufficient entropy, our construction is more efficient than previous black-box constructions. Moreover, it is the first one to provide a tradeoff between the number of samples the encoder needs and the rate at which hiddentext is transmitted.

This paper analyses the authentication and key agreement protocol adopted by Universal Mobile Telecommunication System (UMTS), an emerging standard for third generation (3G) wireless communications. The protocol, known as {\em 3GPP AKA}, is based on the security framework of GSM and provides significant enhancement to address and correct real and perceived weaknesses in GSM and other wireless communication systems. In this paper, we show that 3GPP AKA is vulnerable to a variant of false base station attack. The vulnerability allows an adversary to re-direct user traffic to an unintended network. It also allows an adversary to use authentication vectors obtained from a corrupted network to impersonate all other networks. In addition, we show that the need of synchronization between a mobile station and its home network incurs considerable difficulty for the normal operation of 3GPP AKA. To provide further enhancement on 3GPP AKA, we present an authentication and key agreement protocol which defeats re-direction attack and drastically lowers the impact of network corruption. The proposed protocol also eliminates synchronization between a mobile station and its home network. Following the multi-party simulatability approach, we have developed a formal model of security for symmetric-key based authentication and key agreement protocols in the mobile setting. Within this model, we have analyzed the security of our protocol against a powerful adversary having full control of the communication channels between a user and a network.

An aggregate signature scheme (recently proposed by Boneh, Gentry, Lynn and Shacham) is a method for combining $$ signatures from $$ different signers on $$ different messages into one signature of unit length. We propose \emph{sequential aggregate signatures}, in which the set of signers is ordered. The aggregate signature is computed by having each signer, in turn, add his signature to it. We show how to realize this in such a way that the size of the aggregate signature is independent of $$. This makes sequential aggregate signatures a natural primitive for certificate chains, whose length can be reduced by aggregating all signatures in a chain. We give a construction based on families of certified trapdoor permutations, and show how to instantiate our scheme based on RSA.

In this paper, the authors propose a new structured multisignature scheme that considers the signing order among co-signers. The proposed scheme can resolve signing structures of serial, parallel, and the mix of them. Moreover, the size and the verification of a structured multisignature is the same as those of an individual signature generated by any co-signer. Arithmetically, the proposed scheme makes use of the Gap Diffie-Hellman (GDH) signature scheme recently presented by Boneh, Shacham, and Lynn. Due to the underlying GDH group, our scheme has the merits of simplicity in construction and efficiency in performance.

Asymmetric cryptographic systems using multivariate polynomials over finite fields have been proposed several times since the 1980s. Although some of them have been successfully broken, the area is still vital and promises interesting algorithms with low computational costs, short message, and signature sizes. In this paper, we present two novel strategies ``base transformation" and ``adapted evaluation" for the generation of the public key in such schemes. We demonstrate both at the example of the Hidden Field Equations (HFE) system and outline how they can be adapted to similar systems. In addition, we compare the running time of the previously known technique ``polynomial interpolation" with our new developments both from a theoretical perspective and by empirical studies. These experiments confirm our theoretical studies, namely, base transformation is faster than polynomial interpolation. Especially the first step is $$ while it is $$ for polynomial interpolation where $$ denotes the number of variables. Moreover, the running time of polynomial interpolation is approximately 30\% higher than for base transformation.

A method for elliptic curve point multiplication is proposed with complex multiplication by Sqrt[-2] or by (1+Sqrt[-7])/2 instead of point duplication, speeding up multiplication about 1.34 times. Higher radix makes it possible to use one point duplication instead of two and to speed up computation about 1.6 times. We employ prime group order factorization in corresponding quadratic order and integer exponent reduction modulo quadratic prime in the Euclidean imaginary quadratic ring.

We study elliptic curve cryptosystems by first investigating the schemes defined over $$ and show that the scheme is provably secure against adaptive chosen cipher-text attack under the decisional Diffie-Hellman assumption. Then we derive a practical elliptic curve cryptosystem by making use of some nice elliptic curve where the decisional Diffie-Hellman assumption is reserved.

We propose a simple algorithm to select group generators suitable for pairing-based cryptosystems. The selected parameters are shown to favor implementations of the Tate pairing that are at once conceptually simple and efficient, with an observed performance about 2 to 10 times better than previously reported implementations, depending on the embedding degree. Our algorithm has beneficial side effects: various non-pairing operations become faster, and bandwidth may be saved.

We show all the existing TTM implementation schemes have a defect that there exist linearization equations $$ which are satisfied by the components $$ of the ciphers of the TTM schemes. We further demonstrate that, for the case of the most recent two implementation schemes in two versions of the paper \cite{CM}, where the inventor of TTM used them to refute a claim in \cite{CG}, if we do a linear substitution with the linear equations derived from the linearization equations for a given ciphertext, we can find the plaintext easily by an iteration of the procedure of first search for linear equations by linear combinations and then linear substitution. The computation complexity of the attack on these two schemes is less than $$ over a finite field of size $$.

A Tamed Transformation Method (TTM) cryptosystem was proposed by T.T.Moh in 1999. We describe how the first implementation scheme of the TTM system can be defeated. The computational complexity of our attack is $$ computations on the finite field with $$ elements.

Cryptographic computations are often carried out on insecure devices for which the threat of key exposure represents a serious and realistic concern. In an effort to mitigate the damage caused by exposure of secret keys stored on such devices, the paradigm of \emph{forward security} was introduced. In a forward-secure scheme, secret keys are updated at regular periods of time; exposure of the secret key corresponding to a given time period does not enable an adversary to ``break'' the scheme (in the appropriate sense) for any \emph{prior} time period. A number of constructions of forward-secure digital signature schemes, key-exchange protocols, and symmetric-key schemes are known. We present the first non-trivial constructions of (non-interactive) forward-secure public-key encryption schemes. Our main construction achieves security against chosen-plaintext attacks under the decisional bilinear Diffie-Hellman assumption in the standard model. This scheme is practical, and all parameters grow at most logarithmically with the total number of time periods. We also give a slightly more efficient scheme in the random oracle model. Both our schemes can be extended to achieve security against chosen-ciphertext attacks and to support an unbounded number of time periods. Toward our goal, we introduce the notion of \emph{binary tree encryption} and show how to construct a binary tree encryption scheme in the standard model. This new primitive may be of independent interest. In particular, we use it to construct the first known example of a (hierarchical) identity-based encryption scheme that is secure in the standard model. (Here, however, the notion of security we achieve is slightly weaker than what is achieved in some previous constructions in the random oracle model.)

OMAC, TMAC and XCBC are CBC-type MAC schemes which are provably secure for arbitrary message length. In this paper, we present a more tight upper bound on $$ for each scheme, where $$ denotes the maximum success (forgery) probability of adversaries. Our bounds are expressed in terms of the \textit{total length} of all queries of an adversary to the MAC generation oracle while the previous bounds are expressed in terms of the \textit{maximum length} of each query. In particular, a significant improvement occurs if the lengths of queries are heavily unbalanced.

SOBER-128 joins the SOBER family of stream ciphers, with the added functionality of incorporating a Message Authentication Code generator if required. SOBER-128 draws on the research into the previous SOBER ciphers: the design does not differ significantly from its predecessor SOBER-t32. The biggest change is the replacement of the stuttering with a strengthened non-linear function. SOBER-128 is faster and more secure than SOBER-t32.

We consider non-malleable (NM) and universally composable (UC) commitmentschemes in the common reference string (CRS) model. We show how to construct non-interac\-tive NM commitments that remain non-malleable even if the adversary has access to an arbitrary number of commitments from honest players - rather than one, as in several previous schemes. We show this is a strictly stronger security notion. Our construction is the first non-interactive scheme achieving this that can be based on the minimal assumption of existence of one-way functions. But it can also be instantiated in a very efficient version based on the strong RSA assumption. For UC commitments, we show that existence of a UC commitment scheme in the CRS model (interactive or not) implies key exchange and - for a uniform reference string - even implies oblivious transfer. This indicates that UC commitment is a strictly stronger primitive than NM. Finally, we show that our strong RSA based construction can be used to improve the most efficient known UC commitment scheme so it can work with a CRS of size independent of the number of players, without loss of efficiency.

In this paper we present a fast addition algorithm in the Jacobian of a Picard curve over a finite field $$ of characteristic different from $$. This algorithm has a nice geometric interpretation, comparable to the classic "chord and tangent" law for the elliptic curves. Computational cost for addition is $$ and $$ for doubling.

This paper studies the relation among simulator-based and comparison-based definitions of semantic security. The definitions are considered in a more general framework than the ordinal one; namely, an adversary is assumed to have access to prior information of a plaintext. If the framework is restricted to the ordinal one, then all the security notions considered in this paper, including indistinguishability, are shown to be equivalent. On the other hand, the equivalence is not necessarily valid in the general framework. In fact, it is shown that no encryption scheme is secure in the sense of comparison-based semantic security in the strongest forms. Furthermore, a sufficient condition for the equivalence between semantic security and indistinguishability is derived.

We present a simple, natural random-oracle (RO) model scheme, for a practical goal, that is uninstantiable, meaning is proven in the RO model to meet its goal yet admits NO standard-model instantiation that meets this goal. The goal in question is IND-CCA-preserving asymmetric encryption which formally captures security of the most common practical usage of asymmetric encryption, namely to transport a symmetric key in such a way that symmetric encryption under the latter remains secure. The scheme is an ElGamal variant, called Hash ElGamal, that resembles numerous existing RO-model schemes, and on the surface shows no evidence of its anomalous properties. More generally, we show that a certain goal, that we call key-verifiable, ciphertext-verifiable IND-CCA-preserving asymmetric encryption, is achievable in the RO model (by Hash ElGamal in particular) but unachievable in the standard model. This helps us better understand the source of the anomalies in Hash ElGamal and also lifts our uninstantiability result from being about a specific scheme to being about a primitive or goal. These results extend our understanding of the gap between the standard and RO models, and bring concerns raised by previous work closer to practice by indicating that the problem of RO-model schemes admitting no secure instantiation can arise in domains where RO schemes are commonly designed.

In this paper, an algorithm on Goldbach’s conjecture is newly defined for computing a large even number as a sum of two primes or a sum of prime and composite. Using the conjecture, an ECDSA (Elliptic Curve Digital Signature Algorithm) protocol is newly proposed for authentication. The protocol describes the process of key generation, signature generation and signature verification as well as security issues.

$$ of order $$ is one of the most general cryptographic criteria of secure Boolean functions. In this paper, we introduce its $$-almost version. The new definition requires {\it only} that $$ is {\it almost} uniformly distiributed (while the original definition of $$ of order $$ requires that it is {\it strictly} uniformly distiributed). We next show its construciton. Better parameters are then obtained than normal $$ of order $$ functions.

Electronic voting is a prime application of cryptographic tools. Many researches are addressing election or confidence voting in this area. We address a new type of voting scheme ``Divisible Voting Scheme,'' in which each voter has multiple ballots where the number of ballots can be different among the voters. This type of voting is popular, however there is no secure protocol which achieves this type of voting. We first define the divisible voting scheme and show naive protocols based on existing voting schemes. Then we propose two efficient divisible voting schemes. The first scheme uses multisets, the second scheme uses $$-adic representation of number of ballots. The total cost for a voter is $$ in the first scheme and $$ in the second scheme where $$ is the number of candidates to vote for and $$ is the number of ballots for a voter.

Mambo et al [6-7] introduced a proxy signature scheme. Neuman [8] extended the scheme for delegation by warrant, which was further extended by Kim et al [4] to partial delegation with a warrant. In this paper we propose a new type of digital proxy signature scheme in which the warrant message can be recovered from the proxy signature. In this scheme the warrant message is conveyed within the proxy signature and recovered by the verifier, i.e., the warrant need not be hashed or sent along with the proxy signature. It saves both communication bandwidth and storage space.

Blind signature is the concept to ensure anonymity of e-coins. Untracebility and unlinkability are two main properties of real coins, which require mimicking electronically. Whenever a user is permitted to spend an e-coin, he is in need to fulfill above requirements of blind signature. This paper proposes a proxy blind signature scheme with which a proxy is able to make proxy blind signature which verifier is able to verify in a way similar to proxy signature schemes.

We consider how to avoid unsolicited e-mail -- so called spam -- in a stronger adversarial model than has previously been considered. Our primary concern is the proposal of an architecture and of protocols preventing against successful spamming attacks launched by a strong attacker. This attacker is assumed to control the communication media and to be capable of corrupting large numbers of protocol participants. Additionally, the same architecture can be used as a basis to support message integrity and privacy, though this is not a primary goal of our work. This results in a simple and efficient solution that is largely backwards-compatible, and which addresses many of the concerns surrounding e-mail communication.

CCM is a conventional authenticated-encryption scheme obtained from a 128-bit block cipher. The mechanism has been adopted as the mandatory encryption algorithm in an IEEE 802.11 draft standard [15], and its use has been proposed more broadly [16,17]. In this note we point out a number of limitations of CCM. A related note provides an alternative to CCM [5].

We propose a block-cipher mode of operation, called EAX, for authenticated-encryption with associated-data (AEAD). Given a nonce N, a message M, and a header H, the mode protects the privacy of M and the authenticity of both M and H. Strings N,M,H$$2\lceil |M|/n \rceil + \lceil |H|/n\rceil + \lceil |N|/n\rceil$ block-cipher calls when these strings are nonempty and n is the block length of the underlying block cipher. Among EAX's characteristics are that it is on-line (the length of a message isn't needed to begin processing it) and a fixed header can be pre-processed, effectively removing the per-message cost of binding it to the ciphertext. EAX is obtained by instantiating a simple generic-composition method, and then collapsing its two keys into one. EAX is provably secure under a standard complexity-theoretic assumption. EAX was designed in response to the expressed need of several standardization bodies, including NIST, IETF and IEEE 802.11, for a patent-free AEAD scheme. Such a scheme would have to be conventional, meaning it would make two passes, one aimed at achieving privacy and one aimed at achieving authenticity. EAX aims to fill this need by doing as well as possible within the space of conventional schemes with regard to issues of efficiency, simplicity, elegance, ease of correct use, and provable-security guarantees. EAX is an alternative to CCM.

Digital signature scheme is an important research topic in cryptography. An ordinary digital signature scheme allows a signer to create signatures of documents and the generated signatures can be verified by any person. A proxy signature scheme, a variation of ordinary digital signature scheme, enables a proxy signer to sign messages on behalf of the original signer. To be used in different applications, many proxy signatures were proposed. In this paper, we review Lee et al.'s strong proxy signature scheme, multi-proxy signature scheme, and its application to a secure mobile agent, Shum and Wei's privacy protected strong proxy signature scheme, and Park and Lee's nominative proxy signature scheme, and show that all these proxy signature schemes are insecure against the original signer's forgery. In other words, these schemes do not possess the unforgeability property which is a desired security requirement for a proxy signature scheme.

Pointcheval and Stern introduced in 1996 some forking lemmas useful to prove the security of a family of digital signature schemes. This family includes, for example, Schnorr's scheme and a modification of ElGamal signature scheme. In this work we generalize these forking lemmas to the ring signatures' scenario. In a ring signature scheme, a signer in a subset (or {\it ring}) of potential signers produces a signature of a message in such a way that the receiver can verify that the signature comes from a member of the ring, but cannot know which member has actually signed. We propose a new ring signature scheme, based on Schnorr signature scheme, which provides unconditional anonymity. We use the generalized forking lemmas to prove that this scheme is existentially unforgeable under adaptive chosen-message attacks, in the random oracle model.

An Identity-based cryptosystem is a Public Key cryptosystem in which the public keys of the entities are their identities, or strings derived from their identities. Signcryption combines digital signatures and encryption with a cost significantly smaller than that required for signature-then-encryption. This paper proposes an ID-based signcryption scheme based on bilinear pairings on elliptic curves. It is shown that the new scheme is an improved version of the existing signcryption scheme [10] by comparing the computations in both the schemes.

Textbooks tell us that a birthday attack on a hash function $$ with range size $$ requires $$ trials (hash computations) to find a collision. But this is misleading, being true only if $$ is regular, meaning all points in the range have the same number of pre-images under $$; if $$ is not regular, \textit{fewer} trials may be required. But how much fewer? This paper addresses this question by introducing a measure of the ``amount of regularity'' of a hash function that we call its balance, and then providing estimates of the success-rate of the birthday attack as a function of the balance of the hash function being attacked. In particular, we will see that the number of trials to find a collision can be significantly less than $$ for hash functions of low balance. This leads us to examine popular design principles, such as the MD (Merkle-Damgård) transform, from the point of view of balance preservation, and to mount experiments to determine the balance of popular hash functions.

In this paper, we consider the statistical decision processes behind a linear and a differential cryptanalysis. By applying techniques and concepts of statistical hypothesis testing, we describe precisely the shape of optimal linear and differential distinguishers and we improve known results of Vaudenay concerning their asymptotic behaviour. Furthermore, we formalize the concept of ``sequential distinguisher'' and we illustrate potential applications of such tools in various statistical attacks.

Key exchange protocols in the setting of universal composability are investigated. First we show that the ideal functionality F_KE of [CK02] cannot be realized in the presence of adaptive adversaries, thereby disproving a claim in [CK02]. We proceed to propose a modification F_KE^(i,j), which is proven to be realizable by two natural protocols for key exchange. Furthermore, sufficient conditions for securely realizing this modified functionality are given. Two notions of key exchange are introduced that allow for security statements even when one party is corrupted. Two natural key exchange protocols are proven to fulfill the "weaker" of these notions, and a construction for deriving protocols that satisfy the "stronger" notion is given.

We present a secure unauthenticated as well as an authenticated multi party key agreement protocol. The unauthenticated 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.

We propose public-key cryptosystems with public key a system of polynomial equations, algebraic or differential, and private key a single polynomial or a small-size ideal. We set up probabilistic encryption, signature, and signcryption protocols.

In this paper we determine the number of isomorphism classes of Picard curves, i.e., superelliptic curves $$ of genus three, over finite fields of characteristic different from $$. In the process of doing this we also provide reduced forms of Picard curves together the number of such forms up to isomorphism. In addition to its own theoretical meaning it has applications to cryptography.

All node certificate based transitive signature schemes available in the literature make use of any digital signature scheme which is assumed to be provably secure against adaptive chosen-message attack, as a building block to produce node certificates in a graph. Consequently the algebraic structures to represent nodes in the graph are independent of the algebraic structure of signature scheme employed. This inconsistence of representation structures of the signature scheme, nodes and edges in the graph could increase the cost to manage those public data. For example, the transitive signature schemes presented by Micali and Rivest \cite{MR} and Bellare and Neven (the node certificate based version FBTS-1, in \cite{BN}), both heavily rely on the standard provably secure signature scheme (say Goldwasser-Micali-Rivest's signature scheme \cite{GMR}). Consequently, a core problem related to transitive signature schemes is {\it how to construct transitive signature schemes so that the representation structures of signature schemes, nodes and edges in a graph can be implemented compactly?} \vskip 2mm Bellare and Neven's hash-based modification, FBTS-2, achieving shorter signatures by eliminating the need for node certificates and provable under the same factoring assumption in the random oracle model, is actually the first solution to the above question. Our approach to attack the problem mentioned above, is different from Bellare and Neven's. We attack the problem by first carefully defining algebraic structure to represent vertices and edges in an undirected graph, then we construct a signature scheme so that its algebraic structure is coincident with that of vertices and edges in the graph. Finally, we present a practical realization of a transitive signature scheme that is proven transitively unforgeable under adaptive chosen message attack in the standard intractability paradigm. To the best knowledge of authors, this approach has NOT been reported in the literature.

We propose an elliptic curve trapdoor system which is of interest in key escrow applications. In this system, a pair ($$) of elliptic curves over $$ is constructed with the following properties: (i) the Gaudry-Hess-Smart Weil descent attack reduces the elliptic curve discrete logarithm problem (ECDLP) in $$ to a hyperelliptic curve DLP in the Jacobian of a curve of genus 7 or 8, which is computationally feasible, but by far not trivial; (ii) $$ is isogenous to $$; (iii) the best attack on the ECDLP in $$ is the parallelized Pollard rho method. The curve $$ is used just as usual in elliptic curve cryptosystems. The curve $E_{\rm s} is submitted to a trusted authorityfor the purpose of key escrow. The crucial difference from other key escrow scenarios is that the trusted authority has to invest a considerable amount of computation to compromise a user's private key, which makes applications such as widespread wire-tapping impossible.

We present a new protocol for the following task. Given tow secrets a,b shared among n players, compute the value g^{ab}. The protocol uses the generic BGW approach for multiplication of shared secrets, but we show that if one is computing ``multiplications in the exponent'' the polynomial randomization step can be avoided (assuming the Decisional Diffie-Hellman Assumption holds). This results in a non-interactive and more efficient protocol.

In distributed networks, a target party $$ could be a person never meet with a source party $$, therefore $$ may not hold any prior evaluation of trustworthiness of $$. To get permit to access $$, $$ should be somewhat trusted by $$. Consequently, we should study the approach to evaluate trustworthiness of $$. To attack the problem, we view individual participant in distributed networks as a node of a delegation graph $$ and map a delegation path from target party $$ to source party $$ in networks into an edge in the correspondent transitive closure of graph $$. Based on the transitive closure property of the graph $$, we decompose the problem to three related questions below: -how to evaluate trustworthiness of participants in an edge? -how to compute trustworthiness of participants in a path? -how to evaluate the trustworthiness of a target participant in a transitive closure graph? We attack the above three questions by first computing trustworthiness of participants in distributed and authenticated channel. Then we present a practical approach to evaluate trustworthiness by removing the assumption of the authenticated channel in distributed networks.

Blackmailing may be the most serious drawback of the known electronic cash systems offering unconditional anonymity. Recently, D.Kugler proposed an on-line payment system without trusted party to prevent blackmailing based on the idea of marking. In this paper, some disadvantages of D.Kugler¡¯s scheme are analyzed and then a new online electronic cash scheme to prevent blackmailing is present by using group blind signature technique. In our scheme, the blackmailed cash was marked by an entity, called supervisor, therefore the bank can distinguish it from the valid cash. Also, we can modify our scheme to be offline so that it can used to decrease other crimes, e.g., money laundering, bribery etc. in electronic cash system.

The pairings on elliptic curves have been applied for realizing the secure ID based cryptosystems that can be invulnerable to the collusion attacks. The computation of the pairing are necessary for the cryptosystems, though the computation of the pairing requires high cost compared with the computation cost for the power operation over the finite fields or on the elliptic curve when the parameters are securely to be provided. In this paper we propose an efficient method for a class of ID based cryptosystems which have been proposed by the present authors. The proposed method is able to reduce the number of the computations for the pairing for verifying the ID based signature and also for decoding of the ID based public key cryptosystems with the authentication, by a factor of 2. Moreover we propose the ID based public key cryptosystems with signature and the ID based public key cryptosystems having the multiple centers.

We give a closed formula for the Tate-pairing on the hyperelliptic curve $$ in characteristic $$. This improves recent implementations by Barreto et.al. and by Galbraith et.al. for the special case $$. As an application, we propose a $$-round key agreement protocol for up to $$ participants by extending Joux's pairing-based protocol to $$ rounds.

In this paper we present a practically feasible attack on RSA-based sessions in SSL/TLS protocols. These protocols incorporate the PKCS#1 (v. 1.5) encoding method for the RSA encryption of a premaster-secret value. The premaster-secret is the only secret value that is used for deriving all the particular session keys. Therefore, an attacker who can recover the premaster-secret can decrypt the whole captured SSL/TLS session. We show that incorporating a version number check over PKCS#1 plaintext used in the SSL/TLS creates a side channel that allows the attacker to invert the RSA encryption. The attacker can then either recover the premaster-secret or sign a message on behalf of the server. Practical tests showed that two thirds of randomly chosen Internet SSL/TLS servers were vulnerable. The attack is an extension of Bleichenbacher’s attack on PKCS#1 (v. 1.5). We introduce the concept of a bad-version oracle (BVO) that covers the side channel leakage, and present several methods that speed up the original algorithm. Our attack was successfully tested in practice and the results of complexity measurements are presented in the paper. Plugging a testing server (2x Pentium III/1.4 GHz, 1 GB RAM, 100 Mb/s Ethernet, OS RedHat 7.2, Apache 1.3.27), it was possible to achieve a speed of 67.7 BVO calls per second for a 1024 bits RSA key. The median time for a whole attack on the premaster-secret could be then estimated as 54 hours and 42 minutes. We also propose and discuss countermeasures, which are both cryptographically acceptable and practically feasible.

A hardware random number generator was described at CHES 2002 by T. Tkacik. In this paper, we analyze its method of generating randomness and, as a consequence of the analysis, we describe how, in principle, an attack on the generator can be executed.

We introduce a new cryptographic primitive we call **concealment**, which is related, but quite different from the notion of commitment. A concealment is a publicly known randomized transformation, which, on input m, outputs a *hider* h and a *binder* b. Together, h and b allow one to recover m, but separately, (1) the hider h reveals "no information" about m, while (2) the binder b can be "meaningfully opened" by at most one hider h. While setting b=m, h=empty is a trivial concealment, the challenge is to make |b|<<|m|, which we call a "non-trivial" concealment. We show that non-trivial concealments are equivalent to the existence of collision-resistant hash functions. Moreover, our construction of concealments is extremely simple, optimal, and yet very general, giving rise to a multitude of efficient implementations. We show that concealments have natural and important applications in the area of **authenticated encryption**. Specifically, let AE be an authenticated encryption scheme (either public- or symmetric-key) designed to work on short messages. We show that concealments are **exactly** the right abstraction allowing one to use AE for encrypting long messages. Namely, to encrypt long m, one uses a concealment scheme to get h and b, and outputs authenticated ciphertext (AE(b),h). More surprisingly, the above paradigm leads to a very simple and general solution to the problem of **remotely keyed (authenticated) encryption** (RKAE). In this problem, one wishes to split the task of high-bandwidth authenticated encryption between a secure, but low-bandwidth/computationally limited device, and an insecure, but computationally powerful host. We give formal definitions for RKAE, which we believe are simpler and more natural than all the previous definitions. We then show that our composition paradigm satisfies our (very strong) definition. Namely, for authenticated encryption, the host simply sends a short value b to the device (which stores the actual secret key for AE), gets back AE(b), and outputs (AE(b),h) (authenticated decryption is similar). Finally, we also observe that several previous RKAE proposals are all special examples of our general paradigm.

Boneh and Venkatesan have proposed a polynomial time algorithm for recovering a "hidden" element $$, where $$ is prime, from rather short strings of the most significant bits of the residue of $$ modulo $$ for several randomly chosen $$. Gonzälez Vasco and the first author have recently extended this result to subgroups of $$ of order at least $$ for all $$ and to subgroups of order at least $$ for almost all $$. Here we introduce a new modification in the scheme which amplifies the uniformity of distribution of the `multipliers' $$ and thus extend this result to subgroups of order at least $$ for all primes $$. As in the above works, we give applications of our result to the bit security of the Diffie--Hellman secret key starting with subgroups of very small size, thus including all cryptographically interesting subgroups.

In this paper we introduce the class of composite access structures for secret sharing. We also provide secret sharing schemes realizing these structures and study their information rates. As a particular case of this construction, we present the subclass of iterated threshold schemes, a large class of ideal secret sharing schemes.

Extensive studies have been made of the public-key cryptosystems based on multivariate polynomials . However most of the proposed public-key cryptosystems of rate 1.0 based on multivariate polynomials, are proved not secure. In this paper, we propose several types of new constructions of public-key cryptosystems based on two classes of randomly generated simultaneous equations, namely, a class based on bijective transformation and another class based on random transformation. One of the features of the proposed cryptosystems is that the sets of random simultaneous equations significantly improve the utilization factor of the public-key space. We show an example of the proposed cryptosystem whose size is only 100 bits that seems to be apparently secure in a sense that the utilization factor is significantly large compared with the conventional public-key cryptosystems.

Recently, based on Guillou-Quisquater signature scheme, Saeednia proposed an identity-based society oriented signature scheme. However, in this note, we point out that Saeednia's scheme does not satisfy the claimed properties.

Sufficient conditions are obtained on the prime factors of an RSA modulus in order to avoid Wiener and Boneh-Durfee attacks. The public exponent can be chosen arbitrarily.

An Identity-based cryptosystem is a Public Key cryptosystem in which the public keys of the entities are their identities, or strings derived from their identities. Signcryption combines digital signatures and encryption with a cost significantly smaller than that required for signature-then-encryption. This paper proposes an ID-based signcryption scheme based on bilinear pairings on elliptic curves. It is shown that the new scheme is an improved version of the existing signcryption scheme [10] by comparing the computations in both the schemes.

We present a new, elegant composition method for joint signature and encryption, also referred to as signcryption. The new method, which we call *Padding-based Parallel Signcryption* (PbPS), builds an efficient signcryption scheme from any family of trapdoor permutations, such as RSA. Each user U generates a single public/secret key pair f_U/f^{-1}_U used for both sending and receiving the data. To signcrypt a message m to a recipient with key f_{rcv}, a sender with key f_{snd} efficiently transforms m into a pair {w|s}, and simply sends { f_{rcv}(w) | f^{-1}_{snd}(s) }. PbPS enjoys many attractive properties: simplicity, efficiency, generality, parallelism of ``encrypting''/``signing'', optimal exact security, flexible and ad-hoc key management, key reuse for sending/receiving data, optimally-low message expansion, long message and associated data support, and, finally, complete compatibility with the PKCS#1 infrastructure. The pairs {w|s} sufficient for the security of PbPS are called *universal two-padding schemes*. Using one round of the Feistel transform, we give a very general construction of such schemes. Interestingly, we notice that all popular padding schemes with message recovery used for plain signature or encryption, such as OAEP, OAEP+, PSS-R, and ``scramble all, encrypt small'', naturally consist of two pieces {w|s}. Quite remarkably, we show that all such pairs become special cases of our construction. As a result, we find a natural generalization of all conventional padding schemes, and show that any such padding can be used for signcryption with PbPS. However, none of such paddings gives optimal message bandwidth. For that purpose and of independent interest, we define a new ``hybrid'' between PSS-R and OAEP, which we call *Probabilistic Signature-Encryption Padding* (PSEP). We recommend using PbPS with PSEP to achieve the most flexible and secure signcryption scheme up-to-date. To justify this point, we provide a detailed practical comparison of PbPS/PSEP with other previously-proposed signcryption candidates.

In this paper we show how to achieve timed fair exchange of digital signatures of standard type. Timed fair exchange (in particular, contract signing) has been considered before, but only for Rabin and RSA signatures of a special kind. Our construction follows the gradual release paradigm, and works on a new ``time'' structure that we call a {\em mirrored time-line.} Using this structure, we design a protocol for the timed fair exchange by two parties of arbitrary values (values lying on their respective mirrored time-lines). Finally, we apply the blinding techniques of Garay and Jakobsson to turn this protocol into a protocol for the timed fair exchange of standard signatures. The length of these mirrored time-lines makes another problem apparent, which is making sure that the underlying sequence has a period large enough so that cycling is not observed. We also show how to construct these structures so that, under reasonable assumptions, this is indeed the case.

The shrinking generator is a well-known keystream generator composed of two linear feedback shift registers, LFSR$$ and LFSR$$, where LFSR$$ is clock-controlled according to regularly clocked LFSR$$. The keystream sequence is thus a decimated LFSR$$ sequence. Statistical distinguishers for keystream generators are algorithms whose objective is to distinguish the keystream sequence from a purely random sequence. Previously proposed statistical distinguishers for the shrinking generator are based on detecting binary linear relations in the keystream sequence that hold with a probability sufficiently different from one half. In this paper a novel approach which significantly reduces the required computation time is introduced. It is based on a probabilistic reconstruction of the bits in the regularly clocked LFSR$$ sequence that satisfy the LFSR$$ recurrence or any linear recurrence derived from low-weight multiples of the LFSR$$ characteristic polynomial. The keystream sequence length and the computation time required for a reliable statistical distinction are analyzed both theoretically and experimentally.

We study the relationship between the Walsh transform and the algebraic normal form of a Boolean function. In the first part of the paper, we carry out a combinatorial analysis to obtain a formula for the Walsh transform at a certain point in terms of parameters derived from the algebraic normal form. The second part of the paper is devoted to simplify this formula and develop an algorithm to evaluate it. Our algorithm can be applied in situations where it is practically impossible to use the fast Walsh transform algorithm. Experimental results show that under certain conditions it is possible to execute our algorithm to evaluate the Walsh transform (at a small set of points) of functions on a few scores of variables having a few hundred terms in the algebraic normal form.

We introduce cryptography based on algebraic tori, give a new public key system called CEILIDH, and compare it to other discrete log based systems including LUC and XTR. Like those systems, we obtain small key sizes. While LUC and XTR are essentially restricted to exponentiation, we are able to perform multiplication as well. We also disprove the open conjectures from the paper "Looking beyond XTR", and give a new algebro-geometric interpretation of the approach in that paper and of LUC and XTR.

In this paper, we propose a pretty-simple password-authenticated key-exchange protocol, which is proven to be secure in the standard model under the following three assumptions. (1) DDH (Decision Diffie-Hellman) problem is hard. (2) The entropy of the password is large enough to avoid on-line exhaustive search (but not necessarily off-line exhaustive search). (3) MAC is selectively unforgeable against partially chosen message attacks, (which is weaker than being existentially unforgeable against chosen message attacks).

Recently there has been an interest in zero-knowledge protocols with stronger properties, such as concurrency, unbounded simulation soundness, non-malleability, and universal composability. In this paper, we show a novel technique to convert a large class of existing honest-verifier zero-knowledge protocols into ones with these stronger properties in the common reference string model. More precisely, our technique utilizes a signature scheme existentially unforgeable against adaptive chosen-message attacks, and transforms any $$-protocol (which is honest-verifier zero-knowledge) into an unbounded simulation sound concurrent zero-knowledge protocol. We also introduce $$-protocols, a variant of $$-protocols for which our technique further achieves the properties of non-malleability and/or universal composability. In addition to its conceptual simplicity, a main advantage of this new technique over previous ones is that it avoids the Cook-Levin theorem, which tends to be rather inefficient. Indeed, our technique allows for very efficient instantiation based on the security of some efficient signature schemes and standard number-theoretic assumptions. For instance, one instantiation of our technique yields a universally composable zero-knowledge protocol under the Strong RSA assumption, incurring an overhead of a small constant number of exponentiations, plus the generation of two signatures.

We describe a cryptanalysis of a public-key encryption scheme based on the polynomial reconstruction problem. Given the public-key and a ciphertext, we recover the corresponding plaintext in polynomial time. Therefore, the scheme is not one-way. Our technique is a variant of the Berlekamp-Welsh algorithm.

The proposed approach works for any underlying secret sharing scheme. It is based on the concept of verification sets of participants, related to authorized set of participants. The participants interact (no third party involved) in order to check validity of their shares before they are pooled for secret recovery. Verification efficiency does not depend on the number of faulty participants.

In 1986, Fiat and Shamir suggested a general method for transforming secure 3-round public-coin identification schemes into digital signature schemes. The significant contribution of this method is a means for designing efficient digital signatures, while hopefully achieving security against chosen message attacks. All other known constructions which achieve such security are substantially more inefficient and complicated in design. In 1996, Pointcheval and Stern proved that the signature schemes obtained by the Fiat-Shamir transformation are secure in the so called `Random Oracle Model'. The question is: does the proof of the security of the Fiat-Shamir transformation in the Random Oracle Model, imply that the transformation yields secure signature schemes in the ``real-world"? In this paper we answer this question negatively. We show that there exist secure 3-round public-coin identification schemes for which the Fiat-Shamir methodology produces {\bf insecure} digital signature schemes for {\bf any} implementation of the `Random Oracle Model' in the `real-world' by a function ensemble.

In this paper we describe an integral distinguisher over 2 rounds of Safer++. It allows a practical attack against 3 rounds of Safer++128, as well as attacks on 4 rounds of Safer++128 and Safer++256, under the chosen-plaintext hypothesis. These results achieve much lower complexity than the currently known best attacks on Safer++, namely weak-key linear cryptanalysis by Nakahara. As a side result, we prove that the byte-branch number of the linear transform of Safer++ is 5. We also discuss a way for further research in order to extend integral cryptanalysis.

In this paper we present a general framework for password-based authenticated key exchange protocols, in the common reference string model. Our protocol is actually an abstraction of the key exchange protocol of Katz et al.\ and is based on the recently introduced notion of smooth projective hashing by Cramer and Shoup. We gain a number of benefits from this abstraction. First, we obtain a modular protocol that can be described using just three high-level cryptographic tools. This allows a simple and intuitive understanding of its security. Second, our proof of security is significantly simpler and more modular. Third, we are able to derive analogues to the Katz et al.\ protocol under additional cryptographic assumptions. Specifically, in addition to the DDH assumption used by Katz et al., we obtain protocols under both the Quadratic and $$-Residuosity assumptions. In order to achieve this, we construct new smooth projective hash functions.

We propose a new notion of cryptographic tamper evidence. A tamper-evident signature scheme provides an additional procedure Div which detects tampering: given two signatures, Div can determine whether one of them was generated by the forger. Surprisingly, this is possible even after the adversary has inconspicuously learned some --- or even all --- the secrets in the system. In this case, it might be impossible to tell which signature is generated by the legitimate signer and which by the forger. But at least the fact of the tampering will be made evident. We define several variants of tamper-evidence, differing in their power to detect tampering. In all of these, we assume an equally powerful adversary: she adaptively controls all the inputs to the legitimate signer (i.e., all messages to be signed and their timing), and observes all his outputs; she can also adaptively expose all the secrets at arbitrary times. We provide tamper-evident schemes for all the variants and prove their optimality. We stress that our mechanisms are purely cryptographic: the tamper-detection algorithm Div is stateless and takes no inputs except the two signatures (in particular, it keeps no logs), we use no infrastructure (or other ways to conceal additional secrets), and we use no hardware properties (except those implied by the standard cryptographic assumptions, such as random number generators). Our constructions are based on arbitrary ordinary signature schemes and do not require random oracles.

Secure multi-party computation (MPC) is an active research area, and a wide range of literature can be found nowadays suggesting improvements and generalizations of existing protocols in various directions. However, all current techniques for secure MPC apply to functions that are represented by (boolean or arithmetic) circuits over finite {\em fields}. We are motivated by two limitations of these techniques: {\sc Generality.} Existing protocols do not apply to computation over more general algebraic structures (except via a brute-force simulation of computation in these structures). {\sc Efficiency.} The best known {\em constant-round} protocols do not efficiently scale even to the case of large finite fields. Our contribution goes in these two directions. First, we propose a basis for unconditionally secure MPC over an arbitrary finite {\em ring}, an algebraic object with a much less nice structure than a field, and obtain efficient MPC protocols requiring only a {\em black-box access} to the ring operations and to random ring elements. Second, we extend these results to the constant-round setting, and suggest efficiency improvements that are relevant also for the important special case of fields. We demonstrate the usefulness of the above results by presenting a novel application of MPC over (non-field) rings to the round-efficient secure computation of the maximum function.

We prove that three OAEP-inspired randomised padding schemes (i.e., OAEP, OAEP+ and SAEP), when used with the RSA function in the trapdoor direction, form provably secure signature schemes with message recovery. Two of our three reductionist proofs are tight and hence provide exact security. Because of the exact security and OAEP's optimally high bandwidth for message recovery, our results form a desirable improvement from a previous universal RSA padding scheme good for both encryption and signature.

Elliptic curve cryptosystems in the presence of faults were studied by Biehl, Meyer and Mueller (2000). The first fault model they consider requires that the input point P in the computation of dP is chosen by the adversary. Their second and third fault models only require the knowledge of P. But these two latter models are less `practical' in the sense that they assume that only a few bits of error are inserted (typically exactly one bit is supposed to be disturbed) either into P just prior to the point multiplication or during the course of the computation in a chosen location. This report relaxes these assumptions and shows how random (and thus unknown) errors in either coordinates of point P, in the elliptic curve parameters or in the field representation enable the (partial) recovery of multiplier d. Then, from multiple point multiplications, we explain how this can be turned into a total key recovery. Simple precautions to prevent the leakage of secrets are also discussed.

We develop cryptographically secure techniques to guarantee unconditional privacy for respondents to polls. Our constructions are efficient and practical, and are shown not to allow cheating respondents to affect the ``tally'' by more than their own vote --- which will be given the exact same weight as that of other respondents. We demonstrate solutions to this problem based on both traditional cryptographic techniques and quantum cryptography.

For most of the time since they were proposed, it was widely believed that hyperelliptic curve cryptosystems (HECC) carry a substantial performance penalty compared to elliptic curve cryptosystems (ECC) and are, thus, not too attractive for practical applications. Only quite recently improvements have been made, mainly restricted to curves of genus 2. The work at hand advances the state-of-the-art considerably in several aspects. First, we generalize and improve the closed formulae for the group operation of genus 3 for HEC defined over fields of characteristic two. For certain curves we achieve over 50% complexity improvement compared to the best previously published results. Second, we introduce a new complexity metric for ECC and HECC defined over characteristic two fields which allow performance comparisons of practical relevance. It can be shown that the HECC performance is in the range of the performance of an ECC; for specific parameters HECC can even possess a lower complexity than an ECC at the same security level. Third, we describe the first implementation of a HEC cryptosystem on an embedded (ARM7) processor. Since HEC are particularly attractive for constrained environments, such a case study should be of relevance.

Homomorphic cryptosystems are designed for the first time over any finite group. Applying Barrington's construction we produce for any boolean circuit of the logarithmic depth its encrypted simulation of a polynomial size over an appropriate finitely generated group.

Two common notions of security for public key encryption schemes are shown to be equivalent: we prove that indistinguishability against chosen-ciphertext attacks (IND-CCA) is in fact polynomially equivalent to (yet "slightly" weaker than) securely realizing the ideal functionality F_PKE in the general modeling of cryptographic protocols of [http://eprint.iacr.org/2000/067]. This disproves in particular the claim that security in the sense of IND-CCA strictly implies security in the sense of realizing F_PKE (see [http://eprint.iacr.org/2000/067]). Moreover, we give concrete reductions among such security notions and show that these relations hold for both uniform and non-uniform adversarial entities.

We present a new identity based scheme based on pairings over elliptic curves. It combines the functionalities of signature and encryption and is provably secure in the random oracle model. We compare it with Malone-Lee's one from security and efficiency points of view. We give a formal proof of semantical security under the Decisional Bilinear Diffie-Hellman assumption for this new scheme and we show how to devise other provably secure schemes that produce even shorter ciphertexts.

On January 8th 2003, Eric Filiol published on the eprint a paper (eprint.iacr.org/2003/003/) in which he claims that AES can be broken by a very simple and very fast ciphertext-only attack. If such an attack existed, it would be the biggest discovery in code-breaking since some 10 or more years. Unfortunately the result is very hard to believe. In this paper we present the results of computer simulations done by several independent people, with independently written code. Nobody has confirmed a single anomaly in AES, even for much weaker versions of the bias claimed by the author. We also studied the source code provided by the author to realize that the first version had various issues and bugs, and the latest version still does not confirm the claimed result on AES.

We propose a new cryptographically protected multi-round auction mechanism for online auctions. This auction mechanism is designed to provide (in this order) security, cognitive convenience, and round-effectiveness. One can vary internal parameters of the mechanism to trade off bid privacy and cognitive costs, or cognitive costs and the number of rounds. We are aware of no previous work that interleaves cryptography explicitly with the mechanism design.

In this paper we extend the conditional correlation attack ([LCPP96]) against the nonlinear filter generator (NLFG) by introducing new conditions and generalisations and present two known-plaintext attacks, called hybrid correlation attack and concentration attack. The NLFG is a well known LFSR-based keystream generator which could be used as a basic building block in a synchronous stream cipher system. Both new attacks use methods from the conditional correlation attack and additional from fast correlation attacks to derive the unknown initial state of the LFSR of the NLFG. The basic principle of iteratively cumulating and updating conditional correlations for the NLFG was proposed in [Loh01] and for general combiners with memory in [GBM02]. With the hybrid correlation attack it is possible to successfully attack the NLFG by applying a fast correlation attack, even if the filter function $$ of the NLFG is highly nonlinear, e.g. the normalised nonlinearity $$ is $$. The concentration attack maps all computed conditional correlations to $$ unknown LFSR bits, where $$ and $$ are parameters which can be chosen by the attacker, and $$ is the length of the LFSR of the NLFG. Even with low values of conditional correlations, it is possible to mount the hybrid correlation attack and the concentration attack successfully. This is not the case for the originally version of the conditional correlation attack ([LCPP96]) in a time lower than a full search over all possible initial states.

We propose the first polynomial time algorithm for the braid Diffie-Hellman conjugacy problem (DHCP) on which the braid key exchange scheme and the braid encryption scheme are based~\cite{KLCHKP01}. We show the proposed method solves the DHCP for the image of braids under the Lawrence-Krammer representation and the solutions play the equivalent role of the original key for the DHCP of braids. Given a braid index $$ and a canonical length $$, the complexity is about $$ bit operations, where $$ (Theoretically, it can be reduced to $$ using $$). Further, we show that the generalization into the decomposition problem causes only 8 times of the complexity.

In this paper, we extend the 2-party key exchange protocol on braid groups to the group key agreement protocol based on the hardness of Ko-Lee problem. We also provide authenticity to the group key agreement protocol.

An {\em $$-perfect hash family} is a set of functions $$ from a set $$ of cardinality $$ to a set $$ of cardinality $$ with the property that every $$-subset of $$ is injectively mapped into $$ by at least one of the functions $$. The paper shows that the maximum value $$ that $$ can take for fixed $$ and $$ has a leading term that is linear in $$ if and only if $$. Moreover, for any $$ and $$ such that $$, the paper shows how to calculate the coefficient of this linear leading term; this coefficient is explicitly calculated in some cases. As part of this process, new classes of good perfect hash families are constructed.

We proposed the first threshold GQ signature scheme. The scheme is unforgeable and robust against any adaptive adversary if the base GQ signature scheme is unforgeable under the chosen message attack and computing the discrete logarithm modulo a safe prime is hard. Our scheme achieve optimal resilience, that is, the adversary can corrupt up to a half of the players. As an extension of our work, we proposed a threshold forward-secure signature scheme, which is the threshold version of the most efficient forward-secure signature scheme up to now.

Bridging the gap between formal methods and cryptography has recently received a lot of interest, i.e., investigating to what extent proofs of cryptographic protocols made with abstracted cryptographic operations are valid for real implementations. However, a major goal has not been achieved yet: a soundness proof for an abstract crypto-library as needed for the cryptographic protocols typically proved with formal methods, e.g., authentication and key exchange protocols. Prior work that directly justifies the typical Dolev-Yao abstraction is restricted to passive adversaries and certain protocol environments. Prior work starting from the cryptographic side entirely hides the cryptographic objects, so that the operations are not composable: While secure channels or signing of application data is modeled, one cannot encrypt a signature or sign a key. We make the major step towards this goal: We specify an abstract crypto-library that allows composed operations, define a cryptographic realization, and prove that the abstraction is sound for arbitrary active attacks in arbitrary reactive scenarios. The library currently contains public-key encryption and signatures, nonces, lists, and application data. The proof is a novel combination of a probabilistic, imperfect bisimulation with cryptographic reductions and static information-flow analysis.

In this paper, we present a new stream cipher called Hiji-bij-bij (HBB). The basic design principle of HBB is to mix a linear and a nonlinear map. Our innovation is in the design of the linear and the nonlinear maps. The linear map is realised using two 256-bit maximal period 90/150 cellular automata. The nonlinear map is simple and consists of several alternating linear and nonlinear layers. We prove that the mixing achieved by the nonlinear map is complete and the maximum bias in any non-zero linear combination of the input and output bits of the nonlinear map is at most $$. We also identify a self-synchronizing mode ({\bf SS}) of operation for HBB. The performance of HBB is reasonably good in software and is expected to be very fast in hardware. To the best of our knowledge, a generic exhaustive search seems to be the only method of attacking the cipher.

In smartcard encryption and signature applications, randomized algorithms can be used to increase tamper resistance against attacks based on averaging data-dependent power or EMR variations. Recently, Oswald and Aigner described such an algorithm suitable for point multiplication in elliptic curve cryptography (ECC). With the assumption that an attacker can identify additions and doublings and distinguish them from each other during a single point multiplication, it is shown that the algorithm is insecure for repeated use of the same secret key without blinding of that key. This scotches hopes that the expense of such blinding might be avoided by using the algorithm unless the differences between point additions and doublings can be obscured successfully.

RC4 cipher is the most widely used stream cipher in software applications. It was designed by R. Rivest in 1987. In this paper we find the number of keys of the RC4 cipher generating initial permutations with the same cycle structure. We obtain that the distribution of initial permutations is not uniform.

Key authentication is very important in secret communications and data security. Recently, Lee, Hwang and Li proposed a new public key authentication scheme for cryptosystems with a trusty server. However, in this paper, we will show that Lee-Hwang-Li's key authentication scheme is not secure, from the obtained public information, any one can get the private key of the user. And then, we propose an improved scheme. We conclude that our new key authentication scheme not only resolves the problems appeared but also is secure.

We explain how a differential fault analysis (DFA) works on AES 128, 192 or 256 bits.

We obtain a {\em finite} binary tree algorithm to extend the domain of a UOWHF. The associated key length expansion is only a constant number of bits more than the minimum possible. Our finite binary tree algorithm is a practical parallel algorithm to securely extend the domain of a UOWHF. Also the speed-up obtained by our algorithm is approximately proportional to the number of processors.

In this paper we describe two different DFA attacks on the AES. The first one uses a fault model that induces a fault on only one bit of an intermediate result, hence allowing us to obtain the key by using 50 faulty ciphertexts for an AES-128. The second attack uses a more realistic fault model: we assume that we may induce a fault on a whole byte. For an AES-128, this second attack provides the key by using less than 250 faulty ciphertexts. Moreover, this attack has been successfully put into practice on a smart card.

We present a practical protocol that allows two players to negotiate price over the Internet in a deniable way so that a player $$ can prevent another player $$ from showing this offer $$ to a third party $$ in order to elicit a better offer while player $$ should be sure that this offer $$ generated by $$, but should $$ be unclear whether $$ is generated by $$ or $$ itself, even $$ and $$ fully cooperated. Our protocol is a standard browser-server model and uses a trusted third party, but only in a very limited fashion: the trusted third party is only needed in the cases where one player attempts to cheat or simply crashes, therefore, in the vast of majority transactions, the third party is not to be involved at all. In addition, Our price negotiable transaction system enjoys the following properties: \begin{description} \item[(1)]It works in an asynchronous communication model. \item[(2)]It is inter-operated with existing or proposed scheme for electronics voting system; \item[(3)]The two players need not sacrifice their privacy in making use of the trusted third party; \item[(4)]The deniable property can be proved secure in the random oracle paradigm, while the matching protocol can be proved secure in the standard intractable assumption. \end{description}

We use a general treatment of both information-theoretic and cryptographic settings for Multi-Party Computation (MPC), based on the underlying linear secret sharing scheme. Our goal is to study the Monotone Span Program (MSP), which is the result of local multiplication of shares distributed by two given MSPs as well as the access structure that this resulting MSP computes. First, we expand the construction proposed by Cramer et~al. multiplying two different general access structures and we prove some properties of the resulting MSP $$. Next we expand the definition of multiplicative MSPs and we prove that when one uses dual MSPs only all players together can compute the product, i.e., the construction proposed by Cramer et~al. gives only multiplicative MPC. Third, we propose a solution for the strongly multiplicative MPC (in presence of adversary). The knowledge of the resulting MSP and the access structure it computes allows us to build an analog of the algebraic simplification protocol of Gennaro et~al. We show how to achieve in the computational model MPC secure against adaptive adversary in the zero-error case, through the application of homomorphic commitments. There is an open problem how efficiently we can determine $$ the access structure of the resulting MSP $$. This open problem reflects negatively on the efficiency of the proposed solution.

In threshold cryptography the goal is to distribute the computation of basic cryptographic primitives across a number of nodes in order to relax trust assumptions on individual nodes, as well as to introduce a level of fault-tolerance against node compromise. Most threshold cryptography has previously looked at the distribution of public key primitives, particularly threshold signatures and threshold decryption mechanisms. In this paper we look at the application of threshold cryptography to symmetric primitives, and in particular the encryption or decryption of a symmetric key block cipher. We comment on some previous work in this area and then propose a model for shared encryption / decryption of a block cipher. We will present several approaches to enable such systems and will compare them.

This paper proposes ID-based tripartite authenticated key agreement protocols. The authenticated three party key agreement protocols from pairings [15], and the ID-based two party authenticated key agreement protocol [13] are studied. These two protocols are taken as the basis for designing three new ID-based tripartite authenticated key agreement protocols. The security properties of all these protocols are studied listing out the possible attacks on them. Further, these protocols are extended to provide key confirmation.

This paper presents a new ``operational'' cryptanalysis of block ciphers based on the use of a well-known error-correcting code: the repetition codes. We demonstrate how to describe a block cipher with such a code before explaining how to design a new ciphertext only cryptanalysis of these cryptosystems on the assumption that plaintext belongs to a particular class. This new cryptanalysis may succeed for any block cipher and thus is likely to question the security of those cryptosystems for encryption. We then apply this cryptanalysis to the 128-bit key AES. Our results have been experimentallly confirmed with 100 {\bf effective} cryptanalysis. Our attack enables to recover two information bits of the secret key with only $$ ciphertext blocks and a complexity of $$ with a success probability of 0.68.

A property of the NTRU public-key cryptosystem is that it does not provide perfect decryption. That is, given an instance of the cryptosystem, there exist ciphertexts which can be validly created using the public key but which can't be decrypted using the private key. The valid ciphertexts which an NTRU secret key will not correctly decipher determine, up to a cyclic shift, the secret key. In this paper we present attacks based on this property against the NTRU primitive and many of the suggested NTRU padding schemes. These attacks use an oracle for determining if valid ciphertexts can be correctly deciphered, and recover the user's secret key. The attacks are quite practical. For example, the attack against the NTRU-REACT padding scheme proposed at CRYPTO 2002 with the $$ parameter set requires on average fewer than 30,000 oracle calls and can be performed on a PC in a few minutes. As the traditional definition of a public-key encryption scheme requires perfect decryption, we also define a new type of encryption scheme which encompasses both NTRU and an attack model for the attacks presented against it.

At the recent AES Modes of Operation Conference, several modes of operation were proposed for using a block cipher to provide both confidentiality and authentication. These modes require only a little more work than the cost of encryption alone, and come with proofs of security. However, these modes require the entire message to be sent in encrypted form. This can cause problems in situations where some of the message neeeds to be sent in plaintext while still being authenticated. This paper describes a simple variation that allows any choice of message blocks to be sent in plaintext form rather than in encrypted form. This mode, Partial Encryption with Message Integrity (PEMI), is shown to be secure for message integrity and message secrecy.

An (n,k) pair is a pair of binary nxm matrices (A,B), such that the weight of the modulo-two sum of any i rows, 1\leq i \leq k, from A or B is equal to a_i or b_i, respectively, and moreover, a_i=b_i, for 1\leq i < k, while a_k \neq b_k. In this note we first show how to construct an (n,k) Threshold Visual Secret Sharing Scheme from an (n,k) pair. Then, we explicitly construct an (n,k)-pair for all n and k with 1 \leq k <n.

In this paper, we present a new visual crypto system based on the polarisation of light and investigate the existence and structure of the associated threshold visual secret sharing schemes. It is shown that very efficient $$ schemes exist and that $$ schemes are equivalent to binary codes. The existence of $$ schemes is shown in general by two explicit constructions. Finally, bounds on the physical properties as contrast and resolution are derived.

Padró and Sáez introduced the concept of a $$-partite access structure for secret sharing, and gave a complete characterization of ideal bipartite structures. We derive a necessary condition for ideal tripartite structures, which we conjecture is necessary for all $$.

Password-based key exchange schemes are designed to provide entities communicating over a public network, and sharing a (short) password only, with a session key (e.g, the key is used for data integrity and/or confidentiality). The focus of the present paper is on the analysis of very efficient schemes that have been proposed to the IEEE P1363 Standard working group on password-based authenticated key-exchange methods, but for which actual security was an open problem. We analyze the AuthA key exchange scheme and give a complete proof of its security. Our analysis shows that the AuthA protocol and its multiple modes of operation are provably secure under the computational Diffie-Hellman intractability assumption, in both the random-oracle and the ideal-cipher models.

In this paper we propose an attack on the key stream generator underlying the encryption system $$ used in the Bluetooth specification. We show that the initial value can be recovered by solving a system of nonlinear equations of degree 4 over the finite field GF(2). This system of equations can be transformed by linearization into a system of linear equations with at most $$ unknowns. To our knowledge, this is the best attack on the key stream generator underlying the $$ yet.