# NTRU Implementation of Efficient Privacy-Preserving Location-Based Querying in VANET

Authors: Bo Mi; Darong Huang; Shaohua Wan
Journal: Wireless Communications and Mobile Computing
 (2018)

---

## Abstract

The key for location-based service popularization in vehicular environment is security and efficiency. However, due to the constrained resources in vehicle-mounted system and the distributed structure of fog computation, disposing of the conflicts between real-time implementation and user’s privacy remains an open problem. Aiming at synchronously preserving the position information for users as well as the data proprietorship of service provider, an efficient location-based querying scheme is proposed in this paper. We argue that a recent scheme proposed by Jannati and Bahrak is time-consuming and vulnerable against active adaptive corruptions. Thus accordingly, a postquantum secure oblivious transfer protocol is devised based on efficient NTRU cryptosystem, which then serves as the understructure of a complete location-based querying scheme in ad hoc manner. The security of our scheme is proved under universal composability frame, while performance analysis is also carried out to testify its efficiency.


---

## Body

## 1. Introduction

With the development and fusion of techniques such as sensing, controlling, communication, positioning, and fog computation, vehicular ad hoc network (VANET), which is identified as a specific application of Internet of Things (IoT), has become a promising understructure to enhance traffic safety and convenience. As an important element of the intelligent transportation system (ITS), VANET is typically composed of numerous on-board units (OBU) equipped on vehicles and road-side units (RSUs) serve as infrastructure [1]. Different from traditional networking, vehicular ad hoc network emphasizes heavily on adaptive computation as well as communication of end-users and edge devices, which is characterised as localized data storage, dense geographical distribution, boundary service providing, and compound data aggregation or analysis. A wide range of applications can be supported taking advantage of such fundamental installation; for example, when driving on the road, one can fall back on the VANET to locate services (shops, gas stations, etc.) on his route, or even be notified of any forecasted traffic condition along her itinerary. Though it is envisioned that the future transportation would be “information-driven” and “wirelessly enabled,” the problems of confidential and privacy-preserving communication remain insufficiently solved due to the broadcasting nature of VANET [2]. Moreover, since one of the most attractive applications of VANET is location-based querying, it is always self-extended to traditional networks such as Internet. As illustrated in Figure 1, any authorized on-board unit may access the querying service providers (QSPs) in backbone or local RSUs to inquire about interested information via various communication channels, which makes the security issue more complicated in such foggy environment.Figure 1
VANET extension.As for privacy, the user may not want anybody, including the infrastructure units or service providers, to be aware of any information about her query. That means it should either be impossible to link up a query with the real identity of the user or make the query itself indistinct to some extent. In order to accomplish privacy requirement, two research lines are followed in literatures.


### 1.1. Correlation Concealment

Due to the interactive nature of location-based querying, one can easily associate the identity of a user with a specific location which may severely violate the privacy of personal health condition, social relationships, habits, and so on. Accordingly, once the connectivity of inquired location and user ID are obscured, the sensitive information may be preserved to some extent. This kind of privacy-protection method includes the following.


#### 1.1.1. Anonymity and Pseudonym

The goal of cryptonym methods is to prevent an adversary from reidentifying the data source by exploiting any exposed information. It generally relies on the fact that most location-based services are not strictly dependent on the knowledge of user’s identity. Thereby, the most challenging issues turn into pseudonymous authentication, integrity, and nonrepudiation. Specifically, a large number of certificates are usually preloaded for each vehicle, which will be abandoned after usage in a short period of time. Coupled with reputation mechanisms, those certificates can thus be used to appraise credibility of anonymous sources or to fulfil the backtracking purpose [3]. Nevertheless, anonymity and pseudonym schemes are only robust to semihonest secure model, because malicious vehicles may not discard or update their certificates as required by the protocols [4].


#### 1.1.2. Mix Zones

The technique of mix zones is originally introduced by Beresford and Stajano [5], where the pseudonym should be exchange amongst all users within a same zone. The time interval when a vehicle passes through a mix zone is called the silent period, which means it must dumb its position so as to break off the connection between its identities at the entry and exit points. Palanisamy and Liu [6] investigated various context information in traffic environment that may reveal detailed trajectories such as geometrical or temporal constraints and devised the MobiMix approach directing against such privacy infringement. It is worth mentioning that the idea of k-anonymity presented by Gruteser and Grunwald [7] is always served as a combination of anonymity (pseudonym) and mix zone implementation. For example, Caballero-Gil et al. [8] exploited the spatial and temporal cloaking to calculate the k-anonymity set, which makes a vehicle indistinguishable from other k-1 counterparts. To avoid active corruption, if a number of complaints are received pertinent to a malicious node, a track algorithm can also be carried out to prevent further detriment. Aiming at Sybil attack, Feng et al. [9] bounded k-anonymity and reputation schemes together, which can effectively suppress the spread of false messages when updating the anonymity.


### 1.2. Query Fuzzification

The service of location-based querying can be deemed as a process of information retrieval, which means only the users care about the correctness or precision of the research outcomes. Therefore, lots of approaches are presented taking the advantage of information asymmetry between users and the server, including the following.


#### 1.2.1. Position Dummies

It is aiming to deceive the QSP by confounding the user’s true position together with multiple false locations [10–13]. Nevertheless, since the traffic networks are always scattered but structured, it is difficult to create dummies indistinguishable from the true position. In order to generate plausible dummies, Shankar et al. [14] proposed the SybilQuery approach, which obfuscates the real position with dummies chosen from a historical traffic database.


#### 1.2.2. Obfuscation

The idea behind position obfuscation is to intentionally reduce the precision of inquiry messages. Typically, the protocol proposed by Ardagna et al. [15] used a circular area to substitute the exact position of a user. Though the obfuscation area can be allodially determined by the querier, the trade-off between privacy and precision is of great significance. Thus, accordingly, Reynold et al. [16] introduced a model for probabilistic range queries depending on the overlapping size of the query area and the obfuscation shapes. Another way to obfuscate the user’s position is the coordinate transformation, where some geometric mappings are carried out on a series of users’ coordinates before sending to the server. However, in order to ensure the functionality of the QSP, it is impossible to find an all-sided protection scheme purely based on coordinate transformation because the service provider has to be able to determine the relative position of objects and areas to each other [17]. In addition, to preserve the trajectory of user, a great deal of spatiotemporal location obfuscation schemes are also proposed, which also took the temporal information associated with positions into account [18–25].


#### 1.2.3. Position Sharing

With the existence of several untrusted servers, location information can be mathematically calculated as a series of shares and distributed on different databases. This approach was first proposed by Dürr et al. [26] who split up the location information into shares of strictly limited precision. After retrieving adequate shares from multiple servers, the user can execute a combination algorithm which fuses them into a message of higher precision. In order to prevent attackers from deriving the precise position via coordinate relationships of a map, Skvortsov et al. took map knowledge into account [27] and further improved their protocol by optimizing the placement of shares in terms of servers’ trustworthiness [28]. Though position sharing schemes can also be implemented on account of obfuscation or coordinate transformation [29], cryptography-based fashions are preferable due security consideration [30].


#### 1.2.4. Cryptographic Approaches

Due to the capacities such as confidentiality, integrity, and authenticity, cryptographic primitives are taken as desirable building blocks to realize position privacy. For the sake of concealing the real identity of a user, ring or group signature are generally used to confound the querier as a member of a vehicular set [31, 32]. By using private information retrieval (PIR) technique, a QSP can answer queries without learning or revealing any information of the query [33, 34]. Meanwhile, since the computational result of ciphertext matches that of the plaintext, homomorphic cryptosystems are also valued as promising tools for location privacy application [35, 36].Nevertheless, the aforementioned approaches took only the querier’s position information as a target for protection and simply lost the sight of QSP’s data ownership. Practically, the charging models in nowadays always lie on a per-query basis which enable drivers to use the service in ad hoc manner and pay for their queries according to the quantity. With regard to the proprietorship of QSP’s records, Paulet et al. [37] proposed a location-based querying approach in the light of 1-out-n oblivious transfer (OTn1). Their scheme made use of an ElGamal cryptosystem which imposed an additional privacy property for the sender such that the receiver could learn at most one of the retrieved items. However, Jannati and Bahrak [38] caught the sight of its security defect arguing that the receiver is able to decrypt all ciphered records; thus the QSP’s data ownership cannot be preserved. In order to rectify the vulnerability of Paulet’s scheme, they also reconstructed the oblivious transfer part of it at the cost of higher computational overhead.It is well known that ElGamal encryption is defined over a cyclic groupG, whose security depends on the difficulty of computing discrete logarithms. Therefore, a large security parameter must be considered in order to make sure that it is unbreakable. Though other traditional public key cryptosystems may also be exploited as basic primitives to realize oblivious transfer, they are deficient in efficiency due to computational hardness assumptions depending on large parameters. For the same reason, these cryptosystems tend to be vulnerable with the advent of quantum machine era. The comparison of security parameters amongst diffident cryptosystems is given in Table 1.Table 1
Security parameters for diffident public key cryptosystems.
Mathematical problem Integer factorization Elliptic curve discrete logarithm Discrete logarithm Security level RSA (bits) ECC (bits) ElGamal (bits) Low security 1024 160 1024 Moderate security 2048 224 2048 Standard security 3072 256 3072 High security 7680 384 7680 Highest security 15360 512 15360During encryption phase, ElGamal requires two exponentiation operations, while one exponentiation should be correspondingly carried out for decryption. Since exponentiation on large numbers is always time-consuming and occupies a lot of memory, we argue that Jannati’s scheme is not efficient enough, especially under embedded environments. Moreover, though their scheme is proved to be secure under game-based verification, active and adaptive corruptions are simply ignored because CCA (chosen ciphertext attack) security is unachievable by ElGamal cryptosystem itself [39].In order to eliminate the defects of Jannati’s protocol, we take the advantage of NTRUEncrypt to implement privacy-preserving location-based querying. As a relatively new public key cryptosystem developed in 1996, the number theory research unit encryption (NTRU) [40] runs faster compared to other asymmetric encryption schemes and is more competitive to be realized in resource-constraint environments such as mobile devices or smart cards. Up till 2017, literatures can be found that introduce new parameters to resist currently known attacks and increase its computation power [41, 42]. According to the latest research [43], the parameters in Table 2 are considered secure.Table 2
Security parameters for NTRUEncrypt.
Mathematical problem Shortest vector problem Security level N q p Moderate security 401 2048 3 Standard security 439 2048 3 High security 593 2048 3 Highest security 743 2048 3As for Table2, the parameters, where N defines a truncated polynomial ring R=Zx/(xN-1) used in NTRUEncrypt and q,p are two moduli, are relatively smaller than that of traditional public key cryptosystems. Moreover, it uses only simple polynomial multiplications; the time of performing an NTRU operation increases only quadratically. Taking moderate security for example, if both exponentiation and polynomial multiplication are composed of log2q-bits modular multiplications, the former must invoke the basis q2/log2q times compared to Nlog2N of the latter. It is reported that, using a modern GTX280 GPU, a throughput of up to 200,000 encryptions per second can be reached at a security level of 256 bits [44], which is only approximately 20 times slower than a recent AES implementation [45]. Accordingly, we resort to the characteristics of high efficiency as well as postquantum security and employ NTRUEncrypt as a building block to realize oblivious transfer. Then, based on the novel OTn1 protocol, an adaptive secure location-based querying scheme can thus be achieved.The rest of this paper is organized as follows. We first give some preliminaries about oblivious transfer and NTRUEncrypt in Section2. In Section 3, a NTRU-based 1-out-n oblivious protocol will be devised in advance which is then used to structure the secure location-based querying scheme after describing the system model. Security analyses and performance evaluations are given in Sections 4 and 5. The paper is finally concluded in Section 6.


## 1.1. Correlation Concealment

Due to the interactive nature of location-based querying, one can easily associate the identity of a user with a specific location which may severely violate the privacy of personal health condition, social relationships, habits, and so on. Accordingly, once the connectivity of inquired location and user ID are obscured, the sensitive information may be preserved to some extent. This kind of privacy-protection method includes the following.


### 1.1.1. Anonymity and Pseudonym

The goal of cryptonym methods is to prevent an adversary from reidentifying the data source by exploiting any exposed information. It generally relies on the fact that most location-based services are not strictly dependent on the knowledge of user’s identity. Thereby, the most challenging issues turn into pseudonymous authentication, integrity, and nonrepudiation. Specifically, a large number of certificates are usually preloaded for each vehicle, which will be abandoned after usage in a short period of time. Coupled with reputation mechanisms, those certificates can thus be used to appraise credibility of anonymous sources or to fulfil the backtracking purpose [3]. Nevertheless, anonymity and pseudonym schemes are only robust to semihonest secure model, because malicious vehicles may not discard or update their certificates as required by the protocols [4].


### 1.1.2. Mix Zones

The technique of mix zones is originally introduced by Beresford and Stajano [5], where the pseudonym should be exchange amongst all users within a same zone. The time interval when a vehicle passes through a mix zone is called the silent period, which means it must dumb its position so as to break off the connection between its identities at the entry and exit points. Palanisamy and Liu [6] investigated various context information in traffic environment that may reveal detailed trajectories such as geometrical or temporal constraints and devised the MobiMix approach directing against such privacy infringement. It is worth mentioning that the idea of k-anonymity presented by Gruteser and Grunwald [7] is always served as a combination of anonymity (pseudonym) and mix zone implementation. For example, Caballero-Gil et al. [8] exploited the spatial and temporal cloaking to calculate the k-anonymity set, which makes a vehicle indistinguishable from other k-1 counterparts. To avoid active corruption, if a number of complaints are received pertinent to a malicious node, a track algorithm can also be carried out to prevent further detriment. Aiming at Sybil attack, Feng et al. [9] bounded k-anonymity and reputation schemes together, which can effectively suppress the spread of false messages when updating the anonymity.


## 1.1.1. Anonymity and Pseudonym

The goal of cryptonym methods is to prevent an adversary from reidentifying the data source by exploiting any exposed information. It generally relies on the fact that most location-based services are not strictly dependent on the knowledge of user’s identity. Thereby, the most challenging issues turn into pseudonymous authentication, integrity, and nonrepudiation. Specifically, a large number of certificates are usually preloaded for each vehicle, which will be abandoned after usage in a short period of time. Coupled with reputation mechanisms, those certificates can thus be used to appraise credibility of anonymous sources or to fulfil the backtracking purpose [3]. Nevertheless, anonymity and pseudonym schemes are only robust to semihonest secure model, because malicious vehicles may not discard or update their certificates as required by the protocols [4].


## 1.1.2. Mix Zones

The technique of mix zones is originally introduced by Beresford and Stajano [5], where the pseudonym should be exchange amongst all users within a same zone. The time interval when a vehicle passes through a mix zone is called the silent period, which means it must dumb its position so as to break off the connection between its identities at the entry and exit points. Palanisamy and Liu [6] investigated various context information in traffic environment that may reveal detailed trajectories such as geometrical or temporal constraints and devised the MobiMix approach directing against such privacy infringement. It is worth mentioning that the idea of k-anonymity presented by Gruteser and Grunwald [7] is always served as a combination of anonymity (pseudonym) and mix zone implementation. For example, Caballero-Gil et al. [8] exploited the spatial and temporal cloaking to calculate the k-anonymity set, which makes a vehicle indistinguishable from other k-1 counterparts. To avoid active corruption, if a number of complaints are received pertinent to a malicious node, a track algorithm can also be carried out to prevent further detriment. Aiming at Sybil attack, Feng et al. [9] bounded k-anonymity and reputation schemes together, which can effectively suppress the spread of false messages when updating the anonymity.


## 1.2. Query Fuzzification

The service of location-based querying can be deemed as a process of information retrieval, which means only the users care about the correctness or precision of the research outcomes. Therefore, lots of approaches are presented taking the advantage of information asymmetry between users and the server, including the following.


### 1.2.1. Position Dummies

It is aiming to deceive the QSP by confounding the user’s true position together with multiple false locations [10–13]. Nevertheless, since the traffic networks are always scattered but structured, it is difficult to create dummies indistinguishable from the true position. In order to generate plausible dummies, Shankar et al. [14] proposed the SybilQuery approach, which obfuscates the real position with dummies chosen from a historical traffic database.


### 1.2.2. Obfuscation

The idea behind position obfuscation is to intentionally reduce the precision of inquiry messages. Typically, the protocol proposed by Ardagna et al. [15] used a circular area to substitute the exact position of a user. Though the obfuscation area can be allodially determined by the querier, the trade-off between privacy and precision is of great significance. Thus, accordingly, Reynold et al. [16] introduced a model for probabilistic range queries depending on the overlapping size of the query area and the obfuscation shapes. Another way to obfuscate the user’s position is the coordinate transformation, where some geometric mappings are carried out on a series of users’ coordinates before sending to the server. However, in order to ensure the functionality of the QSP, it is impossible to find an all-sided protection scheme purely based on coordinate transformation because the service provider has to be able to determine the relative position of objects and areas to each other [17]. In addition, to preserve the trajectory of user, a great deal of spatiotemporal location obfuscation schemes are also proposed, which also took the temporal information associated with positions into account [18–25].


### 1.2.3. Position Sharing

With the existence of several untrusted servers, location information can be mathematically calculated as a series of shares and distributed on different databases. This approach was first proposed by Dürr et al. [26] who split up the location information into shares of strictly limited precision. After retrieving adequate shares from multiple servers, the user can execute a combination algorithm which fuses them into a message of higher precision. In order to prevent attackers from deriving the precise position via coordinate relationships of a map, Skvortsov et al. took map knowledge into account [27] and further improved their protocol by optimizing the placement of shares in terms of servers’ trustworthiness [28]. Though position sharing schemes can also be implemented on account of obfuscation or coordinate transformation [29], cryptography-based fashions are preferable due security consideration [30].


### 1.2.4. Cryptographic Approaches

Due to the capacities such as confidentiality, integrity, and authenticity, cryptographic primitives are taken as desirable building blocks to realize position privacy. For the sake of concealing the real identity of a user, ring or group signature are generally used to confound the querier as a member of a vehicular set [31, 32]. By using private information retrieval (PIR) technique, a QSP can answer queries without learning or revealing any information of the query [33, 34]. Meanwhile, since the computational result of ciphertext matches that of the plaintext, homomorphic cryptosystems are also valued as promising tools for location privacy application [35, 36].Nevertheless, the aforementioned approaches took only the querier’s position information as a target for protection and simply lost the sight of QSP’s data ownership. Practically, the charging models in nowadays always lie on a per-query basis which enable drivers to use the service in ad hoc manner and pay for their queries according to the quantity. With regard to the proprietorship of QSP’s records, Paulet et al. [37] proposed a location-based querying approach in the light of 1-out-n oblivious transfer (OTn1). Their scheme made use of an ElGamal cryptosystem which imposed an additional privacy property for the sender such that the receiver could learn at most one of the retrieved items. However, Jannati and Bahrak [38] caught the sight of its security defect arguing that the receiver is able to decrypt all ciphered records; thus the QSP’s data ownership cannot be preserved. In order to rectify the vulnerability of Paulet’s scheme, they also reconstructed the oblivious transfer part of it at the cost of higher computational overhead.It is well known that ElGamal encryption is defined over a cyclic groupG, whose security depends on the difficulty of computing discrete logarithms. Therefore, a large security parameter must be considered in order to make sure that it is unbreakable. Though other traditional public key cryptosystems may also be exploited as basic primitives to realize oblivious transfer, they are deficient in efficiency due to computational hardness assumptions depending on large parameters. For the same reason, these cryptosystems tend to be vulnerable with the advent of quantum machine era. The comparison of security parameters amongst diffident cryptosystems is given in Table 1.Table 1
Security parameters for diffident public key cryptosystems.
Mathematical problem Integer factorization Elliptic curve discrete logarithm Discrete logarithm Security level RSA (bits) ECC (bits) ElGamal (bits) Low security 1024 160 1024 Moderate security 2048 224 2048 Standard security 3072 256 3072 High security 7680 384 7680 Highest security 15360 512 15360During encryption phase, ElGamal requires two exponentiation operations, while one exponentiation should be correspondingly carried out for decryption. Since exponentiation on large numbers is always time-consuming and occupies a lot of memory, we argue that Jannati’s scheme is not efficient enough, especially under embedded environments. Moreover, though their scheme is proved to be secure under game-based verification, active and adaptive corruptions are simply ignored because CCA (chosen ciphertext attack) security is unachievable by ElGamal cryptosystem itself [39].In order to eliminate the defects of Jannati’s protocol, we take the advantage of NTRUEncrypt to implement privacy-preserving location-based querying. As a relatively new public key cryptosystem developed in 1996, the number theory research unit encryption (NTRU) [40] runs faster compared to other asymmetric encryption schemes and is more competitive to be realized in resource-constraint environments such as mobile devices or smart cards. Up till 2017, literatures can be found that introduce new parameters to resist currently known attacks and increase its computation power [41, 42]. According to the latest research [43], the parameters in Table 2 are considered secure.Table 2
Security parameters for NTRUEncrypt.
Mathematical problem Shortest vector problem Security level N q p Moderate security 401 2048 3 Standard security 439 2048 3 High security 593 2048 3 Highest security 743 2048 3As for Table2, the parameters, where N defines a truncated polynomial ring R=Zx/(xN-1) used in NTRUEncrypt and q,p are two moduli, are relatively smaller than that of traditional public key cryptosystems. Moreover, it uses only simple polynomial multiplications; the time of performing an NTRU operation increases only quadratically. Taking moderate security for example, if both exponentiation and polynomial multiplication are composed of log2q-bits modular multiplications, the former must invoke the basis q2/log2q times compared to Nlog2N of the latter. It is reported that, using a modern GTX280 GPU, a throughput of up to 200,000 encryptions per second can be reached at a security level of 256 bits [44], which is only approximately 20 times slower than a recent AES implementation [45]. Accordingly, we resort to the characteristics of high efficiency as well as postquantum security and employ NTRUEncrypt as a building block to realize oblivious transfer. Then, based on the novel OTn1 protocol, an adaptive secure location-based querying scheme can thus be achieved.The rest of this paper is organized as follows. We first give some preliminaries about oblivious transfer and NTRUEncrypt in Section2. In Section 3, a NTRU-based 1-out-n oblivious protocol will be devised in advance which is then used to structure the secure location-based querying scheme after describing the system model. Security analyses and performance evaluations are given in Sections 4 and 5. The paper is finally concluded in Section 6.


## 1.2.1. Position Dummies

It is aiming to deceive the QSP by confounding the user’s true position together with multiple false locations [10–13]. Nevertheless, since the traffic networks are always scattered but structured, it is difficult to create dummies indistinguishable from the true position. In order to generate plausible dummies, Shankar et al. [14] proposed the SybilQuery approach, which obfuscates the real position with dummies chosen from a historical traffic database.


## 1.2.2. Obfuscation

The idea behind position obfuscation is to intentionally reduce the precision of inquiry messages. Typically, the protocol proposed by Ardagna et al. [15] used a circular area to substitute the exact position of a user. Though the obfuscation area can be allodially determined by the querier, the trade-off between privacy and precision is of great significance. Thus, accordingly, Reynold et al. [16] introduced a model for probabilistic range queries depending on the overlapping size of the query area and the obfuscation shapes. Another way to obfuscate the user’s position is the coordinate transformation, where some geometric mappings are carried out on a series of users’ coordinates before sending to the server. However, in order to ensure the functionality of the QSP, it is impossible to find an all-sided protection scheme purely based on coordinate transformation because the service provider has to be able to determine the relative position of objects and areas to each other [17]. In addition, to preserve the trajectory of user, a great deal of spatiotemporal location obfuscation schemes are also proposed, which also took the temporal information associated with positions into account [18–25].


## 1.2.3. Position Sharing

With the existence of several untrusted servers, location information can be mathematically calculated as a series of shares and distributed on different databases. This approach was first proposed by Dürr et al. [26] who split up the location information into shares of strictly limited precision. After retrieving adequate shares from multiple servers, the user can execute a combination algorithm which fuses them into a message of higher precision. In order to prevent attackers from deriving the precise position via coordinate relationships of a map, Skvortsov et al. took map knowledge into account [27] and further improved their protocol by optimizing the placement of shares in terms of servers’ trustworthiness [28]. Though position sharing schemes can also be implemented on account of obfuscation or coordinate transformation [29], cryptography-based fashions are preferable due security consideration [30].


## 1.2.4. Cryptographic Approaches

Due to the capacities such as confidentiality, integrity, and authenticity, cryptographic primitives are taken as desirable building blocks to realize position privacy. For the sake of concealing the real identity of a user, ring or group signature are generally used to confound the querier as a member of a vehicular set [31, 32]. By using private information retrieval (PIR) technique, a QSP can answer queries without learning or revealing any information of the query [33, 34]. Meanwhile, since the computational result of ciphertext matches that of the plaintext, homomorphic cryptosystems are also valued as promising tools for location privacy application [35, 36].Nevertheless, the aforementioned approaches took only the querier’s position information as a target for protection and simply lost the sight of QSP’s data ownership. Practically, the charging models in nowadays always lie on a per-query basis which enable drivers to use the service in ad hoc manner and pay for their queries according to the quantity. With regard to the proprietorship of QSP’s records, Paulet et al. [37] proposed a location-based querying approach in the light of 1-out-n oblivious transfer (OTn1). Their scheme made use of an ElGamal cryptosystem which imposed an additional privacy property for the sender such that the receiver could learn at most one of the retrieved items. However, Jannati and Bahrak [38] caught the sight of its security defect arguing that the receiver is able to decrypt all ciphered records; thus the QSP’s data ownership cannot be preserved. In order to rectify the vulnerability of Paulet’s scheme, they also reconstructed the oblivious transfer part of it at the cost of higher computational overhead.It is well known that ElGamal encryption is defined over a cyclic groupG, whose security depends on the difficulty of computing discrete logarithms. Therefore, a large security parameter must be considered in order to make sure that it is unbreakable. Though other traditional public key cryptosystems may also be exploited as basic primitives to realize oblivious transfer, they are deficient in efficiency due to computational hardness assumptions depending on large parameters. For the same reason, these cryptosystems tend to be vulnerable with the advent of quantum machine era. The comparison of security parameters amongst diffident cryptosystems is given in Table 1.Table 1
Security parameters for diffident public key cryptosystems.
Mathematical problem Integer factorization Elliptic curve discrete logarithm Discrete logarithm Security level RSA (bits) ECC (bits) ElGamal (bits) Low security 1024 160 1024 Moderate security 2048 224 2048 Standard security 3072 256 3072 High security 7680 384 7680 Highest security 15360 512 15360During encryption phase, ElGamal requires two exponentiation operations, while one exponentiation should be correspondingly carried out for decryption. Since exponentiation on large numbers is always time-consuming and occupies a lot of memory, we argue that Jannati’s scheme is not efficient enough, especially under embedded environments. Moreover, though their scheme is proved to be secure under game-based verification, active and adaptive corruptions are simply ignored because CCA (chosen ciphertext attack) security is unachievable by ElGamal cryptosystem itself [39].In order to eliminate the defects of Jannati’s protocol, we take the advantage of NTRUEncrypt to implement privacy-preserving location-based querying. As a relatively new public key cryptosystem developed in 1996, the number theory research unit encryption (NTRU) [40] runs faster compared to other asymmetric encryption schemes and is more competitive to be realized in resource-constraint environments such as mobile devices or smart cards. Up till 2017, literatures can be found that introduce new parameters to resist currently known attacks and increase its computation power [41, 42]. According to the latest research [43], the parameters in Table 2 are considered secure.Table 2
Security parameters for NTRUEncrypt.
Mathematical problem Shortest vector problem Security level N q p Moderate security 401 2048 3 Standard security 439 2048 3 High security 593 2048 3 Highest security 743 2048 3As for Table2, the parameters, where N defines a truncated polynomial ring R=Zx/(xN-1) used in NTRUEncrypt and q,p are two moduli, are relatively smaller than that of traditional public key cryptosystems. Moreover, it uses only simple polynomial multiplications; the time of performing an NTRU operation increases only quadratically. Taking moderate security for example, if both exponentiation and polynomial multiplication are composed of log2q-bits modular multiplications, the former must invoke the basis q2/log2q times compared to Nlog2N of the latter. It is reported that, using a modern GTX280 GPU, a throughput of up to 200,000 encryptions per second can be reached at a security level of 256 bits [44], which is only approximately 20 times slower than a recent AES implementation [45]. Accordingly, we resort to the characteristics of high efficiency as well as postquantum security and employ NTRUEncrypt as a building block to realize oblivious transfer. Then, based on the novel OTn1 protocol, an adaptive secure location-based querying scheme can thus be achieved.The rest of this paper is organized as follows. We first give some preliminaries about oblivious transfer and NTRUEncrypt in Section2. In Section 3, a NTRU-based 1-out-n oblivious protocol will be devised in advance which is then used to structure the secure location-based querying scheme after describing the system model. Security analyses and performance evaluations are given in Sections 4 and 5. The paper is finally concluded in Section 6.


## 2. Preliminaries on 1-Out-n Oblivious Transfer and NTRUEncrypt

Oblivious transfer, originally introduced as conjugate coding, owns its name to Rabin [46]. Amongst different flavors of OT, 1-out-n oblivious transfer has been extensively studied in the literature since any cryptographic task can be achieved by this extremely basic primitive [47]. In cryptography, a 1-out-n oblivious transfer is a type of protocol in which a receiver R is entitled to obtain 1 out of n messages held by a sender S without learning any other messages, while the sender do not know which massage has been chosen. The protocol is formally described as in Table 3.Table 3
Oblivious transfer paradigmFOT.
Input (i)S input m0,m1,…,mn-1∈M (ii)R input δ∈0,1,…,n-1 Output (i)S output ⊥(i.e., nothing) (ii)R output mδIn order to optimize the performance of oblivious transfer protocol, several tricks can be imposed on it. For example, [48] enables the computation of many OTs with a small elementary cost from k OT at a normal cost and also enables to reduce oblivious transfers of long strings to oblivious transfers of short strings using a pseudorandom generator.In this paper, an efficient and secureOTn1 protocol will be constructed based on NTRUEncrypt in the light of its linearity and resistance to quantum machines. The NTRU encryption algorithm works on a truncated polynomial ring R=Zx/(xN-1) with convolution multiplication and all polynomials in the ring have integer coefficients and degree at most N-1:(1)ax=a0+a1x+a2x2+⋯+aN-1xN-1.Similar to the prime decomposition problem exploited by RSA, the security of NTRUEncrypt relies on hardness of factoring a reducible polynomial, which is equivalent to the shortest vector problem. Thus, it is infeasible to usurp the secret key if the parameters are chosen secure enough.For each system, three integer parameters(N,p,q) are specified, where p and q are two moduli who truncate the ring R as Rp=(Z/pZ)x/(xN-1) and Rq=(Z/qZ)x/(xN-1). It is always assumed that N,p are prime while q is coprime to both q and N. To generate a key pair, two key polynomials f and g whose coefficients lie within {-1,0,1} must be generated in advance. An additional requirement that there exist two inverses fp,fq, where f·fp=1modp and f·fq=1modq, must also be satisfied. Then, f together with fp can be preserved as the secret key, while h=p·fq·g will be published to be the public key.During encrypting phase, a messagem should be represented as a binary or ternary string and transformed into a truncated polynomial within the ring R. Then a binding polynomial r with small coefficients should be randomly chosen to calculate the ciphertext as (2)c=r·h+mmodq.In order to decrypt the cryptographc, the receiver first computes (3)a=f·cmodqand then lifts its coefficients to interval [-q/2,q/2] and achieves the plaintext as (4)m=fp·amodp.In order to prove the correctness of our protocols, a polynomial setT(d1,d2) specified by two parameters is defined in advance.Definition 1.
For any positive integersd1 and d2, (5)Td1,d2=d1cofficients  ofaxare1ax∈Rq:d2cofficients  ofaxare-1other  cofficients  ofaxare0.According to Definition1, the correctness of NTRU decryption can be guaranteed in terms of the condition described as below.Lemma 2.
If the polynomials of NTRU cryptosystem are chosen from(6)f∈Td+1,d,g∈Td,d,r∈Td,d,whose coefficients satisfy(7)q>p6d+1,then a legal receiver can accurately recover ciphertext c with her private key.Proof.
Since all polynomials of(8)a=p·g·r+f·mmodqare provided with coefficients designated by formula (6), the parameters of g·r after convolution polynomial multiplication will never overrange [-2d,2d]. Similarly, the parameters of f as well as m are located within [-p/2,p/2] which means that the maximal parameter of f·m is p(d+1/2) to its very extent. As a result, once the condition of q>p(6d+1) is met, all parameters of (8) can be lifted to [-q/2,q/2] without losing any information. Then by computing (9)fp·a=fp·p·g·r+m=mmodp,the message can accurately be recovered.


## 3. Location Privacy-Preserving Querying Based on NTRU

In this paper, a novel location-based querying scheme is proposed aiming at not only protecting the position privacy of drivers but also preserving the data proprietary of QSP. Specifically, three goals must be achieved in terms of security and feasibility.(a) Within authenticated but not confidential communication environments, any malicious third party is incapable of gaining or efficaciously modifying any information of the conversation.(b) Even if active and adaptive corrupted participant exists, the driver must be insensible of any data hold by QSP except the one she requested while keeping her querying information concealed.(c) The protocol should be feasible on both vehicle-mounted devices as well as location-based servers, which means that low computation and communication burden must be fulfilled.For clarity, a novel 1-out-n oblivious transfer protocol will be presented in the first place. Then we will employ it as the building block to complete our entire scheme.


### 3.1. NTRU Implementation of 1-Out-n Oblivious Transfer

Different from traditional public key cryptosystems, NTRU is structured on a truncated polynomial ring which is provided with both addition and multiplication. Since the time of performing convolution multiplication is much faster than that of modular exponentiation on large numbers, the preferable efficiency and security property of NTRU are more appropriate to construct the basic oblivious transfer protocol.In order to realize the NTRU-based 1-out-n oblivious transfer, the messages held by the sender are presented as m0,m1,…,mn-1, which must be kept unacquainted from the receiver except for mδ. Accordingly, we describe the primitive 1-out-n oblivious transfer protocol as below.During key generation phase, the sender constructs a key pair as in Section2, she releases her public key pk=h to all potential receivers or stores it in a communal database, while keeping the secret key sk=(f,fp) private.In oblivious transfer phase, the sender is supposed to choosen random polynomials γ0,γ1,…,γn-1 from Td,d, where ri·h can be represented as p·fq·γi, and encrypt all plaintexts to be (10)ci=ri·h+mimodq,i=0,1,…,n-1,which is then sent to the receiver.When all ciphertexts are received, the receiver first generates a random polynomials belonging to Td,d and figures out its inverse s-1(modp). If the inverse of polynomial s does not exist, she can simply resample another one and repeat the inversion process.After that, the receiver must single out theδth ciphertext and compute it as(11)cδ′=r′·h+s·cδmodq,utilizing another random polynomial r′ chosen from Td,d. The result will be sent back to the sender.Depending on the altered ciphertextcδ′, the sender can calculate(12)aδ=f·cδ′modq,bδ=aδmodpand then(13)cδ′′=fp·bδmodpto be her response for the driver.Since the driver is aware of polynomials, she can achieve the expected messages mδ by multiply cδ′′ with s-1modulo p.The above process is also characterized in Table4.Table 4
O T n 1 protocol based on NTRUEncrypt.
Server Driver Holdsn messages mi∈{0,1}N, Holdsδ,δ∈{0,1,…,n-1}. i = { 0 ,  1 ,  … , n - 1 } . Key generation phase ( q , p , f , f q , f p , g ) ← K e y G e n ( κ ), s k :  ( f , f p ), p k :  h, Sendspk to the driver.  Oblivious transfer phase For alli={0,1,…,n-1}, γ i ← R T d , d , c i = p ⋅ f q ⋅ γ i + m i ( m o d  q ) , Sends allci to the driver. r ′ ← R T d , d , s ← R T d , d, where s is reversible modulo p, c δ ′ = r ′ ⋅ h + s ⋅ c δ ( m o d  q ), Sendscδ′ back to the server. a δ = f ⋅ c δ ′ m o d  q, bδ=aδmodp, c δ ′ ′ = f p ⋅ b δ ( m o d  p ) , Sendscδ′′ to the driver. m δ = c δ ′ ′ ⋅ s - 1 ( m o d  p ).Correctness of the 1-out-n oblivious transfer protocol relies on the computation of polynomials in truncated polynomial ring, as follows.Lemma 3.
The driver can correctly obtain messagemδ if q>2p(2d2+5d).Proof.
Since the parameters ofg·r or γδ·s are seated within [-2d,2d] and the coefficients of f·s·mδ cannot exceed p2d2+d for polynomial aδ=p·g·r′+p·γδ·s+f·s·mδ(modq). No information will be lost when lifting the coefficients of aδ to [-q/2,q/2], if q>2p(2d2+5d) the same as Lemma 2. By computing mδ=cδ′′·s-1(modp), where cδ′′=s·mδ(modp), the driver can achieve the exact message mδ she expected.


### 3.2. Efficient and Secure Location-Based Querying

The system is modelled as a QSP and a series of vehicles. More specifically, the QSP can be considered working in a distributed manner, which is composed of a centralized authentication server together with numerous delivery RSUs. The reason behind such configuration is to separate data retrieval from transaction process, which not only preserves the driver’s position privacy but also abates the operating load of service centre. Resorting to the OBUs equipped on vehicles, drivers are able to determine their current position via localization devices such as GPS or WiFi.Ininitialization phase, the QSP first generates its key pair and divides the geography to be a public grid G composed of V rows and W columns. For each cell v×w of the grid, she assembles all related data as a message di, where i=w+v·W, 0≤v≤V-1, and 0≤w≤W-1, and encrypts it as di′=Emi=kv⊕kw(di) by symmetric cryptosystem E according to the keys kv, kw designated to each row and column. Then, the QSP stores its key pair together with all kv, kw as well as di′ in distributed RSUs.Inretrieving phase, the driver should complete both the payment and oblivious transfer process as follows.In order to actualize the requirement of pay-per-retrieval for location-based service, the driver should ask for a random numberr- from its adjacent RSU and sign it using her private key corresponding to the valid digital certificate. After verifying the digital signature sent by the driver, the authentication server should launch a preconcerted E-commerce protocol to accomplish the transaction, resign the random number r- in terms of her own private key, and then send it back to the driver. Availing herself of the signed random number, the driver can thus prove to the RSU that she has paid for the service.After that, the driver is in a position to interact with the adjacent RSU and acquirekvδ as well as kwδ corresponding to her interested coordinates in the light of the aforementioned 1-out-n oblivious transfer protocol. Then she retrieves all encrypted messages and decrypts dδ=Dmδ=kvδ⊕kwδ(dδ′) to recover the data she expected.It is worth noting that the driver may retrieve all encrypted messages only once and store some of them for further queries. In addition, even if the driver’s identity is exposed during the authenticating process, it will not jeopardize the confidentiality of her queried position due to the intrinsic nature of oblivious transfer.The process is illustrated in Table5.Table 5
The proposed privacy-preserving location-based querying scheme.
Central Server RSUs HoldsV×W messages di, i = w + v ⋅ W ∈ { 0 ,  1 , … , V × W - 1 }. Initialization phase ( s k , p k ) ← K e y G e n ( κ ), G ← G e o g r a p h y, G is a V×W grid, For allv∈{0,1,…,V-1} and  w∈{0,1,…,W-1}, k v , k w ← R { 0,1 } κ, m i = k w ⊕ k v,  i=w+v⋅W, d i ′ = E m i ( d i ), Putsk,pk and all kv,kw,di′ in RSUs. Receives and storessk,pk as well as all kv,kw,di′ locally.  Local RSU Driver Holdssk,pk and all kv,kw,di′ as above. Holds(vδ,wδ),vδ∈{0,1,…,V-1}, w δ ∈ { 0 ,  1 , … , W - 1 } .  Authentication and transaction phase Requests for service. r - ← R { 0,1 } κ and sends it to the driver. S i g n s k d r i v e r ( r - ), Completes the authentication as well as payment process with the central server. ReceivesSignsk(r-) from the central server and sends it to the RSU. VerifiesSignsk(r-). Retrieving phase Retrieves alldi′ from local RSU. Executes the NTRU-basedOT protocol with the driver. Executes the NTRU-basedOT protocol with the RSU and gets kvδ and kwδ. δ = w δ + v δ ⋅ W, m δ = k v δ ⊕ k w δ, d δ = D m δ ( d δ ′ ).In fact, the aforementioned protocol can be regarded as being based on 2-out-n oblivious transfer since two symmetric keys kvδ, kwδ should be retrieved. However, all encrypted data need only to be transmitted once during retrieval phase, which means the extra computation and communication overheads are trivial. Moreover, the public key pair of driver is only used for authentication and payment but not necessarily for oblivious transfer.


## 3.1. NTRU Implementation of 1-Out-n Oblivious Transfer

Different from traditional public key cryptosystems, NTRU is structured on a truncated polynomial ring which is provided with both addition and multiplication. Since the time of performing convolution multiplication is much faster than that of modular exponentiation on large numbers, the preferable efficiency and security property of NTRU are more appropriate to construct the basic oblivious transfer protocol.In order to realize the NTRU-based 1-out-n oblivious transfer, the messages held by the sender are presented as m0,m1,…,mn-1, which must be kept unacquainted from the receiver except for mδ. Accordingly, we describe the primitive 1-out-n oblivious transfer protocol as below.During key generation phase, the sender constructs a key pair as in Section2, she releases her public key pk=h to all potential receivers or stores it in a communal database, while keeping the secret key sk=(f,fp) private.In oblivious transfer phase, the sender is supposed to choosen random polynomials γ0,γ1,…,γn-1 from Td,d, where ri·h can be represented as p·fq·γi, and encrypt all plaintexts to be (10)ci=ri·h+mimodq,i=0,1,…,n-1,which is then sent to the receiver.When all ciphertexts are received, the receiver first generates a random polynomials belonging to Td,d and figures out its inverse s-1(modp). If the inverse of polynomial s does not exist, she can simply resample another one and repeat the inversion process.After that, the receiver must single out theδth ciphertext and compute it as(11)cδ′=r′·h+s·cδmodq,utilizing another random polynomial r′ chosen from Td,d. The result will be sent back to the sender.Depending on the altered ciphertextcδ′, the sender can calculate(12)aδ=f·cδ′modq,bδ=aδmodpand then(13)cδ′′=fp·bδmodpto be her response for the driver.Since the driver is aware of polynomials, she can achieve the expected messages mδ by multiply cδ′′ with s-1modulo p.The above process is also characterized in Table4.Table 4
O T n 1 protocol based on NTRUEncrypt.
Server Driver Holdsn messages mi∈{0,1}N, Holdsδ,δ∈{0,1,…,n-1}. i = { 0 ,  1 ,  … , n - 1 } . Key generation phase ( q , p , f , f q , f p , g ) ← K e y G e n ( κ ), s k :  ( f , f p ), p k :  h, Sendspk to the driver.  Oblivious transfer phase For alli={0,1,…,n-1}, γ i ← R T d , d , c i = p ⋅ f q ⋅ γ i + m i ( m o d  q ) , Sends allci to the driver. r ′ ← R T d , d , s ← R T d , d, where s is reversible modulo p, c δ ′ = r ′ ⋅ h + s ⋅ c δ ( m o d  q ), Sendscδ′ back to the server. a δ = f ⋅ c δ ′ m o d  q, bδ=aδmodp, c δ ′ ′ = f p ⋅ b δ ( m o d  p ) , Sendscδ′′ to the driver. m δ = c δ ′ ′ ⋅ s - 1 ( m o d  p ).Correctness of the 1-out-n oblivious transfer protocol relies on the computation of polynomials in truncated polynomial ring, as follows.Lemma 3.
The driver can correctly obtain messagemδ if q>2p(2d2+5d).Proof.
Since the parameters ofg·r or γδ·s are seated within [-2d,2d] and the coefficients of f·s·mδ cannot exceed p2d2+d for polynomial aδ=p·g·r′+p·γδ·s+f·s·mδ(modq). No information will be lost when lifting the coefficients of aδ to [-q/2,q/2], if q>2p(2d2+5d) the same as Lemma 2. By computing mδ=cδ′′·s-1(modp), where cδ′′=s·mδ(modp), the driver can achieve the exact message mδ she expected.


## 3.2. Efficient and Secure Location-Based Querying

The system is modelled as a QSP and a series of vehicles. More specifically, the QSP can be considered working in a distributed manner, which is composed of a centralized authentication server together with numerous delivery RSUs. The reason behind such configuration is to separate data retrieval from transaction process, which not only preserves the driver’s position privacy but also abates the operating load of service centre. Resorting to the OBUs equipped on vehicles, drivers are able to determine their current position via localization devices such as GPS or WiFi.Ininitialization phase, the QSP first generates its key pair and divides the geography to be a public grid G composed of V rows and W columns. For each cell v×w of the grid, she assembles all related data as a message di, where i=w+v·W, 0≤v≤V-1, and 0≤w≤W-1, and encrypts it as di′=Emi=kv⊕kw(di) by symmetric cryptosystem E according to the keys kv, kw designated to each row and column. Then, the QSP stores its key pair together with all kv, kw as well as di′ in distributed RSUs.Inretrieving phase, the driver should complete both the payment and oblivious transfer process as follows.In order to actualize the requirement of pay-per-retrieval for location-based service, the driver should ask for a random numberr- from its adjacent RSU and sign it using her private key corresponding to the valid digital certificate. After verifying the digital signature sent by the driver, the authentication server should launch a preconcerted E-commerce protocol to accomplish the transaction, resign the random number r- in terms of her own private key, and then send it back to the driver. Availing herself of the signed random number, the driver can thus prove to the RSU that she has paid for the service.After that, the driver is in a position to interact with the adjacent RSU and acquirekvδ as well as kwδ corresponding to her interested coordinates in the light of the aforementioned 1-out-n oblivious transfer protocol. Then she retrieves all encrypted messages and decrypts dδ=Dmδ=kvδ⊕kwδ(dδ′) to recover the data she expected.It is worth noting that the driver may retrieve all encrypted messages only once and store some of them for further queries. In addition, even if the driver’s identity is exposed during the authenticating process, it will not jeopardize the confidentiality of her queried position due to the intrinsic nature of oblivious transfer.The process is illustrated in Table5.Table 5
The proposed privacy-preserving location-based querying scheme.
Central Server RSUs HoldsV×W messages di, i = w + v ⋅ W ∈ { 0 ,  1 , … , V × W - 1 }. Initialization phase ( s k , p k ) ← K e y G e n ( κ ), G ← G e o g r a p h y, G is a V×W grid, For allv∈{0,1,…,V-1} and  w∈{0,1,…,W-1}, k v , k w ← R { 0,1 } κ, m i = k w ⊕ k v,  i=w+v⋅W, d i ′ = E m i ( d i ), Putsk,pk and all kv,kw,di′ in RSUs. Receives and storessk,pk as well as all kv,kw,di′ locally.  Local RSU Driver Holdssk,pk and all kv,kw,di′ as above. Holds(vδ,wδ),vδ∈{0,1,…,V-1}, w δ ∈ { 0 ,  1 , … , W - 1 } .  Authentication and transaction phase Requests for service. r - ← R { 0,1 } κ and sends it to the driver. S i g n s k d r i v e r ( r - ), Completes the authentication as well as payment process with the central server. ReceivesSignsk(r-) from the central server and sends it to the RSU. VerifiesSignsk(r-). Retrieving phase Retrieves alldi′ from local RSU. Executes the NTRU-basedOT protocol with the driver. Executes the NTRU-basedOT protocol with the RSU and gets kvδ and kwδ. δ = w δ + v δ ⋅ W, m δ = k v δ ⊕ k w δ, d δ = D m δ ( d δ ′ ).In fact, the aforementioned protocol can be regarded as being based on 2-out-n oblivious transfer since two symmetric keys kvδ, kwδ should be retrieved. However, all encrypted data need only to be transmitted once during retrieval phase, which means the extra computation and communication overheads are trivial. Moreover, the public key pair of driver is only used for authentication and payment but not necessarily for oblivious transfer.


## 4. Security Analysis

We investigate the server’s data proprietorship and the driver’s position privacy in oblivious transfer at first. It should be noted that the messages obliviously transferred are symmetric keyskvδ, kwδ instead of mδ actually; however, we will alternatively apply these notations for smooth representation.As for the driver’s position privacy, we claim the following.Lemma 4.
The QSP gains no information on the driver’s choiceδ in the proposed OT protocol.Proof.
Using the private keysk, the QSP can compute cδ′′=s·mδ(modp). However, she is ignorant of the driver’s secret polynomial s and thereby cannot differentiate the choice δ from any other by comparing it with possessed messages, though the QSP may fortunately figure out r′+rδ·s(modq) if g is reversible, which means she can further achieve r′+rδ·s·s·mδ-1=r′·s-1·mδ-1+rδ·mδ-1. Nevertheless, since r′ and s are uniformly distributed, mδ is totally indistinguishable.The server’s data proprietorship can be found as follows.Lemma 5.
The driver gains no information onmi if i≠δ.Proof.
The driver is aware ofci=ri·hS+mi(modq) for all messages. Since she does not possess the server’s private key, the mistiness of mi from ci is straight-forward.
With regard to the processes of authentication and transaction, the driver would interact with a central server directly to achieve a voucher signed by the QSP’s private key. That means the RSU is incapable of linking the driver’s current position up to her identity. Moreover, since the voucher is generated according to a provisional random number chosen by the RSU, the chance that a driver replay her voucher to cheat the QSP out of her service is negligible. Thanks to the intrinsic characteristic ofOT, even if the identity of the driver is exposed in case that the RSU colludes with the central server, the confidentially of required coordinate would never be compromised. Supposing that the driver’s identity privacy is obligatory in certain circumstances, anonymous authentication schemes such as that of [49] are further suggested.Now, we argue UC security of the complete scheme. In order to testify that a real-world implementation of our scheme is indistinguishable from its simulation, the ideal functionality is firstly defined as follows.Definition 6.
The ideal functionalityFOT- receives a coordinate (vδ,wδ)∈0,1,…,V-1×0,1,…,W-1 together with an identity from the driver and a vector of l-bits messages, that is, (d0,d1,…,dV×W-1), from the server S, but only outputs a l-bits string dδ to the driver D.In line with Definition6, two simulators S1, S2 can be established to emulate the corrupted QSP and driver, respectively. Since (14)Pr⁡FOT-=δ=1V×W,it is obvious that(15)Pr⁡FOT=δ-Pr⁡FOT-=δ<εκaccording to Lemma 4. So the indistinguishability(16)S111κ,IDdriver,d0,d1,…,dV×W-111≅VIEWQSPIDdriver,d0,d1,…,dV×W-1,vδ,wδ11is straight-forward.Similarly, once the symmetric cryptosystem(E,D) is noncommitting, the distributions of di≠δ′ in FOT and FOT- are both uniform and indiscernible, which means(17)Pr⁡FOT=di≠δ′=Pr⁡FOT-=di≠δ′=1M-1,where |M| stands for the size of plaintext space, and(18)S2κ,vδ,wδ,d0′,d1′,…,dV×W-1′≅VIEWdrivervδ,wδ,d0′,d1′,…,dV×W-1′,due to the ignorance of kvi≠δ and kwi≠δ on driver’s side in terms of Lemma 5.Thus we claim the folowing.Theorem 7.
Our protocol securely implements the functionalityFOT- if the symmetric encryption scheme E,D is noncommitting.


## 5. Performance Evaluation

Since only simple polynomial multiplications are needed for NTRU cryptosystem, it features high speed, low memory requirements, and reasonably short and easily created keys. The moduli used in NTRUEncrypt specially are logarithmically smaller than that of traditional asymmetric cryptosystems based on integer factorization or discrete logarithm, which implies preferable efficiency and practicability. According to the report from [50], the speed of NTRU is up to 1300 times faster than 2048-bit RSA and 117 times faster than ECC NIST-224 when comparing the number of encryptions per second. Our experimental results also signified that the ratio of encryption times between 2048-bit ElGamal and NTRU in moderate security is 355 : 1.In order to impartially compare with Jannati’s protocol, only retrieval process will be considered in the following performance analysis. Though authentication and transaction are introduced in our scheme for pay-per-service purpose, the extra overheads are ineluctable but negligible compared to that of oblivious transfer. Table6 illustrates the comparison of computation as well as communication overheads between our and Jannati’s scheme. However, since the basic operations used in NTRU are absolutely different from that of ElGamal, it should be noted that modular multiplications and modular polynomial multiplications are correspondingly applied to one of them.Table 6
Comparison of computation and communication overheads.
QSP Driver Jannati and Bahrak Ours Jannati and Bahrak Ours Modular exponentiation 3 ( V + W + 1 ) 0 9 0 Modular (polynomial) multiplication 2 ( V + W ) + 1 V + W + 4 7 6 Generating random numbers (polynomials) V + W + 2 V + W 2 4 Secret keys 2 1 2 0 Public keys 2 1 0 0 Communication burden (polynomials) V + W + 1 V + W + 2 2 2Compared to Jannati’s protocol in Table6, it is obvious that no exponentiations would be necessary in our scheme and the overhead of modular multiplication is also halved even without regard for the scale of moduli. It is worth mentioning that, though the number of transmitted messages are almost the same between Jannati’s scheme and ours, we have evidently depressed the communication burden because a ElGamal encryption works on a large cyclic group and produces a double expansion in size from plaintext to ciphertext. Meanwhile, our scheme is more applicable since the receiver is free of generating or distributing any public key during oblivious transfer process.We also simulated our and Jannati’s protocol by C program. The experiment is carried out on an Intel Core i3-2330M processor (Sandy Bridge) where each party runs on one core. The computation burden and communication overhead for each retrieval are averaged by 500 tests.According to Table7, it is obvious that our scheme dramatically outperforms Jannati’s protocol with respect to both computation and communication overheads. Specifically, taking the resource limits of OBU into account, the operational efficiency is 479 times that of Jannati’s protocol, which means our scheme is more applicative in embedded and real-time environments. We simply neglected the delivery load of queried data in our experiment; however, retrieving all di′ indistinguishably from the server is inevitable due to the query privacy for any oblivious transfer. Fortunately, the driver can only retrieve the ciphered messages ones and keep all expected portions in the local storage, or she may ignore any other messages except for dδ′ when receiving the QSP’s broadcast.Table 7
Timings in milliseconds and delivery loads in kilobytes for per retrieval (moderate security).
QSP Driver Jannati and Bahrak Ours Jannati and Bahrak Ours Running time 993.23 3.26 47.85 0.10 Data size (V+W=64) 34.12 8.10 1.08 0.23


## 6. Conclusion

This paper proposed a privacy-preserving location-based querying scheme in virtue of NTRUEncrypt. Thanks to the intrinsic nature of NTRU cryptosystem such as postquantum security, high speed, low storage requirements, and short keys, our scheme is resistant to active adaptive corruptions and more practicable within vehicular ad hoc network. Specifically, the computational overheads are only 0.33 and 0.21 percent while the communication burdens are 24 and 21 percent compared to those of a recent scheme presented by Jannati and Bahrak Besides the theoretical and experimental performance analyses, we also depicted the detailed process of authentication and transaction for pay-per-service purpose. In the light of universal composability frame, it is believable that our scheme is secure with the functionality of oblivious transfer realized. For further work, we expect to reduce the interactive round of retrieving phase from 3 to 2 and decrease the RSU’s overheads to a higher degree.



---

*Source: 7823979-2018-05-03.xml*