# What does the term "asymptotic security" mean?

The Stellar cryptocurrency whitepaper lists "asymptotic security" as a key advantage over other consensus protocols (for example, proof-of-work in Bitcoin). What do they mean by this? As I understood it, it refers to guaranteed safety, as in: results valid and identical at all nodes. However, this can't be guaranteed for a decentralized system, as any node can join the system and refuse to accept the state presented by other nodes. So they must mean something else…

What does the term "asymptotic security" mean?

Here is an excerpt from the whitepaper where they vaguely characterize asymptotic security:

Safety rests on digital signatures and hash families whose parameters can realistically be tuned to protect against adversaries with unimaginably vast computing power.

• Maybe this is nitpicking, and you found the expression in the quote, but: safety and security do not have the same meaning and no security expert should ever use one tearm while meaning the other. Safety protects from randomness (hit by lightning, power spikes, etc.), or from the aftereffects of events (accidents). Security protects from malicious intend of a driven, adaptable and malicious adversary, who knows exactly what you're doing, how you're doing it and maybe knows more about cryptography than yourself.
– tylo
Commented Apr 28, 2017 at 18:44

One of the key ideas of cryptography is to provide security by means of operations that are (relatively) affordable to honest parties but prohibitively costly to adversaries. So one thing you see over and over in cryptographic literature is efforts to quantify the cost to adversaries to break some proposed cryptographic scheme.

Asymptotic security is one paradigm for so doing. In such an analysis, one states the adversary's cost as a function of a designated security parameter (e.g., key length). The scheme is then said to be secure if an only if the adversary's advantage is a negligible function of the security parameter. Very informally, an asymptotically secure scheme is one that's been conditionally proven to be harder than any polynomial for the attacker to break.

What the author seems to be highlighting is that alternatives to their proposal don't enjoy this "harder than polynomial" property (pp. 2-3):

Finally, in contrast to traditional cryptographic protocols, proof of work offers no asymptotic security. Given non-rational attackers—or ones with extrinsic incentives to sabotage consensus—small computational advantages can invalidate the security assumption, allowing history to be re-written in so-called “51% attacks.”

This seems to mean that the computational effort to an adversary who wishes to defeat the proof-of-work system is a linear function ("51%") of the total amount of computing power in the network. That amount of computing power definitely exists, so it is theoretically possible for some combination of actors to collude and assemble that much. Whereas an asymptotically secure scheme—like cryptographic ones are—can in principle be tuned so that the universe might not be big enough to crack them.

When he says:

in contrast to traditional cryptographic protocols, proof of work offers no asymptotic security.

I think he means that it is vulnerable to > 50% hash power attacks.

With "asymptotic" I think he means a miner growing hash power and reaching the limit, in this case 51%.

• Funny that this answer comes shortly after Antbleed's popularity hits. Something about a 51% attack seems much more plausible when there seems to be a way for a major party to DoS competitors.
– Nat
Commented Apr 29, 2017 at 11:35

What asymptotic means is that something is distributed in such a way that it converges on a limit, and this is how elliptic curve cryptography works also, so they are only really saying that they are using points on a curve for cryptography.

A good way to think about an asymptotic sequence is to imagine that there are dots on a chart and as you go towards one edge or limit of the chart the dots are more and more packed together. For example in this image below, we can say that the distribution of dots is asymptotic to the limit which in this case is the center of the graph at the origin.

A commonly used meaning for asymptotic in cryptography is basically just that the distribution or how closely packed together their values are increases as you increase the value of the private key for example. So in ECDSA cryptography the keys will fall along a curve and actually not be evenly or randomly distributed as most think, they are somewhat bunched up towards one or another side. Forming a cluster is another good example, that is, having something gathering around some point in a non-random but changing rate.

• I can't make sense of "in ECDSA cryptography the keys will fall along a curve and actually not be evenly or randomly distributed as most think, they are somewhat bunched up towards one or another side". What exactly would be biased, if that's the idea? That seems to be an extraordinary claim made with no evidence.
– fgrieu
Commented Dec 20, 2023 at 10:53