1. Introduction
1.1. Motivation
1.2. Problem Statements
1.3. System Model
1.4. Key Technique
 The set intersection operation can be omitted to avoid information leakage to Alice.
 The multiplication depth of the equality test can be reduced through batching.
 The number of homomorphic multiplications required for conjunctive equality tests can be decreased using the batch technique.
1.5. Previous Works
1.6. Our Contributions
 We propose an efficient batch private conjunctive query (BPCQ) protocol with the binary encoding, which we call the BPCQ_{2} protocol. Here, we use RLWEbased SwHE for providing security for the binaryencoded values appearing in the predicate of a query and the data in the database.
 As a main technique in our protocol, we develop a datapacking method with a concatenation technique to encode the binary fixedlength multidimensional data appearing in the query and the database to evaluate the PCQ in a few multiplications. Because of using this concatenation technique, our methods presented in this paper overcome the weakness stated in Section 1.5 for conjunctive query processing.
 We propose another efficient protocol for PCQ processing using an Nary fixedlength encoding ($N>2$), which we call the BPCQ_{N} protocol.
 Theoretically, we are able to reduce the lattice dimension by a factor of $\lceil {log}_{2}\left(N\right)\rceil $ in the BPCQ_{N} protocol because of using Nary fixedlength encoding rather than the binary fixedlength data encoding used in the BPCQ_{2} protocol.
 The developed datapacking method is modified to show how the Euclidean distance computation is used to decide conjunctive equality for the Naryencoded BPCQ_{N} protocol.
 Through comparative analysis, we demonstrate that the BPCQ_{N} protocol works at least four times faster than the BPCQ_{2} protocol because of using Nary data encoding.
1.7. Notations
1.8. Outline of This Paper
2. Security Tool
2.1. Asymmetric SwHE Scheme
 $\varphi \left(x\right)$ is a cyclotomic polynomial, where $\varphi \left(x\right)={x}^{n}+1$.
 n denotes the lattice dimension of the ring ${R}_{q}={\mathbb{Z}}_{q}\left[x\right]/\varphi \left(x\right)$, where $n\in \mathbb{Z}$. Here, the value of n is a power of 2, that is, $n={2}^{\Phi}$, where $\Phi \in \mathbb{Z}$.
 q: modulus q is an odd prime such that $q\equiv 1(\phantom{\rule{0.277778em}{0ex}}mod\phantom{\rule{0.277778em}{0ex}}\phantom{\rule{4pt}{0ex}}2n)$ defines the ring ${R}_{q}=R/qR={\mathbb{Z}}_{q}\left[x\right]\varphi \left(x\right)$, which denotes a ciphertext space.
 t is an integer $t<q$, which defines the message space of the scheme as ${R}_{t}={\mathbb{Z}}_{t}\left[x\right]\varphi \left(x\right)$, the ring of integer polynomials modulo $\varphi \left(x\right)$, and t.
 $\delta $ is a standard deviation, where $\delta =4\sim 8$. It is also used to represent a discrete Gaussian error distribution $\chi ={D}_{{\mathbb{Z}}^{n},\delta}$ with an ndimensional integer vector ${\mathbb{Z}}^{n}$.
2.1.1. Key Generation
2.1.2. Encryption
2.1.3. Homomorphic Evaluations
2.1.4. Decryption
2.2. Security of RLWEBased SwHE Scheme
2.3. Correctness of RLWEBased SwHE Scheme
3. Our Protocol
3.1. Protocol Scenario
3.2. Traditional Technique for Solving the PCQ Problem
3.3. Proposed Concatenation Technique for Solving PCQ Problem
3.4. Batch Technique for Boosting Performance
3.4.1. Batching for Traditional Methods
3.4.2. Batching for Concatenation Method
3.5. Batch Private Conjunctive Query Protocol
Inputs:$\mathbf{A}=({v}_{1},\cdots ,{v}_{k})$, ${\mathbf{B}}_{\sigma}=({\mathbf{B}}_{\sigma ,1},\cdots ,{\mathbf{B}}_{\sigma ,\eta})$ where ${v}_{i}=({a}_{i,0},\dots ,{a}_{i,{l}_{i}1})$ and ${\mathbf{B}}_{\sigma ,d}=({w}_{\sigma ,d,1},\cdots ,{w}_{\sigma ,d,k})$ for $1\le d\le \eta $ and $1\le \sigma \le p$. Output:$\left\right\{(\sigma ,d)\mathbf{A}={\mathbf{B}}_{\sigma ,d}\}$ BPCQ protocol:

3.6. Security of the Protocol
4. Data Representation and Its Packing Method
4.1. Data Representation for Conjunctive Query Processing
4.2. Packing Methods
4.3. Existing Packing Method
4.4. Our Packing Method
4.5. Obtaining the Multiple Inner Products
5. Improving the Batch Private Conjunctive Query Protocol
5.1. Binary vs. Nary Encoding
5.2. Private Conjunctive Query Protocol Using Nary Encoding
Inputs:$\mathbb{A}=({v}_{1}^{\prime},\cdots ,{v}_{k}^{\prime})$, ${\mathbb{B}}_{\sigma}=({\mathbb{B}}_{\sigma ,1},\cdots ,{\mathbb{B}}_{\sigma ,\eta})$, where ${v}_{i}=({a}_{i,0},\dots ,{a}_{i,{l}_{i}^{\prime}1})$ and ${\mathbb{B}}_{\sigma ,d}=({w}_{\sigma ,d,1}^{\prime},\cdots ,{w}_{\sigma ,d,k}^{\prime})$ for $1\le d\le \eta $ and $1\le \sigma \le p$. Output:$\left\right\{(\sigma ,d){\mathbb{B}}_{\sigma ,d}=\mathbb{A}\}$ BPCQ_{N} protocol:

5.3. Obtaining Multiple Inner Products
6. Homomorphic Evaluation of Private Conjunctive Query Protocols
6.1. Homomorphic Evaluation of the BPCQ_{2} Protocol
6.1.1. Evaluation Over Packed Ciphertext
6.1.2. Solving Additional Information Leakage Problem of the BPCQ_{N} Protocol
6.2. Homomorphic Evaluation of the BPCQ_{N} Protocol
7. Performance Analysis
7.1. Security Weaknesses and Countermeasures
7.1.1. Security Weaknesses
 When Charlie encrypts and sends Bob all the encrypted data with an insecure channel, Alice can eavesdrop. Alice provides Charlie with a public key and has a private key for it, so if Alice obtains Charlie’s encrypted data, Alice can obtain all the database’s information. This will compromise the basic security of the cryptographic protocol.
 Our protocols are unable to prevent realworld attacks by malicious adversaries because we followed the semihonest model for protocol security.
7.1.2. Countermeasures Against the Weaknesses
7.2. Theoretical Evaluation
7.3. Correctness
7.4. Experimental Settings
7.5. Security Analysis
7.6. Experimental Evaluation of the BPCQ_{2} Protocol
8. Comparative Performance Analysis with the Latest Research Methods
8.1. Correctness
8.2. Parameter Settings
8.3. Performance Comparison
9. Conclusions
Author Contributions
Funding
Acknowledgments
Conflicts of Interest
References
 Rivest, R.L.; Adleman, L.; Dertouzos, M.L. On Data Banks and Privacy Homomorphisms. Found. Secur. Comput. 1978, 4, 169–180. [Google Scholar]
 Rivest, R.L.; Shamir, A.; Adleman, L. A Method for Obtaining Digital Signatures and Publickey Cryptosystems. Commun. ACM 1978, 21, 120–126. [Google Scholar] [CrossRef]
 Gentry, C. Fully Homomorphic Encryption using Ideal Lattices. In Proceedings of the FortyFirst Annual ACM Symposium Theory Computimg (STOC), Bethesda, MD, USA, 31 May–2 June 2009; pp. 169–178. [Google Scholar]
 Cohen, J.D.; Fischer, M.J. A Robust and Verifiable Cryptographically Secure Election Scheme. In Proceedings of the 26th Annual Symposium on Foundations of Computer Science, Portland, OR, USA, 21–23 October 1985; pp. 372–382. [Google Scholar]
 ElGamal, T. A Public Key Cryptosystem and a Signature Scheme Based on Discrete Logarithms. In Proceedings of the Crypto 1984, Santa Barbara, CA, USA, 19–22 August 1984; Volume 196, pp. 10–18. [Google Scholar]
 Goldwasser, S.; Micali, S. Probabilistic Encryption & How to Play Mental Poker Keeping Secret All Partial Information. In Proceedings of the Fourteenth Annual ACM Symposium Theory Computing, San Francisco, CA, USA; 1982; pp. 365–377. [Google Scholar]
 Paillier, P. Publickey Cryptosystems Based on Composite Degree Residuosity Classes. In Proceedings of the International Conference Theory Application of Cryptographic Techniques, Prague, Czech Republic, 2–6 May 1999; Volume 1592, pp. 223–238. [Google Scholar]
 Benaloh, J. Dense Probabilistic Encryption. In Proceedings of the Workshop on Selected Areas of Cryptography, Kingston, ON, Canada, 5–6 May 1994; pp. 120–128. [Google Scholar]
 Boneh, D.; Goh, E.J.; Nissim, K. Evaluating 2DNF Formulas on Ciphertexts. In Proceedings of the 2nd TCC, Cambridge, MA, USA, 10–12 February 2005; Volume 3378, pp. 325–341. [Google Scholar]
 Brakerski, Z.; Vaikuntanathan, V. Fully Homomorphic Encryption from ringLWE and Security for Key Dependent Messages. In Proceedings of the 31st Annual Cryptology Conference, Santa Barbara, CA, USA, 14–18 August 2011; Volume 6841, pp. 505–524. [Google Scholar] [CrossRef]
 Chillotti, I.; Gama, N.; Georgieva, M.; Izabachène, M. Faster Fully Homomorphic Encryption: Bootstrapping in Less than 0.1 Seconds. In Proceedings of the International Conference on the Theory and Application of Cryptology and Information Security, Hanoi, Vietnam, 4–8 December 2016; Volume 10031, pp. 3–33. [Google Scholar] [CrossRef]
 Ducas, L.; Micciancio, D. FHEW: Bootstrapping Homomorphic Encryption in Less Than a Second. In Proceedings of the Eurocrypt 2015, Sofia, Bulgaria, 26–30 April 2015; Volume 9056, pp. 617–640. [Google Scholar]
 Van Dijk, M.; Gentry, C.; Halevi, S.; Vaikuntanathan, V. Fully Homomorphic Encryption Over the Integers. In Proceedings of the Eurocrypt 2010, Nice, France, 30 May–3 June 2010; Volume 6110, pp. 24–43. [Google Scholar]
 Brakerski, Z.; Gentry, C.; Vaikuntanathan, V. (Leveled) Fully Homomorphic Encryption Without Bootstrapping. ACM Trans. Comput. Theory 2014, 6, 1–36. [Google Scholar] [CrossRef]
 Hu, Y. Improving the Efficiency of Homomorphic Encryption Schemes. Ph.D. Thesis, Worcester Polytechnic Institute, Worcester, MA, USA, 2013. [Google Scholar]
 Lyubashevsky, V.; Peikert, C.; Regev, O. On Ideal Lattices and Learning with Errors over Rings. In Proceedings of the Eurocrypt 2010, Nice, France, 30 May–3 June 2010; Volume 6110, pp. 1–23. [Google Scholar] [CrossRef]
 Naehrig, M.; Lauter, K.; Vaikuntanathan, V. Can Homomorphic Encryption be Practical? In Proceedings of the 3rd ACM Workshop Cloud Computing Security Workshop, Chicago, IL, USA, 21 October 2011; pp. 113–124. [Google Scholar]
 Yasuda, M.; Shimoyama, T.; Kogure, J.; Yokoyama, K.; Koshiba, T. Secure Statistical Analysis Using RLWEbased Homomorphic Encryption. In Proceedings of the ACISP 2015, Brisbane, QLD, Australia, 29 June–1 July 2015; Volume 9144, pp. 471–487. [Google Scholar] [CrossRef]
 Saha, T.K.; Koshiba, T. An Enhancement of Privacypreserving Wildcards Pattern Matching. In Proceedings of the International Symposium on Foundations and Practice of Security—FPS 2016, Québec City, QB, Canada, 24–26 October 2016; Volume 10128, pp. 145–160. [Google Scholar]
 Yasuda, M.; Shimoyama, T.; Kogure, J.; Yokoyama, K.; Koshiba, T. Secure Pattern Matching Using Somewhat Homomorphic Encryption. In Proceedings of the 2013 ACM Workshop on Cloud Computing Security Workshop, Berlin, Germany, 8 November 2013; pp. 65–76. [Google Scholar]
 Saha, T.K.; Koshiba, T. Outsourcing Private Equality Tests to the Cloud. J. Inf. Secur. Appl. 2018, 43, 83–98. [Google Scholar] [CrossRef]
 Saha, T.K.; Koshiba, T. Privacypreserving Equality Test towards Big Data. In Proceedings of the International Symposium on Foundations and Practice of Security—FPS 2017, Nancy, France, 23–25 October 2017; Volume 10723, pp. 95–110. [Google Scholar] [CrossRef]
 Saha, T.K.; Rathee, M.; Koshiba, T. Efficient Private Database Queries Using RingLWE Somewhat Homomorphic Encryption. J. Inf. Secur. Appl. 2019, 49, 102406. [Google Scholar] [CrossRef]
 Saha, T.K.; Koshiba, T. Private Conjunctive Query over Encrypted Data. In Proceedings of the Africacrypt 2017, Dakar, Senegal, 24–26 May 2017; Volume 10239, pp. 149–164. [Google Scholar] [CrossRef]
 Saha, T.K.; Mayank; Koshiba, T. Efficient Protocols for Private Database Queries. In Proceedings of the 31st Annual IFIP WG 11.3 Conference on DBSec 2017, Philadelphia, PA, USA, 19–21 July 2017; Volume 10359, pp. 337–348. [Google Scholar]
 Saha, T.K.; Koshiba, T. An Efficient Privacypreserving Comparison Protocol. In Proceedings of the NBiS 2017, Toronto, ON, Canada, 24–26 August 2017; Volume 7, pp. 553–565. [Google Scholar]
 Wang, L.; Saha, T.K.; Aono, Y.; Koshiba, T.; Moriai, S. Enhanced Secure Comparison Schemes Using Homomorphic Encryption. In Proceedings of the Advances in NetworkedBased Information Systems—NBiS 2020, Victoria, BC, Canada, 31 August–2 September 2020; Volume 1264, pp. 211–224. [Google Scholar] [CrossRef]
 Cheon, J.H.; Kim, M.; Kim, M. Optimized Searchandcompute Circuits and Their Application to Query Evaluation on Encrypted Data. IEEE Trans. Inf. Forensics Secur. 2016, 11, 188–199. [Google Scholar] [CrossRef]
 Saha, T.K.; Koshiba, T. Private Equality Test Using RingLWE Somewhat Homomorphic Encryption. In Proceedings of the 2016 3rd AsiaPacific World Congress on Computer Science and Engineering (APWC on CSE), Nadi, Fiji, 5–6 December 2016; pp. 1–9. [Google Scholar] [CrossRef]
 Boneh, D.; Gentry, C.; Halevi, S.; Wang, F.; Wu, D.J. Private Database Queries Using Somewhat Homomorphic Encryption. In Proceedings of the ACNS 2013, Banff, AB, Canada, 25–28 June 2013; Volume 7954, pp. 102–118. [Google Scholar]
 Pappas, V.; Krell, F.; Vo, B.; Kolesnikov, V.; Malkin, T.; Choi, S.G.; George, W.; Keromytis, A.; Bellovin, S. Blind Seer: A Scalable Private DBMS. In Proceedings of the IEEE Symposium on Security and Privacy, San Jose, CA, USA, 18–21 May 2014; pp. 359–374. [Google Scholar] [CrossRef]
 Yao, A.C. Protocols for Secure Computations. In Proceedings of the 23rd Annual Symposium Foundations Computing Science, Chicago, IL, USA, 3–5 November 1982; pp. 160–164. [Google Scholar]
 Fisch, B.A.; Vo, B.; Krell, F.; Kumarasubramanian, A.; Kolesnikov, V.; Malkin, T.; Bellovin, S.M. Maliciousclient Security in Blind Seer: A Scalable Private DBMS. In Proceedings of the 36th IEEE Symposium on Security and Privacy (S&P), San Jose, CA, USA, 18–20 May 2015; pp. 395–410. [Google Scholar]
 Kim, M.; Lee, H.T.; Ling, S.; Wang, H. On the Efficiency of FHEbased Private Queries. IACR Cryptol. ePrint Arch. 2015, 2015, 1176. [Google Scholar] [CrossRef]
 Kim, M.; Lee, H.T.; Ling, S.; Ren, S.Q.; Tan, B.H.M.; Wang, H. Search Conditionhiding Query Evaluation on Encrypted Databases. IEEE Access 2019, 7, 161283–161295. [Google Scholar] [CrossRef]
 Yasuda, M.; Shimoyama, T.; Kogure, J.; Yokoyama, K.; Koshiba, T. Practical Packing Method in Somewhat Homomorphic Encryption. In DPM/SETOP2013; GarciaAlfaro, J., Lioudakis, G., CuppensBoulahia, N., Foley, S., Fitzgerald, W.M., Eds.; Springer: Heidelberg, Germany, 2014; Volume 8247, pp. 34–50. [Google Scholar] [CrossRef]
 Kandah, F.; Singh, Y.; Zhang, W. Mitigating Eavesdropping Attack Using Secure Key Management Scheme in Wireless Mesh Networks. J. Commun. 2012, 7, 596–605. [Google Scholar] [CrossRef]
 Goldreich, O.; Micali, S.; Wigderson, A. How to Play Any Mental Game. In Proceedings of the 19th annual ACM Symposium Theory Computing, New York, NY, USA, 25–27 May 1987; Aho, A., Ed.; ACM Press: New York, NY, USA, 1987; pp. 218–229. [Google Scholar]
 Ishai, Y.; Prabhakaran, M.; Sahai, A. Founding Cryptography on Oblivious Transfer–Efficiently. In Proceedings of the CRYPTO 2008, Santa Barbara, CA, USA, 17–21 August 2008; Volume 5157, pp. 572–591. [Google Scholar]
 Barker, E. NIST Special Publication 80057—Part 1 Revision 4; Recommendation for Key Management—Part 1: General, Dept. Commerce; National Institute of Standard and Technology: Gaithersburg, MD, USA, 2016. [CrossRef]
 Barker, E.; Roginsky, A. Transitioning the Use of Cryptographic Algorithms and Key Lengths; Technical Report; National Institute of Standards and Technology: Gaithersburg, MA, USA, 2018.
 Micciancio, D.; Regev, O. PostQuantum Cryptography; Springer: Heidelberg, Germany, 2009; pp. 147–191. ISBN 9783540887010. [Google Scholar]
 Lindner, R.; Peikert, C. Better Key Sizes (and Attacks) for LWEbased Encryption. In Proceedings of the CTRSA 2011, San Francisco, CA, USA, 14–18 February 2011; Volume 6558, pp. 319–339. [Google Scholar]
 Chen, Y.; Nguyen, P.Q. BKZ 2.0: Better Lattice Security Estimates. In Proceedings of the ASIACRYPT 2011, Seoul, Korea, 4–8 December 2011; Volume 7073, pp. 1–20. [Google Scholar]
 PARI Group. PARI/GP Version 2.7.5. Bordeaux, 2014. Available online: https://pari.math.ubordeaux.fr/archives/pariannounce15/msg00004.html (accessed on 24 August 2018).
Operation  Data Size  Depth of Multiplication  

Cheon et al.’s method [28]  Our method  
Equality  lbit  $logl$  $log3$ 
Index  Parameters $(\mathit{n},\mathit{q},\mathit{t},\mathit{\delta})$  Data Size  Block Size ($\mathit{\eta}$) 

1  $(3000,61\phantom{\rule{4.pt}{0ex}}\mathrm{bits},2048,8)$  15 bits  100 
2  $(6000,63\phantom{\rule{4.pt}{0ex}}\mathrm{bits},2048,8)$  15 bits  
3  $(3200,61\phantom{\rule{4.pt}{0ex}}\mathrm{bits},2048,8)$  16 bits  
4  $(6400,63\phantom{\rule{4.pt}{0ex}}\mathrm{bits},2048,8)$  16 bits  
5  $(3200,61\phantom{\rule{4.pt}{0ex}}\mathrm{bits},2048,8)$  16 bits  
6  $(6400,63\phantom{\rule{4.pt}{0ex}}\mathrm{bits},2048,8)$  16 bits 
Index  $\mathit{\delta}$  Query Size (bits)  Lattice Dimension (n)  Modulas (q)  Plaintext Space (t)  

BPCQ_{2}  BPCQ_{N}  BPCQ_{2}  BPCQ_{N}  BPCQ_{2}  BPCQ_{N}  
1  8  19  32,768  4096  69 bits  73 bits  2048  65,536 
2  8  19  65,536  8192  71 bits  75 bits  2048  65,536 
3  8  19  131,072  16,384  73 bits  77 bits  2048  65,536 
Publisher’s Note: MDPI stays neutral with regard to jurisdictional claims in published maps and institutional affiliations. 
© 2021 by the authors. Licensee MDPI, Basel, Switzerland. This article is an open access article distributed under the terms and conditions of the Creative Commons Attribution (CC BY) license (http://creativecommons.org/licenses/by/4.0/).