
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 |
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
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
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
Definition 1 (Lattice) Let
L(B)def={n∑i=1kibi:ki∈Z,i=1,…,n} |
If
P(B)def={n∑i=1tibi:−12≤ti<12,i=1,…,n} |
then for any
Definition 2 (Ideal lattice) Let
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
Therefore, for any base of a lattice
Theorem 2 Let
Theorem 3 Let
Note that, in Theorem 3, we suppose the matrix
Theorem 4 (Minkowski) For an
λ1(L)≤√n(detL)1n |
where
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
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
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
1)
2)
3)
4)
5)
6) Let
It is required that for all
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
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
Note For simplicity, in the above definition we suppose that
The following provides the security definition of our scheme as usual. Given an encryption scheme
Experiment 1 The eavesdropping experiment
1) Run
2) Adversary
3) A random bit
4)
5) The output of the experiment is defined to be
Definition 4 A public-key encryption scheme with multiple secret-keys
|Pr[MSPubevaA,Π(k,s(k),n)=1]−12|<negl(k) |
where the probability is taken over the random coins used by
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
1)
2)
3)
4)
5)
6) Let
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
Suppose that
Definition 6 Let
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]:
To see the correctness, note that for any
g(Bs,f(Bp,x))=(xmodBp)modBBs=(x+v)modBs=xmodBs=x |
The one-wayness is roughly based on CVP. As
To generalize the above method to obtain multiple trapdoors, we take a number of short bases(of different lattices) and let
Proposition 1 Let
|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
The inequality is tight when the lattices are arbitrary. For example, take
Principal ideal lattice works much better than the arbitrary ones. In the following, let
Theorem 5 Suppose
det(L(Bu)⋂L(Bv))≤det(Bu)det(Bv). |
Proof. As
det(L(Bu)⋂L(Bv))≤det(Bu×v). |
And by Theorem 3,
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
det(k⋂i=1L(Bui)) ≤ k∏i=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)
KS={B∈Zn×n:detB≠0, P(B)⊇B(r)L(B)=L(Bv),v∈ Z[x]/(f)}U={u∈Zn×n:det(u)=±1} |
2)
3)
4)
The correctness of the above trapdoor function is trivial and is omitted.
The domain of the conventional one-way function we give before is
Let
Theorem 7[12] Let
The next theorem gives a way to construct a short base of a principal ideal lattice.
Theorem 8[18] Let
By Theorem 8, if
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
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
Step 1:
Step 2:
Step 3:
Step 4:
Step 5:
When the algorithm
If the multi-trapdoor function
In Table 1, we show a brief comparison of known schemes realizing broadcast encryption, where
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
In Construction 1, we first choose some short bases
By the inequality above,
Here we will compare
By the discussion in Section IV.3, we can choose the base
The second inequality is by Theorem 6. If
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
[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
|
[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. |