Read anywhere, anytime
Description
Subjects
Informations
Published by | mochug |
Reads | 15 |
Language | English |
Epistemic Lessons from Computer Science:
Interactive Proofs and Zero Knowledge
Justin Bledin
December 17, 2007
This paper is situated at the junction of two youthful academic currents. The ﬁrst current
is a philosophical one, with a pioneering group of philosophers of science recently turning their
attention to computer science in earnest, recognizing the Philosophy of Computer Science (PCS)
as a new branch of philosophical inquiry. Current work in this ﬁeld has included discussions on
the nature of computers and computational processes, the relationship between mathematics and
computer science and the position of computer science among the empirical sciences (Eden (2007)
and Colburn (2000) are good examples). The second current is a computational one, with an
‘extroverted complexity theory’ (to use C. Papadimitriou’s term) continuing to disseminate its
thirty-years worth of ideas and inventions across other disciplines. Here it suﬃces to mention the
nowwidespreaduseofNP-completeness,workonbiologicalalgorithmsandthepriceofanarchy,and
the testing of theoretical physics furnished by scientists’ attempts to build a quantum computer.
As part of the ﬁrst current, I am a philosopher interested in computer science. As part of the
second, I am interested in what recent work in theoretical computer science has to contribute to
philosophy, rather than, say, economics or quantum physics. In particular, this paper will look
at two related gems of computer science, the interactive proofs and zero knowledge protocols of
Goldwasser, Micali and Rackoﬀ (1985), and explore what these concepts have to teach philosophers
about proofs and knowledge. Unlike classical mathematical proofs, interactive proofs are dynamic
communications between a prover and veriﬁer where a sequence of messages is exchanged in the
prover’s hope of convincing the veriﬁer of this or that mathematical fact. In the limiting case where
the prover provides the veriﬁer with no additional knowledge beyond the truth of the assertion to
be proved, such a proof is considered zero knowledge. For readers unfamiliar with these concepts, I
begin with an intuitive example of an interactive zero-knowledge protocol in section 1. After then
presenting formal deﬁnitions in section 2, the sections 3 and 4 move on to our epistemic lessons.
1 A Cat and Mouse Game
1Dimitri (the cat) is showing Fievel (the mouse) his new maze . There are two entrances, one on
the north side and one on the south.
1This example is adapted from one in Goldreich (2006: 20) involving Odysseus and the Labyrinth of Aeaea.
12
Dimitri: “Fievel, my little mouse, I bet you cannot traverse my maze. If you can, there is much
cheese for you; if not, a delectable mouse for me!”
Fievel: “But Dimitri, you are a cunning cat! How do I know there is a way through your maze at
all? Prove this to me and I will accept your challenge.”
Dimitri: “You rascal! To give you a proof would be to show you a way through the maze. Then
what fun would we have?”
Fievel: “Not necessarily. You can just drop me at some random spot in the maze. I will then
randomly pick either the North or South gate and you will randomly lead me there. If we repeat
this enough times, I’ll become convinced a path between the gates exists.”
Dimitri: “Indeed, and you still won’t know a path between the gates, just a collection of random
walks from the gates. Brilliant Fievel! Let’s get started then.”
Letusanalyzetheaboveprotocolindetail. Beforethechallengebegins, Fievelhasnoknowledge
of Dimitri’s new maze. If Dimitri is honest, the maze will look like the one on the left with a path
between the north and south entrances (you can verify this). If Dimitri is cunning, no throughfare
will exist, as in the maze on the right. Fievel suggests that in each of K trials, Dimitri drops him
at some random spot in the maze. Fievel then randomly chooses either ‘N’ or ‘S’ and Dimitri must
2lead him by some random walk to the chosen entrance. If Dimitri succeeds in doing so, Fievel
accepts; if not, Fievel rejects. Now if the maze is a fair one, Dimitri will be able to lead Fievel out
3of the maze no matter which entrance he chooses , so Fievel accepts in all K trials. By contrast,
if the maze is a trick, then no matter where Fievel is placed in a particular trial, Dimitri will have
probability only 1/2 of leading Fievel out. In the right maze, for example, if Fievel picks ‘N’, then
Dimitri is defeated; if Fievel picks ‘S’, then Dimitri can lead him out. Iterating this over K trials
Kfor a trick maze, Fievel has probability only (1/2) of accepting in all K trials, or equivalently,
2To make this more precise, assume Dimitri considers all possible acyclic paths from Fievel’s current location in
the maze to the chosen entrance and picks one at random.
3Assumethemazecannotcontainanisolatedregion,i.e.,asetoflocationsfromwhichneitherentranceisreachable.3
Kprobability 1−(1/2) of rejecting in at least one of theK trials. So by following this protocol and
choosingK large enough, Fievel can become convinced with as high a probability as he would like
that the maze is a good one.
Now here is the crucial point: if the maze is fair, then Dimitri can convince Fievel of this fact
while providing no additional knowledge that Fievel could not have gained on his own. To see
this, consider the case where Fievel and Dimitri follow the protocol for the full K trials. By the
completion of the protocol, Fievel has been led from K random spots in the maze along random
walks to either the north or south entrance. He has knowledge of K random walks j ,...,j1 K
and is also convinced that a path exists through the maze. But consider this alternative: for K
trials, Fievel picks one of the entrances at random and begins to walk randomly through the maze,
stopping after some random interval of time has passed and returning back the way he came. In
this case, Fievel is no longer convinced the maze is fair (assume he does not traverse the maze or
exhaust all possible paths) as Fievel can go on these walks in a trick maze as well. But Fievel again
0 0has knowledge of K random walks j ,...,j so this cannot be knowledge gained exclusively in his1 K
interaction with Dimitri. The two alternative protocols are pictured below.
Note that I am not saying Fievel gains no additional knowledge in his interaction with Dimitri
beyond knowledge of the fairness of the maze, only no additional knowledge that he could not have
acquired by himself. To be sure, knowledge of the walks j ,...,j is signiﬁcant and there is even a1 K
chance that the union of some subset of these walks is a path through the maze. The point is that
Fievel could have arrived at the same epistemic state by going for his own walks instead of being
led through the maze by Dimitri. Through slight revisions of the original protocol, this additional
knowledge can also be reduced. Perhaps after Dimitri places Fievel in the maze, he blindfolds
Fievel and only takes the blindfold oﬀ as they approach the chosen entrance. Unless Fievel has an
excellent non-visual sense of direction, knowledge of j ,...,j is now useless.1 K4
2 IP and ZK
Thecatandmouseexamplecapturesthespiritofzero-knowledgeinteractiveproofsperfectly. There
is a repeated dynamic exchange between a prover (Dimitri) and veriﬁer (Fievel) where the prover
attempts to convince the veriﬁer of a particular claim (the maze is a fair one). Both the prover and
veriﬁer can randomize their actions and the prover generally knows something (the maze layout)
thattheveriﬁerdoesnot. Iftheclaimholds,theveriﬁeralwaysacceptsattheendoftheinteraction;
if the claim does not hold, the veriﬁer almost always rejects. When the claim does hold, the veriﬁer
gains no additional knowledge (beyond the validity of the asserted claim) from the interaction that
he could not have gained independently.
These intuitions can be formalized in a computational complexity framework. Introduced by
Goldwasser, Micali and Rackoﬀ (1985), an interactive proof system is a pair of interactive Turing
machines, each with a read-only random tape, write-only work-tape and a communication tape for
sendingmessagestotheothermachine. TheprovermachineP iscomputationallyunboundedwhile
the veriﬁer machine V is polynomial-time (i.e., it has limited computing power). In an interactive
proof, the machines are allowed to interact for multiple trials and in each trial, the prover aims
to convince the veriﬁer of the membership of an input x in a set S by sending messages back and
forth. In the cat and mouse game, for example, Dimitri tries to convince Fievel that his new maze
is contained in the set of all fair mazes with paths between the entrances. The interaction between
4the prover P and veriﬁer V in a particular trial is denoted V ↔P .
A formal deﬁnition of interactive proofs can now be given (Goldreich 2006: 6):
Deﬁnition 1 An interactive proof (V,P) for a set S is a two party game between a probabilistic
polynomial-time veriﬁer V and prover P satisfying the following conditions:
5 Completeness : if x∈S then Pr(V ↔P accepts x) = 1
6 ∗ ∗ Soundness : if x6∈S then for every prover P , Pr(V ↔P accepts x) ≤ 1/2
7The class of sets with interactive proofs is denoted IP .
The completeness condition is straightforward. If the input x lies in S, the prover P can always
convince V of this fact. The soundness condition is more complex. If the input x is not in S (the
maze is a trick), V rejects with probability at least 1/2, though by repeating the interaction over
multiple trials, the soundness error (the probability that V mistakenly accepts the input x) can
∗be made arbitrarily small. The soundness condition must also hold for any possible prover P
that interacts withV, indicating the prover need not be trusted (and hinting at the cryptographic
4This notation is from Trevisan (2007).
5Relaxing the perfect completeness condition to allow for two-sided error (i.e., V is also allowed to occasionally
reject when x∈S) does not increase the power of interactive proofs. (Goldreich 2006: 13)
6 ∗The soundness condition is sometimes relaxed so that it only refers to polynomial-time provers P . In this case,
the condition is called computational soundness and proofs become arguments. (Goldreich 2004: 5)
7A ﬁner hierarchy of classesIP(k(n)) can be deﬁned where for inputx of lengthn andk :N→N,IP(k(n)) is the
class of sets with interactive proofs where the interaction V ↔P involves at most k(n) messages. (Trevisan 2007: 1)5
applications of interactive proofs). Assume for example that Dimitri does not follow the protocol.
He might always drop Fievel in the same spot, or lead him through the maze on previously selected
routes. What the soundness condition ensures is that none of these deviations from the protocol
can trick Fievel enough to impair his better judgment. Irrespective of Dimitri’s actions, Fievel will
still reject a bad maze at least half the time.
8Whereas traditional static proofs (NP proofs ) can be written down in a textbook or journal,
9Goldwasser,MicaliandRackoﬀdescribeinteractiveproofsasthosethatcanbe‘explainedinclass’ :
Informally, in a classroom, the lecturer can take full advantage of the possibility of interacting with the
‘recipients’ of the proof. They may ask questions at crucial points of the argument and receive answers.
This makes life much easier. Writing down a proof that can be checked by everybody without interaction
isamuchhardertask. Insomesense,becauseonehastoanswerinadvanceallpossiblequestions. (1985: 292)
If the intuition here is correct, one would expect interactive proofs to be more powerful than their
static NP counterparts. And in fact, it has been formally proven that they likely are. Later in
this section, I sketch a proof that every set in NP, i.e. whose membership can be decided by
a nondeterministic polynomial-time Turing machine (or equivalently, whose membership can be
veriﬁed by a deterministic polynomial-time Turing machine), is also in IP. This implies that IP
proofs are at least as powerful as NP proofs. But there is also Shamir’s celebrated IP Theorem
10which states that IP =PSPACE. We know NP ⊆PSPACE and it is generally believed that
NP ⊂ PSPACE. If the latter condition holds, then NP ⊂ IP so interactive proofs are more
11powerful than NP proofs.
12Another surprising feature of IP is that given certain intractability assumptions , every set
which has an interactive proof has a zero-knowledge interactive proof as well. Introduced along
with interactive proof systems in Goldwasser, Micali and Rackoﬀ (1985), zero-knowledge proofs are
the limiting cases of IP proofs which are convincing yet provide V with no additional knowledge
beyond the claim x∈S (assuming this holds). This raises immediate conceptual diﬃculties for a
philosopher. What type of knowledge should be considered here? How can we measure the amount
of ‘additional knowledge’ gained in an interaction? The clever stroke used by computer scientists
is to largely sidestep these positive questions altogether and focus solely on the negative, on what
exactly it means to learn nothing from an interaction. Looked at from this angle, characterizing
zero-knowledge becomes tractable: to say the interaction V ↔ P yields no additional knowledge
8Formally, an NP proof system also consists of both prover and veriﬁer machines but there is now only a single
shared tape which the prover can work on and the veriﬁer can only read.
9The cross-examination of a witness in a law court is another nice example of an interactive proof in daily life.
(Goldreich 2006: 4)
10PSPACE is the class of sets whose membership can be decided by a deterministic Turing machine using a
polynomial amount of space on the tape. See Goldreich (2006: 9-12) for a sketch of the proof of the IP Theorem.
11It can be demonstrated that this (potential) added power crucially depends on randomness and soundness error,
leading Goldreich (2006: 7) to write: “The moral is that there is no point to interact with a party whose moves are
easily predictable.”
12i.e., that one-way functions exist; see Goldreich (2004: 6-7).6
otherthanthetruthoftheclaimbeingprovenistosaythatgivenx∈S, theveriﬁerV can simulate
the entire interaction himself. Goldreich (2004: 9) explains, “whatever can be feasibly extracted
[by V] from interaction with [P] on input x∈S, can also be feasibly extracted from x itself. This
meansthatnothingwasgainedbytheinteractionitself(beyondconﬁdenceintheassertionx∈S).”
We have already seen an example of such a simulation in Fievel’s random independent strolls, an
alterative way to generate K random walks through the maze without being led by Dimitri.
Zero knowledge proof systems can be formally deﬁned as follows (Goldreich 2006: 19):
Deﬁnition 2 An interactive proof system (V,P) over a set S is zero-knowledge if for every prob-
∗ ∗abilistic polynomial-time veriﬁer V , there is a probabilistic polynomial-time algorithm S s.t.
∗ ∗ 13 ∗(P,V )(x) and S (x) are computationally indistinguishable for every x ∈ S, where (P,V )(x)
∗ ∗is a random variable representing the output of veriﬁer V after interacting with P on x and S (x)
∗is a random variable representing the output of the simulator S on x.
The class of sets with zero-knowledge proofs is denoted ZK.
∗ ∗Like the veriﬁer V , the simulator machine S has access to a random tape. Consequently, for a
∗given input x, the values (accept/reject) of the simulator’s output, denoted S (x), will be spread
according to some probability distribution. The zero-knowledge condition says that when x ∈ S,
∗the distribution ofS (x) is ‘eﬀectively similar’ (see footnote 13) to the distribution of the output of
∗theinteractionbetweentheproverandveriﬁer(P,V )(x), i.e., ongoodinputs, thepolynomial-time
∗simulator does its job well. Note that zero-knowledge ensures that for any possible veriﬁer V , a
∗simulator S can be found that does the job, indicating that whereas in the soundness condition
for IP proofs it was the prover who could not be trusted, there is now uncertainty regarding the
veriﬁer’s honesty. By asking calculated questions when the protocol asks for random ones,V might
attempt to pry important information from P. In a zero-knowledge system, such attempts are in
vain.
Zero-knowledge has many variants: when the zero-knowledge condition is strengthened so that
∗ ∗the distributions S (x) and (P,V )(x) must be identical (not just computationally indistinguish-
able), we get perfect zero-knowledge interactive proofs and the class PZK; when the condition is
relaxed to allow for minor deviations between the distributions, we get statistical zero-knowledge
14and the classSZK ; when cheating veriﬁers are ignored, we get honest verﬁer zero knowledge and
the classesHVZK, HVPZK andHVSZK; when veriﬁers are allowed to have auxiliary informa-
15tion, we get auxiliary-input zero-knowledge; and so on . These various zero-knowledge systems
have been applied in cryptographic settings, typically to force parties to act according to a prede-
termined protocol. In certain situations, a party may be required to act conditional on some secret
that it does not wish to disclose. By using a zero-knowledge interactive proof system, the secretive
13Roughly,twodistributionsX andY arecomputationallyindistinguishableifnoeﬃcientalgorithmcandistinguish
between them. For a precise deﬁnition, see Goldreich (2004: 7).
14The standard ZK condition deﬁned above is sometimes referred to as computational zero-knowledge.
15For an account of these diﬀerent versions of zero-knowledge, see Goldreich (2004: 9-11).6
7
party can convince the other parties involved that it took the correct action while keeping its secret
hidden (Goldreich 2004: 14 and Goldwasser, Micali and Rackoﬀ: 301-3).
With the antics of Fievel and Dimitri behind us, I conclude this section by presenting a more
sophisticated zero-knowledge protocol. In addition to clarifying the concepts just discussed, the
example establishes that every NP set has a (computational) zero-knowledge interactive proof,
16i.e., NP ⊆ZK . Call a graph 3-colorable if all of its nodes can be colored so that no two nodes
connected by an edge of the graph are given the same color. The problem of Graph 3-colorability
17is to decide whether a particular graph G is in the set of ﬁnite 3-colorable graphs .
Assume prover P knows a 3-coloring of G (a function φ from the nodes of the graph to {1,2,3})
and wants to convince veriﬁer V of this fact. She can use the following protocol:
Prover: randomly select a permutation π over {1,2,3} and for each node i, send V the value
18π(φ(i)) in a locked box .
Veriﬁer: randomly select an edge e = (i,j) from G and send it to P.
Prover: send V the keys to unlock π(φ(i)) and π(φ(j)).
Veriﬁer: unlock π(φ(i)), π(φ(i)) and if π(φ(i)) =π(φ(j)), accept; else, reject.
16The example used is Graph 3-colorability which is NP-complete. As Graph 3-colorability is shown to be in ZK,
any problem in NP can be given a ZK proof by ﬁrst reducing to Graph 3-colorability. In fact, by the ultimate ZK
theorem,IP =ZK (assuming the existence of one-way functions) soZK is likely more powerful thanNP (Goldreich
2006: 24). Given the ultimate ZK theorem, the example also shows that NP⊆IP.
17This example is from Goldreich (2004: 12-14). Additional examples of problems in IP are Graph Non-
Isomorphism(Goldreich2006: 8-9)andQuadraticResiduosity(Goldwasser,MicaliandRackoﬀ1985: 293);additional
examples of problems in ZK are Graph Isomorphism (Trevisan 2007: 2-3; Goldreich 2006: 20-21) and Quadratic
Residuosity (Trevisan 2007: 5-6; Goldwasser, Micali and Rackoﬀ 1985: 298-300).
18The digital analogue of locked boxes are known as commitment schemes which can be implemented so long as
one-way functions exist.6
8
To verify Graph 3-colorability is in ZK, it must be shown that the completeness, soundness and
zero-knowledge conditions hold. Completeness is easy. If φ is a valid 3-coloring of G, so is π◦φ
and for all nodes i,j connected by an edge, π(φ(i)) = π(φ(j)) so V always accepts. By contrast,
if G is not 3-colorable, then φ is not a valid 3-coloring and neither is π◦φ so there must exist
at least one edge e = (i,j) in G for which π(φ(i)) = π(φ(j)). Letting |E| denote the number of
edges in G, the veriﬁer must then select a bad edge with probability at least 1/|E| and reject.
Repeating the protocol enough times in a single trial ensures the soundness condition holds. The
zero-knowledge condition is harder to formally establish and we omit the proof here. Suﬃce it
to say that simulating the interaction in this abstract setting only requires placing two random
19diﬀerent colors in the locked boxes sent to the veriﬁer .
And with that we move on to the epistemic lessons.
3 Lesson: On Proofs
Interactive proofs and zero-knowledge have been heralded by computer scientists as revolutions in
our understanding of proof. In a survey paper on the ‘Theory of Computing’ (TOC), Goldreich
and Wigderson (2001: 3-4) write: “Combining randomness and interaction lead TOC to create
and successfully investigate fascinating concepts such as interactive proofs, zero-knowledge proofs
and Probabilistic Checkable Proofs (PCP). Each of these concepts introduces a deep and fruitful
revolution in the understanding of the notion of proof, one of the most fundamental notions of
civilization.” To be sure, interactive zero-knowledge proofs appear to have marked diﬀerences from
the standard static proofs used by mathematicians. They are dynamic and interactive, allow for
randomnessanderror, andclaimtoprovidenoknowledgebeyondthevalidityoftheassertedclaim.
But are they revolutionary? In this section, I critically examine the apparent diﬀerences between
mathematical proofs and interactive ones, assessing just how ‘deep and fruitful’ are the insights
brought by interactive zero-knowledge proofs on the notion of proof.
It seems repetitive to mention that interactive proofs are dynamic/interactive. But what is less
clear to me is that mathematical proofs are not. Consider this proof of the Pythagorean theorem:
19For more detail, see Goldreich (2006: 23).9
Other examples from mathematics abound: in Henkin’s completeness proof for ﬁrst-order logic,
the sentences of a language are dynamically considered in turn and retained if they are consistent
with earlier ones (Hodges 1997: 12X); in priority arguments in recursion theory, we enumerate sets
in dynamic layered constructions to ensure certain requirements are met (Soare 1987: Chapters
VII and VIII); and for a more interactive example, in Ehrenfeucht-Fra¨ısse back-and-forth games
in model theory, the ﬁctitious players ∀belard and ∃loise take turns choosing elements from two
abstract mathematical structures,∀belard trying to prove them diﬀerent while∃loise tries to prove
them identical (Hodges: 74-81).
At this point, it might be argued that the interactions involved in interactive proofs are of a
fundamentallydiﬀerentsort. ForinexamplesfrommathematicssuchasEhrenfeucht-Fra¨ıssegames,
the interaction enters heuristically in the form of a game, a nonessential mode of presentation used
by the prover to convince the veriﬁer of isomorphic relations between mathematical structures.
And the dynamic elements in the other mathematical examples also stay on the prover side. In
interactive proofs, by contrast, the interaction is between the prover and veriﬁer. But is the same
really not true in mathematics? Looking at mathematical proofs in a wider context involving
conferences and refereed journals, shifting the focus from a printed proof to the mathematical
activity leading to its publication, the proofs lose their static ﬁxed ﬂavor. Now this is somewhat
of a stretch, I know. I do think there is a sharp qualitative diﬀerence between the interaction in
interactive proofs and that found in Ehrenfeucht-Fra¨ısse games or mathematical activity at the
community level. My point is only the weaker one that the interaction/dynamism may not be as
‘revolutionary’ as it initially seems.
Zero-knowledge interactive proofs also allow for randomness and built-in error. Recall that
both P and V have access to a random tape and the deﬁnition of IP proofs explicitly allows the
veriﬁer to mistakenly accept a certain amount of bad inputs. Also recall how the combination of
randomnessandsoundnesserrorlikelymakesIP proofsstrongerthandeterministic‘error-free’NP
proofs. Perhaps one lesson to be learned from interactive proofs is the potential large opportunity
cost of avoiding probabilistic methods and clinging to certainty in mathematics. Don Fallis (1997),
for one, argues there is no epistemic reason for preferring proofs accepted by mathematicians
20over probabilistic proofs. Mathematical proofs such as the classiﬁcation of ﬁnite simple groups
(spread across 500 technical articles) can be just as uncertain as probabilistic proofs and though
mathematical methods arguably provide a conditional guarantee that a particular claim is true (if
the rules of logic were obeyed, the mathematician was not hallucinating, there were no hardware
failureswhenacomputerizedproofwasrun,etc. etc.),Fallisisskepticalthatconditionalguarantees
21have much epistemic worth (p.171-6). To the further objection that probabilistic proofs do not
20In his paper, Fallis considers Adleman’s DNA proofs for determining whether a graph has a Hamiltonian path.
Though this is not an interactive zero-knowledge protocol, Adleman’s methods are probabilistic and can give the
wrong answer (they have perfect soundness but imperfect completeness). As an aside, I urge the curious reader to
read Fallis’ account of Adleman’s work (p. 167-70). It is remarkable.
21Referring to G¨odel’s proof sketch of the Second Incompleteness Theorem in his 1931 paper which was accepted
by mathematicians, Fallis (p.175) writes: “Making wild guesses, however, provides a conditional guarantee in this
same sense. If I guess correctly that the Goldbach conjecture is true, then the Goldbach conjecture must be true.”10
provide the a priori knowledge required of mathematics, Fallis (p.177-80) responds that a worked-
out account of a priori knowledge that drives a wedge between acceptable mathematical methods
and probabilistic ones has simply not been given.
Fallis does feel that “mathematicians probably do have good reasons (for example, sociological
and/or pedagogical ones) for not using probabilistic methods” (p. 166), just no good epistemic
22ones. NowIagreewithFallisthatincertainsituationsorforspeciﬁcpurposes,probabilisticproofs
may be insuﬃcient. I also agree that mathematicians have no good epistemic reasons for avoiding
23probabilistic methods . Where I disagree withFallisis withhisclaim thatnoqualitative epistemic
reasons exist for preferring deterministic proofs. What Fallis overlooks is that the warrant of
probabilisticproofscruciallydependsondeterministicmethodswhilethereversedoesnothold: the
Miller-Rabin primality testing algorithm is built around Fermat’s little theorem, a number theory
classic; the DNA proofs discussed by Fallis (see footnote 20) piggyback on a base of deterministic
chemical theory; interactive zero-knowledge proofs still require nonprobabilistic checks that the
24completeness, soundness and zero-knowledge conditions hold . By contrast, probabilistic methods
are entirely absent in the proof of Fermat’s Little Theorem and the laws of chemistry on which
DNA proofs hinge. Now I cannot defend my counterpoint in full, as this would seem to require
a comprehensive survey of the deterministic/probabilistic methods used by mathematicians and
computer scientists and how they combine in particular proofs. For now, I am content to have
suggested one good epistemic reason why a mathematician, concerned with purity of methods, may
prefer her static traditional proofs to their heterogeneous probabilistic counterparts.
25In addition to the objections just discussed, Fallis also considers some ‘obvious objections’ to
DNA proofs: they typically prove claims that mathematicians would not call theorems and they
do not provide explanations of why such claims are true. The ﬁrst point is dealt with swiftly by
mention of the Four Color Theorem and G. H. Hardy’s view in ‘A Mathematician’s Apology’ that
specialized combinatorial problems like proving that a particular graph has a Hamiltonian path are
pieces of ‘genuine mathematics’; the second by Fallis’ belief that “while providing understanding is
nice, itisnotrequired.”(p.170)Withzero-knowledgeproofs, bothobjectionsaremorepronounced.
26In a zero-knowledge interactive proof for the Hamiltonian Path problem , the veriﬁer V does not
22Recently, Kenny Easwaran (UC Berkeley philosophy lecture, 19 November 2007) has argued that unlike mathe-
matical proofs, probabilistic proofs are non-tranferable in the sense that anyone reviewing a probabilistic proof must
to some degree trust its author as they cannot reconstruct or follow the exact proof themselves. Transferability, then,
appears to be a good epistemic reason for avoiding probabilistic methods. But I am skeptical. I still do not see much
diﬀerence in being handed an algorithm for Miller-Rabin primality testing and the proof of the Four Color Theorem.
The chance of hardware failure (both on my run of the programs and the original run by the authors) may preclude
me from reconstructing the exact original proof in either case.
23Mathematicians are, after all, perfectly happy buying products oﬀ the Internet, a process whose security depends
on RSA cryptography which in turn depends on Miller-Rabin primality testing.
24Goldreich(2006: 5)writesaboutinteractiveproofs,zero-knowledgeandPCP:“Westressthatthe(meta)theorems
that we shall state regarding these proof systems will be proven in the traditional mathematical sense.”
25Fallis (p.180-185) also spends considerable attention on the objection that Adleman’s DNA proofs are not proofs
at all, but I omit this here.
26As Hamiltonian Path∈NP⊆ZK, such a proof exists.
Access to the YouScribe library is required to read this work in full.
Discover the services we offer to suit all your requirements!