Organized by RICAM (Radon Institute for Computational and Applied Mathematics)
in close cooperation with RISC (Research Institute for Symbolic Computation).
Directed by Bruno Buchberger (RISC and RICAM) and Heinz Engl (RICAM).

Workshop D1: Gröbner Bases in Cryptography, Coding Theory, and Algebraic Combinatorics

Date: May 01 - May 06
Chairmen: Mikhail Klin, Ludovic Perret, Max Sala

The workshop is organized in the framework of the Special Semester on Groebner Bases at RICAM and RISC, Austria (see The workshop is divided into three consecutive sessions: Coding (1-2 May), Cryptography (3-4 May) and Algebraic Combinatorics (4 May late afternoon - 6 May). On 30 May, we will be honoured by a starting lecture on Groebner bases by Bruno Buchberger (founder of the method).

The goal of this workshop is to bring experts in three different areas together with a community of people working in Groebner bases. All sides need to understand the computational interests and current possibilities of each other.

The Coding part is structured as a two-day tutorial on Algebraic Coding theory and Groebner basis techniques that can be used in this context. The main research event of this part is the poster session.

The Crypto part mainly consists of a number of invited talks, plus a poster session jointly with the AC part. It concentrates on all aspects of Groebner bases in Cryptography, including recent advances in this area.

The AC part consists of invited talks covering a wide range of aspects of AC, especially those computational aspects where Groebner basis techniques might provide significant advances. The poster session is jointly with the Crypto part.

Sunday, April 30, morning-afternoon

Special Lecture

Sunday, April 30
Location: HF 9901, Campus Linz. See map.
18.00-18.45B. BuchbergerTutorial on Groebner Bases for Newcomers I
19.15-20.00B. BuchbergerTutorial on Groebner Bases for Newcomers II

Coding Session, First Poster Session:

Monday, May 01, morning: "Groebner bases and Cyclic Codes"
Location: 'Managment Zentrum' building, Campus Linz. See map.
09.15-09.30B. BuchbergerKick-Off: Salutatory
09.30-10.10E. Betti, E. OrsiniIntroduction to cyclic codes
10.20-11.00T. Mora, E. OrsiniDecoding cyclic codes: the Cooper philosophy
11.30-12.10M. SalaA theory for the distance of cyclic codes
12.20-13.00D. AugotInterpolation based decoding of Reed-Muller codes



Monday, May 01, afternoon: "AG Goppa Code"
15.30-16.10D. LeonardIntroduction to AG Goppa codes
16.30-17.20J. LittleGroebner bases for encoding of codes from order domains
17.30-18.10O. GeilSome interesting families of AG Goppa codes

Tuesday, May 02, morning: "Combinatorial approach to zero-dimensional ideals"
Location: 'Uni Centre' building, Campus Linz. See map.
09.00-09.45S. SakataOn the Berlekamp-Massey-Sakata algorithm
09.55-10.35T. MoraMoeller's Algorithm
11.00-11.40J.C. FaugèreComputation of Gb by change of ordering: comparing the efficiency of several algorithms
11.50-12.30T. Mora A survey on combinatorial duality approach: Cerlinaco--Mureddu Algorithm, the Axis-of-Evil Theorem, Macaulay's Algorithm, Noether Decomposition


Tuesday, May 02, afternoon: "Combinatorial approach to Groebner bases and coding theory"
14.15-15.00S. SakataApplication of the BMS algorithm to decoding of codes from algebraic curves
15.10-15.50B. TragerBurst Error correction for Reed Solomon Codes
16.20-17.00H. O'Keeffe, P. FitzpatrickA Groebner basis approach to list decoding of Reed-Solomon and Algebraic Geometry Codes
17.10-17.25M. SalaRelations between bounds on the distance of cyclic codes and FGLM decoding
17.25-17.40D. LeonardA module view of integral closure
17.40-17.55O. GeilTwo applications of the footprint bound

Cryptography Session:

Wednesday, May 03
Location: Castle of Hagenberg (the site of RISC), Hagenberg (shuttle busses will be provided free of charge). See RISC web-page.
09.00-09.25L. PerretWhy Can Groebner Bases Be Used in Cryptology ?
09.30-10.10O. BilletMultivariate Cryptography: An Overview
10.35-11.25J.-C. FaugèreThe F5 and FGLM algorithms : Applications to HFE and Sflasfh
11.35-12.15C. DiemOn the Subexponentiality of the Elliptic Curve Discrete Logarithm Problem over Extension Fields
14.00-14.25F. Levy-dit-VehelAlgebraic Decoding of Rank Metric Codes
14.35-15.15M. KreuzerGrobner Basis Cryptosystems
15.35-16.15T. Rai, S. BulyginCountering Chosen-Ciphertext Attacks against Noncommutative Polly Cracker-type Cryptosystems
16.25-17.05H. ParkSecurity of GB Cryptosystems and Castelnuovo-Mumford Regularity
18.15-18.25B. BuchbergerShort Introduction to RISC and Softwarepark Hagenberg
18.25-19.15L. PerretGrobner Bases in Cryptography: A Personal View
19.15Buffet Dinner

Thursday, May 04
Location: 'Uni Centre' building, Campus Linz. See map.
09.30-10.20C. CidAlgebraic Anaysis of the AES
10.30-11.10R.-P. WeinmannBlock Cipher Sensitive to Groebner Bases
11.35-12.25F. ArmknechtA Survey of Algebraic Attacks against Stream Ciphers
14.00-14.40M. SugitaImplementation of F4 algorithm, and Experimental Cryptanalysis of Toyocrypt and 58-round SHA-1 using Groebner Bases
14.50-16.00Panel Discussion on "Groebner Bases in Cryptography: What's the Future?"

Algebraic Combinatorics session:

16.30-17.30M. KlinTutorial Coherent configurations and association schemes, Part I: Definitions, examples, simple facts
17.40-18.30A. HulpkeGroebner Bases and related methods in Group Theory mov
20.30-22.00Joint poster session on Cryptography and Algebraic Combinatorics

Friday, May 05
Location: 'Uni Centre' building, Campus Linz. See map.
10.00-11.00M. MuzychukTutorial Coherent configurations and association schemes, Part II: Spectral properties and mergings of classes
11.25-12.05E. BannaiSpherical packings and association schemes, Part I
12.10-13.00A. SaliGroebner Bases and Extremal Combinatorics, Part I: Combinatorial aspects
14.30-15.30C. PechTutorial Coherent configurations and association schemes, Part III: Galois correspondence between permutation groups and coherent configurations
15.40-16.30G. JonesComputational problems arising from dessins d'enfants
16.55-17.45G.E. MoorhouseApproaching Some Problems in Finite Geometry through Algebraic Geometry
17.55-18.35I. PonomarenkoIsomorphism problem for finite combinatorial objects via coherent configurations

Saturday, May 06
Location: 'Uni Centre' building, Campus Linz. See map.
09.30-10.20V. WelkerGroebner bases with spherical or polytopal initial ideal
10.45-11.25E. Martinez-MoroMattson-Solomon transform and Groebner bases: applications to association schemes and codes
11.35-12.15E. BannaiSpherical packings and association schemes, Part II
12.20-13.00S. ReichardNew ideas in enumeration of coherent subalgebras of a prescribed coherent algebra
14.30-15.20L. RonyaiGroebner Bases and Extremal Combinatorics, Part II: Algebraic aspects
15.30-16.20A. JurisicClassification of triangle-free distance regular graphs (with small application of Groebner bases)
16.45-17.25I. MiyamotoPerformance of the GAP-function Normalizer and an attempt of its improvement
17.30-18.20J. BackelinNon-commutative Gröbner bases, viewed formally or as applied combinatorial algebra.
18.30-19.00Optional: A short concluding discussion
END of workshop D1 not later than on 19:15
Information | Application | Program | Location | Bibliography | Knowledge | Service| Links Webmaster