# Re: A Mathematical One-Way Function.

*From*: jbriggs444 <jbriggs444@xxxxxxxxx>*Date*: Mon, 25 Oct 2010 13:38:42 -0700 (PDT)

On Oct 25, 1:49 pm, Kristian Gjøsteen <kristiag+n...@xxxxxxxxxxxx>

wrote:

jbriggs444 <jbriggs...@xxxxxxxxx> wrote:

Informally speaking, "hard" problems are those problems whose

answers are too big to print. Not those problems whose answers

are too hard to compute. That's uninteresting.

Something went wrong in the translation from formal to informal.

From formal to formal to informal. I think it's a quantifier orderissue. Mark Wooding had it that the choice of TM could be made

after the problem instance had been selected. Wiki requires the

TM to be fixed first. Wiki's version makes more sense.

Try reading the Wikipedia definition as well, and compare.

Right. Some of the same pieces, but not at all the same

definition.

Concretely, we get a (t,eps)-one-way function f:U->V such that for

any A using time at most t (running on some fixed non-stupid computer,

counting the size of the program as part of its time cost),

Pr[ f(A(f(x))) = f(x) ] <= eps,

where x is sampled from the uniform distribution on U .

OK, that seems reasonable. All nice and finite so that you

can have that uniform distribution on a countable space.

Thank you for the pointers.

.

**Follow-Ups**:**Re: A Mathematical One-Way Function.***From:*Kristian Gjøsteen

**References**:**A Mathematical One-Way Function.***From:*adacrypt

**Re: A Mathematical One-Way Function.***From:*unruh

**Re: A Mathematical One-Way Function.***From:*Mark Wooding

**Re: A Mathematical One-Way Function.***From:*jbriggs444

**Re: A Mathematical One-Way Function.***From:*Kristian Gjøsteen

- Prev by Date:
**Re: RSA moduli with common primes** - Next by Date:
**Re: A Mathematical One-Way Function.** - Previous by thread:
**Re: A Mathematical One-Way Function.** - Next by thread:
**Re: A Mathematical One-Way Function.** - Index(es):