I have designed an random encryption in public key setting. I am convinced about its security guarantee but I need a formal way to prove its robustness. How can I prove the security of this random-public-key-encryption algorithm? Any proof method such as induction-method, proof-by-contradiction-method or anything else?

I am trying to publish this algorithm in a journal paper. This is why I need a formal proof.

  • 3
    $\begingroup$ Which problem is it based on? $\endgroup$ Commented May 7, 2017 at 18:36
  • $\begingroup$ Haven't done this before, but I'd think that you'd want to write attack algorithms on your cryption algorithm under the various attack scenarios, then classify the attack's complexity as a function of the algorithm's parameters. $\endgroup$
    – Nat
    Commented May 7, 2017 at 21:45
  • $\begingroup$ Note that you're not obligated to prove that your algorithm can't be efficiently broken; it's sufficient to map seemingly optimal attack algorithms to well-known algorithms that're generally accepted to be infeasible to run. For example, you're not obligated to prove that $\text{P}{\neq}\text{NP}$; it's sufficient that there's no publicly known mapping $\text{NP}{\rightarrow}\text{P}$. $\endgroup$
    – Nat
    Commented May 7, 2017 at 22:00
  • 8
    $\begingroup$ I'm sorry if I misunderstood why nobody mentioned this yet, but: If you have to ask this question, it means you're not yet ready to design such an algorithm, much less publish it in a journal. The current answer nicely shows ways how to learn about this, though, and I appreciate it. $\endgroup$
    – mafu
    Commented May 8, 2017 at 0:51
  • $\begingroup$ Something is wrong. The likelihood of you finding a new public key math problem is remote. If you had a new symmetric algorithm there would be a decent chance but public key is so hard to design for we should rather wonder than any were found. $\endgroup$
    – Joshua
    Commented May 8, 2017 at 1:51

1 Answer 1


What you want to do is the right way. However it's not an easy one.

What you really want to do is to show the following implication: $$ \newcommand{\hard}{\operatorname{hard}} \newcommand{\assumption}{\text{assumption}} \newcommand{\secure}{\operatorname{secure}} \hard(\assumption_1)\land\ldots\land\hard(\assumption_n) =\bigwedge_{i=1}^n\hard(\text{assumption}_i)\\ \implies\secure(\text{cryptosystem})$$

for a (hopefully) small number of assumptions which are already well-studied.

The usual intuition for such proofs is a proof-by-reduction, which is a logical contraposition: $$\neg\secure(\text{cryptosystem})\implies\bigvee_{i=1}^n\neg\hard(\assumption_i)$$ Meaning that you would need to show that breaking the security of your cryptosystem implies that any of your assumptions is not hard.

Of course you first need to find out what "$\hard(\assumption_i)$" and "$\secure(\text{cryptosystem})$" actually mean. The latter is a (preferably) strong security definition, most likely from this list. The former very much depends on the actual assumption at hand and you need to look at the actual, precise definition of said assumption. For example this blog post covers RSA and this one covers the typical DH assumptions.

Now the final and actually hardest part: How to actually make the proof. There's no simple answer to this question. For example you could give game-hopping a look as well as simulation based proofs. You could also look whether proof / verification tools can help you along the way, such as described by Biv here and here. There isn't much more to say on this, except for: Look at the references given, work your way from there through the references they give, continue going through the references until you have an understanding of these proofs and are able to carry out the one you need. It will probably be a hard and / or long journey, but it will pay off.


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.