2
$\begingroup$

Shannon said that every cryptosystem can be expressed as a system of linear equations with a large number of unknowns of complex type. In cryptography groups are used since they are a natural representation of objects that satisfy known relations, this let us to build cryptosystem based on these relations that maintain the scalability when using a decent amount of resources.

Since representation theory is used to represent groups in linear algebra, the aforementioned relations can be also expressed in terms of linear algebra. This theory can lead to representation of cryptosystems as a matrix algebra, thus a system of linear equations can be build to express the cryptosystem's operations.

Q: Is it necessary to study representation theory to analyze cryptosystems based on group theory?

Q: If representation theory is not the point behind group-based cryptanalysis, then what techniques are used here?

$\endgroup$
  • 2
    $\begingroup$ Would the downvoter mind to explain why my question deserves a negative vote? $\endgroup$ – kub0x Oct 12 '18 at 17:37
  • $\begingroup$ Just wonder what will benefit. is this going to open a new direction? $\endgroup$ – kelalaka Oct 12 '18 at 17:51
  • 1
    $\begingroup$ Representation theory is well studied in math, but it's related to crypto since algebraic structures can be represented in terms of linear algebra. For my point of view, it can benefit the understanding of underlying relations in a given cryptosystem, but this doesn't necessarily imply that the cryptosystem can be broken in a reasonable amount of time. $\endgroup$ – kub0x Oct 12 '18 at 18:57
  • $\begingroup$ Is there any tool that will help some of the problems around? Faster algorithms, a different perspective etc. $\endgroup$ – kelalaka Oct 12 '18 at 18:59
  • 1
    $\begingroup$ For example on non-abelian groups where a key exchange is based on a group theoretic algorithm. I want to know if representation theory plays a role on cryptography, and if can help us in a different way than conventional methods. $\endgroup$ – kub0x Oct 12 '18 at 20:37
1
$\begingroup$

Let me answer this question in the context of braid group cryptography since braid groups form the group based cryptosystems which I am most familiar with. Keep in mind that today, most if not all braid based cryptosystems have been successfully attacked. On the other hand, braid group cryptography has not been thoroughly explored and mathematicians still need to investigate braid group cryptography some more. Braid groups are very deep and interesting structures connecting diverse areas such as algebraic topology, quantum computation, and even very large cardinals, so even non-applied mathematicians should appreciate braid group cryptography enough to investigate it further.

There are several well-known representations of the braid groups including the Burau representation (which is not faithful but has a small kernel), the Lawrence-Krammer representation, and several unitary representations used in topological quantum computation. Furthermore, there are several important actions of the braid groups such as the Hurwitz action or the Dynnikov action (these actions are non-linear though). The Hurwitz action generalizes to an action of positive braids on self-distributive algebras and the Burau representation is a special case of the Hurwitz action. The Burau and Lawrence-Krammer representations can be used to attack braid based cryptosystems by first solving the problem (the problem, for example could be the conjugacy search problem) in the matrix group and then lifting the solution back to the braid groups.

The Hurwitz action on braid groups gives very easily computable strong invariants of braids which can in almost all cases distinguish braids in nearly linear time (in a sense, the Hurwitz action gives a 'hash' of a braid). The Dynnikov action can be used to solve the word problem in braid groups using only linearly many integer addition and comparison operations.

There are several ways to analyze braid based cryptosystems which have little or nothing to do with the representations of braid groups. These attacks include length-based attacks, attacks against the conjugacy search problem based on summit sets, and other attacks. Summit sets arise from the Garside normal form and Birman-Ko-Lee normal form of braids which have little to do with their linear representations. Length based attacks are based on length functions which could arise from one of the normal forms of braids. Dehornoy's handle reduction technique and its generalizations are used to minimize the length of a braid and reveal the data that braid based cryptosystems attempt to hide.

I must mention that the attacks against braid based cryptosystems are generally heuristic algorithms, so one will need to program quite a bit in order to properly evaluate these cryptosystems and to evaluate whether an attack against braid based cryptosystems is successful or not.

Since braids are related to a wide array of mathematical structures, it is easier and more direct to understand just braid groups, braid group cryptography, and how braid groups relate to certain areas of mathematics than to be an expert in all of these mathematical disciplines related to braids.

All of these representations and results about braids could be found in the standard references of braids including the survey Braid Group Cryptography by David Garber, the book Braids and Self-Distributivity by Patrick Dehornoy, the book on braid groups by Kassel and Turaev, and the book Ordering Braids by Patrick Dehornoy.

$\endgroup$
  • $\begingroup$ I do not understand why your answer isn't getting upvoted. I'm not studying braids but the protocols that use it as platform group. I've read about Lawrence-Krammer representation being applied here: eprint.iacr.org/2014/041.pdf page 15 section 5.3 paper discusses analysis of non-commutative protocols on braid groups. I accept your answer since you provide enough references taking braids as platform group, the reading will help me a lot. $\endgroup$ – kub0x Oct 27 '18 at 9:42

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.