Anastasia: Cinderella's Stepsister Turning Shabby X.509 Certificates into Elegant Anonymous Key Attestations

Anastasia: Cinderella's Stepsister Turning Shabby X.509 Certificates into Elegant Anonymous Key Attestations Dan Yamamoto (Internet Initiative Japan Inc.) / Katsuyoshi Ozaki (DataSign Inc.) Keisuke Hasegawa (SECOM Intelligent Systems Laboratory) / Kazue Sako (Waseda University) IIW41 / October 21, 2025

Digital Identity Wallet Issuer Verifier Wallet n Name n IsOver21 Credential Presentation n n IsOver21 1

with Device Binding Issuer Wallet n Name n IsOver21 n 𝑑𝑝𝑘 Verifier 𝑑𝑠𝑘 𝑑𝑝𝑘 Credential n Signed nonce verifiable with 𝑑𝑝𝑘 PoP Presentation n n IsOver21 n 𝑑𝑝𝑘 𝑑𝑠𝑘: device private key, 𝑑𝑝𝑘: device public key 2

with Key Attestation Attestation CA X.509 Certs for Key Attestation Issuer n “𝑑𝑝𝑘 is in a secure device” Wallet n Name n IsOver21 n 𝑑𝑝𝑘 Verifier 𝑑𝑠𝑘 𝑑𝑝𝑘 Credential n Signed nonce verifiable with 𝑑𝑝𝑘 PoP Presentation n n IsOver21 n 𝑑𝑝𝑘 𝑑𝑠𝑘: device private key, 𝑑𝑝𝑘: device public key 3

Example: Android Key Attestation Certificate Chain Root Cert CA Cert 1 CA Cert 2 CA Cert 3 EE Cert Algorithm: RSA4096 Algorithm: RSA4096 Algorithm: ES384 Algorithm: ES256 Algorithm: ES256 Issuer: Key Attestation CA Issuer: Key Attestation CA Issuer: Google Droid CA2 Issuer: Google Droid CA3 Issuer: StrongBox Subject: Key Attestation CA Subject: Google Droid CA2 Subject: Google Droid CA3 Subject: StrongBox Subject: Android Keystore Key Validity: 2022-03-20 -- 2042-03-15 Validity: 2022-01-26 -- 2037-01-22 Validity: 2025-10-07 -- 2025-12-16 Validity: 2025-10-06 -- 2025-10-31 Validity: 1970-01-01 -- 2048-01-01 Subject Public Key: 𝑝𝑘! Subject Public Key: 𝑝𝑘" Subject Public Key: 𝑝𝑘# Subject Public Key: 𝑝𝑘$ Subject Public Key: 𝑝𝑘% == device PK Signature: 𝜎! Signature: 𝜎" Signature: 𝜎# Signature: 𝜎$ Signature: 𝜎% 4

5

Challenge: Unlinkable Key Attestation with X.509 n X.509 certificates consist of many correlating factors: lSerial number lValidity period (exact datetime) lSubject public key lSignature value lKey identifiers lExtended attributes for attestation, (e.g., Boot key hash) n … But they do not support selective disclosure or range proofs n Do not provide unlinkability 6

Prior Work: Cinderella n Microsoft Research (Presented at IEEE S&P 2016) n Use zk-SNARKs (Pinocchio) to anonymize RSA-based X.509 certificates n 👍 Tiny proofs (288 B) & fast verification (milliseconds) → verifier-friendly n 👍 “Parse outside, re-serialize inside” design → efficient circuits n 👍 Support proof of OCSP-stapling for revocation n 😢 Huge parameters (GB-scale) & non-universal trusted setup n 😢 Proof generation takes hundreds of seconds → not suitable for mobile devices 7

Cinderella in an ETSI Techinical Report One immediate issue is proving performance. Since the resulting Cinderella pseudo-certificates can take up to 9 minutes to generate for complex policies on a computer, it is recommended that they are generated offline and refreshed typically on a daily basis. … Yet, progress in zk-SNARK proving performance - e.g. lookup table with PLONKish arithmetization, assembly provers for mobile platforms, and tolerance of "bigger" proofs (hundreds of kilobytes) would arguably make a reimplementation of Cinderella practical on mobile phones 8

Our Proposal Anastasia: Cinderella's Stepsister Turning X.509 Certificates into Pseudonymous Key Attestations n Pseudonymous key attestation: an attestation scheme that verifies a device key as genuine while keeping it unlinkable to the device’s real-world identity n Built upon the Cinderella approach, enabling on-device execution on smartphones: l Uses UltraHonk (a PLONKish scheme) instead of Pinocchio to reduce prover computation cost l Prevents memory overflow by concatenating per-certificate proofs instead of generating a single chain-wide proof l Leverages zk-DSL Noir for circuit design, enabling developer-friendly circuit implementation and maintenance, and integrates with Mopro for seamless mobile deployment n Performance: Generates a two-level chain proof (CA → EE; ES256) in about 30 seconds on an Android device (Google Pixel 9a) 9

Example: Pseudonymous Android Key Attestations Root Cert CA Cert 1 CA Cert 2 CA Cert 3 EE Cert Algorithm: RSA4096 Algorithm: RSA4096 Algorithm: ES384 Algorithm: ES256 Algorithm: ES256 Issuer: Key Attestation CA Issuer: Key Attestation CA Issuer: Google Droid CA2 Issuer: Google Droid CA3 Issuer: StrongBox Subject: Key Attestation CA Subject: Google Droid CA2 Subject: Google Droid CA3 Subject: StrongBox Subject: Android Keystore Key Validity: 2022-03-20 -- 2042-03-15 Validity: 2022-01-26 -- 2037-01-22 Validity: 2025-10-07 -- 2025-12-16 Validity: 2025-10-06 -- 2025-10-31 Validity: 1970-01-01 -- 2048-01-01 Subject Public Key: 𝑝𝑘! Subject Public Key: 𝑝𝑘" Subject Public Key: 𝑝𝑘# Subject Public Key: 𝑝𝑘$ Subject Public Key: 𝑝𝑘% 𝑛𝑦𝑚 Signature: 𝜎! Signature: 𝜎" Signature: 𝜎# Signature: 𝜎$ Signature: 𝜎% 10

Current Implementation Root Cert CA Cert 1 CA Cert 2 CA Cert 3 EE Cert Algorithm: RSA4096 Algorithm: RSA4096 Algorithm: ES384 Algorithm: ES256 Algorithm: ES256 Issuer: Key Attestation CA Issuer: Key Attestation CA Issuer: Google Droid CA2 Issuer: Google Droid CA3 Issuer: StrongBox Subject: Not supported Subject: Key Attestation CA Google Droid CA2 Subject: Google Droid CA3 Subject: StrongBox Subject: Android Keystore Key -- 2042-03-15 -- 2037-01-22 Validity: 2025-10-07 -- 2025-12-16 Validity: 2025-10-06 -- 2025-10-31 Validity: 1970-01-01 -- 2048-01-01 Subject Public Key: 𝑝𝑘! Subject Public Key: 𝑝𝑘" Subject Public Key: 𝑝𝑘# Subject Public Key: 𝑝𝑘$ Subject Public Key: 𝑝𝑘% 𝑛𝑦𝑚 Signature: 𝜎! Signature: 𝜎" Signature: 𝜎# Signature: 𝜎$ Signature: 𝜎% (Our ZK circuit currently supports only ES256 Validity: Validity: 2022-03-20anonymization) 2022-01-26 11

Demo 1. Generate a key pair and X.509 certificate chain on Android 2. Prove the validity of attestation certificates on Android 3. Verify proof on Web verifier 12

ZK Circuits 13

Summary and Future Works Summary n We design Anastasia, a system that transforms X.509 certificate chains into anonymous key attestations using ZKP, building upon Microsoft’s Cinderella n In the prototype, a two-level chain proof (CA → EE; ES256) is generated in about 30 seconds on Google Pixel 9a Future Works Repository p Additionally support ES384 and RSA4096 certificates p Support privacy-preserving revocation applying ZK to CRL p Add iOS support p Provide formal security audit 14