Overview
Imminent advent of efficient quantum computers motivates us to rigorously discuss upon efficient quantum-safe cryptographic primitives, whose security is believed to hold even under cryptanalytic attack by a quantum computer. Classical hard mathematical problems like integer factorization, discrete logarithm have been proven not to be quantum-safe due to several quantum algorithms. But various post-quantum secure cryptographic research fields have already emerged, e.g., lattice-based cryptography, code-based cryptography, multivariate cryptography, isogeny-based cryptography. Among them, I have concentrated on lattice-based cryptography. More specifically, I am working around LWE (Learning with Errors) and LWR (Learning with Rounding) assumptions.
Generally, any cryptosystem relies on secure storage of some key. If the key is stored on a single device/server, it leads to a single point of vulnerability. Hence it is always better to let the key remain always split over multiple devices/parties. Now while performing a particular cryptographic operation requiring that key, if only threshold number of devices are sufficient to collaborate with their respective key shares, we call the cryptographic operation to be thresholdized. Its security guarantees that a PPT adversary even with the knowledge of key shares of less than threshold number of parties, can not gain any information about the actual secret.
With the two contexts defined above, my research focuses on "Design and Analysis of Advanced Quantum-safe Cryptographic Primitives".
Threshold FHE:
The advent of cloud computing potentially allows individuals and organizations to outsource storage and processing of large volumes of data to third party servers. However, this leads to privacy concerns - clients typically do not trust service providers to respect the confidentiality of their data. This lack of trust is fortified by threats from malicious insiders and external attackers. A simple and efficient solution for ensuring the privacy of user information is to encrypt the user data before offloading it to the cloud. However, if the data is encrypted using some conventional encryption algorithm (for instance, using the Advanced Encryption Standard a.k.a. AES block cipher), then the cloud loses all ability to compute on the data without decrypting it first. Fully Homomorphic Encryption comes as a solution, which allows evaluation of complex programs on encrypted data, without the need to access any decryption key. The security of most existing FHE proposals crucially relies on secure storage of the decryption key. However, assuming that a single device/server is responsible for secure storage results in a single point of failure, which is undesirable. Hence we proceed towards Threshold Fully Homomorphic Encryption, which enables arbitrary computation on encrypted data, while keeping the decryption key split across several (say, T) computing entities, and a threshold (say, t) number of entities are needed to come together with their respective key shares so as to make the decryption possible. We call it t-out-of-T threshold decryption. A few existing proposals for Threshold FHE suffer from huge overheads in terms of communication, storage and encryption/decryption performance. They also lack in concrete efficiency analysis. Hence our focus is on designing an efficient Threshold FHE scheme.
Threshold PRF:
Pseudo Random Function (PRF) is a deterministic keyed function that, given an input, outputs a value in polynomial time such that the output is indistinguishable from the output of a truly random function. Here, ‘indistinguishability’ means the inability of an adversary having no knowledge about the key to tell whether an output is from a pseudo random function or from a truly random function, even after seeing polynomially many pseudo random function outputs for inputs of its choice. Threshold PRF allows the key to remain distributed among multiple servers (parties) instead of being stored on a single server, and a threshold number of servers are able to evaluate the PRF by collaboration with their respective secret shares. Thus threshold PRF enables us to avoid the single point of vulnerability. Pseudo Random Function is an important cryptographic primitive, having numerous applications in today’s world. However, to the best of our knowledge the construction of a simple but practically efficient post-quantum secure threshold PRF scheme remains an open question. In this work, we provide such a construction and also prove its security in semi-honest adversarial settings based on the hardness assumption of LWR problem. For more details, please refer to the paper here.
Adaptively Secure Threshold PRF:
This work focuses on the adaptive security of efficient quantum-safe distributed PRF. Adaptively secure PRF remains secure even when an adversary is allowed to dynamically choose the parties to corrupt instead of declaring the corrupt set of parties at the beginning.
Other works:
We are also exploring other possible threshold cryptosystems based on several other hardness assumptions apart from lattice-based cryptography.
Supervisor: Dr. Debdeep Mukhopadhyay