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

• Published in: IEEE transactions on information forensics and security 2014-09, Vol.9 (9), p.1406-1415
• Main Author: Jiang, Shaoquan
• Format: Article
• Language: English
• Subjects: Binding; Channels; Codes; Communication channels; Computer information security; Entropy; Errors; Forensic engineering; Memoryless systems; Messages; Noise levels; Noise measurement; Protocols; Receivers; Security; Vectors
• ISSN: 1556-6013; 1556-6021
• DOI: 10.1109/TIFS.2014.2335113

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