Re: [Cfrg] IEEE 1609 requirements (was Re: Curve selection revisited)

[Mike Hamburg <[e-mail]>]

On 7/28/2014 9:14 PM, Watson Ladd wrote:
> On Mon, Jul 28, 2014 at 8:59 PM, William Whyte
> <[e-mail]> wrote:
>> One potential bottleneck bottleneck is verification of incoming
>> messages. There may be 1000 incoming messages per second. Verifying
>> all of these requires hardware acceleration on any realistic
>> automotive device and for any choice of curve that I'm aware of.
>> Another alternative is to only verify certain messages, for example
>> from cars that might potentially cause a hazard. Hardware acceleration
>> is possible, but raises costs and risks locking in a particular crypto
>> solution. Europe and the US are taking different approaches to this:
>> in the European system, the intent is that every message is verified,
>> while in the US the emphasis is more on verify on demand.
A crypto math offload engine would be a good option.  You might not have 
to lock in a particular curve or algorithm.
> Batch verification of some variants of Schnorr is extremely efficient,
> thus reducing
> per-signature costs. I assume this has been considered.
Batch verification cuts signature verify times by up to 50%, but costs 
latency and complexity.  It's definitely an engineering tradeoff worth 
considering.  But I don't think batching is compatible with short 
signatures.

If you can dedicate the RAM and processing time -- which maybe you can't 
in a car system, but who knows -- there is also the option of 
precomputation.  Make a big comb table for g (a few kB in ROM) and a 
little comb table (maybe 256 bytes) for each car y you've seen more than 
n times.  Signature verification is g^x y^e with e short, and you can 
use the comb tables.

Cheers,
-- Mike