近年來，有關射頻識別 (RFID) 技術的研究引起極大的注意。確信RFID將廣泛取代傳統的條碼技術，提供一種更強有力和方便的電子識別服務。在西元2004年，Ari Juels提出「共軛驗證」 (Yoking Proof) 產生機制以驗證兩個RFID標籤 (Tag) 同時存在。後來，共軛驗證被擴展使用來證明任意數量的標籤同時存在於一個RFID讀取器 (Reader) 電波有效涵蓋範圍內的情境，此驗證機制一般稱為「群組驗證」 (Grouping Proof) 。近年來，具備不同特性的群組驗證的方法也不斷被提出，這些群組驗證方法皆局限於單一群組之應用場合。本論文研究進一步將驗證RFID標籤由單一群組應用場合，延伸至可驗證多個RFID標籤之多群組應用場合。
本論文除了整理與探討現已發表與RFID群組驗證相關的協定，並依據是否具備共軛特性、是否與電子標籤讀取順序有關以及電子標籤採用隨機或指定的方式回應，將這些群組驗證的協定做進一步的分類。
部分現有的協定採用共軛驗證的概念來建構群組驗證。因此，某一個標籤必須等待收到特定的標籤響應，然後才能繼續執行群組驗證。但是，當群組驗證與讀取標籤的順序有關時，將會使驗證的效率降低，驗證的失敗率也會隨著提高。所以在本論文中，改進 Saito and Sakurai 的機制並提出與「標籤讀取的順序無關」 (Tag Reading Order Uncorrelation) 的群組驗證產生方法，以此方法產生群組驗證，不受標籤數量改變的影響，而且可提高群組驗證的效率。
另因為先前的群組驗證機制均指定，由讀取器負責呼叫標籤，並且計算群組驗證，再送給後端系統之驗證器(Verifier)。因此，讀取器事先沒有任何信息可判斷群組驗證的完整性。另外，因為一個惡意標籤可能會阻止產生合法的群組驗證或創造一個無用的群組驗證以進行阻斷攻擊。為了要克服這些問題，本論文也提出一種在線上執行的「選擇回應」(Select-Response) 式群組驗證產生方法，此群組驗證係由驗證器主動掌控每一個驗證程序，而不是使用其他研究者所採用的被動式等待方式。由於這個基本的改變，使得驗證過程變得更簡單又靈活。另外所提的方法亦可進行多個不同群組標籤的驗證，並且具備無碰撞、註記漏失的標籤和與讀取標籤的順序無關的特性。
當群組中的標籤數量變大時，由於無線電波傳播的不確定性，以致於使群組驗證機制的失敗率提高。因此，我們提出採用「動態二元樹防碰撞演算法」(Dynamic Binary Tree Anti-collision Algorithm) 將大群組的標籤再細分為若干小群組的方法，來建構新的群組驗證機制。該解決方案結合了本論文所提的「與讀取標籤的順序無關」的理念和「選擇回應」模式產生「分群驗證」 (Subgrouping Proof)。而「共軛驗證」的觀念是應用在各小群組之間以組合成整個群組的群組驗證。相較於相關的研究中，並未細分為若干小群組的群組驗證機制，本方法可提高群組驗證的效率。
最後，將選擇回應群組驗證的概念應用到供應鏈系統。其中包括具備相互鑑別功能的標籤讀取協定和系統的更新協定。我們也修改了群組標籤移交過程並且使它更加合理化。所提出的協定满足大部份供應鏈系統的要求並且可應用在有多批物品同時在一個供應鏈系統的場合。

Radio Frequency Identification (RFID) technology has generated huge interest in recent years. It is believed that traditional barcodes will be widely replaced by RFID because it can provide a more powerful and convenient electronic identification service. In 2004, Ari Juels introduced a proof for the simultaneous reading of two RFID tags and named it as the “Yoking Proof”. Afterward, the yoking proof had been extended to prove the simultaneous presence of an arbitrarily large number of tags within the broadcast range of a reader, which is generally called the “Grouping Proofs”. This dissertation extends the RFID grouping proofs from multiple tags in a single group to multiple tags in multiple groups.
In this dissertation, a comprehensive survey of the existing RFID grouping proof protocols is provided. In addition, classifications of grouping proof protocols according to yoking or non-yoking, tag reading order correlation or uncorrelation, and random or select response properties are provided.
Some of existing protocols adopted the concept of yoking proof to construct the grouping proofs. That is, a tag is required to wait for a specified tag response before any further actions. Such tag reading order correlation in a grouping proof is inefficient and can raise the failure rate of verification. In this dissertation, the Saito and Sakurai’s protocol is modified in which a grouping proof protocol with tag reading order uncorrelation is proposed. The proposed protocol maintains a fixed length of the grouping proof and improves the overall efficiency during the grouping proof verification process.
Moreover, most of the previous grouping proof protocols designate that a reader is responsible for both the queries and computations of a proof for a verifier. There is no information for the reader to judge the completeness of the proof in advance. In addition, DoS is also possible since a malicious tag can obstruct the generation of a legitimate proof or cause a useless proof to be created. To overcome these problems, an online “Select-Response” grouping protocol is proposed in which the verifier is actively involved instead of just waiting a proof from the reader. With this fundamental change, the verification process becomes simple and flexible. In addition, the proposed protocol can perform multi-group verification. It also possesses collision-free, missing tag identification, and tag reading order uncorrelation properties.
In case of a group with large number of tags, the unreliability of radio wave communication could potentially cause high failure rates in the currently existing grouping proofs. Therefore, a novel way of performing the grouping proof is proposed in which the “Dynamic Binary Tree Anti-collision Algorithm” is employed to subgroup the tags. This solution combines the “Tag Reading Order Uncorrelation” idea and the “Select-Response” scheme from my proposed protocols. Each subgroup will generate its own “Subgrouping Proof”. The yoking proof is then generated between subgroups and finally the grouping proof of the whole group is assembled. Thus, the efficiency of the whole group verification will be improved.
Finally, an application of the Select-Response grouping proof concept is realized in a supply chain system. Two protocols are also presented which includes the tags reading protocol with mutual authentication and the updating protocol. The handover process of group tags is also modified that made it more reasonable. The proposed protocol satisfies most of the requirements of supply chain systems and can be applied on the multi-batch supply chain systems.

[1]Finkenzeller, K., RFID Handbook, second edition, John Wiley & Sons Ltd,
England, pp. 29-57 and pp. 200-212 (2003).
[2]Garfinkel, S., and Rosenber, B., RFID: Applications, Security, and Privacy,
Addison-Wesley Professional, pp. 15-21 (2005).
[3]Damith C. Ranasinghe, D. C., Engels, D. W., and Cole, P. H., “Low-Cost
RFID Systems: Confronting Security and Privacy”, In the Auto-ID Labs
Research Workshop,
www.autoidlabs.org/uploads/media/AUTOIDLABS-WP-SWNET-013.pdf (2005).
[4]EPCglobal Inc., “Class-1 Generation-2 UHF RFID Protocol for Communications
at 860 MHz–960 MHz Versions 1.1.0”,
http://www.epcglobalinc.org/standards/uhfc1g2/uhfc1g2_1_1_0-standard-
20071017.pdf (2007).
[5]Ashton, K., “The History of EPC’s Future”, RFID Journal Magazine,
March/April, http://www.rfidjournal.com/magazine/article/2254 (2006).
[6]ISO, “ISO/IEC 18000-6: Information technology - Radio frequency
identification for item management - Part 6: Parameters for air interface
communications at 860 MHz to 960 MHz”, http://www.iso.org (2004).
[7]ISO, “ISO/IEC 15693: Contactless integrated circuit cards –vicinity
cards”, http://www.iso.org (2000).
[8]International Telecommunication Union (ITU), http://www.itu.int/ITU-
R/terrestrial.
[9]FCC Regulations Part 15 2003. http://en.wikipedia.org/wiki/Part 15.
[10]Yousuf, Y., Potdar, V., “A Survey of RFID Authentication Protocols”,
Proceedings of the 22nd International Conference on Advanced Information
Networking and Application-Workshops, pp. 1346-1350 (2008).
[11]Syamsuddin, I., Dillon, T., Chang, E., and Han, S., “A Survey of RFID
Authentication Protocols Based on Hash-Chain Method”, Proceedings of the
3rd International Conference on Convergence and Hybrid Information
Technology, pp. 559-564 (2008).
[12]Weis, S. A., Sarma, E. S., Rivest, R. L., and Engels, D. W., “Security
and Privacy Aspects of Low-cost Radio Frequency Identification Systems”,
Security in Pervasive Computing, vol. 2802, pp. 50–59 (2004).
[13]Sarma, S., Weis, S. A., and Engels, D., “Radio-frequency Identification:
Risks and Challenges”, RSA CryptoBytes, Vol. 6, No. 1, Winter Spring, pp.
1–9 (2003).
[14]Saito, J., Ryou, J-C., and Sakurai, K., “Enhancing Privacy of Universal
Re-encryption Scheme for RFID Tags”, Proceedings of the Embedded and
Ubiquitous Computing-EUC 2004, vol. 3207, Aizu-Wakamatsu City, Japan, pp.
879-890 (2004).
[15]Stephen, C. B., Matthew, G., Adam, S., Juels, A., Aviel, D. R., and
Michael, S., “Security Analysis of a Cryptographically-Enabled RFID
Device”, Proceedings of the 14th USENIX Security Symposium, pp. 1-16
(2005).
[16]Luo, Z., Chan, T., and Li, J. S., “A Lightweight Mutual Authentication
Protocol for RFID Networks”, Proceedings of the 2005 International
Conference on e-Business Engineering, pp 620-625 (2005).
[17]Juels, A., “RFID Security and Privacy: A Research Survey”, IEEE Journal
on Selected Areas in Communications, Vol. 24, No 2, pp. 381–394 (2006).
[18]Ohkubo, M., Suzuki, K., and Kinoshita, S., “RFID Privacy Issues and
Technical Challenges”, Communication of the ACM, Vol. 48, pp. 66-71
(2005).
[19]Rotter, P., “A Framework for Assessing RFID System Security and Privacy
Risks”, IEEE Pervasive Computing, Vol. 7, No. 2, PP.70-77 (2008).
[20]Alomair, B., and Poovendran, R., “On the Authentication of RFID Systems
with Bitwise Operations”, Proceedings of the second IFIP conference on
New Technologies, Mobility and Security - NTMS'08, pp. 1-6 (2008).
[21]Han, D., and Kwon, D., “Vulnerability of an RFID Authentication Protocol
Conforming to EPC Class 1 Generation 2 Standards”, Computer Standards &
Interfaces, Vol. 31, No. 4, pp. 648-652 (2009).
[22]Juels, A., “Yoking-Proofs for RFID Tags”, Proceedings of the Second IEEE
Annual Conference on Pervasive Computing and Communications Workshops, pp.
138-143 (2004).
[23]Saito, J., and Sakurai, K., “Grouping Proof for RFID Tags”, Proceedings
of the 19th International Conference on AINA, Vol.2, pp. 621- 624 (2005).
[24]Piramuthu, S., “On Existence Proofs for Multiple RFID Tags”, Proceedings
of the IEEE International Conference on Pervasive Services (ICPS’06), pp.
317-320 (2006).
[25]Bolotnyy, L., and Robins, G., “Generalized Yoking-Proofs for a Group of
RFID Tags”, Proceedings of the IEEE International Conference on Mobile
and Ubiquitous Systems, pp.1-4 (2006).
[26]Peris-Lopez Pedro, Julio C. Hernandez-Castro, Juan M. Estevez-Tapiador,
and Arturo Ribagorda, “Solving the Simultaneous Scanning Problem
Anonymously:Clumping Proofs for RFID Tags”, Proceedings of the 3rd
International Workshop on Security, Privacy and Trust in Pervasive and
Ubiquitous Computing, pp.55-60 (2007).
[27]Lien, Y.-H., Leng, X., Mayes, K., and Chiu, J.-H., “Reading Order
Independent Grouping Proof for RFID Tags”, Proceedings of the
Intelligence and Security Informatics (ISI) IEEE ISI 2008 International
Lecture Notes in Computer Science 5075 Springer, Taipei, Taiwan, pp.128-
136 (2008).
[28]Cho, J.-S., Yeo, S.-S., Hwang, S., Rhee, S.-Y., and Kim, S. K., “Enhanced
Yoking Proof Protocols for RFID Tags and Tag Groups”, Proceedings of the
22nd Advanced Information Networking and Applications - Workshops, pp.
1591 – 1596 (2008).
[29]Burmester, M., Medeiros, B. de, and Motta, R., “Provably Secure Grouping-
proofs for RFID Tags”, Proceedings of the International Conference, 8th
Smart Card Research and Advanced Applications (CARDIS 2008), IFIP WG
8.8/11.2, pp. 176-190 (2008).
[30]Leng, X., Lien, Y.-H., Mayes, K. E., Markantonakis, K., and Chiu, J-H.,
“Select-Response Grouping Proof for RFID Tags”, Proceedings of the First
Asian Conference on Intelligent Information and Database Systems (ACIIDS),
Dong Hoi City, Vietnam, pp.73-77 (2009).
[31]Lien, .Y-H., Leng, X., Mayes, K. E., and Chiu, J.-H., “Selected-Response
Grouping Proof and Its Verification Protocol for RFID Tags”, accepted and
to be presented at the International Journal of Intelligent Information
and Database Systems (IJIIDS), (2010).
[32]Pedro Peris-Lopez, Agustin Orfila, Julio C. Hernandez-Castro, and Jan C.A.
van der Lubbe, “Flaws on RFID Grouping-Proofs. Guidelines for future
sound protocols”, Journal of Networks and Computer Applications,
Available online 1 May 2010.
[33]Lenstra, A., and Verheul, E., “Selecting Cryptographic Key Sizes”,
Journal of Cryptography, Vol. 14, No. 4, pp. 255–293 (2001).
[34]Liu, Z., and Peng, D., “True Random Number Generator in RFID Systems
Against Traceability,” Proceedings of the IEEE Consumer Communications
and Networking Conference – CCNS, vol. 1, pp. 620–624 (2006).
[35]Don, R., and CliffWood, H., “Analysis of Tree Algorithm for RFID
Arbitration”, Proceedings of the IEEE International Symposium on
Information Theory, pp. 107-116 (1998).
[36]Shih, D.-H., Sun, P.-L., Yen, D. C., and Huang, S-M., “Taxonomy and
Survey of RFID Anti-Collision Protocols”, Journal of the Computer
Communications, Vol. 29, No. 11, pp. 2150-2166 (2006).
[37]Juels, A., “Minimalist Cryptography for RFID Tags”, Security of
Communication Networks (SCN), pp.149-164 (2004).
[38]Li, Y., and Ding, X., “Protecting RFID Communications in Supply Chains”,
Proceedings of the 2nd ACM Symposium on Information, Computer and
Communications Security (ASIACCS’07), Singapore, pp. 234-241 (2007).
[39]Kapoor, G., Zhou, W., and Piramuthu, S., “RFID and Information Security
in Supply Chains”, Proceedings of the International Conference on Mobile
Ad-hoc and Sensor Networks (MSN’08), pp. 59-62 (2008).
[40]Deursen, T. V., and Radomirovic, S., “Security of an RFID Protocol for
Supply Chains, e-Business Engineering”, Proceedings of the IEEE
International Conference (ICEBE '08), pp. 568-573 (2008).
[41]Cai, S., Li, T., Li, Y., and Robert, D., “Ensuring Dual Security Modes in
RFID-Enabled Supply Chain Systems”, Proceedings of the fifth Information
Security Practice and Experience Conference (ISPEC’09), China, pp. 372-
383 (2009).
[42]Juels, A., Pappu, R., and Parno, B., “Unidirectional Key Distribution
Across Time and Space with Applications to RFID Security”, Proceedings of
the 17th USENIX Security Symposium, pp. 75-90 (2008).
[43]Song, B., “RFID Tag Ownership Transfer”, Proceedings of the RFID
Security Conference (RFIDSec’08), Budapest, Hungary.
events. iaik.tugraz.at/RFIDSec08/Papers/Publication/15 - Song - Ownership
Transfer - Paper.pdf (2008)
[44]Garfinkel, S. L., Juels, A. and Pappu, R., “RFID Privacy: An Overview of
Problems and Proposed Solutions”, Security &Privacy Magazine, IEEE, Vol.
3, pp. 34-43 (2005).
[45]Huang, H.-H. and Ku, C.-Y., “A RFID Grouping Proof Protocol for Medication
Safety of Inpatient”, Journal of Medical Systems, Vol. 33, No. 6, pp. 467-
474 (2009).
[46]Perrin, R. A. and Simpson, N., “RFID and Barcodes – Critical Importance
in Enhanceing Safe Patient Care”, Journal of Healthcare Information
Management, Vol. 18, pp. 433-439 (2004).
[47]Wu, F., Kuo, F., and Liu, L.-W., “The Application of RFID on Drug Safety
of Inpatient Nursing Healthcare”, Proceedings of the 7th International
Conference on Electronic Commerce, pp. 85–92 (2005).
[48]Liao, P.-C., Liu, L., Kou, F. And Jin, M.-H., “Developing a Patient
Safety Based RFID Information System- an Empirical in Taiwan”,
Proceedings the International Conference on Management of Innovation and
Technology, pp. 585-589 (2006)
[49]Lai, C-L., Chien, S-W., Chang, L-H., Chen, S-C., and Fang, K., “Enhancing
Medication Safety and Healthcare for Inpatients Using RFID”,
Proceedings of the Portland International Center for Management of
Engineering and Technology ( PICMET 2007), Vol. 1-6, Oregon, Portland, pp.
2783-2790 (2007).
[50]Chien, H.-Y., Yang, C.-C., Wu, T.-C., and Lee, C.-F., “Two RFID-based
Solutions to Enhance Inpatient Medication Safety”, Journal of Medical
Systems, http://www.springerlink.com/content/x2n7x062637g6k74/, May
(2010).