# Definition of "verification"?

I am trying to better understand the concept of verification in cryptography.

Verification algorithms are commonly used in message authentication codes (MACs) and digital signatures to confirm the integrity and authenticity of data. For MACs, verification typically involves recomputing the MAC using the message and comparing it to the transmitted tag. If they match, the data is accepted; otherwise, it is rejected.

This process is closely linked to the concept of correctness. For example, in the context of MACs, we want something like $$\text{Verify}(k, m, t)$$ should output $$1$$ and computes $$\text{Compare}(\text{MAC}(k, m), t)$$ for key $$k$$, message $$m$$, and tag $$t$$, where $$\text{Verify}()$$ and $$\text{Compare}()$$ are autodescriptive. For signatures this should be similar.

Besides that, verification algorithms are not limited to MACs and signatures but are widespread in cryptography, e.g. Zero-Knowledge Proofs, Authenticated Encryption, Commitment Schemes...

My questions:

1. What is verification in general?
2. What is the general purpose and goal of verification?
3. Is there a high-level, abstract definition of verification?
4. How does verification relate to correctness?
5. What properties must a cryptographic primitive fulfill for a verification algorithm to be meaningful?

Note: I am quite familiar with verification within a certain scheme/primitive, for what it is used, and how it works. However, I find it difficult to describe and explain the concept without using an example. Hence the question of an abstract and formal high-level description and explanation.

• Note that the compare within MAC should be time-constant. I'd say that because of that it usually doesn't output $1$; it makes more sense that successful authentication is a $0$, but in the end it is a boolean function. If part of a larger protocol generally the output is $\perp$ instead. For signatures some compare will be done, but it may not be the hash algorithm (see e.g. RSA / PSS). Commented Jul 12 at 21:44

Disclaimer: this is how I understand verification. I won't claim that this is an authoritative answer; given the broad context, I'm not sure one exists.

What is verification in general?

Verification is used to validate that the signing party did create a valid signature, authentication tag or proof. Generally it is seen as a boolean function but in practice signature algorithms may return a boolean, an error code or an exception.

What is the general purpose and goal of verification?

Verification shows that the other party is in possession of a secret key or other information that an adversary should not have access to. This can be used to perform entity authentication. Furthermore it can be used to establish message integrity and authentication of information (such as a message).

Is there a high-level, abstract definition of verification?

Well, you can of course define verification mathematically:

$$\text{Verify}(sk, m, \sigma) = \begin{cases} \text{true} & \text{if } \sigma \text{ is a valid signature for } m \text{ under secret- or private key } sk, \\ \text{false} & \text{otherwise}. \end{cases}$$

or

$$\text{Verify}(P, C) = \begin{cases} \text{true} & \text{if } P \text{ satisfies } C, \\ \text{false} & \text{otherwise}. \end{cases}$$

where $$P$$ is a proof and $$C$$ a condition.

How does verification relate to correctness?

In my opinion, it doesn't, at least not directly:

• Correctness ensures that the cryptographic scheme works as intended, in this case: if a message is signed properly, it should verify successfully;
• Verification is the outcome of the verification algorithm or process.

Although that's using more formal definitions of above. You can of course use these words in a different context, e.g. verification is checking if a signature "is correct" given a key and specific message. Language is fickle.

What properties must a cryptographic primitive fulfill for a verification algorithm to be meaningful?

I think that at minimum the party that is providing the signature or proof must be shown to be in possession of specific data such as a key or specific knowledge while the verifier must be able to define a boolean condition which indicates success or failure.

The related primitives then must be sufficient to be able to perform the required calculations of the signer / proving party as well as those required for the verifier.

I don't think you can get much more specific without defining the type of verification that is performed.

• If somebody does have an authoritative answer then I'll very happily swallow my words. I'd certainly wait a bit rather than accept this answer directly, if it ever gets accepted of course :P Commented Jul 12 at 22:28
• Thank you for the answer. It is a very good answer, but it is not as general as I would have hoped for. Commented Jul 15 at 7:04
• Thanks, wouldn't know how to make it more general. If you have questions or remarks about particular parts of the answer then either comment on them (in case I might be able to adjust accordingly) or ask a new question (5 related questions are already quite a lot to get through, and others may be able to handle additional questions better than I can). Commented Jul 15 at 12:55