Incompressible cryptography (Q2170026)

Incompressible encryption produces very large ciphertexts hence adversaries may exhaust their available storage to attack the scheme. Even more, if the adversary stores anything much smaller than the ciphertext, the adversary learns absolutely nothing about the message, even if the secret key later leaks. Incompressible signatures can be made arbitrarily large and an adversary cannot produce a signature on any message unless one of the signatures is stored essentially in its entirety. An incompressible encryption scheme is built based on functional encryption. In these last schemes, a function class is considered and from a master secret key, a particular secret key \(\mathtt{seckey}_f\) is getting for each function \(f\) in the class. Given a ciphertext \(c=\mathtt{Enc}(\mathtt{masterpubkey},m)\) corresponding to a message \(m\) a decryption process gets \(f(m) = \mathtt{Dec}(\mathtt{seckey}_m,c)\). It is used a \((k,\varepsilon)\)-strong average min-entropy extractor \(\mathtt{Extract}:(c,R,z_0)\mapsto z_1\), where \(R\) is a very large bit string, \(c\) is a cipher to recover a map, and \(z_0,z_1\) are partial masks for a plaintext. The string \(R\) is included within the ciphertext produced by the incompressible encryption scheme. For an incompressible signature scheme, a conventional secure public key signature scheme may be used. For a message \(m\), a large bit string \(R\) is generated, and the message \(R\|m\) is signed with the conventional scheme to obtain the signature \(\sigma\). The new signature is \(R\|\sigma\). Security proofs are provided in terms of special games Prover-Adversary in the context of incompressible cryptography and some comparisons are done with former schemes. For the entire collection see [Zbl 1493.94001].