Adversarial Models in Cryptography

Table of Contents


In its infancy, the internet was conceived as a gated community that only well-meaning and trustworthy individuals could enter.As its reach and appeal broadened with the advent of the World Wide Web, it became clear that the internet outgrew its initial demographic of – as VintCerf put it – "a bunch of geeks who didn’t have any intention of destroying the network"1. Since then, as the data transiting on the network has become more voluminous, it grew more and more valuable, making cyber-crime more tempting.

Today, cyber-criminality is a business, and it is essential to look into what adversaries look like and what they can do. We will thus have a look at a classification of the capabilities adversaries may have, before presenting the main adversarial models cryptographers defend against. Finally, we’ll close this article by relating all this talk of adversaries to Astran’s day to day activities.

Adversary Capabilities

A natural way to classify adversaries is by what they can do and how ready they are to do it, which determines the risk companies face. The three following pairs of opposite adjectives serve as a strong basis to describe an adversary’s capabilities, or the nature of an attack. The leftmost of each pair denotes the weakest of the two in terms of an attacker’s potential.

Static vs. Adaptive

The first distinction we can make is between Static and Adaptive adversaries. Static adversaries may not change their behavior in response to the system while Adaptive adversaries may. As an illustration, imagine a man-in-the-middle eavesdropping a communication channel that guarantees secrecy. A static adversary could only send the messages it sees anew, unchanged. An adaptive adversary on the other hand could alter the message before sending it. For example they could flip some bits in the message and study the response to the modified payload in an attempt to gain information about the channel’s underlying protocols.

Classic vs. Quantum

Another distinction is between Classic and Quantum security. Classic adversaries are attackers who only employ classical computers to perform calculations. But the threat posed by quantum computers has led some cryptographers to reexamine primitives from the perspective of an adversary with quantum computing power2. A lot of cryptographic primitives, including most of what is used today for public key cryptography, would collapse if confronted with quantum adversaries.

Computationally Bounded vs. Unbounded

The final distinction is between Computationally Bounded and Unbounded adversaries.Unbounded adversaries are ideal attackers that possess unlimited computing power and may run any algorithm, regardless of complexity or run time. No truly Unbounded actor exists for now, nevertheless, they are quite useful as a thought experiment and systems in which computationally unbounded attackers may not derive any additional information from ciphered data are said to have perfect security or to be information-theoretically secure. Conversely, Bounded adversaries (also called polynomial-time adversaries) are"real-world" attackers whose computing capacities are bounded by a given polynomial. A system in which computationally bounded attackers may not derive any additional information from ciphered data is said to have semantic security3.For example, Shamir’s secret sharing scheme as described by Aïcha Dridi4 is perfectly secure, whereas an AONT (ibid.), as applied by Astran, has semantic security level.

Adversary Models

Having seen how to describe an adversary’s capabilities, we are now ready to discover and understand some classical adversarial models.


Malicious adversaries are active attackers that can act arbitrarily. They are the stereotypical "bad guys" of the computer world and have no qualms at all, as long as their actions nets them an advantage or furthers their goals. Malicious adversaries can be classic or quantum, static or adaptive, computationally bounded or unbounded. Some examples of Malicious adversaries would be ransomware groups or black-hat hackers.


Honest-but-Curious adversaries are passive, static adversaries whose goal is learning as much information as possible without deviating from protocols they partake in. They work great to model today’s internet barons (Alphabet, Meta, Microsoft, Oracle, etc.). They gather all the data and metadata they can get their eyes on and analyze it later.


In some cases, the honest-but-curious model could be too weak to prove a protocol while the malicious model would be too strong. Covert adversaries were introduced as a middle ground between honest-but-curious and malicious adversaries by Lindell and Aumann to solve this issue5. In their article, they declare that the covert adversary model "accurately models adversarial behavior in the real world". They may deviate from the protocols they take part in if and only if they cannot be caught doing so, because they are afraid of consequences or loss of reputation for example. In other words, they can cheat in a very non obvious way. An example of this type of adversary are known companies that have access to big clients’ data. They may try to modify or learn more only if they are not caught doing so, because else it would make a huge scandal and they would lose their reputation.

Bonus adversary: State-Actor

State-Actors are the ultimate form of Static adversary. While other models only consider polynomial time attacks, State-Actors have all the time in the world to run exponential algorithms or worse ! They are used to model the overwhelming power befitting a nation. They act like honest-but-curious eavesdroppers, collecting all messages of interest transiting on their networks6. However, unlike other attackers, they are computationally unbounded and will one day break any non information-theoretic cryptography used to protect messages. With such an adversary, breaking semantic security is not a question of if, it’s a question of when !

How Astran Fends and Defends

Astran’s goal is to help customers protect their data by storing them in multi-clouds without the need of managing any secret key. The protocol currently used by the company has been rigorously proven to defend against a coalition of up to k-1 malicious cloud providers or less (where k is their construction threshold parameter). Furthermore, our R&D team is currently working on a new protocol in which Astran is no longer modeled as an Honest actor but rather as a covert adversary. This not only means that in the new protocol Astran would not be able to learn anything about user data by examining it in transit, but also that if Astran were to act maliciously at one point in time with a coalition of up to k-1 cloud providers, they would still not be able to uncover the data. This improvement in the protocol can and will increase the trust of clients in Astran’s products and services.






6. "[…] retention in excessof five years is authorized, to include communications […] that are encipheredor reasonably believed to have a secret meaning." From the INTELLIGENCEAUTHORIZATION ACT FOR FISCAL YEAR 2015, section 306

Return to Resources ->