Skip to content
This repository has been archived by the owner on Oct 28, 2024. It is now read-only.

Academic Papers Referenced

Jump to bottom
HaRold edited this page Feb 19, 2019 · 9 revisions

The following academic papers and presentations are used as references:

zkSNARKs

  • On the Size of Pairing-based Non-interactive Arguments

    • Jens Groth

    • Non-interactive arguments enable a prover to convince a verifier that a statement is true. Recently there has been a lot of progress both in theory and practice on constructing highly efficient non-interactive arguments with small size and low verification complexity, so-called succinct non-interactive arguments (SNARGs) and succinct non-interactive arguments of knowledge (SNARKs)...

  • Snarky Signatures: Minimal Signatures of Knowledge from Simulation-Extractable SNARKs

    • Jens Groth and Mary Maller

    • We construct a pairing-based simulation-extractable succinct non-interactive argument of knowledge (SE-SNARK) that consists of only 3 group elements and has highly efficient verification. By formally linking SE-SNARKs to signatures of knowledge, we then obtain a succinct signature of knowledge consisting of only 3 group elements.

  • Making Groth’s zk-SNARK Simulation Extractable in the Random Oracle Model

    • Sean Bowe and Ariel Gabizon

    • The purpose of this note is to provide a variant of Groth’s zk-SNARK [5] that satisfies simulation extractability, which is a strong form of adaptive non-malleability. Let us call such a construction a zk-SE-SNARK for brevity. A straightforward alteration of the construction gives a succinct Signature of Knowledge (SoK). Our construction of both primitives uses a bilinear group (G1, G2, GT ) and a proof/signature requires three G1 elements and two G2 elements.

Elliptic Curves

Twisted Edwards

  • Twisted Edwards Curves

    • Daniel J. Bernstein, Peter Birkner, Marc Joye, Tanja Lange, and Christiane Peters

    • This paper introduces “twisted Edwards curves,” a generalization of the recently introduced Edwards curves; shows that twisted Edwards curves include more curves over finite fields, and in particular every elliptic curve in Montgomery form; shows how to cover even more curves via isogenies; presents fast explicit formulas for twisted Edwards curves in projective and inverted coordinates; and shows that twisted Edwards curves save time for many curves that were already expressible as Edwards curves.

  • Twisted Edwards Curves Revisited

    • Huseyin Hisil, Kenneth Koon-Ho Wong, Gary Carter, and Ed Dawson

    • This paper introduces fast algorithms for performing group operations on twisted Edwards curves, pushing the recent speed limits of Elliptic Curve Cryptography (ECC) forward in a wide range of applications. Notably, the new addition algorithm uses1 8M for suitably selected curve constants. In comparison, the fastest point addition algorithms for (twisted) Edwards curves stated in the literature use 9M + 1S. It is also shown that the new addition algorithm can be implemented with four processors dropping the effective cost to 2M. This implies an effective speed increase by the full factor of 4 over the sequential case. Our results allow faster implementation of elliptic curve scalar multiplication. In addition, the new point addition algorithm can be used to provide a natural protection from side channel attacks based on simple power analysis (SPA).

  • Elliptic Curves for Security

    • A. Langley, M. Hamburg, S. Turner

    • This memo specifies two elliptic curves over prime fields that offer high practical security in cryptographic applications, including Transport Layer Security (TLS). These curves are intended to operate at the ~128-bit and ~224-bit security level, respectively, and are generated deterministically based on a list of required properties.

Montgomery Form

  • Speeding the Pollard and Elliptic Curve Methods of Factorization

    • Peter L. Montgomery

    • Since 1974, several algorithms have been developed that attempt to factor a large number N by doing extensive computations modulo N and occasionally taking GCDs with N. These began with Pollard's p - 1 and Monte Carlo methods. More recently, Williams published a p + 1 method, and Lenstra discovered an elliptic curve method (ECM). We present ways to speed all of these. One improvement uses two tables during the second phases of p ± 1 and ECM, looking for a match. Polynomial preconditioning lets us search a fixed table of size n with n/2 + o(n) multiplications. A parametrization of elliptic curves lets Step 1 of ECM compute the x-coordinate of nP from that of P in about 9.3 log2 n multiplications for arbitrary P.

  • Montgomery curves and the Montgomery ladder

    • Daniel J. Bernstein and Tanja Lange

    • The Montgomery ladder is a remarkably simple method of computing scalar multiples of points on a broad class of elliptic curves. This article surveys a wide range of topics related to the Montgomery ladder, both from the historical perspective of Weierstrass curves and from the modern perspective of Edwards curves. New material includes a full proof of a complete constant-time ladder algorithm suitable for cryptographic applications.

  • Efficient Elliptic Curve Cryptosystems from a Scalar Multiplication Algorithm with Recovery of the y-Coordinate on a Montgomery-Form Elliptic Curve

    • Katsuyuki Okeya and Kouichi Sakurai

    • We present a scalar multiplication algorithm with recovery of the y-coordinate on a Montgomery form elliptic curve over any non-binary field. The previous algorithms for scalar multiplication on a Montgomery form do not consider how to recover the y-coordinate.

  • Can we avoid tests for zero in fast elliptic-curve arithmetic?

    • Daniel J. Bernstein

    • This paper analyzes the exact extent to which 0 and ∞ cause trouble in Montgomery’s fast branchless formulas for x-coordinate scalar multiplication on elliptic curves of the form by^2 = x^3 + ax^2 + x. The analysis shows that some multiplications and branches can be eliminated from elliptic-curve primality proofs and from elliptic-curve cryptography

  • Efficient arithmetic on elliptic curves using a mixed Edwards–Montgomery representation

    • Wouter Castryck, Steven Galbraith, and Reza Rezaeian Farashahi

    • From the viewpoint of x-coordinate-only arithmetic on elliptic curves, switching between the Edwards model and the Montgomery model is quasi cost-free. We use this observation to speed up Montgomery’s algorithm, reducing the complexity of a doubling step from 2M + 2S to 1M + 3S for suitably chosen curve parameters.

Ciphers

  • MiMC: Efficient Encryption and Cryptographic Hashing with Minimal Multiplicative Complexity

    • Martin Albrecht, Lorenzo Grassi, Christian Rechberger, Arnab Roy, and Tyge Tiessen

    • We explore cryptographic primitives with low multiplicative complexity. This is motivated by recent progress in practical applications of secure multi-party computation (MPC), fully homomorphic encryption (FHE), and zero-knowledge proofs (ZK) where primitives from symmetric cryptography are needed and where linear computations are, compared to non-linear operations, essentially “free”. Starting with the cipher design strategy “LowMC” from Eurocrypt 2015, a number of bitoriented proposals have been put forward, focusing on applications where the multiplicative depth of the circuit describing the cipher is the most important optimization goal.

  • MPC-Friendly Symmetric Key Primitives

    • Lorenzo Grassi, Christian Rechberger, Dragos Rotaru, Peter Scholl and Nigel P. Smart

    • We discuss the design of symmetric primitives, in particular Pseudo-Random Functions (PRFs) which are suitable for use in a secret-sharing based MPC system. We consider three different PRFs: the Naor-Reingold PRF, a PRF based on the Legendre symbol, and a specialized block cipher design called MiMC. We present protocols for implementing these PRFs within a secret-sharing based MPC system, and discuss possible applications. We then compare the performance of our protocols. Depending on the application, different PRFs may offer different optimizations and advantages over the classic AES benchmark. Thus, we cannot conclude that there is one optimal PRF to be used in all situations.

  • MARVELlous: a STARK-Friendly Family of Cryptographic Primitives

    • Tomer Ashur and Siemen Dhooghe

    • 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-Dåmgard based hash function instantiated with Jarvis as its compression function thus it inherits its security properties up to the birthday bound.

  • Constructing Cryptographic Hash Functions from Fixed-Key Blockciphers

    • Phillip Rogaway and John Steinberger

    • We propose a family of compression functions built from fixed-key blockciphers and investigate their collision and preimage security in the ideal-cipher model. The constructions have security approaching and in many cases equaling the security upper bounds found in previous work of the authors. In particular, we describe a 2n-bit to n-bit compression function using three n-bit permutation calls that has collision security N^0.5, where N = 2^n, and we describe 3n-bit to 2n-bit compression functions using five and six permutation calls and having collision security of at least N^0.55 and N^0.63.

Signature Schemes

EdDSA

  • High-speed high-security signatures

    • Peter Schwabe, Daniel J. Bernstein, Niels Duif, Tanja Lange, and Bo-Yin Yang

  • EdDSA for more curves

    • Daniel J. Bernstein, Simon Josefsson, Simon Josefsson Datakonsult, Tanja Lange, Peter Schwabe, Bo-Yin Yang

    • The original specification of EdDSA was suitable only for finite fields Fq with q mod 4 = 1. The main purpose of this document is to extend EdDSA to allow finite fields Fq with any odd q. This document also extends EdDSA to support prehashing, i.e., signing the hash of a message.

Optimisations

  • Efficient Software-Implementation of Finite Fields with Applications to Cryptography

    • Jorge Guajardo, Sandeep S. Kumar, Christof Paar, Jan Pelzl

    • In this work, we present a survey of efficient techniques for software implementation of finite field arithmetic especially suitable for cryptographic applications. We discuss different algorithms for three types of finite fields and their special versions popularly used in cryptography: Binary fields, prime fields and extension fields. Implementation details of the algorithms for field addition/subtraction, field multiplication, field reduction and field inversion for each of these fields are discussed in detail. The efficiency of these different algorithms depends largely on the underlying micro-processor architecture. Therefore, a careful choice of the appropriate set of algorithms has to be made for a software implementation depending on the performance requirements and available resources.

  • Highly-Parallel Montgomery Multiplication for Multi-core General-Purpose Microprocessors

    • Selçuk Baktr and Erkay Savas

  • Implementing modular arithmetic using OpenCL

    • Fredrik Gundersen
Clone this wiki locally