A few weeks ago I asked about a new symmetric cryptosystem discovered as consequence of some new mathematics work (link here). As per suggestion of commenters, I spoke with a cryptography professor, a computer security expert, and also continued to discuss with different math professors. We have since established the following facts as given in the below list. We wanted to (for the last time) ask a broad audience that could provide useful feedback given this now established new information.
Encryption takes form $E(T, K, P) = (T, C)$, and $D(T,K, C) = P$ for publicly chosen $T$. Some of the following points have redundancies between each other, but I allow this for clarity. The main properties of the cryptosystem are as follows.
- The security of the system rests on no unproven assumptions (such as the difficulty of factoring).
- Perfect secrecy: for $x \in P, y \in C$, $p(x|y) = p(x)$ (unconditionally secure), as arbitrary number of ciphertext gives no information about key or message.
- Key reuse: unlike the one-time pad, given arbitrary number of $(T, C_i)$ pairs and no plaintext, the attacker learns nothing about $P_i$ or $K$. Given $(T, P_i, C_i)$, the attacker learns nothing about $P_j$, $i \not=j$, given $E(T', K, P_j) = (T', C_j)$ for $T' \not=T$, nor about the key $K$.
- Secure under chosen plaintext attack: the attacker learns nothing usable about $K$ with an arbitrary number of chosen plaintext/ciphertext pairs.
- Semantically secure
- Probabilistic system, but Bob can always successfully decrypt with probability 1
- If the attacker guesses a key $K$, they have no way of verifying if the guess is correct, only that it is false.
- If Alice and Bob share $l$ messages using the same public object $T$, then if Eve obtains a plaintext/ciphertext pair she may decrypt all such messages, but she will be unable to decrypt messages sent using public object $T' \not=T$.
- More general cryptanalysis: with large number $l$ of distinct $(T_i, C_i)$ pairs so that $(T_i, C_i) \not = (T_j, C_j), i \not=j$, then, if Eve has a lot of compute, she may brute force construct an approximating key $K_a$, that would, with probability proportional to the size of $l$, give useful information about any new $C$, thereby ruining any previous notion of perfect secrecy with the cipher. However, if Alice and Bob use the same $T$ for each message, such an approximating key could not be built, but then the messages would be susceptible to plaintext attack.
- Note on efficiency: worst case encryption and decryption times grow linearly with key size. In most cases encryption/decryption time grows at rate of log of key length.
Again, given this new (verified) information, does this system offer any theoretically interesting properties that could warrant publication? Thank you all for your time.