International Association
for Cryptologic Research

Multiple Post-Docs in Post-Quantum Cryptography

Academia Sinica, at the very edge of Taipei, is the national research institute of Taiwan.

Here we have an active group of cryptography researchers, including Dr. Bo-Yin Yang, Dr. Kai-Min Chung, Dr. Tung Chou (joining soon), and Prof. Chen-Mou Cheng (adjunct with National Taiwan University), covering wide research topics in cryptography and actively collaborating with researchers from related research areas such as program verification.

We are looking for Post-Docs in PQC (Post-Quantum Cryptography). Here PQC is broadly defined. Starting date is late 2019 to early 2020, for terms of 1 year, renewable.

Potential PQC research topics include cryptanalysis, implementation, and theory. Bo-Yin is in particular interested in people who have hands on experience with the design, implementation and/or analysis of cryptosystems submitted to NIST\'s post-quantum standardization project, and Kai-Min is looking for people interested in theoretical aspects of Post-Quantum Cryptography, such as security in the QROM model and novel (post-)quantum primitives and protocols. We are also particularly interested in people with diverse background to facilitate collaboration among our group members.

Requires background in mathematics, computer science and cryptography. We desire a research track record in some aspects of post-quantum cryptography, but are especially looking for researchers with a broad research spectrum going from mathematical aspects to the practical side such as implementation aspects.

We offer about 2200 USD (~2000 EUR) per month (commensurate with what a starting assistant professor makes locally) in salary and include a 5000 USD per year personal academic travel budget.

Closing date for applications: 31 December 2019

Contact: Bo-Yin Yang by at crypto dot tw

Kai-Min Chung at kmchung at iis dot sinica dot edu dot tw

Event date: 9 May 2020
Submission deadline: 20 March 2020
Notification: 10 April 2020

Event date: 15 June to 19 June 2020

An exciting new development in differential privacy is the shuffled model, in which an anonymous channel enables circumventing the large errors that are necessary in the local model, while relying on much weaker trust assumptions than in the central model. In this paper, we study basic counting problems in the shuffled model and establish separations between the error that can be achieved in the single-message shuffled model and in the shuffled model with multiple messages per user. For the frequency estimation problem with $n$ users and for a domain of size $B$, we obtain:

- A nearly tight lower bound of $\tilde{\Omega}( \min(n^{1/4}, \sqrt{B}))$ on the error in the single-message shuffled model. This implies that the protocols obtained from the amplification via shuffling work of Erlingsson et al. (SODA 2019) and Balle et al. (Crypto 2019) are essentially optimal for single-message protocols. - A nearly tight lower bound of $\Omega\left(\frac{\log{B}}{\log\log{B}}\right)$ on the sample complexity with constant relative error in the single-message shuffled model. This improves on the lower bound of $\Omega(\log^{1/17} B)$ obtained by Cheu et al. (Eurocrypt 2019).

- Protocols in the multi-message shuffled model with $\mathrm{poly}(\log{B}, \log{n})$ bits of communication per user and $\mathrm{poly}\log{B}$ error, which provide an exponential improvement on the error compared to what is possible with single-message algorithms. They also imply protocols with similar error and communication guarantees for several well-studied problems such as heavy hitters, d-dimensional range counting, and M-estimation of the median and quantiles.

For the related selection problem, we also show a nearly tight sample complexity lower bound of $\Omega(B)$ in the single-message shuffled model. This improves on the $\Omega(B^{1/17})$ lower bound obtained by Cheu et al. (Eurocrypt 2019), and when combined with their $\tilde{O}(\sqrt{B})$-error multi-message algorithm, implies the first separation between single-message and multi-message protocols for this problem.

Given the links between nonlinearity properties and the related tables such as LAT, DDT, BCT and ACT that have appeared in the literature, the boomerang connectivity table BCT seems to be an outlier as it cannot be derived from the others using Walsh-Hadamard transform. In this paper, a brief unified summary of the existing links for general vectorial Boolean functions is given first and then a link between the autocorrelation and boomerang connectivity tables is established.

In 2008, Drimer et al. proposed different AES implementations on a Xilinx Virtex-5 FPGA, making efficient use of the DSP slices and BRAM tiles available on the device. Inspired by their work, in this paper, we evaluate the feasibility of extending AES with the popular GCM mode of operation, still concentrating on the optimal use of DSP slices and BRAM tiles. We make use of a Xilinx Zynq UltraScale+ MPSoC FPGA with improved DSP features. For the AES part, we implement Drimer’s round-based and unrolled pipelined architectures differently, still using DSPs and BRAMs efficiently based on the AES Tbox approach. On top of AES, we append the GCM mode of operation, where we use DSP slices to support the GCM finite field multiplication. This allows us to implement AES-GCM with a small amount of FFs and LUTs. We propose two implementations: a relatively compact round-based design and a faster unrolled design.

Obtaining compact, while cryptographically strong, S-boxes is a challenging task required for hardware implementations of lightweight cryptography. Contrarily to 4-bit permutations design which is somewhat well understood, 8-bit permutations have mainly been investigated only through structured S-boxes built from 4-bit ones by means of Feistel, MISTY or SPN schemes. In this paper, we depart from this common habit and search for compact designs directly in the space of 8-bit permutations. We propose two methods for searching good and compact 8-bit S-boxes. One is derived from an adaptation to 8-bit circuits of a systematic bottom-up exploration already used in previous works for 4-bit permutations. The other is the use of a genetic algorithm that samples solutions in the 8-bit permutations space and makes them evolve toward predefined criteria. Contrarily to similar previous attempts, we chose to encode permutations by their circuits rather than by their tables, which allows to optimize non only w.r.t the cryptographic quality but also w.r.t. compactness. We obtain results which show competitive compared to structured designs and we provide an overview of the relation between quality and compactness in the range of rather small 8-bit circuits. Beside, we also exhibit a 8-gate circuit made of only AND and XOR gates that represents a 4-bit permutation belonging to an optimal equivalence class. This shows that such optimal class can be instantiated by threshold implementation friendly circuits with no extra cost compared to previous works.

S-boxes are the only source of non-linearity in many symmetric primitives. While they are often defined as being functions operating on a small space, some recent designs propose the use of much larger ones (e.g., 32 bits). In this context, an S-box is then defined as a subfunction whose cryptographic properties can be estimated precisely.

In this paper, we present a 64-bit ARX-based S-box called Alzette, which can be evaluated in constant time using only 12 instructions on modern CPUs. Its parallel application can also leverage vector (SIMD) instructions. One iteration of Alzette has differential and linear properties comparable to those of the AES S-box, while two iterations are at least as secure as the AES super S-box.

Since the state size is much larger than the typical 4 or 8 bits, the study of the relevant cryptographic properties of Alzette is not trivial.

Abstract. We present a construction for hash-based one-time group signature schemes, and develop a traceable post-quantum multi-time group signature upon it. A group signature scheme allows group members to anonymously sign a message on behalf of the whole group. The signatures are unforgeable and the scheme enables authorized openers to trace the signature back to the original signer when needed. Our construction utilizes three nested layers to build the group signature scheme. The first layer is key management; it deploys a transversal design to assign keys to the group members and the openers, providing the construction with traceability. The second layer utilizes hash pools to build the group public verification key, to connect group members together, and to provide anonymity. The final layer is a post-quantum hash-based signature scheme, that adds unforgeability to our construction. We extend our scheme to multi-time signatures by using Merkle trees, and show that this process keeps the scalability property of Merkle-based signatures, while it supports the group members signing any number of messages. Keywords: Post Quantum Signatures, Hash-based Signatures, Group Signatures, Transversal Designs, τ−traceability

Revocable identity-based encryption (RIBE) is an extension of IBE which can support a key revocation mechanism, and it is important when deploying an IBE system in practice. Boneh and Franklin (Crypto'01) presented the first generic construction of RIBE, however, their scheme is not scalable where the size of key updates is linear in the number of users in the system. The first generic construction of RIBE is presented by Ma and Lin with complete subtree (CS) method by combining IBE and hierarchical IBE (HIBE) schemes. Recently, Lee proposed a new generic construction using the subset difference (SD) method by combining IBE,identity-based revocation (IBR), and two-level HIBE schemes.

In this paper, we present a new primitive called Identity-Based Encryption with Ciphertext Delegation (CIBE) and propose a generic construction of RIBE scheme via subset difference method using CIBE and HIBE as building blocks. CIBE is a special type of Wildcarded IBE (WIBE) and Identity-Based Broadcast Encryption (IBBE). Furthermore, we show that CIBE can be constructed from IBE in a black-box way. Instantiating the underlying building blocks with different concrete schemes, we can obtain a RIBE scheme with constant-size public parameter, ciphertext, private key and $O(r)$ key updates in the selective-ID model. Additionally, our generic RIBE scheme can be easily converted to a sever-aided RIBE scheme which is more suitable for lightweight devices.

We design a very simple private-key encryption scheme whose decryption function is a rational function. This scheme is not born naturally homomorphic. To get homomorphic properties, a nonlinear additive homomorphic operator is specifically developed. The security analysis is based on symmetry considerations and we prove some formal results under the factoring assumption. In particular, we prove IND-CPA security in the generic ring model. Even if our security proof is not complete, we think that it is convincing and that the technical tools considered in this paper are interesting by themselves. Moreover, the factoring assumption is just needed to ensure that solving nonlinear equations or finding non-null polynomials with many roots is difficult. Consequently, the ideas behind our construction could be re-used in rings satisfying these properties. As motivating perspectives, we then propose to develop a simple multiplicative operator. To achieve this, randomness is added in our construction giving hope to remove the factoring assumption in order to get a pure multivariate encryption scheme.

Public key cryptography is threatened by the advent of quantum computers. Using Shor’s algorithm on a large-enough quantum computer, an attacker could cryptanalyze any RSA/ECDSA public key, and generate fake digital signatures in seconds. In this paper, we profile all 9 digital signature candidate algorithms within NIST’s post-quantum cryptography contest round 2, plus stateful hash-based signatures, and evaluate their suitability against 11 different industry applications. We have found that Falcon, a lattice-based digital signing algorithm, when supplemented with XMSS/LMS hash-based signatures, can best meet all of the application requirements if improvements in key generation and key sizes are achieved.

Finding an isogenous supersingular elliptic curve of a prescribed odd degree is an important building block for all the isogeny-based protocols proposed to date. In this note, we present several strategies for the efficient construction of odd degree isogenies that outperform previously reported methods when dealing with isogeny degrees in the range $[7, 2^{20}].$

AEGIS is one of the authenticated encryption designs selected for the final portfolio of the CAESAR competition. It combines the AES round function and simple Boolean operations to update its large state and extract a keystream to achieve an excellent software performance. In 2014, Minaud discovered slight biases in the keystream based on linear characteristics. For family member AEGIS-256, these could be exploited to undermine the confidentiality faster than generic attacks, but this still requires very large amounts of data. For final portfolio member AEGIS-128, these attacks are currently less efficient than generic attacks. We propose improved keystream approximations for the AEGIS family, but also prove upper bounds below $2^{-128}$ for the squared correlation contribution of any single suitable linear characteristic.

There have been notable improvements in discrete logarithm computations in finite fields since 2015 and the introduction of the Tower Number Field Sieve (TNFS) algorithm for extension fields. The Special TNFS is very efficient in finite fields that are target groups of pairings on elliptic curves, where the characteristic is special (e.g.~sparse). The key sizes for pairings should be increased, and alternative pairing-friendly curves can be considered. We revisit the Special variant of TNFS for pairing-friendly curves. In this case the characteristic is given by a polynomial of moderate degree (between 4 and 38) and tiny coefficients, evaluated at an integer (a seed). We present a polynomial selection with a new practical trade-off between degree and coefficient size. As a consequence, the security of curves computed by Barbulescu, El Mrabet and Ghammam should be revised: we obtain a smaller estimated cost of STNFS for all curves except BLS12 and BN. To obtain TNFS-secure curves, we reconsider the Brezing-Weng generic construction of families of pairing-friendly curves and estimate the cost of our new Special TNFS algorithm for these curves. This improves on the work of Fotiadis and Konstantinou, Fotiadis and Martindale, and Barbulescu, El Mrabet and Ghammam. We obtain a short-list of interesting families of curves that are resistant to the Special TNFS algorithm, of embedding degrees 10 to 16 for the 128-bit security level. We conclude that at the 128-bit security level, a BLS-12 curve over a 440 to 448-bit prime seems to be the best choice for pairing efficiency. We also give a brief overview of the 192-bit security level.

Event date: 23 February 2020
Submission deadline: 13 December 2019
Notification: 17 January 2020

ASCON is an authenticated encryption, selected as the first choice for a lightweight use case in the CAESAR competition in February 2019. In this work, we investigate vulnerabilities of ASCON against fault analysis. We observe that the use of 128-bit random nonce makes it resistant against many cryptanalysis techniques like differential, linear, etc. and their variants. However, XORing the key just before releasing the tag T (a public value) creates a trivial attack path. Also, the S-Box demonstrates a non-random behavior towards subset cryptanalysis. We observe that if the 3rd bit of the S-box input is set to zero, then XoR of the last two output bits is zero, with a probability of $0.625$, i.e., this characteristic is present in 10 out of 16 cases. Our subset fault analysis(SSFA) attack uses this property to retrieve the 128-bit secret key. The SSFA attack can uniquely retrieve the key of full-round ASCON with the complexity of $2^{64}$.

Protection against active physical attacks is of serious concerns of cryptographic hardware designers. Introduction of SIFA invalidating several previously-thought-effective countermeasures, made this challenge even harder. Here in this work we deal with error correction, and introduce a methodology which shows, depending on the selected adversary model, how to correctly embed error-correcting codes in a cryptographic implementation. Our construction guarantees the correction of faults, in any location of the circuit and at any clock cycle, as long as they fit into the underlying adversary model. Based on case studies evaluated by open-source fault diagnostic tools, we claim protection against SIFA.

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.

Certificateless signature was proposed by Al-Riyami and Paterson to eliminate the certificate management in the public-key infrastructures and solve the key escrow problem in the identity-based signature. In 2007, Hu et al. proposed a generic construction of certificateless signature. They construct certificateless signature scheme from any standard identity-based signature and signature scheme. However, their security reduction is loose; the security of the constructed scheme depends on the number of users. In this paper, we show that their construction can achieve tight security if the underlying signature scheme is existentially unforgeable under adaptive chosen-message attacks in the multi-user setting with adaptive corruptions. Moreover, we instantiate a tightly-secure certificateless signature scheme without pairing, whose security is independent of the number of users. Best of our knowledge, this scheme is the first tightly-secure certificateless signature scheme.