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 $(n,n)$ schemes exist and that $(2,n)$ schemes are equivalent to binary codes. The existence of $(k,n)$ 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 $k$-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 $k$.

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 $E_0$ 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 $2^{24.056}$ unknowns. To our knowledge, this is the best attack on the key stream generator underlying the $\mbox{E}_0$ yet.

We define a new authentication tree in the symmetric key setting, which has the same computational time, storage and security parameters as the well known Merkle authentication tree, but which unlike the latter, allows for all the cryptographic operations required for an update to be performed in parallel. The cryptographic operations required for verification can also be parallelized. In particular, we show a provably secure scheme for incremental MAC with partial authentication secure against substitution and replay attacks, which on total data of size $2^n$ blocks, and given $n$ cryptographic engines, can compute incremental macs and perform individual block authentication with a critical path of only one cryptographic operation

In this paper, we introduce a bit-slice approach for auctions and present a more efficient circuit than the normal approach for the highest-price auction. Our circuit can be combined with any auction protocol based on general circuit evaluation. Especially, if we combine with the mix and match technique, then we can obtain a highest-price auction protocol which is at least seven times faster. A second-price auction protocol is also easily constructed from our circuit.

NTRU is an efficient public-key cryptosystem proposed by Hoffstein, Pipher, and Silverman. Assuming access to a decryption oracle, we show ways to recover the private key of NTRU systems that do not include a ciphertext validating procedure. The strongest of our methods will employ just a single call to the oracle, and in all cases, the number of calls needed will be small enough to be realistic.

Artin's braid groups currently provide a promising background for cryptographical applications, since the first cryptosystems using braids were introduced in \cite{SCY,AAF, AAG, KLC}. A variety of key agreement protocols based on braids have been described, but few authentication or signature schemes have been proposed so far. We introduce three authentication schemes based on braids, two of them being zero-knowledge interactive proofs of knowledge. Then we discuss their possible implementations, involving normal forms or an alternative braid algorithm, called handle reduction, which can achieve good efficiency under specific requirements.

Zero-knowledge proofs are proofs that are both convincing and yet yield nothing beyond the validity of the assertion being proven. Since their introduction about twenty years ago, zero-knowledge proofs have attracted a lot of attention and have, in turn, contributed to the development of other areas of cryptography and complexity theory. We survey the main definitions and results regarding zero-knowledge proofs. Specifically, we present the basic definitional approach and its variants, results regarding the power of zero-knowledge proofs as well as recent results regarding questions such as the composeability of zero-knowledge proofs and the use of the adversary's program within the proof of security (i.e., non-black-box simulation).

This paper proposes the Turing stream cipher. Turing offers up to 256-bit key strength, and is designed for extremely efficient software implementation. It combines an LFSR generator based on that of SOBER with a keyed mixing function reminiscent of a block cipher round. Aspects of the block mixer round have been derived from Rijndael, Twofish, tc24 and SAFER.

We investigate a number of issues related to identity based authenticated key agreement protocols using the Weil or Tate pairings. These issues include how to make protocols efficient; how to avoid key escrow by a Trust Authority (TA) who issues identity based private keys for users, and how to allow users to use different Trusted Authorities. We describe a few authenticated key agreement (AK) protocols and AK with key confirmation (AKC) protocols which are modified from Smart's AK protocol. We study the security of these protocols heuristically and using provable security methods. In addition, we prove that our AK protocol is immune to key compromise impersonation attacks, and we also show that our second protocol has the TA forward secrecy property (which we define to mean that the compromise of the TA's private key will not compromise previously established session keys). We also show that this TA forward secrecy property implies that the protocol has the perfect forward secrecy property.

We present extremely simple ways of embedding a backdoor in the key generation scheme of RSA. Three of our schemes generate two genuinely random primes $p$ and $q$ of a given size, to obtain their public product $n=pq$. However they generate private/public exponents pairs $(d,e)$ in such a way that appears very random while allowing the author of the scheme to easily factor $n$ given only the public information $(n,e)$. Our last scheme, similar to the PAP method of Young and Yung, but more secure, works for any public exponent $e$ such as $3,17,65537$ by revealing the factorization of $n$ in its own representation. This suggests that nobody should rely on RSA key generation schemes provided by a third party.

In this paper, we introduce a notion of Oblivious Keyword Search ($OKS$). Let $W$ be the set of possible keywords. In the commit phase, a database supplier $T$ commits $n$ data. In each transfer subphase, a user $U$ can choose a keyword $w \in W$ adaptively and find $Search(w)$ without revealing $w$ to $T$, where $Search(w)$ is the set of all data which includes $w$ as a keyword. We then show two efficient protocols such that the size of the commitments is only $(nB)$ regardless of the size of $W$, where $B$ is the size of each data. It is formally proved that $U$ learns nothing more and $T$ gains no information on the keywords which $U$ searched. We further present a more efficient adaptive $OT_k^n$ protocol than the previous one as an application of our first $OKS$ protocol.

Counting rational points on Jacobian varieties of hyperelliptic curves over finite fields is very important for constructing hyperelliptic curve cryptosystems (HCC), but known algorithms for general curves over given large prime fields need very long running times. In this article, we propose an extremely fast point counting algorithm for hyperelliptic curves of type $y^2=x^5+ax$ over given large prime fields $\Fp$, e.g. 80-bit fields. For these curves, we also determine the necessary condition to be suitable for HCC, that is, to satisfy that the order of the Jacobian group is of the form $l\cdot c$ where $l$ is a prime number greater than about $2^{160}$ and $c$ is a very small integer. We show some examples of suitable curves for HCC obtained by using our algorithm. We also treat curves of type $y^2=x^5+a$ where $a$ is not square in $\Fp$.

In this paper, we present One-key CBC MAC (OMAC) and prove its security for arbitrary length messages. OMAC takes only one key, $K$ ($k$ bits) of a block cipher $E$. Previously, XCBC requires three keys, $(k+2n)$ bits in total, and TMAC requires two keys, $(k+n)$ bits in total, where $n$ denotes the block length of $E$. The saving of the key length makes the security proof of OMAC substantially harder than those of XCBC and TMAC.

Given a positive integer $n$ and a point $P$ on an elliptic curve $E$, the computation of $nP$, that is, the result of adding $n$ times the point $P$ to itself, called the \emph{scalar multiplication}, is the central operation of elliptic curve cryptosystems. We present an algorithm that, using $p$ processors, can compute $nP$ in time $O(\log n+H(n)/p+\log p)$, where $H(n)$ is the Hamming weight of $n$. Furthermore, if this algorithm is applied to Koblitz curves, the running time can be reduced to $O(H(n)/p+\log p)$.

In ISC 2002, J. Zheng proposed a new public key cryptosystem whose security is based upon the algebraic problem of reducing a high degree matrix to its canonical form by similarity transformations. In this paper, we show that factoring a polynomial over a finite field can be used to break down Zheng's public key cryptosystem. The complexity of our attack is polynomial time. In other word, the underlying problem of Zheng's public key cryptosystem is not a ``hard'' problem.

Group signature is very important primitive in cryptography. A group signature scheme allows any group member to sign on behalf of the group in an anonymous and unlinkable fashion .In case of dispute, group manager can reveal the identity of the signer. Recently, S.Xia and J.You proposed a group signature scheme based on identity with strong separability in which the revocation manager can work without the involvement of the membership manger. In this paper, we analyze the security of Xia-You group signature and indicate that two or more group members can collude to construct a valid signature and any group member can forge a valid membership certification.

In this paper, we give the theoretical analysis of Chi-square attack proposed by Knudsen and Meier on the RC6 block cipher. To this end, we propose the novel method of security evaluation against Chi-square attack precisely including key dependency by introducing a technique ``Transition Matrix Computing.'' On the other hand, the way of security evaluation against Chi-square attack has not been known except the computer experiment. We should note that it is the first results the way of security evaluation against Chi-square attack is shown theoretically. Using this method, we can obtain the ``weakest keys'' against the attack.

An aggregate signature scheme is a digital signature that supports aggregation: Given $n$ signatures on $n$ distinct messages from $n$ distinct users, it is possible to aggregate all these signatures into a single short signature. This single signature (and the $n$ original messages) will convince the verifier that the $n$ users did indeed sign the $n$ original messages (i.e., user $i$ signed message $M_i$ for $i=1,\ldots,n$). In this paper we introduce the concept of an aggregate signature scheme, present security models for such signatures, and give several applications for aggregate signatures. We construct an efficient aggregate signature from a recent short signature scheme based on bilinear maps due to Boneh, Lynn, and Shacham. Aggregate signatures are useful for reducing the size of certificate chains (by aggregating all signatures in the chain) and for reducing message size in secure routing protocols such as SBGP. We also show that aggregate signatures give rise to verifiably encrypted signatures. Such signatures enable the verifier to test that a given ciphertext $C$ is the encryption of a signature on a given message $M$. Verifiably encrypted signatures are used in contract-signing protocols. Finally, we show that similar ideas can be used to extend the short signature scheme to give simple ring signatures.

A generic or KEM-DEM hybrid construction is a formal method of combining a asymmetric and symmetric encryption techniques to give an efficient, provably secure public-key encryption scheme. This method combines an asymmetric KEM with a symmetric DEM, and each of these components must satisfy their own security conditions. In this paper we describe generic constructions for provably secure KEMs based on lower level primitives such as one-way trapdoor functions and weak key-agreement protocols.

Group signature schemes enable unlinkably anonymous authentication, in the same fashion that digital signatures provide the basis for strong authentication protocols. This paper introduces the first group signature scheme with constant-size parameters that does not require any group member, including group managers, to know trapdoor secrets. This novel type of group signature scheme allows public parameters to be shared among organizations, and are useful when several distinct groups must interact and exchange information about individuals while protecting their privacy.

Many variants of the ElGamal signature scheme have been proposed. The most famous is the DSA standard. If computing discrete logarithms is hard, then some of these schemes have been proven secure in an idealized model, either the random oracle or the generic group. We propose a generic but simple presentation of signature schemes with security based on the discrete logarithm. We show how they can be proven secure in idealized model, under which conditions. We conclude that none of the previously proposed digital signature schemes has optimal properties and we propose a scheme named PECDSA.

A large number of stream cipher were proposed and implemented over the last twenty years. In 1987 Rivest designed the RC4 stream cipher, which was based on a different and more software friendly paradigm. It was integrated into Microsoft Windows, Lotus Notes, Apple AOCE, Oracle Secure SQL, and many other applications, and has thus become the most widely used a software-based stream cipher. In this paper we describe some properties of an output sequence of RC4. It is proved that the distribution of first, second output values of RC4 and digraphs are not uniform, which makes RC4 trivial to distinguish between short outputs of RC4 and random strings by analyzing their first, or second output values of RC4 or digraphs.

A recent trend in message authentication is the use of a randomizing parameter, such that the authentication tag is based not only on the message and the key, but a public nonce which is changed for every authenticated message. This generally affords a better security proof. However, several new classes of attacks are made available by these techniques. We examine these attacks, and apply some of them to RMAC, a recently published MAC mechanism.

We expand on the idea, proposed by Kelsey et al, of cache memory being used as a side-channel which leaks information during the run of a cryptographic algorithm. By using this side-channel, an attacker may be able to reveal or narrow the possible values of secret information held on the target device. We describe an attack which encrypts $2^{10}$ chosen plaintexts on the target processor in order to collect cache profiles and then performs around $2^{32}$ computational steps to recover the key. As well as describing and simulating the theoretical attack, we discuss how hardware and algorithmic alterations can be used to defend against such techniques.

We propose a new digital signature scheme based on a non-commutative group where the conjugacy search problem is hard and the conjugacy decision problem is feasible. We implement our signature scheme in the braid groups and prove that an existential forgery of the implementation under no message attack gives a solution to a variation of conjugacy search problem. Then we discuss performance of our scheme under suggested parameters.

Group signature and blind signature are very important primitives in cryptography. A group signature scheme allows a group member to sign messages anonymously on behalf of the group and a blind signature scheme can ensure anonymity of the sender of a message. Recently, S. Xia and J. You proposed a group signature scheme with strong separability in which the revocation manager can work without the involvement of the membership manager and J.J-R. Chen and A.P. Chen proposed a blind signature scheme based on dual complexities (which combines factorization and discrete logarithm problem). In this paper, we give a universal forgery attack on Xia-You's group signature scheme which any one (not necessarily a group member) can produce a valid group signature on an arbitrary message, and it is untraceable by the group revocation manager. For Chen-Chen's blind signature scheme, we show that it could not meet the untraceability property of a blind signature, $i.e.$, it could not ensure anonymity of the user.

A. Joux presented a one round protocol for tripartitie key agreement and Al-Riyami et.al. developed a number of tripartitie, one round, authenticated protocols related to MTI and MQV protocols. Recently, Boneh and Silverleg studied multilinear forms, which provides a one round multi-party key agreement protocol. In this paper, we propose $(n+1)$ types of one round authenticated multi-party key agreement protocols from multilinear forms based on the application of MTI and MQV protocols.

We introduce a model for electronic election schemes that involves a more powerful adversary than in previous work. In particular, we allow the adversary to demand of coerced voters that they vote in a particular manner, abstain from voting, or even disclose their secret keys. We define a scheme to be _coercion-resistant_ if it is infeasible for the adversary to determine whether a coerced voter complies with the demands. A first contribution of this paper is to describe and characterize a new and strengthened adversary for coercion in elections. (In doing so, we additionally present what we believe to be the first formal security definitions for electronic elections of _any_ type.) A second contribution is to demonstrate a protocol that is secure against this adversary. While it is clear that a strengthening of attack models is of theoretical relevance, it is important to note that our results lie close to practicality. This is true both in that we model real-life threats (such as vote-buying and vote-cancelling), and in that our proposed protocol combines a fair degree of efficiency with an unusual lack of structural complexity. Furthermore, while previous schemes have required use of an untappable channel, ours only carries the much more practical requirement of an anonymous channel.

Authenticated Key exchange algorithms tend to be either token-based or password based. Token-based schemes are often based on expensive (and irreplaceable) smart-card tokens, while password-only schemes require that a unique password is shared with every correspondent. The magnetic strip swipe card and associated PIN number is a familiar and convenient format that motivates a combined approach. Finally we suggest an extension of the scheme for use in a client-server scenario.

Recently new protocols have been proposed in IETF for protecting remote client authentication protocols by running them within a secure tunnel. Examples of such protocols are PIC, PEAP and EAP-TTLS. One goal of these new protocols is to enable the migration from legacy client authentication protocols to more secure protocols, e.g., from plain EAP type to, say, PEAP. In the new drafts, the security of the subsequent session credentials are based only on keys derived during the unilateral authentication where the network server is authenticated to the client. Client authentication is mentioned as an option in PEAP and EAP-TTLS, but is not mandated. Naturally, the PIC protocol does not even offer this option, because the goal of PIC is to obtain credentials that can be used for client authentication. In addition to running the authentication protocols within such tunnel it should also be possible to use them in legacy mode without any tunnelling so as to leverage the legacy advantages such as widespread use. In this paper we show that in practical situations, such a mixed mode usage opens up the possibility to run a man-in-the-middle attack for impersonating the legitimate client. For those well-designed client authentication protocols that already have a sufficient level of security, the use of tunnelling in the proposed form is a step backwards because they introduce a new vulnerability. The problem is due to the fact that the legacy client authentication protocol is not aware if it is run in protected or unprotected mode. We propose to solve the discovered problem by using a cryptographic binding between the client authentication protocol and the protection protocol.

We consider the problem of constructing randomness extractors which are {\em locally computable}, i.e. only read a small number of bits from their input. As recently shown by Lu (CRYPTO `02), locally computable extractors directly yield secure private-key cryptosystems in Maurer's bounded storage model (J. Cryptology, 1992). In this note, we observe that a fundamental lemma of Nisan and Zuckerman (J. Computer and System Sciences, 1996) yields a general technique for constructing locally computable extractors. Specifically, we obtain a locally computable extractor by combining any extractor with any randomness-efficient (averaging) sampler. Plugging in known extractor and sampler constructions, we obtain locally computable extractors, and hence cryptosystems in the bounded storage model, whose parameters improve upon previous constructions and come quite close to the lower bounds. Along the way, we also present a refinement of the Nisan--Zuckerman lemma, showing that random sampling bits from a weak random source preserves the min-entropy rate up to an arbitrarily small additive loss (whereas the original lemma loses a logarithmic factor).

This paper presents a variant of the new public key encryption of Cramer and Shoup based on Paillier's decision composite residuosity assumption, along with an efficient protocol for verifiable encryption of discrete logarithms. This is the first verifiable encryption system that provides chosen ciphertext security and avoids inefficient cut-and-choose proofs. This has numerous applications, including fair exchange and key escrow. We also present efficient protocols for verifiable decryption, which has applications to, e.g., confirmer signatures. The latter protocols build on a new protocol for proving whether or not two discrete logarithms are equal that is of independent interest. Prior such protocols were either inefficient or not zero-knowledge.

This paper examines mechanical lock security from the perspective of computer science and cryptology. We focus on new and practical attacks for amplifying rights in mechanical pin tumbler locks. Given access to a single master-keyed lock and its associated key, a procedure is given that allows discovery and creation of a working master key for the system. No special skill or equipment, beyond a small number of blank keys and a metal file, is required, and the attacker need engage in no suspicious behavior at the lock's location. Countermeasures are also described that may provide limited protection under certain circumstances. We conclude with directions for research in this area and the suggestion that mechanical locks are worthy objects for study and scrutiny.

In [JJV02] Jaulmes, Joux, and Valette propose a new randomized message authentication scheme, called RMAC, which NIST is currently in the process of standardizing [NIS02]. In this work we present several attacks against RMAC. The attacks are based on a new protocol-level related-key attack against RMAC and can be considered variants of Biham's key-collision attack [Bih02]. These attacks provide insights into the RMAC design. We believe that the protocol-level related-key attack is of independent interest.

This paper is the full book of the 240 dual ciphers of Rijndael, in which only the constants differ from Rijndael. See: ``In How Many Ways Can You Write Rijndael?'', http://eprint.iacr.org.

In this paper we ask the question what happens if we replace all the constants in Rijndael, including the replacement of the irreducible polynomial, the coefficients of the MixColumn operation, the affine transformation in the S box, etc. We show that such replacements can create new dual ciphers, which are equivalent to the original in all aspects. We present several such dual ciphers of Rijndael, such as the square of Rijndael, and dual ciphers with the irreducible polynomial replaced by primitive polynomials. We also describe another family of dual ciphers consisting of the logarithms of Rijndael. We then discuss self-dual ciphers, and extend our results to other ciphers.

In non-repudiation services where digital signatures usually serve as irrefutable cryptographic evidence for dispute resolution, trusted time-stamping and certificate revocation services, although very costly in practice, must be available, to prevent big loss due to compromising of the signing key. In [IR02], a new concept called intrusion-resilient signature} was proposed to get rid of trusted time-stamping and certificate revocation services and a concrete scheme was presented. In this paper, we put forward a new scheme that can achieve the same effect in a much more efficient way. In our scheme, forward-secure signature serves as a building block that enables signature validation without trusted time-stamping, and a one-way hash chain is employed to control the validity of public-key certificates without the CA's involvement for certificate revocation. We adopt a model similar to the intrusion-resilient signature in [IR02], where time is divided into predefined short periods and a user has two modules, signer and home base. The signer generates forward-secure signatures on his own while the home base manages the validity of the signer's public-key certificate with a one-way hash chain. The signature verifier can check the validity of signatures without retrieving the certificate revocation information from the CA. Our scheme is more robust in the sense that loss of synchronization between the signer and the home base could be recovered in the next time period while it is unrecoverable in [IR02]. To facilitate the implementation of our signature validation scheme, we further present a new forward-secure signature scheme which is more efficient than all of the existing forward-secure signature schemes.

The Weil and Tate pairings are a popular new gadget in cryptography and have found many applications, including identity-based cryptography. In particular, the pairings have been used for key exchange protocols. This paper studies the bit security of keys obtained using protocols based on pairings (that is, we show that obtaining certain bits of the common key is as hard as computing the entire key). These results are valuable as they give insight into how many ``hard-core'' bits can be obtained from key exchange using pairings.

We describe and analyze new combinations of multi-exponentiation algorithms with representations of the exponents. We deal mainly but not exclusively with the case where the inversion of group elements is fast: These methods are most attractive with exponents in the range from 80 to 256 bits, and can also be used for computing single exponentiations in groups which admit an automorphism satisfying a monic equation of small degree over the integers. The choice of suitable exponent representations allows us to match or improve the running time of the best multi-exponentiation techniques in the aforementioned range, while keeping the memory requirements as small as possible. Hence some of the methods presented here are particularly attractive for deployment in memory constrained environments such as smart cards. By construction, such methods provide good resistance against side channel attacks. We also describe some applications of these algorithms.

This paper is the third in a line considering the arithmetic in the ideal class group of hyperelliptic genus two curves. The previous two papers deal with generalizations of affine and projective coordinates. Now we investigate how one can obtain inversion free formulae that are faster than projective by considering weighted coordinates. To that end we make an extensive case study to deal with different characteristic, equation of the curve, space requirement and situation of appliance.

This paper presents an analysis of the PES cipher in a similar setting as done by Daemen et al. at Crypto'93 for IDEA. The following results were obtained for 8.5 round PES: a linear weak-key class of size $2^{48}$; two distinct differential weak-key classes of size $2^{41}$; two differential-linear weak-key classes of size $2^{62}$. For 17-round PES (double-PES): a linear weak-key class of size $2^7$, and a differential weak-key class of size $2^7$ were found. Daemen suggested a modified key schedule for IDEA in order to avoid weak keys. We found a differential weak-key class of size $2^{83}$ for 2.5-round IDEA under his redesigned key schedule, and differential-linear relations for 3.5-round IDEA.

We describe a credential system similar to the electronic cash system described by Chaum, Fiat and Naor. Our system uses bit commitments to create selective disclosure credentials which limit what portions of a credential the holder must reveal. We show how credentials from separate issuers can be linked to the same person in order to prevent users from pooling credentials to obtain services no one user could obtain alone. We also describe how to use a blinding technique described by Laurie which may not violate the patents on blind signatures.

Undeniable signature is an intriguing concept introduced by Chaum and Antwerpen at Crypto'89. In 1999, Lee and Hwang presented two group-oriented undeniable signature schemes with a trusted center. Their schemes are natural generalizations of Chaum's zero-knowledge undeniable signature scheme proposed in 1990. However, we find that the Lee-Hwang schemes are insecure. In this paper, we demonstrate five attacks on their schemes: four of them are universal forgery, in which one dishonest member (maybe collude with a verifier) can get a valid signature on any chosen massage, and another attack allows a dishonest member to prevent honest members from generating valid signatures but his cheating behavior is undetected. We also suggest heuristic improvements to overcome some of the problems involved in these attacks.

Recently Filiol proposed to test cryptographic algorithms by making statistics on the number of low degree terms in the boolean functions. The paper has been published on eprint on 23th of July 2002. In this paper we reproduce some of Filiol's simulations. We did not confirm his results: our results suggest that DES, AES, and major hash functions have no significative bias and their output bits behave just like random boolean functions.

We describe a block-cipher mode of operation, EMD, that builds a strong pseudorandom permutation (PRP) on $nm$ bits ($m\ge2$) out of a strong PRP on $n$ bits (i.e., a block cipher). The constructed PRP is also tweaked (in the sense of [LRW02]): to determine the $nm$-bit ciphertext block $C=\E_K^T(P)$ one provides, besides the key $K$ and the $nm$-bit plaintext block $P$, an $n$-bit tweak $T$. The mode uses $2m$ block-cipher calls and no other complex or computationally expensive steps (such as universal hashing). Encryption and decryption are identical except that encryption uses the forward direction of the underlying block cipher and decryption uses the backwards direction. We suggest that EMD provides an attractive solution to the disk-sector encryption problem, where one wants to encipher the contents of an $nm$-bit disk sector in a way that depends on the sector index and is secure against chosen-plaintext/chosen-ciphertext attack.

We investigate formulae to double and add in the ideal class group of a hyperelliptic genus 2 curve avoiding inversions. To that aim we introduce a further coordinate in the representation of a class in which we collect the common denominator of the usual 4 coordinates. The analysis shows that this is practical and advantageous whenever inversions are expensive compared to multiplications like for example on smart cards.

We show that Shoup and Rubin's protocols are not secure against the BBF attack proposed by Bauer, Berson, and Feiertag, and propose an amendment. Furthermore, our results indicate that both Bellare and Rogaway's security and Paulson's security do not imply the security against the BBF attack.

In this paper we present the first lattice attack on an authenticated key agreement protocol, which does not use a digital signature algorithm to produce the authentication. We present a two stage attack on MQV in which one party may recover the other party's static private key from partial knowledge of the nonces from several runs of the protocol. The first stage reduces the attack to a hidden number problem which is partially solved by considering a closest vector problem and using Babai's algorithm. This stage is closely related to the attack of Nguyen and Shparlinski on DSA but is complicated by a non-uniform distribution of multipliers. The second stage recovers the rest of the key using the baby-step/giant-step algorithm or Pollard's Lambda algorithm and runs in time $O(q^{1/4})$. The attack has been proven to work with high probability and validated experimentally. We have thus reduced the security from $O(q^{1/2})$ down to $O(q^{1/4})$ when partial knowledge of the nonces is given.

In this paper, we show that all the coordinate functions of the Advanced Encryption Standard (AES) round function are equivalent under an affi ne transformation of the input to the round function. In other words, let $f_i$ and $f_j$ be any two distinct output coordinates of the AES round function, then there exists a nonsingular matrix $A_{ji}$ over $GF(2)$ such that $f_j(A_{ji} x) + b_{ji}= f_i(x), b_{ji} \in GF(2)$. We also show that such linear relations will always exist if the Rijndael s-b ox is replaced by any bijective monomial over $GF(2^8)$. %We also show that replacing the s-box by any bijective monomial will not change this property.

At EUROCRYPT '96 J. Patarin introduced the "Isomorphisms of Polynomials (IP)" problem as a basis of authentication and signature schemes. We describe an attack on the secret key of "IP with one secret" and demonstrate its efficiency through examples with realistic parameter sizes. To prevent our attack, additional restrictions on the suggested parameters should be imposed.

We demonstrate that the existence of distinguishing attacks against stream ciphers is unrelated to their security in practical use, and in particular that the amount of data required to perform a distinguishing attack is unrelated to the key length of the cipher. The implication for the NESSIE Project is that no submitted symmetric cipher would be accepted under the unpublished rules for distinguishing attacks, not even the block ciphers in Counter Mode or Output Feedback Mode.

Verifiable secret sharing schemes (VSS) are secret sharing schemes (SSS) dealing with possible cheating by participants. In this paper we use the VSS proposed by Cramer, Damgard and Maurer \cite{CDM99,CDM00,Cra00}. They introduced a purely linear algebraic method to transform monotone span program (MSP) based secret sharing schemes into VSS. In fact, the monotone span program model of Karchmer and Wigderson \cite{KW93} deals with arbitrary monotone access structures and not just threshold ones. Stinson and Wei \cite{SW99} proposed a proactive SSS based on threshold (polynomial) VSS. The purpose of this paper is to build unconditionally secure proactive SSS over any access structure, as long as it admits a linear secret sharing scheme (LSSS).

We show how to securely realize any two-party and multi-party functionality in a {\em universally composable} way, regardless of the number of corrupted participants. That is, we consider an asynchronous multi-party network with open communication and an adversary that can adaptively corrupt as many parties as it wishes. In this setting, our protocols allow any subset of the parties (with pairs of parties being a special case) to securely realize any desired functionality of their local inputs, and be guaranteed that security is preserved regardless of the activity in the rest of the network. This implies that security is preserved under concurrent composition of an unbounded number of protocol executions, it implies non-malleability with respect to arbitrary protocols, and more. Our constructions are in the common reference string model and rely on standard intractability assumptions.

Wagner and Magyarik outlined a general construction for public key cryptosystems based on the hardness of the word problem for finitely presented groups. At the same time, they gave a specific example of such a system. We prove that their approach is vulnerable to so-called reaction attacks, namely, it is possible to retrieve the private key just by watching the performance of a legitimate recipient.

Quartz is a signature scheme based on an HFEv- trapdoor function published at Eurocrypt 1996. In this paper we study "inversion" attacks for Quartz, i.e. attacks that solve the system of multivariate equations used in Quartz. We do not cover some special attacks that forge signatures without inversion. We are interested in methods to invert the HFEv- trapdoor function or at least to distinguish it from a random system of the same size. There are 4 types of attacks known on HFE: Shamir-Kipnis, Shamir-Kipnis-Courtois, Courtois, and attacks related to Gröbner bases such as the F5/2 attack by Jean Charles Faugère. No attack has been published so far on HFEv- and it was believed to be more secure than HFE. In this paper we show that even modified HFE systems can be successfully attacked. It seems that the complexity of the attack increases by at least a factor of $q^{tot}$ with $tot$ being the total number of perturbations in HFE. From this and all the other known attacks we will estimate what is the complexity of the best "inversion" attack for Quartz.

Informally, steganography is the process of sending a secret message from Alice to Bob in such a way that an eavesdropper (who listens to all communications) cannot even tell that a secret message is being sent. In this work, we initiate the study of steganography from a complexity-theoretic point of view. We introduce definitions based on computational indistinguishability and we prove that the existence of one-way functions implies the existence of secure steganographic protocols. NOTE: An extended abstract of this paper appeared in CRYPTO 2002. Here we present a full version, including a correction to a small error in Construction 1.

We propose a practical non-interactive key distribution protocol based on pairings and define a notion of security for such a scheme. We prove the security of the system in this setting under the GDBH assumption, and present some possible realisations using Weil or Tate pairings on supersingular and ordinary elliptic curves.

Cryptographic schemes are often designed as a combination of multiple component cryptographic modules. Such a combiner design is {\em robust} for a (security) specification if it meets the specification, provided that a sufficient subset of the components meet their specifications. A folklore combiner for encryption is {\em cascade}, i.e. $c={\cal E}''_{e''}({\cal E}'_{e'}(m))$. We show that cascade is a robust combiner for cryptosystems, under three important indistinguishability specifications: chosen plaintext attack (IND-CPA), non-adaptive chosen ciphertext attack (IND-CCA1), and replayable chosen ciphertext attack (IND-rCCA). We also show that cascade is not robust for the important specifications adaptive CCA (IND-CCA2) and generalized CCA (IND-gCCA). The IND-rCCA and IND-gCCA specifications are closely related, and this is an interesting difference between them. All specifications are defined within. We also analyze few other basic and folklore combiners. In particular, we show that the following are robust combiners: the {\em parallel combiner} $f(x)=f''(x)||f'(x)$ for one-way functions , the {\em XOR-Input combiner} $c=\left({\cal E}''_{e''}(m\oplus r),{\cal E}'_{e'}(r)\right)$ for cryptosystems, and the {\em copy combiner} $f_{k'',k'}(m)=f''_{k''}(m)||f'_{k'}(m)$ for integrity tasks such as Message Authentication Codes (MAC) and signature schemes. Cascade is also robust for the hiding property of commitment schemes, and the copy combiner is robust for the binding property, but neither is a robust combiner for both properties. We present (new) robust combiners for commitment schemes; these new combiners can be viewed as a composition of the cascade and the copy combiners. Our combiners are simple, efficient and practical.

Verifiable secret sharing is an important primitive in distributed cryptography. With the growing interest in the deployment of threshold cryptosystems in practice, the traditional assumption of a synchronous network has to be reconsidered and generalized to an asynchronous model. This paper proposes the first \emph{practical} verifiable secret sharing protocol for asynchronous networks. The protocol creates a discrete logarithm-based sharing and uses only a quadratic number of messages in the number of participating servers. It yields the first asynchronous Byzantine agreement protocol in the standard model whose efficiency makes it suitable for use in practice. Proactive cryptosystems are another important application of verifiable secret sharing. The second part of this paper introduces proactive cryptosystems in asynchronous networks and presents an efficient protocol for refreshing the shares of a secret key for discrete logarithm-based sharings.

We give the first simple and efficient construction of {\em verifiable random functions} (VRFs). VRFs, introduced by Micali et al. [MRV99], combine the properties of regular pseudorandom functions (PRFs) [GGM86] (i.e., indistinguishability from a random function) and digital signatures [GMR88] (i.e., one can provide an unforgeable proof that the VRF\ value is correctly computed). The efficiency of our VRF construction is only slightly worse than that of a regular PRF construction of Naor and Reingold [NR97]. In contrast to ours, the previous VRF constructions [MRV99,Lys02] all involved an expensive generic transformation from verifiable unpredictable functions (VUFs), while our construction is simple and direct. We also provide the first construction of {\em distributed} VRFs. Our construction is more efficient than the only known construction of distributed (non-verifiable) PRFs [Nie02], but has more applications than the latter. For example, it can be used to distributively implement the random oracle model in a {\em publicly verifiable} manner, which by itself has many applications (e.g., constructing threshold signature schemes). Our main construction is based on a new variant of decisional Diffie-Hellman (DDH) assumption on certain groups where the regular DDH assumption does {\em not} hold. We do not make any claims about the validity of our assumption (which we call {\em sum-free} DDH, or sf-DDH). However, this assumption seems to be plausible based on our {\em current} understanding of certain candidate elliptic and hyper-elliptic groups which were recently proposed for use in cryptography [JN01,Jou00]. We hope that the demonstrated power of our sf-DDH assumption will serve as a motivation for its closer study.

We show that any scheme to encrypt m blocks of size n bits while assuring message integrity, that apart from using m+k invocations of random functions (from n bits to n bits) and vn bits of randomness, is linear in (GF2)^n, must have k+v at least Omega(log m). This lower bound is proved in a very general model which rules out many promising linear modes of operations for encryption with message integrity. This lower bound is tight as linear schemes to encrypt m blocks while assuring message integrity by using only m+2+log m invocations are known. of random permutations.

We present a simple to implement and efficient pseudorandom generator based on the factoring assumption. It outputs more than pn/2 pseudorandom bits per p exponentiations, each with the same base and an exponent shorter than n/2 bits. Our generator is based on results by Hastad, Schrift and Shamir [HSS93], but unlike their generator and its improvement by Goldreich and Rosen [GR00], it does not use hashing or extractors, and is thus simpler and somewhat more efficient. In addition, we present a general technique that can be used to speed up pseudorandom generators based on iterating one-way permutations. We construct our generator by applying this technique to results of [HSS93]. We also show how the generator given by Gennaro [Gen00] can be simply derived from results of Patel and Sundaram [PS98] using our technique.

We prove in the random oracle model that OAEP++, which was proposed by us at the rump session of Asiacrypt 2000, can generate IND-CCA2 ciphers using deterministic OW-CPA cryptographic primitives. Note that OAEP++ differs from OAEP$^{++}$ proposed by Jonsson in \cite{Jon02}. While OAEP$^{++}$ requires a non-malleable block cipher, OAEP++ does not require such additional functions. The security reduction of OAEP++ is as tight as that of OAEP$^{++}$.

A new kind of attack on the non-repudiation property of digital signature schemes is presented. We introduce a notion of key-collisions, which may allow an attacker to claim that the message (presented to a judge) has been signed by someone else. We show how to compute key-collisions for the DSA and ECDSA signature schemes effectively. The main idea of these attacks has been inspired by the well-known notion of message-collisions, where an attacker claims that the signature presented at the court belongs to a different message. Both of these collision-based attacks significantly weaken the non-repudiation property of signature schemes. Moreover, they weaken the non-repudiation of protocols based on these schemes. It is shown that key-collision resistance of the (EC)DSA schemes requires the incorporation of a mechanism ensuring honest generation of (EC)DSA instances. The usage of such a mechanism shall be verifiable by an independent third party without revealing any secret information. We propose and discuss basic general countermeasures against key-collision attacks on the (EC)DSA schemes.

Achieving secure communications in networks has been one of the most important problems in information technology. Dolev, Dwork, Waarts, and Yung have studied secure message transmission in one-way or two-way channels. They only consider the case when all channels are two-way or all channels are one-way. Goldreich, Goldwasser, and Linial, Franklin and Yung, Franklin and Wright, and Wang and Desmedt have studied secure communication and secure computation in multi-recipient (multicast) models. In a ``multicast channel'' (such as Ethernet), one processor can send the same message---simultaneously and privately---to a fixed subset of processors. In this paper, we shall study necessary and sufficient conditions for achieving secure communications against active adversaries in mixed one-way and two-way channels. We also discuss multicast channels and neighbor network channels.

In this paper, we first show that many independent pseudorandom permutations over $\{0,1\}^n$ can be obtained from a single public random permutation and secret $n$ bits. We next prove that a slightly modified IAPM is secure even if the underlying block cipher $F$ is publicly accessible (as a blackbox). We derive a similar result for OCB mode, too. We finally prove that our security bound is tight within a constant factor.

The security of many cryptographic constructions relies on assumptions related to Discrete Logarithms (DL), e.g., the Diffie-Hellman, Square Exponent, Inverse Exponent or Representation Problem assumptions. In the concrete formalizations of these assumptions one has some degrees of freedom offered by parameters such as computational model, problem type (computational, decisional) or success probability of adversary. However, these parameters and their impact are often not properly considered or are simply overlooked in the existing literature. In this paper we identify parameters relevant to cryptographic applications and describe a formal framework for defining DL-related assumptions. This enables us to precisely and systematically classify these assumptions. In particular, we identify a parameter, termed granularity, which describes the underlying probability space in an assumption. Varying granularity we discover the following surprising result: We prove that two DL-related assumptions can be reduced to each other for medium granularity but we also show that they are provably not reducible with generic algorithms for high granularity. Further we show that reductions for medium granularity can achieve much better concrete security than equivalent high-granularity reductions.

A way for preventing SPA-like attacks on elliptic curve systems is to use the same formula for the doubling and the general addition of points on the curve. Various proposals have been made in this direction with different results. This paper re-investigates the Jacobi form suggested by Liardet and Smart (CHES 2001). Rather than considering the Jacobi form as the intersection of two quadrics, the addition law is directly derived from the underlying quartic. As a result, this leads to substantial memory savings and produces the fastest unified addition formula for curves of order a multiple of 2.

Skewed trees constitute a two-parameter family of recursively constructed trees. Recently, Willemson proved that suitably picked skewed trees are space-optimal for interval time-stamping. At the same time, Willemson proposed a practical but suboptimal algorithm for nonrecursive traversal of skewed trees. We describe an alternative, extremely efficient traversal algorithm for skewed trees. The new algorithm is surprisingly simple and arguably close to optimal in every imaginable sense. We provide a detailed analysis of the average-case storage (and communication) complexity of our algorithm, by using the Laplace's method for estimating the asymptotic behavior of integrals. Since the skewed trees can be seen as a natural generalization of Fibonacci trees, our results might also be interesting in other fields of computer science.

From a view point of cryptography, we define a new covering radius of Reed-Muller codes as the maximum distance between $t$-{\it resilient} functions and the $r$-th order Reed-Muller code $RM(r,n)$. We next derive its lower and upper bounds. We also present a table of numerical data of our bounds.

With positive applications of Weil pairing (Tate pairing) to cryptography, ID-based encryption schemes, digital signature schemes, blind signature scheme, two-party authenticated key agreement schemes, and tripartite key agreement scheme were proposed recently, all of them using bilinear pairing (Weil or Tate pairing). In this paper, we propose an ID-based one round authenticated tripartite key agreement protocol. The authenticity of the protocol is assured by a special signature scheme, so that messages carrying the information of two ephemeral keys can be broadcasted authentically by an entity. Consequently, one instance of our protocol results in eight session keys for the three entities. Security attributes of our protocol are presented, and the computational overhead and bandwidth of the broadcast messages are analyzed as well.

We extend the explicit formulae for arithmetic on genus two curves of Takahashi and Miyamoto,Doi,Matsuo,Chao,and Tsuji to fields of even characteristic and to arbitrary equation of the curve and slightly improve them. These formulae can be evaluated faster than the more general Cantor algorithm and allow to obtain faster arithmetic on a hyperelliptic genus 2 curve than on elliptic curves. We give timings for implementations using various libraries for the field arithmetic.

We present a security analysis of the Diffie-Hellman key-exchange protocols authenticated with digital signatures used by the Internet Key Exchange (IKE) standard, and of the more comprehensive SIGMA family of key exchange protocols. The analysis is based on an adaptation of the key-exchange security model from [Canetti and Krawczyk, Eurocrypt'01] to the setting where peer identities are not necessarily known or disclosed from the start of the protocol. This is a common practical setting, which includes the case of IKE and other protocols that provide confidentiality of identities over the network. The rigorous study of this ``post-specified peer" model is a further contribution of this paper.

Mix chains as proposed by Chaum allow sending untraceable electronic e-mail without requiring trust in a single authority: messages are recursively public-key encrypted to multiple intermediates (mixes), each of which forwards the message after removing one layer of encryption. To conceal as much information as possible when using variable (source routed) chains, all messages passed to mixes should be of the same length; thus, message length should not decrease when a mix transforms an input message into the corresponding output message directed at the next mix in the chain. Chaum described an implementation for such length-preserving mixes, but it is not secure against active attacks. We show how to build practical cryptographically secure length-preserving mixes. The conventional definition of security against chosen ciphertext attacks is not applicable to length-preserving mixes; we give an appropriate definition and show that our construction achieves provable security.

We propose a robust proactive threshold signature scheme, a multisignature scheme and a blind signature scheme which work in any Gap Diffie-Hellman (GDH) group (where the Computational Diffie-Hellman problem is hard but the Decisional Diffie-Hellman problem is easy). Our constructions are based on the recently proposed GDH signature scheme of Boneh et al. \cite{bls}. Due to the instrumental structure of GDH groups and of the base scheme, it turns out that most of our constructions are simpler, more efficient and have more useful properties than similar existing constructions. We support all the proposed schemes with proofs under the appropriate computational assumptions, using the corresponding notions of security.

We investigate relations among the discrete logarithm (DL) problem, the Diffie-Hellman (DH) problem and the bilinear Diffie-Hellman (BDH) problem when we have an efficient computable non-degenerate bilinear map $e:G\times G \rightarrow H$. Under a certain assumption on the order of $G$, we show that the DH problem on $H$ implies the DH problem on $G$, and both of them are equivalent to the BDH problem when $e$ is {\it weak-invertible}. Moreover, we show that given the bilinear map $e$ an injective homomorphism $f:H\rightarrow G$ enables us to solve the DH problem on $G$ efficiently, which implies the non-existence a {\it self-bilinear} map $e:G\times G \rightarrow G$ when the DH problem on $G$ is hard. Finally we introduce a sequence of bilinear maps and its applications.

This paper describes how any Identity Based Signature schemes can be used to implement a Group Signature scheme. The performance of the generated Group Signature scheme is similar to the performance of the underlying ID-based Signature scheme. This makes our proposal very attractive since most of existing group signature schemes that have been proposed so far are grossly inefficient. In contrast, ID-based signature schemes can be very efficient especially if they use elliptic curves and pairing.

A common practice to encrypt with RSA is to first apply a padding scheme to the message and then to exponentiate the result with the public exponent; an example of this is OAEP. Similarly, the usual way of signing with RSA is to apply some padding scheme and then to exponentiate the result with the private exponent, as for example in PSS. Usually, the RSA modulus used for encrypting is different from the one used for signing. The goal of this paper is to simplify this common setting. First, we show that PSS can also be used for encryption, and gives an encryption scheme semantically secure against adaptive chosen-ciphertext attacks, in the random oracle model. As a result, PSS can be used indifferently for encryption or signature. Moreover, we show that PSS allows to safely use the same RSA key-pairs for both encryption and signature, in a concurrent manner. More generally, we show that using PSS the same set of keys can be used for both encryption and signature for any trapdoor partial-domain one-way permutation. The practical consequences of our result are important: PKIs and public-key implementations can be significantly simplified.

In this paper we investigate the efficiency of cryptosystems based on ordinary elliptic curves over fields of characteristic three. We look at different representations for curves and consider some of the algorithms necessary to perform efficient point multiplication. We give example timings for our operations and compare them with timings for curves in characteristic two of a similar level of security. We show that using the Hessian form in characteristic three produces a point multiplication algorithm under $50$ percent slower than the equivalent system in characteristic two. Thus it is conceivable that curves in characteristic three, could offer greater performance than currently perceived by the community.

Abstract. The Bi-linear Diffie-Hellman (BDH) intractability assumption is required to establish the security of new Weil-pairing based cryptosystems. BDH is reducible to most of the older believed-to-be-hard discrete-log problems and DH problems, but there is no known reduction from any of those problems to BDH. Let the bilinear mapping be e:G1 X G1->G2, where G1 and G2 are cyclic groups. We show that a many-one reduction from any of the relevant problems to BDH has to include an efficient mapping \phi:G2 ->G1 where \phi(g^{x})=f(x)P. Here g, and P are generators of the corresponding cyclic groups. The function \phi must be used in the reduction either before or after the call to oracle BDH. We show that if f(x)=ax^n+b for any constants a,b,n, then \phi could be used as an oracle for a probabilistic polynomial time solution for Decision Diffie-Hellman in G2. Thus such a reduction is unlikely.

We present an algorithm that speeds exponentiation on a general elliptic curve by an estimated 3.8% to 8.5% over the best known general exponentiation methods when using affine coordinates. This is achieved by eliminating a field multiplication when we compute 2P + Q from given points P, Q on the curve. We give applications to simultaneous multiple exponentiation and to the Elliptic Curve Method of factorization. We show how this improvement together with another idea can speed the computation of the Weil and Tate pairings by up to 7.8%.

We show the existence of a previously unknown linear redundancy property of the only nonlinear component of the AES block cipher. It is demonstrated that the outputs of the 8*8 Rijndael s-box (based on inversion in a finite field) are all equivalent under affine transformation. The method used to discover these affine relations is novel and exploits a new fundamental result on the invariance properties of local connection structure of affine equivalence classes. As well as increasing existing concerns about the security of the AES, these results may also have serious consequences for many other ciphers recently proposed for standardisation.

We consider the function ensembles emerging from the construction of Goldreich, Goldwasser and Micali (GGM), when applied to an arbitrary pseudoramdon generator. We show that, in general, such functions fail to yield correlation intractable ensembles. Specifically, it may happen that, given a description of such a function, one can easily find an input that is mapped to zero under this function.

In this paper, a new special-purpose factorization algorithm is presented, which finds a prime factor $p$ of an integer $n $ in polynomial time, if $4p-1$ has the form $d b^2$ where $d \in \{3, 11, 19, 43, 67, 163\}$ and $b$ is an integer. Hence such primes should be avoided when we select the RSA secret keys. Some generalizations of the algorithm are discussed in the paper as well.

A new construction of a pseudorandom generator based on a simple combination of three feedback shift registers (FSRs) is introduced. The main characteristic of its structure is that the output of one of the three FSRs controls the clocking of the other two FSRs. This construction allows users to generate a large family of sequences using the same initial states and the same feedback functions of the three combined FSRs. The construction is related to the Alternating Step Generator that is a special case of this construction. The period, and the lower and upper bound of the linear complexity of the output sequences of the construction whose control FSR generates a de Bruijn sequence and the other two FSRs generate m-sequences are established. Furthermore, it is established that the distribution of short patterns in these output sequences occur equally likely and that they are secure against correlation attacks. All these properties make it a suitable crypto-generator for stream cipher applications.

Using the Frobenius endomorphism the operation of computing scalar-mulitples in the Jacobian of a hyperelliptic curve is sped-up considerably. The kind of curves considered are Kobiltz i.e. subfield curves, defined over a small finite field which are then considered over a large extension field. We deal with computation of the group order over various extension fields, algorithms to obtain the mentioned speed-up, and experimental results concerning both issues. Additionally an alternative set-up is treated which uses arihtmetic in the finite field only and allows shorter code for similar security. Furthermore explicit formulae to perform the arithmetic in the ideal class group explicitely are derived and can thus be used for implementation in hardware; in software they are also faster than the generic Cantor algorithm. As a second group suitable for cryptographic applications the trace-zero-variety is considered. Here we investigate the group operation and deal with security issues.

The characterization of ideal access structures and the search for bounds on the optimal information rate are two important problems in secret sharing. These problems are studied in this paper for access structures with intersection number equal to one, that is, access structures such that there is at most one participant in the intersection of any two different minimal qualified subsets. The main result in this work is the complete characterization of the ideal access structures with intersection number equal to one. Besides, bounds on the optimal information rate are provided for the non-ideal case.

We present an algorithm for computing the zeta function of an arbitrary hyperelliptic curve over a finite field $\FF_q$ of characteristic 2, thereby extending the algorithm of Kedlaya for odd characteristic. For a genus $g$ hyperelliptic curve defined over $\FF_{2^n}$, the average-case time complexity is $O(g^{4 + \varepsilon} n^{3 + \varepsilon})$ and the average-case space complexity is $O(g^{3} n^{3})$, whereas the worst-case time and space complexities are $O(g^{5 + \varepsilon} n^{3 + \varepsilon})$ and $O(g^{4} n^{3})$ respectively.

In regular digital signatures, once the secret key is compromised, all signatures, even those that were issued by the honest signer before the compromise, will not be trustworthy any more. Forward-secure signatures have been proposed to address this major shortcoming. We present a new forward-secure signature scheme, called KREUS, with several advantages. It has the most efficient Key Update of all known schemes, requiring just a single modular squaring. Our scheme thus enables more frequent Key Update and hence allows shorter time periods, enhancing security: fewer signatures might become invalid as a result of key compromise. In addition, the on-line component of signing is also very efficient, consisting of a single multiplication. We precisely analyze the total signer costs and show that they are lower when the number of signatures per time period is small; the advantage of our scheme increases considerably as the number of time periods grows. Our scheme's security relies on the Strong-RSA assumption and the random-oracle-based Fiat-Shamir transform.

Probabilistic Signature Scheme (PSS), Full Domain Hash (FDH) and several of their variants are widely used signature schemes, which can be formally analyzed in the random oracle model. These schemes output a signature of the form (f^{-1}(y),pub), where y somehow depends on the message signed (and pub) and f is some public trapdoor permutation (typically RSA). Interestingly, all these signature schemes can be proven {\em asymptotically} secure for an {\em arbitrary} trapdoor permutation f, but their {\em exact} security seems to be significantly better for {\em special} trapdoor permutations like RSA. This leads to two natural questions: (1) can the asymptotic security analysis be improved with general trapdoor permutations?; and, if not, (2) what {\em general cryptographic assumption} on f --- enjoyed by specific functions like RSA --- is ``responsible'' for the improved security? We answer both these questions. First, we show that if f is a ``black-box'' trapdoor permutation, then the poor exact security is unavoidable. More specifically, the ``security loss'' for general trapdoor permutations is \Omega(q_hash), where q_hash is the number of random oracle queries made by the adversary (which could be quite large). On the other hand, we show that all the security benefits of the RSA-based variants come into effect once f comes from a family of {\em claw-free permutation} pairs. Our results significantly narrow the current ``gap'' between general trapdoor permutations and RSA to the ``gap'' between trapdoor permutations and claw-free permutations. Additionally, they can be viewed as the first {\em security/efficiency} separation between these basic cryptographic primitives. In other words, while it was already believed that certain cryptographic objects {\em can} be build from claw-free permutations but {\em not} from general trapdoor permutations, we show that certain important schemes (like FDH and PSS) provably work with {\em either}, but enjoy a much better tradeoff between security and efficiency when deployed with claw-free permutations.

In order to decide on advertisement fees for web servers, Naor and Pinkas introduced metering schemes secure against coalition of corrupt servers and clients. In their schemes any server is able to construct a proof to be sent to an audit agency if and only if it has been visited by at least a certain number of clients. Several researchers have generalized the idea of Naor and Pinkas: first metering scheme with pricing and dynamic multi-threshold metering schemes have been proposed; later the solution has been extended to allow for general access structures and an approach on linear algebra has been introduced. In this paper we are interested in the efficiency of applying general access structures and linear algebra techniques to metering schemes. We propose a new model considering general access structures for clients, corrupted clients and servers. Then we bind the access structures for clients and corrupted clients into one. We propose a new metering scheme, which is more efficient w.r.t.\ communication complexity and memory requirements than the scheme of Blundo \textit{et al.}

The paper gives an upper bound on the size of a $q$-ary code of length $n$ that has the $k$-identifiable parent property. One consequence of this bound is that the optimal rate of such a code is determined in many cases when $q\rightarrow\infty$ with $k$ and $n$ fixed.

Encryption that is only semantically secure should not be used on messages that depend on the underlying secret key; all bets are off when, for example,one encrypts using a shared key K the value K. Here we introduce a new notion of security, KDM security, appropriate for key-dependent messages. The notion makes sense in both the public-key and shared-key settings. For the latter we show that KDM security is easily achievable within the random-oracle model. By developing and achieving stronger notions of encryption-scheme security it is hoped that protocols which are proven secure under ``formal'' models of security can, in time, be safely realized by generically instantiating their primitives.

This paper presents a new, powerful statistical testing of symmetric ciphers and hash functions which allowed us to detect biases in both of these systems where previously known tests failed. We first give a complete characterization of the Algebraic Normal Form (ANF) of random Boolean functions by means of the Möbius transform. Then we built a new testing based on the comparison between the structure of the different Boolean functions Algebraic Normal Forms characterizing symmetric ciphers and hash functions and those of purely random Boolean functions. Detailed testing results on several cryptosystems are presented. As a main result we show that AES, DES Snow and Lili-128 fail all or part of the tests and thus present strong biases.

A signcryption scheme is a scheme that provides private and authenticated delivery of messages between two parties. It does this in a more efficient manner than a straightforward composition of an encryption scheme with a signature scheme. An identity-based cryptosystem is one in which the public key may be any string (or may be derived from any string). In this paper we propose an identity-based signcryption scheme. We give a security model for such a scheme and sketch the details of how our scheme may be proved secure in this model.

We present a new public key cryptosystem based on the notion called square decisional Diffie-Hellman problem. The scheme is provably secure against adaptive chosen cipher-text attack under the hardness assumption of the square decisional Diffie-Hellman problem. Compared with Cramer and Shoup's notable public key scheme, our scheme enjoys several nice features: (1)Both schemes are provably secure against adaptive chosen cipher-text attack under the intractability paradigm (the security of Cramer-Shoup's scheme is based on the standard decisional Diffie-Hellman problem while ours based on the square decisional Diffie-Hellman problem; (2)The computational and communication complexity of our scheme is equivalent to the Cramer and Shoup's scheme however, the test function of Cramer-shoup's scheme is linear while our scheme is non-linear, therefore our reduction is more efficient.

This note describes a technique for generating large non-singular matrices with blocks of full rank. While this may be of independent interest, our motivation arises in the white-box implementation of cryptographic algorithms with S-boxes.