Glossary of Security Definitions

Security definitions specify what guarantees a protocol provides. They fall into two categories: safety properties (bad things don't happen) and liveness properties (good things eventually happen). The strength of guarantees varies by adversary model and probability bounds.

• Perfect security: probability of failure is exactly 0. Holds against computationally unbounded adversaries.
• Unconditional security: information-theoretic – no computational assumptions needed. In practice, perfect and unconditional are used interchangeably.
• Statistical security: probability of failure is at most some negligible \(\epsilon\). Holds against computationally unbounded adversaries, but with a small error probability.
• Computational security: holds against any probabilistic polynomial-time (PPT) adversary, assuming some computational hardness (e.g., discrete log, factoring).
• Post-quantum security: computational security where the underlying hardness assumptions are believed to hold against quantum adversaries (e.g., lattice-based, hash-based, code-based assumptions rather than discrete log or factoring).

A protocol may achieve different strengths for different properties. For example, Cachin et al. [1] achieve computational correctness (relies on discrete log) but unconditional privacy (the adversary has no information about the secret).

These state that something bad never happens (or happens with negligible probability).

• Agreement: all honest parties produce the same output. Used in consensus, broadcast, secret sharing.
• Consistency: if two honest parties both produce an output, the outputs are the same. Weaker than agreement – does not require all parties to produce output.
• Correctness: if all parties follow the protocol honestly, the output is the right value.
• Soundness: incorrect/invalid statements or inputs are rejected.
• Validity: the output is related to the inputs in a meaningful way. Common variants:
  • Strong validity: the output is some honest party's input.
  • Weak validity: if all honest parties have the same input \(v\), the output is \(v\).
  • External validity: the output satisfies some externally defined predicate.
• Secrecy (privacy): the adversary learns nothing about the secret/inputs beyond what is implied by the output. Formally: the adversary's view can be simulated given only the output and the adversary's own inputs.
• Integrity: a message is delivered only if it was actually sent by the claimed sender. Prevents forgery. Generally, if a node follows the protocol, bad things will not happen to it.

These state that something good eventually happens.

• Termination: all honest parties eventually produce an output. May be deterministic or probabilistic (with probability 1).
• Completeness: if the dealer/sender is honest, all honest parties eventually complete the protocol. Used in secret sharing, broadcast.
• Liveness: the protocol makes progress – honest parties are not stuck forever. Often used interchangeably with termination, but sometimes weaker (e.g., eventual progress without a bound on when).
• Fairness: if any party learns the output, all honest parties learn it. Prevents an adversary from aborting after learning the result but before honest parties do.

• Verifiability: parties can check that their shares/outputs are consistent with a valid dealing/computation. Prevents a corrupt dealer from distributing inconsistent data.
• Public verifiability: anyone (not just protocol participants) can verify correctness. Used in PVSS, public-key encryption, blockchain.
• Robustness: the protocol produces a correct output even if up to \(t\) parties behave maliciously. Stronger than just detecting faults – the protocol tolerates them.
• Accountability: if a party misbehaves, it can be identified and proven faulty to a third party.