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.

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