HIC Is All You Need: Post-Quantum PAPKE Explained

Passwords are often treated as the old part of security: useful, familiar, and fragile. Public-key encryption is treated as the modern part: powerful, asynchronous, and dependent on authentic public keys.

Password-Authenticated Public-Key Encryption connects those two ideas. This article explains the original PAPKE primitive, why it is not the same as encrypting a file with a password, and how this paper, HIC Is All You Need, moves the construction toward practical post-quantum instantiations.

The Problem: Public Keys Still Need Authentication

Public-key encryption solves one problem: a sender can encrypt to a recipient's public key. It leaves another problem open: how does the sender know that this is really the recipient's public key?

In deployed systems, that authenticity usually comes from PKI, certificates, a trusted directory, a messaging provider, or manual fingerprint comparison. Those mechanisms are useful, but they are not always available, simple, or desirable.

Password-Authenticated Public-Key Encryption, or PAPKE, asks whether a short shared password can authenticate a public key without turning the public key or later ciphertexts into an offline password-checking tool.

What PAPKE Adds

The original PAPKE paper by Bradley, Camenisch, Jarecki, Lehmann, Neven, and Xu introduced Password-Authenticated Public-Key Encryption as a primitive combining public-key encryption with password authentication.

At a high level, PAPKE lets the recipient publish a reusable public key that is authenticated with a shared human-memorable password. A sender who knows the password can use the password-authenticated public key and encrypt a message asynchronously.

An attacker who replaces or tampers with that public key should not be able to mount a man-in-the-middle attack unless they can guess the password online. At the same time, merely seeing the authenticated public key or ciphertexts should not let the attacker test password guesses offline.

The caveat is important: the authentication of the public key is only as strong as the shared password. PAPKE is not a silver bullet for weak or reused passwords. If the password is later revealed, an attacker may be able to recognize the authenticated public key and send new encrypted messages to the recipient, but that does not by itself decrypt messages already encrypted; those still depend on the recipient's secret key and on the underlying public-key encryption scheme.

• Reusable public key: the recipient can publish a password-authenticated public key once and receive encrypted messages later.
• Asynchronous communication: the sender can encrypt without first running an interactive key exchange with the recipient.
• Password authentication: the password authenticates which public key is accepted; it is not treated as a high-entropy encryption key.
• Offline dictionary resistance: the authenticated public key and ciphertexts should not become cheap password verifiers.

How PAPKE Works at a High Level

A useful mental model is to split PAPKE into setup and encryption.

During setup, the recipient creates a public-key encryption key pair. The public key is then transformed or protected using the shared password, so that a sender who knows the password can recover or validate the right public key.

During encryption, the sender uses the password to process the password-authenticated public key. If the password is correct, the sender obtains the real encryption public key and encrypts normally. If the password is wrong, the process should not reveal enough information to test guesses offline.

This is different from ordinary password-based symmetric encryption. If an attacker obtains a password-encrypted ciphertext, they can try a guessed password, derive a key, decrypt, and check whether the result looks like normal plaintext. That is an offline dictionary test. PAPKE keeps the structure of public-key encryption, but uses the password to authenticate the public key while preventing the authenticated public key or ciphertexts from becoming a cheap password-checking oracle.

Why the Original Construction Used an Ideal Cipher

The generic PAPKE construction from the original paper uses a CCA-secure, anonymous public-key encryption scheme together with an ideal cipher over the public-key domain.

This creates an unusual tension. In ordinary public-key encryption, the public key is meant to be public: everyone can know it, copy it, and encrypt to it. In PAPKE, the real encryption public key still plays that role after authentication, but the password-authenticated public key must not reveal enough structure to let an attacker check password guesses.

The intuition is that the password hides or transforms the public key so that, to someone without the password, it looks random. The ideal-cipher model is a clean theoretical abstraction for that operation.

That abstraction is useful in a proof, but awkward in implementation. Standard block ciphers operate over fixed-size blocks such as 128 bits, while modern public keys, especially post-quantum public keys, are much larger structured objects.

Why Post-Quantum PAPKE Is Harder

Many classical PAPKE and PAKE-style constructions rely on Diffie-Hellman-like algebra. Large fault-tolerant quantum computers would break the assumptions behind those classical groups, and recent resource estimates make the migration pressure concrete. A Google Quantum AI whitepaper estimates that Shor's algorithm against 256-bit elliptic-curve discrete logarithms could run in minutes on some future fast-clock architectures with fewer than half a million physical qubits. A separate Oratomic/Caltech preprint argues that high-rate error-correcting codes and reconfigurable atomic qubits could bring cryptographically relevant Shor instances into the 10,000-to-100,000-qubit range, with longer runtimes. These are resource estimates, not deployed attacks, but they explain why post-quantum migration is being treated as urgent.

A natural idea is to replace the underlying public-key encryption with a post-quantum PKE or KEM. But that is not a drop-in engineering task. The construction still needs a way to password-authenticate public keys without leaking structure or enabling offline dictionary attacks.

This is where the size and structure of post-quantum keys matter. If the construction expects an ideal cipher over the public-key domain, and the public keys are large lattice- or code-based objects, instantiating that ideal cipher efficiently becomes a central obstacle.

HIC Is All You Need

In this paper, Arriaga, Mestel, Oupicky, Ronne, Skrobot et al. propose a way around that obstacle.

Instead of requiring a full Ideal Cipher over the public-key domain, the construction uses a Half-Ideal Cipher, or HIC. HIC was introduced in earlier EUROCRYPT 2023 work as a relaxation of an ideal cipher that can still be sufficient for certain password-authenticated protocols.

The point is pragmatic: do not instantiate a stronger idealized object than the proof actually needs. If a weaker and more efficiently realizable object is enough, the post-quantum construction becomes much more plausible.

The resulting construction, PAPKE-HIC, is presented as a UC-secure PAPKE scheme built from a public-key encryption scheme and a HIC.

What the Post-Quantum Variant Needs

The HIC paper does not claim that any arbitrary post-quantum encryption scheme can be plugged in blindly. It keeps the original need for CCA-secure anonymous public-key encryption and tightens one point in the PAPKE-IC proof.

At a high level, the encryption scheme must behave well enough that password-authenticated public keys and ciphertexts do not leak the wrong kind of information or create ambiguous decryption behavior.

• CCA security: the underlying PKE must remain confidential even against adaptive chosen-ciphertext attacks. This is stronger and more precise than merely saying that ciphertexts are hard to invert.
• Ciphertext anonymity: a ciphertext should not reveal which public key it was encrypted under, even when the attacker knows the candidate public keys.
• Pseudo-uniform public keys: generated public keys should be computationally hard to distinguish from the public-key distribution the HIC-based construction expects to manipulate.
• Decryption robustness: a ciphertext should not validly decrypt to conflicting messages under different secret keys in a way that breaks the protocol proof. The paper captures the needed version as DROB-CCA and relates it to stronger robustness notions.

Concrete Instantiations

The paper then makes the construction concrete. It studies PAPKE-HIC built from a standard KEM+DEM public-key encryption layer using ML-KEM, FrodoKEM, and Classic McEliece. ML-KEM and FrodoKEM fit the analysis through the prefix-hashing Fujisaki-Okamoto transform, which gives a direct route to the needed decryption-robustness property. Classic McEliece is more delicate: the paper discusses a modified variant and a hashed-public-key transform as a more black-box way to obtain the required robustness. The benchmark code is public in the PAPKE-HIC benchmarks repository, implemented in C++ with Botan for cryptographic primitives and Catch2 for measurements. The benchmarks show the practical point of HIC: for ML-KEM, PAPKE-HIC needs one hash-to-group operation where PAPKE-IC needs several; for Classic McEliece encryption, the HIC variant is reported at about 0.26x the time of the 8-round-Feistel PAPKE-IC variant.

The Practical Meaning

The promise of PAPKE is asynchronous, PKI-free encryption based on a shared password. That fits situations where two people can agree on a password but do not want to rely on certificates, account providers, or manual fingerprint checks.

The promise of PAPKE-HIC is that the same idea can be moved toward the post-quantum setting. Instead of relying on Diffie-Hellman assumptions, the construction can be instantiated with suitable post-quantum public-key encryption tools.

The caveat is that this is cryptographic protocol design, not a simple application feature. The security does not come from just mixing a password with a public key. It comes from a carefully specified primitive, a proof model, and precise requirements on the underlying encryption scheme and the HIC-based public-key transformation.

The Takeaway

PAPKE is useful because it treats passwords as an authentication tool for public keys, while still aiming to prevent offline dictionary attacks.

The original PAPKE work defines the primitive and its relationship to PAKE. HIC Is All You Need shows how the generic PAPKE idea can be made practical in a post-quantum direction by replacing a difficult ideal-cipher component with a Half-Ideal Cipher construction.

In simple terms: passwords can authenticate public keys, public-key encryption can support asynchronous messages, and post-quantum variants become realistic when the public-key transformation is designed with the right cryptographic abstraction.

References

• Bradley et al.: Password-Authenticated Public-Key Encryption
• Arriaga, Mestel, Oupicky, Ronne, Skrobot: HIC Is All You Need
• Freitas Dos Santos, Gu, Jarecki: Randomized Half-Ideal Cipher on Groups
• Babbush et al.: Securing Elliptic Curve Cryptocurrencies against Quantum Vulnerabilities
• Cain et al.: Shor's algorithm is possible with as few as 10,000 reconfigurable atomic qubits
• PAPKE-HIC benchmark implementation repository