Bit Commitment is a widely studied cryptographic primitive with multitudinous applications in secure Multiparty Computation (MPC), blockchains, zero-knowledge proofs, sealed-bid auctions, etc. Consider two siblings, Alice and Bob, who are playing a game of chess. However, it’s late at night so they decide to adjourn the game and continue in the morning. But, there’s a problem! Who makes the last turn? If it is Alice, Bob has the entire night to think about his turn until the next morning, leading to an unfair advantage; similar is the case if Bob makes the last turn.

A possible solution to this problem is that both of them can reach out to their mom and say, that Alice covertly reveals her move to mom that she is going to make the next morning. The next day, when they continue the game, Alice is bound to make the same move as Bob can verify it by asking Mom. Therefore, it ensures fair play in the game in the presence of mom - “a third party”. However, in a real-world scenario, the third party might not be available or its availability might be costlier. Therefore, can we achieve this kind of functionality without a third party?

The answer to this question lies in the Commitment Protocol, which was introduced by [Blum] as a computationally secure model that is based on computational assumptions on the users participating in the protocol. Crepeau et.al designed unconditionally secure or information-theoretically secure commitment protocols with the use of noisy channels. Such unconditionally secure commitment protocols are simply unbreakable even if the adversaries have infinite computing power and time.

Specifically, we have studied Commitment over Discrete Memoryless Channels (DMCs) under input cost constraints and characterized its primal and dual capacity expression. Further, we have also been exploring commitment over unreliable channels. Unreliability comes in two forms viz., passive unreliability and active unreliability. The passively unreliable channel models are often poorly characterized such that the exact channel characteristics remain obscure to both the parties taking part in the commitment protocol. These channels are studied in information theory through the lens of compound channels and arbitrarily varying channels. Further, a stronger form of unreliability (“active” unreliability) comes into the picture if either of the two parties knows the exact channel behavior and can control the channel characteristics covertly, without the other party knowing about the same, to gain unfair advantage/information. Such channel models include Unfair Noisy channels (UNCs), Elastic Channels (ECs), and Reverse Elastic Channels (RECs). In particular, we have explored the commitment capacity of constrained DMCs, compound channels, and reverse elastic channels, which involves deriving a robust upper bound (converse) and designing computationally efficient and capacity-achieving commitment schemes. Our current work focuses on unifying all such channel models into a single frame of an unreliable channel model for studying commitment which can reduce to different channels (compound, ECs, RECs, UNCs) under different conditions .

Example courtesy: [Winter et. al]
References: [Crepeau's webpage]

Bachelor's Thesis Project

Oblivious Transfer (OT) is another interesting cryptographic protocol (closely related to Private Information Retrieval (PIR)) commonly implemented as a sub-protocol in multiparty computations, e-votings, etc. To better understand oblivious transfer, consider the following scenario: Eve is an employee who works in Alice's (employer) company. Bob is a detective (investigator) who suspects Eve of committing a crime. To carry out his investigation, he reaches out to Alice to gather information (data) about Eve's background. However, Bob wants to be assured that Alice doesn't get to know whose data is he seeking because if Alice does, it can jeopardize Eve's job in Alice's company if he later turns out to be innocent. Synchronously, Alice wants to be assured that Bob should “only” receive information/data of the employee that he seeks, not someone else's data to maintain privacy.

So, can this kind of functionality be achieved or implemented? The answer to this question takes us to Oblivious Transfer (OT) protocol!!

OT is an oblivious exchange of messages between two users. Similar to the commitment problem, our work is concentrated on implementing/realizing “unconditionally secure (information-theoretically secure)” oblivious transfer over noisy channels.

Specifically, we are studying OT over the class of unreliable channels. Currently, we are studying (im)possibility results and fundamental performance limits of OT over compound discrete memoryless channels and its sub-class of compound binary erasure channels (C-BEC). The OT capacity characterization involves providing a robust converse (upper bound) for OT rate and designing a computationally efficient OT scheme with a rate that achieves this upper bound. Furthermore, we are also currently exploring OT over adversarial channels (AVCs).

Our work focuses on bridging this gap between the two extremes of information theory and coding theory via the mathematical abstraction of arbitrary varying Channels (AVCs). It involves exploring fundamental performance limits as well as (im) possibility results and designing robust and optimal information processing schemes under malicious interference. Unlike the stochastic noise channels (such as discrete memoryless channels) as studied by Shannon, Arbitrarily Varying Channel models involve a potentially malicious third party a.k.a jammer who inflicts jamming noise “carefully” into the channel based on his observations or capabilities to disrupt the communication between the legitimate parties.

In our work, we are studying reliable communication in the most general scenario of a jammer modeled via omniscient arbitrarily varying channels (omniscient AVCs). The jammer in such channel models is omniscient to the sender's message, codebook, transmitted codeword, and the channel law and inflicts jamming sequence (noise) into the channel based on these observations. Our goal so far has been to explore the (im) possibility results for communication over such channels and to study fundamental and achievable performance limits. We show that the communication over an omniscient AVC is possible iff it satisfies the “non-symmetrizablility” condition. We have designed a cloud-code construction (inspired by satellite codes in broadcast channels) that achieves a large positive rate using a two-step decoder at the receiver. Furthermore, we have also derived sufficient conditions for omniscient AVCs under which simpler decoding rules such as jointly-typicality decoding, MMI decoding, etc. suffice and the code achieves the same positive rate as that by using a two-step decoder.

Currently, we are also studying communication over the class of “myopic” AVCs in which the jammer is comparatively weaker than that in the case of omniscient AVCs, and therefore, observes the noisy version of the transmitted codeword.

Covert communication or communication with a low probability of detection or reliable-deniable communication is an exchange of messages between two or more users in a secret manner such that a third party or adversary doesn't even get to know if the parties are communicating with each other. To understand the problem, let's consider the following hypothetical example: Alice and Bob are criminals who are in jail but with in different cells and want to exchange messages with each other such that the jailor of the jail (Eve) remains unknown of the fact that Alice and Bob are talking to each other.

Noisy channels can be used as a significant resource for implementing covert communication. Mathematically, the goals in covert communication are as follows:
1). Reliability: The receiver, Bob should be able to decode the message with low error probability (decreasing in blockength n).
2). Deniability (Covertness): The adversary, Eve's observation should be statistically close (eg. small KL divergence) to random noise (output distribution induced when the transmitter is not sending any message, i.e., off-input symbol, say 0 is transmitted).

Several works have shown that covert communication over the different classes of channels including discrete memoryless channels (DMCs), as well as the additive white Gaussian noise (AWGN) channels, follows the square-root law i.e., the number of information nats that can be transmitted covertly (k) over the channel grows proportionally to the square root of the total number of channel uses (n). In such transmissions, both the conditions i.e., reliability as well as deniability hold. It has been recently shown that the Reed-Muller codes achieve capacity over any BMS (binary memoryless symmetric) channel in [RP21]. In our work, we focus on realizing covert communication over binary AWGN channels using Reed-Muller codes. We are currently working on showing that using reed muller codes, both the conditions for the covert communication i.e., reliability and covertness can be achieved over a BI-AWGN channel such that the square-root law holds.

Example courtesy: [Prof. Sid's talk]