Boaz Tsaban - Workshop on Secure Implementation of Post-Quantum Cryptography in Israel

Nonabelian cryptosystems, for a change?

Abstract:

Many years passed since the introduction of public key cryptography and still, very few public key cryptosystems are widely believed to be secure. Basically, these are the PKCs based on DH, the closely-related RSA, and Lattices. These trusted PKCs are all based on operations in abelian (commutative) groups. 

The world of nonabelian groups is much wider and richer in computational problems than that of abelian ones. Around the beginning of the present Millenium, attempts have been made to base PKCs on nonabelian groups (and related structures). These attempts have mostly failed. Why?

I am an enthusiast of the potential of nonabelian structures in crypto, my belief is that serious cryptanalysis is necessary for gaining intuition on the promising directions. I have succeeded, with coauthors, cryptanalysing many of the proposals, and in a structural way that makes it possible for PKC designers to check some of their own proposals before releasing them.

I will discuss the methods that I developed with collaborators, and perhaps discuss my opinions on the potential of nonabelian crypto. E.g.:

  1. Serious lack of manpower (equivalently, grants).
  2. Presently, almost only mathematicians consider this directions. Cryptographers need to enter the field in order to bring the proposals to the standards common in crypto (this implies (2)).
  3. Proposals are usually made in a raw stage, prior to serious cryptanalysis. This gives the approach a bad reputation (this implies (0)).
  4. Maybe there is some big phenomenon lurking, that makes it possible to reduce the relevant nonabelian problems to abelian ones (a la Babai et al.) (And maybe not.)

I will, however, mention a very elegant nonabelian cryptographic primitive that resisted all cryptanalytic efforts (mine and many others). It has a worst case to average reduction, and performance-wise, it compares favorably with provable lattice-based candidates.