1. 引言

Brian Thompson, Stuart Haber, William G. Horne,Tomas Sander, and Danfeng Yao 2009年论文《Privacy-Preserving Computation and Verification of Aggregate Queries on Outsourced Databases》中主要提出的是支持SUM求和、AVERAGE求平均值的aggregate query操作的outsourced database协议——aggregate queries can be computed without revealing microdata to service providers.

适于的场景如：

• Database-as-a-service（DAS）：support sophisticated queries such as aggregation while simultaneously maintaining the secrecy of microdata(i.e., individual data entries).
• Cross-domain collaborative data analysis：如multiple regional hospitals collaborate to discover the most frequently occurring flu strain of the season in that area.

所用到的关键技术有：

• Shamir’s Secret-Sharing Scheme: a $k-out-of-n-secret-sharing$k−out−of−n−secret−sharing scheme。基于的是polynomial interpolation多项式插值。 具体可参见博客 verifiable secret sharing可验证的秘密共享。
  
  any $k$k servers can cooperate to determine the answer to an aggregate query, but $k-1$k−1 cooperating servers cannot.

• Pedersen Commitment：主要利用了其加法同态属性，有：
  $c_i=C_{r_i}(x_i)=g^{x_i}h^{r_i}\in G_p$ci​=Cri​​(xi​)=gxi​hri​∈Gp​
  尽管不知道每一个$x_i$xi​值，但是it’s easy to compute a commitment to the sum of the unknown values $X=\sum_{i=1}^{m}x_i(\mod p)$X=∑i=1m​xi​(modp)：$\prod_{i=1}^{m}c_i=C_R(X)\in G_p$∏i=1m​ci​=CR​(X)∈Gp​，其中$R=\sum_{i=1}^{m}r_i(\mod p)$R=∑i=1m​ri​(modp)。