Patent Publication Number: US-2023143175-A1

Title: Device specific multiparty computation

Description:
BACKGROUND 
     Secure multiparty computation (MPC) is a technology that enables different parties with private inputs to carry out a joint computation on their inputs without revealing them to each other. It is a cryptographic protocol that distributes a computation across multiple parties where no individual party can see the other parties&#39; data. Generally, any computable function can be computed securely via MPC. Unfortunately, MPC suffers from high communication complexity and only offers costly input verification options. Moreover, efficient MPC schemes are often not post-quantum secure. Furthermore, efficient MPC solutions do not support general access structures in which any number of arbitrary device-sets from a set of devices are authorized to recreate the secret and hence perform MPC. 
     SUMMARY 
     In one implementation, the disclosure provides systems and methods for a multi-party secret sharing protocol that is device specific in that the secret matrix used herein is tied to individual computing devices. Specifically, the method includes determining device channel errors of a plurality of computing devices based on channel impulse response (CIR) of communication channels of the plurality of computing devices, training a linear regression model using the device channel errors to generate learning with error (LWE) secrets for each of the plurality of computing devices, generating a general access structure secret matrix using the LWE secrets from each of the plurality of computing devices, and distributing shares of the general access structure secret matrix to the plurality of computing devices based on a multi-party secret sharing protocol, wherein the multi-party secret sharing protocol provides that the general access structure secret matrix cannot be constructed without shares from an authorized set of the computing devices. 
     This Summary is provided to introduce a selection of concepts in a simplified form that are further described below in the Detailed Description. This Summary is not intended to identify key features or essential features of the claimed subject matter, nor is it intended to be used to limit the scope of the claimed subject matter. These and various other features and advantages will be apparent from a reading of the following Detailed Description. 
    
    
     
       BRIEF DESCRIPTIONS OF THE DRAWINGS 
       A further understanding of the nature and advantages of the present technology may be realized by reference to the figures, which are described in the remaining portion of the specification. In the figures, like reference numerals are used throughout several figures to refer to similar components. In some instances, a reference numeral may have an associated sub-label consisting of a lower-case letter to denote one of multiple similar components. When reference is made to a reference numeral without specification of a sub-label, the reference is intended to refer to all such multiple similar components. 
         FIG.  1    illustrates an example system that allows multiple parties to share secret in the manner disclosed herein. 
         FIG.  2    illustrates a visual depiction of a procedure for using the secret sharing in the manner disclosed herein. 
         FIG.  3    illustrates example operations for parties to use secret sharing in the manner disclosed herein. 
         FIG.  4    illustrates an example processing system that may be useful in implementing the described technology. 
     
    
    
     DETAILED DESCRIPTION 
     Encryption algorithms including block ciphers like advanced encryption standard (AES) encryption, Blowfish™ etc., are device independent. The same holds for pseudorandom functions (PRFs). Device independence here means that it does not matter whether device A or device B performs the algorithm, and it is the key/index alone that selects a particular instance of the encryption algorithm. The technology disclosed herein provides device-specific encryption algorithms and PRF constructions, which can be tied to individual devices. Specifically, such device-specific encryption algorithms are tied to the individual devices in that one or more inherent and/or unique characteristics of the device performing the calculations govern the behavior of the encryption algorithms. Thus, the implementations of the encryption algorithms disclosed herein may behave differently on different devices. 
     Furthermore, the technology disclosed herein provides device specific two-round secure multiparty communication (MPC) for general access structure of devices with group homomorphism and input verification. Here, MPC refers to implementations that enable different device (or parties) with private inputs to carry out a joint computation on their inputs without revealing their private inputs to each other. Thus, the implementations disclosed herein provide a cryptographic protocol that distributes a computation across multiple devices where no individual device can see the other parties&#39; private inputs. 
     Implementations of the technology disclosed herein provide a multi-party secret sharing protocol that is device specific in that the secret matrix used herein is tied to individual computing devices. Specifically, the secret matrix may be generated based on inherent and/or unique characteristics of the devices participating in the secret sharing protocol—namely channel impulse responses of the communication channels between the participating computing devices. Furthermore, the secret matrix used herein enforces general access structures, which allows defining any number of arbitrary device-sets from a set of devices that are authorized to recreate the secret and hence perform MPC. 
     Secret sharing provides a means to distribute shares of a secret so that any authorized subset of participants may reconstruct the secret. In the field of computer science, such a secret may comprise data in a memory device of a computing system comprising one or more computing devices. Shares of the secret (which may alternatively be referred to as share data) may be created. The shares of the secret may correspond to share data that can be provided to a plurality of computing devices. In turn, when shares are received from any authorized subset of participants, the shares may be used to recompute the secret (i.e., recreate the original data of the secret at a computing device). In trivial secret sharing, it may be that all of the computing devices to which share data has been provided must participate in reconstruction of the secret. This, however, is not optimal as certain parties may be compromised or lose the share data. In this scenario, the secret may not be capable of being reconstructed and the secret data lost. 
     Accordingly, in one example of a secret sharing scheme, a threshold is established corresponding to a given number of participants who must participate in a request to reconstruct the secret to successfully achieve secret reconstruction. In such a scheme, a total number of parties (n) are provided shares such that a threshold (t) number of parties must be participants in secret reconstruction to be successful. This is often referred to as the threshold case or a (t, n)-threshold scheme. In the traditional (t, n)-threshold scheme, the authorized subset of participates required to reconstruct the secret is defined by a publicly known access structure. That is, all participants know that so long as a threshold (t) or greater number of participants provide shares, the secret can be reconstructed. 
     However, certain scenarios may exist where multiple parties wish to perform secret sharing, but the parties to which a share has been provided do not trust each other completely. A multitude of such scenarios can be contemplated including, for example, potentially adverse business parties, potentially adverse government actors, or any other situation in which distrust between parties may exist. In relation to such a scenario, a solution to address this issue has been proposed that implements an asymmetric trust model. In such an asymmetrical trust model, each party to which a share has been provided is allowed to specify a trust structure. In the trust structure, each party declares which of the other parties having shares that it trusts. Such trust structures may be used to define one or more authorized subsets which specify the parties that are trusted by all or at least a majority of the other parties, and adversary subsets which specify the parties that are not trusted by all or at least a majority of the other parties. 
     In any regard, once each party having a share declares its trust structure, the protocol (applied by an entity sometimes referred to as a “dealer,” which may or may not itself be a party having a share) uses the trust structures declared by each party to generate the authorized subset of participants required to successfully reconstruct the secret using the shares of the authorized subset of participants. 
     However, prior solutions proposed for asymmetrical trust models require the trust structure of each party to be public. As can be readily understood, it is highly undesirable in practical settings for the trust structure of each party to be known by the other parties in the secret sharing scheme. For instance, heightened animosity, fear of retaliation, souring of relationships, or other adverse outcomes may occur when trust structures are publicly known. In fact, the problem of mandating public trust structures is common among all secret sharing schemes, irrespective of whether a secret sharing scheme supports threshold or general access structures. 
     Therefore, the solutions disclosed herein provides training a linear regression model using the device channel errors to generate learning with error (LWE) secrets for various devices, generating a secret matrix using the LWE secrets from the various devices, and distributing shares of the secret matrix to the various devices based on a multi-party secret sharing protocol, wherein the multi-party secret sharing protocol provides that the secret matrix cannot be constructed without shares from an authorized set of the devices, and wherein the device channel errors are determined based on channel impulse response (CIR) of communication channels of the various devices. 
     In view of the foregoing, the following discussion relates to mathematical concepts that facilitate the secret access structures having the properties described above. Specifically, a system may have a plurality of parties defined as  ={P 1 , . . . ,  }. An access structure is defined as Γ⊆ , which is a monotone collection of non-empty subsets of the set of parties ( ). A collection Γ⊆  is monotone if  ∈Γ and  ⊆  imply that  ∈Γ. Sets in Γ are called authorized and sets not in Γ are called not authorized. If Γ consists of all subsets of   with size greater than or equal to a fixed threshold t (1≤t≤ ), then Γ is called a t-threshold access structure. For an access structure Γ, a family of minimal authorized subsets Γ 0  ∈Γ is defined as: 
     Γ 0 ={ ∈Γ:   is not a subsetsbust of   for all  ∈Γ\{ }} 
     A computational secret sharing scheme may comprise of a pair of polynomial-time algorithms that are provided respect to an access structure (Γ), a security parameter (ω), a set of  polynomial-time parties  ={P 1 , . . . , P l }, and a set of secrets ( ). Polynomial-time algorithms are utilized in contrast to exponential algorithms to provide computational efficiency to the secret sharing scheme. In this regard, the secret sharing scheme may be conditionally secure against classical and quantum computing resources. 
     The polynomial-time algorithms may include a share generation algorithm and a secret reconstruction algorithm. The share generation algorithm is a randomized algorithm that gets a secret that is an element of the secret set (k∈ ) and access structure Γ as inputs and outputs a share for each of the parties. That is, the share generation algorithm outputs a number of shares equal to the number of parties. The shares may be defined as ({Π 1   (k) , . . .  }). In turn, each share can be provided to a party in the secret sharing scheme such that the access structure is encoded in the share by the share generation algorithm. 
     The secret reconstruction algorithm is a deterministic algorithm that gets as inputs the shares of a participating subset of the parties and outputs a string in the secret set. That is, the participating subset may be defined as  ⊆  denoted by  . 
     In relation to the share generation algorithm and the secret reconstruction algorithm, the algorithms may provide perfect correctness and computational secrecy. In relation to perfect correctness, for all secrets that are an element of the secret set and every authorized subset in the access structure, the output of the secret reconstruction algorithm is the secret (for all k∈K and every authorized subset  ∈θ, it holds that Pr [Recon( ,  )=k]=1). 
     In relation to computational secrecy, for each subset that is not authorized and for any different secrets from the secret set, the distributions of the shares for parties from the unauthorized set are computationally indistinguishable (for every subset  ∉Γ and all different secrets k 1 , k 2  ∈ , it holds that the distributions   and   are computationally indistinguishable with respect to ω). If ∀k 1 , k 2  ∈ K with k 1 ≠k 2 , the distributions   and   are identical, then the scheme is called a perfect sharing scheme. 
     The present invention generally utilizes Extremal Set Theory to construct set systems under certain intersection restrictions and bounding their size. In relation to utilization of such Extremal Set Theory, in one example, it is provided that m=Π i=1   r  p i   α     i    is a positive integer with r&gt;1 different prime divisors. Then there exists an explicitly constructible polynomial Q with n variables and degree 0(n 1/r ), which is equal to 0 on z=(1,1, . . . , 1) ∈ {0,1} n  but is nonzero mod m on all other z ∈ {0,1} n . Furthermore, ∀z ∈ {0,1} n  and ∀i ∈ {1, . . . , r}, it holds that: Q(z) ∈ {0,1} mod p i   α     i   . 
     In addition, let m be a positive integer, and suppose that m has r&gt;1 different prime divisors: m=Π i=1   r  p i   α     i   . Then there exists c=c(m)&gt;0, such that for every integer h&gt;0, there exists an explicitly constructible uniform set-system   over a universe of h elements such that: 
     
       
         
           
             
               
                 
                   
                     
                       1. 
                           
                       
                         
                           ❘ 
                           &#34;\[LeftBracketingBar]&#34; 
                         
                         ℋ 
                         
                           ❘ 
                           &#34;\[RightBracketingBar]&#34; 
                         
                       
                     
                     ≥ 
                     
                       exp 
                       ⁢ 
                          
                       
                         ( 
                         
                           c 
                           ⁢ 
                           
                             
                               
                                 ( 
                                 
                                   log 
                                   ⁢ 
                                      
                                   h 
                                 
                                 ) 
                               
                               r 
                             
                             
                               
                                 ( 
                                 
                                   log 
                                   ⁢ 
                                      
                                   log 
                                   ⁢ 
                                      
                                   h 
                                 
                                 ) 
                               
                               
                                 r 
                                 - 
                                 1 
                               
                             
                           
                         
                         ) 
                       
                     
                   
                   , 
                     
                 
               
             
             
               
                 
                   
                     
                       2. 
                           
                       
                         ∀ 
                         
                           H 
                           ∈ 
                           
                             ℋ 
                             : 
                             
                               
                                 ❘ 
                                 &#34;\[LeftBracketingBar]&#34; 
                               
                               H 
                               
                                 ❘ 
                                 &#34;\[RightBracketingBar]&#34; 
                               
                             
                           
                         
                       
                     
                     = 
                     
                       0 
                       ⁢ 
                          
                       mod 
                       ⁢ 
                          
                       m 
                     
                   
                   , 
                 
               
             
             
               
                 
                   
                     3. 
                        
                     
                       ∀ 
                       G 
                     
                   
                   , 
                   
                     H 
                     ∈ 
                     ℋ 
                   
                   , 
                   
                     G 
                     ≠ 
                     
                       H 
                       : 
                       
                         
                           
                             ❘ 
                             &#34;\[LeftBracketingBar]&#34; 
                           
                           
                             G 
                             ⋂ 
                             H 
                           
                           
                             ❘ 
                             &#34;\[RightBracketingBar]&#34; 
                           
                         
                         ≠ 
                         
                           0 
                           ⁢ 
                              
                           mod 
                           ⁢ 
                              
                           
                             m 
                             . 
                           
                         
                       
                     
                   
                 
               
             
           
         
       
     
     Matching vector (MV) families follow from the foregoing definition in which m=Π i=1   r  p i   α     i    is a positive integer with r&gt;1 different prime divisors and are used in cryptography in the context of private information retrieval, conditional disclosure of secrets, and secret sharing. 
     In addition, let m be a positive integer with r&gt;1 different prime divisors: m=Π i=1   r  p i   α     i   , and S ⊆   m \{0}. The family of vectors {u i } i=1   n , u i  ∈ (   m ) h  is said to be S-matching if the following conditions hold: 
     1.  u i , u i   =0 for every i ∈ [n]. 
     2.  u i , u j    ∈ S for every i≠j. 
     where  ·  denotes the inner product, and h&gt;0 is an integer. 
     The following result has been proven about the existence of MV families, modulo a non-prime power m. For positive integers h, r and m=Π i=1   r  p i   α     i   , there exists a set S, such that |S|=2 r −1, and a family of S-matching vectors {u i } i=1   n , where u i  ∈ (   m ) h , such that n≥ 
     
       
         
           
             exp 
             ⁢ 
                
             
               
                 ( 
                 
                   c 
                   ⁢ 
                   
                     
                       
                         ( 
                         
                           log 
                           ⁢ 
                              
                           h 
                         
                         ) 
                       
                       r 
                     
                     
                       log 
                       ⁢ 
                          
                       
                         
                           log 
                              
                         
                         
                           r 
                           - 
                           1 
                         
                       
                       ⁢ 
                       h 
                     
                   
                 
                 ) 
               
               . 
             
           
         
       
     
     Hence, MV families exist for values of h that are significantly smaller than n. 
     The secret sharing scheme described herein may also leverage discrete Gaussian sampling as will now be described. For any center c ∈ , and Gaussian parameter s ∈    + , the discrete Gaussian distribution may be defined as: 
     
       
         
           
             
               
                 D 
                 
                   s 
                   , 
                   c 
                 
               
               = 
               
                 
                   
                     ρ 
                     
                       s 
                       , 
                       c 
                     
                   
                   ( 
                   x 
                   ) 
                 
                 
                   
                     ∑ 
                     
                       y 
                       = 
                       
                         - 
                         ∞ 
                       
                     
                     ∞ 
                   
                     
                   
                     
                       ρ 
                       
                         s 
                         , 
                         c 
                       
                     
                     ( 
                     y 
                     ) 
                   
                 
               
             
             , 
           
         
       
     
     ∀x ∈ , where ρ s,c (x)=e −π|x−c|     2     /s     2    is the Gaussian function. The parameters of discrete Gaussians are governed by the security proofs of the particular cryptosystem. A finite machine cannot sample from a discrete Gaussian distribution, hence one has to sample from a distribution close to it. It is a common practice to require that the statistical distance of the sampled distribution from the desired discrete Gaussian be less than 2 100 . A number of Gaussian sampling algorithms for lattice-based cryptosystems may be utilized herein without limitation 
     Furthermore, a novel implementation of cumulative distribution function (CDF) inversion sampler with high precision and large tail bound has been demonstrated with maximum statistical distance of 2 −90  to a theoretical discrete Gaussian distribution. Such a sampler may take on average 9.44 random bits and 2.28 clock cycles to generate a sample and consumes 1 block RAM with 17 slices on a Spartan-6 FPGA. Hence, efficient and practical Gaussian sampling for lattice-based cryptography is becoming more practical. 
     Generation of shares may also utilize concepts related to the Learning With Errors (LWE) problem. The learning with errors (LWE) problem requires to recover a secret s given a sequence of ‘approximate’ random linear equations on it. LWE is known to be hard based on certain assumptions regarding the worst-case hardness of standard lattice problems such as GapSVP (decision version of the Shortest Vector Problem) and SIVP (Shortest Independent Vectors Problem). Many cryptosystems have been constructed whose security can be proven under the LWE problem, including (identity-based, leakage-resilient, fully homomorphic, functional) encryption, oblivious transfer, (blind) signatures, pseudorandom functions (PRFs), key-homomorphic PRFs, key-homomorphic constrained PRFs, hash functions, etc. 
     Two examples of implementation of LWE are described. The first is Decision-LWE. In this example, for positive integers n (the security parameter) and q≥2, and an error (probability) distribution x=x(n) over    q , the decision-LWE n,q,x  problem is to distinguish between the following pairs of distributions: 
       (A, A T s+e) and (A, u), 
     where 
     
       
         
           
             
               m 
               = 
               
                 poly 
                 ( 
                 n 
                 ) 
               
             
             , 
             
               A 
               
                 ← 
                 $ 
               
               
                 ℤ 
                 q 
                 
                   n 
                   × 
                   m 
                 
               
             
             , 
             
               s 
               
                 ← 
                 $ 
               
               
                 ℤ 
                 q 
                 n 
               
             
             , 
             
               e 
               
                 ← 
                 $ 
               
               
                 χ 
                 m 
               
             
             , 
             
               
                 and 
                 ⁢ 
                     
                 u 
               
               
                 ← 
                 $ 
               
               
                 
                   ℤ 
                   q 
                   m 
                 
                 . 
               
             
           
         
       
     
     The other is Search-LWE for which positive integers n (the security parameter) and q≥2, and an error (probability) distribution x=x(n) over    q , the search-LWE n,q,x  problem is to recover s ∈    q   n , given m(=(n)) independent samples of (A, A T  s+e), where 
     
       
         
           
             
               A 
               
                 ← 
                 $ 
               
               
                 ℤ 
                 q 
                 
                   n 
                   × 
                   m 
                 
               
             
             , 
             
               s 
               
                 ← 
                 $ 
               
               
                 ℤ 
                 q 
                 n 
               
             
             , 
             
               
                 and 
                 ⁢ 
                     
                 e 
               
               
                 ← 
                 $ 
               
               
                 
                   χ 
                   m 
                 
                 . 
               
             
           
         
       
     
     For security parameter λ such that n=(λ), it has been proven that for a certain noise distribution x and a sufficiently large q, the LWE problem is as hard as the worst-case SIVP (Shortest Independent Vectors Problem) and GapSVP (decision version of the Shortest Vector Problem) under a quantum reduction. These results have been extended to show that s can be sampled from a low norm distribution (in particular, from the noise distribution x) and the resulting problem is as hard as the basic LWE problem. Similarly, the noise distribution x can be a simple low-norm distribution. 
     Note that the seed and error vectors in the definitions can be replaced by matrices of appropriate dimensions, that are sampled from the same distributions as the vectors. Such interchange does not affect the hardness of LWE. 
     The present disclosure may also utilize Trapdoors for Lattices. Trapdoors for lattices utilized in the present disclosure are provided herein. For example, let m≥nk be an integer and  m =m−nk. For A ∈    q   n×m , it may be that R ∈    q     m ×nk  is a trapdoor for A with tag H ∈   q   n×n  if 
     
       
         
           
             
               
                 A 
                 [ 
                 
                   
                     
                       R 
                     
                   
                   
                     
                       I 
                     
                   
                 
                 ] 
               
               = 
               
                 H 
                 · 
                 G 
               
             
             , 
           
         
       
     
     where G ∈    q   n×nk  is a primitive matrix. 
     Given a trapdoor R for A, and an LWE instance B=AS+E mod q for some “short” (with small enough infinity or Euclidean norm) error matrix E ∈    m×n , the LWE inversion algorithm from successfully recovers S (and E) with overwhelming probability. 
       FIG.  1    illustrates an example secret sharing system  100  that allows multiple parties to share and recreate secret in the manner disclosed herein. The secret sharing system  100  may include several devices, such as device  108   a,    108   b,    108   n,  etc., (referred to as  108 ). In one implementation, the devices  108  can be arranged in a directed acyclic graph structure. The devices  108  may be computing devices such as laptops, desktops, servers, mobile phones, tablets, etc. Each of the devices  108  may include a communication channel  110 , a processor  112 , a memory  114 , and several other components. An example of a computing device that maybe used to implement the device  108  is disclosed in  FIG.  4    below. 
     The communication channel  110  may be implemented using a physical transmission medium, preferably, a wireless channel. The communication channel  110  may be used to communicate data between various components of the device  108 , such as data between the processor  112  and the memory  114 , the processor and one or more input/output devices, etc. The communication channel  110  may be characterized by its impulse response, referred to here as the channel impulse response (CIR). Specifically, the CIR of the communication channel  110  may be represented by the output of the communication channel  110  when it is presented with a brief input signal or an impulse. 
     Specifically, CIR of the communication channel  110  represents reaction of the communication channel  110  in response to an input change. The CIR of communication channel  110  is unique for each communication channel  110  of the computing devices. Thus, the CIR of the communication channel  110  of device  108   a  is different than the CIR of the communication channel  110  of the device  108   b,  and they are both different from the CIR of the communication channel  110  of the device  108   n.  In the illustrated implementation, the CIR of the communication channel  110  is used as discrete gaussian error for the devices. 
     The memory  114  may include various computer programmable instructions that may be executable over the processor  112 . In one implementation, the memory  114  includes a Golay code generator  118  that is configured to generate Golay codes and a random number generator (RND)  116  that is configured to generate random numbers. The Golay codes generated by the Golay code generator  118  may be a 24-bit extended binary code or a 23-bit perfect binary code. 
     An error corrector  120  may receive a digitized version of the CIR for the communication channel  110  and use the Golay code received from the Golay code generator  118  to correct device specific errors  122 . Specifically, the error corrector  120  receives CIR c i  from the communication channel  110  for a number of iterations of the communication channel and uses the Golay codes to generate the corrected CIR vector c i ′. The corrected errors  112  generated by the error corrector  1120  maybe represented by y i =c i −c i ′, which can be turned into an element from the desired learning with error (LWE) error distribution by using specifically designated deterministic random number generator RND  116 . 
     Subsequently, the error vector  122  from each of the various devices  108  are communicated to a dealer or a trusted party  130  (referred to hereinafter as the trusted party  130 ). For example, the trusted party  130  may be a trusted party that generates and encodes a secret matrix that may be used by the devices  108  to implement an MPC solution. Specifically, the trusted party  130  may be implemented on a server that is communicatively connected to the devices  108 . Alternatively, one of the devices  108 , that is arranged in a directed acyclic graph may function as the trusted party  130 . 
     The trusted party  130  may include a lattice-based cryptography module  134  that is configured to provides sampling from discrete gaussian distribution of errors  120  received from various devices  120 . The samplings generated by the lattice-based cryptography module  134  are input to a linear regression model (LRM)  132  that generates training data of LWE instances  136  to ensure that the distribution of the LWE instances  136  is discrete gaussian, while still preserving the hardness of LWE. This is referred to herein as learning with linear regression (LWLR). 
     A general access structure (GAS) secret matrix generator  138  generates a secret matrix using the LWE instances  136 . Subsequently, a GAS secret share generator  140  generates shares of the GAS secret matrix for each of the devices  108 . In one implementation, the GAS secret share generator  140  may generate shares for the devices by using a vector family V as per the corollary 2 described below: 
     
       
         
           
               
             
               
                   
               
             
            
               
                 Corollary 2. Let m = p 1   α1 p 2   α2  ... p r   αr  be a positive integer with r &gt; l distinct 
               
               
                 prime divisors, and l ≥ 2 be an integer such that l &lt; min (p 1 , p 2 , ..., p r ). Then, 
               
               
                 there exists c &gt; 0 such that for all integers t ≥ 2 and h ≥ lm, there exists a 
               
               
                 family of vectors v = {u i   N } i = l , such that: 
               
               
                  1. ∀i ∈ [N], it holds that:     u i , U i     = 0 mod m, 
               
               
                  2. V has t-wise restricted intersections modulo m. 
               
               
                  3. ∀i, j ∈ [N], where i ≠ j, it holds that: 
               
               
                   
               
               
                    
           〈       u   i     ,     u   j       〉     ⁢   mod   ⁢         m     =     {         0         if   ⁢           H   i                   H   j     ⁢         or   ⁢           H   j                   H   1                 ≠   0           otherwise   .                 
 
               
               
                   
               
               
                  4. (follows from Remark 1) for each i ∈ [N], there exists either 2 l−1  or l 
               
               
                   number of j ∈ [N] (j ≠ i) such that    u i , u j     = 0 mod m. 
               
               
                   As described in Corollary 2, let V be a vector family consisting of 
               
               
                  representative vectors for the sets in some set-system    . We define a k-multilinear 
               
               
                  form on V k  by: 
               
               
                        w 1 , w 2 , . . . , w k      k  = Σ i=1   h  w 1 , w 2 , i . . . w k , i. 
               
               
                   
               
               
                   For any v ∈ V, we will use the same symbol v to represent the 
               
               
                  corresponding set in H ∈     (by a slight abuse of notation). Let u, v 1 , v 2  ∈ V. 
               
               
                  Then 
               
               
                   
               
               
                     
                   〈     u   ,   v   ,     1   ⋃       〉     ⁢     v   2       =         ❘   &#34;\[LeftBracketingBar]&#34;       u   ⋂     (       v   1     ⋃     v   2       )         ❘   &#34;\[RightBracketingBar]&#34;       =       ❘   &#34;\[LeftBracketingBar]&#34;       u   ⋂     v   1             )     ⋃     (     u   ⋂     v   2       )         ❘   &#34;\[RightBracketingBar]&#34;       =           ❘   &#34;\[LeftBracketingBar]&#34;       (     u   ⋂     v   1       )       ❘   &#34;\[RightBracketingBar]&#34;       +   
       ❘   &#34;\[LeftBracketingBar]&#34;       (     u   ⋂     v   2           ❘   &#34;\[RightBracketingBar]&#34;       -       ❘   &#34;\[LeftBracketingBar]&#34;       u   ⋂     v   1     ⋂     v   2         ❘   &#34;\[RightBracketingBar]&#34;         =       〈     u   ,     v   1       〉     +     〈     u   ,     v   2       〉     -         〈     u   ,     v   1     ,     v   2       〉     3     .             
 
               
               
                   
               
               
                  So by defining F to be 
               
               
                      F(x,y,z) = x+y−z, 
               
               
                  we have 
               
               
                    F(    u, v 1 ),     u, v 2    ,     u, v 1 , v 2     3 ) =     u, v 1  ∪ v 2    . 
               
               
                   Similarly, 
               
               
                   
               
               
                   
           〈     u   ,     v   1     ,       v   2     ⋃     v   3         〉     3     =         ❘   &#34;\[LeftBracketingBar]&#34;       u   ⋂     v   1     ⋂     (       v   2     ⋃     v   3       )         ❘   &#34;\[RightBracketingBar]&#34;       =         ❘   &#34;\[LeftBracketingBar]&#34;         (     u   ⋂     v   1     ⋂     v   2       )     ⋃     (     u   ⋂     v   1     ⋂           ❘   &#34;\[RightBracketingBar]&#34;       =   
           ❘   &#34;\[LeftBracketingBar]&#34;       (     u   ⋂     v   1     ⋂     v   2           ❘   &#34;\[RightBracketingBar]&#34;       +       ❘   &#34;\[LeftBracketingBar]&#34;       (     u   ⋂     v   1     ⋂     v   3           ❘   &#34;\[RightBracketingBar]&#34;       -       ❘   &#34;\[LeftBracketingBar]&#34;       (     u   ⋂     v   1     ⋂     v   2     ⋂     v   3           ❘   &#34;\[RightBracketingBar]&#34;         =       〈     u   ,     v   1     ,     v   2       〉     +   
     〈     u   ,     v   1     ,     v   2       〉     -         〈     u   ,     v   1     ,     v   2     ,     v   3       〉     4     .                 
 
               
               
                   
               
               
                  So 
               
               
                    F(    u, v 1 , v 2     3 ,     u, v 1 , v 3     3 , (   u, v 1 , v 2 , v 3     4 ) =     u, v 1 , v 2  ∪ v 3     3 . 
               
               
                   In similar fashion, we can compute 
               
               
                        u, v 1  ∪ v 2  ∪ . . . ∪ v l     
               
               
                  if we know the values of the k-multilinear forms     w 1 , w 2 , . . . , w k     k  for all 
               
               
                 k ≤ l + 1 and for all w i  ∈ V. 
               
               
                   
               
            
           
         
       
     
     Each device  108  gets shares as c i = u, u i    mod m, where 
     
       
         
         
             
             
         
       
     
     is used to randomly sample u i  ∈ V. Here the vector u is same for each party. 
     The devices  108  also include an MPC based secret reconstruction module  124  that is able to use the shares received from the GAS secret share generator  140 . For each device  108 , the LWE see for GGH15 encoding is computed as S c     i    mod q, where m=ϕ(q). If a device  108 &#39;s input for MPC protocol is b i , then it generates its MPC input as D i •S b     i    mod q. The memory of the device  108  may also include a multiparty computation (MPC) secret constructor  124  that is configured to reconstruct the secret using the shares received from the GAS secret share generator  140  as well as MPC inputs, which are custom c j  values, from other devices  108 . 
     Here the GGH15 scheme is one type of family of multilinear maps, based on the LWE problem with encoding over matrices. A graded encoding scheme for an algebraic “plaintext ring R” provides methods for encoding the ring elements and manipulating the resulting encodings. Such schemes allow a “canonical representation” of the plaintext element to be extracted from its encoding. GGH15 encodes LWE samples in short square matrices of higher dimensions. Addition and multiplication of the encodings corresponds to addition and multiplication of the LWE secrets. The plaintext space is the non-commutative ring of matrices R=   q   n×n . The construction is parametrized by a directed acyclic graph (DAG), G=(V, E), with diameter d. A matrix 
     
       
         
         
             
             
         
       
     
     is associated with each node v ∈ V, and encodings in the scheme are defined relative to the paths in G. A small plaintext matrix S ∈ R is encoded with respect to a path u v via another small matrix D ∈   q   m×m , such that D·A u ≈A v ·S. Given ‘trapdoor information’ τ u  for matrix A u  and error distribution x= , GGH15 generates an encoding D for S with respect to source u and sink v, such that: D·A u =A v ·S+E, where E←(X) m×n  is an LWE error matrix. As the trapdoor information is given for A u  and not A v , the LWE instance {A v , B v (=A v ·S+E)} can still be hard for appropriate parameters. The arithmetic operations are just matrix operations in    q   m×n . It is easy to see that two encodings, D 1  and D 2 , relative to the same path u v can be added, namely from: D 1 ·A u =A v ·S 1 +E 1  and D 2 ·A u =A v ·S 2 +E 2 , we obtain: (D 1 +D 2 )·A u =A v ·(S 1 +S 2 )+E 1 +E 2 , all matrices, S 1 +S 2 , E 1 +E 2  and D 1 +D 2 , are still small. Encodings relative to paths v w and u v, can be multiplied to get an encoding relative to path u w. Namely given D 1 ·A v =A w ·S 1 +E 1  and D 2 ·A u =A v ·S 2 +E 2 , we obtain: D 1 ·D 2 ·A u =D 1 ·(A v ·S 2 +E 2 )=A w ·S 1 ·S 2 +E′, the matrices, D 1 ·D 2 , S 1 ·S 2  and E′ are still small. 
       FIG.  2    illustrates a visual depiction of a secret sharing structure  200  in the manner disclosed herein. Specifically, the secret sharing structure  200  generates shares of a secret S  230  using a trusted party  220 , such as the trusted party  130  disclosed in  FIG.  1   . For example, the shares of the secret S  230 , which may constitute a GAS secret matrix, may be represented by shares S 1 , S 2 , S 3 , etc. Subsequently, the shares S 1 , S 2 , S 3  are distributed to player 1  202 , player 2  204 , and player 3  206 . For example, the player 1  202  may be a first device, the player 2  204  may be a second device, and the player 3  206  may be a third device. 
     In such a secret sharing structure  200 , the secret S may be generated based on the device channel errors of each of the devices  202 ,  204 , and  206 . Furthermore, the device channel errors of these devices  202 ,  204 , and  206  may be based on CIR of the communication channels of these devices  202 ,  204 , and  206 . Thus, the devices  202 ,  204 , and  206  may generate device channel errors e, based on CIR of their individual communication channels and communicate the device channel errors e, to a trusted party  220 . 
     The trusted party  220  may in turn use the errors e to train a linear regression model to generate LWE secrets that can be used to generate the secret S  230 . Specifically, the secret S  230  may be a secret matrix. Subsequently, shares S 1 , S 2 , and S 3  may represent shares for each of the devices  202 ,  204 , and  206  in the secret matrix S  230 . The shares S 1 , S 2 , and S 3  are distributed to the devices. Specifically, the shares S 1 , S 2 , and S 3  are configured such that the general access structure secret matrix S cannot be constructed without shares from an authorized set of the devices  202 ,  204 , and  206 . For example, in one implementation, such authorized set may be at least two of S 1 , S 2 , and S 3 . Alternatively, such authorized set may be a combination of S 1 , S 2 , and S 3  that overcomes a pre-determined threshold. If the combination of the S 1 , S 2 , and S 3  meets the requirements of the authorized set, the reconstructed secret  216  generated from such authorized set may be used for providing access to one or more of the devices  202 ,  204 , and  206 . 
       FIG.  3    illustrates operations  300  for parties to use secret sharing in the manner disclosed herein. One or more of the operations  300  may be implemented by computer instructions stored on a computer readable media where the computer instructions are executable on a computer processor. A determining operation  305  may determine channel impulse responses (CIRs) of device communication channels of various computing devices. Another determining operation  310  uses the CIRs of the device communication channels to generate device channel errors. 
     Subsequently, a training operation  315  may train a linear regression model using device channel errors to generate learning with error (LWE) secrets for each of various computing devices. An operation  320  may generate learning with error (LWE) secrets for each of the various computing devices and an operation  325  may generate a secret matrix based on the LWE secrets from the various computing devices. Subsequently, the shares of the secret matrix to the various computing devices are distributed at an operation  330 . Specifically, the operation  330  may distribute the shares of the secret matrix to the various computing devices based on a multi-party secret sharing protocol, wherein the multi-party secret sharing protocol provides that the secret matrix cannot be constructed without shares from an authorized set of the computing devices. 
     In the above examples, the various modules shown and described with respect to the computing devices (e.g., the communication error detector and correct, hardware error detector and corrector, deterministic error modeler, signature generator, verification module, signature combiner, and broadcaster) may be all be understood as include software stored on a tangible-computer readable storage media. As used herein, “tangible computer-readable storage media” is defined to explicitly excluded carrier waves freely propagating in space and to include memory devices including without limitation RAM, ROM, EEPROM, flash memory or other memory technology, CDROM, digital versatile disks (DVD) or other optical disk storage, magnetic cassettes, magnetic tape, magnetic disk storage or other magnetic storage devices, or any other tangible medium which can be used to store the desired information and which can accessed by mobile device . 
       FIG.  4    illustrates an example processing system  400  that may be useful in implementing the described technology. The processing system  400  is capable of executing a computer program product embodied in a tangible computer-readable storage medium to execute a computer process. Data and program files may be input to the processing system  400 , which reads the files and executes the programs therein using one or more processors (CPUs or GPUs). Some of the elements of a processing system  400  are shown in  FIG.  4    wherein a processor  402  is shown having an input/output (I/O) section  404 , a Central Processing Unit (CPU)  406 , and a memory section  408 . There may be one or more processors  402 , such that the processor  402  of the processing system  400  comprises a single central-processing unit  406 , or a plurality of processing units. The processors may be single core or multi-core processors. The processing system  400  may be a conventional computer, a distributed computer, or any other type of computer. The described technology is optionally implemented in software loaded in memory  408 , a storage unit  412 , and/or communicated via a wired or wireless network link  414  on a carrier signal (e.g., Ethernet, 3G wireless, 8G wireless, LTE (Long Term Evolution)) thereby transforming the processing system  400  in  FIG.  4    to a special purpose machine for implementing the described operations. The processing system  400  may be an application specific processing system configured for supporting a distributed ledger. In other words, the processing system  400  may be a ledger node. 
     The I/O section  404  may be connected to one or more user-interface devices (e.g., a keyboard, a touch-screen display unit  418 , etc.) or a storage unit  412 . Computer program products containing mechanisms to effectuate the systems and methods in accordance with the described technology may reside in the memory section  408  or on the storage unit  412  of such a system  400 . 
     A communication interface  424  is capable of connecting the processing system  400  to an enterprise network via the network link  414 , through which the computer system can receive instructions and data embodied in a carrier wave. When used in a local area networking (LAN) environment, the processing system  400  is connected (by wired connection or wirelessly) to a local network through the communication interface  424 , which is one type of communications device. When used in a wide-area-networking (WAN) environment, the processing system  400  typically includes a modem, a network adapter, or any other type of communications device for establishing communications over the wide area network. In a networked environment, program modules depicted relative to the processing system  400  or portions thereof, may be stored in a remote memory storage device. It is appreciated that the network connections shown are examples of communications devices for and other means of establishing a communications link between the computers may be used. 
     In an example implementation, a user interface software module, a communication interface, an input/output interface module, a ledger node, and other modules may be embodied by instructions stored in memory  408  and/or the storage unit  412  and executed by the processor  402 . Further, local computing systems, remote data sources and/or services, and other associated logic represent firmware, hardware, and/or software, which may be configured to assist in supporting a distributed ledger. A ledger node system may be implemented using a general-purpose computer and specialized software (such as a server executing service software), a special purpose computing system and specialized software (such as a mobile device or network appliance executing service software), or other computing configurations. In addition, keys, device information, identification, configurations, etc. may be stored in the memory  408  and/or the storage unit  412  and executed by the processor  402 . 
     The processing system  400  may be implemented in a device, such as a user device, storage device, IoT device, a desktop, laptop, computing device. The processing system  400  may be a ledger node that executes in a user device or external to a user device. 
     Data storage and/or memory may be embodied by various types of processor-readable storage media, such as hard disc media, a storage array containing multiple storage devices, optical media, solid-state drive technology, ROM, RAM, and other technology. The operations may be implemented processor-executable instructions in firmware, software, hard-wired circuitry, gate array technology and other technologies, whether executed or assisted by a microprocessor, a microprocessor core, a microcontroller, special purpose circuitry, or other processing technologies. It should be understood that a write controller, a storage controller, data write circuitry, data read and recovery circuitry, a sorting module, and other functional modules of a data storage system may include or work in concert with a processor for processing processor-readable instructions for performing a system-implemented process. 
     For purposes of this description and meaning of the claims, the term “memory” means a tangible data storage device, including non-volatile memories (such as flash memory and the like) and volatile memories (such as dynamic random-access memory and the like). The computer instructions either permanently or temporarily reside in the memory, along with other information such as data, virtual mappings, operating systems, applications, and the like that are accessed by a computer processor to perform the desired functionality. The term “memory” expressly does not include a transitory medium such as a carrier signal, but the computer instructions can be transferred to the memory wirelessly. 
     In contrast to tangible computer-readable storage media, intangible computer-readable communication signals may embody computer readable instructions, data structures, program modules or other data resident in a modulated data signal, such as a carrier wave or other signal transport mechanism. The term “modulated data signal” means a signal that has one or more of its characteristics set or changed in such a manner as to encode information in the signal. By way of example, and not limitation, intangible communication signals include wired media such as a wired network or direct-wired connection, and wireless media such as acoustic, RF, infrared and other wireless media. 
     The embodiments of the invention described herein are implemented as logical steps in one or more computer systems. The logical operations of the present invention are implemented (1) as a sequence of processor-implemented steps executing in one or more computer systems and (2) as interconnected machine or circuit modules within one or more computer systems. The implementation is a matter of choice, dependent on the performance requirements of the computer system implementing the invention. Accordingly, the logical operations making up the embodiments of the invention described herein are referred to variously as operations, steps, objects, or modules. Furthermore, it should be understood that logical operations may be performed in any order, unless explicitly claimed otherwise or a specific order is inherently necessitated by the claim language. 
     The above specification, examples, and data provide a complete description of the structure and use of example embodiments of the disclosed technology. Since many embodiments of the disclosed technology can be made without departing from the spirit and scope of the disclosed technology, the disclosed technology resides in the claims hereinafter appended. Furthermore, structural features of the different embodiments may be combined in yet another embodiment without departing from the recited claims.