Search

Let O be a maximal order in a definite quaternion algebra over ℚ of prime discriminant p, and l a small prime. We describe a probabilistic algorithm which, for a given left O-ideal, computes a representative in its left ideal class of l-power norm. In practice the algorithm is efficient and, subject to heuristics on expected distributions of primes, runs in expected polynomial time. This solves the underlying problem for a quaternion analog of the Charles-Goren-Lauter hash function, and has security implications for the original CGL construction in terms of supersingular elliptic curves., SCOPUS: ar.j, info:eu-repo/semantics/published

Hash functions are widely used in cryptography. Recent breakthroughs against the standard SHA-1 prompted NIST to launch a competition for a new secure hash algorithm, SHA-3 [1]. Provably secure hash functions, that is functions whose security reduces to a simply-stated, supposedly hard mathematical problem, are widely believed to be much too slow for the NIST competition. In this paper, we discuss Cayley hashes, a class of efficient and provably secure hash functions constructed from the Cayley graphs of (projective) linear groups. We review two existing constructions, the ZT and LPS hash functions, and put a new one forward, the Morgenstern hash function. We show that Cayley hashes are “provable” and efficient: on one hand, their security reduces to a representation problem in (projective) linear groups; on the other hand, they are only 5 times slower than SHA-2 in FPGA hardware, and about 400 times slower in software (in our future implementations, many optimizations currently under investigation are expected to decrease these gaps even more). Last but not least, Cayley hash computation can be easily parallelized. We believe their nice properties as well as their elegant design make Cayley hashes very interesting hash functions.

We derive an explicit method of computing the composition step in Cantor’s algorithm for group operations on Jacobians of hyperelliptic curves. Our technique is inspired by the geometric description of the group law and applies to hyperelliptic curves of arbitrary genus. While Cantor’s general composition involves arithmetic in the polynomial ring F_q[x], the algorithm we propose solves a linear system over the base field which can be written down directly from the Mumford coordinates of the group elements. We apply this method to give more efficient formulas for group operations in both affine and projective coordinates for cryptographic systems based on Jacobians of genus 2 hyperelliptic curves in general form.

Barreto-Lynn-Scott (BLS) curves are a stand-out candidate for implementing high-security pairings. This paper shows that particular choices of the pairing-friendly search parameter give rise to four subfami- lies of BLS curves, all of which offer highly efficient and implementation- friendly pairing instantiations. Curves from these particular subfamilies are defined over prime fields that support very efficient towering options for the full extension field. The coefficients for a specific curve and its correct twist are automat-ically determined without any computational effort. The choice of an extremely sparse search parameter is immediately reflected by a highly efficient optimal ate Miller loop and final exponentiation. As a resource for implementors, we give a list with examples of implementation-friendly BLS curves through several high-security levels.

Hash functions are an invaluable tool for cryptography. They must primarily satisfy collision resistance, but standardized hash functions like SHA also satisfy stronger properties needed for the wide range of their applications. The design of many hash functions including SHA is based on a compression function that is close to a block cipher and on a domain extension transform like Merkle-Damgård. However, recent attacks against the collision resistance of SHA-1 suggest investigating new designs. The expander hash design, proposed in the early nineties by Zémor and Tillich and recently rediscovered by Charles, Goren and Lauter, consists in defining a cryptographic hash function from an expander graph. The design is simple and elegant and important hash function properties can be interpreted as graph properties. When Cayley expander graphs are used, collision resistance reduces to the hardness of group-theoretical problems. Although these problems are not classical in cryptography, they appear in different forms in other fields and in at least one case, they have remained unbroken since 1994. This thesis studies the expander hash design, its main strengths and weaknesses and the security and efficiency of currently existing instances. We introduce new functions, the Morgenstern hash function and the vectorial and projective versions of the Zémor-Tillich function. We study the security of particular constructions. We present new algorithms breaking the preimage resistance of the LPS hash function and the collision and preimage resistances of the Morgenstern hash function. We improve collision and preimage attacks against Zémor-Tillich and we describe hard and easy components of collision search for this function. We capture the malleability of expander hashes by two definitions of the literature and we describe its positive and negative consequences for applications. We introduce ZesT, an all-purpose hash function based on Zémor-Tillich, keeping its provable collision, (FSA 3) -- UCL, 2009

Collisions in the LPS cryptographic hash function of Charles, Goren and Lauter have been found by Zemor and Tillich, but it was not clear whether computing preimages was also easy for this hash function. We present a probabilistic polynomial time algorithm solving this problem. Subsequently, we study the Morgenstern hash, an interesting variant of LPS hash, and break this function as well. Our attacks build upon the ideas of Zemor and Tillich but are not straightforward extensions of it. Finally, we discuss fixes for the Morgenstern hash function and other applications of our results., Anglais

The authors use the Arf closure relative to divisorial valuations to define an extension of Puiseux exponents for general singularities. Primary exponents come from valuation associated to arc space components. Secondary exponents are related to some Rees valuations.

Elliptic curves with a known number of points over a given prime field with n elements are often needed for use in cryptography. In the context of primality proving, Atkin and Morain suggested the use of the theory of complex multiplication to construct such curves. One of the steps in this method is the calculation of a root modulo n of the Hilbert class polynomial H(X) for a fundamental discriminant D. The usual way is to compute H(X) over the integers and then to find the root modulo n. We present a modified version of the Chinese remainder theorem (CRT) to compute H(X) modulo n directly from the knowledge of H(X) modulo enough small primes. Our complexity analysis suggests that asymptotically our algorithm is an improvement over previously known methods., Comment: 14 pages, complexity analysis redone, several sections rewritten