Digital Signature Ontology

FLOW ALGEBRA
TITLE: Digital Signature Ontology
DOMAIN: Discrete Mathematics / Cryptography
SOURCE_URL: https://kirethresearch.org/booksai-core/discrete-mathematics-ontologies/cryptography/digital-signature-ontology-2.html
VERSION: 1.0
DATE: 2026-10-11
AUTHORS: Mark Higgins — Sky (Recursive AI)
SOURCE_STATUS: Formal synthesis from established cryptography; live source text not independently verified.

1. PURPOSE
Model digital signature generation, verification, key ownership, authenticity, integrity, and the limits of security claims using typed relations and explicit validation rules.

2. TYPED ENTITIES
Message: Bytes
PrivateKey: SecretKeyMaterial
PublicKey: VerificationKeyMaterial
KeyPair: (PrivateKey, PublicKey)
Signature: Bytes
Algorithm: SignatureScheme
Signer: Principal
Verifier: Principal
Certificate: Optional[PublicKeyBinding]
Context: ProtocolContext
VerificationResult: {VALID, INVALID, ERROR}
SecurityProperty: {EUF_CMA, SUF_CMA, INTEGRITY, ORIGIN_AUTHENTICATION}

3. CORE OPERATIONS
KeyGen(algorithm, randomness) -> (sk, pk)
Sign(algorithm, sk, message, context, randomness?) -> signature
Verify(algorithm, pk, message, signature, context) -> VerificationResult
BindKey(principal, pk, evidence) -> KeyBinding
ValidateBinding(binding, trust_policy, time) -> Boolean

4. CORRECTNESS
For honestly generated (sk, pk), supported messages m, and valid signing context c:
  Verify(pk, m, Sign(sk, m, c), c) = VALID
Subject to the scheme's correctness requirements and properly encoded inputs.

5. FORMAL RELATIONS
HAS_PUBLIC_KEY(Signer, PublicKey)
CONTROLS_PRIVATE_KEY(Signer, PrivateKey)
SIGNS(Signer, Message, Signature)
VERIFIES(Verifier, Message, Signature, PublicKey)
BOUND_TO(PublicKey, Signer, Certificate)
USES_ALGORITHM(Signature, Algorithm)
HAS_CONTEXT(Signature, Context)

6. INFERENCE RULES
R1: Valid verification -> signature is mathematically valid for the supplied public key, message, scheme and context.
R2: Valid verification + trusted key-to-identity binding -> evidence of origin from the corresponding key holder, subject to compromise and policy assumptions.
R3: Changed signed bytes -> verification generally fails unless a valid signature for the changed message is supplied.
R4: Invalid verification -> do not assert authenticity or integrity from that signature.
R5: Key revocation, expiry or compromise -> evaluate trust separately from mathematical signature validity.
R6: A digital signature alone does not provide confidentiality.

7. SECURITY MODEL
EUF_CMA: An adversary with signing-oracle access should not be able to produce a valid signature on a new message except with negligible probability under the scheme's security assumptions.
SUF_CMA: Stronger requirement also forbids a new valid signature for a previously signed message.
Security depends on algorithm, parameters, key generation, randomness, implementation, and protocol usage.

8. VALIDATION
- Check algorithm and parameter support.
- Check canonical message encoding and domain separation/context binding.
- Validate key format, public-key binding, and applicable certificate path/policy.
- Verify signature against exact signed bytes.
- Apply timestamp, revocation, expiry, and compromise policies where relevant.
- Reject ambiguous parsing and algorithm substitution.
- Never equate mathematical validity with legal non-repudiation.

9. ALGEBRAIC / SEMANTIC PROPERTIES
Signature verification is a predicate over (public key, message, signature, context).
Message identity is byte-level unless the protocol defines canonicalisation.
Signatures are not necessarily unique for a given message and key.
Verification validity is distinct from signer identity and from certificate trust.

10. SEMANTIC_EQUIVALENCE
'Digital signature' ~= 'cryptographic signature' when referring to asymmetric signing schemes.
'Digital signature' != 'scanned handwritten signature'.
'Signature verification' != 'identity verification' without a trusted binding.
'Message authentication code' != 'digital signature' because MAC verification uses shared secret material.

11. CONFIDENCE
Formal definitions and correctness constraints: HIGH.
Identity attribution: CONDITIONAL on trusted key binding and key custody.
Security guarantee: CONDITIONAL on scheme assumptions and implementation.
Source-page fidelity: UNVERIFIED.

12. FLOW_HASH
HASH_INPUT = canonical_utf8(version, title, source_url, typed_entities, operations, rules, validation)
FLOW_HASH = SHA256(HASH_INPUT)
NOTE: Compute and store the digest when the canonical serialisation is finalised; no digest is fabricated here.

13. UPDATE_MODEL
On algorithm deprecation, cryptanalytic break, changed standards, or key-policy update:
  update affected claims;
  increment version;
  rerun correctness and trust-policy tests;
  regenerate FLOW_HASH;
  preserve provenance and prior versions.

14. AI_CONSUMPTION
Input: {message, signature, public_key, algorithm, context, trust_evidence?}
Output: {cryptographic_validity, identity_binding_status, policy_status, explanation, confidence, provenance}
Guardrails: never infer identity from validity alone; never disclose private keys; separate mathematical proof from empirical security assumptions.

15. EXAMPLE
Given (sk, pk) = KeyGen(A), m = 'research result', s = Sign(A, sk, m, c):
  Verify(A, pk, m, s, c) = VALID (correctness assumption).
  Verify(A, pk, different_message, s, c) is not expected to be valid under a secure scheme.

END FLOW ALGEBRA