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

[Robert Moskowitz <[e-mail]>]

On 07/29/2014 02:38 AM, Mike Hamburg wrote:
>
> 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.

During a traffic mess, you might see 100+ cars for an hour. Probably 
more.  The radio range is 1Km; it will be interesting how it will 
actually work in a congested roadway.   Everything is simulations so far 
(at least congestion areas) that I have seen.  A 20,000 vehicle pilot is 
suppose to be coming soon and perhaps they can stage some congestion 
testing.



> Signature verification is g^x y^e with e short, and you can use the 
> comb tables.
>
> Cheers,
> -- Mike
>