Public-Key Cryptography -- PKC 2015

We study simulation-based, selective opening security against chosen-ciphertext attacks (SIM-SO-CCA security) for public key encryption (PKE). In a selective opening, chosen-ciphertext attack (SO-CCA), an adversary has access to a decryption oracle, sees a vector of ciphertexts, adaptively chooses to open some of them, and obtains the corresponding plaintexts and random coins used in the creation of the ciphertexts. The SIM-SO-CCA notion captures the security of unopened ciphertexts with respect to probabilistic polynomial-time (ppt) SO-CCA adversaries in a semantic way: what a ppt SO-CCA adversary can compute can also be simulated by a ppt simulator with access only to the opened messages. Building on techniques used to achieve weak deniable encryption and non-committing encryption, Fehr

et al.

(Eurocrypt 2010) presented an approach to constructing SIM-SO-CCA secure PKE from extended hash proof systems (EHPSs), collision-resistant hash functions and an information-theoretic primitive called Cross Authentication Codes (XACs). We generalize their approach by introducing a special type of Key Encapsulation Mechanism (KEM) and using it to build SIM-SO-CCA secure PKE. We investigate what properties are needed from the KEM to achieve SIM-SO-CCA security. We also give three instantiations of our construction. The first uses hash proof systems, the second relies on the

$$n$$

-Linear assumption, and the third uses indistinguishability obfuscation (

$$i\mathcal {O}$$

) in combination with extracting, puncturable Pseudo-Random Functions in a similar way to Sahai and Waters (STOC 2014). Our results establish the existence of SIM-SO-CCA secure PKE assuming only the existence of one-way functions and

$$i\mathcal {O}$$

. This result further highlights the simplicity and power of

$$i\mathcal {O}$$

in constructing different cryptographic primitives.

We show that two well-known and widely employed public-key encryption schemes –

RSA

Optimal Asymmetric Encryption Padding (

RSA

-

OAEP

) and Diffie-Hellman Integrated Encryption Standard (

DHIES

), the latter one instantiated with a one-time pad, – are secure under (the strong, simulation-based security notion of) selective opening security against chosen-ciphertext attacks in the random oracle model. Both schemes are obtained via known generic transformations that transform relatively weak primitives (with security in the sense of one-wayness) to

INDCCA

secure encryption schemes. We prove that selective opening security comes for free in these two transformations. Both

DHIES

and

RSA

-

OAEP

are important building blocks in several standards for public key encryption and key exchange protocols. They are the first practical cryptosystems that meet the strong notion of simulation-based selective opening (

SIM-SO-CCA

) security.

This paper presents three curious findings about deterministic public-key encryption (D-PKE) that further our understanding of its security, in particular because of the contrast with standard, randomized public-key encryption (R-PKE):

It would appear to be a triviality, for any primitive, that security in the standard model implies security in the random-oracle model, and it is certainly true, and easily proven, for R-PKE. For D-PKE it is not clear and depends on details of the definition. In particular we can show it in the non-uniform case but not in the uniform case.

The power of selective-opening attacks (SOA) comes from an adversary’s ability, upon corrupting a sender, to learn not just the message but also the coins used for encryption. For R-PKE, security is achievable. For D-PKE, where there are no coins, one’s first impression may be that SOAs are vacuous and security should be easily achievable. We show instead that SOA-security is impossible, meaning no D-PKE scheme can achieve it.

For R-PKE, single-user security implies multi-user security, but we show that there are D-PKE schemes secure for a single user and insecure with two users.

Divisible E-cash systems allow users to withdraw a unique coin of value

$$2^n$$

from a bank, but then to spend it in several times to distinct merchants. In such a system, whereas users want anonymity of their transactions, the bank wants to prevent, or at least detect, double-spending, and trace the defrauders. While this primitive was introduced two decades ago, quite a few (really) anonymous constructions have been introduced. In addition, all but one were just proven secure in the random oracle model, but still with either weak security models or quite complex settings and thus costly constructions. The unique proposal, secure in the standard model, appeared recently and is unpractical. As evidence, the authors left the construction of an efficient scheme secure in this model as an open problem.

In this paper, we answer it with the first efficient divisible E-cash system secure in the standard model. It is based on a new way of building the coins, with a unique and public global tree structure for all the coins. Actually, we propose two constructions: a very efficient one in the random oracle model and a less efficient, but still practical, in the standard model. They both achieve constant time for withdrawing and spending coins, while allowing the bank to quickly detect double-spendings by a simple comparison of the serial numbers of deposited coins to the ones of previously spent coins.

Cryptographic e-cash allows off-line electronic transactions between a bank, users and merchants in a secure and anonymous fashion. A plethora of e-cash constructions has been proposed in the literature; however, these traditional e-cash schemes only allow coins to be transferred once between users and merchants. Ideally, we would like users to be able to transfer coins between each other multiple times before deposit, as happens with physical cash.

“Transferable” e-cash schemes are the solution to this problem. Unfortunately, the currently proposed schemes are either completely impractical or do not achieve the desirable anonymity properties without compromises, such as assuming the existence of a trusted “judge” who can trace all coins and users in the system. This paper presents the first efficient and fully anonymous transferable e-cash scheme without any trusted third parties. We start by revising the security and anonymity properties of transferable e-cash to capture issues that were previously overlooked. For our construction we use the recently proposed malleable signatures by Chase et al. to allow the secure and anonymous transfer of coins, combined with a new efficient double-spending detection mechanism. Finally, we discuss an instantiation of our construction.

Some of the most efficient algorithms for finding the discrete logarithm involve pseudo-random implementations of Markov chains, with one or more “walks” proceeding until a collision occurs, i.e. some state is visited a second time. In this paper we develop a method for determining the expected time until the first collision. We use our technique to examine three methods for solving discrete-logarithm problems: Pollard’s Kangaroo, Pollard’s Rho, and a few versions of Gaudry-Schost. For the Kangaroo method we prove new and fairly precise matching upper and lower bounds. For the Rho method we prove the first rigorous non-trivial lower bound, and under a mild assumption show matching upper and lower bounds. Our Gaudry-Schost results are heuristic, but improve on the prior limited understanding of this method. We also give results for parallel versions of these algorithms.

We investigate the security of the family of MQQ public key cryptosystems using multivariate quadratic quasigroups (MQQ). These cryptosystems show especially good performance properties. In particular, the MQQ-SIG signature scheme is the fastest scheme in the ECRYPT benchmarking of cryptographic systems (eBACS). We show that both the signature scheme MQQ-SIG and the encryption scheme MQQ-ENC, although using different types of MQQs, share a common algebraic structure that introduces a weakness in both schemes. We use this weakness to mount a successful polynomial time key-recovery attack that finds an equivalent key using the idea of so-called

good keys

. In the process we need to solve a MinRank problem that, because of the structure, can be solved in polynomial-time assuming some mild algebraic assumptions. We highlight that our theoretical results work in characteristic

$$2$$

which is known to be the most difficult case to address in theory for MinRank attacks and also without any restriction on the number of polynomials removed from the public-key. This was not the case for previous MinRank like-attacks against

$$\mathcal {MQ}$$

schemes. From a practical point of view, we are able to break an MQQ-SIG instance of

$$80$$

bits security in less than

$$2$$

days, and one of the more conservative MQQ-ENC instances of

$$128$$

bits security in little bit over

$$9$$

days. Altogether, our attack shows that it is very hard to design a secure public key scheme based on an easily invertible MQQ structure.

The BBCRS scheme is a variant of the McEliece public-key encryption scheme where the hiding phase is performed by taking the inverse of a matrix which is of the form

$$\varvec{T}+ \varvec{R}$$

where

$$\varvec{T}$$

is a sparse matrix with average row/column weight equal to a very small quantity

$$m$$

, usually

$$m < 2$$

, and

$$\varvec{R}$$

is a matrix of small rank

$$z\ge 1$$

. The rationale of this new transformation is the reintroduction of families of codes, like generalized Reed-Solomon codes, that are famously known for representin insecure choices. We present a key-recovery attack when

$$z =1$$

and

$$m$$

is chosen between

$$1$$

and

$$1+R+O(\frac{1}{\sqrt{n}})$$

where

$$R$$

denotes the code rate. This attack has complexity

$$O(n^6)$$

and breaks all the parameters suggested in the literature.

We investigate the Hidden Subspace Problem (

$$\mathrm{HSP}_q$$

) over

$${\mathbb {F}}_q$$

:

Input :

$$p_1,\ldots ,p_m,q_1,\ldots ,q_m\in {\mathbb {F}}_q[x_1,\ldots ,x_n]$$

of degree

$$d\ge 3$$

(and

$$n\le m\le 2n$$

).

Find :

a subspace

$$A\subset {{\mathbb {F}}_q}^n$$

of dimension

$$n/2$$

(

$$n$$

is even) such that

$$\begin{aligned} p_i(A)=0\,\,\forall i\in \{1,\ldots ,m\}\,\,\text {and}\,\, q_j(A^{\perp })=0\,\,\forall j\in \{1,\ldots ,m\}, \end{aligned}$$

where

$$A^{\perp }$$

denotes the orthogonal complement of

$$A$$

with respect to the usual scalar product in

$${\mathbb {F}}_q$$

.

This problem underlies the security of the first public-key quantum money scheme that is proved to be cryptographically secure under a non quantum but classic hardness assumption. This scheme was proposed by S. Aaronson and P. Christiano [

1

] at STOC’12. In particular, it depends upon the hardness of

$${\mathrm{HSP}}_2$$

. More generally, Aaronson and Christiano left as an open problem to study the security of the scheme for a general field

$${\mathbb {F}}_q$$

. We present a randomized polynomial-time algorithm that solves the

$${\mathrm{HSP}}_q$$

for

$$q>d$$

with success probability

$$\approx 1-1/q$$

. So, the quantum money scheme extended to

$${\mathbb {F}}_q$$

is not secure for big

$$q$$

. Finally, based on experimental results and a structural property of the polynomials that we prove, we conjecture that there is also a randomized polynomial-time algorithm solving the

$${\mathrm{HSP}}_2$$

with high probability. To support our theoretical results we also present several experimental results confirming that our algorithms are very efficient in practice. We emphasize that [

1

] proposes a non-noisy and a noisy version of the public-key quantum money scheme. The noisy version of the quantum money scheme remains secure.

We construct a signature scheme that is proved secure, without random oracles, under the strong RSA assumption. Unlike other efficient strong-RSA based schemes, the new scheme does not generate large prime numbers during signing. The public key size and signature size are competitive with other strong RSA schemes, but verification is less efficient. The new scheme adapts the prefix signing technique of Hohenberger and Waters (CRYPTO 2009) to work without generating primes.

We present a lattice-based stateless signature scheme provably secure in the standard model. Our scheme has a

constant

number of matrices in the public key and a single lattice vector (plus a tag) in the signatures. The best previous lattice-based encryption schemes were the scheme of Ducas and Micciancio (CRYPTO 2014), which required a logarithmic number of matrices in the public key and that of Bohl et. al (J. of Cryptology 2014), which required a logarithmic number of lattice vectors in the signature. Our main technique involves using fully homomorphic computation to compute a degree

$$d$$

polynomial over the tags hidden in the matrices in the public key. In the scheme of Ducas and Micciancio, only functions

linear

over the tags in the public key matrices were used, which necessitated having

$$d$$

matrices in the public key.

As a matter of independent interest, we extend Wichs’ (eprint 2014) recent construction of homomorphic trapdoor functions into a primitive we call puncturable homomorphic trapdoor functions (PHTDFs). This primitive abstracts out most of the properties required in many different lattice-based cryptographic constructions. We then show how to combine a PHTDF along with a function satisfying certain properties (to be evaluated homomorphically) to give an eu-scma signature scheme.

We give a new framework for obtaining signatures with a tight security reduction from standard hardness assumptions. Concretely, we show that any Chameleon Hash function can be transformed into a (binary) tree-based signature scheme with tight security. The transformation is in the standard model, i.e., it does not make use of any random oracle. For specific assumptions (such as RSA, Diffie-Hellman and Short Integer Solution (SIS)) we further manage to obtain a more efficient flat-tree construction. Our framework explains and generalizes most of the existing schemes as well as providing a generic means for constructing tight signature schemes based on arbitrary assumptions, which improves the standard Merkle tree transformation. Moreover, we obtain the first tightly secure signature scheme from the SIS assumption and several schemes based on Diffie-Hellman in the standard model.

Some of our signature schemes can (using known techniques) be combined with Groth-Sahai proof methodology to yield tightly secure and efficient simulation-sound NIZK proofs of knowledge and CCA-secure encryption in the multi-user/-challenge setting under classical assumptions.

Protecting user data entails providing authenticated users access to their data. The most prevalent and probably also the most feasible approach to the latter is by username and password. With password breaches through server compromise now reaching billions of affected passwords, distributing the password files and user data over multiple servers is not just a good idea, it is a dearly needed solution to a topical problem. Threshold password-authenticated secret sharing (TPASS) protocols enable users to share secret data among a set of servers so that they can later recover that data using a single password. No coalition of servers up to a certain threshold can learn anything about the data or perform an offline dictionary attack on the password. Several TPASS protocols have appeared in the literature and one is even available commercially. Although designed to tolerate server corruptions, unfortunately none of these protocols provide details, let alone security proofs, about how to proceed when a compromise actually occurs. Indeed, they consider static corruptions only, which for instance does not model real-world adaptive attacks by hackers. We provide the first TPASS protocol that is provably secure against adaptive server corruptions. Moreover, our protocol contains an efficient recovery procedure allowing one to re-initialize servers to recover from corruption. We prove our protocol secure in the universal-composability model where servers can be corrupted adaptively at any time; the users’ passwords and secrets remain safe as long as both servers are not corrupted at the same time. Our protocol does not require random oracles but does assume that servers have certified public keys.

We show by counter-example that the soundness security requirement for witness encryption given by Garg, Gentry, Sahai and Waters (STOC 2013) does not suffice for the security of their own applications. We introduce adaptively-sound (AS) witness encryption to fill the gap. We then introduce asymmetric password-based encryption (A-PBE). This offers gains over classical, symmetric password-based encryption in the face of attacks that compromise servers to recover hashed passwords. We distinguish between invasive A-PBE schemes (they introduce new password-based key-derivation functions) and non-invasive ones (they can use existing, deployed password-based key-derivation functions). We give simple and efficient invasive A-PBE schemes and use AS-secure witness encryption to give non-invasive A-PBE schemes.

Indistinguishability under adaptive chosen-ciphertext attack (

IND-CCA

) is now considered the

de facto

security notion for public-key encryption. However, the security guarantee that it offers is sometimes stronger than what is needed by certain applications. In this paper, we consider a weaker notion of security for public-key encryption, termed indistinguishability under plaintext-checking attacks (

IND-PCA

), in which the adversary is only given access to an oracle which says whether or not a given ciphertext encrypts a given message. After formalizing the

IND-PCA

notion, we then design a new public-key encryption scheme satisfying it. The new scheme is a more efficient variant of the Cramer-Shoup encryption scheme with shorter ciphertexts and its security is also based on the plain Decisional Diffie-Hellman (

DDH

) assumption. Additionally, the algebraic properties of the new scheme also allow for proving plaintext knowledge using Groth-Sahai non-interactive zero-knowledge proofs or smooth projective hash functions. Finally, in order to illustrate the usefulness of the new scheme, we further show that, for many password-based authenticated key exchange (

PAKE

) schemes in the Bellare-Pointcheval-Rogaway security model, one can safely replace the underlying

IND-CCA

encryption schemes with our new

IND-PCA

one. By doing so, we were able to reduce the overall communication complexity of these protocols and obtain the most efficient

PAKE

schemes to date based on the plain

DDH

assumption.

Recent work on structure-preserving signatures studies optimality of these schemes in terms of the number of group elements needed in the verification key and the signature, and the number of pairing-product equations in the verification algorithm. While the size of keys and signatures is crucial for many applications, another important aspect to consider for performance is the time it takes to verify a given signature. By far, the most expensive operation during verification is the computation of pairings. However, the concrete number of pairings that one needs to compute is not captured by the number of pairing-product equations considered in earlier work.

To fill this gap, we consider the question of what is the minimal number of pairings that one needs to compute in the verification of structure-preserving signatures. First, we prove lower bounds for schemes in the Type II setting that are secure under chosen message attacks in the generic group model, and we show that three pairings are necessary and that at most one of these pairings can be precomputed. We also extend our lower bound proof to schemes secure under random message attacks and show that in this case two pairings are still necessary.

Second, we build an automated tool to search for schemes matching our lower bounds. The tool can generate automatically and exhaustively all valid structure-preserving signatures within a user-specified search space, and analyze their (bounded) security in the generic group model. Interestingly, using this tool, we find a new randomizable structure-preserving signature scheme in the Type II setting that is optimal with respect to the lower bound on the number of pairings, and also minimal with respect to the number of group operations that have to be computed during verification.

Composite-order bilinear groups provide many structural features that are useful for both constructing cryptographic primitives and enabling security reductions. Despite these convenient features, however, composite-order bilinear groups are less desirable than prime-order bilinear groups for reasons of both efficiency and security. A recent line of work has therefore focused on translating these structural features from the composite-order to the prime-order setting; much of this work focused on two such features, projecting and canceling, in isolation, but a result due to Seo and Cheon showed that both features can be obtained simultaneously in the prime-order setting.

In this paper, we reinterpret the construction of Seo and Cheon in the context of dual pairing vector spaces (which provide canceling as well as useful parameter hiding features) to obtain a unified framework that simulates all of these composite-order features in the prime-order setting. We demonstrate the strength of this framework by providing two applications: one that adds dual pairing vector spaces to the existing projection in the Boneh-Goh-Nissim encryption scheme to obtain leakage resilience, and another that adds the concept of projecting to the existing dual pairing vector spaces in an IND-CPA-secure IBE scheme to “boost” its security to IND-CCA1. Our leakage-resilient BGN application is of independent interest, and it is not clear how to achieve it from pure composite-order techniques without mixing in additional vector space tools. Both applications rely solely on the Symmetric External Diffie Hellman assumption (SXDH).

A group signature allows a group member to anonymously sign messages on behalf of the group. In the past few years, new group signatures based on lattice problems have appeared: the most efficient lattice-based constructions are due to Laguillaumie

et al.

(Asiacrypt ’13) and Langlois

et al.

(PKC ’14). Both have at least

$$O(n^2\log ^2 n \log N)$$

-bit group public key and

$$O(n\log ^3 n\log N)$$

-bit signature, where

$$n$$

is the security parameter and

$$N$$

is the maximum number of group members. In this paper, we present a simpler lattice-based group signature, which is more efficient by a

$$O(\log N)$$

factor in both the group public key and the signature size. We achieve this by using a new non-interactive zero-knowledge (NIZK) proof corresponding to a simple identity-encoding function. The security of our group signature can be reduced to the hardness of SIS and LWE in the random oracle model.

We introduce a lattice-based group signature scheme that provides several noticeable improvements over the contemporary ones: simpler construction, weaker hardness assumptions, and shorter sizes of keys and signatures. Moreover, our scheme can be transformed into the ring setting, resulting in a scheme based on ideal lattices, in which the public key and signature both have bit-size

$$\widetilde{\mathcal {O}}(n\cdot \log N)$$

, for security parameter

$$n$$

, and for group of

$$N$$

users. Towards our goal, we construct a new lattice-based cryptographic tool: a statistical zero-knowledge argument of knowledge of a valid message-signature pair for Boyen’s signature scheme (Boyen, PKC’10), which potentially can be used as the building block to design various privacy-enhancing cryptographic constructions.

As formalized by Kiltz

et al.

(ICALP ’05), append-only signatures (AOS) are digital signature schemes where anyone can publicly append extra message blocks to an already signed sequence of messages. This property is useful,

e.g.

, in secure routing, in collecting response lists, reputation lists, or petitions. Bethencourt, Boneh and Waters (NDSS ’07) suggested an interesting variant, called

history-hiding

append-only signatures (HH-AOS), which handles messages as sets rather than ordered tuples. This HH-AOS primitive is useful when the exact order of signing needs to be hidden. When free of subliminal channels (i.e., channels that can tag elements in an undetectable fashion), it also finds applications in the storage of ballots on an electronic voting terminals or in other archival applications (such as the record of petitions, where we want to hide the influence among messages). However, the only subliminal-free HH-AOS to date only provides heuristic arguments in terms of security: Only a proof in the idealized (non-realizable) random oracle model is given. This paper provides the first HH-AOS construction secure in the standard model. Like the system of Bethencourt

et al.

, our HH-AOS features constant-size public keys, no matter how long messages to be signed are, which is atypical (we note that secure constructions often suffer from a space penalty when compared to their random-oracle-based counterpart). As a second result, we show that, even if we use it to sign ordered vectors as in an ordinary AOS (which is always possible with HH-AOS), our system provides considerable advantages over existing realizations. As a third result, we show that HH-AOS schemes provide improved identity-based ring signatures (i.e., in prime order groups and with a better efficiency than the state-of-the-art schemes).

One-round authenticated key exchange (ORKE) is an established research area, with many prominent protocol constructions like HMQV (Krawczyk, CRYPTO 2005) and Naxos (La Macchia

et al.

, ProvSec 2007), and many slightly different, strong security models. Most constructions combine ephemeral and static Diffie-Hellman Key Exchange (DHKE), in a manner often closely tied to the underlying security model.

We give a generic construction of ORKE protocols from general assumptions, with security in the standard model, and in a strong security model where the attacker is even allowed to learn the randomness or the long-term secret of either party in the target session. The only restriction is that the attacker must not learn

both

the randomness

and

the long-term secret of one party of the target session, since this would allow him to recompute all internal states of this party, including the session key.

This is the first such construction that does not rely on random oracles. The construction is intuitive, relatively simple, and efficient. It uses only standard primitives, namely non-interactive key exchange, a digital signature scheme, and a pseudorandom function, with standard security properties, as building blocks.

We propose the first UC secure commitment scheme with (amortized) computational complexity linear in the size of the string committed to. After a preprocessing phase based on oblivious transfer, that only needs to be done once and for all, our scheme only requires a pseudorandom generator and a linear code with efficient encoding. We also construct an additively homomorphic version of our basic scheme using VSS. Furthermore we evaluate the concrete efficiency of our schemes and show that the amortized computational overhead is significantly lower than in the previous best constructions. In fact, our basic scheme has amortised concrete efficiency comparable with previous protocols in the Random Oracle Model even though it is constructed in the plain model.

This paper considers the problem of secure storage of outsourced data in a way that permits deduplication. We are for the first time able to provide privacy for messages that are both correlated and dependent on the public system parameters. The new ingredient that makes this possible is interaction. We extend the message-locked encryption (MLE) primitive of prior work to interactive message-locked encryption (iMLE) where upload and download are protocols. Our scheme, providing security for messages that are not only correlated but allowed to depend on the public system parameters, is in the standard model. We explain that interaction is not an extra assumption in practice because full, existing deduplication systems are already interactive.

In this paper we present a new multiplication algorithm for residues modulo the Mersenne prime

$$2^{521} - 1$$

. Using this approach, on an Intel Haswell Core i7-4770, constant-time variable-base scalar multiplication on NIST’s (and SECG’s) curve P-521 requires 1,108,000 cycles, while on the recently proposed Edwards curve E-521 it requires just 943,000 cycles. As a comparison, on the same architecture openSSL’s ECDH speed test for curve P-521 requires 1,319,000 cycles. Furthermore, our code was written entirely in C and so is robust across different platforms. The basic observation behind these speedups is that the form of the modulus allows one to multiply residues with as few word-by-word multiplications as is needed for squaring, while incurring very little overhead from extra additions, in contrast to the usual Karatsuba methods.

Related-Key Attacks (RKAs) allow an adversary to observe the outcomes of a cryptographic primitive under not only its original secret key e.g.,

$$s$$

, but also a sequence of modified keys

$$\phi (s)$$

, where

$$\phi $$

is specified by the adversary from a class

$$\varPhi $$

of so-called Related-Key Derivation (RKD) functions. This paper extends the notion of non-malleable Key Derivation Functions (nm-KDFs), introduced by Faust et al. (EUROCRYPT’14), to

continuous

nm-KDFs. Continuous nm-KDFs have the ability to protect against any a-priori

unbounded

number of RKA queries, instead of just a single time tampering attack as in the definition of nm-KDFs. Informally, our continuous non-malleability captures the scenario where the adversary can tamper with the original secret key repeatedly and adaptively. We present a novel construction of continuous nm-KDF for any polynomials of bounded degree over a finite field. Essentially, our result can be extended to richer RKD function classes possessing properties of

high output entropy and input-output collision resistance

. The technical tool employed in the construction is the one-time lossy filter (Qin et al. ASIACRYPT’13) which can be efficiently obtained under standard assumptions, e.g., DDH and DCR. We propose a framework for constructing

$$\varPhi $$

-RKA-secure IBE, PKE and signature schemes, using a continuous nm-KDF for the same

$$\varPhi $$

-class of RKD functions. Applying our construction of continuous nm-KDF to this framework, we obtain the first RKA-secure IBE, PKE and signature schemes for a class of polynomial RKD functions of bounded degree under

standard

assumptions. While previous constructions for the same class of RKD functions all rely on non-standard assumptions, e.g.,

$$d$$

-extended DBDH assumption.

We present a

universal framework

for tamper and leakage resilient computation on a random access machine (RAM). The RAM has one CPU that accesses a storage, which we call the disk. The disk is subject to leakage and tampering. So is the bus connecting the CPU to the disk. We assume that the CPU is leakage and tamper-free. For a fixed value of the security parameter, the CPU has

constant size

. Therefore the code of the program to be executed is stored on the disk, i.e., we consider a von Neumann architecture. The most prominent consequence of this is that the code of the program executed will be subject to tampering.

We construct a compiler for this architecture which transforms any keyed primitive into a RAM program where the key is encoded and stored on the disk along with the program to evaluate the primitive on that key. Our compiler only assumes the existence of a so-called continuous non-malleable code, and it only needs black-box access to such a code. No further (cryptographic) assumptions are needed. This in particular means that given an information theoretic code, the overall construction is information theoretic secure.

Although it is required that the CPU is tamper and leakage proof, its design is independent of the actual primitive being computed and its internal storage is non-persistent, i.e., all secret registers are reset between invocations. Hence, our result can be interpreted as reducing the problem of shielding arbitrary complex computations to protecting a single, simple yet universal component.

Cryptographic schemes based on the Learning Parity with Noise (LPN) problem have several very desirable aspects: Low computational overhead, simple implementation and conjectured post-quantum hardness. Choosing the LPN noise parameter sufficiently low allows for public key cryptography. In this work, we construct the first standard model public key encryption scheme with key dependent message security based solely on the low noise LPN problem. Additionally, we establish a new connection between LPN with a bounded number of samples and LPN with an unbounded number of samples. In essence, we show that if LPN with a small error and a small number of samples is hard, then LPN with a slightly larger error and an unbounded number of samples is also hard. The key technical ingredient to establish both results is a variant of the LPN problem called the extended LPN problem.

We formalise the notion of adaptive proofs of knowledge in the random oracle model, where the extractor has to recover witnesses for multiple, possibly adaptively chosen statements and proofs. We also discuss extensions to simulation soundness, as typically required for the “encrypt-then-prove” construction of strongly secure encryption from IND-CPA schemes. Utilizing our model we show three results:

(1)

Simulation-sound adaptive proofs exist.

(2)

The “encrypt-then-prove” construction with a simulation-sound adaptive proof yields CCA security. This appears to be a “folklore” result but which has never been proven in the random oracle model. As a corollary, we obtain a new class of CCA-secure encryption schemes.

(3)

We show that the Fiat-Shamir transformed Schnorr protocol is

not

adaptively secure and discuss the implications of this limitation.

Our result not only separates adaptive proofs from proofs of knowledge, but also gives a strong hint why Signed ElGamal as the most prominent encrypt-then-prove example has not been proven CCA-secure without making further assumptions.

Damgård, Fazio and Nicolosi (TCC 2006) gave a transformation of Sigma-protocols, 3-move honest verifier zero-knowledge proofs, into efficient non-interactive zero-knowledge arguments for a designated verifier. Their transformation uses additively homomorphic encryption to encrypt the verifier’s challenge, which the prover uses to compute an encrypted answer. The transformation does not rely on the random oracle model but proving soundness requires a complexity leveraging assumption.

We propose an alternative instantiation of their transformation and show that it achieves culpable soundness without complexity leveraging. This improves upon an earlier result by Ventre and Visconti (Africacrypt 2009), who used a different construction which achieved

weak

culpable soundness.

We demonstrate how our construction can be used to prove validity of encrypted votes in a referendum. This yields a voting system with homomorphic tallying that does not rely on the Fiat-Shamir heuristic.

We describe a method to bootstrap a packed BGV ciphertext which does not depend (as much) on any special properties of the plaintext and ciphertext moduli. Prior “efficient” methods such as that of Gentry et al. (PKC 2012) required a ciphertext modulus

$$q$$

which was close to a power of the plaintext modulus

$$p$$

. This enables our method to be applied in a larger number of situations. Also unlike previous methods our depth grows only as

$$O(\log p + \log \log q)$$

as opposed to the

$$\log q$$

of previous methods. Our basic bootstrapping technique makes use of a representation of the group

$${\mathbb {Z}}_q^+$$

over the finite field

$${\mathbb {F}}_p$$

(either based on polynomials or elliptic curves), followed by polynomial interpolation of the reduction mod

$$p$$

map over the coefficients of the algebraic group.

This technique is then extended to the full BGV packed ciphertext space, using a method whose depth depends only logarithmically on the number of packed elements. This method may be of interest as an alternative to the method of Alperin-Sheriff and Peikert (CRYPTO 2013). To aid efficiency we utilize the ring/field switching technique of Gentry et al. (SCN 2012, JCS 2013).

We construct the first fully homomorphic encryption (FHE) scheme that encrypts

matrices

and supports homomorphic

matrix

addition and multiplication. This is a natural extension of packed FHE and thus supports more complicated homomorphic operations. We optimize the bootstrapping procedure of Alperin-Sheriff and Peikert (CRYPTO 2014) by applying our scheme. Our optimization decreases the lattice approximation factor from

$$\tilde{O}(n^{3})$$

to

$$\tilde{O}(n^{2.5})$$

. By taking a lattice dimension as a larger polynomial in a security parameter, we can also obtain the same approximation factor as the best known one of standard lattice-based public-key encryption

without

successive dimension-modulus reduction, which was essential for achieving the best factor in prior works on bootstrapping of standard lattice-based FHE.

At the center of many lattice-based constructions is an algorithm that samples a short vector

$$\mathbf{s}$$

, satisfying

$$[\mathbf{A}|\mathbf{A}\mathbf{R}-\mathbf{H}\mathbf{G}]\mathbf{s}=\mathbf{t}\text { mod }q$$

where

$$\mathbf{A},\mathbf{A}\mathbf{R}, \mathbf{H}, \mathbf{G}$$

are public matrices and

$$\mathbf{R}$$

is a trapdoor. Although the algorithm crucially relies on the knowledge of the trapdoor

$$\mathbf{R}$$

to perform this sampling efficiently, the distribution it outputs should be independent of

$$\mathbf{R}$$

given the public values. We present a new, simple algorithm for performing this task. The main novelty of our sampler is that the distribution of

$$\mathbf{s}$$

does not need to be Gaussian, whereas all previous works crucially used the properties of the Gaussian distribution to produce such an

$$\mathbf{s}$$

. The advantage of using a non-Gaussian distribution is that we are able to avoid the high-precision arithmetic that is inherent in Gaussian sampling over arbitrary lattices. So while the norm of our output vector

$$\mathbf{s}$$

is on the order of

$$\sqrt{n}$$

to

$$n$$

- times larger (the representation length, though, is only a constant factor larger) than in the samplers of Gentry, Peikert, Vaikuntanathan (STOC 2008) and Micciancio, Peikert (EUROCRYPT 2012), the sampling itself can be done very efficiently. This provides a useful time/output trade-off for devices with constrained computing power. In addition, we believe that the conceptual simplicity and generality of our algorithm may lead to it finding other applications.

Functional encryption is a new paradigm in public-key encryption that allows users to finely control the amount of information that is revealed by a ciphertext to a given receiver. Recent papers have focused their attention on constructing schemes for general functionalities at expense of efficiency. Our goal, in this paper, is to construct functional encryption schemes for less general functionalities which are still expressive enough for practical scenarios. We propose a functional encryption scheme for the

inner-product

functionality, meaning that decrypting an encrypted vector

$$\mathbf {x}$$

with a key for a vector

$$\mathbf {y}$$

will reveal only

$$\langle \mathbf {x},\mathbf {y} \rangle $$

and nothing else, whose security is based on the DDH assumption. Despite the simplicity of this functionality, it is still useful in many contexts like descriptive statistics. In addition, we generalize our approach and present a generic scheme that can be instantiated, in addition, under the LWE assumption and offers various trade-offs in terms of expressiveness and efficiency.

We construct a lattice-based predicate encryption scheme for multi-dimensional range and multi-dimensional subset queries. Our scheme is selectively secure and weakly attribute-hiding, and its security is based on the standard learning with errors (LWE) assumption. Multi-dimensional range and subset queries capture many interesting applications pertaining to searching on encrypted data. To the best of our knowledge, these are the first lattice-based predicate encryption schemes for functionalities beyond IBE and inner product.

Functional Encryption (FE) is an exciting new paradigm that extends the notion of public key encryption. In this work we explore the security of Inner Product Functional Encryption schemes with the goal of achieving the highest security against practically feasible attacks. While there has been substantial research effort in defining meaningful security models for FE, known definitions run into one of the following difficulties – if general and strong, the definition can be shown impossible to achieve, whereas achievable definitions necessarily restrict the usage scenarios in which FE schemes can be deployed.

We argue that it is extremely hard to control the nature of usage scenarios that may arise in practice. Any cryptographic scheme may be deployed in an arbitrarily complex environment and it is vital to have meaningful security guarantees for general scenarios. Hence, in this work, we examine whether it is possible to analyze the security of FE in a wider variety of usage scenarios, but with respect to a meaningful class of adversarial attacks known to be possible in practice. Note that known impossibilities necessitate that we must either restrict the usage scenarios (as done in previous works), or the class of attacks (this work). We study real world loss-of-secrecy attacks against Functional Encryption for Inner Product predicates constructed over elliptic curve groups. Our main contributions are as follows:

We capture a large variety of possible usage scenarios that may arise in practice by providing a

stronger

, more general, intuitive framework that supports

function privacy

in addition to data privacy, and a separate

encryption key

in addition to public key and master secret key. These generalizations allow our framework to capture program obfuscation as a special case of functional encryption, and allows for a separation between users that encrypt data, access data and produce secret keys.

We note that the landscape of attacks over pairing-friendly elliptic curves have been the subject of extensive research and there now exist constructions of pairing-friendly elliptic curves where the complexity of all known non-generic attacks is (far) greater than the complexity of generic attacks. Thus, by appropriate choice of the underlying elliptic curve, we can capture all known practically feasible attacks on secrecy by restricting our attention to generic attacks.

We construct a new inner product FE scheme using prime order groups and show it secure under our new, hitherto strongest known framework in the generic group model, thus ruling out all generic attacks in arbitrarily complex real world environments. Since our construction is over prime order groups, we rule out factoring attacks that typically force higher security parameters. Our concrete-analysis proofs provide guidance on the size of elliptic curve groups that are needed for explicit complexity bounds on the attacker.

We construct an identity-based encryption (IBE) scheme that is tightly secure in a very strong sense. Specifically, we consider a setting with many instances of the scheme and many encryptions per instance. In this setting, we reduce the security of our scheme to a variant of a simple assumption used for a similar purpose by Chen and Wee (Crypto 2013). The security loss of our reduction is (

$$\mathbf {O}$$

(

$$k$$

) ) (where

$$k $$

is the security parameter). Our scheme is the first IBE scheme to achieve this strong flavor of tightness under a simple assumption.

Technically, our scheme is a variation of the IBE scheme by Chen and Wee. However, in order to “lift” their results to the multi-instance, multi-ciphertext case, we need to develop new ideas. In particular, while we build on (and extend) their high-level proof strategy, we deviate significantly in the low-level proof steps.