Circuit 1: Key
The key generation circuit
Input : None
Output : A key state
ρ
∈
D
(
Q
(
k
+
m
+
n
+
μ
+
τ
)
⊗
H
p
a
⊗
H
e
c
{\displaystyle \rho \in {\mathcal {D}}({\mathcal {Q}}(k+m+n+\mu +\tau )\otimes {\mathfrak {H}}_{pa}\otimes {\mathfrak {H}}_{ec}}
Sample
θ
←
Θ
{\displaystyle \theta \gets \Theta }
Sample
r
|
I
~
←
{
0
,
1
}
k
{\displaystyle r|_{\tilde {\mathcal {I}}}\gets \{0,1\}^{k}}
where
I
~
=
{
i
∈
[
m
]
|
θ
i
=
1
}
{\displaystyle {\tilde {\mathcal {I}}}=\{i\in [m]|\theta _{i}=1\}}
Sample
u
←
{
0
,
1
}
n
{\displaystyle u\gets \{0,1\}^{n}}
Sample
d
←
{
0
,
1
}
μ
{\displaystyle d\gets \{0,1\}^{\mu }}
Sample
e
←
{
0
,
1
}
τ
{\displaystyle e\gets \{0,1\}^{\tau }}
Sample
H
p
a
←
H
p
a
{\displaystyle H_{pa}\gets {\mathfrak {H}}_{pa}}
Sample
H
e
c
←
H
e
c
{\displaystyle H_{ec}\gets {\mathfrak {H}}_{ec}}
Output
ρ
=
|
r
|
I
~
,
θ
,
u
,
d
,
e
,
H
p
a
,
H
e
c
⟩
⟨
r
|
I
~
,
θ
,
u
,
d
,
e
,
H
p
a
,
H
e
c
|
{\displaystyle \rho =|r|_{\tilde {\mathcal {I}}},\theta ,u,d,e,H_{pa},H_{ec}\rangle \langle r|_{\tilde {\mathcal {I}}},\theta ,u,d,e,H_{pa},H_{ec}|}
Circuit 2: Enc
The encryption circuit
Input : A plaintext state
|
m
s
g
⟩
⟨
m
s
g
|
{\displaystyle |\mathrm {msg} \rangle \langle \mathrm {msg} |}
and a key state
|
r
|
I
~
,
θ
,
u
,
d
,
e
,
H
p
a
,
H
e
c
⟩
⟨
r
|
I
~
,
θ
,
u
,
d
,
e
,
H
p
a
,
H
e
c
|
∈
D
(
Q
(
k
+
m
+
n
+
μ
+
τ
)
⊗
H
p
a
⊗
H
e
c
{\displaystyle |r|_{\tilde {\mathcal {I}}},\theta ,u,d,e,H_{pa},H_{ec}\rangle \langle r|_{\tilde {\mathcal {I}}},\theta ,u,d,e,H_{pa},H_{ec}|\in {\mathcal {D}}({\mathcal {Q}}(k+m+n+\mu +\tau )\otimes {\mathfrak {H}}_{pa}\otimes {\mathfrak {H}}_{ec}}
Output: A ciphertext state
ρ
∈
D
(
Q
(
m
+
n
+
τ
+
μ
)
)
{\displaystyle \rho \in {\mathcal {D}}({\mathcal {Q}}(m+n+\tau +\mu ))}
Sample
r
|
I
←
{
0
,
1
}
s
{\displaystyle r|_{\mathcal {I}}\gets \{0,1\}^{s}}
where
I
=
{
i
∈
[
m
]
|
θ
i
=
0
}
{\displaystyle {\mathcal {I}}=\{i\in [m]|\theta _{i}=0\}}
Compute
x
=
H
p
a
(
r
|
I
)
{\displaystyle x=H_{pa}(r|_{\mathcal {I}})}
where
I
=
{
i
∈
[
m
]
|
θ
i
=
0
}
{\displaystyle {\mathcal {I}}=\{i\in [m]|\theta _{i}=0\}}
Compute
p
=
H
e
c
(
r
|
I
)
⊕
d
{\displaystyle p=H_{ec}(r|_{\mathcal {I}})\oplus d}
Compute
q
=
s
y
n
d
(
r
|
I
)
⊕
e
{\displaystyle q=\mathrm {synd} (r|_{\mathcal {I}})\oplus e}
Output
ρ
=
|
r
θ
⟩
⟨
r
θ
|
⊗
|
m
s
g
⊕
x
⊕
u
,
p
,
q
⟩
⟨
m
s
g
⊕
x
⊕
u
,
p
,
q
|
{\displaystyle \rho =|r^{\theta }\rangle \langle r^{\theta }|\otimes |\mathrm {msg} \oplus x\oplus u,p,q\rangle \langle \mathrm {msg} \oplus x\oplus u,p,q|}
Circuit 3: Dec
The decryption circuit
Input : A key state
|
r
|
I
~
,
θ
,
u
,
d
,
e
,
H
p
a
,
H
e
c
⟩
⟨
r
|
I
~
,
θ
,
u
,
d
,
e
,
H
p
a
,
H
e
c
|
∈
D
(
Q
(
k
+
m
+
n
+
μ
+
τ
)
⊗
H
p
a
⊗
H
e
c
{\displaystyle |r|_{\tilde {\mathcal {I}}},\theta ,u,d,e,H_{pa},H_{ec}\rangle \langle r|_{\tilde {\mathcal {I}}},\theta ,u,d,e,H_{pa},H_{ec}|\in {\mathcal {D}}({\mathcal {Q}}(k+m+n+\mu +\tau )\otimes {\mathfrak {H}}_{pa}\otimes {\mathfrak {H}}_{ec}}
and a ciphertext
ρ
⊗
|
c
,
p
,
q
⟩
⟨
c
,
p
,
q
|
∈
D
(
Q
(
m
+
n
+
μ
+
τ
)
)
{\displaystyle \rho \otimes |c,p,q\rangle \langle c,p,q|\in {\mathcal {D}}({\mathcal {Q}}(m+n+\mu +\tau ))}
Output: A plaintext state
σ
∈
D
(
Q
(
n
)
)
{\displaystyle \sigma \in {\mathcal {D}}({\mathcal {Q}}(n))}
and an error flag
γ
∈
D
(
Q
)
{\displaystyle \gamma \in {\mathcal {D}}({\mathcal {Q}})}
Compute
ρ
′
=
H
θ
ρ
H
θ
{\displaystyle \rho ^{\prime }=\mathrm {H} ^{\theta }\rho \mathrm {H} ^{\theta }}
Measure
ρ
′
{\displaystyle \rho ^{\prime }}
in the computational basis. Call the result
r
{\displaystyle r}
Compute
r
′
=
c
o
r
r
(
r
|
I
,
q
⊕
e
)
{\displaystyle r^{\prime }=\mathrm {corr} (r|_{\mathcal {I}},q\oplus e)}
where
I
=
{
i
∈
[
m
]
|
θ
i
=
0
}
{\displaystyle {\mathcal {I}}=\{i\in [m]|\theta _{i}=0\}}
Compute
p
′
=
H
e
c
(
r
′
)
⊕
d
{\displaystyle p^{\prime }=H_{ec}(r^{\prime })\oplus d}
If
p
≠
p
′
{\displaystyle p\neq p^{\prime }}
, then set
γ
=
|
0
⟩
⟨
0
|
{\displaystyle \gamma =|0\rangle \langle 0|}
. Else, set
γ
=
|
1
⟩
⟨
1
|
{\displaystyle \gamma =|1\rangle \langle 1|}
Compute
x
′
=
H
p
a
(
r
′
)
{\displaystyle x^{\prime }=H_{pa}(r^{\prime })}
Output
ρ
⊗
γ
=
|
c
⊕
x
′
⊕
u
⟩
⟨
c
⊕
x
′
⊕
u
|
⊗
γ
{\displaystyle \rho \otimes \gamma =|c\oplus x^{\prime }\oplus u\rangle \langle c\oplus x^{\prime }\oplus u|\otimes \gamma }
Circuit 4: Del
The deletion circuit
Input : A ciphertext
ρ
⊗
|
c
,
p
,
q
⟩
⟨
c
,
p
,
q
|
∈
D
(
Q
(
m
+
n
+
μ
+
τ
)
)
{\displaystyle \rho \otimes |c,p,q\rangle \langle c,p,q|\in {\mathcal {D}}({\mathcal {Q}}(m+n+\mu +\tau ))}
Output: A certificate string
σ
∈
D
(
Q
(
m
)
)
{\displaystyle \sigma \in {\mathcal {D}}({\mathcal {Q}}(m))}
Measure
ρ
{\displaystyle \rho }
in the Hadamard basis. Call the output y.
Output
σ
=
|
y
⟩
⟨
y
|
{\displaystyle \sigma =|y\rangle \langle y|}
Circuit 5: Ver
The verification circuit
Input : A key state
|
r
|
I
~
,
θ
,
u
,
d
,
e
,
H
p
a
,
H
e
c
⟩
⟨
r
|
I
~
,
θ
,
u
,
d
,
e
,
H
p
a
,
H
e
c
|
∈
D
(
Q
(
k
+
m
+
n
+
μ
+
τ
)
⊗
H
p
a
⊗
H
e
c
{\displaystyle |r|_{\tilde {\mathcal {I}}},\theta ,u,d,e,H_{pa},H_{ec}\rangle \langle r|_{\tilde {\mathcal {I}}},\theta ,u,d,e,H_{pa},H_{ec}|\in {\mathcal {D}}({\mathcal {Q}}(k+m+n+\mu +\tau )\otimes {\mathfrak {H}}_{pa}\otimes {\mathfrak {H}}_{ec}}
and a certificate string
|
y
⟩
⟨
y
|
∈
D
(
Q
(
m
)
)
{\displaystyle |y\rangle \langle y|\in {\mathcal {D}}({\mathcal {Q}}(m))}
Output: A bit
Compute
y
^
′
=
y
^
|
I
~
{\displaystyle {\hat {y}}^{\prime }={\hat {y}}|_{\mathcal {\tilde {I}}}}
where
I
~
=
{
i
∈
[
m
]
|
θ
i
=
1
}
{\displaystyle {\mathcal {\tilde {I}}}=\{i\in [m]|\theta _{i}=1\}}
Compute
q
=
r
|
I
~
{\displaystyle q=r|_{\tilde {\mathcal {I}}}}
If
ω
(
q
⊕
y
^
′
)
<
k
δ
{\displaystyle \omega (q\oplus {\hat {y}}^{\prime })<k\delta }
, output
1
{\displaystyle 1}
. Else, output
0
{\displaystyle 0}
.