GENERAL ACCESS STRUCTURE SECRET SHARING USING AUTHENTIC GARBLED CIRCUITS

1 . A method comprising:

defining, by a computer system acting as a dealer in a general access structure secret sharing (GAS-SS) scheme, an access structure for sharing a secret among N receivers, wherein the access structure identifies one or more qualified sets of the N receivers that are authorized to reveal the secret;

creating, by the computer system, a Boolean circuit that represents the access structure, wherein the Boolean circuit takes as input N input bit values corresponding to the N receivers, each input bit value having a value of zero if its corresponding receiver does not wish to reveal the secret during a reconstruction phase of the GAS-SS scheme and a value of one if its corresponding receiver wishes to reveal the secret during the reconstruction phase, and wherein the Boolean circuit generates an output bit value of zero if a subset of the N receivers that wish to reveal the secret as indicated by the N input bit values is not a qualified set and generates an output bit value of one if the subset of the N receivers that wish to reveal the secret as indicated by the N input bit values is a qualified set;

executing, by the computer system, a garble algorithm of an authentic garbled circuit protocol on the Boolean circuit, the executing of the garble algorithm resulting in a garbled circuit and encoding information specifying N label pairs corresponding to the N receivers;

encrypting, by the computer system, the secret using a garbled output Y 1 , the encrypting resulting in a ciphertext; and

sending, by the computer system to each receiver in the N receivers, the garbled circuit, the ciphertext, and a label pair for the receiver as specified in the encoding information.

2 . The method of claim 1 wherein the garbled output Y 1 is generated by an evaluate algorithm of the authentic garbled circuit protocol in a scenario where the evaluate algorithm receives as input the garbled circuit and a garbled input encoding a set of N input bit values corresponding to a qualified set of the N receivers.

3 . The method of claim 1 wherein the label pair for the receiver includes a zero label representing an input bit value of zero for the receiver and a one label representing an input bit value of one for the receiver.

4 . The method of claim 3 wherein upon receiving the garbled circuit, the ciphertext, and the label pair, each receiver:

informs other receivers in the N receivers whether the receiver wishes to reveal the secret or not.

5 . The method of claim 4 wherein each receiver informs the other receivers by:

sending to the other receivers the receiver's one label if the receiver wishes to reveal the secret; and

sending to the other receivers the receiver's zero label of the receiver does not wish to reveal the secret.

6 . The method of claim 4 wherein each receiver further:

compiles a garbled input based on labels received from the other receivers; and

executes a evaluate algorithm of the authentic garbled circuit protocol on the garbled circuit and the garbled input, the executing of the evaluate algorithm resulting in a garbled output Y.

7 . The method of claim 6 wherein each receiver further:

attempts to decrypt the ciphertext using the garbled output Y as a decryption key.

8 . A non-transitory computer readable storage medium having stored thereon program code executable by a computer system acting as a dealer in a general access structure secret sharing (GAS-SS) scheme, the program code embodying a method comprising:

defining an access structure for sharing a secret among N receivers, wherein the access structure identifies one or more qualified sets of the N receivers that are authorized to reveal the secret;

creating a Boolean circuit that represents the access structure, wherein the Boolean circuit takes as input N input bit values corresponding to the N receivers, each input bit value having a value of zero if its corresponding receiver does not wish to reveal the secret during a reconstruction phase of the GAS-SS scheme and a value of one if its corresponding receiver wishes to reveal the secret during the reconstruction phase, and wherein the Boolean circuit generates an output bit value of zero if a subset of the N receivers that wish to reveal the secret as indicated by the N input bit values is not a qualified set and generates an output bit value of one if the subset of the N receivers that wish to reveal the secret as indicated by the N input bit values is a qualified set;

executing a garble algorithm of an authentic garbled circuit protocol on the Boolean circuit, the executing of the garble algorithm resulting in a garbled circuit and encoding information specifying N label pairs corresponding to the N receivers;

encrypting the secret using a garbled output Y 1 , the encrypting resulting in a ciphertext; and

sending, to each receiver in the N receivers, the garbled circuit, the ciphertext, and a label pair for the receiver as specified in the encoding information.

9 . The non-transitory computer readable storage medium of claim 8 wherein the garbled output Y 1 is generated by an evaluate algorithm of the authentic garbled circuit protocol in a scenario where the evaluate algorithm receives as input the garbled circuit and a garbled input encoding a set of N input bit values corresponding to a qualified set of the N receivers.

10 . The non-transitory computer readable storage medium of claim 8 wherein the label pair for the receiver includes a zero label representing an input bit value of zero for the receiver and a one label representing an input bit value of one for the receiver.

11 . The non-transitory computer readable storage medium of claim 10 wherein upon receiving the garbled circuit, the ciphertext, and the label pair, each receiver:

informs other receivers in the N receivers whether the receiver wishes to reveal the secret or not.

12 . The non-transitory computer readable storage medium of claim 11 wherein each receiver informs the other receivers by:

sending to the other receivers the receiver's one label if the receiver wishes to reveal the secret; and

sending to the other receivers the receiver's zero label of the receiver does not wish to reveal the secret.

13 . The non-transitory computer readable storage medium of claim 11 wherein each receiver further:

compiles a garbled input based on labels received from the other receivers; and

executes a evaluate algorithm of the authentic garbled circuit protocol on the garbled circuit and the garbled input, the executing of the evaluate algorithm resulting in a garbled output Y.

14 . The non-transitory computer readable storage medium of claim 13 wherein each receiver further:

attempts to decrypt the ciphertext using the garbled output Y as a decryption key.

15 . A computer system acting as a dealer in a general access structure secret sharing (GAS-SS) scheme, the computer system comprising:

a processor; and

a non-transitory computer readable medium having stored thereon program code that, when executed, causes the processor to:

define an access structure for sharing a secret among N receivers, wherein the access structure identifies one or more qualified sets of the N receivers that are authorized to reveal the secret;

create a Boolean circuit that represents the access structure, wherein the Boolean circuit takes as input N input bit values corresponding to the N receivers, each input bit value having a value of zero if its corresponding receiver does not wish to reveal the secret during a reconstruction phase of the GAS-SS scheme and a value of one if its corresponding receiver wishes to reveal the secret during the reconstruction phase, and wherein the Boolean circuit generates an output bit value of zero if a subset of the N receivers that wish to reveal the secret as indicated by the N input bit values is not a qualified set and generates an output bit value of one if the subset of the N receivers that wish to reveal the secret as indicated by the N input bit values is a qualified set;

execute a garble algorithm of an authentic garbled circuit protocol on the Boolean circuit, the executing of the garble algorithm resulting in a garbled circuit and encoding information specifying N label pairs corresponding to the N receivers;

encrypt the secret using a garbled output Y 1 , the encrypting resulting in a ciphertext; and

send, to each receiver in the N receivers, the garbled circuit, the ciphertext, and a label pair for the receiver as specified in the encoding information.

16 . The computer system of claim 15 wherein the garbled output Y 1 is generated by an evaluate algorithm of the authentic garbled circuit protocol in a scenario where the evaluate algorithm receives as input the garbled circuit and a garbled input encoding a set of N input bit values corresponding to a qualified set of the N receivers.

17 . The computer system of claim 15 wherein the label pair for the receiver includes a zero label representing an input bit value of zero for the receiver and a one label representing an input bit value of one for the receiver.

18 . The computer system of claim 17 wherein upon receiving the garbled circuit, the ciphertext, and the label pair, each receiver:

informs other receivers in the N receivers whether the receiver wishes to reveal the secret or not.

19 . The computer system of claim 18 wherein each receiver informs the other receivers by:

sending to the other receivers the receiver's one label if the receiver wishes to reveal the secret; and

sending to the other receivers the receiver's zero label of the receiver does not wish to reveal the secret.

20 . The computer system of claim 18 wherein each receiver further:

compiles a garbled input based on labels received from the other receivers; and

executes a evaluate algorithm of the authentic garbled circuit protocol on the garbled circuit and the garbled input, the executing of the evaluate algorithm resulting in a garbled output Y.

21 . The computer system of claim 20 wherein each receiver further:

attempts to decrypt the ciphertext using the garbled output Y as a decryption key.