Search

Many tasks in cryptography (e.g., digital signature verification) call for verification of a basic operation like modular exponentiation in some group: given (g, x, y) check that gx = y. This is typically done by re-computing gx and checking we get y. We would like to do it differently, and faster. The approach we use is batching. Focusing first on the basic modular exponentiation operation, we provide some probabilistic batch verifiers, or tests, that verify a sequence of modular exponentiations significantly faster than the naive re-computation method. This yields speedups for several verification tasks that involve modular exponentiations. Focusing specifically on digital signatures, we then suggest a weaker notion of (batch) verification which we call "screening." It seems useful for many usages of signatures, and has the advantage that it can be done very fast; in particular, we show how to screen a sequence of RSA signatures at the cost of one RSA verification plus hashing. [ABSTRACT FROM AUTHOR]

In this paper we present a method for improving the performance of RSA-type exponentiations. The scheme is based on the observation that replacing the exponent d by d′ = d + kΦ(n) has no arithmetic impact but results in significant speed-ups when k is properly chosen. Statistical analysis, verified by extensive simulations, confirms a performance improvement of 9.3% for the square-and-multiply scheme and 4.3% for the signed binary digit algorithm. However, the most attractive feature of our method seems to be the fact that in most cases, existing exponentiation black-boxes can be accelerated by simple external one-time pre-computations without any internal code or hardware modifications. [ABSTRACT FROM AUTHOR]

We present a new protocol that allows two players to exchange digital signatures over the Internet in a fair way, so that either each player gets the other's signature, or neither player does. The obvious application is where the signatures represent items of value, for example, an electronic check or airline ticket. The protocol can also be adapted to exchange encrypted data. The protocol relies on a trusted third party, but is "optimistic," in that the third party is only needed in cases where one player attempts to cheat or simply crashes. A key feature of our protocol is that a player can always force a timely and fair termination, without the cooperation of the other player. [ABSTRACT FROM AUTHOR]

We consider an environment in which many servers serve an even larger number of clients (e.g. the web), and it is required to meter the interaction between servers and clients. More specifically, it is desired to count the number of clients that were served by a server. A major possible application is to measure the popularity of web pages in order to decide on advertisement fees. The metering process must be very efficient and should not require extensive usage of any new communication channels. The metering ­ould also be secure against fraud attempts by servers which inflate the number of their clients and against clients that attempt to disrupt the metering process. We suggest several secure and efficient constructions of metering systems, based on efficient cryptographic techniques. They are also very accurate and can preserve the privacy of the clients. [ABSTRACT FROM AUTHOR]

Recently, there has been an interest in creating practical anonymous electronic cash with the ability to conduct payments of exact amounts, as is typically the practice in physical payment systems. The most general solution for such payments is to allow electronic coins to be divisible (e.g., each coin can be spent incrementally but total purchases are limited to the monetary value of the coin). In Crypto'95, T. Okamoto presented the first efficient divisible, anonymous (but linkable) off-line e-cash scheme requiring only O(logN) computations for each of the withdrawal, payment and deposit procedures, where N = (total coin value)/ (smallest divisible unit) is the divisibility precision. However, the zero-knowledge protocol used for the creation of a blinded unlinkable coin by Okamoto is quite inefficient and is used only at set-up to make the system efficient. Incorporating "unlinkable" blinding only in the setup, however, limits the level of anonymity offered by allowing the linking of all coins withdrawn—rather than a more desirable anonymity which allows only linking of subcoins of a withdrawn coin. In this paper we make a further step towards practicality of complete (i.e., divisible) anonymous e-cash by presenting a solution where all procedures (set-up, withdrawal, payment and deposit) are bounded by tens of exponentiations; in particular we improve on Okamoto's result by 3 orders of magnitude, while the size of the coin remains about 300 Bytes, based on a 512 bit modulus. Moreover, the protocols are compatible with tracing methods used for "fair" or "revokable" anonymous cash. [ABSTRACT FROM AUTHOR]

Recently an efficient solution to the discrete logarithm problem on elliptic curves over Fp with p points (p: prime), so-called anomalous curves, was independently discovered by Semaev [14], Smart [17], and Satoh and Araki [12]. Since the solution is very efficient, i.e., O(¦p¦3), the Semaev-Smart-Satoh-Araki (SSSA) algorithm implies the possibility of realizing a trapdoor for the discrete logarithm problem, and we have tried to utilize the SSSA algorithm for constructing a cryptographic scheme. One of our trials was to realize an identity-based cryptosystem (key-distribution) which has been proven to be as secure as a primitive problem, called the Diffie-Hellman problem on an elliptic curve over Z/nZ (n = pq, p and q are primes) where Ep and Eq are anomalous curves (anomalous En-Diffie-Hellman problem). Unfortunately we have found that the anomalous En-Diffie-Hellman problem is not secure (namely, our scheme is not secure). First, this paper introduces our trial of realizing an identity-based cryptosystem based on the SSSA algorithm, and then shows why the anomalous En-Diffie-Hellman problem is not secure. In addition, we generalize the observation of our breaking algorithm and present reductions of factoring n to computing the order2 of an elliptic curve over Z/nZ. (These reductions roughly imply the equivalence of intractability between factoring and computing elliptic curve's order.) The algorithm of breaking our identity-based cryptosystem is considered to be a special case of these reductions, and the essential reason why our system was broken can be clarified through these reductions: En in our system is a very specific curve such that the order of En (i.e., n) is trivially known. [ABSTRACT FROM AUTHOR]

Vanstone and Zuccherato [3] propose a cryptographic system based on an elliptic curve modulo a composite number. We show that the composite numbers so constructed are easily factored, rendering the system insecure. [ABSTRACT FROM AUTHOR]

Multi-receiver authentication is an extension of traditional point-to-point message authentication in which a sender broadcasts a single authenticated message such that all the receivers can independently verify the authenticity of the message, and malicious groups of up to a given size of receivers can not successfully impersonate the transmitter, or substitute a transmitted message. This paper presents some new results on unconditionally secure multi-receiver authentication codes. First we generalize a polynomial construction due to Desmedt, Frankel and Yung, to allow multiple messages be authenticated with each key. Second, we propose a new flexible construction for multi-receiver A-code by combining an A-code and an (n, m, k)-cover-free family. Finally, we introduce the model of multi-receiver A-code with dynamic sender and present an efficient construction for that. [ABSTRACT FROM AUTHOR]

A broadcast encryption system allows a center to communicate securely over a broadcast channel with selected sets of users. Each time the set of privileged users changes, the center enacts a protocol to establish a new broadcast key that only the privileged users can obtain, and subsequent transmissions by the center are encrypted using the new broadcast key. We study the inherent trade-off between the number of establishment keys held by each user and the number of transmissions needed to establish a new broadcast key. For every given upper bound on the number of establishment keys held by each user, we prove a lower bound on the number of transmissions needed to establish a new broadcast key. We show that these bounds are essentially tight, by describing broadcast encryption systems that come close to these bounds. [ABSTRACT FROM AUTHOR]

We study the information rate of secret sharing schemes whose access structure is bipartite. In a bipartite access structure there are two classes of participants and all participants in the same class play an equivalent role in the structure. We characterize completely the bipartite access structures that can be realized by an ideal secret sharing scheme. Both upper and lower bounds on the optimal information rate of bipartite access structures are given. [ABSTRACT FROM AUTHOR]

Advances in the design of Boolean functions using heuristic techniques are reported. A genetic algorithm capable of generating highly nonlinear balanced Boolean functions is presented. Hill climbing techniques are adapted to locate balanced, highly nonlinear Boolean functions that also almost satisfy correlation immunity. The definitions for some cryptographic properties are generalised, providing a measure suitable for use as a fitness function in a genetic algorithm seeking balanced Boolean functions that satisfy both correlation immunity and the strict avalanche criterion. Results are presented demonstrating the effectiveness of the methods. [ABSTRACT FROM AUTHOR]

We study a corpus of particular Boolean functions: the idempotents. They enable us to construct functions which achieve the best possible tradeoffs between the cryptographic fundamental properties: balancedness, correlation-immunity, a high degree and a high nonlinearity (that is a high distance from the affine functions). They all represent extremely secure cryptographic primitives to be implemented in stream ciphers. [ABSTRACT FROM AUTHOR]

We determine those Boolean functions on GF(2)n which satisfy the propagation criterion of degree ℓ and order k ≥ n − ℓ }- 2. All of theses functions are quadratic. We design nonquadratic Boolean functions satisfying the criterion PC(ℓ) of order k by using the Maiorana-McFarland construction involving nonlinear mappings derived from non-linear codes. [ABSTRACT FROM AUTHOR]

We introduce a robust and efficient mix-network for exponentiation, and use it to obtain a threshold decryption mix-network for ElGamal encrypted messages, in which mix servers do not need to trust each other for the correctness of the result. If a subset of mix servers cheat, they will be caught with an overwhelming probability, and the decryption can restart after replacing them, in a fashion that is transparent to the participants providing the input to be decrypted. As long as a quorum is not controlled by an adversary, the privacy of the mix is guaranteed. Our solution is proved to be secure if a commonly used assumption, the Decision Diffie-Hellman assumption, holds. Of possible independent interest are two new methods that we introduce: blinded destructive robustness, a type of destructive robustness with protection against leaks of secret information; and repetition robustness, a method for obtaining robustness for some distributed vector computations. Here, two or more calculations of the same equation are performed, where the different computations are made independent by the use of blinding and permutation. The resulting vectors are then unblinded, sorted and compared to each other. This allows us to detect cheating (resulting in inequality of the vectors). Also of possible independent interest is a modular extension to the El-Gamal encryption scheme, making the resulting scheme non-malleable in the random oracle model. This is done by interpreting part of the ciphertext as a public key, and sign the ciphertext using the corresponding secret key. [ABSTRACT FROM AUTHOR]

In this paper we construct a universally verifiable Mix-net where the amount of work done by a verifier is independent of the number of mix-servers. Furthermore, the computational task of each mix-server is constant against the number of mix-servers except for some negligible tasks like addition. The scheme is robust, too. [ABSTRACT FROM AUTHOR]

In response to the current need for fast, secure and cheap public-key cryptography, we study an interactive zero-knowledge identification scheme and a derived signature scheme that combine provable security based on the general problem of computing discrete logarithms modulo any number, short identity-based keys, very short transmission and minimal on-line computation. This leads to both efficient and secure applications well suited to the implementation on low cost smart cards. We develop complete proofs of completeness, soundness and statistical zero-knowledge property of the identification scheme. The security analysis of the signature scheme leads to present a novel number theoretical lemma of independent interest and an original use of the "forking lemma" technique. From a practical point of view, the possible choice of parameters is discussed and we submit performances of an actual implementation on a cheap smart card. As an example, a complete and secure authentication can be performed in less than 20 ms with low cost equipment. [ABSTRACT FROM AUTHOR]

In contrast to ordinary digital signatures, the verification of undeniable signatures and of confirmer signatures requires the cooperation of the signer or of a designated confirmer, respectively. Various schemes have been proposed so far, from practical solutions based on specific number-theoretic assumptions to theoretical constructions using basic cryptographic primitives. To motivate the necessity of new and provably secure constructions for confirmer signatures, we first describe a flaw in a previous realization by Okamoto. We then present two generic constructions for designing provably secure and efficient confirmer variants of many well-known signature schemes, including the schemes by Schnorr, Fiat and Shamir, ElGamal, and the RSA scheme. The constructions employ a new tool called confirmer commitment schemes. In this concept the ability to open the committed value is delegated to a designated confirmer. We present an efficient realization based on the Decision-Diffie-Hellman assumption. [ABSTRACT FROM AUTHOR]

Provable security is a very nice property for cryptographic protocols. Unfortunately, in many cases, this is at the cost of a considerable loss in terms of efficiency. More recently, a new approach to achieve some kind of provable security was explored using the so-called "random oracle model". Last year, Stern and the author studied the security of blind signatures in this model. We first defined appropriate notions of security for electronic cash purpose, then, we proposed the first efficient and provably secure schemes. Unfortunately, even if our proof prevents a user from spending more coins than he had withdrawn, this is only if the number of withdrawn coins is poly-logarithmically bounded. In this paper, we propose a generic transformation of those schemes which extends the security even after polynomially many withdrawals. Moreover, this transformation keeps the scheme efficient and so can be used in a secure and efficient anonymous off-line electronic cash system. [ABSTRACT FROM AUTHOR]

This paper describes efficient protocols for multi-party computations that are information-theoretically secure against passive attacks. The results presented here apply to access structures based on quorum systems, which are collections of sets enjoying a naturally-motivated self-intersection property. Quorum-based access structures include threshold systems but are far richer and more general, and they have specific applicability to several problems in distributed control and management. The achievable limits of security in quorum-based multi-party computation are shown to be equivalent to those determined by Hirt and Maurer in [HM97], drawing a natural but non-obvious connection between quorum systems and the extremes of secure multi-party computation. Moreover, for both the general case and for specific applications, the protocols presented here are simpler and more efficient. [ABSTRACT FROM AUTHOR]

We show that oblivious transfer can be based on a very general notion of asymmetric information difference. We investigate a Universal Oblivious Transfer, denoted UOT(X, Y), that gives Bob the freedom to access Alice's input X in an arbitrary way as long as he does not obtain full information about X. Alice does not learn which information Bob has chosen. We show that oblivious transfer can be reduced to a single execution of UOT(X, Y) with Bob's knowledge Y restricted in terms of Rényi entropy of order α > 1. For independently repeated UOT the reduction works even if only Bob's Shannon information is restricted, i.e. if H(X¦Y) > 0 in every UOT(X, Y). Our protocol requires that honest Bob obtains at least half of Alice's information X without error. [ABSTRACT FROM AUTHOR]

Problems of secure communication and computation have been studied extensively in network models. In this work, we ask what is possible in the information-theoretic setting when the adversary is very strong (Byzantine) and the network connectivity is very low (minimum needed for crash-tolerance). For some natural models, our results imply a sizable gap between the connectivity required for perfect security and for probabilistic security. Our results also have implications to the commonly studied simple channel model and to general secure multiparty computation. [ABSTRACT FROM AUTHOR]

We prove the existence of an oracle relative to which there exist several well-known cryptographic primitives, including one-way permutations, but excluding (for a suitably strong definition) collision-intractible hash functions. Thus any proof that such functions can be derived from these weaker primitives is necessarily non-relativizing; in particular, no provable construction of a collision-intractable hash function can exist based solely on a "black box" one-way permutation. This result can be viewed as a partial justification for the common practice of treating the collision-intractable hash function as a cryptographic primitive, rather than attempting to derive it from a weaker primitive (such as a one-way permutation). [ABSTRACT FROM AUTHOR]

The one-wayness of linear permutations, i.e., invertible linear Boolean functions F: {0,1}n → {0, 1}n, is investigated. For linear permutations with a triangular matrix description (tlinear permutations), we prove that one-wayness, C(F−1)/C(F), is non-trivially upperbounded by 16√n, where C(.) denotes unrestricted circuit complexity. We also prove that this upper bound strengthens as the complexity of the inverse function increases, limiting the one-wayness of t-linear permutations with C(F−1) = n2/(c log2(n)) to a constant, i.e., a value that is independent of n. Direct implications for linear and also non-linear permutations are discussed. Moreover, and for the first time ever, a description is given about where, in the case of linear permutations, practical one-wayness would have to come from, if it exists. [ABSTRACT FROM AUTHOR]

This paper proposes a novel public-key cryptosystem, which is practical, provably secure and has some other interesting properties as follows:1.Its trapdoor technique is essentially different from any other previous schemes including RSA-Rabin and Diffie-Hellman.2.It is a probabilistic encryption scheme.3.It can be proven to be as secure as the intractability of factoring n = p2q (in the sense of the security of the whole plaintext) against passive adversaries.4.It is semantically secure under the p-subgroup assumption, which is comparable to the quadratic residue and higher degree residue assumptions.5.Under the most practical environment, the encryption and decryption speeds of our scheme are comparable to (around twice slower than) those of elliptic curve cryptosystems.6.It has a homomorphic property: E(m0, r0)E(m1, r1) mod n = E(@#@ m0 + m1, r2), where E(m, r) means a ciphertext of plaintext m as randomized by r and m0+ m1 < p.7.Anyone can change a ciphertext, C = E(m, r), into another ciphertext, C′ = Chr' mod n, while preserving plaintext of C (i.e., C′ = E(m,r″)), and the relationship between C and C′ can be concealed. [ABSTRACT FROM AUTHOR]

We introduce a new cryptosystem with trapdoor decryption based on the difficulty of computing discrete logarithms in the class group of the nonmaximal imaginary quadratic order NΔq, where δq = δq2, δ square-free and q prime. The trapdoor information is the conductor q. Knowledge of this trapdoor information enables one to switch to and from the class group of the maximal order NΔ, where the representatives of the ideal classes have smaller coefficients. Thus, the decryption procedure may be performed in the class group of NΔ rather than in the class group of the public NΔq, which is much more efficient. We show that inverting our proposed cryptosystem is computationally equivalent to factoring the non-fundamental discriminant δq, which is intractable for a suitable choice of δ and q. We also describe how signature schemes in NΔq may be set up using this trapdoor information. Furthermore, we illustrate how one may embed key escrow capability into classical imaginary quadratic field cryptosystems. [ABSTRACT FROM AUTHOR]

We present a new scheme called universal block chaining with sum (or chain & sum primitive (C&S) for short), and show its application to the problem of combined encryption and authentication of data. The primitive is a weak CBC-type encryption along with a summing step, and can be used as a front end to stream ciphers to encrypt pages or blocks of data (e.g., in an encrypted file system or in a video stream). Under standard assumptions, the resulting encryption scheme provably acts as a random permutation on the blocks, and has message integrity features of standard CBC encryption. The primitive also yields a very fast message authentication code (MAC), which is a multivariate polynomial evaluation hash. The multivariate feature and the summing aspect are novel parts of the design. Our tests show that the chain & sum primitive adds approximately 20 percent overhead to the fastest stream ciphers. [ABSTRACT FROM AUTHOR]

We argue that the invertibility of a block cipher can reduce the security of schemes that use it, and a better starting point for scheme design is the non-invertible analog of a block cipher, that is, a pseudorandom function (PRF). Since a block cipher may be viewed as a pseudorandom permutation, we are led to investigate the reverse of the problem studied by Luby and Rackoff, and ask: "how can one transform a PRP into a PRF in as security-preserving a way as possible?" The solution we propose is data- dependent re- keying. As an illustrative special case, let E: {0, 1}n x {0, 1}n → {0, 1}n be the block cipher. Then we can construct the PRF F from the PRP E by setting F(k, x) = E(E(k, x), x). We generalize this to allow for arbitrary block and key lengths, and to improve efficiency. We prove strong quantitative bounds on the value of data-dependent re-keying in the Shannon model of an ideal cipher, and take some initial steps towards an analysis in the standard model. [ABSTRACT FROM AUTHOR]

Remotely keyed encryption schemes (RKESs), introduced by Blaze [6], support high-band width cryptographic applications (such as encrypted video conferences) in which long-lived secrets (such as users' private keys) never leave lower-bandwidth environments such as secure smart-cards. We provide a formal framework in which to study the security of RKESs and give an RKES that satisfies our formal security requirements. Our RKES is efficient in that the amount of communication and computation required of the smart-card is independent of the input size. Our proof of security uses the pseudorandom permutation framework of Naor and Reingold [14] in an essential way. [ABSTRACT FROM AUTHOR]

We present fast and practical methods for generating randomly distributed pairs of the form (x,gx mod p) or (x, xe mod N), using precomputation. These generation schemes axe of wide applicability for speeding-up public key systems that depend on exponentiation and offer a smooth memory-speed trade-off. The steps involving exponentiation in these systems can be reduced significantly in many cases. Our schemes are most suited for server applications. We present security analyses of our schemes using standard assumptions, including analyses for fully adaptive attacks. Our methods are novel in the sense that they identify and thoroughly exploit the randomness issues related to the instances generated in these public-key schemes. Our constructions use random walks on Cayley (expander) graphs over Abelian groups. Our analysis involves non-linear versions of lattice problems. It appears that any realistic attack on our schemes would need to solve such problems. [ABSTRACT FROM AUTHOR]

In this paper we describe a new paradigm for carrying out massively parallel computations such as brute force cryptanalysis of encryption schemes. It uses photographic films to store the internal state of a bit-sliced computation, and contact printing to carry out the computational steps. While it does not have the exponential speedup of quantum computation or the potential parallelism of DNA computation, it seems to be more practical since it is based on simple commercially available technology. In the last part of the paper we consider hybrid electronic/photographic computations, which combine the advantages of the two models of computation. [ABSTRACT FROM AUTHOR]

At present, there are two competing index calculus variants for computing discrete logarithms in (ℤ/pℤ)* in practice. The purpose of this paper is to summarize the recent practical experience with a generalized implementation covering both a variant of the Number Field Sieve and the Gaussian integer method. By this implementation we set a record with p consisting of 85 decimal digits. With regard to computational results, including the running time, we provide a comparison of the two methods for this value of p. [ABSTRACT FROM AUTHOR]

This paper is about the design of improved algorithms to solve Isomorphisms of Polynomials (IP) problems. These problems were first explicitly related to the problem of finding the secret key of some asymmetric cryptographic algorithms (such as Matsumoto and Imai's C* scheme of [12], or some variations of Patarin's HFE scheme of [14]). Moreover, in [14], it was shown that IP can be used in order to design an asymmetric authentication or signature scheme in a straightforward way. We also introduce the more general Morphisms of Polynomials problem (MP). As we see in this paper, these problems IP and MP have deep links with famous problems such as the Isomorphism of Graphs problem or the problem of fast multiplication of n x n matrices. The complexities of our algorithms for IP are still not polynomial, but they are much more efficient than the previously known algorithms. For example, for the IP problem of finding the two secret matrices of a Matsumoto-Imai C* scheme over K = Fq, the complexity of our algorithms is $$\mathcal{O}(q^{n/2} )$$ instead of $$\mathcal{O}(q^{(n^2 )} )$$ for previous algorithms. (In [13], the C* scheme was broken, but the secret key was not found). Moreover, we have algorithms to achieve a complexity $$\mathcal{O}(q^{\tfrac{3}{2}n} )$$ on any system of n quadratic equations with n variables over K = Fq (not only equations from C*). We also show that the problem of deciding whether a polynomial isomorphism exists between two sets of equations is not NP-complete (assuming the classical hypothesis about Arthur-Merlin games), but solving IP is at least as difficult as the Graph Isomorphism problem (GI) (and perhaps much more difficult), so that IP is unlikely to be solvable in polynomial time. Moreover, the more general Morphisms of Polynomials problem (MP) is NP-hard. Finally, we suggest some variations of the IP problem that may be particularly convenient for cryptographic use. [ABSTRACT FROM AUTHOR]

Let P(x) ≡ 0(mod N) be a modular multivariate polynomial equation, in m variables, and total degree k with a small root x0. We show that there is an algorithm which determines c (≥ 1) integer polynomial equations (in m variables) of total degree polynomial in cmklog N, in time polynomial in cmklog N, such that each of the equations has x0 as a root. This algorithm is an extension of Coppersmith's algorithm [2], which guarantees only one polynomial equation. It remains an open problem to determine x0 from these linearly independent equations (which may not be algebraically independent) in polynomial time. The algorithm can be used to attack an RSA scheme with small exponent in which a message is padded with random bits in multiple locations. Given two encryptions of the same underlying message with multiple random paddings of total size about 1/9 of the length N (for exponent 3 RSA), the algorithm can be used to obtain the message. [ABSTRACT FROM AUTHOR]

A traceability scheme is a broadcast encryption scheme such that a data supplier T can trace malicious authorized users (traitors) who gave a decryption key to an unauthorized user (pirate). This paper first derives lower bounds on the sizes of keys and ciphertexts. These bounds are all tight because an optimum one-time use scheme is also presented. We then propose a multiple-use scheme which approximately meets our bounds. This scheme is proven to be secure as well as much more efficient than the schemes by Chor, Fiat and Naor. Finally, practical types of asymmetric schemes with arbiter are discussed in which T cannot frame any authorized user as a traitor. [ABSTRACT FROM AUTHOR]

First, we introduce the notion of divertibility as a protocol property as opposed to the existing notion as a language property (see Okamoto, Ohta [OO90]). We give a definition of protocol divertibility that applies to arbitrary 2-party protocols and is compatible with Okamoto and Ohta's definition in the case of interactive zero-knowledge proofs. Other important examples falling under the new definition are blind signature protocols. We propose a sufficiency criterion for divertibility that is satisfied by many existing protocols and which, surprisingly, generalizes to cover several protocols not normally associated with divertibility (e.g., Diffie-Hellman key exchange). Next, we introduce atomic proxy cryptography, in which an atomic proxy function, in conjunction with a public proxy key, converts ciphertexts (messages or signatures) for one key into ciphertexts for another. Proxy keys, once generated, may be made public and proxy functions applied in untrusted environments. We present atomic proxy functions for discrete-log-based encryption, identification, and signature schemes. It is not clear whether atomic proxy functions exist in general for all public-key cryptosystems. Finally, we discuss the relationship between divertibility and proxy cryptography. [ABSTRACT FROM AUTHOR]

Large weak key classes of IDEA are found for which membership is tested with a differential-linear test while encrypting with a single key. In particular, one in every 265 keys for 8.5-round IDEA is weak. A related-key differential-linear attack on 4-round IDEA is presented which is successful for all keys. Large weak key classes are found for 4.5- to 6.5-round and 8-round IDEA for which membership of these classes is tested using similar related-key differential-linear tests. [ABSTRACT FROM AUTHOR]

In this paper we cryptanalyze the proposed (almost accepted) ANSI X9.52 CBCM mode. The CBCM mode is a triple-DES CBC variant which was designed against powerful attacks which control intermediate feedbacks for the benefit of the attacker. For this purpose, it uses intermediate feedbacks that the attacker cannot control, choosing them as a keyed OFB stream, independent of the plaintexts and ciphertexts. The attack we describe finds a way to use even this kind of feedback for the benefit of the attacker. It requires a single chosen ciphertext of 265 blocks and 258 complexity of analysis. We also describe an adaptive known-IV related-key attack which find one of three 56-bit keys requiring one known plaintext encrypted under 233 different but related keys with 257 complexity of analysis. [ABSTRACT FROM AUTHOR]

In this paper we consider generic algorithms for computational problems in cyclic groups. The model of a generic algorithm was proposed by Shoup at Eurocrypt '97. A generic algorithm is a generalpurpose algorithm that does not make use of any particular property of the representation of the group elements. Shoup proved the hardness of the discrete logarithm problem and the Diffie-Hellman problem with respect to such algorithms for groups whose order contains a large prime factor. By extending Shoup's technique we prove lower bounds on the complexity of generic algorithms solving different problems in cyclic groups, and in particular of a generic reduction of the discrete logarithm problem to the Diffie-Hellman problem. It is shown that the two problems are not computationally equivalent in a generic sense for groups whose orders contain a multiple large prime factor. This complements earlier results which stated this equivalence for all other groups. Furthermore, it is shown that no generic algorithm exists that computes p-th roots efficiently in a group whose order is divisible by p2 if p is a large prime. [ABSTRACT FROM AUTHOR]

RC5 is a fast block cipher designed by Ron Rivest in 1994. Since then several attempts of cryptanalysis of this cipher were published. The best previously known attack requires 254 chosen plaintexts in order to derive the full set of 25 subkeys for the 12 round RC5 with 32 bit words. In this paper we show a drastic improvement of these results due to a novel partial differential approach. Our attack requires 244 chosen plaintexts. We show that the 64 bit word version of RC5 is also much weaker than it was expected. [ABSTRACT FROM AUTHOR]

We provide evidence that breaking low-exponent RSA cannot be equivalent to factoring integers. We show that an algebraic reduction from factoring to breaking low-exponent RSA can be converted into an efficient factoring algorithm. Thus, in effect an oracle for breaking RSA does not help in factoring integers. Our result suggests an explanation for the lack of progress in proving that breaking rsa is equivalent to factoring. We emphasize that our results do not expose any specific weakness in the rsa system. [ABSTRACT FROM AUTHOR]

For composite n, we prove that counting the number of points on elliptic curves over the ring Zn is randomly computationally equivalent to factoring n. That is, we prove that if we can count it, we can easily factor n. Furthermore, we also prove that if we can solve the elliptic curve discrete logarithm problem modulo n, we can easily factor n. [ABSTRACT FROM AUTHOR]

A publicly verifiable secret sharing (PVSS) scheme, named by Stadler in [Sta96], is a special VSS scheme in which anyone, not only the shareholders, can verify that the secret shares are correctly distributed. The property of public verifiability is what the first proposed VSS scheme [CGMA85] incorporated but later protocols [GMW87, Fel87, Ped91] failed to include. PVSS can provide some interesting properties in the systems using VSS. For instance, it gives a practical solution to (k, l)-threshold VSS assuming no broadcast channel. Stadler proposed two PVSS protocols: one is as secure as the Decision-Diffie-Hellman problem and the other is not formally discussed about security. This paper presents a practical and provably secure PVSS scheme which is O(¦v¦) times more efficient than Stadler's PVSS schemes where ¦v¦ denotes the size of the secret. It can be incorporated into various cryptosystems based on the factoring and the discrete logarithm to transform them into publicly verifiable key escrow (PVKE) systems. In addition, those key escrow cryptosystems can be easily modified into the verifiable partial key escrow (VPKE) ones with the property of delayed recovery [BG97]. To the best of our knowledge, this is the first realization of a VPKE cryptosystem based on the factoring with the delayed recovery. [ABSTRACT FROM AUTHOR]

In this paper we solve the open problem known as the "software key escrow" problem. To this end we develop a cryptographic notion of auto-recoverable auto-certifiable cryptosystems. We first present the exact specification of the problem, based on what software key escrow can hope to achieve. Then we develop our new scheme, which is an efficient reduction to a software key escrow system from a certified public key system. Namely, our scheme is as efficient for users to use as a public key infrastructure, it does not require a tamper-resistant hardware (i.e., it can be distributed in software to users), and the scheme is shadow public key resistant (does not allow the users to publish public keys other then the ones certified). The scheme enables the efficient verification of the fact that a given user's private key is escrowed properly. [ABSTRACT FROM AUTHOR]

For the most compelling applications of threshold cryptosystems, security against chosen ciphertext attack seems to be a requirement. However, there appear to be no practical threshold cryptosystems in the literature that are provably chosen-ciphertext secure, even in the idealized random hash function model. The contribution of this paper is to present two very practical threshold cryptosystems, and to prove that they are secure against chosen ciphertext attack in the random hash function model. [ABSTRACT FROM AUTHOR]