兩個人如何在不告知對方自己的位置的情況下知道他們之間的距離？

01-25

Alice 和 Bob 通過某基於地理位置的網路交友軟體認識了對方。他們想知道雙方間的距離到底是多少。他們可以通過 GPS 拿到自己的精確坐標，可是卻不願意對方知道自己的位置。假設雙方都不會做假，問有沒有一種方式能夠讓 Alice 和 Bob 得知對方與自己間的距離但是又不對雙方所在的位置有更多的了解？
更新：
不要可信的第三方參與。能利用的只有可靠的信道和雙方自己的位置信息。

有個普適的解決這種問題的框架叫做Yao"s Garbled Circuit. 只要你能把你要計算的函數轉換成一堆boolean circuit, 把每個boolean circuit都按照Yao"s Garbled Circuit的計算方法計算，就可以在雙方都不知道對方input的情況下得到這個函數的結果。

如果用Garbled Circuit來計算一個AND gate, 首先我們需要Bob構建一個garbled circuit. Bob會把這個Gate的兩個input wire和output wire的可能值(0,1)都替換成相應的random string, 然後由此產生出一個新的加密的真值表。接著Bob會把自己加密的input和circuit發給Alice, 但是Alice也需要將自己的input加密才能計算這個circuit. Alice加密自己數據的過程是通過Oblivious transfer來完成的。這樣能保證Alice知道她的input對應的加密值是多少，但是又不知道其他值對應的加密值是多少，同時Bob也不知道Alice是選取了哪個加密值。這個時候Alice就能計算這個加密的circuit了，計算後能得到一個加密的結果，只有在Bob公布了真值表後，雙方才能知道真實的結果。

如果把所有的要計算的函數都轉換成boolean circuit（這個很容易通過circuit design來實現），然後用Yao"s protocol來執行所有的circuit，我們就能在雙方input不公開的情況下也能計算出來要計算的函數的值。

還有另外一種方法就是Homomorphic Encryption. 這種方法的思路就是直接計算加密的input然後再解密。使用這種方法能保證得到的解密值就是不加密直接計算的值。

這類問題叫做「安全多方計算」，Secure Multi-Party Computation，就是解決一組互不信任的參與方之間保護隱私的協同計算問題，既要確保輸入的獨立性，計算的正確性，同時不泄露各輸入值給參與計算的其他成員。

具體到這個問題，它是安全計算幾何裡面的安全距離計算。它的大致思路是A和B經過計算之後分別公布u和v，使得|u-v|為距離。這方面可以找到一些論文。

如果要求不要第三方參與的話，下面給出了一種計算方法，只考慮二維坐標A的坐標P=（x1,x2),B的坐標Q=(y1,y2)，可以向高維擴展。分4個步驟：

步驟1：

A生成隨機數序列{ra0,ra1,ra2}.

然後計算x1"=ra0*x1+ra1;x2"=ra0*x2+2*ra2;

這樣就得到P1=[x1",x2"}.

A生成隨機數u，m，k，計算p=-1/2*ra0*(u+x1^2+x2^2).

再構造一個數組P2=（m-ra1/k,m-ra2/k).

A把P1，P2，p發送給B。

步驟2：

B生成隨機數rb，然後計算：

Q1=（rb*y1,rb*y2),Q2=(rb*y1,2*rb*y2).

再計算

s1=p*rb+P1·Q1

s2=P2·Q2

s3=rb*y1+2*rb*y2

然後把s1,s2,s3發送給A

步驟3：

A計算：

t=-(s1+k*s2-m*k*s3)/ra0

將t發送B

步驟4：

B計算：

v=2*t/rb+y1^2+y2^2

至此計算完畢，可以證明v=u+d^2.(d為距離)。上面的方法來自於A NEW PRIVACY-PRESERVING EUCLID-DISTANCE PROTOCOL AND ITS APPLICATIONS IN WSNS，Journal of Electronics(China)，2013.02.還有基於同態加密的方法、基於離散對數的方法等等。

利用接收器本身不能判斷方位的問題不就行了？比如聲波。。。A發出聲波，B接收到後必須立刻作答，A收到B回答的聲波後也必須作答，拿音速一乘就行了。。。

參見電影颶風營救2，需要兩部手機，一副地圖，一隻筆，幾個炸彈，通過炸彈爆炸後的聲波傳播範圍縮小區域，再試，進一步縮小，直到大致定位。

上面的說的，已經大致給出答案了。不過，不需要進一步縮小，因為所需要求就是知道距離而非精確位置。

概括一下，

1、前提是：所需要的設備能夠無條件的滿足，無視對外界造成的影響。

製造「聲、光、煙霧」等，以圓形輻射狀展開，且在對方接受到時，不會消耗殆盡的信號。（同時應當忽略風速，溫度等影響，即應將空間視為對信號的傳播速度各向同性，否則，就必須考慮不同方向的速度，就必須確定方向，這樣，確定了方向和距離，就確定了對方的位置，這樣就不滿足題意。）根據傳播速度，就可以知道對方距離，而不知道對方位置。

2、AB均告知同一第三方位置，由第三方計算並發布雙方距離，而保留位置信息。

AliceBob……【扶額

確定這不是把作業發上來了！？

兩人分別為A、B，坐標為Ax、Ay；Bx、By

1、A告訴B自己的橫坐標Ax；

2、B計算出Ax和Bx之間的差Cx；

3、B告訴A自己的縱坐標By；

4、A計算出Ay和By之間的差Cy；

5、雙方互換Cx和Cy；

6、Cx的平方+Cy的平方等於距離K的平方

雙方距離得到，且不知道對方的具體位置

看了一下，這個用道具是可以實現的，而且應該還是有比較多的辦法實現的：

想了個操作起來還算簡單的辦法：

需要的材料還是比較簡單的。步驟如下：

1、Alice 取1張A4紙，列印一張世界地圖。記下地圖的比例尺，列印完了裁剪成圓形的。如下，沿著黑圈裁下來。

2、Alice裁一張與黑圈一模一樣大小的白紙黏在地圖後面。

3、Alice弄點兒燒鹼溶液或者其他透明的鹼液滴在地圖上自己所處的位置，確保鹼液能夠滲透到底下白紙上。

4、Alice將地圖連同後面的白紙一起晾乾到看不出鹼液的痕迹來，然後將它們一起交給Bob

5、Bob拿到東西之後，也滴一滴鹼液到地圖上自己所處的位置。晾乾。

6、Bob把地圖揭下來扔掉，只留一張圓圓的空白的白紙底板。

7、兩人一起把空白的白紙底板上塗上稀稀的酚酞溶液。就得到了下面這個：

圓圓的白紙上有倆紅點。

好了，現在按照之前記下的地圖比例尺，計算倆人的距離吧！

Distance measuring equipment

找一個值得信任的第三人，兩個人把各自的地址發給此人，讓此人計算出結果，再告訴他們兩個。