Tuesday, September 30, 2008
Peter Norvig's election FAQ
Peter Norvig wrote up an interesting analysis of the presidential candidates, attempting to be unbiased. He endorses Obama, so watch out for a bias in that direction, but it seemed pretty fair and enlightening to me.
Monday, September 29, 2008
Where did the oracle/high priest concept come from?
Many ancient cultures (and quite a few modern ones) have the notion of a high priest who represents the people. He goes through cleansing rituals and rituals where he/she takes on the identity of the people. Then he enters a place where ordinary people can't go, a sort of portal between two worlds. There he/she meets with an oracle, who in some of the oldest cultures is represented by someone of the opposite sex. They join together figuratively in the modern interpretation, literally in the older one, and thus are the two worlds reconciled. Sometimes a child is produced, a demi-god.
This evening I got to wondering where such an idea might have come from, especially considering how firmly it took hold across all of humanity. Here's what I came up with: think of very primitive, tribal, nomadic man. Some tribes would be much more powerful and wealthy than others, and being strangers with them could be very dangerous. They distrust and fear one another. The weaker tribe wants to join, or at least, get on better terms with the stronger one. They meet near each other, but keep their distance. A representative is sent from each tribe after being cleaned up and festooned with symbols of their tribe's wealth (the Hebrew high priest wore a breastplate with a jewel for each tribe of Israel). They meet in privacy in a central no-man's land, and if they take to one another, potentially produce a child which both of them have an interest in protecting. If the meeting goes well, the tribes are on good terms and everybody's happy.
I have no evidence for that wild hypothesis, but it seems plausible. Perhaps someone can point out a reference to something with a more historical basis.
This evening I got to wondering where such an idea might have come from, especially considering how firmly it took hold across all of humanity. Here's what I came up with: think of very primitive, tribal, nomadic man. Some tribes would be much more powerful and wealthy than others, and being strangers with them could be very dangerous. They distrust and fear one another. The weaker tribe wants to join, or at least, get on better terms with the stronger one. They meet near each other, but keep their distance. A representative is sent from each tribe after being cleaned up and festooned with symbols of their tribe's wealth (the Hebrew high priest wore a breastplate with a jewel for each tribe of Israel). They meet in privacy in a central no-man's land, and if they take to one another, potentially produce a child which both of them have an interest in protecting. If the meeting goes well, the tribes are on good terms and everybody's happy.
I have no evidence for that wild hypothesis, but it seems plausible. Perhaps someone can point out a reference to something with a more historical basis.
Thursday, September 25, 2008
Shuffle lines of a file
Where would I be without tab completion? Not only has it destroyed my typing ability, but today it helped me find a command I've wanted for a long time: shuf, which randomly shuffles input lines.
$ shuf /usr/share/dict/words |head -1
banefullest
$ shuf /usr/share/dict/words |head -1
banefullest
Tuesday, September 23, 2008
Why the 21st century is making you miserable
Another winner from cracked.com:
Why the 21st century is making you miserable
A lot of their stuff is just goofy fun in a very vulgar way; it's too bad that really insightful stuff like this is also vulgar enough to turn off more conservative readers.
Why the 21st century is making you miserable
A lot of their stuff is just goofy fun in a very vulgar way; it's too bad that really insightful stuff like this is also vulgar enough to turn off more conservative readers.
Brainwashing in the election
The always entertaining (and vulgar) cracked.com has an article up about the manipulation techniques being used on both sides of the election:
6 brainwashing techniques they're using on you right now
(Warning: Sports Illustrated-level racy pictures and strong language)
Monday, September 22, 2008
Wandering Star covers
I heard a really cool cover to Portishead's "Wandering Star" the other day on KSJS, and today it occurred to me to try to track it down.
Kid Beyond does a pretty cool a cappella version.
I also liked Level's version.
Then I ran across this pretty amazing song after the manner of Portishead, with a pretty cool video to go with it: Nature Boy, by Peach Stealing Monkeys. They have some other cool songs too.
I never did find the cover I was looking for, but the Peach Stealing Monkeys stuff more than made up for it.
Update: Peach Stealing Monkeys emailed me back and pointed me at another version of Kid Beyond's cover of Wandering Star. I think that's the one I heard, although I didn't notice at the time that it's all a cappella. Thanks PSM!
Kid Beyond does a pretty cool a cappella version.
I also liked Level's version.
Then I ran across this pretty amazing song after the manner of Portishead, with a pretty cool video to go with it: Nature Boy, by Peach Stealing Monkeys. They have some other cool songs too.
I never did find the cover I was looking for, but the Peach Stealing Monkeys stuff more than made up for it.
Update: Peach Stealing Monkeys emailed me back and pointed me at another version of Kid Beyond's cover of Wandering Star. I think that's the one I heard, although I didn't notice at the time that it's all a cappella. Thanks PSM!
California Prop 2 on cruelty to animals
Interesting viewpoint on raising animals for food, and a ballot measure I hadn't heard of:
A Farm Boy Reflects
A Farm Boy Reflects
Friday, September 19, 2008
How digital cash works.
Most people don't realize what amazing kinds of systems cryptographers have come up with over the years. Here's a good example of a way to create a mathematically-based digital cash system with a lot of desirable properties: you can't counterfeit coins without getting caught, we don't have to rely on a central database being up all the time, and best of all, as long as you don't try to cheat, your privacy is mathematically assured!
Secure, anonymous digital cash is real and has been implemented in the real world. In fact it's one of the things that got me into cryptography years ago. It's mathe-magical!
As others have pointed out, online, trusted third party (TTP) systems are an easy way to solve lots of security problems. Tamper-resistant devices are another "easy out". But in this case, there's a purely mathematical solution.
We have two goals: anonymous cash, and cash that prevents double-spending without an on-line authority.
Anonymity: an anonymous coin is one which you can withdraw from the bank, but which the bank can't link to you when you spend it. Sounds impossible, doesn't it? Blind signatures to the rescue. They allow the bank to sign the banknote using its private key without seeing the contents of what it's signing.
If you're scared of math, skip this part and trust me that it's possible to sign a message without seeing what it is. Otherwise, here's the math for how blind signatures work in RSA:
In ordinary RSA, e is the public exponent, d is the private exponent, and m^(ed) = m (modulo n, the signer's modulus) for all suitable messages m. A signature on m can be computed as m^d (mod n).
If I want you to sign m without knowing what it is, I pick a random r and compute r^e. I send you m*r^e and you sign it, returning (m*r^e)^d = m^d*r^(ed) = m^d*r. I divide out r and am left with m^d, the signature for m. You don't know r, so you have no idea what m is.
Okay, done with math for now.
Now, if the bank only uses d to sign, say, $1 coins, then it doesn't care what I chose for m, so it doesn't mind signing it blindly. m just becomes the serial number for the bill, and I pick it randomly each time. Now, I'm perfectly free to repeat a value of m, but the only person that hurts is me, since I'm just left with two copies of the signed bill.
When I want to spend the bill, I present m and m^d (the bill and the bank's signature for the bill) to the merchant, who verifies that it was indeed signed by the bank. He sends it to the bank while Alice waits, and they record the serial number to prevent double spending, but they have no way to link m with the blinded value m*r^e they signed earlier.
So there's anonymity. Now, to show off, we'll remove the need for the online double-spending check.
m now gets fancier. It's now a structured message having an encrypted message saying "Alice, account number: #123456789" and some other special fields. The 256-bit key k for encrypting the message is split into 2 128-bit keys k1 and k2. The special fields h1 and h2 are computed as hash(k1) and hash(k2). That is, they don't reveal what k1 and k2 are (because you can't work backward from a cryptographic hash calculation), but they let you know when you've got k1 or k2, since you can compute hash(k1) yourself and compare.
Alice creates, say, 1024 different versions of m that we'll call m0..m1023. Each has a unique k. She blinds each m with its own blinding factor b and sends them all to the bank. Each is called a "share".
Now we do what's called "cut and choose". The bank picks half of the shares at random and tells Alice to provide the blinding factors and keys for each of those. She does, and the bank verifies that each one matches the blinded values she sent earlier and that each of the keys decrypts properly, revealing Alice's name and account number.
Satisfied that she's not cheating (by putting a bogus name/account in the shares), the bank smooshes the blinded, unrevealed shares together and signs them. Alice gets back the smooshed value and the bank's signature on it, and is able to unblind each of the individual smooshed parts, leaving a completely unblinded smooshed up message and a valid signature for it.
Here's the math: assuming the bank didn't ask to see m0, m3, m4, ..., it'd give back:
((m0*b0^e) * (m3*b3^e) * (m4*b4^e)...)^d (mod n)
= m0^d * b0^ed * m3^d * b3^ed ...
As before, each b^ed = b, and she divides out the b values, leaving:
(m0*m3*m4...)^d
That is, the signature on the product of all the m values.
Still with me? Alice now has a signature on a bunch of smooshed-together shares, and the decryption keys for each share which reveal her identity. The bank's signature is valid, but the bank has never seen the unblinded value and thus won't recognize it as coming from Alice when it sees it later.
Alice goes to spend her $1 coin. She gives the signature to Bob the merchant, along with the shares m0,m3,m4... that make up the signed coin. Bob checks the signature on the smooshed up message and unsmooshes it into the separate shares. So far so good. Now, for each m, Bob picks at random and demands to see either k1 or k2 -- that is, half the key decrypting the message which would identify her. She complies, knowing that he has only half the key for any given message, so her identity is still safe. He computes the hash(k1) or hash(k2) and makes sure it matches what's in each m to make sure she isn't lying about the k values. Satisfied, he accepts the coin, and later, at his leisure, sends the day's spent coins to the bank. Alice securely deletes all the k values and goes on her way.
Now, what happens if she tries to spend the same coin twice? She gives the same signature
and m values to the other merchant, and he now demands to see one half-key or the other for each of the m values. With overwhelming probability, he asks to see the *other* half key for one of the m values the first merchant requested. Call that share m'. One merchant has one half of the key, and the other merchant has the other half. Later, when they each send their version of the spent coin to the bank, the bank will see that they're the same coin, and use the two key halves of m' to decrypt the message incriminating Alice.
Neat, huh? I simplified a lot, so if you want to get all the details, look up "Untraceable Electronic Cash" by Chaum, Fiat and Naor. Chaum actually put a fancier version of his system into practice, and I remember around 1995 downloading a Digicash "wallet" and $100 in play money to spend online in a trial run. He also had real vending machines and bus passes (iirc) in the
Netherlands, but ultimately Digicash went broke for the same reason I moved away from security: very few people actually care enough about security and privacy to pay even a little for it (and big companies like Visa have everything to lose if we have to shift to new ways of doing things).
Secure, anonymous digital cash is real and has been implemented in the real world. In fact it's one of the things that got me into cryptography years ago. It's mathe-magical!
As others have pointed out, online, trusted third party (TTP) systems are an easy way to solve lots of security problems. Tamper-resistant devices are another "easy out". But in this case, there's a purely mathematical solution.
We have two goals: anonymous cash, and cash that prevents double-spending without an on-line authority.
Anonymity: an anonymous coin is one which you can withdraw from the bank, but which the bank can't link to you when you spend it. Sounds impossible, doesn't it? Blind signatures to the rescue. They allow the bank to sign the banknote using its private key without seeing the contents of what it's signing.
If you're scared of math, skip this part and trust me that it's possible to sign a message without seeing what it is. Otherwise, here's the math for how blind signatures work in RSA:
In ordinary RSA, e is the public exponent, d is the private exponent, and m^(ed) = m (modulo n, the signer's modulus) for all suitable messages m. A signature on m can be computed as m^d (mod n).
If I want you to sign m without knowing what it is, I pick a random r and compute r^e. I send you m*r^e and you sign it, returning (m*r^e)^d = m^d*r^(ed) = m^d*r. I divide out r and am left with m^d, the signature for m. You don't know r, so you have no idea what m is.
Okay, done with math for now.
Now, if the bank only uses d to sign, say, $1 coins, then it doesn't care what I chose for m, so it doesn't mind signing it blindly. m just becomes the serial number for the bill, and I pick it randomly each time. Now, I'm perfectly free to repeat a value of m, but the only person that hurts is me, since I'm just left with two copies of the signed bill.
When I want to spend the bill, I present m and m^d (the bill and the bank's signature for the bill) to the merchant, who verifies that it was indeed signed by the bank. He sends it to the bank while Alice waits, and they record the serial number to prevent double spending, but they have no way to link m with the blinded value m*r^e they signed earlier.
So there's anonymity. Now, to show off, we'll remove the need for the online double-spending check.
m now gets fancier. It's now a structured message having an encrypted message saying "Alice, account number: #123456789" and some other special fields. The 256-bit key k for encrypting the message is split into 2 128-bit keys k1 and k2. The special fields h1 and h2 are computed as hash(k1) and hash(k2). That is, they don't reveal what k1 and k2 are (because you can't work backward from a cryptographic hash calculation), but they let you know when you've got k1 or k2, since you can compute hash(k1) yourself and compare.
Alice creates, say, 1024 different versions of m that we'll call m0..m1023. Each has a unique k. She blinds each m with its own blinding factor b and sends them all to the bank. Each is called a "share".
Now we do what's called "cut and choose". The bank picks half of the shares at random and tells Alice to provide the blinding factors and keys for each of those. She does, and the bank verifies that each one matches the blinded values she sent earlier and that each of the keys decrypts properly, revealing Alice's name and account number.
Satisfied that she's not cheating (by putting a bogus name/account in the shares), the bank smooshes the blinded, unrevealed shares together and signs them. Alice gets back the smooshed value and the bank's signature on it, and is able to unblind each of the individual smooshed parts, leaving a completely unblinded smooshed up message and a valid signature for it.
Here's the math: assuming the bank didn't ask to see m0, m3, m4, ..., it'd give back:
((m0*b0^e) * (m3*b3^e) * (m4*b4^e)...)^d (mod n)
= m0^d * b0^ed * m3^d * b3^ed ...
As before, each b^ed = b, and she divides out the b values, leaving:
(m0*m3*m4...)^d
That is, the signature on the product of all the m values.
Still with me? Alice now has a signature on a bunch of smooshed-together shares, and the decryption keys for each share which reveal her identity. The bank's signature is valid, but the bank has never seen the unblinded value and thus won't recognize it as coming from Alice when it sees it later.
Alice goes to spend her $1 coin. She gives the signature to Bob the merchant, along with the shares m0,m3,m4... that make up the signed coin. Bob checks the signature on the smooshed up message and unsmooshes it into the separate shares. So far so good. Now, for each m, Bob picks at random and demands to see either k1 or k2 -- that is, half the key decrypting the message which would identify her. She complies, knowing that he has only half the key for any given message, so her identity is still safe. He computes the hash(k1) or hash(k2) and makes sure it matches what's in each m to make sure she isn't lying about the k values. Satisfied, he accepts the coin, and later, at his leisure, sends the day's spent coins to the bank. Alice securely deletes all the k values and goes on her way.
Now, what happens if she tries to spend the same coin twice? She gives the same signature
and m values to the other merchant, and he now demands to see one half-key or the other for each of the m values. With overwhelming probability, he asks to see the *other* half key for one of the m values the first merchant requested. Call that share m'. One merchant has one half of the key, and the other merchant has the other half. Later, when they each send their version of the spent coin to the bank, the bank will see that they're the same coin, and use the two key halves of m' to decrypt the message incriminating Alice.
Neat, huh? I simplified a lot, so if you want to get all the details, look up "Untraceable Electronic Cash" by Chaum, Fiat and Naor. Chaum actually put a fancier version of his system into practice, and I remember around 1995 downloading a Digicash "wallet" and $100 in play money to spend online in a trial run. He also had real vending machines and bus passes (iirc) in the
Netherlands, but ultimately Digicash went broke for the same reason I moved away from security: very few people actually care enough about security and privacy to pay even a little for it (and big companies like Visa have everything to lose if we have to shift to new ways of doing things).
Thursday, September 18, 2008
The Moral Mind
Interesting TED talk on social psychology. I think he's right on to point out 5 traits that predict political behavior, and I think we can learn a lot if we can identify when conflict boils down to difference of opinion on those traits:
The Moral Mind
At the end he appealed to people to be less polarized, but unfortunately, I think he did it in a way that will only appeal to liberals, by pointing out eastern thinking on the topic.
Hopefully conservatives won't get distracted by that part; there are plenty of Christian and traditional American values that say the same thing. The Good Samaritan, the Sermon on the Mount, the founding fathers all encouraged people to try to accept and understand the virtues that outsiders can bring.
The Moral Mind
At the end he appealed to people to be less polarized, but unfortunately, I think he did it in a way that will only appeal to liberals, by pointing out eastern thinking on the topic.
Hopefully conservatives won't get distracted by that part; there are plenty of Christian and traditional American values that say the same thing. The Good Samaritan, the Sermon on the Mount, the founding fathers all encouraged people to try to accept and understand the virtues that outsiders can bring.
Saturday, September 13, 2008
Monday, September 08, 2008
Hallelujah! Actual journalism!
Why is it so hard to find good journalism anymore? Here newsday gives a neutral presentation of the positions Obama and McCain have taken. No BS about lapel pins or sordid affairs, just a succinct presentation of what each side has proposed to do:
Part 1: Examining key differences between Obama and McCain
Where do Obama, McCain stand on the issues? Part 2
Thank you Newsday! I even looked Newsday up on Wikipedia to see if they were all Secret Muslims or something. Nope, just respected journalists.
Part 1: Examining key differences between Obama and McCain
Where do Obama, McCain stand on the issues? Part 2
Thank you Newsday! I even looked Newsday up on Wikipedia to see if they were all Secret Muslims or something. Nope, just respected journalists.
Friday, September 05, 2008
Thursday, September 04, 2008
Northern Tool sucks
I recently ordered some stuff from northerntool.com, and they've been spamming me with ads ever since, even after I asked them to stop. I was already skeptical about the quality of their products, and this seals the deal. When will companies learn not to abuse their customers?
Wednesday, September 03, 2008
Penn Jillette on presidential candidates
I like what Penn says about small government:
Last thing we need now is a great leader
We need to break the habit of asking what government is going to do for us.
Last thing we need now is a great leader
We need to break the habit of asking what government is going to do for us.
Subscribe to:
Posts (Atom)