186(lab)

2008-07-26

リング署名のサーベイ 22:31

なんかデスクトップにおいてあったので書いておく. まだ大量にあるからなぁ. 網羅できる気がしない.

http://icsd.i2r.a-star.edu.sg/staff/guilin/bible/group-sign.htm

Group Sig. and Ring Sig.

CRYPTO, EURO, ASIA,

PKC

INDOCRYPT

CCS, CANS, ACNS, ACISP, SAC


?

  • (CRYPTO 2002) E. Bresson, J. Stern, M. Szydlo. "Threshold Ring Signatures and Applications to Ad-hoc Groups."
  • (CRYPTO 2002) M. Naor. "Deniable Ring Authentication."
  • (PKC 2007) E. Fujisaki, K.Suzuki. "Traceable Ring Signature."
  • (ACNS 2003) Chong-zhi Gao, Zheng-an Yao, Lei Li: "A Ring Signature Scheme Based on the Nyberg-Rueppel Signature Scheme."
  • (ACNS 2004) Willy Susilo, Yi Mu: "Deniable Ring Authentication Revisited."
  • (ACNS 2005) Sherman S. M. Chow, Siu-Ming Yiu, Lucas Chi Kwong Hui: "Efficient Identity Based Ring Signature."
  • (ACISP 2007) Cheng-Kang Chu, Wen-Guey Tzeng: "Identity-Committable Signatures and Their Extension to Group-Oriented Ring Signatures."
  • (ASIACCS 2007) Reihaneh Safavi-Naini, Shuhong Wang, Yvo Desmedt: "Unconditionally secure ring authentication."
  • (ASIACCS 2007, Short Paper) Kazuki Yoneyama, Kazuo Ohta: "Ring signatures: universally composable definitions and constructions."
  • (INDOCRYPT 2003) Javier Herranz, German Saez: "Forking Lemmas for Ring Signature Schemes."
  • (INDOCRYPT 2006) Man Ho Au, Joseph K. Liu, Willy Susilo, Tsz Hon Yuen: "Constant-Size ID-Based Linkable and Revocable-iff-Linked Ring Signature."
  • M. Abe, M. Ohkubo, and K. Suzuki. 1-out-of-n signatures from a variety of keys. In: ASIACRYPT 2002


  • Ring Sig. in Standard Model (with PKI)
    • (ASIACCS 2006) Sherman S. M. Chow, Victor K.-W. Wei, Joseph K. Liu, Tsz Hon Yuen: "Ring signatures without random oracles."
    • (TCC 2006) A. Bender, J. Katz, R. Morselli. "Ring Signatures: Stronger Definitions, and Constructions without Random Oracles."
  • (PKC 2007?) H. Shacham, B. Waters. "Efficient Ring Signatures without Random Oracles."
  • Ring Sig in ROM
    • (ASIACRYPT 2001) R. L. Rivest, A. Shamir, Y. Tauman. "How to Leak a Secret."
    • (IEIEC Trans. on FECCS, 2006-01) R. Hayashi, K. Tanaka. "Schemes for Encryption with Anonymity and Ring Signature."
    • (IWSEC 2006) Kazuki Yoneyama, Yoshikazu Hanatani, Bagus Santoso, Kazuo Ohta. "Universally Composable Ring Signature."
    • (IWSEC 2006) Ring Signature with Designated Linkability,

Joseph K. Liu, Willy Susilo, Duncan S. Wong,


  • ID-Based Ring Sig.
    • (ASIACRYPT 2002) F. Zhang, K. Kim. "ID-Based Blind Signature and Ring Signature from Pairings."
    • (ePrint 2003/117) C.-Y. Lin, T.-C. Wu. "An identity-based ring signature scheme from bilinear pairings."
  • (IWSEC 2006) Man Ho Au, Joseph K. Liu, Tsz Hon Yuen, Duncan S. Wong. "ID-Based Ring Signature Scheme Secure in the Standard Model."
  • Threshold Ring Sig.
    • (INDOCRYPT 2004) Patrick P. Tsang, Victor K. Wei, Tony K. Chan, Man Ho Au, Joseph K. Liu, Duncan S. Wong: "Separable Linkable Threshold Ring Signatures."
    • (ACISP 2005) T. Isshiki, K. Tanaka. "An (n-t)-out-of-n Threshold Ring Signature Scheme."
  • Others.
    • (IWSEC 2006) Qianhong Wu, Willy Susilo, Yi Mu, Fangguo Zhang. "Ad Hoc Group Signatures."
    • (ACISP 2004) Joseph K. Liu, Victor K. Wei, Duncan S. Wong: "Linkable Spontaneous Anonymous Group Signature for Ad Hoc Groups (Extended Abstract)."


A. Bender, J. Katz, R. Morselli, “Ring Signatures: Stronger Definitions, and Constructions without Random Oracles” (TCC 2006)

Anonymity
Basic anonymity
署名オラクルへの入力は(R,s,M). ただしRはSの部分集合かつRはpk_sを含む. Aは(R,i_0,i_1,M)をチャレンジとしてクエリする. SIGN(R, i_b, M)が返ってくる.
Anonymity w.r.t. adversarially-chosen keys
署名オラクルへの入力は(R,s,M). ただしRはpk_sを含む (RはSの部分集合でなくてもよい). Aは(R,i_0,i_1,M)をチャレンジとしてクエリする. SIGN(R, i_b, M)が返ってくる.
Anonymity against attribution attacs/full key exposure
署名オラクルへの入力は(R,s,M). ただしRはpk_sを含む (RはSの部分集合でなくてもよい). 更に敵による攻撃としてコラプションを考える. CORRオラクルへの入力はi. 鍵生成に用いた乱数が返ってくる. Aは(R,i_0,i_1,M)をチャレンジとしてクエリする. SIGN(R, i_b, M)が返ってくる. (ただし敵はi_0かi_1の両方をCorruptしてはいけない.)

i_0とi_1の両方をcorruptしてもいい版は?

Linkabilityについても議論あり.
Unforgeability
Unforgeability against fixed-ring attacks
敵の初期入力はRのみ. 署名オラクルへの入力は(s,M). Rは固定. 敵は(M,σ)を出力. (*,M)を今までSIGNにきいていなかったら勝ち.
Unforgeability against chosen-subring attacks
敵の初期入力はS. 署名オラクルへの入力は(R,s,M). ただしRはSの部分集合かつRはpk_sを含む. 敵は(R,M,σ)を出力. RがSの部分集合かつ(*,M,R)を今までSIGNにきいていなかったら勝ち.
Unforgeability w.r.t. insider corruption
敵の初期入力はS. 署名オラクルへの入力は(R,s,M). ただしRはpk_sを含む (RはSの部分集合でなくてもよい). CORRオラクルへの入力はiで秘密鍵が返ってくる. 敵は(R,M,σ)を出力. RはcorruptされておらずSの部分集合で, (*,M,R)を今までSIGNにきいていなかったら勝ち.

こっちだと何故か乱数を返さない.

仕事
  • Separationの構成
  • 一般的な仮定からのリング署名の構成
    • 必要なのは以下
      • IND-CPA安全な公開鍵暗号
      • EUF-ACMA安全なデジタル署名
      • ZAPはややこしいので略す. ただこの所為で暗号がPPKを持たないといけないような気がする.
  • 二人用リング署名の構成 (検証者指定署名の構成?)
    • Waters署名を元にしたもの
    • Camenisch-Lysyanskaya署名を元にしたもの

H. Shacham, B. Waters “Efficient Ring Signatures without Random Oracles” (PKC 2007?)

位数N=pqの群GとG_Tを使用. Pairing:G*G→G_Tも使用.

G_pとG_qを位数pとqのGの部分群とする.

  • G_p上のCDH仮定
  • SGH仮定: Gのランダムな要素とG_qのランダムな要素を見分けられない

の二つを利用.

G_p上でのWaters署名を使う. (これはG_p上のCDH仮定の元でEUF-CMA安全.)

定義.

Anonymity against full key exposureを使うが定義が微妙に違う.

Aは(R,i_0,i_1,M)をチャレンジとしてクエリする. (RはSの部分集合でなくてもよい)

SIGN(R, i_b, M)が返ってくる.

ついでにS全員の乱数が返ってくる.

何で乱数を見てから決めちゃいけないの?

UnforgeabilityはUnforgeability w.r.t. insider corruptionを使う.


仕事
  • 先ほどのBKMの二人用リング署名に対してinsider corruptionの元で攻撃
  • リング署名の構成
    • SGH仮定のもとで匿名性
    • G_p上のCDH仮定の元で安全
    • ランダムオラクルは無し. ただしTrusted setup model.

2008-07-25

発表の後始末 23:11

MCMCの方で分布の収束速度が議論されていることを確認 (total variation distanceらしい. 訳は統計的距離でいいのか?). 一様エルゴード収束すれば初期値に依存せずn回の試行で定常分布との統計的距離がMr^n以下になるんだとか.

証明するには適当な初期値の集合と適当な確率分布を持ってきて, 適当な回数 (m回) 回すと初期値に依存しないことを示せばよいらしいって, あんまり難しさ変わってないんじゃねーのか, これ.


nihen vs HiromitsuTakagi 21:26

ブックマークのコメント欄でコメントの応酬されても追えない(;´Д`). 一時的にb:id:nihenをお気に入りに追加. 転載. 今日のところはここまで.

nihenって弐編のことか.

----

続・bloggersによるIPアドレス開示に関する論点整理 - BI@K accelerated: hatena annex, bewaad.com

http://b.hatena.ne.jp/entry/http://d.hatena.ne.jp/bewaad/20080721/p1

HiromitsuTakagi/2008年07月25日

[法律][電気通信事業法]無茶苦茶な理屈 >「はてなユーザは電気通信事業者であるはてなによってIPアドレスを取得できるのですから」< そんなことを言ったら自分の電話で聞いた情報が全部「電気通信事業者の取扱中に係る通信」になってしまう。

----

続・bloggersによるIPアドレス開示に関する論点整理 - BI@K accelerated: hatena annex, bewaad.com

http://b.hatena.ne.jp/entry/http://d.hatena.ne.jp/bewaad/20080721/p1

nihen/2008年07月25日

[通信の秘密]blog主は通信当事者ではないです…http://d.hatena.ne.jp/nihen/20080720/1216587523 / id:HiromitsuTakagi自分の電話が「電気通信事業者の取扱中に係る通信」なのはそのとおりですよ。一方当事者の同意で秘密は放棄できるだけです

----

はてなブックマーク - nihenのブックマーク / 2008年07月25日

http://b.hatena.ne.jp/nihen/20080725#bookmark-9424130

HiromitsuTakagi

[法律][電気通信事業法]「blog主は通信当事者ではないです」< 誰がそんなこと決めたんだ?あなたがそういう仕様のblogを運営することも可能だというだけで、何人も、blog主が通信当事者となるblogを運営する自由があり、判例はそれを否定しない。

----

はてなブックマーク - nihenのブックマーク / 2008年07月25日

http://b.hatena.ne.jp/nihen/20080725?1#bookmark-9424130

HiromitsuTakagi

[法律][電気通信事業法]「自分の電話が「電気通信事業者の取扱中に係る通信」なのはそのとおりですよ。一方当事者の同意で秘密は放棄できるだけです」< 出鱈目。根拠を示してみろ。/ 早く根拠示せよ。

----

はてなブックマーク - nihenのブックマーク / 2008年07月25日

http://b.hatena.ne.jp/nihen/20080725#bookmark-9428055

HiromitsuTakagi

[ゴミ]何の根拠にもなっていない。家庭だろうが公衆電話だろうが、自分の電話で聞いた情報が「電気通信事業者の取扱中に係る通信」なわけがない。早く根拠を示せよ。

----

はてなブックマーク - nihenのブックマーク / 2008年07月25日

http://b.hatena.ne.jp/nihen/20080725#bookmark-9428055

nihen

id:HiromitsuTakagi http://tinyurl.com/577ehoの2.2.2には「利用者の家庭内にある電話線を流れる通信や、...、事業法による秘密保護の対象ではない」とかいてありますが? / これは構内電話のことみたいなので取り下げ

----

はてなブックマーク - HiromitsuTakagiのブックマーク / 2008年07月25日

http://b.hatena.ne.jp/HiromitsuTakagi/20080725#bookmark-9428837

id:HiromitsuTakagi 「電気通信事業者の取扱中に係る通信の…」ん?急に…が最後にはいってますが通信の秘密に論をすり替えようとしてませんか?自分が指摘しているのは「通信」の話ですよ

----

はてなブックマーク - nihenのブックマーク / 2008年07月25日

http://b.hatena.ne.jp/nihen/20080725#bookmark-9428837

あ、これは構内電話のことのみをいっているんだ。だとしたらそれは了解です。

----

はてなブックマーク - nihenのブックマーク / 2008年07月25日

http://b.hatena.ne.jp/nihen/20080725#bookmark-9428942

[ゴミタグとかw]id:HiromitsuTakagi あ。いや。自分の「これは構内電話のことのみをいっているんだ。」はpdf中の「家庭内にある電話線を流れる通信や、... 事業法による秘密保護の対象ではない」に掛ってますので・・・。

----

はてなブックマーク - nihenのブックマーク / 2008年07月25日

http://b.hatena.ne.jp/nihen/20080725#bookmark-9428954

id:HiromitsuTakagi あと第三者が傍受した場合には家庭内においても「電気通信事業者の取扱中に係る通信」であるなら通信当事者であればそうではないとするその根拠は何なんですか?

----

はてなブックマーク - HiromitsuTakagiのブックマーク / 2008年07月25日

http://b.hatena.ne.jp/HiromitsuTakagi/20080725#bookmark-9428055

id:HiromitsuTakagi なんですか私にばっかり根拠示せ示せって、、。自分から先に示してみたらどうですか?

----

はてなブックマーク - hasegawayosukeのブックマーク / 2008年07月25日

http://b.hatena.ne.jp/hasegawayosuke/20080725#bookmark-9429071

id:hasegawayosuke 通信当事者の通信は「電気通信事業者の取扱中に係る通信」なのかということを論議しているので根拠になっていない。むしろ秘密に掛っていることからも「…係る通信」であることが類推できるぐらいです。

2008-01-13

Cも知らないのにDとか 02:39

よくよく考えたら大学で授業を受けたのが, Java, Prolog, Schemeという組み合わせでCだけ受けていない.

D言語が良いと聞くので, 試しに触ってみた.

import std.stdio;
const int n = 64;
const int m = 16;

void main(){
  int[n][m] w;
  writefln(w[0]) // 64次元の配列
  for (int i = 0; i < n; i++){
    for (int j = 0; j < m; j++){
      w[j][i] = 1; // 全て1の行列に
    }
  }
}

添え字が入れ替わるので一瞬はまった. w[j] (j=0,...,m) がn次元の配列なので, それにアクセスするときはw[0][i] (i=0,...,n) ということか.

2007-12-20

[] SCIS 2008 プログラム 00:50

出てた. 全12頁のpdfだった. 一部のタイトルが切れてる気がする.

とりあえず大雑把にチェック.

2007-10-28

[] 00:06

t120 l8
@0 サイン波
o0c4defghab o1c4defghab o2c4defghab o3c4defghab o4c4defghab
o5c4defghab o6c4defghab o7c4defghab o8c4defghab
@1 ノコギリ波
o0c4defghab o1c4defghab o2c4defghab o3c4defghab o4c4defghab
o5c4defghab o6c4defghab o7c4defghab o8c4defghab
@2 三角波
o0c4defghab o1c4defghab o2c4defghab o3c4defghab o4c4defghab
o5c4defghab o6c4defghab o7c4defghab o8c4defghab
@3 パルス波
o0c4defghab o1c4defghab o2c4defghab o3c4defghab o4c4defghab 
o5c4defghab o6c4defghab o7c4defghab o8c4defghab
t120 l16 o4 @2
$SLUR=c&c+&d&d+&e&f&f+&g&g+&a&a+&br4;
$NONS=cc+dd+eff+gg+aa+br4;
$SLUR$NONS;