Papers

[Manuscript] OptRand: Optimistically Responsive Distributed Random Beacons
Paper
Adithya Bhat, Nibesh Shrestha, Aniket Kate, Kartik Nayak

[Manuscript] Player-Replaceable Blockchain Protocols with Forensic Support
Paper
Sreeram Kannan, Kartik Nayak, Peiyao Sheng, Pramod Viswanath, Gerui Wang

[Manuscript] IncShrink: Architecting Efficient Outsourced Database using Incremental MPC and Differential Privacy
Paper
Chenghong Wang, Johes Bater, Kartik Nayak, Ashwin Machanavajjhala

[Manuscript] Optimal Good-case Latency for Rotating Leader Synchronous BFT
Paper
Ittai Abraham, Kartik Nayak, Nibesh Shrestha

[Manuscript] Efficient Adaptively-Secure Byzantine Agreement for Long Messages
Paper
Amey Bhangale, Chen-Da Liu-Zhang, Julian Loss, Kartik Nayak

DP-Sync: Hiding Update Patterns in Secure Outsourced Databases with Differential Privacy
Paper
Accepted in SIGMOD 2021
Chenghong Wang, Johes Bater, Kartik Nayak, Ashwin Machanavajjhala

On the Anonymity Guarantees of Anonymous Proof-of-Stake Protocols
Paper
Accepted in IEEE Security and Privacy (SP), 2021
Markulf Kohlweiss, Varun Madathil, Kartik Nayak, Alessandra Scafuro

Communication-Efficient BFT Protocols Using Small Trusted Hardware to Tolerate Minority Corruption
Paper
Brief Announcement, Accepted in International Symposium on Distributed Computing (DISC), 2021
Sravya Yandamuri, Ittai Abraham, Kartik Nayak, Michael K. Reiter

Good-case Latency of Byzantine Broadcast: a Complete Categorization
Paper
Accepted in Principles of Distributed Computing (PODC), 2021
Ittai Abraham, Kartik Nayak, Ling Ren, Zhuolun Xiang

RandPiper — Reconfiguration-Friendly Random Beacons with Quadratic Communication
Paper
Accepted in Computer and Communication Security (CCS), 2021
Aditya Bhat, Nibesh Shreshta, Aniket Kate, Kartik Nayak

BFT Protocol Forensics
Paper | Video
Accepted in Computer and Communication Security (CCS), 2021
Peiyao Sheng, Gerui Wang, Kartik Nayak, Sreeram Kannan, Pramod Viswanath

Strengthened Fault Tolerance in Byzantine Fault Tolerant Replication
Paper
Accepted in International Conference on Distributed Computing Systems (ICDCS), 2021
Zhuolun Xiang, Dahlia Malkhi, Kartik Nayak, Ling Ren

Perfectly Oblivious (Parallel) RAM Revisited, and Improved Constructions
Paper
Accepted in Information-Theoretic Cryptography (ITC), 2021
T-H. Hubert Chan, Wei-Kai Lin, Kartik Nayak, Elaine Sh

Classifying Trusted Hardware via Unidirectional Communication
Paper
Brief Announcement, Principles of Distributed Computing (PODC), 2021
Naama Ben-David, Kartik Nayak

Making Synchronous BFT Protocols Secure in the Presence of Mobile Sluggish Faults
Paper
Brief Announcement, Principles of Distributed Computing (PODC), 2021
Justin Kim, Vandan Mehta, Kartik Nayak, Nibesh Shrestha

Poirot: Private Contact Summary Aggregation
Paper | Project webpage | Poster | Video
NeurIPS PPML, 2020
ACM SenSys, 2020
Chenghong Wang, David Pujol, Yanping Zhang, Johes Bater, Matthew Lentz, Ashwin Machanavajjhala, Kartik Nayak, Lavanya Vasudevan, Jun Yang

On the Optimality of Optimistic Responsiveness
Paper
ACM Computer and Communications Security (CCS), 2020
Ittai Abraham, Kartik Nayak, Ling Ren, Nibesh Shrestha

Optimal Good-case Latency for Byzantine Broadcast and State Machine Replication
Paper
Brief Announcement, International Symposium on Distributed Computing (DISC), 2020
Ittai Abraham, Kartik Nayak, Ling Ren, Zhuolun Xiang

Improved Extension Protocols for Byzantine Broadcast and Agreement
Paper
International Symposium on Distributed Computing (DISC), 2020
Kartik Nayak, Ling Ren, Elaine Shi, Nitin H. Vaidya, Zhuolun Xiang

OptORAMa: Optimal Oblivious RAM
Paper
Eurocrypt, 2020
Gilad Asharov, Ilan Komargodski, Wei-Kai Lin, Kartik Nayak, Enoch Peserico, Elaine Shi

Sync HotStuff: Simple and Practical State Machine Replication
Paper | Code | Blog post | Short video
IEEE Security and Privacy (SP), 2020
Ittai Abraham, Dahlia Malkhi, Kartik Nayak, Ling Ren, Maofan Yin

Bucket Sort: A Simple Oblivious Sort
Paper
Symposium on Simplicity in Algorithms (SOSA), 2020
Gilad Asharov, T-H. Hubert Chan, Kartik Nayak, Rafael Pass, Ling Ren, Elaine Shi

Flexible Byzantine Fault Tolerance
Paper | Blog post
ACM Computer and Communications Security (CCS), 2019
Dahlia Malkhi, Kartik Nayak, Ling Ren

Communication Complexity of Byzantine Agreement, Revisited
Paper
Principles of Distributed Computing (PODC), 2019
Ittai Abraham, T-H. Hubert Chan, Danny Dolev, Kartik Nayak, Rafael Pass, Ling Ren, Elaine Shi

Locality-Preserving Oblivious RAM
Paper
Eurocrypt, 2019
Gilad Asharov, T-H. Hubert Chan, Kartik Nayak, Rafael Pass, Ling Ren, Elaine Shi

Synchronous Byzantine Agreement with Expected O(1) Rounds, Expected O(n2) Communication, and Optimal Resilience
Paper | Older version
Financial Cryptography and Data Security (FC), 2019
Ittai Abraham, Srinivas Devadas, Danny Dolev, Kartik Nayak, Ling Ren

Dfinity Consensus, Explored
Paper
Ittai Abraham, Dahlia Malkhi, Kartik Nayak, Ling Ren

More is Less: Perfectly Secure Oblivious Algorithms in the Multi-Server Setting
Paper
Asiacrypt, 2018
T-H. Hubert Chan, Jonathan Katz, Kartik Nayak, Antigoni Polychroniadou, Elaine Shi

Perfectly Secure Oblivious Parallel RAM
Paper
Theory of Cryptography Conference (TCC), 2018
T-H. Hubert Chan, Kartik Nayak, Elaine Shi

Solida: A Blockchain Protocol Based on Reconfigurable Byzantine Consensus
Paper
Principles of Distributed Systems (OPODIS), 2017
Ittai Abraham, Dahlia Malkhi, Kartik Nayak, Ling Ren, Alexander Spiegelman

Asymptotically Tight Bounds for Composing ORAM with PIR
Paper
Public Key Cryptography (PKC), 2017
Ittai Abraham, Christopher W. Fletcher, Kartik Nayak, Benny Pinkas, Ling Ren

HOP: Hardware makes Obfuscation Practical
Paper  | Code | Slides | Videos
Network and Distributed System Security (NDSS), 2017
Kartik Nayak, Christopher W. Fletcher, Ling Ren, Nishanth Chandran, Satya Lokam, Elaine Shi, Vipul Goyal

Stubborn Mining: Generalizing Selfish Mining and Combining with an Eclipse Attack
Paper | Code | Slides
IEEE European Symposium on Security and Privacy (Euro SP), 2016
Kartik Nayak, Srijan Kumar, Andrew Miller, Elaine Shi

An Oblivious Parallel RAM with O(log2 N) Parallel Runtime Blowup
Paper
Kartik Nayak, Jonathan Katz

GraphSC: Parallel Secure Computation Made Easy
Paper  | Code | Slides | Videos
IEEE Security and Privacy (SP), 2015
Kartik Nayak, Xiao Wang, Stratis Ioannidis, Udi Weinsberg, Nina Taft, Elaine Shi

ObliVM: A Programming Framework for Secure Computation
Paper | Code 
IEEE Security and Privacy (SP), 2015
Chang Liu, Xiao Wang, Kartik Nayak, Yan Huang, Elaine Shi

Oblivious Data Structures
Paper  | Slides
ACM Computer and Communications Security (CCS), 2014
Xiao Wang, Kartik Nayak, Chang Liu, T-H Hubert Chan, Elaine Shi, Emil Stefanov, Yan Huang

Some Vulnerabilities are Different than Others: Studying Vulnerabilities and Attack Surfaces in the Wild
Paper | Announcement | Slides | Video
Research in Attacks, Intrusions and Defenses (RAID), 2014
Kartik Nayak, Daniel Marino, Petros Efstathopoulos, Tudor Dumitras