What is the strength and attack vectors of this simple scheme?

Question

Let's say that Alice wants to communicate some secret value $S$ to Bob through a public channel in a way that other people don't know what the value was.

To do this, Alice publishes that secret value to the public channel, along with $N-1$ other values, making a list $L$ which has $N$ items in it.

Before this communication, Alice and Bob agreed that the value Alice wanted to communicate to Bob would be $L_M$ where $M \in [0,N)$.

How secure is this scheme? What attack vectors could be used on it? Also, does this technique have a name?

Some thoughts of my own:

• The security of the scheme seems to relate to the size of $N$. Larger $N$ values seem more secure.
• It seems like if you didn't choose the other values of the list carefully, that it could be seen statistically that "one data point doesn't fit with the others" which could make the actual value cared about stick out more obviously.
• One idea to make the value fit in completely could be that if the secret value $S$ could be represented in $B$ bits, that maybe the list $L$ could be a random shuffle of all values $[0,2^B)$, but if someone knew that, they could know that the number was probably on the higher side of the values so this may be too naive.
• Agreeing on $M$ in advance has the usual key generation / key sharing / key storing problems and attack vectors. I'm not interested in that part of the problem.

Thanks for any information or insights!

Answer 1

Short answer: Sorry, no, unfortunately your concept is neither a secure, practical nor efficient crypto scheme.

Slightly longer answer: To illustrate the impractically of your scheme, let's assume you are sending a completely random bit string $S$ of length $B$. In such case, in order to preserve perfect secrecy, you will at least have to send a list $L$ containing all possible values $[0..2^B)$ in random order, except for $S$ which is fixed at position $M$, where $M$ is the secret key you share with the recipient.

Now, if $M$ is selected completely at random from all possible values, it will also be a random element from $[0..2^B)$ and consequently be exactly as long, and contain as much entropy as, the message $S$ you want to sent.

The cipher text $L$ on the other hand, will be exponentially longer than the plain text message $S$. This is bad, because it means that your effort of sending the message securely, will be exactly as great as the effort you want your adversary to suffer trying to brute force guessing the key or the plain text.

Furthermore, if the plain text $S$ is not completely random, securely executing your scheme gets more complicated, but the conclusion doesn't change. If you maximize security, your effort of encoding and sending the plain text will be no less than the effort you want your adversary to suffer trying to break your scheme.

Answer 2

Reviewing crypto-protocols is in general off-topic here, and there has actually been a lot of discussion about it recently. If the voting keeps its trend, it's likely to become an official closing reason around May.

In general, I believe this answer in Sec.SE is amazingly accurate at explaining why building crypto constructions out of thin air is a bad idea. Recently there was another discussion in the same direction that could be also interesting to check.

The point is: don't reinvent the wheel. There is a lot of concepts that can fit your objective and have been widely tested. My first thought was Diffie-Hellman key exchange, but then I realized that a lot of scenarios can fit, including normal symmetric and asymmetric encryption.

There are things that are immediately apparent in your description, starting by the fact that you need to transfer $N$ items to get one value, and the idea that if they can agree on $M$ securely they could agree on $N$ also using the same channel, but then again: don't try to build with sticks when concrete is an option.