On Cryptographic Assumptions


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.

1. An analogy: Complexity Theory

I feel that it is pathetic that we should take a lesson from other fields on this matter, which is at our field's core. Still, it seems that this is useful...

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").

2. Theory versus practice

The dichotomy and/or tension between theory and practice is relevant also for the current discussion. If one needs to construct a scheme that operates now (or in the next five years), then one is forced to base it on some assumptions and the choice must be governed by practical considerations including cost-effectiveness (e.g., what is the benefit in terms of "cost" of making more risky assumptions). Furthermore, in any case, a practical assumption goes far beyond the theoretical assumption, since it specifies a security parameter and refers to concrete computing resources and their cost at a specific time. In particular, the theoretical hierarchy between the various assumptions is not necessarily preserved when making a practical choice; such choices are dominated by a complex web of many practical considerations (and some may even be non-technical (e.g., legal liability)). Likewise, the ROM may offer the best assurance possible *at the moment* for a particular design, whereas from a theoretical perspective it is merely a sanity check.

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.