Jefferson's Wheel

Our paper on using lattice ciphers for low-power public-key encryption targeted to RFID tags is now available. Yu Yao will present the paper in Wuxi, China in April.

Yu Yao, Jiawei Huang, Sudhanshu Khanna, abhi shelat, Benton Highsmith Calhoun, John Lach, and David Evans. A Sub-0.5V Lattice-Based Public-Key Encryption Scheme for RFID Platforms in 130nm CMOS. 2011 Workshop on RFID Security (RFIDsec’11 Asia)
Wuxi, China. 6-8 April 2011.

Abstract: Implementing public-key cryptography on passive RFID tags is very challenging due to the limited die size and power available. Typical public-key algorithms require complex logical components such as modular exponentiation in RSA. We demonstrate the feasibility of implementing public-key encryption on low-power, low cost passive RFID tags to large-scale private identification. We use Oded Regev’s Learning-With-Error (LWE) cryptosystem, which is provably secure under the hardness assumption of classic lattice problems. The advantage of using the LWE cryptosystem is its intrinsic computational simplicity (the main operation is modular addition). We leverage the low speed of RFID application by using circuit design with supply voltage close to transistor threshold (V_t) to lower power. This paper presents protocols for using the LWE cipher to provide private identification, evaluates a design for implementing those protocols on passive RFID tags, and reports on simulation experiments that demonstrate the feasibility of this approach.

Full paper (19 pages): [PDF]

We’ve released our code and paper on efficient privacy-preserving biometric identification:

Yan Huang (University of Virginia), Lior Malka (Intel/University of Maryland), David Evans (University of Virginia), and Jonathan Katz (University of Maryland). Efficient Privacy-Preserving Biometric Identification. To appear in 18^th Network and Distributed System Security Conference (NDSS 2011), 6-9 February 2011. [PDF, 14 pages]

We present an efficient matching protocol that can be used in many privacy-preserving biometric identification systems in the semi-honest setting. Our most general technical contribution is a new backtracking protocol that uses the by-product of evaluating a garbled circuit to enable efficient oblivious information retrieval. We also present a more efficient protocol for computing the Euclidean distances of vectors, and optimized circuits for finding the closest match between a point held by one party and a set of points held by another. We evaluate our protocols by implementing a practical privacy-preserving fingerprint matching system.

Yan will present the paper at NDSS in February. The code for our system is available under the MIT open source license.

flickr cc: didbygraham

Oakland 2010 submissions closed last week. We received 269 total submissions (of which 30 were Systematization of Knowledge papers). The program should be available by early February, for the conference that will be held May 16-19, 2010 at the Claremont Resort in Berkeley, CA.

The Examiner has an article on Facebook privacy issues: To Facebook or not to Facebook, 29 June 2009.

The second approach is even scarier, a feature of Facebook which allows outside developers to create small programs called “applications” for members to do things like playing poker, getting daily horoscopes, and sending each other virtual fantasies. With the younger set, the latter must cause parents a lot of consternation over their kids. Word is there are about 24,000 applications that have been built by 400,000 developers.

And here’s the kicker. Once these developers have your personal data, there is nothing Facebook can do. Adrienne Felt of the University of Virginia investigated the procedure in her thesis and found out that 90 out of 150 of Facebook’s most popular applications (that’s 60 percent) have unnecessary access to your private information.

Jake Widman has written an interesting article about the impact of “oversharing” on Facebook: How Facebook mucks up office life: Managing a workforce is already a challenging job; now Facebook and other social networks raise a host of sticky new situations., ComputerWorld, 30 April 2009.

The key observation is the way social networks mix different social circles that would rarely intersect in real life, along with people’s willingness to accept friend requests from unknown or unvalidated individuals.

Separate from the social challenge is the issue of people, particularly younger Facebook users, becoming friends with people they don’t know well, or even at all. “Facebook doesn’t have our normal social mechanisms for validating someone,” Argast points out — and many users, especially people who use Facebook to network, are reluctant to turn down a friend request.

The article mentions studies that indicate both that a significant fraction (23%) of hiring managers check social networking sites on potential hires, and that the majority of Facebook users do not understand how visible their “private” information is.

The article also highlights the additional risks of applications.

A further issue is the fact Facebook applications gain access to — as the warning screen tells you — “your profile information, photos, your friends’ info, and other content that it requires to work,” whether they need it or not.

In 2007, Adrienne Porter Felt, then a computer science student at the University of Virginia and now a student at U.C. Berkeley, and David Evans, an Associate Professor of Computer Science at the University of Virginia, did a survey of the top 150 Facebook applications and found that “90.7% of applications are being given more privileges than they need” to perform their intended functions.

The researchers haven’t updated those earlier findings, but Evans says he suspects the results would be pretty similar. “If anything, the applications are getting more complex,” he says. “And there is also an emerging model for third-party advertising networks embedded in applications, which has further privacy risks.”

In summary,

Bottom line? Facebook doesn’t call for new principles, Selvas says, just smart application of the old ones. And the constant reminder that you and your employees are in public when you’re on Facebook. As Selvas sums up, “Don’t do anything on Facebook you wouldn’t do in an airport.”

The New York Times has an article on social network privacy issues including the risks of third party applications: When Everyone’s a Friend, Is Anything Private?, New York Times, 7 March 2009 (by Randall Stross, Digital Domain column).

FACEBOOK has a chief privacy officer, but I doubt that the position will exist 10 years from now. That’s not because Facebook is hell-bent on stripping away privacy protections, but because the popularity of Facebook and other social networking sites has promoted the sharing of all things personal, dissolving the line that separates the private from the public.

…

Facebook’s default settings for new accounts protect users in some ways. For instance, the information in one’s profile is restricted to friends only; it is not accessible to friends of friends. But Facebook sets few restrictions by default on what third-party software can see in a network of friends. Members are not likely aware that unless they change the default privacy settings, an application installed by a friend can vacuum up and store many categories of a member’s personal information.

David E. Evans, an associate professor of computer science at the University of Virginia, says he wishes that Facebook would begin with more restrictions on the information that outside software developers can reach. For 15 of 19 information categories, Facebook sets a default setting of “share,” which means the information can be pulled out of Facebook and stored on servers outside its control. These 15 categories include activities, interests, photos and relationship status.

“Facebook could set defaults erring on the side of privacy instead of on the side of giving your information away,” he said.

Chris Kelly, Facebook’s chief privacy officer, defends its current settings, saying it “gives users extensive control over the applications they choose to interact with.” He also said Facebook had removed “thousands” of applications that members deemed untrustworthy.

In Professor Evans’s view, however, banishment of malevolent software comes too late: “Once the application has got the data, it’s got it, stored on someone else’s machine.”

The defaults turn out to be crucially important, because few users go to the trouble of adjusting the settings. Asked how many members ever change a privacy setting, Mr. Kelly said 20 percent.

Randolph Yu Yao is joining our research group and the NSF RFID project. He’s a PhD student in Computer Engineering and will be working on something related to security and privacy for RFID systems that integrates cryptographic requirement with circuit-level designs.

His brief bio is below. Please join me in welcoming Randolph to the group!

I was born in a small city in southeast of China, and traveled from south to north during my high school, undergraduate, half-graduate study. I’m very happy to travel to the other half of the planet for my PhD study here in the end.

I was an EE major and love to deal with various aspects of embedded system. I’ve worked on the RoboCup, which forms a robot team to play “football”; the Mobile Satellite Communication Vehicle, which essentially control the attitude of antenna in dynamic circumstance; the Multi-Agent Cooperation via wireless communication etc. I didn’t realize before that the security issues of the embedded system are very challenge problems and becomes a bottleneck for their ubiquitous deployments, no matter for sensor networks or RFID. My ultimate goal is to enable these smart embedded systems acceptable by common people and put into daily service without concern about the security and reliability in the face of expanding network connection.

I also like sports such as swimming, traveling, exploration, basketball, hiking but no running which I think too boring. I enjoy the weather, the blue sky and fresh air here.

Don Tapscott’s new book, Grown Up Digital: How the Net Generation is Changing Your World, includes a brief description of Adrienne Felt’s work on social network privacy:

I’m still worried, though, and I’m not alone. According to Adrienne Felt, the coauthor of a 2007 study on social networking privacy, the new measures do not fix a key problem. You can decide which of your friends can see what on your profile, and you can stop the applications that your friends install from peering into your Facebook world. But, if you install an application — say, a photo editing application that lets you put Angelina Jolie’s hairdo on your best friend’s high school graduation picture — the maker of that application can see anything you put on your profile, like your dating interest, your summer plans, your political views, your photos, the works. The only way to stop the application developers from peering into your own Facebook world, Felt says, is to not put any applications on your personal profile. The vast majority of applications don’t need your private data to do their thing, she notes, and yet all of them have access to whatever you can see. [footnote that references our Privacy by Proxy paper]

I tried the book’s website http://grownupdigital.com/, but get:

PHP has encountered an Access Violation at 7C81BD02

Perhaps the digital world is not fully grown up yet!

Technology Review has an article surveying the state of RFID security: RFID’s Security Problem, Technology Review, January/February 2009. It focuses on security and privacy issues related to RFID-enabled passports and driver’s licenses.

Excerpt: (bolding is mine)

Meanwhile, although experts say that some RFID technologies are quite secure, a University of Virginia security researcher’s analysis of the NXP Mifare Classic (see Hack, November/December 2008), an RFID chip used in fare cards for the public-­transit systems of ­Boston, London, and other cities, has shown that the security of smart cards can’t be taken for granted. “I think we are in the growing-pains phase,” says Johns Hopkins University computer science professor Avi Rubin, a security and privacy researcher. “This happens with a lot of technologies when they are first developed.”

…
As long as the remaining problems are ignored, though, it’s unlikely that the technology will become good enough to protect international borders without compromising the privacy of thousands or millions of people. Tadayoshi Kohno, for one, says that at this point, he is not convinced that RFID even offers security advantages over the old IDs. Technology used on this scale, and for purposes this important, should be clearly better than what it’s replacing: the U.S. experience with electronic voting systems shows what can happen when it’s not. If officials continue to advocate band-aids such as privacy sleeves rather than working to address the full extent of critics’ concerns, they will ultimately undermine the very technology that they hope to promote. While new ID technology seems likely to stay, it could become a fiasco if officials don’t pay attention to the work of hackers and security researchers. These people try to expose weaknesses before they can be exploited maliciously. It’s much less painful to swallow the news from them than to wait until a problem becomes embarrassing–or devastating.

The list of papers accepted to the 2009 IEEE Symposium on Security and Privacy (Oakland Conference) is now posted here:
http://oakland09.cs.virginia.edu/papers.html.

Twenty-six papers were accepted (from over 250 submissions).

The symposium will be held 17-20 May 2009 at the Claremont Resort in Oakland, CA. Hope to see you there!