Functional Commitments: Lattice-Based Approaches and Constructions

Succinct Vector, Polynomial, and Succinct Vector, Polynomial, and Functional Commitments from Lattices Functional Commitments from Lattices Hoeteck Wee and David Wu April 2023

Functional Commitments ? Commit commitment ? opening ? Open + Verify ?(?) ? ?

Functional Commitments ? Commit commitment ? Commit crs,? ?,st Takes a common reference string and commits to a message Outputs commitment ? and commitment state st

Functional Commitments ? Open + Verify ?(?) ? ? Commit crs,? ?,st Open st,? ? Takes the commitment state and a function ? and outputs an opening ? Verify crs,?, ?,? ,? 0/1 Checks whether ? is valid opening of ? to value ? with respect to ?

Functional Commitments ? Open + Verify ?(?) ? ? Binding: efficient adversary cannot open ? to two different values with respect to the same? ?0 ?,?0 Verify crs,?, ?,?0,?0 = 1 ? ?1 ?,?1 Verify crs,?, ?,?1,?1 = 1

Functional Commitments ? Open + Verify ?(?) ? ? Hiding: commitment ? and opening ? only reveal ? ? Succinctness: commitments and openings should be short Short commitment: ? = poly ?,log ? Short opening: ? = poly ?,log ? , ? ? Special cases: vector commitments, polynomial commitments

Functional Commitment Constructions (not an exhaustive list!) Scheme Function Class Assumption [Mer87] vector commitment collision-resistant hash functions ?-type pairing assumptions [LY10, CF13, LM19, GRWZ20] vector commitment [CF13, LM19, BBF19] vector commitment groups of unknown order [PPS21] vector commitment short integer solutions (SIS) ?-type pairing assumptions [KZG10, Lee20] polynomial commitment [BFS19, BHRRS21, BF23] polynomial commitment groups of unknown order [LRY16] Boolean circuits collision-resistant hash functions + SNARKs non-falsifiable, non-black box

Functional Commitment Constructions (not an exhaustive list!) Scheme Function Class Assumption [Mer87] vector commitment collision-resistant hash functions ?-type pairing assumptions [LY10, CF13, LM19, GRWZ20] vector commitment [CF13, LM19, BBF19] vector commitment groups of unknown order [PPS21] vector commitment short integer solutions (SIS) ?-type pairing assumptions [KZG10, Lee20] polynomial commitment [BFS19, BHRRS21, BF23] polynomial commitment groups of unknown order [LRY16] Boolean circuits collision-resistant hash functions + SNARKs ?-type pairing assumptions [LRY16] linear functions ?-?-ISIS assumption (falsifiable) [ACLMT22] constant-degree polynomials This work vector commitment supports private openings, commitments to large values, linearly-homomorphic short integer solutions (SIS)

Functional Commitment Constructions (not an exhaustive list!) Scheme Function Class Assumption [Mer87] vector commitment collision-resistant hash functions ?-type pairing assumptions [LY10, CF13, LM19, GRWZ20] vector commitment [CF13, LM19, BBF19] vector commitment groups of unknown order [PPS21] vector commitment short integer solutions (SIS) ?-type pairing assumptions [KZG10, Lee20] polynomial commitment [BFS19, BHRRS21, BF23] polynomial commitment groups of unknown order [LRY16] Boolean circuits collision-resistant hash functions + SNARKs ?-type pairing assumptions [LRY16] linear functions ?-?-ISIS assumption (falsifiable) [ACLMT22] constant-degree polynomials This work vector commitment short integer solutions (SIS) ??????????? assumption (falsifiable) This work Boolean circuits BASISstruct assumption less structured than [ACLMT22]

Functional Commitment Constructions (not an exhaustive list!) Scheme Function Class Assumption [Mer87] vector commitment collision-resistant hash functions ?-type pairing assumptions [LY10, CF13, LM19, GRWZ20] vector commitment [CF13, LM19, BBF19] vector commitment groups of unknown order [PPS21] vector commitment short integer solutions (SIS) ?-type pairing assumptions [KZG10, Lee20] polynomial commitment [BFS19, BHRRS21, BF23] polynomial commitment groups of unknown order [LRY16] Boolean circuits collision-resistant hash functions + SNARKs ?-type pairing assumptions [LRY16] linear functions ?-?-ISIS assumption (falsifiable) [ACLMT22] constant-degree polynomials This work vector commitment short integer solutions (SIS) ??????????? assumption (falsifiable) This work Boolean circuits Concurrent works [BCFL22, dCP23]: lattice-based constructions of functional commitments for Boolean circuits

Functional Commitment Constructions (not an exhaustive list!) Scheme Function Class Assumption [Mer87] vector commitment collision-resistant hash functions ?-type pairing assumptions [LY10, CF13, LM19, GRWZ20] vector commitment [CF13, LM19, BBF19] vector commitment groups of unknown order [PPS21] vector commitment short integer solutions (SIS) ?-type pairing assumptions [KZG10, Lee20] polynomial commitment [BFS19, BHRRS21, BF23] [BCFL22]: short openings and supports fast verification with preprocessing; based on (falsifiable) twin-?-?-ISIS assumption polynomial commitment groups of unknown order [LRY16] Boolean circuits collision-resistant hash functions + SNARKs ?-type pairing assumptions [LRY16] linear functions ?-?-ISIS assumption (falsifiable) [ACLMT22] [dCP23]: transparent setup from SIS, long openings, selectively-secure (without complexity leveraging) constant-degree polynomials This work vector commitment short integer solutions (SIS) ??????????? assumption (falsifiable) This work Boolean circuits Concurrent works [BCFL22, dCP23]: lattice-based constructions of functional commitments for Boolean circuits

Framework for Lattice Commitments Captures and generalizes previous lattice-based functional commitments [PPS21, ACLMT22] Common reference string (for inputs of length ): ? ? matrices ?1, ,? ? ?? ?? ??? ? target vectors ?1, ,? ? auxiliary data: short preimages??? where ?????= ?? for ? ?

Framework for Lattice Commitments Captures and generalizes previous lattice-based functional commitments [PPS21, ACLMT22] Common reference string (for inputs of length ): ? ? matrices ?1, ,? ? ?? ?? ??? ? target vectors ?1, ,? ? auxiliary data: short preimages??? where ?????= ?? for ? ? : Opening to value ? at index ?: Commitment to ? ? short ?? such that ? = ? ??+ ???? Honest opening: ? = ???? Correct as long as ? is short ? ??= ????? = ????+ ???? ? = ????+ ???? = ????+ ??????? linear combination of target vectors ? ? ? ? ? ?

Framework for Lattice Commitments Captures and generalizes previous lattice-based functional commitments [PPS21, ACLMT22] Common reference string (for inputs of length ): ? ? matrices ?1, ,? ? ?? ?? ??? ? target vectors ?1, ,? ? auxiliary data: short preimages??? where ?????= ?? for ? ? [PPS21]: ?? and ?? are random suffices for vector commitments (from SIS) [ACLMT22]: ?? and ?? are structured suffices for functional commitments for constant-degree polynomials (from ?-?-ISIS)

Our Approach Captures and generalizes previous lattice-based functional commitments [PPS21, ACLMT22] Verification invariant: ? = ????+ ???? ? [ ] for a short ?? Our approach: rewrite relations as a single linear system ?1 ? ? ?1?1 ? ? ?1 ?? ?? = ? ?? denotes the identity matrix

Our Approach Captures and generalizes previous lattice-based functional commitments [PPS21, ACLMT22] Verification invariant: ? = ????+ ???? ? [ ] for a short ?? Our approach: rewrite relations as a single linear system ?1 ? ? ?1?1 ? ? ?1 ? ? = ? powers of two matrix 2 log ? 1 2 ? = For security and functionality, it will be useful to write ? = ? ? 2log ? 1 2

Our Approach Captures and generalizes previous lattice-based functional commitments [PPS21, ACLMT22] Verification invariant: ? = ????+ ???? ? [ ] for a short ?? Our approach: rewrite relations as a single linear system ?1 ? ? Common reference string: ?1?1 ? ? ?1 ? ? ? ? matrices ?1, ,? ? target vectors ?1, ,? ? auxiliary data: cross-terms??? ?? = ? ? 1??

Our Approach Captures and generalizes previous lattice-based functional commitments [PPS21, ACLMT22] Verification invariant: ? = ????+ ???? ? [ ] for a short ?? Our approach: rewrite relations as a single linear system ?1 ? ? Common reference string: ?1?1 ? ? ?1 ? ? ? ? matrices ?1, ,? ? target vectors ?1, ,? ? auxiliary data: cross-terms??? ?? = ? ? 1?? trapdoor for ? ? Trapdoor for ? can be used to sample short solutions ? to the linear system ? ? = ?(for arbitrary ?)

Our Approach Captures and generalizes previous lattice-based functional commitments [PPS21, ACLMT22] Verification invariant: ? = ????+ ???? ? [ ] for a short ?? Our approach: rewrite relations as a single linear system Committing to an input ?: ?1 ? ? ?1?1 ? ? ?1 ? ? Use trapdoor for ? to jointly sample a solution ?1, ,? , ? ? = ? ? is the commitment and ?1, ,? are the openings = ? ? Supports commitments to arbitrary (i.e., large) values over ?

Our Approach Captures and generalizes previous lattice-based functional commitments [PPS21, ACLMT22] Verification invariant: ? = ????+ ???? ? [ ] for a short ?? Our approach: rewrite relations as a single linear system Committing to an input ?: ?1 ? ? ?1?1 ? ? ?1 ? ? Use trapdoor for ? to jointly sample a solution ?1, ,? , ? ? = ? ? is the commitment and ?1, ? are the openings = ? ? Supports statistically private openings (commitment + opening hides unopened positions)

Computational Binding Captures and generalizes previous lattice-based functional commitments [PPS21, ACLMT22] Verification invariant: ? = ????+ ???? ? [ ] for a short ?? Our scheme Adversary that breaks binding can solve SIS with respect to ?? (technically ?? without the first row which is equivalent to SIS with dimension ? 1) ? ?, hard to find given ? ? short ? 0 such that ?? = ?

Basis-Augmented SIS (BASIS) Assumption Captures and generalizes previous lattice-based functional commitments [PPS21, ACLMT22] Verification invariant: ? = ????+ ???? ? [ ] for a short ?? Our scheme Adversary that breaks binding can solve SIS with respect to ?? Basis-augmented SIS (BASIS) assumption: SIS is hard with respect to ?? given a trapdoor (a basis) for the matrix ?1 ? ? ? = ?

Basis-Augmented SIS (BASIS) Assumption SIS is hard with respect to ?? given a trapdoor (a basis) for the matrix ?1 ? ? ? = ? ? ? are uniform and independent: hardness of SIS implies hardness of BASIS (follows from standard lattice trapdoor extension techniques) When ?1, ,? ? ?1 ? ? ? Sketch for ? = ?: Sample ?2, ,? with trapdoors Use trapdoors for ?2, ,? and ? to trapdoor for ? ?? ? = ?

Basis-Augmented SIS (BASIS) Assumption SIS is hard with respect to ?? given a trapdoor (a basis) for the matrix ?1 ? ? ? = ? ? ? are uniform and independent: hardness of SIS implies hardness of BASIS When ?1, ,? ? Implication: vector commitment that supports committing to large values and private openings based on SIS Previously: could only commit to small values and without hiding

Functional Commitments for Circuits Setting: commit to an input ? 0,1 , open to ?(?) (? can be an arbitrary Boolean circuit) Starting point: lattice-based homomorphic commitments [GSW13, BGGHNSVV14, GVW15] ? ? be an arbitrary matrix Let ? ? homomorphic evaluation ?1= ??1+ ?1? ??= ???+ ? ? ? ? = ?? + ? ? ?? is a commitment to ?(?) with (short) opening ?? [GVW15]: ?? is a commitment to ?? with (short) opening ??

Functional Commitments for Circuits Setting: commit to an input ? 0,1 , open to ?(?) (? can be an arbitrary Boolean circuit) Starting point: lattice-based homomorphic commitments [GSW13, BGGHNSVV14, GVW15] ? ? be an arbitrary matrix Let ? ? [GVW15]: long commitments (linear in ? ) ?1, ,? are independent ?1= ??1+ ?1? Our approach: compress ?1, ,? into a single ? ? = ?? + ? ? 1? ? where ?? ? ? ? is [GVW15]: ?? is a commitment to ?? with (short) opening ?? We will define ??= ?? part of the common reference string

Functional Commitments for Circuits Setting: commit to an input ? 0,1 , open to ?(?) (? can be an arbitrary Boolean circuit) 1? ? = ??1+ ?1? ? ? ? = ?1??1+ ?1?1? ? ? = ? ?? + ? ? ? ?1= ??1+ ?1? ?1 1? ? = ?? + ? ? ? = ?? + ? ? ?1 ? ? ?1 ? ? ?1?1? ? ? ? ??= ??? = ? Our approach: commitment is ? and set ??= ?? 1? ?

Functional Commitments for Circuits Setting: commit to an input ? 0,1 , open to ?(?) (? can be an arbitrary Boolean circuit) As in the case of vector commitments, we can publish a trapdoor for ? in the CRS (along with the matrices ?1, ,? ) ? ?1 ? ? ?1 ? ? ?1?1? ? ? ? ??= ??? = ? Homomorphic computation + opening verification now proceed as in [GVW15]

Functional Commitments from Lattices Security follows from BASIS assumption with a structured matrix: SIS is hard with respect to ? given a trapdoor (a basis) for the matrix ?1 ? ? ? = ? ? ? and ? ? ? ? where ??= ??? where ?? ? Falsifiable assumption but does not appear to reduce to standard SIS = 1 case does follow from plain SIS Open problem: Understanding security or attacks when > 1

Extensions Our functional commitment: ?1 ? ? ?1 ? ? ?1?1? ? ? ? = ? Fast verification: for linear functions (captures polynomial commitments), can preprocess and support fast verification Aggregation: can aggregate openings to ?1, ,??into single opening [see paper for details]

Summary New methodology for constructing lattice-based commitments: 1. Write down the main verification relation (? = ????+ ????) 2. Publish a trapdoor for the linear system by the verification relation Security analysis relies on basis-augmented SIS assumptions: SIS with respect to ? is hard given a trapdoor for a related matrix ? Random variant of BASIS assumption implies vector commitments and reduces to SIS Structured variant of BASIS assumption implies functional commitments

Open Questions Analyzing BASIS family of assumptions (new reductions to SIS or attacks) Describe and analyze knowledge variants of the assumption or the constructions Reducing CRS size: functional commitments with linear-size CRS? Constructing lattice-based subvector commitments Thank you! https://eprint.iacr.org/2022/1515