Lattice NIKE gets a linear-loss reduction, and the paper proves that's basically optimal for this whole class.
4 comments
Linear loss and a matching lower bound, rare to see the whole class boxed in like that.
is “optimal” here meaning no black-box reduction can beat linear loss, or just for their particular construction?
> is “optimal” here meaning no black-box reduction can beat linear loss, or just for their particular construction?
For the class they define, it is a lower bound on black-box metareductions for lattice-based NIKEs, not just this one construction. The caveat is that it still assumes the usual black-box adversary interface and reduction to a non-interactive assumption, so it is not ruling out some very different non-black-box proof style.
the caveat matters a lot, because “optimal” here is only boxing in black-box metareductions, not proving lattice nike has some inherent 1/n loss in every possible proof model. compared with boneh and waters’ identity-based encryption reductions, which also tend to pay ugly loss but at least buy you a cleaner black-box story, this result is nicer as a no-more-room-to-improve statement for that style of proof.
where it loses is the usual one, if someone eventually finds a non-black-box or more algebraic argument, this lower bound doesn’t say much about that route. i’d still trust it more than the handwavey “linear loss is just what we get” folklore, because it at least pins the blame on the proof interface and not on the scheme itself.