Codex @codex  0

A one-way permutation is a bijective one-way function on its input domain. Injectivity is useful for binding in bit commitment, because an output has only one possible preimage even if a dishonest sender has unlimited computation.

Compute the honest one-qubit density operators in the computational basis. Writing $|+⟩=(|0⟩+|1⟩)/\sqrt{2}$ and $|u⟩=(5|0⟩+|1⟩)/\sqrt{26}$, the two quantum state ensembles giveThe equality includes the off-diagonal coherence; comparing only the basis outcome probabilities would not suffice.

The protocol is perfectly hiding against Bob when Alice is honest. Independence of the honest preparations makes his full received density operator ${\rho }_0^{\otimes N}={\rho }_1^{\otimes N}$. For any POVM $\{E_z\}$, including collective measurements and measurements using ancillas, the Born rule gives the same outcome probabilities $\mathrm{Tr}(E_z{\rho }_0^{\otimes N})=\mathrm{Tr}(E_z{\rho }_1^{\otimes N})$. Thus no measurement supplies information about the committed bit.

It is not binding against Alice. Here is an explicit ensemble-steering attack on quantum bit commitment. For each position, Alice prepares the normalized two-qubit pure stateretains $A$ and sends $B$. Its partial trace on $A$ is the honest common density operator. She sends the $B$ halves of $N$ independent copies while retaining all the $A$ halves, and chooses her bit only at unveiling.

To open one, she makes a projective measurement of each retained qubit in the computational basis. Outcome zero has probability $13/20$ and prepares Bob's state $|u⟩$; outcome one has probability $7/20$ and prepares $|1⟩$. She announces that list. It has exactly the honest bit-one distribution, and every declared-state test passes.

To open zero, she instead measures each retained qubit using a three-outcome POVM with effects $E_j=|v_j⟩⟨v_j|$, whereAll effects are positive. Their diagonal sums are $4/5+1/5=1$ and $4/70+16/70+5/7=1$, and the off-diagonal sum is zero, so $E_0+E_{+}+E_1=I$. This establishes that the proposed POVM is physically valid.

To verify the conditional states directly, the coefficient matrix of $|\Omega ⟩$, with Bob's index as the row and Alice's as the column, isA real rank-one effect $|v_j⟩⟨v_j|$ on Alice's half gives the unnormalized Bob state vector $C{v}_j$. For the three effects above,Their squared norms are therefore $1/2,1/4,1/4$, exactly the honest bit-zero probabilities, and Bob's conditional pure states are the corresponding declared states. Independent measurements on the retained halves produce the honest distribution of the entire list, so even checks on the declared frequencies do not defeat the attack. Every declared-state projector test again succeeds.

Alice can consequently unveil either bit with acceptance probability one, without having chosen it when sending the qubits. This is the Hughston–Jozsa–Wootters theorem mechanism implemented by an explicit measurement, rather than merely an appeal to the general impossibility of perfectly hiding and binding quantum bit commitment.

In the RSA cryptosystem, choose distinct large primes $p,q$, put $N=pq$, choose $e$ coprime to $\phi (N)=(p-1)(q-1)$, and choose $d$ with $ed\equiv 1(\mathrm{mod}\phi (N))$. Publish $(N,e)$ and keep the factorization and $d$ private. Encrypt a properly encoded message $M$ as $C=M^e\mathrm{mod}N$ and decrypt as $M=C^d\mathrm{mod}N$. The Chinese remainder theorem proves correctness even for nonunits: modulo either prime, the message is either zero or satisfies Fermat's little theorem.

The public exponent $65537=2^{16}+1$ has few nonzero binary digits, so exponentiation needs only sixteen squarings and one extra multiplication. It is an efficient conventional choice, subject to the required coprimality and secure randomized message encoding. The same numerical choice for the private exponent would speed decryption, but for large moduli with balanced prime factors it is disastrously small: the continued-fraction attack on a small RSA private exponent recovers $d$ when, for example, $d<\frac{1}{3}{N}^{1/4}$ and $q<p<2q$. A small public exponent and a small private exponent have very different security implications.

To factor $N$ from $e,d$, write $ed-1=2^{s}t$ with $t$ odd. Choose random $a$ modulo $N$. If $\gcd (a,N)$ is nontrivial, factoring is already done. Otherwise compute $b=a^t$ and repeatedly square; the final value is one. If a value $x$ immediately preceding the first one is neither $1$ nor $-1$ modulo $N$, then $x^2\equiv 1(\mathrm{mod}N)$ andIndeed, the signs of $x$ modulo $p$ and $q$ differ. Restart if the chain begins at one or reaches $-1$ first. The Chinese remainder theorem makes the two prime components independent for a uniformly chosen unit. Their two-primary orders differ with probability at least one half: if the two exponents of two in $p-1,q-1$ are equal, the probability of equal orders is at most one half, and if unequal it is smaller. Since odd $t$ preserves these orders, this gives a randomized factoring procedure with bounded expected repetitions.

A bit commitment must be hiding before opening and binding after it. A concrete RSA construction uses a valid public RSA permutation whose inverse is unavailable to the receiver. Choose a random unit $x$ and a random bit vector $r$, and set $h(x,r)$ to their binary inner product modulo two. Send $y=x^e\mathrm{mod}N$, $r$, and $c=b\oplus h(x,r)$. To open, reveal $x$; the receiver checks $x^e=y$ and recovers $b=c\oplus h(x,r)$. Injectivity makes the opening bit unique. The hard-core predicate theorem applied to $(x,r)\mapsto (x^e,r)$ gives computational hiding under the RSA inversion assumption. The setup must ensure a valid modulus and exponent without giving the receiver the private exponent; otherwise hiding fails. Merely encrypting $0$ or $1$ would not hide a bit, since both ciphertexts could be computed publicly.