Cryptography and physical layer security: the role of channel coding

This thesis presents a study of channel coding techniques for security issues. Two possible applications are investigated: I) using the decoding problem as a cryptographic trapdoor in an efficient way, from the key size and complexity point of view II) the usage of channel coding techniques aimed to prevent the information eavesdropping on a public insecure channel without encryption. A quantum computer will be able to break the worldwide implemented number-theory-based cryptographic primitives, such as RSA. This could have dramatic consequences, since all the web-banking and e-commerce transactions are protected by this kind of primitives. Decoding a random linear code, is a problem that have been shown to be NP-complete and no algorithm is known to solve it, in reasonable time, even using quantum algorithm. This thesis analyzes the possible introduction of different families of linear codes (GRS and QC-LDPC) in the main code-based cryptosystem: the McEliece cryptosystem. We show how to avoid its biggest problem, the huge key size, by modifying the original system and adopting different codes, obtaining keys that are comparable with non-quantum solutions as RSA, with a reduced decrypting complexity. Moreover, the adoption of similar techniques, that is, a proper mix of scrambling and linear coding, can be used for physical layer security. In a physical layer security scheme, all the users are completely aware of all the components of the communication system, there are no secret keys: the differentiation between legitimate and unauthorized users is based only on the physical channel randomness. As an example, we can imagine a wireless router transmission, the legitimate user is inside the router's room and the eavesdropper is outside of it. The channel deterioration experienced by the attacker, since he is farther than the legitimate receiver, is small and he can correctly receive router's data. The proposed scheme allows to greatly improve the security of the system in such a way to prevent the information leakage, even if the channel difference between the two users is very small.

In questa tesi vengono analizzate due applicazioni della codifica di canale per fini di sicurezza dell'informazione: I) utilizzare il problema di decodifica come primitiva crittografica in maniera efficiente, sia dal punto di vista della dimensione delle chiavi che della complessità computazionale II) l'utilizzo di tecniche di codifica per prevenire il furto di informazioni su un canale insicuro, non protetto da schemi crittografici. Le transazioni commerciali su internet ed il web-banking sono basati su sistemi crittografici (principalmente RSA) che non resisteranno all'avvento dei computer quantistici. D'altro canto, decodificare un codice lineare generico è un problema NP e non è noto alcun algoritmo in grado di risolverlo efficientemente neanche attraverso l'utilizzo di computer quantistici . In questa tesi viene studiata l'adozione di alcune famiglie di codici lineari (GRS e QC-LDPC), come sostituti dei codici di Goppa, nel crittosistema di McEliece, che si basa su tale problema di decodifca. Verrà discusso come l'utilizzo di tali codici permetta di superare il problema che, fino ad oggi, ne ha impedito un pratico utilizzo: l'eccessiva dimensione delle chiavi pubbliche. Attraverso l'utilizzo di questi codici, e modificando il sistema originale, la dimensione delle chiavi può essere ridotta fino a valori prossimi a quelli delle soluzioni non-quantistiche (RSA), con l'ulteriore vantaggio di un costo computazionale ridotto. Tecniche simili (l'uso di codici lineari e scrambling dell'informazione) possono essere adottate anche in schemi di physical layer security. In tali schemi non ci sono chiavi segrete: gli utenti, legittimo e non autorizzato, vengono distinti sulla base delle differenze fisiche dei loro canali. Se consideriamo, come esempio, una comunicazione wireless e due utenti, è possibile utilizzare tali tecniche per ridurre drasticamente la distanza relativa tra utente autorizzato e attaccante, alla quale essi devono essere, per far si che l'utente legittimo possa ricevere dati dal router e l'attaccante non sia in grado di ottenere informazione.