Copy Link

Add to Bookmark

Report

CGC Bulletin 18

eZine lover (@eZine)

Published in

CGC Bulletin

· 11 months ago

Journal of Mathematical Cryptology, Contents of Issues 3 & 4
An Improved Enumeration Scheme for Subset Sum Problem
Discrete logarithms in curves over finite fields
Discrete Groups and Geometric Structures, with Applications III
The REESSE2+ Public-key Encryption Scheme - Another Application of the Lever Function and its Connotation
Zero-knowledge authentication schemes from actions on graphs, groups, or rings
Two independent cryptanalyses of the Algebraic Eraser when it uses standard distributions
School on Algebraic Theory Of Automata
SCC 2008: Second announcement

Boaz Tsaban

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

1. Journal of Mathematical Cryptology, Contents of Issue 3 & 4

Issue 3:

D. R. Stinson and J. Wu: An efficient and secure two-flow zero-knowledge identification protocol.
Joan Daemen and Vincent Rijmen: Probability distributions of correlation and differentials in block ciphers.
P. Gaudry: Fast genus 2 arithmetic based on Theta functions.
Steven D. Galbraith, Colm O hEigeartaigh and Caroline Sheedy: Simplified pairing computation and security implications
Hassan Aly, Wilfried Meidl and Arne Winterhof: On the k-error linear complexity of cyclotomic sequences

Issue 4:

Clemens Heuberger and James A. Muir: Minimal weight and colexicographically minimal integer representations
Ian F. Blake and Igor E. Shparlinski: Statistical distribution and collisions of VSH
Su-Jeong Choi, Simon R. Blackburn and Peter R. Wild: Cryptanalysis of a homomorphic public-key cryptosystem over a finite group
Dima Ruinskiy, Adi Shamir and Boaz Tsaban: Length-based cryptanalysis: the case of Thompson's group
Sarang Aravamuthan and Sachin Lodha: The average transmission overhead for broadcast encryption
Neal Koblitz: Another look at automated theorem-proving

2. An Improved Enumeration Scheme for Subset Sum Problem

Changlin Wan

The subset sum problem (SSP) can be briefly stated as: given a target integer $E$ and a set $A$ containing $n$ positive integers, find a subset of $A$ summing to $E$. The \textit{density} $d$ of an SSP instance is defined by the ratio of $n$ to $m$, where $m$ is the logarithm of the largest integer within $A$. Based on the structural and statistical properties of subset sums, we present an improved enumeration scheme for SSP, and implement it as a complete and exact algorithm (EnumPlus). The algorithm always equivalently reduces an instance to be low-density, and then solve it by enumeration. Through this approach, we show the possibility to design a sole algorithm that can efficiently solve arbitrary density instance in a uniform way. Furthermore, our algorithm has considerable performance advantage over previous algorithms. Firstly, it extends the density scope, in which SSP can be solved in expected polynomial time. Specifically, It solves SSP in expected $O(n\log{n})$ time when density $d \geq c\cdot \sqrt{n}/\log{n}$, while the previously best density scope is $d \geq c\cdot n/(\log{n})^{2}$. In addition, the overall expected time and space requirement in the average case are proven to be $O(n^5\log n)$ and $O(n^5)$ respectively. Secondly, in the worst case, it slightly improves the previously best time complexity of exact algorithms for SSP. Specifically, the worst-case time complexity of our algorithm is proved to be $O((n-6)2^{n/2}+n)$, while the previously best result is $O(n2^{n/2})$.

http://arxiv.org/abs/0712.3203

3. Discrete logarithms in curves over finite fields

Andreas Enge (INRIA Futurs)

A survey on algorithms for computing discrete logarithms in Jacobians of curves over finite fields.

http://arxiv.org/abs/0712.3916

4. Discrete Groups and Geometric Structures, with Applications III

(Crystallographic Groups and their Generalisations V)

K.U.Leuven Campus Kortrijk, Belgium, May 26--30, 2008.

Main invited speakers:

J. Andersen (Aarhus), M. Bridson (Oxford), B. Farb (Chicago), F. Grunewald (Duesseldorf), U. Hamenstaedt (Bonn), A. Lubotzky (Jerusalem), N. Monod (Geneva), J. Parker (Durham), and Y. Shalom (Los Angeles).

All participants are invited to submit a proposal for a short talk and/or poster to the scientific committee. More particularly, the organisers hope to stimulate participation of PhD students and PostDoc researchers.

This and other practical information is now available at the conference's homepage: http://www.kuleuven-kortrijk.be/workshop

We invite in particular those who are looking for cheaper housing, e.g by sharing an appartment, to register early.

On behalf of the organising committee's

Paul Igodt and Karel Dekimpe

5. The REESSE2+ Public-key Encryption Scheme - Another Application of the Lever Function and its Connotation

Shenghui Su, Zunguo Huang, and Jun Hu

This paper gives the definitions of a nonnormal super-increasing sequence and a nonnormal subset sum separately, proves the two properties of a nonnormal super-increasing sequence, and proposes the REESSE2+ public-key encryption scheme which includes the three algorithms for key generation, encryption and decryption. The paper discusses the necessity and sufficiency of the lever function for preventing the Shamir extremum attack, analyzes the security of REESSE2+ against extracting a private key from a public key through the exhaustive search, recovering a plaintext from a ciphertext plus a knapsack of high density through the LLL lattice basis reduction method, and heuristically obtaining a plaintext through the meet-in-the-middle attack or the adaptive-chosen-ciphertext attack. The authors evaluate the time complexity of the REESSE2+ algorithms, compare REESSE2+ with ECC and NTRU, and find that the encryption speed of REESSE2+ is ten thousand times faster than ECC and NTRU bearing the matchable security, and the decryption speed of REESSE2+ is roughly equivalent to ECC and NTRU respectively.

http://arxiv.org/abs/0801.4817

6. Zero-knowledge authentication schemes from actions on graphs, groups, or rings

Dima Grigoriev (IRMAR), Vladimir Shpilrain

We propose a general way of constructing zero-knowledge authentication schemes from actions of a semigroup on a set, without exploiting any specific algebraic properties of the set acted upon. Then we give several concrete realizations of this general idea, and in particular, we describe several zero-knowledge authentication schemes where forgery (a.k.a. impersonation) is NP-hard. Computationally hard problems that can be employed in these realizations include (Sub)graph Isomorphism, Graph Colorability, Diophantine Problem, and many others.

http://arxiv.org/abs/0802.1661

7. Two independent cryptanalyses of the Algebraic Eraser when it uses standard distributions

A. Cryptanalysis of Anshel-Anshel-Goldfeld-Lemieux key agreement protocol Alex D. Myasnikov, Alexander Ushakov

B. Cryptanalysis of the Algebraic Eraser
Arkadius Kalka, Mina Teicher, and Boaz Tsaban

Comment: These two papers describe two independent works by disjoint groups of researchers, on the same public-key scheme. Each of these works describes a very successful attacks on the scheme, if the scheme uses STANDARD DISTRIBUTIONS.

The methods of these papers are different: The first mentioned paper uses a lenth-based attack (modified appropriately) to attack the generators of the system, and the second mentioned paper uses linear algebra and algorithms in permutation groups to attack the public keys of the users. Abstracts follow.

Abstracts:

A. The Anshel-Anshel-Goldfeld-Lemieux (abbreviated AAGL) key agreement protocol is proposed to be used on low-cost platforms which constraint the use of computational resources. The core of the protocol is the concept of an Algebraic Eraser (abbreviated AE) which is claimed to be a suitable primitive for use within lightweight cryptography. The AE primitive is based on a new and ingenious idea of using an action of a semidirect product on a (semi)group to obscure involved algebraic structures. The underlying motivation for AAGL protocol is the need to secure networks which deploy Radio Frequency Identification (RFID) tags used for identification, authentication, tracing and point-of-sale applications.

In this paper we revisit the computational problem on which AE relies and heuristically analyze its hardness. We show that for proposed parameter values it is impossible to instantiate the secure protocol. To be more precise, in 100% of randomly generated instances of the protocol we were able to find a secret conjugator z generated by TTP algorithm (part of AAGL protocol).

This paper is available online: http://arxiv.org/abs/0801.4786

B. On March 2004, Anshel, Anshel, Goldfeld, and Lem\-ieux 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 introduced an efficient concrete realization which they named Colored Burau Key Agreement Protocol (CBKAP). 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 the standard distributions.

Our methods use in an essential way the involvement of matrix groups in the key generation process, and a generically-efficient solution of the membership search problem in permutation groups. We indicate potential fixes of the scheme against our attack.

8. School on Algebraic Theory Of Automata

September 1-12, 2008

Centro De Algebra Da Universidade De Lisboa, Lisboa, Portugal

http://caul.cii.fc.ul.pt/SATA2008/

Dear Colleagues,

This School aims to present to the scientific communities, in particular to post-graduate students, various topics on Algebraic Theory of Automata, delivered as Courses, Advanced Seminars and Student's Seminars. It is sponsored by the Project AutomathA: from Mathematics to Applications of the European Science Foundation (ESF) and it is organized within the activities of Centro de Algebra da Universidade de Lisboa (CAUL) and Centro de Matematica da Universidade do Porto (CMUP).

The school will be held at the Complexo Interdisciplinar da Universidade de Lisboa, Av. Prof. Gama Pinto 2, in Lisbon, Portugal.

The Programme includes eight Courses on various aspects of Algebraic Theory of Automata, plus an Advanced Seminar on mainstream topics and a Student's Seminar on their research work.

INVITED LECTURERS:

Mikolaj Bojanczyk (University of Warsaw, Poland)
Zolt?n ?sik (University of Szeged, Hungary)
Daniel Kirsten (University of Leipzig, Germany)
Michal Kunc (Masaryk University, Czech Republic)
Jean-?ric Pin (University Paris 7 and CNRS, France)
Pedro Silva (University of Porto, CMUP, Portugal)
Howard Straubing (Boston College, USA)
Pascal Tesson (University of Laval, Canada)

ORGANIZING COMMITTEE:

M?rio J.J. Branco (Universidade de Lisboa, CAUL)
Manuel Delgado (Universidade do Porto, CMUP)
V?tor Hugo Fernandes (Universidade Nova de Lisboa, CAUL)
Gracinda M.S.Gomes (Universidade de Lisboa, CAUL)
Ant?nio Malheiro (Universidade Nova de Lisboa, CAUL)

SCIENTIFIC COMMITTEE:

Jorge Almeida (University of Porto, CMUP, Portugal)
Olivier Carton (University Paris VII, France)
Antonio Restivo (UNIPA, Italy)
Mikhail Volkov (Ural State University, Russia)
Thomas Wilke (University of Kiel, Germany)

FINANCIAL SUPPORT:
A limited number of scholarships for postgraduate students are available.
Applications will be accepted until 31st March 2008.

FURTHER INFORMATION:
Patricia Paraiba (Secretarial Staff)
E-mail: patricia@cii.fc.ul.pt

http://caul.cii.fc.ul.pt/SATA2008/

9. SCC 2008: First International Conference on Symbolic Computation and Cryptography

http://www.cc4cm.org/scc2008
Beijing, China, April 28-30, 2008

SECOND CALL FOR PAPERS
Extended submission deadline: February 24, 2008

SCC 2008 is the first of a new series of conferences where research and development in symbolic computation and cryptography may be presented and discussed. It is organized in response to the growing interest in applying and developing methods, techniques, and software tools of symbolic computation for cryptography. The use of lattice reduction algorithms in cryptology and the application of Groebner bases in the context of algebraic attacks are typical examples of explored applications.

SCC 2008 aims at providing an interactive forum for interested researchers to exchange ideas and views, to present research results and progress, and to learn and discuss recent developments and emerging problems on

the design, modeling, and analysis of cryptographic systems and protocols for which symbolic computation may be used or needed, and
the design, implementation, and analysis of algorithms and software tools of symbolic computation that may have potential applications in cryptography.

TOPICS

Specific topics for SCC 2008 include, but are not limited to:

Multivariate cryptography, braid group cryptography, noncommutative cryptography, and quantum cryptography
Code-based, factorization-based, and lattice-based cryptography
Algebraic attacks for block ciphers, stream ciphers, and hash functions
Design and analysis of algebraic, elliptic, and embedded cryptographic systems and protocols
Groebner basis techniques in cryptology, algebraic number theory, and coding theory
Triangular sets and new techniques for solving algebraic systems over finite fields
Algorithms and software for symbolic computation in cryptography

INVITED SPEAKERS

Bruno Buchberger (Johannes Kepler Universitaet Linz, Austria)
Adi Shamir (Weizmann Institute of Science, Israel)
Xiaoyun Wang (Tsinghua University and Shandong University, China)

SUBMISSION

Potential participants of SCC 2008 are invited to submit extended abstracts of 3-5 pages or full papers describing their work to be presented at the conference. The submitted extended abstracts and full papers will be reviewed by members of the program committee (PC) for soundness and relevance to the conference. Submission of original research papers is encouraged, while published material and work in progress will also be considered for presentation at the conference. Extended abstracts and full papers should be prepared using LaTeX with the style file available on the SCC 2008 webpage and according to the instructions given therein. Submissions must be done electronically via EasyChair at http://www.easychair.org/conferences/?conf=scc2008 or sent in PDF or PS format as e-mail attachments to scc2008 @ cc4cm.org.

Accepted extended abstracts and full papers will be printed in the proceedings of SCC 2008 for distribution at the conference.

PUBLICATION

Authors of the extended abstracts and full papers accepted for presentation at the conference will be invited to submit their full and/or revised papers for publication in special issues of Mathematics in Computer Science (MCS - http://www.cc4cm.org/mcs) by Birkhauser/Springer after the meeting. The submitted papers will be formally reviewed by PC members and external referees according to the standard refereeing procedure of MCS.

IMPORTANT DATES

Extended deadline for extended abstract submission: February 24, 2008
Notification of acceptance or rejection: March 16, 2008
Conference taking place: April 28-30, 2008
Deadline for full paper submission: June 30, 2008

GENERAL CHAIR

Zhiming Zheng (China)

PROGRAM COMMITTEE

Anne Canteaut (France) Jintai Ding (USA)
Jean-Charles Faugere, Co-chair (France) Joachim von zur Gathen (Germany)
Pierrick Gaudry (France) Jaime Gutierrez (Spain)
Hoon Hong (USA) Antoine Joux (France)
Martin Kreuzer (Germany) Dongdai Lin (China)
Zhuojun Liu (China) Alexander May (Germany)
Ludovic Perret (France) Igor Shparlinski (Australia)
Damien Stehle (France) Rainer Steinwandt (USA)
Boaz Tsaban (Israel) Dongming Wang, Co-chair (China/France)

LOCAL ARRANGEMENTS