Research question: usefulness of newly discovered symmetric key cryptosystem

Question

both myself and my collaborators are pure mathematicians with only tangential experience in the study of cryptographic systems, so if this question is unclear or does not belong here, please do let me know. I apologize for the length of this question, after necessary background my questions appear in the last part.

As previously stated, my collaborators and I are pure mathematicians and over the coming months we will be publishing work on a new class of mathematical system we have discovered (it relates to many different areas in mathematics, the details are not important for the purpose of this question). One of my collaborators pointed out that certain properties of this system make it ideal for use in cryptography, and indeed upon further analysis this is what we have found.

Using the Alice/Bob/Eve analogy, the basic distinguishing properties of such a cryptographic system are as follows. Because this is a symmetric key system, Alice and Bob must meet to generate their random key. Once Alice and Bob wish to send a message, they publicly chose a particular type of mathematical object at random, call it $T$ (the type of mathematical object is not important), and use this along with their key to generate a set of coordinate points that will each uniquely map to a 0 or a 1.

With this, Alice can send Bob a subset of these coordinates (with each coordinate mapping to 0 or 1), and because Bob has the same set of coordinates he can "decrypt" the message of coordinates to obtain the bit string Alice wished to share.

---

So far this description appears to offer nothing new, and in fact if Alice wishes to only send Bob one message this is equivalent to the one-time pad. The issue with the one-time pad of course and similar systems is that sending multiple messages with the same key leads to leaks, so for every new message Alice and Bob must use a new key, which of course means sharing the keys in the first place which is difficult.

The unique (we think) property of the cryptosystem offered by this mathematical discovery is that so long as Alice and Bob publicly choose a new particular mathematical object ($T$) to apply their key to before each message sent (of which there is a continuum of choices for $T$), they can use the same initially chosen key to send an arbitrary number of messages, for we can prove that it would be mathematically impossible for Eve to ever determine the key if such a method was used.

In fact, we can also prove that so long as Alice and Bob publicly choose a new $T$ for each message, to Eve each message of coordinates sent between Alice and Bob would random, so no cryptanalysis would work.

Further, one of my collaborators has a (light) background in quantum computing and is highly confident that this system is not susceptible to brute-force attack from quantum computers (much less classical ones). We also remark that this encryption scheme is highly efficient, and its encryption/decryption time complexity scales linearly with just the size of the secret key chosen (and the complexity of the encryption scales exponentially with the length of encryption key).

---

My questions are as follows. Does a cryptosystem exhibiting such properties already exist? Would a cryptosystem exhibiting these properties be of any possible use to the community? Even if not (ie. analogous systems already exist), should we pursue publishing the method in a journal? If so, can anyone here recommend any journals, and things to watch out for when publishing in cryptography?

I know I have been incredibly discrete in discussing the details of the mathematical system for I cannot give too much more at the moment, but I hope this information is sufficient for giving general answers to the questions.

Thank you all so much for your time and help.

Answer 1

Does a cryptosystem exhibiting such properties already exist?

For all practical purposes this looks like CPA-secure symmetric encryption which is a solved problem in practice and for practical purposes such a result would only be interesting if it managed to (on-average) encrypt one byte in less than 5 CPU-cycles on a modern CPU.

Would a cryptosystem exhibiting these properties be of any possible use to the community?

If this encryption scheme is unconditionally secure¹ it seems to be described to be, then its existence proves $P\neq NP$. This would indeed be of great interest for the theoretical research community. The $P\neq NP$ proof follows from the chain that symmetric encryption implies PRGs (PDF) and PRGs are trivially cryptographic OWFs and the existence of cryptographic OWFs implies $P\neq NP$.

The requirements as per the above paper for the encryption system are simple:

1. Assume that Alice and Bob share a common secret $k$.
2. Alice can use $k$ and some randomness to create a ciphertext $c$ that Bob (with optional randomness) can successfully decrypt with probability at least $0.9$.
3. For a random $\ell(n)>n$-bit message $m$, a random $\ell(n)$-bit $r$ and the encryption of $m$ under the shared key $c\gets E(k,m)$ and for all probabilistic polynomial-time Turing machines $M$ it holds that $|\Pr[M(1^n,c,m)\to 1]-\Pr[M(1^n,c,r)\to 1]|\leq \varepsilon(n)$ for some negligible function $\varepsilon$.

Obviously reviewers will be aware of the fact that such a cryptosystem would prove $P\neq NP$ and will therefore be very skeptical of any such results.

If so, can anyone here recommend any journals, and things to watch out for when publishing in cryptography?

Cryptographic publishing usually happens via the IACR and conferences, the relevant ones for such a work would probably be the three main ones Crypto, Eurocrypt and Asiacrypt as well as the area-conference TCC, though there is also the Journal of Cryptology and ToSC as well as ePrint for preprints.

^{1: "unconditionally secure" here means that the security definition is satisfied without relying on unproven assumptions like $P\neq NP$.}

Answer 2

The unique (we think) property of the cryptosystem offered by this mathematical discovery is that so long as Alice and Bob publicly choose a new particular mathematical object ($T$) to apply their key to before each message sent (of which there is a continuum of choices for $T$), they can use the same initially chosen key to send an arbitrary number of messages, for we can prove that it would be mathematically impossible for Eve to ever determine the key if such a method was used.

Actually, that can easily shown to be impossible, as long as we make a few minor assumptions:

• We will assume that the adversary is computationally unbounded (that is, he can perform any finite number of computations)

• We will assume that the adversary has access to a number of encrypted messages (along with their corresponding $T$ values); we'll denote these pairs as $(T, C)$ values.

• We will assume that the adversary can recognize an incorrect decryption (perhaps he knows the contents of some of the encrypted messages, which is a standard assumption in cryptography)

• We will assume that, if some keys act the same (that is, they encrypt and decrypt identically), then finding any key in the same equivalence class as the 'correct' key would count as success for the adversary

So, here is what our adversary would do; he would go through all possible values of the key $K'$, and with each possibility, decrypt every ciphertext $(T, C)$ and see if it results in a plausible plaintext. If it every $(T, C)$ pair results in a plausible decryption, then the value $K'$ is declared correct.

It should be obvious that, if $K'$ were not the correct key (or in the same equivalence class), then some ciphertext would have decrypted incorrectly; hence this finds the correct key.

Now, the above procedure shows that key recovery is mathematically possible (and we could make the proof less hand-wavy if we shifted to the question of unknown message decryption, which is what the adversary is really interested in). Of course, if the space of possible keys is large, this procedure is impractical (as we really don't actually have an adversary with unbounded computation), but does leave open the question of whether there are computational optimizations that would make it practical. That I don't know the answer to, and frankly speaking, neither do you.

And, to answer your questions:

Does a cryptosystem exhibiting such properties already exist?

Do we have efficient symmetric cryptosystems that are believed to be secure? Sure, we have quite a number of them.

Even if not (ie. analogous systems already exist), should we pursue publishing the method in a journal?

Actually, in cryptography, there really aren't many journals (there's the Journal of Cryptology, but that's about it, not counting predatory ones that everyone ignores); all the exciting new work is published in conferences. On the other hand, I can't think of any conference that would be interested in what you have; the next level down is publishing on eprint (or arXiv), however I'm not certain that even the eprint editors would be that interested in taking this (unless you do some work to show that you've done the basics to ensure that your system isn't trivially weak).

If you do want to pursue your idea, then things to consider:

• Is your system still strong even if the adversary knows some of the encrypted messages? What if the attacker can pick some of the messages (and use what the ciphertexts look like to decrypt other messages of unknown contents)?

• How would your system respond if an adversary modifies one of the ciphertexts $(T, C)$, and passes that modified ciphertext to be decrypted? Will the modified ciphertext be rejected by the decryptor? That can be handled by other means, however that slows things down (and modern fashion is that encryption and integrity protections should be provided by the same cipher).

• You say your system is efficient; what do you mean by that? For example, if it were implemented on a modern CPU, how long (in CPU cycles) would it do encrypt a message of size L? If it takes T cycles, what's the size of $T/L$? If it's more than 5 or so, well, your system wouldn't be considered efficient (by modern standards).