# Tag Info

## New answers tagged provable-security

3

In general this is not the case. Consider a PRF F which ignores the first bit of the key. Then you can distinguish F'(k,.)=F(.,k) from a random function (and thus break its security as a PRF) by querying it on inputs x and x', where with x' we denote x with the first bit flipped. Note that the outputs of F'(k,.) will collide on inputs x and x' as ...

2

You have just to look at the signing/verification relation. Just write it as $$m\cdot s \equiv r\cdot \alpha + k \bmod (p-1)$$ And the verification relation should be $$g^{s\cdot m}\stackrel{?}{\equiv} y^r\cdot r \bmod p$$ where $y=g^\alpha$ is the public key and you eavesdrop a signature $(r,s)$ for $m$. Obseve that you can take any multiplicative ...

1

Not necessarily. For example, if there is a public-coin collision-resistant hash family then there is a (statistical) zero-knowledge argument system (with negligible soundness error) for NP that uses a constant number of rounds and has a public-coin verifier. However, in the random oracle model, constant-round public-coin computational zero-knowledge ...

1

As correctly pointed out by Ricky Demer it is not necessarily true. However, this implication does not hold for very specific cases. In the case of random oracle gates the existence of the RO changes the functionality of the "scheme", since with RO there are RO-Gates and without there aren't. In most cases the existence of the RO does not affect the ...

1

You always need to have in mind that $A$ is a hypothetical algorithm, since our goal in the reduction is to contradict the existence of such an efficient $A$. Now to your concrete security framework: Here, you are not satisfied by the fact that a hypothetical poly-time $A$ implies a poly-time reduction $A'$, but your aim is that the reduction does not take ...

4

The equation $t'=t+n\cdot t_c$ is an estimation to put an upper limit on $t'$. It might be possible that an attacker $A'$ can use a different, more efficient algorithm. But since the attack will work with using $A$, there exists an attacker $A'$ with at most $t'$. This means it's actually not an equation, but an inequality $t' \leq t + n \cdot t_c$. And then ...

5

Intuition The intuition behind the proof is that a valid ciphertext is correctly generated and, thus, an adversary should query to the random oracles to generate random strings in the ciphertext. In addition, notice that the hash value on an unqueried string is undetermined (to the adversary) in the random oracle model. Therefore, the chance to construct a ...

3

As @xagawa mentioned in his comment, it depends on what you mean by "controled". In the case of using a programmable random oracle, yes, the reduction (in particular the simulation of the challenger of the real game) decides about what to return as answer to an oracle query. Thereby, the reduction has to guarantee that the "programmed" answers are ...

2

Firstly, I should clarify: I am just referring to the standard definition of a random oracle. There are other scenario's (better discussed in DrL's answer), but these tend to be explicitly referred to. That is, if you have a standard 'random oracle', this answer should hold. On the other hand, if you have a different type of oracle, this won't hold. A ...

Top 50 recent answers are included