Alexander Bienstock

I am a fifth year PhD student advised by Professor Yevgeniy Dodis and Professor Marshall Ball in the Cryptography Lab at NYU. I received my B.S. in Computer Science from Columbia University in May 2019, where I worked with Professor Allison Bishop. I am fortunate enough to be supported by an NSF Graduate Research Fellowship and a Google PhD Fellowship.

I am interested in applied cryptography, particularly secure Multi-Party Computation (MPC). My current research focuses on making MPC more practical, both for specific functionalities like Private Set Intersection, as well as for general computation. I have also studied Secure (Group) Messaging and Private Outsourced Storage protocols in the past.

Publications

Two Levels are Better than One: Dishonest Majority MPC with ~O(|C|) Total Communication
Alexander Bienstock, Kevin Yeo
PDF Manuscript
Honest Majority GOD MPC with O(depth(C)) Rounds and O(n|C|) Online Communication
Amit Agarwal, Alexander Bienstock, Ivan Damgård, Daniel Escudero
Manuscript
Perfectly Secure Fluid MPC with Abort and Linear Communication Complexity
Alexander Bienstock, Daniel Escudero, Antigoni Polychroniadou
Manuscript
Batch PIR and Labeled PSI with Oblivious Ciphertext Compression
Alexander Bienstock, Sarvar Patel, Joon Young Seo, Kevin Yeo
PDF USENIX Security 2024
Towards Topology-Hiding Computation from Oblivious Transfer
Marshall Ball, Alexander Bienstock, Lisa Kohl, Pierre Meyer
PDF TCC 2023 TPMPC 2022
Near-Optimal Oblivious Key-Value Stores for Efficient PSI, PSU and Volume-Hiding Multi-Maps
Alexander Bienstock, Sarvar Patel, Joon Young Seo, Kevin Yeo
PDF USENIX Security 2023
On Linear Communication Complexity for (Maximally) Fluid MPC
Alexander Bienstock, Daniel Escudero, Antigoni Polychroniadou
PDF CRYPTO 2023 TPMPC 2023
ASMesh: Secure Messaging in Mesh Networks Using Stronger, Anonymous Double Ratchet
Alexander Bienstock, Paul Rösler, Yi Tang
PDF Code CCS 2023
On the Worst-Case Inefficiency of CGKA
Alexander Bienstock, Yevgeniy Dodis, Sanjam Garg, Garrison Grogan, Mohammad Hajiabadi, Paul Rösler
PDF TCC 2022
A More Complete Analysis of the Signal Double Ratchet Algorithm
Alexander Bienstock, Jaiden Fairoze, Sanjam Garg, Pratyay Mukherjee, Srinivasan Raghuraman
PDF CRYPTO 2022
Multicast Key Agreement, Revisited
Alexander Bienstock, Yevgeniy Dodis, Yi Tang
PDF Code CT-RSA 2022
Forward Secret Encrypted RAM: Lower Bounds and Applications
Alexander Bienstock, Yevgeniy Dodis, Kevin Yeo
PDF TCC 2021
On the Price of Concurrency in Group Ratcheting Protocols
Alexander Bienstock, Yevgeniy Dodis, Paul Rösler
PDF TCC 2020 RWC 2021
From discrete-log to lattices: maybe the real lessons were our broken schemes along the way?
Alexander Bienstock, Allison Bishop, Eli Goldin, Garrison Grogan, Victor Lecomte
PDF CFAIL 2020

Teaching

Fundamental Algorithms
Spring 2021, Fall 2021 Computer Science Department, New York University
Basic Algorithms
Spring 2020, 2021, Fall 2020 Computer Science Department, New York University
Computer Science Theory
Spring 2019 Department of Computer Science, Columbia University
Malware Analysis & Reverse Engineering
Fall 2018 Department of Computer Science, Columbia University
Computing in Context
Fall 2016 Department of Computer Science, Columbia University

Contact