Previous definitions of designated confirmer signatures in the literature are incomplete, and the proposed security definitions fail to capture key security properties, such as unforgeability against malicious confirmers and non-transferability. We propose new definitions. Previous schemes rely on the random oracle model or set-up assumptions, or are secure with respect to relaxed security definitions. We construct a practical scheme that is provably secure with respect to our security definition under the strong RSA-assumption, the decision composite residuosity assumption, and the decision Diffie-Hellman assumption. To achieve our results we introduce several new relaxations of standard notions. We expect these techniques to be useful in the construction and analysis of other efficient cryptographic schemes.

We describe a practical identity-based encryption scheme that is secure in the standard model against chosen-ciphertext (CCA2) attacks. Security is based on an assumption comparable to (but slightly stronger than) Bilinear Decisonal Diffie-Hellman (BDDH). A comparison shows that our construction outperforms all known identity-based encryption schemes in the standard model and its performance is even comparable with the one from the random-oracle based Boneh/Franklin IBE scheme. Our proposed IBE scheme has furthermore the property that it fulfills some notion of ``redundancy-freeness", i.e. the encryption algorithm is not only a probabilistic injection but also a surjection. As a consequence the ciphertext overhead is nearly optimal: to encrypt $k$ bit messages for $k$ bit identities and with $k$ bit randomness we get $3k$ bit ciphertexts to guarantee (roughly) $k$ bits of security.

Modular arithmetic with prime moduli has been crucial in present day cryptography. The primes of Mersenne, Solinas, Crandall and the so called IKE-MODP have been extensively used in efficient implementations. In this paper we study the density of primes with binary signed representation involving a small number of non-zero $\pm 1$-digits.

We define key privacy for IBE systems in terms of two properties, indistinguishability under chosen identity attack, and indistinguishability under chosen key generator attack. Further, we show that the BasicIdent system in the Boneh/Franklin IBE has these properties under chosen plaintext attack.

From designing point of view, it is not a trivial task to convert a group key agreement protocol into password-based setting where the members of the group share only a human-memorable weak password and the system may not have any secure public key infrastructure. Security analysis against dictionary attacks is on the other side of the coin. The low entropy of human memorable password may enable an adversary to mount off-line dictionary attacks if careful approaches are not taken in designing the protocol. Recently, Kim et al. proposed a very efficient provably secure group key agreement protocol KLL, security of which relies on the Computational Diffie-Hellman (CDH) assumption in the presence of random oracles. Dutta-Barua embed the protocol KLL into password-based environment -- yielding the protocol DB-PWD. Abdalla et al. detect certain flaws in the protocol DB-PWD. In this paper, we take suitable measures to overcome these attacks. We introduce a protocol MDB-PWD -- an improved variant of the protocol DB-PWD and analyze its security in the security framework formalized by Bellare et al. in both the ideal cipher model and the random oracle model under CDH assumption.

Given two non-weakly $k$-normal Boolean functions on $n$ variables a method is proposed to construct a non-weakly $(k+1)$-normal Boolean function on $(n+2)$ variables.

An elliptic curve random number generator (ECRNG) has been proposed in ANSI and NIST draft standards. This paper proves that, if three conjectures are true, then the ECRNG is secure. The three conjectures are hardness of the elliptic curve decisional Diffie-Hellman problem and the hardness of two newer problems, the x-logarithm problem and the truncated point problem.

In this article, we present a second preimage attack on a double block-length hash proposal presented at FSE 2006. If the hash function is instantiated with DESX as underlying block cipher, we are able to construct second preimages deterministically. Nevertheless, this second preimage attack does not render the hash scheme insecure. For the hash scheme, we only show that it should not be instantiated with DESX but AES should rather be used. However, we use the instantiation of this hash scheme with DESX to introduce a new property of iterated hash functions, namely a so-called b-block bypass. We will show that if an iterated hash function possesses a b-block bypass, then this implies that second preimages can be constructed. Additionally, the attacker has more degrees of freedom for constructing the second preimage.

Raising of the fixed element of prime order group to arbitrary degree is the main operation specified by digital signature algorithms DSA, ECDSA. Fast exponentiation algorithms are proposed. Algorithms use number system with algebraic integer base (-2)^(1/4), 2^(1/4). Prime group order r can be factored as r = pi*pi1 in Euclidean ring Z[Sqrt[-2]], Z[Sqrt[2]] by Pollard and Schnorr algorithm. Farther factorization of prime quadratic divisor as pi = rho*rho1 in the ring Z[(-2)^(1/4)], Z[2^(1/4)] can be done similarly. Finite field of r elements is represented as quotient ring Z[(-2)^(1/4)]/(rho), Z[2^(1/4)]/(rho). Integer exponent k is reduced in corresponding quotient ring by minimization of its absolute norm. Algorithms can be used for fast exponentiation in arbitrary cyclic group if its order can be factored in corresponding number rings. If window size is 4 bits, this approach allows speeding-up 2.5 times elliptic curve digital signature verification comparatively to known methods with the same window size.

In this paper, for the genus-$2$ hyperelliptic curve $y^{2}=x^{5} -\alpha x$ ($\alpha = \pm2$) defined over finite fields of characteristic five, we construct a distortion map explicitly, and show the map indeed gives an input for which the value of the Tate pairing is not trivial. Next we describe a computation of the Tate pairing by using the proposed distortion map. Furthermore, we also see that this type of curve is equipped with a simple quintuple operation on the Jacobian group, which leads to giving an improvement for computing the Tate pairing. We indeed show that, for the computation of the Tate pairing for genus-$2$ hyperelliptic curves, our method is about twice as efficient as a previous work.

In this paper we introduce a new approach of constructing time capsule signature. Our new construction captures the basic requirements defined by dodis \emph{et al.}, and it is also very straightforward and flexible. The time capsule signature provides an elegant way to produce a ``future signature" that becomes valid from a specific future time $t$, when a trusted third party (called \textit{Time Server}) publishes some trapdoor information associated with the time $t$. It also has many other advantages. Our work includes a developed security model of time capsule signature, a novel way of construction based on the bipartite ring signature, which is proven secure in the random oracle model and a concrete realization of the scheme.

This paper provides the first analytical and practical treatment of entity authentication and authenticated key exchange in the framework of Tree Parity Machines (TPMs). The interaction of TPMs has been discussed as an alternative concept for secure symmetric key exchange. Several attacks have been proposed on the non-authenticated principle. Adding and some extra entity authentication method is straightforward but outside the concept using TPMs. A simple and consequent implicit entity authentication from within the key exchange concept as an extension to the key exchange protocol is suggested. A proof for the soundness of the proposed entity authentication is given. Furthermore, next to averting a Man-In-The-Middle attack, the currently known attacks on the non-authenticated symmetric key exchange principle using TPMs can provably be averted for the authenticated variant.

Batch verification of digital signatures is used to improve the computational complexity when large number of digital signatures must be verified. Lee at al. [2] proposed a new method to identify bad signatures in batches efficiently. We show that the method is flawed.

In this paper we simplify and extend the Eta pairing, originally discovered in the setting of supersingular curves by Baretto et al., to ordinary curves. Furthermore, we show that by swapping the arguments of the Eta pairing, one obtains a very efficient algorithm resulting in a speed-up of a factor of around six over the usual Tate pairing, in the case of curves which have large security parameters, complex multiplication by $D=-3$, and when the trace of Frobenius is chosen to be suitably small. Other, more minor savings are obtained for more general curves.

A main obstacle in manufacturing the TWIRL device for realizing the sieving step of the Number Field Sieve is the sophisticated chip layout. Especially the logic for logging and recovering large prime factors found during sieving adds significantly to the layout complexity. We describe a device building on the Elliptic Curve Method (ECM) that for parameters of interest enables the replacement of the complete logging part in TWIRL by an off-wafer postprocessing. The postprocessing is done in real time, leaving the total sieving time basically unchanged. The proposed device is an optimized ECM implementation building on curves chosen to cope with factor sizes as expected in the output of TWIRL. According to our preliminary analysis, for the relation collection step expected for a 1024-bit factorization our design is realizable with current fab technology at very moderate cost. The proposed ECM engine also finds the vast majority of the needed cofactor factorizations. In summary, we think the proposed device to enable a significant decrease of TWIRL's layout complexity and therewith its cost.

Public key encryption with keyword search (PEKS) enables user Alice to send a secret key $T_W$ to a server that will enable the server to locate all encrypted messages containing the keyword $W$, but learn nothing else. In this paper, we propose a new PKES scheme based on pairings. There is no pairing operation involved in the encryption procedure. Then, we provide further discussion on removing secure channel from PKES, and present an efficient secure channel free PKES scheme. Our two new schemes can be proved secure in the random oracle model, under the appropriate computational assumptions.

We define the weight of an integer $N$ to be the smallest $w$ such that $N$ can be represented as $\sum_{i=1}^w \epsilon_i 2^{c_i}$, with $\epsilon_1,\ldots,\epsilon_w\in\{1,-1\}$. Since arithmetic modulo a prime of low weight is particularly efficient, it is tempting to use such primes in cryptographic protocols. In this paper we consider the difficulty of the discrete logarithm problem modulo a prime $N$ of low weight, as well as the difficulty of factoring an integer $N$ of low weight. We describe a version of the number field sieve which handles both problems. Our analysis leads to the conjecture that, for $N\to\infty$ with $w$ fixed, the worst-case running time of the method is bounded above by ${\rm exp}((c+o(1))(\log\,N)^{1/3}(\log\log\,N)^{2/3})$ with $c<((32/9)(2w-3)/(w-1))^{1/3}$ and below by the same expression with $c=(32/9)^{1/3}((\sqrt{2}w-2\sqrt{2}+1)/(w-1))^{2/3}.$ It also reveals that on average the method performs significantly better than it does in the worst case. We consider all the examples given in a recent paper of Koblitz and Menezes and demonstrate that in every case but one, our algorithm runs faster than the standard versions of the number field sieve.

In 2006, Blake, Murty and Xu proposed three refinements to Miller's algorithm for computing Weil/Tate Pairings. In this paper we extend their work and propose a generalized algorithm, which integrates their first two algorithms. Our approach is to pre-organize the binary representation of the involved integer to the best cases of Blake's algorithms. Further, our refinement is more suitable for Solinas numbers than theirs. We analyze our algorithm and show that our refinement can perform better than the original algorithms.

In this paper we introduce a new idea of tunneling of hash functions. In some sense tunnels replace multi-message modification methods and exponentially accelerate collision search. We describe several tunnels in hash function MD5. Using it we find a MD5 collision roughly in one minute on a standard notebook PC (Intel Pentium, 1.6 GHz). The method works for any initializing value. Tunneling is a general idea, which can be used for finding collisions of other hash functions, such as SHA-1, 2. We show several capabilities of tunnels. A program, which source code is available on a project homepage, experimentally verified the method. Revised version of this paper contains the appendix with the description of more tunnels. These tunnels further decrease the average time of MD5 collision to 31 seconds. On PC Intel Pentium 4 (3,2 GHz) it is 17 seconds in average.

In this paper, we present an improved attack algorithm to find two-block collisions of the hash function MD5. The attack uses the same differential path of MD5 and the set of sufficient conditions that was presented by Wang et al. We present a new technique which allows us to deterministically fulfill restrictions to properly rotate the differentials in the first round. We will present a new algorithm to find the first block and we will use an algorithm of Klima to find the second block. To optimize the inner loop of these algorithms we will optimize the set of sufficient conditions. We also show that the initial value used for the attack has a large influence on the attack complexity. Therefore a recommendation is made for 2 conditions on the initial value of the attack to avoid very hard situations if one has some freedom in choosing this initial value. Our attack can be done in an average of about 1 minute (avg. complexity $2^{32.3}$) on a 3Ghz Pentium4 for these random recommended initial values. For arbitrary random initial values the average is about 5 minutes (avg. complexity $2^{34.1}$). With a reasonable probability a collision is found within mere seconds, allowing for instance an attack during the execution of a protocol.

In Eurocrypt 2006, Contini, Lenstra, and Steinfeld proposed a new hash function primitive, VSH, very smooth hash. In this brief paper we offer commentary on the resistance of VSH against some standard cryptanalytic attacks, including preimage attacks and collision search for a truncated VSH. Although the authors of VSH claim only collision resistance, we show why one must be very careful when using VSH in cryptographic engineering, where additional security properties are often required.

This paper proposes a new efficient signature scheme from bilinear maps that is secure in the standard model (i.e., without the random oracle model). Our signature scheme is more effective in many applications (e.g., blind signatures, group signatures, anonymous credentials etc.) than the existing secure signature schemes in the standard model. As typical applications of our signature scheme, this paper presents efficient blind signatures and partially blind signatures that are secure in the standard model. Here, partially blind signatures are a generalization of blind signatures (i.e., blind signatures are a special case of partially blind signatures) and have many applications including electronic cash and voting. Our blind signature scheme is much more efficient than the existing secure blind signature schemes in the standard model such as the Camenisch-Koprowski-Warinsch and Juels-Luby-Ostrovsky schemes, and is also almost as efficient as the most efficient blind signature schemes whose security has been analyzed heuristically or in the random oracle model. Our partially blind signature scheme is the first one that is secure in the standard model and it is very efficient (as efficient as our blind signatures). The security proof of our blind and partially blind signature schemes requires the 2SDH assumption, a variant of the SDH assumption introduced by Boneh and Boyen, and the 2SDH-IND assumption. This paper also presents an efficient way to convert our (partially) blind signature scheme in the standard model to a scheme secure for a concurrent run of users in the common reference string (CRS) model. Finally, we present a blind signature scheme based on the Waters signature scheme.

Physical Uncloneable Functions (PUFs) can be used as a cost-effective means to store cryptographic key material in an uncloneable way. In coating PUFs, keys are generated from capacitance measurements of a coating containing many randomly distributed particles with different dielectric constants. We introduce a physical model of coating PUFs by simplifying the capacitance sensors to a parallel plate geometry. We estimate the amount of information that can be extracted from the coating. We show that the inherent entropy is proportional to $sqrt{n}(log n)^{3/2}$, where n is the number of particles that fit between the capacitor plates in a straight line. However, measurement noise may severely reduce the amount of information that can actually be extracted in practice. In the noisy regime the number of extractable bits is in fact a decreasing function of n. We derive an optimal value for n as a function of the noise amplitude, the PUF geometry and the dielectric constants.

Group signatures are generalized credential/member authentication schemes with wide applications, such as Trust Computing. Membership revocation problem is a major issue of group signatures. In some applications that group secret keys are stored in tamper resistant chips, a Verifier-Local Revocation resolution is more reasonable than other methods, such as witness based revocation. Boneh et al. formally defined such VLR group signatures and proposed a VLR resolution for a short group signature. Later Nakanishi et al. pointed out it has a disadvantage of backward linkability, and provided a VLR resolution with backward unlinkability at the cost of longer signature size and more computation. We improve Nakanishi et al.'s scheme by reducing the signature size and computations required, without compromising VLR and backward unlinkability.

A cover-free family is a well-studied combinatorial structure that has many applications in computer science and cryptography. In this paper, we propose a new public key traitor tracing scheme based on cover-free families. The new traitor tracing scheme is similar to the Boneh-Franklin scheme except that in the Boneh-Franklin scheme, decryption keys are derived from Reed-Solomon codes while in our case they are derived from a cover-free family. This results in much simpler and faster tracing algorithms for single-key pirate decoders, compared to the tracing algorithms of Boneh-Franklin scheme that use Berlekamp-Welch algorithm. Our tracing algorithms never accuse innocent users and identify all traitors with overwhelming probability.

Recently, Wang proposed a new method to cryptanalyze SHA-1 and found collisions of $58$-round SHA-1. However many details of Wang's attack are still unpublished, especially, 1) How to find differential paths? 2) How to modify messages properly? For the first issue, some results have already been reported. In our article, we clarify the second issue and give a sophisticated method based on Gröbner basis techniques. We propose two algorithm based on the basic and an improved message modification techniques respectively. The complexity of our algorithm to find a collision for 58-round SHA-1 based on the basic message modification is $2^{29}$ message modifications and its implementation is equivalent to $2^{31}$ SHA-1 computation experimentally, whereas Wang's method needs $2^{34}$ SHA-1 computation. We propose an improved message modification and apply it to construct a more sophisticated algorithm to find a collision. The complexity to find a collision for 58-round SHA-1 based on this improved message modification technique is $2^8$ message modifications, but our latest implementation is very slow, equivalent to $2^{31}$ SHA-1 computation experimentally. However we conjecture that our algorithm can be improved by techniques of error correcting code and Gröbner basis. By using our methods, we have found many collisions for $58$-round SHA-1.

In this article, we provide an overview of cryptography and cryptographic key management as they are specified in IPsec, a popular suite of standards for providing communications security and network access control for Internet communications. We focus on the latest generation of the IPsec standards, recently published as Request for Comments 4301–4309 by the Internet Engineering Task Force, and how they have evolved from earlier versions of the standards.

We present the first aggregate signature, the first multisignature, and the first verifiably encrypted signature provably secure without random oracles. Our constructions derive from a novel application of a recent signature scheme due to Waters. Signatures in our aggregate signature scheme are sequentially constructed, but knowledge of the order in which messages were signed is not necessary for verification. The aggregate signatures obtained are shorter than Lysyanskaya et~al. sequential aggregates and can be verified more efficiently than Boneh et~al. aggregates. We also consider applications to secure routing and proxy signatures.

Message Authentication Codes (MACs) are central algorithms deployed in virtually every security protocol in common usage. In these protocols, the integrity and authenticity of messages rely entirely on the security of the MAC; we examine cases in which this security is lost. In this paper, we examine the notion of “reforgeability” for MACs. We first give a definition for this new notion, then examine some of the most widely-used and well-known MACs under our definition. We show that for each of these MACs there exists an attack that allows efficient forgeries after the first one is obtained, and we show that simply making these schemes stateful is usually insufficient. For those schemes where adding state is effective, we go one step further to examine how counter misuse affects the security of the MAC, finding, in many cases, simply repeating a single counter value yields complete insecurity. These issues motivated the design of a new scheme, WMAC, which has a number of desirable properties. It is as efficient as the fastest MACs, resists counter misuse, and has tags which may be truncated to the desired length without affecting security (currently, the fastest MACs do not have this property), making it resistant to reforging attacks and arguably the best MAC for constrained environments.

The MEM mode is a nonce-based enciphering mode of operation proposed by Chakraborty and Sarkar, which was claimed to be secure against symmetric nonce respecting adversaries. We show that this is not correct by using two very simple attcks. One attack need one decryption and one decryption queries, and the other only need one encryption query.

Let $N=pq$ be an RSA modulus where $p$, $q$ are large primes of the same bitsize. We study the class of the public exponents $e$ for which there exist an integer $m$ with $1\leq m\leq {\log{N}\over \log{32}}$ and small integers $u$, $X$, $Y$ and $Z$ satisfying $$(e+u)Y^m-\psi(N)X^m=Z,$$ where $\psi(N)=(p+1)(q-1)$. First we show that these exponents are of improper use in RSA cryptosystems. Next we show that their number is at least $O\left(mN^{{1\over 2}+{\a\over m}-\a-\e}\right)$ where $\a$ is defined by $N^{1-\a}=\psi(N)$.

Let $n=pq$ be an RSA modulus with unknown prime factors and $F$ any function for which there exists an integer $u\neq 0$ satisfying $F(u)\approx n$ and $pu$ or $qu$ is computable from $F(u)$ and $n$. We show that choosing a public key exponent $e$ for which there exist positive integers $X$, $Y$ such that $\left\vert eY-XF(u)\right\vert$ and $Y$ are suitably small, then the system is insecure.

Suppose you want to store a large file on a remote and unreliable server. You would like to verify that your file has not been corrupted, so you store a small private (randomized)``fingerprint'' of the file on your own computer. This is the setting for the well-studied authentication problem, and the size of the required private fingerprint is well understood. We study the problem of sub-linear authentication: suppose you would like to encode and store your file in a way that allows you to verify that it has not been corrupted, but without reading all of it. If you only want to read t bits of the file, how large does the size s of the fingerprint need to be? We define this problem formally, and show a tight lower bound on the relationship between s and t when the adversary is not computationally bounded, namely: s x t= Omega(n) where n is the file size. This is an easier case of the online memory checking problem, introduced by Blum, Evans, Gemmel, Kannan and Naor in 1991, and hence the same (tight) lower bound applies also to this problem. It was previously shown that when the adversary is not computationally bounded, under the assumption that one-way functions exist, it is possible to construct much better online memory checkers and sub-linear authentication schemes. We show that the existence of one-way functions is also a necessary condition: even slightly breaking the s x t= Omega(n) lower bound in a computational setting implies the existence of one-way functions.

Given the original set $X$ where $|X|=s$, a sketch $P$ is computed from $X$ and made public. From another set $Y$ where $|Y| = s$ and $P$, we can reconstruct $X$ if $|X\cap Y|\ge |s-t|$, where $t<s$ is some threshold. The sketch $P$ is secure if it does not reveal much information about $X$. A few constructions have been proposed, but they cannot handle multi-sets, that is, sets that may contain duplicate elements. We observe that the techniques in the set reconciliation protocol proposed by Minsky et al. (ISIT 2001) can be applied and give a secure sketch that supports multi-sets. If $X$ is a subset of an universe with $n$ elements, the running time of the encoding and decoding algorithms will be polynomial w.r.t. $s$ and $\log n$, and the entropy loss due to the sketch is less than $2t(1+\log n)$.

When proving the security of a message authentication scheme, the messages are considered to be atomic objects. Straightforward application of such schemes to some information resources may introduce security flaws. Gennaro and Rohatgi (Crypto '97) identified the streams of data as an important class of information resources that can not be considered to be message-like, and they proposed a solution to the problem of stream signing when the stream is not known in advance. The disadvantage of digital signing streams of data is that it is not efficient when non-repudiation is not important, as in the case of point-to-point communications. We present several schemes and also a family of schemes for stream authentication in a unicast setting. Since many authentication schemes have been broken, we will prove our solutions.

In many practical settings, participants are willing to deviate from the protocol only if they remain undetected. Aumann and Lindell introduced a concept of covert adversaries to formalize this type of corruption. In the current paper, we refine their model to get stronger security guarantees. Namely, we show how to construct protocols, where malicious participants cannot learn anything beyond their intended outputs and honest participants can detect malicious behavior that alters their outputs. As this construction does not protect honest parties from selective protocol failures, a valid corruption complaint can leak a single bit of information about the inputs of honest parties. Importantly, it is often up to the honest party to decide whether to complain or not. This potential leakage is often compensated by gains in efficiency---many standard zero-knowledge proof steps can be omitted. As a concrete practical contribution, we show how to implement consistent versions of several important cryptographic protocols such as oblivious transfer, conditional disclosure of secrets and private inference control.

We analyze a secure routing protocol, Secure Path Vector (SPV), proposed in SIGCOMM 2004. SPV aims to provide authenticity for route announcements in the Border Gateway Protocol (BGP) using an efficient alternative to ordinary digital signatures, called constant-time signatures. Today, SPV is often considered the best cryptographic defense for BGP. We find subtle flaws in the design of SPV which lead to attacks that can be mounted by 60% of Autonomous Systems in the Internet. In addition, we study several of SPV's design decisions and assumptions and highlight the requirements for security of routing protocols. In light of our analysis, we reexamine the need for constant-time signatures and find that certain standard digital signature schemes can provide the same level of efficiency for route authenticity.

Linux is the most popular open source project. The Linux random number generator is part of the kernel of all Linux distributions and is based on generating randomness from entropy of operating system events. The output of this generator is used for almost every security protocol, including TLS/SSL key generation, choosing TCP sequence numbers, and file system and email encryption. Although the generator is part of an open source project, its source code (about $2500$ lines of code) is poorly documented, and patched with hundreds of code patches. We used dynamic and static reverse engineering to learn the operation of this generator. This paper presents a description of the underlying algorithms and exposes several security vulnerabilities. In particular, we show an attack on the forward security of the generator which enables an adversary who exposes the state of the generator to compute previous states and outputs. In addition we present a few cryptographic flaws in the design of the generator, as well as measurements of the actual entropy collected by it, and a critical analysis of the use of the generator in Linux distributions on disk-less devices.

We present an identity-based cryptosystem that features fully anonymous ciphertexts and hierarchical key delegation. We give a proof of security in the standard model, based on the mild Decision Linear complexity assumption in bilinear groups. The system is efficient and practical, with small ciphertexts of size linear in the depth of the hierarchy. Applications include search on encrypted data, fully private communication, etc. Our results resolve two open problems pertaining to anonymous identity-based encryption, our scheme being the first to offer provable anonymity in the standard model, in addition to being the first to realize fully anonymous HIBE at all levels in the hierarchy.

There is a vast body of work on {\em implementing} anonymous communication. In this paper, we study the possibility of using anonymous communication as a {\em building block}, and show that one can leverage on anonymity in a variety of cryptographic contexts. Our results go in two directions. \begin{itemize} \item{\bf Feasibility.} We show that anonymous communication over {\em insecure} channels can be used to implement unconditionally secure point-to-point channels, and hence general multi-party protocols with unconditional security in the presence of an honest majority. In contrast, anonymity cannot be generally used to obtain unconditional security when there is no honest majority. \item{\bf Efficiency.} We show that anonymous channels can yield substantial efficiency improvements for several natural secure computation tasks. In particular, we present the first solution to the problem of private information retrieval (PIR) which can handle multiple users while being close to optimal with respect to {\em both} communication and computation. A key observation that underlies these results is that {\em local randomization} of inputs, via secret-sharing, when combined with the {\em global mixing} of the shares, provided by anonymity, allows to carry out useful computations on the inputs while keeping the inputs private. \end{itemize}

Web users are increasingly victims of phishing, spoofing and malware attacks. In this article, we discuss existing and proposed defense mechanisms. We highlight the vulnerabilities of current defenses, and the challenges of validating and adopting new defenses.

Atomic broadcast is a communication primitive that allows a group of n parties to deliver a common sequence of payload messages despite the failure of some parties. We address the problem of asynchronous atomic broadcast when up to t < n/3 parties may exhibit Byzantine behavior. We provide the first protocol with an amortized expected message complexity of O(n) per delivered payload. The most efficient previous solutions are the BFT protocol by Castro and Liskov and the KS protocol by Kursawe and Shoup, both of which have message complexity O(n^2). Like the BFT and KS protocols, our protocol is optimistic and uses inexpensive mechanisms during periods when no faults occur; when network instability or faults are detected, it switches to a more expensive recovery mode. The key idea of our solution is to replace reliable broadcast in the KS protocol by consistent broadcast, which reduces the message complexity from O(n^2) to O(n) in the optimistic mode. But since consistent broadcast provides weaker guarantees than reliable broadcast, our recovery mode incorporates novel techniques to ensure that safety and liveness are always satisfied.

We enumerate requirements and give constructions for the vote storage unit of an electronic voting machine. In this application, the record of votes must survive even an unexpected failure of the machine; hence the data structure should be durable. At the same time, the order in which votes are cast must be hidden to protect the privacy of voters, so the data structure should be history-independent. Adversaries may try to surreptitiously add or delete votes from the storage unit after the election has concluded, so the storage should be tamper-evident. Finally, we must guard against an adversarial voting machine's attempts to mark ballots through the representation of the data structure, so we desire a subliminal-free representation. We leverage the properties of Programmable Read Only Memory (PROM), a special kind of write-once storage medium, to meet these requirements. We give constructions for data structures on PROM storage that simultaneously satisfy all our desired properties. Our techniques can significantly reduce the need to verify code running on a voting machine.

The only known construction of identity-based signatures that can be proven secure in the standard model is based on the approach of attaching certificates to non-identity-based signatures. This folklore construction method leads to schemes that are somewhat inefficient and leaves open the problem of finding more efficient direct constructions. We present the first such construction. Our scheme is obtained from a modification of Waters' recently proposed identity-based encryption scheme. It is computationally efficient and the signatures are short. The scheme's security is proven in the standard model and rests on the hardness of the computational Diffie-Hellman problem in groups equipped with a pairing.

Known proposals for key establishment schemes based on combinatorial group theory are often formulated in a rather informal manner. Typically, issues like the choice of a session identifier and parallel protocol executions are not addressed, and no security proof in an established model is provided. Successful attacks against proposed parameter sets for braid groups further decreased the attractivity of combinatorial group theory as a candidate platform for cryptography. We present a 2-round group key agreement protocol that can be proven secure in the random oracle model if a certain group-theoretical problem is hard. The security proof builds on a framework of Bresson et al., and explicitly addresses some issues concerning malicious insiders and also forward secrecy. While being designed as a tool for basing group key agreement on non-abelian groups, our framework also yields a 2-round group key agreement basing on a Computational Diffie-Hellman assumption.

Pseudorandom Functions (PRFs), introduced by Goldreich, Goldwasser and Micali, allow one to efficiently simulate the computation of a function which is indistinguishable from a truly random function. A seemingly stronger primitive is that of a (strong) pseudorandom permutation (PRP), which allows one to efficiently simulate a truly random permutation (and its inverse). The celebrated result of Luby and Rackoff shows that these primitives are, in fact, equivalent: four rounds of the Feistel transform are necessary and sufficient to turn a PRF into a (strong) PRP. In this paper we study a similar conversion for the verifiable analogs of PRFs and PRPs, called Verifiable Random Functions (VRFs) and Verifiable Random Permutations (VRPs). VRFs, introduced by Micali, Rabin and Vadhan, extend the notion of a PRF to allow the owner of the secret key for the VRF to prove to the outside parties that a given VRF value was correctly (and uniquely!) computed. Yet, such proofs do not violate the pseudorandomness of the remaining, yet ``unopened'' values. VRPs, introduced in this paper, similarly extend the notion of PRPs. We notice that the result of Luby and Rackoff no longer applies to converting VRFs into VRPs, since the VRP proofs must reveal the VRF outputs (and proofs) of the intermediate rounds. Indeed, we show that even logarithmic (in the security parameter) number of rounds is not enough for this conversion. Our main result, however, shows that super-logarithmic number of rounds of the Feistel transform suffice to build a VRP out of an arbitrary VRF. As an application, we give a construction of non-interactive zero-knowledge (NIZK) proofs with efficient provers for any NP language from any VRF. The result is obtained from our VRF--->VRP conversion, by noticing that VRPs easily yield ``invariant signatures'' of Goldwasser and Ostrovsky , which are known to imply NIZK. (We also notice that the detour through VRPs seems necessary for this implication, since using VRFs in place of invariant signatures is provably insufficient for the NIZK construction of Goldwasser et al. to go through.)

The complexity of a secret sharing scheme is defined as the ratio between the maximum length of the shares and the length of the secret. The optimization of this parameter for general access structures is an important and very difficult open problem in secret sharing. We explore in this paper the connections of this open problem with matroids and polymatroids. Matroid ports were introduced by Lehman in 1964. A forbidden minor characterization of matroid ports was given by Seymour in 1976. These results are previous to the invention of secret sharing by Shamir in 1979. Important connections between ideal secret sharing schemes and matroids were discovered by Brickell and Davenport in 1991. Their results can be restated as follows: every ideal secret sharing scheme defines a matroid, and its access structure is a port of that matroid. In spite of this, the results by Lehman and Seymour and other subsequent results on matroid ports have not been noticed until now by the researchers interested in secret sharing. Lower bounds on the optimal complexity of access structures can be found by taking into account that the joint Shannon entropies of a set of random variables define a polymatroid. We introduce a new parameter, which is denoted by $\kappa$, to represent the best lower bound that can be obtained by this method. We prove that every bound that is obtained by this technique for an access structure applies to its dual structure as well. By using the aforementioned result by Seymour we obtain two new characterizations of matroid ports. The first one refers to the existence of a certain combinatorial configuration in the access structure, while the second one involves the values of the parameter $\kappa$ that is introduced in this paper. Both are related to bounds on the optimal complexity. As a consequence, we generalize the result by Brickell and Davenport by proving that, if the length of every share in a secret sharing scheme is less than 3/2 times the length of the secret, then its access structure is a matroid port. This generalizes and explains a phenomenon that was observed in several families of access structures. Finally, we present a construction of linear secret sharing schemes for the ports of the Vamos matroid and the non-Desargues matroid, which do not admit any ideal secret sharing scheme. We obtain in this way upper bounds on their optimal complexity. These new bounds are a contribution on the search of examples of access structures whose optimal complexity lies between 1 and 3/2.

Let $G_1$ be a cyclic multiplicative group of order $n$. It is known that the Diffie-Hellman problem is random self-reducible in $G_1$ with respect to a fixed generator $g$ if $\phi(n)$ is known. That is, given $g, g^x\in G_1$ and having oracle access to a `Diffie-Hellman Problem' solver with fixed generator $g$, it is possible to compute $g^{1/x} \in G_1$ in polynomial time. On the other hand, it is not known if such a reduction exists when $\phi(n)$ is unknown. We exploit this ``gap'' to construct a cryptosystem based on hidden order groups by presenting a practical implementation of a novel cryptographic primitive called \emph{Strong Associative One-Way Function} (SAOWF). SAOWFs have interesting applications like one-round group key agreement. We demonstrate this by presenting an efficient group key agreement protocol for dynamic ad-hoc groups. Our cryptosystem can be considered as a combination of the Diffie-Hellman and RSA cryptosystems.

A parity checking-styled Weil sum algorithm is presented for a general class of the univariate polynomials which fully characterize a system of $n$ polynomials in $n$ variables over $F_{2}$. The previously known proof methods of explicit Weil sum evaluation of Dembowski-Ostrom polynomials are extended to general case. The algorithm computes the absolute values of the Weil sums of the generic central polynomials in MQ problem.

In Eurocrypt 2005, Wang et al. presented a collision attak on MD5. In their paper, they intoduced "Sufficient Condition" which would be needed to generate collisions. In this paper, we explain how to construct sufficent conditions of MD5 when a differential path is given. By applying our algorithm to a collision path given byWang et al, we found that sufficient conditions introduced by them contained some unnecessary conditions. Generally speaking, when a differential path is given, corresponding sets of sufficient conditions is not unique. In our research, we analyzed the differential path found by Wang et al, and we found a different set of sufficient conditions from that of Wang et al. We have generated collisions by using our sifficient conditions.

In this paper we study security definitions for authenticated key exchange (AKE) protocols. We observe that there are several families of attacks on AKE protocols that lie outside the boundary of the current class of security definitions. In an attempt to bring these attacks within the scope of analysis we extend the AKE security definition to provide greater powers to the adversary. We provide a general framework for defining AKE security, which we call strong AKE security, such that existing security definitions occur as instances of the framework. We then introduce NAXOS, a new two-pass AKE protocol, and prove that it is secure in this stronger definition. In addition, we formulate a notion of ephemeral secret key which captures all ephemeral information used in session establishment. We demonstrate the importance of this formulation by showing that a secure AKE protocol SIG-DH can become vulnerable when instantiated with signature schemes which are insecure against revelation of the secret random bits used in the signature generation.

In this paper we analyze the E0 cipher, which is the cipher used in the Bluetooth specifications. We adapted and optimized the Binary Decision Diagram attack of Krause, for the specific details of E0. Our method requires 128 known bits of the keystream in order to recover the initial value of the four LFSR's in the E0 system. We describe several variants which we built to lower the complexity of the attack. We evaluated our attack against the real (non-reduced) E0 cipher. Our best attack can recover the initial value of the four LFSR's, for the first time, with a realistic space complexity of 2^23 (84MB RAM), and with a time complexity of 2^87. This attack can be massively parallelized to lower the overall time complexity. Beyond the specifics of E0, our work describes practical experience with BDD-based cryptanalysis, which so far has mostly been a theoretical concept.

Motivated by the quest for reducing assumptions in security proofs in cryptography, this paper is concerned with designing efficient symmetric encryption and authentication schemes based on any weak pseudorandom function (PRF) which can be much more efficiently implemented than PRFs. Damgard and Nielsen (CRYPTO '02) have shown how to construct an efficient symmetric encryption scheme based on any weak PRF that is provably secure against chosen-plaintext attacks. The main ingredient is a range-extension construction for weak PRFs. By using well-known techniques, they also showed how their scheme can be made secure against the stronger chosen-ciphertext attacks. The results of our paper are three-fold. First, we give a range-extension construction for weak PRFs that is optimal within a large and natural class of reductions (especially all known today). Second, we propose a construction of a regular PRF from any weak PRF. Third, these two results imply a (for long messages) much more efficient chosen-ciphertext secure encryption scheme than the one proposed by Damgard and Nielsen. The results also give answers to open questions posed by Naor and Reingold (CRYPTO '98) and by Damgard and Nielsen.

The output of RC4 was analyzed using the "book stack" test for randomness. It is experimentally shown that the keystream generated from RC4 can be distinguished from random with about $2^{32}$ output bits.

This paper presents the first automatic technique for proving not only protocols but also primitives in the exact security computational model. Automatic proofs of cryptographic protocols were up to now reserved to the Dolev-Yao model, which however makes quite strong assumptions on the primitives. On the other hand, with the proofs by reductions, in the complexity theoretic framework, more subtle security assumptions can be considered, but security analyses are manual. A process calculus is thus defined in order to take into account the probabilistic semantics of the computational model. It is already rich enough to describe all the usual security notions of both symmetric and asymmetric cryptography, as well as the basic computational assumptions. As an example, we illustrate the use of the new tool with the proof of a quite famous asymmetric primitive: unforgeability under chosen-message attacks (UF-CMA) of the Full-Domain Hash signature scheme under the (trapdoor)-one-wayness of some permutations.

Automated tools such as model checkers and theorem provers for the analysis of security protocols typically abstract from cryptography by Dolev-Yao models, i.e., abstract term algebras replace the real cryptographic operations. Recently it was shown that in essence this approach is cryptographically sound for certain operations like signing and encryption. The strongest results show this in the sense of blackbox reactive simulatability (BRSIM)/UC with only small changes to both Dolev-Yao models and natural implementations. This notion essentially means the preservation of arbitrary security properties under active attacks in arbitrary protocol environments. We show that it is impossible to extend the strong BRSIM/UC results to usual Dolev-Yao models of hash functions in the general case. These models treat hash functions as free operators of the term algebra. In contrast, we show that these models are sound in the same strict sense in the random oracle model of cryptography. For the standard model of cryptography, we also discuss several conceivable restrictions to the Dolev-Yao models and classify them into possible and impossible cases.

The paper is an examination of double-base decompositions of integers $n$, namely expansions loosely of the form $$ n = \sum_{i,j} A^iB^j $$ for some base $\{A,B\}$. This was examined in previous works in the case when $A,B$ lie in $\mathbb{N}$. On the positive side, we show how to extend previous results of to Koblitz curves over binary fields. Namely, we obtain a sublinear scalar algorithm to compute, given a generic positive integer $n$ and an elliptic curve point $P$, the point $nP$ in time $O\left(\frac{\log n}{\log\log n}\right)$ elliptic curve operations with essentially no storage, thus making the method asymptotically faster than any know scalar multiplication algorithm on Koblitz curves. On the negative side, we analyze scalar multiplication using double base numbers and show that on a generic elliptic curve over a finite field, we cannot expect a sublinear algorithm with double bases. Finally, we show that all algorithms used hitherto need at least $\frac{\log n}{\log\log n}$ curve operations.

Digital certificates signed by trusted certification authorities (CAs) are used for multiple purposes, most commonly for secure binding of public keys to names and other attributes of their owners. Although a certificate usually includes an expiration time, it is not uncommon that a certificate needs to be revoked prematurely. For this reason, whenever a client (user or program) needs to assert the validity of another party’s certificate, it performs revocation checking. There are many revocation techniques varying in both the operational model and underlying data structures. One common feature is that a client typically contacts an on-line third party (trusted, untrusted or semi-trusted), identifies the certificate of interest and obtains some form of a proof of either revocation or validity (non-revocation) for the certificate in question. While useful, revocation checking can leak potentially sensitive information. In particular, third parties of dubious trustworthiness discover two things: (1) the identity of the party posing the query, as well as (2) the target of the query. The former can be easily remedied with techniques such as onion routing or anonymous web browsing. Whereas, hiding the target of the query is not as obvious. Arguably, a more important loss of privacy results from the third party’s ability to tie the source of the revocation check with the query’s target. (Since, most likely, the two are about to communicate.) This paper is concerned with the problem of privacy in revocation checking and its contribution is two-fold: it identifies and explores the loss of privacy inherent in current revocation checking, and, it constructs a simple, efficient and flexible privacy-preserving component for one well-known revocation method.

In a seminal paper, Feldman and Micali (STOC '88) show an $n$-party Byzantine agreement protocol tolerating $t < n/3$ malicious parties that runs in expected constant rounds. Here, we show an expected constant-round protocol for authenticated Byzantine agreement assuming honest majority (i.e., $t < n/2$), and relying only on the existence of a secure signature scheme and a public-key infrastructure (PKI). Combined with existing results, this gives the first expected constant-round protocol for secure computation with honest majority in a point-to-point network assuming only one-way functions and a PKI. Our key technical tool --- a new primitive we introduce called moderated VSS --- also yields a simpler proof of the Feldman-Micali result. We also show a simple technique for sequential composition of protocols without simultaneous termination (something that is inherent for Byzantine agreement protocols using $o(n)$ rounds) for the case of $t<n/2$.

At the Asiacrypt 2003 conference Billet and Gilbert introduce a block cipher, which, to quote them, has the following paradoxical traceability properties: it is computationally easy to derive many equivalent distinct descriptions of the same instance of the block cipher; but it is computationally difficult, given one or even up to $k$ of them, to recover the so-called meta-key from which they were derived, or to find any additional equivalent description, or more generally to forge any new untraceable description of the same instance of the block cipher. Their construction relies on the Isomorphism of Polynomials (IP) problem. We here show how to strengthen this construction against algebraic attacks by concealing the underlying IP problems. Our modification is such that our description of the block cipher now does not give the expected results all the time and parallel executions are used to obtain the correct value.

We propose a simple universal (that is, distribution--free) steganographic system in which covertexts with and without hidden texts are statistically indistinguishable. Moreover, the proposed steganographic system has two important properties. First, the rate of transmission of hidden information approaches the Shannon entropy of the covertext source as the size of blocks used for hidden text encoding tends to infinity. Second, if the size of the alphabet of the covertext source and its minentropy tend to infinity then the the number of bits of hidden text per letter of covertext tends to $\log(n!)/n$ where $n$ is the (fixed) size of blocks used for hidden text encoding. The proposed stegosystem uses randomization.

We present MEM, which is a new mode of encryption using a block cipher. MEM is proved to be a strong pseudo-random permutation (SPRP) against {\em symmetric} nonce respecting adversaries, where a symmetric nonce respecting adversary is one which does not repeat nonces to either the encryption or the decryption oracle. Against such adversaries, MEM provides a secure, length preserving, tagless mode of encryption. In our construction, the number of block cipher calls is approximately half that of the earlier known more general constructions CMC, EME and EME$^*$ of tweakable SPRPs. In situations where the appropriate adversary can be assumed, and where a tagless mode of encryption is required, our construction is the most efficient solution till date.

The classic Merkle-Damgård (\textbf{MD}) structure provides a popular way of turning a fixed-length compression function into a variable-length input cryptographic hash function. However, the multi-block collision attacks (MBCA) on the \textbf{MD}-style hash functions MD5, SHA-0 and SHA-1 demonstrate the weakness of the \textbf{MD} construction in extending the collision resistance property of a single compression function to its iterations. In this paper, we investigate a recently proposed cryptographic construction (called \textbf{3C}) devised by enhancing the \textbf{MD} construction, and prove it provides quantitatively more resistance against MBCA than does the \textbf{MD}-style. Specifically, we prove that it requires at least $2^{t/2}$ computational effort to perform any MBCA on the $t$-bit \textbf{3C} hash function when the same attack on a $t$-bit \textbf{MD} hash function (using the same compression function) requires an effort not less than $2^{t/4}$. This is the first result showing a generic construction with resistance to MBCA. We further improve the resistance of the \textbf{3C} design against MBCA and propose the new \textbf{3C+} hash function construction. We prove that \textbf{3C+} is completely \emph{immune} to MBCA since it costs at least $2^{t/2}$ effort to perform any MBCA on the \textbf{3C+} construction. This reduces the collision security of \textbf{3C+} to the collision security of the underlying compression function, hence restoring the paradigm that one only needs to design a secure compression function to obtain a secure iterated hash function. Both the \textbf{3C} and \textbf{3C+} constructions are very simple adjustments to the \textbf{MD} construction and they are immune to the straight forward extension attacks which apply to the \textbf{MD} hash functions. The second preimage attacks on $t$-bit hash functions also do not work on the constructions presented in this paper.

In this paper, we propose an efficient ID-based signature scheme based on pairing. The number of paring operation involved in the verification procedure is one. Our scheme is proved secure against existential forgery on adaptively chosen message and ID attack under the hardness assumption of computational Diffie-Hellman problem, in the random oracle model.

The security and performance of pairing based cryptography has provoked a large volume of research, in part because of the exciting new cryptographic schemes that it underpins. We re-examine how one should implement pairings over ordinary elliptic curves for various practical levels of security. We conclude, contrary to prior work, that the Tate pairing is more efficient than the Weil pairing for all such security levels. This is achieved by using efficient exponentiation techniques in the cyclotomic subgroup backed by efficient squaring routines within the same subgroup.

Web services are an important series of industry standards for adding semantics to web-based and XML-based communication, in particular among enterprises. Like the entire series, the security standards and proposals are highly modular. Combinations of several standards are put together for testing as interoperability scenarios, and these scenarios are likely to evolve into industry best practices. In the terminology of security research, the interoperability scenarios correspond to security protocols. Hence, it is desirable to analyze them for security. In this paper, we analyze the security of the new Secure WS-ReliableMessaging Scenario, the first scenario to combine security elements with elements of another quality-of-service standard. We do this both symbolically and cryptographically. The results of both analyses are positive. The discussion of actual cryptographic primitives of web services security is a novelty of independent interest in this paper.

We propose a new model for key exchange (KE) based on a combination of different types of keys. In our setting, servers exchange keys with clients, who memorize short passwords and carry (stealable) storage cards containing long (cryptographic) keys. Our setting is a generalization of that of Halevi and Krawczyk \cite{HaleviKr99} (HK), where clients have a password and the public key of the server. We point out a subtle flaw in the protocols of HK and demonstrate a practical attack on them, resulting in a full password compromise. We give a definition of security of KE in our (and thus also in the HK) setting and discuss many related subtleties. We define and discuss protection against denial of access (DoA) attacks, which is not possible in any of the previous KE models that use passwords. Finally, we give a very simple and efficient protocol satisfying all our requirements.

We develop a compositional method for proving cryptographically sound security properties of key exchange protocols, based on a symbolic logic that is interpreted over conventional runs of a protocol against a probabilistic polynomial-time attacker. Since key indistinguishability and other previous specifications of secure key exchange suffer from specific compositionality problems, we develop a suitable specification of acceptable key generation. This definition is based on a simple game played by an adversary against a key exchange protocol and a conventional challenger characterizing secure encryption (or other primitives of interest). The method is illustrated using a sample protocol.

A multicollision for a function is a set of inputs whose outputs are all identical. A. Joux showed multicollision attacks on the classical iterated hash function. He also showed how these multicollision attacks can be used to get a collision attack on a concatenated hash function. In this paper, we study multicollision attacks in a more general class of hash functions which we term ``generalized sequential hash functions''. We show that multicollision attacks exist for this class of hash functions provided that every message block is used at most twice in the computation of the message digest.

Radio-Frequency Identifier (RFID) technology, using the ISO-14443 standard, is becoming increasingly popular, with applications like credit-cards, national-ID cards, E-passports, and physical access control. The security of such applications is clearly critical. A key feature of RFID-based systems is their very short range: Typical systems are designed to operate at a range of 5-10cm. Despite this very short nominal range, Kfir and Wool predicted that a rogue device can communicate with an ISO-14443 RFID tag from a distance of 40-50cm, based on modeling and simulations. Moreover, they claimed that such a device can be made portable, with low power requirements, and can be built very cheaply. Such a device can be used as a stand-alone RFID skimmer, to surreptitiously read the contents of simple RFID tags. The same device can be as the ``leech'' part of a relay-attack system, by which an attacker can make purchases using a victim's RFID-enhanced credit card---despite any cryptographic protocols that may be used. In this study we show that the modeling predictions are quite accurate. We show how to build a portable, extended-range RFID skimmer, using only electronics hobbyist supplies and tools. Our skimmer is able to read ISO-14443 tags from a distance of ~25cm, uses a lightweight 40cm-diameter copper-tube antenna, is powered by a 12V battery---and requires a budget of ~$100. We believe that, with some more effort, we can reach ranges of ~35cm, using the same skills, tools, and budget. We conclude that (a) ISO-14443 RFID tags can be skimmed from a distance that does not require the attacker to touch the victim; (b) Simple RFID tags, that respond to any reader, are immediately vulnerable to skimming; and (c) We are about half-way toward a full-blown implementation of a relay-attack.

The paper analyzes a new public key cryptosystem whose security is based on a matrix version of the discrete logarithm problem over an elliptic curve. It is shown that the complexity of solving the underlying problem for the proposed system is dominated by the complexity of solving a fixed number of discrete logarithm problems in the group of an elliptic curve. Using an adapted Pollard rho algorithm it is shown that this problem is essentially as hard as solving one discrete logarithm problem in the group of an elliptic curve.

Hardware side channel vulnerabilities have been studied for many years in embedded silicon-security arena including SmartCards, SetTop-boxes, etc. However, because various recent security activities have goals of improving the software isolation properties of PC platforms, software side channels have become a subject of interest. Recent publications discussed cache-based software side channel vulnerabilities of AES and RSA. Thus, following the classical approach --- a new side channel vulnerability opens a new mitigation research path --- this paper starts to investigate efficient mitigations to protect AES-software against side channel vulnerabilities. First, we will present several mitigation strategies to harden existing AES software against cache-based software side channel attacks and analyze their theoretical protection. Then, we will present a %thorough performance and security evaluation of our mitigation strategies. For ease of evaluation we measured the performance of our code against the performance of the openSSL AES implementation. In addition, we also analyzed our code under various existing attacks. Depending on the level of the required side channel protection, the measured performance loss of our mitigations strategies versus openSSL (respectively best assembler) varies between factors of 1.35 (2.66) and 2.85 (5.83).

We proposed the concept, piece in hand (soldiers in hand) matrix and have developed the framework based on the concept so far. The piece in hand matrix is a general concept which can be applicable to any type of multivariate public key cryptosystems to enhance their security. In this paper, we make improvements in the PH matrix method as follows. (i) In the PH matrix method, an arbitrary number of additional variables can be introduced to the random polynomial term in the public key, which is eliminated by the multiplication of the PH matrix to the public key in the decryption. Thus these additional variables enables the public key to have more than one solution, and therefore increases the difficulty to solve the public key. We show, in an experimental manner, that the PH matrix method improved in this way is secure even against the Gröbner basis attack. (ii) In the nonlinear PH matrix method proposed previously, the degree of polynomials in the public key is more than two, and this may cause an undesirable increase in the length of the public key. In this paper, we propose a nonlinear PH matrix method, where the degree of the public key is kept the same as the degree of the public key of the original cryptosystem, which is normally two.

Recently several researchers and practitioners have begun to address the problem of secure device pairing or how to set up secure communication between two devices without the assistance of a trusted third party. McCune, et al. [12] proposed Seeing-is-Believing (SiB), a system which uses a visual channel. The SiB visual channel consists of one device displaying the hash of its public key in the form of a two-dimensional barcode, and the other device reading this information using a photo camera. Strong mutual authentication in SiB requires running two separate unilateral authentication steps. In this paper, we show how strong mutual authentication can be achieved even with a unidirectional visual channel, where SiB could provide only a weaker property termed as presence. This could help reduce the SiB execution time and improve usability. By adopting recently proposed improved pairing protocols, we propose how visual channel authentication can be used even on devices that have very limited displaying capabilities, all the way down to a device whose display consists of a cheap single light-source, such as an LED. We also describe a new video codec that may be used to improve execution time of pairing in limited display devices, and can be used for other applications besides pairing.

NLS is one of the stream ciphers submitted to the eSTREAM project. We present a distinguishing attack on NLS by Crossword Puzzle (CP) attack method which is newly introduced in this paper. We build the distinguisher by using linear approximations of both the non-linear feedback shift register (NFSR) and the nonlinear filter function (NLF). Since the bias of the distinguisher depends on the $Konst$ value, which is a key-dependent word, we present the graph showing how the bias of distinguisher vary with $Konst$. In result, we estimate the average bias to be around $O(2^{-30})$. Therefore, we claim that NLS is distinguishable from truly random cipher after observing $O(2^{60})$ keystream words on the average. The experiments also show that our distinguishing attack is successful on $90.3\%$ of $Konst$ among $2^{32}$ possible values.

In a multipartite access structure, the set of players is divided into $K$ different entities, in such a way that all players of the same entity play the same role in the structure. Not many results are known about these structures, when $K \geq 3$. Even if the total characterization of ideal multipartite access structures seems a very ambitious goal, we take a first step in this direction. On the one hand, we detect some conditions that directly imply that a multipartite structure cannot be ideal. On the other hand, we prove that three wide families of multipartite access structures are ideal. We believe that the techniques employed in these proofs are so general that they could be used to prove in the future more general results related to the characterization of ideal multipartite access structures.

We describe a faithful embedding of the Dolev-Yao model of Backes, Pfitzmann, and Waidner (CCS 2003) in the theorem prover Isabelle/HOL. This model is cryptographically sound in the strong sense of reactive simulatability/UC, which essentially entails the preservation of arbitrary security properties under active attacks and in arbitrary protocol environments. The main challenge in designing a practical formalization of this model is to cope with the complexity of providing such strong soundness guarantees. We reduce this complexity by abstracting the model into a sound, light-weight formalization that enables both concise property specifications and efficient application of our proof strategies and their supporting proof tools. This yields the first tool-supported framework for symbolically verifying security protocols that enjoys the strong cryptographic soundness guarantees provided by reactive simulatability/UC. As a proof of concept, we have proved the security of the Needham-Schroeder-Lowe protocol using our framework.

Since Diffie-Hellman \cite{DH76}, many secure systems, based on discrete logarithm or Diffie-Hellman assumption in $\mathbb{Z}_p$, were introduced in the literature. In this work, we investigate the possibility to construct efficient primitives from exponentiation techniques over $\mathbb{Z}_p$. Consequently, we propose a new pseudorandom generator, where its security is proven under the decisional Diffie-Hellman assumption. Our generator is the most efficient among all generators from $\mathbb{Z}_p^*$ that are provably secure under standard assumptions. If an appropriate precomputation is allowed, our generator can produce $O(\log\log p)$ bits per modular multiplication. This is the best possible result in the literature (even improved by such a precomputation as well). Interestingly, our generator is the first provably secure under a decisional assumption and might be instructive for discovering potentially more efficient generators in the future. Our second result is a new family of universally collision resistant hash family (CRHF). Our CRHF is provably secure under the discrete log assumption and is more efficient than all previous CRHFs that are provably secure under standard assumptions (especially without a random oracle). This result is important, especially when the unproven hash functions (e.g., MD4, MD5, SHA-1) were broken by Wang et al. \cite{W+05,WY05,WYY05}.

We construct the first fully collusion resistant tracing traitors system with sublinear size ciphertexts and constant size private keys. More precisely, let $N$ be the total number of users. Our system generates ciphertexts of size $O(\sqrt{N})$ and private keys of size $O(1)$. We build our system by first building a simpler primitive called private linear broadcast encryption (PLBE). We then show that any PLBE gives a tracing traitors system with the same parameters. Our system uses bilinear maps in groups of composite order.

We introduce the notion of Linear Integer Secret-Sharing (LISS) schemes, and show constructions of such schemes for any access structure. We show that any LISS scheme can be used to build a secure distributed protocol for exponentiation in any group. This implies, for instance, distributed RSA protocols for arbitrary access structures and with arbitrary public exponents.

HMAC was proved by Bellare, Canetti and Krawczyk [2] to be a PRF assuming that (1) the underlying compression function is a PRF, and (2) the iterated hash function is weakly collision-resistant. However, recent attacks show that assumption (2) is false for MD5 and SHA-1, removing the proof-based support for HMAC in these cases. This paper proves that HMAC is a PRF under the sole assumption that the compression function is a PRF. This recovers a proof based guarantee since no known attacks compromise the pseudorandomness of the compression function, and it also helps explain the resistance-to-attack that HMAC has shown even when implemented with hash functions whose (weak) collision resistance is compromised. We also show that an even weaker-than-PRF condition on the compression function, namely that it is a privacy-preserving MAC, suffices to establish HMAC is a MAC as long as the hash function meets the very weak requirement of being computationally almost universal, where again the value lies in the fact that known attacks do not invalidate the assumptions made.

We consider the problem of efficiently generating sequences in hardware for use in certain cryptographic algorithms. The conventional method of doing this is to use a counter. We show that sequences generated by linear feedback shift registers (LFSRs) can be tailored to suit the appropriate algorithms. For hardware implementation, this reduces both time and chip area. As a result, we are able to suggest improvements to the design of DES Cracker built by the Electronic Frontier Foundation in 1998; provide an efficient strategy for generating start points in time-memory trade/off attacks; and present an improved parallel hardware implementation of a variant of the counter mode of operation of a block cipher.

(Revision of Sept. 2004 of a journal submission from Dec. 2000.) Certified mail is the fair exchange of a message for a receipt, i.e., the recipient gets the message if and only if the sender gets a receipt. It is an important primitive for electronic commerce and other atomicity services. Certified-mail protocols are known in the literature, but there was no rigorous definition yet, in particular for optimistic protocols and for many interleaved executions. We provide such a definition via an ideal system and show that a specific real certified-mail protocol is as secure as this ideal system in the sense of reactive simulatability in the standard model of cryptography and under standard assumptions. As certified mail without any third party is not practical, we consider optimistic protocols, which involve a third party only if one party tries to cheat. The real protocol resembles prior protocols, but we had to use a different cryptographic primitive to achieve simulatability. The communication model is synchronous. This proof first demonstrated that a cryptographic multi-step protocol can fulfil a general definition of reactive simulatability enabling concurrent composition. We also first showed how formal-method style reasoning can be applied over the ideal system in a cryptographically sound way. Moreover, the treatment of multiple protocol runs and their modular proof in spite of the use of common cryptographic primitives for all runs can be seen as a first example of what is now known as joint-state composition.

In a variety of group-oriented applications cryptographic primitives like group signatures or ring signatures are valuable methods to achieve anonymity of group members. However, in their classical form, these schemes cannot be deployed for applications that simultaneously require (i) to avoid centralized management authority like group manager and (ii) the signer to be anonymous only against non-members while group members have rights to trace and identify the signer. The idea of recently introduced {\it democratic group signatures} is to provide these properties. Based on this idea we introduce a group-oriented signature scheme that allows the group members to trace the identity of any other group member who issued a signature while non-members are only able to link the signatures issued by the same signer without tracing. For this purpose the signature scheme assigns to every group member a unique pseudonym that can be used by any non-member verifier to communicate with the anonymous signer from the group. We present several group-oriented application scenarios where this kind of linkability is essential. We propose a concrete linkable democratic group signature scheme for two-parties, prove its security in the random oracle model, and describe how to modularly extend it to the multi-party case.

In this paper we study the probability of differentials and characteristics over 2 rounds of the AES with the objective to understand how the components of the AES round transformation interact. We extend and correct the analysis of the differential properties of the multiplicative inverse in GF($2^n$). We show that AES has characteristics with a fixed-key probability that is many times larger than the EDP. For instance, in the case of 2-round AES, we measured factors up to $2^{100}$. We study the number of characteristics with EDP $>0$ whose probability adds up to the probability of a differential and derive formulas that allow to produce a close estimate of this number for any differential. We show how the properties discovered in our study can be used to explain the values of the differentials with the largest EDP values and to construct new distinguishers using truncated differentials.

We present the Zhuang-Zi algorithm, a new method for solving multivariate polynomial equations over a finite field. We describe the algorithm and present examples, some of which cannot be solved with the fastest known algorithms.

This paper takes UMAC --- a message authentication algorithm (MAC) optimized for performance on 32-bit architectures --- as its starting point, and adapts its strategies for optimum performance on 64-bit architectures. The resulting MAC, called UMAC8, achieves per message forgery probabilities of about $2^{-60}$ and $2^{-120}$ for tags of length 64 and 128 bits. The UMAC strategies are discussed at length and adapted for 64-bit environments, but are also modified to address several UMAC shortcomings, particularly key-agility and susceptibility to timing attacks. UMAC achieved peak throughput rates, when generating 64-bit tags, of 1.0 CPU cycle per byte of message authenticated, while UMAC8 achieves 0.5 cycles per byte.

Vector Stream Cipher (VSC) is a stream cipher designed by ChaosWare and patented by NICT (formerly CRL), Japanese patents 3030341 and 3455758, US patent 6,668,265. VSC is recommended by the Softbank Technology Corporation for use in high bandwidth and high security applications. In this paper we present a practical attack instantly recovering the entire secret key of the high-speed single-round VSC variants with only 4 known subsequent plaintext blocks showing how all single-round VSC variants can be trivially broken due to their simple algebraic nature. The algorithm presented in this paper cannot break the 8-round VSC, but it can be easily adapted to any particular high-speed single-round VSC variant and extended to break some of the multiple-round VSC variants with very little effort and it may help accelerate other attacks.

In this contribution, we derive a novel parallel formulation of the standard Itoh-Tsujii algorithm for multiplicative inverse computation over GF($2^m$). The main building blocks used by our algorithm are: field multiplication, field squaring and field square root operators. It achieves its best performance when using a special class of irreducible trinomials, namely, $P(X) = X^m + X^k + 1$, with $m$ and $k$ odd numbers and when implemented in hardware platforms. Under these conditions, our experimental results show that our parallel version of the Itoh-Tsujii algorithm yields a speedup of about 30% when compared with the standard version of it. Implemented in a Virtex 3200E FPGA device, our design is able to compute multiplicative inversion over GF($2^193$) after 20 clock cycles in about $0.94\mu$S.

We describe a new and practical identity-based key encapsulation mechanism that is secure in the standard model against chosen-ciphertext (CCA2) attacks. Since our construction is direct and not based on hierarchical identity-based encryption, it is more efficient than all previously proposed schemes. Furthermore, we give the first chosen-ciphertext secure identity-based key encapsulation mechanism with threshold key delegation and decryption in the standard model.

This paper aims at introducing generalized Jacobians as a new candidate for discrete logarithm (DL) based cryptography. The motivation for this work came from the observation that several practical DL-based cryptosystems, such as ElGamal, the Elliptic and Hyperelliptic Curve Cryptosystems, XTR, LUC as well as CEILIDH can all naturally be reinterpreted in terms of generalized Jacobians. However, usual Jacobians and algebraic tori are thus far the only generalized Jacobians implicitly utilized in cryptography. In order to go one step further, we here study the simplest nontrivial generalized Jacobians of an elliptic curve. In this first of a series of articles, we obtain explicit formulae allowing to efficiently perform arithmetic operations in these groups. This work is part of our doctoral dissertation, where security aspects are considered in depth. As a result, these groups thus provide the first concrete example of semi-abelian varieties suitable for DL-based cryptography.

Given a Boolean function $f$ on $n$-variables, we find a reduced set of homogeneous linear equations by solving which one can decide whether there exist annihilators at degree $d$ or not. Using our method the size of the associated matrix becomes $\nu_f \times (\sum_{i=0}^{d} \binom{n}{i} - \mu_f)$, where, $\nu_f = |\{x | wt(x) > d, f(x) = 1\}|$ and $\mu_f = |\{x | wt(x) \leq d, f(x) = 1\}|$ and the time required to construct the matrix is same as the size of the matrix. This is a preprocessing step before the exact solution strategy (to decide on the existence of the annihilators) that requires to solve the set of homogeneous linear equations (basically to calculate the rank) and this can be improved when the number of variables and the number of equations are minimized. As the linear transformation on the input variables of the Boolean function keeps the degree of the annihilators invariant, our preprocessing step can be more efficiently applied if one can find an affine transformation over $f(x)$ to get $h(x) = f(Bx+b)$ such that $\mu_h = |\{x | h(x) = 1, wt(x) \leq d\}|$ is maximized (and in turn $\nu_h$ is minimized too). We present an efficient heuristic towards this. Our study also shows for what kind of Boolean functions the asymptotic reduction in the size of the matrix is possible and when the reduction is not asymptotic but constant.

Kurosawa-Desmedt encryption scheme is a variation of Cramer-Shoup encryption schemes, which are the first practical schemes secure against adaptive chosen ciphertext attack in standard model. We introduce a variant of Kurosawa-Desmedt encryption scheme, which is not only secure against adaptive chosen ciphertext attack but also slightly more efficient than the original version.

We improve on the best known cryptanalysis of the stream cipher Py by using a hidden Markov model for the carry bits in addition operations where a certain distinguishing event takes place, and constructing from it an "optimal distinguisher" for the bias in the output bits which makes more use of the information available. We provide a general means to efficiently measure the efficacy of such a hidden Markov model based distinguisher, and show that our attack improves on the previous distinguisher by a factor of 2^16 in the number of samples needed. Given 2^72 bytes of output we can distinguish Py from random with advantage greater than 1/2, or given only a single stream of 2^64 bytes we have advantage 0.03.

Authenticated encryption schemes used in order to send one message to one recipient have received considerable attention in the last years. We investigate the case of schemes, we call authenticated $\mathtt{1{\to}n}$ schemes, that allow one to encrypt efficiently in a public-key setting a message for several, say $n$, recipients in an authenticated manner. We propose formal security definitions for such schemes that work also for $n=1$ and which are stronger and/or more general than those currently proposed. We then present a flexible mode of operation that transforms any $\mathtt{1{\to}1}$ authenticated encryption scheme working on small messages into a $\mathtt{1{\to}n}$ authenticated encryption scheme working on longer messages. We show that it allows the construction of efficient $\mathtt{1{\to}n}$ schemes that are proved secure for the strongest security notion.

Recently Manik et al. [13] proposed a novel remote user authentication scheme using bilinear pairings. Chou et al. [14] identified a weakness in Manik et al.’s scheme and made an improvement. In this paper, we show that both Manik et al.’s and Chou et al.’s schemes are insecure against forgery attack and replay attack.

Low degree annihilators for Boolean functions are of great interest in cryptology because of algebraic attacks on LFSR-based stream ciphers. Several polynomial algorithms for construction of low degree annihilators are introduced in this paper. The existence of such algorithms is studied for the following forms of the function representation: algebraic normal form (ANF), disjunctive normal form (DNF), conjunctive normal form (CNF), and arbitrary formula with the Boolean operations of negation, conjunction, and disjunction. For ANF and DNF of a Boolean function $f$ there exist polynomial algorithms that find the vector space $A_d (f)$ of all annihilators of degree $\leqslant d$. For CNF this problem is NP-hard. Nevertheless author introduces one polynomial algorithm that constructs some subspace of $A_d (f)$ having formula that represents $f$.

We present a general framework for constructing families of elliptic curves of prime order with prescribed embedding degree. We demonstrate this method by constructing curves with embedding degree k = 10, which solves an open problem posed by Boneh, Lynn, and Shacham. We show that our framework incorporates existing constructions for k = 3, 4, 6, and 12, and we give evidence that the method is unlikely to produce infinite families of curves with embedding degree k > 12.

This paper presents a practical digital signature scheme to be used in conjunction with network coding. Our scheme simultaneously provides authentication and detects malicious nodes that intentionally corrupt content on the network. The homomorphic property of the signatures allows nodes to sign any linear comination of the incoming packets without contacting the signing authority, but it is computationally infeasible for a node to sign a linear combination of the packets without disclosing what linear combination was used in the generation of the packet. Furthermore, we prove that the signature scheme is secure under well known cryptographic assumptions of the hardness of the Discrete-Log problem and the computational co-Diffie-Hellman problem on elliptic curves. Our scheme has a three-fold advantage over schemes based on homomorphic hashing: Firstly, we do not need to securely transmit hash values of the packets that the source transmits; secondly, since our scheme is based on elliptic curves, smaller security parameters suffice and this translates to improved efficiency since the bit lengths involved are smaller; finally, our scheme provides authentication of the data in addition to detecting pollution of packets.

Abstract. We show two ways of recovering all matching documents, in the Ostrovsky et al. Private Search [3], while requiring considerably shorter buffers. Both schemes rely on the fact that documents colliding in a buffer position provide the sum of their plaintexts. Efficient decoding algorithms can make use of this property to recover documents never present alone in a buffer position.