The Side Channel

« first day (2054 days earlier) ← previous day next day → last day (2622 days later) »

e-sushi

6:29 PM

That moment…

2 hours later…

MickLH

8:10 PM

Well... after working really hard, I've mostly salvaged my proposal!

but not without some damage to the efficiency... the security proof demands a prime field, which sucks because a binary field would make every operation a lot cheaper

but it's not just an artifact of the proof strategy, I've even constructed a working attack in the binary field case, so those benefits were simply too good to be true

The prime case was the original design anyways, now the only remaining sketchy assumption is about the distribution of prime factors of random numbers of the form $p - 2^\lambda n$ where $n$ is uniform and $p$ is prime.

SEJPM

@MickLH $0<n<p$?

MickLH

Yes

In fact you could even assume $n^3 < p$

SEJPM

@MickLH Is $\lambda$ a fixed constant?

MickLH

Yes, typical security parameter

SEJPM

so something like 128, 192, 256?

MickLH

8:19 PM

Yep exactly those 3 in my experiments

SEJPM

and I guess $p$ has to be in the 2048-bit range?

MickLH

Probably, maybe it can be as low as $4\lambda$ though

SEJPM

@MickLH ask on Math.SE whether they have any ideas?

MickLH

If a non-negligible fraction of those $p-2^\lambda n$ values admit a set of prime factors for which we can find a subset product that is in $[2^{3\lambda}, 2^{3\lambda+1}]$, then I'll be very happy

@SEJPM I guess I'll have to... it's awkward to me even trying to formulate exactly the question I'm after

SEJPM

@MickLH that may already help you solving your problem

MickLH

8:27 PM

@SEJPM Do you know of any work that characterizes the effect of the dimension of an LWE problem with exponentially large modulus?

SEJPM

@MickLH I've no idea about LWE-related research

MickLH

damn. I'm scared that I've interpreted a reduction incorrectly, because only needing one dimension seems too good to be true

Either way I'm very excited, even if the density of the special numbers turns out to be too small, there is still room for a large paranoid choice of dimension while still improving on key size of any other PQ scheme I can find

MickLH

9:24 PM

Q: Factors of integers of the form $p-2^\lambda r$.

Here $p$ is an odd prime, $r$ is uniform on $[0, 2^\lambda]$, and $\lambda$ is a constant. We define distribution $\mathcal{D}$ by: $$x \xleftarrow{\$} p-2^\lambda r$$ Assume $p \approx 2^{4\lambda}$, $\lambda \in \{128, 256\}$, and $0 \leq n \leq \log_2 \lambda$. Do a non-negligible fraction of...