11institutetext: Dianei Technology, Shanghai, China 22institutetext: Shanghai
Jiao Tong University, Shanghai, China
22email<EMAIL_ADDRESS>33institutetext: Wuhan University, Hubei,
China 44institutetext: Technical University of Munich, Munich, Germany
55institutetext: EPFL, Lausanne, Switzerland

# What Makes for Automatic Reconstruction of Pulmonary Segments

Kaiming Kuang Equal contributions: Kaiming Kuang and Li Zhang.11 Li Zhang 1⋆1⋆
Jingyu Li 33 Hongwei Li 44 Jiajun Chen 11
Bo Du 33 Jiancheng Yang Corresponding author: Jiancheng Yang
(jekyll4168@sjtu.edu.cn).112255

###### Abstract

3D reconstruction of pulmonary segments plays an important role in surgical
treatment planning of lung cancer, which facilitates preservation of pulmonary
function and helps ensure low recurrence rates. However, automatic
reconstruction of pulmonary segments remains unexplored in the era of deep
learning. In this paper, we investigate what makes for automatic
reconstruction of pulmonary segments. First and foremost, we formulate,
clinically and geometrically, the anatomical definitions of pulmonary
segments, and propose evaluation metrics adhering to these definitions.
Second, we propose ImPulSe (Implicit Pulmonary Segment), a deep implicit
surface model designed for pulmonary segment reconstruction. The automatic
reconstruction of pulmonary segments by ImPulSe is accurate in metrics and
visually appealing. Compared with canonical segmentation methods, ImPulSe
outputs continuous predictions of arbitrary resolutions with higher training
efficiency and fewer parameters. Lastly, we experiment with different network
inputs to analyze what matters in the task of pulmonary segment
reconstruction. Our code is available at https://github.com/M3DV/ImPulSe.

###### Keywords:

pulmonary segments surface reconstruction implicit fields.

##  1 Introductions

Pulmonary segments are anatomical subunits of pulmonary lobes. There are 18
segments in total, with eight in the left lung and ten in the right [1, 15,
30]. Unlike pulmonary lobes, pulmonary segments are not defined by visible
boundaries but bronchi, arteries and veins. Concretely, pulmonary segments
should include their segmental bronchi and arteries while establishing their
boundaries along intersegmental veins [20, 5]. However, boundaries between
adjacent segments are ambiguous since segmenting planes are valid as long as
they separate segmental bronchi and arteries while lying roughly in the area
of intersegmental veins.

Automatic reconstruction of pulmonary segments helps determine the appropriate
resection method in surgical treatment of lung cancer. Lobectomy (excising the
affected lobe entirely) and segmentectomy (excising only the affected segment)
are two major resection methods for early stage lung cancer. As the standard
care of early stage lung cancer, lobectomy is challenged by segmentectomy as
it preserves more pulmonary function, reduces operation time and blood loss
while leading to similar recurrence rates and survival [27, 5, 32, 9, 10].
However, segmentectomy should only be considered when surgical margins can be
guaranteed to ensure low recurrence rates [27, 19]. Therefore, it is crucially
important to reconstruct pulmonary segments before performing pulmonary
surgeries.

Recent years have witnessed the great success of deep learning in medical
image segmentation [26, 17, 34, 13], as well as in segmentation of pulmonary
structures such as lobes, airways and vessels [7, 6, 18, 24]. Nonetheless,
automatic reconstruction of pulmonary segments remains poorly understood.
First, canonical segmentation methods such as U-Net [26] are not suitable for
this task. These methods create large memory footprint with medical images of
original resolutions, and output poor segmentation if inputs are downsampled.
Second, it is desired that the pulmonary segment reconstruction model can
generate outputs at arbitrary resolutions when given only coarse inputs.
Lately, deep implicit functions show great promises in representing continuous
3D shapes [21, 16, 3, 23, 4, 12]. The learned implicit function predicts
occupancy at continuous locations, thus is capable of reconstructing 3D shapes
at arbitrary resolutions. Moreover, implicit fields can be optimized using
irregular points randomly sampled from the entire continuous space, which
significantly reduces training costs. These characteristics suggest that
implicit functions can be of use in the reconstruction of pulmonary segments.

In this paper, we aim to answer this question: what makes for automatic
reconstruction of pulmonary segments? First and foremost, we give clear and
concrete definitions of the anatomy of pulmonary segments (Section 2.1) and
propose evaluation metrics that adhere to problem definitions (Section 2.2);
Next, we present an implicit-function-based model, named ImPulSe (Implicit
Pulmonary Segment), for the pulmonary segment reconstruction task (Section 2.3
and 2.4). Implicit fields render ImPulSe with high training and parameter
efficiency and the ability to output reconstruction at arbitrary resolutions.
Our proposed method uses only half the training time of U-Net [26] while
having better accuracy. ImPulSe achieves Dice score of 84.63% in overall
reconstruction, 86.18% and 87.00% in segmental bronchus and artery
segmentation. Last but not least, we investigate what inputs matter for
accurate reconstruction of pulmonary segments (Section 3.3). Our experiments
indicate that bronchi and vessels play important roles in the reconstruction
of pulmonary segments.

##  2 Methods

Figure 1: Visualization of pulmonary segment anatomy. A: An overview of
pulmonary segments, including bronchi, arteries and veins. B, C: Bronchus and
artery tree are separated into segmental groups, each of which occupies a
branch of the tree. D: A concrete example of intersegmental boundaries of RUL
S1 (middle), RUL S2 (left) and RUL S3 (right). Segmental bronchi, segmental
arteries and intersegmental veins are colored in gray, blue and red.
Intrasegmental veins are hidden for better visualization. Each segment
completely wraps its own segmental bronchi and arteries. Intersegmental
boundaries lie on the branch of intersegmental veins.

###  2.1 Anatomical Definitions of Pulmonary Segments

To start the investigation of automatic pulmonary segment reconstruction, it
is necessary to first set clear anatomical definitions of pulmonary segments.
Pulmonary segments are subunits of pulmonary lobes. There are 5 pulmonary
lobes: left upper lobe (LUL), left lower lobe (LLL), right upper lobe (RUL),
right middle lobe (RML), and right lower lobe (RLL). These lobes are further
divided into 18 pulmonary segments, with eight segments in the left lung and
ten in the right lung [1, 15, 30]. These segments are numbered from S1 to S10
in either left lung and right lung, with two exceptions in the left lung (LUL
S1+S2 and LLL S7+S8). Unlike other anatomical structures such as pulmonary
lobes, pulmonary segments are not defined by visible boundaries but pulmonary
bronchi, arteries and veins. Pulmonary bronchi and vessels (including arteries
and veins) expand themselves into tree structures in lungs. Branches of
bronchi and vessel trees are then divided into 18 segmental groups (i.e.,
segmental bronchi and arteries), by which pulmonary segments are defined. Fig.
1B and C show the bronchus tree and the artery tree, with segmental groups
marked in different colors. Each color represents a segmental bronchus/artery.
Concretely, pulmonary segments should satisfy the following three rules [20,
5]:

(1) Includes its segmental bronchi. The volume of a certain segment should
completely includes its corresponding segmental bronchus, as in Fig. 1B.

(2) Includes its segmental arteries. A certain segment should contain its
segmental artery as in the case of segmental bronchi. See Fig. 1C.

(3) Establishes its boundaries along intersegmental veins. Pulmonary veins can
be subdivided into intrasegmental or intersegmental veins. Intersegmental
veins serve as important landmarks indicating boundaries between adjacent
segments. Specifically, intersegmental planes should follow intersegmental
veins.

Fig. 1D gives a concrete example of pulmonary segment boundaries (RUL S1 in
the left, RUL S2 in the middle, and RUL S3 in the right). Segmental bronchi,
segmental arteries and intersegmental veins are marked in gray, blue and red,
respectively. Intrasegmental veins are hidden for better visualization. Each
segment completely wraps its own segmental bronchi and arteries. Boundaries
between segments lie on the branch of intersegmental veins, as per
definitions. Segmental bronchi and arteries do not cross segmental boundaries.

###  2.2 Evaluation Metrics

Since the automatic reconstruction of pulmonary segments have not been
systematically investigated, it is equally important to select appropriate
evaluation metrics for this task. Dice score is a commonly-used metric in
segmentation,

$Dice_{\mathbf{s}}=\frac{2\|\mathbf{Y}_{\mathbf{s}}\cap\hat{\mathbf{Y}}_{\mathbf{s}}\|}{\|\mathbf{Y}_{\mathbf{s}}\|+\|\hat{\mathbf{Y}}_{\mathbf{s}}\|},$
(1)

where $\mathbf{Y}_{\mathbf{s}}$ and $\hat{\mathbf{Y}}_{\mathbf{s}}$ are
ground-truth and prediction segmentation of points in the set $\mathbf{s}$,
and $\|\cdot\|$ denotes the number of elements. Definitions of pulmonary
segments suggest that their boundaries are ambiguous. Therefore, it is more
important to guarantee accurate reconstruction of segmental bronchi and
arteries than segment reconstruction itself. Given that, we evaluate our
proposed method and its counterparts not only using the overall Dice score on
18 pulmonary segments ($Dice_{\mathbf{o}}$) but also Dice on segmental bronchi
($Dice_{\mathbf{b}}$) and arteries ($Dice_{\mathbf{a}}$). Note that
$Dice_{\mathbf{b}}$ and $Dice_{\mathbf{a}}$ are not binary Dice scores of
bronchi and arteries. Instead, they are 19-class pulmonary segment Dice scores
evaluated only on voxels of bronchi and arteries. These two metrics measure
how accurate bronchi and arteries are divided into their corresponding
pulmonary segments (as in Fig. 1 B and C). We argue that Dice scores of
segmental bronchi and arteries are more important metrics than the overall
Dice score. We leave veins out of this question because the segment
classification of veins, especially intersegmental veins, is ambiguous. We
find that Dice scores on veins are consistently lower than bronchi and
arteries across all models (see supplementary materials).

###  2.3 The ImPulSe Network

Figure 2: Visualization of shape representations with voxel and implicit
functions. Rather than classifying each voxel, implicit functions representing
shapes by encoding 3D iso-surfaces with function $f(\mathbf{p})=z$. When
queried with a continuous location $\mathbf{p}$, it outputs occupancy $z$ at
the location, Thus, implicit functions can output continuous reconstruction
with high resolutions and fine details. Please note that this is a conceptual
visualization, not a rigorous comparison.

To apply deep learning in automatic pulmonary segment reconstruction, one
problem shows up: CT images come in different sizes. While high-resolution 3D
inputs are not feasible due to large memory footprint, canonical segmentation
methods such as U-Net [26] generate coarse segmentations of fixed sizes given
low-resolution inputs (i.e., low-resolution in, low-resolution out), which
makes them unsuitable for this task. Unlike U-Net, implicit functions generate
continuous outputs of arbitrary resolutions even when only low-resolution
inputs are given. Fig. 2 visualizes implicit functions and voxel-based
representations. Rather than predicting segmentation in a fixed-size voxel
grid, the learned implicit function encodes 3D iso-surfaces with function
$f(\mathbf{p})=z$ and predicts occupancy $z$ at a continuous location
$\mathbf{p}$, thus is capable of reconstructing 3D shapes at arbitrary
resolutions. To take advantage of this in reconstruction of pulmonary
segments, we propose ImPulSe (Implicit Pulmonary Segment), an implicit-
function-based model capable of generating reconstruction of arbitrary sizes.
The overall architecture of ImPulSe is shown in Fig. 3. It consists of an
encoder and a decoder. The encoder $f$ is a small CNN (3D ResNet18 [11, 29] in
our experiments), which takes 3D voxel grids $\mathbf{X}\in\mathbb{R}^{c\times
d\times h\times w}$ as inputs and extracts a feature pyramid
${\mathbf{F}}_{1},{\mathbf{F}}_{2},...,{\mathbf{F}}_{n}$. During the decoding
stage, 3D continuous coordinates $\mathbf{p}\in{[-1,1]}^{3}$ are sampled from
the entire space. This is different than traditional segmentation methods,
where the model runs on discrete voxel grids. These locations are queried
using tri-linear interpolation to extract features at each coordinate
${\mathbf{F}}_{1}(\mathbf{p}),{\mathbf{F}}_{2}(\mathbf{p}),...,{\mathbf{F}}_{n}(\mathbf{p})$.
These features are concatenated with point coordinates $\mathbf{p}$ to form
point encodings $\mathbf{F}(\mathbf{p})$, which are then fed into the decoder
$g$, a two-layer MLP predicting segment occupancy at each location.

Figure 3: The architecture of ImPulSe. ImPulSe consists of an encoder and a
decoder. The encoder $f$ takes a voxel grid $\mathbf{X}$ as input and outputs
a feature pyramid ${\mathbf{F}}_{1},{\mathbf{F}}_{2},...,{\mathbf{F}}_{n}$.
Features at continuous coordinates $\mathbf{p}$, i.e.,
${\mathbf{F}}_{1}(\mathbf{p}),{\mathbf{F}}_{2}(\mathbf{p}),...,{\mathbf{F}}_{n}(\mathbf{p})$,
are sampled with tri-linear interpolation and then concatenated with
$\mathbf{p}$ to form point encodings $\mathbf{F}(\mathbf{p})$. The decoder $g$
takes $\mathbf{F}(\mathbf{p})$ and predicts occupancy at $\mathbf{p}$. Note
that ImPulSe samples far fewer points during training than inference.

Compared with fully-convolutional methods [28, 26, 2], the ImPulSe
architecture has two major advantages: it delivers continuous outputs with
arbitrarily high resolutions and fine-grained details, while significantly
reducing the number of parameters in its decoder. More importantly, thanks to
implicit fields, ImPulSe can be trained on continuous locations instead of
discrete locations on the voxel grid. These advantages render ImPulSe with
high training efficiency while achieving better accuracy than traditional
segmentation networks.

###  2.4 Training and Inference

During training and inference, ImPulSe alternates between random sampling and
uniform sampling (Fig. 3). During the training phase, we train ImPulSe on
randomly sampled points $\mathbf{p}\in{[-1,1]}^{3}$. Random and continuous
sampling implicitly imposes data augmentation and alleviates overfitting while
ensuring sufficient coverage of the entire space. Furthermore, it leads to a
higher training efficiency compared against canonical segmentation methods,
which trains on the entire voxel grid. With random sampling, we are able to
train ImPulSe with far fewer points in each batch (e.g., $16^{3}$ for ImPulSe
versus $64^{3}$ or $128^{3}$ for its counterparts in our experiments) while
achieving better performances. Ground-truth labels on these continuous
positions are queried using nearest-neighbor interpolation. The ImPulSe
network is trained using a weighted combination of cross-entropy loss and Dice
loss [17]. All models are trained on 4 NVIDIA RTX 3090 GPUs with PyTorch
1.10.1 [22]. During inference, we replace the random sampling with uniform
sampling on the voxel grid, thus output pulmonary segment reconstruction at
the original resolution of the CT image.

##  3 Experiments

###  3.1 Datasets

In this study, we compile a dataset containing 800 CT scans with annotations
of pulmonary segments, pulmonary bronchi, arteries and veins. To allow
elaborative analysis of reconstruction performances, pulmonary veins are
further annotated as intrasegmental and intersegmental veins. CT scans are
collected from multiple medical centers to improve the generalization
performance of our model. Z-direction spacings of these scans range from
$0.5mm$ to $1.5mm$. Annotations are manually made by a junior radiologist and
confirmed by a senior radiologist. All CT scans are divided into training,
validation and test subsets with a 7:1:2 ratio. Results are tuned using the
validation set and reported on the test set.

###  3.2 Reconstruction Performances

Table 1: Pulmonary segment reconstruction performances of ImPulSe and its counterparts. All methods are evaluated on Dice score (%) of pulmonary segments ($Dice_{\mathbf{o}}$), segmental bronchi ($Dice_{\mathbf{b}}$) and segmental arteries ($Dice_{\mathbf{a}}$). Best metrics are highlighted in bold. With fewer parameters and less training time, ImPulSe achieves better performances than its counterparts. Tr-res and Tr-time denote the input resolution during training and total training time (same number of epochs across models). DNC stands for "did not converge". Methods |  Tr-Res |  $Dice_{\mathbf{o}}$ |  $Dice_{\mathbf{b}}$ |  $Dice_{\mathbf{a}}$ | #Param | Tr-Time
---|---|---|---|---|---|---
Rikxoort et al. [25] |  $128^{3}$ |  60.63 |  66.01 |  67.54 | 38.9M | 11,009s
FCN [28] |  $128^{3}$ |  81.70 |  83.67 |  84.92 | 33.4M | 10,746s
U-Net [26] |  $128^{3}$ |  83.25 |  84.71 |  86.07 | 38.9M | 11,009s
DeepLabv3 [2] |  $128^{3}$ |  82.44 |  84.48 |  85.64 | 44.4M | 11,220s
Sliding-Window |  $64^{3}$ |  0.11 |  0.05 |  0.02 | 38.9M | DNC
ImPulSe |  $16^{3}$ |  83.54 |  85.14 |  86.26 | 33.3M | 4,962s
Figure 4: Predictions of ImPulSe and some of its counterparts. Thanks to
implicit functions, ImPulSe directly generates reconstruction of original
resolution and therefore outputs predictions with smoother surfaces compared
with its counterparts.

We compare ImPulse and its counterparts, including FCN [28], U-Net [26] and
DeepLabv3 [2] in the pulmonary segment reconstruction task. Additionally, we
roughly reproduce the pulmonary segment reconstruction method in Rikxoort et
al. [25] by feeding relative coordinates into a U-Net [26]. Finally, we train
an extra U-Net counterpart using the sliding-window strategy applied on raw
resolution image. All models share the same encoder architecture (ResNet18
[11, 29]), loss and training schedule to ensure fair comparison. Only CT
images are fed as inputs in this experiment. Images are cropped around the
lung area and downsampled to the size of $128^{3}$ in pre-processing except
the sliding-window experiment. During inference, ImPulSe directly outputs
reconstructions of the original resolution, while predictions of all
counterparts (except sliding-window) are upsampled to the original resolution
with tri-linear interpolation. Table 1 shows performances of ImPulSe and its
counterparts. ImPulSe achieves higher performances than its counterparts in
all metrics with 14% fewer parameters and 55% less training time (compared
against U-Net). The light-weighted decoder of ImPulSe (a two-layer MLP) leads
to its parameter efficiency, while implicit functions enable training on a
small portion of points rather than the entire voxel grid ($16^{3}$ for
ImPulSe versus $64^{3}$ or $128^{3}$ for its counterparts) and largely save
training time. Sliding-window U-Net does not even converge. This is because
learning pulmonary segments requires global information, which is missing in
sliding windows. Plus, sliding-window creates extreme class imbalance since
only a few segments are present in each window. Fig. 4 shows predictions of
ImPulSe and some of its counterparts. The reconstruction of ImPulSe has
smoother surfaces since it directly outputs prediction at the original
resolution.

###  3.3 What Makes for Pulmonary Segment Reconstruction?

In this section, we evaluate effects of different inputs in reconstruction of
pulmonary segments. Various combinations of the following five inputs are
considered: CT images (I), bronchi (B), arteries (A), veins (V) and lobes (L).
To obtain these inputs for inference, we train separate models for bronchus,
vessel and lobe segmentation. These models are trained using the same dataset
and splits as ImPulSe. For all input combinations containing L, B, A and V,
ImPulSe is trained using ground-truths as input and evaluated using both
ground-truths and predictions of aforementioned segmentation models. Table 2
shows performances of ImPulSe given different inputs. Metrics in parentheses
are evaluated using ground-truth of L, B, A and V as input. Our findings are
listed as follows:

Table 2: Reconstruction performances of ImPulSe given different combinations of inputs. I, L, B, A, and V represent images, lobes, bronchi, arteries and veins, respectively. We evaluate ImPulSe on both ground-truth and predictions of L, B, A and V. Metrics outside/inside parentheses are evaluated on predictions/ground-truth (not applicable for I). Best metrics on predictions are highlighted in bold. Inputs |  L |  BAV |  LBAV |  I |  IBAV
---|---|---|---|---|---
$Dice_{\mathbf{o}}$ |  4.03 (73.77) |  81.61 (81.55) |  72.25 (83.21) |  83.54 (n/a) |  84.63 (84.88)
$Dice_{\mathbf{b}}$ |  6.11 (79.01) |  85.72 (85.65) |  84.83 (86.77) |  85.14 (n/a) |  86.18 (86.08)
$Dice_{\mathbf{a}}$ |  6.01 (80.62) |  86.61 (86.75) |  85.53 (88.02) |  86.26 (n/a) |  87.00 (87.15)

##### Bronchi and vessels play important roles.

Even though I outperforms BAV in overall Dice score, BAV surpasses I in
bronchi and arteries. Since $Dice_{\mathbf{b}}$ and $Dice_{\mathbf{a}}$ are
more important in pulmonary segment reconstruction than the overall Dice, it
is clear that bronchi and vessels play crucial roles in this task. Plus,
bronchi and vessels are less noisy than images since they are binary while
images are encoded in HU values of wide ranges.

##### Images and BAV are complementary to each other.

IBAV achieves the highest performances in all metrics. We hypothesize that
this is due to the complementary effect of I and BAV. I signals some basic
knowledge not presented in BAV, e.g., contours of lungs. BAV highlights
bronchi and vessels, which have to be implicitly learned if only image inputs
are given.

##### Lobe as input is prone to overfitting.

Adding lobes into inputs largely impairs performances (over 9% overall Dice
drop from BAV to LBAV). We attribute this to the over-simplified structure of
pulmonary lobes, which makes neural networks prone to overfitting. This is
backed up by the fact that ImPulse only shows large accuracy drops
transferring from ground-truth to prediction when it takes lobes as (part of)
inputs. Furthermore, lobes include no information related to segmental
boundaries, making it difficult to subdivide lobes into segments.

##  4 Conclusions

In this paper, we investigate this question: what makes for automatic
reconstruction of pulmonary segments? We first set concrete definitions of
pulmonary segment anatomy, and suggest approapraite metrics for the
reconstruction task. We propose ImPulSe, an implicit-function-based model for
pulmonary segment reconstruction. Using implicit fields, ImPulSe generates
outputs of arbitrary resolutions with higher training and parameter efficiency
compared with its counterparts. In future works, we will investigate if
template deformation [8, 31, 14, 33] and including intersegmental veins are
beneficial in this task.

####  4.0.1 Acknowledgment.

This work was supported in part by National Science Foundation of China
(82071990, 61976238). This work was also supported in part by a Swiss National
Science Foundation grant. We would like to thank Lei Liang for his generous
help in proofreading, and the anonymous (meta-)reviewers for their valuable
comments.

## References

  * [1] Boyden, E.A.: The intrahilar and related segmental anatomy of the lung. Surgery 18, 706–31 (1945)
  * [2] Chen, L.C., Papandreou, G., Schroff, F., Adam, H.: Rethinking atrous convolution for semantic image segmentation. arXiv Preprint abs/1706.05587 (2017)
  * [3] Chen, Z., Zhang, H.: Learning implicit fields for generative shape modeling. Conference on Computer Vision and Pattern Recognition pp. 5932–5941 (2019)
  * [4] Chibane, J., Alldieck, T., Pons-Moll, G.: Implicit functions in feature space for 3d shape reconstruction and completion. Conference on Computer Vision and Pattern Recognition pp. 6968–6979 (2020)
  * [5] Frick, A.E., Raemdonck, D.V.: Segmentectomies. Shanghai Chest 1, 28–28 (2017)
  * [6] Gerard, S.E., Patton, T.J., Christensen, G., Bayouth, J.E., Reinhardt, J.M.: Fissurenet: A deep learning approach for pulmonary fissure detection in ct images. IEEE Transactions on Medical Imaging 38, 156–166 (2019)
  * [7] Gerard, S.E., Reinhardt, J.M.: Pulmonary lobe segmentation using a sequence of convolutional neural networks for marginal learning. International Symposium on Biomedical Imaging pp. 1207–1211 (2019)
  * [8] Groueix, T., Fisher, M., Kim, V.G., Russell, B.C., Aubry, M.: 3d-coded: 3d correspondences by deep deformation. In: European Conference on Computer Vision (2018)
  * [9] Handa, Y., Tsutani, Y., Mimae, T., Miyata, Y., Okada, M.: Postoperative pulmonary function after complex segmentectomy. Annals of Surgical Oncology 28, 8347–8355 (2021)
  * [10] Harada, H., Okada, M., Sakamoto, T., Matsuoka, H., Tsubota, N.: Functional advantage after radical segmentectomy versus lobectomy for lung cancer. Annals of Thoracic Surgery 80, 2041–2045 (12 2005)
  * [11] He, K., Zhang, X., Ren, S., Sun, J.: Deep residual learning for image recognition. Conference on Computer Vision and Pattern Recognition pp. 770–778 (2016)
  * [12] Huang, X., Yang, J., Wang, Y., Chen, Z., Li, L., Li, T., Ni, B., Zhang, W.: Representation-agnostic shape fields. In: International Conference on Learning Representations (2022)
  * [13] Isensee, F., Jaeger, P.F., Kohl, S.A.A., Petersen, J., Maier-Hein, K.H.: nnu-net: a self-configuring method for deep learning-based biomedical image segmentation. Nature Methods 18, 203–211 (2 2021)
  * [14] Jack, D., Pontes, J.K., Sridharan, S., Fookes, C., Shirazi, S.A., Maire, F., Eriksson, A.P.: Learning free-form deformations for 3d object reconstruction. In: Asian Conference on Computer Vision (2018)
  * [15] Jackson, C.L., Huber, J.F.: Correlated applied anatomy of the bronchial tree and lungs with a system of nomenclature. Chest 9, 319–326 (1943)
  * [16] Mescheder, L.M., Oechsle, M., Niemeyer, M., Nowozin, S., Geiger, A.: Occupancy networks: Learning 3d reconstruction in function space. Conference on Computer Vision and Pattern Recognition pp. 4455–4465 (2019)
  * [17] Milletari, F., Navab, N., Ahmadi, S.A.: V-net: Fully convolutional neural networks for volumetric medical image segmentation. International Conference on 3D Vision pp. 565–571 (2016)
  * [18] Nardelli, P., Jimenez-Carretero, D., Bermejo-Peláez, D., Washko, G.R., Rahaghi, F.N., Ledesma-Carbayo, M.J., Estépar, R.S.J.: Pulmonary artery–vein classification in ct images using deep learning. IEEE Transactions on Medical Imaging 37, 2428–2440 (2018)
  * [19] Oizumi, H., Kanauchi, N., Kato, H., Endoh, M., Suzuki, J., Fukaya, K., Sadahiro, M.: Anatomic thoracoscopic pulmonary segmentectomy under 3-dimensional multidetector computed tomography simulation: A report of 52 consecutive cases. Journal of Thoracic and Cardiovascular Surgery 141, 678–682 (3 2011)
  * [20] Oizumi, H., Kato, H., Endoh, M., Inoue, T., Watarai, H., Sadahiro, M.: Techniques to define segmental anatomy during segmentectomy. Annals of Cardiothoracic Surgery 3, 170–175 (2014)
  * [21] Park, J.J., Florence, P.R., Straub, J., Newcombe, R.A., Lovegrove, S.: Deepsdf: Learning continuous signed distance functions for shape representation. Conference on Computer Vision and Pattern Recognition pp. 165–174 (2019)
  * [22] Paszke, A., Gross, S., Massa, F., Lerer, A., et al.: Pytorch: An imperative style, high-performance deep learning library. In: Advances in Neural Information Processing Systems (2019)
  * [23] Peng, S., Niemeyer, M., Mescheder, L., Pollefeys, M., Geiger, A.: Convolutional occupancy networks. In: European Conference on Computer Vision (2020)
  * [24] Qin, Y., Zheng, H., Gu, Y., Huang, X., Yang, J., Wang, L., Yao, F., Zhu, Y.M., Yang, G.Z.: Learning tubule-sensitive cnns for pulmonary airway and artery-vein segmentation in ct. IEEE Transactions on Medical Imaging 40, 1603–1617 (2021)
  * [25] van Rikxoort, E.M., de Hoop, B., van Amelsvoort-van de Vorst, S., Prokop, M., van Ginneken, B.: Automatic segmentation of pulmonary segments from volumetric chest ct scans. IEEE Transactions on Medical Imaging 28, 621–630 (2009)
  * [26] Ronneberger, O., Fischer, P., Brox, T.: U-net: Convolutional networks for biomedical image segmentation. In: Conference on Medical Image Computing and Computer Assisted Intervention (2015)
  * [27] Schuchert, M.J., Pettiford, B.L., Keeley, S., et al.: Anatomic segmentectomy in the treatment of stage i non-small cell lung cancer. Annals of Thoracic Surgery 84, 926–933 (9 2007)
  * [28] Shelhamer, E., Long, J., Darrell, T.: Fully convolutional networks for semantic segmentation. IEEE Transactions on Pattern Analysis and Machine Intelligence 39, 640–651 (2017)
  * [29] Tran, D., Wang, H., Torresani, L., Ray, J., LeCun, Y., Paluri, M.: A closer look at spatiotemporal convolutions for action recognition. Conference on Computer Vision and Pattern Recognition pp. 6450–6459 (2018)
  * [30] Ugalde, P., de Jesus Camargo, J., Deslauriers, J.: Lobes, fissures, and bronchopulmonary segments. Thoracic Surgery Clinics 17(4), 587–599 (2007)
  * [31] Wang, Y., Aigerman, N., Kim, V.G., Chaudhuri, S., Sorkine-Hornung, O.: Neural cages for detail-preserving 3d deformations. Conference on Computer Vision and Pattern Recognition pp. 72–80 (2020)
  * [32] Wisnivesky, J.P., Henschke, C.I., Swanson, S., Yankelevitz, D.F., Zulueta, J., Marcus, S., Halm, E.A.: Limited resection for the treatment of patients with stage ia lung cancer. Annals of Surgery 251, 550–554 (3 2010)
  * [33] Yang, J., Wickramasinghe, U., Ni, B., Fua, P.: Implicitatlas: Learning deformable shape templates in medical imaging. In: Conference on Computer Vision and Pattern Recognition. pp. 15861–15871 (2022)
  * [34] Zhou, Z., Siddiquee, M.M.R., Tajbakhsh, N., Liang, J.: Unet++: Redesigning skip connections to exploit multiscale features in image segmentation. IEEE Transactions on Medical Imaging 39, 1856–1867 (6 2020)

Figure A1: The overview of pulmonary segment anatomy. There are 18 pulmonary segments in total, with eight segments in the left lung and right segments in the right lung. Bronchi, arteries and veins between left and right lung are highlighted in gray, blue and red, respectively. Table A1: Dice scores of bronchi, arteries and veins. Here veins are further divided into intersegmental veins ($Dice_{\mathbf{inter}}$) and intrasegmental veins ($Dice_{\mathbf{intra}}$). All vein-related metrics, especially $Dice_{\mathbf{inter}}$, are significantly lower than those of bronchi and arteries. This supports our argument that veins are ambiguous in pulmonary segment reconstruction and should not be considered in evaluation. Note that the sliding-window U-Net is omitted in this table since it did not converge. Methods |  $Dice_{\mathbf{b}}$ |  $Dice_{\mathbf{a}}$ |  $Dice_{\mathbf{v}}$ |  $Dice_{\mathbf{inter}}$ |  $Dice_{\mathbf{intra}}$
---|---|---|---|---|---
Rikxoort et al. [25] |  66.01 |  67.54 |  63.01 |  45.92 |  65.42
FCN [28] |  83.67 |  84.92 |  77.77 |  61.63 |  80.57
U-Net [26] |  84.71 |  86.07 |  79.53 |  64.07 |  82.12
DeepLabv3 [2] |  84.48 |  85.64 |  78.57 |  61.65 |  81.49
ImPulSe |  85.14 |  86.26 |  79.51 |  63.80 |  82.20


# Efficient Certifiable Randomness from a Single Quantum Device

Urmila Mahadev California Institute of Technology, USA. Email:
<EMAIL_ADDRESS>Umesh Vazirani UC Berkeley, USA. Email:
<EMAIL_ADDRESS>Thomas Vidick California Institute of Technology,
USA. Email<EMAIL_ADDRESS>
###### Abstract

Brakerski et. al [BCM+18] introduced the model of cryptographic testing of a
single untrusted quantum device and gave a protocol for certifiable randomness
generation. We use the leakage resilience properties of the Learning With
Errors problem to address a key issue left open in previous work — the rate of
generation of randomness. Our new protocol can certify $\Omega(n)$ fresh bits
of randomness in constant rounds, where $n$ is a parameter of the protocol and
the total communication is $O(n)$, thus achieving a nearly optimal rate. The
proof that the output is statistically random is conceptually simple and
technically elementary.

##  1 Introduction

The testing of quantum devices poses fundamental difficulties due to their
computational power and restrictions imposed by the laws of quantum mechanics
on access to their internal state. [BCM+18] introduced a model in which a
purely classical verifier uses cryptography to enhance its interactions with a
single untrusted and polynomial-time bounded quantum computer. In this model,
they gave a protocol for generating certifiably random $n$-bit strings through
$\Theta(n)$ iterations of a basic “qubit certification test.” The correctness
of the qubit certification test is based on a cryptographic primitive called a
Noisy Trapdoor Claw-free functions (NTCFs) with an adaptive hardcore bit. This
primitive in turn was implemented based on the (post-quantum) hardness of the
Learning with Errors problem (LWE). The qubit certification test has since
been used for other tasks including quantum homomorphic encryption [Mah20],
quantum money [Rad19], and delegated quantum computation [Mah18], and has led
to many follow-up works and extensions [CCY20, ACGH20, BKVV20, HG21, GMP22].

Recall that the qubit certification test from [BCM+18] allows a classical
verifier to reach into a quantum computer’s Hilbert space and enforce a qubit
structure in it, by ensuring that the untrusted quantum computer creates a
$\left|+\right>$ state and measures it in the computational basis, thereby
generating $1$ bit of randomness. While the analysis of [BCM+18] is powerful,
in that it uses cryptography to constrain the behavior of a quantum machine,
it leaves a large gap between intuition and what is possible to prove. In
particular, [BCM+18] conjectured that in order to pass the protocol a prover
must generate roughly $n$ bits of randomness per round, while the analysis
could only guarantee a fraction of a bit.

In this paper we show that a small change to the qubit certification test
results in a protocol which consists of two rounds of interaction, each
communicating $\tilde{\Theta}(n)$ classical bits, and is such that any prover
that succeeds with high enough constant probability in the protocol generates
bits that are statistically close to a distribution with $\Theta(n)$ bits of
min-entropy, even conditioned on the verifier’s random questions. This
conclusion holds as long as the prover is quantum polynomial-time bounded and
the (post-quantum) Learning with Errors (QLWE) assumption holds for the
duration of the protocol. We refer to Protocol 2.3 for a description of the
protocol and Theorem 4.12 for the formal guarantees. The small change that we
make, which is described below, allows us to greatly simplify the proof of
correctness while achieving a nearly optimal rate of randomness generation as
a function of the total number of bits sent from the quantum device to the
verifier, thereby also providing a way of certifying that the quantum device
has roughly $n$ bits of quantum memory. We note that a quantum dimension test
was recently obtained in [FWZ22] by performing parallel repetition of (a
variant of) the protocol from [BCM+18]. In contrast, our protocol is more
efficient (constant rounds, linear communication) and our analysis far more
direct.111However, [FWZ22], see also [GMP22], proves a stronger rigidity
result for their protocol, which extends the qubit test to certain $n$-qubit
states.

Beyond these quantitative improvements, our new protocol provides the first
successful attempt to move beyond NCTFs as a tool to help a classical verifier
enforce structure in the quantum computer’s Hilbert space. The main new
ingredient in the improved protocol is a powerful notion from classical
cryptography, called leakage resilience, which helps to more fully
characterize the quantum computer.

Our point of departure is that whereas NTCFs are essentially $2$-to-$1$
functions, here we consider cryptographic primitives that look like $k$-to-$1$
functions for exponentially large $k$, with the goal of certifying $\log k$
bits of randomness, rather than just $1$. More concretely, the $k$-to-$1$
function arises naturally from the use of leakage resilience techniques
developed for the use of LWE in cryptography, and in particular the study of
side channel attacks [GKPV10]. The main idea to establish leakage resilience
of LWE consists in replacing the uniformly random LWE matrix $A$ with a
computationally indistinguishable lossy matrix $\tilde{A}=BC+E$ where $C$ has
a large kernel, and $E$ is “small”. Thus, up to the matrix $E$, which is
needed to guarantee computational indistinguishability, $\tilde{A}$ is a close
to a low-rank matrix—hence the terminology “lossy”.

To see how this would work let’s start with a small change to the qubit
certification protocol by switching from the use of an LWE matrix $A$ to a
lossy matrix $\tilde{A}$. The reader familiar with the qubit certification
protocol will see how at first glance this promises many more random bits.
This is because, informally, in the protocol the quantum prover is tasked with
preparing a uniform superposition
$\frac{1}{\sqrt{2}}(\left|x_{0}\right>+\left|x_{1}\right>)$ over two vectors
$x_{0}$ and $x_{1}$ such that $Ax_{0}$ and $A(x_{1}-s)$ are sufficiently
close, with $s$ a secret that is provided to the prover in encoded form. If
the matrix $A$ is lossy then intuitively $\left|x_{0}\right>$ would be
replaced by $\frac{1}{\sqrt{k}}\sum_{i}|x_{0,i}\rangle$ where $x_{0,i}$ ranges
over all preimages of $Ax_{0}$, and similarly for $\left|x_{1}\right>$. Thus,
by asking such a prover to measure its superposition in the computational
basis one may hope to obtain approximately $\log k$ bits of randomness as
opposed to $1$.

To keep the prover honest, the qubit certification protocol performs an
equation test consisting of a measurement in the Hadamard basis — the crux of
protocol lies in the fact that passing this test implies that the prover must
actually have a superposition over both $x_{0}$ and $x_{1}=x_{0}-s$.
Unfortunately, the use of a lossy matrix and the appearance of multiple
preimages completely breaks the structure of these tests, and it is unclear
how to even test the prover’s behavior for the case when $k$-to-$1$ functions
are used. The actual protocol we analyze has the following structure: in the
test round it uses a $2$-to-$1$ function, while in the randomness generation
round it uses a $k$-to-$1$ function. To do this the verifier sends the prover
an LWE sample $As+e$ in the test round and a lossy sample $\tilde{A}s+E$ in
the generation round. From the viewpoint of the prover the two samples are
indistinguishable, and one might hope that this keeps the prover honest in the
generation round. Armed with this intuition, the challenge lies in showing
that this simple test is sufficient to ensure that an untrusted prover is
forced to output a large amount of min-entropy in the generation round.

Unfortunately this idea faces an immediate difficulty: the tests used in the
qubit certification protocol require the verifier to have knowledge of a
secret trapdoor that allows inversion of the LWE matrix $A$. The use of this
trapdoor rules out a direct kind of hybrid argument where the LWE matrix would
be replaced by an indistinguishable lossy matrix while keeping the prover’s
success probability in the protocol unchanged. Our main idea to overcome this
is to introduce a hypothetical _quantum_ verifier who is able to perform a
meaningful test on the quantum prover _without_ making use of the trapdoor.
This hypothetical verifier is used as an intermediate tool in the analysis,
but the final protocol remains a classical verifier protocol. We explain these
ideas in more detail in the next section, where we also precisely introduce
the qubit certification test to ground the discussion.

NTCFs have proved to be a powerful tool in constraining, characterizing and
verifying the actions of untrusted quantum computers. This work can be viewed
as a step towards leveraging more general cryptographic primitives, and
suggests that leakage resilience may be a powerful new tool in this direction.

##### Acknowledgments

T.V. is supported by AFOSR YIP award number FA9550-16-1-0495, a grant from the
Simons Foundation (828076, TV), MURI Grant FA9550-18-1-0161, the NSF QLCI
program through grant number OMA-2016245 and the IQIM, an NSF Physics
Frontiers Center (NSF Grant PHY-1125565) with support of the Gordon and Betty
Moore Foundation (GBMF-12500028). U.M. is supported by an NSF CAREER grant
(2048204). U.V is supported by Vannevar Bush faculty fellowship
N00014-17-1-3025, MURI Grant FA9550-18-1-0161, and DOE NQISRC Quantum Systems
Accelerator grant FP00010905.

##  2 Overview of results and techniques

We begin with a reminder of the randomness protocol from [BCM+18]. For clarity
we delay a discussion of parameters to Section 3. We let $q\geq 2$ be a prime
and denote vectors and matrices over $\mathbb{Z}_{q}$ using bold font such as
$\mathbf{u}$, $\mathbf{A}$. The protocol from [BCM+18] (with some of the more
technical details omitted for simplicity) consists in the sequential
repetition of the following elementary $2$-round protocol between a trusted
classical _verifier_ and an untrusted quantum polynomial time device, or
_prover_ :

######  Protocol 2.1.

Qubit Certification Test.

  1. 1.

The verifier samples $s\in\mathbbm{Z}_{2}^{n}$,
$\mathbf{A}\in\mathbbm{Z}_{q}^{m\times n}$ along with its trapdoor $t_{A}$ and
an error vector $\mathbf{e}\in\mathbbm{Z}_{q}^{m}$. The verifier computes
$\mathbf{u}=\mathbf{A}s+\mathbf{e}$.

  2. 2.

The verifier sends the sample $(\mathbf{A},\mathbf{u})$ to the prover.

  3. 3.

The prover reports an image $\mathbf{y}\in\mathbb{Z}_{q}^{m}$ to the verifier.

  4. 4.

The verifier chooses to either run a test round or a generation round with
equal probability $\frac{1}{2}$:

    1. (a)

Generation round. The verifier runs a preimage test: he asks the prover for a
bit $b$ and a preimage $\mathbf{x}$ of $\mathbf{y}$ and checks that
$\lVert\mathbf{y}-\mathbf{A}\mathbf{x}-b\cdot\mathbf{u}\rVert$ is sufficiently
small (at most $B_{P}\sqrt{m}$).

    2. (b)

Test round. The verifier runs an equation test: the verifier uses $t_{A}$ to
compute $\mathbf{x}_{0}$ such that
$\mathbf{y}=\mathbf{A}\mathbf{x}_{0}+\mathbf{e}_{0}$ for some small
$\mathbf{e}_{0}$ and asks the prover for an equation, which consists of a bit
$c$ and a string $d\in\\{0,1\\}^{n\log q}$. The verifier checks that
$c=d\cdot(\mathbf{x}_{0}\oplus(\mathbf{x}_{0}-s))$.222Recall from [BCM+18]
that the bit $c$ is computed by converting $\mathbf{x}_{0},\mathbf{x}_{0}-s$
to their binary representations, and that there will also be a check on $d$ to
ensure that the equation is not trivial.

To understand the rest of this overview, it is not necessary to understand all
the details of the above protocol. It is important to understand what the
honest prover’s state looks like, which we now describe, as this will provide
intuition for the changes we will make to the protocol. After reporting $y$ in
Protocol 2.1, an honest prover would hold the state

$\frac{1}{\sqrt{2}}\big{(}\left|0\right>\left|\mathbf{x}_{0}\right>+\left|1\right>\left|\mathbf{x}_{0}-s\right>\big{)}\;.$
(1)

To pass the preimage test the prover would measure their state in the standard
basis, and to pass the equation test they would measure the state in the
Hadamard basis. Both tests would be passed with certainty.

In [BCM+18] it was shown that each generation round of the qubit certification
test generates a fraction of a bit of randomness. The proof relies on a
property called the _adaptive hardcore bit property_ , which (informally)
states that if a computationally bounded prover can pass both the equation
test and the preimage test at the same time then the prover can break the
Learning With Errors assumption by learning a bit of the secret $s$. The
adaptive hardcore bit property implies that the prover must hold an
essentially uniform superposition over both $x_{0}$ and $x_{0}-s$, rather than
a collapsed state. This is because if the superposition was not uniform then
the prover could measure it in the computational basis without completely
disturbing it, and then generate an equation. The prover would thus hold both
an equation and a preimage at the same time, violating the adaptive hardcore
bit property.

The difficulty of learning even a bit of the secret $s$ is a commonly used
notion in classical cryptography referred to as leakage resilience. To prove
leakage resilience, the idea is to replace the matrix $\mathbf{A}$ with a
computationally indistinguishable lossy matrix
$\tilde{\mathbf{A}}=\mathbf{B}\mathbf{C}+\mathbf{E}$, where
$\mathbf{C}\in\mathbbm{Z}_{q}^{\ell\times n}$ ($n\approx\ell\log q)$). The
computational indistinguishability follows from the security of a smaller
instance of LWE (with secrets in $\mathbbm{Z}_{q}^{\ell}$ rather than
$\mathbbm{Z}_{q}^{n}$). Now, the sample $\tilde{\mathbf{A}}s+\mathbf{e}$ hides
$s$ quite well, as the matrix $\mathbf{C}$ has a kernel of size $q^{n-\ell}$.
As mentioned in the introduction there is one particularly intuitive path to
make use of leakage resilience to collect a polynomial amount of randomness
per round: we could replace the matrix $\mathbf{A}$ in Protocol 2.1 with a
lossy matrix $\tilde{\mathbf{A}}$. As a result, for a given image $\mathbf{y}$
reported by the prover there are now up to $q^{n-\ell}$ valid preimages for
each $b$, rather than just 1; the hope is to leverage this structure to
collect linearly many bits of randomness per generation round.

The key difficulty lies in the equation test: the equation test is crucial for
ensuring that the prover is actually generating randomness, as passing the
equation test implies that the prover must actually have a superposition over
both $\mathbf{x}_{0}$ and $\mathbf{x}_{0}-s$. If the superposition over two
preimages is replaced by a superposition over many, it is unclear how to
perform a check in the Hadamard basis. Moreover, in the equation test in step
4(b) of Protocol 2.1, the verifier relied on using a trapdoor to invert
$\mathbf{y}$, thereby finding $\mathbf{x}_{0}$, which was used to compute
$d\cdot(\mathbf{x}_{0}\oplus(\mathbf{x}_{0}-s))$. Of course, the verifier can
no longer rely on a trapdoor, as the image $\mathbf{y}$ inherently has many
valid preimages. Additionally, a useful analytical tool would be to compare
the prover’s behavior in the two different protocols arising from using either
$\mathbf{A}$ or $\tilde{\mathbf{A}}$. If a trapdoor is required, we cannot use
computational indistinguishability to carry out such an analysis.

To handle both issues at once, consider a hypothetical variant of Protocol 2.1
in which the verifier is quantum rather than classical and is allowed access
to the prover’s state. Note that this hypothetical protocol will only be used
as a tool in the analysis; our final protocol will still have a classical
verifier. The advantage of using a quantum verifier is that the verifier’s
knowledge of the secret $s$, as well as access to the prover’s state, can be
used to compute $x_{0}$, thereby removing the need for a trapdoor. This can be
done as long as the prover’s state is in a superposition over preimages, which
we can assume if the prover passes the preimage test perfectly. For intuition,
observe how this can be done in the case of an honest prover. The prover’s
state (as in equation 1) is

$\frac{1}{\sqrt{2}}\big{(}\left|0\right>\left|\mathbf{x}_{0}\right>+\left|1\right>\left|\mathbf{x}_{0}-s\right>\big{)}\;.$

The verifier can copy the preimage ($\mathbf{x}_{0}$ or $\mathbf{x}_{0}-s$)
into an auxiliary register. He can then use his knowledge of $s$ to perform a
controlled shift by $s$; if the first bit of the prover’s state is 1, the
verifier adds $s$ to the auxiliary register. As a result, the auxiliary
register holds $\mathbf{x}_{0}$, thereby removing the need for a trapdoor.
Moreover, if the state was initially in a superposition over many preimages,
rather than just 2, the verifier’s actions will collapse the state to only two
preimages, $\mathbf{x}_{0}$ and $\mathbf{x}_{0}-s$, thereby making it possible
to run the equation test. This protocol is referred to as the _quantum
verifier preimage extraction protocol_ , and is described in detail in
Protocol 4.3.

The preceding idea is the core of our quantum verifier lossy randomness
protocol (recall that it is a hypothetical protocol, which will only be used
as an analytical tool). The protocol is essentially a duplicate of Protocol
2.1, except with the matrix $\mathbf{A}$ replaced by a lossy matrix
$\tilde{\mathbf{A}}$ and the trapdoor recovery of $\mathbf{x}_{0}$ replaced by
the quantum extraction protocol described above.

######  Protocol 2.2.

Quantum Verifier Lossy Randomness Protocol

  1. 1.

The verifier samples $s\in\\{0,1\\}^{n}$, a lossy matrix
$\tilde{\mathbf{A}}\in\mathbbm{Z}_{q}^{m\times n}$ and an error vector
$\mathbf{e}\in\mathbbm{Z}_{q}^{m}$. The verifier computes
$\mathbf{u}=\tilde{\mathbf{A}}s+\mathbf{e}$.

  2. 2.

The verifier sends the sample $(\tilde{\mathbf{A}},\mathbf{u})$ to the prover.

  3. 3.

The prover reports an image $\mathbf{y}\in\mathbbm{Z}_{q}^{m}$ to the
verifier.

  4. 4.

The verifier chooses to either run a test round or a generation round:

    1. (a)

Generation round:  The verifier runs a preimage test: he asks the prover for a
bit $b$ and a corresponding preimage $\mathbf{x}$ of $\mathbf{y}$, and checks
that $\lVert\mathbf{y}-\tilde{\mathbf{A}}\mathbf{x}-b\cdot\mathbf{u}\rVert$ is
sufficiently small (at most $B_{P}\sqrt{m}$).

    2. (b)

Test round:  The verifier runs an equation test: the verifier uses the
preimage extraction protocol (Protocol 4.3) to compute $\mathbf{x}_{0}$ from
$\mathbf{y}$, and then asks the prover for an equation, which consists of a
bit $c$ and a string $d\in\\{0,1\\}^{n\log q}$. The verifier checks that
$c=d\cdot(\mathbf{x}_{0}\oplus(\mathbf{x}_{0}-s))$.

In Theorem 4.6 we show that any prover that succeeds in the test round of
Protocol 2.2 with high enough probability returns a pair $(b,\mathbf{x})$ in
the generation round of the protocol that has min-entropy that scales as
$n-\ell\log q$, even conditioned on data exchanged in the first round of the
protocol (i.e. $\tilde{\mathbf{A}}$, $\mathbf{u}$ and
$\mathbf{y}$).333Precisely, we analyze the smooth min-entropy of the
distribution: a prover with success $1-\varepsilon$ in the test round will
lead to a distribution that is within statistical distance
$\mathrm{poly}(\varepsilon)$ of a distribution with high conditional entropy.
The proof is relatively simple, and consists of two key steps. The first step
is observe that in order to pass the test round, the prover’s collapsed state
after the preimage extraction protocol must be in essentially a uniform
superposition over the two preimages. To prove this, we use the fact that this
statement is true in Protocol 2.1; therefore, if it did not hold for Protocol
2.2, it would be a means of distinguishing between a lossy matrix
$\tilde{\mathbf{A}}$ and a uniform matrix $\mathbf{A}$. The second step relies
on the fact that the secret $s$ is information theoretically hidden; even
given the lossy sample $\mathbf{u}$, there are exponentially many possible
values for $s$. Therefore, prior to the verifier’s preimage extraction
protocol, the prover’s state must be in an essentially uniform superposition
over the exponentially many preimages of $\mathbf{y}$, since the state must
collapse to a balanced superposition over two preimages regardless of the
verifier’s choice of $s$.

Our final protocol is a classical verifier lossy randomness protocol, which
uses Protocol 2.2 as a tool in the analysis. To revert back to a classical
verifier protocol, ideally we could just remove step 4(b) of Protocol 2.2, as
this is the only step that requires a quantum verifier. Of course, removing
this step is problematic; without an equation test, we cannot guarantee that
the prover ever holds a superposition over preimages (rather than just 1
preimage). Our solution is to replace step 4(b) of Protocol 2.2 with step 4(b)
of Protocol 2.1; in other words, our classical verifier lossy randomness
protocol combines the test rounds of the original randomness protocol
(Protocol 2.1) with the generation rounds of our lossy randomness protocol
(Protocol 2.2):

######  Protocol 2.3.

Lossy Randomness Protocol The verifier randomly chooses whether to execute a
generation round or a test round. In the case of a generation round, the
verifier and prover proceed as in Protocol 2.2, from the first step through
the generation round (i.e. steps 1, 2, 3 and 4a). In the case of a test round,
the verifier and prover proceed with Protocol 2.1 steps 1, 2, 3 and 4b.

Protocol 2.3 is restated in more detail in Section 4.3. The key in combining
these protocols is that they are computationally indistinguishable: a prover
passes the test (resp. generation) round of Protocol 2.1 if and only if they
also pass the test (resp. generation) round of Protocol 2.2. Otherwise, the
prover could be used to distinguish between lossy and uniform matrices. This
computational distinguishability argument relies on the fact that the
probability of passing either protocol can be computed using a quantum
algorithm with knowledge of the secret $s$; again, in Protocol 2.1, the use of
the trapdoor can be replaced with a quantum procedure with knowledge of $s$.
Therefore, if the two probabilities differ non-negligibly, knowledge of $s$
can be used to distinguish between lossy and uniform matrices (using a quantum
algorithm). These arguments are formalized in Section 4.3.

##  3 Technical preliminaries

We start with some notation and definitions required for the formal analysis,
which follows in Section 4.

###  3.1 Notation

We use the shorthands PPT and QPT for probabilistic and quantum polynomial-
time respectively. We write $\operatorname{negl}(\lambda)$ for any function
$f:\mathbb{N}\to\mathbb{R}_{+}$ such that for any polynomial $p$,
$\lim_{\lambda\to\infty}p(\lambda)f(\lambda)=0$. For $D$ a distribution on a
finite set $\mathcal{X}$ we write $e\leftarrow D$ for a random element
$e\in\mathcal{X}$ with distribution $D$. If $D$ is uniform we also write
$e\leftarrow_{U}\mathcal{X}$. We use bold font such as $\mathbf{u},\mathbf{A}$
to denote vectors or matrices whose entries are taken from $\mathbbm{Z}_{q}$.

##### Error distributions.

For a positive real $B$ and a positive integer $q$, the truncated discrete
Gaussian distribution over $\mathbbm{Z}_{q}$ with parameter $B$ is the
distribution supported on $\\{x\in\mathbbm{Z}_{q}:\,\|x\|\leq B\\}$ with
density

$D_{\mathbbm{Z}_{q},B}(x)\,=\,\frac{e^{\frac{-\pi\lVert
x\rVert^{2}}{B^{2}}}}{\sum\limits_{x\in\mathbbm{Z}_{q},\,\|x\|\leq
B}e^{\frac{-\pi\lVert x\rVert^{2}}{B^{2}}}}\;.$ (2)

More generally, for a positive integer $m$ the truncated discrete Gaussian
distribution over $\mathbbm{Z}_{q}^{m}$ with parameter $B$ is the distribution
supported on $\\{x\in\mathbbm{Z}_{q}^{m}:\,\|x\|\leq B\sqrt{m}\\}$ with
density

$\forall x=(x_{1},\ldots,x_{m})\in\mathbbm{Z}_{q}^{m}\;,\qquad
D_{\mathbbm{Z}_{q}^{m},B}(x)\,=\,D_{\mathbbm{Z}_{q},B}(x_{1})\cdots
D_{\mathbbm{Z}_{q},B}(x_{m})\;.$ (3)

##### Min-entropy.

For random variables $X$ and $Y$ and $\varepsilon\geq 0$ define the
_$\varepsilon$ -smooth conditional entropy of $X$ given $Y$_ by

$H_{\infty}^{\varepsilon}(X|Y)\,=\,\sup_{\tilde{X}\tilde{Y}:\,\|XY-\tilde{X}\tilde{Y}\|_{TV}\leq\varepsilon}-\log\Big{(}\max_{y:\,\Pr(\tilde{Y}=y)>0}\;\max_{x}\;\Pr\big{(}\tilde{X}=x|\tilde{Y}=y\big{)}\Big{)}\;.$

Here the supremum is taken over all sub-normalized pairs of random variables
$(\tilde{X},\tilde{Y})$ with total variation distance at most $\varepsilon$
from $(X,Y)$.

###  3.2 Parameters

For convenience we collect here a description of the main parameters that are
used in all our protocols. Let $\lambda$ be a security parameter. All other
parameters are functions of $\lambda$. Let $q\geq 2$ be a prime integer. Let
$\ell,n,m,w\geq 1$ be polynomially bounded functions of $\lambda$ and
$B_{L},B_{V},B_{P}$ be positive integers such that the following conditions
hold

  1. (A.1)

$n=\Omega(\ell\log q)$ and $m=\Omega(n\log q)$,

  2. (A.2)

$w=n\lceil\log q\rceil$,

  3. (A.3)

$B_{P}=\frac{q}{2C_{T}\sqrt{mn\log q}}$, for $C_{T}$ a universal constant,

  4. (A.4)

$2\sqrt{n}\leq B_{L}<B_{V}<B_{P}$,

  5. (A.5)

The ratios $\frac{B_{P}}{B_{V}}$ and $\frac{B_{V}}{B_{L}}$ are both super-
polynomial in $\lambda$.

This setting of parameters is the same as the one in [BCM+18]. The
computational assumption that underlies our results is the same assumption
under which the function family $\mathcal{F}_{\mathrm{LWE}}$ introduced in
[BCM+18] is an NTCF family, namely the Learning with Errors (LWE) assumptions
with parameters $\ell,q$ and $B_{L}$. (In contrast to [BCM+18], since we do
not consider quantum side information, we do not need to make the assumption
with respect to quantum advice.)

######  Definition 3.1.

For a security parameter $\lambda$, let $n,m,q\in\mathbb{N}$ be integer
functions of $\lambda$. Let $\chi=\chi(\lambda)$ be a distribution over
$\mathbbm{Z}$. The $\mathrm{LWE}_{n,m,q,\chi}$ problem is to distinguish
between the distributions
$(\mathbf{A},\mathbf{A}\mathbf{s}+\mathbf{e}\pmod{q})$ and
$(\mathbf{A},\mathbf{u})$, where
$\mathbf{A}\leftarrow_{U}\mathbb{Z}_{q}^{n\times m}$,
$\mathbf{s}\leftarrow_{U}\mathbbm{Z}_{q}^{n}$,
$\mathbf{{e}}\leftarrow\chi^{m}$, and
$\mathbf{u}\leftarrow_{U}\mathbbm{Z}_{q}^{m}$. Often we consider the hardness
of solving $\mathrm{LWE}$ for any function $m$ such that $m$ is at most a
polynomial in $n\log q$. This problem is denoted $\mathrm{LWE}_{n,q,\chi}$.

In this paper we make the assumption that no quantum polynomial-time procedure
can solve the $\mathrm{LWE}_{n,q,\chi}$ problem with more than a negligible
advantage in $\lambda$, when $\chi$ is the distribution
$D_{\mathbbm{Z}_{q}^{m},B}$ with $B\in\\{B_{L},B_{V},B_{P}\\}$. We refer to
this assumption as “the $\mathrm{QLWE}$ assumption,” leaving the parameters
$n$ and $q$ implicit.

The conditions (A.1) to (A.5) are such that two additional properties hold,
which were already used in [BCM+18]. Informally, the first property is the
possibility to generate near-uniform LWE matrices $\mathbf{A}$ together with a
trapdoor allowing easy inversion; the second property is the existence of a
computationally indistinguishable lossy mode. More formally, we make use of
the following.

######  Theorem 3.2 (Theorem 5.1 in [MP11]).

Let $n,m\geq 1$ and $q\geq 2$ be such that $m=\Omega(n\log q)$. There is an
efficient randomized algorithm $\textsc{GenTrap}(1^{n},1^{m},q)$ that returns
a matrix $\mathbf{A}\in\mathbbm{Z}_{q}^{m\times n}$ and a trapdoor
$t_{\mathbf{A}}$ such that the distribution of $\mathbf{A}$ is negligibly (in
$n$) close to the uniform distribution. Moreover, there is an efficient
algorithm Invert that, on input $\mathbf{A},t_{\mathbf{A}}$ and
$\mathbf{A}\mathbf{s}+\mathbf{e}$ where $\|\mathbf{e}\|\leq
q/(C_{T}\sqrt{n\log q})$ and $C_{T}$ is a universal constant, returns
$\mathbf{s}$ and $\mathbf{e}$ with overwhelming probability over
$(\mathbf{A},t_{\mathbf{A}})\leftarrow\textsc{GenTrap}(1^{n},1^{m},q)$.

######  Definition 3.3.

Let $\chi=\chi(\lambda)$ be an efficiently sampleable distribution over
$\mathbbm{Z}_{q}$. Define a lossy sampler
$\tilde{\mathbf{A}}\leftarrow\textsc{lossy}(1^{n},1^{m},1^{\ell},q,\chi)$ by
$\tilde{\mathbf{A}}=\mathbf{B}\mathbf{C}+\mathbf{F}$, where
$\mathbf{B}\leftarrow_{U}\mathbbm{Z}_{q}^{m\times\ell}$,
$\mathbf{C}\leftarrow_{U}\mathbbm{Z}_{q}^{\ell\times n}$,
$\mathbf{F}\leftarrow\chi^{m\times n}$.

######  Theorem 3.4 (Lemma 3.2 in [AKPW13]).

Under the $\mathrm{QLWE}$ assumption, the distribution of a random
$\tilde{\mathbf{A}}\leftarrow\textsc{lossy}(1^{n},1^{m},1^{\ell},q,\chi)$ is
computationally indistinguishable from
$\mathbf{A}\leftarrow_{U}\mathbbm{Z}_{q}^{m\times n}$.

##  4 Analysis

Most of this section focuses on analyzing Protocol 2.2.We begin by describing
how to model a general prover; this characterization will be equivalent for
all three protocols (Protocols 2.1, 2.2, 2.3). We then analyze Protocol 2.2:
we first restate the protocol, then show its completeness and finally
soundness: for any computationally bounded prover that succeeds with large
enough constant probability in the protocol, the distribution of $(b,x)$
obtained from a generation round contains a large amount of (smooth)
conditional min-entropy (see Theorem 4.6). Finally, in Section 4.3 we explain
how the analysis of Protocol 2.2 extends to Protocol 2.3.

###  4.1 Prover Behavior

We begin by introducing a unified manner to refer to a prover’s actions,
whether the prover interacts with a verifier that executes Protocol 2.1,
Protocol 2.2 or Protocol 2.3. All protocols have the following structure.

######  Protocol 4.1.

Protocol template

  1. 1.

The verifier sends a pair $(\mathbf{A},\mathbf{u})\in\mathbbm{Z}_{q}^{m\times
n}\times\mathbbm{Z}_{q}^{m}$ to the prover. (All parties are assumed to have
agreed on integers $\lambda,m,n$ and $q$.)

  2. 2.

The prover reports a $\mathbf{y}\in\mathbbm{Z}_{q}^{m}$ to the verifier.

  3. 3.

The verifier chooses a challenge $C\leftarrow_{U}\\{G,T\\}$ and sends $C$ to
the prover.

    1. (a)

(Case $C=G$, “Generation round”:) The prover returns a bit $b$ and an
$\mathbf{x}\in\mathbbm{Z}_{q}^{n}$.

    2. (b)

(Case $C=T$, “Test round”:) The prover returns a bit $c$ and a string
$d\in\\{0,1\\}^{n\lceil\log q\rceil}$.

Any prover in a protocol that has the same message structure as Protocol 4.1
can be modeled as follows. The Hilbert space associated with the prover has
four registers. The first register contains $m\lceil\log q\rceil$ qubits that
will hold the provers’ first answer $\mathbf{y}$. The second register contains
the first component of the prover’s second answer and consists of a single
qubit. The third register contains the second component of the prover’s second
answer and consists of $n\lceil\log q\rceil$ qubits. Finally, the fourth
register contains the workspace of the prover (which is also used to store
messages received from the verifier).

Upon reception of the first message $(\mathbf{A},\mathbf{u})$ the prover may
perform an arbitrary unitary $U^{\prime}$ on all registers (including the
private register, which is assumed to contain a copy of
$(\mathbf{A},\mathbf{u})$) followed by a measurement of the first register in
the standard basis to obtain its first response $\mathbf{y}$. Upon reception
of $C\in\\{G,T\\}$ the prover applies an arbitrary unitary $U^{\prime}_{C}$ on
their entire space, measures the second and third registers (collectively
referred to as the _preimage register_) and return the outcome obtained.

In all protocols considered the honest behavior expected from the prover is
the same, and is identical to the honest behavior in Protocol 2.1 from
[BCM+18]. For clarity we do not reproduce all details here; informally, at the
first step the prover is expected to prepare a uniform superposition over
$(b,\mathbf{x})\in\\{0,1\\}\times\mathbbm{Z}_{q}^{n}$ and evaluate the
function

$f_{\mathbf{A},\mathbf{u}}:\;(b,\mathbf{x})\,\mapsto\,{\mathbf{A}}\mathbf{x}+b\,\mathbf{u}+\mathbf{e}$

in superposition, where $\mathbf{e}\leftarrow D_{\mathbbm{Z}_{q}^{m},B_{P}}$.
(The error vector $\mathbf{e}$ also needs to be computed in superposition; we
refer to [BCM+18, Section 5.3] for a detailed description of how this is
performed.) The prover then measures the output register to obtain
$\mathbf{y}\in\mathbbm{Z}_{q}^{m}$. At the second step the prover is expected
to measure the preimage register either in the computational basis (case
$C=G$) or the Hadamard basis (case $C=T$) and report the outcome. Let
$\hat{U},\hat{U}_{G}=\mathbbm{1}$ and $\hat{U}_{T}=H^{\otimes(1+n\lceil\log
q\rceil)}$ be the three unitaries associated with the honest prover behaviour.

######  Definition 4.2.

Suppose given a prover $\mathds{P}$ for Protocol 4.1 whose three unitaries are
$(U^{\prime},U^{\prime}_{G},U^{\prime}_{T})$. Let
$U_{0}=\hat{U}^{\dagger}U^{\prime}U^{\prime}_{G}$ and
$U=\hat{U}_{G}^{\dagger}(U^{\prime}_{G})^{\dagger}U^{\prime}_{T}$. We say that
the prover $\mathds{P}$ is _characterized by_ $(U_{0},U)$.

The definition is justified as follows. For any prover using unitaries
$(U^{\prime},U^{\prime}_{G},U^{\prime}_{T})$ we may always assume that
$U^{\prime}_{G}$ and $U^{\prime}_{T}$ both commute with a standard basis
measurement of the prover’s first register, because they are only applied
after a measurement of it. Therefore, the prover is equivalently represented
by the triple
$(\hat{U}\hat{U}^{\dagger}U^{\prime}U^{\prime}_{G},\mathbbm{1},\hat{U}_{G}^{\dagger}(U^{\prime}_{G})^{\dagger}U^{\prime}_{T})$.
It is thus without loss of generality that we restrict our attention to
provers characterized by a pair $(U_{0},U)$, where $U_{0}$ represents the
prover’s “deviation” from the honest prover in the first round, and $U$ its
deviation in the second round, for the case $C=T$.

###  4.2 Analysis of Quantum Verifier Lossy Randomness Protocol (Protocol 2.2)

In this section we analyze Protocol 2.2. For clarity we describe the protocol
by filling in the verifier’s actions in the template Protocol 4.1. First we
need the following sub-protocol. This protocol describes an interaction
between a quantum verifier and a quantum prover whose space has the same
structure as considered in the other protocols, i.e. it consists of four
registers, the second and third of which are collectively referred to as the
“preimage register”. In the protocol, the verifier is assumed to possess some
$s\in\\{0,1\\}^{n}$.

######  Protocol 4.3.

Quantum Verifier Preimage Extraction Protocol

  1. 1.

The prover sends their (quantum) preimage register to the verifier.

  2. 2.

The verifier appends an auxiliary register of $n\lceil\log q\rceil$ qubits.

  3. 3.

The verifier coherently copies (in the standard basis) the contents of the
second preimage register to the auxiliary register.

  4. 4.

Conditioned on the first preimage register being in state $\left|1\right>$ the
verifier adds $s$ to the contents of the auxiliary register. (This is done
coherently–if the first register is in state $\left|0\right>$ then no action
is performed.)

  5. 5.

The verifier measure the auxiliary register and stores the result. They return
the preimage register to the prover.

We now restate the quantum verifier lossy randomness protocol.

Protocol 2.2: Quantum Verifier Lossy Randomness Protocol

  1. 1.

Let $\ell,n,m,q$ be functions of $\lambda$ satisfying the conditions
(A.1)–(A.5). Let $\chi$ be the distribution $D_{\mathbbm{Z}_{q}^{m},B_{V}}$.
The verifier samples $s\leftarrow_{U}\\{0,1\\}^{n}$,
$\tilde{\mathbf{A}}\leftarrow\textsc{lossy}(1^{n},1^{m},1^{\ell},q,D_{\mathbbm{Z}_{q}^{m},B_{L}})$
and $\mathbf{e}\leftarrow\chi$. The verifier computes
$\mathbf{u}=\tilde{\mathbf{A}}s+\mathbf{e}$. They send
$(\tilde{\mathbf{A}},\mathbf{u})$ to the prover.

  2. 2.

The prover reports a $\mathbf{y}\in\mathbbm{Z}_{q}^{m}$ to the verifier.

  3. 3.

The verifier chooses to either run a generation round or a test round, with
equal probability $1/2$ each.

    1. (a)

Generation round: The verifier sends $C=G$ to the prover and receives
$(b,\mathbf{x})$ from them. They check that
$\lVert\mathbf{y}-\tilde{\mathbf{A}}\mathbf{x}-b\,\mathbf{u}\rVert$ is at most
$B_{P}\sqrt{m}$ and abort if not.

    2. (b)

Test round: The verifier uses the preimage extraction protocol (Protocol 4.3)
to compute $\mathbf{x}_{0}$ from $\mathbf{y}$. The verifier then sends $C=T$
to the prover and receives $(c,d)$ from them. The verifier checks that $d\neq
0$ and $c=d\cdot(J(\mathbf{x}_{0})\oplus J(\mathbf{x}_{0}-s))$, where $J$ is
the binary representation function, which is applied coordinate-wise.

We note that in step 3(b) the prover is expected to return their preimage
register exactly in the state that they are in after measurement of
$\mathbf{y}$, and as they would be directly measured in the standard basis in
case $C=G$ (see Section 4.1). One could call such provers “semi-honest” since
at that step of the protocol they perform the “honest” action. Recall that
Protocol 2.2 is a hypothetical protocol used for analysis purposes only, and
in Section 4.3 we will see that it is sufficient for us to analyze such “semi-
honest” provers in the protocol.

####  4.2.1 Completeness

We begin with proving completeness of Protocol 2.2. To model the randomness
generated in a run of the protocol we let $(\tilde{A},U,Y,C,B,X)$ be random
variables associated with a transcript of the protocol in the obvious way.
Specifically,

  * •

$(\tilde{A},U,Y)$ are distributed as
$(\tilde{\mathbf{A}},\mathbf{u},\mathbf{y})$ in the first round of Protocol
2.2.

  * •

$C\in\\{G,T\\}$ is chosen uniformly at random.

  * •

If $C=G$ (resp. $C=T$) then $(B,X)$ is distributed as the prover’s answer in a
generation round (resp. test round), conditioned on that type of round having
been chosen by the verifier.

We refer to $(\tilde{A},U,Y,C,B,X)$ as a _random transcript_ of the protocol.

######  Lemma 4.4.

For any setting of parameters satisfying the assumptions (A.1) to (A.5), there
is a prover whose running time is polynomial in $\lambda$ such that the prover
is accepted with probability negligibly close to $1$ in Protocol 2.2.
Furthermore, there is a negligible function
$\varepsilon=\operatorname{negl}(\lambda)$ such that letting
$(\tilde{A},U,Y,C,B,X)$ denote a random transcript of the protocol, it holds
that $H^{\varepsilon}_{\infty}(BX|\tilde{A}UY,C=G)\geq n-\ell\log q-O(1)$.

The following claim will be useful in showing the lemma (it is stronger than
necessary, but is stated in this manner since it will also be used in the
soundness proof):

######  Claim 4.5.

Let $\mathbf{u}\in\mathbbm{Z}_{q}^{n}$. For
$\tilde{\mathbf{A}}\in\mathbbm{Z}_{q}^{m\times n}$ let
$\mathcal{X}_{\tilde{\mathbf{A}}}=\\{\mathbf{x}\in\mathbbm{Z}_{q}^{n}:\,\|\tilde{\mathbf{A}}\mathbf{x}-\mathbf{u}\|\leq
B_{P}\sqrt{m}\\}$. Then

$\displaystyle\Pr_{\tilde{\mathbf{A}}\leftarrow\textsc{lossy}(1^{n},1^{m},1^{\ell},q,D_{\mathbbm{Z}_{q}^{m},B_{V}})}\Big{(}\big{|}\mathcal{X}_{\tilde{\mathbf{A}}}\cap\mathbb{Z}_{2}^{n}\big{|}\,\leq\,\frac{2^{n}-1}{2q^{\ell}}\Big{)}\,=\,\operatorname{negl}(\lambda)\;.$
(4)

###### Proof.

Fix $\mathbf{u}\in\mathbbm{Z}_{q}^{n}$. Recall from Definition 3.3 that
$\tilde{\mathbf{A}}$ can be written as
$\tilde{\mathbf{A}}=\mathbf{B}\mathbf{C}+\mathbf{E}$, for
$\mathbf{C}\in\mathbbm{Z}_{q}^{\ell\times n}$. Since $\mathbf{C}$ is selected
uniformly at random, the probability that a fixed nonzero binary string maps
to $\mathbf{u}$ is exactly $\frac{1}{q^{\ell}}$. For $s\in\\{0,1\\}^{n}$ let
$X_{s}$ be the indicator that $\mathbf{C}s=\mathbf{u}$, so for $s\neq 0^{n}$,
$\textsc{E}[X_{s}]=q^{-\ell}$. By linearity of expectation

$\textsc{E}_{\tilde{\mathbf{A}}}\big{[}|\mathcal{X}_{\tilde{\mathbf{A}}}\cap\mathbb{Z}_{2}^{n}|\big{]}\,=\,\sum_{s}\textsc{E}_{\tilde{\mathbf{A}}}\,[X_{s}]\,=\,\frac{2^{n}-1}{q^{\ell}}\;.$

Observe that $\\{X_{s}\\}_{s\in\\{0,1\\}^{n}}$ are pairwise independent,
because two binary strings $s\neq s^{\prime}$ are always linearly independent
in $\mathbbm{Z}_{q}^{n}$. By applying Chebyshev’s inequality we obtain

$\displaystyle\Pr_{\tilde{\mathbf{A}}}\Big{(}\big{|}\mathcal{X}_{\tilde{\mathbf{A}}}\cap\mathbb{Z}_{2}^{n}\big{|}\,\leq\,\frac{2^{n}-1}{2q^{\ell}}\Big{)}\,\leq\,\frac{4q^{\ell}}{2^{n}-1}\;.$
(5)

This probability is negligible as long as $n$ is sufficiently larger than
$\ell\log q$, which is guaranteed by assumption (A.1). ∎

We now prove Lemma 4.4.

###### Proof of Lemma 4.4.

We use exactly the same prover as the one described in [BCM+18, Section 5.3].
For a generation round, the honest prover’s state immediately after reporting
$\mathbf{y}$ in step 3 of Protocol 2.2 is within negligible trace distance of
the state

$|\psi\rangle\,=\,\sum_{b\in\\{0,1\\}}\sum_{\mathbf{x}_{b}\in\mathcal{X}_{\tilde{\mathbf{A}},b,\mathbf{y}}}\;\frac{1}{\sqrt{2|\mathcal{X}_{\tilde{\mathbf{A}},b,\mathbf{y}}|}}\left|b\right>\left|\mathbf{x}_{b}\right>\;,$

where $\mathcal{X}_{\tilde{\mathbf{A}},b,\mathbf{y}}$ denotes the set of valid
preimages of $\mathbf{y}$ under $\tilde{\mathbf{A}}$, i.e. the set of all
$\mathbf{x}_{b,y}\in\mathbb{Z}_{q}^{n}$ such that
$\|\mathbf{y}-\tilde{\mathbf{A}}\mathbf{x}_{b,\mathbf{y}}-b\,\mathbf{u}\|\leq
B_{P}\sqrt{m}$. This is because by definition the honest prover computes
$\mathbf{y}$ as
$\mathbf{y}=\tilde{\mathbf{A}}\mathbf{x}+b\,\mathbf{u}+\mathbf{e}$ for some
vector $\mathbf{e}$ such that $\|\mathbf{e}\|\leq B_{P}\sqrt{m}$ (see Section
4.1). Using Claim 4.5, with high probability over the choice of
$\tilde{\mathbf{A}}$ it holds that
$|\mathcal{X}_{\tilde{\mathbf{A}},b,\mathbf{y}}|\geq 2^{n}/(2q^{\ell})$. Once
the preimage extraction protocol is applied in step 3(b) of Protocol 2.2, the
fact that the prover passes the test round with probability negligibly close
to $1$ follows from the analysis of the honest strategy in [BCM+18]. ∎

####  4.2.2 Soundness

We will show that for any prover in Protocol 2.2, as long as the prover
succeeds with probability sufficiently high then the output distribution on
pairs $(b,\mathbf{x})$ obtained in a generation round of Protocol 2.2 has high
(smooth) min-entropy, even conditioned on all the information exchanged in the
first round of the protocol, i.e. $(\tilde{\mathbf{A}},\mathbf{u})$ and
$\mathbf{y}$.

######  Theorem 4.6.

Consider a quantum polynomial-time prover $\mathds{P}$ in Protocol 2.2 who
passes the generation round with probability negligibly close to $1$ and the
test round with probability $\frac{1}{2}+p_{T}$, for some
$0<p_{T}\leq\frac{1}{2}$, and make the $\mathrm{QLWE}$ assumption. Let
$(\tilde{A},U,Y,C,B,X)$ be a random transcript for an execution of the
protocol. Then

$H_{\infty}^{\varepsilon}(BX|\tilde{A}UY,C=G)\,\geq\,n-\ell\log q-O(1)\;,$ (6)

where $\varepsilon=2(1-4p_{T}^{2})^{1/4}+\operatorname{negl}(\lambda)$.

We note that the assumption that the prover succeeds in the generation round
perfectly is essentially without loss of generality; see the proof of Theorem
4.12 in Section 4.3. To prove the theorem we need the following refinement of
Claim 4.5.

######  Claim 4.7.

Let $\mathbf{u}\in\mathbbm{Z}_{q}^{n}$. Then, with all but negligible
probability over the choice of $\tilde{\mathbf{A}}\in\mathbbm{Z}_{q}^{m\times
n}$,

$\displaystyle\Pr_{\tilde{\mathbf{A}}\leftarrow\textsc{lossy}(1^{n},1^{m},1^{\ell},q,D_{\mathbbm{Z}_{q}^{m},B_{V}})}\Big{(}\max_{s\in\mathbbm{Z}_{2}^{n}}\Pr(s|\tilde{\mathbf{A}},\mathbf{u})>\frac{3q^{\ell}}{2^{n}-1}\Big{)}\,=\,\operatorname{negl}(\lambda)\;.$
(7)

Here $\Pr(s|\tilde{\mathbf{A}},\mathbf{u})$ denotes the posterior probability
of $s\in\\{0,1\\}^{n}$ having been sampled by the verifier at step 1 of
Protocol 2.2, conditioned on $(\tilde{\mathbf{A}},\mathbf{u})$ having been
sent to the prover.

###### Proof.

Recall from Definition 3.3 that a lossy matrix $\tilde{\mathbf{A}}$ is equal
to $\mathbf{B}\mathbf{C}+\mathbf{E}$, for $\mathbf{B},\mathbf{C}$ sampled
uniformly from $\mathbbm{Z}_{q}^{m\times n}$ and $\mathbbm{Z}_{q}^{\ell\times
n}$ respectively and $\mathbf{E}\leftarrow D_{\mathbbm{Z}_{q}^{m\times
n},B_{L}}$. From Claim 4.5 we already know that for any given
$\mathbf{u}\in\mathbbm{Z}_{q}^{m}$, with high probability over
$\tilde{\mathbf{A}}$, there are many possible strings $s$ that could have led
to $(\tilde{\mathbf{A}},\mathbf{u})$. However, the posterior probability of
each such $s$ is not identical, because different error vectors may have
slightly different probabilities. To quantify this, define
$D_{\tilde{\mathbf{A}},\mathbf{u}}$ to be the distribution on $\\{0,1\\}^{n}$
with probabilities

$\displaystyle
D_{\tilde{\mathbf{A}},\mathbf{u}}(s)\,=\,\frac{D_{\mathbbm{Z}_{q}^{m},B_{V}}(\mathbf{u}-\tilde{\mathbf{A}}s)}{\sum\limits_{s^{\prime}\in\\{0,1\\}^{n}}D_{\mathbbm{Z}_{q}^{m},B_{V}}(\mathbf{u}-\tilde{\mathbf{A}}s^{\prime})}\;.$
(8)

Let $s_{0}\in\\{0,1\\}^{n}$ be a string which minimizes
$\lVert\mathbf{u}-\tilde{\mathbf{A}}s_{0}\rVert$ (and therefore maximizes
$D_{\tilde{\mathbf{A}},\mathbf{u}}$), and let
$\mathbf{e}_{0}=\mathbf{u}-\tilde{\mathbf{A}}s_{0}$. Consider the set
$S=\\{s\in\\{0,1\\}^{n}|\mathbf{C}s=\mathbf{C}s_{0}\\}$. For $s\in S$,
$\tilde{\mathbf{A}}s=\mathbf{B}\mathbf{C}s+\mathbf{E}s=\tilde{\mathbf{A}}s_{0}+\mathbf{E}(s-s_{0})$,
therefore by (8),

$\displaystyle D_{\tilde{\mathbf{A}},\mathbf{u}}(s)$ $\displaystyle\propto$
$\displaystyle
D_{\mathbbm{Z}_{q}^{m},B_{V}}(\mathbf{E}(s_{0}-s)+\mathbf{e}_{0})\;,$ (9)

from which using (8) it follows that

$\displaystyle D_{\tilde{\mathbf{A}},\mathbf{u}}(s_{0})$ $\displaystyle\leq$
$\displaystyle\frac{D_{\mathbbm{Z}_{q}^{m},B_{V}}(\mathbf{e}_{0})}{\sum\limits_{s\in
S}D_{\mathbbm{Z}_{q}^{m},B_{V}}(\mathbf{E}(s_{0}-s)+\mathbf{e}_{0})}\;.$ (10)

To lower bound the denominator we use the facts that for any binary $s$ and
$\mathbf{E}$ in the support of $D_{\mathbbm{Z}_{q}^{m\times n},B_{L}}$,
$\lVert\mathbf{E}(s_{0}-s)\rVert\leq 2B_{L}\sqrt{nm}$, and
$\lVert\mathbf{e}_{0}\rVert\leq B_{V}\sqrt{m}$. Using the definition of
$D_{\mathbbm{Z}_{q}^{m},B_{V}}$ we get that for all $s\in S$,

$\displaystyle
D_{\mathbbm{Z}_{q}^{m},B_{V}}(\mathbf{E}(s_{0}-s)+\mathbf{e}_{0})$
$\displaystyle\geq$ $\displaystyle
D_{\mathbbm{Z}_{q}^{m},B_{V}}(\mathbf{e}_{0})e^{\frac{-\pi(2\lVert\mathbf{E}(s_{0}-s)\rVert\lVert\mathbf{e}_{0}\rVert)}{B_{V}^{2}}}e^{\frac{-\pi(\lVert\mathbf{E}(s_{0}-s)\rVert^{2})}{B_{V}^{2}}}$
$\displaystyle\geq$ $\displaystyle
D_{\mathbbm{Z}_{q}^{m},B_{V}}(\mathbf{e}_{0})e^{\frac{-\pi(4B_{L}\sqrt{nm}B_{V}\sqrt{m})}{B_{V}^{2}}}e^{\frac{-\pi(4B_{L}^{2}nm)}{B_{V}^{2}}}$
$\displaystyle\geq$ $\displaystyle
D_{\mathbbm{Z}_{q}^{m},B_{V}}(\mathbf{e}_{0})e^{\frac{-8\pi
mnB_{L}}{B_{V}}}\;.$

Inserting this bound in (10),

$\displaystyle D_{\tilde{\mathbf{A}},\mathbf{u}}(s_{0})$ $\displaystyle\leq$
$\displaystyle\frac{D_{\mathbbm{Z}_{q}^{m},B_{V}}(\mathbf{e}_{0})}{|S|D_{\mathbbm{Z}_{q}^{m},B_{V}}(\mathbf{e}_{0})e^{\frac{-8\pi
mnB_{L}}{B_{V}}}}$ $\displaystyle=$ $\displaystyle\frac{1}{|S|}e^{\frac{8\pi
mnB_{L}}{B_{V}}}$

Using that by (A.5) the ratio $B_{L}/B_{V}$ is negligible it follows that
$D_{\tilde{\mathbf{A}},\mathbf{u}}(s_{0})\leq|S|^{-1}(1+\operatorname{negl}(\lambda))$.
The claim follows by applying Claim 4.5 to bound the size of $|S|$.

∎

We now prove Theorem 4.6.

###### Proof of Theorem 4.6.

Fix $(\tilde{\mathbf{A}},\mathbf{u},\mathbf{y})$ obtained in the first round
of an execution of Protocol 2.2 with the prover $\mathds{P}$. Since the prover
is assumed to pass the generation round with probability negligibly close to
$1$, the state of the prover immediately prior to step 4 of the protocol is
within negligible trace distance of a state of the form

$\sum_{b\in\\{0,1\\}}\sum_{\mathbf{x}_{b}\in\mathcal{X}_{\tilde{\mathbf{A}},b,\mathbf{y}}}\;\sqrt{p_{b,\mathbf{x}_{b}}}\left|b\right>\left|\mathbf{x}_{b}\right>\left|\psi_{b,\mathbf{x}_{b}}\right>\;,$
(11)

where for $b\in\\{0,1\\}$, $\mathcal{X}_{\tilde{\mathbf{A}},b,\mathbf{y}}$
denotes the set of valid preimages of $\mathbf{y}$, i.e.

$\mathcal{X}_{\tilde{\mathbf{A}},b,\mathbf{y}}\,=\,\big{\\{}\mathbf{x}_{b,\mathbf{y}}\,|\,\lVert\mathbf{y}-\tilde{A}\mathbf{x}_{b,\mathbf{y}}-b\,\mathbf{u}\rVert\leq
B_{P}\sqrt{m}\big{\\}}\;\,$

and the $\left|\psi_{b,\mathbf{x}_{b}}\right>$ are arbitrary normalized
states. (We leave the dependence of $p_{b,\mathbf{x}_{b}}$ and
$\left|\psi_{b,\mathbf{x}_{b}}\right>$ on $\tilde{\mathbf{A}}$, $\mathbf{u}$
and $\mathbf{y}$ implicit.) We now show the following claim.

######  Claim 4.8.

There exists a negligible function $\mu$ such that on average over the
distribution of $(\tilde{\mathbf{A}},\mathbf{u},\mathbf{y})$,

$\textsc{E}_{(\tilde{\mathbf{A}},\mathbf{u},\mathbf{y})}\Big{[}\sum_{\mathbf{x}_{0}\in\mathcal{X}_{\tilde{\mathbf{A}},0,\mathbf{y}}}\big{|}p_{0,\mathbf{x}_{0}}-p_{1,\mathbf{x}_{0}-s}\big{|}\Big{]}\,\leq\,\sqrt{1-4p_{T}^{2}}+\mu\;,$
(12)

where $s$ is as chosen by the verifier in the first step of the protocol.

###### Proof.

Consider the state of the prover after the preimage extraction protocol that
would be performed in step 3(b) of Protocol 2.2. Let $\mathbf{x}_{0}$ denote
the measurement result of the extraction. Based on (11) and the definition of
the preimage extraction protocol, Protocol 4.3, conditioned on
$\mathbf{x}_{0}$ being obtained the state of the prover has collapsed to

$\frac{1}{\sqrt{p_{0,\mathbf{x}_{0}}+p_{1,\mathbf{x}_{1}}}}\sum_{b\in\\{0,1\\}}\sqrt{p_{b,\mathbf{x}_{b}}}\left|b\right>\left|\mathbf{x}_{b}\right>\left|\psi_{b,\mathbf{x}_{b}}\right>\;,$
(13)

where $\mathbf{x}_{1}=\mathbf{x}_{0}-s$. By assumption the probability (over
all previous outcomes obtained in the protocol) of obtaining a correct
equation using the prover’s measurement is $\frac{1}{2}+p_{T}$. Suppose now
that $(b,\mathbf{x}_{b})$ is measured prior to performing the prover’s
measurement. We will use the following claim.

######  Claim 4.9.

Let $\left|\psi\right>=\alpha\left|0\right>+\beta\left|1\right>$ be normalized
and $H$ Hermitian such that $\|H\|\leq 1$. Then

$|\alpha|^{2}\left<0\right|H\left|0\right>+|\beta|^{2}\left<1\right|H\left|1\right>\,\geq\,\left<\psi\right|H\left|\psi\right>-2|\alpha||\beta|\;.$

###### Proof.

By direct calculation,

$\displaystyle\left<\psi\right|H\left|\psi\right>$
$\displaystyle=|\alpha|^{2}\left<0\right|H\left|0\right>+|\beta|^{2}\left<1\right|H\left|1\right>+2\Re\big{(}\alpha\overline{\beta}\left<0\right|H\left|1\right>\big{)}$
$\displaystyle\leq|\alpha|^{2}\left<0\right|H\left|0\right>+|\beta|^{2}\left<1\right|H\left|1\right>+2|\alpha||\beta|\;.$

∎

Applying Claim 4.9, using $H$ the observable that combines the prover’s
equation measurement with the check that the equation is correct, it follows
that the probability of obtaining a correct equation when $(b,\mathbf{x}_{b})$
is measured prior to performing the provers’ equation measurement (summed over
all possible $(b,\mathbf{x}_{b}$) is at least

$\frac{1}{2}+p_{T}-\textsc{E}_{(\tilde{\mathbf{A}},\mathbf{u},\mathbf{y})}\Big{[}\sum_{\mathbf{x}_{0}\in\mathcal{X}_{\tilde{\mathbf{A}},0,\mathbf{y}}}\sqrt{p_{0,\mathbf{x}_{0}}p_{1,\mathbf{x}_{0}-s}}\Big{]}\;.$
(14)

It must be the case that obtaining a correct equation following a measurement
of $(b,\mathbf{x}_{b})$ occurs with probability at most
$\frac{1}{2}+\mu^{\prime}$, for a negligible function $\mu^{\prime}$. This is
because if the probability is non-negligibly larger than $\frac{1}{2}$, prover
$\mathds{P}$ and the verifier can be turned into an efficient adversary for
the adaptive hardcore bit property shown in [BCM+18, Section 4.4]. Therefore,

$\textsc{E}_{(\tilde{\mathbf{A}},\mathbf{u},\mathbf{y})}\Big{[}\sum_{x_{0}\in\mathcal{X}_{\tilde{\mathbf{A}},0,\mathbf{y}}}\sqrt{p_{0,\mathbf{x}_{0}}p_{1,\mathbf{x}_{0}-s}}\Big{]}\,\geq\,\frac{1}{2}+p_{T}-\Big{(}\frac{1}{2}+\mu^{\prime}\Big{)}\;.$
(15)

Using the Cauchy-Schwarz inequality,

$\displaystyle\sum_{\mathbf{x}_{0}\in\mathcal{X}_{\tilde{\mathbf{A}},0,\mathbf{y}}}\big{|}p_{0,\mathbf{x}_{0}}-p_{1,\mathbf{x}_{0}-s}\big{|}$
$\displaystyle=$
$\displaystyle\sum_{\mathbf{x}_{0}\in\mathcal{X}_{\tilde{\mathbf{A}},0,\mathbf{y}}}\big{|}(\sqrt{p_{0,\mathbf{x}_{0}}}-\sqrt{p_{1,\mathbf{x}_{0}-s}})(\sqrt{p_{0,\mathbf{x}_{0}}}+\sqrt{p_{1,\mathbf{x}_{0}-s}})\big{|}$
(16) $\displaystyle\leq$
$\displaystyle\Big{(}\sum_{\mathbf{x}_{0}\in\mathcal{X}_{\tilde{\mathbf{A}},0,\mathbf{y}}}\big{(}\sqrt{p_{0,\mathbf{x}_{0}}}-\sqrt{p_{1,\mathbf{x}_{0}-s}}\big{)}^{2}\Big{)}^{\frac{1}{2}}\Big{(}\sum_{\mathbf{x}_{0}\in\mathcal{X}_{\tilde{\mathbf{A}},0,\mathbf{y}}}\big{(}\sqrt{p_{0,\mathbf{x}_{0}}}+\sqrt{p_{1,\mathbf{x}_{0}-s}}\big{)}^{2}\Big{)}^{\frac{1}{2}}$
$\displaystyle\leq$
$\displaystyle\Big{(}1-4\Big{(}\sum_{\mathbf{x}_{0}\in\mathcal{X}_{\tilde{\mathbf{A}},0,\mathbf{y}}}\sqrt{p_{0,\mathbf{x}_{0}}p_{1,\mathbf{x}_{0}-s}}\Big{)}^{2}\Big{)}^{1/2}$

Combining (15), (16), and using that $x\mapsto\sqrt{1-4x^{2}}$ is concave on
$[0,1/2]$ proves the claim. ∎

Next we take advantage of the fact that the verifier’s sample
$(\tilde{\mathbf{A}},\mathbf{u})$ is lossy to extend (12) to all $s^{\prime}$
which could have resulted in the sample; in other words, all binary
$s^{\prime}$ for which there exists $\mathbf{e}^{\prime}$ (with norm at most
$B_{V}\sqrt{m}$) such that
$\tilde{\mathbf{A}}s^{\prime}+\mathbf{e}^{\prime}=\mathbf{u}$. For any such
$s^{\prime}$, with respect to the first round of the protocol the verifier’s
secret may as well have been $s^{\prime}$ rather than $s$. Since the
$p_{0,\mathbf{x}_{0}}$ defined from the prover’s state at the end of the first
round depend only on $(\tilde{\mathbf{A}},\mathbf{u},\mathbf{y})$ but not
directly on $s$ it follows from Claim 4.8 that there exists a negligible
function $\mu$ such that on average over
$(\tilde{\mathbf{A}},\mathbf{u},\mathbf{y})$,

$\displaystyle\mathrm{E}_{(\tilde{\mathbf{A}},\mathbf{u},\mathbf{y})}\Big{[}\sum_{\mathbf{x}_{0}\in\mathcal{X}_{\tilde{\mathbf{A}},\mathbf{0},\mathbf{y}}}\left|{p_{0,\mathbf{x}_{0}}-\mathrm{E}_{s^{\prime}}[p_{1,\mathbf{x}_{0}-s^{\prime}}]}\right|\Big{]}$
$\displaystyle\leq\mathrm{E}_{(\tilde{\mathbf{A}},\mathbf{u},\mathbf{y})}\Big{[}\mathrm{E}_{s^{\prime}}\Big{[}\sum_{\mathbf{x}_{0,\mathbf{y}}\in\mathcal{X}_{\tilde{\mathbf{A}},0,\mathbf{y}}}\left|{p_{0,\mathbf{x}_{0,\mathbf{y}}}-p_{1,\mathbf{x}_{0,\mathbf{y}}-s^{\prime}}}\right|\Big{]}\Big{]}$
$\displaystyle=\mathrm{E}_{s^{\prime}}\Big{[}\mathrm{E}_{(\tilde{\mathbf{A}},\mathbf{u},\mathbf{y})}\Big{[}\sum_{\mathbf{x}_{0,\mathbf{y}}\in\mathcal{X}_{\tilde{\mathbf{A}},0,\mathbf{y}}}\left|{p_{0,\mathbf{x}_{0,\mathbf{y}}}-p_{1,\mathbf{x}_{0,\mathbf{y}}-s^{\prime}}}\right|\Big{]}\Big{]}$
$\displaystyle\leq\sqrt{1-4p_{T}^{2}}+\mu\;,$ (17)

where here in the first line the expectation on $s^{\prime}$ is taken under
the marginal distribution, conditioned on $(\tilde{\mathbf{A}},\mathbf{u})$,
and in the second line it is uniform over $\\{0,1\\}^{n}$. The first
inequality is Jensen’s inequality. Using Claim 4.7 it follows that except with
negligible probability over the choice of $\tilde{\mathbf{A}}$ and
$\mathbf{u}$,

$\mathrm{E}_{s^{\prime}}\big{[}p_{1,\mathbf{x}_{0,\mathbf{y}}-s^{\prime}}\big{]}\,\leq\,\frac{3q^{\ell}}{2^{n}-1}\;.$
(18)

Combining (17) and (18), by Markov’s inequality with probability at least
$(1-4p_{T}^{2})^{1/4}$ over the choice of
$(\tilde{\mathbf{A}},\mathbf{u},\mathbf{y})$ it holds that the distribution of
$(b,\mathbf{x}_{b})$ obtained in the generation round, conditioned on $b=0$,
is within statistical distance $(1-4p_{T}^{2})^{1/4}+\mu^{\prime}$ of a
distribution with entropy at least $n-\ell\log q-O(1)$. The same reasoning
applies to the distribution over preimages conditioned on $b=1$. This
concludes the proof. ∎

###  4.3 Analysis of Lossy Randomness Protocol (Protocol 2.3)

In this section we describe how Theorem 4.6, which applies to Protocol 2.2,
can be extended to guarantee randomness generation for Protocol 2.3. For
convenience we first restate Protocol 2.3 in the same format as Protocol 2.2,
by filling in the verifier’s actions in the template Protocol 4.1.

Protocol 2.3: Lossy Randomness Protocol

  1. 1.

Let $\ell,n,m,q$ be functions of $\lambda$ satisfying the conditions
(A.1)–(A.5). Let $\chi$ be the distribution $D_{\mathbbm{Z}_{q}^{m},B_{V}}$.
The verifier chooses $C\in\\{G,T\\}$ uniformly at random.

    1. (a)

If $C=G$ the verifier samples $s\leftarrow_{U}\\{0,1\\}^{n}$,
$\tilde{\mathbf{A}}\leftarrow\textsc{lossy}(1^{n},1^{m},1^{\ell},q,D_{\mathbbm{Z}_{q}^{m},B_{L}})$
and $\mathbf{e}\leftarrow\chi$. The verifier computes
$\mathbf{u}=\tilde{\mathbf{A}}s+\mathbf{e}$. They send
$(\tilde{\mathbf{A}},\mathbf{u})$ to the prover.

    2. (b)

If $C=T$ the verifier samples $s\leftarrow_{U}\\{0,1\\}^{n}$,
$({\mathbf{A}},t_{\mathbf{A}})\leftarrow\textsc{GenTrap}(1^{n},1^{m},q)$ and
$\mathbf{e}\leftarrow\chi$. The verifier computes
$\mathbf{u}={\mathbf{A}}s+\mathbf{e}$. They send $({\mathbf{A}},\mathbf{u})$
to the prover.

  2. 2.

The prover reports a $\mathbf{y}\in\mathbbm{Z}_{q}^{m}$ to the verifier.

  3. 3.

The verifier runs either a generation round (in case $C=G$) or a test round
(in case $C=T$).

    1. (a)

Generation round: The verifier sends $C$ to the prover and receives
$(b,\mathbf{x})$ from them. They check that
$\lVert\mathbf{y}-\tilde{\mathbf{A}}\mathbf{x}-b\,\mathbf{u}\rVert$ is at most
$B_{P}\sqrt{m}$ and abort if not.

    2. (b)

Test round: The verifier sends $C$ to the prover and receives $(c,d)$ from
them. They use the trapdoor $t_{\mathbf{A}}$ to compute
$\mathbf{x}_{0}\leftarrow\textsc{Invert}(\mathbf{A},t_{\mathbf{A}},\mathbf{y})$,
where Invert is the algorithm from Theorem 3.2. They check that $d\neq 0$ and
$c=d\cdot(J(\mathbf{x}_{0})\oplus J(\mathbf{x}_{0}-s))$, where $J$ is the
binary representation function, and abort if either condition is not
satisfied.

We start with two preliminary claims that allow us to relate the success
probability of a prover in the generation or test rounds of any of the three
protocols 2.1, 2.2, and 2.3).

######  Claim 4.10.

Consider a prover who passes the generation round of either one of the three
protocols (Protocols 2.1, 2.2, 2.3) with probability $p_{G}$. Such a prover
passes the generation rounds of all three protocols with probability
negligibly close to $p_{G}$.

###### Proof.

All provers must have the same probability of passing the generation rounds of
protocols 2.2 and 2.3, since they are identical. If this probability differed
from the probability of passing the generation round of protocol 2.1, the
prover could be used as an efficient means of distinguishing between
$\tilde{\mathbf{A}}\leftarrow\textsc{lossy}(1^{n},1^{m},1^{\ell},q,D_{\mathbbm{Z}_{q}^{m},B_{L}})$
and ${\mathbf{A}}\leftarrow\textsc{GenTrap}(1^{n},1^{m},q)$, since given
$\tilde{\mathbf{A}}$ or $\mathbf{A}$ estimating the prover’s acceptance
probability in a generation round can be done efficiently. However, by Theorem
3.2 the distribution of $\mathbf{A}$ is statistically close to uniform,
whereas by Theorem 3.4 the distribution of $\tilde{\mathbf{A}}$ is
computationally indistinguishable from uniform. ∎

######  Claim 4.11.

Consider a prover who passes the generation rounds of any one of the three
protocols (Protocols 2.1, 2.2, 2.3) with probability negligibly close to $1$.
For such a prover, the probabilities of passing the test rounds of each of the
three protocols is negligibly close.

###### Proof.

From Claim 4.10, such a prover must pass the generation rounds of all three
protocols with all but negligible probability. If we can show that computing
the probability of passing the test rounds of each of the three protocols does
not require a trapdoor (and is therefore efficient), then the proof is
complete, as otherwise, similarly to the proof of Claim 4.10 differing
probabilities in the test rounds would serve as a means of efficiently
distinguishing between lossy $\tilde{\mathbf{A}}$ and uniform $\mathbf{A}$.

Computing the probability of passing the test round of Protocol 2.2 does not
require the trapdoor, due to the quantum verifier extraction protocol
(Protocol 4.3). We can make the same claim for Protocols 2.1 and 2.3 by
replacing the trapdoor usage in step 3(b) with the quantum verifier extraction
protocol. This change will not affect the prover’s probability of succeeding
in the test round because for provers who pass the generation round with
probability negligibly close to $1$ this replacement does not change the
probability of acceptance in the test round except by a negligible amount. ∎

We can now conclude by stating the completeness and soundness properties of
Protocol 2.3. First we note that the same completeness statement as for
Protocol 2.2 in Lemma 4.4 remains valid for Protocol 2.3, with the same
parameters; moreover, the behavior of the honest prover is exactly the same.
For soundness, using the preceding claims we can show the following by
reduction to Theorem 4.6.

######  Theorem 4.12.

Consider a quantum polynomial-time prover $\mathds{P}$ in Protocol 2.3 who
passes the generation round with probability $p_{G}$ and the test round with
probability $\frac{1}{2}+p_{T}$, for some $0<p_{G}\leq 1$ and $0\leq
p_{T}\leq\frac{1}{2}$ such that
$\delta=\frac{1}{2}-p_{T}+\sqrt{1-p_{G}}\leq\frac{1}{2}$, and make the
$\mathrm{QLWE}$ assumption. Let $(\tilde{A},U,Y,C,B,X)$ be a random transcript
for an execution of the protocol. Then

$H_{\infty}^{\varepsilon}(BX|\tilde{A}UY,C=G)\,\geq\,n-\ell\log q-O(1)\;,$

where $\varepsilon=5\delta^{1/4}+\operatorname{negl}(\lambda)$.

###### Proof.

First we observe that given a prover $\mathds{P}$ that passes the generation
(resp. test) round in Protocol 2.3 with probability $p_{G}$ (resp. $p_{T}$),
it is straightforward to construct a prover $\mathds{P}^{\prime}$ that
succeeds in the generation round with probability negligibly close to $1$, and
the test round with probability $\frac{1}{2}+p^{\prime}_{T}$ for some
$p^{\prime}_{T}\geq p_{T}-\sqrt{1-p_{G}}-\operatorname{negl}(\lambda)$. This
follows from [Mah18, Lemma 7.2] and only uses that checking acceptance in the
generation round is efficient. Moreover, the entire quantum state of
$\mathds{P}$ and $\mathds{P}^{\prime}$ after having reported $\mathbf{y}$ in
the first round are within trace distance
$\sqrt{1-p_{G}}+\operatorname{negl}(\lambda)$, and the provers’ actions are
identical from there on.

Applying Claim 4.11, we deduce that $\mathds{P}^{\prime}$ passes the test
round of Protocol 2.2 with probability negligibly close to
$\frac{1}{2}+p^{\prime}_{T}$. This allows us to apply Theorem 4.6 and conclude
that, when $\mathds{P}^{\prime}$ is used in an execution of Protocol 2.2, the
transcript $(\tilde{A},U,Y,C,B,X)$ of the protocol satisfies (6). Using that
the distribution of outcomes generated by $\mathds{P}^{\prime}$ and
$\mathds{P}$ are within statistical distance
$\sqrt{1-p_{G}}+\operatorname{negl}(\lambda)$, the theorem follows. ∎

## References

  * [ACGH20] Gorjan Alagic, Andrew M Childs, Alex B Grilo, and Shih-Han Hung.  Non-interactive classical verification of quantum computation.  In Theory of Cryptography Conference, pages 153–180. Springer, 2020\.
  * [AKPW13] Joel Alwen, Stephan Krenn, Krzysztof Pietrzak, and Daniel Wichs.  Learning with rounding, revisited: New reduction, properties and applications.  Cryptology ePrint Archive, Report 2013/098, 2013.  https://eprint.iacr.org/2013/098.
  * [BCM+18] Zvika Brakerski, Paul Christiano, Urmila Mahadev, Umesh Vazirani, and Thomas Vidick.  Certifiable randomness from a single quantum device.  In Proceedings of the 2018 IEEE 59th Annual Symposium on Foundations of Computer Science, FOCS ’18, Washington, DC, USA, 2018. IEEE Computer Society.
  * [BKVV20] Zvika Brakerski, Venkata Koppula, Umesh Vazirani, and Thomas Vidick.  Simpler proofs of quantumness.  arXiv preprint arXiv:2005.04826, 2020.
  * [CCY20] Nai-Hui Chia, Kai-Min Chung, and Takashi Yamakawa.  Classical verification of quantum computations with efficient verifier.  In Theory of Cryptography Conference, pages 181–206. Springer, 2020\.
  * [FWZ22] Honghao Fu, Daochen Wang, and Qi Zhao.  Computational self-testing of multi-qubit states and measurements.  arXiv preprint arXiv:2201.13430, 2022.
  * [GKPV10] Shafi Goldwasser, Yael Tauman Kalai, Chris Peikert, and Vinod Vaikuntanathan.  Robustness of the learning with errors assumption.  2010\.
  * [GMP22] Alexandru Gheorghiu, Tony Metger, and Alexander Poremba.  Quantum cryptography with classical communication: parallel remote state preparation for copy-protection, verification, and more.  arXiv preprint arXiv:2201.13445, 2022.
  * [HG21] Shuichi Hirahara and François Le Gall.  Test of quantumness with small-depth quantum circuits.  arXiv preprint arXiv:2105.05500, 2021.
  * [Mah18] Urmila Mahadev.  Classical verification of quantum computations.  In Proceedings of the 2018 IEEE 59th Annual Symposium on Foundations of Computer Science, FOCS ’18, Washington, DC, USA, 2018. IEEE Computer Society.
  * [Mah20] Urmila Mahadev.  Classical homomorphic encryption for quantum circuits.  SIAM Journal on Computing, pages FOCS18–189, 2020.
  * [MP11] Daniele Micciancio and Chris Peikert.  Trapdoors for lattices: Simpler, tighter, faster, smaller.  Cryptology ePrint Archive, Report 2011/501, 2011.  http://eprint.iacr.org/2011/501.
  * [Rad19] Roy Radian.  Semi-quantum money.  In Proceedings of the 1st ACM Conference on Advances in Financial Technologies, pages 132–146, 2019.