The main motivation of this thesis is the uncertain panorama of cybersecurity risks and threats, accentuated by the arrival of the quantum computer. This type of computer is completely disruptive, since its operation is governed by quantum mechanical phenomena. The implementation of Shors algorithm in a quantum computer with relevant size and performance will allow breaking the security of the most currently used pre-quantum asymmetric algorithms. This panorama makes it necessary to research new cryptographic paradigms that are resistant to quantum threats. Thus, quantum and post-quantum cryptography emerge. Several national security agencies are recommending the immediate migration to quantum-resistant solutions of vulnerable critical cryptosystems, mainly by implementing post-quantum algorithms, some of them recently standardized. Quantum cryptography bases its security on the same physical foundations as quantum computers, being independent of the computational capacity of an adversary. The implementation of solutions based on quantum cryptography still requires greater technological maturity, development of standards and certification of devices. In addition, the infrastructures necessary for these networks are expensive and difficult to scale, in their current conception, due to the need to have trusted intermediate nodes. However, the rapid advances in this field allow to further research quantum communications networks to be a reality for daily operations where a high level of security is required. The main objective of this thesis is to investigate quantum cryptography-based solutions that go beyond quantum key distribution (QKD). The thesis has focused on proposing two novel cryptographic mechanisms ensuring that the new protocols are comparable in efficiency with pre-quantum and post-quantum algorithms. Furthermore, it has been taken into account that these protocols are implementable in current quantum communications infrastructures (QCI) to maximize the technical benefit of the investments carried out for these deployments. As a result, a quantum-assisted digital signature protocol (Q-DS) and a quantum zero-knowledge proof (QZKP) have been proposed, analyzed and implemented, which combine symmetric pre-quantum mechanisms with QKD. The proposed quantum-assisted digital signature protocol avoids the use of vulnerable pre- quantum public-key cryptosystems, using symmetric keys generated by QKD and using them with widely known NIST-approved hash functions, giving rise to a composite cryptosystem whose security against various attacks is demonstrated. For its part, the proposed quantum zero-knowledge proof allows the authentication of users in a QCI without revealing personal information during the process. The proposal of a quantum version of ZKP has been done in this thesis for the very first time, without precedent in the literature. A theoretical study as well as experimental tests have been carried out, resulting in a secure and efficient authentication mechanism. Finally, given the industrial nature of this thesis, the evolution of the political panorama regarding quantum technologies and PQC have been closely followed, including the positions of relevant security-oriented organizations and economic investments for project funding. These issues, although not technical, have influenced the design of the cryptographic protocols proposed in this thesis. RESUMEN La principal motivación de esta tesis es el panorama incierto de los riesgos y amenazas de ciberseguridad, acentuado por la llegada del ordenador cuántico. Este tipo de ordenadores son completamente disruptivos, ya que su funcionamiento se rige por fenómenos mecánico-cuánticos. La implementación del algoritmo de Shor en un ordenador cuántico con tamaño y rendimiento relevantes permitirá romper la seguridad de los algoritmos asimétricos pre-cuánticos más utilizados actualmente. Este panorama hace necesario investigar nuevos paradigmas criptográficos que sean resistentes a las amenazas cuánticas. Así, surgen la criptografía cuántica y post-cuántica. Varias agencias de seguridad nacional han recomendado la migración inmediata de los criptosistemas críticos vulnerables a soluciones "quantum-resistant", principalmente mediante la implementación de algoritmos post-cuánticos, algunos de ellos recientemente estandarizados. La criptografía cuántica basa su seguridad en los mismos fundamentos físicos que los ordenadores cuánticos, siendo independiente de la capacidad computacional de un adversario. La implementación de soluciones basadas en criptografía cuántica aún requiere de mayor madurez tecnológica, desarrollo de estándares y certificación de dispositivos. Además, las infraestructuras necesarias para estas redes son costosas y difíciles de escalar, en su concepción actual, debido a la necesidad de contar con nodos intermedios de confianza. Sin embargo, los rápidos avances en este campo permiten que la investigación de las redes de comunicaciones cuánticas se vaya convirtiendo en una realidad para las operaciones diarias donde se requiere un alto nivel de seguridad. El objetivo principal de esta tesis es investigar soluciones basadas en criptografía cuántica que vayan más allá de la distribución de claves cuánticas (QKD). La tesis se ha centrado en proponer dos mecanismos criptográficos novedosos asegurando que los nuevos protocolos sean comparables en eficiencia con algoritmos pre-cuánticos y post-cuánticos. Además, se ha tenido en cuenta que estos protocolos sean implementables en las actuales infraestructuras de comunicaciones cuánticas (QCI) para maximizar el beneficio técnico de las inversiones realizadas para estos despliegues. Como resultado, se han propuesto, analizado e implementado un protocolo de firma digital asistido por claves cuánticas (Q-DS) y una prueba de conocimiento cero cuántica (QZKP), que combinan mecanismos pre-cuánticos simétricos con QKD. El protocolo de firma digital cuántica propuesto evita el uso de criptosistemas de clave pública pre-cuánticos vulnerables, utilizando claves simétricas generadas por QKD y utilizándolas con funciones hash ampliamente conocidas aprobadas por el NIST, dando lugar a un criptosistema compuesto cuya seguridad frente a diversos ataques se demuestra. Por su parte, la QZKP propuesta permite la autenticación de usuarios en una QCI sin revelar información personal durante el proceso. La propuesta de una versión cuántica de ZKP se ha realizado en esta tesis por primera vez, sin precedentes en la literatura. Se ha realizado un estudio teórico así como pruebas experimentales, dando como resultado un mecanismo de autenticación seguro y eficiente. Finalmente, dada la naturaleza industrial de esta tesis, se ha seguido de cerca la evolución del panorama político en relación con las tecnologías cuánticas y PQC, incluyendo las posiciones de las organizaciones relevantes en materia de seguridad y las inversiones económicas para la financiación de proyectos. Estas cuestiones, aunque no técnicas, han influido en el diseño de los protocolos criptográficos propuestos en esta tesis.
John C. Kolesar, Shan Ali, Timos Antonopoulos, Ružica Piskač
Zero-knowledge (ZK) protocols enable software developers to provide proofs of their programs’ correctness to other parties without revealing the programs themselves. Regular expressions are pervasive in real-world software, and zero-knowledge protocols have been developed in the past for the problem of checking whether an individual string appears in the language of a regular expression, but no existing protocol addresses the more complex PSPACE-complete problem of proving that two regular expressions are equivalent. We introduce Crêpe , the first ZK protocol for encoding regular expression equivalence proofs and also the first ZK protocol to target a PSPACE-complete problem. Crêpe uses a custom calculus of proof rules based on regular expression derivatives and coinduction, and we introduce a sound and complete algorithm for generating proofs in our format. We test Crêpe on a suite of hundreds of regular expression equivalence proofs. Crêpe can validate large proofs in only a few seconds each.
The rapid adoption of artificial intelligence (AI) systems, such as predictive AI, generative AI, and explainable AI, is in contrast to the slower development and uptake of robotic AI systems. Dynamic environments, sensory processing, mechanical movements, power management, and safety are inherent complexities of robotic intelligence capabilities that can be addressed using novel AI approaches. The current AI landscape is dominated by machine learning techniques, specifically deep learning algorithms, that have been effective in addressing some of these challenges. However, these algorithms are subject to computationally complex processing and operational needs such as high data dependency. In this paper, we propose a computation-efficient and data-efficient framework for robotic motion intelligence (RMI) based on vector symbolic architectures (VSAs) and blockchain-based smart contracts. The capabilities of VSAs are leveraged for computationally efficient learning and noise suppression during perception, motion, movement, and decision-making tasks. As a distributed ledger technology, smart contracts address data dependency through a decentralized, distributed, and secure transactions ledger that satisfies contractual conditions. An empirical evaluation of the framework confirms its value and contribution towards addressing the practical challenges of robotic motion intelligence by significantly reducing the learnable parameters by 10 times while preserving sufficient accuracy compared to existing deep learning solutions.
Anne Broadbent, Alex B. Grilo, Nagisa Hara, Arthur Mehta
In a proof of knowledge (PoK), a verifier becomes convinced that a prover possesses privileged information. In combination with zero-knowledge proof systems, PoKs play an important role in security protocols such as in digital signatures and authentication schemes, as they enable a prover to demonstrate possession of certain information (such as a private key or a credential), without revealing it. A PoK is formally defined via the existence of an extractor, which is capable of reconstructing the key information that makes a verifier accept, given oracle access to any accepting prover. We extend this concept to the setting of a single classical verifier and multiple quantum provers and present the first statistical zero-knowledge (ZK) PoK proof system for problems in QMA. To achieve this, we establish the PoK property for the ZK protocol of Broadbent, Mehta, and Zhao (TQC 2024), which applies to the local Hamiltonian problem. More specifically, we construct an extractor which, given oracle access to a provers' strategy that leads to high acceptance probability, is able to reconstruct the ground state of a local Hamiltonian. Our result can be seen as a new form of self-testing, where, in addition to certifying a pre-shared entangled state, the verifier also certifies that a prover has access to a quantum system, in particular, a ground state; this indicates a new level of verification for a proof of quantumness.
Yuming Huang, Jing Tang, Qianhao Cong, T. B. Richard · 6 authors
In blockchains using the Proof-of-Work (PoW) consensus mechanism, a mining pool is a joint group of miners who combine their computational resources and share the generated revenue. Similarly, when the Proof-of-Stake (PoS) consensus mechanism is adopted, the staking pool imitates the design of the mining pool by aggregating the stakes. However, in PoW blockchains, the pooling approach has been criticized to be vulnerable to the block withholding (BWH) attack. BWH attackers may steal the dividends from victims by pretending to work but making invalid contributions to the victim pools. It is well known that BWH attackers against PoW face the miner's dilemma . To our knowledge, despite the popularity of PoS, we are the first to study the pool BWH attack against PoS. Interestingly, we find that, for a network only consisting of one attacker pool and one victim pool, the attacker will eventually manipulate the network while the victim will vanish by losing the stake ratio gradually. Moreover, in a more realistic scenario with multiple BWH attacker pools and one solo staker who does not join any pools, we show that only one lucky attacker and the solo staker will survive, whereas all the other pools will vanish gradually, revealing the staker's dilemma . These findings indicate that, compared to PoW, the BWH attack on PoS has a much more severe impact due to the attacker's resource aggregation advantage. Our analysis is supported by experiments on massive real blockchain systems and numerical simulations.
Succinct arguments are proof systems that allow a powerful, but untrusted, prover to convince a weak verifier that an input x belongs to a language \(L \in \mathsf {NP}\) , with communication that is much shorter than the \(\mathsf {NP}\) witness. Such arguments, which grew out of the theory literature, are now drawing immense interest also in practice, where a key bottleneck that has arisen is the high computational cost of proving correctness. In this work, we address this problem by constructing succinct arguments for general computations, expressed as Boolean circuits (of bounded fan-in), with a strictly linear size prover. The soundness error of the protocol is an arbitrarily small constant. Prior to this work, succinct arguments were known with a quasi- linear size prover for general Boolean circuits or with linear-size only for arithmetic circuits, defined over large finite fields. In more detail, for every Boolean circuit \(C=C(x,w)\) , we construct an \(O(\log |C|)\) -round argument-system in which the prover can be implemented by a size \(O(|C|)\) Boolean circuit (given as input both the instance x and the witness w ), with arbitrarily small constant soundness error and using \(\mathrm{poly}(\lambda ,\log |C|)\) communication, where \(\lambda\) denotes the security parameter. The verifier can be implemented by a size \(O(|x|) + \mathrm{poly}(\lambda , \log |C|)\) circuit following a size \(O(|C|)\) private pre-processing step, or, alternatively, by using a purely public-coin protocol (with no pre-processing) with a size \(O(|C|)\) verifier. The protocol can be made zero-knowledge using standard techniques (and with similar parameters). The soundness of our protocol is computational and relies on the existence of collision resistant hash functions that can be computed by linear-size circuits, such as those proposed by Applebaum et al. (ITCS, 2017). At the heart of our construction is a new information-theoretic interactive oracle proof ( \(\mathsf {IOP}\) ), an interactive analog of a \(\mathsf {PCP}\) , for circuit satisfiability, with constant prover overhead. The improved efficiency of our \(\mathsf {IOP}\) is obtained by bypassing a barrier faced by prior \(\mathsf {IOP}\) constructions, which needed to (either explicitly or implicitly) encode the entire computation using a multiplication code.
We examine which decentralized finance architectures enable meaningful regulation by combining financial and computational theory. We show via deduction that a decentralized and permissionless Turing-complete system cannot provably comply with regulations concerning anti-money laundering, know-your-client obligations, some securities restrictions and forms of exchange control. Any system that claims to follow regulations must choose either a form of permission or a less-than-Turing-complete update facility. Compliant decentralized systems can be constructed only by compromising on the richness of permissible changes. Regulatory authorities must accept new tradeoffs that limit their enforcement powers if they want to approve permissionless platforms formally. Our analysis demonstrates that the fundamental constraints of computation theory have direct implications for financial regulation. By mapping regulatory requirements onto computational models, we characterize which types of automated compliance are achievable and which are provably impossible. This framework allows us to move beyond traditional debates about regulatory effectiveness to establish concrete boundaries for automated enforcement.
Secure multi-party computation is an area in cryptography which studies how multiple parties can compare their private information without revealing it. Besides digital protocols, many unconventional protocols for secure multi-party computation using physical objects have also been developed. The vast majority of them use playing cards as the main tools. In 2024, Kaneko et al. introduced the use of a balance scale and coins in zero-knowledge proof protocols for pencil puzzles. In this paper, we extend the use of these tools to secure multi-party computation. In particular, we develop four protocols that can securely compute any $n$-variable Boolean function using a balance scale and coins.
Abstraction Liquidity Theory (ALT) develops a formal framework for determining when local problem-solving traces become reusable abstraction assets that reduce downstream search, evaluation, and certification costs. The paper treats abstractions as operational tokens rather than informal artifacts, and evaluates them through declared receivers, opportunity measures, baselines, lifecycle costs, telemetry, evidence validity, transport scope, authority envelopes, hazard constraints, and runtime certificate packets. The manuscript introduces an actor-neutral certification kernel for AI agents and other computational actors. It specifies machine-readable packet schemas, dual exploration and settlement ledgers, finite-sample lower and upper bounds, causal and calibrated-proxy value estimands, mission-validity certificates, adversarial-token rejection, root/finality checks, baseline refresh, deprecation, resurrection, rollback, and kernel-update bridges. The goal is to make abstraction evaluation executable: an agent should be able to parse a packet, verify evidence, admit or reject a token, suspend stale claims, deprecate negative-liquidity tokens, and preserve raw net safe capital under fail-closed rules. The paper further defines Target-valid ALT-CARA, a criterion for certified ASI realization acceleration. Rather than claiming unconstrained ASI achievement, ALT-CARA formalizes time-to-target acceleration relative to a resource-matched baseline upper envelope, under declared capability bases, target-validity certificates, raw net solvency, viability conditions, hazard and authority constraints, transport validity, finality, and causal reproduction evidence. The framework connects AI evaluation, causal inference, runtime verification, risk control, skill reuse, safe exploration, and distributed certification into a single theory of mission-valid safe abstraction capital.
Orestis Melkonian, Wouter Swierstra, James Chapman, Sub Software Technology · 6 authors
Distributed ledgers nowadays manage substantial monetary funds in the form of cryptocurrencies such as Bitcoin, Ethereum, and Cardano. For such ledgers to be safe, operations that add new entries must be cryptographically sound - but it is less clear how to reason effectively about such ever-growing linear data structures. This paper demonstrates how distributed ledgers may be viewed as computer programs, that, when executed, transfer funds between various parties. As a result, familiar program logics, such as Hoare logic, are applied in a novel setting. Borrowing ideas from concurrent separation logic, this enables modular reasoning principles over arbitrary fragments of any ledger. All of our results have been mechanised in the Agda proof assistant.
Zero-Knowledge Proofs (ZKPs) are public key cryptosystem that enables to demonstrate that a statement which is known by them is correct without revealing the same to the verifier. ZKPs have moved in modern cryptographic systems, blockchain applications, decentralized finance (DeFi) and identity authentication systems. This paper explores the evolution of ZKPs and their significance as in secure and privacy preserving. We classify ZKPs into two groups namely interactive and non-interactive, discussing prominent protocols such as zk-SNARKs, zk-STARKs, Bulletproofs, PLONK, and Halo2. Each approach has advantages as efficiency, proof size, and computational overhead. The study further examines the multitude of applications of ZKPs, as privacy-enhanced blockchain transactions, zero-knowledge rollups for scalability, decentralized identity management, secure voting mechanisms, and regulatorycompliant financial systems. With advantages, possible limitations in scalability, lack of standardization, and vulnerabilities to emerging quantum computing threats. Due to the restrictions, hardware acceleration through GPUs and others, presents promising solutions, while new protocols such as PLONK and Halo2 seek to optimize performance to earlier developed solutions. Finally, we discuss the future trajectory of ZKPs. This review aims to provide an understanding of the current state of ZKP research, its applications, and the key challenges that need to be addressed to facilitate broader adoption.
We initiate the study of relativistic zero-knowledge quantum proof of knowledge systems with classical communication, formally defining a number of useful concepts and constructing appropriate knowledge extractors for all the existing protocols in the relativistic setting which satisfy a weaker variant of the special soundness property due to Unruh (EUROCRYPT 2012). We show that there exists quantum proofs of knowledge with knowledge error 1/2 + negl(η) for all relations in NP via a construction of such a system for the Hamiltonian cycle relation using a general relativistic commitment scheme exhibiting the fairly-binding property due to Fehr and Fillinger (EUROCRYPT 2016). We further show that one can construct quantum proof of knowledge extractors for proof systems which do not exhibit special soundness, and therefore require an extractor to rewind multiple times. We develop a new multi-prover quantum rewinding technique by combining ideas from monogamy of entanglement and gentle measurement lemmas that can break the quantum rewinding barrier. Finally, we prove a new bound on the impact of consecutive measurements and use it to significantly improve the soundness bound of some existing relativistic zero knowledge proof systems, such as the one due to Chailloux and Leverrier (EUROCRYPT 2017).
Junchao Chen, Alberto Sonnino, Lefteris Kokoris-Kogias, Mohammad Sadoghi
Sharding has emerged as a critical technique for enhancing blockchain system scalability. However, existing sharding approaches face unique challenges when applied to Directed Acyclic Graph (DAG)-based protocols that integrate expressive smart contract processing. Current solutions predominantly rely on coordination mechanisms like 2PC and require transaction read/write sets to optimize parallel execution. These requirements introduce two fundamental limitations: 1) additional coordination phases incur latency overhead, and 2) pre-declaration of read/write sets proves impractical for Turing-complete smart contracts with dynamic access patterns. This paper presents Thunderbolt, a novel sharding architecture for both single-shard transactions (Single-shard TXs) and cross-shard transactions (Cross-shard TXs) and enables nonblocking reconfiguration to ensure system liveness. Our design introduces 4 key innovations: 1) each replica serves dual roles as a full-shard representative and transaction proposer, employing the Execution-Order-Validation (EOV) model for Single-shard TXs and Order-Execution (OE) model for Cross-shard TXs. 2) we develop a DAG-based coordination protocol that establishes deterministic ordering between two transaction types while preserving concurrent execution capabilities. 3) we implement a dynamic concurrency controller that schedules Single-shard TXs without requiring prior knowledge of read/write sets, enabling runtime dependency resolution. 4) Thunderbolt introduces a nonblocking shard reconfiguration mechanism to address censorship attacks by featuring frequent shard re-assignment without impeding the construction of DAG nor blocking consensus. Thunderbolt achieves a 50x throughput improvement with 64 replicas compared to serial execution in the Tusk framework.
Treballs Finals de Grau de Matemàtiques, Facultat de Matemàtiques, Universitat de Barcelona, Any: 2024, Director: Bruno Mazorra i Luis Victor Dieulefait
The recent MIP*=RE theorem of Ji, Natarajan, Vidick, Wright, and Yuen shows that the complexity class MIP* of multiprover proof systems with entangled provers contains all recursively enumerable languages. Prior work of Grilo, Slofstra, and Yuen [FOCS '19] further shows (via a technique called simulatable codes) that every language in MIP* has a perfect zero knowledge (PZK) MIP* protocol. The MIP*=RE theorem uses two-prover one-round proof systems, and hence such systems are complete for MIP*. However, the construction in Grilo, Slofstra, and Yuen uses six provers, and there is no obvious way to get perfect zero knowledge with two provers via simulatable codes. This leads to a natural question: are there two-prover PZK-MIP* protocols for all of MIP*? In this paper, we show that every language in MIP* has a two-prover one-round PZK-MIP* protocol, answering the question in the affirmative. For the proof, we use a new method based on a key consequence of the MIP*=RE theorem, which is that every MIP* protocol can be turned into a family of boolean constraint system (BCS) nonlocal games. This makes it possible to work with MIP* protocols as boolean constraint systems, and in particular allows us to use a variant of a construction due to Dwork, Feige, Kilian, Naor, and Safra [Crypto '92] which gives a classical MIP protocol for 3SAT with perfect zero knowledge. To show quantum soundness of this classical construction, we develop a toolkit for analyzing quantum soundness of reductions between BCS games, which we expect to be useful more broadly. This toolkit also applies to commuting operator strategies, and our argument shows that every language with a commuting operator BCS protocol has a two prover PZK commuting operator protocol.
A growing number of products use layer 2 solutions to expand the capabilities of primary blockchains like Ethereum, where computation is off-loaded from the root chain, and the results are published to it in bulk. Those include optimistic and zero-knowledge rollups, information oracles, and app-specific chains. This work presents an analysis of layer 2 blockchain strategies determining the optimal times for publishing transactions on the root chain. There is a trade-off between waiting for a better layer 1 gas price and the urgency to finalize layer 2 transactions. We present a model for the problem that captures this trade-off, generalizing previous works, and we analyze the properties of optimal publishing strategies. We show that such optimal strategies hold a computable simple form for a large class of cost functions.
The Algorand consensus protocol is interesting both in theory and in practice. On the theoretical side, to achieve adaptive security, it introduces the novel idea of player replaceability, where each step of the protocol is executed by a different randomly selected committee whose members remain secret until they send their first and only message. The protocol provides consistency under arbitrary network conditions and liveness under intermittent network partitions. On the practical side, the protocol is used to secure the Algorand cryptocurrency, whose total value is approximately 850M at the time of writing.
The increasing use of artificial intelligence algorithms, smart contracts, the internet of things, cryptocurrencies, and digital money highlights the need for secure and sustainable decentralized solutions. Currently, the blockchain technology serves as the backbone for most decentralized systems. However, the question of axiomatization of the blockchain theory in the first-order logic has been open until today, despite the efficient computational implementations of these systems. This did not allow one to formalize the blockchain structure, as well as to model and verify it using logical methods. This work introduces a finitely axiomatizable blockchain theory T that defines a class of blockchain structures K using the axioms of the first-order logic. The models of the theory T are well-known blockchain implementations with the proof of work consensus algorithm, including Bitcoin, Ethereum (PoW version), Ethereum Classic, and some others. By utilizing mathematical logic, we can study these models and derive new theorems of the theory T through automatic proofs. Also, the axiomatization of blockchain opens up new opportunities to develop blockchain-based systems that can help solve some of the open problems in the fields of artificial intelligence, robotics, cryptocurrencies, etc.
John Bostanci, Yuval Efron, Tony Metger, Alexander Poremba · 6 authors
State transformation problems such as compressing quantum information or breaking quantum commitments are fundamental quantum tasks. However, their computational difficulty cannot easily be characterized using traditional complexity theory, which focuses on tasks with classical inputs and outputs. To study the complexity of such state transformation tasks, we introduce a framework for unitary synthesis problems, including notions of reductions and unitary complexity classes. We use this framework to study the complexity of transforming one entangled state into another via local operations. We formalize this as the Uhlmann Transformation Problem, an algorithmic version of Uhlmann's theorem. Then, we prove structural results relating the complexity of the Uhlmann Transformation Problem, polynomial space quantum computation, and zero knowledge protocols. The Uhlmann Transformation Problem allows us to characterize the complexity of a variety of tasks in quantum information processing, including decoding noisy quantum channels, breaking falsifiable quantum cryptographic assumptions, implementing optimal prover strategies in quantum interactive proofs, and decoding the Hawking radiation of black holes. Our framework for unitary complexity thus provides new avenues for studying the computational complexity of many natural quantum information processing tasks.
In this paper, we propose a physical protocol to verify the first nonzero term of a sequence using a deck of cards. The protocol lets a prover show the value of the first nonzero term of a given sequence to a verifier without revealing which term it is. Our protocol uses $Θ(1)$ shuffles, which is asymptotically lower than that of an existing protocol of Fukusawa and Manabe which uses $Θ(n)$ shuffles, where $n$ is the length of the sequence. We also apply our protocol to construct zero-knowledge proof protocols for three well-known logic puzzles: ABC End View, Goishi Hiroi, and Toichika. These protocols enables a prover to physically show that he/she know solutions of the puzzles without revealing them.