Main Page | Report Page

 

  Science Forum Index » Cryptography Forum » A Mathematical One-Way Function....

Author Message
Bruce Stephens...
Posted: Sun Oct 17, 2010 4:58 am
 
adacrypt <austin.obyrne at (no spam) hotmail.com> writes:

[...]

[quote]I cannot swear to it but I am of the opinion, picked up somewhere in
the past possibly, that a lot of mathematicians are sceptical about
the existence at all of such a thing as a defacto one-way mathematical
function. I claim now that this is one, possibly a mathematical
first.
[/quote]
You haven't defined what you mean by "one-way mathematical function".

The term "one-way function" is generally understood, and sure there's
some doubt about whether such things exist but in practice I don't think
anybody thinks they don't. If P != NP then (I think) that implies that
one-way functions exist (if P = NP then I think it's not known whether
that means that they don't).

[...]
 
jbriggs444...
Posted: Tue Oct 19, 2010 2:52 am
 
On Oct 17, 6:58 am, Bruce Stephens <bruce+use... at (no spam) cenderis.demon.co.uk>
wrote:
[quote]adacrypt <austin.oby... at (no spam) hotmail.com> writes:

[...]

I cannot swear to it but I am of the opinion, picked up somewhere in
the past possibly, that a lot of mathematicians are sceptical about
the existence at all of such a thing as a defacto one-way mathematical
function.  I claim now that this is one, possibly a mathematical
first.

You haven't defined what you mean by "one-way mathematical function".

The term "one-way function" is generally understood, and sure there's
some doubt about whether such things exist but in practice I don't think
anybody thinks they don't.  If P != NP then (I think) that implies that
one-way functions exist (if P = NP then I think it's not known whether
that means that they don't).

[...]
[/quote]
So you're suggesting that a "one-way function" is a function that is
computable using an algorithm in P and has an inverse that is
not computable by any algorithm in P.

Clearly the inverse of any [invertible] function in P can be found in
NP. Make a guess and check it. So if P = NP it's obvious that
one way functions as defined above do not exist.

If P != NP it is possible that they exist, but I see no easy way to
prove it.
 
Mark Wooding...
Posted: Sat Oct 23, 2010 3:46 pm
 
Bruce Stephens <bruce+usenet at (no spam) cenderis.demon.co.uk> writes:

[quote]The term "one-way function" is generally understood, and sure there's
some doubt about whether such things exist but in practice I don't think
anybody thinks they don't. If P != NP then (I think) that implies that
one-way functions exist (if P = NP then I think it's not known whether
that means that they don't).
[/quote]
Wrong way round. If P = NP then one-way functions certainly don't
exist. A preimage works as a perfectly good certificate for any
interesting predicate you might use to define a decision problem based
on your one-way function.

If P /= NP, on the other hand, then we're still not home. Firstly,
one-way functions have to be hard /on average/, while P /= NP only
guarantees that some problems are hard in their worst cases. Secondly,
we don't usually model adversaries as being algorithms in P -- usually
we use BPP, and allow the adversary to make random decisions.

-- [mdw]
 
unruh...
Posted: Sun Oct 24, 2010 1:25 pm
 
On 2010-10-23, Mark Wooding <mdw at (no spam) distorted.org.uk> wrote:
[quote]Bruce Stephens <bruce+usenet at (no spam) cenderis.demon.co.uk> writes:

The term "one-way function" is generally understood, and sure there's
some doubt about whether such things exist but in practice I don't think
anybody thinks they don't. If P != NP then (I think) that implies that
one-way functions exist (if P = NP then I think it's not known whether
that means that they don't).

Wrong way round. If P = NP then one-way functions certainly don't
exist. A preimage works as a perfectly good certificate for any
interesting predicate you might use to define a decision problem based
on your one-way function.

P=NP really has nothng to do with oneway functions. A one way function[/quote]
is one where the inverse is much harder than the forward evaluation.
Whether that "difficulty" is L^1000 vs L or e^L vs L is really
irrelevant since the limit as L goes to 10^10^10^10 or bigger ihas
nothing to do with anything anyone can ever do. ( P and NP are notions
associated with the limit as L goes to infinity).

Ie, one way funtions do exist even if P=NP. All crypto is very very
finite.

[quote]If P /= NP, on the other hand, then we're still not home. Firstly,
one-way functions have to be hard /on average/, while P /= NP only
guarantees that some problems are hard in their worst cases. Secondly,
we don't usually model adversaries as being algorithms in P -- usually
we use BPP, and allow the adversary to make random decisions.

-- [mdw][/quote]
 
jbriggs444...
Posted: Mon Oct 25, 2010 4:51 am
 
On Oct 24, 8:19 pm, Mark Wooding <m... at (no spam) distorted.org.uk> wrote:
[quote]unruh <un... at (no spam) wormhole.physics.ubc.ca> writes:
P=NP really has nothng to do with oneway functions. A one way function
is one where the inverse is much harder than the forward evaluation.

I really wasn't expecting my statement to be controversial.
[/quote]
Well, you have contradicted yourself, at one point saying that P !NP
implies the existence of one way functions and at another point
saying that P/= NP was not sufficient for the existence of one way
functions.

[quote]You need to be really careful here in defining a sound notion of `much
harder'.  The usual notion, for cryptography, and the one I used, is
asymptotic; see, for example, Goldreich's /Foundations of Cryptography/.

Consider a computational task of the following form: for a binary
relation R, given an input x, compute an output y such that R(x, y)
holds.  We say that this task is `easy' if there exists a Turing machine
and polynomials p and q, such that, for any n-bit input x, the machine
halts within p(n) steps and outputs y such that R(x, y) holds with
probability at least 1/q(n).  If, for all polynomials p and q, there
exists infinitely many n such that all Turing machines running on n-bit
input x for p(n) steps succeed in producing output y with R(x, y) with
probability less than 1/q(n), then we say that the task is `hard'.
[/quote]
This model seems to depend on the notion of a Turing machine
possibly equipped with a random oracle so that the TM generates a
output that is non-deterministic, but with a fixed, deterministic
distribution.

OK, I get the "easy" side. If there is _one_ Turing machine that
can always guess right (with polynomial bounds on how long it
can compute and how reliably it must guess) then the relation
is easy.

As written, the "hard" side seems uninteresting. "Hard" relations
are of those relations whose graphs are roughly characterized by
being eventually zero everywhere to the left of a line that
corresponds
to a function that grows faster than every polynomial.

[Suppose that this condition were not upheld. Then we could
hard code a TM for row x that computes the least y such that R(x,y).
The only escape clause is if the number of digits in y precludes
printing in p(log2(x)) steps, e.g. if log2(y) > p(log2(x))]

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.

Given this difficulty, I do not see that it is "obvious" how to
define a one-way function within the framework.

If you can elaborate on where I've failed to follow the
exposition, please do so.
 
Kristian Gjøsteen...
Posted: Mon Oct 25, 2010 7:49 am
 
jbriggs444 <jbriggs444 at (no spam) gmail.com> wrote:
[quote]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.
[/quote]
Something went wrong in the translation from formal to informal.

Try reading the Wikipedia definition as well, and compare.

Wikipedia has a nice informal definition as well.

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 .

--
kg
 
jbriggs444...
Posted: Mon Oct 25, 2010 10:38 am
 
On Oct 25, 1:49 pm, Kristian Gjøsteen <kristiag+n... at (no spam) math.ntnu.no>
wrote:
[quote]jbriggs444  <jbriggs... at (no spam) gmail.com> 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.
[/quote]
From formal to formal to informal. I think it's a quantifier order
issue. 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.

[quote]Try reading the Wikipedia definition as well, and compare.
[/quote]
Right. Some of the same pieces, but not at all the same
definition.

[quote]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 .
[/quote]
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.
 
Kristian Gjøsteen...
Posted: Mon Oct 25, 2010 10:49 am
 
jbriggs444 <jbriggs444 at (no spam) gmail.com> wrote:
[quote]On Oct 25, 1:49 pm, Kristian Gjøsteen <kristiag+n... at (no spam) math.ntnu.no
wrote:
jbriggs444  <jbriggs... at (no spam) gmail.com> 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 order
issue. 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.
[/quote]
Why would the quantifier order matter here?

(I forgot to mention that I don't know anything about complexity theory.)

--
kg
 
Mark Wooding...
Posted: Mon Oct 25, 2010 3:20 pm
 
jbriggs444 <jbriggs444 at (no spam) gmail.com> writes:

[quote]Well, you have contradicted yourself, at one point saying that P != NP
implies the existence of one way functions and at another point saying
that P/= NP was not sufficient for the existence of one way functions.
[/quote]
What? No. I never said that P /= NP implies one-way functions. I said
it was /necessary/ but not /sufficient/.

(At least, I hope so; it's possible that a misstatement slipped through
during editing, but a I didn't notice anything rereading just now. If
you think I said otherwise, please point out where.)

[quote]This model seems to depend on the notion of a Turing machine
possibly equipped with a random oracle so that the TM generates a
output that is non-deterministic, but with a fixed, deterministic
distribution.
[/quote]
The idea of a probabilistic Turing machine is that the machine is
equipped with an additional tape contain a uniformly distributed random
string. At each step, the machine reads the tape, advances one cell
along it, and uses the symbol it read as an additional input to its
state transition function. It's not clever to talk about things being
`deterministic' or `nondeterministic', because those terms have other
meanings in complexity theory.

[quote]As written, the "hard" side seems uninteresting. "Hard" relations are
of those relations whose graphs are roughly characterized by being
eventually zero everywhere to the left of a line that corresponds to a
function that grows faster than every polynomial.
[/quote]
I'm sorry, I don't follow this at all.

[quote][Suppose that this condition were not upheld. Then we could
hard code a TM for row x that computes the least y such that R(x,y).
The only escape clause is if the number of digits in y precludes
printing in p(log2(x)) steps, e.g. if log2(y) > p(log2(x))]
[/quote]
This bit I understand. It appears that glossed over a feature, for
which I must apologize. The input x is itself chosen according to some
probability distribution determined by the security parameter n.

[quote]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.

Given this difficulty, I do not see that it is "obvious" how to
define a one-way function within the framework.
[/quote]
Given a security parameter, determine an instance of the one-way
function f, and sample a point x in the domain of f. Compute z = f(x).
Provide (f, z) to the algorithm, and collect its output y. Then set

R = { ((f, z), y) | f(y) = z }.

-- [mdw]
 
jbriggs444...
Posted: Tue Oct 26, 2010 3:02 am
 
On Oct 25, 5:20 pm, Mark Wooding <m... at (no spam) distorted.org.uk> wrote:
[quote]jbriggs444 <jbriggs... at (no spam) gmail.com> writes:
Well, you have contradicted yourself, at one point saying that P != NP
implies the existence of one way functions and at another point saying
that P/= NP was not sufficient for the existence of one way functions..

What?  No.  I never said that P /= NP implies one-way functions.  I said
it was /necessary/ but not /sufficient/.
[/quote]
You are correct, sir. That was not you. I was mistaken about who
said
what.

[quote](At least, I hope so; it's possible that a misstatement slipped through
during editing, but a I didn't notice anything rereading just now.  If
you think I said otherwise, please point out where.)

This model seems to depend on the notion of a Turing machine
possibly equipped with a random oracle so that the TM generates a
output that is non-deterministic, but with a fixed, deterministic
distribution.

The idea of a probabilistic Turing machine is that the machine is
equipped with an additional tape contain a uniformly distributed random
string.  At each step, the machine reads the tape, advances one cell
along it, and uses the symbol it read as an additional input to its
state transition function.  It's not clever to talk about things being
`deterministic' or `nondeterministic', because those terms have other
meanings in complexity theory.
[/quote]
I regard an oracle and a one-way auxiliary tape as functionally
equivalent in this application. Whether you run your RNG ahead
of time and populate a tape or run it on demand -- six of one,
half-dozen of the other.

Your point about the term "deterministic" is well taken.

[quote]As written, the "hard" side seems uninteresting.  "Hard" relations are
of those relations whose graphs are roughly characterized by being
eventually zero everywhere to the left of a line that corresponds to a
function that grows faster than every polynomial.

I'm sorry, I don't follow this at all.
[/quote]
You wrote:

[quote]If, for all polynomials p and q, there
exists infinitely many n such that all Turing machines running on n-bit
input x for p(n) steps succeed in producing output y with R(x, y) with
probability less than 1/q(n), then we say that the task is `hard'.
[/quote]
I read this as:

For all polynomials p and q
There exist infinitely many n such that
For all n bit x
For all Turing machines t
R(x,t(y)) with probability less than 1/q(n)

Doubtless you intended to write something equivalent to

For all polynomials p and q
There exist infinitely many n such that
For all Turing machines t
For all n bit x
R(x,t(y)) with probability less than 1/q(n)

I can argue that my reading is the correct "as written"
interpretation, but it's clear now that it is not the correct
"as intended" interpretation.

[quote]
[Suppose that this condition were not upheld.  Then we could
hard code a TM for row x that computes the least y such that R(x,y).
The only escape clause is if the number of digits in y precludes
printing in p(log2(x)) steps, e.g. if log2(y) > p(log2(x))]

This bit I understand.  It appears that glossed over a feature, for
which I must apologize.  The input x is itself chosen according to some
probability distribution determined by the security parameter n.
[/quote]
Which matters, once the quantifier order is repaired and feeds into
the probability measure. Yes, that makes sense now.

[quote]
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.

Given this difficulty, I do not see that it is "obvious" how to
define a one-way function within the framework.

Given a security parameter, determine an instance of the one-way
function f, and sample a point x in the domain of f.  Compute z = f(x).
Provide (f, z) to the algorithm, and collect its output y.  Then set

        R = { ((f, z), y) | f(y) = z }.
[/quote]
This looks like a way to identify a relation R with a function f so
that
the hardness or easiness of R is used to define whether f is one-way.

But what's "the algorithm"?

Feel free to tell me to "read a book".
 
Kristian Gjøsteen...
Posted: Tue Oct 26, 2010 3:49 am
 
Kristian Gjøsteen <kristiag+news at (no spam) math.ntnu.no> wrote:
[quote]Why would the quantifier order matter here?
[/quote]
Never mind, I got it.

--
kg
 
unruh...
Posted: Tue Oct 26, 2010 4:14 am
 
On 2010-10-25, jbriggs444 <jbriggs444 at (no spam) gmail.com> wrote:
[quote]On Oct 24, 8:19?pm, Mark Wooding <m... at (no spam) distorted.org.uk> wrote:
unruh <un... at (no spam) wormhole.physics.ubc.ca> writes:
P=NP really has nothng to do with oneway functions. A one way function
is one where the inverse is much harder than the forward evaluation.

I really wasn't expecting my statement to be controversial.

Well, you have contradicted yourself, at one point saying that P !=
NP
implies the existence of one way functions and at another point
saying that P/= NP was not sufficient for the existence of one way
functions.

You need to be really careful here in defining a sound notion of `much
harder'. ?The usual notion, for cryptography, and the one I used, is
asymptotic; see, for example, Goldreich's /Foundations of Cryptography/.
[/quote]
An asymptotic definition is just silly. No cryptosystem operates in the
asymptotic regime.

[quote]
Consider a computational task of the following form: for a binary
relation R, given an input x, compute an output y such that R(x, y)
holds. ?We say that this task is `easy' if there exists a Turing machine
and polynomials p and q, such that, for any n-bit input x, the machine
halts within p(n) steps and outputs y such that R(x, y) holds with
probability at least 1/q(n). ?If, for all polynomials p and q, there
exists infinitely many n such that all Turing machines running on n-bit
input x for p(n) steps succeed in producing output y with R(x, y) with
probability less than 1/q(n), then we say that the task is `hard'.
[/quote]
That is a nonesensical definition for crypto purposes. It may have some
use in complexity theory but not crypto.

All crypto operates on finite length inputs and outputs-- and bounded by
small numbers ( compared to Ackerman(5,5) say) and "one way function"
means that on such a bounded input, the inverse is much more difficult
to calculate than the original. (And n^1000 satisfies that criterion
nicely as long as n is longer than say 10.)
Polynomial, non-polynomial, etc are all irrelevant, except for people
who like exact definitions far more than sensible definitions.




[quote]
This model seems to depend on the notion of a Turing machine
possibly equipped with a random oracle so that the TM generates a
output that is non-deterministic, but with a fixed, deterministic
distribution.

OK, I get the "easy" side. If there is _one_ Turing machine that
can always guess right (with polynomial bounds on how long it
can compute and how reliably it must guess) then the relation
is easy.

As written, the "hard" side seems uninteresting. "Hard" relations
are of those relations whose graphs are roughly characterized by
being eventually zero everywhere to the left of a line that
corresponds
to a function that grows faster than every polynomial.

[Suppose that this condition were not upheld. Then we could
hard code a TM for row x that computes the least y such that R(x,y).
The only escape clause is if the number of digits in y precludes
printing in p(log2(x)) steps, e.g. if log2(y) > p(log2(x))]

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.

Given this difficulty, I do not see that it is "obvious" how to
define a one-way function within the framework.

If you can elaborate on where I've failed to follow the
exposition, please do so.[/quote]
 
Mark Wooding...
Posted: Tue Oct 26, 2010 5:04 am
 
jbriggs444 <jbriggs444 at (no spam) gmail.com> writes:

[quote]From formal to formal to informal. I think it's a quantifier order
issue. Mark Wooding had it that the choice of TM could be made
after the problem instance had been selected.
[/quote]
I did? Oops. That wasn't meant to be the case. Indeed, if that were
the case there'd be no need for the relation/input machinery.

Sorry.

-- [mdw]
 
Mark Wooding...
Posted: Tue Oct 26, 2010 11:24 am
 
jbriggs444 <jbriggs444 at (no spam) gmail.com> writes:

[quote]For all polynomials p and q
There exist infinitely many n such that
For all Turing machines t
For all n bit x
R(x,t(y)) with probability less than 1/q(n)

I can argue that my reading is the correct "as written"
interpretation, but it's clear now that it is not the correct "as
intended" interpretation.
[/quote]
The confusion is surely my fault. I tried to balance precision, casual
comprehension and brevity and ended up botching the result. I'm very
sorry.

So the right answer looks like

For all polynomials p and q
There exist infinitely many n such that
For all randomized Turing machines T
Pr[R(x(n), T(x(n)))] < 1/q(n)

where x(n) is a random variable distributed on n-bit strings.

[quote]Given a security parameter, determine an instance of the one-way
function f, and sample a point x in the domain of f.  Compute z = f(x).
Provide (f, z) to the algorithm, and collect its output y.  Then set

        R = { ((f, z), y) | f(y) = z }.

This looks like a way to identify a relation R with a function f so
that the hardness or easiness of R is used to define whether f is
one-way.

But what's "the algorithm"?
[/quote]
The algorithm is, in this case, an `adversary' which attempts to invert
the function. We say that f is `one-way' if R is hard to satisfy.

[quote]Feel free to tell me to "read a book".
[/quote]
I don't like to direct people at books that they might have to dredge
out of a distant library or purchase at significant personal expense --
particularly since (as seems to be distressingly evident) my ability to
explain things clearly is in such dire need of exercise. Still, since
you ask:

The standard book on the subject is Oded Goldreich's /Foundations of
Cryptography/, published by CUP in two volumes. It's somewhat heavy
going, and seems unnecessarily turgid in some places, but it's well
worth it if you want the theory. Once upon a time, an earlier draft was
available from his web page. Google suggests

http://www.wisdom.weizmann.ac.il/~oded/frag.html

The server is down at the moment, so I can't tell if it's still there.
Goldreich is firmly in the complexity-theoretic polynomials-and-
asymptotics camp.

You may also find Mihir Bellare and Shafi Goldwasser's /Lecture Notes on
Cryptography/ useful:

http://cseweb.ucsd.edu/~mihir/papers/gb.html

The latter (if it's not changed since I last looked at it) also deals
with the explicitly quantitative approach that I actually prefer to work
with.

-- [mdw]
 
 
Page 1 of 1    
All times are GMT - 5 Hours
The time now is Wed Sep 03, 2014 2:34 am