WingNews logo WingNews GitHub [2]

cdavidcash's comments

cdavidcash | 13 years ago | on: NIST Selects Winner of Secure Hash Algorithm (SHA-3) Competition

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.

cdavidcash | 14 years ago | on: Finite Field Arithmetic and Reed-Solomon Coding

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

cdavidcash | 14 years ago | on: Don't use bcrypt

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.

cdavidcash | 15 years ago | on: 25 Questions to Ask During an Information Security Interview

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.

cdavidcash | 15 years ago | on: Understanding "randomness"

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.

cdavidcash | 15 years ago | on: Understanding "randomness"

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

cdavidcash | 15 years ago | on: Mathematics for computer science (Fall 2010, MIT)

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.

cdavidcash | 15 years ago | on: First improvement of fundamental algorithm in 10 years

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.

cdavidcash | 15 years ago | on: Easy Ways to Fail a Ph.D.

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!

cdavidcash | 15 years ago | on: Issues in the Proof that P ≠ NP

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

cdavidcash | 15 years ago | on: P ≠ NP

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.

cdavidcash | 15 years ago | on: P ≠ NP

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

cdavidcash | 15 years ago | on: Two Envelopes Problem

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.

cdavidcash | 15 years ago | on: Two Envelopes Problem

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

cdavidcash | 15 years ago | on: Ask HN: What's your most interesting life goal currently?

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

page 1