こんにちは！聖なる夜にいかがお過ごしでしょうか……
プレイドでインターンをしている有光と申します。

内容

今日の記事は、インターン生共著でして、せっかく学生が書くということで、超優秀エンジニアであり研究者でもある尾澤くん、渡辺くんに彼らの研究内容について書いて貰いました。しかし、私有光はポンコツ文系研究なんてしないよ系エンジニアなので、最近思ってることでもつらつらと書こうと思います。

最近の学び by 有光

僕は大学三年生でして、プログラミングはほぼ独学し、ここプレイドでインターンとして働いています。学部は商学部で、交渉学を勉強しています。一方、技術のことはインターンを通してたくさん学んでいます。

大学三年生の冬となると、大体の大学生の就活がはじまるかな、という時期に差し掛かっています。僕は将来はエンジニアになる！と決めているわけではないので、いろいろな会社のインターン等に参加したりもしています。
プレイドでのインターンや就活の中で学んだことがいくつかあります。

それは

人を納得させるのはロジック。人を動かすのは情熱と共感。
仕事をする上で、大切なのはワクワク感と仲間。

ということです。掘り下げていきます。

人を納得させるのはロジック。人を動かすのは情熱と共感。

たとえば私がある商社に勤めていて、ある日取引先の自動車会社から、「あなたの会社と組んで、若い女性をターゲットに新開発した自動車をA国に売りたいから、事業計画を考え、プレゼンしてほしい」　と依頼されたとします。
ここで大切なことは、私の事業計画がしっかり数字に裏付けされた納得感がある上で、私と、ひいては私の商社と一緒に仕事をしたい！と思わせることだと思います。
具体的には、

売る自動車のターゲットの若い女性(２０歳〜３０歳)はA国に◯万人いて、その△%が車を持っていません。データからの推定からその中の3％が我々の自動車を買ってくれたとすると、一台あたりの利益が☓円なので、得られそうな利益は@円です！

というような数字に裏付けされたロジックがあると、人はそれなりに納得します。
しかし、その上で人を動かすためには、ロジックだけでは足りません。私という人の熱心さや、接待や飲み会で培った信頼感や共感があって初めて、人は動いてくれるのだと学びました。

そして、ここプレイドでは、インターンの裁量がかなり大きいです。社内ツールを開発したり、KARTEの新機能の開発にインターンが参加できます。その中で、技術力だけでなく、自分の意見を相手に伝える発信力、また相手の話への傾聴力は、実際にチームの一員として働くプレイドのインターンだからこそ学べるのだと思っています。

仕事をする上で、大切なのはワクワク感と仲間

この記事を読んでくださっている方の多くがエンジニアだと思いますが、この点については多くの人が共感してくれるのではないかと思います。特に面白くもないコーディングを長々とやりたい人はいないだろうし、イケてるサービスの開発ならコーディングスピードも増すでしょう。そしてあなたは、他のエンジニアやデザイナー、そしてビジネス側の人たちとチームとして、仲間として、共に仕事をしています。時には仕事がとてつもなくきついときもあるでしょう。しかしそんな時に頑張れる原動力となるのは、イケてるサービスを作っているワクワク感と、素敵な仲間と共に働く楽しさかなと思います。

量子暗号について by 尾澤

エンジニアインターン尾澤です。
今回は、自分が大学で研究している量子暗号、特に量子鍵配送について話したいと思います。
ざっくりとした内容ですが、みなさんが少しでも興味を示していただけると幸いです。

厳密な話はできませんが、もし内容に誤りがあった場合、訂正しますのでご指摘ください。

量子鍵配送とは

量子鍵配送とは、量子力学に基づいて暗号通信に用いる鍵を共有する方法です。
量子力学に基づき暗号通信を行うため、理論上どんな方法を用いても解読が不可能です。
解読不可能な一方、量子を扱う場合のノイズの影響などにより、従来の古典暗号と比較して低速です。

	古典暗号	量子暗号
秘匿性の担保	計算量	量子力学
通信速度	高速	低速
盗聴の困難さ	高速計算により解読可能	理論上は解読不可能

※鶴丸豊丸. 量子暗号の基礎とその実用化に向けて. http://ibisml.org/ibis2010/session/ibis2010tsurumaru.pdf, 2010. を参考にしました。

鍵共有とは

暗号通信を行う場合、送信者は通信内容（平文）を鍵を用いて暗号文を作成し、受信者は受信した暗号文を鍵を用いて平文とします。
ここで問題となるのがこの鍵の共有法です。鍵を物理的に運ぶことが最も安全ですが、それでは通信内容自体を運ぶほうが楽です。

既存の技術ではDiffie-Hellman鍵共有を使われることが多く、これは離散対数問題に帰因し秘匿性は担保されています。

離散対数問題とは

離散対数問題とは、素数に関する式
$$
y = a^x \mod p
$$
に対し、(p,a,x)の値からyを求めることは簡単だが、(p,a,y)の値からxを導出することが困難という問題です。
量子コンピュータのような高速計算可能な計算機が実現すると、この問題は解決されます。

Diffie-Hellman鍵共有の問題点

Diffie-Hellman鍵共有は離散対数問題に依存し鍵共有を行います。
主な手順は以下の通りです。
1. 二つの素数pとxを準備する。このpはとても大きな素数である。pとxは公開するため、送信者も受信者も知ることができる。
2. 送信者と受信者はそれぞれ 1~p-2 の任意の値 a,b を準備する。この数aとbは公開しない秘密の値である。
3. 送信者は自分が知っている値である (p,x,a) をもとに、
$$
A = x^a \pmod p
$$ を導出し、この値 Aを受信者に送信する。
4. 受信者も同じく自分が知っている値である (p,x,b) をもとに、
$$
B = x^b \pmod p
$$を導出し、この値Bを送信者に送信する。
5. 送信者は受信者から送られた値 B から
$$
B^a \pmod p = (x^b \mod p)^a \mod p
$$を導出する。
6. Bob も同じく Alice から送られた値 A から
$$
A^b \pmod p = (x^a \mod p)^b \mod p
$$を導出する。
7. それぞれが導出したこの値は、
$$
(x^b \mod p)^a \mod p = x^{ab} \pmod p =(x^a \mod p)^b \mod p
$$より、等しい値であり、これが共有した鍵となる。

このとき公開されている値は(x,p,A,B) だけで、aまたはbの値を知らないため、送信者・受信者以外は高速計算が可能にならない限り、鍵の作成は不可能です。

量子鍵配送の例

代表的な量子鍵配送の方法として、BB84が挙げられます。
簡単に手順を示します。
1. 送信者は0/1に対応し任意の量子状態に変化させ、このビット（通常のビットではなく、光子などの量子ビット）を送信する
2. 受信者は任意の測定方法で受信した量子ビットを測定する
3. 受信者は自分が測定した方法（結果でない）を送信者と任意の手段で確認する
4. 送信者と受信者が等しい方法で量子状態を扱った場合の測定結果（ビット値の集まり）を鍵とする

量子力学（不確定性原理）に基づくと、送信者と受信者が等しい方法で量子を扱った場合、必ず正しいビット値を共有することができます。
これは一般的な位置と運動量ではなく、光子の偏光や位相差に関する不確定性原理を考えた場合に帰因します。

もし通信路上で第三者が量子ビットを解読をしようとすると、量子状態が変化し、送信者と受信者は正しい方法で量子を扱っても正しいビット値を得ることができません。
送信者と受信者は得たビット値の一部を確認しあうことで、第三者の解読の影響を検知することが可能です。

量子鍵配送の現状

既に一部の企業では商用化されています。
例：ID Quantique
https://www.idquantique.com/quantum-safe-security/overview/qkd-technology/

最後に

現状は離散対数問題が解決されていないために計算量依存で暗号通信は行われていますが、2016年にIBMがクラウド上で扱える量子コンピュータシステムを公開したり（https://www.research.ibm.com/ibm-q/ ）、量子コンピュータが実現するのは時間の問題かもしれません。
量子鍵配送が次世代のインターネットを守ると信じ、研究を続ける日々です…。

高速フーリエ変換 (fast Fourier Transform, FFT) による多項式の乗算（畳み込み）をSchemeで実装する by 渡辺

最近、高速フーリエ変換による畳み込みについて理解する必要がありました。$N$ 次元の多項式 $p(x)$ と $q(x)$ の積 $p(x) q(x)$ を計算することを考えます。$p(x) q(x)$ を素直に（つまり、多項式の筆算をするような感じで）計算すると、$p(x)$の各項の係数と $q(x)$ の各項の係数との乗算を行う必要があるため、計算量は $O(N^2)$ となります。しかし、高速フーリエ変換を用いると、$p(x) q(x)$ の計算は計算量 $O(N log N)$ でできます。そのような高速フーリエ変換を理解するために、Schemeで高速フーリエ変換をするプログラムを書きました。

高速フーリエ変換とは、離散フーリエ変換を高速に行うアルゴリズムです。離散フーリエ変換とは、下の式のように表されるものです。

F(t) = \sum_{x=0}^{N-1} f(x) e^{-2 \pi x t i / N}

また、この逆を逆離散フーリエ変換といい、下の式のように表されます。

f(x) = \frac{1}{N} \sum_{t=0}^{N-1} F(t) e^{2 \pi t x i / N}

式通りに素直に計算すると、離散フーリエ変換の結果 $F(t)$ を $t = 0$ から $t = N - 1$まで求めるには計算量 $O(N^2)$ が必要です。高速フーリエ変換とは、上記の離散フーリエ変換を $N$ が2のべき乗になるようにして（本当は、$N$ が2のべき乗でない場合でも計算はできるのですが、2のべき乗の場合が最も効率よく計算できます）、分割統治法を用いて計算量 $O(N log N)$ で行うアルゴリズムです。
高速フーリエ変換による多項式乗算について詳しく知りたい方は、以下のページをご覧ください。
- https://www.geeksforgeeks.org/fast-fourier-transformation-poynomial-multiplication/
- https://qiita.com/hi-watana/items/c361152953b8307f459c

なぜ Scheme なのか

高速フーリエ変換の基本的な考え方が、分割統治法を用いることで計算量を削減するというものであるため、再帰を多用する関数型言語で書きやすいと思ったから。
Scheme は末尾再帰最適化が行われるような仕様であるため。
Scheme で書くと楽しい（と私は思う）から。

実装

まず、末尾再帰最適化を行わず、分割統治法を素直に再現したコードです。
関数fftの引数aは多項式 $p(x)$ の各項の係数 $a_0, a_1, \ldots, a_{N-1}$ をリストにしたもの、引数nはaの長さを表しています。

(define PI (* 4 (atan 1)))

(define (part a)
  (define (_part a o e)
    (cond ((null? a) (values o e))
          (else (_part (cddr a) (cons (cadr a) o) (cons (car a) e)))
          ))
  (_part (reverse a) '() '())
  )
(define (_fft a sign n)
  (cond ((eq? n 1) a)
        (else
          (let* ((ll (receive (a0 a1) (part a) (map (lambda (a) (_fft a sign (ash n -1))) (list a0 a1))))
                 (l2l2 (map (lambda (ys) (append ys ys)) ll))
                 (ws (map (lambda (i) (exp (/ (* sign 2 PI i 0+1i) n))) (iota n))))
            (apply map (cons (lambda (w y0 y1) (+ y0 (* w y1)))
                             (cons ws l2l2)))))))

(define (fft a n) (_fft a -1 n))
(define (inverse-fft a n)
  (map (lambda (z) (/ z n)) (_fft a 1 n)))

次に、末尾再帰最適化を用いたコードを示します。

(define PI (* 4 (atan 1)))
(define (part a)
  (define (_part a o e)
    (cond ((null? a) (values o e))
          (else (_part (cddr a) (cons (cadr a) o) (cons (car a) e)))
          ))
  (_part (reverse a) '() '())
  )
(define (_fft a sign n cont)
  (cond ((eq? n 1) (cont a))
        (else
          (let ((pair (receive (a0 a1) (part a) (cons a0 a1)))
                (n/2 (ash n -1)))
            (_fft (car pair) sign n/2
                  (lambda
                    (a0)
                    (_fft
                      (cdr pair)
                      sign
                      n/2
                      (lambda
                        (a1)
                        (cont (let ((ws (map (lambda (i) (exp (/ (* sign 2 PI i 0+1i) n))) (iota n/2))))
                                (append (map (lambda (w y0 y1) (+ y0 (* w y1))) ws a0 a1)
                                        (map (lambda (w y0 y1) (- y0 (* w y1))) ws a0 a1))))))))))))
(define (fft a n) (_fft a -1 n (lambda (x) x)))
(define (inverse-fft a n)
  (map (lambda (z) (/ z n)) (_fft a 1 n (lambda (x) x))))

末尾再帰最適化の実現のために、継続と呼ばれる手法を用いています。

最後に

実用上は、Schemeで高速フーリエ変換を実装するメリットはあまりないと思います。また、今回は高速フーリエ変換を分割統治法を用いて、再帰的に計算する方法で実装しましたが、高速フーリエ変換の実装にはより効率的な実装があります（例えばこちら https://www.geeksforgeeks.org/iterative-fast-fourier-transformation-polynomial-multiplication/ ）。
今回は実用性を無視して、あくまでも高速フーリエ変換の初歩的な実装を関数型プログラミングで書いてみたら面白いだろうなと思って Scheme で実装してみました。

感想　by 有光

ここまで読んでくださった読者の皆様、いかがだったでしょうか？　
僕には、「なんかおもしろそうやな〜」とか、「これからの日本の技術は君たちに任せた！」という感想しか出てきませんw

ここまで読んでくださってありがとうございました！
プレイドという会社やインターンに興味を持っていただけた方は、
https://www.wantedly.com/companies/plaid?aql=gaFxpXBsYWlk
を見てみて下さい！

プレイドのインターンから

内容