login

Program

The PDF version of the program can be downloaded here.

Thursday, 10 June

9:00 - 9:10Openning
9:10 - 10:00Simon Blackburn
Group theory and cryptography slides
10:00 - 10:10Break
10:00 - 10:35Pavol Zajac
Algebraic cryptanalysis in practice
10:45 - 11:15Coffee break
11:15 - 11:35 Sugata Gangopadhyay, Brajesh Kumar Singh
On second-order nonlinearities of some D0 type bent functions slides
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:40Katalin 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:50Jerzy Kaczorowski
L-function and cryptography slides
9:50 - 10:00Break
10:10 - 10:45Martin Hlaváč
Attacking RSA-CRT with Montgomery, from Schindler to Fourier slides
10:35 - 11:05Coffee break
11:05 - 11:25Maciej Grześkowiak
Algorithm for generating primes p and q such that q divides p4±p3+p2±p+1 slides
11:25 - 11:45Sedat Akleylek, Murat Cenk, Ferruh Özbudak
A New Representation of Elements of Binary Fields with Subquadratic Space Complexity Multiplication slides
11:45 - 12:05Urszula Romanczuk, Vasyl Ustimenko
On the similarity of two pairs of matrices and key exchange protocols
12:05 - 12:25Vasyl Ustimenko, Aneta Wróblewska
On the key exchange via cubical polynomials slides
12:45Bus to Poznań
14:00Lunch(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:20Michal Rjaško, Martin Stanek
Attacking M&M Collective Signature Scheme slides
9:20 - 9:40Konrad Durnoga
Applications of the Deniable Encryption Scheme slides
9:40 - 10:00László Csirmaz, Péter Ligeti, Gábor Tardos
On infinite secret sharing schemes slides
10:00 - 10:10Break
10:10 - 10:30Krzysztof Chmiel, Anna Grocholewska-Czuryło, Janusz Stokłosa
Scalable involutional PP-1 block cipher for limited resources slides
10:30 - 10:50Bernadin Ibrahimpašic
LUC vs KMOV slides
10:50 - 11:20Coffee break
11:20 - 11:55László Mérai
Pseudorandom binary sequences from elliptic curves slides
11:55 - 12:30Krystian Matusiewicz
Groestl - a SHA-3 candidate slides
12:30 - 12:40Closing
13:00Lunch

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 = md 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.