Polar Coding for Ring-LWE-Based Public Key Encryption
Jiabo Wang and Cong Ling
Abstract
Cryptographic constructions based on (RLWE) have emerged as one of the front runners for the standardization of post quantum public key cryptography. As the standardization process continues, optimizing specific parts of proposed schemes becomes a worthwhile endeavor. In this work we focus on using error correcting codes to alleviate a natural trade-off present in most schemes; namely, we would like a wider error distribution to increase security, but a wider error distribution comes at the cost of an increased probability of decryption error. The motivation of this work is to improve the security level of RLWE-based public key encryption (PKE) while keeping the target decryption failure rate (DFR) achievable using error-correcting codes. Specifically, we explore how to implement a family member of error correcting codes, known as polar codes, in RLWE-based PKE schemes in order to effectively lower the DFR. The dependency existing in the additive noise term is handled by mapping every error term (e.g., ) under canonical embedding to the space where a product in the number field gives rise to a coordinate-wise product in . An attempt has been made to make the modulation constellation (message basis) fit in with the canonical basis. Furthermore, we exploit the actuality of some error terms known by the decoder to further lower the DFR. Using our method, the DFR is expected to be as low as for code rate 0.25, and binomial parameter as is exactly the setting of the post-quantum scheme NewHope; DFR is for code rate 0.25, . This new DFR margin enables us to improve the security level by compared with NewHope. Moreover, polar encoding and decoding have quasi-linear complexity and they can be implemented in constant time.
@misc{cryptoeprint:2021/619,
author = {Jiabo Wang and Cong Ling},
title = {Polar Coding for Ring-{LWE}-Based Public Key Encryption},
howpublished = {Cryptology {ePrint} Archive, Paper 2021/619},
year = {2021},
url = {https://eprint.iacr.org/2021/619}
}
Note: In order to protect the privacy of readers, eprint.iacr.org
does not use cookies or embedded third party content.