<p>If you're totally lost, you might not have the needed background to get much use out of the paper.  The paper draws on many concepts and foundational ideas from theoretical cryptography (including how to formalize notions of security for various cryptographic tasks), and it assumes familiarity with those ideas.  If the definition looks confusing, it's probably because you don't have that familiarity; the paper's intended audience was cryptographers who already have that familiarity.</p>

<p>You might want to spend a few weeks studying theoretical cryptography (foundations of cryptography), e.g., from Lindell-Katz, the Goldreich book, and/or many lecture notes online on the foundations of cryptography.  You'll find that this kind of definition is routine, and studying that material will prepare you to be able to understand this material and work through the definitions on your own.</p>

CC BY-SA 3.0
2015-04-07T16:51:37.590Z
Thanks, I was definitely looking for references. I didn't know what field I was looking at, since I don't really have any experience in this.
ansatz387
CC BY-SA 3.0
2015-04-06T06:06:16.823Z
2015-04-06T06:06:16.823Z
D.W.
<p>In Provably Secure Steganography by Hopper, et al, we  have the following definition</p>

<p>Cryptographic notions</p>

<p>Let $F:\{0,1\}^k \times \{0,1\}^L \rightarrow \{0,1\}^l$ denote a family of functions. Let $A$ be an oracle probabilistic adversary:</p>

<p>Define the $prf$-advantage of $A$ over $F$ as</p>

<p>$$Adv^{prf}_F(A)= | Pr_{K \leftarrow U(k), r\leftarrow \{0,1\}^*}[A_r^{F_k(.)}=1]- Pr_{g \leftarrow U(L,l), r\leftarrow \{0,1\}^*}[A_r^{g}=1] |.$$</p>

<p>where $r$ is the string of random bits used by adversary $A$. Define the insecurity of $F$ as</p>

<p>$$InSec^{prf}_{F}(t,q) = max_{A\in \mathcal{A}(t,q)} \{ Adv_F^{prf}(A)\}$$</p>

<p>where $U(k)$ is a uniform distribution over $k$ bits, $U(L,l)$ is a uniform distribution on functions from $\{0,1\}^L$ to $\{0,1\}^l$, and $F_K$ is a function $F_K:\{0,1\}^k\times\{0,1\}^L\to\{0,1\}^\ell$. But honestly, I don't know how I'm supposed to understand or parse the definition. Intuitively, I get the adversary $A$ is outputting $1$ if it decides that $F_K$ is not sufficiently different from a sample $r$ drawn from the channel distribution. But can someone walk me through, like I'm an idiot, as to what role each part of the definition plays in the overall mechanism of prf-advantage?</p>

<p>Link to paper: <a href="https://www.cs.cmu.edu/~biglou/PSS.pdf" rel="nofollow">https://www.cs.cmu.edu/~biglou/PSS.pdf</a></p>

<cr.crypto-security>
Question on cryptographic advantage
ansatz387
# Question on cryptographic advantage

(Asked by: username_0 on 2015-04-06)

In Provably Secure Steganography by Hopper, et al, we have the following definition

Cryptographic notions

Let $F:\{0,1\}^k \times \{0,1\}^L \rightarrow \{0,1\}^l$ denote a family of functions. Let $A$ be an oracle probabilistic adversary:

Define the $prf$-advantage of $A$ over $F$ as

$$Adv^{prf}\_F(A)= | Pr\_{K \leftarrow U(k), r\leftarrow \{0,1\}^\*}[A\_r^{F\_k(.)}=1]- Pr\_{g \leftarrow U(L,l), r\leftarrow \{0,1\}^\*}[A\_r^{g}=1] |.$$

where $r$ is the string of random bits used by adversary $A$. Define the insecurity of $F$ as

$$InSec^{prf}\_{F}(t,q) = max\_{A\in \mathcal{A}(t,q)} \{ Adv\_F^{prf}(A)\}$$

where $U(k)$ is a uniform distribution over $k$ bits, $U(L,l)$ is a uniform distribution on functions from $\{0,1\}^L$ to $\{0,1\}^l$, and $F\_K$ is a function $F\_K:\{0,1\}^k\times\{0,1\}^L\to\{0,1\}^\ell$. But honestly, I don't know how I'm supposed to understand or parse the definition. Intuitively, I get the adversary $A$ is outputting $1$ if it decides that $F\_K$ is not sufficiently different from a sample $r$ drawn from the channel distribution. But can someone walk me through, like I'm an idiot, as to what role each part of the definition plays in the overall mechanism of prf-advantage?

Link to paper: <https://www.cs.cmu.edu/~biglou/PSS.pdf>

**Tags:** cr.crypto-security

---

## 1 answers

### Answer by username_1 on 2015-04-06. Score: 2 | Accepted answer

If you're totally lost, you might not have the needed background to get much use out of the paper. The paper draws on many concepts and foundational ideas from theoretical cryptography (including how to formalize notions of security for various cryptographic tasks), and it assumes familiarity with those ideas. If the definition looks confusing, it's probably because you don't have that familiarity; the paper's intended audience was cryptographers who already have that familiarity.

You might want to spend a few weeks studying theoretical cryptography (foundations of cryptography), e.g., from Lindell-Katz, the Goldreich book, and/or many lecture notes online on the foundations of cryptography. You'll find that this kind of definition is routine, and studying that material will prepare you to be able to understand this material and work through the definitions on your own.

> **Comments:**
> **username_0**: Thanks, I was definitely looking for references. I didn't know what field I was looking at, since I don't really have any experience in this.  

---

