I am interested to identify the effect of replacing $\oplus$ with $\boxplus$ on basic balanced Feistel structures over $r$-rounds. Given:

$F_\boxplus[L,R]= [S,T] = [R,L \boxplus f(R)]$ where $f$ is a PRF

$[L,R] \in \left\{0,1\right\} ^{n} $

Q1 . In terms of CPA and KPA security, does $\boxplus$ replacement add security over 3 rounds, with proof?

Q2 . If $\boxplus$-Feistel structures have better security bounds than $\oplus$-Feistel, why are they not commonly used?

  • 2
    $\begingroup$ I'm assuming $\oplus$ denotes bitwise XOR here, but what's $\boxplus$? $\endgroup$ – Ilmari Karonen Nov 2 '18 at 11:28
  • 2
    $\begingroup$ @IlmariKaronen I would assume it to mean addition (modulo 2^(blocksize /2)) $\endgroup$ – SEJPM Nov 2 '18 at 11:49

In term of CPA and KPA security, does $\boxplus$ replacement add security over 3 rounds, with proof?

No. There's nothing special about $\oplus$ in the Feistel struture. In fact any group operation $\boxplus$ over $\{0,1\}^n$ will do just fine. The main point of these random functions is to "blind" the previous rounds' other halves and for that a group operation is sufficient.

In fact Maurer and Pietrzak proved the more general security bounds for the Feistel construction beyond 4 rounds using an arbitrary group operation $\oplus$.

If $\boxplus$-Feistel structure have better security bounds that $\oplus$-Feistel, why do not we see it common?

Well, as any group operation is sufficient, we usually choose the operation which can be computed fastest on most hardware. In particular you can evaluate XOR on your whole arbitrary-width block without having to consider carries and the like on any word-size. Also it's way easier to construct XOR in hardware than it is to construct any other group operation I can imagine right now. Also it's hard to beat 1 cycle / word with no inter-bit dependencies.

| improve this answer | |
  • 2
    $\begingroup$ The other nice thing about XOR is that it is a self-inverse. Hence, it makes it more convenient to share the same circuitry with encryption and decryption, with the only change being in the key scheduling. Yes, you can do the same with other group operations (e.g. make the even rounds $\boxplus$ and the odd rounds $\boxminus$), but that is more complicated. $\endgroup$ – poncho Jul 15 at 13:10

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.