International Association
for Cryptologic Research

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

We are seeking an Ethereum Virtual Machine (EVM) execution engineer to help implement Subspace, a radically decentralized, next-generation blockchain written in Rust, using the Substrate framework. Subspace employs a novel proof-of-storage consensus algorithm and a decoupled execution framework, which allows it to scale far beyond existing blockchains, without sacrificing security or decentralization. Subspace Labs is an early-stage, venture-backed startup with a globally distributed team. To learn more visit our website or read the technical whitepaper.

Your Responsibilities

• Implement a decoupling of consensus and computation for an EVM style blockchain as described in our technical white paper.
• Develop a system of non-interactive fraud proofs based on an execution trace of incremental commitments to the global state root.
• Develop a VRF-based stake-weighted election mechanism for executors, distinct from the PoR-based space-weighted farmer election.

Basic Requirements

• Experience working with the internals of the EVM, ideally with Geth, Parity/OpenEthereum, or a Substrate based derivative.
• Theoretical background in distributed systems, such as consensus mechanisms, as well as cryptographic fundamentals.
• Strong knowledge of a modern systems programming language, such as Rust, C++, or Go and willing to learn Rust.

Nice to Have

• Familiarity with proof-of-stake consensus, finality gadgets, stateless blockchains, super light clients, and leading blockchain scalability proposals.
• Familiarity with the Rust language and its ecosystem
• Familiarity with Substrate and the Polkadot ecosystem
• A passion for decentralized, peer-to-peer systems and Web3 technologies

Benefits

• A remote work environment with a high degree of autonomy and agency
• You will play a critical role in implementing a new layer one blockchain
• A competitive salary with generous token and equity grants.

Closing date for applications:

Contact: Jeremiah Wagstaff

More information: https://jobs.lever.co/subspacelabs/9d8f9b6d-4141-4782-923a-2872a06c723e?lever-origin=applied&lever-source%5B%5D=IACR

We are seeking a peer-to-peer network engineer to help implement the Subspace Network, a radically decentralized, next-generation blockchain written in Rust, using the Substrate framework. Subspace employs a novel proof-of-storage consensus algorithm and a decoupled execution framework, which allows it to scale far beyond existing blockchains, without sacrificing security or decentralization. Subspace Labs is an early-stage, venture-backed startup with a globally distributed team. To learn more visit our website and read the technical whitepaper.

Your Responsibilities

• Implement a fault-tolerant, load-balanced, and efficiently-retrievable distributed file-system based on the specifications in our white paper.
• Implement a simplified and streamlined Kademlia Distributed Hash Table (K-DHT) to serve as an indexing layer for the Subspace Network.
• Develop a torrent-style synchronization service for new farmers and a tit-for-tat bandwidth sharing mechanism for existing farmers.

Basic Requirements

• Experience employing or implementing peer-to-peer protocols including gossip networks, distributed hash tables, or distributed file systems.
• Theoretical background in distributed systems, such as peer-to-peer networking, as well as cryptographic fundamentals.
• Strong knowledge of a modern systems programming language, such as Rust, C++, or Go and willing to learn Rust.

Nice to Have

• Familiarity with the LibP2P networking stack.
• Familiarity with the Rust language and its ecosystem
• Familiarity with Substrate and the Polkadot ecosystem
• A passion for decentralized, peer-to-peer systems and Web3 technologies

Benefits

• A remote work environment with a high degree of autonomy and agency
• You will play a critical role in implementing a new layer one blockchain
• A competitive salary with generous token and equity grants.

Closing date for applications:

Contact: Jeremiah Wagstaff

More information: https://jobs.lever.co/subspacelabs/6b2c3833-0bbb-409e-9484-049679390756?lever-origin=applied&lever-source%5B%5D=IACR

We are seeking a consensus protocol engineer to help implement the Subspace Network, a radically decentralized, next-generation blockchain written in Rust, using the Substrate framework. Subspace employs a novel proof-of-storage consensus algorithm and a decoupled execution framework, which allows it to scale far beyond existing blockchains, without sacrificing security or decentralization. Subspace Labs is an early-stage, venture-backed startup with a globally distributed team. To learn more visit our website (subspace.network) and read the technical whitepaper.

Your Responsibilities

• Implement a new Nakamoto style consensus algorithm based on a proof-of-useful-storage of the history of the blockchain itself.
• Decouple consensus and computation between two distinct classes of nodes, storage farmers and staked executors, through a system of fraud proofs.
• Implement a series of novel scalability proposals to increase throughput, decrease latency, and achieve fast finality in a permissionless setting.

Basic Requirements

• Experience implementing blockchain consensus protocols, especially Nakamoto style protocols based on proofs of work, stake, or space.
• Theoretical background in distributed systems, consensus algorithms, and cryptographic fundamentals with a focus on Nakamoto style consensus.
• Strong knowledge of a modern systems programming language, such as Rust, C++, or Go and willing to learn Rust.

Nice to Have

• Familiarity with the Rust language and its ecosystem
• Familiarity with Substrate and the Polkadot ecosystem
• Familiarity with proofs of space, storage, replication or space-time.
• A passion for decentralized, peer-to-peer systems and Web3 technologies

Benefits

• A remote work environment with a high degree of autonomy and agency
• You will play a critical role in implementing a new layer one blockchain
• A competitive salary with generous token and equity grants.

Closing date for applications:

Contact: Jeremiah Wagstaff

More information: https://jobs.lever.co/subspacelabs/d5d62ccb-eaaf-43f4-83ad-11ebff2ce3a0?lever-origin=applied&lever-source%5B%5D=IACR

This technical report provides extensive information for designing, implementing, fabricating, and validating CoPHEE: A Co-Processor for Partially Homomorphic Encrypted Execution, complementing the publication appearing in the 2019 IEEE Hardware-Oriented Security and Trust symposium.

We present an adaptive key recovery attack on the leveled homomorphic encryption scheme suggested by Li, Galbraith and Ma (Provsec 2016), which itself is a modification of the GSW cryptosystem designed to resist key recovery attacks by using a different linear combination of secret keys for each decryption. We were able to efficiently recover the secret key for a realistic choice of parameters using a statistical attack. In particular, this means that the Li, Galbraith and Ma strategy does not prevent adaptive key recovery attacks.

Non-malleable secret sharing (NMSS) schemes, introduced by Goyal and Kumar (STOC 2018), ensure that a secret $m$ can be distributed into shares $m_1,...,m_n$ (for some $n$), such that any $t$ (a parameter $<=n$) shares can be reconstructed to recover the secret $m$, any $t-1$ shares doesn't leak information about $m$ and even if the shares that are used for reconstruction are tampered, it is guaranteed that the reconstruction of these tampered shares will either result in the original $m$ or something independent of $m$. Since their introduction, non-malleable secret sharing schemes sparked a very impressive line of research.

In this work, we introduce a feature of local reconstructability in NMSS, which allows reconstruction of any portion of a secret by reading just a few locations of the shares. This is a useful feature, especially when the secret is long or when the shares are stored in a distributed manner on a communication network. In this work, we give a compiler that takes in any non-malleable secret sharing scheme and compiles it into a locally reconstructable non-malleable secret sharing scheme. To secret share a message consisting of $k$ blocks of length $l$ each, our scheme would only require reading $l + log k$ bits (in addition to a few more bits, whose quantity is independent of $l$ and $k$) from each party's share (of a reconstruction set) to locally reconstruct a single block of the message.

We show an application of our locally reconstructable non-malleable secret sharing scheme to a computational non-malleable secure message transmission scheme in the pre-processing model, with an improved communication complexity, when transmitting multiple messages.

Automatic modelling to search distinguishers with high probability covering as many rounds as possible, such as MILP, SAT/SMT, CP models, has become a very popular cryptanalysis topic today. In those models, the optimizing objective is usually the probability or the number of rounds of the distinguishers. If we want to recover the secret key for a round-reduced block cipher, there are usually two phases, i.e., finding an efficient distinguisher and performing key-recovery attack by extending several rounds before and after the distinguisher. The totally attacked number of rounds is not only related to the chosen distinguisher, but also to the extended rounds before and after the distinguisher. In this paper, we try to combine the two phases in a uniform automatic model.

Concretely, we apply this idea to automate the related-key rectangle attacks on SKINNY and ForkSkinny. We propose some new distinguishers with advantage to perform key-recovery attacks. Our key-recovery attacks on a few versions of round-reduced SKINNY and ForkSkinny cover 1 to 2 more rounds than the best previous attacks.

The multivariate scheme HFEv- used to be considered a promising candidate for a post-quantum signature system. First suggested in the early 2000s, a version of the scheme made it to the third round of the ongoing NIST post-quantum standardization process. In late 2020, the system suffered from an efficient rank attack due to Tao, Petzoldt, and Ding. In this paper, we inspect how this recent rank attack is affected by the projection modification. This modification was introduced to secure the signature scheme PFLASH against its predecessor's attacks. We prove upper bounds for the rank of projected HFEv- (pHFEv-) and PFLASH under the new attack, which are tight for the experiments we have performed. We conclude that projection could be a useful tool in protecting against this recent cryptanalysis.

We propose a novel primitive called NIVA that allows the distributed aggregation of multiple users' secret inputs by multiple untrusted servers. The returned aggregation result can be publicly verified in a non-interactive way, i.e. the users are not required to participate in the aggregation except for providing their secret inputs. NIVA allows the secure computation of the sum of a large amount of users' data and can be employed, for example, in the federated learning setting in order to aggregate the model updates for a deep neural network.

We implement NIVA and evaluate its communication and execution performance and compare it with the current state-of-the-art, i.e. Segal et al. protocol (CCS 2017) and Xu et al. VerifyNet protocol (IEEE TIFS 2020), resulting in better user's communicated data and

We define smooth zero-knowledge hash functions (SZKHFs) as smooth projective hash functions (SPHFs) for which the completeness holds even when the language parameter lpar and the projection key HP were maliciously generated. We prove that blackbox SZKHF in the plain model is impossible even if lpar was honestly generated. We then define SZKHF in the registered public key (RPK) model, where both lpar and HP are possibly maliciously generated but accepted by an RPK server, and show that the CRS-model trapdoor SPHFs of Benhamouda et al. are also secure in the weaker RPK model. Then, we define and instantiate subversion-zero knowledge SZKHF in the plain model. In this case, both lpar and HP are completely untrusted, but one uses non-blackbox techniques in the security proof.

In this work, we present a novel approach, called Detector+ , to detect, isolate, and prevent timing-based side channel attacks (i.e., timing attacks) at runtime. The proposed approach is based on a simple observation that the time measurements required by the timing attacks differ from those required by the benign applications as these attacks need to measure the execution times of typically quite short-running operations. Detector+ , therefore, monitors the time readings made by processes and mark consecutive pairs of readings that are close to each other in time as suspicious. In the presence of suspicious time measurements, Detector+ introduces noise into the measurements to prevent the attacker from extracting information by using these measurements. The sequence of suspicious time measurements are then analyzed by using a sliding window based approach to pinpoint the malicious processes at runtime. We have empirically evaluated the proposed approach by using five well known timing attacks, including Meltdown, together with their variations, representing some of the mechanisms that an attacker can employ to become stealthier. In one evaluation setup, each type of attack was carried out concurrently by multiple processes. In the other setup, multiple types of attacks were carried out concurrently. In all the experiments, Detector+ detected all the malicious time measurements with almost a perfect accuracy, prevented all the attacks, and correctly pinpointed all the malicious processes involved in the attacks without any false positives after they have made a few time measurements with an average runtime overhead of 1.56%.