What Changed
Two witness encryption constructions, the affine determinant program (ADP) and its arithmetic extension (AADP), have been compromised. Attacks can now recover encrypted messages directly from public ciphertexts without needing a secret key or valid witness. These attacks exploit a fundamental weakness: reliance on heuristic security arguments instead of proven security reductions.
The first attack uses basic linear algebra on commutators from public ciphertext matrices. In sparse circuits, these commutators show low rank, allowing direct message recovery. The second attack linearizes the nearly-skew-symmetric variant of ADP, extracting both the encryption randomness and the plaintext. Both attacks have been verified in practice.
Key Findings
Heuristic security arguments create exploitable gaps. ADP and AADP schemes base their security on assumed rank properties of structured matrices. Without formal security reductions linking these properties to well-known hard problems, the constructions are vulnerable to attacks that identify unforeseen structural patterns. Your encryption vendor's claim that "no known attacks exist" doesn't mean "provably secure."
Sparse circuits amplify structural weaknesses. These schemes were designed for efficient witness encryption in sparse circuits, precisely where the commutator rank vulnerability is exploitable. The more practical the deployment, the more exposed the weakness. This creates a situation where optimizing for real-world use introduces an attack vector.
Ciphertext structure leaks information. The attacks don't require brute force or quantum computing. They use standard linear algebra techniques on publicly available ciphertext matrices. If your encryption scheme exposes structured mathematical objects as part of the ciphertext, those structures become attack surfaces. Smaller, more efficient ciphertexts can reveal more information through algebraic manipulation.
Identity-based and attribute-based encryption systems face similar risks. Efficient witness encryption enables these systems, often used in payment processing for access control and data compartmentalization. If the underlying witness encryption is compromised, the security of the systems built on top collapses. Your attribute-based access controls for cardholder data environments may rely on cryptographic primitives with unproven security foundations.
Verification of attacks in practice eliminates theoretical uncertainty. Both attacks have been implemented and tested. This isn't a theoretical vulnerability needing impractical resources or idealized conditions. The gap between "potentially vulnerable" and "demonstrably broken" has closed.
What This Means for Your Team
If you're using encryption systems claiming efficiency gains through novel constructions, audit the security foundations. PCI DSS Requirement 3.5.1 mandates cryptographic key management, but it doesn't specify which encryption schemes are acceptable. You're responsible for ensuring the cryptographic primitives protecting cardholder data rest on solid mathematical foundations.
The ADP and AADP failures illustrate a broader pattern: efficiency optimizations in cryptography often trade proven security for assumed security. When a vendor offers smaller ciphertexts, faster encryption, or more flexible access controls through a "novel approach," ask what security reduction supports it. If the answer involves phrases like "believed to be secure" or "no known attacks," you're accepting heuristic security.
For compliance teams, this creates a documentation problem. Your risk assessment should identify which encryption schemes protect cardholder data and whether those schemes rely on security reductions or heuristic arguments. If you're using attribute-based encryption for PAN access controls, verify the underlying witness encryption construction. If you can't trace the security claim to a formal reduction, document that gap in your risk register.
Action Items by Priority
Immediate: Inventory encryption schemes in your cardholder data environment. List every system that encrypts, tokenizes, or protects PANs. For each system, identify the specific cryptographic primitives used. Don't accept vendor claims of "military-grade encryption" or "bank-level security", get the algorithm names and construction details. If your vendor can't or won't provide this information, that's a red flag for your QSA.
Within 30 days: Classify schemes by security foundation. Separate your encryption inventory into two categories: schemes with formal security reductions to well-studied hard problems (like RSA's reduction to integer factorization or AES's resistance to known attacks), and schemes with heuristic security arguments. The second category requires heightened monitoring. If you're using witness encryption, identity-based encryption, or attribute-based encryption, determine whether the construction has published security proofs.
Within 60 days: Establish a cryptographic review process for new systems. Before deploying any new encryption scheme in your cardholder data environment, require documentation of its security foundation. Your review should ask: What hard problem is this reduced to? Has the reduction been peer-reviewed? Are there known attacks against similar constructions? This process should be mandatory for any system touching PANs, not optional.
Ongoing: Monitor cryptographic research for breaks. Subscribe to ePrint archives and cryptography conference proceedings. When attacks are published against schemes you use, assess impact within 48 hours. The ADP and AADP attacks were published in academic papers, if you're using these constructions (or systems built on them), you need to know immediately. Your incident response plan should include a cryptographic break scenario.
Strategic: Prefer conservative cryptographic choices for cardholder data. When you have a choice between a novel, efficient scheme with heuristic security and an established scheme with proven security reductions, choose the established option for PAN protection. Save the experimental cryptography for non-sensitive data. PCI DSS doesn't require you to use the newest or fastest encryption, it requires you to protect cardholder data effectively.
