Amitabh Saxena

2006-06-23 13:19:28 UTC

This may be a trivial question.. but I would appreciate if someone

could clear my confusion.

Suppose we are working in the field F_q, with g being a generator (let

q=2p+1, p prime so that testing generators is easy). We assume that

computing discrete logs in F_q is hard.. Now consider the language

L={h \in F_q | exists x \in Z*_q such that h=g^x}

Clearly L is in P because for all h \in F_q, such an x exists.

however, since computing discrete logs is hard, how do I express the

concept of "knowing the discrete log" using a language outside BPP..

(i.e. I want to prove knowlede of discrete logs in F_q, rather than

just prove that such a discrete log exists)

I understand that the problem of "computing discrete logs" is not in P,

since there is no PPT algorithm.. so if a protocol proves "knowledge of

discrete log", then this is definitely a proof of a language outside

BPP. (yes or no?)

Please give feedback

Thanks in advance.

best,

Amitabh

could clear my confusion.

Suppose we are working in the field F_q, with g being a generator (let

q=2p+1, p prime so that testing generators is easy). We assume that

computing discrete logs in F_q is hard.. Now consider the language

L={h \in F_q | exists x \in Z*_q such that h=g^x}

Clearly L is in P because for all h \in F_q, such an x exists.

however, since computing discrete logs is hard, how do I express the

concept of "knowing the discrete log" using a language outside BPP..

(i.e. I want to prove knowlede of discrete logs in F_q, rather than

just prove that such a discrete log exists)

I understand that the problem of "computing discrete logs" is not in P,

since there is no PPT algorithm.. so if a protocol proves "knowledge of

discrete log", then this is definitely a proof of a language outside

BPP. (yes or no?)

Please give feedback

Thanks in advance.

best,

Amitabh