Introduction

Cryptographic primitives are tools which facilitate the construction of complex cryptographic systems. They are described by mathematical specifications which outline the properties that a particular primitive must have. However, these mathematical notions are idealised and it is unknown whether they are actually physically implementable and usable by computers. We certainly hope that they are, for otherwise cryptography falls apart.

In practice, we have algorithms which strive to imitate said primitives, but we have no way of actually proving if a given algorithm satisfies the properties of some primitive. We believe based on empirical evidence that an algorithm implements some sort of a primitive until someone finds a way to give the lie to it, usually by breaking its security. This is a common theme throughout cryptography because this field deals very complex and niche definitions - they give us a goal to strive for, but they do not provide us with a means to know if we have achieved said goal.