cdavidcash

Rogaway wrote an companion essay for his invited talk that is rather accessible: http://web.cs.ucdavis.edu/~rogaway/papers/moral-fn.pdf

If all it does is prevent length extension attacks, then there are much simpler and less risky ways to do that (i.e., MD variants).

Also, your explanation of the sponge structure omits the real difference between it and MD: It is a transform that turns a non-compressing function (f in that diagram) into a compressing function. MD, on the other hand, starts with a fixed-input-size compressing function and extends its domain.

By the way, what do you mean by "Furthermore, Keccak's Sponge design derives security by only allowing inputs to directly influence a subset of the internal state bits."? That's as true for an MD-type construction as it is for a sponge construction. In fact, it's a crucial fact that allows us to build a reduction from, say, the collision-resistance of MD[f] to the collision-resistance of f.

He is mistaken. What he meant is that there exists a finite field with exactly 256 elements, so you can "make" {0, ..., 255} into a finite field (in the sense that you can make any set of size 256 into a field by assigning + and * operations), but addition and multiplication in that field won't be the usual modular integer arithmetic. Instead, the operations will be determined by mapping the numbers to polynomials and performing modular polynomial operations and then mapping them back to numbers {0,...,255} (or determined by some other process that is morally equivalent).

Cryptographic hash functions, by contrast, are not well understood at all. They are "magic" in many ways, and aren't modeled after anything. Many more "bad things" happen in this space than in the block cipher space.

Is this a common opinion amongst practitioners? The opposite philosophy (e.g., that a random oracle is a "weaker object" than an ideal cipher) underlies some lines of work in the theoretical cryptography literature.

You might want to read the cartoon again to see why this is useless, counterproductive advice.

The suggested solution (modular squaring) already reduces to factoring. http://en.wikipedia.org/wiki/One-way_function#Modular_squari...

(And we'd use a cryptographic hash function anyway.)

Re: the crypto questions.

Not only are these just trying establish if you're in the club or not, but judging from his answers on the DH vs RSA questions (which are not-well formed to begin with), it seems like he's trying to establish if you're in the club that knows the names but has no knowledge of WTF is actually going on in crypto.

It's the most counter-intuitive thing in the world that rand() rand() is less secure than rand(); shouldn't it be twice as unpredictable?*

Under some reasonable assumptions, rand() + rand() mod 1 is twice as random! If both calls return independent samples, and at least one of the calls to rand() returns a uniform sample in [0,1], then the sum will be uniform on [0,1].

So if you assume you get at least one good shot and that the other is not specifically correlated to it, you'll be improving your randomness.

This is because Shannon entropy is basically useless when it comes to proving anything about randomized algorithms or cryptography.

During my first semester in college I took a course that used these notes. It was perhaps the most valuable course I took in college, as I subsequently became a researcher in theoretical computer science (and honestly taught myself a lot of the rest). The value in this type of course is that it introduces very green high school graduates to the type of thinking necessary to reason about proofs. The time required to build up the theory of groups/rings/modules/fields or measure-theoretic probability (is that what you want CS freshman doing?) would be wasted, as those topics are largely beside the point of the course. A sprinkling of conditional probability will at least give them something to remember in their randomized algorithms class.

This is absolutely not true. The wikipedia page for the max flow problem lists several (slower) poly-time algorithms for solving exact max flow. Most theory-101 classes cover at least Ford-Fulkerson.

Sadly, "finite time" is not what we need - they are looking for approximations that will be much rougher than the imprecision of finite numerical precision, and they want the approximation algorithm to have a good provable run time.

In general, taking theoretical approximation algorithms and shrinking the approximation factor to below some threshold where you "tell the difference" is a dead end. For instance, this algorithm's running time has a poly^{1/\epsilon} factor, so you pay a huge cost for it. It is better to think \epsilon = 1/3 or so.

Matt, I understand that you are writing primarily to your graduate students, but I also have to object to your first two points in general. I am a counterexample, as I took 12+ unnecessary math classes (getting A's in them) on my way to a successful PhD in theoretical computer science/crypto. I've found that my background in math has given me some tools and perspective that improve my research (I recognize when we are constructing a finite field in a round-about way, or when the abstraction we really want is a group action, or when Borel-Cantelli is really needed to make an argument rigorous, etc etc). I wouldn't have obtained these tools without a huge investment in time at some point.

Actually, I still find myself reading and learning unnecessary math papers most evenings as a hobby. I think it makes a huge difference.

Perhaps this is unique to mathematics, where theorem proving skills are portable. I certainly wouldn't use my situation to argue that PL grad students need to study French. But maybe the PL students should take an extra distributed systems course - and TA while they do it!

It seems like a bit much to hope to understand and verify the proof without a huge investment of time and effort. The problem is exponentially compounded if you don't already do research in theoretical computer science and have the appropriate logic background.

But! All of this has put a spotlight on a theorem that I had somehow never appreciated. It is a beautiful theorem that is well within reach of a mathematically-literate computer scientist: P = FO(LFP) over finite ordered structures. If you start reading up on this, it's immediately clear that this is interesting, because FO(LFP) say nothing a priori about computational resources in the sense that P does.

Anyway, a sufficiently curious reader can look it up as theorem 4.10 in the following text:

http://www.amazon.com/Descriptive-Complexity-Texts-Computer-...

That book is pretty light on the basics of logic. I used this book:

http://www.amazon.com/Mathematical-Logic-Undergraduate-Texts...

Ah, that is not how those "barriers" work. Roughly, the relativization barrier goes like this: Say you have a proof that P!=NP. Does it also prove that P^A != NP^A for any oracle A? If it does, then the proof is flawed, because there <i>does</i> exist an oracle A such that P^A = NP^A!

Such proofs are said to relativize -- i.e., they are still valid relative to any oracle.

"only certain proof strategies" is technically correct, but its closer to "essentially every proof strategy we can conceive of".

And besides, the question is over the entire proof strategy and not the specific techniques involved. It seems plausible that one could give a relativizing proof using some method of calculation from statistical mechanics, for example.

The Hacker News community has a strange and sad relationship with actual math, that is, math as mathematicians define it. Math formalizable in ZFC and not arguments of A/B test effectiveness and VC funding.

>You don't know how much money is in either envelope, but it needn't have been selected randomly.

This is exactly wrong, at least in the mathematical formalization of this problem that everyone is assuming. The definition of "don't know how much money" must be taken to be "has a uniform distribution".

If you want to use some reasoning that treats the amount of money as an "unknown in an equation" then you are instead giving a solution that differs for each possible value of the money and does not capture the random choices we are trying to model.

By the way, no one said that uniform distributions on infinite sets don't exist. He said "infinite series (the list of possible monies)", a slightly mis-used term that clearly excludes [0,1], your chosen example.

You might find the blog post linked below encouraging. It was written by a professor at UIUC.

http://3dpancakes.typepad.com/ernie/2005/03/re_phd_with_low....

My advice is think about what you really want to do, and why you want to do it. If you want to do good research then it makes sense to apply to highly ranked PhD programs because they will give you a support system to help you learn. If you just want to own a PhD from a specific school, then it will be harder to get in, harder to finish, and less meaningful when you're done.

My advice for your specific goal is to somehow get involved with a professor's research. Preferably someone who will be recognized by admission committees. Their letter will help a lot. This might involve getting an MS at the highest-ranked school you can get admitted to. Sadly, those programs are not usually funded (as opposed to American PhD programs).