  Relativistic cryptography is a proposal for achieving unconditional security
that exploits the fact that no information carrier can travel faster than the
speed of light. It is based on space-time constraints but doesn't require
quantum hardware. Nevertheless, it was unclear whether this proposal is
realistic or not. Recently, Alikhani et al. [ABC+21] performed an
implementation of a relativistic zero-knowledge for NP. Their implemented
scheme shows the feasibility of relativistic cryptography but it is only secure
against classical adversaries. In this work, we present a new relativistic
protocol for NP which is secure against quantum adversaries and which is
efficient enough so that it can be implemented on everyday laptops and internet
connections. We use Stern's zero-knowledge scheme for the Syndrome Decoding
problem, which was used before in post-quantum cryptography. The main technical
contribution is a generalization of the consecutive measurement framework of
[CL17] to prove the security of our scheme against quantum adversaries, and we
perform an implementation that demonstrates the feasibility and efficiency of
our proposed scheme.
