Allison Bishop
(formerly Allison Bishop Lewko)
Home Page:
Office: 410 Mudd (DSI)
Email Address:

About Me

I am an assistant professor in the computer science department at Columbia University. I am on leave this year and not accepting any new students. 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.

Industry and Outreach

  • While on leave, I have been working as a quantitative researcher at the Investors Exchange. Check out our recent blog post and whitepaper at to see what I've been up to.
  • You can also check out my TEDx New York talk "The Adventure of Alice and the Encrypted Message" on YouTube.


  • Spring 2016: CSOR W4231: Analysis of Algorithms I
  • Fall 2015: COMS W4261: Introduction to Cryptography
  • Fall 2014: CSOR W4231: Analysis of Algorithms I (Syllabus)
  • Spring 2014: COMS E6261: Advanced Cryptography (Syllabus)
  • Spring 2014: COMS W3261: Computer Science Theory (Syllabus)

    Academic CV

    Current Ph.D. Students

  • Lucas Kowalczyk (co-advised with Tal Malkin)
  • Kevin Shi (co-advised with Daniel Hsu)
  • Ghada Almashaqbeh (co-advised with Tal Malkin and Justin Cappos)

    Research - Cryptography and Related Topics

  • "Essentially Optimal Robust Secret Sharing with Maximal Corruptions"(EUROCRYPT 2016) with Valerio Pastro, Rajmohan Rajaraman, and Daniel Wichs (PDF)
  • "Balancing Communication for Multi-party Interactive Coding" with Ellen Vitercik (arXiv)
  • "Robust Secret Sharing Schemes Against Local Adversaries" (PKC 2016)with Valerio Pastro (PDF)
  • "Function-Hiding Inner Product Encryption" (ASIACRYPT 2015) with Abhishek Jain and Lucas Kowalczyk (PDF)
  • "New Circular Security Counterexamples from Decision Linear and Learning with Errors" (ASIACRYPT 2015) with Susan Hohenberger and Brent Waters (PDF)
  • "Indistinguishability Obfuscation for Turing Machines with Unbounded Memory" ( STOC 2015) with Venkata Koppula and Brent Waters (PDF)
  • "Interactive Coding for Multiparty Protocols" (ITCS 2015) with Abhishek Jain and Yael Kalai
  • "Interactive Coding for Interactive Proofs" (TCC 2016) with Yevgeniy Dodis (PDF)
  • "Bilinear Entropy Expansion from the Decisional Linear Assumption" (CRYPTO 2015) with Lucas Kowalczyk (PDF)
  • "Indistinguishability Obfuscation from the Multilinear Subgroup Elimination Assumption" (FOCS 2015) with Craig Gentry, Amit Sahai, and Brent Waters (PDF)
  • "A Profitable Sub-Prime Loan: Obtaining the Advantages of Composite Order in Prime-Order Bilinear Groups" (PKC 2015) with Sarah Meiklejohn (PDF)
  • "Witness Encryption from Instance Independent Assumptions" (CRYPTO 2014) with Craig Gentry and Brent Waters (PDF)
  • "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)


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

    Research - Harmonic Analysis, Combinatorics, and Number Theory

  • "The Square Variation of Rearranged Fourier Series" (Amer. J. Math., to appear) 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" (Annales de l'Institut Henri Poincare, to appear) 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)