Pseudo-Secret Random Qubit Generator (PSQRG): Difference between revisions

Pseudo-Secret Random Qubit Generator (PSQRG) (edit)

Revision as of 07:33, 11 July 2019

1,548 bytes added , 11 July 2019

→‎Pseudocode

Shraddha

Write, autoreview, editor, reviewer

3,125

edits

@@ 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).
 * 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==
 ==='''Stage1''' Preimages superposition===
-*'''Input:''' Client uniformly samples a set of random three-bits strings α = (α1,··· ,αn−1) where αi ← {0,1}3, and runs the algorithm (k,tk) ← GenF(1n). The α and k are public inputs (known to both parties), while tk is the “private” input of the Client, A public function family F = {fk : {0,1}n → {0,1}m} of trapdoor one-way functions that are quantum safe, two-regular and collision resistant (or second preimage resistant) (See Supplementary Information for Function Construction)
+'''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>
-#Client: instructs Server to prepare one register at ⊗nH |0i and second register initiated at |0im
+'''Input:''' Client uniformly samples a set of random three-bits strings:
-#Client: returns k to Server and the Server applies Ufk using the first register as control and the second as target
+<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.
-#Server: measures the second register in the computational basis, obtains the outcome y and returns this result y to the Client. Here, an honest Server would have a state (|xi + |x0i) ⊗ |yi with fk(x) = fk(x0) = y and y ∈ =fk.
-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>
- {missing equation}
+* 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 G¯ is the set of bits positions where x,x0 are identical, G is the set of bits positions where the preimages differ, while suitably changing the order of writing the qubits.
+* 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===