cdavidcash

6 ms·

1.
by cdavidcash 11y ago
Rogaway wrote an companion essay for his invited talk that is rather accessible: http://web.cs.ucdavis.edu/~rogaway/papers/moral-fn.pdf
2.
by cdavidcash 14y ago
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 transfo
3.
by cdavidcash 14y ago
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 * operatio
4.
by cdavidcash 15y ago
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 opin
5.
by cdavidcash 15y ago
You might want to read the cartoon again to see why this is useless, counterproductive advice.
6.
by cdavidcash 16y ago
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.)
7.
by cdavidcash 16y ago
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 yo
8.
by cdavidcash 16y ago
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 retu
9.
by cdavidcash 16y ago
This is because Shannon entropy is basically useless when it comes to proving anything about randomized algorithms or cryptography.
10.
by cdavidcash 16y ago
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 o
11.
by cdavidcash 16y ago
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.
12.
by cdavidcash 16y ago
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 gene
13.
by cdavidcash 16y ago
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
14.
by cdavidcash 16y ago
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 appropr
15.
by cdavidcash 16y ago
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 &#
16.
by cdavidcash 16y ago
"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
17.
by cdavidcash 16y ago
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.
18.
by cdavidcash 16y ago
>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 kno
19.
by cdavidcash 16y ago
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.