1,720,979 research outputs found
Towards a provably secure DoS-Resilient key exchange protocol with perfect forward secrecy
No full textJust Fast Keying (JFK) is a simple, efficient and secure key exchange protocol proposed by Aiello et al. (ACM TISSEC, 2004). JFK is well known for its novel design features, notably its resistance to denial-of-service (DoS) attacks. Using Meadows’ cost-based framework, we identify a new DoS vulnerability in JFK. The JFK protocol is claimed secure in the Canetti-Krawczyk model under the Decisional Diffie-Hellman (DDH) assumption. We show that security of the JFK protocol, when reusing ephemeral Diffie-Hellman keys, appears to require the Gap Diffie-Hellman (GDH) assumption in the random oracle model. We propose a new variant of JFK that avoids the identified DoS vulnerability and provides perfect forward secrecy even under the DDH assumption, achieving the full security promised by the JFK protocol
Signcryption in a Quantum World
No full textWith recent advancements and research on quantum computers, it is conjectured that in the foreseeable
future, sufficiently large quantum computers will be built to break essentially all public key
cryptosystems currently in use. As a response, quantum-safe cryptography has recently garnered significant
attention. The aim of quantum-safe cryptography is to design cryptosystems that are secure against
both classical and quantum computers. This involves identifying computational problems that are believed
to be secure against quantum adversaries and building cryptosystems based on such problems.
A related problem of interest is arguing security of quantum-safe cryptosystems within the paradigm
of provable security. Quantum security models for basic primitives like encryption and signature are
gradually evolving and the security of different cryptosystems are being investigated in these models.
Signcryption is a public key primitive that ensures both confidentiality and authenticity of data.
Signcryption security can be modeled in different ways depending on whether the adversary can corrupt
an insider, i.e., the sender or receiver, or not. The aim of this work is a comprehensive treatment of
signcryption against quantum adversaries that are allowed to make oracle queries on quantum superposition
of classical input values. We formulate suitable quantum security definitions for confidentiality and
authenticity of signcryption both in insider and outsider models. We investigate the quantum security of
generic constructions of signcryption schemes based on three paradigms, viz., encrypt-then-sign (EtS),
sign-then-encrypt (StE) and commit-then-encrypt-and-sign (CtE&S). We show that the quantum analogues
of the classical results hold in the insider model with an exception in the StE paradigm. However,
in outsider model we need to consider an intermediate setting in which the adversary is given quantum
access to unsigncryption oracle but classical access to signcryption oracle. In two-user outsider model,
as in the classical setting, we show that post-quantum CPA security of the base encryption scheme is
amplified in the EtS paradigm if the base signature scheme satisfies a stronger notion of security. We
prove an analogous result in the StE paradigm. Interestingly, in the multi-user setting, our results
strengthen the known classical results.
Our results for the EtS and StE paradigms in the two-user outsider model also extend to the setting
of authenticated encryption. We briefly discuss the difficulties in analyzing the full quantum security
of signcryption in outsider model. Finally, we briefly discuss about some existing quantum secure
encryption and signature proposals which can be used to instantiate signcryption schemes based on the
above paradigms
Fully Resilient Non-Interactive ID-Based Hierarchical Key Agreement
No full textNon-Interactive Key Agreement (NIKA) is a cryptographic primitive which allows two parties to agree on a shared secret key without any interaction. Identity-based Non-Interactive Key Agreement (ID-NIKA) allows each party to compute shared secret key using its own secret key and the peer’s identity. ID-NIKA can be used to establish shared secret keys in ad-hoc networks using minimal battery power and communication.
Mobile Ad-hoc NETwork (MANET) is a network of mobile and moderately resource constrained devices communicating through a wireless medium. Examples of standard MANET devices are laptops, cellphones etc. Due to the inherent characteristics like mobility, dynamic topology and lack of centralized infrastructure, MANETs face some serious security issues. We are particularly interested about ID-NIKA in MANETs. This is of crucial interest for secure communication between two nodes in MANETs.
In 2008, Gennaro et al. introduced a scheme called Hybrid Hierarchical Key Agreement Scheme (HH-KAS). HH-KAS uses subset based key agreement scheme at the non-leaf levels and a key agreement scheme due to Sakai et al. (referred as SOK-KAS) at the leaf level. HH-KAS is (i) non-interactive, (ii) identity-based, (iii) hierarchical and (iv) fully resilient against node compromises at leaf level and resilient against node compromises upto certain threshold values in non-leaf levels. Thus one can say that HH-KAS is partially resilient against node compromises. In their paper the authors claim that there is no key agreement scheme for MANETs in the literature, with all above four properties. This was motivated as an interesting open problem in this area.
Guo et al. proposed a scheme known as Strong Key Agreement Scheme (SKAS) in 2011. The authors claimed it as a potential solution to the open problem posed by Gennaro et al. in their work. However, in 2014, Zhu et al. showed a concrete attack on SKAS. This attack makes SKAS practically useless for real life applications.
Our main contribution is a hybrid scheme using two already existing schemes. Our scheme uses a deterministic key pre-distribution scheme by Lee and Stinson termed as Basic Id One-way function Scheme (BIOS) at level 1 (where root is at level 0). Beyond level 1, we use SOK-KAS for key agreement. We refer our scheme as BIOS-SOK key agreement. BIOS and SOK schemes satisfy properties (i), (ii) and (iv) but none of them is hierarchical in nature. In our work we have made an amalgam of both schemes which is hierarchical in nature. Thus, BIOS-SOK scheme satisfies (i), (ii), (iii) and is also fully resilient against arbitrary number of node compromises at any level.
BIOS-SOK scheme also possesses the benefits of low space requirement, low shared key computation time and better scalability for many real-life applications when compared with the scheme of Gennaro et al. In HH-KAS, the key agreement is carried out only at the leaf level. In BIOS-SOK scheme, any two nodes in the hierarchy (at same or different levels) can compute shared secret key. We also provide a rigorous security analysis for our scheme in a stronger security model compared to the security model used for HH-KAS.Indian Institute of Scienc
Efficient and Secure Search over Encrypted Data
No full textDue to a variety of crucial bene fits, enterprises outsource their data to cloud resident storage. The
outsourced data needs to be stored in encrypted form on remote untrusted servers to preserve privacy.
However, if the client has to retrieve the entire data and decrypt it in order to get results for a search query
then that will defeat the purpose of outsourcing. A solution to this problem is Searchable Encryption that
provides a reasonable trade-off between security and effciency.
Our first contribution is in the context of Dynamic Searchable Symmetric Encryption (DSSE). DSSE
schemes, apart from providing support for search operation, allows a client to perform update operations
on outsourced database efficiently. Two security properties, viz., forward privacy and backward privacy are
desirable from a DSSE scheme. The former captures that the newly updated entries cannot be related to
previous search queries and the latter ensures that search queries should not leak matching entries after
they have been deleted. These security properties are formalized in terms of the information leakage that
can be incurred by the respective constructions. Existing backward private constructions either have a non-
optimal communication overhead or they make use of heavy cryptographic primitives. This work makes
two contributions: (i) propose alternative formulations of information leakage for backward privacy after
revisiting the existing ones [Bost et al. CCS'17], (ii) construct three efficient backward private schemes that
aim to achieve practical efficiency by using light weight symmetric cryptographic components only. Our first
construction BP-prime achieves a stronger notion of backward privacy whereas our next two constructions
BP and WBP achieve optimal communication complexity at the cost of some additional leakage. The
prototype implementations of our schemes depict the practicability of the proposed constructions and indicate
that the cost of achieving backward privacy over forward privacy is substantially small.
Certain applications require some type of fuzzy searches like wildcard and edit-distance based search over
encrypted data. In our second work, we investigate the problem of secure wildcard search over encrypted
data in Outsourced Symmetric Private Information Retrieval (OSPIR) setting. The setting comprises of
three entities, viz., the data owner, the server and the client. The data owner outsources the encrypted data
to the server, who obliviously services the clients' queries. We propose two schemes, viz., BS and OTE
to support secure wildcard search over encrypted data. Construction BS reduces the problem of secure
wildcard search to that of boolean search. BS is a sub-linear wildcard search protocol but it allows false
positives. Our second construction OTE utilizes Oblivious Transfer Extension protocols to obtain linear
time wildcard search protocol with no false positives. BS and OTE can then be combined to obtain an
efficient sub-linear solution with no false positives. We provide performance analysis based on our prototype
implementation to depict the feasibility of our proposed constructions
Fully Resilient Non-Interactive ID-Based Hierarchical Key Agreement
No full textNon-Interactive Key Agreement (NIKA) is a cryptographic primitive which allows two parties
to agree on a shared secret key without any interaction. Identity-based Non-Interactive Key
Agreement (ID-NIKA) allows each party to compute shared secret key using its own secret
key and the peer's identity. ID-NIKA can be used to establish shared secret keys in ad-hoc
networks using minimal battery power and communication.
Mobile Ad-hoc NETwork (MANET) is a network of mobile and moderately resource constrained
devices communicating through a wireless medium. Examples of standard MANET
devices are laptops, cellphones etc. Due to the inherent characteristics like mobility, dynamic
topology and lack of centralized infrastructure, MANETs face some serious security issues. We
are particularly interested about ID-NIKA in MANETs. This is of crucial interest for secure
communication between two nodes in MANETs.
In 2008, Gennaro et al. introduced a scheme called Hybrid Hierarchical Key Agreement
Scheme (HH-KAS). HH-KAS uses subset based key agreement scheme at the non-leaf levels
and a key agreement scheme due to Sakai et al. (referred as SOK-KAS) at the leaf level. HHKAS
is (i) non-interactive, (ii) identity-based, (iii) hierarchical and (iv) fully resilient against
node compromises at leaf level and resilient against node compromises upto certain threshold
values in non-leaf levels. Thus one can say that HH-KAS is partially resilient against node compromises.
In their paper the authors claim that there is no key agreement scheme for MANETs
in the literature, with all above four properties. This was motivated as an interesting open
problem in this area.
Guo et al. proposed a scheme known as Strong Key Agreement Scheme (SKAS) in 2011.
The authors claimed it as a potential solution to the open problem posed by Gennaro et al.
in their work. However, in 2014, Zhu et al. showed a concrete attack on SKAS. This attack
makes SKAS practically useless for real life applications.
Our main contribution is a hybrid scheme using two already existing schemes. Our scheme
uses a deterministic key pre-distribution scheme by Lee and Stinson termed as Basic Id Oneway
function Scheme (BIOS) at level 1 (where root is at level 0). Beyond level 1, we use
SOK-KAS for key agreement. We refer our scheme as BIOS-SOK key agreement. BIOS and
SOK schemes satisfy properties (i), (ii) and (iv) but none of them is hierarchical in nature. In
our work we have made an amalgam of both schemes which is hierarchical in nature. Thus,
BIOS-SOK scheme satis es (i), (ii), (iii) and is also fully resilient against arbitrary number of
node compromises at any level.
BIOS-SOK scheme also possesses the bene ts of low space requirement, low shared key
computation time and better scalability for many real-life applications when compared with
the scheme of Gennaro et al. In HH-KAS, the key agreement is carried out only at the leaf
level. In BIOS-SOK scheme, any two nodes in the hierarchy (at same or di erent levels) can
compute shared secret key. We also provide a rigorous security analysis for our scheme in a
stronger security model compared to the security model used for HH-KAS
Quantum-Safe Identity-Based Signature Scheme in Multivariate Quadratic Setting
No full textCryptographic techniques are essential for the security of communication in modern society. Today, nearly all public key cryptographic schemes used in practice are based on the two problems of factoring large integers and solving discrete logarithms. However, as the world grapples with the possibility of widespread quantum computing, these schemes are the ones most threatened. Multivariate Public Key Cryptography is one of the possible candidates for security in a post-quantum society, especially in the area of digital signature. This thesis uses the setting of multivariate cryptography to propose an identity-based signature scheme. Our proposal is based on the Rainbow signature scheme and the multivariate 3-pass identification scheme, both of which have been subjected to scrutiny by cryptographers all over the world and have emerged as strong post-quantum candidates. In our construction, we use the identity of users to generate their private key using Rainbow signature scheme. Thereafter, we use these user private keys to sign messages by applying Fiat-Shamir transform to the 3-pass identification scheme. We support the proposed scheme with suitable proof under appropriate computational assumptions, using the standard notions of security. We study the known attacks against multivariate schemes in general, and Rainbow and MQDSS in particular. We then use this analysis to propose concrete parameter sets for our construction. We implement our proposed scheme on an x86-64 PC platform and provide timing results. Our implementation shows that our construction is both practical and efficient. Thus our proposed scheme stands as a potential post-quantum multivariate signature candidate in the identity-based setting
Security of Post-Quantum Multivariate Blind Signature Scheme: Revisited and Improved
No full textCurrent cryptosystems face an imminent threat from quantum algorithms like Shor's and Grover's, leading us to post-quantum cryptography. Multivariate signatures are prominent in post-quantum cryptography due to their fast, low-cost implementations and shorter signatures. Blind signatures are a special category of digital signatures with two security notions: blindness and one-more unforgeability (OMF). Our work primarily focuses on the multivariate blind signature scheme (MBSS) proposed by Petzoldt et al. We construct a formal proof along the lines of the heuristic sketch given by the authors of MBSS based on the proposed universal one-more unforgeability (UOMF) model, a weaker variant of OMF. Proper reconstruction of their proof led us to identify the various issues in the security argument - mainly the difficulty in simulating the response to the blind signature queries without knowing the secret key of the underlying Rainbow scheme used. Since our investigation revealed the difficulty in reducing the UOMF security to the hardness assumption used by the authors, therefore we design a new class of hardness assumptions: (1) Single Target Inversion Problem, PR-STI (2) Modified Single Target Inversion Problem, PR-mSTI (3) Chosen Target Inversion Problem, PR-CTI. Armed with the new class of computational problems, we reduce the UOMF and OMF security of MBSS to these problems. We begin by giving a security argument of MBSS in the UOMF security model using the PR-mSTI assumption, which is assumed to be quantum-safe. We employ the general forking algorithm in this security reduction. However, we cannot apply the forking algorithm directly owing to the wrapper algorithm being split and the presence of the blind signature oracle. We thus suitably modify the algorithm and then derive the corresponding forking probability. To argue the security of MBSS in the standard security model, i.e., in the OMF model, we try using the PR-CTI assumption. The PR-CTI problem demands computing the solution for more than one target. Computing the solution for more than one target entails using the forking process more than once. Since forking causes a high degradation in the success probability, this leads to a significant degradation factor in the success probability. So, instead, we reduce the OMF security of MBSS to the PR-mSTI assumption (in a restricted setting) and give a comparative analysis between the security arguments in the UOMF and OMF models
Constructing Provably Secure Identity-Based Signature Schemes
Full text linkAn identity-based cryptosystem (IBC) is a public-key system where the public key can be represented by any arbitrary string such as an e-mail address. The notion was introduced by Shamir with the primary goal of simplifying certificate management. An identity-based signature(IBS) is the identity-based counter part of a digital signature.
In the first (and primary) part of the work, we take a closer look at an IBS due to Galindo and Garcia–GG-IBS, for short. GG-IBS is derived through a simple and elegant concatenation of two Schnorr signatures and, importantly, does not rely on pairing. The security is established through two algorithms (both of) which use the Multiple-Forking(MF) Algorithm to reduce the problem of computing the discrete logarithm to breaking the IBS. Our focus is on the security argument : It turns out that the argument is flawed and, as a remedy, we sketch a new security argument. However, the resulting security bound is still quite loose, chiefly due to the usage of the MF Algorithm. We explore possible avenues for improving this bound and , to this end, introduce two notions pertaining to random oracles termed dependency and independency. Incorporating (in) dependency allows us to launch the nested replay attack far more effectively than in the MF Algorithm leading to a cleaner,(significantly) tighter security argument for GG-IBS, completing the final piece of the GG-IBS jigsaw.
The second part of the work pertains to the notion of selective-identity (sID) for IBCs. The focus is on the problem of constructing a fully-secure IBS given an sID-secure IBS without using random oracles and with reasonable security degradation
Towards Secure and Efficient Realization of Pairing-Based Signatures from Static Assumptions.
No full textBilinear pairing defined over elliptic curve group was first used to design novel cryptosystem in 2000. Since then a large number of cryptosystems has been proposed in pairing-based cryptography (PBC). The main tool for all such cryptosystems is the pairing map which can be defined on either composite or prime-order groups. Security of a public key cryptosystem is typically proved under some computational hardness assumption. PBC has witnessed a plenty of parameterized/interactive assumptions. However, it is well-known that such assumptions have several limitations. In this thesis we explore the question of security and efficiency of pairing-based signature schemes based on static assumptions. We have investigated the efficacy of the following approaches towards this goal: (i). frameworks for converting cryptosystems from composite to prime-order bilinear pairing setting, (ii). DejaQ framework, for removing dependency on parameterized assumption and (iii). dual-form signature (DFS) technique, for removing dependency on parameterized/interactive assumption.
First, we focus on the conversion framework. In 2005, Boneh et al. introduced a novel homomorphic encryption scheme using composite-order pairing setting. From then there are plenty of cryptosystems constructed in the composite-order pairing setting. However, it is well known that a composite-order pairing is significantly slower than its prime-order counterpart. This motivated Freeman to propose his conversion framework that converts some cryptographic protocols to the prime-order pairing setting. He formally defined certain properties called projecting and canceling, which are used in the protocol construction and/or in the security argument. Since then several frameworks have been proposed for conversion purpose. We revisit all the projecting frameworks and establish that Freeman's framework is still optimal in the asymmetric pairing setting. We also present an alternative security proof for Seo-Cheon's projecting and canceling framework under the static symmetric external Diffie-Hellman (SXDH) assumption, instead of the original tailor-made assumption. Next, we formalize the full-decomposition notion in the existing projecting frameworks and show that this notion is sufficient instead of the so-called translating property. Then, we abstract an unbalanced projecting framework in the asymmetric pairing setting that allows the pairing source groups to have different orders. As application, we convert the following schemes to the prime-order asymmetric pairing setting: Shacham-Waters ring signature, Boyen-Waters group signature and Meiklejohn et al's round optimal blind signature. In their original construction, security of the above schemes requires both projecting and canceling properties in the composite-order symmetric pairing setting. We show that the framework for projecting and canceling is not necessary to instantiate these schemes.
Next, we focus on a set of parameterized assumptions called the BTA family. Such parameterized assumptions play a crucial role in the security of many novel pairing-based cryptosystems. However, they have some negative impact on efficiency at a concrete security level. A prominent approach to remove the dependency on parameterized assumption is the DejaQ framework of Chase et al. The DejaQ framework aims to establish that certain parameterized assumptions are implied by the subgroup hiding assumption in the composite-order pairing setting. Applying DejaQ framework to a family of assumptions is an important question, as it covers several parameterized assumptions which in turn cover more cryptographic protocols. However, the existing DejaQ framework could cover only Boyen's Uber assumption family. Recently Ghadafi and Groth introduced the bilinear target assumption (BTA) family, that covers more parameterized assumptions including the Uber assumption family. We show that the parameterized assumptions that belong to the BTA family are reducible from the subgroup hiding assumption. In the process, we first suitably extend a property called parameter-hiding and then adapt the DejaQ proof technique on the parameterized assumptions that belong to the BTA family.
Finally, we focus on the applicability of the dual-form signature (DFS) technique on some pairing-based signatures. The DejaQ framework does not address the question of how to remove the dependency on interactive assumption. The DFS technique can be used for this purpose and it is applied directly in the security argument of the protocol. We use the DFS technique to prove the security of Abe et al's structure-preserving signature, Boyen-Waters group signature and Pointcheval-Sanders rerandomizable signature (RRS) under some static assumptions. We also present an efficient construction of RRS scheme in the prime-order setting. Then, we use the proposed RRS scheme as a building block to construct a sequential aggregate signature (SeqAS) scheme with constant-size public key under the SXDH assumption. The performance of the proposed schemes is comparable to that of previous proposals based on some non-standard interactive assumptions
Towards Effcient Privacy-Preserving Two-Party k-Means Clustering Protocol
No full textTwo-party data mining is a win-win game if played with a guarantee of data privacy from each other.
This guarantee is provided by the use of cryptographic techniques in designing the two-party protocol.
The need to obtain collaborative data mining results is growing and so is the need for privacy-preserving data mining protocols.
Clustering is one of the data mining techniques and one of the popular clustering algorithms is k-means clustering.
We studied the recent work for the secure two-party k-means clustering by Bunn and Ostrovosky and found that the protocol is inefficient for practical purposes.
The protocol requires communication rounds which are linear in security parameter for the center initialization step and are quadratic in security parameter for an iterative Lloyd's step of the k-means clustering algorithm.
The challenge in the secure two-party k-means clustering is the exorbitant communication cost occurring due to the high number of interactions between the parties for performing computations on the data.
Our work attempts to resolve this problem of inefficiency in k-means clustering protocol in a two-party setting by proposing some modifications.
We have come up with two comparison protocols that are required in the k-means clustering protocol.
One of the protocols is to find a minimum of two shared numbers which runs in constant communication rounds.
Using this protocol as a building block, another protocol is designed to find a minimum of n shared numbers, which runs in O(n) communication rounds.
We have also improved a protocol that selects a random value from a domain oblivious to both parties.
Apart from this, the idea to avoid the two-party integer division altogether is incorporated in the k-means clustering protocol.
With these improvements, we propose a two-party k-means clustering protocol for which the initialization step requires communication rounds linear in security parameter and Lloyd's step requires communications rounds that are independent of the security parameter.
The protocol provides a security guarantee in the semi-honest model except for some minor information leakage.
We argue that this leakage in the protocol can be tolerated considering the substantial gain in the communication cost
We have verified the gain in performance of the modified protocol by implementing both the k-means clustering protocols and running their instances in the same set-up
- …
