DISTRIBUTED REGISTRATION AND AUTHENTICATION VIA THRESHOLD SECRET SHARING AND ADDITIVELY HOMOMORPHIC ENCRYPTION

Abstract

Techniques for implementing distributed registration and authentication via threshold secret sharing and additively homomorphic encryption are provided. A threshold secret sharing scheme is a cryptographic method for sharing a secret among N parties in a manner that requires at least T+1 of the N parties to cooperate in order to reconstruct/reveal the secret, where T is some threshold value less than N. Additively homomorphic encryption is an encryption scheme that enables users to perform additive computations on encrypted data without first decrypting that data. With these techniques, a group of N nodes can efficiently perform distributed registration and authentication in a correct, secure, and privacy-preserving fashion, even if up to T of the N nodes are corrupted by an adversary.

Claims

1. A method comprising: receiving, by a set of N nodes in a computing system, a registration request from a client, the registration request including a communication endpoint address and a public key of the client; generating, by the set of N nodes, a T-out-of-N sharing [R] of a secret random value R using a threshold secret sharing scheme, wherein T corresponds a maximum number of nodes in the set of N nodes that may be corrupted by an adversary; encrypting, by each node i in the set of N nodes, a share R.sub.i of [R] using an encryption function of an additively homomorphic encryption (AHE) scheme, the encrypting resulting in a ciphertext ct.sub.i; sending, by said each node i in the set of N nodes, ct.sub.i to a designated node in the set of N nodes; computing, by the designated node using an evaluation function of the AHE scheme, a ciphertext ct.sub.f based on the public key, a reconstruct function of the threshold secret sharing scheme, and ct.sub.i received from said each node i; and sending, by the designated node, ct.sub.f to the client at the communication endpoint address.

2. The method of claim 1 further comprising: receiving, by said each node i in the set of N nodes, a share R′.sub.i of a T-out-of-N sharing [R′] from the client, wherein [R′] is generated by the client using the threshold secret sharing scheme based on a value R′ computed from ct.sub.f; computing, by the set of N nodes using their shares of [R] and [R′], a delta value Δ reflecting a difference between R and R′; and upon determining that Δ equals zero, storing, by said each node i in the set of N nodes, a registration entry E.sub.i for the client that includes the communication endpoint address and R.

3. The method of claim 2 wherein the client computes R′ by invoking a decryption function of the AHE scheme on ct.sub.f using a secret key corresponding to the public key.

4. The method of claim 2 wherein the client stores R as an authentication credential for logging into the computing system.

5. The method of claim 2 wherein the computing of Δ comprises: computing a sharing [Δ] of Δ based on [R] and [R′] using a secure multiparty computation (MPC) protocol; and reconstructing Δ from [Δ].

6. The method of claim 2 wherein Δ equals a difference between R and R′ multiplied by a secret random value Q that is unique to the registration request.

7. The method of claim 2 further comprising: receiving, by said each node i in the set of N nodes, an authentication request from the client, the authentication request including the communication endpoint address and a share R″.sub.i of a T-out-of-N sharing [R″], wherein [R″] is generated by the client using the threshold secret sharing scheme based on R; matching, by said each node i in the set of N nodes, the communication endpoint address in the authentication request to the previously stored registration entry E.sub.i; retrieving, by said each node i in the set of N nodes, R.sub.i from E.sub.i; computing, by the set of N nodes using their shares of [R] and [R″], a delta value Δ′ reflecting a difference between R and R″; and upon determining that Δ′ equals zero, outputting, by said each node i in the set of N nodes, a result indicating that the client is successfully authenticated.

8. A non-transitory computer readable storage medium having stored thereon program code executable by a set of N nodes in a computing system, the program code embodying a method comprising: receiving a registration request from a client, the registration request including a communication endpoint address and a public key of the client; generating a T-out-of-N sharing [R] of a secret random value R using a threshold secret sharing scheme, wherein T corresponds a maximum number of nodes in the set of N nodes that may be corrupted by an adversary; encrypting, by each node i in the set of N nodes, a share R.sub.i of [R] using an encryption function of an additively homomorphic encryption (AHE) scheme, the encrypting resulting in a ciphertext ct.sub.i; sending, by said each node i in the set of N nodes, ct.sub.i to a designated node in the set of N nodes; computing, by the designated node using an evaluation function of the AHE scheme, a ciphertext ct.sub.f based on the public key, a reconstruct function of the threshold secret sharing scheme, and ct.sub.i received from said each node i; and sending, by the designated node, ct.sub.f to the client at the communication endpoint address.

9. The non-transitory computer readable storage medium of claim 8 wherein the method further comprises: receiving, by said each node i in the set of N nodes, a share R′.sub.i of a T-out-of-N sharing [R′] from the client, wherein [R′] is generated by the client using the threshold secret sharing scheme based on a value R′ computed from ct.sub.f; computing, by the set of N nodes using their shares of [R] and [R′], a delta value Δ reflecting a difference between R and R′; and upon determining that Δ equals zero, storing, by said each node i in the set of N nodes, a registration entry E.sub.i for the client that includes the communication endpoint address and R.sub.i.

10. The non-transitory computer readable storage medium of claim 9 wherein the client computes R′ by invoking a decryption function of the AHE scheme on ct.sub.f using a secret key corresponding to the public key.

11. The non-transitory computer readable storage medium of claim 9 wherein the client stores R as an authentication credential for logging into the computing system.

12. The non-transitory computer readable storage medium of claim 9 wherein the computing of Δ comprises: computing a sharing [Δ] of Δ based on [R] and [R′] using a secure multiparty computation (MPC) protocol; and reconstructing Δ from [Δ].

13. The non-transitory computer readable storage medium of claim 9 wherein Δ equals a difference between R and R′ multiplied by a secret random value Q that is unique to the registration request.

14. The non-transitory computer readable storage medium of claim 9 wherein the method further comprises: receiving, by said each node i in the set of N nodes, an authentication request from the client, the authentication request including the communication endpoint address and a share R″.sub.i of a T-out-of-N sharing [R″], wherein [R″] is generated by the client using the threshold secret sharing scheme based on R; matching, by said each node i in the set of N nodes, the communication endpoint address in the authentication request to the previously stored registration entry E.sub.i; retrieving, by said each node i in the set of N nodes, R.sub.i from E.sub.i; computing, by the set of N nodes using their shares of [R] and [R″], a delta value Δ′ reflecting a difference between R and R″; and upon determining that Δ′ equals zero, outputting, by said each node i in the set of N nodes, a result indicating that the client is successfully authenticated.

15. A node in a set of N nodes that collectively make up a computing system, the node comprising: a processor; and a non-transitory computer readable medium having stored thereon program code that, when executed, causes the processor to: receive a registration request from a client, the registration request including a communication endpoint address and a public key of the client; generate, in conjunction with other nodes in the set of N nodes, a T-out-of-N sharing [R] of a secret random value R using a threshold secret sharing scheme, wherein T corresponds a maximum number of nodes in the set of N nodes that may be corrupted by an adversary; encrypt a share R.sub.i of [R] using an encryption function of an additively homomorphic encryption (AHE) scheme, the encrypting resulting in a ciphertext ct.sub.i; receive, from the other nodes, other ciphertexts Ct.sub.other created by the other nodes using the encryption function and the other nodes' shares of [R]; compute, using an evaluation function of the AHE scheme, a ciphertext ct.sub.f based on the public key, a reconstruct function of the threshold secret sharing scheme, ct.sub.i, and ct.sub.other; and send ct.sub.f to the client at the communication endpoint address.

16. The node of claim 15 wherein the program code further causes the processor to receive a share R′.sub.i of a T-out-of-N sharing [R′] from the client, wherein [R′] is generated by the client using the threshold secret sharing scheme based on a value R′ computed from ct.sub.f; compute, in conjunction with the other nodes, a delta value Δ reflecting a difference between R and R′; and upon determining that Δ equals zero, store a registration entry E.sub.i for the client that includes the communication endpoint address and R.

17. The node of claim 16 wherein the client computes R′ by invoking a decryption function of the AHE scheme on ct.sub.f using a secret key corresponding to the public key.

18. The node of claim 16 wherein the client stores R as an authentication credential for logging into the computing system.

19. The node of claim 16 wherein the program code that causes the processor to compute Δ comprises program code that causes the processor to: compute a sharing [Δ] of Δ based on [R] and [R′] using a secure multiparty computation (MPC) protocol; and reconstruct Δ from [Δ].

20. The node of claim 16 wherein Δ equals a difference between R and R′ multiplied by a secret random value Q that is unique to the registration request.

21. The node of claim 16 wherein the program code further causes the processor to: receive an authentication request from the client, the authentication request including the communication endpoint address and a share R″.sub.i of a T-out-of-N sharing [R″], wherein [R″] is generated by the client using the threshold secret sharing scheme based on R; match the communication endpoint address in the authentication request to the previously stored registration entry E.sub.i; retrieve R.sub.i from E.sub.i; compute, in conjunction with the other nodes, a delta value Δ′ reflecting a difference between R and R″; and upon determining that Δ′ equals zero, output a result indicating that the client is successfully authenticated.

Description

BRIEF DESCRIPTION OF THE DRAWINGS

[0007] FIG. 1 depicts an example environment according to certain embodiments.

[0008] FIG. 2 depicts a distributed registration workflow according to certain embodiments.

[0009] FIG. 3 depicts a distributed authentication workflow according to certain embodiments.

[0010] FIG. 4 depicts another distributed registration workflow according to certain embodiments.

DETAILED DESCRIPTION

[0011] In the following description, for purposes of explanation, numerous examples and details are set forth in order to provide an understanding of various embodiments. It will be evident, however, to one skilled in the art that certain embodiments can be practiced without some of these details or can be practiced with modifications or equivalents thereof.

1. Overview

[0012] The present disclosure is directed to techniques for implementing distributed registration and authentication, or in other words the collaborative processing of client registration and authentication requests by multiple nodes in a computing system. In one set of embodiments these techniques leverage threshold secret sharing, which is a cryptographic method for sharing a secret among N parties in a manner that requires at least T+1 of the N parties to cooperate in order to reconstruct/reveal the secret, where T is some threshold value less than N. An example of such a scheme is Shamir's secret sharing. In another set of embodiments these techniques also leverage additively homomorphic encryption, which is a type of encryption that enables users to perform additive computations on encrypted data without first decrypting that data.

[0013] With the techniques of the present disclosure, a group of N nodes can efficiently perform distributed registration and authentication in a correct, secure, and privacy-preserving fashion, even if up to T of the N nodes are corrupted by an adversary (subject to certain constraints on T and the nature of the network interconnecting the nodes and clients). These and other aspects are described in further detail below.

2. Example Environment and High-Level Solution Design

[0014] FIG. 1 depicts an example environment 100 in which embodiments of the present disclosure may be implemented. As shown, environment 100 includes a client C (reference numeral 102) that is communicatively coupled with a computing system 104 comprising N nodes S.sub.1, . . . , S.sub.N (reference numerals 106(1)-(N)) via a network 108. Generally speaking, the goal of nodes S.sub.1, . . . , S.sub.N—each of which may be any type of physical or virtual machine known in the art—is to register and authenticate clients like client C that wish to interact with computing system 104. Ideally, nodes S.sub.1, . . . , S.sub.N should implement these registration and authentication procedures in a manner that ensures correctness, security, and privacy in the face of attacks by an adversary.

[0015] As noted in the Background section, according to one approach known as single-node registration and authentication, each node S.sub.1 can handle client registration and authentication requests independently. For example, if node S.sub.1 receives a registration request from client C, S.sub.1 can process that registration request in its entirety without any interaction or communication with other nodes. Similarly, if node S.sub.2 receives an authentication request from client C after it has been registered via node S.sub.1, S.sub.2 can process that authentication request in its entirety without any interaction or communication with other nodes. However, this single-node approach quickly falls apart in the case where an adversary is able to take control of any individual node (i.e., S.sub.corrupted) because the adversary can thereafter censor clients via S.sub.corrupted (resulting in a loss of correctness), impersonate clients via S.sub.corrupted (resulting in a loss of security), and mount an offline attack to invert hashed client passwords via S.sub.corrupted (resulting in a potential loss of privacy).

[0016] To address the foregoing and other similar issues, embodiments of the present disclosure provide a distributed registration and authentication approach that enables nodes S.sub.1, . . . , S.sub.N of computing system 104 to process each client registration/authentication request in a collaborative manner. In various embodiments, this distributed approach relies on a threshold secret sharing scheme like Shamir's secret sharing that provides two functions: Share and Reconstruct. The Share function takes as input a secret s and outputs N cryptographic portions or “shares” of s (collectively known as a “sharing” of s and as denoted as [s]). Each share s.sub.i in [s] can be distributed to a party in a set of N parties, which allows the parties to carry out various operations on secret s using their respective shares (e.g., secure multiparty computations) while keeping s itself hidden from each party.

[0017] The Reconstruct function takes as input the shares created via the Share function and outputs the original secret s. Significantly, this Reconstruct function requires at least T+1 shares in order to reconstruct/reveal s, where T is some threshold number less than N. This guarantees that a coalition of up to T out of the N parties cannot learn secret s by colluding and disclosing their shares of s to each other; instead, a coalition of at least T+1 parties, and thus T+1 shares, are required. For this reason, [s] is sometimes referred to as a “T-out-of-N” sharing of s. In the case of Shamir's secret sharing, each share s.sub.i corresponds to a point p(i) on a T-degree polynomial p, with point p(0) being set to s. It is well known that such a T-degree polynomial cannot be uniquely interpolated with less than T+1 points, and thus this construction hides the secret encoded at p(0) from any subset of at most T parties.

[0018] In addition to the above, threshold secret sharing schemes are linear in nature, which means that given two sharings [x] and [y] where each party i holds x.sub.i and y.sub.i, the parties can locally obtain the sharing [z] where z=αx+βy+γ for some arbitrary public values α, β, γ.

[0019] With the foregoing explanation of threshold secret sharing in mind, the distributed registration procedure of the present disclosure can generally proceed as shown below. In certain embodiments, this implementation assumes threshold value T is less than N/3, where T is the maximum number of nodes out of S.sub.1, . . . , S.sub.N that may be corrupted by an adversary (such that the adversary is able to control the node's internal state and network communications); all network messages passed between client C and nodes S.sub.1, . . . , S.sub.N, as well as between the nodes themselves, are secured from tampering and eavesdropping via a mechanism such as Transport Layer Security (TLS); and network 108 is synchronous, which means that if a receiver does not receive an expected network message from a sender within a bounded period of time, the receiver proceeds with its configured processing using a default message containing some predefined value (e.g., zero or null). [0020] 1. Client C sends a registration request to nodes S.sub.1, . . . , S.sub.N that includes a communication endpoint address (e.g., email address, telephone number, etc.) owned by C [0021] 2. Nodes S.sub.1, . . . , S.sub.N receive the registration request and generate a T-out-of-N sharing of a random secret value R (i.e., [R]) via a threshold secret sharing scheme; the nodes (or a single node) then send information regarding [R] to client C [0022] 3. Client C reconstructs R using the received information, generates a new T-out-of-N sharing of R (i.e., [R′]) via the threshold secret sharing scheme, and sends share R′.sub.i to each node S.sub.i [0023] 4. Nodes S.sub.1, . . . , S.sub.N securely compute a difference (i.e., delta) between R and R′ using their original shares of [R] and the received shares of [R′] and, for each node S.sub.i, if the delta equals zero, node S.sub.i stores a local registration entry for client C comprising the communication endpoint address and its share R.sub.i of [R]; otherwise, the node takes no action [0024] 5. Client C stores R as its authentication credential for logging into system 104

[0025] Further, the distributed authentication procedure of the present disclosure can generally proceed as shown below. In certain embodiments, the same constraints/assumptions noted with respect to the distributed registration procedure also apply to this distributed authentication procedure. [0026] 1. Client C generates a new T-out-of-N sharing of R (i.e., [R′]) via the threshold secret sharing scheme and sends an authentication request to each node S.sub.i that includes C's previously registered communication endpoint address and share R′.sub.i [0027] 2. Nodes S.sub.1, . . . , S.sub.N securely compute a delta between R and R′ using the received shares of [R′] and their original shares of [R] and for each node S.sub.i, if the delta equals zero, node S.sub.i outputs a result (e.g., bit value, flag, etc.) indicating that C has been successfully authenticated by that node; otherwise, node S.sub.i outputs a result indicating that C has not been successfully authenticated by that node [0028] 3. System 104 grants access to client C if at least N−T of nodes S.sub.1, . . . , S.sub.N have successfully authenticated C per the results output at (2)

[0029] With these distributed implementations, client registration and authentication can be achieved while advantageously guaranteeing the properties of correctness, security, and privacy. For example, regarding correctness, an honest client will always be able to register and login by virtue of the characteristics of the threshold secret sharing scheme, as long as there are at most T corrupted nodes. Accordingly, an adversary cannot deny service or censor specific clients.

[0030] Regarding security, at the time a given client attempts to authenticate/login by submitting a communication endpoint address and a sharing [R′] based on its authentication credential R, if that address was not previously registered with the shares of [R] by nodes S.sub.1, . . . , S.sub.N, the delta computed by the nodes at step (2) of the distributed authentication procedure will not equal zero (for example, it may be undefined). Thus, each uncorrupted node will output a result indicating that the client has not been successfully authenticated, thereby denying access to the client.

[0031] And regarding privacy, because the original random value R generated at the time of registration is unknown to the nodes, the probability that an adversary guesses R is 1/ where is the threshold secret sharing scheme's underlying field. With a large enough field, an adversary cannot feasibly guess R. Further, the distributed authentication procedure above makes it impossible to run an offline brute-force attack to guess R, as each guess (which requires the submission of an authentication request) involves processing/interaction by all nodes S.sub.1, . . . , S.sub.N. Yet further, in certain embodiments the foregoing distributed registration and authentication procedures can be enhanced such that, at the time of securely computing the deltas at steps (4) and (2) respectively, nodes S.sub.1, . . . , S.sub.N can multiply each delta by a fresh random value Q. This enhancement, which is described in greater detail in sections (3) and (4) below, ensures that the nodes cannot learn anything regarding original random value R in the case where the client sends a sharing of a value R′ that is different from R.

3. Distributed Registration Workflow

[0032] FIG. 2 depicts a workflow 200 that provides additional details regarding the processing that may be performed by client C and nodes S.sub.1, . . . , S.sub.N of FIG. 1 for implementing distributed registration via threshold secret sharing according to certain embodiments.

[0033] Starting with step 202, client C can send a registration request to nodes S.sub.1, . . . , S.sub.N that includes a communication endpoint address ADDR owned by C (or alternatively, owned by a user/individual operating C). This communication endpoint address can be, e.g., an email address, a telephone number, an ID/username associated with a messaging application, or the like.

[0034] At step 204, nodes S.sub.1, . . . , S.sub.N can receive the registration request and generate/establish a T-out-of-N sharing of a secret random value R (denoted as [R]) via a threshold secret sharing scheme, such that (1) each node S.sub.i holds a share R.sub.i of [R], and (2) no node knows the value of R. For example, in one set of embodiments nodes S.sub.1, . . . , S.sub.N can receive their respective shares R.sub.1, . . . , R.sub.N from a trusted third-party that invokes the Share function of the threshold secret sharing scheme on R. In another set of embodiments, two nodes (e.g., S.sub.1 and S.sub.2) can create sharings of randomly selected values Y and Z where Y is only known to S.sub.1, Z is only known to S.sub.2, and random value R=Y+Z. Nodes S.sub.1 and S.sub.2 can then distribute the shares of [Y] and [Z] to the other nodes and each node can compute its share of [R] as the sum of its shares of [Y] and [Z]. With this method, no single node will know both Y and Z and thus cannot learn R.

[0035] Upon generating/establishing [R], each node S.sub.1 can send its respective share R.sub.i to client C via C's communication endpoint address ADDR (step 206).

[0036] At step 208, client C can receive the shares of [R] at ADDR and can reconstruct R (via the threshold secret sharing scheme's Reconstruct function) using the received shares. Client C then generate a new T-out-of-N sharing of the reconstructed value of R (denoted as [R′]) comprising shares R′.sub.1, . . . , R′.sub.N (step 210) and can send share R′.sub.i to each node S.sub.i (step 212).

[0037] At step 214, nodes S.sub.1, . . . , S.sub.N can receive shares R′.sub.1, . . . , R′.sub.N and can securely compute, via a secure multiparty computation (MPC) protocol, [Δ]=[Q].Math.([R]−[R′]), where [Q] is a new sharing of a non-zero secret random value Q that is generated by the nodes for this specific registration request. As mentioned previously, the use of Q in this computation prevents the nodes from learning anything regarding R in the scenario where R′ is different from R and thereby bolsters the privacy of the solution. In alternative embodiments where this additional degree of privacy preservation is not needed, the nodes can simply compute [Δ]=[R]−[R′].

[0038] Nodes S.sub.1, . . . , S.sub.N can thereafter collectively reconstruct/reveal delta value Δ using their shares of [Δ] (step 216) and each node S.sub.i can check whether Δ=0 (step 218). If the answer is yes (which means R=R′), node S.sub.i can conclude that client C correctly re-shared R at step 208 and thus is the owner of communication endpoint address ADDR. Accordingly, node S.sub.i can create and store a local registration entry E.sub.i for client C that includes ADDR and the node's share R.sub.i of [R] (step 220).

[0039] On the other hand, if the answer at step 218 is no, node S.sub.i can conclude that client C is not the owner of the communication endpoint address (or otherwise re-shared a value R′ that is different from R in violation of the registration procedure). In this case, node S.sub.i can take no action for registering client C (step 222).

[0040] Finally, at step 224, client C can store R as its authentication credential for logging into system 104 and workflow 200 can end.

4. Distributed Authentication Workflow

[0041] FIG. 3 depicts a workflow 300 that provides additional details regarding the processing that may be performed by client C and nodes S.sub.1, . . . , S.sub.N of FIG. 1 for implementing distributed authentication via threshold secret sharing according to certain embodiments. Workflow 300 assumes that client C has registered with system 104 via workflow 200 and thus C holds R and each (uncorrupted) node S.sub.i holds a local registration entry E.sub.i comprising C's communication endpoint address ADDR and that node's share R.sub.i of [R].

[0042] Starting with steps 302 and 304, Client C can generate a new T-out-of-N sharing of R (denoted as [R′]) comprising shares R′.sub.1, . . . , R′.sub.N and can send an authentication request to each node S.sub.i that includes ADDR and share R′.sub.i. In various embodiments, sharing [R′] is not the same as sharing [R′] described in distributed registration workflow 200; instead, [R′] here is a completely new sharing of R that is created by client C for this specific authentication request.

[0043] At step 306, each node S.sub.i can receive the authentication request, match the communication endpoint address ADDR included in the authentication request to the address identified in its local registration entry E.sub.i, and retrieve share R.sub.i from E.sub.i. Nodes S.sub.1, . . . , S.sub.N can then securely compute, via an MPC protocol, [Δ]=[Q].Math.([R]−[R′]) using the shares of R′ included in the received authentication requests and the shares of [R] retrieved from the local registration entries (step 308). As discussed with respect to workflow 200, [Q] is a new sharing of a non-zero secret random value Q that is generated by the nodes for this specific authentication request and is used to obfuscate the true value of [R]−[R] in cases where R≠R′, thereby preventing the nodes from learning anything regarding R.

[0044] At steps 310 and 312, nodes S.sub.1, . . . , S.sub.N can collectively reconstruct/reveal delta value Δ using their shares of [Δ] and each node S.sub.i can check whether Δ=0. If the answer is yes (which means R=R′), node S.sub.1 can conclude that client C has been successfully authenticated and can output a result b.sub.i indicating authentication success (step 314).

[0045] On the other hand, if the answer at step 312 is no, node S.sub.i can conclude that client C has not been successfully authenticated. In this case, node S.sub.i can output a result b.sub.i indicating authentication failure (step 316).

[0046] Finally, at step 318, system 104 can grant client C access if at least N— T nodes have output a result indicating authentication success per step 314 and workflow 300 can end.

5. Distributed Registration Workflow Using Additively Homomorphic Encryption

[0047] One drawback with the distributed registration workflow shown in FIG. 2 and described in section (3) above that that each node S.sub.i separately sends its share R.sub.i of [R] to client C at step 206. This reduces the usability of the solution in scenarios where N is large because the client must wait for and receive N separate messages from the nodes before it can reconstruct R and proceed with the registration.

[0048] To address this issue, FIG. 4 depicts an alternative distributed registration workflow 400 that leverages additively homomorphic encryption (AHE) according to certain embodiments. AHE is an encryption scheme that comprises the following functions: [0049] 1. (sk, pk).fwdarw.KeyGen(λ): The KeyGen function takes as input a security parameter A and outputs secret and public keys (sk, pk) [0050] 2. ct.fwdarw.Enc(pk, pt): The Enc function takes as input a public key pk and a plaintext pt and outputs a ciphertext ct [0051] 3. pt.fwdarw.Dec(sk, ct): The Dec function takes as input a secret key sk and a ciphertext ct and outputs a plaintext pt [0052] 4. ct.sub.f.fwdarw.Ev(pk, f, ct.sub.1, . . . , ct.sub.m): The Ev function takes as input a public key pk, an m-ary linear function ƒ, and a set of m ciphertexts ct.sub.1, . . . , ct.sub.m and outputs a ciphertext ct.sub.f

[0053] Generally speaking, an AHE scheme guarantees that, for any m and every m-ary linear function ƒ, Dec(sk, Ev(pk, f, ct.sub.1, . . . , ct.sub.m))=ƒ(Dec(sk, ct.sub.1), . . . , Dec(sk, ct.sub.m)) where (sk, pk).fwdarw.KeyGen(λ) for some λ and ct.sub.i is either the result of Enc(pk;) or Ev(pk, ƒ;). In other words, it doesn't matter whether you (1) first evaluate ƒ on the ciphertexts ct.sub.1, . . . , ct.sub.m using the Ev function (resulting in ct.sub.f) and then decrypt ct.sub.f or (2) first decrypt each ciphertext ct.sub.i separately using the Dec function (resulting in plaintexts pt.sub.1, . . . , pt.sub.m) and then evaluate ƒ on pt.sub.1, . . . , pt.sub.m; the results of (1) and (2) are the same.

[0054] This means that instead of having each node S.sub.i send its share R.sub.i to client C, each node S.sub.i can encrypt R.sub.i using an AHE scheme and send the resulting ciphertext ct.sub.i to a designated node (e.g., S.sub.1), which maintains the secrecy of the shares from S.sub.1. Designated node S.sub.1 can then compute ct.sub.f.fwdarw.Ev(pk, f, ct.sub.1, . . . , ct.sub.N) (where ƒ is the Reconstruct function of the threshold secret sharing scheme used to generate [R]) and can send ct.sub.f to client C. Client C can thereafter reconstruct R by computing Dec(sk, ct.sub.f) because per the properties of the AHE scheme, Dec(sk, ct.sub.f) is equivalent to Reconstruct(Dec(sk, ct.sub.1), . . . , Dec(sk, ct.sub.N)). Accordingly, with this approach, only a single message needs to be received by client C in order to reconstruct R (i.e., the message comprising ciphertext ct.sub.f sent from designated node S.sub.1), thereby significantly streamlining the registration process.

[0055] Turning now to workflow 400, client C can compute a secret key/public key pair (sk, pk) by invoking the KeyGen function of an AHE scheme (step 402) and can send a registration request to nodes Sp.sub.1, . . . , S.sub.N that includes a communication endpoint address ADDR owned by C (or alternatively, owned by a user/individual operating C) and the public key pk. This communication endpoint address can be, e.g., an email address, a telephone number, an ID/username associated with a messaging application, or the like.

[0056] At step 406, nodes S.sub.1, . . . , S.sub.N can receive the registration request and generate/establish a T-out-of-N sharing of a secret random value R (denoted as [R]) via a threshold secret sharing scheme, such that (1) each node S.sub.1 holds a share R.sub.i of [R], and (2) no node knows the value of R. As mentioned previously, in one set of embodiments nodes S.sub.1, . . . , S.sub.N can receive their respective shares R.sub.1, . . . , R.sub.N from a trusted third-party that invokes the Share function of the threshold secret sharing scheme on R. In another set of embodiments, two nodes (e.g., S.sub.1 and S.sub.2) can create sharings of randomly selected values Y and Z where Y is only known to S.sub.1, Z is only known to S.sub.2, and random value R=Y+Z. Nodes S.sub.1 and S.sub.2 can then distribute the shares of [Y] and [Z] to the other nodes and each node can compute its share of [R] as the sum of its shares of [Y] and [Z]. With this method, no single node will know both Y and Z and thus cannot learn R.

[0057] At step 408, each node S.sub.i can compute ciphertext ct.sub.i by invoking the Enc function of the AHE scheme on its share R.sub.i using public key pk (i.e., Enc(pk, R.sub.i) and can send ct.sub.i to a designated node (e.g., S.sub.1). In response, designated node S.sub.1 can compute ciphertext ct.sub.f by invoking the Ev function of the AHE scheme on the Reconstruct function of the threshold sharing scheme, ciphertexts ct.sub.1, . . . , ct.sub.N, and public key pk (i.e., Ev(pk, Reconstruct, ct.sub.i, . . . , ct.sub.N) (step 410). Designated node S.sub.1 can then send a single message comprising ct.sub.f to client C via C's communication endpoint address ADDR (step 412).

[0058] At step 414, client C can receive ciphertext ct.sub.f at ADDR and can compute R by invoking the Dec function of the AHE scheme on ct.sub.f using its secret key sk (i.e., Dec(sk, ct.sub.f)). Client C can subsequently generate a new T-out-of-N sharing of the reconstructed value of R (denoted as [R′]) comprising shares R′.sub.1, . . . , R′.sub.N (step 416) and can send share R′.sub.i to each node S.sub.i (step 418).

[0059] At step 420, nodes S.sub.1, . . . , S.sub.N can receive shares R′.sub.1, . . . , R′N and can securely compute, via a secure multiparty computation (MPC) protocol, [Δ]=[Q].Math.([R]−[R′]), where [Q] is a new sharing of a non-zero secret random value Q that is generated by the nodes for this specific registration request. As mentioned previously, the use of Q in this computation prevents the nodes from learning anything regarding R in the scenario where R′ is different from R and thereby bolsters the privacy of the solution. In alternative embodiments where this additional degree of privacy preservation is not needed, the nodes can simply compute [Δ]=[R]−[R′].

[0060] Nodes S.sub.1, . . . , S.sub.N can then collectively reconstruct/reveal delta value Δ using their shares of [Δ] (step 422) and each node S.sub.i can check whether Δ=0 (step 424). If the answer is yes (which means R=R′), node S.sub.i can conclude that client C correctly re-shared R at step 418 and thus is the owner of communication endpoint address ADDR. Accordingly, node S.sub.i can create and store a local registration entry E.sub.i for client C that includes ADDR and the node's share R.sub.i of [R] (step 426).

[0061] On the other hand, if the answer at step 424 is no, node S.sub.i can conclude that client C is not the owner of the communication endpoint address (or otherwise re-shared a value R′ that is different from R in violation of the registration procedure). In this case, node S.sub.i can take no action for registering client C (step 428).

[0062] Finally, at step 430, client C can store R as its authentication credential for logging into system 104 and workflow 400 can end.

[0063] In various embodiments, workflow 400 assumes that designated node S.sub.1 is semi-honest (i.e., will not actively attempt to sabotage the registration process) and thus will not send an incorrect value for ciphertext ct.sub.f to client C at step 412. In addition, workflow 400 assumes that the Reconstruct function of the threshold secret sharing scheme is a linear function. This latter assumption will be true if the threshold secret sharing scheme is, e.g., Shamir's secret sharing.

[0064] Certain embodiments described herein can employ various computer-implemented operations involving data stored in computer systems. For example, these operations can require physical manipulation of physical quantities—usually, though not necessarily, these quantities take the form of electrical or magnetic signals, where they (or representations of them) are capable of being stored, transferred, combined, compared, or otherwise manipulated. Such manipulations are often referred to in terms such as producing, identifying, determining, comparing, etc. Any operations described herein that form part of one or more embodiments can be useful machine operations.

[0065] Further, one or more embodiments can relate to a device or an apparatus for performing the foregoing operations. The apparatus can be specially constructed for specific required purposes, or it can be a generic computer system comprising one or more general purpose processors (e.g., Intel or AMD x86 processors) selectively activated or configured by program code stored in the computer system. In particular, various generic computer systems may be used with computer programs written in accordance with the teachings herein, or it may be more convenient to construct a more specialized apparatus to perform the required operations. The various embodiments described herein can be practiced with other computer system configurations including handheld devices, microprocessor systems, microprocessor-based or programmable consumer electronics, minicomputers, mainframe computers, and the like.

[0066] Yet further, one or more embodiments can be implemented as one or more computer programs or as one or more computer program modules embodied in one or more non-transitory computer readable storage media. The term non-transitory computer readable storage medium refers to any storage device, based on any existing or subsequently developed technology, that can store data and/or computer programs in a non-transitory state for access by a computer system. Examples of non-transitory computer readable media include a hard drive, network attached storage (NAS), read-only memory, random-access memory, flash-based nonvolatile memory (e.g., a flash memory card or a solid state disk), persistent memory, NVMe device, a CD (Compact Disc) (e.g., CD-ROM, CD-R, CD-RW, etc.), a DVD (Digital Versatile Disc), a magnetic tape, and other optical and non-optical data storage devices. The non-transitory computer readable media can also be distributed over a network coupled computer system so that the computer readable code is stored and executed in a distributed fashion.

[0067] Finally, boundaries between various components, operations, and data stores are somewhat arbitrary, and particular operations are illustrated in the context of specific illustrative configurations. Other allocations of functionality are envisioned and may fall within the scope of the invention(s). In general, structures and functionality presented as separate components in exemplary configurations can be implemented as a combined structure or component. Similarly, structures and functionality presented as a single component can be implemented as separate components.

[0068] As used in the description herein and throughout the claims that follow, “a,” “an,” and “the” includes plural references unless the context clearly dictates otherwise. Also, as used in the description herein and throughout the claims that follow, the meaning of “in” includes “in” and “on” unless the context clearly dictates otherwise.

[0069] The above description illustrates various embodiments along with examples of how aspects of particular embodiments may be implemented. These examples and embodiments should not be deemed to be the only embodiments and are presented to illustrate the flexibility and advantages of particular embodiments as defined by the following claims. Other arrangements, embodiments, implementations, and equivalents can be employed without departing from the scope hereof as defined by the claims.