Revisiting the security of quantum bit commitment schemes

Abstract

Bit commitment is one of the cornerstones of both classical and quantum cryptography. In the classical world, security analysis is straightforward because both hiding and binding each admit a single natural interpretation. In the quantum world, however, security notions can be defined in different ways that are not necessarily equivalent. Over three decades, several works have introduced numerous binding notions whose precise statements and mu- tual implications remain scattered across the literature. This thesis clarifies that ambiguity. We study quantum binding notions within the framework of canonical purified quantum bit commitment (QBC) schemes, a class that captures both the theoretical generality and the practical mechanisms of recent constructions. In the statistical setting, we examine six binding notions: strong-binding, honest-binding, sum-binding, collapse-binding, extractor- binding, and arbitrary-binding. We prove that all these definitions except strong-binding are equivalent for the class of canonical purified schemes. In the computational setting, we establish that honest-binding, sum-binding, and collapse-binding are equivalent for the same class of schemes. Moreover, we introduce a quantitative framework based on the work of Ref. [26] to quantify the tradeoff between hiding and binding properties, and we use it to provide a geometric proof of the impossibility theorem of Mayers [21] and Lo & Chau [20], for canonical purified schemes. We next revisit the quantum notion of hiding, which is far less ambiguous than binding. Finally, we survey some technical tools that can be used to construct secure QBC schemes. La mise en gage de bit (bit commitment) est est l’un des piliers fondamentaux de la cryptographie, qu’elle soit classique ou quantique. Dans le monde classique, l’analyse de sécurité est directe: les propriétés de camouflage (hiding) et de liaison (binding) n’admettent chacune qu’une interprétation naturelle. Dans le monde quantique, en revanche, les notions de sécurité peuvent être définies de façons différentes sans nécessairement être équivalentes. Depuis plus de trente ans, plusieurs travaux ont introduit une multitude de notions de liaison dont les formulations précises et les implications mutuelles demeurent éparpillées dans la littérature. Cette thèse clarifie cette ambiguïté. Nous étudions les notions quantiques de liaison dans la classe des schémas de mise en gage canoniques et purifiés, une classe qui reflète à la fois la généralité théorique et les mécanismes pratiques des constructions récentes. Dans le cadre statistique, nous examinons six notions de liaison qui ont été proposés au fil des années : strong-binding, honest-binding, sum-binding, collapse-binding, extractor-binding et arbitrary-binding. Nous prouvons que toutes ces définitions, à l’exception de strong-binding, sont équivalentes pour la classe des schémas de mise en gage canoniques et purifiés. Dans le cadre calculatoire, nous démontrons que honest-binding, sum-binding et collapse-binding sont équivalentes pour la même classe des schémas. De plus, nous introduisons un formalisme quantitatif, en se basant sur le travail de Ref. [26], pour quantifier le compromis entre camouflage et liaison, que nous employons pour fournir une preuve géométrique du théorème d’impossibilité de Mayers [21] et de Lo & Chau [20] pour les schémas canoniques purifiés. Nous revisitons ensuite la notion quantique de camouflage qui est beaucoup moins ambiguë que celle de liaison. Enfin, nous passons en revue certains outils techniques permettant de construire des schémas sûrs.