# Viraj Pandya
# Homework Assignment 17 - March 30, 2013
# I give permission to post

Help17:=proc():
	print(`VerifyManySteps(G,i,MrNakamura), DCX(S,t,r,sig,K,T,n,X)`):
end:


###### Problems 1-3

###### I spent a couple hours trying to construct my own programs (see further below)
###### to reproduce Manuel Blum's idea of a zero-knowledge proof
###### but didn't finish yet. I also tried to just manipulate the existing VerifyOneStep
###### but I was having issues there with calling MrNakamura from previous tasks

### Number 4
#Using same test cases from hw16.txt and hw16.mw:

#evalf(C(200,1,.05,.5,120,2)) gives      #90.717271291892172197201967857025821436981088750574

# Z form:  C(S,t,r,sig,K,T)
# Maple form: BlackScholesPrice(S,K,T,sigma,r,d)
# S = 200
# K = 120
# T = T-t = 2 - 1 = 1
# sigma = sig = .5
# r = .05
# d = 0 

## BlackScholesPrice(200,120,1,.5,.05,0);
## gives 90.717271291892172197201967857025821436981088750566

# C(S,t,r,sig,K,T) of C16joey.txt works very well! 
# Only the LAST TWO digits are different!


#### Number 5
DCX:=proc(S,t,r,sig,K,T,n,X):

end:

### taken from C16joey.txt
# DC(S,t,r,sig,K,T,n): The approximate value (with n dicrete steps) 
# using the Cox-Ross-Rubinstein discrete version of Black Scholes
# of a European Call option according to the
# famous Black-Scholes formula. Discrete model. 

DC:=proc(S,t,r,sig,K,T,n) local u,d,p,i:
u:=evalf(exp(sig*sqrt((T-t)/n))):
d:=1/u:
p:=(exp(r*(T-t)/n)-d)/(u-d):

evalf(exp(-r*(T-t)) * add( binomial(n,i)*p^(n-i)*(1-p)^i*max(0,S*u^(n-i)*d^i-K), i=0..n )):

end:


######## TRIED/STARTED TO CREATE MY OWN PROGRAMS FOR BLUM'S PROOF ############

# I was going to write one program called Blum(..)
# that would just implement what Blum told us to do all at once
# and output reject (false) if even just 1 of the k rounds
# did not prove that the graph G was a Hamiltonian graph.
# However, in the interest of time, I did not do that.
# Instead, I just modified VerifyOneStep below.

# Summary of the situation to be coded:
# The prover knows how many nodes, labeled 1...n, comprise the graph G.
# Since the prover is given graph G, the prover knows which of the original
# n nodes are adjacent to each other. 
# The prover fixes one and only one Hamiltonian cycle on G where a Hamiltonian
# cycle is a cycle (or path) through the n nodes of G such that each node is
# passed through only once. (The last node of G must then be connected to the first 
# node of G to truly form a "cycle.")
# After this "initialization" of the situation, there are k rounds where the prover
# encrypts the N nodes with a one-to-one mapping, and then the verifier picks
# one of the two options listed in the Blum paper to verify whether there is 
# indeed a Hamiltonian cycle in G.  
# The prover's encryption protocol results in n + binomial(n,2) "encryption boxes."
# The verifier can either ask the prover to unlock all n + binomial(n,2) boxes, or
# ask them to unlock exactly those binomial(n,2) boxes that contain 1's which mean
# that the i,j vertices corresponding to that binomial(n,2) box are adjacent in G.
# In the first case, the verifier just checks that if, for example, node 1 is in 
# locked box i and node 2 is in locked box j, and if they should be adjacent to each
# other in G, then the "binomial box" with i,j should be 1 only for i= and j = 2 (or perhaps i=2 and j=1) but not any other i,j. 
# In the second case, the verifier is just given the "binomial boxes" and is able
# to verify that a Hamiltonian cycle indeed exists.


blumHGraph:=proc(n,p) local HGraph,HCycle:

# Inputs number of nodes/vertices n and a probability p
# required by the method RandHG(n,p) to construct a random Hamiltonian graph.
# Outputs the Hamiltonian Graph and the Hamiltonian Cycle

HGraph:=convert(RandHG(n,p)[1],list):
HCycle:=convert(RandHG(n,p)[2],list):

[ HGraph,HCycle ]:

# It looks like RandHG(n,p) produces a graph with extra edges so you have to
# "find" the Hamiltonian Cycle, but it is given to us (HCycle).

end:



# blumOneRound(HGraph,HCycle,i) inputs the Hamiltonian Graph, HGraph, and the Hamiltonian
# Cycle, HCycle, outputted by my previous program, blumHGraph(n,p), and i 
# which is the verification choice (1 or 2) of the verifier.
# HGraph has n vertices, and these vertices will be encrypted in the exact same 
# manner described by Blum.
# Each vertex v is mapped to some encryption box B such that
# if, for example, we are talking about some vertex v=i 
# then this v=i can be mapped to any B=j. In other words,
# the mapping v->B is one-to-one (there are only n boxes, B), but
# it is not from v[i]->B[i].
# The probability of v[i] being mapped to some B[j] is 1/(n!). 
# Remember that the mapping is one-to-one so v[i] can't be mapped to 
# some B[j] that is already "taken."
# Then, we can construct a set E = binomial(B,2) consisting of the
# "binomial pair" boxes. This gives us a total of n + binomial(n,2) boxes.

# If the verifier chose option 1, we unlock all n+binomial(n,2) boxes
# and output true if 

##problem: RandHG gives edges, not vertices.


blumOneRound:=proc(n,p) local HGraph:
option remember:

end:


blumZeroKnowledgeProof:=proc(k) local i:
option remember:

end:


################# OLD STUFF #################

#March 28, 12:00noon-1:20pm 2013 Zero-Knowledge proofs

Help:=proc(): print(`RandHG(n,p) , OneStep(G,pi) `):
print(`VerifyOneStep(G,i,MrNakamura) `):

end:

with(combinat):


#RandHG(n,p), inputs a pos. integer n and a rational number
#p and outputs a graph on n vertices that has a Hamiltionian
#cycle pi, and the remaining edges are chosen independently
#with prob. p
RandHG:=proc(n,p) local pi,G, roullete,i,j, justin:
pi:=randperm(n):

roullete:=rand(1..denom(p)):
G:={seq({pi[i],pi[i+1]},i=1..n-1), {pi[n],pi[1]}}:

for i from 1 to n do
 for j from i+1 to n do
   justin:=roullete():
     if justin<=numer(p) then
        G:=G union { {i,j}}:
     fi:
  od:
od:

G,pi:
end:


#Options(G,pi,sig): Given a Hamil. graph G
#and a proof of its Ham. cycle pi (n=nops(pi)) and
######### shouldn't the vertices of this permutation be in order (a list)... 
######### since it's a CYCLE?
#a permutation sig, prepare both options
#either show your enemy the image of the graph
#under sig, OR, show the Hamiltonian cycle
Options:=proc(G,pi,sig) local G1,pi1,i,n,H:
n:=nops(pi):
G1:=subs({seq(i=sig[i],i=1..n)},G):
H:=subs({seq(i=sig[i],i=1..n)},pi):
# H is a graph too, but it's just G re-labeled so that each node is passed through once
# sig is the transformation also known as a one-to-one mapping from 
[G1,sig,H]:
end:



OneStep:=proc(G,pi) local n,coin,sig,tomas:
n:=nops(pi):
sig:=randperm(n):
tomas:=Options(G,pi,sig):

coin:=rand(1..2)():

if coin=1 then
 RETURN(1,[op(1..2,tomas)]):
else

# The Blum paper says to return the Hamiltonian cycle only.
# We don't return the n individual encrypted boxes/nodes of G.
# Only the so-called "binomial(n,2)" boxes containing "1" (not "0"). 
# Of course we didn't do it that way, we are returning H which is a
# Hamiltonian graph so the verifier needs to check whether H is indeed
# a Hamiltonian graph.
# Either way, only return H.

 RETURN(2,tomas[3]):
fi:
end:



VerifyOneStep:=proc(G,i,MrNakamura) local G1,sig,G1a,H,t,n,pi:
# MrNakamura is the 2nd output from OneStep which is a list
# containing either the encrypted graph G1 and the encryption mechanism
# sig (for the verification option i=1), or the Hamiltonian graph H 
# (for the verification option i=2).
# In verification option 1, what we already did in class seems to be correct:
# Just apply the sig mapping to the original graph G to get a new graph G1a 
# and if that new graph equals the given graph G1

# In verification option 2, what we did is incorrect because the verifier should
# only be given the Hamiltonian graph H and check that indeed H is a 
# Hamiltonian graph. This is a "proof" for the existence of a Hamiltonian graph
# from the edges of the original graph G, but we are not giving the verifier the 
# one-to-one encryption mapping.

# How do we access MrNakamura from the OneStep(G,pi) if we are not given pi?


n:=nops(MrNakamura[2]):
if i=1 then 
 G1:=MrNakamura[1]:
 sig:=MrNakamura[2]:
 G1a:=subs({seq(i=sig[i],i=1..n)},G):

  RETURN(evalb(G1=G1a)):
else
 H:=MrNakamura[2]:
 n:=nops(H):
evalb({seq({H[t],H[t+1]},t=1..n-1),{H[n],H[1]}} minus G1 ={}):
fi:

end: