The goal of this paper is to investigate linear approximations of random functions and permutations. Our motivation is twofold. First, before the distinguishability of a practical cipher from an ideal one can be analysed, the cryptanalyst must have an accurate understanding of the statistical behaviour of the ideal cipher. Secondly, this issue has been neglected both in old and in more recent studies, particularly when multiple linear approximations are being used simultaneously. Traditional models have been based on the average behaviour and simplified using other assumptions such as independence of the linear approximations. Multidimensional cryptanalysis was introduced to avoid making artificial assumptions about statistical independence of linear approximations. On the other hand, it has the drawback of including many trivial approximations that do not contribute to the attack but just cause a waste of time and memory. We show for the first time in this paper that the trivial approximations reduce the degree of freedom of the related χ2 distribution. Previously, the affine linear cryptanalysis was proposed to allow removing trivial approximations and, at the same time, admitting a solid statistical model. In this paper, we identify another type of multidimensional linear approximation, called Davies-Meyer approximation, which has similar advantages, and present full statistical models for both the affine and the Davies-Meyer type of multidimensional linear approximations. The new models given in this paper are realistic, accurate and easy to use. They are backed up by standard statistical tools such as Pearson’s χ2 test and finite population correction and demonstrated to work accurately using practical examples.

Linear cryptanalysis introduced by Matsui is a statistical attack which exploits a binary linear relation between plaintext, ciphertext and key, either in Algorithm 1 for recovering one bit of information of the secret key of a block cipher, or in Algorithm 2 for ranking candidate values for a part of the key. The statistical model is based on the expected and observed bias of a single binary value. Multiple linear approximations have been used with the goal to make the linear attack more efficient. More bits of information of the key can potentially be recovered possibly using less data. But then also more elaborated statistical models are needed to capture the joint behaviour of several not necessarily independent binary variables. Also more options are available for generalising the statistics of a single variable to several variables. The multidimensional extension of linear cryptanalysis to be introduced in this paper considers using multiple linear approximations that form a linear subspace. Different extensions of Algorithm 1 and Algorithm 2 will be presented and studied. The methods will be based on known statistical tools such as goodness-of-fit test and log-likelihood ratio. The efficiency of the different methods will be measured and compared in theory and experiments using the concept of advantage introduced by Selçuk. The block cipher Serpent with a reduced number of rounds will be used as test bed. The multidimensional linear cryptanalysis will also be compared with previous methods that use biasedness of multiple linear approximations. It will be shown in the simulations that the multidimensional method is potentially more powerful. Its main theoretical advantage is that the statistical model can be given without the assumption about statistical independence of the linear approximations.

Presents the introductory welcome message from the conference proceedings.

Most contemporary security mechanisms and protocols include exchange of random or time-variant nonces as an essential means of protection against replay and other threats or as a seed for randomness. In many cases, it would be beneficial to have such nonces available from a trusted common source, such as a satellite. The goal of this paper is to present a protocol by which a loosely connected network of devices can agree on a common piece of randomness, and show how it can be applied to improve efficiency of a privacy protection system and group session key exchange for PAN/LAN devices.

In this paper, a multidimensional Walsh transform is used to obtain a characterization of vector-valued bent function in terms of the value distributions of the translates of the function by linear functions.

In a small PAN, devices are typically connected together over wireless or wired link layer technology and communication between devices is point-to-point or point-to-multipoint. In this paper, we discuss some common methods to negotiate unicast and multicast keys on MAC layer. We also present an upper layer group key management framework to facilitate flexible and secure group communication in a PAN. Our main observation is that the current MAC layer security solutions do not support well multicast communications. For improved efficiency, we propose to enhance the MAC layer security solutions with a multiparty handshake procedure.

In this paper we present a modification of the DSA which allows signatures with message recovery. The new public key signature scheme is then applied to create (a) an identity-based public key system without restrictions in trust and (b) a one-pass key exchange protocol with mutual authentication.