2
$\begingroup$

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?

$\endgroup$

1 Answer 1

2
$\begingroup$

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.

$\endgroup$
8
  • $\begingroup$ What exactly is x? A PRG takes only 1 input - the seed - here we see 2 inputs k & x. What is the 2nd input? $\endgroup$
    – user93353
    Dec 9, 2020 at 8:47
  • $\begingroup$ 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? $\endgroup$
    – user93353
    Dec 9, 2020 at 8:48
  • $\begingroup$ @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$). $\endgroup$
    – fgrieu
    Dec 9, 2020 at 8:55
  • $\begingroup$ 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? $\endgroup$
    – user93353
    Dec 9, 2020 at 9:01
  • 1
    $\begingroup$ I think i finally got everything. Thank you for your help. $\endgroup$
    – user93353
    Dec 9, 2020 at 9:29

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.