blocks|key|807285|text|type|unstyled|depth|inlineStyleRanges|entityRanges|data|entityMap^0^^$0|@$1|2|3|-4|4|5|6|B|7|@]|8|@]|9|$]]]|A|$]]

‘Provable security’ just means there is a theorem. It is a <a href="http://cacr.uwaterloo.ca/~ajmeneze/anotherlook/ps.shtml" rel="nofollow noreferrer" title="Neal Koblitz and Alfred Menezes, ‘Another look at provable security’, Journal of Cryptology 20(1), 2007, pp. 3–37.">misleading term of art</a> that should be carefully restricted to the literature if used at all, because it gives people false confidence: a system can have ‘provable security’ in the sense that there is a theorem, and could be completely breakable. There are <a href="https://crypto.stackexchange.com/a/68606" title="Squeamish Ossifrage, Answer to ‘What is the difference between information-theoretic and perfect types of security?’, crypto.stackexchange.com, 2019-04-08.">different kinds of theorems</a>, but let's focus on whether there is a theorem or not and walk through some examples of provable vs. conjectured security.

<ol>
<li>Why do we think it is difficult to find $x$ given $y = x^3 \bmod{pq}$ when $p$ and $q$ are independent uniform random 1024-bit primes and $x$ is a uniform random nonnegative integer below $pq$?

<ul>
<li>Some of the smartest cryptanalysts on the planet have been banging their heads against this problem for nearly half a century, and have only a consistent track record of failure to show for it. Maybe tomorrow someone will find a way to do it: we haven't ruled it out. For example, if they found a way to factor $pq$, they could easily compute $y^d \bmod{pq}$ where $d$ solves $$3d \equiv 1 \pmod{\operatorname{lcm}(p - 1, q - 1)}.$$ Indeed, with unlimited budget or a quantum computer they could do this easily.</li>
<li>This is the RSA problem, with computational conjectured security. Of course, this system is not directly useful for applications, because most applications don't naturally deal in random 1024-bit primes or uniform random ‘messages’ modulo a product of 1024-bit primes. It is primarily a building block for practical cryptosystems.</li>
</ul></li>
<li>Why do we think it is difficult to find $m$ given $m + p$ for $m, p \in \operatorname{GF}(2^t)$, when the distribution on $p$ has statistical distance $\varepsilon$ from uniform and $m$ has any distribution?

<ul>
<li>There is a theorem that the distinguishing advantage of any decision algorithm, that is the probability beyond 1/2 of guessing uniform random $b$ given $m_b + p$ for any choice of $m_0, m_1$, is bounded by $\varepsilon$. No breakthroughs in cryptanalysis can change the result—any failure of security is guaranteed to be a consequence of pad reuse or poor pad generation.</li>
<li>This is a formulation of the one-time pad theorem, with information-theoretic provable security. Of course, this system is not directly useful for applications, because you need a method to choose $p$ from a space as large as your space of possible messages, and do it independently for every message. It is primarily a building block for practical cryptosystems.</li>
</ul></li>
<li>Why do we think it is difficult to find $m$ given $(x^3 \bmod{pq}, m + H(x))$ where $x$ is a uniform random secret, $p$ and $q$ are uniform random secret 1024-bit primes, and $H$ is a uniform random public function?

<ul>
<li>There is a theorem, using the one-time pad theorem in (2) as a lemma, that if there is a decision algorithm with distinguishing advantage $\varepsilon$ against this system, then there is an algorithm that recovers $x$ from $x^3 \bmod{pq}$ with high probability; in other words, if the RSA problem of (1) is hard, then decrypting $(x^3 \bmod{pq}, m + H(x))$ to recover $m$ is hard. As in (1), breakthroughs in cryptanalysis could lead to factoring $pq$ to break this; similarly, since we're using the <a href="https://crypto.stackexchange.com/a/68298" title="Squeamish Ossifrage, Answer to ‘What is the “Random Oracle Model” and why is it controversial?’, crypto.stackexchange.com, 2019-03-26.">random oracle model</a> breakthroughs in cryptanalysis of the specific hash function we choose for $H$ could break this.</li>
<li>This is a weaker version of RSA-KEM/DEM, with computational provable security. The if/then structure of this theorem, using the one-time pad lemma to prove it, enables cryptanalysts to focus their effort on the RSA problem, rather than dividing effort between the $(x^3 \bmod{pq}, m + H(x))$ problem, the RSASSA-PSS problem, the RSA-KEM problem, etc. Of course, this system is not actually secure in a practical sense; you want a real DEM, which $m + H(x)$ is not—if you used this system, you would set yourself up for <a href="https://crypto.stackexchange.com/a/59241" title="Squeamish Ossifrage, Answer to ‘Is the software that uses PGP broken, or is it PGP itself?’, crypto.stackexchange.com, 2018-05-14.">EFAILure</a>. And if anyone solved the RSA problem, this would still have computational provable security; the theorem would just be vacuous!</li>
</ul></li>
<li>Why do we think it is difficult, given a message $m \in x\cdot\mathbb F_q[x] \setminus \{0\}$ and its authenticator $a = m(r) + s$ for uniform random $r, s \in \mathbb F_q$ and $q$ a prime power, to find another message/authenticator pair $(m', a')$ also satisfying $a' = m'(r) + s$? (Here we are interpreting a message as a polynomial over the field $\mathbb F_q$ with zero constant term, e.g. by breaking it into $({\leq}\log_2 q)$-bit chunks and injecting them into $\mathbb F_q$ as coefficients.)

<ul>
<li>There is a theorem that $$\Pr[a' = m'(r) + s \mid a = m(r) + s] \leq \ell/q,$$ where $\ell$ is the maximum length of a message. In other words, the one-time forgery probability is bounded by $\ell/q$. As with the one-time pad theorem in (1), no breakthroughs in cryptanalysis will change this theorem.</li>
<li>This is a universal hashing one-time authenticator, with information-theoretic provable security. Of course, this works only for a single message, so this is mainly useful as a building block for practical cryptosystems like crypto_secretbox_xsalsa20poly1305 or AES-GCM. And, of course, the security depends on the choice of parameters: the theorem is still true when $q = 2$, but a forgery probability bound of 1/2 is not very secure!</li>
</ul></li>
</ol>

blocks|key|807116|text|然后介绍了安全博弈(如CPA、CCA)？我认为这是可证明安全的一部分。|type|blockquote|depth|inlineStyleRanges|entityRanges|data|807117|是。|unstyled|807118|我不认为计算安全性和可证明安全性是两类独立的安全性。我知道计算安全强调攻击者的力量是有界的(多项式时间算法).|807119|807120|证明强调数学假设或密码学原语。但它也与计算能力有关。|807121|可证明安全性是指任何可以正式证明的安全性，即使没有数学上的严格假设(例如，信息论安全性不一定涉及这些假设)。因此，计算安全性只是可证明安全性的<#>部分。|entityMap^0|0|0|0|0|0^^$0|@$1|2|3|4|5|6|7|M|8|@]|9|@]|A|$]]|$1|B|3|C|5|D|7|N|8|@]|9|@]|A|$]]|$1|E|3|F|5|6|7|O|8|@]|9|@]|A|$]]|$1|G|3|C|5|D|7|P|8|@]|9|@]|A|$]]|$1|H|3|I|5|6|7|Q|8|@]|9|@]|A|$]]|$1|J|3|K|5|D|7|R|8|@]|9|@]|A|$]]]|L|$]]

<blockquote>
 And then it introduces the secure game (e.g. CPA, CCA)? I think it is a part of provable security.
</blockquote>

Yes.

<blockquote>
 I do not think computational security and provable security are two independent classes of security. I know that computational security emphasizes the power of attacker is bounded (polynomial-time algorithm). 
</blockquote>

Yes.

<blockquote>
 And the provable emphasizes the mathematical assumptions or cryptography primitives. But it also related to the computational power.
</blockquote>

Provable security refers to any security that can be formally proved, even if there are no mathematical hardness assumptions (e.g., information-theoretic security does not necessarily involve those assumptions). So, computational security is only part of provable security.

I read the book "Introduction modern cryptography". It gives the notion of computational security of private-key encryption at first which comes from perfect security and statistical security.

<blockquote>
 Let $(E,D)$ be an encryption scheme that uses $n$-bits keys to encrypt $l(n)$-length messages. $(E,D)$ is computationally secure if 
 $$E_{U_{n}}(x_{0}) \approx E_{U_{n}}(x_1)$$
</blockquote>

And then it introduces the secure game (e.g. CPA, CCA)? I think it is a part of provable security.

"Unconditional security" (or "information-theoretic security" or "perfectly secrecy") and "computational security" are two opposite classes of security.
But I do not think "computational security" and "provable security" are two independent classes of security. I know that computational security emphasizes the power of attacker is bounded (polynomial-time algorithm). And the provable emphasizes the mathematical assumptions or cryptography primitives. But it also related to the computational power.

What is the relation between computational security and provable security?

翻译质量差，导致语言生硬或混乱。

没有提供实际的解决方法或示例。

解答不清晰，无法理解或解决问题。

页面排版不美观，阅读体验差。

文章

问答

视频

教程

学习中心

腾讯云实验室

直播

竞赛

腾讯云代码分析专区

腾讯iOA零信任安全管理系统专区

腾讯云架构师技术同盟交流圈

腾讯云数据库专区

腾讯云智能顾问专区

腾讯云原生专区

腾讯混元专区

腾讯云TCE专区

腾讯云Lighthouse专区

腾讯云HAI专区

腾讯云Edgeone专区

腾讯云存储专区

腾讯云智能专区

腾讯轻联专区 

腾讯云开发专区

TAPD专区

腾讯轻量云游戏服专区

腾讯云最具价值专家

腾讯云架构师技术同盟

腾讯云创作之星

腾讯云开发者先锋

腾讯云AI代码助手

云原生构建

TAPD 敏捷项目管理

Cloud Studio

SDK中心

API中心

命令行工具

功能1上新10个字符

功能2描述100个字符功能2描述100个字符功能2描述100个字符功能2描述100个字符功能2描述100个字符功能2描述100个字符功能2描述100个字符功能2描述100个字符功能2描述100个字符。

功能2上新100个字符功能2上新100个字符功能2上新100个字符功能2上新100个字符功能2上新100个字符功能2上新100个字符功能2上新100个字符功能2上新100个字符功能2上新100个字符。

功能5描述100个字符功能5描述100个字符功能5描述100个字符功能5描述100个字符功能5描述100个字符功能5描述100个字符

功能5上新100个字符功能5上新100个字符功能5上新100个字符功能5上新100个字符功能5上新100个字符功能5上新100个字符功能5上新100个字符功能5上新100个字符功能5上新100个字符功能5上新100个字符

功能4上新

文章&问答评论现已支持表情

全新交互，全新视觉，新增快捷键、悬浮工具栏、高亮块等功能并同时优化现有功能，全面提升创作效率和体验

社区富文本编辑器全新改版！诚邀体验～ 

精选全网热门MCP server，让你的AI更好用 🚀

💥开发者 MCP广场重磅上线！

涵盖代码开发、场景应用、自动测试全流程，助你从零构建专属AI助手

一站式MCP教程库，解锁AI应用新玩法

聚焦“写作效率、视觉美观与运行性能”三方面进行全面升级，为您提供更高效、稳定的创作环境

社区富文本&Markdown编辑器全新改版上线，欢迎大家体验!

诚挚邀请您参与本次调研，分享您的真实使用感受与建议。您的反馈至关重要，感谢您的支持与参与！

社区新版编辑器体验调研

我读了一本书“现代密码学概论”。首先给出了私钥加密的计算安全的概念，它来源于完善的安全和统计安全。让(E,D)成为一种使用n-bits密钥加密l(n)-length消息的加密方案。如果(E,D)是E_{U_{n}}(x_{0}) \approx E_{U_{n}}(x_1)，则D5在计算上是安全的然后介绍了安全博弈(如CPA、CCA)？我认为这是可证明安全的一部分。“无条件安全”(或“信息论安全”

问计算安全和可证明安全之间的关系是什么？
EN

回答 2

Cryptography用户

Cryptography用户

社区

活动

圈层

关于

腾讯云开发者

热门产品

热门推荐

更多推荐

问计算安全和可证明安全之间的关系是什么？EN

回答 2

Cryptography用户

Cryptography用户

社区

活动

圈层

关于

腾讯云开发者

热门产品

热门推荐

更多推荐

问计算安全和可证明安全之间的关系是什么？
EN