Verifiable Homomorphic Linear Combinations in Multi-Instance Time-Lock Puzzles
<|reference_start|>Verifiable Homomorphic Linear Combinations in Multi-Instance Time-Lock Puzzles: Time-Lock Puzzles (TLPs) have been developed to securely transmit sensitive information into the future without relying on a trusted third party. Multi-instance TLP is a scalable variant of TLP that enables a server to efficiently find solutions to different puzzles provided by a client at once. Nevertheless, existing multi-instance TLPs lack support for (verifiable) homomorphic computation. To address this limitation, we introduce the "Multi-Instance partially Homomorphic TLP" (MH-TLP), a multi-instance TLP supporting efficient verifiable homomorphic linear combinations of puzzles belonging to a client. It ensures anyone can verify the correctness of computations and solutions. Building on MH-TLP, we further propose the "Multi-instance Multi-client verifiable partially Homomorphic TLP" (MMH-TLP). It not only supports all the features of MH-TLP but also allows for verifiable homomorphic linear combinations of puzzles from different clients. Our schemes refrain from using asymmetric-key cryptography for verification and, unlike most homomorphic TLPs, do not require a trusted third party. A comprehensive cost analysis demonstrates that our schemes scale linearly with the number of clients and puzzles.<|reference_end|>
@article{abadi2024verifiable,
    title={Verifiable Homomorphic Linear Combinations in Multi-Instance Time-Lock
  Puzzles},
    author={Aydin Abadi},
    journal={arXiv preprint arXiv:2408.12444},
    year={2024},
    archivePrefix={arXiv},
    eprint={2408.12444},
    primaryClass={cs.CR cs.DC cs.LG}
}