時間が経たないと復号できない「タイムロック暗号」の作り方

お知らせ
Table of Content

この記事は https://eprint.iacr.org/2015/482.pdf の紹介記事になります。

タイムロック暗号のモチベーション
1.既存研究:Timed-release encryption[17][66][69]などの欠点

2.以上を踏まえたモチベーション

本論文で示されること
3.Computational reference clock(計算参照クロック)computational model

4.Witness encryption(証人暗号化モデル)

5.それらの応用としてのタイムロック暗号化スキーム

6.SNARKSによる多線型性の低減

既存研究:Timed-release encryption[17][66][69]などの欠点

信頼できる第三者が適切なタイミングで復号鍵を公開する仕組み

→そのタイミングより前に公開されない為に、計算コストの大きい復号鍵の探索をさせる仕組みにすると、第三者の計算コスト甚大。

以上を踏まえたモチベーション

低い計算コストで、全ての受信者が同時に復号できる方法を作りたい!

Computational reference clock(計算参照クロック)computational model

Computational reference clock・・・計算する時に参照するクロック(時間)のことを「計算参照クロック」という

  • 現在の時間=ビットコインブロックチェーンの現在の長さ
  • 時間間隔=新しいブロックが追加されるまでの時間・・・「clock tick」

Witness encryption(証人暗号化モデル)

元ネタは[43]GargS.,GentryC.,SahaiA.,WatersB.:Witnessencryptionanditsapplications.STOC’13,pp.467–476 (2013).

xはstatement,wはwitness
NP関係Rに対し、(x,w) ∈ R を満たす時、x を c ← WE.Enc(x,m)として暗号化でき、wは暗号文cをm = WE.Dec(c, w) と復号できる。

  • Xを公開鍵、wを秘密鍵と捉えられる

  • 安全性の概念はあるものの、証明はされていない。

それらの応用としてのタイムロック暗号化スキーム

  • For x ∈ N、statementsは1xの形式・・・xを単項表現

  • Witness wをBitcoinブロックチェーン(B1,・・・,Bx)とする。初期状態w0を最新のブロックにすれば古い部分を無視できる

  • (1 ,w) ∈ Rとすれば、先の証人暗号化方式が使える!

攻撃パターン

(1)ブロックチェーンの長さがxになるまで待つ・・・「タイムロックが開いた」

(2)秒速約262ハッシュの速さで計算する採掘者よりも早く、計算してブロックの前倒しを行う
早くメッセージを盗み見るインセンティブ<採掘によるインセンティブより攻撃者のモチベーションは0になるはず・・・!

SNARKSによる多線型性の低減

  • 暗号文の大きさ、暗号・復号化の実行時間はwの大きさに線形。
  • 既存の、多線型性に対する効率的なスキームはコンパクトでなく、多線型性の証人暗号化には不適
    →SNARKsの検証手順を用いて暗号化する

参考文献

What is "witness encryption"?
I recently skimmed over tho papers on time-lock encryption: “Time-release Protocol from Bitcoin and Witness Encryption for SAT” by Liu, Garcia, and Ryan “How t...

コメント

タイトルとURLをコピーしました