Petar Popovski, Editor in Chief of IEEE JSAC
Published: 2 May 2022
The March 2022 issue of IEEE JSAC is dedicated to “Privacy in Retrieval, Computing, and Learning”. It brings different perspectives on the problems of privacy and security, topics that have received an increasing attention within the communication theory community within the past few years. The paper featured in this blog is co-authored by researchers coming from two IITs (Indian Institute of Technology), Kharagpur and Patna, respectively:
A. J. Budkuley, P. Joshi, M. Mamindlapally and A. K. Yadav, "On Reverse Elastic Channels and the Asymmetry of Commitment Capacity Under Channel Elasticity," in _ IEEE Journal on Selected Areas in Communications, vol. 40, no. 3, pp. 862-870, March 2022, doi: 10.1109/JSAC.2022.3142304.
The article deals with the problem of a two-step commitment protocol. In this protocol, Alice is a committer, that is, a party that wants to commit to a certain digital value. This value can be, for example, a bidding price in auction or a result of a rock-paper-scissors move. In the first step of the commitment protocol, the committer Alice sends this value to the receiver Bob, but in a way that the value remains hidden for Bob until the second step of the protocol is executed, in which Alice reveals the previously committed value to Bob. However, even if Bob does not know the value, Alice should stay committed to this value and cannot change it again prior to the moment when the value will be revealed. Think of this as the case in which Alice sends a sealed envelope to Bob; Bob does not know the value in the envelope, but Alice cannot change it after the envelope is delivered.
If there is only noiseless channel from Alice to Bob, then it is impossible to solve the commitment problem in a manner that is secure in an information-theoretic sense. If, though, there is a noisy channel, such as Binary Symmetric Channel (BSC) from Alice to Bob, then the uncertainty introduced by this channel can be used to both to conceal the value from Bob in the first step, as well as to prevent Alice to cheat in the second step. For an intuitive description of the problem for committing the value of a single bit and the solution over a BSC, check this explanation by Claude Crépeau. The main idea is that, after Alice sends a codeword in the first step, then the noisy channel distorts this codeword such that Bob has multiple candidate codewords that could have been sent. Ideally, half of these candidate codewords indicate that the committed bit is 0, and half of them that the committed bit is 1. In the second step Alice uses a noiseless channel (or a different code over the noisy channel) to send the exact codeword she sent in the first step. The key is that Alice does not know the set of candidate codewords at Bob’s side, such that if she sends a codeword that is different from the one in step 1, Bob will detect this with a very high probability.
A central role in the design of these schemes is played by the crossover probability p of the BSC, as the choice of the codebook and the uncertainty induced to Alice and Bob is determined by this probability. But what if either Alice or Bob can control this probability p? If the receiver Bob can control the probability, then we have the case of Elastic Channel. Otherwise, if the committer Alice can control this probability, this is the case of Reverse Elastic Channel, which has been studied in this paper. The paper proves a recent conjecture and shows that the case in which the committer controls the parameters of the noisy communication channel can have a more detrimental impact on the commitment performance compared to the case in which the receiver is able to control these parameters in a similar manner.
In the sequel we provide some further reflections by the authors on their article.
JSAC: You provide a motivating example in the introduction, but could you contextualize it to more practical applications?
Authors: The motivating example in our paper was inspired from the main challenge most of us faced at the time this manuscript was submitted, viz., social distancing. However, commitment is a key primitive in any secure multiparty computation protocol as it essentially constrains parties to behave honestly during the protocol-execution. A sealed-bid auction is a classic application that is widely used to motivate commitment. Any sealed-bid auction among multiple bidding parties and an auctioneer comprises of the two following phases: the bidding phase where competing bidders commit to bids and share concealed bid values with the auctioneer. After receiving all bids, the auctioneer proceeds to the opening phase where the auctioneer reveals all bids publicly and identifies the winning bidder. A bidder seeks to keep the contents of their bid hidden from the auctioneer and other competitors until all bids are simultaneously made public. The auctioneer, on the other hand, seeks to receive bids in a tamper-proof manner thereby “binding” bidders to their original submitted bids. In effect, all parties seek commitment on the presented bid values. Other modern digital technologies like blockchains, cryptocurrencies, etc., also offer an exciting avenue to leverage the power of commitments.
JSAC: What do you think is the weak point of your approach?
Authors: Our principal goal in this work was to study the fundamental limits on the commitment throughout over reverse elastic channels (RECs). As in most such works attempting to understand fundamental performance limits, our “existence” result is based on the construction of a “capacity-achieving” commitment protocols which is not “efficient” in a practical sense; this comes across as a weakness in our current approach. It would be interesting to explore other approaches which construct commitment protocols that are practically implementable, even possibly at some reasonable rate penalty with respect to the optimal throughput (there is already some interesting work in the cryptography community for realizing positive rate commitment schemes).
JSAC: What has been criticized by the reviewers during the review process and how did you address that?
Authors: The reviewers’ comments were generally positive. We benefitted greatly from some excellent suggestions on writing and presentation as those helped improve the overall quality of our manuscript. We would like to discuss one such comment. One of the anonymous reviewers pointed out that our results would hold true in a more general setting when a dishonest committer was allowed to change the reverse elastic channel (REC) adaptively, i.e., in a time-varying manner, across separate uses of the REC (within the allowed elastic range). The model, as specified in that version of our manuscript, did not allow this explicitly. Interestingly, however, our proof was already analysing a potentially adaptive adversary as was pointed out by the reviewer. In our final manuscript, after deliberating extensively, we decided to still go ahead with the original static (instead of an adaptive) adversary in order to establish a direct parallel with the classic REC model as defined in several prior works. However, we made it a point to emphasize clearly and prominently that a more general adversary model would still not degrade the commitment throughput. This was an instance of an excellent suggestion we received during the review process.
Statements and opinions given in a work published by the IEEE or the IEEE Communications Society are the expressions of the author(s). Responsibility for the content of published articles rests upon the authors(s), not IEEE nor the IEEE Communications Society.