We describe and prove (in the random-oracle model) the security of a simple but efficient zero-knowledge identification scheme, whose security is based on the computational Diffie-Hellman problem. Unlike other recent proposals for efficient identification protocols, we don't need any additional assumptions, such as the Knowledge of Exponent assumption. From this beginning, we build a simple key-exchange protocol, and prove that it achieves `SK-security' -- and hence security in Canetti's Universal Composability framework. Finally, we show how to turn the simple key-exchange protocol into a slightly more complex one which provides a number of valuable `real-life' properties, without damaging its security.

Group key exchange (GKE) protocols can be used to guarantee confidentiality and group authentication in a variety of group applications. The notion of provable security subsumes the existence of an abstract formalization (security model) that considers the environment of the protocol and identifies its security goals. The first security model for GKE protocols was proposed by Bresson, Chevassut, Pointcheval, and Quisquater in 2001, and has been subsequently applied in many security proofs. Their definitions of AKE- and MA-security became meanwhile standard. In this paper we analyze the BCPQ model and some of its later appeared modifications and identify several security risks resulting from the technical construction of this model – the notion of partnering. Consequently, we propose a revised model with extended definitions for AKE- and MA-security capturing, in addition, attacks of malicious protocol participants. Further, we analyze some well-known generic solutions (compilers) for AKE- and MA-security of GKE protocols proposed based on the definitions of the BCPQ model and its variants and identify several limitations resulting from the underlying assumptions. In order to remove these limitations and at the same time to show that our revised security model is in fact practical enough for the construction of reductionist security proofs we describe a modified compiler which provides AKE- and MA-security for any GKE protocol, under standard cryptographic assumptions.

The authors propose a new type of hash iterative structure ─ the ring-iterative structure with feedback which is subdivided into the single feedback ring iteration and the multiple feedback ring iteration, namely SFRI and MFRI. Prove that SFRI is at least equivalent to the MD structure in security, and MFRI is at least equivalent to SFRI in security (property 1 makes people incline to believe MFRI is more secure than MD). Analyze the resistance of MFRI, which results from the joint event on message modification, endless loop on message modification and incompatibility of the sufficient conditions, to the multi-block differential collision attack. Argue the ineffectiveness of the D-way second preimage attack on MFRI. Discuss the time and space expenses of MFRI, and point out the advantage of MFRI over the tree-iterative structure and the zipper-iterative structure.

Traitor tracing schemes are used to fight piracy when distributing securely some data to multiple authorized receivers: if some receivers collude and share their decryption keys to build some pirate decoder, a tracing procedure should be able to find at least one of these ``traitors'' from the pirate decoder. In this paper, we consider powerful pirate decoders, which may sometimes refuse to decrypt, or may try to detect when the tracing procedure is running. Most known traitor tracing schemes are not secure against this kind of pirate decoders: this is in particular the case of the schemes with constant ciphertext rate, which are the most efficient ones. We build then a new scheme, with constant ciphertext rate and security against powerful pirate decoders, using watermarking techniques. This scheme has the interesting feature that a receiver may decrypt the ciphertexts progressively, when it was not possible in previous schemes with constant ratio between ciphertext and plaintext.

We propose a protection framework for resource sharing to promote cooperation among nodes in multi-hop wireless networks. In the resource sharing protocol, a node claims credits when it relays others' packets. A node also issues rewards to the node which relays its packets. Rewards are used to validate the correctness of credits. In order to protect credits and rewards, we devise a secure registry scheme that supports the timed test of credit validation, and then prove that the scheme is not susceptible to various security attacks. Without any trusted authority in the operation of the framework, we make cryptographic definitions for the scheme, construct a provably secure registry scheme, and implement the timed test of credit validation with one-way chains. Finally, simulation results observed in J-Sim simulator corroborate that resource sharing is correctly supported and that credits and rewards are secured from selfish behaviors.

The total computation of the generation and verification of personnel identification or digital signature is heavy. For many schemes of them, the total computation is not less than hundreds of modular multiplications. Efficient schemes of personnel identification and digital signature were proposed, which require no more than 10 modular multiplications on generation and verification of challenge-response or digital signature. However, the schemes are weak in security. The paper will show that by interception of a transcript of communications between the prover and verifier, the private key of the prover is revealed.

The goal of a sovereign join operation is to compute a query across independent database relations such that nothing beyond the join results is revealed. Each relation involved in a sovereign join is owned by a distinct entity and the party posing the query is distinct from the relation owners; it is not permitted to access the original relations. One notable recent research result proposed a secure technique for executing sovereign joins. It entails data owners sending their relations to an independent database service provider which executes a sovereign join with the aid of a tamper-resistant secure coprocessor. This achieves the goal of preventing information leakage during query execution. However, as we show in this paper, the proposed technique is actually insecure as it fails to prevent an attacker from learning the query results. We also suggest some measures to remedy the security problems.

The NIST codebook-based deterministic random bit generators are analyzed in the context of being indistinguishable from random. Upper and lower bounds based on the probability of distinguishing the output are proven. These bounds imply that the security of the designs are bounded by the codebook width, or more precisely on the property that the codebooks act like a random permutation, as opposed to their underlying security parameter or key length. This paper concludes that these designs fail to support security parameters larger than the codebook width.

We present a new key exchange primitive based on the decomposition problem over non-commutative groups. Different from the key establishment schemes that rely on the decomposition problem where the problem is decomposing an element into three parts where the middle piece is known, our scheme relies on decomposing an element into three parts, all unknown. We call this problem "Triple Decomposition Problem". This seems to be a harder problem because it requires quadratic systems to be solved instead of linear systems. We discuss the new primitive over two different protocols. The underlying problems in the two protocols differ slightly. We discuss the system and the underlying problems in one of the protocols in detail over braid groups. We manage to provide a setting which resists against linear algebra attacks and length based attacks.

We propose new instantiations of chosen-ciphertext secure identity-based encryption schemes with wildcards (WIBE). Our schemes outperform all existing alternatives in terms of efficiency as well as security. We achieve these results by extending the hybrid encryption (KEM--DEM) framework to the case of WIBE schemes. We propose and prove secure one generic construction in the random oracle model, and one direct construction in the standard model.

In this paper, we present new security proofs of well-known hash constructions NMAC/HMAC proposed by Bellare et al. in 1996. We show that block ciphers should be used in hash functions in another way than it has been so far. We introduce a new cryptographic primitive called special block cipher (SBC) which is resistant to attacks specific for block ciphers used in hash functions. We propose to use SBC in the NMAC/HMAC constructions, what gives rise to the new concept of hash functions called Special NMAC (SNMAC). From our new NMAC/HMAC security proofs it follows that SNMAC hash functions are computationally resistant to preimage and collision attacks. Moreover, at CRYPTO 2005 Coron et al. proved that SNMAC is indifferentiable from a random oracle in the limit. SNMAC construction is general and it enables various proposals using different instances of the special block ciphers. We propose a special block cipher DN (Double Net) and define hash function HDN (Hash Double Net) as the SNMAC construction based on DN.

Distortion maps are a useful tool for pairing based cryptography. Compared with elliptic curves, the case of hyperelliptic curves of genus $g > 1$ is more complicated since the full torsion subgroup has rank $2g$. In this paper we prove that distortion maps always exist for supersingular curves of genus $g>1$ and we give several examples in genus $2$.

This paper describes an algorithm to attack AES using side-channel information from the final round cache lookups performed by the encryption, specifically whether each access hits or misses in the cache, building off of previous work by Aciicmez and Koc. It is assumed that an attacker could gain such a trace through power consumption analysis or electromagnetic analysis. This information has already been shown to lead to an effective attack. This paper interprets cache trace data available as binary constraints on pairs of key bytes then reduces key search to a constraint-satisfaction problem. In this way, an attacker is guaranteed to perform as little search as is possible given a set of cache traces, leading to a natural tradeoff between online collection and offline processing. This paper also differs from previous work in assuming a partially pre-loaded cache, proving that cache trace attacks are still effective in this scenario with the number of samples required being inversely related to the percentage of cache which is pre-loaded.

Certificateless Public Key Cryptography (CL-PKC) enjoys a number of features of Identity-Based Cryptography (IBC) while without having the problem of key escrow. However, it \textit{does} suffer to an attack where the adversary, Carol, replaces Alice's public key by someone's public key so that Bob, who wants to send an encrypted message to Alice, uses Alice's identity and other's public key as the inputs to the encryption function. As a result, Alice cannot decrypt the message while Bob is unaware of this. We call it \textit{Denial-of-Decryption (DoD) Attack} as its nature is similar to the well known Denial-of-Service (DoS) Attack. Based on CL-PKC, we propose a new paradigm called \textit{Self-Generated-Certificate Public Key Cryptography (SGC-PKC)} that captures the DoD Attack. We also provide a generic construction of a self-generated-certificate public key encryption scheme in the standard model. Our generic construction uses certificateless signature and certificateless encryption as the building block. In addition, we further propose a certificateless signature and a certificateless encryption scheme with concrete implementation that are all provably secure in the standard model, which are the first in the literature regardless of the generic constructions by Yum and Lee which may contain security weaknesses as pointed out by others. We believe these concrete implementations are of independent interest.

Elliptic curves with small embedding degree and large prime-order subgroup are key ingredients for implementing pairing-based cryptographic systems. Such "pairing-friendly" curves are rare and thus require specific constructions. In this paper we give a single coherent framework that encompasses all of the constructions of pairing-friendly elliptic curves currently existing in the literature. We also include new constructions of pairing-friendly curves that improve on the previously known constructions for certain embedding degrees. Finally, for all embedding degrees up to 50, we provide recommendations as to which pairing-friendly curves to choose to best satisfy a variety of performance and security requirements.

Recently, there have been many proposals for secure and novel cryptographic protocols that are built on bilinear pairings. The $\eta_T$ pairing is one such pairing and is closely related to the Tate pairing. In this paper we consider the efficient hardware implementation of this pairing in characteristic 3. All characteristic 3 operations required to compute the pairing are outlined in detail. An efficient, flexible and reconfigurable processor for the $\eta_T$ pairing in characteristic 3 is presented and discussed. The processor can easily be tailored for a low area implementation, for a high throughput implementation, or for a balance between the two. Results are provided for various configurations of the processor when implemented over the field $\mathbb{F}_{3^{97}}$ on an FPGA. As far as we are aware, the processor returns the first characteristic 3 $\eta_T$ pairing in hardware that includes a final exponentiation to a unique value.

This paper describes a new practical DoS attack that can be mounted against the ``encryption-only'' configuration (i.e. without authenticated integrity) of ESP as allowed by IPSec. This finding can serve as a strong argument to convince those in charge of the IPSec standardization to improve it by banning the ``encryption-only'' configuration from the standard.

We present an approach to design cryptographic hash functions that builds on and improves the one underlying the Panama hash function. We discuss the properties of the resulting hash functions that need to be investigated and give a concrete design called RadioGatún that is quite competitive with SHA-1 in terms of performance. We are busy performing an analysis of RadioGatún and present in this paper some preliminary results.

In this paper, we propose a Hierarchical Identity Based Encryption scheme that is proven secure under the strongest model of \cite{BonehFr01} directly, without relying on random oracles. The size of the ciphertext is a constant while the size of public parameters is independent to the number of bit representing an identity. It is the first in the literature to achieve such a high security level and space efficiency at the same time. In addition, we also propose the first Hierarchical Identity Based Signature scheme that is proven under the strongest model without relying on random oracles and using more standard $q$-SDH assumption. Similar to the proposed encryption scheme, the space complexity of the signature and public parameters are as efficient as the proposed encryption scheme.

This paper demonstrates that a certificateless signature scheme recently proposed by Gorantla and Saxena is insecure. It is shown that an adversary who replaces the public key of a signer can then forge valid signatures for that signer without knowledge of the signer's private key.

We motivate and describe the problem of finding protocols for multiparty computations that only use a single broadcast round per computation (latency-free computations). We show that solutions exists for one multiparty computation problem, that of elections, and more generally, addition in certain groups. The protocol construction is based on an interesting pseudo-random function family with a novel property.

KD04 proposed by K. Kurosawa and Y. Desmedt is the most efficient public key encryption scheme provably secure against adaptive chosen ciphertext attack in standard model based on decision diffie-hellman problem. We proposed a simplify version of KD04 which is more efficient than KD04 while still can be proved to be secure against adaptive chosen ciphertext attack in standard model based on decision diffie-hellman problem.

It is well understood that passwords must be very long and complex to have sufficient entropy for security purposes. Unfortunately, these passwords tend to be hard to memorize, and so alternatives are sought. Smart Cards, Biometrics, and Reverse Turing Tests (human-only solvable puzzles) are options, but another option is to use pass-phrases. This paper explores methods for making pass-phrases suitable for use with password-based authentication and key-exchange (PAKE) protocols, and in particular, with schemes resilient to server-file compromise. In particular, the $\Omega$-method of Gentry, MacKenzie and Ramzan, is combined with the Bellovin-Merritt protocol to provide mutual authentication (in the random oracle model [CGH04,BBP04,MRH04]. Furthermore, since common password-related problems are typographical errors, and the CAPSLOCK key, we show how a dictionary can be used with the Damerau-Levenshtein string-edit distance metric to construct a case-insensitive pass-phrase system that can tolerate zero, one, or two spelling-errors per word, with no loss in security. Furthermore, we show that the system can be made to accept pass-phrases that have been arbitrarily reordered, with a security cost that can be calculated. While a pass-phrase space of $2^{128}$ is not achieved by this scheme, sizes in the range of $2^{52}$ to $2^{112}$ result from various selections of parameter sizes. An attacker who has acquired the server-file must exhaust over this space, while an attacker without the server-file cannot succeed with non-negligible probability.

We consider oblivious transfer protocols and their applications that use underneath semantically secure homomorphic encryption scheme (e.g. Paillier's). We show that some oblivious transfer protocols and their derivatives such as private matching, oblivious polynomial evaluation and private shared scalar product could be subject to an attack. The same attack can be applied to some non-interactive zero-knowledge arguments which use homomorphic encryption schemes underneath. The roots of our attack lie in the additional property that some semantically secure encryption schemes possess, namely, the decryption also reveals the random coin used for the encryption, and that the (sender's or prover's) inputs may belong to a space, that is very small compared to the plaintext space. In this case it appears that even a semi-honest chooser (verifier) can derive from the random coin bounds for all or some of the sender's (prover's) private inputs with non-negligible probability. We propose a fix which precludes the attacks.

The current work considers the problem of obtaining a hierarchical identity-based encryption (HIBE) protocol which is secure against adaptive key extraction and decryption queries. Such a protocol is obtained by modifying an earlier protocol by Chatterjee and Sarkar (which, in turn, is based on a protocol due to Waters) which is secure only against adaptive key extraction queries. The setting is quite general in the sense that random oracles are not used and security is based on the hardness of the decisional bilinear Diffie-Hellman (DBDH) problem. In this setting, the new construction provides the most efficient (H)IBE protocol known till date. The technique for answering decryption queries in the proof is based on earlier work by Boyen, Mei and Waters. Ciphertext validity testing is done indirectly through a symmetric authentication algorithm in a manner similar to the Kurosawa-Desmedt public key encryption protocol. Additionally, we perform symmetric encryption and authentication by a single authenticated encryption algorithm.

The notion of concurrent signatures was recently introduced by Chen, Kudla and Paterson. In concurrent signature schemes, two entities can produce two signatures that are not binding, until an extra piece of information (namely the keystone) is released by one of the parties. Subsequently, it was noted that the concurrent signature scheme proposed in the seminal paper cannot provide perfect ambiguity. Then, the notion of perfect concurrent signatures was introduced. In this paper, we define the notion of identity-based (or ID-based) perfect concurrent signature schemes. We provide the first generic construction of (ID-based) perfect concurrent signature schemes from ring signature schemes. Using the proposed framework, we give two concrete ID-based perfect concurrent signature schemes based on two major paradigms of ID-based ring signature schemes. Security proofs are based on the random oracle model.

We have shown how, at a cost of about $2^{52}$ calls to the MD5 compression function, for any two target messages $m_1$ and $m_2$, values $b_1$ and $b_2$ can be constructed such that the concatenated values $m_1\|b_1$ and $m_2\|b_2$ collide under MD5. Although the practical attack potential of this construction of \emph{target collisions} is limited, it is of greater concern than random collisions for MD5. In this note we sketch our construction. To illustrate its practicality, we present two MD5 based X.509 certificates with identical signatures but different public keys \emph{and} different Distinguished Name fields, whereas our previous construction of colliding X.509 certificates required identical name fields. We speculate on other possibilities for abusing target collisions.

This note points out a gap between two natural formulations of the concept of a proof of knowledge, and shows that in all natural cases (e.g., NP-statements) this gap can be closed. The aforementioned formulations differ by whether they refer to (all possible) probabilistic or deterministic prover strategies. Unlike in the rest of cryptography, in the current context, the obvious transformation of probabilistic strategies to deterministic strategies does not seem to suffice per se.

Abstract. An encrypted email is sent from Bob to Alice. A gateway wants to check whether a certain keyword exists in an email or not for some reason (e.g. routing). Nevertheless Alice does not want the email to be decrypted by anyone except her including the gateway itself. This is a scenario where public key encryption with keyword search (PEKS) is needed. In this paper we construct a new scheme (KR-PEKS) the KResilient Public Key Encryption with Keyword Search. The new scheme is secure under a chosen keyword attack without the random oracle. The ability of constructing a Public Key Encryption with Keyword Search from an Identity Based Encryption was used in the construction of the KR-PEKS. The security of the new scheme was proved by showing that the used IBE has a notion of key privacy. The scheme was then modified in two different ways in order to fulfill each of the following: the first modification was done to enable multiple keyword search and the other was done to remove the need of secure channels.

The paper cryptanalyses a public-key cryptosystem recently proposed by Grigoriev and Ponomarenko, which encrypts an element from a fixed finite group defined in terms of generators and relations to produce a ciphertext from SL(2, Z). The paper presents a heuristic method for recovering the secret key from the public key, and so this cryptosystem should not be used in practice.

Rewinding techniques form the essence of many security reductions including proofs for identification and signature schemes. We propose a simple and modular approach for the construction of such proofs. Straightforward applications of our central result include, but are not limited to, the security of identification schemes, generic signatures and ring signatures. These results are well known, however, we generalise them in such a way that our technique can be used off-the-shelf for future applications. We note that less is more: as a side-effect of our less complex analysis, all our proofs are more precise; for example, we get a new proof of the forking lemma that is $2^{15}$ times more precise than the original result by Pointcheval and Stern. Finally, we give the first precise security analysis of Blum's coin flipping protocol with $k$-bit strings, as yet another example of the strength of our results.

We provide the first construction of a concurrent and non-malleable zero knowledge argument for every language in NP. We stress that our construction is in the plain model with no common random string, trusted parties, or super-polynomial simulation. That is, we construct a zero knowledge protocol $\Pi$ such that for every polynomial-time adversary that can adaptively and concurrently schedule polynomially many executions of $\Pi$, and corrupt some of the verifiers and some of the provers in these sessions, there is a polynomial-time simulator that can simulate a transcript of the entire execution, along with the witnesses for all statements proven by a corrupt prover to an honest verifier. Our security model is the traditional model for concurrent zero knowledge, where the statements to be proven by the honest provers are fixed in advance and do not depend on the previous history (but can be correlated with each other); corrupted provers, of course, can chose the statements adaptively. We also prove that there exists some functionality F (a combination of zero knowledge and oblivious transfer) such that it is impossible to obtain a concurrent non-malleable protocol for F in this model. Previous impossibility results for composable protocols ruled out existence of protocols for a wider class of functionalities (including zero knowledge!) but only if these protocols were required to remain secure when executed concurrently with arbitrarily chosen different protocols (Lindell, FOCS 2003) or if these protocols were required to remain secure when the honest parties' inputs in each execution are chosen adaptively based on the results of previous executions (Lindell, TCC 2004). We obtain an $\Tilde{O}(n)$-round protocol under the assumption that one-to-one one-way functions exist. This can be improved to $\Tilde{O}(k\log n)$ rounds under the assumption that there exist $k$-round statistically hiding commitment schemes. Our protocol is a black-box zero knowledge protocol.

In this paper, we will propose a new synchronous stream cipher named DICING, which can be taken as a clock-controlled one but with a new mechanism of altering steps. With the simple construction, DICING has satisfactory performance, faster than AES about two times. For the security, there have not been found weakness for the known attacks, the key sizes can be 128bits and 256bits respectively.

The notion of concurrent signatures was introduced by Chen, Kudla and Paterson in their seminal paper in Eurocrypt 2004. In concurrent signature schemes, two entities can produce two signatures that are not binding, until an extra piece of information (namely the keystone) is released by one of the parties. Upon release of the keystone, both signatures become binding to their true signers concurrently. In ICICS 2005, two identity-based perfect concurrent signature schemes were proposed by Chow and Susilo. In this paper, we show that these two schemes are unfair, in which the initial signer can cheat the matching signer. We present a formal definition of ID-based concurrent signatures which redress the flaw of Chow et al.'s definition and then propose two simple but significant improvements to fix our attacks.

We present specifications and provable protocol, for secure ordering and provision of digital goods and services. Notably, our protocol includes fully automated resolution of disputes between providers and customers. Disputes may involve the timely receipt of orders and goods, due to communication failures and malicious faults, as well as disputes of fitness of goods and order. The protocol and specifications are modular, with precise yet general-purpose interfaces. This allows usage as an underlying service to different e-commerce scenarios and applications, in particular secure online banking and brokerage. The protocol is practical, efficient, reliable and secure, under realistic failure and delay conditions. Our design and specifications are a part of a layered architecture for secure e-commerce applications.

Very recently, a new software side-channel attack, called Branch Prediction Analysis (BPA) attack, has been discovered and also demonstrated to be practically feasible on popular commodity PC platforms. While the above recent attack still had the flavor of a classical timing attack against RSA, where one uses many execution-time measurements under the same key in order to statistically amplify some small but key-dependent timing differences, we dramatically improve upon the former result. We prove that a carefully written spy-process running simultaneously with an RSA-process, is able to collect during one \emph{single} RSA signing execution almost all of the secret key bits. We call such an attack, analyzing the CPU's Branch Predictor states through spying on a single quasi-parallel computation process, a \emph{Simple Branch Prediction Analysis (SBPA)} attack --- sharply differentiating it from those one relying on statistical methods and requiring many computation measurements under the same key. The successful extraction of almost all secret key bits by our SBPA attack against an openSSL RSA implementation proves that the often recommended blinding or so called randomization techniques to protect RSA against side-channel attacks are, in the context of SBPA attacks, totally useless. Additional to that very crucial security implication, targeted at such implementations which are assumed to be at least statistically secure, our successful SBPA attack also bears another equally critical security implication. Namely, in the context of simple side-channel attacks, it is widely believed that equally balancing the operations after branches is a secure countermeasure against such simple attacks. Unfortunately, this is not true, as even such ``balanced branch'' implementations can be completely broken by our SBPA attacks. Moreover, despite sophisticated hardware-assisted partitioning methods such as memory protection, sandboxing or even virtualization, SBPA attacks empower an unprivileged process to successfully attack other processes running in parallel on the same processor. Thus, we conclude that SBPA attacks are much more dangerous than previously anticipated, as they obviously do not belong to the same category as pure timing attacks.

This paper studies the security of the block ciphers ARIA and Camellia against impossible differential cryptanalysis. Our work improves the best impossible differential cryptanalysis of ARIA and Camellia known so far. The designers of ARIA expected no impossible differentials exist for 4-round ARIA. However, we found some nontrivial 4-round impossible differentials, which may lead to a possible attack on 6-round ARIA. Moreover, we found some nontrivial 8-round impossible differentials for Camellia, whereas only 7-round impossible differentials were previously known. By using the 8-round impossible differentials, we presented an attack on 12-round Camellia without $FL/FL^{-1}$ layers.

Dynamic compilation systems are of fundamental importance to high performance execution of interpreted languages such as Java. These systems analyse the performance of an application at run-time and aggressively re-compile and optimise code which is deemed critical to performance. However, the premise that the code executed is not the same code as written by the programmer raises a number of important security concerns. In this paper we examine the specific problem that dynamic compilation, through transformation of the code, may introduce side-channel vulnerabilities where before there were none.

A $(k,\ell)$-robust combiner for collision-resistant hash-functions is a construction which from $\ell$ hash-functions constructs a hash-function which is collision-resistant if at least $k$ of the components are collision-resistant. One trivially gets a $(k,\ell)$-robust combiner by concatenating the output of any $\ell-k+1$ of the components, unfortunately this is not very practical as the length of the output of the combiner is quite large. We show that this is unavoidable as no black-box $(k,\ell)$-robust combiner whose output is significantly shorter than what can be achieved by concatenation exists. This answers a question of Boneh and Boyen (Crypto'06).

In this paper, we show a general classification of cryptographically used elliptic and hyperelliptic curves which can be attacked by the Weil descent attack and index calculus algorithms. In particular, we classfy all the Weil restriction of these curves obtained by $(2,...,2)$ covering. Density analysis of these curves are shown. Explicit defintion equations of such weak curves are also provided.

Recently, there are several generic transformation techniques proposed for converting unforgeable signature schemes (the message in the forgery has not been signed yet) into strongly unforgeable ones (the message in the forgery could have been signed previously). Most of the techniques are based on trapdoor hash functions and all of them require adding supplementary components onto the original key pair of the signature scheme. In this paper, we propose a new generic transformation which converts \emph{any} unforgeable signature scheme into a strongly unforgeable one, and also keeps the key pair of the signature scheme unchanged. Our technique is based on \emph{strong one-time signature schemes}. We show that they can be constructed efficiently from any one-time signature scheme that is based on one-way functions. The performance of our technique also compares favorably with that of those trapdoor-hash-function-based ones. In addition, this new generic transformation can also be used for attaining strongly unforgeable signature schemes in other cryptographic settings which include certificateless signature, identity-based signature, and several others. To the best of our knowledge, similar extent of versatility is not known to be supported by any of those comparable techniques. Finally and of independent interest, we show that our generic transformation technique can be modified to an \emph{on-line/off-line} signature scheme, which possesses a very efficient signing process.

We provide algorithms guaranteeing high levels of privacy by computing uniformly random solutions to stable marriages problems. We also provide efficient algorithms extracting a non-uniformly random solution and guaranteeing t-privacy for any threshold t. The most private solution is expensive and is based on a distributed/shared CSP model of the problem. The most efficient version is based on running the Gale-Shapley algorithm after shuffling the men (or women) in the shared secret description of the problem. We introduce an efficient arithmetic circuit for the Gale-Shapley algorithm that can employ a cryptographic primitive we propose for vector access with an arbitrary number of participants. Participants want to find a stable matching as defined by their secret preferences and without leaking any of these secrets. An additional advantage of the solvers based on secure simulations of arithmetic circuits is that it returns a solution picked randomly among existing solutions. Besides the fact that this increases privacy to a level of requested t-privacy, it also provides fairness to participants. A real implementation of a described secure solution usable by participants on distinct computers on the Internet is implemented (by students in a class assignment) and is available on our web-site.

In this paper, we present a new proxy cryptosystem named subject-delegated decryption scheme, in which the original decryptor delegates decryption authority to multiple proxies according to different subjects. The advantage of our scheme is that the proxy authorities are tightly limited (``Tightly" Limited Authority). This means that the proxy authority can be temporarily aborted even if the validity period of the proxy key does not expire. Consequently, our protocol is more practical than the existential protocols because the secrecy of the original decryptor can be protected efficiently from his proxy, especially when the proxy becomes corrupted. Our scheme is efficient because the encryption method in our scheme is based on a hybrid of symmetric key and public key cryptographic techniques. We give the provable security using a variant decisional Bilinear Diffie-Hellman (BDH) assumption.

Verifiably encrypted signature is useful in handling the fair exchange problem especially, online contract signing. In this paper, we propose a verifiably encrypted signature scheme using bilinear pairings. Our scheme facilitates the adjudication to be done in a threshold manner to achieve robustness. We show that the distribution of adjudication capability is robust and unforgeable. Our scheme is secure against extraction and existential forgery in the random oracle model.

In 1997, Cranor and Cytron proposed an electronic voting protocol, Sensus protocol, intended to be applied in a real election. However, in 2005 Fabrizio et.al. pointed out there is a vulnerability exists in their protocol that the validator can impersonate anyone of those abstained voters to cast vote. They proposed a scheme, Seas protocol, to solve this weakness. But in this paper, we will show that Seas protocol is not only inefficient but also impractical. Moreover, we also propose a sound electronic voting protocol based on Sensus protocol from bilinear pairings, which can really satisfy the security requirements of an e-voting system.

MV3 is a new word based stream cipher for encrypting long streams of data. A direct adaptation of a byte based cipher such as RC4 into a 32- or 64-bit word version will obviously need vast amounts of memory. This scaling issue necessitates a look for new components and principles, as well as mathematical analysis to justify their use. Our approach, like RC4's, is based on rapidly mixing random walks on directed graphs (that is, walks which reach a random state quickly, from any starting point). We begin with some well understood walks, and then introduce nonlinearity in their steps in order to improve security and show long term statistical correlations are negligible. To minimize the short term correlations, as well as to deter attacks using equations involving successive outputs, we provide a method for sequencing the outputs derived from the walk using three revolving buffers. The cipher is fast --- it runs at a speed of less than 5 cycles per byte on a Pentium IV processor. A word based cipher needs to output more bits per step, which exposes more correlations for attacks. Moreover we seek simplicity of construction and transparent analysis. To meet these requirements, we use a larger state and claim security corresponding to only a fraction of it. Our design is for an adequately secure word-based cipher; our very preliminary estimate puts the security close to exhaustive search for keys of size < 256 bits.

Since early 1990s, chaos has been widely investigated to construct multimedia encryption scheme for its good cryptography-like characteristics, such as the ergodicity, mixing and exactness property and the sensitivity to initial conditions. This thesis is concerned with the cryptanalyses of some recently-proposed chaos related multimedia encryption schemes. The security of the schemes against some familiar attack methods, such as brute-force attack, known/chosen-plaintext attack, is investigated in detail with theoretical analyses and experimental results. The main achievements are as follows: 1. Based on a normalized encryption/decryption model, from a general perspective this thesis analyzes the security of permutation-only multimedia ciphers. It is pointed out that all permutation-only image ciphers are insecure against known/chosen-plaintext attacks in the sense that only O (log_L(MN)) known/chosen plain-images are enough to break the ciphers, where MN is the size of the image and L is the number of all possible different pixel values. Also, it is found that the attack complexity is only O(n(MN)^2), where n is the number of known/chosen plain-images used. A recently proposed permutation-only image cipher called hierarchical chaotic image encryption (HCIE) is served as a concretized example to show how the attack work. Experiments are shown to verify the feasibility of the known/chosen-plaintext attacks. 2. The security of a recently proposed chaos-based image encryption scheme called RCES (also called RSES) was analyzed and we found that it can be broken with only one or two known/chosen-plaintexts. In addition, the security of RCES against the brute-force attack was overestimated. Both theoretical and experimental analyses are given to show the performance of the suggested known/chosen-plaintext attacks. 3. This thesis analyzes the security of a new multistage encryption system (MES) recently proposed in ISCAS'2004. It is found that MES is insecure against a differential chosen-plaintext/ciphertext attack. Experiments are given to support the proposed attack. It is also pointed out that the security of MES against brute-force attacks is not sufficiently high. 4. This thesis analyzes the security of a new domino signal encryption algorithm(DSEA), and points out the following weaknesses: 1) its security against the brute-force attack was overestimated; 2) it is not sufficiently secure against ciphertext-only attacks, and only one ciphertext is enough to get some information about the plaintext and to break the value of a sub-key; 3) it is insecure against known/chosen-plaintext attacks, in the sense that the secret key can be recovered from a number of continuous bytes of only one known/chosen plaintext and the corresponding ciphertext. Experimental results are given to show the performance of the proposed attacks. 5. A comprehensive analysis on the security of two-dimensional circulation encryption algorithm (TDCEA) is presented. The following security problems are found: 1) there exist some essential security defects in TDCEA; 2) two known-plaintext attacks can break TDCEA; 3) the chosen-plaintext versions of the aforementioned two known-plaintext attacks can break TDCEA even with a smaller complexity and a better performance. Some experiments are given to show the security defects of TDCEA and the feasibility of the proposed known-plaintext attacks. 6. The security of two neural-network-based encryption schemes, which are proposed by Yen et al. and Zhou et al. respectively, are analyzed in detail. It is found that the former can be easily broken by known/chosen-plaintext attacks and the latter can be broken by a chosen-plaintext attack. Experimental analyses are given to support the feasibility of the proposed attacks. 7. Some insecure properties of a VoIP encryption scheme named hierarchical data security protection (HDSP) are pointed out, which are then used to develop known/chosen-plaintext attacks. The following facts are found: 1) given n known plaintexts, only about (50/2n)% of secret chaotic bits cannot be uniquely determined; 2) given only one specially-chosen plaintext, all secret chaotic bits can be uniquely derived; 3) the secret key can be derived with a practically small complexity even when only one plaintext is known(or chosen). Experiments are given to show the feasibility of the proposed attacks. In addition, it is found that the security of HDSP against the bruteforce attack is not practically strong.

Any access structure is the multipartite access structure, The set of players is devided into K different entities, in such a way that all players of the same role in the multipartite access structure, we suppose there is a threshold access structure in every different entity, there is also a threshold access structure in K different entities, we consider their composite access structure, then a new family of Multipartite Access Structure will be given, we will provide secret shring scheme realizing it and prove it is ideal.

Signcryption is a cryptographic primitive that performs signature and encryption simultaneously, at a lower computational costs and communication overheads than the signature-then-encryption approach. In this paper, we propose an efficient multi-recipient signcryption scheme based on the bilinear pairings which broadcasts a message to multiple users in a secure and authenticated manner. We prove its semantic security and unforgeability under the Gap Diffie-Hellman problem assumption in the random oracle model. The proposed scheme is more efficient than re-signcrypting a message n times using a signcryption scheme in terms of computational costs and communication overheads.

In this paper, we propose a new zero-knowledge identification protocol. While the protocol consists of only two message flows, it does not rely on any underlying signature or encryption scheme. Its zero-knowledge property is preserved under concurrent composition and reset settings. It is secure under the strongest attack model which incorporates concurrent attacks, active-intruder attacks and reset attacks. Meanwhile its performance in computation and communication is close to that of the most efficient identification protocols not based on signature or encryption systems, most of which are insecure in this strong attack model.

In the CT-track of the 2006 RSA conference, a new multivariate public key cryptosystem, which is called the Medium Field Equation (MFE) multivariate public key cryptosystem, is proposed by Wang, Yang, Hu and Lai. We use the second order linearization equation attack method by Patarin to break MFE. Given a ciphertext, we can derive the plaintext within $2^{23}$ $\F_{2^{16}}$-operations, after performing once for any public key a computation of complexity less than $2^{52}$. We also propose a high order linearization equation (HOLE) attack on multivariate public key cryptosystems, which is a further generalization of the (first and second order) linearization equation (LE). This method can be used to attack extensions of the current MFE.

Recently, Yoon et al. and Cao et al. propose two deniable authentication protocols respectively. They both claim that their protocols can achieve the deniable property. However, in this paper, we will point out that their protocols each suffers from some malicious attacks. After that, we propose a new identity-based deniable authentication protocol on pairings which can not only attain the desired deniable property but also can prevent attacks.

We present a collision attack on the hash function HAS-160 reduced to 53-steps. The attack has a complexity of about $2^{35}$ hash computations. The attack is based on the work of Cho etal. presented at ICISC 2006. In this article, we improve their attack complexity by a factor of about $2^{20}$ using a slightly different strategy for message modification in the first 20 steps of the hash function.

Déchène has proposed generalized Jacobians as a source of groups for public-key cryptosystems based on the hardness of the Discrete Logarithm Problem (DLP). Her specific proposal gives rise to a group isomorphic to the semidirect product of an elliptic curve and a multiplicative group of a finite field. We explain why her proposal has no advantages over simply taking the direct product of groups. We then argue that generalized Jacobians offer poorer security and efficiency than standard Jacobians.

At Financial Crypto 2006, Golle presented a novel framework for the privacy preserving computation of a stable matching (stable marriage). We show that the communication complexity of Golle's main protocol is substantially greater than what was claimed in that paper, in part due to surprising pathological behavior of Golle's variant of the Gale-Shapley stable matching algorithm. We also develop new protocols in Golle's basic framework with greatly reduced communication complexity.

Generalized Jacobians are natural candidates to use in discrete logarithm (DL) based cryptography since they include the multiplicative group of finite fields, algebraic tori, elliptic curves as well as all Jacobians of curves. This thus led to the study of the simplest nontrivial generalized Jacobians of an elliptic curve, for which an efficient group law algorithm was recently obtained. With these explicit equations at hand, it is now possible to concretely study the corresponding discrete logarithm problem (DLP); this is what we undertake in this paper. In short, our results highlight the close links between the DLP in these generalized Jacobians and the ones in the underlying elliptic curve and finite field.

We investigate the impact of larger digit sets on the length of Double-Base Number system (DBNS) expansions. We present a new representation system called {\em extended DBNS} whose expansions can be extremely sparse. When compared with double-base chains, the average length of extended DBNS expansions of integers of size in the range 200--500 bits is approximately reduced by $20\%$ using one precomputed point, $30\%$ using two, and $38\%$ using four. We also discuss a new approach to approximate an integer $n$ by $d2^a3^b$ where $d$ belongs to a given digit set. This method, which requires some precomputations as well, leads to realistic DBNS implementations. Finally, a left-to-right scalar multiplication relying on extended DBNS is given. On an elliptic curve where operations are performed in Jacobian coordinates, improvements of up to $13\%$ overall can be expected with this approach when compared to window NAF methods using the same number of precomputed points. In this context, it is therefore the fastest method known to date to compute a scalar multiplication on a generic elliptic curve.

Artin's braid groups have been recently suggested as a new source for public-key cryptography. In this paper we first propose the designated verifier group signature scheme based on the conjugacy search problem and the root problem in the braid groups which are believed to be hard problems. Furthermore, our scheme can conceal the message to be signed so that it can be applied to E-voting and calling for tenders

The main characteristic of a mobile ad-hoc network is its infrastructure-less, highly dynamic topology, which is subject to malicious traffic analysis. Malicious intermediate nodes in wireless mobile ad-hoc networks are a threat concerning security as well as anonymity of exchanged information. To protect anonymity and achieve security of nodes in mobile ad-hoc networks, an anonymous on-demand routing protocol, termed RIOMO, is proposed. For this purpose, pseudo IDs of the nodes are generated considering Pairing-based Cryptography. Nodes can generate their own pseudo IDs independently. As a result RIOMO reduces pseudo IDs maintenance costs. Only trust-worthy nodes are allowed to take part in routing to discover a route. To ensure trustiness each node has to make authentication to its neighbors through an anonymous authentication process. Thus RIOMO safely communicates between nodes without disclosing node identities; it also provides different desirable anonymous properties such as identity privacy, location privacy, route anonymity, and robustness against several attacks.

In this paper, we propose a modified $\eta_T$ pairing algorithm in characteristic three which does not need any cube root extraction. We also discuss its implementation on a low cost platform which hosts an Altera Cyclone~II FPGA device. Our pairing accelerator is ten times faster than previous known FPGA implementations in characteristic three.

HB and HB+ are two shared-key, unidirectional authentication protocols whose extremely low computational cost makes them potentially well-suited for severely resource-constrained devices. Security of these protocols is based on the conjectured hardness of learning parity with noise; that is, learning a secret $s$ given ``noisy'' dot products of $s$ that are incorrect with probability $\epsilon$. Although the problem of learning parity with noise is meaningful for any constant $\epsilon < 1/2$, existing proofs of security for HB and HB+ only imply security when $\epsilon < 1/4$. In this note, we show how to extend these proofs to the case of arbitrary $\epsilon < 1/2$.

We construct the first $O(1)$-size designated confirmer signatures (DCS) with security in the state-of-the-art model of Camenisch and Michels, Eurocrypt 2000, without random oracles. In particular, we achieve the security notion called the "invisibility of signature" therein.

We consider broadcast encryption schemes wherein a center needs to broadcast a secret message to a privileged set of receivers. We prescribe a probability distribution $P$ on the privileged set. In this setting, the transmission overhead can be viewed as a random variable over $P$ and we define its expected value as the average transmission overhead (or ato). Given $P$, the Shannon's entropy function $H(.)$ provides a lower bound on the average number of bits required to identify every privileged set. This provides a natural lower bound for the ato in terms of $H(P)$. For session key distribution, we consider the subset cover framework and bound the ato in terms of the size of the cover. We further specialize our bound to accommodate storage constraints at receivers. We consider two families of distributions for $P$ that occur naturally in broadcast networks. -- Each receiver independently joins the privileged set with probability $p$. -- The privileged set is selected uniformly from a collection of subsets of receivers. We evaluate the ato of some practical schemes such as the subset difference method, the LSD scheme and the Partition-and-Power scheme under these distributions. Our investigations lead us to conclude that each scheme is inherently tailored to perform optimally for specific distributions.

In the research of the relationship between the formal and the computational view of cryptography, a recent approach uses static equivalence from cryptographic pi calculi as a notion of formal indistinguishability. Previous work has shown that this yields the soundness of natural interpretations of some interesting equational theories, such as certain cryptographic operations and a theory of XOR. In this paper however, we argue that static equivalence is too coarse for sound interpretations of equational theories in general. We show some explicit examples how static equivalence fails to work in interesting cases. To fix this problem, we propose a notion of formal indistinguishability that is more flexible than static equivalence. We provide a general framework along with general theorems, and then discuss how this new notion works for the explicit examples where static equivalence failed to ensure soundness. We also improve the treatment by using ordered sorts in the formal view, and by allowing arbitrary probability distributions of the interpretations.

The algebraic immunity of an S-box depends on the number and type of linearly independent multivariate equations it satisfies. In this paper techniques are developed to find the number of linearly independent, multivariate, bi-affine and quadratic equations for S-boxes based on power mappings. These techniques can be used to prove the exact number of equations for any class of power mappings. Two algorithms to calculate the number of bi-affine and quadratic equations for any $(n,n)$ S-box based on power mapping are also presented. The time complexity of both algorithms is only $O(n^2)$. To design algebraically immune S-boxes four new classes of S-boxes that guarantee zero bi-affine equations and one class of S-boxes that guarantees zero quadratic equations are presented. The algebraic immunity of power mappings based on Kasami, Niho, Dobbertin, Gold, Welch and Inverse exponents are discussed along with other cryptographic properties and several cryptographically strong S-boxes are identified. It is conjectured that a known Kasami like APN power mapping is maximally nonlinear and a known Kasami like maximally nonlinear power mapping is differentially 4-uniform. Finally an open problem to find an $(n,n)$ bijective nonlinear S-box with more than $5n$ quadratic equations is solved and it is conjectured that the upper bound on this number is $\frac{n(n-1)}{2}$.

A family of pseudorandom generators based on the decisional Diffie-Hellman assumption is proposed. The new construction is a modified and generalized version of the Dual Elliptic Curve generator proposed by Barker and Kelsey. Although the original Dual Elliptic Curve generator is shown to be insecure, the modified version is provably secure and very efficient in comparison with the other pseudorandom generators based on discrete log assumptions. Our generator can be based on any group of prime order provided that an additional requirement is met (i.e., there exists an efficiently computable function that in some sense enumerates the elements of the group). Two specific instances are presented. The techniques used to design the instances, for example, the new probabilistic randomness extractor are of independent interest for other applications.

The Merkle signature scheme (MSS) is an interesting alternative for well established signature schemes such as RSA, DSA, and ECDSA. The security of MSS only relies on the existence of cryptographically secure hash functions. MSS has a good chance of being quantum computer resistant. In this paper, we propose CMSS, a variant of MSS, with reduced private key size, key pair generation time, and signature generation time. We demonstrate that CMSS is competitive in practice by presenting a highly efficient implementation within the Java Cryptographic Service Provider FlexiProvider. We present extensive experimental results and show that our implementation can for example be used to sign messages in Microsoft Outlook.

In this paper, we analyze the security of HMAC and NMAC, both of which are hash-based message authentication codes. We present distinguishing, forgery, and partial key recovery attacks on HMAC and NMAC using collisions of MD4, MD5, SHA-0, and reduced SHA-1. Our results demonstrate that the strength of a cryptographic scheme can be greatly weakened by the insecurity of the underlying hash function.

As a useful means of safeguarding privacy of communications, deniable authentication has received much attention. A Chameleon-based deniable authenticated key agreement protocol is presented in this paper. The protocol has following properties. Any one of the two participants can’t present a digital proof to convince a third party that a claimed agreement has really taken place. Once a forgery occurs, the original entity can present a digital proof to disclose the forgery.

This report presents analysis of the compression function of a recently proposed hash function, FORK-256. We exhibit some unexpected differentials existing for the step transformation and show their possible uses in collision-finding attacks on different variants of FORK-256. As a simple application of those observations we present a method of finding chosen IV collisions for a variant of FORK-256 reduced to two branches : either 1 and 2 or 3 and 4. Moreover, we present how those differentials can be used in the full FORK-256 to easily find messages with hashes differing by only a relatively small number of bits. We argue that this method allows for finding collisions in the full function with complexity not exceeding $2^{126.6}$ hash evaluations, better than birthday attack and additionally requiring only a small amount of memory.

The Elliptic Curve Digital Signature Algorithm admits a natural parallelization wherein the point multiplication step can be split in two parts and executed in parallel. Further parallelism is achieved by executing a portion of the multiprecision arithmetic operations in parallel with point multiplication. This results in a saving in timing as well as gate count when the two paths are implemented in hardware and software. This article attempts to exploit this parallelism in a typical system context in which a microprocessor is always present though a hardware accelerator is being designed for performance. We discuss some implementation aspects of this design with reference to power analysis attacks. We show how the Montgomery point multiplication and the binary extended gcd algorithms can be adapted to prevent simple power analysis attacks. We implemented our design using a hardware/software parallel architecture. We present the results when the software component is coded on an 8051 architecture and an ARM7TDMI processor.

We investigate whether security of multiparty computation in the information-theoretic setting implies their security under concurrent composition. We show that security in the stand-alone model proven using black-box simulators in the information-theoretic setting does not imply security under concurrent composition, not even security under 2-bounded concurrent self-composition with an inefficient simulator and fixed inputs. This in particular refutes recently made claims on the equivalence of security in the stand-alone model and concurrent composition for perfect and statistical security (STOC'06). Our result strongly relies on the question whether every rewinding simulator can be transformed into an equivalent, potentially inefficient non-rewinding (straight-line) simulator. We answer this question in the negative by giving a protocol that can be proven secure using a rewinding simulator, yet that is not secure for any non-rewinding simulator.

We consider a type of zero-knowledge protocols that are of interest for their practical applications within networks like the Internet: efficient zero-knowledge arguments of knowledge that remain secure against concurrent man-in-the-middle attacks. As negative results in the area of concurrent non-malleable zero-knowledge imply that protocols in the standard setting (i.e., under no setup assumptions) can only be given for trivial languages, researchers have studied such protocols in models with setup assumptions, such as the common reference string (CRS) model. This model assumes that a reference string is honestly created at the beginning of all interactions and later available to all parties (an assumption that is satisfied, for instance, in the presence of a trusted party). A growing area of research in Cryptography is that of reducing the setup assumptions under which certain cryptographic protocols can be realized. In an effort to reduce the setup assumptions required for efficient zero-knowledge arguments of knowledge that remain secure against concurrent man-in-the-middle attacks, we consider a model, which we call the Authenticated Public-Key (APK) model. The APK model seems to significantly reduce the setup assumptions made by the CRS model (as no trusted party or honest execution of a centralized algorithm are required), and can be seen as a slightly stronger variation of the Bare Public-Key (BPK) model from \cite{CGGM,MR}, and a weaker variation of the registered public-key model used in \cite{BCNP}. We then define and study man-in-the-middle attacks in the APK model. Our main result is a constant-round concurrent non-malleable zero-knowledge argument of knowledge for any polynomial-time relation (associated to a language in $\mathcal{NP}$), under the (minimal) assumption of the existence of a one-way function family. We also show time-efficient instantiations of our protocol, in which the transformation from a 3-round honest-verifier zero-knowledge argument of knowledge to a 4-round concurrently non-malleable zero-knowledge argument of knowledge for the same relation incurs only $\mathcal{O}(1)$ (precisely, a {\em small} constant) additional modular exponentiations, based on known number-theoretic assumptions. Furthermore, the APK model is motivated by the consideration of some man-in-the-middle attacks in models with setup assumptions that had not been considered previously and might be of independent interest. We also note a negative result with respect to further reducing the setup assumptions of our protocol to those in the (unauthenticated) BPK model, by showing that concurrently non-malleable zero-knowledge arguments of knowledge in the BPK model are only possible for trivial languages.

In cryptosystems based on elliptic curves over finite fields (ECC-systems), the most time-consuming operation is scalar multiplication. We focus on the NIST elliptic curves over prime fields. An implementation of scalar multiplication, developed by IBM Danmark A/S for test purposes, serves as a point of reference. In order to achieve maximal efficiency in an ECC-system, one must choose an optimal method for scalar multiplication and the best possible coordinate representation for the curve being used. We perform an analysis of known scalar multiplication methods. This analysis contains a higher degree of detail than existing publications on the subject and shows that the NAF$_w$ scalar multiplication method with precomputations in affine coordinates, intermediate doublings in Jacobian coordinates and additions in mixed coordinates is the optimal choice. We compare our scalar multiplication scheme with the one implemented by IBM and conclude that a substantial improvement of efficiency is achieved by using our scheme. We implement our efficient scheme and support our conclusions with timings of the implementations. Side channel attacks using power analysis is considered to be a major threat against the security of ECC-systems. Mathematical countermeasures exist but reduce the performance of the system. So far, no comparison of the countermeasures has been published. We perform such a comparison and conclude that if a sufficient amount of storage is available, a combination of side channel atomicity and scalar randomization should be used as a countermeasure. If storage is limited, countermeasures should be based on a combination of Montgomery's ladder algorithm and scalar randomization. We specify side channel atomic elliptic curve operations on the NIST elliptic curves in mixed coordinates. So far, no such specifications have been published. We develop an efficient and secure scalar multiplication scheme and conclude that this scheme is more efficient than the scheme used in the IBM implementation, which provides no security against side channel attacks. We implement our efficient, secure scheme and support our conclusions with timings of the implementations.

We generalize the ElGamal signature scheme for cyclic groups to a signature scheme for n-dimensional vector spaces. The higher dimensional version is based on the untractability of the vector decomposition problem (VDP). Yoshida has shown that under certain conditions, the VDP on a two-dimensional vector space is at least as hard as the computational Diffie-Hellman problem (CDHP) on a one-dimensional subspace. (Added November 19: Steven Galbraith recently showed that for the examples that are used in the paper, the VDP is at most as hard as the Discrete Logarithm problem (DLP) on a one-dimensional subspace. This has as a consequence for the proposed signature scheme that the given examples provide the same security as (ordinary) Elliptic Curve DLP based signature schemes.)

A proxy blind signature combines the properties of proxy signature and blind signature. Recently, Awasthi and Lal proposed a more efficient proxy blind signature based on the proxy signature scheme proposed by Mambo et al.. Later, Sun et al. and Das et al. gave some attacks on Awasthi and Lal's scheme respectively. In this paper, we analyze the two attacks and we point out that those attacks do not apply to Awasthi and Lal's scheme.

We propose a new recursive technique to generate random numbers based on the theory of d-sequences which may be useful in many cryptographic applications requiring easily implementable RNGs.

As more sensitive data is shared and stored by third-party sites on the Internet, there will be a need to encrypt data stored at these sites. One drawback of encrypting data, is that it can be selectively shared only at a coarse-grained level (i.e., giving another party your private key). We develop a new cryptosystem for fine-grained sharing of encrypted data that we call Key-Policy Attribute-Based Encryption (KP-ABE). In our cryptosystem, ciphertexts are labeled with sets of attributes and private keys are associated with access structures that control which ciphertexts a user is able to decrypt. We demonstrate the applicability of our construction to sharing of audit-log information and broadcast encryption. Our construction supports delegation of private keys which subsumes Hierarchical Identity-Based Encryption (HIBE).

The focus of this paper is to design an efficient and secure solution addressing the key escrow problem in ID-based signature schemes, i.e., the Private Key Generator (PKG) knows the user's private key, which damages the essential requirement--``non-repudiation" property of signature schemes. In this paper, we proposed two ID-based threshold signature schemes, which both reach Girault's trusted level 3, and in which there exists only one PKG in our ID-based threshold signature schemes. In particular, the second scheme has another good property: it does not require trusting any particular party at any time. Compared with the previous schemes, our schemes do not need to compute pairings, which make them be more efficient than those schemes. Furthermore, our ID-based signature schemes increase the availability of the signing agency and the difficulty for the adversary to learn the private key.

This was a short note that deals with the design of Rainbow or ``stagewise unbalanced oil-and-vinegar'' multivariate signature schemes. We exhibit new cryptanalysis for current schemes that relates to flawed choices of system parameters in current schemes. These can be ameliorated according to an updated list of security design criteria.

In this paper we investigate a security model for Timed-Release Encryption schemes with Pre-Open Capability (TRE-PC schemes) proposed by Hwang, Yum, and Lee. Firstly, we show that the HYL model possesses a number of defects and fails to model some potentially practical security vulnerabilities faced by TRE-PC schemes. Secondly, we propose a new security model for TRE-PC schemes which models the securities against four kinds of attacker and avoids the defects of the HYL model. We also work out the complete relations among the security notions defined in the new model. Thirdly, we introduce the notion of TRE-PC-KEM, which is a special type of KEM, and show a way to construct a TRE-PC scheme using a TRE-PC-KEM and a DEM. Finally, we propose an instantiation of a TRE-PC-KEM and prove its security.

We describe algorithms for point multiplication on Koblitz curves using multiple-base expansions of the form $k = \sum \pm \tau^a (\tau-1)^b$ and $k= \sum \pm \tau^a (\tau-1)^b (\tau^2 - \tau - 1)^c.$ We prove that the number of terms in the second type is sublinear in the bit length of k, which leads to the first provably sublinear point multiplication algorithm on Koblitz curves. For the first type, we conjecture that the number of terms is sublinear and provide numerical evidence demonstrating that the number of terms is significantly less than that of $\tau$-adic non-adjacent form expansions. We present details of an innovative FPGA implementation of our algorithm and performance data demonstrating the efficiency of our method.

In this paper we introduce a new primitive called identity-based encryption with wildcards, or WIBE for short. It allows to encrypt messages to a whole range of users simultaneously whose identities match a certain pattern. This pattern is defined through a sequence of fixed strings and wildcards, where any string can take the place of a wildcard in a matching identity. Our primitive can be applied to provide an intuitive way to send encrypted email to groups of users in a corporate hierarchy. We propose a full security notion and give efficient implementations meeting this notion under different pairing-related assumptions, both in the random oracle model and in the standard model.

This paper presents a protocol aiming at proving that an encryption system contains structural weaknesses without disclosing any information on those weaknesses. A verifier can check in a polynomial time that a given property of the cipher system output has been effectively realized. This property has been chosen by the prover in such a way that it cannot been achieved by known attacks or exhaustive search but only if the prover indeed knows some unknown weaknesses that may effectively endanger the cryptosystem security. This protocol has been denoted {\em zero-knowledge-like proof of cryptanalysis}. In this paper, we apply this protocol to the Bluetooth core encryption algorithm E0, used in many mobile environments and thus we prove that its security can seriously be put into question.

We consider the problem of non-interactive message authentication using two channels: an insecure broadband channel and an authenticated narrow-band channel. This problem has been considered in the context of ad hoc networks, where it is assumed that there is neither a secret key shared among the two parties, nor a public-key infrastructure in place. We present a formal model for protocols of this type, along with a new protocol which is as efficient as the best previous protocols. The security of our protocol is based on a new property of hash functions that we introduce, which we name ``hybrid-collision resistance''.

We present in this paper a new approach for specific JPEG steganalysis and propose studying statistics of the compressed DCT coefficients. Traditionally, steganographic algorithms try to preserve statistics of the DCT and of the spatial domain, but they cannot preserve both and also control the alteration of the compressed data. We have noticed a deviation of the entropy of the compressed data after a first embedding. This deviation is greater when the image is a cover medium than when the image is a stego image. To observe this deviation, we pointed out new statistic features and combined them with the Multiple Embedding Method. This approach is motivated by the \textit{Avalanche Criterion} of the JPEG lossless compression step. This criterion makes possible the design of detectors whose detection rates are independent of the payload. Finally, we designed a Fisher discriminant based classifier for well known steganographic algorithms, Outguess, F5 and Hide and Seek. The experiemental results we obtained show the efficiency of our classifier for these algorithms. Moreover, it is also designed to work with low embedding rates $(<10^{-5})$ and according to the avalanche criterion of RLE and Huffman compression step, its efficiency is independent of the quantity of hidden information.

In this paper, we point out the security weaknesses of Chen et al.'s e-voting scheme.We give a modification which satisfies the security requirements of a e-voting scheme.

Pairing-based cryptosystems (PBC) have been attracted by researchers in cryptography. Some implementations show that PBC are relatively slower than the standard public key cryptosystems. We present an efficient implementation for computing Tate pairing on a mobile phone using Java. We implemented the $\eta_T$ pairing (a recent efficient variation of Duursma-Lee algorithm) over some finite fields of characteristic 3 with extension degree $m= \{ 97, 167, 193, 239 \}$. Our optimized implementation for $m=97$ achieved about 0.5 seconds for computing Tate pairing over FOMA SH901iS, NTT DoCoMo. Then our implementation of Tate pairing is compared in the same platform with other Java program of the standard cryptosystems, i.e., RSA cryptosystem and elliptic curve cryptosystem (ECC). The computation speed of Tate pairing is comparable to that of RSA or ECC on the same mobile device.

We introduce a simple primitive called Augmented Broadcast Encryption (ABE) that is sufficient for constructing broadcast encryption, traitor-tracing, and trace-and-revoke systems. These ABE-based constructions are resistant to an arbitrary number of colluders and are secure against adaptive adversaries. Furthermore, traitor tracing requires no secrets and can be done by anyone. These broadcast systems are designed for broadcasting to arbitrary sets of users. We then construct a secure ABE system for which the resulting concrete trace-and-revoke system has ciphertexts and private keys of size $\sqrt{N}$ where $N$ is the total number of users in the system. In particular, this is the first example of a fully collusion resistant broadcast system with sub-linear size ciphertexts and private keys that is secure against adaptive adversaries. The system is publicly traceable.

In most forward-secure signature constructions, a program that updates a user's private signing key must have full access to the private key. Unfortunately, these schemes are incompatible with several security architectures including Gnu Privacy Guard (GPG) and S/MIME, where the private key is encrypted under a user password as a ``second factor'' of security, in case the private key storage is corrupted, but the password is not. We introduce the concept of forward-secure signatures with untrusted update, where the key update can be performed on an encrypted version of the key. Forward secure signatures with untrusted update allow us to add forward security to signatures, while still keeping passwords as a second factor of security. We provide a construction that has performance characteristics comparable with the best existing forward-secure signatures. In addition, we describe how to modify the Bellare-Miner forward secure signature scheme to achieve untrusted update.

It has been demonstrated by Bellare, Neven, and Namprempre (Eurocrypt 2004) that identity-based signature schemes can be generically constructed from standard digital signature schemes. In this paper we consider the following natural extension: is there a generic construction of ``identity-based signature schemes with additional properties'' (such as identity-based blind signatures, verifiably encrypted signatures, ...) from standard signature schemes with the same properties? Our results show that this is possible for a number of properties including proxy signatures; (partially) blind signatures; verifiably encrypted signatures; undeniable signatures; forward-secure signatures; (strongly) key insulated signatures; online/offline signatures; threshold signatures; and (with some limitations) aggregate signatures. Using well-known results for standard signature schemes, we conclude that explicit identity-based signature schemes with additional properties can be constructed, enjoying sometimes better properties than specific schemes proposed until know. In particular, our work implies the existence of identity-based signatures with additional properties that are provably secure in the standard model, do not need bilinear pairings, or can be based on general assumptions.

Visual secret sharing scheme (VSSS) is a secret sharing method which decodes the secret by using the contrast ability of the human visual system. Autostereogram is a single two dimensional (2D) image which becomes a virtual three dimensional (3D) image when viewed with proper eye convergence or divergence. Combing the two technologies via human vision, this paper presents a new visual secret sharing scheme called (k, n)-VSSS with autostereogram. In the scheme, each of the shares is an autostereogram. Stacking any k shares, the secret image is recovered visually without any equipment, but no secret information is obtained with less than k shares.

We provide the first proof of security for MDC-2, the most well-known construction for turning an n-bit blockcipher into a 2n-bit cryptographic hash function.

We provide algorithms to solve the free riders problem in broadcast encryption. In this problem, the broadcast server is allowed to choose some small subset F of the revoked set R of users to allow to decrypt the broadcast, despite having been revoked. This may allow the server to significantly reduce network traffic while only allowing a small set of non-privileged users to decrypt the broadcast. Although there are worst-case instances of broadcast encryption schemes where the free riders problem is difficult to solve (or even approximate), we show that for many specific broadcast encryption schemes, there are efficient algorithms. In particular, for the complete subtree method and some other schemes in the subset-cover framework, we show how to find the optimal assignment of free riders in O(|R||F|) time, which is independent of the total number of users. We also define an approximate version of this problem, and study specific distributions of R for which this relaxation yields even faster algorithms. Along the way we develop the first approximation algorithms for the following problem: given two integer sequences a_1 >= a_2>= ... >= a_n and b_1 >= b_2 >= ... >= b_n, output for all i, an integer j' for which a_{j'} + b_{i-j'} <= (1+\epsilon) min_j a_j + b_{i-j}. We show that if the differences a_i - a_{i+1}, b_i-b_{i+1} are bounded, then there is an O(n^{4/3}/\epsilon^{2/3})-time algorithm for this problem, improving upon the O(n^2) time of the naive algorithm.

Multipartite secret sharing schemes are those having a multipartite access structure, in which the set of participants is divided into several parts and all participants in the same part play an equivalent role. In this work, the characterization of ideal multipartite access structures is studied with all generality. Our results are based on the well-known connections between ideal secret sharing schemes and matroids and on the introduction of a new combinatorial tool in secret sharing, integer polymatroids. Our results can be summarized as follows. First, we present a characterization of multipartite matroid ports in terms of integer polymatroids. As a consequence of this characterization, a necessary condition for a multipartite access structure to be ideal is obtained. Second, we use representations of integer polymatroids by collections of vector subspaces to characterize the representable multipartite matroids. In this way we obtain a sufficient condition for a multipartite access structure to be ideal, and also a unified framework to study the open problems about the efficiency of the constructions of ideal multipartite secret sharing schemes. Finally, we apply our general results to obtain a complete characterization of ideal tripartite access structures, which was until now an open problem.

{\it This note was written in 1997 after a talk I gave at the sëminaire de complexitë et cryptographie at the École Normale Supërieure\footnote{http://www.di.ens.fr/~wwwgrecc/Seminaire/1996-97.html} After it was rejected at crypto97 I forgot it until a few colleagues of mine informed me that it could be of some interest to some researchers in the field of algorithmic and cryptography. Although I am not quite happy with the redaction of this note, I believe it is more fair not to improve nor correct it yet. So I leave it in its original state, including misprints. I just added this introductory paragraph. If need be, I will publish an updated version later.} We introduce the notion of hard homogeneous space (HHS) and briefly develop the corresponding theory. We show that cryptographic protocols based on the discrete logarithm problem have a counterpart for any hard homogeneous space. Indeed, the notion of hard homogeneous space is a more general and more natural context for these protocols. We exhibit conjectural hard homogeneous spaces independant from any discrete logarithm problem. They are based on complex multiplication theory. This shows the existence of schemes for authentication and key exchange that do not rely on the difficulty of computing dicrete logarithm in any finite group nor factoring integers. We show that the concept of HHS fits with class field theory to provide a unified theory for the already used discrete logarithm problems (on multiplicative groups of finite fields or rational points on elliptic curves) and the HHS we present here. We discuss a few algorithmic questions related to hard homogeneous spaces. The paper is looking for a wider point of view on the discrete logarithm problem both mathematically and cryptographically.

MAC algorithms can provide cryptographically secure authentication services. One of the most popular algorithms in commercial applications is HMAC based on the hash functions MD5 or SHA-1. In the light of new collision search methods for members of the MD4 family including SHA-1, the security of HMAC based on these hash functions is reconsidered. We present a new method to recover both the inner- and the outer key used in HMAC when instantiated with a concrete hash function by observing text/MAC pairs. In addition to collisions, also other non-random properties of the hash function are used in this new attack. Among the examples of the proposed method, the first theoretical full key recovery attack on NMAC-MD5 is presented. Other examples are distinguishing, forgery and partial or full key recovery attacks on NMAC/HMAC-SHA-1 with a reduced number of steps (up to 61 out of 80). This information about the new, reduced security margin serves as an input to the selection of algorithms for authentication purposes.

We describe the first efficient ring signature scheme secure, without random oracles, based on standard assumptions. Our ring signatures are based in bilinear groups. For $l$ members of a ring our signatures consist of $2l+2$ group elements and require $2l+3$ pairings to verify. We prove our scheme secure in the strongest security model proposed by Bender, Katz, and Morselli: namely, we show our scheme to be anonymous against full key exposure and unforgeable with respect to insider corruption. A shortcoming of our approach is that all the users' keys must be defined in the same group.

This paper presents a new software side-channel attack - enabled by the branch prediction capability common to all modern high-performance CPUs. The penalty payed (extra clock cycles) for a mispredicted branch can be used for cryptanalysis of cryptographic primitives that employ a data-dependent program flow. Analogous to the recently described cache-based side-channel attacks our attacks also allow an unprivileged process to attack other processes running in parallel on the same processor, despite sophisticated partitioning methods such as memory protection, sandboxing or even virtualization. We will discuss in detail several such attacks for the example of RSA, and experimentally show their applicability to real systems, such as OpenSSL and Linux. More specifically, we will present four different types of attacks, which are all derived from the basic idea underlying our novel side-channel attack. Moreover, we also demonstrate the strength of the branch prediction side-channel attack by rendering the obvious countermeasure in this context (Montgomery Multiplication with dummy-reduction) as useless. Although the deeper consequences of the latter result make the task of writing an efficient and secure modular expeonentiation (or scalar multiplication on an elliptic curve) a challenging task, we will eventually suggest some countermeasures to mitigate branch prediction side-channel attacks.

We construct public-key systems that support comparison queries ($x \geq a)$ on encrypted data as well as more general queries such as subset queries $(x \in S)$. These systems also support arbitrary conjunctive queries ($P_1 \wedge \cdots \wedge P_\ell$) without leaking information on individual conjuncts. We present a general framework for constructing and analyzing public-key systems supporting queries on encrypted data.