I'm trying to understand the security implications of addition in a prime field.

Suppose I have X + Y = Z, occurring under prime field P(W) where W is the size of the field.

If I know X and Z, I can trivially derive Y.... as long as Y is known also to be within the prime field.

If however, Y is number significantly larger than W... say 2^128 times larger, it seems to me that Y will be as hard to derive from X and Z as the guaranteed size of Y.

IE: Y is about as safe as an AES128 key.

Is this correct?

  • 1
    $\begingroup$ The question's fragment "X + Y = Z, occurring under prime field" implies that Y is in the prime field. X + Y = Z outside of the prime field stand undefined. Depending on that definition, it can entirely define Y, or leave a great many Y possible. We can't tell. $\endgroup$ – fgrieu Mar 9 '18 at 17:56
  • 1
    $\begingroup$ @fgrieu Have you ever tried to add an element of $\operatorname{GF}(2^{128})$ to a giraffe? I bet it's a lot of fun! $\endgroup$ – Squeamish Ossifrage Mar 9 '18 at 20:09

Y is about as safe as an AES128 key.

Is this correct?

Well, it depends on you're doing with $Y$. The attacker can deduce the value of $Y \bmod W$. Now, if the only thing you're doing with $Y$ is adding it to things modulo $W$, the attacker knows everything he needs to know about $Y$. He may not know the exact value, however he does know that it's one of a large set of values that act exactly the same, and so he doesn't care which one it is.

On the other hand, maybe you're doing something else with $Y$ as well. Whether that is safe or not would depend on what that is (as whether leaking the value $Y \bmod W$ is critical to the secure of that 'something else'.

  • $\begingroup$ Yeah, I'm just using Y, never Y mod W. No need to worry about leakage. Thanks. $\endgroup$ – Erik Aronesty Mar 9 '18 at 20:16
  • $\begingroup$ @ErikAronesty: you might be using $Y$, but the attacker knows $Y \bmod W$. Are you sure that's not giving the attacker too much information? $\endgroup$ – poncho Mar 9 '18 at 20:37
  • $\begingroup$ Yeah, it's fine. Because Y is random and a lot larger than W. $\endgroup$ – Erik Aronesty Mar 20 '18 at 18:00
  • $\begingroup$ if i redo this operation an attacker can see the difference between the two operations and deduce Y. So it's only ever safe to do it once. $\endgroup$ – Erik Aronesty Mar 25 '18 at 23:42

Addition is a bad idea:

Suppose the prime field W is 7, X is 2 and and Y (the secret answer) is 42.

  • ( X + Y = 44 ) % 7 = 2
  • Attacker cannot know Y from W and 2 and X. Instead he now knows only 3 bits of Y. Y can be any value that modulo 7 is 2.
  • Y remains "3-bit secure"

Now you decide to use a new X, with value 4.

  • X + Y = 19 % 7 = 4
  • Attacker still does not know Y, but can now perform this operation F(X,Y,W) even if Y is not known.

This makes the function F essentially useless for cryptography ... unless it is done only once ever.

Multiplication is a little better... but only if you choose safe values for W and Y

  • W cannot be a factor of Y.
  • 7 is a factor of 42 .... and so any choice of X will result in zero... again rendering the function useless.
  • The only safe value to choose for Y would be a prime

If Y is prime, half the bits of your secret are safe under multiplication by X, even if the attacker had access to a F(X, Y, W) machine.

But it's still fairly useless, because although you don't know Y, the attacker now has the ability, by using the inverse modulo, to produce an "equivalent Y" under a fixed prime field. Varying the prime field solves this but blows up the problem into a terrbily expensive protocol.

The correct solution is to do your math "in the exponent.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.