Score:1

# Is PRF Xored (or multiplied) with a random number still a secure PRF?

I've know that a PRF Xored with its key is not a secure PRF. Then I wonder that what if the Xored (or multiplied) item is another random number. The formal expression is as belows:

Let $$F_k(x):\{0,1\}^n \times \{0,1\}^n \rightarrow \{0,1\}^n$$ be a PRF.

"$$<<$$" operation indicates left rotation, "$$\cdot$$" operation indicates the binary multiplication module $$2^n$$ where an $$n$$-bit string is interpreted as number in $$Z_{2^n}$$ and "$$(a, b)$$" denotes the greatest common divisor of $$a$$ and $$b$$.

Q1. Define $$F'_{k_1,k_2}(x) = F_{k_1}(x) \oplus k_2$$, where $$k_2$$ is uniformly choosen from $$\{0,1\}^n$$. Then is $$F'_{k_1,k_2}(x)$$ a PRF?

Q2. Define $$F''_{k_1,k_2}(x) = (F_{k_1}(x)<<1) \oplus k_2$$, where $$k_2$$ is uniformly choosen from $$\{0,1\}$$. Then is $$F''_{k_1,k_2}(x)$$ a PRF?

Q3. Define $$F'''_{k_1,k_2}(x) = k_2 \cdot F_{k_1}(x)$$, where $$k_2$$ is uniformly choosen from $$\{0,1\}^{n-1}||1$$, i.e. $$(k_2,2^n) = 1$$. Then is $$F'''_{k_1,k_2}(x)$$ a PRF?

I think that they are PRFs, but i'm confused how to formally prove it. $$k_2$$ in Q.3 is required to be an odd number since if it's even then $$F'''$$ returns an even number and can't be a PRF.

Regarding Q3: What does multiplication mean there? Are we working $\pmod {2^{n}}$ there or what?
@Maeher Yes the multiplication indicates the binary multiplication $\pmod {2^n}$ and is working in $Z_{2^n}$. Additionally, $k_2$ and $F_{k_1}(x)$ are interpreted as numbers in $Z_{2^n}$. Sorry for that the description of multiplication is not very clear because of typography, and I've edited my typography.
A sufficient condition would be that multiplication $\bmod 2^n$ with an odd constant is a permutation over $\mathbb{Z}_{2^n}$. Intuitively I'd say that's true, but I can't think of a formal argument off the top of my head right now.
@Maeher Yes I also think so, and I think this is the point to prove that $F'''$ is a PRF. Number Theory-related knowledge maybe helpful. I'll try it. If I succeed I'll notify you. Thanks for your help~
If $A=\{a_1,a_2,\cdots, a_m\}$ is a permutation, then $K=\{k \cdot a_1,k \cdot a_2,\cdots, k \cdot a_m\}$ is also a permutation over $Z_{2^n}$, where $k$ is odd and $m \leq 2^n$. Proof. Assume $K$ is not a permutation and $k \cdot a_i \equiv k \cdot a_j \pmod {2^n}$， where $i,j \in [1, m]$. Then we have $a_i \equiv a_j \pmod {2^n}$ since $(k, 2^n)=1$, which contradicts the assumption. Am I right? And Is the subsequent proof process proving Q3 similar to Q1?