Collapseability Implies Collision Resistance Sample Clauses

Collapseability Implies Collision Resistance. ‌ 2.1. Suppose one can obtain distinct x, xj with H(x) = H(xj). We show how such a collision can be used to break the collapseability of H. As the state in the collapsing game, we choose 1 j |φ) = √2 (|x) + |x )) .

Collapseability Implies Collision Resistance. ‌ We show that collapseability is a stronger notion than collision resistance. Our reasoning is similar to the one of Xxxxx [17, Lemma 22] (Lemma 25 in the full version), but simplified to only require the basic knowledge of qubits and measurements given in Sect. 2.1. Suppose one can obtain distinct x, x′ with H(x)= H(x′). We show how such a collision can be used to break the collapseability of H. As the state in the collapsing game, we choose |φ⟩ = √2 (|x⟩ + |x ⟩) . Now φ may or may not get measured in the computational basis. If it gets measured, it either collapses to x or to x′ , both with probability 1/2. If it does not get measured, it stays the same. In order for adversary A to differentiate between the two cases, we measure |φ⟩ in a modified basis. Almost all basis elements stay the same, but we replace |x⟩ and |x′⟩ with |+ ' ⟩ = (|x⟩ + |x ⟩) and |− ' ⟩ = (|x⟩− |x ⟩) . x,x √2 x,x √2 This is still an orthonormal basis. If φ is not measured, it is equal to +x,x' , hence the result of the measurement is +x,x' with probability 1. However, if φ is measured, it is either x or x′ . We rewrite these in the new basis as |x⟩ |x⟩ + |x′⟩ 1 1 |x⟩− |x′⟩)= |+ ' ⟩ + √ |− )+ 2 ( 2 x,x |x′⟩ 1 |x⟩ + |x′⟩) − 1 (|x⟩− |x′⟩)= |+ ' ⟩− |− ' ⟩ . = 2 ( 2 This means that both x and x′ get measured as either +x,x' or x,x' , both with probability 1/2. The adversary thus operates as follows. If it finds +x,x' , it concludes that φ was not measured, and if it finds x,x' , it concludes that φ was measured. Since it gets the case without measurement always right, and it basically guesses in the case with measurement, its advantage is 1/2. Hence H is not collapsing.