Transcript Presentation [PTT] - UCF Computer Science

CRYPTOGRAPHY
COT 6410
AW R A D M O H A M M E D A L I
NESL ISA H TO RO SDAGL I
JO SIAH WO NG
INTRODUCTION
• Cryptography: the field of study that is related to encoded
information. The name comes from combining two Greek words that
mean “hidden word”.
• Encryption: the process of converting plaintext into ciphertext.
• Decryption: the process of converting ciphertext back into plaintext
PERFECT SECRECY
• It is not only important to protect the whole message but also any
partial information.
• The minimal requirement from an encryption is that an eavesdropper
should not be able to tell which message from two random messages
is encrypted with probability much better than ½.
• The assumption that have been made here is that P ≠ NP.
ONE-TIME PAD
• One-time pad is a simple idea of encryption that provides perfect
security.
• Every bit of a one-time pad key is used only once to encrypt a bit of the
message and later this bit is discarded.
• The sender encrypts x by simply sending x ⊕ k. The receiver can recover
the message x from y = x ⊕ k by XORing y once again with k
• The ciphertext is distributed uniformly regardless of the plaintext
message encrypted.
• One-time pad is not a practical solution when we need to securely
exchange information of a big size.
ONE-WAY FUNCTIONS
• One-way functions are used to design secure encryption formulas
with keys shorter than the message’s length.
• They are defined as functions that are easy to compute but hard to
invert using polynomial-time algorithms.
• These functions do not give any partial information about the text to
a polynomial time eavesdropper.
• Example: Multiplication functions
– The input
x Î {0,1}n is treated as two n/2 bit numbers
– Inverting this function is an integer factorization problem
PSEUDORANDOM
GENERATORS
|f(x)| = nc
|x| = n
10011
G
01001010111011101001
K = 10011
f(x) = 01001010111011101001
E(K,M) = E(f(x), M) = C
PSEUDORANDOM
GENERATORS
• Unpredictability implies pseudorandomness
• PRGs: n-bit input >> (n+1)-bit stretch
• PRGs: n-bit input >> (nc)-bit stretch
UNPREDICTABILITY IMPLIES
PSEUDORANDOMNESS
i-1 bits
ith bit
G(x) = 01101 0 …
(l(n) bits)
G is unpredictable
G is pseudorandom
UNPREDICTABILITY IMPLIES
PSEUDORANDOMNESS
G is unpredictable
G(x) = 01101 0 …
B (01101) = 0
G is pseudorandom
A(G(Un)) = 1
A(G(Un)) = 1
A(Ul(n)) = 0
A(Ul(n)) = 0
A(Ul(n)) = 1
A(G(Un)) = 1
A(Ul(n)) = 0
A(G(Un)) = 1
A(Ul(n)) = 0
A(G(Un)) = 0
GOLDREICH-LEVIN THEOREM
x
n
r = ∑ xi ri
i=1
x “sum-and” r
0 0 1 1 0 1
& 1 0 1 0 1 1
0 0 1 0 0 1
x
r
GOLDREICH-LEVIN THEOREM
x
n
r = ∑ xi ri
i=1
x “sum-and” r
ei=0 0 1 0 … 0
ith bit
0 0 1 1 0 1
x
& 1 0 1 0 1 1
r
0+0+1+0+0+1 = 2
x
r=2
0 0 1 1 0 1
x
& 0 0 1 0 0 0
r = ei
0 0 1 0 0 0 = 1
x
r = xi
GOLDREICH-LEVIN THEOREM
• Given: Function f is a one-way permutation
– |x| = |f(x)|
– f is one-to-one
• Assert: Pr[A(f(x), r) = x
r] ≤ 50% + €
• Suppose A could guess x
r with more than P% success.
Then, an algorithm B can get x from f(x).
GOLDREICH-LEVIN THEOREM
• Suppose A could guess x
r with 100% success. Then,
an algorithm B can get x from f(x).
A(f(x), e1) = x
A(f(x), e2) = x
e1 = x1
e2 = x2
…
A(f(x), en) = x
en = xn
x = x1 x2 … xn
ARBITRARILY LONG
STRETCHES
x, r
G
r, 0 … 1 1
x = 1001, r = 0011
f(x) r = f(1010)
f(f(x)) r = 1
…
f l(n)(x)
r=0
0011 = 1101
0011 = 1
ZERO-KNOWLEDGE PROOFS
“I can’t tell you my secret,
but I can prove to you
that I know the secret.”
ZERO-KNOWLEDGE PROOFS
Example: Where is Charlie?
Goal:
1
2
find the reporter Charlie in a big picture,
convince the verifier (me) that you have the
solution without revealing it (neither to me,
nor to the others).
Question: Can you prove to me that you know where Waldo is without
saying anything about where he is?
St éphanie D elaune ( )
Proofs of K nowledge
Sept em ber 6, 2013
4 / 16
ZERO-KNOWLEDGE PROOFS
Example: Where is Charlie?
Goal:
1
2
find the reporter Charlie in a big picture,
convince the verifier (me) that you have the
solution without revealing it (neither to me,
nor to the others).
Question: Can you prove to me that you know where Waldo is without
saying anything about where he is?
St éphanie D elaune ( )
Proofs of K nowledge
Sept em ber 6, 2013
4 / 16
Solution: Get a copy of the picture, cut out Waldo and show it to me.
ZERO-KNOWLEDGE PROOFS
• Zero-knowledge proofs are proofs that are both convincing and yet
yield nothing beyond the validity of the assertion being proved.
−→ introduced 31 years ago by Goldwasser, Micali and Rackoff
[1985]
– Completeness: if the statement is true, the honest verifier will be
convinced of this fact by an honest prover.
– Soundness: if the statement is false, no cheating prover can convince
the honest verifier that it is true.
– Zero-knowledge: If the statement is true, no cheating verifier learns
anything other than this fact.
3-COLORING
3-Coloring of a graph is assigning colors { , ,
} such that no pair
of adjacent vertices are assigned to the same color.
Your Company
Google
Given the graph, how can Bob convince Alice that 3-coloring of this graph is possible
without telling her the solution?
3-COLORING PROTOCOL
{
}k1 {
}k2 {
}k3
(1,4)
Your Company
k1 and k3
Decrypt k1 as
Decrypt k3 as
accept
!=
Google
3-COLORING PROTOCOL
Completeness: If graph is 3-colorable, Verifier will accept the proof with 100%.
Soundness: If the graph is not 3-colorable then there exists at least one edge such
that two adjacent nodes will have the same color.
During any iteration the probability that verifier selects this edge is 1/|E|.
Hence, if not 3-colorable, verifier will reject with probability >= 1/|E|
Zero-knowledge: If the graph 3-colorable, verifier sees two random distinct colors,
does not learn whole coloring information of the graph.
ZERO-KNOWLEDGE
APPLICATIONS
• Credit card payment
→ to prove that you know the secret code without revealing it
• Prove your identity
→ Prove that you belong to a group without revealing who you are
• Vote on an electronic voting system
→ Prove your identity, hide mapping of your identity to your vote.
• To enforce honest behavior in mix net (e.g. e-voting protocols)
• To convince someone that you have solved a Sudoku puzzle without
revealing the solution.
CONCLUSION
• Cryptography, before the introduction of internet, has a military and
bureaucracy use,
• Today it is a very important field that is a part of our daily lives.
• We discussed some of the techniques that have been used in
encryption, one-time pad, one-way functions, pseudorandom
generators, and zero knowledge systems.
ANY QUESTIONS?
REFERENCES
•
Zero-knowledge proofs of Knowledge, Stefanie Delaune.
•
Sanjeev Arora and Boaz Barak. 2009. Computational complexity: a modern approach. Cambridge University Press.
•
Joan Daemen and Vincent Rijmen. 2002. The design of Rijndael: AES-the advanced encryption standard. Springer Science & Business Media.
•
Oded Goldreich and Yair Oren. 1994. Definitions and properties of zero-knowledge proof systems. Journal of Cryptology 7, 1 (1994), 1–32.
•
Shafi Goldwasser, Silvio Micali, and Charles Rackoff. 1989. The knowledge complexity of interactive proof systems. SIAM Journal on
computing 18, 1 (1989), 186–208.
•
Johan Hastad,RussellImpagliazzo,LeonidALevin,andMichaelLuby.1999.Apseudorandomgenerator from any one-way function. SIAM J. Comput.
28, 4 (1999), 1364–1396.
•
Russell Impagliazzo and Michael Luby. 1989. One-way functions are essential for complexity based cryp- tography. In Foundations of
Computer Science, 1989., 30th Annual Symposium on. IEEE, 230–235.
•
Jonathan Katz and Yehuda Lindell. 2014. Introduction to modern cryptography. CRC Press.
•
A. De Santis, G. Di Crescenzo, and G. Persiano. 1994. Secret Sharing and Perfect Zero Knowledge. In PROC. OF CRYPTO 93, SPRINGER
VERLAG LNCS SERIES. Springer–Verlag, 73–84.
•
Michael Sipser. 2006. Introduction to the Theory of Computation. Vol. 2. Thomson Course Technology
•
Boston.
Martin Tompa. 1988. Zero knowledge interactive proofs of knowledge (a digest). In Proceedings of the 2nd Conference on Theoretical Aspects of
Reasoning about Knowledge. Morgan Kaufmann Publishers Inc., 1–12.
•
Feng Li and Bruce McMillin. 2014. Chapter Two - A Survey on Zero-Knowledge Proofs. Advances in Computers, Vol. 94. Elsevier, 25 – 69.
DOI:http://dx.doi.org/10.1016/B978-0-12-800161-5.00002-5