ﻻ يوجد ملخص باللغة العربية
On March 2004, Anshel, Anshel, Goldfeld, and Lemieux introduced the emph{Algebraic Eraser} scheme for key agreement over an insecure channel, using a novel hybrid of infinite and finite noncommutative groups. They also introduced the emph{Colored Burau Key Agreement Protocol (CBKAP)}, a concrete realization of this scheme. We present general, efficient heuristic algorithms, which extract the shared key out of the public information provided by CBKAP. These algorithms are, according to heuristic reasoning and according to massive experiments, successful for all sizes of the security parameters, assuming that the keys are chosen with standard distributions. Our methods come from probabilistic group theory (permutation group actions and expander graphs). In particular, we provide a simple algorithm for finding short expressions of permutations in $S_n$, as products of given random permutations. Heuristically, our algorithm gives expressions of length $O(n^2log n)$, in time and space $O(n^3)$. Moreover, this is provable from emph{the Minimal Cycle Conjecture}, a simply stated hypothesis concerning the uniform distribution on $S_n$. Experiments show that the constants in these estimations are small. This is the first practical algorithm for this problem for $nge 256$. Remark: emph{Algebraic Eraser} is a trademark of SecureRF. The variant of CBKAP actually implemented by SecureRF uses proprietary distributions, and thus our results do not imply its vulnerability. See also arXiv:abs/12020598
Anshel, Anshel, Goldfeld and Lemieaux introduced the Colored Burau Key Agreement Protocol (CBKAP) as the concrete instantiation of their Algebraic Eraser scheme. This scheme, based on techniques from permutation groups, matrix groups and braid groups
We develop a theory of semidirect products of partial groups and localities. Our concepts generalize the notions of direct products of partial groups and localities, and of semidirect products of groups.
We develop the theory of fragile words by introducing the concept of eraser morphism and extending the concept to more general contexts such as (free) inverse monoids. We characterize the image of the eraser morphism in the free group case, and show
Let VB$_n$ be the virtual braid group on $n$ strands and let $mathfrak{S}_n$ be the symmetric group on $n$ letters. Let $n,m in mathbb{N}$ such that $n ge 5$, $m ge 2$ and $n ge m$. We determine all possible homomorphisms from VB$_n$ to $mathfrak{S}_
Inspired by a width invariant defined on permutations by Guillemot and Marx, the twin-width invariant has been recently introduced by Bonnet, Kim, Thomasse, and Watrigant. We prove that a class of binary relational structures (that is: edge-colored p