IACR News item: 26 March 2020
Robert A. Threlfall
ePrint Report
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.
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 and secret-key aware as well as defined by M. Barbosa and P. Farshim (2009). Assuming that our one-way trapdoor function is computationally hard to invert, then this encryption 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.
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 and secret-key aware as well as defined by M. Barbosa and P. Farshim (2009). Assuming that our one-way trapdoor function is computationally hard to invert, then this encryption 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.
Additional news items may be found on the IACR news page.