A New Role of Graph Theory: The Design of Probably Secure Cryptoprotocols

Abstract

This article introduces new methodology for the design of two-party cryptographic protocols using Graph Theory tools. In this sense, several Oblivious Transfer and Bit Commitment algorithms are proposed as primitives in the design of more complex protocols. Special attention is paid to the strong identification problem through Zero Knowledge Proofs, and new solutions based on graphs are given.