Abstract
In this paper, we formally prove that padding the plaintext with a random bit-string provides the semantic security against chosen plaintext attack (IND-CPA) for the McEliece (and its dual, the Niederreiter) cryptosystems under the standard assumptions. Such padding has recently been used by Suzuki, Kobara and Imai in the context of RFID security. Our proof relies on the technical result by Katz and Shin from Eurocrypt ’05 showing “pseudorandomness” implied by the learning parity with noise (LPN) problem. We do not need the random oracles as opposed to the known generic constructions which, on the other hand, provide a stronger protection as compared to our scheme—against (adaptive) chosen ciphertext attack, i.e., IND-CCA(2). In order to show that the padded version of the cryptosystem remains practical, we provide some estimates for suitable key sizes together with corresponding workload required for successful attack.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
Bellare M., Rogaway P.: Random oracles are practical: a paradigm for designing efficient protocols. In: Proceedings of CCS, pp. 62–73 (1993).
Bellare M., Rogaway P.: Optimal asymmetric encryption – how to encrypt with RSA. In: EUROCRYPT ’94, LNCS vol. 950, pp. 92–111 (1995).
Berlekamp E., McEliece R.J., van Tilborg H.C.A. (1978). On the inherent intractability of certain coding problems. IEEE Trans. Inform. Theory 24, 384–386
Blum A., Kalai A., Wasserman H. (2003). Noise-tolerant learning, the parity problem, and the statistical query model. J. ACM 50(4): 506–519
Canteaut A., Chabaud F. (1998). A new algorithm for finding minimum-weight words in a linear code: application to primitive narrow-sense BCH codes of length 511. IEEE Trans. Inform. Theory 44(1): 367–378
Cayrel P.-L., Gaborit P., Girault M.: Identity based identification and signature schemes using correcting codes. In: WCC ’07, pp. 69–78 (2007).
Courtois N., Finiasz M., Sendrier N.: How to achieve a McEliece-based digital signature scheme. In: Asiacrypt ’01, LNCS vol. 2248, pp. 157–174 (2001).
Cramer R., Shoup V.: A practical public key cryptosystem provably secure against adaptive chosen ciphertext attack. In: Crypto ’98, LNCS vol. 1462, pp. 13–25 (1998).
El Gamal T. (1985). A public key cryptosystem and a signature scheme based on discrete logarithms. IEEE Trans. Inform. Theory 31(4): 469–472
Engelbert D., Overbeck R., Schmidt A. (2007). A summary of McEliece-type cryptosystems and their security. J. Math. Cryptol. 1(2): 151–199
Fischer J.-B., Stern J.: An efficient pseudo-random generator provably as secure as syndrome decoding. In: Eurocrypt ’96, LNCS vol. 1070, pp. 245–255 (1996).
Fujisaki E., Okamoto T.: Secure integration of asymmetric and symmetric encryption schemes. In: Crypto ’99, LNCS vol. 1666, pp. 537–554 (1999).
Goldreich O.: Foundation of Cryptography, Basic Tools. Cambridge University Press (2001).
Goldreich O., Levin L.A.: A hard-core predicate for all one-way functions. In: STOC ’89, pp. 25–32 (1989).
Goldwasser S., Micali S. (1984). Probabilistic encryption. J. Comp. Syst. Sci. 28, 270–299
Katz J., Shin J.S.: Parallel and concurrent security of the HB and HB+ protocols. In: Eurocrypt ’06, LNCS vol. 4004, pp. 73–87 (2006).
Kabatiansky G., Krouk E., Semenov S.: Error Correcting Codes and Security for Data Networks. Wiley (2005).
Kobara K., Imai H.: Semantically secure McEliece public-key cryptosystems – conversions for McEliece PKC. In: PKC ’01, LNCS vol. 1992, pp. 19–35 (2001).
Leon J.S. (2001). A probabilistic algorithm for computing minimum weights of large error-correcting codes. IEEE Trans. Inform. Theory 34(5): 1354–1359
Li Y.X., Deng R.H., Wang X.M. (1994). The equivalence of McEliece’s and Niederreiter’s public-key cryptosystems. IEEE Trans. Inform. Theory 40, 271–273
Loidreau P., Sendrier N. (2001). Weak keys in the McEliece public-key cryptosystem. IEEE Trans. Inform. Theory 47(3): 1207–1211
McEliece R.J.: The theory of information and coding. In: The Encyclopedia of Mathematics and Its Applications, vol. 3. Addison-Wesley (1977).
McEliece R.J.: A public-key cryptosystem based on algebraic coding theory. Deep Space Network Prog. Rep. (1978).
Niederreiter H. (1986). Knapsack-type cryptosystems and algebraic coding theory. Prob. Control Inform. Theory 15(2): 159–166
Paillier P.: Public-key cryptosystem based on discrete logarithm residues. In: Eurocrypt ’99, LNCS vol. 1592, pp. 223–238 (1999).
Petrank E., Roth R.M. (1997). Is code equivalence easy to decide?. IEEE Trans. Inform. Theory 43, 1602–1604
Pointcheval D.: Chosen-ciphertext security for any one-way cryptosystem. In: PKC ’00, LNCS vol. 1751, pp. 129–146 (2000).
Sendrier N. (2000). Finding the permutation between equivalent linear codes: the support splitting algorithm. IEEE Trans. Inform. Theory 46(4): 1193–1203
Shoup V.: OAEP reconsidered. In: Crypto ’01, LNCS vol. 2139, pp. 239–259 (2001).
Stern J.: A method for finding codewords of small weight. In: Coding Theory and Applications, LNCS vol. 388, pp. 106–113 (1989).
Suzuki M., Kobara K., Imai H.: Privacy enhanced and light weight RFID system without tag synchronization and exhaustive search. In: IEEE SMC (2006).
Author information
Authors and Affiliations
Corresponding author
Additional information
Ryo Nojima’s work was done when he was at the University of Tokyo, Japan.
Rights and permissions
About this article
Cite this article
Nojima, R., Imai, H., Kobara, K. et al. Semantic security for the McEliece cryptosystem without random oracles. Des. Codes Cryptogr. 49, 289–305 (2008). https://doi.org/10.1007/s10623-008-9175-9
Received:
Revised:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s10623-008-9175-9