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
On Friday, July 2, 2021 at 8:48:14 AM UTC+1 [email protected] wrote:
> 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
>
> On Friday, July 2, 2021 at 12:13:04 AM UTC+1 Martin Albrecht wrote:
>
>> 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 <[email protected]> writes:
>> > 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
>> >
>> > On Thursday, July 1, 2021 at 11:19:07 PM UTC+1 Martin Albrecht wrote:
>> >
>> >> 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
>> >>
>> >> Dima Pasechnik <[email protected]> writes:
>> >> > Don't do Groebner bases over SR, use a proper polynomial ring.
>> >> >
>> >> > On Thu, Jul 1, 2021 at 4:56 PM Sam Ratcliffe
>> >> > <[email protected]> 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 [email protected].
>> >> >> To view this discussion on the web visit
>> >>
>> https://groups.google.com/d/msgid/sage-support/535596c4-8138-4894-b7c0-13293904ee30n%40googlegroups.com
>>
>> >> .
>> >>
>> >>
>> >> --
>> >>
>> >> _pgp: https://keybase.io/martinralbrecht
>> >> _www: https://malb.io
>> >> _prn: he/him or they/them
>> >>
>> >>
>>
>>
>> --
>>
>> _pgp: https://keybase.io/martinralbrecht
>> _www: https://malb.io
>> _prn: he/him or they/them
>>
>>
--
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 [email protected].
To view this discussion on the web visit
https://groups.google.com/d/msgid/sage-support/83cf75ff-47e4-4113-b97a-7416f6c64f50n%40googlegroups.com.
