首页
学习
活动
专区
圈层
工具
发布
社区首页 >问答首页 >安全性参数和$b$-bit安全性之间有什么区别?

问安全性参数和$b$-bit安全性之间有什么区别?
EN

Cryptography用户
提问于 2020-06-28 21:25:54
回答 2查看 249关注 0票数 4

在前一个问题里,我读到

..。对于b-bit安全性而言,O(2^b)对攻击者破坏系统起作用.

在Katz对现代密码学的介绍中,我读到:

密钥生成算法\text{Gen}以输入1^n (即一元写入的安全参数)输出密钥k“。

安全参数和b-bit安全性有什么区别?

编辑:我能给出一个McEliece密码系统的例子吗?

EN

回答 2

Cryptography用户

发布于 2020-06-29 12:01:11

安全参数1^n和b-bit安全性有什么区别?

不是一个,而是两个:

  1. 安全参数1^n没有精确地指定攻击者如何使用n工作。根据作者和上下文的不同,这可以是:未指定的;比n中的任何多项式都快(在非对称加密中常见);在n (在理论对称加密中常见)中是指数的;或者粗略地称为2^n (在应用对称加密中常见)。相反,"b-bit security“指定攻击的工作量大致增长为2^b,就像在对称密码学中,用于恢复理想密码的b-bit密钥的攻击一样。这种区别在RSA中是最重要的,在那里,n通常是模数的位大小,而n=2048被认为产生b\approx112。
  2. 当我们考虑算法最多以多项式的形式运行到其输入的大小时,就像理论工作中的惯例一样:将1^n (指一个由n位组成的位串)作为输入传递意味着运行时间在n中是多项式,当传递n将允许运行时间在\log(n)中是一个多项式。通常,前者在密码学中是可取的。,而"b-bit security“却没有提到运行时。

对粗略的某种定义而言。包括我在内的许多人经常说,预期的攻击者工作是O(2^b)。这是不恰当的,因为上限表示工作。我们至少应该写\Omega(2^b)或\Theta(2^b);参见这。我将回答中的(次要和常见)问题更正为“前面提到的问题”。

票数 4
EN

Cryptography用户

发布于 2020-06-29 00:15:54

它们都与一个比特长度的复杂性有关,但在那里,相似性结束了。

b-位安全性使用猜测2^b的蛮力数,在最坏的情况下确定b-位键(因为有尽可能多的密钥)是最坏的情况。

另一种关于安全参数的表示法是一个符号结构,它确保某个输入具有“正确的大小”,在安全性证明的渐近分析中使用。

维基百科:

在密码学中,安全参数是度量计算问题的输入大小的变量。密码算法或协议的资源需求以及对手破坏安全的概率都用安全参数来表示。安全参数通常表示为一元表示(例如,n的安全参数表示为n 1的字符串)。

注意:这是你的1^n

使得密码算法的时间复杂度在输入的大小上是多项式的。

票数 3
EN
页面原文内容由Cryptography提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接:

https://crypto.stackexchange.com/questions/81593

复制
相关文章

相似问题

领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档