[CFRG] Re: Incorporating OR Proofs in Sigma Protocol Draft

[Watson Ladd <[e-mail]>]

On Fri, Aug 29, 2025, 1:44 PM Cathie Yun <[e-mail]> wrote:

> Hi Lena -
>
> Thanks for the suggestion! This is something we've gone back and forth on,
> where I do see OR proofs being useful in several places, but I do think it
> adds complexity to the spec and implementation. The latter reason is why I
> suggested in IETF123 that OR proofs should be out of scope, but would be
> happy to revisit this.
>

The only bit of code required is to compute the commitment that will enable
a valid response given a challenge for an arbitrary instance. With this the
OR proof simply has to pick the challenge for the unknown arm, create the
commitments and then the responses and send.

I'll have to think how this combines with other tricks

>
> Maybe the best way forward would be to mock up what it would look like for
> the spec to support OR proofs, with an associated proof of concept in code?
> Then we can evaluate if this should be in scope for the sigma protocols, or
> a standalone "extension".
>
> Depending on your language of preference, we have python [1] and rust [2]
> proofs of concept that you are welcome to modify and open a PR to! Thanks
> so much for your enthusiasm and contributions!
>
> Thanks,
> Cathie Yun
>
> [1]
> https://github.com/mmaker/draft-irtf-cfrg-sigma-protocols/tree/main/poc
> [2] https://github.com/mmaker/sigma-rs
>
> On Wed, Aug 27, 2025 at 3:15 AM Lena Heimberger <lena=
> [e-mail]> wrote:
>
>> Dear CFRG,
>>
>> I would like to propose the inclusion of OR proofs within the Sigma
>> Protocol draft[1]. An OR proof allows a prover to demonstrate that at least
>> one of several statements is true without revealing the exact statement. A
>> common application is the construction of range proofs, which are important
>> for a number of privacy-preserving protocols. For example, Anonymous
>> Credit Tokens (ACT)[2] use range proofs to allow a client to prove that
>> their available balance is greater or equal to their spending amount
>> without revealing their exact balance. Anonymous Rate-Limited Credentials
>> (ARC)[3] uses them for nonce hiding. Other use-cases include proving the
>> validity of a timestamp or ensuring a committed value falls within other
>> defined bounds.
>>
>> Adopting a standardized construction for OR proofs within the Sigma
>> protocol framework would simplify specifying protocols like ACT and ARC,
>> which currently define their own range proofs. Future designs could benefit
>> from a reduced development time and a lower risk of implementation errors.
>> Standardization also streamlines the security analysis since the core logic
>> can be analyzed in a single place.
>>
>> I am happy to contribute a pull request to incorporate these changes and
>> look forward to the group's feedback on this proposal.
>>
>> Best regards,
>> Lena Heimberger
>>
>> [1]
>> https://datatracker.ietf.org/doc/html/draft-orru-zkproof-sigma-protocols-00
>>
>> [2]
>> https://samuelschlesinger.github.io/draft-act/draft-schlesinger-cfrg-act.html
>>
>> [3]
>> https://datatracker.ietf.org/doc/html/draft-yun-cfrg-arc#name-presentation-state
>>
>>
>> _______________________________________________
>> CFRG mailing list -- [e-mail]
>> To unsubscribe send an email to [e-mail]
>>
> _______________________________________________
> CFRG mailing list -- [e-mail]
> To unsubscribe send an email to [e-mail]
>
Astra mortemque praestare gradatim