[發(fā)明專利]一種生成隨機(jī)數(shù)的方法和裝置

有效

• 申請(qǐng)?zhí)枺?/td>: 201710978576.9
• 申請(qǐng)日: 2017-10-19
• 公開(kāi)（公告）號(hào): CN107769921B
• 公開(kāi)（公告）日: 2021-03-26
• 發(fā)明（設(shè)計(jì)）人: 楊勝天;毛松志
• 申請(qǐng)（專利權(quán)）人: 浙江工商大學(xué)
• 主分類號(hào): H04L9/08
• 分類號(hào): H04L9/08;G06F17/15
• 代理公司: 暫無(wú)信息
• 代理人: 暫無(wú)信息

本發(fā)明公開(kāi)了一種生成隨機(jī)數(shù)的方法和裝置，屬于計(jì)算機(jī)領(lǐng)域。所述生成隨機(jī)數(shù)的方法包括：采集指定信源生成的數(shù)據(jù)；以預(yù)設(shè)的信源條件和泄密信道條件對(duì)已采集的數(shù)據(jù)序列在信息泄露情況下的信息量的置信區(qū)間進(jìn)行估計(jì)；使用區(qū)間算法對(duì)所述采集的數(shù)據(jù)進(jìn)行處理，輸出二進(jìn)制序列；使用置換函數(shù)對(duì)所述由區(qū)間算法輸出的二進(jìn)制序列進(jìn)行處理，并根據(jù)所述對(duì)已采集數(shù)據(jù)序列信息量的置信區(qū)間的估計(jì)選擇性地輸出經(jīng)置換函數(shù)處理后的二進(jìn)制序列的部分比特。所述生成隨機(jī)數(shù)的裝置包括數(shù)據(jù)采集模塊、信息估計(jì)模塊、區(qū)間算法模塊和置換函數(shù)模塊。該發(fā)明能在一般的信源信息泄露情況下從一般信源生成的數(shù)據(jù)中以接近最優(yōu)的效率提取高質(zhì)量的均勻隨機(jī)比特流。

技術(shù)領(lǐng)域

本發(fā)明涉及計(jì)算機(jī)領(lǐng)域，特別涉及一種生成隨機(jī)數(shù)的方法和裝置。

背景技術(shù)

隨機(jī)數(shù)在計(jì)算機(jī)仿真和信息安全等領(lǐng)域具有廣泛的應(yīng)用。任何一種生成隨機(jī)數(shù)的方法都需要從某個(gè)隨機(jī)信源采集數(shù)據(jù)，進(jìn)而從信源數(shù)據(jù)中提取隨機(jī)性，生成服從目標(biāo)分布的隨機(jī)數(shù)。隨機(jī)數(shù)的質(zhì)量(即隨機(jī)數(shù)真實(shí)分布與目標(biāo)分布的統(tǒng)計(jì)距離)和生成隨機(jī)數(shù)的效率(即生成相同隨機(jī)數(shù)數(shù)量下消耗信源數(shù)據(jù)的多少)是評(píng)價(jià)隨機(jī)數(shù)生成方法的重要指標(biāo)。由于具有二元均勻分布的獨(dú)立同分布隨機(jī)序列(簡(jiǎn)稱均勻隨機(jī)比特流)可以方便地用于生成其它概率分布的隨機(jī)數(shù)，隨機(jī)數(shù)發(fā)生器通常設(shè)計(jì)為輸出均勻隨機(jī)比特流。

在信源統(tǒng)計(jì)模型已知的條件下，區(qū)間算法(Interval Algorithm，如文獻(xiàn)[1])不僅可以生成高質(zhì)量的隨機(jī)數(shù)，而且生成隨機(jī)數(shù)的效率是各種已知方法中最高的。它的缺點(diǎn)是依賴信源統(tǒng)計(jì)模型的準(zhǔn)確度。若信源統(tǒng)計(jì)模型與信源的真實(shí)概率分布有一定差異，即使信源攜帶了充足甚至更多的信息量，其輸出的隨機(jī)數(shù)質(zhì)量仍無(wú)法得到保證。特別地，如果信源數(shù)據(jù)的部分信息經(jīng)某個(gè)泄密信道泄露給隨機(jī)數(shù)的使用方，則其隨機(jī)數(shù)的質(zhì)量急劇惡化。

有種提取器(Seeded Extractor，如文獻(xiàn)[2])可以在信源信息泄露的情況下輸出高質(zhì)量的均勻隨機(jī)比特流，只要信源數(shù)據(jù)在信息泄露情況下依然攜帶了足夠的信息量。該方法在實(shí)施時(shí)，除了需要提供信源數(shù)據(jù)，還需要提供一個(gè)隨機(jī)種子，即一個(gè)定長(zhǎng)均勻分布的隨機(jī)二進(jìn)制串，且與信源數(shù)據(jù)統(tǒng)計(jì)獨(dú)立。這種方法的缺點(diǎn)是定長(zhǎng)輸入定長(zhǎng)輸出，其效率是按最低信息量設(shè)計(jì)的，當(dāng)信源數(shù)據(jù)含有較高的信息量時(shí)，其無(wú)法減少信源數(shù)據(jù)的消耗或生成更多的均勻隨機(jī)比特。

用于比特固定(Bit-Fixing)信源的(無(wú)種)提取器(如文獻(xiàn)[3])是一類與有種提取器類似但專門用于信源信息泄露情形的隨機(jī)數(shù)生成方法。該方法可以在隨機(jī)數(shù)使用者知道信源數(shù)據(jù)的某些比特時(shí)依然輸出具有較高質(zhì)量的均勻隨機(jī)比特串，只要使用者知道的比特?cái)?shù)不超過(guò)設(shè)計(jì)的最大值。這種方法僅適用于獨(dú)立同分布的二元均勻分布信源，且信息泄露方式也僅考慮每個(gè)比特為泄露或不泄露兩種情形。而且，這種方法同樣存在與有種提取器相似的固定生成效率的缺點(diǎn)。

綜上所述，對(duì)于一般信息泄露情況下的一般信源的隨機(jī)數(shù)生成問(wèn)題，現(xiàn)有的方法要么無(wú)法生成高質(zhì)量的隨機(jī)數(shù)，要么無(wú)法保證較高的隨機(jī)數(shù)生成效率。

參考文獻(xiàn)：

[1]Uyematsu T,Li Y.Two algorithms for random number generationimplemented by using arithmetic of limited precision[J].IEICE Transactions onFundamentals of Electronics,Communications and Computer Sciences,2003,E86-A(10):2542-2551.

[2]Guruswami V,Umans C,Vadhan S.Unbalanced expanders and randomnessextractors from Parvaresh-Vardy codes[J].Journal of the ACM,2009,56(4):1-34.