0
$\begingroup$

Suppose Alice and Bob choose a number face to face. Let's call it "97"

Alice's original message is "Where did you study?"

Suppose we have an artificial intelligence. Let this artificial intelligence produce 1000 meaningful messages

1. Message: "You were so good at school"
2. Message: "My uncle came to us. I told my uncle about you"
3. Message: "Has your illness passed? Are you better?"
.
.
.
97. Message: "Where did you study?"
.
.
.
1001. Message: "I didn't understand the ontological argument in the book you suggested"

then send it to Bob. Eve can not be sure about what is the original message. But Bob know because of "97" which is secret key.

Let Bob's answer be "I studied in Ukraine"

Let artificial intelligence prepare 1000 meaningful messages again

1. Message: "You know I got over my depression. it was a lucky day"
2. Message: "So what did you say about me? I hope you mentioned that I'm a great person"
3. Message: "I think I'm dying. Life would be better if I didn't have a chronic cough"
.
.
.
97. Message: "I studied in Ukraine"
.
.
.
1001. Message: "I'm available today. Come to my house and I will help you"

I know if Eve knows Bob or Alice, she can cancel out some probabilities. But if the AI's algorithm is good enough, Eve will be truly helpless. I also know that this algorithm does not check if the message has been corrupted by Eve. But it can be overcome quite simply

Just as Vernam has assumptions such as "totally random", assumptions such as "if the artificial intelligence produces messages that are too good for Eve to sift through" can be made in this algorithm.

Isn't this algorithm as secure as Vernam under these assumption(s)?

$\endgroup$

1 Answer 1

2
$\begingroup$

Suppose I already know that the secret message is 100 English characters long. Based on this, I can't guess your secret message with probability better than $1/26^{100}$. If you encrypt with one-time pad, then even after seeing that ciphertext, I still can't guess your secret message with probability better than $1/26^{100}$. That's what the security of one-time pad gives you: seeing the ciphertext does not help guess what the plaintext was (in fact, the ciphertext by itself gives no information about the plaintext).

However, if you "encrypt" using the method in your question (if I understand it correctly), then after I see that ciphertext I can guess your secret message with probability 1/1001. Seeing the ciphertext significantly improved my chance of guessing the plaintext.


To answer the question in the title: Claude Shannon famously proved a result saying that if an encryption scheme satisfies his "perfect security" definition, then it must have at least as many possible keys as possible plaintexts.

Any perfectly secure encryption scheme that is not wasteful in its keys therefore has exactly as many keys as plaintexts. Now, it is not hard to extend Shannon's result to say that if a scheme has exactly the same number of keys as plaintexts, then in order to be perfectly secure, its encryption operation must be a quasigroup operation, and its keys must be uniformly distributed.

In other words, every perfectly secure encryption scheme is either wasteful in its number of keys, or it looks exactly like one-time pad except possibly replacing XOR by a different group operation.

I can't find a great presentation of Shannon's lower bound theorem and this extension -- the best I could find was this.

$\endgroup$
4
  • $\begingroup$ You are right. But we can't say "only vernam is unbreakable" isn't it? $\endgroup$
    – user97787
    Commented Jan 24, 2022 at 22:47
  • $\begingroup$ I really hate to use language poorly. sorry i was always like this i hope it gets better... I accept your answer but i hope someone answers that question in title too $\endgroup$
    – user97787
    Commented Jan 24, 2022 at 22:55
  • 1
    $\begingroup$ For certain definitions of "unbreakable", and depending on how narrowly you define one-time pad, then yes we can say it. Claude Shannon proved an impossibility result that basically says: any "perfectly secret" encryption scheme has to look very much like one-time pad in the most fundamental aspects (more keys than plaintexts, etc). $\endgroup$
    – Mikero
    Commented Jan 24, 2022 at 22:55
  • 2
    $\begingroup$ "it looks exactly like one-time pad except possibly replacing XOR by a different group operation."; actually, it could use a nongroup Latin square operation (this message was brought to you by Pedants R Us (tm)) $\endgroup$
    – poncho
    Commented Jan 25, 2022 at 4:05

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.