But, from a meta-cryptographic point of view, how do we justify the assumption that there doesn't exist any significantly more efficient algorithms, or any significantly better hardware?
From a cryptographic point of view, the best answer is usually modularity: we want to design schemes which can be based on "instantiation-oblivious" hypothesis (i.e., hypothesis that we can instantiate over a large variety of objects sharing some mathematical structure). For instance, we know that the discrete logarithm problem is hard in a generic group (a group with no additional structure). Therefore, if a scheme based on the discrete log is broken on a given structure, it will likely remain secure if it is instantiated on another group, with less additional structure (notwithstanding the advent of quantum computers, ofc).
From a meta-cryptographic point of view, once a specific system is deployed, our confidence comes essentially from two considerations:
- How long has the underlying problem been studied
- How many people are actively doing research in cryptography (both in academia and companies)
For example, the factorization problem already has a very long history, hence it seems more likely that our understanding of it is more advanced - put otherwise, there is less chance that we missed a simple approach that would allow for fast factoring. However, the second consideration remains probably the most important one. In the 90's, it was plausible for a powerful intelligence agency (such as the NSA) to hire enough mathematicians, and to give them access to a huge computing power, so as to be competitive with what the rest of the world could do. With the evolution of cryptography in the past decades, that does not seem plausible anymore. Thousands of researchers are actively working on cryptography, hence an agency could, at best, hire a very small fraction of these researchers. I see no strong reason to believe that all the best researchers could end up working for the same agency (especially since cryptographic research is spread worldwide). Assuming that the researchers an agency can hire are sufficiently representative samples among good researchers, this implies that the probability that a cryptographic breakthrough comes from a given agency is reasonably small. The same observation holds with respect to computational power: nowadays, even an agency as powerful as the NSA cannot mount cryptographic attacks that would require way more computational power than what, e.g., Google, Apple, or Microsoft have access to.
How likely is it that a single small team, basing their research solely on the state of the public research and their own results, would come up with results years or decades ahead of everyone else in the field?
It is not impossible. It appeared in the past: Clifford Cock had essentially discovered RSA five years before its introduction by Rivest, Adleman, and Shamir, while working for the GCHQ. In the 70's, the NSA had apparently already discovered differential cryptanalysis (see this post by Bruce Schneier), which could break many seemingly secure schemes, and was only 'publicly' discovered in the 90's. However, at the time, the amount of people working in this field was considerably smaller than today. Nowadays, the probability of such an event happening should probably be close to (number of people working for the agency)/(number of researchers working on area related to what the agency works on). Hard to precisely estimate, but likely small.
Is it possible for large organizations to internally accumulate enough research, to give the researchers within that organization a significant head start over independent researchers in the field?
Again, it is not impossible, but it requires luck more than anything else. But that was assuming the question was about finding breakthrough results on cryptanalysis of deployed schemes. In fact, other types of attacks can be found, and they seem way more likely.
- the agency can find an attack, not on a primitive, but on a protocol. Due to their highly complex structures, the landscape of possible attacks in considerably increased. Unlike cryptanalysis of primitives, breaking a protocol is not about finding advanced mathematical methods, it's only about thinking about something that people did not consider before. A good example of it is the recent logjam attack, or 3SHAKE. It is not completely unlikely that some agencies are already aware of attacks of this type that have not yet been publicly revealed.
- Even more likely, the agency can directly find flaws in a specific implementation (either of a cryptographic primitive/protocol, or at a higher level). Those flaws are usually devastating, conceptually very simple, and seem considerably more easy to identify than, say, a new factoring algorithm (such flaws are discovered routinely). One can think for example about the recent heartbleed. Here again, it seems quite likely that some agencies are already aware of security issues that have not been yet publicly revealed.
If "yes" on the previous question, are there ways to reliably tell if an organization has such significant amounts of secret accumulated knowledge? Is it possible to use the numbers of papers and patents the organization outputs, as a reliable indication that it doesn't have a strategy of accumulating knowledge only internally? What about flows of personnel between organizations, i.e. people changing jobs?
If the organization is small and keeps everything it does secret, there is no way to tell. Intelligence agencies will obviously not write patents or publish papers about their most critical discoveries. However, if the organization is small, it has also a very small probability of being the one from which a cryptographic breakthrough originates.
On the other hand, if an organization is large, then there is a standard way to know what it is working on: leakages. If the organization works with many people, on sensible subjects of crucial importance, something will end up leaking - human flaws are the only one that an agency cannot cope with. This happened with Snowden, and can happen again.
What is the likelihood that an organization exploiting weaknesses it has found in cryptographic primitives, would be caught in the act? If the organization is only using the weaknesses for intelligence gathering? Does it matter if the weaknesses require passive attacks or active attacks to be conducted?
That completely depends on the particular scenario: it could be that an active attack will remain undetected, or that it will be detected with noticeable probability. In the field of secure computation, which an important and active research area in cryptography, this fact has been acknowledged by considering three types of adversarial behaviors: passive, covert, and active. Passive and active attacks are the types you already know; a protocol secure against covert adversaries can be broken by an active attack, but it is not possible to break its security without being caught (with good probability). The rationale behind this was that in practice, an important company/agency would likely want to attack cryptographic protocols, but cannot afford being caught when doing so.
If the weaknesses requires only passive attacks, and the agency is only gathering information, there is no way to tell (except internal leakages): a passive attack can be mounted offline, on the transcript of some interaction, hence there is no reason why anyone could discover about the outcome of the attack, unless that person is already part of the agency.
