The microblog: 2018.02.04 02:26:44

2018.02.04 02:26:44 (959961386863521792) from Daniel J. Bernstein, replying to "Niklas Johansson (@Niklas_Skans)" (959946467346669568):

Can you tell us the period of the function mapping an integer x to 2^x mod 2^12345-3? Shor (generalizing Simon) can, given enough fast reliable Hadamard and Toffoli gates.


2018.02.03 19:25:20 (959855338378944522) from "Daniel Loebenberger (@dloebenberger)", replying to "Niklas Johansson (@Niklas_Skans)" (959742896164483072):

But then it cannot be considered a classical break, can it?

2018.02.03 21:32:14 (959887273738162176) from "Paulo Barreto (@pbarreto)", replying to "Daniel Loebenberger (@dloebenberger)" (959855338378944522):

The original attack by Kaplan et al. is quantum and depends on the (so often called "useless") Simon algorithm. The point here is in which conditions it can be de-quantized, since Simon itself can be efficiently simulated classically.

2018.02.04 01:08:16 (959941641758019584) from Daniel J. Bernstein, replying to "Paulo Barreto (@pbarreto)" (959887273738162176):

The claimed simulation (of Simon's method on a non-quantum computer) cheats by asking the user to provide the period as input. For an earlier and more general cheat see "trapdoor simulation" in Useful for verification but not for actual computations.

2018.02.04 01:27:27 (959946467346669568) from "Niklas Johansson (@Niklas_Skans)":

Again then, this problem is about generating the function, not finding the period. Let Alice generate the function then and Bob find the period. Honestly, how would anyone go about building a function with an internal parameter without knowing the parameter?