How to authenticate the quantum monster?

[decltypeme]

The problem:

A classical machine wants to authenticate a quantum server.

The Context:

Classically, authentication protocols are used every second to authenticate entities to each other, sometimes mutually, and sometimes from one-side. In the quantum world, it is desirable that you ensure you are talking to the server you are thinking you are talking to.

How can you do it?

The quantum server owns a pair of public and private keys. She publishes the public key, and keeps the private key. Each execution of the protocol, given the public key, will convince the verifier that they are talking to an entity that indeed has knowledge of this private key without releasing it.

What is that quantumly?

The public key will be an instance of the Local Hamiltonian Problem (Hamiltonian H and Energy E).
The private key will be a state with energy < E.
The protocol execution will be classical interaction where the prover is trying to convince the verifier that the quantum machine indeed possess the private key.

The Protocol

The protocol to do this is the Proof of Knowledge protocol from https://arxiv.org/pdf/1911.07546.pdf
The Ingredients to build it (see section 3.2.):
(1) implement a certain FHE scheme; see 2.4.1. in the paper.
(2) Commitment Scheme described in the paper section 2.4.2.
(3) Implement or potentially use an existing library for classical Non-interactive zero-knowledge.
Then blend these to write the protocol in section 3.2.

Preferred Knowledge Topics

Any knowledge of any of these is a huge plus:

• The Local Hamiltonian Problem
• Algebra and Number Theory
• Knowledge of LWE is a big plus
• Cryptography and Zero-Knowledge.

If you are interested, please feel free to email me ([email protected]) or reply to this thread.
Happy Hacking!