Papers

[Manuscript] Communication and Round Efficient Parallel Broadcast Protocols
Paper
Ittai Abraham, Kartik Nayak, Nibesh Shrestha

[Manuscript] Breaking the Chains of Rationality: Understanding the Limitations to and Obtaining Order Policy Enforcement
Paper | Talk
Sarisht Wadhwa, Luca Zanolini, Francesco D’Amato, Aditya Asgaonkar, Fan Zhang, Kartik Nayak

Abraxas: Throughput-Efficient Hybrid Asynchronous Consensus
Paper
Accepted in ACM CCS, 2023
Erica Blum, Jonathan Katz, Julian Loss, Kartik Nayak, Simon Ochsenreither

Private Proof-of-Stake Blockchains using Differentially-Private Stake Distortion
Paper | Talk
Published in Usenix Security, 2023
Chenghong Wang, David Pujol, Kartik Nayak, Ashwin Machanavajjhala

[Tech Report] HotStuff-2: Optimal Two-Phase Responsive BFT
Paper | Blog post
Dahlia Malkhi, Kartik Nayak

Longshot: Indexing Growing Databases using MPC and Differential Privacy
Paper
Published in Very Large Data Bases (VLDB) Conference, 2023
Yanping Zhang, Johes Bater, Kartik Nayak, Ashwin Machanavajjhala

Player-Replaceability and Forensic Support are Two Sides of the Same (Crypto) Coin
Paper
Published in Financial Cryptography (FC), 2023
Sreeram Kannan, Kartik Nayak, Peiyao Sheng, Pramod Viswanath, Gerui Wang

He-HTLC: Revisiting Incentives in HTLC
Paper | Blog post | Talk
Published in Network and Distributed Systems Security (NDSS), 2023
Sarisht Wadhwa, Jannis Stoeter, Fan Zhang, Kartik Nayak

OptRand: Optimistically Responsive Distributed Random Beacons
Paper
Published in Network and Distributed Systems Security (NDSS), 2023
Adithya Bhat, Nibesh Shrestha, Aniket Kate, Kartik Nayak

TrustBoost: Boosting Trust among Interoperable Blockchains
Paper
Accepted in ACM CCS, 2023
Xuechao Wang, Peiyao Sheng, Sreeram Kannan, Kartik Nayak, Pramod Viswanath

Transparent Batchable Time-lock Puzzles and Applications to Byzantine Consensus
Paper
Published in Public Key Cryptography (PKC), 2023
Shravan Srinivasan, Julian Loss, Giulio Malavolta, Kartik Nayak, Charalampos Papamanthou, and Sri Aravinda Krishnan Thyagarajan

Efficient Adaptively-Secure Byzantine Agreement for Long Messages
Paper | Talk
Published in Asiacrypt 2022
Amey Bhangale, Chen-Da Liu-Zhang, Julian Loss, Kartik Nayak

Communication-Efficient BFT Protocols Using Small Trusted Hardware to Tolerate Minority Corruption
Paper
Published in OPODIS, 2022
Sravya Yandamuri, Ittai Abraham, Kartik Nayak, Michael K. Reiter

Empirical Analysis of EIP-1559: Transaction Fees, Waiting Time, and Consensus Security
Paper | Blog post
Published in CCS 2022
Yulin Liu, Yuxuan Lu, Kartik Nayak, Fan Zhang, Luyao Zhang, Yinhong Zhao

[Manuscript] Efficient Synchronous Distributed Key Generation Without Broadcasts
Paper
Nibesh Shrestha, Adithya Bhat, Aniket Kate, Kartik Nayak

IncShrink: Architecting Efficient Outsourced Database using Incremental MPC and Differential Privacy
Paper
Published in SIGMOD 2022
Chenghong Wang, Johes Bater, Kartik Nayak, Ashwin Machanavajjhala

Locality-Preserving Oblivious RAM
Paper
Published in Journal of Cryptology
(Journal version of Eurocrypt 2019 paper)
Gilad Asharov, T-H. Hubert Chan, Kartik Nayak, Rafael Pass, Ling Ren, Elaine Shi

Communication Complexity of Byzantine Agreement, Revisited
Paper
Published in Distributed Computing Journal, 2022
Ittai Abraham, T-H. Hubert Chan, Danny Dolev, Kartik Nayak, Rafael Pass, Ling Ren, Elaine Shi

Optimal Good-case Latency for Rotating Leader Synchronous BFT
Paper
Published in OPODIS 2021
Best Paper Award: link
Ittai Abraham, Kartik Nayak, Nibesh Shrestha

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

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

On the Anonymity Guarantees of Anonymous Proof-of-Stake Protocols
Paper | Video
Published 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, Published 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
Published in Principles of Distributed Computing (PODC), 2021
Ittai Abraham, Kartik Nayak, Ling Ren, Zhuolun Xiang

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

BFT Protocol Forensics
Paper | Video | Blog post
Published in Computer and Communication Security (CCS), 2021
Best Paper Runner Up at ACM CCS
Peiyao Sheng, Gerui Wang, Kartik Nayak, Sreeram Kannan, Pramod Viswanath

Strengthened Fault Tolerance in Byzantine Fault Tolerant Replication
Paper
Published 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
Published 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

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(n²) 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(log² 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