Abstract
We work within the recent paradigm, started by Groth (ASIACRYPT 2010), of constructing short non-interactive zero knowledge arguments from a small number basic arguments in a modular fashion. The main technical result of this paper is a new permutation argument, by using product and shift arguments of Lipmaa (2014) and a parallelizable variant of the Beneš network. We use it to design a short non-interactive zero knowledge argument for the NP-complete language CircuitSAT with Θ(n log2 n) prover’s computational complexity, where n is the size of the circuit. The permutation argument can be naturally used to design direct NIZK arguments for many other NP-complete languages.
Access provided by Autonomous University of Puebla. Download to read the full chapter text
Chapter PDF
Similar content being viewed by others
Keywords
References
Abe, M.: Mix-Networks on Permutation Networks. In: Lam, K.-Y., Okamoto, E., Xing, C. (eds.) ASIACRYPT 1999. LNCS, vol. 1716, pp. 258–273. Springer, Heidelberg (1999)
Abe, M., Hoshino, F.: Remarks on Mix-Network Based on Permutation Networks. In: Kim, K.-C. (ed.) PKC 2001. LNCS, vol. 1992, pp. 317–324. Springer, Heidelberg (2001)
Ben-Sasson, E., Chiesa, A., Genkin, D., Tromer, E., Virza, M.: SNARKs for C: Verifying Program Executions Succinctly and in Zero Knowledge. In: Canetti, R., Garay, J.A. (eds.) CRYPTO 2013, Part II. LNCS, vol. 8043, pp. 90–108. Springer, Heidelberg (2013)
Beneš, V.E.: Mathematical Theory of Connecting Networks and Telephone Traffic. Academic Press (August 28, 1965)
Bitansky, N., Chiesa, A., Ishai, Y., Ostrovsky, R., Paneth, O.: Succinct Non-interactive Arguments via Linear Interactive Proofs. In: Sahai, A. (ed.) TCC 2013. LNCS, vol. 7785, pp. 315–333. Springer, Heidelberg (2013)
Blelloch, G.: Vector Models for Data-Parallel Computing. MIT Press (1990)
Blum, M., Feldman, P., Micali, S.: Non-Interactive Zero-Knowledge and Its Applications. In: STOC 1988, pp. 103–112. ACM Press (1988)
Chaabouni, R., Lipmaa, H., Zhang, B.: A Non-Interactive Range Proof with Constant Communication. In: Keromytis, A.D. (ed.) FC 2012. LNCS, vol. 7397, pp. 179–199. Springer, Heidelberg (2012)
Clos, C.: A Study of Non-Blocking Switching Networks. Bell System Technical Journal 32(2), 406–424 (1953)
Damgård, I.: Towards Practical Public Key Systems Secure against Chosen Ciphertext Attacks. In: Feigenbaum, J. (ed.) CRYPTO 1991. LNCS, vol. 576, pp. 445–456. Springer, Heidelberg (1992)
Di Crescenzo, G., Lipmaa, H.: Succinct NP Proofs from an Extractability Assumption. In: Beckmann, A., Dimitracopoulos, C., Löwe, B. (eds.) CiE 2008. LNCS, vol. 5028, pp. 175–185. Springer, Heidelberg (2008)
Fauzi, P., Lipmaa, H., Zhang, B.: Efficient Modular NIZK Arguments from Shift and Product. In: Abdalla, M., Nita-Rotaru, C., Dahab, R. (eds.) CANS 2013. LNCS, vol. 8257, pp. 92–121. Springer, Heidelberg (2013)
Gennaro, R., Gentry, C., Parno, B., Raykova, M.: Quadratic Span Programs and Succinct NIZKs without PCPs. In: Johansson, T., Nguyen, P.Q. (eds.) EUROCRYPT 2013. LNCS, vol. 7881, pp. 626–645. Springer, Heidelberg (2013)
Goldwasser, S., Micali, S., Rackoff, C.: The Knowledge Complexity of Interactive Proof-Systems. In: Sedgewick, R. (ed.) STOC 1985, pp. 291–304. ACM Press (1985)
Golle, P., Jarecki, S., Mironov, I.: Cryptographic Primitives Enforcing Communication and Storage Complexity. In: Blaze, M. (ed.) FC 2002. LNCS, vol. 2357, pp. 120–135. Springer, Heidelberg (2003)
Groth, J.: Short Pairing-Based Non-interactive Zero-Knowledge Arguments. In: Abe, M. (ed.) ASIACRYPT 2010. LNCS, vol. 6477, pp. 321–340. Springer, Heidelberg (2010)
Groth, J., Lu, S.: A Non-interactive Shuffle with Pairing Based Verifiability. In: Kurosawa, K. (ed.) ASIACRYPT 2007. LNCS, vol. 4833, pp. 51–67. Springer, Heidelberg (2007)
Hwang, F.K.M.: The Mathematical Theory of Nonblocking Switching Networks, 2nd edn. Series on Applied Mathematics, vol. 15. World Scientific Publishing Co Pte Ltd. (October 1, 2004)
Lipmaa, H.: Progression-Free Sets and Sublinear Pairing-Based Non-Interactive Zero-Knowledge Arguments. In: Cramer, R. (ed.) TCC 2012. LNCS, vol. 7194, pp. 169–189. Springer, Heidelberg (2012)
Lipmaa, H.: Succinct Non-Interactive Zero Knowledge Arguments from Span Programs and Linear Error-Correcting Codes. In: Sako, K., Sarkar, P. (eds.) ASIACRYPT 2013, Part I. LNCS, vol. 8269, pp. 41–60. Springer, Heidelberg (2013)
Lipmaa, H.: Almost Optimal Short Adaptive Non-Interactive Zero Knowledge. Tech. Rep. 2014/396, International Association for Cryptologic Research (2014), http://eprint.iacr.org/2014/396
Lipmaa, H., Zhang, B.: A More Efficient Computationally Sound Non-Interactive Zero-Knowledge Shuffle Argument. In: Visconti, I., De Prisco, R. (eds.) SCN 2012. LNCS, vol. 7485, pp. 477–502. Springer, Heidelberg (2012)
Nassimi, D., Sahni, S.: Parallel Algorithms to Set Up the Benes Permutation Network. IEEE Trans. Computers 31(2), 148–154 (1982)
Opferman, D.C., Tsao-Wu, N.T.: On a Class of Rearrangeable Switching Networks. Part I: Control Algorithm. Bell System Technical Journal 50(5), 1579–1600 (1971)
Pippenger, N.: On the Evaluation of Powers and Monomials. SIAM J. Comput. 9(2), 230–250 (1980)
Pratt, V.R., Stockmeyer, L.J.: A Characterization of the Power of Vector Machines. Journal of Computer and System Sciences 12(2), 198–221 (1976)
Straus, E.G.: Addition Chains of Vectors. American Mathematical Monthly 70, 806–808 (1964)
Waksman, A.: A Permutation Network. Journal of the ACM 15(1), 159–163 (1968)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2014 Springer International Publishing Switzerland
About this paper
Cite this paper
Lipmaa, H. (2014). Efficient NIZK Arguments via Parallel Verification of Benes Networks. In: Abdalla, M., De Prisco, R. (eds) Security and Cryptography for Networks. SCN 2014. Lecture Notes in Computer Science, vol 8642. Springer, Cham. https://doi.org/10.1007/978-3-319-10879-7_24
Download citation
DOI: https://doi.org/10.1007/978-3-319-10879-7_24
Publisher Name: Springer, Cham
Print ISBN: 978-3-319-10878-0
Online ISBN: 978-3-319-10879-7
eBook Packages: Computer ScienceComputer Science (R0)