How Do Successful Decryptions Leak Secret Keys?

TL;DR

Successful decryptions can leak private-key information because each success excludes secret candidates located within particular spherical caps determined by the query. In high-dimensional lattice schemes, incomplete beta functions, cap-disjointness conditions, overlap formulas, and estimates showing that random query directions are nearly orthogonal can quantify this exclusion and help attackers select queries that improve subsequent failure probabilities.

Transcript

Hello, my name is Han Wu. In this video, I will present a paper entitled More Accurate Geometric Analysis on the Impact of Successful Decryptions for IND-CCA Secure Ring, Mod, LWE, LWR-based schemes. This is a joint work with Guanrong Xu. We are from Shandong University. First, let's start with some background. Majority of lattice-based encryption ... Read More

Key Insights

• Decryption failure is equivalent to the infinity norm of a secret-dependent vector expression exceeding one quarter of the modulus. When secret and ciphertext norms are concentrated in high dimensions, this condition indicates that the coefficient vector of the secret is directionally close to a rotation of the ciphertext-related vector.
• Decryption failures are permitted by many lattice-based encryption schemes as a trade-off between efficiency and security. The paper studies a unified framework covering essential ideas from ring, module, LWE, and LWR-based constructions while accounting for both sampled errors and errors introduced by rounding and reconstruction.
• Failure boosting is a technique that raises the probability of decryption failure by searching for ciphertexts with large norms. Directional failure boosting accelerates this search after one or more failed ciphertexts have been identified, using information revealed by those previous failures to guide subsequent queries.
• A successful decryption excludes possible secret keys because the normalized secret cannot lie within two spherical caps associated with rotations of the query vector. This observation allows successful oracle answers, not only failures, to contribute information that can improve the search for later decryption failures.
• The incomplete beta function accurately characterizes the spherical surface proportion excluded by a single cap. The function can be calculated effectively with software such as MATLAB, giving a more precise measure than an unspecified geometric probability for how many candidate secret directions a successful decryption eliminates.
• Cap overlap determines whether exclusion estimates can be multiplied across successful queries. Positive and negative caps associated with the same query rotation are disjoint, but caps belonging to different rotations can intersect, preventing a general lower bound from simply scaling by the number of successful queries.
• Two-cap disjointness can be checked through equivalent conditions involving their angle, distance, or inner product. If the angle between cap centers exceeds twice the cap angle, the caps are disjoint, while intermediate angles require an explicit calculation of the intersecting surface area.
• Random normalized queries in high-dimensional spaces are nearly orthogonal with high probability. The paper bounds their angular deviation from one half of pi using a parameter-dependent epsilon, then compares that range with the spherical-cap angle to predict whether query caps are disjoint or overlapping.

Questions & Answers

Q: How can successful decryptions leak private-key information?

A successful decryption shows that the normalized coefficient vector of the secret does not belong to two spherical caps centered around rotations of the query vector. This removes every candidate secret direction inside those regions. Repeating successful queries can therefore shrink the set of plausible keys, especially when the associated caps are disjoint or their overlaps can be measured accurately.

Q: What condition causes a decryption failure in the unified lattice framework?

For fixed values representing the secret-related matrix, ciphertext-related vector, and combined error, decryption fails if and only if the infinity norm of the transpose of the secret-related matrix multiplied by the ciphertext-related vector, plus the error term, exceeds one quarter of the modulus. In high dimensions, this condition also reflects directional closeness between the relevant coefficient vectors.

Q: What is failure boosting in lattice-based encryption attacks?

Failure boosting increases the decryption-failure rate by searching for ciphertexts whose norms are large. Directional failure boosting extends that approach after one or more failed ciphertexts have been found, using their directional information to accelerate the search for further failures. Related attacks either use failures to produce more failures or use them to recover a secret or error vector.

Q: Why are spherical caps useful for analyzing successful decryption queries?

Spherical caps provide a geometric representation of secret directions that are inconsistent with a successful oracle response. A successful query excludes the normalized secret from two caps associated with rotations of the query. Measuring the caps and their intersections therefore measures how much of the candidate-key space has been eliminated and how useful the success is for future failure boosting.

Q: How is the proportion excluded by one spherical cap calculated?

The paper characterizes the cap's spherical surface proportion with an incomplete beta function, drawing on results from Lee. This function can be evaluated effectively with software such as MATLAB. The resulting proportion represents the share of candidate normalized secret directions excluded by a single cap, subject to the paper's assumptions about the norms of queries and secrets.

Q: When can exclusions from multiple successful queries be added directly?

Exclusions can be added directly when the corresponding spherical caps are completely disjoint. The paper provides equivalent tests based on the angle, distance, and inner product between cap centers, allowing an attacker to check this property. When disjointness holds, the surface proportion of each cap can be multiplied by the number of caps to estimate total excluded candidates.

Q: How does the analysis handle intersecting spherical caps?

When the angle between two cap centers is greater than the cap angle but smaller than twice that angle, the caps may intersect. The paper supplies formulas for calculating the surface area of their intersection and then derives the total proportion covered by the two caps. This prevents overlapping candidates from being counted twice in the exclusion estimate.

Q: Why are random query vectors treated as nearly orthogonal?

In the chosen-ciphertext setting described, queries arise from hash-function calls and can be modeled, after normalization, as uniform random points on a high-dimensional sphere. The paper applies a precise high-dimensional orthogonality result to bound how far the angle between two queries deviates from one half of pi, with probability at least one minus one over two to the security parameter.

Summary & Key Takeaways

• Many ring, module, LWE, and LWR-based encryption schemes permit small decryption-failure probabilities as an efficiency and security trade-off. Under the paper's unified framework, failure occurs exactly when the infinity norm of a combination involving the secret, ciphertext-related values, and errors exceeds one quarter of the modulus, linking failures to vector directions.

• Earlier failure-boosting methods searched for large-norm ciphertexts and later used known failures to find additional failures or recover secret information. Bandele and Shank instead observed that successful oracle responses also reveal information: a success shows that the normalized secret lies outside two spherical caps centered around rotations of the normalized query direction.

• The paper quantifies the excluded surface using an incomplete beta function, provides equivalent angle, distance, and inner-product tests for disjoint caps, and calculates pairwise intersections when caps overlap. A high-dimensional random-angle estimate then predicts whether query caps are probably disjoint or intersecting, enabling more accurate measurements of eliminated key candidates.