CiteULike: Group: Crypto - library [1413 articles]

Bridging and Fingerprinting: Epistemic Attacks on Route Selection

George Danezis — 2008-06-27T14:51:40-00:00

Elementary Number Theory

Gareth Jones — 2008-01-15T16:18:19-00:00

(31 July 1998)

This book gives an undergraduate-level introduction to Number Theory, with the emphasis on fully explained proofs and examples; exercises (with solutions) are integrated into the text. The first few chapters, covering divisibility, prime numbers and modular arithmetic, assume only basic school algebra, and are therefore suitable for first or second year students as an introduction to the methods of pure mathematics. Elementary ideas about groups and rings (summarised in an appendix) are then used to study groups of units, quadratic residues and arithmetic functions with applications to enumeration and cryptography. The final part, suitable for third-year students, uses ideas from algebra, analysis, calculus and geometry to study Dirichlet series and sums of squares; in particular, the last chapter gives a concise account of Fermat's Last Theorem, from its origin in the ancient Babylonian and Greek study of Pythagorean triples to its recent proof by Andrew Wiles.

Finite metric spaces--combinatorics, geometry and algorithms

Nathan Linial — 2005-05-18T08:55:48-00:00

(28 April 2003)

Finite metric spaces arise in many different contexts. Enormous bodies of data, scientific, commercial and others can often be viewed as large metric spaces. It turns out that the metric of graphs reveals a lot of interesting information. Metric spaces also come up in many recent advances in the theory of algorithms. Finally, finite submetrics of classical geometric objects such as normed spaces or manifolds reflect many important properties of the underlying structure. In this paper we review some of the recent advances in this area.

Generatingfunctionology

Herbert Wilf — 2005-11-29T15:03:17-00:00

This is the Second Edition of the highly successful introduction to the use of generating functions and series in combinatorial mathematics. This new edition includes several new areas of application, including the cycle index of the symmetric group, permutations and square roots, counting polyominoes, and exact covering sequences. An appendix on using the computer algebra programs MAPLE(r) and Mathematica(r) to generate functions is also included. The book provides a clear, unified introduction to the basic enumerative applications of generating functions, and includes exercises and solutions, many new, at the end of each chapter. Key Features * Provides new applications on the cycle index of the symmetric group, permutations and square roots, counting polyominoes, and exact covering sequences * Features an Appendix on using MAPLE(r) and Mathematica (r) to generate functions * Includes many new exercises with complete solutions at the end of each chapter

On Picture-Writing

G Polya — 2007-04-23T14:56:12-00:00

The American Mathematical Monthly, Vol. 63, No. 10. (1956), pp. 689-697.

Projection Learning

Leslie Valiant — 2007-03-22T18:23:40-00:00

Machine Learning, Vol. 37, No. 2. (1 November 1999), pp. 115-130.

Elementary Number Theory

João Ferreira — 2007-03-05T10:08:00-00:00

(2007)

Recounting the Rationals

Neil Calkin — 2007-02-26T11:45:41-00:00

The American Mathematical Monthly, Vol. 107, No. 4. (2000), pp. 360-363.

Limits on the provable consequences of one-way permutations

R Impagliazzo — 2007-02-07T16:39:17-00:00

(1989), pp. 44-61.

We present strong evidence that the implication, "if one-way permutations exist, then secure secret key agreement is possible" is not provable by standard techniques. Since both sides of this implication are widely believed true in real life, to show that the implication is false requires a new model. We consider a world where dl parties have access to a black box or a randomly selected permutation. Being totally random, this permutation will be strongly oneway in provable,...

Enumerating the Rationals

Jeremy Gibbons — 2007-02-01T13:56:20-00:00

(2006)

We present a series of lazy functional programs for enumerating the rational numbers without duplication, drawing on some elegant results of Neil Calkin, Herbert Wilf and Moshe Newman.

Algebraic algorithms in GF(q)

J Calmet — 2007-01-10T13:14:05-00:00

Discrete Mathematics, Vol. 56, No. 2-3. (October 1985), pp. 101-109.

This talk reports on joint work with R. Loos (Univ. Karlsruhe) on algebraic algorithms for computing in large Galois Fields GF(q) with Q = pn where p is the characteristic of the field and may be arbitrarily large.This work is materialized by a module of algorithms implemented in the ALDES/SAC2 computer algebra system, which will be available with the next release of this system.

Indifferentiability of Single-Block-Length and Rate-1 Compression Functions

Hidenori Kuwakado — 2007-01-08T09:22:20-00:00

ePrint (2007)

The security notion of indifferentiability was proposed by Maurer, Renner, and Holenstein in 2004. In 2005, Coron, Dodis, Malinaud, and Puniya discussed the indifferentiability of hash functions. They showed that the Merkle-Damgaard construction is not secure in the sense of indifferentiability. In this paper, we analyze the security of single-block-length and rate-1 compression functions in the sense of indifferentiability. We formally show that all single-block-length and rate-1 compression functions, which include the Davies-Meyer compression function, are insecure. Furthermore, we show how to construct a secure single-block-length and rate-1 compression function in the sense of indifferentiability. This does not contradict our result above.

Computing the Algebraic Immunity Efficiently

Frã©dã©ric Didier — 2007-01-05T18:19:18-00:00

: Fast Software Encryption (2006), pp. 359-374.

Inverting HFE Is Quasipolynomial

Louis Granboulan — 2007-01-05T17:57:33-00:00

: Advances in Cryptology - CRYPTO 2006 (2006), pp. 345-356.

The Inverse S-Box, Non-linear Polynomial Relations and Cryptanalysis of Block Ciphers

Nicolas Courtois — 2007-01-05T15:59:53-00:00

: Advanced Encryption Standard â AES (2005), pp. 170-188.

A Zero-Dimensional Groebner Basis for AES-128

Johannes Buchmann — 2007-01-05T14:11:02-00:00

: Fast Software Encryption (2006), pp. 78-88.

The calculational method

2006-12-31T19:53:27-00:00

Inf. Process. Lett., Vol. 53, No. 3. (10 February 1995)

Exercises in Quantifier Manipulation

Roland Backhouse — 2006-12-31T19:47:01-00:00

Mathematics of Program Construction (2006), pp. 69-81.

Mathematics with a little bit of logic: Structured derivations in high-school mathematics

Ralph-Johan Back — 2006-12-31T19:44:15-00:00

A Browsable Format for Proof Presentation

Jim Grundy — 2006-12-31T19:40:50-00:00

(1996)

Doing High School Mathematics Carefully

Ralph-Johan Back — 2006-12-31T19:38:40-00:00

(1997)

Algorithmic Problem Solving (Draft book)

Roland Backhouse — 2006-12-31T19:16:33-00:00

(2006)

An axiomatic basis for computer programming

CAR Hoare — 2005-04-19T01:26:16-00:00

Commun. ACM, Vol. 12, No. 10. (October 1969), pp. 576-580.

Introducing a new variant of fast algebraic attacks and minimizing their successive data complexity

Frederik Armknecht — 2006-12-23T10:06:31-00:00

(2005)

Comparison Between XL and Groebner Basis Algorithms

Gwã©nolã© Ars — 2006-12-23T08:39:09-00:00

: Advances in Cryptology - ASIACRYPT 2004 (2004), pp. 338-353.

Why you cannot even hope to use Gröbner Bases in Public Key Cryptography - An open letter to a scientist who failed and a challenge to those who have not yet failed

Boo Barkee — 2006-12-23T08:22:16-00:00

BWK]). One has an ideal I ae k[X 1 ; : : : ; Xn ] (where k is a field) and a well-ordering compatible with product on the semigroup T of terms (monic monomials) in k[X 1 ; : : : ; Xn ]. This ordering allows to represent uniquely each f 2 k[X 1 ; : : : ; Xn ] as an ordered linear combination of elements of T: f = r X i=1 c i t i c i 2 k n f0g; t i 2 T; t 1 ? Δ Δ Δ ? t r so to each non-zero element f 2 k[X 1 ; : : : ; Xn ], we can associate T

Groebner-Bases, Gaussian elimination and resolution of systems of algebraic equations

Daniel Lazard — 2006-12-22T17:00:45-00:00

(1983), pp. 146-156.

Asymptotic Behaviour of the Index of Regularity of Quadratic Semi-Regular Polynomial Systems

M Bardet — 2006-12-22T16:52:14-00:00

(2005)

We compute the asymptotic expansion of the index of regularity for overdetermined quadratic semi-regular sequences of algebraic equations. This implies bounds for the generic complexity of Grobner bases algorithms, in particular the F5 [Fau02] algorithm. Bounds can also be derived for the XL [SPCK00] family of algorithms used by the cryptographic community.

Projective Aspects of the AES Inversion

Wen-Ai Jackson — 2006-12-05T10:08:25-00:00

(2006)

CTRU, a polynomial analogue of NTRU

Philippe Gaborit — 2006-12-03T09:03:01-00:00

CTRU, a new public-key cryptosystem is introduced. In this analogue of NTRU, the ring of integers is replaced by the ring of polynomials in one variable over a finite field. Attacks based on either the LLL algorithm or the Chinese Remainder Theorem are avoided. An important tool of cryptanalys- is is the Popov normal form of matrices with polynomial entries. The speed of encryption/decryption of CTRU is the same as NTRU for the same value of N. An implementation in Aldor is described.

Algebraic Immunities of functions over finite fields

Gwénolé Ars — 2006-12-03T09:01:16-00:00

A general mathematical definition for a function from $GF(q)^n$ to $GF(q)^m$ to resist to cryptanalytic attacks is developed. It generalize the definition of Algebraic Immunity for Stream Cipher to any finite field and also Block Cipher. This algebraic immunity correspond to equations with low leading term according a monomial ordering. We give properties of this Algebraic Immunity and also compute explicit and asymptotic bounds. We extended the definitions of Algebraic Immunity to functions with memory but they depend on the number of consecutive outputs we look at. We show that all the results obtained for memoryless function give similarly results on memory functions by a change of variables. And then, we prove that, for a memory function f with memory size l and only one output, if there is no relation which not depend on memory for l consecutive output, than we can construct a polynomial that generate all relations without memories. We apply this theorem to the summation generator and compute explicitly the Algebraic Immunity.

Complexity of Gröbner basis computation for Semi-regular Overdetermined sequences over F_2 with solutions in F_2

Magali Bardet — 2006-12-03T08:59:56-00:00

We present complexity results for solving "typical"overdetermined algebraic systems over GF(2) with solutions in GF(2) using Gröbner bases. They are useful for instance to predictthe complexity of an algebraic cryptanalysis over a cryptosystem,they give a priori upper bounds. We define semi-regularsequ ences and their associated notion of degree of regularity Dreg.The motivation for studying semi-regular sequences is that"random" sequences are semi-regular, and Dreg is closely related tothe global cost of the Gröbner basis computation for a gradedadmissible monomial order. Using inparticular the F5 Gröbner basis algorithm, we show that forsemi-regular sequences the behavior of F5 (in a matrix version)can be followed step by step, and the size of all matrices madeexplicit. We deduce Dmax, and using asymptotic analysis methodswe compute its asymptotic expansion. We give many explicitexamples, and discuss the complexity of the global arithmeticcost of the Gröbner basis computation for m quadratic equations in n variables: for m=N n with N constant, the computationis exponential, if n<<m<<n^2 the computation is sub-exponentialand for m=N n^2, with N a constant, thecomplexity is O(n^2,n^(1/8 N)) which is polynomial. Thisclassification gives "generic upper bounds", and thus a prioriupper bounds for many cryptosystems.

An Algebraic Cryptanalysis of Nonlinear Filter Generators using Gröbner bases

Jean-Charles Faugere — 2006-12-03T08:58:56-00:00

This paper presents an algebraic cryptanalysis of nonlinear filter generator. A linear shift register of length L filtered by a non linear boolear function f of degree deg(f) is equivalently described by a set of algebraic equations. More precisely, if N is the size of given output bits then we have a system of N algebraic equations of total degree deg(f) in L variables. By solving this system of equations we can recover all the possible initial state (the secret key) of the device . Gröbner is precisely an efficient tool for solving algebraic systems. Recently, very efficient algorithms (F_5 ) have been proposed which are several order of magnitude faster than the historical Buchberger algorithm. We show that with only a polynomial number of output bits we can recover in polynomial time the initial state. More precisely we can show that is enough to have (L^d) output bits with d where k is the number of variables of the filtering function. Surprisingly, for all the stream ciphers satisfying Golic's design criteria and filtering functions found in literature we found that d is much less than the predicted bound: for instance the Lili is of degree 6 but a simple Gröbner computations shows that it behaves like a degree 4 function. Even more surprisingly, we show experimentally that for some examples we can recover the initial state in polynomial time with only L + output bits. Different attacks have been implemented, and we give a list of timing experimented on many real size size (L80 bits) stream ciphers

Algebraic cryptanalysis of HFE using Gröbner bases

Jean-Charles Faugere — 2006-12-03T08:57:49-00:00

HFE (Hidden Fields Equations) is a public key cryptosystem using (multivariat- e) polynomial operations over finite fields. It has been proposed by Jacques Patarin following the ideas of Matsumoto and Imai. In this paper we present a new and efficient attack of this cryptosystem based on fast algorithms for computing Gröbner basis. The attack consists simply in computing a Gröbner basis of the public key. Of course the efficiency of this attack depends strongly on the choice of the algorithm for computing the Gröbner basis: while the corresponding algebraic systems are completely far beyond the capacity of any implementation of the Buchberger algorithm, it was was possible to break the first HFE challenge (80 bits) in only two days of CPU time by using the new algorithm F5 implemented in C. We establish experimentally that the algebraic systems coming from HFE behave not as «random systems» so that they can be solved in polynomial time when the degree d of the univariate polynomial is fixed. For practical value of d we can establish precisely the complexity of this attack: O(n^8) (resp. O(n^10)) when 16<d<128 (resp. 128<d<513).

Cryptanalysis of block ciphers

Alex Biryukov — 2006-11-28T10:01:54-00:00

On the complexity of Gröbner basis computation of semi-regular overdetermined algebraic equations

Magali Bardet — 2006-11-28T09:59:22-00:00

We extend the notion of regular sequence ([Mac16]) to overdetermined system of algebraic equations. We study generic properties of Gröbner bases and analyse precisely the behavior of the F5 [Fau02] algorithm. Sharp asymptotic estimates of the degree of regularity are given.

Hash Functions: Past, Present and Future

Bart Preneel — 2006-11-28T09:57:39-00:00

An Analysis of the XSL Algorithm

Carlos Cid — 2006-11-28T09:52:51-00:00

Lecture Notes in Computer Science : Advances in Cryptology - ASIACRYPT 2005 (2005), pp. 333-352.

Cryptanalytic Time/Memory/Data Tradeoffs for Stream Ciphers

Alex Biryukov — 2006-11-28T09:50:39-00:00

Lecture Notes in Computer Science : Advances in Cryptology - ASIACRYPT 2000: 6th International Conference on the Theory and Application of Cryptology and Information Security, Kyoto, Japan, December 2000. Proceedings (2000), 1.

On the Existence of low-degree Equations for Algebraic Attacks

Frederik Armknecht — 2006-11-28T09:47:02-00:00

Algebraic attacks on block ciphers and stream ciphers have gained more and more attention in cryptography. The idea is to express a cipher by a system of equations whose solution reveals the secret key. The complexity of an algebraic attack is closely related to the degree of the equations. Hence, low-degree equations are crucial for algebraic attacks. So far, the existence of low-degree equations for simple combiners, combiners with memory and S-boxes was treated independently. In this paper,...

Decorrelation: A Theory for Block Cipher Security

Serge Vaudenay — 2006-11-28T09:40:57-00:00

Pseudorandomness is a classical model for the security of block ciphers. In this paper we propose convenient tools in order to study it in connection with the Shannon Theory, the Carter-Wegman universal hash functions paradigm, and the Luby-Rackoff approach. This enables the construction of new ciphers with security proofs under specic models. We show how to ensure security against basic differential and linear cryptanalysis and even more general attacks. We propose practical construction schemes.

The Two Faces of Lattices in Cryptology

Phong Nguyen — 2006-11-27T14:37:56-00:00

Lecture Notes in Computer Science, Vol. 2146 (2001), pp. 146-??.

Lattices are regular arrangements of points in n-dimensional space, whose study appeared in the 19th century in both number theory and crystallography. Since the appearance of the celebrated LenstraLenstra -Lov'asz lattice basis reduction algorithm twenty years ago, lattices have had surprising applications in cryptology. Until recently, the applications of lattices to cryptology were only negative, as lattices were used to break various cryptographic schemes. Paradoxically, several...

Block Ciphers and Systems of Quadratic Equations

Alex Biryukov — 2006-11-22T12:39:24-00:00

Lecture Notes in Computer Science : Fast Software Encryption (2003), pp. 274-289.

Analysis and Design of Modern Stream Ciphers

Thomas Johansson — 2006-11-22T12:38:17-00:00

Lecture Notes in Computer Science : Cryptography and Coding (2003), pp. 66-66.

An Algebraic Masking Method to Protect AES Against Power Attacks

Nicolas Courtois — 2006-11-22T12:37:46-00:00

Lecture Notes in Computer Science : Information Security and Cryptology - ICISC 2005 (2006), pp. 199-209.

Algebraic Cryptanalysis of Hidden Field Equation (HFE) Cryptosystems Using GrÃ¶bner Bases

Jean-Charles Faugere — 2006-11-22T12:34:54-00:00

Lecture Notes in Computer Science : Advances in Cryptology - CRYPTO 2003 (2003), pp. 44-60.

Algebraic Attacks over GF( q)

Lynn Batten — 2006-11-22T12:34:16-00:00

Lecture Notes in Computer Science : Progress in Cryptology - INDOCRYPT 2004 (2004), pp. 84-91.

Algebraic Attacks on Summation Generators

Dong Lee — 2006-11-22T12:33:49-00:00

Lecture Notes in Computer Science : Fast Software Encryption (2004), pp. 34-48.

Algebraic Attacks on SOBER-t32 and SOBER-t16 without Stuttering

Joo Cho — 2006-11-22T12:33:24-00:00

Lecture Notes in Computer Science : Fast Software Encryption (2004), pp. 49-64.

Algebraic Attacks on Clock-Controlled Stream Ciphers

Sultan Al-Hinai — 2006-11-22T12:32:31-00:00

Lecture Notes in Computer Science : Information Security and Privacy (2006), pp. 1-16.