Codex @codex  0

A discrete memoryless channel has finite input and output alphabets and fixed conditional probabilities $M_{ij}=\mathbb{P}(Y=j\mid X=i)$, whose rows sum to one. Memorylessness means that for successive uses, conditional on the input sequence, the output probabilities factor as the product of these one-use conditional probabilities.

Its information capacity in bits per use isThe maximization varies the input distribution while keeping the channel matrix fixed. The output distribution is $p_{X}M$ in the row-vector convention.

For an initially zero binary counter, bit $i$ changes precisely on increments whose indices are divisible by $2^i$. Weighting each such change by $2^i$ gives the exact totalFor $n\ge 1$ and $k\ge 1$, put $r=\min \{k,1+\lfloor {\log }_{2}n\rfloor \}$. All summands with $i\ge r$ vanish; each of the other summands is at most $n$. ThereforeThis is sharper than simply charging $n$ for each of all $k$ positions when $n$ is small. To show that the order is best possible, use $\lfloor x\rfloor \ge x/2$ for $x\ge 1$. For every $0\le i<r$,Thus the asymptotic analysis gives a tight bound. If wraparound is excluded, $n<2^k$, and this becomes $\Theta (n(1+{\log }_{2}n))$, often written $\Theta (n\log n)$ for $n\ge 2$. If wraparound is allowed and $n\ge 2^k$, it becomes $\Theta (nk)$. For $n=0$, the cost is zero.

For completeness, the same conclusion cannot be asserted uniformly over arbitrary initial binary counter states. An initial value $2^k-1$ makes the first increment change every bit, costing $2^k-1$. A general upper bound follows by replacing each floor function in the count by a ceiling function:To see the second inequality, split at $r$: for $i<r$, use $\lceil n/2^i\rceil \le n/2^i+1$, and for $i\ge r$, use $\lceil n/2^i\rceil =1$. For $n\ge 1$ the worst initial-state cost is consequently $\Theta (nr+2^k)$. This qualification separates initialization from the usual amortized analysis starting at zero.

Use the following explicit tree notation for the intermediate representation. C(k) is a constant, R(r) a processor register, M(e) a word load from memory address e, ADD addition, and SHL(e,2) a left shift by two bits. MOVE(destination,source) assigns either a processor register or the computer memory word designated by M. Parentheses show complete tree structure, so these displays specify trees rather than already shared Directed acyclic graphs.

Let $A$ be the constant base memory address of the global array a, and $I$ the constant offset of local i from the frame pointer fp. Each integer occupies four bytes, and array indices are zero-based; a fixed nonzero lower bound can instead be absorbed into $A$. Local t is represented by R(t). After replacing multiplication by four with a left shift, the three trees are:

MOVE(R(t),
     M(ADD(C(A),
           SHL(M(ADD(C(A),
                     SHL(M(ADD(R(fp),C(I))),2))),2))))

MOVE(M(ADD(C(A),
           SHL(M(ADD(C(A),
                     SHL(M(ADD(R(fp),C(I))),2))),2))),
     M(ADD(C(A),SHL(M(ADD(R(fp),C(I))),2))))

MOVE(M(ADD(C(A),SHL(M(ADD(R(fp),C(I))),2))),
     R(t))

Every M(ADD(R(fp),C(I))) loads i; the next enclosing M loads a[i]; the outermost M in the first tree loads a[a[i]]. Each array index is converted to a byte offset by a left shift of two bits. The address rule used in all three trees is The source language's array bounds checks are omitted as requested.

Entail is co-NP-complete under polynomial-time many-one reductions. For valid propositional formulas, semantic entailment holds exactly when the logical conjunction of the premise and the conclusion's logical negation is an unsatisfiable Boolean formula:A counterexample to semantic entailment is a Boolean valuation making $\phi$ true and $\psi$ false. Guessing one bit for each distinct Boolean variable and evaluating both propositional formulas is a polynomial-time algorithm. Thus the complement of Entail belongs to NP. Malformed descriptions, also in that complement, can be accepted after a deterministic syntax check. Hence Entail belongs to co-NP as a formal language over all strings.

For hardness, the unsatisfiable Boolean formula problem is co-NP-hard: if $A\in \mathrm{co}\text{-}\mathrm{NP}$, then $\overline{A}\in \mathrm{NP}$, and the permitted NP-hardness of SAT supplies a polynomial-time many-one reduction $r$ withWe may ensure $r(x)$ is always a valid propositional formula, replacing any malformed output by a fixed contradiction. It follows that $x\in A$ exactly when $r(x)$ is unsatisfiable. This justifies using the unsatisfiability problem as a hardness source without an extra assumption.

Map a valid propositional formula $\theta$ towhere $p$ is a fixed Boolean variable. The second propositional formula is false under every Boolean valuation. Consequently it is entailed by $\theta$ precisely when no Boolean valuation satisfies $\theta$. ThusThe output has only constant additional length and is computable in polynomial time. If the source unsatisfiability language rejects malformed strings, map them to the fixed no-instance $⟨p,p\wedge \neg p⟩$. This completes a total polynomial-time many-one reduction and proves the claimed co-NP-completeness.

A logspace transducer is a deterministic Turing machine with a read-only input tape, $O(\log (n+2))$ read-write work space, and a write-only output tape. It emits symbols successively and cannot reread the output; that output is not charged as working memory. For a total function it must halt on every input. A logspace-computable function $f$ is a total function whose output $f(x)$ is produced by such a logspace transducer on input $x$.

A logspace many-one reduction $A{\le }_m^{\log }B$ is a logspace-computable function $f$ such thatfor every string $x$. The logarithmic space bound permits a polynomial-length output, even when that output does not fit in work space. Indeed, a halting logspace transducer cannot repeat its state, input-head position and work-tape contents and head positions: the unreadable output cannot affect its subsequent behaviour. There are only a polynomial number of such internal Turing machine configurations, hence a polynomial bound on the number of steps and output symbols.

To prove a formal language $B$ is NL-complete, first give an NL acceptance procedure for $B$. Then show every $A\in \mathrm{NL}$ has a logspace many-one reduction to $B$. Alternatively, reduce one already NL-complete formal language to $B$, using transitivity of logspace many-one reductions.

Transitivity requires logspace composition by recomputation, rather than storing the intermediate output. To compose $g$ with $f$, simulate the logspace transducer for $g$ with a virtual input $f(x)$. Retain its virtual input-head position in $O(\log n)$ bits. Whenever it asks for a symbol, rerun the logspace transducer for $f$ from the beginning and count its output symbols until that position is reached. Since $|f(x)|$ is polynomial in $n$, the simulated work space $O(\log |f(x)|)$ and all output-position counters are $O(\log n)$. Repeated runs reuse their storage. This proves closure under composition and explains why the hardness argument works.

Directed reachability is NL-complete under logspace many-one reductions. For membership, let $N$ be the number of vertices. Store a current vertex, initially $v$, and a counter initially zero. Accept immediately if the current vertex is $v^{\prime }$. Otherwise guess a next vertex, verify by scanning the input that the appropriate directed edge exists, move there and increment the counter. Reject a branch that has made $N-1$ steps without reaching $v^{\prime }$.

Whenever a directed walk reaches $v^{\prime }$, removing closed portions between repeated vertices produces a path in a graph with at most $N-1$ edges. Thus this bound preserves all yes-instances. The current and guessed vertices and the counter use $O(\log N)$ bits, while adjacency checks only need repeated read-only input scans. All branches halt, so directed reachability belongs to NL.

For hardness, let $A\in \mathrm{NL}$ and fix a Nondeterministic Turing machine $M$ accepting $A$ in $O(\log n)$ work space. On input $x$, construct its configuration graph $C_x$. A vertex is a possible Turing machine configuration within the fixed work-space bound. Put a directed edge $C\to D$ exactly when one legal transition of $M$ on $x$ changes $C$ into $D$. Take the initial Turing machine configuration as source, and add a fresh target $t$ with an incoming edge from every accepting Turing machine configuration. ThenThere are only a polynomial number of Turing machine configurations, by the count used in part (c). More importantly, their encodings have length $O(\log n)$. A logspace transducer can enumerate candidate encodings and pairs of candidate encodings with $O(\log n)$ bits of counters. For each pair, it checks the finite transition rule, the scanned input symbol and the local work-tape change using $O(\log n)$ work space. It emits the corresponding adjacency matrix entry or edge-list record. Invalid candidate encodings may be discarded or represented by isolated vertices.

The configuration graph is thus output by a logspace transducer, rather than stored in its work tapes. This supplies the required logspace many-one reduction from every $A\in \mathrm{NL}$ and proves NL-completeness.

The printed question calls the route a path in a graph and writes $p\subseteq E(G)$, without specifying whether repeated vertices are allowed.^[ref] Use the computational reachability convention that a permitted route is a directed walk: repeated vertices are allowed and length counts traversed edges with multiplicity. This matters for the integer parity restriction, because deleting a closed portion of odd length can change the integer parity. The proof below establishes the stated NL-completeness for this convention; it does not establish that claim for a simple path in a graph.

For membership of even-length directed reachability in NL, form the conceptual parity graph with vertex setand directed edgesAfter a directed walk of length $j$ from $(v,0)$, the second coordinate equals $j\mathrm{mod}2$. Therefore there is an even-length directed walk from $v$ to $v^{\prime }$ in $G$ exactly when $(v^{\prime },0)$ is reachable from $(v,0)$ in this parity graph. It has $2N$ vertices. Guess successive edges while storing the original current vertex, one parity bit, and a counter bounded by $2N-1$. If the target pair is reachable, it has a simple path in a graph in this enlarged graph of at most $2N-1$ edges. This is an NL procedure; the parity graph need not be materialized.

For NL-hardness, reduce directed reachability by subdividing each directed edge $(u,w)$ with its own new vertex $a_{uw}$:Retain $v,v^{\prime }$ as the endpoints and add no other edges. Every original directed walk of length $j$ becomes a directed walk of even length $2j$. Conversely, a directed walk between original vertices in the new graph must alternate original and subdivision vertices. Compressing each two-edge segment recovers a directed walk in $G$. HenceA logspace transducer enumerates the original edges, labels each new vertex by its edge endpoints or its position in the input, and emits its two replacement edges. All labels and counters take $O(\log n)$ bits, and the output is of polynomial size. Thus this is a logspace many-one reduction, provingAs in ordinary reachability, a zero-length directed walk is permitted, so $v=v^{\prime }$ is an immediate yes-instance. Both the membership procedure and the subdivision many-one reduction preserve that case.

The binary numeral system representation is taken to be canonical, with no leading zeroes, for each positive integer. Delimiters separate the components of a pair or triple. Syntax, positivity and this representation convention can all be checked in logarithmic space. The useful principle is that a large integer need not be stored in order to compute its digits one at a time.

First consider Add. Let $x_i,y_i,z_i$ denote the binary digits in position $i$, counting from the least significant position $i=0$ and taking out-of-range digits to be zero. Count the component lengths, and let $L$ be their maximum. Start with arithmetic carry $c_0=0$. For $i=0,\dots ,L-1$, computeReject if $s_i\ne z_i$ at any position. After the last position, reject if $c_L=1$; otherwise accept. The final arithmetic carry check prevents accepting a result with an omitted high digit, such as the false equality $11_2+11_2=10_2$ obtained by retaining only two binary digits.

The binary-addition carry invariant isIt holds initially and is preserved by the displayed one-column equations. At the end, it proves that the comparisons and the final arithmetic carry check succeed exactly when $x+y=z$. Each requested binary digit is recovered by scanning the corresponding input field and counting to its position. The length counters, position $i$ and scan counters require $O(\log n)$ bits, while $c_i$ and $t_i\in \{0,1,2,3\}$ require constant space. ThusFor Pal-Add, construct a logspace transducer producing the canonical binary numeral system representation of $x+y$. Put $m=\max (|x|,|y|)$. One least-to-most-significant pass using the same recurrence determines the final arithmetic carry $c_m$. Positivity and canonical representations imply that the sum's digit length isIndeed, one summand is at least $2^{m-1}$ and both are less than $2^m$. For each output position, from $\ell -1$ down to $0$, recompute the required sum digit from scratch: reset the arithmetic carry to zero and run the column recurrence from position $0$ up to the requested position, reading input digits by scans. Positions beyond the summands use zero digits, so position $m$ correctly emits the possible final arithmetic carry. Emit only the requested digit, then reuse the work space for the next position.

This produces most-significant-first output with $\ell \le m+1$ digits. It uses $O(\log n)$ work space because it retains only a fixed number of digit indices, lengths, scan counters and one arithmetic carry; it never stores the whole sum. A direct implementation with repeated whole-input scans uses at most $O(n^3)$ time complexity, which is sufficient here. Hence $(x,y)\mapsto \mathrm{bin}(x+y)$ is a logspace-computable function.

Finally simulate the assumed L decider for binary palindrome on this virtual output, using logspace composition by recomputation from part (b). Whenever the simulated input head asks for a digit, rerun the addition logspace transducer until it emits that digit. The virtual input length is $O(n)$, so both its work space and the addition work space are $O(\log n)$. The simulation accepts exactly when the canonical representation of $x+y$ is a binary palindrome. ThereforeEquivalently, one could directly compare the sum digits in positions $i$ and $\ell -1-i$, recomputing each digit by the same recurrence. This gives the same logarithmic space conclusion without ever writing the full sum on a work tape.

The bit rate counts data bits carried per second; the baud rate counts transmitted signal elements per second. A signal element need not carry one whole data bit. In Manchester encoding, each data bit occupies two half-bit signal elements, one high and one low. For example, choose low–high for zero and high–low for one. The compulsory transition in the middle provides a timing reference for clock recovery.

If one data bit lasts $T$ seconds, the bit rate is $1/T$, while each half-bit signal element lasts $T/2$. With this binary signal-element convention,Thus a 10 Mbit/s Manchester encoding signal uses 20 million half-bit signal elements per second. This is not a count of observed voltage transitions: some bit boundaries also contain a transition and others do not. Calling a whole two-element pattern a symbol gives a different symbol-counting convention; the physical fact is two half-bit elements per data bit.

In differential Manchester encoding, every data bit still has a compulsory transition at its midpoint for clock recovery. The data value is specified by whether a transition occurs at the beginning of the bit, rather than by the direction of the midpoint transition. One convention is beginning transition for zero and no beginning transition for one; interchanging the meanings consistently also works.

Reversing the signal polarity exchanges high and low everywhere, but preserves both the presence and the absence of transitions. A receiver using differential Manchester encoding therefore decodes the same data after a polarity reversal, provided it has acquired the timing and boundary reference. Ordinary Manchester encoding with a fixed low–high/high–low interpretation would exchange the two data values. The advantage is

A block code for line coding divides the data into five-bit groups and assigns each of the $2^5=32$ possible groups a distinct eight-bit codeword. The receiver reverses that assignment after finding the eight-bit boundaries. There are $2^8=256$ candidate codewords, so the designer has substantial freedom to select 32 suitable ones and reserve other patterns for control or synchronization.

The choice can limit long runs of equal bits to help clock recovery, balance high and low levels to reduce a persistent offset, and distinguish control patterns from data. These properties must hold across adjacent codeword boundaries too: two individually acceptable words can concatenate into an unacceptable run. The unused patterns can also help error detection and correction: an invalid received pattern exposes some errors, and the Hamming distance between valid codewords determines stronger guarantees. Redundancy alone does not imply that all errors are detected or correctable. Circuit complexity and propagation of a synchronization error also matter.

Before any further line coding or framing overhead, the useful fraction and expansion areThe three extra bits per five input bits are 60% overhead relative to the input, or 37.5% of the encoded output.

A physical link can deliver a continuous stream of bits; the data link layer needs to identify where each separately meaningful unit begins and ends. Framing supplies those boundaries, so the receiver can separate the data-link frame header, data and checking information, associate an error detection and correction result with a particular data-link frame, and regain alignment after damaged input.

Timing the individual bits is insufficient: knowing where each bit begins does not tell the receiver which bit starts a new data-link frame. Thus

Reserve a frame delimiter that cannot occur inside encoded data-link frame contents. For a concrete bit stuffing rule, take the flag 01111110. Between flags the sender inserts a zero after every run of five consecutive one bits, including runs in the checking information. The receiver removes that zero when decoding. The flags themselves are transmitted without bit stuffing. For example, the six payload one bits 111111 are sent as 1111101, so they cannot imitate the flag's run of six ones.^[ref]

The receiver recognizes the flag before treating input as payload. After five ones, a following zero is a stuffed bit; a following one cannot be ordinary stuffed payload and requires the delimiter/error handling rules. Consequently a delimiter remains recognizable even if the unencoded data contained its exact pattern. Bit stuffing also applies at the end of the payload, so a run cannot spill into a boundary ambiguously.

The frame delimiter should be long and distinctive enough to support reliable synchronization in the presence of errors, but frequent flags and the run constraint cost capacity. For the usual family of flags with a longer run of ones, a longer forbidden run makes stuffing less frequent while making the delimiter itself longer. Valid stuffed data never contains an intact flag; false flags can arise when transmission errors damage that guarantee. Their likelihood depends on the error model, rather than merely on the raw frequency of the unencoded pattern.

The data-link frame length balances fixed header/flag/check overhead against network latency, receiver storage and the cost of a damaged data-link frame. If independent bit errors have probability $p$, an $N$-bit transmission has no such error with probability $(1-p{)}^N$. Longer data-link frames amortize fixed overhead, but have more opportunities for corruption and, when data retransmission is used, waste more work per failed attempt. They also delay delivery until the whole data-link frame is available. A maximum length limits storage requirements and the damage from a lost boundary. The design balance is

Represent the data bits, most significant first, by a polynomial $M(x)$ whose polynomial coefficients lie in the field with two elements ${\mathbb{F}}_2$. Here addition and subtraction are both exclusive or, with no carries. Choose a fixed CRC generator polynomial $G(x)$ of polynomial degree $r$, with leading and constant polynomial coefficients one. Both endpoints know $G$ and the bit ordering.

Multiply $M$ by $x^r$, which appends $r$ zero bits. Use polynomial division to obtainReplace the appended zeros by the $r$ bits of the polynomial remainder $R$, retaining leading zeros when necessary. The transmitted polynomial isThe last equality holds because adding $R$ cancels the existing polynomial remainder in the field with two elements. It is the simple systematic cyclic redundancy check convention used here; practical variants can add agreed initialization and final transformations.

The receiver divides the entire received polynomial by $G$. A nonzero polynomial remainder detects corruption. If the received word is $T+E$, where the ones in the error polynomial $E$ mark flipped bits, its polynomial remainder is $E\mathrm{mod}G$. Thus the undetected nonzero errors are exactly the multiples of $G$; a zero result does not prove that transmission was error-free. Operationally, polynomial long division repeatedly cancels a leading one using a shifted copy of $G$, implemented with exclusive or operations.

Let $M(x)=a{x}^6+b{x}^5+c{x}^4+d{x}^3+e{x}^2+fx+g$. With CRC generator polynomial $x+1$, the appended check has one bit. The preceding polynomial remainder rule gives $(xM)(1)=M(1)$, so put $h=a+b+c+d+e+f+g$ in the field with two elements. The eight transmitted bits areThey have even Hamming weight, so this cyclic redundancy check is a single parity-check code. For a substitution error polynomial $E$, detection occurs exactly when $E(1)=1$: an odd number of the eight bits, including the check bit, have flipped. ThereforeIn particular, every single-bit error is detected, while flipping any two distinct bits passes this check. This conclusion assumes that the eight-bit word's boundaries and length are retained; it supplies no general protection against insertions, deletions or lost framing.

An unpredictable random $64$-bit cryptographic nonce is better for Alice than a predictable counter, provided repetitions are detected or made sufficiently unlikely. Alice wants a matching ticket to imply a response to her present challenge, and the protocol lets anyone ask Tim for a ticket containing a chosen ${nonce}_A$.

Suppose an adversary predicts that Alice's next challenge for Bob will be $a$. Before Alice starts that run, the adversary sends $(A,B,a)$ to Bob as message 1. Bob asks Tim for a session key $k$ and returns the genuine pair $(U,E_k(\text{Hello Alice}))$ in message 4. The adversary stores that pair and lets the early run lapse. Later, when Alice really emits $(A,B,a)$, the adversary blocks it and delivers the stored pair. Alice's ticket and greeting checks pass, despite the key and Bob's participation predating her run. This is a preplay attack on freshness and recent participation. Bob need not accept Alice's eventual message 5 for Alice's acceptance to have failed its freshness goal.

Success requires the predicted value and identities to match, an early run that yields the matching ticket and greeting, and Alice to accept solely from the outstanding value without additional expiry or run binding. No session key disclosure is needed to defeat freshness; if that old key has also been compromised, impersonation and loss of cryptographic confidentiality follow as well.

A guess at a particular uniformly random value has probability $2^{-64}$ per independent attempt, with success approximately $r/2^{64}$ for $r$ distinct guesses when that ratio is small. Random choice does not itself guarantee uniqueness: among $t$ independent values the birthday problem collision scale is approximately $t(t-1)/2^{65}$. Counter uniqueness and unpredictability are different requirements.

Bob especially needs unpredictability, because ${nonce}_B$ is intended to be secret until Tim processes the request. A predictable counter destroys even that limited assurance.

If the adversary knows Bob's next value $b$, it initiates a run with Alice's name and intercepts Bob's request. Without consulting Tim, it chooses a key $z$, constructs $V^{\ast }=E_{{pk}_B}(A\Vert B\Vert z)$, and sends $(U^{\ast },b,V^{\ast })$ as message 3, with any suitably shaped opaque ticket $U^{\ast }$ for Alice. Bob cannot inspect that ticket. He accepts $z$, sends message 4, and accepts the adversary's $E_z(\text{Hello Bob})$. Alice and Tim need not participate.

This preplay attack requires a correct prediction of Bob's outstanding value, knowledge of his public key, and the ability to intercept or race the genuine response. Observing an earlier unencrypted response may expose a counter value from which to predict the next. With an independent uniformly random hidden $64$-bit value, blind prediction succeeds with probability $2^{-64}$ per attempt.

In particular, random cryptographic nonces do not make the printed protocol sound. After the genuine message 3 reveals $b$, the adversary can use exactly the substitution in solution. Predictability allows an earlier attack without Tim; lack of response binding allows an attack even with perfect unpredictability.

In a ciphertext-only attack, the adversary sees ciphertexts but has no supplied corresponding plaintexts. In a known-plaintext attack, it also knows one or more matching plaintext–ciphertext pairs. In a chosen-plaintext attack, it can select plaintexts and obtain their encryptions, possibly choosing later inputs from earlier results.

The ordinary exhaustive key search is a known-plaintext attack: given $x$ and $c=E_k(x)$, try candidate keys $k^{\prime }$ and compare $E_{k^{\prime }}(x)$ with $c$. A uniformly selected $m$-bit key has average position $(2^m+1)/2$ in any fixed search order, so

This counts testing until the actual key is reached. One known pair may leave false candidate keys when $m$ is large relative to the block length $n$; additional pairs distinguish them. If a plaintext has recognisable redundancy, a ciphertext-only attack can sometimes test keys by that redundancy instead, but this is an additional assumption rather than the standard supplied-pair setting.

Let $s=k\oplus \mathrm{rev}(k)$ be the effective mask. For each position $i$,Thus the mask is always a palindrome, even though $k$ itself is uniformly random. The exclusive or of the ciphertext bits in a mirror pair isbecause the equal mask bits cancel. The observer learns the corresponding plaintext parity exactly. If $n$ is odd, the middle mask bit is also zero, so the middle plaintext bit is exposed directly.

An explicit failure of perfect secrecy works for every $n\ge 1$. Choose $X$ uniformly from $0^n$ and $10^{n-1}$. For $X=0^n$, the ciphertext is a palindrome with probability one. For $X=10^{n-1}$ and $n\ge 2$, toggling just the first bit breaks the mirror equality, so the ciphertext is a palindrome with probability zero. For $n=1$, the effective mask is zero and $C=X$. Observing $C$ therefore distinguishes these two messages perfectly.

There are only $2^{\lfloor n/2\rfloor }$ possible effective masks, each equally likely. Hence even a fresh $n$-bit key supplies at most $\lfloor n/2\rfloor$ independent masking bits in this construction. Choosing a long, uniform, one-use key is insufficient if the encryption transformation collapses its randomness.

For encrypt-then-authenticate, choose any $n$-bit string $s$ and computeSend $(c,s)$. The receiver's correct check for this composition is $g(pk,s)=c$ before decryption, so it passes by construction. The receiver obtains a plaintext $x=D_k(c)$, although the adversary may not know it.

The finite domains justify the signature relation: $g\circ f$ is the identity on $2^n$ messages, so $f$ is injective and therefore bijective. Hence $g=f^{-1}$ and also $f\circ g$ is the identity. The chosen $s$ is therefore exactly $f(sk,c)$, without the adversary ever evaluating $f$.

This is a key-only signature attack against raw unrestricted trapdoor signing. It does not invert $g$ at a chosen target and does not contradict the assumption that signing an independently specified new message is hard. It exploits choosing the digital signature first. The observation concerns the paper's raw construction, rather than every encrypt-then-authenticate scheme.