On 2012-05-22 2:51 PM, Whiskey T. Foxtrot wrote:
I am interested (for personal reasons) in crypto based on the braid
group, and in particular in certain claims by a company named SecureRF.
SecureRF claims to have a cryptographic scheme that is both as secure as
traditional methods and much faster than these methods. Specifically,
they claim that the scheme is fast and simple enough (uses few enough
instructions) that it can be implemented on passive RFID chips.
SecureRF's scheme is based on the braid group (and the conjugacy search
problem, etc.). The original idea is described by Anshel, Anshel, and
Golfeld in "An Algebraic Method for PublicKey Cryptography", and by the
same authors plus Fisher in "New Key Agreement Protocols in Braid Group
Cryptography". More details later if necessary. (By the way, Anshel and
Goldfeld are two of SecureRF's cofounders.)
Such schemes (based on the braid group) have been attacked multiple
times with success, using matrix representations, using so-called length
attacks, solving the conjugacy problem, and maybe by other methods that
I don't know. More details here as well if needed.
However, SecureRF claims to have improved the scheme by using what they
call the Algebraic Eraser and the Colored Burau Key Agreement Protocol
(CBKAP). (I must admit here that I haven't yet fully understood this part.)
I see that there has been some attacks on the AE/CBKAP, but it seems
that they may not have been successful after all. For example:
Attack by Kalka et al.: http://arxiv.org/pdf/0804.0629v5.pdf
Answer by Goldfeld and Gunnells: http://arxiv.org/pdf/1202.0598v1.pdf
Attack by Myasnikov and Ushakov: http://arxiv.org/pdf/0801.4786.pdf
Gunnells' answer: http://arxiv.org/pdf/1105.1141v1.pdf
So, I'd love to hear any opinion on the AE/CBKAP. Does the math hold up?
If so, why isn't there more interest in it? I see that many people in
the crypto field have discarded the method (Schneier, for example). Why?
SecureRF's website is full of unhelpful marketing material, and based on
it I wouldn't trust their crypto scheme, but what is the state of actual
research in this area?
A lot of problems that are in principle NP difficult, are in practice
usually a lot easier. The braid conjugacy problem is one such.
Although there is no known polynomial time algorithm that can reliably
solve all braid conjugacy problems, most braid conjugacy problems
somehow turn out to be solvable in polynomial time.
Thus, any cryptographic suite that relies on the hardness braid
conjugacy problem cannot reliably know if the braid conjugacy problems
it generates are hard. It may merely be that no one has yet found the
trick to solving them, and a little more work will reveal the trick -
that being the way things usually turn out with braid conjugacy problems.
The history of braid conjugacy cryptography is that someone finds a
clever way of making sure that the problems are hard, then it turns out
they are not hard at all, then someone finds an even more clever way of
making sure the problems are hard, then again it turns out that the
problems are not hard, then someone finds an even more clever ...
There is widespread suspicion that no braid conjugacy problems are hard.
If their cryptosystem has not been broken yet, the way the wind has been
blowing, it will be broken soon enough.
_______________________________________________
cryptography mailing list
[email protected]
http://lists.randombit.net/mailman/listinfo/cryptography
