# Program

The PDF version of the program can be downloaded here.## Thursday, 10 June

9:00 - 9:10 | Openning |

9:10 - 10:00 | Simon BlackburnGroup theory and cryptography slides |

10:00 - 10:10 | Break |

10:00 - 10:35 | Pavol Zajac Algebraic cryptanalysis in practice |

10:45 - 11:15 | Coffee break |

11:15 - 11:35 | Sugata Gangopadhyay, Brajesh Kumar SinghOn second-order nonlinearities of some D slides_{0} type bent functions |

11:35 - 11:55 | Smile Markovski, Aleksandra Mileva, Vesna Dimitrova Quasigroup String Transformations and Block Cipher Design slides |

11:55 - 12:15 | Vadym Fedyukovych Committing with partial knowledge of group order slides |

12:15 - 12:30 | Break |

12:30 - 12:50 | János Folláth Notes on a Family of Preimage-Resistant Functions slides |

12:50 - 13:10 | Michal Rjaško Combining properties of cryptographic hash functions slides |

13:15 - 15:00 | Lunch |

15:00 - 15:20 | Viktoria Toth The extension of collision and avalanche effect to pseudorandom k-ary sequences slides |

15:20 - 15:40 | Katalin Gyarmati On binary lattices slides |

15:40 - 16:00 | Andrea Huszti Security definitions for electronic exam systems slides |

16:00 - 16:30 | Coffee break |

16:30 - 16:50 | Marina Pudovkina Differential attack on one family of block ciphers based on the SPN structure slides |

16:50 - 17:10 | Piotr Mroczkowski, Janusz Szmidt The cube attack on stream cipher Trivium and quadraticity tests slides |

17:10 - 18:10 | Poster session |

18:15 - 19:00 | Dinner |

## Friday, 11 June

9:00 - 9:50 | Jerzy Kaczorowski
L-function and cryptography slides |

9:50 - 10:00 | Break |

10:10 - 10:45 | Martin Hlaváč
Attacking RSA-CRT with Montgomery, from Schindler to Fourier slides |

10:35 - 11:05 | Coffee break |

11:05 - 11:25 | Maciej Grześkowiak
Algorithm for generating primes p and q such that q divides p slides^{4}±p^{3}+p^{2}±p+1 |

11:25 - 11:45 | Sedat Akleylek, Murat Cenk, Ferruh Özbudak
A New Representation of Elements of Binary Fields with Subquadratic Space
Complexity Multiplication slides |

11:45 - 12:05 | Urszula Romanczuk, Vasyl Ustimenko
On the similarity of two pairs of matrices and key exchange protocols |

12:05 - 12:25 | Vasyl Ustimenko, Aneta Wróblewska
On the key exchange via cubical polynomials slides |

12:45 | Bus to Poznań |

14:00 | Lunch(Faculty of Mathematics and Computer Science, Adam Mickiewicz
University) |

15:30 - 16:30 | Marek Grajek
Roots of Victory |

17:00 - 19:00 | Poznań - Old Town |

20:00 - 22:00 | Party - bonfire |

## Saturday, 12 June

9:00 - 9:20 | Michal Rjaško, Martin Stanek
Attacking M&M Collective Signature Scheme slides |

9:20 - 9:40 | Konrad Durnoga
Applications of the Deniable Encryption Scheme slides |

9:40 - 10:00 | László Csirmaz, Péter Ligeti, Gábor Tardos
On infinite secret sharing schemes slides |

10:00 - 10:10 | Break |

10:10 - 10:30 | Krzysztof Chmiel, Anna Grocholewska-Czuryło, Janusz Stokłosa
Scalable involutional PP-1 block cipher for limited resources slides |

10:30 - 10:50 | Bernadin Ibrahimpašic
LUC vs KMOV slides |

10:50 - 11:20 | Coffee break |

11:20 - 11:55 | László Mérai
Pseudorandom binary sequences from elliptic curves slides |

11:55 - 12:30 | Krystian Matusiewicz
Groestl - a SHA-3 candidate slides |

12:30 - 12:40 | Closing |

13:00 | Lunch |

## Invited speakers

**Jerzy Kaczorowski** *L-functions and cryptography*

Number theory is a reach source of seemingly intractable problems, and hence a
natural place for searching candidates for one-way functions. As well known
such functions are of principal importance for constructing public key
cryptographic algorithms. On the other hand L-functions are among the most
powerful tools in analytic number theory. They are analytic objects, in fact a
kind of generating functions, reflecting pure arithmetic properties of
underlying algebraic or geometric structures. Hence there is a natural desire
for a direct use of them in cryptography. In the talk, which is addressed to
non-experts in analytic number theory, a general notion of an L-function and
its relevance to cryptography will be discussed. The talk is intended as a
promotion of this not yet sufficiently well recognized part of cryptography.

**Simon Blackburn** *Group theory and cryptography*

The talk will give a brief survey of some of the main ideas in
group-theory-based cryptography. The talk will then focus on the
cryptosystem MST_3 that works over a finite group (a proposal due to
Lempken, van Trung, Magliveras and Wei). Several attacks on MST_3 will
be presented, including those that are practical for known methods for
generating the private key. This is joint work with Carlos Cid and
Ciaran Mullan.

**Marek Grajek** *Roots of Victory*

By trade a cryptologist and computer scientist, a historian by avocation. One of the people behind the idea of a statue of Enigma-breakers, which has been erected in front of Imperial Castle in Poznań. A consultant regarding applications of cryptology in the financial world and capital markets. An author of a recently-published book "Enigma. Bliżej prawdy" ("Enigma. Closer to the Truth"),especially lauded for the innovative combination of author's knowledge of exact sciences with his love of history.

## Invited young speakers

**Martin Hlavac** *Attacking RSA-CRT with Montgomery, from Schindler to Fourier*

RSA is a widely used cryptosystem not only on system with powerful general purpose CPUs or even with cryptographic accelerators. It is also employed on small low-memory, low-speed devices such as smart cards, RFID chips, etc. Here, the computation of RSA private key operation c = m^{d} mod N is very expensive. Various methods exist that speed up the operation. This talk presents the evolution of side channel attacks against the implementations that employ Chinese Remainder Theorem (CRT) and Montgomery multiplication algorithm.

The first feasible side channel attack was introduced by Schindler in 2000. It was an adaptive chosen plaintext attack (ACPA) based on binary search for a prime factor of N. The attacker with the access to the timing side channel information was able to factorize the RSA modulus, thus completely break the scheme. RSA blinding prevents the attack.

Building on top of Schindler's result, the second attack by Tomoeda et al. overcame the necessity of the adaptive choice of the plaintexts during the attack. The assumption made here was the availability of the number of so-called extra reductions during one Montgomery exponentiation within one CRT branch. The technique employed is a simple computation of greatest common divisor (GCD). Tomoeda's CPA attack was valid also for the implementations defending themselves with RSA blinding.

In his Master thesis, Primas follows the same general outline of the attack as Tomoeda. Instead of observing as many RSA computation as necessary for successful employment of GCD algorithm, he chooses to minimize the amount of necessary observations. To do so, algorithm solving approximate GCD by Howgrave-Graham is used. The resulting attack needs 25% less observation in case with RSA blinging and 50% less without blinding. Primas also elaborates the theoretical foundations for the heuristics behind Tomoeda's conversion of Schindler's side information.

The only attack described in the talk that is not a CPA attack is the approach by Hlavac. The side channel information necessary is the same as in the case of Tomoeda, the attack needs not to choose the plaintexts, however. The main idea here is to convert the side information to the well-studied Hidden Number Problem (HNP) which is than solved using basic lattice tools, i.e. LLL algorithm.

Finaly, Ruppeldtova investigates the application of Signification Fourier Transform algorithm by Akavia and its adjustments by Vaudenay. Her approach requests far more side channel observations than the previous attacks. However, contrary to previous work the attack tolerates faults in side channel measurement and is able to handle observations with a single bit of information.

**László Mérai** *Pseudorandom binary sequences from elliptic curves*

Mauduit and Sarkozy introduced several measures to
study the pseudorandomness of binary sequences. If we apply these
measures to sequences generating by elliptic curves it turns out that
there is a large family of sequences which cannot be considered as
pseudorandom in terms of these measures. However, it can be give
some necessary and a necessary and sufficient criteria to ensure
that the sequences have good pseudorandom properties in terms
of these measures.

**Pavol Zajac** *Algebraic cryptanalysis in practice*

The design of modern ciphers still respects two main principles stated by Shannon
: diffusion and confusion. The diffusion means that the statistical
structure in a plaintext is dissipated in the statistics of a ciphertext. A weak
diffusion can be exploited by statistical cryptanalytic attacks, such as linear
(LC) and differential (DC) cryptanalysis, respectively. The confusion means
that the relation between plaintext, ciphertext and the key should be a very
complex and involved one. This translates in practice into requirements that
the cipher should be non-linear, and the equations involving plaintext, ciphertext
and key-bits should be of high algebraic degree. Various cryptanalytic
attacks on ciphers with weak confusion, can be put under the common name
algebraic cryptanalysis.

G. Bard defines algebraic cryptanalysis as a two-step process. In the first step, the cipher is converted into a (suitable) system of equations. In the second step, the equation system is solved to obtain the secret values. Depending on the application of the cryptanalytic technique, these values can represent the key, the plaintext, the state of the stream cipher in some time, the colliding pair for a compression function, etc.

It is the authors opinion that the term ”algebraic cryptanalysis” should also denote any algebraic technique, that can provide more information about the state of the cipher (i.e. the permissible keys) than the blackbox model. As opposed to ”statistical cryptanalysis” (like LA and DA), we should be able to obtain this information without the need to collect a large number of plaintextciphertext pairs. It is possible to imagine a class of mixed techniques using tools from both statistical and algebraic cryptanalysis, i.e. preparing a set of equations that can only be solved in a reasonable time with some (non-negligible) probability.

**Krystian Matusiewicz** *Gröstl - a SHA-3 candidate*

**Cryptographic Hash Functions**

Cryptographic hash functions are one of the fundamental classes of algorithms used in modern cryptography. The properties of one-waynes, collision resistance and pseudorandom behaviour make them versatile tools for a broad range of applications, from digital signature schemes through various cryptographic protocols to pseudorandom-number generators.

The main design strategy for cryptographic hash functions is to iterate a compression function that takes a larger input and returns a shorter output. When feeding the output of the previous iteration to the next step, a chunk of the input message is also processed as a part of the input.

The differences appear when it comes to the design of secure compression functions with a few alternative approaches.

The first one is to use a construction that internally uses an existing block cipher in a mode that guarantees the security of the hash function as long as the block cipher is secure.

The other approach is to base the compression function on some asymptotically intractable problem and prove that the function is secure as long as the problem is hard to solve.

Finally, the third approach is to build a dedicated compression function, quite often designing a special-purpose block cipher to be used as a part of the compression function.

The last approach, with prominent examples including MD5, SHA-1 and SHA-256 has been the dominant design strategy, mainly due to high efficiency on the most popular *x86* architecture.

However, such a monoculture turned out to be dangerous. Ingenious attacks by the team of X. Wang broke MD5, SHA-1. Quickly improved by other reseachers, they threatened many other similar hash functions.

**The NIST SHA-3 Competition**

Responding to the attacks on SHA-1 that left only one NIST-standarized function intact, National Institute of Standards and Technology called a competition to develop a new algorithm that would augment the FIPS-180 standard and replace SHA-1 over time.

NIST called for an algorithm stressing provable security of the design, high efficiency and ease of analysis and encouraged alternative constructions deviating from the MD-x family designs.

The community responded with 64 designs submitted to the competition. After the first round, 14 functions have been qualified to the second round. One of them is Gröstl, an algorithm designed by Florian Mendel, Martin Schläffer and Christian Rechberger from Technical University of Graz and Sören S. Thomsen, Lars R. Knudsen, P. Gauravaram and Krystian Matusiewicz from Technical Univerisity of Denmark.

**Gröstl**

Designing a new cryptographic hash function is an extremely challenging task. The first and foremost requirement is cryptographic security while the equally important one is good performance on a wide variety of computing platforms.

Gröstl has been designed specifically with those features in mind.

The security of the hash function is provably dependent on the ideal behaviour of two large, fixed and different permutations. The proofs show that as long as the permutations have no weaknesses, the hash function meets the ideal requirements of preimage and collision resistance as well as pseudorandom behaviour.

The permutations are constructed as an SP-network using the wide-trail strategy which ensures that Gröstl is resistant to many classes of traditional attacks. The permutations reuse AES S-box and other transformations in the round function are modeled after AES components. This design strategy allows to reuse significant amount of analysis that AES building blocks received over the years.

Due to the large internal state compared to the output size (called "wide-pipe" strategy), Gröstl is resistant to all known generic attacks on the iterated hash functions.

On its basic level, Gröstl is byte-oriented and this characteristics makes it suitable to implement on a variety of platforms without significantly favouring one platform at the expense of penalizing others.

Gröstl has already received a significant external cryptanalytic attention which is an extremely valuable addition to the results of internal cryptanalysis performed by the designers.