1
$\begingroup$

Suppose we have $GF(2^{128})=F_2[x]/(x^{128}+x^7+x^2+x+1)$ and $a,b,c \in GF(2^{128})$ with $a*b=c$, where * is multiplication in $GF(2^{128})$. Could we convert them to $a',b',c'$ of length 128 bit vectors, such that $a'\&b'=c'$, where & is bitwise AND?

I think FFT might work, but I am confused how to do a FFT on a length 128 vector in $F_2$.

$\endgroup$

1 Answer 1

2
$\begingroup$

Could we convert them to $a',b',c'$ of length 128 bit vectors, such that $a'\&b'=c'$, where & is bitwise AND?

No. There are $2^{128}$ elements of $GF(2^{128})$, and there are $2^{128}$ length 128 bit vectors, and so there must be a 1:1 correspondence.

Now, consider the $GF(2^{128})$ element that converts to the all-1 vector; call the element $A$, and call the bit vector that is mapped to (namely, the all-1 vector) as $A'$.

Now, we know that the $GF(2^{128})$ equation $B \times C = A$ has at least $2^{128}-1$ solutions in $B, C$, however when looking that the post-mapping and function, we see that the corresponding operation $B' \& C' = A'$ has only one solution (namely, $B' = C' = A'$). Hence, we conclude that any such mapping cannot preserve the multiplication operation.

$\endgroup$
1
  • $\begingroup$ Thank you, this makes sense. I got a new idea: if we have a*b=c^d in $GF(2^{128})$, is it possible to convert it to a'&b'=c'^d'. The arguments do not follow directly, and I am not sure if this is possible. $\endgroup$
    – Halulu
    Sep 28, 2023 at 7:27

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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