1
$\begingroup$

I am looking for an encoding algorithm that would have an encoding function with highly expensive computational costs (ideally like scrypt). At the same time its decoding function must be a lot easier to calculate.

Computational costs should not depend on the size of the encoded data. The size of the encoded data can be up to 10 KB. The encoding part of the algorithm should also be small in the sense of not containing a huge constant data set used for calculations. The decoder can be large but not ridiculously (< 10 MB). Some sorts of encryption are not forbidden.

Under computational costs I understand both calculation and memory costs, however one of them would also suffice

Pseudocode:

var encoded = encode("Hello world"); // Takes 10 seconds
var decoded = decode(encoded); // Takes 0.01 second

Encoding by brute-forcing the decode operation should be slower than encoding operation itself unless decode operation can be kept secret.

I was looking at asymmetric cryptography, I may be wrong, but those algorithms usually have equally expensive encryption and decryption functions. And their keys have length of the same order.

Maybe some of NP-complete problems could be a solution, but I don't know how to reuse them.

Thanks!

$\endgroup$
  • $\begingroup$ Since you mention some kind of encryption: do both encoding functions and decoding functions have to be public? Would you be OK with a public-key scheme, where there is a public key for encoding, and where to decode efficiently you have to know the private (secret) key? $\endgroup$ – D.W. Apr 7 '17 at 0:41
  • $\begingroup$ @D.W. The decoding function can be private. It can also depend on some private (even large) key. $\endgroup$ – Andrej Apr 7 '17 at 1:01
1
$\begingroup$

There is a public-key scheme that achieves this, based on timelock cryptography. It is parameterized by a parameter $t$, which controls how slow encoding is. The time to encode (without knowledge of the private key) will be about $O(t)$; the time to decode (with knowledge of the private key) will be about $O(1)$; and the time to generate a private-public keypair (which should probably be counted as part of the running time spent by the decoder) is approximately $O(\lg t)$. Consequently, by making $t$ sufficiently large, you can have an arbitrarily large ratio between the time to encode and the time to decode.

The specific construction is based on timelock cryptography and the Rabin cryptosystem. Generate a RSA modulus $n=pq$ that has the following special form: $p=4u-1$, $q=4v-1$, $u \equiv v \pmod 2$, and $\gcd(p-1,q-1)=2$, where $u,v$ are integers. Let $\alpha$ be the integer such that $\alpha \equiv u \pmod{p-1}$ and $\alpha \equiv v \pmod{q-1}$. Pick a positive integer $t$, and compute the exponents $e=2^t \bmod \varphi(n)$ and $d = \alpha^t \bmod \varphi(n)$, where $\varphi(n)=(p-1)(q-1)$. Make $n,t$ public. The private key is $d$.

To encode a message $x$, you represent your message as a number $x$ that is a perfect square modulo $n$, a la Rabin's cryptosystem. Then compute $E(x) = x^{2^t} \bmod n$. This can be computed by repeatedly squaring $x$ (do it $t$ times).

To decode a codeword $y$, you compute $D(y) = y^d \bmod n$. Given knowledge of the private key, this can be computed efficiently, regardless of the value of $t$.

The person who creates the keypair can compute $d$ efficiently, using $O(\lg t)$ modular squaring operations (compute $\alpha$ using the Chinese remainder theorem, then compute $d$ using fast modular exponentiation, using knowledge of the factorization of $n$).

The parameter $t$ controls the time to encode. By choosing $t$ sufficiently large, you can make encoding 10 seconds. In contrast, decoding takes constant time (you can choose RSA parameters so that you can decode in 0.01 seconds). Or, to put it another way, creating the keypair takes $O(\lg t)$ time; encoding takes $O(t)$ time; and decoding takes $O(1)$ time. Therefore, the designer of the scheme can choose how long it takes to encode and how big the gap between encoding vs decoding will be.

This is basically the reverse of a timelock puzzle / timed-release cryptography. See https://crypto.stackexchange.com/q/606/351, Is there any problem that is hard to solve, can produce N equiprobable outputs and is easy to verify?, and Is it possible to create a "Time Capsule" using encryption?.

Why does this scheme work? In other words, why does decoding undo the encoding operation? It works for basically the same reason the Rabin cryptosystem works. In particular, raising to the $\alpha$th power computes a square root modulo $n$: raising to the $(p+1)/4=u$th power modulo $p$ computes a square root modulo $p$; raising to the $v$th power computes a square root modulo $q$; and by the Chinese remainder theorem, raising to the $\alpha$th power does both simultaneously, thus computes a square root modulo $n$. Thus $f(x)=x^2 \bmod n$ is a one-way permutation on the set of squares (quadratic residues) modulo $n$, and its inverse is $g(y)=y^\alpha \bmod n$. The crucial thing is that, without knowledge of the factorization of $n$, there is no known way to speed up repeated application of the function $f$; but with knowledge of $n$, you can dramatically speed up repeated application of the function $g$. So, encoding involves iteratively applying $f$; decoding uses the trick to apply $g$ many times, but faster than the naive method.

$\endgroup$
  • $\begingroup$ Thank you! Can you, please, explain how the calculation of d (d=e^-1 mod φ(n)) should use the modulo operation? Isn't 1/e <= 1? $\endgroup$ – Andrej Apr 7 '17 at 18:30
  • $\begingroup$ @Andrej, That operation is a modular inverse, which is computed using the extended Euclidean algorithm; it's a little different from the division you might be used to. It would help to study RSA and modular arithmetic -- standard introductions to those topics will likely discuss what that operation means. $\endgroup$ – D.W. Apr 7 '17 at 18:55
  • $\begingroup$ Thanks again. I just found the definition of the modular inverse. Once I'm done understanding your answer I will mark it as answer. $\endgroup$ – Andrej Apr 7 '17 at 19:00
  • $\begingroup$ It looks like $e$ and $\varphi(n)$ will never be co-prime (they both can be divided by 2) and it makes modular inverse impossible. What do I miss? $\endgroup$ – Andrej Apr 8 '17 at 11:42
  • 1
    $\begingroup$ @Andrej, yes, you're right, it takes a little more setup to make it all work. See my revised answer for something that I think works and takes care of those issues. $\endgroup$ – D.W. Apr 9 '17 at 15:59

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.