Abstract
Continuous Key Agreement (CKA) is a two-party procedure used by Double Ratchet protocols (e. g., Signal). This is a continuous and synchronous protocol that generates a fresh key for every sent/received message. It guarantees forward secrecy and post-compromise security. Alwen et al. have recently proposed a new KEM-based CKA construction where every message contains a ciphertext and a fresh public key. This can be made quantum-safe by deploying a quantum-safe KEM. They mention that the bandwidth can be reduced when using an ElGamal KEM (which is not quantum-safe). In this paper, we generalized their approach by defining a new primitive, namely Merged KEM (MKEM). This primitive merges the key generation and the encapsulation steps of a KEM. This is not possible for every KEM and we discuss cases where a KEM can be converted to an MKEM. One example is the quantum-safe proposal BIKE1, where the BIKE-MKEM saves \(50\%\) of the communication bandwidth, compared to the original construction. In addition, we offer the notion and two constructions for hybrid CKA.
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
Notes
- 1.
We use the terminology quantum-safe to cryptographic algorithms that rely on problems that are believed to be hard even in the presence of quantum computers. For example, cryptographic algorithms that rely on factorization (e. g., RSA) are not considered quantum-safe due to Shor’s algorithm [18]. On the other hand for some parameters cryptographic algorithms that rely on the Shortest Vector Problem over lattices are commonly considered quantum-safe.
- 2.
CKA uses ephemeral keys for both KEM and MKEM. This protects the scheme from attacks that may exploit decapsulation failures, such as [12] in the context of QC-MDPC codes. We note that CKA is aborted (and subsequently re-initialized) upon encountering a decapsulation failure.
References
Messenger secret conversations: Technical whitepaper (2013). https://fbnewsroomus.files.wordpress.com/2016/07/secret_conversations_whitepaper-1.pdf
Nist:post-quantum cryptography - call for proposals, September 2017. https://csrc.nist.gov/Projects/Post-Quantum-Cryptography
Whatsapp encryption overview: Technical white paper, December 2017. https://www.whatsapp.com/security/WhatsApp-Security-Whitepaper.pdf
Alwen, J., Coretti, S., Dodis, Y.: The double ratchet: security notions, proofs, and modularization for the signal protocol. Cryptology ePrint Archive, Report 2018/1037 (2018). https://eprint.iacr.org/2018/1037
Aragon, N., et al.: BIKE: bit flipping key encapsulation (2017)
Bellare, M., Singh, A.C., Jaeger, J., Nyayapati, M., Stepanovs, I.: Ratcheted encryption and key exchange: the security of messaging. In: Katz, J., Shacham, H. (eds.) CRYPTO 2017. LNCS, vol. 10403, pp. 619–650. Springer, Cham (2017). https://doi.org/10.1007/978-3-319-63697-9_21
Bernstein, D.J., et al.: Classic McEliece: conservative code-based cryptography (2017)
Bindel, N., Brendel, J., Fischlin, M., Goncalves, B., Stebila, D.: Hybrid key encapsulation mechanisms and authenticated key exchange. Cryptology ePrint Archive, Report 2018/903, September 2018. http://eprint.iacr.org/
Bos, J., et al.: CRYSTALS - Kyber: a CCA-secure module-lattice-based KEM. Cryptology ePrint Archive, Report 2017/634 (2017). https://eprint.iacr.org/2017/634
Cohn-Gordon, K., Cremers, C., Dowling, B., Garratt, L., Stebila, D.: A formal security analysis of the signal messaging protocol. In: 2017 IEEE European Symposium on Security and Privacy (EuroS P), pp. 451–466, April 2017. https://doi.org/10.1109/EuroSP.2017.27
Durak, F.B., Vaudenay, S.: Bidirectional asynchronous ratcheted key agreement without key-update primitives. Cryptology ePrint Archive, Report 2018/889 (2018). https://eprint.iacr.org/2018/889
Guo, Q., Johansson, T., Stankovski, P.: A key recovery attack on MDPC with CCA security using decoding errors. In: Cheon, J.H., Takagi, T. (eds.) ASIACRYPT 2016. LNCS, vol. 10031, pp. 789–815. Springer, Heidelberg (2016). https://doi.org/10.1007/978-3-662-53887-6_29
Jaeger, J., Stepanovs, I.: Optimal channel security against fine-grained state compromise: the safety of messaging. In: Shacham, H., Boldyreva, A. (eds.) CRYPTO 2018. LNCS, vol. 10991, pp. 33–62. Springer, Cham (2018). https://doi.org/10.1007/978-3-319-96884-1_2
Lund, J.: Signal partners with microsoft to bring end-to-end encryption to skype, October 2018. https://signal.org/blog/skype-partnership
Marlinspike, M.: Open whisper systems partners with Google on end-to-end encryption for allo (2013). https://signal.org/blog/allo/
Perrin, T., Marlinspike, M.: The double ratchet algorithm. GitHub wiki (2016)
Poettering, B., Rösler, P.: Asynchronous ratcheted key exchange. Cryptology ePrint Archive, Report 2018/296 (2018). https://eprint.iacr.org/2018/296
Shor, P.W.: Algorithms for quantum computation: discrete logarithms and factoring. In: Proceedings 35th Annual Symposium on Foundations of Computer Science, pp. 124–134, November 1994. https://doi.org/10.1109/SFCS.1994.365700
Acknowledgments
This research was supported by: The Israel Science Foundation (grant No. 1018/16); The BIU Center for Research in Applied Cryptography and Cyber Security, in conjunction with the Israel National Cyber Bureau in the Prime Minister’s Office; the Center for Cyber Law & Policy at the University of Haifa in conjunction with the Israel National Cyber Directorate in the Prime Minister’s Office.
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
Drucker, N., Gueron, S. (2019). Continuous Key Agreement with Reduced Bandwidth. In: Dolev, S., Hendler, D., Lodha, S., Yung, M. (eds) Cyber Security Cryptography and Machine Learning. CSCML 2019. Lecture Notes in Computer Science(), vol 11527. Springer, Cham. https://doi.org/10.1007/978-3-030-20951-3_3
Download citation
DOI: https://doi.org/10.1007/978-3-030-20951-3_3
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-030-20950-6
Online ISBN: 978-3-030-20951-3
eBook Packages: Computer ScienceComputer Science (R0)