International Association
for Cryptologic Research

The main approaches currently used to construct identity based encryption (IBE) schemes are based on bilinear mappings, quadratic residues and lattices. Among them, the most attractive approach is the one based on quadratic residues, due to the fact that the underlying security assumption is a well understood hard problem. The first such IBE scheme was constructed by Cocks and some of its deficiencies were addressed in subsequent works. In this paper, we will focus on two constructions that address the anonymity problem inherent in Cocks' scheme and we will tackle some of their incomplete theoretical claims. More precisely, we rigorously study Clear et. al and Zhao et. al's schemes and give accurate probabilities of successful decryption and identity detection in the non-anonymized version of the schemes. Also, in the case of Zhao \emph{et. al}'s scheme, we give a proper description of the underlying security assumptions.

Let \(q~=~2^n\), and let \(\mathcal{E} / \mathbb{F}_{q^{\ell}}\) be a generalized Galbraith--Lin--Scott (GLS) binary curve, with $\ell \ge 2$ and \((\ell, n) = 1\). We show that the GLS endomorphism on \(\mathcal{E} / \mathbb{F}_{q^{\ell}}\) induces an efficient endomorphism on the Jacobian \(\mathrm{Jac}_\mathcal{H}(\mathbb{F}_q)\) of the genus-\(g\) hyperelliptic curve \(\mathcal{H}\) corresponding to the image of the GHS Weil-descent attack applied to \(\mathcal{E} / \mathbb{F}_{q^\ell}\), and that this endomorphism yields a factor-$n$ speedup when using standard index-calculus procedures for solving the Discrete Logarithm Problem (DLP) on \(\mathrm{Jac}_\mathcal{H}(\mathbb{F}_q)\). Our analysis is backed up by the explicit computation of a discrete logarithm defined on a prime-order subgroup of a GLS elliptic curve over the field $\mathbb{F}_{2^{5\cdot 31}}$. A Magma implementation of our algorithm finds the aforementioned discrete logarithm in about $1,035$ CPU-days.

Luby and Rackoff used a Feistel cipher over bit strings to construct a pseudorandom permutation from pseudorandom functions in 1988 and in 2002, Patel, Ramzan, and Sundaram generalized the construction to arbitrary abelian groups. They showed that the 3-round Feistel cipher is not superpseudorandom over abelian groups but left as an open problem a proof for non-abelian groups. We give this proof.

Keywords: Feistel, non-abelian group, pseudorandom.

In this work we investigate how the choice of the key-expansion algorithm and its interaction with the round function affect the resistance of Simon-like ciphers against rotational-XOR (RX) cryptanalysis. We observe that among the key-expansion algorithms we consider, Simon is most resistant, while Simeck is much less so. Implications on lightweight ciphers design are discussed and open questions are proposed.

Deep learning techniques with neural networks are developing prominently in recent years and have been deployed in numerous applications. Despite their great success, in many scenarios it is important for the users to validate that the inferences are truly computed by legitimate neural networks with high accuracy, which is referred as the integrity of machine learning predictions. To address this issue, in this paper, we propose zkCNN, a zero knowledge proof scheme for convolutional neural networks (CNN). The scheme allows the owner of the CNN model to prove to others that the prediction of a data sample is indeed calculated by the model, without leaking any information about the model itself. Our scheme can also be generalized to prove the accuracy of a secret CNN model on public dataset.

Underlying zkCNN is a new sumcheck protocol for proving fast Fourier transforms and convolutions with a linear prover time, which is even faster than computing the result asymptotically. We also introduce several improvements and generalizations on the interactive proofs for CNN predictions, including verifying the convolutional layers, the activation function of ReLU and the max pooling. Our scheme is highly efficient in practice. It can scale to the large CNN of VGG16 with 15 million parameters and 16 layers. It only takes 163 seconds to generate the proof, which is 1000x faster than existing schemes. The proof size is 230 kilobytes, and the verifier time is only 172 milliseconds. Our scheme can further scale to prove the accuracy of the same CNN on 100 images.

Post-quantum cryptography (PQC) has a well-deserved NIST status. Our approach (R-Propping) replaces all numeric field arithmetic with GF(2^8) field operations. This method yields both classical and quantum secure protocols. The present work is dedicated to strengthening a chaotic Wolfram Class III cellular automata and discuss its usability as a cryptographical secure PRBG (pseudorandom bit generator), a building block for stream-ciphers, hashing, and other random numbers requiring protocols.

Classic Byzantine fault tolerant (BFT) protocols are designed for a specific timing model, most often one of the following: synchronous, asynchronous or partially synchronous. It is well known that the timing model and fault tolerance threshold present inherent trade-offs. Synchronous protocols tolerate up to $n/2$ Byzantine faults, while asynchronous or partially synchronous protocols tolerate only up to $n/3$ Byzantine faults. In this work, we generalize the fault thresholds of BFT and introduce a new problem called multi-threshold BFT. Multi-threshold BFT has four separate fault thresholds for safety and liveness under synchrony and asynchrony (or partial-synchrony), respectively. Decomposing the fault thresholds in this way allows us to design protocols that provide meaningful fault tolerance under both synchrony and asynchrony (or partial synchrony). We establish tight fault thresholds bounds for multi-threshold BFT and present protocols achieving them. As an example, we show a BFT state machine replication (SMR) protocol that tolerates up to $2n/3$ faults for safety under synchrony while tolerating up to $n/3$ faults for other scenarios (liveness under synchrony as well as safety and liveness under partial synchrony). This is strictly stronger than classic partially synchronous SMR protocols. We also present a general framework to transform known partially synchronous or asynchronous BFT SMR protocols to additionally enjoy the optimal $2n/3$ fault tolerance for safety under synchrony.

We introduce AOT, an anonymous communication system based on mix network architecture that uses oblivious transfer (OT) to deliver messages. Using OT to deliver messages helps AOT resist blending (n−1) attacks and helps AOT preserve receiver anonymity, even if a covert adversary controls all nodes in AOT. AOT comprises three levels of nodes, where nodes at each level perform a different function and can scale horizontally. The sender encrypts their payload and a tag, derived from a secret shared between the sender and receiver, with the public key of a Level-2 node and sends them to a Level-1 node. On a public bulletin board, Level-3 nodes publish tags associated with messages ready to be retrieved. Each receiver checks the bulletin board, identifies tags, and receives the associated messages using OT. A receiver can receive their messages even if the receiver is offline when messages are ready. Through what we call a "handshake" process, communicants can use the AOT protocol to establish shared secrets anonymously. Users play an active role in contributing to the unlinkability of messages: periodically, users initiate requests to AOT to receive dummy messages, such that an adversary cannot distinguish real and dummy requests.

Pravuil is a robust, secure, and scalable consensus protocol for a permissionless blockchain suitable for deployment in an adversarial environment such as the Internet. Pravuil circumvents previous shortcomings of other blockchains:

- Bitcoin’s limited adoption problem: as transaction demand grows, payment confirmation times grow much lower than other PoW blockchains

- higher transaction security at a lower cost

- more decentralisation than other permissionless blockchains

- impossibility of full decentralisation and the blockchain scalability trilemma: decentralisation, scalability, and security can be achieved simultaneously

- Sybil-resistance for free implementing the social optimum

- Pravuil goes beyond the economic limits of Bitcoin or other PoW/PoS blockchains, leading to a more valuable and stable crypto-currency

The Grover search algorithm accelerates the key search on the symmetric key cipher and the pre-image attack on the hash function. In order to perform the Grover search algorithm, the target algorithm should be implemented in a quantum circuit. With this motivation, we propose an optimal SM3 hash function in a quantum circuit. We focused on minimizing the use of qubits together with reducing the use of quantum gates. To do this, an on-the-fly approach is utilized for message expansion and compression function. In particular, the previous value is restored and used without allocating new qubits in the permutation operation. Finally, we estimate quantum resources required for the quantum pre-image attack based on the proposed SM3 hash function implementation in the quantum circuit.

The SM4 block cipher is a Chinese domestic crpytographic that was introduced in 2003. Since the algorithm was developed for the use in wireless sensor networks, it is mandated in the Chinese National Standard for Wireless LAN WAPI (Wired Authentication and Privacy Infrastructure). The SM4 block cipher uses a 128-bit block size and a 32-bit round key. This consists of 32 rounds and one reverse translation \texttt{R}. In this paper, we present the optimized implementation of the SM4 block cipher on 8-bit AVR microcontrollers, which are widely used in wireless sensor devices, and the optimized implementation of SM4 on 64-bit ARM processors with the parallel computation, which are widely used in smartphone and tablet. In the AVR microcontroller, it is implemented in three versions, including speed-optimization, memory-optimization, and code-optimization. As a result, speed-optimization, memory-optimization, and code-optimization achieved 205.2 cycles per byte, 213.3 cycles per byte and 207.4 cycles per byte, respectively. This is faster than the reference implementation written in C (1670.7 cycles per byte). The implementation on 64-bit ARM processors is 8.62 cycles per byte. This is faster than the reference C code implementation (120.07 cycles per byte).

Cloud storage services are top-rated, but there are often concerns about the security of the files there stored. Clouds-of-clouds or multi-clouds are being explored in order to improve that security. The idea is to store the files in several clouds, ensuring integrity and availability. Confidentiality, however, is obtained by encrypting the files with block ciphers that do not provide provable security. Secret sharing allows distributing files among the clouds providing information-theoretic security/secrecy. However, existing secret sharing schemes are space-inefficient (the size of the shares is much larger than the size of the secret) or purely theoretical. In this paper, we propose the first practical space-efficient secret sharing scheme that provides information-theoretic security, which we denominate PRactical Efficient Secret Sharing (PRESS). Moreover, we present the Secure CloUD storage (SCUD) service, a new cloud-of-clouds storage service that leverages PRESS to provide file confidentiality. Additionally, SCUD provides data integrity and availability, leveraging replication.

In this paper, we study sufficient conditions to improve the lower bound on the algebraic immunity of a direct sum of Boolean functions. We exhibit three properties on the component functions such that satisfying one of them is sufficient to ensure that the algebraic immunity of their direct sum exceeds the maximum of their algebraic immunities. These properties can be checked while computing the algebraic immunity and they allow to determine better the security provided by functions central in different cryptographic constructions such as stream ciphers, pseudorandom generators, and weak pseudorandom functions. We provide examples for each property and determine the exact algebraic immunity of candidate constructions.

Guillou-Quisquater (GQ) signature is an efficient RSA-based digital signature scheme amongst the most famous Fiat-Shamir follow-ons owing to its good simplicity. However, there exist two bottlenecks for GQ hindering its application in industry or academia: the RSA trapdoor $n=pq$ in the key generation phase and its high bandwidth caused by the storage-consuming representation of RSA group elements (3072 bits per one element in 128-bit security).

In this paper, we first formalize the definition and security proof of class group based GQ signature (CL-GQ), which eliminates the trapdoor in key generation phase and improves the bandwidth efficiency from the RSA-based GQ signature. Then, we construct a trustless GQ multi-signature scheme by applying non-malleable equivocable commitments and our well-designed compact non-interactive zero-knowledge proofs (NIZK). Our scheme has a well-rounded performance compared to existing multiparty GQ, Schnorr and ECDSA schemes, in the aspects of bandwidth (no range proof or multiplication-to-addition protocol required), rather few interactions (only 4 rounds in signing), provable security in \textit{dishonest majority model} and identifiable abort property. Another interesting finding is that, our NIZK is highly efficient (only one round required) by using the Bezout formula, and this trick can also optimize the ZK proof of Paillier ciphertext which greatly improves the speed of Yi's Blind ECDSA (AsiaCCS 2019).

Today's microprocessors often rely on microcode updates to address issues such as security or functional patches. Unfortunately, microcode update flexibility opens up new attack vectors through malicious microcode alterations. Such attacks share many features with hardware Trojans and have similar devastating consequences for system security. However, due to microcode's opaque nature, little is known in the open literature about the capabilities and limitations of microcode Trojans.

We introduce the design of a microcoded RISC-V processor architecture together with a microcode development and evaluation environment. Even though microcode typically has almost complete control of the processor hardware, the design of meaningful microcode Trojans is not straightforward. This somewhat counter-intuitive insight is due to the lack of information at the hardware level about the semantics of executed software. In three security case studies we demonstrate how to overcome these issues and give insights on how to design meaningful microcode Trojans that undermine system security. To foster future research and applications, we publicly release our implementation and evaluation platform.

In this paper, we study implementations of post-quantum signature schemes on resource-constrained devices. We focus on verification of signatures and cover NIST PQC round-3 candidates Dilithium, Falcon, Rainbow, GeMSS, and SPHINCS+. We assume an ARM CortexM3 with 8 kB of memory and 8 kB of flash for code; a practical and widely deployed setup in, for example, the automotive sector. This amount of memory is insufficient for most schemes. Rainbow and GeMSS public keys are too big; SPHINCS+ signatures do not fit in this memory. To make signature verification work for these schemes, we stream in public keys and signatures. Due to the memory requirements for efficient Dilithium implementations, we stream in the public key to cache more intermediate results. We discuss the suitability of the signature schemes for streaming, adapt existing implementations, and compare performance.

This paper considers the linear cryptanalyses of Authenticated Encryptions with Associated Data (AEADs) GIFT-COFB, SUNDAE-GIFT, and HyENA. All of these proposals take GIFT-128 as underlying primitives. The automatic search with the Boolean satisfiability problem (SAT) method is implemented to search for linear approximations that match the attack settings concerning these primitives. With the newly identified approximations, we launch key-recovery attacks on GIFT-COFB, SUNDAE-GIFT, and HyENA when the underlying primitives are replaced with 16-round, 17-round, and 16-round versions of GIFT-128. The resistance of GIFT-128 against linear cryptanalysis is also evaluated. We present a 24-round key-recovery attack on GIFT-128 with a newly obtained 19-round linear approximation. We note that the attack results in this paper are far from threatening the security of GIFT-COFB, SUNDAE-GIFT, HyENA, and GIFT-128.

To eliminate the unnecessary waste of energy and computing power in Bitcoin, in this paper, we develop a novel proof-of-stake consensus in the permissionless setting. Among other features, our design achieves the ``best possible'' unpredictability for permissionless proof-of-stake protocols. As shown by Brown-Cohen et al~(EC 2019), unpredictability property is critical for proof-of-stake consensus in the rational setting; the flip side of unpredictability property, i.e., predictability can be abused by the attackers for launching strengthened version of multiple attacks such as selfish-mining and bribing, against proof-of-stake systems.

We are inspired by Bitcoin's ``block-by-block'' design, and we show that a direct and natural mimic of Bitcoin's design via proof-of-stake is secure if the majority 73\% of stake is honest. Our result relies on an interesting upper bound of extending proof-of-stake blockchain we establish: players (who may extend all chains) can generate blockchain at most $2.72\times$ faster than playing the basic strategy of extending the longest chain.

We introduce a novel strategy called ``D-distance-greedy'' strategy, which enables us to construct a class of secure proof-of-stake blockchain protocols, against an \textbf{arbitrary} adversary, even assuming much smaller (than 73\% of) stake is honest. To enable a thorough security analysis in the cryptographic setting, we develop several new techniques: for example, to show the chain growth property, we represent the chain extension process via a Markov chain, and then develop a random walk on the Markov chain; to prove the common prefix property, we introduce a new concept called ``virtual chains'', and then present a reduction from the regular version of common prefix to ``common prefix w.r.t. virtual chains''.

Finally, we note that, ours is the first ``block-by-block'' style of proof-of-stake in the permissionless setting, naturally mimicking Bitcoin's design; it turns out that this feature, again allows us to achieve the ``best possible'' unpredictability property. Other existing provably secure permissionless proof-of-stake solutions are all in an ``epoch-by-epoch'' style, and thus cannot achieve the best possible unpredictability.

The Covid Pandemic has taken a toll on one of our young cryptographers and cybersecurity specialist Dr Nishant Sinha on 9th May, 2021. He was a thorough gentleman for whom no challenge was difficult.

Nishant was born on 22 Feb 1985. He completed his Bachelor's in 2009 from Biju Patnaik University of Technology, Odisha, in Computer Science and Engineering. He next post-graduated from the Centre for Development of Advanced Computing in 2012. He had a brief stint as an Assistant professor from April 2012 to Dec 2014. In the year 2015, he joined Indian Institute of Technology Roorkee for Ph. D., which he completed by the year 2018. During this time he was collaborating with Indian Statistical Institute, Kolkata too. His area of research was Cryptanalysis on Symmetric Ciphers. After the PhD he joined Robert Bosch Engineering and Business Solutions at Bangalore, where he surprised everybody by a remarkable transformation from a Cryptology Researcher to a Security Practitioner. We remember working with Nishant both in Academia and Industry. A link to his publication is at https://dblp.org/pid/07/201-3.html .

Nishant is missed by each of his colleagues. During the cryptology conferences and workshops in India, participants from all over the world were greeted by Nishant with his big and bright smile. That is why we think Nishant should be remembered at the IACR webpage. Our heart reaches out to his family - his mother, sister, wife and little baby daughter. We pray God almighty gives them the strength to overcome these difficult times. In the short span Nishant made his brilliance known to all of us. No doubt he leaves a void that we will never be able to fill. Yet we shall be guided and inspired by him especially his simplicity and ability to handle complicated things. May our friend find peace.

Sugata (IIT Roorkee), Shashwat (Bosch), Subhamoy (ISI Kolkata)

At the Faculty of Engineering and Science, Department of Mathematical Sciences one or more positions as Assistant Professor in Discrete Mathematics is open for appointment from 1st September 2021 or soon hereafter. The position is available for a period of three years. The Department of Mathematical Sciences houses three education programs, Mathematics, Mathematics-Economics, and Mathematics- Technology. Furthermore, several courses for programs in Engineering and Social Sciences are taught by the Department of Mathematical Sciences. Aalborg University is comprised of three campuses, Aalborg, Esbjerg, and Copenhagen. Teaching responsibilities may include courses at any of the three campuses. For more information about the department, please see: https://www.math.aau.dk/

JOB DESCRIPTION

Research areas will be within Coding Theory and Cryptography. A selected candidate will have a proven track record of promising research within Coding Theory, Cryptography, or related subjects in Discrete Mathematics.

The ability to contribute to the development of external collaboration and to secure external funding will be taken into account and the applicant is expected to have very good interpersonal skills. Special contributions to the development of educational and teaching related activities will be considered in the overall assessment. The selected candidate is expected to engage in acquiring external funding for research. This will involve collaboration with colleagues from the mathematics department and from other departments at Aalborg University. This includes funding for both theoretical research and for more applied and strategic research activities. Teaching will primarily be in the three mathematical programmes, but also in other study programmes at the university.

Please visit https://www.stillinger.aau.dk to see the full call text and to apply

Closing date for applications:

Contact: You may obtain further professional information from Professor Horia Cornean, phone: +45 9940 8879, e-mail: cornean@math.aau.dk or Head of Department Søren Højsgaard, phone: +45 9940 8801, e-mail: sorenh@math.aau.dk

More information: https://www.stillinger.aau.dk/vis-stilling/?vacancy=1150397