 |
"Comments requested." |
|
(reply) |
The author welcomes suggestions. What had been omitted which should be included? What is unclear?
2 replies:
|
|
|
"Strongly generic sets" |
|
(reply) |
|
I think it would be interesting to discuss how fast the fraction from the definition of generic set goes to 1. Are the problems, mentioned in the survey, strongly generic decidable? I think the strongly generic decidability of a problem is a more strong :) argument for the uselessness of this problem for cryptography than just generic decidability. Becouse in the case of non-strongly generic set we can generate inputs from the black hole which is still big enough (is not exponentially small). For example, it seems (may be I'm wrong :) ) that RSA numbers (numbers of form pq where p and q are prime) form a negligible set but it is not a problem for RSA cryptosystem because this set is big enough (greater than 2^n/n for inputs of the length n).
|
|
"On the notion of the generic algorithm" |
|
(reply) |
|
Generic algorithm gives a correct answer on the generic set and gives the answer "I don't know" on the black hole. For this the generic set must be easy decidable. I think it may extend this notion by elimination of the last property. Namely we say that problem is generically decidable if there is a total algorithm A such that gives a correct answer on the generic set. No matter how A works outside of generic set. It may loop, give wrong answer. Moreover generic set may be undecidable. I argue that in cryptography such generic algorithms may be as useful as original generic algorithms. Becouse for a searching problem we can check a found answer and we can terminate long computation of the algoritm on an input from the black hole.
|
|
