We have to pick a non-linear F

But what F could we pick?

@Evinda I think you actually do want to be able to solve it in every which way, and instead just pick an $F$ that corresponds to a hard problem with a useful solution.

What F could we pick? Could you give me a hint? @MickLH

I probably need more context to give any useful suggestion, but it seems like the usual lattice primitives handle everything

I vaguely remember you saying "Feistel Network" at some point, are you looking for a one way function?

@Evinda the safest solution would be picking a known-safe function, ie something like HMAC

@MickLH Yes

I think @SEJPM's suggestion is a solid way to accomplish the task if you wanted a custom feistel network that probably also works :P

If you're just having fun, or if you feel like working very hard and don't have any heavy risk involved, then you might be able to apply the leftover hash lemma to something like a subset-sum instance

I think subset-sum is even NP-complete, but no surprise here: it's riddled with cases that admit easier solutions than brute force

For example I believe anything with "density" away from $1$ on either side is trivially solved by lattice reduction, but still it would be a shock if a poly time algorithm covered every case

Lets see, I think the syndrome of a random parity check matrix is considered a "good" hash function in some respect

Sorry, I will have to go off for 1-2 hours. I will read your answer later and tell you if I got it

peace ttyl