# Unable to understand the concept of a 1-bit PRF

In his lecture on building Block Ciphers from PRGS, Dan Boneh says this

• Let’s start by finding out if we can build PRF from a PRG?
• Let $$G:\ K \to K^2$$ be a secure PRG
• Define 1-bit PRF $$F:\ K \times \{0,1\} \to K$$ as $$F(k, x\in\{0,1\}) = G(k)[x]$$
$$\quad F$$: if $$0$$ choose $$G(k)[0]$$, if $$1$$, choose $$G(k)[1]$$

I am unable to understand what is a 1-bit PRF. A PRG takes only the seed as input. So what is the $$\{0,1\}$$ in $$F:\ K \times \{0,1\} \to K$$ - considering that $$K$$ is the key/seed of the PRG.

And what does $$G(k)[x]$$ in $$F(k, x\in\{0,1\}) = G(k)[x]$$ mean?

what is a 1-bit PRF?

That would usually be a PRF with a 1-bit output, but the rest of the text clarifies it is meant a 1-bit input.

what is the $$\{0,1\}$$ in $$F:\ K \times \{0,1\} \to K$$ ?

It is the set with two elements $$0$$ and $$1$$. This also is the set of the possible values of the second/right/normal/non-key component of the input of the PRF $$F$$.

Note: a Pseudo Random Function Family (confusingly abbreviated PRF just like a Pseudo Random Function) has two inputs (equivalently: an input consisting of an ordered pair). The first (the left component of the pair) is the key, and the second (the right one) is the normal/non-key input (which is the single input of any particular member of the Pseudo Random Function Family). The member of the Pseudo Random Function Family corresponding to key $$k$$ is often noted $$F_k$$. By that notation $$F_k(x)=F(k,x)=F((k,x))$$. Here, $$F_k:\ \{0,1\}\to K$$ (that's a particular Pseudo Random Function for a certain key $$k$$), since $$F:\ K \times \{0,1\} \to K$$ (that's the whole Pseudo Random Function Family).

what does $$G(k)[x]$$ in $$F(k, x\in\{0,1\}) = G(k)[x]$$ mean?

The PRG $$G$$ takes an input $$k$$ and produces an output $$G(k)$$ consisting of two parts of the same width as $$k$$, as apparent in $$G:\ K \to K^2$$. This is the same as $$G:\ K \to K\times K$$. That is, the output of $$G$$ is an ordered pair of bitstrings, assimilated to a bitstring twice as wide as $$k$$, that we split in two parts as wide as $$k$$, each from the same set $$K$$ as $$k$$ is from.

$$G(k)[x]$$ is the first or the second component/part of the output of $$G(k)$$, according to $$x$$ being $$0$$ or $$1$$. It's also the output of $$F$$ for input $$(k,x)$$ where $$k$$ is the PRF's key, and $$x$$ is the PRF's second/right/normal/non-key input, which is a single bit.

What exactly is $$x$$?

It's a bit. It's not an input of the PRG $$G$$. It selects among the two halves of the output of the PRG $$G$$ for input $$k$$, that is $$G(k)$$. We can think of $$[x]$$ as we'd do for [x] in a computer language with indexes.

• What exactly is x? A PRG takes only 1 input - the seed - here we see 2 inputs k & x. What is the 2nd input? Dec 9, 2020 at 8:47
• What exactly is meant by "first or the second component/part of the output of G(k)" - what exactly is meant by "component" of the output? Dec 9, 2020 at 8:48
• @user: please re-read the part of the (edited) answer where I explain the notation means $G:\ K \to K\times K$, that is the output of $G$ is an ordered pair $(u,v)$ of two bitstrings of the same width as $k$. The first or second components of the output of $G$ are $u$ or $v$. The notation $[x]$ selects the first (when $x=0$) or the second (when $x=1$).
– fgrieu
Dec 9, 2020 at 8:55
• you say that is the set of the possible values of the second/right/normal/non-key component of the input - I am unable to understand why there is a 2nd or non-key component of the input - why would a PRG take input other than a key? Dec 9, 2020 at 9:01
• I think i finally got everything. Thank you for your help. Dec 9, 2020 at 9:29