## CryptoDB

### Kenneth G. Paterson

#### Publications

**Year**

**Venue**

**Title**

2020

JOFC

Multilinear Maps from Obfuscation
Abstract

We provide constructions of multilinear groups equipped with natural hard problems from indistinguishability obfuscation, homomorphic encryption, and NIZKs. This complements known results on the constructions of indistinguishability obfuscators from multilinear maps in the reverse direction. We provide two distinct, but closely related constructions and show that multilinear analogues of the $${\text {DDH}} $$ DDH assumption hold for them. Our first construction is symmetric and comes with a $$\kappa $$ κ -linear map $$\mathbf{e }: {{\mathbb {G}}}^\kappa \longrightarrow {\mathbb {G}}_T$$ e : G κ ⟶ G T for prime-order groups $${\mathbb {G}}$$ G and $${\mathbb {G}}_T$$ G T . To establish the hardness of the $$\kappa $$ κ -linear $${\text {DDH}} $$ DDH problem, we rely on the existence of a base group for which the $$\kappa $$ κ -strong $${\text {DDH}} $$ DDH assumption holds. Our second construction is for the asymmetric setting, where $$\mathbf{e }: {\mathbb {G}}_1 \times \cdots \times {\mathbb {G}}_{\kappa } \longrightarrow {\mathbb {G}}_T$$ e : G 1 × ⋯ × G κ ⟶ G T for a collection of $$\kappa +1$$ κ + 1 prime-order groups $${\mathbb {G}}_i$$ G i and $${\mathbb {G}}_T$$ G T , and relies only on the 1-strong $${\text {DDH}} $$ DDH assumption in its base group. In both constructions, the linearity $$\kappa $$ κ can be set to any arbitrary but a priori fixed polynomial value in the security parameter. We rely on a number of powerful tools in our constructions: probabilistic indistinguishability obfuscation, dual-mode NIZK proof systems (with perfect soundness, witness-indistinguishability, and zero knowledge), and additively homomorphic encryption for the group $$\mathbb {Z}_N^{+}$$ Z N + . At a high level, we enable “bootstrapping” multilinear assumptions from their simpler counterparts in standard cryptographic groups and show the equivalence of PIO and multilinear maps under the existence of the aforementioned primitives.

2019

TOSC

libInterMAC: Beyond Confidentiality and Integrity in Practice
📺
Abstract

Boldyreva et al. (Eurocrypt 2012) defined a fine-grained security model capturing ciphertext fragmentation attacks against symmetric encryption schemes. The model was extended by Albrecht et al. (CCS 2016) to include an integrity notion. The extended security model encompasses important security goals of SSH that go beyond confidentiality and integrity to include length hiding and denial-of-service resistance properties. Boldyreva et al. also defined and analysed the InterMAC scheme, while Albrecht et al. showed that InterMAC satisfies stronger security notions than all currently available SSH encryption schemes. In this work, we take the InterMAC scheme and make it fully ready for use in practice. This involves several steps. First, we modify the InterMAC scheme to support encryption of arbitrary length plaintexts and we replace the use of Encrypt-then-MAC in InterMAC with modern noncebased authenticated encryption. Second, we describe a reference implementation of the modified InterMAC scheme in the form of the library libInterMAC. We give a performance analysis of libInterMAC. Third, to test the practical performance of libInterMAC, we implement several InterMAC-based encryption schemes in OpenSSH and carry out a performance analysis for the use-case of file transfer using SCP. We measure the data throughput and the data overhead of using InterMAC-based schemes compared to existing schemes in OpenSSH. Our analysis shows that, for some network set-ups, using InterMAC-based schemes in OpenSSH only moderately affects performance whilst providing stronger security guarantees compared to existing schemes.

2019

PKC

Safety in Numbers: On the Need for Robust Diffie-Hellman Parameter Validation
Abstract

We consider the problem of constructing Diffie-Hellman (DH) parameters which pass standard approaches to parameter validation but for which the Discrete Logarithm Problem (DLP) is relatively easy to solve. We consider both the finite field setting and the elliptic curve setting.For finite fields, we show how to construct DH parameters (p, q, g) for the safe prime setting in which
$$p=2q+1$$
is prime, q is relatively smooth but fools random-base Miller-Rabin primality testing with some reasonable probability, and g is of order q mod p. The construction involves modifying and combining known methods for obtaining Carmichael numbers. Concretely, we provide an example with 1024-bit p which passes OpenSSL’s Diffie-Hellman validation procedure with probability
$$2^{-24}$$
(for versions of OpenSSL prior to 1.1.0i). Here, the largest factor of q has 121 bits, meaning that the DLP can be solved with about
$$2^{64}$$
effort using the Pohlig-Hellman algorithm. We go on to explain how this parameter set can be used to mount offline dictionary attacks against PAKE protocols. In the elliptic curve case, we use an algorithm of Bröker and Stevenhagen to construct an elliptic curve E over a finite field
$${\mathbb {F}}_p$$
having a specified number of points n. We are able to select n of the form
$$h\cdot q$$
such that h is a small co-factor, q is relatively smooth but fools random-base Miller-Rabin primality testing with some reasonable probability, and E has a point of order q. Concretely, we provide example curves at the 128-bit security level with
$$h=1$$
, where q passes a single random-base Miller-Rabin primality test with probability 1/4 and where the elliptic curve DLP can be solved with about
$$2^{44}$$
effort. Alternatively, we can pass the test with probability 1/8 and solve the elliptic curve DLP with about
$$2^{35.5}$$
effort. These ECDH parameter sets lead to similar attacks on PAKE protocols relying on elliptic curves.Our work shows the importance of performing proper (EC)DH parameter validation in cryptographic implementations and/or the wisdom of relying on standardised parameter sets of known provenance.

2018

TOSC

Frequency-smoothing encryption: preventing snapshot attacks on deterministically encrypted data
Abstract

Statistical analysis of ciphertexts has been recently used to carry out devastating inference attacks on deterministic encryption (Naveed, Kamara, and Wright, CCS 2015), order-preserving/revealing encryption (Grubbs et al., S&P 2017), and searchable encryption (Pouliot and Wright, CCS 2016). At the heart of these inference attacks is classical frequency analysis. In this paper, we propose and evaluate another classical technique, homophonic encoding, as a means to combat these attacks. We introduce and develop the concept of frequency-smoothing encryption (FSE) which provably prevents inference attacks in the snapshot attack model, wherein the adversary obtains a static snapshot of the encrypted data, while preserving the ability to efficiently and privately make point queries. We provide provably secure constructions for FSE schemes, and we empirically assess their security for concrete parameters by evaluating them against real data. We show that frequency analysis attacks (and optimal generalisations of them for the FSE setting) no longer succeed.

2018

TCHES

Cold Boot Attacks on Ring and Module LWE Keys Under the NTT
★
Abstract

In this work, we consider the ring- and module- variants of the LWE problem and investigate cold boot attacks on cryptographic schemes based on these problems, wherein an attacker is faced with the problem of recovering a scheme’s secret key from a noisy version of that key. The leakage resilience of cryptography based on the learning with errors (LWE) problem has been studied before, but there are only limited results considering the parameters observed in cold boot attack scenarios. There are two main encodings for storing ring- and module-LWE keys, and, as we show, the performance of cold boot attacks can be highly sensitive to the exact encoding used. The first encoding stores polynomial coefficients directly in memory. The second encoding performs a number theoretic transform (NTT) before storing the key, a commonly used method leading to more efficient implementations. We first give estimates for a cold boot attack complexity on the first encoding method based on standard algorithms; this analysis confirms that this encoding method is vulnerable to cold boot attacks only at very low bit-flip rates. We then show that, for the second encoding method, the structure introduced by using an NTT is exploitable in the cold boot setting: we develop a bespoke attack strategy that is much cheaper than our estimates for the first encoding when considering module-LWE keys. For example, at a 1% bit-flip rate (which corresponds roughly to what can be achieved in practice for cold boot attacks when applying cooling), a cold boot attack on Kyber KEM parameters has a cost of 243 operations when the second, NTT-based encoding is used for key storage, compared to 270 operations with the first encoding. On the other hand, in the case of the ring-LWE-based KEM, New Hope, the cold boot attack complexities are similar for both encoding methods.

2015

EPRINT

2014

ASIACRYPT

2012

PKC

2010

EPRINT

Plaintext-Dependent Decryption: A Formal Security Treatment of SSH-CTR
Abstract

This paper presents a formal security analysis of SSH in counter mode in a security model that accurately captures the capabilities of real-world attackers, as well as security-relevant features of the SSH specifications and the OpenSSH implementation of SSH. Under reasonable assumptions on the block cipher and MAC algorithms used to construct the SSH Binary Packet Protocol (BPP), we are able to show that the SSH BPP meets a strong and appropriate notion of security: indistinguishability under buffered, stateful chosen-ciphertext attacks. This result helps to bridge the gap between the existing security analysis of the SSH BPP by Bellare et al. and the recently discovered attacks against the SSH BPP by Albrecht et al. which
partially invalidate that analysis.

2010

EPRINT

Time-Specific Encryption
Abstract

This paper introduces and explores the new concept of Time-Specific Encryption (TSE). In (Plain) TSE, a Time Server broadcasts a key at the beginning of each time unit, a Time Instant Key (TIK). The sender of a message can specify any time interval during the encryption process; the receiver can decrypt to recover the message only if it has a TIK that corresponds to a time in that interval. We extend Plain TSE to the public-key and identity-based settings, where receivers are additionally equipped with private keys and either public keys or identities, and where decryption now requires the use of the private key as well as an appropriate TIK. We introduce security models for the plain, public-key and identity-based settings. We also provide constructions for schemes in the different settings, showing how to obtain Plain TSE using identity-based techniques, how to combine Plain TSE with public-key and identity-based encryption schemes, and how to build schemes that are chosen-ciphertext secure from schemes that are chosen-plaintext secure. Finally, we suggest applications for our new primitive, and discuss its relationships with existing primitives, such as Timed Release Encryption and Broadcast Encryption.

2008

EPRINT

Efficient One-round Key Exchange in the Standard Model
Abstract

We consider one-round identity-based key exchange protocols secure
in the standard model. The security analysis uses the powerful security model of Canetti and
Krawczyk and a natural extension of it to the ID-based setting. It is shown how
KEMs can be used in a generic way to obtain two different
protocol designs with progressively stronger security guarantees. A detailed
analysis of the performance of the protocols is included; surprisingly, when
instantiated with specific KEM constructions, the resulting protocols are
competitive with the best previous schemes that have proofs only in the random
oracle model.

2007

EPRINT

Certificateless Encryption Schemes Strongly Secure in the Standard Model
Abstract

This paper presents the first constructions for certificateless encryption (CLE) schemes that are provably secure against strong adversaries in the standard model. It includes both a generic construction for a strongly secure CLE scheme from any passively secure scheme as well as a concrete construction based on the Waters identity-based encryption scheme.

2007

EPRINT

On the Relations Between Non-Interactive Key Distribution, Identity-Based Encryption and Trapdoor Discrete Log Groups
Abstract

We investigate the relationships between identity-based non-interactive key distribution and identity-based encryption. We provide constructions for these schemes that make use of general trapdoor discrete log groups. We then investigate the schemes that result in two concrete settings, obtaining new, provably secure, near-practical identity-based encryption schemes.

2007

EPRINT

Attacking the IPsec Standards in Encryption-only Configurations
Abstract

At Eurocrypt 2006, Paterson and Yau demonstrated how flaws in the Linux implementation of IPsec could be exploited to break encryption-only configurations of ESP, the IPsec encryption protocol. Their work highlighted the dangers of not using authenticated encryption in fielded systems, but did not constitute an attack on the actual IPsec standards themselves; in fact, the attacks of Paterson and Yau should be prevented by any standards-compliant IPsec implementation. In contrast, this paper describes new attacks which break any RFC-compliant implementation of IPsec making use of encryption-only ESP. The new attacks are both efficient and realistic: they are ciphertext-only and need only the capability to eavesdrop on ESP-encrypted traffic and to inject traffic into the network. The paper also reports our experiences in applying the attacks to a variety of implementations of IPsec, and reflects on what these experiences tell us about how security standards should be written so as to simplify the task of software developers.

2006

EPRINT

Efficient Identity-based Signatures Secure in the Standard Model
Abstract

The only known construction of identity-based signatures that can be
proven secure in the standard model is based on the approach of
attaching certificates to non-identity-based signatures. This
folklore construction method leads to schemes that are somewhat
inefficient and leaves open the problem of finding more efficient
direct constructions. We present the first such construction. Our
scheme is obtained from a modification of Waters' recently proposed
identity-based encryption scheme. It is computationally
efficient and the signatures are short. The scheme's security is
proven in the standard model and rests on the hardness of the
computational Diffie-Hellman problem in groups equipped with a
pairing.

2006

EPRINT

A Cryptographic Tour of the IPsec Standards
Abstract

In this article, we provide an overview of cryptography and cryptographic key management as they are specified in IPsec, a popular suite of standards for providing communications security and network access control for Internet communications. We focus on the latest generation of the IPsec standards, recently published as Request for Comments 43014309 by the Internet Engineering Task Force, and how they have evolved from earlier versions of the standards.

2006

EPRINT

Pairings for Cryptographers
Abstract

Many research papers in pairing based cryptography
treat pairings as a ``black box''. These papers build
cryptographic schemes making use of various properties of
pairings.
If this approach is taken, then it is easy for authors to
make invalid assumptions concerning the properties of pairings.
The cryptographic schemes developed
may not be realizable in practice, or may not be
as efficient as the authors assume.
The aim of this paper is to outline, in as simple a fashion
as possible, the basic choices that are available when
using pairings in cryptography. For each choice, the main
properties and efficiency issues are summarized. The paper is
intended to be of use to non-specialists who are interested
in using pairings to design cryptographic schemes.

2006

EPRINT

An Attack on a Certificateless Signature Scheme
Abstract

This paper demonstrates that a certificateless signature scheme recently proposed by Gorantla and Saxena is insecure. It is shown that an adversary who replaces the public key of a signer can then forge valid signatures for that signer without knowledge of the signer's private key.

2005

EPRINT

Cryptography in Theory and Practice: The Case of Encryption in IPsec
Abstract

This paper studies the gaps that exist between cryptography as studied in theory, as defined in standards, as implemented by software engineers, and as actually consumed by users. Our focus is on IPsec, an important and widely-used suite of protocols providing security at the IP layer of network communications. Despite well-known results in theoretical cryptography highlighting the vulnerabilities of unauthenticated encryption, the IPsec standards currently mandate its support. We present evidence that such ``encryption-only'' configurations are in fact still often selected by users in practice, even with strong warnings advising against this in the IPsec standards. We then describe a variety of attacks against such configurations and report on their successful implementation in the case of the Linux kernel implementation of IPsec. Our attacks are
realistic in their requirements, highly efficient, and recover the complete contents of IPsec-protected datagrams. Our attacks still apply when integrity protection is provided by a higher layer protocol, and in some cases even when it is supplied by IPsec itself.
Finally in this paper, we reflect on the reasons why this unsatisfactory situation persists, and make some recommendations for the future development of IPsec and cryptographic software in general.

2004

EPRINT

Why Quantum Cryptography?
Abstract

Quantum Key Exchange (QKE, also known as Quantum Key Distribution or QKD) allows communicating parties to securely establish cryptographic keys. It is a well-established fact that all QKE protocols require that the parties have access to an authentic channel. Without this authenticated link, QKE is vulnerable to man-in-the-middle attacks. Unfortunately this fact is frequently overlooked, resulting in exaggerated claims and/or false expectations about the potential impact of QKE. In this paper we present a systematic comparison of QKE with traditional key exchange protocols in realistic secure communication systems.

2003

EPRINT

Certificateless Public Key Cryptography
Abstract

This paper introduces the concept of 'certificateless public
key cryptography' (CL-PKC). In contrast to traditional public key
cryptographic systems, CL-PKC does not require the use of
certificates to guarantee the authenticity of public keys. It does
rely on the use of a trusted third party (TTP) who is in
possession of a master key. In these respects, CL-PKC is similar
to identity-based public key cryptography (ID-PKC). On the other
hand, CL-PKC does not suffer from the key escrow property that
seems to be inherent in ID-PKC. Thus CL-PKC can be seen as a model
for the use of public key cryptography that is intermediate
between traditional certificated PKC and ID-PKC.
We make concrete the concept of CL-PKC by introducing
certificateless public key encryption (CL-PKE), signature and key
exchange schemes. We also demonstrate how hierarchical CL-PKC can
be supported. The schemes are all derived from pairings on
elliptic curves. The lack of certificates and the desire to prove
the schemes secure in the presence of an adversary who has access
to the master key requires the careful development of new security
models. For reasons of brevity, the focus in this paper is on the
security of CL-PKE. We prove that our CL-PKE scheme is secure in a
fully adaptive adversarial model, provided that an underlying
problem closely related to the Bilinear Diffie-Hellman Problem is
hard.

2003

EPRINT

Cryptanalysis of a Message Authentication Code due to Cary and Venkatesan
Abstract

We present a cryptanalysis of a MAC proposal at CRYPTO 2003 due to
Cary and Venkatesan. Our attacks find collisions for the MAC and yield MAC forgeries, both faster than a straightforward application of the birthday paradox would suggest.

2002

EPRINT

ID-based Signatures from Pairings on Elliptic Curves
Abstract

We present an efficient identity-based signature scheme which makes
use of bilinear pairings on elliptic curves. Our scheme is similar to
the generalized ElGamal signature scheme. We consider the security of
our scheme.

2002

EPRINT

Tripartite Authenticated Key Agreement Protocols from Pairings
Abstract

Joux's protocol is a one round, tripartite key
agreement protocol that is more bandwidth-efficient than any
previous three-party key agreement protocol. But it is insecure,
suffering from a simple man-in-the-middle attack. This paper shows
how to make Joux's protocol secure, presenting several tripartite,
authenticated key agreement protocols that still require only one
round of communication. A pass-optimal authenticated and key
confirmed tripartite protocol that generalises the
station-to-station protocol is also presented. The security
properties of the new protocols are studied using provable
security methods and heuristic approaches. Applications for the
protocols are also discussed.

#### Program Committees

- Crypto 2018
- Crypto 2016
- FSE 2016
- Eurocrypt 2015
- PKC 2014
- Asiacrypt 2013
- Eurocrypt 2013
- Asiacrypt 2012
- Crypto 2012
- Eurocrypt 2011 (Program chair)
- Crypto 2011
- PKC 2010
- PKC 2009
- Eurocrypt 2008
- Crypto 2007
- PKC 2006
- Eurocrypt 2006
- Asiacrypt 2006

#### Coauthors

- Michel Abdalla (2)
- Sattam S. Al-Riyami (4)
- Martin R. Albrecht (7)
- Mihir Bellare (3)
- Fabrice Benhamouda (2)
- Simon R. Blackburn (2)
- Alexandra Boldyreva (3)
- Colin Boyd (1)
- Torben Brandt Hansen (1)
- Xuefei Cao (1)
- Liqun Chen (1)
- Yvonne Cliff (1)
- Jean Paul Degabriele (5)
- Alexander W. Dent (2)
- Amit Deo (1)
- Adam Everspaugh (1)
- Pooya Farshim (5)
- Marc Fischlin (1)
- Eduarda S. V. Freire (1)
- Eduarda S.V. Freire (1)
- Steven D. Galbraith (2)
- Felix Günther (1)
- Shuai Han (1)
- Dennis Hofheinz (5)
- Eike Kiltz (1)
- Weidong Kou (1)
- Hugo Krawczyk (1)
- Caroline Kudla (2)
- Marie-Sarah Lacharité (1)
- Enrique Larraia (3)
- Benoît Libert (4)
- Shengli Liu (2)
- Atul Luykx (1)
- Giorgia Azzurra Marson (1)
- Jake Massimo (1)
- Kanta Matsuura (1)
- Bart Mennink (1)
- Chris J. Mitchell (1)
- Sean Murphy (1)
- Juan Manuel González Nieto (1)
- Alain Passelègue (2)
- Fred Piper (1)
- Bertram Poettering (2)
- Antigoni Polychroniadou (1)
- Elizabeth A. Quaglia (3)
- Thomas Ristenpart (2)
- Phillip Rogaway (2)
- Ruediger Schack (1)
- Jacob C. N. Schuldt (9)
- Samuel Scott (1)
- Thomas Shrimpton (1)
- Dale L. Sibborn (4)
- Nigel P. Smart (1)
- Sriramkrishnan Srinivasan (1)
- Martijn Stam (4)
- Christoph Striecks (1)
- Susan Thomson (2)
- Gaven J. Watson (3)
- Hoeteck Wee (2)
- Peter R. Wild (1)
- Joanne Woodage (1)
- Arnold K. L. Yau (3)