[Verifpal] Feature request: ring signatures

[Nadim Kobeissi]

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 --------------
A non-text attachment was scrubbed...
Name: signature.asc
Type: application/pgp-signature
Size: 833 bytes
Desc: Message signed with OpenPGP
URL: <https://lists.symbolic.software/pipermail/verifpal/attachments/20200207/faabc57b/attachment.sig>