Non-Abelian Groups as Candidate Platform for Cryptographic Schemes: Strengths and Weaknesses Rainer Steinwandt Florida Atlantic University Non-abelian groups in cryptography: Why? … besides being academic fun: • desire for new hardness assumptions (not amenable to known quantum algorithms) • desire for performance improvements (e.g., smaller signatures, faster encryption) Other promising candidates exist, incl. • Lattices (→ NTRU) • Multivariate Cryptography (→ SFLASH) … current state – a pragmatic view • many proposals for encryption, signing, key establishment, … using non-abelian groups have been made • most suggestions that were specified in detail have been attacked successfully hardly any non-abelian proposal available that is accepted as practical and secure What is a cryptographic scheme? Common problems in “non-abelian proposals”: • lack of clearly specified assumptions & goals security model unclear • available cryptographic tools & attack models not taken into account • lack of formal rigor “attacks w/o mathematical value” Example: public key encryption Established minimum requirement: indistinguishable encryptions under chosen plaintext attacks (with proof!) … or be more efficient than the others ☺ • encrypt one bit at a time • “sufficiently complicated” instances • hard to find plaintext from ciphertext MST revisited 1 • introduced as public key encryption scheme • no security proof • no secure key generation known … could yield trapdoor one-way perm. from a group-theoretical problem combination with known cryptographic constructions could yield a “real scheme” Logarithmic signatures of finite groups G a finite group, A , ..., A ⊆ G with G =A ·...·A . 1 s 1 s Then [A , ..., A ] is a logarithmic signature 1 s for G :⇔ each g ∈ G has a unique factorization g = a ·...·a with a ∈ A . 1 s i i Ex.: For a subgroup chain G = G > G >... > G ={id} 0 1 s choose A as left transversal of G mod G i i−1 i The trouble with the instances… MST needs log. signatures Λ so that factoring 1 w.r.t. Λ needs knowledge of trapdoor Z/|G|Z [A ,..., A ] G [B , ..., B ] Z/|G|Z 1 s 1 t mixed basis mixed basis multiply factor represent. represent. n (a , ..., a ) g (b , ..., b ) f (n) 1 s 1 t ... unclear how to generate these reliably (cf. key generation trouble w/ conjugacy & root problem in braid groups) Symmetric cryptography & group theory • For PGM, “a symmetric MST ”, things look 1 better: successful cryptanalysis lacking • Tillich-Zémor hash function from CRYPTO 94 “structurally unbroken” for n prime: 1.) Fix GF(2n)=GF(2)[X]/(f(X)) 2.) For α a root of f(X), set α 1 α α+1 B := , B := ∈ SL (GF(2n)) 0 1 2 1  1 1 0 3.) Hash value of m∈{0,1}* : H(m):=∏ B i i Getting constructive… • Alternative to constructing complete group- based cryptographic scheme from scratch: Provable reduction of, e.g., IND-CCA2 security to group-theoretical assumption ( Cramer-Shoup-like construction). - possibly no efficient instance known + you know what you need & get