Paper 2020/353

A Probabilistic Public Key Encryption Scheme Based on Quartic Reciprocity (Draft V1.22)

Abstract

Using a novel class of single bit one-way trapdoor functions we construct a theoretical probabilistic public key encryption scheme that has many interesting properties. These functions are constructed from binary quadratic forms and rational quartic reciprocity laws. They are not based on class group operations nor on universal one-way hash functions. Inverting these functions appears to be as difficult as factoring, and other than factoring, we know of no reductions between this new number theory problem and the standard number theoretic problems used cryptographically. We are unable to find away to construct a ciphertext without knowing the plaintext, hence this encryption scheme appears to be plaintext aware ($PA1$). By using quartic reciprocity properties there is less information leakage than with quadratic reciprocity based schemes and consequently this encryption scheme appears to be completely non-malleable as defined by M. Fischlin (2005), and strongly plaintext aware ($SPA$) and secret-key aware ($SKA$) as well, as defined by M. Barbosa and P. Farshim (2009). Assuming plaintext awareness ($PA1$), the difficulty of inverting our one-way trapdoor function and the hardness of certain standard number theoretic problems, then this scheme is provably secure against adaptive chosen ciphertext attacks ($IND-CCA2$). The public key is a product of two secret primes. Decryption is fast, requiring just one modular multiplication and one Jacobi symbol evaluation. The encryption step is polynomial time, but slow, and there is a great deal of message expansion. However, the encryption step is amenable to parallelization, both across bits, as well as at the level of encrypting a single bit. The encryption step is also amenable to asynchronous pre-computation. After the pre-computation step, for a $t$ bit public key, encryption only requires three multiplications (with $t+ 2c + 5$ bit length numbers) per encrypted bit, where $100 \leq c \leq 150$ is an adjustable security parameter. The computational cost to break an encrypted bit can be optionally adjusted down on a per bit basis. With no additional keys, multiple senders can individually join secret information to each encrypted bit without changing the parity of the encrypted bit. (Recovering this secret information is harder than recovering the private key.) Each sender can separately and publicly reveal their secret information without revealing the plaintext bit. The senders of the encrypted message bit can also individually authenticate they are senders without the use of a message authentication code and without revealing the plaintext bit. We are not aware of any hardware faults or other adverse events that might occur during decryption that could be exploited to break the secret key. Encryption faults can occur that could be exploited to reveal plaintext bits, however, these faults can be detected with high probability and with low computational cost.

Note: Numerous small errors corrected.