An interesting challenge for the cryptography community is to design authentication protocols that are so simple that a human can execute them without relying on a fully trusted computer. We propose several candidate authentication protocols for a setting in which the human user can only receive assistance from a semi-trusted computer - a computer that stores information and performs computations correctly but does not provide confidentiality. Our schemes use a semi-trusted computer to store and display public challenges C_i\in[n]^k. The human user memorizes a random secret mapping \sigma:[n]\rightarrow \mathbb{Z}_d and authenticates by computing responses f(\sigma(C_i)) to a sequence of public challenges where f:\mathbb{Z}_d^k\rightarrow \mathbb{Z}_d is a function that is easy for the human to evaluate. We prove that any statistical adversary needs to sample m=\tilde{\Omega}\paren{n^{s(f)}} challenge-response pairs to recover \sigma, for a security parameter s(f) that depends on two key properties of f. Our lower bound generalizes recent results of Feldman et al. [Feldman'15] who proved analogous results for the special case d=2. To obtain our results, we apply the general hypercontractivity theorem [O'Donnell'14] to lower bound the statistical dimension of the distribution over challenge-response pairs induced by f and \sigma. Our statistical dimension lower bounds apply to arbitrary functions f:\mathbb{Z}_d^k\rightarrow \mathbb{Z}_d (not just to functions that are easy for a human to evaluate). As an application, we propose a family of human computable password functions f_{k_1,k_2} in which the user needs to perform 2k_1+2k_2+1 primitive operations (e.g., adding two digits or remembering a secret value \sigma(i)), and we show that s(f) = \min{k_1+1, (k_2+1)/2}. For these schemes, we prove that forging passwords is equivalent to recovering the secret mapping. Thus, our human computable password schemes can maintain strong security guarantees even after an adversary has observed the user login to many different accounts.

What can a human compute in his/her head that a powerful adversary cannot infer? To answer this question, we define a model of human computation and a measure of security. Then, motivated by the special case of password creation, we propose a collection of well-defined password-generation methods. We show that our password generation methods are humanly computable and, to a well-defined extent, machine uncrackable. For the proof of security, we posit that password generation methods are public, but that the human’s privately chosen seed is not, and that the adversary will have observed only a few input-output pairs. Besides the application to password generation, our proposed Human Usability Model (HUM) will have other applications.

Keyword-based image search engines are hindered by the lack of proper labeling for images in their indices. In many cases the labels do not agree with the contents of the image itself, since images are generally indexed by their filename and the surrounding text in the Web page. Another popular approach to image search, content based image retrieval, suffers from a gap between the available low level data and the semantic needs of user searches. To overcome these problems we suggest human annotation of images with natural language descriptions. To this end we present Phetch, an engaging multiplayer game that allows people to attach accurate explanatory text captions to arbitrary images on the Web. People play the game because it is fun, and as a side effect we collect valuable information that can be applied towards improving image retrieval. Furthermore, the game can also be used for other novel applications.

Images on the Web present a major accessibility issue for the visually impaired, mainly because the majority of them do not have proper captions. This paper addresses the problem of attaching proper explanatory text descriptions to arbitrary images on the Web. To this end, we introduce Phetch, an enjoyable computer game that collects explanatory descriptions of images. People play the game because it is fun, and as a side effect of game play we collect valuable information. Given any image from the World Wide Web, Phetch can output a correct annotation for it. The collected data can be applied towards significantly improving Web accessibility. In addition to improving accessibility, Phetch is an example of a new class of games that provide entertainment in exchange for human processing power. In essence, we solve a typical computer vision problem with HCI tools alone.

We address the problem of collecting a database of ""common-sense facts"" using a computer game. Informally, a common-sense fact is a true statement about the world that is known to most humans: ""milk is white,"" ""touching hot metal hurts,"" etc. Several efforts have been devoted to collecting common-sense knowledge for the purpose of making computer programs more intelligent. Such efforts, however, have not succeeded in amassing enough data because the manual process of entering these facts is tedious. We therefore introduce Verbosity, a novel interactive system in the form of an enjoyable game. People play Verbosity because it is fun, and as a side effect of them playing, we collect accurate common-sense knowledge. Verbosity is an example of a game that not only brings people together for leisure, but also collects useful data for computer science.

We introduce Peekaboom, an entertaining web-based game that can help computers locate objects in images. People play the game because of its entertainment value, and as a side effect of them playing, we collect valuable image metadata, such as which pixels belong to which object in the image. The collected data could be applied towards constructing more accurate computer vision algorithms, which require massive amounts of training and testing data not currently available. Peekaboom has been played by thousands of people, some of whom have spent over 12 hours a day playing, and thus far has generated millions of data points. In addition to its purely utilitarian aspect, Peekaboom is an example of a new, emerging class of games, which not only bring people together for leisure purposes, but also exist to improve artificial intelligence. Such games appeal to a general audience, while providing answers to problems that computers cannot yet solve.

We review the field of result-checking, discussing simple checkers and self-correctors. We argue that such checkers could profitably be incorporated in software as an aid to efficient debugging and enhanced reliability. We consider how to modify traditional checking methodologies to make them more appropriate for use in real-time, real-number computer systems. In particular, we suggest that checkers should be allowed to use stored randomness: that is, that they should be allowed to generate, preprocess, and store random bits prior to run-time, and then to use this information repeatedly in a series of run-time checks. In a case study of checking a general real-number linear transformation (e.g., a Fourier Transform), we present a simple checker which uses stored randomness, and a self-corrector which is particularly efficient if stored randomness is employed.

We review the field of result-checking and suggest that it be extended to a methodology for enforcing hardware/software reliability. We thereby formulate a vision for "self-monitoring" hardware/software whose reliability is augmented through embedded suites of run-time correctness checkers. In particular, we suggest that embedded checkers and correctors may be employed to safeguard against arithmetic errors such as that which has bedeviled the Intel Pentium Microprocessor. We specify checkers and correctors suitable for monitoring the multiplication and division functionalities of an arbitrary arithmetic processor and seamlessly correcting erroneous output which may occur for any reason during the lifetime of the chip.

A program correctness checker is an algorithm for checking the output of a computation. That is, given a program and an instance on which the program is run, the checker certifies whether the output of the program on that instance is correct. This paper defines the concept of a program checker. It designs program checkers for a few specific and carefully chosen problems in the class FP of functions computable in polynomial time. Problems in FP for which checkers are presented in this paper include Sorting, Matrix Rank and GCD. It also applies methods of modern cryptography, especially the idea of a probabilistic interactive proof, to the design of program checkers for group theoretic computations. Two structural theorems are proven here. One is a characterization of problems that can be checked. The other theorem establishes equivalence classes of problems such that whenever one problem in a class is checkable, all problems in the class are checkable.

We review the field of result-checking, discussing simple checkers and self-correctors. We argue that such checkers could profitably be incorporated in software as an aid to efficient debugging and reliable functionality. We consider how to modify traditional checking methodologies to make them more appropriate for use in real-time, real-number computer systems. In particular, we suggest that checkers should be allowed to use stored randomness: i.e., that they should be allowed to generate, pre-process, and store random bits prior to run-time, and then to use this information repeatedly in a series of run-time checks. In a case study of checking a general real-number linear transformation (for example, a Fourier Transform), we present a simple checker which uses stored randomness, and a self-corrector which is particularly efficient if stored randomness is allowed.>

Designing Programs to Check Their Work Professor Manuel Blurn Department of EECS UC Berkeley and International Computer Science Institute Berkeley, California Abstract Students, engineers, programmers... are all expected to check their work. Computer programs are not. There are several reasons for this: 1. Computer hardware almost never makes errors -- but that fails to recognize that programmers do! 2. Programs are hard enough to write without having to also write program checkers for them -- but that is the price of increased confidence! 3. There is no clear notion what constitutes a good checker. Indeed, the same students and engi-neers who are cautioned to check their work are rarely informed what it is that makes a proce-dure good for doing so -- but that is just the sort of problem that computer science should be able to solve! In my view, the lack of correctness checks in programs is an oversight. Programs have bugs that could perfectly well be caught by such checks. This talk urges that programs be written to check their work, and outlines a promising and rigorous approach to the study of this fascinating new area.

This paper provides the first systematic investigation of checking approximate numerical computations over subsets of the reals. In most cases, approximate checking is more challenging than exact checking. Problem conditioning, i.e., the measure of sensitivity of the output to slight changes in the input, and the presence of approximation parameters foil the direct transformation of many exact checkers to the approximate setting. Furthermore, approximate checking over the reals is complicated by the lack of nice finite field properties such as the existence of a samplable distribution which is invariant under addition or multiplication by a scalar. We overcome the above problems by using such techniques as testing and checking over similar but distinct distributions, using functions' random and downward self-reducibility properties, and taking advantage of the small variance of the sum of independent identically distributed random variables. We provide approximate checkers for a variety of computations, including matrix multiplication, linear system solution, matrix inversion, and computation of the determinant. We also present an approximate version of Beigel's trick and extend the approximate linear self tester/corrector of [8] and the trigonometric self-Tester/corrector of [5] to more general computations.

The authors initiate a computational theory of statistical tests. Loosely speaking, an algorithm is a statistical test if it rejects a 'negligible' fraction of strings. A statistical test is universal for a class of algorithms if it rejects all (but finitely many) of the strings rejected by each algorithm in the class. They consider the existence and efficiency of universal statistical tests for various classes of statistical tests. They also consider the relation between ensembles passing statistical tests of particular complexity and ensembles which are indistinguishable from uniform by algorithms of the same complexity. Some results refer to relatively simple statistical tests (e.g. those implemented by counter machines).>

The notion of program checking is extended to include programs that alter their environment, in particular, programs that store and retrieve data from memory. The model considered allows the checker a small amount of reliable memory. The checker is presented with a sequence of requests (online) to a data structure which must reside in a large but unreliable memory. The data structure is viewed as being controlled by an adversary. The checker is to perform each operation in the input sequence using its reliable memory and the unreliable data structure so that any error in the operation of the structure will be detected by the checker with high probability. Checkers for various data structures are presented. Lower bounds of log n on the amount of reliable memory needed by these checkers, where n is the size of the structure, are proved.>

Abtract It is shown that many different problems have the same degree of unsolvability. Among these problems are: The Inductive Inference Problem. Infer in the limit an index for a recursive function f presented as f(0), f(1),f(2),…. The Recursive Index Problem. Decide in the limit if i is the index of a total recursive function. The Zero Nonvariant Problem. Decide in the limit if a recursive function f presented as f(0), f(1), f(2),… has value unequal to zero for infinitely many arguments. Finally, it is shown that these unsolvable problems are strictly easier than the halting problem.

This paper investigates the possibility of disposing of interaction between prover and verifier in a zero-knowledge proof if they share beforehand a short random string. Without any assumption, it is proven that noninteractive zero-knowledge proofs exist for some number-theoretic languages for which no efficient algorithm is known. If deciding quadratic residuosity (modulo composite integers whose factorization is not known) is computationally hard, it is shown that the NP-complete language of satisfiability also possesses noninteractive zero-knowledge proofs.

Suppose someone gives us an extremely fast program P that we can call as a black box to compute a function f.Should we trust that P works correctly?A self-testing/correcting pair allows us to: (1) estimate the probability that P(x) 5~ f(x) when x is randomly chosen; (2) on any input x, compute f(x) correctly as long as P is not too faulty on average.Furthermore, both (1) and ( 2) take time only slightly more than the original running time of P.We present general techniques for constructing simple to program self-testing/correcting pairs for a variety of numerical problems, including integer multiplication, modular multiplication, matrix multiplication, inverting matrices, computing the determinant of a matrix, computing the rank of a matrix, integer division, modular exponentiation and polynomial multiplication.

A program correctness checker is an algorithm for checking the output of a computation. This paper defines the concept of a program checker. It designs program checkers for a few specific and carefully chosen problems in the class P of problems solvable in polynomial time. It also applies methods of modern cryptography, especially the idea of a probabilistic interactive proof, to the design of program checkers for group theoretic computations. Finally it characterizes the problems that can be checked.

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.

In this paper, we examine various complexity issues relative to an oracle for a generic set in order to determine which are the more "natural" conjectures for these issues. Generic oracle results should be viewed as parallels to random oracle results, as in [BG]; the two are in many ways related, but, as we shall exhibit, not equivalent. Looking at computation relative to a generic oracle is in some ways a better reflection of computation without an oracle; for example, whereas adding a random oracle allows a deterministic polynomial-time machine to solve any problem in BPP, adding a generic oracle will not help solve any recursive problem faster than it could be solved without an oracle. Generic sets were first introduced by Cohen as a tool for proving independence results in set theory [Co]. Their recursion theoretic properties have also been explored in depth; for example, see [J] and [Ku2]. Some related work using forcing and/or generic sets as tools in oracle constructions can be found in [Ku3], [Do], [P], and [A-SFH]. However, this is to our knowledge the first knowledge the first thorough examination of complexity relative to a generic Oracle.

Two closely-related pseudo-random sequence generators are presented: The ${1 / P}$generator, with input P a prime, outputs the quotient digits obtained on dividing 1 by P. The $x^2 \bmod N$generator with inputs N, $x_0 $ (where $N = P \cdot Q$ is a product of distinct primes, each congruent to 3 mod 4, and $x_0 $ is a quadratic residue $\bmod N$), outputs $b_0 b_1 b_2 \cdots $ where $b_i = {\operatorname{parity}}(x_i )$ and $x_{i + 1} = x_i^2 \bmod N$. From short seeds each generator efficiently produces long well-distributed sequences. Moreover, both generators have computationally hard problems at their core. The first generator’s sequences, however, are completely predictable (from any small segment of $2|P| + 1$ consecutive digits one can infer the “seed,” P, and continue the sequence backwards and forwards), whereas the second, under a certain intractability assumption, is unpredictable in a precise sense. The second generator has additional interesting properties: from knowledge of $x_0 $ and N but notP or Q, one can generate the sequence forwards, but, under the above-mentioned intractability assumption, one can not generate the sequence backwards. From the additional knowledge of P and Q, one can generate the sequence backwards; one can even “jump” about from any point in the sequence to any other. Because of these properties, the $x^2 \bmod N$generator promises many interesting applications, e.g., to public-key cryptography. To use these generators in practice, an analysis is needed of various properties of these sequences such as their periods. This analysis is begun here.

von Neumann's trick for generating an absolutely unbiased coin from a biased one is this: 1. Toss the biased coin twice, getting 00, 01, 10, or 11. 2. If 00 or 11 occur, go back to step 1; else 3. Call 10 a H, 01 a T. Since p[H] = p[1]*p[0] = p[T], the output is unbiased. Example: 00 10 11 01 01 /spl I.oarr/ H T T. Peter Elias gives an algorithm to generate an independent unbiased sequence of Hs and Ts that nearly achieves the Entropy of the one-coin source. His algorithm is excellent, but certain difficulties arise in trying to use it (or the original von Neumann scheme) to generate bits in expected linear time from a Markov chain. In this paper, we return to the original one-coin von Neumann scheme, and show how to extend it to generate an independent unbiased sequence of Hs and Ts from any Markov chain in expected linear time. We give a right and wrong way to do this. Two algorithms A and B use the simple von Neumann trick on every state of the Markov chain. They differ in the time they choose to announce the coin flip. This timing is crucial.

We give a set of conditions that allow one to generate 50–50 unpredictable bits.Based on those conditions, we present a general algorithmic scheme for constructing polynomial-time deterministic algorithms that stretch a short secret random input into a long sequence of unpredictable pseudo-random bits. We give an implementation of our scheme and exhibit a pseudo-random bit generator for which any efficient strategy for predicting the next output bit with better than 50–50 chance is easily transformable to an “equally efficient” algorithm for solving the discrete logarithm problem. In particular: if the discrete logarithm problem cannot be solved in probabilistic polynomial time, no probabilistic polynomial-time algorithm can guess the next output bit better than by flipping a coin: if “head” guess “0”, if “tail” guess “1”

A protocol is presented whereby two adversaries may exchange secrets, though neither trusts the other. The secrets are the prime factors of their publicly announced composite numbers. The two adversaries can exchange their secrets bit by bit, but each fears the other will cheat by sending “junk”bits. To solve this problem we show how each of the two can prove, for each bit delivered, that the bit is good.

KeysA protocol is presented whereby two adversaries may exchange secrets, although neither trusts the other.The secrets are the prime factors of their publicly announced composite numbers.The two adversaries can exchange their secrets bit by bit, but each fears the other will cheat by sending "junk" bits.To solve this problem we show how each of the two can prove, for each bit delivered, that the bit is good.Applications are suggested to such electronic business transactions as signing contracts and sending certified electronic mail.

We give a set of conditions that allow one to generate 50–50 unpredictable bits.Based on those conditions, we present a general algorithmic scheme for constructing polynomial-time deterministic algorithms that stretch a short secret random input into a long sequence of unpredictable pseudo-random bits.We give an implementation of our scheme and exhibit a pseudo-random bit generator for which any efficient strategy for predicting the next output bit with better than 50–50 chance is easily transformable to an “equally efficient” algorithm for solving the discrete logarithm problem. In particular: if the discrete logarithm problem cannot be solved in probabilistic polynomial time, no probabilistic polynomial-time algorithm can guess the next output bit better than by flipping a coin: if “head” guess “0”, if “tail” guess “1”

Let h be a recursive function. A partial recursive function ψ is i.o. (infinitely often) h -complex if every program for ψ requires more than h ( χ ) steps to compute ψ ( χ ) for infinitely many inputs χ . A more stringent notion is that of ψ being a.e. (almost everywhere) h -complex: ψ is a.e. h -complex if every program for ψ requires more than h ( χ ) steps to compute ψ ( χ ) for all but finitely many inputs χ . These two definitions of h -complex functions do not yield the same theorems. Although it is possible to prove of every i.o. h -complex recursive function that it is i.o. h -complex, it is not possible to prove of every a.e. h -complex recursive function that it is a.e. h -complex. Similarly, recursive functions not i.o. h -complex can be proven to be such, but recursive functions not a.e. h -complex cannot be so proven. The construction of almost everywhere complex recursive functions appears much more difficult than the construction of infinitely often complex recursive functions. There have been found no “natural” examples of recursive functions requiring more than polynomial time for all but finitely many inputs. It is shown that from a single example of a moderately a.e. complex recursive function, one can obtain a.e. very complex recursive functions.

An important goal of complexity theory, as we see it, is to characterize those partial recursive functions and recursively enumerable sets having some given complexity properties, and to do so in terms which do not involve the notion of complexity. As a contribution to this goal, we provide characterizations of the effectively speedable, speedable and levelable [2] sets in purely recursive theoretic terms. We introduce the notion of subcreativeness and show that every program for computing a partial recursive function f can be effectively speeded up on infinitely many integers if and only if the graph of f is subcreative. In addition, in order to cast some light on the concepts of effectively speedable, speedable and levelable sets we show that all maximal sets are levelable (and hence speedable) but not effectively speedable and we exhibit a set which is not levelable in a very strong sense but yet is effectively speedable.

New upper and lower bounds are presented for the maximum number of comparisons, f(i,n), required to select the i-th largest of n numbers. An upper bound is found, by an analysis of a new selection algorithm, to be a linear function of n:

This paper is concerned with the nature of speedups.Let f be any recursive function.We show that there is no effective procedure for going from an algorithm f o r f to another algorithm for f that is significantly faster on all but a finite number of inputs.On the other hand, for a large class of functions f, one can go effectively from any algorithm for f to one that is faster on at least infinitely many integers.Finally, if one has an algorithm for a given function f, and if there is an algorithm which is faster on all but a finite number of inputs, then even though one cannot get this faster algorithm effectively, one can still obtain a pseudospeedup: This is a very fast algorithm which computes a variant of the function, one which differs from the original function on a finite number of inputs.

This paper is concerned with the nature of speedups. Let f be any recursive function. We show that there is no effective procedure for going from an algorithm for f to a significantly faster algorithm for f. On the other hand, there is an effective procedure for going from any algorithm to a faster algorithm, provided one has a bound on the size of the algorithm that does the computation faster for all inputs. If no bound on the size of the faster algorithm is known in advance, one can still obtain a pseudo speedup: This is a very fast algorithm which computes a variant of the function, one which differs from the original function on a finite number of inputs.

The number of steps required to compute a function depends, in general, on the type of computer that is used, on the choice of computer program, and on the input-output code. Nevertheless, the results obtained in this paper are so general as to be nearly independent of these considerations. A function is exhibited that requires an enormous number of steps to be computed, yet has a “nearly quickest” program: Any other program for this function, no matter how ingeniously designed it may be, takes practically as many steps as this nearly quickest program. A different function is exhibited with the property that no matter how fast a program may be for computing this function another program exists for computing the function very much faster.