Faster alternatives to RSA trapdoor permutation

Question

We're working on web3.0 decentralized internet, a big part of which is a decentralized file storage system where clients upload files to storage providers and pay them for the services. Storage providers return signed messages, with the content hashes included, as guarantees, such that if they lose the file and fail to respond to a verification challenge on the blockchain, by not being able to provide the proof they're still storing the file, they will lose their collateral.

Clients upload files to several storage providers at once for redundancy. We needed to make sure that providers can't collude with each other/one provider can't misrepresent itself as being several and take payments for N copies of the file, getting away with storing only one copy. At the same time, the original file contents should always be available to storage providers, since they're supposed to publicly serve it on the network by responding to requests for the content based on its hash. This means encrypting several copies with AES

The solution I initially came up with is to use pure RSA (not hybrid) algorithm in signature mode, i.e. when you encrypt with the private key, and decrypt with the public key (or, more precisely, sign a message with a private key, and recover the message from the signature using the complement of that, but the math is the same as encryption/decryption, just with swapped keys). That way:

• A client can generate one key pair per provider
• When storing file F with the provider N, it can generate an "encrypted" replica of F (a signature containing the message) specific to that provider, by performing F_N = RSASign(F, k_priv_N), and sending the public key k_pub_N to the provider
• Provider signs the guarantee on the Hash(F_N), promising to store the encrypted copy
• Provider can at any point extract the content by performing F = RSARecover(F_N, k_pub_N) which is analogous to feeding the public key to a decryption algorithm, calculate the real hash Hash(F), and serve this file on the DHT network
• However, all providers, even if they wanted to collude, must continue to store individual encrypted copies/signatures F_N because each signed off on their specific Hash(F_N). There is no way to lose the F_N, deliberately or accidentally, and then recreate it on demand just by having F and k_pub_N, because that would require knowledge of the private key (which also explains why RSA must be in pure mode, and not in hybrid node, because performing AES encryption on provider side is trivial given the symmetric key, and they could get away with having to store just the RSA signature on top of the symmetric key, which is much smaller in size).

This works well, but we've ran into a few problems with this approach:

• RSA in pure mode is extremely slow
• Using proper padding for each block reduces the space we can use for embedding the file chunks, and therefore the resulting files are many percent bigger than the originals

Q: Are there any other similar cryptographic functions we can use for this case, which are superior to the RSA scheme in speed and size?

(For example, we've been looking at elliptic curves but there doesn't seem to be a way to extract the message, or even hash of the message, which would have also been helpful, from an EC signature.)

Answer 1

encrypt with the private key, and decrypt with the public key

That statement, and the very name privateEncrypt, is incompatible with standard terminology: "public" means known to all and opposes to "private"; and "encrypt" implies transforming some information $X$ into $Y$ in a way such that if $Y$ becomes public, $X$ does not.

Per standard terminology we sign with total message recovery, and recover the message. The term "total message recovery" designates a signature scheme where all the data is conveyed in the signature itself. This is how RSA signature was introduced, and the term is used in the ISO/IEC 9796 series of standards.

RSA in pure mode is extremely slow

Whatever the name and the variants, RSASign is indeed rather slow, and usually size-expanding. This can be mitigated, but some slowness will remain.

On the other hand, RSARecover is relatively fast, and Integer Factorization (based) Crypto (the IFC family, which best known member is RSA) is by far the fastest asymmetric crypto around for the task. In the application, if information retrieval quantitatively dominates, that might be an advantage.

Are there any other similar cryptographic functions we can use for this case, which are superior to the RSA scheme in speed and size?

Outside of systems closely related to RSA in that they belong to IFC, none that I have met since I started watching public key crypto¹.

Let's see how we can mitigate the issues:

• RSASign can be made faster by
  • Using a right-sized public modulus (and correspondingly splitting the information into blocks²). Currently the accepted minimum for signature is $n=2048$-bit public modulus, and all things being equal the signature cost per byte grows only slightly slower than $n^2$.
  • Using the Chinese Remainder Theorem method. Every speed-optimized implementation of RSA signature does that, because it reduces computational cost by a factor typically over three. Some implementations also use it to spread most of the workload on several CPU cores, further reducing encryption time. Implementations of RSA encryption can not use that method, because it requires the private key.
  • Using a public modulus product of $k>2$ primes. That's known as multiprime RSA. All things being equal, execution time is roughly halved when we go to 3 primes, divided by more than three with 4 primes. If high security assurance is not paramount, it would be reasonable to consider $(n,k)=(2048,4)$.
  • Using highly optimized implementation. Shay Gueron and Vlad Krasnov's Speed Records for Multi-prime RSA Using AVX2 Architectures (in CIT 2016) report $(1.9,\,1.0,\,0.6)$ million Skylake CPU cycles/signature for $n=2048$, $k=(2,\,3,\,4)$, translating to $(0.4,\,0.7,\,1.3)$MByte/s/core @3GHz (neglecting time and size overhead due to padding). And then dedicated hardware is a possibility.
• Size overhead depends on padding:
  • If we want to use something standardized and cut no corner, we can use ISO/IEC 9796-2 scheme 2 and a random nonce as wide as the hash size. The size overhead is $3h/2+16$ bits out of $n$, that is 206 bytes stored in a 256-byte cryptogram with SHA-256 and $n=2048$ (+24.3% overhead). Even if the data actually stored was entirely constant, it's unlikely two stored blocks would get identical until there are $2^{64}$, that is >3ZiB effective data.
  • If we accept something custom, a deterministic transformation (which allows to store a single copy of identical data blocks), and dropping cryptographic signing, the size overhead can be one bit per block (just apply a reversible transformation to the data followed by textbook RSA signature, that is textbook RSA encryption), or even zero (apply textbook RSA only to values lower than the public modulus after the reversible transformation, and generate the public/private key pair so that the high-order 64 bits of the public modulus are all-one).
• RSARecover can be made faster by
  • Using a low public exponent, such as $e=3$. This allows the exponentiation to use one modular squaring and one modular multiplication, rather than sixteen and one for the most common $e=65537$. Except for possible regulatory requirements, $e=3$ is fine. There's a saving by a factor of roughly 8, and now RSARecover typically is hundreds of times faster than RSASign (when $k=2$). We are talking some gigabit/s on a standard PC.
  • Using $e=2$, which allows a further saving by some factor like two. The name changes from RSA to Rabin signature, there are a few minor complications, but that remains fully academic and covered in ISO/IEC 9796-2.

---

¹ That was in 1980 during one of these strikes France is renewed for. My math (Spé) teacher dropped the official program and showed her class RSA, based on Martin Gardner's article.

² As pointed in comment, if we only do that splitting, we loose overall message integrity assurance (an adversary can swap signed blocks). I don't see that such assurance is indispensable in the context. But if we require it, we can prepend a fixed-width block number to a block's payload, at the expense of increased size overhead. A note suggests "Using CBC rather than ECB" but that does not seem to work unless the data signed is somewhat redundant.