[Cryptography] Fuzzy Grover

Mike Hamburg mike at shiftleft.org
Wed Jun 28 02:09:46 EDT 2017


A follow-on to this: it can be shown that the cutoff+grover approach cannot do better than root-mean-square(distribution).

Proof: Let c be the cutoff, and p be pr(x > cutoff).  With O(sqrt(1/p)) work, the adversary will obtain a sample which is > cutoff with high probability.  Its distribution is then

sum_(x in D, x > cutoff) x * pr(x)/p

Here pr(x)/p sums to 1 by definition of p.  By the power means inequality, the sum is less than or equal to 

sqrt( sum_(x in D, x > cutoff) x^2 * pr(x) / p )

with equality if there is only one value above the cutoff.  Computing the ratio of expectation to work, the sqrt(p) cancels leaving

sqrt( sum_(x in D, x > cutoff) x^2 * pr(x) )

This is at most root-mean-square(D), with equality iff there are no nonzero values less than the cutoff.  Thus, the best you can do is RMS(D), with equality iff the distribution takes on at most one nonzero value, in which case it’s just Grover search.

I still don’t know better if there’s a better algorithm than cutoff+Grover, but it does seem reasonable to hope that you can’t generically do better than RMS(D).

Cheers,
— Mike

> On Jun 27, 2017, at 12:00 AM, Mike Hamburg <mike at shiftleft.org> wrote:
> 
> Hello Crypto list,
> 
> I’m curious about quantum solutions to a variant of search.
> 
> Suppose I have a distribution D on the interval [0,1], and a function F(seed) which samples from D using a random oracle.
> 
> An adversary wants to find seeds such that F(seed) is large, and in particular wants to write a quantum algorithm that maximizes the expectation of F(seed).
> 
> If the distribution is only supported on the endpoints {0,1}, then this is just search and Grover is known to be optimal.  With t quantum oracle evaluations, it produces expectation something like min(1, t^2 * pr(1)).
> 
> But what if it’s not just {0,1}?  Grover can still be applied, just by setting a cutoff x and searching for seeds where F(seed) > x.  But is this optimal, or is there some kind of “fuzzy Grover’s algorithm” that improves on it?
> 
> Thanks,
> — Mike_______________________________________________
> The cryptography mailing list
> cryptography at metzdowd.com
> http://www.metzdowd.com/mailman/listinfo/cryptography

-------------- next part --------------
A non-text attachment was scrubbed...
Name: smime.p7s
Type: application/pkcs7-signature
Size: 3571 bytes
Desc: not available
URL: <http://www.metzdowd.com/pipermail/cryptography/attachments/20170627/db7404e6/attachment.bin>


More information about the cryptography mailing list