請用此 Handle URI 來引用此文件:
http://tdr.lib.ntu.edu.tw/jspui/handle/123456789/56805
標題: | 一個基於BFV加密的高通量安全比較協議 A High Throughput BFV-based Secure Comparison Protocol |
作者: | Tzu-Hsiang Kuo 郭子翔 |
指導教授: | 吳家麟(Ja-Lin Wu) |
關鍵字: | 安全比較協議,安全多方運算,全同態加密,安全拍賣,環容錯, secure comparison,multi-party computation,fully homomorphic encryption,secure auction,ring learning with error, |
出版年 : | 2020 |
學位: | 碩士 |
摘要: | 假設涉事雙方分別握有一個位元的整數(即其大小介於0到2 − 1之間),本文關切之安全比較的目標是:在不洩露各自整數的前提下計算出兩數字的大小關係。 現存較快的安全比較協議都是基於同態加密技術,而大部分基於同態加密的安全比較協議,至少需要加密 其中一方的各個位元。意即每位元至少需要一次加密的時間,這形成一個(時間)效能瓶頸。 在本論文中,我們使用 BFV 加密技術以改善 DGK 安全比較協議,並用批次處理技巧來減少協議中所需的加密次數。舉例來說,我們提出的演算法總共只需要六次加密(並不會隨著 l 的大小增減)。令為事先選定之安全參數,我們可以達到̃( + )的時間複雜度。實驗中我們可在十三毫秒內完成四零九六位元的安全比較,(時間)效能約為現存基於同態加密技術最快安全比較協議的兩百八十倍。 Secure comparison is a fundamental problem in multiparty computation. Assume there are two different parties, each of them holds an l-bit integer, denoted by a and b respectively. The goal of secure comparison is to compute the order relationship between a and b, say (a ≥ b) ∈ {0, 1}, without revealing their inputs to any others. The fastest solution to secure comparison (so far) is based on homomorphic encryption. Since previous solutions based on homomorphic encryption need at least Ω(l) encryptions for each l-bit comparison, the total encryption time leads to a computational bottleneck for these protocols. In this thesis, we present a fast, semi-honest secure comparison protocol based on BFV encryption scheme. With the vector-like plaintext space of BFV scheme, the number of required encryptions can be significantly reduced; actually, only six encryptions are needed for each comparison in our protocol. In other words, the proposed protocol can achieve the time complexity O˜(λ + l) for a given security parameter λ. As a result, 4096-bit integers can be securely compared within 12.08ms, which is 280 times faster than the state-of-the-art homomorphic encryption-based secure comparison protocol. Furthermore, we can compare k pairs of l/k-bit integers with almost the same execution time to comparing l-bit integers, and achieve higher throughput regardless of the compared integer-size. |
URI: | http://tdr.lib.ntu.edu.tw/jspui/handle/123456789/56805 |
DOI: | 10.6342/NTU202001802 |
全文授權: | 有償授權 |
顯示於系所單位: | 資訊工程學系 |
文件中的檔案:
檔案 | 大小 | 格式 | |
---|---|---|---|
U0001-2307202021062800.pdf 目前未授權公開取用 | 1.07 MB | Adobe PDF |
系統中的文件,除了特別指名其著作權條款之外,均受到著作權保護,並且保留所有的權利。