We exploit the idea of [Fen22] which proposes to build an efficient signature scheme based on a zero-knowledge proof of knowledge of a solution of a MinRank instance. The scheme uses the MPCitH paradigm, which is an efficient way to build ZK proofs. We combine this idea with another idea, the hypercube technique introduced in [AMGH+22], which leads to more efficient MPCitH-based scheme. This new approach is more efficient than classical MPCitH, as it allows to reduce the number of party computation. This gives us a first scheme called MIRA-Additive. We then present an other scheme, based on low-threshold secret sharings, called MIRA-Threshold, which is a faster scheme, at the price of larger signatures. The construction of MPCitH using threshold secret sharing is detailed in [FR22]. These two constructions allows us to be faster than classical MPCitH, with a size of signature around 5.6kB with MIRA-Additive, and 8.3kB with MIRA-Threshold. We detail here the constructions and optimizations of the schemes, as well as their security proofs.
Adel Alahmadi, Selda Çalkavur, Patrick Solé, Abdul Nadim Khan · 6 authors
Blockchain is a method of recording information that makes it not feasible for the system to be replaced, attacked, or manipulated. A blockchain is equipped with a notebook that copies and processes the various procedures across the network of computers participating in the blockchain. Digital signature algorithm is one of the cryptographic protocols used by the blockchain. In this work, we introduce a new digital signature scheme based on error correcting codes. In the scheme constructed on a [n, k, d]− code over 𝔽q, which is d ≥ 2t + 1, and the size of the signature length is n − k. The signature verification is based on the bounded distance decoding of the code. Since the verification space is 𝔽qn, the proposed scheme has an improved performance in terms of working in a wider space.
Identity-based cryptography (IBC) can be applied to scenarios that involve a large number of public keys in each execution. In this paper, we propose an efficient identity-based ring signature scheme on lattices with signature size logarithmic to the cardinality of the ring. To this end, we first construct an efficient identity-based ring identification scheme by combining preimage sampling algorithms and a zero-knowledge proof system for a tree-based accumulator. Then we apply the Fiat-Shamir transformation and obtain a secure identity-based ring signature scheme. We prove its security in the random oracle model under the small integer solution assumption.
Marco Radovancovici, Darius Galiş, Ciprian Pungilă
In this paper we perform a practical analysis of techniques for minting genetic information, in particular genomic data, as non-fungible tokens (NFTs) in supporting blockchains, and perform a wide-range analysis of the best and most efficient tools to ensure such data’s privacy, non-repudiation and storage efficiency. We analyze the demands of the NFT-driven blockchain ecosystem today, and discuss how we can apply common approaches in storing and accessing genomic data, such as compression methods and encryption techniques for it, to the NFT world. We perform a practical experiment of our assessment, and compare the publicly available tools and libraries for achieving the aforementioned goal, in order to determine which one provides the best results in terms of speed and storage efficiency, and draw relevant conclusions as to which approach is more beneficial to NFT-driven ecosystems where genomic data could be safely preserved and actively traded.
Makaro is a logic puzzle with an objective to fill numbers into a rectangular grid to satisfy certain conditions. In 2018, Bultel et al. developed a physical zero-knowledge proof (ZKP) protocol for Makaro using a deck of cards, which allows a prover to physically convince a verifier that he/she knows a solution of the puzzle without revealing it. However, their protocol requires several identical copies of some cards, making it impractical as a deck of playing cards found in everyday life typically consists of all different cards. In this paper, we propose a new ZKP protocol for Makaro that can be implemented using a standard deck (a deck consisting of all different cards). Our protocol also uses asymptotically less cards than the protocol of Bultel et al. Most importantly, we develop a general method to encode a number with a sequence of all different cards. This allows us to securely compute several numerical functions using a standard deck, such as verifying that two given numbers are different and verifying that a number is the largest one among the given numbers.
A random beacon provides a continuous public source of randomness and its applications range from public lotteries to zero-knowledge proofs. Existing random beacon protocols sacrifice either the fault tolerance or the communication complexity for security, or ease of reconfigurability. This work overcomes the challenges with the existing works through a novel communication efficient combination of state machine replication and (Publicly) Verifiable Secret Sharing (PVSS/VSS).
Classical cryptography has been around for a long time in the documented human history, but most classical ciphers were broken and even solved by hand. Shannon introduced the notion of perfect secrecy that formally defines confidentiality in the information-theoretic sense, which is only possible in the restricted scenarios where the message is no longer than the encryption key. The invention of public-key cryptography (the Diffie-Hellman key exchange protocol in 1976 and the RSA crypto-system in 1977) marks the birth of modern cryptography, allowing parties to exchange messages securely without sharing any secrets in advance. Furthermore, it provides computational security based on the conjectured hardness of mathematical problems such as factorization and the discrete logarithm. Public-key cryptography has found numerous applications in the Internet, financial and banking industry, and blockchains, and it plays a crucial role in protecting information security and asset safety. Unfortunately, in the 1990s, Shor proposed efficient quantum algorithms that solve number-theoretic problems, including factorization and discrete logarithms in polynomial time. Once a quantum computer of a particular scale becomes a reality, it will cause a devastating blow to the existing public-key infrastructure. To deal with such a ‘quantum crisis’, academia and industry are looking into the design, analysis and standardization of cryptographic algorithms that can resist quantum computers referred to as post-quantum cryptography (PQC). The National Institute of Standards and Technology (NIST) has been soliciting proposals for the post-quantum public-key algorithms since 2016. More recently, the Chinese Association for Cryptologic Research (CACR) held a competition on designing cryptographic algorithms whose public-key cryptography track focused on post-quantum cryptographic algorithms. Lattice-based cryptography is considered by most to be the mainstream technical route of post-quantum cryptography, which is reflected in the number of proposals (and their percentage of the total) received in the NIST PQC process. To reflect the status quo of post-quantum cryptography, we invite leading experts in this area to contribute three technical perspectives that aim to help readers understand the algorithms, the underlying basic techniques and different technical routes to achieve quantum resistance. The first perspective, presented by Lu and Zhang, introduces public-key cryptographic algorithms whose quantum security is reducible from the conjectured quantum hardness of lattice problems. In particular, they mainly focus on public-key encryption (PKE) and the key encapsulation mechanism (KEM), which are essential building blocks for securing the confidentiality of communication without pre-shared secrets. Both types of crypto-systems are solicited by the NIST PQC standardization and the CACR algorithm design competition. This perspective gives a comprehensive survey on practical lattice-based PKEs/KEMs, and their best-known quantum and classical attacks. Another important post-quantum crypto-system is digital signature, which ensures that three goals of information security are met other than confidentiality, namely, integrity, authentication and non-repudiation. The second perspective is on lattice-based signature by Lyubashevsky. In this perspective, he surveys different techniques in building lattice-based post-quantum crypto-systems, discusses the challenges in overcoming performance issues and gives us state-of-the-art digital signature schemes. In addition to ensuring the ‘static’ security of information in storage and transmission, advanced cryptographic algorithms and protocols can guarantee information security during the computation process (possibly among multiple parties), referred to as privacy-preserving computation. Cryptographic techniques involved in privacy-preserving computation include secure multi-party computation, zero-knowledge proof and fully homomorphic encryption. There is a pressing need to migrate them to the post-quantum era. The third perspective, by Yu and Xie, presents practical instantiations of these algorithms and discusses possible ways to migrate them to their quantum-resistant counterparts. To summarize, post-quantum cryptography has received widespread attention and made significant progress in recent years. Some post-quantum cryptographic algorithms, such as the lattice-based candidate, also have other advantages (e.g., computational efficiency and full homomorphism) over their classical counterparts. Lattice-based cryptography is an emerging field with high theoretical value and wide application, and we encourage young researchers to enter and explore this new and exciting field.
In addition to their usefulness in proving one’s identity electronically, identification protocols based on zero-knowledge proofs allow designing secure cryptographic signature schemes by means of the Fiat–Shamir transform or other similar constructs. This approach has been followed by many cryptographers during the NIST (National Institute of Standards and Technology) standardization process for quantum-resistant signature schemes. NIST candidates include solutions in different settings, such as lattices and multivariate and multiparty computation. While error-correcting codes may also be used, they do not provide very practical parameters, with a few exceptions. In this manuscript, we explored the possibility of using the error-correcting codes proposed by Stakhov in 2006 to design an identification protocol based on zero-knowledge proofs. We showed that this type of code offers a valid alternative in the error-correcting code setting to build such protocols and, consequently, quantum-resistant signature schemes.
Mit Bitcoin wurde 2008 die erste Kryptowährung veröffentlicht. Mit ihr können Zahlungen getätigt werden, ohne einer zentralen Stelle wie einer Bank vertrauen zu müssen. Dies wird durch einen innovativen Konsensus-Mechanismus ermöglicht, der unter der Bezeichnung Proof-of-Work bekannt ist. Bitcoin ist noch immer die bekannteste und wertvollste Kryptowährung. Über die Jahre sind jedoch einige Probleme offenkundig geworden, wie z.B. der hohe Energieverbrauch und der niedriger Transaktionsdurchsatz. Um das Jahr 2016 kam eine neue Art von Protokollen auf, welche versprach diese beiden Probleme gleichzeitig zu lösen. Diese Protokolle basieren auf dem Proof-of-Stake (PoS) Mechanismus und verwenden gerichtete azyklische Graphen als Datenstruktur. Da es sich hier ebenfalls um Währungen handelt, spielt Sicherheit eine zentrale Rolle. Dies wirft die Frage auf, wie sicher Protokolle dieser Art wirklich sind. Diese Arbeit trägt zur Beantwortung bei, indem Hashgraph im Detail analysiert wird. Hashgraph ist ein vielversprechender Vertreter dieser Protokollart. Die verschiedensten Sicherheits- und Performanceangaben des Protokolls werden mithilfen eines im Zuge der Arbeit entwickelten und veröffentlichten Simulators überprüft. Der Simulator ermöglicht es, das Verhalten des Protokolls unter vier verschiedenen (Angriffs-)Szenarien zu untersuchen. Er bietet dazu umfangreiche Konfigurationsmöglichkeiten an, welche unzählige verschiedene Verläufe ermöglichen. Akteure/Akteurinnen agieren zufällig basierend auf einem veränderbaren Parameter, der Reproduzierbarkeit gewährleistet. Der Simulator selbst verfügt außerdem über eine grafische Benutzerobefläche, wobei Ergebnisse auch als Text-Dateien für weitere Analysen exportiert werden können. In keiner einzigen von tausenden Simulationen wurde der Konsensus-Mechanismus von Hashgraph gebrochen. Basierend auf der Tatsache das Nachrichten zur Synchronsiation beliebig schnell und an beliebige andere Knoten gesendet werden können, kamen jedoch Schwachstellen zu Tage. Diese Arbeit zeigt auf, dass es möglich ist eine widersprüchliche Transaktion zu einer bereits existierenden zu veröffentlichen und diese schneller bestätigt zu bekommen. Weiters wird belohnt, wer Synchronisationen zuerst mit ganz bestimmten Knoten durchführt, was zu einer Überlastung dieser Knoten führen kann. Die präsentierten Ergebnisse zeigen, dass diese Protokollklasse tatsächlich das Potential besitzt, zwei der grundelegenden Probleme von traditionellen Kryptowährungen zu lösen. Die Möglichkeit von Nachrichten-Spam im System kann dies jedoch zunichte machen und ist ein wichtiger Punkt in der Bewertung solcher Protokolle.
Sudoku is a famous logic puzzle where the player has to fill a number between 1 and 9 into each empty cell of a $9 \times 9$ grid such that every number appears exactly once in each row, each column, and each $3 \times 3$ block. In 2020, Sasaki et al. developed a physical card-based protocol of zero-knowledge proof (ZKP) for Sudoku, which enables a prover to convince a verifier that he/she knows a solution of the puzzle without revealing it. Their protocol uses 90 cards, but requires nine identical copies of some cards, which cannot be found in a standard deck of playing cards (consisting of 52 different cards and two jokers). Hence, nine identical standard decks are required to perform that protocol, making the protocol not very practical. In this paper, we propose a new ZKP protocol for Sudoku that can be performed using only two standard decks of playing cards, regardless of whether the two decks are identical or different. In general, we also develop the first ZKP protocol for a generalized $n \times n$ Sudoku that can be performed using a deck of all different cards.
Javier Herranz, Ramiro Pinilla, Manuel Sánchez-Raya
In an electronic voting procedure, mixing networks are used to ensure anonymity of the casted votes. Each node of the network re-encrypts the input list of ciphertexts and randomly permutes it in a process named shuffle, and must prove (in zero-knowledge) that the process was applied honestly. To maintain security of such a process in a post-quantum scenario, new proofs are based on different mathematical assumptions, such as lattice-based problems. Nonetheless, the best lattice-based protocols to ensure verifiable shuffling have linear communication complexity on N, the number of shuffled ciphertexts.
R. Indrakumari, T. Poongodi, Kavita Saini, B. Balamurugan
A blockchain is a cryptographically signed transactional record shared by the participating nodes in the network. Each record has a timestamp and link to earlier transactions, and it is a predominant architectural design of the distributed ledger concept. The authorized participant with proper access rights can track the history of transactional events belonging to any participant. However, a significant disconnect occurs between the expectation in the market sector and reality. Blockchain consensus protocols assure that the nodes in the network will be synchronized with each other. Consensus means the nodes in the blockchain network will agree on the same state for self-auditing across a distributed network. The main objective of the consensus protocol is to ensure a single chain is utilized and followed, and it is one of the significant revolutionary aspects of blockchain technology. Achieving consensus is an acceptance among nodes on the network for a data value even if some nodes are unreliable. The cryptocurrency must be secured against attacks in the blockchain, and it does not rely on a single centralized authority for security, where the users do not have any prior knowledge about the versions of the valid record. According to Gartner report, there will be an exponential growth of blockchain by 2020 due to the implementation of the smart contract which includes tokenization and decentralization. Furlonger said, “Blockchain is not just a technology, it is a societal change”. Consensus protocols provide rewards and incentives for the participants who are maintaining the blockchain. The rewards in blockchain will be in the form of tokens or cryptocurrencies, and the competition for confirming the next block in the chain is extremely high. The complete history of transaction is maintained in digital currencies to check the user’s balance at any time. Some of the significant objectives of blockchain consensus models are in achieving agreement, cooperation, collaboration, participation and activity. The different types of consensus algorithms are proof of work (PoW), proof of stake (PoS), delegated proof of stake (DPoS), leased proof of stake (LPoS), proof of elapsed time (PoET), practical Byzantine fault tolerance (PBFT), simplified Byzantine fault tolerance (SBFT), delegated Byzantine fault tolerance (DBFT), directed acyclic graphs (DAG), proof of activity (PoA), proof of importance (PoI), proof of capacity (PoC), proof of burn (PoB) and proof of weight (PoWeight). This chapter highlights the significance of consensus algorithms and their usage.
The protocol for cryptocurrencies can be divided into three parts, namely consensus, wallet, and networking overlay. The aim of the consensus part is to bring trustless rational peer-to-peer nodes to an agreement to the current status of the blockchain. The status must be updated through valid transactions. A proof-of-work (PoW) based consensus mechanism has been proven to be secure and robust owing to its simple rule and has served as a firm foundation for cryptocurrencies such as Bitcoin and Ethereum. Specialized mining devices have emerged, as rational miners aim to maximize profit, and caused two problems: i) the re-centralization of a mining market and ii) the huge energy spending in mining. In this paper, we aim to propose a new PoW called Error-Correction Codes PoW (ECCPoW) where the error-correction codes and their decoder can be utilized for PoW. In ECCPoW, puzzles can be intentionally generated to vary from block to block, leading to a time-variant puzzle generation mechanism. This mechanism is useful in repressing the emergence of the specialized mining devices. It can serve as a solution to the two problems of recentralization and energy spending.
Numberlink is a logic puzzle for which the player has to connect all pairs of cells with the same numbers by non-crossing paths in a rectangular grid. In this paper, we propose a physical protocol of zero-knowledge proof for Numberlink using a deck of cards, which allows a player to physically show that he/she knows a solution without revealing it. In particular, we develop a physical protocol to count the number of elements in a list that are equal to a given secret value without revealing that value, the positions of elements in the list that are equal to it, or the value of any other element in the list. Our protocol can also be applied to verify the existence of vertex-disjoint paths connecting all given pairs of endpoints in any undirected graph.
Mikael Beyene, Kannengießer, Niclas, Pandl, Konstantin D, Thiebes, Scott · 5 authors
A concept for distributed gene-drug interaction data sharing based on Ethereum Smart Contracts. The data is stored in a map with, both, keys and values utilizing a mixed-radix integer encoding that relies on the finiteness of the domains of given genes, drugs, and interactions. Thus, we get random access and, further, data queries are reduced to cheap bit comparisons.
Open access
Innovative Microfluidic and Catalytic Techniques Innovation