フィボナッチ数の話
素数体係数多項式の拡張GCDを書かないといけないのだが, それはさておき.
ストリーム版が無いけど気にするな.
;;;素朴 (define (fib1 n) (cond ((= n 0) 0) ((= n 1) 1) (else (+ (fib1 (- n 1)) (fib1 (- n 2)))))) ;(time (fib1 30)) ; real 0.285 ; user 0.281 ; sys 0.000 ;;;末尾再帰 (define (fib2 n) (define (fib-iter i a b) (if (= n i) a (fib-iter (+ i 1) b (+ a b)))) (fib-iter 0 0 1)) ;(time (number? (fib2 100000))) ; real 1.407 ; user 1.217 ; sys 0.156 ;;;ハッシュ (define (fib3 n) (define fib-in-memo (let1 ht (make-hash-table 'eqv?) (define (memo m v) (hash-table-put! ht m v) v) (lambda (m) (cond ((= m 0) 0) ((= m 1) 1) ((hash-table-get ht m #f)) (else (memo m (+ (fib-in-memo (- m 1)) (fib-in-memo (- m 2))))))))) (fib-in-memo n)) ;(time (number? (fib3 100000))) ; real 2.077 ; user 1.514 ; sys 0.546 ;;;行列 ;;; (1 1) ;;; (f(n+2) f(n+1)) = (f(n+1) f(n)) (1 0) (use gauche.array) (define (fib4 n) (array-ref (array-expt (array (shape 0 2 0 2) 1 1 1 0) n) 1 0)) ;(time (number? (fib4 100000))) ; real 0.215 ; user 0.218 ; sys 0.000 ;;;エラー処理とか面倒ですよね (define (fib n) (if (and (integer? n) (not (negative? n))) (array-ref (array-expt (array (shape 0 2 0 2) 1 1 1 0) n) 1 0) (error "Non-negative integer required:" n)))
最近のePrint
まぁ出自が出自なので公開鍵系しか読めませんけど。
- R. P. Singh, A. Saikia and B. K.Sarma. “Little Dragon Two: An efficient Multivariate Public Key Cryptosystem.” (Cryptology ePrint Archive: Report 2009/488)
- A. Lewko and B. Waters. “Efficient Pseudorandom Functions From the Decisional Linear Assumption and Weaker Variants.” (Cryptology ePrint Archive: Report 2009/486)
- タイトルの通りで, DDH仮定で作ってたPRFをk-Linear仮定からでも作れました (よって仮定が弱まりました) だそうで.
- Z. Brakerski, S. Goldwasser, and Y. Kalai. “Circular-Secure Encryption Beyond Affine Functions.” (Cryptology ePrint Archive: Report 2009/485)
うーん
ツッコミに対する反応を見て余計分からなくなった.
mixi日記で、突っ込まれた点について。
量子コンピュータはチューリングマシンでできることは全てできることが証明されているので、かけ算も当然できます。量子力学的重ね合わせを使わなければ、全ての量子ビットが古典ビットになり、状態の読み書きが自由にできるので、古典コンピュータと同じになります。しかし、問題は、高速にできるかどうかです。n量子ビットあれば、2^n個のかけ算を並列にO(1)で処理して欲しく、それがないと、量子コンピュータの価値が出ないのですが、それが、僕には無理そうに見えるという意味です。
O(1)は無理だが, O(n^2)とかO(n log n log log n)なら出来る.
重ね合わせておいてもbをnビット列として,
という演算はO(n)個の量子ゲートで出来る*1. なのでXORとNOT使って掛算回路組めば十分で, 重ね合わせておこうが掛算も出来る.
現実的に10000量子ビット用意して計算するの無理じゃない?という話なら納得出来るんだけど, 何を問題にしたいのかよく分からない.
*1:制御NOTをn個で出来る
論文用のmicroformatは無いの?
誰かやってるだろうと思ってmicroformatで探しても見つからんかった. bibtex準拠とかで広まると, 便利だと思うんですけどね.
IND-CCA2の定義
Bellare, Hofheinz, and Kiltz “Subtleties in the Definition of IND-CCA: When and How Should Challenge-Decryption be Disarrowed?” (ePrint 2009/418)
暗号のIND-CCA2安全性も定義によって強さが変わるという話.
敵がメッセージを2つ出す前に行った復号クエリの集合をS1, チャレンジをもらった後の復号クエリの集合をS2とします.
- IND-CCA2-SP
- b=b'かつチャレンジがS2に入っていなかったら勝ち
- IND-CCA2-BP
- b=b'かつチャレンジがS1とS2に入っていなければ勝ち
- IND-CCA2-SE
- 後の方の復号クエリでチャレンジを投げない敵のみを考える. b=b'なら敵の勝ち.
- IND-CCA2-BE
- 前でも後でも復号クエリでチャレンジを投げない敵のみを考える. b=b'なら敵の勝ち.
とまぁ4通り考えられます.
教科書によって流儀が違っていたらしく, Goldreich, Delfs and Knebel, Katz and LindelはIND-CCA2-SEだけども, Menezes, van Oorschot and VanstoneはIND-CCA2-BEだったりするそうで.
彼らは, たとえば, OWPとIND-CCA2-BP安全な暗号を仮定して, IND-CCA2-BP安全だけどIND-CCA2-SP安全でない暗号を構成しています. (アイデアは意外と単純.)
一番強いのはIND-CCA2-SPかIND-CCA2-SEなのでそれを使えばいいということです.
IDベース暗号
Introduction to Identity-Based Encryption (Information Security and Privacy Series)
- 作者: Luther Martin
- 出版社/メーカー: Artech House
- 発売日: 2008/01
- メディア: ハードカバー
- クリック: 14回
- この商品を含むブログを見る
VoltageのLuther Martinが書いた本. Cocks, Boneh-Franklin, Waters, Sakai-Kasaharaの紹介をしている. 楕円曲線の話にも触れており, 卒論で使うとか, 院生向けの授業に丁度良いんじゃないでしょうか. IDベース関係は良い入門書が無かったのでお勧め.
Identity-Based Cryptography (Cryptology and Information Security Series)
- 作者: Marc Joye,Gregory Neven
- 出版社/メーカー: Ios Pr Inc
- 発売日: 2008/12/15
- メディア: ハードカバー
- クリック: 3回
- この商品を含むブログを見る
JoyeとNevenが編者. 中身はIDベース系の話のサーベイ集. こっちはプロ向け.