
For [1]}. The best algorithm for Hamiltonian cycle on a graph \(G\)  with \(n\)  vertices runs in time \(O(1.657^n)\)[2]} so we need \(n \ge 138\)  in order to achieve 100 bits of security. The best running time is actually performed by a classical algorithm, we don't know a better quantum algorithm for this problem. This protocol requires to commit each bit of the upper triangle of the adjacency matrix of \(G\)  using the relativistic \(\mathbb {F}_Q\)  bit commitment scheme with \(Q > 10000n!\)  (to have soundness close to \(1/2\) ) so each round of communication requires at least \(2*\frac{n(n-1)}{2}\log _2(10000*Q)\)  bits of communication. \(\frac{n(n-1)}{2}\)  is the number of bits in the upper triangle of the adjacency matrix. The factor 2 comes from the fact that the verifier first sends \(\frac{n(n-1)}{2}\)  elements of \(\mathbf {\mathsf {\mathbb {F}_Q}}\)  and then the prover sends back \(\frac{n(n-1)}{2}\)  elements of \(\mathbf {\mathsf {\mathbb {F}_Q}}\) . For \(n = 138\) , this gives a communication of \(1.51 \cdot 10^7 \)  bits which is approximately \(1.89MBytes\) . In order to achieve soundness of \(2^{-100}\) , we use 100 rounds since each round has soundness \(\frac{1}{2}\) .

The protocol of [3]} and its implementation in [4]} uses a graph \(G\)  with 588 vertices and 1097 edges. The communication is essentially sending a edge which is of size less than 2 bytes. In order to achieve a soundness of \(2^{-100}\) , the number of repetition they use is \(10^6\) . These parameters achieve classical security. If we wanted to achieve quantum security, [4]} claims that this would require \((21*|E|)^4*100\)  which is more than \(10^{19}\) , as well as a third prover/verifier pair.

The best quantum algorithm for random instances of the syndrome decoding problem requires time at least \(2^{0.05869n}\)  [6]} for \(k \approx 0.4514n\)  and \(w \approx 0.1268n\) . Our protocol uses \(n = 1704, k = 769, w = 216\)  in order to have 100 bits of security. At each round, we have to commit to 3 strings of \(\mathbf {\mathsf {\mathbb {F}_Q}}\)  which means the communication at each round is \(6\log _2(Q)\) . We can prove security of our scheme by taking \(Q = 10^{12}n!2^{4n}\) , so the communication is \(6\log _2(Q) = 136177\)  bits which is equal to \(17.03KB\) . The number of rounds we take is 340, which allows our protocol to be loss tolerant.

