sample questions for Spring semester 2010
NOTES--
Final is on May 17 3:30- 5:30 ITE 241
If you do not plan to take the final please let me know as soon
as possible....certainly no later than May 15
Hours -- TBA
You are responsible for all of Singh's book. You should take a
good 'look' at it.
Recall that-------************************************************
********************************************************************
The various points needed for each grade are:
points %
A 760* 87
B 648** 74
C 590 67
D 437 50
* In order to receive an A, a student must accumulate at least 760
points and have an average of at least 83 on the exams.
** In order to receive a B, a student must accumulate at least 648
points and have an average of at least 73 on the exams.
Incomplete grades are given only under
extreme conditions described by University policy for granting
incompletes.
***********************************************************************
***********************************************************************
topics -----
Hashing
basic properties
examples
Steganography
Protocols
Diffie-Hellman key exchange
man-in-the-middle
Fair Poker
Zero Knowledge
Secret Sharing
Oblivious transfer
Quantum Cryptography
binary key exchange
quantum factoring
some 'review' type questions
**No answers posted for these questions...
Secret Sharing - (Threshold methods)
____________________________________________________________________________
1.
a) Suppose the Master key is obtained from the polynomial
x^3 + 3*x^2 + x + 20 in mod 31 arithmetic
What is the value of the master key?
c) what is the minimal number of participants would be needed to
reconstruct this key?
2. In the theory of threshold schemes we learned about the idea of
"shadows". Shadows are:
a) passive eavesdroppers
b) 'pieces' used to reconstruct a master key
c) special users whose identities are unknown to others
c) a set of large primes
3. If we implement a threshold scheme with a polynomial h(x)
where
h(x) = (5*x+ ?) mod 11
with shadows (2,7), (3,1), (5,0).
then the give the value of the master key.
Protocols, Zero Knowledge
____________________________________________________________________________
Zero Knowledge___________________________________________________________
2. In the zero knowledge log on procedure discussed in class. The sceptic
(system) reveals a quadratic residue y and a modulus n. Explain
a) what is numeric value is requested from the user on the right
side of the zero knowledge flow chart? (assume the notation
u = z*z mod p and y = x*x mod p)
b) if an adversary is psychic and knows the sceptic is going down the
right side of the flow chart he can pass the required test.
______________________________________Quantum Cryptography____________________
_
1. a) how are bits represented in quantum cryptography?
b) write-down the inequality corresponding to Heisenberg's Uncertainty
Principle. Define each of the terms.
c) let R represent a rectilinear polarizer and D a diagonal polarizer.
Suppose Alice choose the following sequence of orientations
R R D R D D D R D R D D
and sends the sequence 0 0 0 1 1 0 1 0 1 0 0 1
to Bob.
Bob chooses the sequence
R D D R R R D R D D R D
Assuming no eavesdropper what will be the secret key shared by
Alice and Bob?
d) In general, if Alice and Bob both choose a sequence of orientations
(R or D) of length n what would be the average number of cases
of agreement (meaning the number of cases their orientations are the
same)?
e) Eve is eveasdropping on a particular bit. Alice has sent a 0
with an R filter and Eve has a D filter. What is the probability
that Eve will read a 0? a 1?
f) Suppose Eve eavesdrops on every one of n bits. What is the probability
that Eve will be detected by Alice and Bob on a particular bit?
(Assume here that we are only examing cases where Bob and Alice
have used the same orientation of filters).
g) What is the probability that Eve will be detected if all n bits are
taken into consideration?
____________________________________________________________________________
____________________________________________________________________________
----- questions from readings, tape, etc.
1.
2. What is 'wave-particle' duality?
3. Who was Thomas Young? (and what did he observe about the 'nature
of light'?)
4. What do we mean when say that a system is in the 'superposition
of two states'?
5. Singh talks about the 'many-worlds interpretation' of the quantum
world. What does this term mean?
6. If a quantum computer can be sucessfully implemented what will be
the implications for RSA? go into as much detail as you can.
7. What does Peter Shor's algorithm do using quantum computation?
8. "Weisner planned to use the polarisation of photons as a way of
creating dollar bills that ..............." finish the quote.
Other readings---------
Protocols
'Oblivious Protocols'
'Steganography and Steganalysis: An Overview'
'Hash Functions and Other Topics'
'Security of hash functions'
'Overview of Shor's algorithm'
'Grammars and Mimicry'