Abstract
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.
This work is supported by the National Natural Science Foundation of China (Grant No. 60970139,61003276).
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
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. (ed.) CRYPTO 2001. LNCS, vol. 2139, pp. 1–18. Springer, Heidelberg (2001)
Barak, B., Goldreich, O., Impagliazzo, R., Rudich, S., Sahai, A., Vadhan, S.P., Yang, K.: On the (im)possibility of obfuscating programs. J.ACM 59(2), 6 (2012)
Barak, B., Ong, S.J., Vadhan, S.: Derandomization in Cryptography. In: Boneh, D. (ed.) CRYPTO 2003. LNCS, vol. 2729, pp. 299–315. Springer, Heidelberg (2003)
Bitansky, N., Canetti, R.: On strong simulation and composable point obfuscation. In: Rabin, T. (ed.) CRYPTO 2010. LNCS, vol. 6223, pp. 520–537. Springer, Heidelberg (2010)
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)
Bitansky, N., Paneth, O.: Point obfuscation and 3-round zero-knowledge. In: Cramer, R. (ed.) TCC 2012. LNCS, vol. 7194, pp. 190–208. Springer, Heidelberg (2012)
Brzuska, C., Mittelbach, A.: Indistinguishability obfuscation versus point obfuscation with auxiliary input. IACR Cryptology ePrint Archive, 2014:405 (2014)
Canetti, R.: Towards realizing random oracles: Hash functions that hide all partial information. In: Kaliski Jr., B.S. (ed.) CRYPTO 1997. LNCS, vol. 1294, pp. 455–469. Springer, Heidelberg (1997)
Canetti, R., Dakdouk, R.R.: Obfuscating point functions with multibit output. In: Smart, N.P. (ed.) EUROCRYPT 2008. LNCS, vol. 4965, pp. 489–508. Springer, Heidelberg (2008)
Dwork, C., Naor, M.: Zaps and their applications. In: proceedings of the 41th Annual Symposium on Foundations of Computer Science, pp. 283–293. ACM (2000)
Feige, U., Shamir, A.: Witness Indistinguishable and Witness Hiding Protocols. In: Proc. 22nd ACM Symposium on the Theory of Computing, pp. 416–426 (1990)
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–49 (2013)
Garg, S., Gentry, C., Sahai, A., Waters, B.: Witness encryption and its applications. In: STOC, pp. 467–476 (2013)
Goldreich, O., Oren, Y.: Definitions and properties of zero-knowledge proof systems. Journal of Cryptology 7(1), 1–32 (1994)
Goldwasser, S., Kalai, Y.T.: On the impossibility of obfuscation with auxiliary input. In: FOCS, pp. 553–562 (2005)
Goldwasser, S., Kalai, Y.T.: A Note on the Impossibility of Obfuscation with Auxiliary Inputs. IACR Cryptology ePrint Archive, 2013:665 (2013)
Groth, J., Ostrovsky, R., Sahai, A.: New techniques for noninteractive zero-knowledge. J.ACM 59(3), 11 (2012)
Goldwasser, S., Micali, S., Rackoff, C.: The knowledge complexity of interactive proof systems. SIAM Journal on Computing 18(16), 186–208 (1989)
Goldreich, O., Micali, S., Wigderson, A.: Proofs that yield nothing but their validity or all languages in NP have zero-knowledge proof systems. J. of the ACM 38(3), 691–729 (1991)
Goldwasser, S., Rothblum, G.N.: On best-possible obfuscation. In: Vadhan, S.P. (ed.) TCC 2007. LNCS, vol. 4392, pp. 194–213. Springer, Heidelberg (2007)
Hofheinz, D., Malone-Lee, J., Stam, M.: Obfuscation for cryptographic purposes. In: Vadhan, S.P. (ed.) TCC 2007. LNCS, vol. 4392, pp. 214–232. Springer, Heidelberg (2007)
Hohenberger, S., Rothblum, G.N., Shelat, A., Vaikuntanathan, V.: Securely obfuscating re-encryption. In: Vadhan, S.P. (ed.) TCC 2007. LNCS, vol. 4392, pp. 233–252. Springer, Heidelberg (2007)
Matsuda, T., Hanaoka, G.: Chosen ciphertext security via point obfuscation. In: Lindell, Y. (ed.) TCC 2014. LNCS, vol. 8349, pp. 95–120. Springer, Heidelberg (2014)
Wee, H.: On obfuscating point functions. In: STOC, pp. 523–532 (2005)
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2015 Springer International Publishing Switzerland
About this paper
Cite this paper
Niu, Q., Li, H., Huang, G., Liang, B., Tang, F. (2015). One-Round Witness Indistinguishability from Indistinguishability Obfuscation. In: Lopez, J., Wu, Y. (eds) Information Security Practice and Experience. ISPEC 2015. Lecture Notes in Computer Science(), vol 9065. Springer, Cham. https://doi.org/10.1007/978-3-319-17533-1_38
Download citation
DOI: https://doi.org/10.1007/978-3-319-17533-1_38
Publisher Name: Springer, Cham
Print ISBN: 978-3-319-17532-4
Online ISBN: 978-3-319-17533-1
eBook Packages: Computer ScienceComputer Science (R0)