Efficient Functional Commitments for Cryptographic Applications

Lattice Lattice- -Based Functional Commitments: Based Functional Commitments: Fast Verification and Cryptanalysis Fast Verification and Cryptanalysis Hoeteck Wee and David Wu December 2023

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

Functional Commitments ? Commit commitment ? Commit crs,? ?,st Takes a common reference string and commits to an input ? 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 ?(?) ? ? Can also consider the dual notion where user commits to the function? and opens at an input ? to the value ?(?) Commit crs,? ?,st Open st,? ? Takes the commitment state and an input ? and outputs an opening ? Verify crs,?, ?,? ,? 0/1 Checks whether ? is valid opening of ? to value ? at input ?

Functional Commitments ? Open + Verify ?(?) ? ? Can also consider the dual notion where user commits to the function? and opens at an input ? to the value ?(?) Commit crs,? ?,st Open st,? ? Takes the commitment state and an input ? and outputs an opening ? This talk: will just focus on the first notion (commit to ?, open 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 ?(?) ? ? Succinctness: commitments and openings should be short Short commitment: ? = poly ?,log ? Short opening: ? = poly ?,log ? , ? ? Will consider relaxation where ? and ? can grow with depth of the circuit computing ? Fast verification: can preprocess ? into a short verification key vk? so that online verification runs in time poly ?,log ? ,? where ? is the depth of ?

Functional Commitments ? Open + Verify ?(?) ? ? Succinctness: commitments and openings should be short Short commitment: ? = poly ?,log ? Short opening: ? = poly ?,log ? , ? ? fast verification (e.g., verification procedure in [WW23] basically evaluates ? on the commitment) Note: having short commitments + openings does not imply Fast verification: can preprocess ? into a short verification key vk? so that online verification runs in time poly ?,log ? ,? where ? is the depth of ?

Lattice-Based Functional Commitments crs ? ? Scheme Function Class FV BB Assumption [KLVW23] Boolean circuits 1 1 1 LWE ?5 width-?, depth-? circuits twin-?-?-ISIS [BCFL23] 1 1 2 depth-? circuits BASISstruct [WW23] 1 1 2? degree-? polynomials ?-?-ISIS [ACLMT22] 1 1 5? degree-? polynomials twin-?-?-ISIS [BCFL23]* 1 1 ?+1 ?( ?)-succinct SIS degree-? polynomials This work 1 1 is the input length FV: scheme supports fast verification BB: scheme only makes black-box use of cryptography *can decrease CRS size at the cost of longer openings Comparisons ignore all poly ?,?,log terms This talk: only consider lattice-based functional commitment schemes

Lattice-Based Functional Commitments crs ? ? Scheme Function Class FV BB Assumption [KLVW23] Boolean circuits 1 1 1 LWE ?5 width-?, depth-? circuits twin-?-?-ISIS [BCFL23] 1 1 2 depth-? circuits BASISstruct [WW23] 1 1 2? degree-? polynomials ?-?-ISIS [ACLMT22] 1 1 5? degree-? polynomials twin-?-?-ISIS [BCFL23]* 1 1 ?+1 ?( ?)-succinct SIS degree-? polynomials This work 1 1 Concurrent works: [FLV23]: polynomial commitment with linear-size CRS from ?-?-ISIS assumption [CLM23]: functional commitment for quadratic functions with linear linear-size CRS from vanishing SIS

Lattice-Based Functional Commitments crs ? ? Scheme Function Class FV BB Assumption [KLVW23] Boolean circuits 1 1 1 LWE ?5 width-?, depth-? circuits twin-?-?-ISIS [BCFL23] 1 1 2 depth-? circuits BASISstruct [WW23] 1 1 2? degree-? polynomials ?-?-ISIS [ACLMT22] 1 1 5? degree-? polynomials twin-?-?-ISIS [BCFL23]* 1 1 ?+1 ?( ?)-succinct SIS degree-? polynomials This work 1 1 functional commitments 1 [KLVW23] Boolean circuits 1 1 LWE depth-? circuits [dCP23] 1 SIS 2 depth-? circuits -succinct SIS This work 1 1 dual functional commitments This talk: only consider lattice-based functional commitment schemes

This Work Functional commitments with fast verification (and black-box use of cryptography) Functional commitment for degree-? polynomials with ? ?+1-size CRS Previously: ? 2?-size CRS Dual functional commitment for (bounded-depth) Boolean circuits First construction to support fast verification (without non-black-box use of cryptography) This talk Cryptanalysis of knowledge versions of the new lattice assumptions Construct oblivious sampler that (heuristically) falsifies the knowledge ?-?-ISIS assumption in [ACLMT22] Approach breaks extractability of several lattice-based functional commitments (our construction and the [ACLMT22] extractable commitment for linear functions) This talk Attacks do not break standard binding security of the commitment nor does it (currently) give an attack on the SNARK candidates based on knowledge ?-?-ISIS [ACLMT22, CLM23, FLV23] but does break the underlying knowledge assumption for these SNARK candidates

Starting Point: the Wee-Wu Functional Commitment [WW23] Common reference string (CRS) trapdoor for matrix related to ?,?1, ,? ? ? ? ? ? ? ? ? ?1 ? ? ? Commitment relation (for all ? ) ?? ? ? ?? ? ?? commitment gadget matrix opening (matrix with short entries) Trapdoor in CRS allow for joint sampling of ?,?1, ,? Structure does not support fast verification for polynomials of degree ? > 1 commitment to -dimensional vectors ? 0,1

Our Approach: A Chaining Structure Common reference string (CRS) ? ?1 ? trapdoor for matrix related to ?,??,??? ?1,1 ?1, More structure in the CRS ? ,1 ? , [WW23] relation: ??? = ??? ??? This work: ??? = ??? ??? ???? = ???? ???? Will also assume require that ?be a short matrix

Our Approach: A Chaining Structure ??? = ??? ??? ???? = ???? ???? Given commitment ? to ? 0,1 , we construct an opening to ???? as follows: ????2 function of commitment and public parameters

Our Approach: A Chaining Structure ??? = ??? ??? ???? = ???? ???? Given commitment ? to ? 0,1 , we construct an opening to ???? as follows: = ???? ????? ????2 function of commitment and public parameters

Our Approach: A Chaining Structure ??? = ??? ??? ???? = ???? ???? Given commitment ? to ? 0,1 , we construct an opening to ???? as follows: = ???? ????? ????2 function of commitment and public parameters = ????? ?????

Our Approach: A Chaining Structure ??? = ??? ??? ???? = ???? ???? Given commitment ? to ? 0,1 , we construct an opening to ???? as follows: = ???? ????? ????2 function of commitment and public parameters = ????? ????? = ????? ? ???? + ???? opening for ???? (short if ?,??,??,?? short)

Our Approach: A Chaining Structure ??? = ??? ??? ???? = ???? ???? Given commitment ? to ? 0,1 , we construct an opening to ???? as follows: = ???? ????? ????2 function of commitment and public parameters = ????? ????? = ????? ? ???? + ???? opening for ???? (short if ?,??,??,?? short) Verification procedure: compute ????2 and check above relation

Our Approach: A Chaining Structure ??? = ??? ??? ???? = ???? ???? Given commitment ? to ? 0,1 , we construct an opening to ???? as follows: = ???? ????? ????2 function of commitment and public parameters = ????? ????? = ????? ? ???? + ???? Online verification just computes ???2, which is independent of input length Can precompute ??= ?,??????? Verification procedure: compute ????2 and check above relation To open to ? ? = ?,????????, verifier computes ?,????????2

How to Construct ?, ??,???? ??? = ??? ??? ???? = ???? ???? Approach: sample trapdoor for following matrix ?1 ? ?11 ? ? ? ?1 ? ?11 ? ?1? ? ? ?1?1 ? ? ? ? ? can use the trapdoor to sample ?,??,??? that satisfies relation for any ? Size of full trapdoor:?( 4)

How to Construct ?, ??,???? ??? = ??? ??? ???? = ???? ???? Approach: sample trapdoor for following matrix Opening relations are linear: if ?1 is a commitment to ?1 and ?2 is a commitment to ?2, then ?1+ ?2 is a commitment to ?1+ ?2 ?1 ? ?11 ? ? ? ?1 ? ?11 ? ?1? ? ? ?1?1 ? ? ? ? Instead of publishing full trapdoor, publish commitments ? and openings ?1, ,? ,?11, ,? to basis vectors ? Size of full trapdoor:?( 4) Shorter CRS: leverage homomorphism Size of CRS:?( 3)

Evaluation Binding -succinct SIS [Wee23]: SIS is hard with respect to ? even given the trapdoor for the matrix ? ?1 ? ?11 ? The ?? s and ??? s are uniform random Assumption has less structure than BASIS assumption from [WW23] and ?- ?-ISIS assumption from [ACLMT22] ? ? ? Trapdoor for above matrix suffices to simulate CRS Can show that adversary that breaks evaluation binding solves SIS with respect to ? [see paper for details] Conclusion: functional commitment for degree-? polynomials with fast verification and ? ?+1-size CRS from ? ?-succinct SIS

Evaluation Binding -succinct SIS [Wee23]: SIS is hard with respect to ? even given the trapdoor for the matrix ? ?1 ? ?11 ? The ?? s and ??? s are uniform random Assumption has less structure than BASIS assumption from [WW23] and ?- ?-ISIS assumption from [ACLMT22] ? ? ? Trapdoor for above matrix suffices to simulate CRS Previous (black-box) lattice-based constructions with fast verification: ? 2?-size CRS Can show that adversary that breaks evaluation binding solves SIS with respect to ? [see paper for details] Conclusion: functional commitment for degree-? polynomials with fast verification and ? ?+1-size CRS from ? ?-succinct SIS

Cryptanalysis of Lattice Cryptanalysis of Lattice- -Based Knowledge Assumptions Based Knowledge Assumptions

Cryptanalysis of Lattice-Based Knowledge Assumptions Typical lattice-based knowledge assumption (to get extractable commitment / SNARK): ? ? ? ? short given (tall) matrices ?,?and short preimages ?of a random target ? the only way an adversary can produce a short vector ? such that ?? is in the image of ? (i.e., ?? = ??) is by setting ? = ?? Observe: ?? for a random (short) ? is outside the image of ?(since ?is tall)

Obliviously Sampling a Solution Typical lattice-based knowledge assumption (to get extractable commitment / SNARK): ? ? ? ? short This work: algorithm to obliviously sample a solution ?? = ??without knowledge of a linear combination ? = ?? Rewrite ?? = ?? as ? If ? and ? are wide enough, we (heuristically) obtain a basis for ? ?? ? ?? = ? ? 1?

Obliviously Sampling a Solution This work: algorithm to obliviously sample a solution ?? = ??without knowledge of a linear combination ? = ?? Rewrite ?? = ?? as ? If ? and ? are wide enough, we (heuristically) obtain a basis for ? ?? ? ?? = ? ? 1? ? Oblivious sampler (Babai rounding): 1. Take a long integer solution ? where ? ?? ? = ? mod ? 2. Assuming ? is full-rank over , find ?such that ? ? = ? (over ) 3. Set ? = ? ? ? = ? ? ? and parse into ?,? Correctness: ? ?? ? = ? ?? ? (? ? ) = ? mod ? and ? is short

Obliviously Sampling a Solution This work: algorithm to obliviously sample a solution ?? = ??without knowledge of a linear combination ? = ?? Rewrite ?? = ?? as ? If ? and ? are wide enough, we (heuristically) obtain a basis for ? ?? ? ?? = ? ? 1? ? This solution is obtained by rounding off a long solution Oblivious sampler (Babai rounding): 1. Take a long integer solution ? where ? ?? ? = ? mod ? 2. Assuming ? is full-rank over , find ?such that ? ? = ? (over ) 3. Set ? = ? ? ? = ? ? ? and parse into ?,? Question: Can we explain such solutions as taking a short linear combination of ? (i.e., what the knowledge assumption asserts) Correctness: ? ?? ? = ? ?? ? (? ? ) = ? mod ? and ? is short

Template for Analyzing Lattice-Based Knowledge Assumptions 1. Start with the key verification relation (i.e., knowledge of a short solution to a linear system) 2. Express verification relation as finding non-zero vector in the kernel of a lattice defined by the verification equation 3. Use components in the CRS to derive a basis for the related lattice 1 2 ? ?? = ?? ? ?? = ? ? 1? 3 ? ? ?? = ? ? 1?

Template for Analyzing Lattice-Based Knowledge Assumptions 1. Start with the key verification relation (i.e., knowledge of a short solution to a linear system) 2. Express verification relation as finding non-zero vector in the kernel of a lattice defined by the verification equation 3. Use components in the CRS to derive a basis for the related lattice Implications: Oblivious sampler for integer variant of knowledge ?-?-ISIS assumption from [ACLMT22] Implementation by Martin Albrecht: https://gist.github.com/malb/7c8b86520c675560be62eda98dab2a6f Breaks extractability of our functional commitment scheme for quadratic functions (i.e., obliviously sample a commitment ?and openings to ?1 Breaks extractability of the (integer variant of the) linear functional commitment from [ACLMT22] assuming hardness of inhomogeneous SIS (i.e., existence of efficient extractor for oblivious sampler implies algorithm for inhomogeneous SIS) Open question: Can we extend the attacks to break soundness of the SNARK? https://gist.github.com/malb/7c8b86520c675560be62eda98dab2a6f 2= 0,?1?2= 1)

Template for Analyzing Lattice-Based Knowledge Assumptions 1. Start with the key verification relation (i.e., knowledge of a short solution to a linear system) 2. Express verification relation as finding non-zero vector in the kernel of a lattice defined by the verification equation 3. Use components in the CRS to derive a basis for the related lattice Implications: Oblivious sampler for integer variant of knowledge ?-?-ISIS assumption from [ACLMT22] Implementation by Martin Albrecht: https://gist.github.com/malb/7c8b86520c675560be62eda98dab2a6f Breaks extractability of our functional commitment scheme for quadratic functions (i.e., obliviously sample a commitment ?and openings to ?1 Breaks extractability of the (integer variant of the) linear functional commitment from [ACLMT22] assuming hardness of inhomogeneous SIS (i.e., existence of efficient extractor for oblivious sampler implies algorithm for inhomogeneous SIS) Open question: Can we extend the attacks to break soundness of the SNARK? https://gist.github.com/malb/7c8b86520c675560be62eda98dab2a6f The SNARK considers extractable commitment for quadratic functions while our current oblivious sampler only works for linear functions in the case of [ACLMT22] 2= 0,?1?2= 1)

This Work Functional commitments with fast verification (and black-box use of cryptography) Functional commitment for degree-? polynomials with ? ?+1-size CRS Previously: ? 2?-size CRS Dual functional commitment for (bounded-depth) Boolean circuits First construction to support fast verification (without non-black-box use of cryptography) [see paper for details] Cryptanalysis of knowledge versions of the new lattice assumptions Construct oblivious sampler that (heuristically) falsifies the knowledge ?-?-ISIS assumption in [ACLMT22] Approach breaks extractability of several lattice-based functional commitments (our construction and the [ACLMT22] extractable commitment for linear functions)

Open Questions (Black-box) functional commitments with fast verification from standard SIS? Cryptanalysis of lattice-based SNARKs based on knowledge ?-?-ISIS [ACLMT22, CLM23, FLV23] Our oblivious sampler (heuristically) falsifies the assumption, but does not break existing constructions Formulation of new lattice-based knowledge assumptions that avoids our attacks Thank you!