One-Round Witness Indistinguishability from Indistinguishability Obfuscation

详细信息    查看全文

• 作者：Qihua Niu (15) (16)
  Hongda Li (15)
  Guifang Huang (15)
  Bei Liang (15)
  Fei Tang (15)
  
  15. State Key Lab of Information Security ; Institute of Information Engineering ; Chinese Academy of Sciences ; Beijing ; 100093 ; China
  16. School of Science ; University of Petroleum ; China ; Qingdao ; 266580
  
• 关键词：Witness indistinguishability ; indistinguishability obfuscation ; weak auxiliary input multi ; bit output point obfuscation ; witness encryption scheme with unique decryption
• 刊名：Lecture Notes in Computer Science
• 出版年：2015
• 出版时间：2015
• 年：2015
• 卷：9065
• 期：1
• 页码：559-574
• 全文大小：279 KB
• 参考文献：1. Barak, B., Goldreich, O., Impagliazzo, R., Rudich, S., Sahai, A., Vadhan, S.P., Yang, K. On the (Im)possibility of Obfuscating Programs. In: Kilian, J. eds. (2001) Advances in Cryptology - CRYPTO 2001. Springer, Heidelberg, pp. 1-18 CrossRef
  2. Barak, B., Goldreich, O., Impagliazzo, R., Rudich, S., Sahai, A., Vadhan, S.P., Yang, K. (2012) On the (im)possibility of obfuscating programs. J.ACM 59: pp. 6 CrossRef
  3. Barak, B., Ong, S.J., Vadhan, S. Derandomization in Cryptography. In: Boneh, D. eds. (2003) Advances in Cryptology - CRYPTO 2003. Springer, Heidelberg, pp. 299-315 CrossRef
  4. Bitansky, N., Canetti, R. On strong simulation and composable point obfuscation. In: Rabin, T. eds. (2010) Advances in Cryptology 鈥?CRYPTO 2010. Springer, Heidelberg, pp. 520-537 CrossRef
  5. Bitansky, N., Canetti, R., Paneth, O., Rosen, A.: More on the impossibility of VBB obfuscation with auxiliary input. IACR Cryptology ePrint Archive, 2013:701 (2013)
  6. Bitansky, N., Paneth, O. Point obfuscation and 3-round zero-knowledge. In: Cramer, R. eds. (2012) Theory of Cryptography. Springer, Heidelberg, pp. 190-208 CrossRef
  7. Brzuska, C., Mittelbach, A.: Indistinguishability obfuscation versus point obfuscation with auxiliary input. IACR Cryptology ePrint Archive, 2014:405 (2014)
  8. Canetti, R. Towards realizing random oracles: Hash functions that hide all partial information. In: Kaliski, B.S. eds. (1997) Advances in Cryptology - CRYPTO 鈥?7. Springer, Heidelberg, pp. 455-469 CrossRef
  9. Canetti, R., Dakdouk, R.R. Obfuscating point functions with multibit output. In: Smart, N.P. eds. (2008) Advances in Cryptology 鈥?EUROCRYPT 2008. Springer, Heidelberg, pp. 489-508 CrossRef
  10. Dwork, C., Naor, M.: Zaps and their applications. In: proceedings of the 41th Annual Symposium on Foundations of Computer Science, pp. 283鈥?93. ACM (2000)
  11. Feige, U., Shamir, A.: Witness Indistinguishable and Witness Hiding Protocols. In: Proc. 22nd ACM Symposium on the Theory of Computing, pp. 416鈥?26 (1990)
  12. Garg, S., Gentry, C., Halevi, S., Raykova, M., Sahai, A., Waters, B.: Candidate indistinguishability obfuscation and functional encryption for all circuits. In: FOCS, pp. 40鈥?9 (2013)
  13. Garg, S., Gentry, C., Sahai, A., Waters, B.: Witness encryption and its applications. In: STOC, pp. 467鈥?76 (2013)
  14. Goldreich, O., Oren, Y. (1994) Definitions and properties of zero-knowledge proof systems. Journal of Cryptology 7: pp. 1-32 CrossRef
  15. Goldwasser, S., Kalai, Y.T.: On the impossibility of obfuscation with auxiliary input. In: FOCS, pp. 553鈥?62 (2005)
  16. Goldwasser, S., Kalai, Y.T.: A Note on the Impossibility of Obfuscation with Auxiliary Inputs. IACR Cryptology ePrint Archive, 2013:665 (2013)
  17. Groth, J., Ostrovsky, R., Sahai, A. (2012) New techniques for noninteractive zero-knowledge. J.ACM 59: pp. 11 CrossRef
  18. Goldwasser, S., Micali, S., Rackoff, C. (1989) The knowledge complexity of interactive proof systems. SIAM Journal on Computing 18: pp. 186-208 CrossRef
  19. Goldreich, O., Micali, S., Wigderson, A. (1991) Proofs that yield nothing but their validity or all languages in NP have zero-knowledge proof systems. J. of the ACM 38: pp. 691-729 CrossRef
  20. Goldwasser, S., Rothblum, G.N. On best-possible obfuscation. In: Vadhan, S.P. eds. (2007) Theory of Cryptography. Springer, Heidelberg, pp. 194-213 CrossRef
  21. Hofheinz, D., Malone-Lee, J., Stam, M. Obfuscation for cryptographic purposes. In: Vadhan, S.P. eds. (2007) Theory of Cryptography. Springer, Heidelberg, pp. 214-232 CrossRef
  22. Hohenberger, S., Rothblum, G.N., Shelat, A., Vaikuntanathan, V. Securely obfuscating re-encryption. In: Vadhan, S.P. eds. (2007) Theory of Cryptography. Springer, Heidelberg, pp. 233-252 CrossRef
  23. Matsuda, T., Hanaoka, G. Chosen ciphertext security via point obfuscation. In: Lindell, Y. eds. (2014) Theory of Cryptography. Springer, Heidelberg, pp. 95-120 CrossRef
  24. Wee, H.: On obfuscating point functions. In: STOC, pp. 523鈥?32 (2005)
  
• 作者单位：Information Security Practice and Experience
• 丛书名：978-3-319-17532-4
• 刊物类别：Computer Science
• 刊物主题：Artificial Intelligence and Robotics
  Computer Communication Networks
  Software Engineering
  Data Encryption
  Database Management
  Computation by Abstract Devices
  Algorithm Analysis and Problem Complexity
  
• 出版者：Springer Berlin / Heidelberg
• ISSN：1611-3349

文摘

In this work, we build up the relationship between witness indistinguishability (WI) and indistinguishability obfuscation ( \(i\mathcal{O}\) ) by constructing a one-round witness indistinguishable argument system for all languages in NP based on the existence of indistinguishability obfuscator for general circuit class and a number-theoretic assumption. The key tool in our construction is witness encryption scheme with unique decryption which is also proposed and constructed in this work. Our construction of witness encryption scheme with unique decryption is based on a general witness encryption scheme and a weak auxiliary input multi-bit output point obfuscation.