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…
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…
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…
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…
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…
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…
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…
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…
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…
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,…
"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…
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…
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…
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…
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…
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…
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…
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…
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…
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…
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…
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…
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,…
"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…
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…
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…