Using Hamiltonian Totems as Passwords
David Naccache

This paper introduces a new method for someone to authenticate himself into a system. In some sense, this can be seen as the illegitimate child between biometric recognition and passwords. From the first, it borrows the pattern matching algorithms that handle data and from the second, their secrecy. It can also be interpreted as less privacy intrusive than biometrics while keeping most of their characteristics. We call it visual passwords. The underlying principle of visual passwords is quite simple: At the registration step, you choose something as your password and take a photography of it. In reference to the movie Inception, we call this image your totem. You freely choose something that you have under your hand. Your totems choice has to remain secret. The totem is then sent to the authentication service. When you want to authenticate yourself, you take another photography of your totem for a comparison image vs image with the reference.

There are two ways to ensure a good entropy in the totems choice. The first one is to choose among a great variety of different objects. This may cause some difficulties during the second step of verification. The second one is to have an object with a design with many possible configurations. In this paper, we chose to study an object of this type. A Hamiltonian cycle defines a circuit running through all vertexes of a graph. An Hamiltonian graph provides high entropy for our totem and efficient algorithms exist to generate Hamiltonian structures. At first we've thought of creating an Hamiltonian cube but the recognition algorithm doesn't detect inner layers when plunging inside the cube, so we decided to limit the Hamiltonian circuit to the cube's surface. The Hamiltonian cycle is spreading on the cube's four vertical faces and we place two plates on the upper and lower faces for the structure's rigidity. This causes a loss in extractible information available for recognition but we thus created a solid totem's structure. This results in a unique key-ring type structure that is extremely hard to copy.

In the talk we will also mention other uses of Hamiltonian circuits for security purposes.