Notes on GGH13 Without the Presence of Ideals

We investigate the merits of altering the Garg, Gentry and Halevi (GGH13) graded encoding scheme to remove the presence of the ideal \(\langle g \rangle \). In particular, we show that we can alter the form of encodings so that effectively a new \(g_i\) is used for each source group \({\mathbb {G}}_i\), while retaining correctness. This would appear to prevent all known attacks on IO candidates instantiated using GGH13. However, when analysing security in a simplified branching program model, we present an IO distinguishing attack that does not use \(\langle g \rangle \). This result opens a counterpoint with the work of Halevi (EPRINT 2015) which stated that the core computational hardness problem underpinning GGH13 is computing a basis of this ideal. Our attempts seem to suggest that there is a structural vulnerability in the way that GGH13 encodings are constructed that lies deeper than the presence of \(\langle g \rangle \). Tangentially, we observe that our attack is prevented when considering all the added machinery of IO candidates.

1. 1.

   Here we describe an asymmetric MMAP, we can equally describe a symmetric variant where \({\mathbb {G}}_1 = \cdots = {\mathbb {G}}_{\kappa } = {\mathbb {G}}\).

2. 2.

   This model allows all the same operations as the generic graded encoding model along with an additional step where the adversary is allowed to submit certain polynomial evaluations on the results of zero-testing.

3. 3.

   They are thwarted only by the usage of dual-input branching programs which are external to the security model considered. In fact, they note that parts of their attack take place externally to the WGEM and thus suggest that the model is incomplete.

4. 4.

   We use \(5 \times 5\) matrices as these are sufficient for Barrington’s theorem [Bar89].

5. 5.

   The bundling scalars ensure that inputs \(x\) satisfying \(C(x) = 1\) satisfies \(\widehat{\mathcal {M}} _C(x) \ne [0]_\mathcal {U}{}\).

6. 6.

   After each iteration the output is also scaled by the coefficients used previously so these need to be taken account for in further operations.

7. 7.

   We ignore the usage of each \(z_l\) in the encodings for now as these are removed after zero-testing.

8. 8.

   It may be wise to no longer think of these random invertible matrices as offering any security when analysing IO candidates.

9. 9.

   The exact magnitude is not important for the attack in [MSZ16a] as long as \(h \ll q\).

10. 10.

    It is possible to find inputs for both circuits that allow the adversary to construct a basis of \(\langle g \rangle \).

Authors and Affiliations

1. Royal Holloway, University of London, Egham, UK

   Martin R. Albrecht, Alex Davidson & Enrique Larraia

Corresponding authors

Correspondence to Martin R. Albrecht or Alex Davidson .

Editors and Affiliations

1. Queen’s University Belfast, Belfast, United Kingdom

   Máire O'Neill

A Multilinear Jigsaw Puzzles

Typically, IO candidates are instantiated via multilinear jigsaw puzzles (MJPs) — a restricted variant of a GES where lower-level encodings of zero are not permitted and only certain types of multilinear form can be computed. From now on we will use the following MJP formalisation when referring to the functionality required for constructing IO rather than the wider GES framework.

Definition 2

(MJP Scheme). A multilinear jigsaw puzzle consists of two algorithms \((\mathsf {JGen},\mathsf {JVer})\) that generate the puzzle and verify a solution to the puzzle, respectively. We explain the algorithms in detail.

• Puzzle generation: The algorithm \(\mathsf {JGen} \) comprises the triple of sub-algorithms \((\mathsf {JInstGen},\mathsf {JEnc},\mathsf {JGenPuzz})\) described as such:

  –:

  \(\mathsf {JInstGen} (1^{\lambda },1^\kappa ):\) On input the security parameter \(\lambda \) and multilinearity \(\kappa \), this algorithm outputs a set of private parameters \(\mathsf {sk} \) needed to encode ring elements, and a set of public parameters \(\mathsf {pp} = (\mathsf {prms},\mathsf {evk},\mathsf {ztk})\). The last two components of the public tuple are necessary to perform algebraic operations over the encodings, and for zero-testing, respectively. The system-wide parameters \(\mathsf {prms} \) include a prime q defining the working ring, a set universe \(\mathcal {U}\), and a partition \(\{\mathcal {S}_1,\ldots ,\mathcal {S}_\kappa \}\) of \(\mathcal {U}\).

  –:

  \(\mathsf {JEnc} (\mathsf {prms},\mathsf {sk},\mathcal {S},a):\) On input \(\mathsf {sk} \), a set \(\mathcal {S}\subset \mathcal {U}\) and \(a \in {\mathbb {Z}}_q\), this algorithm outputs an encoding v relative to the set \(\mathcal {S}\).

  –:

  \(\mathsf {JGenPuzz} (1^{\lambda },1^\kappa ,l,A):\) Takes as input the security and multilinearity parameters, \(l \in \mathbb {N}\) and a set \(A = (A_1,\ldots ,A_l)\), where \(A_i\) is a set of values \(\{a_j\}_{j \in [m_i]}\) that will be encoded with respect to index set \(\mathcal {S}_i\). First it runs \(\mathsf {JInstGen} (1^{\lambda },1^\kappa )\) to receive system parameters \((\mathsf {sk},\mathsf {pp} =(\mathsf {prms},\mathsf {evk},\mathsf {ztk}))\). It then runs \(\mathsf {JEnc} \) on inputs \((\mathsf {prms},\mathsf {sk})\) and each element \((\mathcal {S}_i,a_j) \in A_i\) to receive encodings \((\mathcal {S}_i,v_j) \in C_i\).

• Let \(\mathsf {puzzle} = (C_1,\ldots ,C_l)\) and let \(X = ((\mathcal {S}_1,v_1), \ldots , (\mathcal {S}_l,v_l))\), then we define \((X,\mathsf {puzzle})\) as the output of \(\mathsf {JGen}\) where X is kept secret and \(\mathsf {puzzle}\) is the public output.

• Puzzle verification: Algorithm \(\mathsf {JVer}\) takes as input the public parameters \(\mathsf {pp} =(\mathsf {prms},\mathsf {evk},\mathsf {ztk})\), the public output \(\mathsf {puzzle}\) of \(\mathsf {JGen}\) and some multilinear form F (the solution to the puzzle). It outputs either acceptance or rejection. More formally, following [MSZ16a], we split the verification into three sub-algorithms \(\mathsf {JVer} = (\mathsf {JCompute},\mathsf {JZTParam},\mathsf {JTest})\). This helps in capturing the weakened grading encoding security model [MSZ16a, GMM+16].

  –:

  \(\mathsf {JCompute} (\mathsf {prms},\mathsf {evk},\mathsf {puzzle},F):\) On input the encodings in \(\mathsf {puzzle}\) and some valid multilinear form F, outputs the encoding \((\mathcal {S},v) = F(\mathsf {puzzle})\) for \(\mathcal {S}{} \subseteq \mathcal {U}{}\). We will sometimes abuse notation and simply write the output of the algorithm as \(F(\mathsf {puzzle})\).

  –:

  \(\mathsf {JZTParam} (\mathsf {prms},\mathsf {ztk},(\mathcal {S},v)):\) On input encoding \((\mathcal {S},v)\) it first checks if \(\mathcal {S}=\mathcal {U}\) and if not aborts. If true, it outputs the ring element \(\delta \). In an honest execution we have that \((\mathcal {S},v)\leftarrow \mathsf {JCompute} (\mathsf {puzzle},F)\).

  –:

  \(\mathsf {JTest} (\mathsf {prms},\delta ):\) On input ring element \(\delta \) it returns 1 or 0. In an honest execution we have that \(\delta \leftarrow \mathsf {JZTParam} (\mathsf {prms} {},\mathsf {ztk} {},(\mathcal {U},v))\).

In the above definition, by valid multilinear form, we mean some sort of computation that respects the computation laws of a graded encoding scheme and outputs a top-level encoding [GGH+13b]. For instance, for any encodings \((\mathcal {S}_1,v_1),(\mathcal {S}_2,v_2)\) we have an addition operation that is defined when \(\mathcal {S}= \mathcal {S}_1 = \mathcal {S}_2\) and outputs the encoding \((\mathcal {S},v_1+v_2)\). We also have multiplication that is defined when \(\mathcal {S}_1 \cap \mathcal {S}_2 = \emptyset \) and results in an encoding \((\mathcal {S},v_1 \cdot v_2)\) for \(\mathcal {S}= \mathcal {S}_1 \cup \mathcal {S}_2\). The output of these operations is said to be a top-level encoding when \(\mathcal {S}= \mathcal {U}\).

Definition 3

(MJP Correctness). A jigsaw verifier \(\mathsf {JVer} \) is correct for a tuple \((\mathsf {pp},(X,\mathsf {puzzle}),F)\) if either \(F(X) = (\mathcal {U}, 0)\) and \(\mathsf {JVer} (\mathsf {puzzle},F) = 1\) or \(F(X) \ne (\mathcal {U},0)\) and \(\mathsf {JVer} (\mathsf {puzzle},F) = 0\). Otherwise it is incorrect on \(F\).

We specifically require that \(\mathsf {JVer}\) is correct on all but negligibly many forms (see [GGH+13b] for an explanation of the requirement).

Security. Characterising the security that should be offered by a MJP is one of the difficulties confronted by constructions of IO. In short, constructions of IO are proven secure in a generic model where encodings are treated as random handles and all operations that can be performed are interacted with via oracle calls. Yet, as discussed above, current MJP constructions do not justify the use of such a model, i.e. they are broken by attacks which fall our side of this model. See [MSZ16a, GMM+16] for more details.

B MJP from Our Encoding Scheme

Using the encodings that we describe in Sect. 3.1 we can now construct an MJP scheme. Note that we refer to jigsaw generation and verification as both algorithms and as specific roles within a computation interchangeably.

1.1 B.1 Setup

Instance Generation. (\(\mathsf {JInstGen}\)): On input the security parameter \(1^{\lambda }\), and perceived multilinearity \(\kappa \) the algorithm does the following:

• Samples the prime integer q

• Samples \(\kappa \) uniform polynomials \(z_i\) from the ring \(R_q\)

• Samples \(\kappa \) polynomials \(\beta _i\) fulfilling the requirements set out in Sect. 3

• Outputs \((\mathsf {sk} {},\mathsf {pp} {}) = ((\beta _i,z_i),(\{\mathcal {S}_i\}_{i \in [\kappa ]},q))\)

Encoding. (\(\mathsf {JEnc}\)): This algorithm takes as input some value \(\alpha \), an index set \(\mathcal {S}_i\) and a pair \((\beta _i,z_i) = \mathsf {sk} {}\) sampled from \(\mathsf {JInstGen}\) and:

• Samples a small element r uniformly from the error distribution \(\chi \)

• Computes \(v = \frac{\alpha + r/\beta _i}{z_i}\) as an encoding of the value \(\alpha \)

Jigsaw Generation. (\(\mathsf {JGen}\)): Takes as input an index set \(\mathcal {S}_i\), the pair \((\beta _i,z_i)\) for \(i \in [\kappa ]\) and associated encoded values \((\alpha _1, \ldots , \alpha _{m_i})\) for each of these pairs, where \(m_i\) is the number of values to be encoded with respect to \(\mathcal {S}_i\). Then this algorithm performs the following:

• Inputs each tuple \((\mathcal {S}_i,\alpha _j)\) for \(j \in [m_i]\) to the encode algorithm \(\mathsf {JEnc}\) and receives back the \(\kappa \) sets \(C_i\) where \(C_i\) consists of all pairs \((\mathcal {S}_i,v_j)\) for \({1 \le j \le m_i}\).

• Generates the zero-testing parameter \(p_{zt}\) by computing

  $$\begin{aligned} p_{zt}= \prod \limits _{i=1}^\kappa \beta _i \cdot z_i \end{aligned}$$

  .

• Creates

  $$\begin{aligned} \mathsf {puzzle} = (q,\{C_1,\ldots ,C_\kappa \},p_{zt}) \end{aligned}$$

  (7)

  as the public output. Let \(\varvec{\alpha }^{(i)}\) be the set of values \(\{\alpha _1,\ldots ,\alpha _{m_i}\}\) that are encoded with respect to \(\mathcal {S}_i\) — then the private output is defined as

  $$\begin{aligned} X = (\varvec{\alpha }^{(1)}, \ldots , \varvec{\alpha }^{(\kappa )}). \end{aligned}$$

Note that the values r, \(\beta \) and z are all kept secret in order to preserve the secrecy of the encoded values. Public access to each \(\beta _i\) and \(z_i\) is granted in the form of the zero-test parameter \(p_{zt}\), though it should be impossible to decompose this into the individual factors.

1.2 B.2 Jigsaw Verification

As before, we note that the zero-test procedure is split into three separate algorithms to accurately model the security setting that we consider. These three algorithms are defined as the following:

Computation. (\(\mathsf {JCompute}\)): Takes as input the encodings \(v^{(i)}_j\) with respect to each index set \(\mathcal {S}_i\) and a multilinear form, F, and outputs

where \(v^*\) is a top-level encoding as shown in Equation (4).

Zero-Testing. (\(\mathsf {JZTParam}\)): Takes as input an encoding \(v^*\) resulting from the \(\mathsf {JCompute} \) algorithm and \(p_{zt}\) from \(\mathsf {puzzle}\) and output \(\delta = p_{zt}\cdot v^*\)

Zero-Test Output. (\(\mathsf {JTest}\)): Takes \(\delta \) as an output from the \(\mathsf {JZTParam} \) algorithm and checks the magnitude of the element. If it has magnitude greater than \(\prod _{i=1}^\kappa \beta _{i} \) then output 1 (encoded value is zero). Otherwise output 0 (encoded value is non-zero).

Finally the overarching \(\mathsf {JVer}\) algorithm defined previously simply runs these three algorithms in sequence and outputs the result of \(\mathsf {JTest}\) .

1.3 B.3 Correctness of Construction

The homomorphic properties of our encodings as shown in the previous section enable us to evaluate the multilinear forms that are input to the \(\mathsf {JCompute}\) algorithm. Correctness is lost post-zero-testing if wrap-around modulo q occurs for a top-level encoding, or if an encoding of zero exceeds \(q^{\frac{\kappa -1}{\kappa }}\). Since we specifically sample the \(\beta _i\) elements from \(R_q\) such that we satisfy these requirements and since each of the sampled elements are small.

C  Additional Ring Preliminaries

Canonical Embeddings. Let \(\zeta _{m}\) denote a primitive \(m\)-th root of unity. The \(m\)-th cyclotomic number field \(Q = \mathbb {Q}(\zeta _{m})\) is the field extension of \(\mathbb {Q}\) obtained by adjoining \(\zeta _{m}\). Let \(n\) be the degree of \(K\) over \(\mathbb {Q}\), then there are \(n\) embeddings \(\sigma _{i}\) of \(K \rightarrow \mathbb {C}\). These \(n\) embeddings correspond precisely to evaluation in each of the \(n\) distinct roots \(\alpha _{i}\) of \(\phi (x)\). In our case, \(\psi (x)\) has \(2\cdot s_{2} = n\) complex conjugate roots. Order the roots such that \(\overline{\alpha _{k}} = \alpha _{s_{2} +k}\) for \(k = 1, \dots , s_{2}\). The canonical embedding \(\sigma : K \rightarrow \mathbb {C}^{n}\) is defined as

The canonical embedding maps into a space \(H \subset \mathbb {C}^{n}\) given by

which is isomorphic to \(\mathbb {R}^{n}\) and we can represent the coordinates of \(\sigma (a)\) by a real vector [CIV16]

This naturally induces a geometry on \(K\) with \(\ell _{2}\)-norm \(\Vert \cdot \Vert _{2}\) and \(\ell _{\infty }\)-norm \(\Vert \cdot \Vert _{\infty }\):

Bounded Distributions. When sampling our encodings we are required to define a B-bounded distribution, where all elements sampled from this distribution have an \(l_\infty \) norm that is bounded by B. In this section we will formally define such a distribution.

Definition 4

(B-bounded element). An element \(p \in R\) is called B -bounded if \({\Vert {p}\Vert }_\infty \le B\).

Definition 5

(B-bounded distribution). A distribution ensemble \({\{\chi _\lambda \}}_{\lambda \in \mathbb {N}}\), supported over R, is called B-bounded (for \(B = B(\lambda )\)) if for all p in the support of \(\chi _\lambda \), we have \({\Vert {p}\Vert }_\infty < B\). In other words, a B-bounded distribution over R outputs a B-bounded polynomial.

Lemma 1

([LTV12]). Let \(n \in \mathbb {N}\), let \(\phi (x) = x^n + 1\) and let \(R = {\mathbb {Z}}[x]/\langle \phi (x) \rangle \). For any \(s,t \in R\),

Corollary 1

([LTV12]). Take \(n,\phi (x),R\) as before. Let where \(\chi \) is a B-bounded distribution over the ring R. Then is \((n^{k-1}B^k)\)-bounded.

Gaussian Sampling. For any real \(r > 0\) the Gaussian function on \(\mathbb {R}^n\) centred at \(\mathbf {c}{}{}\) with parameter r is defined as:

Definition 6

For any \(n \in N\) and for any \(\mathbf {c}{}{}\in \mathbb {R}^n\) and real \(r > 0\), the Discrete Gaussian distribution over \({\mathbb {Z}}^n\) with standard deviation r and centred at \(\mathbf {c}{}{}\) is defined as:

where is a normalisation factor.

The work of [MR04] showed that the discrete Gaussian distribution over \({\mathbb {Z}}^n\) with standard deviation r outputs elements that are (\(r\sqrt{n}\))-bounded with high probability (\(\ge 1 - 1/2^{-n+1}\)). We can then define the truncated Gaussian distribution that is \((r\sqrt{n})\)-bounded and is statistically close to the discrete Gaussian.

The truncated Gaussian with standard deviation r and centred at \(\mathbf {c}{}{}\) will be denoted by \(\bar{D}_{{\mathbb {Z}}^n,r,\mathbf {c}{}{}}\) and can be defined by sampling polynomials according to the discrete Gaussian (\(D_{{\mathbb {Z}}^n,r,\mathbf {c}{}{}}\)) and repeating any samples that are not \((r\sqrt{n})\)-bounded. We note that this distribution is statistically close to \(D_{{\mathbb {Z}}^n,r,\mathbf {c}{}{}}\) as shown in [LTV12]. For the case where \(\mathbf {c}{}{}= 0\) we will simply write \(\bar{D}_{{\mathbb {Z}}^n,r}{}\).

Our GES (Sect. 3) relies on distinguishing between products of \(\kappa -1\) and \(\kappa \) elements. For this, we sample real vectors \(\left( \tilde{a}_{1}, \ldots , \tilde{a}_{n} \right) \) with each coordinate sampled from a Gaussian distribution conditioned on a minimum size through rejection sampling. Mapping these real vectors to elements in \(K\) produces the desired distribution in \(K\). We then discretise, i.e. randomised round each coordinate to an integer to obtain elements in \({\mathbb {Z}}[x]/\langle \phi (x)\rangle \) as usual.

Thus, we may infer the magnitude of elements that are sampled from certain distributions and latterly what the magnitude of such an element is expected to be after multiplying any number of these elements is. We can use this information to make statements on the size of encodings that are made up of elements sampled from such B-bounded distributions.

D GGH13 and Annihilation Attacks

1.1 D.1  GGH13 Overview

The space for GGH13 encodings is \(R_q = R/qR\) where q is some big integer and \(R = {\mathbb {Z}}[x]/(x^m + 1)\) for \(m \in \mathbb {N}\). The plaintext ring is defined by \(R_g = R/gR\) where g is a small element in the ring. A GGH13 encoding takes the form \(v = (\alpha + rg)/z \mod q\) where z is some uniformly random value — z and g are secret — \(\alpha \) is the encoded plaintext value and r is some small random value, all these values are sampled from some error distribution, \(\chi \), over \(R_q\).

The denominators \(z\) enforce the levels of the GES, where we can sample one global \(z\) for the symmetric case and \(z_1,\ldots ,z_\kappa \) in the asymmetric case, we will consider the asymmetric case unless otherwise stated. Where an encoding \(v\) has a denominator \(z_i\) we will say that \(v\) is encoded at level \(\mathcal {S}_i\) where there are \(\kappa \) such index sets. Additions and multiplications are carried out by simply adding and multiplying encodings directly. Clearly, additions of encodings indexed at the same level results in another encoding at that level. Multiplying two encodings, indexed by \(z_1\) and \(z_2\) respectively, results in an encoding at level \(\mathcal {S}_1 \cup \mathcal {S}_2\).

Finally, there is a public zero-test parameter

for some ‘smallish’ \(h \in R_q\).^{Footnote 9} We can learn whether an encoding \((\mathcal {U},v)\) (e.g. top-level with denominator \(z_1 \cdot \cdots \cdot z_\kappa \)) encodes zero or not by computing \(p_{zt}\cdot v\) and seeing if the result is small.

The functionality described can be adapted to construct a correct MJP scheme [GGH+13b].

1.2 D.2  Annihilation Attacks on GGH13

Let \(\widehat{\mathcal {M}} {}\) be a randomised branching program that has entries encoded as GGH13 elements and each pair of matrices \(\widehat{M}_{b,l}{}\) and bookends \(\widehat{M}_0{},\widehat{M}_{L+1}{}\) are encoded with respect to the levels \(l \in \{0,\ldots ,L+1\}\). Let \(x \in \mathcal {X} {}\) be some valid input for \(\widehat{\mathcal {M}} \) and let \(\mu _x \leftarrow \widehat{\mathcal {M}} (x)\) be the output. Finally denote \(\delta _x = p_{zt}\cdot \mu _x = \mathsf {JZTParam} (\mu _x)\) as the zero-tested output.

A top-level GGH13 encoding will have the following form:

after zero-testing has occurred. The target of the annihilation attacks is the polynomial \(\gamma _{1,x}(\alpha ,r)\) which is linear in the unknown sampled elements \(r_j\) from each encoding \(v_j\). Using a change of variables in the branching program it is possible to assume that the adversary has knowledge of the values \(\alpha _j\) that are encoded in each of the matrices [MSZ16a] (see Sect. 4.3 for more details). By choosing enough inputs \(x\) such that \(\alpha _x = 0\), the adversary is able to guarantee that there exists an annihilating polynomial \(Q\) for the set of \(\gamma _{1,x}\) polynomials [Kay09]. In fact, the work of [MSZ16a] explicitly gives a description of \(Q\) for a given single-input branching program \(\mathcal {M} \).

Consequently, the result \(\rho _x \leftarrow Q(\{\delta _x\}_x)\) results in some output where the \(\gamma _{1,x}\) polynomials are eliminated. In particular, this means that \(\rho _x \in \langle g \rangle {}\). By computing enough outputs, an adversary can heuristically construct a basis of \(\langle g \rangle {}\). The attack concludes by specifying a functionally equivalent \(\mathcal {M} '\) where the set of polynomials \(\gamma '_{1,x}\) are not annihilated by \(Q\). The work of [MSZ16a] show that it is possible to construct \(\mathcal {M},\mathcal {M} '\) such that a PPT adversary with obfuscated access to either of the circuits can first construct a basis of \(\langle g \rangle \) ^{Footnote 10} and then secondly distinguish between the circuits. Distinguishing is possible since \(\rho '_x \leftarrow \widehat{\mathcal {M}} '(x)\) is not in \(\langle g \rangle {}\) and so they are able to distinguish using the basis computed in the first step.

E  Algebraic Dependence

Here, we list definitions and key results taken from the work of [Kay09] that we use in the security analysis of our MJP scheme. In short, we articulate the formalisation of expressing algebraic dependencies for a set of polynomials sampled from a particular field.

Definition 7

Let \(f = (f_1,\ldots , f_k)\) be a vector of k polynomials (of degree \(\le d\)) where each \(f_i \in \mathbb {F}[y_1,\ldots ,y_n]\) is an n-variate polynomial over the field \(\mathbb {F}\). A non-zero polynomial \(A(t_1,\ldots ,t_k) \in \mathbb {F}[t_1,\ldots , t_k]\) is said to be an annihilating polynomial for f if \(A(f_1,\ldots , f_k) = 0\). The polynomials \(f_1,\ldots , f_k\) are said to be algebraically dependent if such an annihilating polynomial exists.

Definition 8

Let \(f = (f_1, \ldots , f_k)\) be a vector of k polynomials as above where \(f'\) represents some subset of algebraically independent polynomials of maximal size k (i.e. for any \(f_{k+1} \in \mathbb {F}[y_1,\ldots ,y_n]\) then the set \(f' \cup f_{k+1}\) is algebraically dependent). Then the algebraic rank of the set of polynomials f is k.

Theorem 1

(Theorem 2 [Kay09]). Let \(f_1,\ldots ,f_k \in \mathbb {F}[x_1,\ldots , x_n]\) be a set of k polynomials in n variables over the field \(\mathbb {F}\). Then this set of polynomials has algebraic rank k if and only if the Jacobian matrix, Jf(x), has rank k.

Corollary 2

([Kay09, BS83]). There exists a randomized polynomial time algorithm that on input a set of k arithmetic circuits over a field \(\mathbb {F}\), determines if the polynomials computed by these arithmetic circuits are algebraically dependent or not.

Remark 3

The algorithm mentioned by Corollary 2 essentially requires submitting random values in place of the variables in the Jacobian matrix Jf(x). By the Schwarz-Zippel lemma, the rank of the symbolic matrix is likely to be the same as the rank of the matrix evaluated on random inputs with high probability. As such we can calculate the algebraic rank for a given system of polynomials.

Reprints and permissions

© 2017 Springer International Publishing AG

Policies and ethics