1
$\begingroup$

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]

$\endgroup$

1 Answer 1

0
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ 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. $\endgroup$
    – virtuolie
    Apr 17, 2022 at 21:51

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.