ในขณะที่อ่านบทช่วยสอนเกี่ยวกับการคำนวณสองฝ่าย ฉันพบคำจำกัดความความปลอดภัยที่แตกต่างกันสองคำ (อย่างน้อยอย่างเป็นทางการ) (กับฝ่ายตรงข้ามที่กึ่งซื่อสัตย์) สิ่งที่ฉันต้องการทราบคือคำจำกัดความเหล่านี้แตกต่างกันจริง ๆ หรือสามารถแสดงให้เทียบเท่าได้หรือไม่ ฉันสงสัยว่ามันต่างกัน แต่ฉันอาจขาดอะไรไป เพราะฉันไม่เคยอ่านเกี่ยวกับคำจำกัดความที่ต่างกันเลย
ใน ลินเดลล์ (2559), การคำนวณสองฝ่ายที่ปลอดภัยถูกกำหนดดังนี้: สำหรับแต่ละฝ่าย การกระจายร่วมกันของการจำลองและผลลัพธ์ในอุดมคติจะต้องแยกไม่ออกจากการคำนวณร่วมกันของมุมมองฝ่ายตรงข้ามและผลลัพธ์ที่คำนวณได้ เป็นทางการสำหรับแต่ละคน $i \ใน \{1, 2\}$, ต้องมี p.p.t. อัลกอริทึม $S_i$ ดังนั้น $$ {\lbrace (S_i(1^n, x, f_1(x, y)), f(x, y)) \rbrace}_{x, y, n} \stackrel{c}{\equiv} {\lbrace (\operatorname{view}^\pi_i(x, y, n), \operatorname{output}^\pi_i(x, y, n)) \rbrace}_{x, y, n} \,\ข้อความ{.} $$ คำจำกัดความนี้สมเหตุสมผลสำหรับฉันเนื่องจากผู้เขียนให้คำจำกัดความ ความแตกต่างทางการคำนวณ มากกว่าความน่าจะเป็นทั้งมวลที่จัดทำดัชนีโดยทั้งพารามิเตอร์ความปลอดภัย และอินพุต:
สองชุดน่าจะเป็น $X = \{X(a, n)\}_{a \in {\{0, 1\}}^*; n \in \mathbb{N}}$ และ $Y = \{Y(a, n)\}_{a \in {\{0, 1\}}^*; n \in \mathbb{N}}$ กล่าวกันว่าแยกไม่ออกด้วยการคำนวณซึ่งแสดงโดย $X \stackrel{c}{\equiv} Y$ถ้าสำหรับทุกอัลกอริทึมเวลาพหุนามที่ไม่สม่ำเสมอ $D$ มีฟังก์ชันเล็กน้อยอยู่ $\mu(\cdot)$ เช่นนั้นสำหรับทุกๆ $a \ใน \{0, 1\}^*$ และทุกๆ $n \in \mathbb{N}$, $$ \lvert \Pr[D(X(a, n)) = 1] - \Pr[D(Y(a, n)) = 1] \rvert \leq \mu(n) \,\ข้อความ{.} $$
ซึ่งหมายความว่าจะต้องมีฟังก์ชันเล็กน้อยเพียงฟังก์ชันเดียว $\mu$ สำหรับอินพุตทั้งหมดที่ควบคุมความปลอดภัย
ในทางตรงกันข้าม, อีแวนส์และคณะ (2561) กำหนดความสามารถในการแยกแยะทางคอมพิวเตอร์สำหรับกลุ่มความน่าจะเป็นที่จัดทำดัชนีโดยพารามิเตอร์ความปลอดภัยเท่านั้น ฉันยังเห็นคำจำกัดความของการแยกแยะไม่ได้ของการคำนวณเช่นนี้ที่อื่น จากนั้น เมื่อกำหนดความปลอดภัย พวกเขาต้องการให้การแจกแจงร่วมนั้นแยกไม่ออกจากคอมพิวเตอร์ สำหรับอินพุตทั้งหมด. อย่างน้อยอย่างเป็นทางการสิ่งนี้บอกฉันว่าที่นี่ ฟังก์ชันเล็กน้อยอาจขึ้นอยู่กับอินพุต
คำตอบสำหรับคำถามต่อไปนี้จะได้รับการชื่นชมอย่างมาก:
การกำหนดความแตกต่างนั้นยุ่งยากมากฉันคิดว่าคำจำกัดความในหนังสือของ Evans และคณะ อ่อนแอเกินไป แต่บางที Mike Rosulek จะชั่งน้ำหนัก หากคุณกำหนดความปลอดภัยโดยบอกว่าสำหรับทุกอินพุต การกระจายของ REAL/IDEAL นั้นแยกไม่ออก ดังนั้นสิ่งที่คุณกำลังพูดจะเป็นดังนี้: สำหรับทุกอินพุตและทุกตัวแยกความแตกต่างมีอยู่ ฟังก์ชันเล็กน้อย $\mu$ เพื่อให้ตัวแยกความแตกต่างประสบความสำเร็จด้วยความน่าจะเป็นมากที่สุด $\mu(n)$. ซึ่งหมายความว่าคุณอาจต้องการฟังก์ชันเล็กน้อยที่แตกต่างกันสำหรับแต่ละอินพุต เพื่อให้ชัดเจนยิ่งขึ้น หากเราเปิดสิ่งนี้ให้มากขึ้น คำนิยามนี้บอกว่าสำหรับทุกๆ อินพุต ทุกๆ ดิฟเฟอเรนซ์ $D$ และทุกพหุนาม $p$ มีค่า $n_0$ เช่นนั้นสำหรับทุกๆ $n>n_0$ ผู้แยกแยะประสบความสำเร็จด้วยความน่าจะเป็นน้อยกว่า $1/p(n)$. นี่หมายความว่า $n$ สามารถขึ้นอยู่กับอินพุตและโดยเฉพาะอย่างยิ่งไม่มี $n_0$ เกินกว่านั้น $n_0$ มีความแตกต่างสำหรับอินพุตทั้งหมด ระบุไว้แตกต่างกัน คุณอาจต้องใช้พารามิเตอร์ความปลอดภัยที่แตกต่างกันสำหรับอินพุตที่แตกต่างกัน นั่นไม่ใช่สิ่งที่คุณต้องการจะทำ (และมันเป็นไปไม่ได้เลยด้วยซ้ำ เนื่องจากคุณเห็นด้วยกับพารามิเตอร์ความปลอดภัยโดยไม่ทราบอินพุต และคุณจะกำหนดได้อย่างไรว่าพารามิเตอร์ความปลอดภัยนั้นควรเป็นอย่างไร) ในทางตรงกันข้าม ในคำจำกัดความที่อินพุตเป็นส่วนหนึ่งของชุด มีหนึ่งชุด $n_0$ สำหรับอินพุตทั้งหมด คำถามว่าเรากำหนดสิ่งนั้นได้อย่างไร $n_0$ เป็นเรื่องง่ายในทางปฏิบัติ - เป็นสิ่งที่เราต้องการสำหรับสิ่งดั้งเดิมทั้งหมดที่เราใช้เพื่อความปลอดภัย ไม่จำเป็นต้องพูด Evans และคณะ ไม่ได้ทำอะไรที่แตกต่างในการก่อสร้างของพวกเขา อย่างไรก็ตาม คำจำกัดความมีข้อบกพร่อง ตามความเข้าใจที่ดีที่สุดของฉัน
[หมายเหตุด้านข้าง มีกระดาษสั้นโดย Mihir Bellare เรียกว่า หมายเหตุเกี่ยวกับฟังก์ชันเล็กน้อย ที่ช่วยให้คุณสามารถย้อนกลับปริมาณของฝ่ายตรงข้ามและฟังก์ชันเล็กน้อย อย่างไรก็ตาม ด้วยความรู้ที่ดีที่สุดของฉัน สิ่งนี้ใช้ไม่ได้กับอินพุต]
คนส่วนใหญ่ไม่เข้าใจว่าการถามคำถามมากมายจะปลดล็อกการเรียนรู้และปรับปรุงความสัมพันธ์ระหว่างบุคคล ตัวอย่างเช่น ในการศึกษาของ Alison แม้ว่าผู้คนจะจำได้อย่างแม่นยำว่ามีคำถามกี่ข้อที่ถูกถามในการสนทนา แต่พวกเขาไม่เข้าใจความเชื่อมโยงระหว่างคำถามและความชอบ จากการศึกษาทั้ง 4 เรื่องที่ผู้เข้าร่วมมีส่วนร่วมในการสนทนาด้วยตนเองหรืออ่านบันทึกการสนทนาของผู้อื่น ผู้คนมักไม่ตระหนักว่าการถามคำถามจะมีอิทธิพลหรือมีอิทธิพลต่อระดับมิตรภาพระหว่างผู้สนทนา
