Realizing Consistency-or-Die: Verifiable Consistency for Key Logs

Abstract

Public key cryptography has become an important backbone for end-to-end encrypted communication, commonly used in the majority of the most popular messaging applications, such as WhatsApp and Signal. For this purpose, these applications utilize a centralized key log, which users can query to receive the public key of their desired recipient. However, this can open the possibility of a split-view attack, in which two users receive different information on what keys are registered. To prevent these attacks, the key log must be consistent, meaning there needs to be a way to confirm that all legitimate users receive the same information. While there are already some methods that try to enforce consistency, they either rely on users trusting third parties, or are unscalable to billions of users. Consistency-or-Die is a novel solution which utilizes the large user base together with verifiable randomness to generate endorsements from an ever-changing fraction of users, which can then be used by participants to check consistency. While this approach is promising, it still has not been tested experimentally, and has some theoretical gaps which require additional work, such as the maximum permitted fraction of malicious users along with specifications of how the random seed generation occurs. This thesis presents a concrete design and implementation of the protocol, capable of being tested, and addresses some remaining theoretical challenges. It presents the necessary background required to understand Consistency-or-Die, before explaining the protocol itself, followed by the implementation specifications, design choices and expected execution. Then, it proves that the maximum number of malicious users CoD can efficiently handle is one third of the entire population, and discuss how realistic this scenario is. Furthermore, it analyzes the requirements of seed generation, multiple approaches to generate a random seed and their respective security considerations. Finally, a discussion on the obtained results and future areas of this protocol that could also be improved as well as possible future applications is presented.