11,865 karma · joined March 13, 2008
Research: https://www.cs.princeton.edu/~arvindn/
The rest of my thesis is (almost literally) a concatenation of several of my papers, most of which I've covered on my blog; a quick list is here: http://randomwalker.info/publications/
Some academic with too much time on his hands wrote an entire Ph.D thesis on that very idea [hint: me :-)] http://33bits.org/about/
1. You stop short of actually identifying the thief; is this primarily due to ethical concerns or the paucity of off-network information? Could you speculate on whether non-public information available to law enforcement would be enough to resolve the thief's identity?
2. How easy is it for users to protect themselves to foil your analysis techniques? Could client software automate some of these obfuscation mechanisms?
Incidentally, you cite my Netflix work, but my work on deanonymizing social networks based on topology (http://33bits.org/2011/03/09/link-prediction-by-de-anonymiza..., http://33bits.org/2009/03/19/de-anonymizing-social-networks/) might be more relevant, and some of the techniques potentially applicable to deanonymization of the bitcoin transaction network if and when it grows larger and gains a more substantial resemblance to the network of real-life relationships.
It's been on hiatus for a while.. maybe this would be a good time to restart it.
There's one and only one way to make this work with an already existing social graph: show the user a clustered view of their friends. To see examples, do an image search for 'vizster'. http://vis.stanford.edu/papers/vizster
A standard way to avoid this is by making the image URL http://lilqr.com/qr?rand=[nonce], where you'd generate the nonce randomly on each page load. You can ignore it on the server of course.
$50k/paper is about right. I was surprised to find that even my colleagues didn't know this figure. If only more people were aware of it, perhaps they'd take things more seriously.
The feeling of powerlessness as an individual trapped in the system is only exacerbated by the apparent callousness of those around you.
In the last several years there's been maybe half a dozen times that I failed to find a computer science paper online. I'd estimate that less than 1% of papers in the top conferences are unavailable freely online.
My field (computer science) and a few others at least don't have the problem of paywalls. Authors always make their works available; a few publishers have relaxed their copyright policies and others have an implicit promise not to sue. It's not ideal, but it's not too bad.
Public communication, however, remains quite bad. It is very unfortunate that in the current system, researchers have no incentive to communicate with the public or do anything except rack up publications and citations.
I write a blog about my research (http://33bits.org) and I've been pleasantly surprised by the level of public interest. In my ideal world, research grants would come with some strings attached to get scientists to fulfill some of their social responsibility.
In related news, if you're in the Bay Area there's an Open Science event next week with Michael Nielsen that I'm really excited about. http://blogs.plos.org/everyone/2011/06/15/%E2%80%9Cwhy-the-n...
[1] Is it irony? The word is so overused I can't even tell anymore.
Some quotes:
OpenID is the worst possible "solution" I have ever seen in my entire life to a problem that most people don't really have.
A nerd will wrinkle up his nose at these [non-OpenID] solutions and grumble about the "security vulnerabilities" (and they'll be right, technically) but the truth is that these solutions get people into the site and doing what they want and no one really cares about security anyways.
Let's think about that one for a second. I find this rather typical of Facebook's attitude in general—a monomaniacal focus on increasing engagement or whatever metrics, a complete disregard for externalities and an arrogant rejection of any sort of social responsibility. This is what makes them so successful as well as so dangerous to the rest of the ecosystem.
But somehow they haven't figured out that it is in their own interest to do so the rest of the time.
[1] http://blogs.boomerang.com/blog/2009/06/16/can-spam-2008-uns...
It looks like the site is supported by donations, which I just did.
[1] If you don't feel like an expert, don't worry about it. The bar in Washington for who's considered an expert is fairly low :-)
Edit: I just submitted this here: http://news.ycombinator.com/item?id=2630141
Appeals to free speech and chilling effects are at best temporary measures in the fight against Protect IP and domain seizures. Even if we win this time it will keep coming back in modified form; the only way defeat it for good is to convince Washington that artists are in fact thriving, that piracy is not the real problem, and that takedown efforts are not in the interest of society. We in the tech world know this, but we are doing a poor job of making ourselves heard in Washington, and this needs to change.
Motivated by this incident, I got together with Pete (the author/victim) to write a piece on "The Need to Reboot Robots.txt" [1] but it went nowhere.
Any suggestions on how to give our proposal legs would be much appreciated.
[1] http://33bits.org/2010/12/05/web-crawlers-privacy-reboot-rob...
Tracking is currently a hot topic in the US as well, where a different approach, labeled Do Not Track is being pursued. I happen to be at the thick of it, so I thought I'd add that to the discussion.
Do Not Track (http://donottrack.us/) is fundamentally an opt-out from tracking rather then an opt-in, which makes it much harder to claim that it will threaten the ad industry, startups, puppies, or anything else [1]. It is an HTTP header which, if enabled, signals to advertisers and other trackers to stop tracking you across multiple third-party websites. First-party tracking is OK.
The Do Not Track option has already been implemented in Firefox 4. As of yesterday it is an Internet-Draft[2], and on the legislation side, Congresswoman Speier recently introduced a bill to give the Federal Trade Commission powers to enforce Do Not Track.[3]
I'm a computer scientist and this is my first major foray into the policy arena, and having worked with most of the people/entities involved in this effort, I have to say I've been pleasantly surprised how the disparate parts of the technology/policy/regulatory machinery started to work together.
I don't want to get into which approach is better, but just wanted to describe how we're doing it in the US. Feedback welcome.
[1] http://cyberlaw.stanford.edu/node/6592
[2] http://cyberlaw.stanford.edu/node/6633
[3] https://speier.house.gov/index.cfm?sectionid=48&itemid=6...
As a cryptography researcher I've come across numerous cumbersome anonymous reputation systems, but it didn't occur to me that Facebook is in a position to roll one out right now with a minor change if they chose to. The caveat, of course, is that it is centralized and controlled by FB. Whether they have the incentive to implement it is an entirely different question.
"It's darkly amusing how people pretend this is about anonymity. As if there had never been a sexist jerk who had a name. ..."
I have to say that the results of this experiment make me feel vindicated.
On another note, multiple commenters here say that they won't be using Facebook comments because they don't want to spam their friends' feeds. Apparently they missed the checkbox right underneath the comment box that says "Post to Facebook"?
[1] http://33bits.org/2010/08/30/women-in-tech-how-anonymity-con...
Wow.
(All letters except n, u, w are registered; most are jokes but a few are earnest.)
My real point here is that no chess program incorporates strategy the way humans do, and that it is unfortunate that this goal isn't being pursued.
it's a simple matter to force equal trades; black cannot avoid the exchange of pieces forever, and if white plays a perfect game he will always win, without doubt.
Yes, that's pretty much the human intuition for why no one doubts that White will win. But it is very, very far from a mathematical proof.
Okay, just calculate the moves it would take to force the equal exchange of material from a given position.
Let me remind you that each ply has a branching factor of about 20, which means each move has a branching factor of several hundred. In most positions you'd be lucky to be able to calculate even one or two forced exchanges, let alone all the way to the end of the game.
A program attempting to prove victory operates in a very different context from a normal chess playing program — it is not allowed to prune any positions at all. We haven't even found the status of all seven piece endings yet! That is despite intense effort. See http://en.wikipedia.org/wiki/Endgame_tablebase
It is utterly, utterly inconceivable that a search-based approach will ever prove victory with Queen odds.
Academics react extremely badly to being told to follow procedures as part of their daily workflow, especially ones they don't understand the importance of. In fact, a big part of the reason that they're in academia in the first place is that they're not able to handle the mundane requirements that are usually in place in the "real world."
For example, someone I work with complains incessantly about the fact that department IT forced him to upgrade from pine — pine, in 2010 — because it is no longer supported. If the IT folks tried to institute rigorous procedures, they would be instantly vilified (and ignored). Unlike in a company where there's a hierarchy, professors don't have anyone above giving them orders, and aren't used to the concept.
Of course, scientific protocols themselves often require lots of procedures, but this is very different because it comes from within and is well-motivated from the point of view of the scientist.
Let me clarify: I do think it is very important that what happened here doesn't happen again, but ensuring that is much harder than someone not familiar with the system might assume. It probably needs to be a mixture of carrots and sticks; I'd say a lot more carrots than sticks.
The fundamental reason why this is a big deal is that in the UK, the repercussions of fraud are skewed towards customers rather than the banks. The relevant legal standard is that customers must exercise "reasonable care" with their PIN if the bank is to bear the cost of fraud. Of course, banks always insist that their systems are secure, and that it was the customer's fault. http://www.timesonline.co.uk/tol/money/consumer_affairs/arti...
The Cambridge team has been investigating vulnerabilities in the EMV standard underlying Chip and PIN (ubiquitous in the UK) for a long time.
From 2006: http://www.lightbluetouchpaper.org/2006/03/15/chip-and-skim/
If I understand correctly they first started to find serious vulnerabilities in 2009.
Blog post: http://www.lightbluetouchpaper.org/2009/08/25/defending-agai...
Paper: "Optimised to Fail: Card Readers for Online Banking" http://www.cl.cam.ac.uk/~sd410/papers/optimised_fail.pdf
Media: http://www.youtube.com/watch?v=U1QAnb-wnTs
They escalated that attack in 2010. http://www.lightbluetouchpaper.org/2010/02/11/chip-and-pin-i...
Paper: http://www.cl.cam.ac.uk/~sjm217/papers/oakland10chipbroken.p...
As for whether it will become the new normal, that remains to be seen, but I think there are a couple of differences compared to regular privilege-escalation exploits: (1) everyone agrees that taking over your computer is malicious, whereas the perception of identity leaks is malleable (2) identity leaks are harder to deal with: even after the relevant bug is fixed, the attacker still has the mapping of your identity to your IP/browser fingerprint.
But thanks for the comparison and I will keep an open mind about this :-)
Via a bug in Firefox's Error object: http://33bits.org/2010/06/01/yet-another-identity-stealing-b...
Via a bug in Google spreadsheets: http://33bits.org/2010/02/22/google-docs-leaks-identity/ (I found this one :-)
Via history stealing: http://33bits.org/2010/02/18/cookies-supercookies-and-uberco...
More sophisticated, but hypothetical version of previous: http://33bits.org/2010/02/19/ubercookies-history-stealing-so...
XSS bugs and other problems with Instant personalization partner sites: http://33bits.org/2010/09/28/instant-personalization-privacy...
I've also been predicting that this will eventually become the new normal -- both because the bugs are coming too fast to fix (and exploits in the wild will become more common) and because Facebook is pushing to change people's expectations with Instant Personalization.
The other day I attended a talk about one-click frauds. I realized that that's the perfect black-hat use-case for this class of attacks (although current 1-click fraudsters are apparently rather low tech). Stay tuned.
The question is why are complexity theorists excited about this.
When a problem is too hard to solve, you look for easier versions to solve first. Here the easier version is to prove that the complexity class NEXP (which is intuitively vastly more powerful than even NP) is bigger than a certain class of circuits of constant depth (circuits with polynomial depth are known to be roughly equivalent to P, and constant-depth circuits are intuitively vastly less powerful).
ETA: the circuits considered here are "non-uniform," which makes the previous paragraph slightly inaccurate. Nevertheless, the point stands that the goal here is to separate two complexity classes that are intuitively very different in their power.
Circuit lower bounds -- proving that a restricted class of circuits, as above, is in fact limited in its computational power -- have been notorious for their hardness. The reason one would want to prove this kind of statement is not because these circuits are objects of practical interest, but because of the proof techniques that would come out as a side-effect, in the hope that these techniques would be applicable in solving other, harder problems.
So that's the gist of it: the 3 reasons this theorem is exciting are: proof techniques, proof techniques and proof techniques.
Now some of the statements from the post should hopefully make a lot more sense:
This approach converts weak algorithms for solving circuit satisfiability questions into circuit lower bounds. Ryan's proof doesn't use deep mathematical techniques but rather puts together a series of known tools in amazingly clever ways.
Ryan breaks through the natural proofs barrier in an interesting way. ... he avoids the issue by using diagonalization and so his proof does not fulfill the constructivity requirement of natural proofs.
What's going on here is that there are often meta-proofs in complexity theory showing that a certain approach to proofs won't work. The "natural proofs barrier" being referred to is (apparently) a limit on what you can achieve by a certain type of "natural" construction that is explained in this post by Lipton: http://rjlipton.wordpress.com/2009/03/25/whos-afraid-of-natu...
The one thing I haven't touched upon is why there are "mod m" gates in the circuit class under consideration. That is also (surprise, surprise) related to proof techniques. As Luca Trevisan explains, using mod m gates instead of binary gates or mod-prime gates disables two well-known classes of proofs ("fixing variables to random values" and "low-degree polynomial approximation"), ensuring that some heavy artillery will need to be developed in order to prove statements about them. http://lucatrevisan.wordpress.com/2010/11/08/a-circuit-lower...