PaperlayerView exact revision on arXiv

Source-linked AI summary

Towards the Impossibility of Non-Signalling Privacy Amplification from Time-Like Ordering Constraints

Rotem Arnon, Esther Hänggi, Amnon Ta-Shma

arXiv:1205.3736v2quant-phcs.CR

TL;DR

The paper asks whether privacy amplification remains impossible against non-signalling adversaries when assumptions are strengthened toward physically relevant forward-in-time signalling constraints. It extends the prior adversarial proof to stricter conditions and shows that no hash function can amplify privacy under them, while leaving broader interactive protocols open.

  • Problem

    Privacy amplification is impossible under non-signalling only between Alice and Bob when signalling within their laboratories is allowed, leaving physically relevant intermediate assumptions unresolved.

    Source: §1.1 · p. 1, §1.3 · p. 4, §1.5 · p. 5

  • Method

    The paper adds many non-signalling conditions, constructs a specific system, and extends the adversarial strategy from [11] to prove the result under stricter assumptions.

    Source: §1.5 · p. 5, §2.2 · p. 7, §3.2 · p. 13

  • Results

    For every hash function, a system satisfying the paper’s assumptions has distance from uniform at least c(ε), so privacy amplification remains impossible.

    Source: §3.2 · p. 14, §4.2 · p. 22

  • Takeaways & Limitations

    The impossibility result also applies to almost backward non-signalling systems and narrows the assumptions separating known impossibility from possible privacy amplification.

    Source: §1.5 · p. 5, §5 · p. 22

    Whether privacy amplification becomes possible under exact backward non-signalling assumptions or interactive protocols using both X and Y remains open.

    Source: §5 · p. 22

Abstract

from arXiv · show

In the past few years there was a growing interest in proving the security of cryptographic protocols, such as key distribution protocols, from the sole assumption that the systems of Alice and Bob cannot signal to each other. This can be achieved by making sure that Alice and Bob perform their measurements in a space-like separated way (and therefore signalling is impossible according to the non-signalling postulate of relativity theory) or even by shielding their apparatus. Unfortunately, it was proven in [E. Haenggi, R. Renner, and S. Wolf. The impossibility of non-signaling privacy amplification] that, no matter what hash function we use, privacy amplification is impossible if we only impose non-signalling conditions between Alice and Bob and not within their systems. In this letter we reduce the gap between the assumptions of Haenggi et al. and the physical relevant assumptions, from an experimental point of view, which say that the systems can only signal forward in time within the systems of Alice and Bob. We consider a set of assumptions which is very close to the conditions above and prove that the impossibility result of Haenggi et al. still holds.

1 Introduction and Contribution

The paper studies device-independent cryptography against non-signalling adversaries and asks whether partially secret correlations can be privacy-amplified under physically motivated restrictions. It shows that impossibility persists under assumptions close to forward-in-time signalling constraints.

1.1 Non-signalling cryptography

  • Security is sought from Alice and Bob’s observed correlations while shielding their systems or using space-like separation prevents information leakage to Eve.The protocols are device-independent and allow a super-quantum adversary limited only by non-signalling.Source: §1.1 · pp. 1–2

1.2 Systems and correlations

  • PR-boxes generate non-local correlations satisfying X ⊕ Y = U·V, while unbiased boxes with error ε provide only partial secrecy.Perfect PR-boxes would provide perfect secrecy, but physical implementations require noisy approximations.Source: §1.2 · p. 3

1.3 Privacy amplification

  • Privacy amplification applies a hash function to several partially secret outputs to produce a shorter key whose distance from an ideal secret key decreases with the number of systems.Impossibility requires a system whose secrecy remains bounded away from ideality for every hash function.Source: §1.3 · p. 4

1.4 Related work

  • Prior work established impossibility when signalling is allowed within laboratories, whereas full non-signalling conditions permit privacy amplification; the forward-in-time setting remained largely unresolved.Before this work, impossibility in that intermediate setting was known only for XOR and AND functions.Source: §1.4 · p. 5

1.5 Contribution

  • The paper narrows this gap by imposing stricter non-signalling assumptions close to forward-in-time signalling and extending the adversarial strategy from [11].The proof shows that the strategy remains valid under these additional conditions and implies the result for almost backward non-signalling systems.Source: §1.5 · p. 5

1.6 Outline

  • The letter defines non-signalling conditions and a counterexample system, proves the main theorem, derives Corollary 3.5, and then discusses open questions.The open questions concern whether the differing assumptions explain the adversary’s power and whether interactive protocols using both outputs could help.Source: §1.6 · p. 5, §1.5 · p. 5

2 Preliminaries

This section establishes the notation, assumptions, distance measures, and adversary models used throughout the letter. It formalizes non-signalling adversaries through measurement-induced system partitions, including the one-bit secret-key case.

2.1 Notations

  • The notation defines bit restrictions, complementary index sets, and conditional distributions for correlated random variables.Source: §2.1 · p. 6

2.2 Non-signalling systems

  • The framework distinguishes full, Alice–Bob, backward, and almost backward non-signalling conditions, with the considered conditions combining Alice–Bob non-signalling and almost backward non-signalling.Full non-signalling is experimentally impractical, whereas forward-in-time-only signalling can arise from sequential measurements with apparatus memory; Figure 4 visualizes the distinctions.Source: §2.2 · pp. 6–7, Figure 4 · p. 8

2.3 Distance measures

  • Distances between systems are defined through a distinguisher’s maximum guessing advantage, including adaptive measurement order, with distance from uniform comparing a key–adversary system to an independent uniform key.Source: §2.3 · pp. 9–10

2.4 Modeling non-signalling adversaries

  • Non-signalling adversaries are modeled as partitions into weighted conditional systems that each preserve the imposed non-signalling conditions, and these partitions cover exactly all possible adversarial strategies.The model follows [11, 10, 12], treats Eve’s input as selecting a convex decomposition and her output as identifying a component, and impossibility proofs may reduce Eve’s information to a binary variable [11].Source: §2.4 · pp. 11–12
  • A partition is equivalent to choosing a measurement W = w, allowing the key’s distance from uniform to be written using the partition itself.Source: §2.4 · p. 12
  • The analysis restricts attention to protocols in which Alice and Bob output one secret bit, simplifying the distance-from-uniform expression.Source: §2.4 · p. 12
  • Lemma 2.16 characterizes the case K = f(X) for binary-valued f, with U = u, V = v, and strategy W = w defined by a partition; it is Lemma 5.1 in [10].The proof is referred to Lemma 5.1 in [10].Source: §2.4 · p. 12

3 The Non-signalling Assumptions

Section 3 starts from product systems of imperfect PR-boxes where Alice and Bob cannot signal to each other, then adds stronger within-system non-signalling equations. These stricter assumptions still permit systems that defeat privacy amplification, including almost backward non-signalling systems and systems separately non-signalling on Alice’s and Bob’s sides.

3.1 The basic assumptions

  • The basic model uses n independent unbiased PR-boxes with error ε, while requiring that Alice and Bob cannot signal to each other for every adversary outcome.The product system is defined from n copies of single-box systems, and the bipartite marginal satisfies the Alice-to-Bob and Bob-to-Alice non-signalling conditions.Source: §3.1 · pp. 12–13
  • The paper investigates whether privacy amplification becomes possible between the minimal Alice–Bob condition and full non-signalling, focusing on almost backward non-signalling assumptions.It formalizes additional equations beyond the basic condition and asks what happens when only a subset of the full linear non-signalling equations is imposed.Source: §3.1 · p. 13

3.2 Our additional assumptions

  • Definition 3.2 adds equations ensuring that each pair A_i and B_i together cannot signal to the remaining parties, while still not implying full non-signalling.The paper gives a binary-output example satisfying these additional conditions even though A1 can signal to A2 and B1 together.Source: §3.2 · pp. 13–14
  • Theorem 3.3 shows that under Definition 3.2, every hash function has a partition w for which the hashed output remains at distance at least c(ε) from uniform.Thus, adding many within-system non-signalling equations does not remove the privacy-amplification obstruction.Source: §3.2 · p. 14
  • Lemma 3.4 implies that Definition 3.2 entails the almost backward non-signalling conditions, yielding the same impossibility result for such systems.Corollary 3.5 preserves the bound d(f(X)|Z(w)) ≥ c(ε) for every hash function f.Source: §3.2 · pp. 14–15
  • The same implication holds for systems completely non-signalling on Alice’s side and completely non-signalling on Bob’s side, so Corollary 3.8 gives the identical privacy-amplification impossibility.Definition 3.6 constrains each party’s marginal system, and Lemma 3.7 shows these conditions follow from Definition 3.2.Source: §3.2 · pp. 15–16

4 Privacy Amplification Against Non-signalling Adversaries

The paper extends an adversarial privacy-amplification attack to stricter non-signalling assumptions. It shows that the attack remains valid because probability shifts preserve the relevant symmetries and non-signalling conditions.

4.1 The impossibility of privacy amplification under the basic non-signalling assumptions

  • Alice, Bob, and Eve share a non-signalling extension, while Alice hashes her output X into a key K=f(X) intended to be nearly uniform against Eve.The security criterion is d(K|Z(W)) ≤ ǫ.Source: §4.1 · p. 16
  • The adversary reduces the analysis to deterministic one-bit hash functions and constructs a two-outcome partition whose z=0 branch maximally biases f(X) toward 0.The strategy is chosen after public communication, so it may depend on the hash-function seed.Source: §4.1 · pp. 16–17
  • Eve shifts probability within each row while preserving valid probabilities, normalization, and Alice–Bob non-signalling, yielding the conditional system P^z=0.Because row sums remain unchanged, Bob cannot signal to Alice; additional conditions follow from symmetries of the marginal box.Source: §4.1 · pp. 17–18

4.2 Proof of the theorem - a more general impossibility result

  • The proof extends the same strategy under stricter assumptions by establishing input-flip and row-equivalence lemmas for both Alice’s and Bob’s sides.The lemmas show that the probability-shift factor c remains constant across corresponding cells, preserving the required conditional equalities.Source: §4.2 · pp. 18–20
  • The conditional system preserves the added non-signalling assumptions even after conditioning on Eve’s result, while retaining the high distance from uniform established by the original attack [11].Lemmas 4.3 and 4.6 establish the added assumptions; the row-wise strategy leaves Bob-side full non-signalling intact.Source: §4.2 · pp. 18, 22

5 Concluding Remarks and Open Questions

The conclusion establishes impossibility of privacy amplification under substantially stronger non-signalling assumptions than [11]. It leaves open whether the remaining distinction from backward non-signalling determines the boundary between impossibility and possibility.

5 Concluding Remarks and Open Questions

  • Privacy amplification remains impossible after adding many non-signalling conditions beyond those assumed in [11].The result also implies impossibility for almost backward non-signalling systems.Source: §5 · p. 22
  • Whether privacy amplification is possible for backward non-signalling systems depends on whether the conditions distinguishing them from almost backward non-signalling systems are essential to Eve’s attack.If they are not essential, impossibility extends to backward non-signalling systems; if they are, those conditions may mark a possibility boundary.Source: §5 · p. 22
  • A further open question is whether interactive protocols using both outputs, such as K=g(X,Y), can amplify secrecy beyond hashing Alice’s output alone.The paper explicitly leaves this more interactive protocol model for future investigation.Source: §5 · p. 22
Loading 1205.3736v2…