Wiretap Polar Codes in Encryption Schemes Based on Learning with Errors Problem

The Learning with Errors (LWE) problem has been extensively studied in cryptography due to its strong hardness guarantees, efficiency and expressiveness in constructing advanced cryptographic primitives. In this work, we show that using polar codes in conjunction with LWE-based encryption yields several advantages. To begin, we demonstrate the obvious improvements in the efficiency or rate of information transmission in the LWE-based scheme by leveraging polar coding (with no change in the cryptographic security guarantee). Next, we integrate wiretap polar coding with LWE-based encryption to ensure provable semantic security over a wiretap channel in addition to cryptographic security based on the hardness of LWE. To the best of our knowledge this is the first wiretap code to have cryptographic security guarantees as well. Finally, we study the security of the private key used in LWE-based encryption with wiretap polar coding, and propose a key refresh method using random bits used in wiretap coding. Under a known-plaintext attack, we show that non-vanishing information-theoretic secrecy can be achieved for the key. We believe our approach is at least as interesting as our final results: our work combines cryptography and coding theory in a novel 'non blackbox-way' which may be relevant to other scenarios as well.