Score:1

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

br flag

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]

Score:0
my flag

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.

br flag
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.
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.