Semantic security for the McEliece cryptosystem without random oracles. (English) Zbl 1196.94062
Summary: 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 J. Katz and J. S. Shin from Eurocrypt ’05 [Lect. Notes Comput. Sci. 4004, 73–87 (2006; Zbl 1140.94352)] 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.
MSC:
| 94A60 | Cryptography |
| 11T71 | Algebraic coding theory; cryptography (number-theoretic aspects) |
| 14G50 | Applications to coding theory and cryptography of arithmetic geometry |
Citations:
Zbl 1140.94352Software:
McElieceReferences:
| [1] | Bellare M., Rogaway P.: Random oracles are practical: a paradigm for designing efficient protocols. In: Proceedings of CCS, pp. 62–73 (1993). |
| [2] | Bellare M., Rogaway P.: Optimal asymmetric encryption – how to encrypt with RSA. In: EUROCRYPT ’94, LNCS vol. 950, pp. 92–111 (1995). · Zbl 0881.94010 |
| [3] | 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 · Zbl 0377.94018 · doi:10.1109/TIT.1978.1055873 |
| [4] | Blum A., Kalai A., Wasserman H. (2003). Noise-tolerant learning, the parity problem, and the statistical query model. J. ACM 50(4): 506–519 · Zbl 1296.68122 · doi:10.1145/792538.792543 |
| [5] | 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 · Zbl 1053.94558 · doi:10.1109/18.651067 |
| [6] | Cayrel P.-L., Gaborit P., Girault M.: Identity based identification and signature schemes using correcting codes. In: WCC ’07, pp. 69–78 (2007). · Zbl 1159.68435 |
| [7] | 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). · Zbl 1062.94556 |
| [8] | 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). · Zbl 0931.94018 |
| [9] | El Gamal T. (1985). A public key cryptosystem and a signature scheme based on discrete logarithms. IEEE Trans. Inform. Theory 31(4): 469–472 · Zbl 0571.94014 · doi:10.1109/TIT.1985.1057074 |
| [10] | Engelbert D., Overbeck R., Schmidt A. (2007). A summary of McEliece-type cryptosystems and their security. J. Math. Cryptol. 1(2): 151–199 · Zbl 1278.94047 · doi:10.1515/JMC.2007.009 |
| [11] | 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). · Zbl 1304.94056 |
| [12] | Fujisaki E., Okamoto T.: Secure integration of asymmetric and symmetric encryption schemes. In: Crypto ’99, LNCS vol. 1666, pp. 537–554 (1999). · Zbl 0942.94019 |
| [13] | Goldreich O.: Foundation of Cryptography, Basic Tools. Cambridge University Press (2001). · Zbl 1007.94016 |
| [14] | Goldreich O., Levin L.A.: A hard-core predicate for all one-way functions. In: STOC ’89, pp. 25–32 (1989). |
| [15] | Goldwasser S., Micali S. (1984). Probabilistic encryption. J. Comp. Syst. Sci. 28, 270–299 · Zbl 0563.94013 · doi:10.1016/0022-0000(84)90070-9 |
| [16] | 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). · Zbl 1140.94352 |
| [17] | Kabatiansky G., Krouk E., Semenov S.: Error Correcting Codes and Security for Data Networks. Wiley (2005). |
| [18] | Kobara K., Imai H.: Semantically secure McEliece public-key cryptosystems – conversions for McEliece PKC. In: PKC ’01, LNCS vol. 1992, pp. 19–35 (2001). · Zbl 0988.94021 |
| [19] | Leon J.S. (2001). A probabilistic algorithm for computing minimum weights of large error-correcting codes. IEEE Trans. Inform. Theory 34(5): 1354–1359 · Zbl 0666.94017 · doi:10.1109/18.21270 |
| [20] | 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 · Zbl 0803.94016 · doi:10.1109/18.272496 |
| [21] | Loidreau P., Sendrier N. (2001). Weak keys in the McEliece public-key cryptosystem. IEEE Trans. Inform. Theory 47(3): 1207–1211 · Zbl 0994.94029 · doi:10.1109/18.915687 |
| [22] | McEliece R.J.: The theory of information and coding. In: The Encyclopedia of Mathematics and Its Applications, vol. 3. Addison-Wesley (1977). · Zbl 0376.94011 |
| [23] | McEliece R.J.: A public-key cryptosystem based on algebraic coding theory. Deep Space Network Prog. Rep. (1978). |
| [24] | Niederreiter H. (1986). Knapsack-type cryptosystems and algebraic coding theory. Prob. Control Inform. Theory 15(2): 159–166 · Zbl 0611.94007 |
| [25] | Paillier P.: Public-key cryptosystem based on discrete logarithm residues. In: Eurocrypt ’99, LNCS vol. 1592, pp. 223–238 (1999). · Zbl 0933.94027 |
| [26] | Petrank E., Roth R.M. (1997). Is code equivalence easy to decide?. IEEE Trans. Inform. Theory 43, 1602–1604 · Zbl 0884.94025 · doi:10.1109/18.623157 |
| [27] | Pointcheval D.: Chosen-ciphertext security for any one-way cryptosystem. In: PKC ’00, LNCS vol. 1751, pp. 129–146 (2000). · Zbl 0969.94022 |
| [28] | Sendrier N. (2000). Finding the permutation between equivalent linear codes: the support splitting algorithm. IEEE Trans. Inform. Theory 46(4): 1193–1203 · Zbl 1002.94037 · doi:10.1109/18.850662 |
| [29] | Shoup V.: OAEP reconsidered. In: Crypto ’01, LNCS vol. 2139, pp. 239–259 (2001). · Zbl 1002.94519 |
| [30] | Stern J.: A method for finding codewords of small weight. In: Coding Theory and Applications, LNCS vol. 388, pp. 106–113 (1989). · Zbl 0678.94006 |
| [31] | Suzuki M., Kobara K., Imai H.: Privacy enhanced and light weight RFID system without tag synchronization and exhaustive search. In: IEEE SMC (2006). |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
