Cryptography

# 訊息

## English

``````Chapter 12 Cryptography

One way function f:
1. f is 1-1 and x inΣ*,|x|^1/k ≦ |f(x)| ≦ |x|^k for some k
2. f in FP
3. f-1 !in FP

RSA的另兩個特性：
1. trapdoor function :
fRSA(x,e,p,c(p),q,c(q)) 有一定比例不是Undefine (是defined)
2. d(x) in P, f(d, fRSA(x, e)) = x

Class UP (unambiguous nondeterministic polynomial)
x |{path | M(path, x) = “yes” }| ≦ 1

Theorem : UP = P iff there are no one way function

Signature :
S(x) = (x, D(d,x))

A -- S(x) -- > B – encrypt D(d,x) -- > E(D(d,x)) = x

B check is x = E(D(d,x)) ?
if “yes” then S(x) is send by A
otherwise S(x) may be a lie.

Commutative :
E(e, D(d,x)) = D(d, E(e,x))

Theorem : RSA encryption system is commutative
D(d, E(e,x)) = (x^e)^d mod pq = (x^d)^e mod pq = E(e, D(d,x))

Interactive Proof System (A,B):

x  A    –- m[1],.. , m[2|x|^k-1] -- > B  x
< -- m[2],.. , m[2|x|^k]    --

m[2i-1] = A(x, m[1], .. , m[2i-2])
m[2i]        = B(x,m[1],..,m[2i-1])
m[2|x|^k] in {“yes”, “no”}

m[I] ≦ |x|^k

(A,B) decide L iff
if x in L  then P((A  ,B) accept x) ≧ 1-(2^-|x|)
if x !in L then P((A’,B) accept x) ≦ 2^-|x| , for all A’≠A

Class IP :
x in IP => x decide by some interactive proof system (A,B)

NP  in IP
BPP in IP

Theorem : Graph Nonisomorphizm in IP
Proof :
-- m[1] = (G,G’) -------------->
A  <-- m[2i-1]=(G, Πi(Gi)) ------  B
-- m[2i]= isIso(G, Πi(Gi)) --->

Πi(Gi) : if b[i] = 1 then G else G’

if (isIso(G,G’))
then m[2] = .. = m[2|x|] = 1
else if m[2] = b[1], .., m[2|x|] = b[|x|]
then B accept it (return iso(G,G’))
else B reject it (don’t believe iso(G,G’))```
```