Re: No Phone Home statement by ACLU, EFF, Brave, CDT, etc.

Good point.  Our paper is really about how to implement a ZK presentation
of the existing MDOC flow, but other possibilities exist.  Hopefully the
next few paragraphs will clarify what I have in mind.

Let's agree that server retrieval is a bad idea, and let's work in a world
where server retrieval is removed from the MDOC standard.

I claim that a sufficiently evil issuer can still communicate information
to the relying party even without server retrieval, and that this problem
is not MDOC-specific (SD-JWT would have the same problem).  All that is
needed is some sort of steganographic channel from the issuer to the
relying party.  For example, if the issuer can choose the random salts for
selective disclosure, then the issuer can easily encode a couple of bits of
undetectable information in the salted hashes.  Then the issuer can
instruct the relying party to "phone home" when the relying party detects a
certain watermark.  At least two more stenanographic channels exist because
the issuer can choose the randomness in the ECDSA signature, and because it
can generally choose the public key of the ECDSA signature.   (Forcing the
issuer to use only one signature key is a bad idea for other reasons.)

The ZK scheme in the paper hides all the salts and the ECDSA signature, and
therefore it blocks all steganographic channels except for the choice of
public key.

Our longfellow-zk system in principle allows one to hide the public key of
the issuer.  We always thought that this feature was a matter of policy,
and people in the US seem to be more worried about hiding the issuer than
people in Europe.  However, if one assumes a sufficiently evil issuer, then
hiding the issuer is necessary to block the channel between the issuer and
the relying party.

We didn't write anything about how to hide the issuer in our system, but we
talked about it in various venues and it's not a profound secret.  In one
experiment, we produced a circuit that accepts 1000 public keys and proves
that the ECDSA signature verifies under at least one of the 1000 keys,
without revealing which key.  The extra proving time and proof size were
negligible.  Thus, one can imagine a scheme where an issuer agrees in
advance to a set of keys that it is allowed to use and the prover refuses
to produce a proof if the issuer's pk is not in the set.

Another possibility would be to implement depth-one PKI chain verification
in the circuit.  That is, the issuer agrees to a small number of root keys
and uses signature keys signed by some root key.  Thus, the statement being
proven would be "I know a PK such that: there exists RK in root keys; I
know a signature of PK under RK; PK verifies the signature of my MDOC".  We
didn't implement this second scheme.  The main difficulty will be parsing
the X509 certificate, whose overhead will not be negligible.
Longer in-circuit PKI chains are likely impractical.

My tentative conclusions so far are thus that, if one takes the phone-home
issue seriously, then ZK becomes pretty much mandatory in any presentation,
and hiding the issuer may be necessary depending on the threat model.

On Thu, Jun 5, 2025 at 6:01 AM Jaromil <jaromil@dyne.org> wrote:

>
>
> Dear Matteo
>
> On 4 June 2025 21:21:35 CEST, Matteo Frigo <matteof@google.com> wrote:
> >So it seems
> >to me that there is no solution to this problem outside of a
> zero-knowledge
> >system like the one we are using in Google Wallet, where one can hide the
> >issuer's key.
>
> may I suggest you elaborate a bit more on this extension of the
> longfellow-zk algorithm? right now the published paper has just a 7 lines
> appendix about this variant, but I guess it changes the flow to remove
> PK.II from the public info. After its stated importance here I guess it
> deserves a bit more attention, I'd be grateful for it.
>
>
> thanks,
> ciao
>