In the paper located at https://eprint.iacr.org/2011/401.pdf, suppose we replace matrix multiplication with bitwise XOR operations in Definition 5.1 to create an LWE degree-k PRF. I'm seeking clarification regarding how this alteration affects the proof outlined in section 5.4, particularly with respect to Theorem 5.10. Can we still demonstrate the theorem's validity with this modification, or does it introduce new challenges?

More specifically, the function is defined as

$\mathit{F}(x) = \mathit{F}_{\mathbf{A},\{S_i\}}(x_1 \dots x_k):= \Bigl\lfloor \mathbf{A}^t . \{\oplus_{i=1}^{k}{S_i}^{x_i} \}\Bigr\rceil$

instead of

$\mathit{F}(x) = \mathit{F}_{\mathbf{A},\{S_i\}}(x_1 \dots x_k):= \Bigl\lfloor \mathbf{A}^t . \prod_{i=1}^{k}{S_i}^{x_i} \Bigr\rceil$.

  • $\begingroup$ That's such a weird question. Why would you expect the XOR operation to behave in any way like matrix multiplication? Note that XOR on matrices would presumably be entry-wise, so having matrices at all would hardly make sense to begin with. $\endgroup$ Oct 4, 2023 at 16:32


Your Answer

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