Spatial Discretization for Fine-Grain Zone Checks with STARKs
Fuente:
arXiv
Enregistré dans:
| Auteurs principaux: | , , , |
|---|---|
| Format: | Preprint |
| Publié: |
2025
|
| Sujets: | |
| Accès en ligne: | |
| Tags: |
Ajouter un tag
Pas de tags, Soyez le premier à ajouter un tag!
|
| _version_ | 1866909978750615552 |
|---|---|
| author | Lee, Sungmin Lee, Kichang Han, Gyeongmin Ko, JeongGil |
| author_facet | Lee, Sungmin Lee, Kichang Han, Gyeongmin Ko, JeongGil |
| contents | Many location-based services rely on a point-in-polygon test (PiP), checking whether a point or a trajectory lies inside a geographic zone. Since geometric operations are expensive in zero-knowledge proofs, privately performing the PiP test is challenging. In this paper, we answer the research questions of how different ways of encoding zones affect accuracy and proof cost by exploiting gridbased lookup tables under a fixed STARK execution model. Beyond a Boolean grid-based baseline that marks cells as in- or outside, we explore a distance-aware encoding approach that stores how far each cell is from a zone boundary and uses interpolation to reason within a cell. Our experiments on real-world data demonstrate that the proposed distance-aware approach achieves higher accuracy on coarse grids (max. 60%p accuracy gain) with only a moderate verification overhead (approximately 1.4x), making zone encoding the key lever for efficient zero-knowledge spatial checks. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2512_24238 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Spatial Discretization for Fine-Grain Zone Checks with STARKs Lee, Sungmin Lee, Kichang Han, Gyeongmin Ko, JeongGil Cryptography and Security Many location-based services rely on a point-in-polygon test (PiP), checking whether a point or a trajectory lies inside a geographic zone. Since geometric operations are expensive in zero-knowledge proofs, privately performing the PiP test is challenging. In this paper, we answer the research questions of how different ways of encoding zones affect accuracy and proof cost by exploiting gridbased lookup tables under a fixed STARK execution model. Beyond a Boolean grid-based baseline that marks cells as in- or outside, we explore a distance-aware encoding approach that stores how far each cell is from a zone boundary and uses interpolation to reason within a cell. Our experiments on real-world data demonstrate that the proposed distance-aware approach achieves higher accuracy on coarse grids (max. 60%p accuracy gain) with only a moderate verification overhead (approximately 1.4x), making zone encoding the key lever for efficient zero-knowledge spatial checks. |
| title | Spatial Discretization for Fine-Grain Zone Checks with STARKs |
| topic | Cryptography and Security |
| url | https://arxiv.org/abs/2512.24238 |