在車載網路中，可以藉由傳遞訊息讓使用者享受多元的服務。然而在高密度的環境裡，大量的訊息接收很可能會超過設備所能處理的驗證能力範圍，導致許多訊息無法進行驗證或有大量的安全訊息直接被丟棄，造成使用者無法應對意外狀況的發生，故本碩士論文致力於提高訊息驗證的效率及安全訊息的驗證完成量。在我們的設計中，會先選出基本安全訊息，並在必要時對其進行物理特徵關聯性分類，以對較為重要的訊息優先做驗證，並採用批次驗證以提高訊息驗證的效率。為改善批次驗證失敗時的缺點，我們設計了動態批次驗證機制，會根據過去的批次驗證驗證結果來對每次的批次量做調整，若過去連續批次驗證失敗，會減半批次量以提升驗證效率，若過去連續批次驗證成功，則會加倍批次量以增加單次批次驗證的完成量。當驗證失敗時，會利用分而治之的方式來對訊息進行重新批次驗證，以找出一批中的不合法訊息。最後，透過分析結果顯示，我們提出的機制相較於其他機制能有效降低驗證延遲及增加基本安全訊息的驗證完成量。

In vehicular ad hoc networks (VANETs), users are allowed to enjoy various services through messages dissemination. However, the server may encounter computation difficulty when receiving much more messages than its capacity in a high-density environment. Thus, many safety messages will not be verified in time and then get dropped, making users unable to avoid accidents. Therefore, we aim to improve the efficiency of message verification and the amount of verified safety messages. In our proposed scheme, messages are classified so that more important basic safety messages can be verified first. If necessary, those basic safety messages will be prioritized based on physical attributes. To improve the batch verification, we design a dynamic batch verification scheme to adjust the batch size based on the past verification results. The batch size is halved when batch verification fails consecutively over a certain number of times to improve the efficiency of batch verification. Otherwise, the batch size is doubled to increase the verified messages in one batch. If verification fails, the divide-and-conquer approach is utilized to find the invalid messages. Finally, we show the superiority of our design over some related schemes in the literature in terms of verification delay, amount of verified messages, and amount of verified basic safety messages via analysis.

[1] D. Jiang and L. Delgrossi, “IEEE 802.11p: Towards an International Standard for Wireless Access in Vehicular Environments,” in Proc. IEEE Vehicular Technology Conference (VTC Spring), pp. 2036–2040, May 2008.
[2] “IEEE Trial-Use Standard for Wireless Access in Vehicular Environments (WAVE)—security services for applications and management messages,” in IEEE Std. 1609.2, Jul. 2006.
[3] “Dedicated Short Range Communications (DSRC) Message Set Dictionary.” http://standards.sae.org/j2735_201603/, Mar. 2016. [Online; 30-Mar- 2016].
[4] X. Ma, J. Zhang, X. Yin, and K. S. Trivedi, “Design and analysis of a robust broadcast scheme for VANET safety-related services,” IEEE Transactions on Vehicular Technology, vol. 61, no. 1, pp. 46–61, Jan. 2012.
[5] Q. Xu, T. Mak, J. Ko, and R. Sengupta, “Vehicle-to-vehicle safety messaging in DSRC,” in Proc. of the 1st ACM international workshop on Vehicular ad hoc networks, pp. 19–28, ACM, 2004.
[6] M. Raya, P. Papadimitratos, and J. p. Hubaux, “Securing vehicular communications,” IEEE Wireless Communications, vol. 13, no. 5, pp. 8–15, Oct.2006.
[7] Z. Li and C. Chigan, “On resource-aware message verification in VANETs,” in Proc. IEEE International Conference on Communications (ICC), pp. 1–6, May 2010.
[8] J. H. Cheon and J. H. Yi, Fast Batch Verification of Multiple Signatures, pp. 442–457. 2007.
[9] Y. Liu, L. Wang, and H. H. Chen, “Message authentication using proxy vehicles in vehicular ad hoc networks,” IEEE Transactions on Vehicular Technology, vol. 64, no. 8, pp. 3697–3710, Aug. 2015.
[10] X. Zhu, S. Jiang, L. Wang, and H. Li, “Efficient privacy-preserving authentication for vehicular ad hoc networks,” IEEE Transactions on Vehicular Technology, vol. 63, no. 2, pp. 907–919, Feb. 2014.
[11] K. A. Shim, “Reconstruction of a secure authentication scheme for vehicular ad hoc networks using a binary authentication tree,” IEEE Transactions on Wireless Communications, vol. 12, no. 11, pp. 5386–5393, Nov. 2013.
[12] D. He, S. Zeadally, B. Xu, and X. Huang, “An efficient identity-based conditional privacy-preserving authentication scheme for vehicular ad hoc networks,” IEEE Transactions on Information Forensics and Security, vol. 10, no. 12, pp. 2681–2691, Dec. 2015.
[13] A. L. Ferrara, M. Green, S. Hohenberger, and M. s. Pedersen, “Practical short signature batch verification,” in Proc. Topics in Cryptology – CT-RSA 2009: The Cryptographers’ Track at the RSA Conference 2009, San Francisco, CA, USA, pp. 309–324, Springer, April 2009.
[14] S. Biswas, J. Misic, and V. Misic, “ID-based safety message authentication for security and trust in vehicular networks,” in Proc. 2011 31st International Conference on Distributed Computing Systems Workshops, pp. 323–331, June 2011.
[15] S. Biswas and J. Mišić, “Relevance-based verification of VANET safety messages,” in Proc. 2012 IEEE International Conference on Communications (ICC), pp. 5124–5128, June 2012.
[16] S. Biswas and J. Mišić, “A cross-layer approach to privacy-preserving authentication in WAVE-enabled VANETs,” IEEE Transactions on Vehicular Technology, vol. 62, no. 5, pp. 2182–2192, June 2013.
[17] S. Banani and S. Gordon, “Selecting basic safety messages to verify in VANETs using zone priority,” in Proc. The 20th Asia-Pacific Conference on Communication (APCC2014), pp. 423–428, Oct. 2014.
[18] C. Zhang, X. Lin, R. Lu, P. H. Ho, and X. Shen, “An efficient message authentication scheme for vehicular communications,” IEEE Transactions on Vehicular Technology, vol. 57, no. 6, pp. 3357–3368, Nov. 2008.
[19] J. L. Huang, L. Y. Yeh, and H. Y. Chien, “ABAKA: An anonymous batch authenticated and key agreement scheme for value-added services in vehicular ad hoc networks,” IEEE Transactions on Vehicular Technology, vol. 60, no. 1, pp. 248–262, Jan. 2011.
[20] K. A. Shim, “CPAS : An efficient conditional privacy-preserving authentication scheme for vehicular sensor networks,” IEEE Transactions on Vehicular Technology, vol. 61, no. 4, pp. 1874–1883, May 2012.
[21] N. W. Lo and J. L. Tsai, “An efficient conditional privacy-preserving authentication scheme for vehicular sensor networks without pairings,” IEEE Transactions on Intelligent Transportation Systems, vol. 17, no. 5, pp. 1319–1328, May 2016.
[22] S. Jiang, X. Zhu, and L. Wang, “An efficient anonymous batch authentication scheme based on HMAC for VANETs,” IEEE Transactions on Intelligent Transportation Systems, vol. PP, no. 99, pp. 1–12, 2016.
[23] Y. Zhang, W. Lou, W. Liu, and Y. Fang, “A secure incentive protocol for mobile ad hoc networks,” Wireless Networks, vol. 13, no. 5, pp. 569–582, 2007.
[24] C. Zhang, R. Lu, X. Lin, P. H. Ho, and X. Shen, “An efficient identity-based batch verification scheme for vehicular sensor networks,” in Proc. INFOCOM 2008. IEEE The 27th Conference on Computer Communications., Apr. 2008.
[25] D. Boneh, B. Lynn, and H. Shacham, Short Signatures from the Weil Pairing, pp. 514–532. 2001.