【研究】Separating Sources for Encryption and Secret Sharing (Y.Dodis, K.Piefrazak, B.Przydatek) [TCC'06]

暗号は多くの場合"一様分布"な乱数を用いて構成されているが，乱数が一様じゃなかった場合どうなるんでしょう．


この論文は，"あまり精度のよくない"乱数を用いてどんなものが使えるか？というテーマに沿って

完全な暗号方式が構成可能なソースからならば，(2,2)閾値型完全秘密分散法が構成可能．しかし逆は必ずしも真でない

ということを示している．

グラフを使って，シェアと値の関係についてわかりやすく表してる．

【研究】Efficient Chosen Ciphertext Secure Public Key Encryption under the Computational Diffie-Hellman Assumption (G.Hanaoka, K.Kurosawa) [ASIACRYPT'08]


CDH仮定からCCA安全なKEMができましたよという話．
というか，BEからのconstructionがメイン？

CCA2-PKEは，実はBEの変形と取ることが出来るのさ…だって．

BroadcastEncryption：
Setup
Revocation
鍵共有

General construction BE→CCA-KEM ではなく，提案されたものから基本的なのを考える．


証明（simulation）の観点から考える．
シミュレータはBEから見るとiさんになる（iさんのprivate keyを持つ．作るんだけどね）．
暗号文は（BEから見ると）常に誰か一人をrevokeするようにしておく．
Aの入力に，（BEの観点で見るとiをrevokeした）暗号文を渡す．
そしてAにDecしてもらう．
本来BはDecできないのがDecできてしまうので，矛盾する．


そして問題のDecオラクルのシミュレーションだが，

  1. validなものはDecする
  2. invalidなものはrejectする


ことが必要．


1についてはBEなので，暗号文でiさんがrevokeされていない限りDecできる．
revokeされる暗号文が作れないように，まず肩の上に乗せることによってわからなくし，且つTCRHFを使ってたまたまiさんをrevokeしてしまうことも無いようにした．


2についてが問題で，BEではそれに関する有効な性質が無かった（invalidな暗号文をbroadcastしても気づけない）．
なので，verifiabilityを追加した．
本スキームではNaor-PinkasのBEにverifiabilityを追加したBE'を提案している．
この性質は簡単に言うと，"自分のDecした結果が他の人と同じかどうかチェックすることができる性質"である．
暗号文がinvalidならば，honestにDecしたときみんなバラバラな結果が出るので，verifiabilityがあると暗号文がvalidかどうかチェックすることができる．
なので，この性質を使い，DecオラクルではDecした後に"verify"することで，invalidな暗号文を見分けることができる，と．




まぁそれだけではDDH仮定になるのですが（実際最初のスキームはDDH），
KEMなので鍵共有が出来ればいい（意味のあるメッセージを共有する必要は無い）ので，
hard-core bitをAに吐き出させることでCDH仮定に落とすことに成功しています，と．


よくまぁ，思いつきますね．
言われてみれば「あぁ，そうか」なんですけど．

【研究】Lossy Trapdoor Functions and Their Applications (Peikert, Waters) [STOC'08]

今更．
Lossy TDFsというプリミティブを提案し，それのblack-box-useでアプリケーションを提案．
DDH，LWH　→　lossy TDFs　→　CPA, CCA, OT, TCRHF…


Lossy TDFsは，practicalに使われる関数はinjectiveだが，証明で使うことができる関数は写像先が小さい（lossy．statisticallyに入力がhidden），しかしその2つの関数はindというもの．


leftover hash lemmaはよく知らんが，どれくらいランダムっぽいbitをextractできるのかだと思っている．
そこらへんを評価すると結局，lossy TDFsに対してfamily of pairwise independent HFがハードコア関数となる．
CPAはそれをgoldreich,levin（だっけ）の方法，つまりメッセージをハードコアとex-orすることでマスク．


CCAについては，strong unforgeable one-time signatureを使って，DECできないcをクエリさせないあの方法．
メッセージはハードコア関数でマスク．
NIZKは使っていなくて，乱数を2つの関数でencryptすることによりcheckする．
このとき，lossy TDFsだけだとDECクエリに答えることが出来ないので（statisticallyにDECできない），ABO TDFs（overwhelmingにinjective，ただしある値でlossy）を使って，lossy TDFsがinjective→lossyとなっても答えられるようにしている．


DDHでのconstructionは，加法準同型なElgamalを使って，
要するにinjective→恒等写像，lossy→0行列をメッセージにかけてしまおうというもの．
しかし，lossyである（出力先空間を小さくする）ためにはもうちょっと工夫が必要で，数あるencryptの乱数部分を共通にしてやってencryptすることで，出力先を2^n→pにしている．

【研究】New Attacks on RSA with Small Secret CRT-Exponents　とか　LLL　とか

RSAのCRT復号に用いるprivate exponent値d_p，d_q

N=pq , ed=1 \hspace{4} mod(p-1)(q-1)
d_p = d \hspace{4}mod (p-1)
d_q = d \hspace{4} mod(q-1)

が偏っている場合の攻撃法と，ビット長が等しくても共に小さい場合のアタック方法の提案．

LLL

いくつも性質があるが，規定ベクトルuで与えられる格子で
最も小さいベクトルbを出せる．

Howgrave-Grahamの定理

要するに，〜〜〜な条件を満たせば，modあり多項式をmod無し多項式に変換することができる．


これらを用いて，

ed_p=1\hspace{2}mod(p-1)
ed_q=1\hspace{2}mod(q-1)

からパラメータkを用いて書き換えて行くと以下になり

ed_pq=(k-1)(N-q)+N
f(x,y)=x(N-y)+N

と考えることにより(x_0,y_0)=(k-1,q)を解くとqが求まりRSA解読可能．

上記の数式に対し，x-shift，y-shiftを行って無理やり多項式数を増やし，LLLを適用するという方針．


１．modなし方程式が2つ作れればf(x,y)を解きqを得て解読可能．
２．modなし多項式の数を保障するためには，Mのxy-shiftのLLL変換ドメインが多項式ノルムにあたるので，それを評価すればいい（Howgrave-Graham）．
３．そしてxy-shiftのLLL変換ドメインの評価は，xy-shiftを見ればよい．


ということで，xy-shiftの評価（具体的にはdet）を考えて，攻撃に成功する値の上限値を求める．


もう１つの攻撃法は略．


detやらパラメータの評価がごちゃごちゃしすぎてわかりにくいな．毎回．

【メモ】firefoxのGoogle検索ボックスをデフォルトで”ウェブ全体を

デフォルトは日本語のページを検索だけど、個人的にすごく不便なのでデフォルトでウェブ全体を検索にして欲しい。

ということで自分でやってみた。

ついでにアイコンも最近のに切り替えてみた。


C:\Program Files\Mozilla Firefox\searchplugins\google-jp.xml

を、

【for　アイコン】
6行目のの後の長い文字列を
data:image/x-icon;base64,AAABAAEAEBAAAAEAIABoBAAAFgAAACgAAAAQAAAAIAAAAAEAIAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAC1tbUFHBwcFQAAABoAAAAaAAAAFgAAAA8AAAAWBAAAGwIAABoAAAAXAAAAGQAAABkAAAAaAAAAGg0NDRiOjo4JJiYmDwAAABQAAAATAAAADQwCAR1YFRB4nCsqua0yLMSbLCyxYxoYfBgFAiwDAQAUAAAAEgAAABMAAAAUBwcHEhQUFA0AAAAOAAAACxMEARayLy%2FF7T9C%2F640K7FuJR1pZiMgYpczMZqeLSzBIAcFPQEBABAAAAANAAAADgAAAA4XFxcJAAAACgAAAABbKSNY%2F1ZO%2F3MdHY8AAAAAAAAAAAAAAAAAAAAAjzc2lHwdG7oDAAAVAAAACAAAAAoAAAAKFxcXBgAAAAcAAAAAVj43Tfx6df87BQFmAQIAAgAAAAQAAAAEAAAAAI0vJomvLCftCwEAHQAAAAQAAAAHAAAABxEREQQAAAAEAAAAAwYEAAi4bVm0uT8%2F4UwOC1wnBgMlFAQAEF4YGmnwQ0X8niQfxQEAAAgAAAADAAAABAAAAAQzMzMCHh4eAh8fHwMAAAAAKSglBJVbWGfQX16qxktJsLItKNTqP0X%2F5DxE8VklJTsAAAAAHx8fAh8fHwIfHx8C7%2B%2FvBO3t7QTt7e0E7e3tBOrr6wIAAAAAAAAAALWHgkH%2BVFD%2FxjI226J1dDYAAAAA7e7uBO3t7QTt7e0E7e3tBP%2F%2F%2Fwn%2F%2F%2F8K%2F%2F%2F%2FCv%2F%2F%2Fwv%2F%2F%2F8Eybi3HHw1LHeySkjC%2Fnd2%2F34iIZ1rbGkJ8fHxCv%2F%2F%2Fwr%2F%2F%2F8K%2F%2F%2F%2FCv%2F%2F%2Fwr%2F%2F%2F8R%2F%2F%2F%2FE%2F%2F%2F%2FxP%2F%2F%2F8P9OTiHtFGSNHPKS%2F%2F15KSeP7k4Evgb3DOXh4cjouJiCD9%2Ff4R%2F%2F%2F%2FE%2F%2F%2F%2FxP%2F%2F%2F8T%2F%2F%2F%2FGf%2F%2F%2Fxv%2F%2F%2F8b%2F%2F%2F%2FDvu3rnbrNCn%2Fo1NTk9%2Fr6wn%2F%2F%2F8C%2F9fXaqskJf9kTUxX7e%2FvGP%2F%2F%2Fxr%2F%2F%2F8b%2F%2F%2F%2FG%2F%2F%2F%2FyH%2F%2F%2F8k%2F%2F%2F%2FJP%2F%2F%2Fxb%2F0MyT00JA%2F5Byblv7%2F%2F8d%2F%2F%2F%2FFv7Ix3XUNjH%2FhFhVee%2Fz8x3%2F%2F%2F8j%2F%2F%2F%2FJP%2F%2F%2FyT%2F%2F%2F8o%2F%2F%2F%2FLf%2F%2F%2Fyz%2F%2F%2F8j%2F%2FDmZNphWv%2BOa2ll4urpJPHy8iLwcWDF0zEn%2B7edm1f%2F%2F%2F8m%2F%2F%2F%2FLP%2F%2F%2Fyz%2F%2F%2F8s%2F%2F%2F%2FMP%2F%2F%2FzX%2F%2F%2F80%2F%2F%2F%2FM%2F%2F%2F%2Fy77u7KoxlhZyrV%2Ff3XSc3Oy7z83%2F7w5NtymioZg5OHgOf%2F%2F%2FzP%2F%2F%2F80%2F%2F%2F%2FNf%2F%2F%2Fyv%2F%2F%2F89%2F%2F%2F%2FOv%2F%2F%2Fzr%2F%2F%2F84%2F%2F%2F%2FM%2F%2FT0m%2F3oaGk%2FbS0uv24ubPujouw2oqIoO3j40r%2F%2F%2F83%2F%2F%2F%2FPP%2F%2F%2FzP%2F%2F%2F8K%2F%2F%2F%2FMf%2F%2F%2Fz7%2F%2F%2F89%2F%2F%2F%2FPf%2F%2F%2Fz3%2F%2F%2F80%2F%2F%2F%2FMf%2F%2F%2FzH%2F%2F%2F8x%2F%2F%2F%2FMf%2F%2F%2FzX%2F%2F%2F88%2F%2F%2F%2FPv%2F%2F%2Fzf%2F%2F%2F8SAAAAAAAAAAAAAAAAI8AAACBAAAAAAAAAEAgAAAYQAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA%3D%3D
にする。


【for　ウェブ全体検索】
10行目をにする




５分でやったからもっとスマートな方法が存在するだろうが動いてるからいいや

【研究】pairingってone-wayなの？

Aspects of Pairing Inversion (Galbraith, Hess, Vercauteren)の一部．


ペアリングは果たして一方向性を持つだろうか．
一方向性と種々の問題との関連性を考える．
結論としては，一方向性を持つのではないかという話．


まず一方向性とは．3つの意味がある．

e~:~\mathbb{G}_1 \times \mathbb{G}_2 \rightarrow \mathbb{G}_T
D_1 \in \mathbb{G}_1
D_2 \in \mathbb{G}_2
z \in \mathbb{G}_T
とすると，

1.Fixed Argument Pairing Inversion 1(以降FAPI-1)
D_2 \leftarrow {\cal A}(D_1,z,e)

2.FAPI-2
D_1 \leftarrow {\cal A}(D_2,z,e)

3.Generalized Pairing Inversion(以降GPI)
D_1,D_2 \leftarrow {\cal A}(z,e)

もちろんFAPIはGPIより難しい．


FAPI-1,2と離散対数問題の関係

FAPI-1 or FAPI-2が難しい　→　\mathbb{G}_T上での離散対数問題が難しい


FAPI-1,2とCDHの関係

\mathbb{G}_1上でのCDHが難しい or \mathbb{G}_2上での… or \mathbb{G}_T（以下略　→　FAPI-1 and FAPI-2が難しい


ちょっとずれるがlemma．

FAPI-1が解けるならば，\phi_1 : \mathbb{G}_T \leftarrow \mathbb{G}_Tを満たすような全ての同型写像\phi_1が計算可能
FAPI-2が解けるならば（以下略


以上の話と，ちょっと逆方向の証明を行って，以下を得る

\mathbb{G}_1 or \mathbb{G}_2 or \mathbb{G}_T上でのCDH問題を解ける
\uparrow
FAPI-1が解ける and FAPI-2が解ける
\updownarrow
FAPI-1が解ける and  \phi_2を計算可能
\updownarrow
FAPI-2が解ける and  \phi_1を計算可能


上の結果に加えて，もし \phi_1, \phi_2が簡単に計算できるならば（e.g. \mathbb{G}_1 = \mathbb{G}_2であればidentity map）
FAPI-1,2 "are" hard under CDH assumption in \mathbb{G}_1,\mathbb{G}_2,\mathbb{G}_T.
と言えるので，一方向性を持ちそうだ．




また，FAPIが解ける→BDH問題が解けるという関係もあるので（正確にはBDHにも2種類あり，それぞれfapi-1,2に対応するが）
conclusionとして，

Inverting\hspace{4}pairing\hspace{4} \Rightarrow\hspace{4} solve\hspace{4} CDH\hspace{4} in\hspace{4} \mathbb{G}_1,\mathbb{G}_2,\mathbb{G}_T
Inverting\hspace{4} pairing\hspace{4} \Rightarrow\hspace{4} solve\hspace{4} BDH

が言える（正確には，下は任意のPairingに言え，上は\mathbb{G}_1,\mathbb{G}_2に依存）
ゆえに一方向性を持つ．



ふう．
どうもpairingの実際の実装を知らないせいなのだが，
全てのpairingが持っている性質を利用した攻撃であれば一方向性を持ちそうだというのはわかった．
だが，実際に実現しているモノが，もっと攻撃に利用しやすい性質を持っている可能性って十分に大きいよね，とか思ってしまうのだが．