-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1
An implication of proposals like hashcash, MicroMint,
bit gold, etc. is that there is such a thing as intrapolynomial
cryptography. Three motivations for intrapolynomial
cryptography are (a) novel constructions such as MicroMint,
(b) more accurate estimation of the computational cost of
cracking a cipher, and (c) it might be easier to prove lower
bounds, rather than just conjecture them as is the case with
interpolynomial (standard) cryptography. A major drawback
is that there is very little room for error compared
to standard cryptography. So intrapolynomial cryptography may
only be practical in cases where, as in the above mentioned
proposals, or in the application of securely benchmarking remote
machine performance, accurate measurement of cost
rather than prohibitive cost is the main objective.
I propose the following formalization:
f: {0,1}* --> {0,1}* is called a strong k-benchmark function
for machine model M and k>=1 if the following hold:
1. f is computable in O(p(n)) time on M, where p is a polynomial.
2. f does not shrink the input more than q(n,k), where q(n,k)
is a polynomial of degree k.
3. For every randomized algorithm A running on M in time
less than q(n,k)p(n), there exists an N such that for n > N
Pr[A(f(x)) = f^-1(f(x))] < 1/q(n,k)p(n)
In other words, there is no algorithm running faster
than q(n,k)p(n) which can invert f for more than a negligibly
small number of values.
One can similarly define average-case, best-case, and worst-case
k-degree benchmark functions, analogously to one-way functions.
Open question (analogous to the open question in interpolynomial
cryptography of whether one-way functions exist): can one prove (3)
as lower and upper bounds for some function and k>=1 on some
realizable machine model such as RAM-log?
Strong and average case are most apropos to cryptography
related applications. Unfortunately for these
purposes we'd also need
(a) a list of machine models which is comprehensive
of all physically realizable machines, in the sense
that any such machine can be simulated with a very small
overhead, such as constant or O(log(n)), by some model on
the list, and
(b) to prove lower bounds on a benchmark function for all
models on the list
Since this is at least very tedious, one hopes we can in
practice get away with a short list which covers all plausibly
implemented machine architectures. This might work where
for example the total exposure from cracking a protocol
is less than the R&D costs of designing and building a
novel machine architecture to defeat it. Cryptanalyis
would include discovering the machine architectures
optimal for breaking an intrapolynomial cipher.
One practical implication of the above analysis:
it doesn't make sense to talk about the cryptanalysis
or the cost of computation of hashcash, MicroMint, bit gold, etc.
without reference to machine architectures.
-----BEGIN PGP SIGNATURE-----
Version: PGP for Personal Privacy 5.0
Charset: noconv
iQA/AwUBN8Mt0xBo4n9uScSiEQJVWACg4n2ysUUloEdAe9vqDgAtoxeiTFYAmgOz
IzCIz4RmloQrwzVFCPFALHxh
=cI6x
-----END PGP SIGNATURE-----
[EMAIL PROTECTED]
http://www.best.com/~szabo/
PGP D4B9 8A17 9B90 BDFF 9699 500F 1068 E27F 6E49 C4A2
