International Association
for Cryptologic Research

We present “FairPoS”, the first blockchain protocol that achieves input fairness with adaptive security. Here, we introduce a novel notion of “input fairness”: the adversary cannot learn the plain-text of any finalized client input before it is include in a block in the chain’s common-prefix. Should input fairness hold, input ordering attacks which depend on the knowledge of plain-text of client inputs are thwarted. In FairPoS, input fairness with adaptive security is achieved by means of the delay encryption scheme of DeFeo et al., a recent cryptographic primitive related to time-lock puzzles, allowing all client inputs in a given round to be encrypted under the same key, which can only be extracted after enough time has elapsed. In contrast, alternative proposals that prevent input order attacks by encrypting user inputs are not adaptively secure as they rely on small static committees to perform distributed key generation and threshold decryption for efficiency’s sake. Such small committees are easily corrupted by an adaptive adversary with a corruption budget applicable over a large set of participants in a permissionless blockchain system. The key extraction task in delay encryption can, in principle, be performed by any party and is secure upon adaptive corruption, as no secret key material is learned. However, the key extraction requires highly specialized hardware in practice. Thus, FairPoS requires resource-rich, staking parties to insert extracted keys to blocks which enables light-clients to decrypt past inputs. Note that naive application of key extraction can result in chain stalls lasting the entire key extraction period. In FairPoS, this is addressed by a novel longest-extendable-chain rule. We formally prove that FairPoS achieves input fairness and the original security of Ouroborous Praos against an adaptive adversary.

In CRYPTO 2012, Zhandry developed generic semi-constant oracle technique and proved security of an identity-based encryption scheme, GPV-IBE, and full domain hash (FDH) signature scheme in the quantum random oracle model (QROM). However, the reduction provided by Zhandry incurred a quadratic reduction loss. In this work, we provide a much tighter proof, with linear reduntion loss, for the FDH, probabilistc FDH (PFDH), and GPV-IBE in the QROM. Our proof is based on the measure-and-reprogram technique developed by Don, Fehr, Majenz and Schaffner.

While online interactions and exchanges have grown exponentially over the past decade, most commercial infrastructures still operate through centralized protocols, and their success essentially depends on trust between different economic actors. Digital advances such as blockchain technology has led to a massive wave of Decentralized Ledger Technology (DLT) initiatives, protocols and solutions. This advance makes it possible to implement trustless systems in the real world, which, combined with appropriate economic and participatory incentives, would foster the proper functioning and drive the adoption of a decentralized platform among different actors. This paper describes an alternative to current commercial structures and networks by introducing Lyzis Labs, which is is an incentive-driven and democratic protocol designed to support a decentralized online marketplace, based on blockchain technology. The proposal, Lyzis Marketplace, allows to connect two or more people in a decentralized and secure way without having to rely on a Trusted Third Party (TTP) in order to perform physical asset exchanges while mainly providing transparent and fully protected data storage. This approach can potentially lead to the creation of a permissionless, efficient, secure and transparent business environment where each user can gain purchasing and decision-making power by supporting the collective welfare while following their personal interests during their various interactions on the network.

We revisit the problem of finding two consecutive $B$-smooth integers by giving an optimised implementation of the Conrey-Holmstrom-McLaughlin ``smooth neighbors'' algorithm. While this algorithm is not guaranteed to return the complete set of $B$-smooth neighbors, in practice it returns a very close approximation to the complete set, but does so in a tiny fraction of the time of its exhaustive counterparts. We exploit this algorithm to find record-sized solutions to the pure twin smooth problem. Though these solutions are still not large enough to be cryptographic parameters themselves, we feed them as input into known methods of searching for twins to yield cryptographic parameters that are much smoother than those given in prior works. Our methods seem especially well-suited to finding parameters for the SQISign signature scheme, particularly those that are geared towards high-security levels.

Asiacrypt 2022 will take place on December 5-9, Regent Hotel, Taipei, Taiwan.

More information and registration instructions can be found at https://asiacrypt.iacr.org/2022/

Some rooms at the venue + nearby hotels reserved for attendees at cut prices.
Stipends may still be available.

The Department of Computer Science and Technology is seeking to recruit a new faculty member at the Assistant or Associate Professor level who can contribute to research and teaching in the area of Privacy and/or Security. We aim to substantially broaden coverage of security-related research and teaching in the Department and we welcome applications relating to a wide range of security and privacy topics, including cryptography, cryptographic protocols and verification, distributed-systems security, malware analysis, forensics, machine learning, privacy, software security, computer hardware security, human factors, ledger technologies, security economics.

Closing date for applications:

Contact: Interested applicants are encouraged to make informal enquiries about the post to Dr Alice Hutchings and Professor Robert Watson, Alice.Hutchings@cst.cam.ac.uk Robert.Watson@cst.cam.ac.uk

More information: https://www.jobs.cam.ac.uk/job/37371/

Multiple Post-Docs in Post-Quantum Cryptography Academia Sinica, at the very edge of Taipei, is the national research institute of Taiwan. Here we have an active group of cryptography researchers, including Dr. Bo-Yin Yang, Dr. Kai-Min Chung, Dr. Tung Chou, and Dr. Ruben Niederhagen, 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 2023, 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 (~2200 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.tw)

Kai-Min Chung (kmchung at iis.sinica.edu.tw)

The Department of Information Security and Communication Technology has a vacant tenure-track position as associate professor in cryptology within our Cryptology Discipline.

After six years of standardisation efforts to solicit, evaluate, and standardise one or more quantum-resistant public-key cryptographic algorithms, in the summer of 2022, the National Institute of Standards and Technology (NIST) from the USA has selected a portfolio of several algorithms. Those algorithms will be the new standards for Public-key Encryption and Key-establishment and for Digital Signatures.

We are now entering a phase where those post-quantum cryptographic standards must be efficiently implemented and deployed. The deployment phase faces challenges such as high-performance implementations, protocol updates with the post-quantum primitives, and levels of robustness and trustworthiness.

Duties of the position:

Teaching cryptology, information security and related subjects at undergraduate and graduate level

Developing and maintaining internationally recognized research activity within the area Deployment of Post-Quantum Cryptography

Take part in interdisciplinary research collaborations, both within NTNU and with other national and international partners

Securing research funding from national and international funding agencies

Contribute with developing an innovative course portfolio at the undergraduate and graduate level in cryptology

Educate and supervise students at BSc and MSc level, and supervising PhD and postdoctoral fellowships

Disseminate relevant research to a wider audience (public outreach)

Participate in the management of research, education and other relevant academic activities in agreement with the department

See https://www.jobbnorge.no/en/available-jobs/job/233227/associate-professor-in-post-quantum-cryptography for more details and how to apply.

Closing date for applications:

Contact: Professor Danilo Gligoroski (danilo.gligoroski@ntnu.no)

More information: https://www.jobbnorge.no/en/available-jobs/job/233227/associate-professor-in-post-quantum-cryptography

Fully Homomorphic encryption allows to evaluate any circuits over encrypted data while preserving the privacy of the data.

Another desirable property of FHE called circuit privacy enables to preserve the privacy of the evaluation circuit, i.e. all the information on the bootstrapped ciphertext, including the computation that was performed to obtain it, is destroyed.

In this paper, we show how to directly build a circuit private FHE scheme from TFHE bootstrapping (Asiacrypt 2016). Our proof frame is inspired from the techniques used in Bourse etal (Crypto 2016), we provide a statistical analysis of the error growth during the bootstrapping procedure where we adapt discrete Gaussian lemmata over rings. We make use of a randomized decomposition for the homomorphic external product and introduce a public key encryption scheme with invariance properties on the ciphertexts distribution. As a proof of concept, we provide a C implementation of our sanitization strategy.

We construct the first actively-secure threshold version of the cryptosystem based on class groups from the so-called CL framework (Castagnos and Laguillaumie, 2015). We then show how to use our threshold scheme to achieve general secure multiparty computation (MPC) with only transparent set-up, i.e., with no secret trapdoors involved.

To achieve this, we also design a new zero-knowledge protocol for proving multiplicative relations between encrypted values. As a result, the zero-knowledge proofs needed to get active security add only a constant factor overhead. Finally, we explain how to adapt our protocol for the so called "You-Only-Speak-Once" (YOSO) setting, which is a very promising recent approach for performing MPC over a blockchain.

Predicate encryption (PE) is a type of public-key encryption that captures many useful primitives such as attribute-based encryption (ABE). Although much progress has been made to generically achieve security against chosen-plaintext attacks (CPA) efficiently, in practice, we also require security against chosen-ciphertext attacks (CCA). Because achieving CCA-security on a case-by-case basis is a complicated task, several generic conversion methods have been proposed. However, these conversion methods may incur a significant efficiency trade-off. Notably, for ciphertext-policy ABE, all generic conversion methods provide a significant overhead in the key generation, encryption or decryption algorithm. Additionally, many generic conversion techniques use one-time signatures to achieve authenticity, which are also known to significantly impact the efficiency.

In this work, we present a new approach to achieving CCA-security as generically and efficiently as possible, by splitting the CCA-conversion in two steps. The predicate of the scheme is first extended in a certain way, which is then used to achieve CCA-security generically e.g., by combining it with a hash function. To facilitate the first step efficiently, we also propose a novel predicate-extension transformation for a large class of pairing-based PE---covered by the pair and the predicate encodings frameworks---which incurs only a small constant overhead for all algorithms. In particular, this yields the most efficient generic CCA-conversion for ciphertext-policy ABE.

The proliferation of Decentralised Finance (DeFi) and Decentralised Autonomous Organisations (DAO), which in current form are exposed to front-running of token transactions and proposal voting, demonstrate the need to shield user inputs and internal state from the parties executing smart contracts. In this work we present “Eagle”, an efficient UC-secure protocol which efficiently realises a notion of privacy preserving smart contracts where both the amounts of tokens and the auxiliary data given as input to a contract are kept private from all parties but the one providing the input. Prior proposals realizing privacy preserving smart contracts on public, permissionless blockchains generally offer a limited contract functionality or require a trusted third party to manage private inputs and state. We achieve our results through a combination of secure multi-party computation (MPC) and zero-knowledge proofs on Pedersen commitments. Although other approaches leverage MPC in this setting, these incur impractical computational overheads by requiring the computation of cryptographic primitives within MPC. Our solution achieves security without the need of any cryptographic primitives to be computed inside the MPC instance and only require a constant amount of exponentiations per client input.

The design of FLIP stream cipher presented at Eurocrypt $2016$ motivates the study of Boolean functions with good cryptographic criteria when restricted to subsets of $\mathbb F_2^n$. Since the security of FLIP relies on properties of functions restricted to subsets of constant Hamming weight, called slices, several studies investigate functions with good properties on the slices, i.e. weightwise properties. A major challenge is to build functions balanced on each slice, from which we get the notion of Weightwise Almost Perfectly Balanced (WAPB) functions. Although various constructions of WAPB functions have been exhibited since $2017$, building WAPB functions with high weightwise nonlinearities remains a difficult task. Lower bounds on the weightwise nonlinearities of WAPB functions are known for very few families, and exact values were computed only for functions in at most $16$ variables.

In this article, we introduce and study two new secondary constructions of WAPB functions. This new strategy allows us to bound the weightwise nonlinearities from those of the parent functions, enabling us to produce WAPB functions with high weightwise nonlinearities. As a practical application, we build several novel WAPB functions in up to $16$ variables by taking parent functions from two different known families. Moreover, combining these outputs, we also produce the $16$-variable WAPB function with the highest weightwise nonlinearities known so far.

We provide an expressive framework that allows analyzing and generating provably secure, state-of-the-art Byzantine fault-tolerant (BFT) protocols. Our framework is hierarchical, including three layers. The top layer is used to model the message pattern and abstract key functions on which BFT algorithms can be built. The intermediate layer provides the core functions with high-level properties sufficient to prove the security of the top-layer algorithms. The bottom layer carefully defines predicates according to which we offer operational realizations for the core functions. All three layers in our framework are extensible and enable innovation. One may modify or extend any layer to theoretically cover all BFT protocols, known and unknown. Indeed, unlike prior BFT frameworks, our framework can analyze and recast BFT protocols in an exceedingly fine-grained manner. More importantly, our framework can readily generate new BFT protocols by simply enumerating the parameters in the framework. In this paper, we show that the framework allows us to fully specify and formally prove the security for 23 BFT protocols, including protocols matching HotStuff, Fast-HotStuff, Jolteon, and Marlin, and among these protocols, seven new protocols outperforming existing ones or achieving meaningful trade-offs among various performance metrics.

A ring signature scheme allows a group member to generate a signature on behalf of the whole group, while the verifier can not tell who computed this signature. However, most predecessors do not guarantee security from the secret key leakage of signers. In 2002, Anderson proposed the forward security mechanism to reduce the effect of such leakage. In this paper, we construct the first lattice-based ring signature scheme with forward security. Our scheme combines the binary tree and lattice basis delegation technique to realize a key evolution mechanism, where secret keys are ephemeral and updated with generating nodes in the binary tree. Thus, the adversary cannot forge the past signature even if the users' present secret keys are revealed. Moreover, our scheme can offer unforgeability under standard models. Furthermore, our proposed scheme is expected to realize post-quantum security due to the underlying Short Integer Solution (SIS) problem in lattice-based cryptography.

GGM tree is widely used in the design of correlated oblivious transfer (COT), subfield vector oblivious linear evaluation (sVOLE), distributed point function (DPF), and distributed comparison function (DCF). Often, the cost associated with GGM tree dominates the computation and communication of these protocols. In this paper, we propose a suite of optimizations that can reduce this cost by half.

• Halving the cost of COT and sVOLE. Our COT protocol introduces extra correlation to each level of a GGM tree used by the state-of-the-art COT protocol. As a result, it reduces both the number of AES calls and the communication by half. Extending this idea to sVOLE, we are able to achieve similar improvement with either halved computation or halved communication.

• Halving the cost of DPF and DCF. We propose improved two-party protocols for the distributed generation of DPF/DCF keys. Our tree structures behind these protocols lead to more efficient full-domain evaluation and halve the communication and the round complexity of the state-of-the-art DPF/DCF protocols.

All protocols are provably secure in the random-permutation model and can be accelerated based on fixed-key AES-NI. We also improve the state-of-the-art schemes of puncturable pseudorandom function (PPRF), DPF, and DCF, which are of independent interest in dealer-available scenarios.

Over the last decade, indistinguishability obfuscation (iO) has emerged as a seemingly omnipotent primitive in cryptography. Moreover, recent breakthrough work has demonstrated that iO can be realized from well-founded assumptions. A thorn to all this remarkable progress is a limitation of all known constructions of general-purpose iO: the security reduction incurs a loss that is exponential in the input length of the function. This ``input-length barrier'' to iO stems from the non-falsifiability of the iO definition and is discussed in folklore as being possibly inherent. It has many negative consequences; notably, constructing iO for programs with inputs of unbounded length remains elusive due to this barrier.

We present a new framework aimed towards overcoming the input-length barrier. Our approach relies on short mathematical proofs of functional equivalence of circuits (and Turing machines) to avoid the brute-force ``input-by-input'' check employed in prior works. - We show how to obfuscate circuits that have efficient proofs of equivalence in Propositional Logic with a security loss independent of input length. - Next, we show how to obfuscate Turing machines with unbounded length inputs, whose functional equivalence can be proven in Cook's Theory $PV$. - Finally, we demonstrate applications of our results to succinct non-interactive arguments and witness encryption, and provide guidance on using our techniques for building new applications.

To realize our approach, we depart from prior work and develop a new gate-by-gate obfuscation template that preserves the topology of the input circuit.

Copy-protection is the task of encoding a program into a quantum state to prevent illegal duplications. A line of recent works studied copy-protection schemes under ``1 -> 2 attacks'': the adversary receiving one program copy can not produce two valid copies. However, under most circumstances, vendors need to sell more than one copy of a program and still ensure that no duplicates can be generated. In this work, we initiate the study of collusion resistant copy-protection in the plain model. Our results are twofold:

(*) The feasibility of copy-protecting all watermarkable functionalities is an open question raised by Aaronson et al. (CRYPTO' 21). In the literature, watermarking decryption, digital signature schemes and PRFs have been extensively studied. For the first time, we show that digital signature schemes can be copy-protected. Together with the previous work on copy-protection of decryption and PRFs by Coladangelo et al. (CRYPTO' 21), it suggests that many watermarkable functionalities can be copy-protected, partially answering the above open question by Aaronson et al. (*) We make all the above schemes (copy-protection of decryption, digital signatures, and PRFs) k bounded collusion resistant for any polynomial k, giving the first bounded collusion resistant copy-protection for various functionalities in the plain model.

Currently there exist many blockchains with weak trust guarantees, limiting applications and participation. Existing solutions to boost the trust using a stronger blockchain, e.g., via checkpointing, requires the weaker blockchain to give up sovereignty. In this paper we propose a family of protocols in which multiple blockchains interact to create a combined ledger with boosted trust. We show that even if several of the interacting blockchains cease to provide security guarantees, the combined ledger continues to be secure – our TrustBoost protocols achieve the optimal threshold of tolerating the insecure blockchains. Furthermore, the protocol simply operates via smart contracts and require no change to the underlying consensus protocols of the participating blockchains, a form of “consensus on top of consensus”. The protocols are lightweight and can be used on specific (e.g., high value) transactions; we demonstrate the practicality by implementing and deploying TrustBoost as cross-chain smart contracts in the Cosmos ecosystem using approximately 3,000 lines of Rust code, made available as open source. Our evaluation shows that using 10 Cosmos chains in a local testnet, TrustBoost has a gas cost of roughly $2 with a latency of 2 minutes per request, which is in line with the cost on a high security chain such as Bitcoin or Ethereum.

As the prevalence of quantum computing is growing in leaps and bounds over the past few years, there is an ever-growing need to analyze the symmetric-key ciphers against the upcoming threat. Indeed, we have seen a number of research works dedicated to this. Our work delves into this aspect of block ciphers, with respect to the SPECK family and LowMC family.

The SPECK family received two quantum analysis till date (Jang et al., Applied Sciences, 2020; Anand et al., Indocrypt, 2020). We revisit these two works, and present improved benchmarks SPECK (all 10 variants). Our implementations incur lower full depth compared to the previous works.

On the other hand, the quantum circuit of LowMC was explored earlier in Jaques et al.'s Eurocrypt 2020 paper. However, there is an already known bug in their paper, which we patch. On top of that, we present two versions of LowMC (on L1, L3 and L5 variants) in quantum, both of which incur significantly less full depth than the bug-fixed implementation.