上周跟@lego 和小霖(我找不到你论坛ID啊)吹水的时候聊到一个称体重的问题:

Q:小霖在实验室里有个某米的智能电子秤,在上面称过数据会同步到小霖的手机里,某一天lyy想要称自己的体重,但是不想让小霖知道,那要怎么做?

A:

  1. 随便找几样实验室里的东西分别称重
  2. 在1称过的东西中随机挑几个拿在手里,然后站在某米电子秤上
  3. 把2中称出来的结果减去手里拿着的东西的重量就是实际体重

这个方法是基于背包加密(Knapsack Cryptosystem/Subset-Sum Cryptosystem)改的,不同的地方是把明文M也加到和S中,然后M是不公开的(废话)。M放在不同位置的话Subset-Sum的攻击方法好像就用不了了(当时吹完水后就没有深究了)

应用的话可以把称重这个过程抽象称一个在公开信道上的API,用户调用这个API但是不想泄露输入数据是可以这样搞(不过只能用在可以做加减法的就是了)

PS:😂站长加个密码学tag!

    由于单项物品重量已知,当 N 不够大且 Wi 方差不大时,枚举 2N 种情况可以推断大概的体重范围,这叫做暴力破解(逃

    Tover LYY最有可能的做法是杀人灭口而不是用背包算法:-D

    背包密码看上去是过去时,其实是将来时。后量子时代使用的密码算法很多是基于背包密码的思想。因此还有人估计,未来的图灵奖会颁发给上世纪80年代发明背包密码的Ralph C Merkle,此君还确实是一个天才。不过他已经不研究密码了,做纳米技术和冷冻人技术,不知道ACM会不会还给他颁奖。

      不了解密码学,但感觉这个例子可以从信号处理角度理解:获得的信号=原始信号+噪音

      这里加密了的体重虽然有明确方向(只增加),但必须精确获取噪音才能还原。参考取若干临近值平均值来减弱噪声的方法,但这里体重无法减轻只能增加。

        NTL01 以”获得的信号=原始信号+噪音“这个方向去理解非常好!但是,”必须精确获取噪音才能还原“在密码学而言就不完全正确。密码学中有三种基本参与角色,加密方、解密方和攻击者。加密方产生了”原始信号+噪音“,解密方因为有某些秘密优势,可以无需噪声也可以获取原始信号。只有对攻击者来说才是没有获取噪声就不能还原。

          Bintou 感谢指点!

          我要是想知道她体重,就直接把大妹子抱起来,哈哈

          2 个月 后

          © 2018-2024 0xFFFF