What's a cryptographic primitive, really?

Question

The more I encounter the term "cryptographic primitive," the less I feel confident that I truly understand what it means. Is it just me, or is there no universal definition for the term? Or does the term have some contextual sensitivity that I'm missing?

Some questions that illustrate my confusion:

1. Does the term refer to algorithms for which we only have heuristic security arguments?
2. Does it refer to the building blocks invoked by a mode of operation or protocol, independently of the form of their security arguments?
3. Does it refer to popular security goals like message authentication code, pseudorandom function, collision resistant hash function, etc., that are commonly used as building blocks in modes and protocols?
4. In Merkle–Damgård hash functions like SHA-2, which is the primitive:
   • The hash function as a whole?
   • The compression function?
   • One but not the other, varying with the context in which we're talking about SHA-2? (E.g., analyzing the security of SHA-2 vs. analyzing the security of a protocol that uses it.)
5. Since there are security proofs for HMAC that appeal to properties of the compression function of a Merkle–Damgård hash, which is the "primitive" in this case, the hash function or the compression function?
6. In SHA-3, which of these are "primitives" or not?
   • SHA3-256
   • Keccak sponge functions
   • Keccak permutations

Answer 1

As others have pointed out in the comments, "cryptographic primitives" are generic building blocks. What exactly this means depends on your point of view and the level of abstraction.

The most basic primitives are those, where a function is considered secure, but either you can't break it down any further or there is no security argument for its individual parts. Examples:

• Modular exponentiation in prime fields can't be broken down any more, and we can use this with the inherent discrete log problem to crete public key cryptography.
• Symmetric encryption - we consider symmetric encryption like AES secure, with clearly defined security properties. But its individual parts, e.g. single rounds or single steps in rounds, don't have any meaningful security properties. Sure, they bring certain amounts of confusion and diffusion. However, the strength of the cipher is also a result of the entire construction - as e.g. attacks on AES with reduced rounds are known.

And then there are primitives, which are not specified any further. For example if you assume a public key encryption scheme and just need its generic algorithms (Enc, Dec), then that encryption scheme is your building block. It isn't the underlying trapdoor one-way function, because you don't care which one is actually used.

To answer your questions:

1. No, actually quite differently. Primitives are defined by their security properties. Some have heuristical security properties, namely withstood cryptanalysis for years (e.g. cryptographic hash functions and symmetric encryption). Others have provable security properties - with or without assumptions. Examples with assumptions are public key cryptography, an example without assumption is Shamir's secret sharing - its security is unconditional.
2. Well, the primitive is defined by its security property. I am not sure what you mean with "form of security arguments". But everything with a provable security argument (and some heuristic ones for only the most basic things like symmetric encryption) can be a primitive for a higher level of abstraction.
3. Yes, it can.
4. (and 5., 6.) Hash functions in general can be considered primitives. Compression functions in general are not cryptographic primitives, because they have no security property. But surely you could call it primitive - without cryptographic. This is just like hash functions: In general, a hash function is not cryptographic. If you talk about a cryptographic hash function, you should actually call it a cryptographic hash function - unless the context is absolutely clear.
   But whenever you talk about a specific function and not the general one, then the term primitive is a bad choice.

Answer 2

Instead of primitives, try to think "tool" - cryptographic tools: Loose citation from "Handbook of applied cryptography": This book describes a number of basic cryptographic tools (primitives) used to provide information security. Examples of primitives include encryption schemes, hash functions, and digital signature schemes. ...the figure provides a schematic listing of the primitives considered and how they relate. ...these primitives should be evaluated with respect to various criteria such as: 1. level of security - is usually difficult to quantify. 2. functionality - primitives will need to be combined to meet various information security objectives. 3. methods of operation - primitives, when applied in various ways and with various inputs, will typically exhibit different characteristics; thus, one primitive could provide very different functionality depending on its mode of operation or usage. 4. performance - this refers to the efficiency of a primitive in a particular mode of operation. (For example, an encryption algorithm may be rated by the number of bits per second it can encrypt). 5. ease of implementation - this refers to the difficulty of realizing the primitive in a practical instantiation. This might include the complexity of implementing the primitive in either a software or hardware environment.

Answer 3

To add onto tylo's answer, Cryptographic primitives don't have to be all that primitive. When doing complex opeations: zero knowledge proofs, shared computing and more we find ourselves building on more layers of previous work. The lower layers are the cryptographic primitives. But they could themselves be built using another cryptographic primitive. I would not require atomicity. The primitive has some clear security properties and though the current known constructions may be built using other simpler primitives there could be another path. We have high level building blocks like commitment and oblivious transfer. It may be strange to think of something as complicates as oblivious transfer as primitive but it is useful especially when you consider non algorithmic physical alternatives. It is not difficult for untrusting parties to achieve commitment and oblivious transfer by physical means. Even if P=NP and all basic primitives break. So when designing high level constructs some of our cryptographic primitives may be far from primitive.