I am reading the "W-OTS⁺ – Shorter Signatures for Hash-Based Signature Schemes," by Andreas Hülsing, and I am stuck in understanding the success probability of an adversary, $\mathcal A$, against the one-wayness function of, $\mathcal F_n$; equation #1, page 7,

\begin{align} \operatorname{Succ}^{\operatorname{ow}}_{\mathcal F_n}(A) = \Pr [&k \stackrel$\leftarrow \mathcal K_n;\; x \stackrel$\leftarrow \{0,1\}^n,\, y \leftarrow f_k(x);\; \\ &x' \stackrel$\leftarrow \mathcal A(k, y) : y = f_k(x')] \end{align}

I read this as follows: The success of a one-way function, $\mathcal F_n$, given a random key, $k$, from the space $\mathcal K_n$, and random $x$ such that $f_k(x) = y$ is … I don't know how to read the rest of the equation and I don't know what is the probability here?


1 Answer 1


Inside the probability brackets, everything on one side of the colon describes the distributions of the variables used to define an event on the other side. In the case you described, the success probability of $A$ is the probability that $y=f_k(x')$ (which is the event) happens for $k,x',y$ sampled/generated from the left-side operations, i.e., sampling a random key $k$ and a random $x$, then computing the output $y=f_k(x)$, and finally giving $k,y$ to the adversary $A$ and getting its output. In English, that means the adversary $A$ wins if and only if it can find a preimage of $f_k(x)$ for random $k,x$, where $k$ is known to $A$.


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.