Blockchain Papers

和夫 太田

No abstract is available for this record.

Uriel Feige, Amos Fiat, Adi Shamir

No abstract is available for this record.

Martin Tompa

Suppose an associate handed you a 500 digit number N, and informed you, know the prime factorization of N. What would convince you of the truth of your associate's statement? If your associate could be persuaded to reveal the factorization to you, a few simple tests would convince you of the statement's truth. Unfortunately the associate responds to this request by saying, factorization is a secret. In fact, I would like to convince you that I know the factorization of N without divulging any other useful information. How can you hope to be convinced that your associate is not deceiving you? Needless to say, a primality testing algorithm quickly reveals N to be composite, but your favorite factorization algorithms make no progress whatever. These seemingly irreconcilable positions (the associate's unwillingness to reveal any knowledge, your unwillingness to accept your associate's statement without proof) are reconcilable through a protocol known as a zero interactive proof, introduced by Goldwasser, Micali, and Rackoff [15] in 1985. Informally, an interactive proof is a pair of protocols executed by two parties, called the and the whereby the prover attempts to convince the verifier of the validity of some proposition II. The prover, even by deviating from its protocol, should not be able to convince the verifier of the truth of II if, in fact, II is false. An interactive proof is zero knowledge if the verifier, even by deviating from its protocol, cannot gain any information from the prover (other than the validity of II) that it could not have derived efficiently itself. More specifically, for any verifier that outputs after interacting with the prover, there is an algorithm that, without benefit of interacting with the prover, produces outputs from a distribution indistinguishable from that of the verifier. The interested reader can find careful definitions of these notions in [20]. The particular problem of of factorization will be left on the hook until the last section. The intervening sections contain some interesting historical digressions.

Kentaro Kizaki

No abstract is available for this record.

James Gleick

LOOKING FOR GOD'S FOOTPRINTS / James Gleick "Have you ever thought, Angelica," said Persse, "what a remarkable thing it is that the moon and the sun look to our eyes approximately the same size? . . . The odds against it happening by chance must be billions to one." "You don't think it was by chance?" "I think it's one of the great proofs of a divine creator," said Persse. "I think He had an eye for symmetry." —David Lodge, "Small World" SURE, IT'S EASY TO make fun. Our planet flies through space more smoothly than any airplane, covered with water yet never spilling a drop, so it must have had a Designer. Our eyes display too complex an architecture to be reached by random mutations, so they must have had a Biological Engineer. Our atmosphere contains just enough oxygen, just enough carbon to support life, so it must have had an Environmental Consultant. New York City offers a brilliantly conceived breeding ground for cockroaches; surely, therefore, we can deduce the existence of a cockroach deity. The so-called argument from design—from design, that is, to the existence of God—had barely been thought up before it was being satirized, and you can't always tell the serious versions from the parodies. But lately science has been upping the ante. No one cares any more that the moon is unusually large (although some have argued seriously that its tidal washing and splashing may have been a precondition for life's forward march out of the primordial oceans). Nowadays we have the incredibly well-tuned gravitational force, which, if put ever-so-slightly out of whack, would have turned the universe into a collection of red dwarf stars or blue giant stars, either way presumably inhospitable. We have the strong force in the atomic nucleus—a little stronger or a litter weaker, and stars apparently could not burn at all. The post-Big Bang expansion seems especially problematic. Nonscientists don't realize how lucky they are that the universe got bigger than a Ping Pong ball. When modern physicists and mathematicians calculate the odds against life as we know it, they no longer speak of "billions to one." They toss around numbers like IO40, or IO3"1, or ten to the ten to the thirtieth, a number that cannot even be typeset without either two levels of superscript or a universe full of zeroes. The Missouri Review · Il Certainly, for most of the last millennium, science and faith have been mortal enemies. Science explains; faith builds on the inexplicable. Certainly, amid the agnostic throng, few modern scientists talk openly about belief in God. Yet even so, as science staggers toward its Grand Unified Theory and other grails, some of its practitioners have been seeing an argument for God's existence in the esoterica of high-energy physics. They feel that somewhere in these cosmological coincidences, and also perhaps in the accumulating perfection of modern mathematics, lies the evidence of design that cannot be explained away. Perhaps, they feel, science is finally reaching a level of knowledge that will confirm God, instead of rendering Him superfluous. This is the argument that got its most vigorous and many-sided airing in John Updike's 1986 novel, Roger's Version. Though never quite so earnest, never quite so garrulous about it, some practicing scientists really do share at least a part of the feeling of Updike's pallid, pimpled antagonist, a computer scientist named Dale Köhler, that, as he says: "The most miraculous thing is happening. The physicists are getting down to the nitty-gritty, they've really just about pared things down to the ultimate details, and the last thing they ever expected to happen is happening. God is showing through." Updike's version contains its share of parody, to be sure. It also assembles the richest hodge-podge of scientific shoptalk to be found anywhere in fiction—absolutely authentic in its slangy allusions to cellular automata and fractal patterns and the Mandelbrot set. Dale Köhler knows his science, and he cannot be laughed at when he says, "They've been scraping away at physical reality all these centuries, and...

Gustavus J. Simmons

No abstract is available for this record.

Susan Landau

The game is simple and apparently paradoxical: Prove you know something— an ID number, an access code—without revealing even a single bit of the information itself. The importance is obvious: from credit card numbers to computer passwords, we are increasingly reliant on the secure electronic transmission of what are known as signatures. Yet how can one transmit a signature without potentially revealing to an eavesdropper—or an unethical vendor—all the information he needs in order to masquerade as the sender? Three Israeli computer scientists—Uriel Feige, Amos Fiat and Adi Shamir, of the Weizmann Institute—figured out how to play the game, called zero knowledge proofs of identity. They publicized their result at conferences, and they applied for U.S. patent protection. Ironically the United States said disclosure was detrimental to the national security, and imposed a secrecy order. The three Israelis sought relief, and, with intervention from powerful sources, they got it. Though no one will say for certain, it appears that the National Security Agency (NSA), the government decrypter of secrets, stepped in to help. What the research is, and why the NSA had reason to involve itself, is the story we present here. The technical part has its genesis in the work of Stephen Cook and Richard Karp of the early seventies. Our model of a computer is a RAM, a Random Access Machine. At issue is complexity: on a problem of input size m, how many steps does it take as a function of m to solve the problem? Certain problems are easy; by the obvious method, two m x m matrices can be multiplied in O(m 3) steps (although there are considerably more sophisticated algorithms which require only O(m2-376) steps). Other problems are less obvious. The crucial distinction comes between those problems with polynomial time solutions (the class P), and those which require more than polynomial time. The latter are considered, infeasible. What Cook did was to show that the question Is a boolean expression satisfiable? occupies a special place in the hierarchy of problems. It is solvable in polynomial time by a nondeterministic RAM1 (it is in NP, Nondeterministic Polynomial time), and it is as hard as any other problem in NP (it is complete). If satisfiabilit y has a polynomial time solution, so will any other problem in NP. Karp then showed that a number of combinatorial problems shared that characteristic, called NP-completeness, including kcolorability (can the vertices of a given undirected graph be colored with k colors so that no two adjacent vertices have the same color?), knapsack (given » finite set of integers «,, is there a subset which sums to an integer Kl), This article is the seventeenth in the series of Special Articles published in the Notices. The author, Susan Landau, is an assistant professor of computer science at Weslyan University. She received her Ph. D from M.I.T.; her thesis gave a polynomial time method for determining solvability by radicals. Her research interests include computational complexity and algebra.

David Chaum, Ivan Damgård, Jeroen van de Graaf

No abstract is available for this record.

Joe Kilian

Interactive proof systems are considered in which the best set of possible verifiers is restricted to the class of probabilistic log-space automata. A. Condon (1988) introduced this model and showed that if the protocols are allowed to run for arbitrarily many rounds, exponential-time languages can be proved to a log-space verifier. To better approximate the usual notion of interactive proof systems, a number of researchers have considered a more realistic, further restricted model in which protocols are polynomially bounded, both in the number of rounds of communication and in the number of computational steps allowed to the verifier. A notion of language-recognition zero-knowledge is defined for this model, and it is shown that anything provable in this model can be proved in language-recognition zero-knowledge.>

Joseph Y. Halpern, Yjoram Moses, Mark R. Tuttle

While the intuition underlying a zero knowledge proof system [GMR85] is that no “knowledge” is leaked by the prover to the verifier, researchers are just beginning to analyze such proof systems in terms of formal notions of knowledge. In this paper, we show how interactive proof systems motivate a new notion of practical knowledge, and we capture the definition of an interactive proof system in terms of practical knowledge. Using this notion of knowledge, we formally capture and prove the intuition that the prover does not leak any knowledge of any fact (other than the fact being proven) during a zero knowledge proof. We extend this result to show that the prover does not leak any knowledge of how to compute any information (such as the factorization of a number) during a zero knowledge proof. Finally, we define the notion of a weak interactive proof in which the prover is limited to probabilistic, polynomial-time computations, and we prove analogous security results for such proof systems. We show that, in a precise sense, any nontrivial weak interactive proof must be a proof about the prover's knowledge, and show that, under natural conditions, the notions of interactive proofs of knowledge defined in [TW87] and [FFS87] are instances of weak interactive proofs.

Joe Kilian

Suppose your netmail is being erratically censored by Captain Yossarian. Whenever you send a message, he censors each bit of the message with probability 1/2, replacing each censored bit by some reserved character. Well versed in such concepts as redundancy, this is no real problem to you. The question is, can it actually be turned around and used to your advantage? We answer this question strongly in the affirmative. We show that this protocol, more commonly known as oblivious transfer, can be used to simulate a more sophisticated protocol, known as oblivious circuit evaluation([Y]). We also show that with such a communication channel, one can have completely noninteractive zero-knowledge proofs of statements in NP. These results do not use any complexity-theoretic assumptions. We can show that they have applications to a variety of models in which oblivious transfer can be done.

Louis C. Guillou, Jean-Jacques Quisquater

No abstract is available for this record.

Michael Ben-Or, Shafi Goldwasser, Joe Kilian, Avi Widgerson

Quite complex cryptographic machinery has been developed based on the assumption that one-way functions exist, yet we know of only a few possible such candidates. It is important at this time to find alternative foundations to the design of secure cryptography. We introduce a new model of generalized interactive proofs as a step in this direction. We prove that all NP languages have perfect zero-knowledge proof-systems in this model, without making any intractability assumptions.

Gustavus J. Simmons, George Purdy

No abstract is available for this record.

Manuel Blum, Paul Feldman, Silvio Micali

We show that interaction in any zero-knowledge proof can be replaced by sharing a common, short, random string. We use this result to construct the first public-key cryptosystem secure against chosen ciphertext attack.

Alfredo De Santis, Silvio Micali, Giuseppe Persiano

No abstract is available for this record.

William Aiello, Johan Håstad

A hierarchy of probabilistic complexity classes generalizing NP has recently emerged in the work of [Ba], [GMR], and [GS]. The IP hierarchy is defined through the notion of an interactive proof system, in which an all powerful prover tries to convince a probabilistic polynomial time verifier that a string w is in a language L. The verifier tosses coins and exchanges messages back and forth with the prover before he decides whether to accept w. This proof-system yields "probabilistic" proofs: the verifier may erroneously accept or reject w with small probability. In [GMR] such a protocol was defined to be a zero-knowledge protocol if at the end of the interaction the verifier has learned nothing except that w ∈ L. We study complexity theoretic implications of a language having this property. In particular we prove that if L admits a zeroknowledge proof then L can also be recognized by a two round interactive proof. This complements a result by Fortnow [F] where it is proved that the complement of L has a two round interactive proof protocol. The methods of proof are quite similar to those of Fortnow [F]. As in his case the proof works under the assumption that the original protocol is only zero-knowledge with respect to a specific verifier.

Johannes Sedlmeir, Steffen Schwalm

Zero knowledge protocols provide a way of proving that a statement is true without revealing anything other than the correctness of the claim. Zero knowledge protocols have practical applications in cryptography and are used in many applications. While some applications only exist on a specification level, a direction of research has produced real-world applications. Zero knowledge protocols, also referred to as zero knowledge proofs, are a type of protocol in which one party, called the prover, tries to convince the other party, called the verifier, that a given statement is true. Sometimes the statement is that the prover possesses a particular piece of information. This is a special case of zero knowledge protocol called a zero-knowledge proof of knowledge. Formally, a zero-knowledge proof is a type of interactive proof.

Martin Tompa, Heather Woll

The notion of a zero knowledge interactive proof that one party "knows" some secret information is explored. It is shown that any "random self-reducible" problem has a zero knowledge interactive proof of this sort. The zero knowledge interactive proofs for graph isomorphism, quadratic residuosity, and "knowledge" of discrete logarithms all follow as special cases. Based on these results, new zero knowledge interactive proofs are exhibited for "knowledge" of the factorization of an integer, nonmembership in cyclic subgroups of Zp*, and determining whether an element generates Zp*. None of these proofs relies on any unproven assumptions.

Yair Oren

In this paper we investigate some properties of zero-knowledge proofs, a notion introduced by Goldwasser, Micali and Rackoff. We introduce and classify various definitions of zero-knowledge. Two definitions which are of special interest are auxiliary-input zero-knowledge and blackbox-simulation zero-knowledge. We explain why auxiliary-input zero-knowledge is a definition more suitable for cryptographic applications than the original [GMR1] definition. In particular, we show that any protocol composed of subprotocols which are auxiliary-input zero-knowledge is itself auxiliary-input zero-knowledge. We show that blackbox simulation zero-knowledge implies auxiliary-input zeroknowledge (which in turn implies the [GMR1] definition). We argue that all known zero-knowledge proofs are in fact blackbox-simulation zero-knowledge (i.e. were proved zero-knowledge using blackbox-simulation of the verifier). As a result, all known zero-knowledge proof systems are shown to be auxiliary-input zero-knowledge and can be used for cryptographic applications such as those in [GMW2]. We demonstrate the triviality of certain classes of zero-knowledge proof systems, in the sense that only languages in BPP have zero-knowledge proofs of these classes. In particular, we show that any language having a Las vegas zeroknowledge proof system necessarily belongs to R. We show that randomness of both the verifier and the prover, and nontriviality of the interaction are essential properties of non-trivial auxiliary-input zero-knowledge proofs. In order to derive most of the results in the paper we make use of the full power of the definition of zero-knowledge: specifically, the requirement that there exist a simulator for any verifier, including "cheating verifiers".

Hiroyuki Yoshida

1. A. Weil [3] constructed a universal distribution t on the Weil group.The values of I at various test functions give the contributions from the zeros of L-functions which appear in the .explicitformulas.In this note, we shall construct a universal distribution zi on GL(n) and prove the explicit formula for automorphic L-functions using z/ when n-2.For n 2, to derive such a result, we must assume certain property of characters of infinite dimensional representations of GL(n) over a local field.This property, formulated as Conjecture, seems to lie slightly beyond our present knowledge of harmonic analysis.The distributions A have striking formal resemblance to Weil's one.Furthermore they are related to each other so that zl is the "direct image" of z/ for m n.This is a pleasant fact since we think that a discovery of new functorial properties related to zeros of zeta functions would be crucial for the proof of the Riemann hypothesis.

C. Musès

No abstract is available for this record.

Samuel S. Wagstaff, Kenneth Rosen

P. What is Number Theory? 1. The Integers. Numbers and Sequences. Sums and Products. Mathematical Induction. The Fibonacci Numbers. 2. Integer Representations and Operations. Representations of Integers. Computer Operations with Integers. Complexity of Integer Operations. 3. Primes and Greatest Common Divisors. Prime Numbers. The Distribution of Primes. Greatest Common Divisors. The Euclidean Algorithm. The Fundemental Theorem of Arithmetic. Factorization Methods and Fermat Numbers. Linear Diophantine Equations. 4. Congruences. Introduction to Congruences. Linear Congrences. The Chinese Remainder Theorem. Solving Polynomial Congruences. Systems of Linear Congruences. Factoring Using the Pollard Rho Method. 5. Applications of Congruences. Divisibility Tests. The perpetual Calendar. Round Robin Tournaments. Hashing Functions. Check Digits. 6. Some Special Congruences. Wilson's Theorem and Fermat's Little Theorem. Pseudoprimes. Euler's Theorem. 7. Multiplicative Functions. The Euler Phi-Function. The Sum and Number of Divisors. Perfect Numbers and Mersenne Primes. Mobius Inversion. 8. Cryptology. Character Ciphers. Block and Stream Ciphers. Exponentiation Ciphers. Knapsack Ciphers. Cryptographic Protocols and Applications. 9. Primitive Roots. The Order of an Integer and Primitive Roots. Primitive Roots for Primes. The Existence of Primitive Roots. Index Arithmetic. Primality Tests Using Orders of Integers and Primitive Roots. Universal Exponents. 10. Applications of Primitive Roots and the Order of an Integer. Pseudorandom Numbers. The EIGamal Cryptosystem. An Application to the Splicing of Telephone Cables. 11. Quadratic Residues. Quadratic Residues and nonresidues. The Law of Quadratic Reciprocity. The Jacobi Symbol. Euler Pseudoprimes. Zero-Knowledge Proofs. 12. Decimal Fractions and Continued. Decimal Fractions. Finite Continued Fractions. Infinite Continued Fractions. Periodic Continued Fractions. Factoring Using Continued Fractions. 13. Some Nonlinear Diophantine Equations. Pythagorean Triples. Fermat's Last Theorem. Sums of Squares. Pell's Equation. 14. The Gaussian Integers. Gaussian Primes. Unique Factorization of Gaussian Integers. Gaussian Integers and Sums of Squares.

Lance Fortnow

A Perfect Zero-Knowledge interactive proof system convinces a verifier that a string is in a language without revealing any additional knowledge in an information-theoretic sense. We show that for any language that has a perfect zero-knowledge proof system, its complement has a short interactive protocol. This result implies that there are not any perfect zero-knowledge protocols for NP-complete languages unless the polynomial time hierarchy collapses. This paper demonstrates that knowledge complexity can be used to show that a language is easy to prove.