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
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?
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.
