暗号に基づくワンタイムプログラムの実現

代表研究者

1西出 隆志筑波大学

システム情報系准教授

はじめにGoldwasser ら [GKR08] は One-Time Memroy (OTM) と呼ばれるハードウェアデバイスの存在を仮定し Garbled Circuit と組み合わせることで OTP を構成できることを示した。しかしデバイスを OTP実行者に物理的に配布しなければならないという制限がある。北村ら[KSNO17] はデバイスの使用を避けるためクラウドサーバらに OTM内のデータを秘密分散し，データがアクセスされた後に消すことでOTM の機能をクラウドサーバに分散させることを提案した。ここでは [西 19] の内容に基づき [KSNO17] の手法をさらに発展させた方式について報告する。

OTP 関連研究. Gunupudi ら [GT08] は TPM を拡張することで非対話 Oblivious Transfer を実装し，それにより非対話 Garbled Cir-cuit (GC) を実現した。その後 Goldwasser ら [GKR08] は ObliviousTransfer とほぼ同様に動作する One-Time Memory と呼ばれる耐タンパデバイスの存在を仮定し，GC を少し変形して組み合わせることで OTP を実現した。北村ら [KSNO17] は耐タンパデバイスではなくクラウドサーバに OTM の機能を分散させることで [GKR08] と同様に GC を用いて OTP を構成した。Goyal ら [GG17] は Proof-of-Stakeに基づく Blockchain と Witness Encryption [GGSW13] を仮定し，これらから OTM を構成し [GKR08] と同様 GC を用いて OTP を構成し1た 1) 。Zhao ら [ZCD+ 19] は Trusted Execution Environment (TEE)2)の一つ Intex-TXT[Gre12] と TPM[tpm] を用いて OTM を実装し，そして GC と組み合わせることで OTP を実装した。また OTM の実行だけでなくプログラムの実行全体を TEE により保護する方法でのOTP 実装も提案している。
2準備

2.1

Garbled Circuit

Garbled Circuit (GC) は入力を秘匿したままでの計算を可能とする手法 (garbling scheme) である [Yao86]。今，回路族 {Cn }n∈N の Cn の各回路は n bit の入力を受け取る回路とすると garbling scheme GCは以下のアルゴリズムからなる。

Definition 1 (Garbling Scheme GC).
GC.Garble(1λ , C ∈ Cn ) : セキュリティパラメータ λ と回路 C を受け取り，garbled circuit Cgc とラベルと呼ばれる 3) garbled input
(0)

(1)

{ℓi , ℓi }1≤i≤n を出力する。
(x )GC.Eval(Cgc , {ℓi i }1≤i≤n ) : garbled circuit Cgc と入力ビット列 x =(x1 , . . . , xn ) ∈ {0, 1}n に相当するラベルを受け取り C(x) を出力する。

GC.Garble では回路 C はビット列を入力とする論理 (Boolean) 回路として表現されていることを仮定している。
1)

この方式では OTP 実行者は OTP への入力 (あるいは入力への commitment) をBlockchain に書き込む。その後ある程度伸びた条件を満たす Blockchain を Witnessとして利用し，GC を実行するために必要な (ラベルと呼ばれる) 情報を含む Witness

Encryption の暗号文を復号する。ハードウェアに依存しない方式であるが複雑な条件を判定する Witness Encryption を必要としており，現時点では実用レベルにはまだ近く
2)3)ないと考えられる。
これは特別なデバイスではなく CPU が提供する機能であり，ハードウェアの支援によりプログラムの安全な実行環境を実現する。
token また key と呼ばれることもある [GIS+ 10, BHR12]。

2Functionality OTM(0)• On input (Pi , Pj , sid, id, (ℓ, ℓ(1) )) from party Pi , send (Pi , Pj , sid, id) to Pj andstore the tuple (Pi , Pj , sid, id, (ℓ(0) , ℓ(1) )).
• On

receiving(Pi , sid, id, b(∈(0)(Pi , Pj , sid, id, (ℓ, ℓ(1){0, 1}))

fromparty)) exists, return (Pi , sid, id, ℓ(0)the tuple (Pi , Pj , sid, id, (ℓ, ℓ(1)(b)

Pj ,ifatuple) to Pj and delete)). Else, do nothing.

Fig. 1. Ideal Functionality for OTM [GIS+ 10]

本提案では OTP に適した適応的安全性を満たす GC [BHR12] を使うことを想定する。
2.2

Goldwasser らによる OTP 方式 [GKR08]

ここでは Goldwasser による GC と OTM を用いた OTP 方式 GKR を説明する。[GKR08] では OTM と呼ばれる Fig. 1 の機能を提供するハードウェアデバイスを仮定する。
つまり OTM は内部に (ℓ(0) , ℓ(1) ) の 2 つのラベルを持ち，指定された b に対するラベル ℓ(b) を一度だけ返す。この GC と OTM を用いて

[GKR08] では以下のように回路 C ∈ Cn に対する OTP を構成する。
(0)

(1)

1. OTP 作成者 Gotp は GC.Gable(1λ , C) を実行し，Cgc とラベル {ℓi , ℓi }1≤i≤nを得る。
(0)

(1)

2. Gotp はそれぞれのラベルの組 {ℓi , ℓi } を OTMi に埋め込み，⟨Cgc , {OTMi }1≤i≤n ⟩ を C の OTP として OTP 実行者 Eotp に送る。
3. Eotp は入力ビット列 x = (x1 , . . . , xn ) ∈ {0, 1}n に対応するラベル
(x )

(x )

{ℓi i }1≤i≤n を各 OTMi から取得し，GC.Eval(Cgc , {ℓi i }1≤i≤n ) を実行し C(x) を得る。
2.3

Message Authentication Code (MAC)

MAC は次のアルゴリズムの組から構成される。
Definition 2 (Message Authentication Code (MAC)).
3

MAC.KeyGen(1λ ) : セキュリティパラメータ λ を受け取り鍵 k を出力する。ここで k のビット長 |k| ≥ n となっている。

MAC.Mac(k, m) : 鍵 k とメッセージ m ∈ {0, 1}∗ を受け取り，m のMAC tag tag(m) を出力する。
MAC.Vrfy(k, m, tag) : 鍵 k とメッセージ m と MAC tag tag を受け取り，tag が m の正しい MAC tag なら 1 を，そうでなければ 0 を出力する。

3提案方式

3.1

クラウドに基づくワンタイムプログラム (OTP)[KSNO17] は [GKR08] の OTM の機能を複数のクラウドサーバに分散することにより OTP を構成した 4) 。ここでは [KSNO17] の OTP
方式に対し，以下の改良を加える。

• クラウドサーバに保存するラベルのシェアに対して，MAC を付加することにより安全性を高める。

• クラウドサーバ/ユーザ間の Oblivious Transfer を準同型暗号ベースにし，各クラウドサーバとの個別の通信ではなく単に同一のデータをユーザはクラウドサーバらへブロードキャストするだけで各入力ビットに対するラベルを得られるようにする。
(0)

(1)

[KSNO17] では各ラベルのペア (ℓi , ℓi ) を Shamir の秘密分散[Sha79] により分割して各クラウドサーバに渡している。それに基づき回路 C ∈ Cn に対する OTP 作成処理 (Fig. 2) を提案する。
また Eotp による OTP 実行処理を Fig. 3 に記述する。
4)

ここではクラウドサーバが OTM に相当する分散サービスを提供することで OTP 作成者からサービス料金を得るようなモデルを想定している。

4

(0)

(1)

1) Gotp は garbling scheme により Cgc , {ℓi , ℓi }1≤i≤n を得る。またランダムな鍵skC を生成する。
(0)

(1)

(0)

(1)

2) Gotp は (k, m)-秘密分散により，{ℓi , ℓi }1≤i≤n を {ℓi,j , ℓi,j }1≤i≤n,1≤j≤m のシェアに分割する。

3) Gotp は C の各入力ワイヤに ID として wi = H(skC ∥ i) を割り当て (H は適切な(b)(b)

ハッシュ関数)，各ラベルのシェア ℓi,j の MAC tag tag(ℓi,j ) を次のように計算する。
ここで ∥ はビット列の結合を意味する。
(b)

(b)

tag(ℓi,j ) ← MAC.Mac(skC , ℓi,j ∥ wi ∥ b)4) ク ラ ウ ド サ ー バ 群 を {Sj }1≤j≤m{wi ,(0)ℓi,j ,(1)ℓi,j ,(0)tag(ℓi,j ),と す る 。こ の と きGotpはSjに(1)tag(ℓi,j )}1≤i≤n を送る。

5) Gotp は C に対する OTP として ⟨n, skC , Cgc , {Sj }1≤j≤m ⟩ を OTP 実行者 Eotp に渡す。

Fig. 2. OTP 作成処理

3.2

秘密分散 [Sha79] の (k, m) の設定[KSNO17] で既に言及されているように適切な (k, m) の設定がなされない場合は問題が起こりうる。
今あるラベル (ℓ(0) , ℓ(1) ) の秘密分散に (6, 9)-秘密分散が使用されているとする。このとき敵が 6 台のクラウドサーバをコラプトしない限り両方のラベルが敵に得られることはないと通常なら期待する。
しかし実際には次に示すように 3 台のクラウドサーバをコラプトするだけで両方のラベル (ℓ(0) , ℓ(1) ) を敵は得ることができてしまう。

1. Table 1 のように (ℓ(0) , ℓ(1) ) が {Si }1≤i≤9 によって (6, 9)-秘密分散されているとする。
5)

OTP に与える引数 xi をクラウドサーバから秘匿する必要が無い場合は Oblivious Transfer は不要となる。このときは単純に xi に対応するラベルのシェアを要求することでよ6)

り効率的に実行できる。
ここで Sj 内では適切な排他制御により，あるスレッドが wi のデータ組に対する処理を(0)(1)(0)(1)

行っている間，他のスレッドが {wi , ℓi,j , ℓi,j , MAC(ℓi,j ), MAC(ℓi,j )} へアクセスすることが禁止される実装となっていることを仮定する。

5

1) Eotp は加 法 準 同 型暗 号 の 使 い 捨 て 鍵 (pk, sk) を 生 成 す る 。Eotp は x =(x1 , . . . , xn ) ∈ {0, 1}n を入力として OTP を実行するとする。
(x )2) xi に対するラベルのシェア ℓi,ji を得るために Sj (1 ≤ j ≤ m) に対して xi の pkによる暗号文 Epk (xi ) と xi ∈ {0, 1} であることを示すゼロ知識証明 πx を作成
i

し，⟨wi , pk, Epk (xi ), πx ⟩ を Sj (1 ≤ j ≤ m) に対してブロードキャストする。
i3) Sj は wi に対応するデータが無いあるいは πxi が無効な場合は無視する。それ以外の場合は次の Oblivious Transfer に相当する公開鍵 pk での準同型演算を行う
5)。

ci,j ← Epk (1−xi )·ℓi,j +Epk (xi )·ri,j ,(0)

(0)

(0)

mi,j ← Epk (1−xi )·tag(ℓi,j )+Epk (xi )·γi,j(1)(1)

mi,j ← Epk (xi )·tag(ℓi,j )+Epk (1−xi )·γi,j(1)ci,j ← Epk (xi )·ℓi,j +Epk (1−xi )·ri,j ,
ここで

{wi ,

(0)
ℓi,j ,

ri,j ,(0)γi,j ,(1)ℓi,j ,(0)(0)
tag(ℓi,j ),(0)

(0)

(1)

(0)

(1)

(1)

(1)

(1)
γi,j は 乱 数 で あ る 。そ し て Sj は(1)
(0)
(0)
(1)
(1)
tag(ℓi,j )} を削除し 6) ，⟨ci,j , mi,j , ci,j , mi,j ⟩ をri,j ,Eotp へ返信する。
(x )

(x )

(x )

4) Eotp は ci,ji , mi,ji を sk で復号し，tag(ℓi,ji ) が正しいか MAC.Vrfy と skC を使って検証する。

5) MAC tag の検証が正しい場合は，シェアの集合{(x )}ℓi,jij(x )から ℓi i を復元し，(x )GC.Eval(Cgc , {ℓi i }1≤i≤n ) を実行し C(x) を得る。

Fig. 3. OTP 実行処理(b)

2. 敵が S1 , S2 , S3 をコラプトした場合，敵は {ℓi }1≤i≤3,b=0,1 のシェア(灰色部分) を得る。
(1)

3. 敵は S4 , S5 , S6 に対して 1 のラベルのシェアを要求し {ℓi }4≤i≤6 のシェアを得る (灰色部分)。
(0)

4. 敵は S7 , S8 , S9 に対して 0 のラベルのシェアを要求し {ℓi }7≤i≤9 のシェアを得る (灰色部分)。
6S1S2S3S4 S5 S6 S7 S8 S9ℓ(0)

ℓ1(0)

ℓ2(0)

ℓ3(0)

ℓ4(0)

ℓ5(0)

ℓ6(0)

ℓ7(0)

ℓ8(0)

ℓ9(0)

ℓ(1)

ℓ1(1)

ℓ2(1)

ℓ3(1)

ℓ4(1)

ℓ5(1)

ℓ6(1)

ℓ7(1)

ℓ8(1)

ℓ9(1)

Table 1. ラベル ℓ(0) , ℓ(1) の (6, 9)-秘密分散

このようにクラウドサーバ 3 台をコラプト後，残りのクラウドサーバに 0, 1 異なる両方の (不正な) 要求を送ることによって敵は (ℓ(0) , ℓ(1) )のシェアをそれぞれ 6 個集めることができてしまう 7) 。
このように敵に両方のラベルを得られ，OTP を 2 回以上実行されてしまうことを防ぐための適切な (k, m) の設定を求めておく。ここで敵は多くて t 台のクラウドサーバをコラプト可能と仮定する。このとき (k, m) は以下の条件を満たす必要がある。

1. t < k ≤ m
2. m + t < 2k (t 台コラプト後に上記の攻撃により両方のラベルを得られなくするための条件)
よって k = t + α (α ≥ 1) とすると

m < 2k − t = 2t + 2α − t = t + 2αと設定すればよいことになる 8) 。
参考文献
[BHR12]Mihir Bellare, Viet Tung Hoang, and Phillip Rogaway. Adaptively secure
garbling with applications to one-time programs and secure outsourcing. In
Asiacrypt, pages 134–153. Springer, 2012.

[GG17]

Rishab Goyal and Vipul Goyal. Overcoming cryptographic impossibility
results using blockchains. In TCC, pages 529–561. Springer, 2017.

7)

クラウドサーバ間で連携するプロトコルをさらに組み込むことによってこのような攻撃は防ぐことができるかもしれない。しかし実世界への配置を容易とするためにクラウド

8)

サーバ間での通信を不要な設計としている。
よって冗長性を自由に大きくすることはできないというトレードオフが存在する。

7

[GGSW13] Sanjam Garg, Craig Gentry, Amit Sahai, and Brent Waters. Witness encryption and its applications. In STOC, pages 467–476. ACM, 2013.
[GIS+ 10]

Vipul Goyal, Yuval Ishai, Amit Sahai, Ramarathnam Venkatesan, and Akshay Wadia. Founding cryptography on tamper-proof hardware tokens. InTCC, pages 308–326. Springer, 2010.

[GKR08]

Shafi Goldwasser, Yael Tauman Kalai, and Guy N Rothblum. One-time
programs. In CRYPTO, pages 39–56. Springer, 2008.

[Gre12]James Greene. Intel trusted execution technology. Intel Technology White
Paper, 2012.

[GT08]

Vandana Gunupudi and Stephen R Tate. Generalized non-interactive oblivious transfer using count-limited objects with applications to secure mobile agents. In Financial Cryptography and Data Security, pages 98–112.
Springer, 2008.

[KSNO17] Takuya Kitamura, Kazumasa Shinagawa, Takashi Nishide, and Eiji
Okamoto. One-time programs with cloud storage and its application toelectronic money. In ASIA Public-Key Cryptography (APKC), pages 25–30.
ACM, 2017.
How to share a secret.

Communications of the ACM,

[Sha79]Adi Shamir.

[tpm]

Trusted Computing Group (TCG). TPM main specification. Main

22(11):612–613, 1979.
specification, Trusted Computing Group, May 2009.

http://www.

trustedcomputinggroup.org.
[Yao86]

Andrew Yao. How to generate and exchange secrets. In FOCS, pages 162–167. IEEE, 1986.

+[ZCD 19] Lianying Zhao, Joseph I Choi, Didem Demirag, Kevin RB Butler, Mohammad Mannan, Erman Ayday, and Jeremy Clark. One-time programs madepractical. In Financial Cryptography and Data Security, pages xx–xxx.
Springer, 2019.
[西 19]

西出隆志. ワンタイムプログラムとそのシュノア署名への応用. In Technicalreport of IEICE. ISEC 研究会, 3 月, 2019.

8＜発表資料＞
題名

掲載誌・学会名等

発表年月

Outsourced Private Function Evaluation 17th IEEE International Conference on 2018 年 8 月
with Privacy Policy Enforcement

Trust, Security and Privacy in Computing and Communications (TrustCom)

ワンタイムプログラムとそのシュノア署名 Technical report of IEICE, ISEC

2019 年 3 月

への応用
ノンスベースのハイブリッド暗号

Technical report of IEICE, ISEC

92019 年 3 月