Socialist Millionaire Problem

栏目: IT技术 · 发布时间: 4年前

内容简介:Incryptography, theIt is often used as aAlice and Bob have secret values

Incryptography, the socialist millionaire problem is one in which two millionaires want to determine if their wealth is equal without disclosing any information about their riches to each other. It is a variant of the Millionaire's Problem whereby two millionaires wish to compare their riches to determine who has the most wealth without disclosing any information about their riches to each other.

It is often used as a cryptographic protocol that allows two parties to verify the identity of the remote party through the use of a shared secret, avoiding a man-in-the-middle attack without the inconvenience of manually comparing public key fingerprints through an outside channel. In effect, a relatively weak password/passphrase in natural language can be used.

Contents

Motivation [ edit ]

Alice and Bob have secret values and , respectively. Alice and Bob wish to learn if without allowing either party to learn anything else about the other's secret value.

A passive attacker simply spying on the messages Alice and Bob exchange learns nothing about and , not even whether .

Even if one of the parties is dishonest and deviates from the protocol, that person cannot learn anything more than if .

An active attacker capable of arbitrarily interfering with Alice and Bob's communication (aman-in-the-middle) cannot learn more than a passive attacker and cannot affect the outcome of the protocol other than to make it fail.

Therefore, the protocol can be used to authenticate whether two parties have the same secret information. Popular instant message cryptography package Off-the-Record Messaging uses the Socialist Millionaire protocol for authentication, in which the secrets and contain information about both parties' long-term authentication public keys as well as information entered by the users themselves.

Off-the-Record Messaging protocol [ edit ]

Main article: Off-the-Record Messaging

Socialist Millionaire Problem

State machine of a socialist millionaire protocol (SMP) implementation.

A prime, , and any non-identity element, , of are agreed on before the protocol, and in practice are generally fixed in a given implementation. For example, in the Off-the-Record Messaging protocol, is a specific fixed 1,536-bit prime. is then a generator of , and all operations are performed modulo , or in other words, in themultiplicative group, .

By , denote the secure multiparty computation , Diffie–Hellman–Merkle key exchange , which, for the integers, , returns to each party:

  • Alice calculates and sends it to Bob, who then calculates .
  • Bob calculates and sends it to Alice, who then calculates .

as multiplication in is associative. Note that this procedure is insecure againstman-in-the-middle attacks.

The Socialist millionaire protocolonly has a few steps that are not part of the above procedure, and the security of each relies on the difficulty of thediscrete logarithm problem, just as the above does. All sent values also include zero-knowledge proofs that they were generated according to protocol.

Part of the security also relies on random secrets. However, as written below, the protocol is vulnerable to poisoning if Alice or Bob chooses any of , , , or to be zero. To solve this problem, each party must check during theDiffie-Hellman exchanges that none of the or that they receive is equal to 1. It is also necessary to check that and .

Alice Multiparty Bob
1 Message
Random
Public Message
Random
2 Secure
3 Secure
4 Test , Test ,
5
6 Insecure exchange
7 Secure
8 Test , Test ,
9 Test Test

Note that:

and therefore

.

Because of the random values stored in secret by the other party, neither party can force and to be equal unless equals , in which case . This proves correctness.

See also [ edit ]

References [ edit ]


以上就是本文的全部内容,希望对大家的学习有所帮助,也希望大家多多支持 码农网

查看所有标签

猜你喜欢:

本站部分资源来源于网络,本站转载出于传递更多信息之目的,版权归原作者或者来源机构所有,如转载稿涉及版权问题,请联系我们

Hackers

Hackers

Steven Levy / O'Reilly Media / 2010-5-30 / USD 21.99

This 25th anniversary edition of Steven Levy's classic book traces the exploits of the computer revolution's original hackers -- those brilliant and eccentric nerds from the late 1950s through the ear......一起来看看 《Hackers》 这本书的介绍吧!

CSS 压缩/解压工具
CSS 压缩/解压工具

在线压缩/解压 CSS 代码

SHA 加密
SHA 加密

SHA 加密工具

html转js在线工具
html转js在线工具

html转js在线工具