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

  • $\begingroup$ It would be more common to see $\: A^{F_k}\hspace{-0.03 in}(r) \:$ and $\: A^g\hspace{-0.02 in}(r) \:$ than $\: A_r^{F_k(.)} \:$ and $\: A_r^g \;$. $\hspace{1.49 in}$ $\endgroup$
    – user6973
    Apr 6 '15 at 18:12

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.

  • $\begingroup$ 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. $\endgroup$
    – ansatz387
    Apr 7 '15 at 16:51

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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