Blockchain Papers

Carlos Aguilar-Melchor, Nicolas Gama, James Howe, Andreas Hülsing · 6 authors

No abstract is available for this record.

Andrea Basso, Giulio Codogni, Deirdre Connolly, Luca De Feo · 10 authors

No abstract is available for this record.

Clémence Bouvier, Anne Canteaut, Léo Perrin

No abstract is available for this record.

Thibauld Feneuil, Antoine Joux, Matthieu Rivain

No abstract is available for this record.

Augustin Bariant, Clémence Bouvier, Gaëtan Leurent, Léo Perrin

Recent advanced Zero-Knowledge protocols, along with other high-level constructions such as Multi-Party Computations (MPC), have highlighted the need for a new type of symmetric primitives that are not optimized for speed on the usual platforms (desktop computers, servers, microcontrollers, RFID tags...), but for their ability to be implemented using arithmetic circuits.Several primitives have already been proposed to satisfy this need. In order to enable an efficient arithmetization, they operate over large finite fields, and use round functions that can be modelled using low degree equations. The impact of these properties on their security remains to be completely assessed. In particular, algebraic attacks relying on polynomial root-finding become extremely relevant. Such attacks work by writing the cryptanalysis as systems of polynomial equations over the large field, and solving them with off-the-shelf tools (SageMath, NTL, Magma, . . . ).The need for further analysis of these new designs has been recently highlighted by the Ethereum Foundation, as it issued bounties for successful attacks against round-reduced versions of several of them.In this paper, we show that the security analysis performed by the designers (or challenge authors) of four such primitives is too optimistic, and that it is possible to improve algebraic attacks using insights gathered from a careful study of the round function.First, we show that univariate polynomial root-finding can be of great relevance n practice, as it allows us to solve many of the Ethereum Foundation’s challenges on Feistel–MiMC. Second, we introduce a trick to essentially shave off two full rounds at little to no cost for Substitution-Permutation Networks (SPN). This can be combined with univariate (resp. multivariate) root-finding, which allowed to solve some challenges for Poseidon (resp. Rescue–Prime). Finally, we also find an alternative way to set up a system of equations to attack Ciminion, leading to much faster attacks than expected by the designers.

Lorenzo Grassi, Silvia Onofri, Marco Pedicini, Luca Sozzi

Motivated by new applications such as secure Multi-Party Computation (MPC), Fully Homomorphic Encryption (FHE), and Zero-Knowledge proofs (ZK), many MPC-, FHE- and ZK-friendly symmetric-key primitives that minimize the number of multiplications over Fp for a large prime p have been recently proposed in the literature. This goal is often achieved by instantiating the non-linear layer via power maps x↦xd. In this paper, we start an analysis of new non-linear permutation functions over Fnp that can be used as building blocks in such symmetrickey primitives. Given a local map F : Fmp→ Fp, we limit ourselves to focus on S-Boxes over Fnp for n ≥ m defined as SF (x0, x1, . . . , xn−1) = y0|y1| . . . |yn−1 where yi := F(xi, xi+1, . . . , xi+m−1). As main results, we prove that• given any quadratic function F : F2p→ Fp, the corresponding S-Box SF over Fnp for n ≥ 3 is never invertible;• similarly, given any quadratic function F : F3p → Fp, the corresponding S-Box SF over Fnp for n ≥ 5 is never invertible.Moreover, for each p ≥ 3, we present (1st) generalizations of the Lai-Massey construction over Fnp defined as before via functions F : Fmp → Fp for each n = m ≥ 2 and (2nd) (non-trivial) quadratic functions F : F3p → Fp such that SF over Fnp for n ∈ {3, 4} is invertible. As an open problem for future work, we conjecture that for each m ≥ 1 there exists a finite integer nmax(m) such that SF over Fnp defined as before via a quadratic function F : Fmp →Fp is not invertible for each n ≥ nmax(m). Finally, as a concrete application, we propose Neptune, a variant of the sponge hash function Poseidon, whose non-linear layer is designed by taking into account the results presented in this paper. We show that this variant leads to a concrete multiplication reduction with respect to Poseidon.

Arnab Roy, Matthias Steiner

In recent years a new class of symmetric-key primitives over $\mathbb{F}_p$ that are essential to Multi-Party Computation and Zero-Knowledge Proofs based protocols have emerged. Towards improving the efficiency of such primitives, a number of new block ciphers and hash functions over $\mathbb{F}_p$ were proposed. These new primitives also showed that following alternative design strategies to the classical Substitution-Permutation Network (SPN) and Feistel Networks leads to more efficient cipher and hash function designs over $\mathbb{F}_p$ specifically for large odd primes $p$. In view of these efforts, in this work we build an \emph{algebraic framework} that allows the systematic exploration of viable and efficient design strategies for constructing symmetric-key (iterative) permutations over $\mathbb{F}_p$. We first identify iterative polynomial dynamical systems over finite fields as the central building block of almost all block cipher design strategies. We propose a generalized triangular polynomial dynamical system (GTDS), and based on the GTDS we provide a generic definition of an iterative (keyed) permutation over $\mathbb{F}_p^n$. Our GTDS-based generic definition is able to describe the three most well-known design strategies, namely SPNs, Feistel networks and Lai--Massey. Consequently, the block ciphers that are constructed following these design strategies can also be instantiated from our generic definition. Moreover, we find that the recently proposed \texttt{Griffin} design, which neither follows the Feistel nor the SPN design, can be described using the generic GTDS-based definition. We also show that a new generalized Lai--Massey construction can be instantiated from the GTDS-based definition. We further provide generic analysis of the GTDS including an upper bound on the differential uniformity and the correlation.

Shay Gueron, Edoardo Persichetti, Paolo Santini

This paper defines a new practical construction for a code-based signature scheme. We introduce a new protocol that is designed to follow the recent paradigm known as “Sigma protocol with helper”, and prove that the protocol’s security reduces directly to the Syndrome Decoding Problem. The protocol is then converted to a full-fledged signature scheme via a sequence of generic steps that include: removing the role of the helper; incorporating a variety of protocol optimizations (using e.g., Merkle trees); applying the Fiat–Shamir transformation. The resulting signature scheme is EUF-CMA secure in the QROM, with the following advantages: (a) Security relies on only minimal assumptions and is backed by a long-studied NP-complete problem; (b) the trusted setup structure allows for obtaining an arbitrarily small soundness error. This minimizes the required number of repetitions, thus alleviating a major bottleneck associated with Fiat–Shamir schemes. We outline an initial performance estimation to confirm that our scheme is competitive with respect to existing solutions of similar type.

Augustin Bariant, Clémence Bouvier, Gaëtan Leurent, Léo Perrin

Several challenges have been announced on arithmetization-oriented hash functions, with bounties funded by the Ethereum Foundation. In this note, we report on our work to solve several of these challenges, on Feistel-MiMC, Rescue Prime and Poseidon. Our results are obtained by writing the challenges as systems of polynomial equations over the large field, and solving them with off-the-shelf tools (SageMath, NTL, Magma).

Alexei Petrenko, Sergei Petrenko

Abstract Purpose of work is the development of a new method for estimating the quantum resilience of modern blockchain platforms based on the effective solution of cryptanalysis problems for asymmetric encryption schemes (RSA, El-Gamal) and digital signature (DSA, ECDSA or RSA-PSS), based on computationally difficult problems of factorization and discrete logarithm. Research method is the use of quantum algorithms providing exponential gain (eg Shor’s algorithm) and quadratic gain (eg Grover’s algorithm). Due to the fact that the class of problems solved by quantum algorithms in polynomial time cannot yet be significantly expanded, more attention is paid to cryptanalysis based on the quantum Shor algorithm and other polynomial algorithms. Results of the study include a classification of well-known algorithms and software packages for cryptanalysis of asymmetric encryption schemes (RSA, El-Gamal) and digital signature (DSA, ECDSA or RSA-PSS) based on computationally difficult problems of factorization and discrete logarithm has been built. A promising method for solving problems of cryptanalysis of asymmetric encryption schemes (RSA, ElGamal) and digital signature (DSA, ECDSA or RSA-PSS) of known blockchain platforms in polynomial time in a quantum computing model is proposed. Algorithms for solving problems of quantum cryptanalysis of two-key cryptography schemes of known blockchain platforms in polynomial time are developed, taking into account the security of the discrete algorithm (DLP) and the discrete elliptic curve algorithm (ECDLP). A structural and functional diagram of the software package for quantum cryptanalysis of modern blockchain platforms “Kvant-K”, adapted to work in a hybrid computing environment of the IBM Q quantum computer (20 and 100 qubits) and the IBM BladeCenter (2022) supercomputer, has been designed. A methodology has been developed for using the “Kvant-K” software package to assess the quantum stability of blockchain platforms: InnoChain (Innopolis University), Waves Enterprise (Waves, Vostok), Hyperledger Fabric (Linux, IBM), Corda Enterprise, Bitfury Exonum, Blockchain Industrial Alliance, Exonum (Bitfury CIS), NodesPlus (b41), Masterchain (Sberbank), Microsoft Azure Blockchain, Enterprise Ethereum Alliance, etc. Practical relevance: The developed new solution for computationally difficult problems of factorization and discrete logarithm, given over finite commutative (and non-commutative) associative algebras, in a quantum model of computing in polynomial time. It is essential that the obtained scientific results formed the basis for the development of the corresponding software and hardware complex “Kvant-K”, which was tested in a hybrid computing environment (quantum computer IBM Q (20 and 100 qubits) and/or 5th generation supercomputer: IBM BladeCenter (2022), RCS based on FPGA Virtex UltraScale (2020), RFNC-VNIIEF (2022) and SKIF P-0.5 (2021). An appropriate method for estimating the quantum stability of these blockchain platforms based on the author’s models, methods and algorithms of quantum cryptanalysis has been developed and tested. Keywords: blockchain and distributed ledger technologies (DLT), SMART contracts, blockchain security threat model, quantum security threat, cryptographic attacks, quantum cryptanalysis, quantum and post-quantum cryptography, quantum algorithms Shor, Grover and Simon algorithms, quantum Fourier transform, factorization and discrete logarithm problem, post-quantum cryptography, quantum resilience of blockchain platforms.

Jiamin Cui, Kai Hu, Meiqin Wang, Puwen Wei

No abstract is available for this record.

Sudheer Chava, Fred Hu, Nikhil Paradkar

Abstract We proxy retail investor attention through Google Trends and find that fungible and non-fungible crypto tokens generate greater attention from high-gambling propensity regions. Crypto attention is higher during bubble-like episodes in the crypto market and for more lottery-like tokens. Moreover, retail crypto attention decreases after sports gambling is legalized. Higher token attention is associated with more contributors and higher fundraising. However, consumer credit default rates spike after periods of high crypto attention, but solely in the subprime segment. Overall, our findings suggest that gambling preferences strongly predict retail investor interest in the crypto market.

Thibauld Feneuil, Antoine Joux, Matthieu Rivain

No abstract is available for this record.

Nicolas Magaud

We study how to formalize in the Coq proof assistant the smallest projective space PG(3,2). We then describe formally the spreads and packings of PG(3,2), as well as some of their properties. The formalization is rather straightforward, however as the number of objects at stake increases rapidly, we need to exploit some symmetry arguments as well as smart proof techniques to make proof search and verification faster and thus tractable using the Coq proof assistant. This work can be viewed as a first step towards formalizing projective spaces of higher dimension, e.g. PG(4,2), or larger order, e.g. PG(3,3).

Yeow Meng Chee, Tuvi Etzion, Han Mao Kiah, Alexander Vardy

<p style='text-indent:20px;'>The Hamming ball of radius <inline-formula><tex-math id="M1">\begin{document}$ w $\end{document}</tex-math></inline-formula> in <inline-formula><tex-math id="M2">\begin{document}$ \{0,1\}^n $\end{document}</tex-math></inline-formula> is the set <inline-formula><tex-math id="M3">\begin{document}$ \mathcal{B}(n,w) $\end{document}</tex-math></inline-formula> of all binary words of length <inline-formula><tex-math id="M4">\begin{document}$ n $\end{document}</tex-math></inline-formula> and Hamming weight at most <inline-formula><tex-math id="M5">\begin{document}$ w $\end{document}</tex-math></inline-formula>. We consider injective mappings <inline-formula><tex-math id="M6">\begin{document}$ \varphi : \{0,1\}^m \to \mathcal{B}(n,w) $\end{document}</tex-math></inline-formula> with the following <i>domination property:</i> every position <inline-formula><tex-math id="M7">\begin{document}$ j \in [n] $\end{document}</tex-math></inline-formula> is dominated by some position <inline-formula><tex-math id="M8">\begin{document}$ i \in [m] $\end{document}</tex-math></inline-formula>, in the sense that if position <inline-formula><tex-math id="M9">\begin{document}$ i $\end{document}</tex-math></inline-formula> in <inline-formula><tex-math id="M10">\begin{document}$ {\mathit{\boldsymbol{x}}} \in \{0,1\}^m $\end{document}</tex-math></inline-formula> is "switched off" (equal <i>zero</i>), then necessarily position <inline-formula><tex-math id="M11">\begin{document}$ j $\end{document}</tex-math></inline-formula> in its image <inline-formula><tex-math id="M12">\begin{document}$ \varphi({\mathit{\boldsymbol{x}}}) $\end{document}</tex-math></inline-formula> is switched off. This property may be described more precisely in terms of a bipartite <i>domination graph</i> <inline-formula><tex-math id="M13">\begin{document}$ G = \bigl([m] \cup [n], E\bigr) $\end{document}</tex-math></inline-formula> with no isolated vertices; for all <inline-formula><tex-math id="M14">\begin{document}$ (i,j) \in E $\end{document}</tex-math></inline-formula> and all <inline-formula><tex-math id="M15">\begin{document}$ {\mathit{\boldsymbol{x}}}\in \{0,1\}^m $\end{document}</tex-math></inline-formula>, we require that <inline-formula><tex-math id="M16">\begin{document}$ x_i = 0 $\end{document}</tex-math></inline-formula> implies <inline-formula><tex-math id="M17">\begin{document}$ y_j = 0 $\end{document}</tex-math></inline-formula>, where <inline-formula><tex-math id="M18">\begin{document}$ {\mathit{\boldsymbol{y}}} = \varphi({\mathit{\boldsymbol{x}}}) $\end{document}</tex-math></inline-formula>. Although such domination mappings recently found applications in the context of coding for high-performance interconnects, to the best of our knowledge, they were not previously studied. The concept of domination mapping is thus interesting from both practical and combinatorial points of view. <p style='text-indent:20px;'>In this paper, we begin with simple necessary conditions for the existence of an <i><inline-formula><tex-math id="M19">\begin{document}$ (m,n,w) $\end{document}</tex-math></inline-formula>-domination mapping <inline-formula><tex-math id="M20">\begin{document}$ \varphi : \{0,1\}^m \to \mathcal{B}(n,w) $\end{document}</tex-math></inline-formula></i>. We then provide several explicit constructions of such mappings, which show that the necessary conditions are also sufficient when <inline-formula><tex-math id="M21">\begin{document}$ w = 1 $\end{document}</tex-math></inline-formula>, when <inline-formula><tex-math id="M22">\begin{document}$ w = 2 $\end{document}</tex-math></inline-formula> and <inline-formula><tex-math id="M23">\begin{document}$ m $\end{document}</tex-math></inline-formula> is odd, or when <inline-formula><tex-math id="M24">\begin{document}$ m \leqslant 3w $\end{document}</tex-math></inline-formula>. One of our main results herein is a proof that the trivial necessary condition <inline-formula><tex-math id="M25">\begin{document}$ | \mathcal{B}(n,w)| \geqslant 2^m $\end{document}</tex-math></inline-formula> is, in fact, sufficient for the existence of an <inline-formula><tex-math id="M26">\begin{document}$ (m,n,w) $\end{document}</tex-math></inline-formula>-domination mapping whenever <inline-formula><tex-math id="M27">\begin{document}$ m $\end{document}</tex-math></inline-formula> is sufficiently large. We also present a polynomial-time algorithm that, given any <inline-formula><tex-math id="M28">\begin{document}$ m $\end{document}</tex-math></inline-formula>, <inline-formula><tex-math id="M29">\begin{document}$ n $\end{document}</tex-math></inline-formula>, and <inline-formula><tex-math id="M30">\begin{document}$ w $\end{document}</tex-math></inline-formula>, determines whether an <inline-formula><tex-math id="M31">\begin{document}$ (m,n,w) $\end{document}</tex-math></inline-formula>-domination mapping exists for a domination graph with an equitable degree distribution.

Yu Yu

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.

Jung Hee Cheon, Dongwoo Kim, Duhyeong Kim, Keewoo Lee

The scaled inverse of a nonzero element $a(x)\in \mathbb{Z}[x]/f(x)$, where $f(x)$ is an irreducible polynomial over $\mathbb{Z}$, is the element $b(x)\in \mathbb{Z}[x]/f(x)$ such that $a(x)b(x)=c \pmod{f(x)}$ for the smallest possible positive integer scale $c$. In this paper, we investigate the scaled inverse of $(x^i-x^j)$ modulo cyclotomic polynomial of the form $\Phi_{p^s}(x)$ or $\Phi_{p^s q^t}(x)$, where $p, q$ are primes with $p<q$ and $s, t$ are positive integers. Our main results are that the coefficient size of the scaled inverse of $(x^i-x^j)$ is bounded by $p-1$ with the scale $p$ modulo $\Phi_{p^s}(x)$, and is bounded by $q-1$ with the scale not greater than $q$ modulo $\Phi_{p^s q^t}(x)$. Previously, the analogous result on cyclotomic polynomials of the form $\Phi_{2^n}(x)$ gave rise to many lattice-based cryptosystems, especially, zero-knowledge proofs. Our result provides more flexible choice of cyclotomic polynomials in such cryptosystems. Along the way of proving the theorems, we also prove several properties of $\{x^k\}_{k\in\mathbb{Z}}$ in $\mathbb{Z}[x]/\Phi_{pq}(x)$ which might be of independent interest.

彦伟 周, 波 杨, 喆 夏, 明武 张

Leakage of private information has become a threat to the security of cryptography systems. It has become a common security requirement that a cryptography scheme should withstand various leakage attacks. The non-interactive zero-knowledge (NIZK) argument system, one-time lossy filter (OT-LF) and one-time signature were widely used to create the generic constructions of leakage-resilient identity-based encryption (IBE) scheme with chosen-ciphertext attack (CCA) security. However, the computational efficiency of the corresponding generic construction is low because the underlying cryptographic tool is low. Thus, to solve the above problem, a new cryptographic primitive, called identity-based hash proof system with two encapsulated-key (T-IB-HPS), is proposed. The new generic constructions of leakage resilient IBE scheme with CCA security is created from the T-IB-HPS and message authentication code (MAC), and the security of the above proposed scheme is proved from the security of the underlying cryptographic tool. To further show the practicability, an instantiation of T-IB-HPS is constructed, and the formal security proof of the above instantiation is shown based on the decisional bilinear Diffie-Hellman (DBDH) assumption. Compared with the previous generic constructions of leakage resilient IBE scheme with CCA security, since the underlying cryptographic tools with low computational efficiency are not used, our generic construction has high computational efficiency.

Hazay, Carmit, Venkitasubramaniam, Muthuramakrishnan, Weiss, Mor

Leakage-resilient cryptography aims to protect cryptographic primitives from so-called "side channel attacks" that exploit their physical implementation to learn their input or secret state. Starting from the works of Ishai, Sahai and Wagner (CRYPTO`03) and Micali and Reyzin (TCC`04), most works on leakage-resilient cryptography either focus on protecting general computations, such as circuits or multiparty computation protocols, or on specific non-interactive primitives such as storage, encryption and signatures. This work focuses on leakage-resilience for the middle ground, namely for distributed and interactive cryptographic primitives. Our main technical contribution is designing the first secret-sharing scheme that is equivocal, resists adaptive probing of a constant fraction of bits from each share, while incurring only a constant blowup in share size. Equivocation is a strong leakage-resilience guarantee, recently introduced by Hazay et al. (ITC`21). Our construction is obtained via a general compiler which we introduce, that transforms any secret-sharing scheme into an equivocal scheme against adaptive leakage. An attractive feature of our compiler is that it respects additive reconstruction, namely, if the original scheme has additive reconstruction, then the transformed scheme has linear reconstruction. We extend our compiler to a general paradigm for protecting distributed primitives against leakage, and show its applicability to various primitives, including secret sharing, verifiable secret sharing, function secret sharing, distributed encryption and signatures, and distributed zero-knowledge proofs. For each of these primitives, our paradigm transforms any construction of the primitive into a scheme that resists adaptive party corruptions, as well as adaptive probing leakage of a constant fraction of bits in each share when the share is stored in memory (but not when it is used in computations). Moreover, the transformation incurs only a constant blowup in the share size, and respects additive reconstruction - an important feature for several of these primitives, such as function secret sharing and distributed encryption.

Emanuele Bellini, Chiara Marcolla, Nadir Murru

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.

Peijun Zhang, Lianhai Wang, Wei Wang, Kunlun Fu · 5 authors

Blockchain, which has a distributed structure, has been widely used in many areas. Especially in the area of smart cities, blockchain technology shows great potential. The security issues of blockchain affect the construction of smart cities to varying degrees. With the rapid development of quantum computation, elliptic curves cryptosystems used in blockchain are not secure enough. This paper presents a blockchain system based on lattice cipher, which can resist the attack of quantum computation. The most challenge is that the size of public keys and signatures used by lattice cryptosystems is typically very large. As a result, each block in a blockchain can only accommodate a small number of transactions. It will affect the running speed and performance of the blockchain. For overcoming this problem, we proposed a way that we only put the hash values of public keys and signatures on the blockchain and store the complete content of them on an IPFS (interplanetary file system). In this way, the number of bytes occupied by each transaction is greatly reduced. We design a bitcoin exchange scheme to evaluate the performance of the proposed quantum-resistant blockchain system. The simulation platform is verified to be available and effective.

Gabrielle De Micheli, Pierrick Gaudry, Cécile Pierrot

No abstract is available for this record.

Carmit Hazay, Muthuramakrishnan Venkitasubramaniam, Mor Weiss

Zero-Knowledge PCPs (ZK-PCPs; Kilian, Petrank, and Tardos, STOC `97) are PCPs with the additional zero-knowledge guarantee that the view of any (possibly malicious) verifier making a bounded number of queries to the proof can be efficiently simulated up to a small statistical distance. Similarly, ZK-PCPs of Proximity (ZK-PCPPs; Ishai and Weiss, TCC `14) are PCPPs in which the view of an adversarial verifier can be efficiently simulated with few queries to the input. Previous ZK-PCP constructions obtained an exponential gap between the query complexity q of the honest verifier, and the bound q^* on the queries of a malicious verifier (i.e., q = poly log (q^*)), but required either exponential-time simulation, or adaptive honest verification. This should be contrasted with standard PCPs, that can be verified non-adaptively (i.e., with a single round of queries to the proof). The problem of constructing such ZK-PCPs, even when q^* = q, has remained open since they were first introduced more than 2 decades ago. This question is also open for ZK-PCPPs, for which no construction with non-adaptive honest verification is known (not even with exponential-time simulation). We resolve this question by constructing the first ZK-PCPs and ZK-PCPPs which simultaneously achieve efficient zero-knowledge simulation and non-adaptive honest verification. Our schemes have a square-root query gap, namely q^*/q = O(√n) where n is the input length. Our constructions combine the "MPC-in-the-head" technique (Ishai et al., STOC `07) with leakage-resilient secret sharing. Specifically, we use the MPC-in-the-head technique to construct a ZK-PCP variant over a large alphabet, then employ leakage-resilient secret sharing to design a new alphabet reduction for ZK-PCPs which preserves zero-knowledge.

Suthee Ruangwises

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.