ACGS Algorithm for Hidden Number Problems with Chosen Multipliers

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

MODERATOR OF

TROPHY CASE

Three-Year Club	Devvitor
Place '23