Join Log in
Score:0
avatar Crypto

While Such Algorithm Option Is Possible, How Can Vernam Be The Only Unbreakable Cryptography?

cn flag
whatamnotsaying

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

87
0 + 0
Score:2
avatar Crypto
us flag
Mikero

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.

0 + 0
cn flag
whatamnotsaying
You are right. But we can't say "only vernam is unbreakable" isn't it?
0
Reply
cn flag
whatamnotsaying
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
0
Reply
us flag
Mikero
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).
1
Reply
poncho avatar
my flag
poncho
"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))
2
Reply
ธงชาติไทย
Elon Musk
I sit in a Tesla and translated this thread with Ai:

mangohost

Post an answer

Most people don’t grasp that asking a lot of questions unlocks learning and improves interpersonal bonding. In Alison’s studies, for example, though people could accurately recall how many questions had been asked in their conversations, they didn’t intuit the link between questions and liking. Across four studies, in which participants were engaged in conversations themselves or read transcripts of others’ conversations, people tended not to realize that question asking would influence—or had influenced—the level of amity between the conversationalists.