International Association
for Cryptologic Research

The efficiency of a black-box reduction is an important goal of modern cryptography. Traditionally, the time complexity and the success probability were considered as the main aspects of efficiency measurements. In CRYPTO 2017, Auerbach et al. introduced the notion of memory-tightness in cryptographic reductions and showed a memory-tight reduction of the existential unforgeability of the RSA-FDH signature scheme. Unfortunately, their techniques do not extend directly to the reductions involving intricate RO-programming. The problem seems to be inherent as all the other existing results on memory-tightness are lower bounds and impossibility results. In fact, Auerbach et al. conjectured that a memory-tight reduction for IND-CCA security of Hashed-ElGamal KEM is impossible.   -We refute the above conjecture. Using a simple RO simulation technique, we provide memory-tight reductions of IND-CCA  security of the Cramer-Shoup and the ECIES version of Hashed-ElGamal KEM.  

- We prove memory-tight reductions for different variants of Fujisaki-Okamoto Transformation. We analyze the modular transformations introduced by  Hofheinz,  H\"{o}vermanns and Kiltz (TCC 2017). In addition to the constructions involving implicit rejection, we present a memory-tight reduction for the IND-CCA  security of the transformation ${\mbox{QFO}_m^\perp}$. Our techniques can withstand correctness-errors, and applicable to several lattice-based KEM candidates.

A nothing-up-my-sleeve number is a cryptographic constant, such as a field size in elliptic curve cryptography, with qualities to assure users against subversion of the number by the system designer. A number with low Kolmogorov descriptional complexity resists being subverted to the extent that the speculated subversion would leave a trace that cannot be hidden within the short description. The roll programming language, a version of Godel's 1930s definition of computability, can somewhat objectively quantify low descriptional complexity, a nothing-up-my-sleeve quality, of a number. For example, $(2^{127}-1)^2$ and $2^{255}-19$ can be described with roll programs of 58 and 84 words.

We study anonymity of probabilistic encryption (pE) and probabilistic authenticated encryption (pAE). We start by providing concise game-based security definitions capturing anonymity for both pE and pAE, and then show that the commonly used notion of indistinguishability from random ciphertexts (IND\$) indeed implies the anonymity notions for both pE and pAE. This is in contrast to a recent work of Chan and Rogaway (Asiacrypt 2019), where it is shown that IND\$-secure nonce-based authenticated encryption can only achieve anonymity if a sophisticated transformation is applied. Moreover, we also show that the Encrypt-then-MAC paradigm is anonymity-preserving, in the sense that if both the underlying probabilistic MAC (pMAC) and pE schemes are anonymous, then also the resulting pAE scheme is. Finally, we provide a composable treatment of anonymity using the constructive cryptography framework of Maurer and Renner (ICS 2011). We introduce adequate abstractions modeling various kinds of anonymous communication channels for many senders and one receiver in the presence of an active man-in-the-middle adversary. Then we show that the game-based notions indeed are anonymity-preserving, in the sense that they imply constructions between such anonymous channels, thus generating authenticity and/or confidentiality as expected, but crucially retaining anonymity if present.

We present a cryptographic construction for anonymous tokens with private metadata bit, a primitive that enables an issuer to provide a user with anonymous trust tokens that can embed a single private metadata bit, which is accessible only to the party who holds the secret authority key and is private with respect to anyone else. Our construction provides unforgeability, unlinkability and privacy for the metadata bit properties.

The potential development of large-scale quantum computers is raising concerns among IT and security research professionals due to their ability to solve (elliptic curve) discrete logarithm and integer factorization problems in polynomial time. All currently used public key algorithms would be deemed insecure in a post-quantum (PQ) setting. In response, the National Institute of Standards and Technology (NIST) has initiated a process to standardize quantum-resistant crypto algorithms, focusing primarily on their security guarantees. Since PQ algorithms present significant differences over classical ones, their overall evaluation should not be performed out-of-context. This work presents a detailed performance evaluation of the NIST signature algorithm candidates and investigates the imposed latency on TLS 1.3 connection establishment under realistic network conditions. In addition, we investigate their impact on TLS session throughput and analyze the trade-off between lengthy PQ signatures and computationally heavy PQ cryptographic operations.

Our results demonstrate that the adoption of at least two PQ signature algorithms would be viable with little additional overhead over current signature algorithms. Also, we argue that many NIST PQ candidates can effectively be used for less time-sensitive applications, and provide an in-depth discussion on the integration of PQ authentication in encrypted tunneling protocols, along with the related challenges, improvements, and alternatives. Finally, we propose and evaluate the combination of different PQ signature algorithms across the same certificate chain in TLS. Results show a reduction of the TLS handshake time and a significant increase of a server's TLS tunnel connection rate over using a single PQ signature scheme.

We provide a standard-model implementation (of a relaxation) of the algebraic group model (AGM, [Fuchsbauer, Kiltz, Loss, CRYPTO 2018]). Specifically, we show that every algorithm that uses our group is algebraic, and hence ``must know'' a representation of its output group elements in terms of its input group elements. Here, ``must know'' means that a suitable extractor can extract such a representation efficiently. We stress that our implementation relies only on falsifiable assumptions in the standard model, and in particular does not use any knowledge assumptions.

As a consequence, our group allows to transport a number of results obtained in the AGM into the standard model, under falsifiable assumptions. For instance, we show that in our group, several Diffie-Hellman-like assumptions (including computational Diffie-Hellman) are equivalent to the discrete logarithm assumption. Furthermore, we show that our group allows to prove the Schnorr signature scheme tightly secure in the random oracle model.

Our construction relies on indistinguishability obfuscation, and hence should not be considered as a practical group itself. However, our results show that the AGM is a realistic computational model (since it can be instantiated in the standard model), and that results obtained in the AGM are also possible with standard-model groups.

A blockchain is redactable if a private key holder (e.g. a central authority) can change any single block without violating integrity of the whole blockchain, but no other party can do that. In this paper, we offer a simple method of constructing redactable blockchains inspired by the ideas underlying the well-known RSA encryption scheme. Notably, our method can be used in conjunction with any reasonable hash function that is used to build a blockchain. Public immutability of a blockchain in our construction is based on the computational hardness of the RSA problem and not on properties of the underlying hash function. Corruption resistance is based on the computational hardness of the discrete logarithm problem.

In this note we provide a theoretical argument towards an unsolved question related to Mantin's Digraph Repetition Bias (2005) that is observed in the key-stream of RC4. The open question, that depends on the observation that arrival of four consecutive same bytes in RC4 key-stream is slightly negatively biased, was posed by Bricout et al [Des. Codes Cryptogr. (2018) 86:743-770] in 2016.

We present Daence, a deterministic authenticated cipher based on a pseudorandom function family and a universal hash family, similar to SIV. We recommend instances with Salsa20 or ChaCha, and Poly1305, for high performance, high security, and easy deployment.

Talek is a private group messaging system that sends messages through potentially untrustworthy servers, while hiding both data content and the communication patterns among its users. Talek explores a new point in the design space of private messaging; it guarantees access sequence indistinguishability, which is among the strongest guarantees in the space, while assuming an anytrust threat model, which is only slightly weaker than the strongest threat model currently found in related work. Our results suggest that this is a pragmatic point in the design space, since it supports strong privacy and good performance: we demonstrate a 3-server Talek cluster that achieves throughput of 9,433 messages/second for 32,000 active users with 1.7-second end-to-end latency. To achieve its security goals without coordination between clients, Talek relies on information-theoretic private information retrieval. To achieve good performance and minimize server-side storage, Talek intro- duces new techniques and optimizations that may be of independent interest, e.g., a novel use of blocked cuckoo hashing and support for private notifications. The latter provide a private, efficient mechanism for users to learn, without polling, which logs have new messages.

The Centre for Secure Information Technologies (CSIT) at Queen's University Belfast is seeking motivated PhD students to work on the following research topics:

Secure IoT devices using Digital Fingerprint

Investigating Security Vulnerabilities of Approximate Computing

Practical and Post-quantum IoT security

Practical Privacy-preserving homomorphic analytics

Post Quantum Anonymous Credential

Functional Encryption and its Application

For further information and how to apply, please visit the QUB website for PhD study: http://www.qub.ac.uk/schools/eeecs/Research/PhDStudy/

Closing date for applications:

Contact: Ciara Rafferty: c.m.rafferty@qub.ac.uk

More information: http://www.qub.ac.uk/schools/eeecs/Research/PhDStudy/

Primality testing is a basic cryptographic task. But developers today are faced with complex APIs for primality testing, along with documentation that fails to clearly state the reliability of the tests being performed. This leads to the APIs being incorrectly used in practice, with potentially disastrous consequences. In an effort to overcome this, we present a primality test having a simplest-possible API: the test accepts a number to be tested and returns a Boolean indicating whether the input was composite or probably prime. For all inputs, the output is guaranteed to be correct with probability at least $1 - 2^{128}$. The test is performant: on random, odd, 1024-bit inputs, it is faster than the default test used in OpenSSL by 17\%. We investigate the impact of our new test on the cost of random prime generation, a key use case for primality testing. The OpenSSL developers have adopted our suggestions in full; our new API and primality test are scheduled for release in OpenSSL 3.0.

Dual system encryption is an important method used in pairing-based cryptography for constructing fully secure IBE, ABE and FE schemes. A long time open question is that, whether there is an analogue of dual system method in lattice, which can be used to prove the full security of lattice-based ABE or FE schemes. We solve this problem in this paper.

We do this by introducing a new primitive called approximate inner product encryption (aIPE), which is the approximate version of the well known inner product encryption. We show that a fully secure ABE supporting CNF as its access policy can be constructed from a selectively secure aIPE and the LWE assumption. We also point out that the functionality of aIPE is included in FE for arbitrary circuits, which can be constructed from LWE assumption, hence the full security of our scheme can be totally based on the hardness of LWE.

LAC is a Ring Learning With Error based cryptosystem that has been proposed to the NIST call for post-quantum standardization and passed the first round of the submission process. The particularity of LAC is to use an error-correction code ensuring a high security level with small key sizes and small ciphertext sizes. LAC team proposes a CPA secure cryptosystem, LAC.CPA, and a CCA secure one, LAC.CCA, obtained by applying the Fujisaki-Okamoto transformation on LAC.CPA. In this paper, we study the security of LAC Key Exchange (KE) mechanism, using LAC.CPA, in a misuse context: when the same secret key is reused for several key exchanges and an active adversary has access to a mismatch oracle. This oracle indicates information on the possible mismatch at the end of the KE protocol. In this context, we show that an attacker needs at most $8$ queries to the oracle to retrieve one coefficient of a static secret key. This result has been experimentally confirmed using the reference and optimized implementations of LAC. Since our attack can break the CPA version in a misuse context, the Authenticated KE protocol, based on the CCA version, is not impacted. However, this research provides a tight estimation of LAC resilience against this type of attacks.

Zero-knowledge proofs and in particular succinct non-interactive zero-knowledge proofs (so called zk-SNARKs) are getting increasingly used in real-world applications, with cryptocurrencies being the prime example. Simulation extractability (SE) is a strong security notion of zk-SNARKs which informally ensures non-malleability of proofs. This property is acknowledged as being highly important by leading companies in this field such as Zcash and supported by various attacks against the malleability of cryptographic primitives in the past. Another problematic issue for the practical use of zk-SNARKs is the requirement of a fully trusted setup, as especially for large-scale decentralized applications finding a trusted party that runs the setup is practically impossible. Quite recently, the study of approaches to relax or even remove the trust in the setup procedure, and in particular subversion as well as updatable zk-SNARKs (with latter being the most promising approach), has been initiated and received considerable attention since then. Unfortunately, so far SE-SNARKs with aforementioned properties are only constructed in an ad-hoc manner and no generic techniques are available.

In this paper we are interested in such generic techniques and therefore firstly revisit the only available lifting technique due to Kosba et al. (called COCO) to generically obtain SE-SNARKs. By exploring the design space of many recently proposed SNARK- and STARK-friendly symmetric-key primitives we thereby achieve significant improvements in the prover computation and proof size. Unfortunately, the COCO framework as well as our improved version (called OCOCO) is not compatible with updatable SNARKs. Consequently, we propose a novel generic lifting transformation called Lamassu. It is built using different underlying ideas compared to COCO (and OCOCO). In contrast to COCO it only requires key-homomorphic signatures (which allow to shift keys) covering well studied schemes such as Schnorr or ECDSA. This makes Lamassu highly interesting, as by using the novel concept of so called updatable signatures, which we introduce in this paper, we can prove that Lamassu preserves the subversion and in particular updatable properties of the underlying zk-SNARK. This makes Lamassu the first technique to also generically obtain SE subversion and updatable SNARKs. As its performance compares favorably to OCOCO, Lamassu is an attractive alternative that in contrast to OCOCO is only based on well established cryptographic assumptions.

In a transaction-output-based blockchain system, where each transaction spends UTXOs (the previously unspent transaction outputs), a user must provide a signature, or more precisely a \(\textit{scriptSig}\) for Bitcoin, to spend an UTXO, which proves the ownership of the spending output. When Pedersen commitment \(g^xh^a\) or ElGamal commitment \((g^xh^a,h^x)\) introduced into blockchain as transaction output, for supporting confidential transaction feature, where the input and output amounts in a transaction are hidden, the prior signature schemes such as Schnorr signature scheme and its variants does not directly work here if using the commitment as the public key, since nobody including the committer knows the private key of a \(g^xh^a\) when $a$ is not zero, meaning no one knows the $c$ such that \((g^c=g^xh^a)\). This is a signature scheme which is able to use the \(C=g^xh^a\) as the signature public key for any value of $a$. The signer, proceeding from a random Pedersen commitment \(R=g^{k_1}h^{k_2}\), generates a random bit sequence $e$, by multiplication of a stored private key $x$ with the bit sequence $e$ and by addition of the random number $k_1$ to get the $u$, by multiplication of the committed value $a$ with the bit sequence $e$ and by addition of the random number $k_2$ to get the $v$, finally constructs \(\sigma=(R,u,v)\) as the signature, with the corresponding public key $C$. In turn, the verifier calculates a Pedersen commitment \(S=g^uh^v\), and accepts the signature if \(S=RC^e\). For an electronic signature, a hash value $e$ is calculated from a random Pedersen commitment $R$, the Pedersen commitment $C$, and from the message $m$ to be signed. This signature scheme will be very helpful in the design of a non-interactive transaction in Mimblewimble.

Non-repudiation of messages generated by users is a desirable feature in a number of applications ranging from online banking to IoT scenarios. However, it requires certified public keys and usually results in poor usability as a user must carry around his certificate (e.g., in a smart-card) or must install it in all of his devices. A user-friendly alternative, adopted by several companies and national administrations, is to have a ``cloud-based'' PKI. In a nutshell, each user has a PKI certificate stored at a server in the cloud; users authenticate to the server---via passwords or one-time codes---and ask it to sign messages on their behalf. As such, there is no way for the server to prove to a third party that a signature on a given message was authorized by a user. As the server holds the user's certified key, it might as well have signed arbitrary messages in an attempt to impersonate that user. In other words, a user could deny having signed a message, by claiming that the signature was produced by the server without his consent. The same holds in case the secret key is derived deterministically from the user's password, for the server, by knowing the password, may still frame the user.

In this paper we provide a "password-only" solution to non-repudiation of user messages by introducing Auditable Asymmetric Password Authenticated Public Key Establishment (A2PAKE). This is a PAKE-like protocol that generates an asymmetric key-pair where the public key is output to every participant, but the secret key is private output to just one of the parties (e.g., the user). Further, the protocol can be audited, i.e., given the public key output by a protocol run with a user, the server can prove to a third party that the corresponding secret key is held by that specific user. Thus, if the user signs messages with that secret key, then signatures are non-repudiable. We provide a universally composable definition of A2PAKE and an instantiation based on a distributed oblivious pseudo-random function. We also develop a prototype implementation of our instantiation and use it to evaluate its performance in realistic settings.

ARX-KW is a family of key wrapping construction based on add-rotate-xor primitives: the pseudo-random function SipHash for authentication and the stream cipher ChaCha for confidentiality. This paper presents ARX-KW, proposes a specific instantiation of ARX-KW and details the design decisions that were made.

Today, deep neural networks represent a common option when conducting the profiled side-channel analysis. Such techniques commonly do not require pre-processing, and yet, they can break targets that are even protected with countermeasures. Unfortunately, it is usually far from trivial to find neural network hyper-parameters that would result in such top-performing attacks. The hyper-parameter leading the training process is the number of epochs during which the training happens. If the training is too short, the network does not reach its full capacity, while if the training is too long, the network overfits, and consequently, is not able to generalize to unseen examples. Finding the right moment to stop the training process is particularly difficult for side-channel analysis as there are no clear connections between machine learning and side-channel metrics that govern the training and attack phases, respectively.

In this paper, we tackle the problem of determining the correct epoch to stop the training in deep learning-based side-channel analysis. First, we explore how information is propagated through the hidden layers of a neural network, which allows us to monitor how training is evolving. Second, we demonstrate that the amount of information transferred to the output layer can be measured and used as a reference metric to determine the epoch at which the network offers optimal generalization. To validate the proposed methodology, we provide extensive experimental results that confirm the effectiveness of our metric of choice for avoiding overfitting in the profiled side-channel analysis.

Let $X \in {\mathbb{Z}}^{n \times m}$, with each entry independently and identically distributed from an integer Gaussian distribution. We consider the orthogonal lattice $\Lambda^\perp(X)$ of $X$, i.e., the set of vectors $\mathbf{v} \in {\mathbb{Z}}^m$ such that $X \mathbf{v}= \mathbf{0}$. In this work, we prove probabilistic upper bounds on the smoothing parameter and the $(m-n)$-th minimum of $\Lambda^\perp(X)$. These bounds improve and the techniques build upon prior works of Agrawal, Gentry, Halevi and Sahai [Asiacrypt'13], and of Aggarwal and Regev [Chicago J. Theoret. Comput. Sci.'16].