Privacy-Preserving Computation and Verification of Aggregate Queries on Outsourced Databases学习笔记

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 − o u t − o f − n − s e c r e t − s h a r i n g k-out-of-n-secret-sharing k−out−of−n−secret−sharing scheme。基于的是polynomial interpolation多项式插值。 具体可参见博客 verifiable secret sharing可验证的秘密共享。 any k k k servers can cooperate to determine the answer to an aggregate query, but k − 1 k-1 k−1 cooperating servers cannot.

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