Paper 2018/1142
Factoring Products of Braids via Garside Normal Form
Simon-Philipp Merz and Christophe Petit
Abstract
Braid groups are infinite non-abelian groups naturally arising from geometric braids. For two decades they have been proposed for cryptographic use. In braid group cryptography public braids often contain secret braids as factors and it is hoped that rewriting the product of braid words hides individual factors. We provide experimental evidence that this is in general not the case and argue that under certain conditions parts of the Garside normal form of factors can be found in the Garside normal form of their product. This observation can be exploited to decompose products of braids of the form
Metadata
- Available format(s)
-
PDF
- Category
- Public-key cryptography
- Publication info
- Preprint. MINOR revision.
- Keywords
- group based cryptographypost-quantum digital signaturesconjugacy search problemcryptanalysis
- Contact author(s)
- simon-philipp merz 2018 @ live rhul ac uk
- History
- 2019-01-18: revised
- 2018-11-29: received
- See all versions
- Short URL
- https://ia.cr/2018/1142
- License
-
CC BY
BibTeX
@misc{cryptoeprint:2018/1142, author = {Simon-Philipp Merz and Christophe Petit}, title = {Factoring Products of Braids via Garside Normal Form}, howpublished = {Cryptology {ePrint} Archive, Paper 2018/1142}, year = {2018}, url = {https://eprint.iacr.org/2018/1142} }