Top

Published in:

2025 | OriginalPaper | Chapter

Split-State Non-malleable Codes and Secret Sharing Schemes for Quantum Messages

Authors : Naresh Goud Boddu, Vipul Goyal, Rahul Jain, 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

Non-malleable codes are fundamental objects at the intersection of cryptography and coding theory. These codes provide security guarantees even in settings where error correction and detection are impossible, and have found applications to several other cryptographic tasks. One of the strongest and most well-studied adversarial tampering models is 2-split-state tampering. Here, a codeword is split into two parts which are stored in physically distant servers, and the adversary can then independently tamper with each part using arbitrary functions. This model can be naturally extended to the secret sharing setting with several parties by having the adversary independently tamper with each share. Previous works on non-malleable coding and secret sharing in the split-state tampering model only considered the encoding of classical messages. Furthermore, until recent work by Aggarwal, Boddu, and Jain (IEEE Trans. Inf. Theory 2024 & arXiv 2022), adversaries with quantum capabilities and shared entanglement had not been considered, and it is a priori not clear whether previous schemes remain secure in this model.

In this work, we introduce the notions of split-state non-malleable codes and secret sharing schemes for quantum messages secure against quantum adversaries with shared entanglement. Then, we present explicit constructions of such schemes that achieve low-error non-malleability. More precisely, for some constant \(c>0\), we construct efficiently encodable and decodable split-state non-malleable codes and secret sharing schemes for quantum messages preserving entanglement with external systems and achieving security against quantum adversaries having shared entanglement with codeword length n, any message length at most \(n^c\), and error \(\varepsilon =2^{-{n^{c}}}\). In the easier setting of average-case non-malleability, we achieve efficient non-malleable coding with rate close to 1/11.

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 Real-Valued Somewhat-Pseudorandom Unitaries

next chapter Cryptography in the Common Haar State Model: Feasibility Results and Separations

A set \(\varGamma \subseteq 2^{[p]}\) is monotone if \(A\in \varGamma \) and \(A\subseteq B\) imply that \(B\in \varGamma \).

Meaning that the codeword is divided into three parts and the adversary tampers each part independently. We note that constructing NMCs in the 3-split-state model is considerably easier than in the 2-split-state model.

Tampering maps are assumed to be unitary without any loss of generality. This is because, in the presence of unbounded arbitrary shared entanglement, tampering with unitary maps is equivalent to tampering with CPTP maps. More precisely, consider a tampering adversary that uses two CPTP maps \(\varPhi _1\) and \(\varPhi _2\) acting on registers \(E_1 W_1\) and \(E_2 W_2\), respectively. Then, the action of this adversary is equivalent to another adversary who tampers using Stinespring isometry extensions U and V of \(\varPhi _1\) and \(\varPhi _2\), respectively, which act on \(E_1 W_1 A_1\) and \(E_2 W_2 A_2\), respectively, where \(A_1\) and \(A_2\) are unentangled ancilla registers set to \(|{0}\rangle \) without loss of generality and can be seen as part of the shared entanglement.

By this, we mean that \(p_{\mathcal {A}}\) can be computed and the state \(\gamma ^{\mathcal {A}}_{M}\) can be prepared without the knowledge of the input message \(\sigma _{M\hat{M}}\).

Clifford-based quantum authentication schemes apply a random (secret) Clifford operator to the message plus several additional “trap registers” initialized to \(|{0}\rangle \). Verifying whether tampering of the authenticated state occurred consists of checking whether the trap registers all return to the \(|{0}\rangle \) state after applying the inverse Clifford operator. If this does not hold, then the verification procedure outputs the special symbol \(\perp \), which we call the “trap flag”.

For the experienced reader, Batra, Boddu, and Jain [16] construct an explicit quantum-secure 2-source non-malleable extractor \(\textrm{nmExt}\) with a large output length. We can then sample classical bitstrings X and Y uniformly at random with appropriate lengths and set the classical key R to be \(R=\textrm{nmExt}(X,Y)\); this is the quantum-secure classical NMRE that we use in our optimized coding scheme.

“qpa-state” stands for quantum purified adversary state.

Aggarwal, D., Agrawal, S., Gupta, D., Maji, H.K., Pandey, O., Prabhakaran, M.: Optimal computational split-state non-malleable codes. In: Kushilevitz, E., Malkin, T. (eds.) Theory of Cryptography, pp. 393–417. Springer, Heidelberg (2016)CrossRef

Aggarwal, D., Boddu, N.G., Jain, R.: Quantum secure non-malleable codes in the split-state model. IEEE Trans. Inf. Theory 70(1), 349–371 (2024). https://doi.org/10.1109/TIT.2023.3328839MathSciNetCrossRef

Aggarwal, D., et al.: Stronger leakage-resilient and non-malleable secret sharing schemes for general access structures. In: Boldyreva, A., Micciancio, D. (eds.) CRYPTO 2019. LNCS, vol. 11693, pp. 510–539. Springer, Cham (2019). https://doi.org/10.1007/978-3-030-26951-7_18

Aggarwal, D., Dodis, Y., Lovett, S.: Non-malleable codes from additive combinatorics. SIAM J. Comput. 47(2), 524–546 (2018). https://doi.org/10.1137/140985251. Preliminary version in STOC 2014

Aggarwal, D., Dziembowski, S., Kazana, T., Obremski, M.: Leakage-resilient non-malleable codes. In: Dodis, Y., Nielsen, J.B. (eds.) Theory of Cryptography, pp. 398–426. Springer, Heidelberg (2015)CrossRef

Aggarwal, D., Kanukurthi, B., Obbattu, S.L.B., Obremski, M., Sekar, S.: Rate one-third non-malleable codes. In: Proceedings of the 54th Annual ACM SIGACT Symposium on Theory of Computing (STOC 2022), pp. 1364–1377. Association for Computing Machinery, New York (2022). https://doi.org/10.1145/3519935.3519972

Aggarwal, D., Obremski, M.: A constant rate non-malleable code in the split-state model. In: 2020 IEEE 61st Annual Symposium on Foundations of Computer Science (FOCS), pp. 1285–1294. IEEE Computer Society, Los Alamitos (2020). https://doi.org/10.1109/FOCS46700.2020.00122

Alagic, G., Majenz, C.: Quantum non-malleability and authentication. In: Katz, J., Shacham, H. (eds.) CRYPTO 2017. LNCS, vol. 10402, pp. 310–341. Springer, Cham (2017). https://doi.org/10.1007/978-3-319-63715-0_11CrossRef

Ambainis, A., Bouda, J., Winter, A.: Nonmalleable encryption of quantum information. J. Math. Phys. 50(4), 042106 (2009). https://doi.org/10.1063/1.3094756MathSciNetCrossRef

10.

Badrinarayanan, S., Srinivasan, A.: Revisiting non-malleable secret sharing. In: Ishai, Y., Rijmen, V. (eds.) EUROCRYPT 2019. LNCS, vol. 11476, pp. 593–622. Springer, Cham (2019). https://doi.org/10.1007/978-3-030-17653-2_20CrossRef

11.

Ball, M., Chattopadhyay, E., Liao, J., Malkin, T., Tan, L.: Non-malleability against polynomial tampering. In: Micciancio, D., Ristenpart, T. (eds.) Advances in Cryptology - CRYPTO 2020, pp. 97–126. Springer (2020).https://doi.org/10.1007/978-3-030-56877-1_4

12.

Ball, M., Dachman-Soled, D., Kulkarni, M., Malkin, T.: Non-malleable codes for bounded depth, bounded fan-in circuits. In: Fischlin, M., Coron, J.-S. (eds.) EUROCRYPT 2016. LNCS, vol. 9666, pp. 881–908. Springer, Heidelberg (2016). https://doi.org/10.1007/978-3-662-49896-5_31CrossRef

13.

Ball, M., Dachman-Soled, D., Kulkarni, M., Malkin, T.: Non-malleable codes from average-case hardness: \(\sf AC^0\), decision trees, and streaming space-bounded tampering. In: Nielsen, J.B., Rijmen, V. (eds.) Advances in Cryptology - EUROCRYPT 2018, pp. 618–650. Springer (2018).https://doi.org/10.1007/978-3-319-78372-7_20

14.

Ball, M., Guo, S., Wichs, D.: Non-malleable codes for decision trees. In: Boldyreva, A., Micciancio, D. (eds.) CRYPTO 2019. LNCS, vol. 11692, pp. 413–434. Springer, Cham (2019). https://doi.org/10.1007/978-3-030-26948-7_15CrossRef

15.

Barnum, H., Crepeau, C., Gottesman, D., Smith, A., Tapp, A.: Authentication of quantum messages. In: The 43rd Annual IEEE Symposium on Foundations of Computer Science (FOCS), 2002, pp. 449–458 (2002). https://doi.org/10.1109/SFCS.2002.1181969

16.

Batra, R., Boddu, N.G., Jain, R.: Quantum secure non-malleable randomness encoder and its applications. arXiv preprint arXiv:2308.07340 (2023). Contributed talk at QCRYPT 2023

17.

Bergamaschi, T.: Pauli manipulation detection codes and applications to quantum communication over adversarial channels. In: Joye, M., Leander, G. (eds.) Advances in Cryptology – EUROCRYPT 2024, pp. 404–433. Springer, Cham (2024). https://arxiv.org/abs/2304.06269

18.

Blakley, G.R.: Safeguarding cryptographic keys. In: 1979 International Workshop on Managing Requirements Knowledge (MARK), pp. 313–318 (1979). https://doi.org/10.1109/MARK.1979.8817296

19.

Boddu, N.G., Goyal, V., Jain, R., Ribeiro, J.: Split-state non-malleable codes and secret sharing schemes for quantum messages. arXiv preprint arXiv:2308.06466

20.

Boddu, N.G., Jain, R., Kapshikar, U.: Quantum secure non-malleable-extractors. arXiv preprint arXiv:2109.03097 (2021). Contributed talk at TQC 2022

21.

Brian, G., Faonio, A., Obremski, M., Simkin, M., Venturi, D.: Non-malleable secret sharing against bounded joint-tampering attacks in the plain model. In: Micciancio, D., Ristenpart, T. (eds.) CRYPTO 2020. LNCS, vol. 12172, pp. 127–155. Springer, Cham (2020). https://doi.org/10.1007/978-3-030-56877-1_5CrossRef

22.

Brian, G., Faonio, A., Ribeiro, J., Venturi, D.: Short non-malleable codes from related-key secure block ciphers, revisited. IACR Trans. Symmet. Cryptol. 2022(3), 1–19 (2022). https://doi.org/10.46586/tosc.v2022.i3.1-19

23.

Brian, G., Faonio, A., Venturi, D.: Continuously non-malleable secret sharing: joint tampering, plain model and capacity. In: Nissim, K., Waters, B. (eds.) Theory of Cryptography, pp. 333–364. Springer, Cham (2021)CrossRef

24.

Brian, G., Faust, S., Micheli, E., Venturi, D.: Continuously non-malleable codes against bounded-depth tampering. In: Agrawal, S., Lin, D. (eds.) Advances in Cryptology - ASIACRYPT 2022, pp. 384–413. Springer (2022). https://doi.org/10.1007/978-3-031-22972-5_14

25.

Broadbent, A., Wainewright, E.: Efficient simulation for quantum message authentication. In: Nascimento, A.C., Barreto, P. (eds.) Information Theoretic Security, pp. 72–91. Springer, Cham (2016)CrossRef

26.

Çakan, A., Goyal, V., Liu-Zhang, C.D., Ribeiro, J.: Unbounded leakage-resilience and intrusion-detection in a quantum world (2024). https://eprint.iacr.org/2023/410, to appear at TCC 2024. Contributed talk at TQC 2024. https://eprint.iacr.org/2023/410

27.

Chandran, N., Kanukurthi, B., Obbattu, S.L.B., Sekar, S.: Short leakage resilient and non-malleable secret sharing schemes. In: Dodis, Y., Shrimpton, T. (eds.) Advances in Cryptology - CRYPTO 2022, pp. 178–207. Springer (2022). https://doi.org/10.1007/978-3-031-15802-5_7

28.

Chattopadhyay, E., Goyal, V., Li, X.: Nonmalleable extractors and codes, with their many tampered extensions. SIAM J. Comput. 49(5), 999–1040 (2020). https://doi.org/10.1137/18M1176622. Preliminary version in STOC 2016

29.

Cheraghchi, M., Guruswami, V.: Non-malleable coding against bit-wise and split-state tampering. In: Proceedings of Theory of Cryptography Conference (TCC), pp. 440–464 (2014). https://doi.org/10.1007/978-3-642-54242-8_19. Extended Version in Journal of Cryptology

30.

Cheraghchi, M., Guruswami, V.: Capacity of non-malleable codes. IEEE Trans. Inf. Theory 62(3), 1097–1118 (2016). https://doi.org/10.1109/TIT.2015.2511784MathSciNetCrossRef

31.

Clauser, J.F., Horne, M.A., Shimony, A., Holt, R.A.: Proposed experiment to test local hidden-variable theories. Phys. Rev. Lett. 23, 880–884 (1969). https://doi.org/10.1103/PhysRevLett.23.880

32.

Cleve, R., Gottesman, D., Lo, H.K.: How to share a quantum secret. Phys. Rev. Lett. 83, 648–651 (1999). https://doi.org/10.1103/PhysRevLett.83.648

33.

Cleve, R., Leung, D., Liu, L., Wang, C.: Near-linear constructions of exact unitary 2-designs. Quantum Info. Comput. 16(9–10), 721–756 (2016)

34.

Dankert, C., Cleve, R., Emerson, J., Livine, E.: Exact and approximate unitary 2-designs and their application to fidelity estimation. Phys. Rev. A 80, 012304 (2009). https://doi.org/10.1103/PhysRevA.80.012304

35.

Datta, N.: Min- and max- relative entropies and a new entanglement monotone. IEEE Trans. Inf. Theory 55, 2816–2826 (2009)MathSciNetCrossRef

36.

Dziembowski, S., Kazana, T., Obremski, M.: Non-malleable codes from two-source extractors. In: Canetti, R., Garay, J.A. (eds.) CRYPTO 2013. LNCS, vol. 8043, pp. 239–257. Springer, Heidelberg (2013). https://doi.org/10.1007/978-3-642-40084-1_14CrossRef

37.

Dziembowski, S., Pietrzak, K., Wichs, D.: Non-malleable codes. J. ACM 65(4), 1–32 (2018). https://doi.org/10.1145/3178432. Preliminary version in ICS 2010

38.

Faonio, A., Venturi, D.: Non-malleable secret sharing in the computational setting: adaptive tampering, noisy-leakage resilience, and improved rate. In: Boldyreva, A., Micciancio, D. (eds.) CRYPTO 2019. LNCS, vol. 11693, pp. 448–479. Springer, Cham (2019). https://doi.org/10.1007/978-3-030-26951-7_16CrossRef

39.

Faust, S., Hostáková, K., Mukherjee, P., Venturi, D.: Non-malleable codes for space-bounded tampering. In: Katz, J., Shacham, H. (eds.) Advances in Cryptology - CRYPTO 2017, pp. 95–126. Springer (2017). https://doi.org/10.1007/978-3-319-63715-0_4

40.

Faust, S., Mukherjee, P., Nielsen, J.B., Venturi, D.: Continuous non-malleable codes. In: Lindell, Y. (ed.) Theory of Cryptography - 11th Theory of Cryptography Conference, TCC 2014, pp. 465–488. Springer, Heidelberg (2014). https://doi.org/10.1007/978-3-642-54242-8_20

41.

Fehr, S., Karpman, P., Mennink, B.: Short non-malleable codes from related-key secure block ciphers. IACR Trans. Symmet. Cryptol. 2018(1), 336–352 (2018). https://doi.org/10.13154/tosc.v2018.i1.336-352

42.

Goyal, V., Kumar, A.: Non-malleable secret sharing. In: Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing (STOC 2018), pp. 685–698. Association for Computing Machinery, New York (2018). https://doi.org/10.1145/3188745.3188872

43.

Goyal, V., Kumar, A.: Non-malleable secret sharing for general access structures. In: Shacham, H., Boldyreva, A. (eds.) CRYPTO 2018. LNCS, vol. 10991, pp. 501–530. Springer, Cham (2018). https://doi.org/10.1007/978-3-319-96884-1_17CrossRef

44.

Goyal, V., Pandey, O., Richelson, S.: Textbook non-malleable commitments. In: Proceedings of the Forty-Eighth Annual ACM Symposium on Theory of Computing (STOC 2016), pp. 1128–1141. Association for Computing Machinery, New York (2016). https://doi.org/10.1145/2897518.2897657

45.

Goyal, V., Srinivasan, A., Zhu, C.: Multi-source non-malleable extractors and applications. In: Canteaut, A., Standaert, F.-X. (eds.) EUROCRYPT 2021. LNCS, vol. 12697, pp. 468–497. Springer, Cham (2021). https://doi.org/10.1007/978-3-030-77886-6_16CrossRef

46.

Jain, R., Radhakrishnan, J., Sen, P.: Privacy and interaction in quantum communication complexity and a theorem about the relative entropy of quantum states. In: The 43rd Annual IEEE Symposium on Foundations of Computer Science, 2002, pp. 429–438 (2002). https://doi.org/10.1109/SFCS.2002.1181967

47.

Kanukurthi, B., Obbattu, S.L.B., Sekar, S.: Non-malleable randomness encoders and their applications. In: Nielsen, J.B., Rijmen, V. (eds.) Advances in Cryptology - EUROCRYPT 2018, pp. 589–617. Springer, Cham (2018)CrossRef

48.

Kiayias, A., Liu, F.H., Tselekounis, Y.: Practical non-malleable codes from \(\ell \)-more extractable hash functions. In: Proceedings of the 2016 ACM SIGSAC Conference on Computer and Communications Security (CCS 2016), pp. 1317–1328. Association for Computing Machinery, New York (2016). https://doi.org/10.1145/2976749.2978352

49.

Li, X.: Three-source extractors for polylogarithmic min-entropy. In: 2015 IEEE 56th Annual Symposium on Foundations of Computer Science, pp. 863–882 (2015). https://doi.org/10.1109/FOCS.2015.58

50.

Li, X.: Improved non-malleable extractors, non-malleable codes and independent source extractors. In: Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing (STOC 2017), pp. 1144–1156. Association for Computing Machinery, New York (2017). https://doi.org/10.1145/3055399.3055486

51.

Li, X.: Non-malleable extractors and non-malleable codes: partially optimal constructions. In: Proceedings of the 34th Computational Complexity Conference (CCC 2019). Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik, Dagstuhl, DEU (2019). https://doi.org/10.4230/LIPIcs.CCC.2019.28

52.

Li, X.: Two source extractors for asymptotically optimal entropy, and (many) more. In: 2023 IEEE 64th Annual Symposium on Foundations of Computer Science (FOCS), pp. 1271–1281 (2023). https://doi.org/10.1109/FOCS57990.2023.00075

53.

Liu, F.-H., Lysyanskaya, A.: Tamper and leakage resilience in the split-state model. In: Safavi-Naini, R., Canetti, R. (eds.) CRYPTO 2012. LNCS, vol. 7417, pp. 517–532. Springer, Heidelberg (2012). https://doi.org/10.1007/978-3-642-32009-5_30CrossRef

54.

Nielsen, M.A., Chuang, I.L.: Quantum Computation and Quantum Information. Cambridge University Press, Cambridge (2000)

55.

Ozols, M.: Lecture 5: quantum information processing protocols, quantum computing: exercise sheet 2 (2016). https://www.cl.cam.ac.uk/teaching/1617/QuantComp/exercise2.pdf

56.

Shamir, A.: How to share a secret. Commun. ACM 22(11), 612–613 (1979). https://doi.org/10.1145/359168.359176

57.

Srinivasan, A., Vasudevan, P.N.: Leakage resilient secret sharing and applications. In: Boldyreva, A., Micciancio, D. (eds.) CRYPTO 2019. LNCS, vol. 11693, pp. 480–509. Springer, Cham (2019). https://doi.org/10.1007/978-3-030-26951-7_17CrossRef

58.

Watrous, J.: The Theory of Quantum Information. Cambridge University Press, Cambridge (2018)CrossRef

Title: Split-State Non-malleable Codes and Secret Sharing Schemes for Quantum Messages
Authors: Naresh Goud Boddu
Vipul Goyal
Rahul Jain
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_3

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"