What Feistel network block ciphers do not use data-dependent table lookups or modular additions?

I am looking for block cipher algorithms based on Feistel networks. The algorithm is required to not use data-dependent table lookups (or data-dependent rotations) or modular additions/multiplications.

The only two algorithms that I have found are Simon and Simeck. Are there any alternatives?

• None that known. But since Feistel network only require a cryptographic pseudo random permutation, you can try putting Keccak or Gimli in Feistel mode. Both of the two permutations I've mentioned have constant-time data-independent implementations. – DannyNiu Nov 30 '18 at 7:11
• @DannyNiu: can you explain how to do that? These two algorithms are unkeyed permutations. How to construct a block cipher based on such functions? – lyrically wicked Nov 30 '18 at 7:23
• I'm going to close this question even though it is an interesting question. But the way the question is stated, it only asks for references. I guess we can keep it for future reference. If it is put on hold then we don't get long lists of answers with a single algorithm, hoping to answer it indefinitely. – Maarten Bodewes Dec 4 '18 at 15:26

I didn't wish to post an answer because I don't want invent any scheme that may cause security hole in somebody elses' system. But here I'll do a bit of illustration for you.

Because both Gimli and Keccak have large enough block size in their typical instantiation, we can simply put key in one half and cipher block data in another half (zero-extend if needed repeat key bytes if needed, as is being done with ChaCha20 and Salsa ciphers):

Gimli: [ data 128 bits | key 128,192,256 bits ] 384 bits.


Invoke the permutation:

Gimli: [ Random....... | Bitstring........... ] 384 bits.


And bring it into the Feistal network:

[ Block half A | Block half B ] // Plaintext block.
|              |
|      Key     V
data:->[Permute]->[+]
|              |
V              V
[ Block half A | Block half B']
|              |
V      Key'    |
[+]<-[Permute]<-:data
|              |
V              V
[ Block half A'| Block half B'] // Ciphertext block.


Possible ways to increase security:

• Increase the number of rounds from 2 to higher,

• Derive a key schedule for example by running the permutation in XOF sponge mode.

• Assuming that || denotes a concatenation, does this construction imply that Gimli(A||B) is used as F(A, B) in the scheme described in the “Construction details” section in the Wikipedia article? – lyrically wicked Nov 30 '18 at 8:25
• @lyricallywicked Yes. Although I've used single vertical bar character. – DannyNiu Nov 30 '18 at 9:14
• You may also be interested in this – DannyNiu Nov 30 '18 at 9:18
• Use at least four rounds. (That might not be enough depending on what security properties you need. Unfortunately I don't remember those "rules" so researching "minimum number of rounds for a Feistel cipher" is an exercise left to the reader.) Also use one of the input bytes to Gimli to store the round number. – Future Security Dec 1 '18 at 17:45