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?
Sort a section of a file
Using `printf` to print variable containing `%` percent sign results in "bash: printf: `p': invalid format character"
Can ThermodynamicData be used with NSolve?
Why do academics prefer Mac/Linux?
Who is frowning in the sentence "Daisy looked at Tom frowning"?
Can I modify the report menu?
Can an airline pilot be prosecuted for killing an unruly passenger who could not be physically restrained?
How was the blinking terminal cursor invented?
Are spiritual pleasures > carnal pleasures, according to Catholicism?
Why didn't Daenerys' advisers suggest assassinating Cersei?
Why aren't satellites disintegrated even though they orbit earth within earth's Roche Limits?
Why are there five extra turns in tournament Magic?
Appropriate liquid/solvent for life in my underground environment on Venus
Is it a good idea to teach algorithm courses using pseudocode?
Is there any deeper thematic meaning to the white horse that Arya finds in The Bells (S08E05)?
Cryptic crossword (printer's devilry edition)
Working hours and productivity expectations for game artists and programmers
How many Dothraki are left as of Game of Thrones S8E5?
What should I wear to go and sign an employment contract?
Failing students when it might cause them economic ruin
I just found out that my recent promotion comes with an unexpected 24/7/365 on-call status
Taylor series leads to two different functions - why?
Can a generation ship withstand its own oxygen and daily wear for many thousands of years?
How to laser-level close to a surface
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 5 hours ago
ChrisChris
61727
$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 5 hours ago
ChrisChris
61727
$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♦
2 hours ago
$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
12 mins ago
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 5 hours ago
ChrisChris
61727
$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 5 hours ago
ChrisChris
61727
asked 5 hours ago
ChrisChris
61727
asked 5 hours ago
ChrisChris
61727
asked 5 hours ago
ChrisChris
61727
asked 5 hours ago
ChrisChris
61727
61727
$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♦
2 hours ago
$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
12 mins ago
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♦
2 hours ago
$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
12 mins ago
$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♦
2 hours ago
$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♦
2 hours ago
$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
12 mins ago
$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
12 mins ago
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!
answered 4 hours ago
Squeamish OssifrageSqueamish Ossifrage
24.9k136111
$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♦
2 hours ago
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 4 hours ago
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♦
2 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%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!
answered 4 hours ago
Squeamish OssifrageSqueamish Ossifrage
24.9k136111
$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♦
2 hours ago
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!
answered 4 hours ago
Squeamish OssifrageSqueamish Ossifrage
24.9k136111
$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♦
2 hours ago
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!
answered 4 hours ago
Squeamish OssifrageSqueamish Ossifrage
24.9k136111
$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!
answered 4 hours ago
Squeamish OssifrageSqueamish Ossifrage
24.9k136111
edited 6 mins ago
answered 4 hours ago
Squeamish OssifrageSqueamish Ossifrage
24.9k136111
answered 4 hours ago
Squeamish OssifrageSqueamish Ossifrage
24.9k136111
answered 4 hours ago
Squeamish OssifrageSqueamish Ossifrage
24.9k136111
24.9k136111
$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♦
2 hours ago
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♦
2 hours ago
$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♦
2 hours ago
$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♦
2 hours ago
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 4 hours ago
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♦
2 hours ago
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 4 hours ago
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♦
2 hours ago
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 4 hours ago
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 4 hours ago
Ella Rose♦Ella Rose
17.2k44586
answered 4 hours ago
Ella Rose♦Ella Rose
17.2k44586
answered 4 hours ago
Ella Rose♦Ella Rose
17.2k44586
answered 4 hours ago
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♦
2 hours ago
add a comment |
$begingroup$
I wonder what security claims that scheme achieves, ie could one (probably) build CCA-secure encryption from that?
$endgroup$
– SEJPM♦
2 hours ago
$begingroup$
I wonder what security claims that scheme achieves, ie could one (probably) build CCA-secure encryption from that?
$endgroup$
– SEJPM♦
2 hours ago
$begingroup$
I wonder what security claims that scheme achieves, ie could one (probably) build CCA-secure encryption from that?
$endgroup$
– SEJPM♦
2 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%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♦
2 hours ago
$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
12 mins ago