CGC Bulletin 12

eZine lover (@eZine)

Published in

CGC Bulletin

· 11 months ago

Using finite non-abelian p-groups in the MOR cryptosystem
An L(1/3+epsilon) Algorithm for the Discrete Logarithm Problem for Low Degree Curves
What is the Inverse of Repeated Square and Multiply Algorithm?
An Introduction to Quantum Computing for Non-Physicists
A Proof of the Security of Quantum Key Distribution
Registration deadline for the CGC courses in CRM
International conference on Geometic and Combinatorial Group Theory with Applications (GCGTA)

Bulletin's webpage: http://www.cs.biu.ac.il/~tsaban/CGC/cgc.html

Boaz Tsaban

1. Using finite non-abelian p-groups in the MOR cryptosystem

Ayan Mahalanobis

The MOR cryptosystem is a natural generalization of the El-Gamal cryptosystem to non-abelian groups. Using a p-group, a cryptosystem was built by this author in 'A simple generalization of El-Gamal cryptosystem to non-abelian groups'. It seems reasonable to assume the cryptosystem is as secure as the El-Gamal cryptosystem over finite fields. A natural question arises can one make a better cryptosystem using p-groups? In this paper we show that the answer is no.

http://arXiv.org/abs/cs/0702095

2. An L(1/3+epsilon) Algorithm for the Discrete Logarithm Problem for Low Degree Curves

Andreas Enge and Pierrick Gaudry

The discrete logarithm problem in Jacobians of curves of high genus g over finite fields \FF_q is known to be computable with subexponential complexity L_{q^g}(1/2, O(1)). We present an algorithm for a family of plane curves whose degrees in X and Y are low with respect to the curve genus, and suitably unbalanced. The finite base fields are arbitrary, but their sizes should not grow too fast compared to the genus. For this family, the group structure can be computed in subexponential time of L_{q^g}(1/3, O(1)), and a discrete logarithm computation takes subexponential time of L_{q^g}(1/3+\epsilon, o(1)) for any positive \epsilon. These runtime bounds rely on heuristics similar to the ones used in the number field sieve or the function field sieve algorithms.

http://arXiv.org/abs/cs/0703032

3. What is the Inverse of Repeated Square and Multiply Algorithm?

H. Gopalkrishna Gadiyar, K. M. Sangeeta Maini, and R. Padma

It is well known that the repeated square and multiply algorithm is an efficient way of modular exponentiation. The obvious question to ask is if this algorithm has an inverse which would calculate the discrete logarithm efficiently. The technical hitch is in fixing the right sign of the square root and this is the heart of the discrete logarithm problem over finite fields of characteristic not equal to 2. In this paper a couple of probabilistic algorithms to compute the discrete logarithm over finite fields are given by bypassing this difficulty. One of the algorithms was inspired by the famous 3x+1 problem.

Analysis of the algorithms shows that these algorithms are of square root type like the baby step-giant step method, Pollards rho method etc.

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

4. An Introduction to Quantum Computing for Non-Physicists

Eleanor G. Rieffel, Wolfgang Polak

Richard Feynman's observation that quantum mechanical effects could not be simulated efficiently on a computer led to speculation that computation in general could be done more efficiently if it used quantum effects. This speculation appeared justified when Peter Shor described a polynomial time quantum algorithm for factoring integers. In quantum systems, the computational space increases exponentially with the size of the system which enables exponential parallelism. This parallelism could lead to exponentially faster quantum algorithms than possible classically. The catch is that accessing the results, which requires measurement, proves tricky and requires new non-traditional programming techniques. The aim of this paper is to guide computer scientists and other non-physicists through the conceptual and notational barriers that separate quantum computing from conventional computing. We introduce basic principles of quantum mechanics to explain where the power of quantum computers comes from and why it is difficult to harness. We describe quantum cryptography, teleportation, and dense coding. Various approaches to harnessing the power of quantum parallelism are explained, including Shor's algorithm, Grover's algorithm, and Hogg's algorithms. We conclude with a discussion of quantum error correction.

http://arxiv.org/abs/quant-ph/9809016

5. A Proof of the Security of Quantum Key Distribution

Eli Biham, Michel Boyer, P. Oscar Boykin, Tal Mor, and Vwani Roychowdhury

We prove the security of theoretical quantum key distribution against the most general attacks which can be performed on the channel, by an eavesdropper who has unlimited computation abilities, and the full power allowed by the rules of classical and quantum physics. A key created that way can then be used to transmit secure messages such that their security is also unaffected in the future.

http://arXiv.org/abs/quant-ph/0511175

6. Registration deadline for the CGC courses in CRM

Recall that the deadline for registration to the CRM Advanced Course on Group-Based Cryptography is April 27. More details at Issue 9: http://www.cs.biu.ac.il/~tsaban/CGC/Issues/CGC9.txt

7. International conference on Geometic and Combinatorial Group Theory with Applications (GCGTA)

DATES/PLACE: August 27^th to August 31^st, 2007, in the campus of the University of Dortmund (Fachbereich Mathematik), Dortmund, Germany.

WEB SITE: http://www.mathematik.uni-dortmund.de/~gcgta/

TOPICS: The conference is devoted to a variety of topics in Geometric and Combinatorial Group Theory, including asymptotic and probabilistic methods, as well as algorithmic and computational aspects of group theory. More specifically, this includes but is not limited to: combinatorial methods, group actions, hyperbolicity, quasi-isometries, isoperimetric functions, growth, asymptotic invariants, random walks, algorithmic problems related to groups, etc.

To emphasize applications of combinatorial and asymptotic group theory, and to highlight recent developments in "group based cryptography", we will devote a half a day to this subject: August 29^th will be the "Cryptography Day". We are planning a cultural program at the evening of August 29^th.

INVITED SPEAKERS

Martin Bridson, Imperial College London (Great Britain): TBA
Peter Brinkmann, City College of New York (USA): An efficient algorithm for automorphisms of free groups
Dima Grigor'ev, University of Rennes (France): A universal cryptosystem. (To be confirmed)
Vincent Guirardel, Universite Paul Sabatier de Toulouse (France): Makanin's algorithm for virtually free groups and the isomorphism problem for hyperbolic groups with torsion
Jim Howie, Heriot-Watt University of Edinburgh (Great Britain): One-relator quotients of limit groups.(To be confirmed)
Gilbert Levitt, Universite de Caen (France): JSJ splittings and generalized Baumslag-Solitar groups
Alexei Miasnikov, McGill University (Canada): Group actions, infinite words, and non-standard Cayley graphs
Vladimir Shpilrain, City College of New York (USA): New trends in public-key cryptography
Boaz Tsaban, Weizmann Institute of Science (Israel): A closer look at length-based algorithms
Enric Ventura, Universitat Politecnica de Catalunya and Centre de Recerca Matematica (Spain): Orbit decidability and the conjugacy problem

Additionally, there will be a possibility for participants to give contributed talks (20-40 min).

REGISTRATION: To register for the conference, please visit the web page and follow the instructions there. Note that the deadline to register is April 27^th. Registration fee is 40 Euros, to be paid in cash upon arrival.

FINANCIAL SUPPORT: Some partial financial support can be provided to young researchers, graduate students, and researchers coming from underdeveloped countries. The form of the support given (free registration, partial or free accommodation), as well as the total amount, will depend on the number of applications and the total funds available.

ORGANIZING COMMITTEE

O. Bogopolski (coordinator) (Universitat Dortmund, Germany)
B. Fine (Fairfield University, USA)
G. Rosenberger (Universitat Dortmund, Germany)
V. Shpilrain (City College of New York, USA)
E. Ventura (Universitat Politecnica de Catalunya, Spain)

SCIENTIFIC COMMITTEE

O. Bogopolski (Universitat Dortmund, Germany)
A. Miasnikov (McGill University, Canada)
A. Ol'shanskij (Vanderbilt University, USA)
G. Rosenberger (Universitat Dortmund, Germany)
V. Shpilrain (City College of New York, USA)

MORE INFORMATION: For more information, please contact O. Bogopolski (gcgta@mathematik.uni-dortmund.de) or V. Shpilrain (shpil@groups.sci.ccny.cuny.edu), concerning the cryptography day.