International Association
for Cryptologic Research

Constructions and equivalence of APN functions play a significant role in the research of cryptographic functions. On finite fields of characteristic 2, 6 families of power APN functions and 14 families of polynomial APN functions have been constructed in the literature. However, the study on the equivalence among the aforementioned APN functions is rather limited to the equivalence in the power APN functions. Meanwhile, the theoretical analysis on the equivalence between the polynomial APN functions and the power APN functions, as well as the equivalence in the polynomial APN functions themselves, is far less studied. In this paper, we give the theoretical analysis on the inequivalence in 8 known families of polynomial APN functions and power APN functions.

Ethereum Research team has proposed a family of Casper blockchain consensus protocols. It has been shown in the literature that the Casper Friendly Finality Gadget (Casper FFG) cannot achieve liveness property in partially synchronous networks such as the Internet environment. The ``Correct-by-Construction'' family of Casper blockchain consensus protocols (CBC Casper) has been proposed as a finality gadget for the future Proof-of-Stake (PoS) based Ethereum blockchain. Unfortunately, no satisfactory/constructive finality rules have been proposed for CBC Casper and no satisfactory liveness property has been obtained for CBC Casper. Though it is commonly/widely believed in the community that CBC Casper could not achieve liveness property in asynchronous networks, this paper provides a surprising result by proposing the first CBC Casper protocol that achieves liveness property against t=n/5 Byzantine participants in completely asynchronous networks. Our protocol can also be considered as an improvement of the seminal work by Ben-Or. That is, Ben-Or's BFT protocol converges in exponential steps in asynchronous networks. Our result show that the revised Ben-Or's BFT protocol could converge in constant steps with the identical Byzantine fault tolerance threshold.

Isogeny-based key establishment protocols are believed to be resistant to quantum cryptanalysis. Two such protocols---supersingular isogeny Diffie-Hellman (SIDH) and commutative supersingular isogeny Diffie-Hellman (CSIDH)---are of particular interest because of their extremely small public key sizes compared with other post-quantum candidates. Although SIDH and CSIDH allow us to achieve key establishment against passive adversaries and authenticated key establishment (using generic constructions), there has been little progress in the creation of provably-secure isogeny-based password-authenticated key establishment protocols (PAKEs). This is in stark contrast with the classical setting, where the Diffie-Hellman protocol can be tweaked in a number of straightforward ways to construct PAKEs, such as EKE, SPEKE, PAK (and variants), J-PAKE, and Dragonfly. Although SIDH and CSIDH superficially resemble Diffie-Hellman, it is often difficult or impossible to ``translate'' these Diffie-Hellman-based protocols to the SIDH or CSIDH setting; worse still, even when the construction can be ``translated,'' the resultant protocol may be insecure, even if the Diffie-Hellman based protocol is secure. In particular, a recent paper of Terada and Yoneyama and ProvSec 2019 purports to instantiate encrypted key exchange (EKE) over SIDH and CSIDH; however, there is a subtle problem which leads to an offline dictionary attack on the protocol, rendering it insecure. In this work we present man-in-the-middle and offline dictionary attacks on isogeny-based PAKEs from the literature, and explain why other classical constructions do not ``translate'' securely to the isogeny-based setting.

Irreducible polynomials or IPs have many applications in the field of computer science and information technology. Algorithms in artificial intelligence and substitution boxes in cryptographic ciphers are some evident example of such important applications. But till now the study is mostly limited to the binary Galois field GF prime two and extension q . Some works are there to generate IPs over some non-binary Galois field GF prime p and extension q where p is the prime modulus and p greater than two but the maximum value of p is not more than thirteen and the maximum value of extension q is not more than four. In this paper a new algorithm to search for monic irreducible polynomials over extended Galois field GF prime p and extension q entitled as Composite Algorithm is introduced to computer scientists. Here all possible set of two monic elemental polynomials or EPs one one with highest degree less than equal to q minus one divided by two (for odd value of q) and less than equal to q divided by two (for even value of q) is multiplied over the Galois field GF prime p and extension q to one with highest degree greater than equal to q minus one divided by two (for odd value of q) and greater than q divided by two (for even value of q). All resultant monic polynomials are then divided over the Galois field GF prime p and extension q by a monic basic polynomial or BP one. If for all resultant polynomials the residue is one for a monic BP then the monic BP is termed as monic IP. The time complexity of the said algorithm is prove to be the best among existing such algorithms and efficient of all among them.

In modern ciphers of commercial computer cryptography 4-bit crypto substitution boxes or 4-bit crypto S-boxes are of utmost importance since the late sixties. Since then the 4 bit Boolean functions (BFs) are proved to be the best tool to generate the said 4-bit crypto S-boxes. In this paper the crypto related properties of the 4-bit BFs such as the algebraic normal form (ANF) of the 4-bit BFs, the balancedness, the linearity, the nonlinearity, the affinity and the non-affinity of the 4-bit BFs and the strict avalanche criterion (SAC) of 4-bit BFs are studied in detail. An exhaustive study of 4-bit BFs with some new observations and algorithms on SAC of 4-bit BFs is also reported in this paper. A bit later in the end of nineties the Galois field polynomials over Galois field GF(28) are in use to generate the 8-bit crypto S-box of the Advance Encryption Standard (AES). A detailed study on generation of the 4-bit crypto S-boxes with such Galois field polynomials over the binary as well as non-binary extended Galois fields is also given in this paper. The generated 4-bit crypto S-boxes are analyzed with four cryptanalysis techniques and the well-defined SAC algorithms of 4-bit crypto S-boxes to search for the best possible 4-bit crypto S-boxes. Some existing 4-bit crypto S-boxes like the 32 4-bit crypto S-boxes of the Data Encryption Standard (DES) and the four 4-bit crypto S-boxes of the two variants of the Lucifer are analyzed to report the weakness of such S-boxes. A comparative study of the ancient as well as the modern 4-bit crypto S-boxes with the generated 4-bit crypto S-boxes proves the said generated 4-bit crypto S-boxes to be the best possible one.

In modern era of computer science there are many applications of the polynomials over finite fields especially of the polynomials over extended Galois fields GF(p^q) where p is the prime modulus and q is the extension of the said Galois field, in the generation of the modern algorithms in the computer science, the soft computation, the cryptology and the cryptanalysis and especially in generation of the S-boxes of the cryptographic block and stream ciphers. The procedure and the algorithms of the subtraction and the division of the two Galois field polynomials over the Galois field GF(p^q) was remained untouched to the researchers of the applications of finite field theory in the computer science. In this paper the procedure and algorithms to subtract and divide the two Galois field polynomials over Galois field GF(p^q) or the two Galois field numbers over the Galois field GF(p^q) are introduced in detail. If a monic basic polynomial over the Galois field GF(p^q) (BP) [1] is divisible by any of the monic elemental polynomials over the Galois field GF(p^q) (EP) [1] except the constant polynomials (CPs) [1] over the Galois field GF(p^q) then the monic BP over the Galois field GF(p^q) is termed as the monic reducible polynomial (RP) [1] over the Galois field GF(pq) and if a monic BP over the Galois field GF(p^q) is not divisible to any of the EPs over the Galois field GF(p^q) except the CPs over the Galois field GF(p^q) or more specifically to any monic EP over the Galois field GF(p^q) with half of the degree of the concerned monic BP over the Galois field GF(p^q) then the monic BP over Galois field GF(p^q) is called as the irreducible polynomial (IP) [1] over the Galois field GF(p^q). Here the common algorithm to generate all the monic IPs over the Galois field GF(p^q) is introduced. The time complexity analyses of the algorithms prove the said algorithms to be less time consuming and efficient

We introduce a generalization of substitution permutation networks using quasigroups. Then, we prove that for quasigroups isotopic with a group $\mathbb{G}$, the complexity of mounting a differential attack against our generalization is the same as attacking a substitution permutation network based on $\mathbb{G}$. Although the result is negative, we believe that the design can be instructional for teaching students that failure is a natural part of research. Also, we hope to prevent others from making the same mistake by showing where such a path leads.

Over the past 20 years, the efficiency of secure multi-party protocols has been greatly improved. While the seminal protocols from the late 80's require a communication of $\Omega(n^6)$ field elements per multiplication among $n$ parties, recent protocols offer linear communication complexity. This means that each party needs to communicate a constant number of field elements per multiplication, independent of $n$.

However, these efficient protocols only offer active security, which implies that at most $t<n/3$ (perfect security), respectively $t<n/2$ (statistical or computational security) parties may be corrupted. Higher corruption thresholds (i.e., $t\geq n/2$) can only be achieved with degraded security (unfair abort), where one single corrupted party can prevent honest parties from learning their outputs.

The aforementioned upper bounds ($t<n/3$ and $t<n/2$) have been circumvented by considering mixed adversaries (Fitzi et al., Crypto' 98), i.e., adversaries that corrupt, at the same time, some parties actively, some parties passively, and some parties in the fail-stop manner. It is possible, for example, to achieve perfect security even if $2/3$ of the parties are faulty (three quarters of which may abort in the middle of the protocol, and a quarter may even arbitrarily misbehave). This setting is much better suited to many applications, where the crash of a party is more likely than a coordinated active attack.

Surprisingly, since the presentation of the feasibility result for the mixed setting, no progress has been made in terms of efficiency: the state-of-the-art protocol still requires a communication of $\Omega(n^6)$ field elements per multiplication.

In this paper, we present a perfectly-secure MPC protocol for the mixed setting with essentially the same efficiency as the best MPC protocols for the active-only setting. For the first time, this allows to tolerate faulty majorities, while still providing optimal efficiency. As a special case, this also results in the first fully-secure MPC protocol secure against any number of crashing parties, with optimal (i.e., linear in $n$) communication. We provide simulation-based proofs of our construction.

This is a fully-funded Ph.D. position for a UK/EU/International student (tuition fees plus stipend) to pursue a Ph.D. research degree in the Department of Computer Science, University of Warwick. Note that for international students, the overseas tuition gap will be covered as well.

The project is in the area of security and cryptography, in particular, investigating next-generation cryptocurrency that is more scalable, privacy-preserving, and usable than what we have today.

An ideal candidate should have excellent undergraduate and master degrees (equivalent to at least a UK 2.1) in Computer Science or relevant disciplines such as Mathematics and Engineering; a solid mathematical background as well as strong programming skills; experience in security research.

The closing date for application is 30 April 2020.

Interested candidates are encouraged to apply as early as possible. First, express your interest by sending your CV to Prof Feng Hao (feng.hao@warwick.ac.uk). If your background is found suitable, you will be directed to make a formal application. All formal applications will need to be made online through https://warwick.ac.uk/study/postgraduate/apply/research/.

Further information about the research environment: The Department of Computer Science, University of Warwick is one of the leading CS departments in the UK. In the latest 2014 REF (Research Excellence Framework) assessment participated by all UK universities, Warwick Computer Science is ranked the 1st for research output, 2nd for research impact, and 2nd overall among 89 CS departments in the UK. The University of Warwick is consistently ranked among the top 10 universities in the UK. It is also known for its beautiful campus, friendly social environment, vivid student lives, and easy transport links to all major cities in the UK including London.

Closing date for applications:

Contact: Professor Feng Hao

More information: https://warwick.ac.uk/fac/sci/dcs/research/doctoralstudies/fundingadvice/researchstudentships/?newsItem=8a17841b70e3f5d8

We are looking for candidates for 1 Research Fellow / postdoc position (from fresh post-docs to senior research fellows, flexible contract duration) on symmetric-key cryptography and/or side-channel analysis. Candidates are expected to have a proven record of publications in top cryptography/security venues. Salaries are competitive and are determined according to the successful applicants accomplishments, experience and qualifications. Interested applicants should send their detailed CVs, cover letter and references to Prof. Thomas Peyrin (thomas.peyrin@ntu.edu.sg). Review of applications starts immediately and will continue until positions are filled.

Closing date for applications:

Contact: Thomas Peyrin (thomas.peyrin@ntu.edu.sg)

The Security and Networking Lab (SECAN-Lab, https://secan-lab.uni.lu/) at the University of Luxembourg offers a full-time position for a PhD candidate (3 years, with a possible extension of 1 year) in the area of Application-Driven Cryptographic Protocols, in particular Privacy-Preserving Protocols. Potential application domains include Mobile Payments, Vehicular Networks, Autonomous Driving, etc. We are looking for an ambitious candidate with an excellent Master’s degree (top 10%) in Computer Science, Mathematics, Physics, or Electrical Engineering and a specialization in IT-Security and Cryptography. The position is embedded in an excellent international working environment comprising domain as well as cryptography experts, and comes with a competitive salary.

Closing date for applications:

Contact: Thomas Engel (thomas.engel@uni.lu), Andy Rupp (andy.rupp@uni.lu)

Nakamoto’s Bitcoin protocol inspired interest in the permissionless regime of distributed computing, in which participants may join and leave an internet-scale protocol execution at will, without needing to register with any authority. The permissionless regime poses challenges to the classical techniques used for consensus protocols, in which participants attempt to agree on a function of their inputs. Crucially, classical consensus techniques require honest participants to remain online and active, and to know an upperbound on the number of participants. Bitcoin addresses this issue by requiring Proof of Work in order to send a message in protocol, and other Bitcoin-inspired works have developed Proof of X variants to remediate the shortcomings of Proof of Work. We propose an abstraction for Proof of X called resources, inspired by how many variants are used in practice. We then show that given few additional assumptions, resources are sufficient to achieve consensus in the permissionless regime. In particular, with appropriate assumptions about resources, it is not necessary to know a bound on the network delay, participants do not need clocks, and participants can join and leave the execution arbitrarily. The core idea is to shift focus from the proportion of honest parties in an execution to the proportion of messages sent by honest parties. We formally model consensus protocols in the permissionless regime, and show how to parameterize a permissionless execution using only the long-term proportion of resources acquired by honest participants and an upperbound on the rate at which resources enter the system, relative to the maximum network delay (without needing to know the network delay). Along the way, we provide a generalized definition of blockchains which we call graph consensus. We present a protocol in the permissionless regime that achieves graph consensus, even when resources enter the system at high rates, but the required honest majority increases with the rate. We show how the protocol can be modified slightly to achieve one-bit consensus. Finally, we show that for every graph consensus protocol that outputs a majority of honest vertices there exists a one-bit consensus protocol.

The ElGamal cryptosystem is one of the most widely used public-key cryptosystems that depends on the difficulty of computing the discrete logarithms over finite fields. Over the years, the original system has been modified and altered in order to achieve a higher security and efficiency. In this paper, a generalization for the original ElGamal system is proposed which also relies on the discrete logarithm problem. The encryption process of the scheme is improved such that it depends on the prime factorization of the plaintext. Modular exponentiation is taken twice during the encryption; once with the number of distinct prime factors of the plaintext and then with the secret encryption key. If the plaintext consists of only one distinct prime factor, then the new method is similar to that of the basic ElGamal algorithm. The proposed system preserves the immunity against the Chosen Plaintext Attack (CPA).

Using a novel class of single bit one-way trapdoor functions we construct a theoretical probabilistic public key encryption scheme that has many interesting properties. These functions are constructed from binary quadratic forms and rational quartic reciprocity laws. They are not based on class group operations nor on universal one-way hash functions. Inverting these functions appears to be as difficult as factoring, and other than factoring, we know of no reductions between this new number theory problem and the standard number theoretic problems used cryptographically.

By using quartic reciprocity properties there is less information leakage than with quadratic reciprocity based schemes and consequently this encryption scheme appears to be completely non-malleable as defined by M. Fischlin (2005) and strongly plaintext aware and secret-key aware as well as defined by M. Barbosa and P. Farshim (2009). Assuming that our one-way trapdoor function is computationally hard to invert, then this encryption scheme is provably secure against adaptive chosen ciphertext attacks ($IND-CCA2$).

Decryption is fast, requiring just one modular multiplication and one Jacobi symbol evaluation. The encryption step is polynomial time, but slow, and there is a great deal of message expansion. The encryption step is amenable to parallelization, both across bits, as well as at the level of encrypting a single bit. The computational cost to break an encrypted bit can be optionally adjusted down on a per bit basis.

With no additional keys, multiple senders can individually join secret information to each encrypted bit without changing the parity of the encrypted bit. (Recovering this secret information is harder than recovering the private key.) Each sender can separately and publicly reveal their secret information without revealing the plaintext bit. The senders of the encrypted message bit can also individually authenticate they are senders without the use of a message authentication code and without revealing the plaintext bit.

We introduce the notion of a succinct blockchain, a replicated state machine in which each state transition (block) can be efficiently verified in constant time regardless of the number of prior transitions in the system. Traditional blockchains require verification time linear in the number of transitions. We show how to construct a succinct blockchain using recursively composed succinct non-interactive arguments of knowledge (SNARKs). Finally, we instantiate this construction to implement Coda, a payment system (cryptocurrency) using a succinct blockchain. Coda offers payment functionality similar to Bitcoin, with a dramatically faster verification time of 200ms making it practical for lightweight clients and mobile devices to perform full verification of the system’s history.

A zero-knowledge proof is a method by which one can prove knowledge of general non-deterministic polynomial (NP) statements. SNARKs are in addition non-interactive, short and cheap to verify. This property makes them suitable for recursive proof composition, that is proofs attesting to the validity of other proofs. Recursive proof composi- tion has been empirically demonstrated for pairing-based SNARKs via tailored constructions of expensive elliptic curves. We thus construct on top of the curve BLS12-377 a new pairing-friendly elliptic curve which is STNFS-secure and optimized for one layer composition. We show that it is at least five times faster to verify a composed SNARK proof on this curve compared to the previous state-of-the-art. We propose to name the new curve BW6-761.

The stream cipher ChaCha is an ARX type algorithm developed by Daniel Bernstein in 2008. Since its development, ChaCha has received a lot of attention and is currently being used in several systems. The most powerful cryptanalysis of reduced versions of this cipher was presented by Choudhuri and Maitra on FSE 2017 by using differential-linear cryptanalysis. In their work they show that is possible to obtain linear relations between bits from different rounds with high probability and use the proposed equations to create multi-bit differentials and improve previous attacks. In this work, we provide new linear approximations that can be used in a similar fashion but with increased efficiency. Therefore, we show that using these new equations is possible to improve the attacks against 6 and 7 rounds of ChaCha.

Differential power analysis (DPA) is a statistical analysis of the power traces of cryptographic computations. DPA has many applications including key-recovery on linear feedback shift register based stream ciphers. In 2017, Dobraunig et. al. presented a DPA on Keymill to uncover the bit relations of neighbouring bits in the shift registers, effectively reduces the internal state guessing space to 4-bit. In this work, we generalise the analysis methodology to uncover more bit relations on both linear feedback shift registers (LFSRs) and non-linear feedback shift registers (NLFSRs) and with application to fresh re-keying scheme --- LR-Keymill. In addition, we improve the DPA on Keymill by halving the data resources needed for the attack.

Groups of hidden order have gained a surging interest in recent years due to applications to cryptographic commitments, verifiable delay functions and zero knowledge proofs. Recently, Dobson and Galbraith ([DG20]) proposed Jacobians of genus three hyperelliptic curves as a suitable candidate for such a group. While this looks like a promising idea, certain Jacobians are less secure than others and hence, the curve has to be chosen with caution. In this short note, we explore the types of Jacobians that would be suitable for this purpose.

The efficiency of zero-knowledge protocols is measured by the round complexity. The construction of low round zero-knowledge protocols for any NP language has been a classical and open question.

In this paper, we focus on zero-knowledge protocols for NP with low round complexity under the augmented black-box simulation technique, in which the simulator has access to the verifier's secret information, and obtain positive results on 3-round zero-knowledge proofs and 2-round zero-knowledge arguments and proofs. More precisely, our contributions are five-fold: (i) we propose the notion of generalized claw-free function and the notion of trapdoor generalized claw-free function, and then we show a construction of trapdoor generalized claw-free function under the discrete logarithm assumption and the knowledge of exponent assumption, (ii) we propose the notion of completely extractable bit-commitment and give a construction of it from trapdoor generalized claw-free functions, (iii) we present a 3-round zero-knowledge proof for NP based on the completely extractable bit-commitment schemes and Yao's garbling circuit technique, (iv) we show a 2-round zero-knowledge argument for NP based on indistinguishable obfuscator, (v) we transform the basic 2-round honest verifier zero-knowledge proof protocol for quadratic non-residue into a 2-round zero-knowledge proof protocol.