I'm studying the paper Polynomial evaluation and message authentication https://cr.yp.to/antiforgery/pema-20071022.pdf , by Daniel J. Bernstein. He frequently makes arguments like the following:
Fix a finite field $k$. [Generate] 9 independent uniform random secrets $r1, r2, . . . , r8, s \in k$.
...[T]he sender wants to send a message $m$... where $m$ is a sequence of 8 components $m1,m2, . . . ,m8 \in k$. The sender transmits $m$ together with the authenticator $a = m1r1 + · · · + m8r8 + s \in k$.
...From the attacker’s point of view, given (m, a), all #k8 choices of (r1, . . . , r8) are equally likely: each choice of (r1, . . . , r8) is consistent with exactly one choice of s. (emphasis added)
I am trying to understand his claim that each choice of $r_1...r_8$ is consistent with exactly one choice of $s$. Outside of finite fields, I do not believe this to be true: That is, in general (not restricted to finite fields), many choices of $r_1...r_8$ may exclude certain $s$.
Below is what I've reasoned. Is it correct?
In a group, each element defines a permutation. The converse is not necessarily true: Other than the symmetric group, many permutations will not have a corresponding element which performs them.
Similarly, in a field, each non-zero element defines two permutations.
Consequently, if $a$ and $b$ are randomly selected from group $G$ or field $F$ with uniform probability, $ab$ has uniform probability over the entire $G$ or $F$. This has clear implications for cryptography: We can select any non-zero element at random and use it without fear that operating it will enter a trap. In this sense, all elements of the field are "equal" in that they each define a permutation.
Exponentiation
In section 4.2, Bernstein uses similar arguments to replace $r_1...r_8$ with $r^1...r^8$:
authenticator $a = m_1r^8 + · · · + m_8r + s \in k$.
This was very surprising! I can only partially justify it, as follows:
Since every finite field is cyclic, if $r$ is a generator for the field, if $n$ is a random variable with uniform probability, $r^n$ will be randomly distributed over the field with uniform probability. This has the same advantages.
What if $r$ is not a generator? It would seem that $r^n$ will only map to certain elements of the field, making $r^n$ poorly suited for crypto. Yet Bernstein makes no such restriction on $r$ being a generator. Can you please help me understand this?
Update
In discussing the Bernstein paper, Proctor writes ( https://eprint.iacr.org/2014/613.pdf ):
. When encrypted with a one-time pad, the digest output from [Bernstein] forms an information-theoretic message authentication code.
This is a great way to consolidate my question: Under what circumstances does finite field addition, multiplication, or exponentiation by a randomly selected element act like a one-time pad?
My tentative answer is:
- Addition: Always
- Multiplication: Iff the element is non-zero
- Exponentiation: Iff the base element is a generator