Bootstrapping Mutual Attestation with Kleene's Second Recursion Theorem
Abstract
Remote attestation is a procedure by which a system (such as a Trusted Execution Environment) proves its own configuration to a remote peer. Here, the configuration includes the measurements (hash digests) of software components. When multiple nodes perform mutual attestation, each node must maintain the reference values for its peers' measurements. We refer to this as the reference-value bootstrapping problem for mutual attestation. In this paper, we formulate the problem as a fixed-point equation and solve it directly using Kleene's second recursion theorem. In our approach, nodes can reconstruct one another's source code, thereby allowing each node to derive the reference values at runtime. When a source code itself is deployed, as with a Python script, a node derives the peer's reference value directly from its reconstructed source. When a build artifact is deployed, as with AWS Nitro Enclaves, a node instead reproducibly builds the peer's artifact from its reconstructed source and derives the reference value from it. As a proof of concept, we develop transpilers in Python and Nix to generate mutually referencing programs. Using these transpilers, we demonstrate the mutual derivation of reference values for the two deployment models mentioned above. Our solution is architecture-independent, requires no trusted third party, and works with existing attestation stacks without modification.
Related
- A Kleene-inspired sequent system for a minimal logic of evidence and truth
- Exact Error Bootstrapping and Comb Bootstrapping in FHEW/TFHE
- Bootstrapping autoregressive duration models
- A Contraction Framework for Stochastic Operators with Bootstrapping: Application to TD Learning
- Beyond Verified Answers: Solver-Informed Self-Distillation for Bootstrapping Operations Research Language Models
BibTeX
@misc{imamura2026bootstrapping,
title = {{Bootstrapping Mutual Attestation with Kleene's Second Recursion Theorem}},
author = {Takuma Imamura},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2608.20671},
eprint = {2608.20671},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2608.20671},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - Bootstrapping Mutual Attestation with Kleene's Second Recursion Theorem
AU - Takuma Imamura
PY - 2026
DA - 2026/09/30
PB - arXiv
DO - 10.48550/arxiv.2608.20671
UR - https://arxiv.org/abs/2608.20671
AB - Remote attestation is a procedure by which a system (such as a Trusted Execution Environment) proves its own configuration to a remote peer. Here, the configuration includes the measurements (hash digests) of software components. When multiple nodes perform mutual attestation, each node must maintain the reference values for its peers' measurements. We refer to this as the reference-value bootstrapping problem for mutual attestation. In this paper, we formulate the problem as a fixed-point equation and solve it directly using Kleene's second recursion theorem. In our approach, nodes can reconstruct one another's source code, thereby allowing each node to derive the reference values at runtime. When a source code itself is deployed, as with a Python script, a node derives the peer's reference value directly from its reconstructed source. When a build artifact is deployed, as with AWS Nitro Enclaves, a node instead reproducibly builds the peer's artifact from its reconstructed source and derives the reference value from it. As a proof of concept, we develop transpilers in Python and Nix to generate mutually referencing programs. Using these transpilers, we demonstrate the mutual derivation of reference values for the two deployment models mentioned above. Our solution is architecture-independent, requires no trusted third party, and works with existing attestation stacks without modification.
ER -