Cryptography

The design and analysis of protocols that protect information or authenticate messages in the presence of adversaries. It includes ciphers, digital signatures and cryptographic hash functions.

Cryptographic leakage is information about secret inputs or internal state that an observer obtains through the interfaces or observations admitted by a security model. A model can explicitly permit some disclosures, such as message length, while requiring other information to remain hidden. In universal composability, an ideal cryptographic functionality states such permitted disclosure through information sent to the cryptographic simulator.^[ref]

A simple cryptographic leakage function writes the disclosed value as $L=\ell (X)$, where $X$ is a secret random variable. An original example takes $X$ uniform on the 256 eight-bit strings and lets $L$ reveal its first four bits. Before observing $L$, every complete secret has probability $1/256$. Afterwards, exactly sixteen secrets remain equally likely, so the best complete-secret guess succeeds with probability $1/16$. The calculation assumes that the observer has no additional correlated information.

Using information entropy measured in bits, this example givesHere $H(X\mid L)$ is conditional entropy and $I(X;L)$ is mutual information. Revealing four bits does not make the entire secret known, but it reduces a sixteen-way uncertainty in the first half to certainty. Guessing probability and entropy describe related but different quantities; the simple powers of two arise from this example's uniform conditional distributions.

Length disclosure gives another operational example. Suppose a cryptographic environment privately chooses a uniform bit $b$, then submits a one-byte message when $b=0$ and a two-byte message when $b=1$. Observing the length reveals $b$ exactly, even if the encryption hides all message contents at each fixed length. An ideal service that reveals no such distinction cannot support the same pre-delivery observation. The security specification must either permit length disclosure or require an implementation to conceal it.

The permitted observations must be stated before making a security claim. A cryptographic transcript that omits timing does not itself prove security against timing observations. Likewise, a model that permits a chosen disclosure does not assert that the disclosure is harmless for every application. The useful question is which secrets remain hidden from an observer with that particular view.

A cryptographic leakage function specifies which observation of secret state is disclosed in a model. A deterministic version writes $L=\ell (X)$, where $X$ is a secret random variable. It is a description of an observer's information, not an encryption algorithm. An ideal cryptographic functionality can explicitly send permitted disclosures to its cryptographic simulator; Canetti's secure-communication example permits disclosure of message length.^[ref]

For an observed value $l$ of positive probability, possible secrets lie in its preimage under $\ell$. Their posterior probabilities areEqual likelihood within that set requires a uniform prior there; it is not a consequence of the word leakage.

An original example takes $X$ uniform on all eight-bit strings and lets $\ell (X)$ be its Hamming weight. The disclosure has only nine possible values, but its consequences vary. If $L=4$, there are $\left(\genfrac{}{}{0ex}{}{8}{4}\right)=70$ equally likely secrets and the best exact guess succeeds with probability $1/70$. If $L=0$, the secret is certainly the all-zero string. A rare disclosure can therefore determine the complete secret even though the observation is encoded in only four bits.

Averaging optimal exact-guess success over all disclosed weights givescompared with $1/256$ before observation. This Hamming-weight leakage of a uniform bit string distinguishes an average guessing probability from the worst conditional outcome.

Specify repeated observations and any correlated side information too. Two individually limited disclosures can jointly identify a secret. A randomized or noisy observation is described by a conditional channel rather than only a deterministic function. Stating an allowed cryptographic leakage function makes a security claim precise; it does not establish that the disclosure is harmless for every application.

Let $X$ be uniformly distributed over the $2^n$ bit strings of length $n$, and disclose only its Hamming weight $W$, the number of one-bits. This is a deterministic cryptographic leakage function. Its consequences depend on the observed weight, even though $W$ has only $n+1$ possible values. A permitted disclosure belongs in the security model; the existence of that model does not establish that the disclosure is harmless.^[ref]

There are $\left(\genfrac{}{}{0ex}{}{n}{w}\right)$ strings of weight $w$. Hence $W$ has a binomial distribution, and conditional probability givesfor each compatible string $x$. The optimal complete-string guess therefore succeeds with probability $1/\left(\genfrac{}{}{0ex}{}{n}{w}\right)$ after that observation. For $n=4$, observing $w=2$ leaves six equally likely strings; observing $w=0$ identifies 0000 exactly.

Averaging over disclosed weights yieldscompared with $2^{-n}$ before disclosure. For four bits this changes $1/16$ to $5/16$. The worst conditional outcome has success probability one. An average guarantee and a guarantee for every observation are consequently different claims.

The information entropy calculation answers another question. Since $W$ is determined by $X$, the mutual information satisfies $I(X;W)=H(W)$ andFor $n=4$, $H(W)\approx 2.03064$ bits and $H(X\mid W)\approx 1.96936$ bits. These entropy values are not obtained by taking the logarithm of the average guessing probability. All calculations here assume the uniform prior and no additional correlated observation.

A cryptographic test vector is a specified collection of algorithm inputs, parameters and expected outputs used to check an implementation. Exact byte encodings are part of the vector: a key displayed in hexadecimal represents bytes, not necessarily the displayed characters. A known-answer test compares a computed result with the supplied answer. RFC 4231 provides such vectors for several HMAC instantiations.^[ref]

For its Test Case 1, use a key of twenty bytes each equal to hexadecimal 0b, and the eight ASCII message bytes spelling Hi There. HMAC with SHA-256 must produce

b0344c61d8db38535ca8afceaf0bf12b881dc200c9833da726e9376c2e32cff7.

The output has 64 hexadecimal digits, hence 32 bytes. The key has twenty bytes; using the forty ASCII characters obtained by writing 0b twenty times supplies a different key. Adding a newline to the message supplies different message bytes too.^[ref]

A good vector identifies the complete algorithm variant. An unkeyed SHA-256 digest of that message is not the expected HMAC result, and SHA-512/256 is a different hash operation despite its equal digest length. HKDF additionally needs its salt, initial material, context and requested output length; its primary specification supplies all those fields together with the expected extraction and expansion results.^[ref]

Passing a vector establishes agreement for those inputs. It does not prove collision resistance, key secrecy or a cryptographic protocol's security. Nor does one short input exercise every implementation path. Vectors covering long keys, truncation and boundary lengths can reveal mistakes that a single example misses; RFC 4231 includes separate cases for those behaviours.^[ref]

A known-answer test checks a cryptographic implementation by supplying fixed, completely specified inputs and comparing its output with an independently established expected value. The input and expected output together form a cryptographic test vector; the test is the act of executing the implementation and checking that agreement. Published HMAC vectors explicitly support conformance testing.^[ref]

For example, take the four key bytes 4a 65 66 65, representing Jefe, and the 28 ASCII message bytes representing what do ya want for nothing?. The published HMAC with SHA-256 result is

5bdcc146bf60754e6a042426089575c75a003f089d2739839dec58b964ec3843.

A known-answer test decodes that 64-digit hexadecimal value to 32 expected bytes, computes the keyed result, and compares all 32 bytes. Neither the message's terminating string-storage zero nor a newline is part of these input bytes.^[ref]

Several different errors can cause failure: decoding hexadecimal as text, including an extra byte, using the wrong key, selecting another cryptographic hash function, or serializing the result incorrectly. A failure establishes disagreement with the vector; it does not identify the responsible step by itself. A useful test harness reports the selected function, input lengths and first differing output position.

Passing also has a precise limit. A defective implementation that returns this expected value for this one input and zero for every other input passes this test. Thus a finite set of known-answer tests is evidence about those cases, not a proof of correctness for all inputs or a proof of cryptographic security. Boundary cases complement ordinary short examples: the primary vector set includes output truncation and keys longer than a hash's input block.^[ref]

An independently fixed expected value is essential. Computing the “expected” output with the same implementation under test can reproduce the same defect on both sides. Known-answer tests are especially useful for reproducible checks of exact byte conventions across different implementations.

A key derivation function transforms initial keying material, together with specified parameters and context, into one or more cryptographic keys. The output lengths and security requirements belong to the application. HKDF separates extraction of a pseudorandom key from expansion into the needed output material; the design and its assumptions are analysed in Krawczyk's primary paper.^[ref]

Derivation does not create secret information from nothing. For an original counting example, suppose a secret input is uniformly selected from only $2^{20}$ possibilities and every other derivation input is public and fixed. A deterministic function producing 256 output bits can then reach at most $2^{20}$ different outputs, not all $2^{256}$ strings independently. An adversary able to enumerate the original possibilities can enumerate the derived possibilities too. More output bytes alone do not raise the input's information entropy.

Context supports cryptographic domain separation. For a stipulated application, deriving a sending key with an unambiguous label send and a receiving key with receive assigns different intended roles to the outputs. Deriving both with exactly the same inputs and parameters instead reproduces exactly the same key. This deterministic equality is a functional property, not a failure to obtain fresh randomness during a repeated call. HKDF's info input is explicitly intended to bind output to application context.^[ref]

Parameter encodings must also distinguish intended inputs. Naive concatenation makes pairs ab, c and a, bc both encode as abc. A defined length-prefixed or otherwise unambiguous encoding avoids that collision of descriptions. Changing the encoding changes the KDF input even if a user informally regards the labels as equivalent.

A KDF therefore supplies a specified transformation and separation mechanism. Its security still depends on the initial material, the selected construction and the surrounding cryptographic protocol. It does not by itself authenticate the peer that supplied a shared secret.

Cryptographic domain separation distinguishes intended uses of cryptographic computations by encoding their roles or contexts into the inputs. A key derivation function can thereby derive different role-specific cryptographic keys from shared initial material. For HKDF, the info field is specifically intended to bind the output to application context, including relevant protocol and algorithm information.^[ref]

For an original computed example, use the extraction result from RFC 5869 Test Case 1, then expand it to sixteen bytes with the ASCII context app/send. The result is

e2f1c135562168a517b5c5451fd68f76.

Keeping the same intermediate key and length but changing context to app/recv gives

c5302399f25698fce7c4e33ad0c8b479.

These are new computations using the specified HKDF expansion; the contexts are illustrative application labels, not additional published test vectors. Repeating exactly the first set of inputs reproduces exactly its first output. The distinction is encoded in the context rather than obtained by hoping repeated deterministic calls will differ.

The encoding must preserve the intended distinction. Raw concatenation sends both field pairs ab, c and a, bc to abc. A length-prefixed encoding with one-byte lengths instead gives 02 61 62 01 63 and 01 61 02 62 63. These five-byte strings differ, even though their unstructured character concatenations agree. The one-byte example assumes each field is shorter than 256 bytes; a protocol must define its full length limits and encoding.

Different encodings do not mathematically guarantee different finite-length digests: distinct inputs can still collide. Domain separation supplies a structured distinction on which the construction's security argument can rely. It also does not authenticate a context string supplied by an attacker. The surrounding cryptographic protocol must establish the identities and agreed roles whose labels it encodes.

Salt and context have different jobs in HKDF. The cryptographic salt is an extraction input, while info is an expansion input. Reusing one parameter as if it automatically established every other required binding changes the specified construction.

A length-prefixed encoding represents a variable-size field by writing a length before its payload. The length's units, width, endianness, permitted range and inclusion or exclusion of the prefix itself are part of the serialization format. For example, the Transport Layer Security presentation language counts vector lengths in bytes and encodes variable-length vectors with a length field whose width follows the specified upper bound.^[ref]

An original two-field format uses one unsigned byte for each payload length:Here $|x|$ counts payload bytes and $\Vert$ is concatenation. The ASCII fields ab and c give 02 61 62 01 63, while a and bc give 01 61 02 62 63. Bare concatenation would give 61 62 63 in both cases. This distinction is useful when a cryptographic hash function or message authentication code must commit to two separate fields.

The encoding is an injective function on its stated input set. Read the first length byte $n$, then exactly $n$ bytes for $x$; read the next length byte $k$, then exactly $k$ bytes for $y$. This reconstructs both fields uniquely. For a complete two-field record, require that no bytes remain. Missing bytes, absent length fields or forbidden lengths are rejected rather than silently reinterpreted. The proof depends on these parsing rules, not merely on putting some number before the data.

A fixed-width length field also imposes a representable limit: 256 payload bytes cannot be encoded by the one-byte scheme above. Truncating that length modulo 256 would make the parser see zero and destroy the intended format. A larger format must specify a larger prefix or a different encoding.

Finally, byte count and text-character count can differ. The text é has two bytes c3 a9 in UTF-8, so its one-byte length prefix here is 02. A length prefix provides boundaries; cryptographic domain separation may additionally require a field type, role label or protocol version to distinguish records with different meanings.

A fixed-width length field uses a fixed number of encoded bytes to state a payload length. The payload itself can vary in size. For an unsigned $k$-byte field in big-endian endianness, bytes $b_0,\dots ,b_{k-1}$ representThe format must additionally define the length unit, permitted range and whether headers count toward it. TLS uses unsigned, network-order integers and gives variable-length vectors a prefix wide enough for their declared maximum; its vector length counts bytes, not elements.^[ref]

For an original two-byte length-prefixed encoding, prefix 02 01 means $2\cdot 256+1=513$ payload bytes in big-endian order. The complete field then occupies $515$ bytes. The same two prefix bytes would mean $258$ under little-endian interpretation, changing the boundary of every following field. The byte order is therefore part of the serialization, not a display preference.

A two-byte field can represent at most $65535$; a format permitting payload lengths only up to $400$ must reject larger encoded values even though they fit the field. Conversely, a $300$-byte payload needs prefix 01 2c under this convention. Truncating it to one byte would declare only $44$ bytes. A format change cannot be implemented by silently discarding high-order bits.

Length-prefix validation before allocation checks the declared range and available input before reserving space or consuming the payload. A complete decoder also specifies how truncation and trailing bytes are handled. Byte count and character count differ for encodings such as UTF-8. A length prefix supplies boundaries; a field's role or type may still need binding through cryptographic domain separation.

Length-prefix validation before allocation checks that an encoded payload length is permitted and safely usable before requesting memory allocation based on it. A fixed-width length field bounds what the encoding can represent; an application can impose a smaller limit. TLS vectors, for example, have explicitly specified minimum and maximum byte lengths.^[ref]

For an original decoder model, let $n$ be the decoded unsigned payload length, $L$ the application limit and $R$ the bytes remaining in a complete input buffer after the prefix. Before allocating or consuming that payload, requireCheck that the complete prefix is available before reading it. For a two-byte big-endian prefix 02 01, $n=513$. With $L=400$ and $R=300$, the input fails both checks. Prefix 01 2c instead declares $300$ bytes and satisfies these two bounds. The example counts only payload bytes in $n$.

Arithmetic needs its own bound. If an allocation includes $h$ additional bytes and the size type's maximum value is $M$, verify $h\le M$ and $n\le M-h$ before forming $n+h$. Computing the sum first can already cause integer overflow. Similarly, when allocating $n$ elements of positive size $s$, check $n\le \lfloor M/s\rfloor$ before multiplication.

For a streaming decoder, $n>R$ can mean that more input is needed rather than that the final message is malformed. It still does not justify consuming unavailable bytes or allocating beyond the stated resource limit. Nested fields need bounds relative to their enclosing field. These checks establish safe structural handling of a length-prefixed encoding; they do not authenticate the sender or validate the payload's meaning.

A cryptographic salt is an additional input used by a cryptographic construction to vary or condition its processing of secret material. Its required properties depend on the construction. In HKDF, the salt is the key input to the extraction HMAC, while the initial keying material is the HMAC message. The salt is normally non-secret, and the specification permits reuse and defines a default when no salt is provided.^[ref]

For HKDF extraction,Fixing both inputs gives a deterministic intermediate key. Changing salt changes the HMAC computation even if the initial material is unchanged. The public salt can therefore distinguish extraction contexts; it does not need to be counted as another secret shared by the participants. The RFC's security discussion also requires attention to how salts are obtained and to adversarial control of inputs.^[ref]

An original counting argument separates public variability from secret uncertainty. Suppose secret $X$ is uniform over $2^{20}$ values and independent public salt $S$ is uniform over $2^{16}$ values. There are $2^{36}$ possible input pairs before either value is known. Once $S=s$ is public, however, only $2^{20}$ candidate secrets remain. For any deterministic derived key $K=f(X,S)$,where $H$ is information entropy and the conditioning uses conditional entropy. Producing a 256-bit key string does not turn that twenty-bit secret source into 256 bits of conditional uncertainty.

The same example shows why per-target guessing and preparing a table for every possible salt are different tasks. A table enumerating every stipulated secret/salt pair would have $2^{36}$ entries, while enumeration for one known salt still has $2^{20}$ candidate secrets. This counts the toy input space, not the cost or guarantee of a particular password-processing scheme.

A salt is also distinct from a cryptographic nonce, whose permitted reuse is specified by the consuming algorithm, and from the expansion context used for cryptographic domain separation. Parameter names alone do not make their requirements interchangeable.

HKDF is an HMAC-based key derivation function with extraction and expansion stages. Extraction combines initial material $\mathrm{IKM}$ with a cryptographic salt to produce an intermediate key $\mathrm{PRK}$. Expansion uses that key, context info and an output length $L$. RFC 5869 specifies the construction as an Informational RFC.^[ref]

Writing $\Vert$ for concatenation, its equations areThe output is the first $L$ bytes of $T_1\Vert \cdots \Vert T_N$, where $N=\lceil L/h\rceil$ and $h$ is the digest length in bytes. The counter occupies one byte, giving $L\le 255h$. The first HMAC argument is the key; swapping its two arguments changes the construction.^[ref]

For SHA-256, $h=32$. Requesting $L=42$ therefore requires two expansion blocks, using all 32 bytes of the first and ten of the second. The maximum specified length is $255\times 32=8160$ bytes. Requesting a longer output under that one-byte counter rule is not an additional iteration of the same specification.

RFC 5869 Appendix A.1 supplies a reproducible example: 22 input bytes each equal to hexadecimal 0b, salt bytes 00 through 0c, and info bytes f0 through f9, with $L=42$. The resulting output, written as hexadecimal, is

3cb25f25faacd57a90434f64d0362f2a2d2d0a90cf1a5a4c5db02d56ecc4c5bf34007208d5b887185865.

That is 84 hexadecimal digits representing 42 bytes. Each expansion block depends on its predecessor as well as the context and counter; independently hashing the counter would describe a different function.^[ref]

A salt need not be secret, while the derived key material must receive the protection required by its role. Context can distinguish protocol uses through cryptographic domain separation. Neither changing a label nor asking for more bytes supplies additional secret entropy to a weak input.

Provable security is a mathematical guarantee that a cryptographic protocol satisfies a precisely defined security property under stated assumptions. A cryptographic security game specifies the adversary's observations, permitted queries and success condition. A security reduction transforms an adversary breaking that property into an algorithm solving another problem, such as one covered by a computational hardness assumption. The reduction accounts for both running time and success probability.^[ref]

For an original numerical example, suppose a proved reduction givesAn attack with advantage $0.01$ would yield an algorithm $B$ with advantage at leastIf the underlying assumption excludes that advantage at $B$'s running time, the scheme attack is excluded too. A larger multiplicative loss would weaken the inference; ignoring the reduction's resource cost could also make the resulting bound uninformative.

The definition matters as much as the deduction. A message authentication code theorem concerns forgery under the specified access model; it does not thereby establish encryption confidentiality. The useful result is an explicit chain from the application's formal security property to the assumption being studied.^[ref]

A cryptographic security game is a precisely specified experiment defining what an adversary may observe and do, and what counts as success. Its rules include key generation, random choices, permitted queries, resource limits and a winning condition. Security statements bound the winning probability or a specified cryptographic distinguishing advantage, often as a function of a cryptographic security parameter. A reduction proves a result about that defined experiment, not every informal meaning of the word secure.^[ref]

For an original one-challenge confidentiality game, an adversary chooses two equal-length plaintexts $m_0,m_1$. A challenger samples an independent uniform bit $b$, encrypts $m_b$, and gives the ciphertext to the adversary, which returns a guess $b^{\prime }$. In this simplified game there are no additional encryption or decryption queries. DefineRandom guessing has advantage zero. A success probability $5/8$ gives advantage $1/8$. Another convention doubles this value; stating the normalization avoids a factor-of-two ambiguity when comparing bounds.

The one-time pad supplies a complete worked example. Let messages and the independently uniform key $k$ contain $n$ bits, and set $c=m_b\oplus k$. For any fixed $n$-bit string $c_0$ and either challenge bit,since exactly one key gives that ciphertext. The ciphertext distribution is identical for $b=0$ and $b=1$, so no function of it and the chosen messages can outperform guessing. The advantage is zero in this game.

Changing the rules can change the result. Reusing the pad for another message supplies the relation $c_1\oplus c_2=m_1\oplus m_2$. A chosen-plaintext attack game grants access to encryptions selected by the adversary; a chosen-ciphertext attack game grants additional decryption access with carefully stated restrictions. The proof for the one-challenge experiment does not establish security under those extra observations.

A forgery game for a message authentication code instead asks for an accepted message/tag pair meeting its freshness condition. That is a different winning event from guessing an encrypted message. The cryptographic security game makes these distinctions inspectable and provides the exact target for a security reduction.

Cryptographic distinguishing advantage measures how differently a specified test behaves on two distributions or experiments. For a binary-output distinguisher $D$ and distributions $X,Y$, one common definition isA cryptographic security game must state its convention and the allowed computation and observations. Provable security uses such quantitative bounds together with the resources required by a security reduction.^[ref]

An original two-world example explains a common normalization difference. Let $X$ be a bit equal to one with probability $3/4$, and $Y$ a bit equal to one with probability $1/4$. The test $D(x)=x$ has ${\Delta }_D=1/2$. If a challenger selects the world with equal prior probability and the observer guesses X on output one and Y on output zero, its success probability is $3/4$. Its advantage above random guessing is $1/4$, half the probability-gap convention.

In general, orienting the decision rule toward the larger probability givesThus a statement of advantage $0.02$ can mean either a probability gap of $0.02$ or a success probability $0.52$, depending on the convention. The numerical security claim is incomplete until that choice is specified.

If every event test is allowed, the largest probability gap is total variation distance. Restricting the distinguisher to an efficient algorithm yields a computational notion: distributions can differ substantially statistically while being difficult for a resource-bounded observer to distinguish. Computational indistinguishability describes the asymptotic version indexed by a cryptographic security parameter.

For any fixed $D$, adding and subtracting its intermediate acceptance probability givesFor example, bounds $0.003$ and $0.004$ on two successive changes give an overall bound $0.007$. This simple triangle inequality explains how a sequence of controlled experiment changes can support a security argument. The distributions, permitted observers and resource costs must remain the ones justified at each step.

A security reduction turns an adversary breaking one stated cryptographic property into an algorithm breaking another property or solving an assumed-hard problem. It specifies the simulation given to the adversary, the relation between success probabilities and the additional computation required. A primitive's hardness assumption can then imply a bound for the constructed scheme.^[ref]

An original reduction illustrates this without a numerical loss. Let a pseudorandom generator expand a uniformly sampled $\lambda$-bit seed $s$ into an $n$-bit string $G(s)$. Consider one-use encryption $c=m\oplus G(s)$ for $n$-bit messages. Suppose adversary $A$ distinguishes which of $m_0,m_1$ was encrypted in the one-challenge cryptographic security game.

Construct a distinguisher $D$ given a string $w$ that is either a generator output or uniformly random. Run $A$ to obtain its message pair, select an independent uniform bit $b$, and give it $c=m_b\oplus w$. Output one exactly when $A$ guesses $b$ correctly. If $w=G(s)$, this is the real encryption experiment. If $w$ is uniform, it is a one-time pad, and the success probability is $1/2$. ThereforeAny nonzero advantage for that encryption game gives the same distinguishing advantage against the generator. The reduction adds the challenge-bit choice, an exclusive or and bookkeeping to the cost of running $A$. It establishes this one-use confidentiality result, without claiming authenticity or safe pad reuse.

Other reductions lose probability or require more computation. For a separate stipulated bound,an adversary with advantage $10^{-3}$, $q=100$ and $\delta =10^{-5}$ implies primitive advantage at least $9.9\times 10^{-6}$. Conversely, a primitive bound $10^{-8}$ at the reduction's actual running time gives only the scheme bound $1.1\times 10^{-5}$. The coefficient and additive term are original illustrative values, not a published bound for a named cipher.

The cryptographic security game and resource accounting remain part of the theorem. A proof cannot transfer a primitive bound stated for a small computation budget to a reduction that exceeds it, or replace the exact scheme's assumptions by a different informal hardness claim.

Symmetric-key cryptography uses shared secret key material for cryptographic operations, including encryption and authentication. In a symmetric encryption scheme, a recipient holding the secret key can recover the plaintext from a ciphertext. Keeping the algorithm public does not prevent security: the secret is the key, not the procedure.

For example, a one-time pad encrypts a bit string $m$ as $c=m\oplus k$ and decrypts with $c\oplus k=m$. Perfect secrecy requires an independently uniform secret key as long as the message and never reused. Reusing it gives $c_1\oplus c_2=m_1\oplus m_2$, exposing a relation between messages. Ordinary efficient symmetric ciphers instead offer computational guarantees under stated assumptions. Confidentiality alone does not ensure message integrity; authenticated encryption addresses both.^[ref]

A computational hardness assumption states that a specified computational task cannot be solved efficiently in a specified model and input distribution. A useful cryptographic statement identifies the parameter controlling size, the adversary's resources and the permitted success probability. Difficulty on occasional worst-case instances alone need not protect the instances produced by a key-generation algorithm.

For example, a proposed encryption scheme may reduce message recovery to solving learning with errors instances sampled in a particular way. The reduction says that a successful attack would yield a solver for those instances; security remains conditional on the hardness assumption and the implementation meeting the model. Oded Regev's lattice reduction makes this relationship unusually concrete, connecting a noisy average-case problem to worst-case lattice problems through a quantum reduction.^[ref]

Authenticated encryption combines message confidentiality with protection against unauthorized alteration. Encryption produces a ciphertext with authentication information; decryption returns either the verified plaintext or a failure indication. Associated data can be authenticated without being encrypted, for example a packet's routing header.^[ref]

For example, a receiver should reject a modified payment amount instead of releasing a plausible but corrupted plaintext. An authenticated header can bind that amount to the intended record type while leaving the header readable. A nonce is an additional per-encryption input; schemes requiring nonce uniqueness can lose their guarantees if a key/nonce pair is reused. The exact rule belongs to the selected construction. Authentication establishes validity under a key; the surrounding cryptographic protocol still determines who owns that key.^[ref]

The Fiat-Shamir transform replaces a verifier's random challenge in a suitable interactive proof protocol by a cryptographic hash function of the public statement and transcript so far. For a commitment $a$ about statement $x$, the prover computes $c=H(x,a)$ and then a response $z$. A verifier recomputes $c$ and checks the response. In signature applications the message is also bound into the hashed transcript.

This removes an interaction, but hashing an arbitrary protocol is not automatically secure: the protocol structure, transcript encoding and security model matter. CRYSTALS-Dilithium uses a version with aborts, discarding unsuitable responses through rejection sampling so that released responses have the required distribution. This illustrates how the transformation and its concrete implementation need separate arguments.^[ref]

ML-DSA is the module-lattice digital signature scheme standardized in FIPS204 in2024, derived from CRYSTALS-Dilithium. Key generation creates a public verification key and a secret signing key. Signing combines a sampled masking vector with a message-derived challenge; bounds and rejection sampling prevent unsuitable responses from revealing the secret. Verification reconstructs the commitment information and checks the challenge and response bounds.^[ref]

A valid signature authenticates a message under a particular public key; it does not hide the message or independently establish whose public key was supplied. The standardized parameter sets ML-DSA-44,65 and87 have different key/signature sizes and security targets. Implementations must follow the standardized encodings and checks rather than assuming every older Dilithium implementation accepts the same byte strings.

ML-KEM is the module-lattice key encapsulation mechanism standardized in FIPS203 in2024, derived from CRYSTALS-Kyber. Key generation supplies an encapsulation key and a decapsulation key. Encapsulation returns both a ciphertext and a shared secret; decapsulation uses the secret key to recover the shared secret from that ciphertext.^[ref]

The mechanism is built on noisy module-linear equations and a chosen-ciphertext-secure transformation. Decapsulation performs an internal consistency check and uses an alternate secret-derived result for invalid ciphertexts rather than exposing a simple decryption-failure response. ML-KEM-512,768 and1024 are separate standardized parameter sets. Establishing a secret this way does not authenticate the peer by itself: an unauthenticated exchange remains vulnerable to public-key substitution. A surrounding cryptographic protocol supplies identities and transcript binding.

CRYSTALS-Dilithium is a lattice-based digital signature design whose arithmetic uses vectors of polynomials modulo a fixed polynomial and integer modulus. Its design follows the Fiat-Shamir transform with aborts: derive a challenge from a commitment and message, form a secret-dependent response, and use rejection sampling to avoid releasing responses with an unsuitable distribution. The designers chose uniform sampling rather than requiring a discrete Gaussian sampler.^[ref]

The goal is efficient signing and verification while making forgery difficult even for proposed quantum attacks on its underlying assumptions. ML-DSA is the later standardized descendant. The relationship is historical and mathematical, not a promise of interchangeable parameter names, key encodings or signatures: a protocol must identify the exact scheme and version it uses.

CRYSTALS-Kyber is a key encapsulation mechanism based on module learning with errors. Its underlying encryption uses polynomial-vector arithmetic with small secret and error coefficients; a transformation around that encryption supplies resistance to chosen-ciphertext attacks. Encapsulation produces a fresh shared secret and the ciphertext needed by the decapsulating party.^[ref]

Using a module structure reduces representation and computation costs compared with a fully unstructured matrix description. The security claim concerns the difficulty of the resulting noisy algebraic problem; the word lattice does not by itself prove resistance to every attack. ML-KEM standardizes a descendant of Kyber with exact algorithms and encodings. Applications must name the chosen version rather than treating Kyber and ML-KEM as byte-for-byte synonyms.

A key encapsulation mechanism consists of key generation, encapsulation and decapsulation algorithms. Given a public encapsulation key $pk$, encapsulation produces $(K,c)$: a shared secret $K$ and an encapsulation ciphertext $c$. Given the secret key $sk$ and $c$, decapsulation produces the same $K$, except for any explicitly bounded correctness failure.^[ref]

For example, a sender can encapsulate $K$, derive a session encryption key from $K$ and agreed context, then use authenticated encryption for a long message. The ciphertext $c$ carries the encapsulated secret, while the separate encrypted payload carries the message. Chosen-ciphertext security considers an attacker who can request decapsulation of other ciphertexts; correctness alone does not provide that protection. Authentication and binding the public key to the intended recipient remain responsibilities of the surrounding cryptographic protocol.

Lattice-based cryptography constructs security mechanisms from computational problems associated with Euclidean lattices and related noisy linear equations. A lattice is easy to describe by a basis, while finding particular short vectors or recovering hidden information from noisy equations can be difficult in suitably chosen dimensions and parameter ranges. Different constructions rely on different problems and reductions.

For the schematic learning with errors relation $b=As+e(\mathrm{mod}q)$, $A$ and $b$ are public, while the secret vector $s$ is masked by a small error vector $e$. With no error, ordinary modular linear algebra may recover $s$ efficiently when the system has suitable rank. The noise changes the problem. Real security depends on error distribution, dimension, modulus, available samples and attack model, rather than merely making the displayed equation look complicated. ML-KEM and ML-DSA illustrate encapsulation and signature applications; they use structured module arithmetic to obtain practical sizes and computation costs.

Learning with errors asks for a secret vector $s$ from noisy modular linear observations. An observation has a known random vector $a$ andwhere $e$ is sampled from a specified small-error probability distribution. The search version recovers $s$; the decision version distinguishes these samples from uniformly random pairs. Parameters and the error distribution are essential parts of the problem.

For a tiny illustration, let $q=17$, $s=(3,5)$ and $a=(2,4)$. The exact inner product is $26\equiv 9(\mathrm{mod}17)$, while error $e=-1$ gives $b=8$. Without errors, enough independent equations admit ordinary modular linear solving; adding errors obstructs that direct approach. This tiny instance is not a secure parameter choice. Oded Regev's work connects appropriately parameterized instances to worst-case lattice problems and constructs a public-key cryptography from the assumption.^[ref]

Module learning with errors is a structured version of learning with errors in which matrix entries and secret components are elements of a specified polynomial ring. A typical relation isHere $A$ is a public $k\times k$ matrix of ring elements, while $s$ and $e$ have sampled small coefficients. Multiplication combines polynomial multiplication with reduction by the defining polynomial and coefficient modulus.

A ring element packs $n$ coefficients, giving structured linear operations without storing an arbitrary dense matrix of all scalar coefficients. This saves space and computation, while introducing an algebraic structure that the security assumption must cover. CRYSTALS-Kyber uses module-LWE, and ML-KEM standardizes a related encapsulation construction. This is a conditional hardness basis, not a proof that every choice of ring and parameters is secure.^[ref]

Trying candidate keys and testing them against known plaintext–ciphertext pairs or another available verification condition. A uniformly selected key in a space of size $2^m$ appears at average position $(2^m+1)/2$ in a fixed enumeration.

An attack in which an adversary selects plaintexts and obtains their encryptions, possibly choosing later requests adaptively.

An attack using one or more known plaintext–ciphertext pairs, without necessarily controlling the plaintexts.

An attack using observed ciphertexts without supplied corresponding plaintexts. Recognisable message redundancy or publicly testable relations can sometimes provide key-testing predicates.

A symbolic adversarial model of Danny Dolev and Andrew Yao granting control of the network while treating cryptographic operations as ideal constructors and destructors. An adversary may split unprotected tuples, replay messages and encrypt with known public keys, but cannot decrypt without the required key. Separate encrypted components are not automatically bound to adjacent clear fields.

A cryptographic protocol specifies an interaction between parties using cryptographic operations to achieve a security property under stated assumptions. A key-exchange protocol, for example, aims to establish a shared secret while controlling what an adversary can learn or alter. Messages need meanings, order, identities and session context in addition to encryption or signatures. A sound primitive does not by itself make every composition secure: replaying a valid message in the wrong session can break an otherwise plausible exchange. Correctness and security depend on the adversary model and the exact transcript rules.

A cryptographic transcript is the specified record of messages exchanged during a cryptographic protocol execution. Its content depends on the purpose: a public communication record differs from a participant's complete private view, which can also include its input, secret state and randomness. Order, message boundaries and the identities or roles associated with messages can matter.

For a concrete standardized use, Transport Layer Security 1.3 authenticates a transcript hash computed from selected handshake messages in their prescribed order. It includes handshake type and length headers, but excludes record-layer headers. Its retry path specifies a special replacement for the first client message.^[ref]

An original toy transcript makes the distinction between messages and concatenated payloads visible. Suppose a sender transmits ab and then c. The payload sequence is $(\mathtt{ab},\mathtt{c})$. Another execution transmits a and then bc. Both flatten to ASCII bytes 61 62 63, even though they have different first messages. A length-prefixed encoding preserves the distinction as 02 61 62 01 63 versus 01 61 02 62 63. A hash cannot recover boundaries that were omitted before hashing.

Direction can be equally important. The records “initiator sends yes” and “responder sends yes” contain identical payloads but assert different behavior. A format used to authenticate those assertions must bind the relevant roles, either explicitly in the encoded record or through an unambiguous protocol context. This toy rule is not a replacement for the TLS transcript format.

In a security proof, the observer's view and its correlations must be specified. A cryptographic simulator that samples messages with correct individual frequencies may still produce the wrong joint probability distribution with the cryptographic environment's retained inputs. A cryptographic transcript also discloses only the observations it records: a transcript omitting timing cannot by itself justify a security claim against timing observations.

A transcript hash is a compact fingerprint of the encoded record under the relevant cryptographic hash function assumptions. An unkeyed hash alone does not identify the speaker: a digital signature or message authentication code must bind it to an authenticated context when that is the intended guarantee.

A transcript hash is a cryptographic hash function applied to the defined encoding of a cryptographic transcript. The included messages, ordering, boundaries and algorithm are part of its definition:In TLS1.3 the inputs include handshake type and length headers but exclude record-layer headers. A retry has an explicit synthetic-message substitution; ordinary payload concatenation is not that protocol's definition.^[ref]

An original ten-byte example uses a deliberately separate toy format: one type byte, a two-byte big-endian payload length, then payload. The first message is 01 00 02 48 69, carrying ASCII Hi; the second is 02 00 02 4f 4b, carrying OK. The SHA-256 digest of these ten bytes in that order is

2cd107ca2c002f392a6c26a4b2ed3caca0c23ecf0d67e3a790e787800caadc19.

Reversing the two encoded messages gives

7efaeb2cd69eae34b41ea8316a104ba7964254bd86e9b9ba14df77bb29163b66.

These are original computations, not TLS test vectors. Both message order and the encoded headers contribute to the input bytes.

Incremental hashing of a cryptographic transcript feeds those byte sequences into one continuing hash context and finalizes at the required point. It computes the same digest as hashing their full concatenation. Computing $H(H(M_1)\Vert M_2)$ is a different operation: the finalized inner digest replaces the first message and introduces its own hashing boundary. A running internal state is not interchangeable with a completed digest.

An unkeyed transcript hash alone does not authenticate who spoke. A digital signature or message authentication code binds it to the required authenticated context. Nor can a hash recover message boundaries omitted by an ambiguous encoder. TLS's Finished message illustrates the separate authentication step by applying HMAC to the specified transcript hash.^[ref]

Incremental hashing of a cryptographic transcript supplies successive encoded message bytes to one continuing cryptographic hash function state. Finalizing after the selected messages gives the same transcript hash as hashing their full concatenation in one call. TLS explicitly permits implementing the handshake computation using a running hash.^[ref]

For an original SHA-256 example, updating with ASCII ab and then c gives the same result as one update with abc:

ba7816bf8f01cfea414140de5dae2223b00361a396177a9cb410ff61f20015ad.

A chunk boundary is an input-delivery detail. It does not insert a separator byte or end a message. A continuing implementation must preserve the processed bit count and any incomplete block as well as its chaining state; final padding encodes the complete input length. SHA-256's specification processes 512-bit blocks and pads the complete message before its final compression operations.^[ref]

In particular, $H(\mathtt{ab}\Vert \mathtt{c})$ and $H(H(\mathtt{ab})\Vert \mathtt{c})$ specify different inputs. The latter inserts a completed digest, with its already finalized hashing boundary, where the original bytes belonged. It is not an incremental implementation of the former.

The protocol must still define which bytes enter the state. TLS includes handshake headers in the transcript hash and specifies a special first-message substitution after a retry. A running hash implements that prescribed input, rather than defining the transcript by itself.^[ref] An unkeyed digest also supplies no sender authentication by itself; the protocol must bind it through its specified digital signature or message authentication code.

Universal composability is a framework for specifying and proving security of cryptographic protocols so that their guarantees survive the framework's protocol-composition operation. It compares a real implementation with an ideal cryptographic functionality describing the intended service, permitted leakage and adversarial influence. Ran Canetti's primary work develops the composition guarantee, including concurrent executions.^[ref]

The comparison uses a cryptographic simulator in the ideal execution and a cryptographic environment trying to distinguish the executions. Schematically, in the computational formulation,Here $A$ is the real adversary, $S$ the simulator, $Z$ the environment, $z$ an auxiliary input and $\lambda$ the cryptographic security parameter. The participants have the specified computational bounds, and ${\approx }_c$ denotes computational indistinguishability. The simulator is chosen for the adversary before universally quantifying over environments; a different simulator chosen after seeing each environment would be a weaker requirement.^[ref]

An original distinguishing example shows why permitted leakage belongs in the specification. Suppose an ideal channel hides a message's length before delivery, but a proposed real implementation exposes that length. An environment privately selects a uniform bit $b$ and supplies an honest sender a one-byte message if $b=0$ or a two-byte message if $b=1$. It asks the adversary to guess $b$ before the honest recipient supplies any output. Visible length lets a real adversary guess perfectly. An ideal simulator receiving no length or content information can guess only with probability $1/2$. The environment accepts when the guess equals its private bit, giving a probability gap $1/2$.

That mismatch can be addressed by changing the implementation, for example with suitable padding, or by specifying the intended length leakage in the ideal service. The two choices describe different security properties. Correctly delivering messages does not by itself resolve the distinction.

The composition theorem permits replacing an ideal-service call by a protocol that realizes that service, under the theorem's interface and execution-model conditions. This supports modular proofs: a larger protocol need not reanalyse the lower-level implementation from scratch.^[ref] The guarantee belongs to the modelled setup, identities and allowed interactions; an isolated confidentiality game is not automatically a proof of universal composability.

A cryptographic environment is the interactive external context used to judge a cryptographic protocol in universal composability. It supplies honest parties' inputs, observes their outputs, communicates with the adversary, and ultimately outputs a decision bit. The comparison asks whether this bit's probability distribution changes detectably between the real execution and an ideal execution with a cryptographic simulator.^[ref]

The cryptographic environment models other software using the service, including choices depending on earlier outputs. It can retain private information with which to check later responses. Its view therefore includes the relationship between inputs, outputs and adversarial messages, not just isolated packet statistics.

An original two-bit example shows why that relationship matters. Let $B$ be a random variable with the uniform distribution on a finite set $\{0,1\}$. One system returns $(B,B)$; another returns $(B,C)$ with $C$ an independent uniform bit. Each individual coordinate has the same marginal distribution in both systems. Nevertheless, the test “accept exactly when the two bits agree” has acceptance probabilitiesIts cryptographic distinguishing advantage is $1/2$. Matching each output's marginal does not match their joint probability distribution. An interactive cryptographic environment can perform corresponding consistency checks against its retained inputs.

In the computational definition, the cryptographic environment has the specified polynomial time bound indexed by the cryptographic security parameter. For each real adversary, one cryptographic simulator must handle every allowed cryptographic environment; choosing a new simulator after learning which particular context will test it changes the requirement.^[ref]

This breadth explains the usefulness of universal composability: a service can be analysed within a larger application context. The conclusion still concerns the interactions and cryptographic leakage admitted by the stated execution model.

A cryptographic simulator is an algorithm in a security proof that reproduces an adversary's externally observable behavior using the interfaces and cryptographic leakage allowed by an ideal cryptographic functionality. In universal composability, substituting it for the real adversary should leave every allowed cryptographic environment unable to distinguish real and ideal executions efficiently.^[ref]

The central question is what information the simulator receives. An original elementary example uses a one-time pad. For a fixed $n$-bit message $m$, let its fresh secret key $K$ be uniform on $\{0,1{\}}^n$. Its ciphertext is $C=m\oplus K$, where $\oplus$ is bitwise exclusive or. For every $n$-bit value $c$,A simulator told only $n$ can therefore reproduce this one ciphertext's distribution by generating $n$ independent uniform bits, without knowing $m$. With $n=5$, each of the 32 possible ciphertexts has probability $1/32$ in both constructions. This is a direct distribution calculation, not a complete universal composability proof for a messaging system: other visible inputs, outputs and correlations would also need to match.

Now modify the toy system so its visible packet includes a secret input bit $b$ in the clear. Suppose the cryptographic environment selected $b$ uniformly and the ideal service reveals neither $b$ nor any correlated information before the simulator must report its guessed packet bit $g$. In the real system the environment's test $g=b$ succeeds with probability one. Any simulator whose information is independent of $b$ succeeds with probability $1/2$, even without a computation bound. The cryptographic distinguishing advantage is therefore $1/2$.

Allowing the ideal service to reveal $b$ would remove that particular simulation obstacle, but would specify a different disclosure policy. A valid simulator must use the actual permitted cryptographic leakage, rather than assume access to an honest party's private data.

More generally, reproducing a cryptographic transcript requires its correlations with the cryptographic environment's state to be correct. Sampling plausible-looking individual messages is insufficient. Efficiency also matters: an unbounded reconstruction algorithm does not supply a polynomial time simulator when the security definition requires one.

An ideal cryptographic functionality is an executable specification of a desired cryptographic service, represented as a trusted computation. Its interfaces specify inputs, outputs, state, permitted cryptographic leakage and permitted adversarial influence. In universal composability, honest-party forwarding interfaces connect it to the cryptographic environment, while the cryptographic simulator uses its adversarial interface.^[ref]

An ideal service is a way to state the security goal; it does not assert that the deployed system contains a physically trusted central machine. A cryptographic protocol realizes the service only if the relevant real/ideal comparison is proved.

For a concrete original specification, consider a single-message channel between two fixed, honest parties, with no party corruption in this toy model. Its state begins empty. On the designated sender's submission of $(\mathrm{sid},m)$, it stores the message under the session label $\mathrm{sid}$ and marks it pending. It reveals the session label, sender, recipient and byte length $|m|$ to the adversarial interface, but not $m$. A later delivery instruction naming that pending session makes it output the stored $m$ to the designated recipient and mark the session delivered. Further delivery instructions for that session have no effect; a second submission for the same session is rejected.

This state machine gives both message authentication and message confidentiality specific meanings. The adversarial interface has no instruction for replacing the stored message or impersonating the designated sender. It can delay delivery indefinitely. Thus the toy specification permits length disclosure and denial of delivery, while excluding content disclosure through that interface, message replacement and repeated delivery. These are separate choices, rather than consequences of the word “secure”. The primary tutorial similarly distinguishes authenticated communication, delayed delivery, corruption and message-hiding guarantees.^[ref]

For an example execution, the sender submits ASCII bytes 41 42 43 under a fresh session label. Before delivery, the simulator learns length three and the endpoints. On the first delivery instruction the recipient receives those three stored bytes. A second delivery instruction produces no new recipient output. If no delivery instruction arrives, the message remains pending. An observed recipient output 41 42 44 would violate this toy specification, regardless of whether it had the correct length.

Stating these transitions makes a proof obligation testable: an implementation must match the specified service's observable behavior against every allowed cryptographic environment. Changing the permitted cryptographic leakage, delivery rule or corruption behavior changes the service being implemented.

A cryptographic security parameter is an integer $\lambda$ indexing a family of cryptographic protocols or algorithms. It controls the scale at which efficiency and security guarantees are stated. Theoretical algorithms are often given $1^{\lambda }$, a string of $\lambda$ ones, so polynomial time in that input length means polynomial time in $\lambda$.^[ref]

A typical asymptotic guarantee requires a cryptographically negligible probability: for every fixed $c>0$, the relevant probability eventually falls below ${\lambda }^{-c}$. An exponential such as $2^{-\lambda }$ has that property; $1/\lambda$ does not, because it fails the requirement for $c=2$.

An original idealized guessing example separates a parameter from a concrete security claim. If a secret is uniform among $2^{128}$ possible values and no other information about it is supplied, one fixed guess succeeds with probability $2^{-128}$. Checking $q$ distinct guesses covers at most a fractionof those possibilities. This is a counting argument under the stated uniform-secret model, not a guarantee for every scheme described as having a128-bit key.

The parameter's numerical value, key length, algorithmic cost and actual adversary advantage are related through the particular construction. Naming the parameter alone does not establish a concrete work estimate or compensate for a flaw in the protocol.

A cryptographically negligible probability is a function $\epsilon (\lambda )$ of the cryptographic security parameter that eventually becomes smaller than every inverse power of that parameter. Formally,The threshold $N_c$ may depend on $c$. This is the inverse-polynomial definition of negligibility used in asymptotic cryptography.^[ref]

For example, $2^{-\lambda }$ is negligible because an exponential eventually dominates every fixed power. The function ${\lambda }^{-100}$ is not negligible: it exceeds ${\lambda }^{-101}$ whenever $\lambda >1$. Even the constant $10^{-30}$ is not negligible as a function of $\lambda$, although it is numerically small. Negligibility describes a family of experiments as the parameter grows, rather than a synonym for “unlikely” in one experiment.

An original closure calculation explains why the definition is useful. Suppose an adversary gets at most ${\lambda }^3$ attempts and each has success probability at most $\epsilon (\lambda )$. The union bound gives total success probability at most ${\lambda }^3\epsilon (\lambda )$, without requiring independent attempts. Given any $c>0$, negligibility with exponent $c+4$ eventually givesThus a polynomial number of opportunities preserves negligibility. A concrete numerical guarantee still requires an explicit bound at the chosen parameter; the asymptotic quantifiers alone do not supply that value.

Cryptographic setup is the generation and distribution of initial parameters or other resources required by a cryptographic protocol. Its specification includes the input cryptographic security parameter, the sampling procedure, the public output and any information that must remain secret. Setup is part of the protocol's security model, rather than an arbitrary source of well-formatted constants.

A common reference string gives one example. Parties to a non-interactive zero-knowledge proof may share a public string $\sigma$ sampled by the prescribed setup. The definition describes both its distribution and how that setup participates in real and simulated proof experiments.^[ref]

An original distribution example makes the generation rule explicit. Let a toy setup sample two independent uniform bits $a,b$ and publishIts support is $\{000,011,101,110\}$, each with probability $1/4$. A uniformly sampled three-bit string instead has eight possible values, each with probability $1/8$. The two generators publish strings of the same length, but the second satisfies the parity equation only half the time.

This toy setup is not a secure proof-system construction. It demonstrates why replacing a specified generator by a different random-looking source changes the experiment. Public availability of setup data and correctness of its generation are separate properties.

A proof of knowledge is a proof protocol whose success is linked to an efficient procedure for obtaining a cryptographic witness from the prover's behavior. The procedure is a knowledge extractor, with access to the prover specified by the definition. The ordinary verifier in an interactive proof need not receive the witness during the real exchange.^[ref]

A standard formulation measures a prover's acceptance probability $p(x)$ against a knowledge error $\kappa (x)$. When $p(x)>\kappa (x)$ on an input with a witness, extraction has an expected-time bound of the formfor an appropriate fixed constant $c$. The relation, oracle access and false-input guarantees must also be specified; this expression alone is not the complete definition.^[ref]

For an explicit graph-isomorphism proof protocol extraction, suppose the same commitment graph $H$ has accepting responsesto the two possible challenges. The compositionis a graph isomorphism, hence a witness for the public claim. Rewinding in cryptographic proofs can provide the extractor with differently challenged continuations of a common earlier state.

The formula explains a knowledge claim without invoking a human notion of understanding. Soundness of an interactive proof and zero-knowledge proof privacy are separate requirements: excluding false statements and hiding information do not by themselves establish extraction.

Rewinding in cryptographic proofs is a simulation or extraction technique that returns an algorithmic participant to an earlier state and explores another continuation. The saved state includes the relevant earlier messages and randomness. The technique is justified by the simulator's or extractor's access in the mathematical model; it is not an extra power of the ordinary verifier during a live exchange.^[ref]

For the graph-isomorphism proof protocol, two accepting continuations of the same first message can answer different challenge bits. A knowledge extractor can combine their response mappings to obtain a cryptographic witness. If the prover instead starts again with a different first message, the responses need not combine in that way.

An original retry calculation explains an efficiency condition. Suppose independent simulation attempts succeed with probability $q$ and each failed attempt returns to the required earlier state. The attempt count $T$ has a geometric distribution:At $q=1/2$, the expected number of attempts is2; at $q=1/100$, it is100. Constant or inverse-polynomial success can therefore support expected polynomial time, whereas exponentially rare success generally cannot.

A valid argument must also account for the cost of each attempt and show that the resulting output distribution is correct. Restoring a state, conditioning on success and restarting an entire protocol are distinct operations.

The knowledge error $\kappa (x)$ of a proof of knowledge is a threshold in its extraction guarantee. If a prover's acceptance probability $p(x)$ exceeds that threshold, the definition requires a knowledge extractor with an appropriate expected extraction time. It is not simply the probability that the extractor outputs an incorrect witness.^[ref]

In one standard formulation, on an input in the witness relation's domain,where $C$ is an appropriate polynomial. The extraction guarantee includes the relation and oracle-access conditions as well as this bound.^[ref]

For an original numerical comparison, set $\kappa =1/2$. Acceptance probability $p=0.6$ leaves a gap of0.1, giving a factor10 multiplying $C(|x|)$ in this bound. At $p=0.51$, the factor is100. As success approaches the threshold, the permitted expected running time worsens. At $p=\kappa$, this displayed guarantee does not apply.

The single-challenge graph-isomorphism proof protocol illustrates why a nonzero threshold can be meaningful. A strategy can prepare a relabeling of one public graph and answer only its corresponding challenge, succeeding with probability $1/2$ without using an isomorphism between the two public graphs. Success beyond that baseline is what the extraction analysis exploits.^[ref]

A knowledge extractor is the algorithm that turns sufficiently successful proving behavior into a valid cryptographic witness in the definition of a proof of knowledge. The definition specifies its access to the prover and its efficiency guarantee, often in terms of acceptance probability above a knowledge error. The real verifier need not execute the extractor or learn the witness.^[ref]

A concrete algebraic step appears in the graph-isomorphism proof protocol. Suppose two accepting continuations with the same commitment $H$ supply mappingsThe extractor returnsTo check it, take any edge of $G_0$. The first mapping sends it to an edge of $H$, and the inverse second mapping sends that edge to an edge of $G_1$. Both mappings are bijections, so their composition is a graph isomorphism. The same argument handles nonedges.

This verifies the output once the two continuations have been obtained. A full extraction proof must also justify obtaining them, for example through permitted rewinding in cryptographic proofs, within the promised expected extraction time.

A zero-knowledge simulator solves a different task: it reproduces a verifier-view distribution without the witness. An extractor produces a witness from successful proving behavior. Confusing those output requirements would obscure both the privacy and knowledge guarantees.

The expected extraction time of a knowledge extractor is the expected value of its running time over the randomness in the extraction experiment. The definition specifies the extractor's access to a prover and the cryptographic witness it must return. A common proof of knowledge formulation bounds that expectation, on valid inputs and for acceptance probability $p(x)$ above knowledge error $\kappa (x)$, bywhere $C$ is a fixed polynomial. The access and output conditions are essential parts of the definition.^[ref]

An original asymptotic comparison makes the denominator meaningful. Write $n=|x|$ and suppose $C(n)=n^3$. A gap $p-\kappa =n^{-2}$ gives an expected bound $n^5$. A gap $p-\kappa =2^{-n}$ instead gives $n^3{2}^n$. The displayed extraction theorem therefore does not promise polynomial time uniformly for arbitrarily tiny positive gaps.

An expected bound also permits rare long executions. As a separate toy running-time distribution, let $T=1$ with probability $1-2^{-n}$ and $T=2^n$ with probability $2^{-n}$. Thenalthough the worst-case execution is exponential. This distribution illustrates the distinction; it is not itself an extraction construction. Markov's inequality turns an expected bound into the tail estimate $\mathrm{Pr}(T\ge a\mathbb{E}[T])\le 1/a$ for $a>0$. Converting an extractor into a procedure with a fixed deadline must account for the resulting probability of stopping before it finds a witness.

A cryptographic witness is auxiliary information $w$ that satisfies an efficiently checkable relation for a public statement $x$. Writing the relation as $R(x,w)=1$ separates the claim from the information that certifies it. In a zero-knowledge proof, a prover may use such a witness without revealing it.^[ref]

For an original graph isomorphism example, let the public graphs $G$ and $H$ both be the path with edges $\{1,2\},\{2,3\}$. A witness is a bijection of vertices preserving adjacency. Bothandare valid. A witness need not be unique. With an adjacency-matrix encoding, a verifier can check all vertex pairs and their images in $O(n^2)$ comparisons for an $n$-vertex pair.

The public assertion is that a suitable mapping exists; the witness supplies one particular mapping. Whether that mapping is secret depends on the application. Calling it a witness does not inherently make it a password or a secret key.

A further distinction concerns what a proof establishes. Soundness of an interactive proof protects against acceptance of false statements. A proof of knowledge requires an additional formal relationship between a successful prover and extraction of a witness. Validity of a statement and knowledge of its certificate are not interchangeable claims.

A common reference string is public setup data shared by the parties to a cryptographic protocol. Its distribution is specified by the cryptographic setup. In a non-interactive zero-knowledge proof, the prover and verifier can use the same string $\sigma$ without exchanging a new challenge during each proof.^[ref]

A common random string is the special case in which the setup string is uniformly sampled; more general reference-string models specify another efficiently generated distribution. Being public is compatible with its purpose: the cryptographic witness may be secret even though the reference string is available to everyone.

An original eight-bit example shows why format and distribution are distinct. A uniform eight-bit string satisfiesA generator that always outputs those eight zeros satisfies the same length requirement but gives that event probability one. Checking length alone cannot establish the intended sampling law. This example illustrates a distributional distinction, not a proposed secure setup.

The zero-knowledge simulator may also simulate the joint distribution of setup data and proof. Consequently, the definition must state how setup is generated and what generation-related information the relevant parties possess. A public string with the right shape is not by itself evidence for the security properties of a proof system.^[ref]

A zero-knowledge proof is a proof protocol that convinces a verifier of a public statement's validity while revealing no additional information that the verifier could not efficiently obtain from that statement and its permitted prior information. The formal comparison uses a zero-knowledge simulator: an efficient randomized algorithm that reproduces the verifier's view without the prover's secret cryptographic witness.^[ref]

An interactive proof system separates three questions. Completeness of an interactive proof asks whether an honest prover can convince the verifier of a true statement. Soundness of an interactive proof bounds acceptance of false statements. Zero knowledge concerns information disclosure, so a protocol can pass a soundness test without being zero knowledge. The simulator comparison may require equality of distributions, statistical closeness or computational indistinguishability, depending on the definition.^[ref]

For an original soundness calculation, suppose a fixed false-statement strategy can answer only one of two equally likely challenges. Its acceptance probability is at most $1/2$. If this conditional bound continues to hold after every preceding transcript and fresh challenges are used, $k$ sequential successful rounds have probability at mostAt $k=20$, the bound is $2^{-20}\approx 9.54\times 10^{-7}$. This stipulated calculation does not prove that any particular protocol has the required per-round bound, nor does it establish zero knowledge.

The simulator supplies the separate privacy argument. It must reproduce the relevant distribution efficiently, rather than merely output one accepting transcript. A zero-knowledge proof can be interactive or a non-interactive zero-knowledge proof; its precise verifier and setup assumptions are part of its security claim.

The graph-isomorphism proof protocol is a three-message interactive proof system for the claim that public graphs $G_0,G_1$ are isomorphic. An honest prover in an interactive proof knows a cryptographic witness $\varphi :G_0\to G_1$.^[ref]

The prover samples a uniform vertex permutation $\pi$ and sends $H=\pi (G_0)$. The verifier in an interactive proof replies with a uniform bit $b$. The prover then sends an isomorphism ${\rho }_b:G_b\to H$: use ${\rho }_0=\pi$ or ${\rho }_1=\pi \circ {\varphi }^{-1}$. The verifier checks the mapping and its effect on all edges.

For an original three-vertex example, let $G_0$ have edges $\{1,2\},\{2,3\}$, and let $\varphi$ map $(1,2,3)$ to $(2,3,1)$. Then $G_1$ has edges $\{2,3\},\{1,3\}$. Choose $\pi$ mapping $(1,2,3)$ to $(2,1,3)$; the sent graph $H$ has edges $\{1,2\},\{1,3\}$. The two responses areEach maps the corresponding input graph's edges to those of $H$. These tiny graphs illustrate the checks, not a difficult cryptographic instance.

An honest prover always passes. If the public graphs are not isomorphic, a fixed $H$ cannot have valid responses to both challenges: composing them would give an isomorphism between the inputs. Thus a cheating strategy answers at most one of the two equally likely challenges for that commitment, giving single-round acceptance at most $1/2$.

The standard protocol also admits zero-knowledge simulator constructions. An elementary sampler proves honest-verifier zero knowledge; treating arbitrary verifier strategies requires an additional simulation argument.^[ref]

Honest-verifier zero knowledge is the zero-knowledge proof simulation requirement restricted to a verifier that follows its prescribed algorithm. The zero-knowledge simulator reproduces that verifier's view without the prover's secret cryptographic witness. General zero knowledge must account for permitted deviations by the verifier as well.^[ref]

In the graph-isomorphism proof protocol, the honest verifier chooses an independent uniform challenge bit. A simulator can first choose $b$, sample a uniform permutation $\rho$, set $H=\rho (G_b)$ and output $(H,b,\rho )$. For isomorphic public graphs, this has the same distribution as the honest conversation.^[ref]

An original small example shows what changes if the verifier deviates. Suppose $H$ is a uniform relabeling of a three-vertex path. There are three labeled paths; two contain the edge $\{1,2\}$. A different verifier could choose $b=1$ exactly when that edge is present, soThe elementary honest-verifier simulator chooses a uniform bit and instead gives $\mathrm{Pr}(b=1)=1/2$. It therefore fails to reproduce this changed verifier's view.

This comparison does not show that the standard graph protocol lacks general zero knowledge. It shows that a simulator for the honest verifier does not automatically prove the stronger property. The general analysis may use rewinding in cryptographic proofs to simulate challenges that depend on the first message. The stated adversary model is part of the theorem.

A zero-knowledge simulator is an efficient randomized algorithm that reproduces the relevant verifier-view distribution of a zero-knowledge proof without receiving the prover's secret cryptographic witness. Depending on the definition, the real and simulated views must be identical, statistically close or satisfy computational indistinguishability.^[ref]

The graph-isomorphism proof protocol provides an illuminating example for honest-verifier zero knowledge. On a fixed public isomorphic pair $G_0,G_1$, a real prover sends a random relabeling $H$, receives a uniform challenge bit $b$, and supplies a graph isomorphism from $G_b$ to $H$.^[ref]

An explicit simulation reverses that construction. First choose a uniform bit $b$ and a uniform vertex permutation $\rho$. Setand output the transcript $(H,b,\rho )$. The simulator never needs a mapping between $G_0$ and $G_1$. For an isomorphic public pair, random relabelings of either graph have the same probability distribution; conditional on $b$, the response mapping is uniform in both constructions. Thus the honest verifier's transcript distribution is reproduced exactly.

This does not give a live cheating prover control of the verifier's future challenge. The simulator chooses a complete transcript in a different order from the real exchange. Nor does this simple sampler establish security against an arbitrary malicious verifier, whose challenge could depend on $H$.

The example exposes the central requirement: producing one plausible accepting transcript is insufficient. The simulator must reproduce the specified distribution within the required efficiency bound and adversary model.

A non-interactive zero-knowledge proof allows a prover to send one proof message that a verifier can check without an ensuing challenge-response conversation, while satisfying an appropriate zero-knowledge proof definition. Non-interactive describes the proof exchange; it does not mean that setup assumptions disappear.^[ref]

In a common reference string model, both parties use public setup data $\sigma$. The prover constructs a proof $\pi$ for a public statement $x$, and the verifier evaluatesThe setup's distribution and the adversary's knowledge of its generation must be specified. In the tutorial's basic common-random-string model, the zero-knowledge simulator produces a reference-string/proof pair with the required computational indistinguishability from a real pair.^[ref]