4
$\begingroup$

Alice has a private key, $x$, and a public key $P = [x] \cdot G$ in a group of order $n$.

Alice would like to also publish her inverse public key (inverted modulo the group order) $P_{inv} = [x^{-1} \mod n] \cdot G $, for the purposes of a simple homomorphic encryption algorithm that allows people to re-encrypt documents for her. For simplicity, I'm going to assume that that system is otherwise perfectly secure.

Alice is using a pairing-based curve, and that same public key $P$ is used in a number of pairing operations, signing operations, and DH key exchanges that could be observed by an attacker.

Can this be used to make an attack on Alice's private key easier? Now we have 2 equations - instead of one.

The closest related proof I've found is: Variations of Diffie-Hellman Problem, which demonstrated that it's hard to get $P_{inv}$ from $P$.

Does anyone know of a paper that uses $P_{inv}$ or uses published public "inversions"? of keys in this way?

Improve this question
$\endgroup$
5
  • $\begingroup$ @fgrieu thanks, i made some edits. $\endgroup$ – Erik Aronesty May 14 '20 at 15:18
  • $\begingroup$ It occurred to me that the related proof I posted might be used to prove that it's impossible to prove that this is hard using a $Oracle([x] \cdot G, [x^-1] \cdot G)$ to break the DLP. which makes my head hurt - but maybe there's some other way of doing it. $\endgroup$ – Erik Aronesty May 14 '20 at 15:26
  • 1
    $\begingroup$ The paper you link shows that $\mathsf{CDH}\iff \mathsf{InvCDH}$. The later problem is to, on input $(g, g^x)$, compute $g^{x^{-1}}$. This means that if you have oracle access to such a problem, you can break CDH. You're essentially suggesting to give the adversary the oracle queried on the particular point $\mathcal{O}(g, g^x) = g^{x^{-1}}$. Their attack seems to require it queried on $\mathcal{O}(g^x, g) = g^{x^2}$. I don't see how to use your single query to implement their reduction, but that doesn't mean what you do is secure (other reductions may exist). $\endgroup$ – Mark May 14 '20 at 23:42
  • 1
    $\begingroup$ This question and answer indicates that there's no known way to take advantage of $P_{inv}$: crypto.stackexchange.com/questions/35553/… $\endgroup$ – Aman Grewal May 17 '20 at 13:04
  • $\begingroup$ I think that link is the answer. $\endgroup$ – Erik Aronesty May 21 '20 at 17:16

Your Answer

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

Browse other questions tagged or ask your own question.