[Verifpal] Feature request: ring signatures

Sebastian Verschoor sebastian.verschoor at gmail.com
Wed Feb 12 06:24:28 CET 2020


Hi Nadim,

Unfortunately I am not very proficient in go, so I couldn't say to much
about the code directly.

However, I can understand the tests you wrote. To be honest, I am a bit
surprised that the first test succeeds. I would have expected
`authentication? Bob -> Damian: m` to fail, as a ring-signature does not
provide such a guarantee. Instead, it guarantees `authentication? {Alice,
Bob, Carol} -> Damian: m`. I don't think Verifpal currently has the syntax
to express this. I played a bit with it here:
https://gist.github.com/sebastianv89/bbab7402dcd047923254aab392c7f675 but
that code gives an error.

The second test fails for the right reason, so that is a good indication.

Best,
Sebastian

On Fri, 7 Feb 2020 at 14:47, Nadim Kobeissi <nadim at symbolic.software> wrote:

> Sebastian,
>
> It would be nice to get your feedback on this:
>
> https://source.symbolic.software/verifpal/verifpal/commit/fbc4d7372c0fe7df484d7331f045ff5710a63d37
>
> https://source.symbolic.software/verifpal/verifpal/commit/29c0f2121c4e9bb0ce377e0571defc46c551b275
>
> You can try it yourself by compiling Verifpal straight from the master
> branch.
>
> Looking forward to hearing your thoughts,
>
> Nadim Kobeissi
> Symbolic Software • https://symbolic.software
>
> > On 6 Feb 2020, at 11:06 PM, Nadim Kobeissi <nadim at symbolic.software>
> wrote:
> >
> > Hi Sebastian,
> >
> > I see what you mean; I’ll endeavor to have this supported in Verifpal
> soon. If you have other suggestions, please communicate them!
> >
> > Thanks,
> >
> > Nadim Kobeissi
> > Symbolic Software • https://symbolic.software
> >
> >> On 6 Feb 2020, at 4:26 PM, Sebastian Verschoor <
> sebastian.verschoor at gmail.com> wrote:
> >>
> >>
> >>
> >> On Thu, 6 Feb 2020 at 10:24, Sebastian R. Verschoor <
> srverschoor at uwaterloo.ca> wrote:
> >> 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/20200212/caac3ac9/attachment.htm>


More information about the Verifpal mailing list