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.
In our day to day life, information security is a predominant topic. More specifically, (online) users expect to be asked for consent and that service providers handle their personal data with care and integrity. This urges the design of systems enforcing such expectations. The field of cryptography provides such powerful privacy-preserving tools. In this thesis, we consider one of those tools: pairings over elliptic curves. We strongly diverge from the general approach, i.e. taking already standardized curves regardless of the cryptographic protocol, and suggest curves satisfying chosen criteria. The given curves in this thesis have more efficient operations in the first pairing group than the curves from the literature. We follow by giving a group signature scheme, a primitive enabling the anonymity of its users among the group they belong to, designed using pairing over elliptic curves. This group signature is efficient when compared to the state-of-the-art, thanks to the very nice interaction between two randomizable signature schemes, allowing us to get rid of costly zero-knowledge proofs.