Search Results

Documents authored by Zhou, Hong-Sheng

Document
Brief Announcement
DOI: 10.4230/LIPIcs.DISC.2024.45
Brief Announcement: Best-Possible Unpredictable Proof-Of-Stake

Authors: Lei Fan, Jonathan Katz, Zhenghao Lu, Phuc Thai, and Hong-Sheng Zhou

Published in: LIPIcs, Volume 319, 38th International Symposium on Distributed Computing (DISC 2024)

Abstract
The proof-of-stake (PoS) protocols aim to reduce the unnecessary computing power waste seen in Bitcoin. Various practical and provably secure designs have been proposed, like Ouroboros Praos (Eurocrypt 2018) and Snow White (FC 2019). However, the essential security property of unpredictability in these protocols remains insufficiently explored. This paper delves into this property in the cryptographic setting to achieve the "best possible" unpredictability for PoS. We first present an impossibility result for all PoS protocols under the single-extension design framework, where each honest player extends one chain per round. The state-of-the-art permissionless PoS protocols (e.g., Praos, Snow White, and more), are all under this single-extension framework. Our impossibility result states that, if a single-extension PoS protocol achieves the best possible unpredictability, then this protocol cannot be proven secure unless more than 73% of stake is honest. To overcome this impossibility, we introduce a new design framework called multi-extension PoS, allowing each honest player to extend multiple chains using a greedy strategy in a round. This strategy allows us to construct a class of PoS protocols that achieve the best possible unpredictability. It is noteworthy that these protocols can be proven secure, assuming a much smaller fraction (e.g., 57%) of stake to be honest.
Cite as

Lei Fan, Jonathan Katz, Zhenghao Lu, Phuc Thai, and Hong-Sheng Zhou. Brief Announcement: Best-Possible Unpredictable Proof-Of-Stake. In 38th International Symposium on Distributed Computing (DISC 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 319, pp. 45:1-45:7, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{fan_et_al:LIPIcs.DISC.2024.45,
  author =	{Fan, Lei and Katz, Jonathan and Lu, Zhenghao and Thai, Phuc and Zhou, Hong-Sheng},
  title =	{{Brief Announcement: Best-Possible Unpredictable Proof-Of-Stake}},
  booktitle =	{38th International Symposium on Distributed Computing (DISC 2024)},
  pages =	{45:1--45:7},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-352-2},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{319},
  editor =	{Alistarh, Dan},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.DISC.2024.45},
  URN =		{urn:nbn:de:0030-drops-212731},
  doi =		{10.4230/LIPIcs.DISC.2024.45},
  annote =	{Keywords: blockchain, consensus, proof-of-stake, unpredictability}
}
Document
DOI: 10.4230/LIPIcs.TQC.2020.6
Towards Quantum One-Time Memories from Stateless Hardware

Authors: Anne Broadbent, Sevag Gharibian, and Hong-Sheng Zhou

Published in: LIPIcs, Volume 158, 15th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2020)

Abstract
A central tenet of theoretical cryptography is the study of the minimal assumptions required to implement a given cryptographic primitive. One such primitive is the one-time memory (OTM), introduced by Goldwasser, Kalai, and Rothblum [CRYPTO 2008], which is a classical functionality modeled after a non-interactive 1-out-of-2 oblivious transfer, and which is complete for one-time classical and quantum programs. It is known that secure OTMs do not exist in the standard model in both the classical and quantum settings. Here, we propose a scheme for using quantum information, together with the assumption of stateless (i.e., reusable) hardware tokens, to build statistically secure OTMs. Via the semidefinite programming-based quantum games framework of Gutoski and Watrous [STOC 2007], we prove security for a malicious receiver, against a linear number of adaptive queries to the token, in the quantum universal composability framework, but leave open the question of security against a polynomial amount of queries. Compared to alternative schemes derived from the literature on quantum money, our scheme is technologically simple since it is of the "prepare-and-measure" type. We also show our scheme is "tight" according to two scenarios.
Cite as

Anne Broadbent, Sevag Gharibian, and Hong-Sheng Zhou. Towards Quantum One-Time Memories from Stateless Hardware. In 15th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 158, pp. 6:1-6:25, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{broadbent_et_al:LIPIcs.TQC.2020.6,
  author =	{Broadbent, Anne and Gharibian, Sevag and Zhou, Hong-Sheng},
  title =	{{Towards Quantum One-Time Memories from Stateless Hardware}},
  booktitle =	{15th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2020)},
  pages =	{6:1--6:25},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-146-7},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{158},
  editor =	{Flammia, Steven T.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.TQC.2020.6},
  URN =		{urn:nbn:de:0030-drops-120654},
  doi =		{10.4230/LIPIcs.TQC.2020.6},
  annote =	{Keywords: quantum cryptography, one-time memories, semi-definite programming}
}
Document
DOI: 10.4230/DagSemProc.08491.5
Sound and Fine-grain Specification of Ideal Functionalities

Authors: Juan Garay, Aggelos Kiayias, and Hong-Sheng Zhou

Published in: Dagstuhl Seminar Proceedings, Volume 8491, Theoretical Foundations of Practical Information Security (2009)

Abstract
Nowadays it is widely accepted to formulate the security of a protocol carrying out a given task via the "trusted-party paradigm," where the protocol execution is compared with an ideal process where the outputs are computed by a trusted party that sees all the inputs. A protocol is said to securely carry out a given task if running the protocol with a realistic adversary amounts to "emulating" the ideal process with the appropriate trusted party. In the Universal Composability (UC) framework the program run by the trusted party is called an ideal functionality. While this simulation-based security formulation provides strong security guarantees, its usefulness is contingent on the properties and correct specification of the ideal functionality, which, as demonstrated in recent years by the coexistence of complex, multiple functionalities for the same task as well as by their "unstable" nature, does not seem to be an easy task. In this paper we address this problem, by introducing a general methodology for the sound specification of ideal functionalities. First, we introduce the class of canonical ideal functionalities for a cryptographic task, which unifies the syntactic specification of a large class of cryptographic tasks under the same basic template functionality. Furthermore, this representation enables the isolation of the individual properties of a cryptographic task as separate members of the corresponding class. By endowing the class of canonical functionalities with an algebraic structure we are able to combine basic functionalities to a single final canonical functionality for a given task. Effectively, this puts forth a bottom-up approach for the specification of ideal functionalities: first one defines a set of basic constituent functionalities for the task at hand, and then combines them into a single ideal functionality taking advantage of the algebraic structure. In our framework, the constituent functionalities of a task can be derived either directly or, following a translation strategy we introduce, from existing game-based definitions; such definitions have in many cases captured desired individual properties of cryptographic tasks, albeit in less adversarial settings than universal composition. Our translation methodology entails a sequence of steps that derive a corresponding canonical functionality given a game-based definition. In this way, we obtain a well-defined mapping of game-based security properties to their corresponding UC counterparts. Finally, we demonstrate the power of our approach by applying our methodology to a variety of basic cryptographic tasks, including commitments, digital signatures, zero-knowledge proofs, and oblivious transfer. While in some cases our derived canonical functionalities are equivalent to existing formulations, thus attesting to the validity of our approach, in others they differ, enabling us to "debug" previous definitions and pinpoint their shortcomings.
Cite as

Juan Garay, Aggelos Kiayias, and Hong-Sheng Zhou. Sound and Fine-grain Specification of Ideal Functionalities. In Theoretical Foundations of Practical Information Security. Dagstuhl Seminar Proceedings, Volume 8491, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2009)

Copy BibTex To Clipboard

@InProceedings{garay_et_al:DagSemProc.08491.5,
  author =	{Garay, Juan and Kiayias, Aggelos and Zhou, Hong-Sheng},
  title =	{{Sound and Fine-grain Specification of Ideal Functionalities}},
  booktitle =	{Theoretical Foundations of Practical Information Security},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2009},
  volume =	{8491},
  editor =	{Ran Canetti and Shafi Goldwasser and G\"{u}nter M\"{u}ller and Rainer Steinwandt},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagSemProc.08491.5},
  URN =		{urn:nbn:de:0030-drops-18911},
  doi =		{10.4230/DagSemProc.08491.5},
  annote =	{Keywords: Security definitions, universal composability, cryptographic protocols, lattices and partial orders.}
}
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact