# Require x of y possible passwords to decrypt

Is there a way to set up encryption so that a certian number (x) out of a total (y) number of users/passwords are required to do the decryption?

Background: This is mostly a thought experiment, and I don't have a realisitic real world application for it, although they may exist. I recall first getting the idea from an interview with Edward Snowden (Neil deGrasse Tysons podcast I beleive), but cannot find any follow information about the concept.

Hypothetical example 1: There are 3 "leaders" to a finctional technologically country. In order to start a war, 2 of them must agree and provide their crypto keys to decrypt the required commands/codes.

Hypotheical example 2: There are 435 congressmen in the USA. Sometime in the future, bills must be passed using cryptographic methods. 50% of them must provide their key/password in order to get the master key and pass a law.

Trivial Solution: For each combination users, encrypt the master decryption key in order (alphabetical by username). For the first example, there are only 3 combinations, and it is trivial to just encrypt the master key 3 different ways. Unfortunately this does not scale well. For the second example, 218 out of 435 gives us ~3*10^129. (For reference, there are 10^80 atoms in the universe.)

Is their a more programatic way to perform this type of encryption? The more I learn about crypto, the more I see amazing applications for reletively straightforward mathematical algorithms.

• The case where everybody learns the secret afterwards is called secret sharing and the case where everybody just learns the (valid) result is called multi-party computation, but I can't comment what exactly is possible and feasible with regards to your question there. – SEJPM Dec 19 '16 at 23:32

This is a well studied problem in cryptography; what you're looking for is known as a Secret Sharing Scheme. This is a scheme where we take a master secret, and from that generate $N$ shares, and with any collection of $T$ shares, we can reconstruct the master secret (and we can't with $T-1$ of them). We can make $N$ and $T$ as large as we like, and so it works in the "any 218 out of 435" case.

See this article for more details, as well as pointers to practical ways to implement it.

A bitcoin style block chain may provide a solution here. If every vote is signed with the a 'trusted' private key and added to the chain that is in turn hashed with the previous block it may be able to provide an immutable ledger of cast votes. Especially if such a chain were run for a long time over many different decision making processes for example all bills passed in the Senate or Parliament.

Bitcoin solves everything it seems these days.

This sort of thing can be and is done in practice. One open-source example is that Hashicorp Vault, a secret management tool for software systems, has an "unseal" procedure that requires some threshold number of parties to present their shares of the master key that it uses for encrypting the secrets it manages. This uses the same sort of secret sharing mechanisms that other responses and comments have mentioned.

Vault also adds another practical trick to this, which is that at the time that a master key is generated and split into shares, it supports encrypting the key shares using the shareholders' PGP public keys, so that the master key's shares' plaintext values are never written to the terminal, network or disk. This means that the person who runs the command to generate a new master key doesn't get to see the master key shares themselves, only their encryptions with key pairs they don't control. Since PGP private keys are normally password protected, this actually ends up working in a way similar to what you ask—the master key can only be reconstructed through a process where a threshold number of participants enter their passwords.

To unseal the Vault, a threshold number of participants must decrypt their own key share, and submit it to the Vault server's API endpoint, which they can do independently each on their own computer if they so choose.