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

The Garden-Hose Game and Application to Position-Based Quantum Cryptography

Harry Buhrman, Serge Fehr, Christian Schaffner, Florian Speelman

Published Jan 1, 2011• 0 citations
OpenAlex

Related papers

A game-theoretic security framework for quantum cryptography: Performance analysis and application

Songyang Han, Walter O. Krawec, Fei Miao

Quantum Information Processing•Sep 22, 2020•0 citations

Position-Based Quantum Cryptography and the Garden-Hose Game

Florian Speelman

We study position-based cryptography in the quantum setting. We examine a class of protocols that only require the communication of a single qubit and 2n bits of classical information. To this end, we define a new model of communication complexity, the garden-hose model, which enables us to prove upper bounds on the number of EPR pairs needed to attack such schemes. This model furthermore opens up a way to link the security of position-based quantum cryptography to traditional complexity theory.

arXiv:1210.4353•Oct 16, 2012•10 citations

Position-Based Quantum Cryptography: Impossibility and Constructions

Harry Buhrman, Nishanth Chandran, Serge Fehr +4 more

Lecture notes in computer science•Jan 1, 2011•59 citations

A survey of quantum games

Hong Mei Guo, Juheng Zhang, Gary J. Kœhler

Decision Support Systems•Jul 11, 2008•145 citations

On the riddle of coding equality function in the garden hose model

Oded Margalit

Recently, Harry Buhrman et al introduced a novel communication complexity model, called “garden-hose”. This model sprout from a research on using quantum properties to allow for position based cryptography. SAT is one of the fundamental NP-Complete problem - finding a satisfying assignment to a CNF (conjunctive Normal Form) formula, or proving that none exists. We will not get into the details of the quantum physics, neither we are going to explain the internal work of SAT solver. Instead we will start from the mathematical garden hose model; describe the way we used SAT solver as a tool; give some lower and upper bounds on implementing the equality function; and conclude with open questions.

Information Theory and Applications Workshop (ITA)•Feb 1, 2014•3 citations

New Bounds for the Garden-Hose Model

Hartmut Klauck, Supartha Podder

We show new results about the garden-hose model. Our main results include improved lower bounds based on non-deterministic communication complexity (leading to the previously unknown $Θ(n)$ bounds for Inner Product mod 2 and Disjointness), as well as an $O(n\cdot \log^3 n)$ upper bound for the Distributed Majority function (previously conjectured to have quadratic complexity). We show an efficient simulation of formulae made of AND, OR, XOR gates in the garden-hose model, which implies that lower bounds on the garden-hose complexity $GH(f)$ of the order $Ω(n^{2+ε})$ will be hard to obtain for explicit functions. Furthermore we study a time-bounded variant of the model, in which even modest savings in time can lead to exponential lower bounds on the size of garden-hose protocols.

arXiv:1412.4904•Leibniz international proceedings in informatics•Jan 1, 2014•13 citations
Recently, Harry Buhrman et al introduced a novel communication complexity model, called “garden-hose”. This model sprout from a research on using quantum properties to allow for position based cryptography. SAT is one of the fundamental NP-Complete problem - finding a satisfying assignment to a CNF (conjunctive Normal Form) formula, or proving that none exists. We will not get into the details of the quantum physics, neither we are going to explain the internal work of SAT solver. Instead we will start from the mathematical garden hose model; describe the way we used SAT solver as a tool; give some lower and upper bounds on implementing the equality function; and conclude with open questions.
We show new results about the garden-hose model. Our main results include improved lower bounds based on non-deterministic communication complexity (leading to the previously unknown Θ(n)Θ(n)Θ(n) bounds for Inner Product mod 2 and Disjointness), as well as an O(n⋅log⁡3n)O(n\cdot \log^3 n)O(n⋅log3n) upper bound for the Distributed Majority function (previously conjectured to have quadratic complexity). We show an efficient simulation of formulae made of AND, OR, XOR gates in the garden-hose model, which implies that lower bounds on the garden-hose complexity GH(f)GH(f)GH(f) of the order Ω(n2+ε)Ω(n^{2+ε})Ω(n2+ε) will be hard to obtain for explicit functions. Furthermore we study a time-bounded variant of the model, in which even modest savings in time can lead to exponential lower bounds on the size of garden-hose protocols.