Programmi RAM con query limitate e loro applicazioni

Abstract degli autori

I programmi quantistici monouso (Broadbent, Gutoski e Stebila, CRYPTO 2013), o OTP in breve, permettono di codificare una funzionalità in un token quantistico, che può essere valutato su un singolo input scelto e poi diventa inutilizzabile. Pur essendo potente, questo primitivo è intrinsecamente privo di stato e legato a uno scenario in cui occorre emettere e distribuire un token quantistico per ogni singola valutazione di un circuito. Da qui una domanda naturale: è possibile estendere il paradigma della computazione monouso a forme più articolate di accesso controllato e con stato? E una simile estensione offrirebbe vantaggi intrinseci rispetto agli OTP standard? Introduciamo i $\textit{query-limited RAM programs}$ (QLP), una generalizzazione dei QOTP basata su RAM, che supporta computazioni strutturate e con stato, con accesso limitato o determinato da una policy. I QLP consentono sequenze controllate di valutazioni, impedendo al contempo agli avversari di effettuare fork o rollback dello stato computazionale. Questo permette nuove applicazioni che vanno oltre i programmi monouso privi di stato, tra cui token quantistici per macchine di Turing la cui dimensione dipende solo dalla $\textit{code length}$ (e non dal tempo di esecuzione), programmi trasferibili utilizzabili $k$ volte o soggetti a un limite di budget e meccanismi a bassa comunicazione per delegare computazioni in scenari come il Software-as-a-Service. Per costruire i QLP, introduciamo i $\textit{one-shot programs}$, che unificano le firme one-shot (Amos, Georgiou, Kiayias e Zhandry, STOC 2020) con il paradigma della singola interrogazione effettiva (Gupte, Liu, Raizes, Roberts e Vaikuntanathan, STOC 2025). Dimostriamo che i programmi one-shot implicano genericamente programmi query-limited, mostrando che le garanzie rafforzate di non clonabilità delle firme one-shot si traducono in funzionalità potenziate. Nel farlo, chiariamo la relazione tra i primitivi basati su token-firma e i programmi quantistici monouso tramite costruzioni generiche, mostrando in sostanza che i programmi di firma monouso implicano la computazione generale monouso.