2
$\begingroup$

Bilinear Pairings are widely used in many new schemes like Group Signature and Aggregate Signature. The problem is whether it is post-quantum secure. In other words, does Bilinear Diffie-Hellman intractability assumption stand against a quantum computer?

With a quantum computer, Shor's Algorithm solves Prime Factorization and Discrete Log problem in polynomial time, which nullifies the security of plain Diffie-Hellman-based schemes. But Bilinear Diffie-Hellman is a bit different since it has a mapping e(g,g), instead of plain g. I haven't seen any quantum-resistance analysis/discussion on Pairing-related papers, nor have I seen any paper that specifically discusses this topic. Anyone has a clue?

Related pages: What is the post-quantum cryptography alternative to Diffie-Hellman?

$\endgroup$

1 Answer 1

6
$\begingroup$

Is pairing-based crypto post-quantum secure?

No. That's because solving the Discrete Logarithm Problem in one of the pairing's source groups breaks the pairing's security, and Shor's algorithm running on a Cryptographically Relevant Quantum Computer could solve such DLP.

More justification per request: all usages of pairings in cryptography assume that the Computational Diffie-Hellman problem is hard on one at least of the pairing's source group (often noted $\mathbb G_1$ or/and designated the Gap Group). Breaking the DLP also breaks CDH, thus a security assumption on the pairing. Typical example: Dan Boneh, Ben Lynn, Hovav Shacham, Short Signatures from the Weil Pairing, in JoC 2004:

Our signature scheme uses groups where the CDH problem is hard.

$\endgroup$
1

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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