International Association
for Cryptologic Research

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.

In this paper, we study the security of the Legendre PRF against quantum attackers, given classical queries only, and without quantum random-access memories. We give two algorithms that recover the key of a shifted Legendre symbol with unknown shift, with a complexity smaller than exhaustive search of the key. The first one is a quantum variant of the table-based collision algorithm. The second one uses Kuperberg's abelian hidden shift algorithm in an offline manner. We show that the latter, although asymptotically promising, is not currently the most efficient against practical parameters.

Development of signature schemes providing short signatures is a quite relevant non-trivial challenge for cryptographers. Since the late 1980’s many short signature schemes have been proposed. The most perspective schemes are multivariate schemes and schemes based on Weil pairing. Unfortunately, the cryptographic tools used in these schemes are still not supported by most cryptographic software that complicates their effortless use in practice.

In the current paper we investigate the opportunity of shortening the standard ElGamal-type signatures. We propose three methods of shortening signatures (for any ElGamal-type schemes such as ECDSA, GOST and SM2) and analyze how applying these methods affects the security. Applying all three methods to the GOST signature scheme with elliptic curve subgroup order $q$, $2^{255} < q < 2^{256}$, can reduce the signature size from $512$ to $320$ bits. The modified scheme provides sufficient security and acceptable (for non-interactive protocols) signing and verifying time.

Although there have been many successes in verifying proofs of non-interactive cryptographic primitives such as encryption and signatures, formal verification of interactive cryptographic protocols is still a nascent area. While in principle, it seems possible to extend general frameworks such as Easycrypt to encode proofs for more complex, interactive protocols, a big challenge is whether the human effort would be scalable enough for proof mechanization to eventually acquire mainstream usage among the cryptography community. We work towards closing this gap by introducing a simple framework, Interactive Probabilistic Dependency Logic (IPDL), for reasoning about a certain well-behaved subset of cryptographic protocols. A primary design goal of IPDL is for formal cryptographic proofs to resemble their on-paper counterparts. To this end, IPDL includes an equational logic to reason about approximate observational equivalence (i.e., computational indistinguishability) properties between protocols. IPDL adopts a channel-centric core logic, which decomposes the behavior of the protocol into the behaviors along each communication channel. IPDL supports straight-line programs with statically bounded loops. This design allows us to capture a broad class of protocols encountered in the cryptography literature, including multi-party, reactive, and/or inductively-defined protocols; meanwhile, the logic can track the runtime of the computational reduction in security proofs, thus ensuring computational soundness. We demonstrate the use of IPDL by a number of case studies, including a multi-use, secure message communication protocol, a multi-party coin toss with abort protocol, several oblivious transfer constructions, as well as the two-party GMW protocol for securely evaluating general circuits. We provide a mechanization of the IPDL proof system and our case studies in Coq, and our code is open sourced at https://github.com/ipdl/ipdl.

With an eye towards applications in cryptography, we consider the problem of evaluating boolean functions through affine-linear arithmetic functionals. We show that each subset of the discrete unit cube admits an exact covering by affine hyperplanes (over a sufficiently large prime field). We study the complexity class consisting of boolean functions whose on-sets and off-sets admit coverings by polynomially many hyperplanes. This extends and improves upon a framework of Ishai and Kushilevitz (FOCS '00). We also investigate a number of concrete examples.

We moreover study the concrete construction of compact coverings, and provide new geometric algorithms. Our logic synthesizer constructs affine coverings of cube subsets using a recursive backtracking procedure, and minimizes the total number of flats used; it may be of independent interest. This represents a new paradigm in boolean logic minimization. We relate this paradigm to classical logic synthesis.

Applying our paradigm, we present a general protocol for commitment-consistent secure two-party computation with an untrusted third party, generalizing a construction of Wagh, Gupta, and Chandran (PETS '19). Our generalization supports the secure evaluation of arbitrary boolean functionalities; we also add commitment-consistency and malicious security under one corruption. We report on a highly efficient implementation of a specialization of this general protocol to a certain natural boolean function.