We present an attack on DSA smart-cards which combines physical fault injection and lattice reduction techniques. This seems to be the first (publicly reported) physical experiment allowing to concretely pull-out DSA keys out of smart-cards. We employ a particular type of fault attack known as a glitch attack, which will be used to actively modify the DSA nonce k used for generating the signature: k will be tampered with so that a number of its least significant bytes will flip to zero. Then we apply well-known lattice attacks on El Gamal-type signatures which can recover the private key, given sufficiently many signatures such that a few bits of each corresponding k are known. In practice, when one byte of each k is zeroed, 27 signatures are sufficient to disclose the private key. The more bytes of k we can reset, the fewer signatures will be required. This paper presents the theory, methodology and results of the attack as well as possible countermeasures.

The currently known constructions of Boolean functions with high nonlinearities, high algebraic degrees and high resiliency orders do not seem to permit achieving sufficiently high algebraic immunities. We introduce a construction of Boolean functions, which builds a new function from three known ones. Assuming that the three functions have some resiliency order, nonlinearity and algebraic degree, as well as their sum modulo 2, the constructed function has the same resiliency order and can have the same nonlinearity, but has potentially better algebraic degree and algebraic immunity. The set of classical constructions together with this new one (and with a simpler derived one, having the same advantages) permit now to obtain functions achieving all necessary criteria for being used in the pseudo-random generators in stream ciphers.\\ We also apply this construction to obtain bent functions from known ones.

Bribe and coercion are common in conventional voting systems and usually will lead to a biased result that imparts the desired democracy. However, these problems become more difficult to solve when using e-voting schemes. Up to now, many e-voting schemes have been proposed to provide receipt-freeness and uncoercibility to solve these problems. Unfortunately, none is both secure and practical enough. In this paper, we describe an e-voting scheme that can solve or at least lessen the problems of bribe and coercion, and can be realized with current techniques. By using smart cards to randomize part content of the ballot, the voter can not construct a receipt. By using physical voting booths, bribers and coercers can not monitor the voter while he votes. Unlike conventional voting systems, the voter of the proposed scheme can choose any voting booth that is convenient and safe to him. Furthermore, the performance of the proposed schemes is optimal in that time and communication complexity for the voter is independent of the number of voting authorities.

By the relationship between the Walsh spectra at partial points and the Walsh spectra of its sub-functions, by the action of general linear group on the set of Boolean functions, and by the Reed-Muller transform, a novel method is developed, which can theoretically construct all bent functions. With this method, we enumerate all bent functions in 6 variables; in 8-variable case, our method is more efficient than the method presented by Clark though we still can not enumerate all bent functions; enumeration of all homogeneous bent functions of degree 3 in eight variables can be done in one minute by a P4 1.7G HZ computer; construction of homogenous bent function of degree 3 in 10 variables is efficient too; the nonexistence of homogeneous bent functions in 10 variables of degree 4 is proved

In [1], Li et al. proposed a new type of signature scheme, called the $(t,n)$ threshold-mutisignature scheme. The first one needs a mutually trusted share distribution center (SDC) while the second one does not. In this paper, we present a security analysis on their second schemes. We point out that their second threshold-multisignature scheme is vulnerable to universal forgery by an insider attacker under reasonable assumptions. In our attack, $(n-t+1)$ colluding members can control the group secret key. Therefore, they can generate valid threshold-multisignautre for any message without the help of other members. Furthermore, honest members cannot detect this security flaw in the system, since any $t$ members can generate threshold-multisignatures according to the prescribed protocols.

In this note we introduce a variation of the standard definition of chosen-ciphertext security, which we call IND-CCA3, and prove that IND-CCA3 is equivalent to authenticated-encryption.

Mundja is a MAC generation algorithm that has been designed for use together with a stream cipher. Mundja accumulates the message onto two independent registers: the first is a Cyclic Redundancy Checksum (CRC) that uses linear feedback; the second is a strengthened version of the SHA-256 register that uses nonlinear feedback. Mundja is fast (asymptotically about 4 times the speed of HMAC-SHA-256), and can generate MACs of any desired length. Mundja is designed to be secure at the equivalent level of 128-bit keys. When used in cooperation with a correspondingly secure stream cipher, it is hoped to remain secure even at the equivalent level of 256-bit keys. Appendices give details of the use of Mundja with the SOBER-128, Turing and RC4 stream ciphers.

An enhanced authentication key exchange protocol was proposed to exchange multiple session keys between two participants at a time. This paper shows that this enhanced protocol is insecure under the known session key attack, known long-term private key attack, signature forgery attack, and replay attack. This paper also proposes an enhanced and secure key agreement protocol for exchanging multiple session keys in one run of the protocol. The protocol is secure against the attacks mentioned above. Besides, a formal proof is given to guarantee the security of the proposed protocol under other potential attacks.

In [1], Li et al. proposed a new type of signature scheme, called the $(t,n)$ threshold-mutisignature scheme. The first one needs a mutually trusted share distribution center (SDC) while the second one does not. In this paper, we present a security analysis on their second schemes. We point out that their second threshold-multisignature scheme is vulnerable to universal forgery by an insider attacker under reasonable assumptions. In our attack, $(n-t+1)$ colluding members can control the group secret key. Therefore, they can generate valid threshold-multisignautre for any message without the help of other members. Furthermore, honest members cannot detect this security flaw in the system, since any $t$ members can generate threshold-multisignatures according to the prescribed protocols.

Wang et al. recently proposed an improved edition based on Tseng-Jan group signature scheme${}^{[1]}$. In the paper, we show that the scheme is untraceable by a simple attack.

A ring signature scheme is a group signature scheme with no group manager to setup a group or revoke a signer. A linkable ring signature, introduced by Liu, et al. \cite{LWW04}, additionally allows anyone to determine if two ring signatures are signed by the same group member (a.k.a. they are \emph{linked}). In this paper, we present the first separable linkable ring signature scheme, which also supports an efficient thresholding option. We also present the security model and reduce the security of our scheme to well-known hardness assumptions. In particular, we introduce the security notions of {\em accusatory linkability} and {\em non-slanderability} to linkable ring signatures. Our scheme supports ``event-oriented'' linking. Applications to such linking criterion is discussed.

This paper introduces a new radix-2 representation with the same average weight as the width-$w$ nonadjacent form ($w$-NAF). In both $w$-NAF and the proposed representations, each nonzero digit is an odd integer with absolute value less than $M$. However, for $w$-NAF, $M$ is of the form $2^{w-1}$, while for the proposed representation it can be any positive integer. Therefore, using the proposed integer representation we can use the available memory efficiently, which is attractive for devices with limited memory. Another advantage of the proposed representation over $w$-NAF is that it can be obtained by scanning the bits from left-to-right. This property is also useful for memory-constrained devices because it can reduce both time and space complexityof fast point multiplication techniques.

Distributed control systems (DCS) and supervisory control and data acquisition (SCADA) systems were developed to reduce labor costs, and to allow system-wide monitoring and remote control from a central location. Control systems are widely used in critical infrastructures such as electric grid, natural gas, water, and wastewater industries. While control systems can be vulnerable to a variety of types of cyber attacks that could have devastating consequences, little research has been done to secure the control systems. This paper presents a suite of security protocols optimized for SCADA/DCS systems which include: point-to-point secure channels, authenticated broadcast channels, authenticated emergency channels, and revised authenticated emergency channels. These protocols are designed to address the specific challenges that SCADA systems have.

Wang et al. caused great excitement at CRYPTO2004 when they announced a collision for MD5~\cite{R92_MD5}. This paper is examines the internal differences and conditions required for the attack to be successful. There are a large number of conditions that must be satisfied, thus indicating Wang at al. have found a clever way to generate message pairs for which the conditions are satisfied. The large number of conditions suggests that an attacker cannot use these differentials to cause second pre-image attacks with complexity less than generic attacks. Initial examination also suggests that an attacker cannot cause such collisions for HMAC-MD5 with complexity less than generic attacks.

In this article, we investigate the class of multivariate quadratic (\MQ) public key systems. These systems are becoming a serious alternative to RSA or ECC based systems. After introducing the main ideas and briefly sketching some relevant systems, we deal with the advantages and disadvantages of these kind of schemes. Based on our observations, we determine application domains in which \MQ-schemes have advantages over RSA or ECC. We concentrate on product activation keys, electronic stamps and fast one-way functions.

Duc et al. proposed a forward-secure blind signature scheme in [1]. They claimed that the scheme is constructed from the provably secure Okamoto-Guilou-Quisquater blind signature scheme. But we recently found that their scheme is insecure. In the paper, we show the scheme is universally forgeable by a simple and direct attack.

Recently, Canetti, Halevi, and Katz showed a general method for constructing CCA-secure encryption schemes from identity-based encryption schemes in the standard model. We improve the efficiency of their construction, and show two specific instantiations of our resulting scheme which offer the most efficient encryption (and, in one case, key generation) of any CCA-secure encryption scheme to date.

This paper considers the fundamental problem of key agreement among a group of parties communicating over an insecure public network. Over the years, a number of solutions to this problem have been proposed with varying degrees of complexity. However, there seems to have been no previous systematic look at the growing problem of key agreement over combined wired/wireless networks, consisting of both high-performance computing machines and low-power mobile devices. In this paper we present an efficient group key agreement scheme well suited for this networking environment. Our construction is intuitively simple, and yet offers a scalable solution to the problem.

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.