Security Proofs and Reductions
Expert-defined terms from the Professional Certificate in Post-Quantum Cryptography course at London School of Business and Administration. Free to read, free to share, paired with a professional course.
Term #
Adaptive Security
Explanation #
Adaptive security measures a cryptographic scheme’s resilience when an adversary can choose queries based on information gathered from previous answers. In post‑quantum settings, adaptive security often requires proofs that remain valid even when the attacker can adaptively request quantum superposition queries.
Example #
A lattice‑based encryption algorithm is said to be adaptively IND‑CCA secure if no quantum polynomial‑time adversary can distinguish between encryptions of chosen plaintexts, even after adaptively requesting decryption of related ciphertexts (excluding the challenge).
Practical application #
Adaptive security is essential for protocols such as secure messaging, where attackers may observe traffic and adapt their attacks in real time.
Challenges #
Proving adaptive security against quantum adversaries is difficult because the quantum random‑oracle model (QROM) introduces subtle issues with query rewinding and measurement.
Term #
Average‑Case Hardness
Explanation #
Average‑case hardness asserts that solving a problem on randomly chosen instances is as difficult as solving the hardest instances. In post‑quantum cryptography, many constructions rely on reductions from worst‑case lattice problems to average‑case problems like LWE.
Example #
The security proof for the Ring‑LWE encryption scheme reduces breaking the scheme to solving the Shortest Vector Problem (SVP) on any lattice, which is a worst‑case problem.
Practical application #
This property underpins the confidence that randomly generated keys in lattice‑based schemes inherit the hardness of the underlying lattice problem.
Challenges #
Constructing tight reductions that preserve security parameters while avoiding large loss factors is an ongoing research focus.
Term #
Hybrid Argument
Explanation #
A hybrid argument is a proof technique that links the real cryptographic game to an ideal game through a sequence of intermediate games, each differing by a small change. The adversary’s advantage is bounded by the sum of differences between successive hybrids.
Example #
In a proof of IND‑CPA security for a code‑based encryption scheme, the challenger gradually replaces the public matrix with a random matrix, analyzing the impact at each step.
Practical application #
Hybrid arguments are used to prove security of constructions such as KEM‑DEM hybrids and composable protocols.
Challenges #
In the QROM, hybrids must handle quantum query superpositions, complicating the analysis of each transition.
Term #
Indistinguishability
Explanation #
Indistinguishability captures the inability of any efficient adversary to tell apart two distributions, typically a real ciphertext from a simulated one. Different levels (CPA, CCA) correspond to the adversary’s capabilities.
Example #
A code‑based cryptosystem is IND‑CPA secure if no quantum polynomial‑time algorithm can distinguish an encryption of 0 from an encryption of 1 with non‑negligible advantage.
Practical application #
Indistinguishability is the backbone of security definitions for encryption, key‑exchange, and signature schemes.
Challenges #
Demonstrating indistinguishability in the presence of quantum side‑information often requires novel proof techniques, such as measurement‑independent reductions.
Term #
Indistinguishability under Chosen‑Plaintext Attack (IND‑CPA)
Explanation #
IND‑CPA asserts that an adversary given access to an encryption oracle cannot distinguish between the encryptions of two chosen plaintexts. The definition is extended to quantum adversaries by allowing superposition queries to the encryption oracle.
Example #
The NIST‑standardized Kyber KEM is proven IND‑CPA secure under the assumption that solving the Module‑LWE problem is hard for quantum computers.
Practical application #
IND‑CPA security is a minimal requirement for public‑key encryption schemes used in key‑exchange protocols.
Challenges #
Achieving IND‑CPA security in the QROM often leads to looser reductions, requiring larger parameters to compensate for proof loss.
Term #
Indistinguishability under Chosen‑Ciphertext Attack (IND‑CCA)
Explanation #
IND‑CCA extends IND‑CPA by granting the adversary access to a decryption oracle, except for the challenge ciphertext. The adversary must still be unable to distinguish the encrypted messages.
Example #
The McEliece encryption scheme can be transformed into an IND‑CCA secure KEM using the Fujisaki‑Okamoto (FO) transformation, with a security proof that reduces breaking IND‑CCA to solving the underlying decoding problem.
Practical application #
IND‑CCA security is required for protocols that must resist active attacks, such as TLS.
Challenges #
Proving IND‑CCA security against quantum adversaries often incurs a security loss because the standard FO proof relies on classical rewinding, which is not directly applicable in the quantum setting.
Term #
Key‑Encapsulation Mechanism (KEM)
Explanation #
A KEM is a public‑key primitive that encapsulates a symmetric key, which can later be used with a data‑encapsulation mechanism (DEM) to encrypt arbitrary messages. Security is typically defined via indistinguishability of the encapsulated key.
Example #
The Saber KEM, based on Module‑LWR, provides IND‑CPA security under the hardness of the Learning With Rounding problem.
Practical application #
KEMs are employed in hybrid encryption schemes, where the public‑key operation encrypts a short symmetric key and the symmetric key encrypts the bulk data.
Challenges #
Ensuring IND‑CCA security for KEMs in the quantum setting often requires tight reductions and careful handling of decryption‑oracle queries.
Term #
Lattice‑Based Cryptography
Explanation #
Lattice‑based cryptography builds primitives on the presumed hardness of lattice problems such as the Shortest Vector Problem (SVP) and Learning With Errors (LWE). These problems remain hard for both classical and quantum algorithms.
Example #
The NIST‑selected Kyber KEM is a lattice‑based scheme whose security reduces to the hardness of Module‑LWE.
Practical application #
Lattice‑based schemes support advanced functionalities like fully homomorphic encryption (FHE) and attribute‑based encryption.
Challenges #
Tight security reductions often require large parameter sizes, impacting performance and key/ciphertext sizes.
Term #
Learning With Errors (LWE)
Explanation #
LWE is a problem where one must recover a secret vector from noisy linear equations. The noise makes the problem computationally hard, and it is believed to be resistant to quantum attacks.
Example #
The security of the NewHope key‑exchange protocol reduces to solving the LWE problem over a ring.
Practical application #
LWE underlies many post‑quantum constructions, including encryption, signatures, and key‑exchange.
Challenges #
Parameter selection balances security against efficiency; overly conservative parameters increase bandwidth and latency.
Term #
Module‑LWE
Explanation #
Module‑LWE generalizes LWE to modules over rings, offering a trade‑off between security and efficiency. It enables more flexible dimension choices than Ring‑LWE while retaining similar hardness assumptions.
Example #
Kyber’s security proof reduces breaking its IND‑CPA security to solving Module‑LWE with specific dimensions.
Practical application #
Module‑LWE is used in NIST‑selected KEMs to achieve compact ciphertexts and fast operations.
Challenges #
Analyzing the exact hardness of Module‑LWE remains an active area, especially under quantum reductions.
Term #
Module‑LWR
Explanation #
Learning With Rounding (LWR) replaces the error term of LWE with a deterministic rounding operation, simplifying implementation while preserving hardness. Module‑LWR extends this to modules.
Example #
Saber’s security proof relies on the hardness of Module‑LWR, showing that distinguishing rounded samples from uniform is as hard as solving worst‑case lattice problems.
Practical application #
Module‑LWR enables efficient key‑generation and encapsulation with lower noise handling overhead.
Challenges #
Proving tight reductions from worst‑case problems to Module‑LWR in the quantum setting is non‑trivial.
Term #
Quantum Random Oracle Model (QROM)
Explanation #
The QROM extends the classical random‑oracle model by allowing adversaries to query the oracle on superpositions of inputs, reflecting realistic quantum capabilities. Proofs in the QROM must account for the inability to rewind quantum queries.
Example #
The security proof of the FO transformation for Kyber in the QROM replaces classical rewinding with a “measure‑once” technique to bound the adversary’s advantage.
Practical application #
The QROM is used to analyze hash‑based signatures, KEM transformations, and other protocols where hash functions are modeled as random oracles.
Challenges #
Designing reductions that remain tight in the QROM often leads to larger security loss, requiring careful parameter inflation.
Term #
Random Oracle Model (ROM)
Explanation #
The ROM treats a hash function as a truly random function accessible to all parties. It simplifies security proofs by allowing the challenger to program the oracle’s responses.
Example #
The original FO transformation proves IND‑CCA security of a KEM by programming the ROM to embed the challenge ciphertext.
Practical application #
Many post‑quantum schemes are proven secure in the ROM before being instantiated with concrete hash functions.
Challenges #
Translating ROM proofs to the QROM requires new techniques because quantum adversaries can query the oracle in superposition.
Term #
Reduction
Explanation #
A reduction shows that breaking a cryptographic scheme would solve a known hard problem. The reduction is often black‑box, using the adversary as a subroutine.
Example #
The reduction from IND‑CPA security of Kyber to solving Module‑LWE constructs an algorithm that, given a Module‑LWE instance, uses an IND‑CPA adversary to recover the secret.
Practical application #
Reductions justify the security of protocols by linking them to well‑studied hardness assumptions.
Challenges #
Reductions can be loose, introducing security loss that must be compensated by larger parameters; achieving tight reductions in the quantum setting is particularly demanding.
Term #
Security Parameter
Explanation #
The security parameter λ determines the size of keys, ciphertexts, and other algorithmic components, directly influencing the computational effort required to break the scheme.
Example #
In Kyber, λ = 128 bits leads to a lattice dimension of 256, yielding a concrete security level against known quantum attacks.
Practical application #
Selecting λ balances security against performance and bandwidth constraints.
Challenges #
Over‑estimating λ inflates resource consumption, while under‑estimating may expose the system to quantum breakthroughs.
Term #
Semantic Security
Explanation #
Semantic security is equivalent to IND‑CPA; it states that an adversary learns no additional information about the plaintext beyond its length.
Example #
A code‑based encryption scheme that is IND‑CPA secure automatically satisfies semantic security.
Practical application #
Semantic security is a baseline requirement for any encryption used in real‑world protocols.
Challenges #
Demonstrating semantic security against quantum adversaries often mirrors the challenges of IND‑CPA proofs in the QROM.
Term #
Simulation‑Based Proof
Explanation #
Simulation‑based proofs compare a real protocol execution with an ideal execution where a trusted party enforces the desired functionality. The proof shows that any adversary in the real world can be simulated in the ideal world.
Example #
The security proof of a post‑quantum secure multi‑party computation protocol may use a simulation‑based approach to argue that the real protocol leaks no more information than the ideal functionality.
Practical application #
Simulation‑based proofs are central to universally composable (UC) security frameworks.
Challenges #
Constructing simulators that work against quantum adversaries requires careful handling of quantum information and may increase proof complexity.
Term #
Statistical Distance
Explanation #
Statistical distance measures how far two probability distributions are from each other. In cryptographic proofs, it bounds the adversary’s advantage.
Example #
In a hybrid argument, the difference between two adjacent games is bounded by the statistical distance of the replaced component.
Practical application #
Statistical distance is used to quantify the leakage of information in encryption schemes.
Challenges #
In the quantum setting, the appropriate metric is trace distance, which behaves similarly but demands quantum‑aware analysis.
Term #
Trace Distance
Explanation #
Trace distance extends statistical distance to quantum states, measuring the maximum distinguishing advantage between two density matrices.
Example #
A security proof in the QROM may bound the adversary’s advantage by the trace distance between the real and ideal quantum oracle responses.
Practical application #
Trace distance is crucial for proofs involving quantum side‑information, such as in quantum‑secure hash‑based signatures.
Challenges #
Computing trace distance can be mathematically intensive, and reductions must preserve this metric throughout the proof.
Term #
Tight Reduction
Explanation #
A tight reduction has a small loss factor, meaning the advantage of breaking the underlying hard problem is close to the advantage of breaking the cryptographic scheme. Tightness directly impacts parameter selection.
Example #
The reduction from IND‑CPA security of Kyber to Module‑LWE is relatively tight, requiring only a modest increase in lattice dimension to achieve a target security level.
Practical application #
Tight reductions enable more efficient schemes with smaller keys and ciphertexts.
Challenges #
Achieving tightness in the QROM is harder because many proof techniques (e.g., rewinding) inherently introduce loss.
Term #
Worst‑Case to Average‑Case Reduction
Explanation #
This reduction shows that solving random instances of a problem (average case) is as hard as solving the hardest instances (worst case). It provides confidence that randomly generated keys inherit the hardness of the underlying problem.
Example #
The reduction from the Shortest Independent Vectors Problem (SIVP) to LWE demonstrates that breaking LWE on average would solve SIVP in the worst case.
Practical application #
Worst‑case reductions justify the use of randomly generated public parameters in lattice‑based schemes.
Challenges #
The reduction often incurs a polynomial loss, which must be compensated by larger parameters.
Term #
Zero‑Knowledge Proof
Explanation #
A zero‑knowledge proof allows a prover to convince a verifier of a statement’s truth without revealing any additional information. Post‑quantum zero‑knowledge protocols must remain sound against quantum verifiers.
Example #
The lattice‑based ZK‑Schnorr protocol proves knowledge of a short vector without revealing it, and its security is based on the hardness of SIS (Short Integer Solution).
Practical application #
Zero‑knowledge proofs are employed in privacy‑preserving authentication and blockchain consensus mechanisms.
Challenges #
Designing efficient post‑quantum zero‑knowledge proofs with small communication overhead is an active research area.
Term #
Signature Scheme
Explanation #
A signature scheme enables a signer to produce a short, verifiable token on a message. Security is often defined as existential unforgeability under adaptive chosen‑message attacks (EU‑F‑CMA).
Example #
Dilithium, a lattice‑based signature, is proven EU‑F‑CMA secure by reducing forgery to solving the Short Integer Solution problem.
Practical application #
Post‑quantum signatures replace RSA/ECDSA in TLS, code‑signing, and firmware updates.
Challenges #
Maintaining small signature sizes and fast verification while achieving tight reductions in the QROM is challenging.
Term #
Short Integer Solution (SIS)
Explanation #
SIS asks for a short non‑zero integer vector that maps to zero under a given matrix modulo q. It is believed to be hard for quantum computers and underlies many hash‑based and signature constructions.
Example #
The security of the lattice‑based hash function “Lattice‑Hash” reduces to SIS, ensuring collision resistance.
Practical application #
SIS is the foundation of many post‑quantum signatures, such as Falcon and Dilithium.
Challenges #
Parameter selection must balance the hardness of SIS against efficiency; overly conservative choices increase key and signature sizes.
Term #
Short‑Signature Scheme
Explanation #
Short‑signature schemes aim to produce signatures comparable in size to classical RSA signatures while retaining post‑quantum security. Falcon achieves this by leveraging the Fast Fourier Transform (FFT) on NTRU lattices.
Example #
Falcon’s security proof reduces forging a signature to solving the SIS problem on NTRU lattices.
Practical application #
Falcon is attractive for constrained environments like IoT devices where bandwidth is limited.
Challenges #
Implementing the FFT‑based signing algorithm securely against side‑channel attacks adds complexity.
Term #
Side‑Channel Resistance
Explanation #
Side‑channel resistance ensures that an implementation does not leak secret information through timing, power, or electromagnetic emissions. In post‑quantum schemes, the larger arithmetic operations increase the attack surface.
Example #
Constant‑time implementations of Kyber’s NTT (Number Theoretic Transform) mitigate timing attacks.
Practical application #
Side‑channel hardening is mandatory for hardware security modules (HSMs) and smart cards.
Challenges #
Achieving constant‑time behavior for lattice reductions and sampling procedures can degrade performance.
Term #
Number Theoretic Transform (NTT)
Explanation #
The NTT is a finite‑field analogue of the Fast Fourier Transform, enabling fast polynomial multiplication, a core operation in many lattice‑based schemes.
Example #
Kyber uses the NTT to multiply ring elements efficiently during key generation and encapsulation.
Practical application #
Optimized NTT implementations improve throughput for KEMs and signatures.
Challenges #
Secure NTT implementations must avoid data‑dependent memory accesses that could be exploited in side‑channel attacks.
Term #
Quantum‑Resistant Assumption
Explanation #
A quantum‑resistant assumption posits that a problem remains intractable for both classical and quantum adversaries. It forms the basis of security proofs for post‑quantum primitives.
Example #
The assumption that Module‑LWE is hard for quantum polynomial‑time algorithms.
Practical application #
All NIST‑selected post‑quantum schemes are built on such assumptions.
Challenges #
New quantum algorithms (e.g., for lattice reduction) could weaken these assumptions, requiring continual reassessment.
Term #
Quantum Adversary Model
Explanation #
The quantum adversary model defines the capabilities of an attacker equipped with a quantum computer, including the ability to query oracles in superposition and store quantum states.
Example #
In the QROM, a quantum adversary can query the random oracle on a superposition of inputs, receiving the corresponding superposed outputs.
Practical application #
Security proofs must explicitly consider quantum adversaries to be valid in a post‑quantum world.
Challenges #
Classical proof techniques often rely on rewinding, which is incompatible with quantum queries, necessitating novel proof strategies.
Term #
Quantum Polynomial‑Time (QPT) Algorithm
Explanation #
A QPT algorithm runs in time polynomial in the security parameter on a quantum computer. Security reductions aim to show that breaking a scheme would enable a QPT algorithm to solve a hard problem.
Example #
If an IND‑CCA adversary exists, a QPT reduction could solve the underlying SIS problem.
Practical application #
Demonstrating that no QPT algorithm can break a scheme underpins its post‑quantum security claim.
Challenges #
Proving that reductions are QPT‑preserving often requires careful accounting of quantum resources such as qubits and query complexity.
Term #
Quantum‑Safe Hash Function
Explanation #
A quantum‑safe hash function maintains collision resistance against quantum attacks, typically requiring at least 2n/3 bits of output to resist Grover’s algorithm.
Example #
SHA‑3 with 256‑bit output is considered quantum‑safe for most applications.
Practical application #
Hash functions are used as random oracles in KEM transformations and signature schemes.
Challenges #
Replacing legacy hash functions with quantum‑safe alternatives may affect protocol compatibility and performance.
Term #
Reductionist Proof Technique
Explanation #
A reductionist proof constructs a direct reduction from breaking a scheme to solving a hard problem, often using black‑box access to the adversary. It is the standard method for establishing security guarantees.
Example #
The reduction from IND‑CPA security of a code‑based KEM to decoding random linear codes.
Practical application #
Reductionist proofs provide a clear security argument that can be audited and verified.
Challenges #
Achieving tightness and handling quantum queries within reductionist proofs remain significant hurdles.
Term #
Game‑Based Proof
Explanation #
Game‑based proofs define a game between a challenger and an adversary; the goal is to bound the adversary’s advantage. Each game corresponds to a security definition (e.g., IND‑CPA).
Example #
In the IND‑CPA game, the adversary receives an encryption oracle and must guess which of two messages was encrypted.
Practical application #
Game‑based proofs are intuitive and align with protocol specifications.
Challenges #
Translating game‑based arguments to the QROM requires careful handling of quantum queries and measurement.
Term #
Oracle‑Based Reduction
Explanation #
An oracle‑based reduction treats the adversary’s access to an oracle (e.g., encryption, decryption) as a black box, and the reduction simulates this oracle while embedding a hard problem instance.
Example #
The FO transformation’s reduction simulates the decryption oracle using the random oracle to embed the challenge ciphertext.
Practical application #
Oracle‑based reductions are common in KEM‑DEM constructions.
Challenges #
In the QROM, simulating an oracle that can be queried in superposition demands quantum‑compatible programming techniques.
Term #
Rewinding Technique
Explanation #
Rewinding allows a proof to run an adversary, then revert its state to an earlier point to extract information. Classical proofs often rely on rewinding to extract a secret.
Example #
The classic proof of the Fiat‑Shamir transformation rewinds the adversary to obtain two transcripts and extract the witness.
Practical application #
Rewinding is used in many zero‑knowledge and signature proofs.
Challenges #
Quantum adversaries cannot be rewound without violating the no‑cloning theorem, leading to alternative techniques such as “measure‑once” or “semi‑classical” rewinding.
Term #
Measure‑Once Technique
Explanation #
Measure‑once avoids rewinding by performing a single measurement that captures enough information to complete the reduction. It is compatible with quantum adversaries.
Example #
In the QROM proof of the FO transformation for Kyber, the challenger measures the adversary’s query only once, then programs the oracle accordingly.
Practical application #
Measure‑once enables security proofs of hash‑based KEMs against quantum attackers.
Challenges #
Designing a measurement that preserves the adversary’s advantage while providing the necessary extraction can be intricate.
Term #
Indistinguishability Obfuscation (iO)
Explanation #
iO is a powerful primitive that makes two equivalent programs computationally indistinguishable after obfuscation. Its security is defined via indistinguishability games.
Example #
Recent constructions propose iO based on lattice assumptions, though concrete post‑quantum security remains speculative.
Practical application #
iO enables advanced functionalities like functional encryption and program sanitization.
Challenges #
Existing iO constructions rely on assumptions that are not yet proven quantum‑secure, and their reductions are extremely loose.
Term #
Functional Encryption (FE)
Explanation #
FE allows a holder of a secret key to learn a specific function of the encrypted data without revealing the data itself. Security proofs often reduce FE to iO or other hard problems.
Example #
A lattice‑based FE scheme may rely on the hardness of LWE and a reduction to an indistinguishability game.
Practical application #
FE is useful for privacy‑preserving data analytics and cloud computing.
Challenges #
Achieving efficient, post‑quantum FE with tight security reductions is an open problem.
Term #
Fully Homomorphic Encryption (FHE)
Explanation #
FHE permits arbitrary computation on encrypted data. Most constructions are based on lattice problems and require reductions to LWE or related assumptions.
Example #
The BGV scheme’s security reduces to the hardness of Ring‑LWE.
Practical application #
FHE enables secure outsourced computation, such as encrypted machine learning.
Challenges #
Bootstrapping introduces large noise growth, and security reductions often have significant loss, demanding large parameters for quantum security.
Term #
Bootstrapping
Explanation #
Bootstrapping refreshes ciphertexts by homomorphically evaluating the decryption circuit, reducing accumulated noise. Its correctness and security depend on the underlying hardness assumptions.
Example #
In the CKKS scheme, bootstrapping is used to maintain approximate arithmetic on encrypted data.
Practical application #
Bootstrapping extends the depth of feasible homomorphic computations.
Challenges #
The bootstrapping process is computationally heavy, and proving its security against quantum adversaries adds further complexity.
Term #
Noise Flooding
Explanation #
Noise flooding adds additional random error to ciphertexts to obscure any information that could be extracted via decryption queries, aiding IND‑CCA proofs.
Example #
The FO transformation for LWE‑based KEMs uses noise flooding to ensure that decryption queries do not reveal the secret.
Practical application #
Noise flooding is a practical technique to achieve strong security without large parameter blow‑up.
Challenges #
Excessive noise can degrade decryption correctness, requiring careful parameter balancing.
Term #
Rejection Sampling
Explanation #
Rejection sampling generates samples from a target distribution by repeatedly drawing from an easier distribution and accepting based on a criterion. It is used to hide secret information in signatures.
Example #
Dilithium’s signing algorithm employs rejection sampling to produce signatures whose distribution does not leak the secret key.
Practical application #
Rejection sampling ensures that signatures are statistically close to uniform, supporting EU‑F‑CMA security.
Challenges #
The sampling loop may cause variable execution time, which can be exploited in side‑channel attacks; constant‑time implementations are required.
Term #
Statistical Zero‑Knowledge (SZK)
Explanation #
SZK guarantees that the simulated view is statistically indistinguishable from the real view, even against unbounded adversaries. It is a stronger notion than computational zero‑knowledge.
Example #
Certain lattice‑based protocols achieve SZK by ensuring that the distribution of commitments is independent of the secret.
Practical application #
SZK protocols are valuable in settings where adversaries may have large computational resources, such as national‑level threats.
Challenges #
Constructing SZK proofs with post‑quantum assumptions while keeping communication overhead low is non‑trivial.
Term #
Collision‑Resistant Hash Function (CRHF)
Explanation #
A CRHF makes it infeasible for any adversary to find two distinct inputs that hash to the same output. In the quantum setting, the birthday bound is reduced by Grover’s algorithm, requiring larger output sizes.
Example #
SHA‑256 with 256‑bit output offers ~128‑bit security against quantum collision attacks.
Practical application #
CRHFs are used in Merkle tree constructions for blockchain and in the FO transformation as random oracles.
Challenges #
Designing hash functions that maintain collision resistance under quantum attacks without incurring excessive performance penalties is an ongoing concern.
Term #
Quantum‑Secure Signature (QSS)
Explanation #
A QSS is a digital signature scheme provably secure against quantum adversaries, typically defined by EU‑F‑CMA in the QROM.
Example #
Falcon’s security proof shows that any forgery leads to solving SIS, even when the adversary can query the hash oracle in superposition.
Practical application #
QSS replace classical signatures in protocols like TLS 1.3 and code‑signing pipelines.
Challenges #
Maintaining small signature sizes while achieving tight reductions in the QROM is a design trade‑off.
Term #
Quantum‑Resistant Key‑Derivation Function (KDF)
Explanation #
A KDF expands a shared secret into cryptographic keys, and must resist attacks accelerated by quantum algorithms. Using hash functions with sufficient output length mitigates Grover’s speedup.
Example #
HKDF‑SHA‑256 is often employed after a post‑quantum KEM to derive symmetric keys.
Practical application #
KDFs are integral to TLS handshakes and secure storage solutions.
Challenges #
Ensuring that the KDF’s security proof remains valid in the QROM may require additional assumptions about the hash function’s quantum resistance.
Term #
Quantum‑Secure Randomness Extractor
Explanation #
An extractor converts a weakly random source into nearly uniform random bits, even against quantum side‑information. Security is measured via the trace distance between the output and the ideal uniform distribution.
Example #
A Trevisan extractor can be used to derive seeds for post‑quantum protocols from noisy hardware sources.
Practical application #
Extractors are employed in key‑generation processes where the entropy source may be partially compromised.
Challenges #
Designing extractors with low computational overhead and provable security against quantum adversaries is technically demanding.
Term #
Quantum‑Resistant Pseudorandom Function (PRF)
Explanation #
A PRF outputs values indistinguishable from random, even when queried by a quantum adversary. Security proofs often rely on reductions to hard problems like LWE.
Example #
The LWE‑based PRF used in some lattice‑based constructions offers quantum‑resistant security.
Practical application #
PRFs are used in authenticated encryption and key‑stretching.
Challenges #
Ensuring that the PRF remains secure under superposition queries without excessive performance penalties is a key research area.
Term #
Quantum‑Secure Oblivious Transfer (OT)
Explanation #
OT enables a sender to transfer one of many pieces of data to a receiver while remaining oblivious to which piece was chosen. Security against quantum adversaries often reduces to lattice hardness.
Example #
An OT protocol based on the hardness of Ring‑LWE can be proven secure in the QROM.
Practical application #
OT is a building block for secure multiparty computation and private set intersection.
Challenges #
Achieving efficient, constant‑round OT with tight quantum‑secure reductions remains an open problem.
Term #
Quantum‑Secure Multiparty Computation (MPC)
Explanation #
MPC allows multiple parties to jointly compute a function over their inputs while keeping those inputs private, even in the presence of quantum adversaries. Security proofs typically combine OT, zero‑knowledge, and other primitives.
Example #
An MPC protocol that uses lattice‑based OT and zero‑knowledge proofs can achieve security against QPT adversaries.
Practical application #
MPC is used for collaborative analytics on sensitive data, such as joint fraud detection across banks.
Challenges #
The overhead of quantum‑secure MPC is high; reducing communication and round complexity while preserving security is an active research direction.
Term #
Quantum‑Secure Public‑Key Infrastructure (PKI)
Explanation #
A PKI manages digital certificates and public keys, requiring quantum‑secure signatures and key‑exchange mechanisms to maintain trust.
Example #
Replacing RSA signatures