Re: [sage-support] SR: RuntimeError: error in Singular function call 'groebner': int overflow in hilb 1

[Dima Pasechnik]

Don't do Groebner bases over SR, use a proper polynomial ring.

On Thu, Jul 1, 2021 at 4:56 PM Sam Ratcliffe
<samuel.r...@hotmail.co.uk> wrote:
>
> I am using the SageMath implementation of SR and wish to recover all solutions to a polynomial system using the variety function for ideals as specified here: https://doc.sagemath.org/html/en/reference/cryptography/sage/crypto/mq/sr.html
>
> When I run the following (as available on the above link):
>
> sage: sr = mq.SR(1,1,1,4, gf2=True, polybori=True)
> sage: K = sr.base_ring()
> sage: a = K.gen()
> sage: K = [a]
> sage: P = [1]
> sage: F,s = sr.polynomial_system(P=P, K=K)
> sage: I = F.ideal()
> sage: for V in I.variety():
> ....: for k,v in sorted(V.items()): ....: print("{} {}".format(k, v)) ....: print("\n")
>
> --
> You received this message because you are subscribed to the Google Groups "sage-support" group.
> To unsubscribe from this group and stop receiving emails from it, send an email to sage-support...@googlegroups.com.
> To view this discussion on the web visit https://groups.google.com/d/msgid/sage-support/535596c4-8138-4894-b7c0-13293904ee30n%40googlegroups.com.

[Sam Ratcliffe]

I am using SageMath's implementation of SR and encountered the above error when trying to display the solutions to a polynomial system using the variety function for ideals, as specified here: https://doc.sagemath.org/html/en/reference/cryptography/sage/crypto/mq/sr.html. I am running SageMath 9.2 on Windows 10 with an Intel Core i5-6600K CPU @ 3.50GHz, 3501 Mhz, 4 Core(s), 4 Logical Processor(s).

I use the following commands:

sage: sr = mq.SR(2,1,1,4, gf2=True, polybori=True, allow_zero_inversions=True) 

sage: K = sr.base_ring() 

sage: a = K.gen() 

sage: K = [a] 

sage: P = [1] 

sage: F,s = sr.polynomial_system(P=P, K=K)

sage: I = F.ideal() 

sage: for V in I.variety(): 

....:             for k,v in sorted(V.items()): 

....:                     print("{} {}".format(k, v)) 

....:             print("\n")

This works only for SR(1,1,1,4) i.e. SR using only one round. If I even increase the round number to 2 I encounter the following error:

RuntimeError: error in Singular function call 'groebner':
int overflow in hilb 1
error occurred in or before standard.lib::stdhilb line 350: ` i = std(i, hi);`
leaving standard.lib::stdhilb
leaving standard.lib::groebner

Any help with this would be much appreciated, thank you.

The entire error message is much larger:

AttributeError                            Traceback (most recent call last)

/opt/sagemath-9.2/local/lib/python3.7/site-packages/sage/rings/polynomial/multi_polynomial_ideal.py in dimension(self, singular)

   1141         try:

-> 1142             return self.__dimension

   1143         except AttributeError:

/opt/sagemath-9.2/local/lib/python3.7/site-packages/sage/structure/element.pyx in sage.structure.element.Element.__getattr__ (build/cythonized/sage/structure/element.c:4703)()

    492         """

--> 493         return self.getattr_from_category(name)

    494

/opt/sagemath-9.2/local/lib/python3.7/site-packages/sage/structure/element.pyx in sage.structure.element.Element.getattr_from_category (build/cythonized/sage/structure/element.c:4815)()

    505             cls = P._abstract_element_class

--> 506         return getattr_from_other_class(self, cls, name)

    507

/opt/sagemath-9.2/local/lib/python3.7/site-packages/sage/cpython/getattr.pyx in sage.cpython.getattr.getattr_from_other_class (build/cythonized/sage/cpython/getattr.c:2619)()

    371         dummy_error_message.name = name

--> 372         raise AttributeError(dummy_error_message)

    373     attribute = <object>attr

AttributeError: 'MPolynomialIdeal' object has no attribute '_cache__gens'

During handling of the above exception, another exception occurred:

KeyError                                  Traceback (most recent call last)

/opt/sagemath-9.2/local/lib/python3.7/site-packages/sage/misc/cachefunc.pyx in sage.misc.cachefunc.CachedMethodCaller.__call__ (build/cythonized/sage/misc/cachefunc.c:10304)()

   1942             try:

-> 1943                 return cache[k]

   1944             except TypeError:  # k is not hashable

KeyError: (('', None, None, False), ())

During handling of the above exception, another exception occurred:

RuntimeError                              Traceback (most recent call last)

RuntimeError: Error raised calling singular function

Exception ignored in: 'sage.libs.singular.function.LibraryCallHandler.handle_call'

RuntimeError: Error raised calling singular function

---------------------------------------------------------------------------

AttributeError                            Traceback (most recent call last)

/opt/sagemath-9.2/local/lib/python3.7/site-packages/sage/rings/polynomial/multi_polynomial_ideal.py in dimension(self, singular)

   1141         try:

-> 1142             return self.__dimension

   1143         except AttributeError:

/opt/sagemath-9.2/local/lib/python3.7/site-packages/sage/structure/element.pyx in sage.structure.element.Element.__getattr__ (build/cythonized/sage/structure/element.c:4703)()

    492         """

--> 493         return self.getattr_from_category(name)

    494

/opt/sagemath-9.2/local/lib/python3.7/site-packages/sage/structure/element.pyx in sage.structure.element.Element.getattr_from_category (build/cythonized/sage/structure/element.c:4815)()

    505             cls = P._abstract_element_class

--> 506         return getattr_from_other_class(self, cls, name)

    507

/opt/sagemath-9.2/local/lib/python3.7/site-packages/sage/cpython/getattr.pyx in sage.cpython.getattr.getattr_from_other_class (build/cythonized/sage/cpython/getattr.c:2619)()

    371         dummy_error_message.name = name

--> 372         raise AttributeError(dummy_error_message)

    373     attribute = <object>attr

AttributeError: 'Singular' object has no attribute '_strip_prompt'

During handling of the above exception, another exception occurred:

KeyError                                  Traceback (most recent call last)

/opt/sagemath-9.2/local/lib/python3.7/site-packages/sage/misc/cachefunc.pyx in sage.misc.cachefunc.CachedMethodCaller.__call__ (build/cythonized/sage/misc/cachefunc.c:10304)()

   1942             try:

-> 1943                 return cache[k]

   1944             except TypeError:  # k is not hashable

KeyError: (('', None, None, False), ())

During handling of the above exception, another exception occurred:

RuntimeError                              Traceback (most recent call last)

<ipython-input-11-f2c1e1116d2f> in <module>

----> 1 for V in I.variety():

      2     for k,v in sorted(V.items()):

      3         print("{} {}".format(k, v))

      4     print("\n")

      5

/opt/sagemath-9.2/local/lib/python3.7/site-packages/sage/rings/polynomial/pbori/pbori.pyx in sage.rings.polynomial.pbori.pbori.BooleanPolynomialIdeal.variety (build/cythonized/sage/rings/polynomial/pbori/pbori.cpp:43416)()

   5198         I = R.ideal([R(f) for f in self.groebner_basis()])

   5199         J = FieldIdeal(R)

-> 5200         solutions = (I + J).variety(**kwds)

   5201         return [KeyConvertingDict(R_bool, s) for s in solutions]

   5202

/opt/sagemath-9.2/local/lib/python3.7/site-packages/sage/rings/polynomial/multi_polynomial_ideal.py in __call__(self, *args, **kwds)

    295         if not R.base_ring().is_field():

    296             raise ValueError("Coefficient ring must be a field for function '%s'."%(self.f.__name__))

--> 297         return self.f(self._instance, *args, **kwds)

    298

    299 require_field = RequireField

/opt/sagemath-9.2/local/lib/python3.7/site-packages/sage/rings/polynomial/multi_polynomial_ideal.py in variety(self, ring)

   2566         if ring is not None: P = P.change_ring(ring)

   2567         try:

-> 2568           TI = self.triangular_decomposition('singular:triangLfak')

   2569           T = [list(each.gens()) for each in TI]

   2570         except TypeError: # conversion to Singular not supported

/opt/sagemath-9.2/local/lib/python3.7/site-packages/sage/rings/polynomial/multi_polynomial_ideal.py in __call__(self, *args, **kwds)

    295         if not R.base_ring().is_field():

    296             raise ValueError("Coefficient ring must be a field for function '%s'."%(self.f.__name__))

--> 297         return self.f(self._instance, *args, **kwds)

    298

    299 require_field = RequireField

/opt/sagemath-9.2/local/lib/python3.7/site-packages/sage/rings/qqbar_decorators.py in wrapper(*args, **kwds)

     94                    or is_PolynomialSequence(a)

     95                    and is_AlgebraicField_common(a.ring().base_ring()) for a in args):

---> 96             return func(*args, **kwds)

     97

     98         polynomials = []

/opt/sagemath-9.2/local/lib/python3.7/site-packages/sage/interfaces/singular.py in wrapper(*args, **kwds)

   2782     def wrapper(*args, **kwds):

   2783         with SingularGBDefaultContext():

-> 2784             return func(*args, **kwds)

   2785     return wrapper

/opt/sagemath-9.2/local/lib/python3.7/site-packages/sage/libs/singular/standard_options.py in wrapper(*args, **kwds)

    139         """

    140         with LibSingularGBDefaultContext():

--> 141             return func(*args, **kwds)

    142     return wrapper

/opt/sagemath-9.2/local/lib/python3.7/site-packages/sage/rings/polynomial/multi_polynomial_ideal.py in triangular_decomposition(self, algorithm, singular)

   1059                 I = MPolynomialIdeal(Q, I.groebner_basis()[::-1])

   1060

-> 1061         if I.dimension() != 0:

   1062             raise TypeError("dimension must be zero")

   1063

/opt/sagemath-9.2/local/lib/python3.7/site-packages/sage/rings/polynomial/multi_polynomial_ideal.py in __call__(self, *args, **kwds)

    295         if not R.base_ring().is_field():

    296             raise ValueError("Coefficient ring must be a field for function '%s'."%(self.f.__name__))

--> 297         return self.f(self._instance, *args, **kwds)

    298

    299 require_field = RequireField

/opt/sagemath-9.2/local/lib/python3.7/site-packages/sage/rings/qqbar_decorators.py in wrapper(*args, **kwds)

     94                    or is_PolynomialSequence(a)

     95                    and is_AlgebraicField_common(a.ring().base_ring()) for a in args):

---> 96             return func(*args, **kwds)

     97

     98         polynomials = []

/opt/sagemath-9.2/local/lib/python3.7/site-packages/sage/rings/polynomial/multi_polynomial_ideal.py in dimension(self, singular)

   1145                 import sage.libs.singular.function_factory

   1146                 dim = sage.libs.singular.function_factory.ff.dim

-> 1147                 v = MPolynomialIdeal(self.ring(),self.groebner_basis())

   1148                 self.__dimension = Integer(dim(v, attributes={v:{'isSB':1}}))

   1149             except TypeError:

/opt/sagemath-9.2/local/lib/python3.7/site-packages/sage/misc/cachefunc.pyx in sage.misc.cachefunc.CachedMethodCaller.__call__ (build/cythonized/sage/misc/cachefunc.c:10438)()

   1946                 return cache[k]

   1947         except KeyError:

-> 1948             w = self._instance_call(*args, **kwds)

   1949             cache[k] = w

   1950             return w

/opt/sagemath-9.2/local/lib/python3.7/site-packages/sage/misc/cachefunc.pyx in sage.misc.cachefunc.CachedMethodCaller._instance_call (build/cythonized/sage/misc/cachefunc.c:9917)()

   1822             True

   1823         """

-> 1824         return self.f(self._instance, *args, **kwds)

   1825

   1826     cdef fix_args_kwds(self, tuple args, dict kwds):

/opt/sagemath-9.2/local/lib/python3.7/site-packages/sage/rings/qqbar_decorators.py in wrapper(*args, **kwds)

     94                    or is_PolynomialSequence(a)

     95                    and is_AlgebraicField_common(a.ring().base_ring()) for a in args):

---> 96             return func(*args, **kwds)

     97

     98         polynomials = []

/opt/sagemath-9.2/local/lib/python3.7/site-packages/sage/rings/polynomial/multi_polynomial_ideal.py in groebner_basis(self, algorithm, deg_bound, mult_bound, prot, *args, **kwds)

   4294         if not algorithm:

   4295             try:

-> 4296                 gb = self._groebner_basis_libsingular("groebner", deg_bound=deg_bound, mult_bound=mult_bound, *args, **kwds)

   4297             except (TypeError, NameError): # conversion to Singular not supported

   4298                 try:

/opt/sagemath-9.2/local/lib/python3.7/site-packages/sage/libs/singular/standard_options.py in wrapper(*args, **kwds)

    139         """

    140         with LibSingularGBDefaultContext():

--> 141             return func(*args, **kwds)

    142     return wrapper

/opt/sagemath-9.2/local/lib/python3.7/site-packages/sage/rings/polynomial/multi_polynomial_ideal.py in _groebner_basis_libsingular(self, algorithm, *args, **kwds)

    537             S = slimgb_libsingular(self)

    538         elif algorithm == "groebner":

--> 539             S = groebner(self)

    540         else:

    541             try:

/opt/sagemath-9.2/local/lib/python3.7/site-packages/sage/libs/singular/function.pyx in sage.libs.singular.function.SingularFunction.__call__ (build/cythonized/sage/libs/singular/function.cpp:15176)()

   1332         if not (isinstance(ring, MPolynomialRing_libsingular) or isinstance(ring, NCPolynomialRing_plural)):

   1333             raise TypeError("Cannot call Singular function '%s' with ring parameter of type '%s'"%(self._name,type(ring)))

-> 1334         return call_function(self, args, ring, interruptible, attributes)

   1335

   1336     def _instancedoc_(self):

/opt/sagemath-9.2/local/lib/python3.7/site-packages/sage/libs/singular/function.pyx in sage.libs.singular.function.call_function (build/cythonized/sage/libs/singular/function.cpp:17178)()

   1530     if errorreported:

   1531         errorreported = 0

-> 1532         raise RuntimeError("error in Singular function call %r:\n%s" %

   1533             (self._name, "\n".join(error_messages)))

   1534

RuntimeError: error in Singular function call 'groebner':

int overflow in hilb 1

error occurred in or before standard.lib::stdhilb line 350: `    i = std(i, hi);`

leaving standard.lib::stdhilb

leaving standard.lib::groebner

[Martin R. Albrecht]

Hi all,

I think there’s a name clash here. mq.SR is a thing I wrote ages ago for producing systems of equations for small-scale variants of AES (not the symbolic ring).

The problem comes from the variety() call and I think Sam did find a bug:

sage: sr = mq.SR(2,1,1,4, gf2=True, polybori=True, allow_zero_inversions=True)

sage: P = sr.vector([0, 0, 1, 0])
sage: C = sr.vector([1, 0, 0, 0])
sage: F,s = sr.polynomial_system(P=P, C=C)
sage: G = F.groebner_basis() # this succeeds
sage: G.ideal().variety()

More directly:

sage: B = BooleanPolynomialRing(36, "x")
sage: I = Ideal([B.random_element(degree=1) for _ in range(36)])
sage: I.variety()

RuntimeError: error in Singular function call 'groebner':
int overflow in hilb 1

error occurred in or before standard.lib::stdhilb line 300: ` intvec hi = hilb( Id[1],1,W );`
expected intvec-expression. type 'help intvec;'
leaving standard.lib::stdhilb (0)
leaving standard.lib::groebner (1104)

@Sam: as a workaround, you can “read off” the solution directly.

Cheers,
Martin

--

_pgp: https://keybase.io/martinralbrecht
_www: https://malb.io
_prn: he/him or they/them

[Vesselin Velichkov]

Hi Martin,

Thank you for your reply!

By "name clash" do you mean that both mq and BooleanPolynomialRing use the same name i.e. "variety" for two different functions?

Also, I didn't quite understand your solution -- the call to G.ideal().variety() from your first example still fails on my side with the same overflow error. The call to I.variety() in the second example succeeds though.

Also, what do you mean by reading off the solution directly? How can one do that?

Thanks again!

Best,
Vesselin

[Martin R. Albrecht]

Hi Vesselin,

Sorry! Name-clash: Sage uses SR for the “Symbolic Ring” and we use “mq.SR” for the small scale AES generator. This is what caused Dima’s confusion, that’s all.

A workaround is to look at the linear equations directly and to extract a solution from it “by hand”, i.e. there’s a bug.

Indeed, the bug is unrelated to PolyBoRi:

sage: R = PolynomialRing(GF(2), 36, "x", order="lex")
sage: I = Ideal([R.random_element(degree=1, terms=20) for _ in range(36)])
sage: I.groebner_basis() # bombs out

RuntimeError: error in Singular function call 'groebner':
int overflow in hilb 1
error occurred in or before standard.lib::stdhilb line 300: ` intvec hi = hilb( Id[1],1,W );`
expected intvec-expression. type 'help intvec;'
leaving standard.lib::stdhilb (0)

FWIW:

sage: I.groebner_basis(algorithm="singular:std") # works as expected


Cheers,
Martin

[Vesselin Velichkov]

Thanks, Martin!

> A workaround is to look at the linear equations directly and to extract a solution from it “by hand

Oh, you mean he can directly look at the ideal and extract the solutions from there without having to compute the variety?

For the particular SR(2,1,1,4) example the ideal would be

sage: I
Ideal (k200, k201, k202 + 1, k203, x200, x201 + 1, x202 + 1, x203, w200, w201 + 1, w202 + 1, w203 + 1, s100, s101, s102 + 1, s103 + 1, k100 + 1, k101 + 1, k102 + 1, k103, x100 + 1, x101 + 1, x102 + 1, x103 + 1, w100 + 1, w101, w102, w103, s000 + 1, s001 + 1, s002, s003, k000 + 1, k001, k002 + 1, k003) of Boolean PolynomialRing in k200, k201, k202, k203, x200, x201, x202, x203, w200, w201, w202, w203, s100, s101, s102, s103, k100, k101, k102, k103, x100, x101, x102, x103, w100, w101, w102, w103, s000, s001, s002, s003, k000, k001, k002, k003

The above are the linear equations you are referring to, right?

Best,
Vesselin

[Sam Ratcliffe]

Hi Martin,

Thank you for the assistance! I am in the process of performing repeated experiments in which I extract the key bits from the ideal/Groebner basis, so reading off the solutions by hand is not ideal for repeated usage or the scenarios in which there are fewer equations than variables and I can't directly extract the key bits without solving for other variables too. I tried to extract the generators from the ideal and construct a polynomial sequence to solve and extract the key bits. I have tried doing this using the solve() function for linear equations, but I can't seem to find a way to specify that the solutions I am looking for are within GF(2).

Additionally, I have run into problems with the groebner_basis() function. For SR(i,1,1,4) the function seems to work correctly for all values of i. However, when I change the array size to even SR(2,2,2,4) the groebner_basis() function won't compute the Groebner basis of the polynomial system, it runs for a while, and aborts with an error message. I run the following:

sage: sr = mq.SR(2,2,2,4,gf2=True,polybori=True,allow_zero_inversions=True)

sage: R = sr.ring().base_ring()

sage: P = sr.vector([R.random_element() for _ in range(sr.r*sr.c*sr.e)])

sage: K = sr.vector([R.random_element() for _ in range(sr.r*sr.c*sr.e)])

sage: C = sr(P, K)

sage: F, s = sr.polynomial_system(P=P, C=C)

sage: G = F.groebner_basis()

And receive the following error:

terminate called after throwing an instance of 'polybori::PBoRiError'

  what():  Built-in matrix-size exceeded!

---------------------------------------------------------------------------

RuntimeError                              Traceback (most recent call last)

<ipython-input-10-9eabeb133a4e> in <module>

----> 1 G = F.groebner_basis()

/opt/sagemath-9.2/local/lib/python3.7/site-packages/sage/rings/polynomial/multi_polynomial_sequence.py in groebner_basis(self, *args, **kwargs)

    534             [a, b, d]

    535         """

--> 536         return self.ideal().groebner_basis(*args, **kwargs)

    537

    538     def monomials(self):

/opt/sagemath-9.2/local/lib/python3.7/site-packages/sage/rings/polynomial/pbori/pbori.pyx in sage.rings.polynomial.pbori.pbori.BooleanPolynomialIdeal.groebner_basis (build/cythonized/sage/rings/polynomial/pbori/pbori.cpp:42313)()

   5095             if "redsb" not in kwds:

   5096                 kwds["redsb"]=True

-> 5097             sig_on()

   5098             gb = self._groebner_basis(**kwds)

   5099             sig_off()

RuntimeError: Aborted

Any help with getting past this would be appreciated.

Thanks again,

Sam

[Sam Ratcliffe]

Hi Martin,

I managed to circumvent the bug in the variety function for ideals for the GF(2) equation system generated by AES by using a sat solver. When generating an AES equation system over GF(2^e), I run into the same error using the variety function and was wondering if you knew any way around it?

Thanks again for the help,

Sam