隨著越來越多的感測器和物聯網設備被部署在智慧城市中，產生的資訊量也顯著增加。在來自外部的惡意攻擊者和濫用資料訪問權限的內部人員同時存在的情況下，防止隱私數據洩露和身份洩露對智慧城市而言是當務之急。系統的安全假設，不應該只仰賴於權限和存取控制被正確實作。反過來說，系統可以設計成在已經被入侵的情況下，使用者的身份數據和使用痕跡還是不會被洩露。基於我們之前關於藍芽低能量信標(BLE)的路邊停車系統研究，我們在認證系統中應用了一種被稱為零知識證明的密碼學元件。我們結合了密碼學承諾和默克爾樹來達成零知識集合成員證明。這樣一來，使用者在不同的登入之間對伺服器能夠保持匿名，同時伺服器仍然能夠驗證該使用者的合法性。這麼做，路邊停車系統就不會出現隱私數據洩露的情況，因為攻擊者無法在系統內進行大規模查詢，追蹤特定使用者的使用足跡。

The amount of information generated grows as more and more sensor and IoT devices are deployed in smart cities. It is of utmost importance for us to consider the privacy data leakage and compromised identity from both outside adversaries and inside abuse of data access privilege. The security assumption of the system should not solely rely on the fact that permission and access control were being implemented correctly. Quite the contrary, a system can be designed in a way that user’s identity data and usage traces are not leaked even if the system had been compromised. Based upon our previous on-street parking system utilizing Bluetooth Low Energy (BLE) beacons, we applied a cryptographic primitive called zero-knowledge proof to our authentication system. A commitment scheme and Merkle tree is combined in the setup to achieve zero-knowledge set membership proof. Doing so, the user is anonymous to the server between authentication sessions, while the server’s still able to verify the legitimacy of such user. The on-street parking system is therefore immune to privacy data leakage, as for now one cannot mass-query and profile certain user‘s traces within the system.

I.	Introduction	1
II.	Literature Review	7
A.	Off-Label Uses of Zero-Knowledge Proof	7
B.	Data Anonymization	8
C.	Authentication	9
D.	Similar Works	11
E.	Review The Whole Picture	12
III.	Preliminaries	14
A.	NP Language	14
B.	Boolean satisfiability problem (SAT), Circuit satisfiability problem (CircuitSAT), Quadratic Arithmetic Programs, and Arithmetic circuits	15
C.	Proving System	18
IV.	Proposed System Model	20
A.	Overview	20
B.	Registration Phase	23
C.	Authentication Phase	24
V.	Performance Analysis	28
A.	Proof System Performances	28
B.	System Performance	30
VI.	Discussions	34
VII.	Conclusion	39
References	41

List of Tables
Table I: Notations	22
Table II: Proof System Performance Comparison	29
Table III: Comparison of Performance on Physical Machine	32

List of Figures
Fig. 1.  The system architecture in our previous work.	4
Fig. 2.  System Architecture.	20
Fig. 3.  Circuit constraints versus the number of hashes [59].	30

[1]	D. Eckhoff and I. Wagner, ‘Privacy in the smart city—applications, technologies, challenges, and solutions’, IEEE Communications Surveys & Tutorials, vol. 20, no. 1, pp. 489–516, 2017.
[2]	K. Zhang, J. Ni, K. Yang, X. Liang, J. Ren, and X. S. Shen, ‘Security and privacy in smart city applications: Challenges and solutions’, IEEE Communications Magazine, vol. 55, no. 1, pp. 122–129, 2017.
[3]	J. Joy and M. Gerla, ‘Internet of Vehicles and Autonomous Connected Car - Privacy and Security Issues’, in 2017 26th International Conference on Computer Communication and Networks (ICCCN), Jul. 2017, pp. 1–9, doi: 10.1109/ICCCN.2017.8038391.
[4]	Y. Qu, M. R. Nosouhi, L. Cui, and S. Yu, ‘Chapter 6 - Privacy Preservation in Smart Cities’, in Smart Cities Cybersecurity and Privacy, D. B. Rawat and K. Z. Ghafoor, Eds. Elsevier, 2019, pp. 75–88.
[5]	DEFCONConference, ‘DEF CON 23 - Marc Rogers and Kevin Mahaffey - How to Hack a Tesla Model S’, presented at the Defcon 23, Dec. 2015, Accessed: Dec. 14, 2020. [Online]. Available: https://www.youtube.com/watch?v=KX_0c9R4Fng.
[6]	C. Cerrudo, ‘Hacking Traffic Control Systems (U.S, UK, Australia, France, etc.)’, p. 30.
[7]	Y. Sun et al., ‘Security and Privacy in the Internet of Vehicles’, in 2015 International Conference on Identification, Information, and Knowledge in the Internet of Things (IIKI), 2015, pp. 116–121.
[8]	K.-T. Cho and K. G. Shin, ‘Fingerprinting electronic control units for vehicle intrusion detection’, in 25th ${$USENIX$}$ Security Symposium (${$USENIX$}$ Security 16), 2016, pp. 911–927.
[9]	J. Hua, H. Sun, Z. Shen, Z. Qian, and S. Zhong, ‘Accurate and efficient wireless device fingerprinting using channel state information’, in IEEE INFOCOM 2018-IEEE Conference on Computer Communications, 2018, pp. 1700–1708.
[10]	G. Wang, B. Wang, T. Wang, A. Nika, H. Zheng, and B. Y. Zhao, ‘Defending against sybil devices in crowdsourced mapping services’, in Proceedings of the 14th Annual International Conference on Mobile Systems, Applications, and Services, 2016, pp. 179–191.
[11]	‘Code42 2019 Global Data Exposure Report Finds 69% of Security Leaders Say Data Loss Prevention Cannot Stop Insider Threat’, Bloomberg.com, Oct. 03, 2019.
[12]	Chief Optimist, ‘Government Data Breaches: An Inside Job? [Infographic]’, 20:49:14 UTC, Accessed: Jan. 23, 2021. [Online]. Available: https://www.slideshare.net/Xerox-MPS/government-data-breaches-an-inside-job-infographic.
[13]	‘Top 10 Biggest Government Data Breaches of All Time in the U.S.’, Digital Guardian, Apr. 10, 2017. https://digitalguardian.com/blog/top-10-biggest-us-government-data-breaches-all-time (accessed Jan. 23, 2021).
[14]	C.-F. Chien, H.-T. Chen, and C.-Y. Lin, ‘A Low-Cost On-Street Parking Management System Based on Bluetooth Beacons’, Sensors, vol. 20, p. 4559, Aug. 2020, doi: 10.3390/s20164559.
[15]	M. Ryan, ‘Bluetooth: With low energy comes low security’, 2013.
[16]	J. Padgette, K. Scarfone, and L. Chen, ‘Guide to bluetooth security’, NIST special publication, vol. 800, no. 121, p. 25, 2012.
[17]	A. M. Lonzetta, P. Cope, J. Campbell, B. J. Mohd, and T. Hayajneh, ‘Security vulnerabilities in Bluetooth technology as used in IoT’, Journal of Sensor and Actuator Networks, vol. 7, no. 3, p. 28, 2018.
[18]	A. Gabizon, Z. J. Williamson, and O. Ciobotaru, ‘PLONK: Permutations over Lagrange-bases for Oecumenical Noninteractive arguments of Knowledge.’, IACR Cryptol. ePrint Arch., vol. 2019, p. 953, 2019.
[19]	T. P. Pedersen, ‘Non-interactive and information-theoretic secure verifiable secret sharing’, in Annual international cryptology conference, 1991, pp. 129–140.
[20]	R. C. Merkle, ‘A digital signature based on a conventional encryption function’, in Conference on the theory and application of cryptographic techniques, 1987, pp. 369–378.
[21]	Y. Liu, Y. Wang, and G. Chang, ‘Efficient Privacy-Preserving Dual Authentication and Key Agreement Scheme for Secure V2V Communications in an IoV Paradigm’, IEEE Transactions on Intelligent Transportation Systems, vol. 18, no. 10, pp. 2740–2749, Oct. 2017, doi: 10.1109/TITS.2017.2657649.
[22]	H. J. Jo, J. H. Kim, H. Choi, W. Choi, D. H. Lee, and I. Lee, ‘MAuth-CAN: Masquerade-Attack-Proof Authentication for In-Vehicle Networks’, IEEE Transactions on Vehicular Technology, vol. 69, no. 2, pp. 2204–2218, Feb. 2020, doi: 10.1109/TVT.2019.2961765.
[23]	P. Gope and B. Sikdar, ‘An efficient privacy-preserving authenticated key agreement scheme for edge-assisted internet of drones’, IEEE Transactions on Vehicular Technology, 2020, [Online]. Available: https://sci-hub.se/10.1109/TVT.2020.3018778.
[24]	Z. J. Haddad, S. Taha, and I. A. Saroit, ‘Anonymous authentication and location privacy preserving schemes for LTE-A networks’, Egyptian Informatics Journal, vol. 18, no. 3, pp. 193–203, Nov. 2017, doi: 10.1016/j.eij.2017.01.002.
[25]	B. Soewito and Y. Marcellinus, ‘IoT security system with modified Zero Knowledge Proof algorithm for authentication’, Egyptian Informatics Journal, Oct. 2020, doi: 10.1016/j.eij.2020.10.001.
[26]	M. Han, Z. Yin, P. Cheng, X. Zhang, and S. Ma, ‘Zero-knowledge identity authentication for internet of vehicles: Improvement and application’, PLOS ONE, vol. 15, no. 9, p. e0239043, Sep. 2020, doi: 10.1371/journal.pone.0239043.
[27]	D. Gabay, K. Akkaya, and M. Cebe, ‘Privacy-Preserving Authentication Scheme for Connected Electric Vehicles Using Blockchain and Zero Knowledge Proofs’, IEEE Transactions on Vehicular Technology, vol. 69, no. 6, pp. 5760–5772, Jun. 2020, doi: 10.1109/TVT.2020.2977361.
[28]	M. Walshe, G. Epiphaniou, H. Al-Khateeb, M. Hammoudeh, V. Katos, and A. Dehghantanha, ‘Non-interactive zero knowledge proofs for the authentication of IoT devices in reduced connectivity environments’, Ad Hoc Networks, vol. 95, p. 101988, Dec. 2019, doi: 10.1016/j.adhoc.2019.101988.
[29]	L. Zhu, M. Li, Z. Zhang, and Z. Qin, ‘ASAP: An anonymous smart-parking and payment scheme in vehicular networks’, IEEE Transactions on Dependable and Secure Computing, 2018.
[30]	C. Huang, R. Lu, X. Lin, and X. Shen, ‘Secure Automated Valet Parking: A Privacy-Preserving Reservation Scheme for Autonomous Vehicles’, IEEE Transactions on Vehicular Technology, vol. 67, no. 11, pp. 11169–11180, Nov. 2018, doi: 10.1109/TVT.2018.2870167.
[31]	K. Kursawe, G. Danezis, and M. Kohlweiss, ‘Privacy-friendly aggregation for the smart-grid’, in International Symposium on Privacy Enhancing Technologies Symposium, 2011, pp. 175–191.
[32]	L. Guo et al., ‘A secure mechanism for big data collection in large scale internet of vehicle’, IEEE Internet of Things Journal, vol. 4, no. 2, pp. 601–610, 2017.
[33]	J. Sun, H. Xiong, S. Zhang, X. Liu, J. Yuan, and R. H. Deng, ‘A Secure Flexible and Tampering-Resistant Data Sharing System for Vehicular Social Networks’, IEEE Transactions on Vehicular Technology, vol. 69, no. 11, pp. 12938–12950, Nov. 2020, doi: 10.1109/TVT.2020.3015916.
[34]	W. Ou, M. Deng, and E. Luo, ‘A Decentralized and Anonymous Data Transaction Scheme Based on Blockchain and Zero-Knowledge Proof in Vehicle Networking (Workshop Paper)’, in Collaborative Computing: Networking, Applications and Worksharing, Cham, 2019, pp. 712–726, doi: 10.1007/978-3-030-30146-0_48.
[35]	‘An Incomplete Guide to Rollups’. https://vitalik.ca/general/2021/01/05/rollup.html (accessed Feb. 03, 2021).
[36]	‘Plasma - EthHub’. https://docs.ethhub.io/ethereum-roadmap/layer-2-scaling/plasma/ (accessed Feb. 03, 2021).
[37]	‘State Channels - EthHub’. https://docs.ethhub.io/ethereum-roadmap/layer-2-scaling/state-channels/ (accessed Feb. 03, 2021).
[38]	D. Hopwood, S. Bowe, T. Hornby, and N. Wilcox, ‘Zcash protocol specification’, GitHub: San Francisco, CA, USA, 2016.
[39]	M. El-hajj, A. Fadlallah, M. Chamoun, and A. Serhrouchni, ‘A Survey of Internet of Things (IoT) Authentication Schemes’, Sensors, vol. 19, no. 5, Art. no. 5, Jan. 2019, doi: 10.3390/s19051141.
[40]	S. Goldwasser, S. Micali, and C. Rackoff, ‘The knowledge complexity of interactive proof systems’, SIAM Journal on computing, vol. 18, no. 1, pp. 186–208, 1989.
[41]	S. Arora and B. Barak, Computational complexity: a modern approach. Cambridge University Press, 2009.
[42]	S. A. Cook, ‘The complexity of theorem-proving procedures’, in Proceedings of the third annual ACM symposium on Theory of computing, 1971, pp. 151–158.
[43]	L. A. Levin, ‘Universal sequential search problems’, Problemy peredachi informatsii, vol. 9, no. 3, pp. 115–116, 1973.
[44]	R. Gennaro, C. Gentry, B. Parno, and M. Raykova, ‘Quadratic span programs and succinct NIZKs without PCPs’, in Annual International Conference on the Theory and Applications of Cryptographic Techniques, 2013, pp. 626–645.
[45]	A. Nitulescu, ‘zk-SNARKs: A Gentle Introduction’.
[46]	R. Raz, ‘Elusive functions and lower bounds for arithmetic circuits’, in Proceedings of the fortieth annual ACM symposium on Theory of computing, 2008, pp. 711–720.
[47]	A. Shamir, ‘Ip= pspace’, Journal of the ACM (JACM), vol. 39, no. 4, pp. 869–877, 1992.
[48]	J. Groth, ‘[Groth16]On the size of pairing-based non-interactive arguments’, in Annual international conference on the theory and applications of cryptographic techniques, 2016, pp. 305–326.
[49]	S. Arora, C. Lund, R. Motwani, M. Sudan, and M. Szegedy, ‘Proof verification and the hardness of approximation problems’, Journal of the ACM (JACM), vol. 45, no. 3, pp. 501–555, 1998.
[50]	K. Gurkan, K. W. Jie, and B. Whitehat, ‘Community Proposal: Semaphore: Zero-Knowledge Signaling on Ethereum’, 2020.
[51]	M. Blum, A. De Santis, S. Micali, and G. Persiano, ‘Noninteractive zero-knowledge’, SIAM Journal on Computing, vol. 20, no. 6, pp. 1084–1118, 1991.
[52]	J. Groth, M. Kohlweiss, M. Maller, S. Meiklejohn, and I. Miers, ‘Updatable and universal common reference strings with applications to zk-SNARKs’, in Annual International Cryptology Conference, 2018, pp. 698–728.
[53]	M. Maller, S. Bowe, M. Kohlweiss, and S. Meiklejohn, ‘Sonic: Zero-knowledge SNARKs from linear-size universal and updatable structured reference strings’, in Proceedings of the 2019 ACM SIGSAC Conference on Computer and Communications Security, 2019, pp. 2111–2128.
[54]	‘dusk-network/plonk’, GitHub. https://github.com/dusk-network/plonk (accessed Feb. 21, 2021).
[55]	‘Extended protocol design’, Privacy Pass. https://privacypass.github.io/protocol/ (accessed Dec. 27, 2020).
[56]	D. Jovanović and P. Janičić, ‘Logical analysis of hash functions’, in International Workshop on Frontiers of Combining Systems, 2005, pp. 200–215.
[57]	L. Grassi, D. Khovratovich, C. Rechberger, A. Roy, and M. Schofnegger, ‘Poseidon: A new hash function for zero-knowledge proof systems’, 2020.
[58]	R. Dahlberg, T. Pulls, and R. Peeters, ‘Efficient sparse Merkle trees: caching strategies and secure (non-) membership proofs [C]’, 2016.
[59]	T. Walton-Pocock, ‘PLONK Benchmarks II — ~5x faster than Groth16 on Pedersen Hashes’, Medium, May 20, 2020. https://medium.com/aztec-protocol/plonk-benchmarks-ii-5x-faster-than-groth16-on-pedersen-hashes-ea5285353db0 (accessed Mar. 03, 2021).
[60]	Fluidex/plonkit. Fluidex, 2021.
[61]	‘Gas and circuit constraint benchmarks of binary and quinary incremental Merkle trees using the Poseidon hash function’, Ethereum Research, May 20, 2020. https://ethresear.ch/t/gas-and-circuit-constraint-benchmarks-of-binary-and-quinary-incremental-merkle-trees-using-the-poseidon-hash-function/7446 (accessed Mar. 03, 2021).
[62]	M. Z. Lee, A. M. Dunn, J. Katz, B. Waters, and E. Witchel, ‘Anon-Pass: Practical Anonymous Subscriptions’, p. 17.
[63]	M. Chase, M. Kohlweiss, A. Lysyanskaya, and S. Meiklejohn, ‘Malleable proof systems and applications’, in Annual International Conference on the Theory and Applications of Cryptographic Techniques, 2012, pp. 281–300.
[64]	A. Rial and G. Danezis, ‘Privacy-preserving smart metering’, in Proceedings of the 10th annual ACM workshop on Privacy in the electronic society, 2011, pp. 49–60.
[65]	M. Jawurek, M. Johns, and F. Kerschbaum, ‘Plug-in privacy for smart metering billing’, 2011.
[66]	J. Balasch, A. Rial, C. Troncoso, B. Preneel, I. Verbauwhede, and C. Geuens, ‘PrETP: Privacy-Preserving Electronic Toll Pricing.’, in USENIX Security Symposium, 2010, vol. 10, pp. 63–78.
[67] ‘ZKP in Civic Tech - Re-imagining Identity Infrastructures’.
https://geek.sg//blog/zkp-in-civic-tech%E2%80%8A-%E2%80%8Are- imagining-identity-infrastructures (accessed Feb. 25, 2021).