Abstract
Pseudo-random functions are a useful cryptographic primitive that, can be combined with zero-knowledge proof systems in order to achieve privacy-preserving identification. Libert et al. (ASIACRYPT 2017) has investigated the problem of proving the correct evaluation of lattice-based PRFs based on the Learning-With-Rounding (LWR) problem. In this paper, we go beyond lattice-based assumptions and investigate, whether we can solve the question of proving the correct evaluation of PRFs based on code-based assumptions such as the Syndrome Decoding problem. The answer is affirmative and we achieve it by firstly introducing a very efficient code-based PRG based on the Regular Syndrome Decoding problem and subsequently, we give a direct construction of a code-based PRF. Thirdly, we provide a zero-knowledge protocol for the correct evaluation of a code-based PRF, which allows a prover to convince a verifier that a given output y is indeed computed from the code-based PRF with a secret key k on an input x, i.e., \(y=f(k,x)\). Finally, we analytically evaluate the protocol’s communication costs.
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
Similar content being viewed by others
References
Adleman, L.M.: Implementing an electronic notary public. In: Advances in Cryptology (1983)
Aguilar, C., Gaborit, P., Schrek, J.: A new zero-knowledge code based identification scheme with reduced communication. In: 2011 IEEE Information Theory Workshop (2011). https://doi.org/10.1109/ITW.2011.6089577
Augot, D., Finiasz, M., Sendrier, N.: A family of fast syndrome based cryptographic hash functions. In: Dawson, E., Vaudenay, S. (eds.) Mycrypt 2005. LNCS, vol. 3715, pp. 64–83. Springer, Heidelberg (2005). https://doi.org/10.1007/11554868_6
Banerjee, A., Peikert, C., Rosen, A.: Pseudorandom functions and lattices. In: Pointcheval, D., Johansson, T. (eds.) EUROCRYPT 2012. LNCS, vol. 7237, pp. 719–737. Springer, Heidelberg (2012). https://doi.org/10.1007/978-3-642-29011-4_42
Berlekamp, E., McEliece, R., Van Tilborg, H.: On the inherent intractability of certain coding problems (Corresp.). IEEE Transact. Inf. Theory 24(3), 384–386 (1978)
Brunetta, C., Liang, B., Mitrokotsa, A.: Lattice-based simulatable VRFs: challenges and future directions. J. Internet Serv. Inf. Secur. (JISIS) 8(4), 57–69 (2018)
Cayrel, P.L., Gaborit, P., Girault, M.: Identity-based identification and signature schemes using correcting codes. In: WCC, vol. 2007 (2007)
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: Selected Areas in Cryptography (2011)
Chabaud, F.: On the security of some cryptosystems based on error-correcting codes. In: De Santis, A. (ed.) EUROCRYPT 1994. LNCS, vol. 950, pp. 131–139. Springer, Heidelberg (1995). https://doi.org/10.1007/BFb0053430
El Yousfi Alaoui, S.M., Cayrel, P.-L., Mohammed, M.: Improved identity-based identification and signature schemes using quasi-dyadic Goppa codes. In: Kim, T., Adeli, H., Robles, R.J., Balitanas, M. (eds.) ISA 2011. CCIS, vol. 200, pp. 146–155. Springer, Heidelberg (2011). https://doi.org/10.1007/978-3-642-23141-4_14
Ezerman, M.F., Lee, H.T., Ling, S., Nguyen, K., Wang, H.: A provably secure group signature scheme from code-based assumptions. In: Iwata, T., Cheon, J.H. (eds.) ASIACRYPT 2015. LNCS, vol. 9452, pp. 260–285. Springer, Heidelberg (2015). https://doi.org/10.1007/978-3-662-48797-6_12
Fischer, J.-B., Stern, J.: An efficient pseudo-random generator provably as secure as syndrome decoding. In: Maurer, U. (ed.) EUROCRYPT 1996. LNCS, vol. 1070, pp. 245–255. Springer, Heidelberg (1996). https://doi.org/10.1007/3-540-68339-9_22
Gaborit, P., Lauradoux, C., Sendrier, N.: SYND: a fast code-based stream cipher with a security reduction. In: 2007 IEEE International Symposium on Information Theory, June 2007. https://doi.org/10.1109/ISIT.2007.4557224
Gilbert, E.N.: A comparison of signalling alphabets. Bell Syst. Tech. J. 31(3), 504–522 (1952). https://doi.org/10.1002/j.1538-7305.1952.tb01393.x
Goldreich, O., Levin, L.A.: A hard-core predicate for all one-way functions. In: STOC 1989. ACM (1989). https://doi.org/10.1145/73007.73010
Goldreich, O., Goldwasser, S., Micali, S.: How to construct random functions. J. ACM 33(4), 792–807 (1986). https://doi.org/10.1145/6490.6503
Hu, R., Morozov, K., Takagi, T.: Proof of plaintext knowledge for code-based public-key encryption revisited. In: ASIA CCS 2013 (2013). https://doi.org/10.1145/2484313.2484385
Katz, J., Lindell, Y.: Introduction to Modern Cryptography. CRC Press, Boca Raton (2014)
Libert, B., Ling, S., Nguyen, K., Wang, H.: Zero-knowledge arguments for lattice-based PRFs and applications to E-Cash. In: Takagi, T., Peyrin, T. (eds.) ASIACRYPT 2017. LNCS, vol. 10626, pp. 304–335. Springer, Cham (2017). https://doi.org/10.1007/978-3-319-70700-6_11
Meziani, M., Cayrel, P.-L., El Yousfi Alaoui, S.M.: 2SC: An efficient code-based stream cipher. In: Kim, T., Adeli, H., Robles, R.J., Balitanas, M. (eds.) ISA 2011. CCIS, vol. 200, pp. 111–122. Springer, Heidelberg (2011). https://doi.org/10.1007/978-3-642-23141-4_11
Meziani, M., Hoffmann, G., Cayrel, P.-L.: Improving the performance of the SYND stream cipher. In: Mitrokotsa, A., Vaudenay, S. (eds.) AFRICACRYPT 2012. LNCS, vol. 7374, pp. 99–116. Springer, Heidelberg (2012). https://doi.org/10.1007/978-3-642-31410-0_7
Stern, J.: A new paradigm for public key identification. IEEE Transact. Inf. Theory 42(6), 1757–1768 (1996). https://doi.org/10.1109/18.556672
Stern, J.: A method for finding codewords of small weight. In: Cohen, G., Wolfmann, J. (eds.) Coding Theory 1988. LNCS, vol. 388, pp. 106–113. Springer, Heidelberg (1989). https://doi.org/10.1007/BFb0019850
Varshamov, R.R.: Estimate of the number of signals in error correcting codes. Docklady Akad. Nauk, S.S.S.R. 117, 739–741 (1957)
Yu, Y., Steinberger, J.: Pseudorandom Functions in Almost Constant Depth from Low-Noise LPN. In: Fischlin, M., Coron, J.-S. (eds.) EUROCRYPT 2016. LNCS, vol. 9666, pp. 154–183. Springer, Heidelberg (2016). https://doi.org/10.1007/978-3-662-49896-5_6
Acknowledgement
We are grateful to the anonymous reviewers for their insightful comments. This work was partially supported by the Swedish Research Council (Vetenskapsrådet) through the grant PRECIS (621-2014-4845).
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2019 Springer Nature Switzerland AG
About this paper
Cite this paper
Brunetta, C., Liang, B., Mitrokotsa, A. (2019). Code-Based Zero Knowledge PRF Arguments. In: Lin, Z., Papamanthou, C., Polychronakis, M. (eds) Information Security. ISC 2019. Lecture Notes in Computer Science(), vol 11723. Springer, Cham. https://doi.org/10.1007/978-3-030-30215-3_9
Download citation
DOI: https://doi.org/10.1007/978-3-030-30215-3_9
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-030-30214-6
Online ISBN: 978-3-030-30215-3
eBook Packages: Computer ScienceComputer Science (R0)