Paper 2014/324

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

Sandro Coretti and Ueli Maurer and Björn Tackmann and Daniele Venturi

Abstract

One approach towards basing public-key encryption schemes on weak and credible assumptions is to build ``stronger'' or more general schemes generically from ``weaker'' or more restricted schemes. One particular line of work in this context, which has been initiated by Myers and Shelat (FOCS '09) and continued by Hohenberger, Lewko, and Waters (Eurocrypt '12), is to build a multi-bit chosen-ciphertext (CCA) secure public-key encryption scheme from a single-bit CCA-secure one. While their approaches achieve the desired goal, it is fair to say that the employed techniques are complicated and that the resulting ciphertext lengths are impractical. We propose a completely different and surprisingly simple approach to solving this problem. While it is well-known that encrypting each bit of a plaintext string independently is insecure---the resulting scheme is malleable---we show that applying a suitable non-malleable code (Dziembowski et al., ICS '10) to the plaintext and subsequently encrypting the resulting codeword bit-by-bit results in a secure scheme. Our result is the one of the first applications of non-malleable codes in a context other than memory tampering. The original notion of non-malleability is, however, not sufficient. We therefore prove that (a simplified version of) the code of Dziembowski et al. is actually continuously non-malleable (Faust et al., TCC '14). Then, we show that this notion is sufficient for our application. Since continuously non-malleable codes require to keep a single bit of (not necessarily secret) state in the decoding, the decryption of our scheme also has to keep this state. This slight generalization of the traditional formalization of public-key encryption schemes seems appropriate for applications. Compared to the previous approaches, our technique leads to conceptually simpler and more efficient schemes.