# How to prove security of a randomized encryption algorithm?

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.

• Which problem is it based on? – CodesInChaos May 7 '17 at 18:36
• 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. – Nat May 7 '17 at 21:45
• 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}$. – Nat May 7 '17 at 22:00
• 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. – mafu May 8 '17 at 0:51
• 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. – Joshua May 8 '17 at 1:51

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})$$
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.