Are there any symmetric cryptosystems based on computational complexity assumptions?What is the relation between computational security and provable security?Reason for difference in assumptions for practical private-key and public-key cryptoWhat does “Worst-case hardness” mean in lattice-based cryptography?Do we need symmetric cryptosystems?Reductionist proofs of decisional problems to computationalAre there any quantum-resistant symmetric encryption schemes?Defining Symmetric vs Asymmetric cryptosystemsIs AES (or DES) provably secure? What is the hardness assumption underlying these cryptosystems?Lattice Crypto worst case to average caseProof by reduction vs. hybrid argumentWhat conditions does a provable secure cryptosystem satisfy?
What is the recommended procedure to land a taildragger in a crosswind?
How did NASA Langley end up with the first 737?
Sorting with IComparable design
How to determine if a hyphen (-) exists inside a column
Can a ring of spell storing and access to Find spells produce an endless menagerie?
Cardio work for Muay Thai fighters
...And they were stumped for a long time
How to melt snow without fire or using body heat?
Best shape for a necromancer's undead minions for battle?
What would prevent living skin from being a good conductor for magic?
Why sampling a periodic signal doesn't yield a periodic discrete signal?
Security vulnerabilities of POST over SSL
Which European Languages are not Indo-European?
Creating second map without labels using QGIS?
Navigating a quick return to previous employer
Using too much dialogue?
xcolor breaking ligatures
Is my plasma cannon concept viable?
Does an eye for an eye mean monetary compensation?
Who knighted this Game of Thrones character?
Burned out due to current job, Can I take a week of vacation between jobs?
Are cells guaranteed to get at least one mitochondrion when they divide?
What did the 'turbo' button actually do?
Why do Russians almost not use verbs of possession akin to "have"?
Are there any symmetric cryptosystems based on computational complexity assumptions?
What is the relation between computational security and provable security?Reason for difference in assumptions for practical private-key and public-key cryptoWhat does “Worst-case hardness” mean in lattice-based cryptography?Do we need symmetric cryptosystems?Reductionist proofs of decisional problems to computationalAre there any quantum-resistant symmetric encryption schemes?Defining Symmetric vs Asymmetric cryptosystemsIs AES (or DES) provably secure? What is the hardness assumption underlying these cryptosystems?Lattice Crypto worst case to average caseProof by reduction vs. hybrid argumentWhat conditions does a provable secure cryptosystem satisfy?
$begingroup$
Are there any symmetric cryptosystems which are provably secure in the sense that there exists a reduction from their security to the hardness of some underlying hard problem such as integer factorisation?
If not, why not?
symmetric provable-security
asked May 16 at 15:33
ChrisChris
63227
$endgroup$
add a comment |
$begingroup$
Are there any symmetric cryptosystems which are provably secure in the sense that there exists a reduction from their security to the hardness of some underlying hard problem such as integer factorisation?
If not, why not?
symmetric provable-security
asked May 16 at 15:33
ChrisChris
63227
$endgroup$
$begingroup$
The pohlig-helman cipher ($c=m^ebmod p$ for some secret $e,p$) could be a candidate for replacing AES in a "provably secure way" (though I couldn't find a proof right now).
$endgroup$
– SEJPM♦
May 16 at 18:31
$begingroup$
AES in CTR mode is just as ‘provable’ as Pohlig–Hellman in, say, CBC mode. Both of them rely on unproven conjectures: that AES and Pohlig–Hellman are PRPs. But AES is tremendously more efficient for the same conjectured security.
$endgroup$
– Squeamish Ossifrage
May 16 at 20:28
$begingroup$
If Hash function count, there was a candidate for SHA-3 based on lattice problems (SWIFFT).
$endgroup$
– LeoDucas
May 17 at 6:04
add a comment |
$begingroup$
Are there any symmetric cryptosystems which are provably secure in the sense that there exists a reduction from their security to the hardness of some underlying hard problem such as integer factorisation?
If not, why not?
symmetric provable-security
asked May 16 at 15:33
ChrisChris
63227
$endgroup$
Are there any symmetric cryptosystems which are provably secure in the sense that there exists a reduction from their security to the hardness of some underlying hard problem such as integer factorisation?
If not, why not?
symmetric provable-security
symmetric provable-security
asked May 16 at 15:33
ChrisChris
63227
asked May 16 at 15:33
ChrisChris
63227
asked May 16 at 15:33
ChrisChris
63227
asked May 16 at 15:33
ChrisChris
63227
asked May 16 at 15:33
ChrisChris
63227
63227
$begingroup$
The pohlig-helman cipher ($c=m^ebmod p$ for some secret $e,p$) could be a candidate for replacing AES in a "provably secure way" (though I couldn't find a proof right now).
$endgroup$
– SEJPM♦
May 16 at 18:31
$begingroup$
AES in CTR mode is just as ‘provable’ as Pohlig–Hellman in, say, CBC mode. Both of them rely on unproven conjectures: that AES and Pohlig–Hellman are PRPs. But AES is tremendously more efficient for the same conjectured security.
$endgroup$
– Squeamish Ossifrage
May 16 at 20:28
$begingroup$
If Hash function count, there was a candidate for SHA-3 based on lattice problems (SWIFFT).
$endgroup$
– LeoDucas
May 17 at 6:04
add a comment |
$begingroup$
The pohlig-helman cipher ($c=m^ebmod p$ for some secret $e,p$) could be a candidate for replacing AES in a "provably secure way" (though I couldn't find a proof right now).
$endgroup$
– SEJPM♦
May 16 at 18:31
$begingroup$
AES in CTR mode is just as ‘provable’ as Pohlig–Hellman in, say, CBC mode. Both of them rely on unproven conjectures: that AES and Pohlig–Hellman are PRPs. But AES is tremendously more efficient for the same conjectured security.
$endgroup$
– Squeamish Ossifrage
May 16 at 20:28
$begingroup$
If Hash function count, there was a candidate for SHA-3 based on lattice problems (SWIFFT).
$endgroup$
– LeoDucas
May 17 at 6:04
$begingroup$
The pohlig-helman cipher ($c=m^ebmod p$ for some secret $e,p$) could be a candidate for replacing AES in a "provably secure way" (though I couldn't find a proof right now).
$endgroup$
– SEJPM♦
May 16 at 18:31
$begingroup$
The pohlig-helman cipher ($c=m^ebmod p$ for some secret $e,p$) could be a candidate for replacing AES in a "provably secure way" (though I couldn't find a proof right now).
$endgroup$
– SEJPM♦
May 16 at 18:31
$begingroup$
AES in CTR mode is just as ‘provable’ as Pohlig–Hellman in, say, CBC mode. Both of them rely on unproven conjectures: that AES and Pohlig–Hellman are PRPs. But AES is tremendously more efficient for the same conjectured security.
$endgroup$
– Squeamish Ossifrage
May 16 at 20:28
$begingroup$
AES in CTR mode is just as ‘provable’ as Pohlig–Hellman in, say, CBC mode. Both of them rely on unproven conjectures: that AES and Pohlig–Hellman are PRPs. But AES is tremendously more efficient for the same conjectured security.
$endgroup$
– Squeamish Ossifrage
May 16 at 20:28
$begingroup$
If Hash function count, there was a candidate for SHA-3 based on lattice problems (SWIFFT).
$endgroup$
– LeoDucas
May 17 at 6:04
$begingroup$
If Hash function count, there was a candidate for SHA-3 based on lattice problems (SWIFFT).
$endgroup$
– LeoDucas
May 17 at 6:04
add a comment |
2 Answers
2
active
oldest
votes
$begingroup$
Finding uniform random $x$ given $x^3 bmodpq$ for uniform random 1024-bit primes $p$ and $q$ is conjectured to be hard because smart, motivated cryptanalysts have spent decades trying to do so and have left only a track record of failure.*
Finding uniform random $k$ given $operatornameAES256_k(92187681)$ is conjectured to be hard because smart, motivated cryptanalysts have spent decades trying to do so and have left only a track record of failure.
That said, the best estimates for the cost of (1) are much cheaper than the best estimates for (2), and the computation of $x^3 bmodpq$ is much costlier than the computation of $operatornameAES256_k(92187681)$. In other words, RSA-2048 is much more expensive for less security than AES-256.
You might be tempted to say that the RSA problem is a more fundamental problem in number theory, and as such is the only one that's really a ‘hard problem’. But it is precisely because RSA is embedded in a rich mathematical theory—as is needed for separate public key and private key operations!—that it is more vulnerable to attacks. In reality, AES is a much harder problem than RSA!
There are many symmetric cryptosystems that use AES, and for which there is a theorem that breaking them can't be much easier than breaking AES, such as AES-GCM. Similarly, there are many public-key cryptosystems that use the RSA trapdoor permutation, and for which there is a theorem that breaking them can't be much easier than inverting the RSA trapdoor permutation, like RSA-PSS and RSA-KEM.
The term ‘provable security’ means nothing more than there is a theorem. These cryptosystems—AES-GCM, RSA-PSS, and RSA-KEM alike—all have ‘provable security’ because there is a theorem, not because of any mathematical theory around AES or RSA. So does a 1-bit universal hashing authenticator have provable security, even though the amount of security it provides is so small an attacker will win with the probability of a fair coin toss coming up heads.
* Incidentally, while the RSA problem can't be harder than factorization, we don't have a proof that it can't be easier. There is some weak evidence—a reduction in the generic ring model—but there's no theorem that if factoring is hard then the RSA problem is hard. Hence not even the RSA problem has ‘provable security’ relative to factoring.
answered May 16 at 16:13
Squeamish OssifrageSqueamish Ossifrage
25.7k139117
$endgroup$
$begingroup$
A different way to say it is to say that "RSA has more structure than AES and thus is weaker", but of course you need that extra structure for public key encryption...
$endgroup$
– SEJPM♦
May 16 at 18:26
add a comment |
$begingroup$
The cipher from Fully Homomorphic Encryption over the Integers is a candidate example.
It is a symmetric cipher that is provably reducible to the approximate greatest common divisor problem.
Note that it is symmetric in the sense of "the same key is used to encrypt and decrypt", as opposed to "extremely fast and useful for bulk data". The latter definition is typically assumed when the words "symmetric cipher" are used, but that is not the case here.
answered May 16 at 16:03
Ella Rose♦Ella Rose
17.2k44586
$endgroup$
$begingroup$
I wonder what security claims that scheme achieves, ie could one (probably) build CCA-secure encryption from that?
$endgroup$
– SEJPM♦
May 16 at 18:27
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%2f70597%2fare-there-any-symmetric-cryptosystems-based-on-computational-complexity-assumpti%23new-answer', 'question_page');
);
Post as a guest
Required, but never shown
2 Answers
2
active
oldest
votes
2 Answers
2
active
oldest
votes
active
oldest
votes
active
oldest
votes
$begingroup$
Finding uniform random $x$ given $x^3 bmodpq$ for uniform random 1024-bit primes $p$ and $q$ is conjectured to be hard because smart, motivated cryptanalysts have spent decades trying to do so and have left only a track record of failure.*
Finding uniform random $k$ given $operatornameAES256_k(92187681)$ is conjectured to be hard because smart, motivated cryptanalysts have spent decades trying to do so and have left only a track record of failure.
That said, the best estimates for the cost of (1) are much cheaper than the best estimates for (2), and the computation of $x^3 bmodpq$ is much costlier than the computation of $operatornameAES256_k(92187681)$. In other words, RSA-2048 is much more expensive for less security than AES-256.
You might be tempted to say that the RSA problem is a more fundamental problem in number theory, and as such is the only one that's really a ‘hard problem’. But it is precisely because RSA is embedded in a rich mathematical theory—as is needed for separate public key and private key operations!—that it is more vulnerable to attacks. In reality, AES is a much harder problem than RSA!
There are many symmetric cryptosystems that use AES, and for which there is a theorem that breaking them can't be much easier than breaking AES, such as AES-GCM. Similarly, there are many public-key cryptosystems that use the RSA trapdoor permutation, and for which there is a theorem that breaking them can't be much easier than inverting the RSA trapdoor permutation, like RSA-PSS and RSA-KEM.
The term ‘provable security’ means nothing more than there is a theorem. These cryptosystems—AES-GCM, RSA-PSS, and RSA-KEM alike—all have ‘provable security’ because there is a theorem, not because of any mathematical theory around AES or RSA. So does a 1-bit universal hashing authenticator have provable security, even though the amount of security it provides is so small an attacker will win with the probability of a fair coin toss coming up heads.
* Incidentally, while the RSA problem can't be harder than factorization, we don't have a proof that it can't be easier. There is some weak evidence—a reduction in the generic ring model—but there's no theorem that if factoring is hard then the RSA problem is hard. Hence not even the RSA problem has ‘provable security’ relative to factoring.
answered May 16 at 16:13
Squeamish OssifrageSqueamish Ossifrage
25.7k139117
$endgroup$
$begingroup$
A different way to say it is to say that "RSA has more structure than AES and thus is weaker", but of course you need that extra structure for public key encryption...
$endgroup$
– SEJPM♦
May 16 at 18:26
add a comment |
$begingroup$
Finding uniform random $x$ given $x^3 bmodpq$ for uniform random 1024-bit primes $p$ and $q$ is conjectured to be hard because smart, motivated cryptanalysts have spent decades trying to do so and have left only a track record of failure.*
Finding uniform random $k$ given $operatornameAES256_k(92187681)$ is conjectured to be hard because smart, motivated cryptanalysts have spent decades trying to do so and have left only a track record of failure.
That said, the best estimates for the cost of (1) are much cheaper than the best estimates for (2), and the computation of $x^3 bmodpq$ is much costlier than the computation of $operatornameAES256_k(92187681)$. In other words, RSA-2048 is much more expensive for less security than AES-256.
You might be tempted to say that the RSA problem is a more fundamental problem in number theory, and as such is the only one that's really a ‘hard problem’. But it is precisely because RSA is embedded in a rich mathematical theory—as is needed for separate public key and private key operations!—that it is more vulnerable to attacks. In reality, AES is a much harder problem than RSA!
There are many symmetric cryptosystems that use AES, and for which there is a theorem that breaking them can't be much easier than breaking AES, such as AES-GCM. Similarly, there are many public-key cryptosystems that use the RSA trapdoor permutation, and for which there is a theorem that breaking them can't be much easier than inverting the RSA trapdoor permutation, like RSA-PSS and RSA-KEM.
The term ‘provable security’ means nothing more than there is a theorem. These cryptosystems—AES-GCM, RSA-PSS, and RSA-KEM alike—all have ‘provable security’ because there is a theorem, not because of any mathematical theory around AES or RSA. So does a 1-bit universal hashing authenticator have provable security, even though the amount of security it provides is so small an attacker will win with the probability of a fair coin toss coming up heads.
* Incidentally, while the RSA problem can't be harder than factorization, we don't have a proof that it can't be easier. There is some weak evidence—a reduction in the generic ring model—but there's no theorem that if factoring is hard then the RSA problem is hard. Hence not even the RSA problem has ‘provable security’ relative to factoring.
answered May 16 at 16:13
Squeamish OssifrageSqueamish Ossifrage
25.7k139117
$endgroup$
$begingroup$
A different way to say it is to say that "RSA has more structure than AES and thus is weaker", but of course you need that extra structure for public key encryption...
$endgroup$
– SEJPM♦
May 16 at 18:26
add a comment |
$begingroup$
Finding uniform random $x$ given $x^3 bmodpq$ for uniform random 1024-bit primes $p$ and $q$ is conjectured to be hard because smart, motivated cryptanalysts have spent decades trying to do so and have left only a track record of failure.*
Finding uniform random $k$ given $operatornameAES256_k(92187681)$ is conjectured to be hard because smart, motivated cryptanalysts have spent decades trying to do so and have left only a track record of failure.
That said, the best estimates for the cost of (1) are much cheaper than the best estimates for (2), and the computation of $x^3 bmodpq$ is much costlier than the computation of $operatornameAES256_k(92187681)$. In other words, RSA-2048 is much more expensive for less security than AES-256.
You might be tempted to say that the RSA problem is a more fundamental problem in number theory, and as such is the only one that's really a ‘hard problem’. But it is precisely because RSA is embedded in a rich mathematical theory—as is needed for separate public key and private key operations!—that it is more vulnerable to attacks. In reality, AES is a much harder problem than RSA!
There are many symmetric cryptosystems that use AES, and for which there is a theorem that breaking them can't be much easier than breaking AES, such as AES-GCM. Similarly, there are many public-key cryptosystems that use the RSA trapdoor permutation, and for which there is a theorem that breaking them can't be much easier than inverting the RSA trapdoor permutation, like RSA-PSS and RSA-KEM.
The term ‘provable security’ means nothing more than there is a theorem. These cryptosystems—AES-GCM, RSA-PSS, and RSA-KEM alike—all have ‘provable security’ because there is a theorem, not because of any mathematical theory around AES or RSA. So does a 1-bit universal hashing authenticator have provable security, even though the amount of security it provides is so small an attacker will win with the probability of a fair coin toss coming up heads.
* Incidentally, while the RSA problem can't be harder than factorization, we don't have a proof that it can't be easier. There is some weak evidence—a reduction in the generic ring model—but there's no theorem that if factoring is hard then the RSA problem is hard. Hence not even the RSA problem has ‘provable security’ relative to factoring.
answered May 16 at 16:13
Squeamish OssifrageSqueamish Ossifrage
25.7k139117
$endgroup$
Finding uniform random $x$ given $x^3 bmodpq$ for uniform random 1024-bit primes $p$ and $q$ is conjectured to be hard because smart, motivated cryptanalysts have spent decades trying to do so and have left only a track record of failure.*
Finding uniform random $k$ given $operatornameAES256_k(92187681)$ is conjectured to be hard because smart, motivated cryptanalysts have spent decades trying to do so and have left only a track record of failure.
That said, the best estimates for the cost of (1) are much cheaper than the best estimates for (2), and the computation of $x^3 bmodpq$ is much costlier than the computation of $operatornameAES256_k(92187681)$. In other words, RSA-2048 is much more expensive for less security than AES-256.
You might be tempted to say that the RSA problem is a more fundamental problem in number theory, and as such is the only one that's really a ‘hard problem’. But it is precisely because RSA is embedded in a rich mathematical theory—as is needed for separate public key and private key operations!—that it is more vulnerable to attacks. In reality, AES is a much harder problem than RSA!
There are many symmetric cryptosystems that use AES, and for which there is a theorem that breaking them can't be much easier than breaking AES, such as AES-GCM. Similarly, there are many public-key cryptosystems that use the RSA trapdoor permutation, and for which there is a theorem that breaking them can't be much easier than inverting the RSA trapdoor permutation, like RSA-PSS and RSA-KEM.
The term ‘provable security’ means nothing more than there is a theorem. These cryptosystems—AES-GCM, RSA-PSS, and RSA-KEM alike—all have ‘provable security’ because there is a theorem, not because of any mathematical theory around AES or RSA. So does a 1-bit universal hashing authenticator have provable security, even though the amount of security it provides is so small an attacker will win with the probability of a fair coin toss coming up heads.
* Incidentally, while the RSA problem can't be harder than factorization, we don't have a proof that it can't be easier. There is some weak evidence—a reduction in the generic ring model—but there's no theorem that if factoring is hard then the RSA problem is hard. Hence not even the RSA problem has ‘provable security’ relative to factoring.
answered May 16 at 16:13
Squeamish OssifrageSqueamish Ossifrage
25.7k139117
edited May 16 at 21:20
answered May 16 at 16:13
Squeamish OssifrageSqueamish Ossifrage
25.7k139117
answered May 16 at 16:13
Squeamish OssifrageSqueamish Ossifrage
25.7k139117
answered May 16 at 16:13
Squeamish OssifrageSqueamish Ossifrage
25.7k139117
25.7k139117
$begingroup$
A different way to say it is to say that "RSA has more structure than AES and thus is weaker", but of course you need that extra structure for public key encryption...
$endgroup$
– SEJPM♦
May 16 at 18:26
add a comment |
$begingroup$
A different way to say it is to say that "RSA has more structure than AES and thus is weaker", but of course you need that extra structure for public key encryption...
$endgroup$
– SEJPM♦
May 16 at 18:26
$begingroup$
A different way to say it is to say that "RSA has more structure than AES and thus is weaker", but of course you need that extra structure for public key encryption...
$endgroup$
– SEJPM♦
May 16 at 18:26
$begingroup$
A different way to say it is to say that "RSA has more structure than AES and thus is weaker", but of course you need that extra structure for public key encryption...
$endgroup$
– SEJPM♦
May 16 at 18:26
add a comment |
$begingroup$
The cipher from Fully Homomorphic Encryption over the Integers is a candidate example.
It is a symmetric cipher that is provably reducible to the approximate greatest common divisor problem.
Note that it is symmetric in the sense of "the same key is used to encrypt and decrypt", as opposed to "extremely fast and useful for bulk data". The latter definition is typically assumed when the words "symmetric cipher" are used, but that is not the case here.
answered May 16 at 16:03
Ella Rose♦Ella Rose
17.2k44586
$endgroup$
$begingroup$
I wonder what security claims that scheme achieves, ie could one (probably) build CCA-secure encryption from that?
$endgroup$
– SEJPM♦
May 16 at 18:27
add a comment |
$begingroup$
The cipher from Fully Homomorphic Encryption over the Integers is a candidate example.
It is a symmetric cipher that is provably reducible to the approximate greatest common divisor problem.
Note that it is symmetric in the sense of "the same key is used to encrypt and decrypt", as opposed to "extremely fast and useful for bulk data". The latter definition is typically assumed when the words "symmetric cipher" are used, but that is not the case here.
answered May 16 at 16:03
Ella Rose♦Ella Rose
17.2k44586
$endgroup$
$begingroup$
I wonder what security claims that scheme achieves, ie could one (probably) build CCA-secure encryption from that?
$endgroup$
– SEJPM♦
May 16 at 18:27
add a comment |
$begingroup$
The cipher from Fully Homomorphic Encryption over the Integers is a candidate example.
It is a symmetric cipher that is provably reducible to the approximate greatest common divisor problem.
Note that it is symmetric in the sense of "the same key is used to encrypt and decrypt", as opposed to "extremely fast and useful for bulk data". The latter definition is typically assumed when the words "symmetric cipher" are used, but that is not the case here.
answered May 16 at 16:03
Ella Rose♦Ella Rose
17.2k44586
$endgroup$
The cipher from Fully Homomorphic Encryption over the Integers is a candidate example.
It is a symmetric cipher that is provably reducible to the approximate greatest common divisor problem.
Note that it is symmetric in the sense of "the same key is used to encrypt and decrypt", as opposed to "extremely fast and useful for bulk data". The latter definition is typically assumed when the words "symmetric cipher" are used, but that is not the case here.
answered May 16 at 16:03
Ella Rose♦Ella Rose
17.2k44586
answered May 16 at 16:03
Ella Rose♦Ella Rose
17.2k44586
answered May 16 at 16:03
Ella Rose♦Ella Rose
17.2k44586
answered May 16 at 16:03
Ella Rose♦Ella Rose
17.2k44586
17.2k44586
$begingroup$
I wonder what security claims that scheme achieves, ie could one (probably) build CCA-secure encryption from that?
$endgroup$
– SEJPM♦
May 16 at 18:27
add a comment |
$begingroup$
I wonder what security claims that scheme achieves, ie could one (probably) build CCA-secure encryption from that?
$endgroup$
– SEJPM♦
May 16 at 18:27
$begingroup$
I wonder what security claims that scheme achieves, ie could one (probably) build CCA-secure encryption from that?
$endgroup$
– SEJPM♦
May 16 at 18:27
$begingroup$
I wonder what security claims that scheme achieves, ie could one (probably) build CCA-secure encryption from that?
$endgroup$
– SEJPM♦
May 16 at 18:27
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%2f70597%2fare-there-any-symmetric-cryptosystems-based-on-computational-complexity-assumpti%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
$begingroup$
The pohlig-helman cipher ($c=m^ebmod p$ for some secret $e,p$) could be a candidate for replacing AES in a "provably secure way" (though I couldn't find a proof right now).
$endgroup$
– SEJPM♦
May 16 at 18:31
$begingroup$
AES in CTR mode is just as ‘provable’ as Pohlig–Hellman in, say, CBC mode. Both of them rely on unproven conjectures: that AES and Pohlig–Hellman are PRPs. But AES is tremendously more efficient for the same conjectured security.
$endgroup$
– Squeamish Ossifrage
May 16 at 20:28
$begingroup$
If Hash function count, there was a candidate for SHA-3 based on lattice problems (SWIFFT).
$endgroup$
– LeoDucas
May 17 at 6:04