2
$\begingroup$

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.

Improve this question
$\endgroup$
5
  • $\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
    Commented Oct 23, 2015 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
    Commented Oct 23, 2015 at 20:35
  • $\begingroup$ Are you looking for a commutable cipher like crypto.stackexchange.com/questions/101544/… ? $\endgroup$
    – David Cary
    Commented Sep 8, 2022 at 18:49
  • $\begingroup$ Some secret sharing schemes, to avoid the "key as big as the original file" problem, use a "hybrid cryptosystem" where the XOR or other secret sharing technique only applies to a small 32-byte encrypted header, which is later decrypted to recover the one-time symmetric key used to recover the plaintext of the large original file. Would that work for your application? $\endgroup$
    – David Cary
    Commented Sep 8, 2022 at 18:59
  • $\begingroup$ Are you looking for a commutable cipher like "Commutable and Composable Asymmetric Encryption/Decryption" or "Are there any secure commutative ciphers?" ? $\endgroup$
    – David Cary
    Commented Sep 8, 2022 at 19:02

1 Answer 1

Reset to default
2
$\begingroup$

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
$\endgroup$
0

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.