Advances in Cryptology - ASIACRYPT 2003

We propose asymmetric encryption schemes for which all ciphertexts are valid (which means here “reachable”: the encryption function is not only a probabilistic injection, but also a surjection). We thus introduce the Full-Domain Permutation encryption scheme which uses a random permutation. This is the first IND-CCA cryptosystem based on any trapdoor one-way permutation without redundancy, and more interestingly, the bandwidth is optimal: the ciphertext is over k more bits only than the plaintext, where 2 −  k is the expected security level. Thereafter, we apply it into the random oracle model by instantiating the random permutation with a Feistel network construction, and thus using OAEP. Unfortunately, the usual 2-round OAEP does not seem to be provably secure, but a 3-round can be proved IND-CCA even without the usual redundancy $m || 0^{k_1}$, under the partial-domain one-wayness of any trapdoor permutation. Although the bandwidth is not as good as in the random permutation model, absence of redundancy is quite new and interesting: many implementation risks are ruled out.

In this paper, we study some RSA-based semantically secure encryption schemes (IND-CPA) in the standard model. We first derive the exactly tight one-wayness of Rabin-Paillier encryption scheme which assumes that factoring Blum integers is hard. We next propose the first IND-CPA scheme whose one-wayness is equivalent to factoring generaln=pq (not factoring Blum integers). Our reductions of one-wayness are very tight because they require only one decryption-oracle query.

At Eurocrypt ‘02 Cramer and Shoup [7] proposed a general paradigm to construct practical public-key cryptosystems secure against adaptive chosen-ciphertext attacks as well as several concrete examples. Among the others they presented a variant of Paillier’s [21] scheme achieving such a strong security requirement and for which two, independent, decryption mechanisms are allowed. In this paper we revisit such scheme and show that by considering a different subgroup, one can obtain a different scheme (whose security can be proved with respect to a different mathematical assumption) that allows for interesting applications. In particular we show how to construct a perfectly hiding commitment schemes that allows for an on-line / off-line efficiency tradeoff. The scheme is computationally binding under the assumption that factoring is hard, thus improving on the previous construction by Catalano et al. [5] whose binding property was based on the assumption that inverting RSA[N,N] (i.e. RSA with the public exponent set to N) is hard.

We estimate the yield of the number field sieve factoring algorithm when applied to the 1024-bit composite integer RSA-1024 and the parameters as proposed in the draft version [17] of the TWIRL hardware factoring device [18]. We present the details behind the resulting improved parameter choices from [18].

We present a variation of the index calculus attack by Gaudry which can be used to solve the discrete logarithm problem in the Jacobian of hyperelliptic curves. The new algorithm has a running time which is better than the original index calculus attack and the Rho method (and other square-root algorithms) for curves of genus ≥ 3. We also describe another improvement for curves of genus ≥ 4 (slightly slower, but less dependent on memory space) initially mentioned by Harley and used in a number of papers, but never analyzed in details.

One of the recent thrust areas in research on hyperelliptic curve cryptography has been to obtain explicit formulae for performing arithmetic in the Jacobian of such curves. We continue this line of research by obtaining parallel versions of such formulae. Our first contribution is to develop a general methodology for obtaining parallel algorithm of any explicit formula. Any parallel algorithm obtained using our methodology is provably optimal in the number of multiplication rounds. We next apply this methodology to Lange’s explicit formula for arithmetic in genus 2 hyperelliptic curve – both for the affine coordinate and inversion free arithmetic versions. Since encapsulated add-and-double algorithm is an important countermeasure against side channel attacks, we develop parallel algorithms for encapsulated add-and-double for both of Lange’s versions of explicit formula. For the case of inversion free arithmetic, we present parallel algorithms using 4, 8 and 12 multipliers. All parallel algorithms described in this paper are optimal in the number of parallel rounds. One of the conclusions from our work is the fact that the parallel version of inversion free arithmetic is more efficient than the parallel version of arithmetic using affine coordinates.

The Weil and Tate pairings have been used recently to build new schemes in cryptography. It is known that the Weil pairing takes longer than twice the running time of the Tate pairing. Hence it is necessary to develop more efficient implementations of the Tate pairing for the practical application of pairing based cryptosystems. In 2002, Barreto et al. and Galbraith et al. provided new algorithms for the fast computation of the Tate pairing in characteristic three. In this paper, we give a closed formula for the Tate pairing on the hyperelliptic curve y2 = xp – x + d in characteristic p. This result improves the implementations in [BKLS02], [GHS02] for the special case p=3.

We describe an algorithm, AGM-X₀(N), for point counting on elliptic curves of small characteristic p using p-adic lifts of their invariants associated to modular curves X₀(N). The algorithm generalizes the contruction of Satoh [10], SST [11], and Mestre [9]. We describe this method and give details of its implementation for characteristics 2, 3, 5, 7, and 13.

This paper proposes a family of key management schemes for broadcast encryption based on a novel underlying structure – Time Varying Heterogeneous Logical Key Hierarchy (TVH-LKH). Note that the main characteristics of the previously reported key management schemes include the following: employment of a static underlying structure for key management, and addressing the subset covering problem over the entire underlying structure. Oppositely, the main underlying ideas for developing of the novel key management schemes based on TVH-LKH include the following: (i) employment of a reconfigurable underlying structure; and (ii) employment of a divide-and-conquer approach related to the underlying structure and an appropriate communications-storage-processing trade-off (for example, a small increase of the communication overload and large reduction of the storage and processing overload) for addressing the subset covering problem and optimization of the overloads. The design is based on a set of “static” keys at a receiver (stateless receiver) which are used in all possible reconfiguration of the underlying structure for key management, and accordingly, in a general case, a key plays different roles depending on the employed underlying structure. A particular family of the components for developing TVH-LKH, is also proposed and discussed. The proposed technique is compared with the recently reported schemes, and the advantages of the novel one are pointed out.

Authenticated Key Establishment (AKE) protocols enable two entities, say a client (or a user) and a server, to share common session keys in an authentic way. In this paper, we review AKE protocols from a little bit different point of view, i.e. the relationship between information a client needs to possess (for authentication) and immunity to the respective leakage of stored secrets from a client side and a server side. Since the information leakage would be more conceivable than breaking down the underlying cryptosystems, it is desirable to enhance the immunity to the leakage. First and foremost, we categorize AKE protocols according to how much resilience against the leakage can be provided. Then, we propose new AKE protocols that have immunity to the leakage of stored secrets from a client and a server (or servers), respectively. And we extend our protocols to be possible for updating secret values registered in server(s) or password remembered by a client.

A fair network payment protocol plays an important role in electronic commerce. The fairness concept in payments can be illustrated as that two parties (e.g. customers and merchants) exchange the electronic items (e.g. electronic money and goods) with each other in a fair manner that no one can gain advantage over the other even if there are malicious actions during exchanging process. In the previous works of fair payments, the buyer is usually required to sign a purchase message which can be traced by everyone. The information about where the buyer spent the money and what he purchased would easily be revealed by this way. This paper employs two techniques of off-line untraceable cash and designated confirmer signatures to construct a new fair payment protocol, in which the untraceability (or privacy) property can be achieved. A Restrictive Confirmation Signature Scheme (RCSS) will be introduced and used in our protocol to prevent the interested persons except the off-line TTP (Trusted Third Party) from tracing the buyer’s spending behavior.

We introduce a new cryptographic tool: multiset hash functions. Unlike standard hash functions which take strings as input, multiset hash functions operate on multisets (or sets). They map multisets of arbitrary finite size to strings (hashes) of fixed length. They are incremental in that, when new members are added to the multiset, the hash can be updated in time proportional to the change. The functions may be multiset-collision resistant in that it is difficult to find two multisets which produce the same hash, or just set-collision resistant in that it is difficult to find a set and a multiset which produce the same hash.We demonstrate how set-collision resistant multiset hash functions make an existing offline memory integrity checker secure against active adversaries. We improve on this checker such that it can use smaller time stamps without increasing the frequency of checks. The improved checker uses multiset-collision resistant multiset hash functions.

We present two new parallel algorithms for extending the domain of a UOWHF. The first algorithm is complete binary tree based construction and has less key length expansion than Sarkar’s construction which is the previously best known complete binary tree based construction. But only disadvantage is that here we need more key length expansion than that of Shoup’s sequential algorithm. But it is not too large as in all practical situations we need just two more masks than Shoup’s. Our second algorithm is based on non-complete l-ary tree and has the same optimal key length expansion as Shoup’s which has the most efficient key length expansion known so far. Using the recent result [9], we can also prove that the key length expansion of this algorithm and Shoup’s sequential algorithm are the minimum possible for any algorithms in a large class of “natural” domain extending algorithms. But its parallelizability performance is less efficient than complete tree based constructions. However if l is getting larger, then the parallelizability of the construction is also getting near to that of complete tree based constructions. We also give a sufficient condition for valid domain extension in sequential domain extension.

HAVAL is a cryptographic hash function proposed in 1992 by Zheng, Pieprzyk and Seberry. Its has a structure that is quite similar to other well-known hash functions such as MD4 and MD5. The specification of HAVAL includes a security parameter: the number of passes (that is, the number of times that a particular word of the message is used in the computation) can be chosen equal to 3, 4 or 5. In this paper we describe a practical attack that finds collisions for the 3-pass version of HAVAL. This means that it is possible to generate pairs of messages hashing to the same value. The computational complexity of the attack corresponds to about 229 computations of the compression function of 3-pass HAVAL; the required amount of memory is negligible.

Group signature schemes are fundamental cryptographictools that enable unlinkably anonymous authentication, in the same fashion that digital signatures provide the basis for strong authentication protocols. In this paper we present the first group signature scheme with constant-size parameters that does not require any group member, including group managers, to know trapdoor secrets. This novel type of group signature scheme allows public parameters to be shared among organizations. Such sharing represents a highly desirable simplification over existing schemes, which require each organization to maintain a separate cryptographic domain.

Constructing practical and provably secure group signature schemes has been a very active research topic in recent years. A group signature can be viewed as a digital signature with certain extra properties. Notably, anyone can verify that a signature is generated by a legitimate group member, while the actual signer can only be identified (and linked) by a designated entity called a group manager. Currently, the most efficient group signature scheme available is due to Camenisch and Lysyanskaya [CL02]. It is obtained by integrating a novel dynamic accumulator with the scheme by Ateniese, et al. [ACJT00].In this paper, we construct a dynamic accumulator that accumulates composites, as opposed to previous accumulators that accumulated primes. We also present an efficient method for proving knowledge of factorization of a committed value. Based on these (and other) techniques we design a novel provably secure group signature scheme. It operates in the common auxiliary string model and offers two important benefits: 1) the Join process is very efficient: a new member computes only a single exponentiation, and 2) the (unoptimized) cost of generating a group signature is 17 exponentiations which is appreciably less than the state-of-the-art.

ESIGN is an efficient signature scheme that has been proposed in the early nineties (see [14]). Recently, an effort was made to lay ESIGN on firm foundations, using the methodology of provable security. A security proof [15] in the random oracle model, along the lines of [2], appeared in support for ESIGN. However, several unexpected difficulties were found. Firstly, it was observed in [20], that the proof from [15] holds in a more restricted model of security than claimed. Even if it is quite easy to restore the usual security level, as suggested in [9], this shows that the methodology of security proofs is more subtle than it at first appears. Secondly, it was found that the proof needs the additional assumption that e is prime to φ(n), thus excluding the case where e is a small power of two, a very attractive parameter choice. The difficulty here lies in the simulation of the random oracle, since it relies on the distribution of e-th powers, which is not completely understood from a mathematical point of view, at least when e is not prime to φ(n). In this paper, we prove that the set of e-th power modulo an RSA modulus n, which is a product of two equal size integers p,q, is almost uniformly distributed on any large enough interval. This property allows to complete the security proof of ESIGN. We actually offer two proofs of our result: one is based on two-dimensional lattice reduction, and the the other uses Dirichlet characters. Besides yielding better bounds, the latter is one new example of the use of analytic number theory in cryptography.

We present an algorithm that finds polynomials with many roots modulo many primes by rotating candidate Number Field Sieve polynomials using the Chinese Remainder Theorem. We also present an algorithm that finds a polynomial with small coefficients among all integral translations of X of a given polynomial in ℤ[X]. These algorithms can be used to produce promising candidate Number Field Sieve polynomials.

The best practical algorithm for class group computations in imaginary quadratic number fields (such as group structure, class number, discrete logarithm computations) is a variant of the quadratic sieve factoring algorithm. Paradoxical as it sounds, the principles of the number field sieve, in a strict sense, could not be applied to number field computations, yet. In this article we give an indication of the obstructions.In particular, we first present fundamental core elements of a number field sieve for number field computations of which it is absolutely unknown how to design them in a useful way. Finally, we show that the existence of a number field sieve for number field computations with a running time asymptotics similar to that of the genuine number field sieve likely implies the existence of an algorithm for elliptic curve related computational problems with subexponential running time.

Most ancient Chinese padlocks are key-operated locks with splitting springs, and partially keyless letter-combination locks. They can be characterized based on the types of locks, the shapes of locks, the engravings of locks, the materials of locks, and the mechanisms of locks. Some locks and keys are not only very beautiful and artistic colorful, but also with various designs. As a result, a splitting spring padlock is an asymmetric key cryptosystem, and a combination padlock is a symmetric key cryptosystem.

In this paper we propose a new symmetric block cipher with the following paradoxical traceability properties: it is computationally easy to derive many equivalent secret keys providing distinct descriptions of the same instance of the block cipher. But it is computationally difficult, given one or even up to k equivalent keys, to recover the so called meta-key from which they were derived, or to find any additional equivalent key, or more generally to forge any new untraceable description of the same instance of the block cipher. Therefore, if each legitimate user of a digital content distribution system based on encrypted information broadcast (e.g. scrambled pay TV, distribution over the Internet of multimedia content, etc.) is provided with one of the equivalent keys, he can use this personal key to decrypt the content. But it is conjectured infeasible for coalitions of up to k traitors to mix their legitimate personal keys into untraceable keys they might redistribute anonymously to pirate decoders. Thus, the proposed block cipher inherently provides an efficient traitor tracing scheme [4]. The new algorithm can be described as an iterative block cipher belonging to the class of multivariate schemes. It has advantages in terms of performance over existing traitor tracing schemes and furthermore, it allows to restrict overheads to one single block (i.e. typically 80 to 160 bits) per encrypted content payload. Its strength relies upon the difficulty of the “Isomorphism of Polynomials” problem [17], which has been extensively investigated over the past years. An initial security analysis is supplied.

Khazad is a new block cipher initially proposed as a candidate to the NESSIE project. Its design is very similar to Rijndael, although it is a 64-bit block cipher. In this paper, we propose a new attack that can be seen as an extension of the Square attack. It takes advantage of redundancies between the round key derivation and the round function, and also exploits some algebraic observations over a few rounds. As a result, we can break 5 rounds of Khazad faster than exhaustive key search. This is the best known cryptanalytic result against Khazad.

We propose a new public key trace and revoke scheme secure against adaptive chosen ciphertext attack. Our scheme is more efficient than the DF scheme suggested by Y. Dodis and N. Fazio[9]. Our scheme reduces the length of enabling block of the DF scheme by (about) half. Additionally, the computational overhead of the user is lower than that of the DF scheme; instead, the computational overhead of the server is increased. The total computational overhead of the user and the server is the same as that of the DF scheme, and therefore, our scheme is more practical, since the computing power of the user is weaker than that of the server in many applications. In addition, our scheme is secure against adaptive chosen ciphertext attack under only the decision Diffie-Hellman (DDH) assumption and the collision-resistant hash function H assumption, whereas the DF scheme also needs the one-time MAC (message authentication code) assumption.

We study two closely related primitives: Broadcast Encryption and Key Predistribution Schemes (KPS). Broadcast Encryption allows a broadcaster to broadcast an encrypted message so that only a designated group of users can decrypt it. KPS allows a designated group of users to establish a common key non-interactively. We discover a generic method to construct efficient broadcast encryption schemes and KPSs naturally from Pseudo-Random Sequence Generators (PRSG) by observing that there are general ”patterns” to do so. The two currently best PRSG-based broadcast encryption schemes such as the ”Subset Difference” (SD) scheme by Naor Naor and Lotspiech and its refinement, the “Layered SD” (LSD) scheme by Halevy and Shamir, are indeed two special cases of our method. We demonstrate the power of this generic method by giving: (1) A solution to the most challenging variant of KPS: the one which supports arbitrary number of users to form a group yet secure against any collusion. We obtain a lower bound of the private key size at each user for any PRSG-based KPSs in this setting and construct a KPS that meets this bound. (2) An evidence that previous PRSG-based BE schemes, such as SD and LSD, can be further improved without any further assumption using this general method. We construct ”Flexible SD” and ”Flexible LSD” broadcast encryption schemes, which require less private key size while still maintain exactly the same broadcast size compared to their original SD/LSD schemes.

In Eurocrypt 2003, Boneh et al. presented a novel cryptographic primitive called aggregate signatures. An aggregate signature scheme is a digital signature that supports aggregation: i.e. given k signatures on k distinct messages from k different users it is possible to aggregate all these signatures into a single short signature.Applying the above concept to verifiably encrypted signatures, Boneh et al. introduced a new complexity assumption called the k-Element Aggregate Extraction Problem.In this paper we show that the k-Element Aggregate Extraction Problem is nothing but a Computational Diffie-Hellman Problem in disguise.

We show how to construct practical honest-verifier statistical zero-knowledge Diophantine arguments of knowledge (HVSZK AoK) that a committed tuple of integers belongs to an arbitrary language in bounded arithmetic. While doing this, we propose a new algorithm for computing the Lagrange representation of nonnegative integers and a new efficient representing polynomial for the exponential relation. We apply our results by constructing the most efficient known HVSZK AoK for non-negativity and the first constant-round practical HVSZK AoK for exponential relation. Finally, we propose the outsourcing model for cryptographic protocols and design communication-efficient versions of the Damgård-Jurik multi-candidate voting scheme and of the Lipmaa-Asokan-Niemi (b+1)st-price auction scheme that work in this model.

We describe slightly modified version (that we call the HOT protocol) of the Aiello-Ishai-Reingold oblivious transfer protocol from Eurocrypt 2001. In particular, the HOT protocol will be what we call weakly secure when coupled with many different homomorphic semantically secure public-key cryptosystems. Based on the HOT protocol, we construct an efficient verifiable oblivious transfer protocol and an efficient verifiable private equality test. As a concrete application of our results, we propose a novel protocol called proxy verifiable private equality test, and apply it to a cryptographic auction scheme to improve its security.

This paper investigates some modular powering functions suitable for cryptography. It is well known that the Rabin encryption function is a 4-to-1 mapping and breaking its one-wayness is secure under the factoring assumption. The previously reported encryption schemes using a powering function are variants of either the 4-to-1 mapping or higher n-to-1 mapping, where n>4. In this paper, we propose an optimized powering function that is a 3-to-1 mapping using a p2q-type modulus. The one-wayness of the proposed powering function is as hard as the infeasibility of the factoring problem. We present an efficient algorithm for computing the decryption for a p2q-type modulus, which requires neither modular inversion nor division. Moreover, we construct new provably secure digital signatures as an application of the optimized functions. In order to achieve provable security in the random oracle model, we usually randomize a message using random hashing or padding. However, we have to compute the randomization again if the randomized message is a non-cubic residue element — it is inefficient for long messages. We propose an algorithm that can deterministically find the unique cubic residue element for a randomly chosen element.

This paper introduces and makes concrete the concept of certificateless public key cryptography (CL-PKC), a model for the use of public key cryptography which avoids the inherent escrow of identity-based cryptography and yet which does not require certificates to guarantee the authenticity of public keys. The lack of certificates and the presence of an adversary who has access to a master key necessitates the careful development of a new security model. We focus on certificateless public key encryption (CL-PKE), showing that a concrete pairing-based CL-PKE scheme is secure provided that an underlying problem closely related to the Bilinear Diffie-Hellman Problem is hard.

In this paper, we introduce a conceptually very simple and demonstrative algorithm for finding small solutions (x,y) of ax + y = c mod N, where gcd(a,N)=1. Our new algorithm is a variant of the Euclidian algorithm. Unlike former methods, it finds a small solution whenever such a solution exists. Further it runs in time $\mathcal{O}((log N)^{3})$, which is the same as the best known previous techniques, e.g. lattice-based solutions.We then apply our algorithm to RSA-OAEP and RSA-Paillier to obtain better security proofs. We believe that there will be many future applications of this algorithm in cryptography.

Provable security usually makes the assumption that asource of perfectly random and secret data is available. However, in practical applications, and especially when smart cards are used, random generators are often far from being perfect or may be monitored using probing or electromagnetic analysis. The consequence is the need of a careful evaluation of actual security when idealized random generators are implemented.In this paper, we show that Esign signature scheme, like many cryptosystems, is highly vulnerable to so called partially known nonces attacks. Using a 1152-bit modulus, the generation of an Esign signature requires to draw at random a 768-bit integer. We show that the exposure of only 8 bits out of those 768 bits, for 57 signatures, is enough to recover the whole secret signature key in a few minutes.It should be clear that we do not cryptanalyze a good implementation of Esign nor do we find a theoretical flaw. However, our results show that random data used to generate signatures must be very carefully produced and protected against any kind of exposure, even partial.As an independent result, we show that the factorization problem is equivalent to the existence of an oracle returning the most or least significant bits of S mod p, on input S randomly chosen in ℤ _pq .

One-time proxy signatures are one-time signatures for which a primary signer can delegate his or her signing capability to a proxy signer. In this work we propose two one-time proxy signature schemes with different security properties. Unlike other existing one-time proxy signatures that are constructed from public key cryptography, our proposed schemes are based one-way functions without trapdoors and so they inherit the communication and computation efficiency from the traditional one-time signatures. Although from a verifier point of view, signatures generated by the proxy are indistinguishable from those created by the primary signer, a trusted authority can be equipped with an algorithm that allows the authority to settle disputes between the signers. In our constructions, we use a combination of one-time signatures, oblivious transfer protocols and certain combinatorial objects. We characterise these new combinatorial objects and present constructions for them.

Motivated by privacy issues associated with dissemination of signed digital certificates, we define a new type of signature scheme called a ‘Universal Designated-Verifier Signature’ (UDVS). A UDVS scheme can function as a standard publicly-verifiable digital signature but has additional functionality which allows any holder of a signature (not necessarily the signer) to designate the signature to any desired designated-verifier (using the verifier’s public key). Given the designated-signature, the designated-verifier can verify that the message was signed by the signer, but is unable to convince anyone else of this fact.We propose an efficient deterministic UDVS scheme constructed using any bilinear group-pair. Our UDVS scheme functions as a standard Boneh-Lynn-Shacham (BLS) signature when no verifier-designation is performed, and is therefore compatible with the key-generation, signing and verifying algorithms of the BLS scheme. We prove that our UDVS scheme is secure in the sense of our unforgeability and privacy notions for UDVS schemes, under the Bilinear Diffie-Hellman (BDH) assumption for the underlying group-pair, in the random-oracle model. We also demonstrate a general constructive equivalence between a class of unforgeable and unconditionally-private UDVS schemes having unique signatures (which includes the deterministic UDVS schemes) and a class of ID-Based Encryption (IBE) schemes which contains the Boneh-Franklin IBE scheme but not the Cocks IBE scheme.