We thank the reviewers for helpful comments and detailed inspection. All concerns and minor typos will be addressed. We are especially thankful for the presentation suggestion of Reviewer A for introduction and Section 5, and for the detailed input on the Definition 5 and suggestions for technical overview from Reviewer B, we will take them all in account for the final version.

General Comments –Comparison with previous work–

We recall the difference from O(m^2) in Caulk+ to O(m) in Baloo is in group operations for the prover, while in the field asymptotic efficiency is the same. In Flookup techniques are very different and the construction uses a non-homomorphic commitment to the big table; this makes it complicated to use it as a building block in many protocols, which is one of the goals for Baloo. An extra discussion is devoted to EFG22 as it is the only one that, while having homomorphic commitments, outperforms Baloo. We have only compared concrete performance with Caulk because it is, to the best of our knowledge, the only protocol that has an implementation publicly available. It is in our interests to compare with all existing constructions.

EFG22: We apologize as there is a typo in the table on the performance of cq, where it says O(m log^2 m) should be O(m log m). Please note the reported efficiency in the paragraph called "Concurrent work" is the correct one. We are especially interested in a comparison with EFG22, as the prover performance only differs asymptotically on a log(m) factor for field operations, while Baloo offers an extra feature.
Namely, in cq two lookup tables

$\overrightarrow{a}=(a_1,a_3,a_7,a_3)$ and

${\overrightarrow{a}}^{\prime }=(a_7,a_1,a_3,a_3)$ are indistinguishable. That is, given table

$\overrightarrow{t}$, the prover in cq commits to the elements taken from the public table to construct the lookup, and its repetitions, but not to the order. In Baloo, as we use a matrix to construct the lookup from the public table, the prover commits to the elements, the repetitions, and the order as well.
The difference above implies Baloo can be used for proving "repeated" lookups, meaning the same lookup operation is applied to one or two different tables, and also for the case where the lookup is made public (either because matrix

$\begin{array}{c}M\end{array}$ is public or published by the Prover after the interaction). The latter is the case in applications such as memory access or subset opening, where the system needs to keep track of the order of the elements in all tables.

Reviewer A

On the right side of page 4, once the expansion relationship is modeled as Equation (1), the paper claims that the lincheck argument is modified from [RZ21] and the inner product is also proven using the generalized univariate sumcheck in [RZ21]. It will be better to explain why the protocols in [RZ21] can’t work for a committed matrix instead of a public matrix, and what modifications in this paper are critical to make it work.

• In the protocol of [RZ21], the matrix is public and fixed. "Since M is only known by the prover in our new construction, we replace the offline phase usually performed by some untrusted party with a commitment phase performed by the prover itself" refers specifically to polynomial
  $v(X)$(that describes matrix M) in Fig.2, that is sent by the prover in Baloo but part of an offline untrusted pre-computation in [RZ21].

Reviewer B

The core underlying idea is to replace one of the building blocks in the lookup arguments of Caulk and Caulk+, with a different linear argument which is a protocol from RZ21 for proving linear relations.

The exposition is less than satisfactory: there is no clear explanation of the key technical idea that bring the prover down from quadratic to linear. Moreover, the paper seems to be written for an audience that is familiar with Caulk, Caulk+ and other closely related work.

• Exposition is incredibly important. We did spend time and effort on the writing quality but remain eager for suggestions for how to improve. We can certainly expand the background on Caulk and Caulk+. Unfortunately we cannot give you one simple core technical idea for bringing the prover time down. Caulk and Caulk+ use a protocol for proving the relation between
  $\overrightarrow{t}$ and
  $\overrightarrow{a}$ that is quadratic on the size of
  $\overrightarrow{a}$. We replace this building block, which is the bottleneck, entirely. Thus, we get rid of the quadratic computations for the prover. An overview of this new building block is given in Section 4, "Expansion as a linear relation", and we will take the reviewer's suggestion to improve it.

It is unclear why the abstraction of CSS, and commit-and-prove CSS is useful in achieving linear prover; what is the relation that shows up in look up arguments that is a natural CSS relation.

• We use the framework of [RZ21], which consists of performing a CSS+inner product. For the CSS, encode matrix
  $\begin{array}{c}M\end{array}$ as a bivariate polynomial. Then, the prover samples a vector in row space of the matrix, with random coins chosen by the verifier, and outputs a polynomial
  $D(X)$ encoding it, which will later be used for the inner product argument. The prover has to convince the verifier that
  $D(X)$ is indeed well formed.
• The CSS we use, while inspired in one of the constructions in [RZ21] (that inspires itself in Marlin), differs a lot and brings many challenges. (see CSS item on page 6)

In the Sampling phase: cns <- C. What is the space C? What is cns and the sampling algorithm Smp for s = Smp(cns)? None of these seem to be defined.

• $\mathsf{cns}$ are the random coins sampled by the Verifier, sampled from space
  $\mathcal{C}$.
  $\mathsf{Smp}:\mathcal{C}\to {\mathbb{F}}^m$ is a sampling function, in Section 5.3,
  $\mathsf{cns}=\alpha$ and
  $\mathsf{Smp}(\alpha )=({\mu }_1(\alpha ),\dots ,{\mu }_m(\alpha ))$.

Soundness: b ← ⟨P∗CSS(instance),VCSS(instance)⟩ instance is undefined. Presumably, the interactive Sample protocol determines cns and D, and that together with inst, defines the instance for the commit-and-prove protocol?

• $\mathsf{instance}$ is a tuple
  $({\mathsf{cm}}_{{\mathbb{H}}_I},{\mathsf{cm}}_{\begin{array}{c}M\end{array}},\mathsf{cns},D(X))$ as in the definition of
  ${\mathbb{R}}_{\mathsf{CSS}}$.
  $\mathsf{cns}$ and
  $D(X)$ are defined during the interaction of
  $\mathcal{P}$ and
  $\mathcal{V}$.

Section 6: what is the difference between Rlookup and Rcp-expansion? It looks like the same relation? Is the vector c part of the instance in Rlookup; is it known to the verifier?

• ${\mathbb{R}}_{\mathsf{lookup}}$ and
  ${\mathbb{R}}_{\mathsf{cp}\mathsf{-}\mathsf{expansion}}$ differ as the former compares vector
  $\overrightarrow{a}$ encoded in polynomial
  $\varphi (X)$ with the public table
  $\overrightarrow{c}\in {\mathbb{F}}^N$ while the latter compares it with a vector
  $\overrightarrow{t}$ that is potentially unknown to the verifier, that why "cp" in the name. We call it cp-expansion because we will have that all the elements in
  $\overrightarrow{t}$ are also in
  $\overrightarrow{a}$, but with repetitions, and thus
  $\overrightarrow{a}$ is an expansion of
  $\overrightarrow{t}$.