Computational Aspects in the Braid Group and Applications to Cryptography

Computer Science/Discrete Mathematics Seminar I
Topic:Computational Aspects in the Braid Group and Applications to Cryptography
Speaker:Mina Teicher
Affiliation:Bar-Ilan University; Member, School of Mathematics
Date:Monday, March 12
Time/Room:11:15am - 12:15pm/West Bldg. Lecture Hall

The braid group on n strands may be viewed as an infinite analog of the symmetric group on n elements with additional topological phenomena. It appears in several areas of mathematics, physics and computer sciences, including knot theory, algebraic geometry, quantum mechanics, quantum computing and cryptography. I will start with a presentation of the braid group and its three main structural and relationship problems – the Word problem, Conjugacy problem, and the Hurwitz Equivalence problem. I will talk about algorithms for these problems and will detail one probabilistic algorithm. I shall talk about the celebrated un-decidability result of the Hurwitz Equivalence, on an attack on a braid group based PKC and will mention the application to classification of surfaces