×

Constructions for quantum indistinguishability obfuscation. (English) Zbl 1497.81039

Longa, Patrick (ed.) et al., Progress in cryptology – LATINCRYPT 2021. 7th international conference on cryptology and information security in Latin America, Bogotá, Colombia, October 6–8, 2021. Proceedings. Cham: Springer. Lect. Notes Comput. Sci. 12912, 24-43 (2021).
Summary: An indistinguishability obfuscator is a polynomial-time probabilistic algorithm that takes a circuit as input and outputs a new circuit that has the same functionality as the input circuit, such that for any two circuits of the same size that compute the same function, the outputs of the indistinguishability obfuscator are indistinguishable. Here, we study schemes for indistinguishability obfuscation for quantum circuits. We present two definitions for indistinguishability obfuscation: in our first definition \((qi\mathcal{O})\) the outputs of the obfuscator are required to be indistinguishable if the input circuits are perfectly equivalent, while in our second definition \((qi\mathcal{O}_\mathbf{D} )\), the outputs are required to be indistinguishable as long as the input circuits are approximately equivalent with respect to a pseudo-distance \(\mathbf{D}\). Our main results provide (1) a computationally-secure scheme for \(qi\mathcal{O}\) where the size of the output of the obfuscator is exponential in the number of non-Clifford (\( \mathsf{T}\) gates), which means that the construction is efficient as long as the number of \(\mathsf{T}\) gates is logarithmic in the circuit size and (2) a statistically-secure \(qi\mathcal{O}_\mathbf{D},\) for circuits that are close to the \(k\)th level of the Gottesman-Chuang hierarchy (with respect to \(\mathbf{D}\)); this construction is efficient as long as \(k\) is small and fixed.
For the entire collection see [Zbl 1487.94007].

MSC:

81P94 Quantum cryptography (quantum-theoretic aspects)
94A60 Cryptography
68Q10 Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.)
68Q06 Networks and circuits as models of computation; circuit complexity
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] Aaronson, S.: Quantum copy-protection and quantum money. In: 24th Annual Conference on Computational Complexity-CCC 2009, pp. 229-242 (2009). doi:10.1109/CCC.2009.42
[2] Aaronson, S., Gottesman, D.: Improved simulation of stabilizer circuits. Phys. Rev. A 70(5), 052328 (2004). doi:10.1103/PhysRevA.70.052328
[3] Alagic, G., Brakerski, Z., Dulek, Y., Schaffner, C.: Impossibility of quantum virtual black-box obfuscation of classical circuits (2020). https://arxiv.org/abs/2005.06432 · Zbl 1487.81059
[4] Alagic, G., Fefferman. G.: On quantum obfuscation (2016). https://arxiv.org/abs/1602.01771
[5] Alagic, G., Jeffery, S., Jordan. S.: Circuit obfucation using braids. In: 9th Conference on the Theory of Quantum Computation, Communication and Cryptography-TQC 2014, pp. 141-160 (2014). doi:10.4230/LIPIcs.TQC.2014.141 · Zbl 1359.94568
[6] Albrecht, M., Bai, S., Ducas, L.: A subfield lattice attack on overstretched NTRU assumptions. In : Advances in Cryptology-CRYPTO 2016, vol. 1, pp. 153-178 (2016). doi:10.1007/978-3-662-53018-4_6 · Zbl 1351.94019
[7] Amy, M.; Maslov, D.; Mosca, M., Polynomial-time \(T\)-depth optimization of Clifford+\(T\) circuits via matroid partitioning, IEEE Trans. Comput.-Aided Des. Integr. Circ. Syst., 33, 10, 1476-1489 (2014) · doi:10.1109/TCAD.2014.2341953
[8] Amy, M.; Maslov, D.; Mosca, M.; Roetteler, M., A meet-in-the-middle algorithm for fast synthesis of depth-optimal quantum circuits, IEEE Trans. Comput.-Aid. Des. Integr. Circ. Syst., 32, 6, 818-830 (2013) · doi:10.1109/TCAD.2013.2244643
[9] Ananth, P., Jain, A., Lin, H., Matt, C., Sahai, A.: Indistinguishability obfuscation without multilinear maps: new paradigms via low degree weak pseudorandomness and security amplification. In: Advances in Cryptology-CRYPTO 2019, vol. 3, pp.284-332 (2019). doi:10.1007/978-3-030-26954-8_10 · Zbl 1436.94030
[10] Ananth, P., La Placa, R.L.: Secure software leasing (2020). https://arxiv.org/abs/2005.05289 · Zbl 07440617
[11] Barak, B.; Goldreich, O.; Impagliazzo, R.; Rudich, S.; Sahai, A.; Vadhan, S.; Yang, K., On the (im)possibility of obfuscating programs, J. ACM, 59, 2, 6 (2012) · Zbl 1281.68118 · doi:10.1145/2160158.2160159
[12] Bitansky, N., Paneth, O.: ZAPs and non-interactive witness indistinguishability from indistinguishability obfuscation. In: 12th Theory of Cryptography Conference-TCC 2015, vol. II, pp. 401-427 (2015). doi:10.1007/978-3-662-46497-7_16 · Zbl 1319.94053
[13] Boneh, D., Zhandry, M.: Multiparty key exchange, efficient traitor tracing, and more from indistinguishability obfuscation. In: Advances in Cryptology-CRYPTO 2014, vol. I, pp. 480-499 (2014). doi:10.1007/978-3-662-44371-2_27 · Zbl 1310.94130
[14] Brakerski, Z.: Quantum FHE: (almost) as secure as classical. In: Advances in Cryptology-CRYPTO 2018, vol. 3, pp. 67-95 (2018). doi:10.1007/978-3-319-96878-0_3 · Zbl 1457.94102
[15] Broadbent, A., Jeffery, S.: Quantum homomorphic encryption for circuits of low T-gate complexity. In: Advances in Cryptology-CRYPTO 2015, vol. 2, pp. 609-629 (2015). doi:10.1007/978-3-662-48000-7_30 · Zbl 1369.94521
[16] Broadbent, A., Kazmi, R.A.: Constructions for quantum indistinguishability obfuscation (2020). https://eprint.iacr.org/2020/639
[17] Broadbent, A., Lord, S.: Uncloneable quantum encryption via oracles. In: Theory of Quantum Computation, Communication, and Cryptography-TQC 2020, pp. 4:1-4:22 (2020). doi:10.4230/LIPIcs.TQC.2020.4 · Zbl 1507.81067
[18] Canetti, R., Lin, H., Tessaro, S., Vaikuntanathan, V.: Obfuscation of probabilistic circuits and applications. In: 12th Theory of Cryptography Conference-TCC 2015, vol. II, pp. 468-497 (2015). doi:10.1007/978-3-662-46497-7_19 · Zbl 1382.94078
[19] Chen, Y., Gentry, C., Halevi, S.: Cryptanalyses of candidate branching program obfuscators. In: Advances in Cryptology-EUROCRYPT 2017, vol. 3, pp. 278-307 (2017). doi:10.1007/978-3-319-56617-7_10 · Zbl 1415.94418
[20] Coron, J.-S. Lepoint, T., Tibouchi, M.: Practical multilinear maps over the integers. In: Advances in Cryptology-CRYPTO 2013, vol. 1, pp. 476-493 (2013). doi:10.1007/978-3-642-40041-4_26 · Zbl 1309.94139
[21] Cramer, R., Ducas, L., Peikert, C., Regev, O.: Recovering short generators of principal ideals in cyclotomic rings. In: Advances in Cryptology-EUROCRYPT 2016, vol. 2, pp. 559-585 (2016). doi:10.1007/978-3-662-49896-5_20 · Zbl 1371.94630
[22] Di Matteo, O., Mosca, M.: Parallelizing quantum circuit synthesis. Quant. Sci. Technol. 1(1), 015003 (2016). doi:10.1088/2058-9565/1/1/015003
[23] Dulek, Y., Schaffner, C., Speelman, F.: Quantum homomorphic encryption for polynomial-sized circuits. In: Advances in Cryptology-CRYPTO 2016, pp. 3-32 (2016). doi:10.1007/978-3-662-53015-3_1 · Zbl 1406.94047
[24] Garg, S., Gentry, C., Halevi, S., Raykova, M., Sahai, A., Waters, B.: Candidate indistinguishability obfuscation and functional encryption for all circuits. In: 54th Annual Symposium on Foundations of Computer Science-FOCS 2013, pp.40-49 (2013). doi:10.1109/FOCS.2013.13 · Zbl 1348.94048
[25] Gay, R., Jain, A., Lin, H., Sahai, A.: Indistinguishability obfuscation from simple-to-state hardness assumptions (2021). https://eprint.iacr.org/2020/764.pdf · Zbl 1479.94177
[26] Gentry, C., Gorbunov, S., Halevi, S.: Graph-induced multilinear maps from lattices. In: 12th Theory of Cryptography Conference-TCC 2015, vol. 2, pp. 498-527 (2015). doi:10.1007/978-3-662-46497-7_20 · Zbl 1315.94076
[27] Giles, B., Selinger, P.: Remarks on Matsumoto and Amano’s normal form for single-qubit Clifford+\({T}\) operators (2019). https://arxiv.org/abs/1312.6584
[28] Goldwasser, S.; Rothblum, GN, On best-possible obfuscation, J. Cryptol., 27, 3, 480-505 (2014) · Zbl 1302.94048 · doi:10.1007/s00145-013-9151-z
[29] Gottesman, D.: The Heisenberg representation of quantum computers. In: 22nd International Colloquium on Group Theoretical Methods in Physics-GROUP 22, pp. 32-43 (1998). http://arxiv.org/abs/quant-ph/9807006 · Zbl 0977.81005
[30] Gottesman, D.; Chuang, IL, Demonstrating the viability of universal quantum computation using teleportation and single-qubit operations, Nature, 402, 390-393 (1999) · doi:10.1038/46503
[31] Guo, S., Malkin, T., Oliveira, I.C., Rosen, A.: The power of negations in cryptography. In: 12th Theory of Cryptography Conference-TCC 2015, vol. 1, pp. 36-65 (2015). doi:10.1007/978-3-662-46494-6_3 · Zbl 1354.94032
[32] Jain, A., Lin, H., Sahai, A.: Indistinguishability obfuscation from well-founded assumptions (2020). https://eprint.iacr.org/2020/1003
[33] Kaye, P., Laflamme, R., Mosca, R.: An Introduction to Quantum Computing. Oxford University Press, Oxford (2007) · Zbl 1297.68001
[34] Langlois, A., Stehlé, D., Steinfeld, R.: GGHLite: more efficient multilinear maps from ideal lattices. In: Advances in Cryptology-EUROCRYPT 2014, pp. 239-256 (2014). doi:10.1007/978-3-642-55220-5_14 · Zbl 1332.94071
[35] Low, R.A.: Learning and testing algorithms for the Clifford group. Phys. Rev. 80(5):052314 (2009). doi:10.1103/PhysRevA.80.052314
[36] Matsumoto, K., Amano, K.: Representation of quantum circuits with Clifford and \(\pi /8\) gates (2008). https://arxiv.org/abs/0806.3834
[37] Niemann, P., Wille, R., Drechsler, R.: Efficient synthesis of quantum circuits implementing Clifford group operations. In: 19th Asia and South Pacific Design Automation Conference-ASP-DAC 2014, pp. 483-488 (2014). doi:10.1109/ASPDAC.2014.6742938
[38] Sahai, A., Waters, B.: How to use indistinguishability obfuscation: deniable encryption, and more. In: 46th Annual ACM Symposium on Theory of Computing-STOC 2014, pp. 475-484 (2014). doi:10.1145/2591796.2591825 · Zbl 1315.94102
[39] Selinger, R.: Generators and relations for \(n\)-qubit Clifford operators (2013). https://arxiv.org/abs/1310.6813 · Zbl 1391.81066
[40] Sipser, M.: Introduction to the Theory of Computation. Cengage Learning, 3rd edn. Cengage, Boston (2012)
[41] Speelman. F.: Instantaneous non-local computation of low \(T\)-depth quantum circuits. In: 11th Conference on the Theory of Quantum Computation, Communication and Cryptography-TQC 2016, pp. 9:1-9:24 (2016). doi:10.4230/LIPIcs.TQC.2016.9 · Zbl 1370.81046
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.