Processing math: 100%
ZHAI Jiaqi, LIU Jian, CHEN Lusheng, WANG Lingyu. MSK-PK: A Public-Key Encryption Cryptosystem with Multiple Secret-Keys[J]. Chinese Journal of Electronics, 2022, 31(4): 764-772. DOI: 10.1049/cje.2020.00.049
Citation: ZHAI Jiaqi, LIU Jian, CHEN Lusheng, WANG Lingyu. MSK-PK: A Public-Key Encryption Cryptosystem with Multiple Secret-Keys[J]. Chinese Journal of Electronics, 2022, 31(4): 764-772. DOI: 10.1049/cje.2020.00.049

MSK-PK: A Public-Key Encryption Cryptosystem with Multiple Secret-Keys

Funds: This work was supported by National Key R&D Program of China (2019YFB2101700), National Key Research and Development Program of China (2018YFA0704703), and National Natural Science Foundation of China (61902276)
More Information
  • Author Bio:

    ZHAI Jiaqi: received the B.E. and M.S degrees from Nankai University, China, in 2013 and 2016, respectively. Currently he is pursuing his Ph.D degree in Nankai University, China. His research interests include digital signatures, publickey encryption schemes, and cryptographic protocols. (Email: JQZhai@mail.nankai.edu.cn)

    LIU Jian: (corresponding author) received the B.S. and Ph.D. degrees from the School of Mathematical Sciences at Nankai University, Tianjin, China, in 2009, and 2015, respectively. She was a Visiting Ph.D. Student at the Department of Mathematics, University of Paris VIII, Paris, France. She is currently an Associate Professor with the School of Cybersecurity, College of Intelligence and Computing, Tianjin University, Tianjin, China. Her research interests include cryptography and coding theory. (Email: jianliu.nk@gmail.com)

    CHEN Lusheng: received the B.S. degree in mathematics from Nankai University, Tianjin, China, in 1984, the M.S. degree in computer science, Shandong University, Jinan, China, in 1987, and the Ph.D. degree in mathematics from Nankai University in 2000. He is currently a Professor of the School of Mathematical Sciences at Nankai University. His research interests include cryptography, coding theory, and information theory. (Email: lschen@nankai.edu.cn)

    WANG Lingyu: is a Professor at the Concordia Institute for Information Systems Engineering (CIISE) at Concordia University, Montreal, Canada. He holds the NSERC/Ericsson Senior Industrial Research Chair in SDN/NFV security. He received the Ph.D. degree in information technology from George Mason University in 2006. He holds the M.E. degree from Shanghai Jiao Tong University and the B.E. degree from Shenyang Aerospace University. His research interests include cloud computing security, SDN/NFV security, security metrics, software security, and privacy. (Email: wang@ciise.concordia.ca)

  • Received Date: February 13, 2020
  • Accepted Date: January 05, 2022
  • Available Online: February 18, 2022
  • Published Date: July 04, 2022
  • By allowing intermediate nodes to combine multiple packets before forwarding them, the concept of network coding in multi-cast networks can provide maximum possible information flow. However, this also means traditional encryption methods are less applicable, since the different public-keys of receivers imply different ciphertexts which cannot be easily combined by network coding. While network coding itself may provide confidentiality, its effectiveness heavily depends on the underlying network topology and ability of the eavesdroppers. Finally, broadcast encryption and group key agreement techniques both allow a sender to broadcast the same ciphertext to all the receivers, although they rely on the assumptions of trusted key servers or secure channels. In this paper, we propose a novel public-key encryption concept with a single public-key for encryption and multiple secret keys for decryption (MSK-PK), which has limited ciphertext expansion and does not require trusted key servers or secure channels. To demonstrate the feasibility of this concept, we construct a concrete scheme based on a class of lattice-based multi-trapdoor functions. We prove that those functions satisfy the one-wayness property and can resist the nearest plane algorithm.
  • Efficient group communication using multi-cast networks is important for many popular and emerging applications, such as social networks, instant messaging, and peer-to-peer electronic trading using distributed ledgers. To that end, the concept of network coding has been proposed to maximize the throughput of multi-cast networks by allowing intermediate nodes to modify and combine packets before forwarding them[1]. Later, Li et al. show that linear coding suffices to achieve the max-flow from the source to each sink node in a multi-cast network[2], and Jaggi et al. gave polynomial time algorithms for designing linear codes for acyclic directed graphs[3]. The security of network coding has also received attentions lately, such as Ref.[4], message authentication code[5] and digital signature[6] schemes for protecting data and origin integrity.

    However, protecting the confidentiality for network coding in multi-cast networks faces unique challenges. Although existing secure network coding schemes may provide limited data confidentiality[7], their reliability, effectiveness, and stability heavily depend on the underlying network topology and the capability of eavesdroppers. For instance, the network coding construction in Ref.[7] relies on assumptions about the number of edges that have been eavesdropped, which means the confidentiality might be breached if the eavesdroppers can access extra edges or when part of the network topology is changed. On the other hand, the design of secure network coding usually aims at theoretical security bounds under information theory, which may not always be necessary in practice. Instead, an interesting question is whether there exists a cryptographic primitive that can facilitate network coding while providing confidentiality independent of the network topology.

    To that end, conventional public-key cryptosystems are usually not satisfactory. In a multi-cast network, a source node who wants to send a message to n sink nodes must encrypt the same message n times using n different public-keys. In this case, the benefit of multi-cast and network coding cannot be easily attained, since each of the n ciphertexts must be transmitted separately to each sink node, and intermediate nodes will not be able to easily modify or combine those ciphertexts. Therefore, a conventional public-key cryptosystem will lead to low transmission efficiency if it is directly applied to such applications. On the other hand, broadcast encryption (see Refs.[8, 9]) allows the sender to broadcast a secret to any subset of privileged users, while users not in this subset cannot learn anything about the secret even if all of them collude. However, a broadcast encryption scheme typically requires a trusted party to first generate and send private keys to the users via secure channels before broadcasting the ciphertext. To eliminate the need for a trusted party, Wu et al.[10] introduce the contributory broadcast encryption by combining broadcast encryption with group key agreement protocols; however, the scheme assumes that a group of members will negotiate a common public encryption key in advance.

    In this paper, we propose a novel public-key encryption concept, namely, the MSK-PK cryptosystem, which has a single public-key for encryption and multiple secret decryption keys. In contrast to traditional broadcast encryption schemes, MSK-PK does not need a trusted party to generate all the users’ private keys, nor does it require a group of members to negotiate their common public-key in advance. In a single-source multi-cast network without any secure channels, MSK-PK allows the source node to take advantage of network coding by using a single public-key for encryption, while the corresponding secret-keys are generated by the sink nodes independently. More specifically, MSK-PK works as follows.

    1) Each client generates his/her secret-key and the corresponding public-key;

    2) Each client adds his/her own public-key to the request and sends to the server;

    3) The server collects all the public-keys and generates a new common public-key for encryption;

    4) The server encrypts the requested data using the common public-key, and sends the ciphertext as well as the common public-key to all the clients through multicast using network coding;

    5) Each client receives the ciphertext and decrypts it using his/her own secret-key.

    There actually exists a trivial construction as follows. To generate the common public-key for n clients in step 3) above, the server simply concatenates all the n public-keys. Then, in step 4), the server encrypts the data using each of the n public-keys, and concatenates the results as the final ciphertext. However, in this case, the length of the ciphertext will expand n times. This realization is basically the conventional public-key encryption schemes and can not enjoy the benefits from network coding as each sink node receives too much redundant information except the ciphertext he/she is able to decrypt. To the best of our knowledge, there exists no related work on the design of non-trivial MSK-PK schemes with less ciphertext expansion. In the remainder of this paper, we propose to obtain such non-trivial MSK-PK schemes from the construction of multi-trapdoor functions based on some hard problems in lattice. We prove the one-wayness of our multi-trapdoor functions and show the resistance against the nearest plane algorithm. We also give an upper bound on the length of the ciphertext for our construction.

    The remainder of this paper is organized as follows. We will use lattice as our main tool, and the formal definitions and necessary preliminaries are introduced in Section Ⅱ. In Section Ⅲ, we give the definition of our public-key cryptosystem with multiple secret-keys. The main construction of the multi-trapdoor one-way functions is presented in Section Ⅳ. Finally, in Section Ⅴ we give some security analysis.

    In this section, we provide a brief review of lattice and some of its hard problems, which will be necessary for further discussions. A lattice is a discrete subgroup of the additive group of Rn. Lattice has become a widely-used tool in cryptography due to the hard problems about its geometric structure. The applications of the lattices include constructing one-way functions[11], collision-free hash functions[12], digital signature schemes[13], encryption schemes[14-20], and particularly the first fully homomorphic encryption scheme[19]. The construction of one-way functions in this paper is based on Ref.[19].

    Definition 1 (Lattice) Let B={b1,,bn} be a collection of independent vectors in Rn. Then the lattice defined by B is

    L(B)def={ni=1kibi:kiZ,i=1,,n}

    If c1,,cn are in a lattice L and L={ni=1kici:kiZ,i=1,,n}, then we say c1,,cn is a base of L. Supppose B={b1,,bn} is a base of L. Let

    P(B)def={ni=1tibi:12ti<12,i=1,,n}

    then for any xRn, there exists one and only one yP(B) which is referred as xmodB such that xyL.

    Definition 2 (Ideal lattice) Let Z[x] be the integral coefficient polynomial ring, f(x)Z[x] a monic polynomial of degree n. Then hn1xn1++h1x+h0(hn1,,h1,h0) is a group homomorphism between R=Z[x]/(f(x)) as an additive group and Zn. So R can be seen as the lattice Zn and it is easy to see that the ideal of R is a sublattice of Zn. We call the ideal of R an ideal lattice and the principal ideal of R a principal ideal lattice.

    The following are some facts about lattice. We will use the same symbol to denote a base of a lattice and the matrix consisting of the vectors in the base as column vectors in the following.

    Theorem 1 Let L(B) be an n-dimensional lattice, then CRn×n is a base of L(B) if and only if there exists a unimodular matrix U such that C=BU.

    Therefore, for any base of a lattice L, |det(B)| is a positive constant denoted by det(L). And det(L) is called the determinant of the lattice.

    Theorem 2 Let L be a lattice and suppose LL is a sublattice having the same dimension with L, then det(L)/det(L) is a positive integer. Specifically, det(L)det(L), with the equality holds if and only if L=L.

    Theorem 3 Let f(x) be a monic polynomial with integral coefficients, and R= Z[x]/(f(x)), vR. Then Bv={v×xi(mod f(x)):i=0,,n1} is a base of lattice (v) which is the principal ideal generated by v, i.e., (v)=L(Bv). Bv is called the rotation base of (v). Moreover, we have that for any u,vRBu×v=BuBv.

    Note that, in Theorem 3, we suppose the matrix Bv is full-rank. When f is irreducible, the condition will always be satisfied and this is the case we will focus on in the following. However, even if Bv is not full-rank, the columns of Bv can also generate the principal lattice (v).

    Theorem 4 (Minkowski) For an n-dimensional lattice L, we have

    λ1(L)n(detL)1n

    where λ1(L) is the length of the shortest vector in L.

    The following are some hard problems on lattice:

    1) Shortest vector problem (SVP): Given a base of a lattice, find the shortest vector in the lattice.

    2) Closest vector problem (CVP): Given a base of a lattice and a vector, find the closest lattice point to the vector.

    3) Shortest independent vectors problem (SIVP): Given a base of an n-dimensional lattice, find n independent vectors in the lattice such that the norm of the vectors is minimal, where the norm of a collection of vectors means the length of the longest one.

    Most of the lattice-based encryption schemes are based on the approximation versions of the above problems. A detailed discussion and deduction about some common versions of lattice problems can be found in Ref.[21].

    In this section, we define our MSK-PK public-key cryptosystem with multiple secret-keys. To motivate the discussions, consider the multi-cast network model shown in Fig.1. Suppose the source node S wants to send the same data to all the sink nodes T1,T2,,Tn using network coding. As mentioned earlier, network coding requires that each intermediate node (e.g., I1) must be able to modify and combine the messages destined to different sink nodes (e.g., T1, T2 and T3). Conventional public-key encryption is not suitable for such a case, since it either prevents network coding (if S encrypts the messages using different private keys of the sink nodes) or requires the sink nodes to share a common private key, which is not realistic in practice. A natural question is therefore: Can we design an encryption scheme to support such a scenario with a single public-key for encryption by S, and different secret-keys for decryption by T1,T2,,Tn? For simplicity, we will assume network coding is always in place, and omit the intermediate nodes in further discussions.

    Figure  1.  Multi-cast network

    We define our MSK-PK public-key cryptosystem with multiple secret-keys as follows.

    Definition 3 (MSK-PK scheme) A public-key encryption scheme with multiple secret-keys is a set of probabilistic polynomial-time algorithms Setup, KeyGen, PKGen, Enc, Dec that satisfies the following:

    1) Setup takes as input a security parameter 1k and an integer s bounding the most secret-keys that are allowed. Setup outputs the algorithms KeyGen, PKGen, Enc, Dec and the plaintext space P.

    2) KeyGen outputs a pair of keys (pk,sk) each time, pk is the public-key and sk is the secret-key.

    3) PKGen takes (pk1,,pkn)(ns) as input. It outputs PK as a public-key for encryption and the ciphertext space C, where pk1,, pkn are the public-keys generated by KeyGen in step 2).

    4) Enc takes (PK,m) as input and outputs the ciphertext c, where mP.

    5) Dec takes (ski,{pki}ni=1,c) as input and outputs mP, where the secret-key ski is corresponding to the public-key pki in step 3).

    6) Let ln be the length of ciphertext when there are n secret-keys. It is required that ln<nl1.

    It is required that for all (1k,s), KeyGen, PKGen Enc, Dec which are determined by Setup(1k,s), and (pk1,sk1),,(pkn,skn) output by KeyGen, PK= PKGen(pk1,,pkn), mP, the following holds:

    Dec(ski,{pki}ni=1,Enc(PK,m))=m,i=1,,n.

    There is a trivial realization for the Definition 3 if we were to ignore the condition 6). Suppose Π=(Gen,Enc,Dec) is a public-key encryption scheme. Let Gen function be Setup and KeyGen, and PKGen outputs what it takes as input. Enc encrypts the plaintext with each public-key and concatenates the results. Dec decrypts the corresponding part of the ciphertext with a secret-key. i.e.

    PK=(pk1,,pkn)
    Enc(PK,m)=(Enc(pk1,m),,Enc(pkn,m))
    Dec(ski,(c1,,cn))=Dec(ski,ci)

    It is easy to see that, by simply encrypting the plaintext with different secret-keys and concatenating the ciphertexts to obtain the final ciphertext, the above scheme satisfies Definition 3 excluding condition 6). However, such a trivial construction is meaningless since each receiver essentially only needs 1/n (n is the number of receivers) of the ciphertext and the rest is redundant. One way to exclude such trivial constructions is by adding a limitation on the length of the ciphertext. Our definition above describes the limitation as that the ciphertext should not be longer than n times of the length of the ciphertext from an encryption scheme that has the same performance in terms of security, efficiency, etc. Note that when n is equal to 1 in Definition 3, the scheme is actually a normal public-key encryption scheme. Therefore, we can limit the length of ciphertext by comparing it with that of the case n=1, as described in above condition 6).

    Note For simplicity, in the above definition we suppose that PKGen is a deterministic algorithm. So Dec does not need the PK for decryption (for it can generate PK itself with {pki}ni=1). However, in some particular construction, Dec may only need PK instead of {pki}ni=1, so any receiver does not need others’ public-keys.

    The following provides the security definition of our scheme as usual. Given an encryption scheme Π=(Setup, KeyGen, PKGen, Enc, Dec) as defined in Definition 3 and an adversary A, consider the following experiment:

    Experiment 1 The eavesdropping experiment MSPubevaA,Π(k,s(k),n):

    1) Run Setup(1k,s) to obtain KeyGen, PKGen, Enc, Dec. And run KeyGen n times to obtain (pk1,sk1),,(pkn,skn).

    2) Adversary A is given pk1,,pkn and outputs a pair of messages m0,m1. Here the parameters (1k,s) and algorithms KeyGen,PKGen,Enc,Dec are known by A.

    3) A random bit b is chosen, PKGen is run to obtain pk=PKGen(pk1,,pkn), then the ciphertext cEnc(pk,mb) is computed and given to A.

    4) A outputs a bit b.

    5) The output of the experiment is defined to be 1 if b=b, and 0 otherwise.

    Definition 4 A public-key encryption scheme with multiple secret-keys Π=(Setup,KeyGen,PKGen, Enc,Dec) has indistinguishable encryption under chosen-plaintext attacks if for any integer ns and any probabilistic polynomial-time adversary A, there exists a negligible function negl such that:

    |Pr[MSPubevaA,Π(k,s(k),n)=1]12|<negl(k)

    where the probability is taken over the random coins used by A, as well as the random coins used to generate (pk1,sk1),...,(pkn,skn), choose b, and encrypt mb.

    In this section, we confirm the feasibility of constructing our MSK-PK encryption scheme by presenting a class of “multi-trapdoor” functions which can be used to construct the aforementioned scheme. Section IV.1 first defines our multi-trapdoor functions. Sections IV.2 and IV.3 provide detailed construction of the multi-trapdoor functions. Section IV.4 shows how to use such trapdoor functions to construct the MSK-PK encryption scheme.

    To construct our MSK-PK encryption scheme (as detailed in Definition 3), our main idea is to first generate a number of pairs of public-keys and secret-keys, and then to generate a new public-key from those public-keys such that ciphertexts encrypted using the new public-key can be decrypted using any of the aforementioned secret-keys. There are standard methods to obtain public-key encryption schemes in the random oracle model from trapdoor functions, for example the OAEP technique[22]. Therefore, we focus on designing a special class of “multi-trapdoor” functions which can be used to construct our MSK-PK encryption scheme.

    Definition 5 (Multi-trapdoor functions) A multi-trapdoor function is defined by a set of polynomial-time algorithms (Setup, Sample, Gen, F, G) satisfying:

    1) Setup takes as input (1n,s), where s is an integer, and outputs I, which defines the key set KI and the domain D.

    2) SampleI samples an element from KI. SampleI is run m times to get (pk1,sk1),, (pkm,skm), where ms.

    3) GenI takes pk1,,pkm as input and outputs a function index P as well as the range R.

    4) FI takes as input P and xD, and outputs yR. It is required that FI(P,) to be a one-way function and also injective.

    5) GI takes as input P,{pki}mi=1,yR and any ski,i{1,,m}, and outputs xD, satisfying GI(P,{pki}mi=1,ski,FI(P,x))=x, where I,P,ski,i=1,,m are as above.

    6) Let Cm denote the size of the range, then logCm<mlogC1.

    We note the following about Definition 5.

    • The function defined above is not a direct generalization of trapdoor function. In fact, as it can be seen, this is not even a normal function. We introduce it here as an intermediate form to construct the scheme described in Definition 3. Apparently, this cannot be used as an encryption scheme for its lack of semantic security. Here we refer to it as a function for simplicity.

    • The fifth condition in Definition 5 is added for the similar reason with the sixth condition in Definition 3, aiming to exclude the trivial construction from normal trapdoor function.

    • The algorithm Setup does not determine the domain and range of the function. Instead, they will eventually be determined after the keys are sampled. We may adjust the definition letting Setup output the domain and range. There is a notable difference between those two possible approaches to the definition. Suppose the scheme is an encryption scheme. If the plaintext space and ciphertext space are defined by Setup, then a receiver holding a valid secret-key can decrypt the ciphertext as soon as he/she receives it; if the domain and range are influenced by the public-keys, then the secret-keys holders have to learn all the other public-keys in some way. The drawback of the former is that as the length of the function value is fixed, there will be much redundancy when the number of secret-keys is small. However, the former can be seen as a special case of the latter. Therefore, for completeness we adopt the latter in Definitions 5 and 3.

    Suppose that B is a short base of a lattice L, than for a vector x, x(xmodB) is a lattice point with short distance from x. Therefore, a short base provides an algorithm to find a lattice point near a given vector while an arbitrary base cannot, which means a short base functions as a trapdoor. In the rest of the paper, all lattices are integral n-dimensional lattice in Rn and “n” is omitted for simplicity.

    Definition 6 Let B(x;r) denote the open ball of radius r centered at x, x may be omitted when it is the origin. The ith successive minima λi(L) is the radius of the smallest closed ball centered at the origin containing i linearly independent lattice vectors. When B are n linearly independent vectors, r(B) is denoted the supremum of {r:B(r)P(B)}.

    The author in Ref.[18] gives a somewhat homomorphic encryption scheme and turns it into a fully homomorphic one using the bootstrap technique. Here we describe a one-way function using the similar idea in the construction of the somewhat homomorphic encryption scheme in Ref.[18].

    One-way function[18]:

    Gen: Gen(n) generates (Bs,Bp,r), where Bs,Bp are bases of the same lattice and Bs is a short one, Bp is a random one. Let r be r(Bs).

    f(Bp,): For any mB(r)Zn, f(Bp,m)= mmodBpP(Bp).

    g(Bs,): For cP(Bp),g(Bs,c)=cmodBs.

    To see the correctness, note that for any xR, (xmodBp)=x+v for some lattice vector v. So when xP(Bs), which means (xmodBs)=x, we have

    g(Bs,f(Bp,x))=(xmodBp)modBBs=(x+v)modBs=xmodBs=x

    The one-wayness is roughly based on CVP. As Bp is a random base, (xmodBp) should be a “long” vector. If the closest lattice vector from (xmodBp) is v, then (xmodBp)v=x. So finding x means finding the closest vector v, which implies the one-wayness.

    To generalize the above method to obtain multiple trapdoors, we take a number of short bases(of different lattices) and let B be a base of the intersection of the lattices which is also a lattice. So we can use B as Bp in the above construction and any short bases can be used as Bs. A direct problem is that the new lattice may be too “small” or “sparse” which means the closest vector problem can be easy in this case. First we take a look at how sparse the intersection of two arbitrary lattices can be.

    Proposition 1 Let L(B1),L(B2)Zn×n be two integral lattices and L(B)= L(B1) L(B2). Then

    |det(B)||det(B1)|n|det(B2)|

    Moreover,

    |det(B)|min(|det(B1)|n|det(B2)|,|det(B1)||det(B2)|n) (1)

    Proof It can be seen that L(det(B1)B2)L(B1)L(B2). In fact, for any xZn, det(B1)B2x= B1B11det(B1)B2x=B1B1B2x=B1(B1B2x), where B1 is the adjoint of B1. Then B1B2xZn. So B1B2xZn. And we have |det(L(B1)L(B2))||det(L(det(B1)B2))|= |det(B1)|n|det(B2)|.

    The inequality is tight when the lattices are arbitrary. For example, take B1=pI,B2=qI, where I is identity matrix, p,q are relatively-prime, then equality holds in inequality (1). When the equality holds, the size of the range is |det(B1)|n|det(B2)| and the length in binary is nlog|detB1|+log|detB2| which is worse than the trivial realization (combining the two results of the original functions). What is worse is that the new construction is not one-way function any more.

    Principal ideal lattice works much better than the arbitrary ones. In the following, let f(x) be a monic integral polynomial of degree n, R=Z[x]/(f(x)), vR. An element in R, the corresponding polynomial and lattice vector are denoted by the same letter. Bv denotes the rotation base of the principal ideal lattice (v).

    Theorem 5 Suppose f(x) and R are as above. Let f(x) be irreducible, and u,vR, Bu,Bv be rotation bases. Then

    det(L(Bu)L(Bv))det(Bu)det(Bv).

    Proof. As (u)(v)(u×v), by Theorem 2 we have

    det(L(Bu)L(Bv))det(Bu×v).

    And by Theorem 3, det(Bu×v)=det(BuBv)=det(Bu)det(Bv), so it follows that

    det(L(Bu)L(Bv))det(Bu)det(Bv)

    Theorem 5 can be generalized to the case where more than two lattices intersect.

    Theorem 6 Suppose f(x),R are as in Theorem 5, and u1,...,ukR, then

    det(ki=1L(Bui))  ki=1det(L(Bui))

    After the discussion above, we describe a construction of one-way function with multiple trapdoors.

    Construction 1 One-way function with multiple trapdoors

    1) Setup(n,r). Outputs I=(f,r), DI=B(r), KI={(pk,sk):skKS,pk=skU, for some UU}, where f is an irreducible monic polynomial with integral coefficients and

    KS={BZn×n:detB0, P(B)B(r)L(B)=L(Bv),v Z[x]/(f)}U={uZn×n:det(u)=±1}

    2) Gen. Takes pk1=B1,,pkm=Bm as input, outputs a base BP of mi=1L(Bi) and the range P(BP).

    3) F. Takes xB(r)Zn as input and outputs y=xmodBPP(BP).

    4) G. Takes yP(BP), and BSi, as input and outputs G(y,BSi)=ymodBSi.

    The correctness of the above trapdoor function is trivial and is omitted.

    The domain of the conventional one-way function we give before is B(r)Zn where r=r(Bs) and the range is P(Bp)Zn. Clearly, vol(P(Bp))=vol(P(Bs)) >vol(B(r)). In other words, the range has more elements than the domain does which means some elements in the range would not be taken. To reduce these redundancy, we hope B(r) contains as many elements of vol(P(Bs)) as possible, i.e. vol(B(r))|det(BS)| or logvol(B(r))log|det(BS)|. Then in the multi-trapdoor case, we have vol(B(r))|det(BSi)|, i=1,,k, by Theorem 6, we have |det(BP)|ki=1|det(BSi)|vol(B(r))k|det(BS1)|k, Take the logarithm of the values we get the approximate relation of the length of the variable and the function value, log|det(BP)|logki=1|det(BSi)|logvol(B(r))klog|det(BS1)|k. i.e. log|det(BP)|ki=1log|det(BSi)|klog|det(BS1)|klog|det(BP1)|, where log|det(BP)| is the length of function value and log|det(BP1)| is the length of the input of the function. This relation shows that the construction meets the fifth condition in Definition 5.

    Let f(x),R are as above, then there exists a constant relating to R such that u,vR, it satisfies that u×vc(R)uv, where “×” is the multiplication in the ring R.

    Theorem 7[12] Let B be a base of an n-dimensional integral lattice, i.e. L(B) Zn, r=r(B). Then r=12((B)1)T, where is a matrix norm denoting the maximal l2 norm of the columns of a matrix.

    The next theorem gives a way to construct a short base of a principal ideal lattice.

    Theorem 8[18] Let f,R be as in Theorem 5, and c(R) be as above, a,bR satisfying bMnc(R)a, where M>1. If ube1+B(a), and Bu is the rotation base of u, then r(Bu)(1212M)b. Here ei denotes both the unit vector whose ith component is 1 and also the corresponding element in R.

    By Theorem 8, if M=2, then r(Bu) 14b. While the edges of P(Bu) is not longer than c(R)a+b, so when a is much smaller than b, we have λ(L(Bu))<c(R)a+bb. Also r=r(Bu)14b. It follows that λ(L(Bu))=Θ(r). We can also see that det(L(Bu))ni=1B(i)uni=1(c(R)a+b)=(c(R)a+b)n, where B(i)u is the ith column of the matrix of Bu. So (det(L(Bu)))1nc(R)a+bb. Moreover, the diameter of P(Bu) d<n(c(R)a+b)nb. That means the diameter of P(Bu) is not longer than 4n times of r(Bu).

    The last issue about Construction 1 is to find a base of the intersection of a number of lattices. It can be solved in a regular way. Here we focus on the case when only two lattices intersect, and the problem in general case can be solved by repeating the procedure in the simple case. Let A,BZn×n, detA0,detB0 be bases of two lattices. Then ZL(A)L(B) when there exists X,YZn satisfying Z=AX=BY. As AX=BYAXBY=0(AB)(XY)=0, denoting M=(A B),W=(XY), the last equality above can be written as MW=0. So computing the intersection of two integral lattice can be solved by finding integral solutions of homogeneous linear functions with integral coefficients. The latter problem can be solved via matrix decomposition.

    The OAEP (optimal asymmetric encryption padding)[23] and the subsequent OAEP+ techniques[24] allow constructing secure encryption schemes based on trapdoor permutations. Specifically, by applying OAEP, any one-way trapdoor permutation can be used to construct an encryption scheme which is semantically secure under chosen plaintext attack (CPA) in the random oracle model. Furthermore, OAEP+ provides semantic security under chosen ciphertext attack (CCA). OAEP can also be applied to multi-trapdoor functions in a similar way. Therefore, we will combine OAEP with a multi-trapdoor function to construct a MSK-PK scheme which is secure under CPA (CCA security can be obtained similarly by applying OAEP+).

    Suppose that F=(Setup, Sample, Gen, F,G) is a muti-trapdoor function as defined in Section IV.1. For simplicity, suppose that values in the domain of F are bit strings of length l(k), where k is the security parameter and l is a polynomial. We use OAEPG,H(m;r){0,1}l to denote the OAEP encoding, where m is the message to encode, r is the random string, and G, H are the random oracles used in the encoding. OAEP1G,H(y) denotes OAEP decoding, outputting a message or an error . The MSK-PK encryption scheme constructed based on the multi-trapdoor function F can be constructed as follows:

    Step 1: Setup runs Setup(1k,s) to obtain I.

    Step 2: KeyGen runs SampleI each time to obtain (pk,sk).

    Step 3: PKGen takes (pk1,...,pkn)(ns) as input. It runs GenI(pk1,...,pkn) to obtain P and let PK=P. Then it outputs PK as the public-key for encryption. Here we denote the domain D={0,1}l(k). The range R of the multi-trapdoor function is determined by P.

    Step 4: Enc takes (PK,m) as input, where m is a bit string with length l/4. Then, it samples r{0,1}l/2 and outputs c=FI(P,OAEPG,H(m;r)).

    Step 5: Dec takes (ski,{pki}ni=1,c) as input. It computes ˆm=GI(P,{pki}mi=1,ski,c), and then outputs OAEP1G,H(ˆm).

    When the algorithm PKGen is deterministic, the encryption public-key P can be derived from {pki}mi=1. Therefore, Dec does not require P while knowing {pki}mi=1. However, if PKGen is probabilistic, the input of Dec should involve P. We note that {pki}mi=1 may become unnecessary for decryption while knowing P (e.g., Construction 1 given in the following subsection is in this case).

    If the multi-trapdoor function F satisfies the last condition in Definition 5, the above MSK-PK scheme satisfies the last condition in Definition 3. The proof of the semantic security of this scheme is the same as that of the one-way trapdoor permutation case[23,24] and hence is omitted here.

    In Table 1, we show a brief comparison of known schemes realizing broadcast encryption, where n denotes the number of users. Our MSK-PK scheme would benefit from decreasing the length of common public-key significantly while making the ciphertext expansion no larger than the trivial realization.

    Table  1.  Feature Comparison of Schemes
    SchemeNecessary of secure channelLength of private-keyLength of public-keyCiphertext expansion
    Ref.[8] YES O(1) O(n) O(n)
    Ref.[10] NO O(n2/3) O(n) O(n2/3)
    Trivial realization NO O(1) O(n) O(n)
    Our MSK-PK scheme NO O(1) O(1) O(n)
     | Show Table
    DownLoad: CSV

    In this section, we discuss the one-way property of the function defined in Construction 1, and show that Nearest Plane algorithm cannot compute the pre-image.

    As we have seen in Section II, the two basic hard problems about lattice are shortest vector problem (SVP) and closest vector problem (CVP). The best known polynomial-time algorithms for the two problems are LLL algorithm[25] (and its improved versions) and Nearest Plane algorithm[26]. LLL algorithm takes a base of an n-dimensional lattice L and outputs a lattice vector with length no longer than 2n12λ1(L). Nearest Plane algorithm is based on LLL algorithm. It takes a base of an n-dimensional lattice L and a vector x as input, and outputs a lattice vector v satisfying xv2n2dist(x,L), where dist(x,L) denotes the distance between x and L.

    In Construction 1, we first choose some short bases B1,,Bk independently, satisfying B(r)P(Bi), i=1,,k, then compute a base Bp of the lattice ki=1L(Bi). The domain of the function is B(r)Zn and the function value is y=xmodBp. So inverting the function is equivalent to solving the CVP. The function value must not be too close to the lattice L(Bp) which means that r cannot be too small compared with λ1(L(Bp)). When r is too small, say r2n21λ1(L(Bp)), then Nearest Plane algorithm can find the pre-image y. Let the output of Nearest Plane algorithm be u, then yu2n2dist(y,L(Bp))2n22n21λ1(L(Bp))=12λ1(L(Bp)).

    By the inequality above, u is actually the nearest lattice vector.

    Here we will compare r and λ1(L(Bp)) in Construction 1. We should restrict λ1(L(Bp)) to be at most polynomial times larger than r. In the following, “x poly y” means x differs from y by at most a polynomial factor.

    By the discussion in Section IV.3, we can choose the base Bi such that (|detBi|)1n=Θ(r). By Theorem 4, λ1(L(Bp))n|detBp|1nn(ki=1|detBi|)1n=nki=1|detBi|1npolynrkpolyrk.

    The second inequality is by Theorem 6. If r is a polynomial of n, we have rkpolyr. So λ1(L(Bp))/r=Θ(nc), c is a constant, which means that λ1(L(Bp)) will not be too large compared with r and Nearest Plane algorithm cannot break the one-way property.

    The discussion above gives the one-way property of the trapdoor function in Construction 1. One-way injections can be used to construct public-key encryption schemes by some standard technique, for example OAEP (see more details in Section IV.4), thus Construction 1 yields an encryption scheme which resists against attacks based on Nearest Plane algorithm.

    In this paper, we introduce a cryptographic primitive, called public-key encryption scheme with multiple secret-keys (MSK-PK scheme), giving a possible construction and discussing its feasibility. We follow the standard way of constructing public-key encryption schemes from trapdoor permutations, and build a class of “multi-trapdoor” functions for this purpose. As far as we know, this is the first time that a method for constructing efficient MSK-PK schemes could be obtained. Comparing with some known broadcast encryption schemes, MSK-PK scheme has a significantly small length of generated common public-key (achieving O(1)). Our work may pave the way to designing practical encryption schemes to support efficient communications in multi-cast networks without secure channel.

  • [1]
    R. Ahlswede, N. Cai, S. Y. R. Li, et al., “Network information flow,” IEEE Transactions on Information Theory, vol.46, no.4, pp.1204–1216, 2000. DOI: 10.1109/18.850663
    [2]
    S. Y. R. Li, R. W. Yeung, and N. Cai, “Linear network coding,” IEEE Transactions on Information Theory, vol.49, no.2, pp.371–381, 2003. DOI: 10.1109/TIT.2002.807285
    [3]
    S. Jaggi, P. Sanders, P. A. Chou, et al., “Polynomial time algorithms for multicast network code construction,” IEEE Transactions on Information Theory, vol.51, no.6, pp.1973–1982, 2005. DOI: 10.1109/TIT.2005.847712
    [4]
    N. Cai and R. W. Yeung, “Secure network coding,” IEEE International Symposium on Information Theory, Lausanne, Switzerland, DOI: 10.1109/ISIT.2002.1023595, 2002.
    [5]
    S. Agrawal and D. Boneh, “Homomorphic MACs: MAC-based integrity for network coding,” 7th International Conference on Applied Cryptography and Network Security (ACNS 2009), Paris, France, pp.292–305, 2009.
    [6]
    D. Boneh, D. Freeman, J. Katz, et al., “Signing a linear subspace: Signature schemes for network coding,” International Workshop on Public Key Cryptography (PKC 2009), Irvine, CA, USA, pp.68–87, 2009.
    [7]
    K. Bhattad and K. R. Narayanan, “Weakly secure network coding,” availabel at: https://www.researchgate.net/publication/248407006_Weakly_Secure_Network_Coding, 2005.
    [8]
    D. Boneh, C. Gentry, and B. Waters, “Collusion resistant broadcast sencryption with short ciphertexts and private keys,” 25th Annual Int. Cryptology Conference (CRYPTO 2005), Santa Barbara, CA, USA, pp.258–275, 2005.
    [9]
    A. Fiat and M. Naor, “Broadcast encryption,” 13th Annual International Cryptology Conference (CRYPTO’ 93), Santa Barbara, CA, USA, pp.480–491, 2007.
    [10]
    Q. Wu, B. Qin, L. Zhang, et al., “Contributory broadcast encryption with efficient encryption and short ciphertexts,” IEEE Transactions on Computers, vol.65, no.2, pp.466–479, 2016. DOI: 10.1109/TC.2015.2419662
    [11]
    M. Ajtai, “Generating hard instances of lattice problems (extended abstract),” The 28th Annual ACM Symposium on Theory of Computing (STOC96), Philadelphia, PA, USA, pp.99–108, 1996.
    [12]
    O. Goldreich, Studies in Complexity and Cryptography - Miscellanea on the Interplay between Randomness and Computation, Berlin, Heidelberg: Springer, 2011.
    [13]
    Z. Liu, Y. Han, X. Yang, et al., “A generalized signcryption scheme based on LWE over rings,” Acta Electonica Sinica, vol.49, no.7, pp.1314–1322, 2021. (in Chinese)
    [14]
    L. Wu, Y. Han, X. Yang, et al., “Robust threshold proxy re-encryption scheme from ideal lattices,” Acta Electonica Sinica, vol.48, no.9, pp.1786–1794, 2020. (in Chinese)
    [15]
    M. Ajtai and C. Dwork, “A public-key cryptosystem with worst-case/average-case equivalence,” The 29th Annual ACM Symposium on Theory of Computing (STOC’97), El Paso, TX, USA, pp.284–293, 1997.
    [16]
    O. Goldreich, S. Goldwasser, and S. Halevi, “Public-key cryptosystems from lattice reduction problems,” 17th Annual International Cryptology Conference (CRYPTO’97), Santa Barbara, California, USA, pp.112–131, 1997.
    [17]
    J. Hoffstein, J. Pipher, and J. H. Silverman, “NTRU: A ring-based public key cryptosystem,” International Algorithmic Number Theory Symposium (ANTS 1998), Portland, OR, USA, pp.267–288, 1998.
    [18]
    C. Gentry, “A fully homomorphic encryption scheme,” PhD Thesis, Stanford University, USA, 2009.
    [19]
    C. Gentry, “Fully homomorphic encryption using ideal lattices,” The 41st Annual ACM Symposium on Theory of Computing (STOC’09), Bethesda, MD, USA, pp.169–178, 2009.
    [20]
    M. Coglianese and B. M. Goi, “MaTRU: A new NTRU-based cryptosystem,” 6th International Conference on Cryptology in India (INDOCRYPT 2005), Bangalore, India, pp.232–243, 2005.
    [21]
    D. Micciancio and O. Regev, “Worst-case to average-case reductions based on Gaussian measures,” SIAM Journal on Computing, vol.37, no.1, pp.267–302, 2007. DOI: 10.1137/S0097539705447360
    [22]
    J. Katz and Y. Lindell, Introduction to Modern Cryptography: Principles and Protocols, 1st ed., Chapman and Hall/CRC, 2007.
    [23]
    M. Bellare and P. Rogaway, “Optimal asymmetric encryption,” Workshop on the Theory and Application of Cryptographic Techniques (EUROCRYPT’94), Perugia, Italy, pp.92–111, 1995.
    [24]
    V. Shoup, “OAEP reconsidered,” Journal of Cryptology, vol.15, pp.223–249, 2002.
    [25]
    A. K. Lenstra, H. W. Lenstra, and L. Lovász, “Factoring polynomials with rational coefficients,” Mathematische Annalen, vol.261, no.4, pp.515–534, 1982. DOI: 10.1007/BF01457454
    [26]
    L. Babai, “On Lovász’ lattice reduction and the nearest lattice point problem,” Combinatorica, vol.6, no.1, pp.1–13, 1986. DOI: 10.1007/BF02579403
  • Related Articles

    [1]PENG Yuhuai, DENG Qingxu, GUO Lei, WANG Fanzhao. A New Network Coding Based Routing Protocol for Enhancing Throughput Capacity in Wireless Mesh Networks[J]. Chinese Journal of Electronics, 2019, 28(2): 416-422. DOI: 10.1049/cje.2019.01.015
    [2]XIE Jia, HU Yupu, GAO Juntao, JIANG Mingming. Certificateless Sequential Aggregate Signature Scheme on NTRU Lattice[J]. Chinese Journal of Electronics, 2019, 28(2): 294-300. DOI: 10.1049/cje.2019.01.019
    [3]NING Zuoting, ZHANG Dafang, LIU Xuchong. A Novel Approach of Network Coding in Wireless Networks Overhearing[J]. Chinese Journal of Electronics, 2018, 27(6): 1297-1304. DOI: 10.1049/cje.2018.06.010
    [4]ZHANG Xiaojun, XU Chunxiang, XIE Run, JIN Chunhua. Designated Cloud Server Public Key Encryption with Keyword Search from Lattice in the Standard Model[J]. Chinese Journal of Electronics, 2018, 27(2): 304-309. DOI: 10.1049/cje.2018.01.012
    [5]ZHU Weiling, YU Jianping, WANG Ting, ZHANG Peng, XIE Weixin. Efficient Attribute-Based Encryption from R-LWE[J]. Chinese Journal of Electronics, 2014, 23(4): 778-782.
    [6]LIU Hongwei, CAO Wenming. Public Proof of Cloud Storage from Lattice Assumption[J]. Chinese Journal of Electronics, 2014, 23(1): 186-190.
    [7]PENG Liqiang, ZUO Jinyin, HU Lei, XU Jun. Analysis of Two Public Key Cryptosystems Based on Randomized Knapsack Sequences[J]. Chinese Journal of Electronics, 2014, 23(1): 175-178.
    [8]GUANG Xuan, FU Fangwei. On Random Linear Network Coding for Butterfly Network[J]. Chinese Journal of Electronics, 2011, 20(2): 283-286.
    [9]DU Bing and ZHANG Jun. Parity Check Network Coding for WirelessCooperative Communications[J]. Chinese Journal of Electronics, 2010, 19(2): 339-344.
    [10]ZHOU Yejun, LI Hui, MA Jianfeng. Secure Network Coding Against the Contamination and Eavesdropping Adversaries[J]. Chinese Journal of Electronics, 2009, 18(3): 411-416.

Catalog

    Figures(1)  /  Tables(1)

    Article Metrics

    Article views (468) PDF downloads (25) Cited by()
    Related

    /

    DownLoad:  Full-Size Img  PowerPoint
    Return
    Return