[Ppm] Some clarifications about draft-dss-star-01

[Alex Davidson <[e-mail]>]

Hi all,

I just wanted to summarise a discussion for the mailing list between the
authors of draft-dss-star-01 and Christopher Wood, related to devising
implementations of STAR.

- Implementation of secret sharing.

The STAR paper (https://arxiv.org/abs/2109.10074) and existing
implementation (https://github.com/brave/sta-rs/) uses a specific secret
sharing framework known as adept secret sharing, that uses traditional
Shamir secret sharing under the hood. This is to smooth out some aspects of
the security proof in the paper. However, adept secret sharing adds some
overheads, and we can probably use traditional secret sharing without any
problems.

- What are the parameters of the field for Shamir's scheme?

Currently, we use a fixed modulus in the implementation for either a
129-bit or 255-bit field. The field size does not impact security rather
correctness, and we can probably get away with using a 128-bit prime field
that will provide roughly 1/2^64 chance of correctness errors. A future
version of the draft will hardcode a specific modulus that can be used in
all implementations.

- Does this require a key-committing AEAD so that the same ciphertext can't
be decrypted to two different plaintexts?

This is something that could be useful, and we can specify that the
symmetric encryption used in STAR uses such an AEAD.

- What happens when the aggregation server decrypts and discovers that one
of the values does not match all the others?

This is something that seems difficult to solve, and a slight discrepancy
between STAR and other DAPs. Overall, the client must encrypt their
measurement as a plaintext value in their message, but if they encrypt a
different value we need a good way to recover.

One possibility is just to throw out batches where client plaintext
measurements do not agree (but where the deterministic tags do). However,
this may make it easy for clients to poison batches. The aggregation server
could similarly use majority vote and throw out differing plaintexts, but
this may also be vulnerable to poisoning. An alternative possibility is to
have a short crossover period where the randomness server still tolerates
queries to their VOPRF key, so that if the aggregation server uncovers
differing plaintext measurements, they are able to check which is the
correct one. However, this may harm client privacy, see next question.

- What information is leaked through the common tag? (If threshold is not
reached, you still learn when two clients sent the same measurement value,
you just don't learn what it is. Does this help brute force attacks?)

Common tags can be brute-forced in the window that the VOPRF keypair is in
action for. As long as the keypair is rotated before clients actually send
their messages for aggregation, then the aggregation server must launch the
brute-force attack without seeing any leakage from client messages.
However, if client measurements are inherently predictable, even before
they are received, then the aggregation server can learn things. Keeping
the keypair window as short as possible is the best way of ensuring client
privacy.

Ideally clients would construct message on day i, and then send them on day
i+1 after the key rotation occurs. If you need some sort of cross-over
between periods then things may become more complicated, since you may need
to keep track of multiple keys at once. But having a crossover period may
allow the aggregation server to launch brute-force attacks with the
additional leakage that is present in the messages, which may make the
attacks more efficient.

- How do you prevent Sybil attacks from the aggregation server?

Sybil attacks are possible against all DAPs, STAR does not have any
specific mechanism for dealing with them.

- Is an OPRF sufficient here? If the randomness server changes its key it
will just disrupt the ability for clients to reach the threshold.

An OPRF is probably sufficient, the VOPRF is useful for showing to the
clients that the randomness server is acting honestly. In the OPRF case,
the randomness server could simply respond with random values. This will
not harm privacy provided the two servers are non-colluding, but will
poison the aggregation.

- When will the sta-rs implementation move to an OPRF/VOPRF instead of the
PPOPRF?

The current STAR implementation uses a non-standard version of an oblivious
pseudorandom function, for devising interoperable implementations we will
probably aim to write an implementation with a CFRG-based (V)OPRF in the
near future.

Thanks,
Alex (on behalf of the authors of draft-dss-star-01)