When do we call an assumption to be minimal assumption? What's the difference if we say just using assumption X the protocol Y is constructed instead of using minimal assumption X the protocol Y is constructed.

Example: Oblivious transfer is considered to be minimal assumption for constructing MPC protocol. Why so?


1 Answer 1


"X is a minimal assumption for Y" means: the existence of X is equivalent to the existence of Y.

  • If you can securely realize oblivious transfer then you can securely realize any MPC task/functionality. This was first shown famously by Kilian. Conversely, OT is just one possible MPC task. So clearly if you can securely realize all MPC tasks then you can realize OT. They are equivalent, hence we say that OT is a minimal assumption for MPC.

  • One-way functions imply PRGs, which imply PRFs, which imply PRPs, which imply CPA-secure symmetric-key encryption, which implies CCA-secure symmetric-key encryption and AEAD. Conversely, all of these primitives also imply one-way functions. They are equivalent, hence we say that OWF is a minimal assumption for all of symmetric-key cryptography.

These are the two examples that are most clear-cut that I can think of.

  • $\begingroup$ Could you write out the abbreviations once? (I guess OT = oblivious transfer, from the tag, but all the others are not clear to me as a casual reader.) $\endgroup$ Commented Jun 11 at 23:31
  • $\begingroup$ @PaŭloEbermann MPC = multiparty computation, PRG = pseudorandom generator, PRF = pseudorandom function, PRP = psudorandom permutation, CPA = chosen plaintext attack, CCA = chosen ciphertext attack, AEAD = authenticated encryption with associated data and OWF = one-way function. $\endgroup$
    – Mahesh S R
    Commented Jun 12 at 10:09

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.