56 results sorted by ID
Key Policy Attribute-Based Encryption Leveraging Isogeny-Based Cryptography
Madické Diadji Mbodj, Anis Bkakria
Public-key cryptography
We present the first Key Policy Attribute-Based Encryption (KP-ABE) scheme employing isogeny-based cryptography through class group actions, specifically utilizing the Csi-FiSh instantiation and pairing groups. We introduce a new assumption, denoted Isog-DLin, which combines the isogeny and DLin assumptions. We propose the following constructions: a small universe KP-ABE and a large universe KP-ABE under the Isog-DBDH assumption, and a small universe KP-ABE under the Isog-DLin assumption. In...
Attribute-Based Signatures for Circuits with Optimal Parameter Size from Standard Assumptions
Ryuya Hayashi, Yusuke Sakai, Shota Yamada
Public-key cryptography
Attribute-based signatures (ABS) allow users to simultaneously sign messages and prove their possession of some attributes while hiding the attributes and revealing only the fact that they satisfy a public policy. In this paper, we propose a generic construction of ABS for circuits of unbounded depth and size, with optimal parameter size—meaning the lengths of public parameters, keys, and signatures are all constant. Our construction can be instantiated from various standard assumptions,...
FABESA: Fast (and Anonymous) Attribute-Based Encryption under Standard Assumption
Long Meng, Liqun Chen, Yangguang Tian, Mark Manulis
Public-key cryptography
Attribute-Based Encryption (ABE) provides fine-grained access control to encrypted data and finds applications in various domains. The practicality of ABE schemes hinges on the balance between security and efficiency. The state-of-the-art adaptive secure ABE scheme, proven to be adaptively secure under standard assumptions (FAME, CCS'17), is less efficient compared to the fastest one (FABEO, CCS'22) which is only proven secure under the Generic Group Model (GGM). These traditional ABE...
Indistinguishability Obfuscation from LPN over F_p, DLIN, and PRGs in NC^0
Aayush Jain, Huijia Lin, Amit Sahai
Foundations
In this work, we study what minimal sets of assumptions suffice for constructing indistinguishability obfuscation ($i\mathcal{O}$). We prove:
{\bf Theorem}(Informal): Assume sub-exponential security of the following assumptions:
- the Learning Parity with Noise ($\mathsf{LPN}$) assumption over general prime fields $\mathbb{F}_p$ with
polynomially many $\mathsf{LPN}$ samples and error rate $1/k^\delta$, where $k$ is the dimension of the $\mathsf{LPN}$ secret, and $\delta>0$ is any...
Decentralized Multi-Authority ABE for NC^1 from Computational-BDH
Pratish Datta, Ilan Komargodski, Brent Waters
Public-key cryptography
Decentralized multi-authority attribute-based encryption (𝖬𝖠-𝖠𝖡𝖤) is a strengthening of standard ciphertext-policy attribute-based encryption so that there is no trusted central authority: any party can become an authority and there is no requirement for any global coordination other than the creation of an initial set of common reference parameters. Essentially, any party can act as an authority for some attribute by creating a public key of its own and issuing private keys to different...
Simple and Efficient FE for Quadratic Functions
Junqing Gong, Haifeng Qian
Public-key cryptography
This paper presents the first functional encryption schemes for quadratic functions (or degree-2 polynomials) achieving simulation-based security in the semi-adaptive model with constant-size secret key. The unique prior construction with the same security guarantee by Gay [PKC 20] has secret keys of size linear in the message size. They also enjoy shorter ciphertexts:
- our first scheme is based on bilateral DLIN (decisional linear) assumption as Gay's scheme and the ciphertext is 15%...
Statistical ZAPR Arguments from Bilinear Maps
Alex Lombardi, Vinod Vaikuntanathan, Daniel Wichs
Cryptographic protocols
Dwork and Naor (FOCS '00) defined ZAPs as 2-message witness-indistinguishable proofs that are public-coin. We relax this to ``ZAPs with private randomness'' (ZAPRs), where the verifier can use private coins to sample the first message (independently of the statement being proved), but the proof must remain publicly verifiable given only the protocol transcript. In particular, ZAPRs are reusable, meaning that the first message can be reused for multiple proofs without compromising...
Compact NIZKs from Standard Assumptions on Bilinear Maps
Shuichi Katsumata, Ryo Nishimaki, Shota Yamada, Takashi Yamakawa
Foundations
A non-interactive zero-knowledge (NIZK) protocol enables a prover to convince a verifier of the truth of a statement without leaking any other information by sending a single message.
The main focus of this work is on exploring short pairing-based NIZKs for all NP languages based on standard assumptions.
In this regime, the seminal work of Groth, Ostrovsky, and Sahai (J.ACM'12) (GOS-NIZK) is still considered to be the state-of-the-art.
Although fairly efficient, one drawback of GOS-NIZK is...
Verifiable Inner Product Encryption Scheme
Najmeh Soroush, Vincenzo Iovino, Alfredo Rial, Peter B. Roenne, Peter Y. A. Ryan
Public-key cryptography
In the standard setting of functional encryption (FE), we assume both the Central Authority (CA) and the encryptors to run their respective algorithms faithfully.
Badrinarayanan et al [ASIACRYPT 2016] put forth the concept of verifiable FE, which essentially guarantees that dishonest encryptors and authorities, even when colluding together, are not able to generate ciphertexts and tokens that give inconsistent results.
They also provide a compiler turning any perfectly correct FE into a...
Extracting Randomness from Extractor-Dependent Sources
Yevgeniy Dodis, Vinod Vaikuntanathan, Daniel Wichs
Foundations
We revisit the well-studied problem of extracting nearly uniform randomness from an arbitrary source of sufficient min-entropy. Strong seeded extractors solve this problem by relying on a public random seed, which is unknown to the source. Here, we consider a setting where the seed is reused over time and the source may depend on prior calls to the extractor with the same seed. Can we still extract nearly uniform randomness?
In more detail, we assume the seed is chosen randomly, but the...
Shorter QA-NIZK and SPS with Tighter Security
Masayuki Abe, Charanjit S. Jutla, Miyako Ohkubo, Jiaxin Pan, Arnab Roy, Yuyu Wang
Public-key cryptography
Quasi-adaptive non-interactive zero-knowledge proof (QA-NIZK) systems and structure-preserving signature (SPS) schemes are two powerful tools for constructing practical pairing-based cryptographic schemes. Their efficiency directly affects the efficiency of the derived ad- vanced protocols.
We construct more efficient QA-NIZK and SPS schemes with tight security reductions. Our QA-NIZK scheme is the first one that achieves both tight simulation soundness and constant proof size (in terms of...
Fully Homomorphic NIZK and NIWI Proofs
Prabhanjan Ananth, Apoorvaa Deshpande, Yael Tauman Kalai, Anna Lysyanskaya
Foundations
In this work, we define and construct fully homomorphic non-interactive zero knowledge (FH-NIZK) and non-interactive witness-indistinguishable (FH-NIWI) proof systems.
We focus on the NP complete language $L$, where, for a boolean circuit $C$ and a bit $b$, the pair $(C,b) \in L$ if there exists an input $w$ such that $C(w)=b$. For this language, we call a non-interactive proof system 'fully homomorphic' if, given instances $(C_i,b_i) \in L$ along with their proofs $\Pi_i$, for $i \in...
Attribute Based Encryption for Deterministic Finite Automata from DLIN
Shweta Agrawal, Monosij Maitra, Shota Yamada
Public-key cryptography
Waters [Crypto, 2012] provided the first attribute based encryption scheme ABE for Deterministic Finite Automata (DFA) from a parametrized or ``q-type'' assumption over bilinear maps. Obtaining a construction from static assumptions has been elusive, despite much progress in the area of ABE.
In this work, we construct the first attribute based encryption scheme for DFA from static assumptions on pairings, namely, the DLIN assumption. Our scheme supports unbounded length inputs, unbounded...
Efficient Attribute-Based Signatures for Unbounded Arithmetic Branching Programs
Pratish Datta, Tatsuaki Okamoto, Katsuyuki Takashima
Public-key cryptography
This paper presents the first attribute-based signature (ABS) scheme in which the correspondence between
signers and signatures is captured in an arithmetic model of computation. Specifically, we design a fully
secure, i.e., adaptively unforgeable and perfectly signer-private ABS scheme for signing policies realizable
by arithmetic branching programs (ABP), which are a quite expressive model of arithmetic computations.
On a more positive note, the proposed scheme places no bound on the size...
Adaptively Simulation-Secure Attribute-Hiding Predicate Encryption
Pratish Datta, Tatsuaki Okamoto, Katsuyuki Takashima
Public-key cryptography
This paper demonstrates how to achieve simulation-based strong attribute hiding against adaptive adversaries
for predicate encryption (PE) schemes supporting expressive predicate families under standard
computational assumptions in bilinear groups. Our main result is a simulation-based adaptively strongly
partially-hiding PE (PHPE) scheme for predicates computing arithmetic branching programs (ABP) on
public attributes, followed by an inner-product predicate on private attributes. This...
Improved (Almost) Tightly-Secure Simulation-Sound QA-NIZK with Applications
Masayuki Abe, Charanjit S. Jutla, Miyako Ohkubo, Arnab Roy
We construct the first (almost) tightly-secure unbounded-simulation-sound quasi-adaptive non-interactive zero-knowledge arguments (USS-QA-NIZK) for linear-subspace languages with compact (number of group elements independent of the security parameter) common reference string (CRS) and compact proofs under standard assumptions in bilinear-pairings groups. Specifically, our construction has $ O(\log Q) $ reduction to the SXDH, DLIN and matrix-DDH assumptions, where $ Q $ is the number of...
Improved Inner-product Encryption with Adaptive Security and Full Attribute-hiding
Jie Chen, Junqing Gong, Hoeteck Wee
Public-key cryptography
In this work, we propose two IPE schemes achieving both adaptive security and full attribute-hiding in the prime-order bilinear group, which improve upon the unique existing result satisfying both features from Okamoto and Takashima [Eurocrypt '12] in terms of efficiency.
- Our first IPE scheme is based on the standard $k$-Lin assumption and has shorter master public key and shorter secret keys than Okamoto and Takashima's IPE under weaker DLIN=$2$-lin assumption.
- Our second IPE scheme...
New Lower Bounds on Predicate Entropy for Function Private Public-Key Predicate Encryption
Sikhar Patranabis, Debdeep Mukhopadhyay
Public-key cryptography
We present function private public-key predicate encryption schemes from standard cryptographic assumptions, that achieve new lower bounds on the min-entropy of underlying predicate distributions. Existing function private predicate encryption constructions in the public-key setting can be divided into two broad categories. The first category of constructions are based on standard assumptions, but impose highly stringent requirements on the min-entropy of predicate distributions, thereby...
Embed-Augment-Recover: Function Private Predicate Encryption from Minimal Assumptions in the Public-Key Setting
Sikhar Patranabis, Debdeep Mukhopadhyay
We present a new class of public-key predicate encryption schemes that are provably function private in the standard model under well-known cryptographic assumptions, and assume predicate distributions satisfying realistic min-entropy requirements. More concretely, we present public-key constructions for identity-based encryption (IBE) and inner-product encryption (IPE) that are computationally function private in the standard model under a family of weaker variants of the DLIN assumption....
Partitioning via Non-Linear Polynomial Functions: More Compact IBEs from Ideal Lattices and Bilinear Maps
Shuichi Katsumata, Shota Yamada
Public-key cryptography
In this paper, we present new adaptively secure identity-based encryption (IBE) schemes. One of the distinguishing property of the schemes is that it achieves shorter public parameters than previous schemes. Both of our schemes follow the general framework presented in the recent IBE scheme of Yamada (Eurocrypt 2016), employed with novel techniques tailored to meet the underlying algebraic structure to overcome the difficulties arising in our specific setting. Specifically, we obtain the...
A Tag Based Encoding: An Efficient Encoding for Predicate Encryption in Prime Order Groups
Jongkil Kim, Willy Susilo, Fuchun Guo, Man Ho Au
Public-key cryptography
We introduce a tag based encoding, a new generic framework for modular design of Predicate Encryption (PE) schemes in prime order groups. Our framework is equipped with a compiler which is adaptively secure in prime order groups under the standard Decisional Linear Assumption (DLIN). Compared with prior encoding frameworks in prime order groups which require multiple group elements to interpret a tuple of an encoding in a real scheme, our framework has a distinctive feature which is that...
Verifiable Functional Encryption
Saikrishna Badrinarayanan, Vipul Goyal, Aayush Jain, Amit Sahai
Public-key cryptography
In light of security challenges that have emerged in a world with complex networks and cloud computing, the notion of functional encryption has recently emerged. In this work, we show that in several applications of functional encryption (even those cited in the earliest works on functional encryption), the formal notion of functional encryption is actually \emph{not} sufficient to guarantee security. This is essentially because the case of a malicious authority and/or encryptor is not...
Function-Revealing Encryption
Marc Joye, Alain Passelègue
Multi-input functional encryption is a paradigm that allows an authorized user to compute a certain function---and nothing more---over multiple plaintexts given only their encryption. The particular case of two-input functional encryption has very exciting applications, including comparing the relative order of two plaintexts from their encrypted form (order-revealing encryption).
While being extensively studied, multi-input functional encryption is not ready for a practical deployment,...
Groth-Sahai Proofs Revisited Again: A Bug in ``Optimized'' Randomization
Keita Xagawa
Cryptographic protocols
The Groth-Sahai proof system (EUROCRYPT 2008, SIAM Journal of Computing 41(5)) provides efficient non-interactive witness-indistinguishable (NIWI) and zero-knowledge (NIZK) proof systems for languages over bilinear groups and is a widely-used versatile tool to design efficient cryptographic schemes and protocols.
We revisit randomization of the prover in the GS proof system. We find an unnoticed bug in the ``optimized'' randomization in the symmetric bilinear setting with several...
Adaptive partitioning
Dennis Hofheinz
Public-key cryptography
We present a new strategy for partitioning proofs, and use it to obtain new tightly secure encryption schemes. Specifically, we provide the following two conceptual contributions:
- A new strategy for tight security reductions that leads to compact public keys and ciphertexts.
- A relaxed definition of non-interactive proof systems for non-linear (``OR-type'') languages. Our definition is strong enough to act as a central tool in our new strategy to obtain tight security, and is achievable...
Verifiable Random Functions from Standard Assumptions
Dennis Hofheinz, Tibor Jager
The question whether there exist verifiable random functions with exponential-sized input space and full adaptive security based on a non-interactive, constant-size assumption is a long-standing open problem. We construct the first verifiable random functions which simultaneously achieve all these properties.
Our construction can securely be instantiated in symmetric bilinear groups, based on any member of the (n-1)-linear assumption family with n >= 3. This includes, for example, the...
New Proof Techniques for DLIN-Based Adaptively Secure Attribute-Based Encryption
Katsuyuki Takashima
We propose adaptively secure attribute-based encryption (ABE) schemes for boolean formulas over large universe attributes from the decisional linear (DLIN) assumption, which allow attribute reuse in an available formula without the previously employed redundant multiple encoding technique. Thus our KP-(resp. CP-)ABE has non-redundant ciphertexts (resp. secret keys). For achieving the results, we develop a new encoding method for access policy matrix for ABE, by decoupling linear secret...
Verifiably Encrypted Signatures with Short Keys based on the Decisional Linear Problem and Obfuscation for Encrypted VES
Ryo Nishimaki, Keita Xagawa
Cryptographic protocols
Verifiably encrypted signatures (VES) are signatures encrypted by a public key of a trusted third party and we can verify their validity without decryption. This paper proposes a new VES scheme which is secure under the decisional linear (DLIN) assumption in the standard model. We also propose new obfuscators for encrypted signatures (ES) and encrypted VES (EVES) which are secure under the DLIN assumption.
All previous efficient VES schemes in the standard model are either secure under...
Tightly-Secure Authenticated Key Exchange
Christoph Bader, Dennis Hofheinz, Tibor Jager, Eike Kiltz, Yong Li
Cryptographic protocols
We construct the first Authenticated Key Exchange (AKE) protocol whose security does not degrade with an increasing number of users or sessions. We describe a three-message protocol and prove security in an enhanced version of the classical Bellare-Rogaway security model.
Our construction is modular, and can be instantiated efficiently from standard assumptions (such as the SXDH or DLIN assumptions in pairing-friendly groups). For instance, we provide an SXDH-based protocol whose...
Bilinear Entropy Expansion from the Decisional Linear Assumption
Lucas Kowalczyk, Allison Bishop Lewko
We develop a technique inspired by pseudorandom functions that allows us to increase the entropy available for proving the security of dual system encryption schemes under the Decisional Linear Assumption. We show an application of the tool to Attribute-Based Encryption by presenting a Key-Policy ABE scheme that is fully-secure under DLIN with short public parameters.
Concise Multi-Challenge CCA-Secure Encryption and Signatures with Almost Tight Security
Benoit Libert, Marc Joye, Moti Yung, Thomas Peters
Public-key cryptography
To gain strong confidence in the security of a public-key scheme, it
is most desirable for the security proof to feature a \emph{tight}
reduction between the adversary and the algorithm solving the
underlying hard problem. Recently, Chen and Wee (Crypto\,'13) described the first Identity-Based Encryption scheme with almost
tight security under a standard assumption. Here, ``almost tight''
means that the security reduction only loses a factor $O(\lambda)$
-- where $\lambda$ is the security...
Related-Key Secure Pseudorandom Functions: The Case of Additive Attacks
Benny Applebaum, Eyal Widder
Foundations
In a related-key attack (RKA) an adversary attempts to break a cryptographic primitive by invoking the primitive with several secret keys which satisfy some known relation. The task of constructing provably RKA secure PRFs (for non-trivial relations) under a standard assumption has turned to be challenging. Currently, the only known provably-secure construction is due to Bellare and Cash (Crypto 2010). This important feasibility result is restricted, however, to linear relations over...
How to Watermark Cryptographic Functions
Ryo Nishimaki
We introduce a notion of watermarking for cryptographic functions and propose a concrete scheme for watermarking cryptographic functions. Informally speaking, a digital watermarking scheme for cryptographic
functions embeds information, called a \textit{mark}, into functions such as one-way functions and decryption functions of public-key encryption. There are two basic requirements for watermarking schemes.
(1) A mark-embedded function must be functionally equivalent to the original...
Adaptively Secure Functional Encryption for Finite Languages from DLIN Assumption
Tapas Pandit, Rana Barua
Public-key cryptography
In this paper, we present Functional Encryption (FE) schemes for finite languages from standard static assumption, viz., \textit{Decisional Linear} (DLIN) assumption. These finite languages are described by deterministic finite automata. Our first scheme is ciphertext-policy functional encryption (CP-FE), where a key $\sk_w$ is labeled with a string $w$ over a fixed alphabet $\Sigma$ and a ciphertext $\cipher_\amn$ is associated with a deterministic finite Automaton (DFA) $\amn$ over the...
Expressive Attribute-Based Encryption with Constant-Size Ciphertexts from the Decisional Linear Assumption
Katsuyuki Takashima
Public-key cryptography
We propose a key-policy attribute-based encryption (KP-ABE) scheme with constant-size ciphertexts, whose semi-adaptive security is proven under the decisional linear (DLIN) assumption in the standard model. The access structure is expressive, that is given by non-monotone span programs. It also has fast decryption, i.e., a decryption includes only a constant number of pairing operations. As an application of our KP-ABE construction, we also propose a fully secure attribute-based signatures...
Fully, (Almost) Tightly Secure IBE from Standard Assumptions
Jie Chen, Hoeteck Wee
Public-key cryptography
We present the first fully secure Identity-Based Encryption scheme
(IBE) from the standard assumptions where the security loss depends
only on the security parameter and is independent of the number of
secret key queries. This partially answers an open problem posed by
Waters (Eurocrypt 2005). Our construction combines Waters' dual
system encryption methodology (Crypto 2009) with the Naor-Reingold
pseudo-random function (J. ACM, 2004) in a novel way. The security
of our scheme relies on the...
Functional Encryption and Property Preserving Encryption: New Definitions and Positive Results
Shashank Agrawal, Shweta Agrawal, Saikrishna Badrinarayanan, Abishek Kumarasubramanian, Manoj Prabhakaran, Amit Sahai
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. In addition, we improve efficiency/ underlying assumptions/ security achieved by existing inner product Functional Encryption and Property Preserving Encryption schemes, in both the private and public key setting. Our...
Fully-Anonymous Functional Proxy-Re-Encryption
Yutaka Kawai, Katsuyuki Takashima
Public-key cryptography
In this paper, we introduce a general notion of functional proxy-re-encryption (F-PRE), where a wide class of functional encryption (FE) is combined with proxy-re-encryption (PRE) mechanism. The PRE encryption system should reveal {\em minimal} information to a proxy, in particular, hiding parameters of re-encryption keys and of original ciphertexts which he manipulate is highly desirable. We first formulate such a {\em fully-anonymous} security notion of F-PRE including usual payload-hiding...
Function-Private Identity-Based Encryption: Hiding the Function in Functional Encryption
Dan Boneh, Ananth Raghunathan, Gil Segev
Public-key cryptography
We put forward a new notion, function privacy, in identity-based encryption and, more generally, in functional encryption. Intuitively, our notion asks that decryption keys reveal essentially no information on their corresponding identities, beyond the absolute minimum necessary. This is motivated by the need for providing predicate privacy in public-key searchable encryption. Formalizing such a notion, however, is not straightforward as given a decryption key it is always possible to learn...
On the (Im)possibility of Projecting Property in Prime-Order Setting
Jae Hong Seo
Projecting bilinear pairings have frequently been used for designing cryptosystems since they were first derived from composite order bilinear groups. There have been only a few studies on the (im)possibility of projecting bilinear pairings. Groth and Sahai (EUROCRYPT 2008) showed that projecting bilinear pairings can be achieved in a prime-order group setting. They constructed both projecting asymmetric bilinear pairings and projecting symmetric bilinear pairings, where a bilinear pairing...
Improving the Message-ciphertext Rate of Lewko's Fully Secure IBE Scheme
Dingding Jia, Bao Liand Yamin Liu, Qixiang Mei
Public-key cryptography
In Eurocrypt 2012, Lewko presented a fully secure IBE scheme in the
prime order setting based on the decisional linear assumption. We note that
some random factor involved in the ciphertext can further be used to hide yet another message
, and get a new fully secure IBE scheme with better message-ciphertext rate.
Similar to Lewko's
scheme, we use dual pairing vector space in prime order bilinear
groups to simulate the canceling and parameter hiding properties of
composite order settings. The...
Shorter Quasi-Adaptive NIZK Proofs for Linear Subspaces
Charanjit S. Jutla, Arnab Roy
Public-key cryptography
We define a novel notion of quasi-adaptive non-interactive zero knowledge (NIZK) proofs for probability distributions on parametrized languages. It is quasi-adaptive in the sense that the common reference string (CRS) generator can generate the CRS depending on the language parameters. However, the simulation is required to be uniform, i.e., a single efficient simulator should work for the whole class of parametrized languages. For distributions on languages that are linear subspaces of...
Efficient, Adaptively Secure, and Composable Oblivious Transfer with a Single, Global CRS
Seung Geol Choi, Jonathan Katz, Hoeteck Wee, Hong-Sheng Zhou
Cryptographic protocols
We present a general framework for efficient, universally composable oblivious transfer (OT)
protocols in which a single, global, common reference string (CRS) can be used for multiple
invocations of oblivious transfer by arbitrary pairs of parties. In addition:
- Our framework is round-efficient. E.g., under the DLIN or SXDH assumptions we achieve
round-optimal protocols with static security, or 3-round protocols with adaptive security
(assuming erasure).
- Our resulting protocols are...
Fully Secure Unbounded Inner-Product and Attribute-Based Encryption
Tatsuaki Okamoto, Katsuyuki Takashima
Public-key cryptography
In this paper, we present the first inner-product encryption (IPE) schemes that are unbounded in the sense that the public parameters do not impose additional limitations on the predicates and attributes used for encryption and decryption keys. All previous IPE schemes were bounded, or have a bound on the size of predicates and
attributes given public parameters fixed at setup. The proposed unbounded IPE schemes are fully (adaptively) secure and fully attribute-hiding in the standard model...
New Leakage Resilient CCA-Secure Public Key Encryption
Kaoru Kurosawa, Ryo Nojima, Le Trieu Phong
Public-key cryptography
This paper shows a generic method of constructing CCA-secure public key encryption schemes with leakage resilience on the secret key. It is based on a new kind of universal$_2$ hash proof system which accepts an auxiliary parameter. Specifically, two schemes are presented, basing on the DCR assumption and DLIN assumption respectively.
2012/381
Last updated: 2013-07-22
A Strongly Secure Authenticated Key Exchange Protocol from Bilinear Groups without Random Oracles
Zheng Yang
Since the introducing of extended Canetti-Krawczyk~(eCK) security model for two party key exchange, many protocols have been proposed to provide eCK security. However, most of those protocols are provably secure in the random oracle model or rely on special design technique well-known as the NAXOS trick. In contrast to previous schemes, we present an eCK secure protocol in the standard model, without NAXOS trick and without knowledge of secret key (KOSK) assumption for public key...
Shorter IBE and Signatures via Asymmetric Pairings
Jie Chen, Hoon Wei Lim, San Ling, Huaxiong Wang, Hoeteck Wee
Public-key cryptography
We present efficient Identity-Based Encryption (IBE) and signature
schemes under the Symmetric External Diffie-Hellman (SXDH)
assumption in bilinear groups; our IBE scheme also achieves
anonymity. In both the IBE and the signature schemes, all parameters
have constant numbers of group elements, and are shorter than those
of previous constructions based on Decisional Linear (DLIN)
assumption. Our constructions use both dual system encryption
(Waters, Crypto '09) and dual pairing vector spaces...
Malleable Proof Systems and Applications
Melissa Chase, Markulf Kohlweiss, Anna Lysyanskaya, Sarah Meiklejohn
Foundations
Malleability for cryptography is not necessarily an opportunity for attack, but in many cases a potentially useful feature that can be exploited. In this work, we examine notions of malleability for non-interactive zero-knowledge (NIZK) proofs. We start by defining a malleable proof system, and then consider ways to meaningfully control the malleability of the proof system, as in many settings we would like to guarantee that only certain types of transformations can be performed. We also...
Decentralized Attribute-Based Signatures
Tatsuaki Okamoto, Katsuyuki Takashima
Public-key cryptography
In this paper, we present the first decentralized multi-authority
attribute-based signature (DMA-ABS) scheme, in which no central authority and no trusted setup are required. The proposed DMA-ABS scheme for general (non-monotone) predicates is fully secure(adaptive-predicate unforgeable and perfect private) under a standard assumption, the decisional linear (DLIN) assumption,
in the random oracle model. Our DMA-ABS scheme is comparably as efficient as the most efficient ABS scheme. As a...
Efficient Attribute-Based Signatures for Non-Monotone Predicates in the Standard Model
Tatsuaki Okamoto, Katsuyuki Takashima
Public-key cryptography
This paper presents a fully secure (adaptive-predicate unforgeable and private) attribute-based signature (ABS) scheme in the standard model. The security of the proposed ABS scheme is proven under standard assumptions, the decisional linear (DLIN) assumption
and the existence of collision resistant (CR) hash functions. The admissible predicates of the proposed ABS scheme are more general than those of the existing ABS schemes, i.e., the proposed ABS scheme
is the first to support general...
Fully Secure (Doubly-)Spatial Encryption under Simpler Assumptions
Cheng Chen, Zhenfeng Zhang, Dengguo Feng
Public-key cryptography
Spatial encryption was first proposed by Boneh and Hamburg in 2008. It is one implementation of the generalized identity-based encryption schemes and many systems with a variety of properties can be derived from it. Recently, Hamburg improved the notion by presenting a variant called doubly-spatial encryption. The doubly spatial encryption is more powerful and expressive. More useful cryptography systems can be builded from it, such as attribute-based encryption, etc. However, most presented...
Achieving Short Ciphertexts or Short Secret-Keys for Adaptively Secure General Inner-Product Encryption
Tatsuaki Okamoto, Katsuyuki Takashima
Public-key cryptography
In this paper, we present two non-zero inner-product encryption (NIPE) schemes that are adaptively secure under a standard assumption, the decisional linear (DLIN) assumption, in the standard model. One of the proposed NIPE schemes features constant-size ciphertexts and the other features constant-size secret-keys. Our NIPE schemes imply an identity-based revocation (IBR) system
with constant-size ciphertexts or constant-size secret-keys that is adaptively secure under the DLIN assumption....
Maximum Leakage Resilient IBE and IPE
Kaoru Kurosawa, Le Trieu Phong
Public-key cryptography
In this paper, we show the first identity-based encryption (IBE) scheme, and inner product encryption (IPE) scheme, both of which achieve the maximum possible leakage rate $1-o(1)$ in the standard model under a static assumption. Specifically, under the DLIN assumption, even if $1-o(1)$ fraction of each private key is arbitrarily leaked, the IBE scheme is fully secure and the IPE scheme is selectively secure. (To our knowledge, no {\it leakage resilient} IPE scheme has been known so far.)
A Domain Transformation for Structure-Preserving Signatures on Group Elements
Melissa Chase, Markulf Kohlweiss
Public-key cryptography
We present a generic transformation that allows us to use a large class of pairing-based signatures to construct schemes for signing group elements in a structure preserving way.
As a result of our transformation we obtain a new efficient signature scheme for signing a vector of group elements that is based only on the well established decisional linear assumption (DLIN). Moreover, the public keys and signatures of our scheme consist of group elements only, and a signature is verified by...
Fully Secure Functional Encryption with General Relations from the Decisional Linear Assumption
Tatsuaki Okamoto, Katsuyuki Takashima
Public-key cryptography
This paper presents a fully secure functional encryption scheme for a wide class of relations, that are specified by non-monotone access structures combined with inner-product relations. The security is proven under a standard assumption, the decisional linear (DLIN) assumption, in the standard model. The proposed functional encryption
scheme covers, as special cases, (1) key-policy and ciphertext-policy attribute-based encryption with non-monotone access structures, and (2) (hierarchical)...
Pseudorandom Functions and Permutations Provably Secure Against Related-Key Attacks
Mihir Bellare, David Cash
Secret-key cryptography
This paper fills an important foundational gap with the first proofs, under standard assumptions and in the standard model, of the existence of pseudorandom functions (PRFs) and pseudorandom permutations (PRPs) resisting rich and relevant forms of related-key attacks (RKA). An RKA allows the adversary to query the function not only under the target key but under other keys derived from it in adversary-specified ways. Based on the Naor-Reingold PRF we obtain an RKA-PRF whose keyspace is a...
We present the first Key Policy Attribute-Based Encryption (KP-ABE) scheme employing isogeny-based cryptography through class group actions, specifically utilizing the Csi-FiSh instantiation and pairing groups. We introduce a new assumption, denoted Isog-DLin, which combines the isogeny and DLin assumptions. We propose the following constructions: a small universe KP-ABE and a large universe KP-ABE under the Isog-DBDH assumption, and a small universe KP-ABE under the Isog-DLin assumption. In...
Attribute-based signatures (ABS) allow users to simultaneously sign messages and prove their possession of some attributes while hiding the attributes and revealing only the fact that they satisfy a public policy. In this paper, we propose a generic construction of ABS for circuits of unbounded depth and size, with optimal parameter size—meaning the lengths of public parameters, keys, and signatures are all constant. Our construction can be instantiated from various standard assumptions,...
Attribute-Based Encryption (ABE) provides fine-grained access control to encrypted data and finds applications in various domains. The practicality of ABE schemes hinges on the balance between security and efficiency. The state-of-the-art adaptive secure ABE scheme, proven to be adaptively secure under standard assumptions (FAME, CCS'17), is less efficient compared to the fastest one (FABEO, CCS'22) which is only proven secure under the Generic Group Model (GGM). These traditional ABE...
In this work, we study what minimal sets of assumptions suffice for constructing indistinguishability obfuscation ($i\mathcal{O}$). We prove: {\bf Theorem}(Informal): Assume sub-exponential security of the following assumptions: - the Learning Parity with Noise ($\mathsf{LPN}$) assumption over general prime fields $\mathbb{F}_p$ with polynomially many $\mathsf{LPN}$ samples and error rate $1/k^\delta$, where $k$ is the dimension of the $\mathsf{LPN}$ secret, and $\delta>0$ is any...
Decentralized multi-authority attribute-based encryption (𝖬𝖠-𝖠𝖡𝖤) is a strengthening of standard ciphertext-policy attribute-based encryption so that there is no trusted central authority: any party can become an authority and there is no requirement for any global coordination other than the creation of an initial set of common reference parameters. Essentially, any party can act as an authority for some attribute by creating a public key of its own and issuing private keys to different...
This paper presents the first functional encryption schemes for quadratic functions (or degree-2 polynomials) achieving simulation-based security in the semi-adaptive model with constant-size secret key. The unique prior construction with the same security guarantee by Gay [PKC 20] has secret keys of size linear in the message size. They also enjoy shorter ciphertexts: - our first scheme is based on bilateral DLIN (decisional linear) assumption as Gay's scheme and the ciphertext is 15%...
Dwork and Naor (FOCS '00) defined ZAPs as 2-message witness-indistinguishable proofs that are public-coin. We relax this to ``ZAPs with private randomness'' (ZAPRs), where the verifier can use private coins to sample the first message (independently of the statement being proved), but the proof must remain publicly verifiable given only the protocol transcript. In particular, ZAPRs are reusable, meaning that the first message can be reused for multiple proofs without compromising...
A non-interactive zero-knowledge (NIZK) protocol enables a prover to convince a verifier of the truth of a statement without leaking any other information by sending a single message. The main focus of this work is on exploring short pairing-based NIZKs for all NP languages based on standard assumptions. In this regime, the seminal work of Groth, Ostrovsky, and Sahai (J.ACM'12) (GOS-NIZK) is still considered to be the state-of-the-art. Although fairly efficient, one drawback of GOS-NIZK is...
In the standard setting of functional encryption (FE), we assume both the Central Authority (CA) and the encryptors to run their respective algorithms faithfully. Badrinarayanan et al [ASIACRYPT 2016] put forth the concept of verifiable FE, which essentially guarantees that dishonest encryptors and authorities, even when colluding together, are not able to generate ciphertexts and tokens that give inconsistent results. They also provide a compiler turning any perfectly correct FE into a...
We revisit the well-studied problem of extracting nearly uniform randomness from an arbitrary source of sufficient min-entropy. Strong seeded extractors solve this problem by relying on a public random seed, which is unknown to the source. Here, we consider a setting where the seed is reused over time and the source may depend on prior calls to the extractor with the same seed. Can we still extract nearly uniform randomness? In more detail, we assume the seed is chosen randomly, but the...
Quasi-adaptive non-interactive zero-knowledge proof (QA-NIZK) systems and structure-preserving signature (SPS) schemes are two powerful tools for constructing practical pairing-based cryptographic schemes. Their efficiency directly affects the efficiency of the derived ad- vanced protocols. We construct more efficient QA-NIZK and SPS schemes with tight security reductions. Our QA-NIZK scheme is the first one that achieves both tight simulation soundness and constant proof size (in terms of...
In this work, we define and construct fully homomorphic non-interactive zero knowledge (FH-NIZK) and non-interactive witness-indistinguishable (FH-NIWI) proof systems. We focus on the NP complete language $L$, where, for a boolean circuit $C$ and a bit $b$, the pair $(C,b) \in L$ if there exists an input $w$ such that $C(w)=b$. For this language, we call a non-interactive proof system 'fully homomorphic' if, given instances $(C_i,b_i) \in L$ along with their proofs $\Pi_i$, for $i \in...
Waters [Crypto, 2012] provided the first attribute based encryption scheme ABE for Deterministic Finite Automata (DFA) from a parametrized or ``q-type'' assumption over bilinear maps. Obtaining a construction from static assumptions has been elusive, despite much progress in the area of ABE. In this work, we construct the first attribute based encryption scheme for DFA from static assumptions on pairings, namely, the DLIN assumption. Our scheme supports unbounded length inputs, unbounded...
This paper presents the first attribute-based signature (ABS) scheme in which the correspondence between signers and signatures is captured in an arithmetic model of computation. Specifically, we design a fully secure, i.e., adaptively unforgeable and perfectly signer-private ABS scheme for signing policies realizable by arithmetic branching programs (ABP), which are a quite expressive model of arithmetic computations. On a more positive note, the proposed scheme places no bound on the size...
This paper demonstrates how to achieve simulation-based strong attribute hiding against adaptive adversaries for predicate encryption (PE) schemes supporting expressive predicate families under standard computational assumptions in bilinear groups. Our main result is a simulation-based adaptively strongly partially-hiding PE (PHPE) scheme for predicates computing arithmetic branching programs (ABP) on public attributes, followed by an inner-product predicate on private attributes. This...
We construct the first (almost) tightly-secure unbounded-simulation-sound quasi-adaptive non-interactive zero-knowledge arguments (USS-QA-NIZK) for linear-subspace languages with compact (number of group elements independent of the security parameter) common reference string (CRS) and compact proofs under standard assumptions in bilinear-pairings groups. Specifically, our construction has $ O(\log Q) $ reduction to the SXDH, DLIN and matrix-DDH assumptions, where $ Q $ is the number of...
In this work, we propose two IPE schemes achieving both adaptive security and full attribute-hiding in the prime-order bilinear group, which improve upon the unique existing result satisfying both features from Okamoto and Takashima [Eurocrypt '12] in terms of efficiency. - Our first IPE scheme is based on the standard $k$-Lin assumption and has shorter master public key and shorter secret keys than Okamoto and Takashima's IPE under weaker DLIN=$2$-lin assumption. - Our second IPE scheme...
We present function private public-key predicate encryption schemes from standard cryptographic assumptions, that achieve new lower bounds on the min-entropy of underlying predicate distributions. Existing function private predicate encryption constructions in the public-key setting can be divided into two broad categories. The first category of constructions are based on standard assumptions, but impose highly stringent requirements on the min-entropy of predicate distributions, thereby...
We present a new class of public-key predicate encryption schemes that are provably function private in the standard model under well-known cryptographic assumptions, and assume predicate distributions satisfying realistic min-entropy requirements. More concretely, we present public-key constructions for identity-based encryption (IBE) and inner-product encryption (IPE) that are computationally function private in the standard model under a family of weaker variants of the DLIN assumption....
In this paper, we present new adaptively secure identity-based encryption (IBE) schemes. One of the distinguishing property of the schemes is that it achieves shorter public parameters than previous schemes. Both of our schemes follow the general framework presented in the recent IBE scheme of Yamada (Eurocrypt 2016), employed with novel techniques tailored to meet the underlying algebraic structure to overcome the difficulties arising in our specific setting. Specifically, we obtain the...
We introduce a tag based encoding, a new generic framework for modular design of Predicate Encryption (PE) schemes in prime order groups. Our framework is equipped with a compiler which is adaptively secure in prime order groups under the standard Decisional Linear Assumption (DLIN). Compared with prior encoding frameworks in prime order groups which require multiple group elements to interpret a tuple of an encoding in a real scheme, our framework has a distinctive feature which is that...
In light of security challenges that have emerged in a world with complex networks and cloud computing, the notion of functional encryption has recently emerged. In this work, we show that in several applications of functional encryption (even those cited in the earliest works on functional encryption), the formal notion of functional encryption is actually \emph{not} sufficient to guarantee security. This is essentially because the case of a malicious authority and/or encryptor is not...
Multi-input functional encryption is a paradigm that allows an authorized user to compute a certain function---and nothing more---over multiple plaintexts given only their encryption. The particular case of two-input functional encryption has very exciting applications, including comparing the relative order of two plaintexts from their encrypted form (order-revealing encryption). While being extensively studied, multi-input functional encryption is not ready for a practical deployment,...
The Groth-Sahai proof system (EUROCRYPT 2008, SIAM Journal of Computing 41(5)) provides efficient non-interactive witness-indistinguishable (NIWI) and zero-knowledge (NIZK) proof systems for languages over bilinear groups and is a widely-used versatile tool to design efficient cryptographic schemes and protocols. We revisit randomization of the prover in the GS proof system. We find an unnoticed bug in the ``optimized'' randomization in the symmetric bilinear setting with several...
We present a new strategy for partitioning proofs, and use it to obtain new tightly secure encryption schemes. Specifically, we provide the following two conceptual contributions: - A new strategy for tight security reductions that leads to compact public keys and ciphertexts. - A relaxed definition of non-interactive proof systems for non-linear (``OR-type'') languages. Our definition is strong enough to act as a central tool in our new strategy to obtain tight security, and is achievable...
The question whether there exist verifiable random functions with exponential-sized input space and full adaptive security based on a non-interactive, constant-size assumption is a long-standing open problem. We construct the first verifiable random functions which simultaneously achieve all these properties. Our construction can securely be instantiated in symmetric bilinear groups, based on any member of the (n-1)-linear assumption family with n >= 3. This includes, for example, the...
We propose adaptively secure attribute-based encryption (ABE) schemes for boolean formulas over large universe attributes from the decisional linear (DLIN) assumption, which allow attribute reuse in an available formula without the previously employed redundant multiple encoding technique. Thus our KP-(resp. CP-)ABE has non-redundant ciphertexts (resp. secret keys). For achieving the results, we develop a new encoding method for access policy matrix for ABE, by decoupling linear secret...
Verifiably encrypted signatures (VES) are signatures encrypted by a public key of a trusted third party and we can verify their validity without decryption. This paper proposes a new VES scheme which is secure under the decisional linear (DLIN) assumption in the standard model. We also propose new obfuscators for encrypted signatures (ES) and encrypted VES (EVES) which are secure under the DLIN assumption. All previous efficient VES schemes in the standard model are either secure under...
We construct the first Authenticated Key Exchange (AKE) protocol whose security does not degrade with an increasing number of users or sessions. We describe a three-message protocol and prove security in an enhanced version of the classical Bellare-Rogaway security model. Our construction is modular, and can be instantiated efficiently from standard assumptions (such as the SXDH or DLIN assumptions in pairing-friendly groups). For instance, we provide an SXDH-based protocol whose...
We develop a technique inspired by pseudorandom functions that allows us to increase the entropy available for proving the security of dual system encryption schemes under the Decisional Linear Assumption. We show an application of the tool to Attribute-Based Encryption by presenting a Key-Policy ABE scheme that is fully-secure under DLIN with short public parameters.
To gain strong confidence in the security of a public-key scheme, it is most desirable for the security proof to feature a \emph{tight} reduction between the adversary and the algorithm solving the underlying hard problem. Recently, Chen and Wee (Crypto\,'13) described the first Identity-Based Encryption scheme with almost tight security under a standard assumption. Here, ``almost tight'' means that the security reduction only loses a factor $O(\lambda)$ -- where $\lambda$ is the security...
In a related-key attack (RKA) an adversary attempts to break a cryptographic primitive by invoking the primitive with several secret keys which satisfy some known relation. The task of constructing provably RKA secure PRFs (for non-trivial relations) under a standard assumption has turned to be challenging. Currently, the only known provably-secure construction is due to Bellare and Cash (Crypto 2010). This important feasibility result is restricted, however, to linear relations over...
We introduce a notion of watermarking for cryptographic functions and propose a concrete scheme for watermarking cryptographic functions. Informally speaking, a digital watermarking scheme for cryptographic functions embeds information, called a \textit{mark}, into functions such as one-way functions and decryption functions of public-key encryption. There are two basic requirements for watermarking schemes. (1) A mark-embedded function must be functionally equivalent to the original...
In this paper, we present Functional Encryption (FE) schemes for finite languages from standard static assumption, viz., \textit{Decisional Linear} (DLIN) assumption. These finite languages are described by deterministic finite automata. Our first scheme is ciphertext-policy functional encryption (CP-FE), where a key $\sk_w$ is labeled with a string $w$ over a fixed alphabet $\Sigma$ and a ciphertext $\cipher_\amn$ is associated with a deterministic finite Automaton (DFA) $\amn$ over the...
We propose a key-policy attribute-based encryption (KP-ABE) scheme with constant-size ciphertexts, whose semi-adaptive security is proven under the decisional linear (DLIN) assumption in the standard model. The access structure is expressive, that is given by non-monotone span programs. It also has fast decryption, i.e., a decryption includes only a constant number of pairing operations. As an application of our KP-ABE construction, we also propose a fully secure attribute-based signatures...
We present the first fully secure Identity-Based Encryption scheme (IBE) from the standard assumptions where the security loss depends only on the security parameter and is independent of the number of secret key queries. This partially answers an open problem posed by Waters (Eurocrypt 2005). Our construction combines Waters' dual system encryption methodology (Crypto 2009) with the Naor-Reingold pseudo-random function (J. ACM, 2004) in a novel way. The security of our scheme relies on the...
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. In addition, we improve efficiency/ underlying assumptions/ security achieved by existing inner product Functional Encryption and Property Preserving Encryption schemes, in both the private and public key setting. Our...
In this paper, we introduce a general notion of functional proxy-re-encryption (F-PRE), where a wide class of functional encryption (FE) is combined with proxy-re-encryption (PRE) mechanism. The PRE encryption system should reveal {\em minimal} information to a proxy, in particular, hiding parameters of re-encryption keys and of original ciphertexts which he manipulate is highly desirable. We first formulate such a {\em fully-anonymous} security notion of F-PRE including usual payload-hiding...
We put forward a new notion, function privacy, in identity-based encryption and, more generally, in functional encryption. Intuitively, our notion asks that decryption keys reveal essentially no information on their corresponding identities, beyond the absolute minimum necessary. This is motivated by the need for providing predicate privacy in public-key searchable encryption. Formalizing such a notion, however, is not straightforward as given a decryption key it is always possible to learn...
Projecting bilinear pairings have frequently been used for designing cryptosystems since they were first derived from composite order bilinear groups. There have been only a few studies on the (im)possibility of projecting bilinear pairings. Groth and Sahai (EUROCRYPT 2008) showed that projecting bilinear pairings can be achieved in a prime-order group setting. They constructed both projecting asymmetric bilinear pairings and projecting symmetric bilinear pairings, where a bilinear pairing...
In Eurocrypt 2012, Lewko presented a fully secure IBE scheme in the prime order setting based on the decisional linear assumption. We note that some random factor involved in the ciphertext can further be used to hide yet another message , and get a new fully secure IBE scheme with better message-ciphertext rate. Similar to Lewko's scheme, we use dual pairing vector space in prime order bilinear groups to simulate the canceling and parameter hiding properties of composite order settings. The...
We define a novel notion of quasi-adaptive non-interactive zero knowledge (NIZK) proofs for probability distributions on parametrized languages. It is quasi-adaptive in the sense that the common reference string (CRS) generator can generate the CRS depending on the language parameters. However, the simulation is required to be uniform, i.e., a single efficient simulator should work for the whole class of parametrized languages. For distributions on languages that are linear subspaces of...
We present a general framework for efficient, universally composable oblivious transfer (OT) protocols in which a single, global, common reference string (CRS) can be used for multiple invocations of oblivious transfer by arbitrary pairs of parties. In addition: - Our framework is round-efficient. E.g., under the DLIN or SXDH assumptions we achieve round-optimal protocols with static security, or 3-round protocols with adaptive security (assuming erasure). - Our resulting protocols are...
In this paper, we present the first inner-product encryption (IPE) schemes that are unbounded in the sense that the public parameters do not impose additional limitations on the predicates and attributes used for encryption and decryption keys. All previous IPE schemes were bounded, or have a bound on the size of predicates and attributes given public parameters fixed at setup. The proposed unbounded IPE schemes are fully (adaptively) secure and fully attribute-hiding in the standard model...
This paper shows a generic method of constructing CCA-secure public key encryption schemes with leakage resilience on the secret key. It is based on a new kind of universal$_2$ hash proof system which accepts an auxiliary parameter. Specifically, two schemes are presented, basing on the DCR assumption and DLIN assumption respectively.
Since the introducing of extended Canetti-Krawczyk~(eCK) security model for two party key exchange, many protocols have been proposed to provide eCK security. However, most of those protocols are provably secure in the random oracle model or rely on special design technique well-known as the NAXOS trick. In contrast to previous schemes, we present an eCK secure protocol in the standard model, without NAXOS trick and without knowledge of secret key (KOSK) assumption for public key...
We present efficient Identity-Based Encryption (IBE) and signature schemes under the Symmetric External Diffie-Hellman (SXDH) assumption in bilinear groups; our IBE scheme also achieves anonymity. In both the IBE and the signature schemes, all parameters have constant numbers of group elements, and are shorter than those of previous constructions based on Decisional Linear (DLIN) assumption. Our constructions use both dual system encryption (Waters, Crypto '09) and dual pairing vector spaces...
Malleability for cryptography is not necessarily an opportunity for attack, but in many cases a potentially useful feature that can be exploited. In this work, we examine notions of malleability for non-interactive zero-knowledge (NIZK) proofs. We start by defining a malleable proof system, and then consider ways to meaningfully control the malleability of the proof system, as in many settings we would like to guarantee that only certain types of transformations can be performed. We also...
In this paper, we present the first decentralized multi-authority attribute-based signature (DMA-ABS) scheme, in which no central authority and no trusted setup are required. The proposed DMA-ABS scheme for general (non-monotone) predicates is fully secure(adaptive-predicate unforgeable and perfect private) under a standard assumption, the decisional linear (DLIN) assumption, in the random oracle model. Our DMA-ABS scheme is comparably as efficient as the most efficient ABS scheme. As a...
This paper presents a fully secure (adaptive-predicate unforgeable and private) attribute-based signature (ABS) scheme in the standard model. The security of the proposed ABS scheme is proven under standard assumptions, the decisional linear (DLIN) assumption and the existence of collision resistant (CR) hash functions. The admissible predicates of the proposed ABS scheme are more general than those of the existing ABS schemes, i.e., the proposed ABS scheme is the first to support general...
Spatial encryption was first proposed by Boneh and Hamburg in 2008. It is one implementation of the generalized identity-based encryption schemes and many systems with a variety of properties can be derived from it. Recently, Hamburg improved the notion by presenting a variant called doubly-spatial encryption. The doubly spatial encryption is more powerful and expressive. More useful cryptography systems can be builded from it, such as attribute-based encryption, etc. However, most presented...
In this paper, we present two non-zero inner-product encryption (NIPE) schemes that are adaptively secure under a standard assumption, the decisional linear (DLIN) assumption, in the standard model. One of the proposed NIPE schemes features constant-size ciphertexts and the other features constant-size secret-keys. Our NIPE schemes imply an identity-based revocation (IBR) system with constant-size ciphertexts or constant-size secret-keys that is adaptively secure under the DLIN assumption....
In this paper, we show the first identity-based encryption (IBE) scheme, and inner product encryption (IPE) scheme, both of which achieve the maximum possible leakage rate $1-o(1)$ in the standard model under a static assumption. Specifically, under the DLIN assumption, even if $1-o(1)$ fraction of each private key is arbitrarily leaked, the IBE scheme is fully secure and the IPE scheme is selectively secure. (To our knowledge, no {\it leakage resilient} IPE scheme has been known so far.)
We present a generic transformation that allows us to use a large class of pairing-based signatures to construct schemes for signing group elements in a structure preserving way. As a result of our transformation we obtain a new efficient signature scheme for signing a vector of group elements that is based only on the well established decisional linear assumption (DLIN). Moreover, the public keys and signatures of our scheme consist of group elements only, and a signature is verified by...
This paper presents a fully secure functional encryption scheme for a wide class of relations, that are specified by non-monotone access structures combined with inner-product relations. The security is proven under a standard assumption, the decisional linear (DLIN) assumption, in the standard model. The proposed functional encryption scheme covers, as special cases, (1) key-policy and ciphertext-policy attribute-based encryption with non-monotone access structures, and (2) (hierarchical)...
This paper fills an important foundational gap with the first proofs, under standard assumptions and in the standard model, of the existence of pseudorandom functions (PRFs) and pseudorandom permutations (PRPs) resisting rich and relevant forms of related-key attacks (RKA). An RKA allows the adversary to query the function not only under the target key but under other keys derived from it in adversary-specified ways. Based on the Naor-Reingold PRF we obtain an RKA-PRF whose keyspace is a...