從擴展圖構造散列函數的製作方法

2023-05-31 20:13:16

專利名稱：從擴展圖構造散列函數的製作方法
從擴展圖構造散列函數
背學
散列函數構造在許多算法和密碼協議中使用。它們是將其像"均勻"分布
的函數/'u + s，其中iu^isi。換言之，對於大多數
K",ltve"l/W〃)l接近於l^。
使衝突對(colliding pair)，即使得/(力=/6^的對(&力的數量最小化的散 列函數是非常有用的。對於散列函數的密碼學應用，通常希望工程設計衝突的 問題是困難的。這意味著找到使得/w =/^的不同元素^和;;的任務在計算上 是困難的。通常，對於以下較弱的性質是感興趣的給定x，找到另一》使得 /^=/6^是困難的。
概述
提供本概述以便用簡化的形式介紹將在以下詳細描述中進一步描述的一 些概念。本概述並不旨在確定所要求保護的主題的關鍵特徵或必要特徵，也不 旨在用於幫助確定所要求保護的主題的範圍。
鑑於上述內容，描述了從擴展圖(expander graph)構造散列函數。在一 方面，走査作為散列函數的輸入的擴展圖。使用輸入消息的相應子集來走査該 擴展圖。散列函數的輸出是所走查的最後一個頂點的標籤。
附圖簡述
在附圖中，組件參考標號最左邊的數字標識該組件首次出現的特定圖。

圖1示出了根據一個實施例的用於從擴展圖構造散列函數的示例性系統。 圖2示出了根據一個實施例的用於從擴展圖構造散列函數的示例性過程。 圖3示出了根據一個實施例的用於從擴展圖構造散列函數的示例性過程。 圖4示出了其中可全部或部分地實現從擴展圖的散列函數構造的合適的 計算環境的一個示例。詳細描述 綜述
以下參考圖1到4描述用於從擴展圖構造散列函數的系統(例如，系統、 裝置、計算機可讀介質等)和方法。散列函數通過在特定擴展圖上走查來構造。 對一擴展圖的隨機走查非常快速地混合，因此散列函數輸出在輸入消息是均勻 地隨機的時候一般是均勻的。在一個實現中，該系統和方法使用提取器
(extractor)結合擴展圖來產生散列函數。在此實現中，輸入消息對最小熵 (min-entropy)具有特定下限。例如，用密碼籤署一消息(通過散列來完成)
是在向該消息添加"隨機填充(random pad)"之後完成的。(該過程將熵注
入到籤名中)。假設輸入消息具有某一少量的熵，則利用提取器來提取該隨機
性然後根據提取器的輸出執行走查。
現在更詳細描述用於從擴展圖構造散列函數的系統列和方法的這些和其
它方面。
示例性系統
儘管並非必需，但是用於從擴展圖構造散列函數的系統和方法將在由諸如 個人計算機等計算設備執行的計算機可執行指令(程序模塊)的一般上下文中 描述。程序模塊一般包括執行特定的任務或實現特定的抽象數據類型的例程、 程序、對象、組件、數據結構等等。儘管該系統和方法是在上述上下文中描述 的，但是以下所描述的動作和操作也可以用硬體來實現。
圖1示出了根據一個實施例的用於從擴展圖構造散列函數的示例性系統 100。系統100包括計算設備102,它包括耦合到系統存儲器106的一個或多個 處理單元104。處理器104從程序模塊108中取出並執行電腦程式指令，並 從系統存儲器106存取程序數據110部分。程序模塊108包括，例如擴展圖散 列函數構造模塊("EGHF構造模塊")112和其它程序模塊114。其它程序 模塊114包括，例如作業系統和利用由模塊112生成的基於擴展圖的散列函數 構造116的一個或多個應用程式。存在對其可用這一散列函數構造116的許多 應用程式。例如，這一構造可用於實現密碼術、散列表、糾錯、音頻標識、Rabin-Karp串搜索算法等的一個或多個應用程式。
EGHF構造模塊112從輸入消息118和"個頂點的擴展圖120生成散列函 數構造116。擴展圖118是具有高頂點或邊擴展，或者換言之是高度連接的稀 疏圖。在一個實現中，擴展圖118是Ramanujan圖。在一個實現中，輸入消息 118具有一隨機性程度(或熵)。
例如，在一個實現中，擴展圖120如下確定。設p是質數，並設￡ (^p)
是另一質數。擴展圖G(p, f)具有V作為其頂點集，V是有限域Fq上的超奇異
(supersingular) j不變式(j-invariant) , q=p2。如果在其j不變式是j！和j2的 超奇異橢圓曲線之間有次數為￡的同源，則在頂點j,和J2之間有一條邊。圖 G(p,《)被稱為是￡+1正則Ramanujan圖。G(p， ￡)的頂點數是四元數代數B^的 類數，這大約是p/12。 G(p, ￡)是擴展圖120。
在另一實現中，擴展圖120是Lubotzky-Phillips-Sarnak擴展圖，如在以下 "替換實施例"一節中所描述的。
為了生成散列函數構造116,擴展圖散列函數構造模塊112標識消息118。 在一個實現中消息具有熵次數。EG HF構造模塊112向構成擴展圖120的"個 頂點中的每一頂點分配相應的名稱或標籤。當輸入消息具有與其相關聯的熵次 數時，EGHF構造模塊112用一提取器函數來提取(確定)隨機性程度。從這 一消息中提取隨機性的示例性的這樣的提取函數和技術在以下題為"從輸入中 提取隨機性"一節中更詳細描述。
鑑於標識要隨機地走查(訪問)的擴展圖120的頂點的可配置頂點邊約定， 構造模塊112基於所提取的熵次數(當存在時)或其它客觀準則(以下描述) 來標識輸入消息118的k長度比特段。走査擴展圖120的示例性操作在以下題 為"示例性過程" 一節中更詳細描述。與所走査的頂點中的最後一個頂點相關 聯的相應名稱/標籤表示散列函數構造114的輸出。
從輸入中提取隨機性
最小熵設X是在{0, l}n中取值的隨機變量。X的最小熵被定義為以下量
分布接近度(closeness):設X和Y是{0， l"上的兩個分布。如果formula see original document page 8
則它們被認為是e接近(e-close)的(￡是實數)。
提取器如果對最小熵(O，ir上的任何隨機變量X，至少k和W ({0, l}d 上的均勻分布)，分布AW(X，"J對Um是e接近的，則函數
￡w:{0，l}"x{0,l}rf—{0,1}"被稱為(^)提取器((&e)-extractor)。
定理如果ficW0,irx(0,ir"M0,ir"是(^)提取器，則對於隨機種子
ex e {0,l}rf的大多數選擇，分布E:"(Z,t/》對Um是e接近的。
證明分布五;"(X，^)可被描述為在由cre(0,ir索引的分布的簇;^中均勻
地隨機選擇一分布，其中o"^0，ir由X,-E對(y,c7)定義。五W是提取器的事實
意味著這些分布中的許多都對Um是e接近的(證明結束)。
如果"至少是log、並且附=^—",其中a是任意實數，則多項式時間提取 器的構造對於任何*>^ (/0都是已知的。
散列函數的構造
表示對散列函數構造116的輸入的隨機變量M (即，輸入消息118)具有 至少為k)g^"的最小熵，其中"是G(p，f)的頂點數，且々>0。設{0，1"是輸入
空間。為確定M的熵次數122，構造模塊112實現提取器函數五;^，並用參數 A = log1""來修正函數￡w: {0,1}W x{0,l}rf — {0,l}m ， e非常小並且w = 0(log1+a ")。
出於示例性說明的目的，這些參數被示為"其它數據"124的相應部分。系統 100假定^ = ^(1).。構造模塊112從{0, l"中均勻地隨機選取"。給定輸入 xe{0,l}w，構造模塊112計算c7-^(;c,")(即，熵次數122)。該構造的結果
是大小為w的串。構造模塊112從某一固定頂點vo開始沿著由w給出的方向 對m執行走査，並且散列函數116的輸出是走查中的最終頂點的標籤。
對於其節點是超奇異橢圓曲線對質數p的模，並且邊是橢圓曲線之間次數 為f的同源的擴展圖，可如下在圍繞該圖執行走査步驟
在對應於橢圓曲線E的節點處開始，首先找出的f扭矩的生成元戶和
g。為此
1. 設"為使得^(E[f])s々。
2. 設5=6￡(^);五上的有理點；的個數(原始)。3. 設s-S/"，其中產是整除S的《的最大冪(注意*^2)。
4. 從￡[。中隨機地選取兩個點屍和2:
(a) 從A(々)中隨機地選取兩個點U、 V。
(b) 設屍'"f/且Q'-W，如果屍'或2'等於(9,則重複步驟(i)。
(c) 找出最小的,;，/2 ，使得f'屍VO且^2^0，但是,+1屍'=6>且
f 2"g' = O 。
5. 使用公知的Shank的小步一大步(Baby-steps-Giant-steps)算法，確定Q
是否屬於由P生成的群。如果是，則重複步驟(d)。 《+ l條橢圓曲線上的々中與五同源的j不變式是乂,…,力w。為找到它們
(a) 對於W"，設Gi-〈Q〉且Gw"P + (i-i;TQ〉。
(b) 對於每一/， 1&、"1，使用Vdu公式計算橢圓曲線五/G的j不變 式。
如果使用例如具有2同源的超奇異橢圓曲線的圖，則可用以下顯式方式進 行隨機走査在每一步，在找到E的三個非平凡2扭矩點之後，按照其x坐標 以預先指定的方式對它們進行排序。然後，對散列函數使用輸入比特來確定要 選擇哪一點來對橢圓曲線求商以到達走查中的下一節點。
散列函數幾乎是均勻的證明
按照定理，由擴展圖散列函數構造模塊112實現的提取器函數的輸出接近 均勻，並且在擴展圖120上進行的走查非常接近隨機走査。(走査是隨機的僅
僅意味著在圖上的某一頂點v處，在下一步在其任一相鄰點處的可能性是相等 的。)現在，由於圖G(p，C)具有"個頂點，並且m:Q(log""")，因此走査迅速
混合併且輸出頂點非常接近均勻。接著，使得以上陳述更精確。在w個頂點的 c/正則圖G (例如)上的O(logn)步的隨機走査迅速混合的一種表述方式是formula see original document page 9
其中s很小，^是G的鄰接矩陣，v可被取作為任一標準單位向量，T是向量(l， 1， ...， 1)。矩陣可被認為是圖120上的均勻隨機Markov鏈的轉移矩陣。在此實現中，系統100 在圖120上實現幾乎隨機的走査。這可被認為是使用矩陣B作為轉移矩陣，使
得
丄M
並且S是很小的實數(其中符號l l表示矩陣模)。換言之，構造模塊112將隨
機走査攝動一較小的量。以下定理示出該新的隨機走查在S可取得足夠小的時 候快速混合。
定理設^和萬是兩個子隨機矩陣，貝1」|^-^卜44-4。 證明可將差^-54寫為
0轟-1
對兩邊取模並使用M卜M卜i的事實(因為它們是子隨機矩陣)，得到結 果。(證明結束)。
由於所進行的隨機走查的長度是O(log n)。如果可將參數5安排如下 、1og "
則所得的近似隨機走查也將快速混合。這可通過將提取器的參數s設為等於以
下來安排 (9
1
log w
抗衝突
在這一散列函數116下明確地找到衝突等效於找到相同C次方的一對超奇 異橢圓曲線之間的兩個同源。如果圖G(p,f)沒有小環，則這一問題是非常困難 的，因為在曲線之間構造高次同源公知地是計算上的難題。
替換實施例
作為對上述使用圖G(p, 的 一 種替換，系統100利用了 Lubotzky-Phillips-Sarnak擴展圖120。設￡和p是兩個不同的質數，其中￡是小質數，而p相當大。還假設p和f ^lmod4並且f是modp的二次剩餘(這是 一-^三lmodp的情況)。用X^來表示具有參數f和p的LPS圖。接著定義 構成圖Xt,p的頂點和邊。Xt,p的頂點是PSL(2,Fp)中的矩陣，即不可逆2x2矩陣， 其項Fp中，行列式為l，以及對任何矩陣A的等價關係A =-A。給定一行列 式為1的2x2矩陣A，頂點的名稱將是A的項或-A的項的4元組，取決於在 集合(0,…，p-l"的普通排序中哪一個在字典順序上更小。接著報述構成圖的邊。 矩陣A連接到矩陣giA，其中g,是以下顯式定義的矩陣。設i是滿足i2E -l m0d p的整數。對等式gQ2+ gl2+ g22+ g32 = €恰好有8(f+l)個解g = (gG, gl, g2, g3)。在 這些解中只有￡+1個的§>0且為奇數，並且對]=1,2, 3, gj是偶數。對於每
一這樣的g，關聯矩陣
這給出了 PSL(2,Fp)中￡+1個矩陣的集合S。 gi是此集合中的矩陣。事實是， 如果g在S中，則g"也在S中。此外，由於￡很小，因此，該矩陣集合S可 通過窮盡搜索非常快地找到。
示例性過程
圖2示出了根據一個實施例的用於從擴展圖構造散列函數的示例性過程 200。出於示例性描述的目的，過程200的操作相對於圖1的系統100的組件 來描述。組件參考標號最左邊的數字指示了該組件首次被描述的特定圖。
在框202處，EG HF構造模塊112 (圖1)將輸入消息118劃分成段。例 如，輸入消息的長度為N。假設在k正則擴展圖120中有w個頂點(每一頂點 具有名稱/標籤)，則從任一頂點出發的每一條邊的名稱將具有logk比特。輸 入消息118被分解成長度為logk的塊。在框204處，EGHF構造模塊112走 査作為對散列函數的輸入的擴展圖120。走查如下確定假定在某一頂點v處， 走査中的下一頂點通過從輸入中讀取下一 log k的塊以確定從頂點v出發的將 遍歷的邊來確定，該邊的另一端點將是走査的下一頂點。例如，EGHF構造模 塊112從由輸入消息118的前k個比特(段/塊)指定的第一頂點開始對擴展圖 120中的邊的隨機走査。在擴展圖120中走査的下一頂點由下一 logk比特的塊 來指定。考慮到指定邊的名稱如何對應於擴展圖120中的頂點的約定，迭代地執行這些運算。 一個示例性的這樣的約定是對於每一頂點V，存在函數 /V:{1,...,W4K。由此，y;(l)是從V出發的第一條邊，乂(2)是從V出發的第二
條邊，依此類推。
在框206處，EGHF構造模塊112確定所走査的最後一個頂點的標籤。在 框208處，EGHF構造模塊112輸出標籤作為散列函數的結果。
圖3示出了根據一個實施例用於從擴展圖構造散列函數的示例性過程。出 於示例性描述的目的，過程300的操作相對於圖1的系統100的組件來描述。 在框302處，擴展圖散列函數構造模塊("EGHF構造模塊")112 (圖1)標 識具有熵次數的消息118。在框304處，EGHF構造模塊112向擴展圖120中 的每一頂點分配相應的標籤。在框306處，EGHF構造模塊112使用提取器函 數來確定輸入消息118中的熵次數。所確定的次數被示為所提取的熵次數122。 在框308處，EGHF構造模塊基於所提取的熵次數122走查擴展圖120。在框 310處，EGHF構造模塊112輸出與所走查的最後一個頂點的標籤以及擴展圖 120作為散列函數構造116的結果。5卩，框302到310的操作對應於散列函數 構造116的操作。
示例性操作環境
圖4示出了其中可全部或部分實現從擴展圖構造散列函數的合適的計算 環境的一個示例。計算性計算環境400僅為適用於圖1的示例性系統以及圖2 和3的示例性操作的計算環境的一個示例，並非對此處所描述的系統和方法的 使用範圍或功能提出任何局限。也不應將計算環境400解釋為對計算環境400 中示出的任一組件或其組合具有任何依賴性或要求。
此處所描述的方法和系統可以使用眾多其它通用或專用計算系統環境或 配置來操作。適合使用的眾所周知的計算系統、環境和/或配置的示例包括但不 限於，個人計算機、伺服器計算機、多處理器系統、基於微處理器的系統、網 絡PC、小型機、大型機、包括任一上述系統或設備的分布式計算環境等等。 該框架的緊湊或子集形式也可以在諸如手持式計算機或其它計算設備等有限 資源的客戶機中實現。本發明在其中任務由通過通信網絡連結的遠程處理設備 來執行的分布式計算環境中實踐。在分布式計算環境中，程序模塊可以位於本地和遠程存儲器存儲設備中。
參考圖4，用於從擴展圖構造散列函數的示例性系統包括實現例如圖1的
系統100的計算機410形式的通用計算設備。以下描述的計算機410的各方面 是圖1的計算設備102的示例性實現。計算機410的組件可包括但不限於，處 理單元420、系統存儲器430以及將包括系統存儲器的各類系統組件耦合至處 理單元420的系統總線421。系統總線421可以是若干種總線結構的任一種， 包括存儲器總線或存儲器控制器、外圍總線以及使用各類總線體系結構的任一 種的局部總線。作為示例而非局限，這類體系結構包括工業標準體系結構(ISA) 總線、微通道體系結構(MCA)總線、增強型ISA (EISA)總線、視頻電子 技術標準協會(VESA)局部總線、外圍部件互連(PCI)總線(也稱為小背板 (Mezzanine)總線)。
計算機410通常包括各種計算機可讀介質。計算機可讀介質可以是可由計 算機410訪問的任一可用介質，包括易失性和非易失性介質、可移動和不可移
動介質。作為示例而非局限，計算機可讀介質包括計算機存儲介質和通信介質。 計算機存儲介質包括以用於儲存諸如計算機可讀指令、數據結構、程序模塊或
其它數據等信息的任一方法或技術實現的易失性和非易失性，可移動和不可移 動介質。計算機存儲介質包括但不限於，RAM、 ROM、 EEPROM、快閃記憶體或其 它存儲器技術、CD-ROM、數字多功能盤(DVD)或其它光碟存儲、磁盒、磁 帶、磁碟存儲或其它磁存儲設備、或可以用來儲存所期望的信息並可由計算機 410訪問的任一其它介質。
通信介質通常以諸如載波或其它傳輸機制等已調製數據信號來體現計算 機可讀指令、數據結構、程序模塊或其它數據，並包括任一信息傳送介質。術 語"已調製數據信號"指以對信號中的信息進行編碼的方式設置或改變其一個 或多個特徵的信號。作為示例而非局限，通信介質包括有線介質，如有線網絡 或直接連線連接，以及無線介質，如聲學、RF、紅外和其它無線介質。上述任 一的組合也應當包括在計算機可讀介質的範圍之內。
系統存儲器430包括易失性和/或非易失性存儲器形式的計算機存儲介質， 如只讀存儲器(ROM) 431和隨機存取存儲器(RAM) 432。基本輸入/輸出系 統433 (BIOS)包括如在啟動時幫助在計算機410內的元件之間傳輸信息的基本例程，它通常儲存在ROM431中。RAM432通常包含處理單元420立即可 訪問和/或當前正在操作的數據和/或程序模塊。作為示例而非局限，圖4示出 了作業系統434、應用程式435、其它程序模塊436和程序數據437。
計算機410也可包括其它可移動/不可移動、易失性/非易失性計算機存儲 介質。僅作示例，圖4示出了對不可移動、非易失性磁介質進行讀寫的硬碟驅 動器441，對可移動、非易失性磁碟432進行讀寫的磁碟驅動器431，以及對 可移動、非易失性光碟436，如CDROM或其它光介質進行讀寫的光碟驅動器 433。可以在示例性操作環境中使用的其它可移動/不可移動、易失性/非易失性 計算機存儲介質包括但不限於，磁帶盒、快閃記憶體卡、數字多功能盤、數字錄像帶、 固態RAM、固態ROM等等。硬碟驅動器441通常通過不可移動存儲器接口， 如接口 440連接到系統總線421，磁碟驅動器431和光碟驅動器433通常通過 可移動存儲器接口，如接口 430連接到系統總線421。
上文討論並在圖4示出的驅動器及其關聯的計算機存儲介質為計算機410 提供了計算機可讀指令、數據結構、程序模塊和其它數據的存儲。例如，在圖 4中，示出硬碟驅動器441儲存作業系統444、應用程式443、其它程序模塊 446和程序數據447。注意，這些組件可以與作業系統434、應用程式433、其 它程序模塊436和程序數據437相同，也可以與它們不同。應用程式433包括 例如圖1的計算設備102的程序模塊108。程序數據437包括例如圖1的計算 設備102的程序數據110。這裡對作業系統444、應用程式443、其它程序模塊 446和程序數據447給予不同的標號來說明至少它們是不同的副本。
用戶可以通過輸入設備，如鍵盤462和定位設備461 (通常指滑鼠、跟蹤 球或觸摸墊)向計算機410輸入命令和信息。其它輸入設備(未示出)可包括 話筒、操縱杆、遊戲手柄、圓盤式衛星天線、掃描儀等等。這些和其它輸入設 備通常通過耦合至系統總線421的用戶輸入接口 460連接至處理單元420，但 是也可以通過其它接口和總線結構連接，如並行埠、遊戲埠或通用串行總 線(USB)。
監視器491或其它類型的顯示設備也通過接口，如視頻接口 490連接至系 統總線421。除監視器之外，計算機也可包括其它外圍輸出設備，如印表機496 和音頻設備497，它們通過輸出外圍接口 493連接。計算機410可以使用到一個或多個遠程計算機，如遠程計算機480的邏輯 連接在網絡化環境中操作。在一個實現中，遠程計算機480表示圖1的計算設 備102或聯網計算機104。遠程計算機480可以是個人計算機、伺服器、路由 器、網絡PC、對等設備或其它常見的網絡節點，並根據其具體實現，可以包 括許多或所有相對於計算機410所描述的元件，儘管在圖4中僅示出了存儲器 存儲設備481。圖4描述的邏輯連接包括區域網(LAN) 471和廣域網(WAN) 473，但也可包括其它網絡。這類網絡環境常見於辦公室、企業範圍計算機網 絡、內聯網以及網際網路。
當在LAN網絡環境中使用時，計算機410通過網絡接口或適配器470連 接至LAN471。當在WAN網絡環境中使用時，計算機410通常包括調製解調 器472或用於通過WAN473，如網際網路建立通信的其它裝置。數據機472 可以是內置或外置的，它通過用戶輸入接口 460或其它適當的機制連接至系統 總線421。在網絡化環境中，相對於計算機410所描述的程序模塊或其部分可 儲存在遠程存儲器存儲設備中。作為示例而非局限，圖4示出遠程應用程式483 駐留在存儲器設備481上。可以理解，示出的網絡連接是示例性的，也可以使 用在計算機之間建立通信鏈路的其它手段。
結論
儘管以對結構特徵和/或方法操作或動作專用的語言描述了用於從擴展圖 構造散列函數的系統和方法，但是可以理解，所附權利要求書中定義的實現不 一定限於所描述的具體特徵或動作。相反，系統100的具體特徵和操作是作為 實現所要求保護的主題的示例性形式而公開的。
權利要求
1.一種計算機實現的方法，包括根據對一散列函數的輸入走查一擴展圖，所述擴展圖是使用輸入消息的相應子集來走查的；確定所走查的最後一個頂點的標籤；以及輸出所述標籤作為所述散列函數的結果。
2. 如權利要求l所述的方法，其特徵在於，所述擴展圖是Ramanujan圖。
3. 如權利要求1所述的方法，其特徵在於，所述擴展圖是 Lubotzky-Phillips-Sarnak擴展圖。
4. 如權利要求1所述的方法，其特徵在於，所述擴展圖是有限特徵域p 上的超奇異橢圓曲線的圖。
5. 如權利要求l所述的方法，其特徵在於，所述結果是密碼散列。
6. 如權利要求1所述的方法，其特徵在於，找出所述散列函數的衝突在 計算上是困難的。
7. 如權利要求1所述的方法，其特徵在於，所述輸入消息具有特定的熵 次數，並且其中，所述散列函數是抗衝突的。
8. 如權利要求l所述的方法，其特徵在於，走查還包括 將所述輸入消息劃分成段；以及對這些段中的至少一個子集，基於一子集的特定一段的各方面來確定到所 述擴展圖中的下一相應頂點的路徑。
9. 如權利要求l所述的方法，其特徵在於，所述擴展圖包括"個頂點， 其中所述輸入消息具有一熵次數，並且其中，所述方法還包括向所述圖的各頂點分配相應的標籤； 確定所述熵次數；其中，走査還包括使用所述熵次數來走査所述w個頂點以標識完全隨機的 頂點輸出；並且所述輸出是所走査的"個頂點中的最後一個頂點的相應的所分配的標籤。
10. 如權利要求9所述的方法，其特徵在於，確定所述熵次數還包括使用一提取器函數來確定與所述輸入消息相關聯的隨機性程度。
11. 一種包括可由處理器執行的計算機編程的指令的計算機可讀介質，所 述指令用於將消息劃分成段；根據對一散列函數的輸入走查一擴展圖，所述擴展圖是使用所述各段中的 相應段確定到所述擴展圖中的W個頂點中的下一頂點的路徑來走查的； 確定所走查的最後一個頂點的標籤；以及 輸出所述標籤作為所述散列函數的結果。
12. 如權利要求11所述的計算機可讀介質，其特徵在於，所述擴展圖是 Ramanujan圖或Lubotzky-Phillips誦Sarnak擴展圖。
13. 如權利要求11所述的計算機可讀介質，其特徵在於，所述結果是密 碼散列。
14. 如權利要求11所述的計算機可讀介質，其特徵在於，找出所述散列 函數的衝突在計算上是困難的。
15. 如權利要求11所述的計算機可讀介質，其特徵在於，所述消息基於 從所述消息中提取的熵次數被劃分成所述段。
16. 如權利要求11所述的計算機可讀介質，其特徵在於，所述擴展圖包 括w個頂點，其中所述消息具有一熵次數，並且其中，所述電腦程式指令還 包括用於執行以下動作的結構向所述圖的各頂點分配相應的標籤； 確定所述熵次數；其中，走査還包括使用所述熵次數來走查所述《個頂點以標識完全隨機的 頂點輸出；並且所述輸出是所走査的"個頂點中的最後一個頂點的相應的所分配的標籤。
17. 如權利要求11所述的計算機可讀介質，其特徵在於，所述用於確定 熵次數的計算機編程的指令還包括用於使用一提取器函數來確定與所述消息 相關聯的隨機性程度的指令。
18. —種計算設備，包括 處理器；以及耦合到所述處理器的存儲器，所述存儲器包括可由所述處理器執行的計算 機程序指令，所述指令用於向一擴展圖中的W個頂點中的相應頂點分配相應的標籤； 確定輸入消息的隨機性；走査作為對一散列函數的輸入的所述擴展圖，所述擴展圖中的頂點是 基於所述隨機性來訪問的；確定所走査的頂點中的最後一個頂點的標籤；以及 輸出所述標籤作為所述散列函數的結果。
19. 如權利要求18所述的計算設備，其特徵在於，所述擴展圖是Ramanujan 圖或Lubotzky-Phillips-Sarnak擴展圖。
20. 如權利要求18所述的計算設備，其特徵在於，所述結果是密碼散列。
全文摘要
描述了從擴展圖構造散列函數。在一方面，走查一擴展圖以計算散列函數。該擴展圖是使用輸入消息的相應子集來走查的。所走查的最後一個頂點的標籤是該散列函數的輸出。
文檔編號G06F17/00GK101300569SQ200680040456
公開日2008年11月5日 申請日期2006年10月16日 優先權日2005年11月1日
發明者D·X·查爾斯, E·Z·戈倫, K·E·勞特 申請人:微軟公司