A strong 2-ary one-way function using an oracle.

[Amitabh Saxena]

[Note: A strong one-way 2-ary function is one that cannot be inverted
if one argument and the output is given. That is, it may be possible to
invert the function if none of the arguements are given but it is not
possible to invert the function with respect to one given argument. In
addition to this, I require the 2-ary function to be associative]

Assume that n = p.q where p and q are two large secret primes and n is
public.

We assume an oracle O with access to p and q that we will model our
one-way function with. Define the oracle function for any positive
inputs x, y as:

O(x, y) = ((((x.y) mod m) ^ r) mod n).m + (x.y) mod m

where r is some random secret known only to the oracle. Then we observe
that O(.,.) is associative.

(1) I think that given O(x, y) and x, it is hard to recover
corresponding y.
(2) I think it is not possible to factor n using the oracle.

The output of the oracle can be checked as follows:
select any random element u from Zn. Then ((u^x)^y) = u^O(x, y) [mod n]
Thus the output of the oracle can be verified but O cannot be strongly
inverted. I want to know if my assumptions (1) and (2) above are
correct.

Thanks in advance.
Rgds

[David Wagner]

Post by Amitabh Saxena
[Note: A strong one-way 2-ary function is one that cannot be inverted
if one argument and the output is given. That is, it may be possible to
invert the function if none of the arguements are given but it is not
possible to invert the function with respect to one given argument.

That doesn't make any sense. If I can find a pre-image without being
given any arguments, then I can surely find a pre-image when given the
first argument: I just forget that you told me the first argument, and
find a pre-image without using any knowledge of the arguments. (Remember
that breaking a one-way function means finding *any* pre-image.)

Post by Amitabh Saxena
Assume that n = p.q where p and q are two large secret primes and n is
public.
We assume an oracle O with access to p and q that we will model our
one-way function with. Define the oracle function for any positive
O(x, y) = ((((x.y) mod m) ^ r) mod n).m + (x.y) mod m
where r is some random secret known only to the oracle. Then we observe
that O(.,.) is associative.

More concisely: O(x,y) = (xy)^r + xy mod m.

No, it's not associative. Take x=2, y=3, z=5, r=2; then
(xy)^r * z != x * (yz)^r. Try some examples, and you'll see what I mean.

Did you perhaps mean commutative instead of associative? Associative
means that O(x,O(y,z)) = O(O(x,y),z). Your function is commutative but
not associative.

Post by Amitabh Saxena
(1) I think that given O(x, y) and x, it is hard to recover
corresponding y.

Sounds plausible. It smells vaguely related to DDH in some subgroup
of (Z/mZ)^* and to finding small-order elements of (Z/mZ)^*, both of
which ought to be hard.

If you drop the + xy, so that O(x,y) = (xy)^r, and work in some
prime-order subgroup, then finding r should be as hard as the DDH
problem, I suspect. And finding r should remain hard even given
O(.,.) (i.e., ability to choose both x and y). Caution: I didn't check
either of these claims. Please work out a proof, if you care.

Post by Amitabh Saxena
(2) I think it is not possible to factor n using the oracle.

I agree. Given r, m, I can compute O(x,y) myself. Therefore, if this
oracle helped me to factor n through some magical procedure, I could pick
a random r, then run the magical procedure with a simulated oracle (using
the r I just picked). Conclusion: no such magical procedure can exist,
if factoring is hard.

Post by Amitabh Saxena
select any random element u from Zn. Then ((u^x)^y) = u^O(x, y) [mod n]

That doesn't make any sense to me. (u^x)^y = u^{xy}, which is not
the same as u^{O(x,y)}.

[Amitabh Saxena]

Post by David Wagner
That doesn't make any sense. If I can find a pre-image without being
given any arguments, then I can surely find a pre-image when given the
first argument: I just forget that you told me the first argument, and
find a pre-image without using any knowledge of the arguments. (Remember
that breaking a one-way function means finding *any* pre-image.)

In some cases, it may be required to find a particular pre-image rather
than any pre-image. For example, given any RSA public key (e, n), it is
easy to find two values a, b such that a^e mod n = b. However, given
the public key and the value b, it is hard to find the specific a.

Post by David Wagner

Post by Amitabh Saxena
O(x, y) = ((((x.y) mod m) ^ r) mod n).m + (x.y) mod m
where r is some random secret known only to the oracle. Then we observe
that O(.,.) is associative.

More concisely: O(x,y) = (xy)^r + xy mod m.

I don't see how ((((x.y) mod m) ^ r) mod n).m = xy ^ r

Post by David Wagner
No, it's not associative. Take x=2, y=3, z=5, r=2; then
(xy)^r * z != x * (yz)^r. Try some examples, and you'll see what I mean.

Proof of associativity:

O(x,y) = [((((x.y) mod m) ^ r) mod n).m + (x.y) mod m]
O((x,y), z) = ((([((((x.y) mod m) ^ r) mod n).m + (x.y) mod m].z) mod
m)^r mod n).m + [(((((x.y) mod m) ^ r) mod n).m+(x.y) mod m)].z) mod m

= ((x.y.z)^ r mod n).m + (x.y.z) mod m

same with O(x, O(y, z))

I think I am correct about the one-way ness.

[Amitabh Saxena]

The oracle is insecure in the simple case when the inputs x, y are such
that xy is less than m. Since making an oracle call and computing
O(x,y)-xy will give us a multiple of phi(n) and reveal factors of n.

To make it secure, I modify the input conditions to ensure that one of
the inputs (the left one) is always greater than n.

O:(Z - Zn) x Z -> Z(phi(n)^2)

Post by Amitabh Saxena
I think I am correct about the one-way ness.