# What's the probability of cracking this cipher using partial information about the private key obtained from $k$ public keys?

For the following cipher, what is the probability of someone without the private key generating a valid public key, using only information from a list of $$k$$ public keys previously generated with the private key?

This is the cipher:

To generate the private encryption key, $$Y$$: Let $$X$$ be an $$n$$ by $$i$$ matrix of random integers between $$0$$ and $$9$$, inclusive. Let $$Y$$ be a vector of the $$n$$ real numbers defined by converting each row in $$X$$ to a real number between $$0$$ and $$1$$, e.g., $$x_{1.} = (1, 2, 3)$$ becomes $$y_{1} = .123$$.

To generate public decryption keys, $$W$$: Create a pair of random $$j$$-digit numbers between $$0$$ and $$1$$ inclusive, $$a < b$$. Let $$Z =$$ $$R((Y - a/b)^2)$$, where $$R(.)$$ returns the ascending rank order of reals, e.g., $$R(23, 44, 2) = (2, 3, 1)$$. Let $$W = (a, b, Z)$$.

To decrypt with public key: Test if $$R((Y - w_{1}/w_{2})^2) = (w_{3}, w_{4}, ... , w_{n}).$$

The probability of successfully generating a valid $$W$$ without any information about $$Y$$ is $$1$$ out of $$n!$$. What is the probability of successfully generating a valid $$W$$ with only the information from $$k$$ public keys previously generated from $$Y$$, in terms of $$n$$, $$i$$, $$j$$, and $$k$$?

Of note: According to @grand_chat's answer here, we can uniquely define any $$Y$$ as the sequence of solutions to the infinite series of functions $$R((Y - r)^2)$$, as $$r$$ ranges over the rational numbers from $$min(Y)$$ to $$max(Y)$$. This implies that one cannot deduce a unique $$Y$$ from any finite $$k$$ of distinct $$W$$, but also that the probability of generating a valid $$W$$ increases with increasing $$k$$.

[probability of correctly guessing W corrected from $$1/10^n$$ to $$1/n!$$ per response]

## 1 Answer

The probability of successfully generating a valid W without any information about Y is 1 out of $$10^n$$

Actually, it appears that the only information that's hard to guess in W is the Z component, which is some permutation of the values $$(1, 2, 3, ..., n)$$. Hence, the probability of guessing successful is 1 in $$n!$$.

What is the probability of successfully generating a valid $$W$$ with only the information from $$k$$ public keys previously generated from $$Y$$, in terms of $$n, i, j$$, and $$k$$?

The obvious approach would take a valid public key, and adjust the listed $$a, b$$ so that $$a/b \approx a'/b'$$; this will correspond (with quite good probability) to the same $$Z$$, and hence a valid $$W$$. That is, with a single public key, we can generate another one.

• Right on both counts! I corrected the probability in the post as you suggested. I agree the best strategy would be to make a trivially small alteration of the original a/b, which makes it a much less interesting problem than I'd thought it was. This is actually a major simplification of a related cypher that would not share this vulnerability. I simplified it because a) long questions are less likely to be answered, and b) @grand_chat's proof, while very clever, does not generalize beyond functions of this sort. I'll have to work out a new version of the cypher, but I'll post here to update. Apr 17, 2022 at 21:51