数理解析研究所講究録
第 1562 巻 2007 年 73-78

73

Asymmetric secret key ciphers and encrypted data retrieval
schemes*Akihiro Yamamura
National Institute of Information and Communications Technology
4-2-1, Nukui-Kitamachi, Koganei, Tokyo 184-8795, Japan

1

Introduction

Traditionally cryptosystems are mainly divided into two categories; symmetric encryptions andasymmetric encryptions. Symmetric ciphers are often called a conventional cipher, a secret key
cipher or a common key cipher. The cryptosystems in this category share the property that thelegitimate users share a common key in advance and the key are used to both encrypt plaintexts
and decrypt ciphertexts. On the other hand, the asymmetric ciphers are often called a public key
cryptosystem. The cryptosystem in this category share the property that the message receiverpublicize his encryption key arid keeps his decryption key. Any message sender can encrypt amessage using the public encryption key. It is clear that the decryption key is different from thepublic key otherwise the anybody can decrypt any message. Thus, the first category of ciphers iscalled a symmetric key cipher and the second is called asymmetric key cipher. There is anotherpossible category of cryptosystems that have not been studied so far. We examine cryptosystems
whose encryption keys are different from the decryption keys and the both are kept secret. On
the other hand, we shall show that the class of asymmetric secret key cryptosystem makes sense
in a certain occasion. Briefly speaking, we need extra properties for secret key ciphers, which thetraditional secret key cipher usually does not possess. To construct a valiant of oblivious transfer
scheme, we need commutative property for the family of secret key ciphers. Then wc shall $8how$ thatboth commutativity property and security cannot be achieved together by a family of symmetricsecret key ciphers. Therefore, it is essential to construct a family of asymmetric secret key ciphersthat satisfies the commutative property.
We also consider the family of encryption functions. A family of encryption functions $\{f_{1}|i\in$, where each is an encryption function of the set of messages $M$ onto Af, is called commutativeif $f_{j}(f_{j}(m))=f_{j}(f_{1}(m))$ for every $m$ in $M$ and $i,j\in I$ . We shall propose a commutative family ofasymmetric secret key ciphers. The commutative property is implicitly used to construct a blindsignature. Our method is similar to the construction of blind signature, however, ours is based on
different assumptions on algorithmic problems and attacking models.
Our motivation comes from the data management in the.ubiquitous network, in particular,
retrieving data from ciphertext embedded in an RFID. As we will see such scheme is closely related
to the oblivious transfer schemes and private information retrievals. Oblivious transfer schemes and$I\}$$f_{i}$’This paper is an extended abstract and the detailed version will be publiShed elsewhere.

74

all-or-nothing disclosure schemes attain the ability of retrieving secretly data from the databaseserver, however, both schemes suffer from the communIcation complexity. If the database is massive, the communication complexity is also large and this is fatal for some applications. In thispaper, we propose a concept of encrypted data retrieval scheme that solves the problem and give aconcrete method to construct such schemes employing a commutative family of asymmetric sccretkey ciphers.

2Private encrypted data retrieval

2.1

Oblivious transfer and private information retrieval

Oblirrious(OT) refer\S to several types of two party $protoco1_{8}$ , where one party, the sender,
traomits part of its input to another $pa$rty, the chooser, in away that protects both parties: thesender is assured that the chooeer does not get more information than it is entitled, and chooeer i8$\mathfrak{R}unSfer$assured that thc sender does not learn which part of the inputs it. The notion of l-outfor short) was introduced in [8], as generalization of $RabIns$ conceptof-2 oblirrious tmnsfer (of OT [11]. Brassard, Cr\’epeau, and Robert in [3] generalized thefurther to J-out-of-N$oblim\dot{o}us$
all-or-nothingunder
thenamedisclosuoe(ANDOS).
ANDOS allows thetransfersender, who holds several secrets, to discloee one of them to the receiver, with the guarantee thatno informatIon about other secrets will be revealed. Furthermore, the receiver has the $1^{arantee}$the sender will not be able to find out which secret was picked.
Private Infomation Retrieval (PIR) schemes [5] allow allser toa $datab_{1}secor\iota si_{f};ting$of $N$ data $m_{1},m_{2},$ $\ldots,m_{N}$ (usually data are just abit) and read any elements without adatabasemanager learning which element $wa8$ accessed. The emphasis in PIR is on $communicat\ddagger on$ complexity which must be $o(N)$ . PIR schemae do not protect the owner of the database, because they do
not prevent the user from learning more than asingle element. Currently, the $qu\infty tion$ of protecting
the database was addressed as well. APIR scheme where auser does not leam more thana single
data is calleda $Symmetr\dot{\tau}c$ PIR (SPIR) [9].
An all-or-nothing discloeure is atwo party protocol in $whic1_{1}t\}_{1C}$ vendor, who holds several
secrets, to discloee one of them to the buyer, with the guarantee that no information about othersecrets will be revealed. Krthermore, the buyer has the $g_{t1}arantee$ the vendor will not be able to findout which secret was picked. In the literature only l-out-of-t all-or-nothing disclosure schemes havebeen studied as far as the authors know. J.Stern [12] propos\’ea l-out-of-t all-or-nothing disclosure
scheme bas $ed$ on $homomorph\ddagger c$ encryptions. $Suppoee$ that avendor poesesses data.
Abuyer wishae to obtain data out of data without informing which data the buyer tries to$i_{\hslash}(1\leq i_{1}<i_{2}<\cdots<i_{s}\leq t)$ ,retrieve. Suppoee thc indices of the buyer’s toice arethat is, the buyer
to obtain the data.
Wc Propose asimilar data retried scheme using our asymmetric secret kcy ciphe,rs. In thescheme, the database is encrypted by the server’s encrypted key and each user has to aek theserver to decrypt it in the way that the server does not notice which data he is decrypting. In ourapproach, the databaee is encrypted and publicized and this reduce the communication complexityof both directioo. This is extremely ideal to ubiquitous setting where wireless transmission islimited and required to reduce the amount of data transmission.
Suppose that is the number of the data in theand is the size of group elementin the data retricval schcmes. The we $S11mmarir_{l}e$ thcse approachoe as follows. Clcarly ollr scheme$rece\ddagger ved$

$OT_{1}^{2}$$not\ddagger on$$(OT_{1}^{N})$$acce_{\wedge}ss$

$t$

$s$

$t$

$i_{1},$ $i_{2},$$wi\epsilon hes$$n$$d_{i_{1}},$$d_{i_{2}},$$\ldots,$$\ldots,$$d_{i_{\epsilon}}$$databa\epsilon e$$k$$d_{1},$ $d_{2},$$d_{t}$$\ldots,$

75

is suitable to application in which data transmission is limited such as RFID embedded systems
because communication complexity of our method is much smaller than the others. In particular,
if the number of data is large, then the communication complexity of the other two will gets large
whereas the communication complexity of ours does not depend on the number of data.

Table 1: Data retrieval

3

Asymmetric secret key ciphers

3.1

Asymmetric secret key cipher based on RSA modulus

Examples in $[1, 2]$ are explained. Let and be distinct primes of the same size. Set $n=pq$ . We
deflne an encryption function enc of the set of messages(denoted by $M$ ) onto itself. Suppose$e\in Z/(p-1)(q-1)$ such thatand $(p-1)(q-1)$ are coprime. Then the set $K$ of keys is$Z/(p-1)(q-1)$ . Then there exists $d\in \mathbb{Z}/(p-1)(q-1)$ such that $m^{ed}=m$ for every $m\in M$ .
$p$$q$$\mathbb{Z}/n$$e$

Secret key The pair $(e, d)$ is a secret key.
Public information The primes$p$and$q$

are publicized.

Encryption Take message $m\in M$ . The function of $MxK$ into $M$ is defined by $f(m, e)=m^{e}$ ,where $(m, e)\in MxK$ . The ciphertext $enc_{e}(m)$ of $m$ is given by $f(m, e)=m^{e}$ , that is, $enc_{\epsilon}(m)=$$f$$f(m,e)$Decryption For any $C\in M$ , the decryption related to the key$dec_{d}(c)=f(c,d)=c^{d}$ .
Commutative property Thebecause$fan\dot{u}ly$$d$

is given by $f(c, d)$ , that is,of encryption functions $\{enc_{\epsilon}|e\in K\}$ is commutative$e_{2}\in K$ .
for all $m\in M$ every$enc_{e_{1}}(enc_{\epsilon_{2}}(m))=m^{\epsilon_{1}\epsilon_{2}}=m^{e_{2}\epsilon_{1}}=enc_{\epsilon_{2}}(enc_{e_{1}}(m))$

Security We suppose that the discrete logarithm problem for $(Z/p)^{*}$ and$e_{1},$$(\mathbb{Z}/p)^{r}$

are intractable.

Remark The encryption is not a public key cryptosystem although we employ completely sameingredient as the RSA public key cryptosystem. We note that the factorization of the modulus issecret in RSA whereas the factorization is public in our cipher. On the other hand, the encryption
parameter is public in RSA, whereas both and are secret in our cipher. Publicizing the primes$n$$e$$e$$d$76

and , anybody can create the encryption and decryption keys in our cipher. Thus, this cipher
algorithm related to the modulus can be employed by multiple users.
The textbook RSA is not randomized cryptosystem and so the scheme is not semantic secure.
We shall discuss randomized asymmetric secret key ciphers which are more secure than the ones in
the full version of the paper.

$p$

$q$

$n$

4

Private encrypted data retrieval protocols

We shall briefly discuss how to construct secret data retrieval schemes using asymmetric secret key
ciphers.

4.1

Basic scheme

Suppose $\{enc_{k}|k\in K\}$ is a family of commutative symmetric ciphers.
The server $S$ encrypts the data $m_{1},m_{2},$by his secret encryption key
and publicizes
the ciphertexts $enc_{e_{n}}(m_{1}),$ $enc_{e_{*}}(m_{2}),$, $enc_{e}.(m_{N})$ .
The receiver wishes to obtain one of the data (say) by decryptingin the waythat $S$ cannot obtain any information on while gets only
. Note that has access to the$enc_{e_{*}}(m_{N})$ , which makes a difference between
ciphertexts $enc_{e}.(m_{1}),$ $enc_{e_{*}}(m_{2}),$
theusual oblivious transfer protocol. The second condition implies that cannot obtain the secret key. A general one round private encrypted data retrievaJ protocol runs as follows:$\ldots,$$m_{N}$$enc_{\epsilon}.(m_{3}),$$e_{\iota}$$\ldots$$\mathcal{U}$$enc_{\epsilon_{*}}(m_{\alpha})$$m_{\alpha}$$\mathcal{U}$$\alpha$$enc_{\epsilon}.(m_{3}),$$\mathcal{U}$$m_{\alpha}$$\ldots,$$\mathcal{U}$$e_{\epsilon}$

Step 1$\mathcal{U}$Step 2$S$$QtoS$ .

generates the system parameters.

receives$Q$$\mathcal{U}$receives

computes $Q=enc_{e_{u}}(enc_{e}.(m_{\alpha}))$ . Then$\mathcal{R}$sends

and computes $dec_{e}.(Q)=dec_{e}.(enc_{e_{u}}(enc_{\epsilon}.(m_{a})))$. Then sends
to .
$S$

$=dec_{C}.(enc_{\epsilon_{*}}(enc_{e_{u}}(m_{\alpha})))=enc_{\epsilon_{u}}(m_{\alpha})$Step 3$\mathcal{U}$$enc_{c_{u}}(m_{\alpha})$and computes

Correctness
If both party play honestly,$\mathcal{U}$obtains

Privacy forcannot distinguish a query for the$m_{\alpha}$$enc_{e_{u}}(m_{\alpha})$$\mathcal{U}$$dec_{\epsilon_{u}}(enc_{e_{u}}(m_{\alpha}))=m_{\alpha}$.

.

$\mathcal{U}$$S$$\alpha th$and the$\beta th$data for all$\alpha$and .
$\beta$Privacy forcannot obtain any information on the other data. This implicitly implies that the protocol
guarantees that cannot obtain any information on the secret key .
Computation
Computations of both and are bounded above by a polynomial in the size $N$ of the database
and the security parameter .
$S$$\mathcal{U}$$\mathcal{U}$$e_{S}$$S$$\mathcal{U}$

$k$

4.2

Proposed scheme

In the basic scheme, there is a security issue. The family of commutative symmetric ciphers may
satisfy the homomorphic property as well. In such a case,may be able to obtain information$\mathcal{U}$77of bothandby only one query. For example,
computes $\beta=enc_{e_{\delta}}(m_{1})enc_{\epsilon_{*}}(m_{2})=$$S$and sends $Q=enc_{e_{u}}(\beta)$ to S.
computes $dec_{e_{\epsilon}}(Q)=enc_{e_{u}}(m_{1}m_{2})$ and sends it to. Then can obtain, which contains information on both. Thus the scheme
anddoes not satisfy the privacy for $S$ .
To repair this flaw, we operate another encryption for the data. Suppose thatis a random
permutation with the key space $\{k|k\in K\}$ and totally anti-homomorp $hic$ . This means that forevery pair of messages$R_{k}(m_{1})R_{k}(m_{2})$ and $R_{k}(m_{1}m_{2})$ are not correlated, that is, there
andis no relation between the distribution $R_{k}(m_{1})R_{k}(m_{2})$ and $R_{k}(m_{1}m_{2})$ .
Then the proposed scheme is described as follows.
The serverencrypts the data,by his secret encryption key
and andpublicizes the ciphertexts $enc_{e}.(R_{k}(m_{1})),$ $enc_{e},(R_{(}m_{2})),$ $enc_{e}.(R_{k}(m_{3})),$$enc_{e}.(R_{k}(m_{N}))$ .
Step 1
gencrates the system parameters.
computes $Q=enc_{e_{u}}(enc_{e}.(R_{k}(m_{\alpha})))$ . Then$m_{1}$$\mathcal{U}$$m_{2}$$enc_{e_{\iota}}(m_{1}m_{2})$$\mathcal{U}$$\mathcal{U}$$m_{1}m_{2}$$m_{1}$$m_{2}$$R_{k}$$m_{1}$$m_{2},$$S$$m_{1},$ $m_{2},$$\ldots$$m_{N}$$e_{\iota}$$k$$\ldots,$$\mathcal{U}$$\mathcal{U}$$\mathcal{R}$sends $QtoS$ .
Step 2$S$

receives$Q$and computes $dec_{e}.(Q)=dec_{e}.(enc_{e_{u}}(enc_{\epsilon}.(R_{k}(m_{\alpha}))))$. Then sends$=dec_{\epsilon}.(enc_{\epsilon}.(enc_{c_{u}}(R_{k}(m_{a}))))=enc_{\epsilon_{u}}(R_{k}(m_{\alpha}))$Step 3
receives
putes $D_{k}(R_{k}(m_{\alpha})=m_{\alpha}$ .
$\mathcal{U}$$enc_{e_{u}}(R_{k}(m_{\alpha}))$and computes$S$$enc_{\epsilon_{u}}(R_{k}(m_{\alpha}))$to$dec_{e_{u}}(enc_{\epsilon_{u}}(R_{k}(m_{\alpha})))=R_{k}(m_{\alpha})$$\mathcal{U}$.

. Finally com-

We should note that using
prevents from obtaining more information from one query. For
example, by the strategy above,
can obtain $R_{k}(m_{1})R_{k}(m_{2})$ that is not related to $R_{k}(m_{1}m_{2})$ .
Therefore, can obtain no information on.
$R_{k}$$\mathcal{U}$$\mathcal{U}$$\mathcal{U}$$m_{1}m_{2}$References[1] F.Bau, R.Deng, and P.Feng, An efficient and practical schcme for privacy protection in theE-commerce of digital goods, ICISC 2000, LNCS 2015 (2000), 162-170[2] F.Bau, R.Deng, P.Feng, Y.Guo, aiid H.Wu, Secure and private distribution of online video andsome related cryptographic issues, ACISP2001, LNCS 2119 (2001), 190-205[3] G. Brassard, C. Cr\’epeau and J.-M. Robert, All-or-Nothing Disclosure of Secrets, CRYPTO’86
LNCS, Vol. 263. Springer-Verlag, (1987) 234-238.
[4] C.Cachin,, S.Micali, M.Stadler, Computationally Private Information Retrieval with Polylogarithmic Communication, Advances in Cryptology. Lecture Notes in Computer Science, Vol.
1592. Springer-Verlag, (1999) 402-414[5] B.Chor, O.Goldreich, Kushilevitz,E., Sudan,M.: Private Information Retrieval, IEEE Symposium on Foundations of Computer Science. (1995) 41-50[6] C. K. Chu and W. G. Tzen . “Efficient k-out-of-n Oblivious Transfer Schemes with Adaptiveand Non-Adaptive Queries”. In Proc. of PKC ’05, LNCS 3386, pages 172-183. Springer Verlag,$g$

2005.

[7] B.Chor, N.Gilboa, Computationally Private Information Retrieval ACM Symposium on The
ory of Computing. (1997) 304-313

78[8] S. Even, O. Goldreich and A. Lempel, A randomized protocol for signing contracts, Communications of the ACM 28 (1985) 637-647.
[9] Y. Gertner, Y. Ishai, E. Kushilevitz, T. Malkin, Protecting data privacy in private data information retrieval schemes, $STOC’ 98$ (1998) 151-160.

[10] E.Kushilevitz, R.Ostrovsky, Replication Is not Needed: Single Database, Computationallyprivate Information Retrieval, IEEE Symposium on Foundations of Computer Science. (1997)

364-373[11] M. Rabin, How to exchange secerts ‘by oblivious transfer, Technical Report TR-81, Harvard
University (1981)[12] J.Stern, A new and efficien-nothing disclosure of secrets protocol, Advances in Cryptology. LNCS, Vol. 1514. Springer-Verlag, (1998) 357-371$allarrow or$[13] W. G. Tzeng. “Efficient l-Out-n Oblivious Transfer Schemes”. In Proc.
LNCS 2274, pages 159-171. Springer-Verlag, 2002.

of PKC ’02,

[14] D.Q.Viet, A.Yamamura, and H.Tanaka, Anoymous Password-based Authenticated Key Exchange, Prvgress in $C\eta ptology$ (Indocrypt 2005) LNCS 3797, Springer-Verlag, (2005) 244-257.

[15] A.Yamamura, T,Jajcayova, and T.Kurokawa, Oblivious transfer and private information retrieval based on the p-subgroup assumption, SOFSEM 2005 Communications, Slovak Society
for Computer Science, (2005) 101-110.
[16] A.Yamamura, T.Kurokawa, and J.Nakazato, Threshold anonymous group identification andzero-knowledge proof, Infomation Security and Privacy (ACISP2007) LNCS 4586, SpringerVerlag, (2007) $37k384$ .

[17] A.Yamamura and T.Saito, Private information retrieval based on the subgroup membership problem, (with T.Saito) Infomation Security and Privacy (ACISP2001), LNCS 2119,Springer-Verlag, (2001) 206-220.
[18] A.Yamamura and T.Saito, Subgroup membership problems and applications to information
security, Scientiae Mathematicae Japonicae, (1) 57 (2003) 25-41.