Assessment of Cryptographic Approaches for Quantum-Resistant Galileo OSNMA

REFERENCES

1. ↵
   1. Alvaro, A.,
   2. Pascual, L.,
   3. Abad, A.,
   4. Pinto, P.,
   5. Alvarez-Herrero, A.,
   6. Belenguer, T.,
   7. Miravet, C.,
   8. Campo, P.,
   9. Rodriguez, L. F.,
   10. Reyes, M.,
   11. Socas, J., &
   12. Bermejo, J.

   (2022). CARAMUEL: The future of space quantum key distribution in GEO. Proc. of the 2022 IEEE International Conference on Space Optical Systems and Applications (ICSOS), Kyoto City, Japan, 57–65. https://doi.org/10.1109/ICSOS53063.2022.9749720
2. ↵
   1. Aumasson, J.-P.,
   2. Bernstein, D. J., &
   3. Beullens, W.

   (2022). SPHINCS+: Submission to the NIST post-quantum project, v.3.1 (tech. rep.). https://sphincs.org/data/sphincs+-r3.1-specification.pdf
3. ↵
   1. Avanzi, R.,
   2. Bos, J.,
   3. Ducas, L.,
   4. Kiltz, E.,
   5. Lepoint, T.,
   6. Lyubashevsky, V.,
   7. Schanck, J. M.,
   8. Schwabe, P.,
   9. Seiler, G., &
   10. Stehlé, D.

   (2021). CRYSTALS-Kyber: Algorithm specifications and supporting documentation (tech. rep.). https://pq-crystals.org/kyber/data/kyber-specification-round3-20210131.pdf
4. ↵
   1. Bai, S.,
   2. Ducas, L.,
   3. Kiltz, E.,
   4. Lepoint, T.,
   5. Lyubashevsky, V.,
   6. Schwabe, P.,
   7. Seiler, G., &
   8. Stehlé, D.

   (2021). CRYSTALS-Dilithium: Algorithm specifications and supporting documentation (version 3.1) (tech. rep.). https://pq-crystals.org/dilithium/data/dilithium-specification-round3-20210208.pdf
5. ↵
   1. Baldini, G.,
   2. Sportiello, L.,
   3. Chiaramello, M., &
   4. Mahieu, V.

   (2018). Regulated applications for the road transportation infrastructure: The case study of the smart tachograph in the European Union. International Journal of Critical Infrastructure Protection, 21, 3–21. https://doi.org/10.1016/j.ijcip.2018.02.001
6. ↵
   1. Barker, E. B., &
   2. Dang, Q. H.

   (2015). Recommendation for key management part 3: Application-specific key management guidance (tech. rep. NIST SP 800-57Pt3r1). National Institute of Standards and Technology. https://doi.org/10.6028/NIST.SP.800-57Pt3r1
7. ↵
   1. Boeyen, S.,
   2. Santesson, S.,
   3. Polk, T.,
   4. Housley, R.,
   5. Farrell, S., &
   6. Cooper, D.

   (2008). Internet x.509 public key infrastructure certificate and certificate revocation list (CRL) profile, RFC 5280. Internet Engineering Task Force, 1–151. https://doi.org/10.17487/RFC5280
8. ↵
   1. Buchmann, J.,
   2. Dahmen, E., &
   3. Schneider, M.

   (2008). Merkle tree traversal revisited. In J. Buchmann & J. Ding (Eds.), Postquantum cryptography, 63–78. Springer. https://doi.org/10.1007/978-3-540-88403-3_5
9. ↵
   1. Castryck, W., &
   2. Decru, T.

   (2022). An efficient key recovery attack on SIDH. https://eprint.iacr.org/2022/975
10. ↵
    1. Celi, S.

    (2022). The post-quantum state: A taxonomy of challenges. http://blog.cloudflare.com/Post-Quantum-taxonomy/
11. ↵
    1. Chen, X.,
    2. Luo, R.,
    3. Liu, T.,
    4. Yuan, H., &
    5. Wu, H.

    (2023). Satellite navigation signal authentication in GNSS: A survey on technology evolution, status, and perspective for BDS. Remote Sensing, 15(5), 1462. https://doi.org/10.3390/rs15051462
12. ↵
    1. Dahmen-Lhuissier, S.

    (n.d.). Quantum-safe cryptography (QSC). Retrieved March 31, 2023, from https://www.etsi.org/technologies/quantum-safe-cryptography
13. ↵
    1. Eledlebi, K.,
    2. Yeun, C. Y.,
    3. Damiani, E., &
    4. Al-Hammadi, Y.

    (2022). Empirical studies of tesla protocol: Properties, implementations, and replacement of public cryptography using biometric authentication. IEEE Access, 10, 21941–21954. https://doi.org/10.1109/ACCESS.2022.3152895
14. ↵
    1. European Commission

    . (n.d.). EU space strategy for security and defence. https://defence-industry-space.ec.europa.eu/eu-space/eu-space-strategy-security-and-defence_en
15. ↵
    1. European Union

    . (2021a). European GNSS (Galileo) open service signal-in space interface control document issue 2.0. https://galileognss.eu/wp-content/uploads/2021/01/Galileo_OS_SIS_ICD_v2.0.pdf
16. ↵
    1. European Union

    . (2021b). Galileo - open service - service definition document. https://www.gsc-europa.eu/sites/default/files/sites/all/files/Galileo-OS-SDD_v1.2.pdf
17. ↵
    1. European Union

    . (2021c). Galileo open service navigation message authentication (OSNMA) receiver guidelines for the test phase: Issue 1.0, November 2021. Publications Office. https://doi.org/10.2878/230609
18. ↵
    1. European Union

    . (2022). Galileo open service navigation message authentication (OSNMA): Signal in space interface control document (SIS ICD): Issue 1.0, December 2022. Publications Office. https://doi.org/10.2878/594840
19. ↵
    1. EUSPA

    . (n.d.). Services—European GNSS service centre. European Union Agency for the Space Programme. https://www.gsc-europa.eu/galileo/services
20. ↵
    1. EUSPA

    . (2024). Services–Galileo. European Union Agency for the Space Programme. https://www.euspa.europa.eu/galileo/services
21. ↵
    1. Faz-Hernández, A., &
    2. Kwiatkowski, K.

    (2019). Introducing CIRCL: An advanced cryptographic library. Cloudflare. https://blog.cloudflare.com/introducing-circl
22. ↵
    1. Federal Office for Information Security

    . (2022). Quantum-safe cryptography–Fundamentals, current developments and recommendations. Federal Office for Information Security (BSI). 1–72. https://www.bsi.bund.de/SharedDocs/Downloads/EN/BSI/Publications/Brochure/quantum-safe-cryptography.html
23. ↵
    1. Fernandez-Hernandez, I.,
    2. Cancela, S.,
    3. Terris-Gallego, R.,
    4. Seco-Granados, G.,
    5. López-Salcedo, J. A.,
    6. O’Driscoll, C.,
    7. Winkel, J.,
    8. dalla Chiara, A.,
    9. Sarto, C.,
    10. Rijmen, V.,
    11. Blonski, D., &
    12. de Blas, J.

    (2022). Semi-assisted signal authentication based on Galileo ACAS [arXiv:2204.14026 [cs, eess]]. https://doi.org/10.48550/arXiv.2204.14026
24. ↵
    1. Fernandez-Hernandez, I.,
    2. Chamorro-Moreno, A.,
    3. Cancela-Diaz, S.,
    4. Calle-Calle, J. D.,
    5. Zoccarato, P.,
    6. Blonski, D.,
    7. Senni, T.,
    8. de Blas, F. J.,
    9. Hernández, C.,
    10. Simón, J., &
    11. Mozo, A.

    (2022). Galileo high accuracy service: Initial definition and performance. GPS Solutions, 26(3), 65. https://doi.org/10.1007/s10291-022-01247-x
25. ↵
    1. Fernandez-Hernandez, I.,
    2. Hirokawa, R.,
    3. Rijmen, V., &
    4. Aikawa, Y.

    (2023). PPP/PPP-RTK message authentication. NAVIGATION, 70 (2). https://doi.org/10.33012/navi.579
26. ↵
    1. Fernandez-Hernandez, I.,
    2. Winkel, J.,
    3. O’Driscoll, C.,
    4. Cancela, S.,
    5. Terris-Gallego, R.,
    6. López-Salcedo, J. A.,
    7. Seco-Granados, G.,
    8. Chiara, A. D.,
    9. Sarto, C.,
    10. Blonski, D., &
    11. Blas, J. D.

    (2023). Semi-assisted signal authentication for Galileo: Proof of concept and results. IEEE Transactions on Aerospace and Electronic Systems, 59(4), 4393–4404. https://doi.org/10.1109/TAES.2023.3243587
27. ↵
    1. Fernández-Hemández, I.,
    2. Ashur, T., &
    3. Rijmen, V.

    (2021). Analysis and recommendations for mac and key lengths in delayed disclosure GNSS authentication protocols. IEEE Transactions on Aerospace and Electronic Systems, 57(3), 1827–1839. https://doi.org/10.1109/TAES.2021.3053129
28. ↵
    1. Fouque, P.-A.,
    2. Hoffstein, J.,
    3. Kirchner, P.,
    4. Lyubashevsky, V.,
    5. Pornin, T.,
    6. Prest, T.,
    7. Ricosset, T.,
    8. Seiler, G.,
    9. Whyte, W., &
    10. Zhang, Z.

    (2020). Falcon: Fast-Fourier lattice-based compact signatures over NTRU (tech. rep.). https://falcon-sign.info/falcon.pdf
29. ↵
    1. Fries, S., &
    2. Tschofenig, H.

    (2006). Bootstrapping timed efficient stream loss-tolerant authentication (TESLA), RFC 4442. Internet Engineering Task Force, 1–18. https://doi.org/10.17487/RFC4442
30. ↵
    1. Gaglione, S.,
    2. Angrisano, A.,
    3. Freda, P.,
    4. Innac, A.,
    5. Vultaggio, M., &
    6. Crocetto, N.

    (2015). Benefit of GNSS multiconstellation in position and velocity domain. Proc. of the 2015 IEEE Metrology for Aerospace (MetroAeroSpace), Benevento, Italy, 9–14. https://doi.org/10.1109/MetroAeroSpace.2015.7180618
31. ↵
    1. Galbraith, S. D., &
    2. Vercauteren, F.

    (2018). Computational problems in supersingular elliptic curve isogenies. Quantum Information Processing, 17(10), 265. https://doi.org/10.1007/s11128-018-2023-6
32. ↵
    1. Gidney, C., &
    2. Ekerå, M.

    (2021). How to factor 2048 bit RSA integers in 8 hours using 20 million noisy qubits. Quantum, 5, 433. https://doi.org/10.22331/q-2021-04-15-433
33. ↵
    1. GlobalSign

    . (2022). GlobalSign root certificates. GMO Internet Group. https://support.globalsign.com/ca-certificates/root-certificates/globalsign-root-certificates
34. ↵
    1. Grover, L. K.

    (1996). A fast quantum mechanical algorithm for database search. Proc. of the 28th Annual ACM Symposium on the Theory of Computing (STOC ‘96), Philadelphia, PA, 212–219. https://doi.org/10.1145/237814.237866
35. ↵
    1. Hoffstein, J.,
    2. Pipher, J., &
    3. Silverman, J. H.

    (1998). NTRU: A ring-based public key cryptosystem. In J. P. Buhler (Ed.), Algorithmic number theory, 267–288. Springer. https://doi.org/10.1007/BFb0054868
36. ↵
    1. Hosoyamada, A., &
    2. Sasaki, Y.

    (2018). Cryptanalysis against symmetric-key schemes with online classical queries and offline quantum computations. In N. P. Smart (Ed.), Topics in cryptology – CT-RSA 2018, 198–218. Springer International Publishing. https://doi.org/10.1007/978-3-319-76953-0_11
37. ↵
    1. Huelsing, A.,
    2. Butin, D.,
    3. Gazdag, S.-L.,
    4. Rijneveld, J., &
    5. Mohaisen, A.

    (2018). XMSS: Extended Merkle signature scheme, RFC 8391. Internet Engineering Task Force. 1–74. https://doi.org/10.17487/RFC8391
38. ↵
    1. Hülsing, A.

    (2017). WOTS+ – Shorter signatures for hash-based signature schemes [Report Number: 965]. https://eprint.iacr.org/2017/965
39. ↵
    1. Joseph, D.,
    2. Misoczki, R.,
    3. Manzano, M.,
    4. Tricot, J.,
    5. Pinuaga, F. D.,
    6. Lacombe, O.,
    7. Leichenauer, S.,
    8. Hidary, J.,
    9. Venables, P., &
    10. Hansen, R.

    (2022). Transitioning organizations to post-quantum cryptography. Nature, 605, 237–243. https://doi.org/10.1038/s41586-022-04623-2
40. ↵
    1. Krawczyk, H.,
    2. Bellare, M., &
    3. Canetti, R.

    (1997). HMAC: Keyed-hashing for message authentication, RFC 2104. Internet Engineering Task Force, 1–11. https://doi.org/10.17487/RFC2104
41. ↵
    1. Kwiatkowski, K., &
    2. Valenta, L.

    (2019). TLS post-quantum experiment. Cloudflare. http://blog.cloudflare.com/the-tls-Post-Quantum-experiment/
42. ↵
    1. Langley, R. B.,
    2. Teunissen, P. J., &
    3. Montenbruck, O.

    (2017). Introduction to GNSS. In P. J. Teunissen & O. Montenbruck (Eds.), Springer handbook of global navigation satellite systems, 3–23. Springer International Publishing. https://doi.org/10.1007/978-3-319-42928-1_1
43. ↵
    1. Lopez, M. A.,
    2. Barbosa, G. N. N., &
    3. Mattos, D. M. F.

    (2022). New barriers on 6G networking: An exploratory study on the security, privacy and opportunities for aerial networks. Proc. of the 2022 1st International Conference on 6G Networking (6GNet), Paris, France, 1–6. https://doi.org/10.1109/6GNet54646.2022.9830402
44. ↵
    1. Lou, X.,
    2. Zhang, T.,
    3. Jiang, J.,
    4. Zhang, Y.

    (2021). A survey of microarchitectural side-channel vulnerabilities, attacks, and defenses in cryptography. ACM Computing Surveys, 54(6), 1–37. https://dl.acm.org/doi/abs/10.1145/3456629
45. ↵
    1. Lyubashevsky, V.

    (2009). Fiat-Shamir with aborts: Applications to lattice and factoring-based signatures. In M. Matsui (Ed.), Advances in cryptology – ASIACRYPT 2009, 598–616. Springer. https://doi.org/10.1007/978-3-642-10366-7_35
46. ↵
    1. Lyubashevsky, V.,
    2. Peikert, C., &
    3. Regev, O.

    (2013). On ideal lattices and learning with errors over rings. Retrieved April 17, 2023, from https://eprint.iacr.org/2012/230.pdf
47. ↵
    1. McGrew, D.,
    2. Curcio, M., &
    3. Fluhrer, S.

    (2019). Leighton-Micali hash-based signatures, RFC 8554. Internet Research Task Force, 1–61. https://doi.org/10.17487/RFC8554
48. ↵
    1. Mosca, M.

    (2018). Cybersecurity in an era with quantum computers: Will we be ready? IEEE Security & Privacy, 16(5), 38–41. https://doi.org/10.1109/MSP.2018.3761723
49. ↵
    1. National Institute of Standards and Technology

    . (2016). Request for comments on post-quantum cryptography requirements and evaluation criteria. Federal Register, 81(148), 50686–50687. https://www.federalregister.gov/documents/2016/08/02/2016-18150/request-for-comments-on-Post-Quantumcryptography-requirements-and-evaluation-criteria
50. ↵
    1. National Institute of Standards and Technology

    . (2017a). Post-quantum cryptography standardization - post-quantum cryptography. Computer Security Division, Information Technology Laboratory. https://csrc.nist.gov/projects/post-quantum-cryptography/post-quantum-cryptography-standardization
51. ↵
    1. National Institute of Standards and Technology

    . (2017b). Round 4 submissions - post-quantum cryptography. Computer Security Division, Information Technology Laboratory. https://csrc.nist.gov/projects/Post-Quantum-cryptography/round-4-submissions
52. ↵
    1. National Institute of Standards and Technology

    . (2017c). Selected algorithms 2022 - post-quantum cryptography. Computer Security Division, Information Technology Laboratory. https://csrc.nist.gov/projects/Post-Quantum-cryptography/selected-algorithms-2022
53. ↵
    1. National Institute of Standards and Technology

    . (2018). Stateful hash-based signatures. Computer Security Division, Information Technology Laboratory. https://csrc.nist.gov/projects/stateful-hash-based-signatures
54. ↵
    1. National Institute of Standards and Technology

    . (2022). Announcing PQC candidates to be standardized, plus fourth round candidates. Computer Security Division, Information Technology Laboratory. https://csrc.nist.gov/News/2022/pqc-candidates-to-be-standardized-and-round-4
55. ↵
    1. Neish, A.,
    2. Walter, T., &
    3. Enge, P.

    (2018). Parameter selection for the TESLA keychain. Proc. of the 31st International Technical Meeting of the Satellite Division of the Institute of Navigation (ION GNSS+ 2018), Miami, FL, 2155–2171. https://doi.org/10.33012/2018.15852
56. ↵
    1. Nemec, M.,
    2. Sys, M.,
    3. Svenda, P.,
    4. Klinec, D., &
    5. Matyas, V.

    (2017). The return of coppersmith’s attack: Practical factorization of widely used RSA moduli. Proc. of the 2017 ACM SIGSAC Conference on Computer and Communications Security (CCS ’17), 1631–1648. https://doi.org/10.1145/3133956.3133969
57. ↵
    1. Nicola, M.,
    2. Motella, B., &
    3. Gamba, M. T.

    (2021). GPS Chimera: A software receiver implementation. Proc. of the 34th International Technical Meeting of the Satellite Division of the Institute of Navigation (ION GNSS+ 2021), St. Louis, MO, 4264–4273. https://doi.org/10.33012/2021.18127
58. ↵
    1. Ntanos, A.,
    2. Lyras, N. K.,
    3. Stathis, A.,
    4. Zavitsanos, D.,
    5. Giannoulis, G.,
    6. Panagopoulos, A. D., &
    7. Avramopoulos, H.

    (2023). Entanglement-based QKD over LEO satellite-to-ground time-varying atmospheric channel. Proc. of the Free-Space Laser Communications XXXV (SPIE 12413), San Francisco, CA, 476–488. https://doi.org/10.1117/12.2649702
59. ↵
    1. Open Quantum Safe

    . (n.d.). Open quantum safe: Software for the transition to quantum-resistant cryptography. https://openquantumsafe.org/
60. ↵
    1. Ott, D.,
    2. Peikert, C., & Other workshop participants

    . (2019). Identifying research challenges in post-quantum cryptography migration and cryptographic agility [arXiv:1909.07353 [cs]]. https://doi.org/10.48550/arXiv.1909.07353
61. ↵
    1. Parliament, E.

    (2011). Decision no 1104/2011/EU of the European Parliament and of the Council of 25 October 2011 on the rules for access to the public regulated service provided by the global navigation satellite system established under the Galileo programme [Legislative Body: EP, CONSIL]. https://eur-lex.europa.eu/eli/dec/2011/1104/oj
62. ↵
    1. Pazienza, A.,
    2. Lella, E.,
    3. Noviello, P., &
    4. Vitulano, F.

    (2022). Analysis of network-level key exchange protocols in the post-quantum era. Proc. of the 2022 IEEE 15th Workshop on Low Temperature Electronics (WOLTE), Matera, Italy, 1–4. https://doi.org/10.1109/WOLTE55422.2022.9882818
63. ↵
    1. Perrig, A.,
    2. Canetti, R.,
    3. Tygar, J., &
    4. Briscoe, B.

    (2005). Timed efficient stream loss-tolerant authentication (TESLA): Multicast source authentication transform introduction (Vol. RFC 4082) [Journal Abbreviation: Internet Requests for Comments Publication Title: Internet Requests for Comments]. https://doi.org/10.17487/RFC4082
64. ↵
    1. Petrenko, A. S.,
    2. Petrenko, S. S.,
    3. Makoveichuk, K. A.,
    4. Olifirov, A. V., &
    5. Krachunov, H.

    (2021). Security threat model based on analysis of foreign national quantum programs. Proc. of the 6th International Scientific and Practical Conference, Distance Learning Technologies (DLT 2021), Yalta, Crimea, 11–25. https://ceur-ws.org/Vol-3057/paper2.pdf
65. ↵
    1. Pornin, T.

    (2013). Deterministic usage of the digital signature algorithm (DSA) and elliptic curve digital signature algorithm (ECDSA), RFC 6979. Internet Engineering Task Force, 1–79. https://doi.org/10.17487/RFC6979
66. ↵
    1. Preston, R. H.

    (2022). Applying Grover’s algorithm to hash functions: A software perspective. IEEE Transactions on Quantum Engineering, 3, 1–10. https://doi.org/10.1109/TQE.2022.3233526
67. ↵
    1. Rivest, R. L., &
    2. Silverman, R. D.

    (2001). Are ‘strong’ primes needed for RSA? Cryptology ePrint Archive, Paper 2001/007. https://eprint.iacr.org/2001/007
68. ↵
    1. Shannon, C.

    (1956). The zero error capacity of a noisy channel. IRE Transactions on Information Theory, 2(3), 8–19. https://doi.org/10.1109/TIT.1956.1056798

    CrossRefWeb of Science
69. ↵
    1. Shor, P.

    (1994). Algorithms for quantum computation: Discrete logarithms and factoring. Proc. of the 35th Annual Symposium on Foundations of Computer Science, Santa Fe, NM, 124–134. https://doi.org/10.1109/SFCS.1994.365700
70. ↵
    1. Sikeridis, D.,
    2. Kampanakis, P., &
    3. Devetsikiotis, M.

    (2020). Assessing the overhead of post-quantum cryptography in TLS 1.3 and SSH. Proc. of the 16th International Conference on Emerging Networking EXperiments and Technologies (CoNEXT ’20), Barcelona, Spain, 149–156. https://doi.org/10.1145/3386367.3431305
71. ↵
    1. Sosnowski, M.,
    2. Wiedner, F.,
    3. Hauser, E.,
    4. Steger, L.,
    5. Schoinianakis, D.,
    6. Gallenmüller, S., &
    7. Carle, G.

    (2023). The performance of post-quantum TLS 1.3. Companion of the 19th International Conference on emerging Networking EXperiments and Technologies (CoNEXT ’23), Paris, France, 19–27. https://doi.org/10.1145/3624354.3630585
72. ↵
    1. Stebila, D.,
    2. Fluhrer, S., &
    3. Gueron, S.

    (2023). Hybrid key exchange in TLS 1.3 (Internet Draft draft-ietf-tls-hybrid-design-06) [Num Pages: 22]. Internet Engineering Task Force. https://datatracker.ietf.org/doc/draftietf-tls-hybrid-design
73. ↵
    1. Stebila, D., &
    2. Mosca, M.

    (n.d.). Post-quantum key exchange for the internet and the open quantum safe project. https://eprint.iacr.org/2016/1017.pdf
74. ↵
    1. Steinfeld, R., &
    2. Zheng, Y.

    (2004). On the security of RSA with primes sharing least-significant bits. Applicable Algebra in Engineering, Communication and Computing, 15(3), 179–200. https://doi.org/10.1007/s00200-004-0164-6
75. ↵
    1. Westerbaan, B.

    (2021). Sizing up post-quantum signatures. https://blog.cloudflare.com/sizing-up-post-quantum-signatures
76. ↵
    1. Zurabov, Y.,
    2. Ivanov, K., &
    3. Kuropyatnikov, A.

    (1998). COSPAS-SARSAT satellite system. Proc. of the 3rd International Conference on Satellite Communications, Moscow, Russia, 156–158. https://doi.org/10.1109/ICSC.1998.741402