A Discussion On Collusion-Resistant Protocols In Secret Sharing

One of the biggest problems faced by organizations in the cryptography era is securing sensitive data like private keys used for encryption and authentication. An individual’s private key is the gateway to their financial assets, so losing it or getting it stolen can be catastrophic. The current solutions control the access of private keys through sophisticated hardware storage devices or have multi-factor authentication systems to access them; and yet, private keys get hacked. The reason is simple: a single point of failure. A hacker just has to penetrate one location — either the hardware device or a web server, to get complete control of an individual’s life savings.

So have we accepted this eternal truth that one day some hacker in their “Dali” mask with a few lines of code can steal everything? The answer to this question was given by Yao [7] in the 1980s and further researched by Goldreich, Micali, and Wigderson through the introduction of Multi-Party Computation (MPC) [4][5].

MPC today has turned out to be a turning point in answering how private data should be stored on the internet.

For example, consider an organization that distributes a randomly selected private key to its users. Each time a user logs in to the central server of the organization, it looks up the corresponding public key and authenticates the user. The private key is either stored in the server or in some hardware device of the user, yet in both scenarios, it can be stolen.

MPC can play a significant role in hardening the server or the storage device of the user. In both cases, the private key can be sharded into multiple parts and can be stored on multiple servers or user drives. Now, the attacker has to compromise all the locations where the shares are stored to gain access to the complete key. Whenever a user logs in, he gets his shares from all of the locations to recompute it securely using MPC so that he can authenticate himself safely.

1.1 Core of MPC: Secret Sharing Scheme

In simple terms, MPC enables distributed parties to compute a cryptographic function without revealing private keys. As we saw in the above example the user’s authenticated themselves by bringing together the shares of their private key. Sharding the private key into several parts is one of the central concepts in multiparty computation and the concept of secret sharing achieves it.

Let us try to understand the concept of the secret-sharing scheme with an example.

Let us try to understand the concept of the secret-sharing scheme with the following example:
Imagine you discovered an ancient treasure vault in a cave. As you touch the vault, an oracle pops up and asks you to find all 100 pieces of the vault’s key to enjoy the treasure. Let’s say you found 99 pieces of the keys and tried to open the treasure vault — you are still destined to Fail! The 99 pieces are useless unless and until you find the last piece of the key.

The treasure vault may open with a magic spell after all 100 pieces are found but in cryptography, the magic spell is possible through the underlying mathematics of the secret-sharing scheme [8].

In addition, we do not require all the pieces of the secret-sharing scheme because there may be practical anomalies in some parties, eg: a node may be lost or shares of some parties may be corrupted.

Therefore, depending on the degree of anomaly, a secret-sharing scheme defines a threshold. For example, In (3,4) threshold secret-sharing schemes, the private key is distributed among 4 parties and any three of them can regenerate it. Further, parties less than the threshold can never regenerate the secret.

1.1.1 Shamir’s Secret Sharing

Shamir’s Secret Sharing [3][8] Scheme is a classic example of t-out-of-n threshold secret sharing. It utilizes the fact that for any t+1 points on a two-dimensional plane, it is possible to generate a curve f(x) having unique x values Refer to Figure 1. Furthermore, it is possible to reconstruct the polynomial f(x) using any t points from the curve using a mathematical technique called ‘Lagrange Interpolation’.

Let’s say a user wants to create (3, 4)-Shamir’s Secret sharing of his secret key “Privkey”. First, he generates a function f(x) with two coefficients: a1 and a2, and embeds their private key in the constant term of the function:

Now he generates solves f(x) for unique x values to get the shares in the form of points on the curve: (x1, y1), (x2, y2), (x3, y3), and (x4, y4). One fine day the user decides to regenerate his private key. He polls any 3 shares, plugs them into a Lagrange interpolation formula, and gets back his original function f(x). The user knows that the constant term of f(x) is the secret.

1.2 Collusion Problem in Secret Sharing Scheme

With Shamir’s Secret sharing in place, the user relaxes in their utopian world thinking he is immune to any hacking; after all, they have applied all the mathematical exercises, they thought no one uses after high school. Unfortunately, nothing outside utopia is perfect, and somehow sophisticated hackers always chance upon those imperfections and show us the futility of all our efforts.

This time, let’s assume the hackers somehow get control of the servers and engage in threshold secret sharing with the goal to get the private key. They silently play by the rules of Shamir’s Secret sharing but try to regenerate the private key without the user's knowledge. If the hackers are able to control the threshold number of key storage servers of the user, they can easily reconstruct the private key.

This particular loophole in secret-sharing schemes where the same parties are corrupt is called Collusion[6]. The corrupt parties are said to be involved in covert communication with each other to gain maximum benefits from a threshold secret-sharing scheme.

To understand the impact of collusion let’s look at the following real-life bidding scenario involving some corrupt parties:

1.2.1 Example: Collusion in Public Bidding

The Public Welfare Department in Westeros opened up a tender for their construction work. Several construction firms participated in the bidding. The tender was awarded to a well-known firm of Westeros — The Lannister Group at a much higher market price. During an investigation, it was revealed that the Lannister Group and fifty other construction firms participating in the bid, decided earlier on the result and purposefully bid a higher price. In return, the Lannister Group awarded secret payments to its competitors. The above example showcases collusion on behalf of the Lannister group and fifty other construction companies, causing the tender to be offered at an unnecessarily inflated price.

This type of scenario was rampant across Westeros so the Department of Expenditure decided to put forward some policies to combat it. Two solutions were presented:

• Formation of a trusted authorizing body: A trusted body can be formed that can act as a regulatory board to counter faked and inflated prices. The bid can be successful, if and only if, the trusted party approves it. This solution does not give away the entire control of bidding results to the bidders but rather shares them with an external trusted party that acts as a regulator.

• Trusting the Auctioneer and air-gapping the Bidders: In this case, the auctioneer (Public Welfare Department of Westeros in the above example) can restrict communication between the bidders. Any result of bidding would be communicated by the auctioneer (Refer to Figure 2) himself to each of the bidders. This can be successful, if and only if the auctioneer is not corrupt

In the secret sharing scheme, mathematics cannot distinguish between honest and dishonest secret reconstruction, much like the Public Welfare Department of Westeros was unable to identify price hype due to collusion between construction companies.

2. Collusion Avoidance Methods in Secret Sharing Scheme

If a group of participants can reconstruct the secret legitimately, then that same group of participants can reconstruct it maliciously. Therefore, we cannot guarantee that the protocol would prevent covert communication in a strict peer-to-peer environment. This implies that some trusted entity is required to monitor such covert communication. That entity could either be one of the parties participating in secret sharing or an external entity called the ‘dealer’.

With a trusted entity, there are two possible ways that collusion can be avoided:

• Access Control through Authority: A trusted party can be given higher authority/access. The idea is even though collusion occurs it wouldn’t affect the final result.
• Trusted Party as Mediator: A trusted party as a mediator, takes control of all the messages shared between the distributed parties. Here the goal is to restrict communication between parties such that they share valid messages through the mediator [2].

We further elaborate on how we can utilize a trusted authority to build access control and avoid collusion.

2.1 Collusion-Free Secret Sharing Protocol with Trusted Authority

This approach for collusion-free secret-sharing protocol is based on defining an access structure enforced by a Hierarchical secret-sharing scheme (HSS) [1]. In this scheme, other than the threshold, a factor or trust is assigned to each party that shares. Different parties have different trust levels represented by their ranks forming a hierarchy. The secret can be regenerated if and only if the highest-ranked participant (the most trusted of them all) is present.

2.1.1 Construction of Authority

Let’s understand how authority and access structure is constructed using hierarchy with the following example:

The Kargil War ended and the protocol “Grave” was activated which aimed to destroy all classified documents of war by the Defence Organisation. These documents were kept in a safe and are still highly protected. The document cannot be destroyed by the Chief of Defence alone, rather the protocol compulsorily requires the presence of the Head of Navy, Head of Army, and Head of Air Combat with their Admiral, General, and Marshal respectively.

‍

Figure 3 describes the hierarchy in the Defence Organisation with the Chief of Defence having the highest accessibility followed by the Head of Army, Navy, and Air combat. At the lowest level of the hierarchy are the Generals, Admirals, and Marshals of the Army, Navy, and Air combat respectively.

We want to ensure that out of 13 army officers assigned to the protocol “Grave”, at least 10 should be present, otherwise the protocol cannot be activated.

In addition to this, for any 10 of the present members the following rules are applied:

• The Chief of Defence must be present;
• Any 2 of the following heads: Head of Army, Head of Navy, and Head of Air Combat must be present;
• At least 2 members each from the General, Admiral, and Marshal must be present.

The protocol is activated if and only if these conditions are satisfied.

2.1.2 Hierarchy for Building Access Structure

Hierarchy can ensure that Protocol Grave is activated according to its defined rules. HSS takes care of the rules from 2 dimensions:

1. It can ensure that at least 10 members are present.
2. Rules at each level are enforced.

One way to implement the above rules is to have a secret code to the vault to be distributed among all members. It is important to note that the parts of the secret code cannot be equally distributed because each member belongs to a hierarchy level with designated access rights.

1. The “secret” is distributed to all the members of Protocol Grave. Figure 4 below, shows the sharing of a “secret code” among all the members of Grave according to HSS.

2. During the day of activation of Protocol Grave, at least 10 members can present their shares. The secrets shared are presented on the activation day by 10 members of Grave. Note that at each level the hierarchy is enforced (Refer to Figure 5).

3. The vault can open if and only if all the hierarchical rules are satisfied. Figure 6 shows the failure of the vault opening. Even though at least 10 members are present the secret code regeneration fails. The reason for the failure is the hierarchy rules are not satisfied. Note that the Chief of Defence is absent during the protocol activation day.

‍

The above example shows how the access structure is defined by utilizing ranks. The trusted authority — the Chief of Defence in the above example has a significant stake in regenerating the secret code. Even if covert communication happens without his participation no group members can collude to access the vault.

2.2 Hierarchical Secret Sharing Scheme

The Hierarchical Secret sharing scheme achieves a granular level of access policy by utilizing Birkhoff Interpolation [1]. The goal of Birkhoff Interpolation is to provide more data about the secret to the participants at the higher level and the lower ones, in the form of shares. Eventually, the presence of higher hierarchy shares is required to regenerate the secret.

This constructs a notion of authority in the higher-ranked participants. In this section we explain why shares of highest rank parties have the authority to avoid collusion:

1. All parties generate a function f(x) by providing random coefficients and random x values with a secret kept in the constant term of f(x).
2. Shares are generated for each party according to their ranks.
3. Trusted Party Shares: For the trusted party the x values are plugged into f(x) to evaluate y. The shares they receive are in the form (x, y)
4. For others, the f(x) is differentiated according to their rank. Suppose the rank of a party is 1 (trusted party is ranked 0), f(x) is differentiated once, and then x values are plugged in and y is evaluated from f(x).
5. During regeneration, all the shares are polled but without the presence of the shares from trusted authority protocol does not complete. To understand this, let’s assume we have 3 parties P1, P2, P3, and P1 is the trusted party with rank 0, and P2 and P3 have ranks 1 and threshold t=2.

The parties generate f(x) as follows:

The shares are generated as follows:

Shares for P1 : x=23, rank =0

Shares for P1 x=24 rank =1

Observe that the shares of P1 ( the trusted party) contain a secret entity, not P3 and P2. Hence without the presence of P1, it is impossible to regenerate the secret and complete the secret reconstruction.

3. Applications of Collusion Free Secret Sharing Protocols

1. Distributed storage of an owner’s private key: If a user wants to store their private key in a distributed manner with a collusion-free secret sharing protocol then they can act as a trusted authority with the highest rank. That means, without the user’s shares no other party can regenerate the private key.
2. Authorization with Vertical Access Structure: Hierarchical secret sharing can be used in large organizations structured among various groups vertically. This scheme can ensure fairness while authorizing access among the organization.

References

1. Tassa, T. Hierarchical Threshold Secret Sharing. J Cryptology 20, 237–264 (2007). https://doi.org/10.1007/s00145-006-0334-8
2. Alwen, J., Katz, J., Lindell, Y., Persiano, G., Visconti, I. (2009, August). Collusion-free multi- party computation in the mediated model. In Annual International Cryptology Conference (pp. 524–540). Springer, Berlin, Heidelberg, https://crypto.ethz.ch/publications/AKLPSV09.html.
3. Shamir, A. (1979). How to share a secret. Communications of the ACM, 22(11), 612–613, https://web.mit.edu/6.857/OldStuff/Fall03/ref/Shamir-HowToShareASecret.pdf.
4. Lindell, Y. (2020). Secure multiparty computation (MPC). Cryptology ePrint Archive, https://eprint.iacr.org/2020/300.
5. A beginner’s guide to Secure Multiparty Computation, https://medium.com/@keylesstech/a-beginners-guide-to-secure-multiparty-computation-dc3fb9365458
6. Zhang, X., & He, M. (2010, April). Collusion attack resistance and practice-oriented threshold changeable secret sharing schemes. In 2010 24th IEEE International Conference on Advanced Information Networking and Applications (pp. 745–752). IEEE, https://ieeexplore.ieee.org/document/5474795.
7. Lecture on Yao’s protocol https://people.eecs.berkeley.edu/~sanjamg/classes/cs294-spring16/scribes/1.pdf
8. Lecture on Secret Sharing https://www.cs.purdue.edu/homes/hmaji/teaching/Fall%202020/lectures/08.pdf

‍