Braid groups has drawn the attention of cryptographers for a few years, as a promising platform for post-quantum cryptographic protocols. The security of the proposed schemes mostly relied on conjugacy problems, and attacks against this problem were discovered, and cryptographers lost interest in those braid groups. But as far as I know, those attacks don't completely break the security of braid groups. For example, conjugacy problems can be solved by computing the USS (Ultra Summit Set) of a braid, but this set can have exponential size in the length of the braid (for some classes of braids).

I don't know much about other attacks on braid groups, but do they definitely put an end to any applications of braids to cryptography? If we could highlight properties of braids comparable to bilinear pairings for elliptic curves, allowing some of the related advanced protocols in a post-quantum world, would they become more interesting or are they definitely too weak for cryptography?

EDIT:

Note that my question didn't mean to say "is anyone still interested in braids", but rather "do we know attacks (that I am not aware of) on conjugacy related problems for braids that definitely label them as 'not suitable for cryptography'". I am certainly not looking for (or expecting) as an answer any opinion about how interesting they are.

I believe that the conjugacy search problem is broken by probabilistic attacks (see chapter 7). I am not sure if this completely ends braid cryptography, however, since there are other difficult problems in braid groups that have not been studied extensively.

I do not believe that braid based cryptography is dead since new ways of applying braid groups to cryptography are currently being investigated and have recently been proposed. In fact, recently researchers have observed how braids could be used for reversible circuit obfuscation.

A recent paper on braid-based obfuscation

The 2014 paper, Partial-indistinguishability obfuscation using braids, by Alagic, Jeffery, and Jordan explains how braid groups could be used to obfuscate reversible circuits and thus obfuscate all forms of classical computation. The paper goes even further to explain how braids could be used to obfuscate quantum computation as well. This method of obfuscation does not rely on the difficulty of one of the conjugacy problems for braids.

The mathematics behind braid-based obfuscation

An algebraic structure $(X,*)$ is said to be an LD-system if $(X,*)$ satisfies the identity $x*(y*z)=(x*y)*(x*z)$. In other words, LD-systems satisfy a self-distributivity identity. Define a mapping $L_{a}:X\rightarrow X$ for each $a\in X$ by letting $L_{a}(x)=a*x$. A rack is an LD-system $(X,*)$ where each mapping $L_{a}$ is bijective. For example, if $G$ is a group and $*$ is the conjugacy operation on $G$ defined by $x*y=xyx^{-1}$, then $(G,*)$ is a rack.

If $(X,*)$ is a rack, then the braid group $B_{n}$ acts on $X^{n}$ by letting $(x_{1},...,x_{n})\sigma_{i}=(x_{1},...,x_{i}*x_{i+1},x_{i},x_{i+2},...,x_{n})$.

The action of $\sigma_{i}$ on $(x_{1},...,x_{n})$ should be thought of as running the elements $(x_{i},x_{i+1})$ through the reversible gate $(a,b)\mapsto(a*b,a)$. Therefore, the action of a braid word on $(x_{1},...,x_{n})$ should be thought of as running $(x_{1},...,x_{n})$ through a reversible circuit.

It turns out that the reversible circuits for the action of braid words on the LD-system $(A_{5},*)$ is universal for reversible computation.

Therefore, to obfuscate a reversible circuit, first we represent the reversible circuit as a braid word $w$. Then let $w'$ be the unique braid word equivalent to $w$ but in some normal form. Then the braid word $w'$ represents an obfuscated reversible circuit that computes the same thing as $w$.

Unfortunately, the classical circuit obfuscator in 1 is insecure since length based attacks work against it. However, little is known about the security of insecurity of the quantum obfuscator.

As a datapoint: the company SecureRF has a scheme they call "Group Theoretic Cryptography" (really guys? possible to be any more generic?) that is based on braid groups. [see their list of published papers and presentations]

This is not my area of expertise, but I believe they get their security from a trapdoor construction called e-multiplication rather than from conjugacy problems.

I believe they are planning to submit to NIST's Post-Quantum competition, so that would answer your question "Yes, there are braid group constructions which are believed to be unbroken and quantum-secure".

  • 1
    By late 2015, SecreRF's Algebraic Eraser was in the broken state of a multiple break/fix cycles, and the arguments developed to repel the last break quite questionable; see this and the answer. – fgrieu Jul 24 '17 at 18:40
  • @fgrieu LOL that blog post by Schneier is wonderful. Alright, I'll avoid buying anything from them, and get out my popcorn for their NIST submission to get torn to shreds. – Mike Ounsworth Jul 24 '17 at 18:47
  • 1
    I did a 2017-07 update; SecureRF has reluctantly admitted that some of the proposed Algebraic Eraser standard was vulnerable, and introduced Ironwood which looks like a replacement. The latest claims are more modest (Ironwood as parametrized is no longer presented as quite a full-blown asymmetric authentication and key agreement protocol) and appear to address earlier attacks; on the other hand, it is a very new protocol, and one without a formal security reduction, contrary to the tendency in modem crypto in the past 20 years. – fgrieu Jul 25 '17 at 11:19
  • @fgrieu Yeah, that's more consistent with what SecureRF presented at a recent conference. I also like security proofs, but as the quantum threat gets closer and it's becoming clear that many schemes with formal proofs have unusably large data structures, I'm seeing more and more schemes get proposed without proofs - for example at the recent PQCrypto2017 conference. – Mike Ounsworth Jul 25 '17 at 13:49

Your Answer

 
discard

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

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