図面 (/)

この項目の情報は公開日時点(2017年1月12日)のものです。
また、この項目は機械的に抽出しているため、正しく解析できていない場合があります

図面 (4)

課題・解決手段

データ値の暗号化された表現を使って該データ値の諸変換の安全なシーケンスを実行するシステムが開示される。システムは、入力データ値に変換を適用してその不明化された表現を得る第一の変換手段101を有し、前記不明化された表現はある入力変数に依存する冗長性を含む。システムは、変換を適用して変換された不明化された表現を計算するための第二の変換手段のシーケンス102;110を有する。システムはさらに、最後の不明化された変換されたデータが得られるよう変換を適用する第四の変換手段103を有する。システムは、最後の不明化された変換されたデータおよび前記入力データに依存する変換を適用する第五の変換手段104を有する。

概要

背景

近年、コンピュータ動作をより安全にするために開発がなされている。たとえば、装置はある種のデータを復号することが許容されることがあるが、この能力は他の装置またはユーザーに簡単に移行可能であるべきではない。

ホワイトボックス暗号は、関数評価事前計算された諸ルックアップテーブルによって実行される技術である。この技術は、プログラムのコードへのアクセスをもちうる攻撃者から機能を隠すために使われることができる。それらのルックアップテーブルは、テーブル検索シーケンスが異なる諸ルックアップテーブルを使って実行されるような仕方で設計されてもよい。それらのルックアップテーブルはさらに、相続くテーブル検索の間の中間結果ランダム全単射によってエンコードされるような仕方で設計されてもよい。ホワイトボックス技術はたとえば非特許文献1から知られている。

特許文献1は、暗号学的処理方法において使用するために好適な対応表を生成する方法であって、複数の入力データ項目および出力データ項目を表中に格納することを含み、各入力データ項目は表中で少なくとも一つの出力データ項目と関連付けられるものを開示している。各入力データ項目について、出力データ項目の少なくとも一つが、第一の補助データ項目と、入力データ項目に依存する暗号化された中間データ項目とに符号化関数を適用することによって得られる。

概要

データ値の暗号化された表現を使って該データ値の諸変換の安全なシーケンスを実行するシステムが開示される。システムは、入力データ値に変換を適用してその不明化された表現を得る第一の変換手段101を有し、前記不明化された表現はある入力変数に依存する冗長性を含む。システムは、変換を適用して変換された不明化された表現を計算するための第二の変換手段のシーケンス102;110を有する。システムはさらに、最後の不明化された変換されたデータが得られるよう変換を適用する第四の変換手段103を有する。システムは、最後の不明化された変換されたデータおよび前記入力データに依存する変換を適用する第五の変換手段104を有する。

目的

本発明は、データ値の暗号化された表現を使って、i=1,…,nであるとして、該データ値のn個の変換Tiの安全なシーケンスを実行するシステムであって:
入力データ値w0に変換を適用してw0の不明化された〔難読化された(obfuscated)〕表現(X0,Y0)を得る第一の変換手段であって、前記不明化された表現は入力変数rに依存する冗長性をもつ、手段と;
i=1,…,n−1のそれぞれについて、





のように(Xi-1,Yi-1)から(Xi,Yi)を計算するよう変換





を適用する第二の変換手段と;
wn=G(Xi-1,Yi-1,r)を計算することによってXn-1,Yn-1およびrに依存する変換Gを適用して、変換の前記シーケンスの結果を得る第三の変換手段とを有しており、





であり、
i=0,1,…,nについて(Xi,Yi)=Ψi(wi,σi)であり、Ψiは、(Xi,Yi)と(wi,σi)の間の一対一関係を定義するあらかじめ定義された不明化関数であり、Ψiは(Xi,Yi)=Ψi(wi,σi)となるよう(Xi,σi)の任意の値を(wi,Yi)の値にマッピングする一対一マッピングがあるという条件を満たし;
σ0はrに依存し;
あらかじめ決められた関数Tiおよびgiについてi=1,…,nについてwi=Ti(wi-1)およびσi=gi(σi-1)であり、w1,…,wn-1およびσ0,…,σnは当該システムによって明示的に計算されない、
システムを提供する

効果

実績

技術文献被引用数
0件
牽制数
0件

この技術が所属する分野

ライセンス契約や譲渡などの可能性がある特許掲載中! 開放特許随時追加・更新中 詳しくはこちら

請求項1

データ値の暗号化された表現を使って、i=1,…,nであるとして、該データ値w0のn個の変換Tiの安全なシーケンスを実行するシステムであって:入力データ値w0に変換を適用してw0の不明化された表現(X0,Y0)を得る第一の変換手段であって、前記不明化された表現(X0,Y0)は入力変数rに依存する冗長性をもつ、手段と;i=1,…,n−1のそれぞれについて、のように(Xi-1,Yi-1)から(Xi,Yi)を計算するよう変換を適用する第二の変換手段と;wn=G(Xi-1,Yi-1,r)を計算することによってXn-1,Yn-1およびrに依存する変換Gを適用して、変換の前記シーケンスの帰結を得る第三の変換手段とを有しており、であり、i=0,1,…,nについて(Xi,Yi)=Ψi(wi,σi)であり、Ψiは、(Xi,Yi)と(wi,σi)の間の一対一関係を定義するあらかじめ定義された不明化関数であり、Ψiは(Xi,Yi)=Ψi(wi,σi)となるよう(Xi,σi)の任意の値を(wi,Yi)の値にマッピングする一対一マッピングがあるという条件を満たし;σ0はrに依存し;あらかじめ決められた関数Tiおよびgiについてi=1,…,nについてwi=Ti(wi-1)およびσi=gi(σi-1)であり、前記第一の変換手段、前記第二の変換手段および前記第三の変換手段はw1,…,wn-1およびσ0,…,σnの値を不明化するよう構成されている、システム。

請求項2

前記第三の変換手段は、Xn=un(Xn-1,Yn-1)のような変換unを適用するための第四の変換手段と;wn=F(Xn,r)を計算することによってXnおよびrに依存する変換Fを適用してwnの値を得るための第五の変換手段とを有する、請求項1記載のシステム。

請求項3

i=0,1,…,nについて(Xi,Yi)=Ψi(wi,σi)として定義され、は演算子であり、Ai、Bi、CiおよびDiは演算子に関して線形な演算子であり、演算子AnおよびDnは可逆であり、(u,v)をにマッピングする演算子Eiは可逆であり、ΨiX、ΨiY、φi1、φi2は可逆なマッピングである、請求項1記載のシステム。

請求項4

演算子はビット毎のXOR演算である、請求項3記載のシステム。

請求項5

rはw0に等しい、請求項1記載のシステム。

請求項6

は恒等関数である、請求項1記載のシステム。

請求項7

前記第一、第二および第三の変換手段のうちの少なくとも一つは、少なくとも一つの事前計算されたルックアップテーブルによって実装される、請求項1記載のシステム。

請求項8

データ値の暗号化された表現を使って、i=1,…,nであるとして、該データ値にn個の変換Tiの安全なシーケンスを実行するシステムを提供する方法であって:第一の変換手段を提供し、入力データ値w0に変換を適用してw0の不明化された表現(X0,Y0)を得るよう該第一の変換手段を構成する段階であって、前記不明化された表現(X0,Y0)は入力変数rに依存する冗長性を含む、段階と;第二の変換手段を提供し、i=1,…,n−1のそれぞれについて、のように(Xi-1,Yi-1)から(Xi,Yi)を計算するよう変換を適用するよう該第二の変換手段を構成する段階と;第三の変換手段を提供し、wn=G(Xi-1,Yi-1,r)を計算することによってXn-1,Yn-1およびrに依存する変換Gを適用して、変換の前記シーケンスの帰結を得るよう該第三の変換手段を構成する段階とを含み、であり、i=0,1,…,nについて(Xi,Yi)=Ψi(wi,σi)であり、Ψiは、(Xi,Yi)と(wi,σi)の間の一対一関係を定義するあらかじめ定義された不明化関数であり、Ψiは(Xi,Yi)=Ψi(wi,σi)となるような仕方で(Xi,σi)の任意の値を(wi,Yi)の値にマッピングする一対一マッピングがあるという条件を満たし;σ0はrに依存し;あらかじめ決められた関数Tiおよびgiについてi=1,…,nについてwi=Ti(wi-1)およびσi=gi(σi-1)であり、前記第一の変換手段、前記第二の変換手段および前記第三の変換手段はw1,…,wn-1およびσ0,…,σnの値を不明化するよう構成される、方法。

請求項9

前記第一の変換手段を構成する段階は、w0の値の(X0,Y0)の対応する値へのマッピングを表わす少なくとも一つのルックアップテーブルを計算することを含む、請求項8記載の方法。

請求項10

前記第二の変換手段を構成する段階は、前記関数のうちの少なくとも一つの関数の少なくとも一つのルックアップテーブルを計算することを含み、前記ルックアップテーブルはを計算することによって(Xi-1,Yi-1)の値を(Xi,Yi)の値にマッピングし、Ψi-1inverseはΨi-1の逆関数である、請求項8記載の方法。

請求項11

(XI,Yi)=Ψi(wI,σI)はとして定義され、は演算子であり、Ai、Bi、CiおよびDiは演算子に関して線形な演算子であり、演算子AnおよびDnは可逆であり、(u,v)をにマッピングする演算子Eiは可逆であり、ΨiX、ΨiY、φi1、φi2は可逆なマッピングであり、前記第二の変換手段を構成する段階は、関数のうちの少なくとも一つの関数の少なくとも一つのルックアップテーブルを計算することを含み、前記ルックアップテーブルはを計算することによって(Xi-1,Yi-1)の値を(Xi,Yi)の値にマッピングし、ここで、fiはによって定義される関数を表わし、fi-1inverseはfi-1の逆関数である、請求項8記載の方法。

請求項12

rはw0に等しく、前記第三の変換手段を構成する段階は、関数Gを表わす少なくとも一つのルックアップテーブルを計算することを含み、前記少なくとも一つのルックアップテーブルは(Xi-1,Yi-1,w0)のタプルをwn=G(Xi-1,Yi-1,w0)の対応する値にマッピングする、請求項8記載の方法。

請求項13

データ値の暗号化された表現を使って、i=1,…,nであるとして、該データ値にn個の変換Tiの安全なシーケンスを実行する方法であって:入力データ値w0に変換を適用してw0の不明化された表現(X0,Y0)を得る段階であって、前記不明化された表現は入力変数rに依存する冗長性を含む、段階と;i=1,…,n−1のそれぞれについて、のように(Xi-1,Yi-1)から(Xi,Yi)を計算するよう変換を適用する段階と;wn=G(Xi-1,Yi-1,r)を計算することによってXn-1,Yn-1およびrに依存する変換Gを適用して、変換の前記シーケンスの帰結を得る段階とを含んでおり、であり、i=0,1,…,nについて(Xi,Yi)=Ψi(wi,σi)であり、Ψiは、(Xi,Yi)と(wi,σi)の間の一対一関係を定義するあらかじめ定義された不明化関数であり、Ψiは(Xi,Yi)=Ψi(wi,σi)となるような仕方で(Xi,σi)の任意の値を(wi,Yi)の値にマッピングする一対一マッピングがあるという条件を満たし;σ0はrに依存し;あらかじめ決められた関数Tiおよびgiについてi=1,…,nについてwi=Ti(wi-1)およびσi=gi(σi-1)であり、w1,…,wn-1およびσ0,…,σnは変換を適用する上記の諸段階において不明化される、方法。

請求項14

プロセッサ・システムに請求項7ないし13のうちいずれか一項記載の方法を実行させるための命令を有するコンピュータプログラム

技術分野

0001

本発明はデータ値の暗号化された表現を使ってデータの変換を計算することに関する。

背景技術

0002

近年、コンピュータ動作をより安全にするために開発がなされている。たとえば、装置はある種のデータを復号することが許容されることがあるが、この能力は他の装置またはユーザーに簡単に移行可能であるべきではない。

0003

ホワイトボックス暗号は、関数評価事前計算された諸ルックアップテーブルによって実行される技術である。この技術は、プログラムのコードへのアクセスをもちうる攻撃者から機能を隠すために使われることができる。それらのルックアップテーブルは、テーブル検索シーケンスが異なる諸ルックアップテーブルを使って実行されるような仕方で設計されてもよい。それらのルックアップテーブルはさらに、相続くテーブル検索の間の中間結果ランダム全単射によってエンコードされるような仕方で設計されてもよい。ホワイトボックス技術はたとえば非特許文献1から知られている。

0004

特許文献1は、暗号学的処理方法において使用するために好適な対応表を生成する方法であって、複数の入力データ項目および出力データ項目を表中に格納することを含み、各入力データ項目は表中で少なくとも一つの出力データ項目と関連付けられるものを開示している。各入力データ項目について、出力データ項目の少なくとも一つが、第一の補助データ項目と、入力データ項目に依存する暗号化された中間データ項目とに符号化関数を適用することによって得られる。

0005

米国特許出願公開第2012/0300922A1号

先行技術

0006

S. Chow, P.A. Eisen, H.Johnson, and P.C. van Oorschot、"White-Box Cryptography and anAES Implementation"、Proceeding SAC 2002 Revised Papers from the 9th Annual International Workshop on Selected Areas in Cryptography, pp.250-270, Springer-Verlag London, UK

発明が解決しようとする課題

0007

データの安全な処理を許容するシステムであって、攻撃に対して改善された保護をもつものを有することが有利であろう。

課題を解決するための手段

0008

第一の側面では、本発明は、データ値の暗号化された表現を使って、i=1,…,nであるとして、該データ値のn個の変換Tiの安全なシーケンスを実行するシステムであって:
入力データ値w0に変換を適用してw0の不明化された〔難読化された(obfuscated)〕表現(X0,Y0)を得る第一の変換手段であって、前記不明化された表現は入力変数rに依存する冗長性をもつ、手段と;
i=1,…,n−1のそれぞれについて、

0009

のように(Xi-1,Yi-1)から(Xi,Yi)を計算するよう変換

0010

を適用する第二の変換手段と;
wn=G(Xi-1,Yi-1,r)を計算することによってXn-1,Yn-1およびrに依存する変換Gを適用して、変換の前記シーケンスの結果を得る第三の変換手段とを有しており、

0011

であり、
i=0,1,…,nについて(Xi,Yi)=Ψi(wi,σi)であり、Ψiは、(Xi,Yi)と(wi,σi)の間の一対一関係を定義するあらかじめ定義された不明化関数であり、Ψiは(Xi,Yi)=Ψi(wi,σi)となるよう(Xi,σi)の任意の値を(wi,Yi)の値にマッピングする一対一マッピングがあるという条件を満たし;
σ0はrに依存し;
あらかじめ決められた関数Tiおよびgiについてi=1,…,nについてwi=Ti(wi-1)およびσi=gi(σi-1)であり、w1,…,wn-1およびσ0,…,σnは当該システムによって明示的に計算されない、
システムを提供する。

0012

ここで、演算子Aは、

0013

である場合かつその場合にのみ「演算子

0014

に関して線形である」と考えられる。

0015

このシステムは、入力値を変更してシステム挙動解析することによりシステムの内部のはたらきを解析するのが、より難しくなるという利点がある。たとえば、攻撃者による中間値(たとえば何らかのiについてのXiまたはYi)の変更は状態σnの変更を引き起こしうるからである。このため、第五の変換手段の結果は予測不可能になる。変換F(Xn,r)は、σの期待される値をXnに存在するσに関係する情報と混合するためにrを使うからである。rとXnに存在するσに関係する情報とがσの同じ値に対応しなければ、第五の変換手段の出力は異常になることがあり、このことはシステムを理解するために攻撃者が実行しなければならない解析を複雑にする。

0016

第三の変換手段は、Xn=un(Xn-1,Yn-1)のような変換unを適用するための第四の変換手段と;wn=F(Xn,r)を計算することによって変換Fを適用して前記変換のシーケンスの帰結を得るための第五の変換手段を有していてもよい。ここで、

0017

である。これは効率的な実装を許容する。変換が諸ルックアップテーブルの形で実装される場合、この特徴は低減されたメモリスペースでのルックアップテーブルの実装を許容する。

0018

一例では、i=0,1,…,nについて(Xi,Yi)=Ψi(wi,σi)は次のように定義される。

0019

ここで、

0020

は演算子であり、
Ai、Bi、CiおよびDiは演算子

0021

に関して線形な演算子であり、演算子AnおよびDnは可逆であり、(u,v)を

0022

にマッピングする演算子Eiは可逆であり、
ΨiX、ΨiY、φi1、φi2は可逆なマッピングである。

0023

不明化関数Ψiのこの例はシステムの比較的簡単な設計を提供する。これらの演算子ΨiXおよびΨiYはΨiを置換または実装するために使用されてもよい。この例では、演算子Gは、

0024

が一般に成り立つ場合に演算子

0025

に関して線形であると考えられる。

0026

たとえば、演算子AiおよびDiはすべてのi=0,1,…,nについて可逆な線形演算子である。

0027

たとえば、rはw0に等しい。これは、状態変数σ0がw0に依存することを意味する。入力データw0と状態変数σ0の間の関係は、第一の変換手段によって実装される関係を用いてこの関係を不明化することによって、たとえば値σ0がシステム中の中間結果として計算されないような仕方でルックアップテーブルを使って入力データw0と不明化された表現(X0,Y0)との間の関係を実装することによって、攻撃者に対して不明瞭なままとなりうる。

0028

たとえば、

0029

0030

の計算量よりも小さい計算量をもつ。これは、変換Fが比較的小さな計算量をもつことを許容する。たとえば、

0031

の計算量はnに依存しない。

0032

たとえば、

0033

は恒等関数である。これは、F(Xn,r)を設計するのを簡単にする。σ0の値も、第一の変換手段におけるそのrへの依存性において暗黙的に使われるからである。

0034

たとえば、演算子

0035

ビット毎のXOR演算である。

0036

たとえば、第一、第二、第三、第四および第五の変換手段のうちの少なくとも一つは、ルックアップテーブルにおいて変換された値を見出すよう構成されている。たとえば、第一、第二および第三の変換手段のそれぞれはルックアップテーブルにおいて変換された値を見出すよう構成されている。もう一つの例では、第一、第二、第四および第五の変換手段のそれぞれはルックアップテーブルにおいて変換された値を見出すよう構成されている。これらの例は、ルックアップテーブルがいかなる使用されるアルゴリズムをも隠すことを許容するため、特に安全な実装を許容する。

0037

もう一つの側面は、データ値の暗号化された表現を使って、i=1,…,nであるとして、該データ値にn個の変換Tiの安全なシーケンスを実行するシステムを提供する方法であって:
第一の変換手段を提供し、入力データ値w0に変換を適用してw0の不明化された表現(X0,Y0)を得るよう該第一の変換手段を構成する段階であって、前記不明化された表現(X0,Y0)は入力変数rに依存する冗長性を含む、段階と;
第二の変換手段を提供し、i=1,…,n−1のそれぞれについて、

0038

のように(Xi-1,Yi-1)から(Xi,Yi)を計算するよう変換

0039

を適用するよう該第二の変換手段を構成する段階と;
第四の変換手段を提供し、Xn=un(Xn-1,Yn-1)のような変換unを適用するよう該第四の変換手段を構成する段階と;
第五の変換手段を提供し、wn=F(Xn,r)のように変換Fを適用して前記変換のシーケンスの帰結を得るよう該第五の変換手段を構成する段階であって、

0040

である、段階とを含み、
i=0,1,…,nについて(Xi,Yi)=Ψi(wi,σi)であり、Ψiは、(Xi,Yi)と(wi,σi)の間の一対一関係を定義するあらかじめ定義された不明化関数であり、Ψiは(Xi,Yi)=Ψi(wi,σi)となるような仕方で(Xi,σi)の任意の値を(wi,Yi)の値にマッピングする一対一マッピングがあるという条件を満たし;
σ0はrに依存し;
あらかじめ決められた関数Tiおよびgiについてi=1,…,nについてwi=Ti(wi-1)およびσi=gi(σi-1)であり、
前記第一の変換手段、前記第二の変換手段、前記第四の変換手段および前記第五の変換手段はw1,…,wn-1およびσ0,…,σnの値を不明化するよう構成される、
方法を有する。

0041

この方法は前記システムを生成することを許容する。

0042

前記第二の変換手段を構成する段階は、前記関数

0043

のうちの少なくとも一つの関数の少なくとも一つのルックアップテーブルを計算することを含んでいてもよい。ここで、ルックアップテーブルは

0044

を計算することによって(Xi-1,Yi-1)の値を(Xi,Yi)の値にマッピングする。ここで、Ψi-1inverseはΨi-1の逆関数である。このようにして、ui〔下線付き〕を計算することに関わるアルゴリズム段階が、一つまたは複数のルックアップテーブルに隠されうる。ルックアップテーブルの使用は、上述したホワイトボックス実装を含むさらなる不明化技法を許容する。

0045

あるいはまた、前記第二の変換手段を構成する段階は、関数ui〔下線付き〕のうちの少なくとも一つの関数の少なくとも一つのルックアップテーブルを計算することを含んでいてもよい。ここで、ルックアップテーブルは

0046

を計算することによって(Xi-1,Yi-1)の値を(Xi,Yi)の値にマッピングする。ここで、fiは

0047

によって定義される関数を表わし、fiinverseはfiの逆関数である。このようにして、fi、fiinverseおよびTiを計算することに関わるアルゴリズム段階が、一つまたは複数のルックアップテーブルに隠されうる。ルックアップテーブルの使用は、上述したホワイトボックス実装を含むさらなる不明化技法を許容する。

0048

たとえば、rはw0に等しく、前記第三の変換手段を構成する段階は、関数Gを表わす少なくとも一つのルックアップテーブルを計算することを含む。ここで、前記少なくとも一つのルックアップテーブルは(Xi-1,Yi-1,w0)のタプルをwn=G(Xi-1,Yi-1,w0)の対応する値にマッピングする。関係した例において、第五の変換手段を構成する段階は、関数Fを表わす少なくとも一つのルックアップテーブルを計算することを含む。ここで、前記少なくとも一つのルックアップテーブルは(Xn,w0)のペアをwn=F(Xn,w0)の対応する値にマッピングする。これらの例において、GまたはFを計算することに関わるアルゴリズム段階が、一つまたは複数のルックアップテーブルに隠されうる。ルックアップテーブルの使用は、上述したホワイトボックス実装を含むさらなる不明化技法を許容する。

0049

もう一つの側面によれば、データ値の暗号化された表現を使って、i=1,…,nであるとして、該データ値にn個の変換Tiの安全なシーケンスを実行する方法であって:
入力データ値w0に変換を適用してw0の不明化された表現(X0,Y0)を得る段階であって、前記不明化された表現は入力変数rに依存する冗長性を含む、段階と;
i=1,…,n−1のそれぞれについて、

0050

のように(Xi-1,Yi-1)から(Xi,Yi)を計算するよう変換

0051

を適用する段階と;
wn=G(Xi-1,Yi-1,r)を計算することによってXn-1,Yn-1およびrに依存する変換Gを適用して、変換の前記シーケンスの帰結を得る段階とを含んでおり、

0052

であり、
i=0,1,…,nについて(Xi,Yi)=Ψi(wi,σi)であり、Ψiは、(Xi,Yi)と(wi,σi)の間の一対一関係を定義するあらかじめ定義された不明化関数であり、Ψiは(Xi,Yi)=Ψi(wi,σi)となるような仕方で(Xi,σi)の任意の値を(wi,Yi)の値にマッピングする一対一マッピングがあるという条件を満たし;
σ0はrに依存し;
あらかじめ決められた関数Tiおよびgiについてi=1,…,nについてwi=Ti(wi-1)およびσi=gi(σi-1)であり、
w1,…,wn-1およびσ0,…,σnは変換を適用する上記の諸段階において不明化される、
方法が提供される。

0053

個別的な例では、変換Gを適用する段階は、Xn=un(Xn-1,Yn-1)のような変換unを適用し;wn=F(Xn,r)のように変換Fを適用して前記変換のシーケンスの帰結を得ることを含む。ここで、

0054

である。

0055

もう一つの側面によれば、プロセッサ・システムに上記の方法を実行させるための命令を有するコンピュータ・プログラム・プロダクトが提供される。

0056

業者には、本発明の上記の特徴が有用と見なされる任意の仕方で組み合わされてもよいことが理解されるであろう。さらに、システムに関して記載された修正および変形は方法およびコンピュータ・プログラム・プロダクトに同様に適用されてもよく、方法に関して記載された修正および変形はシステムおよびコンピュータ・プログラム・プロダクトに同様に適用されてもよい。

図面の簡単な説明

0057

下記では、本発明の諸側面が、図面を参照して、例によって明快にされる。図面は図的なものであり、縮尺通りに描かれていない。諸図面を通じて、同様の項目は同じ参照符号で指示されている。
変換のシーケンスを安全に実行するためのシステムのブロック図である。
安全なデータ変換のシーケンスを含む方法を示す図である。
図1に示されるシステムを提供する方法を示す図である。

実施例

0058

多くの用途において、入力データw0に対して変換Tを適用することが必要になる。複雑さの理由または他の理由のため、Tが、変換T1,…,Tnを逐次適用することによって計算されることが望ましいことがある。すなわち、1≦i≦nについて、以下の計算段階
wi=Ti(wi-1)
が実行される。変換T1,…,Tnは、この逐次反復の結果wnがT(w0)と等しいように選ばれる。しかしながら、たとえ悪意のあるユーザーが作業メモリへのアクセスを含め当該装置へのフル・アクセスを有する場合でも、あるいは悪意のあるユーザーがアプリケーションを解析するデバッグ・ツールを使う能力をもつ場合でも、これらの変換において使われるアルゴリズムを隠すこと、および/または中間的な値w1,…,wn-1が悪意のあるユーザーから隠されることが望ましいであろう。

0059

したがって、w1,…,wn-1の値を明示的に計算するのではなく、代替的な値z1,…,zn-1が計算され、その中にそれぞれw1,…,wn-1の値が隠される。z1,…,zn-1の値はw1,…,wn-1よりも多くの情報ビットを含む。値z1,…,zn-1は冗長な状態変数σiの値をも表わすからである。ある好ましい例では、wnの値はznおよびw0から計算される。

0060

以下の説明で使われるいくらか記法を導入しておく。0≦i≦nについて、wiの潜在的な値の集合はWiによって記される。0≦i≦nについて、空でない「状態集合」Σiは状態変数σiの可能な値を含む。自明なものを避けるため、Σ0は少なくとも二つの要素をもつとする。好ましくは、各Σiは少なくとも二つの要素をもち、より好ましくは各Σiは二つより多くの要素をもつ。0≦i≦n−1について、σi+1=gi(σi)を定義するために秘密の「次状態」関数gi:Σi→Σi+1が選ばれる。さらに、σ0=s(w0)となるような秘密の「状態導入」関数s:Wi→Σ0が選ばれる。最後に、0≦i≦nについて、要素数|Wi|・|Σi|の集合Ziおよび秘密の一対一マッピングfi:Wi×Σi→Ziが選ばれる。たとえば、Zi=Wi×Σiである。マッピングfiは、安全なコンピューティング装置によって計算される値ziと(wi,σi)の対応する値との間の関係を記述する。ここで、wiは処理されるデータであり、σiはwiをその表現ziにおいて不明化するのを助ける冗長な状態変数である。

0061

0≦i≦nであるとする。定義により、zi=fi(wi,σi)=fi(Ti(wi-1),gi(σi-1))である。fi-1は可逆なので、wi-1およびσi-1を(wi-1,σi-1)=fi-1inverse(zi-1)として計算することが可能である。結果として、まず(wi-1,σi-1)=fi-1inverse(zi-1)を、次いでzi=fi(wi,σi)=fi(Ti(wi-1),gi(σi-1))を計算することによってzi-1からziを計算することが可能である。この計算は、(wi-1,σi-1)または(wi,σi)の中間値を計算することなく、たとえばziおよび対応するzi-1の値を表にすることによって、あるいはzi-1からziを計算する関数

0062

の別の不明化された計算によって、実行されることができる。ziおよび対応するzi-1、(Xi-1,Yi-1)からの(Xi,Yi)

0063

ziは、0≦i≦nについて、zi=(Xi,Yi)というように二つの成分に分けられていてもよいことを注意しておく。すなわち、wiおよびσiのそれぞれの情報は成分XiおよびYiの両方に分配されてもよい。個別的な例では、Zi=Wi×Σiであり、よってXi∈WiかつYi∈Σiである。あるいはまた、Xiは要素数|Wi|の集合から選択され、Yiは要素数|Σi|の集合から選択される。

0064

計算は、(X0,Y0)=f0(w0,s(w0))を使ってw0からz0=(X0,Y0)を計算することによって開始されてもよい。ここで、s(w0)は入力値w0から状態値σ0を計算する関数を表わす。攻撃者からσ0の値を隠すため、数s(w0)およびf0はたとえばルックアップテーブルにおいて組み合わされてもよい。あるいはまた、σ0の値はw0の代わりに別の入力データ要素rに依存してもよい。

0065

ペアzi=(Xi,Yi)が電子装置によって計算される仕方(上述)のため、これらの値zi=(Xi,Yi)は入力値w0および任意的には追加の入力要素rに依存することになる。同様に、σiの値(電子装置によって計算されないが)はw0および/または任意的に追加的な入力要素rに依存する。

0066

電子装置が上記の仕方でzn=(Xn,Yn)を計算する場合、該電子装置はwn=fninverse(zn)を計算することができる。しかしながら、適正な制約条件があれば、Xnおよびw0から(および/またはσ0がrに依存する場合にはrから)wnを計算することも可能である。この制約条件は次のようなものである:w≠w'として任意の二つの値w∈Wnおよびw'∈Wnおよび任意のσ∈Σnについて、(X,Y)=fn(w,σ)および(X',Y')=fn(w',σ)であるとして、X≠X'が成り立つべきである。この性質が成り立てば、Xnおよびw0のペア(またはXnおよびrのペア)をwnの対応する値にマッピングする変換、たとえばルックアップテーブルを構築することが可能である。そのような場合、Ynを計算することは必要ない。これは、Xiおよび/またはYiを変えることによって電子装置から情報を抽出することをより難しくしうる。

0067

この記述では、fiはΨiによって記されることもある。これらの記述はこの記述では同じ意味をもつ。よって、0≦i≦nについて、(Xi,Yi)=Ψi(wi,σi)である。ここで、Ψiは、(Xi,Yi)と(wi,σi)の間の一対一関係を定義するあらかじめ定義された不明化関数である。Ynの値を必要とすることなくXnおよびσnに基づいてwnを決定できるために、関数Ψnは、(Xn,Yn)=Ψn(wn,σn)となるような仕方で(Xn,σn)の任意の値を(wn,Yn)の値にマッピングする一対一マッピングがあるという条件を満たす。そのような関数は試行錯誤によって設計されうる。

0068

以下では、アルゴリズムのいくつかの構成要素についてより詳細な例が与えられる具体例を記述する。この例では、すべてのiについてWi={0,1}pおよびΣi={0,1}qとなるような正の整数pおよびqがある。さらに、Zi=Wi×Σi={0,1}p×{0,1}qである。これはZi={0,1}p+qと置くことと等価であることを注意しておく。

0069

一層詳細な例では、先の例において選択された集合に加えて、関数fiはfi(wi,σi)=(Xi,Yi)となるよう選択される。ここで、

0070

ここで、

0071

はビット毎のモジュロ演算を示す。Aiは{0,1}pから{0,1}pの上への可逆な線形マッピングである。Diは{0,1}qから{0,1}qの上への可逆な線形マッピングである。Biは{0,1}qから{0,1}pの上への線形マッピングである。Ciは{0,1}pから{0,1}qの上への線形マッピングである。関数の上付き添え字インデックスを表わす。(u,v)を

0072

にマッピングする線形マッピングEiは可逆である。φi1およびΨiXは{0,1}p上での可逆なマッピングであり、これは非線形であってもよい。φi2およびΨiYは{0,1}q上での可逆なマッピングであり、これは非線形であってもよい。p=qの場合、BiおよびCiも可逆であることが好ましい。p≠qの場合には、線形マッピングBiおよびCiに対応する行列はフルの階数をもつことが好ましい。

0073

原理的には、上記の式を使ってzn=(Xn,Yn)からwnの値を計算することが可能である。しかしながら、ある好ましい実施形態では、装置はYnを計算せず、Xnを計算するだけである。その場合、装置はXnおよびw0(あるいは場合によってはr)からwnを計算するよう構成される。

0074

であることを注意しておく。ΨnXは可逆なので、所与のXnから

0075

の値を計算することが可能である。しかしながら、σnはw0(あるいは場合によってはr)から得られうるので、w0(あるいは場合によってはr)からBn(φn2(σn))を計算することが可能である。この情報から、wnが決定されることができる。好ましくは、wnは、この段落で言及した中間結果のいずれも明かすことなく、Xnおよびw0から直接得られる。たとえば、関係が表または複数の表に記憶されていてもよい。たとえばwnの一つまたは複数のビットがw0の全部のビットおよび/またはXnの全部のビットには依存しない場合に、複数の表が使用されうる。

0076

たとえば、

0077

0078

の計算量よりも実質的に小さい計算量をもつ。これは、比較的小さな計算量をもってXnおよびrからwnが計算できることを許容する。たとえば、

0079

の計算量はnに依存しない。

0080

たとえば、

0081

は恒等関数である。これは、F(Xn,r)を設計するのを簡単にする。σ0の値も、第一の変換手段におけるそのrへの依存性において暗黙的に使われるからである。

0082

図1は、変換の安全なシーケンスを実行するためのシステムの実施形態を示している。図面において、いくつかの処理手段が長方形によって表わされており、時に長方形内に本稿で使われる対応する記号をもつ。さらに、データ要素はその変数記号および所与の長さのビット・シーケンスを象徴する描かれた配列によって示されている。しかしながら、各データ要素のビット・シーケンスの実際の長さは変えられてもよい。図面はデータ要素の実際の長さを示すものではない。システムは、適正にプログラムされたコンピュータ、スマートフォンまたはスマートカードのような単一の処理装置上で実装されてもよい。システムは、いくつかの異なる処理装置上に分散されてもよい。

0083

システムは、入力データ値w0を決定するためのデータ入力ユニット111を有する。たとえば、入力ユニット111は、装置の通信サブシステムを介して入力データ値を受領するよう構成される。あるいはまた、入力ユニット111は、内部メモリまたは外部メモリでありうるメモリから入力データ値を受領するよう構成されていてもよい。システムはさらに、入力データ値w0に変換を適用して(X0,Y0)=f0(w0,s(w0))のようにw0の不明化された表現(X0,Y0)を得る第一の変換手段101を有する。個別的な例では、w0、σ0=s(w0)、X0およびY0はみな同じビット数をもつデータ値である。

0084

システムはさらに、第二の変換手段102を有する。第二の変換手段102は一つまたは複数のさらなる変換手段110を有する。さらなる変換手段110は、i=1,…,n−1として、iの特定の値について

0085

を実装する。第二の変換手段102は、一つまたは複数の反復工程において前記の不明化されたデータに前記さらなる変換手段110を適用するよう構成されている。より具体的には、前記さらなる変換手段110はi=1,…,n−1について、

0086

を計算する。ここで、nは実行されるべき変換の数である。前記さらなる変換手段110は各反復工程において異なる演算を実行してもよいことは理解されるであろう。すなわち、

0087

は各i=1,…,n−1について異なる演算であってもよい。しかしながら、

0088

の一部または全部が同一の演算であることができるので、これは制限ではない。

0089

システムはさらに、wn=G(Xn-1,Yn-1,r)を計算することによってXn-1,Yn-1およびrに依存する変換Gを適用して、変換の前記シーケンスの帰結を得る第三の変換手段を有している。ここで、

0090

である。ここで、GはG(Xn-1,Yn-1,r)=F(un(Xn-1,Yn-1),r)として定義される。図1に示した例示的実施形態では、第三の変換手段は第四の変換手段103および第五の変換手段104の組み合わせとして実装される。

0091

第四の変換手段103はXn=un(Xn-1,Yn-1)となるよう変換unを使ってXnを計算するよう構成されている。こうして、Ynの計算は省略されうる。

0092

第五の変換手段104は、wn=F(Xn,w0)のように関数Fを使ってwnを計算するために、第四の変換手段103からの値Xnと、値w0とを受領するよう構成されている。たとえば、第五の変換手段104は値w0をデータ入力ユニット111から受領する。

0093

システムはさらに、第五の変換手段104からwnの計算された値を受領して、wnの該値をシステムの他のコンポーネント(図示せず)に転送するおよび/またはwnの該値をメモリに記憶するよう構成された出力ユニット112を有する。たとえば、出力ユニット112は、データwnの視覚化表示装置上に表示するおよび/または該データをオーディオ装置上で再生するよう構成されていてもよい。

0094

個別的な例では、前記第二の変換手段102、前記さらなる変換手段110の一つまたは複数および/または前記第四の変換手段はさらなるオペランド値(単数または複数)を外部源からまたはシステムの別の計算ユニットから受領してもよい。そのような場合、たとえば、関数

0095

0096

の形をもつ。ここで、(X',Y')は状態パラメータσ'をもつ別のデータ要素w'の不明化された表現を表わす。この不明化された表現は本稿で記載されるものと同様の形を有していてもよい。あるいはまた、前記さらなるオペランド値(単数または複数)は平文で提供されてもよい。すなわち、

0097

は、w'は不明化されていないさらなるデータ要素であるとして、

0098

の形を有していてもよい。

0099

図1に示されるシステムの個別的な変形では、第一の変換手段101はさらなるパラメータr(図示せず)を受領するよう構成されていてもよく、w0の不明化された表現(X0,Y0)における冗長性は上記で説明したように入力変数rに依存してもよい。そのような場合、同じさらなるパラメータrが第三の変換ユニットおよび/または第五の変換ユニット104にも提供され、それによりたとえば第五の変換ユニット104はXnおよびrの両方に依存してwnの値を計算することができる。

0100

前記第一の変換手段101、前記第二の変換手段102、前記第三の変換手段、前記第四の変換手段103および/または前記第五の変換手段104はルックアップテーブルによって実装されてもよいことを注意しておく。たとえば、前記第一の変換手段101、前記第二の変換手段102の前記さらなる変換手段110、前記第四の変換手段103および/または前記第五の変換手段104がそれぞれ単一のルックアップテーブルによって実装されてもよい。あるいはまた、前記変換のうちの一つを一緒に実装するよう前記変換手段の一つによって協働して適用されるよう設計された複数のルックアップテーブルを使うことが可能である。任意的には、これらのルックアップテーブルは、たとえばChow et al.から知られる技法を使ってルックアップテーブルの入力および出力をエンコードすることによってさらに不明化されてもよい。ルックアップテーブルは、隠されたままであるべきである中間結果を明かすことなくいかにして変換が実行できるかの例である。該中間結果はたとえば、i=0,…,nについてのσiの値であり、特に前記第一および第五の変換手段において(あるいはより一般には前記第一および第三の変換手段)役割を演じるσ0である。

0101

図2は、データ値の暗号化された表現を使って、i=1,…,nであるとして、該データ値にn個の変換Tiの安全なシーケンスを実行する方法を示している。本方法は、入力データ値w0に変換を適用してw0の不明化された表現(X0,Y0)を得る段階201を含む。前記不明化された表現(X0,Y0)は入力変数rに依存する冗長性を含む。

0102

次に、段階206において、i=1と置くことによりインデックス値iが初期化される。

0103

次に、本方法は、

0104

のように(Xi-1,Yi-1)から(Xi,Yi)を計算するよう変換

0105

を適用する段階202を進める。該変換を適用後、iが1だけ増加させられる。

0106

次に、本方法は、i=nかどうかを検査することによって反復処理が完了したかどうかを検証する段階203を進める。i≠nであれば、本方法はiの更新された値を用いて段階202を繰り返す。

0107

段階203においてi=nであれば、本方法はXn=un(Xn-1,Yn-1)のように変換unを適用する段階204を進める。次に、本方法は、wn=F(Xn,r)のように変換Fを適用して変換の前記シーケンスの帰結を得る段階205を進める。ここで、

0108

である。段階204および段階205は単一の段階に組み合わされてもよいことを注意しておく。

0109

上記の方法において、記号はいくつかの例において本稿で上記に説明したとおりである。

0110

たとえば、i=1,…,nについて、

0111

であり、

0112

は演算子であり、
Ai、Bi、CiおよびDiは演算子

0113

に関して線形な演算子であり、演算子AiおよびDiは可逆であり、(u,v)を

0114

にマッピングする演算子Eiは可逆であり、
ΨiX、ΨiY、φi1、φi2は可逆なマッピングであり、
σ0はrに依存し、
あらかじめ決められた関数Tiおよびgiについてi=1,…,nについてwi=Ti(wi-1)およびσi=gi(σi-1)である。ここで、w1,…,wn-1およびσ0,…,σnはシステムによって明示的に計算されない。

0115

図3は、データ値の暗号化された表現を使って、i=1,…,nであるとして、該データ値にn個の変換Tiの安全なシーケンスを実行するシステムを提供する方法を示している。

0116

本方法は、第一の変換手段101を提供し、入力データ値w0に変換を適用してw0の不明化された表現(X0,Y0)を得るよう該第一の変換手段201を構成する段階301で始まる。前記不明化された表現(X0,Y0)は入力変数rに依存する冗長性を含む。

0117

本方法は、第二の変換手段102を提供することを段階302において進める。段階311では、iはi=1と設定することによってインデックス値iが初期化される。次に、段階310において、前記第二の変換手段102にさらなる変換手段110が含められる。このさらなる変換手段110は、

0118

のように(Xi-1,Yi-1)から(Xi,Yi)を計算するよう変換

0119

を適用するよう構成される。その後、インデックス値iがインクリメントされる。段階312では、i=nであるかどうかが検査される。段階312においてi≠nであれば、本方法はiの更新された値を用いて段階310を繰り返す。

0120

段階312においてi=nであれば、本方法は、第四の変換手段を提供し、Xn=un(Xn-1,Yn-1)のような変換unを適用するよう該第四の変換手段を構成する段階303を進める。

0121

次に、段階304において、本方法は、第五の変換手段を提供し、wn=F(Xn,r)のように変換Fを適用して前記変換のシーケンスの帰結を得るよう該第五の変換手段を構成することを進める。ここで、

0122

である。

0123

段階303および304は、上記で説明したような変換Gを適用する第三の変換手段が提供されるように組み合わされてもよい。

0124

これらの方法段階は、前記第一の変換手段、前記第二の変換手段、前記第四の変換手段および前記第五の変換手段がw1,…,wn-1およびσ0,…,σnの値を不明化するよう構成されるように実行される。特に、前記第一の変換手段101および前記第五の変換手段104は、たとえばXnおよびrに基づいて(あるいはXnおよびw0に基づいて)最終結果wnを直接生成する計算中のショートカットを作り出すことによって、rに(あるいは上記で説明したようにw0に)依存するσ0の値を不明化するよう構成される。

0125

そのような不明化の個別的な例が、最も脆弱な諸変換について諸ルックアップテーブルを提供することによって与えられる。たとえば、前記第二の変換手段を構成する段階302は、前記関数

0126

のうちの少なくとも一つの関数の少なくとも一つのルックアップテーブルを計算することを含んでいてもよい。ここで、ルックアップテーブルは(Xi-1,Yi-1)の値を(Xi,Yi)の値にマッピングする。このルックアップテーブルは、(Xi-1,Yi-1)の適切な値について、

0127

を計算することによって計算されてもよい。ここで、fiは

0128

によって定義される関数を表わし、fiinverseはfiの逆関数である。これら上記の式において、Tiはfi-1inverseの成分wiのみを使い、giはfiinverseの成分σiのみを使う。

0129

前記第四の変換は、

0130

として、上記と同様のルックアップテーブルを含んでいてもよい。ここで、Tiはfn-1inverseの成分wn-1のみを使い、Ynの出力値は省略される。

0131

もう一つの例として、r=w0である個別的な例において、前記第一の変換を構成する段階301は、w0の値を(X0,Y0)の対応する値にマッピングする関数のルックアップテーブルを提供することを含んでいてもよい。この関係は、上記のように、(X0,Y0)=Ψ0(w0,s(w0))によって与えられてもよい。ここで、s(w0)は、w0の値をσ0にマッピングする秘密のマッピングである。表にされたw0の値および(X0,Y0)の対応する値を提供することによって、システムはσ0の値を計算することなく変換を適用しうる。

0132

上記のより個別的な例によれば、第一の変換手段のルックアップテーブルによって実装される関係は次式によって与えられてもよい。

0133

r=w0であるもう一つの例では、前記第五の変換を構成する段階304は、関数Fのルックアップテーブルを提供することを含んでいてもよい。この表は(Xn,w0)のペアをwn=F(Xn,w0)の対応する値にマッピングしてもよい。

0134

rがw0とは別個の異なる入力値である場合について同様の表が用意されてもよい。

0135

データ値の暗号化された表現を使って該データ値の諸変換の安全なシーケンスを実行するシステムが提供されてもよい。システムは、入力データ値に変換を適用してその不明化された表現を得る第一の変換手段を有し、前記不明化された表現はある入力変数に依存する冗長性を含む。システムは、変換を適用して変換された不明化された表現を計算するための第二の変換手段のシーケンスを有する。システムはさらに、最後の不明化された変換されたデータが得られるよう変換を適用する第四の変換手段を有する。システムは、最後の不明化された変換されたデータおよび前記入力データに依存する変換を適用する第五の変換手段を有する。

0136

本発明の一部または全部の側面は、ソフトウェア、特にコンピュータ・プログラム・プロダクトの形で実装されるのに好適でありうる。そのようなコンピュータ・プログラム・プロダクトはソフトウェアが記憶されている記憶媒体を含みうる。そのような記憶媒体は、たとえば光ディスク磁気ディスクまたはフラッシュ・メモリを含んでいてもよい。また、コンピュータ・プログラムは、光ファイバーケーブルまたは空気のような伝送媒体によって搬送される光信号または電磁信号のような信号によって表現されてもよい。コンピュータ・プログラムは部分的にまたは完全に、コンピュータ・システムによって実行されるのに好適な、ソース・コード、オブジェクト・コードまたは擬似コードの形をもちうる。たとえば、コードは、一つまたは複数のプロセッサによって直接実行可能であってもよい。あるいはまた、コードは一つまたは複数のプロセッサによって実行されるインタープリタによってインタープリットされてもよい。本稿に記載されるシステムの諸部分がソフトウェアの形で実装されてもよいことは理解されるであろう。さらに、本稿に記載される方法段階は、部分的または完全にソフトウェアで実装されてもよい。ソフトウェアは、サブルーチンによって編成されてもよい。サブルーチンは、スタンドアローンの実行可能なプログラムをなすよう組み合わされてもよい。あるいはまた、サブルーチンは動的にリンク可能なライブラリとして編成されてもよい。該動的にリンク可能なライブラリからのサブルーチンを使うメインプログラム実行可能ファイルが提供されてもよい。本稿に記載される処理段階および/またはシステム・コンポーネントのそれぞれは、それが動的にリンクされるライブラリにあってもあるいは実行可能ファイルにあっても、実行可能コードによって表現されてもよい。機能の一部または全部がオペレーティング・システムの一部として実装されてもよく、何らかの機能が動的にリンクされるライブラリにおいて実装されてもよく、何らかの機能がアプリケーション・プログラム・ファイルとして実装されてもよい。

0137

本稿に記載される例および実施形態は、本発明を限定するのではなく例解するはたらきをする。当業者は、請求項の範囲から外れることなく、代替的な実施形態を設計できるであろう。請求項において括弧に入れた参照符号があったとしても請求項の範囲を限定するものと解釈してはならない。請求項または明細書において別個のエンティティとして記述される項目が、記載される諸項目の特徴を組み合わせる単一のハードウェアまたはソフトウェア項目として実装されてもよい。

ページトップへ

この技術を出願した法人

この技術を発明した人物

ページトップへ

関連する挑戦したい社会課題

関連する公募課題

ページトップへ

おススメ サービス

おススメ astavisionコンテンツ

新着 最近 公開された関連が強い技術

この 技術と関連性が強い技術

関連性が強い 技術一覧

この 技術と関連性が強い人物

関連性が強い人物一覧

この 技術と関連する社会課題

関連する挑戦したい社会課題一覧

この 技術と関連する公募課題

関連する公募課題一覧

astavision 新着記事

サイト情報について

本サービスは、国が公開している情報(公開特許公報、特許整理標準化データ等)を元に構成されています。出典元のデータには一部間違いやノイズがあり、情報の正確さについては保証致しかねます。また一時的に、各データの収録範囲や更新周期によって、一部の情報が正しく表示されないことがございます。当サイトの情報を元にした諸問題、不利益等について当方は何ら責任を負いかねることを予めご承知おきのほど宜しくお願い申し上げます。

主たる情報の出典

特許情報…特許整理標準化データ(XML編)、公開特許公報、特許公報、審決公報、Patent Map Guidance System データ