[Boneh-crypto-course] Are we keeping up?

[Jim Blandy]

I just finished the week three problem set; it took me two tries. I
was completely unable to figure out the last one, but guessed my way
through it, and read the explanation carefully.

So, I've watched up through 6.6. I haven't tried any of the
programming assignments yet. I'd love to be able to pick up the pace a
bit so I'd have time for that. What degree of effort is involved in
them? It's hard to imagine a programming assignment that doesn't take
quite a bit longer than the quizzes.

I've been translating stuff into Haskell, which works nicely:

The adversary in a MAC advantage computation gets to take a series of
turns, offering as many queries as it likes, and prior results can
influence future results. So I modeled that as an algebraic type that
has a continuation of sorts in there:

data (Bits x, Bits t) => AdvantageMACAdversary x t =
   Query ([x], (t -> AdvantageMACAdversary x t)) |
   Guess ([x], t)

advantageMAC :: (Bits x, Bits t) => AdvantageMACAdversary x t -> MAC k
[x] t -> Double
advantageMAC a (s, v) = pr (\u ->
                           let k = chooseChallengerKey u
                               game (Query (m, next)) used | not (elem m used) =
                                                              game
(next (s k m)) (m : used)
                               game (Guess (m, t)) _ = v k m t
                           in game a [])

-- cascadeExtensionAttacker f fpad is an adversary that can break nmac
(f, fpad)'s
-- cascade after making only one query.
cascadeExtensionAttacker :: (Bits k, Bits x) => (k -> x -> k) ->
AdvantageMACAdversary x k
cascadeExtensionAttacker f = Query ([1729],
                                   \t -> Guess ([1729, 42], f t 42))

The type checker doesn't produce very legible error messages, but it's
caught many, many typos.

> (I've been surprised to hear that again and again, the systems with
> really strong security properties are not used in practice, apparently
> for performance reasons. Provably secure ciphers are not used; instead
> we use AES which we think is probably secure. We don't want secure
> systems: we want secure-enough systems.)

The only such thing I've seen so far is the compression function:

provable p u v = \accum x -> (u^accum * v^x) `mod` p

Is that what you have in mind? You don't mean one-time pads, do you?