I am studying a little bit about one-way functions from Dr Goyal's notes.

He constructs the following OWF:

Let $D=\Bbb Z_2^{n^3}$ and $R=\Bbb Z_2^{2 n}$. Given $x \in D$, $f$ interprets $x$ as a set $S$ of $n^2$ numbers, each of $n$ bits and uses deterministic PT primality test to find the first two 2 primes in $S$. If $f$ finds $p$ and $q$, then output $p q$. Otherwise, it outputs FAIL.

My Question here is what does it mean Mathematically the phrase $\color{blue}{\text{$f$ interprets $x$ as a set $S$ of $n^2$ numbers, each of $n$ bits}}$.

Can you please give a clarification together with an Example, in case mine is not correct?

For example, I took $n=2$ and $x=11101110\in \Bbb Z_2^{2^3}$, so $|x|=2^3$. Thus, we get the $n^2=2^2=4$, $n=2$-bit integers $11,10,11,10$, which correspond to $3$, $2$. Is this what he means?



1 Answer 1


It is common to find this sort of high-level abstraction of how things are encoded. For this specific case, it uses the fact that the set $\Bbb Z_2^{n^3}$ has the same cardinality as $\Bbb Z_2^{n}\times \Bbb Z_2^{n}\times\dots\times \Bbb Z_2^{n}$ where the product is over $n^2$ copies of $\Bbb Z_2^{n}$. So there is a one-to-one mapping $\varphi$ that takes an element of $\Bbb Z_2^{n^3}$ and maps it to an element of $\Bbb Z_2^{n}\times \Bbb Z_2^{n}\times\dots\times \Bbb Z_2^{n}$. Note that formally speaking $S$ is a tuple of $n^2$ numbers and not a set since elements can repeat. It doesn't really matter what $\varphi$ is, only that it is one-to-one. Changing $\varphi$ would change the function $f$, but it is still one-way since you're only changing the encoding.

  • $\begingroup$ Thank you for your answer, So, you say that $\Bbb Z_2^{n^3}$ is isomorphic to $\underbrace{\Bbb Z_2^{n}\times \Bbb Z_2^{n}\times\dots\times \Bbb Z_2^{n}}_{n^2}$, but as what structure? As rings? Also, what is precisely the map? In addition, it makes sense to me that $S$ is a collection of numbers; if my example is correct, then by taking the pairs of $11101110$ we get $11,10,11,10$, so in decimal $3,2$. So, the distinct elements of $S$ are only 2. But is it correct? $\endgroup$
    – Chris
    Commented Oct 5, 2023 at 21:20
  • $\begingroup$ Isomorphic is not the right word, I meant that they have the same cardinality. I'll edit my answer. For your example, 11101110 is the binary representation of 356, so the function $\varphi$ would map 356 to the tuple (3,2,3,2) which is (11,10,11,10) in binary. $\endgroup$
    – lamontap
    Commented Oct 6, 2023 at 12:40
  • $\begingroup$ So, $\varphi$ is in fact a bijection and my example is a correct interpretation. :) $\endgroup$
    – Chris
    Commented Oct 6, 2023 at 20:09

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.