Allison Bishop
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.
  • The kickstarter campaign for the math-inspired kids book I've written with Sasha Fradkin: Funville Adventures.
  • I'm running the NYC marathon on November 5, 2017 as part of the charity team for Sanctuary for Families, an organization that helps survivors of domestic violence. Check out the funny campaign video I made at: Marathon Campaign Page.


  • Fall 2017: COMS W4261: Introduction to Cryptography
  • 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)