JPH0946333A

JPH0946333A - 暗号通信法

Info

Publication number: JPH0946333A
Application number: JP8196548A
Authority: JP
Inventors: Jacques Patarin; ジヤツク・パタラン
Original assignee: C P 8 TORANZATSUKU; CP 8 TRANSAC; Bull CP8 SA
Current assignee: C P 8 TORANZATSUKU; CP 8 TRANSAC; Bull CP8 SA
Priority date: 1995-07-27
Filing date: 1996-07-25
Publication date: 1997-02-14
Anticipated expiration: 2016-07-25
Also published as: SG50745A1; NO321409B1; EP0756399A2; KR100259179B1; FR2737370A1; CN1185821C; NO963141D0; AR003051A1; AU6075596A; JP3583555B2; CN1146676A; TW367684B; FR2737370B1; US5790675A; KR970009022A; EP0756399A3; CA2181299A1; IL118857A; IL118857A0; BR9603150A

Abstract

(57)【要約】【課題】検証、暗号化及び解読のための方法を提供す
る。【解決手段】暗号化、サイン、真正性の認証に使用で
きる非対象の新しい暗号通信方法。この方法は、有限環
Ｋにおける値を有する小さな次数の公開多項方程式に基
づくものである。メカニズムは必ずしも全単射ではな
い。秘密キーによって、環Ｋの拡大のなかに値を有する
多項方程式を隠すことができる。これらの方程式の解法
は、秘密キーを手に入れれば、公開キーだけでは行うこ
とができない演算を行うことを可能にする。

Description

【発明の詳細な説明】

【０００１】

【発明の属する技術分野】本発明は、対話者（interloc
uteur ）間のメッセージを処理し、通信の秘密を保護す
るための非対称暗号通信法（procede de communication
cryptographique）に関する。この方法は、非対称にメ
ッセージを暗号化する（chiffrer）、または同じく非対
称にメッセージにサインする（signer）ために利用する
ことができる。この方法は、非対称な認証（authentifi
cation）にも利用できる。

【０００２】周知の第一の方法は１９７７年に考案され
た。この方法は、１９７７年１２月１４日付けで、発明
者Ｒｉｖｅｓｔ、Ｓｈａｍｉｒ、Ａｄｌｅｍａｎによっ
て登録された米国特許４，４０５，８２９号の対象とな
っている。発明者の名をとってＲＳＡと呼ばれているこ
の方法は二種類のキー（cle ）を使用している。第一の
キー（Ｋｐ）はメッセージの暗号化を行い、第二のキー
（Ｋｓ）は解読を行う。世界中で知られているこの方法
は、暗号化キーと解読キーが異なることから、非対称暗
号通信法と呼ばれる暗号方式を基礎にしている。同一の
ネットワークの中で、各メンバー（ｉ）は、一対のキー
を所有している。第一のキー（Ｋｐ_i）は公開され、す
べての人に知られているものであり、第二のキー（Ｋｓ
_i）は秘密で、決して教えてはならないものである。

【０００３】同一ネットワークの二人の対話者（１）と
（２）間の暗号化された通信は以下の要領で行われる。
まず最初に、（１）と（２）は互いの公開キー（Ｋ
ｐ₁、Ｋｐ₂）を知らせ合い、次に（１）が（２）にメ
ッセージ（Ｍ）を送ろうとするとき、このメッセージを
キー（Ｋｐ₂）によって暗号化する。（２）がいったん
受け取ったこのメッセージは、（２）が保持している秘
密キー（Ｋｓ₂）を用いない限り解読することができな
い。

【０００４】暗号化Ｍ’＝ＲＳＡ（Ｍ、Ｋｐ₂）解読Ｍ＝ＲＳＡ（Ｍ’、Ｋｓ₂）（２）が（１）にメッセージを送ろうとするとき、
（１）の公開キー（Ｋｐ₁）を暗号化し、（１）は自分
の秘密キー（Ｋｓ₁）によって解読する。

【０００５】ＲＳＡ法はサインにも使用することができ
る。メッセージは、個人に固有の秘密キーによって暗号
化され、このときサイン（signature ）とよばれる暗号
化されたメッセージが普通の文字のメッセージとともに
転送される。メッセージの受信者は、当該の個人の公開
キーを当局（autorite）に尋ね、サインの解読のために
そのキーを使用する。解読されたテキストが普通の文字
によるメッセージに対応している場合には、サインは本
物である。

【０００６】この暗号通信法にはいくつかの欠点があ
る。たとえば、操作する数がかなり多く（現在のとこ
ろ、５１２ビットが典型的）、その結果数多くの計算が
必要になり、サインするのにかなり長い時間がかかる。
さらに、因数分解（factorisation ）に新しい進展が得
られた場合には、ＲＳＡの安全性が侵される恐れがあ
る。

【０００７】メッセージの非対称の暗号化またはサイン
機能を遂行するために、「リュックサック（sac-a dos
）」をベースにしたアルゴリズムまたはマツモト−イ
マイのアルゴリズムを使用する方法のような他の非対称
暗号通信法も提案されている。しかしながら、これらの
二つの例は、安全性のレベルが不十分であるということ
がわかっている。

【０００８】

【発明が解決しようとする課題】本発明は、これら二つ
の例のいくつかの利点を残しながらも、それらの欠点を
もたない解決策を提案することにある。本発明は、ＲＳ
Ａのように、真正性の検証、暗号化及びサインのために
使用することができる「隠された体のアルゴリズム（Al
gorithme des Corps Caches ）」またはＨＦＥ（Ｈｉｄ
ｄｅｎＦｉｅｌｄＥｑｕａｔｉｏｎｓ）と呼ばれる
新しいアルゴリズムを使用する。さらに、ＲＳＡは主に
数の大きな因数分解の問題に基づいているのに対して、
ＨＦＥアルゴリズムは完全に異なる問題に基づいてい
る。実際には、次数（degre ）の小さい（典型的には次
数が２または３の）多変数方程式の解法に基づいてい
る。マツモト−イマイのアルゴリズムもまたこの特性を
もっているが、すでに指摘したように、安全性のレベル
は不十分であることがわかっており、その結果、暗号通
信法の中で使用するには適していない点に注意する必要
がある。そもそも、本発明の発明者が、マツモト−イマ
イのアルゴリズムが暗号通信法においては信頼性が確か
なものでないことを発見した。

【０００９】ＨＦＥアルゴリズムの確かさに貢献してい
る新しいエレメントとしては、このアルゴリズムが必ず
しも全単射（bijectif）でない点及び非常に一般的な多
項方程式を使用できる点を挙げることができる。

【００１０】本発明の他の利点は、現在知られている最
も短い非対称サインは約２２０または３２０ビットであ
る（ＳＣＨＮＯＲＲのアルゴリズムまたはＤＳＳアルゴ
リズムを用いて得られる。これらのアルゴリズムは、サ
インまたは真正性の検証にのみ使用され、暗号化や解読
には使用できない）のに対して、ＨＦＥアルゴリズムに
対して超短サイン（２００ビット未満）を計算すること
ができる可能性を有する点である。ＲＳＡを使用する場
合には、５１２ビット以上を使用することが望ましい。

【００１１】定義１．Ａ［Ｘ］／ｇ（Ｘ）のあらゆる同型代数構造を環
（anneau）Ａのｎ次数の「拡大（extension ）」と呼
ぶ。ここでＡ［Ｘ］はＡについての不定な多項式の環で
あり、ｇ（Ｘ）は次数ｎの多項式である。

【００１２】とりわけ重要なケースは、Ａが有限体（co
rps fini）Ｆ_qであり、ｇがＦ_qについて次数ｎの既約
多項式となるケースである。一方、Ａ［ｘ］／ｇ（ｘ）
はＦ_qｎと同形の有限体である。

【００１３】２．Ｌ_nのすべての元（element ）ｅが唯
一、

【００１４】

【数９】

【００１５】の形で表すことができるような、Ｌ_nのｎ
個の元、（ｅ₁、ｅ₂、・・・ｅ_n）の族（famille ）
をＡの次数ｎの拡大Ｌ_nの「基底（base）」と呼ぶ。

【００１６】このために、本発明は、有限環（Ｋ）の
（ｎ）個の元によって表される値（Ｘ）を環（Ｋ）の
（ｎ’）個の元によって表される像値（valeur image）
（Ｙ）に変換する暗号通信法に関するものであり、次の
ような特徴を有する。

【００１７】ａ）像値（Ｙ）の各元（ｎ’）は、値
（Ｘ）の元（ｎ）において、２あるいは２以上（典型的
にはＤ＝２または３）の小さな次数（Ｄ）をもつ公開多
項方程式の形を有する。

【００１８】ｂ）像値（Ｙ）はまた、以下の段階を含む
変換によって（Ｘ）の値から得ることができる。これら
の段階の少なくともいくつかは、暗号の秘密に関する知
識を必要とする。

【００１９】ｂ１）値（Ｘ）に対して、次数１の秘密多
項式（ｓ）の値（Ｘ）の（ｎ）個の元への第一の変換を
適用して、（ｎ）個の元をもつ第一の写像（Ｉ１）を得
る。

【００２０】ｂ２）一つまたは複数の分岐（branche ）
を形成し、各分岐は第一の写像（Ｉ１）の元で構成され
る（たとえば、第一の分岐は、Ｉ１のｎ₁個の第一の元
を含み、第二の分岐は次のｎ₂個の元を含み、以下同様
となるか、あるいは同一の元が複数の分岐の中に存在し
てもよい）。かつ、・少なくとも分岐の一つ（ｅ）（場合によってはすべ
て）の中では、分岐の（ｎ_e）個の元が、Ｗ＊ｋ＝ｎ_e
である環（Ｋ）の次数Ｗの拡大（Ｌ_W）に属するいくつ
か（ｋ）の変数（ｘ、ｘ’、ｘ”、・・・、ｘ^k）また
は一つの変数を示すものとみなされ、少なくともこの分
岐（ｅ）に対して、以下のように定義される変換を適用
する。

【００２１】

【数１０】

【００２２】

【数１１】

【００２３】上式で変換ｆ_eによって（ｘ、ｘ’、
ｘ”、・・・、ｘ^k）の写像を（ｙ、ｙ’、ｙ”、・・
・、ｙ^k）と表し、ｆ_eは以下の二つの特性を検証する
ものである。

【００２４】−ｂ２．１）環（Ｌ_W）の拡大の基底
（Ｂ）において、写像の各成分（ｙ、ｙ’、ｙ”、・・
・、ｙ^k）は、この基底の成分（ｘ、ｘ’、ｘ”、・・
・、ｘ^k）による多項式の形で表される。この多項式は
公開多項方程式の前記の次数（Ｄ）以下の総合次数（de
gre total ）を有する。

【００２５】−ｂ２．２）環（Ｌ_W）の拡大において表
される変換（ｆ_e）は、（ｆ_e）の前項が存在する場合
には一定のエントリ（entree）の数が全エントリ数に対
して無視できる場合を除き、それを計算することができ
るように行われる。（この計算は、ｎ_eが非常に小さい
場合には網羅的調査によって、また有限環の中ではこの
タイプの多項方程式の解法の数学的アルゴリズムを用い
て行われる）。

【００２６】・場合によっては他の分岐に対して、前記
の次数（Ｄ）以下の次数の多項式から環（Ｋ）の値をも
つ成分への変換を適用する。

【００２７】ｂ３）このように変換された分岐または他
の分岐の終わりに、この分岐の直前に位置する分岐の変
数にのみ依存する（Ｄ）以下の次数の多項式（秘密また
は公開）を付け加える（この段階は必ずしも必要なく、
ゼロの多項式を加えることもできる）。

【００２８】ｂ４）このように変換され、次に連結され
た（すなわち再編成された）一つの分岐または複数の分
岐が、第二の写像（Ｉ２）を構成する。

【００２９】ｂ５）第二の写像（Ｉ２）に対して、次数
１をもつ秘密多項式（ｔ）から第二の写像（Ｉ２）の元
への第二の変換を適用して定められた元の数を有する第
三の写像（Ｉ３）を得る。そして、ｂ６）前記の像値
（Ｙ）を形成するために第三の写像（Ｉ３）の元全体の
中から（ｎ’）個の元を選別する（たとえば、最初の
ｌ、あるいはまた、特定の代替案においては、Ｉ３のあ
らゆる元をとる。この場合Ｙ＝Ｉ３）。

【００３０】本発明はまた、以下の通信法を利用する、
非対称サイン法及び非対称真正性検証法に関する。

【００３１】添付の図面を参照して、限定的でない望ま
しいいくつかの実施形態を説明することで本発明の他の
利点及び詳細をみてみる。

【００３２】

【発明の実施の形態】本発明の説明をする前に、まず第
一に、特に有限体の特性に関する数学の基礎を簡単に思
い出してみよう。

【００３３】有限体の説明と特性１）関数ｆ指標（caracteristique ）ｐで基数（cardinal）ｑの有
限体をＫとする（強制ではないが、典型的にはｑ＝ｐ＝
２）。Ｋの次数Ｎの拡大をＬ_Nとし、Ｌ_nの元を
β_i,j、α_i、μ₀またはθ_i,j、φ_i,jとし、整数を
ξ_iとする。以下の写像をｆとすると

【００３４】

【数１２】

【００３５】

【数１３】

【００３６】ここで、

【００３７】

【数１４】

【００３８】および

【００３９】

【数１５】

【００４０】ここで、ｆはｘによる多項式であり、
（＊）は乗法関数である。したがって、Ｑ、Ｐ、Ｓは、
場合によってはこの表記のなかではいくつかの値を表す
こともある。なぜなら、複数のθ_i,j、φ_i,j、ξ_iを
もつことができるからである。

【００４１】さらに、あらゆる整数

【００４２】

【数１６】

【００４３】は、

【００４４】

【数１７】

【００４５】の線形写像（application lineaire）であ
る。したがって、ｆは二次関数である。

【００４６】Ｌ_Nの基底をＢとすると、基底Ｂにおける
ｆの式は次のようになる。

【００４７】ｆ（ｘ₁、．．．、ｘ_N）＝（Ｐ
₁（Ｘ₁、．．．、ｘ_N）、．．．、Ｐ
_N（ｘ₁、．．．、ｘ_N））ここで、Ｐ₁、・・・、Ｐ
_Nは、Ｎ個の変数ｘ₁、・・・、ｘ_Nにおける合計次数
２の多項式である。

【００４８】多項式Ｐ₁、・・・、Ｐ_NはＬ_Nの表現
（representation）を用いて計算される。Ｌ_Nの表現
は、次数ＮのＫについての既約多項式ｉ_N（Ｘ）のデー
タである。このことから、Ｋ［Ｘ］／（ｉ_N（Ｘ））に
おけるＬ_Nを識別することができる。したがって、多項
式Ｐ₁、・・・、Ｐ_Nを計算することは簡単である。

【００４９】２）ｆの反転多項式ｆのｘにおける次数をμとしよう。ｆは、必ずし
も

【００５０】

【数１８】

【００５１】の全単射ではない。

【００５２】１）“ａ”はＬ_Nの元であることから、μ
がそれほど大きすぎない場合には（たとえばμ≦１００
０）、ｆ（ｘ）＝ａのように、Ｌ_Nのｘのあらゆる値
（それらが存在する場合には）を比較的簡単に見つける
ことができるアルゴリズムが知られている。

【００５３】２）さらに、Ｌ_Nのあらゆる“ａ”につい
て、せいぜいｆ（ｘ）＝ａのｘにおける“μ”個の解法
がある。

【００５４】３）場合によっては、ｆは全単写となるこ
ともある。

【００５５】暗号化／解読システムのためのベースとな
るＨＦＥアルゴリズムここで、新しいＨＦＥアルゴリズムの第一のバージョン
（version ）について説明する。このバージョンは、限
定的でなものではなく、次の章ではより一般的なバージ
ョンを紹介する。

【００５６】ｑ＝ｐ^m個の元を含む体Ｋは公開である。
各メッセージはＫのｎ個の元で構成される。たとえば、
ｐ＝２の場合には、各メッセージはｎ＊ｍビットをも
ち、ｎは同じく公開である。ｎはｄ個の整数に分けられ
る。つまりｎ＝ｎ₁＋・・・＋ｎ_dとなる。

【００５７】これらの整数ｎ_e（１＜＝ｅ＜＝ｄ）の各
々について、次数ｎ_eの体Ｋの拡大Ｌｎ_eを結び付ける
（記号＜＝は「未満または等しい」を意味している）。

【００５８】Ｋの成分によって表される値を「ワード
（mot ）」と呼ぼう。たとえば、Ｌｎ_eの元（１＜＝ｅ
＜＝ｄ）は長さｎ_eのワードとして表される。これから
説明する暗号化のメカニズムにおいては、Ｎ＝ｎ₁をｆ
₁、Ｎ＝ｎ₂をｆ₂・・・等々とみなしながら、先に説
明した関数ｆと同類の二次関数ｆ₁、・・・、ｆ_dを使
用する。これらの関数はｄ個のワードを発生する。この
ときこれらのｄ個のワードは長さｎの一つのワードと再
び組み合わされる。

【００５９】・秘密オブジェクトは以下の通りである。

【００６０】１）

【００６１】

【数１９】

【００６２】の全単射の二つのアフィン変換（transfor
mation affiner）ｓとｔ。これらのアフィン全単射は、
Ｋにおける係数及び次数１の多項式による基底のなかに
表すことができる。

【００６３】２）ｎをｄ個の整数に分ける。ｎ＝ｎ₁＋
・・・＋ｎ_d。

【００６４】３）体Ｌｎ₁、・・・、Ｌｎ_dの表現。こ
れらの“表現”は、ｄ個の既約多項式の選択によって与
えられる。１＜＝ｅ＜＝ｄのようなｅとともに、この表
現によって与えられたＬｎ_eに向かうＫⁿｅの同形表現
をΨｎ_eと記す。

【００６５】４）“関数ｆ”と題されたパラグラフに与
えられた関数ｆと同タイプの二次関数ｆ₁、・・・、ｆ
_d（Ｎ＝ｎ_e及び１＜＝ｅ＜＝ｄ）。

【００６６】第一の注記：これらのオブジェクト（obje
t ）はすべて先験的に秘密であるが、実際には上記の
２）、３）、４）の項目のオブジェクトは、公開とする
こともできる。というのもアルゴリズムの安全性は主に
秘密変換（transformation secrete）ｓとｔに基づいて
いるからである。

【００６７】第二の注記：ｓとｔは、全単射写像である
が、また“ほぼ（quasi ）全単射”とすることもでき
る。すなわち、せいぜいほんのわずかな前項しかもたな
い写像となることもある。

【００６８】暗号化のメカニズムは図１に説明されてい
る。演算のシーケンスは、高いところから始まって低い
方へ向かって進行する。まず第一に、

【００６９】

【数２０】

【００７０】の全単射のアフィン変換が行われる。

【００７１】関数μ₁、・・・、μ_dは、

【００７２】

【数２１】

【００７３】（ここでは１＜＝ｅ＜＝ｄ）の射影関数で
あり、μは逆連結関数（fonction deconcatenation inv
erse ）である。関数μ₁、・・・、μ_dは、いわばｄ
個の“分岐”のｎ個の元に分けられる。

【００７４】同型表現Ψｎ_eは、異なる体Ｋ^neから体の
異なる表現Ｌｎ₁、・・・、Ｌｎ_dに向かって応用さ
れ、次に二次関数ｆ₁、・・・、ｆ_dは、Ｌｎ₁、・・
・、Ｌｎ_dのなかのそれぞれＬｎ₁、・・・、Ｌｎ_dに
適用される。次に、逆同形表現（Ψｎ_e）^-1は、体Ｌｎ
₁、・・・、Ｌｎ_dの異なる表現からさまざまな体Ｋⁿ
ｅに向かって応用される。

【００７５】次に、逆連結関数μは、ＫⁿｅからＫⁿに
向かって適用される。最後に、変換ｓと類似している一
般的形態の

【００７６】

【数２２】

【００７７】の全単射アフィン変換ｔが行われる。

【００７８】Ｆ₂は、最も左側のブロックの変数に左右
される多くとも次数（Ｄ）の関数である。より一般的に
は、Ｆ_i（２＜＝ｉ＜＝ｄ）はブロック１、２、・・・
ｉ−１の変数に依存している多くとも次数（Ｄ）の変数
である。

【００７９】注記：これらの関数Ｆ₂、・・・、Ｆ
_dは、ブロックによるＦｅｉｓｔｅｌの図をつくりだ
す。多くの場合、ＨＦＥアルゴリズムのなかにこれらの
関数つまり、Ｆ₂＝・・・＝Ｆ_d＝０を関与させること
はない。

【００８０】重要なことであり注意すべきとして、これ
らすべての演算の構成は、基底のなかの成分を用いてこ
の関数を表す時には二次関数を発生させる。したがっ
て、この関数は、Ｋにおける係数をもつｎ個の多項式
（Ｐ₁、・・・、Ｐ_n）によって与えられることが可能
である。これらの多項式は普通の文字のテキストｘに応
じて暗号化されたテキスト（ｙ）を計算することが可能
である。

【００８１】・公開オブジェクトは、以下の通りであ
る。

【００８２】１）ｑ＝ｐ^m元の体Ｋ及びメッセージの長
さｎ２）Ｋのｎ個の変数によるｎ個の多項式（Ｐ₁、・・
・、Ｐ_n）。このように、誰でもメッセージを暗号化す
ることができる（したがって、暗号化のアルゴリズム
は、本発明の請求の対象となっている特性にしたがって
まさしく公開である）。

【００８３】さらに、秘密オブジェクトが知られている
場合には解読が可能である。というのも、図１に記され
たあらゆる演算を反転させることが可能だからである。
たとえば、関数ｆ_eの反転は、上記の「ｆの反転」と題
されたパラグラフの中のｆについて示されているよう
に、体Ｌｎ_eのなかの未知数における多項式の解法から
なる。しかしながら、ｆ_eは必ずしも全単射でないこと
に注意する必要がある。したがって複数の前項を得るこ
とが可能である。そこで普通の文字によるテキストの選
択は、普通の文字のテキストの中に入れられた冗長度
（redondance）を用いて決定される。解読されたテキス
トは、この冗長度をもつテキストとなる。関数が全単射
でない場合には、この冗長度を普通の文字のメッセージ
に体系的に入れることを考える必要がある。

【００８４】サインによるアルゴリズムの使用例二つのケースが考えられる。

【００８５】・関数が全単射であるケース。

【００８６】Ｈは、サインされるメッセージに適用され
る「ハッシャージュ（hachage ）」関数（英語の“ｈａ
ｓｈ”から）の結果であり（たとえば、Ｈは１２８ビッ
トのフォーマットを有している）、それに対してサイン
ＳはＳ＝ＨＦＥ^-1（Ｈ）である。

【００８７】このように、暗号化関数ＨＦＥが公開であ
ることから、誰でも、Ｈ’＝ＨＦＥ（Ｓ）とし、Ｈ’＝
Ｈであるかどうかを確認することでサインを検証するこ
とができる。サインの発信者はもちろんＳを計算するた
めの秘密を所有しなければならない。

【００８８】・関数が全単射でないケース。

【００８９】この場合、たとえば、ＨＦＥアルゴリズム
によって前項を計算できることをほぼ確かにするために
出力ビットの数より大きいＨＦＥの入力ビット数を選択
することができる。

【００９０】たとえば、Ｈは１２８ビットで表すことが
でき、Ｓは１２８＋２０＝１４８ビットで表すことがで
きる。

【００９１】実施の特殊なケースＨＦＥアルゴリズムを行うための複数の方法には、その
実践と実施に関する重要な利点を示している。

【００９２】・単一分岐によるアルゴリズムのケース
（すなわちｄ＝１とともに）。

【００９３】このバージョンは、唯一の（大きな）分岐
しかもっておらず、したがって、各等式において、あら
ゆる変数、すなわちメッセージのあらゆるビットが関わ
っている。この分岐の規模の大きさを考慮に入れると、
この実施形態は小規模の分岐の弱さをもっていないとい
える。

【００９４】・同一関数ｆをともなう小さい分岐のケー
スこの特殊なケースは、たとえば１２ビットの値をともな
う小さな分岐と同一関数ｆを関与させる。このバージョ
ンは、とりわけ興味深いものである。なぜなら内蔵され
た小型の処理ユニットのなかに、たとえばチップ型カー
ド（cartes a puce ）中で簡単に実施できるからであ
る。実施は、数学的プログラムまたは相互プロセッサ
（co-processeur ）を用いて可能となる。

【００９５】ＨＦＥアルゴリズムの第一の代替案本明細書の中ですでに記したような各分岐において使用
される関数ｆは、有限体のなかに唯一の変数ｘをもつ多
項方程式である。基底の中に表されるこの関数ｆは、合
計次数が２となるような方程式のように表される。

【００９６】事実、あらかじめ定義された一般的モデル
からわずかに逸脱している別のタイプの関数ｆを使用す
ることもできる。この新しいタイプの関数は、ｆとして
有限体の複数の変数たとえば二つの変数ｘ₁とｘ₂に依
存している関数を選択することからなり、その結果、基
底において座標に応じた式は、合計次数が２のままであ
り、前項が存在する場合には、常にｆの定められた値に
よって前項を計算し直すことができるようになる。

【００９７】この変数は、以下の数値例によってよりわ
かりやすくなるであろう。６４ビットの値とｐ＝２とと
もにアルゴリズムの分岐を考えてみよう。この代替案に
よれば、以下のようなｆ（ｘ，ｘ’）＝（ｙ、ｙ’）と
ともに、それぞれ３２ビットの２つの変数ｘとｘ’に依
存しているｆをみてみよう。

【００９８】ｙ＝ｘ⁴＋ｘ＊ｘ’＋ｘ’ （１）ｙ’＝ｘ¹⁷＋ｘ⁴＊ｘ’＋ｘ’³ （２）（とりわけこの厳密な関数を使用することが勧められて
いるわけではない。この厳密な関数はあくまで例として
与えられたものである。）（ｙ、ｙ’）から対（ｘ、ｘ’）を決定するためには、
以下の要領で行うことができる。

【００９９】方程式（１）から、ｘ’＝（ｙ−ｘ⁴）／（ｘ＋１）（３）を求める。

【０１００】この結果方程式（２）からｙ’（ｘ＋１）³＝ｘ¹⁷（ｘ＋１）³＋ｘ⁴（ｙ−
ｘ⁴）（ｘ＋１）²＋（ｙ−ｘ⁴）³ （４）を求める。

【０１０１】ところで、（４）は唯一の変数ｘをもつ多
項方程式である。すでに指摘したように、数学者はすで
に、このタイプの方程式を解くための一般的方法を知っ
ている。したがって、（４）を解くことができ、その結
果方程式を解く値ｘを定義することができる。次に、方
程式（３）のなかでｘをこれらの値に置き換えること
で、ｘ’の値を導き出すことができる。

【０１０２】注記：有限体の中に複数の変数をもつ方程
式について現在知られている解法技術によって、この例
によって示されている方程式とは別のタイプの方程式を
正しく解くことができる。とりわけ、必ずしも他の関数
に応じて一つの変数を表し、それを置き換える必要があ
るわけではない方程式を解くことができる。

【０１０３】ＨＦＥアルゴリズムの第二の代替案必然的に、ＨＦＥアルゴリズムの説明とその代替案は、
本発明の特許請求の範囲を、次数１、次数２をもつ多項
方程式の利用に限定するものではない。次数３を使用す
ることも完全に可能である。このときは、次数３の公開
形態をとる。

【０１０４】同様に、次数４さらに５も考えられる。し
かしながら、その結果生じる公開方程式がコンピュータ
によって簡単に記憶し、計算することができるように、
次数はかなり小さいままである必要がある。

【０１０５】パラメータの選択はまた、最大限の安全性
を保証し、暗号通信への侵入をできるだけ防ぐために重
要である。このように安全性の理由から、以下であるこ
とが望ましい。

【０１０６】１）各分岐には、少なくとも３２ビットの
一つの変数が存在する、できれば少なくとも６２ビット
の変数が存在する。

【０１０７】２）Σγ_ijｘ_iｙ_j＋Σα_iｘ_i＋Σβ_j
ｙ_j＋δ₀＝０の形をとる等式は存在しない。係数
γ_ij、α_i、β_jあるいはσ₀の少なくともいずれか一
つはゼロでなく、ｙ_jが暗号化されたテキストの成分で
ある場合には、またｘ_iが普通の文字によるテキストの
成分である場合には、それらの係数は常に検証される。
注記：上記のマツモト−イマイのアルゴリズムが完全に
安全でないことが明らかになったのは、とりわけこのよ
うな条件を検証できないからである。

【０１０８】３）Σγ_ijkｘ_iｙ_jｙ_k＋Σα_ijｘ_iｙ
_j＋Σβ_ijｙ_jｙ_k＋Σμ_iｘ_i＋Σν_iｙ_i＋δ₀＝
０の形の方程式、すなわち合計次数３で、ｘにおける次
数が１の方程式が存在しない。

【０１０９】４）より一般的には、安全性のために、小
さい多項式による公開方程式の積の線形組合わせを別に
して、普通の文字のメッセージと暗号化されたメッセー
ジの座標の間で常に検証される「小さい」次数の方程式
が存在しないことが望ましい。

【０１１０】ＨＦＥアルゴリズムの第三の代替案関数が全単射でない場合には、ＨＦＥアルゴリズムを使
用するために、普通の文字のテキストの中に冗長度を入
れる可能性を指摘してきた。

【０１１１】他の可能性も存在する。実際に、暗号化さ
れた値の中にＫの新しい元を入れる場合には、普通の文
字の値Ｘの規模より大きな暗号化文字の値Ｙをもつこと
ができるからである。これらの新しい元もまた、Ｘの成
分において次数２の方程式によって与えられる。より一
般的に、図１の表記法を再記することによって、ｓ
（ｘ）の同じ元を複数の分岐の中に転送することができ
る。基底の中に次数２の任意の方程式で構成される一つ
もしくは複数の分岐を付け加えることもできるが、これ
らの追加分岐は、正しい前項を他から区別するのに役立
つ。

【０１１２】ＨＦＥアルゴリズムの第四の代替案図１の最終関数を与えるあらゆる方程式を公開にする代
わりに、その一つもしくは複数の機密を保護することが
できる。すなわち、（Ｐ₁、・・・、Ｐ_n）を公開にす
る代わりに、これらの方程式の一部だけを公開にするこ
とができる。このとき、暗号化は公開の（Ｐ₁、・・
・、Ｐ_n）のみを計算することによって行われる。

【０１１３】解読のためには、非公開のＰ_iに可能なあ
らゆる値を試してみる。このことから先験的に、可能な
複数の解読されたメッセージを与えることができ、正し
いメッセージは、これまでのように、普通の文字のメッ
セージに冗長度を入れることによって、あるいは第三の
代替案のなかで示した方法によって、正しいメッセージ
がマークされる。

【０１１４】注記：このように、一つもしくは複数の公
開方程式をを削除することによって、特定のケースで
は、ＨＦＥアルゴリズムによって隠された体の構造の発
見が一層難しくなる恐れがある。

【０１１５】図２の説明図２は、上述の暗号通信アルゴリズムを使用する暗号化
／解読システムの一例を概略的に示している。

【０１１６】同じ通信ネットワークに属している二人の
個人ＡとＢがおり、各々がメッセージの送信／受信装置
１と２をそれぞれ所有しているとする。この装置には、
メッセージの暗号化と解読を行うために配置された計算
手段、たとえばコンピュータと記憶手段が備えられてい
る。少なくともこれらの計算または記憶手段の一部は、
アクセスが制御されるゾーンの範囲を定めるマイクロケ
ーブル論理回路またはマイクロプロセッサを内蔵したポ
ータブルオブジェクト（objet portatif）の中に置くこ
とができ、その結果、暗号通信キーのような秘密情報を
閉じ込めることができる（たとえば、フランス特許第２
４０１４５９号に記載されたポータブルオブジェクトを
参照のこと）。

【０１１７】各装置には、特に一つのプログラムの形で
先述のようなＨＦＥアルゴリズム及びＨＦＥ^-1逆アルゴ
リズムが組込まれている。

【０１１８】二台の装置は、互いに通信ライン３を用い
てつながっている。

【０１１９】二人の個人ＡとＢはそれぞれ、一対のキー
をもっている。公開キーＣｐ^AとＣｐ^B及び、対応する
公開キーＣｐ^AとＣｐ^Bと相関関係にある秘密キーＣｓ
^AとＣｓ^Bである。ＡとＢが、キーの対を計算する手段
を有していない場合には、ネットワークが非常に正確に
その計算を行うことができ、その結果、ネットワークの
各メンバーに対してある程度の権限（autorite）が与え
られる。これら二人の個人が秘密を保護して互いに対話
しようとする場合、交換されたデータが誰にも理解され
ないようにする場合には、以下の手順を行う。

【０１２０】個人ＡはＢに対して自分の公開キーＣｐ^A
を送り、ＢはＡに対して自分の公開キーＣｐ^Bを送る。
代替案によれば、ネットワークは中央記憶装置にすべて
のメンバーの公開キーを保存しており、メンバーの要求
に対してそれを知らせることができる。Ａがいったん公
開キーＣｐ^Bを受け取ると、ＡはＢに送りたいと考えて
いるメッセージＭを暗号通信アルゴリズムＨＦＥを用い
てメッセージＭ’に暗号化するためにこの公開キーを使
用する。このメッセージは、いったんＢによって受信さ
れると、暗号通信アルゴリズムＨＦＥ^-1と秘密キーＣｓ
^Bを用いて解読される。Ｂだけがこのメッセージを解読
することができる。なぜなら、Ｂはこのキーを所有して
いるネットワークの唯一のメンバーだからである。Ｂか
らＡに向けてメッセージを伝達するための手順もまった
く同じである。

【０１２１】図３の説明図３は、図２のシステムを利用して、先述の暗号通信ア
ルゴリズムを使用する計算及びサインの検証手順を実施
する例を概略的に示している。

【０１２２】ここで、メッセージの伝達は真正性の検証
とともに行われる、すなわち、メッセージＭの受信者
が、そのメッセージは特定の人物から送られたものであ
ることを確信できることが必要である。たとえば、Ａが
Ｂに対して真正性が検証されたメッセージを伝えたいと
しよう。二人の対話者は以下の手順を行うことができ
る。

【０１２３】個人Ａは、まず第一にＢに対して自分の公
開キーＣｐ^Aを送り、Ｂはまたこのキーをネットワーク
に要求する。次に、Ａは自分の秘密キーＣｓ^Aと暗号通
信アルゴリズムＨＦＥ^-1とともにメッセージを暗号化す
る。ここで得られた結果は、メッセージのサインＳと呼
ばれる。さらに、このメッセージ（したがって普通の文
字で通過するメッセージ）とそのサインがＢに送られ
る。Ｂは、暗号通信アルゴリズムＨＦＥと先に受け取っ
た公開キーＣｐ^Aを用いてサインを解読する。Ｍ”と記
される得られた結果は、受信されたメッセージＭに等し
くなければならない。そうである場合には、サインは秘
密キーＣｓ^Aを用いて正しく計算され、その結果、メッ
セージは、ネットワークの中でこのキーを唯一の所有し
ているメンバーであるＡから送られてきたものであるこ
とが証明される。

【０１２４】このシステムのそれ自体よく知られた改良
は、メッセージのサインではなくて、メッセージを濃縮
した（concentre ）サインを計算することからなる。こ
のように、「ハッシャージュ」機能によって、比較的重
要なメッセージはメッセージの特徴的データＨに圧縮さ
れる。この「ハッシャージュ」機能は、従来のハッシャ
ージュ機能（ＭＤ５またはＳＨＡ）を使用して行うこと
ができる。

【０１２５】要約すると、本発明は以下の発見の結果で
ある。

【０１２６】１．発明者は、マツモト−イマイの最初の
アルゴリズムが暗号通信としては信頼性が確かなもので
はないことがわかった（資料Ｃｒｙｐｔｏ’９５、２４
８から２６１ページ参照）。このアルゴリズムは、二つ
のアフィン変換ｓとｔを用いてＱ＝ｑ^θのときｆ
（ｂ）＝ａ^1+Qの形の全単射ｆを「隠す（cacher）」こ
とからなる。

【０１２７】２．発明者は、はるかに一般的な機能をｆ
とみなすことが可能であるとわかった。というのも、発
明者は、非全単射機能ｆを利用することが可能であるこ
とが分かった一方で、たとえば、多項式のＰＧＣＤや多
項式の結果の計算を利用したり、ＧＲＯＢＮＥＲの基底
を利用することによって、多項式の非常に多様な族につ
いて前項を計算できるという事実を利用できることが分
かったからである。

【０１２８】３．少なくとも分岐のいずれか一つがそれ
ほど小さすぎないことが必要である。というのも、発明
者は、小さい分岐は脆弱なＨＦＥアルゴリズムを導くこ
とを発見したからである。

【０１２９】４．さらに発明者は、場合によっては、第
二の秘密の多項式変換によって第二の写像（Ｉ２）の変
換の結果生じた第三の写像（Ｉ３）を構成する元の一部
のみを選別することが可能である点に注目した。

【図面の簡単な説明】

【図１】メッセージを処理するために使用される変換の
連鎖（enchainement）を示す図である。

【図２】メッセージの暗号・解読を行うために使用され
る通信装置を示す図である。

【図３】メッセージのサイン及びその認証を行うために
使用される同一の装置を示す図である。

【符号の説明】

１、２送信／受信装置３通信ライン

【手続補正書】

【提出日】平成８年７月３１日

【手続補正１】

【補正対象書類名】図面

【補正対象項目名】図２

【補正方法】変更

【補正内容】

【図２】

【手続補正２】

【補正対象書類名】図面

【補正対象項目名】図３

【補正方法】変更

【補正内容】

【図３】

───────────────────────────────────────────────────── フロントページの続き (51)Int.Cl.⁶ 識別記号庁内整理番号ＦＩ技術表示箇所Ｈ０４Ｌ 9/32 Ｈ０４Ｌ 9/00 ６７５Ａ C8,C12

Claims

【特許請求の範囲】

【請求項１】有限環（Ｋ）の（ｎ）個の元によって表
される値（Ｘ）を環（Ｋ）の（ｎ’）個の元によって表
される像値（Ｙ）に変換する暗号通信法であって、ａ）像値（Ｙ）の各元（ｎ’）が値（Ｘ）の元（ｎ）に
よる２以上または２の小さな次数（Ｄ）を有する公開多
項方程式の形を有し、ｂ）像値（Ｙ）はまた、ｂ１）値（Ｘ）に対して次数１の秘密多項式（ｓ）の、
値（Ｘ）の（ｎ）個の元への第一の変換を適用して、
（ｎ）個の元をもつ第一の写像（Ｉ１）を得る段階と、ｂ２）変換ｆによる（ｘ、ｘ’、ｘ”、・・・、ｘ^k）
の写像を（ｙ、ｙ’、ｙ”、・・・、ｙ^k）で表し、か
つｆは −ｂ２．１）環の拡大（Ｌ_W）の基底（Ｂ）において、
写像（ｙ、ｙ’、ｙ”、・・・、ｙ^k）の各成分は、こ
の基底における（ｘ、ｘ’、ｘ”、・・・、ｘ^k）の成
分における多項式の形で表されており、この多項式は、
公開多項方程式の前記の次数（Ｄ）以下の総合次数を有
すること、及び −ｂ２．２）環の拡大（Ｌ_W）の中で表される変換
（ｆ）は、場合によっては、入力の合計数に対してその
数がほんのわずかであるような特定の入力についてを除
いて、（ｆ）の前項が存在する場合には、その前項を計
算することができるようなものであるという二つの特性
を検証するものとして、第一の写像（Ｉ１）の（ｎ）個
の元は、Ｗ＊ｋ＝ｎである環（Ｋ）の次数Ｗの拡大（Ｌ
_W）に属する小さな数（ｋ）の変数（ｘ、ｘ’、ｘ”、
・・・、ｘ^k）または一つの変数を表すものとみなされ
るので、【数１】【数２】のように定義される変換を第一の写像（Ｉ１）に適用す
る段階と、ｂ３）このように変換された第一の写像（Ｉ１）が、第
二の写像（Ｉ２）を構成する段階と、ｂ４）第二の写像（Ｉ２）に対して、次数１を有するよ
うな第二の秘密多項式（ｔ）の第二の写像（Ｉ２）の元
への変換を適用して、定められた数の元を有する第三の
写像（Ｉ３）を得る段階と、ｂ５）前記の像値（Ｙ）を形成するために、第三の写像
（Ｉ３）の元全体から（ｎ’）個の元を選別する段階と
の各段階を含む変換によって値（Ｘ）から得ることがで
き、上記段階のうちのいくつかは少なくとも暗号の秘密
に関する知識を必要とすることを特徴とする暗号通信方
法。
【請求項２】公開多項方程式の前記の小さい次数
（Ｄ）が２となるような請求項１に記載の方法。
【請求項３】変数の数ｋが１となるような請求項１に
記載の方法。
【請求項４】公開多項方程式の前記の小さな次数
（Ｄ）が２となり、（Ｋ）は有限体であり、前記の変換
（ｆ）が、【数３】【数４】の形をとり、上式において、ｑは体（Ｋ）の基数であ
り、【数５】および【数６】 β_i,j、α_iおよびμ₀は、Ｌ_Wの元であり、θ_i,j、
φ_i,jおよびξ_iは整数であり、多項式ｆのｘによる次
数は１０００以下である請求項３に記載の方法。
【請求項５】小さい多項式による公開方程式の積の線
形組合せ以外の（ｘ、ｘ’、ｘ”、・・・、ｘ^k）と
（ｙ、ｙ’、ｙ”、・・・、ｙ^k）の成分による合計次
数が小さい多項方程式が存在しないような請求項１に記
載の方法。
【請求項６】係数γ_ij、α_i、β_jまたはδ₀の少な
くとも一つがゼロでなく、Σγ_ijｘ_iｙ_j＋Σα_iｘ_i
＋Σβ_jｙ_j＋δ₀＝０の形の多項方程式が存在せず、
ｙ_jが暗号化されたメッセージの成分であり、ｘ_iが普
通の文字で書かれたメッセージの成分である場合には常
に検証されるような請求項１に記載の方法。
【請求項７】環（Ｋ）が有限体であり環の拡大
（Ｌ_W）が環（Ｋ）の次数Ｗの拡大である、すなわち、
（Ｌ_W）がＫ［Ｘ］／ｇ（Ｘ）の同形であり、ここでｇ
はＫについての次数Ｗの既約多項式であるような請求項
１に記載の方法。
【請求項８】検証者（verifieur ）と呼ばれる第一の
人物によって、証明者（prouveur）とよばれる他の人物
の真正性を検証する非対称の方法であって、検証者は証明者に対して第一の値（Ｙ）を送り、証明者は、検証者に対して、請求項１に記載の方法の対
象となる変換の逆の変換に対応する変換を第一の値
（Ｙ）に応用することによって得られた第二の値（Ｘ）
を送り返し、検証者は、第二の値（Ｘ）に対して、請求項１の変換を
適応し、結果が第一の値（Ｙ）に関連したあらかじめ定
められた関係にしたがっていることを検証することを特
徴とする方法。
【請求項９】有限環（Ｋ）の（ｎ）個の元によって表
される値（Ｘ）を環（Ｋ）の（ｎ’）個の元によって表
される像値（Ｙ）に変換する暗号通信法であって、ａ）像値（Ｙ）の各元（ｎ’）が値（Ｘ）の元（ｎ）に
よる２以上または２の次数（Ｄ）を有する公開多項方程
式の形を有し、ｂ）像値（Ｙ）はまた、ｂ１）値（Ｘ）に対して次数１を有する秘密多項式
（ｓ）の値（Ｘ）の（ｎ）個の元への第一の変換を適応
して、（ｎ）個の元をもつ第一の写像（Ｉ１）を得る段
階と、ｂ２）一つまたは複数の分岐を形成し、各分岐が第一の
写像（Ｉ１）の元によって構成されており、・変換ｆ_eによる（ｘ、ｘ’、ｘ”、・・・、ｘ^k）の
写像を（ｙ、ｙ’、ｙ”、・・・、ｙ^k）で表して、か
つｆ_eは、 −ｂ２．１）環の拡大（Ｌ_W）の基底（Ｂ）において、
写像（ｙ、ｙ’、ｙ”、・・・、ｙ^k）の各成分は、こ
の基底における（ｘ、ｘ’、ｘ”、・・・、ｘ^k）の成
分における多項式の形で表されており、この多項式は、
公開多項方程式の前記の次数（Ｄ）以下の総合次数を有
すること、及び −ｂ２．２）環の拡大（Ｌ_W）の中で表される変換（ｆ
_e）は、場合によっては、入力の合計数に対してその数
がほんのわずかであるような特定の入力についてを除い
て、（ｆ_e）の前項が存在する場合には、その前項を計
算することができるようなものであることという二つの
特性を検証するものとして、少なくとも一つの分岐
（ｅ）においては、分岐の（ｎ_e）個の元が、Ｗ＊ｋ＝
ｎ_eである環（Ｋ）の次数Ｗの拡大（Ｌ_W）に属する小
さな数（ｋ）の変数（ｘ，ｘ’，ｘ”，・・・，ｘ^k）
または一つの変数を表すとみなされ、少なくともこの分
岐に対して【数７】【数８】のように定義された変換を適応し、・さらに、場合によっては他の分岐に対して、前記の次
数（Ｄ）以下の次数の多項式の環（Ｋ）のなかの値をも
つ成分への変換を適応する段階と、ｂ３）このように変換された分岐、またはこのように変
換され連結された複数の分岐が、第二の写像（Ｉ２）を
構成する段階と、ｂ４）第二の写像（Ｉ２）に対して、次数１を有するよ
うな第二の秘密多項式（ｔ）の第二の写像（Ｉ２）の元
への変換を適用して、定められた数の元を有する第三の
写像（Ｉ３）を得る段階と、ｂ５）前記の像値（Ｙ）を形成するために、第三の写像
（Ｉ３）の元全体から（ｎ’）個の元を選別する段階と
の各段階を有する変換によって値（Ｘ）から得ることが
でき、上記の段階のうちのいくつかは少なくとも暗号の
秘密に関する知識を必要とすることを特徴とする方法。
【請求項１０】このように変換された分岐または他の
分岐の出力に、この分岐の直前に位置している分岐の変
数のみに依存する（Ｄ）以下の次数の多項式を付け加え
る請求項９に記載の方法。
【請求項１１】第一の写像（Ｉ１）が複数の分岐を備
えており、分岐のいずれか一つが少なくとも３２ビット
の値を演算する請求項９に記載の方法。
【請求項１２】メッセージ（Ｘ）の非対称サイン及び
このサインの検証方法であって、このサインは、このメ
ッセージまたはメッセージの公開変換に対して、請求項
１または９の方法の対象となる変換の逆の変換に対応す
る変換を応用することによって得られ、さらに、この検
証は、サインするメッセージに関連したあらかじめ定め
られた関係にしたがう結果（Ｙ）を得るように制御する
ことを特徴とする方法。