Slashback: Passports, Microscopes, IQ Points

Slashback tonight with updates and clarifications on recent Slashdot stories (and story arcs), including a downright Operatic end to Jon S. von Tetzchner's cross-oceanic attempt (or was that just in fun?), the status of post-death email privacy, minimizing the dangers of RFID passports, and more - read on for the details.

Actually, it's taking tests that reduces IQ. The guys at Mind Hacks have dissected the widely reported story that 'email destroys the mind faster than marijuana' [Posted on Slashdot a few days ago -- T.] and found that it is more spin than science. The results show simply that people do worse at IQ tests when distracted, although Hewlett-Packard are not releasing details of the experiment, so others cannot even evaluate if the research is sound. The use of psychobabble for marketing marches on.

One day this will all be commemorated as ... an opera. GreyPoopon writes "It looks like Jon's attempt at swimming the Atlantic has ended in early failure. Taking the blame once again is is PR Manager, Eskil Sivertsen. The raft he was using was somehow punctured this morning, and Jon had to abondon his trek to perform a heroic rescue. Perhaps someone should take on the task of sending our downtrodden adventurer a cup of Mom's hot chocolate."

PCP theorem simplified, still way over my head. Stridar writes "Sanjeev Arora's proof of the PCP theorem was a great acheivement. This theorem, a reduction of NP to PCP, allowed for many striking results on the difficulty of finding approximate solutions to NP-Hard problems. However, his original proof is long and technical, focusing on the arithmetization of booelan formulas. It has long been an open problem to simplify this result. Now Irit Dinur , a mathematician at the Hebrew University, has given a purely combinatorial proof of the PCP theorem, in her exciting paper "The PCP Theorem by Gap Amplification" ."

I think several other things end at death, too. microbee writes "The Register reports that Yahoo has complied with a court order to give a dead soldier's email account to his parents. It's not clear to me from the news whether they got direct access to the actual mail box, or just hard copy of those emails. If the former, it's a bit funny to read "the family complain they have only got emails received by Justin, not those he wrote." People have to wonder whether their privacy ends at death."

Haven't they ever seen The Killing Fields? valdean writes "Following up on past Slashdot stories, Wired News reports that the State Department is now considering adding a password to the new RFID passports, in response to 'criticism from computer security professionals and civil libertarians.' According to the article, 'The data... would be locked and unavailable to any reader that doesn't know a secret key or password to unlock the data. To obtain the key, a passport officer would need to physically scan the machine-readable text that's printed on the passport page beneath the photo... The reader would then hash the data to create a unique key that could be used to authenticate the reader and unlock the data on the RFID chip.'"

Anything with LEDs in it makes me happy. HunterD writes "Apparently a company called DigitalBlue purchased the rights to the Intel Play series, which included the Intel QX3 microscope. Well, DigitalBlue has released an upgrade called the QX5 that features an Ultrabright LED, a better camera, and a number of other upgrades."

Comments

Mac Drivers!!!!eleven!!!1!!

[BandwidthHog]

This page linked from the blog entry has Mac OS X downloads ($12 shareware) for both the original Intel scope and the new QX5. I have neither, so can't test it, but it's suddenly an appealing way to blow a hundred bucks!

They list the capabilities thusly:

miXscope QX5 is a Mac OS X application written specifically for the USB QX5 Computer Microscope. The software allows you to capture images, create time-lapse movies, add a text comment, add a time stamp, add an image overlay, make a measurement, apply realtime frame averaging, or add a special effect.

Of course, I just spotted the fact that Digital Blue are also the fine folks who brought us the American Idol Digital Camcorder, so that does temper my enthusiasm for handing them cash just a wee bit. But still...

The PCP Theorem

[cpeikert]

The PCP theorem is a beautiful piece of computer science and mathematics. What's it good for? Well, for starters:

• One can use it to show that not only are some problems very hard to get exact answers to, they are very hard to even get approximate answers to! In the most extreme case, it's hard to tell whether a graph has an enormous clique (taking up almost all the vertices), or just a very small one.
• PCPs can be used to build very low-communication zero-knowledge proofs. So you can prove a mathematical statement to someone, using much less communication than it takes to even write down that statement, and giving her no idea why the statement is true, even though she will be absolutely convinced that it really is true!
• PCPs can also be used to write down a (long) proof of a mathematical theorem, so that to check the theorem only requires you to look in a few random places. If the theorem is false, you'll detect it, otherwise you'll be convinced that it's true. It's as if there was a huge book of mathematics, and you opened to a random page, read a few characters, and said, "yep, it's definitely all true."

In short: amazing!

Re:The PCP Theorem

[Nitish]

Well, you don't need to feel bad about not understanding the PCP theorem. It's a difficult concept to grasp. For example, you could be an extremely intelligent and motivated high school student who can't "get it" even if you try, because you just haven't studied all the pre-requisite material you need. Though perhaps you can't go to the PCP theorem from where you are now, you might be able to understand it once you have all the background knowledge.

The original poster described the PCP theorem well, but it might not make a lot of sense to people who haven't studied algorithms or complexity theory. This might help:
A lot of problems people want to solve in practice are "optimization" problems. That is, given a problem, we want to find the optimum (minimum or maximum, as the case may be) solution. For example, if you have to travel to several cities, you might want to know the cost of the cheapest tour that visits all of them. Or you might want to know what the most efficient way of scheduling jobs on a machine is. These (and several other) problems, are what we call NP-Hard. That has a technical meaning, but in short, it takes a *really* long time (far more than is practical) to compute the best solutions for these problems. And so if you wanted a solution, instead of spending forever to find the best tour, you might settle for a tour that cost only 1% more, if you could find it quickly. Algorithms which do this are called approximation algorithms; they don't always find the best solution, but they approximate it - the solution they find is nearly as good... perhaps just a little more expensive or less inefficient.

Approximation algorithms are useful because people are often satisfied with solutions that are "good enough", even if not perfect. So for a hard problem, it's worth spending time trying to find a good approximate solution.

Enter the PCP theorem! You can use it to show that some problems can't even be approximately solved in a reasonable amount of time, and that's what the original poster was talking about.

Besides this, the theorem is important and loved because not only is it useful, it's non-obvious and beautiful

The Mind Hacks analysis

[wka]

Sine it does not seem to be posted above, here is a link to the Mind Hacks analysis of the IQ study.

Comment removed

[account_deleted]

Comment removed based on user account deletion

Linux QX3 drivers

[jonsmirl]

The CPiA webcam driver supports the QX3 on Linux.
CPiA webcam driver for Linux
Just turn on CONFIG_VIDEO_CPIA=m when you build your kernel. You can even use /proc to turn the microscope lights on and off.

CPiA is not made any more. Maybe the QX5 uses a similar webcam chip.

Old slashdot story about the QX3

Re:MJ?

[flink]

You left out the biggest one: seized assets of drug dealers. When someone gets convicted, federal laws allow all their drug-related assets (cars, bank accounts, houses, bling, etc.) to go to the state. This is a huge revenue stream for local law enforcement agencies and is probably the single largest unspoken reason why you won't see legalization anytime soon.

Re:Yes a novel solution...

[swillden]

Or how about just NOT using RFID in passports and instead using tried and tested chips or strips?

Several reasons:

• Increased security. The main reason for going to a chip of some sort is to both make the passports harder to forge and to add biometrics in order to better authenticate the holder. Biometric templates are often large, and they also need to be cryptographically signed by the issuer. That means that tens of kilobytes of data storage are required. Note that some magnetic and optical stripes could partially fulfill this requirement, but aren't as secure as a chip.
• Reliability/Durability. A contact-type chip is problematic for a passport because of the booklet form factor. Where do you put the contact plate? At the very least you'd have to make part of the booklet out of rigid plastic so that the contact plate would slot into the right place. Non-standard readers would have to be designed and built, also. Existing smart card readers expect a card form factor, obviously.
• Convenience. Contactless is quicker and easier to use. Not much, but enough to matter when you're trying to move large numbers of people through quickly. The immigration agent does not have to spend time putting the correct corner of the passport into the correct location in the correct way.
• Speed. Strange as it may seem, it's a fact that off-the-shelf RF technology achieves *much* higher data rates than contact smart card technology. Contact chips communicate at between 9.9bps and 115kbps, contactless chips talk at either 400kbps or 800kbps. In practice, contact chips rarely run at over 9.9kbps, which means that data moves at less then 1KBps. It's expected that many of these passports will store 20-40KB of data, so the high data rate will be important.

The first plan by the state dept. was terrible; they took absolutely no precautions to protect the passport holder's privacy. I wrote to them to complain. The latest announcement, however, shows that they have listened and fixed all of the problems.

They've made three changes to the plans:

1. The chip will not divulge any data without an appropriate cryptographic authentication. The key used to perform the authentication is derived from data printed inside the passport.
2. All communications with the chip will be encrypted using a session key so that no one can eavesdrop when the passport is being read.
3. The passport cover will incorporate RF shielding, so that when the passport is closed the chip cannot be activated. This is to prevent an attacker from being able to identify who is carrying a passport by scanning them, as well as a few more difficult attacks.

With these changes, there are no additional security risk as long as passport holders are careful to keep their passports closed when not being checked.

The other concern that will no doubt be raised by some slashdotters is whether or not someone who gets hold of your passport can get your biometric data. They can, but it doesn't do any good. The data stored is in the form of a pre-processed template, not an image. It's not possible to reconstruct the original fingerprint/iris/whatever image because the template construction process discards data. It is possible to construct a *different* image which will match when compared to the template, but the constructed image will not really look like the person's biometric.

That said, I think there are legitimate privacy arguments against the use of biometrics. The contactless smart card chip, however, poses no security risks to the passport holder, and offers improves security and convenience -- not for the holder, but for the government who issued the passport.

Re:Sol, if you're scanning the passport

[swillden]

If you're physically scanning the passport, you no longer have any of the advantages of RFID over, say, magstripe or 2D barcodes.

Yes, you do, actually. Two major advantages. The first is that the chip can authenticate itself cryptographically, making forgery vastly more difficult. The second is data volumes. You could hold enough data on a magnetic stripe (though it would have to be both much larger and far more dense -- and correspondingly less reliable -- than a credit card stripe) but you'd have a hard time getting a 2D barcode that stores 40KB of data. Also, the 2D barcode can't be updated without reprinting, whereas the chip can have data added at any time, including dynamic data, like electronic passport stamps.

A magnetic stripe almost does the job, but is less secure. A 2D barcode is simply inadequate.

The Opera Swim...

[mute47]

The day after Jon S. von Tetzchner made the anouncement, one of the icelandic papers (http://www.mbl.is/) had a short interview with his mother. She was apparently stunned about his thoughtfulness, coming to visit her, but said that he could just drive as she has lived in Norway for over 17 years...