The Garden-Hose Model

Abstract

We define a new model of communication complexity, called the garden-hose model. Informally, the garden-hose complexity of a function f:{0,1}^n x {0,1}^n to {0,1} is given by the minimal number of water pipes that need to be shared between two parties, Alice and Bob, in order for them to compute the function f as follows: Alice connects her ends of the pipes in a way that is determined solely by her input x \in {0,1}^n and, similarly, Bob connects his ends of the pipes in a way that is determined solely by his input y \in {0,1}^n. Alice turns on the water tap that she also connected to one of the pipes. Then, the water comes out on Alice's or Bob's side depending on the function value f(x,y). We prove almost-linear lower bounds on the garden-hose complexity for concrete functions like inner product, majority, and equality, and we show the existence of functions with exponential garden-hose complexity. Furthermore, we show a connection to classical complexity theory by proving that all functions computable in log-space have polynomial garden-hose complexity. We consider a randomized variant of the garden-hose complexity, where Alice and Bob hold pre-shared randomness, and a quantum variant, where Alice and Bob hold pre-shared quantum entanglement, and we show that the randomized garden-hose complexity is within a polynomial factor of the deterministic garden-hose complexity. Examples of (partial) functions are given where the quantum garden-hose complexity is logarithmic in n while the classical garden-hose complexity can be lower bounded by n^c for constant c>0. Finally, we show an interesting connection between the garden-hose model and the (in)security of a certain class of quantum position-verification schemes.

19 pages, 1 figure, accepted at QCRYPT 2011. v2: fixed problem with missing references, no changes in content, v3: equivalent to final ITCS 2013 proceedings version. Substantial updates: re-ordering of subjects, introduction of randomized and quantum garden-hose models. Previous Section 3 regarding the optimality of a particular attack is removed but can be found in arxiv:1210.4353

References in corpus (6)

• Asymptotic teleportation scheme as a universal programmable quantum processor
• Simplified instantaneous non-local quantum computation with applications to position-based cryptography
• Quantum teleportation scheme by selecting one of multiple output ports
• Quantum Tagging: Authenticating Location via Quantum Information and Relativistic Signalling Constraints
• Location-Dependent Communications using Quantum Entanglement
• Insecurity of position-based quantum cryptography protocols against entanglement attacks

Cited by in corpus (8)

• Quantum Cryptography Beyond Quantum Key Distribution
• Complexity and entanglement in non-local computation and holography
• A single-qubit position verification protocol that is secure against multi-qubit attacks
• Geometry of Banach spaces: a new route towards Position Based Cryptography
• Bounds on Instantaneous Nonlocal Quantum Computation
• Relating non-local quantum computation to information theoretic cryptography
• Code-routing: a new attack on position verification
• Linear gate bounds against natural functions for position-verification