4
$\begingroup$

When I read some articles about cryptography on wikipedia, I took note of the following statements (please, correct me, if any of these are wrong):

  • Perfect S-box (based on bent functions) provides maximum possible security against linear (and differential?) cryptanalysis.
  • The problem with using perfect S-boxes is that an S-box constructed purely from bent functions can not be invertible.
  • F function in Feistel network does not have to be neither balanced nor invertible. One could even make an extremely unbalanced Feistel network, where one side is only one bit, and have a bent function used as F.

From these statements it seems that using perfect S-boxes in F-function of an unbalanced Feistel network is an obvious choice for a simple and secure cipher. I understand, that someone would have come up with this long ago, if it was indeed so simple, but I can not find any information regarding possible downsides of such design.

Improve this question
$\endgroup$
4
  • 1
    $\begingroup$ Maybe you mean almost perfect. There are no perfect nonlinear binary sboxes $\endgroup$
    – kodlu
    Commented Dec 24, 2019 at 1:57
  • $\begingroup$ I have not yet red the article, but it seems to suggest they exist: Perfect nonlinear S-boxes. I will comment again when I get to read it. $\endgroup$
    – MadCake - Reinstate Monica
    Commented Dec 24, 2019 at 13:17
  • $\begingroup$ "In 94 we present an example how balancedness can be achieved without completely destroying the original good property." huh, it seems, the title was a bit misleading. $\endgroup$
    – MadCake - Reinstate Monica
    Commented Dec 24, 2019 at 13:23
  • $\begingroup$ Yes, they exist for odd characteristic, e.g., ternary vectors, but for binary they don't. $\endgroup$
    – kodlu
    Commented Dec 24, 2019 at 13:28

1 Answer 1

Reset to default
4
$\begingroup$

Almost perfect nonlinear permutations of $\{0,1\}^n$ are the best known designs for addressing both linear and differential cryptanalysis simultaneously. However $n$ needs to be odd. Such sboxes could be used in an SPN or feistel setup, but since one usually likes not just even length but power of two sbox bitlengths, for efficiency and implementation considerations, it is not common.

For your $(n-1)$ to one bit, very unbalanced feistel idea, the two issues I see are:

  1. Extremely slow diffusion due to the single bit.
  2. Bent functions are not balanced.

There are balanced quadratic functions which are almost perfect one can use, however, to address 2.

This is an active area of research.

See here, for example, for more discussion of sboxes which are permutations.

Improve this answer
$\endgroup$
3
  • $\begingroup$ It seems at the time of writing my question I was a bit confused about what unbalanced means (I thought it meant the number of input bits is not equal to the number of output bits). Using the proper definition (output yields as many 0s as 1s over its input set), it is correct that unbalanced functions make encryption more predictable, because one of the outputs (1 or 0) is more likely? $\endgroup$
    – MadCake - Reinstate Monica
    Commented Dec 24, 2019 at 13:12
  • 1
    $\begingroup$ Yes, you are right. $\endgroup$
    – kodlu
    Commented Dec 24, 2019 at 13:29
  • $\begingroup$ Sorry, I forgot that accepting an answer in less than 24 hours after asking is considered bad practice. I will check it back when the time passes. Thank you for helping me figure it out. $\endgroup$
    – MadCake - Reinstate Monica
    Commented Dec 24, 2019 at 13:33

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.