Most things in complexity-based cryptography (for examples, see page 4) are known to imply
the existence of one-way functions, especially after this paper proved that implication for weak coin-flipping with any constant bias. ​ However, this paper shows a relativized world with non-trivial 2-round argument systems but no one-way functions, which makes we wonder about the
possibility of complexity-based cryptography, beyond ideal SNARKs, without one-way functions.
With that in mind, I initially thought about multi-party versions of honest-majority coin-flipping
with negligible bias, but discovered that there were too many possible specifications
for me to decide which of them to ask about. ​ (For example, are there secret channels,
is broadcast available, what are the requirements in case of abort?)
Accordingly, I'm instead asking about 2 parties choosing an element from {0,1,2}.

Consider the 2-party functionality:

If the parties are both corrupt or both honest then choose y uniformly from {0,1,2}.
Otherwise, receive an element x of ​ {0,1,2} ​ from the
adversary and choose y uniformly from ​ {0,1,2} - {x} .
In either case, output y to both parties.

Is it known that if there is a secure 2-party implementation
of that functionality then one-way functions exist?

(Obviously, one doesn't need to care about what happens when both parties are corrupt.
Slightly less obviously, when both parties are honest, it suffices to make sure they get the same value, since the protocol could be modified to start with one party choosing an element of {0,1,2} uniformly at random and then at the end, adding that to the inner protocol's output mod 3.)


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy