In 2003, Boyd et al. have proposed two deniable authenticated key establishment protocols for Internet Key Exchange (IKE). However, both schemes have been broken by Chou et al. in 2005 due to their susceptibility to key-compromise impersonation (KCI) attack. In this paper, we put forward the improved variants of both Boyd et al.'s schemes in order to defeat the KCI attack. On top of justifying our improvements, we further present a detailed security analysis to ensure that the desired security attributes: deniability and authenticity remain preserved.

It is debatable if current direct-recording electronic voting machines can sufficiently be trusted for a use in elections. Reports about malfunctions and possible ways of manipulation abound. Voting schemes have to fulfill seemingly contradictory requirements: On one hand the election process should be verifiable to prevent electoral fraud and on the other hand each vote should be deniable to avoid coercion and vote buying. This work presents a new verifiable and coercion-free voting scheme Bingo Voting, which is based on a trusted random number generator. As a motivation for the new scheme two coercion/vote buying attacks on voting schemes are presented which show that it can be dangerous to let the voter contribute randomness to the voting scheme. A proof-of-concept implementation of the scheme shows the practicality of the scheme: all costly computations can be moved to a non time critical pre-voting phase.

This paper illustrates the use of ciphertext-policy attribute-based encryption (CP-ABE), a recently proposed primitive, in the setting of group key management. Specifically, we use the CP-ABE scheme of Bethencourt, Sahai and Waters to implement flat table group key management. Unlike past implementations of flat table, our proposal is resistant to collusion attacks. We also provide efficient mechanisms to refresh user secret keys (for perfect forward secrecy) and to delegate managerial duties to subgroup controllers (for scalability). Finally, we discuss performance issues and directions for future research.

Recently, Tanaka proposed an identity based non-interactive key sharing scheme and its corresponding identity based encryption scheme based on the intractability of integer factorization and discrete logarithm. The proposed identity based non-interactive key sharing scheme is similar to the well-known Maurer-Yacobi public key distribution scheme but the computational complexity for private key generation can be significantly reduced. It is also claimed that the proposed identity based non-interactive key sharing scheme is "collusion-attack free", i.e., secure against collusion attacks. In this paper, we analyze the security of the "collusion-attack free" identity based non-interactive key sharing scheme. First, we show that, without colluding with other users, a single user can recover some of the secret information of the private key generator. Then we show that a small group of users can collude to recover all of the secret information held by the private key generator. Thus, the "collusion-attack free" identity based non-interactive key sharing scheme can be completely compromised by collusion attacks.

An Attribute Based Group Signature (ABGS) allows a verifier to request a signature from a member of a group who possesses certain attributes. Therefore, a signature should authenticate a person in a group and prove ownership of certain properties. The major difference between our scheme and previous group signatures, is that the verifier can determine the role of the actual signer within the group. In this paper we define the first ABGS scheme, and security notions such as anonymity and traceability. We then construct the scheme and prove it secure.

In Crypto 2001, Bellare {\em et al.} introduced {\em online cipher} (or online permutation) and proposed two Hash-CBC mode constructions, namely {\bf HCBC} and {\bf HPCBC} along with security proofs. We observe that, the security proofs in their paper are {\em wrong} and it may not be fixed easily. In this paper, we provide a {\em simple} security analysis of these online ciphers. Moreover, we propose two variants of HPCBC, namely {\bf MHCBC-1} and {\bf MHCBC-2}. The first variant, MHCBC-1, is a slight modification of HPCBC so that it is more efficient in performance as well as in memory compare to HPCBC. The other one, MHCBC-2 requires only {\em one-key} (note that, HCBC and HPCBC require at least two and three keys respectively) and does not require any $\varepsilon$-$\mathrm{\Delta}$Universal Hash Family (which is costly in general).

We present an experimental block cipher, ConSum, based on a hitherto unstudied design element: the Conway transformation. ConSum features an extremely simple design and the ability to operate with arbitrary key lengths, block sizes and round numbers. We study it empirically and statistically so as to illustrate how it might be secure.

This paper is concerned about relating formal and computational models of cryptography in case of active adversaries when formal security analysis is done with first order logic. We first present a criticism of the way Datta et al. defined computational semantics to their Protocol Composition Logic, concluding that problems arise from focusing on occurrences of bit-strings on individual traces instead of occurrences of probability distributions of bit-strings across the distribution of traces. We therefore introduce a new, fully probabilistic method to assign computational semantics to the syntax. We present this via considering a simple example of such a formal model, the Basic Protocol Logic of K. Hasebe and M. Okada, but the technique is suitable for extensions to more complex situations such as PCL. The idea is to make use of the usual mathematical treatment of stochastic processes, hence be able to treat arbitrary probability distributions, non-negligible probability of collision, causal dependence or independence.

Non-interactive zero-knowledge proofs and non-interactive witness-indistinguishable proofs have played a significant role in the theory of cryptography. However, lack of efficiency has prevented them from being used in practice. One of the roots of this inefficiency is that non-interactive zero-knowledge proofs have been constructed for general NP-complete languages such as Circuit Satisfiability, causing an expensive blowup in the size of the statement when reducing it to a circuit. The contribution of this paper is a general methodology for constructing very simple and efficient non-interactive zero-knowledge proofs and non-interactive witness-indistinguishable proofs that work directly for groups with a bilinear map, without needing a reduction to Circuit Satisfiability. Groups with bilinear maps have enjoyed tremendous success in the field of cryptography in recent years and have been used to construct a plethora of protocols. This paper provides non-interactive witness-indistinguishable proofs and non-interactive zero-knowledge proofs that can be used in connection with these protocols. Our goal is to spread the use of non-interactive cryptographic proofs from mainly theoretical purposes to the large class of practical cryptographic protocols based on bilinear groups.

We have designed three fast implementations of recently proposed family of hash functions Edon--${\cal R}$. They produce message digests of length 256, 384 and 512 bits. We have defined huge quasigroups of orders $2^{256}$, $2^{384}$ and $2^{512}$ by using only bitwise operations on 32 bit values (additions modulo $2^{32}$, XORs and left rotations) and achieved processing speeds of the Reference C code of 16.18 cycles/byte, 24.37 cycles/byte and 32.18 cycles/byte on x86 (Intel and AMD microprocessors). In this paper we give their full description, as well as an initial security analysis.

We investigate the decoding problem of Reed-Solomon (RS) Codes, also known as the Polynomial Reconstruction Problem (PR), from a cryptographic hardness perspective. Namely, we deal with PR instances with parameter choices for which decoding is not known to be feasibly solvable and where part of the solution polynomial is the hidden input. We put forth a natural decisional intractability assumption that relates to this decoding problem: distinguishing between a single randomly chosen error-location and a single randomly chosen non-error location for a given corrupted RS codeword with random noise. We prove that under this assumption, PR-instances are entirely pseudorandom, i.e., they are indistinguishable from random vectors over the underlying finite field. Moreover, under the same assumption we show that it is hard to extract any partial information related to the hidden input encoded by the corrupted PR-instance, i.e., PR-instances hide their message polynomial solution in the semantic security sense. The above results lay a framework for the exploitation of PR as an intractability assumption for provable security of cryptographic primitives. Based on this framework, we present provably secure cryptographic constructions for (i) a pseudorandom extender, (ii) a semantically secure version of the Oblivious Polynomial Evaluation Protocol, and (iii) a stateful cipher with a set of interesting properties that include: semantic security, forward secrecy, error-correcting decryption and an array of random self-reducibility properties with respect to the plaintext choice, key choice and partial domain choice.

The cipher CTC (Courtois Toy Cipher) has been designed to demonstrate that it is possible to break on a PC a block cipher with good diffusion and very small number of known (or chosen) plaintexts. It has however never been designed to withstand all known attacks on block ciphers and Dunkelman and Keller have shown that a few bits of the key can be recovered by Linear Cryptanalysis (LC) - which cannot however compromise the security of a large key. This weakness can easily be avoided: in this paper we give a specification of CTC2, a tweaked version of CTC. The new cipher is MUCH more secure than CTC against LC and the key scheduling of CTC has been extended to use any key size, independently from the block size. Otherwise, there is little difference between CTC and CTC2. We will show that up to 10 rounds of CTC2 can be broken by simple algebraic attacks.

Motivated by the challenging task of designing ``secure'' vote storage mechanisms, we study information storage mechanisms that operate in extremely hostile environments. In such environments, the majority of existing techniques for information storage and for security are susceptible to powerful adversarial attacks. We propose a mechanism for storing a set of at most $K$ elements from a large universe of size $N$ on write-once memories in a manner that does not reveal the insertion order of the elements. We consider a standard model for write-once memories, in which the memory is initialized to the all $0$'s state, and the only operation allowed is flipping bits from $0$ to $1$. Whereas previously known constructions were either inefficient (required $\Theta(K^2)$ memory), randomized, or employed cryptographic techniques which are unlikely to be available in hostile environments, we eliminate each of these undesirable properties. The total amount of memory used by the mechanism is linear in the number of stored elements and poly-logarithmic in the size of the universe of elements. We also demonstrate a connection between secure vote storage mechanisms and one of the classical distributed computing problems: conflict resolution in multiple-access channels. By establishing a tight connection with the basic building block of our mechanism, we construct the first deterministic and non-adaptive conflict resolution algorithm whose running time is optimal up to poly-logarithmic factors.

This paper provides a probabilistic algorithm to determine generators of the m-torsion subgroup of the Jacobian of a hyperelliptic curve of genus two.

Braid cryptosystem was proposed in CRYPTO 2000 as an alternate public-key cryptosystem. The security of this system is based upon the conjugacy problem in braid groups. Since then, there have been several attempts to break the braid cryptosystem by solving the conjugacy problem in braid groups. In this paper, we first survey all the major attacks on the braid cryptosystem and conclude that the attacks were successful because the current ways of random key generation almost always result in weaker instances of the conjugacy problem. We then propose several alternate ways of generating hard instances of the conjugacy problem for use braid cryptography.

Compact e-cash schemes allow a user to withdraw a wallet containing $k$ coins in a single operation, each of which the user can spend unlinkably. One big open problem for compact e-cash is to allow multiple denominations of coins to be spent efficiently without executing the spend protocol a number of times. In this paper, we give a (\emph{partial}) solution to this open problem by introducing two additional protocols, namely, compact spending and batch spending. Compact spending allows spending all the $k$ coins in one operation while batch spending allows spending any number of coins in the wallet in a single execution. We modify the security model of compact e-cash to accommodate these added protocols and present a generic construction. While the spending and compact spending protocol are of constant time and space complexities, complexities of batch spending is linear in the number of coins to be spent together. Thus, we regard our solution to the open problem as {\it partial}. We provide two instantiations under the $q$-SDH assumption and the LRSW assumption respectively and present security arguments for both instantiations in the random oracle model.

There are several public key establishment protocols as well as complete public key cryptosystems based on allegedly hard problems from combinatorial (semi)group theory known by now. Most of these problems are search problems, i.e., they are of the following nature: given a property P and the information that there are objects with the property P, find at least one particular object with the property P. So far, no cryptographic protocol based on a search problem in a non-commutative (semi)group has been recognized as secure enough to be a viable alternative to established protocols (such as RSA) based on commutative (semi)groups, although most of these protocols are more efficient than RSA is. In this paper, we suggest to use decision problems from combinatorial group theory as the core of a public key establishment protocol or a public key cryptosystem. By using a popular decision problem, the word problem, we design a cryptosystem with the following features: (1) Bob transmits to Alice an encrypted binary sequence which Alice decrypts correctly with probability "very close" to 1; (2) the adversary, Eve, who is granted arbitrarily high (but fixed) computational speed, cannot positively identify (at least, in theory), by using a "brute force attack", the "1" or "0" bits in Bob's binary sequence. In other words: no matter what computational speed we grant Eve at the outset, there is no guarantee that her "brute force attack" program will give a conclusive answer (or an answer which is correct with overwhelming probability) about any bit in Bob's sequence.

Time Capsule Signature, first formalized by Dodis and Yum in Financial Cryptography 2005, is a digital signature scheme which allows a signature to bear a (future) time t so that the signature will only be valid at time t or later, when a trusted third party called time server releases time-dependent information for checking the validity of a time capsule signature. Also, the actual signer of a time capsule signature has the privilege to make the signature valid before time t. In this paper, we provide a new security model of time capsule signature such that time server is not required to be fully trusted. Moreover, we provide two e±cient constructions in random oracle model and standard model. Our improved security model and proven secure constructions have the potential to build some new E-Commerce applications.

We study the round complexity of various cryptographic protocols. Our main result is a tight lower bound on the round complexity of any fully-black-box construction of a statistically-hiding commitment scheme from one-way permutations, and even from trapdoor permutations. This lower bound matches the round complexity of the statistically-hiding commitment scheme due to Naor, Ostrovsky, Venkatesan and Yung (CRYPTO '92). As a corollary, we derive similar tight lower bounds for several other cryptographic protocols, such as single-server private information retrieval, interactive hashing, and oblivious transfer that guarantees statistical security for one of the parties. Our techniques extend the collision-finding oracle due to Simon (EUROCRYPT '98) to the setting of interactive protocols (our extension also implies an alternative proof for the main property of the original oracle). In addition, we substantially extend the reconstruction paradigm of Gennaro and Trevisan (FOCS '00). In both cases, our extensions are quite delicate and may be found useful in proving additional black-box separation results.

We will review the past history of the attacks and defenses of TTM. The main tool of the past attacks is linear algebra, while the defenses rely on algebraic geometry and commutative algebra. It is hard for attackers to completely succeed against the formidable castle of modern mathematics. It is out of the common sense that problems of algebraic geometry can always be solved by linear algebra. It repeatly happens that the attackers find some points which could be exploited by linear algebra using complicated computations, usually the attackers overexaggerate the power of linear algebra and illusional believe that they succeed totally, then the points are disappearing by a simple twist in algebraic geometry and commutative algebra. All attacks in the past simply strengthen the structures of TTM. For these facts we are very grateful to the attackers. Last year there is a paper entitled "{\it Breaking a New Instance of TTM Cryptosystem}" by Xuyun Nie, Lei Hu, Jianyu Li, Crystal Updegrove and Jintai Ding [11] claiming a successive attack on the scheme of TTM presented in [7]. In our previous article [8], we show that their claim is a {\bf misunderstanding}. The discussions of [11] and [8] center on if in [11] the authors really just use the {\it public keys}. Right aft er we post [8], to settle the discrepancy of [11] and [8], we have sent the public keys of a new example (which is attached as the {\bf Appendix I} of this article) to the authors of [11] to test their claim in the {\it abstract} of [11], i.e., they will be able to crack TTM using only the public keys (in 20 minutes as stated in the abstract of [11]). After two weeks, Mr Nie asks the private keys of the new example for his {\it theoretical analysis} and we will consider his request only if he concedes that he is unable to crack the new example by the method of [11]. Since there is no definite answer from them after 4 months, we will publish the example in this article to give other people chances to attack. Furthermore, we publish a second example as {\bf Appendix II}.

We introduce an offline precomputation technique for mix-nets that drastically reduces the amount of online computation needed. Our method can be based on any additively homomorphic cryptosystem and is applicable when the number of senders and the maximal bit-size of messages are relatively small.

A tripartite authenticated key agreement protocol is generally designed to accommodate the need of three specific entities in communicating over an open network with a shared secret key, which is used to preserve data confidentiality and integrity. Since Joux proposed the first pairing-based one-round tripartite key agreement protocol in 2000, numerous authenticated protocols have been proposed after then. However, most of them have turned out to be flawed due to their inability in achieving some desirable security attributes. In 2005, Lin-Li had identified the weaknesses of Shim's protocol and subsequently proposed their improved scheme by introducing an extra verification process. In this paper, we prove that Lin-Li's improved scheme remains insecure due to its susceptibility to the insider impersonation attack. Based on this, we propose an enhanced scheme which will not only conquer their defects, but also preserves the desired security attributes of a key agreement protocol.

In this paper, we present a practical attack on the signature scheme SFLASH proposed by Patarin, Goubin and Courtois in 2001 following a design they had introduced in 1998. The attack only needs the public key and requires about one second to forge a signature for any message, after a one-time computation of several minutes. It can be applied to both SFLASHv2 which was accepted by NESSIE, as well as to SFLASHv3 which is a higher security version.

This paper introduces Hidden Identity-based Signatures (Hidden-IBS), a type of digital signatures that provide mediated signer-anonymity on top of Shamir's Identity-based signatures. The motivation of our new signature primitive is to resolve an important issue with the kind of anonymity offered by ``group signatures'' where it is required that either the group membership list is {\em public} or that the opening authority is {\em dependent} on the group manager for its operation. Contrary to this, Hidden-IBS do not require the maintenance of a group membership list and they enable an opening authority that is totally independent of the group manager. As we argue this makes Hidden-IBS much more attractive than group signatures for a number of applications. In this paper, we provide a formal model of Hidden-IBS as well as two efficient constructions that realize the new primitive. Our elliptic curve construction that is based on the SDH/DLDH assumptions produces signatures that are merely half a Kbyte long and can be implemented very efficiently. To demonstrate the power of the new primitive, we apply it to solve a problem of current onion-routing systems focusing on the Tor system in particular. Posting through Tor is currently blocked by sites such as Wikipedia due to the real concern that anonymous channels can be used to vandalize online content. By injecting a Hidden-IBS inside the header of an HTTP POST request and requiring the exit-policy of Tor to forward only properly signed POST requests, we demonstrate how sites like Wikipedia may allow anonymous posting while being ensured that the recovery of (say) the IP address of a vandal would be still possible through a dispute resolution system. Using our new Hidden-IBS primitive in this scenario allows to keep the listing of identities (e.g., IP addresses) of Tor users computationally hidden while maintaining an independent Opening Authority which would not have been possible with previous approaches.

Evidences of delivery are essential for resolving (and avoiding) disputes on delivery of messages, in classical as well as electronic commerce. We present the first rigorous specifications and provably-secure implementation, for a communication layer providing time-stamped evidences for the message delivery process. This improves on existing standards for evidences (‘non-repudiation’) services, based on informal specifications and unproven designs. Our work also improves on the large body of analytical works on tasks related to evidences of delivery, such as certified mail/delivery protocols and fair exchange (of signatures). We improve by addressing practical needs and scenarios, using realistic synchronization and communication assumptions, supporting time-outs and failures, and providing well-defined interface to the higher-layer protocols (application). Furthermore, we use the layered specifications framework, allowing provably-secure use of our protocol, with lower and higher layer protocols, with complete re-use of our analysis (theorems).

In this paper, a method for the efficient computation of Tate pairings on curves which is a generalization of Barreto, etc.'s method [2] is presented. It can reduce the number of loops in the computation of the Tate pairing. The method can be applied not only to supersingular curves but to non-supersingular curves. An example shows the cost of the algorithm in this paper can be reduced by 18% than the best known algorithm in some elliptic curves.

We propose the idea of building a secure hash using quadratic or higher degree multivariate polynomials over a finite field as the compression function, whose security relies on simple hard questions. We analyze some security properties and potential feasibility, where the compression functions are randomly chosen high-degree polynomials. Next, we propose to improve on the efficiency of the system by using some specially designed polynomials using composition of maps and certain sparsity property, where the security of the system would then relies on stronger assumptions.

In this paper we propose a new class of Fair Exchange Signature Scheme(FESS) that allows two players to exchange digital signatures in a fair way. Our signature scheme is a general idea and has various implementations on most of the existing signature schemes, thus it may also be considered as an interesting extension of concurrent signature presented in EUROCRYPT 2004 that is constructed from ring signatures. In our scheme, two unwakened signatures signed separately by two participants can be verified easily by the other player, but it would not go into effect until an extra piece of commitment keystone is released by one of the players. Once the keystone revealed, two signatures are both aroused and become effective. A key feature of the proposed scheme is that two players can exchange digital signatures simultaneously through a secret commitment keystone without involvement of any Trusted Third Party. Moreover, the efficiency of our signature scheme is higher than that of concurrent signature.

In this paper, we introduce the exact concept of ID-based signature without trusted Private Key Generator (PKG), which solves the key escrow problem through binding two partially public keys with a same identity. In this scheme, PKG is prevented from forging a legal user’s signature because he only generates the partially private key. Using Gap Diffie-Hellman (GDH) groups, we construct an efficient ID-based signature scheme without trusted PKG, which security relies on the hardness of the Computation Diffie-Hellman Problem (CDHP). More precisely, under the random oracle model, our scheme is proved to be secure against existential forgery on adaptively chosen message and ID attack, which is a natural ID-based version of the standard adaptively chosen message attack, assuming CDHP is intractable. Our scheme not only eliminates the inherent key escrow problem but also has a higher efficiency than the existing schemes.

The threshold voltage VT of EEPROM cells is a very important technological parameter for storing data and keys in a cryptographic device like smartcards. Furthermore, main objective of this paper is to check whether it is possible to get the key stored in the EEPROM cell through measuring the current consumption of the cryptographic device during read key command for encryption before and after baking at a certain temperature. This stress (baking) of the charge in the floating gate of the cells shifts the threshold voltage. Especially this effect will be considered whether the unknown key in the EEPROM cells can be estimated by using the charge shift in the floating gate. The test labs might need to check during an evaluation procedure of the smartcards if parts or whole key can be estimated successfully by stressing the threshold parameter VT. The result of this evaluation is (will be) an input for countermeasures against possible attacks. It is also an additional input for further design structures in order to avoid information gain after baking the EEPROM cells at a certain temperature.

We construct two simple families of two-message $(n,1)$-oblivious transfer protocols based on degree-$t$ homomorphic cryptosystems with the communication of respectively $1+\lceil n/t \rceil$ and $3+\lceil n/(t+1) \rceil$ ciphertexts. The construction of both families relies on efficient cryptocomputable conditional disclosure of secret protocols; the way this is done may be of independent interest. The currently most interesting case $t=2$ can be based on the Boneh-Goh-Nissim cryptosystem. As an important application, we show how to reduce the communication of virtually any existing oblivious transfer protocols by proposing a new related communication-efficient generic transformation from computationally-private information retrieval protocols to oblivious transfer protocols.

We study the design of practical blind signatures in the universal composability (UC) setting against adaptive adversaries. We introduce a new property for blind signature schemes that is fundamental for managing adaptive adversaries: an {\em equivocal blind signature} is a blind signature protocol where a simulator can construct the internal state of the client so that it matches a simulated transcript even after a signature was released. % We present a general construction methodology for building practical adaptively secure blind signatures: the starting point is a 2-move ``lite blind signature'', a lightweight 2-party signature protocol that we formalize and implement both generically as well as number theoretically: formalizing a primitive as ``lite'' means that the adversary is required to show all private tapes of adversarially controlled parties; this enables us to conveniently separate zero-knowledge (ZK) related security requirements from the remaining security properties in the primitive's design methodology. % We then focus on the exact ZK requirements for building blind signatures. To this effect, we formalize two special ZK ideal functionalities, single-verifier-ZK (SVZK) and single-prover-ZK (SPZK) and we investigate the requirements for realizing them in a commit-and-prove fashion as building blocks for adaptively secure UC blind signatures. SVZK can be realized without relying on a multi-session UC commitment; as a result, we realize SVZK in a very efficient manner using number theoretic mixed commitments while employing a constant size common reference string and without the need to satisfy non-malleability. Regarding SPZK we find the rather surprising result that realizing it only for static adversaries is sufficient to obtain adaptive security for UC blind signatures. This important observation simplifies blind signature design substantially as one can realize SPZK very efficiently in a commit-and-prove fashion using merely an extractable commitment. We instantiate all the building blocks of our design methodology efficiently thus presenting the first practical UC blind signature that is secure against adaptive adversaries in the common reference string model. In particular, we present (1) a lite equivocal blind signature protocol that is based on elliptic curves and the 2SDH assumption of Okamoto, (2) efficient implementations of SPZK, SVZK for the required relations. % Our construction also takes advantage of a round optimization method we discuss and it results in a protocol that has an overall communication overhead of as little as 3Kbytes, employing six communication moves and a constant length common reference string. We also present alternative implementations for our equivocal lite blind signature thus demonstrating the generality of our approach. Finally we count the exact cost of realizing blind signatures with our protocol design by presenting the distance between the $\Fbsig$-hybrid world and the $\Fcrs$-hybrid world as a function of environment parameters. The distance calculation is facilitated by a basic lemma we prove about structuring UC proofs that may be of independent interest.

We present a new non-interactive message authentication protocol in manual channel model (NIMAP, for short) using the weakest assumption on the manual channel (i.e. assuming the strongest adversary). Our protocol uses enhanced target collision resistant (eTCR) hash family and is provably secure in the standard model. We compare our protocol with protocols with similar properties and show that the new NIMAP has the same security level as the best previously known NIMAP whilst it is more practical. In particular, to authenticate a message such as a 1024-bit public key, we require an eTCR hash family that can be constructed from any off-the-shelf Merkle-Damgård hash function using randomized hashing mode. The underlying compression function must be {\em evaluated second preimage resistant} (eSPR), which is a strictly weaker security property than collision resistance. We also revisit some closely related security notions for hash functions and study their relationships to help understanding our protocol.

Anonymity(key-privacy) as well as security(data-privacy) are all important features in public-key encryption applications. In this paper two new and general concepts, named “relevant anonymity” and “relevant security”, are defined. Based-upon these concepts some general results on anonymity in public-key encryption are proved, which fall in three categories. The first results are two general relationships between anonymity and security; the second are a sufficient and necessary condition for chosen-plaintext anonymity in Fujisaki-Okamoto hybrid construction and a sufficient condition for its chosen-ciphertext anonymity; the third is a sufficient condition for chosen-ciphertext anonymity in Okamoto-Pointcheval hybrid construction (REACT). All these conditions are also easy-to-use criteria in practice. By examples such general consequences are applied to some specific schemes and as a result anonymity of some well-known schemes are re-established in a simpler way. Furthermore, NISSIE scheme PSEC-/1/2/3’s chosen-ciphertext anonymity are proved.

Trivium is a stream cipher candidate of the eStream project. It has successfully moved into phase three of the selection process under the hardware category. No attacks faster than the exhaustive search have so far been reported on Trivium. Bivium-A and Bivium-B are simplified versions of Trivium that are built on the same design principles but with two registers. The simplified design is useful in investigating Trivium type ciphers with a reduced complexity and provides insight into effective attacks which could be extended to Trivium. This paper focuses on an algebraic analysis which uses the boolean satisfiability problem in propositional logic. For reduced variants of the cipher, this analysis recovers the internal state with a minimal amount of keystream observations.

We present a new mechanized prover for showing correspondence assertions for cryptographic protocols in the computational model. Correspondence assertions are useful in particular for establishing authentication. Our technique produces proofs by sequences of games, as standard in cryptography. These proofs are valid for a number of sessions polynomial in the security parameter, in the presence of an active adversary. Our technique can handle a wide variety of cryptographic primitives, including shared- and public-key encryption, signatures, message authentication codes, and hash functions. It has been implemented in the tool CryptoVerif and successfully tested on examples from the literature.

In a threshold broadcast encryption scheme, a sender chooses (ad-hoc) a set of $n$ receivers and a threshold $t$, and then encrypts a message by using the public keys of all the receivers, in such a way that the original plaintext can be recovered only if at least $t$ receivers cooperate. Previously proposed threshold broadcast encryption schemes have ciphertexts whose length is $\O(n)$. In this paper, we propose new schemes, for both PKI and identity-based scenarios, where the ciphertexts' length is $\O(n-t)$. The construction uses secret sharing techniques and the Canetti-Halevi-Katz transformation to achieve chosen-ciphertext security. The security of our schemes is formally proved under the Decisional Bilinear Diffie-Hellman (DBDH) Assumption.

We propose an interesting efficient member ID-based group signatures, i.e., verification of output from algorithm OPEN run by the group manager does not have to refer to a registration table (acting as certification list). The proposal is free of GM-frameability, i.e., secret key of member is not escrowed to GM, which is unique among all known member ID-based group signatures as far as we know. The proposal also has two distinguished extra features, one is that the group manager does not have to maintain a registration table to obtain the real identity of the signer in contrast to other schemes, another is that it provides an alternative countermeasure against tampered registration table to applying integrity techniques to the table in case registration table is maintained.

At Eurocrypt 2006, Paterson and Yau demonstrated how flaws in the Linux implementation of IPsec could be exploited to break encryption-only configurations of ESP, the IPsec encryption protocol. Their work highlighted the dangers of not using authenticated encryption in fielded systems, but did not constitute an attack on the actual IPsec standards themselves; in fact, the attacks of Paterson and Yau should be prevented by any standards-compliant IPsec implementation. In contrast, this paper describes new attacks which break any RFC-compliant implementation of IPsec making use of encryption-only ESP. The new attacks are both efficient and realistic: they are ciphertext-only and need only the capability to eavesdrop on ESP-encrypted traffic and to inject traffic into the network. The paper also reports our experiences in applying the attacks to a variety of implementations of IPsec, and reflects on what these experiences tell us about how security standards should be written so as to simplify the task of software developers.

VEST is a set of four stream cipher families targeted to semiconductor applications. All VEST family members support efficient encryption, single pass authenticated encryption, and collision resistant hashing in the one low area module. VEST was submitted by Synaptic Laboratories to the ECRYPT NoE eSTREAM project in 2005. Recently, a single digit typographical error was identified in the VEST counter diffuser description. Shortly afterwards Antoine Joux and Jean-René Reinhard published collisions in the counter-diffuser based upon the erroneous description. By extending these collisions across the entire cipher state, they were able to explore various attack scenarios. We prove that the correction of the typographical error removes all the exploitable collisions in the counter diffuser during key and IV loading operations; thereby establishing that the Joux-Reinhard attacks are an artefact of the erroneous description. Complete test vectors are included.

LaMacchia, Lauter and Mityagin recently presented a strong security definition for authenticated key agreement strengthening the well-known Canetti-Krawczyk definition. They also described a protocol, called NAXOS, that enjoys a simple security proof in the new model. Compared to MQV and HMQV, NAXOS is less efficient and cannot be readily modified to obtain a one-pass protocol. On the other hand MQV does not have a security proof, and the HMQV security proof is extremely complicated. This paper proposes a new authenticated key agreement protocol, called CMQV (`Combined' MQV), which incorporates design principles from MQV, HMQV and NAXOS. The new protocol achieves the efficiency of HMQV and admits a natural one-pass variant. Moreover, we present a simple and intuitive proof that CMQV is secure in the LaMacchia-Lauter-Mityagin model.

In this paper we investigate the security properties of three versions of the WAI protocol in Chinese WLAN implementation plan. We first revisit the security analysis that has been done to the version 1 and 2. we show that the security proof given by Li, Moon, and Ma is incorrect and the alternative protocol EWAP of Zhang and Ma is insecure. We further analyse the third version of the WAI protocol and prove its security in the Canetti-Krawczyk model. In addition, we also provide some practical security analysis of this version.

This paper presents the first constructions for certificateless encryption (CLE) schemes that are provably secure against strong adversaries in the standard model. It includes both a generic construction for a strongly secure CLE scheme from any passively secure scheme as well as a concrete construction based on the Waters identity-based encryption scheme.

We demonstrate an active attack on the WEP protocol that is able to recover a 104-bit WEP key using less than 40.000 frames in 50% of all cases. The IV of these packets can be randomly chosen. This is an improvement in the number of required frames by more than an order of magnitude over the best known key-recovery attacks for WEP. On a IEEE 802.11g network, the number of frames required can be obtained by re-injection in less than a minute. The required computational effort is approximately 2^{20} RC4 key setups, which on current desktop and laptop CPUs is neglegible.

We give the first perfectly rerandomizable, Replayable-CCA (RCCA) secure encryption scheme, positively answering an open problem of Canetti et al. [CRYPTO 2003]. Our encryption scheme, which we call the Double-strand Cramer-Shoup scheme, is a non-trivial extension of the popular Cramer-Shoup encryption. Its security is based on the standard DDH assumption. To justify our definitions, we define a powerful "Replayable Message Posting" functionality in the Universally Composable (UC) framework, and show that any encryption scheme that satisfies our definitions of rerandomizability and RCCA security is a UC-secure implementation of this functionality. Finally, we enhance the notion of rerandomizable RCCA security by adding a receiver-anonymity (or key-privacy) requirement, and show that it results in a correspondingly enhanced UC functionality. We leave open the problem of constructing a scheme that achieves this enhancement.

We present a general framework for constructing two-message oblivious transfer protocols using a modification of Cramer and Shoup's notion of smooth projective hashing (2002). This framework is an abstraction of the two-message oblivious transfer protocols of Naor and Pinkas (2001) and Aiello et al. (2001), whose security is based on the Decisional Diffie Hellman Assumption. In particular, we give two new oblivious transfer protocols. The security of one is based on the Quadratic Residuosity Assumption, and the security of the other is based on the $N$'th Residuosity Assumption. Compared to other applications of smooth projective hashing, in our context we must deal also with maliciously chosen parameters, which raises new technical difficulties. We also improve on prior constructions of factoring-based smooth universal hashing, in that our constructions *do not require that the underlying RSA modulus is a product of safe primes*. (This holds for the schemes based on the Quadratic Residuosity Assumption as well as the ones based on the $N$'th Residuosity Assumption.) In fact, we observe that the safe-prime requirement is unnecessary for many prior constructions. In particular, the factoring-based CCA secure encryption schemes due to Cramer-Shoup, Gennaro-Lindell, and Camenisch-Shoup remain secure even if the underlying RSA modulus is not a product of safe primes.

The recent algebraic attacks have received a lot of attention in cryptographic literature. The algebraic immunity of a Boolean function quantifies its resistance to the standard algebraic attacks of the pseudo-random generators using it as a nonlinear filtering or combining function. Very few results have been found concerning its relation with the other cryptographic parameters or with the $r$-th order nonlinearity. As recalled by Carlet at Crypto'06, many papers have illustrated the importance of the $r$th-order nonlinearity profile (which includes the first-order nonlinearity). The role of this parameter relatively to the currently known attacks has been also shown for block ciphers. Recently, two lower bounds involving the algebraic immunity on the $r$th-order nonlinearity have been shown by Carlet et \emph{al}. None of them improves upon the other one in all situations. In this paper, we prove a new lower bound on the $r$th-order nonlinearity profile of Boolean functions, given their algebraic immunity, that improves significantly upon one of these lower bounds for all orders and upon the other one for low orders.

In this paper, we propose a zero-knowledge authenticated key agreement protocol with key confirmation (AKC) in asymmetric setting. The protocol has several desirable security attributes like some classical AKCs such as STS and MQV. One highlight of our protocol is its zero-knowledge property, which enables succinct proofs of the claimed security attributes, while the overhead in communication and computation resulting from the special design to achieve zero-knowledge is insignificant.

We introduce a new infinite family of multiterm functions that are APN on $GF(2^{2k})$ for odd $k$.

We introduce a new kind of word-oriented linear feedback shift register called $\sigma-$LFSR which is constructed with the instructions of the modern processor and have fast software implementation. We offer an algorithm to search for good primitive $\sigma-$LFSR. In particular, we give two examples HHZ-1 and HHZ-2 and compare their efficiency and security with those of the LFSRs appearing in stream ciphers such as SNOW, SOBER and Turing. Our results show that replacing the LFSRs in SNOW, SOBER and Turing with HHZ-1 will improve security and the efficiency of fast software implementation.

Deniability is defined as a privacy property which enables protocol principals to deny their involvement after they had taken part in a particular protocol run. Lately, Chou et al. had proposed their ID-based deniable authentication protocol after proving the vulnerability to Key-Compromise Impersonation (KCI) attack in Cao et al.'s protocol. In addition, they claimed that their protocol is not only secure, but also able to achieve both authenticity and deniability properties. However, in this paper, we demonstrate that Chou et al.'s protocol is not flawless as it remains insecure due to its susceptibility to the KCI attack. Based on this, we propose an enhanced scheme which will in fact preserves the authenticity, the deniability and the resistance against the KCI attack.

We study the solution of the discrete logarithm problem for the Jacobian of a curve of genus g defined over an extension field Fqn, by decomposed attack, considering a external elements B0 given by points of the curve whose x-coordinates are defined in Fq. In the decomposed attack, an element of the group which is written by a sum of some elements of external elements is called (potentially) decomposed and the set of the terms, that appear in the sum, is called decomposed factor. In order for the running of the decomposed attack, a test for the (potential) decomposeness and the computation of the decomposed factor are needed. Here, we show that the test to determine if an element of the Jacobian (i.e., reduced divisor) is written by an ng sum of the elements of the external elements and the computation of decomposed factor are reduced to the problem of solving some multivariable polynomial system of equations by using the Riemann-Roch theorem. In particular, in the case of a hyperelliptic curve, we construct a concrete system of equations, which satisfies these properties and consists of (n2¡n)g quadratic equations. Moreover, in the case of (g; n) = (1; 3); (2; 2) and (3; 2), we give examples of the concrete computation of the decomposed factors by using the computer algebra system Magma.

With the growing demand of databases outsourcing and its security concerns, we investigate privacy-preserving set intersection in a distributed scenario. We propose a one-round protocol for privacy-preserving set intersection based on a combination of secret sharing scheme and homomorphic encryption. We then show that, with an extra permutation performed by each of contacted servers, the cardinality of set intersection can be computed efficiently. All protocols constructed in this paper are provably secure against a semi-honest adversary under the Decisional Diffie-Hellman assumption.

We explain a method of finding the polynomials representing $\sqrt{-D}$ and $\zeta_k$ over the field containing $\sqrt{-D}$ and $\zeta_k$ and how to construct a pairing friendly elliptic curves over the cyclotomic fields containing ${\mathbb Q} (\zeta_k, \sqrt{-D})$ for arbitrary $k$ and $D$ by CP method. By using the factorization of the cyclotomic polynomial combined some polynomial, we extend the construction over cyclotomic fields to the construction over some extensions of the cyclotomic fields containing ${\mathbb Q} (\zeta_k, \sqrt{-D})$. We explain the limitation of finding more families of pairing friendly elliptic curves with embedding degree 10. For all computation, we use the PARI-GP \cite{GP}.

Given (deterministic) ciphers $\calE$ and~$E$ that can encipher messages of $\el$ and $n$ bits, respectively, we construct a cipher~$\calE^*=XLS[\calE,E]$ that can encipher messages of $\el+s$ bits for any $s<n$. Enciphering such a string will take one call to~$\calE$ and two calls to~$E$. We prove that~$\calE^*$ is a strong pseudorandom permutation as long as~$\calE$ and~$E$ are. Our construction works even in the tweakable and VIL (variable-input-length) settings. It makes use of a multipermutation (a pair of orthogonal Latin squares), a combinatorial object not previously used to get a provable-security result.

Dragon stream cipher is one of the focus ciphers which have reached Phase 2 of the eSTREAM project. In this paper, we present a new method of building a linear distinguisher for Dragon. The distinguisher is constructed by exploiting the biases of two S-boxes and the modular addition which are basic components of the nonlinear function $F$. The bias of the distinguisher is estimated to be around $2^{-75.32}$ which is better than the bias of the distinguisher presented by Englund and Maximov. We have shown that Dragon is distinguishable from a random cipher by using around $2^{150.6}$ keystream words and $2^{59}$ memory. In addition, we present a very efficient algorithm for computing the bias of linear approximation of modular addition.

The realization of the quantum computer will enable to break public-key cryptosystems based on factoring problem and discrete logarithm problem. It is considered that even the quantum computer can not solve NP-hard problem in a polynomial time. The subset sum problem is known to be NP-hard. Merkle and Hellman proposed a knapsack cryptosystem using the subset sum problem. However, it was broken by Shamir or Adleman because there exist the linearity of the modular transformation and the specialty in the secret keys. It is also broken with the low-density attack because the density is not sufficiently high. In this paper, we propose a new class of knapsack scheme without modular transformation. The specialty and the linearity can be avoidable by using the Chinese remainder theorem as the trapdoor. The proposed scheme has a high density and a large dimension to be sufficiently secure against a practical low-density attack.

Extensive studies have been made of the Secret Sharing Scheme(SSS). In this paper new classes of SSS, referred to as K-SSS, $\rm{K_I}$-SSS, $\rm{K_{I\hspace{-.1em}I}}$-SSS and $\tilde{{\rm K}}$-SSS are presented on the basis of recovering algorithm, K-RA. As an application, we shall also present a method for the recovering of secret informations learned only by heart, based on a particular class of K-SSS, $\rm{K_I}$-SSS.

We define a new notion of a reduced lattice, based on a quantity introduced in the LLL paper. We show that lattices reduced in this sense are simultaneously reduced in both their primal and dual. We show that the definition applies naturally to blocks, and therefore gives a new hierarchy of polynomial time algorithms for lattice reduction with fixed blocksize. We compare this hierarchy of algorithms to previous ones. We then explore algorithms to provably minimize the associated measure, and also some more efficient heuristics. Finally we comment on the initial investigations of applying our technique to the NTRU family of lattices.

At DRM 2002, Chow et al. presented a method for implementing the DES block cipher such that it becomes hard to extract the embedded secret key in a white-box attack context. In such a context, an attacker has full access to the implementation and its execution environment. In order to provide an extra level of security, an implementation shielded with external encodings was introduced by Chow et al. and improved by Link and Neumann. In this paper, we present an algorithm to extract the secret key from such white-box DES implementations. The cryptanalysis is a differential attack on obfuscated rounds, and works regardless of the shielding external encodings that are applied. The cryptanalysis has a average time complexity of $2^{14}$ and a negligible space complexity.

We discuss irreducible polynomials that can be used to speed up square root extraction in fields of characteristic two. We call such polynomials \textit{square root friendly}. The obvious applications are to point halving methods for elliptic curves and divisor halving methods for hyperelliptic curves. We note the existence of square root friendly trinomials of a given degree when we already know that an irreducible trinomial of the same degree exists, and formulate a conjecture on the degrees of the terms of square root friendly polynomials. We also give a partial result that goes in the direction of the conjecture. Irreducible polynomials $p(X)$ such that the square root $\zeta$ of a zero $x$ of $p(X)$ is a sparse polynomial are considered and those for which $\zeta$ has minimal degree are characterized. In doing this we discover a surprising connection these polynomials and those defining polynomial bases with an extremal number of trace one elements. We also show how to improve the speed of solving quadratic equations and that the increase in the time required to perform modular reduction is marginal and does not affect performance adversely. Experimental results confirm that the new polynomials mantain their promises; These results generalize work by Fong et al.\ to polynomials other than trinomials. Point halving gets a speed-up of $20\%$ and the performance of scalar multiplication based on point halving is improved by at least $11\%$.

In a series of papers, Küsters et al. investigated the relationships between various notions of simulation-based security. Two main factors, the placement of a ``master process'' and the existence of ``forwarder processes'', were found to affect the relationship between different definitions. In this extended abstract, we add a new dimension to the analysis of simulation-based security, namely, the scheduling of concurrent processes. We show that, when we move from sequential scheduling (as used in previous studies) to task-based nondeterministic scheduling, the same syntactic definition of security gives rise to incomparable semantic notions of security. Under task-based scheduling, the hierarchy based on placement of ``master process'' is no longer relevant, because no such designation is necessary to obtain meaningful runs of a system. On the other hand, the existence of ``forwarder processes'' remains an important factor.

This paper shows an attack against APOP protocol which is a challenge-and-response protocol. We utilize the Wang's attack to make collisions in MD5, and apply it to APOP protocol. We confirmed that the first 3 octets of secret key can be recovered by several hundred queries under the man-in-the-middle environment.

Identity-based encryption (IBE) schemes are usually used in multiple-PKG environments --- on the one hand, each administrative domain (e.g., a relatively small and close organization) maintains its own private key generator (PKG); on the other hand, encryption across domains becomes a prevalent requirement. In this paper, we present a new IBE scheme using bilinear pairings. Compared with the famous IBE scheme of Boneh and Franklin, we show that ours is more practical in the multiple-PKG environment. We prove that our scheme meets chosen ciphertext security in the random oracle model, assuming the intractability of the standard Bilinear Diffie-Hellman (BDH) problem. As an application of our IBE scheme, we also propose an escrowed ElGamal scheme which possesses certain good properties in practice.

Let $p$ be a prime and let $E(\F_p)$ be an elliptic curve defined over the finite field $\F_p$ of $p$ elements. For a given point $G \in E(\F_p)$ the linear congruential genarator on elliptic curves (EC-LCG) is a sequence $(U_n)$ of pseudorandom numbers defined by the relation $$ U_n=U_{n-1}\oplus G=nG\oplus U_0,\quad n=1,2,\ldots,$$ where $\oplus$ denote the group operation in $E(\F_p)$ and $U_0 \in E(\F_p)$ is the initial value or seed. We show that if $G$ and sufficiently many of the most significants bits of two consecutive values $U_n, U_{n+1}$ of the EC-LCG are given, one can recover the seed $U_0$ (even in the case where the elliptic curve is private) provided that the former value $U_n$ does not lie in a certain small subset of exceptional values. We also estimate limits of a heuristic approach for the case where $G$ is also unknown. This suggests that for cryptographic applications EC-LCG should be used with great care. Our results are somewhat similar to those known for the linear and non-linear pseudorandom number congruential generator.

A method for constructing differentially 4-uniform quadratic hexanomials has been recently introduced by J. Dillon. We give various generalizations of this method and we deduce the constructions of new infinite classes of almost perfect nonlinear quadratic trinomials and hexanomials from $\mathbb{F}_{2^{2m}}$ to $\mathbb{F}_{2^{2m}}$. We check for $m=3$ that some of these functions are CCZ-inequivalent to power functions.

In this paper we obtain conditions on the divisors of the group order of the Jacobian of a hyperelliptic genus 2 curve, generated by the complex multiplication method described by Weng (2003) and Gaudry (2005). Examples, where these conditions imply that the Jacobian has a large cyclic subgroup, are given.

We have discovered conjectural near-addition formulas for Somos sequences. We have preliminary evidence suggesting the existence of modular theta functions.

Despite the large number of certificateless encryption schemes recently proposed, many of them have been found to be insecure under a practical attack called \emph{malicious-but-passive} KGC attack, since they all follow the same key generation procedure as that of the one proposed by Al-Riyami and Paterson in ASIACRYPT 2003. The only provably secure certificateless encryption scheme against this attack is due to Libert and Quisquater (PKC 2006). However, the security can only be shown in the random oracle model. % In this paper, we first show that a scheme which has a different key generation procedure from that of Al-Riyami and Paterson also suffers from the malicious-but-passive KGC attack. Our attacking techniques are different from the previous attacks and may cause greater extent of damage than the previous ones. We also propose a generic construction of certificateless encryption which can be proven secure against this attack \emph{in the standard model}. This generic scheme is not only the first one proven secure in the standard model, but is also very efficient to instantiate. We also describe how to use short signature and hybrid encryption to construct highly efficient instantiations of this generic scheme.

We introduce the mesh signature primitive as an anonymous signature that borrows from ring signatures, but with added modularity and a much richer language for expressing signer ambiguity. The language can represent complex access structures, and in particular allows individual signature components to be replaced with modular certificate chains. As a result, withholding one's public key from view is no longer a shield against being named as a possible cosignatory; and hence, a mesh signature may be used as a ring signature substitute with compulsory enrollment. We give an efficient construction based on bilinear maps in the common random string model. Our mesh signatures have linear size, achieve everlasting perfect anonymity, and as a special case induce the most efficient and first unconditionally anonymous ring signatures without random oracles or trusted setup authorities. We prove non-repudiation from a mild extension of the SDH assumption, which we introduce and justify meticulously.

The number and diversity of electronic gadgets has been steadily increasing and they are becoming indispensable to more and more professionals and non-professionals alike. At the same time, there has been fairly little progress in secure pairing of such devices. The pairing challenge revolves around establishing on-the-fly secure communication without any trusted (on- or off-line) third parties between devices that have no prior association. The main security issue is the danger of so-called Man-in-the-Middle (MiTM) attacks, whereby an adversary impersonates one of the devices by inserting itself into the pairing protocol. One basic approach to countering these MiTM attacks is to involve the user in the pairing process. Therein lies the usability challenge since it is natural to minimize user burden. Previous research yielded some interesting secure pairing techniques, some of which ask too much of the human user, while others assume availability of specialized equipment (e.g., wires, photo or video cameras) on devices. Furthermore, all prior methods assumed the existence of a common digital (humanimperceptible) communication medium, such as Infrared, 802.11 or Bluetooth. In this paper we introduce a very simple technique called HAPADEP (Human-Assisted Pure Audio Device Pairing). It places very little burden on the human user and requires no common means of electronic communication. Instead, HAPADEP uses the audio channel to exchange both data and verification information among devices. It makes secure pairing possible even if devices are equipped only with a microphone and a speaker. Despite its simplicity, a number of interesting issues arise in the design of HAPADEP. We discuss design and implementation highlights as well as usability features and limitations.

In this paper we present that some statistical properties of points on elliptic curve can be used to form new equivalence classes. This can have an impact on solving discrete logarithm (ECDLP) owing to the reduction of the number of points among which a logarithm is searched to points of particular features. It should lead to an improvement of the Pollard-rho algorithm.

Since their introduction in constructive cryptographic applications, pairings over (hyper)elliptic curves are at the heart of an ever increasing number of protocols. Software implementations being rather slow, the study of hardware architectures became an active research area. In this paper, we first study an accelerator for the $\eta_T$ pairing over $\mathbb{F}_3[x]/(x^{97}+x^{12}+2)$. Our architecture is based on a unified arithmetic operator which performs addition, multiplication, and cubing over $\mathbb{F}_{3^{97}}$. This design methodology allows us to design a compact coprocessor ($1888$ slices on a Virtex-II Pro~$4$ FPGA) which compares favorably with other solutions described in the open literature. We then describe ways to extend our approach to any characteristic and any extension field.

This paper studies the security of a recently-proposed image encryption scheme based on chaos, and points out the following problems: 1) there exist a number of invalid keys and weak keys, and some keys are partially equivalent for the encryption/decryption processes; 2) given one chosen plain-image, a sub-key $K_{10}$ can be guessed with a smaller computational complexity than that of the simple brute-force attack; 3) given $O(10)$ (at most 128) chosen plain-images, a chosen-plaintext attack may be able to break the following part of the secret key: $(\{K_i\bmod 128\}_{i=4}^{10})$, which works very well when $K_{10}$ is not too large; 4) when $K_{10}$ is relatively small, a known-plaintext attack can be mounted with only one known plain-image to recover some visual information of other plain-images encrypted by the same key.

The black-box field (BBF) extraction problem is, for a given field $\F$, to determine a secret field element hidden in a black-box which allows to add and multiply values in $\F$ in the box and which reports only equalities of elements in the box. This problem is of cryptographic interest for two reasons. First, for $\F=\F_p$ it corresponds to the generic reduction of the discrete logarithm problem to the computational Diffie-Hellman problem in a group of prime order $p$. Second, an efficient solution to the BBF problem proves the inexistence of certain field-homomorphic encryption schemes whose realization is an interesting open problems in algebra-based cryptography. BBFs are also of independent interest in computational algebra. In the previous literature, BBFs had only been considered for the prime field case. In this paper we consider a generalization of the extraction problem to BBFs that are extension fields. More precisely we discuss the representation problem defined as follows: For given generators $g_1,\ldots,g_d$ algebraically generating a BBF and an additional element $x$, all hidden in a black-box, express $x$ algebraically in terms of $g_1,\ldots,g_d$. We give an efficient algorithm for this representation problem and related problems for fields with small characteristic (e.g. $\F=\F_{2^n}$ for some $n$). We also consider extension fields of large characteristic and show how to reduce the representation problem to the extraction problem for the underlying prime field. These results imply the inexistence of field-homomorphic (as opposed to only group-homomorphic, like RSA) one-way permutations for fields of small characteristic.

In this paper we present a new algorithm for finding small roots of a system of multivariate polynomials over the integers based on lattice reduction techniques. Our simpler heuristic method is inspired in algorithms for predicting pseudorandom numbers, and it can be considered as another variant of Coppersmith's method for finding small solutions of integer bivariate polynomials. We also apply the method to the well known problem of factoring an integer when we know the high-order bits of one of the factors.

Digital signature schemes based on public-key cryptosystems generally permit existential forgery, except the schemes are equipped with some message formatting mechanisms, such as using hash functions or padding redundancies. In 2004, Chang et al. proposed a new digital signature scheme, and claimed the scheme without using any hash function or padding any redundancy can resist forgery attacks. However, many attacks on Chang et al.'s scheme were presented. Kang et al. also gave an effective improvement to resist these forgery attacks. In this letter, we gave a further improvement to shorten the signed signature. Our improvement keeps the security of Kang et al.'s scheme and makes it more efficient in computation and communication.

We present two universally composable and practical protocols by which a dealer can, verifiably and non-interactively, secret-share an integer among a set of players. Moreover, at small extra cost and using a distributed verifier proof, it can be shown in zero-knowledge that three shared integers $a,b,c$ satisfy $ab =c$. This implies by known reductions non-interactive zero-knowledge proofs that a shared integer is in a given interval, or that one secret integer is larger than another. Such primitives are useful, e.g., for supplying inputs to a multiparty computation protocol, such as an auction or an election. The protocols use various set-up assumptions, but do not require the random oracle model.

In this paper, we present a new type of MultiCollision attack on the compression functions both of MD4 and 3-Pass HAVAL. For MD4, we utilize two feasible different collision differential paths to find a 4-collision with 2^{19} MD4 computations. For 3-Pass HAVAL, we present three near-collision differential paths to find a 8 NearCollision with 2^{9} HAVAL computations.

At Eurocrypt 2005, Boneh, Boyen and Goh presented a constant size ciphertext hierarchical identity based encryption (HIBE) protocol. Our main contribution is to present a variant of the BBG-HIBE. The new HIBE is proved to be secure (without any degradation) in an extension of the sID model (denoted the s$^+$-ID model) and the components of the identities are from $\bbbz_p$, where $p$ is a suitable large prime. The BBG-HIBE is proved to be secure in the selective-ID (sID) security model and the components of the identities are from $\bbbz_p^*$. In the s$^+$-ID model the adversary is allowed to vary the length of the challenge identity whereas this is not allowed in the sID model. The new HIBE shares all the good features of the BBG-HIBE. The drawback is that the public parameters and the private key are longer than that of the BBG-HIBE. We also provide two more extensions of the basic constant size ciphertext HIBE. The first is a constant size ciphertext HIBE secure in the generalised selective-ID model $\clsM_2$. The second one is a product construction composed of two HIBEs and a trade-off is possible between the private key size and the ciphertext size.

In this paper, we introduce the notion of a Public-Key Encryption Scheme that is also a Locally-Decodable Error-Correcting Code (PKLDC). In essence, this is a protocol that is semantically-secure in the standard sense, but possesses the additional property that it is a binary error-correcting locally-decodable code against any polynomial-time Adversary. That is, we allow a polynomial-time Adversary to read the entire ciphertext, perform any polynomial-time computation and change an arbitrary (i.e. adversarially chosen) constant fraction of {\em all} bits of the ciphertext. The goal of the Adversary is to cause error in decoding any bit of the plaintext. Nevertheless, the decoding algorithm can decode {\bf all} bits of the plaintext (given the corrupted ciphertext) while making a mistake on \emph{any} bit of the plaintext with only a negligible in $k$ error probability. In addition, the decoding algorithm has a {\bf Local Decodability} property. That is, given a corrupted ciphertext of $E(x)$ the decoding algorithm, for any $1 \le i \le n$, can recover the $i$'th bit of the plaintext $x$ with overwhelming probability reading a sublinear (in $|x|$) number of bits of the corrupted ciphertext and performing computation polynomial in the security parameter $k$. We present a general reduction from any semantically-secure encryption protocol and any computational Private Information Retrieval (PIR) protocol to a PKLDC. In particular, since it was shown that homomorphic encryption implies PIR, we give a general reduction from any semantically-secure homomorphic encryption protocol to a PKLDC. Applying our construction to the best known PIR protocol (that of Gentry and Ramzan), we obtain a PKLDC, which for messages of size $n$ and security parameter $k$ achieves ciphertexts of size $\O(n)$, public key of size $\O(n+k)$, and locality of size $\O(k^2)$. This means that for messages of length $n = \omega(k^{2+\epsilon})$, we can decode bit of the plaintext from a corrupted ciphertext while doing computation sublinear in $n$. We emphasize that this protocol achieves codewords that are only a \emph{constant} times larger than the underlying plaintext, while the best known locally-decodable codes (due to Yekhanin) have codewords that are only slightly subexponential in the length of the plaintext. In addition, we believe that the tools and techniques developed in this paper will be of independent interest in other settings as well.

Deniable authentication is a technique that allows one party to send messages to another while the latter can not prove to a third party the fact of communication. In this paper, we first formalize a natural notion of deniable security and naturally extend the basic authenticator theorem by Bellare et al. \cite{bck98} to the setting of deniable authentication. Of independent interest, this extension is achieved by defining a deniable MT-authenticator via a game. This game is essentially borrowed from the notion of universal composition \cite{can01} although we do not assume any result or background about it. Then we construct two deniable MT-authenticators: uncontrollable random oracle based and the PKI based, both of which are just 3-round protocols. The second construction assumes the receiver owns a secret key. Such a setup assumption is very popular in the real world. (Without this assumption), all the previous protocols do not have a widely satisfiable performance when applied in the Internet-like environment. Finally, as our application, we obtain key exchange protocols that is deniably secure in the real world.

A recent paper by Wang \emph{et al.} has revealed a vulnerability in the ECKE-1 key agreement protocol. In particular, contrary to the author's claims, protocol ECKE-1 is shown to be susceptible to a key-compromise impersonation attack. This attack was also independently pointed out by the author in another recent paper published in the EURASIP Journal on Embedded Systems. Here we present a revised version of the protocol, ECKE-1R, that is key-compromise impersonation resilient at the expense of a higher computational workload and communication complexity with respect to the original protocol ECKE-1.

If a signature scheme is secure in the sense that no forgery on any new message (i.e., a message that has never been signed) is available for any computation restricted adversary, it is said weakly unforgeable (wUF), in contrast to strongly unforgeable (sUF) meaning no new signature on any old message (i.e., a valid signature on the message is already known) is available to such adversaries. sUF signatures are generally considered advantageous over wUF ones because of preference for high level security. But the case may be different when they are employed to construct group signatures. wUF but not sUF signatures, called WoUF signatures in this paper, are investigated in this paper. It is found that by applying a generic construction to WoUF signatures with indirectly-signability and perfectly-unlinkability (also defined in this paper), we can regenerate many efficient group signatures in literature. We also propose improvements to the group signature schemes of CL04, NSN04, KY05, in line with our generic construction.

The hash function HAVAL is an Australian extension of well known Merkle-Damgård hash functions such as MD4 and MD5. It has three variants, $3$-, $4$- and $5$-pass HAVAL. On $3$-pass HAVAL, the best known attack finds a collision pair with $2^{7}$ computations of the compression function. To find $k$ collision pairs, it requires $2^{7}k$ computations. In this paper, we present a better collision attack on $3$-pass HAVAL, which can find $k$ collision pairs with only $2k+33$ computations. Further, our message differential is different from the previous ones. (It is important to find collisions for different message differentials.)

Secure function evaluation (SFE) allows a set of players to compute an arbitrary agreed function of their private inputs, even if an adversary may corrupt some of the players. Secure multi-party computation (MPC) is a generalization allowing to perform an arbitrary on-going (also called reactive or stateful) computation during which players can receive outputs and provide new inputs at intermediate stages. At Crypto~2006, Ishai \emph{et al.} considered mixed threshold adversaries that either passively corrupt some fixed number of players, or, alternatively, actively corrupt some (smaller) fixed number of players, and showed that for certain thresholds, cryptographic SFE is possible, whereas cryptographic MPC is not. However, this separation does not occur when one considers \emph{perfect} security. Actually, past work suggests that no such separation exists, as all known general protocols for perfectly secure SFE can also be used for MPC. Also, such a separation does not show up with \emph{general adversaries}, characterized by a collection of corruptible subsets of the players, when considering passive and active corruption. In this paper, we study the most general corruption model where the adversary is characterized by a collection of adversary classes, each specifying the subset of players that can be actively, passively, or fail-corrupted, respectively, and show that in this model, perfectly secure MPC separates from perfectly secure SFE. Furthermore, we derive the exact conditions on the adversary structure for the existence of perfectly secure SFE resp.~MPC, and provide efficient protocols for both cases.

It is proved that a bent function has zero second derivative with respect to $a$, $b$, $a \ne b$, if and only if it is affine on all the flats parallel to the two dimensional subspace $V = \langle a, b \rangle$.

It is known that perfectly secure ($1$-round, $n$-channel) message transmission (MT) schemes exist if and only if $n \geq 3t+1$, where $t$ is the number of channels that the adversary can corrupt. Then does there exist an {\it almost} secure MT scheme for $n=2t+1$ ? In this paper, we first sum up a number flaws of the previous {\it almost} secure MT scheme presented at Crypto 2004. (The authors already noted in thier presentation at Crypto'2004 that their scheme was flawed.) We next show an equivalence between almost secure MT schemes and secret sharing schemes with cheaters. By using our equivalence, we derive a lower bound on the communication complexity of almost secure MT schemes. Finally, we present a near optimum scheme which meets our bound approximately. This is the first construction of provably secure almost secure ($1$-round, $n$-channel) MT schemes for $n=2t+1$.

The stream ciphers Py, Py6 were designed by Biham and Seberry for the ECRYPT-eSTREAM project in 2005. However, due to several recent cryptanalytic attacks on them, a strengthened version Pypy was proposed to rule out those attacks. The ciphers have been promoted to the `Focus' ciphers of the Phase II of the eSTREAM project. The impressive speed of the ciphers make them the forerunners in the competition. Unfortunately, even the new cipher Pypy was found to retain weaknesses, forcing the designers to again go for modifications. As a result, three new ciphers TPypy, TPy and TPy6 were built. Among all the members of the Py-family of ciphers, the TPypy is conjectured to be the strongest. So far, there is no known attack on the TPypy. This paper shows that the security of TPypy does not grow exponentially with the key-size. The main achievement of the paper is the detection of input-output correlations of TPypy that allow us to build a distinguisher with $2^{281}$ randomly chosen key/IVs and as many outputwords (each key generating one outputword). The cipher TPypy was claimed by the designers to be secure with keysize up to 256 bytes, i.e., 2048 bits. Our results establish that the TPypy fails to provide adequate security if the keysize is longer than 35 bytes, i.e., 280 bits. Note that the distinguisher is built within the design specifications of the cipher. Because of remarkable similarities between the TPypy and the TPy, our attacks are shown to be effective for TPy also. The paper also points out how the other members of the Py-family (i.e., TPy6, Py6, Pypy and Py6) are also weak against the current and some existing attacks.

We describe a CCA-secure public-key encryption scheme, in the Cramer-Shoup paradigm, based on the Linear assumption of Boneh, Boyen, and Shacham. Through a comparison to the Kiltz tag-encryption scheme from TCC 2006, our scheme gives evidence that the Cramer-Shoup paradigm yields CCA encryption with shorter ciphertexts than the Canetti-Halevi-Katz paradigm. We present a generalization of the Linear assumption into a family of progressively weaker assumptions and show how to instantiate our Linear Cramer-Shoup encryption using the progressively weaker members of this family.

Consider the following problem: Alice wishes to maintain her email using a storage-provider Bob (such as a Yahoo! or hotmail e-mail account). This storage-provider should provide for Alice the ability to collect, retrieve, search and delete emails but, at the same time, should learn neither the content of messages sent from the senders to Alice (with Bob as an intermediary), nor the search criteria used by Alice. A trivial solution is that messages will be sent to Bob in encrypted form and Alice, whenever she wants to search for some message, will ask Bob to send her a copy of the entire database of encrypted emails. This however is highly inefficient. We will be interested in solutions that are communication-efficient and, at the same time, respect the privacy of Alice. In this paper, we show how to create a public-key encryption scheme for Alice that allows PIR searching over encrypted documents. Our solution provides a theoretical solution to an open problem posed by Boneh, DiCrescenzo, Ostrovsky and Persiano on ``Public-key Encryption with Keyword Search'', providing the first scheme that does not reveal any partial information regarding user's search (including the access pattern) in the public-key setting and with non-trivially small communication complexity. The main technique of our solution also allows for Single-Database PIR writing with sub-linear communication complexity, which we consider of independent interest.

In this paper, we investigate the application of concurrent error detection circuitry to a compact application-specific integrated circuit (ASIC) implementation of the Advanced Encryption Standard (AES). The specific objective of the design is to develop a method suitable for compact ASIC implementations targeted to embedded systems such that the system is resistant to fault attacks. To provide the error detection, recognizing that previously proposed schemes are not well suited to compact implementations, it is proposed to adopt a hybrid approach consisting of parity codes in combination with partial circuit redundancy. For compact ASIC implementations, taking such an approach gives a better ability to detect faults than simple parity codes, with less area cost than proposed schemes which use full hardware redundancy. The results of the implementation analysis in this paper show that it is possible to implement an error detection scheme that is robust to multiple faults in a compact AES design such that about 39% of the overall system is devoted to the error detection functionality.

We prove in a non-black-box way that every bounded list and set commitment scheme is knowledge-binding. This is a new and rather strong security condition, which makes the security definitions for time-stamping much more natural compared to the previous definitions, which assume unpredictability of adversaries. As a direct consequence, list and set commitment schemes with partial opening property are sufficient for secure time-stamping if the number of elements has an explicit upper bound N. On the other hand, white-box reductions are in a sense strictly weaker than black-box reductions. Therefore, we also extend and generalize the previously known reductions. The corresponding new reductions are Theta(sqrt(N)) times more efficient, which is important for global-scale time-stamping schemes where N is very large.

At FSE 2004 two new stream ciphers VMPC and RC4A have been proposed. VMPC is a generalisation of the stream cipher RC4, whereas RC4A is an attempt to increase the security of RC4 by introducing an additional permuter in the design. This paper is the first work presenting attacks on VMPC and RC4A. We propose two linear distinguishing attacks, one on VMPC of complexity $2^{39.97}$, and one on RC4A of complexity $2^{58}$. We investigate the RC4 family of stream ciphers and show some theoretical weaknesses of such constructions.

Since the introduction of nominative signature in 1996, there have been only a few schemes proposed and all of them have already been found flawed. In addition, there is no formal security model defined. Even more problematic, there is no convincing application proposed. Due to these problems, the research of nominative signature has almost stalled and it is unknown if a secure nominative signature scheme can be built or there exists an application for it. In this paper, we give positive answers to these problems. First, we illustrate that nominative signature is a better tool for building user certification systems which are originally believed to be best implemented using a universal designated-verifier signature. Second, we propose a formal definition and a rigorous set of adversarial models for nominative signature. Third, we show that Chaum's undeniable signature can be transformed efficiently to a nominative signature and prove its security.

The only known constructions of Hierarchical Identity Based Signatures that are proven secure in the strongest model without random oracles are based on the approach of attaching certificate chains or hierarchical authentication tree with one-time signature. Both construction methods lead to schemes that are somewhat inefficient and leave open the problem of efficient direct construction. In this paper, we propose the first direct construction of Hierarchical Identity Based Signature scheme that is proven under the strongest model without relying on random oracles and using more standard $q$-SDH assumption. It is computationally efficient and the signature size is constant. When the number of hierarchical level is set to be one, our scheme is a normal identity based signature scheme. It enjoys the shortest size in public parameters and signatures when compare with others in the literature, with the same security level.

withdrawn

The low-density attack proposed by Lagarias and Odlyzko is a powerful algorithm against the subset sum problem. The improvement algorithm due to Coster et al. would solve almost all the problems of density < 0.9408... in the asymptotical sense. On the other hand, the subset sum problem itself is known as an NP-hard problem, and a lot of efforts have been paid to establish public-key cryptosystems based on the problem. In these cryptosystems, densities of the subset sum problems should be higher than 0.9408... in order to avoid the low-density attack. For example, the Chor-Rivest cryptosystem adopted subset sum problems with relatively high densities. In this paper, we further improve the low-density attack by incorporating an idea that integral lattice points can be covered with polynomially many spheres of shorter radius and of lower dimension. As a result, the success probability of our attack can be higher than that of Coster et al.'s attack for fixed dimensions. The density bound is also improved for fixed dimensions. Moreover, we numerically show that our improved low-density attack makes the success probability higher in case of low Hamming weight solution, such as the Chor-Rivest cryptosystem, if we assume SVP oracle calls.

Suppose that we are given an ideal oblivious transfer protocol (OT). We wish to construct a larger OT by using the above OT as a blackbox. Then how many instances of the given ideal OT should be invoked ? For this problem, some lower bounds were derived using entropy. In this paper, we show more tight lower bounds by using combinatorial techniques. Roughly speaking, our lower bounds are two times larger than the previous bounds.

In cryptography, there has been tremendous success in building primitives out of homomorphic semantically-secure encryption schemes, using homomorphic properties in a black-box way. A few notable examples of such primitives include items like private information retrieval schemes and collision-resistant hash functions. In this paper, we illustrate a general methodology for determining what types of protocols can be implemented in this way and which cannot. This is accomplished by analyzing the computational power of various algebraic structures which are preserved by existing cryptosystems. More precisely, we demonstrate lower bounds for algebraically generating generalized characteristic vectors over certain algebraic structures, and subsequently we show how to directly apply this abstract algebraic results to put lower bounds on algebraic constructions of a number of cryptographic protocols, including PIR-writing and private keyword search protocols. We hope that this work will provide a simple ``litmus test'' of feasibility for use by other cryptographic researchers attempting to develop new protocols that require computation on encrypted data. Additionally, a precise mathematical language for reasoning about such problems is developed in this work, which may be of independent interest.