(57)【特許請求の範囲】
【請求項１】
第１の装置と第２の装置との間の暗号通信方法であって、各装置は計算手段と記憶手段とを含み、通信ラインによって他方の装置に接続されており、第１の装置は、第１の装置の記憶手段に記憶される、有限環（Ｋ）の（ｎ）個の元によって表される値（Ｘ）を有限環（Ｋ）の（ｎ’）個の元によって表される像値（Ｙ）に変換する第１のアルゴリズム手段を含み、該第１のアルゴリズム手段は、
ａ）像値（Ｙ）の各元（ｎ’）が、前記記憶手段において読まれる、値（Ｘ）の元（ｎ）による２以上または２の小さな次数（Ｄ）を有する公開多項方程式を、第１の装置の計算手段によって、値（Ｘ）に適用することによって得ることができ、
ｂ）像値（Ｙ）はまた、
ｂ１）前記記憶手段において読まれる、値（Ｘ）に対して、値（Ｘ）の（ｎ）個の元への次数１の第一の秘密多項式（ｓ）の変換を、前記計算手段によって適用して、前記記憶手段に記憶される、（ｎ）個の元をもつ第一の写像（Ｉ１）を得る段階と、
ｂ２）変換ｆによる（ｘ、ｘ’、ｘ”、・・・、ｘｋ）の写像を（ｙ、ｙ’、ｙ”、・・・、ｙｋ）で表し、かつｆは
−ｂ２．１）環の拡大（Ｌｗ）の基底（Ｂ）において、写像（ｙ、ｙ’、ｙ”、・・・、ｙｋ）の各成分は、前記記憶手段において読まれる、この基底における（ｘ、ｘ’、ｘ”、・・・、ｘｋ）の成分における多項式として計算され、この多項式は、公開多項方程式の前記の次数（Ｄ）以下の総合次数を有すること、及び
−ｂ２．２）環の拡大（ＬＷ）の中で表される変換（ｆ）は、場合によっては、入力の合計数に対してその数がほんのわずかであるような特定の入力についてを除いて、（ｆ）の前項が存在する場合には、その前項を計算することができるようなものであるという二つの特性を検証するものとして、
第一の写像（Ｉ１）の（ｎ）個の元は、Ｗ＊ｋ＝ｎである次数Ｗの環（Ｋ）の拡大（ＬＷ）に属する小さな数（ｋ）の変数（ｘ、ｘ’、ｘ”、・・・、ｘｋ）または一つの変数を表すものとみなされるので、
【数１】
0003583555.tif 000017
【数２】
0003583555.tif 000018
のように定義される変換を、前記計算手段によって、第一の写像（Ｉ１）に適用する段階と、
ｂ３）このように変換された第一の写像（Ｉ１）が、前記記憶手段に記憶される第二の写像（Ｉ２）を構成する段階と、
ｂ４）前記記憶手段において読まれる、第二の写像（Ｉ２）に対して、第二の写像（Ｉ２）の元への、次数１を有するような第二の秘密多項式（ｔ）の変換を前記計算手段によって、適用して、定められた数の元を有し、前記記憶手段に記憶される第三の写像（Ｉ３）を得る段階と、
ｂ５）前記の像値（Ｙ）を形成するために、前記記憶手段において読まれる、第三の写像（Ｉ３）の元全体から（ｎ’）個の元を選別する段階と
の各段階を含む変換によって値（Ｘ）から得ることができ、上記段階のうち少なくともいくつかは暗号の秘密に関する知識を必要とするることを特徴とし、
前記第２の装置が、前記第１のアルゴリズム手段の逆である、第２のアルゴリズム手段を含む暗号通信方法。
【請求項２】
公開多項方程式の前記の小さい次数（Ｄ）が２となるような請求項１に記載の方法。
【請求項３】
変数の数ｋが１となるような請求項１に記載の方法。
【請求項４】
公開多項方程式の前記の小さな次数（Ｄ）が２となり、（Ｋ）は有限体であり、前記の変換（ｆ）が、
【数３】
0003583555.tif 000019
【数４】
0003583555.tif 000020
の形をとり、上式において、ｑは体（Ｋ）の基数であり、
【数５】
0003583555.tif 000021
および
【数６】
0003583555.tif 000022
βｉ，ｊ、αｉおよびμ０は、ＬＷの元であり、θｉ，ｊ、φｉ，ｊおよびξｉは整数であり、多項式ｆのｘによる次数は１０００以下である請求項３に記載の方法。
【請求項５】
小さい多項式による公開方程式の積の線形組合せ以外の（ｘ、ｘ’、ｘ”、・・・、ｘｋ）と（ｙ、ｙ’、ｙ”、・・・、ｙｋ）の成分における合計次数が小さい多項方程式が存在しないような請求項１に記載の方法。
【請求項６】
係数γｉｊ、αｉ、βｊまたはδ０の少なくとも一つがゼロでなく、Σγｉｊｘｉｙｊ＋Σαｉｘｉ＋Σβｊｙｊ＋δ０＝０の形の多項方程式が存在せず、ｙｊが暗号化されたメッセージの成分であり、ｘｉが普通の文字で書かれたメッセージの成分である場合には常に検証されるような請求項１に記載の方法。
【請求項７】
環（Ｋ）が有限体であり環の拡大（ＬＷ）が次数Ｗの環（Ｋ）の拡大である、すなわち、（ＬＷ）がＫ［Ｘ］／ｇ（Ｘ）の同形であり、ここでｇはＫについての次数Ｗの既約多項式であるような請求項１に記載の方法。
【請求項８】
検証者（ｖｅｒｉｆｉｅｕｒ  ）と呼ばれる第一の人物によって、証明者（ｐｒｏｕｖｅｕｒ）とよばれる他の人物の真正性を検証する非対称の方法であって、該検証者は前記第１のアルゴリズム手段を含む請求項１の前記第１の装置を使用し、該証明者は前記第１のアルゴリズム手段の逆である前記第２のアルゴリズム手段を含む請求項１の第２の装置を使用し、
検証者は証明者に対して、第２の装置の記憶手段に記憶される第一の値（Ｙ）を送り、
証明者は、検証者に対して、前記第２のアルゴリズム手段を使用して、第２の装置の記憶手段において読まれる第一の値（Ｙ）を、第２の装置の計算手段によって、変換することによって得られた第二の値（Ｘ）を送り返し、第二の値（Ｘ）は第１の装置の記憶手段に記憶され、
検証者は、前記第１のアルゴリズム手段を使用して、第１の装置の記憶手段において読まれる第二の値（Ｘ）を、第１の装置の計算手段によって、変換し、結果が、第１の装置の記憶手段において読まれる第一の値（Ｙ）に関連したあらかじめ定められた関係にしたがっていることを検証することを特徴とする方法。
【請求項９】
第１の装置と第２の装置との間の暗号通信方法であって、各装置は計算手段と記憶手段とを含み、通信ラインによって他方の装置に接続されており、第１の装置は、第１の装置の記憶手段に記憶される、有限環（Ｋ）の（ｎ）個の元によって表される値（Ｘ）を有限環（Ｋ）の（ｎ’）個の元によって表される像値（Ｙ）に変換する第１のアルゴリズム手段を含み、該第１のアルゴリズム手段は、
ａ）像値（Ｙ）の各元（ｎ’）が、前記記憶手段において読まれる、値（Ｘ）に対して、値（Ｘ）の元（ｎ）による２以上または２の次数（Ｄ）を有する公開多項方程式を、第１の装置の計算手段によって、適用することによって得ることができ、
ｂ）像値（Ｙ）はまた、
ｂ１）前記記憶手段において読まれる、値（Ｘ）に対して、値（Ｘ）の（ｎ）個の元への、次数１を有する第一の秘密多項式（ｓ）の変換を、前記計算手段によって、適用して、前記記憶手段に記憶される、（ｎ）個の元をもつ第一の写像（Ｉ１）を得る段階と、
ｂ２）一つまたは複数の分岐を、前記計算手段によって、形成し、各分岐が、前記記憶手段において読まれる、第一の写像（Ｉ１）の元によって構成されており、
・変換ｆｅによる（ｘ、ｘ’、ｘ”、・・・、ｘｋ）の写像を（ｙ、ｙ’、ｙ”、・・・、ｙｋ）で表して、かつｆｅは、
−ｂ２．１）環の拡大（ＬＷ）の基底（Ｂ）において、写像（ｙ、ｙ’、ｙ”、・・・、ｙｋ）の各成分は、前記記憶手段において読まれる、この基底における（ｘ、ｘ’、ｘ”、・・・、ｘｋ）の成分における多項式として計算され、この多項式は、公開多項方程式の前記の次数（Ｄ）以下の総合次数を有すること、及び
−ｂ２．２）環の拡大（ＬＷ）の中で表される変換（ｆｅ）は、場合によっては、入力の合計数に対してその数がほんのわずかであるような特定の入力についてを除いて、（ｆｅ）の前項が存在する場合には、その前項を計算することができるようなものであることという二つの特性を検証するものとして、
少なくとも一つの分岐（ｅ）においては、分岐の（ｎｅ）個の元が、Ｗ＊ｋ＝ｎｅ  である次数Ｗの環（Ｋ）の拡大（ＬＷ）に属する小さな数（ｋ）の変数（ｘ，ｘ’，ｘ”，・・・，ｘｋ）または一つの変数を表すとみなされ、少なくともこの分岐に対して
【数７】
0003583555.tif 000023
【数８】
0003583555.tif 000024
のように定義された変換を、前記計算手段によって、適用し、
・さらに、場合によっては他の分岐に対して、前記の次数（Ｄ）以下の次数の多項式の、前記記憶手段において読まれる、環（Ｋ）のなかの値をもつ成分への変換を、前記計算手段によって、適用する段階と、
ｂ３）前記計算手段によって、このように変換された分岐、またはこのように変換され連結された複数の分岐が、前記記憶手段に記憶される第二の写像（Ｉ２）を構成する段階と、
ｂ４）前記記憶手段において読まれる、第二の写像（Ｉ２）に対して、次数１を有するような第二の秘密多項式（ｔ）の第二の写像（Ｉ２）の元への変換を、前記計算手段によって、適用して、定められた数の元を有し、前記記憶手段に記憶される第三の写像（Ｉ３）を得る段階と、
ｂ５）前記の像値（Ｙ）を形成するために、前記記憶手段において読まれる、第三の写像（Ｉ３）の元全体から（ｎ’）個の元を選別する段階と
の各段階を有する変換によって値（Ｘ）から得ることができ、上記段階のうち少なくともいくつかは暗号の秘密に関する知識を必要とするることを特徴とし、
前記第２の装置が、前記第１のアルゴリズム手段の逆である、第２のアルゴリズム手段を含む暗号通信方法。
【請求項１０】
このように変換された分岐または他の分岐の出力に、この分岐の直前に位置している分岐の変数のみに依存する（Ｄ）以下の次数の多項式を付け加える請求項９に記載の方法。
【請求項１１】
第一の写像（Ｉ１）が複数の分岐を備えており、分岐のいずれか一つが少なくとも３２ビットの値を演算する請求項９に記載の方法。
【請求項１２】
前記第１のアルゴリズム手段の逆である、第２のアルゴリズム手段を含む請求項１または９の前記第２の装置を使用する、第２の装置の記憶手段に記憶されるメッセージ（Ｘ）の非対称サイン及び第１のアルゴリズム手段を含む請求項１または９の第１の装置を使用する、このサインの検証方法であって、このサインは、前記第２のアルゴリズム手段を使用して、第２の装置の計算手段によって、メッセージの変換またはメッセージの公開変換によって得られ、さらに、この検証は、サインするメッセージに関連したあらかじめ定められた関係にしたがう結果（Ｙ）を得ることを、第１の装置の計算手段によって、確認することを特徴とする方法。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は、対話者（ｉｎｔｅｒｌｏｃｕｔｅｕｒ  ）間のメッセージを処理し、通信の秘密を保護するための非対称暗号通信法（ｐｒｏｃｅｄｅ  ｄｅ  ｃｏｍｍｕｎｉｃａｔｉｏｎ  ｃｒｙｐｔｏｇｒａｐｈｉｑｕｅ）に関する。この方法は、非対称にメッセージを暗号化する（ｃｈｉｆｆｒｅｒ）、または同じく非対称にメッセージにサインする（ｓｉｇｎｅｒ）ために利用することができる。この方法は、非対称な認証（ａｕｔｈｅｎｔｉｆｉｃａｔｉｏｎ）にも利用できる。
【０００２】
周知の第一の方法は１９７７年に考案された。この方法は、１９７７年１２月１４日付けで、発明者Ｒｉｖｅｓｔ、Ｓｈａｍｉｒ、Ａｄｌｅｍａｎによって登録された米国特許４，４０５，８２９号の対象となっている。発明者の名をとってＲＳＡと呼ばれているこの方法は二種類のキー（ｃｌｅ  ）を使用している。第一のキー（Ｋｐ）はメッセージの暗号化を行い、第二のキー（Ｋｓ）は解読を行う。世界中で知られているこの方法は、暗号化キーと解読キーが異なることから、非対称暗号通信法と呼ばれる暗号方式を基礎にしている。同一のネットワークの中で、各メンバー（ｉ）は、一対のキーを所有している。第一のキー（Ｋｐｉ  ）は公開され、すべての人に知られているものであり、第二のキー（Ｋｓｉ  ）は秘密で、決して教えてはならないものである。
【０００３】
同一ネットワークの二人の対話者（１）と（２）間の暗号化された通信は以下の要領で行われる。まず最初に、（１）と（２）は互いの公開キー（Ｋｐ１  、Ｋｐ２  ）を知らせ合い、次に（１）が（２）にメッセージ（Ｍ）を送ろうとするとき、このメッセージをキー（Ｋｐ２  ）によって暗号化する。（２）がいったん受け取ったこのメッセージは、（２）が保持している秘密キー（Ｋｓ２  ）を用いない限り解読することができない。
【０００４】
暗号化  Ｍ’＝ＲＳＡ（Ｍ、Ｋｐ２  ）
解読    Ｍ＝ＲＳＡ（Ｍ’、Ｋｓ２  ）
（２）が（１）にメッセージを送ろうとするとき、（１）の公開キー（Ｋｐ１  ）を暗号化し、（１）は自分の秘密キー（Ｋｓ１  ）によって解読する。
【０００５】
ＲＳＡ法はサインにも使用することができる。メッセージは、個人に固有の秘密キーによって暗号化され、このときサイン（ｓｉｇｎａｔｕｒｅ  ）とよばれる暗号化されたメッセージが普通の文字のメッセージとともに転送される。メッセージの受信者は、当該の個人の公開キーを当局（ａｕｔｏｒｉｔｅ）に尋ね、サインの解読のためにそのキーを使用する。解読されたテキストが普通の文字によるメッセージに対応している場合には、サインは本物である。
【０００６】
この暗号通信法にはいくつかの欠点がある。たとえば、操作する数がかなり多く（現在のところ、５１２ビットが典型的）、その結果数多くの計算が必要になり、サインするのにかなり長い時間がかかる。さらに、因数分解（ｆａｃｔｏｒｉｓａｔｉｏｎ  ）に新しい進展が得られた場合には、ＲＳＡの安全性が侵される恐れがある。
【０００７】
メッセージの非対称の暗号化またはサイン機能を遂行するために、「リュックサック（ｓａｃ−ａ  ｄｏｓ  ）」をベースにしたアルゴリズムまたはマツモト−イマイのアルゴリズムを使用する方法のような他の非対称暗号通信法も提案されている。しかしながら、これらの二つの例は、安全性のレベルが不十分であるということがわかっている。
【０００８】
【発明が解決しようとする課題】
本発明は、これら二つの例のいくつかの利点を残しながらも、それらの欠点をもたない解決策を提案することにある。本発明は、ＲＳＡのように、真正性の検証、暗号化及びサインのために使用することができる「隠された体のアルゴリズム（Ａｌｇｏｒｉｔｈｍｅ  ｄｅｓ  Ｃｏｒｐｓ  Ｃａｃｈｅｓ  ）」またはＨＦＥ（Ｈｉｄｄｅｎ  Ｆｉｅｌｄ  Ｅｑｕａｔｉｏｎｓ）と呼ばれる新しいアルゴリズムを使用する。さらに、ＲＳＡは主に数の大きな因数分解の問題に基づいているのに対して、ＨＦＥアルゴリズムは完全に異なる問題に基づいている。実際には、次数（ｄｅｇｒｅ  ）の小さい（典型的には次数が２または３の）多変数方程式の解法に基づいている。マツモト−イマイのアルゴリズムもまたこの特性をもっているが、すでに指摘したように、安全性のレベルは不十分であることがわかっており、その結果、暗号通信法の中で使用するには適していない点に注意する必要がある。そもそも、本発明の発明者が、マツモト−イマイのアルゴリズムが暗号通信法においては信頼性が確かなものでないことを発見した。
【０００９】
ＨＦＥアルゴリズムの確かさに貢献している新しいエレメントとしては、このアルゴリズムが必ずしも全単射（ｂｉｊｅｃｔｉｆ）でない点及び非常に一般的な多項方程式を使用できる点を挙げることができる。
【００１０】
本発明の他の利点は、現在知られている最も短い非対称サインは約２２０または３２０ビットである（ＳＣＨＮＯＲＲのアルゴリズムまたはＤＳＳアルゴリズムを用いて得られる。これらのアルゴリズムは、サインまたは真正性の検証にのみ使用され、暗号化や解読には使用できない）のに対して、ＨＦＥアルゴリズムに対して超短サイン（２００ビット未満）を計算することができる可能性を有する点である。ＲＳＡを使用する場合には、５１２ビット以上を使用することが望ましい。
【００１１】
定義
１．Ａ［Ｘ］／ｇ（Ｘ）のあらゆる同型代数構造を環（ａｎｎｅａｕ）Ａのｎ次数の「拡大（ｅｘｔｅｎｓｉｏｎ  ）」と呼ぶ。ここでＡ［Ｘ］はＡについての不定な多項式の環であり、ｇ（Ｘ）は次数ｎの多項式である。
【００１２】
とりわけ重要なケースは、Ａが有限体（ｃｏｒｐｓ  ｆｉｎｉ）Ｆｑ  であり、ｇがＦｑ  について次数ｎの既約多項式となるケースである。一方、Ａ［ｘ］／ｇ（ｘ）はＦｑ  ｎと同形の有限体である。
【００１３】
２．Ｌｎ  のすべての元（ｅｌｅｍｅｎｔ  ）ｅが唯一、
【００１４】
【数９】
0003583555.tif 000002
【００１５】
の形で表すことができるような、Ｌｎ  のｎ個の元、（ｅ１  、ｅ２  、・・・ｅｎ  ）の族（ｆａｍｉｌｌｅ  ）をＡの次数ｎの拡大Ｌｎ  の「基底（ｂａｓｅ）」と呼ぶ。
【００１６】
このために、本発明は、有限環（Ｋ）の（ｎ）個の元によって表される値（Ｘ）を環（Ｋ）の（ｎ’）個の元によって表される像値（ｖａｌｅｕｒ  ｉｍａｇｅ）（Ｙ）に変換する暗号通信法に関するものであり、次のような特徴を有する。
【００１７】
ａ）像値（Ｙ）の各元（ｎ’）は、値（Ｘ）の元（ｎ）において、２あるいは２以上（典型的にはＤ＝２または３）の小さな次数（Ｄ）をもつ公開多項方程式の形を有する。
【００１８】
ｂ）像値（Ｙ）はまた、以下の段階を含む変換によって（Ｘ）の値から得ることができる。これらの段階の少なくともいくつかは、暗号の秘密に関する知識を必要とする。
【００１９】
ｂ１）値（Ｘ）に対して、次数１の秘密多項式（ｓ）の値（Ｘ）の（ｎ）個の元への第一の変換を適用して、（ｎ）個の元をもつ第一の写像（Ｉ１）を得る。
【００２０】
ｂ２）一つまたは複数の分岐（ｂｒａｎｃｈｅ  ）を形成し、各分岐は第一の写像（Ｉ１）の元で構成される（たとえば、第一の分岐は、Ｉ１のｎ１  個の第一の元を含み、第二の分岐は次のｎ２  個の元を含み、以下同様となるか、あるいは同一の元が複数の分岐の中に存在してもよい）。かつ、
・少なくとも分岐の一つ（ｅ）（場合によってはすべて）の中では、分岐の（ｎｅ  ）個の元が、Ｗ＊ｋ＝ｎｅ  である環（Ｋ）の次数Ｗの拡大（ＬＷ  ）に属するいくつか（ｋ）の変数（ｘ、ｘ’、ｘ”、・・・、ｘｋ  ）または一つの変数を示すものとみなされ、少なくともこの分岐（ｅ）に対して、以下のように定義される変換を適用する。
【００２１】
【数１０】
0003583555.tif 000003
【００２２】
【数１１】
0003583555.tif 000004
【００２３】
上式で変換ｆｅ  によって（ｘ、ｘ’、ｘ”、・・・、ｘｋ  ）の写像を（ｙ、ｙ’、ｙ”、・・・、ｙｋ  ）と表し、ｆｅ  は以下の二つの特性を検証するものである。
【００２４】
−ｂ２．１）環（ＬＷ  ）の拡大の基底（Ｂ）において、写像の各成分（ｙ、ｙ’、ｙ”、・・・、ｙｋ  ）は、この基底の成分（ｘ、ｘ’、ｘ”、・・・、ｘｋ  ）による多項式の形で表される。この多項式は公開多項方程式の前記の次数（Ｄ）以下の総合次数（ｄｅｇｒｅ  ｔｏｔａｌ  ）を有する。
【００２５】
−ｂ２．２）環（ＬＷ  ）の拡大において表される変換（ｆｅ  ）は、（ｆｅ  ）の前項が存在する場合には一定のエントリ（ｅｎｔｒｅｅ）の数が全エントリ数に対して無視できる場合を除き、それを計算することができるように行われる。（この計算は、ｎｅ  が非常に小さい場合には網羅的調査によって、また有限環の中ではこのタイプの多項方程式の解法の数学的アルゴリズムを用いて行われる）。
【００２６】
・場合によっては他の分岐に対して、前記の次数（Ｄ）以下の次数の多項式から環（Ｋ）の値をもつ成分への変換を適用する。
【００２７】
ｂ３）このように変換された分岐または他の分岐の終わりに、この分岐の直前に位置する分岐の変数にのみ依存する（Ｄ）以下の次数の多項式（秘密または公開）を付け加える（この段階は必ずしも必要なく、ゼロの多項式を加えることもできる）。
【００２８】
ｂ４）このように変換され、次に連結された（すなわち再編成された）一つの分岐または複数の分岐が、第二の写像（Ｉ２）を構成する。
【００２９】
ｂ５）第二の写像（Ｉ２）に対して、次数１をもつ秘密多項式（ｔ）から第二の写像（Ｉ２）の元への第二の変換を適用して定められた元の数を有する第三の写像（Ｉ３）を得る。そして、
ｂ６）前記の像値（Ｙ）を形成するために第三の写像（Ｉ３）の元全体の中から（ｎ’）個の元を選別する（たとえば、最初のｌ、あるいはまた、特定の代替案においては、Ｉ３のあらゆる元をとる。この場合Ｙ＝Ｉ３）。
【００３０】
本発明はまた、以下の通信法を利用する、非対称サイン法及び非対称真正性検証法に関する。
【００３１】
添付の図面を参照して、限定的でない望ましいいくつかの実施形態を説明することで本発明の他の利点及び詳細をみてみる。
【００３２】
【発明の実施の形態】
本発明の説明をする前に、まず第一に、特に有限体の特性に関する数学の基礎を簡単に思い出してみよう。
【００３３】
有限体の説明と特性
１）関数ｆ
指標（ｃａｒａｃｔｅｒｉｓｔｉｑｕｅ  ）ｐで基数（ｃａｒｄｉｎａｌ）ｑの有限体をＫとする（強制ではないが、典型的にはｑ＝ｐ＝２）。Ｋの次数Ｎの拡大をＬＮ  とし、Ｌｎ  の元をβｉ，ｊ  、αｉ  、μ０  またはθｉ，ｊ  、φｉ，ｊ  とし、整数をξｉ  とする。以下の写像をｆとすると
【００３４】
【数１２】
0003583555.tif 000005
【００３５】
【数１３】
0003583555.tif 000006
【００３６】
ここで、
【００３７】
【数１４】
0003583555.tif 000007
【００３８】
および
【００３９】
【数１５】
0003583555.tif 000008
【００４０】
ここで、ｆはｘによる多項式であり、（＊）は乗法関数である。したがって、Ｑ、Ｐ、Ｓは、場合によってはこの表記のなかではいくつかの値を表すこともある。なぜなら、複数のθｉ，ｊ  、φｉ，ｊ  、ξｉ  をもつことができるからである。
【００４１】
さらに、あらゆる整数
【００４２】
【数１６】
0003583555.tif 000009
【００４３】
は、
【００４４】
【数１７】
0003583555.tif 000010
【００４５】
の線形写像（ａｐｐｌｉｃａｔｉｏｎ  ｌｉｎｅａｉｒｅ）である。したがって、ｆは二次関数である。
【００４６】
ＬＮ  の基底をＢとすると、基底Ｂにおけるｆの式は次のようになる。
【００４７】
ｆ（ｘ１  、．．．、ｘＮ  ）＝（Ｐ１  （Ｘ１  、．．．、ｘＮ  ）、．．．、ＰＮ  （ｘ１  、．．．、ｘＮ  ））
ここで、Ｐ１  、・・・、ＰＮ  は、Ｎ個の変数ｘ１  、・・・、ｘＮ  における合計次数２の多項式である。
【００４８】
多項式Ｐ１  、・・・、ＰＮ  はＬＮ  の表現（ｒｅｐｒｅｓｅｎｔａｔｉｏｎ）を用いて計算される。ＬＮ  の表現は、次数ＮのＫについての既約多項式ｉＮ  （Ｘ）のデータである。このことから、Ｋ［Ｘ］／（ｉＮ  （Ｘ））におけるＬＮ  を識別することができる。したがって、多項式Ｐ１  、・・・、ＰＮ  を計算することは簡単である。
【００４９】
２）ｆの反転
多項式ｆのｘにおける次数をμとしよう。ｆは、必ずしも
【００５０】
【数１８】
0003583555.tif 000011
【００５１】
の全単射ではない。
【００５２】
１）“ａ”はＬＮ  の元であることから、μがそれほど大きすぎない場合には（たとえばμ≦１０００）、ｆ（ｘ）＝ａのように、ＬＮ  のｘのあらゆる値（それらが存在する場合には）を比較的簡単に見つけることができるアルゴリズムが知られている。
【００５３】
２）さらに、ＬＮ  のあらゆる“ａ”について、せいぜいｆ（ｘ）＝ａのｘにおける“μ”個の解法がある。
【００５４】
３）場合によっては、ｆは全単写となることもある。
【００５５】
暗号化／解読システムのためのベースとなるＨＦＥアルゴリズム
ここで、新しいＨＦＥアルゴリズムの第一のバージョン（ｖｅｒｓｉｏｎ  ）について説明する。このバージョンは、限定的でなものではなく、次の章ではより一般的なバージョンを紹介する。
【００５６】
ｑ＝ｐｍ  個の元を含む体Ｋは公開である。各メッセージはＫのｎ個の元で構成される。たとえば、ｐ＝２の場合には、各メッセージはｎ＊ｍビットをもち、ｎは同じく公開である。ｎはｄ個の整数に分けられる。つまりｎ＝ｎ１  ＋・・・＋ｎｄ  となる。
【００５７】
これらの整数ｎｅ  （１＜＝ｅ＜＝ｄ）の各々について、次数ｎｅ  の体Ｋの拡大Ｌｎｅ  を結び付ける（記号＜＝は「未満または等しい」を意味している）。
【００５８】
Ｋの成分によって表される値を「ワード（ｍｏｔ  ）」と呼ぼう。たとえば、Ｌｎｅ  の元（１＜＝ｅ＜＝ｄ）は長さｎｅ  のワードとして表される。これから説明する暗号化のメカニズムにおいては、Ｎ＝ｎ１  をｆ１  、Ｎ＝ｎ２  をｆ２  ・・・等々とみなしながら、先に説明した関数ｆと同類の二次関数ｆ１  、・・・、ｆｄ  を使用する。これらの関数はｄ個のワードを発生する。このときこれらのｄ個のワードは長さｎの一つのワードと再び組み合わされる。
【００５９】
・秘密オブジェクトは以下の通りである。
【００６０】
１）
【００６１】
【数１９】
0003583555.tif 000012
【００６２】
の全単射の二つのアフィン変換（ｔｒａｎｓｆｏｒｍａｔｉｏｎ  ａｆｆｉｎｅｒ）ｓとｔ。これらのアフィン全単射は、Ｋにおける係数及び次数１の多項式による基底のなかに表すことができる。
【００６３】
２）ｎをｄ個の整数に分ける。ｎ＝ｎ１  ＋・・・＋ｎｄ  。
【００６４】
３）体Ｌｎ１  、・・・、Ｌｎｄ  の表現。これらの“表現”は、ｄ個の既約多項式の選択によって与えられる。１＜＝ｅ＜＝ｄのようなｅとともに、この表現によって与えられたＬｎｅ  に向かうＫｎ  ｅの同形表現をΨｎｅ  と記す。
【００６５】
４）“関数ｆ”と題されたパラグラフに与えられた関数ｆと同タイプの二次関数ｆ１  、・・・、ｆｄ  （Ｎ＝ｎｅ  及び１＜＝ｅ＜＝ｄ）。
【００６６】
第一の注記：これらのオブジェクト（ｏｂｊｅｔ  ）はすべて先験的に秘密であるが、実際には上記の２）、３）、４）の項目のオブジェクトは、公開とすることもできる。というのもアルゴリズムの安全性は主に秘密変換（ｔｒａｎｓｆｏｒｍａｔｉｏｎ  ｓｅｃｒｅｔｅ）ｓとｔに基づいているからである。
【００６７】
第二の注記：ｓとｔは、全単射写像であるが、また“ほぼ（ｑｕａｓｉ  ）全単射”とすることもできる。すなわち、せいぜいほんのわずかな前項しかもたない写像となることもある。
【００６８】
暗号化のメカニズムは図１に説明されている。演算のシーケンスは、高いところから始まって低い方へ向かって進行する。まず第一に、
【００６９】
【数２０】
0003583555.tif 000013
【００７０】
の全単射のアフィン変換が行われる。
【００７１】
関数μ１  、・・・、μｄ  は、
【００７２】
【数２１】
0003583555.tif 000014
【００７３】
（ここでは１＜＝ｅ＜＝ｄ）の射影関数であり、μは逆連結関数（ｆｏｎｃｔｉｏｎ  ｄｅ  ｃｏｎｃａｔｅｎａｔｉｏｎ  ｉｎｖｅｒｓｅ  ）である。関数μ１  、・・・、μｄ  は、いわばｄ個の“分岐”のｎ個の元に分けられる。
【００７４】
同型表現Ψｎｅ  は、異なる体Ｋｎｅから体の異なる表現Ｌｎ１  、・・・、Ｌｎｄ  に向かって応用され、次に二次関数ｆ１  、・・・、ｆｄ  は、Ｌｎ１  、・・・、Ｌｎｄ  のなかのそれぞれＬｎ１  、・・・、Ｌｎｄ  に適用される。次に、逆同形表現（Ψｎｅ  ）−１は、体Ｌｎ１  、・・・、Ｌｎｄ  の異なる表現からさまざまな体Ｋｎ  ｅに向かって応用される。
【００７５】
次に、逆連結関数μは、Ｋｎ  ｅからＫｎ  に向かって適用される。最後に、変換ｓと類似している一般的形態の
【００７６】
【数２２】
0003583555.tif 000015
【００７７】
の全単射アフィン変換ｔが行われる。
【００７８】
Ｆ２  は、最も左側のブロックの変数に左右される多くとも次数（Ｄ）の関数である。より一般的には、Ｆｉ  （２＜＝ｉ＜＝ｄ）はブロック１、２、・・・ｉ−１の変数に依存している多くとも次数（Ｄ）の変数である。
【００７９】
注記：これらの関数Ｆ２  、・・・、Ｆｄ  は、ブロックによるＦｅｉｓｔｅｌの図をつくりだす。多くの場合、ＨＦＥアルゴリズムのなかにこれらの関数つまり、Ｆ２  ＝・・・＝Ｆｄ  ＝０を関与させることはない。
【００８０】
重要なことであり注意すべきとして、これらすべての演算の構成は、基底のなかの成分を用いてこの関数を表す時には二次関数を発生させる。したがって、この関数は、Ｋにおける係数をもつｎ個の多項式（Ｐ１  、・・・、Ｐｎ  ）によって与えられることが可能である。これらの多項式は普通の文字のテキストｘに応じて暗号化されたテキスト（ｙ）を計算することが可能である。
【００８１】
・公開オブジェクトは、以下の通りである。
【００８２】
１）ｑ＝ｐｍ  元の体Ｋ及びメッセージの長さｎ
２）Ｋのｎ個の変数によるｎ個の多項式（Ｐ１  、・・・、Ｐｎ  ）。このように、誰でもメッセージを暗号化することができる（したがって、暗号化のアルゴリズムは、本発明の請求の対象となっている特性にしたがってまさしく公開である）。
【００８３】
さらに、秘密オブジェクトが知られている場合には解読が可能である。というのも、図１に記されたあらゆる演算を反転させることが可能だからである。たとえば、関数ｆｅ  の反転は、上記の「ｆの反転」と題されたパラグラフの中のｆについて示されているように、体Ｌｎｅ  のなかの未知数における多項式の解法からなる。しかしながら、ｆｅ  は必ずしも全単射でないことに注意する必要がある。したがって複数の前項を得ることが可能である。そこで普通の文字によるテキストの選択は、普通の文字のテキストの中に入れられた冗長度（ｒｅｄｏｎｄａｎｃｅ）を用いて決定される。解読されたテキストは、この冗長度をもつテキストとなる。関数が全単射でない場合には、この冗長度を普通の文字のメッセージに体系的に入れることを考える必要がある。
【００８４】
サインによるアルゴリズムの使用例
二つのケースが考えられる。
【００８５】
・関数が全単射であるケース。
【００８６】
Ｈは、サインされるメッセージに適用される「ハッシャージュ（ｈａｃｈａｇｅ  ）」関数（英語の“ｈａｓｈ”から）の結果であり（たとえば、Ｈは１２８ビットのフォーマットを有している）、それに対してサインＳはＳ＝ＨＦＥ−１（Ｈ）である。
【００８７】
このように、暗号化関数ＨＦＥが公開であることから、誰でも、Ｈ’＝ＨＦＥ（Ｓ）とし、Ｈ’＝Ｈであるかどうかを確認することでサインを検証することができる。サインの発信者はもちろんＳを計算するための秘密を所有しなければならない。
【００８８】
・関数が全単射でないケース。
【００８９】
この場合、たとえば、ＨＦＥアルゴリズムによって前項を計算できることをほぼ確かにするために出力ビットの数より大きいＨＦＥの入力ビット数を選択することができる。
【００９０】
たとえば、Ｈは１２８ビットで表すことができ、Ｓは１２８＋２０＝１４８ビットで表すことができる。
【００９１】
実施の特殊なケース
ＨＦＥアルゴリズムを行うための複数の方法には、その実践と実施に関する重要な利点を示している。
【００９２】
・単一分岐によるアルゴリズムのケース（すなわちｄ＝１とともに）。
【００９３】
このバージョンは、唯一の（大きな）分岐しかもっておらず、したがって、各等式において、あらゆる変数、すなわちメッセージのあらゆるビットが関わっている。この分岐の規模の大きさを考慮に入れると、この実施形態は小規模の分岐の弱さをもっていないといえる。
【００９４】
・同一関数ｆをともなう小さい分岐のケース
この特殊なケースは、たとえば１２ビットの値をともなう小さな分岐と同一関数ｆを関与させる。このバージョンは、とりわけ興味深いものである。なぜなら内蔵された小型の処理ユニットのなかに、たとえばチップ型カード（ｃａｒｔｅｓ  ａ  ｐｕｃｅ  ）中で簡単に実施できるからである。実施は、数学的プログラムまたは相互プロセッサ（ｃｏ−ｐｒｏｃｅｓｓｅｕｒ  ）を用いて可能となる。
【００９５】
ＨＦＥアルゴリズムの第一の代替案
本明細書の中ですでに記したような各分岐において使用される関数ｆは、有限体のなかに唯一の変数ｘをもつ多項方程式である。基底の中に表されるこの関数ｆは、合計次数が２となるような方程式のように表される。
【００９６】
事実、あらかじめ定義された一般的モデルからわずかに逸脱している別のタイプの関数ｆを使用することもできる。この新しいタイプの関数は、ｆとして有限体の複数の変数たとえば二つの変数ｘ１  とｘ２  に依存している関数を選択することからなり、その結果、基底において座標に応じた式は、合計次数が２のままであり、前項が存在する場合には、常にｆの定められた値によって前項を計算し直すことができるようになる。
【００９７】
この変数は、以下の数値例によってよりわかりやすくなるであろう。６４ビットの値とｐ＝２とともにアルゴリズムの分岐を考えてみよう。この代替案によれば、以下のようなｆ（ｘ，ｘ’）＝（ｙ、ｙ’）とともに、それぞれ３２ビットの２つの変数ｘとｘ’に依存しているｆをみてみよう。
【００９８】
ｙ＝ｘ４  ＋ｘ＊ｘ’＋ｘ’            （１）
ｙ’＝ｘ１７＋ｘ４  ＊ｘ’＋ｘ’３        （２）
（とりわけこの厳密な関数を使用することが勧められているわけではない。この厳密な関数はあくまで例として与えられたものである。）
（ｙ、ｙ’）から対（ｘ、ｘ’）を決定するためには、以下の要領で行うことができる。
【００９９】
方程式（１）から、ｘ’＝（ｙ−ｘ４  ）／（ｘ＋１）    （３）
を求める。
【０１００】
この結果方程式（２）から
0003583555.tif 000016
を求める。
【０１０１】
ところで、（４）は唯一の変数ｘをもつ多項方程式である。すでに指摘したように、数学者はすでに、このタイプの方程式を解くための一般的方法を知っている。したがって、（４）を解くことができ、その結果方程式を解く値ｘを定義することができる。次に、方程式（３）のなかでｘをこれらの値に置き換えることで、ｘ’の値を導き出すことができる。
【０１０２】
注記：有限体の中に複数の変数をもつ方程式について現在知られている解法技術によって、この例によって示されている方程式とは別のタイプの方程式を正しく解くことができる。とりわけ、必ずしも他の関数に応じて一つの変数を表し、それを置き換える必要があるわけではない方程式を解くことができる。
【０１０３】
ＨＦＥアルゴリズムの第二の代替案
必然的に、ＨＦＥアルゴリズムの説明とその代替案は、本発明の特許請求の範囲を、次数１、次数２をもつ多項方程式の利用に限定するものではない。次数３を使用することも完全に可能である。このときは、次数３の公開形態をとる。
【０１０４】
同様に、次数４さらに５も考えられる。しかしながら、その結果生じる公開方程式がコンピュータによって簡単に記憶し、計算することができるように、次数はかなり小さいままである必要がある。
【０１０５】
パラメータの選択はまた、最大限の安全性を保証し、暗号通信への侵入をできるだけ防ぐために重要である。このように安全性の理由から、以下であることが望ましい。
【０１０６】
１）各分岐には、少なくとも３２ビットの一つの変数が存在する、できれば少なくとも６２ビットの変数が存在する。
【０１０７】
２）Σγｉｊｘｉ  ｙｊ  ＋Σαｉ  ｘｉ  ＋Σβｊ  ｙｊ  ＋δ０  ＝０の形をとる等式は存在しない。係数γｉｊ、αｉ  、βｊ  あるいはσ０  の少なくともいずれか一つはゼロでなく、ｙｊ  が暗号化されたテキストの成分である場合には、またｘｉ  が普通の文字によるテキストの成分である場合には、それらの係数は常に検証される。注記：上記のマツモト−イマイのアルゴリズムが完全に安全でないことが明らかになったのは、とりわけこのような条件を検証できないからである。
【０１０８】
３）Σγｉｊｋ  ｘｉ  ｙｊ  ｙｋ  ＋Σαｉｊｘｉ  ｙｊ  ＋Σβｉｊｙｊ  ｙｋ  ＋Σμｉ  ｘｉ  ＋Σνｉ  ｙｉ  ＋δ０  ＝０の形の方程式、すなわち合計次数３で、ｘにおける次数が１の方程式が存在しない。
【０１０９】
４）より一般的には、安全性のために、小さい多項式による公開方程式の積の線形組合わせを別にして、普通の文字のメッセージと暗号化されたメッセージの座標の間で常に検証される「小さい」次数の方程式が存在しないことが望ましい。
【０１１０】
ＨＦＥアルゴリズムの第三の代替案
関数が全単射でない場合には、ＨＦＥアルゴリズムを使用するために、普通の文字のテキストの中に冗長度を入れる可能性を指摘してきた。
【０１１１】
他の可能性も存在する。実際に、暗号化された値の中にＫの新しい元を入れる場合には、普通の文字の値Ｘの規模より大きな暗号化文字の値Ｙをもつことができるからである。これらの新しい元もまた、Ｘの成分において次数２の方程式によって与えられる。より一般的に、図１の表記法を再記することによって、ｓ（ｘ）の同じ元を複数の分岐の中に転送することができる。基底の中に次数２の任意の方程式で構成される一つもしくは複数の分岐を付け加えることもできるが、これらの追加分岐は、正しい前項を他から区別するのに役立つ。
【０１１２】
ＨＦＥアルゴリズムの第四の代替案
図１の最終関数を与えるあらゆる方程式を公開にする代わりに、その一つもしくは複数の機密を保護することができる。すなわち、（Ｐ１  、・・・、Ｐｎ  ）を公開にする代わりに、これらの方程式の一部だけを公開にすることができる。このとき、暗号化は公開の（Ｐ１  、・・・、Ｐｎ  ）のみを計算することによって行われる。
【０１１３】
解読のためには、非公開のＰｉ  に可能なあらゆる値を試してみる。このことから先験的に、可能な複数の解読されたメッセージを与えることができ、正しいメッセージは、これまでのように、普通の文字のメッセージに冗長度を入れることによって、あるいは第三の代替案のなかで示した方法によって、正しいメッセージがマークされる。
【０１１４】
注記：このように、一つもしくは複数の公開方程式をを削除することによって、特定のケースでは、ＨＦＥアルゴリズムによって隠された体の構造の発見が一層難しくなる恐れがある。
【０１１５】
図２の説明
図２は、上述の暗号通信アルゴリズムを使用する暗号化／解読システムの一例を概略的に示している。
【０１１６】
同じ通信ネットワークに属している二人の個人ＡとＢがおり、各々がメッセージの送信／受信装置１と２をそれぞれ所有しているとする。この装置には、メッセージの暗号化と解読を行うために配置された計算手段、たとえばコンピュータと記憶手段が備えられている。少なくともこれらの計算または記憶手段の一部は、アクセスが制御されるゾーンの範囲を定めるマイクロケーブル論理回路またはマイクロプロセッサを内蔵したポータブルオブジェクト（ｏｂｊｅｔ  ｐｏｒｔａｔｉｆ）の中に置くことができ、その結果、暗号通信キーのような秘密情報を閉じ込めることができる（たとえば、フランス特許第２４０１４５９号に記載されたポータブルオブジェクトを参照のこと）。
【０１１７】
各装置には、特に一つのプログラムの形で先述のようなＨＦＥアルゴリズム及びＨＦＥ−１逆アルゴリズムが組込まれている。
【０１１８】
二台の装置は、互いに通信ライン３を用いてつながっている。
【０１１９】
二人の個人ＡとＢはそれぞれ、一対のキーをもっている。公開キーＣｐＡ  とＣｐＢ  及び、対応する公開キーＣｐＡ  とＣｐＢ  と相関関係にある秘密キーＣｓＡ  とＣｓＢ  である。ＡとＢが、キーの対を計算する手段を有していない場合には、ネットワークが非常に正確にその計算を行うことができ、その結果、ネットワークの各メンバーに対してある程度の権限（ａｕｔｏｒｉｔｅ）が与えられる。これら二人の個人が秘密を保護して互いに対話しようとする場合、交換されたデータが誰にも理解されないようにする場合には、以下の手順を行う。
【０１２０】
個人ＡはＢに対して自分の公開キーＣｐＡ  を送り、ＢはＡに対して自分の公開キーＣｐＢ  を送る。代替案によれば、ネットワークは中央記憶装置にすべてのメンバーの公開キーを保存しており、メンバーの要求に対してそれを知らせることができる。Ａがいったん公開キーＣｐＢ  を受け取ると、ＡはＢに送りたいと考えているメッセージＭを暗号通信アルゴリズムＨＦＥを用いてメッセージＭ’に暗号化するためにこの公開キーを使用する。このメッセージは、いったんＢによって受信されると、暗号通信アルゴリズムＨＦＥ−１と秘密キーＣｓＢ  を用いて解読される。Ｂだけがこのメッセージを解読することができる。なぜなら、Ｂはこのキーを所有しているネットワークの唯一のメンバーだからである。ＢからＡに向けてメッセージを伝達するための手順もまったく同じである。
【０１２１】
図３の説明
図３は、図２のシステムを利用して、先述の暗号通信アルゴリズムを使用する計算及びサインの検証手順を実施する例を概略的に示している。
【０１２２】
ここで、メッセージの伝達は真正性の検証とともに行われる、すなわち、メッセージＭの受信者が、そのメッセージは特定の人物から送られたものであることを確信できることが必要である。たとえば、ＡがＢに対して真正性が検証されたメッセージを伝えたいとしよう。二人の対話者は以下の手順を行うことができる。
【０１２３】
個人Ａは、まず第一にＢに対して自分の公開キーＣｐＡ  を送り、Ｂはまたこのキーをネットワークに要求する。次に、Ａは自分の秘密キーＣｓＡ  と暗号通信アルゴリズムＨＦＥ−１とともにメッセージを暗号化する。ここで得られた結果は、メッセージのサインＳと呼ばれる。さらに、このメッセージ（したがって普通の文字で通過するメッセージ）とそのサインがＢに送られる。Ｂは、暗号通信アルゴリズムＨＦＥと先に受け取った公開キーＣｐＡ  を用いてサインを解読する。Ｍ”と記される得られた結果は、受信されたメッセージＭに等しくなければならない。そうである場合には、サインは秘密キーＣｓＡ  を用いて正しく計算され、その結果、メッセージは、ネットワークの中でこのキーを唯一の所有しているメンバーであるＡから送られてきたものであることが証明される。
【０１２４】
このシステムのそれ自体よく知られた改良は、メッセージのサインではなくて、メッセージを濃縮した（ｃｏｎｃｅｎｔｒｅ  ）サインを計算することからなる。このように、「ハッシャージュ」機能によって、比較的重要なメッセージはメッセージの特徴的データＨに圧縮される。この「ハッシャージュ」機能は、従来のハッシャージュ機能（ＭＤ５またはＳＨＡ）を使用して行うことができる。
【０１２５】
要約すると、本発明は以下の発見の結果である。
【０１２６】
１．発明者は、マツモト−イマイの最初のアルゴリズムが暗号通信としては信頼性が確かなものではないことがわかった（資料Ｃｒｙｐｔｏ’９５、２４８から２６１ページ参照）。このアルゴリズムは、二つのアフィン変換ｓとｔを用いてＱ＝ｑθ のときｆ（ｂ）＝ａ１＋Ｑ  の形の全単射ｆを「隠す（ｃａｃｈｅｒ）」ことからなる。
【０１２７】
２．発明者は、はるかに一般的な機能をｆとみなすことが可能であるとわかった。というのも、発明者は、非全単射機能ｆを利用することが可能であることが分かった一方で、たとえば、多項式のＰＧＣＤや多項式の結果の計算を利用したり、ＧＲＯＢＮＥＲの基底を利用することによって、多項式の非常に多様な族について前項を計算できるという事実を利用できることが分かったからである。
【０１２８】
３．少なくとも分岐のいずれか一つがそれほど小さすぎないことが必要である。というのも、発明者は、小さい分岐は脆弱なＨＦＥアルゴリズムを導くことを発見したからである。
【０１２９】
４．さらに発明者は、場合によっては、第二の秘密の多項式変換によって第二の写像（Ｉ２）の変換の結果生じた第三の写像（Ｉ３）を構成する元の一部のみを選別することが可能である点に注目した。
【図面の簡単な説明】
【図１】メッセージを処理するために使用される変換の連鎖（ｅｎｃｈａｉｎｅｍｅｎｔ）を示す図である。
【図２】メッセージの暗号・解読を行うために使用される通信装置を示す図である。
【図３】メッセージのサイン及びその認証を行うために使用される同一の装置を示す図である。
【符号の説明】
１、２  送信／受信装置
３  通信ライン
【図１】
0003583555.tif 000025
【図２】
0003583555.tif 000026
【図３】
0003583555.tif 000027