# Knowledge-driven Subword Grammar Modeling for Automatic Speech Recognition
in Tamil and Kannada

Madhavaraj A11footnotemark: 1<EMAIL_ADDRESS>Bharathi
Pilar222Electrical Engineering, Indian Institute of Science
Bangalore, Karnataka, India<EMAIL_ADDRESS>Ramakrishnan A.
G.33footnotemark: 3<EMAIL_ADDRESS>
###### Abstract

In this paper, we present specially designed automatic speech recognition
(ASR) systems for the highly agglutinative and inflective languages of Tamil
and Kannada that can recognize unlimited vocabulary of words. We use subwords
as the basic lexical units for recognition and construct subword grammar
weighted finite state transducer (SG-WFST) graphs for word segmentation that
captures most of the complex word formation rules of the languages. We have
identified the following category of words (i) verbs, (ii) nouns, (ii)
pronouns, and (iv) numbers. The prefix, infix and suffix lists of subwords are
created for each of these categories and are used to design the SG-WFST
graphs. We also present a heuristic segmentation algorithm that can even
segment exceptional words that do not follow the rules encapsulated in the SG-
WFST graph. Most of the data-driven subword dictionary creation algorithms are
computation driven, and hence do not guarantee morpheme-like units and so we
have used the linguistic knowledge of the languages and manually created the
subword dictionaries and the graphs. Finally, we train a deep neural network
acoustic model and combine it with the pronunciation lexicon of the subword
dictionary and the SG-WFST graph to build the subword-ASR systems. Since the
subword-ASR produces subword sequences as output for a given test speech, we
post-process its output to get the final word sequence, so that the actual
number of words that can be recognized is much higher. Upon experimenting the
subword-ASR system with the IISc-MILE Tamil and Kannada ASR corpora, we
observe an absolute word error rate reduction of 12.39% and 13.56% over the
baseline word-based ASR systems for Tamil and Kannada, respectively.

###### keywords:

Speech recognition, Subword modeling, Deep neural network, Weighted finite
state transducers

††journal: Pattern Recognitionlabel2label2footnotetext: University College
Mangalore, Karnartaka, India

##  1 Introduction

Research in automated speech recognition (ASR) has led to significant
advancements and finds many applications in the field of industry and home
automation, mobile telephony, healthcare, defence, etc. Most of the ASR
research methodologies and techniques in the literature focusing mainly on
English and other European languages, and no significant progress has been
made for Indian languages, especially Dravidian languages such as Tamil and
Kannada. One of the main challenges in developing a automatic speech
recognition systems for these languages is the unavailability of standard
speech and text corpora, and the other reason being its complicated
morphological structure. This paper focuses on overcoming these limitations by
building a reasonably good, ASR systems for both Tamil and Kannada languages
using subword modeling.

Since the word-based ASR approach is impractical for these languages due to
the ever increasing vocabulary size, it is not possible to sufficiently cover
the large vocabulary of words without utilizing subword units [1]. The subword
modelling technique, where each word is split into two or more morpheme-like
units, decreases the out of vocabulary (OOV) rate; besides the smaller subword
vocabulary reduces the model complexity significantly. It also makes it
possible to build n-gram language models to cover millions of words [2]. It
still requires special solutions for the state-of-the-art neural network
language models [3] to train an output layer that has a vast number of
possible output symbols. DNNs trained on several thousand hours of speech have
reduced the word error rate (WER) significantly compared to the traditional
methods and achieve word-level accuracy of nearly 90% for vocabulary sizes of
about 200,000 for English [4]. Such ASR systems are now widely used for
commercial and entertainment purposes.

Various methods have been used for segmenting the word into its constituent
subwords. One of the popular techniques is the morphological analyzer that is
used for segmenting words into morphs and also to obtain other information
such as stems and part-of-speech. The morphological analyzers have been used
in works [5],[6]. Syllables and other rule-based systems have been used in
[7], [8]. Data-driven algorithms have been used in [9], [10]. In this paper,
we employ knowledge-driven approach and use the morphological rules for word
formation in constructing the subword grammar WFST which is then used in the
decoding graph of our proposed subword-based ASR.

The rest of the paper is organised a follows. Section 2 gives an overall
outline of the proposed subword modeling based ASR approach. Section 3
describes the subword dictionary construction procedure and the design of the
subword grammar WFST for word segmentation. Further, a heuristics-based
algorithm is also presented to segment exception words. In section 4, we
elaborate the procedure to create the final subword grammar WFST and subword
lexicon WFST to be used in our proposed subword-based ASR. Also, the post-
processing steps to convert the recognized subword sequence from the subword-
based ASR back to word sequence is also discussed. Section 5 presents the
experimental setup and performance of the proposed approach, followed by
conclusion and future scope of this work.

##  2 The proposed subword-based ASR approach

The block diagram illustrating the training and testing of the proposed
subword-based ASR is shown in figure 1. First, we get the vocabulary of words
from the input text corpus and create the list of prefixes, infixes and
suffixes and categorize them into different word forms to create SG-WFST based
on the word formation rules of the languages. Based on linguistic knowledge,
we have formed the following category of words: (i) verbs, (ii) pronouns,
(iii) numbers and (iv) nouns. These prefix, infix, and suffix lists of
subwords are created such that a simple string concatenation of a prefix with
one or more infixes and suffixes will form a valid Tamil word.

Next, we segment all the words in the text corpus using the SG-WFST graph, and
the exception words that cannot be segmented is now segmented using another
specially designed U-WFST graph. We then create the subword language model
WFST and subword lexicon WFST and combine them with the trained DNN-based
acoustic model to create the final decoding graph for the subword-ASR system.
This decoding graph is used during testing to decode any given test speech.
Since the subword-ASR produces a sequence of subwords, we post-process its
output using deterministic rules as explained in [11] to get the final output
word sequence. Since both Tamil and Kannada languages share almost similar
word formation rules, the word categories remains same for both the languages.

Figure 1: Block diagram of the proposed subword modeling approach for building
Tamil/Kannada ASR.

For our Kannada experiments, we have used our IISc-MILE Kannada ASR Corpus,
which has 347 hours (275 hours for training and 72 hours for testing) of data.
For the Tamil experiments, we use IISc-MILE Tamil ASR Corpus and Microsoft
Tamil data [12]. The combined Tamil dataset contains 217 hours (152 hours for
training and 65 hours for testing) of transcribed speech data. The performance
of the proposed subword-based ASR is compared with that of the baseline word-
based ASR system. We have followed the procedure illustrated in [13] to build
the baseline system. The IISc-MILE speech corpora have now been made publicly
available on OpenSLR [14, 15].

##  3 Subword grammar WFST creation and segmentation

###  3.1 WFST implementation of word segmentation using manually created
subword dictionary

Initially, we have classified the words from the text corpus into 5
categories, namely, (i) past tense verbs, (ii) present and future tense verbs,
(iii) nouns, (iv) pronouns and (v) numbers. This categorization is based on
the linguistic knowledge of tense, number, person, gender, case, mood, and
voice markers in Tamil and Kannada languages. We have analysed these five
categories and divided each word into prefix, infix and suffix. The words are
partitioned in such a way that the original word can be obtained by performing
a simple string concatenation of the constituent subwords.

Word segmentation based on morphology involves the tedious task of
constructing the subword grammar graphs which needs hard coding of a lot of
grammar rules. However, the proposed approach of segmenting a word into its
constituent prefix (modified form of root) and infix/suffixes (morphemes) has
the following advantages: (i) It does not require hard coding of grammar rules
during post-processing (ii) It does not involve modifications for lexicon
preparation.

Creating a subword list for words formed out of verb roots: In our framework,
we have created two different sub-categories having distinct verb roots for
the same verb for the words formed with (i) past tense markers and (ii) future
and present tense markers. Since many other markers can be combined along with
the tense markers to form valid words, we have carefully segregated the
infixes and suffixes and sequentially ordered them to construct a flowchart
such that there will be at least one valid path for most of the words that can
be formed with the given root verb prefix. In figure 2, we have shown the
flowchart that forms most of the words having an example past tense verb root
prefix (*B /keetta/ , meaning “asked” in English). For simplicity, we have
only given a handful of infix and suffix subwords in the flowchart. We see
from this figure that we have taken care of the ordering of infixes that can
be added to the verb root by cascading two sets of infixes and placing them
between the prefix and suffix lists [16, 17]. This configuration is
particularly useful when building lexicon graph to be used in our subword ASR,
since it reduces the space and time when performing graph search during
decoding.

Figure 2: Flowchart illustrating the rules to generate valid words that can be
formed with an example past tense verb root *B /keetta/ in Tamil Figure 3:
Flowchart illustrating the rules to generate valid words that can be formed
from a present/future tense verb root *B /sei/ in Tamil

Figure 3 shows the flowchart that forms present/future tense words that are
derived from a single example verb root prefix (*B /sei/, meaning “do” in
English). With these flowcharts shown in figures 2 and 3, we can generate not
only verbs but adjectives, nouns, infinitives, etc., that can be derived from
the given set of verb root prefixes.

Similar flowcharts for Kannada language are shown. Figure 4 shows the
flowchart that forms most of the words having the past tense verb root prefix
( *B /maadi/, meaning “do” in English). In figure 5, we show the flowchart
that forms present/future tense words that are derived from the example verb
root prefix (*B /oodu/, meaning “read” in English) [18].

Figure 4: Flowchart illustrating the rules to generate valid words from an
example Kannada past tense verb root *B /maadi/ , meaning ’to do’ in English
Figure 5: Flowchart illustrating the rules to generate valid words from an
example Kannada present/future tense verb root *B /oodu/ (means ’to read’).

Creating subword list for words formed out of noun roots: Similar to verbs, we
have created a list of possible prefixes, infixes and suffixes for nouns. We
have employed the morphological rules given in [19] for pruning the nouns to
create the noun prefix list to be used in constructing the graph. The
flowchart in figure 6 shows the Tamil words that can be formed from the noun
(*B /isai/ , meaning “music” in English).

Figure 6: Flowchart illustrating the rules to generate valid derived words
from an example Tamil noun root word *B /isai/

A similar flowchart is shown for Kannada in figure 7, with the rules that form
words from the noun *B /mane/, meaning “house” in English).

Figure 7: Flowchart illustrating the rules to generate valid derived words
from an example Kannada noun root word *B /mane/

Creating subword list for words formed out of pronoun roots: The list of
suffixes is almost the same for pronouns and nouns. Since no literature is
available describing the rules for creating prefix list for pronouns, we have
created a custom list of prefixes so that it can be incorporated in our
framework. Figure 8 shows the flowchart for generating words that can be
formed from the two pronoun roots *B /en/ and *B /nam/ (meaning “my” and “our”
in English), respectively).

Figure 8: Flowchart illustrating the rules to generate valid words that can be
formed with the Tamil pronoun root words *B /en/ and *B /nam/. (Note that all
possible prefixes for these roots have been added to the prefix list.)

The same observation is true for Kannada. Figure 9 shows the flowchart for
deriving words from the two pronoun roots *B /nanna/ and *B /namma/ (meaning
“my” and “our” in English, respectively).

Figure 9: Flowchart illustrating the rules to derive valid words for two
Kannada pronoun root words *B /nanna/ and *B /namma/.

Creating subword list for words formed out of number roots: In the case of
Tamil words formed from number root prefixes, in addition to inflexion, we
need to handle agglutination. This has been performed by pruning some of the
prefixes and including them in the infix list.

This pruning is performed based on our knowledge of the rules for numeric word
formation. Figure 10 shows the flowchart that can generate all the words that
can be formed from an example number word (*B /aindhu/, meaning “five” in
English).

Figure 10: An example flowchart illustrating the rules to generate valid words
that can be formed from an example Tamil number root word *B /aindhu/ (meaning
five in English) with all possible prefixes added to the prefix list.

Similarly we have created flowcharts for the numbers in Kannada. Figure 11
shows the flowchart that can generate all the words that can be formed from an
example number word *B /koti/, meaning “crore” in English).

Figure 11: Flowchart illustrating the rules in Kannada to generate valid words
that can be formed from the number root *B /koti/ with all possible suffixes
added to the suffix list.

It is to be noted that, although we have used only five categories of words,
other words belonging to adjectives, adverbs, infinitives, etc., categories
can also be handled by our subword-ASR using the subword dictionary which we
have manually created, if the lexicon WFST is constructed according to the
manner explained as explained in section 4.

###  3.2 WFST implementation of word segmentation using manually created
subword dictionary

The first step is to construct the subword grammar WFST (SG-WFST) using the
flowcharts shown in figures 2-11 as templates independently for each language.
SG-WFST contains five subgraphs, one for each of the categories of words.
(i.e., past tense verbs, present/future tense verbs, nouns, pronouns and
numbers). This graph contains a single loop state to which the start and end
nodes of the five subgraphs are connected through the transitions with
$\epsilon$ labels at both input and output as shown in figure 12. Each
subgraph is a cascade of prefix, infix and suffix lists with appropriate skip
transitions between them.

Figure 12: Template of the manual subword weighted finite state transducer
(SG-WFST) showing the subgraphs of the five categories connected to the loop
state from both ends.

Figure 13 and 14 shows an example WFST subgraph for pronoun category, for
Tamil and Kannada respectively, which is a cascade of a set of smaller
subgraphs of prefixes and suffixes. Every path from the start to the end state
of the pronoun prefix subgraph contains a set of left-to-right transitions
whose input labels are the characters in the subword that the path encodes and
the output labels are the pronoun prefix subword string in the last transition
and $\epsilon$ labels for the rest of the transitions. Similar structure is
followed for pronoun suffix subgraphs as well, whose start state will be the
end state of pronoun prefix subgraph, as shown in figure 13 and 14. Thus, we
form SG-WFST by connecting the subgraphs of all the five categories in
parallel.

Figure 13: The pronoun subgraph for Tamil which is used in the construction of
SG-WFST. This graph is constructed using the flowchart shown in figure 8.

Figure 14: The pronoun subgraph for Kannada which is used in the construction
of SG-WFST. This graph is constructed using the flowchart shown in figure 8.

In the second step, for each of the words in the vocabulary $\mathbb{V}$, we
construct a W-WFST which contains only one path having unique start and end
states. The input label for the first transition of the path is the word $w$
and $\epsilon$ for the rest of the transitions, while the output labels are
the individual characters of $w$ as shown in figure 15 for an example Tamil
and Kannada word.

Figure 15: W-WFST for an example (a) Tamil word *B /varugiraan/ and (b)
Kannada word *B /baruva/.

Next, each of these W-WFSTs are composed with SG-WFST individually and the
resulting WFST has only one path from the start to the end state. The output
labels along this path provide the sequence of subwords segmented for the
given word.

###  3.3 Construction of U-WFST to handle unsegmented words

It is to be noted that not all the words in the vocabulary can be segmented
using this method since SG-WFST has been manually created with a finite number
of subwords. Due to agglutination and OOV issues, some of the words in the
vocabulary do not follow the word formation rules encapsulated in the SG-WFST.
However, we try our best to automatically segment such words with a new graph
(named U-WFST) using some heuristic knowledge and assumptions.

First, we we take the segmentation sequences of all the words in the
vocabulary that can be segmented using the method explained in subsection 3.2.
Next, we add context identification markers (“+”) to every subword in the
segments to identify whether they are prefixes, infixes, suffixes or singleton
subwords [11]. Prefix subwords have markers only at the end of the string;
suffix subwords have markers only at the beginning; infixes have markers at
both the ends; whereas, singleton subwords have no markers. Figure 16 show
some example Tamil words, their segmented subword sequences and context
markers added to the subwords.

Figure 16: Illustration of segmentation of some sample Tamil words and
addition of context markers to the segmented subwords based on their category.

Then we replace all the words in the text corpus by their context-marked
segmentation sequences. Then, we create the dictionary of context-marked
subwords (say $\mathbb{D}^{+}$) and calculate the unigram probability of their
occurrences in the text corpus and create a list of 2-tuples
$\\{(s,\phi(s)):\forall s\in\mathbb{D}^{+}\\}$. We then create another list of
2-tuples which contains all the individual characters of the language with a
very small ($\delta$) weight associated with each of them. These two lists are
merged to form the final list of 2-tuples (expressed in equation 1) to be used
as labels and weights when constructing the U-WFST graph.

$\mathbb{F}=\\{(s,\phi(s)):\forall
s\in\mathbb{D}^{+}\\}\;\;\bigcup\;\;\\{(c,\delta):\forall c\in\mathbb{C}\\}$
(1)

where $\mathbb{C}$ is the set of all valid characters of the language and the
value of $\delta$ is chosen as 0.0001.

Finally, we create the U-WFST by having one loop state and creating an unique
path for each entry in the list $\mathbb{F}$ starting and ending in the loop
state. The input labels for the transitions along a path are the individual
characters of the subword, and the output labels are the subword string for
the last transition and $\epsilon$ labels for the rest of the transitions. The
weight of a path encoding the subword $s$ (or $c$) is set accordingly as
$\phi(s)$ (or $\delta$) as shown in figure 17a.

Figure 17: Handling unsegmented words: (a) Template of U-WFST. (b) W-WFST for
an example unsegmented word *B /ikkaalathil/. (c) possible segmentation paths
obtained when composing (b) and (a). (d) optimal segmentation path chosen
based on the proposed criteria. (e) segmentation obtained after merging
contiguous 1-length subwords. (f) context markers added to the subword
segments.

Segmentation using U-WFST and optimal subword sequence selection: Next, we
create W-WFSTs for all the unsegmented words and compose them with U-WFST. The
resulting WFST obtained has many possible segmentation paths, out of which we
choose the optimal one and prune the segments based on the following criteria.

  * 1.

Criterion 1:  Merge contiguous segments if they are 1-character length
subwords.

  * 2.

Criterion 2:  Consider only those paths where all the intermediate segments
(whose individual lengths are more than 1) start and end with the context
marker “+”.

  * 3.

Criterion 3:  If there are many such paths satisfying criteria 1 and 2, the
path which has the maximum weight is chosen.

  * 4.

Criterion 4:  For a given word, if there is no such path satisfying the above
criteria, then we consider the whole word as one subword unit and add it to
the subword dictionary (in the independent category).

We avoid the problem of over-segmentation of words by keeping a very low value
for $\delta$ (so that the joint weight of the over-segmented subword sequence
is very low) and the choice of the selection criteria. Figure 17b-f shows an
example unsegmented word being segmented using U-WFST and how we select the
best possible segmentation path. Thus, using both SG-WFST and U-WFST, we are
able to segment any given word to subwords.

##  4 Creation of n-gram subword language model and lexicon WFST for the
proposed subword-ASR system

In this section, we describe the way to use subwords as vocabulary units and
pre-process the original text corpus and learn n-gram subword language model
(LM) and use it in our subword-ASR system. Since subword-ASR system uses
subwords as vocabulary units, the first step is to segment the words in the
transcription text and the LM text corpus into subwords using the segmentation
technique explained in section 3. We then add context-dependent markers to the
segmented subwords based on their category. N-gram subword LM is then learnt
from the segmented LM text corpus. In all our subword-ASR experiments, we have
used $6^{th}$ order LM to learn the grammar of subword units. In normal ASRs,
$3^{rd}$ order word-level LM is used. In our case, since each word is split
into $2$ to $4$ subwords, only by increasing the subword LM order to $6$, we
would match the performance and learn the grammar context of the $3^{rd}$
order word-level LM.

To create subword lexicon WFST, we first create the lists of prefixes,
infixes, suffixes and singleton words in past-tense verb, future/present-tense
verb, noun, pronoun, number and independent categories. Then, we construct the
lexicon WFST using the same template as SG-WFST, except that the input labels
are context-independent phones rather than characters. In addition, another
subgraph for independent category is included. The pronunciation dictionary is
created for every entry in the subword list using grapheme-to-phoneme (G2P)
converters that we have built [20]. Figure 18 shows a sample lexicon WFST
created for Tamil. It can be seen that by carefully designing the flow of
transitions in the graph, we can encapsulate the word formation rules of the
language so that a huge number of words can be recognized (after due post-
processing) using this lexicon WFST.

Figure 18: Lexicon WFST created for an example context-marked subword
dictionary $\mathbb{D^{+}}$ to be used in Tamil subword modeling ASR

Finally, we use the training set of the IISc-MILE ASR corpus to train the DNN
acoustic model (AM) with the same procedure explained in [13]. This DNN AM is
combined with the subword lexicon and language model WFSTs to create the
decoding graph which we use for decoding the utterances from the test set.

The subword-ASR produces a sequence of subwords as output for a given
utterance. Hence we need to post-process it to get a valid sequence of words.
Post-processing is done by concatenating the subwords having the context
markers (“+”) at either sides of the point of concatenation. Next, we remove
all the context markers from the concatenated string to get the final post-
processed word sequence which is then used to compute the WER. For the purpose
of comparison, and to illustrate the benefits of subword-ASR for
Tamil/Kannada, we have considered only the words in the training corpus to
build the lexicon for the baseline word-based ASR system. Hence its OOV and
WER on the test set are higher.

##  5 Experimental setup and results

In this section we compare the performance of our proposed subword-ASR with
respect to the baseline word-based ASR system for subword LMs of different
orders. The performance of subword-based ASRs is compared with the baseline
word-based ASRs in terms of OOV rate and WER to illustrate the significance of
subword modeling to handle highly agglutinative languages like Tamil and
Kannada.

The language models are learnt from a large text corpus of 4.4 million Tamil
words and 8 million Kannada words. The size of dictionary of words that we
have used in building our Tamil and Kannada baseline word-based ASR systems
are 182771 and 201055, respectively. For, the subword-ASR systems, the Tamil
and Kannada subword dictionaries that we have manually created contain 43856
and 58098 words, respectively.

Table 1: Comparison of the word error rates (WER) and out of vocabulary (OOV) rates of the subword-ASR system for Tamil language. Method | Word Error Rate (%) | OOV
---|---|---
3-gram LM | 4-gram LM | 5-gram LM | 6-gram LM
Baseline | 24.70 | -NA- | -NA- | -NA- | 10.73
Manual method | 18.04 | 15.93 | 14.12 | 12.31 | 1.68
Table 2: Comparison of the word error rates (WER) and out of vocabulary (OOV) rates of the subword-ASR system for Kannada language. Method | Word Error Rate (%) | OOV
---|---|---
3-gram LM | 4-gram LM | 5-gram LM | 6-gram LM
Baseline | 21.95 | -NA- | -NA- | -NA- | 8.64
Manual method | 12.97 | 10.27 | 9.47 | 8.39 | 1.12

Tables 1 and 2 compare the WER performance of the proposed subword ASR systems
for subword LMs of different orders, with the baseline method. We have also
listed the OOV rates to further justify the effectiveness of the subword
modeling. OOV rate is defined as the ratio of number of words in the test
corpus which are not present in the training corpus to the total number of
words in the test corpus.

Since the subword dictionary creation and word segmentation methods have been
carefully handcrafted to handle the agglutination and inflexion of Tamil and
Kannada words, this method gives the best WER of 12.31% which is an absolute
improvement of 12.39% over the baseline word-level ASR system in the case of
Tamil, whereas best WER of 8.39% (an absolute improvement of 13.56% over the
baseline word-level ASR system) is obtained for Kannada. However, the OOV
rates of 1.68% and 1.12% for Tamil and Kannada languages, respectively, arise
due to proper nouns and other uncommon words present in the test set. Such
words can also be easily handled by the ASR when they are included in the
independent category without any additional manual effort.

##  6 Conclusion and future work

In this paper, we have presented a novel design for Tamil and Kannada ASR
systems based on subword modeling by manually creating the subword dictionary
and using to design a specialized SG-WFST for word segmentation purpose. We
have used linguistic knowledge and identified the following category of words
(i) verbs, (ii) pronouns, (iii) numbers and (iv) nouns to create the prefix,
infix and suffix lists to design the SG-WFST that capture the word formation
rules of Tamil and Kannada. Experiments conducted on the IISc-MILE ASR corpus
validate the significance of the proposed subword-ASR system in bringing down
the OOV and WER by a huge margin.

The proposed SG-WFST creation and segmentation technique finds application not
only in ASR but also in other areas of natural language processing. It can be
used for applications like lemmatization, parts-of-speech tagging, text
translation and transliteration, by simply changing the input and output
labels of the graph. The same approach is also very useful for correction of
the recognized text in the case of printed or handwritten text recognition
systems, since they have the same issue of having to deal with unlimited word-
vocabulary.

## References

  * Hirsimaki et al. [2009] T. Hirsimaki, J. Pylkkonen, M. Kurimo,  Importance of high-order n-gram models in morph-based speech recognition,  IEEE Trans. Audio, Speech, and Language Processing 17 (2009) 724–732.
  * Varjokallio et al. [2016] M. Varjokallio, M. Kurimo, S. Virpioja,  Class n-gram models for very large vocabulary speech recognition of finnish and estonian,  in: Int. Conf. Stat. Lang. Speech Process., Springer, 2016, pp. 133–144.
  * Enarvi and Kurimo [2016] S. Enarvi, M. Kurimo,  Theanolm-an extensible toolkit for neural network language modeling,  arXiv preprint arXiv:1605.00942 (2016).
  * Hinton et al. [2012] G. Hinton, L. Deng, D. Yu, G. E. Dahl, A.-r. Mohamed, N. Jaitly, A. Senior, V. Vanhoucke, P. Nguyen, T. N. Sainath, et al.,  Deep neural networks for acoustic modeling in speech recognition: The shared views of four research groups,  IEEE Sig. Process. Mag. 29 (2012) 82–97.
  * Hirsimäki et al. [2006] T. Hirsimäki, M. Creutz, V. Siivola, M. Kurimo, S. Virpioja, J. Pylkkönen,  Unlimited vocabulary speech recognition with morph language models applied to finnish,  Computer Speech & Language 20 (2006) 515–541.
  * Byrne et al. [2000] W. Byrne, J. Hajič, P. Ircing, P. Krbec, J. Psutka,  Morpheme based language models for speech recognition of czech,  in: International Workshop on Text, Speech and Dialogue, Springer, 2000, pp. 211–216.
  * Erdogan et al. [2005] H. Erdogan, O. Buyuk, K. Oflazer,  Incorporating language constraints in sub-word based speech recognition,  in: IEEE Workshop on Automatic Speech Recognition and Understanding, 2005., IEEE, 2005, pp. 98–103.
  * Laureys et al. [2002] T. Laureys, V. Vandeghinste, J. Duchateau,  A hybrid approach to compounds in lvcsr,  in: VII Int. Conf. Spoken Language Processing, 2002\.
  * Hacioglu et al. [2003] K. Hacioglu, B. Pellom, T. Ciloglu, O. Ozturk, M. Kurimo, M. Creutz,  On lexicon creation for turkish lvcsr,  in: Eighth European Conf. Speech Communication and Tech., 2003.
  * Arısoy et al. [2007] E. Arısoy, H. Sak, M. Saraçlar,  Language modeling for automatic turkish broadcast news transcription,  in: Eighth Annual Conf. Int. Speech Communication Assoc., 2007.
  * Smit et al. [2017] P. Smit, S. Virpioja, M. Kurimo,  Improved subword modeling for WFST-based speech recognition,  in: 18th Ann. Conf. Int. Speech Communication Assoc. (INTERSPEECH 2017), 2017, pp. 2551–2555.
  * mic [2018] Data provided by SpeechOcean.com and Microsoft, Microsoft, 2018.
  * Madhavaraj and Ramakrishnan [2017] A. Madhavaraj, A. G. Ramakrishnan,  Design and development of a large vocabulary, continuous speech recognition system for Tamil,  in: 2017 14th IEEE India Council International Conference (INDICON), IEEE, 2017, pp. 1–5.
  * mil [2022a] Openslr: Iisc mile kannada asr corpus, 2022a. URL: http://www.openslr.org/126/.
  * mil [2022b] OpenSLR: IISc MILE Tamil ASR corpus, 2022b. URL: http://www.openslr.org/127/.
  * Sarveswaran et al. [2018] K. Sarveswaran, G. Dias, M. Butt,  ThamizhiFST: a morphological analyser and generator for Tamil verbs,  in: 2018 3rd Int. Conf. Inf. Tech. Res. (ICITR), 2018, pp. 1–6.
  * Agesthialingom [1971] S. Agesthialingom,  A note on Tamil verbs,  in: Anthropological Linguistics, volume 13, 1971, pp. 121–125.
  * Prathibha and Padma [2013] R. Prathibha, M. Padma,  Development of morpholoical analyzer for kannada verbs (2013).
  * Lushanthan et al. [2014] S. Lushanthan, A. R. Weerasinghe, D. L. Herath,  Morphological analyzer and generator for Tamil language,  in: 2014 14th Int. Conf. Adv. ICT for Emerging Regions (ICTer), 2014, pp. 190–196.
  * Ramakrishnan and Narayana [2007] A. Ramakrishnan, M. L. Narayana,  Grapheme to phoneme conversion for tamil speech synthesis,  in: Proc. Workshop in Image and Signal Processing (WISP-2007), IIT Guwahati, 2007, pp. 96–99.


# Entropically secure encryption
with faster key expansion

Mehmet Hüseyin Temel and Boris Škorić Part of this work was supported by the
Dutch Startimpuls NAQT KAT-2 and NGF Quantum Delta NL KAT-2.

###### Abstract

Entropically secure encryption is a way to encrypt a large plaintext with a
small key and still have information-theoretic security, thus in a certain
sense circumventing Shannon’s result that perfect encryption requires the key
to be at least as long as the entropy of the plaintext. Entropically secure
encryption is not perfect, and it works only if a lower bound is known on the
entropy of the plaintext. The typical implementation is to expand the short
key to the size of the plaintext, e.g. by multiplication with a public random
string, and then use one-time pad encryption. This works in the classical as
well as the quantum setting. In this paper, we introduce a new key expansion
method that is faster than existing ones. We prove that it achieves the same
security. The speed gain is most notable when the key length is a sizeable
fraction of the message length. In particular, a factor of 2 is gained in the
case of approximate randomization of quantum states.

###### Index Terms:

Approximate quantum encryption, entropic security, key expansion, one-time
pad,

††publicationid: pubid:

##  I Introduction

###  I-A Entropic Security

An encryption scheme is called perfect if the ciphertext reveals no
information whatsoever about the plaintext. For perfect encryption of
classical plaintexts, the length of the key needs to be at least the entropy
of the plaintext, and the simplest cipher is the One-Time Pad (OTP) or Vernam
cipher [1]. In the quantum setting, perfect encryption of an $n$-qubit
plaintext state requires a key length of $2n$ bits and the simplest cipher
achieving this kind of encryption is the Quantum One-Time Pad (QOTP) [2, 3,
4].

If one does not aim for perfect security, it is possible to get information-
theoretic guarantees about the encryption even with shorter keys, as long as a
lower bound is known on the min-entropy of the plaintext. The notion of
$(t,\varepsilon)$-entropic security has been introduced [5, 6], stating that
the adversary’s advantage in guessing any function of the plaintext is upper
bounded by $\varepsilon$ if the min-entropy of the plaintext (conditioned on
Eve’s side information) is at least $t$. It can be seen as an information-
theoretic version of semantic security. It has been shown that
$(t,\varepsilon)$-entropically secure encryption of an $n$-(qu)bit plaintext
can be achieved with key length $n-t+2\log{\textstyle\frac{1}{\varepsilon}}$
[6, 7, 8]. In the quantum case, the $t$ can become negative when Eve’s quantum
memory is entangled with the plaintext state.

The standard way to perform entropically secure encryption is to expand the
short key to a pseudorandom string which is then used as the key for (Q)OTP
encryption. The key expansion is done either using small-bias spaces or by
universal hashing with a public random string.

###  I-B Contribution and Outline

We introduce a new key expansion method for entropically secure encryption,
both classical and quantum. The main idea is to append a pseudorandom string
$f(k)$ to the short key $k$, instead of creating an entirely new string from
$k$. For the computation of $f(k)$, we use finite-field multiplication with a
public random string.

  * •

Our key expansion is faster than all previous constructions while achieving
the shortest known key length $n-t+2\log{\textstyle\frac{1}{\varepsilon}}$. In
particular, a factor of 2 in speed is gained in the unentangled quantum case
without further assumptions on Eve and the entropy of the plaintext.

  * •

Our security proof in the quantum case is a bit more straightforward than [8],
as we avoid expanding states in the Pauli basis.

The outline of the paper is as follows. We discuss related work on entropic
security in Section II. We present the relevant definitions and lemmas from
the literature in Section III. In Section IV, we present our classical scheme
and its security proof. Then in Section V, we do the same for the quantum
scheme, additionally giving an analysis of the computational complexity of the
key expansion, especially in the unentangled case in Section VI. Finally, in
Section VII, we comment on possible improvements.

##  II Related work

###  II-A Entropic Security for Classical Plaintext

The entropic security notion and its definition for encryption were coined
first by Russell and Wang [5]. They showed that it is possible to encrypt a
high-entropy $n$-bit plaintext using a key shorter than $n$ such that an
attacker has less than $\varepsilon$ advantage in predicting predicates of the
plaintext. Such schemes are called Entropically Secure Encryption (ESE)
schemes. They provided an ESE with key length
$n-t+3\log{\textstyle\frac{1}{\varepsilon}}+{\mathcal{O}}(1)$, where $t$ is
the min-entropy of the plaintext.

Dodis and Smith [6] gave a stronger definition by considering all functions of
the plaintext instead of only predicates. They also showed the equivalence
between ESE and indistinguishability (in terms of statistical distance) of
ciphertexts. They introduced two simple constructions, one of which uses XOR-
universal hash functions and improves the key length to
$n-t+2\log{\textstyle\frac{1}{\varepsilon}}+{\mathcal{O}}(1)$. They proved
that the key length of any ESE needs to be at least $n-t$ bits.

Fehr and Schaffner [9] introduced a classical indistinguishable encryption
scheme secure against quantum adversaries. It has key length $n-t+2\log
n+2\log{\textstyle\frac{1}{\varepsilon}}+{\mathcal{O}}(1)$, where $t$ is the
collision entropy of the (classical) plaintext given Eve’s quantum side
information. Different from [5, 6] they used collision entropy in the security
definition instead of min-entropy.

###  II-B Entropic Security in the Quantum Setting

In order to perfectly encrypt any $n$-qubit state, the necessary and
sufficient key length is $2n$ bits [2, 3, 4]. In its simplest form, quantum
one-time pad (QOTP) encryption and decryption work by applying to each
individual qubit a Pauli operation from the set
$\\{\mathbb{1},\sigma_{x},\sigma_{y},\sigma_{z}\\}$. The choice of Pauli
operations constitutes the key. For someone who does not know this key, the
state after encryption equals the fully mixed state regardless of the
plaintext state.

Entropic security has been generalized to the fully quantum setting where both
the plaintext and ciphertext are quantum states. Desrosiers [7] introduced
definitions of entropic security and entropic indistinguishability for quantum
ciphers. Similar to the classical setting, these definitions are equivalent up
to parameter changes. He also introduced a scheme with a key length of
$n-t+2\log{\textstyle\frac{1}{\varepsilon}}$ using a similar key expansion
method as [6]. Here $t$ is the min-entropy of the plaintext quantum state. The
analysis in [7] applies only if Eve is not entangled with the plaintext.
Desrosiers and Dupuis [8] generalized the analysis, with conditional quantum
min-entropy as defined by Renner [10], and showed that the results hold even
with entanglement.111 The conditional quantum min-entropy of an $n$-qubit
system ranges between $-n$ and $n$. A maximally entangled state has
conditional min-entropy $t=-n$.  They also proved a minimum required key
length of $n-t-1$.

###  II-C Approximate Randomization

The quantum setting without entanglement ($t\geq 0$) is a special case that
has received a lot of attention by itself, as it occurs naturally: It
corresponds to the situation where Alice prepares a plaintext state and
encrypts it. As long as the plaintext state is generated entirely by Alice (as
opposed to being received by Alice as part of a larger protocol), Eve is not
entangled with it. In the literature, this special case goes by the name
approximate randomization or approximate quantum encryption. Hayden et al.
[11] showed that approximate randomization is possible with a key length of
$n+\log n+2\log{\textstyle\frac{1}{\varepsilon}}$ by using sets of random
unitaries.222 They also provided a result for the $\infty$-norm, with key
length $n+\log n+2\log{\textstyle\frac{1}{\varepsilon}}+\log 134$; unitaries
are drawn from the Haar measure. This was later improved to
$n+2\log{\textstyle\frac{1}{\varepsilon}}+\log 150$ by Aubrun [12]. Ambainis
and Smith [13] introduced far more efficient schemes that work with a
pseudorandom sequence which selects Pauli operators as in the QOTP. In one of
them, they expanded the key using small-bias sets and achieve key length
$n+2\log n+2\log{\textstyle\frac{1}{\varepsilon}}$. This scheme is length-
preserving, i.e. the cipherstate consists of $n$ qubits. In another
construction, they expanded the key by multiplying it with a random binary
string of length $2n$; this string becomes part of the cipherstate. The key
length is reduced to $n+2\log{\textstyle\frac{1}{\varepsilon}}$. Dickinson and
Nayak [14] improved the small-bias based scheme of [13] and achieved key
length $n+2\log{\textstyle\frac{1}{\varepsilon}}+4$. Škorić and de Vries [15]
described a pseudorandom QOTP scheme that has key length
$n+2\log{\textstyle\frac{1}{\varepsilon}}$, but they need an exponentially
large common random string to be stored. Table I shows an overview of these
results.

TABLE I: Results on approximate randomization of $n$ qubits

|  Key length $\ell$ |  Ciphertext length |  Randomization process
---|---|---|---
[11] | $n+\log n+2\log{\textstyle\frac{1}{\varepsilon}}$ |  $n$ qubits |  Random unitaries (non-Haar, e.g. Pauli)
[13] | $n+2\log n+2\log{\textstyle\frac{1}{\varepsilon}}$ |  $n$ qubits |  Pseudorandom QOTP based on small-bias sets. Key expansion takes ${\mathcal{O}}(n^{2})$ operations.
[13] | $n+2\log{\textstyle\frac{1}{\varepsilon}}$ |  $n$ qubits + $2n$ bits |  Pseudorandom QOTP based on multiplication in GF$(2^{2n})$. Key expansion takes $\approx 6n\log_{3}n$ operations.
[14] | $n+2\log{\textstyle\frac{1}{\varepsilon}}+4$ |  $n$ qubits |  Pseudorandom QOTP based on small-bias spaces. Key expansion takes ${\cal O}(n^{2}\log n)$ operations.
[15] | $n+2\log{\textstyle\frac{1}{\varepsilon}}$ |  $n$ qubits |  Pseudorandom QOTP based on huge Common Reference String.
This work | $n+2\log{\textstyle\frac{1}{\varepsilon}}$ |  $n$ qubits + $2n$ bits |  Pseudorandom QOTP based on affine function in GF($2^{\ell}$). Key expansion takes $\approx 3n\log_{3}n$ operations.

The security is in terms of the trace distance: $\|{\rm cipherstate}-\mbox{\rm
fully mixed state}\|_{1}\leq\varepsilon$. The listed complexity for the finite
field
multiplications is based on the fastest known implementation and shows only
the number of AND operations. (See Section VI)

The ‘$\varepsilon$-close to fully mixed’ property can be expressed as a
distance with respect to different norms, e.g. the $1$-norm (trace norm) or
the $\infty$-norm (maximum absolute eigenvalue). In this paper, we consider
only the $1$-norm, since it expresses the distinguishability of states and it
is a universally composable measure of security [16, 17, 18].

##  III Preliminaries

###  III-A Notation; Entropic Quantities

Random variables are written in uppercase and their realizations in lowercase.
The statistical distance between random variables $X,Y\in{\mathcal{X}}$ is
given by $\Delta(X,Y)={\textstyle\frac{1}{2}}\sum_{a\in{\mathcal{X}}}|{\rm
Pr}[X=a]-{\rm Pr}[Y=a]|$. Expectation over a random variable $X$ is written as
${\mathbb{E}}_{x}$. The Rényi entropy of order $\alpha$ (with $\alpha\neq 1$)
is defined as ${\sf H}_{\alpha}(X)=(1-\alpha)^{-1}\log\sum_{x}{\rm
Pr}[X=x]^{\alpha}$. Special cases are the collision entropy ${\sf
H}_{2}(X)=-\log(\sum_{x}{\rm Pr}[X=x]^{2})$ and the min-entropy ${\sf H}_{\rm
min}(X)={\sf H}_{\infty}(X)=-\log(\max_{x}{\rm Pr}[X=x])$.

We denote the space of density matrices on Hilbert space ${\mathcal{H}}$ as
${\mathcal{D}}({\mathcal{H}})$. The single-qubit Hilbert space is denoted as
${\mathcal{H}}_{2}$. A bipartite state comprising subsystems ‘A’ and ‘B’ is
written as $\rho^{\rm AB}\in{\mathcal{D}}({\mathcal{H}}_{\rm
A}\otimes{\mathcal{H}}_{\rm B})$. The state of a subsystem is obtained by
taking the partial trace over the other subsystem, e.g. $\rho^{\rm A}={\rm
Tr}\,_{\\!\rm B}\,\rho^{\rm AB}$. The identity operator on ${\mathcal{H}}$ is
denoted by $\mathbb{1}_{\mathcal{H}}$; we will simply write $\mathbb{1}$ when
the Hilbert space is clear from the context. Similarly, we write
$\tau^{\mathcal{H}}$ for the fully mixed state $\mathbb{1}_{\mathcal{H}}/{\rm
dim}({\mathcal{H}})$, often omitting the superscript. Let $M$ be an operator
with eigenvalues $\lambda_{i}$. The Schatten $1$-norm of $M$ is given by
$\|M\|_{1}={\rm Tr}\,\sqrt{M^{{\dagger}}M}=\sum_{i}|\lambda_{i}|$. The trace
distance between states $\rho,\sigma$ is $\|\rho-\sigma\|_{\rm
tr}={\textstyle\frac{1}{2}}\|\rho-\sigma\|_{1}$.

In the literature, there are multiple definitions of quantum conditional Rényi
entropy. We will work with the definition of [19], which is based on
sandwiched relative entropy, and which has been shown in [20] to possess the
most favorable properties. Let $\rho,\sigma\geq 0$ with $\rho\neq 0$, and
$\alpha\in(0,1)\cup(1,\infty)$. The sandwiched quantum Rényi relative entropy
is given by

$\displaystyle D_{\alpha}(\rho||\sigma)\stackrel{{\scriptstyle\rm
def}}{{=}}\frac{1}{\alpha-1}\log{\rm
Tr}\,\Big{[}\Big{(}\sigma^{{\textstyle\frac{1-\alpha}{2\alpha}}}\rho\,\sigma^{{\textstyle\frac{1-\alpha}{2\alpha}}}\Big{)}^{\alpha}\Big{]}$
(1)

if $\sigma\gg\rho\,\vee\,(\alpha<1\wedge\rho\not\perp\sigma)$, and otherwise
$D_{\alpha}(\rho||\sigma)=\infty$. Here $\sigma\gg\rho$ denotes that $\sigma$
dominates $\rho$, i.e. that the kernel of $\sigma$ is contained in the kernel
of $\rho$. For $\alpha\in(0,1)\cup(1,\infty)$ and $\rho^{\rm
AE}\in{\mathcal{D}}({\mathcal{H}}_{A}\otimes{\mathcal{H}}_{E})$, the
conditional quantum Rényi entropy is given by

${\sf H}_{\alpha}(A|E)_{\rho}\stackrel{{\scriptstyle\rm
def}}{{=}}-\inf_{\sigma\in{\mathcal{D}}({\mathcal{H}}_{E})}D_{\alpha}(\rho^{\rm
AE}||\mathbb{1}_{A}\otimes\sigma).$ (2)

In the limit $\alpha\to\infty$ this reproduces the conditional Rényi entropy
as introduced by Renner [10],

${\sf H}_{\rm
min}(A|E)_{\rho}=\sup_{\sigma\in{\mathcal{D}}({\mathcal{H}}_{E})}-\log\min\\{\lambda\,|\,\lambda\mathbb{1}_{A}\otimes\sigma-\rho^{\rm
AE}\geq 0\\}.$ (3)

###  III-B Security Definitions and Useful Lemmas

######  Definition III.1 (Classical encryption scheme)

A classical encryption scheme for a message space ${\mathcal{X}}$ with key
space ${\mathcal{K}}$ and ciphertext space ${\mathcal{C}}$ consists of three
algorithms $({\sf Gen,Enc,Dec})$. Gen is a probabilistic algorithm that
outputs a key $k\in{\mathcal{K}}$. The Enc:
${\mathcal{K}}\times{\mathcal{X}}\to{\mathcal{C}}$ is a possibly randomized
algorithm that takes a key $k$ and a message $x\in{\mathcal{X}}$ and outputs a
ciphertext $c\in{\mathcal{C}}$. The Dec:
${\mathcal{K}}\times{\mathcal{C}}\to{\mathcal{X}}$ is the decryption algorithm
that takes a key $k\in{\mathcal{K}}$ and a ciphertext $c\in{\mathcal{C}}$ as
inputs and outputs a message $x\in{\mathcal{X}}$. It must hold that
$\forall_{k\in{\mathcal{K}},x\in{\mathcal{X}}}{\sf Dec}(k,{\sf Enc}(k,x))=x$.

Entropic security of an encryption scheme is formulated as the property that
the encryption Enc hides all functions of the plaintext $X$. ‘Hiding’ means
that an adversary ${\mathcal{A}}$ who sees the ciphertext has no advantage in
guessing function values $f(X)$ over an adversary ${\mathcal{A}}^{\prime}$ who
does not observe the ciphertext. Here the function $f$ is fixed before
${\mathcal{A}}$ observes the ciphertext. This is phrased in [6] as: ‘$Y$ leaks
no a priori information about $X$’.

######  Definition III.2 (Hiding all functions)

A probabilistic map $Y$ is said to hide all functions of $X$ with leakage
$\varepsilon$ if

$\forall_{\mathcal{A}}\exists_{{\mathcal{A}}^{\prime}}\forall_{f}\quad\Big{|}{\rm
Pr}[{\mathcal{A}}(Y(X))=f(X)]-{\rm
Pr}[{\mathcal{A}}^{\prime}()=f(X)]\Big{|}\leq\varepsilon.$ (4)

######  Definition III.3 (Entropic security in the classical setting, Def.1 in
[6])

A probabilistic map is $Y$ called $(t,\varepsilon)$-entropically secure if

$\displaystyle{\sf H}_{\rm min}(X)\geq t\implies$ $\displaystyle Y\mbox{ hides
all functions of }X$ (5) $\displaystyle\mbox{with leakage }\varepsilon.$

An encryption scheme is $(t,\varepsilon)$-entropically secure if
$Y(\cdot)={\sf Enc}(K,\cdot)$ satisfies Def. III.3. The definition is similar
to semantic security, but it works with unbounded adversaries and is
restricted to high-entropy plaintext.

It has been shown that entropic security implies statistical
indistinguishability and vice versa, with small modifications in the $t$ and
$\varepsilon$ parameter. Indistinguishability is defined by the existence of a
variable $G$ such that a ciphertext resulting from random $X$ (from some
distribution) and random $K$ is $\varepsilon$-close to $G$ in terms of
statistical distance.

######  Definition III.4 (Entropic indistinguishability in the classical
setting, Def.2 in [6])

333 In [6] the name ‘indistinguishability’ is used. Ref. [8] sharpened the
naming to ‘entropic indistinguishability’ to emphasize the condition on the
entropy.

A randomized map $Y$ is called $(t,\varepsilon)$-indistinguishable if

$\exists_{G}\quad{\sf H}_{\rm min}(X)\geq
t\implies\Delta(Y(X),G)\leq\varepsilon.$ (6)

######  Lemma III.5 (Paraphrased from [6])

Let $t\geq 2\log{\textstyle\frac{1}{\varepsilon}}-5$. Then
$(t-2,8\varepsilon)$-indistinguishability implies $(t,\varepsilon)$-entropic
security for all functions.

######  Lemma III.6 (Claim 2 in [21])

Let $D$ be a distribution on a finite set ${\mathcal{S}}$. If the collision
probability of $D$ is at most $(1+2\varepsilon^{2})/|{\mathcal{S}}|$, then $D$
is at a statistical distance at most $\varepsilon$ from the uniform
distribution.

######  Definition III.7 (Quantum encryption scheme)

A quantum encryption scheme with quantum message space ${\mathcal{H}}$,
classical key space ${\mathcal{K}}$, and quantum ciphertext space
${\mathcal{H}}^{\prime}$ consists of a triplet $({\sf Gen},{\sf Enc},{\sf
Dec})$. Gen is a probabilistic algorithm that outputs a key
$k\in{\mathcal{K}}$. The
Enc$:{\mathcal{K}}\times{\mathcal{D}}({\mathcal{H}})\to{\mathcal{D}}({\mathcal{H}}^{\prime})$
is a (possibly randomized) algorithm that takes as input a classical key
$k\in{\mathcal{K}}$ and a quantum state
$\varphi\in{\mathcal{D}}({\mathcal{H}})$, and outputs a quantum state
$\omega={\sf Enc}(k,\varphi)\in{\mathcal{D}}({\mathcal{H}}^{\prime})$ called
the cipherstate. ${\sf
Dec}:{\mathcal{K}}\times{\mathcal{D}}({\mathcal{H}}^{\prime})\to{\mathcal{D}}({\mathcal{H}})$
is an algorithm that takes as input a key $k\in{\mathcal{K}}$ and a state
$\omega\in{\mathcal{D}}({\mathcal{H}}^{\prime})$, and outputs a state ${\sf
Dec}(k,\omega)\in{\mathcal{D}}({\mathcal{H}})$. It must hold that
$\forall_{k\in{\mathcal{K}},\varphi\in{\mathcal{D}}({\mathcal{H}})}\;{\sf
Dec}(k,{\sf Enc}(k,\varphi))=\varphi$.

Note that Def. III.7 allows the cipherstate space to be larger than the
plaintext space, $\dim{\mathcal{H}}^{\prime}>\dim{\mathcal{H}}$. We will be
working with the special case where the cipherstate consists of a quantum
state of the same dimension as the input, accompanied by classical
information.

The effect of the encryption, with the key unknown to the adversary, can be
described as a completely positive trace-preserving (CPTP) map
$R:{\mathcal{D}}({\mathcal{H}})\to{\mathcal{D}}({\mathcal{H}}^{\prime})$ as
follows,

$R(\varphi)=\sum_{k\in{\mathcal{K}}}\frac{1}{|{\mathcal{K}}|}{\sf
Enc}(k,\varphi).$ (7)

If the plaintext state is entangled with Eve (E), e.g. the state is
$\varphi^{\rm AE}$, then the encryption and decryption act only on the A
subspace; we write $R(\rho^{\rm AE})$ for $(R\otimes\mathbb{1}_{E})(\rho^{\rm
AE})$. The definition of entropic security is more involved than in the
classical case.

######  Definition III.8 (Strong entropic security in the quantum setting,
Def.4 in [8])

An encryption system $R$ is called strongly $(t,\varepsilon)$-entropically
secure if for all states $\varphi^{\rm AE}$ satisfying ${\sf H}_{\rm
min}(A|E)_{\varphi}\geq t$, all interpretations $\\{(p_{i},\sigma_{i}^{\rm
AE})\\}$ of $\varphi^{\rm AE}$, all adversaries ${\mathcal{A}}$ and all
functions $f$, it holds that

$\Big{|}\Pr[{\mathcal{A}}(R(\sigma_{i}^{\rm
AE}))=f(i)]-\Pr[{\mathcal{A}}(R(\varphi^{\rm
A})\otimes\sigma_{i}^{E})=f(i)]\Big{|}\leq\varepsilon.$ (8)

Here ‘interpretation’ means $\varphi^{\rm AE}=\sum_{i}p_{i}\sigma^{\rm
AE}_{i}$. Def. III.8 implies another definition of entropic security given in
[8] that contains an adversary ${\mathcal{A}}^{\prime}$ who gets access only
to the own subsystem $\sigma_{i}^{\rm E}$. Similar to the classical case, the
equivalence has been shown between entropic security and entropic
indistinguishability in the quantum setting.

######  Definition III.9 (Entropic indistinguishability in the quantum
setting, Def.3 in [8])

An encryption system
$R:{\mathcal{D}}({\mathcal{H}}_{A})\to{\mathcal{D}}({\mathcal{H}}_{A^{\prime}})$
is called $(t,\varepsilon)$-indistinguishable if

$\displaystyle\exists_{\Omega^{\rm
A^{\prime}}\in{\mathcal{D}}({\mathcal{H}}_{A^{\prime}})}{\sf H}_{\rm
min}(A|E)_{\varphi}$ $\displaystyle\geq t$ $\displaystyle\implies$
$\displaystyle\|R({\varphi}^{AE})-\Omega^{\rm
A^{\prime}}\otimes\varphi^{E}\|_{1}\leq\varepsilon.\quad$ (9)

######  Lemma III.10 (Theorem 1 in [8])

$(t-1,\varepsilon/2)$-entropic indistinguishability implies strong
$(t,\varepsilon)$-entropic security for all functions.

######  Lemma III.11 (Lemma 5.1.3 in [10])

Let $S$ be a Hermitian operator and $\sigma$ a nonnegative operator. It holds
that

$\big{\|}S\big{\|}_{1}\leq\sqrt{{\rm Tr}\,(\sigma){\rm
Tr}\,(S\sigma^{-1/2}S\sigma^{-1/2})}.$ (10)

###  III-C The Quantum One Time Pad (QOTP)

Let ${\mathcal{H}}_{2}$ denote the Hilbert space of a qubit. Let $Z$ and $X$
be single-qubit Pauli operators, in the standard basis given by
$Z={1\;\phantom{-}0\choose 0\;-1}$ and $X={0\;1\choose 1\;0}$. For QOTP
encryption of one qubit, the key consists of two bits $s,q\in\\{0,1\\}$. The
encryption of a state $\varphi\in{\mathcal{D}}({\mathcal{H}}_{2})$ is given by
$X^{s}Z^{q}\varphi Z^{q}X^{s}$. Decryption is the same operation as
encryption, but with the order of applying the $Z^{q}$ and $X^{s}$
interchanged.

The simplest way to encrypt an $n$-qubit state
$\varphi\in{\mathcal{D}}({\mathcal{H}}_{2}^{\otimes n})$ is to encrypt each
qubit independently. The QOTP key $\beta$ has length $2n$ and can be expressed
as $\beta=s\|q$, with $s,q\in\\{0,1\\}^{n}$. In the rest of the paper we will
use the following shorthand notation for the QOTP cipherstate,

$F_{\beta}(\varphi)=U_{\beta}\varphi U_{\beta}^{{\dagger}}\quad\mbox{where
}U_{\beta}=\bigotimes_{i=1}^{n}X^{s_{i}}Z^{q_{i}}.$ (11)

Let ${\mathcal{H}}_{A^{\prime}}={\mathcal{H}}_{A}={\mathcal{H}}_{2}^{\otimes
n}$ and let $\varphi^{\rm
AE}\in{\mathcal{D}}({\mathcal{H}}_{A}\otimes{\mathcal{H}}_{E})$ be a bipartite
state. Encryption of the A subsystem is written as
$F_{\beta}(\varphi^{AE})=(U_{\beta}\otimes\mathbb{1}^{E})\varphi^{\rm
AE}(U_{\beta}^{{\dagger}}\otimes\mathbb{1}^{E})$. For any $\varphi^{\rm AE}$
it holds that

$\frac{1}{2^{2n}}\sum_{\beta\in\\{0,1\\}^{2n}}F_{\beta}(\varphi^{AE})=\tau^{\rm
A^{\prime}}\otimes\varphi^{\rm E},$ (12)

i.e. Def. III.9 is achieved with $t=-n$ and $\varepsilon=0$: no matter how
entangled E is with A, from the adversary’s point of view the $A^{\prime}$
subsystem is fully mixed and entirely decoupled from E.

##  IV Our results on entropically secure classical encryption

We present a modification of Ambainis and Smith’s second construction in [13].
The difference lies in the hash function, which in our case consists of the
concatenation of the short key $k$ with an affine function of $k$. In Section
IV-B we show that the key length as a function of the security parameter
$\varepsilon$ is essentially the same as in [13]. We comment on the speed gain
in Section VI.

###  IV-A The Construction

Our construction has message space ${\mathcal{X}}=\\{0,1\\}^{n}$, key space
${\mathcal{K}}=\\{0,1\\}^{\ell}$ (with $\ell\leq n$) and ciphertext space
${\mathcal{C}}=\\{0,1\\}^{2n}$. Let $\lambda=\max\\{\ell,n-\ell\\}$. Let
$u\in\\{0,1\\}^{\lambda}$, $v\in\\{0,1\\}^{n-\lambda}$. We define a hash
function $h$ as follows,

$h_{uv}(k)\stackrel{{\scriptstyle\rm def}}{{=}}k\|(uk+v)_{\rm lsb}$ (13)

where $\|$ denotes string concatenation. The addition and multiplication in
the expression $uk+v$ take place in GF$(2^{\lambda})$; the subscript ‘lsb’
denotes taking the $n-\ell$ least significant bits in case $\lambda>n-\ell$.
Note that $(uk+v)_{\rm lsb}=(uk)_{\rm lsb}+v$. The encryption is randomized,
with uniformly random strings $u,v$ which become part of the ciphertext,

${\sf Enc}_{uv}(k,x)=\big{(}u,v,x\oplus h_{uv}(k)\big{)}.$ (14)

Here $\oplus$ stands for bitwise xor. The decryption is

${\sf Dec}\big{(}k,(c_{1},c_{2},c_{3})\big{)}=c_{3}\oplus h_{c_{1},c_{2}}(k).$
(15)

###  IV-B Security Proof

###### Theorem IV.1

Our classical encryption scheme described in Section IV-A satisfies

$\displaystyle{\rm Pr}[{\sf Enc}_{UV}(K,X)$ $\displaystyle=$
$\displaystyle{\sf Enc}_{U^{\prime}V^{\prime}}(K^{\prime},X^{\prime})]$ (16)
$\displaystyle\leq$ $\displaystyle 2^{-2n}(1+2^{n-\ell-{\sf H}_{2}(X)}).$

Proof: To start, due to the prepended $u,v$ in (14) we get
$U^{\prime}V^{\prime}=UV$ and we acquire an overall factor $2^{-n}$ from ${\rm
Pr}[UV=U^{\prime}V^{\prime}]=2^{-n}$. Next, we need to bound the expression
${\rm Pr}[X\oplus h_{UV}(K)=X^{\prime}\oplus h_{UV}(K^{\prime})]$, which we
can rewrite as ${\rm Pr}[X\oplus X^{\prime}=h_{UV}(K)\oplus
h_{UV}(K^{\prime})]$ $=\sum_{a\in\\{0,1\\}^{n}}{\rm Pr}[X\oplus
X^{\prime}=a]{\rm Pr}[h_{UV}(K)\oplus h_{UV}(K^{\prime})=a]$. The $a=0$ term
yields a contribution ${\rm Pr}[K^{\prime}=K]{\rm
Pr}[X^{\prime}=X]=2^{-\ell}{\rm Pr}[X^{\prime}=X]$.

$\displaystyle{\rm Pr}[U^{\prime}V^{\prime}=UV]{\rm Pr}[X\oplus
h_{UV}(K)=X^{\prime}\oplus h_{UV}(K^{\prime})]$
$\displaystyle=2^{-n}\Big{(}2^{-\ell}{\rm Pr}[X^{\prime}=X]$
$\displaystyle\quad+\sum_{\stackrel{{\scriptstyle a\in\\{0,1\\}^{n}}}{{a\neq
0}}}{\rm Pr}[X\oplus X^{\prime}=a]{\rm Pr}[h_{UV}(K)\oplus
h_{UV}(K^{\prime})=a]\Big{)}$

For the $a\neq 0$ part of the summation we split up $a$ as $a=a_{L}||a_{R}$
with $a_{L}\in\\{0,1\\}^{\ell}$, $a_{R}\in\\{0,1\\}^{n-\ell}$ and write

$\displaystyle\sum_{\stackrel{{\scriptstyle a\in\\{0,1\\}^{n}}}{{a\neq
0}}}{\rm Pr}[X\oplus X^{\prime}=a]{\rm Pr}[h_{UV}(K)\oplus
h_{UV}(K^{\prime})=a]$ $\displaystyle=\\!\\!\\!\\!\\!\sum_{(a_{L},a_{R})\neq
0}\\!\\!\\!\\!\\!{\rm Pr}[X\oplus X^{\prime}=a]{\rm Pr}[K\oplus
K^{\prime}=a_{L}]{\rm Pr}[(Ua_{L})_{\rm lsb}=a_{R}]$
$\displaystyle=\sum_{\stackrel{{\scriptstyle a_{L}\neq 0}}{{a_{R}}}}{\rm
Pr}[X\oplus X^{\prime}=a]{\rm Pr}[K\oplus K^{\prime}=a_{L}]{\rm
Pr}[(Ua_{L})_{\rm lsb}=a_{R}].$

The last equality follows from that fact that $a_{L}=0$ implies $Ua_{L}=0$ and
hence $a_{R}=0$, while $(a_{L},a_{R})=(0,0)$ is not part of the summation;
hence $a_{L}=0$ drops from the summation. Next, we note that $K\oplus
K^{\prime}$ is uniform on $\\{0,1\\}^{\ell}$, yielding ${\rm Pr}[K\oplus
K^{\prime}=a_{L}]=2^{-\ell}$ and that $(Ua_{L})_{\rm lsb}$ for $a_{L}\neq 0$
is uniform on $\\{0,1\\}^{n-\ell}$, yielding ${\rm Pr}[(Ua_{L})_{\rm
lsb}=a_{R}]=2^{-(n-\ell)}$. Combining all these results we get

$\displaystyle{\rm Pr}[{\sf Enc}_{UV}(K,X)={\sf
Enc}_{U^{\prime}V^{\prime}}(K^{\prime},X^{\prime})]$
$\displaystyle=2^{-n}\Big{(}2^{-\ell}{\rm
Pr}[X^{\prime}=X]+2^{-n}\sum_{a_{L}\neq 0}\sum_{a_{R}}{\rm Pr}[X\oplus
X^{\prime}=a]\Big{)}$ $\displaystyle=2^{-n}\Big{(}2^{-\ell}{\rm
Pr}[X^{\prime}\\!=\\!X]+2^{-n}[1\\!-\\!\sum_{a_{R}}{\rm Pr}[X\oplus
X^{\prime}\\!=\\!0||a_{R}]]\Big{)}$ $\displaystyle\leq
2^{-2n}(1+2^{n-\ell-{\sf H}_{2}(X)})$ (19)

where we have used that ${\sf H}_{2}(X)=-\log{\rm Pr}[X^{\prime}=X]$.
$\square$

###### Theorem IV.2

Let $t\geq 2\log\frac{1}{\varepsilon}-5$. Let the key length be set as
$\ell=n-t+2\log\frac{1}{\varepsilon}-5$. Then the encryption scheme of Section
IV-A is $(t,\varepsilon)$-entropically secure.

Proof: Setting $\ell=n-t+2\log\frac{1}{\varepsilon}-5$ in (16) yields a
collision probability upper bound of $2^{-2n}(1+2\tilde{\varepsilon}^{2})$,
with $\tilde{\varepsilon}=8\varepsilon\sqrt{2^{[t-2]-{\sf H}_{2}(X)}}$. Thus,
according to Lemma III.6 and Def. 3, our scheme has $(t-2,8\varepsilon)$
entropic indistinguishability.444 Note that ${\sf H}_{2}(X)\geq{\sf H}_{\rm
min}(X)$.  Finally we invoke Lemma III.5 for the implication of
$(t,\varepsilon)$-entropic security. $\square$

##  V Our results on entropically secure quantum encryption

Our construction for encrypting $n$ qubits is very similar to the classical
construction. The difference lies in the use of the QOTP instead of classical
OTP, and in the length of the expanded key which is now $2n$ instead of $n$.

###  V-A The Construction

The message space is ${\mathcal{D}}({\mathcal{H}}_{2}^{\otimes n})$. The key
space is ${\mathcal{K}}=\\{0,1\\}^{\ell}$. Let
$\lambda=\max\\{\ell,2n-\ell\\}$. The ciphertext space is
$\\{0,1\\}^{2n-\ell+\lambda}\times{\mathcal{D}}({\mathcal{H}}_{2}^{\otimes
n})$. Let $u\in\\{0,1\\}^{\lambda}$ and $v\in\\{0,1\\}^{2n-\ell}$. We define a
hash function $b$ as

$b(k,u,v)=k\|(uk+v)_{\rm lsb}.$ (20)

Here the multiplication and addition in $uk+v$ are GF$(2^{\lambda})$
operations. The subscript ‘lsb’ (Least Significant Bits) stands for taking the
last $2n-\ell$ bits of the string; in the finite field representation, this
corresponds to taking a polynomial in $x$ modulo $x^{2n-\ell}$. Instead of
$(uk+v)_{\rm lsb}$ we can also write $(uk)_{\rm lsb}+v$.

Let $\varphi\in{\mathcal{D}}({\mathcal{H}}_{2}^{\otimes n})$. The encryption
step draws random $u,v$ and outputs $n$ qubits as well as the $u,v$,

${\sf Enc}_{uv}(k,\varphi)=\Big{(}u,v,F_{b(k,u,v)}(\varphi)\Big{)}$ (21)

with $F$ the QOTP encryption as defined in (11) and $b(\cdot,\cdot,\cdot)$ as
defined by (20). Decryption is essentially the same as encryption,

${\sf
Dec}\big{(}k,(u,v,\tilde{\varphi})\big{)}=F_{b(k,u,v)}(\tilde{\varphi}).$ (22)

###  V-B Security Proof

Let ${\mathcal{H}}_{A}={\mathcal{H}}_{2}^{\otimes n}$ and let Eve be entangled
with the plaintext state. The joint state is $\varphi^{\rm
AE}\in{\mathcal{D}}({\mathcal{H}}_{A}\otimes{\mathcal{H}}_{E})$. As discussed
in Section III-C, the encryption Enc acts only on the ‘A’ subsystem. As the
parameters $u,v$ are public we focus on the quantum part of the ciphertext.
From Eve’s point of view, the state after encryption is

$R_{uv}(\varphi^{\rm AE})\stackrel{{\scriptstyle\rm
def}}{{=}}\frac{1}{2^{\ell}}\sum_{k\in\\{0,1\\}^{\ell}}F_{b(k,u,v)}(\varphi^{\rm
AE}).$ (23)

###### Lemma V.1

It holds that

${\mathbb{E}}_{v}R_{uv}(\varphi^{\rm AE})=\tau^{\rm A}\otimes\varphi^{\rm E}.$
(24)

Proof: We write ${\mathbb{E}}_{v}R_{uv}(\varphi^{\rm
AE})={\mathbb{E}}_{kv}F_{b(k,u,v)}(\varphi^{\rm AE})$. Next,
${\mathbb{E}}_{kv}F_{b(k,u,v)}(\varphi^{\rm
AE})={\mathbb{E}}_{\beta\in\\{0,1\\}^{2n}}F_{\beta}(\varphi^{\rm
AE})=\tau^{\rm A}\otimes\varphi^{\rm E}$. The first equality follows from the
fact that for any fixed $u$, the $k$ and $v$ together can create any string in
$\\{0,1\\}^{2n}$ in precisely one way. The second equality is due to the fact
that the QOTP is completely randomizing (12). $\square$

###### Lemma V.2

Let $f$ be any (possibly operator-valued) function acting on $\\{0,1\\}^{2n}$.
It holds that

$\displaystyle{\mathbb{E}}_{kk^{\prime}uv}f(b(k,u,v))f(b(k^{\prime},u,v))=2^{-\ell}{\mathbb{E}}_{\beta}f(\beta)f(\beta)$
$\displaystyle\quad\quad+{\mathbb{E}}_{\beta\beta^{\prime}}f(\beta)f(\beta^{\prime})-2^{-\ell}{\mathbb{E}}_{kgg^{\prime}}f(k\|g)f(k\|g^{\prime}).\quad\quad\quad$
(25)

Here $\beta,\beta^{\prime}\in\\{0,1\\}^{2n}$, and ${\mathbb{E}}_{\beta}$
stands for $2^{-2n}\sum_{\beta}$. Similarly,
$g,g^{\prime}\in\\{0,1\\}^{2n-\ell}$ and ${\mathbb{E}}_{g}$ stands for
$2^{\ell-2n}\sum_{g}$.

Proof: We use shorthand notation $g=(uk+v)_{\rm lsb}$,
$g^{\prime}=(uk^{\prime}+v)_{\rm lsb}$ and we write $f_{x}$ instead of $f(x)$.
We omit the $\|$ in the expression $k\|g$. In this notation the left hand side
of (25) is ${\mathbb{E}}_{kk^{\prime}uv}f_{kg}f_{k^{\prime}g^{\prime}}$.

$\displaystyle{\mathbb{E}}_{kk^{\prime}uv}f_{kg}f_{k^{\prime}g^{\prime}}$
$\displaystyle=\frac{1}{|{\mathcal{K}}|^{2}}\sum_{k}{\mathbb{E}}_{uv}f_{kg}f_{kg}+\frac{1}{|{\mathcal{K}}|^{2}}\sum_{kk^{\prime}:k\neq
k^{\prime}}{\mathbb{E}}_{uv}f_{kg}f_{k^{\prime}g^{\prime}}$
$\displaystyle\stackrel{{\scriptstyle(a)}}{{=}}\frac{1}{|{\mathcal{K}}|}{\mathbb{E}}_{\beta}f_{\beta}f_{\beta}+\frac{1}{|{\mathcal{K}}|^{2}}\sum_{kk^{\prime}:k\neq
k^{\prime}}{\mathbb{E}}_{gg^{\prime}}f_{kg}f_{k^{\prime}g^{\prime}}$ (26)
$\displaystyle=\frac{1}{|{\mathcal{K}}|}{\mathbb{E}}_{\beta}f_{\beta}f_{\beta}+\frac{1}{|{\mathcal{K}}|^{2}}\sum_{kk^{\prime}}{\mathbb{E}}_{gg^{\prime}}f_{kg}f_{k^{\prime}g^{\prime}}-\frac{1}{|{\mathcal{K}}|^{2}}\sum_{k}{\mathbb{E}}_{gg^{\prime}}f_{kg}f_{kg^{\prime}}$
$\displaystyle=\frac{1}{|{\mathcal{K}}|}{\mathbb{E}}_{\beta}f_{\beta}f_{\beta}+{\mathbb{E}}_{\beta\beta^{\prime}}f_{\beta}f_{\beta^{\prime}}-\frac{1}{|{\mathcal{K}}|}{\mathbb{E}}_{k}{\mathbb{E}}_{gg^{\prime}}f_{kg}f_{kg^{\prime}}.\qquad\qquad$
(27)

In step (a) we used in the first term that summation over
$k\in\\{0,1\\}^{\ell}$ and $v\in\\{0,1\\}^{2n-\ell}$ exactly corresponds to
summation over $\beta\in\\{0,1\\}^{2n}$; in the second term we used that (for
$k^{\prime}\neq k$) averaging over $(u,v)$ exactly corresponds to averaging
over $(g,g^{\prime})$. The latter is obvious in the case
$u\in\\{0,1\\}^{2n-\ell}$ ($\lambda=2n-\ell$), as the ‘lsb’ in $(uk)_{\rm
lsb}$ can be omitted. In the case $u\in\\{0,1\\}^{\ell}$ ($\lambda=\ell$), the
$(u,v)$-summation covers the $(g.g^{\prime})$-space exactly an integer number
($2^{2\ell-2n}$) of times. This is seen as follows. When the two equations
$g=(uk+v)_{\rm lsb}$, $g^{\prime}=(uk^{\prime}+v)_{\rm lsb}$ are added, the
$v$ disappears and we get $[u(k+k^{\prime})]_{\rm lsb}=g+g^{\prime}$, which
has $2^{\ell}/2^{2n-\ell}$ solutions $u$. Then, at fixed
$k,k^{\prime},g,g^{\prime},u$ the solution for $v$ is unique. $\square$

###### Theorem V.3

Our encryption scheme described in Section V-A satisfies

${\mathbb{E}}_{uv}\Big{\|}R_{uv}(\varphi^{\rm AE})-\tau^{A}\otimes\varphi^{\rm
E}\Big{\|}_{1}\leq\sqrt{2^{n-\ell-{\sf H}_{2}(A|E)_{\varphi}}}.$ (28)

$\displaystyle{\mathbb{E}}_{uv}\|R_{uv}(\varphi^{\rm
AE})-\tau^{A}\otimes\varphi^{\rm E}\|_{1}$ (29)
$\displaystyle\quad\quad\stackrel{{\scriptstyle\rm
Lemma~{}\ref{lemma:rennerineq}}}{{\leq}}{\mathbb{E}}_{uv}\sqrt{{\rm
Tr}\,\sigma}\sqrt{{\rm Tr}\,[R_{uv}(\varphi^{\rm
AE})\sigma^{-{\textstyle\frac{1}{2}}}-\tau^{A}\otimes\varphi^{\rm
E}\sigma^{-{\textstyle\frac{1}{2}}}]^{2}}$ (30)
$\displaystyle\quad\quad\stackrel{{\scriptstyle\rm Jensen}}{{\leq}}\sqrt{{\rm
Tr}\,\sigma}\sqrt{{\rm Tr}\,{\mathbb{E}}_{uv}[R_{uv}(\varphi^{\rm
AE})\sigma^{-{\textstyle\frac{1}{2}}}-\tau^{A}\otimes\varphi^{\rm
E}\sigma^{-{\textstyle\frac{1}{2}}}]^{2}}$ (31)
$\displaystyle\quad\quad\stackrel{{\scriptstyle\rm
Lemma~{}\ref{lemma:EvRistau}}}{{=}}\sqrt{{\rm Tr}\,\sigma}\sqrt{{\rm
Tr}\,{\mathbb{E}}_{uv}[R_{uv}(\varphi^{\rm
AE})\sigma^{-{\textstyle\frac{1}{2}}}]^{2}-{\rm
Tr}\,[\tau^{A}\otimes\varphi^{\rm
E}\sigma^{-{\textstyle\frac{1}{2}}}]^{2}}\quad$ (32)
$\displaystyle\quad\quad=\sqrt{{\rm Tr}\,\sigma}\sqrt{{\rm
Tr}\,{\mathbb{E}}_{kk^{\prime}uv}F_{b(kuv)}(\varphi^{\rm
AE})\sigma^{-{\textstyle\frac{1}{2}}}F_{b(k^{\prime}uv)}(\varphi^{\rm
AE})\sigma^{-{\textstyle\frac{1}{2}}}-2^{-n}{\rm Tr}\,[\varphi^{\rm
E}\sigma_{E}^{-{\textstyle\frac{1}{2}}}]^{2}}.$ (33)

Proof: Let $\sigma_{E}$ be a non-negative operator on ${\mathcal{H}}_{E}$. Let
$\sigma=\mathbb{1}_{A}\otimes\sigma_{E}$. [See (29)–(33) at the bottom of the
page.] Next, we apply Lemma V.2 to the first expression under the square root
in (33), taking $f(b(k,u,v))$ $=F_{b(kuv)}(\varphi^{\rm
AE})\sigma^{-{\textstyle\frac{1}{2}}}$. This yields

$\displaystyle{\rm Tr}\,{\mathbb{E}}_{kk^{\prime}uv}F_{b(kuv)}(\varphi^{\rm
AE})\sigma^{-{\textstyle\frac{1}{2}}}F_{b(k^{\prime}uv)}(\varphi^{\rm
AE})\sigma^{-{\textstyle\frac{1}{2}}}$ $\displaystyle={\rm
Tr}\,\Big{[}2^{-\ell}{\mathbb{E}}_{\beta}F_{\beta}(\varphi^{\rm
AE})\sigma^{-{\textstyle\frac{1}{2}}}F_{\beta}(\varphi^{\rm
AE})\sigma^{-{\textstyle\frac{1}{2}}}+(\tau^{\rm A}\otimes\varphi^{\rm
E}\sigma_{E}^{-{\textstyle\frac{1}{2}}})^{2}$
$\displaystyle\qquad\qquad-2^{-\ell}{\mathbb{E}}_{kgg^{\prime}}F_{kg}(\varphi^{\rm
AE})\sigma^{-{\textstyle\frac{1}{2}}}F_{kg^{\prime}}(\varphi^{\rm
AE})\sigma^{-{\textstyle\frac{1}{2}}}\Big{]}$ (34) $\displaystyle\leq
2^{-\ell}{\rm Tr}\,{\mathbb{E}}_{\beta}F_{\beta}(\varphi^{\rm
AE})\sigma^{-{\textstyle\frac{1}{2}}}F_{\beta}(\varphi^{\rm
AE})\sigma^{-{\textstyle\frac{1}{2}}}+2^{-n}{\rm Tr}\,(\varphi^{\rm
E}\sigma^{-{\textstyle\frac{1}{2}}})^{2}.$

Substitution into (33), and writing ${\rm Tr}\,\sigma=2^{n}{\rm
Tr}\,\sigma_{E}$, gives

$\displaystyle{\mathbb{E}}_{uv}\|R_{uv}(\varphi^{\rm AE})-\tau^{\rm
A}\otimes\varphi^{\rm E}\|_{1}$ $\displaystyle\leq\sqrt{2^{n-\ell}}\sqrt{{\rm
Tr}\,\sigma_{E}}\sqrt{{\mathbb{E}}_{\beta}{\rm Tr}\,F_{\beta}(\varphi^{\rm
AE})\sigma^{-{\textstyle\frac{1}{2}}}F_{\beta}(\varphi^{\rm
AE})\sigma^{-{\textstyle\frac{1}{2}}}}$
$\displaystyle=\sqrt{2^{n-\ell}}\sqrt{{\rm
Tr}\,\sigma_{E}}\sqrt{{\mathbb{E}}_{\beta}{\rm Tr}\,U_{\beta}\varphi^{\rm
AE}U_{\beta}^{{\dagger}}\sigma^{-{\textstyle\frac{1}{2}}}U_{\beta}\varphi^{\rm
AE}U_{\beta}^{{\dagger}}\sigma^{-{\textstyle\frac{1}{2}}}}$
$\displaystyle=\sqrt{2^{n-\ell}}\sqrt{{\rm
Tr}\,\sigma_{E}}\sqrt{{\mathbb{E}}_{\beta}{\rm Tr}\,\varphi^{\rm
AE}(U_{\beta}^{{\dagger}}\sigma^{-{\textstyle\frac{1}{2}}}U_{\beta})\varphi^{\rm
AE}(U_{\beta}^{{\dagger}}\sigma^{-{\textstyle\frac{1}{2}}}U_{\beta})}$
$\displaystyle=\sqrt{2^{n-\ell}}\sqrt{{\rm Tr}\,\sigma_{E}}\sqrt{{\rm
Tr}\,\varphi^{\rm AE}\sigma^{-{\textstyle\frac{1}{2}}}\varphi^{\rm
AE}\sigma^{-{\textstyle\frac{1}{2}}}}.$ (36)

In (36) we have used the fact that the $U_{\beta}$ acts only on the ‘A’
subsystem, leaving $\sigma^{-\frac{1}{2}}$ unchanged. Finally, we restrict
$\sigma_{E}$ to ${\mathcal{D}}({\mathcal{H}}_{E})$, so that ${\rm
Tr}\,\sigma_{E}=1$, and apply the definition of conditional quantum Rényi
entropy (2) to get the bound ${\rm Tr}\,\varphi^{\rm
AE}\sigma^{-{\textstyle\frac{1}{2}}}\varphi^{\rm
AE}\sigma^{-{\textstyle\frac{1}{2}}}\leq 2^{-{\sf H}_{2}(A|E)_{\varphi}}$.
$\square$

###### Theorem V.4

Let the key length be set as $\ell=n-t+2\log\frac{1}{\varepsilon}+3$. Then the
quantum encryption scheme of Section V-A is $(t,\varepsilon)$-strongly
entropically secure for all functions.

Proof: The ciphertext space is
$\\{0,1\\}^{2n-\ell+\lambda}\times{\mathcal{D}}({\mathcal{H}}_{2}^{\otimes
n})$. The quantum-classical ciphertext state, entangled with Eve, is
$\varphi^{\rm A^{\prime}E}={\mathbb{E}}_{uv}|uv\rangle\langle uv|\otimes
R_{uv}(\varphi^{\rm AE})$. According to the entropic indistinguishability
definition (Def. III.9), the quantity to be bounded is $\|\varphi^{\rm
A^{\prime}E}-\Omega^{\rm A^{\prime}}\otimes\varphi^{\rm E}\|_{1}$, which,
after setting $\Omega^{\rm A^{\prime}}=\tau^{\rm A^{\prime}}$, becomes
$\|{\mathbb{E}}_{uv}|uv\rangle\langle uv|\otimes R_{uv}(\varphi^{\rm
AE})-{\mathbb{E}}_{uv}|uv\rangle\langle uv|\otimes\tau^{\rm
A}\otimes\varphi^{\rm E}\|_{1}$ =${\mathbb{E}}_{uv}\|R_{uv}(\varphi^{\rm
AE})-\tau^{\rm A}\otimes\varphi^{\rm E}\|_{1}$. This we upper bound with
Theorem V.3. Next, setting $\ell=n-t+2\log\frac{1}{\varepsilon}+3$ in (28)
yields $\|\varphi^{\rm A^{\prime}E}-\tau^{\rm A^{\prime}}\otimes\varphi^{\rm
E}\|_{1}\leq$ $\frac{\varepsilon}{2}\sqrt{2^{[t-1]-{\sf
H}_{2}(A|E)_{\varphi}}}$. Hence we have $(t-1,\frac{\varepsilon}{2})$ entropic
indistinguishability according to Def. III.9. This implies $(t,\varepsilon)$
strong entropic security according to Lemma III.10. $\square$

Note that we achieve $(t,\varepsilon)$-entropic indistinguishability with key
length $n-t+2\log\frac{1}{\varepsilon}$. For approximate randomization, where
the plaintext is unentangled ($t=0$), we thus get the key length
$n+2\log\frac{1}{\varepsilon}$ as listed in Table I.

A special case of quantum encryption is when the plaintext is classical. Then
the quantum encryption scheme typically reduces to a classical scheme that is
secure against quantum adversaries. The QOTP (11), when applied to classical
plaintext bits encoded in the $z$-basis555 A similar result holds for the $x$
and $y$ basis. However, if the $(1,1,1)$ basis is chosen then the result is a
quantum encryption scheme for classical plaintext, with recyclable keys [15].
, has the effect of xor-ing the plaintext with the string $s\in\\{0,1\\}^{n}$,
while the string $q$ does nothing and can be omitted from the scheme.

##  VI Complexity of the key expansion

We comment on the complexity of our key expansion compared to previous works.
Complexity is typically quantified as the number of bit-AND operations; bit-
XOR operations are considered to be much cheaper. Multiplication in
GF$(2^{\nu})$ has time complexity ${\mathcal{O}}(\nu\log\nu)$ [22, 23] whereas
GF$(2^{\nu})$ addition (subtraction) consists of $\nu$ bit-XOR operations.
Mateer [24] introduced an improved version of Schönhage’s multiplication
algorithm [25]. If $m$ is of the form $3^{\kappa}$ and $\kappa$ is a power of
two, then multiplication of two elements in GF($2^{2m}$) requires
${\textstyle\frac{17}{3}}m\log_{3}m$ bit-AND operations and at least
${\textstyle\frac{52}{5}}m\log m\log(\log m)+{\textstyle\frac{3}{2}}m\log
m-{\textstyle\frac{3}{2}}m+{\textstyle\frac{11}{2}}\sqrt{m}$ bit-XORs. If
$\kappa$ is not a power of two, then the number of ANDs slightly increases to
$6m\log_{3}m$ while the bound on the XORs stays the same.

Entropically secure encryption.
Dodis and Smith’s key expansion for classical entropically-secure encryption
[6] makes use of a xor-universal hash function that is implemented by
GF($2^{n}$)-multiplying the key $k\in\\{0,1\\}^{\ell}$ times a random string
$i\in\\{0,1\\}^{n}$. In contrast, our classical scheme has multiplication in
GF$(2^{\lambda})$, and the concatenation with $k$ is for free. For short keys
the speedup is modest; only when the key length $\ell$ is a sizeable part of
$n$ does the speedup become interesting.

The situation is similar in the general quantum case with entanglement. The
scheme of Desrosiers and Dupuis [8] has a key expansion that is the same as in
[6] but for string length $2n$ instead of $n$. Again, our speedup from
GF($2^{2n}$)-multiplication to GF($2^{2n-\ell}$) is modest when the key is
short.

Approximate randomization.
The case of approximate randomization corresponds to entropically secure
encryption with $t=0$, i.e. without entanglement between Eve and the plaintext
state, but with no further guarantees about Eve’s (lack of) knowledge. The key
size $\ell$ is slightly larger than one-half of the extended length $2n$. Our
key expansion consists of one multiplication in GF($2^{\ell}$) and one
addition in GF($2^{2n-\ell}$) or, since $\ell$ asymptotically almost equals
$n$, roughly speaking one multiplication and one addition in GF($2^{n}$). With
Mateer’s multiplication for general $\kappa$, this yields a total cost of
$3n\log_{3}n-3n\log_{3}2$ ANDs and $\geq n\log
n\\{\frac{26}{5}\log\log\frac{n}{2}+\frac{3}{4}\\}-n\\{\frac{26}{5}\log\log\frac{n}{2}+\frac{1}{2}\\}$
$+{\cal O}(\sqrt{n})$ XORs for our key expansion.

In [13] the $\ell$-bit key $k$ is multiplied by a string
$\alpha\in\\{0,1\\}^{2n}$, and the multiplication is in GF($2^{2n}$). If we
write $\alpha=L||R$ and take $\ell\approx n$ then this can be reorganized into
the following steps: (i) a polynomial multiplication $k\cdot R$ without
modular reduction; (ii) a polynomial multiplication $k\cdot L$ shifted by $n$
positions, resulting in a polynomial of degree at most $3n$, followed by
GF($2^{2n}$) modular reduction; (iii) addition of the two above contributions.
As we count two XORs per monomial that needs to be reduced666 With
$m=3^{\kappa}$ it is possible to use the trinomial $x^{2m}+x^{m}+1$ as the
irreducible polynomial, which allows for efficient reduction. If we depart
from the $3^{\kappa}$ form, irreducible polynomials of degree 5 may become
necessary, which leads to more costly modular reduction. It has been shown
[26] that irreducible pentanomials can be chosen such that no more than three
XORs are required per monomial reduction. , we see that the addition in step
(iii) precisely compensates the missing reduction in step (i). Furthermore,
the number of monomials that needs reducing in step (ii) is $n$, which is the
same as in GF($2^{n}$) multiplication. Hence the cost of computing
$k\cdot\alpha$ equals the cost of two GF($2^{n}$) multiplications. Since in
GF($2^{n}$) multiplication is much more expensive than addition, we see that
our key expansion is a factor 2 cheaper than [13].

##  VII Discussion

Our scheme achieves the same shortest key length
$\ell=n-t+2\log\frac{1}{\varepsilon}$ reported in other studies, but with a
more efficient key expansion.

It is interesting to note that the security proof in [13] uses Fourier
analysis and $\delta$-biased families, and invokes Cayley graphs for
intuition, whereas our proof is more straightforward. Furthermore, the
security proof in [8] uses an expansion in the Pauli basis, which we do not
need.

We note that in the classical case our scheme always needs public randomness
that is as large as the plaintext. In the quantum case, however, the size of
the public randomness is not the same in the two cases that we distinguish
($\ell<n$ versus $\ell>n$). It is left for future work to see if this can be
improved.

All the definitions of entropic indistinguishability and entropic security put
a condition on the min-entropy of the plaintext, whereas all the security
proofs yield expressions that contain the collision entropy. It may be
advantageous to work with modified definitions that put a condition on the
collision entropy, since that is more easily met.

## Acknowledgments

We thank Tanja Lange and Dan Bernstein for discussions on multiplication
complexity.

## References

  * [1] G. Vernam, “Secret signaling system,” 1918, uS Patent 1310719.
  * [2] A. Ambainis, M. Mosca, A. Tapp, and R. de Wolf, “Private quantum channels,” in _Annual Symposium on Foundations of Computer Science_ , 2000, pp. 547–553.
  * [3] P. Boykin and V. Roychowdhury, “Optimal encryption of quantum bits,” _Phys. Rev. A_ , vol. 67, no. 4, p. 042317, 2003.
  * [4] D. Leung, “Quantum Vernam cipher,” _Quantum Information and Computation_ , vol. 2, no. 1, pp. 14–34, 2002.
  * [5] A. Russell and H. Wang, “How to fool an unbounded adversary with a short key,” in _International conference on the theory and applications of cryptographic techniques_. Springer, 2002, pp. 133–148.
  * [6] Y. Dodis and A. Smith, “Entropic security and the encryption of high entropy messages,” in _Theory of Cryptography Conference_. Springer, 2005, pp. 556–577.
  * [7] S. Desrosiers, “Entropic security in quantum cryptography,” _Quantum Information Processing_ , vol. 8, no. 4, pp. 331––345, 2009.
  * [8] S. Desrosiers and F. Dupuis, “Quantum entropic security and approximate quantum encryption,” _IEEE Transactions on Information Theory_ , vol. 56, no. 7, pp. 3455–3464, 2010.
  * [9] S. Fehr and C. Schaffner, “Randomness extraction via $\delta$-biased masking in the presence of a quantum attacker,” in _Theory of Cryptography Conference_. Springer, 2008, pp. 465–481.
  * [10] R. Renner, “Security of quantum key distribution,” _International Journal of Quantum Information_ , vol. 6, no. 01, pp. 1–127, 2008.
  * [11] P. Hayden, D. Leung, P. Shor, and A. Winter, “Randomizing quantum states: constructions and applications,” _Commun. Math. Phys._ , vol. 250, pp. 371–391, 2004.
  * [12] G. Aubrun, “On almost randomizing channels with a short Kraus decomposition,” _Communications in mathematical physics_ , pp. 1103–1116, 2009.
  * [13] A. Ambainis and A. Smith, “Small pseudo-random families of matrices: Derandomizing approximate quantum encryption,” in _Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques_. Springer, 2004, pp. 249–260.
  * [14] P. Dickinson and A. Nayak, “Approximate randomization of quantum states with fewer bits of key,” in _Quantum computing: back action_ , vol. 864\. AIP, 2006, pp. 18–36.
  * [15] B. Škorić and M. de Vries, “Quantum Key Recycling with 8-state encoding (The Quantum One-Time Pad is more interesting than we thought),” _International Journal of Quantum Information_ , vol. 15, no. 03, p. 1750016, 2017.
  * [16] R. Canetti, “Universally composable security: a new paradigm for cryptographic protocols,” in _Symposium on Foundations of Computer Science_. IEEE, 2001, pp. 136–145.
  * [17] M. Ben-Or, M. Horodecki, D. Leung, D. Mayers, and J. Oppenheim, “The universal composable security of quantum key distribution,” in _Theory of Cryptography Conference_. Springer, 2005, pp. 386–406.
  * [18] S. Fehr and C. Schaffner, “Composing quantum protocols in a classical environment,” in _Theory of Cryptography Conference_. Springer, 2009, pp. 350–367.
  * [19] M. Müller-Lennert, F. Dupuis, O. Szehr, S. Fehr, and M. Tomamichel, “On quantum Rényi entropies: A new generalization and some properties,” _Journal of Mathematical Physics_ , vol. 54, no. 12, p. 122203, 2013.
  * [20] M. Tomamichel, M. Berta, and M. Hayashi, “Relating different quantum generalizations of the conditional Rényi entropy,” _Journal of Mathematical Physics_ , vol. 55, no. 8, p. 082206, 2014.
  * [21] R. Impagliazzo and D. Zuckerman, “How to recycle random bits,” in _FOCS_ , vol. 30, 1989, pp. 248–253.
  * [22] A. Aho, J. Hopcroft, and J. Ullman, _The design and analysis of computer algorithms_ , ser. Addison-Wesley series in computer science and information processing. Addison-Wesley Pub. Co, 1974\.
  * [23] D. Cantor, “On arithmetical algorithms over finite fields,” _Journal of Combinatorial Theory, Series A_ , vol. 50, no. 2, pp. 285–300, 1989.
  * [24] T. Mateer, “Fast Fourier transform algorithms with applications,” Ph.D. dissertation, Clemson University, 2008.
  * [25] A. Schönhage, “Schnelle Multiplikation von Polynomen über Körpern der Charakteristik 2,” _Acta Informatica_ , vol. 7, no. 4, pp. 395–398, 1977.
  * [26] G. Banegas, R. Custódio, and D. Panario, “A new class of irreducible pentanomials for polynomial-based multipliers in binary fields,” _Journal of Cryptographic Engineering_ , vol. 9, no. 4, pp. 359–373, 2019\.