Top

Published in:

2025 | OriginalPaper | Chapter

Unbounded Leakage-Resilience and Intrusion-Detection in a Quantum World

Authors : Alper Çakan, Vipul Goyal, Chen-Da Liu-Zhang, João Ribeiro

Published in: Theory of Cryptography

Publisher: Springer Nature Switzerland

Activate our intelligent search to find suitable subject content or patents.

search-config

AI-assisted search

Off

Abstract

Can an adversary hack into our system and steal sensitive data such as cryptographic keys? This question is as old as the Internet and significant effort has been spent on designing mechanisms to prevent and detect hacking attacks. Once quantum computers arrive, will the situation remain the same or can we hope to live in a better world?

We first consider ubiquitous side-channel attacks, which aim to leak side information on secret system components, studied in the leakage-resilient cryptography literature. Classical leakage-resilient cryptography must necessarily impose restrictions on the type of leakage one aims to protect against, such as the popular bounded leakage model. Although such leakage bounds are necessary, many real-world side-channel attacks cannot be captured by bounded leakage. In this work, we design cryptographic schemes that provide guarantees against arbitrary side-channel attacks:

Using techniques from unclonable quantum cryptography, we design several basic leakage-resilient primitives, such as public- and private-key encryption, pseudorandom functions, digital signatures and quantum money schemes which remain secure under unbounded adaptive classical leakage over unbounded number of rounds.
What if the adversary simply breaks into our system to steal our secret keys, rather than mounting only a side-channel attack? What if the adversary can even tamper with the data arbitrarily, for example to cover its tracks? We initiate the study of intrusion-detection in the quantum setting, where one would like to detect if security has been compromised even in the face of such attacks. We design cryptographic schemes supporting intrusion-detection for a host of primitives such as public- and private-key encryption, digital signature, functional encryption, program obfuscation and software protection. Our schemes are based on techniques from cryptography with secure key leasing and certified deletion.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 102.000 Bücher
über 537 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 390 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Maschinenbau + Werkstoffe

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 340 Zeitschriften

aus folgenden Fachgebieten:

Bauwesen + Immobilien
Business IT + Informatik
Finance + Banking
Management + Führung
Marketing + Vertrieb
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

previous chapter Robust Combiners and Universal Constructions for Quantum Cryptography

next chapter Bit-Security Preserving Hardness Amplification

A copy of this public verification key could be stored offline or at multiple locations. Note that the notion of intrusion-detection is meaningless in the absence of such a public verification key, since in that case the adversary can simply swap our whole system, including the verification key, with a fresh instance of the scheme.

Note that this notion is impossible with classical signatures since the adversary can simply leak a classical signature.

Such obfuscation for compute-and-compare can be constructed from LWE [28].

As discussed, this notion is not possible with classical signatures.

Similarly to coset states, subspace states satisfy a property called direct product hardness [11]: no efficient adversary, even given oracle access to the membership checking program for A, can output \(v \in A, w \in A^\perp \) given a single copy of \(|A\rangle \).

We give a concrete construction based on equivocal CRHFs. Using similar ideas, any quantum lightning scheme based on classical oracles suffices.

Note that inputs x to \(\mathcal {O}_1\) are required to start with 0, and inputs x to \(\mathcal {O}_2\) are required to start with 1. Thus, if we had the same y and valid \(x_1,x_2\) for both oracles, we would have \(H(x_1) = H(x_2)\) and \((x_1)_1 = 0, (x_2)_1 = 1\) (thus \(x_1 \ne x_2\)).

This scheme unfortunanely lacks public verifiability, which is crucial for intrusion-detection since the adversary gets the complete state of the honest party, including the verification key.

We assume that the adversary outputs the classical description of an appropriate quantum circuit in a canonical representation.

In the computational setting, this will implicitly be any (not a-priori bounded) polynomial.

We also call this non-adaptive unbounded classical leakage adversary, since the leakage circuit is not specified by \(\mathcal {A}\) after getting the public parameters. However, we note that this is still somewhat adaptive since the leakage circuit \(E_0\) does get the public parameters.

We bundle the leakage circuit description in the state \(\sigma \).

This is not needed for the construction but it is needed for the security proof.

Note that banknote queries being before the leakage phase is without loss of generality since there is no input for the banknote queries.

See the full version [15] for the construction and security proof.

If we insist on efficiency of the oracles, we can instead use PRFs.

Aaronson, S.: The complexity of quantum states and transformations: from quantum money to black holes. arXiv preprint arXiv:1607.05256 (2016)

Aaronson, S., Christiano, P.: Quantum money from hidden subspaces. In: Proceedings of the Forty-Fourth Annual ACM Symposium on Theory of Computing, pp. 41–60 (2012)

Aaronson, S., Liu, J., Liu, Q., Zhandry, M., Zhang, R.: New approaches for quantum copy-protection. In: Malkin, T., Peikert, C. (eds.) CRYPTO 2021. LNCS, vol. 12825, pp. 526–555. Springer, Cham (2021). https://doi.org/10.1007/978-3-030-84242-0_19CrossRef

Agrawal, D., Archambeault, B., Rao, J.R., Rohatgi, P.: The EM side–channel(s). In: Kaliski, B.S., Koç, Ç.K., Paar, C. (eds.) Cryptographic Hardware and Embedded Systems - CHES 2002, pp. 29–45. Springer, Heidelberg (2003)CrossRef

Agrawal, S., Kitagawa, F., Nishimaki, R., Yamada, S., Yamakawa, T.: Public key encryption with secure key leasing. In: Hazay, C., Stam, M. (eds.) Advances in Cryptology - EUROCRYPT 2023, pp. 581–610. Springer, Cham (2023)CrossRef

Ahmad, A., Lee, S., Peinado, M.: Hardlog: Practical tamper-proof system auditing using a novel audit device. In: 2022 IEEE Symposium on Security and Privacy (SP), pp. 1791–1807 (2022). https://doi.org/10.1109/SP46214.2022.9833745

Amos, R., Georgiou, M., Kiayias, A., Zhandry, M.: One-shot signatures and applications to hybrid quantum/classical authentication. In: Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing, pp. 255–268 (2020)

Ananth, P., La Placa, R.L.: Secure software leasing. In: Canteaut, A., Standaert, F.-X. (eds.) EUROCRYPT 2021. LNCS, vol. 12697, pp. 501–530. Springer, Cham (2021). https://doi.org/10.1007/978-3-030-77886-6_17CrossRef

Bartusek, J., Goyal, V., Khurana, D., Malavolta, G., Raizes, J., Roberts, B.: Software with certified deletion. In: Joye, M., Leander, G. (eds.) Advances in Cryptology - EUROCRYPT 2024, pp. 85–111. Springer, Cham (2024)CrossRef

10.

Bartusek, J., Khurana, D.: Cryptography with certified deletion. In: Handschuh, H., Lysyanskaya, A. (eds.) Advances in Cryptology – CRYPTO 2023, pp. 192–223 (2023)

11.

Ben-David, S., Sattath, O.: Quantum tokens for digital signatures. Quantum 7, 901 (2023). https://doi.org/10.22331/q-2023-01-19-901

12.

Bennett, C.H., Bernstein, E., Brassard, G., Vazirani, U.: Strengths and weaknesses of quantum computing. SIAM J. Comput. 26(5), 1510–1523 (1997)MathSciNetCrossRef

13.

Brian, G., et al.: The mother of all leakages: how to simulate noisy leakages via bounded leakage (almost) for free. IEEE Trans. Inf. Theory 68(12), 8197–8227 (2022). https://doi.org/10.1109/TIT.2022.3193848. Preliminary version in Eurocrypt 2021

14.

Çakan, A., Goyal, V.: Unclonable cryptography with unbounded collusions (2023). https://eprint.iacr.org/2023/1841

15.

Cakan, A., Goyal, V., Liu-Zhang, C.D., Ribeiro, J.: Unbounded leakage-resilience and intrusion-detection in a quantum world. Cryptology ePrint Archive, Paper 2023/410 (2023). https://eprint.iacr.org/2023/410

16.

Coladangelo, A., Liu, J., Liu, Q., Zhandry, M.: Hidden cosets and applications to unclonable cryptography. In: Malkin, T., Peikert, C. (eds.) CRYPTO 2021. LNCS, vol. 12825, pp. 556–584. Springer, Cham (2021). https://doi.org/10.1007/978-3-030-84242-0_20CrossRef

17.

Kalai, Y.T., Reyzin, L.: A survey of leakage-resilient cryptography. In: Providing Sound Foundations for Cryptography: On the Work of Shafi Goldwasser and Silvio Micali, pp. 727–794. ACM (2019)

18.

Kitagawa, F., Nishimaki, R.: Functional encryption with secure key leasing. In: Agrawal, S., Lin, D. (eds.) Advances in Cryptology - ASIACRYPT 2022, pp. 569–598. Springer, Cham (2022)CrossRef

19.

Kocher, P.C.: Timing attacks on implementations of Diffie-Hellman, RSA, DSS, and other systems. In: Koblitz, N. (ed.) Advances in Cryptology — CRYPTO 1996, pp. 104–113 (1996)

20.

Liu, J., Liu, Q., Qian, L., Zhandry, M.: Collusion resistant copy-protection for watermarkable functionalities. In: Kiltz, E., Vaikuntanathan, V. (eds.) Theory of Cryptography, TCC 2022, pp. 294–323. Springer, Cham (2022). https://doi.org/10.1007/978-3-031-22318-1_11

21.

Pass, R., Shelat, A.: A course in cryptography (2010)

22.

Quisquater, J.J., Samyde, D.: ElectroMagnetic analysis (EMA): measures and counter-measures for smart cards. In: Attali, I., Jensen, T. (eds.) Smart Card Programming and Security, pp. 200–210. Springer, Heidelberg (2001)CrossRef

23.

Regev, O.: On lattices, learning with errors, random linear codes, and cryptography. J. ACM 56(6), 1–40 (2009)MathSciNetCrossRef

24.

Sahai, A., Waters, B.: How to use indistinguishability obfuscation: deniable encryption, and more. In: Proceedings of the Forty-Sixth Annual ACM Symposium on Theory of Computing (STOC 2014), pp. 475–484. Association for Computing Machinery, New York (2014). https://doi.org/10.1145/2591796.2591825

25.

Sinha, A., Jia, L., England, P., Lorch, J.R.: Continuous tamper-proof logging using TPM 2.0. In: Holz, T., Ioannidis, S. (eds.) Trust and Trustworthy Computing, pp. 19–36. Springer, Cham (2014)

26.

Snodgrass, R.T., Yao, S.S., Collberg, C.: Tamper detection in audit logs. In: Proceedings of the Thirtieth International Conference on Very Large Data Bases (VLDB 2004), vol. 30, pp. 504–515. VLDB Endowment (2004)

27.

Vidick, T., Zhang, T.: Classical proofs of quantum knowledge. In: Canteaut, A., Standaert, F.-X. (eds.) EUROCRYPT 2021. LNCS, vol. 12697, pp. 630–660. Springer, Cham (2021). https://doi.org/10.1007/978-3-030-77886-6_22CrossRef

28.

Wichs, D., Zirdelis, G.: Obfuscating compute-and-compare programs under LWE. In: 2017 IEEE 58th Annual Symposium on Foundations of Computer Science (FOCS), pp. 600–611 (2017). https://doi.org/10.1109/FOCS.2017.61

29.

Zhandry, M.: Quantum lightning never strikes the same state twice. In: Ishai, Y., Rijmen, V. (eds.) EUROCRYPT 2019. LNCS, vol. 11478, pp. 408–438. Springer, Cham (2019). https://doi.org/10.1007/978-3-030-17659-4_14CrossRef

30.

Zhandry, M.: Schrödinger’s pirate: how to trace a quantum decoder. In: Pass, R., Pietrzak, K. (eds.) Theory of Cryptography, pp. 61–91. Springer, Cham (2020)CrossRef

Title: Unbounded Leakage-Resilience and Intrusion-Detection in a Quantum World
Authors: Alper Çakan
Vipul Goyal
Chen-Da Liu-Zhang
João Ribeiro
Publisher: Springer Nature Switzerland
Book: Theory of Cryptography
Print ISBN: 978-3-031-78016-5

Electronic ISBN: 978-3-031-78017-2

Copyright Year: 2025
DOI: https://doi.org/10.1007/978-3-031-78017-2_6

Springer Professional

Abstract

Please log in to get access to your license.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Technik"

Springer Professional "Wirtschaft"