In braid based cryptography, one typically wants to conceal the way a certain braid $b$ has been obtained. One therefore puts $b$ into some normal form. Since every braid has a unique normal form, the normal form of $b$ only reveals the braid $b$ without revealing any other information about how the braid $b$ was obtained. Therefore, normal forms conceal the method which the braid has been obtained. However, do braid normal forms really conceal information about the braids any better than randomly applying the braid laws?
Let $b$ be a positive braid. Let $H$ be the set of all positive braid words which are equivalent to $b$. Now say that two braid words $w,w'$ are $\simeq$-equivalent if $w'$ can be obtained from $w$ by applying only the identities $\sigma_{i}\sigma_{j}=\sigma_{j}\sigma_{i}$ for $|i-j|>1$. Let $V=H/\simeq$. Let $E$ be the set of all pairs $\{\mathbf{x},\mathbf{y}\}\in V$ where there exists representatives $x\in\mathbf{x},y\in\mathbf{y}$ such that $y$ can be obtained from $x$ by applying the relation $\sigma_{i}\sigma_{i+1}\sigma_{i}=\sigma_{i+1}\sigma_{i}\sigma_{i+1}$. What is the random walk mixing time for the graph $(V,E)$? Does it take longer for a computer to calculate a normal form for the braid $b$ or to take a nearly random walk on $[b]$ up to the mixing time?
