By reduction, suppose is not . That is break for . Construct R to break for .
, let , let . Compute for times for each . If wins, or , then and wins.
for , .
If
Define good set as:
(w.h.p.=with high probability)
WTS s.t. is large enough.
s.t. for x, . Then
Suppose not. ,
we show
Some distributions:
dist. over is -comp. indist. if PPT distinguisher running in ,
denoted as
dist. over is -pseudorandom if
, . s.t. is -pseudorandom.
is comp. indist. if PPT distinguisher , s.t. suff. large n,
denoted as
is PRG if
An oracle is a (potentially randomized) “black-box” function that can be queried by an algorithm. Specifically, on input query x, the oracle returns .
An oracle algorithm is an algorithm that is given oracle access to an oracle . Namely, can make an arbitrary number of oracle queries to and receive answers during its computation.
A keyed function is PRF if for a fixed , f(k,x) is pseudorandom (not possible because there are exponential 's, even only checking all in linear time will cost exponential time).
The correct definition:
is the uniform distribution of uniformly random functions that maps n-bit strings to n-bit strings.
In the form of a game:
GGM(Goldreich-Goldwasser-Micali) is a way to construct PRF
Let PRG , .
Input: , sample , and output
GOAL: show that and are indistinguishable.
Define
Let
Suppose for contradiction that , where is non-negligible.
By triangle inequality,
By averaging argument, there exists an such that . This breaks the assumption that is a PRG.
Note: t mustn't be exponential of n, otherwise is negligible.
Hint: construct a polynomial number of Hybrids.
Observation: GGM is a binary tree with height , so there are leaf nodes of n-bits string.
Equivalent to replacing the i-th layer of the tree to be all independent . Upper layers(0~i-1) don't matter.
Alice | Bob | |
---|---|---|
pk-> | ||
m'=Dec{sk}(ct) | <-ck |
ct:cipher text,
The channel(pk,ct) may be public(everyone can access it), but assumed to be authenticated(no one can modify content).
may have randomness:
is deterministic, outputting m or (invalid)
CPA: Chosen-Plaintext Attack
Ch | Adv | |
---|---|---|
pk,ct-> | ||
Adv wins if | <-m' |
Secure if
保證的是不能還原全部訊息,但如果被還原部分訊息還是很危險。
Ch | Adv | |
---|---|---|
pk-> | ||
<- | ||
ct-> | ||
wins if | <-b' |
Secure if
Some other people (Eve) may ask Alice what corresponds to a cipher text . And find some patterns in its reaction.
CCA: Chosen-Ciphertext Attack
Ch | Adv | |
---|---|---|
pk-> | ||
<-(Multiple times) | ||
-> | ||
<- | ||
ct-> | ||
<-(Multiple times) | ||
-> | ||
wins if | <-b' |
先試很多次再收問題,然後可以再試很多次。
Secure定義和IND-CPA一樣
限制
等價定義:Adv given access to an oracle
cyclic group:, which includes ${id,g,g2,g3,\ldots,g^{q-1}}
Ex: , where is a prime.
不care group的細節,但大概會是從elliptic curve group來
Suppose some efficient operations:
Hard operation problems:
Ch | Adv | |
---|---|---|
-> | ||
Adv wins if | <-x' |
某些prime簡單,某些prime難
最弱的assumption,要造PKE需要更強的assumption
DDH: decisional Diffie–Hellman problem
Can distinguish and given .
Game就不寫了
滿好用的,可以造PKE
Search version:CDH(computational Diffie–
Hellman)
Given , compute .
El Gamal PKE=
Correctness:
Suppose not, breaks IND-CPA-secure. That is, , such that
Ch | Adv | |
---|---|---|
-> | ||
<- | ||
-> | ||
Adv wins if | <- |
Claim: 給Adv選和只給他選,隨機選是等價的
Ch | R | Adv | ||
---|---|---|---|---|
-> | -> | |||
<- | ||||
-> | ||||
<- | <- |
Lattice-based Assumption
Let be the security parameter, be a modulus(poly or ), and be an error probability distrubution over (usually discrete Gaussian distribution).
A sample from LWE distribution is generated by:
Output
胖度 : discrete Gaussian distribution 中間高起來的寬度(幾標準差)
If , we can easily distinguish them by trying to solve s. is -dimensional and we map to , so is also -dimensional. is -dimensional, so it's unlikely to be solved.
直覺:越胖越難解
會比較簡單一點
因此不會與差太多
Suppose not, breaks IND-CPA-secure. That is, , such that
Ch | Adv | |
---|---|---|
-> | ||
<- | ||
-> | ||
Adv wins iff | <- |
is given
Think of LWE assumption, change the public key given to Adv from to , where .
Claim:
So given , can also win with a non-negligible advantage.
Claim: and are pseudorandom.
where .
Given the cipher text is random, can also solve the message. Impossible!
Let , , ,
where
Then
For the Hybrid argument Step 2
Increase by 1, the result still holds.
The public key includes a matrix, which may be too expensive.
It can be solved by Ring LWE instead of Module LWE.
El Gamel's and Regev's PKE are not IND-CCA-secure.
Assuming RO(Random oracle), given an OW-CPA/IND-CPA-secure PKE, we can transform it into an IND-CCA-secure PKE. Practically, we will simulate the RO with a hash function. For post-quantum security, we need quantum RO.
KEM:可以想像成先用PKE產生一個雙方都知道的random key,然後用SKE。
RO: a deterministic random function, for each input the output is uniformly random. Deterministic means the same input will always lead to the same output.
所有人都共用一個RO
As in GGM. Initialize an empty table. For each query, output the entry if there is, otherwise sample one and return it.
和OW-CPA很像,但加上adversary可以query ,但
更強的版本: 可以call (Enc的隨機性來源)
For an IND-CPA PKE , with a random oracle, we can construct an OW-CCA PKE .
Note that the T transform outputs a deterministic PKE.
R用Adv(breaks OW-CCA) break IND-CPA:
For the
避免攻擊者傳送偽造或變造的訊息給接收者
digital signature scheme= Vrfy=Verify
Signer | Verifier | |
---|---|---|
pk-> | ||
-> |
Completeness:
Adv 給定 ,可以 query Ch 很多次 ,並得到對應的 ,最後若能給出一對 使得 且 沒有出現過,則 Adv 成功偽造(Forge)了一個簽章。這個機率要是negligible( 的 space 很大)
Schnorr signature scheme(in ROM) is group-based:
Signer | Verifier | |
---|---|---|
-> | ||
-> | check if & |
直覺會覺得要破Schnorr無論如何都需要破discrete log
證明需要許多步驟:
An NP relation is a binary relation . Elements of X are called statements. If , y is called a witness for x.
Example:
Prover想證明對於某個問題的某個x,他有答案y,但不想把答案透漏給Verifier,因此:
Prover | Verifier | |
---|---|---|
Commit(Com) -> | ||
<- Challenge(Ch) | ||
Response(Resp) -> |
當y真的是答案(is a witness for x) ,V永遠輸出1:
角括號代表兩者互動過程中V的輸出
一個(P,V)有special soundness,如果有一個PPT algorithm Ext(a witness extractor) such that 若input為 x,與對應的任兩個相異()互動過程 ,Ext可以輸出正確的y,即。
Note: 但是要有同樣的 !
一個(P,V)是HVZK,如果有一個PPT algorithm Sim,input x,輸出的分布與互動過程一樣。
Ex: DL problem:
當中,原本 與 是 uniformly random,而 是兩者 deterministically 決定。但其實 的 marginal probability 也是 uniform 的,所以我們可以先 sample 再算出 。
已知 ,所以 。
且輸出的 distribution 與原本的相同(都是 uniform)
HVZK 的意思是在 verifier 是誠實(c 確實是 random)的情況下,會是 zero knowledge。
Note: 有 Simulator 也不能 forge signature,因為 Verifier 問的 Ch 幾乎不會是 Simulator 生出來的。
Reduction by rewinding
Suppose breaks ID scheme security with advantage , we can construct a reduction that breaks the average hard NP relation.
如果能夠用同樣的 commit 叫 兩次,就能用 special soundness 的 Ext 來找出 witness。
所以需要 rewinding,因為 是一個 PPT algorithm,假設它由兩部分組成,且隨機性是給定的,因此變成 deterministic:
用 good :
Given RO , we can construct a Signature scheme from an ID scheme. In other words, suppose there's an that breaks the EUF-CMA of the transformed signature scheme(acts as a Prover), we can construct a reduction that breaks the ID scheme.
is given access to a RO and a signature oracle , simulate them by:
The key problem is that we need to answer to an interactive transcript but the can only generate a fixed transcript. So, a trivial solution doesn't work, and we have to generate a earlier.
The method is similar to that of FO transformation. Since wins if , it very likely needs to query for the the . So sends one () from the queries of the and set the result to be from .
Ch | Adv | |
---|---|---|
$A\overset{$}\gets \mathbb{Z}_q^{n\times m}$ | -> | |
wins iff | <- |
Additional requirements:
This can be reduced to Lattice problems that are proven to be NP-hard.
is the security parameter, should be sufficiently large(so that there's a solution), is a modulus(suff. large), is the shortness parameter.
不只找到 是 hard,找到隨便一個 也是 hard。
Informal notes:
Prover works in plaintext space, Verifier works in the ciphertext space.
(use non-homogeneous SIS)
However, the SIS Sigma protocol is not a sigma protocol (no special soundness, no HVZK). So, we need to make a version with abort and achieve a type 1 ID scheme.
Reduction:
Use a similar special soundness argument.
Suppose a breaks the ID scheme, we can construct a reduction that breaks the SIS assumption.
samples a by himself and send . similarly supports rewinding. So queries for a same and get , such that and .
Therefore, can get a by:
So can simply outputs .
A problem is that may not be short and maybe 0.(ignore this)
Another problem is that multiple may correspond to the same . Somehow this can be solved.
Simulate 出來的 要 hide ,否則無法在不知道 的情況下 simulate 出來。
但 SIS-based 中, 是 mean 0 的 discrete Gaussian,所以 相當於被平移 ,所以 可能包含一些 的資訊。
解決的關鍵:with abort version。
-protocal for (honest verifier)
For some dishonest verifier, it may get from , and sends . Therefore it can know from . 這個互動過程就無法 simulate,因為 決定後, 就會被 決定,但 不知道 。
A interactive protocal for a NP relation R is ZK if , the interaction of and the output of is computationally indistinguishable(or statistically indistinguishable).
可以互動很多次
For an NP language L, polynomial time s.t. witness s.t. . And witness .
, witness is a map
互動多次
, committer(sender) and receiver
直覺理解: committer 傳送放在箱子裡的 m,receiver 不能打開,但在驗證階段(reveil phase),committer 把鑰匙給 receiver,receiver 可以驗證當初傳的確實是 m。
正式定義:
一樣 binding, hiding 都有可能是 PPT 或 unbounded。但是不能兩個都 unbounded(left as exercise)
For a OWP with its hardcore predicate , we can construct a commitment scheme for 1 bit.
這會是 stat.(perfect) binding,因為一個 adversary 想找出 ,但是 決定後, 和 都決定。
comp. binding,因為如果能區分 會 break HC,而 unbounded adversary 可以直接算出 再算 。
用一個上面的 commitment scheme
Security
Hybrid argument: 從有 witness 的 到沒有 witness 的