Please use this identifier to cite or link to this item: http://hdl.handle.net/11455/19387
標題: 具密碼安全強度的擬亂函數與其應用
Cryptographically Strong Pseudorandom Functions and Their Applications
作者: 陳昱升
Chen, Yu-Sheng
關鍵字: Cryptography
密碼學
Information Security
Pseudorandom Function
Pseudorandom Generator
RFID
資訊安全
擬亂函數
亂數產生器
無線射頻辨識
出版社: 資訊科學系所
引用: [1] M. Blum and S. Micali, "How to Generate Cryptographically Strong Sequences of Pseudo-Random Bits", SIAM Journal on Computing, Vol.13, No.4, pp.850-864, 1984. [2] A. C. Yao, "Theory and applications of trapdoor functions", Proceedings of the 23rd IEEE Symposium on Foundations of Computer Science, pp.80-91, 1982. [3] O. Goldreich, S. Goldwasser,and S. Micali, "How to construct random functions", Journal of the ACM, Vol.33, No.4, pp.792-807, 1986. [4] M. Naor and O. Reingold, "Synthesizers and Their Application to the Parallel Construction of Pseudo-Random Functions", Journal of Computer and System Sciences, Vol.58, No.2, pp.336-375, 1999. [5] M. Naor and O. Reingold, "Number-theoretic constructions of efficient pseudo-random functions", Journal of the ACM, Vol.51, No.2, pp.231-262, 2004. [6] M. Naor, O. Reingold, and A. Rosen, "Pseudorandom Functions and Factoring", SIAM Journal on Computing, Vol.31, No.5, pp.1383-1404, 2002. [7] M. Blum, W. S. Evans, P. Gemmell, S. Kannan, and M. Naor, "Checking the Correctness of Memories", Algorithmica, Vol.12, No.2/3, pp.225-244, 1994. [8] O. Goldreich, S. Goldwasser,and S. Micali, "On the Cryptographic Applications of Random Functions", CRYPTO 1984, pp.276-288, 1984. [9] O. Goldreich and R. Ostrovsky, "Software Protection and Simulation on Oblivious RAMs", Journal of the ACM, Vol.43, No.3, pp.431-473, 1996. [10] M. Naor and O. Reingold, "On the Construction of Pseudorandom Permutations: Luby-Rackoff Revisited", Journal of Cryptology, Vol.12, No.1, pp.29-66, 1999. [11] C. H. Papadimitriou, "Computational Complexity", Addison Wesley, 1995. [12] AJ Menezes, PC van Oorschot, and SA Vanstone, Handbook of Cryptography, CRC Press, 1997. [13] J. Plumstead. “Inferring a sequence generated by a linear congruence”, In Proc. 23rd IEEE Symp, On Foundations of Comp. Science, pp. 153-159, 1982. [14] S. Golomb, Shift Register Sequences, Revised Edition. Aegean Park Press: Laguna Hills, CA, 1982. [15] S. W. Golomb. Shift Register Sequences. Aegean Park Press, Laguna Hills, Revised edition ,1982. [16] L. Blum, M. Blum, and M. Shub, "A Simple Unpredictable Pseudo-Random Number Generator", SIAM Journal on Computing, Vol.15, No.2, pp.364-383, 1986. [17] O. Goldreich, "Foundations of Cryptography (Fragments of a Book)", electronic publication:http://theory.lcs.mit.edu/~oded/frag.html, 1995. [18] S. Goldwasser and M. Bellare, "Lecture Notes on Cryptography", http://www.cs.ucsd.edu/users/mihir/papers/gb.html, 2001. [19] Adi Shamir , “On the generation of cryptographically strong pseudorandom sequences”, vol. 1, no. 1, pp.38-44, 1983. [20] D. Long and A.Wigderson, “The Discrete Log Hides O(log n) Bits”, SIAM J. Comput., vol.17, pp.363-372, 1988. [21] U. V. Vazirani and V. V. Vazirani, “Efficient and secure pseudorandom number generation”, Advances in Cryptology-Proceedings of of CRYPTO 84(LNCS 196), pp.193-202, 1985. [22 ] W. Alexi, B. Chor, O. Goldreich, and C.P. Schnorr, “RSA and Rabin functions: Certain parts are as hard as the whole”, SIAM Journal on Computing, Vol.17, pp.194-209, 1988. [23] S. Micali and C.P. Schnorr, "Efficient, perfect polynomial random number generators", Journal of Cryptology, No. 3, 157-172, 1991. [24] J. H°astad, A.W. Schrift, and A. Shamir, “The discrete logarithm modulo a composite hides O(n) bits”, Journal of Computer and System Sciences, Vol.47, pp.376-404, 1993. [25] O. Goldreich and V. Rosen, “On the Security of Modular Exponentiation with Application to the Construction of Pseudorandom Generators”, J. Cryptology, Vol. 16, pp.71-93, 2003. [26] N. Dedić, L. Reyzin, S. Vadhan, “An Improved Pseudorandom Generator Based on Hardness of Factoring”, Security in Communication Networks: Third International Conference (SCN 2002), Vol. 2576 of Lecture Notes in Computer Science, pp.88-101, 2002. [27] E. Biham. D. Boneh, O. Reingold, “Breaking generalized Diffie-Hellman modulo a composite is no easier than Factoring", Information Processing Letters, Vol. 70, pp. 83-87, 1999. [28] Z. Shmuley, “Composite Diffie-Hellman public-key generating systems are hard to. Break”, Technical Report No. 356, Computer Science Department, Technion, Israel, 1985. [29] Y.C. Chang, C.Y. Hsiao,and C.J. Lu, "The Impossibility of Basing One-Way Permutations on Central Cryptographic Primitives", Journal of Cryptology, Vol.19, No.1, 2006. [30] M. Luby and C. Rackoff, “Pseudorandom permutation generators and cryptographic composition", SIAM Journal on Computing, Vol.17, 1988. [31] M. Naor and O. Reingold, “On the construction of pseudorandom permutations: Luby-Rackoff revisited”, J. of Cryptology, Vol.12, 1999. [32] K. Finkenzeller, RFID Handbook: Fundamentals and Applications in Contactless Smart cards and Identification, second ed., John Wiley &Sons, 2003. [33] Simson L. Garfinkel, Ari Juels, Ravi Pappu, “RFID Privacy: An Overview of Problems and Proposed Solutions,” IEEE Security & Privacy, Vol. 3 Issue 3, 2005. [34] S.E. Sarma, S.A. Weis, D.W. Engels, “RFID systems and security and privacy implications,” Workshop on Cryptographic Hardware and Embedded Systems (CHES) 2002, LNCS no. 2523, pp. 454-469, 2003. [35] S.A. Weis, S.E. Sarma, R.L. Rivest, D.W. Engels, “Security and Privacy Aspects of Low-Cost Radio Frequency Identification Systems”, Security in Pervasive Computing 2003, LNCS no. 2802, pp. 201-212, 2004. [36] Miyako Ohkubo, Koutarou Suzuki, and Shingo Kinoshita, “Cryptographic approach to a privacy friendly tag”, RFID Privacy Workshop, MIT, 2003. [37] Gildas Avoine and Philippe Oechslin, “A Scalable and Provably Secure Hash-Based RFID Protocol”, The 2nd IEEE International Workshop on Pervasive Computing and Communication Security (PerSec 2005), pp. 110-114, 2005. [38] Tassos Dimitriou, "A Lightweight RFID protocol to protect against Traceability and Cloning attacks", IEEE International Conference on Security and Privacy for Emerging Areas in Communication Networks(SECURECOMM 2005), 2005. [39] Gene Tsudik, “YA-TRAP: Yet Another Trivial RFID Authentication Protocol”, International Conference on Pervasive Computing and Communications, PerCom 2006.
摘要: 近代密碼學理論主要基植在計算複雜度理論(Computational Complexity Theory)上,把實際的程式對應到理論上的演算法,執行時間在機率多項式時間內的演算法被視為實際上可行的方法,例如在加解密裡,在鑰匙保密的情況下,解密不該能被在多項式時間內完成;在數位簽章裡,簽章不能在多項式時間內被偽造,這些密碼系統的設計通常必須用到具有某種單向性質的元件(primitive)。 在本研究中,我們探討一個重要的密碼學元件—擬亂函數(Pseudorandom function),擬亂函數是一個逼近真亂函數(Random function)的函數,意即經由詢問一個擬亂函數取得其回應值,不能在機率多項式時間內被辨別出此函數是否為真亂函數。 本研究之主要成果可分為兩部分,第一,我們針對前人所提出的一個一般性的擬亂函數建構法進行分析與改善;第二,我們應用擬亂函數此元件,於實用於商品辨識的RFID系統中,設計出一有效率的防偽防追蹤協定。
Modern cryptology is largely based on Computational Complexity Theory. A realistic program corresponds to an algorithm or a Turing machine in the theory. An algorithm running in probabilistic polynomial time is considered to be a feasible method. For instance, for an encryption/decryption method, the decryption should not be accomplished in polynomial time without knowing the decryption key; for a digital signature, the signature should not be forged in polynomial time. The design of those cryptosystem usually needs primitives with some one-way property. In this study, we investigate an important cryptographic primitive—pseudorandom functions. A pseudorandom function is designed to approximate a random function, that is, through querying a pseudorandom function and obtaining the function values, we cannot distinguish the function from a random function in polynomial time. The result of this study can be divided into two parts. First, we analyze and improve a generic method of the construction of pseudorandom functions. Second, we use pseudorandom functions as components to design a practical protocol in the RFID system which is suitable for identifying merchandise. The proposed protocol is efficient and can resist tag counterfeiting and malicious tracing.
URI: http://hdl.handle.net/11455/19387
其他識別: U0005-2606200614162500
文章連結: http://www.airitilibrary.com/Publication/alDetailedMesh1?DocID=U0005-2606200614162500
Appears in Collections:資訊科學與工程學系所

文件中的檔案:

取得全文請前往華藝線上圖書館



Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.