Allison Bishop Lewko
Home Page: http://www.cs.columbia.edu/~alewko
Office: 519 CSB
Email Address:

About Me

I am an assistant professor in the computer science department at Columbia University. My current areas of research are cryptography, complexity theory, harmonic analysis, combinatorics, and distributed computing. Previously, I was a postdoctoral researcher at Microsoft Research New England. I completed my Ph.d. in Computer Science at UT-Austin, advised by Brent Waters. I have also received a certificate of advanced study in mathematics from the University of Cambridge and earned my bachelor's degree in mathematics from Princeton University.

Teaching

  • Spring 2014: COMS E6261: Advanced Cryptography (Syllabus) *Note schedule change!
  • Spring 2014: COMS W3261: Computer Science Theory (Syllabus) *Note TA office hours change.

    CV

    Research - Cryptography and Related Topics

  • "Why Proving HIBE Systems Secure is Difficult" (Eurocrypt 2014) with Brent Waters (PDF)
  • "On the Complexity of Asynchronous Agreement Against Powerful Adversaries" (PODC 2013) with Mark Lewko (arXiv)
  • "Dual Form Signatures: An Approach for Proving Security from Static Assumptions" (ASIACRYPT 2012) with Michael Gerbush, Adam O'Neill, and Brent Waters (PDF)
  • "Formulas Resilient to Short-Circuit Errors" (FOCS 2012) with Yael Kalai and Anup Rao (PDF)
  • "New Proof Methods for Attribute-Based Encryption: Achieving Full Security through Selective Techniques" (CRYPTO 2012) with Brent Waters (PDF)
  • "Tools for Simulating Features of Composite Order Bilinear Groups in the Prime Order Setting" (Eurocrypt 2012) (PDF)
  • "Detecting Dangerous Queries: A New Approach for Chosen Ciphertext Security" (Eurocrypt 2012) with Susan Hohenberger and Brent Waters (PDF)
  • "Bounded-Collusion IBE from Key Homomorphism" (TCC 2012) with Shafi Goldwasser and David A. Wilson
  • "Storing Secrets on Continually Leaky Devices" (FOCS 2011) with Yevgeniy Dodis, Brent Waters, and Daniel Wichs (PDF)
  • "The Contest Between Simplicity and Efficiency in Asynchronous Byzantine Agreement" (DISC 2011) (arXiv)
  • "How to Leak on Key Updates" (STOC 2011) with Mark Lewko and Brent Waters (PDF)
  • "Decentralizing Attribute-Based Encryption" (Eurocrypt 2011) with Brent Waters (PDF)
  • "Unbounded HIBE and Attribute-Based Encryption" (Eurocrypt 2011) with Brent Waters (PDF)
  • "Achieving Leakage Resilience Through Dual System Encryption" (TCC 2011) with Yannis Rouselakis and Brent Waters (PDF)
  • "On the Insecurity of Parallel Repetition for Leakage Resilience" (FOCS 2010) with Brent Waters (PDF)
  • "Fully Secure Functional Encryption: Attribute-Based Encryption and (Hierarchical) Inner Product Encryption" (Eurocrypt 2010) with Tatsuaki Okamoto, Amit Sahai, Katsuyuki Takashima, and Brent Waters (PDF)
  • "New Techniques for Dual System Encryption and Fully Secure HIBE with Short Ciphertexts" (TCC 2010) with Brent Waters (PDF)
  • "Revocation Systems with Very Small Private Keys" (IEEE Symposium on Security and Privacy 2010) with Amit Sahai and Brent Waters (PDF)
  • "Efficient Pseudorandom Functions from the Decisional Linear Assumption and Weaker Variants" (CCS 2009) with Brent Waters (PDF)

    Dissertation

  • "Functional Encryption: New Proof Techniques and Advancing Capabilities" (PDF)

    Research - Harmonic Analysis, Combinatorics, and Number Theory

  • "The Square Variation of Rearranged Fourier Series" (submitted) with Mark Lewko (arXiv)
  • "Orthonormal Systems in Linear Spans" (Analysis & PDE, to appear) with Mark Lewko (arXiv)
  • "Maximal Operators Associated to Multiplicative Characters" (Proceedings of the AMS, to appear) with Mark Lewko (arXiv)
  • "A Variational Barban-Davenport-Halberstam Theorem" (Journal of Number Theory, 132 (2012) 2020-2045) with Mark Lewko (arXiv)
  • "Estimates for the Square Variation of Partial Sums of Fourier Series and their Rearrangements" (Journal of Functional Analysis, 262 (2012) 2561-2607) with Mark Lewko (arXiv)
  • "An Exact Asymptotic for the Square Variation of Partial Sum Processes" (submitted) with Mark Lewko (arXiv)
  • "Endpoint Restriction Estimates for the Paraboloid over Finite Fields" (Proceedings of the AMS, 140 (2012) 2013-2028) with Mark Lewko (arXiv)
  • "On the Structure of Sets of Large Doubling" (European Journal of Combinatorics, 32 (2011) 688-708) with Mark Lewko (arXiv)