Recently, Al-Riyami and Paterson proposed four authenticated tripartite key agreement protocols which make use of Weil pairing. In this paper, we show that the protocols are insecure against the man-in-the middle attack, key compromise impersonation attack and several known-key attacks.

We present the first cryptographically sound security proof of the well-known Needham-Schroeder-Lowe public-key protocol. More precisely, we show that the protocol is secure against arbitrary active attacks if it is implemented using provably secure cryptographic primitives. Although we achieve security under cryptographic definitions, our proof does not have to deal with probabilistic aspects of cryptography and is hence in the scope of current proof tools. The reason is that we exploit a recently proposed ideal cryptographic library, which has a provably secure cryptographic implementation. Besides establishing the cryptographic security of the Needham-Schroeder-Lowe protocol, our result also exemplifies the potential of this cryptographic library and paves the way for cryptographically sound verification of security protocols by means of formal proof tools.

Complexity-theoretic cryptography considers only abstract notions of computation, and hence cannot protect against attacks that exploit the information leakage (via electromagnetic fields, power consumption, etc.) inherent in the physical execution of any cryptographic algorithm. Such "physical observation attacks" bypass the impressive barrier of mathematical security erected so far, and successfully break mathematically impregnable systems. The great practicality and the inherent availability of physical attacks threaten the very relevance of complexity-theoretic security. To respond to the present crisis, we put forward physically observable cryptography: a powerful, comprehensive, and precise model for defining and delivering cryptographic security against an adversary that has access to information leaked from the physical execution of cryptographic algorithms. Our general model allows for a variety of adversaries. In this paper, however, we focus on the strongest possible adversary, so as to capture what is cryptographically possible in the worst possible, physically observable setting. In particular, we -- consider an adversary that has full (and indeed adaptive) access to any leaked information; -- show that some of the basic theorems and intuitions of traditional cryptography no longer hold in a physically observable setting; and -- construct pseudorandom generators that are provably secure against all physical-observation attacks. Our model makes it easy to meaningfully restrict the power of our general physically observing adversary. Such restrictions may enable schemes that are more efficient or rely on weaker assumptions, while retaining security against meaningful physical observations attacks.

The use of FPGAs for cryptographic applications is highly attractive for a variety of reasons but at the same time there are many open issues related to the general security of FPGAs. This contribution attempts to provide a state-of-the-art description of this topic. First, the advantages of reconfigurable hardware for cryptographic applications are discussed from a systems perspective. Second, potential security problems of FPGAs are described in detail, followed by a proposal of a some countermeasure. Third, a list of open research problems is provided. Even though there have been many contributions dealing with the algorithmic aspects of cryptographic schemes implemented on FPGAs, this contribution appears to be the first comprehensive treatment of system and security aspects.

In this paper we describe a low-tech and user friendly solution for secure two-way communication between two parties over a network of untrusted devices. We present a solution in which displays play a central role. Our approach guarantees privacy and allows to check the authenticity of information presented on displays. Furthermore, we provide the user with a secure return channel. To this end we propose to provide every user with a small decryption display which is, for example, integrated in a credit card and requires very limited computing power. The authentication and security are based on visual cryptography which was first introduced by Naor and Shamir in 1994. We solve some practical shortcomings of traditional visual cryptography and develop protocols for two-way authentication and privacy in untrusted environments.

At the conference Asiacrypt 2001, Rivest, Shamir and Tauman firstly addressed the concept of ring signature. In this paper we propose an identity-based ring signature scheme from bilinear pairings. As compared with the Zhang-Kim scheme (presented at the conference Asiacrypt 2002), our scheme is more efficient in computation and requires fewer pairing operations.

We argue that traditional ID-based systems from pairings seem unsuitable for designing group signature schemes due to the problem of key escrow. In this paper we propose new ID-based public key systems without trustful KGC from bilinear pairings. In our new ID-based systems, if dishonest KGC impersonates an honest user to communicate with others, the user can provide a proof of treachery of the KGC afterwards, which is similar to CA-based systems. Furthermore, we propose a group signature scheme under the new systems, the security and performance of which rely on the new systems. The size of the group public key and the length of the signature are independent on the numbers of the group.

In this paper, we show that the Nalla-Reddy's one round ID-based tripartite authenticated key agreement protocols are still insecure against the man-in-the-middle attacks. We also break the Nalla's ID-based tripartite authenticated key agreement protocol with signatures.

The cryptographic concept of simulatability has become a salient technique for faithfully analyzing and proving security properties of arbitrary cryptographic protocols. We investigate the relationship between simulatability in synchronous and asynchronous frameworks by means of the formal models of Pfitzmann et. al., which are seminal in using this concept in order to bridge the gap between the formal-methods and the cryptographic community. We show that the synchronous model can be seen as a special case of the asynchronous one with respect to simulatability, i.e., we present an embedding between both models that we show to preserve simulatability. We show that this result allows for carrying over lemmas and theorems that rely on simulatability from the asynchronous model to its synchronous counterpart without any additional work. Hence future work can concentrate on the more general asynchronous case, without having to neglect the analysis of synchronous protocols.

Recently, Shim proposed a tripartite authenticated key agreement protocol from Weil pairing to overcome the security flaw in Joux's protocol. Later, Shim also proposed an ID-based authenticated key agreement protocol which is an improvement of Smart's protocol in order to provide the forward secrecy. In this paper, we show that these two protocols are insecure against the key-compromise impersonation attack and the man-in-the-middle attack respectively.

Constructing practical and provably secure group signature schemes has been a very active research topic in recent years. A group signature can be viewed as a digital signature with certain extra properties. Notably, anyone can verify that a signature is generated by a legitimate group member, while the actual signer can only be identified (and linked) by a designated entity called a group manager. Currently, the most efficient group signature scheme available is due to Camenisch and Lysyanskaya \cite{CL02}. It is obtained by integrating a novel dynamic accumulator with the scheme by Ateniese, et al. \cite{ACJT00}. In this paper, we construct a dynamic accumulator that accumulates \emph{composites}, as opposed to previous accumulators that accumulated \emph{primes}. We also present an efficient method for proving knowledge of factorization of a committed value. Based on these (and other) techniques we design a novel provably secure group signature scheme. It operates in the \emph{common auxiliary string} model and offers two important benefits: 1) the {\sf Join} process is very efficient: a new member computes only a single exponentiation, and 2) the (unoptimized) cost of generating a group signature is 17 exponentiations which is appreciably less than the state-of-the-art.

Proxy signature is a signature that an original signer delegates his or her signing capability to a proxy signer, and then the proxy signer creates a signature on behalf of the original signer. However, Sun et al.[7] showed that the proxy and multi-proxy signatures of Lee et al.[3], and the strong proxy signature scheme with proxy signer privacy protection of Shum et al.[6] are not against the original signer's forgery attack, so these schemes do not process the property of unforgeability. In this paper, we present an extensive forgery method on these schemes, which makes the forgery method of Sun et al.be a special case of ours.

Biometric personal authentication systems have a common problem --- the biological information can easily be stolen by other individuals. In line with the process of the activities for the international standardization of the biometric system, this paper proposes a typical way to embed biological information, whatever its kind, into cryptographic keys as a measure for privacy protection and against unauthorized use. We believe that our proposal presents the following advantages: the improvement of protecting the privacy of biological information, economical effectiveness resulting from the practical use of the infrastructure of Public Key Infrastructure (PKI) as a biological information database, and humanity given to a man-machine interface by embedding an individual's biological information into a public key, an important element of the system. This paper also proposes how to build up a practical personal authentication system through the method proposed.

This paper presents several multiset and boomerang attacks on SAFER++ up to 5.5 out of its 7 rounds. These are the best known attacks for this cipher and significantly improve the previously known results. The attacks in the paper are practical up to 4 rounds. The methods developed to attack SAFER++ can be applied to other substitution-permutation networks with incomplete diffusion.

Rijndael, or the Advanced Encryption Standard, is an interesting cipher from a designer's viewpoint. Over the last few decades, the most notable, and successful attacks against the best block ciphers were linear and differential cryptanalysis. On the other hand, Rijndael is designed from the ground up to resist these attacks, as well as many others, by employing special algebraic properties of its primitive operations. The byte inversion operation over finite field $\mathbb{F}_{256}$ was chosen by its designer to thwart all possibly useful linear and difference invariances, the basic ingredients of linear and differential cryptanalysis. However, by using simple algebraic operations with known properties, the combinations of them may possess many interesting, and unexpected, algebraic properties that were not known at design time. This paper presents such new unknown properties on the combinations of primitive operations of AES.

At Crypto'99, Fujisaki and Okamoto~\cite{FO99} presented a nice generic transformation from weak asymmetric and symmetric schemes into an IND-CCA hybrid encryption scheme in the Random Oracle Model. From this transformation, two specific candidates to standardization were designed: EPOC-2~\cite{EPOC} and PSEC-2~\cite{PSEC}, based on Okamoto-Uchiyama and El Gamal primitives, respectively. Since then, several cryptanalysis of EPOC have been published, one in the Chosen Ciphertext Attack game and others making use of a poor implementation that is vulnerable to reject timing attacks. The aim of this work is to avoid these attacks from the generic transformation, identifying the properties that an asymmetric scheme must hold to obtain a secure hybrid scheme. To achieve this, some ambiguities in the proof of the generic transformation~\cite{FO99} are described, which can lead to false claims. As a result the original conversion is modified and the range of asymmetric primitives that can be used is shortened. In second place, the concept of {\it Easy Verifiable Primitive} is formalized, showing its connection with the Gap problems. Making use of these ideas, a {\it new} security proof for the modified transformation is given. The good news is that the reduction is {\it tight}, improving the concrete security claimed in the original work for the Easy Verifiable Primitives. For the rest of primitives the concrete security is improved at the cost of stronger assumptions. Finally, the resistance of the new conversion against reject timing attacks is addressed.

We introduce CWC, a new block cipher mode of operation for protecting both the privacy and the authenticity of encapsulated data. CWC is currently the only such mode having all five of the following properties: provable security, parallelizability, high performance in hardware, high performance in software, and no intellectual property concerns. We believe that having all five of these properties makes CWC a powerful tool for use in many performance-critical cryptographic applications. CWC is also the only appropriate solution for some applications; e.g., standardization bodies like the IETF and NIST prefer patent-free modes, and CWC is the only such mode capable of processing data at 10Gbps in hardware, which will be important for future IPsec (and other) network devices. As part of our design, we also introduce a new parallelizable universal hash function optimized for performance in both hardware and software.

We show how to construct practical honest-verifier statistical zero-knowledge \emph{Diophantine} arguments of knowledge (HVSZK AoK) that a committed tuple of integers belongs to an arbitrary language in bounded arithmetic. While doing this, we propose a new algorithm for computing the Lagrange representation of nonnegative integers and a new efficient representing polynomial for the exponential relation. We apply our results by constructing the most efficient known HVSZK AoK for non-negativity and the first constant-round practical HVSZK AoK for exponential relation. Finally, we propose the outsourcing model for cryptographic protocols and design communication-efficient versions of the Damgård-Jurik multi-candidate voting scheme and of the Lipmaa-Asokan-Niemi $(b+1)$st-price auction scheme that work in this model.

Proxy signatures are very useful tools when one needs to delegate his/her signing capability to other party. After Mambo $et\ al.$'s first scheme was announced, many proxy signature schemes and various types of proxy signature schemes have been proposed. Due to the various applications of the bilinear pairings in cryptography, there are many ID-based signature schemes have been proposed. In this paper, we address that it is easy to design proxy signature and proxy blind signature from the conventional ID-based signature schemes using bilinear pairings, and give some concrete schemes based on existed ID-based signature schemes. At the same time, we introduce a new type of proxy signature -- proxy ring signature, and propose the first proxy ring signature scheme based on an existed ID-based ring signature scheme.

In this paper we propose security analysis on passive attack for Nalla-Reddy's ID-AK-2 and ID-AK-3 protocols.

In this note, we describe a probabilistic attack on public key cryptosystems based on the word/conjugacy problems for finitely presented groups of the type proposed recently by Anshel, Anshel and Goldfeld. In such a scheme, one makes use of the property that in the given group the word problem has a polynomial time solution, while the conjugacy problem has no known polynomial solution. An example is the braid group from topology in which the word problem is solvable in polynomial time while the only known solutions to the conjugacy problem are exponential. The attack in this paper is based on having a canonical representative of each string relative to which a length function may be computed. Hence the term length attack. Such canonical representatives are known to exist for the braid group.

Out of the public key ($\mathcal{PK}$) we recover a polynomial of the same shape as the private polynomial. Then we give an algorithm for solving such a special-form polynomial. This fact puts an eavesdropper in the same position with a legitimate user in decryption. An upper bound for the complexity of that all is $\mathcal{O}(n^6)$ bit operations for $n$ the degree of the field extension.

Until recently, most research on the topic of secure computation focused on the stand-alone model, where a single protocol execution takes place. In this paper, we construct protocols for the setting of {\em bounded-concurrent self composition}, where a (single) secure protocol is run many times concurrently, and there is a predetermined bound on the number of concurrent executions. In short, we show that {\em any} two-party functionality can be securely computed under bounded-concurrent self composition, in the {\sf plain model} (where the only setup assumption made is that the parties communicate via authenticated channels). Our protocol provides the first feasibility result for general two-party computation in the plain model, {\em for any model of concurrency}. All previous protocols assumed a trusted setup phase in order to obtain a common reference string. On the downside, the number of rounds of communication in our protocol is super-linear in the bound on the number of concurrent executions. However, we believe that our constructions will lead to more efficient protocols for this task.

Braid Groups have recently been considered for use in Public-Key Cryptographic Systems. The most notable of these system has been the Birman-Ko-Lee system presented at Crypto 2000. This article gives a brief introduction into braid groups and the hard problems on which public key systems have been defined. It suggests a canonical form max run form using the Artin generators and supplies some supporting algorithms necessary for cryptographic operations.

Vaudenay has shown in [5] that a CBC encryption mode ([2], [9]) combined with the PKCS#5 padding [3] scheme allows an attacker to invert the underlying block cipher, provided she has access to a valid-padding oracle which for each input ciphertext tells her whether the corresponding plaintext has a valid padding or not. Having on mind the countermeasures against this attack, different padding schemes have been studied in [1]. The best one is referred to as the ABYT-PAD. It is designed for byte-oriented messages. It removes the valid-padding oracle, thereby defeating Vaudenay's attack, since all deciphered plaintexts are valid in this padding scheme. In this paper, we try to combine the well-known cryptographic message syntax standard PKCS#7 [8] with the use of ABYT-PAD instead of PKCS#5. Let us assume that we have access to a PKCS#7CONF oracle that tells us for a given ciphertext (encapsulated in the PKCS#7 structure) whether the deciphered plaintext is correct or not according to the PKCS#7 (v1.6) syntax. This is probably a very natural assumption, because applications usually have to reflect this situation in its behavior. It could be a message for the user, an API error message, an entry in the log file, different timing behavior, etc. We show that access to such an oracle again enables an attacker to invert the underlying block cipher. The attack requires single captured ciphertext and approximately 128 oracle calls per one ciphertext byte. It shows that we cannot hope to fully solve problems with side channel attacks on the CBC encryption mode by using a “magic” padding method or an obscure message-encoding format. Strong cryptographic integrity checks of ciphertexts should be incorporated instead.

It is widely believed that genus four hyperelliptic curve cryptosystems (HECC) are not attractive for practical applications because of their complexity compared to systems based on lower genera, especially elliptic curves. Our contribution shows that for low cost security applications genus-4 hyperelliptic curves (HEC) can outperform genus-2 HEC and that we can achieve a performance similar to genus-3 HEC. Furthermore our implementation results show that a genus-4 HECC is an alternative cryptosystem to systems based on elliptic curves. In the work at hand we present for the first time explicit formulae for genus-4 HEC, resulting in a 60% speed-up compared to the best published results. In addition we implemented genus-4 HECC on a Pentium4 and an ARM microprocessor. Our implementations on the ARM show that for genus four HECC are only a factor of 1.66 slower than genus-2 curves considering group order ~2^{190}. For the same group order ECC and genus-3 HECC are about a factor of 2 faster than genus-4 curves on the ARM. The two most surprising results are: 1) for low cost security application, namely considering an underlying group of order 2^{128}, HECC with genus 4 outperform genus-2 curves by a factor of 1.46 and has similar performance to genus-3 curves on the ARM and 2) when compared to genus-2 and genus-3, genus-4 HECC are better suited to embedded microprocessors than to general purpose processors.

A proxy signature scheme permits an entity to delegate its signing rights to another entity. These schemes have been suggested for use in numerous applications, particularly in distributed computing. But to date, no proxy signature schemes with guaranteed security have been proposed; no precise definitions or proofs of security have been provided for such schemes. In this paper, we formalize a notion of security for proxy signature schemes and present provably-secure schemes. We analyze the security of the well-known delegation-by-certificate scheme and show that after some slight but important modifications, the resulting scheme is secure, assuming the underlying standard signature scheme is secure. We then show that employment of the recently introduced aggregate signature schemes permits bandwidth and computational savings. Finally, we analyze the proxy signature scheme of Kim, Park and Won, which offers important performance benefits. We propose modifications to this scheme that preserve its efficiency, and yield a proxy signature scheme that is provably secure in the random-oracle model, under the discrete-logarithm assumption.

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

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

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

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

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

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

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

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

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

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

We show all the existing TTM implementation schemes have a defect that there exist linearization equations $$ \sum_{i=1,j=1}^{n,m} a_{ij}x_iy_j(x_1,\dots,x_{n})+ \sum_{i=1}^{n} b_ix_i+\sum_{j=1}^{m} c_jy_j(x_1,\dots,x_{n}) + d= 0, $$ which are satisfied by the components $y_i(x_1,\dots,x_n)$ of the ciphers of the TTM schemes. We further demonstrate that, for the case of the most recent two implementation schemes in two versions of the paper \cite{CM}, where the inventor of TTM used them to refute a claim in \cite{CG}, if we do a linear substitution with the linear equations derived from the linearization equations for a given ciphertext, we can find the plaintext easily by an iteration of the procedure of first search for linear equations by linear combinations and then linear substitution. The computation complexity of the attack on these two schemes is less than $2^{35}$ over a finite field of size $2^8$.

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

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

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

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

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

In this paper we present a fast addition algorithm in the Jacobian of a Picard curve over a finite field $\mathbb F _q$ of characteristic different from $3$. This algorithm has a nice geometric interpretation, comparable to the classic "chord and tangent" law for the elliptic curves. Computational cost for addition is $144M + 12SQ + 2I$ and $158M + 16SQ + 2I$ for doubling.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

We present a secure unauthenticated as well as an authenticated multi party key agreement protocol. The unauthenticated version of our protocol uses ternary trees and is based on bilinear maps and Joux's three party protocol. The number of rounds, computation/communication complexity of our protocol compares favourably with previously known protocols. The authenticated version of our protocol also uses ternary trees and is based on public IDs and Key Generation Centres. The authenticated version of our protocol is more efficient than all previously known authenticated key agreement protocols.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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