Towards generating secure keys for braid cryptography

Braid cryptosystem was proposed in CRYPTO 2000 as an alternate public-key cryptosystem. The security of this system is based upon the conjugacy problem in braid groups. Since then, there have been several attempts to break the braid cryptosystem by solving the conjugacy problem in braid groups. In this article, we first survey all the major attacks on the braid cryptosystem and conclude that the attacks were successful because the current ways of random key generation almost always result in weaker instances of the conjugacy problem. We then propose several alternate ways of generating hard instances of the conjugacy problem for use braid cryptography.      

On bifurcation braid monodromy of elliptic fibrations

We propose to study a new kind of monodromy homomorphism for families of regular elliptic fibrations of a given differentiable fibration type to get a hold on topological properties of moduli stacks of elliptic surfaces.In specific cases, including the most significant one, when all singular fibres are nodal irreducible rational curves, we compute the corresponding monodromy group, a subgroup of the mapping class group of the fibration base punctured at the singular values of the fibration.We study a tentative algebraic characterisation and give implications for the group of diffeomorphisms compatible with the fibration.     

Effective invariants of braid monodromy

In this paper we construct new invariants of algebraic curves based on (not necessarily generic) braid monodromies. Such invariants are effective in the sense that their computation allows for the study of Zariski pairs of plane curves. Moreover, the Zariski pairs found in this work correspond to curves having conjugate equations in a number field, and hence are not distinguishable by means of computing algebraic coverings. We prove that the embeddings of the curves in the plane are not homeomorphic. We also apply these results to the classification problem of elliptic surfaces.

     

A formula for the braid index of links

Morton and Franks–Williams independently gave a lower bound for the braid index b(L) of a link L in S³ in terms of the v-span of the Homfly-pt polynomial P_L(v,z) of L: . Up to now, many classes of knots and links satisfying the equality of this Morton–Franks–Williams's inequality have been founded. In this paper, we give a new such a class of knots and links and make an explicit formula for determining the braid index of knots and links that belong to the class . This gives simultaneously a new class of knots and links satisfying the Jones conjecture which says that the algebraic crossing number in a minimal braid representation is a link invariant. We also give an algorithm to find a minimal braid representative for a given knot or link in .     

Entity authentication schemes using braid word reduction

Artin's braid groups currently provide a promising background for cryptographical applications, since the first cryptosystems using braids were introduced in [I. Anshel, M. Anshel, D. Goldfeld, An algebraic method for public-key cryptography, Math. Res. Lett. 6 (1999) 287-291, I. Anshel, M. Anshel, B. Fisher, D. Goldfeld, New key agreement schemes in braid group cryptography, RSA 2001, K.H. Ko, S.J. Lee, J.H. Cheon, J.W. Han, J.S. Kang, C. Park, New public-key cryptosystem using braid groups, Crypto 2000, pp. 166-184] (see also [V.M. Sidelnikov, M.A. Cherepnev, V.Y. Yashcenko, Systems of open distribution of keys on the basis of noncommutative semigroups, Ross. Acad. Nauk Dokl. 332-5 (1993); English translation: Russian Acad. Sci. Dokl. Math. 48-2 (1194) 384-386]). A variety of key agreement protocols based on braids have been described, but few authentication or signature schemes have been proposed so far. We introduce three authentication schemes based on braids, two of them being zero-knowledge interactive proofs of knowledge. Then we discuss their possible implementations, involving normal forms or an alternative braid algorithm, called handle reduction, which can achieve good efficiency under specific requirements.     

Presentations of subgroups of the braid group generated by powers of band generators

According to the Tits conjecture proved by Crisp and Paris (2001) [4], the subgroups of the braid group generated by proper powers of the Artin elements σi are presented by the commutators of generators which are powers of commuting elements. Hence they are naturally presented as right-angled Artin groups.The case of subgroups generated by powers of the band generators aij is more involved. We show that the groups are right-angled Artin groups again, if all generators are proper powers with exponent at least 3. We also give a presentation in cases at the other extreme, when all generators occur with exponent 1 or 2. Such presentations are distinctively more complicated than those of right-angled Artin groups.     

A faithfulness criterion for the Gassner representation of the pure braid group

This work is directed towards the open question of the faithfulness of the reduced Gassner representation of the pure braid group, . Long and Paton proved that if a Burau matrix has ones on the diagonal and zeros below the diagonal then is the identity matrix. In this paper, a generalization of Long and Paton's result will be proved. Our main theorem is that if the trace of the image of an element of under the reduced Gassner representation is , then this element lies in the kernel of this representation. Then, as a corollary, we prove that an analogue of the main theorem holds true for the Burau representation of the braid group.

     

The braid index is not additive for the connected sum of 2-knots

Any -dimensional knot can be presented in a braid form, and its braid index, , is defined. For the connected sum of -knots and , it is easily seen that holds. Birman and Menasco proved that the braid index (minus one) is additive for the connected sum of -dimensional knots; the equality holds for -knots. We prove that the equality does not hold for -knots unless or is a trivial -knot. We also prove that the -knot obtained from a granny knot by Artin's spinning is of braid index , and there are infinitely many -knots of braid index .

     

Complex specializations of the reduced Gassner representation of the pure braid group

We will give a necessary and sufficient condition for the specialization of the reduced Gassner representation to be irreducible. It will be shown that for , is irreducible if and only if .

     

On the cycling operation in braid groups

The cycling operation is a special kind of conjugation that can be applied to elements in Artin’s braid groups, in order to reduce their length. It is a key ingredient of the usual solutions to the conjugacy problem in braid groups. In their seminal paper on braid-cryptography, Ko, Lee et al. proposed the cycling problem as a hard problem in braid groups that could be interesting for cryptography. In this paper we give a polynomial solution to that problem, mainly by showing that cycling is surjective, and using a result by Maffre which shows that pre-images under cycling can be computed fast. This result also holds in every Artin-Tits group of spherical type, endowed with the Artin Garside structure.On the other hand, the conjugacy search problem in braid groups is usually solved by computing some finite sets called (left) ultra summit sets (left-USSs), using left normal forms of braids. But one can equally use right normal forms and compute right-USSs. Hard instances of the conjugacy search problem correspond to elements having big (left and right) USSs. One may think that even if some element has a big left-USS, it could possibly have a small right-USS. We show that this is not the case in the important particular case of rigid braids. More precisely, we show that the left-USS and the right-USS of a given rigid braid determine isomorphic graphs, with the arrows reversed, the isomorphism being defined using iterated cycling. We conjecture that the same is true for every element, not necessarily rigid, in braid groups and Artin-Tits groups of spherical type.     

Stable decompositions for some symmetric group characters arising in braid group cohomology

We prove that certain permutation characters for the symmetric group Σn decompose in a manner that is independent of n for large n. This result is a key ingredient in the recent work of T. Church and B. Farb, who obtain a “representation stability” theorem for the character of Σn acting on the cohomology Hp(Pn,C) of the pure braid group Pn.     

The Witt classes of torsion linking forms of (4n−1)-manifolds with pseudo-free circle actions

In this paper we compute the Witt class of torsion linking forms of (4n−1)-dimensional closed oriented manifolds admitting orientation preserving pseudo-free circle actions.     

Synchronism of an incompressible non-free Seifert surface for a knot and an algebraically split closed incompressible surface in the knot complement

We give a necessary and sufficient condition for knots to bound incompressible non-free Seifert surfaces.

     

The fixed subgroups of homeomorphisms of Seifert manifolds

Let M be a compact connected orientable Seifert manifold with hyperbolic orbifold B M,and fπ : π1(M) →π1(M) be an automorphism induced by an orientation-reversing homeomorphism f of M. We give a bound on the rank of the fixed subgroup of fπ, namely, rank Fix(fπ) 2rankπ1(M),which is an analogue of inequalities on surface groups and hyperbolic 3-manifold groups.     

Efficient solutions to the braid isotopy problem

We describe the most efficient solutions to the word problem of Artin’s braid group known so far, i.e., in other words, the most efficient solutions to the braid isotopy problem, including the Dynnikov method, which could be especially suitable for cryptographical applications. Most results appear in the literature; however, some results about the greedy normal form and the symmetric normal form and their connection with grid diagrams may have never been stated explicitly.     

Flat connections on configuration spaces and braid groups of surfaces

We construct an explicit bundle with flat connection on the configuration space of n points on a complex curve. This enables one to recover the ‘1-formality’ isomorphism between the Lie algebra of the prounipotent completion of the pure braid group of n   points on a surface and an explicitly presented Lie algebra, and to extend it to a morphism from the full braid group of the surface to the semidirect product of the associated group with the symmetric group _Sn$S_n$.     

On the Structure of Cimpact Simply Connected Manifolds of Positive Sectional Curvature

We present a first structure theorem for compact simply connected positively curved manifolds with arbitrarily small pinching constants: For each nN and 0<1, there exists a positive number V = V(n,) such that if (M,g) is a compact simply connected n-dimensional Riemannian manifold with sectional curvature 0相似文献