How to Construct Polar Codes for Ring-LWE-Based Public Key Encryption.

Area of Science:

• Cryptography
• Coding Theory
• Computer Science

Background:

• Public key encryption (PKE) schemes based on ring learning with errors (RLWE) face a trade-off between security (wider error distribution) and decryption failure rate (DFR).
• Existing RLWE-based PKE schemes struggle to effectively apply standard error-correcting codes due to correlated error terms and security concerns with decoding algorithms.
• Accurate DFR estimation is challenging for RLWE schemes, hindering the creation of a sufficient DFR margin for enhanced security.

Purpose of the Study:

• To propose a novel polar coding scheme for RLWE-based PKE to address the security-DFR trade-off.
• To overcome limitations of traditional error-correcting codes in cryptographic applications.
• To enhance the security and reliability of RLWE-based PKE systems.

Main Methods:

• Developed a polar coding scheme tailored for RLWE-based PKE.
• Introduced a relaxed 'independence' assumption to derive an uncorrelated residue noise term.
• Utilized wireless communication strategies (outage) for polar code construction and exploited residue noise properties for improved decoding.

Main Results:

• The proposed polar coding scheme achieves a significant DFR margin, enhancing security by 28.8% compared to benchmarks.
• A decryption failure rate (DFR) of 2^-149 was achieved with specific parameters (code rate 0.25, n=1024, q=12,289, k=55).
• Polar encoding and decoding exhibit quasilinear complexity (O(Nlog2N)) and support constant-time implementations, addressing safety concerns.

Conclusions:

• Polar coding offers a viable and effective solution for RLWE-based PKE, balancing security and decryption reliability.
• The scheme provides a competitive security improvement and a low DFR, making it suitable for practical cryptographic applications.
• The constant-time nature of polar decoding enhances the security of RLWE-based PKE against side-channel attacks.