[Verifpal] Feature request: ring signatures

Sebastian R. Verschoor srverschoor at uwaterloo.ca
Thu Feb 6 16:24:27 CET 2020


Hi Nadim,

The signature function has a small typo I think (ga should be gb)
`s = RINGSIGN(a, m, G^a, gb, gc)`
and for the verification the argument `ga` is repeated, so instead:
`_ = RINGSIGNVERIF(m, s, ga, G^b, gc)?`

However, one important detail is that the verification function does not
leak which principal actually created the signature, for example through
the argument order. In other words, the following verifications should all
succeed.
`_ = RINGSIGNVERIF(m, s, ga, gc, G^b)?`
`_ = RINGSIGNVERIF(m, s, G^b, ga, gc)?`
`_ = RINGSIGNVERIF(m, s, G^b, gc, ga)?`
`_ = RINGSIGNVERIF(m, s, gc, ga, G^b)?`
`_ = RINGSIGNVERIF(m, s, gc, G^b, ga)?`

Of course this means there are n factorial verification functions for a
signature using n keys. Maybe a more intuitive implementation would be to
instead implement this over the set of public keys (because in sets the
order does not matter):
`s = RINGSIGN(a, m, {G^a, gb, gc})`
`_ = RINGSIGNVERIF(m, s, {G^b, ga, gc})`

Thanks!
Sebastian


On Thu, 6 Feb 2020 at 09:46, Nadim Kobeissi <nadim at symbolic.software> wrote:

> Dear Sebastian,
>
> Ring signatures sounds like a great primitive to add to Verifpal. I
> propose the following interface:
>
> ```
> principal Alice[
>         knows private a
>         knows private m
>         ga = G^a
>         // Alice has previously received G^b, G^c
>         s = RINGSIGN(a, m, G^a, ga, gc)
> ]
>
> Alice -> Bob: m, s, ga
>
> principal Bob[
>         _ = RINGSIGNVERIF(ga, m, s, ga, G^b, gc)?
> ]
> ```
>
> Would this interface work for your use case?
>
> Thank you,
>
> Nadim Kobeissi
> Symbolic Software • https://symbolic.software
>
> > On 5 Feb 2020, at 10:01 PM, Sebastian Reynaldo Verschoor via Verifpal
> <verifpal at lists.symbolic.software> wrote:
> >
> > Hi,
> >
> > Not sure if this is the way to do it, but I'd like to request a new
> crypto primitive for Verifpal, namely ring signatures.
> > The reason is that I'd be interested in modelling OTRv4, where ring
> signatures are used for deniability. (In that context, I would only need
> unlinkable, untraceable signatures over three public keys, if that makes
> the request easier?)
> > As a possible alternative, I was wondering if you are planning the
> option for the user to construct their own primitives in some future
> release?
> >
> > Thanks,
> > Sebastian
> >
> >
> > _______________________________________________
> > Verifpal mailing list
> > Verifpal at lists.symbolic.software
> > https://lists.symbolic.software/mailman/listinfo/verifpal
>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <https://lists.symbolic.software/pipermail/verifpal/attachments/20200206/1c17582f/attachment.htm>


More information about the Verifpal mailing list