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

Journal of Cryptology

Polynomial Runtime and Composability

Dennis Hofheinz, Dominique Unruh, Jörn Müller‐Quade

Published Aug 16, 2012• 24 citations
Publisher
DOI
10.1007/s00145-012-9127-4

Related papers

Concurrently Composable Security with Shielded Super-Polynomial Simulators

Brandon Broadnax, Nico Döttling, Gunnar Hartung +2 more

Lecture notes in computer science•Jan 1, 2017•19 citations

Polynomial Runtime and Composability.

Dennis Hofheinz, Dominique Unruh, Jörn Müller‐Quade

Abstract. To prove security of a multi-party cryptographic protocol, one often reduces attacks on the protocol to attacks on a suitable computational problem. Thus, if the computational problem is hard, then the protocol is secure. But to allow for a security reduction, the protocol itself and the attack on the protocol must be efficient, i.e., polynomialtime. Of course, the obvious way to enforce an overall polynomial runtime of the protocol is to require each individual protocol machine and adversarial entity to be polynomialtime. However, as the specific case of zero-knowledge protocols demonstrates, an a priori polynomial-time bound on all entities may not be an optimal choice because the running time of some machines needs to depend on that of others. As we want to be able to model arbitrary protocol tasks, we work in the Universal Composability framework (UC). This framework additionally provides strong composability guarantees. We will point out that in the UC setting, finding a useful notion of polynomial-time for the analysis of general protocols is a highly non-trivial task. Our goal in this work is to find a good and useful definition of polynomial-time for multiparty protocols in the UC setting that matches the intuition of what is feasible. A good

•Jan 1, 2009•8 citations

Algebraic Adversaries in the Universal Composability Framework

Michel Ferreira Abdalla, Manuel Barbosa, Jonathan I. Katz +2 more

Lecture notes in computer science•Jan 1, 2021•20 citations

Algorithms and Computation

Masanori Ohya, Igor Vasil'evich Volovich

Theoretical and mathematical physics•Jan 1, 2011•0 citations

Classical Simulation of Peaked Shallow Quantum Circuits

Sergey B. Bravyi, David Gosset, Yinchen Liu

An n-qubit quantum circuit is said to be peaked if it has an output probability that is at least inverse-polynomially large as a function of n. We describe a classical algorithm with quasipolynomial runtime nO(logn) that approximately samples from the output distribution of a peaked constant-depth circuit. We give even faster algorithms for circuits composed of nearest-neighbor gates on a D-dimensional grid of qubits, with polynomial runtime nO(1) if D=2 and almost-polynomial runtime nO(loglogn) for D>2. Our sampling algorithms can be used to estimate output probabilities of shallow circuits to within a given inverse-polynomial additive error, improving previously known methods. As a simple application, we obtain a quasipolynomial algorithm to estimate the magnitude of the expected value of any Pauli observable in the output state of a shallow circuit (which may or may not be peaked). This is a dramatic improvement over the prior state-of-the-art algorithm which had an exponential scaling in √n.

arXiv:2309.08405•ACM Symposium on Theory of Computing (STOC)•Jun 10, 2024•16 citations

Classical simulation of non-Gaussian bosonic circuits

Beatriz Dias, Robert König

The authors present efficient classical algorithms for simulating linear bosonic circuits applied to non-Gaussian states composed of superpositions of Gaussian states. Their approach, based on an augmented covariance matrix formalism, enables exact simulations with polynomial runtime in the number of modes and circuit size, and quadratic runtime in the number of superposition terms. They also present an approximate algorithm whose runtime is linear in the number of superposition terms.

arXiv:2403.19059•Physical Review A•Oct 1, 2024•23 citations
Abstract. To prove security of a multi-party cryptographic protocol, one often reduces attacks on the protocol to attacks on a suitable computational problem. Thus, if the computational problem is hard, then the protocol is secure. But to allow for a security reduction, the protocol itself and the attack on the protocol must be efficient, i.e., polynomialtime. Of course, the obvious way to enforce an overall polynomial runtime of the protocol is to require each individual protocol machine and adversarial entity to be polynomialtime. However, as the specific case of zero-knowledge protocols demonstrates, an a priori polynomial-time bound on all entities may not be an optimal choice because the running time of some machines needs to depend on that of others. As we want to be able to model arbitrary protocol tasks, we work in the Universal Composability framework (UC). This framework additionally provides strong composability guarantees. We will point out that in the UC setting, finding a useful notion of polynomial-time for the analysis of general protocols is a highly non-trivial task. Our goal in this work is to find a good and useful definition of polynomial-time for multiparty protocols in the UC setting that matches the intuition of what is feasible. A good
An n-qubit quantum circuit is said to be peaked if it has an output probability that is at least inverse-polynomially large as a function of n. We describe a classical algorithm with quasipolynomial runtime nO(logn) that approximately samples from the output distribution of a peaked constant-depth circuit. We give even faster algorithms for circuits composed of nearest-neighbor gates on a D-dimensional grid of qubits, with polynomial runtime nO(1) if D=2 and almost-polynomial runtime nO(loglogn) for D>2. Our sampling algorithms can be used to estimate output probabilities of shallow circuits to within a given inverse-polynomial additive error, improving previously known methods. As a simple application, we obtain a quasipolynomial algorithm to estimate the magnitude of the expected value of any Pauli observable in the output state of a shallow circuit (which may or may not be peaked). This is a dramatic improvement over the prior state-of-the-art algorithm which had an exponential scaling in √n.