1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ I guess the first assumption about it being proven to be secure is the main interesting part. Other than the OTP, I don't think that there are any provable secure schemes out there. If you already have spoken to a number of professors it starts to look interesting, I think they are a better judge if this scheme is worth a paper or not, as we're just being told the properties. $\endgroup$ – Maarten Bodewes Mar 14 '20 at 23:14
  • $\begingroup$ I am not an expert in details of provably secure systems, though this paper co-authored by a reputable author in the coding theory community claims to have designed one, for whatever it may be worth. I am unfamiliar with the specific journal and did not do any reputation search for the journal: hindawi.com/journals/mpe/2016/7920495 $\endgroup$ – kodlu Mar 15 '20 at 1:30
  • 1
    $\begingroup$ I would say that this is not perfect secrecy. $\endgroup$ – Patriot Mar 15 '20 at 16:15
2
$\begingroup$

Again, given this new (verified) information, does this system offer any theoretically interesting properties that could warrant publication?

Again, no. You could put together a paper and submit it to eprint (or maybe arxiv, I'm not familiar with their acceptance policies), but beyond that, I can't think of any journal or conference that'd be interested.

As for your "verified" information:

Perfect secrecy: for $x \in P, y \in C$, $p(x|y) = p(x)$

It is a homework exercise to show that if you have this property, then you must have at least as many keys as possible plaintexts. So, to encrypt a megabyte plaintext, you must have a megabyte key. So, do you have megabyte keys? Or, do you have a low ceiling on the size of the plaintext you can encrypt?

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

So, the public object $T$ is effectively a nonce; that is, a given $T$ value can be used to encrypt only a single message.

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$

So, if the attacker gets a number of ciphertexts, they can get information about plaintexts encrypted with the same key. This falls rather short of the "perfect secrecy" you claimed in the previous bullet points.

The only comeback would appear to be "by a lot, you mean more computation than is feasible. However, if you make that argument, you have to assume that there are no optimizations beyond the attack you have sketched out; that means that you are making an assumption (and so you are not really any better than, say, AES or ChaCha…)

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.

I'm not sure what to make of this. By 'key length', we typically mean 'length of the key in bits'. To use $n$ bits of the key as part of the encryption or decryption time, that takes at least $O(n)$ time (if nothing else, to read the key bits). If encryption/decryption time grows (in most cases) logrhythmically with key length, that means in most cases you don't access the majority of the key bits (because you don't have the time). This property would make key searching attacks far more efficient (as the attacker wouldn't have to guess most of the key).

Is that what you really meant?

$\endgroup$
  • $\begingroup$ Could the downvoter provide the reason? $\endgroup$ – kelalaka Mar 15 '20 at 18:19
  • $\begingroup$ I was wondering that myself - do they disagree that there's no venue (other than eprint and arxiv) that would accept it (and if so, could they list one)? Or, do they disagree with my analysis of the various claims that the OP makes? $\endgroup$ – poncho Mar 15 '20 at 18:41

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.