[Boneh-crypto-course] Finished lecture 1!
jason.orendorff at gmail.com
Mon Mar 12 19:09:21 CDT 2012
On Sun, Mar 11, 2012 at 11:43 PM, Jim Blandy <jimb at red-bean.com> wrote:
> You can say something about a construction C's security by proving that,
> if I have an algorithm A that breaks C with a given time complexity, I
> can use X as a solution for some other difficult problem with that time
> complexity (or better). So you prove that breaking C is equivalent to
> solving some other problem that is known to be hard.
> Such proofs seem like pretty rigorous statements about a construction's
> security against a specific attack.
I agree, and this approach came as a surprising insight to me.
(But see "Week 1 notes", last section, "General musings on knowing and
(BTW I have done the programming exercises for week 1 but have not
finished the problem set.)
> In the spirit of SICM, I'm trying to translate what he puts on the board
> into Scheme functions. He's got unstated parameters and free variables
> flying around all over the place. It's confusing, but I'm trying to
> persuade myself that I'm dealing with issues up front instead of being
> bewildered later.
I’ve been taking this as an opportunity to learn Clojure. So far I
really like it, and it has one feature that makes it especially
suitable to this kind of material: immutable persistent data
Also it has a nice list-comprehension macro built-in.
> For example, the probability of an event, (Pr E), is only defined
> under a given probability distribution.
Yeah - see my post about this (it is probably currently in your
moderation queue, due to technicalities—now fixed—sorry). I even talk
about how to factor Pr...
> (forall ((V D) ...) body ...) ; all body expressions are true for
> every Vs from Ds
> (exists ((V D) ...) body ...) ; all body expressions are true for
> some Vs from Ds
> (set ((V S) ...) (if COND) ... EXPR ...) ; set comprehension; S is set
> (array ((I A)) expr) ; array comprehension; A
> is sequence
> (sum ((V S) ...) (if COND) ... EXPR ...) ; sigma, with guards!
In Python, you write sigma like this:
sum(EXPR for V in S ... if COND ...)
and the same for all four of the others (they are called all, any,
set, and list).
Clojure is similar:
(reduce + (for [V S ... :when COND ...] EXPR))
Note that in both languages, the object created by the comprehension
is lazy, so the complete sequence never exists in memory all at once.
> ;; Applying = to functions! ACL to the rescue!
> (= ((random-variable-distribution (uniform (bitstrings n))) bitcount)
> (lambda (v) (/ (choose n v) (expt 2 n))))
What does ACL refer to here?
More information about the Boneh-crypto-course