信息處理設備、密鑰生成設備、籤名驗證設備、信息處理方法、籤名生成方法和程序的製作方法

2023-06-01 07:05:21

專利名稱：信息處理設備、密鑰生成設備、籤名驗證設備、信息處理方法、籤名生成方法和程序的製作方法
技術領域：
本發明涉及信息處理裝置、密鑰生成裝置、籤名驗證裝置、信息處理方法、籤名生成方法和程序。
背景技術：
隨著信息處理技術和通信技術的飛速發展，文檔(不管是官方文檔還是私人文 檔)正被快速地轉換成電子形式。因此，許多個人和企業顯示出對電子文檔的安全控制的極大興趣。隨著這種越來越大的興趣，針對諸如對電子文檔的竊聽(wiretapping)和偽造之類的篡改的安全在各種地區被更加積極並越來越多地討論。例如，可以通過對電子文檔進行加密來確保針對電子文檔的竊聽的安全。例如，可以通過利用電子籤名來確保從對電子文檔的偽造的安全。但是，加密和電子籤名必須具有對篡改的足夠抵抗力。電子籤名被用來識別電子文檔的作者。因此，電子籤名應當僅能由作者創建。如果惡意第三方能夠創建相同的電子籤名，則第三方可偽裝成電子文檔的作者。即，電子文檔被惡意第三方偽造。為了防止這種偽造，已經以多種方式討論了電子籤名的安全。當前被廣泛使用的電子籤名方法例如包括利用RSA籤名方法或DSA籤名方法的方法。RSA籤名方法將安全基於「難於將大的合數因式分解成素分量(以下，稱為因式分解成素分量的問題)」。DSA籤名方法將安全基於「難於解決離散對數問題」。這些基礎可歸因於如下事實不存在通過利用經典計算機來有效解決因式分解成素分量的問題或離散對數問題的算法。即，以上的困難意味著經典計算機的計算困難。此處的經典計算機意味著不是所謂的量子計算機的計算機。量子計算機被稱為能夠有效地計算因式分解成素分量的問題或離散對數問題的答案。因此，注意力集中於具有不同於RSA籤名方法或DSA籤名方法的基礎的安全基礎的算法或協議。其一個主要的候選是多變量公鑰密碼(MPKC)籤名方法，其將安全基於「難於解決多變量多項式(以下，稱為多變量多項式問題)」。據稱，不存在通過量子計算機來有效求解多變量多項式問題的算法。當與RSA籤名方法或DSA籤名方法相比時，MPKC籤名方法用以確保相同水平的安全所保持的信息量更小。因此，MPKC籤名方法還適於具有更少操作能力或存儲容量的設備的使用。作為MPKC籤名方法，例如，廣泛已知基於MI(松本今井密碼(Matsumoto-Imaicryptography))、HFE (隱藏場方程密碼；例如參見非專利文獻I)、OV (油醋籤名機制(Oil-Vinegar signature scheme))和 TTM(馴服改造方法密碼(Tamed TransformationMethod cryptography))的方法。作為HFE籤名方法的導出形式，已知HFE籤名方法和OV籤名方法的組合(以下，稱為HFEv籤名方法)以及HFE籤名方法和PFDH(全域概率哈希(Probabilistic Full Domain Hash))籤名方法的組合(以下，稱為HFE+PFDH方法；例如參見非專利文獻2)。引用列表
非專利文獻 I :Jacques Patarin Asymmetric Cryptography with a HiddenMonomial, CRYPTO 1996，第 45 頁至第 60 頁。非專利文獻2 Patarin> J.、Courtois> N.和 Goubin> L. QUARTZ, 128-Bit LongDigital Signatures。出現在CT-RSA 2001 (美國加州舊金山，2001年4月)關於密碼學的話題，Naccache、D.、Ed, Springer-Verlag計算機科學的講義,第2020卷,第282頁至第297 頁

發明內容
技術問題如上所述，諸如HFE籤名方法和OV籤名方法之類的MPKC籤名方法具有優越的特點，諸如，通過利用量子計算機能對抗篡改行為，並且，與RSA籤名方法相比，具有更少的操作負荷和存儲使用。但是，在諸如HFE籤名方法和OV籤名方法之類的MPKC籤名方法中所使用的帶有陷門(trapdoor)的單向函數f不是雙射的(bi jective)。因此,MPKC籤名方法不確保針對選定消息攻擊(chosen-message attacks) (CMA)的安全。選定消息攻擊是在一種環境中試圖偽造電子籤名的行為，其中，除了諸如驗證密鑰之類的公共信息以外，攻擊者可自由地獲取對任意電子文檔的電子籤名。鑑於上述，做出了本發明，並且，希望提供能夠實現對應於MPKC籤名方法中所使用的帶有陷門的單向函數的映射雙射或接近映射雙射的屬性的新穎並改善的信息處理裝置、密鑰生成裝置、籤名驗證裝置、信息處理方法、籤名生成方法和程序。問題的解決方案根據為了達到上述目標的本發明的第一方面，提供了一種信息處理裝置，包括第一逆變換單元，該第一逆變換單元通過第一秘密多項式T的逆變換T—1將包括由η個數所組成的元素的有限環Kn的元素y變換成所述有限環Kn的元素y';元素計算單元，該元素計算單元將通過所述第一逆變換單元所獲得的有限環Kn的元素y'看作有限環K的η次擴展A的元素Y，並且，通過利用所述元素Y來計算由預定多變量多項式所表示的映射f (f A —A)的原像的元素X e {Z e AI f (Z) = Y};元素選擇單元，該元素選擇單元以與所述原像的元素數α成正比的概率P選擇由所述元素計算單元所計算的所述原像的一個元素X，並且，以概率(Ι-p)輸出異常值；以及第二逆變換單元，該第二逆變換單元將由所述元素選擇單元所選擇的所述元素X看作所述有限環Kn的元素X，，並且，通過第二秘密多項式S的逆變換S—1將所述有限環Kn的元素X'變換成所述有限環Kn的元素X。根據為了達到上述目標的本發明的第二方面，提供了一種信息處理裝置，包括部分元素選擇單元，該部分元素選擇單元選擇包括由V個數所組成的元素的有限環Kv的元素νχ ;第一逆變換單元，該第一逆變換單元通過第一秘密多項式T的逆變換Γ1將包括由m個數所組成的元素的有限環Km的元素y變換成所述有限環Km的元素y';元素計算單元，該元素計算單元將通過所述第一逆變換單元所獲得的有限環Km的元素y'看作有限環K的m次擴展A的元素Y，並且，通過利用所述元素Y和由所述部分元素選擇單元所選擇的所述元素νχ來計算由預定多變量多項式所表示的映射f(f =AXKv — B，B是所述有限環K的ο次擴展)的原像的元素Xe {Z e B|f (Ζ,νχ) = Y};元素選擇單元，該元素選擇單元以與所述原像的元素數α成正比的概率P選擇由所述元素計算單元所計算的所述原像的一個元素X，並且，以概率(I-P)輸出異常值；以及第二逆變換單元，該第二逆變換單元將由所述元素選擇單元所選擇的所述元素X看作有限環K。的元素ox，並且，通過第二秘密多項式S的逆變換S—1將所述有限環Kn(n = ο+χ)的元素X』 = (οχ, νχ)變換成所述有限環Kn的元素X。該信息處理裝置還可包括數生成單元,該數生成單元生成數r ;數據生成單元，該數據生成單元通過利用由所述數生成單元所生成的所述數r和電子數據M來生成所述有限環Kn的元素y;以及籤名生成單元，該籤名生成單元將由所述數據生成單元生成的所述有限環Kn的元素y輸入到所述第一逆變換單元，以生成包括通過所述第一逆變換單元、所述元素計算單元、所述元素選擇單元和所述第二逆變換單元的處理所獲得的所述有限環Kn的元素X的電子籤名σ。在該情形中，如果所述元素選擇單元輸出了異常值，則所述籤名生成單元導致所述數生成單元生成不同的數r，並且，基於所述不同的數r，將由所述數據生成單元所生成的所述有限環Kn的元素y輸入到所述第一逆變換單元，以生成包括通過所述第一逆變換單元、所述元素計算單元、所述元素選擇單元和所述第二逆變換單元的處理所 獲得的所述有限環Kn的元素X的電子籤名σ。根據為了達到上述目標的本發明的第三方面，提供了一種密鑰生成裝置，包括秘密密鑰生成單元，該秘密密鑰生成單元生成由計算算法所使用的秘密密鑰，該計算算法具有第一逆變換單元，該第一逆變換單元通過第一秘密多項式T的逆變換Γ1將包括由η個數所組成的元素的有限環Kn的元素y變換成所述有限環Kn的元素y';元素計算單元，該元素計算單元將通過所述第一逆變換單元所獲得的有限環Kn的元素y'看作有限環K的η次擴展A的元素Y，並且，通過利用所述元素Y來計算由預定多變量多項式所表示的映射f (f A —A)的原像的元素X e {Z e AI f (Z) = Y};元素選擇單元，該元素選擇單元以與所述原像的元素數α成正比的概率P選擇由所述元素計算單元所計算的所述原像的一個元素X，並且，以概率(Ι-p)輸出異常值；以及第二逆變換單元，該第二逆變換單元將由所述元素選擇單元所選擇的所述元素X看作有限環Kn的元素X，，並且，通過第二秘密多項式S的逆變換S—1將所述有限環Kn的元素X'變換成所述有限環Kn的元素X，其中，該秘密密鑰包括關於所述第一秘密多項式Τ、所述第二秘密多項式S和所述預定多變量多項式的信息；以及公鑰生成單元，該公鑰生成單元生成公鑰，該公鑰包括關於由所述第一秘密多項式Τ、所述映射f和所述第二秘密多項式S所組成的複合映射F的信息。根據為了達到上述目標的本發明的第四方面，提供了一種密鑰生成裝置，包括部分元素選擇單元，該部分元素選擇單元選擇包括由V個數所組成的元素的有限環Kv的元素νχ ;秘密密鑰生成單元，該秘密密鑰生成單元生成由計算算法所使用的秘密密鑰，該計算算法具有第一逆變換單元，該第一逆變換單元通過第一秘密多項式T的逆變換Γ1將包括由m個數所組成的元素的有限環Km的元素y變換成所述有限環Km的元素y';元素計算單元，該元素計算單元將通過所述第一逆變換單元所獲得的有限環Km的元素y'看作有限環K的m次擴展A的元素Y，並且，通過利用所述元素Y和由所述部分元素選擇單元所選擇的所述元素νχ來計算由預定多變量多項式所表示的映射f(f =AXKv — B，B是所述有限環k的ο次擴展)的原像的元素Xe {Z e B| f (Ζ,νχ) = Y};元素選擇單元，該元素選擇單元以與所述原像的元素數α成正比的概率P選擇由所述元素計算單元所計算的所述原像的一個元素X，並且，以概率(I-P)輸出異常值；以及第二逆變換單元，該第二逆變換單元將由所述元素選擇單元所選擇的所述元素X看作有限環K。的元素οχ，並且，通過第二秘密多項式S的逆變換s—1將所述有限環Kn(n = ο+χ)的元素X，= (οχ, νχ)變換成所述有限環Kn的元素X，其中，該秘密密鑰包括關於所述第一秘密多項式Τ、所述第二秘密多項式S和所述預定多變量多項式的信息；以及公鑰生成單元，該公鑰生成單元生成公鑰，該公鑰包括關於由所述第一秘密多項式Τ、所述映射f和所述第二秘密多項式S所組成的複合映射F的信息。根據為了達到上述目標的本發明的第五方面，提供了一種信息處理裝置，包括部分元素選擇單元，該部分元素選擇單元選擇包括由V個數所組成的元素的有限環Kv的元素νχ ;數生成單元，該數生成單元生成數r ;數據生成單元，該數據生成單元通過利用由所述數生成單元所生成的所述數r和電子數據M來生成所述有限環Kn的元素y ;第一逆變換單元，該第一逆變換單元通過第一秘密多項式T的逆變換Γ1將由所述數據生成單元所生成的有限環Km的元素y變換成所述有限環Km的元素y';元素計算單元，該元素計算單元通過利用由所述第一逆變換單元所獲得的所述有限環Km的元素y'和由所述部分元素選擇單元所選擇的所述元素vx來計算由預定多變量多項式所表示的映射f (f Kn — Κ°, η = ο+ν)的元素οχ e {Z e K°|f(Z, νχ) = y' };元素選擇單元，如果存在所述原像的元素，則該元素 選擇單元選擇由所述元素計算單元所計算的所述原像的所述元素ox，並且，如果不存在所述原像的元素，則該元素選擇單元導致所述數生成單元生成不同的數r，並且，通過利用所述不同的數r，選擇通過所述數據生成單元、所述第一逆變換單元和所述元素計算單元的處理所計算的所述原像的元素ox ;第二逆變換單元，該第二逆變換單元通過第二秘密多項式S的逆變換S4將包括由所述元素選擇單元所選擇的所述元素ox的所述有限環Kn (η = ο+χ)的元素x』 = (οχ, νχ)變換成所述有限環Kn的元素Χ;以及籤名生成單元，該籤名生成單元生成包括通過所述第二逆變換單元所獲得的所述有限環Kn的元素X的電子籤名σ。根據為了達到上述目標的本發明的第六方面，提供了一種信息處理裝置，包括數據生成單元，該數據生成單元通過利用電子數據M來生成包括由m個數所組成的元素的所述有限環Km的元素y ;部分元素選擇單元，該部分元素選擇單元選擇包括由V個數所組成的元素的有限環Kv的元素νχ ;第一逆變換單元，該第一逆變換單元通過第一秘密多項式T的逆變換Γ1將由所述數據生成單元所生成的所述有限環Km的元素y變換成所述有限環Km的元素f ;元素計算單元，該元素計算單元通過使用由所述第一逆變換單元所獲得的所述有限環Km的元素y'和由所述部分元素選擇單元所選擇的所述元素νχ來計算由預定多變量多項式所表示的映射:κη — K°, n = 0+V)的元素οχ e {Ζ e K0I f (Ζ, νχ) = y' };元素選擇單元，如果存在所述原像的元素，則該元素選擇單元選擇由所述元素計算單元所計算的所述原像的所述元素ox，並且，如果不存在所述原像的元素，則該元素選擇單元導致所述部分元素選擇單元選擇不同的數νχ，並且，通過利用所述不同的數νχ，選擇通過所述第一逆變換單元和所述元素計算單元的處理所計算的所述原像的元素οχ ;第二逆變換單元，該第二逆變換單元通過第二秘密多項式S的逆變換S—1將包括由所述元素選擇單元所選的所述元素ox的所述有限環Kn(η = ο+χ)的元素X』= (οχ,νχ)變換成所述有限環Kn的元素χ ;以及籤名生成單元，該籤名生成單元生成包括通過所述第二逆變換單元所獲得的所述有限環Kn的元素χ的電子籤名σ，其中，針對所述有限環K的元素數q，m滿足η彡m+ β條件，並且，β滿足q_@ << I條件。根據為了達到上述目標的本發明的第七方面，提供了一種信息處理裝置，包括數據生成單元，該數據生成單元通過利用電子數據M來生成包括由m個數所組成的元素的所述有限環Km的元素y ;部分元素選擇單元，該部分元素選擇單元選擇包括由V個數所組成的元素的有限環Kv的元素νχ ;第一逆變換單元，該第一逆變換單元通過第一秘密多項式T的逆變換Γ1將由所述數據生成單元所生成的所述有限環Km的元素y變換成所述有限環Km的元素f ;元素計算單元，該元素計算單元通過使用由所述第一逆變換單元所獲得的所述有限環Km的元素y'和由所述部分元素選擇單元所選擇的所述元素νχ來計算由預定多變量多項式所表示的映射:κη — K°, n = 0+V)的元素οχ e {Ζ e K0I f (Ζ, νχ) = y' };元素選擇單元，如果存在所述原像的元素，則該元素選擇單元選擇由所述元素計算單元所計算的所述原像的所述元素ox，並且，如果不存在所述原像的元素，則該元素選擇單元導致所述部分元素選擇單元選擇不同的數νχ，並且，通過利用所述不同的數νχ，選擇通過所述第一逆變換單元和所述元素計算單元的處理所計算的所述原像的元素οχ ;第二逆變換單元，該第二逆變換單元通過第二秘密多項式S的逆變換S—1將包括由所述元素選擇單元所選的所述元素ox的所述有限環Κη(η = ο+χ)的元素χ』 = (οχ, νχ)變換成所述有限環Kn的元素X ;以及籤名生成單元，該籤名生成單元生成包括通過所述第二逆變換單元所獲得的所述有限環Kn的元素X的電子籤名O，其中，針對OX= (OX1,…,OXtj^PvX= (VX1, 'VXv),映射 f 被表示為 Mox1，···, OX0, VX1, ···, VXv) = L(vx1； ...,VxvMox1, ···, ox0)T+g(vx1；…，VXv), L 被表示為 L(vx1; ···, VXv) = L1L2(VX1, ···, vxv)L3,其中，L1 和 L3 是非奇異矩陣,並且，L2是具有將Vx1,…,vxv的函數IijOx1, .",Vxv)作為第i行第j列元素並將I作為對角線分量的上三角矩陣或下三角矩陣。第二秘密多項式S可以是身份映射。根據為了達到上述目標的本發明的第八方面，提供了一種密鑰生成裝置，包括秘密密鑰生成單元，該秘密密鑰生成單元生成由計算算法所使用的秘密密鑰，該計算算法具有部分元素選擇單元和數生成單元，該部分元素選擇單元選擇包括由V個數所組成的元素的有限環Kv的元素vx，該數生成單元生成數r ;數據生成單元，該數據生成單元通過利用由所述數生成單元所生成的數r和電子數據M來生成包括由m個數所組成的元素的有限環Km的元素y ;第一逆變換單元，該第一逆變換單元通過第一秘密多項式T的逆變換T—1將由所述數據生成單元所生成的所述有限環Km的元素y變換成所述有限環Km的元素y';元素計算單元，該元素計算單元通過使用由所述第一逆變換單元所獲得的所述有限環Km的元素I'和由所述部分元素選擇單元所選擇的所述元素vx來計算由預定多變量多項式所表示的映射f(f :Κη —Κ°, η = ο+ν)的元素οχ e {ζ e K01 f (Ζ, νχ) = y' };元素選擇單元,如果存在所述原像的元素，則該元素選擇單元選擇由所述元素計算單元所計算的所述原像的所述元素ox，並且，如果不存在所述原像的元素，則該元素選擇單元導致所述數生成單元選擇不同的數r，並且，通過利用所述不同的數r，選擇通過所述數據生成單元、所述第一逆變換單元和所述元素計算單元的處理所計算的所述原像的元素ox ;第二逆變換單元，該第二逆變換單元通過第二秘密多項式S的逆變換S4將包括由所述元素選擇單元所選的所述元素OX的所述有限環Κη(η = ο+χ)的元素χ』 = (οχ, νχ)變換成所述有限環Kn的元素χ ；以及籤名生成單元，該籤名生成單元生成包括通過所述第二逆變換單元所獲得的所述有限環Kn的元素χ的電子籤名σ，其中，該秘密密鑰包括關於所述第一秘密多項式Τ、所述第二秘密多項式S和所述預定多變量多項式的信息；以及公鑰生成單元，該公鑰生成單元生成公鑰，該公鑰包括關於由所述第一秘密多項式Τ、所述映射f和所述第二秘密多項式S所組成、的複合映射F的信息。根據為了達到上述目標的本發明的第九方面，提供了一種信息驗證裝置，包括獲取單元，該獲取單元從籤名生成裝置獲取關於由第一秘密多項式T、映射f和第二秘密多項式S所組成的複合映射F、電子籤名O和電子數據M的信息，該籤名生成裝置具有部分元素選擇單元和數生成單元，該部分元素選擇單元選擇包括由V個數所組成的元素的有限環Kv的元素vx，該數生成單元生成數r ;第一數據生成單元，該第一數據生成單元通過利用由所述數生成單元所生成的數r和電子數據M來生成包括由m個數所組成的元素的有限環Km的元素y ;第一逆變換單元，該第一逆變換單元通過第一秘密多項式T的逆變換T—1將由所述數據生成單元所生成的所述有限環Km的元素y變換成所述有限環Km的元素y';元素計算單元，該元素計算單元通過使用由所述第一逆變換單元所獲得的所述有限環Km的元素I'和由所述部分元素選擇單元所選擇的所述元素vx來計算由預定多變量多項式所表示的映射f (f :κη — K°,n = 0+V)的元素ox e {z e K0I f (Ζ,νχ) = y' };元素選擇單元,如果存在所述原像的元素，則該元素選擇單元選擇由所述元素計算單元所計算的所述原像的所 述元素ox，並且，如果不存在所述原像的元素，則該元素選擇單元導致所述數生成單元選擇不同的數r，並且，通過利用所述不同的數r，選擇通過所述第一數據生成單元、所述第一逆變換單元和所述元素計算單元的處理所計算的所述原像的元素ox ;第二逆變換單元，該第二逆變換單元通過第二秘密多項式S的逆變換S—1將包括由所述元素選擇單元所選的所述元素ox的所述有限環Κη(η = ο+χ)的元素χ』 = (οχ, νχ)變換成所述有限環Kn的元素χ ；以及籤名生成單元，該籤名生成單元生成包括通過所述第二逆變換單元所獲得的所述有限環Kn的元素χ和由所述數生成單元所生成的數r的電子籤名σ ;第二數據生成單元，該第二數據生成單元通過利用包括在電子籤名σ中的數r和所述電子數據M來生成所述有限環Km的元素yl ;第三數據生成單元，該第三數據生成單元通過將包括在電子籤名σ中的所述有限環Kn的元素χ應用到所述複合映射F來生成所述有限環Km的元素y2 ；以及驗證單元，該驗證單元驗證由所述第二數據生成單元所生成的有限環Km的元素yl是否與由所述第三數據生成單元所生成的有限環Km的元素y2相匹配。根據為了達到上述目標的本發明的第十方面，提供了一種信息處理方法，包括通過第一秘密多項式T的逆變換T—1將包括由η個數所組成的元素的有限環Kn的元素y變換成所述有限環Kn的元素y'的第一逆變換步驟；將通過所述第一逆變換步驟中所獲得的有限環Kn的元素y'看作有限環K的η次擴展A的元素Y並通過利用所述元素Y來計算由預定多變量多項式所表示的映射f(f :Α —Α)的原像的元素Xe {Ze A|f(Z) = Y}的元素計算步驟；以與所述原像的元素數α成正比的概率P選擇在所述元素計算步驟中所計算的所述原像的一個元素X並以概率(I-P)輸出異常值的元素選擇步驟；以及將在所述元素選擇步驟中所選擇的所述元素X看作所述有限環Kn的元素χ'並通過第二秘密多項式S的逆變換S—1將所述有限環Kn的元素χ'變換成所述有限環Kn的元素χ的第二逆變換步驟。根據為了達到上述目標的本發明的第十一方面，提供了一種信息處理方法，包括選擇包括由V個數所組成的元素的有限環Kv的元素νχ的部分元素選擇步驟；通過第一秘密多項式T的逆變換Γ1將包括由m個數所組成的元素的有限環Km的元素y變換成所述有限環Km的元素y'的第一逆變換步驟；將在所述第一逆變換步驟中所獲得的有限環Km的元素I'看作有限環K的m次擴展A的元素Y並通過利用所述元素Y和在所述部分元素選擇步驟中所選擇的所述元素vx來計算由預定多變量多項式所表示的映射f (f =AXKv — B，B是所述有限環K的ο次擴展)的原像的元素Xe {Z e B|f(Z, νχ) = Y}的元素計算步驟；以與所述原像的元素數α成正比的概率P選擇由所述元素計算單元所計算的所述原像的一個元素X並以概率(I-P)輸出異常值的元素選擇步驟；以及將在所述元素選擇步驟中所選擇的所述元素X看作有限環K。的元素οχ並通過第二秘密多項式S的逆變換S—1將所述有限環Γ(η = ο+χ)的元素χ』 = (οχ, νχ)變換成所述有限環Kn的元素χ的第二逆變換步驟。

根據為了達到上述目標的本發明的第十二方面，提供了一種籤名生成方法，包括選擇單元選擇包括由V個數所組成的元素的有限環Kv的元素νχ的部分元素選擇步驟；生成數r的數生成步驟；通過利用在所述數生成步驟中所生成的所述數r和電子數據M來生成包括由m個數所組成的元素的有限環Kn的元素y的數據生成步驟；通過第一秘密多項式T的逆變換Γ1將在所述數據生成步驟中所生成的有限環Km的元素y變換成所述有限環Km的元素y';通過利用在所述第一逆變換步驟中所獲得的所述有限環Km的元素y'和在所述部分元素選擇步驟中所選擇的所述元素vx來計算由預定多變量多項式所表示的映射f (f :Kn — K°, n = 0+V)的元素ox e {z e K01 f (Ζ, νχ) = y' }的元素計算步驟；如果存在所述原像的元素，則元素選擇步驟選擇在所述元素計算步驟中所計算的所述原像的所述元素ox，並且，如果不存在所述原像的元素，則該元素選擇步驟導致所述數生成步驟生成不同的數r，並且，通過利用所述不同的數r，選擇通過所述數據生成步驟、所述第一逆變換步驟和所述元素計算步驟中的處理所計算的所述原像的元素ox ;通過第二秘密多項式S的逆變換S—1將包括在所述元素選擇步驟中所選擇的所述元素ox的所述有限環Κη(η = ο+χ)的元素χ』 = (οχ, νχ)變換成所述有限環Kn的元素χ的第二逆變換步驟；以及生成包括在所述第二逆變換步驟中所獲得的所述有限環Kn的元素χ的電子籤名σ的籤名生成步驟。根據為了達到上述目標的本發明的第十三方面，提供了一種程序，該程序導致計算機執行以下步驟通過第一秘密多項式T的逆變換Γ1將包括由η個數所組成的元素的有限環Kn的元素y變換成所述有限環Kn的元素y'的第一逆變換步驟；將通過所述第一逆變換步驟中所獲得的有限環Kn的元素y'看作有限環K的η次擴展A的元素Y並通過利用所述元素Y來計算由預定多變量多項式所表示的映射f (f :Α — Α)的原像的元素Xe {Z eA|f(Z) =Yj的元素計算步驟；以與所述原像的元素數α成正比的概率P選擇在所述元素計算步驟中所計算的所述原像的一個元素X並以概率(I-P)輸出異常值的元素選擇步驟；以及將在所述元素選擇步驟中所選擇的所述元素X看作所述有限環Kn的元素χ'並通過第二秘密多項式S的逆變換S—1將所述有限環Kn的元素χ'變換成所述有限環Kn的元素χ的第二逆變換步驟。發明的有益效果根據本發明，如上所述，可實現對應於MPKC籤名方法中所使用的帶有陷門的單向函數的映射雙射或接近映射雙射的屬性。結果，針對MPKC籤名方法，可確保來自選定消息攻擊的安全。


圖I是示出了帶有陷門的單向函數的屬性的說明示圖。
圖2是提供了對使用帶有陷門的單向函數的FDH籤名方法的概述的說明示圖。圖3是示出了 RSA函數的屬性的說明示圖。圖4是提供了對基於RS函數的FDH籤名方法的概述的說明示圖。圖5是示出了 HFE函數的屬性的說明示圖。圖6是提供了對基於HFE函數的PFDH籤名方法的概述的說明示圖。圖7是示出了 HFE函數的屬性的說明示圖。圖8是示出了根據本發明的第一實施例的技術所應用的HFE函數(擴展的HFE函數)的屬性的說明示圖。圖9是示出了 OV函數的屬性的說明示圖。圖10是提供了對基於OV函數的FDH籤名方法的概述的說明示圖。圖11是示出了根據本發明的第二實施例的技術所應用的基於OV函數的FDH籤名方法(擴展的OV籤名方法)的屬性的說明示圖。圖12是示出了 HFEv函數的屬性的說明示圖。圖13是提供了對基於HFEv函數的FDH籤名方法的概述並示出了根據本發明的第三實施例的擴展方法的說明示圖。圖14是示例出根據基於HFE函數的PFDH籤名方法的籤名生成算法的說明示圖。圖15是示例出根據基於HFE函數的PFDH籤名方法的籤名驗證算法的說明示圖。圖16是示例出根據基於OV/HFEv函數的FDH籤名方法的籤名生成算法的說明示圖。圖17是示例出根據基於OV/HFEv函數的FDH籤名方法的籤名驗證算法的說明示圖。圖18是示例出根據本發明的第一實施例(擴展的HFE籤名方法)的籤名生成算法的說明示圖。圖19是示例出根據本發明的第一實施例(擴展的HFE籤名方法)的籤名驗證算法的說明示圖。圖20是示例出根據本發明的第三實施例(第一擴展的HFEv籤名方法)的籤名生成算法的說明示圖。圖21是示例出根據本發明的第三實施例(第一擴展的HFEv籤名方法)的籤名驗證算法的說明示圖。 圖22是示例出根據本發明的第二實施例(第一擴展的OV籤名方法)的籤名生成算法的說明示圖。圖23是示例出根據本發明的第二實施例(第一擴展的OV籤名方法)的籤名生成算法的說明示圖。圖24是示例出根據本發明的第三實施例(第二擴展的HFEv籤名方法)的籤名生成算法的說明示圖。圖25是示例出根據本發明的第三實施例(第二擴展的HFEv籤名方法)的籤名驗證算法的說明示圖。圖26是示例出根據本發明的第二實施例(第二擴展的OV籤名方法)的籤名生成算法的說明示圖。
圖27是示例出根據本發明的第二實施例(第二擴展的OV籤名方法)的籤名驗證算法的說明示圖。圖28是示出了能夠實現根據本發明的第一至第三實施例的電子籤名方法的系統的配置示例的說明示圖。圖29是提供了對基於HFE函數的PFDH籤名方法的安全認證的概述的說明示圖。圖30是提供了對基於OV函數的FDH籤名方法的安全認證的概述的說明示圖。圖31是示出了能夠實現根據本發明的第一至第三實施例的電子籤名方法的系統的各種裝置的硬體配置示例的說明示圖。
具體實施方式
以下，將參照附圖來詳細描述本發明的優選實施例。注意，在本說明書和示圖中，用相同的參考標誌來表示具有本質上相同的功能和結構的元件，並且，省去了重複的說明。[描述流程]將簡要談及關於以下所描述的本發明的實施例的描述流程。首先，參照圖I至圖4來簡要描述帶有陷門的單向函數和利用該函數的電子籤名方法。在描述中，RSA函數被引用為帶有陷門的單向函數，並且，描述了其屬性，並且，還簡要描述了利用RSA函數的FDH籤名方法。參照圖28來簡要描述電子籤名系統的系統配置示例。接下來，參照圖5至圖8、圖14、圖15、圖18和圖19來描述根據本發明的第一實施例的帶有陷門的單向函數和利用該函數的電子籤名方法(以下，稱為擴展的HFE籤名方法)。在描述中，描述了一般的HFE函數和利用該HFE函數的電子籤名方法，參照圖29，指出了該電子籤名方法的問題，並且，描述了通過應用根據本發明的第一實施例的技術所獲得的改進效果。接下來，參照圖9至圖11、圖16、圖17、圖22、圖23、圖26和圖27來描述根據本發明的第二實施例的帶有陷門的單向函數和利用該函數的電子籤名方法(以下，稱為擴展的OV籤名方法)。在描述中，描述了一般的OV函數和利用該OV函數的電子籤名方法，參照圖30，指出了該電子籤名方法的問題，並且，描述了通過應用根據本發明的第二實施例的技術所獲得的改進效果。接下來，參照圖12、圖13、圖16、圖17、圖20、圖21、圖24和圖25來描述根據本發明的第三實施例的帶有陷門的單向函數和利用該函數的電子籤名方法(以下，稱為擴展的HFEv籤名方法)。在描述中，描述了組合一般的HFE籤名方法和OV籤名方法的HFEv籤名方法，指出了該電子籤名方法的問題，並且，描述了通過應用根據本發明的第三實施例的技術所獲得的改進效果。接下來，提供了關於根據本發明的第一至第三實施例的電子籤名方法的擴展的補充描述。接下來，簡要描述了包括在能夠實現根據本發明的第一至第三實施例的電子籤名方法的電子籤名系統中的各種裝置的配置示例。最後，總結了本發明的第一至第三實施例的技術想法，並且，簡要描述了從該技術想法所獲得的操作效果。(描述項目)I.介紹1-1.電子籤名系統的配置示例
1-2.帶有陷門的單向函數的屬性1-3.基於帶有陷門的單向函數的電子籤名方法1-4. RSA 籤名方法2.第一實施例(HFE籤名方法的應用示例)2-1. HFE函數的屬性2-2. HFE 籤名方法2-3.擴展的HFE籤名方法3.第二實施例(0V籤名方法的應用示例)3-1. OV函數的屬性3-2. OV籤名方法3-3.第一擴展的OV籤名方法3-4.第二擴展的OV籤名方法4.第三實施例(HFEv籤名方法的應用示例)4-1 · HFEV函數的屬性4-2. HFEv 籤名方法4-3.第一擴展的HFEv籤名方法4-4.第二擴展的HFEv籤名方法5.補充5-1.對PSS籤名方法的擴展5-2.對多層OV籤名方法的擴展5-3. HFE 函數 Ft 的減擴展方法(Minus Extension Method)6.硬體配置示例7.結論〈I.介紹 >首先，在描述本發明的實施例之前，將簡要描述電子籤名系統的系統配置、電子籤名方法中所使用的帶有陷門的單向函數的屬性、以及基於帶有陷門的單向函數的電子籤名方法的示例(FDH籤名方法和RSA籤名方法)。[1-1.電子籤名系統的配置示例]首先，將參照圖28來描述電子籤名系統的系統配置示例。圖28是示出了電子籤名系統的系統配置示例的說明示圖。例如，通過將稍後描述的各種電子籤名方法的操作算法具體地應用於圖28中所示的系統配置，可構造基於操作算法的電子籤名系統。如圖28中所示，電子籤名系統包括籤名方10和驗證方20兩個實體。電子籤名系統的功能通過密鑰生成算法Gen、籤名生成算法Sig和籤名驗證算法Ver三種算法實現。密鑰生成算法Gen和籤名生成算法Sig由籤名方10使用。籤名驗證算法Ver由驗證方20使用。在圖28的示例中，密鑰生成算法Gen由密鑰生成裝置100執行。籤名生成算法Sig由 籤名生成裝置150執行。籤名驗證算法Ver由籤名驗證裝置200執行。系統參數CP被給予籤名方10。系統參數CP例如由電子籤名系統的管理員給予。系統參數cp是基於安全參數1λ生成的。針對系統參數cp的輸入，密鑰生成算法Gen輸出特定於籤名方10的一對籤名密鑰sk和驗證密鑰pk((sk, pk) — Gen(cp))。籤名密鑰sk被保密，並且，被用於由籤名方10生成電子籤名。另一方面，驗證密鑰Pk被發布給驗證方20，並且，被用於由驗證方20進行對電子籤名的驗證。針對從密鑰生成算法Gen輸出的籤名密鑰sk和添加了電子籤名的電子數據(以下，稱為消息)M的輸入，籤名生成算法Sig輸出電子籤名σ(σ —Sig(sk，M))。電子籤名與消息M —起被提供到驗證方20，並且，被用於驗證消息M的真實性。針對由籤名方10所發布的驗證密鑰pk、籤名方10所提供的消息M和電子籤名σ的輸入，籤名驗證算法Ver輸出驗證結果0/1。例如，如果電子籤名σ證實了消息M的真實性((Μ，σ)被接受)，則籤名驗證算法Ver輸出I。另一方面，如果電子籤名σ未證實消息M的真實性((Μ，σ )被拒絕)，則籤名驗證算法Ver輸出O。如上所述，電子籤名系統主要包括密鑰生成算法Gen、籤名生成算法Sig和籤名驗證算法Ver。針對不同的電子籤名方法，這些算法是不同的。本說明書集中於籤名生成算法Sig和籤名驗證算法Ver。
[1-2.帶有陷門的單向函數的屬性]通過使用帶有陷門Ft的單向函數，實現了籤名生成算法Sig和籤名驗證算法Ver的功能。如圖I中所示，帶有陷門Ft的單向函數是這樣一種函數如果陷門未知，則很難從該函數獲得反向操作結果(X = Ff1(Y))。S卩，雖然存在用於(A)Ft的反向計算(Y = Ft(X))的無需陷門而有效計算的計算算法，但是，不存在用於(B)Ft的反向計算的無需陷門而有效計算的計算算法。具有這種屬性的函數Ft被稱為帶有陷門的單向函數。在本說明書中，將使用「前向計算算法」和「反向計算算法」的表達。將描述「前向計算算法」和「反向計算算法」的定義。用於映射f :A — B的「前向計算算法」是這樣一種算法當提供了 χ e A時，計算滿足f (χ) = y的y e B。另一方面，用於映射f :A — B的「反向計算算法」是這樣一種算法當提供了 y e B時,計算滿足fVy) = χ的χ e A。在前向計算算法中，針對輸入χ e A來決定一個輸出值f (χ) = γ。另一方面,在反向計算算法中，針對輸入y e B，可存在多個輸出值X，或可不存在輸出值。因此,反向計算算法的輸出值變為A U {err}，其中，err表示異常值。[1-3.基於帶有陷門的單向函數的電子籤名方法]帶有陷門的單向函數Ft被以圖2中所示的形式應用於籤名生成算法Sig和籤名驗證算法Ver。圖2是提供了對被稱為FDH籤名方法的電子籤名方法的概述的說明示圖。FDH籤名方法的特徵在於哈希值(Hash值)而非消息M被用作用於生成電子籤名的輸入值。通過利用哈希函數(Hash函數)來計算哈希值H。可由任何人來執行對哈希值H的生成處理(C)。在利用帶有陷門的單向函數Ft的電子籤名方法中，驗證密鑰pk是帶有陷門的單向函數Ft。籤名密鑰sk是帶有陷門的單向函數Ft的陷門。因此，帶有陷門的單向函數Ft被發布給驗證方20。另一方面，陷門由籤名方10秘密管理。籤名生成算法Sig是通過利用帶有陷門的單向函數Ft的反向操作(B)來從哈希值H生成電子籤名σ的計算算法。如果陷門未知，則很難執行帶有陷門的單向函數Ft的反向操作(B)。因此，除了籤名方10以外的各方無法生成電子籤名σ。另一方面，籤名驗證算法Ver是通過利用帶有陷門的單向函數Ft的前向操作(A)來驗證消息M的電子籤名σ的真實性的計算算法。無需知曉陷門，就可執行帶有陷門的單向函數Ft的前向計算算法(A)。因此，任何知曉驗證密鑰pk(帶有陷門的單向函數Ft)的人可驗證電子籤名σ。通過使用上述帶有陷門的單向函數Ft，籤名方10肯定可被附接到消息M的電子籤名σ所識別。但是，假定不知道陷門的第三方不能容易地執行對帶有陷門的單向函數Ft的逆運算。如果該假定不成立，則籤名方10可能不一定被電子籤名σ所識別。[1-4. RSA 籤名方法]RSA函數可被引用為電子籤名系統所使用的典型的帶有陷門的單向函數Ft。RSA函數Ft將反向運算的困難基於「難於找到將大的合數因式分解為素分量的計算解答(因式分解為素分量的問題)」。如果P和q(p古q)是素數，N = p*q, e是n_l個彼此互質的整數，d是滿足d*e ^ I (mod η)的整數，並且，Zn是模N的剩餘類環，則RSA函數Ft被表示為以下公式⑴[數學I]
權利要求
1.一種信息處理裝置，包括 第一逆變換單元，該第一逆變換單元通過第一秘密多項式T的逆變換Γ1，將包括由η個數所組成的元素的有限環Kn的元素y變換成所述有限環Kn的元素y'； 元素計算單元，該元素計算單元將通過所述第一逆變換單元所獲得的有限環Kn的元素Y,看作有限環K的η次擴展A的元素Y，並且，通過利用所述元素Y來計算由預定多變量多項式表示的映射f(f A — A)的原像的元素Xe {Z e A|f(Z) = Y}； 元素選擇單元，該元素選擇單元以與所述原像的元素數α成正比的概率P，選擇由所述元素計算單元所計算的所述原像的一個元素X，並且，以概率(I-P)輸出異常值；以及第二逆變換單元，該第二逆變換單元將由所述元素選擇單元所選擇的所述元素X看作所述有限環Kn的元素X，，並且，通過第二秘密多項式S的逆變換S—1，將所述有限環Kn的元素V變換成所述有限環Kn的元素X。
2.一種信息處理裝置，包括 部分元素選擇單元，該部分元素選擇單元選擇包括由V個數所組成的元素的有限環Kv的元素VX ； 第一逆變換單元，該第一逆變換單元通過第一秘密多項式T的逆變換Γ1，將包括由m個數所組成的元素的有限環Km的元素y變換成所述有限環Km的元素y'； 元素計算單元，該元素計算單元將通過所述第一逆變換單元所獲得的有限環Km的元素Y,看作有限環K的m次擴展A的元素Y，並且，通過利用所述元素Y和由所述部分元素選擇單元所選擇的所述元素vx來計算由預定多變量多項式所表示的映射f(f :AXKV —B, B是所述有限環K的ο次擴展)的原像的元素Xe {Z e B | f (Z，vx) = Y}； 元素選擇單元，該元素選擇單元以與所述原像的元素數α成正比的概率P，選擇由所述元素計算單元所計算的所述原像的一個元素X，並且，以概率(I-P)輸出異常值；以及第二逆變換單元，該第二逆變換單元將由所述元素選擇單元所選擇的所述元素X看作有限環K。的元素οχ，並且，通過第二秘密多項式S的逆變換S—1，將所述有限環Kn(n = ο+χ)的元素X』 = (ox, vx)變換成所述有限環Kn的元素X。
3.根據權利要求I所述的信息處理裝置，還包括 數生成單元，該數生成單元生成數r ； 數據生成單元，該數據生成單元通過利用電子數據M和由所述數生成單元所生成的數r來生成所述有限環Kn的元素y ；以及 籤名生成單元，該籤名生成單元將由所述數據生成單元生成的所述有限環Kn的元素y輸入到所述第一逆變換單元，以生成包括通過所述第一逆變換單元、所述元素計算單元、所述元素選擇單元和所述第二逆變換單元的處理所獲得的所述有限環Kn的元素X的電子籤名σ，其中，如果所述元素選擇單元輸出了異常值，則所述籤名生成單元使所述數生成單元生成不同的數r，並且，基於所述不同的數r，將由所述數據生成單元所生成的所述有限環Kn的元素I輸入到所述第一逆變換單元，以生成包括通過所述第一逆變換單元、所述元素計算單元、所述元素選擇單元和所述第二逆變換單元的處理所獲得的所述有限環Kn的元素X的電子籤名σ。
4.根據權利要求2所述的信息處理裝置，還包括 數生成單元，該數生成單元生成數r ；數據生成単元，該數據生成単元通過利用電子數據M和由所述數生成単元所生成的所述數r來生成所述有限環Kn的元素y ；以及 籤名生成単元，該籤名生成單元將由所述數據生成単元生成的所述有限環Kn的元素y輸入到所述第一逆變換單元，以生成包括通過所述第一逆變換單元、所述元素計算單元、所述元素選擇單元和所述第二逆變換單元的處理所獲得的所述有限環Kn的元素X的電子籤名σ，其中，如果所述元素選擇單元輸出了異常值，則所述籤名生成単元使所述數生成単元生成不同的數r，並且，基於所述不同的數r，將由所述數據生成単元所生成的所述有限環Kn的元素I輸入到所述第一逆變換單元，以生成包括通過所述第一逆變換單元、所述元素計算單元、所述元素選擇單元和所述第二逆變換單元的處理所獲得的所述有限環Kn的元素X的電子籤名σ。
5.一種密鑰生成裝置，包括 秘密密鑰生成単元，該秘密密鑰生成単元生成由計算算法所使用的秘密密鑰，該計算算法具有第一逆變換單元，該第一逆變換單元通過第一秘密多項式T的逆變換Γ1將包括由η個數所組成的元素的有限環Kn的元素y變換成所述有限環Kn的元素デ；元素計算單元，該元素計算單元將通過所述第一逆變換單元所獲得的有限環Kn的元素デ看作有限環K的η次擴展A的元素Y，並且，通過利用所述元素Y來計算由預定多變量多項式所表示的映射f (f :A —A)的原像的元素X e {Z e AI f (Z) = Y};元素選擇單元，該元素選擇單元以與所述原像的元素數α成正比的概率ρ，選擇由所述元素計算單元所計算的所述原像的ー個元素X，並且，以概率(Ι-p)輸出異常值；以及第ニ逆變換單元，該第二逆變換單元將由所述元素選擇單元所選擇的所述元素X看作有限環Kn的元素X'，並且，通過第二秘密多項式S的逆變換S—1，將所述有限環Kn的元素X'變換成所述有限環Kn的元素X，其中，所述秘密密鑰包括關於所述第一秘密多項式Τ、所述第二秘密多項式S和所述預定多變量多項式的信息；以及 公鑰生成単元，該公鑰生成単元生成公鑰，該公鑰包括關於由所述第一秘密多項式Τ、所述映射f和所述第二秘密多項式S所組成的複合映射F的信息。
6.一種密鑰生成裝置，包括 部分元素選擇單元，該部分元素選擇單元選擇包括由V個數所組成的元素的有限環Kv的元素VX ; 秘密密鑰生成単元，該秘密密鑰生成単元生成由計算算法所使用的秘密密鑰，該計算算法具有第一逆變換單元，該第一逆變換單元通過第一秘密多項式T的逆變換T—1，將包括由m個數所組成的元素的有限環Km的元素y變換成所述有限環Km的元素デ；元素計算單元，該元素計算單元將通過所述第一逆變換單元所獲得的有限環Km的元素デ看作有限環K的m次擴展A的元素Y，並且，通過利用所述元素Y和由所述部分元素選擇單元所選擇的所述元素Vx來計算由預定多變量多項式表示的映射f (f =AXKv — B，B是所述有限環k的ο次擴展)的原像的元素X e {Z e B|f (Z, vx) = Y};元素選擇單元,該元素選擇單元以與所述原像的元素數α成正比的概率P，選擇由所述元素計算單元所計算的所述原像的ー個元素X，並且，以概率(I-P)輸出異常值；以及第二逆變換單元，該第二逆變換單元將由所述元素選擇單元所選擇的所述元素X看作有限環K。的元素οχ，並且，通過第二秘密多項式S的逆變換S—1，將所述有限環Kn(n = ο+χ)的元素X』 = (ox, vx)變換成所述有限環Kn的元素X，其中，所述秘密密鑰包括關於所述第一秘密多項式T、所述第二秘密多項式S和所述預定多變量多項式的信息；以及 公鑰生成單元，該公鑰生成單元生成公鑰，該公鑰包括關於由所述第一秘密多項式T、所述映射f和所述第二秘密多項式S所組成的複合映射F的信息。
7.一種信息處理裝置，包括 部分元素選擇單元，該部分元素選擇單元選擇包括由V個數所組成的元素的有限環Kv的元素VX ; 數生成單元，該數生成單元生成數r ； 數據生成單元，該數據生成單元通過利用電子數據M和由所述數生成單元所生成的所述數r來生成包括由m個數所組成的元素的所述有限環Km的元素y ； 第一逆變換單元，該第一逆變換單元通過第一秘密多項式T的逆變換Γ1，將由所述數據生成單元所生成的有限環Km的元素y變換成所述有限環Km的元素y'； 元素計算單元，該元素計算單元通過利用由所述第一逆變換單元所獲得的所述有限環Km的元素y'和由所述部分元素選擇單元所選擇的所述元素vx來計算由預定多變量多項式表示的映射 f (f Kn — Κ°, η = ο+ν)的元素 οχ e {Ζ e K。I f(Z, vx) = y' }； 元素選擇單元，如果存在所述原像的元素，則該元素選擇單元選擇由所述元素計算單元所計算的所述原像的所述元素ox，並且，如果不存在所述原像的元素，則該元素選擇單元使所述數生成單元生成不同的數r，並且，通過利用所述不同的數r，選擇通過所述數據生成單元、所述第一逆變換單元和所述元素計算單元的處理所計算的所述原像的元素ox ;以及 第二逆變換單元，該第二逆變換單元通過第二秘密多項式S的逆變換S—1，將包括由所述元素選擇單元所選擇的所述元素ox的所述有限環Kn(n = ο+χ)的元素X』 = (οχ,νχ)變換成所述有限環Kn的元素X ；以及 籤名生成單元，該籤名生成單元生成包括通過所述第二逆變換單元所獲得的所述有限環Kn的元素X的電子籤名σ。
8.一種信息處理裝置，包括 數據生成單元，該數據生成單元通過利用電子數據M來生成包括由m個數所組成的元素的有限環Km的元素y; 部分元素選擇單元，該部分元素選擇單元選擇包括由V個數所組成的元素的有限環Kv的元素VX ; 第一逆變換單元，該第一逆變換單元通過第一秘密多項式T的逆變換Γ1，將由所述數據生成單元所生成的所述有限環Km的元素y變換成所述有限環Km的元素y'； 元素計算單元，該元素計算單元通過使用由所述第一逆變換單元所獲得的所述有限環Km的元素y'和由所述部分元素選擇單元所選擇的所述元素vx來計算由預定多變量多項式表示的映射 f (f κη — Κ°, η = ο+ν)的元素 οχ e {ζ e κ° I f(Z, vx) = y' }； 元素選擇單元，如果存在所述原像的元素，則該元素選擇單元選擇由所述元素計算單元所計算的所述原像的所述元素ox，並且，如果不存在所述原像的元素，則該元素選擇單元導致使所述部分元素選擇單元選擇不同的數vx，並且，通過利用所述不同的數vx，選擇通過所述第一逆變換單元和所述元素計算單元的處理所計算的所述原像的元素ox ；第二逆變換單元，該第二逆變換單元通過第二秘密多項式S的逆變換S—1，將包括由所述元素選擇單元所選的所述元素OX的所述有限環Kn(n = ο+χ)的元素X』 = (οχ,νχ)變換成所述有限環Kn的元素X ；以及 籤名生成単元，該籤名生成単元生成包括通過所述第二逆變換單元所獲得的所述有限環Kn的元素X的電子籤名σ，其中，對於所述有限環K元素數q，m滿足η彡m+β條件，並且，β滿足q_@ << I條件。
9.ー種信息處理裝置，包括 數據生成単元，該數據生成単元通過利用電子數據M來生成包括由m個數所組成的元素的所述有限環Km的元素y; 部分元素選擇單元，該部分元素選擇單元選擇包括由V個數所組成的元素的有限環Kv的元素vx ； 第一逆變換單元，該第一逆變換單元通過第一秘密多項式T的逆變換Γ1，將由所述數據生成単元所生成的所述有限環Km的元素y變換成所述有限環Km的元素デ； 元素計算單元，該元素計算單元通過使用由所述第一逆變換單元所獲得的所述有限環Km的元素デ和由所述部分元素選擇單元所選擇的所述元素vx來計算由預定多變量多項式表示的映射 f (f κη — Κ°, η = ο+ν)的元素 ox e {z e κ° I f(Z, vx) = y' }； 元素選擇單元，如果存在所述原像的元素，則該元素選擇單元選擇由所述元素計算單元所計算的所述原像的所述元素ox，並且，如果不存在所述原像的元素，則該元素選擇單元使所述部分元素選擇單元選擇不同的數vx，並且，通過利用所述不同的數vx，選擇通過所述第一逆變換單元和所述元素計算單元的處理所計算的所述原像的元素ox ； 第二逆變換單元，該第二逆變換單元通過第二秘密多項式S的逆變換S—1，將包括由所述元素選擇單元所選的所述元素ox的所述有限環Κη(η = ο+χ)的元素X』 = (οχ,νχ)變換成所述有限環Kn的元素X ；以及 籤名生成単元，該籤名生成単元生成包括通過所述第二逆變換單元所獲得的所述有限環Kn的元素X的電子籤名O，其中，對於OX= (OX1, ···, OXtj^PvX= (VX1, ·Η,νχν),映射 f 被表示為 Hox1，···, OX0, VX1, ···, VXv) = L(vx1； ...,VXvバOX1, ···, ox0)T+g(vx1；VXv), L 被表示為 L(vx1; ···, VXv) = L1L2(VX1, ···, vxv)L3,其中，L1 和 L3 是非奇異矩陣,並且，L2是具有將Vx1,…，vxv的函數IijOx1, """,VXv)作為第i行第j列元素並將I作為對角線分量的上三角矩陣或下三角矩陣。
10.根據權利要求7所述的信息處理裝置，其中，所述第二秘密多項式S是身份映射。
11.根據權利要求8所述的信息處理裝置，其中，所述第二秘密多項式S是身份映射。
12.根據權利要求9所述的信息處理裝置，其中，所述第二秘密多項式S是身份映射。
13.一種密鑰生成裝置，包括 秘密密鑰生成単元，該秘密密鑰生成単元生成由計算算法所使用的秘密密鑰，該計算算法具有部分元素選擇單元和數生成單元，該部分元素選擇單元選擇包括由V個數所組成的元素的有限環Kv的元素vx,該數生成單元生成數r ;數據生成単元,該數據生成單元通過利用電子數據M和由所述數生成単元所生成的數r來生成包括由m個數所組成的元素的有限環Km的元素y ;第一逆變換單元，該第一逆變換單元通過第一秘密多項式T的逆變換Γ1，將由所述數據生成単元所生成的所述有限環Km的元素y變換成所述有限環Km的元素デ；元素計算單元，該元素計算單元通過使用由所述第一逆變換單元所獲得的所述有限環Km的元素V和由所述部分元素選擇單元所選擇的所述元素VX來計算由預定多變量多項式表示的映射f (f :Kn — K0, η = ο+ν)的元素ox e {z e K01 f (Z, vx) = y' };元素選擇單元，如果存在所述原像的元素，則該元素選擇單元選擇由所述元素計算單元所計算的所述原像的所述元素ox，並且，如果不存在所述原像的元素，則該元素選擇單元使所述數生成單元生成不同的數r，並且，通過利用所述不同的數r，選擇通過所述數據生成單元、所述第一逆變換單元和所述元素計算單元的處理所計算的所述原像的元素ox ;第二逆變換單元，該第二逆變換單元通過第二秘密多項式S的逆變換S4,將包括由所述元素選擇單元所選的所述元素OX的所述有限環Κη(η = ο+χ)的元素X』 = (ox, vx)變換成所述有限環Kn的元素x ；以及籤名生成單元，該籤名生成單元生成包括通過所述第二逆變換單元所獲得的所述有限環Kn的元素X的電子籤名σ，其中，所述秘密密鑰包括關於所述第一秘密多項式Τ、所述第二秘密多項式S和所述預定多變量多項式的信息；以及 公鑰生成單元，該公鑰生成單元生成公鑰，該公鑰包括關於由所述第一秘密多項式Τ、所述映射f和所述第二秘密多項式S所組成的複合映射F的信息。
14.一種籤名驗證裝置，包括 獲取單元，該獲取單元從籤名生成裝置獲取關於由第一秘密多項式T、映射f和第二秘密多項式S所組成的複合映射F的信息、電子籤名σ和電子數據M，該籤名生成裝置具有部分元素選擇單元，該部分元素選擇單元選擇包括由V個數所組成的元素的有限環Kv的元素VX ;數生成單元,該數生成單元生成數r ;第一數據生成單元,該第一數據生成單元通過利用所述電子數據M和由所述數生成單元所生成的數r來生成包括由m個數所組成的元素的有限環Km的元素y ;第一逆變換單元，該第一逆變換單元通過第一秘密多項式T的逆變換Γ1，將由所述第一數據生成單元所生成的所述有限環Km的元素y變換成所述有限環Km的元素f ;元素計算單元，該元素計算單元通過使用由所述第一逆變換單元所獲得的所述有限環Km的元素y'和由所述部分元素選擇單元所選擇的所述元素vx來計算由預定多變量多項式表示的映射f (f :Kn — Κ°, η = ο+ν)的元素ox e {Z e K°| f (Z, vx) = y' };元素選擇單元，如果存在所述原像的元素，則該元素選擇單元選擇由所述元素計算單元所計算的所述原像的所述元素ox，並且，如果不存在所述原像的元素，則該元素選擇單元使所述數生成單元選擇不同的數r，並且，通過利用所述不同的數r，選擇通過所述第一數據生成單元、所述第一逆變換單元和所述元素計算單元的處理所計算的所述原像的元素ox ;第二逆變換單元，該第二逆變換單元通過第二秘密多項式S的逆變換S—1，將包括由所述元素選擇單元所選的所述元素ox的所述有限環Κη(η = ο+χ)的元素χ』 = (οχ,νχ)變換成所述有限環Kn的元素χ ；以及籤名生成單元，該籤名生成單元生成包括通過所述第二逆變換單元所獲得 的所述有限環Kn的元素χ和由所述數生成單元所生成的數r的電子籤名σ ; 第二數據生成單元，該第二數據生成單元通過利用包括在所述電子籤名σ中的數r和所述電子數據M來生成所述有限環Km的元素yl ； 第三數據生成單元，該第三數據生成單元通過將包括在所述電子籤名σ中的所述有限環Kn的元素χ應用到所述複合映射F來生成所述有限環Km的元素y2 ；以及 驗證單元，該驗證單元驗證由所述第二數據生成單元所生成的有限環Km的元素yl與由所述第三數據生成單元所生成的有限環Km的元素y2是否匹配。
15.—種信息處理方法,包括 第一逆變換步驟，該步驟通過第一秘密多項式T的逆變換Γ1，將包括由η個數所組成的元素的有限環Kn的元素y變換成所述有限環Kn的元素デ； 元素計算步驟，該步驟將所述第一逆變換步驟中所獲得的有限環Kn的元素デ看作有限環K的η次擴展A的元素Y，並通過利用所述元素Y來計算由預定多變量多項式表示的映射 f(f :A —A)的原像的元素 X e {Z e A|f (Z) = Y}； 元素選擇步驟，該步驟以與所述原像的元素數α成正比的概率P，選擇在所述元素計算步驟中所計算的所述原像的ー個元素X，並以概率(I-P)輸出異常值；以及 第二逆變換步驟，該步驟將在所述元素選擇步驟中所選擇的所述元素X看作所述有限環1^的元素X'，並通過第二秘密多項式S的逆變換S—1，將所述有限環Kn的元素X'變換成所述有限環Kn的元素X。
16.—種信息處理方法,包括 部分元素選擇步驟，該步驟選擇包括由V個數所組成的元素的有限環Kv的元素vx ；第一逆變換步驟，該步驟通過第一秘密多項式T的逆變換Γ1將包括由m個數所組成的元素的有限環Km的元素y變換成所述有限環Km的元素デ； 元素計算步驟，該步驟將在所述第一逆變換步驟中所獲得的有限環Km的元素デ看作有限環K的m次擴展A的元素Y，並通過利用所述元素Y和在所述部分元素選擇步驟中所選擇的所述元素vx來計算由預定多變量多項式表示的映射f (f =AXKv — B，B是所述有限環K的ο次擴展)的原像的元素Xe {Z e B | f (Z，vx) = Y}； 元素選擇步驟，該步驟以與所述原像的元素數α成正比的概率P，選擇所述元素計算步驟所計算的所述原像的ー個元素X，並以概率(I-P)輸出異常值；以及 第二逆變換步驟，該步驟將在所述元素選擇步驟中所選擇的所述元素X看作有限環κ°的元素οχ，並通過第二秘密多項式S的逆變換S—1將所述有限環Kn(η = ο+χ)的元素X』 =(ox, vx)變換成所述有限環Kn的元素X。
17.—種籤名生成方法,包括 部分元素選擇步驟，該步驟選擇包括由V個數所組成的元素的有限環Kv的元素vx ； 數生成步驟，該步驟生成數r; 數據生成步驟，該步驟通過利用電子數據M和在所述數生成步驟中所生成的所述數r來生成包括由m個數所組成的元素的有限環Km的元素y ； 第一逆變換步驟，該步驟通過第一秘密多項式T的逆變換Γ1，將在所述數據生成步驟中所生成的有限環Km的元素y變換成所述有限環Km的元素デ； 元素計算步驟，該步驟通過利用在所述第一逆變換步驟中所獲得的所述有限環Km的元素デ和在所述部分元素選擇步驟中所選擇的所述元素vx來計算由預定多變量多項式所表示的映射 f (f κη — Κ°, η = ο+ν)的元素 ox e {z e κ° I f(Z, vx) = y' }；元素選擇步驟，如果存在所述原像的元素，則元素選擇步驟選擇在所述元素計算步驟中所計算的所述原像的所述元素ox，並且，如果不存在所述原像的元素，則該元素選擇步驟使所述數生成步驟生成不同的數r，並且，通過利用所述不同的數r，選擇通過所述數據生成步驟、所述第一逆變換步驟和所述元素計算步驟中的處理所計算的所述原像的元素ox ；第二逆變換步驟，該步驟通過第二秘密多項式S的逆變換S—1，將包括在所述元素選擇步驟中所選擇的所述元素OX的所述有限環Κη(η = ο+χ)的元素χ』 = (οχ,νχ)變換成所述有限環Kn的元素χ;以及 籤名生成步驟，該步驟生成包括在所述第二逆變換步驟中所獲得的所述有限環Kn的元素X的電子籤名σ。
18.—種程序，該程序使得計算機執行以下步驟 第一逆變換步驟，該步驟通過第一秘密多項式T的逆變換Γ1，將包括由η個數所組成的元素的有限環Kn的元素y變換成所述有限環Kn的元素y'； 元素計算步驟，該步驟將所述第一逆變換步驟中所獲得的有限環Kn的元素y'看作有限環K的η次擴展A的元素Y，並通過利用所述元素Y來計算由預定多變量多項式所表示的映射f(f A — A)的原像的元素Xe {Z e A| f (Z) = Y}； 元素選擇步驟，該步驟以與所述原像的元素數α成正比的概率P，選擇在所述元素計算步驟中所計算的所述原像的一個元素X，並以概率(I-P)輸出異常值；以及 第二逆變換步驟，該步驟將在所述元素選擇步驟中所選擇的所述元素X看作所述有限環1^的元素χ'，並通過第二秘密多項式S的逆變換S—1，將所述有限環Kn的元素χ'變換成所述有限環Kn的元素X。
全文摘要
提供了用於實現能夠進行關於選定消息攻擊的安全認證的MPKC籤名方法的電子籤名系統。一種信息處理裝置，包括第一逆變換單元，該第一逆變換單元通過第一秘密多項式T的逆變換T-1將包括由n個數所組成的元素的有限環Kn的元素y變換成有限環Kn的元素y′；元素計算單元，該元素計算單元將通過第一逆變換單元所獲得的有限環Kn的元素y′看作有限環K的n次擴展A的元素Y，並且，通過利用元素Y來計算由預定多變量多項式所表示的映射fA→A的原像的元素X∈{Z∈A|f(Z)＝Y}；元素選擇單元，該元素選擇單元以與原像的元素數α成正比的概率p選擇原像的一個元素X，並且，以概率(1-p)輸出異常值；以及第二逆變換單元，該第二逆變換單元將此處所選擇的元素X看作有限環Kn的元素x′，並且，通過第二秘密多項式S的逆變換S-1將限環Kn的元素x′變換成限環Kn的元素x。
文檔編號H04L9/32GK102640451SQ201080051409
公開日2012年8月15日 申請日期2010年9月21日 優先權日2009年11月19日
發明者作本紘一, 樋渡玄良, 白井太三 申請人:索尼公司