International Association
for Cryptologic Research

Inverse sqrt and sqrt function have numerous applications in linear algebra and machine learning such as vector normalisation, eigenvalue computation, dimensionality reduction, clustering, etc. This paper presents a method to approximate and securely perform the inverse sqrt function using CKKS homomorphic encryption scheme. Since the CKKS homomorphic scheme allows only computation of polynomial functions, we propose a method to approximate the inverse sqrt function polynomially. In the end, we provide an implementation of our method for the inverse sqrt function.

Cryptographic voting protocols have recently seen much interest from practitioners due to their (planned) use in countries such as Estonia, Switzerland and Australia. Many organizations also use Helios for elections. While many efficient protocols exist from discrete log-type assumptions, the situation is less clear for post-quantum alternatives such as lattices. This is because previous voting protocols do not carry over easily due to issues such as noise growth and approximate relations. In particular, this is a problem for tested designs such as verifiable mixing and decryption of ballot ciphertexts.

In this work, we make progress in this direction. We propose a new verifiable secret shuffle for BGV ciphertexts as well as a compatible verifiable distributed decryption protocol. The shuffle is based on an extension of a shuffle of commitments to known values which is combined with an amortized proof of correct re-randomization. The verifiable distributed decryption protocol uses noise drowning for BGV decryption, proving correctness of decryption steps in zero-knowledge.

We give concrete parameters for our system, estimate the size of each component and provide an implementation of all sub-protocols. Together, the shuffle and the decryption protocol are suitable for use in real-world cryptographic voting schemes, which we demonstrate with a prototype voting protocol design.

The evolution of Smart Contracts in recent years inspired a crucial question: Do Smart Contract evaluation protocols provide the required level of Privacy when executing contracts on the Blockchain? The Hawk (IEEE S\&P '16) paper introduces a way to solve the problem of Privacy in Smart Contracts by evaluating the contracts \textit{off-chain}, albeit with the trust assumption of a \textit{manager}. To avoid the partially trusted manager altogether, a novel approach named zkHawk (IEEE BRAINS '21) explains how we can evaluate the contracts privately off-chain using a Multi-Party Computation (MPC) protocol instead of trusting said manager. This paper dives deeper into the detailed construction of a variant of the zkHawk protocol titled \textit{V-zkHawk} using formal proofs to construct the said protocol and model its security in the Universal Composability (UC) framework (FOCS '01). The V-zkHawk protocol discussed here does not support immediate closure, i.e, all the parties ($n$) have to send a message to inform the blockchain that the contract has been executed with corruption allowed for up to $t$ parties, where $t

We introduce and study elastic SNARKs, a class of succinct arguments where the prover has multiple configurations with different time and memory tradeoffs, which can be selected depending on the execution environment and the proved statement. The output proof is independent of the chosen configuration.

We construct an elastic SNARK for rank-1 constraint satisfiability (R1CS). In a time-efficient configuration, the prover uses a linear number of cryptographic operations and a linear amount of memory. In a space-efficient configuration, the prover uses a quasilinear number of cryptographic operations and a logarithmic amount of memory. A key component of our construction is an elastic probabilistic proof. Along the way, we also formulate a streaming framework for R1CS that we deem of independent interest.

We additionally contribute Gemini, a Rust implementation of our protocol. Our benchmarks show that Gemini, on a single machine, supports R1CS instances with tens of billions of constraints.

We construct polynomial commitment schemes with constant sized evaluation proofs and logarithmic verification time in the transparent setting. To the best of our knowledge, this is the first result achieving this combination of properties.

Our starting point is a transparent inner product commitment scheme with constant-sized proofs and linear verification. We build on this to construct a polynomial commitment scheme with constant size evaluation proofs and logarithmic (in the degree of the polynomial) verification time. Our constructions makes use of groups of unknown order instantiated by class groups. We prove security of our construction in the Generic Group Model (GGM). Using our polynomial commitment scheme to compile an information-theoretic proof system yields Dew - a transparent and constant-sized zkSNARK (Zero-knowledge Succinct Non-interactive ARguments of Knowledge) with logarithmic verification.

Finally, we show how to recover the result of DARK (Bünz et al., Eurocrypt 2020). DARK presented a succinct transparent polynomial commitment scheme with logarithmic proof size and verification. However, it was recently discovered to have a gap in its security proof (Block et al, CRYPTO 2021). We recover its extractability based on our polynomial commitment construction, thus obtaining a transparent polynomial commitment scheme with logarithmic proof size and verification under same assumptions as DARK.

With the enormous increase in portable cryptographic devices, physical attacks are becoming similarly popular. One of the most common physical attacks is Side-Channel Analysis (SCA), extremely dangerous due to its non-invasive nature. Threshold Implementations (TI) was proposed as the first countermeasure to provide provable security in masked hardware implementations. While most works on hardware masking are focused on optimizing the area requirements, with the newer and smaller technologies area is taking a backseat, and low-latency is gaining importance. In this work, we revisit the scheme proposed by Arribas et al. in TCHES 2018 to secure unrolled implementations. We formalize and expand this methodology, to devise a masking scheme, derived from TI, designed to secure hardware implementations optimized for latency named Low-Latency Threshold Implementations (LLTI). By applying the distributive property and leveraging a divide-and-conquer strategy, we split a non-linear operation in layers which are masked separately. The result is a more efficient scheme than the former TI for any operation of algebraic degree greater than two, achieving great optimizations both in terms of speed and area. We compare the performance of first-order LLTI with first-order TI in securing a cubic gate and a degree-7 AND gate without using any registers in between. We achieve a 137% increase in maximum frequency and a 60% reduction in area for the cubic gate, and 3131 times reduction in area in the case of a degree-7 AND gate compared to TI. To further illustrate the power of our scheme we take a low-latency PRINCE implementation from the literature and, by simply changing the secure S-box with the LLTI version, we achieve a 46% max. frequency improvement and a 38% area reduction. Moreover, we apply LLTI to a secure a low-latency AES implementation and compare it with the TI version, achieving a 6.9 times max. freq. increase and a 47.2% area reduction.

The last ten years have seen a tremendous growth in the interest and practicality of secure multiparty computation (MPC) and its possible applications. Secure MPC is indeed a very hot research topic and recent advances in the eld have already been translated into commercial products world-wide. A major pillar in this advance has been in the case of active security with a dishonest majority, mainly due to the SPDZ-line of work protocols. This survey gives an overview of these protocols, with a focus of the original SPDZ paper (CRYPTO 2012) and its subsequent optimizations. It also covers some alternative approaches based on oblivious transfer, oblivious linear-function evaluation, and constant-round protocols.

Ring signatures and ID-based cryptography are considered promising in terms of application. A ring signature authenticates messages while the author of the message remains anonymous. ID-based cryptographic primitives suppress the need for certificates in public key infrastructures (PKI). In this work, we propose a generic construction for post-quantum ID-based ring signatures (IDRS) based on symmetric-key primitives from which we derive the first two constructions of IDRS. The first construction named PicRS utilizes the Picnic digital signature to ensure its security while the second construction XRS is motivated by the stateful digital signature XMSS instead of Picnic, allowing a signature size reduction. Both constructions have a competitive signature size when compared with state-of-the-art lattice-based IDRS. XRS can achieve a competitive signature size of 889KB for a ring of 4096 users while the fully stateless PicRS achieves a signature size of 1.900MB for a ring of 4096 users. In contrast, the shortest lattice-based IDRS achieves a signature size of 335MB for the same ring size.

We propose an efficient oblivious transfer in the random oracle model based on public key encryption with pseudorandom public keys. The construction is as efficient as the state of art though it has a significant advantage. It has a tight security reduction to the multi-user security of the underlying public key encryption. In previous constructions, the security reduction has a multiplicative loss that amounts in at least the amount of adversarial random oracle queries. When considering this loss for a secure parameter choice, the underlying public key encryption or elliptic curve would require a significantly higher security level which would decrease the overall efficiency.

Our OT construction can be instantiated from a wide range of assumptions such as DDH, LWE, or codes based assumptions as well as many public key encryption schemes such as the NIST PQC finalists. Since tight multi-user security is a very natural requirement which many public key encryption schemes suffice, many public key encryption schemes can be straightforwardly plugged in our construction without the need of reevaluating or adapting any parameter choices.

Public key cryptography is used to asymmetrically establish keys, authenticate or encrypt data between communicating parties at a relatively high performance cost. To reduce computational overhead, modern network protocols combine asymmetric primitives for key establishment and authentication with symmetric ones. Similarly, Hybrid Public Key Encryption, a relatively new scheme, uses public key cryptography for key derivation and symmetric key cryptography for data encryption. In this paper, we present the first quantum-resistant implementation of HPKE to address concerns that quantum computers bring to asymmetric algorithms. We propose PQ-only and PQ-hybrid HPKE variants and analyze their performance for two post-quantum key encapsulation mechanisms and various plaintext sizes. We compare these variants with RSA and classical HPKE and show that the additional post-quantum overhead is amortized over the plaintext size. Our PQ-hybrid variant with a lattice-based KEM shows an overhead of 52% for 1KB of encrypted data which is reduced to 17% for 1MB of plaintext. We report 1.83, 1.78, and 2.15 x10^6 clock cycles needed for encrypting 1MB of message based on classical, PQ-only, and PQ-hybrid HPKE respectively, where we note that the cost of introducing quantum-resistance to HPKE is relatively low.

Eurocrypt 2022 will take place as a hybrid event online and in Trondheim, Norway on May 30 to June 3, 2022 with affiliated events taking place on Sunday May 29 and Monday May 30.

The registration site is now open: https://eurocrypt.iacr.org/2022/registration.php

Early bird registration closes: April 29

For more information please visit: https://eurocrypt.iacr.org/2022/

Event date: 20 March to 24 March 2023

We have multiple PhD positions in Applied Cryptography, Post Quantum Cryptography and Blockchains. Topics include (but not limited to) Layer-2 scalability and interoperability of blockchains, decentralised storage, verifiable computation, post quantum cryptography for blockchains.

Students who have completed a bachelor’s degree or a master’s degree in Computer Science, Mathematics or a related discipline or in their final year of study are welcome to apply. Prospective students should have a strong mathematical inclination and excellent understanding of data structures, discrete mathematics and algorithms. Candidates with demonstrated knowledge of cryptography will be preferred.

The school accepts applications in multiple rounds, but it is good to contact early to avail some of the scholarships.

The earliest deadline at UNSW is May 13, 2022.

Closing date for applications:

Contact: Sushmita Ruj, sushmita.ruj@unsw.edu.au

Applications are invited for a Post-Doctoral Research Fellow position to conduct research into the application of advanced machine learning techniques for use in hardware Trojan detection, as part of the EPSRC-funded DeepSecurity project within the UK Research Institute in Secure Hardware and Embedded Systems (RISE: ukrise.org), hosted by the Centre for Secure Information Technology (CSIT) at Queen’s.

The successful candidate must have and your CV/Cover letter application should clearly demonstrate you have:
• 2:1 Honours degree in Electrical and Electronic Engineering/Computer Science/Mathematics (or related discipline)
• A PhD, or about to obtain a PhD, in a relevant subject
• At least 3 years relevant research experience in FPGA/ASIC/Embedded systems design
• Evidence of a strong publication record commensurate with career stage and experience.

This is a fixed term contract available until 31 March 2023.

Closing date for applications:

Contact: Professor Máire O'Neill

More information: https://hrwebapp.qub.ac.uk/tlive_webrecruitment/wrd/run/ETREC107GF.open?VACANCY_ID=551890GLbr&WVID=6273090Lgx&LANG=USA

Sharding is a key approach to scaling the performance of on-chain transactions: the network is randomly partitioned into smaller groups of validator nodes, known as \textit{shards}, each growing a disjoint ledger of transactions via state-machine replication (SMR) in parallel to other shards. As SMR protocols typically incur a quadratic message complexity in the network size, shards can process transactions significantly faster than the entire network. On the downside, shards cannot be made arbitrarily small due to the exponentially-increasing probability that malicious nodes take over a sufficient majority in small shards, compromising the security of SMR. In practice, this dictates relatively large shards with hundreds of nodes each, significantly limiting the scalability benefits of sharding.

In this paper, we propose \textit{Instachain}, a novel sharding approach that breaks the scalability limits of sharding by reducing the shard size to significantly-smaller numbers than was previously considered possible. We achieve this by relaxing the liveness property for some of the shards while still preserving the safety property across all shards. To do this, we carefully adjust the quorum size parameter of the intra-shard SMR protocol to achieve maximum parallelism across all shards without compromising security. In addition, Instachain is the first sharding protocol to adopt the stateless blockchain model in shards, which in conjunction with a novel cross-shard verification technique allows the protocol to efficiently prevent double-spending attempts across significantly-more shards than previous work.

We present the first specification-compliant constant-time FPGA implementation of the Classic McEliece cryptosystem from the third-round of NIST's Post-Quantum Cryptography standardization process. In particular, we present the first complete implementation including encapsulation and decapsulation modules as well as key generation with seed expansion. All the hardware modules are parametrizable, at compile time, with security level and performance parameters. As the most time consuming operation of Classic McEliece is the systemization of the public key matrix during key generation, we present and evaluate three new algorithms that can be used for systemization while complying with the specification: hybrid early-abort systemizer (HEA), single-pass early-abort systemizer (SPEA), and dual-pass early-abort systemizer (DPEA). All of the designs outperform the prior systemizer designs for Classic McEliece by 2.2x to 2.6x in average runtime and by 1.7x to 2.4x in time-area efficiency. We show that our complete Classic McEliece design for example can perform key generation in 5.2-20ms, encapsulation in 0.1-0.5ms, and decapsulation in 0.7-1.5ms for all security levels on an Xlilinx Artix 7 FPGA. The performance can be increased even further at the cost of resources by increasing the level of parallelization using the performance parameters of our design.

Modular reduction is a core operation in public-key cryptography. While a standard modular reduction is often required, a partial reduction limiting the growth of the coefficients is enough for several usecases.

Knowing the quotient of the Euclidean division of an integer by the modulus allows to easily recover the remainder. We propose a way to compute efficiently, without divisions, an approximation of this quotient. From this approximation, both full and partial reductions are deduced. The resulting algorithms are modulus specific: the sequence of operations to perform in order to get a reduction depends on the modulus and the size of the input.

We analyse the cost of our algorithms for a usecase coming from post-quantum cryptography. We show that with this modulus, on a CPU with a slow multiplication, our method gives an algorithm faster than prior art algorithms.

The Internet of Things (IoT) has brought new ways for humans and machines to communicate with each other over the internet. Though sensor-driven devices have largely eased our everyday lives, most IoT infrastructures have been suffering from security challenges. Since the emergence of IoT, lightweight block ciphers have been a better option for intelligent and sensor-based applications. When public-key infrastructure dominates worldwide, the symmetric key encipherment such as Advanced Encryption Standard (AES) shows immense prospects to sit with the smart home IoT appliances. As investigated, chaos motivated logistic map shows enormous potential to secure IoT aligned real-time data communication. The unpredictability and randomness features of the logistic map in sync with chaos-based scheduling techniques can pave the way to build a particular dynamic key propagation technique for data confidentiality, availability and integrity. After being motivated by the security prospects of AES and chaos cryptography, the paper illustrates a key scheduling technique using a 3-dimensional S-box (substitution-box). The logistic map algorithm has been incorporated to enhance security. The proposed approach has applicability for lightweight IoT devices such as smart home appliances. The work determines how seeming chaos accelerates the desired key-initiation before message transmission. The proposed model is evaluated based on the key generation delay required for the smart-home sensor devices.

Proof-of-stake algorithms implemented as distributed consensus mechanisms in the base layer of blockchain networks are defective cryptosystems by nature. By trying to improve the energy efficiency of blockchains using proof-of-work in the consensus mechanism, proof-of-stake is introducing a set of significant new flaws in both monetary and governance models. Such systems are plutocratic, oligopolistic, and permissioned.

In this article we perform a general study on the criterion of weightwise nonlinearity for the functions which are weightwise perfectly balanced (WPB). First, we investigate the minimal value this criterion can take over WPB functions, deriving theoretic bounds, and exhibiting the first values. We emphasize the link between this minimum and weightwise affine functions, and we prove that for $n\ge 8$ no $n$-variable WPB function can have this property. Then, we focus on the distribution and the maximum of this criterion over the set of WPB functions. We provide theoretic bounds on the latter and algorithms to either compute or estimate the former, together with the results of our experimental studies for $n$ up to $8$. Finally, we present two new constructions of WPB functions obtained by modifying the support of linear functions for each set of fixed Hamming weight. This provides a large corpus of WPB function with proven weightwise nonlinearity, and we compare the weightwise nonlinearity of these constructions to the average value, and to the parameters of former constructions in $8$ and $16$ variables.