Are there any good symmetric-ish cyphers that involve three or more steps with independent key material for each step?

Formally, there should be a function $K(s)$ that returns a tuple $(k_1,..,k_n)$ and a function $P(k,d)$ such that if $d_i = P(k_i,d_{i-1})$ then $d_n=d_0$ but there are no known relationships between strictly fewer than $n$ of the $k_i$.

Stream cyphers provide this for $n=2$ of course, as the independence requirement becomes vacuous, but I'm unaware of anything with $n>2$ that's both secure and efficient as a symmetric cypher.

It's okay if we replace $P$ by another operation $P'$ for the $i$-th step for preferably at most one i but we do not want any relationship between $k_i$ and $k_j$ for $j \neq i$.

One could use secret sharing algorithms, or simply XOR, to do this quite securely, but that'd require key material as big as the original file, making it inefficient.

There are tricks for doing roughly this with asymmetric systems like elliptic curve scalar multiplication, but that's too slow for my purposes.

  • $\begingroup$ Any cypher I know has the property that identical key material must be used both for encryption and decryption, meaning $k_i$ is a substring of $k_j$ for some $i \ne j$. At a consequence, any system using onion encryption has at most one "cut-out" node : en.wikipedia.org/wiki/Cut-out_%28espionage%29 $\endgroup$ – Jeff Burdges Oct 23 '15 at 20:33
  • $\begingroup$ I'm asking for a cypher with an algebraic property of the key material that allows the keys to be split into multiple parts to be used separately. There are several ways to do with with elliptic curves, but one needs something with symmetric-like speed and security, ideally including immunity to quantum computers. $\endgroup$ – Jeff Burdges Oct 23 '15 at 20:35

This is not possible with symmetric cryptography.
To show this, I will construct an asymmetric encryption algorithm from your scheme.
Consider $pub = (k_1, \dots, k_{n-2})$ as the public key and $prk = (k_{n-1}, k_n)$ as the private key.
The encryption algorithm will be $c = enc(pub, d) := P(k_{n-2},P(k_{n-3},\dots ,P(k_1,d)))$
The decryption algorithm will be $d = dec(prk, c) := P(k_{n}, P(k_{n-1}, c))$
Since there may be no relations in the sets $puk \cup \{k_{n-1} \}$ and $puk \cup \{k_{n} \}$ , the computation of prk from puk will be infeasible.
This is a property of an asymmetric cryptographic system.

| improve this answer | |

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.