Chris Peikert

I am now employed in the Computer Science Laboratory at SRI International. This page may disappear/relocate soon.

In 2006 I received my Ph.D. from the Computer and Information Security Group at the MIT Computer Science and Artificial Intelligence Laboratory. Silvio Micali was my advisor.

My academic interests include cryptography, coding theory, algorithms, and computational complexity.

I attended MIT as an undergrad, graduating with an S.B. (in Pure Mathematics) in 2000, and a combined S.B./Master of Engineering (in Computer Science) in 2001.

You can jump directly to my -- research -- teaching -- coursework -- people -- readings

Research

"Research is what I'm doing when I don't know what I'm doing." -- Wernher Von Braun

Newer

• Limits on the Hardness of Lattice Problems in l_p Norms [Slides]
  Chris Peikert.
  Computational Complexity 17(2):300-351 (May 2008). Preliminary version in Complexity 2007.
• Noninteractive Statistical Zero-Knowledge Proofs for Lattice Problems
  Chris Peikert, Vinod Vaikuntanathan.
  In CRYPTO 2008.
• A Framework for Efficient and Composable Oblivious Transfer [Slides]
  Chris Peikert, Vinod Vaikuntanathan, Brent Waters.
  In CRYPTO 2008.
• Trapdoors for Hard Lattices and New Cryptographic Constructions [Slides]
  Craig Gentry, Chris Peikert, Vinod Vaikuntanathan.
  In STOC 2008.
• Lossy Trapdoor Functions and Their Applications [Slides]
  Chris Peikert, Brent Waters.
  In STOC 2008. Invited to SIAM Journal on Computing.
• SWIFFT: A Modest Proposal for FFT Hashing
  Vadim Lyubashevsky, Daniele Micciancio, Chris Peikert, Alon Rosen.
  In FSE 2008.
• Lattices that Admit Logarithmic Worst-Case to Average-Case Connection Factors [Slides]
  Chris Peikert, Alon Rosen.
  In STOC 2007.

Older

• Provably Secure FFT Hashing
  Vadim Lyubashevsky, Daniele Micciancio, Chris Peikert, Alon Rosen.
  In 2nd NIST Cryptographic Hash Function Workshop, 2006.
• Efficient Collision-Resistant Hashing from Worst-Case Assumptions on Cyclic Lattices [Slides]
  Chris Peikert, Alon Rosen.
  In TCC 2006.
• On Error Correction in the Exponent [Slides]
  Chris Peikert.
  In TCC 2006.
• Optimal Error Correction Against Computationally Bounded Noise
  Silvio Micali, Chris Peikert, Madhu Sudan, David A. Wilson.
  In TCC 2005.
• Completely Fair SFE and Coalition-Safe Cheap Talk
  Matt Lepinski, Silvio Micali, Chris Peikert, abhi shelat.
  In PODC 2004.
• Lower Bounds for Collusion-Secure Fingerprinting
  Chris Peikert, Adam Smith, abhi shelat.
  In SODA 2003.
• March Madness is (NP-)Hard
  David Liben-Nowell, Moses Liskov, Chris Peikert, abhi shelat, Adam Smith, Grant Wang.
  Unpublished manuscript.
• Adaptive Security in the Threshold Setting: From Cryptosystems to Signature Schemes
  Anna Lysyanskaya, Chris Peikert.
  In ASIACRYPT 2001.

Theses

• PhD thesis: Cryptographic Error Correction.
• Masters thesis: Adaptive Security in the Threshold Setting: From Cryptosystems to Signatures.

Teaching

"Good teaching is one-fourth preparation and three-fourths theater." -- Gail Godwin

In the past, I've been a teaching assistant for:

• 6.857: Network and Computer Security (Fall 2005), taught by Shafi Goldwasser - Underground Guide Evaluation (requires MIT certificates)
• 6.875: Cryptography and Cryptanalysis (Spring 2004), taught by Silvio Micali - Underground Guide Evaluation (requires MIT certificates)
• 6.857: Network and Computer Security (Fall 2003), taught by Ron Rivest - Underground Guide Evaluation (requires MIT certificates)
• 6.046: Introduction to Algorithms (Fall 2002) (head TA), taught by Erik Demaine and Shafi Goldwasser
• 6.87s: Cryptography and Computer Security (Summer 2002), taught by Shafi Goldwasser and Mihir Bellare.
• 6.046: Introduction to Algorithms (Spring 2001), taught by Madhu Sudan and Piotr Indyk - Underground Guide Evaluation (requires MIT certificates)
• 6.001: Structure and Interpretation of Computer Programs (Fall 2000), taught by Eric Grimson - Underground Guide Evaluation (requires MIT certificates)

Coursework

"I never let my schooling interfere with my education." -- Mark Twain

Notable classes I've taken, with links (where available):

• 6.897: Algorithmic Introduction to Coding Theory (Fall 2001),
• 6.854: Advanced Algorithms (Fall 2001),
• 6.897: Selected Topics in Cryptography (Spring 2004),
• 6.876: Advanced Topics in Cryptography (Spring 2001, Spring 2003, Fall 2004),
• 6.856: Randomized Algorithms (Fall 2000),
• 6.875: Cryptography and Cryptanalysis (Fall 1999),
• 6.841: Advanced Complexity Theory (Spring 1999),
• 6.840: Theory of Computation (Fall 1997),
• Harvard CS225: Pseudorandomness (Spring 2002, Listener),
• 18.419: Random Walks and Polynomial-Time Algorithms (Spring 2002),
• 18.904: Seminar in Algebraic Topology (Spring 2000),
• 18.901: Topology (Fall 1999),
• 18.701/702: Algebra I/II (Fall 1997/Spring 1998),
• 18.101: Analysis on Manifolds (Spring 2000),
• 15.099: Special Seminar in Operations Research: Proofs from The Book (Fall 2002)

You might also be interested in the Theory of Computation Calendar.

People

"A wise man would pick up a grain of sand and envision the entire universe. A stupid man would roll in seaweed, stand up, and say, 'Look, I'm vine man.'" -- Jack Handey

I am the product of a collaboration between my parents, Michael and Frances Peikert. Having not learned their lesson, my sister Stephanie arrived 18 months later. These baby pictures of us are pretty embarassing, I think.

My wife Briana fulfills her community service requirements by spending her time with me.

Around the lab, I have been seen, at one time or another, in the company of abhi shelat, the invisible hand of Adam Smith, my arch-nemesis-from-Ohio-State Susan Hohenberger, fellow Kalamazooan and KAMSC alum Hanson Zhou, certified mixologist Steve Weis, the mispronounced Grant Wang, the hyphenated David Liben-Nowell, the not-related-to-the-shoe-company Ben Adida, and my poker protégés Matt Lepinski and Moses Liskov.

Readings

"Thank you for sending me a copy of your book - I'll waste no time in reading it." -- Moses Hadas

Sometimes I get my hands on a good book of fiction, and (even less sometimes) have time to read it. Here are some of the better ones, with links (note: I do not benefit if you decide to buy):

• 41 Stories by O. Henry, by O. Henry
• Selected Short Stories, by Guy De Maupassant
• Fifth Business and The Manticore, by Robertson Davies (World of Wonders would finish off The Deptford Trilogy)
• 1984, by George Orwell
• Frankenstein, by Mary Shelley
• Pride and Prejudice, by Jane Austen
• The Grapes of Wrath, by John Steinbeck
• A Confederacy of Dunces, by John Kennedy Toole
• Uncle Tom's Cabin, by Harriet Beecher Stowe
• A Prayer for Owen Meany, and the less-outstanding-but-still-good A Widow for One Year, by John Irving
• The Diamond Age, by Neal Stephenson.
• Red Sky At Morning, by Richard Bradford.
• "Surely You're Joking, Mr. Feynman!", by Richard Feynman (must be fiction; these stories are over the top)
• Gödel, Escher, Bach: An Eternal Golden Braid, by Douglas R. Hofstadter (non-fiction, but very, very good)