"位数nの楕円曲線E上で動作する暗号システムであって、前記暗号システムは、第1の通信相手であって、第2の通信相手に対するデータを暗号処理する第1の通信相手を含み、前記第1の通信相手は、メモリ及び第1の暗号プロセッサを含み、前記第1の暗号プロセッサは、前記第1のメモリ内に、1つの群から別の群に対する自己準同形写像[z]を格納することであって、前記自己準同形写像[z]は、z2uzv=0を満たす二次代数的整数zに対応し、u及びvは秘密の整数であり、vはnに対して互いに素である、ことと、対応する秘密鍵操作[-w][u][z]を有する公開鍵操作として前記自己準同形写像[z]を識別することであって、wは整数であり、wv=1modnであり、[-w]は-wに対応する自己準同形写像であり、[u]はuに対応する自己準同形写像である、ことと、暗号処理されるべきデータxを獲得することと、前記公開鍵操作を前記データxに適用することにより、改変済みデータx’を獲得することと、前記改変済みデータx’を前記暗号システム内の前記第2の通信相手に提供することにより、前記第2の通信相手における第2の暗号プロセッサが、前記改変済みデータx’に対して秘密鍵操作を実行することを可能にすることとを実行するように構成されている、暗号システム。前記暗号データxは、メッセージmを含み、前記第1の暗号プロセッサによる前記公開鍵操作は、前記メッセージmを暗号化して、暗号化されたメッセージm’を獲得するように作用し、前記第2の暗号プロセッサによる前記秘密鍵操作の適用は、前記暗号化されたメッセージm’を復号化して、前記メッセージmを獲得する、請求項1に記載の暗号システム。第1の通信相手が、位数nの楕円曲線E上で動作する暗号システムにおいて、第2の通信相手に対するデータを暗号処理する方法であって、前記方法は、前記第1の通信相手において、第1の暗号プロセッサが、メモリ内に、1つの群から別の群に対する自己準同形写像[z]を格納することであって、前記自己準同形写像[z]は、z2uzv=0を満たす二次代数的整数zに対応し、u及びvは秘密の整数であり、vはnに対して互いに素である、ことと、前記第1の暗号プロセッサが、対応する秘密鍵操作[-w][u][z]を有する公開鍵操作として前記自己準同形写像[z]を識別することであって、wは整数であり、wv=1modnであり、[-w]は-wに対応する自己準同形写像であり、[u]はuに対応する自己準同形写像である、ことと、前記第1の暗号プロセッサが、暗号処理されるべきデータxを獲得することと、前記第1の暗号プロセッサが、前記公開鍵操作を前記データxに適用することにより、改変済みデータx’を獲得することと、前記第1の暗号プロセッサが、前記改変済みデータx’を前記暗号システム内の前記第2の通信相手に提供することにより、前記第2の通信相手における第2の暗号プロセッサが、前記改変済みデータx’に対して秘密鍵操作を実行することを可能にすることとを含む、方法。前記暗号データxは、メッセージmを含み、前記第1の暗号プロセッサによる前記公開鍵操作の適用は、前記メッセージmを暗号化して、暗号化されたメッセージm’を獲得し、前記第2の暗号プロセッサによる前記秘密鍵操作の適用は、前記暗号化されたメッセージm’から前記メッセージmを獲得する、請求項3に記載の暗号システム。位数nの楕円曲線E上で動作する暗号システムであって、前記暗号システムは、第1の通信相手であって、第2の通信相手に対するデータを暗号処理する第1の通信相手を含み、前記第1の通信相手は、メモリ及び第1の暗号プロセッサを含み、前記第1の暗号プロセッサは、対応する公開鍵操作[z]を有する秘密鍵操作[-w][u][z]を決定することであって、wは整数であり、wv=1modnであり、[z]は1つの群から別の群に対する自己準同形写像であり、前記自己準同形写像[z]は、z2uzv=0を満たす二次代数的整数zに対応し、u及びvは秘密の整数であり、vはnに対して互いに素であり、[-w]は-wに対応する自己準同形写像であり、[u]はuに対応する自己準同形写像である、ことと、暗号処理されるべきデータxを獲得することと、前記秘密鍵操作を前記データxに適用することにより、改変済みデータx’を獲得することと、前記改変済みデータx’を前記暗号システム内の前記第2の通信相手に提供することにより、前記第2の通信相手における第2の暗号プロセッサが、前記改変済みデータx’に対して公開鍵操作を実行することを可能にすることとを実行するように構成されている、暗号システム。前記データxは、署名されるべきメッセージmを含み、前記第1の暗号プロセッサは、前記メッセージmに対して前記秘密鍵操作を適用して、署名sを獲得し、前記公開鍵操作は、前記署名を検証する、請求項5に記載の暗号システム。前記メッセージmは、前記第2の通信相手によって提供される当初のメッセージMに適用されるハッシュ関数から生成される、請求項6に記載の暗号システム。前記暗号データxは、前記第1の通信相手によって署名を受ける複数のメッセージを含み、前記第1の通信相手は、前記複数のメッセージの組み合わせに前記秘密鍵操作を適用して、前記署名を獲得し、前記公開鍵操作は、前記第2の通信相手によって用いられて、前記署名を検証し、これにより、前記複数のメッセージのそれぞれを検証する、請求項5に記載の暗号システム。第1の通信相手が、位数nの楕円曲線E上で動作する暗号システムにおいて、第2の通信相手に対するデータを暗号処理する方法であって、前記方法は、前記第1の通信相手において、第1の暗号プロセッサが、対応する公開鍵操作[z]を有する秘密鍵操作[-w][u][z]を決定することであって、wは整数であり、wv=1modnであり、[z]は1つの群から別の群に対する自己準同形写像であり、前記自己準同形写像[z]は、z2uzv=0を満たす二次代数的整数zに対応し、u及びvは秘密の整数であり、vはnに対して互いに素であり、[-w]は-wに対応する自己準同形写像であり、[u]はuに対応する自己準同形写像である、ことと、前記第1の暗号プロセッサが、暗号処理されるべきデータxを獲得することと、前記第1の暗号プロセッサが、前記秘密鍵操作を前記データxに適用することにより、改変済みデータx’を獲得することと、前記第1の暗号プロセッサが、前記改変済みデータx’を前記暗号システム内の前記第2の通信相手に提供することにより、前記第2の通信相手における第2の暗号プロセッサが、前記改変済みデータx’に対して公開鍵操作を実行することを可能にすることとを含む、方法。前記データxは、署名されるべきメッセージmを含み、前記方法は、前記第1の暗号プロセッサが、前記秘密鍵操作を適用して前記メッセージmに作用することにより、署名sを獲得することを含み、前記公開鍵操作は、前記署名sを検証する、請求項9に記載の方法。前記メッセージmは、前記第2の通信相手によって当初のメッセージMに適用されるハッシュ関数から生成される、請求項10に記載の方法。前記暗号データxは、署名を受ける複数のメッセージを含み、前記秘密鍵操作は、前記複数のメッセージの組み合わせに作用して、前記署名を獲得し、前記公開鍵操作は、前記署名を検証し、これにより、前記複数のメッセージのそれぞれを検証する、請求項9に記載の方法。前記データxは、複数の署名者により署名されるべきメッセージを含み、前記秘密鍵操作は、前記複数の署名者のそれぞれに対応する複数の操作を含み、前記複数の操作は、前記メッセージに連続的に適用されて、署名を獲得し、前記公開鍵操作は、前記複数の署名者のそれぞれに対応する複数の対応する操作を含み、前記対応する操作は、前記複数の署名者のそれぞれに対応する前記複数の操作とは反対の順序で連続的に適用されて、前記署名を検証する、請求項9に記載の方法。位数nの楕円曲線E上で動作する暗号システムであって、前記暗号システムは、第1の通信相手であって、第2の通信相手から受信されたデータを暗号処理する第1の通信相手を含み、前記第1の通信相手は、メモリ及び第1の暗号プロセッサを含み、前記第1の暗号プロセッサは、前記第1のメモリ内に、1つの群から別の群に対する自己準同形写像[z]を格納することであって、前記自己準同形写像[z]は、z2uzv=0を満たす二次代数的整数zに対応し、u及びvは秘密の整数であり、vはnに対して互いに素である、ことと、対応する秘密鍵操作[-w][u][z]を有する公開鍵操作として前記自己準同形写像[z]を識別することであって、wは整数であり、wv=1modnであり、[-w]は-wに対応する自己準同形写像であり、[u]はuに対応する自己準同形写像である、ことと、前記第2の通信相手から改変済みデータx’を受信することであって、前記第2の通信相手は、前記改変済みデータx’を生成する際に前記秘密鍵操作を適用することによって暗号処理されたデータxを有する、ことと、前記改変済みデータx’に対して前記公開鍵操作を実行することによって、前記改変済みデータx’を暗号処理することとを実行するように構成されている、暗号システム。前記改変済みデータx’は、前記秘密鍵操作を用いて前記第2の通信相手によって署名されるメッセージmに対する署名sを含み、前記公開鍵操作は、前記署名を検証する、請求項14に記載の暗号システム。前記メッセージmは、前記第1の通信相手によって前記第2の通信相手に提供される当初のメッセージMに適用されるハッシュ関数から生成される、請求項15に記載の暗号システム。前記改変済みデータx’は、前記秘密鍵操作を用いて前記第2の通信相手によって署名される複数のメッセージに対する署名を含み、前記公開鍵操作は、前記署名を検証し、これにより、前記複数のメッセージのそれぞれを検証する、請求項14に記載の暗号システム。第1の通信相手が、位数nの楕円曲線E上で動作する暗号システムにおいて、第2の通信相手から受信されたデータを暗号処理する方法であって、前記方法は、前記第1の通信相手において、第1の暗号プロセッサが、メモリ内に、1つの群から別の群に対する自己準同形写像[z]を格納することであって、前記自己準同形写像[z]は、z2uzv=0を満たす二次代数的整数zに対応し、u及びvは秘密の整数であり、vはnに対して互いに素である、ことと、前記第1の暗号プロセッサが、対応する秘密鍵操作[-w][u][z]を有する公開鍵操作として前記自己準同形写像[z]を識別することであって、wは整数であり、wv=1modnであり、[-w]は-wに対応する自己準同形写像であり、[u]はuに対応する自己準同形写像である、ことと、前記第1の暗号プロセッサが、前記第2の通信相手から改変済みデータx’を受信することであって、前記第2の通信相手は、前記改変済みデータx’を生成する際に前記秘密鍵操作を適用することによって暗号処理されたデータxを有する、ことと、前記第1の暗号プロセッサが、前記改変済みデータx’に対して前記公開鍵操作を実行することによって、前記改変済みデータx’を暗号処理することとを含む、方法。前記改変済みデータx’は、前記秘密鍵操作を用いて前記第2の通信相手によって署名されるメッセージmに対する署名sを含み、前記公開鍵操作は、前記署名を検証する、請求項18に記載の方法。前記メッセージmは、前記第1の通信相手によって前記第2の通信相手に提供される当初のメッセージMに適用されるハッシュ関数から生成される、請求項19に記載の方法。前記改変済みデータx’は、前記秘密鍵操作を用いて前記第2の通信相手によって署名される複数のメッセージに対する署名を含み、前記公開鍵操作は、前記署名を検証し、これにより、前記複数のメッセージのそれぞれを検証する、請求項18に記載の方法。位数nの楕円曲線E上で動作する暗号システムであって、前記暗号システムは、第1の通信相手であって、第2の通信相手から受信されたデータを暗号処理する第1の通信相手を含み、前記第1の通信相手は、メモリ及び第1の暗号プロセッサを含み、前記第1の暗号プロセッサは、対応する公開鍵操作[z]を有する秘密鍵操作[-w][u][z]を決定することであって、wは整数であり、wv=1modnであり、[z]は1つの群から別の群に対する自己準同形写像であり、前記自己準同形写像[z]は、z2uzv=0を満たす二次代数的整数zに対応し、u及びvは秘密の整数であり、vはnに対して互いに素であり、[-w]は-wに対応する自己準同形写像であり、[u]はuに対応する自己準同形写像である、ことと、前記第2の通信相手から改変済みデータx’を受信することであって、前記第2の通信相手は、前記改変済みデータx’を生成する際に前記公開鍵操作を適用することによって暗号処理されたデータxを有する、ことと、前記改変済みデータx’に対して前記秘密鍵操作を実行することによって、前記改変済みデータx’を暗号処理することとを実行するように構成されている、暗号システム。前記整数zは、実数成分および虚数成分を含む複素数である、請求項1、5、14、22のいずれか一項に記載の暗号システム。前記自己準同形写像[z]は、有理マップとして表される、請求項1、5、14、22のいずれか一項に記載の暗号システム。前記改変済みデータx’は、暗号化されたメッセージm’を含み、前記暗号化されたメッセージm’は、前記第2の通信相手によって前記公開鍵操作を用いてメッセージmを暗号化することにより生成され、前記第1の暗号プロセッサによる前記秘密鍵操作の適用は、前記暗号化されたメッセージm’を復号化して、前記メッセージmを獲得する、請求項22に記載の暗号システム。第1の通信相手が、位数nの楕円曲線E上で動作する暗号システムにおいて、第2の通信相手から受信されたデータを暗号処理する方法であって、前記方法は、前記第1の通信相手において、第1の暗号プロセッサが、対応する公開鍵操作[z]を有する秘密鍵操作[-w][u][z]を決定することであって、wは整数であり、wv=1modnであり、[z]は1つの群から別の群に対する自己準同形写像であり、前記自己準同形写像[z]は、z2uzv=0を満たす二次代数的整数zに対応し、u及びvは秘密の整数であり、vはnに対して互いに素であり、[-w]は-wに対応する自己準同形写像であり、[u]はuに対応する自己準同形写像である、ことと、前記第1の暗号プロセッサが、前記第2の通信相手から改変済みデータx’を受信することであって、前記第2の通信相手は、前記改変済みデータx’を生成する際に前記公開鍵操作を適用することによって暗号処理されたデータxを有する、ことと、前記第1の暗号プロセッサが、前記改変済みデータx’に対して前記秘密鍵操作を実行することによって、前記改変済みデータx’を暗号処理することとを含む、方法。前記整数zは、実数成分および虚数成分を含む複素数である、請求項3、9、18、26のいずれか一項に記載の方法。前記自己準同形写像[z]は、有理マップとして表される、請求項3、9、18、26のいずれか一項に記載の方法。前記改変済みデータx’は、暗号化されたメッセージm’を含み、前記暗号化されたメッセージm’は、前記第2の通信相手によって前記公開鍵操作を用いてメッセージmを暗号化することにより生成され、前記第1の暗号プロセッサによる前記秘密鍵操作の適用は、前記暗号化されたメッセージm’を復号化して、前記メッセージmを獲得する、請求項26に記載の方法。発明者たちは、帯域幅の減少した強靭な暗号システムを提供するTOWFを得るために楕円曲線暗号システムの属性を使用し得ることを認識した。一側面において、本発明は、位数nの楕円曲線E上で動作する暗号システムを提供する。この暗号システムは、z2uzv=0の形を有する二次代数的整数zに対応する自己準同形写像[z]とここでu及びvは秘密の整数であり、vはnと互いに素である、自己準同形写像[z]を暗号データxに適用して改変済みデータx’を得る公開鍵操作と、データxを得るために改変済みデータx’に[-w][u][z]を適用する秘密鍵操作とを有するwは、整数であり,wv=1modnである。本発明は、他の面において、位数nの楕円曲線E上で動作する暗号システムにおいて暗号操作を実行するための方法を提供する。この方法は、z2uzv=0の形を有する二次代数的整数zに対応する自己準同形写像[z]を導出するステップであって、u及びvが秘密の整数であり、vがnと互いに素であるステップと、自己準同形写像[z]を用いる公開鍵操作を暗号データxに適用して改変済みデータx’を得るステップと、データxを得るために[-w][u][z]を用いる秘密鍵操作を改変済みデータx’に適用するステップであって、wが整数であり,wv=1modnであるステップとを含む。例えば、本発明は以下の項目を提供する項目1位数nの楕円曲線E上で動作する暗号システムであって、前記暗号システムは、z2uzv=0の形を有する二次代数的整数zに対応する自己準同形写像[z]であって、u及びvが秘密の整数であり、vとnとが互いに素である自己準同形写像と、前記自己準同形写像[z]を暗号データxに適用して改変済みデータx’を得る公開鍵操作と、前記データxを得るために前記改変済みデータx’に[-w][u][z]を適用する秘密鍵操作であって、wが整数であり、wv=1modnである秘密鍵操作とを有することを特徴とする暗号システム。項目2前記整数zは、実数成分及び虚数成分を有する複素数であることを特徴とする項目1に記載の暗号システム。項目3前記自己準同形写像[z]は、有理マップとして表されることを特徴とする項目1に記載の暗号システム。項目4前記暗号データxは、メッセージmを含み、前記公開鍵操作は、暗号化されたメッセージm’を得るために前記メッセージmを暗号化するように作用し、前記秘密鍵操作は、前記メッセージmを得るために前記暗号化されたメッセージm’を復号化する様に作用し、前記公開鍵操作は第1エンティティーにより実行され前記秘密鍵操作は第2エンティティーにより実行され、前記第1エンティティー及び前記第2エンティティーは前記暗号システムの部分であることを特徴とする項目1に記載の暗号システム。項目5前記データx’は、前記暗号システムの第1エンティティーにより署名されるメッセージmを含み、前記秘密鍵操作は署名sを得るために前記メッセージmに作用し、前記公開鍵操作は前記署名を検証するために前記暗号システムの第2エンティティーによって前記署名sに作用し、前記メッセージmは、当初、前記第2エンティティーによって生成されることを特徴とする項目1に記載の暗号システム。項目6前記メッセージmは、当初のメッセージMに適用されるハッシュ関数から生成されることを特徴とする項目5に記載の暗号システム。項目7前記暗号データxは、前記暗号システムの第1エンティティーによる署名を受ける複数のメッセージを含み、前記秘密鍵操作は前記署名を得るために前記複数のメッセージの組み合わせに作用し、前記公開鍵操作は前記署名を検証することにより前記複数のメッセージの各々を検証するために前記暗号システムの第2エンティティーによって使用されることを特徴とする項目1に記載の暗号システム。項目8位数nの楕円曲線E上で動作する暗号システムにおいて暗号操作を実行するための方法であって、前記方法は、z2uzv=0の形を有する二次代数的整数zに対応する自己準同形写像[z]を導出するステップであって、u及びvが秘密の整数であり、vとnとが互いに素であるステップと、前記自己準同形写像[z]を使用する公開鍵操作を暗号データxに適用して改変済みデータx’を得るステップと、前記データxを得るために[-w][u][z]を使用する秘密鍵操作を前記改変済みデータx’に適用するステップであって、wが整数であり、wv=1modnであるステップとを含むことを特徴とする方法。項目9前記整数zは、実数成分及び虚数成分を有する複素数であることを特徴とする項目8に記載の方法。項目10前記自己準同形写像[z]は、有理マップとして表されることを特徴とする項目8に記載の方法。項目11前記暗号データxは、メッセージmを含み、前記公開鍵操作の適用は、暗号化されたメッセージm’を得るために前記メッセージmを暗号化し、前記秘密鍵操作の適用は、前記暗号化されたメッセージm’から前記メッセージmを復号化することを特徴とする項目8に記載の方法。項目12前記データx’は、署名されるメッセージmを含み、前記秘密鍵操作は、署名sを得るために前記メッセージmに作用し、前記公開鍵操作はそれを検証するために前記署名に作用することを特徴とする項目8に記載の方法。項目13前記メッセージmは、当初のメッセージMに適用されるハッシュ関数から生成されることを特徴とする項目12に記載の方法。項目14前記暗号データxは、署名を受ける複数のメッセージを含み、前記秘密鍵操作は、前記署名を得るために前記複数のメッセージの組み合わせに作用し、前記公開鍵操作は、前記署名を検証することにより前記複数のメッセージの各々を検証するために前記署名に作用することを特徴とする項目8に記載の方法。項目15前記データxは、複数の署名者により署名されるべきメッセージを含み、前記秘密鍵操作は、各前記署名者に対応する複数の操作を含み、前記秘密鍵操作は、署名を得るために前記メッセージに連続的に適用され、前記公開鍵操作は、各前記署名者に対応する複数の操作を含み、前記公開鍵操作は、前記署名を検証するために前記秘密鍵操作とは反対の順序で連続的に適用されることを特徴とする項目8に記載の方法。次に添付図面を参照して本発明の実施態様を単に例として説明する。従って図1を参照すると、暗号システム10は、通信チャネル16を介して通信する第1エンティティー12と第2エンティティー14とを有する。第1エンティティー12と第2エンティティー14とは、両方のエンティティー12,14にとって使用可能な公開鍵関数又は秘密鍵関数18を適用する暗号モジュール15を各々有する。各エンティティー12,14は、上記のように暗号化/復号化又は署名/検証を得るためにTOWFと共に鍵関数18を利用する。このようなシステムを実現するためには、対応する公開鍵関数及び秘密鍵関数で適切なTOWFを決定する必要がある。発明者たちは、二次代数的整数zの使用によって適切なTOWFが得られることを認識した。次に曲線Eと、E上の[z]を定義する有理マップとを見出す。その有理マップ[z]はTOWFである。zの賢明な選択は、それが所要の暗号属性を有することを保証する、すなわち:a[z]が効率的に計算され得ること、b[z]を反転させることが困難であること、c[z]を定義する有理関数からのzの決定が困難であること、dzを知れば楕円曲線点の一定の集合上で[z]を反転させうること、を保証する。より一般的には、2つの異なる曲線E及びE’間の有理マップrを使用することができる。その有理マップはTOWFとして使用され得る。しかし、実現を容易にするためには、E=E’を使用するのが好都合である。EからEへの有理マップが好ましい実現形態である。有理マップすなわちEからEへのは、全て、平行移動translationと自己準同形写像との結合であり、平行移動は決定しやすく且つ反転させやすいので、有理マップの最も安全な部分は自己準同形写像である。従って自己準同形写像は有理マップの好ましい実現形態である。発明者等は、zを反転させるためにトラップドア逆数を計算する1つの有望な方法はzについて二次方程式z2uzv=0を使用することであることを認識した。ここでu及びvは整数である。この方程式をvzで割るとzu/v1/z=0が与えられる。従って1/z=-zu/vである。1/zは一般には二次代数的整数ではない。より精密には、もしzが1より大きな次数を有するならば、1/zは二次代数的整数ではない。従って、[z]を反転させる自己準同形写像は無い。その代わりに二元自己準同形写像[z’]=[-zu]があり、これは[z][z’]=[v]を満たす。特定の体Fでは、楕円曲線Eの位数nは時にはvと互いに素であり得、このことはwv=1modnとなるような整数wが存在することを意味する。これは、F上で定義されたEの点について[w]が[v]の逆関数として作用することを意味する。この場合、EFに対する[z]の作用は自己準同形写像[w][z’]=[-wzu]により反転可能である。もし[z]が効率よく発見され得るならば、[-wzu]も同様でありそうである。これについての代わりの式は[-w][u][z]である。従って、自己準同形写像[z]を公開鍵操作として利用し、[-w][w][z]という関係を秘密鍵操作として利用することが可能である。整数u,vは秘密に保たれて、秘密鍵機能を実行するエンティティーだけが利用可能である。これが体Fに特有であって他の体F’上で定義されたEについては当てはまらないということが理解されるであろう。F上で定義されたEの点は、Fの外側の座標を有する点が考慮されていないことを強調するために、時にはEFと表示される。[z]がトラップドア1方向性関数であるためには、[z]の公開定義からu及びvを決定することが計算上不可能であるべきであり、さもなければEFにおけるその逆数が[-w][u][z]として効率よく計算可能である。従って、[z]は、u及びvの容易な決定を許さない形で与えられなければならない。[z]を1対の有理関数として与えることにより,u及びvを容易に決定することはできないと考えられる。通例、第1の座標はxだけの関数であるので、[z]は或る程度は基底形式rx、gx、yであり、たとえrxを2つの多項式の比として完全に展開することが項の数の多さの故に実行不可能であったとしてもrxを見積もるための記述がrxの分子の次数をもしかすると明らかにするかもしれない。[z]の次数はvであるので、[z]の記述がvを暴露してしまう可能性がある。従って、[z]が1方向性トラップドアであることを確実にするためには、uも暴露されないことを保証することが重要であり、さもなければ上記のように[z]が反転され得る。シルバーマンによれば、一般的楕円曲線の自己準同形写像リングを決定することは自明の問題ではない。v及びuは整数因数に至るまで自己準同形写像リングを本質的に決定するので、楕円曲線についての記述だけからv及びuを決定することは一般には不可能である。従って、単一の複素自己準同形写像の記述からは、自己準同形写像リングを決定することは依然として自明の問題ではなさそうである。特に、このことは、uを[z]の記述から1対の有理関数として決定することが依然として自明の問題ではなさそうであることを意味する。従って、zの次数は、適度に大きな位数を有するように選択されるべきである。これは、u2<4vという関係を使ってuの全ての可能な値を調べ尽くすことができないことを確実にするのに役立つ。これは上記のことから言えることである。なぜならば、zは虚数複素数animaginarycomplexnumberでなければならないからである。[z]についての1つの可能な組み立ては、次の所見に基く。上記のように、もしe=[z]=rx,cyr’xが次数mを有するならば、rx=px/qxであり、ここでp及びqは夫々次数m及びm-1の多項式である。eのカーネルは、1からmまでのjについてeZj=Oであるようなm個の点楕円mpointsellipticO=Z1,Z2,...,Zmの集合である。もし2からmまでのjについてZj=zj,yjならば、qx=x-z2x-z3...x-zmであると仮定することができる。更に、mZj=Oである。なぜならば、[z’][z]=[m]であり、ここでz’はmZj=[m]Zj=[z’][z]Zj=[z’]O=Oとして上で決定されたzの共役theconjugateだからである。更に、eのカーネルは、必ずしもEFの一部としてではないけれども、楕円曲線Eにおける位数mの部分群である。楕円曲線は、全体として、一般には少なくともm1個のこのような部分群を有する。次に、点B=0,√bを含む楕円曲線を考察する。[z]W=Bであるような点Wが存在すると仮定する。1からmまでのjについてWj=WZjとする。W1=WZ1=WO=Wであることに留意1からmまでのjについてWj=wj,ujであると仮定する。すると、何らかの定数dについてpx=dx-w1x-w2...x-wmとなる。px=dx-w1uxであることに注意する。ここでuxの根は本質的にqxの根の有理関数である。2つの多項式の根がこのような単純な関係を有するときには、該多項式の係数の変換則atransformationが存在する。例えばuxの根がqxの根の平方であるならばux=q√xq-√x-1degqxである。この様に、qxを数的に表現する能力は、uxを数的に表現する手段を与えることが分かる。上記の所見を用いて、その有限x座標が低ハミングウェイトalowHammingWeight多項式qxの零点である何らかの楕円曲線Eにおける位数mの部分群を捜し求めることができる。低ハミングウェイト多項式qxを持つことは望ましいことである。なぜならば、それらの数値を効率よく求められるからである。次に、上記のように点Wを見出し、それは上で概説されたように分子pxを効率よく計算することを可能にする。px及びqxの値を求めることができれば、rxの値を求めることができる。そのような多項式px、qxを見出す方法についての1つの説明は次のとおりである。もしZjが[z]のカーネルであれば-Zjもそうであり、従ってzjはqxの二重根として現れることができる。qxが素数である次数mを有すると仮定する。更にmがエルキース素数anElkiesprimeであると仮定するが、その正確な意味は以下の議論においては問題ではない。これは、次数m-1/2の多項式sxについてqx=sx2であることを意味し、それはm番目の除算多項式themthdivisionpolynomialの1つの因数である。楕円曲線EF上の点を数えるためのスクーフ-エルキース-アトキンSchoof-Elkies-AtkinSEAアルゴリズムは、sxの形の多項式が見出されるステップを含む。多項式vxの係数は再帰方程式arecursionequationにより見出される。従って、そのような多項式を組み立てるための方法が知られている。SEAアルゴリズムでは、そのようなsxがmの割合に小さな値について見出されるが、本目的のためにはmを大きくするのが有利である。もう一つの可能なアプローチは低ハミングウェイトの既約多項式sxを選ぶことである。zをその根のうちの1つであるとし、ここでzは楕円曲線E上の或る点のx座標である。その点は有限の位数mを有することができる。この有限位数は、ガロア自己同形写像を適用することにより、sxの任意の根zについて当てはまる。sxの根から生じるこれらの点が下に閉じられているということ、すなわちそれらがEの部分群を形成するということも事実であるならば、sxは望ましい形を有する。そうであるためには、基本的に、gP=2Pであるようなガロアの自己同形写像gとE上の点Pとを必要とする。これが可能になるようにg,P,及びEを探すことにより、所望の形の多項式sxを見出せるかもしれない。実際問題としては、y座標は、2つの値のうちの一方をとり得るに過ぎないので、無視できる。もし自己準同形写像のカーネルが点Oにおいてのみ群EFと交差するならば、自己準同形写像eの群EFに対する作用は反転可能である。この場合、自己準同形写像eは群EFの自己同形写像である。一般に群EFは巡回性cyclicであり、以下の議論においてはEFは巡回性であると仮定する。もしeが位数nの巡回群の自己同形写像であれば、発明者たちにより実現されたアルゴリズムはeG=dGとなるように整数dを決定し、ここではその群について加法表示法を使用する。このアルゴリズムのコストは、n-1の因数分解による。nのランダムな値が一般に約n1/3である因数fを有するということが知られている。このサイズの因数が与えられると、該アルゴリズムはfの一定倍数のステップでdを決定することができる。これは、dGが与えられた場合にdを見出す一般的アルゴリズムよりかなり速い。これらの一般的アルゴリズムはn1/2ステップを必要とする。従って、n-1がn1/3に近い因数fを持たないような位数nを群EFが持つことが望ましい。nをこの様に選ぶことの代わりは、考慮される敵対者にとってn1/3の攻撃のコストが高すぎるように、単にnを僅かに大きく選ぶことである。例えば、80ビットのセキュリティレベルでは、そのような大きなnをnが約2240であるように選ぶことができ、128ビットのセキュリティレベルではnが約2384であるようにnを選ぶことができる。しかし、効率上の理由からより小さなnを用いるのが好都合であり、従ってn-1がn1/3と同様のサイズを持つことを保証するために必要な特別の作業が行われると想定される。自己準同形写像eが使用される方法が一般的に図2に示されている。第1エンティティー12は1つのxの値をとる。それは、2つの対応するyの値のうちの一方を任意に選ぶことができる。それは次に公開鍵関数[z]を有利マップe=rx,gx,yとして適用し、何らかの値x’、y’に到達するためにex,yの値を求める。これは基本的公開鍵操作であろう。第2エンティティー14は、メッセージx’、y’を受け取って、値x,yを得るためにe-1を適用する。これは基本的秘密鍵操作[-w][u][z]であろう。yが-yに変更されればy’は-y’に変化するけれども、x’及びxは影響を受けない。従って全ての実際的目的のためにyをおおむね無視することができる。図3に示されている暗号化にこれを適用するために、第1エンティティー12は公開鍵関数[z]の使用によりxを平文にセットし、x’を暗号文にセットする。公開鍵暗号化への既知の精巧なアプローチは一般に、特に同じ平文の繰り返し暗号化が別々の暗号文を与えるように、何らかのランダム化されたパディングを平文xに対して適用する。第2エンティティー14は、平文xを得るために秘密鍵関数を用いて暗号文x’を復号化する。これを図4に示されているように署名に適用するために、第2エンティティー14は、署名されるべきメッセージになるようにx’をセットし、秘密鍵関数の適用によってxを署名として計算する。一般に長いメッセージからx’を生成するために何らかのハッシングが使用され、それはデジタル署名のための標準的手法である。第1エンティティー12は、ex,y=x’,y’であることを確かめるために公開鍵操作eを用いる。ハッシュ関数は1方向性であるので、第1エンティティーはx,yから出発してeを適用してx’、y’を得ることによって署名を偽造することはできない。なぜならば、次のステップはx’=HashMであるようにメッセージMを見出すことであり、これは1方向性ハッシュ関数に関しては実行不可能であると考えられるからである。もし[z]を反転させる問題がEにおける離散値対数問題と同じく難しければ、暗号群のサイズはRSATOWFのために使われる群より小さくなり得る。例えば、3072ビットRSA係数は、256ビット体上で定義された楕円曲線とおおよそ同程度に安全であると考えられる。これら両者のセキュリティレベルは128ビットであると考えられ、これは、オンラインバンキング用などにインターネットで今日非常に広く用いられている商業級セキュリティレベルである。楕円曲線トラップドア1方向性関数[z]、署名x又は基本暗号文x’のサイズは256ビットであり、これに対してRSAについてはサイズは3072ビットである。在来の楕円曲線暗号法ECCと比べると、256ビット楕円曲線についての署名の長さは約512ビットであり、これは楕円曲線TOWFについての署名のサイズの2倍である。同様の節約が暗号化のために可能である。本発明のもう一つの実施態様及び応用においてはTOWFは署名又は暗号文の集合に対して応用される。以下は署名について説明されるけれども、暗号文についての詳細が全く同様であることが理解されるであろう。署名の集合は、単一の署名が単一の署名者により署名された多数のメッセージ、又は多数の署名者により署名された単一のメッセージ、又は多数の署名者により署名された多数のメッセージを表すことを意味する。次に図5を参照すると、t個のメッセージm1,m2,...,mtに署名するために署名者例えば第1エンティティー12は各メッセージをハッシュし、各ハッシュを楕円曲線点に変換してt個の点P1,...Ptを生じさせ、これらは加え合わされて点P=P1...Ptを生じさせる。署名者は、その後、逆関数e-1を適用して署名S=e-1Pを得、これは多数のメッセージのための単一のメッセージである。次に、他のエンティティー例えば第2エンティティー14による検証は、該メッセージをハッシュし、各ハッシュを1つの点に変換し、合計してトータルPとし、次にeS=Pであるか否か検査することにより公開鍵18操作eをSに適用することから成る。これを反復して該メッセージを単に連結することの利点は、署名操作が加法型であるので、メッセージの部分を変更することを望む署名者のために大きな融通性を達成することである。上記の手続きは、個々のメッセージコンポーネントに署名する順序を課さない、すなわち、署名検証は、同じエンティティーにより署名された署名の非順序集合に関連する。しかし、個々のスカラー倍’重み’が検証をするエンティティーによって取り出され或いは導出され得るとすれば、この手続きが個々の署名コンポーネントS1,...,Stの和にではなくて個々の署名の加重和に向けて容易に一般化され得ることに留意するべきである。これは、重みを適用可能な順序付けに依存させることによって、これらのt個のメッセージの署名プロセスにおける順序付けの実行を可能にする。次に図6を参照して、もしt個の異なる署名者例えば、全体として第1エンティティー12が同じ楕円曲線群を使用すると共に別々のTOWFe1,...,etを有するならば、それらは次のように単一のメッセージの集合署名を形成することができる。メッセージmに署名するために、第1エンティティー12の第1署名者はそのメッセージのハッシュを計算し、そのハッシュを楕円曲線点Pに変換する。その後、それらは共にすなわち、第1エンティティー12の全署名者が、自分たちの秘密鍵操作を各々適用することによってet-1et-1-1...e1-1Pを計算し、ここで署名はエンティティー1,2,...,tによって順に行われる。検証例えば第2エンティティー14によるは、対応する公開鍵18操作の各々を逆順に適用し、得られた点Pが署名されたメッセージmのハッシュ値に対応するか否かを調べることから成る。一般に、楕円曲線自己準同形写像は交換可能であるので、多数のエンティティーによる単一のメッセージの署名順序は重要でないと思われる。しかし、例えば署名プロセスにおいて順序付けを実行するために、この手続きは容易に一般化され得るということに留意するべきである。これは、例えば、下記のように、各々の署名をするエンティティーに、計算される署名に対してオフセットを使用させることによって、実現され得る。点Pでのエンティティーiによる個々の署名がei-1PAiであり、ここで楕円曲線点Aiがエンティティーiについて唯一であると仮定する。すると、エンティティー1,2,...,tによるメッセージm上の順序付き集合書名は、mをハッシュしてこれを楕円曲線点Pに変換し前のように、その後に、署名をするエンティティーの各々に、得られた値に対して自分自身の署名操作を適用させることによって、得られる。これはS1=e1-1PA1,S2=e2-1S1A2,...,St=et-1St-1At、をもたらし、ここでStは、得られた集合署名である。署名検証は、個々のオフセットA1,...,Atが検証を行うエンティティーによって取り出され或いは導出され得るのであれば、いまや上記手続きの些細な改変であって、シーケンスSt-1=etSt-At,St-2=etSt-1-At-1,...,S1=e2S2-A2,P=e1S1-A1を計算すると共に楕円曲線点Pが署名されているメッセージmのハッシュ値に対応するか否かを調べることに依存する。上では、元の方式の改変は、署名をするエンティティーの各々について独特のオフセットAiを用いて署名プロセスの順序付けを実施するように記載されている。Si=ei-1PAiではなくてSi=ei-1fP,iを定義するような改変が可能であることが分かり、ここでfは、fP,iと署名するエンティティーiに関連する公開情報とからPを効率よく再計算できるという特性を有するEにおけるマッピングである。多数のエンティティーによる単一のメッセージの順序付けられた署名は、多数の書名が必要とされると共に、関係する権限を授けられた当事者によりプロジェクトが特定の階層順に例えば、ボトムアップ署名の上で放棄される必要のある場合に、例えば大規模な組織でプロジェクトを署名の上で放棄するために有益であり得る。本発明は或る特定の実施態様に関連して説明されたけれども、その種々の改変は、本書に添付されている項目で概説されている発明の範囲から逸脱すること無く当業者にとっては明らかであろう。上で列挙された全ての参考文献の開示内容全体が参照により本書に組み込まれる。"