# Tag Info

## New answers tagged provable-security

0

Actually, I think I found the answer to my question while writing it, but I'll post it anyway, since it might be interesting to others: Yes, OFB mode is secure even with 8-bit feedback, at least as long as IVs are chosen randomly. Specifically, in the paper "New proof for old modes" (IACR Cryptology ePrint Archive, 2008), which I've cited earlier here, ...

3

Ok, here's a version that definitely works. Three points: If we know $S_2$ is close to $1/2$, then the statement that $S_1$ and $S_2$ are close is equivalent to saying that $S_1$ is close to $1/2$. So I'll prove the latter version. The way to deal with the edge cases, I think, is to demand Pr$[S_2|F] = 1/2$. This is the case whenever the game (not the ...

3

However I think that the requirement on $\Pr[F]$ is way too strong: one can prove security with much more frequent faults. Maybe this short paper by Alexander W. Dent could be of interest: A Note On Game-Hopping Proofs? In this paper he introduces a fourth kind of game hop, namely transitions based on large failure events, which seems to be exactly what ...

5

As fgrieu notes in the comments, the protocol might not even work reliably in the absence of adversaries: if the tag fails to receive the reader's reply of "True", the keys will get out of sync. (If that happens, the tag will just retry the next exchange with the old key, so this could be fixed by having the reader remember one more "subkey". But the ...

5

My experience of such proofs is that often you're proving a much stronger statement: in any execution of Game i+1, either everything is distributed identically to Game i or else F must have happened. In other words, the conditional distribution of game i+1 conditioned on F not happening is identical to the distribution of Game i. For example, one of ...

1

Your observations are basically correct. Informally it is as follows: For a uniform PPT algorithm think of a fixed Turing machine that has access to some random tape and the output of the algorithm is a random variable. For non-uniform algorithms it is best to think of a family of circuits indexed by the length of the input (so for every input length the ...

Top 50 recent answers are included