Anonymous Permutation Routing Theory in Cryptography Conference
Join the TCC conference in Taipei, Taiwan on December 1, 2023, to explore the theory of anonymous permutation routing in cryptography. Discover innovative solutions, threat models, and applications in this cutting-edge field. Our results include a theorem statement and an overview of techniques used. Dive into the complexities of non-interactive anonymous routers and sender-receiver permutations for secure message transmission.
Download Presentation
Please find below an Image/Link to download the presentation.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author. Download presentation by click this link. If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.
E N D
Presentation Transcript
Anonymous Permutation Routing Theory of Cryptography Conference (TCC) PAUL BUNN PAUL BUNN December 1, 2023 Taipei, Taiwan EYAL KUSHILEVITZ RAFAIL OSTROVSKY
Outline Problem Statement Threat Model Applications Existing Solutions Background Our Result Theorem Statement Intuition Overview Of Techniques
Outline Problem Statement Threat Model Applications Existing Solutions Background Our Result Theorem Statement Intuition Overview Of Techniques
Problem Statement Anonymous Permutation Routing [Shi Wu 21: Non-Interactive Anonymous Router] N Senders, N Receivers
Problem Statement Anonymous Permutation Routing [Shi Wu 21: Non-Interactive Anonymous Router] Senders Receivers N Senders, N Receivers
Problem Statement Anonymous Permutation Routing [Shi Wu 21: Non-Interactive Anonymous Router] Senders Receivers N Senders, N Receivers, permutation , messages {mi}
Problem Statement Anonymous Permutation Routing [Shi Wu 21: Non-Interactive Anonymous Router] Senders Receivers m1 N Senders, N Receivers, permutation , messages {mi} m2 m3 mN
Problem Statement Anonymous Permutation Routing [Shi Wu 21: Non-Interactive Anonymous Router] Senders Receivers m1 N Senders, N Receivers, permutation , messages {mi} Central Router C m2 m3 mN
Problem Statement Anonymous Permutation Routing [Shi Wu 21: Non-Interactive Anonymous Router] Senders Receivers m1 N Senders, N Receivers, permutation , messages {mi} Central Router C m2 C m3 mN
Problem Statement Anonymous Permutation Routing [Shi Wu 21: Non-Interactive Anonymous Router] Senders Receivers m1 N Senders, N Receivers, permutation , messages {mi} Central Router C Protect: Message contents {mi} Permutation : Unknown to all (2N + 1) parties Adversary: HBC, Static Collusion: Router C, plus: Basic : Up to (N-2) Sender-Receiver pairs Sender Collusion : All Senders, Up to (N-2) Receivers Receiver Collusion : All Receivers, Up to (N-2) Senders m2 C m3 mN
Applications Collusion: Router C, plus: Basic : Up to (N-2) Sender-Receiver pairs Sender Collusion : All Senders, Up to (N-2) Receivers Receiver Collusion : All Receivers, Up to (N-2) Senders
Applications Collusion: Router C, plus: Basic : Up to (N-2) Sender-Receiver pairs Sender Collusion : All Senders, Up to (N-2) Receivers Receiver Collusion : All Receivers, Up to (N-2) Senders Basic Collusion C + (up to) N-2 Sender-Receiver pairs Sender Collusion Receiver Collusion C + (up to) all Receivers + (up to) N-2 Senders C + (up to) all Senders + (up to) N-2 Receivers Arbitrary Collusion C + (up to) 2N 2 Senders + Receivers
Applications Collusion: Router C, plus: Basic : Up to (N-2) Sender-Receiver pairs Sender Collusion : All Senders, Up to (N-2) Receivers Receiver Collusion : All Receivers, Up to (N-2) Senders Basic Collusion: P2P Messaging Basic Collusion C + (up to) N-2 Sender-Receiver pairs Sender Collusion Receiver Collusion C + (up to) all Receivers + (up to) N-2 Senders C + (up to) all Senders + (up to) N-2 Receivers Arbitrary Collusion C + (up to) 2N 2 Senders + Receivers
Applications Collusion: Router C, plus: Basic : Up to (N-2) Sender-Receiver pairs Sender Collusion : All Senders, Up to (N-2) Receivers Receiver Collusion : All Receivers, Up to (N-2) Senders Basic Collusion: P2P Messaging Sender Collusion: Pub/Sub with Privacy Multi-Client PIR Basic Collusion C + (up to) N-2 Sender-Receiver pairs Sender Collusion Receiver Collusion C + (up to) all Receivers + (up to) N-2 Senders C + (up to) all Senders + (up to) N-2 Receivers Arbitrary Collusion C + (up to) 2N 2 Senders + Receivers
Applications Collusion: Router C, plus: Basic : Up to (N-2) Sender-Receiver pairs Sender Collusion : All Senders, Up to (N-2) Receivers Receiver Collusion : All Receivers, Up to (N-2) Senders Basic Collusion: P2P Messaging Sender Collusion: Pub/Sub with Privacy Multi-Client PIR Receiver Collusion: NIAS [Shi Wu 21] Multi-Client PIW Basic Collusion C + (up to) N-2 Sender-Receiver pairs Sender Collusion Receiver Collusion C + (up to) all Receivers + (up to) N-2 Senders C + (up to) all Senders + (up to) N-2 Receivers Arbitrary Collusion C + (up to) 2N 2 Senders + Receivers
Applications Collusion: Router C, plus: Basic : Up to (N-2) Sender-Receiver pairs Sender Collusion : All Senders, Up to (N-2) Receivers Receiver Collusion : All Receivers, Up to (N-2) Senders Basic Collusion: P2P Messaging Sender Collusion: Pub/Sub with Privacy Multi-Client PIR Receiver Collusion: NIAS [Shi Wu 21] Multi-Client PIW Non-corrupt Router C Oblivious Shuffle Basic Collusion C + (up to) N-2 Sender-Receiver pairs Sender Collusion Receiver Collusion C + (up to) all Receivers + (up to) N-2 Senders C + (up to) all Senders + (up to) N-2 Receivers Arbitrary Collusion C + (up to) 2N 2 Senders + Receivers
Our Work Applications Collusion: Router C, plus: Basic : Up to (N-2) Sender-Receiver pairs Sender Collusion : All Senders, Up to (N-2) Receivers Receiver Collusion : All Receivers, Up to (N-2) Senders Basic Collusion: P2P Messaging Sender Collusion: Pub/Sub with Privacy Multi-Client PIR Receiver Collusion: NIAS [Shi Wu 21] Multi-Client PIW Non-corrupt Router C Oblivious Shuffle Basic Collusion C + (up to) N-2 Sender-Receiver pairs Sender Collusion Receiver Collusion C + (up to) all Receivers + (up to) N-2 Senders C + (up to) all Senders + (up to) N-2 Receivers Arbitrary Collusion C + (up to) 2N 2 Senders + Receivers
Outline Problem Statement Threat Model Applications Existing Solutions Background Our Result Theorem Statement Intuition Overview Of Techniques
Existing Solutions Na ve Solution 1: Flooding (+ Encryption) O(N2) (total) Communication O(N2) Computation (at C) Non-Interactive Senders Receivers m1 m2 C m3 mN Per message bit
Existing Solutions Na ve Solution 1: Flooding (+ Encryption) O(N2) (total) Communication O(N2) Computation (at C) Non-Interactive Senders Receivers m1 m2 Na ve Solution 2: [Single-Server] PIR (+ Encryption) O(N polylog N) (total) Communication O(N2) Computation (at C) Non-Interactive (after 1-time Setup) C m3 mN Per message bit
Existing Solutions Na ve Solution 1: Flooding (+ Encryption) O(N2) (total) Communication O(N2) Computation (at C) Non-Interactive Senders Receivers m1 m2 Na ve Solution 2: [Single-Server] PIR (+ Encryption) O(N polylog N) (total) Communication O(N2) Computation (at C) Non-Interactive (after 1-time Setup) C m3 Solution 3: [Shi Wu 21] Non-Interactive Anonymous Router O(N polylog N) (total) Communication O(N2) Computation (at C) Non-Interactive (after 1-time Setup) Per message bit mN
Concurrent Work [Fernando, Shi, Soni, Vanjani, Waters 23 Next Talk]: Collusion tolerance: Per message bit
Our Work Concurrent Work [Fernando, Shi, Soni, Vanjani, Waters 23 Next Talk]: Collusion tolerance: Basic Collusion C + (up to) N-2 Sender-Receiver pairs Sender Collusion Receiver Collusion C + (up to) all Receivers + (up to) N-2 Senders C + (up to) all Senders + (up to) N-2 Receivers Arbitrary Collusion C + (up to) 2N 2 Senders + Receivers Per message bit
[FSSVW] Concurrent Work [Fernando, Shi, Soni, Vanjani, Waters 23 Next Talk]: Collusion tolerance: Basic Collusion C + (up to) N-2 Sender-Receiver pairs Sender Collusion Receiver Collusion C + (up to) all Receivers + (up to) N-2 Senders C + (up to) all Senders + (up to) N-2 Receivers Arbitrary Collusion C + (up to) 2N 2 Senders + Receivers Per message bit
[FSSVW] Concurrent Work [Fernando, Shi, Soni, Vanjani, Waters 23 Next Talk]: Collusion tolerance: Improves upon original NIAR [Shi, Wu 21]: Achieves quasi-linear overall performance Requires obfuscation: iO vs. Rate-1 OT (DDH, QR,LWE) Basic Collusion C + (up to) N-2 Sender-Receiver pairs Sender Collusion Receiver Collusion C + (up to) all Receivers + (up to) N-2 Senders C + (up to) all Senders + (up to) N-2 Receivers Arbitrary Collusion C + (up to) 2N 2 Senders + Receivers Per message bit
Problem Statement Is there a NIAR solution with overall (quasi-) linear performance? E.g. requires quasi-linear computation at C Under standard crypto assumptions? E.g. feasible in practice
Outline Problem Statement Threat Model Applications Existing Solutions Background Our Result Theorem Statement Intuition Overview Of Techniques
Background Rate-1 OT [DGI+ 1-out-of-2 string OT 19, GHO 20, CGH+ 21]: Server response size message size Known instantiating assumptions (can use any of): DDH, QR, LWE (post-quantum) [DGI+ 19]
Outline Problem Statement Threat Model Applications Existing Solutions Background Our Result Theorem Statement Intuition Overview Of Techniques
Our Result Theorem: Assuming rate-1 OT, there is a solution to the Anonymous Permutation Routing problem that achieves: O(N polylog N) (total) Communication O(N polylog N) Computation (at C) Non-Interactive (after 1-time Setup) Per message bit
Our Result: Intuition Senders Receivers Observation 1: Anonymous Permutation Routing is similar to (non-anonymous) Permutation Routing m1 m2 C m3 mN
Our Result: Intuition Senders Receivers Observation 1: Anonymous Permutation Routing is similar to (non-anonymous) Permutation Routing m1 m2 m3 mN
Our Result: Intuition Senders Receivers Observation 1: Anonymous Permutation Routing is similar to (non-anonymous) Permutation Routing m1 m2 Choose paths per permutation m3 mN
Our Result: Intuition Senders Receivers Observation 1: Anonymous Permutation Routing is similar to (non-anonymous) Permutation Routing m1 m2 Choose paths per permutation m3 mN
Our Result: Intuition Senders Receivers Observation 1: Anonymous Permutation Routing is similar to (non-anonymous) Permutation Routing m1 m2 Choose paths per permutation m3 mN
Our Result: Intuition Senders Receivers Observation 1: Anonymous Permutation Routing is similar to (non-anonymous) Permutation Routing m1 m2 Choose paths per permutation m3 mN
Our Result: Intuition Senders Receivers Observation 1: Anonymous Permutation Routing is similar to (non-anonymous) Permutation Routing m1 m2 Choose paths per permutation m3 mN
Our Result: Intuition Senders Receivers Observation 2: Because (non-anonymous) Permutation Routing networks are small (N polylog N), central router can simulate it m1 m2 m3 mN
Our Result: Intuition Senders Receivers Observation 2: Because (non-anonymous) Permutation Routing networks are small (N polylog N), central router can simulate it m1 m2 C m3 mN
Our Result: Intuition Observation 3: Use PIR to add anonymity ( Obfuscated Gate ) m1 m2 n n Wire: wi Value: qi = PIRquery(DB, j) mn m1 m2 . DB= . . . . . mj . . . mn
Our Result: Overview of Techniques 1. Combine Observations 1-3 Central Router simulates a virtual (permutation) network, where routing decisions at each gate are obfuscated by PIR (PIR queries are assigned to each edge in a 1-time Setup) 2. Need Small Networks Issue (Cost): Computation at C is proportional to network size (number of edges) Solution: Results from the literature in Permutation Routing use small networks (N polylog N) 3. Need Specialized PIR Issue (Cost): Standard PIR (server response size has non-constant stretch) won t work Solution:Use rate-1 (constant stretch) PIR (immediate from rate-1 OT)
Our Result: Overview of Techniques 4. Need Edge-Disjoint Paths Issue (Correctness): If two paths collide on an edge, PIR will fail (message will be lost) Solution: Choose network carefully so randomly chosen paths will (w.h.p) be edge-disjoint 5. Edge-Disjoint Not Enough Issue (Anonymity): Knowing that paths are disjoint, and able to observe (N-2) paths (of the corrupt parties), Adversary can have advantage is guessing the other 2 paths. Solution: Define a property locally reversible edge-disjointness that a (Network, PathSelection protocol) pair can satisfy, which can be used to prove anonymity.
Thank You! Questions?
