Journal of Computer Security - Volume 21, issue 5

Authors: Visconti, Ivan

Article Type: Editorial

DOI: 10.3233/JCS-130483

Citation: Journal of Computer Security, vol. 21, no. 5, pp. 599-600, 2013

Authors: Baron, Joshua | El Defrawy, Karim | Minkovich, Kirill | Ostrovsky, Rafail | Tressler, Eric

Article Type: Research Article

Abstract: In this paper we consider the problem of secure pattern matching that allows single-character wildcards and substring matching in the malicious (stand-alone) setting. Our protocol, called 5PM, is executed between two parties: Server, holding a text of length n, and Client, holding a pattern of length m to be matched against the text, where our notion of matching is more general than traditionally considered and includes non-binary alphabets, non-binary Hamming distance and non-binary substring matching. 5PM is the first secure expressive pattern matching protocol designed to optimize round complexity by carefully specifying the entire protocol round by round. 5PM …requires only eight rounds in the malicious (static corruptions) model. In the malicious model, 5PM requires O ( ( m + n ) k 2 ) communication complexity and O ( m + n ) encryptions, where m is the pattern length and n is the text length. Further, 5PM can hide pattern size with no asymptotic additional costs in either computation or bandwidth. Show more

Keywords: Secure pattern matching, secure two-party computation, malicious adversary, full simulation, homomorphic encryption

DOI: 10.3233/JCS-130481

Citation: Journal of Computer Security, vol. 21, no. 5, pp. 601-625, 2013

Authors: Blazy, Olivier | Fuchsbauer, Georg | Pointcheval, David | Vergnaud, Damien

Article Type: Research Article

Abstract: Blind signatures allow users to obtain signatures on messages hidden from the signer; moreover, the signer cannot link the resulting message/signature pair to the signing session. This paper presents blind signature schemes, in which the number of interactions between the user and the signer is minimal and whose blind signatures are short. Our schemes are defined over bilinear groups and are proved secure in the common-reference-string model without random oracles and under standard assumptions: CDH and the decision-linear assumption. (We also give variants over asymmetric groups based on similar assumptions.) The blind signatures are Waters signatures, which consist of 2 …group elements. Moreover, we instantiate partially blind signatures, where the message consists of a part hidden from the signer and a commonly known public part, and schemes achieving perfect blindness. We propose new variants of blind signatures, such as signer-friendly partially blind signatures, where the public part can be chosen by the signer without prior agreement, 3-party blind signatures, as well as blind signatures on multiple aggregated messages provided by independent sources. We also extend Waters signatures to non-binary alphabets by proving a new result on the underlying hash function. Show more

Keywords: Blind signatures, e-cash, WSN, mixed commitments

DOI: 10.3233/JCS-130477

Citation: Journal of Computer Security, vol. 21, no. 5, pp. 627-661, 2013

Authors: Gentry, Craig | Halevi, Shai | Peikert, Chris | Smart, Nigel P.

Article Type: Research Article

Abstract: The security of contemporary homomorphic encryption schemes over cyclotomic number field relies on fields of very large dimension. This large dimension is needed because of the large modulus-to-noise ratio in the key-switching matrices that are used for the top few levels of the evaluated circuit. However, a smaller modulus-to-noise ratio is used in lower levels of the circuit, so from a security standpoint it is permissible to switch to lower-dimension fields, thus speeding up the homomorphic operations for the lower levels of the circuit. However, implementing such field-switching is nontrivial, since these schemes rely on the field algebraic structure for …their homomorphic properties. A basic ring-switching operation was used by Brakerski, Gentry and Vaikuntanathan, over rings of the form Z [ X ] / ( X 2 n + 1 ) , in the context of bootstrapping. In this work we generalize and extend this technique to work over any cyclotomic number field, and show how it can be used not only for bootstrapping but also during the computation itself (in conjunction with the “packed ciphertext” techniques of Gentry, Halevi and Smart). Show more

Keywords: Homomorphic encryption, ring-LWE

DOI: 10.3233/JCS-130480

Citation: Journal of Computer Security, vol. 21, no. 5, pp. 663-684, 2013

Authors: Lipmaa, Helger | Zhang, Bingsheng

Article Type: Research Article

Abstract: We propose a new non-interactive perfect zero-knowledge (NIZK) shuffle argument that, when compared with the only previously known efficient NIZK shuffle argument by Groth and Lu, has a small constant factor times smaller computation and communication, and is based on more standard computational assumptions. Differently from Groth and Lu who only prove the co-soundness of their argument under purely computational assumptions, we prove computational soundness under a necessary knowledge assumption. We also present a general transformation that results in a shuffle argument that has a quadratically smaller common reference string (CRS) and a small constant factor times longer argument than …the original shuffle. This can be interpreted as a general technique of decreasing the offline cost of an arbitrary shuffle argument. Show more

Keywords: Bilinear pairings, Clos network, cryptographic shuffle, non-interactive zero-knowledge, progression-free sets

DOI: 10.3233/JCS-130478

Citation: Journal of Computer Security, vol. 21, no. 5, pp. 685-719, 2013

Authors: Myers, Steven | Sergi, Mona | shelat, abhi

Article Type: Research Article

Abstract: We construct a Non-Malleable Chosen Ciphertext Attack (NM-CCA1) encryption scheme from any encryption scheme that is also plaintext aware and weakly simulatable. We believe this is the first construction of a NM-CCA1 scheme that follows strictly from encryption schemes with seemingly weaker or incomparable security definitions to NM-CCA1. Previously, the statistical Plaintext Awareness #1 (PA1) notion was only known to imply CCA1. Our result is therefore novel because unlike the case of Chosen Plaintext Attack (CPA) and Chosen Chiphertext Attack (CCA2), it is unknown whether a CCA1 scheme can be transformed into an NM-CCA1 scheme. Additionally, we show both …the Damgård Elgamal Scheme (DEG) [in: CRYPTO, J. Feigenbaum, ed., Lecture Notes in Computer Science, Vol. 576, Springer, 1991, pp. 445–456] and the Cramer–Shoup Lite Scheme (CS-Lite) [SIAM J. Comput. 33(1) (2003), 167–226] are weakly simulatable under the DDH assumption. Since both are known to be statistical Plaintext Aware 1 (PA1) under the Diffie–Hellman Knowledge (DHK) assumption, they instantiate our scheme securely. Furthermore, in response to a question posed by Matsuda and Matsuura [in: Public Key Cryptography, D. Catalano, N. Fazio, R. Gennaro and A. Nicolosi, eds, Lecture Notes in Computer Science, Vol. 6571, Springer, 2011, pp. 246–264], we define cNM-CCA1-security in which an NM-CCA1-adversary is permitted to ask a c ≥ 1 number of parallel queries after receiving the challenge ciphertext. We extend our construction to yield a cNM-CCA1 scheme for any constant c. All of our constructions are black-box. Show more

Keywords: Public-key encryption, plaintext-awareness, non-malleability

DOI: 10.3233/JCS-130485

Citation: Journal of Computer Security, vol. 21, no. 5, pp. 721-748, 2013

Authors: Nieto, Juan González | Manulis, Mark | Poettering, Bertram | Rangasamy, Jothi | Stebila, Douglas

Article Type: Research Article

Abstract: In many applications where encrypted traffic flows from an open (public) domain to a protected (private) domain there exists a gateway that bridges these two worlds, faithfully forwarding all incoming traffic to the receiver. We observe that the notion of indistinguishability against (adaptive) chosen-ciphertext attacks (IND-CCA2), which is a mandatory goal in face of active attacks in a public domain, can be relaxed to indistinguishability against chosen-plaintext attacks (IND-CPA) once the ciphertexts passed the gateway. The latter then acts as an IND-CCA2/CPA filter by first checking the validity of an incoming IND-CCA2-secure ciphertext, transforming it (if valid) into an IND-CPA-secure …ciphertext, and finally forwarding it to the recipient in the private domain. Non-trivial filtering can result in reduced decryption costs on the recipient's side. We identify a class of encryption schemes with publicly verifiable ciphertexts that admit generic constructions of IND-CCA2/CPA filters (with non-trivial verification). These schemes are characterized by existence of public algorithms that can distinguish ultimately between valid and invalid ciphertexts. To this end, we formally define public verifiability of ciphertexts for general encryption schemes, key encapsulation mechanisms and hybrid encryption schemes, encompassing public-key, identity-based and tag-based encryption flavours. We further analyze the security impact of public verifiability and discuss generic transformations and concrete constructions that enjoy this property. Show more

Keywords: Ciphertext filtering, public key encryption, identity-based encryption, chosen ciphertext attacks

DOI: 10.3233/JCS-130473

Citation: Journal of Computer Security, vol. 21, no. 5, pp. 749-778, 2013