单向函数

✍ dations ◷ 2024-12-22 20:41:50 #计算机科学中未解决的问题,密码学

单向函数 (One-way function)是一种具有下述特点的单射函数：对于每一个输入，函数值都容易计算（多项式时间）；但是对于一个随机的函数值，算出其对应的输入却比较困难（无法在多项式时间内使用确定性图灵机计算）。单向函数是否存在仍然是计算机科学中的一个开放性问题。事实上，如果单向函数存在，将证明复杂性类P/NP问题中，P不等于NP。:ex. 2.2, page 70与之相对，P不等于NP的假设并不能直接推出单向函数的存在。

实践中，常将“容易计算”和“不容易计算”定义为“对于合法用户容易计算，对于恶意用户不容易计算”。从这个意义上，密码散列函数可以被当作单向函数。这是因为，虽然单向函数可能根本不存在，也无人能证明一个散列函数真的是单向函数，但也无人发现可以在合理时间内破解它们的实用算法。

函数: {0, 1}* → {0, 1}* 是一个单向函数当且仅当可以用一个多项式时间的算法计算，但是对于任意一个以为输入的随机化多项式算法，任意一个多项式()，和足够大,使得

相关

肺栓塞肺栓塞（英语：Pulmonary embolism，简称 PE），系描述肺动脉遭到来自其他地方的物质，经过血液循环而阻塞肺动脉的病况。肺栓塞的症状有呼吸困难、吸气时胸痛，以及咳血等等，也可能会出现
拉特克利夫彼得·约翰·拉特克利夫爵士（英语：Sir Peter John Ratcliffe，1954年3月14日－），英国医学家、分子生物学家。生于兰开夏，1972年赴剑桥大学和圣巴多罗买医院学习医学，1978年毕业后转赴
恋袜恋袜指对于袜子（包括短袜、中统袜、长袜、膝上袜、大腿袜、裤袜、学生袜、运动袜、丝袜、船袜及泡泡袜等）的实物，以及在印刷品或者电子媒体上出现的袜子图像有特殊迷恋的恋物行
洋姜菊芋（学名：Helianthus tuberosus），也称洋姜、鬼子姜、块根向日葵，是一种菊科向日葵属宿根性草本植物。原产北美洲，十七世纪传入欧洲，后传入中国。菊芋被联合国粮农组织官员称为“21
生态金字塔能量塔（又称能量金字塔；英文：Ecological Pyramid或Trophic pyramid）是某生态系统中各营养级所占的生物质能或拥有的生物质能生产力的图形表示，用来表达各级之间生物能量的传递关
732年晋国曲沃之乱开始，前745年晋昭侯把曲沃（在今中国山西省曲沃县）封给其叔成师。前739年晋大臣潘父弑杀了晋昭侯，迎立曲沃桓叔。晋人发兵攻桓叔，桓叔退回曲沃。晋人共立昭侯子公子平
北高加索动乱俄罗斯伊斯兰国北高加索起义是俄罗斯与高加索酋长国的武装分子之间的武装冲突，伊斯兰国从2015年6月开始涉入。历时10年之久的第二次车臣战争在2009年4月16日正式结束，但冲突却
伊夫·肖万伊夫·肖万（法语：Yves Chauvin，1930年10月10日－2015年1月28日），法国化学家，诺贝尔化学奖获得者。他是法国石油研究所的荣誉研究主任，法国科学院成员。由于从1970年代开始的在烯烃复
何华仁何华仁，知名台湾版画大师、儿童绘本作家，擅常用木刻版画制作跟鸟类有关的儿童绘本，著有多本知名绘本著作。【彩鹬奶爸】
格查战士格查战士（西班牙语：güecha）是前哥伦布时期穆伊斯卡邦联于Tenza谷、乌瓦克谷与昆迪博亚卡高原的战士。格查战士以态度与体格来选拔，并非是靠阶级。有着独特的社会地位并著有金子