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.Category / Keywords: public-key cryptography / Date: received 9 May 2014, last revised 6 Oct 2014 Contact author: corettis at inf ethz ch Available format(s): PDF | BibTeX Citation Version: 20141006:200727 (All versions of this report) Discussion forum: Show discussion | Start new discussion