Cryptographie symétrique | EPFL Graph Search

vignette|320x320px|Schéma du chiffrement symétrique: la même clé est utilisée pour le chiffrement et le déchiffrement La cryptographie symétrique, également dite à clé secrète (par opposition à la cryptographie asymétrique), est la plus ancienne forme de chiffrement. Elle permet à la fois de chiffrer et de déchiffrer des messages à l'aide d'un même mot clé. On a des traces de son utilisation par les Égyptiens vers 2000 av. J.-C. Plus proche de nous, on peut citer le chiffre de Jules César, dont le ROT13 est une variante. Clé et sécurité L'un des concepts fondamentaux de la cryptographie symétrique est la clé. Une clé est une donnée qui (traitée par un algorithme) permet de chiffrer et de déchiffrer un message. Toutes les méthodes de chiffrement n'utilisent pas de clé. Le ROT13, par exemple, n'a pas de clé. Quiconque découvre qu'un message a été codé avec cet algorithme peut le déchiffrer sans autre information. Une fois l'algorithme découvert, tous les messages chiffrés p

Implications of Position in Cryptography

Handan Kilinç Alper

In our daily lives, people or devices frequently need to learn their location for many reasons as some services depend on the absolute location or the proximity. The outcomes of positioning systems can have critical effects e.g., on military, emergency. Thus, the security of these systems is quite important. In this thesis, we concentrate on many security aspects of position in cryptography. The first part of this thesis focuses on the theory of distance bounding. A distance bounding protocol is a two-party authentication protocol between a prover and a verifier which considers the distance of the prover as a part of his/her credential. It aims to defeat threats by malicious provers who try to convince that they are closer to the verifier or adversaries which seek to impersonate a far-away prover. In this direction, we first study the optimal security bounds that a distance bounding protocol can achieve. We consider the optimal security bounds when we add some random delays in the distance computation and let the prover involve distance computation. Then, we focus on solving the efficiency problem of public-key distance bounding because the public-key cryptography requires much more computations than the symmetric-key cryptography. We construct two generic protocols (one without privacy, one with) which require fewer computations on the prover side compared to the existing protocols while keeping the highest security level. Then, we describe a new security model involving a tamper-resistant hardware. This model is called the secure hardware model (SHM). We define an all-in-one security model which covers all the threats of distance bounding and an appropriate privacy notion for SHM. The second part of this thesis is to fill the gap between the distance bounding and its real-world applications. We first consider contactless access control. We define an integrated security and privacy model for access control using distance bounding (DB) to defeat relay attacks. We show how a secure DB protocol can be converted to a secure contactless access control protocol. Regarding privacy (i.e., keeping anonymity in a strong sense to an active adversary), we show that the conversion does not always preserve privacy, but it is possible to study it on a case by case basis. Then, we consider contactless payment systems. We design an adversarial model and define formally the contactless payment security against malicious cards and malicious terminals. Accordingly, we design a contactless payment protocol and show its security in our security model. The last part of this thesis focuses on positioning. We consider two problems related to positioning systems: localization and proof of location. In localization, a user aims to find its position by using a wireless network. In proof of location, a user wants to prove his/her position e.g., to have access to a system or authorize itself. We first formally define the problem of localization and construct a formal security model. We describe algorithms and protocols for localization which are secure in our model. Proof of location has been considered formally by Chandran et al. in CRYPTO 2009 and it was proved that achieving security is not possible in the vanilla model. By integrating the localization and the secure hardware model, we obtain a model where we can achieve proof of location.

EPFL2018

Symmetry in design and decoding of polar-like codes

Kirill Ivanov

The beginning of 21st century provided us with many answers about how to reach the channel capacity. Polarization and spatial coupling are two techniques for achieving the capacity of binary memoryless symmetric channels under low-complexity decoding algorithms. Recent results prove that another way to achieve capacity is via symmetry, which is the case of the Reed-Muller and extended Bose-Chaudhuri-Hocquenghem (BCH) codes. However, this proof holds only for erasure channel and maximum a posteriori decoding, which is computationally intractable for the general channels.In the first part of this thesis, we talk about the performance improvements that an automorphism group of the code brings on board. We propose two decoding algorithms for the Reed-Muller codes, which are invariant under a large group of permutations and are expected to benefit the most. The former is based on plugging the codeword permutations in successive cancellation decoding, and the latter utilizes the code representation as the evaluations of Boolean monomials. However, despite the performance improvements, it is clear that the decoding complexity grows quickly and becomes impractical for moderate-length codes. In the second part of this thesis, we provide an explanation for this observation. We use the Boolean polynomial representation of the code in order to show that polar-like decoding of sufficiently symmetric codes asymptotically needs an exponential complexity. The automorphism groups of the Reed-Muller and eBCH codes limit the efficiency of their polar-like decoding for long codes, hence we either should focus on short lengths or find another way. We demonstrate that asymptotically same restrictions (although with a slower convergence) hold for more relaxed condition that we call partial symmetry. The developed framework also enables us to prove that the automorphism group of polar codes cannot include a large affine subgroup.In the last part of this thesis, we address a completely different problem. A device-independent quantum key distribution (DIQKD) aims to provide private communication between parties and has the security guarantees that come mostly from quantum physics, without making potentially unrealistic assumptions about the nature of the communication devices. After the quantum part of the DIQKD protocol, the parties share a secret key that is not perfectly correlated. In order to synchronize, some information needs to be revealed publicly, which makes this formulation equivalent to the asymmetric Slepian-Wolf problem that can be solved using binary linear error-correction codes. As any amount of the revealed information reduces the key secrecy, the utilized code should operate close to the finite-length limits. The channel in consideration is non-standard and, due to its experimental nature, it can actually slightly differ from the considered models. In order to solve this problem, we designed a simple scheme using universal SC-LDPC codes and used in the first successful experimental demonstration of DIQKD protocol.

EPFL2022

Symmetry in design and decoding of polar-like codes

Kirill Ivanov

EPFL2022

Implications of Position in Cryptography

Handan Kilinç Alper

EPFL2018