Are DSA and ECDSA provably secure assuming DL security?DSA, RSA, ECDSA etc - which one is cheapest for signing?Verifying DER encoded DSA/ECDSA signature with extra content?Can Alice send Bob a secure message with only DSA and no key exchange?Cost of attack on DSA with attack on DLPWhat is the intuition for ECDSA?How does the “biased-$k$ attack” on (EC)DSA work?Why is ECDSA secure?Is it actually possible to secure data with gpg DSA keys?Group signatures, security and ECDSASecurity of Fast Two-Party ECDSA Signing
How to project 3d image in the planes xy, xz, yz?
Compiling c files on ubuntu and using the executable on Windows
How did students remember what to practise between lessons without any sheet music?
What is the actual quality of machine translations?
Confusion about off peak timings of London trains
Random Unitary Matrices
What makes an item an artifact?
Can a user sell my software (MIT license) without modification?
How do governments keep track of their issued currency?
"You've got another thing coming" - translation into French
What's the largest optical telescope mirror ever put in space?
Is the term 'open source' a trademark?
How would a aircraft visually signal "in distress"?
Why only the fundamental frequency component is said to give useful power?
Russian equivalents of "no love lost"
How to retract an idea already pitched to an employer?
Find the Factorial From the Given Prime Relationship
How can I most clearly write a homebrew item that affects the ground below its radius after the initial explosion it creates?
Are DSA and ECDSA provably secure assuming DL security?
Can an Aarakocra use a shield while flying?
How did they achieve the Gunslinger's shining eye effect in Westworld?
Should I give professor gift at the beginning of my PhD?
What's the name of this light airplane?
Why is one of Madera Municipal's runways labelled with only "R" on both sides?
Are DSA and ECDSA provably secure assuming DL security?
DSA, RSA, ECDSA etc - which one is cheapest for signing?Verifying DER encoded DSA/ECDSA signature with extra content?Can Alice send Bob a secure message with only DSA and no key exchange?Cost of attack on DSA with attack on DLPWhat is the intuition for ECDSA?How does the “biased-$k$ attack” on (EC)DSA work?Why is ECDSA secure?Is it actually possible to secure data with gpg DSA keys?Group signatures, security and ECDSASecurity of Fast Two-Party ECDSA Signing
$begingroup$
Is there proof that the DSA construction, also used by ECDSA, is secure assuming that discrete logarithms in the relevant group representation are difficult?
provable-security dsa
asked 8 hours ago
MyriaMyria
943414
$endgroup$
add a comment |
$begingroup$
Is there proof that the DSA construction, also used by ECDSA, is secure assuming that discrete logarithms in the relevant group representation are difficult?
provable-security dsa
asked 8 hours ago
MyriaMyria
943414
$endgroup$
add a comment |
$begingroup$
Is there proof that the DSA construction, also used by ECDSA, is secure assuming that discrete logarithms in the relevant group representation are difficult?
provable-security dsa
asked 8 hours ago
MyriaMyria
943414
$endgroup$
Is there proof that the DSA construction, also used by ECDSA, is secure assuming that discrete logarithms in the relevant group representation are difficult?
provable-security dsa
provable-security dsa
asked 8 hours ago
MyriaMyria
943414
asked 8 hours ago
MyriaMyria
943414
asked 8 hours ago
MyriaMyria
943414
asked 8 hours ago
MyriaMyria
943414
asked 8 hours ago
MyriaMyria
943414
943414
add a comment |
add a comment |
1 Answer
1
active
oldest
votes
$begingroup$
(The (EC)DSA algorithm involves two functions: (i) the "conversion function" $f$, which for the case of DSA is a modulo $q$ operation and for ECDSA is the modulo $q$ operation applied to the $x$-coordinate of the input point; and (ii) $H$ a cryptographic hash function applied to the message.)
Brown [B] showed that the DLP implies security of ECDSA in the generic group model and under idealised modelling of the conversion function $f$. The second assumption is in particular unrealistic as in (EC)DSA it is implemented by a simple modulo operation.
There have been some recent results by Fersch et al. [FKP1,FKP2] which have tried to relax the above assumptions. In [FKP1] it is shown that under weaker (but still quite strong) assumption on the conversion function $f$ (and under some reasonable assumption on the hash function $H$) that DLP implies the security of (EC)DSA. Perhaps the security argument with the most reasonable assumptions is given in [FKP2]. There, assuming that the hash function $H$ is modelled as a random oracle, and the signer issues at most one signature per message, then EC(DSA) is unforgeable if and only if they are key-only unforgeable (this applies also to other schemes like the Russian GOST 34.14 and the Chinese SM2). It is not known if the key-only security of (EC)DSA reduces to DLP.
So, in short, the answer would be no, not under reasonable assumptions.
(Note however, that there are close variants of the (EC)DSA, most notably the Schnorr signature and the scheme by Brickell et al [B+] which do come with security reductions in the random oracle model. Also it is baffling why (EC)DSA is still in use since the patent on Schnorr expired in 2008.)
[B] Brown. Generic Groups, Collision Resistance and ECDSA.
[B+] Brickell et al. Design validations for discrete logarithm based signature schemes. PKC'00.
[FKP1] Fersch, Kiltz and Pöttering. On the Provable Security of (EC)DSA Signatures. CCS'16.
[FKP2] Fersch, Kiltz and Pöttering. On the One-Per-Message Unforgeability of (EC)DSA and its Variants. TCC'17.
answered 7 hours ago
Occams_TrimmerOccams_Trimmer
1,74411119
$endgroup$
$begingroup$
Your answer is better than mine was.
$endgroup$
– fgrieu
7 hours ago
$begingroup$
Based on context, $f$ is the reduction of the group operation $g^k$ interpreted as an integer, taken modulo $q$?
$endgroup$
– Myria
6 hours ago
$begingroup$
That's correct, and $H$ is the hash function applied to the message. I'll add it to the answer.
$endgroup$
– Occams_Trimmer
6 hours ago
add a comment |
Your Answer
StackExchange.ready(function()
var channelOptions =
tags: "".split(" "),
id: "281"
;
initTagRenderer("".split(" "), "".split(" "), channelOptions);
StackExchange.using("externalEditor", function()
// Have to fire editor after snippets, if snippets enabled
if (StackExchange.settings.snippets.snippetsEnabled)
StackExchange.using("snippets", function()
createEditor();
);
else
createEditor();
);
function createEditor()
StackExchange.prepareEditor(
heartbeatType: 'answer',
autoActivateHeartbeat: false,
convertImagesToLinks: false,
noModals: true,
showLowRepImageUploadWarning: true,
reputationToPostImages: null,
bindNavPrevention: true,
postfix: "",
imageUploader:
brandingHtml: "Powered by u003ca class="icon-imgur-white" href="https://imgur.com/"u003eu003c/au003e",
contentPolicyHtml: "User contributions licensed under u003ca href="https://creativecommons.org/licenses/by-sa/3.0/"u003ecc by-sa 3.0 with attribution requiredu003c/au003e u003ca href="https://stackoverflow.com/legal/content-policy"u003e(content policy)u003c/au003e",
allowUrls: true
,
noCode: true, onDemand: true,
discardSelector: ".discard-answer"
,immediatelyShowMarkdownHelp:true
);
);
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function ()
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fcrypto.stackexchange.com%2fquestions%2f71029%2fare-dsa-and-ecdsa-provably-secure-assuming-dl-security%23new-answer', 'question_page');
);
Post as a guest
Required, but never shown
1 Answer
1
active
oldest
votes
1 Answer
1
active
oldest
votes
active
oldest
votes
active
oldest
votes
$begingroup$
(The (EC)DSA algorithm involves two functions: (i) the "conversion function" $f$, which for the case of DSA is a modulo $q$ operation and for ECDSA is the modulo $q$ operation applied to the $x$-coordinate of the input point; and (ii) $H$ a cryptographic hash function applied to the message.)
Brown [B] showed that the DLP implies security of ECDSA in the generic group model and under idealised modelling of the conversion function $f$. The second assumption is in particular unrealistic as in (EC)DSA it is implemented by a simple modulo operation.
There have been some recent results by Fersch et al. [FKP1,FKP2] which have tried to relax the above assumptions. In [FKP1] it is shown that under weaker (but still quite strong) assumption on the conversion function $f$ (and under some reasonable assumption on the hash function $H$) that DLP implies the security of (EC)DSA. Perhaps the security argument with the most reasonable assumptions is given in [FKP2]. There, assuming that the hash function $H$ is modelled as a random oracle, and the signer issues at most one signature per message, then EC(DSA) is unforgeable if and only if they are key-only unforgeable (this applies also to other schemes like the Russian GOST 34.14 and the Chinese SM2). It is not known if the key-only security of (EC)DSA reduces to DLP.
So, in short, the answer would be no, not under reasonable assumptions.
(Note however, that there are close variants of the (EC)DSA, most notably the Schnorr signature and the scheme by Brickell et al [B+] which do come with security reductions in the random oracle model. Also it is baffling why (EC)DSA is still in use since the patent on Schnorr expired in 2008.)
[B] Brown. Generic Groups, Collision Resistance and ECDSA.
[B+] Brickell et al. Design validations for discrete logarithm based signature schemes. PKC'00.
[FKP1] Fersch, Kiltz and Pöttering. On the Provable Security of (EC)DSA Signatures. CCS'16.
[FKP2] Fersch, Kiltz and Pöttering. On the One-Per-Message Unforgeability of (EC)DSA and its Variants. TCC'17.
answered 7 hours ago
Occams_TrimmerOccams_Trimmer
1,74411119
$endgroup$
$begingroup$
Your answer is better than mine was.
$endgroup$
– fgrieu
7 hours ago
$begingroup$
Based on context, $f$ is the reduction of the group operation $g^k$ interpreted as an integer, taken modulo $q$?
$endgroup$
– Myria
6 hours ago
$begingroup$
That's correct, and $H$ is the hash function applied to the message. I'll add it to the answer.
$endgroup$
– Occams_Trimmer
6 hours ago
add a comment |
$begingroup$
(The (EC)DSA algorithm involves two functions: (i) the "conversion function" $f$, which for the case of DSA is a modulo $q$ operation and for ECDSA is the modulo $q$ operation applied to the $x$-coordinate of the input point; and (ii) $H$ a cryptographic hash function applied to the message.)
Brown [B] showed that the DLP implies security of ECDSA in the generic group model and under idealised modelling of the conversion function $f$. The second assumption is in particular unrealistic as in (EC)DSA it is implemented by a simple modulo operation.
There have been some recent results by Fersch et al. [FKP1,FKP2] which have tried to relax the above assumptions. In [FKP1] it is shown that under weaker (but still quite strong) assumption on the conversion function $f$ (and under some reasonable assumption on the hash function $H$) that DLP implies the security of (EC)DSA. Perhaps the security argument with the most reasonable assumptions is given in [FKP2]. There, assuming that the hash function $H$ is modelled as a random oracle, and the signer issues at most one signature per message, then EC(DSA) is unforgeable if and only if they are key-only unforgeable (this applies also to other schemes like the Russian GOST 34.14 and the Chinese SM2). It is not known if the key-only security of (EC)DSA reduces to DLP.
So, in short, the answer would be no, not under reasonable assumptions.
(Note however, that there are close variants of the (EC)DSA, most notably the Schnorr signature and the scheme by Brickell et al [B+] which do come with security reductions in the random oracle model. Also it is baffling why (EC)DSA is still in use since the patent on Schnorr expired in 2008.)
[B] Brown. Generic Groups, Collision Resistance and ECDSA.
[B+] Brickell et al. Design validations for discrete logarithm based signature schemes. PKC'00.
[FKP1] Fersch, Kiltz and Pöttering. On the Provable Security of (EC)DSA Signatures. CCS'16.
[FKP2] Fersch, Kiltz and Pöttering. On the One-Per-Message Unforgeability of (EC)DSA and its Variants. TCC'17.
answered 7 hours ago
Occams_TrimmerOccams_Trimmer
1,74411119
$endgroup$
$begingroup$
Your answer is better than mine was.
$endgroup$
– fgrieu
7 hours ago
$begingroup$
Based on context, $f$ is the reduction of the group operation $g^k$ interpreted as an integer, taken modulo $q$?
$endgroup$
– Myria
6 hours ago
$begingroup$
That's correct, and $H$ is the hash function applied to the message. I'll add it to the answer.
$endgroup$
– Occams_Trimmer
6 hours ago
add a comment |
$begingroup$
(The (EC)DSA algorithm involves two functions: (i) the "conversion function" $f$, which for the case of DSA is a modulo $q$ operation and for ECDSA is the modulo $q$ operation applied to the $x$-coordinate of the input point; and (ii) $H$ a cryptographic hash function applied to the message.)
Brown [B] showed that the DLP implies security of ECDSA in the generic group model and under idealised modelling of the conversion function $f$. The second assumption is in particular unrealistic as in (EC)DSA it is implemented by a simple modulo operation.
There have been some recent results by Fersch et al. [FKP1,FKP2] which have tried to relax the above assumptions. In [FKP1] it is shown that under weaker (but still quite strong) assumption on the conversion function $f$ (and under some reasonable assumption on the hash function $H$) that DLP implies the security of (EC)DSA. Perhaps the security argument with the most reasonable assumptions is given in [FKP2]. There, assuming that the hash function $H$ is modelled as a random oracle, and the signer issues at most one signature per message, then EC(DSA) is unforgeable if and only if they are key-only unforgeable (this applies also to other schemes like the Russian GOST 34.14 and the Chinese SM2). It is not known if the key-only security of (EC)DSA reduces to DLP.
So, in short, the answer would be no, not under reasonable assumptions.
(Note however, that there are close variants of the (EC)DSA, most notably the Schnorr signature and the scheme by Brickell et al [B+] which do come with security reductions in the random oracle model. Also it is baffling why (EC)DSA is still in use since the patent on Schnorr expired in 2008.)
[B] Brown. Generic Groups, Collision Resistance and ECDSA.
[B+] Brickell et al. Design validations for discrete logarithm based signature schemes. PKC'00.
[FKP1] Fersch, Kiltz and Pöttering. On the Provable Security of (EC)DSA Signatures. CCS'16.
[FKP2] Fersch, Kiltz and Pöttering. On the One-Per-Message Unforgeability of (EC)DSA and its Variants. TCC'17.
answered 7 hours ago
Occams_TrimmerOccams_Trimmer
1,74411119
$endgroup$
(The (EC)DSA algorithm involves two functions: (i) the "conversion function" $f$, which for the case of DSA is a modulo $q$ operation and for ECDSA is the modulo $q$ operation applied to the $x$-coordinate of the input point; and (ii) $H$ a cryptographic hash function applied to the message.)
Brown [B] showed that the DLP implies security of ECDSA in the generic group model and under idealised modelling of the conversion function $f$. The second assumption is in particular unrealistic as in (EC)DSA it is implemented by a simple modulo operation.
There have been some recent results by Fersch et al. [FKP1,FKP2] which have tried to relax the above assumptions. In [FKP1] it is shown that under weaker (but still quite strong) assumption on the conversion function $f$ (and under some reasonable assumption on the hash function $H$) that DLP implies the security of (EC)DSA. Perhaps the security argument with the most reasonable assumptions is given in [FKP2]. There, assuming that the hash function $H$ is modelled as a random oracle, and the signer issues at most one signature per message, then EC(DSA) is unforgeable if and only if they are key-only unforgeable (this applies also to other schemes like the Russian GOST 34.14 and the Chinese SM2). It is not known if the key-only security of (EC)DSA reduces to DLP.
So, in short, the answer would be no, not under reasonable assumptions.
(Note however, that there are close variants of the (EC)DSA, most notably the Schnorr signature and the scheme by Brickell et al [B+] which do come with security reductions in the random oracle model. Also it is baffling why (EC)DSA is still in use since the patent on Schnorr expired in 2008.)
[B] Brown. Generic Groups, Collision Resistance and ECDSA.
[B+] Brickell et al. Design validations for discrete logarithm based signature schemes. PKC'00.
[FKP1] Fersch, Kiltz and Pöttering. On the Provable Security of (EC)DSA Signatures. CCS'16.
[FKP2] Fersch, Kiltz and Pöttering. On the One-Per-Message Unforgeability of (EC)DSA and its Variants. TCC'17.
answered 7 hours ago
Occams_TrimmerOccams_Trimmer
1,74411119
edited 6 hours ago
answered 7 hours ago
Occams_TrimmerOccams_Trimmer
1,74411119
answered 7 hours ago
Occams_TrimmerOccams_Trimmer
1,74411119
answered 7 hours ago
Occams_TrimmerOccams_Trimmer
1,74411119
1,74411119
$begingroup$
Your answer is better than mine was.
$endgroup$
– fgrieu
7 hours ago
$begingroup$
Based on context, $f$ is the reduction of the group operation $g^k$ interpreted as an integer, taken modulo $q$?
$endgroup$
– Myria
6 hours ago
$begingroup$
That's correct, and $H$ is the hash function applied to the message. I'll add it to the answer.
$endgroup$
– Occams_Trimmer
6 hours ago
add a comment |
$begingroup$
Your answer is better than mine was.
$endgroup$
– fgrieu
7 hours ago
$begingroup$
Based on context, $f$ is the reduction of the group operation $g^k$ interpreted as an integer, taken modulo $q$?
$endgroup$
– Myria
6 hours ago
$begingroup$
That's correct, and $H$ is the hash function applied to the message. I'll add it to the answer.
$endgroup$
– Occams_Trimmer
6 hours ago
$begingroup$
Your answer is better than mine was.
$endgroup$
– fgrieu
7 hours ago
$begingroup$
Your answer is better than mine was.
$endgroup$
– fgrieu
7 hours ago
$begingroup$
Based on context, $f$ is the reduction of the group operation $g^k$ interpreted as an integer, taken modulo $q$?
$endgroup$
– Myria
6 hours ago
$begingroup$
Based on context, $f$ is the reduction of the group operation $g^k$ interpreted as an integer, taken modulo $q$?
$endgroup$
– Myria
6 hours ago
$begingroup$
That's correct, and $H$ is the hash function applied to the message. I'll add it to the answer.
$endgroup$
– Occams_Trimmer
6 hours ago
$begingroup$
That's correct, and $H$ is the hash function applied to the message. I'll add it to the answer.
$endgroup$
– Occams_Trimmer
6 hours ago
add a comment |
Thanks for contributing an answer to Cryptography Stack Exchange!
- Please be sure to answer the question. Provide details and share your research!
But avoid …
- Asking for help, clarification, or responding to other answers.
- Making statements based on opinion; back them up with references or personal experience.
Use MathJax to format equations. MathJax reference.
To learn more, see our tips on writing great answers.
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function ()
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fcrypto.stackexchange.com%2fquestions%2f71029%2fare-dsa-and-ecdsa-provably-secure-assuming-dl-security%23new-answer', 'question_page');
);
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
