If I have committed to a number x by revealing g^x mod p, can I prove that 0 < x mod (p-1) < (p-1)/2, i.e. that x is positive, without leaking any more information about x?

My bounty is ending in 4 days and I am unsatisfied with the current answers so I would like to provide more context and also expand the question for the limited time remaining. Consider the following situation:

Paul and Quentin are wealthy and competitive with each other and they frequently settle their account with great variance: one week Paul is ahead by a million dollars, the next week Quentin is ahead by a billion, the next week Paul is ahead by only a thousand. Paul and Quentin have a wealthy rival Raul, whom they shun, but all 3 persons patronize the same accountant Verne. Verne is honest and discreet and frugal and he will never make a payment to a client on credit, but he will pay an owed amount to a client on demand. Raul can profit from information about Paul's account, indirectly costing Paul, and everyone knows this. How can Verne manage his accounts without having to buy insurance against Paul's legal accusation of a conflict of interest?

11more comments