Collaborators: Prof. Amitalok J. Budkuley (supervisor), Prof. Manoj Mishra, Manideep Mamindlapally, and Pranav Joshi

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, 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 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 which are based on computational assumptions on the users participating in the protocol. Crepeau et.al designed unconditionally secure or the 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 costs constraints and cahracterized it primal and dual capacity expression. Further, we have also been exploring commitment over unreliable channels. Unreliability comes in two forms viz., paasive 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 characterstics covertly, without the other party knowing about the same, in order 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 protcol in multiparty computations, e-votings, etc. To better understand oblivious transfer, consider the following scenario: Eve is a employee who works in Alice's (employer) company. Bob is a detective (investigator) who suspects Eve of committing a crime. In order to carry out his investigation, he reaches out to Alice in order to gather information (data) about Eve's background. However, Bob want to be assured that Alice's doesn't gets 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 for, not someone else's data in order to maintain privacy.

So, can this kind of functionality be acheived or implemented? The answer to this questions 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 it 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 rate that achieves this upper bound. Furthermore, we are also currently exploring OT over adversarial channels (AVCs).

Collaborators: Prof. Sidharth Jaggi (supervisor), Dr. Yihan Zhang, and Prof. Amitalok J. Budkuley

Our work focuses on bridging this gap between the two extremes of information theory and coding theory via the mathematical abstraction of Arbitrarily Varying Channels (AVCs). It involves exploring fundamental performance limits as well as (im) possibility results, and desiging 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 in order to disrupt the communication between the legitimate parties.

In our work, we are studying reliable communication in the most general scenario of a jammer modelled 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 acheivable performance limits. We show that the communication over an omniscient AVC is possible iff it satisfies the “non-symmetrizablility” condition. We have deisnged a cloud-code construction (inspired by satellite codes in broadcast channels) which achieves a large positive rate using a two-step decoder at the receiver. Furthermore, we have also dereived sufficient conditions for omniscient AVCs under which simpler decoding rules such as jointy-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 comparitively weaker than that in the case of omniscient AVCs, and therefore, observes the noisy version of the transmitted codeword.

Collaborators: Prof. Laura Luzzi (supervisor), and Prof. Ligong Wang

Covert communication or communication with low probability of detection or reliable-deniable communication is a exchange of messages between two or more users in a secret manner such that a third-party or adversary doesn't even gets 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 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 in communication have shown that the covert communication over different class 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 holds. 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 of realizing covert communication over binary AWGN channel using Reed Muller codes. We are currently working on to show 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]