Preimage selective trapdoor function: how to repair an easy problem
type: Item
instance of: scholarly article
title: Preimage selective trapdoor function: how to repair an easy problem
zbMATH Open document ID: 1407.94158
DOI: 10.1155/2014/475678
author: Baocang Wang
published in: Mathematical Problems in Engineering
publication date: 2019-02-08T00:00:00Z
review text: 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.
Mathematics Subject Classification ID: 94A60
Mathematics Subject Classification ID: 11Y16
zbMATH DE Number: 7016519
Wikidata QID: Q59067642
MaRDI profile type: Publication
full work available at URL: https://doi.org/10.1155/2014/475678
OpenAlex ID: W1964597925
cites work: Q4249337
cites work: A public key cryptosystem and a signature scheme based on discrete logarithms
cites work: Relation between the hardness of a problem and the number of its solutions
cites work: Cryptanalysis of a knapsack-based probabilistic encryption scheme
cites work: Q4004196
cites work: The Computational Complexity of Simultaneous Diophantine Approximation Problems
cites work: Knapsack Public Key Cryptosystems and Diophantine Approximation
cites work: Q4364552
cites work: Q4250818
cites work: A method for obtaining digital signatures and public-key cryptosystems
cites work: A knapsack-type public key cryptosystem based on arithmetic in finite fields
cites work: Q4536799
cites work: Enumerative source encoding
cites work: Adapting Density Attacks to Low-Weight Knapsacks
cites work: Cryptanalysis of the Chor-Rivest cryptosystem
cites work: Safer parameters for the Chor-Rivest cryptosystem
cites work: Low-density attack revisited
cites work: New Definition of Density on Knapsack Cryptosystems
cites work: An Improved Low-Density Subset Sum Algorithm
cites work: Improved low-density subset sum algorithms
cites work: Algebraic aspects of cryptography. With an appendix on hyperelliptic curves by Alfred J. Menezes, Yi-Hong Wu, and Robert J. Zuccherato
cites work: Q3360789
cites work: A knapsack-based probabilistic encryption scheme
cites work: Factorization of a 768-Bit RSA Modulus
cites work: Solving a system of linear Diophantine equations with lower and upper bounds on the variables.
cites work: Hiding information and signatures in trapdoor knapsacks
cites work: A polynomial-time algorithm for breaking the basic Merkle - Hellman cryptosystem
cites work: Q4314376
description: scientific article; zbMATH DE number 7016519