Weaker alternative to Ed25519? For me, the main advantages of Ed25519 are that it avoids patents (by computing in one dimension) and that it is fast.

However, the 128bit security of Ed25519 is sometimes too strong to comply with export regulations.

So I wonder if there are any weaker curves of the same type (i.e. also patent-free and fast) that I can use instead? (or should I go deeper into ECC and try to determine myself the parameters of such a curve?)
You could try the 112-bit secp112r1 cited in [1].

Before you do this, the problem with that paper is they actually show how to break the discrete log problem on this curve! And this was back in 2012. So any export-strength implementation of ECC is definitely breakable by governments, research groups and sufficiently determined/resourceful commercial adversaries.

So you'd be selling crypto that, while safely exportable, is known to be breakable and you're competing against other crypto libraries that don't have this "feature". I'm skeptical whether this is a sensible idea.

EDIT: oops, I forgot to check the key point - that it's patent-free. But the problem remains that any 112-bit curve, patented or not, is small enough that one can feasibly if not easily take discrete logs.

EDIT2: on my machine, openssl ecparam -list_curves includes secp112r1 and according to [2] sun wrote the OpenSSL ECC package "precisely to avoid any patented method". To me it looks like you should be fine with that curve as long as you don't re-implement it using any of the patented implementation techniques. This is not legal advice of course.

[1] http://lacal.epfl.ch/files/content/sites/lacal/files/papers/noan112.pdf

[2] https://security.stackexchange.com/questions/3519/can-ecc-be-used-without-infringing-on-patents