Cryptology ePrint Archive: Report 2020/353

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

Robert A. Threlfall

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 know of no way 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 $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$).

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. The encryption step is amenable to parallelization, both across bits, as well as at the level of encrypting a single bit. 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.

Category / Keywords: public-key cryptography / Probabilistic public-key encryption, Adaptive chosen-ciphertext attack, Binary quadratic forms, Class number, Quadratic residues, Quadratic nonresidues, Quartic reciprocity

Date: received 24 Mar 2020, last revised 5 Apr 2020

Contact author: rthrelfall at secure-systems org

Available format(s): PDF | BibTeX Citation

Note: Fixed a spelling mistake and revised fault injection section.

Version: 20200405:221547 (All versions of this report)

Short URL:

[ Cryptology ePrint archive ]