Quorum-based encryption

Question

The task

Encrypt data in a way that a freely choosable quorum of n people out of a group of m participants are required to decrypt that data.

It is not necessary to have to fulfil the quorum to encrypt data.

What crypto systems and algorithms exist that solve this task?

Example: A poor solution that does the trick

A method that seems obvious but scales poorly, is to create a separate ciphertext for each permutation of n people, creating m keys and encrypting each plaintext-copy n times with n different keys.

m = 4, n = 3

ciphertext1 = m( m( m( plain, keyA ), keyB ), keyC )  
ciphertext2 = m( m( m( plain, keyA ), keyB ), keyD )   
ciphertext3 = m( m( m( plain, keyA ), keyC ), keyD )
ciphertext4 = m( m( m( plain, keyB ), keyC ), keyD )

Downsides:

• This requires a single point of trust. Whereever the plaintext is encrypted, all keys have to be known as well.
• It does not scale. The effort in storing and distributing keys and ciphertext is very high. Furthermore the encryption function needs to be called m*n times

A slightly better variant would use the scheme above and instead of encrypting the payload, an encryption key that works on actual data would be encrypted instead. This removes the need to perform the encryption operation on the payload multiple times and to store multiple copies of the encrypted payload.

Answer 1

This sounds exactly like secret-sharing. Briefly, you can secret share a secret key $sk$ in a k-out-of n fashion where the corresponding public key $pk$ is known by everyone.

Then, everyone can encrypt a message $m$ to a ciphertext $c$ using the public key yet, only a quorum of size $k$ can decrypt $c$.

In particular, this kind of secret sharing can be done without any central party by running a distributed key generation algorithm (DKG) among participants.