Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

Lecture notes in computer science

On the relationship among cryptographic physical assumptions

Tatsuaki Okamoto

Published Jan 1, 1993• 3 citations
Publisher
DOI
10.1007/3-540-57568-5_268

Related papers

A Survey On Cryttograthic Assumptions

Hyunyong Shin

The security of many cryptosystems are based on several cryptographic assumptions. In this paper, we survey on some cryptographic assumptions which are widely used and their relationship. We explain the bit commitment scheme and oblivious transfer somewhat in detail.

Information Security and Cryptology•Jan 1, 1992•0 citations

Towards Verifying Physical Assumption in Card-Based Cryptography

Masahisa Shimano, Kazuo Sakiyama, Daiki Miyahara

Lecture notes in computer science•Jan 1, 2023•1 citation

Quantum One-Way Functions and Related Cryptographic Primitives

Georgios M. Nikolopoulos

Quantum cryptographic primitives beyond key distribution remain a less well understood area of research. In classical cryptography, one-way functions underpin nearly all standard cryptographic protocols, motivating the search for meaningful quantum analogues and for a clear understanding of the physical and computational mechanisms that could enforce one-wayness. In this article, we review quantum one-way functions and a range of closely related quantum-state primitives, including one-way state generators, pseudorandom quantum states, and efficiently indistinguishable pairs of states. We discuss both computational and information-theoretic notions of quantum one-wayness, emphasizing the different adversarial models and security assumptions that underlie these constructions. We compare and contrast the various proposed primitives, and clarify their conceptual relationships. Particular emphasis is placed on questions of physical realizability, experimental feasibility, and robustness to noise. Finally, we outline open problems and future directions toward the development of practical quantum cryptographic primitives beyond key distribution, and the emergence of a broader quantum-cryptographic ecosystem.

quant-pharXiv:2608.05754•New Journal of Physics•Aug 7, 2026•1 citation

Cryptographic Complexity Classes and Computational Intractability Assumptions

Hemanta K. Maji, Manoj Prabhakaran, Mike Rosulek

Which computational complexity assumptions are inherent to cryptography? We present a broad framework to pose and investigate this question. We first aim to understand the “cryptographic complexity ” of various tasks, independent of any computational assumptions. In our framework the cryptographic tasks are modeled as multi-party computation functionalities. We consider a universally composable secure protocol for one task given access to another task as the most natural complexity reduction between the two tasks. Some of these cryptographic complexity reductions are unconditional, others are unconditionally non-existent, but the vast majority appear to depend on computational assumptions; it is this relationship with computational assumptions that we study. In our detailed investigation of large classes of 2-party functionalities, we find that every reduction we are able to classify turns out to be unconditionally true or false, or else equivalent to the existence of one-way functions (OWF) or of semi-honest (equivalently, standalone-secure) oblivious transfer protocols (sh-OT). This leads us to conjecture that there are only a small finite number of distinct (i.e., black-box separable) computational assump-tions that are inherent among the infinite number of different cryptographic reductions in our framework. On moving to 3-party functionalities, there does exist a natural computational assumption, distinct from the OWF and sh-OT assumptions (namely, the existence of a key agreement protocol) that manifests itself as a cryptographic

International Conference on Supercomputing•Jan 1, 2009•12 citations

Theory of Cryptography

Joe Kilian

•Jan 1, 2005•0 citations

Theory of Cryptography

Salil Vadhan

•Jan 1, 2007•1 citation
Quantum cryptographic primitives beyond key distribution remain a less well understood area of research. In classical cryptography, one-way functions underpin nearly all standard cryptographic protocols, motivating the search for meaningful quantum analogues and for a clear understanding of the physical and computational mechanisms that could enforce one-wayness. In this article, we review quantum one-way functions and a range of closely related quantum-state primitives, including one-way state generators, pseudorandom quantum states, and efficiently indistinguishable pairs of states. We discuss both computational and information-theoretic notions of quantum one-wayness, emphasizing the different adversarial models and security assumptions that underlie these constructions. We compare and contrast the various proposed primitives, and clarify their conceptual relationships. Particular emphasis is placed on questions of physical realizability, experimental feasibility, and robustness to noise. Finally, we outline open problems and future directions toward the development of practical quantum cryptographic primitives beyond key distribution, and the emergence of a broader quantum-cryptographic ecosystem.
Which computational complexity assumptions are inherent to cryptography? We present a broad framework to pose and investigate this question. We first aim to understand the “cryptographic complexity ” of various tasks, independent of any computational assumptions. In our framework the cryptographic tasks are modeled as multi-party computation functionalities. We consider a universally composable secure protocol for one task given access to another task as the most natural complexity reduction between the two tasks. Some of these cryptographic complexity reductions are unconditional, others are unconditionally non-existent, but the vast majority appear to depend on computational assumptions; it is this relationship with computational assumptions that we study. In our detailed investigation of large classes of 2-party functionalities, we find that every reduction we are able to classify turns out to be unconditionally true or false, or else equivalent to the existence of one-way functions (OWF) or of semi-honest (equivalently, standalone-secure) oblivious transfer protocols (sh-OT). This leads us to conjecture that there are only a small finite number of distinct (i.e., black-box separable) computational assump-tions that are inherent among the infinite number of different cryptographic reductions in our framework. On moving to 3-party functionalities, there does exist a natural computational assumption, distinct from the OWF and sh-OT assumptions (namely, the existence of a key agreement protocol) that manifests itself as a cryptographic