[Boneh-crypto-course] Finished lecture 1!

[Jason Orendorff]

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
computability".)

(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
structures.

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?

-j