From Single-Bit to Multi-bit Public-Key Encryption via Non-malleable Codes

One approach towards basing public-key encryption (PKE) schemes on weak and credible assumptions is to build “stronger” or more general schemes generically from “weaker” or more restricted ones. One particular line of work in this context was initiated by Myers and shelat (FOCS ’09) and continued by Hohenberger, Lewko, and Waters (Eurocrypt ’12), who provide constructions of multi-bit CCA-secure PKE from single-bit CCA-secure PKE. It is well-known that encrypting each bit of a plaintext string independently is not chosen-ciphertext secure—the resulting scheme is malleable. This paper analyzes the conceptually simple approach of applying a suitable non-malleable code (Dziembowski et al., ICS ’10) to the plaintext and subsequently encrypting the resulting codeword bit-by-bit. An attacker’s ability to make multiple decryption queries requires that the underlying code be continuously non-malleable (Faust et al., TCC ’14). This flavor of non-malleable codes can only be achieved if the decoder is allowed to “self-destruct” when it processes an invalid encoding. The resulting PKE scheme inherits this property and therefore only achieves a weaker variant of chosen-ciphertext security, where the decryption becomes dysfunctional once the attacker submits an invalid ciphertext. We first show that the above approach based on non-malleable codes indeed yields a solution to the problem of domain extension for publickey encryption where the decryption may self-destruct, provided that the underlying code is continuously non-malleable against a reduced form of bit-wise tampering. This statement is shown by combining a simple information-theoretic argument with the constructive cryptography perspective on PKE (Coretti et al., Asiacrypt ’13). Then, we prove that the code of Dziembowski et al. is actually already continuously non-malleable against (full) bit-wise tampering; this constitutes the first informationtheoretically secure continuously non-malleable code, a technical contribution that we believe is of independent interest. Compared to the previous approaches to PKE domain extension, our scheme is more efficient and intuitive, at the cost of not achieving full CCA security. Our result is also one of the first applications of non-malleable codes in a context other than memory tampering.