CGC Bulletin 19
Contents
- 0. Cryptanalysis of the Algebraic Eraser and short expressions of permutations as products
- 1. New Combinatorial Complete One-Way Functions
- 2. Generic case complexity and One-Way functions
- 3. Knapsack cryptosystems built on NP-hard instance
- 4. Graph braid groups and right-angled Artin groups
- 5. Mathematical Methods in Computer Science 2008 (MMICS 2008)
Boaz Tsaban
Bulletin's webpage: http://www.cs.biu.ac.il/~tsaban/CGC/cgc.html
---
0. Cryptanalysis of the Algebraic Eraser and short expressions of permutations as products
Arkadius Kalka, Mina Teicher, Boaz Tsaban
On March 2004, Anshel, Anshel, Goldfeld, and Lemieux introduced the _Algebraic Eraser_scheme for key agreement over an insecure channel. This scheme is based on semidirect products of algebraic structures, and uses a novel hybrid of infinite and finite noncommutative groups. They also introduced the_Colored Burau Key Agreement Protocol (CBKAP)_, a concrete realization of this scheme. We present an efficient method to extract the shared key out of the public information provided by CBKAP, assuming that the keys are chosen with standard distributions.
Our methods come from probabilistic group theory, and seem to have not been used before in cryptanalysis. Of independent interest may be a simple heuristic algorithm we propose for finding short expressions of permutations as products of given random permutations. According to heuristic analysis supported by experiments, our algorithm gives expressions of length O(n^2log n) in running time O(n^4log n).
http://arxiv.org/abs/0804.0629
1. New Combinatorial Complete One-Way Functions
Arist Kojevnikov, Sergey I. Nikolenko
Proceedings of the 25th Annual Symposium on the Theoretical
Aspects of Computer Science - STACS 2008, Bordeaux : France (2008)
In 2003, Leonid A. Levin presented the idea of a combinatorial complete one-way function and a sketch of the proof that Tiling represents such a function. In this paper, we present two new one-way functions based on semi-Thue string rewriting systems and a version of the Post Correspondence Problem and prove their completeness. Besides, we present an alternative proof of Levin's result. We also discuss the properties a combinatorial problem should have in order to hold a complete one-way function.
http://arxiv.org/abs/0802.2863
2. Generic case complexity and One-Way functions
Alex D. Myasnikov
The goal of this paper is to introduce ideas and methodology of the generic case complexity to cryptography community. This relatively new approach allows one to analyze the behavior of an algorithm on ''most'' inputs in a simple and intuitive fashion which has some practical advantages over classical methods based on averaging. We present an alternative definition of one-way function using the concepts of generic case complexity and show its equivalence to the standard definition. In addition we demonstrate the convenience of the new approach by giving a short proof that extending adversaries to a larger class of partial algorithms with errors does not change the strength of the security assumption.
http://arxiv.org/abs/0802.3734
3. Knapsack cryptosystems built on NP-hard instance
Laurent Evain
We construct three public key knapsack cryptosystems. Standard knapsack cryptosystems hide easy instances of the knapsack problem and have been broken. The systems considered in the article face this problem: They hide a random (possibly hard) instance of the knapsack problem. We provide both complexity results (size of the key, time needed to encypher/decypher...) and experimental results. Security results are given for the second cryptosystem (the fastest one and the one with the shortest key). Probabilistic polynomial reductions show that finding the private key is as difficult as factorizing a product of two primes. We also consider heuristic attacks. First, the density of the cryptosystem can be chosen arbitrarily close to one, discarding low density attacks. Finally, we consider explicit heuristic attacks based on the LLL algorithm and we prove that with respect to these attacks, the public key is as secure as a random key.
http://arxiv.org/abs/0803.0845
4. Graph braid groups and right-angled Artin groups
Jee Hyoun Kim, Ki Hyoung Ko, Hyo Won Park
We give a necessary and sufficient condition for a graph to have a right-angled Artin group as its braid group for braid index $\ge 5$. In order to have the necessity part, graphs are organized into small classes so that one of homological or cohomological characteristics of right-angled Artin groups can be applied. For lower braid indices, we give few conjectures.
http://arxiv.org/abs/0805.0082
5. Mathematical Methods in Computer Science 2008 (MMICS 2008)
December 17-19, 2008, Karlsruhe, Germany
http://iks.ira.uka.de/mmics/
The "Mathematical Methods in Computer Science" conference will be held in memory of Thomas Beth. Its scope is defined by the research areas of Thomas Beth. Topics of interest include, but are not restricted to:
- Coding Theory
- Cryptography
- Design Theory
- Quantum Information
- Signal Processing
- Symbolic Computation
SUBMISSIONS
Authors are invited to submit original, unpublished papers (at most 20 pages long) in PDF format using the MMICS`08 submission page, at the EasyChair conference system. Authors are encouraged to use the Springer llncs class files. The necessary style files and instructions can be found at http://www.springer.de/comp/lncs/authors.html. The submission page for MMICS`08 is http://www.easychair.org/conferences/?conf=mmics08 All submissions will be reviewed by at least two referees. A blind review process will be enforced, thus AUTHORS SHOULD NOT REVEAL AUTHORSHIP DIRECTLY OR INDIRECTLY THROUGH REFERENCES.
CONFERENCE PROCEEDINGS
Proceedings will be published in Springer's Lecture Notes in Computer Science series (as a commemorative LNCS Festschrift). They will be available at the conference. Only accepted papers whose authors have registered at the date of receipt of the final version will appear in the proceedings.
IMPORTANT DATES
Submission: July 20th, 2008
Notification: September 10th, 2008
Final Version: October 13th, 2008
ORGANIZERS
Jacques Calmet, Willi Geiselmann, Joern Mueller-Quade, Universitaet Karlsruhe, Germany
PROGRAM COMMITTEE
Bruno Buchberger, RISC Linz, Austria
Jacques Calmet, Universitaet Karlsruhe, Germany
Reiner Creutzburg, Brandenburg University of Applied Sciences, Germany
Willi Geiselmann, Universitaet Karlsruhe, Germany
Dieter Gollmann, Technische Universitaet Hamburg-Harburg, Germany
Maria Isabel Gonzalez Vasco, Universidad Rey Juan Carlos, Madrid, Spain
Markus Grassl, Oesterreichische Akademie der Wissenschaften, Austria
Hideki Imai, Research Center for Information Security, AIST, Japan
Dominik Janzing, Max Planck Institute for Biological Cybernetics, Tuebingen, Germany
Dieter Jungnickel, Universitaet Augsburg, GermanyAndreas Klappenecker, Texas A&M University
Wolfgang Mathis, Universitaet Hannover, Germany
Joern Mueller-Quade, Universitaet Karlsruhe, Germany (Program Chair)
Harald Niederreiter, National University of Singapore
Markus Pueschel, Carnegie Mellon University, USA
Rainer Steinwandt, Florida Atlantic University, USA
Felix Ulmer, Universite Rennes 1, France
Roland Vollmar, Universitaet Karlsruhe, Germany
Submitted by Rainer Steinwandt
---
End of Issue
