(57)【特許請求の範囲】
【請求項１】
安全な計算を実行するコンピューティング装置の作動方法であって：
受領手段が、少なくとも一つの関数入力値および状態入力値を受け取る段階と；
決定手段が、前記計算において実行されるべき演算の数を決定する段階であって、前記計算は、前記関数入力値に対して第一の演算が実行され、前の演算によって生成された結果に対してその後の演算が実行されるものである、段階と；
設定手段が、前記計算において実行されるべき演算の数に基づいて前記関数入力値について初期の暗号化ランクを設定する段階と；
エンコード手段が、前記初期の暗号化ランクに応じて、前記少なくとも一つの関数入力値および前記状態入力値を一緒にエンコードして、エンコードされた入力値を得る段階であって、前記暗号化ランクは該エンコードにおいて前記状態入力値のビットのいくつかを占める、段階と；
計算手段が、前記計算を実行する段階であって、エンコードされた入力値に対して第一の演算が実行されてエンコードされた結果を生成し、その後の演算が前の演算によって生成されたそれぞれのエンコードされた結果に対して実行されて、さらなるエンコードされた結果を生成する、段階と；
設定手段が、前記計算における演算が前記エンコードされた入力値または前の演算によって生成されたエンコードされた結果に対して実行されるときに新たな暗号化ランクを設定する段階であって、前記計算における前記演算の前記エンコードされた結果が前記新たな暗号化ランクをもつ、段階と；
デコード手段が、デコード関数を実行する段階であって、前記デコード関数は、エンコードされた結果があらかじめ定義された値に到達した暗号化ランクをもつ場合にのみ、該エンコードされた結果から使用可能な出力値を提供する、段階とを含む、
方法。
【請求項２】
前記関数入力値が人間が解釈できるデータを含む、請求項１記載の方法。
【請求項３】
前記関数入力値が所定の暗号化プロセスに従って暗号化されたデータを含む、請求項１記載の方法。
【請求項４】
前記使用可能な出力値は人間が解釈できるデータを含む、請求項１ないし３のうちいずれか一項記載の方法。
【請求項５】
前記使用可能な出力値が所定の暗号化プロセスに従って暗号化されたデータを含む、請求項１ないし３のうちいずれか一項記載の方法。
【請求項６】
前記関数入力値について初期の暗号化ランクを設定する段階が、前記初期の暗号化ランクを、前記計算において実行されるべき演算の数に等しく設定することを含み、
前記計算において前記エンコードされた入力値または前の演算によって生成された結果に対して演算が実行されるたびに新たな暗号化ランクを設定する段階が、前記暗号化ランクを1だけデクリメントすることを含み、
デコード関数を実行する段階が、デコード関数を実行する段階であって、前記デコード関数は、前記暗号化ランクが0に等しい場合にのみ、エンコードされた結果から使用可能な出力値を提供する、段階を含む、
請求項１ないし５のうちいずれか一項記載の方法。
【請求項７】
前記計算が、未知の回数実行される可能性がある第一の数の演算を含むループを含んでおり、
前記関数入力値について初期の暗号化ランクを設定する段階が、前記初期の暗号化ランクを、前記ループに含まれる各演算の一回の生起を含む前記計算において実行されるべき演算の数に等しく設定することを含み、
前記計算において前記エンコードされた入力値または前の演算によって生成された結果に対して演算が実行されるたびに新たな暗号化ランクを設定する段階が、前記暗号化ランクを1だけデクリメントすることを含み、
デコード関数を実行する段階が、デコード関数を実行する段階であって、前記デコード関数は、前記暗号化ランクが前記第一の数を法として0に等しい場合にのみ、エンコードされた結果から使用可能な出力値を提供する、段階を含む、
請求項１ないし５のうちいずれか一項記載の方法。
【請求項８】
前記計算が、未知の回数実行される可能性がある第一の数の演算を含むループを含んでおり、
前記関数入力値について初期の暗号化ランクを設定する段階が、前記初期の暗号化ランクを、前記ループに含まれる演算を除いて前記計算において実行されるべき演算の数に等しく設定することを含み、
前記計算において前記エンコードされた入力値または前の演算によって生成された結果に対して演算が実行されるたびに新たな暗号化ランクを設定する段階が、前記ループに含まれない演算が実行されるたびに前記暗号化ランクを1だけデクリメントすることを含み、
デコード関数を実行する段階が、デコード関数を実行する段階であって、前記デコード関数は、前記暗号化ランクが0に等しい場合にのみ、エンコードされた結果から使用可能な出力値を提供する、段階を含む、
請求項１ないし５のうちいずれか一項記載の方法。
【請求項９】
安全な計算を実行するコンピューティング装置であって：
少なくとも一つの関数入力値および状態入力値を受け取るための入力と；
前記計算における複数の演算を実行するためのプロセッサであって、前記計算は、前記関数入力値に対して第一の演算が実行され、前の演算によって生成された結果に対してその後の演算が実行されるものである、プロセッサと；
初期の暗号化ランクに応じて前記少なくとも一つの関数入力値および前記状態入力値を一緒にエンコードして、エンコードされた入力値を得るためのエンコーダであって、前記関数入力値についての前記初期の暗号化ランクは前記計算において実行されるべき演算の数に基づいて設定され、前記暗号化ランクは該エンコードにおいて前記状態入力値のビットのいくつかを占める、エンコーダとを有しており、
前記プロセッサは前記計算を実行するためであり、それにより、エンコードされた入力値に対して第一の演算が実行されてエンコードされた結果を生成し、その後の演算が前の演算によって生成されたそれぞれのエンコードされた結果に対して実行されて、さらなるエンコードされた結果を生成し、前記計算における演算が前記エンコードされた入力値または前の演算によって生成されたエンコードされた結果に対して実行されるときに新たな暗号化ランクが設定されて、前記計算における前記演算の前記エンコードされた結果が前記新たな暗号化ランクをもち；
当該コンピューティング装置はさらにデコード関数を実行するためのデコーダを有しており、前記デコード関数は、エンコードされた結果があらかじめ定義された値に到達した暗号化ランクをもつ場合にのみ、該エンコードされた結果から使用可能な出力値を提供するものである、
コンピューティング装置。
【請求項１０】
前記関数入力値が人間が解釈できるデータを含む、請求項９記載のコンピューティング装置。
【請求項１１】
前記関数入力値が所定の暗号化プロセスに従って暗号化されたデータを含む、請求項９記載のコンピューティング装置。
【請求項１２】
前記使用可能な出力値は人間が解釈できるデータを含む、請求項９ないし１１のうちいずれか一項記載のコンピューティング装置。
【請求項１３】
前記使用可能な出力値が所定の暗号化プロセスに従って暗号化されたデータを含む、請求項９ないし１１のうちいずれか一項記載のコンピューティング装置。
【請求項１４】
前記関数入力値についての前記初期の暗号化ランクが、前記計算において実行されるべき演算の数に等しく設定され、
前記計算において前記エンコードされた入力値または前の演算によって生成された結果に対して演算が実行されるたびに前記新たな暗号化ランクが、前記暗号化ランクを1だけデクリメントすることによって得られ、
前記デコード関数は、前記暗号化ランクが0に等しい場合にのみ、エンコードされた結果から使用可能な出力値を提供するものである、
請求項９ないし１３のうちいずれか一項記載のコンピューティング装置。
【請求項１５】
前記計算が、未知の回数実行される可能性がある第一の数の演算を含むループを含んでおり、
前記関数入力値についての前記初期の暗号化ランクが、前記ループに含まれる各演算の一回の生起を含む前記計算において実行されるべき演算の数に等しく設定され、
前記計算において前記エンコードされた入力値または前の演算によって生成された結果に対して演算が実行されるたびに前記新たな暗号化ランクが、前記暗号化ランクを1だけデクリメントすることによって得られ、
前記デコード関数は、前記暗号化ランクが前記第一の数を法として0に等しい場合にのみ、エンコードされた結果から使用可能な出力値を提供するものである、
請求項９ないし１３のうちいずれか一項記載のコンピューティング装置。
【請求項１６】
前記計算が、未知の回数実行される可能性がある第一の数の演算を含むループを含んでおり、
前記関数入力値についての前記初期の暗号化ランクが、前記ループに含まれる演算を除いて前記計算において実行されるべき演算の数に等しく設定され、
前記計算において前記エンコードされた入力値または前の演算によって生成された結果に対して演算が実行されるたびに前記新たな暗号化ランクが、前記ループに含まれない演算が実行されるたびに前記暗号化ランクを1だけデクリメントすることによって得られ、
前記デコード関数は、前記暗号化ランクが0に等しい場合にのみ、エンコードされた結果から使用可能な出力値を提供するものである、
請求項９ないし１３のうちいずれか一項記載のコンピューティング装置。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明はコンピューティングの分野に関し、詳細には暗号化された値での計算に関する。
【背景技術】
【０００２】
特許文献１は、暗号化された値での計算のためのコンピューティング装置を開示している。
【０００３】
より詳細には、特許文献１は、テーブル・ネットワークを記憶しているコンピューティング装置を開示している。装置は関数入力値をエンコードされた入力値として取得するよう構成される。ここで、エンコードされた入力値は、関数入力値を状態入力値と組み合わせて単一の値に一緒に暗号化したものである。テーブル・ネットワークは、その入力としてこのエンコードされた入力値を取り、その出力としてエンコードされた出力値を生成する。エンコードされた出力値は、関数出力値を状態出力値と組み合わせて単一の値に一緒に暗号化したものである。ここで、関数出力値は、関数入力値にデータ関数を適用した結果に等しく、状態出力値は状態入力値に状態関数を適用した結果に等しい。
【０００４】
特許文献２は、排他的ORを使う鍵注入に関わる暗号学的プロセスにおいて暗号鍵を隠すための解決策を開示している。特許文献２は、鍵および暗号文の両方に対して線形転置Pを実行することによってサイファー鍵を隠す。「通常の」世界に戻ることなく転置Pを通された値に対してXORを直接計算できるので、攻撃者から隠された仕方で演算が実行でき、攻撃者が観察できるのは転置された鍵だけである。
【先行技術文献】
【特許文献】
【０００５】
【特許文献１】国際公開第2014/096117号
【特許文献２】米国特許出願公開第2012/155638号
【発明の概要】
【課題を解決するための手段】
【０００６】
本発明のある側面によれば、安全な計算を実行する方法であって：少なくとも一つの関数入力値および状態入力値を受け取る段階と；前記計算において実行されるべき演算の数を決定する段階であって、前記入力値に対して第一の演算が実行され、前の演算によって生成された結果に対してその後の演算が実行される、段階と；前記計算において実行されるべき演算の数に基づいて前記入力値について初期暗号化ランクを設定する段階と；前記少なくとも一つの関数入力値および／または状態入力値を前記初期暗号化ランクで一緒にエンコードする段階であって、前記暗号化ランクは前記エンコードにおいて前記関数入力値および／または状態入力値のビットのいくつかを占める、段階と；前記計算を実行する段階であって、エンコードされた入力値に対して第一の演算が実行されてエンコードされた結果を生成し、その後の演算が前の演算によって生成されたそれぞれのエンコードされた結果に対して実行されて、さらなるエンコードされた結果を生成する、段階と；前記計算における演算が前記エンコードされた入力値または前の演算によって生成されたエンコードされた結果に対して実行されるときに新たな暗号化ランクを設定する段階であって、前記計算におけるその演算の前記エンコードされた結果が前記新たな暗号化ランクをもつ、段階と；デコード関数を実行する段階であって、前記デコード関数は、エンコードされた結果があらかじめ定義された値に到達した暗号化ランクをもつ場合にのみ、該エンコードされた結果から使用可能な出力値を提供する、段階とを含む、方法が提供される。
いくつかの態様を記載しておく。
〔態様１〕
安全な計算を実行する方法であって：
少なくとも一つの関数入力値および状態入力値を受け取る段階と；
前記関数入力値に対して第一の演算が実行され前の演算によって生成された結果に対してその後の演算が実行される前記計算において実行されるべき演算の数を決定する段階と；
前記計算において実行されるべき演算の数に基づいて前記関数入力値について初期暗号化ランクを設定する段階と；
前記少なくとも一つの関数入力値および／または状態入力値を前記初期暗号化ランクに応じてエンコードする段階であって、前記暗号化ランクは該エンコードにおいて前記関数入力値および／または状態入力値のビットのいくつかを占める、段階と；
前記計算を実行する段階であって、エンコードされた入力値に対して第一の演算が実行されてエンコードされた結果を生成し、その後の演算が前の演算によって生成されたそれぞれのエンコードされた結果に対して実行されて、さらなるエンコードされた結果を生成する、段階と；
前記計算における演算が前記エンコードされた入力値または前の演算によって生成されたエンコードされた結果に対して実行されるときに新たな暗号化ランクを設定する段階であって、前記計算における前記演算の前記エンコードされた結果が前記新たな暗号化ランクをもつ、段階と；
デコード関数を実行する段階であって、前記デコード関数は、エンコードされた結果があらかじめ定義された値に到達した暗号化ランクをもつ場合にのみ、該エンコードされた結果から使用可能な出力値を提供する、段階とを含む、
方法。
〔態様２〕
前記関数入力値が人間が解釈できるデータを含む、態様１記載の方法。
〔態様３〕
前記関数入力値が所定の暗号化プロセスに従って暗号化されたデータを含む、態様１記載の方法。
〔態様４〕
前記使用可能な出力値は人間が解釈できるデータを含む、態様１ないし３のうちいずれか一項記載の方法。
〔態様５〕
前記使用可能な出力値が所定の暗号化プロセスに従って暗号化されたデータを含む、態様１ないし３のうちいずれか一項記載の方法。
〔態様６〕
前記関数入力値について初期暗号化ランクを設定する段階が、前記初期暗号化ランクを、前記計算において実行されるべき演算の数に等しく設定することを含み、
前記計算において前記エンコードされた入力値または前の演算によって生成された結果に対して演算が実行されるたびに新たな暗号化ランクを設定する段階が、前記暗号化ランクを1だけデクリメントすることを含み、
デコード関数を実行する段階が、デコード関数を実行する段階であって、前記デコード関数は、前記暗号化ランクが0に等しい場合にのみ、エンコードされた結果から使用可能な出力値を提供する、段階を含む、
態様１ないし５のうちいずれか一項記載の方法。
〔態様７〕
前記計算が、未知の回数実行される可能性がある第一の数の演算を含むループを含んでおり、
前記関数入力値について初期暗号化ランクを設定する段階が、前記初期暗号化ランクを、前記ループに含まれる各演算の一回の生起を含む前記計算において実行されるべき演算の数に等しく設定することを含み、
前記計算において前記エンコードされた入力値または前の演算によって生成された結果に対して演算が実行されるたびに新たな暗号化ランクを設定する段階が、前記暗号化ランクを1だけデクリメントすることを含み、
デコード関数を実行する段階が、デコード関数を実行する段階であって、前記デコード関数は、前記暗号化ランクが前記第一の数を法として0に等しい場合にのみ、エンコードされた結果から使用可能な出力値を提供する、段階を含む、
態様１ないし５のうちいずれか一項記載の方法。
〔態様８〕
前記計算が、未知の回数実行される可能性がある第一の数の演算を含むループを含んでおり、
前記関数入力値について初期暗号化ランクを設定する段階が、前記初期暗号化ランクを、前記ループに含まれる演算を除いて前記計算において実行されるべき演算の数に等しく設定することを含み、
前記計算において前記エンコードされた入力値または前の演算によって生成された結果に対して演算が実行されるたびに新たな暗号化ランクを設定する段階が、前記ループに含まれない演算が実行されるたびに前記暗号化ランクを1だけデクリメントすることを含み、
デコード関数を実行する段階が、デコード関数を実行する段階であって、前記デコード関数は、前記暗号化ランクが0に等しい場合にのみ、エンコードされた結果から使用可能な出力値を提供する、段階を含む、
態様１ないし５のうちいずれか一項記載の方法。
〔態様９〕
安全な計算を実行するコンピューティング装置であって：
少なくとも一つの関数入力値および状態入力値を受け取るための入力と；
前記関数入力値に対して第一の演算が実行され前の演算によって生成された結果に対してその後の演算が実行される前記計算における複数の演算を実行するためのプロセッサと；
前記少なくとも一つの関数入力値および／または状態入力値を初期暗号化ランクで一緒にエンコードするためのエンコーダであって、前記関数入力値についての前記初期暗号化ランクは前記計算において実行されるべき演算の数に基づいて設定される、エンコーダを有しており、
前記プロセッサは前記計算を実行するためであり、それにより、エンコードされた入力値に対して第一の演算が実行されてエンコードされた結果を生成し、その後の演算が前の演算によって生成されたそれぞれのエンコードされた結果に対して実行されて、さらなるエンコードされた結果を生成し、前記計算における演算が前記エンコードされた入力値または前の演算によって生成されたエンコードされた結果に対して実行されるときに新たな暗号化ランクが設定されて、前記計算における前記演算の前記エンコードされた結果が前記新たな暗号化ランクをもち；
当該コンピューティング装置はさらにデコード関数を実行するためのデコーダを有しており、前記デコード関数は、エンコードされた結果があらかじめ定義された値に到達した暗号化ランクをもつ場合にのみ、該エンコードされた結果から使用可能な出力値を提供するものである、
コンピューティング装置。
〔態様１０〕
前記関数入力値が人間が解釈できるデータを含む、態様９記載のコンピューティング装置。
〔態様１１〕
前記関数入力値が所定の暗号化プロセスに従って暗号化されたデータを含む、態様９記載のコンピューティング装置。
〔態様１２〕
前記使用可能な出力値は人間が解釈できるデータを含む、態様９ないし１１のうちいずれか一項記載のコンピューティング装置。
〔態様１３〕
前記使用可能な出力値が所定の暗号化プロセスに従って暗号化されたデータを含む、態様９ないし１１のうちいずれか一項記載のコンピューティング装置。
〔態様１４〕
前記関数入力値についての前記初期暗号化ランクが、前記計算において実行されるべき演算の数に等しく設定され、
前記計算において前記エンコードされた入力値または前の演算によって生成された結果に対して演算が実行されるたびに前記新たな暗号化ランクが、前記暗号化ランクを1だけデクリメントすることによって得られ、
前記デコード関数は、前記暗号化ランクが0に等しい場合にのみ、エンコードされた結果から使用可能な出力値を提供するものである、
態様９ないし１３のうちいずれか一項記載のコンピューティング装置。
〔態様１５〕
前記計算が、未知の回数実行される可能性がある第一の数の演算を含むループを含んでおり、
前記関数入力値についての前記初期暗号化ランクが、前記ループに含まれる各演算の一回の生起を含む前記計算において実行されるべき演算の数に等しく設定され、
前記計算において前記エンコードされた入力値または前の演算によって生成された結果に対して演算が実行されるたびに前記新たな暗号化ランクが、前記暗号化ランクを1だけデクリメントすることによって得られ、
前記デコード関数は、前記暗号化ランクが前記第一の数を法として0に等しい場合にのみ、エンコードされた結果から使用可能な出力値を提供するものである、
態様９ないし１３のうちいずれか一項記載のコンピューティング装置。
〔態様１６〕
前記計算が、未知の回数実行される可能性がある第一の数の演算を含むループを含んでおり、
前記関数入力値についての前記初期暗号化ランクが、前記ループに含まれる演算を除いて前記計算において実行されるべき演算の数に等しく設定され、
前記計算において前記エンコードされた入力値または前の演算によって生成された結果に対して演算が実行されるたびに前記新たな暗号化ランクが、前記ループに含まれない演算が実行されるたびに前記暗号化ランクを1だけデクリメントすることによって得られ、
前記デコード関数は、前記暗号化ランクが0に等しい場合にのみ、エンコードされた結果から使用可能な出力値を提供するものである、
態様９ないし１３のうちいずれか一項記載のコンピューティング装置。
【０００７】
これは、ある種の実施形態では、権限のない者が、計算における演算の中間結果を得ることによってエンコード・プロセスについての情報を得ることができないという利点をもつ。
【０００８】
本発明の第二の側面によれば、第一の側面の方法を実行するためのコンピューティング装置が提供される。
【０００９】
本発明のこれらおよび他の側面は、以下に記載される実施形態から明白であり、それを参照することから明快にされるであろう。
【図面の簡単な説明】
【００１０】
本発明のこれらおよび他の側面は、図面を参照して以下に記載される実施形態から明白であり、それを参照することから明快にされるであろう。
【図１】計算を実行する方法を示すフローチャートである。
【図２】データ関数および状態関数を実装するテーブル・ネットワークを示す概略図である。
【図３】計算を実行する方法を示すフローチャートである。
【図４】計算を実行するためのコンピューティング装置を示す図である。
【発明を実施するための形態】
【００１１】
図１は、安全な計算を実行する方法を示すフローチャートである。第一の演算ブロック２０に少なくとも一つの入力値が供給され、第一の演算ブロック２０は入力値（単数または複数）に対して関数または演算を実行して少なくとも一つの結果値を生成する。
【００１２】
第一の演算ブロック２０からの前記少なくとも一つの結果値は判断ブロック２２に供給され、判断ブロック２２は第一の演算ブロック２０からの前記少なくとも一つの結果値が第一の指定された基準を満たすかどうかを判定する。第一の指定された基準が満たされる場合、前記第一の演算ブロック２０からの前記少なくとも一つの結果値は、可能性としては少なくとも一つの追加的な入力値と一緒に、第二の演算ブロック２４に供給され、第二の演算ブロック２４は前記入力値（単数または複数）に対して関数または演算を実行して少なくとも一つの結果値を生成する。
【００１３】
第一の指定された基準が満たされない場合には、前記第一の演算ブロック２０からの前記少なくとも一つの結果値は前記第一の演算ブロック２０の入力に戻され、それぞれの関数または演算が再び実行される。これは、何回繰り返されてもよい。
【００１４】
前記第二の演算ブロック２４からの前記少なくとも一つの結果値は第二の判断ブロック２６に供給され、第二の判断ブロック２６は第二の演算ブロック２４からの前記少なくとも一つの結果値が第二の指定された基準を満たすかどうかを判定する。第二の指定された基準が満たされる場合、前記第二の演算ブロック２４からの前記少なくとも一つの結果値は、可能性としては少なくとも一つの追加的な入力値と一緒に、第三の演算ブロック２８に供給される。
【００１５】
第三の演算ブロック２８は前記入力値（単数または複数）に対して関数または演算を実行して少なくとも一つの結果値を生成する。前記第三の演算ブロック２８からの前記少なくとも一つの結果値は、可能性としては少なくとも一つの追加的な入力値と一緒に、第四の演算ブロック３０に供給される。
【００１６】
第四の演算ブロック３０は前記入力値（単数または複数）に対して関数または演算を実行して少なくとも一つの結果値を生成する。
【００１７】
前記第四の演算ブロック３０からの前記少なくとも一つの結果値は、可能性としては少なくとも一つの追加的な入力値と一緒に、第五の演算ブロック３２に供給される。
【００１８】
第五の演算ブロック３２は前記入力値（単数または複数）に対して関数または演算を実行して少なくとも一つの結果値を生成する。
【００１９】
第二の判断ブロック２６が第二の指定された基準が満たされないと判定する場合には、前記第二の演算ブロック２４からの前記少なくとも一つの結果値は、可能性としては少なくとも一つの追加的な入力値と一緒に、第六の演算ブロック３４に供給される。
【００２０】
第六の演算ブロック３４は前記入力値（単数または複数）に対して関数または演算を実行して少なくとも一つの結果値を生成する。前記第六の演算ブロック３４からの前記少なくとも一つの結果値は、可能性としては少なくとも一つの追加的な入力値と一緒に、前記第五の演算ブロック３２に供給される。
【００２１】
先と同様に、第五の演算ブロック３２は前記入力値（単数または複数）に対して関数または演算を実行して少なくとも一つの結果値を生成する。
【００２２】
この場合、前記第五の演算ブロック３２は本方法における最終演算ブロックであり、第五の演算ブロック３２によって生成された結果値は、本方法の出力値のはたらきをする。
【００２３】
ある実施形態では、最初の演算ブロック２０に供給される入力値および最後の演算ブロック３２から供給される出力値はプレーンな、人間に解釈可能な形である。他の実施形態では、最初の演算ブロック２０に供給される入力値自身が暗号化された形であってもよい。たとえば、入力値は特定の認証プロトコルを使って署名されていてもよく、あるいはデータ暗号化規格（DES:  Data  Encryption  Standard）または先進暗号化規格（AES:  Advanced  Encryption  Standard）を使って必要に応じて特定のDES鍵またはAES鍵に基づいて暗号化されいてもよい。入力値は、特定の暗号化ドメインで受領されてもよく（暗号化されていないデータも一つの具体的な暗号化ドメインと見なされる）、出力値は、同じ暗号化ドメインでまたは異なるドメインで生成されてもよい。こうして、出力値はその後のプロセスによって使用されることができる。
【００２４】
より一般には、入力値および出力値はそれぞれ、事実上いかなる者によってでも解釈されることのできる情報を含む公開ドメインにあると言うことができる。
【００２５】
図２は、ある実施形態において、演算ブロック２０、２４、２８、３０、３２、３４のそれぞれの形をより詳細に示している。
【００２６】
具体的には、図２は、演算ブロックがテーブル・ネットワークを使って動作する場合を示している。
【００２７】
図２は、より大きなテーブル・ネットワーク１００に埋め込まれたテーブル・ネットワーク１８０を示している。このように、テーブル・ネットワーク１８０は、図１に示した演算ブロック２０、２４、２８、３０、３２、３４のために使われてもよい。図示したテーブル・ネットワーク１８０は単一のテーブル１３０のみを含んでいる。わかるだろうが、テーブル１３０をテーブル・ネットワークとして、たとえばテーブル・サイズと安全性の間のトレードオフにおいて実装することが可能である。図２では、テーブルは長方形で示されており、値は右上隅を切り欠いた長方形で示されている。
【００２８】
テーブル・ネットワーク１８０は、入力として複数のエンコードされた入力値、たとえばエンコードされた入力値１２２および１２４を取るよう構成される。テーブル・ネットワーク１８０は、出力としてエンコードされた出力値１６０を生成するよう構成される。以下の記述では、二つの入力値および単一の出力値をもつデータ関数および状態関数を想定するが、実施形態は任意の数の入力値および／または出力値に拡張されうる。特に、一つの入力および一つの出力をもつデータ／状態関数が可能であり、二つの入力および一つの出力をもつデータ／状態関数が可能である。
【００２９】
テーブル・ネットワーク１８０は前記データ関数のために構成され、電子記憶において記憶される。電子記憶は、前記テーブル・ネットワークを適用することによって前記データ関数を計算するよう構成された電子プロセッサに結合される。
【００３０】
エンコードされた値１２２は関数入力値１０２および状態入力値１１２から得られる。たとえば、これはエンコーダ１１０によってなされてもよい。エンコーダ１１０は、テーブル・ネットワーク１８０を含む同じ装置に含まれていてもよいが、これは必須ではない。入力値は、すでにエンコードされた形になって受領されてもよく、および／またはエンコードされた形で伝送されてもよい。あるいは、入力値は、エンコードされていない形で受領／伝送されてもよい。後者の場合、入力値は、エンコードされ、内部ではエンコードされた形で使われてもよい。たとえば装置の外部で異なるエンコードが使われる場合、再エンコードがあってもよい。たとえば、関数出力値１６２および状態出力値１６４がデコーダ１７０から得られてもよい。データ関数のエンコードされた入力は、別のテーブルまたはテーブル・ネットワークの出力であってもよい。これは、二つの関数のために構成されたテーブル・ネットワークであってもなくてもよい。異なるデータ関数のために構成されたテーブル・ネットワークを組み合わせることによって、プログラム全体が構築されてもよい。
【００３１】
エンコーダ１１０およびデコーダ１７０は互いの逆として得られてもよい。
【００３２】
エンコーダ１１０は次のように得られてもよい。関数入力値および状態入力値のそれぞれの可能な組み合わせがリストされる。たとえば、両方が4ビット幅である場合、16*16＝256通りの可能な組み合わせがある。256の組み合わせは、ランダムな全単射順で自分自身にマッピングされてもよい。同じことは他のサイズにも当てはまる。また、何らかの秘密のエンコード鍵を使って、暗号化関数が使われてもよく、たとえば、8ビット・ブロック・サイファーが適用されてもよい。
【００３３】
エンコードされた入力データは関数入力値１０２（下記ではωと称する）および状態入力値１１２（下記ではσと称する）を相互依存する仕方で含む。たとえば、関数入力は、エンコードされた入力のすべてのビットに依存する。このように、エンコードされた入力値１２２の一部のみを知っても、一般には、関数入力値１０２や状態入力値１１２を見出すことはできない。
【００３４】
こうして、入力値はエンコードされ、入力値に対して演算が実行されて、エンコードされた出力値が得られる。
【００３５】
下記でより詳細に述べるように、それぞれのエンコードされた値は、暗号化されたデータ・ドメイン内であり、このドメインへの鍵をもつ者によってのみ解釈されることができる。
【００３６】
図１に示される、プロセスが複数の演算を含む一般型の方法においては、一つの演算の結果は、デコードなしにその後の演算の入力に渡されてもよい。
【００３７】
しかしながら、本方法についての情報を得たい攻撃者は本方法を解釈し、ある演算の前記エンコードされた結果を得ることができるかもしれない。すると、攻撃者は、本方法についての情報を得るために、そのエンコードされた結果にデコード段階を適用することができることがありうる。
【００３８】
したがって、ある実施形態では、本方法は、たとえば本方法を実行するプログラムをコンパイルする際に実行される初期段階であって、方法内の演算の数を決定する段階を含む。ある実施形態では、これは、各変数がちょうど一度代入される静的単一代入（static  single  assignment）形式を使うコンパイラーによって達成される。したがって、使用される任意の変数は、典型的には、インデックスを用いて延長され、すべての新たに再定義される変数は一意的なインデックスを使うことができる。このプロセスは、この場合、入力値に対していくつの演算が実行されるかを決定するために使われることができる。これは、その変数に割り当てられる異なるインデックスの数に等しいからである。
【００３９】
次いで、初期の入力値（単数または複数）、たとえば第一の演算ブロック２０に供給された初期の入力値（単数または複数）について、初期暗号化ランクが設定される。この初期暗号化ランクは、それらの値が本方法の一環として受ける演算の数に基づいて設定される。次いで、この初期暗号化ランクはエンコードされた入力値に関連付けられる。
【００４０】
暗号化ランクは、関数値ωおよび状態値σとは別個であってもよく、あるいはωおよび／またはσ空間のビットのいくつかを占有してもよい。
【００４１】
次いで、各演算が実行されるときに、暗号化ランクが変更される。
【００４２】
各暗号化ランクは、別個のエンコード・スキームと考えられることができる。計算の中間段において使用されるエンコード・スキームは、デコードされて使用可能な結果を生じることができないようなものである。
【００４３】
たとえば、ある実施形態では、初期暗号化ランクは、本方法の一環としてそれらの値が受ける演算の数に等しい数に設定される。すなわち、本方法がn個の演算に関わるなら、初期暗号化ランクはnに設定され、初期入力値（単数または複数）に対してエンコードEnが実行される。その後、計算においてエンコードされた入力値に対して演算が実行されるたびに、エンコードされた値に関連付けられた暗号化ランクは1だけデクリメントされる。こうして、一つの演算が実行された後には、新たな暗号化ランクは(n−1)であり、よってエンコードEn-1が中間的な値（単数または複数）に対して実行される。
【００４４】
本方法の各段においてエンコードされた値からデコードされた出力を得るために必要とされるデコード演算Dは、エンコード演算の逆であってもよく、この実施形態では、解読が、暗号化ランクが0までデクリメントされた場合に、使用可能な結果を生じるのみであるように、定義される。
【００４５】
すなわち、解読関数は次のように作用する。
【００４６】
【数１】
0006499323.tif 000002
Di(Ej(ω,σ))＝⊥という文は、関数Diがこの特定の入力について、任意の無意味な値を返し、該無意味な値は大半の入力についてωではないことを意味する。だが関数Diは、ωの一部の値についてはωを返すこともある。すなわち、0に等しくないiまたはi≠jのいくつかの値についてDi(Ej(ω,σ))＝ωとなるωのいくつかの値があることがある。だがこれらの値はわからないので、前記結果を傍受する者がこれらの値を使ってエンコードについての情報を推定することは可能ではない。Di(Ej(ω,σ))＝⊥という文は、Ej(ω,σ)とωの間に相関がないことを意味する。
【００４７】
初期暗号化ランクを設定し、演算が実行されるときに暗号化ランクをデクリメントし、ランクが0であるときに使用可能な出力値を生成するデコード演算を実行するこの方法はほんの一例であることは理解されるであろう。他の多くの方式が使用できる。たとえば、エンコードされた入力値に関連付けられた暗号化ランクが当該計算において入力値に対して実行された演算の数が何らかの以前に決定された基準を満たしたことを示す場合にのみ、エンコードされた入力値が有用な出力値に解読されることができる方法である。
【００４８】
たとえば、エンコードされた入力値に関連付けられた暗号化ランクが当該計算において入力値に対して実行された演算の数が以前に決定された演算総数に達したことを示す場合にのみ、エンコードされた入力値が有用な出力値に解読されるのでもよい。この文脈において、有用な出力値は、入力値と同じ暗号化ドメインにある値であってもよい。こうして、入力値が人間が解釈できる形であれば、出力値も人間が解釈できる形であってもよい。入力値自身がテーブル・ネットワーク・ドメインの外部で暗号化された形で提供される場合には、有用な出力値は同じ暗号化された形であってもよく、よってその後のプロセスによって使用されることができる。しかしながら、入力値が暗号化された形で提供されるが出力値は人間が解釈できる形であったり、あるいはその逆であったりすることも可能である。
【００４９】
図１に示し上述した方法では、入力値に対して実行される演算の数は、本方法が第三の演算ブロック２８および第四の演算ブロック３０を含む分枝をたどるか、あるいは第六の演算ブロック３４を含む分枝を取るかに依存して変わる。
【００５０】
したがって、図１に示されるような分岐した方法では、入力値に対して実行される演算の数が各分枝で同じになるよう、入力値を変更しない一つまたは複数のダミー演算（たとえば入力値に0を加算するまたは入力値に1を乗算するなど）が分枝の一つに含められてもよい。
【００５１】
こうして、図１は、この目的のために含められるダミー演算３６を含めることを示している。この場合、第六の演算ブロック３４からの前記少なくとも一つの出力値はダミー演算ブロック３６に供給され、ダミー演算ブロック３６の出力は可能性としては前記少なくとも一つの追加的な入力値と一緒に、第五の演算ブロック３２に供給される。
【００５２】
さらに、図１に示される方法では、潜在的なループがある。すなわち、事前には、第一の演算ブロック２０が何回その演算を実行するかはわからない。
【００５３】
これに対処するために、第一の演算ブロック２０は、プロセスが二回目またはその後の回のためにブロック２０にループで戻るとき、暗号化ランクは、プロセスが初めてブロック２０に到達したときに取っていた値にリセットされる。
【００５４】
こうして、演算ブロック２０、２４、２８、３０、３２、３４およびダミー演算ブロック３６は、それぞれの演算が完了されるときに暗号化ランクが1だけデクリメントされるよう、構成される。
【００５５】
すると、その効果は、上記方法が完了である場合にのみ、解読マッピングを適用することによって有用な出力値を得ることができるというものであり、最終的な出力値は第五の演算ブロック３２の出力において得られる。
【００５６】
これはつまり、たとえ攻撃者が中間的な値へのアクセスを得たとしても、攻撃者はこれらを解読して有用な値を得ることはできず、よって本方法の中間段階について情報を得ることができないということである。
【００５７】
計算が潜在的なループを含む図１に示した状況に対処するための代替として、モジュロ算術を使う方法が使われてもよい。こうして、たとえば、計算がp個の演算および未知の回数実行されるループ内のさらなるq個の演算を含む状況を考える。すると、初期暗号化ランクは(p＋q)に設定され、このランクは演算が実行されるたびにデクリメントされ、解読関数は、暗号化ランクが「qを法として0」に等しい場合に有用な出力を生成するよう設定される。すなわち、ループ内の演算が一度実行される場合、実行される演算の総数は(p＋q)であり、計算完了後の暗号化ランクは上述した単純な場合と同様に0に等しく、よって解読関数は有用な結果を生じる。しかしながら、ループ内の演算がm回実行される場合には、実行される演算の総数は(p＋m・q)であり、計算完了後の暗号化ランクは−m・qに等しい。これは「qを法として0」に等しいので、解読関数はやはり有用な結果を生じる。
【００５８】
図３は、コンピューティング装置における安全な計算を実行する方法の概要を示すフローチャートである。段階２００では、コンピューティング装置は、少なくとも一つの入力値を受け取る。段階２０２では、コンピューティング装置は、前記計算において実行されるべき演算の数を決定する。前記入力値に対して第一の演算が実行され、前の演算によって生成された結果に対してその後の演算が実行される。段階２０４では、上記でより詳細に述べたように、コンピューティング装置は、前記計算において実行されるべき演算の数に基づいて前記入力値について初期暗号化ランクを設定する。段階２０６では、コンピューティング装置は、前記少なくとも一つの入力値を前記初期暗号化ランクと一緒にエンコードする。段階２０８では、コンピューティング装置は前記計算を実行し、それにより、エンコードされた入力値に対して第一の演算が実行されてエンコードされた結果を生成し、その後の演算が前の演算によって生成されたそれぞれのエンコードされた結果に対して実行されて、さらなるエンコードされた結果を生成する。段階２１０では、前記計算における演算が前記エンコードされた入力値または前の演算によって生成されたエンコードされた結果に対して実行されるときに、コンピューティング装置が新たな暗号化ランクを設定する。それにより、前記計算における前記演算の前記エンコードされた結果が前記新たな暗号化ランクをもつ。段階２１２では、コンピューティング装置は、デコード関数を実行する。デコード関数は、エンコードされた結果があらかじめ定義された値に到達した暗号化ランクをもつ場合にのみ、該エンコードされた結果から使用可能な出力値を提供する。
【００５９】
図３は本発明のある実施形態において実行される段階を示しているが、段階の順序は必ずしも図３に記載されるとおりではないことが理解されるであろう。たとえば、デコード関数を実行する段階は、何らかの入力値が受領される前に、コンピューティング装置の初期のセットアップおよび前記エンコードの一環として実行されることができる。同様に、実行されるべき演算の数を決定する段階は、何らかの入力値が受領される前に実行されることができる。
【００６０】
図４は、安全な計算を実行するためのコンピューティング装置３００を示している。コンピューティング装置３００は、前記少なくとも一つの入力値を初期暗号化ランクと一緒にエンコードするために提供される。入力値についての初期暗号化ランクは、前記計算において実行されるべき演算の数に基づいて設定される。プロセッサ３０６は前記計算における複数の演算を実行する。ここで、エンコードされた入力値に対して第一の演算が実行され、前の演算によって生成されたそれぞれのエンコードされた結果に対してその後の演算が実行されて、さらなるエンコードされた結果を生成する。前記計算におけるある演算が前記エンコードされた入力値または前の演算によって生成されたエンコードされた結果に対して実行されるときに、新たな暗号化ランクが設定される。それにより、前記計算における前記演算の前記エンコードされた結果が前記新たな暗号化ランクをもつ。デコーダ３０８がデコード関数を実行する。デコード関数は、エンコードされた結果があらかじめ定義された値に到達した暗号化ランクをもつ場合にのみ、該エンコードされた結果から使用可能な出力値を提供する。
【００６１】
本稿では方法は値がデータ値である実装において記述されているが、同じ方法は値がアドレス値である応用において適用されることができる。その場合、出力値は、暗号化ランクが0までデクリメントされた場合にのみ、正しいアドレスにマッピングされる有用な値である。
【００６２】
当業者には明確であろうが、本方法を実行する多くの異なる仕方が可能である。たとえば、段階の順序は変更でき、あるいはいくつかの段階が並列に実行されてもよい。さらに、段階と段階の間に、他の方法段階が挿入されてもよい。挿入される段階は、本稿に記載されるような方法の洗練を表わしてもよく、あるいは本方法とは無関係であってもよい。
【００６３】
上述した実施形態は本発明を限定するのではなく例解するものであること、当業者は多くの代替的な実施形態を考案できるであろうことを注意しておくべきである。
【００６４】
請求項において、括弧内に参照符号があったとしてもその請求項を限定すると解釈してはならない。動詞「有する／含む」およびその活用形の使用は、請求項において述べられているもの以外の要素やステップの存在を排除しない。要素の単数形の表現はそのような要素の複数の存在を排除しない。本発明は、いくつかの相異なる要素を有するハードウェアによって、および好適にプログラムされたコンピュータによって実装されうる。いくつかの手段を列挙する装置請求項では、これらの手段のいくつかが同一のハードウェア項目によって具現されてもよい。ある種の施策が互いに異なる従属請求項において記載されているというだけの事実が、これらの施策の組み合わせが有利に使用できないことを示すものではない。
【００６５】
開示されている実施形態への他の変形が、図面、本開示および付属の請求項の吟味から、特許請求される発明を実施する際に当業者によって理解され、実施されることができる。請求項において、「有する／含む」の語は他の要素やステップを排除するものではない。単数表現は複数を排除するものではない。単一のプロセッサまたは他のユニットが請求項において記述されているいくつかの項目の機能を充足してもよい。ある種の施策が互いに異なる従属請求項において記載されているというだけの事実が、これらの施策の組み合わせが有利に使用できないことを示すものではない。コンピュータ・プログラムは、他のハードウェアと一緒にまたは他のハードウェアの一部として供給される光記憶媒体または半導体媒体のような好適な媒体上で記憶／頒布されてもよいが、インターネットまたは他の有線もしくは無線の遠隔通信システムを介してなど他の形で頒布されてもよい。請求項における参照符号は範囲を限定するものと解釈されるべきではない。
【図１】
0006499323.tif 000003
【図２】
0006499323.tif 000004
【図３】
0006499323.tif 000005
【図４】
0006499323.tif 000006