International Association
for Cryptologic Research

In this work, we present highly-optimized constant-time software libraries for Supersingular Isogeny Key Encapsulation (SIKE) protocol on ARMv8 processors. Our optimized hand-crafted assembly libraries provide the most efficient timing results on 64-bit ARM-powered devices. Moreover, the presented libraries can be integrated into any other cryptography primitives targeting the same finite field size. We design a new mixed implementation of field arithmetic on 64-bit ARM processors by exploiting the A64 and Advanced SIMD processing units working in parallel. Using these techniques, we are able to improve the performance of the entire protocol by the factor of 5 times compared to optimized C implementations on 64-bit ARM high-performance cores, providing 83-, 124-, and 159-bit quantum-security levels. Furthermore, we compare the performance of our proposed library with the previous highly-optimized ARMv8 assembly library available in the literature. The implementation results illustrate the overall 10% performance improvement in comparison with previous work, highlighting the benefit of using mixed implementation over relatively-large finite field size.

We present the first quantum-resistant $n$-party key agreement scheme based on supersingular elliptic curve isogenies. We show that the scheme is secure against quantum adversaries, by providing a security reduction to an intractable isogeny problem. We describe the communication and computational steps required for $n$ parties to establish a common shared secret key. Our scheme is the first non-generic quantum-resistant group key agreement protocol, and is more efficient than generic protocols, with near-optimal communication overhead. In addition, our scheme is contributory, which in some settings is a desirable security property: each party applies a function of their own private key to every further transmission. We implement the proposed protocol in portable C for the special case where three parties establish a shared secret. Moreover, we benchmark our software on two generations of Intel processors, highlighting the feasibility and efficiency of using the proposed scheme in practical settings. The proposed software computes the entire group key agreement in 994 and 1,374 millions of clock cycles on Intel Core i7-6500 Skylake and Core i7-2609 Sandy Bridge processors, respectively.

We construct a publicly verifiable protocol for proving computational work based on collision-resistant hash functions and a new plausible complexity assumption regarding the existence of "inherently sequential" hash functions. Our protocol is based on a novel construction of time-lock puzzles. Given a sampled "puzzle" $P \gets D_n$, where $n$ is the security parameter and $D_n$ is the distribution of the puzzles, a corresponding "solution" can be generated using $N$ evaluations of the sequential hash function, where $N>n$ is another parameter, while any feasible adversarial strategy for generating valid solutions must take at least as much time as $\Omega(N)$ *sequential* evaluations of the hash function after receiving $P$. Thus, valid solutions constitute a "proof" that $\Omega(N)$ parallel time elapsed since $P$ was received. Solutions can be publicly and efficiently verified in time $\poly(n) \cdot \polylog(N)$. Applications of these "time-lock puzzles" include noninteractive timestamping of documents (when the distribution over the possible documents corresponds to the puzzle distribution $D_n$) and universally verifiable CPU benchmarks.

Our construction is secure in the standard model under complexity assumptions (collision-resistant hash functions and inherently sequential hash functions), and makes black-box use of the underlying primitives. Consequently, the corresponding construction in the random oracle model is secure unconditionally. Moreover, as it is a public-coin protocol, it can be made non-interactive in the random oracle model using the Fiat-Shamir Heuristic.

Our construction makes a novel use of ``depth-robust'' directed acyclic graphs---ones whose depth remains large even after removing a constant fraction of vertices---which were previously studied for the purpose of complexity lower bounds. The construction bypasses a recent negative result of Mahmoody, Moran, and Vadhan (CRYPTO `11) for time-lock puzzles in the random oracle model, which showed that it is impossible to have time-lock puzzles like ours in the random oracle model if the puzzle generator also computes a solution together with the puzzle.

We show that every construction of one-time signature schemes from a random oracle achieves black-box security at most $2^{(1+o(1))q}$, where $q$ is the total number of oracle queries asked by the key generation, signing, and verification algorithms. That is, any such scheme can be broken with probability close to $1$ by a (computationally unbounded) adversary making $2^{(1+o(1))q}$ queries to the oracle. This is tight up to a constant factor in the number of queries, since a simple modification of Lamport's one-time signatures (Lamport'79) achieves $2^{(0.812-o(1))q}$ black-box security using $q$ queries to the oracle.

Our result extends (with a loss of a constant factor in the number of queries) also to the random permutation and ideal-cipher oracles. Since the symmetric primitives (e.g. block ciphers, hash functions, and message authentication codes) can be constructed by a constant number of queries to the mentioned oracles, as corollary we get lower bounds on the efficiency of signature schemes from symmetric primitives when the construction is black-box. This can be taken as evidence of an inherent efficiency gap between signature schemes and symmetric primitives.

Research area

The successful candidate will join the CryptoLUX group led by Prof. Alex Biryukov. Candidates with proven research track record in one or more of the following areas are particularly encouraged to apply:

• Design/analysis of lightweight crypto (with the goal to evaluate NIST competition submissions)
• Financial cryptography (cryptocurrencies, blockchain tech)
• Privacy enhancing technologies

Your Profile

A Ph.D. degree in Computer Science, Applied Mathematics or a related field; Competitive research record in applied cryptography or information security (at least one paper in top 10 IT security/crypto conferences; or several papers at ToSC(FSE), CHES, PETs or TCC); Strong mathematical and algorithmic CS background; Good skills in programming and scripting languages; Commitment, team working and a critical mind; Fluent written and verbal communication skills in English are mandatory.

The University offers a one years employment contract (with extension possibility). The University offers highly competitive salaries and is an equal opportunity employer. You will work in an exciting international environment of a large IT security-focused research center (SnT/CSC), developing technologies which will have direct impact on the future.

Applications, written in English, should be submitted by e-mail and should include:

• A brief cover letter explaining the candidate\'s motivation and research interests
• Curriculum Vitae (including photo, education/research/ work, publications, interests)
• Information on participation in competitions, Olympiads, CTFs is a plus
• Contact information of 2-3 references

Applications will be considered on receipt therefore applying before the deadline is encouraged.

Closing date for applications: 1 May 2019

Contact: Prof. Alex Biryukov

More information: https://www.cryptolux.org/index.php/Vacancies

Applications are invited from the Indian nationals for the position of Project Associate to work in the field of Hardware Security in the project entitled “Physical Unclonable Function (PUF) based Application Specific IC (ASIC) by Technology-Circuit-System Co-Development for Strategic Applications” funded by the office of Principal Scientific Advisor (PSA) to the Government of India.

Post: Project Associate (Number of Posts: 2)

Project Duration: 3 years (the positions as proposed are purely temporary and would be filled on Contract basis with consolidated salary under the project). The appointment will be made initially for a period of two years and extendable upto further one more year or the closing date of the project whichever is earlier.

Salary: Rs 40,000 to Rs 50,000 per month commensurate to relevant experience

Essential Qualifications: M.E/M.Tech in Electronics and Communication Engineering/ Computer Science and Engineering/ Applied Electronics/ Embedded Systems/ VLSI Design from a recognized university in First Class with 60% or above marks or equivalent.

Areas of Skill sets/ Knowledge required:

a) Knowledge in cryptology and strong background in digital system design, including project development experience in C, MATLAB, VHDL/Verilog programming. b) In-depth knowledge of front-end digital design process and related design flows (Xilinx FPGA /ASIC digital IC design). c) Candidates with prior industrial/research experience in the field of Hardware Security including Physical Unclonable Function (PUF) and Side Channel Attacks (SCA) are preferred.

Selection Procedure: Written Test and/or Interview

How to Apply?

1) Applications received via email will ONLY be considered. Candidate should write “Application for Project Associate Position” in the subject line of his/her E-mail. 2) The candidate is required to attach the Personal Particulars Form in pdf format duly filled and signed. 3) The email should be sent to hrpuf2019 (at) setsindia.net

Closing date for applications: 10 April 2019

Contact: N. Nalla Anandakumar, Scientist, SETS (Co-Principal Investigator)

More information: https://setsindia.in/careers

White-box cryptography was originally introduced in the setting of digital rights management with the goal of preventing a user from illegally re-distributing their software decryption program. In recent years, mobile payment has become a popular new application for white-box cryptography. Here, white-box cryptography is used to increase the robustness against external adversaries (i.e., not the user) who aim to misuse/attack the cryptographic functionalities of the payment application. A necessary requirement for secure white-box cryptography is that an adversary cannot extract the embedded secret key from the implementation. However, a white-box implementation needs to fulfill further security properties in order to provide useful protection of an application. In this paper we focus on the popular property incompressibility that is a mitigation technique against code-lifting attacks. We provide an incompressible white-box encryption scheme based on the standard-assumption of one-way permutations whereas previous works used either public-key type assumptions or non-standard symmetric-type assumptions.

The Lightning Network is a second layer technology running on top of Bitcoin and other Blockchains. It is composed of a peer-to-peer network, used to transfer raw information data. Some of the links in the peer-to-peer network are identified as payment channels, used to conduct payments between two Lightning Network clients (i.e., the two nodes of the channel). Payment channels are created with a fixed credit amount, the channel capacity. The channel capacity, together with the IP address of the nodes, is published to allow a routing algorithm to find an existing path between two nodes that do not have a direct payment channel. However, to preserve users' privacy, the precise balance of the pair of nodes of a given channel (i.e. the bandwidth of the channel in each direction), is kept secret. Since balances are not announced, second-layer nodes probe routes iteratively, until they find a successful route to the destination for the amount required, if any. This feature makes the routing discovery protocol less efficient but preserves the privacy of channel balances. In this paper, we present an attack to disclose the balance of a channel in the Lightning Network. Our attack is based on performing multiple payments ensuring that none of them is finalized, minimizing the economical cost of the attack. We present experimental results that validate our claims, and countermeasures to handle the attack.

A generalized Feistel cipher is one of the methods to construct block ciphers, and it has several variants. Dong, Li, and Wang showed quantum distinguishing attacks against the $(2d-1)$-round Type-1 generalized Feistel cipher with quantum chosen-plaintext attacks, where $d\ge 3$, and they also showed key recovery attacks [Dong, Li, Wang. Sci China Inf Sci, 2019, 62(2): 022501].

In this paper, we show a polynomial time quantum distinguishing attack against the $(3d-3)$-round version, i.e., we improve the number of rounds by $(d-2)$. We also show a quantum distinguishing attack against the $(d^2-d+1)$-round version in the quantum chosen-ciphertext setting. We apply these quantum distinguishing attacks to obtain key recovery attacks against Type-1 generalized Feistel ciphers.

The need for structured and trusted common parameters is often cited as one of the major drawbacks of pairing-based SNARKs. Although multiparty computation techniques can be used to address this, the resulting parameters are circuit dependent and this costly process must be repeated for every circuit. Recent proposals to switch to a weaker updatable model for parameter generation are not yet sufficiently efficient. We propose a new model for updatability which generates the common reference string in two phases, each of them updatable: in the first phase, parameters are generated for a set of universal quadratic constraints and in the second phase specific circuit dependent parameters which impose some affine constraints can be derived from them non-interactively. We propose a concrete construction based on (but more efficient than) Pinocchio.

An additional contribution of the paper is to obtain a very efficient argument for verifiable computation using the same design principles which is based on weaker assumptions. The communication is approximately 4d group elements and verifying a proof requires computing around 4d pairings and O(n+d) exponentiations, where n is the input size and d the circuit depth. While the argument for the quadratic constraints is based on standard falsifiable assumptions, the argument for the linear constraints is based on a very ad-hoc assumption about certain properties of arguments of membership in linear spaces.

A decision graph is a well-studied classifier and has been used to solve many real-world problems. We assumed a typical scenario between two parties in this study, in which one holds a decision graph and the other wants to know the class label of his/her query without disclosing the graph and query to the other. We propose a novel protocol for this scenario that can obliviously evaluate a graph that is designed by an efficient data structure called the graph level order unary degree sequence (GLOUDS). The time and communication complexities of this protocol are linear to the number of nodes in the graph and do not include any exponential factors. The experiment results revealed that the actual runtime and communication size were well concordant with theoretical complexities. Our method can process a graph with approximately 500 nodes in only 11 s on a standard laptop computer. We also compared the runtime of our method with that of previous methods and confirmed that it was one order of magnitude faster than the previous methods.

Traceable ring signatures are a variant of ring signatures which allows the identity of a user to be revealed, when it signs two different messages with respect to the same group of users. It has applications in e-voting and in cryptocurrencies, such as the well-known Monero. We propose the first traceable ring signature scheme whose security is based on the hardness of the Syndrome Decoding problem, a problem in coding theory which is conjectured to be unsolvable by both classical and quantum algorithms. To construct the scheme, we use a variant of Stern's protocol and, by applying the Fiat-Shamir transform to it in an ingenious way, we obtain a ring signature that allows traceability. We prove that the resulting protocol has the standard security properties for traceable ring signatures in the random oracle model: tag-linkability, anonymity and exculpability. As far as we know, this is the first proposal for a traceable ring signature scheme in the post-quantum setting.

We introduce the concept of computationally independent pair of one-way functions (CI-OWF). We also provide two rich classes of examples of such functions based on standard assumptions. We revisit two-party interactive protocols for proving possession of computational power and existing two-flow challenge-response protocols. We analyze existing protocols for proof of computation power and propose a new two-flow protocol using CI-OWF based on square Diffie-Hellman problem.

In this paper, we present a high-speed constant time hardware implementation of NTRUEncrypt Short Vector Encryption Scheme (SVES), fully compliant with the IEEE 1363.1 Standard Specification for Public Key Cryptographic Techniques Based on Hard Problems over Lattices. Our implementation follows an earlier proposed Post-Quantum Cryptography (PQC) Hardware Application Programming Interface (API), which facilitates its fair comparison with implementations of other PQC schemes. The paper contains the detailed flow and block diagrams, timing analysis, as well as results in terms of latency (in clock cycles), maximum clock frequency, and resource utilization in modern high-performance Field Programmable Gate Arrays (FPGAs). Our design takes full advantage of the ability to parallelize the major operation of NTRU, polynomial multiplication, in hardware. As a result, the execution time bottleneck shifts to the hash function, SHA-256, which is sequential in nature and as a result cannot be easily sped up in hardware. The obtained FPGA results for NTRU Encrypt SVES are compared with the equivalent results for Classic McEliece, a competing, well-established Post-Quantum Cryptography encryption scheme, with a long history of unsuccessful attempts at breaking. Our code for NTRUEncrypt SVES is being made open-source to speed-up further design-space exploration and benchmarking on multiple hardware platforms.

Elliptic curves based algorithms are nowadays widely spread among embedded systems. They indeed have the double advantage of providing efficient implementations with short certicates and of being relatively easy to secure against side-channel attacks. As a matter of fact, when an algorithm with constant execution flow is implemented together with randomization techniques, the obtained design usually thwarts classical side-channel attacks while keeping good performances. Recently, a new technique that makes randomization ineffective, has been successfully applied in the context of RSA implementations. This method, related to a so-called horizontal modus operandi, introduced by Walter in 2001, turns out to be very powerful since it only requires leakages on a single algorithm execution. In this paper, we combine such kind of techniques together with the collision correlation analysis, introduced at CHES 2010 by Moradi et al., to propose a new attack on elliptic curves atomic implementations (or unified formulas) with input randomization. We show how it may be applied against several state-of-the art implementations, including those of Chevallier-Mames et al., of Longa and of Giraud-Verneuil and also Bernstein and Lange for unied Edward's formulas. Finally, we provide simulation results for several sizes of elliptic curves on different hardware architectures. These results, which turn out to be the very rst horizontal attacks on elliptic curves, open new perspectives in securing such implementations. Indeed, this paper shows that two of the main existing countermeasures for elliptic curve implementations become irrelevant when going from vertical to horizontal analysis.

Many advanced lattice based cryptosystems require to sample lattice points from Gaussian distributions. One challenge for this task is that all current algorithms resort to floating-point arithmetic (FPA) at some point, which has numerous drawbacks in practice: it requires numerical stability analysis, extra storage for high-precision, lazy/backtracking techniques for efficiency, and may suffer from weak determinism which can completely break certain schemes.

In this paper, we give techniques to implement Gaussian sampling over general lattices without using FPA. To this end, we revisit the approach of Peikert, using perturbation sampling. Peikert's approach uses the Cholesky decomposition $\mathbb{\Sigma} = \mathbb{A} \mathbb{A}^t$ of the target covariance matrix $\mathbb{\Sigma}$, giving rise to a square matrix $\mathbb{A}$ with real (not integer) entries. Our idea, in a nutshell, is to replace this decomposition by an integral one. While there is in general no integer solution if we restrict $\mathbb{A}$ to being a square matrix, we show that such a decomposition can be efficiently found by allowing $\mathbb{A}$ to be wider (say $n \times 9n$). This can be viewed as an extension of Lagrange's four-square theorem to matrices. In addition, we adapt our integral decomposition algorithm to the ring setting: for power-of-2 cyclotomics, we can exploit the tower of rings structure for improved complexity and compactness.

Due to the public visible nature of blockchain, the seminal cryptocurrencies such as Bitcoin and Ethereum do not provide sufficient level of privacy, i.e., the addresses of sender and receiver and the transfer amount are all stored in plaintexts on blockchain. As the privacy concerns grow, several newly emerged cryptocurrencies such as Monero and ZCash provide strong privacy guarantees (including anonymity and confidentiality) by leveraging cryptographic technique.

Despite strong privacy is promising, it might be overkilled or even could be abused in some cases. In particular, anonymity seems contradict to accountability, which is a crucial property for scenarios requiring disputes resolving mechanism, e.g. e-commerce.

To address the above issues, we introduce accountability to blockchain-based confidential transaction system for the first time. We first formalize a general framework of confidential transaction system with accountability from digital signature, homomorphic public-key encryption and non-interactive zero-knowledge arguments, then present a surprisingly simple and efficient realization called PGC. To avoid using general-purpose zero-knowledge proofs (such as zk-SNARK and zk-STARK), we twist the ElGamal encryption as the underlying homomorphic PKE and develop ciphertext-refreshing approach. This not only enables us to prove transaction validity/correctness by using efficient Sigma protocols and zero-knowledge range proofs, but also makes PGC largely compatible with Bitcoin and Ethereum, which could be used as a drop-in to provide confidential enforcements with accountability.

Generalized Feistel Schemes (GFS) are important components of symmetric ciphers, which have been extensively researched in classical setting. However, the security evaluations of GFS in quantum setting are rather scanty.

In this paper, we give more improved polynomial-time quantum distinguishers on Type-1 GFS in quantum chosen-plaintext attack (qCPA) setting and quantum chosen-ciphertext attack (qCCA) setting. In qCPA setting, we give new quantum polynomial-time distinguishers on $(3d-3)$-round Type-1 GFS with branches $d\geq3$, which gain $d-2$ more rounds than the previous distinguishers. Hence, we could get better key-recovery attacks, whose time complexities gain a factor of $2^{\frac{(d-2)n}{2}}$. In qCCA setting, we get $(3d-3)$-round quantum distinguishers on Type-1 GFS, which gain $d-1$ more rounds than the previous distinguishers.

In addition, we give some quantum attacks on CAST-256 block cipher. We find 12-round and 13-round polynomial-time quantum distinguishers in qCPA and qCCA settings, respectively, while the best previous one is only 7 rounds. Hence, we could derive quantum key-recovery attack on 19-round CAST-256. While the best previous quantum key-recovery attack is on 16 rounds. When comparing our quantum attacks with classical attacks, our result also reaches 16 rounds on CAST-256 with 128-bit key under a competitive complexity.

We present Libra, the first zero-knowledge proof system that has both optimal prover time and succinct proof size/verification time. In particular, if C is the size of the circuit being proved (i) the prover time is O(C) irrespective of the circuit type; (ii) the proof size and verification time are both O(d log C) for d-depth log-space uniform circuits (such as RAM programs). In addition Libra features an one-time trusted setup that depends only on the size of the input to the circuit and not on the circuit logic. Underlying Libra is a new linear-time algorithm for the prover of the interactive proof protocol by Goldwasser, Kalai and Rothblum (also known as GKR protocol), as well as an efficient approach to turn the GKR protocol to zero-knowledge using small masking polynomials. Not only does Libra have excellent asymptotics, but it is also efficient in practice. For example, our implementation shows that it takes 200 seconds to generate a proof for constructing a SHA2-based Merkle tree root on 256 leaves, outperforming all existing zero-knowledge proof systems. Proof size and verification time of Libra are also competitive.

For all vectorial boolean functions up to dimension 4, we present canonical representatives for all extended affine (EA) and CCZ equivalence classes. We also answer the following questions: How large are these classes? Which of these classes contain bijective functions? And how are these classes grouped into CCZ equivalence classes?