A Prio Instantiation for Vector Sums with an L1 Norm Bound on Contributions

Status of This Memo

This Internet-Draft is submitted in full conformance with the provisions of BCP 78 and BCP 79.¶

Internet-Drafts are working documents of the Internet Engineering Task Force (IETF). Note that other groups may also distribute working documents as Internet-Drafts. The list of current Internet-Drafts is at https://datatracker.ietf.org/drafts/current/.¶

Internet-Drafts are draft documents valid for a maximum of six months and may be updated, replaced, or obsoleted by other documents at any time. It is inappropriate to use Internet-Drafts as reference material or to cite them other than as "work in progress."¶

This Internet-Draft will expire on 31 May 2025.¶

Copyright Notice

Copyright (c) 2024 IETF Trust and the persons identified as the document authors. All rights reserved.¶

This document is subject to BCP 78 and the IETF Trust's Legal Provisions Relating to IETF Documents (https://trustee.ietf.org/license-info) in effect on the date of publication of this document. Please review these documents carefully, as they describe your rights and restrictions with respect to this document. Code Components extracted from this document must include Revised BSD License text as described in Section 4.e of the Trust Legal Provisions and are provided without warranty as described in the Revised BSD License.¶

Table of Contents

1. Introduction

Existing Prio instantiations of a Verifiable Distributed Aggregation Function (VDAF) [VDAF] all support a simple summation of measurements. From Prio3Count (Section 7.4.1 of [VDAF]), which adds measurements containing a single one or a zero value, to Prio3SumVec (Section 7.4.3 of [VDAF]), which adds measurements containing an vector where each dimension is a limited number of bits, all instantations take the same basic form.¶

One case that is presently not included in the suite of instantiations is the addition of vectors or histogram contributions, where each measurement has an L1 bound. The L1 norm of a vector is defined as the sum of its components. An L1 bound limits that sum to some maximum.¶

This document defines the Prio3L1BoundSum instantiation. This instantiation limits the L1 norm of a vector or histogram to a value that is one less than a chosen power of 2, or 2ⁿ-1. This choice significantly reduces the size of the encoding relative to a more flexible limit.¶

This instantiation has similarities with other instantiations. Unlike Prio3Histogram (Section 7.4.4 of [VDAF]), in which measurements need to have an L1 norm of exactly 1, a valid measurement for Prio3L1BoundSum can have an L1 norm equal to any value between 0 and the chosen limit. Unlike Prio3MultiHotCountVec (Section 7.4.5 of [VDAF]), in which each component can only be zero or one, components in Prio3L1BoundSum can take any value up to the L1 bound as long as their sum is within that bound.¶

Section 3 defines the Prio3L1BoundSum VDAF.¶

2. Conventions and Definitions

The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT", "SHOULD", "SHOULD NOT", "RECOMMENDED", "NOT RECOMMENDED", "MAY", and "OPTIONAL" in this document are to be interpreted as described in BCP 14 [RFC2119] [RFC8174] when, and only when, they appear in all capitals, as shown here.¶

This document uses the terminology and functions defined in Section 2 of [VDAF].¶

3. Prio3L1BoundSum Definition

The Prio3L1BoundSum instantiation of Prio [PRIO] supports the addition of a vector of integers. The instantiation is summarized in Table 1.¶

The function takes three parameters: length, bits, and chunk_length. The vector contains "length" components, each of which is a non-negative integer less than 2^bits.¶

def encode(self, measurement: list[int]) -> list[F]:
    encoded = []
    weight = self.field(0)
    for v in measurement:
        weight += v
        encoded += self.field.encode_into_bit_vector(v, self.bits)
    w_bits = self.field.encode_into_bit_vector(weight, self.bits)
    return encoded + w_bits

def truncate(self, meas: list[F]) -> list[F]:
    return [
       self.field.decode_from_bit_vector(m)
       for m in chunks(meas, self.bits)
    ]

def decode(self, output: list[F], _count) -> list[int]:
    return [x.as_unsigned() for x in output]

def eval(self, meas: list[F],
         joint_rand: list[F], num_shares: int) -> list[F]:
    assert len(meas) == (self.length + 1) * self.bits
    shares_inv = self.field(num_shares).inv()
    parallel_sum = ParallelSum(Mul(), chunk_length)

    num_chunks = ceil(len(meas) / self.chunk_length)
    pad_len = self.chunk_length * num_chunks - len(meas)
    meas += [self.field(0)] * pad_len

    range_check = self.field(0)
    for (r, m) in zip(joint_rand, chunks(meas, self.chunk_length)):
        inputs = []
        for i in range(self.chunk_length):
            inputs += [
                r**(i + 1) * m[i],
                m[i] - shares_inv,
            ]
        range_check += parallel_sum.eval(self.field, inputs)

    components = [
        self.field.decode_from_bit_vector(m)
        for m in chunks(meas, self.bits)
    ]
    observed_weight = sum(components[:self.length])
    claimed_weight = components[self.length]
    weight_check = observed_weight - claimed_weight

    return [range_check, weight_check]

4. Security Considerations

The Prio3L1BoundSum VDAF is subject to the same considerations as other Prio-based VDAFs. These considerations are detailed in Section 9 of [VDAF].¶

In particular, this instantiation uses Field128 to ensure robustness despite the use of joint randomness in proofs. Joint randomness increases the risk of an attacker finding a combination of invalid inputs that passes validation. A larger field increases the computational cost of finding such a combination.¶

5. IANA Considerations

This document registers a codepoint for Prio3L1BoundSum in the "Verifiable Distributed Aggregation Functions (VDAF)" registry as defined by Section 10 of [VDAF]. This entry contains the following fields:¶

Value:

0xTBD¶

Scheme:

Prio3L1BoundSum¶

Type:

VDAF¶

Reference:

RFCXXXX (this document)¶

6. References

Acknowledgments

Chris Patton provided extensive input into the construction of this VDAF.¶

Authors' Addresses