ConferenceLeibniz International Proceedings in Informatics, LIPIcs · October 24, 2024
Today’s mainstream network timing models for distributed computing are synchrony, partial synchrony, and asynchrony. These models are coarse-grained and often make either too strong or too weak assumptions about the network. This paper introduces a new tim ...
Full textCite
ConferenceProceedings of the Annual ACM Symposium on Principles of Distributed Computing · June 17, 2024
The view synchronization problem lies at the heart of many Byzantine Fault Tolerant (BFT) State Machine Replication (SMR) protocols in the partial synchrony model, since these protocols are usually based on views. Liveness is guaranteed if honest processor ...
Full textCite
ConferenceLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) · January 1, 2024
Player-replaceability is a property of a blockchain protocol that ensures every step of the protocol is executed by an unpredictably random (small) set of players; this guarantees security against a fully adaptive adversary and is a crucial property in bui ...
Full textCite
ConferenceProceedings - IEEE Symposium on Security and Privacy · January 1, 2024
The Tor network enhances clients' privacy by routing traffic through an overlay network of volunteered intermediate relays. Tor employs a distributed protocol among nine hard-coded Directory Authority (DA) servers to securely disseminate information about ...
Full textCite
ConferenceCCS 2023 - Proceedings of the 2023 ACM SIGSAC Conference on Computer and Communications Security · November 15, 2023
Currently there exist many blockchains with weak trust guarantees, limiting applications and participation. Existing solutions to boost the trust using a stronger blockchain, e.g., via checkpointing, requires the weaker blockchain to give up sovereignty. I ...
Full textCite
ConferenceCCS 2023 - Proceedings of the 2023 ACM SIGSAC Conference on Computer and Communications Security · November 15, 2023
Protocols for state-machine replication (SMR) often trade off performance for resilience to network delay. In particular, protocols for asynchronous SMR tolerate arbitrary network delay but sacrifice throughput/latency when the network is fast, while parti ...
Full textCite
Journal ArticleDistributed Computing · March 1, 2023
As Byzantine Agreement (BA) protocols find application in large-scale decentralized cryptocurrencies, an increasingly important problem is to design BA protocols with improved communication complexity. A few existing works have shown how to achieve subquad ...
Full textCite
ConferenceLeibniz International Proceedings in Informatics, LIPIcs · February 1, 2023
Agreement protocols for partially synchronous networks tolerate fewer than one-third Byzantine faults. If parties are equipped with trusted hardware that prevents equivocation, then fault tolerance can be improved to fewer than one-half Byzantine faults, b ...
Full textCite
Journal ArticleProceedings of the VLDB Endowment · January 1, 2023
In this work, we propose Longshot, a novel design for secure outsourced database systems that supports ad-hoc queries through the use of secure multi-party computation and differential privacy. By combining these two techniques, we build and maintain data ...
Full textCite
ConferenceLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) · January 1, 2023
Time-lock puzzles (TLP) are a fascinating type of cryptographic problem that is easy to generate, but takes a certain time to solve, even when arbitrary parallel speedup is allowed. TLPs have wide-ranging applications including fairness, round efficient co ...
Full textCite
Conference32nd USENIX Security Symposium, USENIX Security 2023 · January 1, 2023
Safety, liveness, and privacy are three critical properties for any private proof-of-stake (PoS) blockchain. However, prior work (SP’21) has shown that to obtain safety and liveness, a PoS blockchain must in theory forgo privacy. Specifically, to ensure sa ...
Cite
Conference30th Annual Network and Distributed System Security Symposium, NDSS 2023 · January 1, 2023
Hashed Time-Locked Contracts (HTLCs) are a widely used primitive in blockchain systems such as payment channels, atomic swaps, etc. Unfortunately, HTLC is incentive-incompatible and is vulnerable to bribery attacks. The state-of-the-art solution is MAD-HTL ...
Full textCite
Conference30th Annual Network and Distributed System Security Symposium, NDSS 2023 · January 1, 2023
—Public random beacons publish random numbers at regular intervals, which anyone can obtain and verify. The design of public distributed random beacons has been an exciting research direction with significant implications for blockchains, voting, and beyon ...
Full textCite
Journal ArticleJournal of the ACM · December 20, 2022
Oblivious RAM (ORAM), first introduced in the ground-breaking work of Goldreich and Ostrovsky (STOC '87 and J. ACM '96) is a technique for provably obfuscating programs' access patterns, such that the access patterns leak no information about the programs' ...
Full textCite
ConferenceProceedings of the ACM Conference on Computer and Communications Security · November 7, 2022
A transaction fee mechanism (TFM) is an essential component of a blockchain protocol. However, a systematic evaluation of the real-world impact of TFMs is still absent. Using rich data from the Ethereum blockchain, the mempool, and exchanges, we study the ...
Full textCite
ConferenceProceedings of the ACM SIGMOD International Conference on Management of Data · June 10, 2022
In this paper, we consider secure outsourced growing databases (SOGDB) that support view-based query answering. These databases allow untrusted servers to privately maintain a materialized view. This allows servers to use only the materialized view for que ...
Full textCite
Journal ArticleJournal of Cryptology · April 1, 2022
Oblivious RAMs, introduced by Goldreich and Ostrovsky [JACM’96], compile any RAM program into one that is “memory oblivious,” i.e., the access pattern to the memory is independent of the input. All previous ORAM schemes, however, completely break the local ...
Full textCite
ConferenceLeibniz International Proceedings in Informatics, LIPIcs · February 1, 2022
This paper explores the good-case latency of synchronous Byzantine Fault Tolerant (BFT) consensus protocols in the rotating leader setting. We first present a lower bound that relates the latency of a broadcast when the sender is honest and the latency of ...
Full textCite
ConferenceLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) · January 1, 2022
We investigate the communication complexity of Byzantine agreement protocols for long messages against an adaptive adversary. In this setting, prior n-party protocols either achieved a communication complexity of O(nl· poly(κ) ) or O(nl+ n2· poly(κ) ) for ...
Full textCite
ConferenceProceedings of the ACM Conference on Computer and Communications Security · November 12, 2021
A random beacon provides a continuous public source of randomness and its applications range from public lotteries to zero-knowledge proofs. Existing random beacon protocols sacrifice either the fault tolerance or the communication complexity for security, ...
Full textCite
ConferenceProceedings of the ACM Conference on Computer and Communications Security · November 12, 2021
Byzantine fault-tolerant (BFT) protocols allow a group of replicas to come to consensus even when some of the replicas are Byzantine faulty. There exist multiple BFT protocols to securely tolerate an optimal number of faults t under different network setti ...
Full textCite
ConferenceLeibniz International Proceedings in Informatics, LIPIcs · October 1, 2021
Small trusted hardware primitives can improve fault tolerance of Byzantine Fault Tolerant (BFT) protocols to one-half faults. However, existing works achieve this at the cost of increased communication complexity. In this work, we explore the design of com ...
Full textCite
ConferenceProceedings of the Annual ACM Symposium on Principles of Distributed Computing · July 21, 2021
This paper explores the good-case latency of Byzantine fault-tolerant broadcast, motivated by the real-world latency and performance of practical state machine replication protocols. The good-case latency measures the time it takes for all non-faulty parti ...
Full textCite
ConferenceProceedings of the Annual ACM Symposium on Principles of Distributed Computing · July 21, 2021
It is well known that Byzantine fault tolerant (BFT) consensus cannot be solved in the classic asynchronous message passing model when one-third or more of the processes may be faulty. Since many modern applications require higher fault tolerance, this bou ...
Full textCite
ConferenceProceedings of the Annual ACM Symposium on Principles of Distributed Computing · July 21, 2021
BFT protocols in the synchronous setting rely on a strong assumption: every message sent by a party will arrive at its destination within a known bounded time. To allow some degree of asynchrony while still tolerating a minority corruption, recently, in Cr ...
Full textCite
ConferenceLeibniz International Proceedings in Informatics, LIPIcs · July 1, 2021
Oblivious RAM (ORAM) is a technique for compiling any RAM program to an oblivious counterpart, i.e., one whose access patterns do not leak information about the secret inputs. Similarly, Oblivious Parallel RAM (OPRAM) compiles a parallel RAM program to an ...
Full textCite
ConferenceProceedings - International Conference on Distributed Computing Systems · July 1, 2021
Byzantine fault tolerant (BFT) state machine replication (SMR) is an important building block for constructing permissioned blockchain systems. In contrast to Nakamoto Consensus where any block obtains higher assurance as buried deeper in the blockchain, i ...
Full textCite
ConferenceProceedings - IEEE Symposium on Security and Privacy · May 1, 2021
In proof-of-stake (PoS) blockchains, stakeholders that extend the chain are selected according to the amount of stake they own. In SP 2019 the "Ouroboros Crypsinous"system of Kerber et al. (and concurrently Ganesh et al. in EUROCRYPT 2019) presented a mech ...
Full textCite
ConferenceProceedings of the ACM SIGMOD International Conference on Management of Data · January 1, 2021
In this paper, we consider privacy-preserving update strategies for secure outsourced growing databases. Such databases allow appendonly data updates on the outsourced data structure while analysis is ongoing. Despite a plethora of solutions to securely ou ...
Full textCite
ConferenceSenSys 2020 - Proceedings of the 2020 18th ACM Conference on Embedded Networked Sensor Systems · November 16, 2020
Physical distancing between individuals is key to preventing the spread of a disease such as COVID-19. On the one hand, having access to information about physical interactions is critical for decision makers; on the other, this information is sensitive an ...
Full textCite
ConferenceProceedings of the ACM Conference on Computer and Communications Security · October 30, 2020
Synchronous consensus protocols, by definition, have a worst-case commit latency that depends on the bounded network delay. The notion of optimistic responsiveness was recently introduced to allow synchronous protocols to commit instantaneously when some o ...
Full textCite
ConferenceLeibniz International Proceedings in Informatics, LIPIcs · October 1, 2020
Byzantine broadcast (BB) and Byzantine agreement (BA) are two most fundamental problems and essential building blocks in distributed computing, and improving their efficiency is of interest to both theoreticians and practitioners. In this paper, we study e ...
Full textCite
ConferenceLeibniz International Proceedings in Informatics, LIPIcs · October 1, 2020
This paper investigates the problem good-case latency of Byzantine agreement, broadcast and state machine replication in the synchronous authenticated setting. The good-case latency measure captures the time it takes to reach agreement when all non-faulty ...
Full textCite
ConferenceProceedings - IEEE Symposium on Security and Privacy · May 1, 2020
Synchronous solutions for Byzantine Fault Tolerance (BFT) can tolerate up to minority faults. In this work, we present Sync HotStuff, a surprisingly simple and intuitive synchronous BFT solution that achieves consensus with a latency of 2? in the steady st ...
Full textCite
ConferenceLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) · January 1, 2020
Oblivious RAM (ORAM), first introduced in the ground-breaking work of Goldreich and Ostrovsky (STOC ’87 and J. ACM ’96) is a technique for provably obfuscating programs’ access patterns, such that the access patterns leak no information about the programs’ ...
Full textCite
Conference3rd SIAM Symposium on Simplicity in Algorithms, SOSA 2020 · January 1, 2020
We propose a conceptually simple oblivious sort and oblivious random permutation algorithms called bucket oblivious sort and bucket oblivious random permutation. Bucket oblivious sort uses 6n log n time (measured by the number of memory accesses) and 2Z cl ...
Cite
ConferenceProceedings of the ACM Conference on Computer and Communications Security · November 6, 2019
This paper introduces Flexible BFT, a new approach for BFT consensus solution design revolving around two pillars, stronger resilience and diversity. The first pillar, stronger resilience, involves a new fault model called alive-but-corrupt faults. Alive-b ...
Full textCite
ConferenceProceedings of the Annual ACM Symposium on Principles of Distributed Computing · July 16, 2019
As Byzantine Agreement (BA) protocols find application in large-scale decentralized cryptocurrencies, an increasingly important problem is to design BA protocols with improved communication complexity. A few existing works have shown how to achieve subquad ...
Full textCite
ConferenceLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) · January 1, 2019
Oblivious RAMs, introduced by Goldreich and Ostrovsky [JACM’96], compile any RAM program into one that is “memory oblivious”, i.e., the access pattern to the memory is independent of the input. All previous ORAM schemes, however, completely break the local ...
Full textCite
ConferenceLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) · January 1, 2019
We present new protocols for Byzantine agreement in the synchronous and authenticated setting, tolerating the optimal number of f faults among parties. Our protocols achieve an expected O(1) round complexity and an expected communication complexity. The ex ...
Full textCite
ConferenceLeibniz International Proceedings in Informatics, LIPIcs · March 1, 2018
The decentralized cryptocurrency Bitcoin has experienced great success but also encountered many challenges. One of the challenges has been the long confirmation time. Another challenge is the lack of incentives at certain steps of the protocol, raising co ...
Full textCite
ConferenceLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) · January 1, 2018
The problem of Oblivious RAM (ORAM) has traditionally been studied in the single-server setting, but more recently the multi-server setting has also been considered. Yet it is still unclear whether the multi-server setting has any inherent advantages, e.g. ...
Full textCite
ConferenceLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) · January 1, 2018
We show that PRAMs can be obliviously simulated with perfect security, incurring only blowup in parallel runtime, blowup in total work, and O(1) blowup in space relative to the original PRAM. Our results advance the theoretical understanding of Oblivious ( ...
Full textCite
ConferenceLeibniz International Proceedings in Informatics, LIPIcs · October 1, 2017
This paper presents new protocols for Byzantine state machine replication and Byzantine agreement in the synchronous and authenticated setting. The PBFT state machine replication protocol tolerates f Byzantine faults in an asynchronous setting using n = 3f ...
Full textCite
ConferenceProceedings - 2016 IEEE Cybersecurity Development, SecDev 2016 · February 1, 2017
While several mature cryptographic frameworks exist, and have been utilized for building complex applications, developers often use these frameworks incorrectly and introduce security vulnerabilities. This stems from several challenges, including (i) an ex ...
Full textCite
ConferenceLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) · January 1, 2017
Oblivious RAM (ORAM) is a cryptographic primitive that allows a trusted client to outsource storage to an untrusted server while hiding the client’s memory access patterns to the server. The last three decades of research on ORAMs have reduced the bandwidt ...
Full textCite
Conference24th Annual Network and Distributed System Security Symposium, NDSS 2017 · January 1, 2017
Program obfuscation is a central primitive in cryptography, and has important real-world applications in protecting software from IP theft. However, well known results from the cryptographic literature have shown that software only virtual black box (VBB) ...
Full textCite
ConferenceOnward! 2016 - Proceedings of the 2016 ACM International Symposium on New Ideas, New Paradigms, and Reflections on Programming and Software · October 20, 2016
Several mature cryptographic frameworks are available, and they have been utilized for building complex applications. However, developers often use these frameworks incorrectly and introduce security vulnerabilities. This is because current cryptographic f ...
Full textCite
ConferenceProceedings - 2016 IEEE European Symposium on Security and Privacy, EURO S and P 2016 · May 9, 2016
Selfish mining, originally discovered by Eyal et al. [9], is a well-known attack where a selfish miner, under certain conditions, can gain a disproportionate share of reward by deviating from the honest behavior. In this paper, we expand the mining strateg ...
Full textCite
ConferenceProceedings - IEEE Symposium on Security and Privacy · July 17, 2015
We design and develop Obli VM, a programming framework for secure computation. ObliVM offers a domain specific language designed for compilation of programs into efficient oblivious representations suitable for secure computation. ObliVM offers a powerful, ...
Full textCite
ConferenceProceedings - IEEE Symposium on Security and Privacy · July 17, 2015
We propose introducing modern parallel programming paradigms to secure computation, enabling their secure execution on large datasets. To address this challenge, we present Graph SC, a framework that (i) provides a programming paradigm that allows non-cryp ...
Full textCite
ConferenceProceedings of the ACM Conference on Computer and Communications Security · November 3, 2014
We design novel, asymptotically more efficient data structures and algorithms for programs whose data access patterns exhibit some degree of predictability. To this end, we propose two novel techniques, a pointer-based technique and a locality-based techni ...
Full textCite
ConferenceLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) · January 1, 2014
The security of deployed and actively used systems is a moving target, influenced by factors not captured in the existing security metrics. For example, the count and severity of vulnerabilities in source code, as well as the corresponding attack surface, ...
Full textCite
