Factoring Products of Braids via Garside Normal Form

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Standard

Factoring Products of Braids via Garside Normal Form. / Merz, Simon-Philipp; Petit, Christophe.

Public-Key Cryptography – PKC 2019 - 22nd IACR International Conference on Practice and Theory of Public-Key Cryptography, Proceedings: 22nd IACR International Conference on Practice and Theory of Public-Key Cryptography, Beijing, China, April 14-17, 2019, Proceedings, Part II. ed. / Kazue Sako; Dongdai Lin. Springer, 2019. p. 646-678 (Lecture Notes in Computer Science; Vol. 11443 LNCS).

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Harvard

Merz, S-P & Petit, C 2019, Factoring Products of Braids via Garside Normal Form. in K Sako & D Lin (eds), Public-Key Cryptography – PKC 2019 - 22nd IACR International Conference on Practice and Theory of Public-Key Cryptography, Proceedings: 22nd IACR International Conference on Practice and Theory of Public-Key Cryptography, Beijing, China, April 14-17, 2019, Proceedings, Part II. Lecture Notes in Computer Science, vol. 11443 LNCS, Springer, pp. 646-678, 2nd IACR International Conference on Practice and Theory of Public-Key Cryptography (PKC 2019), Beijing, China, 14/04/19. https://doi.org/10.1007/978-3-030-17259-6_22

APA

Merz, S-P., & Petit, C. (2019). Factoring Products of Braids via Garside Normal Form. In K. Sako, & D. Lin (Eds.), Public-Key Cryptography – PKC 2019 - 22nd IACR International Conference on Practice and Theory of Public-Key Cryptography, Proceedings: 22nd IACR International Conference on Practice and Theory of Public-Key Cryptography, Beijing, China, April 14-17, 2019, Proceedings, Part II (pp. 646-678). (Lecture Notes in Computer Science; Vol. 11443 LNCS). Springer. https://doi.org/10.1007/978-3-030-17259-6_22

Vancouver

Merz S-P, Petit C. Factoring Products of Braids via Garside Normal Form. In Sako K, Lin D, editors, Public-Key Cryptography – PKC 2019 - 22nd IACR International Conference on Practice and Theory of Public-Key Cryptography, Proceedings: 22nd IACR International Conference on Practice and Theory of Public-Key Cryptography, Beijing, China, April 14-17, 2019, Proceedings, Part II. Springer. 2019. p. 646-678. (Lecture Notes in Computer Science). https://doi.org/10.1007/978-3-030-17259-6_22

Author

Merz, Simon-Philipp ; Petit, Christophe. / Factoring Products of Braids via Garside Normal Form. Public-Key Cryptography – PKC 2019 - 22nd IACR International Conference on Practice and Theory of Public-Key Cryptography, Proceedings: 22nd IACR International Conference on Practice and Theory of Public-Key Cryptography, Beijing, China, April 14-17, 2019, Proceedings, Part II. editor / Kazue Sako ; Dongdai Lin. Springer, 2019. pp. 646-678 (Lecture Notes in Computer Science).

Bibtex

@inproceedings{865f8284b42f4b12b23b1e30034fb989,
title = "Factoring Products of Braids via Garside Normal Form",
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 ABC when only B is known. Our decomposition algorithm yields a universal forgery attack on WalnutDSA{\texttrademark}, which is one of the 20 proposed signature schemes that are being considered by NIST for standardization of quantum-resistant public-key cryptography. Our attack on WalnutDSA{\texttrademark} can universally forge signatures within seconds for both the 128-bit and 256-bit security level, given one random message-signature pair. The attack worked on 99.8% and 100% of signatures for the 128-bit and 256-bit security levels in our experiments. Furthermore, we show that the decomposition algorithm can be used to solve instances of the conjugacy search problem and decomposition search problem in braid groups. These problems are at the heart of other cryptographic schemes based on braid groups.",
author = "Simon-Philipp Merz and Christophe Petit",
year = "2019",
month = apr,
day = "6",
doi = "10.1007/978-3-030-17259-6_22",
language = "English",
isbn = "978-3-030-17258-9",
series = "Lecture Notes in Computer Science",
publisher = "Springer",
pages = "646--678",
editor = "Kazue Sako and Dongdai Lin",
booktitle = "Public-Key Cryptography – PKC 2019 - 22nd IACR International Conference on Practice and Theory of Public-Key Cryptography, Proceedings",
note = "2nd IACR International Conference on Practice and Theory of Public-Key Cryptography (PKC 2019) ; Conference date: 14-04-2019 Through 17-04-2019",

}

RIS

TY - GEN

T1 - Factoring Products of Braids via Garside Normal Form

AU - Merz, Simon-Philipp

AU - Petit, Christophe

PY - 2019/4/6

Y1 - 2019/4/6

N2 - 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 ABC when only B is known. Our decomposition algorithm yields a universal forgery attack on WalnutDSA™, which is one of the 20 proposed signature schemes that are being considered by NIST for standardization of quantum-resistant public-key cryptography. Our attack on WalnutDSA™ can universally forge signatures within seconds for both the 128-bit and 256-bit security level, given one random message-signature pair. The attack worked on 99.8% and 100% of signatures for the 128-bit and 256-bit security levels in our experiments. Furthermore, we show that the decomposition algorithm can be used to solve instances of the conjugacy search problem and decomposition search problem in braid groups. These problems are at the heart of other cryptographic schemes based on braid groups.

AB - 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 ABC when only B is known. Our decomposition algorithm yields a universal forgery attack on WalnutDSA™, which is one of the 20 proposed signature schemes that are being considered by NIST for standardization of quantum-resistant public-key cryptography. Our attack on WalnutDSA™ can universally forge signatures within seconds for both the 128-bit and 256-bit security level, given one random message-signature pair. The attack worked on 99.8% and 100% of signatures for the 128-bit and 256-bit security levels in our experiments. Furthermore, we show that the decomposition algorithm can be used to solve instances of the conjugacy search problem and decomposition search problem in braid groups. These problems are at the heart of other cryptographic schemes based on braid groups.

UR - http://www.scopus.com/inward/record.url?scp=85064899117&partnerID=8YFLogxK

U2 - 10.1007/978-3-030-17259-6_22

DO - 10.1007/978-3-030-17259-6_22

M3 - Conference contribution

SN - 978-3-030-17258-9

T3 - Lecture Notes in Computer Science

SP - 646

EP - 678

BT - Public-Key Cryptography – PKC 2019 - 22nd IACR International Conference on Practice and Theory of Public-Key Cryptography, Proceedings

A2 - Sako, Kazue

A2 - Lin, Dongdai

PB - Springer

T2 - 2nd IACR International Conference on Practice and Theory of Public-Key Cryptography (PKC 2019)

Y2 - 14 April 2019 through 17 April 2019

ER -