cjpatton
commented
1 year ago Good catch, and +1 to clarifying. (Please follow up on the list, if you haven't already.)
In [DPRS23] we ended up needing extractability for the IDPF (Definition 5) in order to prove security for Doplar. However, our design is more conservative, I think due to the more flexible VDAF abstraction. in Doplar, we need to be able to extract the IDPF inputs from the random oracle even if the attacker doesn't query the leaf nodes. I think [BBCG+21] expect the IDPF to always be queried at the leaf nodes (eventually), which maybe is enough in a more restricted threat model.
cc/ @schoppmp
A recent email on the PPM list mentioned using Poplar1 and making some optimizations in the traversal of the IDPF tree. One natural way to alter the tree traversal algorithm would be to stop early before reaching the leaf level, but I'm concerned that doing so would lose the benefit of the "extractability" property, which depends on the leaf level field size being larger, and thus it could impact the whole scheme's robustness. Currently, we only mention extractability twice, in the context of the public share and the leaf level field size, but we do not explain its relevance. Is it the case that maliciously constructed reports could evaluate to "1" on multiple prefixes at some inner level, but it would be computationally infeasible to do the same on the leaf level? If so, we should outline the limitations on robustness, and possibly provide advice about skipping tree levels, i.e. to always do one last subset histogram at the leaf level. In what way do the secure sketching scheme and the extractability property contribute to the overall VDAF's robustness? Would the attack on an inner level be brute-forcing keys that produce values that pass secure sketching by pure chance, inside a ~2^-64 soundness error?