# EFFICIENT IMAGE CATEGORIZATION WITH SPARSE FISHER VECTOR

###### Abstract

In object recognition, Fisher vector (FV) representation is one of the state-
of-art image representations ways at the expense of dense, high dimensional
features and increased computation time. A simplification of FV is attractive,
so we propose Sparse Fisher vector (SFV). By incorporating locality strategy,
we can accelerate the Fisher coding step in image categorization which is
implemented from a collective of local descriptors. Combining with pooling
step, we explore the relationship between coding step and pooling step to give
a theoretical explanation about SFV. Experiments on benchmark datasets have
shown that SFV leads to a speedup of several-fold of magnitude compares with
FV, while maintaining the categorization performance. In addition, we
demonstrate how SFV preserves the consistence in representation of similar
local features.

Index Terms—  Sparse Fisher vector, locality strategy, Generalized Max
Pooling, image categorization

##  1 Introduction

The Fisher vector approach [1, 2, 3, 4, 5, 6] is an extension of the popular
Bag-Of-Words (BOW) model by encoding for codeword the mean and variance of
local descriptors. It consists of two steps (i) encoding step, encoding the
descriptors into dense and high-dimensional features codes; and (ii) pooling
step, pooling the codes into a vector. With several improvements [2, 3],
Fisher vector has been one of the most effective ways for image
categorization.

The success of FV representation is ascribed to its high dimensionality, but
FV representation also suffers high computation cost when compared to BOW
model [3], especially for large-scale image retrieval and object detection.
For specific tasks, several simplified [4, 7, 8] and extended [2, 5, 6, 9]
versions of Fisher coding have emerged. In [4], Jegou et al. proposed the VLAD
representation in which each local descriptor is assigned to the nearest
visual word, then the differences between codewords and corresponding
descriptor are accumulated. In [5], Florent Perronnin et al. compressed the
high-dimensional Fisher vectors through Local Sensitive Hashing. Recently, Dan
Oneata et al. [7] presented approximations to normalizations in Fisher vector.
In [8], authors realized a fast local area independent representation by
representing the picture as sparse integral images. In this paper, we combine
the locality strategy into Fisher vector to reduce the time consumption in
feature coding step.

Locality strategy has been used in Linear Embedding and spectral clustering
i.e. Local Linear Embedding [10] and local spectral clustering [11]. Inspired
by this strategy, many localized coding ways or nearest search algorithms have
emerged in BOW, for example, Locality-constrained Linear Coding (LLC) [12],
Local Soft Coding (LSC) [13], Laplacain Sparse Coding [14], Local Coordinate
Coding [15], local sparse coding [16]. Also this locality-preserving method
has been used in pooling step [17]. This locality will produce an early cut
off effect to remove the unreliable longer distances. Previous work has shown
the effectiveness of preserving configuration space locality during coding, so
that similar inputs lead to similar codes [14]. Also we can view them as a
trick whose computational cost would be prohibitive with standard coding.
Because all the coding coefficients can be regarded as the probability density
to describe the feature which can be represented by histogram or fisher
vector. In this paper, we will introduce the LLC, LSC and SFV from
probabilistic perspective and reveal the relationships between LLC, LSC and
SFV, and this part will be discussed in section 4.

For the pooling step in image categorization, Naila Murray [18] et al. tried
to generalize max pooling (GMP) to Fisher vector by constructing object
function with loss term. Based on this structure, we reformulate the sparse
Fisher vector which is the origin Fisher vector combined with locality
strategy.

A notable previous idea which is similar to our work is proposed in [3] with
”posterior thresholding”. But [3] only regarded this as an accelerating trick,
and failed to provide the detailed theoretical proof and the effectiveness of
the proposed method are not explained. Our paper provides the detailed
explanation of the scheme and implement a experimental evaluation on image
categorization task.

##  2 Generalized max pooling revisit

Fisher vector is essentially the sum pooling of encoded SIFT features. It
should be noted that the sum-pooled representation is more influenced by
frequent descriptors in one image. While max-pooled representation only
considers the greatest response, and therefore immune to this effect, but it
does not apply to aggregation-based encoding such as FV representation. To
alleviate the problem, [18] proposed the generalized max pooling method that
mimics the desirable properties of max pooling. They denote $\phi_{n}$ the
code vector of each feature, and $\phi^{max}$ the GMP vector. GMP demands that
$\phi_{\rm{n}}^{\rm{T}}{\phi^{{\rm{max}}}}={\rm{Const}}$, which indicates that
$\phi^{max}$ is equally similar to frequent and rare features. In the BOF
case, GMP is strictly equivalent to max pooling [18]. GMP can be formalized in
two ways. The first is the primal formulation:

$\phi^{gmp}=\mathop{\arg\min}\limits_{\phi}{\left\|{{\Phi^{T}}\phi-{\textbf{1}_{\rm{N}}}}\right\|^{2}}$
(1)

which directly gives the result of pooling $\phi^{gmp}$, where
$\textbf{1}_{\rm{N}}$ is the N-dimensional vector of all ones. The second is
the dual formulation:

$\alpha_{\lambda}=\mathop{\arg\min}\limits_{\alpha}{\left\|{{\Phi^{T}}\Phi\alpha-{\textbf{1}_{\rm{N}}}}\right\|^{2}}+\lambda{\left\|{\Phi\alpha}\right\|^{2}}\
$ (2)

which gives the weight of each feature. $\phi^{gmp}$ is the result of weighted
sum pooling.

##  3 SPARSE FISHER VECTOR THEORY

Let $X=\\{{x_{1}},....{x_{N}}\\}$ be a set of N local descriptors extracted
from an image. We denote M the number of Gaussian Mixture Model(GMM) clusters,
and D the dimension of SIFT descriptors after using PCA. Clearly. According to
Section 2, the Fisher vector representation $\phi$ should be equally similar
to each Fisher vector code, which is defined as:

${\Phi}^{{T}}\phi={\textbf{1}_{{N}}}\ $ (3)

where $\Phi$ is the code matrix, of which each row represents a Fisher vector
code corresponding to the descriptor $\emph{x}_{n}$.

${\Phi}=\left({\begin{array}[]{*{20}{c}}{{{{G}}_{1}}\left({{{{x}}_{1}}}\right)}&\cdots&{{{{G}}_{{M}}}\left({{{{x}}_{1}}}\right)}\\\
\vdots&\ddots&\vdots\\\
{{{{G}}_{1}}\left({{{{x}}_{{N}}}}\right)}&\cdots&{{{{G}}_{{M}}}\left({{{{x}}_{{N}}}}\right)}\end{array}}\right)$
(4)

where $G_{m}(x_{n})$ is the sub-vector of cluster m of the Fisher vector code
corresponding to ${\emph{x}_{n}}$.

In [1], the normalization of the Fisher information matrix takes a diagonal
form, which assumes the sub-vectors are independent of each other. Therefore
it is natural to divide Eq. 3 into M subtasks. We denote by $\Phi_{m}$ the
m-th column of $\Phi$, which is the code matrix in the $m$-th subtask:

${{{\Phi}}_{{m}}}=\left({\begin{array}[]{*{20}{c}}{{{{G}}_{m}}\left({{{{x}}_{1}}}\right)}\\\
\vdots\\\ {{{{G}}_{m}}\left({{{{x}}_{{N}}}}\right)}\end{array}}\right)$ (5)

And $\Phi=(\Phi_{1}\cdots\Phi_{M})$. If each subtask is fulfilled as follows,
the whole task likes Eq. 3 will be fulfilled as:

$\Phi^{T}_{m}\phi_{m}=\textbf{1}_{{N}}$ (6)

The objective function of the $m$-th subtask in the primal formulation is:

$\phi_{m,gmp}=\arg\min\left\|\Phi^{T}_{m}\phi_{m}-\textbf{1}_{{N}}\right\|+\lambda\left\|\phi_{m}\right\|^{2}_{2}$
(7)

Clearly the primal formulation does not have the sparsifying effect, so we
turn to the dual formulation. According to Section 2, we denote by
$\alpha_{m}$ the code weight so that $\Phi_{m}\alpha_{m}=\phi_{m}$, which
means that $\phi_{m}$ is the pooling result of code matrix $\Phi_{m}$ with
weight $\alpha_{m}$ [17]. $\alpha_{m}$ is consistent with the idea of Sparse
Fisher vector because it can determine whether a Fisher vector code is valid
in the final image representation.

The objective function of the $m$-th task in the dual formulation is:

${{{\alpha}}_{{{m}},{{gmp}}}}={{\arg\min}}\left\|{{{\Phi}}_{{m}}^{{T}}{{{\Phi}}_{{m}}}{{{\alpha}}_{{m}}}-{\textbf{1}_{{N}}}}\right\|_{2}^{2}+{{\lambda}}\left\|{{{\Phi}}{{{\alpha}}_{{m}}}}\right\|_{2}^{2}$
(8)

For convenience, we substitute $K$ for $\Phi^{T}_{m}\Phi_{m}$. The analytical
solution to the dual formulation is:

${{{\alpha}}_{{{m}},{{gmp}}}}={\left({K+{{\lambda
I}}}\right)^{-1}}{\textbf{1}_{{N}}}$ (9)

The analytical solution indicates that we can leverage the individual items of
$\alpha_{m}$ which are the weights of the Fisher vector codes in the $m$-th
subtasks. If the weight is zero, then the corresponding descriptor makes no
contributions in the pooling. In other words, the $m$-th component of the
Fisher Vector code is sparsified, whose idea is like FV sparsity encoding in
[3].

In LLC [12], weighted L2-norm constraint is used to assure that the local
atoms are preserved, which inspires us to use a similar regularity to leverage
the sparsity of $\alpha_{m}$, let $\alpha_{m,{sfv}}$ denote the SFV
representation,

${{{\alpha}}_{{{m}},{{sfv}}}}={{\arg\min}}\left\|{{{K}}{{{\alpha}}_{{m}}}-{\textbf{1}_{{N}}}}\right\|_{2}^{2}+{{\lambda}}\left\|{{{d}}\odot{{{\alpha}}_{{m}}}}\right\|_{2}^{2}$
(10)

where d gives different constraints to the individual items of $\alpha_{m}$.
Specially,

$d_{j}^{m}=\left\\{\begin{array}[]{l}{\kern 1.0pt}{\kern 1.0pt}{\kern
1.0pt}{\kern 1.0pt}{\kern 1.0pt}{\kern 1.0pt}{\kern 1.0pt}1{\kern 1.0pt}{\kern
1.0pt}{\kern 1.0pt}{\kern 1.0pt}{\kern 1.0pt}{\kern 1.0pt}{\kern 1.0pt}{\kern
1.0pt}{\kern 1.0pt}{\kern 1.0pt}{\kern 1.0pt}{\kern 1.0pt}{\kern
1.0pt}if{\kern 1.0pt}{\kern 1.0pt}{\kern 1.0pt}j{\kern 1.0pt}{\kern
1.0pt}{\kern 1.0pt}{\kern 1.0pt}{\kern 1.0pt}\in{\kern 1.0pt}{\kern
1.0pt}{\kern 1.0pt}{\kern 1.0pt}\mathcal{N}_{\emph{k}}^{m}{\kern 1.0pt}\\\
{\kern 1.0pt}{\kern 1.0pt}{\kern 1.0pt}{\kern 1.0pt}{\kern 1.0pt}{\kern
1.0pt}{\kern 1.0pt}\infty{\kern 1.0pt}{\kern 1.0pt}{\kern 1.0pt}{\kern
1.0pt}{\kern 1.0pt}{\kern 1.0pt}{\kern 1.0pt}{\kern
1.0pt}otherwise\end{array}\right.{\kern 1.0pt}{\kern 1.0pt}{\kern 1.0pt}$ (11)

$\mathcal{N}_{\emph{k}}^{m}$ denotes the first k maximum posterior of m-th
cluster. The analytical solution is:

${{{\alpha}}_{{{m}},{{sfv}}}}={\left({K^{T}K+{{\lambda
dia}}{{{g}}^{2}}\left({{d}}\right)}\right)^{-1}}K{\textbf{1}_{{N}}}$ (12)

When $\lambda$ approaches infinity, $K^{T}K$ will be comparatively negligible,
and the solution can be written as:

${{{\alpha}}_{{{m}},{{sfv}}}}={\left({{{\lambda
dia}}{{{g}}^{2}}\left({{d}}\right)}\right)^{-1}}K{\textbf{1}_{{N}}}$ (13)

Eq. 13 sparsifies the items in $\alpha_{m}$ that are heavily constrained by
_d_ , but the weights of the unsparsified descriptors are determined by
$K{\textbf{1}_{{N}}}$, which is time-costly. Therefore, we make a further
simplification. $K$ is the kernel matrix of patch-to-patch similarities.
Clearly $\alpha_{m,sfv}$ only depends on $K$: when a feature shows little
similarity with the other features, the corresponding weight $\alpha$ will be
greater. Because the Fisher vector codes are all normalized, the diagonal
items of $K$ are all ones. If we ignore the non-diagonal items of $K$ which
means that the Fisher vector codes are orthogonal, Eq. 13 goes to:
${{{\alpha}}_{{{m}},{{sfv}}}}={\left({{{\lambda
dia}}{{{g}}^{2}}\left({{d}}\right)}\right)^{-1}}{\textbf{1}_{{N}}}$.

Because $\lambda$ will be eliminated by normalization, the individual item of
$\alpha_{m,sfv}$ can be written as:

${{\alpha}}_{{{m}},{{sfv}}}^{\left({{j}}\right)}=\left\\{{\begin{array}[]{*{20}{c}}{\begin{array}[]{*{20}{c}}1&{{{d}}{{}_{j}^{m}}=1}\end{array}}\\\
{\begin{array}[]{*{20}{c}}0&{d{{}_{j}^{m}}=\infty}\end{array}}\end{array}}\right.$
(14)

where $\alpha_{m,sfv}^{j}$ is the j-th term of $\alpha_{m,sfv}$, and
$\emph{d}{{}_{j}^{m}}$ is the j-th term of $\emph{d}{{}^{m}}$. As
$\Phi_{m}\alpha_{m}$, sparse $\alpha_{m}$ makes $\Phi_{m}$ be sparsified,
i.e., Sparse Fisher vector.

For $\lambda=0$, we have $\alpha_{m,sfv}=\textbf{1}_{{N}}/\lambda$, which
corresponds to the original Fisher vector. Therefore, $\lambda$ does not only
play a role in regularization, but also realize a smooth transition between
the solution to original Fisher vector ($\lambda=0$) and Sparse Fisher vector
($\lambda\rightarrow\infty$).

Table 1: Experiment results on PASCAL VOC 2007 Coding ways | Feature Dims | Accuracy(%) | Time per image(s)
---|---|---|---
FV(M=32) | 4096 | 49.75 | 3.14
FV(M=64) | 8192 | 52.48 | 5.43
FV(M=128) | 16384 | 55.18 | 9.73
FV(M=256) | 32768 | 58.42 | 16.97
SFV(M=32) | 4096 | 49.76 | 1.04
SFV(M=64) | 8192 | 52.49 | 1.81
SFV(M=128) | 16384 | 55.18 | 2.39
SFV(M=256) | 32768 | 58.25 | 3.72
BOW(M=8192) | 8192 | 39.60 | 2.45
FV(M=256)[43] | 32768 | 58.3 | –

##  4 EXPERIMENT EVALUATIONS

To verify the effectiveness of Sparse Fisher vector, we validate the proposed
approach on image category task. Firstly, we describe the image classification
datasets and experimental setup. We experimentally compare the Sparse Fisher
vector against the canonical Fisher vector for two large data sets:
Caltech-101 by Fei-Fei et al. [19] and the Pascal VOC sets of 2007 [20] .

###  4.1 Experimental setup

We compute all SIFT descriptors on overlapping $32\times 32$ pixels patches
with the step size of 4 pixels. We reduce their dimensionality to 64
dimensions with PCA, so as to better fit the diagonal covariance matrix
assumption.

EM algorithm is employed to learn the parameters of the GMM and the cluster
number ranges from 64 to 256. By default, for Fisher vector, we calculate the
gradient with respect to mean and standard deviation. And for the Sparse
Fisher vector we set the neighborhood as $\emph{k}=5$. We streamline the
standard experimental setting and employ linear SVM. It is worth mentioning
that the computing platform in our experiments is Intel Core Duo (4G RAM), so
the results are slightly different with origin paper in computation time. We
use the origin Fisher vector [1, 2] as the baseline and also the Sparse Fisher
vector is improved based on origin Fisher vector.

###  4.2 PASCAL VOC 2007

The Pascal VOC 2007 database contains 9,963 images of 20 classes. We use the
standard protocol which consists in training on the provided trainval set and
testing on the test set and we set the BOW model as the baseline. The
classification results are compared in Table 1, where M denotes the number of
clusters in GMM. We compared three sections in different coding ways,
including feature dimensions, accuracy and coding time per image.

For the same feature dimension, for example 8192, the FV achieves higher
accuracy than BOW. This result shows that the FV is more discriminative than
BOW with the double time cost. But for SFV, when the cluster number of
Gaussian mixture distributions(GMM) is 64, we can obtain a comparable accuracy
with FV but much faster image coding. This result is in accordance with the
conditions of 32, 128 and 256 clusters number.

###  4.3 Caltech-101

Caltech 101 dataset consists of 9144 images of 102 classes like animals,
flower and so on. Following the standard experimental setting, we use 30
images per class for training while leaving the remaining for test. Other
experimental setting agrees with experiment setup above. Classification
results are compared in Table 2.

Table 2: Experiment results on Caltech-101 Coding ways | Accuracy(%) | Time per image(s)
---|---|---
FV(M=32) | 61.00 | 1.46
FV(M=64) | 65.09 | 2.33
FV(M=128) | 67.85 | 4.50
FV(M=256) | 70.79 | 10.69
SFV(M=32) | 61.05 | 0.81
SFV(M=64) | 65.03 | 0.96
SFV(M=128) | 67.82 | 1.30
SFV(M=256) | 70.75 | 1.98

Table 2 shows the similar result as Table 1. Under the same size of codebook,
SFV runs more quickly than FV with a comparable accuracy. And with the
increase in codebook size, the difference of time consuming between these two
coding ways is increasing. For example, when the codebook size is 256, coding
time per image in FV is 10.69 s, while for SFV is 1.98 s which is nearly 5
times as fast as FV.

###  4.4 Experiment analysis

####  4.4.1 Computation cost analysis

To further show the advantage of SFV in computation cost, we demonstrate the
average coding time per image with the size of codebook and analyze the
computation complexity.

(a) PASCAL VOC 2007

(b) Caltech 101

Fig. 1: Comparison between theoretical and empirical results, Black line
indicate the origin FV and the red one indicate the SFV.

Fig.1(a) and Fig. 1(b) show the average coding time per image as a function of
the codebooks size on datasets above. As was the case on both datasets, SFV
consistently outperforms the FV and the computation time difference increase
with the codebooks size.

Considering the D dims of features and M clusters mentioned above, we can
estimate the computation complexity. There are two sub-steps in FV encoding
steps: the first sub-step is calculating the posterior probability and the
second sub-step is calculating the derivation on the GMM. The computation
complexity of the first step is $O[3MD]$ which is same for FV and SFV. The
computaion complexity of the second step is $O[(3+5)MD]$ and $O[(3+5)kD]$
respectively. As $M\gg k$ , so the total time of SFV is much less than FV and
the time difference increases with M which is consist with experiment results.

####  4.4.2 Similarity correspondence between SIFT and Sparse Fisher vector

One implicit contribution of our work is that SFV better preserves similarity.
To demonstrate this, 200 SIFT features from PASCAL VOC 2007 are randomly
selected. We calculate the pair-wise similarity by using cosine measure. The
similarity correspondence is shown in Fig. 2. Fig. 2 indicates an obvious
linear trend of the similarity between SFV against the similarity between SIFT
features, while FV does not. The comparison confirmed that the effectiveness
of preserving configuration space locality during coding, which makes similar
inputs correspond to similar codes [14, 21].

(a) FV

(b) SFV

Fig. 2: Experiment result on Pascal VOC 2007. The similarity correspondence
relationship between the FV(left) or SFV(right) and the SIFT feature. A linear
trend can be found in SFV.

###  4.5 Discussion about SFV

In Fisher vector, local features are described by deviation from a GMM. The
probability representation of a feature by GMM can be represented as:

$\displaystyle p\left({x|\theta}\right)$
$\displaystyle=\sum_{m=1}^{M}\omega_{m}p_{m}\left({x|\theta}\right)$ (15)
$\displaystyle p_{m}\left({x|\theta}\right)$
$\displaystyle=\frac{exp(-\frac{1}{2}(x-\mu_{m})^{T}\Sigma^{-1}_{m}(x-\mu_{m}))}{(2\pi)^{D/2}\left|\Sigma_{m}\right|^{1/2}}$

where $\omega_{m}$ denotes the prior of the codeword and
${p_{m}}\left({x|\theta}\right)$ reflects the probability of feature x belongs
to the m-th cluster. So we can regard the feature coding coefficient as the
probability of a feature belonging to the codebook. We notice that no matter
in LLC [12], or LSC [13], codewords in codebook are independent and there are
no priors on them or we can regard the priors as equal. For LSC, Eq.15 can be
rewritten as:

$\displaystyle p\left({x|B}\right)$
$\displaystyle=\sum\limits_{m=1}^{M}{{p_{m}}\left({x|B}\right)}$ (16)
$\displaystyle p_{m}\left({x|B}\right)$
$\displaystyle=\exp\left({\left\|{x-{b_{m}}}\right\|_{2}^{2}/\sigma}\right)$

Eq.16 can be seen as the probability of input feature x belonging to the m-th
codeword [22], where M  denotes the number of codewords in codebook. So the
object function of LSC can be represented as:

$\displaystyle\max P(x|B)$
$\displaystyle=\sum\limits_{m=1}^{M}{{P_{m}}(x|B)\odot I(m)}$ (17)
$\displaystyle s.t\quad{\left\|I\right\|_{0}}$ $\displaystyle=k$

where I is a binary vector.

Also we need to notice that all dimensions of soft coding [13, 23] are
independent of each other. In Fisher coding, the relations among different
dimensions are represented by GMM. The object function of SFV can be
represented as:

$\displaystyle\max\gamma(m)$
$\displaystyle=P(m|x,\theta)=\frac{{P(m){P_{m}}(x|\theta)}}{{\sum{P(m){P_{m}}(x|\theta)}}}\odot
I(m)$ (18) $\displaystyle s.t\quad{\left\|I\right\|_{0}}$ $\displaystyle=k$

where I  is a binary vector.

So when we execute the localization operation in Eq. 16, we calculate the
codewords which belong to the k-nearest neighborhood of the feature. This can
be regarded as the soft maximum of the likelihood of conditional probability.
This is also true for LLC model. But in SFV, when we execute the early cut off
operation, the prior of the codeword is incorporated. So we calculate the
codewords which belong to the k-nearest neighborhood of the feature as Eq. 15.
This can be regarded as a soft maximum of the posterior probability.

##  5 Conclusion

In this paper, we have introduced a ’localized’ Fisher vector called Sparse
Fisher vector. Based on GMP, we sparsified the Fisher vector code matrix by
adding local regular term. These ways allow efficient image categorization
without undermining its performance on several public datasets and coding
outputs preserve the similarity among input features.

Fisher vector origins from the natural gradient in [24], so Sparse Fisher
vector can be seen as partial gradient descent. Also, from probabilistic
perspective, Sparse Fisher vector can be regarded as a soft maximum of the
posterior probability. Since GMP considers the uniqueness of features and
weight them according to uniqueness, we will combine it in our future work.

##  6 Acknowledgement

This work was supported in part by the National Basic Research Program of
China(2012CB719903).

##  7 REFERENCES

##

  * [1] Florent Perronnin and Christopher R. Dance.  Fisher kernels on visual vocabularies for image categorization.  In 2007 IEEE Computer Society Conference on Computer Vision and Pattern Recognition (CVPR 2007), 18-23 June 2007, Minneapolis, Minnesota, USA, 2007.
  * [2] Florent Perronnin, Jorge Sánchez, and Thomas Mensink.  Improving the fisher kernel for large-scale image classification.  In Computer Vision - ECCV 2010, 11th European Conference on Computer Vision, Heraklion, Crete, Greece, September 5-11, 2010, Proceedings, Part IV, pages 143–156, 2010.
  * [3] Jorge Sánchez, Florent Perronnin, Thomas Mensink, and Jakob J. Verbeek.  Image classification with the fisher vector: Theory and practice.  International Journal of Computer Vision, 105(3):222–245, 2013\.
  * [4] Herve Jegou, Matthijs Douze, Cordelia Schmid, and Patrick Pérez.  Aggregating local descriptors into a compact image representation.  In The Twenty-Third IEEE Conference on Computer Vision and Pattern Recognition, CVPR 2010, San Francisco, CA, USA, 13-18 June 2010, pages 3304–3311, 2010.
  * [5] Florent Perronnin, Yan Liu, Jorge Sánchez, and Herve Poirier.  Large-scale image retrieval with compressed fisher vectors.  In The Twenty-Third IEEE Conference on Computer Vision and Pattern Recognition, CVPR 2010, San Francisco, CA, USA, 13-18 June 2010, pages 3384–3391, 2010.
  * [6] Ramazan Gokberk Cinbis, Jakob J. Verbeek, and Cordelia Schmid.  Segmentation driven object detection with fisher vectors.  In IEEE International Conference on Computer Vision, ICCV 2013, Sydney, Australia, December 1-8, 2013, pages 2968–2975, 2013.
  * [7] Dan Oneata, Jakob J. Verbeek, and Cordelia Schmid.  Efficient action localization with approximately normalized fisher vectors.  In 2014 IEEE Conference on Computer Vision and Pattern Recognition, CVPR 2014, Columbus, OH, USA, June 23-28, 2014, pages 2545–2552, 2014.
  * [8] Koen E. A. van de Sande, Cees G. M. Snoek, and Arnold W. M. Smeulders.  Fisher and VLAD with FLAIR.  In 2014 IEEE Conference on Computer Vision and Pattern Recognition, CVPR 2014, Columbus, OH, USA, June 23-28, 2014, pages 2377–2384, 2014.
  * [9] Jie Lin, Ling-Yu Duan, Tiejun Huang, and Wen Gao.  Robust fisher codes for large scale image retrieval.  In IEEE International Conference on Acoustics, Speech and Signal Processing, ICASSP 2013, Vancouver, BC, Canada, May 26-31, 2013, pages 1513–1517, 2013.
  * [10] Sam T Roweis and Lawrence K Saul.  Nonlinear dimensionality reduction by locally linear embedding.  Science, 290(5500):2323–2326, 2000.
  * [11] Andrew Y. Ng, Michael I. Jordan, and Yair Weiss.  On spectral clustering: Analysis and an algorithm.  In Advances in Neural Information Processing Systems 14 [Neural Information Processing Systems: Natural and Synthetic, NIPS 2001, December 3-8, 2001, Vancouver, British Columbia, Canada], pages 849–856, 2001.
  * [12] Jinjun Wang, Jianchao Yang, Kai Yu, Fengjun Lv, Thomas S. Huang, and Yihong Gong.  Locality-constrained linear coding for image classification.  In The Twenty-Third IEEE Conference on Computer Vision and Pattern Recognition, CVPR 2010, San Francisco, CA, USA, 13-18 June 2010, pages 3360–3367, 2010.
  * [13] Lingqiao Liu, Lei Wang, and Xinwang Liu.  In defense of soft-assignment coding.  In IEEE International Conference on Computer Vision, ICCV 2011, Barcelona, Spain, November 6-13, 2011, pages 2486–2493, 2011.
  * [14] Shenghua Gao, Ivor Wai-Hung Tsang, Liang-Tien Chia, and Peilin Zhao.  Local features are not lonely - laplacian sparse coding for image classification.  In The Twenty-Third IEEE Conference on Computer Vision and Pattern Recognition, CVPR 2010, San Francisco, CA, USA, 13-18 June 2010, pages 3555–3561, 2010.
  * [15] Kai Yu and Tong Zhang.  Improved local coordinate coding using local tangents.  In Proceedings of the 27th International Conference on Machine Learning (ICML-10), June 21-24, 2010, Haifa, Israel, pages 1215–1222, 2010.
  * [16] Jianchao Yang, Kai Yu, and Thomas S. Huang.  Efficient highly over-complete sparse coding using a mixture model.  In Computer Vision - ECCV 2010 - 11th European Conference on Computer Vision, Heraklion, Crete, Greece, September 5-11, 2010, Proceedings, Part V, pages 113–126, 2010.
  * [17] Y-Lan Boureau, Nicolas Le Roux, Francis Bach, Jean Ponce, and Yann LeCun.  Ask the locals: Multi-way local pooling for image recognition.  In IEEE International Conference on Computer Vision, ICCV 2011, Barcelona, Spain, November 6-13, 2011, pages 2651–2658, 2011.
  * [18] Naila Murray and Florent Perronnin.  Generalized max pooling.  pages 2473–2480, 2014.
  * [19] Fei-Fei Li, Robert Fergus, and Pietro Perona.  Learning generative visual models from few training examples: An incremental bayesian approach tested on 101 object categories.  Computer Vision and Image Understanding, 106(1):59–70, 2007.
  * [20] Mark Everingham, Luc J. Van Gool, Christopher K. I. Williams, John M. Winn, and Andrew Zisserman.  The pascal visual object classes (VOC) challenge, 2010.
  * [21] Shenghua Gao, Ivor Wai-Hung Tsang, and Liang-Tien Chia.  Laplacian sparse coding, hypergraph laplacian sparse coding, and applications.  IEEE Trans. Pattern Anal. Mach. Intell., 35(1):92–104, 2013.
  * [22] Yongzhen Huang, Zifeng Wu, Liang Wang, and Tieniu Tan.  Feature coding in image classification: A comprehensive study.  IEEE Trans. Pattern Anal. Mach. Intell., 36(3):493–506, 2014\.
  * [23] Jan van Gemert, Cor J. Veenman, Arnold W. M. Smeulders, and Jan-Mark Geusebroek.  Visual word ambiguity.  IEEE Trans. Pattern Anal. Mach. Intell., 32(7):1271–1283, 2010\.
  * [24] Shun-ichi Amari.  Natural gradient works efficiently in learning.  Neural Computation, 10(2):251–276, 1998.


# Towards A Post-Quantum Cryptography in Blockchain I: Basic Review on
Theoretical Cryptography and Quantum Information Theory

Tatsuru Kikuchi Faculty of Economics, The University of Tokyo,
7-3-1 Hongo, Bunkyo-ku, Tokyo 113-0033 Japan

(())

###### Abstract

Recently, the invention of quantum computers was so revolutionary that they
bring transformative challenges in a variety of fields, especially for the
traditional cryptographic blockchain, and it may become a real thread for most
of the cryptocurrencies in the market. That is, it becomes inevitable to
consider to implement a post-quantum cryptography, which is also referred to
as quantum-resistant cryptography, for attaining quantum resistance in
blockchains.

##  1 Introduction

Recently, the invention of quantum computers was so revolutionary that they
bring transformative challenges in a variety of fields, especially for the
traditional cryptographic blockchain, and it may become a real thread for most
of the cryptocurrencies in the market. That is, it becomes inevitable to
consider to implement a post-quantum cryptography, which is also referred to
as quantum-resistant cryptography, and post-quantum ledger for attaining
quantum resistance in blockchains.

One of the known quantum cryptography is the so-called, quantum key
distribution (QKD). There exists a conceptually huge gap between the quantum
key distribution and the public key cryptography (PKC). The security of key-
encryption in QKD relies based on the mathematical foundation of quantum
information theory, in contrast to traditional PKC that relies on the
computational difficulty of the algebraic structure of elliptic curves over
finite fields, which can not provide any mathematical proof as to the actual
complexity of reversing the mathematical functions used. The key ingredient of
QKD is based on the fundamental principle of quantum mechanics, in which the
process of measuring a quantum system disturbs the system. If there is some
third-party attacks to read the encrypted data, the quantum state in a Hilbert
space, which is initially a superposition of several states in the Hilbert
space, reduces to a single state that differs from the original state.

##  2 Preliminary — Cryptographic algorithms

In this section, we describe the basic notions of cryptography. Cryptography
is the foundations of secure communication including an exchange of
transactions between two parties in the presence of adversaries.

###  2.1 Encryption

######  Definition 2.1 (Encryption scheme).

Formally, an encryption scheme (or, cipher) is defined by a tuple
$\displaystyle{\mathcal{E}}=({\mathsf{Gen}},{\mathsf{Enc}},{\mathsf{Dec}})$
with a finite size message space $\displaystyle{\mathcal{M}}$. Each algorithms
are defined as follows.

  * •

Key Generation Algorithm ($\displaystyle{\mathsf{Gen}}$): it is a
probabilistic algorithm that outputs a key $\displaystyle k$ chosen according
to some distribution. The set of all possible key space generated by
$\displaystyle{\mathsf{Gen}}$ is called a key space, denoted by
$\displaystyle{\mathcal{K}}$.

  * •

Encryption Algorithm ($\displaystyle{\mathsf{Enc}}$): it takes as input a key
$\displaystyle k$ and a message $\displaystyle m$ and outputs a ciphertext
$\displaystyle c$. We denote by $\displaystyle{\mathsf{Enc}}_{k}(m)$ the
encryption of the plaintext $\displaystyle m$ using the key $\displaystyle k$.
We denote by $\displaystyle{\mathcal{C}}$, the set of all possible ciphertext
which is the output of $\displaystyle{\mathsf{Enc}}(k,m)$ for all possible
choices of $\displaystyle k\in{\mathcal{K}}$ and $\displaystyle
m\in{\mathcal{M}}$.

  * •

Decryption Algorithm ($\displaystyle{\mathsf{Dec}}$): it takes as input a key
$\displaystyle k$ and a ciphertext $\displaystyle c$ and outputs a plaintext
$\displaystyle m$. We denote the decryption of the ciphertext $\displaystyle
c$ using the key $\displaystyle k$ by $\displaystyle{\mathsf{Dec}}(k,c)$. We
assume the perfect correctness, meaning that for all $\displaystyle
k\in{\mathcal{K}}$, $\displaystyle m\in{\mathcal{M}}$, and any ciphertext
$\displaystyle c$, the output of $\displaystyle{\mathsf{Enc}}(k,m)$, it holds
that $\displaystyle m={\mathsf{Dec}}(k,c)$ with probability 1.

######  Definition 2.2 (Perfect secure).

Let
$\displaystyle{\mathcal{E}}=({\mathsf{Gen}},{\mathsf{Enc}},{\mathsf{Dec}})$ be
an encryption scheme with a finite size message space
$\displaystyle{\mathcal{M}}$, and consider a probabilistic experiment in which
a random variable $\displaystyle k\in{\mathcal{K}}$ is uniformly distributed
over $\displaystyle{\mathcal{K}}$. It is called perfect secure if for all
messages $\displaystyle m_{0},m_{1}\in{\mathcal{M}}$ and every ciphertext
$\displaystyle c\in{\mathcal{C}}$, the following condition holds:

${\mathbb{P}}\left({\mathsf{Enc}}(k,m_{0})=c\right)={\mathbb{P}}\left({\mathsf{Enc}}(k,m_{1})=c\right)\;.$
(1)

######  Theorem 2.1.

Let
$\displaystyle{\mathcal{E}}=({\mathsf{Gen}},{\mathsf{Enc}},{\mathsf{Dec}})$ be
perfect secure encryption scheme with a finite size message space
$\displaystyle{\mathcal{M}}$ and a key space $\displaystyle{\mathcal{K}}$,
then we have $\displaystyle|{\mathcal{K}}|\geq|{\mathcal{M}}|$

######  Definition 2.3 (One-time Pad).

One-time Pad is defined as an encryption scheme with the following property.
For a given positive integer $\displaystyle\ell\in{\mathbb{N}}$, and an
encryption scheme
$\displaystyle{\mathcal{E}}=({\mathsf{Gen}},{\mathsf{Enc}},{\mathsf{Dec}})$
with a finite size message space $\displaystyle{\mathcal{M}}$. where the keys,
messages, and ciphertexts are the bit strings with the same length
$\displaystyle\ell$, that is,

${\mathcal{K}}={\mathcal{M}}={\mathcal{C}}=\\{0,1\\}^{\ell}\;.$ (2)

  * •

Key Generation Algorithm: it chooses a key from
$\displaystyle{\mathcal{K}}=\\{0,1\\}^{\ell}$ according to the uniform
distribution.

  * •

Encryption Algorithm: for a given key $\displaystyle k\in\\{0,1\\}^{\ell}$ and
a message $\displaystyle m\in\\{0,1\\}^{\ell}$, it outputs the ciphertext
$\displaystyle c=k\oplus m$.

  * •

Decryption Algorithm: for a given key $\displaystyle k\in\\{0,1\\}^{\ell}$ and
a ciphertext $\displaystyle c\in\\{0,1\\}^{\ell}$, it outputs the message
$\displaystyle m=k\oplus c$.

######  Theorem 2.2.

One-time Pad is a perfect secure encryption scheme.

######  Theorem 2.3 (Shannon’s theorem).

Let
$\displaystyle{\mathcal{E}}=({\mathsf{Gen}},{\mathsf{Enc}},{\mathsf{Dec}})$ be
an encryption scheme with a finite size message space
$\displaystyle{\mathcal{M}}$, for which
$\displaystyle|{\mathcal{K}}|=|{\mathcal{M}}|=|{\mathcal{C}}|$. The encryption
scheme is perfect secure if and only if the following two properties hold,

  * •

Every key $\displaystyle k\in{\mathcal{K}}$ is chosen with equal probability
$\displaystyle{\mathbb{P}}\left({\mathsf{Enc}}(k,m)=c\right)=1/|{\mathcal{M}}|$
for every $\displaystyle m\in{\mathcal{M}}$ and $\displaystyle
c\in{\mathcal{C}}$.

  * •

For every $\displaystyle m\in{\mathcal{M}}$ and $\displaystyle
c\in{\mathcal{C}}$, there exists a unique key $\displaystyle
k\in{\mathcal{K}}$ such that $\displaystyle{\mathsf{Enc}}(k,m)=c$.

######  Definition 2.4 (Attack Game 1 — semantic security).

Let
$\displaystyle{\mathcal{E}}=({\mathsf{Gen}},{\mathsf{Enc}},{\mathsf{Dec}})$ be
an encryption scheme defined over
$\displaystyle({\mathcal{K}},{\mathcal{M}},{\mathcal{C}})$, and for a given
adversary $\displaystyle{\mathcal{A}}$, we define two experiments described
below. For $\displaystyle b=0,1$, we consider the attack game as follows:

  * •

The adversary computes $\displaystyle m_{0},m_{1}\in{\mathcal{M}}$, of the
same length, and sends them to the challenger.

  * •

The challenger computes $\displaystyle k\in{\mathcal{K}}$, $\displaystyle
c={\mathsf{Enc}}(k,m_{b})$, and sends $\displaystyle c$ to the adversary.

  * •

The adversary outputs a bit $\displaystyle b\in\\{0,1\\}$.

For $\displaystyle b=0,1$, let $\displaystyle W_{b}$ be the event that the
adversary $\displaystyle{\mathcal{A}}$ outputs $\displaystyle 1$ in experiment
$\displaystyle b$. We define the semantic security advantage of the adversary
$\displaystyle{\mathcal{A}}$ with respect to
$\displaystyle{\mathcal{E}}=({\mathsf{Gen}},{\mathsf{Enc}},{\mathsf{Dec}})$ as

${\mathsf{SSadv}}({\mathcal{A}},\,{\mathcal{E}})=\big{|}{\mathbb{P}}\left(W_{0}\right)-{\mathbb{P}}\left(W_{1}\right)\big{|}\;.$
(3)

######  Definition 2.5 (Semantic security).

The cipher
$\displaystyle{\mathcal{E}}=({\mathsf{Gen}},{\mathsf{Enc}},{\mathsf{Dec}})$ is
semantic secure if for all efficient adversaries $\displaystyle{\mathcal{A}}$,
the value $\displaystyle{\mathsf{SSadv}}({\mathcal{A}},\,{\mathcal{E}})$ is
negligible.

######  Definition 2.6 (Attack Game 2 — message recovery).

For a given cipher
$\displaystyle{\mathcal{E}}=({\mathsf{Gen}},{\mathsf{Enc}},{\mathsf{Dec}})$ be
an encryption scheme defined over
$\displaystyle({\mathcal{K}},{\mathcal{M}},{\mathcal{C}})$, and for a given
adversary $\displaystyle{\mathcal{A}}$, the attack game proceeds as follows:

  * •

The challenger computes $\displaystyle m\in{\mathcal{M}}$, $\displaystyle
k\in{\mathcal{K}}$, $\displaystyle c={\mathsf{Enc}}(k,m)$, and sends
$\displaystyle c$ to the adversary.

  * •

The adversary outputs a message $\displaystyle m^{\prime}\in{\mathcal{M}}$.

  * •

Let $\displaystyle W$ be the event with $\displaystyle m^{\prime}=m$.

In this case, we say that the adversary $\displaystyle{\mathcal{A}}$ wins the
game, and we define the message recovery advantage of the adversary
$\displaystyle{\mathcal{A}}$ with respect to
$\displaystyle{\mathcal{E}}=({\mathsf{Gen}},{\mathsf{Enc}},{\mathsf{Dec}})$ as

${\mathsf{MRadv}}({\mathcal{A}},\,{\mathcal{E}})=\big{|}{\mathbb{P}}\left(W\right)-1/|{\mathcal{M}}|\big{|}\;.$
(4)

######  Definition 2.7 (Message recovery security).

The cipher
$\displaystyle{\mathcal{E}}=({\mathsf{Gen}},{\mathsf{Enc}},{\mathsf{Dec}})$ is
secure against message recovery if for all efficient adversaries
$\displaystyle{\mathcal{A}}$, the value
$\displaystyle{\mathsf{MRadv}}({\mathcal{A}},\,{\mathcal{E}})$ is negligible.

######  Theorem 2.4.

Let
$\displaystyle{\mathcal{E}}=({\mathsf{Gen}},{\mathsf{Enc}},{\mathsf{Dec}})$ be
a cipher defined over
$\displaystyle({\mathcal{K}},{\mathcal{M}},{\mathcal{C}})$. If
$\displaystyle{\mathcal{E}}$ is semantic secure then
$\displaystyle{\mathcal{E}}$ is secure against message recovery.

######  Definition 2.8 (Attack Game 3 — parity prediction).

For a given cipher
$\displaystyle{\mathcal{E}}=({\mathsf{Gen}},{\mathsf{Enc}},{\mathsf{Dec}})$ be
a cipher defined over
$\displaystyle({\mathcal{K}},{\mathcal{M}},{\mathcal{C}})$. For $\displaystyle
m\in{\mathcal{M}}$, we define parity by $\displaystyle{\mathrm{parity}}(m)=1$
if the number of $\displaystyle 1$’s in $\displaystyle m$ is odd, otherwise
$\displaystyle{\mathrm{parity}}(m)=0$. For a given adversary
$\displaystyle{\mathcal{A}}$, the attack game proceeds as follows:

  * •

The challenger computes $\displaystyle m\in{\mathcal{M}}$, $\displaystyle
k\in{\mathcal{K}}$, $\displaystyle c={\mathsf{Enc}}(k,m)$, and sends
$\displaystyle c$ to the adversary.

  * •

The adversary outputs $\displaystyle b^{\prime}\in\\{0,\,1\\}$.

  * •

Let $\displaystyle W$ be the event with $\displaystyle
b^{\prime}={\mathrm{parity}}(m)$.

In this case, we say that the adversary $\displaystyle{\mathcal{A}}$ wins the
game, and we define the message recovery advantage of the adversary
$\displaystyle{\mathcal{A}}$ with respect to
$\displaystyle{\mathcal{E}}=({\mathsf{Gen}},{\mathsf{Enc}},{\mathsf{Dec}})$ as

${\mathsf{Parityadv}}({\mathcal{A}},\,{\mathcal{E}})=\big{|}{\mathbb{P}}\left(W\right)-1/2\big{|}\;.$
(5)

######  Definition 2.9 (Parity prediction security).

A cipher
$\displaystyle{\mathcal{E}}=({\mathsf{Gen}},{\mathsf{Enc}},{\mathsf{Dec}})$ is
secure against parity prediction if for all efficient adversaries
$\displaystyle{\mathcal{A}}$, the value
$\displaystyle{\mathsf{Parityadv}}({\mathcal{A}},\,{\mathcal{E}})$ is
negligible.

######  Theorem 2.5.

Let
$\displaystyle{\mathcal{E}}=({\mathsf{Gen}},{\mathsf{Enc}},{\mathsf{Dec}})$ be
a cipher defined over
$\displaystyle({\mathcal{K}},{\mathcal{M}},{\mathcal{C}})$. If
$\displaystyle{\mathcal{E}}$ is semantic secure then
$\displaystyle{\mathcal{E}}$ is secure against parity prediction.

######  Definition 2.10 (Negligible function).

A function $\displaystyle f:{\mathbb{N}}\to{\mathbb{R}}$ is called negligible
if for all $\displaystyle c\in\mathbb{R}_{++}$ there exists $\displaystyle
n_{0}\in{\mathbb{N}}$ such that for all integers $\displaystyle
n\in{\mathbb{Z}}$ with $\displaystyle n\geq n_{0}$, we have
$\displaystyle|f(n)|<1/n^{c}$.

######  Corollary 2.1.

A function $\displaystyle f:{\mathbb{N}}\to{\mathbb{R}}$ is negligible if and
only if for all $\displaystyle n\in{\mathbb{Z}}$ and $\displaystyle
c\in\mathbb{R}_{++}$, we have

$\lim_{n\to\infty}f(n)\,n^{c}=0\;.$ (6)

######  Definition 2.11 (Super-poly function).

A function $\displaystyle f:{\mathbb{N}}\to{\mathbb{R}}$ is called super-poly
if $\displaystyle 1/f$ is negligible.

######  Definition 2.12 (Poly-bounded function).

A function $\displaystyle f:{\mathbb{N}}\to{\mathbb{R}}$ is called poly-
bounded if there exists $\displaystyle c,d\in\mathbb{R}_{++}$ such that for
all integers $\displaystyle n\in{\mathbb{Z}}$, we have
$\displaystyle|f(n)|\leq n^{c}+d$.

######  Definition 2.13 (Efficient algorithm).

Let $\displaystyle{\mathcal{A}}$ be an efficient (probabilistic) algorithm
that takes as input a security parameter $\displaystyle\lambda\in{\mathbb{N}}$
as well as other parameters encoded as a bit string $\displaystyle
x\in\\{0,1\\}^{\leq p(\lambda)}$ for some fixed polynomial function
$\displaystyle p$. We call $\displaystyle{\mathcal{A}}$ an efficient
(probabilistic) algorithm if there exists a poly-bounded function
$\displaystyle\tau$ and a negligible function $\displaystyle\epsilon$ such
that for all $\displaystyle\lambda\in{\mathbb{N}}$ and all $\displaystyle
x\in\\{0,1\\}^{\leq p(\lambda)}$, the probability that the running time of
$\displaystyle{\mathcal{A}}$ on input $\displaystyle(\lambda,x)$ exceeds
$\displaystyle\tau(\lambda)$ is at most $\displaystyle\epsilon(\lambda)$.

######  Definition 2.14 (System parameterization).

A system parameterization is an efficient probabilistic algorithm
$\displaystyle P$ that given a security parameter
$\displaystyle\lambda\in{\mathbb{N}}$ as input, outputs a bit string
$\displaystyle\Lambda$, which is called a system parameter, whose length is
bounded by a polynomial function in $\displaystyle\lambda$. We also define
something related terminologies.

  * •

A collection
$\displaystyle{\mathbb{S}}=\\{S_{\lambda\,,\Lambda}\\}_{\lambda\,,\Lambda}$ of
a finite sets of bits of strings, where $\displaystyle\lambda\in{\mathbb{N}}$
and $\displaystyle\Lambda\in\operatorname{supp}(P(\lambda))$, is called as a
family of spaces with system parameterization $\displaystyle P$, provided the
lengths of all the strings in each of the sets $\displaystyle
S_{\lambda\,,\Lambda}$ are bounded by some polynomial function $\displaystyle
p$ in $\displaystyle\lambda$.

  * •

We call that
$\displaystyle{\mathbb{S}}=\\{S_{\lambda\,,\Lambda}\\}_{\lambda\,,\Lambda}$ is
efficiently recognizable if there is an efficient deterministic algorithm that
on input $\displaystyle\lambda\in{\mathbb{N}}$,
$\displaystyle\Lambda\in\operatorname{supp}(P(\lambda))$, and $\displaystyle
s\in\\{0,1\\}^{\leq p(\lambda)}$, determines if $\displaystyle\lambda\in
S_{\lambda\,,\Lambda}$.

  * •

We call that
$\displaystyle{\mathbb{S}}=\\{S_{\lambda\,,\Lambda}\\}_{\lambda\,,\Lambda}$ is
efficiently sampleable if there is an efficient probabilistic algorithm that
on input $\displaystyle\lambda\in{\mathbb{N}}$ and
$\displaystyle\Lambda\in\operatorname{supp}(P(\lambda))$, outputs an element
uniformly distributed over $\displaystyle S_{\lambda\,,\Lambda}$.

  * •

We call that
$\displaystyle{\mathbb{S}}=\\{S_{\lambda\,,\Lambda}\\}_{\lambda\,,\Lambda}$
has an efficient length function if there is an efficient deterministic
algorithm that on input $\displaystyle\lambda\in{\mathbb{N}}$,
$\displaystyle\Lambda\in\operatorname{supp}(P(\lambda))$, and $\displaystyle
s\in S_{\lambda\,,\Lambda}$, outputs a non-negative integer, called the length
of $\displaystyle s$.

######  Definition 2.15 (Computational cipher).

A computational cipher consists of a pair of algorithms
$\displaystyle({\mathsf{Enc}},{\mathsf{Dec}})$, along with three families of
spaces with system parameterization $\displaystyle P$.

$\displaystyle\displaystyle{\mathbb{K}}$ $\displaystyle\displaystyle=$
$\displaystyle\displaystyle\\{K_{\lambda\,,\Lambda}\\}_{\lambda\,,\Lambda}\;,$
$\displaystyle\displaystyle{\mathbb{M}}$ $\displaystyle\displaystyle=$
$\displaystyle\displaystyle\\{M_{\lambda\,,\Lambda}\\}_{\lambda\,,\Lambda}\;,$
$\displaystyle\displaystyle{\mathbb{C}}$ $\displaystyle\displaystyle=$
$\displaystyle\displaystyle\\{C_{\lambda\,,\Lambda}\\}_{\lambda\,,\Lambda}\;.$

  * •

$\displaystyle{\mathbb{K}}$, $\displaystyle{\mathbb{M}}$, and
$\displaystyle{\mathbb{C}}$ are efficiently recognizable.

  * •

$\displaystyle{\mathbb{K}}$ is efficiently sampleable.

  * •

$\displaystyle{\mathbb{M}}$ has an efficient length function.

  * •

$\displaystyle{\mathsf{Enc}}$ is an efficient probabilistic algorithm that on
inputs $\displaystyle\lambda\,,\Lambda\,,k\,,m$, where
$\displaystyle\lambda\in{\mathbb{N}}$,
$\displaystyle\Lambda\in\operatorname{supp}(P(\lambda))$, $\displaystyle k\in
K_{\lambda\,,\Lambda}$, and $\displaystyle m\in M_{\lambda\,,\Lambda}$,
outputs an element of $\displaystyle C_{\lambda\,,\Lambda}$.

  * •

$\displaystyle{\mathsf{Dec}}$ is an efficient deterministic algorithm that on
inputs $\displaystyle\lambda\,,\Lambda\,,k\,,c$, where
$\displaystyle\lambda\in{\mathbb{N}}$,
$\displaystyle\Lambda\in\operatorname{supp}(P(\lambda))$, $\displaystyle k\in
K_{\lambda\,,\Lambda}$, and $\displaystyle c\in C_{\lambda\,,\Lambda}$,
outputs an element of $\displaystyle M_{\lambda\,,\Lambda}$, or a special
symbol which express to reject $\displaystyle\notin M_{\lambda\,,\Lambda}$.

  * •

For all $\displaystyle\lambda\,,\Lambda\,,k\,,m\,,c$, where
$\displaystyle\lambda\in{\mathbb{N}}$,
$\displaystyle\Lambda\in\operatorname{supp}(P(\lambda))$, $\displaystyle k\in
K_{\lambda\,,\Lambda}$, $\displaystyle m\in M_{\lambda\,,\Lambda}$, and
$\displaystyle
c\in\operatorname{supp}({\mathsf{Enc}}(\lambda\,,\Lambda\,;k\,,m))$, we have
$\displaystyle m={\mathsf{Dec}}(\lambda\,,\Lambda\,;k\,,c)$.

###  2.2 Stream cipher

Recall that One-Time Pad is a Shanon’s cipher
$\displaystyle{\mathcal{E}}=({\mathsf{Gen}},{\mathsf{Enc}},{\mathsf{Dec}})$
defined over $\displaystyle({\mathcal{K}},\mathcal{M},\mathcal{C})$, where
$\displaystyle|{\mathcal{K}}|=|{\mathcal{M}}|=|{\mathcal{C}}|=\\{0,1\\}^{L}$.
Here we consider the possible scheme with shorter length of encryption key. We
consider the case where the encryption key is given by a $\displaystyle n$-bit
string with $\displaystyle\ell<L$. Thus, the modified One-Time Pad is defined
as follows: for $\displaystyle s\in\\{0,1\\}^{\ell}$ and $\displaystyle
m,c\in\\{0,1\\}^{L}$, the encryption and decryption scheme are given by

${\mathsf{Enc}}(s,m)=G(s)\oplus m\;,~{}{\mathsf{Dec}}(s,c)=G(s)\oplus c\;,$
(7)

where the function $\displaystyle G(s)$ is called as the pseudo-random
generator (PRG), and this cipher is called as stream cipher. According to the
Shannon’s Theorem, this stream cipher by itself cannot achieve a perfect
security; however if $\displaystyle G(s)$ satisfies some appropriate security
property, then the stream cipher can be semantic secure.

######  Definition 2.16 (Pseudo-random generator (PRG)).

A pseudo-random generator (PRG) consists of an algorithm $\displaystyle
G:\\{0,1\\}^{\ell}\to\\{0,1\\}^{L}$, along with two families of spaces with
system parametrization $\displaystyle P$:

${\mathbb{S}}=\\{S_{\lambda\,,\Lambda}\\}_{\lambda\,,\Lambda}~{}~{}{\mathrm{and}}~{}~{}{\mathbb{R}}=\\{R_{\lambda\,,\Lambda}\\}_{\lambda\,,\Lambda}\;,$
(8)

such that

  * •

$\displaystyle{\mathbb{S}}$ and $\displaystyle{\mathbb{R}}$ are efficiently
recognizable and sampleable.

  * •

Algorithm $\displaystyle G$ is an efficient deterministic algorithm that on
inputs $\displaystyle\lambda\,,\Lambda\,,s$, where
$\displaystyle\lambda\in{\mathbb{N}}$,
$\displaystyle\Lambda\in\operatorname{supp}(P(\lambda))$, and $\displaystyle
s\in S_{\lambda\,,\Lambda}$, outputs an element $\displaystyle r\in
R_{\lambda\,,\Lambda}$.

######  Definition 2.17 (Attack Game 4 — PRG).

For a given PRG $\displaystyle G$, defined over $\displaystyle(S,R)$, and for
a given adversary $\displaystyle{\mathcal{A}}$, the attack game proceeds as
follows.

  * •

The challenger computes $\displaystyle r\in R$ as follows.
If $\displaystyle b=0$: $\displaystyle r=G(s)$ for $\displaystyle s\in S$,
If $\displaystyle b=1$: $\displaystyle r\in R$.
and sends the output $\displaystyle r$ to the adversary.

  * •

The adversary outputs a bit $\displaystyle b^{\prime}\in\\{0,1\\}$.

Let $\displaystyle W_{b}$ be the event where the adversary
$\displaystyle{\mathcal{A}}$ outputs a bit $\displaystyle 1$ for a given bit
$\displaystyle b\in\\{0,\,1\\}$. We define $\displaystyle{\mathcal{A}}$’s
advantage with respect to $\displaystyle G$ as

${\mathsf{PRGadv}}({\mathcal{A}},\,G)=\big{|}{\mathbb{P}}\left(W_{0}\right)-{\mathbb{P}}\left(W_{1}\right)\big{|}\;.$
(9)

######  Definition 2.18 (PRG security).

A PRG $\displaystyle G$ is secure if the value
$\displaystyle{\mathsf{PRGadv}}({\mathcal{A}},\,G)$ is negligible for all
efficient adversaries $\displaystyle{\mathcal{A}}$.

######  Definition 2.19 (Stream cipher).

Let $\displaystyle G:\\{0,1\\}^{\ell}\to\\{0,1\\}^{L}$ be a PRG algorithm, the
stream cipher
$\displaystyle{\mathcal{E}}=({\mathsf{Gen}},{\mathsf{Enc}},{\mathsf{Dec}})$
constructed from $\displaystyle G$ is defined over
$\displaystyle(\\{0,1\\}^{\ell},\\{0,1\\}^{\leq L},\\{0,1\\}^{\leq L})$. For
$\displaystyle s\in\\{0,1\\}^{\ell}$ and $\displaystyle m,c\in\\{0,1\\}^{\leq
L}$, the encryption and decryption schemes are defined as follows. If
$\displaystyle|m|=v$,

${\mathsf{Enc}}(s,m)=G(s)[0,\cdots,v-1]\oplus m\;,$ (10)

and if $\displaystyle|c|=v$,

${\mathsf{Dec}}(s,c)=G(s)[0,\cdots,v-1]\oplus c\;.$ (11)

###  2.3 Block cipher

######  Definition 2.20 (Block cipher).

A block cipher is a deterministic cipher
$\displaystyle{\mathcal{E}}=({\mathsf{Gen}},{\mathsf{Enc}},{\mathsf{Dec}})$
whose message space and cipher space are given by the same set
$\displaystyle{\mathcal{S}}$. We call $\displaystyle S$ as the data block
space, and whose element $\displaystyle s\in S$ is referred as the data block.

There is a famous product of block cipher, which is the so-called, AES
(Advanced Encryption Standard). The AES keys (or, AES data block) has 128-bit
strings, hence the size of data block space is given by
$\displaystyle|\mathcal{S}|=2^{128}$. The key ingredient of block cipher is
that we choose two steps for choosing random numbers: 1) random choice of
keys, 2) random permutation of a chosen key. We denotes the set of all
permutations on $\displaystyle\mathcal{S}$ as
$\displaystyle{\mathsf{Perm{[\mathcal{S}]}}}$. The size of those set is given
by $\displaystyle|{\mathsf{Perm{[\mathcal{S}]}}}|=|\mathcal{S}|!$. In the case
of AES scheme with $\displaystyle|\mathcal{S}|=2^{128}$, the number of
permutations is about

$|{\mathsf{Perm{[\mathcal{S}]}}}|\cong 2^{2^{135}}\;,$ (12)

while the number of permutations defined by 128-bit strings AES scheme is at
most $\displaystyle 2^{128}$. More precisely, block cipher is constructed to
behave as pseudo-random permutations. Because there are $\displaystyle
2^{\ell}!$ permutations on $\displaystyle\ell$-bit strings, it is said that a
secure block cipher should be computational indistinguishable from a random
permutation.

######  Definition 2.21 (Attack Game 5 — block cipher).

For a given block cipher
$\displaystyle{\mathcal{E}}=({\mathsf{Gen}},{\mathsf{Enc}},{\mathsf{Dec}})$
defined over $\displaystyle({\mathcal{K}},\mathcal{S},\mathcal{S})$. , and for
a given adversary $\displaystyle{\mathcal{A}}$, we define two experiments
described below. For $\displaystyle b=0,1$, the attack game proceeds as
follows:

  * •

The challenger choose a function $\displaystyle f$ as follows:
If $\displaystyle b=0$: $\displaystyle k\in\mathcal{K}$, $\displaystyle
f(s)={\mathsf{Enc}}(k,s)$ for $\displaystyle s\in\mathcal{S}$, else if
$\displaystyle b=1$: $\displaystyle f\in\mathsf{Perm{[\mathcal{S}]}}$.

  * •

The adversary send a sequence of queries to the challenger.
For a given $\displaystyle i\in{\mathbb{N}}$, $\displaystyle i$-th query is is
a data block $\displaystyle x_{i}\in\mathcal{S}$. The challenger computes
$\displaystyle y_{i}=f(x_{i})\in\mathcal{S}$, and gives $\displaystyle y_{i}$
to the adversary.

  * •

The adversary outputs a bit $\displaystyle b^{\prime}\in\\{0,\,1\\}$.

Let $\displaystyle W_{b}$ be the event where the adversary
$\displaystyle{\mathcal{A}}$ outputs a bit $\displaystyle 1$ for a given bit
$\displaystyle b\in\\{0,\,1\\}$. We define $\displaystyle{\mathcal{A}}$’s
advantage with respect to the block cipher $\displaystyle{\mathcal{E}}$ as

${\mathsf{BCadv}}({\mathcal{A}},\,{\mathcal{E}})=\big{|}{\mathbb{P}}\left(W_{0}\right)-{\mathbb{P}}\left(W_{1}\right)\big{|}\;.$
(13)

Finally, we call that the adversary $\displaystyle{\mathcal{A}}$ is a q-query
BC adversary if $\displaystyle{\mathcal{A}}$ issues at most q queries.

######  Definition 2.22 (Block cipher security).

A block cipher $\displaystyle{\mathcal{E}}$ is secure if for all efficient
adversaries $\displaystyle{\mathcal{A}}$, the value
$\displaystyle{\mathsf{BCadv}}({\mathcal{A}},\,{\mathcal{E}})$ is negligible.

Let
$\displaystyle{\mathcal{E}}=({\mathsf{Gen}},{\mathsf{Enc}},{\mathsf{Dec}})$ be
a block cipher defined over
$\displaystyle({\mathcal{K}},\mathcal{S},\mathcal{S})$. If
$\displaystyle{\mathcal{E}}$ is secure, it must be unpredictable, which means
that every efficient adversary wins the following prediction game with
negligible probability. In the prediction game, the challenger chooses a
random key $\displaystyle k\in{\mathcal{K}}$, and the adversary send a
sequence of queries $\displaystyle\\{x_{1},\cdots,x_{q}\\}$ in response to the
$\displaystyle i$-th query $\displaystyle x_{i}\in\mathcal{S}$ and the
challenger responds with $\displaystyle{\mathsf{Enc}}(k,x_{i})\in\mathcal{S}$.
These queries are adaptive since each query may depend on the previous
response. Finally, the adversary $\displaystyle{\mathcal{A}}$ outputs a pair
of values $\displaystyle(x_{q+1},\,y)$, where $\displaystyle
x_{q+1}\notin\\{x_{1},\cdots,x_{q}\\}$. The adversary
$\displaystyle{\mathcal{A}}$ wins this prediction game if $\displaystyle
y={\mathsf{Enc}}(k,x_{q+1})$.

Furthermore, if $\displaystyle{\mathcal{E}}$ is unpredictable, then it is
secure against key-recovery, which means that every efficient adversary wins
the following key-recovery game with negligible probability. In the key-
recovery game, the adversary interacts with the challenger as the same with
the prediction game, except that at the end, the adversary
$\displaystyle{\mathcal{A}}$ outputs a candidate key $\displaystyle
k^{\prime}\in{\mathcal{K}}$, and $\displaystyle{\mathcal{A}}$ wins the game if
$\displaystyle k^{\prime}=k$.

Combining those two implications, if $\displaystyle{\mathcal{E}}$ is a secure
block cipher, it must be secure against key-recovery. Moreover, if
$\displaystyle{\mathcal{E}}$ is secure against key-recovery, it must be the
case that $\displaystyle|{\mathcal{K}}|$ is large (i.e., super-poly). We can
see this as follows. An adversary can always win the key-recovery game with
the probability $\displaystyle 1/|{\mathcal{K}}|$ by simply choosing the key
$\displaystyle k^{\prime}\in{\mathcal{K}}$ at random. If
$\displaystyle|{\mathcal{K}}|$ is not super-poly, then this probability
$\displaystyle 1/|{\mathcal{K}}|$ is non-negligible.

We can trade success probability for running-time proceeding a different
attack, called an exhaustive search attack. In the exhaustive search attack,
the adversary $\displaystyle{\mathcal{A}}$ makes a few, arbitrary queries
$\displaystyle\\{x_{1},\cdots,x_{q}\\}$ in the key-recovery game to obtain the
responses $\displaystyle\\{y_{1},\cdots,y_{q}\\}$. One may argue — at least,
assuming that $\displaystyle|{\mathcal{S}}|\leq|{\mathcal{K}}|$ and
$\displaystyle|{\mathcal{K}}|$ is super-poly — that for fairly small values of
$\displaystyle q$ (in fact, $\displaystyle q=2$), with all but negligible
probability, only one key satisfies

$y_{i}={\mathsf{Enc}}(k,x_{i})~{}{\mathrm{for}}~{}i=1,\cdots,q\;.$ (14)

If there is only one such key, the key that the adversary finds will be the
one that is chosen by the challenger, and the adversary will win the game.
Thus, the adversary wins the key-recovery game with all but negligible
probability; however, the running time is linear in
$\displaystyle|{\mathcal{K}}|$.

######  Definition 2.23 (ECB cipher).

Let
$\displaystyle{\mathcal{E}}=({\mathsf{Gen}},{\mathsf{Enc}},{\mathsf{Dec}})$ be
a block cipher defined over
$\displaystyle({\mathcal{K}},\mathcal{S},\mathcal{S})$. For any poly-bounded
$\displaystyle\ell\geq 1$, we can define a block cipher
$\displaystyle{\mathcal{E}}^{\prime}$ defined over
$\displaystyle({\mathcal{K}},\mathcal{S}^{\leq\ell},\mathcal{S}^{\leq\ell})$
as follows.

  * •

For $\displaystyle k\in{\mathcal{K}}$ and $\displaystyle
m\in\mathcal{S}^{\leq\ell}$ with $\displaystyle v=|m|$, we define

${\mathsf{Enc}}(k,m)^{\prime}=\left({\mathsf{Enc}}(k,m[0]),\cdots,{\mathsf{Enc}}(k,m[v-1])\right)\;.$
(15)

  * •

For $\displaystyle k\in{\mathcal{K}}$ and $\displaystyle
c\in\mathcal{S}^{\leq\ell}$ with $\displaystyle v=|c|$, we define

${\mathsf{Dec}}(k,m)^{\prime}=\left({\mathsf{Dec}}(k,m[0]),\cdots,{\mathsf{Dec}}(k,m[v-1])\right)\;.$
(16)

We call this block cipher $\displaystyle{\mathcal{E}}^{\prime}$ as the
$\displaystyle\ell$-wise electronic code book (ECB) cipher derived from the
block cipher $\displaystyle{\mathcal{E}}$.

######  Theorem 2.6.

Let $\displaystyle\mathcal{E}=({\mathsf{Gen}},{\mathsf{Enc}},{\mathsf{Dec}})$
be a block cipher defined over
$\displaystyle(\mathcal{K},\mathcal{S},\mathcal{S})$. Let
$\displaystyle\ell\in{\mathbb{N}}$ be any poly-bounded value, and
$\displaystyle{\mathcal{E}}^{\prime}$ be the $\displaystyle\ell$-wise ECB
cipher derived from $\displaystyle{\mathcal{E}}$, but with the message space
restricted to all sequences of at most $\displaystyle\ell$ distinct data
blocks. If $\displaystyle{\mathcal{E}}$ is a secure block cipher, then
$\displaystyle{\mathcal{E}}^{\prime}$ is semantically secure.

The block ciphers are the most primitive scheme in cryptography. In practice,
constructing block ciphers use the same scheme, called the iterated block
cipher. At first, we chooses a simple block cipher,
$\displaystyle\mathcal{E}=({\mathsf{Gen}},{\mathsf{Enc}},{\mathsf{Dec}})$
defined over $\displaystyle({\mathcal{K}},\mathcal{S},\mathcal{S})$, which is
apparently insecure at this time. This block cipher is called as the round
cipher. Second, we chooses a PRG $\displaystyle G$ that is used to generate
$\displaystyle n$-sequence of pseudo-random keys
$\displaystyle(k_{1},\cdots,k_{n})$ from $\displaystyle k\in{\mathcal{K}}$. In
this case, the PRG $\displaystyle G$ is called as the key expansion function.
More precisely speaking, the second step in constructing the iterated block
cipher is proceeded in iterative ways, that is,

  * •

Key expansion:

$(k_{1},\cdots,k_{n})=G(k)\;,~{}{\mathrm{for}}~{}n\in{\mathbb{N}}\;,~{}k\in{\mathcal{K}}\;.$
(17)

  * •

Iteration: for each $\displaystyle i=1,\cdots,n$, we apply the encryption
function with the generated pseudo-random key $\displaystyle k_{i}$, and
outputs

$y={\mathsf{Enc}}(k_{n},{\mathsf{Enc}}(k_{n-1},\cdots,{\mathsf{Enc}}(k_{2},{\mathsf{Enc}}(k_{1},x)))\cdots)\;.$
(18)

At each step, the operation of encryption function
$\displaystyle{\mathsf{Enc}}$ is called the round, and the generated sequence
of keys are called the round keys. The iteration of decryptions is almost the
same except that the round keys are applied in reverse order.

$x={\mathsf{Dec}}(k_{1},{\mathsf{Dec}}(k_{2},\cdots,{\mathsf{Dec}}(k_{n-1},{\mathsf{Dec}}(k_{n},y)))\cdots)\;.$
(19)

One of the most famous algorithm of the round cipher is known as the Data
Encryption Standard (DES). A strengthen version of the DES is called as the
Triple-DES (3DES), which consists of three times of the rounds with each key
space having $\displaystyle 56$-bits key strings, hence the key length is
$\displaystyle 3\times 56=168$. The Triple-DES has been approved through the
year 2030 by the NIST as the U.S. standard in 1998. However, in 2002, it was
superseded by the more secured AES algorithm, which has $\displaystyle
128$-bits in each key space, and $\displaystyle 10$ times of the rounds.

###  2.4 Universal hash function

######  Definition 2.24 (Hash function).

A hash function $\displaystyle H$ is a deterministic algorithm, whose inputs
are a key $\displaystyle k$ and a message $\displaystyle m$, its output
$\displaystyle t=H(k,m)$ is called as digest. The hash function is defined
over the space $\displaystyle({\mathcal{K}},\mathcal{M},\mathcal{T})$, where
the digest space $\displaystyle\mathcal{T}$ is the space in which the digest
$\displaystyle t$ lies. In general, for two messages $\displaystyle
m_{1},m_{2}\in\mathcal{M}$ with $\displaystyle m_{1}\neq m_{2}$ and
$\displaystyle k\in\mathcal{K}$, we say those two messages form collision for
the hash function $\displaystyle H$ under the key $\displaystyle k$ if

$H(k,m_{1})=H(k,m_{2})\;.$ (20)

In general, since the size of the space $\displaystyle\mathcal{T}$ is much
smaller than that of the space $\displaystyle\mathcal{M}$, it often happens to
occur the collisions for the hash function $\displaystyle H$. However, it is
necessary condition that the collision-less property of the hash function when
using it in cryptography. In practice, it is enough to satisfy the weak
collision-less property, in which the adversary must find a collision with no
information on the keys at all.

######  Definition 2.25 (Attack Game 6 — collision-less security).

For a hash function $\displaystyle H$ defined over the space
$\displaystyle({\mathcal{K}},\mathcal{M},\mathcal{T})$, and consider the
adversary $\displaystyle{\mathcal{A}}$, the attack game proceeds as follows.

  * •

The challenger chooses a random key $\displaystyle k\in{\mathcal{K}}$, and
keeps it to itself.

  * •

The adversary $\displaystyle{\mathcal{A}}$ outputs two distinct messages
$\displaystyle m_{1},m_{2}\in\mathcal{M}$.

We say that the adversary $\displaystyle{\mathcal{A}}$ wins the game if two
messages collide:

$H(k,m_{1})=H(k,m_{2})\;.$ (21)

We define $\displaystyle{\mathcal{A}}$’s advantage with respect to
$\displaystyle H$, denoted by
$\displaystyle{\mathsf{UHFadv}}({\mathcal{A}},H)$ as the probability that
$\displaystyle{\mathcal{A}}$ wins the game.

######  Definition 2.26 (Universal hash function).

Let $\displaystyle H$ be a hash function defined over the space
$\displaystyle({\mathcal{K}},\mathcal{M},\mathcal{T})$.

  * •

We call that $\displaystyle H$ is $\displaystyle\epsilon$-bounded universal
hash function (or $\displaystyle\epsilon$-UHF) if
$\displaystyle{\mathsf{UHFadv}}({\mathcal{A}},H)\leq\epsilon$ for all the
adversary $\displaystyle{\mathcal{A}}$. Equivalently, for every pair of
distinct messages $\displaystyle m_{1},m_{2}\in\mathcal{M}$, $\displaystyle H$
is $\displaystyle\epsilon$-UHF if we have

${\mathbb{P}}\left[H(k,m_{1})=H(k,m_{2})\right]\leq\epsilon\;,$ (22)

where the probability is taken all over the random choice of $\displaystyle
k\in{\mathcal{K}}$.

  * •

We call that $\displaystyle H$ is a statistical UHF if it is an
$\displaystyle\epsilon$-UHF with some negligible $\displaystyle\epsilon$.

  * •

We call that $\displaystyle H$ is a computational UHF if
$\displaystyle{\mathsf{UHFadv}}({\mathcal{A}},H)$ is negligible for all the
efficient adversaries $\displaystyle{\mathcal{A}}$.

###  2.5 Public-key encryption

######  Definition 2.27 (Trapdoor function scheme).

A trapdoor function scheme is a tuple of efficient algorithms
$\displaystyle\mathcal{E}=({\mathsf{Gen}},{\mathsf{Enc}},{\mathsf{Dec}})$
along with two families of spaces with system parametrization $\displaystyle
P$:

${\mathbb{M}}=\\{M_{\lambda\,,\Lambda}\\}_{\lambda\,,\Lambda}~{}~{}{\mathrm{and}}~{}~{}{\mathbb{C}}=\\{C_{\lambda\,,\Lambda}\\}_{\lambda\,,\Lambda}\;,$
(23)

where $\displaystyle\lambda\in{\mathbb{N}}$ and
$\displaystyle\Lambda\in\operatorname{supp}(P(\lambda))$. The following
properties must be held.

  * •

$\displaystyle{\mathbb{M}}$ is efficiently recognizable and sampleable.

  * •

$\displaystyle{\mathbb{C}}$ is efficiently recognizable.

  * •

$\displaystyle{\mathsf{Gen}}$ is an efficient probabilistic algorithm such
that on inputs $\displaystyle\lambda\in{\mathbb{N}}$ and
$\displaystyle\Lambda\in\operatorname{supp}(P(\lambda))$, it outputs a pair
$\displaystyle(p_{k},s_{k})$ where $\displaystyle p_{k}$ and $\displaystyle
s_{k}$ are the bit strings those lengths must be poly-bounded in
$\displaystyle\lambda$.

  * •

$\displaystyle{\mathsf{Enc}}$ is an efficient deterministic function so that
on inputs $\displaystyle\lambda\in{\mathbb{N}}$,
$\displaystyle\Lambda\in\operatorname{supp}(P(\lambda))$, $\displaystyle
p_{k}$ with
$\displaystyle(p_{k},s_{k})\in\operatorname{supp}({\mathsf{Gen}}(\lambda,\Lambda))$,
and $\displaystyle m\in M_{\lambda\,,\Lambda}$, it outputs an element of
$\displaystyle C_{\lambda\,,\Lambda}$.

  * •

$\displaystyle{\mathsf{Dec}}$ is an efficient deterministic function so that
on inputs $\displaystyle\lambda\in{\mathbb{N}}$,
$\displaystyle\Lambda\in\operatorname{supp}(P(\lambda))$, $\displaystyle
s_{k}$ with
$\displaystyle(p_{k},s_{k})\in\operatorname{supp}({\mathsf{Gen}}(\lambda,\Lambda))$,
and $\displaystyle c\in C_{\lambda\,,\Lambda}$, it outputs an element of
$\displaystyle M_{\lambda\,,\Lambda}$.

  * •

For all $\displaystyle\lambda\in{\mathbb{N}}$,
$\displaystyle\Lambda\in\operatorname{supp}(P(\lambda))$,
$\displaystyle(p_{k},s_{k})\in\operatorname{supp}({\mathsf{Gen}}(\lambda,\Lambda))$,
and $\displaystyle m\in M_{\lambda\,,\Lambda}$, it satisfies

${\mathsf{Dec}}(\lambda\,,\Lambda;s_{k},{\mathsf{Enc}}(\lambda\,,\Lambda;p_{k},m))=m\;.$
(24)

One of the most famous example of the trapdoor function scheme is the so-
called, RSA scheme.

######  Definition 2.28 (RSA trapdoor permutation scheme).

The basic algorithms for the RSA trapdoor permutation scheme
$\displaystyle\mathcal{E}=({\mathsf{Gen}},{\mathsf{Enc}},{\mathsf{Dec}})$ are
explained as follows. It is parametrized by fixed values of
$\displaystyle\ell>2$ (integer) and $\displaystyle e>2$ (odd integer). Then,
we proceed the following steps.

  * •

Key generation: At first, we use an efficient probabilistic algorithm
$\displaystyle{\mathsf{RSAGen}}$ which outputs a pair of integers
$\displaystyle(n,d)={\mathsf{RSAGen}}(\ell,e)$, where $\displaystyle
n=p\dot{q}$ with $\displaystyle p,~{}q$ be distinct primes, and $\displaystyle
d=e^{-1}$ (mod $\displaystyle(p-1)(q-1)$). Then, a pair of keys
$\displaystyle(p_{k},s_{k})$ is given by $\displaystyle p_{k}=(n,e)$ and
$\displaystyle s_{k}=(n,d)$.

  * •

Encryption: For a given public key $\displaystyle p_{k}=(n,e)$ and
$\displaystyle m\in{\mathbb{Z}}_{n}$, we define
$\displaystyle{\mathsf{Enc}}(p_{k},x)=x^{e}\in{\mathbb{Z}}_{n}$.

  * •

Decryption: For a given secret key $\displaystyle s_{k}=(n,d)$ and
$\displaystyle c\in{\mathbb{Z}}_{n}$, we define
$\displaystyle{\mathsf{Dec}}(s_{k},c)=c^{d}\in{\mathbb{Z}}_{n}$.

######  Definition 2.29 (Public key encryption).

A public key encryption scheme is a tuple
$\displaystyle\mathcal{E}=({\mathsf{Gen}},{\mathsf{Enc}},{\mathsf{Dec}})$ with
the following properties, defined over the space
$\displaystyle(\mathcal{M},\mathcal{C})$.

  * •

$\displaystyle{\mathsf{Gen}}$ is a probabilistic function which is defined by
$\displaystyle(p_{k},s_{k})={\mathsf{Gen}}(\kappa)~{}(\kappa\in\mathcal{K})$.

  * •

For a given output of $\displaystyle{\mathsf{Gen}}$ and a message
$\displaystyle m\in\mathcal{M}$, $\displaystyle{\mathsf{Enc}}$ is a
probabilistic function which output the ciphertext $\displaystyle
c={\mathsf{Enc}}(p_{k},m)\in\mathcal{C}$.

  * •

$\displaystyle{\mathsf{Dec}}$ is a deterministic function which is defined by
$\displaystyle c={\mathsf{Dec}}(s_{k},m)$, where $\displaystyle c$ is a
ciphertext and $\displaystyle m$ is either a message $\displaystyle
m\in\mathcal{M}$ or a ’rejection’ message that is distinct from all the
messages.

######  Definition 2.30 (Attack Game 6 — RSA security).

Let $\displaystyle\mathcal{E}=({\mathsf{Gen}},{\mathsf{Enc}},{\mathsf{Dec}})$
be a RSA trapdoor permutation scheme with $\displaystyle\ell>2$ (integer) and
$\displaystyle e>2$ (odd integer). For a given adversary
$\displaystyle{\mathcal{A}}$, the attack game proceeds as follows.

  * •

The challenger computes a pair of integers
$\displaystyle(n,d)={\mathsf{RSAGen}}(\ell,e)$, and outputs $\displaystyle
m\in{\mathbb{Z}}_{n}$ and $\displaystyle c=m^{d}\in{\mathbb{Z}}_{n}$. Then,
she sends the inputs $\displaystyle(n,c)$ to the adversary.

  * •

The adversary outputs $\displaystyle m^{\prime}\in{\mathbb{Z}}_{n}$.

We define $\displaystyle{\mathcal{A}}$’s advantage in breaking RSA trapdoor
permutation scheme as the probability so that $\displaystyle m^{\prime}=m$,
which is denoted by $\displaystyle{\mathsf{RSAadv}}({\mathcal{A}},\ell,e)$.

######  Definition 2.31 (RSA assumption).

For given $\displaystyle\ell>2$ (integer) and $\displaystyle e>2$ (odd
integer), we call that the RSA assumption holds if for all
$\displaystyle{\mathcal{A}}$,
$\displaystyle{\mathsf{RSAadv}}({\mathcal{A}},\ell,e)$ is negligible.

###  2.6 Key-exchange protocol

The quotient group $\displaystyle({\mathbb{Z}}/n{\mathbb{Z}})^{\times}$ is
defined by
$\displaystyle({\mathbb{Z}}/n{\mathbb{Z}})^{\times}=\\{0,\cdots,n-1\\}$, whose
order is given by the Euler’s totient function
$\displaystyle\varphi(n)=|({\mathbb{Z}}/n{\mathbb{Z}})^{\times}|$. For prime
$\displaystyle p$, $\displaystyle\varphi(p)=p-1$. The group
$\displaystyle({\mathbb{Z}}/n{\mathbb{Z}})^{\times}$ becomes cyclic if and
only if $\displaystyle n=1,2,4,p^{k}$ or $\displaystyle n=2p^{k}$ where
$\displaystyle p$ is odd prime and $\displaystyle k>0$. The quotient group
becomes the cyclic group $\displaystyle C_{n}$, that is given by

$({\mathbb{Z}}/n{\mathbb{Z}})^{\times}\cong
C_{\varphi(n)}\;,~{}\text{where}~{}\varphi(p^{k})=\varphi(2p^{k})=p^{k}-p^{k-1}\;.$
(25)

By definition, the group becomes cyclic if and only if it has a generator
$\displaystyle g$, that is, each element can be written by the powers of
$\displaystyle g$:

$C_{\varphi(n)}=\\{g^{0}\,g^{1},\cdots,g^{\varphi(n)-1}\\}\;.$ (26)

The Diffie-Hellman key-exchange protocol is briefly described as follows.

  * •

Alice computes $\displaystyle\alpha\in{\mathbb{Z}}_{q}$, $\displaystyle
u=g^{\alpha}\in C_{p-1}$, and sends the output $\displaystyle u$ to Bob.

  * •

Bob computes $\displaystyle\beta\in{\mathbb{Z}}_{q}$, $\displaystyle
v=g^{\beta}\in C_{p-1}$, and sends the output $\displaystyle v$ to Alice.

  * •

Alice computes $\displaystyle w=v^{\alpha}$ upon receiving $\displaystyle v$
from Bob.

  * •

Bob computes $\displaystyle w=u^{\beta}$ upon receiving $\displaystyle u$ from
Alice.

Then, the secret shared between them is given by

$w=v^{\alpha}=g^{\alpha\beta}=u^{\beta}\;.$ (27)

It is said that the Diffie-Hellman key-exchange protocol is secure if and only
if the following property holds:

$\text{For given}~{}g^{\alpha},g^{\beta}\in
C_{p-1}\;,\text{where}~{}\alpha,\beta\in{\mathbb{Z}}_{q},\text{it is hard to
computes}~{}g^{\alpha\beta}\in C_{p-1}\;.$ (28)

This security property is called the computational Diffie-Hellman assumption.

######  Definition 2.32 (Attack Game 7 — decisional Diffie-Hellman security).

Let $\displaystyle C_{p-1}$ be a cyclic group with $\displaystyle p$ a prime,
whose generated is written by $\displaystyle g\in C_{p-1}$. For a given
adversary $\displaystyle{\mathcal{A}}$, the Diffie-Hellman attack game
proceeds as follows. For given $\displaystyle b=0,1$:

  * •

The challenger computes $\displaystyle\alpha,\beta\in{\mathbb{Z}}_{q}$,
$\displaystyle u=g^{\alpha},v=g^{\beta}\in C_{p-1}$, and $\displaystyle
g^{\alpha\beta}\in C_{p-1}$ . and send a pair of outputs $\displaystyle(u,v)$
to the adversary. For a given $\displaystyle b=0,1$,

  * •

The adversary computes outputs some value of $\displaystyle w^{\prime}\in
C_{p-1}$.

  * •

Let $\displaystyle W_{b}$ be the event where the adversary
$\displaystyle{\mathcal{A}}$ outputs a bit $\displaystyle 1$ for a given bit
$\displaystyle b\in\\{0,\,1\\}$. We define $\displaystyle W_{1}$ be the event
when the adversary $\displaystyle{\mathcal{A}}$ wins the game, i.e.,
$\displaystyle w^{\prime}=w$.

${\mathsf{DDHadv}}({\mathcal{A}},\,C_{p-1})=\big{|}{\mathbb{P}}\left(W_{0}\right)-{\mathbb{P}}\left(W_{1}\right)\big{|}\;.$
(29)

We define $\displaystyle{\mathcal{A}}$’s advantage in solving the decisional
Diffie-Hellman problem with $\displaystyle C_{p-1}$.

######  Definition 2.33 (Decisional Diffie-Hellman (DDH) assumption).

We say that decisional Diffie-Hellman (DDH) assumption holds for
$\displaystyle C_{p-1}$ if for all efficient adversaries
$\displaystyle{\mathcal{A}}$ the value of
$\displaystyle{\mathsf{DDHadv}}({\mathcal{A}},\,C_{p-1})$ is negligible.

##  3 Quantum Cryptography

###  3.1 Qubits, Entanglement, and Quantum Gates

At the beginning, we summarize basic notions in describing for the quantum
computers and quantum cryptography. In classical computers, the fundamental
unit is a ’bit’, which can be either 0 or 1. In quantum computers, the
fundamental unit is a ’qubit’, which is a superposition of 0 and 1. In
general, a single qubit state is written as a state in the Hilbert space
$\displaystyle{\cal{H}}={\mathbb{C}}^{2}$

$\big{|}\psi\rangle=\alpha\,\big{|}0\rangle+\beta\,\big{|}1\rangle\;,$ (30)

where $\displaystyle|\alpha|^{2}+|\beta|^{2}=1$ with the basis
$\displaystyle{\mathcal{B}}_{z}=\left\\{\big{|}0\rangle,\,\big{|}1\rangle\right\\}$.
We can always make change of a basis to another one by using a unitary
transformation. The following basis are also often used

$\big{|}\pm\rangle=\frac{\big{|}0\rangle\pm\big{|}1\rangle}{\sqrt{2}}\;,$ (31)

and we denote it as
$\displaystyle{\mathcal{B}}_{x}=\left\\{\big{|}+\rangle,\,\big{|}-\rangle\right\\}$.

We can construct a $\displaystyle N$ qubit system from single qubit systems by
taking $\displaystyle N$ tensor products of the Hilbert spaces as
$\displaystyle{\cal{H}}^{\otimes N}=\otimes_{i=1}^{N}{\cal{H}}_{i}$. For
instance, 2 qubit state is spanned by 3 basis states when taking the
orthogonal conditions into account. That is, taking a tensor product of two
Hilbert spaces
$\displaystyle{\cal{H}}_{1}\otimes{\cal{H}}_{2}={\mathbb{C}}^{2}\otimes{\mathbb{C}}^{2}$,
the 2 qubit state can be expressed by

$\big{|}\psi_{1}\rangle\otimes\big{|}\psi_{2}\rangle=\big{|}\psi_{1}\psi_{2}\rangle\in{\cal{H}}_{1}\otimes{\cal{H}}_{2}\;,$
(32)

where $\displaystyle\big{|}\psi_{1}\rangle\in{\cal{H}}_{1}$ and
$\displaystyle\big{|}\psi_{2}\rangle\in{\cal{H}}_{2}$. We will often
abbreviate $\displaystyle\big{|}\psi_{1}\rangle\otimes\big{|}\psi_{2}\rangle$
to $\displaystyle\big{|}\psi_{1}\psi_{2}\rangle$, etc.

An important property in quantum information theory is the so-called,
’entanglement’, which refers to the quantum correlation between different
qubits. In order to give more formal definition to that, we define a density
operator $\displaystyle\rho$ associated to a given qubit
$\displaystyle\big{|}\psi\rangle$ as follows.

$\rho=\big{|}\psi\rangle\langle\psi\big{|}\;.$ (33)

The qubit is called a pure state if and only if the density operator satisfies
the following condition,

$\rho^{2}=\rho\;.$ (34)

Equivalently, a qubit state in the Hilbert space
$\displaystyle{\cal{H}}_{1}\otimes{\cal{H}}_{2}$ is called a pure state if it
can be expressed in the separable form:
$\displaystyle\big{|}\psi_{1}\rangle\otimes\big{|}\psi_{2}\rangle$. On the
other hand, a qubit state which cannot be written in such a separable way is
called the entangled state. The standard basis for the two qubits consists of
four orthonormal states which is called as the Bell states. The Bell states
can be expressed as follows.

$\displaystyle\displaystyle\big{|}\Psi_{1}^{\pm}\rangle$
$\displaystyle\displaystyle=$
$\displaystyle\displaystyle\frac{\big{|}01\rangle\pm\big{|}10\rangle}{\sqrt{2}}\;,$
$\displaystyle\displaystyle\big{|}\Psi_{2}^{\pm}\rangle$
$\displaystyle\displaystyle=$
$\displaystyle\displaystyle\frac{\big{|}00\rangle\pm\big{|}11\rangle}{\sqrt{2}}\;.$

These states are maximally entangled.

A unitary operator that acts on a small number of qubits (say, up to 3) is
called ’quantum gate’ (or, gate). That is a quantum analogous to the classical
gates like ’AND’, ’OR’, and ’NOT’. If we take a set of basis in the Hilbert
space $\displaystyle{\cal{H}}$, the quantum gates are defined by the outer
products

$\displaystyle\displaystyle\big{|}0\rangle\langle 0\big{|}$
$\displaystyle\displaystyle=$ $\displaystyle\displaystyle\begin{pmatrix}1&0\\\
0&0\end{pmatrix}\,,~{}~{}\big{|}0\rangle\langle 1\big{|}=\begin{pmatrix}0&1\\\
0&0\end{pmatrix}\;,$ $\displaystyle\displaystyle\big{|}1\rangle\langle
0\big{|}$ $\displaystyle\displaystyle=$
$\displaystyle\displaystyle\begin{pmatrix}0&0\\\
1&0\end{pmatrix}\,,~{}~{}\big{|}1\rangle\langle 1\big{|}=\begin{pmatrix}0&0\\\
0&1\end{pmatrix}\;.$

The Pauli matrices are examples of $\displaystyle 1$-qubit gates.

$\displaystyle\displaystyle{\mathsf{I}}$ $\displaystyle\displaystyle=$
$\displaystyle\displaystyle\big{|}0\rangle\langle
0\big{|}+\big{|}1\rangle\langle 1\big{|}\;,$
$\displaystyle\displaystyle{\mathsf{X}}$ $\displaystyle\displaystyle=$
$\displaystyle\displaystyle\big{|}0\rangle\langle
1\big{|}+\big{|}1\rangle\langle 0\big{|}\;,$
$\displaystyle\displaystyle{\mathsf{Y}}$ $\displaystyle\displaystyle=$
$\displaystyle\displaystyle-i\big{|}0\rangle\langle
1\big{|}+i\big{|}1\rangle\langle 0\big{|}\;,$
$\displaystyle\displaystyle{\mathsf{Z}}$ $\displaystyle\displaystyle=$
$\displaystyle\displaystyle\big{|}0\rangle\langle
0\big{|}-\big{|}1\rangle\langle 1\big{|}\;.$

Among those quantum gates, the bit-flip gate $\displaystyle{\mathsf{X}}$
(a.k.a., NOT-gate) negates the computational basis, i.e., it swaps
$\displaystyle\big{|}0\rangle$ and $\displaystyle\big{|}1\rangle$. The phase-
flip gate $\displaystyle{\mathsf{Z}}$ puts a minus sign in front of a qubit
state $\displaystyle\big{|}1\rangle$. Another important $\displaystyle
1$-qubit gate is the phase-shift gate, $\displaystyle{\mathsf{R}}_{\phi}$,
which merely rotate the phase of the qubit state
$\displaystyle\big{|}1\rangle$ by $\displaystyle\phi$, that is,
$\displaystyle{\mathsf{R}}_{\phi}\big{|}1\rangle=e^{i\phi}\big{|}1\rangle$.
Note that $\displaystyle{\mathsf{Z}}$ is a special case of
$\displaystyle{\mathsf{R}}_{\phi}$ with $\displaystyle\phi=\pi$. Moreover,
$\displaystyle{\mathsf{R}}_{\phi}$ gate with $\displaystyle\phi=\pi/4$ is
often called as $\displaystyle T$-gate. In practice, the most relevant
$\displaystyle 1$-qubit gate is the so-called, Hadamard gate
$\displaystyle{\mathsf{H}}$, which is given by

${\mathsf{H}}=\frac{1}{\sqrt{2}}\,\begin{pmatrix}1&1\\\ 1&-1\end{pmatrix}$
(35)

The actions of the Hadamard gate $\displaystyle{\mathsf{H}}$ on the qubits
exchange one basis to the other.

$\displaystyle\displaystyle{\mathsf{H}}\,\big{|}0\rangle$
$\displaystyle\displaystyle=$
$\displaystyle\displaystyle\big{|}+\rangle\;,\quad{\mathsf{H}}\,\big{|}1\rangle=\big{|}-\rangle\;,$
$\displaystyle\displaystyle{\mathsf{H}}\,\big{|}+\rangle$
$\displaystyle\displaystyle=$
$\displaystyle\displaystyle\big{|}0\rangle\;,\quad{\mathsf{H}}\,\big{|}-\rangle=\big{|}1\rangle\;.$

The crucial property of the Hadamard gate is that if we act it to the qubit
state with a superposition $\displaystyle\big{|}0\rangle+\big{|}1\rangle$,
then we have

${\mathsf{H}}\,\frac{1}{\sqrt{2}}\left(\big{|}0\rangle+\big{|}1\rangle\right)=\big{|}0\rangle\;.$
(36)

The result of disappearance in the initial qubit state
$\displaystyle\big{|}1\rangle$ is a result of the quantum interference.

An example of a $\displaystyle 2$-qubit gate is the controlled-not gate, CNOT.
The CNOT gate negates the second bit of its input if the first qubit is 1, and
does nothing if the first qubit is 0.

$\displaystyle\displaystyle{\mathsf{CNOT}}\,\big{|}0\rangle\otimes\big{|}b\rangle$
$\displaystyle\displaystyle=$
$\displaystyle\displaystyle\big{|}0\rangle\otimes\big{|}b\rangle\;,$
$\displaystyle\displaystyle{\mathsf{CNOT}}\,\big{|}1\rangle\otimes\big{|}b\rangle$
$\displaystyle\displaystyle=$
$\displaystyle\displaystyle\big{|}0\rangle\otimes\big{|}1-b\rangle\;.$

where $\displaystyle b=0,1$. The first qubit is called as the control qubit
and the second qubit is called as the target qubit, respectively. We can
express the CNOT gate as a matrix form by

${\mathsf{CNOT}}=\begin{pmatrix}1&0&0&0\\\ 0&1&0&0\\\ 0&0&0&1\\\ 0&0&1&0\\\
\end{pmatrix}\;.$ (37)

###  3.2 Quantum Teleportation

Now, we consider the quantum transportation, in which Alice has a qubit
$\displaystyle\big{|}\psi\rangle$ at the beginning, and she send the qubit to
Bob. Let us consider the situation where an entangled pair of qubit is shared
between Alice and Bob. Then, Alice performs a Bell measurement of the
entangled pair of qubit and a target qubit $\displaystyle\big{|}\psi\rangle$,
which is given by

$\big{|}\psi\rangle=\alpha\big{|}0\rangle+\beta\big{|}1\rangle\;,$ (38)

and suppose that they share one of the Bell states,

$\big{|}\Psi_{2}^{+}\rangle=\frac{\big{|}00\rangle+\big{|}11\rangle}{\sqrt{2}}\;.$
(39)

Then, the total state is expressed by the tensor product between
$\displaystyle\big{|}\psi\rangle$ and
$\displaystyle\big{|}\Psi_{2}^{+}\rangle$ as follows.

$\displaystyle\displaystyle\big{|}\psi\rangle\otimes\big{|}\Psi_{2}^{+}\rangle$
$\displaystyle\displaystyle=$
$\displaystyle\displaystyle\frac{1}{2}\left(\alpha\big{|}000\rangle+\beta\big{|}100\rangle+\alpha\big{|}011\rangle+\beta\big{|}111\rangle\right)$
$\displaystyle\displaystyle=$
$\displaystyle\displaystyle\frac{1}{2}\left\\{\big{|}\Psi_{2}^{+}\rangle\otimes\left(\alpha\big{|}0\rangle+\beta\big{|}1\rangle\right)+\big{|}\Psi_{2}^{-}\rangle\otimes\left(\alpha\big{|}0\rangle-\beta\big{|}1\rangle\right)\right\\}$
$\displaystyle\displaystyle+$
$\displaystyle\displaystyle\frac{1}{2}\left\\{\big{|}\Psi_{1}^{+}\rangle\otimes\left(\alpha\big{|}0\rangle+\beta\big{|}1\rangle\right)+\big{|}\Psi_{1}^{-}\rangle\otimes\left(\alpha\big{|}0\rangle-\beta\big{|}1\rangle\right)\right\\}\;.$

When Alice makes the Bell measurement, then she will have one of the four Bell
states, that can be encoded by two classical bits by

$\Psi_{2}^{+}:00\;,~{}\Psi_{2}^{-}:01\;,~{}\Psi_{1}^{+}:10\;,~{}\Psi_{1}^{-}:11\;.$
(40)

Depending on the results of the Bell measurement, Bob performs one of four
actions to his qubit and end up with the qubit
$\displaystyle\big{|}\phi\rangle$.

Measurement | Classical bit | Bob’s qubit | Quantum gate
---|---|---|---
$\displaystyle\Psi_{2}^{+}$ | $\displaystyle 00$ | $\displaystyle\alpha\big{|}0\rangle+\beta\big{|}1\rangle$ | $\displaystyle{\mathsf{I}}$
$\displaystyle\Psi_{2}^{-}$ | $\displaystyle 01$ | $\displaystyle\alpha\big{|}0\rangle+\beta\big{|}1\rangle$ | $\displaystyle{\mathsf{Z}}$
$\displaystyle\Psi_{1}^{+}$ | $\displaystyle 10$ | $\displaystyle\alpha\big{|}0\rangle+\beta\big{|}1\rangle$ | $\displaystyle{\mathsf{X}}$
$\displaystyle\Psi_{1}^{-}$ | $\displaystyle 11$ | $\displaystyle\alpha\big{|}0\rangle+\beta\big{|}1\rangle$ | $\displaystyle{\mathsf{Y}}$

In every case, Bob can end up with the correct qubit
$\displaystyle\big{|}\psi\rangle$ and the initial qubit
$\displaystyle\big{|}\psi\rangle$ for Alice has collapsed after the Bell
measurement. This process for sending a qubit from Alice to Bob is called as
quantum transportation.

Let us consider a quantum gate $\displaystyle\rho$, we can construct a von
Neumann entropy $\displaystyle S(\rho)$, which is defined by

$S(\rho)=-\operatorname{Tr}\left(\rho\ln\rho\right)\;.$ (41)

The basic properties of von Neumann entropy are summarized below.

  * •

$\displaystyle S(\rho)\geq 0\;,$

  * •

$\displaystyle S(\rho)=0\;,~{}\text{if and only if $\displaystyle\rho$ is a
pure state}\;,$

  * •

$\displaystyle S(\rho)\leq N\;,~{}~{}\text{$\displaystyle N$ is the dimension
of the Hilbert space: $\displaystyle N={\mathrm{dim}}({\cal{H}})$}\;.$

In regard to the third property, the equality holds if and only if the qubit
is maximally entangled. This means that a maximally entangled qubit is the
state which maximize the von Neumann entropy. If we consider the tensor
product Hilbert space
$\displaystyle{\cal{H}}={\cal{H}}_{1}\otimes{\cal{H}}_{2}$, and
$\displaystyle\rho_{i}~{}(i=1,2)$ be the density operators on each Hilbert
space. Then, we can define the relative (von Neumann) entropy by

$\displaystyle\displaystyle S(\rho_{1}\|\rho_{2})$
$\displaystyle\displaystyle=$
$\displaystyle\displaystyle\operatorname{Tr}\left(\rho_{1}\ln\rho_{1}\right)-\operatorname{Tr}\left(\rho_{1}\ln\rho_{2}\right)$
$\displaystyle\displaystyle=$
$\displaystyle\displaystyle\operatorname{Tr}\left[\rho_{1}\left(\ln\rho_{1}-\ln\rho_{2}\right)\right]\;.$

######  Theorem 3.1 (Holevo’s theorem).

Let us consider an $\displaystyle N$ tensor products Hilbert space
$\displaystyle{\cal{H}}={\cal{H}}_{1}\otimes\cdots\otimes{\cal{H}}_{N}$, and
$\displaystyle\rho_{i}=\big{|}\psi_{i}\rangle\langle\psi_{i}\big{|}$ where
$\displaystyle\psi_{i}\in{\cal{H}}_{i}~{}(i=1,\cdots,N)$. Suppose that any
$\displaystyle\rho_{i}~{}(i=1,\cdots,N)$ are the entangled states, and let
$\displaystyle X$ be a random variable with $\displaystyle
p_{i}={\mathbb{P}}(X=i)~{}(i=1,\cdots,N)$, and define the total density
operator $\displaystyle\rho$ as

$\rho=\sum_{i=1}^{N}p_{i}\,\rho_{i}\;,$ (42)

and $\displaystyle Y$ be the Bell measurement on $\displaystyle\rho$. Then, it
holds the following inequality

$S(\rho_{XY}\|\rho_{X}\otimes\rho_{Y})\leq\chi\;,$ (43)

where $\displaystyle\chi=S(\rho)-\sum_{i=1}^{N}p_{i}\,S(\rho_{i})$, and
$\displaystyle\chi$ is called the Holevo information.

This theorem states that there is an upper bound of the information that can
be known on a quantum state when we perform a Bell measurement.

###  3.3 Quantum Key Distribution

The goal of Quantum Key Distribution (QKD) is to provide a way to share the
secrete key between two parties, Alice and Bob. The
$\displaystyle{\mathsf{BB84}}$ protocol is one of the first examples to
realize the QKD. The basic procedures of $\displaystyle{\mathsf{BB84}}$ is
described as follows.

  1. 1.

Alice chooses a random bit and random basis using a random generator.

  2. 2.

Alice encodes the chosen bit and sends the qubit to Bob by using a quantum
channel.

  3. 3.

Bob chooses a random basis using a random generator.

  4. 4.

Bob measures the received qubit in the chosen basis and decodes the bit.

  5. 5.

If Alice and Bob have the same basis, then they can share the same bit, and if
not the case, they can only share the same bit withe a probability of 1/2, and
they can share a different bit with the same probability of 1/2.

  6. 6.

Alice and Bob repeat the steps 1 to 5 until a reasonable amount of bits have
been exchanged.

  7. 7.

After that they share the basis used for encoding and decoding for using the
classical channel.

  8. 8.

They discard every bit where the basis are not the same one, and keeps the
others without revealing the value of bits.

  9. 9.

To verify that nobody eavesdropped, they publicly share a reasonable amount of
bits and verify that they agree. If they agree on all the bits, they discard
the used bits and keep the secret key. If they disagree, they discard the
secret key and start again.

At the end of this procedure, Alice and Bob share the identical and secured
secrete key. This $\displaystyle{\mathsf{BB84}}$ protocol has a loophole when
the third part, Eve attacks to gain information on the exchanged bits. Before
explaining the loophole of the $\displaystyle{\mathsf{BB84}}$ protocol, let us
see the example of this procedure and how this protocol protects against
passive eavesdropping. In the example shown below, we abbreviates the names of
three characters by Alice, Bob, and Eve.

n | A’s bit | A’s basis | A’s qubit | E’s basis | E’s qubit | B’s bit | B’s basis | B’s qubit | Key
---|---|---|---|---|---|---|---|---|---
1 | 0 | $\displaystyle{\mathsf{Z}}$ | $\displaystyle\big{|}0\rangle$ | $\displaystyle{\mathsf{Z}}$ | $\displaystyle\big{|}0\rangle$ | 0 | $\displaystyle{\mathsf{Z}}$ | $\displaystyle\big{|}0\rangle$ | 0
2 | 0 | $\displaystyle{\mathsf{Z}}$ | $\displaystyle\big{|}0\rangle$ | $\displaystyle{\mathsf{Z}}$ | $\displaystyle\big{|}0\rangle$ | 1 | $\displaystyle{\mathsf{X}}$ | $\displaystyle\big{|}-\rangle$ |
3 | 1 | $\displaystyle{\mathsf{X}}$ | $\displaystyle\big{|}-\rangle$ | $\displaystyle{\mathsf{Z}}$ | $\displaystyle\big{|}1\rangle$ | 0 | $\displaystyle{\mathsf{X}}$ | $\displaystyle\big{|}+\rangle$ | 0
4 | 0 | $\displaystyle{\mathsf{X}}$ | $\displaystyle\big{|}+\rangle$ | $\displaystyle{\mathsf{X}}$ | $\displaystyle\big{|}+\rangle$ | 1 | $\displaystyle{\mathsf{Z}}$ | $\displaystyle\big{|}1\rangle$ |
5 | 1 | $\displaystyle{\mathsf{X}}$ | $\displaystyle\big{|}-\rangle$ | $\displaystyle{\mathsf{X}}$ | $\displaystyle\big{|}-\rangle$ | 1 | $\displaystyle{\mathsf{X}}$ | $\displaystyle\big{|}-\rangle$ | 1
6 | 1 | $\displaystyle{\mathsf{Z}}$ | $\displaystyle\big{|}1\rangle$ | $\displaystyle{\mathsf{Z}}$ | $\displaystyle\big{|}1\rangle$ | 1 | $\displaystyle{\mathsf{Z}}$ | $\displaystyle\big{|}1\rangle$ | 1
7 | 0 | $\displaystyle{\mathsf{Z}}$ | $\displaystyle\big{|}0\rangle$ | $\displaystyle{\mathsf{Z}}$ | $\displaystyle\big{|}0\rangle$ | 1 | $\displaystyle{\mathsf{X}}$ | $\displaystyle\big{|}-\rangle$ |
8 | 0 | $\displaystyle{\mathsf{Z}}$ | $\displaystyle\big{|}0\rangle$ | $\displaystyle{\mathsf{X}}$ | $\displaystyle\big{|}+\rangle$ | 0 | $\displaystyle{\mathsf{Z}}$ | $\displaystyle\big{|}0\rangle$ | 0
Table 1: An example of $\displaystyle{\mathsf{BB84}}$ protocol

If both Alice and Bob have the same basis, which correspond to $\displaystyle
n=1,3,5,6,8$, then they can share the same key, hence we only consider the
case when $\displaystyle n=1,3,5,6,8$. Let us denote
$\displaystyle{\mathcal{B}}_{A}$, $\displaystyle{\mathcal{B}}_{A}$, and
$\displaystyle{\mathcal{B}}_{A}$ the basis of Alice, Eve, and Bob,
respectively. Lets consider the case when
$\displaystyle{\mathcal{B}}_{A}={\mathcal{B}}_{B}\neq{\mathcal{B}}_{E}$. Then,
without loss of generality, we can take
$\displaystyle{\mathcal{B}}_{A}={\mathcal{B}}_{B}={\mathsf{Z}}$ and
$\displaystyle{\mathcal{B}}_{E}={\mathsf{X}}$ and that Alice ant to encode her
qubit $\displaystyle 0$. In this case, the probability to find Eve is
$\displaystyle 1/2$. After discarding the bits, we have only two possibilities
for the basis,

  1. 1.

$\displaystyle{\mathcal{B}}_{A}={\mathcal{B}}_{B}={\mathcal{B}}_{E};~{}~{}p=\frac{1}{2}$

  2. 2.

$\displaystyle{\mathcal{B}}_{A}={\mathcal{B}}_{B}\neq{\mathcal{B}}_{E};~{}~{}p=\frac{1}{2}$

Then, the probability not to find her by revealing one bit becomes

$\displaystyle\displaystyle P$ $\displaystyle\displaystyle=$
$\displaystyle\displaystyle{\mathbb{P}}({\mathcal{B}}_{A}={\mathcal{B}}_{B}={\mathcal{B}}_{E})+{\mathbb{P}}({\mathcal{B}}_{A}={\mathcal{B}}_{B}\neq{\mathcal{B}}_{E})\times{\mathbb{P}}(\text{A's
bit}=\text{B's bit})$ $\displaystyle\displaystyle=$
$\displaystyle\displaystyle\frac{1}{2}+\frac{1}{2}\times\frac{1}{2}=\frac{3}{4}\;.$

As the events are supposed to be independent each other, the probability not
to find her by giving away $\displaystyle k$-bits is given by

$P_{k}=\left(\frac{3}{4}\right)^{k}\;,$ (44)

and then the probability not to find her by giving away $\displaystyle k$-bits
becomes

$\hat{P}_{k}=1-\left(\frac{3}{4}\right)^{k}\;,$ (45)

The result shows that the more bits are giving away, the more chance to find
Eve.

##  4 Cryptographic Algorithms

The primary cryptographic algorithms of blockchain basically consist of three
types of cryptographic algorithms: cryptographic hash functions, symmetric
cryptographic algorithms, and asymmetric cryptographic algorithms. The basic
difference between symmetric cryptographic algorithms and asymmetric
cryptographic algorithms is in the way to distribute the cryptographic keys.
The use of Federal Information Processing Standard (FIPS) is approved by the
security of commerce. The National Institute of Standards and Technology
(NIST) has published a Special Publication (SP) which gives a standardization
procedure as similar to the FIPS provided by the security of commerce.

###  4.1 Cryptographic Hash Algorithms

A cryptographic hash algorithm is a cryptographic primitive algorithm that
basically map input data of any length to fixed length values. There are
basically three types of security properties in the cryptographic hash
algorithm (or hash function $\displaystyle H$).

  1. 1.

One-way function:
It is practically impossible to reverse the process from the hash value to the
input value such that $\displaystyle H(x)=y$.

  2. 2.

Weak-collision resistance:
It is practically impossible to find another distinct value of $\displaystyle
x^{\prime}$ for a given input value of $\displaystyle x$, such that the output
of hash function match $\displaystyle H(x)=H(x^{\prime})~{}(x\neq
x^{\prime})$.

  3. 3.

Strong-collision resistance:
It is practically impossible to find two distinct values of $\displaystyle x$
and $\displaystyle x^{\prime}$ in such a way that the output of hash function
match $\displaystyle H(x)=H(x^{\prime})$.

###  4.2 Symmetric Cryptographic Algorithms

Symmetric cryptographic algorithm (or secret-key algorithm) uses a single,
unique secrete-key in both encryption and decryption of the data. In order to
make this algorithm much more secured, several symmetric cryptographic
algorithms have been approved by NIST for the protection of sensitive data.
The symmetric cryptographic algorithm combined with the use of hash function
has been specified and approved in SP-800.

###  4.3 Asymmetric Cryptographic Algorithms

Asymmetric cryptographic algorithm (or public-key algorithm) uses a pair of
keys, a public-key and a private-key which are related to each other. The
public-key may be made public without reducing the security of the process,
but the private-key must remain secrete if the cryptographic protection is to
remain effective.

####  4.3.1 Digital Signatures Algorithms

Digital signatures algorithms are used to provide identity authorization,
integrity authorization, source authorization, and support for non-
repudiation. Digital signatures are used in conjunction with hash functions
The FIPS-186 specifies algorithms that are approved for the computation of
digital signatures. It specifies several types of algorithms; RSA algorithm,
the Elliptic Curve digital signature algorithm (ECDSA), and the Edwards Curve
digital signature algorithm (EdDSA). The FIPS-186 also specifies additional
requirements in each algorithms, which include the key sizes for each
algorithms, and methods for generating the key pairs.

  1. 1.

RSA scheme:
The RSA scheme is the most simple public-key algorithm, which is approved in
FIPS-186 for the generation and verification of digital signatures, and
specified in PKCS-1 and RFC-9017. Since the RSA digital signature scheme has a
mathematically hard problem, that is so called, the Integer Factorization
Problem (IFP), most of the cryptocurrencies do not use the RSA digital
signature scheme.

  2. 2.

ECDSA scheme:
The ECDSA digital signature scheme is approved and specified in FIPS-186, and
is used to generate and verify the digital signatures based on the use of
elliptic curves. Since the ECDSA digital signature scheme is more secured than
the RSA scheme. most of the major cryptocurrencies, such as Bitcoin (BTC),
Ethereum (ETH), Ripple (XRP), have adopted the ECDSA scheme.

  3. 3.

EdDSA scheme:
The EdDSA digital signature scheme is adopted in FIPS-186 and described in
RFC-8032. While the ECDSA scheme requires the use of a random (unique) value
for the generation of each signature, the EdDSA scheme is deterministic, that
is, the unique value for the generation of each signature is computed by the
private key. While it is not as widely adopted as ECDSA, some
cryptocurrencies, such as Monero (XMR), Zcash (ZEC), Stellar (XLM), have
adopted EdDSA for their digital signature algorithm.

####  4.3.2 Key Establishment Schemes

Asymmetric cryptographic algorithms are used to set up keys to be used in
communicating between entities. The scheme is a set of transformations that
provide a cryptographic service. The scheme is used in a protocol that
actually performs the communication needed for the key establishment process.
There are two types of approved key establishment schemes; discrete-log-based
scheme and integer factorization scheme. SP-800 specifies key establishment
schemes that use RSA algorithm is also approved to use for key establishment,
as well as for the generation and verification of digital signatures.

  1. 1.

Diffie-Hellman (DH) and MQV:
SP-800 specifies key establishment schemes that use discrete-log-based
algorithms. Two algorithms are approved for key agreement; Diffie-Hellman (DH)
and MQV.

  2. 2.

RSA:
RSA algorithm can be used for key establishment, as well as for the generation
and verification of digital signatures. Its use for key establishment is
specified in SP-800, it specifies approved methods for both key agreement and
key transport.

## References

  * S. Joshi, A. Choudhury, R.I. Minu (2023) S. Joshi, A. Choudhury, R.I. Minu, ’Quantum blockchain-enabled exchange protocol model for decentralized systems’, Quant.Inf.Proc. 22 (11), 404 (2023).
  * A. Naik, E. Yeniaras, G. Hellstern, G. Prasad, S. Vishwakarma (2023) A. Naik, E. Yeniaras, G. Hellstern, G. Prasad, S. Vishwakarma, ’From Portfolio Optimization to Quantum Blockchain and Security: A Systematic Review of Quantum Computing in Finance’, arXiv:2307.01155
  * D. Stebila, M. Mosca, N. Lutkenhaus (2010) D. Stebila, M. Mosca, N. Lutkenhaus, ’The Case for Quantum Key Distribution’, Quantum Communication and Quantum Networking, In: Sergienko, A., Pascazio, S., Villoresi, P. (eds) Quantum Communication and Quantum Networking. QuantumComm 2009. Lecture Notes of the Institute for Computer Sciences, Social Informatics and Telecommunications Engineering, vol 36. Springer, Berlin, Heidelberg.