Archive for the 'Teaching' Category

Summer School at Notre Dame

Friday, May 13th, 2016

I presented two tutorials on oblivious computation at Notre Dame’s Summer School on Secure and Oblivious Computation and Outsourcing. SRG PhD Yan Huang, now at Indiana University, was one of the other tutorial presenters. I also learned a lot about verifiable computation and argument systems from Justin Thaler. Thanks to Marina Blanton for organizing a great summer school!

Slides for my tutorials on garbling techniques and memory for data oblivious computation are below.




Hacker School Talk: What Every Hacker Should Know about Theory of Computation

Thursday, October 16th, 2014

I had a chance earlier this week to visit and speak at Hacker School in New York. Hacker School is an amazing place, billed as a “retreat for programmers”, where a remarkable group of curious and self-motivated people from a wide range of backgrounds put their lives on hold for 12 weeks to gather with like-minded people to learn about programming and spend their evenings (and 21st birthday parties) hearing talks about computability!

Slides and notes from my talk are here: What Every Hacker Should Know about Theory of Computation.



Engineering Cryptosystems

Wednesday, October 30th, 2013

I gave a four-session “mini-course” for Microstrategy on Engineering Cryptosystems. It ended up attracting enough interest to be moved from their offices to a nearby movie theater!



The course was targeted to engineers at Microstrategy with no prior experience with cryptography, and designed to give them some ideas of the power of modern cryptography, and to provide enough stories about cryptosystems going bad to convince them not do try to develop their own cryptosystems, and to know enough to ask the right questions of people who do.

The four main topics were:

Since it was in a movie theater, it also provided an opportunity to officially screen this trailer in a real movie theater:



Congratulations SRG Graduates

Monday, May 27th, 2013

Congratulations to the 2013 SRG Graduates!


Tianhao Tong (MCS), Dr. Yan Huang (PhD)


Jonathan Burket (BACS with Highest Distinction), William Melicher (BSCS, not pictured)

MOOCs, KOOCS, and SMOOCHs

Thursday, May 2nd, 2013

UVa Today has an article about my talk yesterday on open education: Evans: U.Va. Should Be a Global Leader in MOOCS, Online Learning, UVaToday, 1 May 2013. The article focuses just on the last slide, which is my proposal for what UVa should do.

The full talk is available at http://www.cs.virginia.edu/evans/talks/smoochs/ and below:


CS101: One Year Later

Thursday, February 21st, 2013

I’ve written a post for the Udacity blog on CS101: One Year Later.

The Power of Computing

Wednesday, August 1st, 2012

I’m quoted in this USA Today article: The power of computing, USA Today, 4 June 2012.

“To understand the world, you need to understand computing and programming,” Evans, who is also a computer science professor at University of Virginia, said in an email. “Without understanding computers and how they are programmed, much of the world will increasingly seem like magic.”

While Steve Jobs famously talked about computers as bicycles for the mind 20 years ago, computers today are far more powerful and connected worldwide as “super-tanker-sized, hypersonic spaceships of the mind,” said Evans.

“Without learning to program, you can still ride them if you are willing to remove your shoes at the security checkpoint and go where the pilot wants to go,” said Evans, “but if you want to be the one flying, you need to learn about computing.”

Silver Bullet Interview

Saturday, July 28th, 2012

I was interviewed on Gary McGraw’s Silver Bullet podcast.

Gary and Dave discuss the founding of the Interdisciplinary Major in Computer Science (BA) at UVa and why a broad approach to Computer Science and Computer Security is a good idea, why data privacy gets short shrift in the United States, why people think (for no apparent reason) that their mobile devices are secure, groceries, David’s research on Secure Computation, and the Udacity project. They close out their discussion with a story about David’s trip to the World Cup in Korea and a choice between GEB and scheme.

You can download the podcast from http://www.cigital.com/silver-bullet/show-076/.

Professors Without Borders

Tuesday, July 17th, 2012

My favorite article about Udacity so far is Professors without Borders, Prospect Magazine, 28 June 2012.

Not long ago, on a rainy Saturday morning, Professor Dave Evans and I hung out in bed while he tried to explain recursive functions (for the fourth time) and I worked on my homework. Or rather, I hung out in bed, and Evans, a computer science professor at the University of Virginia, hung out on my laptop screen, where I could—click—pause him midsentence and pour myself another cup of coffee.

“Computer Science 101: Building a Search Engine” was one of Udacity’s first offerings, and for seven weeks this spring, Evans was teaching me and 30,000 others to write enough Python—a basic programming language—to create a mini Google. We started with basics, including the difference between a computer and a toaster, and “bits” versus “bytes.” Then we went back in time for a little nerd history, from Augusta Ada King, Lord Byron’s daughter and the world’s first “programmer,” to PageRank, the search algorithm that powers Google.

Evans is the kind of nerdy savant whose gap-tooth smile and Monty Python humour attract a cult following on campus. (As an academic, he’s also a world-class cryptographer.) Thrun and Stavens found him in November 2011, flew him to Palo Alto in December, and by January he was crammed in a makeshift recording studio—still in Thrun’s guesthouse—rejigging his standard university curriculum into a Udacity one.

Hacking the World Cup Draw

Thursday, December 3rd, 2009

The New York Times has an article about rigging the World Cup draw (which takes place tomorrow in South Africa): In World Cup Draw, Conspiracy Theories Abound, 3 December 2009.

The article mentions the final exam from my 2005 Cryptography course:

It is anyone’s guess how the 32 teams in the 2010 World Cup will be grouped by the draw Friday in South Africa, but one thing is for sure: the event will elicit sightings of things as far-fetched as U.F.O.’s and the Virgin Mary’s image on a potato chip.

Yet conspiracy theories abound. In 2005, the issue was part of a final exam in a cryptology course at the University of Virginia.

Here’s the actual exam: http://www.cs.virginia.edu/cs588/final/final.html and an excerpt from my comments:

4W. Germany 1, USA 0

After the 1994 World Cup draw placed the host USA in a very difficult
group, the USA coach, Bora Milutinovic, is reputed to have complained
that the US organizing committee was so incompetent they couldn’t even
rig the draw properly. For purposes of this question, assume the DFB
(German soccer federation) which is hosting the 2006 World Cup does not
suffer from such incompetence.

The draw assigns each qualified team to a group (one of eight, A-H) and
position (1-4). For example, in the 2002 draw the USA was assigned D3.
The host country is placed into position A1.

The protocol for the draw for the 2006 World Cup finals has not been
announced yet, but assume it will follow a protocol similar to this one
which was used in 2002:

    Before the draw event:

  1. The name of each finalist (except the host country which is placed
    in position A1) is printed on a slip of paper which is placed in a
    white, spherical ball. The ball is made of two hemispheres that connect
    to each other, and can be separated to insert or remove the paper. The
    balls are placed into different bowls based on a partitioning determined
    by FIFA.
  2. The letter name to identify each group (A, B, C, D, E, F, G, H) is
    printed on a slip of paper and placed in a red, spherical ball. All the
    red balls are placed in a bowl.
  3. The position number (1, 2, 3, 4) is printed on a slip of paper and
    placed in a blue, spherical ball. There are eight bowls of the four
    numbers, one corresponding to each group A-H. (In the bowl for A, only
    three balls with numbers 2, 3 and 4 are used, since the host country was
    preassigned to position A1).

    At the draw event:

  4. A well-known celebrity picks a white ball from one of the country
    bowls and hands it to Sepp Blatter, the President of FIFA.
  5. Blatter unscrews the ball, extracts the slip of paper, reads the
    country name, and holds it up so everyone can see. After reading the
    slip, it is placed in a trash bin that is not examined after the draw.
  6. A different well-known celebrity picks a red ball from the
    group bowl and hand it to Blatter.
  7. Blatter unscrews the ball, extracts the slip of paper, reads the
    group name, and holds it up so everyone can see.
  8. A different well-known celebrity picks a blue ball from the
    positions bowl corresponding to the selected group and hand it to Blatter.
  9. Blatter unscrews the ball, extracts the slip of paper, reads the
    position number, and holds it up so everyone can see.

Note that at the end of the draw, all balls have been opened. It is a
check on the protocol that all positions, groups and countries have been
seen by the end. The actual slips of paper are destroyed (without
examination) after the draw.

You should assume both the DFB who is hosting the draw, and Sepp
Blatter, are both highly motivated to rig the results to ensure an easy
path to the second round for the host country. Well-known celebrities
are used to pick the balls to ensure a low likelihood that a selector
can be corrupted. The pre-draw steps are done in secret by the DFB.
The draw event itself is witnessed by thousands of people live and in
person and approximately a billion people live on TV around the world
(it is the world’s most watched televised event that is not a soccer
game).

Analyze the security of the World Cup draw procedure as described
above. Either describe tactics the DFB could use to improve the
likelihood that Germany get a favorable draw, or argue that the
procedure is secure and there is no reasonable way of effecting the
result. If you identify security weaknesses in the draw protocol,
suggest modifications that would make it more secure.

For inspiration, you may want to read Bruce Schneier’s Hacking the Papal Election analysis of the Papal election procedure.


(Note: this question should in no way be interpreted as
questioning the integrity of FIFA or the DFB, especially if they are
using RFID tags to track my tickets’ whereabouts.)

Comments: There are lots of weaknesses in the described protocol
(which does not match the actual world cup draw protocol which may have even more vulnerabilities) that could be used to alter the draw outcome.

The least risky way of rigging the draw would be to adjust the weights of the balls to increase the likelihood that certain balls end up on the outside edge of the bowl and will be picked early. This can effect the probabilities of getting certain teams in Germany’s group, and involves little risk of getting caught (as long as the process of loading the balls is done in secret by trusted (but not trustworthy) people).

A riskier, but more certain, way of fixing the draw would be to put two slips in some of the balls. Blatter would need to be able to pick the right slip without anyone noticing him doing so. The easiest way would be to have two slips of different length that are attached with a very weak adhesive. Blatter knows that the shorter slip has the strong team and the longer slip has the weak team. There are two balls with two slips, so Blatter will need to remember for the next ball to pick the opposite one. This allows control of two teams, which is not enough to control the whole draw, but is enough to give Germany one easier team.

Blatter could also have a slip “up his sleeve” with a desirable team name on it, but it would be difficult to pull of any sleight of hand tricks without getting caught.

Some improvements that would make cheating more difficult would be to have an independent third party create the balls in public, to have a multiple-readers strategy like in the Pope election where several people examine each slip in public, to have the celebrities (considered uncorruptable) not only pick the ball but open it and examine the slip before it is read, and to have all the balls selected before any one it opened (to prevent any attacks that depend on knowing what was in the previous ball to pick a desirable ball).

From the NYT article, I may be mistaken about the rumors of Bora Milutinovic’s comments about the 1994 draw. Perhaps it was really Bruce Arena’s quote about the draw for the 1996 Olympics, quoted in the NYT article which is presumably a fairly reputable source.

As for tomorrow’s draw, so long as the US doesn’t end up in a group with Brazil, France, and Ivory Coast, I’m willing to assume its not rigged.