International Association
for Cryptologic Research

Solving the equation $P_a(X):=X^{q+1}+X+a=0$ over finite field $\GF{Q}$, where $Q=p^n, q=p^k$ and $p$ is a prime, arises in many different contexts including finite geometry, the inverse Galois problem \cite{ACZ2000}, the construction of difference sets with Singer parameters \cite{DD2004}, determining cross-correlation between $m$-sequences \cite{DOBBERTIN2006,HELLESETH2008} and to construct error-correcting codes \cite{Bracken2009}, as well as to speed up the index calculus method for computing discrete logarithms on finite fields \cite{GGGZ2013,GGGZ2013+} and on algebraic curves \cite{M2014}.

Subsequently, in \cite{Bluher2004,HK2008,HK2010,BTT2014,Bluher2016,KM2019,CMPZ2019,MS2019}, the $\GF{Q}$-zeros of $P_a(X)$ have been studied: in \cite{Bluher2004} it was shown that the possible values of the number of the zeros that $P_a(X)$ has in $\GF{Q}$ is $0$, $1$, $2$ or $p^{\gcd(n, k)}+1$. Some criteria for the number of the $\GF{Q}$-zeros of $P_a(x)$ were found in \cite{HK2008,HK2010,BTT2014,KM2019,MS2019}. However, while the ultimate goal is to identify all the $\GF{Q}$-zeros, even in the case $p=2$, it was solved only under the condition $\gcd(n, k)=1$ \cite{KM2019}.

We discuss this equation without any restriction on $p$ and $\gcd(n,k)$. New criteria for the number of the $\GF{Q}$-zeros of $P_a(x)$ are proved. For the cases of one or two $\GF{Q}$-zeros, we provide explicit expressions for these rational zeros in terms of $a$. For the case of $p^{\gcd(n, k)}+1$ rational zeros, we provide a parametrization of such $a$'s and express the $p^{\gcd(n, k)}+1$ rational zeros by using that parametrization.

We show that many symmetric cryptography primitives would not be less safe with significantly fewer rounds. To support this claim, we review the cryptanalysis progress in the last 20 years, examine the reasons behind the current number of rounds, and analyze the risk of doing fewer rounds. Advocating a rational and scientific approach to round numbers selection, we propose revised number of rounds for AES, BLAKE2, ChaCha, and SHA-3, which offer more consistent security margins across primitives and make them much faster, without increasing the security risk.

Almost perfect nonlinear (APN) and almost bent (AB) functions are integral components of modern block ciphers and play a fundamental role in symmetric cryptography. In this paper, we describe a procedure for searching for quadratic APN functions with coefficients in GF(2) over the finite fields GF(2^n) and apply this procedure to classify all such functions over GF(2^n) with n up to 9. We discover two new APN functions (which are also AB) over GF(2^9) that are CCZ-inequivalent to any known APN function over this field. We also verify that there are no quadratic APN functions with coefficients in GF(2) over GF(2^n) with n between 6 and 8 other than the currently known ones.

In 2017, Ward Beullens et al. submitted Lifted Unbalanced Oil and Vinegar (LUOV), a signature scheme based on the famous multivariate public key cryptosystem (MPKC) called Unbalanced Oil and Vinegar (UOV), to NIST for the competition for post-quantum public key scheme standardization. The defining feature of LUOV is that, though the public key $\mathcal{P}$ works in the extension field of degree $r$ of $\mathbb{F}_2$, the coefficients of $\mathcal{P}$ come from $\mathbb{F}_2$. This is done to significantly reduce the size of $\mathcal{P}$. The LUOV scheme is now in the second round of the NIST PQC standardization process. In this paper we introduce a new attack on LUOV. It exploits the "lifted" structure of LUOV to reduce direct attacks on it to those over a subfield.

While end-to-end encryption protocols with strong security are known and widely used in practice, designing a protocol that scales efficiently to large groups and enjoys similar security guarantees remains an open problem. The only known approaches to date are ART (Cohn-Gordon et al., CCS18) and TreeKEM (IETF, The Messaging Layer Security Protocol, draft). ART enjoys a security proof, albeit with a superexponential bound, and is not dynamic enough for practical purposes. TreeKEM has not been proven secure at this point and can suffer some efficiency issues due to dynamic group operations (i.e. adding and removing users). As a first contribution we present a variant of TreeKEM, that we call Tainted TreeKEM, which can be more efficient than TreeKEM depending on the distribution of add and remove operations. Our second contribution is a security proof for Tainted TreeKEM (and also TreeKEM) with a meaningful security bound against active and adaptive adversaries, showing that the protocol supports post compromise security and forward security. Concretely, we achieve an only slightly superpolynomial security loss of q^{\log\log(n)}, where n is the group size and q the total number of (update/remove/invite) operations.

Fine-grained cryptographic primitives are secure against adversaries with bounded resources and can be computed by honest users with less resources than the adversaries. In this paper, we revisit the results by Degwekar, Vaikuntanathan, and Vasudevan in Crypto 2016 on fine-grained cryptography and show constructions of three key fundamental fine-grained cryptographic primitives: one-way permutations, hash proof systems (which in turn implies a public-key encryption scheme against chosen chiphertext attacks), and trapdoor one-way functions. All of our constructions are computable in $\mathsf{NC}^1$ and secure against (non-uniform) $\mathsf{NC}^1$ circuits under the widely believed worst-case assumption $\mathsf{NC}^1 \subsetneq \oplus \mathsf{L/poly}$.

The existing power trace extractors consider the case that the number of power traces owned by the attacker is sufficient to guarantee his successful attacks, and the goal of power trace extraction is to lower the complexity rather than increase the success rates. Although having strict theoretical proofs, they are too simple and leakage characteristics of POIs have not been thoroughly analyzed. They only maximize the variance of data-dependent power consumption component and ignore the noise component, which results in very limited SNR to improve and seriously affects the performance of extractors. In this paper, we provide a rigorous theoretical analysis of SNR of power traces, and propose a novel SNR-centric extractor, named Shortest Distance First (SDF), to extract power traces with smallest the estimated noise by taking advantage of known plaintexts. In addition, to maximize the variance of the exploitable component while minimizing the noise, we refer to the SNR estimation model and propose another novel extractor named Maximizing Estimated SNR First (MESF). Finally, we further propose an advanced extractor called Mean optimized MESF (MMESF) that exploits the mean power consumption of each plaintext byte value to more accurately and reasonably estimate the data-dependent power consumption of the corresponding samples. Experiments on both simulated power traces and measurements from an ATmega328p micro-controller demonstrate the superiority of our new extractors.

We present efficient Zero-Knowledge Proofs of Knowledge (ZKPoK) for linear and multiplicative relations among secret messages hidden as Ring Learning With Errors (RLWE) samples. Messages are polynomials in $\mathbb{Z}_q[x]/\left<x^{n}+1\right>$ and our proposed protocols for a ZKPoK are based on the celebrated paper by Stern on identification schemes using coding problems (Crypto'93). Our $5$-move protocol achieves a soundness error slightly above $1/2$ and perfect Zero-Knowledge.

As an application we present Zero-Knowledge Proofs of Knowledge of relations between committed messages. The resulting commitment scheme is perfectly binding with overwhelming probability over the choice of the public key, and computationally hiding under the RLWE assumption. Compared with previous Stern-based commitment scheme proofs we decrease computational complexity, improve the size of the parameters and reduce the soundness error of each round.

Identity-based encryption (IBE) is a powerful mechanism for maintaining security. However, systems based on IBE are unpopular when compared with those of the public-key encryption (PKE). In our opinion, one of the reasons is a gap between theory and practice. For example, a generic transformation of weakly/strongly robust IBE from any IBE has been proposed by Abdalla et al., no robust IBE scheme is explicitly given. This means that, theoretically, anyone can construct a weakly/strongly robust IBE scheme by employing this transformation. However, this seems not easily applicable to non-cryptographers. In this paper, we first introduce the Gentry IBE scheme constructed over Type-3 pairings by employing the transformation proposed by Abe et al., and second we explicitly give strongly/weakly robust Gentry IBE schemes by employing the Abdalla et al. transformation. Finally, we show its implementation result and show that we can add strong robustness to the Gentry IBE scheme with a very few additional costs. We employ the mcl library to support a Barreto-Naehrig curve defined over the 462-bit prime. The encryption requires about 5 ms, whereas the decryption requires about 9 ms.

Blockchain which realize state machine replication (SMR) is widely studied recently as the fundamental building block of decentralized cryptocurrency and smart contract which need consensus mechanism in the global scale public trustless network. In such situation larger resiliency (e.g., minority fault)of the protocol is favorable, that motivate some research on synchronous protocol which have been studied only on the theoretical level but not for realistic use. Abraham et al. published a synchronous SMR protocol called Sync Hotstuff at ePrint (which will appear in IEEE S&P 2020) which is extremely simple and practical. It achieve $2\Delta$ latency which is near optimal in a synchronous model, and without lock-step execution its throughput is comparable to that of partially synchronous protocols. They present not only for standard synchronous model but for weaker model called mobile sluggish model which is more realistic. And it also adopts optimistic responsive mode where its latency is independent of $\Delta$. However, there is a critical security vulnerability. In this paper, we present force-locking attack on Sync Hotstuff. This attack violate safety of the protocol for standard synchronous model, and liveness of all versions of the protocol including for the mobile sluggish model and with responsive mode. This attack is not only a specific attack on Sync Hotstuff but a general form of attack scheme in the blockchain protocol we call force-locking. We then present some refinements to prevent this attack. Our modification remove its security vulnerability without any performance compromises. We also give formal proofs of security for each model.

Event date: 8 July to 10 July 2020
Submission deadline: 1 March 2020
Notification: 15 April 2020

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, and Dr. Tung Chou (joining soon), 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 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:

Contact:

Bo-Yin Yang by at crypto dot tw

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

We are seeking research scientists and post-doctoral fellows with high impact journal publications. Research scientists are required to have been awarded a doctoral degree for more than five years and work in Korea for 6 months - 3 years. Post-doctoral fellows are required to have been awarded a doctoral degree within the past five years as of May 31, 2020 and work in Korea for 3-5 years. Please email with subject ‘Research fellow position’ statement of research and CV with publication list to Prof. Hwang.

Closing date for applications:

Contact: Prof. Seong Oun Hwang (seongoun.hwang@gmail.com)

More information: http://shinan.hongik.ac.kr/~sohwang/index_e.htm

In this work, we study the computation and communication costs and their possible trade-offs in existing constructions for private information retrieval (PIR), including schemes based on homomorphic encryption and the Gentry--Ramzan PIR (ICALP'05). We present MulPIR, a PIR construction which uses somewhat homomorphic encryption in a new way that provides a better trade-off between communication and computation, and for the first time enables the implementation of PIR with full recursion. Our construction leverages optimizations from SealPIR (S&P'18) and extends them with new packing and compression techniques. We also present improvements for the Gentry--Ramzan PIR that reduce significantly the computation cost, the main overhead for this scheme, which achieves optimal communication in several settings. We further show how to efficiently construct PIR for sparse databases. Our constructions support batching for multi-queries as well as symmetric PIR. We finally implement several PIR constructions and present a comprehensive comparison of their communication and computation overheads, as well as a cost analysis assuming a standard price setting for CPU power and bandwidth.

We present a new succinct zero knowledge argument scheme for layered arithmetic circuits without trusted setup. The prover time is $O(C + n \log n)$ and the proof size is $O(D \log C + \log^2 n)$ for a $D$-depth circuit with $n$ inputs and $C$ gates. The verification time is also succinct, $O(D \log C + \log^2 n)$, if the circuit is structured. Our scheme only uses lightweight cryptographic primitives such as collision-resistant hash functions and is plausibly post-quantum secure. We implement a zero knowledge argument system, Virgo, based on our new scheme and compare its performance to existing schemes. Experiments show that it only takes 53 seconds to generate a proof for a circuit computing a Merkle tree with 256 leaves, at least an order of magnitude faster than all other succinct zero knowledge argument schemes. The verification time is 50ms, and the proof size is 253KB, both competitive to existing systems. Underlying Virgo is a new transparent zero knowledge verifiable polynomial delegation scheme with logarithmic proof size and verification time. The scheme is in the interactive oracle proof model and may be of independent interest.

In this work we study metric properties of the well-known family of binary Reed-Muller codes. Let $A$ be an arbitrary subset of the Boolean cube, and $\widehat{A}$ be the metric complement of $A$ --- the set of all vectors of the Boolean cube at the maximal possible distance from $A$. If the metric complement of $\widehat{A}$ coincides with $A$, then the set $A$ is called a {\it metrically regular set}. The problem of investigating metrically regular sets appeared when studying {\it bent functions}, which have important applications in cryptography and coding theory and are also one of the earliest examples of a metrically regular set. In this work we describe metric complements and establish metric regularity of the codes $\mathcal{RM}(0,m)$ and $\mathcal{RM}(k,m)$ for $k \geqslant m-3$. Additionally, metric regularity of the $\mathcal{RM}(1,5)$ code is proved. Combined with previous results by Tokareva N. (2012) concerning duality of affine and bent functions, this proves metric regularity of most Reed-Muller codes with known covering radius. It is conjectured that all Reed-Muller codes are metrically regular.

Vélu's formulas for computing isogenies over Weierstrass model of elliptic curves has been extended to other models of elliptic curves such as the Huff model, the Edwards model and the Jacobi model of elliptic curves. This work continues this line of research by providing efficient formulas for computing isogenies over elliptic curves of Hessian form. We provide explicit formulas for computing isogenies of degree 3 and isogenies of degree l not divisible by 3. The theoretical cost of computing these maps in this case is slightly faster than the case with other curves. We also extend the formulas to obtain isogenies over twisted and generalized Hessian forms of elliptic curves. The formulas in this work have been verified with the Sage software and are faster than previous results on the same curve.

We present an advanced encoding framework for predicate encryption (PE) in prime order groups. Our framework captures a wider range of adaptively secure PE schemes such as non-monotonic attribute-based encryption by allowing PE schemes to have more flexible structures. Prior to our work, frameworks featuring adaptively secure PE schemes in prime order groups require strong structural restrictions on the schemes. In those frameworks, exponents of public keys and master secret keys of PE schemes, which are also referred to as common variables, must be linear. In our work, we introduce a modular framework which includes non-linear common variables in PE schemes. First, we formalize non-linear structures which can appear in PE by improving Attrapadung's pair encoding framework (Eurocrypt'14). Then, we provide a generic compiler that features encodings under our framework to PE schemes in prime order groups. Particularly, the security of our compiler is proved by introducing a new technique which decomposes common variables into two types and makes one of them be shared between semi-functional and normal spaces on processes of the dual system encryption to mitigate the linear restriction. As instances of our new framework, we introduce new attribute-based encryption schemes supporting non-monotonic access structures, namely non-monotonic ABE, in prime order groups. We introduce adaptively secure non-monotonic ABE schemes having either short ciphertexts (if KP-ABE) or short keys (if CP-ABE) for the first time. Additionally, we introduce the first non-monotonic ABE schemes supporting both adaptive security and multi-use of attributes property in prime order groups.

Leakage detection seeking the evidence of sensitive data dependencies in the side-channel traces instead of trying to recover the sensitive data directly under the enormous efforts with numerous leakage models and state-of-the-art distinguishers can provide a fast preliminary security assessment on the cryptographic devices for designers and evaluators. Therefore, it is a popular topic in recent side-channel research of which the Welch's $t$-test-based Test Vector Leakage Assessment (TVLA) methodology is the most widely used one. However, the TVLA is not always the best option under all kinds of conditions (as we can see in the latter section of this paper). Kolmogorov-Smirnov test is a well-known nonparametric method for statistical analysis to determine whether the samples are from the same distribution by analyzing the cumulative distribution. It has been proposed into side-channel analysis as a successful distinguisher. This paper proposes---to our knowledge, for the first time---Kolmogorov-Smirnov test as a new method for leakage detection. Besides, we propose two implementations to speed up the KS leakage detection procedure. Experimental results on simulated leakage with various parameters and the practical traces verify that KS is an effective and robust leakage detection tool and the comprehensive comparison with TVLA shows that KS-based leakage detection can be a right-hand supplement to TVLA when performing the side-channel assessment.

While several works have explored the application of deep learning for efficient profiled side-channel analysis, explainability or in other words what neural networks learn remains a rather untouched topic. As a first step, this paper explores the Singular Vector Canonical Correlation Analysis (SVCCA) tool to interpret what neural networks learn while training on different side-channel datasets, by concentrating on deep layers of the network. Information from SVCCA can help, to an extent, with several practical problems in a profiled side-channel analysis like portability issue and criteria to choose a number of layers/neurons to fight portability, provide insight on the correct size of training dataset and detect deceptive conditions like over-specialization of networks.