search

cfrg / draft-irtf-cfrg-voprf

Oblivious Pseudorandom Functions (OPRFs) using Prime-Order Groups
https://cfrg.github.io/draft-irtf-cfrg-voprf/#go.draft-irtf-cfrg-voprf.html
Other
39 stars 15 forks source link

Consider to add a table of groups and their parameters #90

Closed armfazh closed 4 years ago

armfazh commented 4 years ago

Originally posted by @chris-wood in https://github.com/cfrg/draft-irtf-cfrg-voprf/pull/78

Should we include a table that lists the group (name) and its parameters, e.g., the generator, base field prime order, etc.?

alxdavids commented 4 years ago

@chris-wood This is actually going to be pretty difficult due to the trade-offs that can be chosen with the static DH oracle. Essentially, due to Brown-Gallant & Cheon the strength of breaking DLP is: image (taken from Section 21.5 of https://www.math.auckland.ac.nz/~sgal018/crypto-book/main.pdf). This translates, for example, to: image But each curve comes with its own r-1 factors. There are also variants of the attack that can be done for r+1, see this email for a good summary: https://mailarchive.ietf.org/arch/msg/cfrg/YDVS5Trpr6suig_VCFEOH6SOn8Q/.

The problem is that for each curve we can choose different trade-offs based on the factor itself. For example, if you can tolerate more queries you can choose a bigger factor and the group loses more security. But if this query tolerance is stricter, then the amount of security loss is also restricted. With all of this in mind, and because there are so many combinations of factors for each of the curves. I think the table here would be too complex to offer much value.

What do you think?

cc @armfazh also.

alxdavids commented 4 years ago

FWIW, I think this could be a separate CFRG draft

chris-wood commented 4 years ago

FWIW, I think this could be a separate CFRG draft

That's an interesting idea -- is this something you and Taylor could work on?

chris-wood commented 4 years ago

I don't think I visualize the table yet, so I can't speak to its supposed complexity, but you do make a compelling argument against it :-) How about we just keep the static DH oracle section separate and point to it from the ciphersuite section? That is, each ciphersuite could list the effective security level in the absence of these oracles, but then we point to another section which explains the oracle problem.

alxdavids commented 4 years ago

That's an interesting idea -- is this something you and Taylor could work on?

I think that's something I can definitely explore.

I don't think I visualize the table yet, so I can't speak to its supposed complexity, but you do make a compelling argument against it :-) How about we just keep the static DH oracle section separate and point to it from the ciphersuite section? That is, each ciphersuite could list the effective security level in the absence of these oracles, but then we point to another section which explains the oracle problem.

Yeah I think that will probably be the best approach. I'll write a candidate PR.

armfazh commented 4 years ago

Well, let's keep it simple. The purpose of listing the groups is to have a clear vision of all the parameters involved. Listing the security level is probably not required. We are adopting state-of-the-art group instances with well-known security bounds.

I think Section 7.1.4 gives a good explantion of security levels without going into the details.

alxdavids commented 4 years ago

This will be fixed in #121

alxdavids commented 4 years ago

121 was merged, so I don't think we have to worry any more about this.