By considering a new metric, we generalize cryptographic properties of Boolean functions such as resiliency and propagation characteristics. These new definitions result in a better understanding of the properties of Boolean functions and provide a better insight in the space defined by this metric. This approach leads to the construction of ``hand-made'' Boolean functions, i.e., functions for which the security with respect to some specific monotone sets of inputs is considered, instead of the security with respect to all possible monotone sets with the same cardinality, as in the usual definitions. This approach has the advantage that some trade-offs between important properties of Boolean functions can be relaxed.

Since Boneh and Franklin published their seminal paper on identity based encryption (IBE) using the Weil pairing , there has been a great deal of interest in cryptographic primitives based on elliptic-curve pairings. One particularly interesting application has been to control access to data, via possibly complex policies. In this paper we continue the research in this vein. We present an encryption scheme such that the receiver of an encrypted message can only decrypt if it satisfies a particular policy chosen by the sender at the time of encryption. Unlike standard IBE, our encryption scheme is escrow free in that no key-issuing authority (or colluding set of key-issuing authorities) is able to decrypt ciphertexts itself. In addition we describe a security model for the scenario in question and provide proofs of security for our scheme (in the random oracle model).

Very recently, Jung, Paeng and Kim [IEEE Communications Letters, Vol 8, No 7, pp 446--448, July 2004] have demonstrated the insecurity of Xu and Tilborg's ID-based conference key distribution scheme, and in addition, have revised the scheme to fix the security flaws discovered by them. However, in this paper, we show that Jung-Paeng-Kim's revised scheme is still insecure since it is vulnerable to an active attack of colluding adversaries. We also show that our attack can be easily thwarted by a simple patch.

In this paper, we study, in relationship with covering sequences, the structure of those subsets of $\V {n}$ which can be the Walsh supports of Boolean functions.

We deal with a divisor class halving algorithm on hyperelliptic curve cryptosystems (HECC), which can be used for scalar multiplication, instead of a doubling algorithm. It is not obvious how to construct a halving algorithm, due to the complicated addition formula of hyperelliptic curves. In this paper, we propose the first halving algorithm used for HECC of genus 2, which is as efficient as the previously known doubling algorithm. From the explicit formula of the doubling algorithm, we can generate some equations whose common solutions contain the halved value. From these equations we derive four specific equations and show an algorithm that selects the proper halved value using two trace computations in the worst case. If a base point is fixed, we can reduce these extra field operations by using a pre-computed table which shows the correct halving divisor class —the improvement over the previously known fastest doubling algorithm is up to about 10%. This halving algorithm is applicable to DSA and DH scheme based on HECC. Finally, we present the divisor class halving algorithms for not only the most frequent case but also other exceptional cases.

A new method for digital true random number generation based on asynchronous logic circuits with feedback is introduced. In particular, a concrete technique using the so-called Fibonacci and Galois ring oscillators is developed and experimentally tested in FPGA technology. The generated random binary sequences inherently have a high speed and a very high and robust entropy rate in comparison with previous proposals for digital random number generators. A new method for digital post-processing of random data based on non-autonomous synchronous logic circuits with feedback is also introduced and a concrete technique using a self-clock-controlled linear feedback shift register is proposed. The post-processing can provide both randomness extraction and computationally secure speed increase of input random data.

This paper deals with the security of iterated hash functions against generic attacks, such as, e.g., Joux' multicollision attacks from Crypto 04. The core idea is to increase the size of the internal state of an n-bit hash function to w > n bit. Variations of this core idea allow the use of a compression function with n output bits, even if the compression function itself is based on a block cipher. In a formal model, it is shown that these modifications quantifiably improve the security of iterated hash functions against generic attacks.

This paper provides either security proofs or attacks for a large number of identity-based identification and signature schemes defined either explicitly or implicitly in existing literature. Underlying these is a framework that on the one hand helps explain how these schemes are derived, and on the other hand enables modular security analyses, thereby helping to understand, simplify and unify previous work. We also analyze a generic folklore construction that in particular yields identity-based identification and signature schemes without random oracles.

In this paper, we show that Bresson-Chevassut-Essiari-Pointcheval's group key agreement scheme does not meet the main security properties: implicit key authentication, forward secrecy, and known key security. Also, we propose an improved version which fixes the security flaws found in the scheme.

Identity-based (ID-based) public key cryptosystem can be a good alternative for certificate-based public key setting, especially when efficient key management and moderate security are required. In a $(t,n)$ threshold proxy signature scheme, the original signer delegates the power of signing messages to a designated proxy group of $n$ members. Any $t$ or more proxy signers of the group can cooperatively issue a proxy signature on behalf of the original signer, but $t-1$ or less proxy signers cannot. In this paper, we present an ID-based threshold proxy signature scheme using bilinear pairings. We show the scheme satisfies all security requirements in the random oracle model. To the best of authors' knowledge, our scheme is the first ID-based threshold proxy signature scheme.

Two possible types of attack (a replay attack and a type attack) on a key establishment protocol (mechanism 12) standardised in ISO/IEC 11770-2 are described and two solutions are proposed.

This paper presents an efficient approach for classification of the affine equivalence classes of cosets of the first order Reed-Muller code with respect to cryptographic properties such as correlation-immunity, resiliency and propagation characteristics. First, we apply the method to completely classify all the $48$ classes into which the general affine group $AGL(2,5)$ partitions the cosets of $RM(1,5)$. Second, we describe how to find the affine equivalence classes together with their sizes of Boolean functions in 6 variables. We perform the same classification for these classes. Moreover, we also determine the classification of $RM(3,7)/RM(1,7)$. We also study the algebraic immunity of the corresponding affine equivalence classes. Moreover, several relations are derived between the algebraic immunity and other cryptographic properties. Finally, we introduce two new indicators which can be used to distinguish affine inequivalent Boolean functions when the known criteria are not sufficient. From these indicators a method can be derived for finding the affine relation between two functions (if such exists). The efficiency of the method depends on the structure of the Walsh or autocorrelation spectrum.

A new, vectorial approach to fast correlation attacks on binary memoryless combiners is proposed. Instead of individual input sequences or their linear combinations, the new attack is targeting subsets of input sequences as a whole, thus exploiting the full correlation between the chosen subset and the output sequence. In particular, all the input sequences can be targeted simultaneously. The attack is based on a novel iterative probabilistic algorithm which is also applicable to general memoryless combiners over finite fields or finite rings. Experimental results obtained for randomly chosen binary combiners with balanced combining functions show that the vectorial approach yields a considerable improvement in comparison with the classical, scalar approach.

We study the limitations of steganography when the sender is not using any properties of the underlying channel beyond its entropy and the ability to sample from it. On the negative side, we show that the number of samples the sender must obtain from the channel is exponential in the rate of the stegosystem. On the positive side, we present the first secret-key stegosystem that essentially matches this lower bound regardless of the entropy of the underlying channel. Furthermore, for high-entropy channels, we present the first secret-key stegosystem that matches this lower bound statelessly (i.e., without requiring synchronized state between sender and receiver).

Error correcting codes and matroids have been widely used in the study of ordinary secret sharing schemes. In this paper, we study the connections between codes, matroids, and a special class of secret sharing schemes: multiplicative linear secret sharing schemes. Such schemes are known to enable multi-party computation protocols secure against general (non-threshold) adversaries. Two open problems related to the complexity of multiplicative LSSSs are considered in this paper. The first one deals with strongly multiplicative LSSSs. As opposed to the case of multiplicative LSSSs, it is not known whether there is an efficient method to transform an LSSS into a strongly multiplicative LSSS for the same access structure with a polynomial increase of the complexity. We prove a property of strongly multiplicative LSSSs that could be useful in solving this problem. Namely, using a suitable generalization of the well-known Berlekamp-Welch decoder, we show that all strongly multiplicative LSSSs enable efficient reconstruction of a shared secret in the presence of malicious faults. The second one is to characterize the access structures of ideal multiplicative LSSSs. Specifically, we wonder whether all self-dual vector space access structures are in this situation. By the aforementioned connection, this in fact constitutes an open problem about matroid theory, since it can be re-stated in terms of representability of identically self-dual matroids by self-dual codes. We introduce a new concept, the flat-partition, that provides a useful classification of identically self-dual matroids. Uniform identically self-dual matroids, which are known to be representable by self-dual codes, form one of the classes. We prove that this property also holds for the family of matroids that, in a natural way, is the next class in the above classification: the identically self-dual bipartite matroids.

In many situations we want to enjoy confidentiality, authenticity and non-repudiation of message simultaneously. One approach to achieve this objective is to "sign-then-encrypt" the message, or we can employ special cryptographic scheme like signcryption. Two open problems about identity-based (ID-based) signcryption were proposed in \cite{CryptoePrint:2003:023}. The first one is to devise an efficient forward-secure signcryption scheme with public verifiability and public ciphertext authenticity, which is promptly closed by \cite{LNCS2971:ICISC2003:CYHC}. Another one which still remains open is to devise a hierarchical ID-based signcryption scheme that allows the user to receive signcrypted messages from sender who is under another sub-tree of the hierarchy. This paper aims at solving this problem by proposing two concrete constructions of hierarchical ID-based signcryption.

Chameleon signatures were introduced by Krawczyk and Rabin, being non-interactive signature schemes that provide non-transferability. However, that first construction employs a chameleon hash that suffers from a key exposure problem: The non-transferability property requires willingness of the recipient in consequentially exposing a secret key, and therefore invalidating all signatures issued to the same recipient's public key. To address this key-revocation issue, and its attending problems of key redistribution, storage of state information, and greater need for interaction, an identity-based scheme was proposed in [1], while a fully key-exposure free construction, based on the elliptic curves with pairings, appeared later in [7]. Herein we provide several constructions of exposure-free chameleon hash functions based on different cryptographic assumptions, such as the RSA and the discrete logarithm assumptions. One of the schemes is a novel construction that relies on a single trapdoor and therefore may potentially be realized over a large set of cryptographic groups (where the discrete logarithm is hard).

After some excitement generated by recently suggested public key exchange protocols due to Anshel-Anshel-Goldfeld and Ko-Lee et al., it is a prevalent opinion now that the conjugacy search problem is unlikely to provide sufficient level of security if a braid group is used as the platform. In this paper we address the following questions: (1) whether choosing a different group, or a class of groups, can remedy the situation; (2) whether some other ``hard" problem from combinatorial group theory can be used, instead of the conjugacy search problem, in a public key exchange protocol. Another question that we address here, although somewhat vague, is likely to become a focus of the future research in public key cryptography based on symbolic computation: (3) whether one can efficiently disguise an element of a given group (or a semigroup) by using defining relations.

Computing the order of the Jacobian of a hyperelliptic curve remains a hard problem. It is usually essential to calculate the order of the Jacobian to prevent certain sub-exponential attacks on the cryptosystem. This paper reports on the viability of implementations of various point-counting techniques. We also report on the scalability of the algorithms as the fields grow larger.

This paper shows that many of elliptic curve cryptosystems over quartic extension fields of odd characteristics are reduced to genus two hyperelliptic curve cryptosystems over quadratic extension fields. Moreover, it shows that almost all of the genus two hyperelliptic curve cryptosystems over quadratic extension fields of odd characteristics come under Weil descent attack. This means that many of elliptic curve cryptosystems over quartic extension fields of odd characteristics can be attacked by Weil descent uniformly.

We propose a new class of key establishment schemes which are based on geometric generalizations of the classical Diffie-Hellman. The simplest of our schemes – based on the geometry of the unit circle – uses only multiplication of rational numbers by integers and addition of rational numbers in its key creation. Its first computer implementation works significantly faster than all known implementations of Diffie-Hellman. Preliminary estimations show that our schemes are resistant to attacks. This resistance follows the pattern of the discrete logarithm problem and hardness of multidimensional lattice problems

Since 1981, when Lamport introduced the remote user authentication scheme using table, a plenty of schemes had been proposed with table and without table using. Recently Das, Saxena and Gulati have proposed A dynamic ID-based remote user authentication scheme. They claimed that their scheme is secure against ID-theft, and can resist the reply attacks, forgery attacks, and insider attacks and so on. In this paper we show that Das et al.’s scheme is completely insecure and using of this scheme is equivalent to an open server access without any password.

In this paper, we study the new class step-wise Triangular Schemes (STS) of public key cryptosystems (PKC) based on multivariate quadratic polynomials. In these schemes, we have $m$ the number of equations, $n$ the number of variables, $L$ the number of steps/layers, $r$ the number of equations/variables per step, and $q$ the size of the underlying field. We present two attacks on the STS class by exploiting the chain of the kernels of the private key polynomials. The first attack is an inversion attack which computes the message/signature for given ciphertext/message in $O(mn^3Lq^r + n^2Lrq^r)$, the second is a structural attack which recovers an equivalent version of the secret key in $O(mn^3Lq^r + mn^4)$ operations. Since the legitimate user has workload $q^r$ for decrypting/computing a signature, the attacks presented in this paper are very efficient. As an application, we show that two special instances of STS, namely RSE(2)PKC and RSSE(2)PKC, recently proposed by Kasahara and Sakai, are insecure.

It is found that Chang et al.'s signature scheme with message recovery is not as secure as they claimed, in fact. In this letter, two forgery attacks is proposed to show that the signature can be forged on any uncontrolled messages. To overcome these attacks, the one-way hash functions and the message redundancy schemes may be still used.

A finite field K is said to be weak for elliptic curve cryptography if all instances of the discrete logarithm problem for all elliptic curves over K can be solved in significantly less time than it takes Pollard's rho method to solve the hardest instances. By considering the GHS Weil descent attack, it was previously shown that characteristic two finite fields GF(q^5) are weak. In this paper, we examine characteristic two finite fields GF(q^n) for weakness under Hess' generalization of the GHS attack. We show that the fields GF(q^7) are potentially partially weak in the sense that any instance of the discrete logarithm problem for half of all elliptic curves over GF(q^7), namely those curves E for which #E is divisible by 4, can likely be solved in significantly less time than it takes Pollard's rho method to solve the hardest instances. We also show that the fields GF(q^3) are partially weak, that the fields GF(q^6) are potentially weak, and that the fields GF(q^8) are potentially partially weak. Finally, we argue that the other fields GF(2^N) where N is not divisible by 3, 5, 6, 7 or 8, are not weak under Hess' generalized GHS attack.

A (t,n) threshold proxy signature scheme enables an original signer to delegate the signature authority to a proxy group of n member such that t or more than t proxy signers can cooperatively sign messages on behalf of the original signer. In the paper, we review the security of some nonrepudiable threshold proxy signature schemes with known signers. We show that Sun's threshold proxy scheme, Yang et al.'s threshold proxy signature scheme and Tzeng et al.'s threshold proxy signature scheme are insecure against an original signer's forgery. We also show that Hsu et al.'s threshold proxy signature scheme suffers from the conspiracy of the original signer and the secret share dealer SA, and that Hwang et al.'s threshold proxy signature scheme is universally forgeable. In a word, none of the above-mentioned threshold proxy signature schemes can provide non-repudiation.

Password-based authenticated key exchange are protocols which are designed to be secure even when the secret key or password shared between two users is drawn from a small set of values. Due to the low entropy of passwords, such protocols are always subject to on-line guessing attacks. In these attacks, the adversary may succeed with non-negligible probability by guessing the password shared between two users during its on-line attempt to impersonate one of these users. The main goal of password-based authenticated key exchange protocols is to restrict the adversary to this case only. In this paper, we consider password-based authenticated key exchange in the three-party scenario, in which the users trying to establish a secret do not share a password between themselves but only with a trusted server. Towards our goal, we recall some of the existing security notions for password-based authenticated key exchange protocols and introduce new ones that are more suitable to the case of generic constructions. We then present a natural generic construction of a three-party protocol, based on any two-party authenticated key exchange protocol, and prove its security without making use of the Random Oracle model. To the best of our knowledge, the new protocol is the first provably-secure password-based protocol in the three-party setting.

Synchronous stream ciphers need perfect synchronization between sender and receiver. In practical applications, this is ensured by a resync mechanism. Daemen et al first described attacks on ciphers using such a resync mechanism. In this paper, we extend their attacks in several ways by combining the standard attack with several cryptanalytic techniques such as algebraic attacks and linear cryptanalysis. Our results show that using linear resync mechanisms should be avoided, and give lower bounds for the nonlinearity required from a secure resync mechanism.

In this paper we consider two security notions related to Identity Based Encryption: Key-insulated public key encryption, introduced by Dodis, Katz, Xu and Yung; and Timed-Release Public Key cryptography, introduced independently by May and Rivest, Shamir and Wagner. We first formalize the notion of secure timed-release public key encryption, and show that, despite several differences in its formulation, it is equivalent to strongly key-insulated public key encryption (with optimal threshold and random access key updates). Next, we introduce the concept of an authenticated timed-release cryptosystem, briefly consider generic constructions, and then give a construction based on a single primitive which is efficient and provably secure.

This paper proposes a new scheme for partially blind signature based on the difficulty in solving the discrete logarithm problem. Under the assumption of the generic model, random oracle model, and intractable ROS-problem, this paper formally proves that the proposed scheme is secure against one-more signature forgery under the adaptively parallel attack. Previous schemes using two signing equations for plain information and commitment. The proposed scheme uses two secret keys to combine these two signing equations, thus it is more efficient than previous schemes in both communicational and computational cost.

The notion of quantum secure direct communication (QSDC) has been introduced recently in quantum cryptography as a replacement for quantum key distribution, in which two communication entities exchange secure classical messages without establishing any shared keys previously. In this paper, a quantum secure direct communication scheme using quantum Calderbank-Shor-Steane (CCS) error correction codes is proposed. In the scheme, a secure message is first transformed into a binary error vector and then encrypted(decrypted) via quantum coding(decoding) procedures. An adversary Eve, who has controlled the communication channel, can't recover the secrete messages because she doesn't know the deciphering keys. Security of this scheme is based on the assumption that decoding general linear codes is intractable even on quantum computers.

The distribution of r-patterns is an important aspect of pseudorandomness for periodic sequences over finite field.The aim of this work is to study the distribution of r-patterns in the Kerdock-code binary sequences and the highest level sequences of primitive sequences over $Z_{2^l}$.By combining the local Weil bound with spectral analysis,we derive the upper bound of the deviation to uniform distribution.As a consequence,the recent result on the quantity is improved.

We present a new type of fault attacks on elliptic curve scalar multiplications: Sign Change Attacks. These attacks exploit different number representations as they are often employed in modern cryptographic applications. Previously, fault attacks on elliptic curves aimed to force a device to output points which are on a cryptographically weak curve. Such attacks can easily be defended against. Our attack produces points which do not leave the curve and are not easily detected. The paper also presents a revised scalar multiplication algorithm that provably protects against Sign Change Attacks.

We show new lower bounds and impossibility results for general (possibly *non-black-box*) zero-knowledge proofs and arguments. Our main results are that, under reasonable complexity assumptions: 1. There does not exist a two-round zero-knowledge *proof* system with perfect completeness for an NP-complete language. The previous impossibility result for two-round zero knowledge, by Goldreich and Oren (J. Cryptology, 1994) was only for the case of *auxiliary-input* zero-knowledge proofs and arguments. 2. There does not exist a constant-round zero-knowledge *strong* proof or argument of knowledge (as defined by Goldreich (2001)) for a nontrivial language. 3. There does not exist a constant-round public-coin *proof* system for a nontrivial language that is *resettable zero knowledge*. This result also extends to "bounded-resettable" zero knowledge, in which the number of resets is a priori bounded by a polynomial in the input length and prover-to-verifier communication. In contrast, we show that under reasonable assumptions, there does exist such a (computationally sound) *argument* system that is bounded-resettable zero knowledge. The complexity assumptions we use are not commonly used in cryptography. However, in all cases, we show that assumptions similar to ours are necessary for the above results. Most previously known lower bounds, such as those of Goldreich and Krawczyk (SIAM J. Computing, 1996), were only for *black-box* zero knowledge. However, a result of Barak (FOCS 2001) shows that many (or even most) of these black-box lower bounds do *not* extend to the case of general zero knowledge.

A general mathematical framework behind algebraic cryptanalytic attacks is developed. The framework relates to finding algebraic equations induced by vectorial Boolean functions and, in particular, equations of low algebraic degree. The equations may involve only a subset of input variables and may or may not be conditioned on the values of output variables. In addition, the equations may have a special form interesting for the so-called fast algebraic attacks. A possible divide-and-conquer effect is pointed out and the notion of algebraic immunity order, naturally extending the notion of correlation immunity order, is introduced. An application of general results to stream ciphers known as combiners with or without memory, with possibly multiple outputs, is studied in particular detail. Special properties of combiners with finite input memory, such as nonlinear filter generators, are established. Finally, finding induced algebraic equations for divide-and-conquer algebraic attacks on combiners with or without memory is also considered.

Let n be an RSA modulus and let P,Q in (Z/nZ)[X]. This paper explores the following problem: Given polynomials Q and Q(P), find polynomial P. We shed light on the connections between the above problem and the RSA problem and derive from it new zero-knowledge protocols suited to smart-card applications.

Hyperelliptic curve cryptosystem (HECC) is becoming more and more promising for network security applications because of the common effort of several academic and industrial organizations. With short operand size compared to other public key cryptosystems, HECC has showed excellent performance in embedded processors. Recently years, many effort has been made to investigate all kinds of explicit formulae for speeding up group operation of HECC. In this paper, explicit formulae without using inversion for genus 3 HECC are given. We introduce a further coordinate to collect the common denominator of the usual 6 coordinates. The proposed formulae can be used in smart card where inversion is much more expensive than multiplication.

The Unbalanced Oil and Vinegar scheme (UOV) is a signature scheme based on multivariate quadratic equations. It uses $m$ equations and $n$ variables. A total of $v$ of these are called ``vinegar variables". In this paper, we study its security from several points of view. First, we are able to demonstrate that the constant part of the affine transformation does not contribute to the security of UOV and should therefore be omitted. Second, we show that the case $n \geq 2m$ is particularly vulnerable to Gröbner basis attacks. This is a new result for UOV over fields of odd characteristic. In addition, we investigate a modification proposed by the authors of UOV, namely to chose coefficients from a small subfield. This leads to a smaller public key. But due to the smaller key-space, this modification is insecure and should therefore be avoided. Finally, we demonstrate a new attack which works well for the case of small $v$. It extends the affine approximation attack from Youssef and Gong against the Imai-Matsumoto Scheme~B for odd characteristic and applies it against UOV. This way, we point out serious vulnerabilities in UOV which have to be taken into account when constructing signature schemes based on UOV.

We consider the problem of defining and achieving plaintext-aware encryption without random oracles in the classical public-key model. We provide definitions for a hierarchy of notions of increasing strength: PA0, PA1 and PA2, chosen so that PA1+IND-CPA => IND-CCA1 and PA2+IND-CPA => IND-CCA2. Towards achieving the new notions of plaintext awareness, we show that a scheme due to Damgard, denoted DEG, and the ``lite'' version of the Cramer-Shoup scheme, denoted CSL, are both PA0 under the KEA0 assumption of Damgard, and PA1 under an extension of this assumption called KEA1. As a result, DEG is the most efficient proven IND-CCA1 scheme known.

This paper revisits a public key cryptosystem which is based on finite Church-Rosser string-rewriting systems. We consider some ideas for cryptanalysis and discuss issues concerning practical usage. It turns out that without changing crucial details of key generation this cryptosystem does not offer acceptable cryptographic security. We also provide the source code of our rudimentary implementation, if someone would like to use it for further cryptanalysis.

Russell and Wang (Eurocrypt 2002) recently introduced an elegant, information-theoretic notion called entropic security of encryption: they required that the cipher text leak no predicate of the plaintext (similar to semantic security (Goldwasser and Micali, JCSS 1984)) but only as long as the distribution on messages has high entropy from the adversary's point of view. They show that this notion of security can be achieved with very short keys for entropically rich message spaces. Canetti, Miccianci and Reingold (STOC, 1998) had previously constructed hash functions which satisfy a similar entropic security condition. The output of such hash function leaks no partial information about the input, provided the input has sufficiently high entropy. This paper studies entropic security in general, and its application to the encryption of high-entropy messages. (1) We elucidate the notion of entropic security. Our results apply to all entropically-secure primitives, including both encryption and hash functions. We strengthen the formulation of Canetti and Russell and Wang: we require that an entropically-secure primitive leak no function whasoever of its input, while the previous works focus only on predicates. This stronger formulation is much closer to the original notion of semantic security. We also show that entropic security is equivalent to indistinguishability on pairs of input distributions of sufficiently high entropy. This equivalence generalizes the conventional equivalence between indistinguishability and semantic security. Indistinguishability, in turn, is related to randomness extraction from non-uniform distributions. The proof of the equivalence of hiding predicates to hiding all functions is quite involved, and requires very different techniques from those of Goldwasser and Micali. (2) We use the equivalence above, and the connection to randomness extraction, to prove several new results on entropically-secure encryption. We obtain: (a) Two general frameworks for constructing entropically secure encryption schemes, one based on expander graphs and the other on XOR-universal hash functions. These schemes generalize the schemes of Russell and Wang, yielding simpler constructions and proofs as well as improved parameters. The best scheme uses a key of length k=n-t+2log(1/eps)+O(1), where eps is a measure of leakage and t is the initial min-entropy of the message. (b) Lower bounds on the key length k for entropic security and indistinguishability. In particular, we show near tightness of Russell-Wang constructions: k > n-t. (In fact, for a large class of schemes k >= n-t + log(1/eps).)

We propose a new security class, called plaintext-simulatability, defined over the public-key encryption schemes. The notion of plaintext simulatability (denoted PS) is similar to the notion of plaintext awareness (denoted PA), but it is, ``properly'', a weaker security class for public-key encryption. In most cases, PA is ``unnecessarily'' strong, --- only used to prove that a public-key encryption scheme is CCA2-secure, because it looks much easier than to prove ``directly'' that the scheme meets IND-CCA2. We show that PS also implies IND-CCA2, while preserving a good view of the security proofs as well as PA. PS looks ``properly'' stronger than IND-CCA2. So far, however, it is not sure how to prove this, which remains open.

Recently, Augot and Finiasz presented a coding theoretic public key cryptosystem that suggests a new approach for designing such systems based on the Polynomial Reconstruction Problem. Their cryptosystem is an instantiation of this approach under a specific choice of parameters which, given the state of the art of coding theory, we show in this work to be sub-optimal. Coron showed how to attack the Augot and Finiasz cryptosystem. A question left open is whether the general approach suggested by the cryptosystem works or not. In this work, we show that the general approach (rather than only the instantiation) is broken as well. Our attack employs the recent powerful list-decoding mechanisms.

The necessity to secure the communication between hardware components in embedded systems becomes increasingly important with regard to the secrecy of data and particularly its commercial use. We suggest a low-cost (i.e. small logic-area) solution for flexible security levels and short key lifetimes. The basis is an approach for symmetric key exchange using the synchronisation of Tree Parity Machines. Fast successive key generation enables a key exchange within a few milliseconds, given realistic communication channels with a limited bandwidth. For demonstration we evaluate characteristics of a standard-cell ASIC design realisation as IP-core in 0.18 micrometer-technology.

We present novel realizations of the transitive signature primitive introduced by Micali and Rivest, enlarging the set of assumptions on which this primitive can be based, and also providing performance improvements over existing schemes. More specifically, we propose new schemes based on factoring, the hardness of the one-more discrete logarithm problem, and gap Diffie-Hellman groups. All these schemes are proven transitively unforgeable under adaptive chosen-message attack. We also provide an answer to an open question raised by Micali and Rivest regarding the security of their RSA-based scheme, showing that it is transitively unforgeable under adaptive chosen-message attack assuming the security of RSA under one-more-inversion. We then present hash-based modifications of the RSA, factoring and gap Diffie-Hellman based schemes that eliminate the need for ``node certificates'' and thereby yield shorter signatures. These modifications remain provably secure under the same assumptions as the starting scheme, in the random oracle model.

A Boolean function is called normal if it is constant on flats of certain dimensions. This property is relevant for the construction and analysis of cryptosystems. This paper presents an asymmetric Monte Carlo algorithm to determine whether a given Boolean function is normal. Our algorithm is far faster than the best known (deterministic) algorithm of Daum et al. In a first phase, it checks for flats of low dimension whether the given Boolean function is constant on them and combines such flats to flats of higher dimension in a second phase. This way, the algorithm is much faster than exhaustive search. Moreover, the algorithm benefits from randomising the first phase. In addition, by evaluating several flats implicitly in parallel, the time-complexity of the algorithm decreases further. As an application, we determine the level of normality for several, highly nonlinear Boolean power functions.

Recently, Chang \textit{et al}. \cite{Chang} proposed a new digital signature scheme with message recovery and claimed that neither one-way hash functions nor message redundancy schemes were employed in their scheme. However, in this letter, two forgery attacks are proposed to show that Chang \textit{et al.}'s signature scheme is not secure. To resist these attacks, the message redundancy schemes may be still used.

A forward-secure encryption scheme protects secret keys from exposure by evolving the keys with time. Forward security has several unique requirements in Hierarchical Identity-Based Encryption (HIBE) scheme: (1) users join dynamically; (2) encryption is joining-time-oblivious; (3) users evolve secret keys autonomously. We present a scalable forward-secure HIBE scheme satisfying the above properties. Note that a naive combination of Gentry-Silverberg HIBE scheme with the forward-secure Public-Key Encryption scheme by Canetti, Halevi and Katz would not meet the requirements. We also show how our fs-HIBE scheme can be used to construct a forward-secure public-key Broadcast Encryption scheme, which protects the secrecy of prior transmissions in the Broadcast Encryption setting. We further generalize fs-HIBE into a collusion-resistant Multiple Hierarchical ID-Based Encryption scheme, which can be used for secure communications with entities having multiple roles in Role-Based Access Control. The security of our schemes is based on the Bilinear Diffie-Hellman assumption in the random oracle model.

We consider the problem of sending messages into the future, commonly known as timed release cryptography. Existing schemes for this task either solve the relative time problem with uncontrollable, coarse-grained release time (time-lock puzzle approach) or do not provide anonymity to sender and/or receiver and are not scalable (server-based approach). Using a bilinear paring on any Gap Diffie-Hellman group, we solve this problem by giving a scalable, server-passive and user-anonymous timed release public-key encryption scheme which allows precise absolute release time specifications. Unlike the existing server-based schemes, the trusted time server in our scheme is completely passive --- no interaction between it and the sender or receiver is needed; it is even not aware of the existence of a user, thus assuring the anonymity of both the sender and receiver of a message and the privacy of the message. Besides, our scheme also has a number of desirable properties including self-authenticated time-bound key updates, a single form of update for all receivers, simple public-key renewal and key insulation, making it a scalable and appealing solution.

This paper examines the methods in which the ideas behind a KEM--DEM hybrid encryption scheme can be extended to other types of asymmetric primitives, particularly to signcryption schemes. The central principle is a keyed symmetric algorithm can be used to provide a security service for in an asymmetric algorithm provided that that symmetric primitive is under the control of the asymmetric part of the cipher (say, if asymmetric techniques are used to generate the key that the symmetric primitive uses). This theory is applied to signcryption schemes with outsider security and an efficient, provably secure scheme, termed ECISS-KEM, is proposed. The theory is also applied to signature schemes, where it is shown that efficient hybrid signature schemes can never exist, and to signcryption schemes with insider security, where it is shown that several existing schemes can be considered hybrid signcryption schemes.

We report experiments on the security of the GGH-like cryptosystem proposed by Micciancio. Based on these experiments, we conclude that the system can be securely used only in lattice dimensions > 781. Further experiments on the efficiency of the system show that it requires key sizes of 1 MByte and more and that the key generation as well as the decryption take inacceptibly long. Therefore, Micciancio's cryptosystem seems currently far from being practical.

We address one of the most fundamental problems concerning the RSA cryptosystem: does the knowledge of the RSA public and secret key-pair (e,d) yield the factorization of N=pq in polynomial time? It is well-known that there is a probabilistic polynomial time algorithm that on input (N,e,d) outputs the factors p and q. We present the first deterministic polynomial time algorithm that factors N provided that e,d<N. Our approach is an application of Coppersmith's technique for finding small roots of univariate modular polynomials.

The Secure Hash Standard (SHS) [3] includes hashing algorithms denoted SHA-n, (n in {224, 256, 384, 512}) for producing message digests of length n. These algorithms are based on a common design, sometimes known as SHA-2, that consists of a message schedule and a register. The most successful attacks on the SHA algorithms are Chabaud-Joux differential collisions [1, 2, 4, 5, 7], which are based on finding a corrective pattern for the register. Previous analysis of the SHA-2 algoritms [4] indicated that, for all SHA-2 algorithms, the best corrective pattern has probability 2^-66. We find that the complexity of obtaining a collision is 2^39 when the register state is unknown. Of this complexity, a factor of 2^9 corresponds to conditions on the internal state that must be satisfied, and a factor of 2^30 corresponds to 30 bits of internal state that must be guessed correctly in order to generate a collision. When the register state is known (as is the case when generating a hash) then the guessed bits are known and the complexity is reduced to 2^9. The simple analysis of the message schedule in [4] determines limits on the probability of collision for SHA-2, and was sufficient at that time to conclude that the algorithms resist the attacks. In [4] the claimed complexity is compared against the birthday attack bound of 2^n/2. However, the corrective pattern can be converted into a second pre-image attack for which the complexity should be greater than 2^n. When accounting for the complexity of 2^9 per corrective pattern, the previous analysis of the message schedule yields lower bounds on the complexities 2^27 for SHA-224/256 and 2^45 for SHA-224/256. These complexities are significantly less than the 2^n bound. It is no longer certain that SHA-2 resists this attack. More detailed analysis of the message schedule is required.

Identity-based (ID-based) public key cryptosystem can be a good alternative for certificate-based public key setting, especially when efficient key management and moderate security are required. A proxy signature scheme permits an entity to delegate its signing rights to another entity. But to date, no ID-based proxy signature schemes with provable security have been proposed. In this paper, we formalize a notion of security for ID-based proxy signature schemes and propose a scheme based on the bilinear pairings. We show that the security of our scheme is tightly related to the computational Diffie-Hellman assumption in the random oracle model.

This paper describes the direct anonymous attestation scheme (DAA). This scheme was adopted by the Trusted Computing Group as the method for remote authentication of a hardware module, called trusted platform module (TPM), while preserving the privacy of the user of the platform that contains the module. Direct anonymous attestation can be seen as a group signature without the feature that a signature can be opened, i.e., the anonymity is not revocable. Moreover, DAA allows for pseudonyms, i.e., for each signature a user (in agreement with the recipient of the signature) can decide whether or not the signature should be linkable to another signature. DAA furthermore allows for detection of ``known'' keys: if the DAA secret keys are extracted from a TPM and published, a verifier can detect that a signature was produced using these secret keys. The scheme is provably secure in the random oracle model under the strong RSA and the decisional Diffie-Hellman assumption.

The synchronisation of Tree Parity Machines (TPMs), has proven to provide a valuable alternative concept for secure symmetric key exchange. Yet, from a cryptographer's point of view, authentication is at least as important as a secure exchange of keys. Adding an authentication via hashing e.g. is straightforward but with no relation to Neural Cryptography. We consequently formulate an authenticated key exchange within this concept. Another alternative, integrating a Zero-Knowledge protocol into the synchronisation, is also presented. A Man-In-The-Middle attack and even all currently known attacks, that are based on using identically structured TPMs and synchronisation as well, can so be averted. This in turn has practical consequences on using the trajectory in weight space. Both suggestions have the advantage of not affecting the previously observed physics of this interacting system at all.

The Internet Chess Club (ICC) is a popular online chess server with more than 30,000 members worldwide including various celebrities and the best chess players in the world. Although the ICC website assures its users that the security protocol used between client and server provides sufficient security for sensitive information to be transmitted (such as credit card numbers), we show this is not true. In particular we show how a passive adversary can easily read all communications with a trivial amount of computation, and how an active adversary can gain virtually unlimited powers over an ICC user. We also show simple methods for defeating the timestamping mechanism used by ICC. For each problem we uncover, we suggest repairs. Most of these are practical and inexpensive.

In this paper, we continue the study of the covering radius in the set of resilient functions, which has been defined by Kurosawa. This new concept is meaningful to cryptography especially in the context of the new class of algebraic attacks on stream ciphers proposed by Courtois and Meier at Eurocrypt 2003 and Courtois at Crypto 2003. In order to resist such attacks the combining Boolean function should be at high distance from lower degree functions. Using a result from coding theory on the covering radius of $(n-3)$-rd Reed-Muller codes, we establish exact values of the the covering radius of $RM(n-3,n)$ in the set of $1$-resilient Boolean functions of $n$ variables, when $\lfloor n/2 \rfloor = 1 \mod\;2$. We also improve the lower bounds for covering radius of the Reed-Muller codes $RM(r,n)$ in the set of $t$-resilient functions, where $\lceil r/2 \rceil = 0 \mod\;2$, $t \leq n-r-2$ and $n\geq r+3$.

A publicly verifiable secret sharing scheme is more applicable than a verifiable secret sharing because of the property that the validity of the shares distributed by the dealer can be verified by any party. In this paper, we construct a non-interactive and information-theoretic publicly verifiable secret sharing by a computationally binding and unconditionally hiding commitment scheme and zero-knowledge proof of knowledge.

This work addresses the problem of cheating prevention in secret sharing. The scheme is said to be $k$-cheating immune if any group of $k$ cheaters has no advantage over honest participants. In this paper we study the constraints of cheating immune secret sharing schemes. We give a necessary and sufficient condition for SSSs to be cheating immune. Then, we improve the upper bound of D'Arco {\textit et.~al} on the number of cheaters tolerated in such scheme. Our proof is much simpler than the proof of D'Arco {\textit et.~al} and relies on certain properties of cryptographic Boolean functions. As a result of independent interest we provide a condition given function to be $t$-resilient and to satisfy the propagation criterion of degree $\ell$ over any finite field.

A digit-serial, multiplier-accumulator based cryptographic co-processor architecture is proposed, similar to fix-point DSP's with enhancements, supporting long modular arithmetic and general computations. Several new “column-sum” variants of popular quadratic time modular multiplication algorithms are presented (Montgomery and interleaved division-reduction with or without Quisquater scaling), which are faster than the traditional implemen-tations, need no or very little memory beyond the operand storage and perform squaring about twice faster than general multiplications or modular reductions. They provide similar advantages in software for general purpose CPU's.

This note describes an SPA-based side channel attack against a CRT implementation of an RSA function. In contrast with Novak’s attack [8], it concentrates on the initial modular reduction. With the help of lattice reduction it applies even to implementations which use a common randomising technique to ensure resistance against certain side channel attacks.

A reasonably efficient password based key exchange (KE) protocol with provable security without random oracle was recently proposed by Katz, {\em et al.} \cite{KOY01} and later by Gennaro and Lindell \cite{GL03}. However, these protocols do not support mutual authentication (MA). The authors explained that this could be achieved by adding an additional flow. But then this protocol turns out to be 4-round. As it is known that a high entropy secret based key exchange protocol with MA\footnote{we do not consider a protocol with a time stamp or a stateful protocol (e.g., a counter based protocol). In other words, we only consider protocols in which a session execution within an entity is independent of its history, and in which the network is asynchronous.} is optimally 3-round (otherwise, at least one entity is not authenticated since a replay attack is applicable), it is quite interesting to ask whether such a protocol in the password setting (without random oracle) is achievable or not. In this paper, we provide an affirmative answer with an efficient construction in the common reference string (CRS) model. Our protocol is even simpler than that of Katz, {\em et al.} Furthermore, we show that our protocol is secure under the DDH assumption ({\em without} random oracle).

The most common method for computing exponentiation of random elements in Abelian groups are sliding window schemes, which enhance the efficiency of the binary method at the expense of some precomputation. In groups where inversion is easy (e.g. elliptic curves), signed representations of the exponent are meaningful because they decrease the amount of required precomputation. The asymptotic best signed method is wNAF, because it minimizes the precomputation effort whilst the non-zero density is nearly optimal. Unfortunately, wNAF can be computed only from the least significant bit, i.e. right-to-left. However, in connection with memory constraint devices left-to-right recoding schemes are by far more valuable. In this paper we define the MOF (Mutual Opposite Form), a new canonical representation of signed binary strings, which can be computed in any order. Therefore we obtain the first left-to-right signed exponent-recoding scheme for general width w by applying the width w sliding window conversion on MOF left-to-right. Moreover, the analogue right-to-left conversion on MOF yields wNAF, which indicates that the new class is the natural left-to-right analogue to the useful wNAF. Indeed, the new class inherits the outstanding properties of wNAF, namely the required precomputation and the achieved non-zero density are exactly the same.

Recently Kurosawa and Desmedt presented a new hybrid encryption scheme which is secure against adaptive chosen-ciphertext attack. Their scheme is a modification of the Cramer-Shoup encryption scheme. Its major advantage with respect to Cramer-Shoup is that it saves the computation of one exponentiation and produces shorter ciphertexts. However, the proof presented by Kurosawa and Desmedt relies on the use of information-theoretic key derivation and message authentication functions. In this note we present a different proof of security which shows that the Kurosawa-Desmedt scheme can be instantiated with any computationally secure key derivation and message authentication functions, thus extending the applicability of their paradigm, and improving its efficiency.

The recently introduced Galois/Counter Mode (GCM) of operation for block ciphers provides both encryption and message authentication, using universal hashing based on multiplication in a binary finite field. We analyze its security and performance, and show that it is the most efficient mode of operation for high speed packet networks, by using a realistic model of a network crypto module and empirical data from studies of Internet traffic in conjunction with software experiments and hardware designs. GCM has several useful features: it can accept IVs of arbitrary length, can act as a stand-alone message authentication code (MAC), and can be used as an incremental MAC. We show that GCM is secure in the standard model of concrete security, even when these features are used. We also consider several of its important system-security aspects.

In 2004, W. C. Ku and S. M. Chen proposed an efficient remote user authentication scheme using smart cards to solve the security problems of Chien et al.’s scheme. Recently, Hsu and Yoon et al. pointed out the security weakness of the Ku and Chen’s scheme Furthermore, Yoon et al.’s scheme also proposed a new efficient remote user authentication scheme using smart cards. This paper analyzes the security pitfalls of Yoon et al’s scheme and aims to show that the Yoon et al.’s scheme is still vulnerable to the password guessing attack and the insider attack.

The pipelining scheme proposed in~\cite{PKM04} is an efficient and secure scheme for computing scalar multiplication in Elliptic Curve Cryptosystems (ECC). The scheme proposed in~\cite{PKM04} does not assume any pre-computation. In this work we extend the scheme to the situation where the system allows some pre-computation and is capable of storing some precomputed values. Like the scheme proposed in~\cite{PKM04} our scheme uses an extra multiplier. On the performance front, it outperforms the best known sequential and parallel schemes. On the security front, our algorithm uses two countermeasures against SPA and hence are doubly secured against SPA. Also, it is secure against DPA using the Joye-Tymen's curve randomization countermeasure.

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. In this work, we extend this concept to that of distributed ring signatures, where a subset of users cooperate to compute a distributed anonymous signature on a message, on behalf of a family of subsets. We propose two schemes, one for general families of subsets, and a more efficient one for threshold families of subsets. The security of both proposals is formally proved, assuming the hardness of the Computational Diffie-Hellman problem. Our two schemes run in an identity-based scenario, where public keys of the users can be derived from their identities. This fact avoids the necessity of digital certificates, and therefore allows more efficient implementations of such systems.

We present a new probabilistic algorithm to compute modular polynomials modulo a prime. Modular polynomials parameterize pairs of isogenous elliptic curves and are useful in many aspects of computational number theory and cryptography. Our algorithm has the distinguishing feature that it does not involve the computation of Fourier coefficients of modular forms. We avoid computing the exponentially large integral coefficients by working directly modulo a prime and computing isogenies between elliptic curves via Velu's formulas.

In 1997,Patarin and Goubin introduce new asymmetric cryptosystems based on the difficulty of recovering two systems of multivariate polynomials from their composition. We make a different use of this difficult algorithmic problem to obtain a way of representing block ciphers concealing their design but still leaving them executable. We show how to implement our solution with Field Programmable Gate Array. Finally, we give a compact representation of our solution using Binary Decision Diagrams.

In this paper, we present a new parallel architecture to avoid side-channel analyses such as: timing attack, simple/differential power analysis, fault induction attack and simple/differential electromagnetic analysis. We use a Montgomery Multiplication based on Residue Number Systems. Thanks to RNS, we develop a design able to perform an RSA signature in parallel on a set of identical and independent coprocessors. Of independent interest, we propose a new DPA countermeasure in the framework of RNS. It is only (slightly) memory consuming (1.5 KBytes). Finally, we synthesized our new architecture on FPGA and it presents promising performance results. Even if our aim is to sketch a secure architecture, the RSA signature is performed in less than 160 ms, with competitive hardware resources. To our knowledge, this is the first proposal of an architecture counteracting electromagnetic analysis apart from hardware countermeasures reducing electromagnetic radiations.

Hwang and Li proposed the first remote user authentication scheme using smart cards to solve the problems of Lamport scheme. Unfortunately, Hwang and Li’s scheme has some security weaknesses. First, Chan- Chang, Shen- Lin- Hwang and then Chang-Hwang pointed out some attacks on Hwang – Li’s scheme. This paper presents a new remote user authentication scheme with forward secrecy, which provides forward secrecy to the long term secret key of the authentication server. This scheme is also secure against Chan – Cheng and all the extended attacks.

Algebraic attacks on block ciphers and stream ciphers have gained more and more attention in cryptography. The idea is to express a cipher by a system of equations whose solution reveals the secret key. The complexity of an algebraic attack is closely related to the degree of the equations. Hence, low-degree equations are crucial for algebraic attacks. So far, the existence of low-degree equations for simple combiners, combiners with memory and S-boxes was treated independently. In this paper, we unify these approaches by reducing them to the same problem: finding low-degree annihilators. This enables a systematic treatment and implies a general criterion for the existence of low-degree equations. The unification allows to extend former results to all three cases. Therefore, we repeat an algorithm for finding a generating set of all low-degree equations. Additionally, we introduce a new improved version, adapted to specific keystream generators (e.g., for the Bluetooth keystream generator). Finally, we describe for certain cases an upper and a lower bound for the lowest possible degree. To the best of our knowledge, the upper bound has only been presented in the context of keystream generators before and the lower bound was not published previously.

n 2001, Rivest et al. firstly introduced the concept of ring signatures. A ring signature is a simplified group signature without any manager. It protects the anonymity of a signer. The first scheme proposed by Rivest et al. was based on RSA cryptosystem and certificate based public key setting. The first ring signature scheme based on DLP was proposed by Abe, Ohkubo, and Suzuki. Their scheme is also based on the general certificate-based public key setting too. In 2002, Zhang and Kim proposed a new ID-based ring signature scheme using pairings. Later Lin and Wu proposed a more efficient ID-based ring signature scheme. Both these schemes have some inconsistency in computational aspect. In this paper we propose a new ID-based ring signature scheme and a proxy ring signature scheme. Both the schemes are more efficient than existing one. These schemes also take care of the inconsistencies in above two schemes.

In this paper, we present two forward secure signature schemes based on gap Diffie-Hellman groups and prove these schemes to be secure in the sense of slightly stronger security notion than that by Bellare and Miner in the random oracle model. Both schemes use the same key update strategy as the encryption scheme presented by Canetti, Halevi and Katz. Hence, our schemes outperform the previous tree-based forward secure signature scheme by Bellare and Miner in the key generation and key update time, which are only constant in the number of time periods. Specifically, we describe a straightforward scheme following from the encryption scheme, and then improve its efficiency for signature verification algorithm which needs only 3 pairing computations independent of the total time periods.

Goldreich and Lindell (CRYPTO `01) recently presented the first protocol for password-authenticated key exchange in the standard model (with no common reference string or set-up assumptions other than the shared password). However, their protocol uses several heavy tools and has a complicated analysis. We present a simplification of the Goldreich--Lindell (GL) protocol and analysis for the special case when the dictionary is of the form $D=\{0,1\}^d$, i.e. the password is a short random string (like an ATM PIN number). Our protocol can be converted into one for arbitrary dictionaries using a common reference string of logarithmic length. The security bound achieved by our protocol is somewhat worse than the GL protocol. Roughly speaking, our protocol guarantees that the adversary can ``break'' the scheme with probability at most $O(\mathrm{poly}(n)/|D|)^{\Omega(1)}$, whereas the GL protocol guarantees a bound of $O(1/|D|)$. We also present an alternative, more natural definition of security than the ``augmented definition'' of Goldreich and Lindell, and prove that the two definitions are equivalent.

A fundamental problem of distributed computing is that of simulating a secure broadcast channel, within the setting of a point-to-point network. This problem is known as Byzantine Agreement (or Generals) and has been the focus of much research. Lamport et al. showed that in order to achieve Byzantine Agreement in the standard model, more than 2/3 of the participating parties must be honest. They further showed that by augmenting the network with a public-key infrastructure for digital signatures, it is possible to obtain protocols that are secure for any number of corrupted parties. The problem in this augmented model is called "authenticated Byzantine Agreement". In this paper we consider the question of concurrent, parallel and sequential composition of authenticated Byzantine Agreement protocols. We present surprising impossibility results showing that: * If an authenticated Byzantine Agreement protocol remains secure under parallel or concurrent composition (even for just two executions), then more than 2/3 of the participating parties must be honest. * Deterministic authenticated Byzantine Agreement protocols that run for $r$ rounds and tolerate 1/3 or more corrupted parties, can remain secure for at most $2r-1$ sequential executions. In contrast, we present randomized protocols for authenticated Byzantine Agreement that remain secure under sequential composition, for {\em any}\/ polynomial number of executions. We exhibit two such protocols. In the first protocol, the number of corrupted parties may be any number less than 1/2 (i.e., an honest majority is required). In the second protocol, any number of parties may be corrupted; however, the overall number of parties must be limited to $O(\log k/\log\log k)$, where $k$ is the security parameter (and so all parties run in time that is polynomial in $k$). Finally, we show that when the model is further augmented so that unique and common session identifiers are assigned to each concurrent session, then any polynomial number of authenticated Byzantine agreement protocols can be concurrently executed, while tolerating any number of corrupted parties.

We present the first efficient Identity-Based Encryption (IBE) scheme that is fully secure without random oracles. We first present our IBE construction and reduce the security of our scheme to the decisional Bilinear Diffie-Hellman (BDH) problem. Additionally, we show that our techniques can be used to build a new signature scheme that is secure under the computational Diffie-Hellman assumption without random oracles.

In threshold ring signature schemes, any group of $t$ entities spontaneously conscripting arbitrarily $n-t$ entities to generate a publicly verifiable $t$-out-of-$n$ signature on behalf of the whole group, yet the actual signers remain anonymous. The spontaneity of these schemes is desirable for ad-hoc groups such as mobile ad-hoc networks. In this paper, we present an identity based (ID-based) threshold ring signature scheme. The scheme is provably secure in the random oracle model and provides trusted authority compatibility. To the best of authors' knowledge, our scheme is the first ID-based threshold ring signature scheme which is also the most efficient (in terms of number of pairing operations required) ID-based ring signature scheme (when $t = 1$) and threshold ring signature scheme from pairings.

We consider the problem of changing the parameters of an established ideal $(k,n)$-threshold scheme without the use of secure channels. We identify the parameters $(k',n')$ to which such a scheme can be updated by means of a broadcast message and then prove a lower bound on the size of the relevant broadcast. The tightness of this bound is demonstrated by describing an optimal procedure for updating the parameters of an ideal scheme.

Threshold schemes allow secret data to be protected amongst a set of participants in such a way that only a pre-specified threshold of participants can reconstruct the secret from private information (shares) distributed to them on system setup using secure channels. We consider the general problem of designing unconditionally secure threshold schemes whose defining parameters (the threshold and the number of participants) can later be changed by using only public channel broadcast messages. In this paper we are interested in the efficiency of such threshold schemes, and seek to minimise storage costs (size of shares) as well as optimise performance in low bandwidth environments by minimising the size of necessary broadcast messages. We prove a number of lower bounds on the smallest size of broadcast message necessary to make general changes to the parameters of a threshold scheme in which each participant already holds shares of minimal size. We establish the tightness of these bounds by demonstrating optimal schemes.

We describe an identity based signature scheme that uses biometric information to construct the public key. Such a scheme would be beneficial in a legal dispute over whether a contract had been signed or not by a user. A biometric reading provided by the alleged signer would be enough to verify the signature. We make use of Fuzzy extractors to generate a key string from a biometric measurement. We use this biometric based key string and an elliptic curve point embedding technique to create the public key and corresponding private key. We then make use of a pairing based signature scheme to perform signing and verification with these keys. We describe a possible attack on this system and suggest ways to combat it. Finally we describe how such a biometric signature scheme can be developed by reusing existing components in our Java Identity Based Encryption implementation. The design allows traditional as well as biometric identity based signatures.

In the mid 1980's, Yao presented a constant-round protocol for securely computing any two-party functionality in the presence of semi-honest adversaries (FOCS 1986). In this paper, we provide a complete description of Yao's protocol, along with a rigorous proof of security. Despite the importance of Yao's protocol to the field of secure computation, to the best of our knowledge, this is the first time that a proof of security has been published.

We construct a short group signature scheme. Signatures in our scheme are approximately the size of a standard RSA signature with the same security. Security of our group signature is based on the Strong Diffie-Hellman assumption and a new assumption in bilinear groups called the Decision Linear assumption. We prove security of our system, in the random oracle model, using a variant of the security definition for group signatures recently given by Bellare, Micciancio, and Warinschi.

We present a fully secure identity based encryption scheme whose proof of security does not rely on the random oracle heuristic. Security is based on the decisional bilinear Diffie-Hellman assumption. Previous constructions of this type incurred a large penalty factor in the security reduction from the underlying complexity assumption. The security reduction of the present system is polynomial in all the parameters.

We construct two efficient Identity Based Encryption (IBE) systems that are selective identity secure {\em without the random oracle model} in groups equipped with a bilinear map. Selective identity secure IBE is a slightly weaker security model than the standard security model for IBE. In this model the adversary must commit ahead of time to the identity that it intends to attack, whereas in the standard model the adversary is allowed to choose this identity adaptively. The first system is based on the decisional bilinear Diffie-Hellman assumption, and extends to give a selective identity Hierarchical IBE secure without random oracles. The second system is based on a related assumption called the bilinear Diffie-Hellman inversion assumption. Applications of either system include an efficient CCA2 public key cryptosystem that supports non-interactive threshold decryption in the standard model, and a simple and practical IBE system that remains secure against full adaptive-ID attacks, under some security penalty, without random oracles.

We describe a short signature scheme which is existentially unforgeable under a chosen message attack without using random oracles. The security of our scheme depends on a new complexity assumption we call the {\em Strong Diffie-Hellman} assumption. This assumption has similar properties to the Strong RSA assumption, hence the name. Strong RSA was previously used to construct signature schemes without random oracles. However, signatures generated by our scheme are much shorter and simpler than signatures from schemes based on Strong RSA. Furthermore, our scheme provides a limited form of message recovery.

A *consistent query protocol* (CQP) allows a database owner to publish a very short string $c$ which *commits* her and everybody else to a particular database $D$, so that any copy of the database can later be used to answer queries and give short proofs that the answers are consistent with the commitment $c$. Here *commits* means that there is at most one database $D$ that anybody can find (in polynomial time) which is consistent with $c$. (Unlike in some previous work, this strong guarantee holds even for owners who try to cheat while creating $c$.) Efficient CQPs for membership and one-dimensional range queries are known \cite{BRW02,K98,MR}: given a query pair $a,b\in \mathbb{R}$, the server answers with all the keys in the database which lie in the interval $[a,b]$ and a proof that the answer is correct. This paper explores CQPs for more general types of databases. We put forward a general technique for constructing CQPs for any type of query, assuming the existence of a data structure/algorithm with certain inherent robustness properties that we define (called a *data robust algorithm*). We illustrate our technique by constructing an efficient protocol for *orthogonal range queries*, where the database keys are points in $\mathbb{R}^d$ and a query asks for all keys in a rectangle $[a_1,b_1]\times\ldots \times [a_d,b_d]$. Our data-robust algorithm is within a $O(\log N)$ factor of the best known standard data structure (a range tree, due to Bentley (1980)). We modify our protocol so that it is also private, that is, the proofs leak no information about the database beyond the query answers. We show a generic modification to ensure privacy based on zero-knowledge proofs, and also give a new, more efficient protocol tailored to hash trees.

One of the driving forces behind the development of 3G systems is the potential to deliver complex content to consumers. This is evident from the growing collaboration between broadcast and mobile network operators, and the expectation that future broadcast receivers will be able to forward content to mobile devices. One challenge in providing such a service is the requirement for content protection. An aspect of this that is particularly relevant to mobile systems is the ability to control where content is viewed. Although 3G networks can provide location of a user’s receiver, this device may be in a different location from the device that renders the content. Thus the provider cannot be certain where the content will be viewed. This paper proposes two protocols that will provide the location of the end device in a secure manner that can be trusted by the content provider.

We think that there are two main attacks on TTM cryptosystem; the Goubin-Courtois attack ([6]) and the Ding-Schmidt attack ([5]). The paper of Goubin-Courtois is not clearly written. Their arguments (with many gaps) depend on an parameter $r$ which is never defined. It is nature to take their parameter $r$ to be the index $s$ used in our "lock polynomials" (see section 1). Later on Courtois implies otherwise in his website. In their paper ([6]) or in his website, Courtois simply declares that TTM is of rank 2 (i.e., $r=2$) without any justification. In this paper, we will illustrate another example (cf Example below) satisfies both requirements, i.e., the index $s$ used in our "lock polynomials" (see section 1) is 7, and the number of variables in all quartic forms is 4 which shows that Goubin-Courtois' unsubstantial claim: "TTM is rank 2" invalid. Thus we settle this question of Goubin-Courtois attack once for all. To guard against "high rank attack", in this Example every variable appears 9 times in 9 different polynomials. On the other hand J.~Ding and D.~Schmidt show ([5]) how to construct an interesting attack on some implementations of TTM ([10,11]) based on Patarin's idea ([14]) of bilinear relations created by the structure in the kernel equations in an implementation of TTM. The success of this attack is accidental. In our Example, the attack fails. we will describe a {\it mixed implementation} which will make any attack, which is sensitive to the size of the ground field, ineffective. In this paper, the Example is strong (i.e., $\geq 2^{148})$ against both Goubin-Courtois attack and Ding-Schmidt attack as well as other previously proposed incomplete attacks like XL($>2^{97}$), FXL($>2^{112}$).

This paper proposes a key exchange protocol with mutual authentication, which requires only 0.1 modular multiplications for online computations. This online computation is ten times faster than that of conventional protocols. The message size of the proposed protocol is about half (50%~66%) that of the previous protocols. In addition to its efficiency in online computation and bandwidth, the paper provides a formal proof to guarantee the security of the proposed protocol. Possessing of both secure and efficient properties makes the proposed protocol suitable for the low power mobile communications.

We revisit the randomized approach followed in the design of the RMAC message authentication code in order to construct a MAC with similar properties, but based on Wegman-Carter's $\varepsilon$-universal hash families instead of a classical CBC chain. This yields a new message authentication code called FRMAC whose security bounds are, as in RMAC, beyond the birthday paradox limit. With efficient hash functions in software, the performance of FRMAC for large messages is similar to those of the fastest previously known schemes. FRMAC can also be more efficient for small messages. Furthermore, due to relaxed requirements about the nonces in the security proof, the implementation of FRMAC in real applications tends to be easier.

We compare both the security and performance issues related to the choice of MNT curves against supersingular curves in characteristic three, for pairing based systems. We pay particular attention to equating the relevant security levels and comparing not only computational performance and bandwidth performance. The paper focuses on the BLS signature scheme and the Boneh--Franklin encryption scheme, but a similar analysis can be applied to many other pairing based schemes.

We present identity-based identification (resp. encryption, signature, blind signature,ring signature) from composite degree residuosity (CDR). Constructions of identifications and signatures motivated by several existing CDR-based bandwidth-efficient encryption schemes are presented. Their securities are proven equivalent to famous hard problems, in the random oracle model. Motivated by Cocks,we construct an identity-based encryption from CDR. Its security is proven equivalent to a new problem, the JSR (Jacobi Symbol of Roots of two quadratic polynomials) Problem. We prove JSR is at least as hard as QRP (Quadratic Residuosity Problem). Furthermore, we present the first two-way equivalence reduction of the security of Cocks' IBE, to the JSR Problem.

In 2002, Chien et al. proposed an efficient remote user authentication scheme using smart cards. Later, in 2004, W. C. Ku and S. M. Chen pointed out some attacks on Chien et al.’s scheme. W. C. Ku and S. M. Chen also proposed a modified scheme to prevent the attacks on Chien et al.’s scheme. This paper discusses the security of the W. C. Ku and S. M. Chen’s scheme. This paper aims to show that the modified scheme is still vulnerable to the password guessing attack and the insider attack.

We consider the scenario where Alice wants to send a secret(classical) $n$-bit message to Bob using a classical key, and where only one-way transmission from Alice to Bob is possible. In this case, quantum communication cannot help to obtain perfect secrecy with key length smaller then $n$. We study the question of whether there might still be fundamental differences between the case where quantum as opposed to classical communication is used. In this direction, we show that there exist ciphers with perfect security producing quantum ciphertext where, even if an adversary knows the plaintext and applies an optimal measurement on the ciphertext, his Shannon uncertainty about the key used is almost maximal. This is in contrast to the classical case where the adversary always learns $n$ bits of information on the key in a known plaintext attack. We also show that there is a limit to how different the classical and quantum cases can be: the most probable key, given matching plain- and ciphertexts, has the same probability in both the quantum and the classical cases. We suggest an application of our results in the case where only a short secret key is available and the message is much longer.

Gaudry present a variation of index calculus attack for solving the DLP in the Jacobian of hyperelliptic curves. Harley and Thériault improve these kind of algorithm. Here, we will present a variation of these kind of algorithm, which is faster than previous ones. Its complexity is $O(2-\frac{2}{g}+\epsilon)$. Recently, P. Gaudry and E. Thomé http://eprint.iacr.org/2004/153/ present the algorithm, whose complexity is same as our results. So I submit my manuscript to this eprint archive.

Traitor Tracing Schemes constitute a very useful tool against piracy in the context of digital content broadcast. In such multi-recipient encryption schemes, each decryption key is fingerprinted and when a pirate decoder is discovered, the authorities can trace the identities of the users that contributed in its construction (called traitors). Public-key traitor tracing schemes allow for a multitude of non-trusted content providers using the same set of keys, which makes the scheme ``server-side scalable.'' To make such schemes also ``client-side scalable,'' i.e. long lived and usable for a large population of subscribers that changes dynamically over time, it is crucial to implement efficient Add-user and Remove-user operations. Previous work on public-key traitor tracing did not address this dynamic scenario thoroughly, and there is no efficient scalable public key traitor tracing scheme that allows an increasing number of Add-user and Remove-user operations. To address these issues, we introduce the model of Scalable Public-Key Traitor Tracing, and present the first construction of such a scheme. Our model mandates for deterministic traitor tracing and an unlimited number of efficient Add-user operations and Remove-user operations. A scalable system achieves an unlimited number of revocations while retaining high level of efficiency by dividing the run-time of the system into periods. Each period has a saturation level for the number of revocations. When a period becomes saturated, an _efficient_ New-period operation is issued by the system server that resets the saturation level. We present a formal adversarial model for our system taking into account its periodic structure, and we prove our construction secure, both against adversaries that attempt to cheat the revocation mechanism as well as against adversaries that attempt to cheat the traitor tracing mechanism.