Abstract
After the work of Impagliazzo and Rudich (STOC, 1989), the black box framework has become one of the main research domain of cryptography. However black box techniques say nothing about non-black box techniques such as making use of zero-knowledge proofs. Brakerski et al. introduced a new black box framework named augmented black box framework, in which they gave a zero-knowledge proof oracle in addition to a base primitive oracle (TCC, 2011). They showed a construction of a non-interactive zero knowledge proof system based on a witness indistinguishable proof system oracle. They presented augmented black box construction of chosen ciphertext secure public key encryption scheme based on chosen plaintext secure public key encryption scheme and augmented black box separation between one-way function and key agreement.
In this paper we simplify the work of Brakerski et al. by introducing a proof system oracle without witness indistinguishability, named coin-free proof system oracle, that aims to give the same construction and separation results of previous work. As a result, the augmented black box framework becomes easier to handle. Since our oracle is not witness indistinguishable, our result encompasses the result of previous work.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
Change history
26 September 2019
The original structure of the book is incorrect and cannot be corrected. The papers “A Coin-Free Oracle-Based Augmented Black Box Framework” (Chapter 15) and “FSPVDsse: A Forward Secure Publicly Verifiable Dynamic SSE Scheme” (Chapter 23) were switched. Chapter 15 was supposed to appear under the Part Title: Short Papers, while Chapter 23 was supposed to appear under the Part Title: Protocols.
References
Boneh, D., Papakonstantinou, P., Rackoff, C., Vahlis, Y., Waters, B.: On the impossibility of basing identity based encryption on trapdoor permutations. In: Proceedings of the 2008 49th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2008, pp. 283–292. IEEE Computer Society, Washington, DC, USA (2008). https://doi.org/10.1109/FOCS.2008.67
Brakerski, Z., Katz, J., Segev, G., Yerukhimovich, A.: Limits on the power of zero-knowledge proofs in cryptographic constructions. In: Ishai, Y. (ed.) TCC 2011. LNCS, vol. 6597, pp. 559–578. Springer, Heidelberg (2011). https://doi.org/10.1007/978-3-642-19571-6_34
Diffie, W., Hellman, M.: New directions in cryptography. IEEE Trans. Inf. Theory 22, 644–654 (1976). https://doi.org/10.1109/TIT.1976.1055638
Feige, U., Shamir, A.: Witness indistinguishable and witness hiding protocols. In: Proceedings of the Twenty-second Annual ACM Symposium on Theory of Computing, STOC 1990. pp. 416–426. ACM, New York (1990). https://doi.org/10.1145/100216.100272
Goldwasser, S., Micali, S., Rackoff, C.: The knowledge complexity of interactive proof-systems. In: Proceedings of the Seventeenth Annual ACM Symposium on Theory of Computing, STOC 1985, pp. 291–304. ACM, New York (1985). https://doi.org/10.1145/22145.22178
Impagliazzo, R., Rudich, S.: Limits on the provable consequences of one-way permutations. In: Proceedings of the Twenty-first Annual ACM Symposium on Theory of Computing, STOC 1989, pp. 44–61. ACM, New York (1989). https://doi.org/10.1145/73007.73012
Karp, R.M.: Reducibility among Combinatorial Problems. In: Miller, R.E., Thatcher, J.W., Bohlinger, J.D. (eds.) Complexity of Computer Computations. The IBM Research Symposia Series, pp. 85–103. Springer, Boston (1972). https://doi.org/10.1007/978-1-4684-2001-2_9
Naor, M., Yung, M.: Public-key cryptosystems provably secure against chosen ciphertext attacks. In: Proceedings of the Twenty-Second Annual ACM Symposium on Theory of Computing, STOC 1990. pp. 427–437. ACM, New York (1990). https://doi.org/10.1145/100216.100273
Reingold, O., Trevisan, L., Vadhan, S.: Notions of reducibility between cryptographic primitives. In: Naor, M. (ed.) TCC 2004. LNCS, vol. 2951, pp. 1–20. Springer, Heidelberg (2004). https://doi.org/10.1007/978-3-540-24638-1_1
Sahai, A.: Non-malleable non-interactive zero knowledge and adaptive chosen-ciphertext security. In: Proceedings of the 40th Annual Symposium on Foundations of Computer Science. FOCS 1999, p. 543. IEEE Computer Society, Washington, DC (1999)
Yamashita, K., Tibouchi, M., Abe, M.: A coin-free oracle-based augmented black box framework. Cryptology ePrint Archive, Report 2019/859 (2019). https://eprint.iacr.org/2019/859
Yao, A.C.: Theory and application of trapdoor functions. In: Proceedings of the 23rd Annual Symposium on Foundations of Computer Science, SFCS 1982, pp. 80–91. IEEE Computer Society, Washington, DC (1982). https://doi.org/10.1109/SFCS.1982.95
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2019 Springer Nature Switzerland AG
About this paper
Cite this paper
Yamashita, K., Tibouchi, M., Abe, M. (2019). A Coin-Free Oracle-Based Augmented Black Box Framework. In: Steinfeld, R., Yuen, T. (eds) Provable Security. ProvSec 2019. Lecture Notes in Computer Science(), vol 11821. Springer, Cham. https://doi.org/10.1007/978-3-030-31919-9_15
Download citation
DOI: https://doi.org/10.1007/978-3-030-31919-9_15
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-030-31918-2
Online ISBN: 978-3-030-31919-9
eBook Packages: Computer ScienceComputer Science (R0)