量子计算与密码学.doc

1 量 子 計 算 與 密 碼 學 曾文貴 交通大學 資訊科學系 愛因斯坦 Albert Einstein 說 上帝不丟骰子 意味著他相信世界的下一步 是確定的 然而經由驗證 貝爾不等式 J Bell s inequality 代表 世界的下 一步是隨機的 的量子 quantum mechanics 學派得到現今大多數物理學家的認 同 物理的論證似乎有了一個定論 但是密碼學家的夢靨才剛剛要開始 自從費因曼 Richard Feynman 在八十年代提出利用量子現象來增加計算的 速度之後 量子電腦 quantum computer 的概念漸漸的形成 量子電腦的最大特 點是 N 個儲存位元可以同時儲存 2N個資料 因此量子電腦可以在多項式時間 內解決一些目前電腦還需要指數計算量才能解決的問題 例如質因數分解 計 算整數對數等 另外 量子電腦也可以加快完全搜尋 exhaustive search 的速度 根據估計 只要有幾千量子位元 qbits quantum bits 的量子電腦 它的計算 能力就要比現今地球上所有電腦的計算能力總和強上不知凡幾倍 目前具有幾 個量子位元的量子電腦已經實驗成功 20 至 30 量子位元的量子電腦也在設計 與實驗中 如果實用的量子電腦實現了 密碼的研究要往哪裡走呢 這篇文章介紹 量子計算 quantum computation 量子密碼分析 quantum cryptanalysis 量子密碼方法 quantum cryptography 等 並討論未 來密碼研究的方向 奇妙量子的世界 物質具有粒子與波的雙重特性 到了次原子的世界 他們所產生的 量子現象實在是令人難以相信 我 們先來說一個大家熟悉的電子繞射 干擾實驗 圖一中的電子槍 E 將電 子一顆一顆的射向有 A 和 B 兩個細 縫閘的薰黑玻璃 這時螢幕 S 上會 有光點一個一個出現 而且漸漸地 顯示出明顯的干涉條文 但是如果 將 B 閘遮蓋起來 則螢幕上會呈現出如圖二的一片模糊 我們現在來看這個實驗的量子現象 在圖二中 當一個電子從 E 到達 A 閘 時 它可以到達螢幕上的任一點 因此螢幕呈現出一團模糊的光點 在圖一中 S A B E 2 多一個 B 閘 因此一個電子可以到達 A 閘或是 B 閘 然後再到螢幕上顯像出來 問題是當一個電子在 A 閘 或 B 閘 時 它如何得知 B 閘 或 A 閘 是開的 然後跑到螢幕相關的位置上而形成干涉條文 這不是很奇怪嗎 量子論對此的解釋是一個電子 是可以 同時同時 出現在 A 閘與 B 閘 因此它知道要在螢幕上形成干涉的 條文 量子論稱同時出現在不同的 位置為 重位置 superposition 也就是這些量子狀態 coherence 在一 起 因此我們可以用一個量子來 同時 表示兩個不同的狀態 這 稱為一個量子位元 qbit 以此類推 N 個量子位元可以 同時 表示 2N種不同的狀態 舉例來說 目前兩個位元的暫存器 在一個時間上只能表示 00 01 10 和 11 中的一種狀態 但是兩個量子位元的暫存器 在一個時間上卻可以同時表 示 00 01 10 和 11 四種狀態 四個數字 我們可以把一個運算同時作用在這 四個數字上 量子電腦的超級計算能力就是來自這裡 量子電腦如何計算 一個量子位元的兩個狀態以 0 和 1 來表示 其中 a 和 b 為虛數 但 是 1 兩個量子位元的暫存器 2 qbit register 可以代表 a1 00 a2 01 a3 10 和 a4 11 其中各 ai為虛數 而且 a1 a2 a3 a4 1 其餘 的以此類推 我們可以把一個運算 unitary operation F 對 N 量 子位元暫存器作運算 將重 位置由 a1 00 0 a2 00 1 a2N 11 1 轉換成 b1 00 0 b2 00 1 b2N 11 1 例如 圖三中的 F 對三個 量子位元暫存器的八個數字 作運算而得到新的重位置 因此 F 是對這 2N個數字同 時作運算 也就是 量子平行運算 但是只要有個量子位元的暫存器及一些量 子邏輯閘即可 量子電腦的功能雖然強大 實際使用時必須克服一些問題 主要是 量子 狀態的不可回覆性 及 量子狀態的脆弱性 雖然量子電腦可以同時表示 2N a1 000 a2 001 a3 010 a4 011 a5 100 a6 101 a7 110 a8 111 F a1F 000 a2F 001 a3F 010 a4F 011 a5F 100 a6F 101 a7F 110 a8F 111 b1 000 b2 001 b3 010 b4 011 b5 100 b6 101 b7 110 b8 111 S A E 3 個值 但是如果我們要得到暫存器的內容時 必須作 de coherence 的動作 也 就是摧毀量子狀態而得到一個值 這個值是所有狀態的一種 而且得到某個值 的機會是相對狀態的係數的長度 更困難的是 量子狀態一但 de coherence 之 後就無法恢復到原來的狀態 因此計算必須一氣呵成 因為要得到某個特定的 值是不可行的 只好將我們要的值的係數估算出來 再利用統計的方法求之 因此每一次計算都要準備 m 個相同量子計算 再利用 random sampling 的技巧 來估算未知值 量子狀態也非常脆弱 易受外在環境的干擾而崩潰 因此要將 量子狀態維持一段時間以完成計算並不容易 也許未來可以克服這個技術問題 總括來說 量子的計算可以分成下列幾個步驟 1 準備 m 個相同的量子暫存器 並將它們狀態的係數調好 2 把運算作用在這些暫存器上 使得某些狀態的值為結果 並計算這些 狀態的係數 3 對 m 個量子暫存器作 de coherence 而得到一些 random sampling 的結 果 再利用統計的方法計算出我們要的值 量子密碼分析 量子電腦對密碼學的衝擊來自它能在多項式時間內作 因數分解 及 計 算整數對數 現在我們來看量子電腦如何做因數分解 量子電腦計算 N 的因數分解是求 FN x ax mod N 的週期 order 也就是求 T 使得 aT mod N 1 如果我們能求得 T 且 T 為偶數 那麼有很大的機會 gcd aT 2 1 N 是 N 的因數 例如 如果要因數分解 N 21 我們找任一數 a 2 計算出它的週期 T 6 因此 gcd 23 1 21 3 和 7 是 21 的因數 量子電腦準備兩個量子暫存器 R1 及 R2 各有 n log N 位元 然後執行下 列步驟 1 將 R1 的位元設定為含有 2n個值的重位置 superposition 也就是 R1 含有所有可能的 n 位元值 x 從 00 0 到 11 1 這可以輕易的達到 首先將每個量子位元設為 1 0 再利用簡單的 unitary 轉換將它轉成 1 0 2 1 然後兩個量子位元會 coherence 變成 11 10 01 00 2 1 1 0 2 1 1 0 2 1 其餘的以此類推 2 對 R1 的重位置值 x 計算 FN x 並放到 R2 內 這時 R1 和 R2 的量子 位元形成新的重位置 不列出各狀態的係數 x N xFx 4 3 將 R2 的內容 de coherence 得到某一個 FN k 值 這時 R1 內的重位置 值為 其中 x k k T k 2T 也就是所有的 x 值使得 FN x x x FN k 4 對 R1 的內容作 quantum Fourier transformation 將 R1 的內容作一個 平行位移並將週期調成 1 T 就是 x 的值為 1 T 的倍數 5 將 R1 的內容作 de coherence 得到一些值 再求這些值得 gcd 得到 1 T 6 最後用一般的計算機求 gcd kT 2 1 N 量子電腦也可以在多項式時間內計算自然對數 它還可以加快完全搜尋 目前已經把完全搜尋時間由 2N推進到 2N 3 新的演算法還在研究之中 量子密碼方法 從另一個角度來看 量子特性也可以用來解決安全上的問題 最主要是利 用 量子不可能被竊聽 的物理特性 因為攻擊者一旦竊聽了量子所帶的資訊 也就破壞了量子的狀態 接收者也就收不到該信息了 量子金匙分配 quantum key distribution 就是利用這個特性來達成 一個光子可以用不同的測量方法 basis X 或 Y 來測量它的狀態 現在我 們令它們代表不同的值如下 StateBasisValue 0 X0 1 X1 0 1 Y0 0 1 Y1 如果 Alice 和 Bob 要建一把秘密金匙 K 先假設 K 只有一個位元 Alice 任 意選用四種狀態 state basis 中的一種來產生光子 並將它傳送給 Bob Bob 任意用 X 或 Y 測量方法來測量該光子的狀態 如果 Bob 所使用的測量方法和 Alice 相同 那麼他會得到 Alice 所送的值 如果 Bob 所使用的測量方法與 Alice 的不同 所得到的值就不一定和 Alice 的相同 應該捨棄該位元 重新再 作 整個步驟如下 1 Alice 任選一個 state basis s b 然後送該光子給 Bob 2 Bob 任選一個測量方法 b 來測量送來的光子 3 Alice 和 Bob 都公開宣佈他們所用的測量方法 b 和 b 4 如果 b b 則 Alice 和 Bob 共有一個值 如上表所示 重複上述步驟多次 可以得到一個 n 位元的共同秘密金匙 K 對竊聽者 Eve 而言 她可以使用 X 或 Y 測量方法來偵測傳送給 Bob 的光子的值 如果 Eve 用的測量方法和 Bob 相同 Bob 所收到的值就和 Eve 相同 但是如果他們 用的測量方法不同 Bob 所收到的是一個任意值 因此即使 Bob 和 Alice 使用 相同的測量方法 仍然有一半的機會他們的值是不相同的 最後 Alice 和 Bob 5 利用 K 加密一個公開的明文 就可確定是否有竊聽者 目前已有多處實驗室在實驗量子金匙分配 到 1996 年為止 已經能夠利用 光纖將光子傳送到 23 公里遠的地方 2 到 1998 年 50 公里的傳送也實現了 如果是在一般的空間中傳送 也可以達到幾十呎遠 結論 目前的公開金匙系統大都是基於解自然對數及因數分解的困難度 但是量 子電腦能夠解決這些問題 因此如果量子電腦成功 基於這些問題困難度的加 密系統 數位簽章 及密碼協定都將變的不安全 然而安全性基於 資訊理論 information theoretic 的密碼系統仍然能夠保持安全 從另一個角度來看 量 子計算也提供了另一種設計密碼系統的工具 例如量子金匙分配 因此量子密 碼系統的設計與分析是值得注意的 Peter Shor 利用量子演算法 quantum algorithm 解決自然對數及因數分解等 問題 8 促使更多研究者投入這方面的研究 量子電腦上演算法的設計與分析 是一個值得注意的研究方向 要實現量子電腦的技術還在萌芽階段 它的前景仍然充滿不確定性 有人 樂觀 有人完全不看好 我們應該密切注意它的發展 後記 量子計算與量子密碼學簡史 Richard Feynman 於 1982 年首先提出量子計算的慨念 7 但是沒有馬上受 到重視 直到 1985 年 David Deutsch 提出一個量子電腦 universal quantum computer 的計算模式之後 4 才有一些研究者加入研究 然而幾年的研究 並 沒有太大的突破 量子電腦似乎不能解決什麼實際的問題 直到 1994 年 Peter Shor 提出因數分解與計算自然對數的量子演算法後 8 大家才認識到量子電腦 的超強計算能力 特別是破解編碼的能力 之後就有很多研究者加入這方面的 研究 Stephen Wiesner 於 1969 年首先將量子理論應用到密碼學上 他提出 conjugate coding 開創了 Quantum cryptography 但是並沒有受到什麼注意 因此直到 1983 年才發表了這個結果 9 Charles H Bennett 和 Gilles Brassard 是 比較早認識到這個結果的重要性的人 他們在 1984 年提出量子金匙分配的方法 1 並致力推廣量子計算 參考資料參考資料 1 C H Bennett G Brassard Quantum cryptography public key distribution and coin tossing Proceedings of IEEE International Conference on Computers System and Signal Processing Bangalore India pp 175 179 1984 2 G Brassard C Cr peau Cryptology column 25 years of quantum cryptography 6 SIGACT News 1996 3 G Brassard Quantum information processing the good the bad and the ugly Advances in Cryptology Crypto 97 pp 337 341 1997 4 D Deutsch Quantum theory the Church Turing Principle and the universal quantum