Explore the paper on privately comparing regions in Euclidean space for validating sensor outputs, with applications in collaborative obstacle detection for connected autonomous vehicles. The research addresses the challenge of maintaining trust and privacy among different manufacturers while ensuring covert operations. Parties aim to determine overlapping regions defined by vertices, considering assumptions of finite space and convex regions. Challenges include dealing with sensor output variations and the computational cost of determining regions of overlap. The study proposes private protocols for secure communication and validation in a global frame of reference.
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. If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.
You are allowed to download the files provided on this website for personal or commercial use, subject to the condition that they are used lawfully. All files are the property of their respective owners.
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.
What is this paper about? What is this paper about? Security Metaphysics I see an object at (x1 , y1, z1). Do you? Can we design protocols to privately compare regions (enclosing an object) in an arbitrary-dimension Euclidean space? Stony Brook Network Security and Applied Cryptography Laboratory Stony Brook Network Security and Applied Cryptography Laboratory 2 2
Applications Applications Security Metaphysics Connected autonomous vehicles (CAVs) sharing info to validate sensors, detect obstacles Collaborative obstacle detection detect obstacles, limited view, terrain, covert Why private protocols? trust between different manufacturers, maintaining covertness, location privacy * image courtesy AUDI A2D2 **image courtesy US FORCENET Stony Brook Network Security and Applied Cryptography Laboratory Stony Brook Network Security and Applied Cryptography Laboratory 3 3
Problem setting Problem setting Security Metaphysics Parties: two semi-honest Inputs:?-dimensional objects (or enclosing regions) defined by vertices Output: do the vertices outline regions that overlap, and by how much? Assumptions: Finite space, global frame of reference, convex regions Stony Brook Network Security and Applied Cryptography Laboratory Stony Brook Network Security and Applied Cryptography Laboratory 4 4
Challenges Challenges Security Metaphysics Sensor outputs aren t exact, variations in measurement possible comparing vertices isn t enough, need fuzzy matches Detecting overlaps is not enough computing region of overlap is expensive I see an object at (x2, y2, z2) I see an object at (x1 , y1, z1) Stony Brook Network Security and Applied Cryptography Laboratory Stony Brook Network Security and Applied Cryptography Laboratory 5 5
Our Idea Our Idea Security Metaphysics Use cheap primitives to detect overlaps Approximate volume of overlap: high volume of overlap objects are same Stony Brook Network Security and Applied Cryptography Laboratory Stony Brook Network Security and Applied Cryptography Laboratory 6 6
Existing works do not scale Existing works do not scale Security Metaphysics Cryptographic matching (exact/fuzzy) designed for point comparisons: scale to large (infinite) sets of points? Secure computation geometry [Atallah & Du, 2001] limited research, expensive primitives, 2D applications common Generic secure computation (FHE/garbled circuits) complex algorithms, slower than tailor-made tools Stony Brook Network Security and Applied Cryptography Laboratory Stony Brook Network Security and Applied Cryptography Laboratory 7 7
Our results Our results Security Metaphysics Detecting overlaps of axis-aligned boxes in d-dimensional space Approximating volume of overlap of axis-aligned boxes in d-dimensional space Approximating volume of overlap of oriented boxes in d-dimensional space Detecting overlaps of oriented boxes in d-dimensional space Stony Brook Network Security and Applied Cryptography Laboratory Stony Brook Network Security and Applied Cryptography Laboratory 8 8
Detecting axis Detecting axis- -aligned box overlaps aligned box overlaps Security Metaphysics Problem: Given two AA boxes in ?-dimensional space, determine if they overlap Compute Minkowski difference of boxes: pairwise differences of all points Check if origin lies inside the Minkowski difference of boxes Requires drange checks (millionaire s problem) ?(?) A B A - B Minkowski difference Original boxes Stony Brook Network Security and Applied Cryptography Laboratory Stony Brook Network Security and Applied Cryptography Laboratory 9 9
Approximating volume of overlap Approximating volume of overlap Security Metaphysics Problem: Approximate volume of overlap without computing the region Volume computation through point queries [Bringmann & Friedrich] Randomly sample points from box A Count how many points are in box B New private point inclusion protocol ? ???? ?,? ? B A Pr[????????? ?????????? ?,?????????? + ? ] 1 ? Error Slack probability Stony Brook Network Security and Applied Cryptography Laboratory Stony Brook Network Security and Applied Cryptography Laboratory 10 10
Benchmarks Benchmarks Security Metaphysics Datasets: Randomly generated polytopes in 2D, 3D Axis-aligned boxes from CARLA driving simulator Axis-aligned boxes from Audi A2D2 dataset Oriented boxes from ScanNet Metrics Communication volume Compute time Scaling with multiple objects Stony Brook Network Security and Applied Cryptography Laboratory Stony Brook Network Security and Applied Cryptography Laboratory 11 11
Detecting overlaps Detecting overlaps Security Metaphysics Axis-aligned boxes Comm. (KB) Compute (ms) Improvement Our work 42 2.8 - , - GC baseline 51 11.6 21% less comm., 4.2x faster (lower is better) Oriented boxes Comm. (KB) Compute (ms) Improvement Our work 26 211 - , - GC baseline 30 280 15% less comm, 1.3x faster (lower is better) Stony Brook Network Security and Applied Cryptography Laboratory Stony Brook Network Security and Applied Cryptography Laboratory 12 12
Approximating volume of overlap Approximating volume of overlap Security Metaphysics Comm. volume vs Number of boxes Compute time vs Number of boxes 25 300 250 20 Comm. (in KB) Time (in ms) 200 15 4.3x 150 4x 10 100 5 50 0 0 2 4 6 8 10 2 4 6 8 10 number of boxes number of boxes Our Protocol Baseline Our Protocol Baseline Compute time vs. number of boxes (lower is better) Communication volume vs. number of boxes (lower is better) Slack = 0.1, Error = 0.001 Stony Brook Network Security and Applied Cryptography Laboratory Stony Brook Network Security and Applied Cryptography Laboratory 13 13
Conclusion Conclusion Security Metaphysics New private protocols for secure computational geometry Applications to autonomous vehicles Benchmarks on real data shows feasibility Stony Brook Network Security and Applied Cryptography Laboratory Stony Brook Network Security and Applied Cryptography Laboratory 14 14
Thank you Thank you Security Metaphysics Stony Brook Network Security and Applied Cryptography Laboratory Stony Brook Network Security and Applied Cryptography Laboratory 15 15
Detecting overlaps Detecting overlaps Security Metaphysics Problem: Given two oriented in d-dimensional space, determine if they overlap Edge-face intersection End point of edge on opposite side of face Check sign of scalar product with face normal vector V-OLE based scalar product computation ?(???_????? ???_????? ?) Enclosing boxes: random point test ?(?) A B a b a and b are on opposite sides of the face Random point in A lies in B Stony Brook Network Security and Applied Cryptography Laboratory Stony Brook Network Security and Applied Cryptography Laboratory 16 16
Scaling with number of boxes Scaling with number of boxes Security Metaphysics Comm. volume vs Number of boxes Compute time vs Number of boxes 250 3500 3000 200 Comm. (in KB) Time (in ms) 2500 150 2000 5.1 6.1 1500 100 1000 50 500 0 0 2 4 6 8 10 2 4 6 8 10 number of boxes number of boxes Our Protocol Baseline Our Protocol Baseline Compute time vs. number of boxes (lower is better) Communication volume vs. number of boxes (lower is better) Stony Brook Network Security and Applied Cryptography Laboratory Stony Brook Network Security and Applied Cryptography Laboratory 17 17
