Abstract
We present two zero-knowledge protocols for the code-based McEliece public key encryption scheme in the standard model. Consider a prover who encrypted a plaintext m into a ciphertext c under the public key pk. The first protocol is a proof of plaintext knowledge (PPK), where the prover convinces a polynomially bounded verifier on a joint input (c,pk) that he knows m without actually revealing it. This construction uses code-based Véron’s zero-knowledge identification scheme. The second protocol, which builds on the first one, is a verifiable McEliece encryption, were the prover convinces a polynomially bounded verifier on a joint input (c,pk,m) that c is a valid encryption of m, without performing decryption. These protocols are the first PPK and the first verifiable encryption for code-based cryptosystems.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Aumann, Y., Rabin, M.O.: A Proof of Plaintext Knowledge Protocol and Applications. Manuscript (June 2001), Available as slides from 1998 IACR Distinguished Lecture by M.O. Rabin, http://www.iacr.org/publications/dl/rabin98/rabin98slides.ps
Asokan, N., Shoup, V., Waidner, M.: Optimistic Fair Exchange of Digital Signatures (Extended Abstract). In: Nyberg, K. (ed.) EUROCRYPT 1998. LNCS, vol. 1403, pp. 591–606. Springer, Heidelberg (1998)
Bendlin, R., Damgård, I.: Threshold Decryption and Zero-Knowledge Proofs for Lattice-Based Cryptosystems. In: Micciancio, D. (ed.) TCC 2010. LNCS, vol. 5978, pp. 201–218. Springer, Heidelberg (2010)
Bernstein, D.J., Lange, T., Peters, C.: Wild McEliece. In: Biryukov, A., Gong, G., Stinson, D.R. (eds.) SAC 2010. LNCS, vol. 6544, pp. 143–158. Springer, Heidelberg (2011)
Berlekamp, E., McEliece, R., van Tilborg, H.: On the inherent intractability of certain coding problems. IEEE Trans. on Inf. Theory 24, 384–386 (1978)
Bernstein, D.J.: Grover vs. McEliece. In: Sendrier, N. (ed.) PQCrypto 2010. LNCS, vol. 6061, pp. 73–80. Springer, Heidelberg (2010)
Bernstein, D.J., Lange, T., Peters, C.: Smaller Decoding Exponents: Ball-Collision Decoding. In: Rogaway, P. (ed.) CRYPTO 2011. LNCS, vol. 6841, pp. 743–760. Springer, Heidelberg (2011)
Camenisch, J., Damgård, I.: Verifiable Encryption, Group Encryption, and Their Applications to Separable Group Signatures and Signature Sharing Schemes. In: Okamoto, T. (ed.) ASIACRYPT 2000. LNCS, vol. 1976, pp. 331–345. Springer, Heidelberg (2000)
Camenisch, J.L., Shoup, V.: Practical Verifiable Encryption and Decryption of Discrete Logarithms. In: Boneh, D. (ed.) CRYPTO 2003. LNCS, vol. 2729, pp. 126–144. Springer, Heidelberg (2003)
Cayrel, P.-L., Véron, P., El Yousfi Alaoui, S.M.: A Zero-Knowledge Identification Scheme Based on the q-ary Syndrome Decoding Problem. In: Biryukov, A., Gong, G., Stinson, D.R. (eds.) SAC 2010. LNCS, vol. 6544, pp. 171–186. Springer, Heidelberg (2011)
Dowsley, R., van de Graaf, J., Müller-Quade, J., Nascimento, A.C.A.: Oblivious Transfer Based on the McEliece Assumptions. In: Safavi-Naini, R. (ed.) ICITS 2008. LNCS, vol. 5155, pp. 107–117. Springer, Heidelberg (2008)
Engelbert, D., Overbeck, R., Schmidt, A.: A Summary of McEliece-Type Cryptosystems and their Security. Journal of Mathematical Cryptology 1, 151–199 (2007), Walter de Gruyter
Finiasz, M., Sendrier, N.: Security Bounds for the Design of Code-Based Cryptosystems. In: Matsui, M. (ed.) ASIACRYPT 2009. LNCS, vol. 5912, pp. 88–105. Springer, Heidelberg (2009)
Fischer, J.-B., Stern, J.: An Efficient Pseudo-random Generator Provably as Secure as Syndrome Decoding. In: Maurer, U.M. (ed.) EUROCRYPT 1996. LNCS, vol. 1070, pp. 245–255. Springer, Heidelberg (1996)
Galil, Z., Haber, S., Yung, M.: Symmetric Public-Key Encryption. In: Williams, H.C. (ed.) CRYPTO 1985. LNCS, vol. 218, pp. 128–137. Springer, Heidelberg (1986)
Goldreich, O.: Foundations of Cryptography I: Basic Tools. Cambridge University Press (2001)
Goldreich, O.: Foundations of Cryptography II: Basic Applications. Cambridge University Press (2004)
Goldreich, O., Micali, S., Wigderson, A.: Proofs that Yield Nothing But Their Validity for All Languages in NP Have Zero-Knowledge Proof Systems. J. ACM 38(3), 691–729 (1991)
Goldwasser, S., Kharchenko, D.: Proof of Plaintext Knowledge for the Ajtai-Dwork Cryptosystem. In: Kilian, J. (ed.) TCC 2005. LNCS, vol. 3378, pp. 529–555. Springer, Heidelberg (2005)
Goppa, V.D.: A new class of linear error-correcting code. Probl. Peredach. Inform. 6, 24–30 (1970) (in Russian)
Ishai, Y., Kushilevitz, E., Ostrovsky, R., Sahai, A.: Zero-knowledge from secure multiparty computation. In: STOC, pp. 21–30 (2007)
Janwa, H., Moreno, O.: McEliece Public Key Cryptosystems Using Algebraic-Geometric Codes. Des. Codes Cryptography 8(3), 293–307 (1996)
Katz, J.: Efficient and Non-Malleable Proofs of Plaintext Knowledge and Applications. In: Biham, E. (ed.) EUROCRYPT 2003. LNCS, vol. 2656, pp. 211–228. Springer, Heidelberg (2003)
Kobara, K., Morozov, K., Overbeck, R.: Coding-Based Oblivious Transfer. In: MMICS, pp. 142–156 (2008)
MacWilliams, F.J., Sloane, N.J.A.: The Theory of Error-Correcting Codes. North-Holland, Amsterdam (1992)
McEliece, R.J.: A Public-Key Cryptosystem Based on Algebraic Coding Theory. Deep Space Network Progress Rep. (1978)
Naor, M.: Bit Commitment Using Pseudo-Randomness (Extended Abstract). In: Brassard, G. (ed.) CRYPTO 1989. LNCS, vol. 435, pp. 128–136. Springer, Heidelberg (1990)
Niederreiter, H.: Knapsack-type Cryptosystems and Algebraic Coding Theory. Prob. of Control and Inf. Theory 15(2), 159–166 (1986)
Nojima, R., Imai, H., Kobara, K., Morozov, K.: Semantic security for the McEliece cryptosystem without random oracles. Des. Codes Cryptography 49(1-3), 289–305 (2008)
Roth, R.: Introduction to coding theory. Cambridge University Press (2006)
Sendrier, N.: On the security of the McEliece public-key cryptosystem. In: Information, Coding and Mathematics – Proceedings of Workshop honoring Prof. Bob McEliece on his 60th Birthday, pp. 141–163. Kluwer (2002)
Shor, P.W.: Polynominal Time Algorithms for Discrete Logarithms and Factoring on a Quantum Computer. In: Huang, M.-D.A., Adleman, L.M. (eds.) ANTS 1994. LNCS, vol. 877, p. 289. Springer, Heidelberg (1994)
Stadler, M.: Publicly Verifiable Secret Sharing. In: Maurer, U.M. (ed.) EUROCRYPT 1996. LNCS, vol. 1070, pp. 190–199. Springer, Heidelberg (1996)
Stern, J.: A New Identification Scheme Based on Syndrome Decoding. In: Stinson, D.R. (ed.) CRYPTO 1993. LNCS, vol. 773, pp. 13–21. Springer, Heidelberg (1994)
Véron, P.: Improved identification schemes based on error-correcting codes. Appl. Algebra Eng. Commun. Comput. 8(1), 57–69 (1996)
Xagawa, K., Kawachi, A., Tanaka, K.: Proof of Plaintext Knowledge for the Regev Cryptosystems. Tech.rep. C-236, Tokyo Inst. of Technology (2007)
Xagawa, K., Tanaka, K.: Zero-Knowledge Protocols for NTRU: Application to Identification and Proof of Plaintext Knowledge. In: Pieprzyk, J., Zhang, F. (eds.) ProvSec 2009. LNCS, vol. 5848, pp. 198–213. Springer, Heidelberg (2009)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2012 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Morozov, K., Takagi, T. (2012). Zero-Knowledge Protocols for the McEliece Encryption. In: Susilo, W., Mu, Y., Seberry, J. (eds) Information Security and Privacy. ACISP 2012. Lecture Notes in Computer Science, vol 7372. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-31448-3_14
Download citation
DOI: https://doi.org/10.1007/978-3-642-31448-3_14
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-31447-6
Online ISBN: 978-3-642-31448-3
eBook Packages: Computer ScienceComputer Science (R0)