Fuzzy Query on Encrypted Phone Numbers: 5 Solutions & Production Java Implementation
This article compares five technical approaches for fuzzy querying encrypted phone numbers, detailing the industry-standard prefix/suffix hash indexing and 3-gram fragment indexing with complete Java implementations using AES-256-GCM and HMAC-SHA256, covering database schema, security hardening, production challenges, and interview strategies.
Problem Statement
The core conflict is between data security (encrypted storage to prevent data breaches) and query efficiency (fuzzy matching like 138****1234 or *1234). Direct decryption of the entire table causes performance disasters (million-row query timeouts) and security risks (frequent decryption of sensitive data).
Comparison of Five Mainstream Solutions
1. Prefix/Suffix Hash Indexing (Recommended, 95%+ adoption in big tech)
Pre-compute salted hashes of all possible prefixes (first 3 to 11 digits) and suffixes (last 1 to 4 digits), store in a separate index table. Query matches the hash index first, then joins the main table for the encrypted full phone number. Supports prefix and suffix matching; high security, extremely fast query, medium storage overhead.
2. Elasticsearch Field-Level Encryption (30% adoption)
Use ES native field-level encryption with fuzzy queries. Supports arbitrary fuzzy matching; medium security and performance, medium storage. Requires careful key management and isolation of sensitive data.
3. N-Gram Tokenization Hashing (<5% adoption)
Build hash indexes on continuous n-gram tokens. Supports arbitrary fuzzy matching but suffers from slow writes, extremely high storage overhead, and medium security.
4. Order-Preserving Encryption (OPE) (Rarely used)
Encryption preserves plaintext order, enabling range queries. Low security, slow performance, low storage overhead.
5. Fully Homomorphic Encryption (FHE) (Theoretical stage)
Compute directly on ciphertext. Extremely high security but extremely slow performance; not practical for production.
Deep Dive: Prefix/Suffix Hash Indexing (Big Tech Standard)
Core Design
Pre-calculate salted hashes for every possible prefix (length 3–11) and suffix (length 1–4) of the 11-digit phone number. Store these hashes in a dedicated index table with columns: user_id, hash_type (1=prefix, 2=suffix), hash_length, hash_value (SHA-256 salted hash). A unique key on ( user_id, hash_type, hash_length) and a composite index on ( hash_type, hash_length, hash_value) enable fast equality lookups.
Database Schema
-- Main user table (stores AES-256-GCM encrypted full phone number)
CREATE TABLE user (
id BIGINT PRIMARY KEY AUTO_INCREMENT,
phone_encrypted VARCHAR(64) NOT NULL COMMENT 'AES-256-GCM encrypted full phone number (Base64)',
create_time DATETIME NOT NULL DEFAULT CURRENT_TIMESTAMP
);
-- Phone hash index table (stores only hashes, no plaintext)
CREATE TABLE phone_hash_index (
id BIGINT PRIMARY KEY AUTO_INCREMENT,
user_id BIGINT NOT NULL COMMENT 'Foreign key to user',
hash_type TINYINT NOT NULL COMMENT '1:prefix 2:suffix',
hash_length TINYINT NOT NULL COMMENT 'Length of plaintext segment',
hash_value CHAR(64) NOT NULL COMMENT 'SHA-256 salted hash',
UNIQUE KEY uk_user_hash (user_id, hash_type, hash_length),
KEY idx_hash_query (hash_type, hash_length, hash_value)
);Write Process
Encrypt the full phone number with AES-256-GCM (random 12-byte IV, 128-bit auth tag) and insert into user table, obtaining user_id.
For each prefix length 3 to 11: extract prefix, compute SHA-256(prefix + GLOBAL_SALT), add to batch.
For each suffix length 1 to 4: extract suffix, compute SHA-256(suffix + GLOBAL_SALT), add to batch.
Batch insert all hash records into phone_hash_index using JDBC batchUpdate with rewriteBatchedStatements=true for 10x performance gain. Wrap in a local transaction for atomicity.
Query Process (Example: suffix "1234")
Compute hash = SHA-256("1234" + GLOBAL_SALT).
Query index table:
SELECT user_id FROM phone_hash_index WHERE hash_type=2 AND hash_length=4 AND hash_value=?.
Fetch encrypted phone numbers from user table for the returned user_id list.
Decrypt each with AES-256-GCM, mask as 138****1234, return masked results.
Key Security Optimizations
Mandatory salting: hash_value = SHA-256(phone_part + GLOBAL_SALT); salt sourced from KMS, prevents rainbow tables.
Strong hash only: Use SHA-256 or above; never MD5 or SHA-1.
Index table isolation: Store hash index in a separate database/shard from main table to reduce breach impact.
Rate limiting: Limit query API to 10 requests/minute per IP; block unlimited batch queries.
Special Scenarios
Middle Fuzzy Query (e.g., "380")
Not recommended for technical implementation. Mitigate via product design: guide users to provide first 3 + last 4 digits; restrict middle fuzzy queries to internal admin systems with strict RBAC and audit logs.
Existing Elasticsearch Full-Text Search
Enable ES field-level encryption (not transport encryption), store only phone numbers in ES, rotate ES encryption keys regularly.
Interview Bonus Points
Articulate the core trade-off: security vs. performance balance, not technical perfection.
Recommend battle-tested big-tech solutions over cutting-edge but immature ones.
Address security details: salting, hash algorithm choice, brute-force protection.
Show product thinking: know when to replace a technical solution with a product design change.
Core Java Implementation
1. AES-256-GCM Encryptor (Authenticated Encryption)
@Component
public class AesEncryptor {
private static final String AES_KEY = "your-256-bit-aes-key-from-kms";
private static final int GCM_IV_LENGTH = 12;
private static final int GCM_TAG_LENGTH = 128;
public String encrypt(String plaintext) throws Exception {
SecretKeySpec keySpec = new SecretKeySpec(AES_KEY.getBytes(), "AES");
Cipher cipher = Cipher.getInstance("AES/GCM/NoPadding");
byte[] iv = new byte[GCM_IV_LENGTH];
new SecureRandom().nextBytes(iv);
GCMParameterSpec gcmSpec = new GCMParameterSpec(GCM_TAG_LENGTH, iv);
cipher.init(Cipher.ENCRYPT_MODE, keySpec, gcmSpec);
byte[] ciphertext = cipher.doFinal(plaintext.getBytes());
byte[] result = new byte[GCM_IV_LENGTH + ciphertext.length];
System.arraycopy(iv, 0, result, 0, GCM_IV_LENGTH);
System.arraycopy(ciphertext, 0, result, GCM_IV_LENGTH, ciphertext.length);
return Base64.getEncoder().encodeToString(result);
}
public String decrypt(String ciphertextBase64) throws Exception {
byte[] ciphertext = Base64.getDecoder().decode(ciphertextBase64);
SecretKeySpec keySpec = new SecretKeySpec(AES_KEY.getBytes(), "AES");
Cipher cipher = Cipher.getInstance("AES/GCM/NoPadding");
byte[] iv = new byte[GCM_IV_LENGTH];
System.arraycopy(ciphertext, 0, iv, 0, GCM_IV_LENGTH);
GCMParameterSpec gcmSpec = new GCMParameterSpec(GCM_TAG_LENGTH, iv);
cipher.init(Cipher.DECRYPT_MODE, keySpec, gcmSpec);
byte[] plaintext = cipher.doFinal(ciphertext, GCM_IV_LENGTH, ciphertext.length - GCM_IV_LENGTH);
return new String(plaintext);
}
}Technical highlights: AES-256-GCM provides confidentiality and integrity; random IV per encryption; key from KMS, never hardcoded; output includes IV + ciphertext + auth tag.
2. SHA-256 Salted Hash Utility
@Component
public class HashUtil {
private static final String GLOBAL_SALT = "your-global-salt-from-kms-32bit+";
public String sha256(String plaintext, String userSalt) {
try {
MessageDigest digest = MessageDigest.getInstance("SHA-256");
byte[] hash = digest.digest((plaintext + GLOBAL_SALT + userSalt).getBytes());
StringBuilder hexString = new StringBuilder();
for (byte b : hash) {
String hex = Integer.toHexString(0xff & b);
if (hex.length() == 1) hexString.append('0');
hexString.append(hex);
}
return hexString.toString();
} catch (Exception e) {
throw new RuntimeException("SHA-256 calculation failed", e);
}
}
public String sha256(String plaintext) {
return sha256(plaintext, "");
}
}Highlights: SHA-256 strong collision resistance; global salt + optional user salt double-salting; thread-safe MessageDigest usage.
3. User Write Service (Batch Insert Optimization)
@Service
public class UserService {
private final JdbcTemplate jdbcTemplate;
private final AesEncryptor aesEncryptor;
private final HashUtil hashUtil;
@Transactional(rollbackFor = Exception.class)
public void createUser(String phone) throws Exception {
String encryptedPhone = aesEncryptor.encrypt(phone);
Long userId = jdbcTemplate.queryForObject(
"INSERT INTO user (phone_encrypted) VALUES (?)", Long.class, encryptedPhone);
List<HashIndex> hashIndices = new ArrayList<>();
for (int i = 3; i <= 11; i++) {
String prefix = phone.substring(0, i);
String hash = hashUtil.sha256(prefix);
hashIndices.add(new HashIndex(userId, (byte)1, (byte)i, hash));
}
for (int i = 1; i <= 4; i++) {
String suffix = phone.substring(11 - i);
String hash = hashUtil.sha256(suffix);
hashIndices.add(new HashIndex(userId, (byte)2, (byte)i, hash));
}
batchInsertHashIndices(hashIndices);
}
private void batchInsertHashIndices(List<HashIndex> indices) {
String sql = "INSERT INTO phone_hash_index (user_id, hash_type, hash_length, hash_value) VALUES (?, ?, ?, ?)";
jdbcTemplate.batchUpdate(sql, new BatchPreparedStatementSetter() {
@Override
public void setValues(PreparedStatement ps, int i) throws SQLException {
HashIndex index = indices.get(i);
ps.setLong(1, index.getUserId());
ps.setByte(2, index.getHashType());
ps.setByte(3, index.getHashLength());
ps.setString(4, index.getHashValue());
}
@Override
public int getBatchSize() { return indices.size(); }
});
}
private static class HashIndex {
private Long userId; private Byte hashType; private Byte hashLength; private String hashValue;
// constructor, getters omitted
}
}Highlights: JDBC batch insert with rewriteBatchedStatements=true for 10x throughput; local transaction ensures atomicity between main and index tables; pre-computes all hashes in memory to minimize DB round-trips.
4. Fuzzy Query Service
@Service
public class PhoneQueryService {
private final JdbcTemplate jdbcTemplate;
private final AesEncryptor aesEncryptor;
private final HashUtil hashUtil;
public List<String> queryBySuffix(String suffix) throws Exception {
if (suffix.length() != 4) throw new IllegalArgumentException("Suffix must be 4 digits");
String hash = hashUtil.sha256(suffix);
List<Long> userIds = jdbcTemplate.queryForList(
"SELECT user_id FROM phone_hash_index WHERE hash_type=2 AND hash_length=4 AND hash_value=?",
Long.class, hash);
if (userIds.isEmpty()) return new ArrayList<>();
String placeholders = String.join(",", Collections.nCopies(userIds.size(), "?"));
List<String> encryptedPhones = jdbcTemplate.queryForList(
"SELECT phone_encrypted FROM user WHERE id IN (" + placeholders + ")",
String.class, userIds.toArray());
List<String> result = new ArrayList<>();
for (String encryptedPhone : encryptedPhones) {
String plainPhone = aesEncryptor.decrypt(encryptedPhone);
String maskedPhone = plainPhone.substring(0, 3) + "****" + plainPhone.substring(7);
result.add(maskedPhone);
}
return result;
}
}Highlights: Prepared statements prevent SQL injection; index-first lookup avoids full-table scan and decryption; decryption only on tiny candidate set; masked output prevents plaintext leakage.
Production Challenges & Big-Tech Solutions
Hash Collision Risk
Solution: SHA-256 + 32+ byte salt; unique constraint uk_user_hash; on collision detection, append random suffix and re-hash. WeChat Pay practice: collision probability below 1e-18, zero collisions in 10 years.
Main/Index Table Consistency
Solution: Same database: local transaction. Cross-database: transactional messages (RocketMQ) + retry + nightly reconciliation job. Alibaba practice: RocketMQ transactional messages + scheduled reconciliation, inconsistency rate < 0.0001%.
Sharded Query Routing
Solution: Shard by user_id; use Sharding-JDBC to broadcast query to all shards' hash indexes; parallel execution with 100ms timeout. Meituan practice: parallel query across 32 shards, avg 50ms latency.
Salt/Key Leakage Emergency
Solution: Rotate keys every 90 days; 30-day dual-key compatibility period; immediate re-encryption job on leak. ByteDance practice: automatic 90-day rotation, 30-day overlap, zero-downtime switch.
Bulk Historical Data Migration
Solution: Canal for incremental sync; batch migrate historical data (1000 rows/batch); gray-scale traffic switch with rollback plan. Tencent practice: Canal + DataX for zero-downtime migration.
Brute-Force Protection
Solution: Rate limit: 10 req/min/IP, 50 req/day/user; CAPTCHA/SMS verification; lock account after 5 consecutive failures for 1 hour. Alipay practice: multi-layer risk control on sensitive query APIs, manual review for anomalies.
Alternative Approach: 3-gram Fragment Indexing with HMAC (Interview Deep-Dive)
For arbitrary substring matching (e.g., "138" anywhere), use a sliding window of 3 digits (3-gram) over the 11-digit phone number, producing 9 fragments. Compute HMAC-SHA256(fragment, secret_key) for each fragment, store in phone_fragment_index with user_id, fragment_hash, fragment_pos (starting position). Composite index on ( fragment_hash, fragment_pos).
Write: Build Fragment Index
private static final int GRAM_SIZE = 3;
private static final String HMAC_ALG = "HmacSHA256";
private static final int PHONE_LEN = 11;
public List<PhoneFragmentIndex> buildFragmentIndex(String phone, Long userId) {
List<PhoneFragmentIndex> result = new ArrayList<>();
for (int i = 0; i <= PHONE_LEN - GRAM_SIZE; i++) {
String fragment = phone.substring(i, i + GRAM_SIZE);
String hash = hmacHash(fragment);
result.add(new PhoneFragmentIndex(userId, hash, i));
}
return result;
}
private String hmacHash(String data) {
try {
Mac mac = Mac.getInstance(HMAC_ALG);
SecretKeySpec keySpec = new SecretKeySpec(SECRET_KEY.getBytes(), HMAC_ALG);
mac.init(keySpec);
byte[] raw = mac.doFinal(data.getBytes(StandardCharsets.UTF_8));
return Base64.getEncoder().encodeToString(raw);
} catch (Exception e) {
throw new RuntimeException("HMAC calculation failed", e);
}
}Query: Search Encrypted Phones
public List<String> searchEncryptedPhones(String keyword) {
if (keyword.length() < GRAM_SIZE) throw new IllegalArgumentException("Keyword must be at least " + GRAM_SIZE + " digits");
List<String> keywordFragments = new ArrayList<>();
for (int i = 0; i <= keyword.length() - GRAM_SIZE; i++) {
keywordFragments.add(hmacHash(keyword.substring(i, i + GRAM_SIZE)));
}
if (!bloomFilter.mightContainAll(keywordFragments)) return Collections.emptyList();
List<Long> candidateUserIds = fragmentIndexMapper.selectUserIdsByHashes(keywordFragments);
return decryptAndVerify(candidateUserIds, keyword);
}
private List<String> decryptAndVerify(List<Long> userIds, String keyword) {
List<String> matchedEncrypted = new ArrayList<>();
for (Long uid : userIds) {
String encryptedPhone = userMapper.getEncryptedPhone(uid);
String plainPhone = aesDecryptor.decrypt(encryptedPhone);
if (plainPhone.contains(keyword)) matchedEncrypted.add(encryptedPhone);
}
return matchedEncrypted;
}Highlights: Bloom filter in Redis blocks non-existent queries instantly; final decryption verification eliminates hash collisions; returns ciphertext to avoid plaintext exposure.
Mapper SQL (MyBatis)
@Mapper
public interface FragmentIndexMapper {
@Select("<script>"
+ "SELECT user_id, COUNT(*) AS cnt "
+ "FROM phone_fragment_index "
+ "WHERE fragment_hash IN "
+ "<foreach item='hash' collection='hashes' open='(' separator=',' close=')'>"
+ " #{hash}"
+ "</foreach>"
+ "GROUP BY user_id "
+ "HAVING cnt >= #{minMatch} "
+ "</script>")
List<Long> selectUserIdsByHashes(@Param("hashes") List<String> hashes, @Param("minMatch") int minMatch);
}Security & Operations
Rainbow table defense: HMAC mixes secret key into hash; key stored in KMS/config center, not in code.
Key rotation: Offline recompute new index table, verify, switch config, retire old table after 30-day overlap.
Bloom filter: Reduces useless DB hits on massive datasets.
Limitations
Naturally supports arbitrary substring containment (including middle and suffix patterns).
Requires search keyword length ≥ gram size (typically 3). Shorter input must be rejected or fall back to prefix match with decryption verification.
Summary
The engineering sweet spot for fuzzy querying encrypted phone numbers is one-way hash searchable indexes + Bloom filter noise reduction + tail decryption verification . This balances security, performance, and cost: the prefix/suffix hash method covers 95% of business needs with minimal storage and latency; the 3-gram HMAC fragment index handles arbitrary substring search at the cost of larger index size and a minimum keyword length. Both approaches keep plaintext out of indexes, use strong cryptographic primitives (AES-256-GCM, SHA-256/HMAC-SHA256), manage keys via KMS with rotation, and protect against brute-force via rate limiting and Bloom filters. The provided Java code and SQL are production-ready patterns used at WeChat Pay, Alibaba, Meituan, ByteDance, Tencent, and Alipay.
Signed-in readers can open the original source through BestHub's protected redirect.
This article has been distilled and summarized from source material, then republished for learning and reference. If you believe it infringes your rights, please contactand we will review it promptly.
How this landed with the community
Was this worth your time?
0 Comments
Thoughtful readers leave field notes, pushback, and hard-won operational detail here.
