New answers tagged security-definition
13
You are (mostly) right. Reductions are an algorithmic notion — $P$ reduces to $Q$ if the ability to solve $Q$ allows you to solve $P$. There are many ways to formalize this, but the one that you describe (using $Q$ as a subroutine/oracle to solve $P$) is the most common in cryptography (it is known as a Turing reduction).
I will notate this $P \leq Q$.
...
5
What is meant by "$r$ may be chosen in a way dependent on $z$"?
An hypothetical algorithm $\mathcal A_2$ breaking the strong RSA assumption has input¹ $(n,z)$ with $n$ generated by the RSA key generation procedure, and outputs² $(r,y)$ such that $y^r\equiv z\pmod n$, with the only other constraint on $r$ that $r>1$. Contrast with an hypothetical ...
1
"Short" and "long" are relative terms. If I secretly make 128 coin flips and write down the results, that sounds like a lot of coin flips, doesn't it? There's $2^{128} > 10^{38}$ combinations I could get, a number bigger than 1 with 38 zeroes after it, so you have no hope of guessing what results I got.
Yet that unguessable result fits in $128 ÷ 8 = 16$ ...
Top 50 recent answers are included
