International Association for Cryptologic Research

International Association
for Cryptologic Research

CryptoDB

Reihaneh Safavi-Naini

Affiliation: AIST, JP

Publications

Year
Venue
Title
2015
EPRINT
2014
EPRINT
2014
EPRINT
2011
EUROCRYPT
2008
PKC
2008
EPRINT
New Results on Unconditionally Secure Multireceiver Manual Authentication
Shuhong Wang Reihaneh Safavi-Naini
Manual authentication is a recently proposed model of communication motivated by the settings where the only trusted infrastructure is a low bandwidth authenticated channel, possibly realized by the aid of a human, that connects the sender and the receiver who are otherwise connected through an insecure channel and do not have any shared key or public key infrastructure. A good example of such scenarios is pairing of devices in Bluetooth. Manual authentication systems are studied in computational and information theoretic security model and protocols with provable security have been proposed. In this paper we extend the results in information theoretic model in two directions. Firstly, we extend a single receiver scenario to multireceiver case where the sender wants to authenticate the same message to a group of receivers. We show new attacks (compared to single receiver case) that can launched in this model and demonstrate that the single receiver lower bound $2\log(1/\epsilon)+O(1)$ on the bandwidth of manual channel stays valid in the multireceiver scenario. We further propose a protocol that achieves this bound and provides security, in the sense that we define, if up to $c$ receivers are corrupted. The second direction is the study of non-interactive protocols in unconditionally secure model. We prove that unlike computational security framework, without interaction a secure authentication protocol requires the bandwidth of the manual channel to be at least the same as the message size, hence non-trivial protocols do not exist.
2008
EPRINT
Attribute-Based Encryption with Key Cloning Protection
In this work, we consider the problem of key cloning in attribute-based encryption schemes. We introduce a new type of attribute-based encryption scheme, called token-based attribute-based encryption, that provides strong deterrence for key cloning, in the sense that delegation of keys reveals some personal information about the user. We formalize the security requirements for such a scheme in terms of indistinguishability of the ciphertexts and two new security requirements which we call uncloneability and privacy-preserving. We construct a privacy-preserving uncloneable token-based attribute-based encryption scheme based on Cheung and Newport's ciphertext-policy attribute-based encryption scheme and prove the scheme satisfies the above three security requirements. We discuss our results and show directions for future research.
2007
EPRINT
Noninteractive Manual Channel Message Authentication Based On eTCR Hash Functions
Reza Reyhanitabar Shuhong Wang Reihaneh Safavi-Naini
We present a new non-interactive message authentication protocol in manual channel model (NIMAP, for short) using the weakest assumption on the manual channel (i.e. assuming the strongest adversary). Our protocol uses enhanced target collision resistant (eTCR) hash family and is provably secure in the standard model. We compare our protocol with protocols with similar properties and show that the new NIMAP has the same security level as the best previously known NIMAP whilst it is more practical. In particular, to authenticate a message such as a 1024-bit public key, we require an eTCR hash family that can be constructed from any off-the-shelf Merkle-Damg{\aa}rd hash function using randomized hashing mode. The underlying compression function must be {\em evaluated second preimage resistant} (eSPR), which is a strictly weaker security property than collision resistance. We also revisit some closely related security notions for hash functions and study their relationships to help understanding our protocol.
2007
EPRINT
Construction of Universal Designated-Verifier Signatures and Identity-Based Signatures from Standard Signatures
Siamak F Shahandshti Reihaneh Safavi-Naini
We give a generic construction of universal designated-verifier signature schemes from a large class C of signature schemes. Our constructions are comparable in terms of cost and size to their counterparts, while offering the following two main attractive features: Firstly, our constructions are provably non-delegatable beside being DV-unforgeable and non-transferable. Secondly, in our constructions, the signer and the designated verifier can choose different cryptographic settings of their own independently. We also propose a generic construction of identity-based signature schemes from any signature scheme in C and prove the construction secure against adaptive chosen message and identity attacks. We discuss possible extensions of our constructions to universal multi-designated-verifier signatures, hierarchical identity-based signatures, identity-based universal designated verifier signatures, and identity-based ring signatures from any signature in C.
2006
EPRINT
An Efficient Single-Key Pirates Tracing Scheme Using Cover-Free Families
Dongvu Tonien Reihaneh Safavi-Naini
A cover-free family is a well-studied combinatorial structure that has many applications in computer science and cryptography. In this paper, we propose a new public key traitor tracing scheme based on cover-free families. The new traitor tracing scheme is similar to the Boneh-Franklin scheme except that in the Boneh-Franklin scheme, decryption keys are derived from Reed-Solomon codes while in our case they are derived from a cover-free family. This results in much simpler and faster tracing algorithms for single-key pirate decoders, compared to the tracing algorithms of Boneh-Franklin scheme that use Berlekamp-Welch algorithm. Our tracing algorithms never accuse innocent users and identify all traitors with overwhelming probability.
2006
EPRINT
Information Theoretic Bounds on Authentication Systems in Query Model
Reihaneh Safavi-Naini Peter Wild
Authentication codes provide message integrity guarantees in an information theoretic sense within a symmetric key setting. Information theoretic bounds on the success probability of an adversary who has access to previously authenticated messages have been derived by Simmons and Rosenbaum, among others. In this paper we consider a strong attack scenario where the adversary is adaptive and has access to authentication and verification oracles. We derive information theoretic bounds on the success probability of the adversary and on the key size of the code. This brings the study of unconditionally secure authentication systems on a par with the study of computationally secure ones. We characterize the codes that meet these bounds and compare our result with the earlier ones.
2005
ASIACRYPT
2005
PKC
2005
EPRINT
A Provably Secure and Efficient Verifiable Shuffle based on a Variant of the Paillier Cryptosystem
Lan Nguyen Rei Safavi-Naini Kaoru Kurosawa
We propose a variant of the Paillier cryptosystem that improves efficiency in encryption, re-encryption and decryption while preserving the homomorphic property. We then use this variant to construct a new verifiable shuffle system and prove its security. We show that the new shuffle scheme has the least number of rounds and exponentiations compared to all known shuffle schemes. Finally, we show how to construct a publicly verifiable mix-net using the shuffle system.
2005
EPRINT
Recursive Constructions of Secure Codes and Hash Families Using Difference Function Families
Dongvu Tonien Reihaneh Safavi-Naini
To protect copyrighted digital data against piracy, codes with different secure properties such as frameproof codes, secure frameproof codes, codes with identifiable parent property (IPP codes), traceability codes (TA codes) are introduced. In this paper, we study these codes together with related combinatorial objects called separating and perfect hash families. We introduce for the first time the notion of difference function families and use these difference function families to give generalized recursive techniques that can be used for any kind of secure codes and hash families. We show that some previous recursive techniques are special cases of these new techniques.
2005
EPRINT
Verifiable Shuffles: A Formal Model and a Paillier-based 3-Round Construction with Provable Security
Lan Nguyen Rei Safavi-Naini Kaoru Kurosawa
We propose a formal model for security of verifiable shuffles and a new verifiable shuffle system based on the Paillier encryption scheme, and prove its security in the proposed model. The model is general, so it can be extended to verifiable shuffle decryption and provides a direction for provable security of mix-nets.
2005
EPRINT
Fuzzy Universal Hashing and Approximate Authentication
Reihaneh Safavi-Naini Dongvu Tonien
Traditional data authentication systems are sensitive to single bit changes and so are unsuitable for message spaces that are naturally fuzzy where similar messages are considered the same or at least indistinguishable. In this paper, we study unconditional secure approximate authentication. We generalize traditional universal hashing to fuzzy universal hashing and use it to construct secure approximate authentication for multiple messages.
2005
EPRINT
Dynamic k-Times Anonymous Authentication
Lan Nguyen Rei Safavi-Naini
k-times anonymous authentication (k-TAA) schemes allow members of a group to be anonymously authenticated by application providers for a bounded number of times. k-TAA has application in e-voting, e-cash, electronic coupons and anonymous trial browsing of content. In this paper, we extend k-TAA model to dynamic k-TAA in which application providers can independently grant or revoke users from their own groups and so have the required control on their clients. We give a formal model for dynamic k-TAA, propose a dynamic k-times anonymous authentication scheme from bilinear pairing, and prove its security. We also construct an ordinary k-TAA from the dynamic scheme and show communication efficiency of the schemes compared to the previously proposed schemes.
2005
EPRINT
Public Key Encryption with Keyword Search Revisited
Joonsang Baek Reihaneh Safavi-Naini Willy Susilo
The public key encryption with keyword search (PEKS) scheme recently proposed by Boneh, Di Crescenzo, Ostrovsky, and Persiano enables one to search encrypted keywords without compromising the security of the original data. In this paper, we address three important issues of a PEKS scheme, ``refreshing keywords'', ``removing secure channel'', and ``processing multiple keywords'', which have not been considered in Boneh et. al.'s paper. We argue that care must be taken when keywords are used frequently in the PEKS scheme as this situation might contradict the security of PEKS. We then point out the inefficiency of the original PEKS scheme due to the use of the secure channel. We resolve this problem by constructing an efficient PEKS scheme that removes secure channel. Finally, we propose a PEKS scheme that encrypts multiple keywords efficiently.
2005
EPRINT
Explicit Construction of Secure Frameproof Codes
Dongvu Tonien Reihaneh Safavi-Naini
$\Gamma$ is a $q$-ary code of length $L$. A word $w$ is called a descendant of a coalition of codewords $w^{(1)}, w^{(2)}, \dots, w^{(t)}$ of $\Gamma$ if at each position $i$, $1 \leq i \leq L$, $w$ inherits a symbol from one of its parents, that is $w_i \in \{ w^{(1)}_i, w^{(2)}_i, \dots, w^{(t)}_i \}$. A $k$-secure frameproof code ($k$-SFPC) ensures that any two disjoint coalitions of size at most $k$ have no common descendant. Several probabilistic methods prove the existance of codes but there are not many explicit constructions. Indeed, it is an open problem in [J. Staddon et al., IEEE Trans. on Information Theory, 47 (2001), pp. 1042--1049] to construct explicitly $q$-ary 2-secure frameproof code for arbitrary $q$. In this paper, we present several explicit constructions of $q$-ary 2-SFPCs. These constructions are generalisation of the binary inner code of the secure code in [V.D. To et al., Proceeding of IndoCrypt'02, LNCS 2551, pp. 149--162, 2002]. The length of our new code is logarithmically small compared to its size.
2004
ASIACRYPT
2004
PKC
2004
PKC
2004
EPRINT
Efficient Verifiably Encrypted Signature and Partially Blind Signature from Bilinear Pairings
Fangguo Zhang Reihaneh Safavi-Naini Willy Susilo
Verifiably encrypted signatures are used when Alice wants to sign a message for Bob but does not want Bob to possess her signature on the message until a later date. Such signatures are used in optimistic contact signing to provide fair exchange. Partially blind signature schemes are an extension of blind signature schemes that allows a signer to sign a partially blinded message that include pre-agreed information such as expiry date or collateral conditions in unblinded form. These signatures are used in applications such as electronic cash (e-cash) where the signer requires part of the message to be of certain form. In this paper, we propose a new verifiably encrypted signature scheme and a partially blind signature scheme, both based on bilinear pairings. We analyze the security and efficiency of these schemes and show that they are more efficient than the previous schemes of their kinds.
2004
EPRINT
Efficient and Provably Secure Trapdoor-free Group Signature Schemes from Bilinear Pairings
Lan Nguyen Rei Safavi-Naini
Group signature schemes are cryptographic systems that provide revocable anonymity for signers. We propose a group signature scheme with constant-size public key and signature length that does not require trapdoor. So system parameters can be shared by multiple groups belonging to different organizations. The scheme is provably secure in the formal model recently proposed by Bellare, Shi and Zhang (BSZ04), using random oracle model, Decisional Bilinear Diffie-Hellman and Strong Diffie-Hellman assumptions. We give a more efficient variant scheme and prove its security in a formal model which is a modification of BSZ04 model and has a weaker anonymity requirement. Both schemes are very efficient and the sizes of signatures are approximately one half and one third, respectively, of the sizes of the well-known ACJT00 scheme. We will show that the schemes can be used to construct a traceable signature scheme and identity escrow schemes. They can also be extended to provide membership revocation.
2003
EPRINT
Distributing the Encryption and Decryption of a Block Cipher
In threshold cryptography the goal is to distribute the computation of basic cryptographic primitives across a number of nodes in order to relax trust assumptions on individual nodes, as well as to introduce a level of fault-tolerance against node compromise. Most threshold cryptography has previously looked at the distribution of public key primitives, particularly threshold signatures and threshold decryption mechanisms. In this paper we look at the application of threshold cryptography to symmetric primitives, and in particular the encryption or decryption of a symmetric key block cipher. We comment on some previous work in this area and then propose a model for shared encryption / decryption of a block cipher. We will present several approaches to enable such systems and will compare them.
2003
EPRINT
New Proxy Signature, Proxy Blind Signature and Proxy Ring Signature Schemes from Bilinear Pairing
Fangguo Zhang Reihaneh Safavi-Naini Chih-Yin Lin
Proxy signatures are very useful tools when one needs to delegate his/her signing capability to other party. After Mambo $et\ al.$'s first scheme was announced, many proxy signature schemes and various types of proxy signature schemes have been proposed. Due to the various applications of the bilinear pairings in cryptography, there are many ID-based signature schemes have been proposed. In this paper, we address that it is easy to design proxy signature and proxy blind signature from the conventional ID-based signature schemes using bilinear pairings, and give some concrete schemes based on existed ID-based signature schemes. At the same time, we introduce a new type of proxy signature -- proxy ring signature, and propose the first proxy ring signature scheme based on an existed ID-based ring signature scheme.
2003
EPRINT
Attack on Han et al.'s ID-based Confirmer (Undeniable) Signature at ACM-EC'03
Fangguo Zhang Reihaneh Safavi-Naini Willy Susilo
At the fourth ACM conference on electronic commerce (EC'03), S. Han, K.Y. Yeung and J. Wang proposed an ID-based confirmer signature scheme using pairings (actually, this is an ID-based undeniable signature scheme). However, in this paper, we will show that this signature scheme is not secure. The signer can deny any signature, even this signature is his valid signature and any one can forge a valid confirmer signature of a signer with identity ID on an arbitrary message and confirm this signature to the verifier.
2003
EPRINT
ID-Based Chameleon Hashes from Bilinear Pairings
Fangguo Zhang Reihaneh Safavi-Naini Willy Susilo
Chameleon hash function is a trapdoor one-way hash function. The ID-based chameleon hash function was first introduced by Ateniese and Medeiros \cite{AM03}. As discussed by \cite{AM03}, the general advantages of ID-based cryptography over conventional cryptography with respect to key distribution are even more pronounced in a chameleon hashing scheme, because the owner of a public key does not necessarily need to retrieve the associated secret key. In this paper, we propose two new ID-based Chameleon hashing schemes from bilinear pairings. Also we analyze their security and efficiency. Based on these ID-based chameleon hashes, ID-based chameleon signature schemes can be designed.
2000
CRYPTO
Sequential Traitor Tracing
Reihaneh Safavi-Naini Yejing Wang
1999
ASIACRYPT
1999
ASIACRYPT
1998
ASIACRYPT
1998
EUROCRYPT
1998
FSE
1998
PKC
1994
ASIACRYPT
1994
EUROCRYPT
1994
EUROCRYPT
1993
EUROCRYPT
1992
AUSCRYPT
1992
AUSCRYPT
1991
ASIACRYPT
Feistel Type Authentication Codes
Reihaneh Safavi-Naini
1991
EUROCRYPT
1990
AUSCRYPT

Program Committees

TCC 2019
Asiacrypt 2017
Crypto 2016
Asiacrypt 2016
Asiacrypt 2015
Asiacrypt 2013
Crypto 2012
Asiacrypt 2012
Crypto 2011
Asiacrypt 2009
PKC 2009
Eurocrypt 2008
Asiacrypt 2008
Crypto 2007
Asiacrypt 2006
PKC 2005
Asiacrypt 2005
Asiacrypt 2004
Asiacrypt 2003
Crypto 2002
Eurocrypt 2002
Asiacrypt 2001
Eurocrypt 1998
Asiacrypt 1994
Auscrypt 1992
Auscrypt 1990