iBet uBet web content aggregator. Adding the entire web to your favor.
iBet uBet web content aggregator. Adding the entire web to your favor.



Link to original content: https://doi.org/10.1007/978-3-319-02937-5_6
Efficient Modular NIZK Arguments from Shift and Product | SpringerLink
Skip to main content
Springer Nature Link
Log in

Efficient Modular NIZK Arguments from Shift and Product

  • Conference paper
Cryptology and Network Security (CANS 2013)

Part of the book series: Lecture Notes in Computer Science ((LNSC,volume 8257))

Included in the following conference series:

  • 1336 Accesses

Abstract

We propose a non-interactive product argument, that is more efficient than the one by Groth and Lipmaa, and a novel shift argument. We then use them to design several novel non-interactive zero-knowledge (NIZK) arguments. We obtain the first range proof with constant communication and subquadratic prover’s computation. We construct NIZK arguments for NP-complete languages, Set-Partition, Subset-Sum and Decision-Knapsack, with constant communication, subquadratic prover’s computation and linear verifier’s computation.

This is a preview of subscription content, log in via an institution to check access.

Access this chapter

Log in via an institution

Subscribe and save

Springer+ Basic
$34.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Chapter
USD 29.95
Price excludes VAT (USA)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
eBook
USD 39.99
Price excludes VAT (USA)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
Softcover Book
USD 54.99
Price excludes VAT (USA)
  • Compact, lightweight edition
  • Dispatched in 3 to 5 business days
  • Free shipping worldwide - see info

Tax calculation will be finalised at checkout

Purchases are for personal use only

Institutional subscriptions

Preview

Unable to display preview. Download preview PDF.

Unable to display preview. Download preview PDF.

Similar content being viewed by others

References

  1. 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)

    Chapter  Google Scholar 

  2. Bitansky, N., Chiesa, A., Ishai, Y., Paneth, O., Ostrovsky, R.: Succinct Non-interactive Arguments via Linear Interactive Proofs. In: Sahai, A. (ed.) TCC 2013. LNCS, vol. 7785, pp. 315–333. Springer, Heidelberg (2013)

    Chapter  Google Scholar 

  3. Blelloch, G.: Vector Models for Data-Parallel Computing. MIT Press (1990)

    Google Scholar 

  4. Blum, M., Feldman, P., Micali, S.: Non-Interactive Zero-Knowledge and Its Applications. In: STOC 1988, May 2-4, pp. 103–112. ACM Press, Chicago (1988)

    Google Scholar 

  5. Boneh, D., Franklin, M.: Identity-Based Encryption from the Weil Pairing. In: Kilian, J. (ed.) CRYPTO 2001. LNCS, vol. 2139, pp. 213–229. Springer, Heidelberg (2001)

    Chapter  Google Scholar 

  6. Boudot, F.: Efficient Proofs That a Committed Number Lies in an Interval. In: Preneel, B. (ed.) EUROCRYPT 2000. LNCS, vol. 1807, pp. 431–444. Springer, Heidelberg (2000)

    Chapter  Google Scholar 

  7. Brassard, G., Chaum, D., Crépeau, C.: Minimum Disclosure Proofs of Knowledge. Journal of Computer and System Sciences 37(2), 156–189 (1988)

    Article  MathSciNet  MATH  Google Scholar 

  8. Camenisch, J.L., Chaabouni, R., Shelat, A.: Efficient Protocols for Set Membership and Range Proofs. In: Pieprzyk, J. (ed.) ASIACRYPT 2008. LNCS, vol. 5350, pp. 234–252. Springer, Heidelberg (2008)

    Chapter  Google Scholar 

  9. Canetti, R., Goldreich, O., Halevi, S.: The Random Oracle Methodology, Revisited. In: Vitter, J.S. (ed.) STOC 1998, Dallas, Texas, USA, May 23-26, pp. 209–218 (1998)

    Google Scholar 

  10. Chaabouni, R., Lipmaa, H., Shelat, A.: Additive Combinatorics and Discrete Logarithm Based Range Protocols. In: Steinfeld, R., Hawkes, P. (eds.) ACISP 2010. LNCS, vol. 6168, pp. 336–351. Springer, Heidelberg (2010)

    Chapter  Google Scholar 

  11. 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)

    Chapter  Google Scholar 

  12. Cooley, J.W., Tukey, J.W.: An Algorithm for the Machine Calculation of Complex Fourier Series. Mathematics of Computation 19, 297–301 (1965)

    Article  MathSciNet  MATH  Google Scholar 

  13. Dybizbański, J.: Sequences Containing No 3-Term Arithmetic Progressions. Electron. J. of Combin. 19(2), P15 (2012)

    Google Scholar 

  14. Elkin, M.: An Improved Construction of Progression-Free Sets. Israel J. of Math. 184, 93–128 (2011)

    Article  MathSciNet  MATH  Google Scholar 

  15. Erdős, P., Turán, P.: On Some Sequences of Integers. J. London Math. Soc. 11(4), 261–263 (1936)

    Article  Google Scholar 

  16. Gennaro, R., Gentry, C., Parno, B., Raykova, M.: Quadratic Span Programs and NIZKs without PCPs. In: Johansson, T., Nguyen, P.Q. (eds.) EUROCRYPT 2013. LNCS, vol. 7881, pp. 626–645. Springer, Heidelberg (2013)

    Chapter  Google Scholar 

  17. Gentleman, W.M., Sande, G.: Fast Fourier Transforms — For Fun and Profit. In: Fall Joint Computer Conf. AFIPS Proc., vol. 29, pp. 563–578. ACM, Washington, DC (1966)

    Google Scholar 

  18. Gentry, C., Wichs, D.: Separating Succinct Non-Interactive Arguments from All Falsifiable Assumptions. In: Vadhan, S. (ed.) STOC 2011, June 6-8, pp. 99–108. ACM Press, San Jose (2011)

    Google Scholar 

  19. Goldwasser, S., Kalai, Y.T.: On the (In)security of the Fiat-Shamir Paradigm. In: FOCS 2003, October 11–14, pp. 102–113. IEEE (2003)

    Google Scholar 

  20. Goldwasser, S., Micali, S., Rackoff, C.: The Knowledge Complexity of Interactive Proof-Systems. In: Sedgewick, R. (ed.) STOC 1985, May 6-8, pp. 291–304. ACM Press, Providence (1985)

    Google Scholar 

  21. 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)

    Chapter  Google Scholar 

  22. Hess, F., Smart, N.P., Vercauteren, F.: The Eta Pairing Revisited. IEEE Transactions on Information Theory 52(10), 4595–4602 (2006)

    Article  MathSciNet  MATH  Google Scholar 

  23. van Hoeij, M., Novocin, A.: Gradual Sub-lattice Reduction and a New Complexity for Factoring Polynomials. In: López-Ortiz, A. (ed.) LATIN 2010. LNCS, vol. 6034, pp. 539–553. Springer, Heidelberg (2010)

    Chapter  Google Scholar 

  24. Joux, A.: A One-Round Protocol for Tripartite Diffie-Hellman. In: Bosma, W. (ed.) ANTS 2000. LNCS, vol. 1838, pp. 385–393. Springer, Heidelberg (2000)

    Chapter  Google Scholar 

  25. Lenstra, A.K., Lenstra Jr., H.W., Lovász, L.: Factoring Polynomials with Rational Coefficients. Mathematische Annalen 261, 513–534 (1982)

    Article  Google Scholar 

  26. Lipmaa, H.: On Diophantine Complexity and Statistical Zero-Knowledge Arguments. In: Laih, C.-S. (ed.) ASIACRYPT 2003. LNCS, vol. 2894, pp. 398–415. Springer, Heidelberg (2003)

    Chapter  Google Scholar 

  27. 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)

    Chapter  Google Scholar 

  28. 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)

    Chapter  Google Scholar 

  29. Lipmaa, H., Asokan, N., Niemi, V.: Secure Vickrey Auctions without Threshold Trust. In: Blaze, M. (ed.) FC 2002. LNCS, vol. 2357, pp. 87–101. Springer, Heidelberg (2003)

    Chapter  Google Scholar 

  30. 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)

    Chapter  Google Scholar 

  31. Pippenger, N.: On the Evaluation of Powers and Monomials. SIAM J. Comput. 9(2), 230–250 (1980)

    Article  MathSciNet  MATH  Google Scholar 

  32. Rial, A., Kohlweiss, M., Preneel, B.: Universally Composable Adaptive Priced Oblivious Transfer. In: Shacham, H., Waters, B. (eds.) Pairing 2009. LNCS, vol. 5671, pp. 231–247. Springer, Heidelberg (2009)

    Chapter  Google Scholar 

  33. Sakai, R., Ohgishi, K., Kasahara, M.: Cryptosystems Based on Pairing. In: SCIS 2000, Okinawa, Japan (2000)

    Google Scholar 

  34. Sanders, T.: On Roth’s Theorem on Progressions. Ann. of Math. 174(1), 619–636 (2011)

    Article  MathSciNet  MATH  Google Scholar 

  35. Tao, T., Vu, V.: Additive Combinatorics. Cambridge Studies in Advanced Mathematics. Cambridge University Press (2006)

    Google Scholar 

Download references

Author information

Authors and Affiliations

  1. University of Tartu, Estonia

    Prastudy Fauzi & Helger Lipmaa

  2. National and Kapodistrian University of Athens, Greece

    Bingsheng Zhang

Authors
  1. Prastudy Fauzi
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Helger Lipmaa
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Bingsheng Zhang
    View author publications

    You can also search for this author in PubMed Google Scholar

Editor information

Editors and Affiliations

  1. École Normale Supérieure and CNRS,, 45 rue d’Ulm, 75005, Paris, France

    Michel Abdalla

  2. Department of Computer Science, Purdue University, LWSN 2142J, 305 N. University Street,, 47907, West Lafayette, IN, USA

    Cristina Nita-Rotaru

  3. Institute of Computing, University of Campinas, Avenida Albert Einstein 1251, 13083-852, Campinas, SP, Brazil

    Ricardo Dahab

Rights and permissions

Reprints and permissions

Copyright information

© 2013 Springer International Publishing Switzerland

About this paper

Cite this paper

Fauzi, P., Lipmaa, H., Zhang, B. (2013). Efficient Modular NIZK Arguments from Shift and Product. In: Abdalla, M., Nita-Rotaru, C., Dahab, R. (eds) Cryptology and Network Security. CANS 2013. Lecture Notes in Computer Science, vol 8257. Springer, Cham. https://doi.org/10.1007/978-3-319-02937-5_6

Download citation

  • DOI: https://doi.org/10.1007/978-3-319-02937-5_6

  • Publisher Name: Springer, Cham

  • Print ISBN: 978-3-319-02936-8

  • Online ISBN: 978-3-319-02937-5

  • eBook Packages: Computer ScienceComputer Science (R0)

Publish with us

Policies and ethics

Search

Navigation