Efficient Non-interactive Universally Composable String-Commitment Schemes | SpringerLink
Skip to main content
Springer Nature Link
Log in

Efficient Non-interactive Universally Composable String-Commitment Schemes

  • Conference paper
Provable Security (ProvSec 2009)

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

Included in the following conference series:

Abstract

The universal composability (UC) for commitment is a very strong security notion. It guarantees that commitment schemes remain secure even if they are composed with arbitrary protocols and polynomially many copies of the schemes are run concurrently. Several UC commitment schemes in the common reference string (CRS) model have been proposed, but, they are either interactive commitment or bit-commitment (not string-commitment) schemes. We propose new non-interactive string-commitment schemes that achieve UC security in the CRS model assuming the difficulty of the decisional Diffie-Hellman problem or the decisional composite residuosity problem, but our schemes are not reusable. The main building blocks of our constructions are all-but-one trapdoor functions (ABO-TDFs) introduced by Peikert and Waters in STOC 2008 to construct secure public-key encryption schemes. Our main idea is to use the homomorphic properties of the function indices of the all-but-one trapdoor functions and to extend the functions to probabilistic ones by using re-randomization of ciphertexts. This is a new application of ABO-TDFs.

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

Access this chapter

Log in via an institution

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. Barak, B., Canetti, R., Nielsen, J.B., Pass, R.: Universally Composable Protocols with Relaxed Set-up Assumptions. In: FOCS 2004, pp. 186–195 (2004)

    Google Scholar 

  2. Camenisch, J., 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)

    Google Scholar 

  3. Canetti, R.: Universally Composable Security: A New Paradigm for Cryptograpic Protocols. In: Cryptology ePrint Archive, Report 2000/067, Preliminary version appeared in FOCS 2001 (2005)

    Google Scholar 

  4. Canetti, R., Dodis, Y., Pass, R., Walfish, S.: Universally Composable Security with Global Setup. In: Vadhan, S.P. (ed.) TCC 2007. LNCS, vol. 4392, pp. 61–85. Springer, Heidelberg (2007)

    Chapter  Google Scholar 

  5. Canetti, R., Fischlin, M.: Universally Composable Commitments. In: Kilian, J. (ed.) CRYPTO 2001. LNCS, vol. 2139, pp. 19–40. Springer, Heidelberg (2001)

    Chapter  Google Scholar 

  6. Canetti, R., Kushilevitz, E., Lindell, Y.: On the Limitations of Universally Composable Two-Party Computation Without Set-Up Assumptions. J. Cryptology 19(2), 135–167 (2006)

    Article  MATH  MathSciNet  Google Scholar 

  7. Canetti, R., Lindell, Y., Ostrovsky, R., Sahai, A.: Universally Composable Two-Party and Multi-Party Secure Computation. In: STOC 2002, pp. 494–503 (2002)

    Google Scholar 

  8. Canetti, R., Pass, R., Shelat, A.: Cryptography from Sunspots: How to Use an Imperfect Reference String. In: FOCS 2007, pp. 249–259 (2007)

    Google Scholar 

  9. Canetti, R., Rabin, T.: Universal Composition with Joint State. In: Boneh, D. (ed.) CRYPTO 2003. LNCS, vol. 2729, pp. 265–281. Springer, Heidelberg (2003)

    Google Scholar 

  10. Damgård, I., Jurik, M.: A Generalisation, a Simplification and Some Applications of Paillier’s Probabilistic Public-Key System. In: Kim, K.-c. (ed.) PKC 2001. LNCS, vol. 1992, pp. 125–140. Springer, Heidelberg (2001)

    Chapter  Google Scholar 

  11. Damgård, I., Groth, J.: Non-interactive and Reusable Non-Malleable Commitment Schemes. In: STOC 2003, pp. 426–437 (2003)

    Google Scholar 

  12. Damgård, I., Nielsen, J.B.: Perfect Hiding and Perfect Binding Universally Composable Commitment Schemes with Constant Expansion Factor. In: Yung, M. (ed.) CRYPTO 2002. LNCS, vol. 2442, pp. 581–596. Springer, Heidelberg (2002)

    Chapter  Google Scholar 

  13. Dodis, Y., Ostrovsky, R., Reyzin, L., Smith, A.: Fuzzy Extractors: How to Generate Strong Keys from Biometrics and Other Noisy Data. SIAM J. Computing 38(1), 97–139 (2008)

    Article  MATH  MathSciNet  Google Scholar 

  14. Dolev, D., Dwork, C., Naor, M.: Non-malleable cryptography. SIAM J. Computing 30, 391–437 (2000)

    Article  MATH  MathSciNet  Google Scholar 

  15. Goldreich, O., Micali, S., Wigderson, A.: Proofs that Yield Nothing but their Validity, or All Languages in NP have Zero-Knowledge Proof Systems. Journal of the ACM 38(3), 691–729 (1991); Preliminary version appeared in FOCS 1986

    Article  MATH  MathSciNet  Google Scholar 

  16. Hofheinz, D., Müller-Quade, J.: Universally Composable Commitments Using Random Oracles. In: Naor, M. (ed.) TCC 2004. LNCS, vol. 2951, pp. 58–76. Springer, Heidelberg (2004)

    Google Scholar 

  17. Katz, J.: Universally Composable Multi-party Computation Using Tamper-Proof Hardware. In: Naor, M. (ed.) EUROCRYPT 2007. LNCS, vol. 4515, pp. 115–128. Springer, Heidelberg (2007)

    Chapter  Google Scholar 

  18. Naor, M.: Bit Commitment Using Pseudorandomness. J. Cryptology 4(2), 151–158 (1991)

    Article  MATH  Google Scholar 

  19. Pedersen, T.P.: Non-Interactive and Information-Theoretic Secure Verifiable Secret Sharing. In: Feigenbaum, J. (ed.) CRYPTO 1991. LNCS, vol. 576, pp. 129–140. Springer, Heidelberg (1992)

    Google Scholar 

  20. Peikert, C., Waters, B.: Lossy Trapdoor Functions and Their Applications. In: STOC 2008, pp. 187–196 (2008)

    Google Scholar 

  21. Prabhakaran, M., Sahai, A.: New Notions of Security: Achieving Universal Composability without Trusted Setup. In: STOC 2004, pp. 242–251 (2004)

    Google Scholar 

  22. Rosen, A., Segev, G.: Efficient Lossy Trapdoor Functions based on the Composite Residuosity Assumption. In: Cryptology ePrint Archive, Report 2008/134 (2008)

    Google Scholar 

  23. Zhu, H.: New Constructions for Reusable, Non-erasure and Universally Composable Commitments. In: Bao, F., Li, H., Wang, G. (eds.) ISPEC 2009. LNCS, vol. 5451, pp. 102–111. Springer, Heidelberg (2009)

    Google Scholar 

Download references

Author information

Authors and Affiliations

  1. NTT, 3-9-11 Midori-cho, Musashino-shi, Tokyo, 180-8585, Japan

    Ryo Nishimaki & Eiichiro Fujisaki

  2. Department of Mathematical and Computing Sciences, Tokyo Institute of Technology, W8-55, 2-12-1 Ookayama, Meguro-ku, Tokyo, 152-8552, Japan

    Ryo Nishimaki & Keisuke Tanaka

Authors
  1. Ryo Nishimaki
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Eiichiro Fujisaki
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Keisuke Tanaka
    View author publications

    You can also search for this author in PubMed Google Scholar

Editor information

Editors and Affiliations

  1. Department of Computing, Macquarie University, 2109, Sydney, NSW, Australia

    Josef Pieprzyk

  2. School of Information Science and Technology, Sun Yat-Sen University, 510275, Guangzhou, P.R.China

    Fangguo Zhang

Rights and permissions

Reprints and permissions

Copyright information

© 2009 Springer-Verlag Berlin Heidelberg

About this paper

Cite this paper

Nishimaki, R., Fujisaki, E., Tanaka, K. (2009). Efficient Non-interactive Universally Composable String-Commitment Schemes. In: Pieprzyk, J., Zhang, F. (eds) Provable Security. ProvSec 2009. Lecture Notes in Computer Science, vol 5848. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-04642-1_3

Download citation

  • DOI: https://doi.org/10.1007/978-3-642-04642-1_3

  • Publisher Name: Springer, Berlin, Heidelberg

  • Print ISBN: 978-3-642-04641-4

  • Online ISBN: 978-3-642-04642-1

  • eBook Packages: Computer ScienceComputer Science (R0)

Publish with us

Policies and ethics

Search

Navigation