Limits of privacy amplification against nonsignaling memory attacks

The task of privacy amplification, in which Alice holds some partially secret information with respect to an adversary Eve and wishes to distill it until it is completely secret, is known to be solvable almost optimally in both the classical and quantum worlds. Unfortunately, when considering an adversary who is limited only by nonsignaling constraints such a statement cannot be made in general. We here consider systems which violate the chained Bell inequality and prove that under the natural assumptions of a time-ordered nonsignaling system, which allow past subsystems to signal future subsystems (using the device's memory for example), superpolynomial privacy amplification by any hashing is impossible. This is of great relevance when considering practical device-independent key-distribution protocols which assume a superquantum adversary.

Figure 1

Time-ordered nonsignaling condition for $i=3$. Signaling is impossible in the direction of the straight arrow.

Figure 2

Binary tree with pivotal nodes. The pivotal nodes are marked with circles.

Figure 3

The unbiased system $P_{X_i{Y}_i|U_i{V}_i}$ for which $I_N^{☆}=2N{\sin }^2\frac{\pi }{4N}$. The empty squares in the figure are not relevant for the correlations and therefore are not considered in cryptographic protocols.

Figure 4

The biased system $P_{X_i{Y}_i|U_i{V}_i}^{z_i=0}$. Here are the same squares of Fig. 3 after the probability shift.

Figure 5

Two possible cases: $i\left(x\right)\in I_1$ or $i\left(x\right)\in I_2$.