公钥密码学中的新Rabin型陷门置换与因子分解

理论计算机科学电子笔记157（2006）79-94www.elsevier.com/locate/entcs一个新的Rabin型陷门置换与因子分解卡佳·施密特-萨摩亚德国达姆施塔特工业大学计算机科学系摘要公钥密码学是为了解决开放网络中的一些密钥管理问题而发明的。尽管公钥密码学的几乎所有方面都依赖于陷门单向函数的存在，但迄今为止只有极少数候选者被观察到。 本文基于因子分解的困难性，引入了一种新的陷门单向置换2p q型整数 我们指出，拉宾的活板门之间有一些相似之处突变和我们的提议 虽然我们的函数效率较低，但它具有一个很好的功能，这是模块化平方所不知道的，即有一个具有不同且易于处理的域的变体。 因此，它为实际应用提供了一些优势。 为了证实这一说法，我们开发了一个简单的混合加密方案，基于我们提出的陷门排列，在随机预言模型中是CCA安全的。保留字：陷门单向置换，混合加密，Tag-KEM/DEM框架1介绍非正式地说，单向置换是一个双射函数，它“容易”计算，但“难以”求逆。如果有一些信息标记使得反演也是一项容易的任务，那么我们称函数为trapdoor。陷门单向置换被用作各种密码体制的构造块，例如：G. 非对称加密、数字签名和私人信息检索。毫无疑问，陷阱门单向排列的概念特别重要，尤其是在公共场合1电子邮件：samoa@informatik.tu-darmstadt.de1571-0661 © 2006 Elsevier B. V.在CC BY-NC-ND许可下开放访问。doi：10.1016/j.entcs.2005.09.03980K. Schmidt-Samoa/Electronic Notes in Theoretical Computer Science 157（2006）79n密钥加密然而，在文献中只能找到相对较少的这里的Promising意味着单向性可以简化为一个假定的困难问题，例如整数分解问题。由于今天甚至无法证明单向函数的纯粹存在性2，这种可证明的安全陷门置换是目前最好的替代方案。1.1以前的工作最古老且最著名的候选陷门置换是RSA函数i。e. 模幂运算的指数与乘法剩余群的阶数互质[21]。模的因子可以作为翻转RSA函数的陷门，但相反的方向是未知的。因此RSA不是可证明等价于因子分解，并且存在严重的怀疑，这种等价性确实存在[3]。无论如何，由于RSA问题已经被广泛研究了几十年，现在RSA函数的反演被广泛认为是一个困难的问题。稍后，M。O.拉宾观察到模平方的特殊情况可以简化为因子分解[20]。然而，模平方不是一个置换，它是4比1（如果使用双因子 这是可以克服的：对Blum整数3n取模平方是二次剩余模n的置换。由此产生的活板门每-突变在文献中被称为Blum-Williams函数，而扩张（指数为2e，其中e与λ（n）互质）被称为Rabin-Williams函数。 Kurosawa等人[11]、Paillier[17，18]和Galindo等人提出了更多基于因子分解的陷门排列。 [9]的文件。在[19]中可以找到关于陷阱门排列的调查，包括一些不太确定的候选者1.2我们的贡献本文引入了一个相当简单的陷门单向置换，它等价于n =p2q整数的因式分解与许多先前的候选者一样，我们提出的陷门函数也是基于模展式的，即在我 们 的 情 况 下 ， 公 共 指 数 与 模 n=p2q 相 同 。 当 整 环 Z× 时 ， 函 数x<$→xnmodn是p对e，但仅限于模n的n个剩余子群，它确实是一个置换.这个性质类似于Blum-Williams函数（其中第n个残基被二次残基取代）。类似于二次剩余[2]有趣的是，目前复杂性理论中的知识甚至不允许证明假设P /=NP的单向函数的存在性。3Blum整数是两个不同素数的乘积，每个素数都与3模4全等K. Schmidt-Samoa/Electronic Notes in Theoretical Computer Science 157（2006）7981PQPQnnn假设，我们假设在不知道n的因式分解的情况下，很难区分n次剩余与非剩余，而如果n的因子已知，则是有效然而，限制域具有一些同样适用于Blum-Williams和Rabin-Williams函数的短时间限制：在实际应用中，数据必须被预处理成第n个函数的集合，resp.二次剩余但幸运的是，我们可以证明，对于n=p2q，第n个剩余集同构于Z×，因此我们提出的陷门函数也是易于处理的域Z×第n个的集合残基 Rabin型函数没有这样的性质。 我确可以表明，我们提出的陷门置换很容易提供实际应用，通过构建一个混合加密方案的基础上安倍等。’s Tag-KEM/DEM framework2与因子分解等价的陷门单向置换在本节中，我们介绍一个新的陷门单向置换。为了加深对p2q型群Z×（n为n）特殊性质的理解，本文还对其数学背景作了简要的说明2.1符号和定义设n为正整数。 记Zn为模n剩余类环，记Z×为其乘法群i. e. 模n的可逆元素的集合。 对x ∈ Z×，ordn（x）表示x模n的乘法阶，i. e. 最小的正整数k，xk= 1modn。此外，n：N→N表示欧拉对于任何同态h，我们分别用ker（h）和im（h）表示核和像。通常，概率Pr（k）被称为可忽略的，如果Pr（k）比k中任何多项式的倒数下降得更快，i。e. kc（k > kc<$Pr（k）p}nd{gmmodn|我 <不想让你这么做。88K. Schmidt-Samoa/Electronic Notes in Theoretical Computer Science 157（2006）793.2用于混合加密的Tag-KEM/DEM框架除了将特定的通用构造应用于合适的非对称和对称原语的技术之外，Cramer和Shoup在[4]中引入了一种更通用的混合加密解决方案在本文中，Cramer和Shoup形式化了所谓的KEM/DEM框架，其中KEM是一种概率非对称密钥封装机制，DEM是一种对称加密方案（一种数据封装机制），用于使用KEM给出的密钥对任意长度的消息进行加密。不用说，这种公开密钥和秘密密钥的组合方案多年来一直是民间传说，但Cramer和Shoup第一次对这个主题进行了严格请注意，KEM与密钥协商协议不同：封装的密钥被指定为仅使用一次，因此DEM只需要在一次性场景中是安全的有关安全定义和要求的更多详细信息，请参阅[4]。粗略地说，如果KEM和DEM部分都是CCA安全的，那么整个KEM/DEM方案也是在今年的欧洲密码会议上，Abe等人。通过引入标记KEM的概念增强了Cramer和Shoup的框架，标记KEM是配备有特殊信息片段（标记）的KEM[ 1 ]。在他们新颖的混合加密框架中，这个标签作为CCA安全标签-KEM的一部分被分配来保护DEM部分的不可延展性因此，对于具有CCA安全的Tag-KEM的整个Tag-KEM/DEM混合方案的CCA安全性，仅需要DEM部分对被动对手是安全的与KEM/DEM框架相比，这是一个明显的改进，但硬币的另一面是，Tag-KEM的安全性证明比“普通”KEM的模拟证明更复杂接下来，我们基于我们提出的陷门置换构造了一个新的Tag-KEM，并在随机预言机模型下证明了它的CCA安全性然后，我们将展示如何导致CCA安全的混合加密方案中的Tag-KEM/DEM框架。最后，我们比较了这种新的方案与EPOC-2/3。3.3建议的Tag-KEM在[1]中，Tag-KEM的概念被正式定义。在这里-TKEM.Gen（1k）：设k为安全参数。选择两个不同的k位素数p，q，其中p<$q−1，q<$p− 1，使得p−1，q− 1中的每一个都有一个大的K. Schmidt-Samoa/Electronic Notes in Theoretical Computer Science 157（2006）79891主要因素6.构建乘积n=p2q，计算d=n−1 modn（pq）并定义rLen= 2k−2。 选择一个密钥导出函数KDF，它将位串映射到指定DEM的密钥空间中，并选择一个散列函数H，输出长度为hashLen的位串。返回一对公钥和私钥（pk，sk），其中pk =（n，rLen，KDF，H），sk =（d，p，q）。TKEM.Key（pk）：选择ω∈ {0，1，.，2 rLen− 1}随机一致地，计算dk= KDF（ω）并返回（ω，dk）。TKEM.Enc（ω，τ）：给定密钥载体ω和标签τ，计算c1=ωnmodn，c2 =H（ω，τ），返回ω n =（c1，c2）.TKEM.Decsk（τ，τ）：给定封装的密钥τ和标签τ，将τ解析为c1，c2和computer=cdmodpq。 If|R|2>rLen或H（r，τ）=1c2，返回k，返回KDF（r），否则。第一步，生成密钥对。然后，通过将密钥导出函数应用于随机比特串来构造用于DEM部分的一次性密钥dk。在安全性证明中，KDF和H都被建模为随机预言机[2]。在步骤TKEM.Enc中，一次性密钥（其在某种意义上嵌入在ω中）与标签τ一起被加密。最后，使用TKEM.Decsk，可以从封装密钥恢复一次性密钥dk和标签τ。备注3.1在解封过程中，需要检查r是否确实符合长度要求（|R|2≤ rLen = 2 k− 2），因为否则可以进行简单的选择密文攻击，通过二进制搜索获得秘密因子pq[10]。Tag-KEM的CCA安全性要求具有自适应oracle的对手访问TKEM.Decsk没有机会区分给定的一次性密钥dk是否封装在挑战（k，τ）中，即使标签τ是由对手自己选择的。像往常一样，这是通过适当的游戏来定义的值得注意的是，尽管对手被限制为不对挑战（τ，τ）查询解封装预言，但是允许针对τi=τ i的查询（τ，τ i）因此，安全的Tag-KEM提供标签的不可延展性详情见[1]。由于空间限制，以下定理的冗长证明在本文的完整版本中给出[23]：定理3.2如果因式分解n = p2q的整数是困难的，则上面定义的Tag-KEM在随机预言模型中是CCA安全的。6意味着p-1的位长度（分别为Q=O（logk）90K. Schmidt-Samoa/Electronic Notes in Theoretical Computer Science 157（2006）79Kdk1更正式地说：如果存在攻击者AT攻击随机预言模型中提出的Tag-KEM，- 在时间t中，- 具有优势的是，- 最多查询表示所述密钥导出函数的随机预言qK次，- 查询表示所述散列函数的所述随机预言至多qH次，- 调用解封装预言至多qD次，则存在对手A事实，其在时间tJ中分解n=p2q，并且具有优势，其中tJ≤t+tgcd（qH）+tf.PQqD，- 是的 ΣJ≥qK2qDϵ− − −11−，KlenHashLenn+HashLen p时间复杂度为O（n），时间复杂度为O（n）而tfpq是计算tfpq的时间。3.4提出的混合加密方案如前所述，为了避免冗长的递归，我们不回顾通用的Tag-KEM/DEM框架，但我们只描述当将我们提出的Tag-KEM与适当的DEM相结合时获得的具体混合加密方案有兴趣的读者可以参考[1]的一般治疗-我是说。设（Esym，Dsym）是具有密钥K的任何对称密码系统，K K一次安全（粗略地说，这意味着（Esym，Dsym）是语义的，K K当K仅被使用一次时，对被动的对手是安全的）。假设Esym的消息空间被给定为{0， 1}mLen。密钥生成：密钥生成与TKEM.Gen（.）中的相同加密和解密如下执行：Epk（m）：ω{0，1}RLendk ： =KDF （ ω ）τEsym（m）Dsk（τ，τ）：（c1，c2）：= 0r：=cd modpq如果|R|2> RLen或H（r，τ）/= c2返回H：=（ωnmodn，H（ω，τ））返回（τ，τ）symKDF（r）返回m（τ）注意，用加密的一次性密钥加密的消息m的DEM密文用作标签。因此，DEM部分的不可延展性m：=DK. Schmidt-Samoa/Electronic Notes in Theoretical Computer Science 157（2006）7991由于CCA安全的Tag-KEM提供了标签的完整性，因此直观地实现了。从[1]的结果，我们得到：定理3.3若p ~2q型整数的因式分解是困难的，且若（Esym，Dsym）K K是一次安全的，那么所提出的混合加密方案是CCA安全的在随机预言模型中。 更准确地说，我们有hy≤ 2 KEM+DEM，其中hy，KEM和DEM表示针对所提出的混合加密方案的CCA安全性的多项式时间攻击的 最 大 优势 ，针对我们新的Tag-KEM的CCA安全性，反对一次性的安全性（E sym，Dsym）。K K在上述定理中，混合加密的CCA安全性在标准意义上被定义，即。e. 自适应选择密文攻击下密文的不可破译性。请注意，对因子分解的简化是严格的。3.5比较在本节中，我们将简要比较EPOC-2/3和我们提出的混合加密方案。表1总结了有关安全性和性能的最重要加密和解密的效率是以模乘来测量的，其中MM（k）表示以k位数为模的模乘我们不区分乘法和平方，并且我们假设具有k位指数的模幂运算大约需要3k/2模乘法，而执行Okamoto-Uchiyama加密所需的双幂运算使用标准技术大约需要7k/ 4模乘法我们没有考虑指数重编码技术，但如果可能的话，中国的重编码也被考虑散列、密钥导出函数的评估和对称密钥操作不被测量，因为这些幅度在所有方案中是可比的。为了评估公钥大小，我们比较了EPOC-2/3侧的n，g，h与我们提出的方案中的n。密钥大小是相同的（即，对于EPOC-2/3，分别是3k，指p，gpp，d为我们提出的方案）。所有量都是根据安全参数k（i）来测量的。e. 素因子p，q的比特长度）。在EPOC-2/3的情况下，我们假设rLen=k，并且HashLen≥2k hold（这些值决定指数大小）。由于模乘是模长度的二次方，所以我们的方案在解密中是最有效的，而在加密中它的效率略低于EPOC-2/3。此外，在我们提出的方案中，公钥短了3倍，并且基本的安全假设是最优的（就像EPOC-2一样）。我们的方案的另一个优点是：如果一次一密用于对称部分，92K. Schmidt-Samoa/Electronic Notes in Theoretical Computer Science 157（2006）79方案假设加密解密pkEPOC-2事实≥7k/ 2MM（3k）3千/ 2毫米（2千）+ 7千/ 4毫米（千）9KEPOC-3Gap-HR≥7k/ 2MM（3k）300万/2毫米（2千）9K提出事实2.9公里/ 2毫米（3公里）300万毫米（千）3K表1重要参数则与EPOC-2/3中的k相比，我们方案中的消息长度是2k。这是因为fpq的带宽是Okamoto-Uchiyama加密带宽的两倍。此外，由于在解密中，在两个潜在的拒绝事件之间只需要计算一个散列，因此我们的方案比EPOC-2更能抵抗拒绝定时攻击[25，5]，其中执行重新加密。四、结论本文基于因子分解的困难性，由于可证明安全的陷门单向置换是如此罕见，但在公钥密码学中具有突出的重要性，因此新候选者的开发本身就是一个基本问题此外，为了证明我们提出的陷门函数不仅具有理论意义，我们构造了一个新的CCA安全混合加密方案作为示例性应用。为此，我们利用最近出版的Tag-KEM/DEM框架进行混合加密。我们能够证明，我们提出的特设结构已经与著名的EPOC家族的成员相比毫不逊色，这些成员基于与我们的提议相同的棘手性假设。确认作者希望感谢匿名推荐人提供的有用意见。引用[1] M.亚伯河Gennaro，K. Kurosawa和V. Shoup。Tag-KEM/DEM：一种新的混合加密框架和对Kurosawa-Desmedt KEM的新分析。在Ronald Cramer，编辑，EUROCITY PT，计算机科学讲义第3494卷，第128-146页。施普林格，2005年。[2] M. Bellare 和 P. Rogaway 。Random oracles are practical ：A paradigm for designing efficientprotocols. 第一届ACM计算机和通信安全会议（CCS），第62-73页。ACM Press，1993.[3] D. Boneh和R.文卡特桑打破RSA可能不等同于因式分解。在Nyberg [13]，第59K. Schmidt-Samoa/Electronic Notes in Theoretical Computer Science 157（2006）7993[4] R. Cramer和R.欢呼抗适应性选择密文攻击之实用公开金钥加密方案之设计与分析。SIAM J.Comput. ，33（1）：167[5] A. W. Dent.对EPOC-2公钥密码体制的实现攻击。Electronics Letters，38（9）：412[6] E. Fujisaki，T.小林H. Morita，H. Oguro，T.冈本，S. Okazaki，D. Pointcheval，以及S.内山EPOC：高效概率公钥加密。已提交ISO和NESSIE。[7] E. Fujisaki 和 T. 冈 本 非 对 称 和 对 称 加 密 方 案 的 安 全 集 成 。 在 Michael J. Wiener ， editor ，BUSINESS PTO，volume 1666 ofLecture Notes in Computer Science，pages 537-554中。Springer，1999年。[8] E. 藤崎EPOC-2的Chosen-Chipertext安全性技术报告，NTT Corporation，2001年。[9] D. Gali and o，S. M. Mollev'enches，P. Morillo，anddJ. L. 维拉本文给出了Paillier和Rabin方案的一个实用的数值解。在Yvo Desmedt，编辑，Public Key Cryptography，计算机科学讲义第2567卷，第279-291页Springer，2003年。[10] M. Joye，J.- J. Quisquater和M.容关于行为不端的对手的力量和原始EPOC的在Naccache [12]，第208[11] K. Kurosawa，T. Ito和M.竹内使用倒数的公钥密码系统，其复杂性与大数的因数分解相同。《人类学》，12（4）：225-233，1988年。[12] DavidNaccache，编辑。TopicsinCryptology-CT-RSA2001，TheCryptographerSpringer，2001年。[13] Kaisa Nyberg，编辑Advances in Cryptology --EUROPENTPTSpringer，1998年。[14] T. Okamoto和D.波因特什瓦尔EPOC-3 -有效概率公钥加密，2000年。已提交IEEE P1363。[15] T. Okamoto和D.波因特什瓦尔REACT：快速增强安全的非对称密码系统转换。在Naccache [12]，第159[16] T. Okamoto和S.内山一个新的公钥密码系统的安全性与因子分解。在Nyberg [13]，第308[17] P. Paillier.基于复合度剩余类的公钥密码体制。在Jacques Stern，编辑，EUROPELLECTORPT，计算机科学讲义第1592卷，第223 - 229238. Springer-Verlag，1999.[18] P. Paillier.一种等价于因式分解的陷门置换。在Hideki Imai和Yuliang Zheng，编辑，Public KeyCryptography，计算机科学讲义第1560卷，第219 - 222页。Springer-Verlag，1999.[19] J. Patarin和L. 狗宾 陷门单向置换与多元多项式。Yongfei Han，Tatsuaki Okamoto，and SihanQing，editors，ICICS，volume 1334 ofLecture Notes in Computer Science，pages 356-368.Springer，1997年。[20] M. O.拉宾数字化签名和公钥函数像因子分解一样棘手。技术报告212，麻省理工学院计算机科学实验室，剑桥，1979年。[21] R. L. Rivest ， A. Shamir 和 L. 艾 德 曼 一 种 获 得 数 字 签 名 和 公 钥 密 码 系 统 的 方 法 。Communications of the ACM，21（2）：120[22] K.施密特-萨摩亚基于因式分解的故障-停止签名的重新审视。Javier Lopez，Sihan Qing，and EijiOkamoto，editors，ICICS，volume 3269 ofLecture Notes in Computer Science，pages 118-131. Springer，2004.94K. Schmidt-Samoa/Electronic Notes in Theoretical Computer Science 157（2006）79nn[23] K.施密特-萨摩亚一个新的与因子分解等价的rabin型陷门置换及其应用。《密码学电子印刷档案》，2005年第278号报告。http://eprint.iacr.org/。2[24] K. Schmidt-Samoa和T. 高木 Paillier陷阱承诺计划。In S. Vaudenay，编辑，MYSTPPT，计算机科学讲义第3715卷。Springer-Verlag，2005.[25] K. Sakurai和T.高木对IND-CCA 2公钥密码体制的拒绝定时攻击。 Pil Joong Lee和Chae HoonLim，编辑，ICISC，计算机科学讲义第2587卷，第359-379页，柏林，2003年。史普林格出版社A一些证据下面的证明已经在[22]中发表，因此我们把它们放在附录中。引理2.3的证明设x是Z×中乘法阶为p的元素. 然后我们有xp= 1 modn（xp= 1 modpxp = 1 modq）n（x = 1 mod p n x = 1 mod q）。因此是pq|x − 1必须成立，我们得出x ∈ S。另一方面，从二项式展开公式可以明显地看出，对于所有x∈S，我们有xp= 1modn<$x/ = 1，因此断言如下。Q引理2.4的证明注意，由于p是n的唯一非平凡公因子，并且n（n）=p（p-1），1）（q-1），我们必须有xn= 1 modnx =1 ordn（x）=p因此，h的核由1和Z×中乘法阶为p的元素组成，即引理2.3中定义的S的元素。Q