Preimage selective trapdoor function: how to repair an easy problem
Summary: Public key cryptosystems are constructed by embedding a trapdoor into a one-way function. So, the one-wayness and the trapdoorness are vital to public key cryptography. In this paper, we propose a novel public key cryptographic primitive called preimage selective trapdoor function. This scenario allows to use exponentially many preimage to hide a plaintext even if the underlying function is not one-way. The compact knapsack problem is used to construct a probabilistic public key cryptosystem, the underlying encryption function of which is proven to be preimage selective trapdoor one-way functions under some linearization attack models. The constructive method can guarantee the noninjectivity of the underlying encryption function and the unique decipherability for ciphertexts simultaneously. It is heuristically argued that the security of the proposal cannot be compromised by a polynomial-time adversary even if the compact knapsack is easy to solve. We failed to provide any provable security results about the proposal; however, heuristic illustrations show that the proposal is secure against some known attacks including brute force attacks, linearization attacks, and key-recovery attacks. The proposal turns out to have acceptable key sizes and performs efficiently and hence is practical.
- A knapsack-based probabilistic encryption scheme
- A knapsack-type public key cryptosystem based on arithmetic in finite fields
- A method for obtaining digital signatures and public-key cryptosystems
- A polynomial-time algorithm for breaking the basic Merkle - Hellman cryptosystem
- A public key cryptosystem and a signature scheme based on discrete logarithms
- Adapting Density Attacks to Low-Weight Knapsacks
- Algebraic aspects of cryptography. With an appendix on hyperelliptic curves by Alfred J. Menezes, Yi-Hong Wu, and Robert J. Zuccherato
- An Improved Low-Density Subset Sum Algorithm
- Cryptanalysis of a knapsack-based probabilistic encryption scheme
- Cryptanalysis of the Chor-Rivest cryptosystem
- Enumerative source encoding
- Factorization of a 768-Bit RSA Modulus
- Hiding information and signatures in trapdoor knapsacks
- scientific article; zbMATH DE number 4213909 (Why is no real title available?)
- scientific article; zbMATH DE number 54007 (Why is no real title available?)
- scientific article; zbMATH DE number 1302853 (Why is no real title available?)
- scientific article; zbMATH DE number 1304120 (Why is no real title available?)
- scientific article; zbMATH DE number 691485 (Why is no real title available?)
- scientific article; zbMATH DE number 1088235 (Why is no real title available?)
- scientific article; zbMATH DE number 1759776 (Why is no real title available?)
- Improved low-density subset sum algorithms
- Knapsack public key cryptosystems and Diophantine approximation
- Low-density attack revisited
- New Definition of Density on Knapsack Cryptosystems
- Relation between the hardness of a problem and the number of its solutions
- Safer parameters for the Chor-Rivest cryptosystem
- Solving a system of linear Diophantine equations with lower and upper bounds on the variables.
- The Computational Complexity of Simultaneous Diophantine Approximation Problems
This page was built for publication: Preimage selective trapdoor function: how to repair an easy problem
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1718474)
