Beyond Las Vegas And Monte Carlo Algorithms
Functions that use randomness
Shafi Goldwasser is one of the world leaders in cryptography, and is especially brilliant at the creation of new models. This would be true even if she were not one of the creators of IP and ZK; for example, consider her work on fault-tolerant computing. She recently gave one of the best talks at the Princeton Turing Conference, which we just discussed here.
Today I would like to talk about her new model of computation, which was joint work with Eran Gat at the Weizmann Institute.
Well their model is not just off the press, having been posted as an ECCC TR last October, but it is relatively new—and frankly I was not aware of it. So perhaps some of you would like to know about it.
Before I discuss the details of her definition I would like to say: how did we miss it, how could we not have seen it years ago? Or did we—and she is just another example of the principle that we have discussed before—the discoverer of an idea is not the first, nor the second, but the last who makes the discovery. Shafi is the last in this case.
Strange to relate, I (Dick) drafted these words before I knew that one of the previous discoverers was Ken—in an old 1993 draft paper with Mitsunori Ogihara. Ken recalled he had talked with Mitsu about “BPSV” as we finished the previous post, but didn’t discover they had made a paper until late Friday afternoon; it had been an unsuccessful conference submission. Then we discovered that Mitsu and Ken had incorporated the best parts of their draft into a successful conference paper at STACS 1995, of which I had become a co-author. This paper treats puzzles of the kind I thought of during Shafi’s lecture. Déjà vu, but also déjà forgotten.
First A Puzzle
Here is a simple puzzle that is central to Shafi’s work, and I would like to state it first. You can skip this section and return later on, or never. Your choice. But it seems like a cool simple puzzle.
Alice and Bob again have a challenge. An adversary distributes balls— red and black—between two urns and . The division is whatever the adversary wants: each urn could have half black and half red, or one could be all black and the other all red. Alice and Bob have no idea which is the case. Then the adversary gives Alice and , and gives an identical set of urns to Bob.
Pretty exciting? Well Alice and Bob are allowed to sample balls with replacement from their respective urns. Their job is to pick an urn: or . They get “paid” the number of black balls in the urns they pick. So far very simple: their best strategy seems clear, sample and select based on the expected number of black balls. This is nothing new.
The twist is this: Alice and Bob only get paid if they select the same urn. Of course Alice and Bob can agree on a strategy ahead of time, and they also have access to private coins. But they must somehow synchronize their choices. This is what makes the problem a puzzle—at least to me.
A trivial strategy is available to them. Just have each flip a fair coin and take or with equal probability. Note, half the time they will take the same urn and half the time they with get at least half the black balls. Thus their expected payoff in black balls is . This is a pretty dumb strategy, surely they can use sampling to be more clever and beat . But I do not see how. Perhaps this is well known, or perhaps you can solve it. Let us know. Actually we knew, but the question is, what did we know, and when did we know it?
Now on to Shafi’s model, and then we will connect back to this problem.
Shafi’s insight is that deterministic algorithms compute functions. That is, given the same input they will always output the same value. This is just the definition of what a function is: each yields a unique . Okay, seems pretty simple. She then defines an algorithm that uses randomness to be functional provided it also defines a function. Well not exactly. In the spirit of cryptography she actually only insists that the algorithm have two properties:
- The algorithm, over its random choices, has expected polynomial running time.
- The algorithm for any input gives the same output at least of the time.
Of course by the usual trick of simply running the algorithm many times and taking the majority output, we can make the output of the algorithm functional with very small probability of error.
The beautiful point here is that algorithms that use randomness but are functional in the above sense have many cool properties. Let’s look next at some of those properties before we get into some of her results.
Functions are good. And algorithms of the kind Shafi has described are almost as good as functions. Let me just list three properties that they have that are quite useful.
Functions are great for debugging. The repeatability of an algorithm that always gives the same answer to the same input makes it easier to get it right. One of the great challenges in debugging any algorithm is “nondeterministic” behavior. Errors that are reproducible are much easier to track down and fix, while errors that are not—well good luck.
Functions are great for protocols. Imagine that Alice and Bob wish to use some object . They can have one create it and send it to the other. But this could be expensive if the object is large. A better idea is for each to create their own copy of the object. But they must get the same one for the protocol to work properly. So they need to create the object using functions. A simple example is when they both need an irreducible polynomial over a finite field. There are lots of fast random algorithms for this, but the standard ones are not functional.
Functions are great for cloud computing. Shafi points out that one way to be sure that a cloud system is computing the correct value is to have it execute functional algorithms. For example, if you wish to have computed, ask several cloud vendors to compute and take the majority answer. As long as the algorithms they use are functional in her sense, you will get the right value. Pretty neat.
Some Cases and Results
Shafi associates to every decision problem a search problem. For example, if the decision problem is whether a polynomial of degree over a finite field is not identically zero, the search problem is to find for which . The famous lemma we covered here says that unless is tiny we can succeed by picking at random—indeed for any of size we can get . But different random choices may yield different ‘s. Can we, given a circuit for a non-zero , always fixate most of the probability on a single ?
Eran and Shafi’s answer is to use self-reducibility. For each try as the value for , and test the decision problem to see if the resulting substitution leaves a zero polynomial. For the first (in some ordering of ) that says “non-zero,” fix that as the value of , and proceed to . Since each decision is correct with very high probability, the produced this way is unique. This also exemplifies a main technical theorem of their paper:
Theorem 1 A function is feasibly computable in their model if and only if it deterministically reduces in polynomial time to a decision problem in .
Another example takes primes such that divides and produces a number , , such that is not congruent to any -th power modulo . Such an is easy to find by random sampling and then test by verifying that
But again different random choices yield different ‘s. They show how to make unique by using as a subroutine a randomized routine for finding -th roots that itself is made functional.
Both theirs and Mitsu and Ken’s draft paper mention the open problem of finding a generator for a given prime , namely whose powers span all of . Eran and Shafi show uniqueness is possible with high-probability if one is given also a prime dividing such that is small, namely is bounded by a polynomial in . Of course for many there are no such , but large characterizes strong primes which are useful in cryptography.
Shafi’s Main Open Problem
The open problem that she emphasized in her talk is: how to find a prime number in a given interval ? The obvious method is to pick a random in and test to see if is a prime. Actually on can find discussions on this issue in works by Eric Bach—for instance this paper (also nice poster by a co-author)—or see here.
This procedure uses randomness in an essential manner, even if one uses the deterministic primality test of AKS. She asks: can one find an algorithm that would select the same prime? Note, if one assumes a strong enough assumption about primes—ERH for example—then it is easy, since the gaps between primes are very small. But without such a strong assumption there could be huge gaps.
I have an idea for this problem. It is based on using a random factoring algorithm. The key insight is that factoring is by definition a function. So no matter how you use randomness inside the algorithm you must be functional. Then I suggest that we pick that are not likely to be prime, but are provably going to have few prime factors. But first this takes us back to the Alice-and-Bob puzzle.
Bob & Mitsu & Ken & Alice
Consider the possibilities. For any input , each possible value has a true probability . If the highest is bounded away from the next—it does not even have to be above 50%—then sufficient sampling will allow both Alice and Bob to observe this fact with high probability, and hence agree on the same .
Actually it suffices for there to be some with bounded away from any other frequency above or below. So long as Alice and Bob know fixed such that has a gap of , and no higher has a gap more than , they will isolate this same with high probability after a polynomial amount of sampling. In fact all we need is bounded below by . This fits in with a general notation for error and amplification in Mitsu and Ken’s draft.
One can regard the themselves as the values, and further regard them as outputs of a randomized approximation scheme. This is how Ken and Mitsu conceived the unique-value problem, and Oded Goldreich also saw this in section 3 of his recent paper on promise problems. Ken and Mitsu proved that it is necessary and sufficient to succeed in the case where there are only two values—that is, given a , compute a function that always produces one of the two values allows. This is the result that went into Section 3 of the published paper.
This brings everything back to the Alice and Bob urn problem, where urn has a true frequency of red balls. Can we beat for one play of the game? Can we devise a strategy that could do better in repeated plays while navigating a larger search tree?
Besides the problems above, I personally do not know what she should call this class of algorithms. The class of functions can be called , but that still does not nicely name the algorithms. Any suggestions?