0
$\begingroup$

In DGHV Security How to get reliable oracle for least significant bit and then uses binary GCD algorothm that uses reliable oracle to find secret key p.Also what is oracle. Is this a turing machine.How we get Least Significant Bit from it. Please giude. Thanks

$\endgroup$

1 Answer 1

2
$\begingroup$

You should read this article about Security of DGHV Encryption.

Oracle machine is an abstract machine used to study decision problems. It can be visualized as a Turing machine with a black box, called an oracle, which is able to decide certain decision problems in a single operation. The problem can be of any complexity class. Even undecidable problems, like the halting problem, can be used.

$\endgroup$
2
  • $\begingroup$ Thanks for reply. I want to know how security of DGHV can be breached using oracle and Binary GCD. As I study the eprint.iacr.org/2009/616.pdf But Not able to understand Section 4.1 Theorem4.2 Subroutine Learn-LSB(z,pk) and Binary GCD following it. Any help be appreciated $\endgroup$
    – vivek
    Apr 19, 2016 at 6:11
  • $\begingroup$ @HakanALTAS the link is broken but its edit distance to the correct link is only one deletion :p So, could you please fix it? I'd do it by myself, but I think editing one answer because of a single character may not fit the editing criteria... $\endgroup$ May 26, 2016 at 19:20

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.