# On the construction and notation of a certain OWF

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?

Thanks!

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.
• 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? Commented Oct 5, 2023 at 21:20
• 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. Commented Oct 6, 2023 at 12:40
• So, $\varphi$ is in fact a bijection and my example is a correct interpretation. :) Commented Oct 6, 2023 at 20:09