3
$\begingroup$

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.

$\endgroup$
  • 5
    $\begingroup$ OK, so to bring this more in-line with more traditional cryptographic understanding. The claim is that assuming two parties share a long-term symmetric key $K$, then you can find $R$ such that $(R,C=E(K,R,M))$ doesn't leak any information about either $K$ nor $M$ for any number of observed $(R,C)$ pairs? $\endgroup$ – SEJPM Feb 27 at 20:48
  • 1
    $\begingroup$ publish it and face the music. please note cryptographic systems with usable properties are discrete in nature, so if there is some chaotic or continuous dynamical systems aspects, with asymptotic or fully probabilistic proofs, this will weaken your claims in terms of usable cryptography. a worst case not average case point of view is needed in serious crypto. $\endgroup$ – kodlu Feb 27 at 20:55
  • 1
    $\begingroup$ @Grassi: In your question, you write that "no cryptanalysis would work". But the brute-force attack always works for symmetric cryptosystems if there is sufficient key reuse and sufficient computational power (e.g. for a known plaintext attack, the adversary can always check if a given key transforms the given message and additional randomness into the given ciphertext and thereby in the end discard all key candidates that don't work). Do you then really mean to say that no cryptanalysis works or merely that no cryptanalysis works better than brute force? $\endgroup$ – Polytropos Feb 27 at 22:01
  • 1
    $\begingroup$ I think we're shadow boxing, you need to write it up and submit or upload to ArXiv or IACR eprint server or whereever. There is no way of rigorously evaluating your proposal otherwise, short of employing a cryptography expert under an NDA, of course. $\endgroup$ – kodlu Feb 27 at 23:25
  • 6
    $\begingroup$ @Grassi: Encryption with an unconditional security proof (even in a fairly easy setting, say indistinguishability under known-plaintext attack) that allows key reuse would certainly be interesting. However, it would also come close at least to providing a $P \neq NP$ separation (although there may be ways to avoid that outcome). As a reviewer, I would expect to find a flaw in the proofs and possibly also exploitable weaknesses in the proposed mechanism, given its claimed properties. I would advise you to talk to a cryptographer at your institution before going public. $\endgroup$ – Polytropos Feb 28 at 1:59
5
$\begingroup$

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 secure1 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$.

$\endgroup$
  • $\begingroup$ Would you be able to clarify what you mean by "unconditionally secure"? For example if it is impossible to determine the encryption key (with certainty) given the ciphertext and public mathematical object with infinite time and computational resources, would this be called "unconditional security"? $\endgroup$ – GEG Feb 29 at 3:11
  • $\begingroup$ @Grassi I added a footnote as to what "unconditionally secure" means, TL;DR: "you don't rely on unproven assumptions". $\endgroup$ – SEJPM Feb 29 at 12:52
  • $\begingroup$ I apologize for asking another question on this, but with this scheme there is a deterministic formulation where the same input gives the same output every time, but it would be “easy” to find pseudo inverses. However if a non deterministic formulation were to be used then a pseudo inverse could only be obtained with negligible probability. In both cases however the system would be unconditionally secure. I take it that the relative ease of finding pseudo inverses for the deterministic case shows it doesn’t prove P not equal to NP, so is less likely to be met with skepticism? $\endgroup$ – GEG Mar 5 at 1:27
7
$\begingroup$

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).

$\endgroup$

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.