[Cryptography] crypto strength ... was: ratcheting DH strengths over time

John Denker jsd at av8n.com
Mon Nov 23 12:22:55 EST 2015


On 11/22/2015 03:47 PM, Ray Dillinger wrote:

> If everybody's
> using the same curve, the same computation searches for
> everybody's keys.

OK.

That reflects the attack_value_per_break relative to the 
attack_cost_per_break.  Note that we need to pay attention
to both the numerator and denominator.

> our attacker model should be the cost PER KEY
> of breaking any key in a very large batch.

Maybe it should go without saying, but let me say it anyway:
Ideally, this should be a /minimax/ proposition.  Specifically,
the design objective should be to maximize [over all designs] 
the minimum [over any batch] cost per key ... not the average
cost per key or typical cost per key.

Use case scenario: Suppose my friend in Ptomainia sends me
10,000 messages.  If any one of them gets broken he gets killed.
In this scenario, the attacker doesn't need to break the average
key, but only the weakest key.

Similarly:  Suppose I download 10,000 software packages from a
trusted distributor.  If the attacker can "taylor" any *one*
of them, I get pwned.

In such a scenario, we need:
 *) a large batch of keys, to minimize the attack_value_per_break
 *) a large *minimum* cost (not merely a large "average" cost)
  per broken key.

One can imagine other scenarios where the average cost is all
that matters, but we cannot always count on this.

FWIW, in cases where cost is related to some probability distribution
P, these ideas are related to things that can be quantified by using
various Rényi functionals:
 -- average cost <-->  H1[P] ≡ entropy
 -- minimax cost <-->  H∞[P]



More information about the cryptography mailing list