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.

We propose a new computational complexity assumption from bilinear map, based on which we construct Verifier-Local Revocation group signatures with shorter lengths than previous ones.

Secure use of the BGLS aggregate signature schemes is restricted to the aggregation of distinct messages (for the basic scheme) or per-signer distinct messages (for the enhanced, prepend-public-key version of the scheme). We argue that these restrictions preclude interesting applications, make usage of the schemes error-prone and are generally undesirable in practice. Via a new analysis and proof, we show how the restrictions can be lifted, yielding the first truly unrestricted aggregate signature scheme. Via another new analysis and proof, we show that the distinct signer restriction on the sequential aggregate signature schemes of Lysyanskaya et al. can also be dropped, yielding an unrestricted sequential aggregate signature scheme. Finally, we present variants of these schemes with tight security reductions.

Protocols for group key exchange (GKE) are cryptographic algorithms that describe how a group of parties communicating over a public network can come up with a common secret key. Due to their critical role in building secure multicast channels, a number of GKE protocols have been proposed over the years in a variety of settings. However despite many impressive achievements, it still remains a challenging problem to design a secure GKE protocol which scales very well for large groups. Our observation is that all provably-secure constant-round GKE protocols providing forward secrecy thus far are not fully scalable, but have a computational complexity that scales only linearly in group size. Motivated by this observation, we propose a new GKE protocol that not only offers full scalability in all directions but also attains provable security against active adversaries. Full scalability is achieved by using a complete binary tree structure where users are arranged on both internal and leaf nodes. Security is proved via reduction to the decisional Diffie-Hellman assumption in a well-defined formal model of communication and adversarial capabilities.

Most cryptographic primitives require randomness (for example, to generate their secret keys). Usually, one assumes that perfect randomness is available, but, conceivably, such primitives might be built under weaker, more realistic assumptions. This is known to be true for many authentication applications, when entropy alone is typically sufficient. In contrast, all known techniques for achieving privacy seem to fundamentally require (nearly) perfect randomness. We ask the question whether this is just a coincidence, or, perhaps, privacy inherently requires true randomness? We completely resolve this question for the case of (information-theoretic) private-key encryption, where parties wish to encrypt a b-bit value using a shared secret key sampled from some imperfect source of randomness S. Our main result shows that if such n-bit source S allows for a secure encryption of b bits, where b>log n, then one can deterministically extract nearly b almost perfect random bits from S. Further, the restriction that b>log n is nearly tight: there exist sources S allowing one to perfectly encrypt (log n - loglog n) bits, but not to deterministically extract even a single slightly unbiased bit. Hence, to a large extent, *true randomness is inherent for encryption*: either the key length must be exponential in the message length b, or one can deterministically extract nearly b almost unbiased random bits from the key. In particular, the *one-time pad scheme is essentially universal*. Our technique also extends to related *computational* primitives which are perfectly-binding, such as perfectly-binding commitment and computationally secure private- or public-key encryption, showing the necessity to efficiently extract almost b *pseudorandom* bits.

Recently, Boneh, Gentry, and Waters '05 presented an efficient broadcast encryption, and Boneh, Sahai, and Waters '06 presented an efficient traitor tracing scheme. The former broadcast encryption result contains both a simpler chosen plaintext secure version and a more complicated but chosen ciphertext secure version. The latter traitor tracing scheme is only chosen plaintext secure. In this paper, we use the twin encryption technique of Naor and Yung '90 to add chosen ciphertext security to both papers. By``twinning", we extend the simpler chosen plaintext secure broadcast encryption to achieve chosen ciphertext security, and we extend the chosen plaintext secure traitor tracing to achieve chosen ciphertext security. We also extend both schemes to versions corresponding to threshold encryption which we call "broadcast threshold encryption" and "threshold-traitor tracing", i.e. tracing of threshold traitors. In these schemes, any $\theta$ un-revoked users can decrypt while $\theta-1$ users cannot. The tracing is to a set of $\theta$ users. We call this set a "threshold-traitor". Our broadcast threshold encryption is collusion resistant. Our threshold-traitor tracing is collusion resistant in its traceability.

There is a rarely mentioned foundational problem involving collision-resistant hash-functions: common constructions are keyless, but formal definitions are keyed. The discrepancy stems from the fact that a function H:{0,1}^* -> {0,1}^n always admits an efficient collision-finding algorithm, it's just that us human beings might be unable to write the program down. We explain a simple way to sidestep this difficulty that avoids having to key our hash functions. The idea is to state theorems in a way that prescribes an explicitly-given reduction, normally a black-box one. We illustrate this approach using well-known examples involving digital signatures, pseudorandom functions, and the Merkle-Damgard construction.

We extend the definitional work of Dwork, Naor and Sahai from deniable authentication to deniable key-exchange protocols. We then use these definitions to prove the deniability features of SKEME and SIGMA, two natural and efficient protocols which serve as basis for the Internet Key Exchange (IKE) protocol. The two protocols require distinct approaches to their deniability analysis, hence highlighting important definitional issues as well as necessitating different tools in the analysis. SKEME is an encryption-based protocol for which we prove full deniability based on the plaintext awareness of the underlying encryption scheme. Interestingly SKEME's deniability is possibly the first ``natural'' application which essentially requires plaintext awareness (until now this notion has been mainly used as a tool for proving chosen-ciphertext security); in particular this use of plaintext awareness is not tied to the random oracle model. SIGMA, on the other hand, uses non-repudiable signatures for authentication and hence cannot be proven to be fully deniable. Yet we are able to prove a weaker, but meaningful, ``partial deniability" property: a party may not be able to deny that it was ``alive" at some point in time but can fully deny the contents of its communications and the identity of its interlocutors. We remark that the deniability of SKEME and SIGMA holds in a concurrent setting and does not essentially rely on the random oracle model.

At Eurocrypt 2005, Waters proposed an efficient identity based encryption (IBE) scheme. One drawback of this scheme is that the size of the public parameter is rather large. Our first contribution is a generalization of Waters scheme. In particular, we show that there is an interesting trade-off between the tightness of the security reduction and smallness of the public parameter size. For a given security level, this implies that if one reduces the public parameter size there is a corresponding increase in the computational cost. This introduces a flexibility in choosing the public parameter size without compromising in security. In concrete terms, to achieve $80$-bit security for 160-bit identities we show that compared to Waters protocol the public parameter size can be reduced by almost $90 \%$ while increasing the computation cost by $30\%$. Our second contribution is to extend the IBE protocol to a hierarchical IBE (HIBE) protocol which can be shown to be secure in the full model without the use of random oracle. A previous construction of a HIBE in the same setting is due to Waters. Our construction improves upon Waters' suggestion by significantly reducing the number of public parameters.

This paper examines methods for formally proving the security of cryptographic schemes. We show that, despite many years of active research, there are fundamental problems which have yet to be solved. We also present a new approach to one of the more controversial aspects of provable security: the random oracle model.

This paper concerns the possibility of developing a coherent theory of security when feasibility is associated with expected probabilistic polynomial-time (expected PPT). The source of difficulty is that the known definitions of expected PPT strategies (i.e., expected PPT interactive machines) do not support natural results of the type presented below. To overcome this difficulty, we suggest new definitions of expected PPT strategies, which are more restrictive than the known definitions (but nevertheless extend the notion of expected PPT non-interactive algorithms). We advocate the conceptual adequacy of these definitions, and point out their technical advantages. Specifically, identifying a natural subclass of black-box simulators, called normal, we prove the following two results: (1) Security proofs that refer to all strict PPT adversaries (and are proven via normal black-box simulators), extend to provide security with respect to all adversaries that satisfy the restricted definitions of expected PPT. (2) Security composition theorems of the type known for strict PPT hold for these restricted definitions of expected PPT, where security means simulation by normal black-box simulators. Specifically, a normal black-box simulator is required to make an expected polynomial number of steps, when given oracle access to any strategy, where each oracle call is counted as a single step. This natural property is satisfies by most known simulators and is easy to verify.

We address the issue of encrypting data in local storage using a key that is derived from the user's password. The typical solution in use today is to derive the key from the password using a cryptographic hash function. This solution provides relatively weak protection, since an attacker that gets hold of the encrypted data can mount an off-line dictionary attack on the user's password, thereby recovering the key and decrypting the stored data. We propose an approach for limiting off-line dictionary attacks in this setting without relying on secret storage or secure hardware. In our proposal, the process of deriving a key from the password requires the user to solve a puzzle that is presumed to be solvable only by humans (e.g, a CAPTCHA). We describe a simple protocol using this approach: many different puzzles are stored on the disk, the user's password is used to specify which of them need to be solved, and the encryption key is derived from the password and the solutions of the specified puzzles. Completely specifying and analyzing this simple protocol, however, raises a host of modeling and technical issues, such as new properties of human-solvable puzzles and some seemingly hard combinatorial problems. Here we analyze this protocol in some interesting special cases.

We present PEP, which is a new construction of a tweakable strong pseudo-random permutation. PEP uses a hash-encrypt-hash approach which has recently been used in the construction of HCTR. This approach is different from the encrypt-mask-encrypt approach of constructions such as CMC, EME and EME$^*$. The general hash-encrypt-hash approach was earlier used by Naor-Reingold to provide a generic construction technique for an SPRP (but not a tweakable SPRP). PEP can be seen as the development of the Naor-Reingold approach into a fully specified mode of operation with a concrete security reduction for a tweakable strong pseudo-random permutation. The security bound of HCTR which is also based on the Naor-Reingold approach is weaker than that of PEP. Compared to previous known constructions, PEP is the only construction of tweakable SPRP which uses a single key, is efficiently parallelizable and can handle an arbitrary number of blocks.

Recently, Fang et al [24] proposed an improvement to Das et al's scheme [6] to prevent some weaknesses. Further, Chou et al [19] and Thulasi et al [23] pointed out some weakness of Das et al's scheme. However, the improvd scheme is still insecure to off-line attack. In this paper, we propose an improvement of their schemes that provides the better security compared to the schemes previously published. Further, proposed scheme enables users to choose and change their password by their own choices without the help of a remote server.

With the rapid spread of various mobile terminals in our society, the importance of secure positioning is growing for wireless networks in adversarial settings. Recently, several authors have proposed a secure positioning mechanism of mobile terminals which is based on the geometric property of wireless node placement, and on the postulate of modern physics that a propagation speed of information never exceeds the velocity of light. In particular, they utilize the measurements of the round-trip time of radio signal propagation and bidirectional communication for variants of the challenge-and-response. In this paper, we propose a novel means to construct the above mechanism by use of unidirectional communication instead of bidirectional communication. Our proposal is based on the assumption that a mobile terminal incorporates a high-precision inner clock in a tamper-resistant protected area. In positioning, the mobile terminal uses its inner clock and the time and location information broadcasted by radio from trusted stations. Our proposal has a major advantage in protecting the location privacy of mobile terminal users, because the mobile terminal need not provide any information to the trusted stations through positioning procedures. Besides, our proposal is free from the positioning error due to claimant's processing-time fluctuations in the challenge-and-response, and is well-suited for mobile terminals in the open air, or on the move at high speed, in terms of practical usage. We analyze the security, the functionality, and the feasibility of our proposal in comparison to previous proposals.

Random delays are commonly used as a countermeasure to inhibit side channel analysis and fault attacks in embedded devices. This paper proposes a different manner of generating random delays. The alternative proposed increases the desynchronisation compared to uniformly distributed random delays. It is also shown that it is possible to reduce the amount of time lost due to random delays, while maintaining the increased variation.

Blockwise-adaptive chosen-plaintext and chosen-ciphertext attack are new models for cryptanalytic adversaries, first discovered by Joux, et al [JMV02], and describe a vulnerability in SSH discovered by Bellare, et al [BKN02]. Unlike traditional chosen-plaintext (CPA) or chosen-ciphertext (CCA) adversaries, the blockwise adversary can submit individual blocks for encryption or decryption rather than entire messages. This paper focuses on the search for on-line encryption schemes which are resistant to blockwise-adaptive chosen-plaintext attack. We prove that one oracle query with non-equal inputs is sufficient to win the blockwise-adaptive chosen-plaintext game if the game can be won by any adversary in ppt with non-negligible advantage. In order to uniformly describe such encryption schemes, we define a canonical representation of encryption schemes based on functions believed to be pseudorandom (i.e. Block Ciphers). This Canonical Form is general enough to cover many modes currently in use, including ECB, CBC, CTR, OFB, CFB, ABC, IGE, XCBC, HCBC and HPCBC. An immediate result of the theorems in this paper is that CTR, OFB, CFB, HCBC and HPCBC are proven secure against blockwise-adaptive CPA, as well as S-ABC under certain conditions. Conversely ECB, CBC, IGE, and P-ABC are proven to be blockwise-adaptive CPA insecure. Since CBC, IGE and P-ABC are chosen-plaintext secure, this indicates that the blockwise-adaptive chosen-plaintext model is a non-trivial extension of the traditional chosen-plaintext attack model.

One of the most commonly used two-factor authentication mechanisms is based on smart card and user's password. Throughout the years, there have been many schemes proposed, but most of them have already been found flawed due to the lack of formal security analysis. On the cryptanalysis of this type of schemes, in this paper, we further review two recently proposed schemes and show that their security claims are invalid. To address the current issue, we propose a new and simplified property set and a formal adversarial model for analyzing the security of this type of schemes. We believe that the property set and the adversarial model themselves are of independent interest. We then propose a new scheme and a generic construction framework. In particular, we show that a secure password based key exchange protocol can be transformed efficiently to a smartcard and password based two-factor authentication scheme provided that there exist pseudorandom functions and collision-resistant hash functions.

Hermes8 is one of the stream ciphers submitted to the ECRYPT Stream Cipher Project (eSTREAM). In this paper we present an analysis of the Hermes8 stream ciphers. In particular, we show an attack on the latest version of the cipher (Hermes8F), which requires very few known keystream bytes and recovers the cipher secret key in less than a second on a normal PC. Furthermore, we make some remarks on the cipher's key schedule and discuss some properties of ciphers with similar algebraic structure to Hermes8.

KEM (Key Encapsulation Mechanism) was introduced by Shoup to formalize the asymmetric encryption specified for key distribution in ISO standards on public-key encryption. Shoup defined the ``semantic security (IND) against adaptively chosen ciphertext attacks (CCA2)'' as a desirable security notion of KEM. This paper introduces ''non-malleability (NM)'' of KEM, a stronger security notion than IND. We provide three definitions of NM, and show that these three definitions are equivalent. We then show that NM-CCA2 KEM is equivalent to IND-CCA2 KEM. That is, we show that NM is equivalent to IND under CCA2 attacks, although NM is stronger than IND in the definition (or under some attacks like CCA1). In addition, this paper defines the universally composable (UC) security of KEM and shows that NM-CCA2 KEM is equivalent to UC KEM.

We show how to significantly speed-up the encryption portion of some public-key cryptosystems by the simple expedient of allowing a sender to maintain state that is re-used across different encryptions. In particular we present stateful versions of the DHIES and Kurosawa-Desmedt schemes that each use only one exponentiation to encrypt, as opposed to two and three respectively in the original schemes, yielding the fastest discrete-log based public-key encryption schemes known in the random-oracle and standard models respectively. The schemes are proven to meet an appropriate extension of the standard definition of IND-CCA security that takes into account novel types of attacks possible in the stateful setting.

We present a novel approach for proving secrecy properties of security protocols by mechanized flow analysis. In contrast to existing tools for proving secrecy by abstract interpretation, our tool enjoys cryptographic soundness in the strong sense of blackbox reactive simulatability/UC which entails that secrecy properties proven by our tool are automatically guaranteed to hold for secure cryptographic implementations of the analyzed protocol, with respect to the more fine-grained cryptographic secrecy definitions and adversary models. Our tool is capable of reasoning about a comprehensive language for expressing protocols, in particular handling symmetric encryption and asymmetric encryption, and it produces proofs for an unbounded number of sessions in the presence of an active adversary. We have implemented the tool and applied it to a number of common protocols from the literature.

The KEM/DEM hybrid encryption paradigm combines the efficiency and large message space of secret key encryption with the advantages of public key cryptography. Due to its simplicity and flexibility, the approach has ever since gained increased popularity and has been successfully adapted in encryption standards. In hybrid public key encryption (PKE), first a key encapsulation mechanism (KEM) is used to fix a random session key that is then fed into a highly efficient data encapsulation mechanism (DEM) to encrypt the actual message. A composition theorem states that if both the KEM and the DEM have the highest level of security (i.e. security against chosen-ciphertext attacks), then so does the hybrid PKE scheme. It is not known if these strong security requirements on the KEM and DEM are also neccessary, nor if such general composition theorems exist for weaker levels of security. In this work we study neccessary and sufficient conditions on the security of the KEM and the DEM in order to guarantee a hybrid PKE scheme with a certain given level of security. More precisely, using nine different security notions for KEMs, ten for DEMs, and six for PKE schemes we completely characterize which combinations lead to a secure hybrid PKE scheme (by proving a composition theorem) and which do not (by providing counterexamples). Furthermore, as an independent result, we revisit and extend prior work on the relation among security notions for KEMs and DEMs.

Recently Bernstein has provided a simpler proof of unpredictability of CBC construction which is giving insight of the construction. Unpredictability of any function intuitively means that the function behaves very closely to a uniform random function. In this paper we make a unifying and simple approach to prove unpredictability of many existing constructions. We first revisit Bernstein's proof. Using this idea we can show a simpler proof of unpredictability of a class of DAG based construction, XCBC, TMAC, OMAC and PMAC. We also provide a simpler proof for stronger bound of CBC and a simpler proof of security of on-line Hash-CBC. We note that there is a flaw in the original security proof of Hash-CBC. This paper will help to understand security analysis of unpredictability of many constructions in a simpler way.

With the exception of the recently proposed class of cascaded dynamic convolutional cryptosystems, all the symmetric cryptosystems studied so far in the literature are static, in the sense that their structure do not change at all during encryption/decryption. In this paper, we propose and analyze a new class of dynamic symmetric cryptosystems, called automata-based dynamic convolutional cryptosystems (ADCCs). The paper is organized as follows. First, we provide the reader with a brief introduction to convolutional codes. Second, we give the definition of an ADCC, and then show how to use such a cryptosystem for encryption/decryption. Third, we provide a thorough security analysis of ADCCs, and then discuss their practical advantages. The conclusion of our cryptanalysis is that an ADCC is very hard to break completely, but quite easy to break partially. Fourth, an extension of ADCCs, called nonlinear cascaded ADCCs, is proposed and shown to be much more secure in practice than ADCCs. Finally, an efficient FPGA implementation of nonlinear cascaded ADCCs is presented.

This thesis is about a breadth-first exploration of logical concepts in cryptography and their linguistic abstraction and model-theoretic combination in a comprehensive logical system, called CPL (for Cryptographic Protocol Logic). We focus on two fundamental aspects of cryptography. Namely, the security of communication (as opposed to security of storage) and cryptographic protocols (as opposed to cryptographic operators). The primary logical concepts explored are the following: the modal concepts of belief, knowledge, norms, provability, space, and time. The distinguishing feature of CPL is that it unifies and refines a variety of existing approaches. This feature is the result of our wholistic conception of property-based (modal logics) and model-based (process algebra) formalisms.

We show in this paper how to apply well known methods from sparse linear algebra to the problem of computing the immunity of a Boolean function against algebraic or fast algebraic attacks. For an $n$-variable Boolean function, this approach gives an algorithm that works for both attacks in $O(n2^{n} D)$ complexity and $O(n2^n)$ memory. Here $D = \binom{n}{d}$ and $d$ corresponds to the degree of the algebraic system to be solved in the last step of the attacks. For algebraic attacks, our algorithm needs significantly less memory than the algorithm in \cite{ACGKMR06} with roughly the same time complexity (and it is precisely the memory usage which is the real bottleneck of the last algorithm). For fast algebraic attacks, it does not only improve the memory complexity, it is also the algorithm with the best time complexity known so far for most values of the degree constraints.

Game hopping is a method for proving the security of a cryptographic scheme. In a game hopping proof, we observe that an attacker running in a particular attack environment has an unknown probability of success. We then slowly alter the attack environment until the attackers success probability can be computed. We also bound the increase in the attacker's success probability caused by the changes to the attack environment. Thus, we can deduce a bound for the attacker's success probability in the original environment. Currently, there are three known ``types'' of game hop: transitions based on indistinguishability, transitions based on failure events, and bridging steps. This note introduces a fourth type of game hop.

Consider an electronic election scheme implemented using a mix-net; a large number of voters submit their votes and then a smaller number of servers compute the result. The mix-net accepts an encrypted vote from each voter and outputs the set of votes in sorted order without revealing the permutation used. To ensure a fair election, the votes of corrupt voters should be independent of the votes of honest voters, i.e., some type of non-malleability or plaintext awareness is needed. However, for efficiency reasons the servers typically expect inputs from some homomorphic cryptosystem, which is inherently malleable. In this paper we consider the problem of how non-malleability can be guaranteed in the submission phase and still allow the servers to start their computation with ciphertexts of the appropriate homomorphic cryptosystem. This can clearly be achieved using general techniques, but we would like a solution which is: (1) provably secure under standard assumptions, (2) non-interactive for the submitting parties, (3) very efficient for all parties in terms of computation and communication. We give the first solution to this problem which has all these properties. Our solution is surprisingly simple and can be based on various Cramer-Shoup cryptosystems. To capture its security properties we introduce a variation of CCA2-security.

We present attacks against two cognitive authentication schemes [W06] recently proposed at the 2006 IEEE Symposium on Security and Privacy. These authentication schemes are designed to be secure against eavesdropping attacks while relying only on human cognitive skills. They achieve authentication via challenge response protocols based on a shared secret set of pictures. Our attacks use a SAT solver to recover a user's key in a few seconds, after observing only a small number of successful logins. These attacks demonstrate that the authentication schemes of [W06] are not secure against an eavesdropping adversary.

Efficient halving of divisor classes offers the possibility to improve scalar multiplication on hyperelliptic curves and is also a step towards giving hyperelliptic curve cryptosystems all the features that elliptic curve systems have. We present a halving algorithm for divisor classes of genus 2 curves over finite fields of characteristic 2. We derive explicit halving formulae from a doubling algorithm by reversing this process. A family of binary curves, that are not known to be weak, is covered by the proposed algorithm. Compared to previous known halving algorithms, we achieve a noticeable speed-up for this family of curves.

One of the central questions in Cryptography is to design round-efficient protocols that are secure under man-in-the-middle attacks. In this paper we introduce and study the notion of non-malleable witness indistinguishability (NMWI) and examine its relation with the classic notion of non-malleable zero knowledge (NMZK). Indeed, despite tremendous applicability of witness indistinguishability, while a lot of attention has been given to NMZK, very little attention has been given to witness indistinguishability in case of man-in-the-middle attacks. We initiate this study, with several (perhaps somewhat surprising) results: 1) We give the first definition of NMWI proof systems. Just like every NMZK proof is a zero-knowledge proof which aims to attain a very strong proof independence property, we require (and formalize) the notion that every NMWI proof is a witness indistinguishable proof system which enjoys a very strong witness independence property against any man-in-the-middle attack. 2) We show the existence of a constant-round NMWI argument system for NP in the standard model (i.e. without any trusted or any other setup assumptions). 3) It is known that every zero-knowledge (ZK) argument is also a witness indistinguishable (WI) argument, but not vice-versa, i.e. ZK is not contained in WI. Rather surprisingly, we show that NMWI and NMZK argument systems are incomparable. That is, we show that there exists a NMZK argument system that is not a NMWI argument system and we also show that there is a NMWI argument system that is not a NMZK argument system. 4) We show that our constant-round NMWI argument system is also secure under a concurrent man-in-the-middle attack, i.e., it is a concurrent constant-round NMWI argument system. This is somewhat surprising since the question of a constant-round concurrent NMZK argument system is still open. 5) We then turn our attention to Bare Public-Key (BPK) model. We show how to expand upon our concurrent NMWI result in the plain model to obtain a constant-round concurrent NMZK argument system for any NP language in the BPK model.

Identity-based cryptosystems have an inherent key escrow issue, that is, the Key Generation Center (KGC) always knows user secret key. If the KGC is malicious, it can always impersonate the user. Certificateless cryptography, introduced by Al-Riyami and Paterson in 2003, is intended to solve this problem. However, in all the previously proposed certificateless schemes, it is always assumed that the malicious KGC starts launching attacks (so-called Type II attacks) only after it has generated a master public/secret key pair honestly. In this paper, we propose new security models that remove this assumption for both certificateless signature and encryption schemes. Under the new models, we show that a class of certificateless encryption and signature schemes proposed previously are insecure. These schemes still suffer from the key escrow problem. On the other side, we also give new proofs to show that there are two generic constructions, one for certificateless signature and the other for certificateless encryption, proposed recently that are secure under our new models.

Several standard cryptographic hash functions were broken in 2005. Some essential building blocks of these attacks lend themselves well to automation by encoding them as CNF formulas, which are within reach of modern SAT solvers. In this paper we demonstrate effectiveness of this approach. In particular, we are able to generate full collisions for MD4 and MD5 given only the differential path and applying a (minimally modified) off-the-shelf SAT solver. To the best of our knowledge, this is the first example of a SAT-solver-aided cryptanalysis of a non-trivial cryptographic primitive. We expect SAT solvers to find new applications as a validation and testing tool of practicing cryptanalysts.

The discrete logarithm problem (DLP) generalizes to the constrained DLP, where the secret exponent $x$ belongs to a set known to the attacker. The complexity of generic algorithms for solving the constrained DLP depends on the choice of the set. Motivated by cryptographic applications, we study sets with succinct representation for which the constrained DLP is hard. We draw on earlier results due to Erdös et~al. and Schnorr, develop geometric tools such as generalized Menelaus' theorem for proving lower bounds on the complexity of the constrained DLP, and construct sets with succinct representation with provable non-trivial lower bounds.

Key agreement protocols are a fundamental building block for ensuring authenticated and private communications between two parties over an insecure network. This paper focuses on key agreement protocols in the asymmetric authentication model, wherein parties hold a public/private key pair. In particular, we consider a type of known key attack called key compromise impersonation that may occur once the adversary has obtained the private key of an honest party. This attack represents a subtle threat that is often underestimated and difficult to counter. Several protocols are shown vulnerable to this attack despite their authors claiming the opposite. We also consider in more detail how three formal (complexity-theoretic based) models of distributed computing found in the literature cover such attacks.

Solving a dense linear system of boolean equations is the final step of several cryptanalytic attacks. Examples include stream cipher cryptanalysis via XL and related algorithms, integer factorization, and attacks on the HFE public-key cryptosystem. While both Gaussian Elimination and Strassen’s Algorithm have been proposed as methods, this paper specifies an algorithm that is much faster than both in practice. Performance is formally modeled, and experimental running times are provided, including for the optimal setting of the algorithm’s parameter. The consequences for published attacks on systems are also provided. The algorithm is named Method of Four Russians for Inversion (M4RI), in honor of the matrix multiplication algorithm from which it emerged, the Method of Four Russians Multiplication (M4RM).

CTC is a toy cipher designed by Courtois in order to prove the strength of algebraic attacks. In this paper we study the differential and the linear behavior of the 85 S-boxes version, which is attacked using algebraic techniques faster than exhaustive key search. We show that an $n$-round variant of the cipher can be attacked by a linear attack using only $2^{2n+2}$ known plaintexts, with a negligible time complexity. We conclude that CTC is insecure, even for quite a large number of rounds. We note that our observations can be probably used to devise other attacks that exploit the relatively slow diffusion of CTC.

The existence of $9$-variable Boolean functions having nonlinearity strictly greater than $240$ has been shown very recently (May 2006) by Kavut, Maitra and Yücel. The functions with nonlinearity 241 have been identified by a heuristic search in the class of Rotation Symmetric Boolean Functions (RSBFs). In this paper we efficiently perform the exhaustive search to enumerate the 9-variable RSBFs having nonlinearity $> 240$ and found that there are such functions with nonlinearity 241 only and there is no RSBF having nonlinearity $> 241$. Our search enumerates $8 \times 189$ many 9-variable RSBFs having nonlinearity 241. We further show that there are only two functions which are different up to the affine equivalence. Towards the end we explain the coding theoretic significance of these functions.

Frey proposed the idea of `disguising' an elliptic curve. This is a method to obtain a `black box' representation of a group. We adapt this notion to finite fields and tori and study the question of whether such systems are secure. Our main result is an algebraic attack which shows that it is not secure to disguise the torus $T_2$. We also show that some methods for disguising an elliptic curve are not secure. Finally, we present a method to disguise an elliptic curve which seems to resist our algebraic attack.

Aimed at computer scientists, this "how to" describes a method (with detailed algorithms) that allows to compute the factors of a class polynomial over the genus field. Though we only consider polynomials having real factors over the genus field, it is not difficult to adapt the method so that it works when these factors are complex.

We discuss the general theoretical ideas of the possibility using cryptosystems based on the partial differential equations (PDE) and the role of inverse scattering problem for the cryptanalysis as the possible way to the postquantum cipher scheme. An application of the nonlinear Schrödinger equation and optical fibre technology in cryptology is presented.

Key issuing protocols deal with overcoming the two inherent problems: key escrow and secure channel requirement of the identity based cryptosystems. An efficient key issuing protocol enables the identity based cryptosystems to be more acceptable and applicable in the real world. We present a secure and efficient threshold key issuing protocol. In our protocol, neither KGC nor KPA can impersonate the users to obtain the private keys and thus it achieves the trust level III \cite{girault}. The protocol is secure against replay, man-in-the-middle and insider attacks.

The length-based approach is a heuristic for solving randomly generated equations in groups which possess a reasonably behaved length function. We describe several improvements of the previously suggested length-based algorithms, that make them applicable to Thompson's group with significant success rates. In particular, this shows that the Shpilrain-Ushakov public key cryptosystem based on Thompson's group is insecure, and suggests that no practical public key cryptosystem based on this group can be secure.

Pairings on elliptic curves have been used as cryptographic primitives for the development of new applications such as identity based schemes. For the practical applications, it is crucial to provide efficient and secure implementations of the pairings. There have been several works on efficient implementations of the pairings. However, the research for secure implementations of the pairings has not been thoroughly investigated. In this paper, we investigate vulnerability of the pairing used in some pairing based protocols against side channel attacks. We propose an efficient algorithm secure against such side channel attacks of the eta pairing using randomized projective coordinate systems for the pairing computation.

In this paper, we prove the probability advantages of two linear expressions which are summarized from the ABC stream cipher submitted to ECRPYT Estream Project. Two linear expressions with probability advantages reflect the linear correlations among Modular Addition equations. Corresponding to each linear expression and its advantage, a large amount of weak keys are derived under which all the ABC main keys can be retrieved successively. The first linear expression is a generic bit linear correlation between two Modular Addition equations. The second is a linear correlation of bit carries derived from three Modular Addition equations and the linear equation of LFSR in ABC. It is remarked that the second is found by Wu and Preneel, and has been used to find $2^{96}$ weak keys. In the cryptanalysis of ABC, Wu and Preneel only utilized its estimated probability advantage which is concluded by experimental data, and they did not give its strict proof. Modular Addition and XOR operations are widely used in designing symmetric ciphers. We believe that these types of linear expressions with probability advantages not only can be used to analyze some other symmetric ciphers, but also are important criteria in designing secure symmetric ciphers.

We investigate definitions of security for previously proposed schemes for electronic cash and strengthen them so that the bank does need to be trusted to the same extent. We give an experiment-based definition for our stronger notion and show that they imply security in the framework for Universal Composability. Finally we propose a scheme secure under our definition in the common reference string (CRS) model under the assumption that trapdoor permutations exist. As a tool we define and prove the existence of simulation-sound non-interactive zero-knowledge proofs (NIZK-PK) in the CRS-model under the assumption that a family of trapdoor permutations exists.

In this paper we present a $p$-adic algorithm to compute the zeta function of a nondegenerate curve over a finite field using Monsky-Washnitzer cohomology. The paper vastly generalizes previous work since all known cases, e.g. hyperelliptic, superelliptic and $C_{ab}$ curves, can be transformed to fit the nondegenerate case. For curves with a fixed Newton polytope, the property of being nondegenerate is generic, so that the algorithm works for almost all curves with given Newton polytope. For a genus $g$ curve over $\FF_{p^n}$, the expected running time is $\widetilde{O}(n^3 g^6 + n^2 g^{6.5})$, whereas the space complexity amounts to $\widetilde{O}(n^3 g^4)$, assuming $p$ is fixed.

In this paper we resolve an open problem regarding resettable zero knowledge in the bare public-key (BPK for short) model: Does there exist constant round resettable zero knowledge argument with concurrent soundness for $\mathcal{NP}$ in BPK model without assuming \emph{sub-exponential hardness}? We give a positive answer to this question by presenting such a protocol for any language in $\mathcal{NP}$ in the bare public-key model assuming only collision-resistant hash functions against \emph{polynomial-time} adversaries.

A secure index search protocol makes it possible to search for the index of encrypted documents using specified keywords without decrypting them. %An untrusted database manager learns nothing more %than the search result about the documents without revealing the %keyword. These days, personally portable devices of huge storage such as a USB are easily used and hence private and sensitive documents of a user may be securely kept in such personal devices. However, secret documents shared by groups are usually stored in database. In real organizations such as government offices or enterprises with many departments, a group search occurs more often. In this paper, we propose two search schemes for a hierarchical group under an untrusted server ; A security-centered search scheme(SSIS) and an optimized efficient search scheme(ESIS) for commercial business use. We define `correlation resistance' as privacy requirement over encrypted search system and prove that SSIS can meet the notion. Also, we experimented two our proposed schemes. In the first try, the performance of both schemes was not good to use for practical business use. It was not until examining the reason of this that we learned the efficient DB schema must be applied into the search system for good performance. However, it was hard to apply efficient DB schema into SSIS because of its data structure. Hence, we applied efficient DB schema into only ESIS. The experiments show that ESIS is approximately 200 times faster than SSIS, which implies that other existing schemes are also not practical because the data structure of them is similar to SSIS. ESIS achieves real practicabilty by loosening its security, but with at least extend. Therefore, in the near future, it's required to develop keyword search system over encrypted data which is secure and applicable to efficient DB schema. In addition, we learned a lesson that works about the efficiency must consider mutual interactive operation with application layer as well as computational efficiency of a proposing scheme.

We present an investigation into the security of three practical pairing algorithms; the Tate, Eta and Ate pairing, in terms of side channel vulnerability. These three algorithms have recently shown to be efficiently computable on the resource constrained smart card, yet no in depth side channel analysis has yet appeared in the literature. Since the secret parameter input to the pairing can potentially be entered in either of the two possible positions, there exist two avenues of attack, i.e. e(P,Q) or e(Q,P) where P is public and Q is private. We analyse the core operations fundamental to pairings and not only highlight how each implementation may potentially succumb to a side channel attack, but also show how one path is more susceptible than the other in Tate and Ate. For those who wish to deploy pairing based systems we make a simple suggestion to improve resistance to side channel attacks.

Efficient authentication is one of important security requirements in mobile ad hoc network (MANET) routing systems. The techniques of digital signatures are generally considered as the best candidates to achieve strong authentication. However, using normal digital signature schemes is too costly to MANET due to the computation overheads. Considering the feasibility of incorporating digital signatures in MANET, we incorporate the notion of online/offline signatures, where the computational overhead is shifted to the offline phase. However, due to the diversity of different routing protocols, a universal scheme that suits all MANET routing systems does not exist in the literature. Notably, an authentication scheme for the AODV routing is believed to be not suitable to the DSR routing. In this paper, we first introduce an efficient ID-based online/offline scheme for authentication in AODV and then provide a formal transformation to convert the scheme to an ID-based online/offline multisignature scheme. Our scheme is unique, in the sense that a single ID-based online/offline signature scheme can be applied to both AODV and DSR routing protocols. We provide the generic construction as well as the concrete schemes to show an instantiation of the generic transformation. We also provide security proofs for our schemes based on the random oracle model. Finally, we provide an application of our schemes in the dynamic source routing protocol.

Let $N=pq$ be an RSA modulus where $p$, $q$ are large primes of the same bitsize and $\phi(N)=(p-1)(q-1)$. We study the class of the public exponents $e$ for which there exist integers $X$, $Y$, $Z$ satisfying $$eX+\phi(N)Y=NZ,$$ with $\vert XY\vert <{\sqrt{2}\over 6}N^{1\over 2}$ and all prime factors of $\vert Y\vert$ are less than $10^{40}$. We show that these exponents are of improper use in RSA cryptosystems and that their number is at least $O\left(N^{{1\over 2}-\e}\right)$ where $\e$ is a small positive constant. Our method combines continued fractions, Coppersmith's lattice-based technique for finding small roots of bivariate polynomials and H. W. Lenstra's elliptic curve method (ECM) for factoring.

Recently, Juels and Weis defined strong privacy for RFID tags. We add to this definition a completeness and a soundness requirement, i.e., a reader should accept valid tags and only such tags. For the case where tags hold independent keys, we prove a conjecture by Juels and Weis, namely in a strongly private and sound RFID system using only symmetric cryptography, a reader must access virtually all keys in the system when reading a tag. It was already known from work by Molnar et al. that when keys are dependent, the reader only needs to access a logarithmic number of keys, but at a cost in terms of privacy: for that system, strong privacy is lost if an adversary corrupts only a single tag. We propose protocols offering a new range of tradeoffs between security and efficiency. For instance the number of keys accessed by a reader to read a tag can be significantly smaller than the number of tags while retaining security, as long as we assume suitable limitations on the adversary.

In this paper we propose the group of unitriangular matrices over a finite field as a non-abelian group and composition of inner, diagonal and central automorphisms as a group of automorphisms for the MOR cryptosystem.

We propose to verify the AKS algorithm identities not for sequential integers, but for integers which are sequentially squared. In that case a number of elements, for which the identities are valid, doubles.

A coupon is an electronic data that represents the right to access a service provided by a service provider (e.g. gift certificates or movie tickets). Recently, a privacy-protecting multi-coupon system that allows a user to withdraw a predefined number of single coupons from the service provider has been proposed by Chen et al. at Financial Crypto 2005. In this system, every coupon has the same value which is predetermined by the system. The main drawbacks of Chen et al. proposal are that the redemption protocol of their system is inefficient, and that no formal security model is proposed. In this paper, we consequently propose a formal security model for coupon systems and design a practical multi-coupon system with new features: the quantity of single coupons in a multi-coupon is not defined by the system and the value of each coupon is chosen in a predefined set of values.

Starting with Shoup's seminal paper [24], the generic group model has been an important tool in reductionist security arguments. After an informal explanation of this model and Shoup's theorem, we discuss the danger of flaws in proofs. We next describe an ontological difference between the generic group assumption and the random oracle model for hash functions. We then examine some criticisms that have been leveled at the generic group model and raise some questions of our own.

We discuss the question of how to interpret reduction arguments in cryptography. We give some examples to show the subtlety and difficulty of this question.

We prove the equivalence of two definitions of non-malleable encryption, one based on the simulation approach of Dolev, Dwork and Naor and the other based on the comparison approach of Bellare, Desai, Pointcheval and Rogaway. Our definitions are slightly stronger than the original ones. The equivalence relies on a new characterization of non-malleable encryption in terms of the standard notion of indistinguishability of Goldwasser and Micali. We show that non-malleability is equivalent to indistinguishability under a ``parallel chosen ciphertext attack,'' this being a new kind of chosen ciphertext attack we introduce, in which the adversary's decryption queries are not allowed to depend on answers to previous queries, but must be made all at once. This characterization simplifies both the notion of non-malleable encryption and its usage, and enables one to see more easily how it compares with other notions of encryption. The results here apply to non-malleable encryption under any form of attack, whether chosen-plaintext, chosen-ciphertext, or adaptive chosen-ciphertext.

RFID-Tags are small devices used for identification purposes in many applications nowadays. It is expected that they will enable many new applications and link the physical and the virtual world in the near future. Since the processing power of these devices is low, they are often in the line of fire when their security and privacy is concerned. It is widely believed that devices with such constrained resources can not carry out sufficient cryptographic operations to guarantee security in new applications. In this paper, we show that identification of RFID-Tags can reach high security levels. In particular, we show how secure identification protocols based on the DL problem on elliptic curves are implemented on a constrained device such as an RFID-Tag requiring between 8500 and 14000 gates, depending on the implementation characteristics. We investigate the case of elliptic curves over $F_{2^p}$ with p prime and over composite fields $F_{2^{2p}}$. The implementations in this paper make RFID-Tags suitable for anti-counterfeiting purposes even in the off-line setting.

At Eurocrypt 2004, Chen, Kudla and Paterson introduced the concept of {\it concurrent signatures}, which allows two parties to produce two ambiguous signatures until an extra piece of information (called {\it keystone}) is released by the initial signer. Once the keystone is released publicly, both signatures are binding to their true signers {\it concurrently}. At ICICS 2004, Susilo, Mu and Zhang further proposed {\it perfect concurrent signatures} to strengthen the ambiguity of concurrent signatures. That is, even the both signers are known having issued one of the two ambiguous signatures, any third party is still unable to deduce who signed which signature, different from Chen et al.'s scheme. However, this paper points out that Susilo et al.'s two perfect concurrent signatures are actually {\it not} concurrent signatures. Specifically, we identify an attack that enables the initial signer to release a carefully prepared keystone that binds the matching signer's signature, but not the initial signer's. Therefore, both of their two schemes are {\it unfair} for the matching signer. Moreover, we present a simple but effective way to avoid this attack such that the improved schemes are truly perfect concurrent signatures.

A time-bound hierarchical key assignment scheme is a method to assign time-dependent encryption keys to a set of classes in a partially ordered hierarchy, in such a way that each class can compute the keys of all classes lower down in the hierarchy, according to temporal constraints. In this paper we design and analyze time-bound hierarchical key assignment schemes which are provably-secure and efficient. We consider both the unconditionally secure and the computationally secure settings and distinguish between two different goals: security with respect to key indistinguishability and against key recovery. We first present definitions of security with respect to both goals in the unconditionally secure setting and we show tight lower bounds on the size of the private information distributed to each class. Then, we consider the computational setting and we further distinguish security against static and adaptive adversarial behaviors. We explore the relations between all possible combinations of security goals and adversarial behaviors and, in particular, we prove that security against adaptive adversaries is (polynomially) equivalent to security against static adversaries. Afterwards, we prove that a recently proposed scheme is insecure against key recovery. Finally, we propose two different constructions for time-bound key assignment schemes. The first one is based on symmetric encryption schemes, whereas, the second one makes use of bilinear maps. Both constructions support updates to the access hierarchy with local changes to the public information and without requiring any private information to be re-distributed. These appear to be the first constructions for time-bound hierarchical key assignment schemes which are simultaneously practical and provably-secure.

In this work we generalize the classical Karatsuba Algorithm (KA) for polynomial multiplication to (i) polynomials of arbitrary degree and (ii) recursive use. We determine exact complexity expressions for the KA and focus on how to use it with the least number of operations. We develop a rule for the optimum order of steps if the KA is used recursively. We show how the usage of dummy coefficients may improve performance. Finally we provide detailed information on how to use the KA with least cost, and also provide tables that describe the best possible usage of the KA for polynomials up to a degree of 127. Our results are especially useful for efficient implementations of cryptographic and coding schemes over fixed-size fields like $GF(p^m)$.

Firstly, we demonstrate a pathological hash function choice that makes RSA-OAEP insecure. This shows that at least some security property is necessary for the hash functions used in RSA-OAEP. Nevertheless, we conjecture that only some very minimal security properties of the hash functions are actually necessary for the security of RSA-OAEP. Secondly, we consider certain types of reductions that could be used to prove the OW-CPA (i.e., the bare minimum) security of RSA-OAEP. We apply metareductions that show if such reductions existed, then RSA-OAEP would be OW-CCA2 insecure, or even worse, that the RSA problem would solvable. Therefore, it seems unlikely that such reductions could exist. Indeed, no such reductions proving the OW-CCA2 security of RSA-OAEP exist.

In this paper we view interleaved Gabidulin codes and describe how to correct errors up to a rank equal to the amount of redundancy of the code with high probability. We give a detailed proof for our estimation of the probability of correct decoding. In a second part, we view the application to variants of the GPT cryptosystem. For GGPT this leads to an efficient attack on the remaining secure instances, whereas it allows to derive at least partial information of the plaintext in the case of RRC-GPT.