The original paper does not have an abstract. This is a scanned version of the original hand written manuscript of this paper. It appeared in print as a Harvard University Technical Report, but at some point the university ran out of copies. At that time copies of the hand written version started to circulate, and were the only ones available. As access to these copies has become difficult I have scanned my copy of the paper and I'm posting it on the web for others to read. *Note that the manuscript has a different title, but the paper is most commonly (if not only) cited with this title. Thus, I assume that it should continue to be cited in this manner with reference to the original technical report.

The unlinkability is an important security property that blind signature schemes should satisfy. But we find that the several blind signature schemes [1,2,3] are linkable. The Signer can derive a link between a protocol view and a valid blind signature. They are not secure.

In this paper we analyse the security of two authenticated group key agreement schemes based on the group key agreement protocol of Burmester and Desmedt. One scheme was proposed by Burmester and Desmedt, and uses a separate authentication scheme to achieve authentication among the participants. We show that this scheme suffers from a number of security vulnerabilities. The other scheme was generated using the general protocol compiler of Katz and Yung. We show that in some circumstances, even if key confirmation is implemented, this scheme still suffers from insider attacks (which are not covered by the security model used by Katz and Yung).

To protect copyrighted digital data against piracy, codes with different secure properties such as frameproof codes, secure frameproof codes, codes with identifiable parent property (IPP codes), traceability codes (TA codes) are introduced. In this paper, we study these codes together with related combinatorial objects called separating and perfect hash families. We introduce for the first time the notion of difference function families and use these difference function families to give generalized recursive techniques that can be used for any kind of secure codes and hash families. We show that some previous recursive techniques are special cases of these new techniques.

This document revisits the PEKE (Probabilistic Encryption Key Exchange) cryptosystem and proposes the enhanced PEKEv1.25 that performs a hash computation on the original PEKE output in order to improve the security assurance and to broaden the field of use. For a key establishment application where only the server side publishes a long-term public key and can adequately protect the private key counterpart from implementation attacks, we claim that PEKE is unsurpassed in security and efficiency, among the finite field arithmetic cryptosystems (e.g. RSA and finite field Diffie-Hellman). We use an original definition for the type of key encapsulation service provided by PEKE, hoping that this abstract definition captures the characteristics of the protocol and usage context. However, we only suggest that related security proofs are encouraging for the security of PEKE.

Recently, Chang et al. proposed an authenticated key agreement and protected password change scheme. They claimed that their scheme is simple and efficient. However, in this letter we point out that their protected password change protocol is insecure under the denial-of-service attack and the dictionary attack in some situations.

This paper tries to sell a potential approach to making the process of writing and verifying our cryptographic proofs less prone to errors. Specifically, I advocate creating an automated tool to help us with the mundane parts of writing and checking common arguments in our proofs. On a high level, this tool should help us verify that two pieces of code induce the same probability distribution on some of their common variables. In this paper I explain why I think that such a tool would be useful, by considering two very different proofs of security from the literature and showing the places in those proofs where having this tool would have been useful. I also explain how I believe that this tool can be built. Perhaps surprisingly, it seems to me that the functionality of such tool can be implemented using only ``static code analysis'' (i.e., things that compilers do).

Most recently, Lee B. et al proposed a key issuing protocol for ID-based cryptography to solve the key escrow problem. However in this letter, we show that a malicious key generation center (KGC) can successfully attack the protocol to obtain users¡¯ private keys. This means that in the protocol, the key escrow problem isn¡¯t really removed.

We introduce a new method of achieving intrusion-resilience in the cryptographic protocols. More precisely we show how to preserve security of such protocols, even if a malicious program (e.g. a virus) was installed on a computer of an honest user (and it was later removed). The security of our protocols relies on the assumption that the amount of data that the adversary can transfer from the infected machine is limited (however, we allow the adversary to perform any efficient computation on user's private data, before deciding on what to transfer). We focus on two cryptographic tasks, namely: authenticated key exchange and entity authentication. Our method is based on the results from the Bounded-Storage Model.

Miyaji et.al proposed a fully functional(i.e., satisfying unforgeability, exculpability,anonymity, traceability, unlinkability, and revocability.) group signature over only known-order groups, that is based only on Discrete logarithm related assumptions, specifically, multiple DLP they proposed in the same paper [MU04]. In this paper, we point out their scheme and an improved scheme [ZZW05] do not have unlinkability.

We prove that for $d>1$ the information rate of the perfect secret sharing scheme based on the edge set of the $d$-dimensional cube is exactly $2/d$. Using the technique developed, we also prove that the information rate of the infinite $d$-dimensional lattice is $1/d$.

The MQV protocol of Law, Menezes, Qu, Solinas and Vanstone is possibly the most efficient of all known authenticated Diffie-Hellman protocols that use public-key authentication. In addition to great performance, the protocol has been designed to achieve a remarkable list of security properties. As a result MQV has been widely standardized, and has recently been chosen by the NSA as the key exchange mechanism underlying ``the next generation cryptography to protect US government information." One question that has not been settled so far is whether the protocol can be proven secure in a rigorous model of key-exchange security. In order to provide an answer to this question we analyze the MQV protocol in the Canetti-Krawczyk model of key exchange. Unfortunately, we show that MQV fails to a variety of attacks in this model that invalidate its basic security as well as many of its stated security goals. On the basis of these findings, we present HMQV, a carefully designed variant of MQV, that provides the same superb performance and functionality of the original protocol but for which all the MQV's security goals can be formally proved to hold in the random oracle model under the computational Diffie-Hellman assumption. We base the design and proof of HMQV on a new form of ``challenge-response signatures", derived from the Schnorr identification scheme, that have the property that both the challenger and signer can compute the {\em same} signature; the former by having chosen the challenge and the latter by knowing the private signature key. REVISION: In http://eprint.iacr.org/2005/205, Menezes [32] describes some shortcomings in our analysis that lead to the need for a prime-order verification of public DH values in the protocol. Some of Menezes's claims are correct and some other are not. We keep the originally posted paper here but add a {\em Preface} section (preceding the introduction) that briefly explains these findings and their implications to our results. In essence, the provability of HMQV and its security superiority relative to MQV remain valid; even computation-wise, after adding the verification steps where needed, HMQV is as efficient as (and in some cases even more efficient than) MQV

In this paper we propose a new 32-bit RC4 like keystream generator. The proposed generator produces 32 bits in each iteration and can be implemented in software with reasonable memory requirements. Our experiments show that this generator is 3.2 times faster than original 8-bit RC4. It has a huge internal state and offers higher resistance against state recovery attacks than the original 8-bit RC4. We analyze the randomness properties of the generator using a probabilistic approach. The generator is suitable for high speed software encryption.

An increasingly important design constraint for software running on ubiquitous computing devices is security, particularly against physical methods such as side-channel attack. One well studied methodology for defending against such attacks is the concept of indistinguishable functions which leak no information about program control flow since all execution paths are computationally identical. However, the constructing such functions by hand is laborious and error prone as their complexity increases. We investigate techniques for automating this process and find that effective solutions can be constructed with only minor amounts of computational effort.

In this paper we demonstrate the existence of a number of weaknesses in a leakage-resilient authenticated key transport (RSA-AKE) protocol due to Shin, Kobara and Imai.

We introduce mechanisms for secure keyword searches on a document server. We propose protocols with computational privacy, query correctness assurances and minimal or no leaks: the server either correctly executes client queries or (if it behaves maliciously) is immediately detected. The client is then provided with strong assurances proving the authenticity and completeness of server replies. This is different from existing research efforts, where a cooperating, non-malicious server behavior is assumed. We also strengthen the privacy guarantees. The oblivious search protocol not only hides (from the server) the outsourced data but also does not leak client access patterns, the queries themselves, the association between previously searched keywords and returned documents or between newly added documents and their corresponding keywords (not even in encrypted form). This comes naturally at the expense of additional computation costs which we analyze in the context of today's off the shelf hardware. In a reasonable scenario, a single CPU off-the-shelf PC can easily handle hundreds of such oblivious searches per minute.

We present a cryptographically sound formal method for proving correctness of key exchange protocols. Our main tool is a fragment of a symbolic protocol logic. We demonstrate that proofs of key agreement and key secrecy in this logic imply simulatability in Shoup's secure multi-party framework for key exchange. As part of the logic, we present cryptographically sound abstractions of CMA-secure digital signatures and a restricted form of Diffie-Hellman exponentiation, which is a technical result of independent interest. We illustrate our method by constructing a proof of security for a simple authenticated Diffie-Hellman protocol.

We introduce and motivate the concept of unclonable group identification, that provides maximal protection against sharing of identities while still protecting the anonymity of users. We prove that the notion can be realized from any one-way function and suggest a more efficient implementation based on specific assumptions.

This work is concerned with the security of the standard T10 OSD protocol, a capability-based protocol for object stores designed by the OSD SNIA working group. The Object Store security protocol is designed to provide access control enforcement in a distributed storage setting such as a Storage Area Network (SAN) environment. In this work we consider in particular the ability of the OSD protocol to enforce *confinement*, which is the property that even misbehaving participants can not leak secret information across predefined boundaries. We observe that being a "pure capability" protocol, the plain vanilla OSD protocol is incapable of enforcing confinement. We show, however, that given a trustworthy infrastructure for authentication and secure channels, the protocol can be used in a manner that achieves the desired property (and does not require any change in the message format). Thus we demonstrate that object stores can in principle be used in a standard fashion in applications that require protection against leakage of secret data. Having identified a problem and proposed a solution, we proceed to prove formally that the proposed protocol indeed meets all its security goals. In the process we refine common cryptographic models in order to be able to reason about confinement, and then devise a precise model for a distributed capability-based access-control mechanism. To our knowledge, this is the first time such a model for access-control is defined in a cryptographic setting, and defining it highlights what can and cannot be achieved by such mechanisms.

k-times anonymous authentication (k-TAA) schemes allow members of a group to be anonymously authenticated by application providers for a bounded number of times. k-TAA has application in e-voting, e-cash, electronic coupons and anonymous trial browsing of content. In this paper, we extend k-TAA model to dynamic k-TAA in which application providers can independently grant or revoke users from their own groups and so have the required control on their clients. We give a formal model for dynamic k-TAA, propose a dynamic k-times anonymous authentication scheme from bilinear pairing, and prove its security. We also construct an ordinary k-TAA from the dynamic scheme and show communication efficiency of the schemes compared to the previously proposed schemes.

In this paper, we suggest to use the curve $\curve, b=0 \mbox{ or } 1$ over $\Ftn$ for a secure and efficient pairing-based cryptosystems. For this curve, we develop efficient algorithms to compute the Tate pairing and give an implementation result of Tate paring on the curve $H_0$.

In recent papers \cite{Bar05} and \cite{CKL}, Barreto et al and Choie et al worked on hyperelliptic curves $H_b$ defined by $y^2+y = x^5 + x^3 + b$ over a finite field $\Ftn$ with $b=0$ or $1$ for a secure and efficient pairing-based cryptosystems. We find a completely general method for computing the Tate-pairing over divisor class groups of the curves $H_b$ in a very explicit way. In fact, the Tate-pairing is defined over the entire divisor class group of a curve, not only over the points on a curve. So far only pointwise approach has been made in ~\cite{Bar05} and ~\cite{CKL} for the Tate-pairing computation on the hyperelliptic curves $H_b$ over $\Ftn$. Furthermore, we obtain a very efficient algorithm for the Tate pairing computation over divisors by reducing the cost of computing. We also find a crucial condition for divisor class group of hyperelliptic curve to have a significant reduction of the loop cost in the Tate pairing computation.

We propose two stream ciphers based on a non-secure pseudorandom number generator (called the mother generator). The mother generator is here chosen to be the Mersenne Twister (MT), a widely used 32-bit integer generator having 19937 bits of internal state and period $2^19937-1$. One proposal is CryptMT, which computes the accumulative product of the output of MT, and use the most significant 8 bits as a secure random numbers. Its period is proved to be $2^19937-1$, and it is 1.5-2.0 times faster than the most optimized AES in counter-mode. The other proposal, named Fubuki, is designed to be usable also as a block cipher. It prepares nine different kinds of encryption functions (bijections from blocks to blocks), each of which takes a parameter. Fubuki encrypts a sequence of blocks (= a plain message) by applying these encryption functions iteratedly to each of the blocks. Both the combination of the functions and their parameters are pseudorandomly chosen by using its mother generator MT. The key and the initial value are passed to the initialization scheme of MT.

Abstract: The COSvd Ciphers has been proposed by Filiol and others (2004). It is a strengthened version of COS stream cipher family denoted COSvd that has been adopted for at least one commercial standard. We propose a distinguish attack on this version, and prove that, it is distinguishable from a random stream. In the COSvd Cipher used one S-Box (10×8) on the final part of cipher. We focus on S-Box and use weakness this S-Box for distinguish attack. In addition, found a leak on HNLL that the sub s-boxes don’t select uniformly. We use this property for an Improve distinguish attack.

Protocols for authenticated key exchange (AKE) allow parties within an insecure network to establish a common session key which can then be used to secure their future communication. It is fair to say that group AKE is currently less well understood than the case of two-party AKE; in particular, attacks by malicious insiders --- a concern specific to the group setting --- have so far been considered only in a relatively ``ad-hoc'' fashion. The main contribution of this work is to address this deficiency by providing a formal, comprehensive model and definition of security for group AKE which automatically encompasses insider attacks. We do so by defining an appropriate ideal functionality for group AKE within the universal composability (UC) framework. As a side benefit, any protocol secure with respect to our definition is secure even when run concurrently with other protocols, and the key generated by any such protocol may be used securely in any subsequent application. In addition to proposing this definition, we show that the resulting notion of security is strictly stronger than the one proposed by Bresson, et al. (termed ``AKE-security''), and that our definition implies all previously-suggested notions of security against insider attacks. We also show a simple technique for converting any AKE-secure protocol into one secure with respect to our definition.

We propose a variant of the Paillier cryptosystem that improves efficiency in encryption, re-encryption and decryption while preserving the homomorphic property. We then use this variant to construct a new verifiable shuffle system and prove its security. We show that the new shuffle scheme has the least number of rounds and exponentiations compared to all known shuffle schemes. Finally, we show how to construct a publicly verifiable mix-net using the shuffle system.

Some message authentication codes (MACs) are vulnerable to multiple forgery attacks, in which an attacker can gain information that allows her to succeed in forging multiple message/tag pairs. This property was first noted in MACs based on universal hashing, such as the Galois/Counter Mode (GCM) of operation for block ciphers. However, we show that CBC-MAC and HMAC also have this property, and for some parameters are more vulnerable than GCM. We present multiple-forgery attacks against these algorithms, then analyze the security against these attacks by using the expected number of forgeries. We compare the different MACs using this measure. This document is a pre-publication draft manuscript.

When developing secure, high-performance cryptographic software, the programmer is presented with a wide range of problems. Not only must they be conversant with pertinent scientific results, they must efficiently translate said results into a practical context. Unlike when writing normal programs, they are given little help from either the language or compiler: both are typically too general purpose to offer domain specific optimisation or analysis that would save the programmer time and reduce the potential for error. As a step toward solving this problem we present CAO, a cryptography-aware domain-specific language and associated compiler system. Rather than being a panacea, we pitch CAO as a mechanism for transferring and automating the expert knowledge of cryptographers into a form which is accessible to anyone writing security conscious software.

We study pseudorandom generator (PRG) constructions G^f : {0,1}^l -> {0,1}^{l+s} from one-way functions f : {0,1}^n \to {0,1}^m. We consider PRG constructions of the form G^f(x) = C(f(q_{1}) ... f(q_{poly(n)})) where C is a polynomial-size constant depth circuit (i.e. AC^0) and C and the q's are generated from x arbitrarily. We show that every black-box PRG construction of this form must have stretch s bounded as s < l ( log^{O(1)} n)/ m + O(1) = o(l). This holds even if the PRG construction starts from a one-to-one function f : {0,1}^n \to {0,1}^m where m < 5n. This shows that either adaptive queries or sequential computation are necessary for black-box PRG constructions with constant factor stretch (i.e. s = \Omega(l)) from one-way functions, even if the functions are one-to-one. On the positive side we show that if there is a one-way function f : {0,1}^n \to {0,1}^m that is regular (i.e. the number of preimages of f(x) depends on |x| but not on x) and computable by polynomial-size constant depth circuits then there is a PRG : {0,1}^l \to {0,1}^{l+1} computable by polynomial-size constant depth circuits. This complements our negative result above because one-to-one functions are regular. We also study constructions of average-case hard functions starting from worst-case hard ones, i.e. hardness amplifications. We show that if there is an oracle procedure Amp^f in the polynomial time hierarchy (PH) such that Amp^f is average-case hard for every worst-case hard f, then there is an average-case hard function in PH \emph{unconditionally}. Bogdanov and Trevisan (FOCS '03) and Viola (CCC'03) show related but incomparable negative results.

In this paper we propose a new class of cryptosystems that utilizes metric continuity. The geometric cryptosystem considered in this paper as the main example of metric cryptosystems has a number of interesting properties such as resistance to several basic cryptographic attacks, efficiency and detection of transmission errors.

Encryption algorithms are becoming more necessary to ensure data is securely transmitted over insecure communication channels. FOX is a recently developed algorithm and its structure is based on the already proven IDEA (International Data Encryption Algorithm) cipher. FOX is a symmetric (private key) block cipher. Its top-level structure uses the Lai-Massey scheme and the round functions used in the scheme are substitution permutation networks (SPN). Its flexibility lies in the fact that it can be efficiently implemented in hardware and software. We report some of the first results of implementing the cipher on an FPGA.

In this paper we show that two potential security vulnerabilities exist in the strong password-only authenticated key exchange scheme due to Jablon. Two standardised schemes based on Jablon's scheme, namely the first password-based key agreement mechanism in ISO/IEC FCD 11770-4 and the scheme BPKAS-SPEKE in IEEE P1363.2 also suffer from one or both of these security vulnerabilities. We further show that other password-based key agreement mechanisms, including those in ISO/IEC FCD 11770-4 and IEEE P1363.2, also suffer from these two security vulnerabilities. Finally, we propose means to remove these security vulnerabilities.

Py (pronounced Roo, a shorthand for Kangaroo) is a new stream cipher designed especially for the Ecrypt stream cipher contest. It is based on a new kind of primitive, which we call Rolling Arrays. It also uses various other ideas from many types of ciphers, including variable rotations and permutations. In some sense, this design is a kind of a new type of rotor machine, which is specially designed with operations that are very efficient in software. The allowed stream size is $2^{64}$ bytes in each stream (or $2^{40}$ in the smaller version Py6). The security claims of the cipher are that no key recovery attacks can be performed with complexity smaller than that of exhaustive search, and distinguishing attacks are also impractical with a similar complexity. The speed of the cipher is impressively fast, as it is more than 2.5 times faster than RC4 on a Pentium III (with less than 2.9 cycles/byte when implemented with the API of NESSIE and tested with the NESSIE software).

High levels of security often imply that the computation time should be independent of the value of involved secrets. When the expected answer of the solver is either a solution or unsatisfiable, then the previous assumption leads to algorithms that take always the computation time of the worst case. This is particularly disturbing for NP-hard combinatorial problems. In this work we start from the observation that sometimes (specially for hard problems) users find it acceptable to receive as answer either a solution, the answer unsatisfiable or a failure with meaning don't know. More exactly users accept incomplete solvers. As argued in [Silaghi,Flairs 05], for certain problems privacy reasons lead users to prefer having an answer meaning don't know even when the secure multi-party computation could have proven unsatisfiable (to avoid revealing that all alternatives are infeasible). While the solution proposed there is slower than complete algorithms, here we show secure stochastic solutions that are faster than complete solvers, allowing to address larger problem instances. Two new refined concepts of privacy are introduced, namely 'requested t-privacy' that factors out treatment of knowledge of the protocol in t-privacy, and a slightly weaker version called 'non-uniform requested t-privacy'. In the last section we discuss arithmetic circuits for complete and stochastic solutions to constraint optimization problems.

Attack is possible upon all three RSA analogue PKCs based on singular cubic curves given by Koyama. While saying so, Seng et al observed that the scheme become insecure if a linear relation is known between two plaintexts. In this case, attacker has to compute greatest common divisor of two polynomials corresponding to those two plaintexts. However, the computation of greatest common divisor of two polynomials is not efficient. For the reason, the degree e of both polynomials, an encryption exponent, is quite large. In this paper, we propose an algorithm, which makes the attack considerably efficient. Subsequently we identify isomorphic attack on the Koyama schemes by using the isomorphism between two singular cubic curves.

The security of iterated hash functions relies on the properties of underlying compression functions. We study highly efficient compression functions based on block ciphers. We propose a model for high-rate compression functions, and give an upper bound for the rate of any collision resistant compression function in our model. In addition, we show that natural generalizations of constructions by Preneel, Govaerts, and Vandewalle to the case of rate-$2$ compression functions are not collision resistant.

In this paper, we propose an attack method to find collisions of MD4 hash function. This attack is the improved version of the attack which was invented by Xiaoyun Wang et al [1]. We were able to find collisions with probability almost 1, and the average complexity to find a collision is upper bounded by three times of MD4 hash operations. This result is improved compared to the original result of [1] where the probability were from $2^{-6}$ to $2^{-2}$, and the average complexity to find a collision was upper bounded by $2^8$ MD4 hash operations. We also point out the lack of sufficient conditions and imprecise modifications for the original attack in [1].

In this paper we describe a simple protocol for securely delegating elliptic-curve pairings. A computationally limited device (typically a smart-card) will delegate the computation of the pairing e(A,B) to a more powerful device (for example a PC), in such a way that: 1. the powerful device learns nothing about the points being paired (A and B), nor about the pairing’s result e(A,B), 2. and the limited device is able to detect when the powerful device is cheating. We also describe more efficient variants of our protocol when one of the points or both are already known, and further efficiency gains when constant points are used.

We introduce a new digital signature model, called conditionally verifiable signature (CVS), which allows a signer to specify and convince a recipient under what conditions his signature would become valid and verifiable; the resulting signature is not publicly verifiable immediately but can be converted back into an ordinary one (verifiable by anyone) after the recipient has obtained proofs, in the form of signatures/endorsements from a number of third party witnesses, that all the specified conditions have been fulfilled. A fairly wide set of conditions could be specified in CVS. The only job of the witnesses is to certify the fulfillment of a condition and none of them need to be actively involved in the actual signature conversion, thus protecting user privacy. It is guaranteed that the recipient cannot cheat as long as at least one of the specified witnesses does not collude. We formalize the concept of CVS and give a generic CVS construction based on any CPA-secure identity based encryption (IBE) scheme. Theoretically, we show that the existence of IBE with indistinguishability under a chosen plaintext attack (a weaker notion than the standard one) is necessary and sufficient for the construction of a secure CVS.\footnote{Due to page limit, some proofs are omitted here but could be found in the full version \cite{CB05ibecvs}.}

Time-stamping protocols, which assure that a document was existed at a certain time, are applied to some useful and practical applications such as electronic patent applications and so on. There are two major time-stamping protocols, the simple protocol and the linking protocol. In the former, a time-stamp authority issues a time-stamp token that is the digital signature of the concatenated value of a hashed message and the present time. In the latter, the time-stamp authority issues a time-stamp token that is the hash value of the concatenated value of a hashed message and the previous hash value. Although security requirements and analysis for above time-stamping protocols has been discussed, there are no strict cryptographic security notions for them. In this paper, we reconsider the security requirements for time-stamping protocols and define security notions for them, in a universally composable security sense, which was proposed by Canetti. We also show that these notions can be achieved using combinations of a secure key exchange protocol, a secure symmetric encryption scheme, and a secure digital signature scheme.

We introduce the notion of tamper-evidence for digital signature generation in order to defend against attacks aimed at covertly leaking secret information held by corrupted network nodes. This is achieved by letting observers (which need not be trusted) verify the absence of covert channels by means of techniques we introduce herein. We call our signature schemes tamper-evident since any deviation from the protocol is immediately detectable. We demonstrate our technique for RSA-PSS and DSA signature schemes and how the same technique can be applied to Feige-Fiat-Shamir (FFS) and Schnorr signature schemes. Our technique does not modify the distribution of the generated signature transcripts, and has only a minimal overhead in terms of computation, communication, and storage. Keywords. covert channel, malware, observer, subliminal channel, tamper-evident, undercover

In this paper we present a fully pipelined high speed hardware architecture for Galois/Counter Mode of Operation (GCM) by analyzing the data dependencies in the GCM algorithm at the architecture level. We show that GCM encryption circuit and GCM authentication circuit have similar critical path delays resulting in an efficient pipeline structure. The proposed GCM architecture yields a throughput of 34 Gbps running at 271 MHz using a 0.18 um CMOS standard cell library.

A secure sketch is a set of published data that can help to recover the original biometric data after they are corrupted by permissible noises, and by itself does not reveal much information about the original. Several constructions have been proposed for different metrics, and in particular, set difference. We observe that in many promising applications, set difference alone is insufficient to model the noises. We propose to look into point-set difference, which measures noises that not only remove/introduce new feature points in the biometric objects, but may also perturb the points. In this paper, we first give an improvement for set difference construction that can be extended to multi-sets, where the sketch is small and there is an efficient decoding algorithm. We next give a sketch for point-set difference in both one and two-dimensional spaces. By using results in almost k-wise independence, the size of the sketch is reduced to near-optimal.

In this paper, the block cipher Kaweichel is presented. It is an extension of Blowfish for 64-bit architectures. The aim is to use the commonplace instructions of modern microprocessors. A main objective was to harden against known attacks on Blowfish. The author does not claim intellectual property on Kaweichel and the cipher will remain unpatented. A C reference implementation is available on the web.

In this paper, we contribute the construction of practical perfect multiparty computation protocols based on the connectivity of graphs.

Broadcast encryption (BE) deals with the problem of establishing a secret, shared by $g=G-r$ \textit{privileged} nodes, among a set $G$ nodes. Specifically, a set of $r$ \textit{revoked} nodes are denied access to the secret. Many schemes to address this problem, based on key pre-distribution schemes (KPS), have been proposed in the literature. Most state-of-the-art methods employ tree-based techniques. However, \textit{random} key pre-distribution schemes (RKPS), which have received a lot of attention in the recent past (especially in the context of ad hoc and sensor network security), also cater for BE. In this paper we analyze the performance of BE using RKPSs. While in most tree-based methods the source of the broadcast is assumed to be the root of the tree (unless asymmetric cryptographic primitives can be used), BE using RKPSs caters for BE by \textit{peers} - without the need for asymmetric cryptography. Furthermore, unlike most BE schemes where the identities of the revoked nodes have to be explicitly specified, BE using RKPSs allow for protecting the identities of the revoked nodes, which could be a useful property in application scenarios where privacy is a crucial issue.

In this paper we analyse a password-based authenticated key establishment protocol due to Laih, Ding and Huang, which enables a user to authenticate himself to a server and negotiate a shared session key. This protocol is also designed to guarantee that a human being is actually involved in an ongoing protocol execution. However we show that the protocol suffers from offline dictionary attacks. We propose an enhanced password-based authenticated key establishment protocol which is secure against offline dictionary attacks, and that possesses an additional feature guaranteeing that a user is involved in each protocol execution.

We show that if a set of players hold shares of a value $a\in Z_p$ for some prime $p$ (where the set of shares is written $[a]_p$), it is possible to compute, in constant round and with unconditional security, sharings of the bits of $a$, i.e.~compute sharings $[a_0]_p, \ldots, [a_{l-1}]_p$ such that $l = \lceil \log_2(p) \rceil$, $a_0, \ldots, a_{l-1} \in \{0,1\}$ and $a = \sum_{i=0}^{l-1} a_i 2^i$. Our protocol is secure against active adversaries and works for any linear secret sharing scheme with a multiplication protocol. This result immediately implies solutions to other long-standing open problems, such as constant-round and unconditionally secure protocols for comparing shared numbers and deciding whether a shared number is zero. The complexity of our protocol is $O(l \log(l))$ invocations of the multiplication protocol for the underlying secret sharing scheme, carried out in $O(1)$.

In number theoretic cryptography there is always the problem of scaling-up security to a higher level. This usually means increasing the size of the modulus, from, say 1024 bits to 2048 bits. In pairing-based cryptography however another option is available, keeping the modulus constant and increasing instead the embedding degree. This has a big potential advantage in smart-card and embedded applications -- security can be scaled up while continuing to use the same sized calculations. For example a cryptographic co-processor which does 512-bit modular multiplications can be directly re-used in the higher security setting. Here we investigate the scaling-up issue in the context of prime characteristic non-supersingular elliptic curves. We also confirm the observation that at higher levels of security a slightly modified Weil pairing becomes more efficient than the Tate pairing.

We introduce an efficient random key pre-distribution scheme (RKPS) whose performance is 2 to 3 \textit{orders of magnitude} better than schemes of comparable complexity in the literature. This dramatic improvement is achieved by increasing \textit{insecure} storage complexity (for example using external flash memory). The proposed scheme is a combination of the Kerberos-like key distribution scheme (KDS) proposed by Leighton and Micali, and random key pre-distribution schemes based on subset intersections. We also investigate a simple security policy, DOWN (decrypt only when necessary) (which along with very reasonable assurances of tamper resistance / read-proofness could ensures that no more than \textit{one} secret an be exposed by tampering with a node), and its effect on the security of key pre-distribution schemes. The proposed scheme lends itself well for efficient implementation of the DOWN policy, and therefore in practice could be a secure and efficient alternative to more complex conventional key distribution schemes.

We introduce the first El Gamal based mix-net in which each mix-server partially decrypts and permutes its input, i.e., no re-encryption is necessary. An interesting property of the construction is that a sender can verify non-interactively that its message is processed correctly. We call this sender verifiability. We prove the security of the mix-net in the UC-framework against static adversaries corrupting any minority of the mix-servers. The result holds under the decision Diffie-Hellman assumption, and assuming an ideal bulletin board and an ideal zero-knowledge proof of knowledge of a correct shuffle. Then we construct the first proof of a decryption-permutation shuffle, and show how this can be transformed into a zero-knowledge proof of knowledge in the UC-framework. The protocol is sound under the strong RSA-assumption and the discrete logarithm assumption. Our proof of a shuffle is not a variation of existing methods. It is based on a novel idea of independent interest, and we argue that it is at least as efficient as previous constructions.

We develop a couple of new methods to reduce transmission overheads in broadcast encryption. The methods are based on the idea of assigning {\it one key per each partition using one-way key chains} after partitioning the users. One method adopts {\it skipping chains} on partitions containing up to $p$ revoked users and the other adopts {\it cascade chains} on partitions with layer structure. The scheme using the former reduces the transmission overhead down to $\frac r{p+1}$ asymptotically as $r$ grows, and the scheme using the latter keeps the transmission overhead very small when $r$ approaches 0, where $r$ is the number of revoked users. Combining the two schemes, we propose a new broadcast encryption scheme with least transmission overhead. Our schemes also possess a remarkable feature that any number of new users can join at any time without key update, which is not available for most of known practical schemes.

In this paper we will extend the Benes and Luby-Rackoff constructions to design various pseudo-random functions and pseudo-random permutations with near optimal information-theoretic properties. An example of application is when Alice wants to transmit to Bob some messages against Charlie, an adversary with unlimited computing power, when Charlie can receive only a percentage $\tau$ of the transmitted bits. By using Benes, Luby-Rackoff iterations, concatenations and fixing at 0 some values, we will show in this paper how to design near optimal pseudo-random functions for all values of $\tau$. Moreover we will show how to design near optimal pseudo-random permutations when $\tau$ can have any value such that the number of bits obtained by Charlie is smaller than the square root of all the transmitted bits.

We introduce a novel cryptographic paradigm of broadcast authentication with ``preferred'' verifiers (BAP). With BAP, the message source explicitly targets a set of one or more verifiers. For an attacker, forging authentication data of a source, for purposes of fooling preferred verifiers may be substantially more difficult than fooling other (non-preferred) verifiers. We investigate broadcast authentication (BA) with \textit{hashed random preloaded subsets} (HARPS), which caters for such a distinction. HARPS, provides for efficient broadcast authentication, with and without preferred verifiers.

Previously known techniques to construct pairing-friendly curves of prime or near-prime order are restricted to embedding degree $k \leqslant 6$. More general methods produce curves over $\F_p$ where the bit length of $p$ is often twice as large as that of the order $r$ of the subgroup with embedding degree $k$; the best published results achieve $\rho \equiv \log(p)/\log(r) \sim 5/4$. In this paper we make the first step towards surpassing these limitations by describing a method to construct elliptic curves of prime order and embedding degree $k = 12$. The new curves lead to very efficient implementation: non-pairing cryptosystem operations only need $\F_p$ and $\F_{p^2}$ arithmetic, and pairing values can be compressed to one \emph{sixth} of their length in a way compatible with point reduction techniques. We also discuss the role of large CM discriminants $D$ to minimize $\rho$; in particular, for embedding degree $k = 2q$ where $q$ is prime we show that the ability to handle $\log(D)/\log(r) \sim (q-3)/(q-1)$ enables building curves with $\rho \sim q/(q-1)$.

Providing anonymity support for peer-to-peer (P2P) overlay networks is critical. Otherwise, potential privacy attacks (e.g., network address traceback) may deter a storage source from providing the needed data. In this paper we use this practical application scenario to verify our observation that network-based anonymity can be modeled as a complexity based cryptographic problem. We show that, if the routing process between senders and recipients can be modeled as abstract entities, network-based anonymity becomes an analogy of cryptography. In particular, perfect anonymity facing an unbounded traffic analyst corresponds to Shannon's perfect secrecy facing an unbounded cryptanalyst. More importantly, in this paper we propose Probabilistic Polynomial Route (PPR) model, which is a new polynomially-bounded anonymity model corresponding to the Probabilistic Polynomial Time (PPT) model in cryptography. Afterwards, network-based anonymity attacks are with no exception in BPP. This phenomenon has not been discovered in previous anonymity research.

We present a provably secure tree based authenticated group key agreement protocol in dynamic scenario. Bilinear pairing and multi-signature are at the heart of our protocol. We prove that our protocol is provably secure in the standard security model of Bresson et al. An appropriate modification of Katz-Yung approach to tree based setting is adopted while proving its security against active adversaries. The protocol has an in-built hierarchical structure that makes it desirable for certain applications.

Construction of Boolean functions with cryptographic properties is an important and difficult work. In this paper, we concentrate on rotation symmetric Boolean functions(RSBFs), which are invariant under circular translation of indices. Recent research show that this class of Boolean function is rich in functions of cryptographic signifinance. In this paper, we consider the RSBFs on even number variable. We show that the matrix $_n\mathcal{A}$ may result in a better form after rearrange the representative elements. This allows us to improved the search strategy. At last, some combinaatorial results about ${\mathcal P}_n^{1}$ , which only apear in the case $n$ even, are presented in the case $n=2p$, $p$ be odd prime.

Since Bellare and Rogway's work [15], the indistinguishability-based security models of authenticated key agreement protocols in simple cases have been evolving for ten years. In this report, we review and organize the models under a unified framework with some new extensions. By providing a new ability (the Coin query) to adversaries and redefining two key security notions, the framework fully exploits an adversary's capability and can be used to prove all the commonly required security attributes of key agreement protocols with key confirmation. At the same time, the Coin query is also used to define a model which can be used to heuristically evaluate the security of a large category of authenticated protocols without key confirmation. We use the models to analyze a few pairing-based authenticated key agreement protocols.

The XL (EXTENDED LINEARIZATION) is an equation-solving algorithm ,which is used as direct attacks against multivariate Public-Key Cryptosystems and as final stages for many algebraic cryptanalysis used today. XL produces lots excrescent multiply monomials in the solving process. The original equations multiplied by excrescent monomials are worthless for solving equations, what's more they increase the complexity of computation. In this paper the behavior of XL is analyzed, and a new version of XL called RXL to handle this problem is presented. In RXL, part of XL's excrescent multiply monomials are removed before Gaussian Elimination, so, RXL is more efficient than XL. The experimental results show that RXL need only about 75\% computation of XL. It is easy to extend our method to the existing XL's variants, and all algorithms of XL family are improved.

Currently, many industrial initiatives focus on web-based applications. In this context an important requirement is that the user should only rely on a standard web browser. Hence the underlying security services also rely solely on a browser for interaction with the user. Browser-based identity federation is a prominent example of such a protocol. Unfortunately, very little is still known about the security of browser-based protocols, and they seem at least as error-prone as standard security protocols. In particular, standard web browsers have limited cryptographic capabilities and thus new protocols are used. Furthermore, these protocols require certain care by the user in person, which must be modeled. In addition, browsers, unlike normal protocol principals, cannot be assumed to do nothing but execute the given security protocol. In this paper, we lay the theoretical basis for the rigorous analysis and security proofs of browser-based security protocols. We formally model web browsers, secure browser channels, and the security-relevant browsing behavior of a user as automata. As a first rigorous security proof of a browser-based protocol we prove the security of password-based user authentication in our model. This is not only the most common stand-alone type of browser authentication, but also a fundamental building block for more complex protocols like identity federation.

The shrinking generator is a well-known key stream generator composed of two LFSR’s, LFSRx and LFSRc, where LFSRx is clock-controlled according to the regularly clocked LFSRc. In this paper we investigate the minimum required length of the output sequence for successful reconstruction of the LFSRx initial state in an optimal probabilistic divide and conquer correlation attack. We extract an exact expression for the joint probability of the prefix of length m of the output sequence of LFSRx and prefix of length n of the output sequence of the generator. Then we use computer simulation to compare our probability measure and two other probability measures, previousely proposed in [5] and [3], in the sense of minimum required output length. Our simulation results show that our measure reduces the required output length.

We introduce two new left-to-right integer recodings which can be used to perform scalar multiplication with a fixed sequence of operations. These recodings make it possible to have a simple power analysis resistant implementation of a group-based cryptosystem without using unified formulas or introducing dummy operations. This approach is very useful for groups in which the doubling step are less expensive than the addition step, for example with hyperelliptic curves over binary fields or elliptic curves with mixed coordinates.

We present a new primitive--Append-only Signatures (AOS)--with the property that any party given an AOS signature aossig[M_1] on message M_1 can compute aossig[M_1||M_2] for any message M_2, where M_1||M_2 is the concatenation of M_1 and M_2. We define the security of AOS, present concrete AOS schemes, and prove their security under standard assumptions. In addition, we find that despite its simple definition, AOS is equivalent to Hierarchical Identity-based Signatures (HIBS) through efficient and security-preserving reductions. Finally, we show direct applications of AOS to problems in network security. Our investigations indicate that AOS is both useful in practical applications and worthy of further study as a cryptographic primitive.

We propose a dynamic accumulator scheme from bilinear pairings, whose security is based on the Strong Diffie-Hellman assumption. We show applications of this accumulator in constructing an identity-based (ID-based) ring signature scheme with constant-size signatures and its interactive counterpart, and providing membership revocation to group signature, traceable signature and identity escrow schemes and anonymous credential systems. The ID-based ring signature scheme and the group signature scheme have extremely short signature sizes. The size of our group signatures with membership revocation is only half the size of the well-known ACJT00 scheme, which does not provide membership revocation. The schemes do not require trapdoor, so system parameters can be shared by multiple groups belonging to different organizations. All schemes proposed are provably secure in formal models. We generalize the definition of accumulators to model a wider range of practical accumulators. We provide formal models for ID-based ad-hoc anonymous identification schemes and identity escrow schemes with membership revocation, based on existing ones.

Group signature schemes allow a member of a group to sign messages anonymously on behalf of the group. In the case of later dispute, a designated group manager can revoke the anonymity and identify the originator of a signature. In Asiacrypt 2004, Nguyen and Safavi-Naini proposed a group signature scheme that has a constant-size public key and signature length, and more importantly, their group signature scheme does not require trapdoor. Their scheme is very efficient and the sizes of signatures are shorter compared to the existing schemes that were proposed earlier. In this paper, we point out that Nguyen and Safavi-Naini's scheme is insecure. In particular, we provide a cryptanalysis of the scheme that allows a non-member of the group to sign on behalf of the group. The resulting group signature can convince any third party that a member of the group has indeed generated such a signature, although none of the members has done it. Therefore, in the case of dispute, the group manager cannot identify who has signed the message. We also provide a new scheme that does not suffer against this problem.

We present a novel idea for user authentication that we call pass-thoughts. Recent advances in Brain-Computer Interface (BCI) technology indicate that there is potential for a new type of human-computer interaction: a user transmitting thoughts directly to a computer. The goal of a pass-thought system would be to extract as much entropy as possible from a user’s brain signals upon “transmitting” a thought. Provided that these brain signals can be recorded and processed in an accurate and repeatable way, a pass-thought system might provide a quasi two-factor, changeable, authentication method resilient to shoulder-surfing. The potential size of the space of a pass-thought system would seem to be unbounded in theory, due to the lack of bounds on what composes a thought, although in practice it will be finite due to system constraints. In this paper, we discuss the motivation and potential of pass-thought authentication, the status quo of BCI technology, and outline the design of what we believe to be a currently feasible pass-thought system. We also briefly mention the need for general exploration and open debate regarding ethical considerations for such technologies.

Although many watermarking schemes consider the case of universal verifiability, it is undesirable in some applications. Designated verification is a possible solution for this problem. Watermarking scheme with (non-interactive) designated verification through non-invertible schemes was proposed by Lee et al in 2003, to resolve multiple watermarking problem. Yoo et al [14] proposed a very similar watermarking scheme. In this paper, we propose a cryptanalytic attack on both of these schemes that allows a dishonest watermarker to send illegal watermarked images and to convince the designated verifier or customer that received watermarked images are valid. We modify the above schemes to overcome the attack. Further, we also propose a new robust watermarking scheme with (non-interactive) designated verification through non-invertible watermarks. Interestingly, our scheme can be extended for joint copyright protection (security of ownership rights for images to be owned by more than one entity).

We present a novel index calculus algorithm for the discrete logarithm problem (DLP) in degree 0 class groups of curves over finite fields. A heuristic analysis of our algorithm indicates that asymptotically for varying q, ``essentially all'' instances of the DLP in degree 0 class groups of curves represented by plane models of a fixed degree d over $\mathbb{F}_q$ can be solved in an expected time of $\tilde{O}(q^{2 -2/(d-2)})$. A particular application is that heuristically, ``essentially all'' instances of the DLP in degree 0 class groups of non-hyperelliptic curves of genus 3 (represented by plane curves of degree 4) can be solved in an expected time of $\tilde{O}(q)$. We also provide a method to represent ``sufficiently general'' (non-hyperelliptic) curves of genus $g \geq 3$ by plane models of degree $g+1$. We conclude that on heuristic grounds the DLP in degree 0 class groups of ``sufficiently general'' curves of genus $g \geq 3$ (represented initially by plane models of bounded degree) can be solved in an expected time of $\tilde{O}(q^{2 -2/(g-1)})$.

In this paper we analyze the combinatorial properties related to the Walsh spectra of rotation symmetric Boolean functions on even number of variables. These results are then applied in studying rotation symmetric bent functions.

The first practical identity based encryption (IBE) scheme was proposed by Boneh and Franklin. In this work we point out that there is a flawed step in the security reduction exhibited by the authors. Fortunately, it is possible to fix it without changing the scheme or the underlying assumption. In the second place, we introduce a variant of the seminal IBE scheme which allows a more efficient security reduction. The new scheme is simpler, and has more compact ciphertexts than Boneh-Franklin's proposal, while keeping the computational cost. Finally, we observe that the flawed step pointed out here is present in several works, and that our techniques can be applied to obtain tighter reductions for previous relevant schemes.

In this paper we examine the hard problems underlying asymmetric pairings, their precise relationships and how they affect a number of existing protocols. Furthermore, we present a new model for the elliptic curve groups used in asymmetric pairings, which allows both an efficient pairing and an efficiently computable isomorphism.

In this paper we analyze and discuss the cryptographic robustness of key-dependent substitution boxes (KDSBs); these can be found in some symmetric-key algorithms such as Khufu, Blowfish, and the AES finalist Twofish. We analyze KDSBs in the framework of composite permutations, completing the theory developed by O'Connor. Under the basic assumption that KDSBs are built choosing permutations randomly from the symmetric group $S_{2^m}$ by means of the key, the expressions of their linear and differential characteristics are derived. These results are used as a statistical tool to show that Twofish KDSBs, although very efficient, can be easily distinguished from truly randomly built KDSBs. We also analyze the motivations that lead to this previously unknown property; it can be concluded that the efficiency of the construction and the small computational complexity of Twofish KDSBs, although very desirable, cannot be easily obtained together with the highest level of security.

We propose a new secure communication primitive called an \emph{Intrusion-Resilient Channel (IRC)} that limits the damage resulting from key exposures and facilitates recovery. We define security against passive but mobile and highly adaptive adversaries capable of exposing even expired past secrets. We describe an intuitive channel construction using (as a black box) existing public key cryptosystems. The simplicity of the construction belies the technical challenges in its security proof. Additionally, we outline a general strategy for proving enhanced security for two-party protocols when an IRC is employed to secure all communication. Specifically, given a protocol proved secure against adversaries with restricted access to protocol messages, we show how the use of an IRC allows some of these adversary restrictions to be lifted. Once again, proving the efficacy of our intuitive approach turns out to be non-trivial. We demonstrate the strategy by showing that the intrusion-resilient signature scheme of [IR02] can be made secure against adversaries that expose even expired secrets.

A new technique is proposed in which bandwidth and memory are together used to reduce both the number of point additions and doublings required in computing random point multiplication. Using the proposed technique, we show that a significant speed-up can be obtained at the cost of slightly increased bandwidth. In addition, we show that the proposed technique is well-suited for parallel processing.

In this paper, we investigate the relationship between the squared Weil/Tate pairing and the plain Weil/Tate pairing. Along these lines, we first show that the squared pairing for arbitrary chosen point can be transformed into a plain pairing for the trace zero point which has a special form to compute them more efficiently. This transformation requires only a cost of some Frobenius actions. Additionally, we show that the squared Weil pairing can be computed more efficiently for trace zero point and derive an explicit formula for the 4th powered Weil pairing as an optimized version of the Weil pairing.

In1985, Shmuley proposed a theorem about intractability of Composite Diffie-Hellman [Sh85]. The Theorem of Shmuley may be paraphrased as saying that if there exist a probabilistic poly-time oracle machine which solves the Diffie-Hellman modulo an RSA-number with odd-order base then there exist a probabilistic algorithm which factors the modulo. In the other hand factorization of the module obtained only if we can solve the Diffie-Hellman with odd-order base. In this paper we show that even if there exist a probabilistic poly-time oracle machine which solves the problem only for even-order base and abstain answering the problem for odd-order bases still a probabilistic algorithm can be constructed which factors the modulo in poly-time for more than 98% of RSA-numbers.

In this paper we study a key exchange protocol similar to Diffie-Hellman key exchange protocol using abelian subgroups of the automorphism group of a non-abelian nilpotent group. We also generalize group no.92 of Hall-Senior table \cite{halltable}, for arbitrary prime $p$ and show that for those groups, the group of central automorphisms commute. We use these for the key exchange we are studying.

An efficient and semantically secure public key cryptosystem based on singular cubic curve is proposed in this paper. It is about two times faster than the cryptosystem of David at the same security label and more efficient than the Koyama scheme at high security level. Further, the partially known plaintext attack and the linearly related plaintext attacks are analyzed and concluded that those are not possible in the proposed scheme.

Several identity based and authenticated key agreement protocols have been proposed in recent years and all of them have been shown to be non-secure. It remains an open question to design secure identity based and authenticated key agreement protocols. In this paper, we propose an efficient identity-based and authenticated key agreement protocol IDAK using Weil/Tate pairing. A security model for identity based key agreement protocol is established and the security properties of IDAK are proved in this model with random oracle. In particular, it is shown that the IDAK protocol possesses all characteristics that a secure key agreement should have.

In this paper we analyze the $E_0$ cipher, which is the encryption system used in the Bluetooth specification. We suggest a uniform framework for cryptanalysis of the $E_0$ cipher. Our method requires 128 known bits of the keystream in order to recover the initial state of the LFSRs, which reflects the secret key of this encryption engine. In one setting, our framework reduces to an attack of D. Bleichenbacher. In another setting, our framework is equivalent to an attack presented by Fluhrer and Lucks. Our best attack can recover the initial state of the LFSRs after solving $2^{86}$ boolean linear systems of equations, which is roughly equivalent to the results obtained by Fluhrer and Lucks.

We construct a secure protocol for any multi-party functionality that remains secure (under a relaxed definition of security) when executed concurrently with multiple copies of itself and other protocols. We stress that we do *not* use any assumptions on existence of trusted parties, common reference string, honest majority or synchronicity of the network. The relaxation of security, introduced by Prabhakaran and Sahai (STOC '04), is obtained by allowing the ideal-model simulator to run in *quai-polynomial* (as opposed to polynomial) time. Quasi-polynomial simulation suffices to ensure security for most applications of multi-party computation. Furthermore, Lindell (FOCS '03, TCC' 04) recently showed that such a protocol is *impossible* to obtain under the more standard definition of *polynomial-time* simulation by an ideal adversary. Our construction is the first such protocol under reasonably standard cryptographic assumptions. That is, existence of a hash function collection that is collision resistent with respect to circuits of subexponential size, and existence of trapdoor permutations that are secure with respect to circuits of quasi-polynomial size. We introduce a new technique: ``protocol condensing''. That is, taking a protocol that has strong security properties but requires *super-polynomial* communication and computation, and then transforming it into a protocol with *polynomial* communication and computation, that still inherits the strong security properties of the original protocol. Our result is obtained by combining this technique with previous techniques of Canetti, Lindell, Ostrovsky, and Sahai (STOC '02) and Pass (STOC '04).

Given a corrupted word $\w = (w_1, \ldots, w_n)$ from a Reed-Solomon code of distance $d$, there are many ways to efficiently find and correct its errors. But what if we are instead given $(g^{w_1}, \ldots, g^{w_n})$ where $g$ generates some large cyclic group --- can the errors still be corrected efficiently? This problem is called \emph{error correction in the exponent}, and though it arises naturally in many areas of cryptography, it has received little attention. We first show that \emph{unique decoding} and \emph{list decoding} in the exponent are no harder than the computational Diffie-Hellman (CDH) problem in the same group. The remainder of our results are negative: * Under mild assumptions on the parameters, we show that \emph{bounded-distance decoding} in the exponent, under $e=d-k^{1-\epsilon}$ errors for any $\epsilon > 0$, is as hard as the discrete logarithm problem in the same group. * For \emph{generic} algorithms (as defined by Shoup, Eurocrypt 1997) that treat the group as a ``black-box,'' we show lower bounds for decoding that exactly match known algorithms. Our generic lower bounds also extend to decisional variants of the decoding problem, and to groups in which the decisional Diffie-Hellman (DDH) problem is easy. This suggests that hardness of decoding in the exponent is a qualitatively new assumption that lies ``between'' the DDH and CDH assumptions.

This report explicitly refutes the analysis behind a recent claim that NTRUEncrypt has a bit security of at most 74 bits. We also sum up some existing literature on NTRU and lattices, in order to help explain what should and what should not be classed as an improved attack against the hard problem underlying NTRUEncrypt. We also show a connection between Schnorr's RSR technique and exhaustively searching the NTRU lattice.

An ad-hoc anonymous identification scheme is a new multi-user cryptographic primitive that allows participants from a user population to form ad hoc groups, and then prove membership anonymously in such groups. Recently, Nguyen \cite{Lan05} proposed an ID-based ad-hoc anonymous identification scheme from bilinear pairings. However, in this paper, we propose an attack on Nguyen's ID-based ad-hoc anonymous identification scheme. We show that any one can impersonate a valid group member to perform the anonymous identification protocol successfully. Furthermore, we propose a solution to improve this scheme against our attack.

In this paper, we summarize the results achieved during our brief three months long research on collisions of the MD5 hash function. Being inspired by the results announced by Wang et al. [1] we independently developed methods for finding collisions which work for any initialization value and which are quicker than the methods presented in [1, 8]. It enables us to find a MD5 collision on a standard notebook PC roughly in 8 hours [7]. Independently on [1, 8], we discovered and propose several multi-message modification methods, which are more effective than methods described in [1, 8]. We show their principle.

We consider expansions of the Abadi-Rogaway logic of indistinguishability of formal cryptographic expressions. The formal language of this logic uses a box as notation for indecipherable strings, through which formal equivalence is defined. We expand the logic by considering different kinds of boxes corresponding to equivalence classes of formal ciphers. We consider not only computational, but also purely probabilistic, information-theoretic interpretations. We present a general, systematic treatment of the expansions of the logic for symmetric encryption. We establish general soundness and completeness theorems for the interpretations. We also present applications to specific settings not covered in earlier works: a purely probabilistic one that interprets formal expressions in One-Time Pad, and computational settings of the so-called type 2 (which-key revealing) cryptosystems based on computational complexity.

Bent functions are important cryptographic Boolean functions. In order to enumerate eight-variable bent functions, we solve the following three key problems. Firstly, under the action of $AGL(7,2)$, we almost completely classify $R(4,7)/R(2,7)$. Secondly, we construct all seven-variable \emph{plateaued} functions from the orbits of $R(4,7)/R(2,7)$. Thirdly, we present a fast algorithm to expand \emph{plateaued} function into bent functions. Based on the results above, it is feasible to enumerate eight-variable bent functions in practice.

This paper points out to a generic vulnerability of certain broadcast encryption schemes. This vulnerability can be effectively explored assuming chosen plaintext attacks, and in some cases even under ciphertext only attack. The developed methods for cryptanalysis are based on an attacking approach not taken into account in the security evaluations of the reported broadcast encryption schemes. The proposed attacks are based on employment of a dedicated time-data-memory trade-off approach for cryptanalysis. Two algorithms for cryptanalysis are proposed and their main characteristics regarding the complexity and required sample are pointed out. The algorithms are applied for cryptanalysis of particular recently reported broadcast encryption schemes implying that their security is far below the claimed ones.

A predicate is opaque for a given system, if an adversary will never be able to establish truth or falsehood of the predicate for any observed computation. This notion has been essentially introduced and studied in the context of transition systems whether describing the semantics of programs, security protocols or other systems. In this paper, we are interested in studying opacity in the probabilistic computational world. Indeed, in other settings, as in the Dolev-Yao model for instance, even if an adversary is $99\%$ sure of the truth of the predicate, it remains opaque as the adversary cannot conclude for sure. In this paper, we introduce a computational version of opacity in the case of passive adversaries called cryptographic opacity. Our main result is a composition theorem: if a system is secure in an abstract formalism and the cryptographic primitives used to implement it are secure, then this system is secure in a computational formalism. Security of the abstract system is the usual opacity and security of the cryptographic primitives is IND-CPA security. To illustrate our result, we give two applications: a short and elegant proof of the classical Abadi-Rogaway result and the first computational proof of Chaum's visual electronic voting scheme.

Recently, it has been proved that computational security can be automatically verified using the Dolev-Yao abstraction. We extend these results by adding a widely used component for cryptographic protocols: Diffie-Hellman exponentiation. Thus our main result is: if the Decisional Diffie-Hellman assumption is verified and the cryptographic primitives used to implement the protocol are secure, then safety in the symbolic world implies safety in the computational world. Therefore, it is possible to prove automatically safety in the computational world.

I present some results towards a classification of power functions with positive exponents that are Almost Perfect Nonlinear (APN), or equivalently differentially 2-uniform, over ${\mathbb{F}}_{2^n}$ for infinitely many $n$. APN functions are useful in constructing S-boxes in AES-like cryptosystems. An application of Weil's theorem on absolutely irreducible curves shows that a monomial $x^m$ is not APN over ${\mathbb{F}}_{2^n}$ for all sufficiently large $n$ if a related two variable polynomial has an absolutely irreducible factor defined over ${\mathbb{F}}_{2}$. I will show that the latter polynomial's singularities imply that except in three cases, all power functions have such a factor. Two of these cases are already known to be APN for infinitely many fields. A third case is still unproven. Some specific cases of power functions have already been known to be APN over only finitely many fields, but they will mostly follow from the main result below.

Within the next year, travelers from dozens of nations may be carrying a new form of passport in response to a mandate by the United States government. The e-passport, as it is sometimes called, represents a bold initiative in the deployment of two new technologies: Radio-Frequency Identification (RFID) and biometrics. Important in their own right, e-passports are also the harbinger of a wave of next-generation ID cards: several national governments plan to deploy identity cards integrating RFID and biometrics for domestic use. We explore the privacy and security implications of this impending worldwide experiment in next-generation authentication technology. We describe privacy and security issues that apply to e-passports, then analyze these issues in the context of the International Civil Aviation Organization (ICAO) standard for e-passports.

ID-based cryptosystem has been, for a few years, the most active area of research and currently is of great interest to the cryptographic society. In this work we survey three fundamental ID-based cryptographic primitives Digital Signature, Encryption and Key Agreement, which are based on the mathematical concepts Integer Factorization, Quadratic Residues and Bilinear Pairings. We review several schemes along with their efficiency and security considerations. The survey helps in understanding the research work carried out in the area of ID-based cryptosystems from the year 1984 to 2004.

We propose a two-party identity-based key agreement and key agreement with confirmation from pairing that can be used with escrow mode or without escrow mode.,It can also be used between users of different KGC (Key Generation Centre).We will show that the our scheme is a secure key agreement in the mode proposed by Bellare and Rogaway[2],and we will show that the scheme has the attribute of Known Key-Security ,Key-Compromise-Impersonation, Unknown-Key-Share, Perfect-Forward-Secrecy and Key-Control.

We prove a general domain extension theorem for pseudo-random functions (PRFs). Given a PRF $F$ from $n$ bits to $n$ bits, it is well known that employing $F$ in a chaining mode (CBC-MAC) yields a PRF on the bigger domain. Viewing each application of $F$ in this chaining mode to be a node in a graph, and the chaining as the edges between the nodes, the resulting graph is just a line graph. In this paper, we show that the underlying graph can be an arbitrary directed acyclic graph (DAG), and the resulting function on the larger domain is still a PRF. The only requirement on the graph is that it have unique source and sink nodes, and no two nodes have the same set of incident nodes. A new highly parallelizable MAC construction follows which has a critical path of only $3+\log ^{*} n $ applications of $F$.\\ \hspace*{0.1in} If we allow Galois field arithmetic, we can consider edge colored DAGs, where the colors represent multiplication in the field by the color number. We prove an even more general theorem, where the only restriction on the colored DAGs is that if two nodes ($u$ and $v$) have the same set of incident nodes $W$, then at least one $w$ in $W$ is incident on $u$ and $v$ with a different colored edge. PMAC (parallelizable message authentication \cite{black}) is a simple example of such graphs. The general thoerem allows one to have further optimizations over PMAC, and many modes which deal with variable lengths.

We identify and describe a new type of phishing attack that circumvents what is probably today's most efficient defense mechanism in the war against phishing, namely the shutting down of sites run by the phisher. This attack is carried out using what we call a distributed phishing attack (DPA). The attack works by a per-victim personalization of the location of sites collecting credentials and a covert transmission of credentials to a hidden coordination center run by the phisher. We show how our attack can be simply and efficiently implemented and how it can increase the success rate of attacks while at the same time concealing the tracks of the phisher. We briefly describe a technique that may be helpful to combat DPAs.

Some of the existing time memory tradeoff attacks (TMTO) on specific systems can be reinterpreted as methods for inverting general oneway functions. We apply these methods back to specific systems in ways not considered before. This provides the following startling results. No streamcipher can provide security equal to its key length; some important blockcipher modes of operations are vulnerable to TMTO; and no hash function can provide preimage resistance equal to its digest length.

Boolean functions form basic building blocks in various cryptographic algorithms. They are used for instance as filters in stream ciphers. Maximally non-linear (necessarily non-balanced) Boolean functions with an even number of variables are called bent functions. Bent functions can be modified to get balanced highly non-linear Boolean functions. Recently the first author has demonstrated how bent functions can be studied in a recursive framework of certain integer-valued functions. Based on this new approach we describe the practical systematic construction of $8$-bit bent functions. We outline also how to compute the number of all $8$-bit bent functions.

We present an update of the Pelican MAC function, called Pelican 2.0. Both versions have the Alred construction and are based on Rijndael. they are a factor 2.5 more efficient than CBC-MAC with Rijndael, while providing a comparable claimed security level. The difference between Pelican 2.0 and the original version is that the initial value changes from the all-zero string to another constant. The reason for this is the negative impact on security if key check values are available computed with a certain standard key check value algorithm that applies the block cipher to the zero string and takes as key check value its truncated output. The security impact of this on a number of standard MACs is studied in Cryptology ePrint Archive Report 2014/183 and the analysis carries over for Pelican.