Please use this identifier to cite or link to this item:
標題: 具密碼安全強度的擬亂函數與其應用
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:, 1995. [18] S. Goldwasser and M. Bellare, "Lecture Notes on Cryptography",, 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)的函數,意即經由詢問一個擬亂函數取得其回應值,不能在機率多項式時間內被辨別出此函數是否為真亂函數。


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.
其他識別: U0005-2606200614162500
Appears in Collections:資訊科學與工程學系所

Show full item record

Google ScholarTM


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