【手続補正書】
【提出日】令和1年12月5日(2019.12.5)
【手続補正１】
【補正対象書類名】特許請求の範囲
【補正対象項目名】全文
【補正方法】変更
【補正の内容】
【特許請求の範囲】
【請求項１】
主群（（Ｍ，＋））の２つの元の難読化された加算のための電子計算デバイスであって、前記主群が有限アーベル群（
【数６１】
2018538620.tif 000001
）であり、
前記主群に対して定義されるのは、
第１（Ｎ）及び第２（Ｈ）の作用群であって、前記第１（Ｎ）及び第２（Ｈ）の作用群が前記主群（Ｍ）に作用し、前記第２の作用群（Ｈ）が生成元（ｈ）によって生成される巡回群である（Ｈ＝（ｈ））、第１（Ｎ）及び第２（Ｈ）の作用群と、
前記主群（Ｍ）の第１の部分集合（Δ）であって、前記主群（Ｍ）の任意の元（ｍ）が、前記第１の作用群（Ｎ）の元（ｎ）と前記第１の部分集合（Δ）の元（Ｘ）との積（ｍ＝ｎＸ）として表され得る第１の部分集合（Δ）において、前記第１の作用群（Ｎ）の前記元（ｎ）と前記第１の部分集合（Δ）の前記元（Ｘ）とが、前記主群（Ｍ）の前記元（ｍ）の正規化表現と呼ばれる、第１の部分集合（Δ）と、
前記主群（Ｍ）の任意の元（ｍ）が複数の被加数の和（
【数６２】
2018538620.tif 000002
）として表され得る前記主群（Ｍ）の第２の部分集合（Ｍ０＝｛ｍ０，．．．，ｍｒ−１｝）であって、各被加数が前記第１の作用群（Ｎ）の元（γｔ）と、前記第２の部分集合（Ｍ０）の元（
【数６３】
2018538620.tif 000003
）と、前記生成元の冪乗（ｈｔ）との積であり、
前記複数の被加数における前記第１の作用群の複数の元が、前記主群（Ｍ）の前記元（ｍ）の一般化表現と呼ばれる、第２の部分集合（Ｍ０＝｛ｍ０，．．．，ｍｒ−１｝）と
であり、前記電子計算デバイスが、
前記第２の部分集合（Ｍ０）の各元（ｍｉ）についてルックアップテーブル（Ｐｉ）を記憶する加算テーブル記憶装置であって、前記ルックアップテーブルが、前記主群（Ｍ）の正規化元（（γ，Ｘ））を入力として取り、前記入力を前記第１の作用群（Ｎ）の元（λ）と前記第１の部分集合（Δ）の元（Ｙ）とに写像し、前記第１の作用群（Ｎ）の前記元（λ）と前記第１の部分集合（Δ）の前記元（Ｙ）との積が、前記正規化元（γＸ）と前記第２の部分集合（Ｍ０）の前記元（ｍｉ）との和（λＹｈ＝γＸ＋ｍｉ）である、加算テーブル記憶装置と、
第１の加算入力（α０Ｘ０）及び第２の加算入力（
【数６４】
2018538620.tif 000004
）を受信する加算ユニットであって、前記第１及び第２の加算入力が前記主群（Ｍ）の元であり、前記第１の加算入力が正規化表現で受信され、前記第２の加算入力が一般化表現で受信され、前記第１の加算入力及び前記第２の加算入力の前記主群（Ｍ）における和を計算し、
前記第２の加算入力の前記被加数を前記第１の加算入力に順次加算することによって部分和を計算し、
前記第２の加算入力の被加数（
【数６５】
2018538620.tif 000005
）を前記部分和に加算することが、前記被加数における前記第２の部分集合（Ｍ０）の前記元（
【数６６】
2018538620.tif 000006
）についての、前記加算テーブル記憶装置に記憶された前記ルックアップテーブル（
【数６７】
2018538620.tif 000007
）を適用することを含む、
加算ユニットと
を備え、
＃Ｎ・＃Δ≧＃Ｍ、及び（＃Ｎ・＃Ｍ０）＃Ｈ≧＃Ｍであり、ここで、
＃Ｎは第１の作用群（Ｎ）の大きさであり、
＃Ｈは第２の作用群（Ｈ）の大きさであり、
＃Δは第１の部分集合（Δ）の大きさであり、
＃Ｍ０は第２の部分集合（Ｍ０）の大きさであり、
＃Ｍは主群（Ｍ）の大きさである、
電子計算デバイス。
【請求項２】
正規化表現の前記主群（Ｍ）の元（ｍ）が、前記電子計算デバイスにおいて２つの数のペアとして表され、前記２つの数の第１の数が前記第１の作用群（Ｎ）の前記元（ｎ）を示し、前記２つの数の第２の数が前記第１の部分集合（Δ）の前記元（Ｘ）を示し、
一般化表現の前記主群（Ｍ）の元（ｍ）が、前記電子計算デバイスにおいて少なくとも第１の数の系列として表され、前記第１の数の系列が前記被加数における前記第１の作用群（Ｎ）の前記元（γｔ）を示す、
請求項１に記載の電子計算デバイス。
【請求項３】
前記加算ユニットによって計算される前記和が正規化形式で表される、
請求項１又は請求項２に記載の電子計算デバイス。
【請求項４】
前記電子計算デバイスの外部のコンピュータから１つ又は複数の加算入力を受信するネットワークインターフェースであって、前記１つ又は複数の加算入力が一般化表現である、ネットワークインターフェースと、
１つ又は複数の定数加算入力を正規化表現で記憶する定数記憶装置と
を備え、
前記電子計算デバイスが、前記ネットワークインターフェースを介して受信される選択された加算入力と、前記定数記憶装置からの選択された定数加算入力とを前記加算ユニットを使用して加算する、
請求項１から請求項３までのいずれか一項に記載の電子計算デバイス。
【請求項５】
変換入力を受信する変換ユニット
を備え、
前記変換入力が一般化形式であり、前記変換ユニットが、正規化形式の前記主群の元を加算することによって、前記変換入力を正規化形式に変換し、及び／又は、
前記変換入力が正規化入力であり、前記変換ユニットが、前記第１の部分集合の元を一般化形式に写像する変換テーブルを記憶する、
請求項１から請求項４までのいずれか一項に記載の電子計算デバイス。
【請求項６】
線形関数（ｆ）を一般化形式の関数入力に適用する関数ユニットと、
前記第１の作用群（Ｎ）の元（γｔ）と、前記第２の部分集合（Ｍ０）の元（
【数６８】
2018538620.tif 000008
）と、前記生成元の冪乗（ｈｔ）との積（
【数６９】
2018538620.tif 000009
）を入力として取り、
前記積を、前記線形関数を前記積に適用した結果に写像するテーブルを記憶する線形関数テーブル記憶装置と
を備え、
前記関数ユニットが、前記線形関数テーブル記憶装置の前記テーブルを前記関数入力の前記被加数に適用する、
請求項１から請求項５までのいずれか一項に記載の電子計算デバイス。
【請求項７】
前記第２の作用群（Ｈ）が３つ以上の元を有するか、
前記第２の作用群（Ｈ）が２つの元を有するか、
前記第２の部分集合（Ｍ０）が２つ以上の元を有するか、
前記第２の部分集合（Ｍ０）が単位元でない１つの元を有するか、
前記主群（Ｍ）が、たとえばｌ≧４のアーベル群（
【数７０】
2018538620.tif 000010
）であるか、又は、
前記第１の作用群（Ｎ）が３つ以上の元を有する巡回群である、
請求項１から請求項６までのいずれか一項に記載の電子計算デバイス。
【請求項８】
前記生成元（ｈ）が次数ｋを有し、一般化表現の前記生成元（ｈ）の指数（ｔ）が、高々前記次数（ｋ）の特定の倍数マイナス１であり（ｔ≦λｋ−１）、前記特定の倍数が前記主群の全ての元について同一である、
請求項１から請求項７までのいずれか一項に記載の電子計算デバイス。
【請求項９】
前記主群が標数２を有し、前記第２の作用群が次数２を有し、一般化表現の前記生成元（ｈ）の前記冪乗（ｈｔ）が、高々前記次数の２倍マイナス１であるか（ｔ≦２ｋ−１）、又は、
前記主群が２より大きい標数を有するか、若しくは前記第２の作用群の次数が２より大きく、一般化表現の前記生成元（ｈ）の前記冪乗（ｈｔ）が高々前記次数マイナス１である（ｔ≦ｋ−１）、
請求項８に記載の電子計算デバイス。
【請求項１０】
前記加算ユニットが、
前記部分和を最初は前記第１の加算入力（α０，Ｘ０）に設定し、
前記第１の加算入力の前記被加数にわたってループし、各ループにおいて、前記第１の加算入力の前記被加数（
【数７１】
2018538620.tif 000011
）を加算することによって前記部分和を更新する、
請求項１から請求項９までのいずれか一項に記載の電子計算デバイス。
【請求項１１】
前記第１の加算入力が、α０∈Ｎ及びＸ０∈Δでの前記主群の元α０Ｘ０であり、前記第２の加算入力が前記主群の元
【数７２】
2018538620.tif 000012
であり、ｋが前記生成元の次数であり、γｉ∈Ｎ及びｍｉ∈Ｍ０であり、ｈが前記生成元であり、
前記加算ユニットが、
前記部分和を最初は前記第１の加算入力α０，Ｘ０に設定し、
０からλｋ−１までの前記生成元（ｈｔ）の各指数（ｔ）について、
【数７３】
2018538620.tif 000013
についての前記ルックアップテーブル（
【数７４】
2018538620.tif 000014
）をγｔ−１γｔ−１αｔＸｔに適用して、前記指数（
【数７５】
2018538620.tif 000015
）に対応する前記被加数を加算することによって、現在の部分和（αｔＸｔ）から次の部分和（αｔ＋１Ｘｔ＋１）を取得し、γ−１が前記主群（Ｍ）の単位元であり、αｔＸｔが前記現在の部分和であり、
前記部分和がγｔ−１αｔＸｔｈｔに等しい、
請求項１０に記載の電子計算デバイス。
【請求項１２】
前記第１の部分集合（Δ）が、前記第１の作用群（Ｎ）の元と、前記第２の部分集合の元と、前記第２の作用群（Ｈ）の元との積を総和して形成される元に、前記生成元の、前記生成元の次数マイナス１乘を加えたもの（
【数７６】
2018538620.tif 000016
）のみを含み、前記第２の作用群の前記元が、高々前記生成元の次数マイナス２乗の前記生成元（ｈ）の冪乗である、
請求項１から請求項１１までのいずれか一項に記載の電子計算デバイス。
【請求項１３】
前記主群（（Ｍ，＋））が、前記主群を環（（Ｒ，＋，・））にするさらなる演算（・）を有し、
第１の乗算入力及び第２の乗算入力を受信する乗算ユニットであって、前記第１及び第２の乗算入力が主環（Ｒ）の元であり、前記第１の乗算入力が正規化表現（（β０ｈ０＋・・・βｋ−２ｈｋ−２＋ｈｋ−１）α＝Ｘα）で受信され、前記第２の乗算入力が一般化表現（γ０ｈ０＋γ１ｈ１＋γ２ｈ２＋・・・）で受信され、前記第１の乗算入力及び前記第２の乗算入力の前記環（Ｒ）における積を計算し、
前記第１の乗算入力と、前記第２の乗算入力の第１の被加数とから第１の加算入力を計算し、前記第１の加算入力が正規化形式（Ｘ（αγ０））であり、
前記第１の乗算入力と、前記第１の被加数以外の前記第２の乗算入力の複数の被加数とから１つ又は複数の第２の加算入力を計算し、前記１つ又は複数の第２の加算入力が一般化形式（Ｘ（αγｉ）ｈｉ＝（Ｘｈｉ）ｎ’）であり、
前記第１の加算入力と前記１つ又は複数の第２の加算入力とを前記加算ユニットを介して加算する、
乗算ユニット
を備える、
請求項１２に記載の電子計算デバイス。
【請求項１４】
（＃Ｎ・＃Ｍ０）＃Ｈ≧３／２（＃Ｎ・＃Δ）であり、
より詳細には、
（＃Ｎ・＃Ｍ０）＃Ｈ≧５／２（＃Ｎ・＃Δ）であり、
＃Ｎが前記第１の作用群（Ｎ）の大きさであり、
＃Ｈが前記第２の作用群（Ｈ）の大きさであり、
＃Δが前記第１の部分集合（Δ）の大きさであり、
＃Ｍ０が前記第２の部分集合（Ｍ０）の大きさであり、
＃Ｍが前記主群（Ｍ）の大きさである、
請求項１から請求項１３までのいずれか一項に記載の電子計算デバイス。
【請求項１５】
主群（（Ｍ，＋））の２つの元を加算する電子計算デバイスで使用されるルックアップテーブルを計算するためのテーブル計算デバイスであって、前記主群が有限アーベル群
【数７７】
2018538620.tif 000017
であり、
第２の部分集合（Ｍ０）の元（ｍｉ）についての前記ルックアップテーブルを構築するテーブル作成ユニットであって、
前記主群（Ｍ）の入力された正規化元（（γ，Ｘ））を繰り返し選択し、
前記入力された正規化元（γＸ）と前記第２の部分集合（Ｍ０）の前記元（ｍｉ）との和（λＹｈ＝γＸ＋ｍｉ）を決定し、
第１の作用群（Ｎ）の元（λ）と、第１の部分集合（Δ）の元（Ｙ）とを、前記第１の作用群（Ｎ）の前記元（λ）と、前記第１の部分集合（Δ）の前記元（Ｙ）との積が前記和となるように決定し、
入力された環の元を前記第１の作用群（Ｎ）の前記元（λ）と、前記第１の部分集合（Δ）の前記元（Ｙ）とに写像する前記ルックアップテーブルにエントリを追加する
テーブル作成ユニット
を備える、テーブル計算デバイス。
【請求項１６】
主群（（Ｍ，＋））の２つの元の難読化された加算のための電子計算方法であって、前記主群が有限アーベル群
【数７８】
2018538620.tif 000018
であり、
前記主群に対して定義されるのは、
第１（Ｎ）及び第２（Ｈ）の作用群であって、前記第１（Ｎ）及び第２（Ｈ）の作用群が前記主群（Ｍ）に作用し、前記第２の作用群（Ｈ）が生成元（ｈ）によって生成される巡回群である（Ｈ＝（ｈ））、第１（Ｎ）及び第２（Ｈ）の作用群と、
前記主群（Ｍ）の第１の部分集合（Δ）であって、前記主群（Ｍ）の任意の元（ｍ）が、前記第１の作用群（Ｎ）の元（ｎ）と前記第１の部分集合（Δ）の元（Ｘ）との積（ｍ＝ｎＸ）として表され得る第１の部分集合（Δ）において、前記第１の作用群（Ｎ）の前記元（ｎ）と前記第１の部分集合（Δ）の前記元（Ｘ）とが、前記主群（Ｍ）の前記元（ｍ）の正規化表現と呼ばれる、第１の部分集合（Δ）と、
前記主群（Ｍ）の任意の元（ｍ）が複数の被加数の和として表され得る前記主群（Ｍ）の第２の部分集合（Ｍ０＝｛ｍ０，．．．，ｍｒ−１｝）であって、各被加数が前記第１の作用群（Ｎ）の元（γｔ）と、前記第２の部分集合（Ｍ０）の元（
【数７９】
2018538620.tif 000019
）と、前記生成元の冪乗（ｈｔ）との積（
【数８０】
2018538620.tif 000020
）であり、
前記複数の被加数における前記第１の作用群の複数の元が、前記主群（Ｍ）の前記元（ｍ）の一般化表現と呼ばれる、第２の部分集合（Ｍ０＝｛ｍ０，．．．，ｍｒ−１｝）と
であり、前記電子計算方法が、
前記第２の部分集合（Ｍ０）の各元（ｍｉ）についてルックアップテーブル（Ｐｉ）を記憶するステップであって、前記ルックアップテーブルが、前記主群（Ｍ）の正規化元（（γ，Ｘ））を入力として取り、前記入力を前記第１の作用群（Ｎ）の元（λ）と前記第１の部分集合（Δ）の元（Ｙ）とに写像し、前記第１の作用群（Ｎ）の前記元（λ）と前記第１の部分集合（Δ）の前記元（Ｙ）との積が、前記正規化元（γＸ）と前記第２の部分集合（Ｍ０）の前記元（ｍｉ）との和（λＹｈ＝γＸ＋ｍｉ）である、記憶するステップと、
第１の加算入力（α０Ｘ０）及び第２の加算入力（
【数８１】
2018538620.tif 000021
）を受信し、前記第１及び第２の加算入力が前記主群（Ｍ）の元であり、前記第１の加算入力が正規化表現で受信され、前記第２の加算入力が一般化表現で受信され、前記第１の加算入力及び前記第２の加算入力の前記主群（Ｍ）における和を計算するステップであって、
前記第２の加算入力の前記被加数を前記第１の加算入力に順次加算することによって部分和を計算するステップ
を有し、
前記第２の加算入力の被加数（
【数８２】
2018538620.tif 000022
）を前記部分和に加算するステップが、前記被加数における前記第２の部分集合（Ｍ０）の前記元（
【数８３】
2018538620.tif 000023
）についての、記憶された前記ルックアップテーブル（
【数８４】
2018538620.tif 000024
）を適用するステップを有する、
計算するステップと
を有し、
＃Ｎ・＃Δ≧＃Ｍ、及び（＃Ｎ・＃Ｍ０）＃Ｈ≧＃Ｍであり、ここで、
＃Ｎは第１の作用群（Ｎ）の大きさであり、
＃Ｈは第２の作用群（Ｈ）の大きさであり、
＃Δは第１の部分集合（Δ）の大きさであり、
＃Ｍ０は第２の部分集合（Ｍ０）の大きさであり、
＃Ｍは主群（Ｍ）の大きさである、
電子計算方法。
【請求項１７】
主群（（Ｍ，＋））の２つの元を加算する電子計算デバイスで使用されるルックアップテーブルを計算するためのテーブル計算方法であって、前記主群が有限アーベル群（
【数８５】
2018538620.tif 000025
）であり、
前記主群（Ｍ）の入力された正規化元（（γ，Ｘ））を繰り返し選択するステップと、
前記入力された正規化元（γＸ）と第２の部分集合（Ｍ０）の前記元（ｍｉ）との和（λＹｈ＝γＸ＋ｍｉ）を決定するステップと、
第１の作用群（Ｎ）の元（λ）と、第１の部分集合（Δ）の元（Ｙ）とを、前記第１の作用群（Ｎ）の前記元（λ）と、前記第１の部分集合（Δ）の前記元（Ｙ）との積が前記和となるように決定するステップと、
入力された環の元を前記第１の作用群（Ｎ）の前記元（λ）と、前記第１の部分集合（Δ）の前記元（Ｙ）とに写像する前記ルックアップテーブルにエントリを追加するステップと
を有する、テーブル計算方法。
【請求項１８】
コンピュータ上で実行された場合に、請求項１６に記載の電子計算方法又は請求項１７に記載のテーブル計算方法を実施するコンピュータプログラム命令を含む、コンピュータプログラム。
【請求項１９】
請求項１８に記載のコンピュータプログラムを含む、コンピュータ可読媒体。