Amitabh Saxena

2005-08-12 09:13:30 UTC

[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

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