<div dir="ltr"><div><div>I was considering similar scheme some time ago. Good idea is that key expansion to permutation is actually computable in linear-time [1]. Bad problem is the "whiteness". I only considered a scheme where you expand any bit string to a string with exactly 1:1 amount of ones and zeroes (that is achievable in decent time with colex ranking/unranking, e.g. my implementation [2]), but that is fully breakable when an attacker has a chance to see results of n*log(n) chosen encryptions with your key. Schema is like this, for n=8:<br><br></div><div>you encrypt 00001111<br></div><div>then 00110011<br></div><div>then 01010101<br></div><div>get all the ciphertexts, AND them together, and you know the position of permuted last bit. Repeat for all other bits.<br><br></div><div>If the inputs to the permutations were hard for attacker to modify, the scheme would be secure. Similar scheme was (successfully) applied to original McEliece scheme - secret permutation P was used to hide the structure of the generator matrix.<br></div><div><br></div><div>Certainly some whitening could help the situation, but I'm not sure whether there is some decent algorithm for reversible unranking of string to whitened counterparts. One of the simplest methods is again found in McEliece, namely the matrix S that is used for the exactly same purpose (whitening the input). But that is a bit hardcore for our purpose (S can "swallow" the permutation functionality anyway).<br><br></div><div>There is probably a simpler approach - you can pad the original input with a simple hash of the plaintext, which (after colex unranking) effectively prohibits any fixed ones/zeros in the permutation input:<br><br></div><div>encrypt(m,k) = rank_colex( permute( unrank_perm(k), unrank_colex(m | hash(m)) ) )<br><br></div><div>It certainly needs some more research.<br></div><div><br></div><div>Hope this helped a bit.<br><br></div><div>-mk<br></div><div><br>[1] Mares - Linear-time ranking of permutations<br></div></div>[2] <a href="https://github.com/exaexa/codecrypt/blob/master/src/bvector.cpp#L355">https://github.com/exaexa/codecrypt/blob/master/src/bvector.cpp#L355</a><br></div>