Multi-party computation (MPC) is a key topic of discussion when it comes to data privacy, particularly in sensitive applications such as analysing financial transactions or conducting medical data analysis. As one of the Privacy Enhancing Technologies, MPC is a cryptographic technique that allows multiple parties to collaboratively compute a function on their private input data without disclosing the input data itself. At the heart of many MPC implementations (not all) lies a technique known as Shamir's secret sharing. This powerful primitive allows data to be split into multiple encoded parts called ‘secret shares’, which on their own reveal nothing about the original data. However, when two parties perform the same operation on a set of shares and then recombine them, it's as if that operation was performed on the original data itself. In this post, we'll delve into the fascinating world of Shamir's Secret Sharing and its vital role in respective MPC implementations.
Before delving into the realm of perfect secrecy, it's helpful to understand the foundation laid by simpler encryption techniques like Caesar's cipher. This substitution cipher involves replacing each letter in the plaintext with a letter some fixed number of positions down the alphabet (for example, if the shift was 7,
a --> h). While Caesar's cipher offers a basic level of encryption, it's relatively easy to crack through brute force, as the number of possible combinations is limited to the length of the alphabet (26). This indicates the need for a more robust method when tackling the unique challenges of data security in the world today.
The above shows how Caesar’s cipher shifts each character in the message.
Credit: Wikipedia
The complexities of keeping secrets secure in today's interconnected world demand a higher level of protection than what Caesar's cipher can offer. Consider, for instance, the need to share sensitive information among multiple parties without granting any single party complete access to it. The traditional approach of splitting the secret into pieces and sharing it among the parties (i.e., splitting an 8-digit key into 2 pieces of 4 digits) falls short – each piece could potentially reveal partial information about the secret, making it easier for someone to guess the key.
We can effectively address this challenge with a perfectly secret system where every possible key appears equally likely, ensuring that someone with one share is no more likely to guess the key than someone without a share. It is in this pursuit of perfect secrecy that we uncover more sophisticated cryptographic techniques capable of meeting the demands we require.
The concept of perfect secrecy comes alive with a technique known as the one-time pad, proven by Claude Shannon to be perfectly secret in 1949. In this method, each letter of a message is shifted by a different random number between 1 and 26, resulting in a mind-boggling number of possible combinations (26^n - as opposed to the whole message being shifted by a single number between 1 and 26). This makes it virtually impossible for a person with only one share to guess the key any more easily than someone without a share (perfect secrecy). However, to be able to replicate the most desired functionality using MPC, we need to be able to support secure multiplication operations – which is not practical with the one-time pad.
The illustration above shows that to share the secret ‘privacy’, each letter would be shifted by a random number between 1-26. One party would receive the random shifts, and the other would receive the random secret. They can only uncover the random message by combining both of
their information.
To address the drawbacks of the one-time pad, Adi Shamir introduced a game-changing solution in 1979. He devised an algorithm that shared a secret among multiple parties using the concept of geometric secret sharing. The secret was represented as a point in space, while the shares were considered points along a secret random curve. This method allowed the secret to be shared among as many parties as needed (n), with a minimum number of parties (k) required to recover the secret, known as a k-n scheme (threshold-based). This approach allows for more flexible and practical sharing of secrets among multiple parties, and it can support secure multiplication operations.
Shamir's Secret Sharing involves creating a polynomial with a degree of k-1 (in the example below k is 3 which is why this is of degree 2), where k is the minimum number of shares needed to recover the secret. The secret (302) is hidden as the constant term of the polynomial, while other coefficients are chosen randomly. Shares are generated by evaluating the polynomial at different points. To recover the secret, any k shares can be used to interpolate the polynomial, and the constant term is the secret.
Firstly, while Shamir's Secret Sharing is a powerful and widely used primitive in many MPC implementations, it's important to note that it's not a fundamental component in all flavors of multi-party computation. By using Shamir's Secret Sharing to distribute shares of the input data, privacy can be ensured in even the most sensitive applications.
Imagine a group of medical researchers who want to analyze patient data from multiple hospitals without exposing individual patient information. By employing multi-party computation powered by Shamir's Secret Sharing, these researchers can work on the shared data, perform analyses, and draw conclusions without ever having access to the actual patient records. This ensures patient privacy while still allowing for valuable research to be conducted, to continuously improve health outcomes.
Similarly, in the realm of financial transactions, multi-party computation enables secure processing of financial transactions without revealing customer information. Banks can work together to improve the predictive power of models for Anti-Money Laundering alerts (which would save a considerable amount of money, given that 95% of these alerts turn out to be false positives - Reuters).
Shamir's Secret Sharing is an incredible cryptographic achievement that has revolutionized the data privacy space as we know it. As we continue to navigate the digital age and face an increasing wave of privacy regulations, understanding the intricacies of cryptographic algorithms like Shamir's Secret Sharing will be essential in unlocking the full potential of privacy-preserving computation.