フィボナッチ数の話

素数体係数多項式の拡張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)
    • まさかのLittle Dragon. 多変数多項式系. 自己評価のところでざらっと考えられる攻撃に関する話があったので話半分に聞いておくことにする. そういえばSquare (C. Clough, J. Baena, J. Ding, B.-Y. Yang, and M.-S. Chen CT-RSA 2009) も破れたんですかねぇ。O. Billet and G. Macario-Rat (ASIACRYPT 2009) とかタイトルがそれっぽい.
  • 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)
    • アフィン関数に関するKDM安全な公開鍵暗号方式にはDDHベースのものとLWEベースのものがある. これをどうにかしてd次の多項式辺りまで持ち上げる話. DDHベースの方は鍵が長くなるだけだが, LWEベースの方はエラーの所為で仮定を相当強めなくてはならないとかなんとか. ざっと見た限りでは, GapSVPに落とすと近似度がquasi-polyで敵の能力もquasi-poly. あらー. でもしょうがないかという感じ.

うーん

ツッコミに対する反応を見て余計分からなくなった.

mixi日記で、突っ込まれた点について。
量子コンピュータチューリングマシンでできることは全てできることが証明されているので、かけ算も当然できます。量子力学的重ね合わせを使わなければ、全ての量子ビットが古典ビットになり、状態の読み書きが自由にできるので、古典コンピュータと同じになります。しかし、問題は、高速にできるかどうかです。n量子ビットあれば、2^n個のかけ算を並列にO(1)で処理して欲しく、それがないと、量子コンピュータの価値が出ないのですが、それが、僕には無理そうに見えるという意味です。

O(1)は無理だが, O(n^2)とかO(n log n log log n)なら出来る.
重ね合わせておいてもbをnビット列として,
\sum_{a=0...0}^{1...1} \alpha_{a} |a\rangle|b\rangle \rightarrow \sum_{a=0...0}^{1...1} \alpha_{a}|a \oplus b\rangle|b\rangle
という演算はO(n)個の量子ゲートで出来る*1. なのでXORとNOT使って掛算回路組めば十分で, 重ね合わせておこうが掛算も出来る.

現実的に10000量子ビット用意して計算するの無理じゃない?という話なら納得出来るんだけど, 何を問題にしたいのかよく分からない.

*1:制御NOTをn個で出来る

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)

Introduction to Identity-Based Encryption (Information Security and Privacy Series)


VoltageのLuther Martinが書いた本. Cocks, Boneh-Franklin, Waters, Sakai-Kasaharaの紹介をしている. 楕円曲線の話にも触れており, 卒論で使うとか, 院生向けの授業に丁度良いんじゃないでしょうか. IDベース関係は良い入門書が無かったのでお勧め.
Identity-Based Cryptography (Cryptology and Information Security Series)

Identity-Based Cryptography (Cryptology and Information Security Series)


JoyeとNevenが編者. 中身はIDベース系の話のサーベイ集. こっちはプロ向け.