如何在云计算环境中实现加密数据的高效范围查询

Here's a detailed, structured breakdown of the approach to implement efficient range queries on encrypted data in a semi-trusted cloud environment—this tackles the core challenge of processing encrypted data without exposing sensitive plaintext values.

Problem Context #

We aim to enable efficient range queries on encrypted data stored in the cloud. A key hurdle here is processing this encrypted data on a semi-trusted server, where we need to ensure plaintext values stay hidden while still getting accurate query outcomes.

Algorithm Inputs #

• Processing key: gpt
• Encrypted key: [xi] = Cxi
• Scenario-specific input pairs:
  • Scenario 1: [a] = Ca, [y] = Cy
  • Scenario 2: [b] = Cb, [y] = Cy

Algorithm Output #

A binary result indicating the comparison outcome:

• 1: Represents the result is >=
• 0: Represents the result is <

Step-by-Step Execution #

First, a universal preprocessing step applies to both scenarios:

1. Compute the combined encrypted value:
   Cx = Cxi * Cy = g^{s(xi+y)} * h^{ry+ri}

Scenario 1: Query with [a] = Ca and [y] = Cy #

2. Calculate the pairing-based value:
   Xi = e(Ca * Cx ; gpt) = e(g; g)^{pst(s+a(xi+y))}
3. Generate the hash of this value: H(Xi)
4. Check membership of H(Xi) in the predefined set H:
   • If H(Xi) is in H: Return 0 (interpretation: a < (xi + y))
   • If H(Xi) is not in H: Return 1 (interpretation: a >= (xi + y))

Scenario 2: Query with [b] = Cb and [y] = Cy #

2. Calculate the pairing-based value:
   Xi = e(Cb * Cx ; gpt) = e(g; g)^{pst(s+b(xi+y))}
3. Generate the hash of this value: H(Xi)
4. Check membership of H(Xi) in the predefined set H:
   • If H(Xi) is in H: Return 0 (interpretation: b < (xi + y))
   • If H(Xi) is not in H: Return 1 (interpretation: b >= (xi + y))

内容的提问来源于stack exchange，提问作者Boluwatife