In public key encryption with keyword search I read this sentence in Billinear Diffie Hellman problem.
It means the researchers are making an assumption on how hard it is to solve the problem based on how hard it is to solve in practice. This is similar to how we assume Integer Factorization or Discrete log problem are intractable, yet the problem doesn't fall into many useful computational complexity classes to better understand it. All they are saying is they believe the problem is hard to solve, so they are using that assumption to prove further results. E.g., if I say this one problem is hard to solve as an assumption, then if I show any other scheme is just as hard or harder, then my assumption follows for those schemes. Most of the reasons for these assumptions fall from reductions from one scheme to another. For example, there exists a reduction from Integer Factorization to Discrete Log Problem, so Discrete Log problem is at least as difficult to solve as Integer Factorization.
I find this to be a very handy resources in understanding this and where reductions do exist: http://www.ecrypt.eu.org/documents/D.MAYA.3.pdf
A negligible function is any function f() such that f(x) -> 0 faster than any function of the form 1/P(x), where P() is a polynomial function, when x -> infinity. Informally, computational security is usually proved by showing that breaking a given scheme is as hard as distinguishing two probability distributions whose distance is a negligible function (in the security parameter) : as long as the adversary runs in polynomial time (at most), he will not manage to distinguish those distibutions.
have a look at the following link for the negligible function:
http://crypto.stackexchange.com/questions/5832/what-exactly-is-a-negligible-and-non-negligible-function
- Badges
- Science topic
- Similar topics
- Statistics
- Survey