6
$\begingroup$

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

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

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

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

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

$\endgroup$
  • 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
3
$\begingroup$

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.

$\endgroup$

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.