We solve Bellman's lost-in-a-forest problem for the golden gnomon $G$, the isosceles triangle with equal sides $1$ and apex angle $108^\circ$: the shortest curve guaranteed to reach the boundary of $G$ from an unknown starting position and heading is a symmetric seven-piece path of segments, circular shoulders, and tangents, of exactly determined length $C=1.282676025459\ldots$. To our knowledge, this is the first proved exact optimum for an isosceles triangle whose base angle is below $45^\circ$. The curve's parameters come from one isolated quartic root, and $C$ is transcendental. Equivalently, $C^{-1}G$ is the smallest homothetic golden-gnomon cover of all unit arcs. The proof introduces a balanced support calibration: one weighted family of escape inequalities, built on the linear relation among the triangle's three normals, exactly saturated by the candidate, through eighteen exact support windows, and confronting every shorter competitor at once. Aggregation along the normal fan compresses the calibration to a finite zero-sum family of supported vectors; summation by parts then bounds its total by path length whenever the running suffix balance, the ledger, stays in the unit disk. A local two-gap surgery and cyclic bitonicity force a shortest hypothetical counterexample into exactly the temporal order the ledger tolerates. Lean 4 verifies the two finite algebraic certificate families and the reusable discrete ledger identities and bounds.
# VeriSBOM: Secure and Verifiable SBOM Sharing Via Zero-Knowledge Proofs **VeriSBOM**, a trustless, selectively disclosed SBOM framework that provides cryptographic verifiability of SBOMs using zero-knowledge proofs. Within VeriSBOM, third parties can validate specific statements about a delivered software, mainly regarding the authenticity of the dependencies and policy compliance, without inspecting the content of an SBOM. Respectively, VeriSBOM allows independent third parties to verify if a software contains authentic dependencies distributed by official package managers and that the same dependencies satisfy rigorous policy constraints such as the absence of vulnerable dependencies or the adherence with specific licenses models. ## Key Features * **Selective Disclosure (Hiding):** Choose which proprietary components to hide from the public SBOM. The system generates a cryptographic proof that replaces the plaintext data, guaranteeing privacy. * **High-Performance Folding:** Powered by **Nova-Scotia**, utilizing recursive SNARKs to handle SBOMs. * **Interactive Dashboard:** A complete 4-step workflow (Package Manager, Auditor, Vendor, Client) built with **Streamlit**. ## Repository structure The repository contains three main folders: 1. **Empirical**: contains **Benchmarking** and **src**, for the analysis and source code, respectively. 2. **User study**: contains the code and results of the user study. 3. **README_Doc**: contains the images used for this documentation. ## VeriSBOM Architecture The system is divided into four main roles: 1. **Package Manager**: Maintains the package repository with the allowed packages. 2. **Auditor:** Represents the regulatory body marking the compliance status by checking the packages of the package manager. 3. **Software Vendor:** Represents the entity that provides software artefacts and wants to hide the related SBOMs for privacy reasons. He is responsible for the generation of the cryptographic proofs as verifiable substitutes of the hidden packages in SBOMs. 4. **Client:** The end-user who receives the cryptographic proofs along with the software artefact for verifying binding, inclusion and compliance status. ## Web Access (Recommended) **For direct access to the artefact, VeriSBOM can be accessed at this public link** https://verisbom-verisbom-software.hf.space ## Setup & Installation Follow the README within the artefact ## Operational Workflow The application follows a **linear workflow** composed of four steps. Each step depends on the output generated in the previous one. > **Performance Note** Due to the cryptographic operations involved, generating proofs may take some time depending on the number and complexity of the active policy constraints. In the current reference environment, proof generation takes approximately **~5 seconds**, while verification takes around **~3 seconds per proof**. ## Step 1 — Package Manager In this step, the **Package Manager initialises the package repository**. ### Instructions 1. Open the **Package Manager** tab. 2. Click **`Load repository`**. > For convenience, the system automatically loads a **default repository containing packages from the NPM ecosystem**. ### Expected Output After successful execution: - A **green confirmation message** is displayed. - The **package list** appears on the left panel. - The **dependencies of each package** can be inspected on the right panel using the search bar. - A **dependency graph** is displayed at the bottom of the interface. ## Step 2 — Auditor In this step, the **Auditor defines policy constraints** that will be applied to the packages in the repository. ### Instructions 1. Enter a **policy name** (e.g., `Vulnerabilities`, `MIT License`). 2. Click **`Add`** to create the policy constraint. 3. Use the **search bar** to locate target packages. 4. **Uncheck packages** to mark them as **non-compliant**. > By default, **all packages are marked as compliant**. 5. Click **`Save and Propagate`** to apply the policy. ### Optional - Repeat the previous steps to create additional policy constraints. - Remove policies that are no longer required. ### Expected Output - A **green confirmation message** appears. - A **dependency graph visualisation** shows how non-compliance propagates across dependencies for the selected policy (or combination of policies). ## Step 3 — Software Vendor In this step, the **Software Vendor generates cryptographic proofs for a given SBOM**. ### Instructions 1. Upload a **local SBOM file**. > For demonstration purposes, the system automatically loads an **example SBOM**. 2. In the **Selective Disclosure** section: - Select which SBOM packages should be used for proof generation. 3. Click **`Generate Proofs`**. 3. Click **`Download`**. - Download the SBOM with hidden components and plaintext components ### Expected Output - A **progress bar** indicates the proof generation process. - **Green confirmation messages** appear once proofs are generated successfully. > **Important:** Successful proof generation only means that the **cryptographic proof has been constructed correctly**. Compliance with policies is verified only in **Step 4**. ## Step 4 — Client In the final step, the **Client verifies the proofs generated by the vendor**. ### Instructions 1. Upload the **SBOM**. 2. Select a **policy** from the dropdown menu. 3. Click **`Verify`**. ### Expected Output - **Verified (green badge)** The SBOM satisfies the selected policy. - **Failed (red badge)** The verification failed, and the interface displays the reason for the failure.
Hotaru Beam is a logic puzzle which objective is to connect circles placed on a grid by drawing only lines with specified starting points and numbers of bends. A zero-knowledge proof is a communication protocol that allows one player to persuade the other that they are in possession of a certain piece of information without actually revealing it. We show that Hotaru Beam is NP-complete and present a physical zero-knowledge proof (i.e. implementable using physical items) for proving that one knows a solution to the puzzle.
The problem of determining the position relationship between points and polygons is very extensive in practical applications. However, the existing solutions are only applicable to the case of convex polygons, and no solutions are given for arbitrary polygons. In addition, most of the existing schemes are carried out under the semi-honest model, and cannot resist the active attack of malicious adversaries. In order to solve these problems, this paper uses Paillier's encryption scheme, the idea of zero-knowledge proof to design a decision protocol to protect the position relationship between points and arbitrary polygons, which can not only prevent the deceptive behavior of malicious adversaries, but also extend the application from convex polygons to arbitrary polygons. A simulation example is used to prove that this paper is safe and efficient under the malicious model.
Proof-of-Stake (PoS) is often promised to decentralize the blockchain security over Proof-of-Work (PoW) by allowing more people to join without specialized mining hardware. However, there is no consensus in the literature on PoS's centralization, with strong arguments from both sides. Furthermore, theoretical models of PoS often assume very strong conditions that cannot be justified in practice. I relax these assumptions and derive a more realistic model that takes into account trading activity and fees. My model shows that the limiting distribution can be centralized regardless of the initial distribution, reconciling conclusions in prior studies.
We propose a technique to construct physical Zero-Knowledge Proof (ZKP) protocols for puzzles that require a single loop draw feature. Our approach is based on the observation that a loop has only one hole and this property remains stable by some simple transformations. Using this trick, we can transform a simple big loop, which is visible to anyone, into the solution loop by using transformations that do not disclose any information about the solution. We illustrate our technique by applying it to construct physical ZKP protocols for two Nikoli puzzles: Slitherlink and Masyu.
Abstract—Digital signature schemes are a founda-tional cryptographic building block in certification and the projection of trust. Based on a signature scheme on committed graphs, we propose a toolkit of certification and proof methods to sign committed topology graphs and to prove properties of their certificates in zero-knowledge. This toolkit allows an issuer, such as an auditor, to sign the topology repre-sentation of an infrastructure. The prover, such as an infrastructure provider, can then convince a verifier of topology properties, such as partitions, connectivity or isolation, without disclosing the structure of the topol-ogy itself. By that, we can achieve the certification of the structure of critical systems, such as infrastructure clouds or outsourced systems, while still maintaining confidentiality. We offer zero-knowledge proofs of knowledge for a general specification language of security goals for virtualized infrastructures, such that high-level security goals can be proven over the topology certificate. Our method builds upon the Camenisch-Lysyanskaya signature scheme, is based on honest-verifier proofs and the strong RSA assumption. I.
The paper presents a more efficient noninteractive zero knowledge proof system (NIZK) for 3 colorability. The length of the proof is 1/3 and the length of the reference string is 1/4 of those of Blum et al. (1988) respectively. The proposed NIZK is based on the quadratic residuosity assumption.>