-----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