Score:0

Crypto

Computational indistinguishability

Sean

11/22/22, 12:22 PM

Given a multiplicative group of order $q$ and modulus $p$. Given two constants $a$ and $b$ randomly sampled from $Z_q$. Let random variable $x_a$ be a pair $(x, x^a \mod p)$ and random variable $x_b$ be a pair $(x, x^b \mod p)$. Would the distribution of $x_a$ and $x_b$ be computationally distinguishable?

1 + 2

indistinguishability

Sean

11/22/22, 12:35 PM

Here $a$ and $b$ are are known, otherwise the decision is simple: since a is known, simply gets $a^{-1}$ and given pair $(x, x^a)$ apply $(x^a)^{1/a}$ and check if it is equal to $x$.

Mark

11/22/22, 2:56 PM

Do you mean $a$ and $b$ are *unknown*?

Score:1

Crypto

Yehuda Lindell

11/22/22, 12:49 PM

The question is confusing in the use of the term "constants". However, it does say randomly sampled. So the random variable is $(x,x^a \bmod p)$ where $a$ is random in $\mathbb{Z}_q$. If this is the case, then the two distributions are identical. They are just the same distribution with different notation for the randomly sampled value.

0 + 8

Sean

11/22/22, 12:59 PM

Thanks for the feedback. I am still confused a bit. Given a pair $(x, x^a)$, I would assume that its probability appearing in the 2nd distribution would be 0? In another word, the $a$ and $b$ are fixed for the 1st and 2nd distribution. The $x$ is randomly sampled and then it leads to tuple $(x,x^a)$ and $(x, x^b)$.

Yehuda Lindell

11/22/22, 6:41 PM

I think I misunderstood the question. Is the probability space only over the choice of $x$, but not of $a$ or $b$? In that case, the distributions are trivially distinguished.

Sean

11/23/22, 12:52 AM

Thanks for the input! I'm wondering what is the idea for distinguishing the two using an efficient program? Given $x$, how does a probabilistic machine tell the difference between $x^a$ and $x^b$ if $a$ and $b$ are unknown? It looks like that it needs a lot of samples (of the two distribution) to find a conflicting pair?

Yehuda Lindell

11/23/22, 12:47 PM

There is confusion here. There isn't known and unknown. If they are fixed then they are assumed to be known. If they are unknown, then that would mean they are randomly chosen, and then it's the same random variable. There can of course be a case where a single $a$ is chosen and then many pairs with different random $x$'s are given relative to the same $a$. Bottom line, this just isn't well defined.

Sean

11/23/22, 11:54 PM

I guess I will have to rephrase my question:

Sean

11/24/22, 12:00 AM

Let me rephrase the question: let $P_a$ be a probabilistic machine which knows a secret $a$ and generates a sequence of $n$ tuples: $(x_1, {x_1}^{a}), ..., (x_n, {x_n}^a)$ where the $x_i$ for each tuple is randomly sampled. Similarly, let a PPT $P_b$ be defined. Now let a challenger randomly pick two sequences generated by $P_a$ and $P_b$ (they could be both from $P_a$ or one from $P_a$ and one from $P_b$). Can one tell if the two sequences are generated by two different PPTs?

Yehuda Lindell

12/24/22, 12:45 PM

Does only $P_a$ know $a$, or does the distinguisher also know $a$? If the former, then the distributions are statistically identical; if the latter, then the distributions are trivially distinguished.

Sean

12/27/22, 12:29 PM

Thanks for the response! Distinguisher does not know $a$, $b$. So that solves my problem then. Thanks again!

Elon Musk

I sit in a Tesla and translated this thread with Ai:

EN: Computational indistinguishability

TH: การแยกไม่ออกทางการคำนวณ

RO: Indistincbilitatea computațională

RU: Вычислительная неразличимость

VI: tính toán không thể phân biệt

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.