Write, autoreview, editor, reviewer
3,129
edits
Pseudo-Secret Random Qubit Generator (PSQRG): Difference between revisions
Jump to navigation
Jump to search
Pseudo-Secret Random Qubit Generator (PSQRG) (edit)
Revision as of 06:33, 11 July 2019
, 11 July 2019→Pseudocode
| Line 28: | Line 28: | ||
*''Correctness'' If both the Client and the Server follow the protocol, the protocol aborts when {missing equation}, while otherwise the Server ends up with the output (single) qubit being in the state ), where <math>\theta</math> is given by [[equation|equation]] (see Pseudo Code). | *''Correctness'' If both the Client and the Server follow the protocol, the protocol aborts when {missing equation}, while otherwise the Server ends up with the output (single) qubit being in the state ), where <math>\theta</math> is given by [[equation|equation]] (see Pseudo Code). | ||
* The single qubit state generated by the protocol remains private against a QHBC Server. | * The single qubit state generated by the protocol remains private against a QHBC Server. | ||
==Notations== | |||
**<math>f_k</math>, function for target register | |||
**<math>t_k</math>, trapdoor for function <math>f_k</math> | |||
**<math>U_{f_k}</math>, Unitary operated on the target register taking first register as control, used to compute output of the function in the target register | |||
**y, measurement outcome of the target register | |||
**<math>x,x'</math>, pre-image pair for a given measurement outcome y | |||
**<math>x_i</math> value of qubit i for pre-image x | |||
**<math>x_i'</math> value of qubit i for pre-image x’ | |||
**<math>\alpha_i</math>, Client’s measurement angles for qubit i in the control register | |||
**<math>b_i</math>, Server’s measurement outcome for qubit i in the control register | |||
**<math>\theta</math>, classical description of the hidden input state | |||
==Pseudocode== | ==Pseudocode== | ||
==='''Stage1''' Preimages superposition=== | ==='''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 can rewrite the superposition in the control register for herself as, | * 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 | |||
where | * 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=== | ==='''Stage2''' Squeezing=== | ||