Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It only takes a minute to sign up.
Sign up to join this community
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$.
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.
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$