The Experts below are selected from a list of 2649 Experts worldwide ranked by ideXlab platform

Markus Michels - One of the best experts on this subject based on the ideXlab platform.

  • Separability and Efficiency for Generic Group Signature Schemes
    Advances in Cryptology — CRYPTO’ 99, 1999
    Co-Authors: Jan L Camenisch, MARTIN MICHELS, Markus Michels
    Abstract:

    A cryptographic protocol possesses separability if the participants\ncan choose their keys independently of each other. This is advantageous\nfrom a key-management as well as from a security point of view. This\npaper focuses on separability in group signature schemes. Such schemes\nallow a group member to sign messages anonymously on the group's\nbehalf. However, in case of this anonymity's misuse, a trustee can\nreveal the originator of a signature. We provide a generic fully\nseparable group signature scheme and present an efficient instantiation\nthereof. The scheme is suited for large groups; the size of the group's\npublic key and the length of signatures do not depend on the number\nof group member. Its efficiency is comparable to the most efficient\nschemes that do not offer separability and is an order of magnitude\nmore efficient than a previous scheme that provides partial separability.\nAs a side result, we provide efficient proofs of the equality of\ntwo Discrete Logarithms from different groups and, more general,\nof the validity of polynomial relations in Z among Discrete Logarithms\nfrom different groups.

  • separability and eciency for generic group signature schemes extended abstract
    1999
    Co-Authors: Jan L Camenisch, Markus Michels
    Abstract:

    A cryptographic protocol possesses separability if the par- ticipants can choose their keys independently of each other. This is ad- vantageous from a key-management as well as from a security point of view. This paper focuses on separability in group signature schemes. Such schemes allow a group member to sign messages anonymously on the group's behalf. However, in case of this anonymity's misuse, a trustee can reveal the originator of a signature. We provide a generic fully separa- ble group signature scheme and present an ecient instantiation thereof. The scheme is suited for large groups; the size of the group's public key and the length of signatures do not depend on the number of group member. Its eciency is comparable to the most ecient schemes that do not oer separability and is an order of magnitude more ecient than a previous scheme that provides partial separability. As a side result, we provide ecient proofs of the equality of two Discrete Logarithms from dierent groups and, more general, of the validity of polynomial relations in among Discrete Logarithms from dierent groups.

Leonard M Adleman - One of the best experts on this subject based on the ideXlab platform.

  • function field sieve method for Discrete Logarithms over finite fields
    Information & Computation, 1999
    Co-Authors: Leonard M Adleman, Mingdeh A Huang
    Abstract:

    We present a function field sieve method for Discrete Logarithms over finite fields. This method is an analog of the number field sieve method originally developed for factoring integers. It is asymptotically faster than the previously known algorithms when applied to finite fields Fpn, where p6?n.

  • a subexponential algorithm for Discrete Logarithms over the rational subgroup of the jacobians of large genus hyperelliptic curves over finite fields
    Algorithmic Number Theory Symposium, 1994
    Co-Authors: Leonard M Adleman, Jonathan Demarrais, Mingdeh A Huang
    Abstract:

    There are well known subexponential algorithms for finding Discrete Logarithms over finite fields. However, the methods which underlie these algorithms do not appear to be easily adaptable for finding Discrete Logarithms in the groups associated with elliptic curves and the Jacobians of hyperelliptic curves. This has led to the development of cryptographic systems based on the Discrete logarithm problem for such groups [12, 7, 8]. In this paper a Subexponential algorithm is presented for finding Discrete Logarithms in the group of rational points on the Jacobians of large genus hyperelliptic curves over finite fields. We give a heuristic argument that under certain assumptions, there exists a c e ℜ>0 such that for all sufficiently large g e Z>0, for all odd primes p with log p ≤ (2g + 1).98, the algorithm computes Discrete Logarithms in the group of rational points on the Jacobian of a genus g hyperelliptic curve over GF(p) within expected time: Lp2g+1[1/2, c] where c ≤ 2.181.

  • a subexponential algorithm for Discrete Logarithms over all finite fields
    International Cryptology Conference, 1993
    Co-Authors: Leonard M Adleman, Jonathan Demarrais
    Abstract:

    There are numerous subexponential algorithms for computing Discrete Logarithms over certain classes of finite fields. However, there appears to be no published subexponential algorithm for computing Discrete Logarithms over all finite fields. We present such an algorithm and a heuristic argument that there exists a c ? R > 0 such that for all sufficiently large prime powers pn, the algorithm computes Discrete Logarithms over GF(pn) within expected time: ec(log(pn)log log(pn))1/2.

Michael J Wiener - One of the best experts on this subject based on the ideXlab platform.

  • parallel collision search with cryptanalytic applications
    Journal of Cryptology, 1999
    Co-Authors: Paul C Van Oorschot, Michael J Wiener
    Abstract:

    A simple new technique of parallelizing methods for solving search problems which seek collisions in pseudorandom walks is presented. This technique can be adapted to a wide range of cryptanalytic problems which can be reduced to finding collisions. General constructions are given showing how to adapt the technique to finding Discrete Logarithms in cyclic groups, finding meaningful collisions in hash functions, and performing meet-in-the-middle attacks such as a known-plaintext attack on double encryption. The new technique greatly extends the reach of practical attacks, providing the most cost-effective means known to date for defeating: the small subgroup used in certain schemes based on Discrete Logarithms such as Schnorr, DSA, and elliptic curve cryptosystems; hash functions such as MD5, RIPEMD, SHA-1, MDC-2, and MDC-4; and double encryption and three-key triple encryption. The practical significance of the technique is illustrated by giving the design for three $10 million custom machines which could be built with current technology: one finds elliptic curve Logarithms in GF(2155) thereby defeating a proposed elliptic curve cryptosystem in expected time 32 days, the second finds MD5 collisions in expected time 21 days, and the last recovers a double-DES key from two known plaintexts in expected time 4 years, which is four orders of magnitude faster than the conventional meet-in-the-middle attack on double-DES. Based on this attack, double-DES offers only 17 more bits of security than single-DES.

  • parallel collision search with application to hash functions and Discrete Logarithms
    Computer and Communications Security, 1994
    Co-Authors: Paul C Van Oorschot, Michael J Wiener
    Abstract:

    Current techniques for collision search with feasible memory requirements involve pseudo-random walks through some space where one must wait for the result of the current step before the next step can begin. These techniques are serial in nature, and direct parallelization is inefficient. We present a simple new method of parallelizing collision searches that greatly extends the reach of practical attacks. The new method is illustrated with applications to hash functions and Discrete Logarithms in cyclic groups. In the case of hash functions, we begin with two messages; the first is a message that we want our target to digitally sign, and the second is a message that the target is willing to sign. Using collision search adapted for hashing collisions, one can find slightly altered versions of these messages such that the two new messages give the same hash result. As a particular example, a $10 million custom machine for applying parallel collision search to the MD5 hash function could complete an attack with an expected run time of 24 days. This machine would be specific to MD5, but could be used for any pair of messages. For Discrete Logarithms in cyclic groups, ideas from Pollard's rho and lambda methods for index computation are combined to allow efficient parallel implementation using the new method. As a concrete example, we consider an elliptic curve cryptosystem over GF (2 155 ) with the order of the curve having largest prime factor of approximate size 10 36 . A $10 million machine custom built for this finite field could compute a Discrete logarithm with an expected run time of 36 days.

Mingdeh A Huang - One of the best experts on this subject based on the ideXlab platform.

  • function field sieve method for Discrete Logarithms over finite fields
    Information & Computation, 1999
    Co-Authors: Leonard M Adleman, Mingdeh A Huang
    Abstract:

    We present a function field sieve method for Discrete Logarithms over finite fields. This method is an analog of the number field sieve method originally developed for factoring integers. It is asymptotically faster than the previously known algorithms when applied to finite fields Fpn, where p6?n.

  • a subexponential algorithm for Discrete Logarithms over the rational subgroup of the jacobians of large genus hyperelliptic curves over finite fields
    Algorithmic Number Theory Symposium, 1994
    Co-Authors: Leonard M Adleman, Jonathan Demarrais, Mingdeh A Huang
    Abstract:

    There are well known subexponential algorithms for finding Discrete Logarithms over finite fields. However, the methods which underlie these algorithms do not appear to be easily adaptable for finding Discrete Logarithms in the groups associated with elliptic curves and the Jacobians of hyperelliptic curves. This has led to the development of cryptographic systems based on the Discrete logarithm problem for such groups [12, 7, 8]. In this paper a Subexponential algorithm is presented for finding Discrete Logarithms in the group of rational points on the Jacobians of large genus hyperelliptic curves over finite fields. We give a heuristic argument that under certain assumptions, there exists a c e ℜ>0 such that for all sufficiently large g e Z>0, for all odd primes p with log p ≤ (2g + 1).98, the algorithm computes Discrete Logarithms in the group of rational points on the Jacobian of a genus g hyperelliptic curve over GF(p) within expected time: Lp2g+1[1/2, c] where c ≤ 2.181.

Antoine Joux - One of the best experts on this subject based on the ideXlab platform.

  • Nearly Sparse Linear Algebra
    2016
    Co-Authors: Antoine Joux
    Abstract:

    Abstract. In this article, we propose a method to perform linear alge-bra on a matrix with nearly sparse properties. More precisely, although we require the main part of the matrix to be sparse, we allow some dense columns with possibly large coefficients. We modify Block Wiedemann algorithm and show that the contribution of these heavy columns can be made negligible compared to the one of the sparse part of the ma-trix. In particular, this eases the computation of Discrete Logarithms in medium and high characteristic finite fields, where nearly sparse matrices naturally appear

  • the function field sieve in the medium prime case
    Lecture Notes in Computer Science, 2006
    Co-Authors: Antoine Joux
    Abstract:

    In this paper, we study the application of the function field sieve algorithm for computing Discrete Logarithms over finite fields of the form F q n when q is a medium-sized prime power. This approach is an alternative to a recent paper of Granger and Vercauteren for computing Discrete Logarithms in tori, using efficient torus representations. We show that when q is not too large, a very efficient L(1/3) variation of the function field sieve can be used. Surprisingly, using this algorithm, Discrete Logarithms computations over some of these fields are even easier than computations in the prime field and characteristic two field cases. We also show that this new algorithm has security implications on some existing cryptosystems, such as torus based cryptography in T 30 , short signature schemes in characteristic 3 and cryptosystems based on super-singular abelian varieties. On the other hand, cryptosystems involving larger basefields and smaller extension degrees, typically of degree at most 6, such as LUC, XTR or T 6 torus cryptography, are not affected.

  • improvements to the general number field sieve for Discrete Logarithms in prime fields a comparison with the gaussian integer method
    Mathematics of Computation, 2003
    Co-Authors: Antoine Joux, Reynald Lercier
    Abstract:

    In this paper, we describe many improvements to the number field sieve. Our main contribution consists of a new way to compute individual Logarithms with the number field sieve without solving a very large linear system for each logarithm. We show that, with these improvements, the number field sieve outperforms the gaussian integer method in the hundred digit range. We also illustrate our results by successfully computing Discrete Logarithms with GNFS in a large prime field.

  • the weil and tate pairings as building blocks for public key cryptosystems
    Algorithmic Number Theory Symposium, 2002
    Co-Authors: Antoine Joux
    Abstract:

    Elliptic curves were first proposed as a tool for cryptography by V. Miller in 1985 [29]. Indeed, since elliptic curves have a group structure, they nicely fit as a replacement for more traditional groups in Discrete logarithm based systems such as Diffie-Hellman or ElGamal. Moreover, since there is no non-generic algorithm for computing Discrete Logarithms on elliptic curves, it is possible to reach a high security level while using relatively short keys.