Complexity leveraging
Complexity leveraging derives a security notion from a super-polynomially strong form of an assumption through a reduction whose loss, in advantage or in running time, exceeds every polynomial. Typically the reduction guesses an -bit value that the adversary chooses during the game and loses a factor , which sub-exponential hardness absorbs once the security parameter is a large enough polynomial in — standard. The term is due to CGGM00, in their treatment of resettable zero knowledge in the bare public-key model.
Guessing the challenge
Let be a game in which names a value — a challenge identity, attribute set, input or message — at a point of its choosing, subject to admissibility constraints that refer to (no key query on the challenge identity, no signing query on the forged message). Let be the same game except that outputs before the game starts, the challenger’s behaviour being otherwise the same.
From an adaptive , the selective adversary samples , outputs it as its choice, and runs , relaying messages between and its own challenger. It stops as soon as makes a query that is inadmissible for or names some , and then outputs a uniform bit in a bit-guessing game and gives up in a search game; otherwise it outputs what outputs. Until stops, ‘s view is distributed as in and is independent of , and an admissible that names makes no query inadmissible for . Hence in a bit-guessing game
so for the advantage , and in a search game — standard. runs in the time of plus the time to sample and compare it with ‘s queries and challenge.
For IBE, the remark that selective-identity security yields full security with a loss of the size of the identity space is due to BB04b (Sub-exponential IND-sID-CPA ⇒ IND-ID-CPA security); the HIBE analogue loses the number of identity vectors (Sub-exponentially selective HIBE ⇒ adaptive HIBE) — folklore.
Absorbing the loss
Let , and suppose every selective adversary of size at most has advantage at most . Then every adaptive whose reduction has size at most has advantage at most . Adaptive security against all polynomial-size adversaries follows when is super-polynomial and is negligible — standard.
- Polynomial hardness does not suffice. For a negligible need not make negligible. For HIBE and CP-ABE, if selectively secure schemes with a super-polynomial challenge space exist, selective security of such a scheme does not imply its adaptive security (No fixed-construction reduction from IND-sHIBE-CPA to IND-HIBE-CPA security, No fixed-construction reduction from selective to adaptive CP-ABE security) — folklore.
- Sub-exponential hardness suffices. If against size for a constant , then for the adaptive advantage of every polynomial-size adversary is at most . Equivalently, a scheme with -bit challenges is run at a security parameter , polynomial in — standard. Sub-exponential notions on this site include sub-exponential one-wayness, sub-exponential IND-sID-CPA security and sub-exponentially secure iO.
Guessing an index versus a value
A hybrid argument with transitions is often run by a reduction that samples the index of the transition it attacks and loses a factor ; for the loss is polynomial and no leveraging is needed, and a non-uniform reduction may instead hard-wire the best index — standard. Leveraging is needed when the guessed object ranges over a super-polynomial set: a value chosen adaptively by the adversary, as above, or the index of a hybrid sequence of super-polynomial length, such as one that changes an obfuscated program on one input at a time and so has steps — standard. The hard PPAD instances of Sub-exponential injective OWF + iO ⇒ PPAD hardness assume sub-exponentially secure iO and injective one-way functions to absorb a super-polynomial reduction loss — BPR15.
Non-adaptive soundness of a NIZK argument gives adaptive soundness for statements of length with a loss of : a cheating prover that chooses a false after seeing and succeeds with probability succeeds with probability at least on some fixed false statement , which a non-uniform reduction fixes in advance — standard.
Leveraging running time
A reduction may also run in super-polynomial time, for instance to break one component of a scheme by exhaustive search, and then needs the remaining assumptions to hold against adversaries of that running time. Such proofs set the components at different security levels: one breakable by exhaustive search in time , the others secure against adversaries running in time — standard.
Participates in
Used via Complexity leveraging