International Association
for Cryptologic Research

We initiate the study of verifiable capacity-bound function (VCBF). The main VCBF property imposes a lower bound on the number of bits read from memory during evaluation (referred to as minimum capacity). No adversary, even with unbounded resources, should produce an output without spending this minimum memory capacity. Moreover, a VCBF allows for an efficient public verification process: Given a proof-of-correctness, checking the validity of the output takes significantly fewer memory resources, sublinear in the target minimum capacity. Finally, it achieves soundness, i.e., no computationally bounded adversary can produce a proof that passes verification for a false output. With these properties, we believe a VCBF can be viewed as a “space” analog of a verifiable delay function. We then propose the first VCBF construction relying on evaluating a degree-$d$ polynomial $f$ from $\mathbb{F}_p[x]$ at a random point. We leverage ideas from Kolmogorov complexity to prove that sampling $f$ from a large set (i.e., for high-enough $d$) ensures that evaluation must entail reading a number of bits proportional to the size of its coefficients. Moreover, our construction benefits from existing verifiable polynomial evaluation schemes to realize our efficient verification requirements. In practice, for a field of order $O(2^\lambda)$ our VCBF achieves $O((d + 1)\lambda)$ minimum capacity, whereas verification requires just $O(\lambda)$.

Adaptor signature is becoming an increasingly important tool in solving the scalability and interoperability issues of blockchain applications. It has many useful properties. Firstly, it can reduce on-chain cost when it is used in off-chain authenticated communication. Secondly, it can increase the fungibility of transactions using it as the signature. Thirdly, it can help circumvent the limitation of the blockchain's scripting language.

In this paper, we propose the first generic construction of adaptor signatures which is compatible with different signature schemes. It can be used as a general framework to combine with different privacy-preserving cryptosystems. Finally, we propose blind adaptor signature and linkable ring adaptor signature. We believe they are of independent interests.

We construct more efficient cryptosystems with provable security against adaptive attacks, based on simple and natural hardness assumptions in the standard model. Concretely, we describe:

- An adaptively-secure variant of the efficient, selectively-secure LWE-based identity-based encryption (IBE) scheme of Agrawal, Boneh, and Boyen (EUROCRYPT 2010). In comparison to the previously most efficient such scheme by Yamada (CRYPTO 2017) we achieve smaller lattice parameters and shorter public keys of size $\mathcal{O}(\log \lambda)$, where $\lambda$ is the security parameter.

- Adaptively-secure variants of two efficient selectively-secure pairing-based IBEs of Boneh and Boyen (EUROCRYPT 2004). One is based on the DBDH assumption, has the same ciphertext size as the corresponding BB04 scheme, and achieves full adaptive security with public parameters of size only $\mathcal{O}(\log \lambda)$. The other is based on a $q$-type assumption and has public key size $\mathcal{O}(\lambda)$, but a ciphertext is only a single group element and the security reduction is quadratically tighter than the corresponding scheme by Jager and Kurek (ASIACRYPT 2018).

- A very efficient adaptively-secure verifiable random function where proofs, public keys, and secret keys have size $\mathcal{O}(\log \lambda)$.

As a technical contribution we introduce blockwise partitioning, which leverages the assumption that a cryptographic hash function is weak near-collision resistant to prove full adaptive security of cryptosystems.

Despite significant recent progress toward making multi-party computation (MPC) practical, no existing MPC library offers complete robustness---meaning guaranteed output delivery, including in the offline phase---in a network that even has intermittent delays. Importantly, several theoretical MPC constructions already ensure robustness in this setting. We observe that the key reason for this gap between theory and practice is the absence of efficient verifiable/complete secret sharing (VSS/CSS) constructions; existing CSS protocols either require a) challenging broadcast channels in practice or b) introducing computation and communication overhead that is at least quadratic in the number of players.

This work presents hbACSS, a suite of optimal-resilience asynchronous complete secret sharing protocols that are (quasi)linear in both computation and communication overhead. Towards developing hbACSS, we develop hbPolyCommit, an efficient polynomial commitment scheme that is (quasi)linear (in the polynomial degree) in terms of computation and communication overhead without requiring a trusted setup. We implement our hbACSS protocols, extensively analyze their practicality, and observe that our protocols scale well with an increasing number of parties. In particular, we use hbACSS to generate MPC input masks: a useful primitive which had previously only been calculated nonrobustly in practice.

In the model of Perfectly Secure Message Transmission (PSMT), a sender Alice is connected to a receiver Bob via $n$ parallel two-way channels, and Alice holds an $\ell$ symbol secret that she wishes to communicate to Bob. There is an unbounded adversary Eve that controls $t$ of the channels, where $n=2t+1$. Eve is able to corrupt any symbol sent through the channels she controls, and furthermore may attempt to infer Alice's secret by observing the symbols sent through the channels she controls. The transmission is required to be (a) reliable, i.e., Bob must always be able to recover Alice's secret, regardless of Eve's corruptions; and (b) private, i.e., Eve may not learn anything about the Alice's secret. We focus on the two-round model, where Bob is permitted to first transmit to Alice, and then Alice responds to Bob.

In this work we provide tight upper and lower bounds for the PSMT model when the length of the communicated secret $\ell$ is asymptotically large. Specifically, we first construct a protocol that allows Alice to communicate an $\ell$ symbol secret to Bob by transmitting at most $2(1+o(1))n\ell$ symbols. We complement this with a lower bound showing that $2n\ell$ symbols are necessary for Alice to privately and reliably communicate her secret. Thus, we completely determine the optimal transmission rate in this regime, even up to the leading constant.

ASCON is one of the elegant designs of authenticated encryption with associated data (AEAD) that was selected as the first choice for lightweight ap- plications in the CAESAR competition, which also has been submitted to NIST lightweight cryptography standardization. ASCON has been in the literature for a while, however, there has been no successful AEAD which is secure at the same time lighter than ASCON. In this article, we have overcome the challenge of constructing a permutation that is lighter than the ASCON permutation while ensuring a similar performance, and based on which we achieve a more lightweight AEAD which we call Sycon. Extensive security analysis of Sycon confirms that it provides the same level of security as that of ASCON. Our hardware implementation result shows that the Sycon permutation has 5.35% reduced area, compared to the ASCON permutation. This leads to a remarkable area reduction for Sycon AEAD which is about 14.95% as compared to ASCON AEAD. We regard the Sycon as a new milestone as it is the lightest among all the AEADs belonging to the ASCON family.

EasyCrypt is a proof assistant used for verifying computational security proofs of cryptographic constructions. It has been applied to several prominent examples, including the SHA3 standard and a critical component of AWS Key Management Services. In this paper we enhance the EasyCrypt proof assistant to reason about computational complexity of adversaries. The key technical tool is a Hoare logic for reasoning about computational complexity (execution time and oracle calls) of adversarial computations. Our Hoare logic is built on top of the module system used by EasyCrypt for modeling adversaries. We prove that our logic is sound w.r.t. the semantics of EasyCrypt programs --- we also provide full semantics for the EasyCrypt module system, which was previously lacking. We showcase (for the first time in EasyCrypt and in other computer-aided cryptographic tools) how our approach can express precise relationships between the probability of adversarial success and their execution time. In particular, we can quantify existentially over adversaries in a complexity class, and express general composition statements in simulation-based frameworks. Moreover, such statements can be composed to derive standard concrete security bounds for cryptographic constructions whose security is proved in a modular way. As a main benefit of our approach, we revisit security proofs of some well-known cryptographic constructions and we present a new formalization of Universal Composability (UC).

FrodoKEM is a lattice-based key encapsulation mechanism, currently a semi-finalist in NIST’s post-quantum standardization effort. A condition for these candidates is to use NIST standards for sources of randomness (i.e., seed-expanding), and as such most candidates utilize SHAKE, an XOF defined in the SHA-3 standard. However, for many of the candidates, this module is a significant implementation bottleneck. Trivium is a lightweight, ISO standard stream cipher which performs well in hardware and has been used in previous hardware designs for lattice-based cryptography. This research proposes optimized designs for FrodoKEM, concentrating on high throughput by parallelising the matrix multiplication operations within the cryptographic scheme. This process is eased by the use of Trivium due to its higher throughput and lower area consumption. The parallelisations proposed also complement the addition of first-order masking to the decapsulation module. Overall, we significantly increase the throughput of FrodoKEM; for encapsulation we see a 16x speed-up, achieving 825 operations per second, and for decapsulation we see a 14x speed-up, achieving 763 operations per second, compared to the previous state-of-the-art, whilst also maintaining a similar FPGA area footprint of less than 2000 slices.

We present Vortex a new family of one way hash functions that can produce message digests of 224, 256, 384 and 512 bits. The main idea behind the design of these hash functions is that we use well known algorithms that can support very fast diffusion in a small number of steps. We also balance the cryptographic strength that comes from iterating block cipher rounds with SBox substitution and diffusion (like Whirlpool) against the need to have a lightweight implementation with as small number of rounds as possible. We use a variable number of Rijndael rounds with a stronger key schedule. Our goal is not to protect a secret symmetric key but to support perfect mixing of the bits of the input into the hash value. Rijndael rounds are followed by our variant of Galois Field multiplication. This achieves cross-mixing between 128-bit or 256-bit sets. Our hash function uses the Enveloped Merkle-Damgard construction to support properties such as collision resistance, first and second pre-image resistance, pseudorandom oracle preservation and pseudorandom function preservation. We provide analytical results that demonstrate that the number of queries required for finding a collision with probability greater or equal to 0.5 in an ideal block cipher approximation of Vortex 256 is at least 1.18x2^122.55 if the attacker uses randomly selected message words. We also provide experimental results that indicate that the compression function of Vortex is not inferior to that of the SHA family regarding its capability to preserve the pseudorandom oracle property. We list a number of well known attacks and discuss how the Vortex design addresses them. The main strength of the Vortex design is that this hash function can demonstrate an expected performance of 2.2-2.5 cycles per byte in future processors with instruction set support for Rijndael rounds and carry-less multiplication. We provide arguments why we believe this is a trend in the industry. We also discuss how optimized assembly code can be written that demonstrates such performance.

Vortex is a new family of one-way hash functions which has been submitted to the NIST SHA-3 competition. Its design is based on using the Rijndael block cipher round as a building block, and using a multiplication-based merging function to support fast mixing in a small number of steps. Vortex is designed to be a fast hash function, when running on a processor that has AES acceleration and has a proven collision resistance [2]. Several attacks on Vortex have been recently published [3, 4, 5, 6] exploiting some structural properties of its design, as presented in the version submitted to the SHA-3 competition. These are mainly ¯rst and second preimage attacks with time complexity below the ideal, as well as attempts to distinguish the Vortex output from random. In this paper we study the root-cause of the attacks and propose few amendments to the Vortex structure, which eliminate the attacks without a®ecting its collision resistance and performance.

Event date: 5 December to 8 December 2021
Submission deadline: 27 April 2021
Notification: 15 June 2021

Overview

Huawei’s Munich Research Center (MRC) in Munich is responsible for advanced technical research, architecture evolution design and strategic technical planning. For the Trustworthy Technology and Engineering Lab in Munich, we are looking for a (Senior) Security Research Engineer.

Responsibilities

• Research and analyze state of the art system security technologies for trusted computing and platform cyber resilience
• Design and implement technology prototypes for validating and demonstrating their feasibility, as well as support their integration into the products
• Write design documentation and publish the research results
• Participate in the industry analysis, strategic planning of new features and standardization

Requirements

• PhD in computer science or system security, with publications at top security conferences
• Solid understanding of computer architecture, from hardware to operating system
• Proven experience in designing and implementing system security technologies such as hardware-assisted security, trusted computing, TEEs, enclaves, runtime integrity
• Experience in programming with security protocols and crypto libraries
• Hands-on software development skills in some or all of
  • Linux kernel and KVM hypervisor (e.g. security subsystem, memory management etc.)
  • Microkernels and microvisors
  • Embedded firmware development
• Active contributions to open-source projects are a big plus
• Excellent communication skills, teamwork spirit, initiative and autonomous working are required
• Proficiency in English and interest to work in a truly diverse cultural environment

Benefits

• Chance to work together with domain experts on cutting edge technologies
• Unique environment for bringing research concepts into actual products
• Position to influence and drive technology adoption across the entire company

If you want to have a high level of impact on future Huawei products and to design novel solutions together with a multicultural team of researchers and engineers in Huawei’s Munich Research Center in M

Closing date for applications:

Contact: Silviu Vlasceanu (first.last @ huawei.com)

More information: https://apply.workable.com/huawei-16/j/ED1F5C1EB1/

The Selmer Center in Secure Communication is looking for a PhD student to join us in our new research project Cryptographic Boolean Functions for Threshold Implementations, funded by the Norwegian Research Council. This study will be supervised by Prof. Budaghyan, Prof. Carlet and Prof. Rijmen.

Applicants interested in helping us over the next 3 years to study Boolean functions used as building blocks in cryptographic primitives and their Threshold Implementations in order to find efficient ways of preventing Side Channel Attacks, must have:

• obtained a master's degree in Mathematics or Computer Science by 01.11.2021 (the position's starting date),
• strong background in Discrete Mathematics or symmetric cryptography, and
• good programming skills

For further information and the online application form please follow the link in the title above.

Closing date for applications:

Contact: Prof. Lilya Budaghyan

More information: https://www.jobbnorge.no/en/available-jobs/job/200521/phd-position-in-informatics-cryptography

Event date: 30 May to 3 June 2022

Event date: 19 May to 7 July 2021
Submission deadline: 15 March 2021
Notification: 15 April 2021

Lattice-based cryptography relies on generating random bases which are difficult to fully reduce. Given a lattice basis (such as the private basis for a cryptosystem), all other bases are related by multiplication by matrices in $GL(n,\mathbb{Z})$. How can one sample random elements from $GL(n,\mathbb{Z})$? We consider various methods, finding some are stronger than others with respect to the problem of recognizing rotations of the $\mathbb{Z}^n$ lattice. In particular, the standard algorithm of multiplying unipotent generators together (as implemented in Magma's RandomSLnZ command) generates instances of this last problem which can be efficiently broken, even in dimensions nearing 1,500. Similar weaknesses for this problem are found with the random basis generation method in one of the NIST Post-Quantum Cryptography competition submissions (DRS). Other algorithms are described which appear to be much stronger.

It is well known that the general supersingular isogeny problem reduces to the supersingular endomorphism ring computation problem. However, in order to attack SIDH-type schemes one requires a particular isogeny which is usually not returned by the general reduction. At Asiacrypt 2016, Galbraith et al. presented a polynomial-time reduction of the problem of finding the secret isogeny in SIDH to the problem of computing the endomorphism ring of a supersingular elliptic curve. Their method exploits that secret isogenies in SIDH are short, and thus it does not extend to other SIDH-type schemes where this condition is not fulfilled. We present a more general reduction algorithm that generalises to all SIDH-type schemes. The main idea of our algorithm is to exploit available torsion point images together with the KLPT algorithm to obtain a linear system of equations over a certain residue class ring. Lifting the solution of this linear system yields the secret isogeny. As a consequence, we show that the choice of the prime $p$ in B-SIDH is tight.

In this paper, we study the hybrid dual attack over Learning with Errors (LWE) problems for any secret distribution. Prior to our work, hybrid attacks are only considered for sparse and/or small secrets. A new and interesting result from our analysis shows that a hybrid dual attack can outperform a standalone dual attack, regardless of the secret distribution. We formulate our results into a framework of predicting the performance of the hybrid dual attacks. We also present a few tricks that further improve our attack. To illustrate the effectiveness of our result, we re-evaluate the security of all LWE related proposals in round 3 of NIST’s post-quantum cryptography process, and improve the state-of- the-art cryptanalysis results by 1-9 bits, under the BKZ-core-SVP model.

Identifiable abort (IA) is the strongest security guarantee that is achievable for secure multi-party computation in the dishonest majority setting. Protocols that achieve IA ensure that, in case of an abort, all honest parties agree on the identity of at least one corrupt party who can be held accountable for the abort. It is important to understand what computational primitives must be used to obtain secure computation with identifiable abort. This can be approached by asking which oracles can be used to build perfectly secure computation with identifiable abort. Ishai, Ostrovsky, and Zikas (Crypto 2014) show that an oracle that returns correlated randomness to all $n$ parties is sufficient; however, they leave open the question of whether oracles that return output to fewer than $n$ parties can be used.

In this work, we show that for $t \leq n - 2$ corruptions, oracles that return output to $n - 1$ parties are sufficient to obtain perfectly secure computation with identifiable abort. Using our construction recursively, we see that for $t \leq n - \ell - 2$ and $\ell \in \mathcal{O}(1)$, oracles that return output to $n - \ell - 1$ parties are sufficient.

For our construction, we introduce a new kind of secret sharing scheme which we call unanimously identifiable secret sharing with public and private shares (UISSwPPS). In a UISSwPPS scheme, each share holder is given a public and a private shares. Only the public shares are necessary for reconstruction, and the knowledge of a private share additionally enables the identification of at least one party who provided an incorrect share in case reconstruction fails. The important new property of UISSwPPS is that, even given all the public shares, an adversary should not be able to come up with a different public share that causes reconstruction of an incorrect message, or that avoids the identification of a cheater if reconstruction fails.

Adaptor signatures are a novel cryptographic primitive with important applications for cryptocurrencies. They have been used to construct second layer solutions such as payment channels or cross-currency swaps. The basic idea of an adaptor signature scheme is to tie the signing process to the revelation of a secret value in the sense that, much like a regular signature scheme, an adaptor signature scheme can authenticate messages, but simultaneously leaks a secret to certain parties. Recently, Aumayr et al. provide the first formalization of adaptor signature schemes, and present provably secure constructions from ECDSA and Schnorr signatures. Unfortunately, the formalization and constructions given in this work have two limitations: (1) current schemes are limited to ECDSA and Schnorr signatures, and no generic transformation for constructing adaptor signatures is known; (2) they do not offer support for aggregated two-party signing, which can significantly reduce the blockchain footprint in applications of adaptor signatures.

In this work, we address these two shortcomings. First, we show that signature schemes that are constructed from identification (ID) schemes, which additionally satisfy certain homomorphic properties, can generically be transformed into adaptor signature schemes. We further provide an impossibility result which proves that unique signature schemes (e.g., the BLS scheme) cannot be transformed into an adaptor signature scheme. In addition, we define two-party adaptor signature schemes with aggregatable public keys and show how to instantiate them via a generic transformation from ID-based signature schemes. Finally, we give instantiations of our generic transformations for the Schnorr, Katz-Wang and Guillou-Quisquater signature schemes.