Linear Corrector Overcoming Minimum DistanceLimitation for Secure TRNG from (17, 9, 5) Quadratic Residue Code

ETRI Journal

关键词: true random number generator (TRNG);    Shannon entropy;    statistical tests;    post-processing;    nonce;    key generation;    AIS31 standard;   

Others  :  1185995
DOI  :  10.4218/etrij.10.0109.0141

【 摘 要 】

A true random number generator (TRNG) is widely used to generate secure random numbers for encryption, digital signatures, authentication, and so on in crypto-systems. Since TRNG is vulnerable to environmental changes, a deterministic function is normally used to reduce bias and improve the statistical properties of the TRNG output. In this paper, we propose a linear corrector for secure TRNG. The performance of a linear corrector is bounded by the minimum distance of the corresponding linear error correcting code. However, we show that it is possible to construct a linear corrector overcoming the minimum distance limitation. The proposed linear corrector shows better performance in terms of removing bias in that it can enlarge the acceptable bias range of the raw TRNG output. Moreover, it is possible to efficiently implement this linear corrector using only XOR gates, which must have a suitable hardware size for embedded security systems.

   

【 参考文献 】

• [1]W. Killmann and W. Schindler, "A Proposal for Functionality Classes and Evaluation Methodology for True (Physical) Random Number Generators," AIS.31 Standard, 2001, URL: http://www. bsi.bund.de/ zertifiz/zert/interpr/trngk31e.pdf
• [2]J.-S. No and P.V. Kumar, "A New Family of Binary Pseudorandom Sequences Having Optimal Periodic Correlation Properties and Large Linear Span," IEEE Trans. Inf. Theory, vol. IT-35, no. 2, Mar. 1989, pp. 371-379.
• [3]O. Farooq and S. Datta, "Signal-Dependent Chaotic-State-Modulated Digital Secure Communication," ETRI J., vol. 28, no. 2, Apr. 2006, pp. 250-252.
• [4]Y.S. Kim et al., "New Constructions of p-ary Bent Sequences," IEICE Trans. Fundamentals, vol. E87-A no. 2, Feb. 2004, pp. 489-494.
• [5]M. Bucci and R. Luzzi, "Design of Testable Random Bit Generators," CHES 2005, LNCS, vol. 3659, 2005, pp. 147-156.
• [6]J.D. Golic, "New Methods for Digital Generation and Postprocessing of Random Data," IEEE Trans. Computers, vol. 55, no. 10, 2006, pp. 1217-1229.
• [7]B. Sunar, W. Martin, and D. Stinson, "A Provably Secure True Random Number Generator with Built-In Tolerance to Active Attacks," IEEE Trans. Computers, vol. 56, no. 1, 2007, pp. 109-119.
• [8]M. Dichtl and J. Golic, "High-Speed True Random Number Generation with Logic Gates Only," CHES 2007, LNCS, vol. 4727, 2007, pp. 45-62.
• [9]I. Vasyltsov et al., "Fast Digital TRNG Based on Metastable Ring Oscillator," CHES 2008, LNCS, vol. 5154, 2008, pp. 164-180.
• [10]E. Trichina et al., "Supplemental Cryptographic Hardware for Smart Cards," IEEE Micro., vol. 21, no. 6, 2001, pp. 26-35.
• [11]W. Kim et al., "A Platform-Based SoC Design of a 32-Bit Smart Card," ETRI J., vol. 25, no. 6, Dec. 2003, pp. 510-516.
• [12]FIPS PUB 140-1: Security Requirements for Cryptographic Modules, 1994.
• [13]FIPS PUB 140-2: Security Requirements for Cryptographic Modules, 2001.
• [14]W. Schindler and W. Killmann, "Evaluation Criteria for True (Physical) Random Number Generators Used in Cryptographic Applications," CHES 2002, LNCS, vol. 2523, 2003, pp. 431-449.
• [15]Y.-S. Kim and I. Vasyltsov, "New Methods for Efficient Online Test of TRNG," Samsung Journal of Innovative Technology, Communication & Network Technology, vol. 4, no. 1, Feb. 2008, pp. 117-131.
• [16]P. Lacharme, "Post-processing Functions for a Biased Physical Random Number Generator," FSE 2008, LNCS 5086, 2008, pp. 334-342.
• [17]J. von Neumann, "Various Techniques for Use in Connection with Random Digits," Von Neumann’s Collected Works, London: Pergamon, 1963, pp. 768-770.
• [18]Y. Peres, "Iterating von Neumann’s Procedure for Extracting Random Bits," Annals of Statistics, vol. 20, no. 1, 1992, pp. 590-597.
• [19]10.1214/aos/1176348543
• [20]S. Markovski, D. Gligoroski, and L. Kocarev, "Unbiased Random Sequences from Quasigroup String Transformations," FSE 2005, LNCS, vol. 3557, 2005, pp. 163-180.
• [21]M. Dichtl, "Bad and Good Ways of Post-processing Biased Physical Random Numbers," FSE 2007, LNCS 4593, 2007, pp. 137-152.
• [22]F.J. Mac Williams and N.J.A Sloane, The Theory of Error Correcting Codes, Amsterdam: North-Holland Pub., 1977.
• [23]T.M. Cover and J.A. Thomas, Elements of Information Theory, 2nd ed., Hoboken, New Jersey: John Wiley and Sons, 2006.
• [24]T.K. Truong, Y. Chang, and C.D. Lee, "The Weight Distributions of Some Binary Quadratic Residue Codes," IEEE Trans. Inf. Theory, vol. 51, no. 5, May 2005, pp. 1776-1782.
• [25]J.-S. Coron, "On the Security of Random Source," PKC’99, LNCS, vol. 1560, 1999, pp. 29-42.