International Association for Cryptologic Research

International Association
for Cryptologic Research

CryptoDB

Kristian Gjøsteen

Publications

Year
Venue
Title
2020
CRYPTO
Fast and Secure Updatable Encryption 📺
Updatable encryption allows a client to outsource ciphertexts to some untrusted server and periodically rotate the encryption key. The server can update ciphertexts from an old key to a new key with the help of an update token, received from the client, which should not reveal anything about plaintexts to an adversary. We provide a new and highly efficient suite of updatable encryption schemes that we collectively call SHINE. In the variant designed for short messages, ciphertext generation consists of applying one permutation and one exponentiation (per message block), while updating ciphertexts requires just one exponentiation. Variants for longer messages provide much stronger security guarantees than prior work that has comparable efficiency. We present a new confidentiality notion for updatable encryption schemes that implies prior notions. We prove that SHINE is secure under our new confidentiality definition while also providing ciphertext integrity.
2019
CRYPTO
Highly Efficient Key Exchange Protocols with Optimal Tightness 📺
In this paper we give nearly-tight reductions for modern implicitly authenticated Diffie-Hellman protocols in the style of the Signal and Noise protocols, which are extremely simple and efficient. Unlike previous approaches, the combination of nearly-tight proofs and efficient protocols enables the first real-world instantiations for which the parameters can be chosen in a theoretically sound manner.Our reductions have only a linear loss in the number of users, implying that our protocols are more efficient than the state of the art when instantiated with theoretically sound parameters. We also prove that our security proofs are optimal: a linear loss in the number of users is unavoidable for our protocols for a large and natural class of reductions.
2018
CRYPTO
Practical and Tightly-Secure Digital Signatures and Authenticated Key Exchange 📺
Kristian Gjøsteen Tibor Jager
Tight security is increasingly gaining importance in real-world cryptography, as it allows to choose cryptographic parameters in a way that is supported by a security proof, without the need to sacrifice efficiency by compensating the security loss of a reduction with larger parameters. However, for many important cryptographic primitives, including digital signatures and authenticated key exchange (AKE), we are still lacking constructions that are suitable for real-world deployment.We construct the first truly practical signature scheme with tight security in a real-world multi-user setting with adaptive corruptions. The scheme is based on a new way of applying the Fiat-Shamir approach to construct tightly-secure signatures from certain identification schemes.Then we use this scheme as a building block to construct the first practical AKE protocol with tight security. It allows the establishment of a key within 1 RTT in a practical client-server setting, provides forward security, is simple and easy to implement, and thus very suitable for practical deployment. It is essentially the “signed Diffie-Hellman” protocol, but with an additional message, which is crucial to achieve tight security. This additional message is used to overcome a technical difficulty in constructing tightly-secure AKE protocols.For a theoretically-sound choice of parameters and a moderate number of users and sessions, our protocol has comparable computational efficiency to the simple signed Diffie-Hellman protocol with EC-DSA, while for large-scale settings our protocol has even better computational performance, at moderately increased communication complexity.
2015
JOFC
2015
EPRINT
2010
EPRINT
Analysis of an internet voting protocol
Kristian Gjøsteen
The Norwegian government is planning trials of internet voting in the 2011 local government elections. We describe and analyse the cryptographic protocol that will be used. In our opinion, the protocol is suitable for trials of internet voting, even though it is not perfect. This paper is a second1 step in an ongoing evaluation of the cryptographic protocol.
2007
CRYPTO
2007
EPRINT
A Security Analysis of the NIST SP 800-90 Elliptic Curve Random Number Generator
Daniel R. L. Brown Kristian Gjøsteen
An elliptic curve random number generator (ECRNG) has been approved in a NIST standards and proposed for ANSI and SECG draft standards. This paper proves that, if three conjectures are true, then the ECRNG is secure. The three conjectures are hardness of the elliptic curve decisional Diffie-Hellman problem and the hardness of two newer problems, the x-logarithm problem and the truncated point problem. The x-logarithm problem is shown to be hard if the decisional Diffie-Hellman problem is hard, although the reduction is not tight. The truncated point problem is shown to be solvable when the minimum amount of bits allowed in NIST standards are truncated, thereby making it insecure for applications such as stream ciphers. Nevertheless, it is argued that for nonce and key generation this distinguishability is harmless.
2006
EPRINT
A Latency-Free Election Scheme
Kristian Gjøsteen
We motivate and describe the problem of finding protocols for multiparty computations that only use a single broadcast round per computation (latency-free computations). We show that solutions exists for one multiparty computation problem, that of elections, and more generally, addition in certain groups. The protocol construction is based on an interesting pseudo-random function family with a novel property.
2006
EPRINT
Universally Composable Blind Signatures in the Plain Model
Aslak Bakke Buan Kristian Gjøsteen Lillian Kr\aa kmo
In the universal composability framework, we define an ideal functionality for blind signatures, as an alternative to a functionality recently proposed by Fischlin. Fischlin proves that his functionality cannot be realized in the plain model, but this result does not apply to our functionality. We show that our functionality is realized in the plain model by a blind signature protocol if and only if the corresponding blind signature scheme is secure with respect to blindness and non-forgeability, as defined by Juels, Luby and Ostrovsky.
2005
ASIACRYPT
2005
PKC
2005
EPRINT
Security notions for disk encryption
Kristian Gjøsteen
We define security goals and attack models for disk encryption, and prove several relationships between the resulting security notions, and some general results about disk encryption. We give concrete constructions for every security notion along with security proofs. Finally, we briefly discuss the security of some implementations and standards for disk encryption.
2005
EPRINT
Spreading Alerts Quietly and the Subgroup Escape Problem
We introduce a new cryptographic primitive called the blind coupon mechanism (BCM). In effect, the BCM is an authenticated bit-commitment, which is AND-homomorphic. It has not been known how to construct such commitments before. We show that the BCM has natural and important applications. In particular, we use it to construct a mechanism for transmitting alerts undetectably in a message-passing system of n nodes. Our algorithms allow an alert to quickly propagate to all nodes without its source or existence being detected by an adversary, who controls all message traffic. Our proofs of security are based on a new subgroup escape problem, which seems hard on certain groups with bilinear pairings and on elliptic curves over the ring Zn.
2004
EPRINT
A new security proof for Damg?rd's ElGamal
Kristian Gjøsteen
We provide a new security proof for a variant of ElGamal proposed by Damg{\aa}rd, showing that it is secure against non-adaptive chosen ciphertext. Unlike previous security proofs for this cryptosystem, which rely on somewhat problematic assumptions, our computational problem is similar to accepted problems such the Gap and Decision Diffie-Hellman problems.
2003
EPRINT
Homomorphic public-key systems based on subgroup membership problems
Kristian Gjøsteen
We describe the group structure underlying several popular homomorphic public-key systems and the problems they are based on. We prove several well-known security results using only the group structure and assumptions about the related problems. Then we provide examples of two new instances of this group structure and analyse their security.

Program Committees

Crypto 2008
PKC 2008