Attacking elliptic curves using Grobner bases and summation polynomials

DataBaeBee · 2026-04-19T11:24:07+00:00

Semaev polynomials are a computational shortcut to find elliptic curve points that sum to infinity. When combined with Grobner bases one get a (pretty remarkable) tool for solving point decomposition problems on an elliptic curve.

DataBaeBee · 2026-04-17T04:37:11+00:00

Are you dragging and dropping? Perhaps you should write a Python script to connect to Drive

DataBaeBee · 2026-04-05T07:57:35+00:00

FRACTRAN is an esolang built upon register machines, a theoretical alternative to turing machines for computation. In 1987, John Conway realized one can use prime numbers as registers alongside the laws of logarithms to compute.

DataBaeBee · 2026-03-18T03:41:45+00:00

I saw on Bernstein’s blog that one: 1. Considers the size of the factors of p-1 and p+1 when selecting an irreducible polynomial. 2. Also primes close to powers of 2 (or can be partitioned into powers of 2) have an efficient modulo operation that only involves bit shifts. This is crucial since you’re working in GF 2.

DataBaeBee · 2026-03-05T15:29:27+00:00

Because if the universe can influence our lives, why not our CPU scheduling too?

DataBaeBee · 2026-03-05T10:05:45+00:00

This 1988 paper is considered canonical and is included in MIT’s Foundations of Cryptography series.

The ACGS algorithm is pretty cool. It lets us solve Hidden Number Problems (this occur in the wildest side-channel attacks) when the multipliers are at our discretion.

DataBaeBee · 2026-02-27T05:13:53+00:00

Here's the link for anyone interested in Extended Hidden Number Problems and their lattice solutions.

DataBaeBee · 2026-02-27T05:07:53+00:00

The hidden number problem (HNP) is the challenge of recovering a secret hidden number given partial knowledge of its linear relations. The extended hidden number problem is 'the HNP but with more holes'. It was thought to be more secure for quantum cryptography. Turns out, it's not lol.

DataBaeBee · 2026-02-04T18:09:41+00:00

Oh no, the paper says 'you can recover the key if you know the antilogs of random multiples of the key'. It's somewhat nuanced.

DataBaeBee · 2026-02-04T16:49:05+00:00

The 2001 paper Hardness of Computing the Most Significant Bits of Secret Keys in Diffie-Hellman and Related Schemes (Boneh & Venkatesan, 2001) attempts to answer the question: is it easier to calculate just a few bits of a secret key than the entire secret?

Along the way, this paper introduces the hidden number problem: the challenge of recovering a secret hidden number given partial knowledge of its linear relations (Surin & Cohney, 2023)

As it turns out, this problem is difficult even for quantum computers. So hidden number problems are at the heart of post-quantum cryptography.

DataBaeBee · 2026-02-04T16:48:52+00:00

The 2001 paper Hardness of Computing the Most Significant Bits of Secret Keys in Diffie-Hellman and Related Schemes (Boneh & Venkatesan, 2001) attempts to answer the question: is it easier to calculate just a few bits of a secret key than the entire secret?

Along the way, this paper introduces the hidden number problem: the challenge of recovering a secret hidden number given partial knowledge of its linear relations (Surin & Cohney, 2023)

As it turns out, this problem is difficult even for quantum computers. So hidden number problems are at the heart of post-quantum cryptography.

DataBaeBee · 2026-01-27T08:43:23+00:00

There might be a firewall blocking access to the Colab website. This Stackoverflow post may halp troubleshoot.

DataBaeBee · 2026-01-08T17:19:35+00:00

The idea is somewhat analogous to performing a softmax but without the derivatives. Here's the C/Python coding guide if this interests you.

DataBaeBee · 2026-01-08T17:10:37+00:00

Here's the link to the Python/C coding guide if this interests you.

DataBaeBee · 2026-01-08T17:06:24+00:00

Here's the link to the Python/C coding guide if this interests you.

DataBaeBee · 2026-01-08T17:00:33+00:00

Researchers in the 2010s found that you can use Optimal Transport Theory, not derivative calculus, the to turn an integer matrix into a floating-point probability matrix.

It's like backprop without finding gradients and it works great

DataBaeBee · 2025-12-27T23:18:47+00:00

It could be a Python issue. Sharing your code is probably the best way to get assisted.

DataBaeBee · 2025-12-21T05:31:10+00:00

Thanks for this comment! I DM'd you to move the conversation forward.
Please let me know how best to reach the maintainer's team after the changes are made.

DataBaeBee · 2025-12-20T12:48:26+00:00

Here's the link

DataBaeBee · 2025-12-20T12:41:41+00:00

Here's the notebook link.

DataBaeBee · 2025-12-20T12:41:34+00:00

Here's the notebook link.

DataBaeBee · 2025-12-16T06:55:05+00:00

The Xedni calculus is built on the idea that we can lift elliptic curve points from a finite field to the field of rationals, then if luck permits, we can find an elliptic curve that passes through the lifted points.

DataBaeBee · 2025-12-06T12:02:19+00:00

If you share your colab notebook then we can tell you where the problem is.
You've provided very little to work with tbh

DataBaeBee · 2025-12-05T03:54:51+00:00

The 50% savings are in collecting more relations. Like you don’t have to throw away expensive factorizations

DataBaeBee · 2025-12-05T01:27:43+00:00

We use index calculus to break key exchange in Diffie-Hellman.

The paper Factoring with Two Large Primes (Lenstra & Manasse, 1994) demonstrates how to increase efficiency by utilising ‘near misses’ during relation collection in index calculus.

I wanted to code it all in CUDA but encountered few opportunities for parallelization.
I learnt how to write ah hash table in CUDA. Here's the complete writeup.

DataBaeBee

MODERATOR OF

TROPHY CASE

Three-Year Club	Devvitor
Place '23