Abstract
Location-based services are quite popular. Their variety and their numerous users show it clearly. However, these applications rely on the persons’ honesty to use their real location. If they are motivated to lie about their position, they can do so. A location-proof system allows a prover to obtain proofs from nearby witnesses, for being at a given location at a given time. Such a proof can be used to convince a verifier later on. Many solutions have been designed in the last decade, but none protects perfectly the privacy of their participants. Indeed, provers and witnesses may want to keep their identity and location private. In this paper, a solution is presented in which a malicious adversary, acting as a prover, cannot cheat on his position. It relies on multi-party computations and group-signature schemes to protect the private information of both the prover and the witnesses against any semi-honest participant. Additionally, this paper gives a new secure multi-party maximum computation protocol requiring \(\mathcal {O}(n \log (n))\) computations and communications, which greatly improves the previously known solutions having \(\mathcal {O}(n^2)\) complexities. Although it is designed for our location-proof system, it can be applied to any scenario in which a small information leakage is acceptable.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
References
Bultel, X., Gambs, S., Gérault, D., Lafourcade, P., Onete, C., Robert, J.M.: A prover-anonymous and terrorist-fraud resistant distance-bounding protocol. In: Proceedings of WISec, pp. 121–133. ACM (2016)
Cramer, R., Fehr, S., Ishai, Y., Kushilevitz, E.: Efficient multi-party computation over rings. In: Biham, E. (ed.) EUROCRYPT 2003. LNCS, vol. 2656, pp. 596–613. Springer, Heidelberg (2003). https://doi.org/10.1007/3-540-39200-9_37
Davis, B., Chen, H., Franklin, M.: Privacy-preserving alibi systems. In: Proceedings of ASIACCS, pp. 1–10. ACM (2012)
Franklin, M., Zhang, H.: Unique group signatures. In: Foresti, S., Yung, M., Martinelli, F. (eds.) ESORICS 2012. LNCS, vol. 7459, pp. 643–660. Springer, Heidelberg (2012). https://doi.org/10.1007/978-3-642-33167-1_37
Gambs, S., Killijian, M.O., Roy, M., Traoré, M.: PROPS: a privacy-preserving location proof system. In: Proceedings of SRDS, pp. 1–10. IEEE (2014)
Graham, M., Gray, D.: Protecting privacy and securing the gathering of location proofs – the secure location verification proof gathering protocol. In: Schmidt, A.U., Lian, S. (eds.) MobiSec 2009. LNICST, vol. 17, pp. 160–171. Springer, Heidelberg (2009). https://doi.org/10.1007/978-3-642-04434-2_14
Hasan, O., Brunie, L., Bertino, E.: Preserving privacy of feedback providers in decentralized reputation systems. Comput. Secur. 31, 816–826 (2012)
Hazay, C., Lindell, Y.: Efficient Secure Two-Party Protocols: Techniques and Constructions. Springer, Heidelberg (2010). https://doi.org/10.1007/978-3-642-14303-8
Lin, H.-Y., Tzeng, W.-G.: An efficient solution to the millionaires’ problem based on homomorphic encryption. In: Ioannidis, J., Keromytis, A., Yung, M. (eds.) ACNS 2005. LNCS, vol. 3531, pp. 456–466. Springer, Heidelberg (2005). https://doi.org/10.1007/11496137_31
Luo, W., Hengartner, U.: Proving your location without giving up your privacy. In: Proceedings of the HotMobile, pp. 7–12. ACM (2010)
Luo, W., Hengartner, U.: Veriplace: a privacy-aware location proof architecture. In: Proceedings of SIGSPATIAL, pp. 23–32. ACM (2010)
Paillier, P.: Public-key cryptosystems based on composite degree residuosity classes. In: Stern, J. (ed.) EUROCRYPT 1999. LNCS, vol. 1592, pp. 223–238. Springer, Heidelberg (1999). https://doi.org/10.1007/3-540-48910-X_16
Pham, A., Huguenin, K., Bilogrevic, I., Dacosta, I., Hubaux, J.P.: SecureRun: cheat-proof and private summaries for location-based activities. In: Proceedings of TMC, pp. 2109–2123. IEEE (2015)
Saroiu, S., Wolman, A.: Enabling new mobile applications with location proofs. In: Proceedings of HotMobile, pp. 1–6. ACM (2009)
Sastry, N., Shankar, U., Wagner, D.: Secure verification of location claims. In: Proceedings of WISEC, pp. 1–10. ACM (2003)
Singelee, D., Preneel, B.: Location verification using secure distance bounding protocols. In: Proceedings of MASS, pp. 7–14. IEEE (2005)
Talasila, M., Curtmola, R., Borcea, C.: LINK: location verification through immediate neighbors knowledge. In: Sénac, P., Ott, M., Seneviratne, A. (eds.) MobiQuitous 2010. LNICST, vol. 73, pp. 210–223. Springer, Heidelberg (2012). https://doi.org/10.1007/978-3-642-29154-8_18
Zhu, Z., Cao, G.: APPLAUS: a privacy-preserving location proof updating system for location-based services. In: Proceedings of INFOCOM, pp. 1889–1897. IEEE (2011)
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Appendices
A Complexity of the Overall System
We have detailed the computational and communication complexity in each sub-protocols, but we are now interested in the complexity of the overall location-proof system (Protocol 1), depending on the number of witnesses. For simplicity, let us assume there are \(m=4n\) witnesses, i.e. n in each direction. Let |N| denote the size of the keys (the size of a ciphertext is simply 2|N| with the Paillier’s cryptosystem) and |S| denote the size of group signatures. We consider that the encryption, decryption functions and homomorphic operations are in \(\mathcal {O}(1)\).
Table 2 presents the number of cryptographic operations processed by the prover and by each witness, the number of communications and the bits exchanged during the different protocols. We only deal with the worst case scenario: a marked witness for the computational complexity in \(\textsf {Protocol}~3\), and only a witness A in Protocol 4. This can obviously be optimized by giving role B to marked witnesses as often as possible. The complexity of Protocol 3 is an approximation of the total number of comparisons. An exact formula is given in Sect. 4.3. In Protocol 4, it has been shown that \(\mathcal {P}\) runs \(l+1\) operations in \(n-1\) comparisons, and only 1 otherwise. Thus, the number of operations done by the prover in Protocol 3 and 4 is approximately \((n-1)l + \frac{n}{2}\lceil \log {n} \rceil \).
To summarize, the global complexity, both in terms of computations and communication, is in \(\mathcal {O}(n\log {n})\) for the prover and \(\mathcal {O}(\log {n})\) for a witness. In comparison, most previous location-based systems have a complexity for the prover in \(\mathcal {O}(n)\), and \(\mathcal {O}(1)\) for a witness. This is due to the fact that witnesses do not need to interact with each other. However, location-privacy requires such interactions, and thus we do not reach the same objectives.
B Security Proofs of the Two-Party Comparison Protocol
In this annex, we give more details about some security goals of Protocol 4: (1) A cannot find b, (3) \(\mathcal {P}\) cannot find neither a nor b and (4) the result of the comparison is known only to \(\mathcal {P}\).
Proof
(Objective (1)). At the beginning of Step 3, A learns \(\pi _B(\delta _1,\cdots , \delta _l)\) with
Remember that \(h(T_0^b[i])\) can be seen as an encoding of b. Let us prove that the vector \(\delta \) does not leak any information about b.
W.l.o.g. assume that \(\pi _B(\cdot )\) is the permutation identity. Let us take any value \(b' \ne b\) and show that the same vector \(\delta \) can be obtained from \(b'\) and thus does not leak any information.
If \(a>b'\), let \(i^*\) be the index such that \(T_1^a[i^*] = T_0^{b'}[i^*]\) and take \(r_B = \delta _{i^*}\). On the other hand, if \(a \le b'\), we can choose arbitrarily \(r_B\). Now if we take:
then we obtain the same vector \(\delta \).
This can be generalized to permutation \(\pi _B(\cdot )\). Hence, \(\delta \) can be obtained from any value of \(b'\) with the same probability, and does not therefore leak any information about b.
It remains to prove that A does not learn the result of the comparison (part of Objective (4)) which would leak partial information about b. The result of the comparison (either in the vector \(\mu \), the value \(s_A\) or \(s_B\)) is always encrypted under the public key of \(\mathcal {P}\). We assume the cryptosystem is semantically secure, which ends the proof of Objective (1). \(\square \)
Proof
(Objective (3)). At the beginning of Step 4, \(\mathcal {P}\) learns \(\pi _A(\mu _1,\cdots , \mu _l)\) where
and \(\delta ^*_i = \delta _{\pi _B(i)}\). To simplify notations, assume that \(\pi _A(\cdot )\) and \(\pi _B(\cdot )\) are the identity permutation. If \(s_A\) or \(s_B\) is different from 0, this case is simple (Objective (7)): the vector \(\mu \) follows an independent uniform distribution of \(\mathbb {Z}_{N_\mathcal {P}}^l\). Thus, we only study the case:
Knowing that \(a > b\), we will now show that for any couple \((a',b')\) such that \(a' > b'\), we can obtain the same vector \(\mu \) with the same probability. In this case, let \(i^*\) be the index such that \(T_1^{a'}[i^*] = T_0^{b'}[i^*]\). In this case, \(k_{i^*}\) can be chosen arbitrarily. For all other value \(i \ne i^*\), \(r_{A,i}\) can be chosen arbitrarily, and \(k_i\) can be defined as:
Finally, if \(a \le b\), this is simpler. In this case, the index \(i^*\) is not defined, and the values of all \(r_{A,i}\) and \(k_i\) are defined as above.
Thus, the same vector \(\mu \) can be obtained. This can be done for any values of \(a'\) and \(b'\), as long as the result remains unchanged, and for any permutation \(\pi _A(\cdot )\) and \(\pi _B(\cdot )\). Therefore, the vector \(\mu \) does not leak any information about a or b except whether \(a > b\) or not, which ends the proof.
\(\square \)
Rights and permissions
Copyright information
© 2018 Springer Nature Switzerland AG
About this paper
Cite this paper
Dupin, A., Robert, JM., Bidan, C. (2018). Location-Proof System Based on Secure Multi-party Computations. In: Baek, J., Susilo, W., Kim, J. (eds) Provable Security. ProvSec 2018. Lecture Notes in Computer Science(), vol 11192. Springer, Cham. https://doi.org/10.1007/978-3-030-01446-9_2
Download citation
DOI: https://doi.org/10.1007/978-3-030-01446-9_2
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-030-01445-2
Online ISBN: 978-3-030-01446-9
eBook Packages: Computer ScienceComputer Science (R0)