数理解析研究所講究録
第 1554 巻 2007 年 117-124

117

Quantum Asymmetric-Key Cryptosystems Secure Against

Computationally Unbounded Adversaries
Akinori Kawachi*

Christopher Portmann*$n\circ tre1yonacomputationa11yhardprobAb_{8}tract-Inthispaperwepropoae_{?_{emforsecurity,a1}^{uanttrikeycrypt_{08}ystems,whichd\circ}}umasymme_{butonuncertntyprincip1esof}c-$

to produce exponentially more encryption keys.

Keywords: quantum cryptography, asymmetric-key cryptography, universal composability, information-theoretic security

Introduction

1

Public-key cryptography is the most used cryptographic paradigm. In contrast to secret-key schemes,
where the key used to encrypt messages must be
kept hidden from the adversary and communicated$8ecretly$ to anyone wishing to send a secret message, in public-key cryptography the encryption
key can be announced publicly and given to any
party who wishes it, because knowledge of this key
is not sufficient to perform the reverse operation,
decryption, efficiently. But the person who generated the public key, also generated a secret key, thedecryption key, which he keeps private and uses todecrypt any message sent to him, which was encrypted with the public key he published.
The most famous public-key cryptosystem is RSA,
which $relie8$ on the difficulty of factoring large numbers to make the attack inefficient for anyone whodoes not have knowledge of the secret key. Anyclassical public-key cryptosystem must similarly
rely on the computational difficulty of some problem. But with the advent of quantum computers,a lot of these difficult problems have been proved
to be efficiently solvable [17]. And new paradigms
have to be found.
Where quantum computation makes existing protocols insecure, it also provides new protocols. BB84
[4] marked the breakthrough of quantum cryptography, a quantum key-distribution protocol which.

Department of Mathematical and Computing SciW8-55, 2ences, Tokyo Institute of Technology.
12-1 Ookayama, Meguro-ku, Tokyo 15 -8552, Japan.
titech. ac. jp.
{kewachi, $chrl\cdot to5$ }$\bullet i\cdot$.

is unconditionally secure, when classical key-distribution
protocols are only computationally secure and vulnerable to quantum adversaries. Instead of relying
on the difficulty of some computational problem,
as classical key distribution does, QKD uses funsuch
damental principles of quantum
as the indigtinguishability of non-orthogonal quantum states and the fact that eavesdropping pro
duces noise (we refer to the textbook by Nielsen
and Chuang [12] for an introduction to quantum
information), to ensure that the eavesdropper has
no information on the quantum communication
between Alice and Bob. Other $protocol8$ with security relying on the fundamental principles of quantum mechanics were developed, such as quantum
oblivious transfer [7], quantum string commitment[5] or quantum digital signatures [8], often leading
to unconditional security. But little has been donein this area for quantum asymmetric-key cryptoeys
tems.
The development of quantum key distribution
allows the usage of secret-key cryptosystems which
are secure against a computationally unbounded
quantum adversary. But public-key cryptosystems
have advantages which we want to $pre8erve$ . To
make them secure against quantum attacks, a possible solution is to develop schemes which rely on
problems thought to be hard even on quantum
computers, e.g., NP-hard problems, either clnsical $protoco1_{8}$ as in [14], or quantum protocols asin [11]. But such schemes are still only computationally secure, and thus vulnerable to further
development of (quantum) computation. The alternative solution is to design $protoco1_{8}$ which are$mechanic\epsilon_{!}$

118
secure by virtue of quantum mechanical principles,
and thus produce a scheme which is secure against
a computationally unbounded adversary. In thispaper we propose such quantum asymmetric-key
cryptosystems.

Model The first quantum encryption scheme using the same model as ours was proposed by Kawachi
et al. in [10]. In this model, which is illustrated
in Figure 1and will be described in more detail in
Section 2, Alice distributes aquantum state, ,which se rves as an encryption key .nd corresponds
to adecryption key, to anyone who wants to send
. She also publishes some enher asecret, which Bob applies tocoding operations
Alice’s state when he wants to send her the mes,
$8ages$ . He thus creates the statetoitmeasures
then
She
to
Alice.
back
it
sends
and
was applied, $i.e.$ .decrypt
detect which operator$Bob’ s$ message .
Public-key cryptosystems are vulnerable to manin-the-middle attacks, in which an adversary intercepts or modifles the public key sent by Alice toBob, and replaces it by her own. So some authen, to ensure that the
tication protocol
key Bob receives really is the one Alice sent. As
authentication is out of the $8cope$ of this work, themodel we consider requires an authentic quantum
channel as cryptographic primitive for the distribution of the encryption-key states (which can bewith unconditional security, see, e.g., [1]and Section 2.2 for further discussion). The adversary can not tamper with the encryption-key states
before they are received by Bob, but she cantercept the cipher he sends back to Alice and allother encryption-key states, and has unbounded
computational power. (See Figure 2.)$\rho_{\nu}$$a$$mes\epsilon age$$\{U_{\iota}\}_{\iota\in S}$$\rho_{\nu,\iota}=U_{*}\rho_{\nu}Uf$$U_{l}$$s$$i_{8}neces\epsilon ary$

$reali_{\mathbb{Z}}ed$$inarrow$

Security Alice can perform ameasurement todecrypt the $me88age$ sent to her by Bob, because
she $know8$ how she constructed her encryption key
she knows
she knows the decryption key
adversarythe enhow to measure it. But to thepossibleofallcryption key looks like amixture, and as a $mea8urement$ destroys the state andquantum mechanics doae not allow cloning [12],the adversary is very dependent on the numberof copies of the encryption key released by Alice,
to measure it precisely, extract the decryption key
and thus flnd away to measure $Bob’ s$ cipher state,. So by keeping the number of copies of the encryption key $relea8ed$ bellow acertain $thre8hold$ ,the secrecy is guaranteed even against acomputationally unbounded $adver8ary$ . Aproof of security$ba8ed$ on that idea for the scheme by Kawachi etextension in [11], $wa8$ proved by
al. [10], andHayashi, Kawachi and $Kobaya8hi$ in [9].
$\nu,$$\rho_{\nu},$$\rho_{\nu}$$\rho_{\nu,\iota}$$it_{8}$$8O$

The previous paragraph briefly sketches how theadversary could try to extract the decryption key
from multiple copies of the encryption $key$ to breakthe cryptosystem. This is one strategy amongst
many, and the security criteria, which is discussed
in detail in Section 3, has to encompass any possible attack allowed by the model. But what ismore, we want the encryption scheme to still be
secure –or at least as secure as an ideal functionsome partial informaality
if the adversary
may be leaked if
whichmessageortion about theothers,e.g., if Alwith
combined
this protocol isreceived,ormessage
she
of
the
part
ice publishes
tosomeoneittosend
encrypts it a second timeelse, the rest of the message should still be secure.
This notion is captured by what is called universal
composability, which was first proposed by Canetti[6] and adapted to the quantum setting by Mayers et al. $[3, 2]$ and in parallel by Unruh [18]. So
in Section 3 we $U8e$ such a universally composable
security notion for this encryption scheme.
$get_{8}$–Main Results Our main result is a new encryption scheme based on [11], which improves the previous best bound on the number of encryption-key
states which can be released [9], by a factor exponential in the length of the message which Bob cansend. We also derived a new universal security criteria for the quantum asymmetric-key cryptosystem considered, based on the universal composability framework in $[3, 2]$ , and proved the scheme
secure according to this condition.
More precisely, Hayashi et al. found in [9], thatencrypAlioe can safely produce
crypasymmetric-key
for the quantumtion$m$numtheiswheretosystem proposed in [11],
is
the
i.e,,
log
send,
can
ber of messages Bob
.
is
a
bits,
and
messageinlength of the secretsecurity parameter, polynomial in the size of theencryption-key state. Their security criteria was
the indistinguishability of any two cipher states,
which is weaker than the universal security criteria we use, but their work can be adapted to meetours and still keep the samethe same criteria
allows Alice to produce
schemebound on . Our
copies of the encryptionkey state, thus improving the bound by a factor$m/3$ , which is exponential in the length of the message. $Thi8$ allows Alice to produce that many more
encryption keys and receive that many more mes$k=o( \frac{n10\alpha n}{m\log m})$$key_{8}$

$m$

$n$

$a8$

$k$

$k \leq\frac{n}{3}r_{ogm}^{\iota_{0arrow^{n}-O}}(\frac{n}{\log m})$sages.

119
2Model

Key generation: Alice chooses an element
uniformly at random. and creates copies of, which she sends tothe encryption key
any party who asks for one on an authentic
quantum channel. She also publishes the set.
of encoding operations$\nu\in\Gamma$

2.1 Scheme
The following two definitions describe the statesand operations required by the encryption scheme(illustrated in Figure 1), which were sketch\’e inthe introduction. Definition 1describes the various quantum states, operations and measurements
which the cryptosystem needs, and which need to
be defined when an implementation of the model
is given. Definition 2degcribes how the protocol
is executed and how the elements fit together.

$\rho_{\nu}$$\{U_{l}\}_{s\epsilon s}$

Encryption: To encode the $mes8ages$ , Bob apto the encryption key,plies the unitary, which he sends
and obtains
back to Alice.
with the POVM
Decryption: Alice measures$U_{*}$$\rho_{\nu,s}=U_{s}\rho_{\nu}U_{l}^{1}$$\rho_{\nu,\ell}$$\mathbb{R}=\{E_{*}^{\nu}\}_{\epsilon\in S},$

corresponding to her choice

.
$Bob$

$requir\text{\’{e}}.Firstofa11itisnecessaryforAlicetobeF_{orsuchaschemetobeusefulthreething\epsilon are}^{\circ fdecryptionkey\nu.Sheobtainstheraeult}\epsilon’whichisherguessofBob’ smes\S age$$\ovalbox{\tt\small REJECT}_{\overline{\rho_{s\nu}--U,p_{\nu}U’}}^{\underline{\rho_{\nu}}}Alice.-\cdot$

ciphers
able to distinguish between the$me8sages\epsilon\inS$
and a
for all
se $nt$ by Bob,
given decryption key which we will refer to as
the coroectness of the protocol. More precisely, wewant the probability of Alice decoding the, to be close to 1for evsage correctly,
and $s\in S.$ But it must be hard forery
Eve to $distingui\epsilon h$ between them when she ha\S noor only partial information on the decryption key
on $Bob’ sme8sage\epsilon,$ or any other kind of information she might obtain. This latter conditionis the security of the protocol, which we will di8$CUS8$ in the next section. And thirdly, we want the
protocol to be efficient: i.e., the encoding andcoding operations have to be implementable by apolynomial-time quantum algorithm.
$pos\epsilon ible$$U_{i^{:\cdot nc.oporator}}s:mell\iota po$$\rho_{\nu}^{\gamma:d\infty..k\iota y}:enck\epsilon y$$\rho_{\nu,\prime},$$\nu_{i}$$m\varpi$

Figure 1: Encryption scheme$tr(E_{l}^{\nu}\rho_{\nu,t})$$\nu\in\Gamma$

Deflnition 1. The asymmetric-key $crypt_{08}y_{8}tem$
model considered $consist_{8}$ of atuple of three $e1-$,
ements,where.

$\mathcal{M}_{A\mathcal{K}C}=(\{\rho_{\nu}\}_{\nu\epsilon r}, \{L^{\gamma},\}_{\iota\in S}, \{L\}_{\nu\epsilon r})$of quantum states lying inis aof dimension , whichaHilbert space
we will call $enc$ ryption keys, indexed by el, which we will call decryption
ements$s\epsilon t$$\{\rho_{\nu}\}_{\nu\epsilon r}$$\mathcal{H}_{i}$$d$$\nu\in\Gamma$

keys.
$\bullet$is aset of unitary operators of dimension , which we will call encoding
ators, index\’e by elements $s\in S$ , which we$\{U_{*}\}_{\iota\in S}$$d$.

$0_{\Psi^{r-}}$will all secnt messages.
$c$is aset of POVMe, which we willcall decding $mea\epsilon uoements$ , where
are the POVM elements, indexed by the decryption keys and $8ecretmes8age8$ re8pec$\{\mathbb{R}\}_{\nu\epsilon r}$$L=\{E_{*}^{\nu}\},\epsilon s$

tively.

$\nu,$$darrow$

2.2 Channels and $Adver\iota ary$
An adversary, Eve, could perform a
middle attack, and replace the encryption-key state
sent by Alice to Bob by her own state. If Aliceand Bob do not run $8ome$ authentication protocol,
to ensure that the key Bob receives really is theone Alice sent, then any cipher state se nt back to
Alice by Bob, which is encrypted using the unauthenticated encryption key he received, could bereadable by the adversary.
work we study the feasibility of encryptIn$ing$ messages into quantum states of which the adversary has copioe. We do not consider thecols which allow $the8e8tat\infty$ to be distributed. We
therefore require an authentic quantum channel
cryptographic primitive. Such achannel could be
alized with anon-interactive protocol if adecryption key is shared by the two parties,
posed in [1], in which case this \S cheme can be seen
key into apublic one. Alternaas turning atively, an interactive protocol involving entanglement distillation or quantum error correction$man- in- th\triangleright$$thi_{8}$Although we have specified aset of POVMs as
decoding measurements in this definition, practically we will give aprotocol, or aset of unitary
operations followed by ameasurement, which areequivalent to aPOVM.

Deflnition 2. The protocol consists of three steps,
which use the states and operations given in Definition 1, namely key generation, encryption anddecryption.

$prot\triangleright$

$a8$

$re$

$a8pr\triangleright$$\epsilon ecret$$(\epsilon ee$

120[12] for an overvi $ew$ of these techniques) can be
used.

too much of Bob’s message, although individuallyneither this protocol nor the subsequent leaks give.
any non-negligible amount of information toThis stronger security notion is captured by what
is called $univ\epsilon rsally$ composable security.
Universal composability was first introduced by
Canetti in [6] for classical cryptography. The idea
is to ensure that acryptographic protocol is stillsecure when combined in acomplex system withother protocols, and that the developer of $8uch$ asystem only needs to consider the ideal functionalities the protocols are trying to implement, and$E\backslash ^{r}e$Figure 2: The adversary’s attack
In this model we therefore have an authentic
quantum channel for the distribution of the encryptionkey stat , and a totally insecure quantum channel
for sending the cipher state. Thus the adversary
cannot tamper with the encryption key, but he canand can intercept the cipher
make a copy ofstate and all of the other encryption keys published, as illustrated in Figure 2. The adversaryis also computationally unbounded, and can perform any operation and measurement allowed byquantum mechanics on the states she intercepted.
$e$$it^{1}$

3

Security$i8$$a\epsilon|2$

The security of the general scheme proeented in
the previous section relies on the indistinguishability of non-orthogonal quantum states. For a given, the encodings of the posdecryption key
sible messages $s\in S$ must be near-orthogonal, sothat Alice can distinguish between them with highprobability. But when is not known, the possible ciphers over all possible decryption keys mustbe highly non-orthogonal, so that Eve cannot distinguish between them without knowing in whichbasis to measure Bob’s message.
Each encryption key Alice publishes is information leaked to the adversary. With sufficient copies
of it, Eve can measure it $preci_{8}ely$ and thus discover how to measure Bob’s message in order toextract the secret message. So it is necessary tofind a bound on the number of encryption keys
Alice can release, so that Eve only gets negligible
information on Bob’s message.
Yet as such, this security notion is not strong
enough. Eve may obtain information from othersources or in subequent protocols, which combined with what is leaked by this protocol reveal$\nu\in\Gamma$

$\nu$

1

not the details of the implementations, when combining them together. The framework proposed in[6] wae extended to the quantum setting by BenOr and Mayers in [3] and adapt\’e to quantum key
distribution in [2]. In these works, aprotocol
consider\’e secure if the environment, which com$prise8$ all adversaries and the inputs and outputs ofthe protocol, can only $di_{8}tinguish$ with negligible
probability between the real protocol and the ideal
functionality the protocol is trying to implement.
The ideal functionality can thus be substituted forthe real protocol in the analysis of any other cryp-.
tographic protocol which uses it as asubroutine,as the two cannot be distinguished.
Aslightly different approach to quantum universal security by Renner lead to the same definition] and was apfor the security of secret keys
pli\’e to quantum privacy ampliAcation $|16$] andquantum key distribution [15]. Here the $q_{Ue8}tion$$a8kedi8$ whether the scheme is still secure if theadversary postpones the measurement of whatever
information he posse8\S es encodcd in aquantum
state until alater time when he might have gathered extra information, e.g., part of the message,
telling him how to perform the measurement, thus
unlocking much more information than he could
have obtained initially, This extra information
the adversary might get, could be from anotherprotocol, when several are combined together. So

Cloning of a quantum state is generally impossible. But
as we use an authentic quantum channel as a black box,
by assuming the adversary gets a copy of the state weupper bound the information he might obtain.

$the8e$ two approaches

are basically the same. But

ageneralization of
the latter can also be seenother speciflc security requirements, $8ucha8$ wanting the last bit of the key to still be $8ecret$ if therest of it is revealed, or not wanting the adversary
to be able to $di8tingui8h$ between any two possible ciphers, which was the security criteria used infor the quantum $a\epsilon ymmetric$-key cryptosystem
proposed in [11].
Generally, let be asecret (e.g., akey or, which consists of thesage) with distributionbeinput or output of aprotocol , and let
the adversary’s syst $em$ after the execution of thisprotocol, when the secret take\S the value , forany element of S. The resulting system can be
$a8$

$|9]$

$S$

$me\epsilon-$$P_{S}$$\mathcal{P}$$\rho_{B}$$\epsilon$$\epsilon$

121
described by the following density operator:$\rho_{SB}=\sum_{s\in S}P_{S}(s)|sXs|\rho_{B}^{s}$,(1)

have access to her secret key, so no extra information will ever be leaked about it. The adversary’s
system consists of all the encryption keys and theintercepted cipher state ’ from Bob, as definedin Section 2. If Alice chooses the decryption key
uniformly at random from a set and publishes
copies of the encryption key , the adversary’s
system conditioned on the secret message beingis then in the state$\rho_{\nu},$

is an orthonormal basis of somewhere {. With an ideal protocol , theHilbert spaceadversary system would be uncorrelated to thesecret. Thus not only he gets no direct information
about the secret, but if this protocol is combinedwith others which share the same secret input or
output and leak some information about it, the adversary cannot use this extra information to help
him extract the secret from the states this protocol leaked. I.e., the system would be in the state$|\epsilon\rangle$$1,\in S$$\mathcal{P}\tau$$\mathcal{H}_{S}$$s$$\rho_{U}\otimes\rho_{B}$,(2)

is the fully
where,
mixed state in the Hilbert space of the secretandis the $adver8arys$ state, namely$\rho_{U}=\Pi^{1}s^{I}=\cap^{1}s\sum_{\iota}\epsilon s|\epsilon Xs|$$\mathcal{H}s$$\rho_{B}$$\rho_{E}=tr_{S}(\rho_{SB})=\sum_{l\epsilon s}P_{S}(\epsilon)\rho_{B}^{l}$.

(3)

We want the distance between the real situation(Eq. (1)) and the ideal one (Eq. (2)) to be small.

Therefore$||\rho_{SB}-\rho_{U}\otimes\rho_{B}||_{1}\leq\epsilon$.

$\mathcal{P}$$\epsilon$$\epsilon$$\mathcal{P}_{\mathcal{I}}$$Q$$\epsilon’$$\mathcal{P}x$$\mathcal{P}$$(\epsilon’+\epsilon)$$S$$\rho_{\nu}$$\epsilon$$p_{B}^{l}= \frac{1}{|\Gamma|}\sum_{\nu\epsilon\Gamma}\rho_{\nu,\iota}\otimes\rho_{\nu}^{\otimes k}$.

By placing Eq. (5) in Eq. (4), we get a universal
security criteria for the scheme. It depends however not only on the choice of the encryption-key

stat es , but also on the way the encoding of themessage is done and the resulting cipher states. In Theorem 3 we will show that the uni$\rho_{\nu}$$s$$\rho_{\nu_{l}},$versal security of the encryption-key scheme only
depends on a near-uniform distribution of the mesand the security of the encryption-key
sages
state, namely the difficulty to distinguish it fromthe fully mixed state when drawn uniformly at random, given extra copies of it.
$\epsilon\in S$$k$

Theorem 3. If(6),where is the dimension of and I is the identity
operator of dimension , and if the $non- unifomit\emptyset$of the message probability distnbution is less thanthen an asymmetri c-key cryptosystem as described in Section 2, $i.e.$ , which leaves the adversary’s system in the state(Eq. (5)) when the message is and the encryption,
key is chosen uniformly at random from.
-secure with respectthen such a scheme is$i.e.$ ,to the Hilbert space$d$$\rho_{\nu}$$d$$\frac{\delta}{2}$$\rho_{B}^{l}=k\sum_{\nu\epsilon r}\rho_{\nu,\iota}\otimes\rho_{\nu}^{\otimes k}$$s$$\{\rho_{\nu}\}_{\nu\epsilon}r$$(\delta+\epsilon)$$\mathcal{H}_{B},$$\mathcal{H}_{B}$$\epsilon$(5)$\Vert\frac{1}{|\Gamma|}\sum_{\nu\epsilon r}p_{\nu}^{\otimes(t+1)}-\frac{1}{d}I\otimes\frac{1}{|\Gamma|}\sum_{\nu\epsilon r}\rho_{\nu}^{\otimes k\Vert_{1}\leq\frac{\epsilon}{2}}$$||\rho-\sigma||_{1}$$\mathcal{P}$

$k$

(4)

where the distan ce measure used, known as the$:=tr(|\rho-\sigma|)$ .
l-distance, is defined as
According to the work done in $[3, 2]$ , if Eq. (4)is respected, then the environment cannot distinand the ideal
guish between the real protocol, except with probability . The
functionality
protocolis said to -securely realize the ideal, and by the composition theorem
functionality
from $[3, 2]$ , any protocol which is -secure whenas subroutine, isusing the ideal functionality-secure when using the real protocol as
subroutine. In [15], if Eq. (4) is respected, the se.
cret is said to be -sec un with respect to
The ideal and real situations are -close, and as
the l-distance cannot increase when applying an
arbitrary quantum operator, it will remain so for
any further evolution of the world.
We therefore take Eq. (4) as our definition ofuniversally composable security, and adapt it to
the particular context of our encryption scheme.
The secret which maybe be seen as both input andoutput of the encryption protocol is Bob’s message. Alice or Bob may publish part of it, or encrypt
it again to send it to another party. It can be usedby any super protocol which accesses this encryption scheme as subroutine. Ahce’s secret key on
the other hand is kept secret by Alice. No matter how other protocols use thiv one, they do not$\mathcal{P}x$$\Gamma$$\nu$$||\rho_{SB}-\rho_{U}\otimes\rho_{B}||_{1}\leq\delta+\epsilon$.

(7)$\epsilon$. Let$Pr\mathfrak{v}of$$\sigma_{\iota}$$;= \frac{1}{|\Gamma|}\sum_{\nu\epsilon r}p_{\nu,\iota}\otimes\rho_{\nu}^{\emptyset k}-\frac{1}{d}I\otimes\frac{1}{|\Gamma|}\sum_{\nu\in\Gamma}\rho_{\nu}^{\theta k}$

,

then

. (8)

$\frac{1}{|\Gamma|}\sum_{\nu\epsilon r}p_{\nu,\iota}\otimes\rho_{\nu}^{\otimes k}=\frac{1}{d}I\otimes\frac{1}{|\Gamma|}\sum_{\nu\epsilon r}\rho_{\nu}^{\Phi k}+\sigma_{\iota}$$\epsilon$

is obtained from by applying the
Because$U,$, and because a unitary operation does
unitary$\rho_{\nu,\iota}$$\rho_{\nu}$

2 The non-unifomity of a probability distribution $P\chi$ is its

variational distance from the uniform distribution, i.e.,$d\langle P\chi)=_{2\epsilon x}1\Sigma.|P_{X}(x)-*|$

122
not change the l-distance, we have$s_{2}\in S$ . Then by the hypothesis of thisfor any.
lemma (Eq. (6)),
By placing Eq. (8) in the left-hand side of Eq. (7)with their exact values
andand replacing(Eqs. (1), (3) and (5)), we get$||\sigma_{\iota_{1}}||=||\sigma_{\epsilon_{2}}||$$s_{1},$

can directly use the security bound derived in Section 4.1.

$|| \sigma_{t}||_{1}\leq\frac{\epsilon}{2}$$\rho_{E}$$\rho_{SB}$

Coset States
Definition 4. Let be a finite group and $H$ a
subgroup of . The coset state of $H$ is then $p_{H}=$$\Pi^{1}G\sum_{g\epsilon c}|gHXgH|=E^{H}\sum_{g\epsilon c/H}|gHXgH|$ , withis an or, where, andthonormal basis of some Hilbert space$gh$ is the composition of
and with the group
operation.

4.1

$G$

$G$

$\{|g\rangle\}_{g\in G}$$|gH \rangle=\frac{1}{\sqrt{}|H|}\sum_{h\in H}|gh\rangle$$\Vert\sum_{\prime\epsilon s}P_{S}(s)|sX^{s|\otimes}(\frac{1}{d}I\otimes\frac{1}{|\Gamma|}\sum_{\nu\in\Gamma}\rho_{\nu}^{\otimes k}+\sigma.)$$\mathcal{H}_{G}$

$h$

$g$

$- \frac{1}{|S|}I\otimes\sum_{\epsilon s}P_{S}(\epsilon)(\frac{1}{d}I\otimes\frac{1}{|\Gamma|}\sum_{\nu\epsilon r}p_{\nu}^{\otimes k}+\sigma_{\iota})\Vert_{1}$$\leq\Vert\sum_{l\in S}P_{S}(s)|_{\delta}X\epsilon|-\frac{1}{|S|}I\Vert_{1}+\Vert\sum_{l\epsilon s}P_{S}(\epsilon)|_{8}X^{\epsilon|\otimes\sigma_{\iota}\Vert_{1}}$These coset states appear in what is known as
the standard method to solve the hidden subgroupproblem, which is one of the central issues in quantum computation, introduced for revealing the structure behind exponential speedups in quantum computation. Let be a finite group, and $H$ a hiddenfrom to a fisubgroup of . Given a map$f_{H}(g)=f_{H}(gh)$if and only ifthatnite set such$h\in H$ , the hidden subgroup problem (HSP) is the
problem of outputting a set of generators for thehidden subgroup $H$ .
In the following lemma (which is a slight modification of Theorem 2.4 in [9]) and Corollary 6ofjust after, we substitute coset states
subgroups $H\in H$ with prime cardinality for thein Eq. (6), and findencryption-key states
an upper bound on the number of $co$ pies of thewhich can be released, so that thecoset state
environment can only distinguish with probability
between an encryption key drawn at random andthe fully mixed state when provided with extra
copies of it.
$G$$+ \Vert\frac{1}{d}I\otimes\frac{1}{|S|}\sum_{\iota\epsilon s}\sigma.\Vert_{1}\leq\delta+\frac{\epsilon}{2}+\frac{\epsilon}{2}$.

$G$$f_{H}$

$G$

$S$

口

We can require from Bob that the non-uniformity
be negof the distribution of his messages
universal
forconditions
ligible. So the sufficient
security expressed in Theorem 3 are reduced toEq. (6). From the universal composability viewpoint, this criteria can be see as a universal security requirement for the encryption key, namely
a negligible probability that the environment candrawn
distinguish between the encryption key
key-states
possibleall
uniformly at random fromand the fully mixed state, given extra copies of
the key.
This criteria can be used to find bounds on thenumber of copies of the encryption key which
can safely be released, for particular instances orfamily of instances of states and encoding operations implementing Definition 1, which is what we
do in the next section.
$\epsilon\in S$$n$$\rho_{\nu}$$k$$\{\rho_{H}\}_{H}\epsilon H$$\{\rho_{\nu}\}_{\nu\in\Gamma}$$k$$p_{H}$$\epsilon$

$k$

$k$

$\Vert\frac{1}{|H|}\sum_{H\epsilon H}p_{H}^{\otimes(k+1)}-\frac{1}{|G|}I\otimes\frac{1}{|H|}\sum_{H\epsilon w}p_{H}^{\otimes k}\Vert_{1}\leq\epsilon$,

for $H\in H$ with rime cardindity.
Proof. Simply by expanding the coset stat es and$p$Instances
In Section 4.2 we will give a specific implementation of encryption key, encoding-operation andmeasurement tuple, with a precise bound on the
security. But before that, in Section 4.1, we will
study a family of good encryption key candidates,
namely what known as coset states of a subgroupof prime order (see Definition 4). This allows us
to derive a bound on the number of encryptionkey states which can be released for the universal
security criteria found in Section 3 (Eq. (6)), for a4

using the triangle inequality with a similar argument of [9], we obtain$\Vert\frac{1}{|H|}\sum_{H\epsilon H}\rho_{H}^{Q(k+1)}-\frac{1}{|G|}I\otimes\frac{1}{|H|}\sum_{H\in H}\rho_{H}^{\emptyset k\Vert_{1}}$$i_{8}$

specific family of states with common proprieties.
The final scheme we propose in Section 4.2 is aparticular instance of this family of states, and we$\leq$$m \frac{\max_{H\epsilon H}|H|^{k+\iota}}{|H|}$,is the L2-norm. The last inequality
where
is obtained by using the fact that the $8ubgrou\mu$considered have prime cardinality which implies
that $|H\cap H’|=1$ if $H\neq H’$ .
$||\cdot||_{2}$123, which the$m$ ,cardinality
send,
have
to
scheme allows Bob
naturalbythethem
representus$|S|=m$ , and let
numbers, i.e., $S=\{0, \cdots , m-1\}$ . To encrypt thedefined previously, letmessage in the state
unitary
Bob apply the

Definition 8. Let the message set

asCorollary 6. If we use coset states
described
theschemeinencryption keys
in Section 2, and each $H\in H$ has the same cardinality, then the scheme isif the number
keyisreleasedencryption
thecopiesofof$\{p_{H}\}_{H\epsilon H}$$\{\rho_{\nu}\}_{\nu\in\Gamma}$$S$$\rho_{\pi}$$\epsilon$$\epsilon\cdot secure$$k$.

$k \leq\frac{2\log\epsilon+\log|H|}{\log|H|}-1$

4.2$Implementationtions$(9)with Cyclic Permuta-$U,$$:= \sum_{x=0}^{m-1}e^{2\pi i\iota r/m}|XX^{x|}$

.

(11)

This unitary is only defined on a space of dimension and acts on the first register of the encryptionkey state , so it needs to be padded by an idento be formally cortity operator of dimension
simplicity and alfor
omit
itrect. But we will
instead oftowrite
low ourselves$m$$p_{r}$$n!$

We now propose a particular instance for thescheme discussed so far, namely cosets of subgroups, whereis the setof the groupof natural numbers smaller than and the groupis the set
operation is addition modulo , andof all permutations of an n-tuple and the group operation is permutation composition. and $m$ are
ditwo parameters such that $m$ is prime andvides , but for the rest they can be chosen freely.
As it will become clear as we define the encrypis the number oftion scheme more precisely,
messages which can be encoded, and is a security parameter. By choosing big enough, we will
be able to make the scheme -secure, for an exponentially small in .
$ln$ Section 4.2.1 we will deflne the encryptionkey states, encoding operations and decoding measurements precisely, and show that the scheme iscorrect, i.e., that Alice can decode Bob’s message
with probability 1 if the adversary does not intervene. In Section 4.2.2 we will then prove that thescheme is secure and find a bound on the numberof encryption keys which can be released.
$G=\mathbb{Z}_{m}xS_{\mathfrak{n}}$$\rho_{\pi},$$\mathbb{Z}_{m}$$m$$S_{n}$$m$$n$$\rho_{\pi,\iota}=(U_{*}\otimes I)\rho,$..

$=U.\rho_{\pi}L_{l}^{r\dagger}$$(U_{l}^{1}\otimes I)$

Ifthe first register is represented by
Eq. (11) can be rewritten as
where$\hat{U},$$m$$U_{\iota j}=|($

).

$n$

$m$

$n$

$n$

$\epsilon$$\epsilon$$n$4.2.1 Correctness
The following definition specffies the encryptionkey state , where is the decryption key.

differs slightly from , in that it isand also
defined on a space of dimension 2
modifies the first register if it takes a value $m\leq$$x\leq 2^{\lceil\log m1}-1$ .
But the encryption-key states, are only defined with values of the first registerand$0\leq x\leq m-1$ , so for all decryption keys
. The operators
messagescan thus be efficiently implemented.
defined in Eq. (11) take any
The operators
to mutually orthogonal
encryption-key statesubspaces, which allows them to be distinguishedby Alice with probability 1, as the following theorem shows.
Theorem 9. There exists a polynomial-time quan, decrypts
tum algorithm that, for each1.
prvbability
to withNote that, be the set composedof $n/m$ disjoint cyclic permutations. We now define the encryption-key state , where the decryp,tion key is chosen uniformly at random from

Deflnition 7. Let$\mathcal{K}_{n}^{m}\subseteq S_{n}$$p_{n}$$\mathcal{K}_{n}^{m}$

$\pi$

as

$\rho_{\pi}:=\frac{1}{n!}\sum_{\sigma\epsilon s_{*}}|\Phi_{\pi}^{\sigma}X\Phi_{\pi}^{\sigma}|$

,

(10)

$U_{1}$$\hat{U}_{*}$$\lceil\log m\rceil$$\rho$

$\pi$

$s,$

$U.\rho_{\pi}U_{l}^{1}=\hat{U}.p_{\pi}\hat{U}_{*}\dagger$$\{U,\}_{\iota\in S}$$U_{*}$$\rho_{\pi}$$\rho_{\pi},$$\pi$$\rho_{l}$.

$\pi\in \mathcal{K}_{n}^{m}$$=U_{\iota}\rho_{\pi}U_{l}^{1}$

Proof.

$s$.

$\rho_{\pi,\iota}=\urcorner_{n}1$$\sum_{\sigma\in S}$.

$|\Phi_{\iota}^{\sigma}X^{\Phi_{\iota}^{\sigma}|}$$|\Phi_{\pi}^{\sigma}\rangle$$= \star_{m}\sum_{\iota=0}^{m-1}|x,$

.
$s$

$U$

$p_{\pi}$$\rho_{\pi,\iota}=U,\rho_{l}U_{l}^{1}$

$U$

$=$

This state is a super. So it suffiposition of the pure statesalgorithm
quantum
cient to give a polynomial-time
independently
anywhich can extract fromfrom , and by linearity the algorithm can extract.
fromthe $controlled-\pi^{-1}$ operBy applying to, whichator,
to the secapplies times the permutation
ond register, when the first register contains , weobtain:The second register is now un-entangled from thefirst, and by applying the inverse Fourier transform on the first register we get .
$i_{8}$$s$$|\Phi_{\pi,*}^{\sigma}\rangle$$\sigma$$\rho_{\pi,*}$$C_{\pi^{-1}}= \sum_{x=0}^{m-1}\sum_{\sigma\epsilon s}$

Alice will send this state to Bob, or any party
who wishes it. To send a message to Alice, Bob
will apply a unitary , to t.he encryption key ,, which he sends back to
obtaining,are defined as follows.
Alice. The operations$|\Phi_{w}^{\sigma},\rangle$$|\Phi_{\pi,\iota}^{\sigma}\rangle$$|\Phi_{\pi,\iota}^{\sigma}\rangle$

where, where$7^{1}\overline{m}^{\sum_{\epsilon=0^{1}}^{m-}e^{2\pi i*x/m}|x,\sigma\pi^{l})}$$\epsilon$$\sigma\pi^{x}\rangle$

qubits,,$=\otimes_{j=0}r\log m1-1U_{l,j}$$e^{2wi\cdot 2^{j}\prime m}0$$01$$\lceil\log m\rceil$.

$|x,$ $\sigma\pi^{-e}Xx,\sigma|$$\pi^{-1}$

$x$

$x$

$C_{n^{-1}}|\Phi_{\pi}^{\sigma},\rangle$$=\nabla^{1}\overline{m}^{\sum_{l=0}^{m-1}e^{2ri\iota ae\prime m}|x\rangle|\sigma)}$$\epsilon$

124[9] M. Hayashi, A. Kawachi, and H. Kobayashi.
Quantum measurements for hidden subgroupproblems with optimal sample complexity.

The efficiency of this algorithm is straightforward from its construction.
Theorem 9 not only proves that the cipher stat es
can be decoded, but it also gives an explicit
efficient algorithm to do it, which serves as the
decoding POVMs required by the definition of thescheme (Definition 1 in Section 2).
$\square$quant-ph/0604174, 2006.

$p_{\pi,s}$[10] A. Kawachi, T. Koshiba, H. Nishimura, andT. Yamakami. Computational indistinguishability between quantum states and its cryptographic application. In Proc. EUROCRYPT
2005, LNCS 3494, pages 268-284, 2005.

4.2.2 Security
To prove that a scheme using the encryption key
defined in the previous section (Deflnition 7) is secure, we will show that it is a coset state, and thenwe apply the bound from Eq. (9) from Corollary 6.
Theorem 10. An encryption scheme as defined in
Section 2 using the encryption keys given in Definition 7 is -secure, if the number of encryption
keys leased isThus, if the number of the released encryption
keys is at most log $n/3\log m-O(n/\log m)$ , weby this theorem.
can guarantee[11] A. Kawachi, T. Koshiba, H. Nishimura, andT. Yamakami. Computational indistinguishability between quantum states and its cryptographic application. Full version of [10],quant-ph/0403069, 2006.

[12] M. Nielsen and I. Chuang. Quantum Computation and Quantum Information. Cambridge
University Press, 2000.

$k$$\epsilon$$re$$k\leq m_{\log m}610_{3}\epsilon n1on$$k$[13] T. Okamoto, K. Tannka, and S. Uchiyama.
cryptosystems. In Proc.
Quantum$200C$
1880, pages 147-165,,
LNCS
CRYPTO$n$$public- k^{r_{\vee}}y$$\epsilon=2^{-\Theta(n)}$2000,

References[1] H. Barnum, C. Cr\’epeau, D. Gottesman. A.
Smith, and A. Tapp. Authentication of 4uan, pages
tum messages. In Proc. FOCS
449-458, 2002.
$2^{p}01$[14] O. Regev. On lattices, learning with errors,
random linear codes, and cryptography. In
Proc. STOC 2005, pages 84-93, 2005.
[15] R. Renner. Securi $ty$ of Quantum Key Distri
bution. PhD thesis, Swiss Federal Institute ofTechnology Zurich, September 2005.
$\cdot$[2] M. Ben-Or, M. Horodecki, D. Leung, D. Mayers, and J. Oppenheim. The universal composable security of quantum key distribution.
In Proc. TCC 2005, pages 386-406, 2005.

[3] M. Ben-Or and D. Mayers. General security
definition and composability for quantum&
classical protocols. quant-ph/0409062, 2004.
[4] C. Bennett and G. Brassard. Quantum cryptography: Public key distribution and cointossing. In Proceedings of IEEE Intemational
Conference on Computers, Sys tems, and $Sig$
nal $Pr\propto essing$ , pages 175-179, 1984.

.

[5] H. Buhrman, M. Christandl, P. Hayden, H.K. Lo, and S. Wehner. On the (im)possibility
quantof quantum string commitment.
$ph/0504078$ , 2005.

[6] R. Canetti. Universally composable security:
A new paradigm for cryptographic protocols.
In Proc. FOCS 2001, pages 136-145, 2001.

Quantum oblivious transfer.
Journd of Modern Optics, 41 (12) $:2445-2454$ ,1994.
[8] D. Gottesman and I. Chuang. Quantum digital signatures. quant-ph/0105032, 2001.

[7] C. Cr\’epeau.

[16] R. Renner and R. Koenig. Universally com-posable privacy amplification against quantum adversaries. In Proc. TCC 2005, LNCS
3378, $page8407-425$ , 2005.

Polynomial-time algorithms for[17] P. Shor.
prime factorization and discrete logarithms
SICOMP,
on a quantum computer.
$26(5):1484-1509$ , 1997.
[18] D. Unruh. Simulatable security for quantum
protocols. quant-ph/0409125, 2004.