(Current homepage of the author is at http://www.postech.ac.kr/~jccha/.)
CBraid is a C++ class library that implements algorithms for computations in braid groups, including ones described in the author's paper [1] and more.
Recently some braid cryptosystems, which are based on non-commutative structures, have been introduced and become a matter of interest for the cryptography research community. There still remain lots of things to be studied on braid cryptosystems, and many of them needs to be aided by a computer. In this regard, the main aim of CBraid library is to offer a basic tool that is useful in braid cryptography research.
CBraid offers a set operations in braid groups, including:
Many operations are provided as overloaded operators as well as member functions, so that users can write simple and easy-to-read code for braid computation; for example, a conjugation can be written as y=a*x*!a in one's C++ code.
It supports computations in both of the Artin presentation and the band-generator presentation.
The algorithms that are implemented in CBraid are theoretically optimized, but the source code does not use any technical coding tricks for speed improvement; for the research purpose, readability is much more important than (perhapsely little) speed improvement. For instance, assembly codes have not been used and will be never used in CBraid. In contrast to this, I heavily used C++ language features for abstraction, including operator overloading and templates, to show the structure of the algorithms and related theory in the source code.
My todo list includes a comprehensive documentation, the computation of various invariants of braids, hash functions for braids, and several kinds of conversions between braids and bitstrings.
This is 2001/12/07 snapshot of the source code of CBraid library.
Download cbraid-20011207.tar.gz
Added on October 28, 2011. A patched version of CBraid for more recent compilers is available at http://code.google.com/p/cbraid/.
On most Unix-like environments, it is straighforward to compile CBraid. Uncompressing and expanding the tarball, top directory "cbraid" is created. Go into "lib" subdirectory and use "make" command to create "libcbraid.a" library file. Go into "sample" subdirectory and use "make" command to create sample programs.
For Unix-like environments, I recommend recent versions of GCC (and friend tools) for CBraid. I use GCC 2.95.3 on a FreeBSD 4.x machine.
For win32 environments, I recommend Cygnus GNU-Win32, which provides a development environment almost identical with Unix's one.
Because CBraid does not use any vender-specific extensions of C++ language (beyond the language features described in Stroustrap's book), any standard C++ compiler could be used to compile CBraid, if an appropriate makefile were written.
CBraid is neither large-scale nor compilicated, and hence sophisticated configuration tools like GNU autoconf are not used.
CBraid uses internally CLN library written by Bruno Haible, for large integer manipulation. If you want to use the full features of CBraid, CLN must be installed on your system before compilation of CBraid. For more information on CLN, refer CLN home page. After installing CLN, you may need to modify CPPFLAGS_CLN variable in "lib/Makefile" and "sample/Makefile" of CBraid, to specify correct paths.
Removing CPPFLAGS_CLN and LIBFLAGS_CLN in "lib/Makefile" and "sample/Makefile", CBraid can be built without CLN. In this case, the random braid generation feature in the band-generator presentation is disabled (but not in the Artin presentation). Actually, in braid algorithms, large integers do not play an essential role; they are used only for the computation of the Catalan Numbers which are necessary in generating random braids in the band-generator presentation.
Copyright (C) 2000-2001 Jae Choon Cha.
CBraid is distributed under the terms of the GNU General Public License. For details, see the comments of the source files and GPL.TXT file.
The followings are typo errors that were found in [1] after it had been published. They are not essential in understanding the ideas of [1], but may confuse slightly ones who implement the algorithms described in [1].
Page 11, line 9: replace each "k" by "(k-1)".[1] Jae Choon Cha, et al., "An efficient implementation of braid groups", AsiaCrypt 2001, Lecture Notes in Computer Science 2248, pp. 157-174.
$Id: index.php3,v 1.7 2001/12/17 02:56:50 jccha Exp $