Cryptology and Graph Theory
Jean-Jacques Quisquater
[email protected] November 16, 2005 http://www.uclcrypto.org Mierlo, Netherlands
Warning: Audience may be addicted by Powerpoint. Use with moderation. © UCL Crypto group, a member of EIDMA. November 2005
Menu • • • • • • • •
Cryptology Large graphs and cryptology Cayley graphs Expanders (SL(2,p)) Hash function (Zémor-Tillich) Generating Sm, Am Research No conclusion © UCL Crypto group, a member of EIDMA. November 2005
2
Cryptology • Confidentiality, integrity, identification (design and attacks: cryptography and cryptanalysis) • Integrity: send a message M with an added information for detection of change • Detection or correction codes if noise • Cryptographic hash function h(), value protected by signature, if malicious context • Hash function: given h(M), difficult to find another message with same value h(M): other definitions
© UCL Crypto group, a member of EIDMA. November 2005
3
• MD4, MD5, SHA-0, … « broken » (August 2004) • See program codes in http://www.stachliu.com.nyud.net:8090/collisions.html
• SHA-1 (random collision in 263 computations) • State-of-the-art at http://www.csrc.nist.gov/pki/HashWorkshop/program.htm
October 31-November 1st, 2005 • Confidence in others?
© UCL Crypto group, a member of EIDMA. November 2005
4
Large graphs and Cryptology • Protocols: graph isomorphism (theoretical, pedagogical, not efficient) • Primitives for integrity: Zémor-Tillich fonction (Eurocrypt’91, Crypto’94) • Attacks: use of expanders • Proofs of security: use of expanders • Physical distribution of secrets: (delta-D)-graphs (Q., 1998), Cayley graphs © UCL Crypto group, a member of EIDMA. November 2005
5
Cayley graphs (1) • Generator set A • Generated group G • Graph: – group elements as vertices – edges defined by generators
© UCL Crypto group, a member of EIDMA. November 2005
a3
a
a
1
a2 a
a
a
group elements
generators
6
Cayley graphs (2)
© UCL Crypto group, a member of EIDMA. November 2005
7
Expander (1) • Graph G with n vertices (often fixed degree) • All subsets of k nodes have at least βk neighboring vertices • Expanding constant (isoperimetric constant)
© UCL Crypto group, a member of EIDMA. November 2005
8
Expander (2) • (condensers, extractors, (super)concentrators…), • Many applications: – Circuit complexity, randoms, communications, cryptography, data structures …
• Pure mathematics: topology, group theory, measure theory, number theory, graph theory, …
© UCL Crypto group, a member of EIDMA. November 2005
9
Ramanujan graph
© UCL Crypto group, a member of EIDMA. November 2005
10
Computing the expanding constant • Explicit: difficult but very interesting results • Specific: complete graphs, cycles, … • Cayley graphs • Eigenvalue computations: the best ones today (related to random walks)
© UCL Crypto group, a member of EIDMA. November 2005
11
SL(2,p) (example) • •
Group of invertible matrices with determinant 1 Operations modulo p
A=
⎛1 2⎞ ⎜⎜ ⎟⎟ ⎝0 1⎠
B=
⎛ 1 0⎞ ⎜⎜ ⎟⎟ ⎝ 2 1⎠
A, B generate a group, described by a Cayley graph
© UCL Crypto group, a member of EIDMA. November 2005
12
Hash function based on SL(2,p) (Zemor-Tillich: 1994) • •
Group of invertible matrices with determinant 1 Operations modulo p
A=
⎛1 2⎞ ⎜⎜ ⎟⎟ ⎝0 1⎠
B=
⎛ 1 0⎞ ⎜⎜ ⎟⎟ ⎝ 2 1⎠
= A or B if i = 0 or 1 M = m0m1m2…ml-2ml-1
i C
Cm0Cm1Cm2…Cml-2Cml-1 = h(M) © UCL Crypto group, a member of EIDMA. November 2005
13
Security • NB: associativity (no other hash functions like this) • (Close to cascades (Delsarte-Q., 1974)) • Length of h(M) constant (independent of M) • NP-complete problem (representation of an element of a group given a set of generators) • Cayley graph • p with 500 bits or more (large graphs!) © UCL Crypto group, a member of EIDMA. November 2005
14
• Girth (collision): partial proof of security (maille, tour de taille): other examples: VSH (Contini, A. Lenstra, Stenfield, based on factorization) and also expanders (Charles, Goren and Lauter, 2005) • Diameter of the graph (not too large): and if expander good random walks • Not very efficient (one bit as exponent) • Construction similar to expanders based on Cayley graphs (Ramanujan graphs, …) © UCL Crypto group, a member of EIDMA. November 2005
15
Secure camcoder: Joye-Q.:JCS, 1997 • • • •
Integrity of forms (precomputation) Signatures of sequences Postprocessing of videos (authenticity) Efficiency (?) and easy use thanks to associativity
© UCL Crypto group, a member of EIDMA. November 2005
16
Better? (1) • Ci = A or B if i = 0 or 1 • Binary -> n-ary • Cayley graphs generated by n generators • (associativity) • Other groups: well known? • Symmetric groups, alternating groups (all or all even permutations on m elements)? © UCL Crypto group, a member of EIDMA. November 2005
17
Better? (2) • Generating symmetric groups Sm • Easy?: « any » 2 random elements from Sm generate Sm with high probability (Dixon, 1969) • Choice related to girth and diameter (security) • BUT not so many results
© UCL Crypto group, a member of EIDMA. November 2005
18
Research (Q., 2004) • Choice n generators generating Sm, Am, with good diameter and girth • Expanders? • Done: family of n generators (n in 2 …log(m) ... m) with good diameter, with good algorithm of representation (oops!) • Girth? • Subgroups?
© UCL Crypto group, a member of EIDMA. November 2005
19
Group generations • • • •
Few results if optimal in complexity Golunkov (1971) Babai, Kantor (1988) JJQ (1983, 1987, 2004, …)
© UCL Crypto group, a member of EIDMA. November 2005
20
Group generations (applications) • Gluskov automaton (1965): • Cellular logic (Elspas, Stone, 1968 …): • Cryptographic algos (modelling by finite lossless automata): Huffman (1955), Kurmit (1974), • Analog scrambling: Wyner (1975), Sloane (1982), • Random access memory: Stone, Aho-Ullmann, • Access to databases (Klugge, 1977) • Bubble memories (aso), • Random generators (Luby-Rackoff, 1986), • Criteria for Feistel schemes (Even-Goldreich, 1981), • (Bill Gates) …
© UCL Crypto group, a member of EIDMA. November 2005
21
Symmetric groups Sn • Pick at random an element (permutation): cycle structure? Goncharov(1942-1944), Knuth-Pardo (1976), • Pick at random 2 or more elements: proba of generating S: Netto (1892), Dixon (1969), • Diameter, girth? • Cayley graphs
© UCL Crypto group, a member of EIDMA. November 2005
22
Results • Easy and flexible constructions of sets of generators for Sm and Am • Very diameter (close to lower bound) • 2, 3, …, log(log(m)), … log(m), … generators (except few cases) • Hamiltonian paths • Bipartite graphs • (too) easy computation of paths from 0 © UCL Crypto group, a member of EIDMA. November 2005
23
Coming back to expanders • Such graphs are « good » expanders • Need of a seed graph in an iterative context (Wigderson et al, 2004) • …
© UCL Crypto group, a member of EIDMA. November 2005
24
Conclusions • • • •
Hash functions? Interesting results anyway Thanks for your interest Questions, answers, comments?
© UCL Crypto group, a member of EIDMA. November 2005
25