Join Log in
Score:1
zhuo chen avatar Crypto

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

cn flag
zhuo chen

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.

119
0 + 0
cn flag
Maeher
Regarding Q3: What does multiplication mean there? Are we working $\pmod {2^{n}}$ there or what?
0
Reply
zhuo chen avatar
cn flag
zhuo chen
@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.
0
Reply
cn flag
Maeher
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.
0
Reply
zhuo chen avatar
cn flag
zhuo chen
@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~
0
Reply
zhuo chen avatar
cn flag
zhuo chen
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?
0
Reply
ธงชาติไทย
Elon Musk
I sit in a Tesla and translated this thread with Ai:

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.