using braid groups vs. number theory for pki

dmolnar dmolnar at hcs.harvard.edu
Tue Jan 23 22:44:01 PST 2001




On Wed, 24 Jan 2001, Phillip Zakas wrote:

> mathematics seems to imply much faster encryption/decryption engines.
> Before I spend the next month working through this, does anyone know of a
> braid group-based encryption/decryption engine?  Did it work?  Any
> cryptanalysis  on this?

Helger Lipmaa's truly amazing collection of links reveals

"Practical comparison of Fast Public-key Cryptosystems"
P. Karu, J. Loikkanen
http://www.tml.hut.fi/~pk/crypto/fast_pk_crypto.ps

which is an account of an implementation of braid group encryption and a
performance comparison to ECC and NTRU. The implementation was done in
C++, so I bet your assembly version would kill it - but of course you'd
have to do the same for NTRU to acheive proper comparison...
(I didn't see it available for download - maybe contact the authors)

The rest of the links are worth checking out as well.
http://www.tml.hut.fi/~helger/crypto/link/public/braid/

and include some cryptanalysis and other links. Be careful when reading
these - the "word problem" is not what you may think it is, and some of
the cryptosystems seem to depend on more than just the word problem for
their security. If you have a good library nearby, you may want to look
for Rotman's _Introduction to Combinatorial Group Theory_ as a guide; it's
the best introduction I've found so far to the general issues. 

Short answer to "is it secure" is "maybe." Keep in mind that all you need
these days is a very weak trapdoor function and then you can "boost" it to
create a full public key cryptosystem. So if we can find any "hardness" at
all, that may be enough. 

> 
> Also, does anyone have any stats on the performance of popular pki systems?

Sorry, don't know more here than "look for white papers." Most of which
probably won't help you.

-David







More information about the cypherpunks-legacy mailing list