Are DSA and ECDSA provably secure assuming DL security?DSA, RSA, ECDSA etc - which one is cheapest for...
Where does "0 packages can be updated." come from?
How is water heavier than petrol, even though its molecular weight is less than petrol?
Passing multiple files through stdin (over ssh)
"You've got another thing coming" - translation into French
Why only the fundamental frequency component is said to give useful power?
Watts vs. Volt Amps
What could have caused a rear derailleur to end up in the back wheel suddenly?
Was the output of the C64 SID chip 8 bit sound?
How can drunken, homicidal elves successfully conduct a wild hunt?
Is the term 'open source' a trademark?
What should the arbiter and what should have I done in this case?
How to build suspense or so to establish and justify xenophobia of characters in the eyes of the reader?
Should I give professor gift at the beginning of my PhD?
Compiling c files on ubuntu and using the executable on Windows
Smooth switching between 12 V batteries, with a toggle switch
What makes an item an artifact?
How Can I Tell The Difference Between Unmarked Sugar and Stevia?
Can an Aarakocra use a shield while flying?
Can anyone identify this tank?
Are there downsides to using std::string as a buffer?
What is the actual quality of machine translations?
Find the Factorial From the Given Prime Relationship
An average heaven where everyone has sexless golden bodies and is bored
Should an arbiter claim draw at a K+R vs K+R endgame?
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 9 hours ago
MyriaMyria
948414
$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 9 hours ago
MyriaMyria
948414
$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 9 hours ago
MyriaMyria
948414
$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 9 hours ago
MyriaMyria
948414
asked 9 hours ago
MyriaMyria
948414
asked 9 hours ago
MyriaMyria
948414
asked 9 hours ago
MyriaMyria
948414
asked 9 hours ago
MyriaMyria
948414
948414
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 8 hours ago
Occams_TrimmerOccams_Trimmer
1,74411119
$endgroup$
$begingroup$
Your answer is better than mine was.
$endgroup$
– fgrieu
8 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
8 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
8 hours ago
$begingroup$
As I'm always confused about this bit, what's the relationship of EdDSA to the (EC)DSA answer?
$endgroup$
– grawity
3 mins 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 8 hours ago
Occams_TrimmerOccams_Trimmer
1,74411119
$endgroup$
$begingroup$
Your answer is better than mine was.
$endgroup$
– fgrieu
8 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
8 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
8 hours ago
$begingroup$
As I'm always confused about this bit, what's the relationship of EdDSA to the (EC)DSA answer?
$endgroup$
– grawity
3 mins 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 8 hours ago
Occams_TrimmerOccams_Trimmer
1,74411119
$endgroup$
$begingroup$
Your answer is better than mine was.
$endgroup$
– fgrieu
8 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
8 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
8 hours ago
$begingroup$
As I'm always confused about this bit, what's the relationship of EdDSA to the (EC)DSA answer?
$endgroup$
– grawity
3 mins 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 8 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 8 hours ago
Occams_TrimmerOccams_Trimmer
1,74411119
edited 7 hours ago
answered 8 hours ago
Occams_TrimmerOccams_Trimmer
1,74411119
answered 8 hours ago
Occams_TrimmerOccams_Trimmer
1,74411119
answered 8 hours ago
Occams_TrimmerOccams_Trimmer
1,74411119
1,74411119
$begingroup$
Your answer is better than mine was.
$endgroup$
– fgrieu
8 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
8 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
8 hours ago
$begingroup$
As I'm always confused about this bit, what's the relationship of EdDSA to the (EC)DSA answer?
$endgroup$
– grawity
3 mins ago
add a comment |
$begingroup$
Your answer is better than mine was.
$endgroup$
– fgrieu
8 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
8 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
8 hours ago
$begingroup$
As I'm always confused about this bit, what's the relationship of EdDSA to the (EC)DSA answer?
$endgroup$
– grawity
3 mins ago
$begingroup$
Your answer is better than mine was.
$endgroup$
– fgrieu
8 hours ago
$begingroup$
Your answer is better than mine was.
$endgroup$
– fgrieu
8 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
8 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
8 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
8 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
8 hours ago
$begingroup$
As I'm always confused about this bit, what's the relationship of EdDSA to the (EC)DSA answer?
$endgroup$
– grawity
3 mins ago
$begingroup$
As I'm always confused about this bit, what's the relationship of EdDSA to the (EC)DSA answer?
$endgroup$
– grawity
3 mins 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
