Transcript ppt - IEEE-SA - Working Group

Pairing Standards
Mike Scott
Noretech Ltd
Standards.
• “What the Gods would destroy they first
send to the IEEE for standardization”
(Slashdot quote from last week….)
• Its important to come up with a standard
that is as “simple” and implementerfriendly as possible. Not too mathematical.
A Unified approach
• Can a scheme like IBE be presented in a
curve-independent fashion?
• Probably not – but worth a try.
• B&F IBE can use SS or non-SS curves,
char p, or char 2, or char 3, or genus 2…
• I have tried to describe it in this way –
pushing differences and detail down a
level.
B&F vs B&B
• New IBE scheme
• IDs hash to integer – much easier than
hashing to a curve point
• Like Sakai & Kasahara
• Note attempt to generalise description for
non-SS curves – see θ function
Some notation
• Field size F
• Group size G
• Standard contemporary security (F/G) =
(1024/160)
• How to scale up – remember SHA-1?
• Koblitz & Menezes, Scott – increase
embedding degree k → non-SS curves
Do all schemes scale?
• BLS signature does not scale
• I don’t see a long term future for it.
• No known way to find suitable curve with
F≈G and k>6
Weil Pairing anyone?
• Eventually, it must be faster
• Complexity O(F2G) vs O(F3)
• Unsure as to cross-over point – more
experimentation required
• Probably not superior to Tate for
“reasonable” security levels
Characteristic 2 SS curves
• Fastest known pairings??
• See section 6 of recent eprint paper by
Barreto,Galbraith,O’hEigeartaigh,Scott
• If we are envisaging implementation on
low powered devices (sensor networks)..
• No power consuming fast integer mul
instruction needed.
• Hashing ID to point much faster
Char 2/3 characteristic curves
• Security questions?
• See Lenstra (“Unbelievable security”
Asiacrypt 2001) for authoritative opinion.
• Personally I don’t like char 3 – made
popular by BLS short signature (See
above)
• Higher embedding degree offset by
awkward implementation on binary
computers?
Attachments
• Very draft standard for IBE schemes.
Need to add a “tips” section for
optimizations for each particular type of
curve. Owes a lot to Voltage #IBCS 1.
• “Scaling the Tate Pairing” – some
experimental results
• Deterministic hashing to curve points is
possible for certain curves.
Concerns
• Need to be careful not to do anything to
upset security proofs.
• Not sure of demarcation line between what
I am trying to do, and Hovav’s work.
• I am sure others will disagree with my
approach – but I am eager to take on
board the views of others!