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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Standards bodies have been addressing the key-wrap problem, a cryptographic goal that has never received a provable-security treatment. In response, we provide one, giving definitions, constructions, and proofs. We suggest that key-wrap’s goal is security in the sense of deterministic authenticated-encryption (DAE), a notion that we put forward. We also provide an alternative notion, a pseudorandom injection (PRI), which we prove to be equivalent. We provide a DAE construction, SIV, analyze its concrete security, develop a blockcipher-based instantiation of it, and suggest that the method makes a desirable alternative to the schemes of the X9.102 draft standard. The construction incorporates a method to turn a PRF that operates on a string into an equally efficient PRF that operates on a vector of strings, a problem of independent interest. Finally, we consider IV-based authenticated- encryption (AE) schemes that are maximally forgiving of repeated IVs, a goal we formalize as misuse-resistant AE.We show that a DAE scheme with a vector-valued header, such as SIV, directly realizes this goal.

Montgomery's ladder algorithm for elliptic curve scalar multiplication uses only the x-coordinates of points. Avoiding calculation of the y-coordinates saves time for certain curves. Montgomery introduced his method to accelerate Lenstra's elliptic curve method for integer factoring. Bernstein extended Montgomery's ladder algorithm by computing integer combinations of two points, thus accelerating signature verification over certain curves. This paper modifies and extends Bernstein's algorithm to integer combinations of two or more points.

We present a computational analysis of basic Kerberos with and without its public-key extension PKINIT in which we consider authentication and key secrecy properties. Our proofs rely on the Dolev--Yao-style model of Backes, Pfitzmann, and Waidner, which allows for mapping results obtained symbolically within this model to cryptographically sound proofs if certain assumptions are met. This work was the first verification at the computational level of such a complex fragment of an industrial protocol. By considering a recently fixed version of PKINIT, we extend symbolic correctness results we previously attained in the Dolev--Yao model to cryptographically sound results in the computational model.

The standard symbolic, deducibility-based notions of secrecy are in general insufficient from a cryptographic point of view, especially in presence of hash functions. In this paper we devise and motivate a more appropriate secrecy criterion which exactly captures a standard cryptographic notion of secrecy for protocols involving public-key enryption and hash functions: protocols that satisfy it are computationally secure while any violation of our criterion directly leads to an attack. Furthermore, we prove that our criterion is decidable via an NP decision procedure. Our results hold for standard security notions for encryption and hash functions modeled as random oracles.

The work contains a statistical investigation of the MARS block cipher --- one of the AES finalists. It is shown that 8 MARS round ciphertext can be recognized from a uniform distribution with the help of the ``Book Stack"\, test providing that $2^{18}$ blocks of plaintexts and $2^{20}$ bytes of memory are avaliable. The previous published attacks on this cipher were only theoretical with unrealistic resource requirements.

In this paper, we propose a new fast and secure point multiplication algorithm. It is based on a particular kind of addition chains involving only additions (no doubling), providing a natural protection against side channel attacks. Moreover, we propose new addition formulae that take into account the specific structure of those chains making point multiplication very efficient.

Recently, a novel image scrambling (i.e., encryption) scheme without bandwidth expansion was proposed based on two-dimensional (2-D)discrete prolate spheroidal sequences (DPSS). This paper gives a comprehensive cryptanalysis of the image scrambling scheme, and draw a conclusion that it is not sufficiently secure against various cryptographical attacks, including ciphertext-only attack, known/chosen-plaintext attack and chosen-ciphertext attack. The cryptanalytic results suggest that the image scrambling scheme can only be used to realize perceptual encryption, instead of provide content protection for digital images.

Password-authenticated key exchange (PAKE) protocols allow users sharing a password to agree upon a high entropy secret. In this paper, a provably secure password-authenticated pro- tocol for group key establishment in the common reference string (CRS) model is presented. Our protocol is quite efficient, as regardless of the number of involved participants it can be imple- mented with only three communication rounds. We use a (by now classical) trick of Burmester and Desmedt for deriving group key exchange protocols using a two-party construction as main building block. In our case, the two party PAKE used as a base is a one-round protocol by Katz and Vaikuntanatan, which in turn builds upon a special kind of smooth projective hash functions (KV-SPHFs). As evidenced by Benhamouda et al., KV-SPHFs can be instantiated on Cramer-Shoup ciphertexts, thus yielding very efficient (and pairing free) constructions.

The Feistel-network is a popular structure underlying many block-ciphers where the cipher is constructed from many simpler rounds, each defined by some function which is derived from the secret key. Luby and Rackoff showed that the three-round Feistel-network -- each round instantiated with a pseudorandom function secure against adaptive chosen plaintext attacks (CPA) -- is a CPA secure pseudorandom permutation, thus giving some confidence in the soundness of using a Feistel-network to design block-ciphers. But the round functions used in actual block-ciphers are -- for efficiency reasons -- far from being pseudorandom. We investigate the security of the Feistel-network against CPA distinguishers when the only security guarantee we have for the round functions is that they are secure against non-adaptive chosen plaintext attacks (NCPA). We show that in the information-theoretic setting, four rounds with NCPA secure round functions are sufficient (and necessary) to get a CPA secure permutation. Unfortunately, this result does not translate into the more interesting pseudorandom setting. In fact, under the so-called Inverse Decisional Diffie-Hellman assumption the Feistel-network with four rounds, each instantiated with a NCPA secure pseudorandom function, is in general not a CPA secure pseudorandom permutation. We also consider other relaxations of the Luby-Rackoff construction and prove their (in)security against different classes of attacks.

Common occurrence of server overload and the threat of denial-of-service (DoS) attacks makes highly desirable to improve the performance and DoS resistance of SSL handshakes. In this paper, we tackle these two related problems by proposing reverse SSL, an extension in which the server is relieved from the heavy public key decryption operation and authenticated by means of a digital signature instead. On the server side, reverse SSL employs online/offline signatures to minimize the online computation required to generate the signature and on the client side, RSA key generation computation can be used as a client puzzle when clients do not have a public key certificate. The preliminary performance results show that reverse SSL is a promising technique for improving the performance and DoS resistance of SSL servers.

This paper surveys the literature on certificateless encryption schemes. In particular, we examine the (large number of) security models that have been proposed to prove the security of certificateless encryption schemes and propose a new nomenclature for these models. This allows us to "rank" the notions of security for a certificateless encryption scheme against an outside attacker and a passive key generation centre, and we suggest which of these notions should be regarded as the "correct" model for a secure certificateless encryption scheme. We also examine the security models that aim to provide security against an actively malicious key generation centre and against an outside attacker who attempts to deceive a legitimate sender into using an incorrect public key (with the intention to deny the the legitimate receiver that ability to decrypt the ciphertext). We note that the existing malicious key generation centre model fails to capture realistic attacks that a malicious key generation centre might make and propose a new model. Lastly, we survey the existing certificateless encryption schemes and compare their security proofs. We show that few schemes provide the correct notion of security without appealing to the random oracle model. The few schemes that do provide sufficient security guarantees are comparatively inefficient. Hence, we conclude that more research is needed before certificateless encryption schemes can be thought to be a practical technology.

Searchable symmetric encryption (SSE) allows a party to outsource the storage of his data to another party in a private manner, while maintaining the ability to selectively search over it. This problem has been the focus of active research and several security definitions and constructions have been proposed. In this paper we begin by reviewing existing notions of security and propose new and stronger security definitions. We then present two constructions that we show secure under our new definitions. Interestingly, in addition to satisfying stronger security guarantees, our constructions are more efficient than all previous constructions. Further, prior work on SSE only considered the setting where only the owner of the data is capable of submitting search queries. We consider the natural extension where an arbitrary group of parties other than the owner can submit search queries. We formally define SSE in this multi-user setting, and present an efficient construction.

Redundant number systems (e.g. signed binary representations) have been utilized to efficiently implement algebraic operations required by public-key cryptosystems, especially those based on elliptic curves. Several families of integer representations have been proposed that have a minimal number of nonzero digits (so-called \emph{minimal weight} representations). We observe that many of the constructions for minimal weight representations actually work by building representations which are minimal in another sense. For a given set of digits, these constructions build \emph{colexicographically minimal} representations; that is, they build representations where each nonzero digit is positioned as far left (toward the most significant digit) as possible. We utilize this strategy in a new algorithm which constructs a very general family of minimal weight dimension-$d$ \emph{joint} representations for any $d \geq 1$. The digits we use are from the set $\{a \in \ZZ: \ell \leq a \leq u\}$ where $\ell \leq 0$ and $u \geq 1$ are integers. By selecting particular values of $\ell$ and $u$, it is easily seen that our algorithm generalizes many of the minimal weight representations previously described in the literature. From our algorithm, we obtain a syntactical description of a particular family of dimension-$d$ joint representations; any representation which obeys this syntax must be both colexicographically minimal and have minimal weight; moreover, every vector of integers has exactly one representation that satisfies this syntax. We utilize this syntax in a combinatorial analysis of the weight of the representations.

Many theoretical PIR (Private Information Retrieval) constructions have been proposed in the past years. Though information theoretically secure, most of them are impractical to deploy due to the prohibitively high communication and computation complexity. The recent trend in outsourcing databases fuels the research on practical PIR schemes. In this paper, we propose a new PIR system by making use of trusted hardware. Our system is proven to be information theoretically secure. Furthermore, we derive the computation complexity lower bound for hardware-based PIR schemes and show that our construction meets the lower bounds for both the communication and computation costs, respectively.

At CRYPTO 2004, Kurosawa and Desmedt presented a hybrid public-key encryption scheme that is chosen-ciphertext secure in the standard model. Until now it was unknown if the key-encapsulation part of the Kurosawa-Desmedt scheme by itself is still chosen-ciphertext secure or not. In this short note we answer this question to the negative, namely we present a simple chosen-ciphertext attack on the Kurosawa-Desmedt key encapsulation mechanism.

Pseudorandom Generators (PRGs) based on the RSA inversion (one-wayness) problem have been extensively studied in the literature over the last 25 years. These generators have the attractive feature of provable pseudorandomness security assuming the hardness of the RSA inversion problem. However, despite extensive study, the most efficient provably secure RSA-based generators output asymptotically only at most $O(\log n)$ bits per multiply modulo an RSA modulus of bitlength $n$, and hence are too slow to be used in many practical applications. To bring theory closer to practice, we present a simple modification to the proof of security by Fischlin and Schnorr of an RSA-based PRG, which shows that one can obtain an RSA-based PRG which outputs $\Omega(n)$ bits per multiply and has provable pseudorandomness security assuming the hardness of a well-studied variant of the RSA inversion problem, where a constant fraction of the plaintext bits are given. Our result gives a positive answer to an open question posed by Gennaro (J. of Cryptology, 2005) regarding finding a PRG beating the rate $O(\log n)$ bits per multiply at the cost of a reasonable assumption on RSA inversion.

The only known construction of ID-based ring signature schemes which maybe secure in the standard model is to attach certificates to non-ID-based ring signatures. This method leads to schemes that are somewhat inefficient and it is an open problem to find more efficient and direct constructions. In this paper, we propose two such constructions. Our first scheme, with signature size linear in the cardinality of the ring, is secure in the standard model under the computational Diffie-Hellman assumption. The second scheme, achieving constant signature size, is secure in a weaker attack model (the selective ID and weak chosen message model), under the Diffie-Hellman Inversion assumption.

Elliptic (ECC) and hyperelliptic curve cryptosystems (HECC) have emerged as cryptosystems of choice for small handheld and mobile devices. A lot of research has been devoted to the secure and efficient implementation on these devices. As such devices come with very low amount of resources, efficient memory management is an important issue in all such implementations. HECC arithmetic is now generally performed using so called explicit formulae. In literature, there is no result which focuses on the exact memory requirement for implementation these formulae. This is the first work to report such minimal memory requirement. Also, in the work we have provided a general methodology for realization of explicit formulae with minimal number of registers. Applying such methodology this work settles the issue for some important explicit formula available in the literature. This is an attempt to experimentally solve a particular instance based on HECC explicit formulae of the so called ``Register Sufficiency Problem", which is an NP-complete problem.

We generalize the selective-ID security model for HIBE by introducing two new security models. Broadly speaking, both these models allow the adversary to commit to a set of identities and in the challenge phase choose any one of the previously committed identities. Two constructions of HIBE are presented which are secure in the two models. Further, we show that the HIBEs can be modified to obtain a multiple receiver IBE which is secure in the selective-ID model without the random oracle assumption.

Recently, the authors proposed a method for computing the Tate pairing using a distortion map for $y^{2}=x^{5} -\alpha x$ ($\alpha = \pm2$) over finite fields of characteristic five. In this paper, we show the Ate pairing, an invariant of the Tate pairing, can be applied to this curve. This leads to about $50\%$ computational cost-saving over the Tate pairing.

Pairing-based cryptosystems have been developing very fast in the last few years. The efficiencies of the cryptosystems are determined by the computation of the Tate pairing. In this paper a new efficient algorithm based on double-base chain for computing the Tate pairing is proposed for odd characteristic $p>3$. The inherent sparseness of double-base number system reduces the computational cost for computing the Tate pairing evidently. It is $9\%$ faster than the previous fastest method for MOV degree k=6.

Abstract. Recently Manik et al. [13] proposed a novel remote user authentication scheme using bilinear pairings. Chou et al. [14] identified a weakness in Manik et al.’s scheme and made an improvement. Thulasi et al. [15] show that both Manik et al.’s and Chou et al.’s schemes are insecure against forgery attack and replay attack. But Thulasi et al. do not propose a improvement. In this paper, we propose an improvement to over come the flaws.

In recent years, a large number of identity-based key agreement protocols from pairings have been proposed. Some of them are elegant and practical. However, the security of this type of protocols has been surprisingly hard to prove. The main issue is that a simulator is not able to deal with reveal queries, because it requires solving either a computational problem or a decisional problem, both of which are generally believed to be hard (i.e., computationally infeasible). The best solution of security proof published so far uses the gap assumption, which means assuming that the existence of a decisional oracle does not change the hardness of the corresponding computational problem. The disadvantage of using this solution to prove the security for this type of protocols is that such decisional oracles, on which the security proof relies, cannot be performed by any polynomial time algorithm in the real world, because of the hardness of the decisional problem. In this paper we present a method incorporating a built-in decisional function in this type of protocols. The function transfers a hard decisional problem in the proof to an easy decisional problem. We then discuss the resulting efficiency of the schemes and the relevant security reductions in the context of different pairings one can use. We pay particular attention, unlike most other papers in the area, to the issues which arise when using asymmetric pairings.

We study the problem of private classification using kernel methods. More specifically, we propose private protocols implementing the Kernel Adatron and Kernel Perceptron learning algorithms, give private classification protocols and private polynomial kernel computation protocols. The new protocols return their outputs---either the kernel value, the classifier or the classifications---in encrypted form so that they can be decrypted only by a common agreement by the protocol participants. We also show how to use the encrypted classifications to privately estimate many properties of the data and the classifier. The new SVM classifiers are the first to be proven private according to the standard cryptographic definitions.

A novel algorithm for solving the LPN problem is proposed and analyzed. The algorithm originates from the recently proposed advanced fast correlation attacks, and it employs the concepts of decimation, linear combining, hypothesizing and minimum distance decoding. The proposed algorithm appears as more powerful than the best one previously reported known as the BKW algorithm. In fact the BKW algorithm is shown to be a special instance of the proposed algorithm, but without optimized parameters. An improved security evaluation of the HB protocol for RFID authentication is then developed. Employing the proposed algorithm, the security of the HB protocol is reevaluated, implying that the previously reported security margins appear as overestimated.

The algorithms submitted to the ECRYPT Stream Cipher Project (eSTREAM) were tested using the recently suggested statistical test named ``Book Stack''. All the ciphers except ZK-Crypt have passed the tests. The paper briefly describes the essence of the test. Computer implementation of the test in C++ language is supplied.

Signature schemes with message recovery have been wildly investigated a decade ago in the literature, but the first ID-based signature with message recovery goes out into the world until 2005. In this paper, we first point out and revise one little but important problem which occurs in the previous ID-based signature with message recovery scheme. Then, by completely different setting, we propose a new ID-based signature scheme with message recovery. Our scheme is much more efficient than the previous scheme. In our scheme (as well as other signature schemes with message recovery), the message itself is not required to be transmitted together with the signature, it turns out to have the least data size of communication cost comparing with generic (not short) signature schemes. Although the communication overhead is still larger than Boneh et al. 's short signature (which is not ID-based), the computational cost of our scheme is more efficient than Boneh et al. 's scheme in the verification phase. We will also prove that the proposed scheme is provably secure in the random oracle model under CDH Assumption.

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

We construct the first several efficient threshold ring signatures (TRS) without random oracles. Specializing to a threshold of one, they are the first several efficient ring signatures without random oracles after the only earlier instantiation of Chow, Liu, Wei, and Yuen. Further specializing to a ring of just one user, they are the short (ordinary) signatures without random oracles summarized in Wei and Yuen. We also construct the first hierarchical identity-based threshold ring signature without random oracles. The signature size is $O(n\lambda_s)$ bits, where $\lambda_s$ is the security parameter and $n$ is the number of users in the ring. Specializing to a threshold of one, it is the first hierarchical identity-based ring signature without random oracles. Further specializing to a ring of one user, it is the constant-size hierarchical identity-based signature (HIBS) without random oracles in Yuen-Wei - the signature size is $O(\lambda_s)$ bits which is independent of the number of levels in the hierarchy.

Abstract: This paper describes the influences of the threshold voltage VT on the leakage behavior of the dice after a fabrication process. By measuring the current consumption (leakage) on a CMOS cryptographic device like smartcard security controller and using the DPA analysis it is possible to make the key visible which is used during a cryptographic operation. Therefore, in this paper not only the security risks by using the smartcard security controller will be shown where no DPA attacks have been performed. Furthermore, it will be shown that the results of DPA analysis only on a coincidentally selected die cannot be representative for the whole production. Rather the DPA analysis must be performed on a particularly selected die with the smallest VT parameter (worst case in the leakage behavior), so that the result for all other dice on the wafer (or for the whole production) can be considered as relevant. Thus, it will be shown that the test labs must use different methods regarding the DPA analysis in order to be able to cover the leakage behavior on all wafers of a production. For further re-evaluation of smartcards it is important that the manufacturer and the test labs can save time and costs by DPA measuring on the special selected worst case die.

RSA type public key cryptosystems based on the Pell's equation are proposed in the honor of an Indian mathematician Brahmgupta who studied Pell's equation long before European mathematicians came to know about it. Three RSA type schemes are proposed, first two are not semantically secure where as the other two schemes are semantically secure. The decryption speed of the proposed schemes is about two times as fast as RSA for a 2 log n-bit message. It is shown that the proposed schemes are more secure than the RSA scheme when purely common plaintexts are encrypted in the broadcast application and are as secure as the RSA scheme against ciphertext attack. In addition the proposed schemes are also secure against partially known plaintext attack. First two are not semantically secure but the third one is semantically secure.

The Dual Elliptic Curve Pseudorandom Generator (DEC PRG) is proposed by Barker and Kelsey in a draft NIST Special Publication. It is claimed that the pseudorandom generator is secure unless the adversary can solve the elliptic curve discrete logarithm problem (ECDLP) for the corresponding elliptic curve. The claim is supported only by an informal discussion. No security reduction is given, that is, it is not shown that an adversary that breaks the pseudorandom generator implies a solver for the ECDLP. Our experimental results and also empirical argument show that the DEC PRG is insecure. The attack does not imply solving the ECDLP for the corresponding elliptic curve. The attack is very efficient.

Rivest proposed the idea of a chaffing-and-winnowing scheme, in which confidentiality is achieved through the use of an authentication code. Thus it would still be possible to have confidential communications even if conventional encryption schemes were outlawed. Hanaoka et al. constructed unconditionally secure chaffing-and-winnowing schemes which achieve perfect secrecy in the sense of Shannon. Their schemes are constructed from unconditionally secure authentication codes. In this paper, we construct unconditionally secure chaffing-and-winnowing schemes from unconditionally secure authentication codes in which the authentication tags are very short. This could be a desirable feature, because certain types of unconditionally secure authentication codes can provide perfect secrecy if the length of an authentication tag is at least as long as the length of the plaintext. The use of such a code might be prohibited if encryption schemes are made illegal, so it is of interest to construct chaffing-and-winnowing schemes based on "short'' authentication tags.

In this paper, we define and analyze a new blockcipher mode of operation for encryption, CENC, which stands for Cipher-based ENCryption. CENC has the following advantages: (1) beyond the birthday bound security, (2) security proofs with the standard PRP assumption, (3) highly efficient, (4) single blockcipher key, (5) fully parallelizable, (6) allows precomputation of keystream, and (7) allows random access. CENC is based on the new construction of ``from PRPs to PRF conversion,'' which is of independent interest. Based on CENC and a universal hash-based MAC (Wegman-Carter MAC), we also define a new authenticated-encryption with associated-data scheme, CHM, which stands for CENC with Hash-based MAC. The security of CHM is also beyond the birthday bound.

HMAC is a widely used message authentication code and a pseudorandom function generator based on cryptographic hash functions such as MD5 and SHA-1. It has been standardized by ANSI, IETF, ISO and NIST. HMAC is proved to be secure as long as the compression function of the underlying hash function is a pseudorandom function. In this paper we devise two new distinguishers of the structure of HMAC, called {\em differential} and {\em rectangle distinguishers}, and use them to discuss the security of HMAC based on HAVAL, MD4, MD5, SHA-0 and SHA-1. We show how to distinguish HMAC with reduced or full versions of these cryptographic hash functions from a random function or from HMAC with a random function. We also show how to use our differential distinguisher to devise a forgery attack on HMAC. Our distinguishing and forgery attacks can also be mounted on NMAC based on HAVAL, MD4, MD5, SHA-0 and SHA-1. Furthermore, we show that our differential and rectangle distinguishers can lead to second-preimage attacks on HMAC and NMAC.

We present as-strong-as-possible definitions of privacy, and constructions achieving them, for public-key encryption schemes where the encryption algorithm is \textit{deterministic}. We obtain as a consequence database encryption methods that permit fast (i.e.~sub-linear, and in fact logarithmic, time) search while provably providing privacy that is as strong as possible subject to this fast search constraint. One of our constructs, called RSA-DOAEP, has the added feature of being length preserving, so that it is the first example of a public-key cipher. We generalize this to obtain a notion of efficiently-searchable encryption schemes which permit more flexible privacy to search-time trade-offs via a technique called bucketization. Our results answer much-asked questions in the database community and provide foundations for work done there.

We show that every language in NP has a *statistical* zero-knowledge argument system under the (minimal) complexity assumption that one-way functions exist. In such protocols, even a computationally unbounded verifier cannot learn anything other than the fact that the assertion being proven is true, whereas a polynomial-time prover cannot convince the verifier to accept a false assertion except with negligible probability. This resolves an open question posed by Naor, Ostrovsky, Venkatesan, and Yung (CRYPTO `92, J. Cryptology `98). Departing from previous works on this problem, we do not construct standard statistically hiding commitments from any one-way function. Instead, we construct a relaxed variant of commitment schemes called "1-out-of-2-binding commitments," recently introduced by Nguyen and Vadhan (STOC `06).

In a traditional signature scheme, a signature $\sigma$ on a message $m$ is issued under a public key $\pk$, and can be interpreted as follows: "The owner of the public key $\pk$ and its corresponding secret key has signed message $m$." In this paper we consider schemes that allow one to issue signatures on behalf of any NP statement, that can be interpreted as follows: "A person in possession of a witness $w$ to the statement that $x \in L$ has signed message $m$." We refer to such schemes as \emph{signatures of knowledge}. We formally define the notion of a signature of knowledge. We begin by extending the traditional definition of digital signature schemes, captured by Canetti's ideal signing functionality, to the case of signatures of knowledge. We then give an alternative definition in terms of games that also seems to capture the necessary properties one may expect from a signature of knowledge. We then gain additional confidence in our two definitions by proving them equivalent. We construct signatures of knowledge under standard complexity assumptions in the common-random-string model. We then extend our definition to allow signatures of knowledge to be \emph{nested} i.e., a signature of knowledge (or another accepting input to a UC-realizable ideal functionality) can itself serve as a witness for another signature of knowledge. Thus, as a corollary, we obtain the first \emph{delegatable} anonymous credential system, i.e., a system in which one can use one's anonymous credentials as a secret key for issuing anonymous credentials to others.

The standard security definition of unconditional secure function evaluation, which is based on the ideal/real model paradigm, has the disadvantage of being overly complicated to work with in practice. On the other hand, simpler ad-hoc definitions tailored to special scenarios have often been flawed. Motivated by this unsatisfactory situation, we give an information-theoretic security definition of secure function evaluation which is very simple yet provably equivalent to the standard, simulation-based definitions.

We study the problem of circuit obfuscation, ie, transforming the circuit in a way that hides everything except its input-output behavior. Barak et al. showed that a universal obfuscator that obfuscates every circuit class cannot exist, leaving open the possibility of special-purpose obfuscators. Known positive results for obfuscation are limited to point functions (boolean functions that return 1 on exactly one input) and simple extensions thereof in the random oracle model, ie, assuming black-box access to a true random function. It was also shown by Wee how to instantiate random oracles so as to achieve a slightly weaker form of point function obfuscation. Two natural questions arise: (i) what circuits have obfuscators whose security can be reduced in a black-box way to point function obfuscation? and (ii) for what circuits obfuscatable in the random oracle model can we instantiate the random oracles to build obfuscators in the plain model? We give partial answers to these questions: there is a circuit in AC^0 which can be obfuscated in the random oracle model, but not secure when random oracles are instantiated with Wee's construction. More generally, we present evidence for the impossibility of a black-box reduction of the obfuscatability of this circuit to point function obfuscation. Conversely, this result shows that to instantiate random oracles in general obfuscators, one needs to utilize properties of the instantiation that are not satisfied by point function obfuscators.

For the first time we find Boolean functions on 9 variables having nonlinearity 241, that remained as an open question in literature for almost three decades. Such functions are discovered using a suitably modified steepest-descent based iterative heuristic search in the class of rotation symmetric Boolean functions (RSBFs). This shows that there exist Boolean functions on $n$ (odd) variables having nonlinearity $> 2^{n-1} - 2^{\frac{n-1}{2}}$ if and only if $n > 7$. Using the same search method, we also find several other important functions and we study the autocorrelation, propagation characteristics and resiliency of the RSBFs (using proper affine transformations, if required). The results show that it is possible to get balanced Boolean functions on $n=10$ variables having autocorrelation spectra with maximum absolute value $< 2^{\frac{n}{2}}$, which was not known earlier. In certain cases the functions can be affinely transformed to get first order propagation characteristics. We also obtain 10-variable functions having first order resiliency and nonlinearity 492 which was posed as an open question in Crypto 2000.

In this paper we consider the notions of the Hamming weight and the algebraic normal form. We solve an open problem devoted to checking divisibility of the weight by $2^k$. We generalize the criterion for checking the evenness of the weight in two ways. Our main result states that for checking whether the Hamming weight of $f$ is divisible by $2^k, \,k>1$, it is necessary and sufficient to know its algebraic normal form accurate to an additive constant.

Though the implementation of the Tate pairing is commonly believed to be computationally more intensive than other cryptographic operations, such as ECC point multiplication, there has been a substantial progress in speeding up the Tate pairing computations. Because of their inherent parallelism, the existing Tate pairing algorithms are very suitable for hardware implementation aimed at achieving a high operation speed. Supersingular elliptic curves over binary fields are good candidates for hardware implementation due to their simple underlying algorithms and binary arithmetic. In this paper we propose efficient Tate pairing implementations over binary fields $\mathbb F_{2^{239}}$ and $\mathbb F_{2^{283}}$ via FPGA. Though our field sizes are larger than those used in earlier architectures with the same security strength based on cubic elliptic curves or binary hyperelliptic curves, fewer multiplications in the underlying field are required, so that the computational latency for one pairing can be reduced. As a result, our pairing accelerators implemented via FPGA can run 15-to-25 times faster than other FPGA realizations at the same level of security strength, and at the same time achieve lower product of latency by area.

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

We consider the cryptographic two-party protocol task of extending a given coin toss. The goal is to generate n common random coins from a single use of an ideal functionality which gives m<n common random coins to the parties. In the framework of Universal Composability we show the impossibility of securely extending a coin toss for statistical and perfect security. On the other hand, for computational security the existence of a protocol for coin toss extension depends on the number m of random coins which can be obtained "for free". For the case of stand-alone security, i.e., a simulation based security definition without an environment, we present a novel protocol for unconditionally secure coin toss extension. The new protocol works for superlogarithmic m, which is optimal as we show the impossibility of statistically secure coin toss extension for smaller m. Combining our results with already known results, we obtain a (nearly) complete characterization under which circumstances coin toss extension is possible.

In this paper, we revisit the problem of computing the kernel of a separable isogeny of degree $\ell$ between two elliptic curves defined over a finite field $\GF{q}$ of characteristic $p$. We describe an algorithm the asymptotic time complexity of which is equal to $\SoftO(\ell^2(1+\ell/p)\log q)$ bit operations. This algorithm is particularly useful when $\ell > p$ and as a consequence, we obtain an improvement of the complexity of the SEA point counting algorithm for small values of $p$. More precisely, we obtain a heuristic time complexity $\SoftO(\log^{4} q)$ and a space complexity $O(\log^{2} q)$, in the previously unfavorable case where $p \simeq \log q$. Compared to the best previous algorithms, the memory requirements of our SEA variation are smaller by a $\log^2 q$ factor.

We address the message authentication problem in two seemingly different communication models. In the first model, the sender and receiver are connected by an insecure channel and by a low-bandwidth auxiliary channel, that enables the sender to ``manually'' authenticate one short message to the receiver (for example, by typing a short string or comparing two short strings). We consider this model in a setting where no computational assumptions are made, and prove that for any $0 < \epsilon < 1$ there exists a $\log^* n$-round protocol for authenticating $n$-bit messages, in which only $2 \log(1 / \epsilon) + O(1)$ bits are manually authenticated, and any adversary (even computationally unbounded) has probability of at most $\epsilon$ to cheat the receiver into accepting a fraudulent message. Moreover, we develop a proof technique showing that our protocol is essentially optimal by providing a lower bound of $2 \log(1 / \epsilon) - O(1)$ on the required length of the manually authenticated string. The second model we consider is the traditional message authentication model. In this model the sender and the receiver share a short secret key; however, they are connected only by an insecure channel. We apply the proof technique above to obtain a lower bound of $2 \log(1 / \epsilon) - 2$ on the required Shannon entropy of the shared key. This settles an open question posed by Gemmell and Naor (CRYPTO '93). Finally, we prove that one-way functions are {\em necessary} (and sufficient) for the existence of protocols breaking the above lower bounds in the computational setting.

This paper proposes investigation of special sessions of the Diffie Hellman (DH) key exchange scheme on elliptic curves for which the shared key can be computed by a polynomial time algorithm. Such sessions are called \emph{singular}. Existence of singular sessions are demonstrated using the Frobenius expansion and polynomial representation of public keys which lead to an expression for the shared key. When the Weil pairing can be computed on the elliptic curve along with a modified pairing defined by a distortion map efficiently, a sufficient condition is obtained for sessions to be singular which can be verified in polynomial time. Hence this condition identifies sessions whose singular nature can be determined in polynomial time. A single round three party key exchange scheme is proposed using singular sessions in which efficient computation of the shared key of a pair of users by the third party is a necessary requirement. This scheme is thus a positive application of singular sessions and offers a possible alternative to the need for using super singular curves on which pairings can be computed efficiently.

In this paper, we present some more results about the security of the Kurosawa-Desmedt encryption scheme and a variant of it. We prove that after a modification, those schemes are secure against adaptive chosen-ciphertext attack not only under the decisional Diffie-Hellman assumption in standard model as before but also under the computational Diffie-Hellman assumption in the random oracle model. These results ensure that both the Kurosawa-Desmedt scheme and the variant have similar security merits as the Cramer-Shoup encryption scheme, which is proposed as a standard.

In many pairing-based protocols often the evaluation of the product of many pairing evaluations is required. In this paper we consider methods to compute such products efficiently. Focusing on pairing-friendly fields in particular, we evaluate methods for the Weil, Tate and Ate pairing algorithms for ordinary elliptic curves at various security levels. Our operation counts indicate that the minimal cost of each additional pairing relative to the cost of one is $\approx 0.61$, $0.45$, and $0.43$, for each of these pairings respectively at the 128-bit security level. For larger security levels the Ate pairing can have a relative additional cost of as low as $0.13$ for each additional pairing. These estimates allow implementors to make optimal algorithm choices for given scenarios, in which the number of pairings in the product, the security level, and the embedding degree are factors under consideration.

Cryptographic security for key exchange and secure session establishment protocols is often defined in the so called ``adaptive corruptions'' model. Even if the adversary corrupts one of the participants in the middle of the protocol execution and obtains the victim's secrets such as the private signing key, the victim must be able to detect this and abort the protocol. This is usually achieved by adding a key confirmation message to the protocol. Conventional symbolic methods for protocol analysis assume unforgeability of digital signatures, and thus cannot be used to reason about security in the adaptive corruptions model. We present a symbolic protocol logic for reasoning about authentication and key confirmation in key exchange protocols. The logic is cryptographically sound: a symbolic proof of authentication and secrecy implies that the protocol is secure in the adaptive corruptions model. We illustrate our method by formally proving security of an authenticated Diffie-Hellman protocol with key confirmation.

A visual cryptography scheme encodes a black&white secret image into n shadow images called shares which are distributed to the n participants. Such shares are such that only qualified subsets of participants can ``visually'' recover the secret image. Usually, the reconstructed image will be darker than the background of the image itself. In this paper we consider visual cryptography schemes satisfying the model introduced by Tzeng and Hu (Designs, Codes and Cryptography, Vol. 27, No. 3, pp. 207-227, 2002). In such a model the recovered secret image can be darker or lighter than the background. We prove a lower bound on the pixel expansion of the scheme and, for (2,n)-threshold visual cryptography schemes, we provide schemes achieving the bound. Our schemes improve on the ones proposed by Tzeng and Hu.

Recent progress on pairing implementation has made certain pairings extremely simple and fast to compute. Hence, it is natural to examine if there are consequences for the security of pairing-based cryptography. This paper gives a method to compute eta pairings in a way which avoids the requirement for a final exponentiation. The method does not lead to any improvement in the speed of pairing implementation. However, it seems appropriate to re-evaluate the security of pairing based cryptography in light of these new ideas. A multivariate attack on the pairing inversion problem is proposed and analysed. Our findings support the belief that pairing inversion is a hard computational problem.

In this paper we give a specification of a new block cipher that can be called the Courtois Toy Cipher (CTC). It is quite simple, and yet very much like any other known block cipher. If the parameters are large enough, it should evidently be secure against all known attack methods. However, we are not proposing a new method for encrypting sensitive data, but rather a research tool that should allow us (and other researchers) to experiment with algebraic attacks on block ciphers and obtain interesting results using a PC with reasonable quantity of RAM. For this reason the S-box of this cipher has only 3-bits, which is quite small. Ciphers with very small S-boxes are believed quite secure, for example the Serpent S-box has only 4 bits, and in DES all the S-boxes have 4 output bits. The AES S-box is not quite as small but can be described (in many ways) by a very small systems of equations with only a few monomials (and this fact can also be exploited in algebraic cryptanalysis). We believe that results on algebraic cryptanalysis of this cipher will have very deep implications for the security of ciphers in general.

Current electronic voting systems are not sufficient to satisfy trustworthy elections as they do not provide any proofs or confirming evidences of their honesty. This lack of trustworthiness is the main reason why e-voting is not widely spread even though e-voting is expected to be more efficient than the current plain paper voting. Many experts believe that the only way to assure voters that their intended votes are casted is to use paper receipts. In this paper, we propose an efficient scheme for issuing receipts to voters in e-voting using the well-known divide-and-choose method. Our scheme does not require any special printers or scanners, nor frequent observations to voting machines. In addition to that, our scheme is more secure than the previous ones.

In this paper we extend the threshold secret sharing schemes based on the Chinese remainder theorem in order to deal with more general access structures. Aspects like verifiability, secret sharing homomorphisms and multiplicative properties are also discussed.

Many research papers in pairing based cryptography treat pairings as a ``black box''. These papers build cryptographic schemes making use of various properties of pairings. If this approach is taken, then it is easy for authors to make invalid assumptions concerning the properties of pairings. The cryptographic schemes developed may not be realizable in practice, or may not be as efficient as the authors assume. The aim of this paper is to outline, in as simple a fashion as possible, the basic choices that are available when using pairings in cryptography. For each choice, the main properties and efficiency issues are summarized. The paper is intended to be of use to non-specialists who are interested in using pairings to design cryptographic schemes.

We introduce a set of criterions for classifying signature-only signature models. By the criterions, we classify signature models into 5 basic types and 69 general classes. Theoretically, 21140 kinds of signature models can be deduced by appropriately combining different general classes. The result comprises almost existing signature models. We also contribute a lot of new signature models. Moreover, we find the three signature models, i.e., group-nominee signature, multi-nominee signature and threshold-nominee signature, are of great importance in light of our classification.

The purpose of this paper is to calculate the running time of dense boolean matrix operations, as used in stream cipher cryptanalysis and integer factorization. Several variations of Gaussian Elimination, Strassen's Algorithm and the Method of Four Russians are analyzed. In particular, we demonstrate that Strassen's Algorithm is actually slower than the Four Russians algorithm for matrices of the sizes encountered in these problems. To accomplish this, we introduce a new model for tabulating the running time, tracking matrix reads and writes rather than field operations, and retaining the coefficients rather than dropping them. Furthermore, we introduce an algorithm known heretofore only orally, a ``Modified Method of Four Russians'', which has not appeared in the literature before. This algorithm is $\log n$ times faster than Gaussian Elimination for dense boolean matrices. Finally we list rough estimates for the running time of several recent stream cipher cryptanalysis attacks.

In this paper we give an overview of some of the cryptographic applications which were derived from the proposal of R.J. McEliece to use error correcting codes for cryptographic purposes. Code based cryptography is an interesting alternative to number theoretic cryptography. Many basic cryptographic functions like encryption, signing, hashing, etc. can be realized using code theoretic concepts. In this paper we briefly show how to correct errors in transmitted data by employing Goppa codes and describe possible applications to public key cryptography. The main focus of this paper is to provide detailed insight into the state of art of cryptanalysis of the McEliece cryptosystem and the effect on different cryptographic applications. We conclude, that for code based cryptography a public key of $88$KB offers sufficient security for encryption, while we need a public key of at least $597$KB for secure signing.

HAVAL is a cryptographic hash function proposed by Zheng et al. Rompay et al and Wang et al found collisions of full 3-Pass HAVAL. In this paper, we study the security of 4-Pass HAVAL. We find collisions of full versions of 4-Pass HAVAL. The attack is similar to the two-block attack of MD5 proposed by Wang et al. The computational complexity of the attack is about 2^30-2^32 for the first block and 2^27-2^29 for the second block. We use this attack to find 256bit collisions of 4-Pass HAVAL in 3-4 hour on a common PC.

In recent years, a large number of identity-based key agreement protocols from pairings have been proposed. Some of them are elegant and practical. However, the security of this type of protocols has been surprisingly hard to prove. The main issue is that a simulator is not able to deal with reveal queries, because it requires solving either a computational problem or a decisional problem, both of which are generally believed to be hard (i.e., computationally infeasible). The best solution of security proof published so far uses the gap assumption, which means assuming that the existence of a decisional oracle does not change the hardness of the corresponding computational problem. The disadvantage of using this solution to prove the security for this type of protocols is that such decisional oracles, on which the security proof relies, cannot be performed by any polynomial time algorithm in the real world, because of the hardness of the decisional problem. In this paper we present a method incorporating a built-in decisional function in this type of protocols. The function transfers a hard decisional problem in the proof to an easy decisional problem. We then discuss the resulting efficiency of the schemes and the relevant security reductions in the context of different pairings one can use.

At PKC 2006, Chow, Boyd, and Nieto introduced the concept of security-mediated certificateless (SMC) cryptography. This notion can be considered as a variant of certificateless cryptography with the property of instantaneous key revocation, or a variant of mediated cryptography without full key escrow. They presented a definition of security for SMC encryption, which covers (fully-adaptive) chosen ciphertext attack with public key replacement considered as a strong but essential attack on certificateless cryptographic schemes. They proposed two SMC encryption schemes, one is a generic construction based on any public key encryption, identity-based encryption and one-time signature schemes and the other is a concrete construction based on bilinear pairings, which were shown to be secure under their security definition. In this note, we, however, present two types of attacks demonstrating that their generic construction for SMC encryption fails to meet their security requirement. We then discuss how to repair the scheme and provide a provably-secure solution.

This paper proposes a new ID-based proxy signature scheme based on the bilinear pairings. The number of paring operation involved in the verification procedure of our scheme is only one, so our scheme is more efficient comparatively. The new scheme can be proved secure with the hardness assumption of the k-Bilinear Diffie-Hellman Inverse problem, in the random oracle model.

We propose cryptographic primitives for reading and assigning the (shared) secret found at a secret index in a vector of secrets. The problem can also be solved in constant round with existing general techniques based on arithmetic circuits and the ``equality test'' in [Damgard.et.al 05]. However the proposed technique requires to exchange less bits. The proposed primitives require a number of rounds that is independent of the size N of the vector, and only depends (linearly) on the number t of computing servers. A previously known primitive for reading a vector at a secret index works only for 2-party computations. Our primitives work for any number of computing participants/servers. The proposed techniques are secure against passive attackers, and zero knowledge proofs are provided to show that exactly one index of the array is read/written. The techniques work both with multiparty computations based on secret sharing and with multiparty computations based on threshold homomorphic encryption.

In this note we prove that the controversial Diffie-Hellman Knowledge problem is secure in the generic group model. This appears to be the first paper that presents any evidence as to whether the Diffie-Hellman Knowledge problem is true or false.

We define and construct Independent Zero-Knowledge Sets (ZKS) protocols. In a ZKS protocols, a Prover commits to a set $S$, and for any $x$, proves non-interactively to a Verifier if $x \in S$ or $x \notin S$ without revealing any other information about $S$. In the {\em independent} ZKS protocols we introduce, the adversary is prevented from successfully correlate her set to the one of a honest prover. Our notion of independence in particular implies that the resulting ZKS protocol is non-malleable. On the way to this result we define the notion of {\em independence} for commitment schemes. It is shown that this notion implies non-malleability, and we argue that this new notion has the potential to simplify the design and security proof of non-malleable commitment schemes. Efficient implementations of ZKS protocols are based on the notion of mercurial commitments. Our efficient constructions of independent ZKS protocols requires the design of {\em new} commitment schemes that are simultaneously independent (and thus non-malleable) and mercurial.

Two variants of CA-based public key authentication framework are proposed in this paper. The one is termed as public key cryptosystem without certificate management center (PKCwCMC) and the other is termed as proxy signature based authentication framework (PS-based AF). Moreover, we give an implementation of the former based on quadratic residue theory and an implementation of the latter from RSA. Both of the two variants can be looked as lite-CA based authentication frameworks since the workload and deployment of CAs in these systems are much lighter and easier than those of in the traditional CA-based PKC.

Several compositional forms of simulation-based security have been proposed in the literature, including universal composability, black-box simulatability, and variants thereof. These relations between a protocol and an ideal functionality are similar enough that they can be ordered from strongest to weakest according to the logical form of their definitions. However, determining whether two relations are in fact identical depends on some subtle features that have not been brought out in previous studies. We identify the position of a ``master process" in the distributed system, and some limitations on transparent message forwarding within computational complexity bounds, as two main factors. Using a general computational framework, called Sequential Probabilistic Process Calculus (SPPC), we clarify the relationships between the simulation-based security conditions. We also prove general composition theorems in SPPC. Many of the proofs are carried out based on a small set of equivalence principles involving processes and distributed systems. This gives us results that carry over to a variety of computational models.

Bilinear pairings based mutual authentication scheme using smart card is presented. We propose a novel technique of using two different servers, one for registration and other for authentication. The scheme is resilient to replay, forgery, man-in-the-middle and insider attacks.

Recently, there has been much interest in extending models for simulation-based security in such a way that the runtime of protocols may depend on the length of their input. Finding such extensions has turned out to be a non-trivial task. In this work, we propose a simple, yet expressive general computational model for systems of Interactive Turing Machines (ITMs) where the runtime of the ITMs may be polynomial per activation and may depend on the length of the input received. One distinguishing feature of our model is that the systems of ITMs that we consider involve a generic mechanism for addressing dynamically generated copies of ITMs. We study properties of such systems and, in particular, show that systems satisfying a certain acyclicity condition run in polynomial time. Based on our general computational model, we state different notions of simulation-based security in a uniform and concise way, study their relationships, and prove a general composition theorem for composing a polynomial number of copies of protocols, where the polynomial is determined by the environment. The simplicity of our model is demonstrated by the fact that many of our results can be proved by mere equational reasoning based on a few equational principles on systems.

We observe that a certain RSA-based secure hash function is homomorphic. We describe a protocol based on this hash function which prevents `cheating' in a data transfer transaction, while placing little burden on the trusted third party that oversees the protocol. We also describe a cryptographic protocol based on similar principles, through which a prover can demonstrate possession of an arbitrary set of data known to the verifier. The verifier isn't required to have this data at hand during the protocol execution, but rather only a small hash of it. The protocol is also provably as secure as integer factoring.