# Understanding reversible addition in a prime field

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?

• 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. – fgrieu Mar 9 '18 at 17:56
• @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! – 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'.

• Yeah, I'm just using Y, never Y mod W. No need to worry about leakage. Thanks. – Erik Aronesty Mar 9 '18 at 20:16
• @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? – poncho Mar 9 '18 at 20:37
• Yeah, it's fine. Because Y is random and a lot larger than W. – Erik Aronesty Mar 20 '18 at 18:00
• 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. – Erik Aronesty Mar 25 '18 at 23:42

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.