Blockchain Papers

Itai Dinur, Daniel Kales, Angela Promitzer, Sebastian Ramacher · 5 authors

No abstract is available for this record.

M. Albrecht, Carlos Cid, Lorenzo Grassi, Dmitry Khovratovich · 7 authors

No abstract is available for this record.

Daniel Kales, Sebastian Ramacher, Christian Rechberger, Roman Walch · 5 authors

Post-quantum cryptography has received increased attention in recent years, in particular, due to the standardization effort by NIST. One of the second-round candidates in the NIST post-quantum standardization project is Picnic, a post-quantum secure signature scheme based on efficient zero-knowledge proofs of knowledge. In this work, we present the first FPGA implementation of Picnic. We show how to efficiently calculate LowMC, the block cipher used as a one-way function in Picnic, in hardware despite the large number of constants needed during computation. We then combine our LowMC implementation and efficient instantiations of Keccak to build the full Picnic algorithm. Additionally, we conform to recently proposed hardware interfaces for post-quantum schemes to enable easier comparisons with other designs. We provide evaluations of our Picnic implementation for both, the standalone design and a version wrapped with a PCIe interface, and compare them to the state-of-the-art software implementations of Picnic and similar hardware designs. Concretely, signing messages on our FPGA takes 0.25 ms for the L1 security level and 1.24 ms for the L5 security level, beating existing optimized software implementations by a factor of 4.

Carlo Brunetta, Bei Liang, Aikaterini Mitrokotsa

No abstract is available for this record.

Vanesa Daza, Alonso González, Zaira Pindado, Carla Ràfols · 5 authors

No abstract is available for this record.

Elette Boyle, Geoffroy Couteau, Niv Gilboa, Yuval Ishai

Oblivious linear-function evaluation (OLE) is a secure two-party protocol allowing a receiver to learn any linear combination of a pair of field elements held by a sender. OLE serves as a common building block for secure computation of arithmetic circuits, analogously to the role of oblivious transfer (OT) for boolean circuits. A useful extension of OLE is vector OLE (VOLE), allowing the receiver to learn any linear combination of two vectors held by the sender. In several applications of OLE, one can replace a large number of instances of OLE by a smaller number of instances of VOLE. This motivates the goal of amortizing the cost of generating long instances of VOLE. We suggest a new approach for fast generation of pseudo-random instances of VOLE via a deterministic local expansion of a pair of short correlated seeds and no interaction. This provides the first example of compressing a non-trivial and cryptographically useful correlation with good concrete efficiency. Our VOLE generators can be used to enhance the efficiency of a host of cryptographic applications. These include secure arithmetic computation and non-interactive zero-knowledge proofs with reusable preprocessing. Our VOLE generators are based on a novel combination of function secret sharing (FSS) for multi-point functions and linear codes in which decoding is intractable. Their security can be based on variants of the learning parity with noise (LPN) assumption over large fields that resist known attacks. We provide several constructions that offer tradeoffs between different efficiency measures and the underlying intractability assumptions.

Bagus Santoso, Taiyo Yamaguchi

In 1996, Stern proposed a three-pass zero-knowledge identification (ID) scheme where the cheating probability, i.e., the success probability of cheating prover, is 2/3. Since then, variants and generalization of Stern's ID have been proposed. However, within two-bit challenge space, all of them are having the cheating probability of more than half or reaching half only in an asymptotic manner with more than three passes in one round. In this paper, we propose the first code-based zero-knowledge three-pass ID scheme with the cheating probability of exactly half even with only two-bit challenge space. Our proposed ID scheme can reduce the necessary number of rounds in order to achieve the targeted security against impersonation. Since rewinding technique cannot be used against a quantum adversary in the security proof, we prove the security using the lossy paradigm and rely on the decisional version of syndrome decoding problem so that we do not have to rewind the adversary.

Jean-François Geneste

We propose building a new PKC in a ring structure, the classification of rings being an open problem. The difficulty of the scheme is based on retrieving the eigenvalues of endomorphism on a finite type module over a non-commutative ring. It is resistant to a chosen cipher text attack. Working in the fraction ring of a non-commutative ring makes our scheme a zero-knowledge proof of knowledge, result indistinguishable, in the Naor-Yung model. Finally, a dramatic improvement in security is obtained through the drawing with uniform probability of the working ring at high frequency.

Amir S. Mortazavi, Mahmoud Salmasizadeh, Amir Daneshgar

No abstract is available for this record.

Susumu Kiyoshima

No abstract is available for this record.

Takashi Yamakawa

Bilinear maps (also called pairings) have been used for constructing various kinds of cryptographic primitives including (but not limited to) short signatures, identity-based encryption, attribute-based encryption, and non-interactive zero-knowledge proof systems. In known instantiations of cryptographic bilinear maps based on eliptic curves, source and target groups are different groups, which may restrict applications of bilinear maps. Cheon and Lee studied self-bilinear maps, which are bilinear maps whose source and target groups are identical. They showed huge potential of self-bilinear maps by showing that self-bilinear maps can be transformed into multilinear maps, which give further more cryptographic applications including (but not limited to) multiparty non-interactive key exchange, broadcast encryption, attribute-based encryption, homomorphic signatures, and obfuscation. However, they also showed a strong negative result on the existence of cryptographic self-bilinear maps. Namely, they showed that if there exists an efficiently computable self-bilinear map on a known order group, then the computational Diffie-Hellman (CDH) assumption does not hold on the group. This means that cryptographically useful self-bilinear maps do not exist on groups of known order. On the other hand, there is no negative result for self-bilinear maps on groups of unknown order. Indeed, Yamakawa et al. gave a partial positive result for self-bilinear maps on unknown order groups. Namely, they constructed self-bilinear maps with auxiliary information, which is a weaker variant of self-bilinear maps based on indistinguishability obfuscation. Though they showed that they are sufficient for some applications of self-bilinear maps, they are not as useful as "ideal" self-bilinear maps, which do not need auxiliary information. In this talk, we first review the construction of self-bilinear maps with auxiliary information given by Yamakawa et al. Then we consider the possibility of constructing ideal self-bilinear maps.

Tomer Ashur, Siemen Dhooghe

The ZK-STARK technology, published by Ben-Sasson et al. in ePrint 2018/046 is hailed by many as being a viable, efficient solution to the scaling problem of cryptocurrencies. In essence, a ZK-STARK proof uses a Merkle-tree to compress the data that needs to be verified, thus greatly reduces the communication overhead between the prover and the verifier. We propose MARVELlous a family of cryptographic algorithms specifically designed for STARK efficiency. The family currently includes the block cipher Jarvis and the hash function Friday. The design of Jarvis is inspired by the design of Rijndael, better known as the AES. By doing so we create a cipher with similar properties to those of Rijndael which allows us to reuse the wide-trail strategy to argue the resistance of the design against differential and linear cryptanalysis and focus our efforts on resistance against algebraic attacks. Friday is a Merkle-Damgard based hash function instantiated with Jarvis as its compression function thus it inherits its security properties up to the birthday bound. Jarvis and Friday have been suggested to be used in the Ethereum protocol by Ben-Sasson in Ethereum's Devcon IV. In this paper, we instantiate versions of Jarvis offering 128, 160, 192 and 256-bit security (both state- and key-size) which are used to implement Friday. We warmly invite the community to study and assess the security of the designs.

Zvika Brakerski, Vadim Lyubashevsky, Vinod Vaikuntanathan, Daniel Wichs

No abstract is available for this record.

Fuyuki Kitagawa, Keisuke Tanaka

We propose a framework for achieving a public-key encryption (PKE) scheme that satisfies key dependent message security against chosen ciphertext attacks (KDM-CCA security) based on projective hash function. Our framework can be instantiated under the decisional diffie-hellman (DDH), quadratic residuosity (QR), and decisional composite residuosity (DCR) assumptions. The constructed schemes are KDM-CCA secure with respect to affine functions and compatible with the amplification method shown by Applebaum (EUROCRYPT 2011). Thus, they lead to PKE schemes satisfying KDM-CCA security for all functions computable by a-priori bounded size circuits. They are the first PKE schemes satisfying such a security notion in the standard model using neither non-interactive zero knowledge proof nor bilinear pairing. The above framework based on projective hash function captures only KDM-CCA security in the single user setting. However, we can prove the KDM-CCA security in the multi user setting of our concrete instantiations by using their algebraic structures explicitly. Especially, we prove that our DDH based scheme satisfies KDM-CCA security in the multi user setting with the same parameter setting as in the single user setting.

Keisuke Hara, Fuyuki Kitagawa, Takahiro Matsuda, Goichiro Hanaoka · 5 authors

No abstract is available for this record.

Chloé Hébant, Duong Hieu Phan, David Pointcheval

Since the seminal paper on Fully Homomorphic Encryption (FHE) by Gentry in 2009, a lot of work and improvements have been proposed, with an amazing number of possible applications. It allows outsourcing any kind of computations on encrypted data, and thus without leaking any information to the provider who performs the computations. This is quite useful for many sensitive data (finance, medical, etc.).

Areej M. Abduldaim, Nadia M. G. Al-Saidi

Algebra is one of the important fields of mathematics. It concerns with the study and manipulation of mathematical symbols. It also concerns with the study of abstractions such as groups, rings, and fields. Due to the development of these abstractions, it is extended to consider other structures, such as vectors, matrices, and polynomials, which are non-numerical objects. Computer algebra is the implementation of algebraic methods as algorithms and computer programs. Recently, many algebraic cryptosystem protocols are based on non-commutative algebraic structures, such as authentication, key exchange, and encryption-decryption processes are adopted. Cryptography is the science that aimed at sending the information through public channels in such a way that only an authorized recipient can read it. Ring theory is the most attractive category of algebra in the area of cryptography. In this paper, we employ the algebraic structure called skew -Armendariz rings to design a neoteric algorithm for zero knowledge proof. The proposed protocol is established and illustrated through numerical example, and its soundness and completeness are proved.

Kirill Morozov

No abstract is available for this record.

Olivier Blazy, Philippe Gaborit, Julien Schrek, Nicolas Sendrier

In this paper we give the first blind signature protocol for code-based cryptography. Our approach is different from the classical original RSA based blind signature scheme, it is done in the spirit of the Fischlin approach [9] which is based on proofs of knowledge. To achieve our goal we consider a new tool for zero-knowledge (ZK) proofs, the Concatenated Stern ZK protocol, which permits to obtain an authentication protocol for concatenated matrices. A signature is then obtained from the usual Fiat-Shamir heuristic. We describe our blind signature protocol for cryptography based on Hamming metric and show how it can be extended to rank based cryptography. The security of our blind protocol is based on the security of a trapdoor function for the syndrome decoding problem: the CFS signature scheme for Hamming distance and on the more recent RankSign protocol for rank metric. We give proofs in the random oracle model (ROM) for our blind signature scheme, which rely on the Syndrome Decoding problem. The parameters we obtain for our protocol are practical for rank metric (200kBytes) for the signature length and 15kBytes for public key size) and a little less practical for Hamming distance.

Ran Canetti, Amit Lichtenberg

The modeling of trapdoor permutations has evolved over the years. Indeed, finding an appropriate abstraction that bridges between the existing candidate constructions and the needs of applications has proved to be challenging. In particular, the notions of certifying permutations (Bellare and Yung, 96), enhanced and doubly enhanced trapdoor permutations (Goldreich, 04, 08, 11, Goldreich and Rothblum, 13) were added to bridge the gap between the modeling of trapdoor permutations and needs of applications. We identify an additional gap in the current abstraction of trapdoor permutations: Previous works implicitly assumed that it is easy to recognize elements in the domain, as well as uniformly sample from it, even for illegitimate function indices. We demonstrate this gap by using the (Bitansky-Paneth-Wichs, 16) doubly-enhanced trapdoor permutation family to instantiate the Feige-Lapidot-Shamir (FLS) paradigm for constructing non-interactive zero-knowledge (NIZK) protocols, and show that the resulting proof system is unsound. To close the gap, we propose a general notion of certifiably injective doubly enhanced trapdoor functions (DECITDFs), which provides a way of certifying that a given key defines an injective function over the domain defined by it, even when that domain is not efficiently recognizable and sampleable. We show that DECITDFs suffice for instantiating the FLS paradigm; more generally, we argue that certifiable injectivity is needed whenever the generation process of the function is not trusted. We then show two very different ways to construct DECITDFs: One is via the traditional method of RSA/Rabin with the Bellare-Yung certification mechanism, and the other using indistinguishability obfuscation and injective pseudorandom generators. In particular the latter is the first candidate injective trapdoor function, from assumptions other than factoring, that suffices for the FLS paradigm. Finally we observe that a similar gap appears also in other paths proposed in the literature for instantiating the FLS paradigm, specifically via verifiable pseudorandom generators and verifiable pseudorandom functions. Closing the gap there can be done in similar ways to the ones proposed here.

Magnus Gausdal Find, Daniel Smith Tone, Meltem Sönmez Turan

Multiplicative complexity is a complexity measure defined as the minimum number of AND gates required to implement a given primitive by a circuit over the basis (AND, XOR, NOT). Implementations of cyphers with a small number of AND gates are preferred in protocols for fully homomorphic encryption, multiparty computation and zero-knowledge proofs. Fischer and Peralta (2002) computed the number of n-variable Boolean functions with multiplicative complexity 1. In this paper, we study Boolean functions that can be constructed with two AND gates. By characterising the structure of these functions in terms of affine equivalence relations, we provide a closed-form formula for the number of Boolean functions with multiplicative complexity 2.

Areej M. Abduldaim

Innovative idea using ring theory is raised to build a new algorithm for zero knowledge (ZK) cryptosystem. In this paper we introduce an algorithm for zero knowledge protocol based on a specific kind of rings named weak Armendariz. On the other hand, the aim of this paper focuses on the category of noncommutative algebraic structures to describe a new algebraic scheme of zero knowledge proof using weak Armendariz rings. As a result, we employ for the first time weak Armendariz rings in the science of cryptographic which regards as a new application of this class of rings. Finally, we present a novel idea combining between abstract algebra and cryptography.

Sébastien Canard, Fabien Laguillaumie, Paindavoine

One of today’s main challenge related to cloud storage is to maintain the functionalities and the efficiency of customers’ and service providers’ usual environments while protecting the confidentiality of sensitive data. Deduplication is one of those functionalities: it enables cloud storage providers to save a lot of memory by storing only once a file uploaded several times. However, classical encryption schemes block deduplication. One needs to use a “message-locked encryption” scheme (MLE), which allows the detection of duplicates and the storage of only one encrypted file on the server, which can be decrypted by any owner of the file. However, in most existing scheme, a user can bypass this deduplication protocol. In this article, we provide servers verifiability for MLE schemes: the servers can verify that the ciphertexts are well-formed. This property forces a customer to prove that she complied to the deduplication protocol, thus preventing her to deviate from the prescribed functionality of MLE. Then, we provide an MLE scheme satisfying this new security property. To achieve the deduplication consistency, our construction primarily relies on zero-knowledge proofs. Unlike Abadi et al.’s MLE, we instantiate those proofs, so<br> that we obtain a more efficient scheme, secure in the random oracle model.

Silvio Biagioni, Daniel Masny, Daniele Venturi

Abstract The Naor–Yung paradigm [63] allows to generically boost security under chosen-plaintext attacks (CPA) to security against chosen-ciphertext attacks (CCA) for public-key encryption (PKE) schemes. The main idea is to encrypt the plaintext twice (under independent public keys), and to append a non-interactive zero-knowledge (NIZK) proof that the two ciphertexts indeed encrypt the same message. Later work by Camenisch, Chandran, and Shoup [32] and Naor and Segev [ 28 , 30 ] established that the very same technique can also be used in the settings of key-dependent message (KDM) and key-leakage attacks (respectively). In this paper we study the conditions under which the two ciphertexts in the Naor–Yung construction can share the same random coins. We find that this is possible, provided that the underlying PKE scheme meets an additional simple property. The motivation for re-using the same random coins is that this allows to design much more efficient NIZK proofs. We showcase such an improvement in the random oracle model, under standard complexity assumptions including Decisional Diffie–Hellman, Quadratic Residuosity, and Subset Sum. The length of the resulting ciphertexts is reduced by 50%, yielding truly efficient PKE schemes achieving CCA security under KDM and key-leakage attacks. As an additional contribution, we design the first PKE scheme whose CPA security under KDM attacks can be directly reduced to (low-density instances of) the Subset Sum assumption. Our PKE scheme supports key-dependent messages computed via any affine function of the secret key.