Skip to main content
main-content
Top

Hint

Swipe to navigate through the articles of this issue

Published in: Designs, Codes and Cryptography 2/2022

16-01-2022

Generic transformation from broadcast encryption to round-optimal deniable ring authentication

Authors: Keisuke Hara, Takahiro Matsuda, Goichiro Hanaoka, Keisuke Tanaka

Published in: Designs, Codes and Cryptography | Issue 2/2022

Login to get access
share
SHARE

Abstract

Deniable ring authentication enables a prover in some group (called a ring) to authenticate a message to a verifier using its secret key while at the same time allowing the prover to deny ever having interacted with the verifier. This primitive furthermore guarantees the anonymity of the prover in the sense that the verifier will learn nothing about the prover’s identity except that it is included in the ring. In this work, we propose a new generic construction of two-round concurrently deniable ring authentication in the random oracle model. Our generic construction is based on any \(\text {IND-CPA}\) secure broadcast encryption (BE) scheme. Instantiating the underlying \(\text {IND-CPA}\) secure BE scheme with the schemes proposed by Agrawal and Yamada (EUROCRYPT 2020) or Agrawal, Wichs, and Yamada (TCC 2020), we obtain the first two-round concurrently deniable ring authentication scheme with optimal efficiency in an asymptotic sense. Here, by optimal efficiency, we mean that all of the sizes of a public parameter and secret keys, the communication costs, and the number of pairing operations are independent of n, where n is the number of users in a ring. In addition to these main instantiations, through our generic construction, we further obtain various two-round concurrently deniable ring authentication schemes.
Appendix
Available only for authorised users
Footnotes
1
We note that some previous works (e.g., [33, 34]) proposed non-interactive deniable ring authentication schemes with partial deniability. Partial deniability only ensures that a user in the authentication protocol can deny the contents of its communications. That is, it cannot deny its involvement in the authentication protocol. In this work, we focus only on deniability in the sense of [16].
 
2
The public parameter size, the secret key size, and communication complexity of our schemes actually have \(\mathsf{poly} (\log n)\) factors. In this paper, however, we ignore them since \(\mathsf{poly} (\log n)\) factors are asymptotically absorbed into \(\mathsf{poly} (\lambda )\) factors, where \(\lambda \) is a security parameter.
 
3
Actually, in our generic construction, we require that the underlying \(\text {IND-CPA}\) secure BE scheme satisfy a subtle additional property called smoothness. As mentioned in Sect. 3.1, many known \(\text {IND-CPA}\) secure BE schemes have smoothness unconditionally and any BE scheme can be easily converted to one satisfying this property (with essentially no overhead).
 
4
This property is called verifiability in the previous work [26].
 
5
Here, in order to share a ring R and a message m between an OBU and an RSU in an anonymous manner, we assume that a specialized anonymous channel has been equipped between them.
 
6
Note that as in plaintext awareness in the RO model for PKE [7], plaintext awareness in the RO model for BE is defined using a universal extractor that works for any PPT adversary \(\mathcal {A}\).
 
7
Actually, this step is never reached since we are assuming that \(\mathcal {A}\) always makes exactly \(Q_{dec}\) decryption queries, and thus \(\mathcal {B}^{\mathsf {pa} }\) will terminate when \(\mathcal {A}\) makes the \(j^*\)-th decryption query with \(j^*\in [Q_{dec}]\).
 
8
In a protocol in which the prover first speaks and a prover instance is invoked for the first time, we only allow \(\mathsf {msg} \) to be an empty string.
 
9
Although we present the deniable ring authentication scheme in the RO model, we explicitly introduce a collision-resistant hash function for simplifying our arguments.
 
10
Looking ahead, since we would like to rely on the plaintext awareness of BE in the RO model for proving concurrent deniability, we consider BE in the RO model here. If we only consider concurrent soundness and source hiding for our construction, an RO is not needed.
 
11
Note that while \(\mathcal {TO}\) just gives \(\mathsf {msg} _2 :=t\) to \(\mathcal {A}\) (without decrypting c) here, this does not affect the view of \(\mathcal {A}\) due to the correctness of \(\mathsf {BE} \).
 
Literature
1.
go back to reference Agrawal S., Yamada S.: Optimal broadcast encryption from pairings and LWE. In: Rijmen V., Ishai Y. (eds.) EUROCRYPT 2020, pp. 13–43. Part I, LNCS. Springer, Heidelberg (2020). Agrawal S., Yamada S.: Optimal broadcast encryption from pairings and LWE. In: Rijmen V., Ishai Y. (eds.) EUROCRYPT 2020, pp. 13–43. Part I, LNCS. Springer, Heidelberg (2020).
2.
go back to reference Agrawal S., Wichs D., Yamada S.: Optimal broadcast encryption from LWE and pairings in the standard model. In: TCC 2020, pp. 149–178. Part I, LNCS. Springer, Heidelberg (2020). Agrawal S., Wichs D., Yamada S.: Optimal broadcast encryption from LWE and pairings in the standard model. In: TCC 2020, pp. 149–178. Part I, LNCS. Springer, Heidelberg (2020).
3.
go back to reference Alekhnovich M.: More on average case vs approximation complexity. In: 44th FOCS, pp. 298–307. IEEE Computer Society Press (2003). Alekhnovich M.: More on average case vs approximation complexity. In: 44th FOCS, pp. 298–307. IEEE Computer Society Press (2003).
4.
go back to reference Baltico C.E., Zaira C., Dario F., Dario G., Gay R.: Practical functional encryption for quadratic functions with applications to predicate encryption. In: Katz J., Shacham H. (eds.) CRYPTO 2017, pp. 67–98. Part I, vol. 10401 of LNCS. Springer, Heidelberg (2017). Baltico C.E., Zaira C., Dario F., Dario G., Gay R.: Practical functional encryption for quadratic functions with applications to predicate encryption. In: Katz J., Shacham H. (eds.) CRYPTO 2017, pp. 67–98. Part I, vol. 10401 of LNCS. Springer, Heidelberg (2017).
5.
go back to reference Bellare M., Palacio A.: Towards plaintext-aware public-key encryption without random oracles. In: Pil J.L. (ed.) ASIACRYPT 2004, vol. 3329 of LNCS, pp. 48–62. Springer, Heidelberg (2004). Bellare M., Palacio A.: Towards plaintext-aware public-key encryption without random oracles. In: Pil J.L. (ed.) ASIACRYPT 2004, vol. 3329 of LNCS, pp. 48–62. Springer, Heidelberg (2004).
6.
go back to reference Bellare M., Rogaway P.: Random oracles are practical: A paradigm for designing efficient protocols. In: Denning D.E., Pyle R., Ganesan R., Sandhu R.S., Ashby V. (eds.) ACM CCS 93, pp. 62–73. ACM Press, (1993). Bellare M., Rogaway P.: Random oracles are practical: A paradigm for designing efficient protocols. In: Denning D.E., Pyle R., Ganesan R., Sandhu R.S., Ashby V. (eds.) ACM CCS 93, pp. 62–73. ACM Press, (1993).
7.
go back to reference Bellare M., Desai A., Pointcheval D., Rogaway P.: Relations among notions of security for public-key encryption schemes. In: Krawczyk H. (ed.) CRYPTO’98, vol. 1462, pp. 26–45. LNCS. Springer, Heidelberg (1998). Bellare M., Desai A., Pointcheval D., Rogaway P.: Relations among notions of security for public-key encryption schemes. In: Krawczyk H. (ed.) CRYPTO’98, vol. 1462, pp. 26–45. LNCS. Springer, Heidelberg (1998).
8.
go back to reference Bellare M., Hofheinz D., Kiltz E.: Subtleties in the definition of IND-CCA: when and how should challenge decryption be disallowed? J. Cryptol. 28(1), 29–48 (2015). MathSciNetCrossRef Bellare M., Hofheinz D., Kiltz E.: Subtleties in the definition of IND-CCA: when and how should challenge decryption be disallowed? J. Cryptol. 28(1), 29–48 (2015). MathSciNetCrossRef
9.
go back to reference Beullens W., Wee H.: Obfuscating simple functionalities from knowledge assumptions. In: PKC 2019, pp. 254–283. Part II, LNCS. Springer, Heidelberg (2019). Beullens W., Wee H.: Obfuscating simple functionalities from knowledge assumptions. In: PKC 2019, pp. 254–283. Part II, LNCS. Springer, Heidelberg (2019).
10.
go back to reference Blum M., Feldman P., Micali S.: Non-interactive zero-knowledge and its applications (extended abstract). In: 20th ACM STOC, pp. 103–112. ACM Press (1988). Blum M., Feldman P., Micali S.: Non-interactive zero-knowledge and its applications (extended abstract). In: 20th ACM STOC, pp. 103–112. ACM Press (1988).
11.
go back to reference Boneh D., Gentry C., Waters B.: Collusion resistant broadcast encryption with short ciphertexts and private keys. In: Shoup V. (ed.) CRYPTO 2005, vol. 3621, pp. 258–275. LNCS. Springer, Heidelberg (2005). Boneh D., Gentry C., Waters B.: Collusion resistant broadcast encryption with short ciphertexts and private keys. In: Shoup V. (ed.) CRYPTO 2005, vol. 3621, pp. 258–275. LNCS. Springer, Heidelberg (2005).
12.
go back to reference Chen J., Gay R., Wee H.: Improved dual system ABE in prime-order groups via predicate encodings. In: Oswald E., Fischlin M. (eds.) In: EUROCRYPT 2015, pp. 595–624. Part II, vol. 9057 of LNCS. Springer, Heidelberg (2015). Chen J., Gay R., Wee H.: Improved dual system ABE in prime-order groups via predicate encodings. In: Oswald E., Fischlin M. (eds.) In: EUROCRYPT 2015, pp. 595–624. Part II, vol. 9057 of LNCS. Springer, Heidelberg (2015).
13.
go back to reference Cramer R., Shoup V.: Universal hash proofs and a paradigm for adaptive chosen ciphertext secure public-key encryption. In Knudsen L.R., (eds.) EUROCRYPT 2002, vol. 2332 of LNCS, pp. 45–64. Springer, Heidelberg (2002). Cramer R., Shoup V.: Universal hash proofs and a paradigm for adaptive chosen ciphertext secure public-key encryption. In Knudsen L.R., (eds.) EUROCRYPT 2002, vol. 2332 of LNCS, pp. 45–64. Springer, Heidelberg (2002).
14.
go back to reference Damgård I.: Towards practical public key systems secure against chosen ciphertext attacks. In: Feigenbaum J. (ed.) CRYPTO’91, vol. 576, pp. 445–456. LNCS. Springer, Heidelberg (1992). Damgård I.: Towards practical public key systems secure against chosen ciphertext attacks. In: Feigenbaum J. (ed.) CRYPTO’91, vol. 576, pp. 445–456. LNCS. Springer, Heidelberg (1992).
15.
go back to reference Di Raimondo M., Gennaro R.: New approaches for deniable authentication. In: Vijayalakshmi A., Catherine M., Ari J. (eds.) In: ACM CCS 2005, pp. 112–121. ACM Press (2005). Di Raimondo M., Gennaro R.: New approaches for deniable authentication. In: Vijayalakshmi A., Catherine M., Ari J. (eds.) In: ACM CCS 2005, pp. 112–121. ACM Press (2005).
16.
go back to reference Di Raimondo M., Gennaro R., Krawczyk H.: Deniable authentication and key exchange. In Ari J., Wright R.N., di Vimercati S.D.C. (eds.) In: ACM CCS 2006, pp. 400–409. ACM Press (2006). Di Raimondo M., Gennaro R., Krawczyk H.: Deniable authentication and key exchange. In Ari J., Wright R.N., di Vimercati S.D.C. (eds.) In: ACM CCS 2006, pp. 400–409. ACM Press (2006).
17.
go back to reference Dolev D., Dwork C., Naor M.: Non-malleable cryptography (extended abstract). In: 23rd ACM STOC, pp. 542–552. ACM Press (1991). Dolev D., Dwork C., Naor M.: Non-malleable cryptography (extended abstract). In: 23rd ACM STOC, pp. 542–552. ACM Press (1991).
18.
go back to reference Dowsley R., Hanaoka G., Imai H., Nascimento A.C.: Round-optimal deniable ring authentication in the presence of big brother. In: Chung Y., Yung M. (eds.) WISA 10, vol. 6513, pp. 307–321. LNCS. Springer, Heidelberg (2011). Dowsley R., Hanaoka G., Imai H., Nascimento A.C.: Round-optimal deniable ring authentication in the presence of big brother. In: Chung Y., Yung M. (eds.) WISA 10, vol. 6513, pp. 307–321. LNCS. Springer, Heidelberg (2011).
19.
go back to reference Dwork C., Naor M., Sahai A.: Concurrent zero-knowledge. In: 30th ACM STOC, pp. 409–418. ACM Press (1998). Dwork C., Naor M., Sahai A.: Concurrent zero-knowledge. In: 30th ACM STOC, pp. 409–418. ACM Press (1998).
20.
go back to reference ElGamal T.: A public key cryptosystem and a signature scheme based on discrete logarithms. In: Blakley G.R., Chaum D (eds.) In: CRYPTO’84 vol. 196 of LNCS, pp. 10–18. Springer, Heidelberg (1984). ElGamal T.: A public key cryptosystem and a signature scheme based on discrete logarithms. In: Blakley G.R., Chaum D (eds.) In: CRYPTO’84 vol. 196 of LNCS, pp. 10–18. Springer, Heidelberg (1984).
21.
go back to reference Escala A., Herold G., Kiltz E., Ràfols C., Villar J.: An algebraic framework for Diffie-Hellman assumptions. In: Canetti R., Garay J.A. (eds.) CRYPTO 2013, pp. 129–147. Part II, vol. 8043 of LNCS. Springer, Heidelberg (2013). Escala A., Herold G., Kiltz E., Ràfols C., Villar J.: An algebraic framework for Diffie-Hellman assumptions. In: Canetti R., Garay J.A. (eds.) CRYPTO 2013, pp. 129–147. Part II, vol. 8043 of LNCS. Springer, Heidelberg (2013).
22.
go back to reference Fiat A., Naor M.: Broadcast encryption. In: Stinson D.R. (ed.) CRYPTO’93, vol. 773, pp. 480–491. LNCS. Springer, Heidelberg (1994). Fiat A., Naor M.: Broadcast encryption. In: Stinson D.R. (ed.) CRYPTO’93, vol. 773, pp. 480–491. LNCS. Springer, Heidelberg (1994).
23.
go back to reference Fujisaki E., Okamoto T.: How to enhance the security of public-key encryption at minimum cost. In: Imai H., Zheng Y. (eds.) PKC’99, vol. 1560, pp. 53–68. LNCS. Springer, Heidelberg (1999). Fujisaki E., Okamoto T.: How to enhance the security of public-key encryption at minimum cost. In: Imai H., Zheng Y. (eds.) PKC’99, vol. 1560, pp. 53–68. LNCS. Springer, Heidelberg (1999).
24.
go back to reference Gay R., Kowalczyk L., Wee H.: Tight adaptively secure broadcast encryption with short ciphertexts and keys. In: Catalano D., De Prisco R. (eds.) SCN 18, vol. 11035, pp. 123–139. LNCS. Springer, Heidelberg (2018). Gay R., Kowalczyk L., Wee H.: Tight adaptively secure broadcast encryption with short ciphertexts and keys. In: Catalano D., De Prisco R. (eds.) SCN 18, vol. 11035, pp. 123–139. LNCS. Springer, Heidelberg (2018).
25.
go back to reference Groth J., Sahai A.: Efficient non-interactive proof systems for bilinear groups. In: Smart N.P. (ed.) EUROCRYPT 2008, vol. 4965, pp. 415–432. LNCS. Springer, Heidelberg (2008). Groth J., Sahai A.: Efficient non-interactive proof systems for bilinear groups. In: Smart N.P. (ed.) EUROCRYPT 2008, vol. 4965, pp. 415–432. LNCS. Springer, Heidelberg (2008).
26.
go back to reference Hanaoka G., Kurosawa K.: Efficient chosen ciphertext secure public key encryption under the computational Diffie-Hellman assumption. In: Pieprzyk J. (ed.) ASIACRYPT 2008, vol. 5350, pp. 308–325. LNCS. Springer, Heidelberg (2008). Hanaoka G., Kurosawa K.: Efficient chosen ciphertext secure public key encryption under the computational Diffie-Hellman assumption. In: Pieprzyk J. (ed.) ASIACRYPT 2008, vol. 5350, pp. 308–325. LNCS. Springer, Heidelberg (2008).
27.
go back to reference Harkins D., Carrel D. (eds.): The Internet Key Exchange (IKE). RFC 2409 (1998). Harkins D., Carrel D. (eds.): The Internet Key Exchange (IKE). RFC 2409 (1998).
28.
go back to reference Katz J.: Efficient and non-malleable proofs of plaintext knowledge and applications. In: Biham E. (ed.) EUROCRYPT 2003, vol. 2656, pp. 211–228. LNCS. Springer, Heidelberg (2003). Katz J.: Efficient and non-malleable proofs of plaintext knowledge and applications. In: Biham E. (ed.) EUROCRYPT 2003, vol. 2656, pp. 211–228. LNCS. Springer, Heidelberg (2003).
29.
go back to reference Naor M.: Deniable ring authentication. In: Yung M. (ed.) CRYPTO 2002, vol. 2442, pp. 481–498. LNCS. Springer, Heidelberg (2002). Naor M.: Deniable ring authentication. In: Yung M. (ed.) CRYPTO 2002, vol. 2442, pp. 481–498. LNCS. Springer, Heidelberg (2002).
31.
go back to reference Pass R.: On deniability in the common reference string and random oracle model. In: Boneh D. (ed.) CRYPTO 2003, vol. 2729, pp. 316–337. LNCS. Springer, Heidelberg (2003). Pass R.: On deniability in the common reference string and random oracle model. In: Boneh D. (ed.) CRYPTO 2003, vol. 2729, pp. 316–337. LNCS. Springer, Heidelberg (2003).
32.
go back to reference Regev O.: On lattices, learning with errors, random linear codes, and cryptography. In: Gabow H.N., Fagin R. (eds.) In: 37th ACM STOC, pp. 84–93. ACM Press (2005). Regev O.: On lattices, learning with errors, random linear codes, and cryptography. In: Gabow H.N., Fagin R. (eds.) In: 37th ACM STOC, pp. 84–93. ACM Press (2005).
33.
go back to reference Susilo W., Mu Y.: Non-interactive deniable ring authentication. In: Lim J.I., Lee D.H. (eds.) ICISC 03, vol. 2971 of LNCS, pp. 386–401. Springer, Heidelberg (2004). Susilo W., Mu Y.: Non-interactive deniable ring authentication. In: Lim J.I., Lee D.H. (eds.) ICISC 03, vol. 2971 of LNCS, pp. 386–401. Springer, Heidelberg (2004).
34.
go back to reference Susilo W., Yi M.: Deniable ring authentication revisited. In: Jakobsson M., Yung M., Zhou J. (eds.) ACNS 04, vol. 3089, pp. 149–163. LNCS. Springer, Heidelberg (2004). Susilo W., Yi M.: Deniable ring authentication revisited. In: Jakobsson M., Yung M., Zhou J. (eds.) ACNS 04, vol. 3089, pp. 149–163. LNCS. Springer, Heidelberg (2004).
35.
go back to reference Yamada S., Attrapadung N., Santoso B., Schuldt J.C.N., Hanaoka G., Kunihiro N.: Verifiable predicate encryption and applications to CCA security and anonymous predicate authentication. In: Fischlin M., Buchmann J., Manulis M. (eds.) PKC 2012, vol. 7293, pp. 243–261. LNCS. Springer, Heidelberg (2012). Yamada S., Attrapadung N., Santoso B., Schuldt J.C.N., Hanaoka G., Kunihiro N.: Verifiable predicate encryption and applications to CCA security and anonymous predicate authentication. In: Fischlin M., Buchmann J., Manulis M. (eds.) PKC 2012, vol. 7293, pp. 243–261. LNCS. Springer, Heidelberg (2012).
36.
go back to reference Zeng S., Chen Y., Tan S., He M.: Concurrently deniable ring authentication and its applications to LBS in VANETs. Peer-to-Peer Netw. Appl. 10(4), 844–856 (2017). CrossRef Zeng S., Chen Y., Tan S., He M.: Concurrently deniable ring authentication and its applications to LBS in VANETs. Peer-to-Peer Netw. Appl. 10(4), 844–856 (2017). CrossRef
37.
go back to reference Zeng S., Mu Y., Yang G., He M.: Deniable ring authentication based on projective hash functions. In: Okamoto T., Yu Y., Au M.H., Yannan L. (eds.) ProvSec 2017, vol. 10592 of LNCS, pp. 127–143. Springer, Heidelberg (2017). Zeng S., Mu Y., Yang G., He M.: Deniable ring authentication based on projective hash functions. In: Okamoto T., Yu Y., Au M.H., Yannan L. (eds.) ProvSec 2017, vol. 10592 of LNCS, pp. 127–143. Springer, Heidelberg (2017).
Metadata
Title
Generic transformation from broadcast encryption to round-optimal deniable ring authentication
Authors
Keisuke Hara
Takahiro Matsuda
Goichiro Hanaoka
Keisuke Tanaka
Publication date
16-01-2022
Publisher
Springer US
Published in
Designs, Codes and Cryptography / Issue 2/2022
Print ISSN: 0925-1022
Electronic ISSN: 1573-7586
DOI
https://doi.org/10.1007/s10623-021-00975-4

Other articles of this Issue 2/2022

Designs, Codes and Cryptography 2/2022 Go to the issue

Premium Partner