The **Visions of Cryptography workshop** workshop,
which was part of the Celebration of the work
of Shafi Goldwasser and Silvio Micali
at Weizmann (Dec. 10-12, 2013),
has a panel discussion the issue of assumptions in cryptography.
Here is a posting of some of my thoughts regarding this matter.
It is intended for experts in the theory of cryptography,
and may be unintelligible for others.

Think of the way Complexity Theory (CT) handles assumptions such as "P \neq NP", "NP \neq coNP", "PH does not collapse", and the more recent UGC (Unique Game Conjecture). It is unthinkable that a CT paper will claim a conditional result (which relies on one of the aforementioned assumptions) without explicitly stating the condition/assumption that it is using, and paying great attention to the difference between the various assumptions. In fact, many papers seem to be focused on the differences between these assumptions.

Unfortunately, we have nowadays more than a handful of popular assumptions, still I think that each conditional result must be always stated with the condition on which it relies. One cannot say "We have primitive P", but rather "We have primitive P, assuming A". The only exception may be results in which it is *totally* obvious (i.e., obvious to any reasonable potential reader) *which* assumption is used, and even in this case the theorems must state this condition. The only such cases (which I can think of), are such that use OWF.

Beyond this, we may have OWP, claw-free permutation pairs, TDP (and their enhancements), CRH, and a host of specific assumptions ranging from Factoring, RSA, DLP, DDH to LWE and MLM. Some primitive (e.g., PRF, PKE, IBE, FHE, and IO) can also be used as assumptions. Indeed, it may be more appealing to say that "IO implies X" (for a vast list of X's) than to say that "We can do X, based on assumption Y (which implies IO)" , let alone just saying "We can do X"....

In other words, what we are constructing is a directed graph of implications between assumptions and primitives, where many of these implications are far from being clear (since they relate objects that are fundamentally different in many cases).

[Actually, things are even more complex, since at times we need several incomparable assumptions to get a consequence, which may be modeled by a directed hyper-edge. Also, the various implications may have different flavors ranging from stronger than normal implications (i.e., flavors of black-box) to weaker than normal implications (i.e., flavors of non-uniformity).]

Another pathetic suggestion is to take a lesson from our own field's past... (Indeed, it is pathetic to look back to the "good old days").

I do not envy the practical cryptographers; their life is far harder than ours. Hence, it should come at little surprise that I don't think that their choices should determine ours.

Our task is different: It is to develop a sound theory for cryptography. A theory that may inform practice, not replace it. Such theory may emphasize distinctions that get blurred at current practice. For example, I am quite sure that practionnaires do not come to their boss saying "This scheme is secure under assumption A" but rather "We constructed a secure scheme" (or "we constructed a scheme that we are confident to be secure"). This may be reasonable for them, but not for us. If we wish to develop theory, we should emphasize differences and distinctions (e.g., regarding the assumptions on which schemes are based) rather than de-emphasize them.

Taking the ROM and other idealized models as an example, it is crucial to realize that from a theoretical point of view these are merely sanity checks for certain designs or feasibility claims. That is, unless one proposed to actually implement such ideal objects (which I don't consider so absurd as it may sound), then results that use such ideal objects cannot be claimed to be more than a sanity check: That is, if the design failed in the ideal model, then it is certainly bad, and that's all what one can say. That is, I'd say "Design D cannot be shown to be insecure in the ideal model IM"; sure, one can claim that it is OK to say "secure in IM" , but I think it is better (i.e., better reflects the reality) to say "is not insecure in IM". N.B.: This entire paragraph refers to theory, not to practice! Getting back to the analogy to CT, note that it is unthinkable that a paper in CT would present a lower bound in a restricted model of computation without highlighting the restriction, and it will be clear to all that this is merely a sanity check.

Back to Oded's page of essays and opinions or to Oded's homepage.