(Im)possibility of Deterministic Commitment Over a Discrete Memoryless Channel

In this paper, we study the commitment over a discrete memoryless channel W : X → Y, where both a sender and a receiver are deterministic. We call it (δ_h, δ_b)-secure if it has a hiding error δ_h and binding error δ_b. For any c ∈ (0, log |X|) and any σ ∈ (0, c), we propose a framework for a message domain of size 2^n(c-σ) such that any δ_h > min_PX:H(X)=c(I(X; Y)/H(X) - c) with an exponentially (in n) small δ_b can be achieved, where Y is the output of W with input X and n is the number of channel uses. We show that lim_c→0 min_PX:H(X)=c(I(X; Y)/H(X)) = 0 if and only if a very weak condition on W holds. Note that when lim_c→0 min_PX:H(X)=c(I(X; Y)/H(X)) = 0, we are guaranteed that our framework can commit to a message from a domain of size approximately 2^nc for small c with a nearly zero hiding error δ_h and an exponentially small binding error δ_b. The price for this is a small commitment rate. We obtain some impossibility results for (δ_b, δ_h). For the space M of the commitment input, we show that when |M| = O(1), then (z, o(1))-security is impossible for any z <; 1; when |M| = ω(1), then δ_h <; min{α/γ, 1} and δ_b = 2^-nα is impossible where γ = lim sup_n→∞(log |M|/n) and α > 0.