Copy Link
Add to Bookmark
Report

CGC Bulletin 3

eZine's profile picture
Published in 
CGC Bulletin
 · 11 months ago

CONTENTS

  1. Slides for the Bochum Workshop talks
  2. A useful information resource for CGC
  3. A new key exchange protocol based on the decomposition problem
  4. A Practical Attack on the Root Problem in Braid Groups
  5. Recent doctoral dissertations in the field

1. Slides for the Bochum Workshop talks

The slides of most of that talks in the Bochum Workshop "Algebraic methods in cryptography" are now available at the workshop's web-page:

http://www.ruhr-uni-bochum.de/ffm/Lehrstuehle/Lehrstuhl-VI/Workshop05.htm

2. A useful information resource for CGC

We maintain here in New York a useful information resource, called Virtual Algebra Center:

http://algebraweb.info/

Vladimir Shpilrain

3. A new key exchange protocol based on the decomposition problem

In this paper we present a new key establishment protocol based on the decomposition problem in non-commutative groups which is: given two elements w, w_1 of the platform group G and two subgroups A, B \subseteq G (not necessarily distinct), find elements a in A, b in B such that w_1 = a w b$. Here we introduce two new ideas that improve the security of key establishment protocols based on the decomposition problem. In particular, we conceal (i.e., do not publish explicitly) one of the subgroups A, B, thus introducing an additional computationally hard problem for the adversary, namely, finding the centralizer of a given finitely generated subgroup.

http://arXiv.org/abs/math/0512140

Vladimir Shpilrain and Alexander Ushakov

4. A Practical Attack on the Root Problem in Braid Groups

Cryptology ePrint Archive: Report 2005/459 http://eprint.iacr.org/2005/459

Anja Groch, Dennis Hofheinz, and Rainer Steinwandt

Using a simple heuristic approach to the root problem in braid groups, we show that cryptographic parameters proposed in this context must be considered as insecure. In our experiments we can, often within seconds, extract the secret key of an authentication system based on the root problem in braid groups.

5. Recent doctoral dissertations in the field

Xiaowei Xu, Cryptographic Systems Using Linear Groups


Abstract:

The objective of my thesis is to propose and discuss some new public-key encoding and zero-knowledge protocols based on matrix groups over polynomial rings. One of the key aspects of these protocols is the use of a rewriting system, known as the method of Reidemeister and Schreier, which is common in group theory but not used until now in cryptography. In this talk, we will explore how to use groups of matrices over polynomial rings in cryptography. This will involve solving various group-theoretic problems and the difficulty of solving various polynomial equations. This will allow us to propose various new public-key encoding and zero-knowledge protocols.

Instead of using protocols based on number theory, we will devise protocols based on groups of matrices, whose entries consist of polynomials in a number of variables. The groups involved will be free groups and we use the free generators as letters in an alphabet which permit the encoding of messages in terms of matrices. We then transform these matrices into 2X2 integral matrices of determinant 1. The Euclidean algorithm and the method of Reidemeister-Schreier alluded to above, and then enable us to decode the given messages.

We describe two cryptography schemes based on combinatorial group theory. We will discuss the underlying theory and provide some explicit examples. We suggest that combinatorial group theory could be the next generation platform in the development of cryptography because it is more general and more flexible to take advantage of dynamic algebraic structures instead of static arithmetic. Our various schemes are based on more than one secret element and break one doesn't break the whole scheme. We have developed some polynomial matrix software and utilize the software to investigate our protocols.

Related Publications:

  • G. Baumslag, B. Fine and X.Xu, A Proposed Public Key Cryptosystem, to appear.
  • G. Baumslag, B. Fine and X.Xu, Linear Group Cryptosystems, Proceedings of Algebraic Cryptography 2005.
  • S. Shankar, S. Asa, V. Sipos and X. Xu, Reasoning about RealTime State charts in the Presence of Semantic Variations, ACM International Conference on Automated Software Engineering 2005.
  • X. Xu, S. D. Dexter and A. M. Eskicioglu, A hybrid scheme for encryption and watermarking, Security, Steganography, and Watermarking of Multimedia Contents 2004, 725-736.
  • S. Shankar and V. Sipos and X. Xu, Model Checking Concurrent Real-Time State charts, First Conference on the Principles of Software Engineering 2004.
  • S. Shankar and X. Xu, Automating Object-Oriented Software Refactoring, Software Engineering Research and Practice 2003, 561-567.

http://web.gc.cuny.edu/Computerscience/EXAMS/DISSERTATIONS/2005-12-19XXui.htm

Michael Anshel


Dmitry Bormotov, Algorithms for Solving Hard Problems in Group Theory


Abstract:

In this thesis we developed some methods of a new emerging area of mathematics, which we call experimental algebra. We designed new algorithms, both deterministic and heuristic, aimed at hard problems in algebra. Using these algorithms we solved some open problems in groups and semigroups. These algorithms are implemented and organized in a package. In addition to implementations of stand-alone algorithms for solving particular problems, the package contains a variety of reusable components - tools that can be used to modify the behavior of existing algorithms, to form alternative strategies and to build new algorithms out of provided components.

The results of the package include:

  • genetic algorithms for solving equations in free groups and free semigroups;
  • effective deterministic algorithm for finding all solutions of one-variable equations in free groups;
  • solving the Genus problem;
  • classifying primitive elements in a free group;
  • evaluating and attacking Dehornoy forms;
  • key hiding system based on braid groups.

Related Publications:

  • "Experimenting with Primitive Elements in F_2," Contemporary Mathematics, Volume 349, 2004.
  • "Genetic algorithms and Equations in Free Groups and Semigroups" (with Richard F. Booth and Alexandre V. Borovik), Contemporary Mathematics, Volume 349, 2004.
  • "Effective algorithm for finding all solutions of one-variable equations in free groups" (with Robert H. Gilman and Alexei G. Myasnikov), submitted.

http://web.gc.cuny.edu/Computerscience/EXAMS/DISSERTATIONS/DD-5-6-05_Bormotov.html

Michael Anshel

← previous
next →
loading
sending ...
New to Neperos ? Sign Up for free
download Neperos App from Google Play
install Neperos as PWA

Let's discover also

Recent Articles

Recent Comments

guest's profile picture
@guest
10 Nov 2024
الاسم : جابر حسين الناصح - السن :٤٢سنه - الموقف من التجنيد : ادي الخدمه - خبره عشرين سنه منهم عشر سنوات في كبرى الشركات بالسعوديه وعشر سنوات ...

lostcivilizations's profile picture
Lost Civilizations (@lostcivilizations)
6 Nov 2024
Thank you! I've corrected the date in the article. However, some websites list January 1980 as the date of death.

guest's profile picture
@guest
5 Nov 2024
Crespi died i april 1982, not january 1980.

guest's profile picture
@guest
4 Nov 2024
In 1955, the explorer Thor Heyerdahl managed to erect a Moai in eighteen days, with the help of twelve natives and using only logs and stone ...

guest's profile picture
@guest
4 Nov 2024
For what unknown reason did our distant ancestors dot much of the surface of the then-known lands with those large stones? Why are such cons ...

guest's profile picture
@guest
4 Nov 2024
The real pyramid mania exploded in 1830. A certain John Taylor, who had never visited them but relied on some measurements made by Colonel H ...

guest's profile picture
@guest
4 Nov 2024
Even with all the modern technologies available to us, structures like the Great Pyramid of Cheops could only be built today with immense di ...

lostcivilizations's profile picture
Lost Civilizations (@lostcivilizations)
2 Nov 2024
In Sardinia, there is a legend known as the Legend of Tirrenide. Thousands of years ago, there was a continent called Tirrenide. It was a l ...

guest's profile picture
@guest
2 Nov 2024
What is certain is that the first Greek geographer to clearly place the Pillars of Hercules at Gibraltar was Eratosthenes (who lived between ...

guest's profile picture
@guest
1 Nov 2024
Disquieting thc drinks has been quite the journey. As someone keen on unpretentious remedies, delving into the in every respect of hemp has ...
Neperos cookies
This website uses cookies to store your preferences and improve the service. Cookies authorization will allow me and / or my partners to process personal data such as browsing behaviour.

By pressing OK you agree to the Terms of Service and acknowledge the Privacy Policy

By pressing REJECT you will be able to continue to use Neperos (like read articles or write comments) but some important cookies will not be set. This may affect certain features and functions of the platform.
OK
REJECT