A necessary condition for CPA-security of randomized symmetric code cryptosystems

Fìz.-mat. model. ìnf. tehnol. 2021, 33:78-82

Abstract

We investigate a class of symmetric code cryptosystems constructed similarly to the well-known randomized (asymmetric) McEliece cryptosystem. A necessary condition for CPA- security of such cryptosystems is obtained (that is, their security against arbitrary distinguishing chosen-plaintext attacks). To each randomized code cryptosystem of specified type correspond its shortening, which is its reduced version. It is proved that the CPA-security of the input cryptosystem imply the CPA-security of its shortening. To a certain extent, this makes it possible to reduce the question about the CPA-security of randomized code cryptosystems to similar question about cryptosystems that have simpler structure. The obtained result can be used in further research in the construction of provable secure symmetric code cryptosystems.

References

1. Shevchuk, O. S. (2020). Randomized symmetric McEliece cryptosystem based on generalized Reed-Solomon codes. Radiotekhnika: All-Ukr. Sci. Interdep. Mag., 200, 25–36. [in Ukrainian].
   DOI https://doi.org/10.30837/rt.2020.1.200.03
2. Nojima, R, Imai, H, Kobara, K, Morozov, K. (2008). Semantic security for the McEliece cryptosystem without random oracles. Des. Codes Cryptography, 49(1–3), 289–305.
   DOI https://doi.org/10.1007/s10623-008-9175-9
3. Jordan, J. P. (1983). A variant of public key cryptosystem based on Goppa codes. Sigact news, 15(1), 61–66.
   DOI https://doi.org/10.1145/1008908.1008918
4. Rao, T. R. N. (1984). Cryptosystem using algebraic codes. Int. Conf on Computer Systems & Signal Processing. Bangalore, India.
5. Rao, T. R. N., Nam, K. H. (1989). Private-key algebraic code encryption. IEEE Trans. on Inform Theory, 35(4), 829–833.
   DOI https://doi.org/10.1109/18.32159
6. Gilbert, H., Mattew, J. B., Robshaw, M. J. B, Seurin, Y. (2008). How to Encrypt with the LPN Problem. ICALP (2), Proceedings, Springer Verlag, 679-690.
   DOI https://doi.org/10.1007/978-3-540-70583-3_55
7. Katz, J., Lindell, Y. (2015). Introduction to modern cryptography. Chapman and Hall/CRC Press.
8. MacWilliams, F. J., Sloane, N. J. A. (1977). The theory of error-correcting codes. North Holland, Amsterdam: North-Holland Mathematical Library.
   DOI https://doi.org/10.1016/s0924-6509(08)x7030-8