Concurrent Non-Malleable Witness Indistinguishable Argument from Any One-Way Function

详细信息    查看全文

• 作者：Guifang Huang (18)
  Lei Hu (18)
  
• 关键词：concurrent non ; malleable witness indistinguishability ; strong non ; malleable witness indistinguishability ; commitment ; special ; sound WI proofs
• 刊名：Lecture Notes in Computer Science
• 出版年：2012
• 出版时间：2012
• 年：2012
• 卷：1
• 期：1
• 页码：379-392
• 全文大小：267KB
• 参考文献：1. Barak, B.: How to Go Beyond the Black-Box Barrier. In: 42nd Annual Symposium on Foundations of Computer Science (FOCS 2001), pp. 106鈥?15. IEEE Computer Society Press, Washington (2001)
  2. Barak, B.: Constant-Round Coin-Tossing or Realizing the Shared random String Model. In: 43rd Annual Symposium on Foundations of Computer Science (FOCS 2002), pp. 345鈥?55. IEEE Computer Society Press, Washington (2002) CrossRef
  3. Blum, M.: How to Prove a Theorem So No One Else Can Claim It. In: International Congress of Mahematicians (ICM 1986), pp. 1444鈥?451 (1986)
  4. Cramer, R., Damg氓rd, I., Schoenmakers, B.: Proof of Partial Knowledge and Simplified Design of Witness Hiding Protocols. In: Desmedt, Y.G. (ed.) CRYPTO 1994. LNCS, vol.聽839, pp. 174鈥?87. Springer, Heidelberg (1994)
  5. Di Crescenzo, G., Ishai, Y., Ostrovsky, R.: Non-Interactive and Non-Malleable Commitments. In: Vitter, J.S. (ed.) 30th Annual ACM Symposium on Theory of Computing (STOC 1998), pp. 141鈥?50. ACM Press, New York (1998) CrossRef
  6. Di Crescenzo, G., Katz, J., Ostrovsky, R., Smith, A.: Efficient and Non-interactive Non-malleable Commitment. In: Pfitzmann, B. (ed.) EUROCRYPT 2001. LNCS, vol.聽2045, pp. 40鈥?9. Springer, Heidelberg (2001) CrossRef
  7. Damg氓rd, I., Groth, J.: Non-Interactive and Reusable Non-Malleable Commitment Schemes. In: Larmore, L.L., Goemans, M.X. (eds.) 35th Annual ACM Symposium on Theory of Computing (STOC 2003), pp. 426鈥?37. ACM Press, New York (2003)
  8. Damg氓rd, I.: On 危-Protocols, http://www.daimi.au.dk/~ivan/CPT.html
  9. Dolev, D., Dwork, C., Naor, M.: Non-Malleable Cryptography. SIAM Journal on Computing聽30(2), 391鈥?37 (2000) CrossRef
  10. Dork, C., Naor, M., Sahai, A.: Concurrent Zero Knowledge. In: Vitter, J.S. (ed.) 30th Annual ACM Symposium on Theory of Computing (STOC 1998), pp. 141鈥?50. ACM Press, New York (1998)
  11. Even, S., Goldreich, O., Lempel, A.: A Randomized Protocol for Signing Contracts. Communications of the ACM聽28(6), 637鈥?47 (1985) CrossRef
  12. Fischlin, M., Fischlin, R.: Efficient Non-Malleable Commitment Schemes. In: Bellare, M. (ed.) CRYPTO 2000. LNCS, vol.聽1880, pp. 413鈥?31. Springer, Heidelberg (2000) CrossRef
  13. Feige, U., Lapidot, D., Shamir, A.: Multiple Non-Interactive Zero Knowledge Proofs Under General Assumptions. SIAM Journal on Computing聽29(1), 1鈥?8 (1999) CrossRef
  14. Feige, U., Shamir, A.: Witness Indistinguishable and Witness Hiding Protocols. In: Ortiz, H. (ed.) 22nd Annual Symposium on Theory of Computing (STOC 1990), pp. 416鈥?26. ACM Press, New York (1990)
  15. Garay, J.A., Mackenzie, P., Yang, K.: Strengtheninging Zero Knowledge Protocols Using Signatures. Journal of Cryptology聽19(2), 169鈥?09 (2006) CrossRef
  16. Goldwasser, S., Micali, S., Rackoff, C.: The Knowledge Complexity of Interactive Proof Systems. SIAM Journal on Computing聽18(1), 186鈥?08 (1989) CrossRef
  17. Lin, H., Pass, R., Venkitasubramaniam, M.: Concurrent Non-malleable Commitments from Any One-Way Function. In: Canetti, R. (ed.) TCC 2008. LNCS, vol.聽4948, pp. 571鈥?88. Springer, Heidelberg (2008) CrossRef
  18. Lin, H., Pass, R., Venkitasubramaniam, M.: A Unified Framework for Concrrent Security: Universal Composability from Stand-Alone Non-Malleability. In: Mitzenmacher, M. (ed.) 41st Annual ACM Symposium on Theory of Computing (STOC 2009), pp. 179鈥?88. ACM Press, New York (2009) CrossRef
  19. Lin, H., Pass, R., Tseng, W.-L.D., Venkitasubramaniam, M.: Concurrent Non-Malleable Zero Knowledge Proofs. In: Rabin, T. (ed.) CRYPTO 2010. LNCS, vol.聽6223, pp. 429鈥?46. Springer, Heidelberg (2010)
  20. Naor, M.: Bit Commitment Using Pseudo-Randomness. Journal of Crypto.聽4(2), 151鈥?58 (1991)
  21. Ostrovsky, R., Persiano, G., Visconti, I.: Concurrent Non-Malleable Witness Indistinguishability and Its Applications. Electronic Colloquium on Computational Complexity (ECCC), Report (2006)
  22. Ostrovsky, R., Persiano, G., Visconti, I.: Constant-Round Concurrent Non-malleable Zero Knowledge in the Bare Public-Key Model. In: Aceto, L., Damg氓rd, I., Goldberg, L.A., Halld贸rsson, M.M., Ing贸lfsd贸ttir, A., Walukiewicz, I. (eds.) ICALP 2008, Part II. LNCS, vol.聽5126, pp. 548鈥?59. Springer, Heidelberg (2008) CrossRef
  23. Ostrovsky, R., Persiano, G., Visconti, I.: Simulation-Based Concurrent Non-Malleable Commitments and Decommitments. In: Reingold, O. (ed.) TCC 2009. LNCS, vol.聽5444, pp. 91鈥?08. Springer, Heidelberg (2009) CrossRef
  24. Pass, R., Rosen, A.: New and Improved Constructions of Non-Malleable Cryptographic Protocols. In: Gabow, H.N., Fagin, R. (eds.) 37th Annual ACM Symposium on Theory of Computing (STOC 2005), pp. 533鈥?42. ACM Press, New York (2005) CrossRef
  25. Pass, R., Rosen, A.: Concurrent Non-Malleable Commitments. In: 46th Annual Symposium on Foundations of Computer Science (FOCS 2005), pp. 563鈥?72. IEEE Computer Society Press, Washington (2005) CrossRef
  26. Rompel, J.: One-Way Function are Necessary and Sufficient for Secure Signatures. In: Ortiz, H. (ed.) 22nd Annual ACM Symposium on Theory of Computing (STOC 1990), pp. 387鈥?94. ACM Press, New York (1990) CrossRef
  27. Richardson, R., Kilian, J.: On the Concurrent Composition of Zero-Knowledge Proofs. In: Stern, J. (ed.) EUROCRYPT 1999. LNCS, vol.聽1592, pp. 415鈥?31. Springer, Heidelberg (1999)
  28. Sahai, A.: Non-Malleable Non-Interactive Zero Knowledge and Adaptive Chosen Cipher-Text Security. In: 40th Annual Symposium on Foundations of Computer Science (FOCS 1999), pp. 543鈥?53. IEEE Computer Society Press, Washington (1999)
  29. De Santis, A., Di Crescenzo, G., Ostrovsky, R., Persiano, G., Sahai, A.: Robust Non-interactive Zero Knowledge. In: Kilian, J. (ed.) CRYPTO 2001. LNCS, vol.聽2139, pp. 566鈥?98. Springer, Heidelberg (2001) CrossRef
  
• 作者单位：Guifang Huang (18)
  Lei Hu (18)
  
  18. State Key Laboratory of Information Security, Graduate University of Chinese Academy of Sciences, Beijing, 100049, P.R. China
  
• ISSN：1611-3349

文摘

Non-malleable witness indistinguishability (NMWI) is a security notion against man-in-the-middle attacks which requires that the witness encoded in the right interaction is computationally independent of that used by honest prover in the left. In STOC 2009, Lin et al. defined strongly non-malleable witness indistinguishability (SNMWI) which is similar in spirit to NMWI, and proposed a SNMWI scheme based on one-way function. In this paper, we firstly show that the two notions NMWI and SNMWI are incomparable: there exists a SNMWI argument which is not NMWI, and vice versa. Furthermore, it is pointed out that the SNMWI construction given in STOC 2009 is not NMWI. Then, we present a variant of LPV08 scheme [17] and show that this variant is a concurrent NMWI argument. Compared with the concurrent NMWI argument of [22] which was shown to be non-malleable by using non-black-box techniques and whose difficulty assumption was claw-free permutation, our new scheme is based on the existence of one-way functions and its proof of security relies on black-box techniques.