Editing Pseudo-Secret Random Qubit Generator (PSQRG) (section)

==Protocol Description==

==='''Stage1''' Preimages superposition===
'''Requirements:''' </br>
Public: A family <math>\mathcal{F}=\{f_k : \{0,1\}^n \rightarrow \{0,1\}^m \}</math> of trapdoor one-way functions that are quantum-safe, two-regular and collision resistant (or second preimage resistant) (See article for Function Construction)</br>
'''Input:''' Client uniformly samples a set of random three-bits strings:
<math>\alpha=(\alpha_1,\cdots,\alpha_{n-1})</math> where <math>\alpha_i\leftarrow\{0,1\}^3</math>, and runs the algorithm <math>(k,t_k) \leftarrow \text{Gen}_{\mathcal{F}}(1^n)</math>. The <math>\alpha</math> and <math>k</math> are public inputs (known to both parties), while <math>t_k</math> is the ''private'' input of the Client.
 
* Client: instructs Server to prepare one register at <math>\otimes^n H |0\rangle</math> and second register initiated at <math>|0\rangle^{m}</math>
* Client: returns <math>k</math> to Server and the Server applies <math>U_{f_k}</math> using the first register as control and the second as target
* Server: measures the second register in the computational basis, obtains the outcome <math>y</math> and returns this result <math>y</math> to the Client. Here, an honest Server would have a state <math>{(|x\rangle+|x'\rangle) \otimes |y\rangle}</math> with <math>f_k(x)=f_k(x')=y</math> and <math>y\in \Im f_k</math>.
* Client can rewrite the superposition in the control register for herself as,
<math>(|x\rangle+|x'\rangle)=(|x_1\cdots x_n\rangle+|x'_1\cdots x'_n\rangle)</math>
<math>=\big(\otimes_{i\in \bar{G}}|x_{i}\rangle\big)\otimes\big(\otimes_{j\in G}|x_{j}\rangle+\otimes_{j\in G}|x_{j}\oplus 1\rangle\big)</math>
<math>\quad\quad\quad\quad\quad\quad=\big(\otimes_{i\in \bar{G}}|x_{i}\rangle\big)\otimes\Big(\prod_{j\in G}X^{x_{j}}\Big)\big(|0\cdots 0\rangle_{G}+|1\cdots 1\rangle_{G}\big)</math>,</br>
where <math>\bar{G}</math> is the set of bits positions where <math>x,x'</math> are identical, <math>G</math> is the set of bits positions where the pre-images differ, while suitably changing the order of writing the qubits.

==='''Stage2''' Squeezing===
*'''Output''': If the protocol is run honestly, when there is no abort, the state that Server has is <math>+_{\theta}</math>, where the Client (only) knows the classical description.
#Client: instructs the Server to measure all the qubits (except the last one) of the first register in the <math>\left\{|0\rangle\pm e^{\alpha_i\pi/4}|1\rangle\right\}</math> basis. Server obtains the outcomes <math>b=(b_1,\cdots,b_{n-1})</math> and returns the result <math>b</math> to the Client.
#Client: using the trapdoor <math>t_k</math> computes <math>x,x'</math>. Then check if the <math>n^{\text{th}}</math> bit of <math>x</math> and <math>x'</math> (corresponding to the y received in stage 1) are the same or different. If they are the same, returns abort, otherwise, obtains the classical description of the Server’s state.