Hence, S reveals nothing about the

Hence, S reveals nothing about the inputs and outputs of the gate.

Second, if P 2 (Q[Q0), then the inductive invariant is that the collection of all shares held by dishonest parties in Q and Q0 does not give the adversary any information about the inputs and the outputs. As the base case, it is clear that the invariant is valid for input gates. The induction step is as follows. The adversary can obtain at most 2(N=6) = N=3 shares of any shared value during the computation step; N=6 from dishonest parties in Q and N=6 from dishonest parties in Q0. By the secrecy of the VSS scheme, at least N=3+1 shares are required for reconstructing the secret. By the secrecy of RenewShares and Multiply, when at most N=3 of the shares are revealed, the secrecy of the computation step is proved using universal computability of multi-party protocols.

Query Processing. The correctness and secrecy follows from the proof of the Reconst algorithm and the standard assumption that the location-based server correctly executes the queries and sends the results back to the parties.

Lemma 3. The protocol LocationSharing sends ~O (n) bits, computes ~O(n) operations, and has O(log2 n) rounds of communication.

We rst compute the cost of each step of the protocol separately and then compute the total cost. Based on [22], the communication and computation complexity of the VSS subprotocol is O(poly(n)) when it is invoked among n parties. Also, the VSS protocol takes constant rounds of communication.
 Setup. The communication and computation costs are equal to those costs of the quorum building algorithm of Theorem 3, which is ~O (1) for each party. This protocol takes constant rounds of communication.
 Input Broadcast. The input broadcast step invokes the VSS protocol n times among N = O(log n) parties. So, this step sends O(n
poly(N)) bits and performs O(n
poly(N)) operations. Since the VSS scheme is constant-round, this step also takes constant rounds.
 Random Generation. It is easy to see that the subprotocol GenRand sends O(N
poly(N)) messages, performs O(N
poly(N)), and has constant rounds.
 Circuit Computation. The Batcher's sorting network [4] has O(n log2 n) gates. So, the communication cost of this step is equal to the communication and computation cost of running O(n log2 n) instantiations of Compare and RenewShares. Compare requires O(log q) invocation of Multiply which sends O(poly(N)) messages and computes O(poly(N)) operations. Renew- Shares also sends O(poly(N)) messages and computes O(poly(N)) operations. Hence, the circuit computation phase sends O(n log n
log q
poly(N)) messages computes O(n log n
log q
poly(N)) . Since the sorting network has depth O(log2 n), and Compare takes constant rounds, this steps takes O(log2 n) rounds of communication.
 Query Processing. The costs are equal to the communication and computation costs of running n instantiations of Reconst. Thus, this step sends ~O(n) messages and performs ~O (n) operations. Since Reconst is a constant-round protocol and the communications with the server take constant rounds, this step of the protocol also takes constant rounds.
 Total. Since q > 3 2kn2 log n, for a constant k, q = O(n3) and log q = O(log n). Thus, Protocol 1 sends ~O (n) bits and computes ~O(n) operations. Finally, the protocol requires O(log2 n) rounds of communication. This completes the proof of Theorem 1.

ผลลัพธ์ (ไทย) 1:

ด้วยเหตุนี้ S เปิดเผยอะไรเกี่ยวกับอินพุตและเอาต์พุตของประตูถ้าสอง P 2 (Q[Q0) แล้วเหนี่ยวนำไม่เป็นที่เก็บของทั้งหมดที่ถือ โดยบุคคลที่ไม่สุจริตใน Q และ Q0 ไม่ให้ปฏิปักษ์ข้อมูลใด ๆ เกี่ยวกับการอินพุตและการ เป็นกรณีพื้นฐาน เป็นที่ชัดเจนว่า การไม่ถูกต้องสำหรับเข้าประตู ขั้นตอนการเหนี่ยวนำจะเป็นดังนี้ ปฏิปักษ์ได้มากที่สุด 2(N=6) = N = 3 หุ้นมีมูลค่าใช้ร่วมกันระหว่างขั้นตอนการคำนวณ N = 6 จากกิจการทุจริตใน Q และ N = 6 จากกิจการทุจริตใน Q0 โดยความลับของแบบ VSS น้อย N = 3 + 1 หุ้นจำเป็นสำหรับฟื้นฟูความลับ โดยความลับ ของ RenewShares และคูณ เมื่อมากที่สุด N = 3 ของหุ้นที่ถูกเปิดเผย ความลับของขั้นตอนการคำนวณเป็นเครื่องพิสูจน์โดยใช้การคำนวณได้สากลเป็นหลายฝ่ายการประมวลผลแบบสอบถาม ดังนี้ความถูกต้องและเป็นความลับจากหลักฐานของอัลกอริทึม Reconst และมาตรฐานสันนิษฐานว่า เซิร์ฟเวอร์ตามตำแหน่งที่ตั้งอย่างถูกต้องดำเนินการสอบถาม และส่งผลลัพธ์กลับไปยังฝ่ายหน่วยการที่ 3 โพรโทคอลส่ง LocationSharing ~ O (n) bits คำนวณการดำเนินการ ~O(n) และมีรอบ O (log2 n) ของการสื่อสารเรา rst คำนวณต้นทุนของแต่ละขั้นตอนของโพรโทคอแยกต่างหาก และคำนวณต้นทุนรวม จาก [22], ความซับซ้อนการติดต่อสื่อสารและการคำนวณของ VSS subprotocol เป็น O(poly(n)) เมื่อมันถูกเรียกในหมู่กิจการ n ยัง โพรโทคอล VSS จะรอบคงที่ของการสื่อสารการตั้งค่า การสื่อสารและการคำนวณต้นทุนจะเท่ากับต้นทุนดังกล่าวของสร้างอัลกอริทึมของทฤษฎีบท 3 ซึ่งเป็นองค์ประชุม ~ O (1) สำหรับแต่ละฝ่าย โพรโทคอลนี้ใช้รอบคงที่ของการสื่อสารการออกอากาศที่ป้อนเข้า ขั้นออกอากาศสัญญาณเรียกใช้โพรโทคอล VSS n ครั้งระหว่าง N = O (n ล็อก) กิจการ ดังนั้น การขั้นตอนนี้ส่ง O (n poly(N)) bits และทำ O (n poly(N)) การปฏิบัติการ ตั้งแต่แบบ VSS รอบคง ขั้นตอนนี้ยังใช้รอบคงการสร้างแบบสุ่ม มันเป็นเรื่องง่ายเพื่อดูว่า subprotocol GenRand ส่ง O (N poly(N)) ข้อความ ทำ O (N poly(N)) และมีรอบคงวงจรคำนวณการ เครือข่ายการเรียงลำดับของ Batcher [4] มี O (n log2 n) ประตู ดังนั้น ต้นทุนการสื่อสารของขั้นตอนนี้จะเท่ากับการสื่อสารและการคำนวณต้นทุนของการทำงาน O (n log2 n) instantiations ของเปรียบเทียบและ RenewShares เปรียบเทียบต้องเรียก O (ล็อก q) คูณซึ่งส่งข้อความ O(poly(N)) และคำนวณการดำเนินงาน O(poly(N)) หุ้นต่ออายุยังส่งข้อความ O(poly(N)) และคำนวณการดำเนินงาน O(poly(N)) ด้วยเหตุนี้ ขั้นตอนการคำนวณวงจรส่ง O (n ล็อกล็อก n q poly(N)) ข้อความคำนวณ O (n ล็อกล็อก n q poly(N)) เนื่องจากเครือข่ายการเรียงลำดับมีความลึก O (log2 n), และเปรียบเทียบเวลารอบคง นี้ขั้นตอนใช้เวลา O (log2 n) รอบการสื่อสารการประมวลผลแบบสอบถาม ต้นทุนจะเท่ากับการสื่อสารและการคำนวณต้นทุนใช้ n instantiations ของ Reconst ดังนั้น ขั้นตอนนี้ส่งข้อความ ~O(n) และทำ ~ O (n) การดำเนินงาน ตั้งแต่ Reconst เป็นโพรโทคอรอบคงและการสื่อสารกับเซิร์ฟเวอร์ด้วยรอบคง ขั้นตอนนี้ของโพรโทคอยังรอบเวลาคงผลรวม ตั้งแต่ q > 3 2kn2 ล็อก n สำหรับ k คง q = q O(n3) และล็อก = O (n บันทึก) ดังนั้น 1 โพรโทคอลการส่ง ~ O (n) bits และคำนวณการดำเนินงาน ~O(n) ในที่สุด โพรโทคอลต้องรอบ O (log2 n) ของการสื่อสาร ทฤษฎีบท 1 หลักฐานสมบูรณ์

ผลลัพธ์ (ไทย) 2:

ดังนั้น S เผยให้เห็นอะไรเกี่ยวกับปัจจัยการผลิตและผลของประตู.

ประการที่สองถ้า P 2 (Q [Q0) แล้วคงอุปนัยคือคอลเลกชันของหุ้นทั้งหมดที่ถือโดยบุคคลที่ไม่สุจริตใน Q และ Q0 ไม่ให้ฝ่ายตรงข้ามใด ๆ ข้อมูลเกี่ยวกับปัจจัยการผลิตและผลผลิต ในฐานะที่เป็นกรณีฐานเป็นที่ชัดเจนว่าคงเป็นที่ถูกต้องสำหรับการป้อนข้อมูลประตู ขั้นตอนการเหนี่ยวนำเป็นดังนี้ ศัตรูจะได้รับมากที่สุด 2 (N = 6) = N = 3 หุ้นมูลค่าที่ใช้ร่วมกันใด ๆ ในระหว่างขั้นตอนการคำนวณ; N = 6 จากบุคคลที่ไม่น่าไว้วางใจใน Q และ N = 6 จากบุคคลที่ไม่น่าไว้วางใจใน Q0 โดยความลับของโครงการ VSS อย่างน้อย N = 3 + 1 หุ้นที่จำเป็นสำหรับการฟื้นฟูความลับ โดยความลับของ RenewShares และคูณเมื่อที่มากที่สุด N = 3 ของจำนวนหุ้นที่จะถูกเปิดเผยความลับของขั้นตอนการคำนวณที่มีการพิสูจน์โดยใช้การคำนวณสากลของโปรโตคอลหลายฝ่าย.

ประมวลผลแบบสอบถาม ความถูกต้องและเป็นความลับต่อไปนี้จากหลักฐานของขั้นตอนวิธี Reconst และสมมติฐานมาตรฐานที่เซิร์ฟเวอร์ตามสถานที่ต่างๆได้อย่างถูกต้องดำเนินการสอบถามและส่งผลกลับไปยังฝ่าย.

แทรก 3. โปรโตคอล LocationSharing ส่ง ~ O (n) บิตคำนวณ ~ O (n) การดำเนินงานและมี O (log2 n) รอบของการสื่อสาร.

เรา RST คำนวณค่าใช้จ่ายในขั้นตอนของโปรโตคอลแต่ละแยกแล้วคำนวณค่าใช้จ่ายทั้งหมด ขึ้นอยู่กับ [22] การสื่อสารและการคำนวณความซับซ้อนของ subprotocol VSS เป็น O (Poly (N)) เมื่อมันถูกเรียกในหมู่บุคคลที่ n นอกจากนี้โปรโตคอล VSS รอบจะใช้เวลาอย่างต่อเนื่องของการสื่อสาร.
? ติดตั้ง. ค่าใช้จ่ายในการติดต่อสื่อสารและการคำนวณจะเท่ากับค่าใช้จ่ายที่ของขั้นตอนวิธีการสร้างองค์ประชุมของทฤษฎีบทที่ 3 ซึ่งเป็น ~ O (1) สำหรับแต่ละบุคคล โปรโตคอลนี้จะใช้เวลารอบอย่างต่อเนื่องของการสื่อสาร.
? ออกอากาศการป้อนข้อมูล การป้อนข้อมูลที่ออกอากาศเรียกขั้นตอนโปรโตคอล VSS ครั้ง N หมู่ N = O (log n) กิจการ ดังนั้นขั้นตอนนี้จะส่ง O (n? โพลี (N)) บิตและดำเนินการ O (n? โพลี (N)) การดำเนินงาน ตั้งแต่โครงการ VSS เป็นค่าคงที่ตลอดทั้งขั้นตอนนี้ยังใช้เวลารอบอย่างต่อเนื่อง.
? การสร้างแบบสุ่ม มันเป็นเรื่องง่ายที่จะเห็นว่า subprotocol GenRand ส่ง O (n? โพลี N) () ข้อความดำเนิน O (n? โพลี (N)) และมีรอบอย่างต่อเนื่อง.
? การคำนวณวงจร เครือข่ายการเรียงลำดับของ Batcher [4] มี O (n log2 n) ประตู ดังนั้นค่าใช้จ่ายในการสื่อสารของขั้นตอนนี้จะมีค่าเท่ากับการสื่อสารและการคำนวณค่าใช้จ่ายของการใช้ O (n log2 n) instantiations ของเปรียบเทียบและ RenewShares เปรียบเทียบต้อง O (log Q) อุทธรณ์ของคูณซึ่งจะส่ง O (โพลี N) () ข้อความและคำนวณ O (Poly (N)) การดำเนินงาน หุ้น Renew- ยังส่ง O (โพลี N) () ข้อความและคำนวณ O (Poly (N)) การดำเนินงาน ดังนั้นขั้นตอนการคำนวณวงจรส่ง O (n log n? เข้าสู่ระบบ Q? โพลี (N)) ข้อความคำนวณ O (n log n? เข้าสู่ระบบ Q? โพลี (N)) เนื่องจากเครือข่ายการเรียงลำดับมีความลึก O (log2 n), และเปรียบเทียบเตะรอบคงที่ขั้นตอนนี้จะใช้เวลา O (log2 n) รอบของการสื่อสาร.
? ประมวลผลแบบสอบถาม ค่าใช้จ่ายจะเท่ากับการสื่อสารและการคำนวณค่าใช้จ่ายของการทำงานของ instantiations n Reconst ดังนั้นขั้นตอนนี้จะส่ง ~ O (n) ข้อความและดำเนิน ~ O (n) การดำเนินงาน ตั้งแต่ Reconst เป็นโปรโตคอลคงรอบและการสื่อสารกับเซิร์ฟเวอร์ใช้รอบคงที่ขั้นตอนของโปรโตคอลนี้ยังใช้เวลารอบอย่างต่อเนื่อง.
? ทั้งหมด. ตั้งแต่ Q> 3 2kn2 log n สำหรับ K คง q = O (N3) และเข้าสู่ระบบ q = O (log n) ดังนั้นพิธีสาร 1 ส่ง ~ O (n) บิตและคำนวณ ~ O (n) การดำเนินงาน สุดท้ายต้องใช้โปรโตคอล O (log2 n) รอบของการสื่อสาร เสร็จสมบูรณ์พิสูจน์ทฤษฎีบทที่ 1

ผลลัพธ์ (ไทย) 3:

ดังนั้น ด้วยเปิดเผยอะไรเกี่ยวกับอินพุตและเอาต์พุตของเกตอย่างที่สอง ถ้า P ( q [ q0 ) แล้วไม่เปลี่ยนแปลงอุปนัยคือคอลเลกชันของหุ้นที่ถือโดยบุคคลที่ทุจริตใน Q และ q0 ไม่ให้คู่ต่อสู้ใด ๆ ข้อมูลเกี่ยวกับปัจจัยการผลิตและผลผลิต เป็นฐานกรณี มันชัดเจนว่า ความถูกต้องเพื่อประตูใส่ อุปนัยขั้นตอนมีดังนี้ ซาตานสามารถได้รับมากที่สุด 2 ( n = 6 ) = n = 3 หุ้นคุณค่าร่วมกันใด ๆในระหว่างการคำนวณขั้นตอน ; n = 6 พรรคการเมืองทุจริตใน Q และ N = 6 พรรคการเมืองทุจริตใน q0 . โดยความลับของโครงการมหาวิทยาลัยอย่างน้อย n = 3 + 1 หุ้นที่จําเป็นสําหรับการสร้างความลับ โดยความลับของ renewshares และทวีมากขึ้น เมื่อ n = 3 ที่สุดของหุ้นจะเปิดเผย ความลับของการคำนวณขั้นตอนพิสูจน์การใช้คอมพิวเตอร์ของสากลหลายโปรโตคอลการประมวลผลแบบสอบถาม ความถูกต้องและความลับ ดังนี้ จากหลักฐานของ reconst ขั้นตอนวิธีและมาตรฐานสมมติฐานที่ใช้เซิร์ฟเวอร์ได้อย่างถูกต้องรันแบบสอบถามและส่งผลไปงานปาร์ตี้พ 3 . โปรโตคอล locationsharing ส่ง ~ O ( n ) บิต . ~ o ( n ) การดำเนินงานและมี O ( LOG ) รอบของการสื่อสารเราน่ะ คำนวณต้นทุนของแต่ละขั้นตอนของระเบียบแยกแล้วคำนวณค่าใช้จ่ายทั้งหมด ตาม [ 22 ] , การสื่อสารและการคำนวณที่ซับซ้อน subprotocol VSS เป็น O ( poly ( n ) เมื่อมีการเรียกใช้ระหว่างที่อยู่ฝ่าย นอกจากนี้ VSS โปรโตคอลใช้รอบคงที่ของการติดต่อสื่อสารการติดตั้ง ค่าใช้จ่ายในการสื่อสารและการคำนวณจะเท่ากับที่ค่าใช้จ่ายขององค์ประชุมอัลกอริทึมอาคารของทฤษฎีบท 3 ซึ่งเป็น ~ O ( 1 ) ของแต่ละพรรค โปรโตคอลนี้ใช้รอบคงที่ของการติดต่อสื่อสารสัญญาณออกอากาศ สัญญาณออกอากาศขั้นตอนจะเรียก VSS พิธีสาร n ครั้งระหว่าง N = O ( log n ) พรรค ดังนั้น ขั้นตอนนี้ส่ง O ( n โพลี ( n ) บิตและมีประสิทธิภาพ O ( n โพลี ( n ) การดำเนินงาน เนื่องจากโครงการ VSS เป็นรอบคงที่ ขั้นตอนนี้ยังใช้รอบคงที่สุ่มสร้าง มันเป็นเรื่องง่ายเพื่อดูว่า subprotocol genrand ส่ง O ( n โพลี ( n ) ) ข้อความแสดง O ( n โพลี ( n ) ) และมีรอบคงที่วงจรการคำนวณได้ ของเจ้าตัวพลาดอย่างเรียง 4 [ เครือข่าย ] ได้ O ( LOG ) ประตู ดังนั้นการสื่อสารค่าใช้จ่ายของขั้นตอนนี้คือเท่ากับการสื่อสารและค่าใช้จ่ายในการคำนวณใช้ O ( N LN N ) instantiations ของเปรียบเทียบและ renewshares . เปรียบเทียบต้อง O ( log P ) เรียก คูณ ซึ่งส่ง ( poly ( n ) O . O ) ข้อความ ( poly ( n ) การดำเนินงาน ฟื้น - หุ้นยังส่ง O ( poly ( n ) ข้อความ . O ( poly ( n ) การดำเนินงาน ดังนั้น วงจรการคำนวณระยะส่ง O ( n log n ) Q โพลี ( n ) O ( n log n . ข้อความเข้าสู่ระบบ Q โพลี ( N ) ตั้งแต่แยกเครือข่ายมีความลึก O ( LOG ) และเปรียบเทียบใช้รอบคงที่ ขั้นตอนนี้จะใช้เวลา O ( LOG ) รอบของการสื่อสารการประมวลผลแบบสอบถาม ค่าใช้จ่ายจะเท่ากับต้นทุนการสื่อสารและการคำนวณการใช้ N instantiations ของ reconst . ดังนั้นขั้นตอนนี้ส่ง ~ O ( n ) ข้อความและแสดง ~ O ( n ) การดำเนินงาน ตั้งแต่ reconst เป็นโปรโตคอลรอบคงที่ และสื่อสารกับเซิร์ฟเวอร์ที่ใช้รอบคงที่ ขั้นตอนนี้ของพิธีสารยังใช้รอบคงที่ทั้งหมด ตั้งแต่ Q > ล็อก 3 2kn2 N สำหรับค่าคงที่ K , Q = o ( N3 ) และ log Q = O ( log n ) และพิธีสาร 1 ส่ง ~ O ( n ) บิตและคำนวณ ~ O ( n ) การดำเนินงาน ในที่สุด ซึ่งต้องใช้ O ( LOG ) รอบของการสื่อสาร นี้เสร็จสมบูรณ์ในการพิสูจน์ทฤษฎีบท 1