# Applied Cryptography

Cryptography provides a fundamental set of techniques that underpin secure systems. It includes basic techniques to enable services such as confidentiality and integrity of data in secure communication systems, as well as much more advanced methods such as cryptographic schemes that enable searches over encrypted data. It draws broadly from theoretical computer science (algorithms, complexity theory), mathematics (number theory, probability) and engineering (both electronic- and software-engineering). Our research in Applied Cryptography brings all of these strands together to produce impactful research that improves the security of today’s and tomorrow’s cryptographic systems.

We analyse cryptographic protocols that are deployed at Internet scale, using techniques from provable security to provide assurance in such systems. Our work in this domain includes analysis of TLS, perhaps the most widely-used secure communications protocol today, as well as SSH, the sysadmin’s tool of choice for remote access to computer systems. This work involves the development of new, practice-driven security models and their immediate application to real-world systems. We also perform system-, protocol- and algorithm-level cryptanalysis to detect defects in such systems. Here, our work has led to significant changes in the way protocols such as WPA, SSH and TLS make use of cryptography today, with billions of users being better protected as a result.

We are involved in the on-going global effort to develop post-quantum cryptography — cryptography which resists attacks by quantum computers. Here, we are designing new cryptographic algorithms and protocols with a focus on combining efficiency, conservative design, and security proofs. In parallel, we have initiated a study of side-channel attacks on such algorithms, where an attacker learns additional information through the execution of the cryptographic algorithm or via memory leakage.

In another strand of work, we have been examining the security of data at rest. One focus has been on key rotation, which refers to the ability of customers to efficiently and conveniently change their encryption keys for data held in cloud systems. Another focus is on analysing and exploiting the leakage from encrypted database systems that support rich classes of queries on data. Our work here has shown that certain classes of leakage — such as access pattern leakage or even just data volume leakage — can be fatal to security. It illustrates the shortcomings of current approaches to security data at rest and motivates the development of new, theory-backed solutions with strong security guarantees.

Privacy-preserving technologies are another research focus of the group. They aim to reconcile privacy and usability when these may a priori seem antagonistic, e.g., proving that one is above a certain age to access a service without revealing any information beyond that. Such technologies for instance include group signatures and credential systems. Our goal in this line of work is to build practical schemes that can be analysed in models which capture strong security and privacy requirements.

Zero-knowledge proofs are fundamental in cryptography as they allow to prove statements without revealing any information beyond their validity. Their versatility makes them suitable for a wide range of applications which include CCA encryption, digital signatures, privacy-preserving protocols, secure computation and cryptocurrencies. We are thus interested in developing practical zero-knowledge proof systems under minimal assumptions. The group also studies, from a cryptanalytic viewpoint, the security of these proofs when deployed in larger real-world systems, wherein the running time of a larger protocol may for example induce an undesirable leak of information.

Randomness in cryptography is also a research focus of the group. The security of most cryptosystems relies on access to perfect randomness, especially when generating keys, but it is hardly ever guaranteed in practice. We thus study the impact of randomness failure on real-world schemes. A complementary research direction of the group is that of randomness certification, i.e., attesting that cryptographic keys were generated with high-entropy randomness.

We work closely with industry to remediate any security issues that we find, following responsible disclosure processes. Finally, we are also working in standards bodies (IETF and IRTF) to lead the development of new cryptographic standards for the Internet.

## Publications

S. Patranabis and D. Mukhopadhyay. Forward and Backward Private Conjunctive Searchable Symmetric Encryption. NDSS Symposium 2021.

N. Alamati, L. De Feo, H. Montgomery and S. Patranabis. Cryptographic Group Actions and Applications. Asiacrypt 2020.

J. Brendel, M. Fischlin, F. Günther, C. Janson and D. Stebila. Towards Post-Quantum Security for Signal’s X3DH Handshake. SAC 2020.

H. Shafagh, L. Burkhalter, S. Ratnasamy and A. Hithnawi. Droplet: Decentralized Authorization and Access Control for Encrypted Data Streams. USENIX Security Symposium 2020, pp. 2469-2486.

F. Tramèr, D. Boneh and K. G. Paterson. Remote Side-Channel Attacks on Anonymous Transactions. USENIX Security Symposium 2020, pp. 2739-2756.

B. Dowling, M. Fischlin, F. Günther and D. Stebila. A Cryptographic Analysis of the TLS 1.3 Handshake Protocol. Journal of Cryptology 2020.

M. Fischlin, F. Günther and P. Muth. Information-Theoretic Security of Cryptographic Channels. ICICS 2020.

V. Maram. On the Security of NTS-KEM in the Quantum Random Oracle Model. CBCrypto 2020, pp. 1-19.

M. Bellare and I. Stepanovs. Security under Message-Derived Keys: Signcryption in iMessage. Eurocrypt 2020, pp. 507-537.

B. Dowling, T. B. Hansen and K. G. Paterson. Many a Mickle Makes a Muckle: A Framework for Provably Quantum-Secure Hybrid Key Exchange. PQCrypto 2020, pp. 483-502.

J. Massimo and K. G. Paterson. A Performant, Misuse-Resistant API for Primality Testing. ACM CCS 2020.

M. Bellare, H. Davis and F. Günther. Separate Your Domains: NIST PQC KEMs, Oracle Cloning and Read-Only Indifferentiability. Eurocrypt 2020, pp. 3-32.

H. Boyapally, P. Mathew, S. Patranabis, U. Chatterjee, U. Agarwal, M. Maheshwari, S. Dey and D. Mukhopadhyay.

Safe is the new Smart: PUF-based Authentication for Load Modification-Resistant Smart Meters. IEEE Transactions on Dependable and Secure Computing 2020.

L. Burkhalter, A. Hithnawi, A. Viand, H. Shafagh and S. Ratnasamy. TimeCrypt: Encrypted Data Stream Processing at Scale with Cryptographic Access Control. USENIX Symposium on Networked Systems Design and Implementation 2020, pp. 835-850.

K. Cohn-Gordon, C. Cremers, B. Dowling, L. Garratt and D. Stebila. A Formal Security Analysis of the Signal Messaging Protocol. Journal of Cryptology 2020.

B. Dowling, P. Rösler and J. Schwenk. Flexible Authenticated and Confidential Channel Establishment (fACCE): Analyzing the Noise Protocol Framework. PKC 2020, pp. 341-373.

M. Fischlin and F. Günther. Modeling Memory Faults in Signature and Authenticated Encryption Schemes. CT-RSA 2020, pp. 56-84.

F. Günther. Modeling advanced security aspects of key exchange and secure channel protocols. it – Information Technology.

S. Saha, A. Bag, D. B. Roy, S. Patranabis and D. Mukhopadhyay. Fault Template Attacks on Block Ciphers Exploiting Fault Propagation. Eurocrypt 2020, pp. 612-643.

M.R. Albrecht, T.B. Hansen and K.G. Paterson. libInterMAC: Beyond Confidentiality and Integrity in Practice. IACR ToSC 2019(1), pp. 46-83.

S. Galbraith, J. Massimo and K.G. Paterson. Safety in Numbers: On the Need for Robust Diffie-Hellman Parameter Validation. PKC 2019, pp.379-407.

P. Grubbs, M.-S. Lacharité, B. Minaud and K.G. Paterson. Learning to Reconstruct: Statistical Learning Theory and Encrypted Database Attacks. 2019 IEEE Symposium on Security and Privacy, pp.1067-1083.

M.R. Albrecht, A. Deo and K.G. Paterson. Cold Boot Attacks on Ring and Module LWE Keys Under the NTT. IACR Transactions on Cryptographic Hardware and Embedded Systems (TCHES), 2018 (3), 173-213 (2018).

M.R. Albrecht, J. Massimo, K.G. Paterson and J. Somorovsky. Prime and Prejudice: Primality Testing Under Adversarial Conditions. In D. Lie, M. Mannan, M. Backes and X. Wang (eds.), ACM CCS, 281-298 (2018).

B. Dowling and K.G. Paterson. A Cryptographic Analysis of the WireGuard Protocol. B. Preneel, F. Vercauteren (eds.), ACNS 2018, Lecture Notes in Computer Science, Vol. 10892, pp. 3-21, Springer, 2018.

P. Grubbs, M.-S. Lacharité, B. Minaud and K.G. Paterson. Pump up the Volume: Practical Database Reconstruction from Volume Leakage on Range Queries. In D. Lie, M. Mannan, M. Backes and X. Wang (eds.), ACM CCS, 315-331, 2018.

P. Kotzias, A. Razaghpanah, J. Amann, K.G. Paterson, N. Vallina-Rodriguez and J. Caballero. Coming of Age: A Longitudinal Study of TLS Deployment. Proceedings of the Internet Measurement Conference 2018, IMC 2018, Boston, MA, USA, October 31 – November 02, 2018. ACM 2018, pp 415-428.

M.-S. Lacharité, B. Minaud and K.G. Paterson. Improved Reconstruction Attacks on Encrypted Data Using Range Query Leakage. 2018 IEEE Symposium on Security and Privacy, pp. 297 – 314, IEEE Computer Society, 2018.

M.-S. Lacharité and K.G. Paterson. Frequency-smoothing encryption: preventing snapshot attacks on deterministically-encrypted data. IACR Transactions on Symmetric Cryptology, 2018(1), 277-313.

E. Ronen, K.G. Paterson and A. Shamir. Pseudo Constant Time Implementations of TLS Are Only Pseudo Secure. In D. Lie, M. Mannan, M. Backes and X. Wang (eds.), ACM CCS, 1397-1414 (2018).

M.R. Albrecht, E. Orsini, K.G. Paterson, G. Peer and N.P. Smart. Tightly Secure Ring-LWE Based Key Encapsulation with Short Ciphertexts. S.N. Foley, D. Gollmann, E. Snekkenes (eds.), ESORICS 2017, Lecture Notes in Computer Science, Vol. 10492, pp. 29-46, Springer, 2017.

A. Everspaugh, T. Ristenpart, K.G. Paterson, and S. Scott. Key Rotation for Authenticated Encryption. In J. Katz and H. Shacham (eds.), CRYPTO 2017 (III), Lecture Notes in Computer Science, Vol. 10403, pp. 98-129, Springer, 2017.

M.R. Albrecht, J.P. Degabriele, T.B. Hansen and K.G. Paterson. A surfeit of SSH cipher suites. In E.R. Weippl, S. Katzenbeisser, C. Kruegel, A.C. Myers and S. Halevi (eds.), Proceedings of the 2016 ACM Conference on Computer and Communications Security (CCS 2016), pp. 1480-1491, ACM Press, 2016.