An efficient IND-CCA2 secure Paillier-based cryptosystem

Report
An efficient IND-CCA2 secure
Paillier-based cryptosystem
Angsuman Das, Avishek Adhikari (India)
Information Processing Letters 112 (2012) 885-888
Citation: 2
Presenter: 方竣民
Date: 2013/12/02
Outline
Introduction
 Preliminaries and definitions
 The proposed IND-CCA2 conversion
 Security analysis
 Comparison
 Conclusions

Introduction
公開金鑰密碼系統的目標是設計可抵抗
選擇密文攻擊的密碼系統。
CCA2的安全性是有用的概念,當攻擊者
被允許Query Oracle來做加解密,利用他
自己選擇的密文,並嘗試破解。
這些不安全的方案在做一些較大的應用
時,有被攻擊者利用的可能。
Introduction
對於許多現存的public-key密碼系統都只
達到CPA-secure,CPA密碼系統存在著通
用與專用的轉換至CCA2 secure。
在現有的work,一個新的Paillier加密方
案至IND-CCA2的轉換被提出。
並展示這種轉換比現有的各種通用或專
用的轉換都更好。
Preliminaries and definitions
決策性複合剩餘假設
∗
設定n = pq,其中p,q為大質數,g ∈ 2 ,
= ( − 1,  − 1)
Res n = z ∈ ∗ 2 ∃α ∈ ∗ 2 with α = z}
Γ = z ∈ ∗ 2 z ≡ 1 mod n}
我們定義ε :  × ∗ → ∗ 2
其中 ε ,  =   ∙    2
Preliminaries and definitions
決策性複合剩餘假設
L: Γ →     =
−1

ε 為一個同構(isomorphism)函式,若g的順序在∗ 2
是n的倍數
簡單地說是區分從Res n 或是∗ 2 選出的隨機元素
從形式上看,使得Gen為一個polynomial-time演算法
Input 1
Outputs (n,p,q),n=pq
p,q為k bits的質數,除非概率可以忽略不計k
Preliminaries and definitions
決策性複合剩餘假設(Definition)
我們說決策性複合剩餘問題,如果對所有
概率多項式時間演算法ℬ,是很難相對於
Gen,存在一個可忽略的函數negl使得
| Pr ℬ n,    2 = 1 − Pr[ℬ n, r
= 1]| ≤ negl(k)
該判定的複合剩餘假設(DCRA)是存在一
個Gen相對於該判定的複合剩餘問題是很難
的假設。
Preliminaries and definitions
自訂選擇密文安全
自訂選擇密文攻擊的密碼系統被定義為一個遊戲,在一個公鑰
加密方案PKE挑戰者和攻擊者之間互動如下:
1.給一安全參數t,挑戰者產生public key與secret key pair
並將public key給攻擊者
2.製作一解密query的數值給,每一個這樣的查詢是一個密
文c
解密c,並將結果寄給
3.製作一個挑戰query,內容為明文對(m0 , m1 )
選擇b ∈ {0,1}
加密m ,並將結果密文c ∗ 寄給 
4.製作更多的解密query,同第二步的步驟,但c ≠ c ∗
5.輸出b ∈ {0,1}
Preliminaries and definitions
自訂選擇密文安全
2
其攻擊成功的機率Adv,PKE
()被定義為
1
| Pr b =  − |
2
這個方案PKE可說是安全可抵抗自訂義選擇
密文攻擊,假如對於有效的,這個攻擊
2
成功的機率Adv,PKE
()可以被忽略不計
如果PKE方案在ROM進行分析,然後hash
function是由random oracle queries替換成合
適的
Preliminaries and definitions
Paillier密碼系統
Key Generation:
1.選擇兩個長度相同的質數p,q,n=pq
∗
∗
2.選擇g ∈ 2 ,g的順序在2 裡面是n的倍
數
3.設定N,g為public key
 = ( − 1,  − 1)為private key
Preliminaries and definitions
Paillier密碼系統
Encryption: 給予public key N,g以及訊息m
∈ 
1.選擇r ∈ ∗
2.輸出密文 c := [ ∙    2 ]
Decryption: 給一private key λ 以及密文c
1.計算m:=
L cλ mod n2
L
gλ
mod n2
 
Preliminaries and definitions
Pillier密碼系統的兩個主要特點是:
1.它是在明文空間的加法同態。
2.訊息、臨時密鑰在解密階段都是可提取的。
相反,在許多密碼系統的問題就像臨時密
鑰丟失,也就是說,即使有私鑰的幫助,
也是不可提取。
事實上,這個屬性是非常重要的,能夠實
現更好的效率。
The proposed IND-CCA2
conversion
Key Generation:
1.選擇兩個長度相同的質數p,q,n=pq 關
係到DCRP,t ≪ |n|
2.選擇g ∈ ∗ 2 ,g的順序在∗ 2 裡面是n的
倍數
3.選擇一個hash function H: {0,1}∗ → 
4.設定(N,g,H)為public key
 = ( − 1,  − 1)為private key
The proposed IND-CCA2
conversion
Encryption: 給予public key (N,g,H)以及訊
息m ∈ {0,1}  −−1
1.選擇r ∈ {0,1}
設定z = [H(m||r)]  2
M = m||r
2.輸出密文 c := [ ∙   2 ]
The proposed IND-CCA2
conversion
Decryption: 給一private key λ 以及密文c
1.計算M’:=
L cλ mod n2
L
gλ
mod n2
 
M ′ as m′ ||r′
′
−′
2.計算z ≔ 
  2
3.若等式z ′ = H(m′ | r ′  2
則回傳m’,否則回傳”invalid”
Security analysis
Theorem4.1 以上方案達到IND-CCA2安全性
≡ DCRA holds
Proof.
使得(z, n) 是DCR問題的一個實例,即z是否為第
n次剩餘在∗ 2 之中。
透過演算法ℬ,可input(z,n)解出DCR,
使用一個IND-CCA2的攻擊者作為子程序。
Security analysis
模擬公開參數:
∗
設定g = 1 + n,其中1+n為2 中順序n的
一個元素。
給 (g,n)
需要的H-values由ℬ提供
Security analysis
模擬H-oracle
當送出H-query( ,  )
ℬ選擇一個亂數α ∈  ,α 
≠   2
回傳α 給
對於所有回傳的值,
ℬ會建立一個H-list( ,  , α )
Security analysis
模擬解密oracle
在解密的query裡面,當query c 被問到時
ℬ先檢查看H-list裡面有沒有資料
有的話直接回傳對應的m
沒有的話回傳”invalid”
Security analysis
模擬解密oracle
當要回答H-query時,ℬ確認答案α 不會
導致無效
並由解密oracle宣布為密文
這提供了一個完美的模擬來生產的有效
密文,不預先作出相應的H-query的機率
是零。
Security analysis
模擬解密oracle
Phase1.
當query結束後,回傳兩個明文m0 , m1
∈ {0,1}  −−1 給ℬ
ℬ隨機選擇一個bit b ∈ 0,1 , r ∈ {0,1}
並設定M = m ||
ℬ回傳給一個挑戰密文
c ∗ = g  ∙   2
z是DCR問題的實例。
Security analysis
模擬解密oracle
Phase2.
被同意製造任何的H-query和比對挑戰密文c ∗
之外的任何解密query。
若製作H-query(0 , )或是(1 , )
則停止game,且ℬ回傳failure
abort於上述原因的機率≤ q  /2
其中q  是H-query的個數
在第二輪結束後,輸出一個對b的猜測值b′
若b′ = ,則ℬ回傳z ∈ Res(n)
若不相等,則回傳z ∈ ∗ 2
Security analysis
模擬解密oracle
令ϵ為合法密文的機率,
可以正確猜到b
這個理論可用以下兩個Lemma解釋
Security analysis
Lemma4.2 當模擬器input z 來自Res(n),
則的view以及隱藏的bit b,在統計上的
聯合分布是沒有區別的。
∗
z來自2 ,則隱
Lemma4.3 當模擬器input
藏bit b的分佈是獨立於的view。
Security analysis
Proof.
提供一個模擬器input z 來自Res(n),
即存在α
其中α =   2
不會有n次方的H-query(α )給z,
合理的假設H(m | r = α
除非m0 ||r或m1 ||r是被問過H-oracle的答
案
Security analysis
Proof.
原因:m0 是相關明文對應於挑戰密文c ∗ 。
現若在第二階段,問到m0 ||r及得到答
案α′
則c ∗ 在(α′ ) = 時會變成一個合法密文
故為了保持c ∗ 的合法性
ℬ必須回應 query(m0 ||r)與α,α 從z開始
Security analysis
Proof.
ℬ應該能找到開n次根號的z,為了回應
query(m0 ||r)
這本身就是對計算複合剩餘問題。
同樣地,當m1 是挑戰密文c ∗ 底層明文。
這就是為什麼ℬ在被問到(m0 ||r)或(m1 ||r)
會輸掉game的原因
Security analysis
Proof.
c ∗ 是一合法密文,除非m0 ||r或m1 ||r是被
問過H-oracle的答案
因此,可以正確猜到b
即ℬ決定z的複合剩餘機率≥ ϵ − q /2
Security analysis
Lemma4.2 當模擬器input z 來自Res(n),
則的view以及隱藏的bit b,在統計上的
聯合分布是沒有區別的。
∗
z來自2 ,則隱
Lemma4.3 當模擬器input
藏bit b的分佈是獨立於的view。
Security analysis
Proof.
∗
當模擬器的input z 來自2
c ∗ 開始z及g  || 的產生
∗
(同樣取自2 )
則挑戰密文c ∗ 是獨立於基底明文m
故隱藏bit b獨立於的view之中。
Comparison
轉換技術
加密
解密
密文展開
FujisakiOkamoto
Pointcheval
1H
1H+1E
|n|+t
2H
2H+1E
2|n|+t
REACT
2H+1SE
2H+1SD
|n|+t+s
GEM
3H+1SE
3H+1SD
|n|+s
PaillierPointcheavl
Proposed
2H
2H
|n|+t+1
1H
1H
|n|+t+1
|n|: 公開模數n的bit長度, t: 增加t個bit
H: hashing, E: Paillier Encryption, s: SE用到的bit數
SE: Symmetric-key encryption
SD: Symmetric-key decryption
Conclusions
本方案展示了一個有效率的IND-CCA2安
全的Paillier-based加密方案,以DCRA為
基底的ROM。
比較其他的轉換法,顯示出此方案是到
目前為止,以加解密的花費、密文的擴
展而言,最有效率的IND-CCA2之Paillier
密碼系統轉換法。
Conclusions
這種效率提升(減少hash的次數)連同本來
的Paillier原始隨機性萃取可能使一個可能
的候選一個高效率的簽密方案,因為它
可能是可行的整合在一個特定的消息m的
簽名在加密m的同時作為臨時密鑰。

similar documents