Re: [P1363:] HIBE Scheme
On May 25, 2009, at 3:35 AM, kobayashi.tetsutaro wrote:
I do not agree that the Boneh-Boyen HIBE framework [BBG-HIBE]
outperforms the Gentry-Silverberg [GS-HIBE] by every criterion.
You'll note I suggested the Boneh-Boyen HIBE, not the BBG HIBE.
First, [GS-HIBE] is more efficient than [BBG-HIBE] at least for
encryption. [GS-HIBE] is more efficient than [BBG-HIBE] also for
decryption if t< 3, where t is the depth of hierarchy.
Actually, both BBG and BB are more efficient than GS. You state below
that BBG needs a pairing for encryption, but that's not the case, just
as it's not the case for BB. The value e(g1,g2) is a constant that
can be cached or included in the public key. What you have for
e(g1,g2)^s is just an exponentiation in GT. By contrast, Boneh-
Franklin (and therefore also GS) actually does require a pairing for
encryption, since the value e(Q0, H1(ID1))^r must be computed in the
ciphertext. Because H1 is a random oracle there's no more efficient
way to compute this value without first evaluating H1 and then pairing
it with Q0^r, at least for the first time you send a message to a
given receiver.
And this ignores a number of other factors. GS instantiated with an
asymmetric pairing either has very large ciphertexts (if the Ui's live
in G2) or expensive hashing to G2 (if the Si's live in G2). GS
instantiated with a symmetric pairing scales worse than BB/BBG. For
GS encryption the bases used in exponentiation are random outputs of
the the hash; for BB/BBG, they are fixed. This means that -- with
appropriate precomputation -- each of the BB/BBG exponentiations
should take about one-sixth as long as each of each of the GS
exponentiations, even if we instantiated both systems on the same
curve (which, as noted above, is unfair to BB/BBG).
Second, the security assumption of [GS-HIBE] differs from that of
[BBG-HIBE]. That is, [GS-HIBE] is secure in the Random Oracle model
assuming the BDH assumption, where [BBG-HIBE] is secure in the generic
model assuming the l-BDH assumption. I cannot say which outperforms
the
other.
You mean "the standard model," I think, not "the generic model." In
any case, Boneh-Boyen is selective-ID secure in the standard model
under the DBDH assumption. With random oracles, it's fully (i.e.,
adaptive-ID) secure under DBDH. Alternatively, replacing the Boneh-
Boyen hash with the Waters hash in the BB framework would give a fully
secure HIBE in the standard model under DBDH. I suspect random
oracles could be used to give computational BDH security, just like BF/
GS.
Yours --
Hovav.
[GS-HIBE] Hierarchical ID-Based Cryptography, C.Gentry, A.Silverberg,
ASIACRYPT2002
Security: random oracle model, BDH assumption
Efficiency for encryption: (t-1) EC-Scalar Mults
Efficiency for decryption: t Pairings
[BBG-HIBE] Hierachical Identity Based Encryption with Constant Size
Ciphertext, D.Boneh, X.Boyen, E.Goh, EUROCRYPT2005
Security: generic model, l-BDH assumption
Efficiency for encryption: 1 Pairing + t EC-Scalar Mults
Efficiency for decryption: 2 Pairings + (2t+4) EC-Scalar Mults
______________________________________________________________________
To unsubscribe, mail LISTSERV@xxxxxxxxxxxxxxxxx with
the body of the message containing: SIGNOFF STDS-P1363-DISCUSS
Send any concerns to STDS-P1363-DISCUSS-request@xxxxxxxxxxxxxxxxx,
or manage subscriptions at http://listserv.ieee.org/cgi-bin/wa
Visit IEEE P1363 on the web at: http://grouper.ieee.org/groups/1363
______________________________________________________________________