Ce mémoire étudie le problème ancestral 1 de déterminer la puissance relative de l’intrication préalable en complexité de la communication comparée à la communication quantique. L’idée maîtresse du mémoire est d’opérer un rapprochement entre la complexité de la communication et la théorie des jeux non-locaux. Spécifiquement, nous contemplons une variété de manières de convertir des jeux non-locaux pour lesquels il est su que beaucoup d’intrication est requise en problèmes de complexité de la communication. Ce faisant, nous obtenons les problèmes de communications affichant les plus grands écarts connus à ce jour entre les deux modèles pour des problèmes fonctionnels. / Ce mémoire étudie le problème ancestral 1 de déterminer la puissance relative de l’intrication préalable en complexité de la communication comparée à la communication quantique. L’idée maîtresse du mémoire est d’opérer un rapprochement entre la complexité de la communication et la théorie des jeux non-locaux. Spécifiquement, nous contemplons une variété de manières de convertir des jeux non-locaux pour lesquels il est su que beaucoup d’intrication est requise en problèmes de complexité de la communication. Ce faisant, nous obtenons les problèmes de communications affichant les plus grands écarts connus à ce jour entre les deux modèles pour des problèmes fonctionnels.

Dans cette thèse,nous étudions comment exploiter des contraintes spatio-temporelles,notamment le principe d'impossibilité de transmission supraluminique,dans le but de créer des primitives cryptographiques sûres,par exemple la vérification de position ou la "mise en gage de bit''(bit commitment). D'après le principe d'impossibilité de transmission supraluminique,aucun vecteur physique d'information ne peut voyager plus vite que la vitesse de la lumière. Ce principe entraîne une contrainte sur le temps de communication entre deux points éloignés. Ce délai dans le transfert d'information peut être utilisé comme une contrainte temporelle interdisant la communication. En cryptographie multi-agents,il est connu que l'hypothèse de non-communication entre les agents permet de réaliser de manière sécurisée de nombreuses primitives comme la "mise en gage de bit'' et l'un des buts de cette thèse est de comprendre à quel point les contraintes spatio-temporelles peuvent être exploitèes pour simuler des scénarios de non-communication. Dans la première partie de cette thèse nous étudions comment utiliser une contrainte de non-communication pour essayer de vérifier la position d'une personne.Dans la dernière partie,nous nous penchons sur deux exemples de protocoles de ``mise en gage de bit'' relativistes afin d'en étudier la sécurité contre des adversaires classiques. Pour conclure cette thèse,nous mentionnons quelques problèmes ouverts intéréssants. Ces problèmes ouverts peuvent être très utiles pour comprendre le rôle de contraintes spatio-temporelles,par exemple de l'impossibilité de transmission supraluminique,dans la conception de primitives cryptographiques parfaitement sûres. / In this thesis we have studied how to exploit relativistic constraints such as the non-superluminal signalling principle to design secure cryptographic primitives like position-verification and bit commitment. According to non-superluminal signalling principle, no physical carrier of information can travel faster than the speed of light. This put a constraint on the communication time between two distant stations. One can consider this delay in information transfer as a temporal non-communication constraint. Cryptographic primitives like bit-commitment, oblivious transfer can be implemented with perfect secrecy under such non-communication assumption between the agents. The first part of this thesis has studied how non-signalling constraints can be used for secure position verification. Here, we have discussed about a strategy which can attack any position verification scheme. In the next part of this thesis we have discussed about the nonlocal games, relevant for studying relativistic bit commitment protocols. We have established an upper bound on the classical value of such family of games. The last part of this thesis discusses about two relativistic bit commitment protocols and their security against classical adversaries. We conclude this thesis by giving a brief summary of the content of each chapter and mentioning interesting open problems. These open problems can be very useful for better understanding of the role of spacetime constraints such as non-superluminal signalling in designing perfectly secure cryptographic primitives.