access icon free Security of weak secrets based cryptographic primitives via the Rényi entropy

© The Institution of Engineering and Technology
Received 06/05/2014, Accepted 29/11/2015, Revised 18/11/2015, Published 21/06/2016

In ideality, cryptographic primitives take for granted that the secret sources are derived from uniform distribution. However, in reality, we may only obtain some ‘weak’ random sources guaranteed with high unpredictability (e.g. biometric data, physical sources, and secrets with partial leakage). Formally, the security of cryptographic primitives is measured by the expectation of some function, called ‘perfect’ expectation in the ideal model and ‘weak’ expectation in the real model. The authors propose some elementary inequalities which show that the ‘weak’ expectation is not much worse than the ‘perfect’ expectation. The authors present how to overcome weak expectations dependent on the Rényi entropy other than the min and collision entropies by Dodis and Yu [TCC 2013]. The authors achieve these results by capturing on two approaches: one is by observing a new relationship between the collision entropy and other Rényi entropy, the other is by developing the connection between different moments of a variable. Furthermore, pseudorandom generator, and pairwise independent hash function family, the authors extend key derivation functions based on the Rényi entropy. The results are applied to all unpredictability applications and ‘square-friendly’ indistinguishability applications including CPA-secure symmetric-key encryption schemes.

Inspec keywords: private key cryptography

Other keywords: Renyi entropy; secret source; collision entropy; pairwise independent hash function family; universal hash function family; CPA-secure symmetric-key encryption scheme; pseudorandom generator; Holder inequality; extend key derivation function; cryptographic primitive

Subjects: Data security; Cryptography

References

    1. 1)
      • 1. Boyen, X., Dodis, Y., Katz, J., et al: ‘Secure remote authentication using biometric data’. EUROCRYPT, 2005 (LNCS, 3494), pp. 147–163.
    2. 2)
      • 8. Blum, M.: ‘Independent unbiased coin-flips from a correclated biased source-a finite state Markov chain’, Combinatorica, 1986, 6, (2), pp. 97–108.
    3. 3)
      • 27. Maurer, U., Wolf, S.: ‘Privacy amplification secure against active adversaries’. CRYPTO, 1997 (LNCS, 1294), pp. 307–321.
    4. 4)
      • 17. Rényi, A.: ‘On measures of information and entropy’. Proc. of the 4th Berkeley Symp. on Mathematics, Statistics and Probability, 1960, pp. 547–561.
    5. 5)
      • 6. Krawczyk, H.: ‘Cryptographic extraction and key derivation: the HKDF scheme’. CRYPTO, 2010 (LNCS, 6223), pp. 631–648.
    6. 6)
      • 12. Lichtenstein, D., Linial, N., Saks, M.E.: ‘Some extremal problems arising form discrete control processes’, Combinatorica, 1989, 9, (3), pp. 269–287.
    7. 7)
      • 22. Dodis, Y.: ‘Shannon impossibility, revisited’. Proc. of the 6th Int. Conf. on Information Theoretic Security (ICITS 2012) (LNCS, 7412), pp. 100–110.
    8. 8)
      • 14. von Neumann, J.: ‘Various techniques used in connection with random digits’. National Bureau of Standards, Applied Math. Series, 1951, 12, pp. 36–38.
    9. 9)
      • 33. Hsiao, C.Y., Lu, C.J., Reyzin, L.: ‘Conditional computational entropy, or toward separating pseudoentropy from compressibility’. EUROCRYPT, 2007 (LNCS, 4515), pp. 169–186.
    10. 10)
      • 2. Dodis, Y., Ostrovsky, R., Reyzin, L., et al: ‘Fuzzy extractors: How to generate strong keys from biometrics and other noisy data’, SIAM J. Comput., 2008, 38, (1), pp. 97–139.
    11. 11)
      • 3. Barak, B., Halevi, S.: ‘A model and architecture for pseudo-random generation with applications to /dev/random’. Proc. of the 12th ACM Conf. on Computer and Communication Security, 2005, pp. 203–212.
    12. 12)
      • 21. Shannon, C.E.: ‘Communication theory of secrecy systems’, Bell Tech. J., 1949, 28, pp. 656–715.
    13. 13)
      • 20. Iwamoto, M., Shikata, J.: ‘Information theoretic security for encryption based on conditional Rényi entropies’. ICITS, 2013, pp. 103–121.
    14. 14)
      • 5. Gennaro, R., Krawczyk, H., Rabin, T.: ‘Secure hashed diffie-hellman over non-ddh groups’. EUROCRYPT, 2004 (LNCS, 3027), pp. 361–381.
    15. 15)
      • 26. Stinson, D.R.: ‘Universal hashing and authentication codes’, Designs Codes Cryptogr., 1994, 4, (4), pp. 369–380.
    16. 16)
      • 35. Reingold, O., Shaltiel, R., Wigderson, A.: ‘Extracting randomness via repeated condensing’, SIAM J. Comput., 2006, 35, (5), pp. 1185–1209.
    17. 17)
      • 15. Zuckerman, D.: ‘Simulating BPP using a general weak random source’, Algorithmica, 1996, 16, (4/5), pp. 367–391.
    18. 18)
      • 24. Barak, B., Dodis, Y., Krawczyk, H., et al: ‘Leftover hash lemma, revisited’. CRYPTO 2011, 2011, 6841, pp. 1–20.
    19. 19)
      • 16. Dodis, Y., Yu, Y.: ‘Overcoming weak expectations’. TCC, 2013, pp. 1–22.
    20. 20)
      • 30. Naor, M., Reingold, O.: ‘Synthesizers and their application to the parallel construction of pseudo-random functions’, J. Comput. Syst. Sci., 1999, 58, (2), pp. 336–375.
    21. 21)
      • 31. Barak, B., Shaltiel, R., Wigderson, A.: ‘Computational analogues of entropy’. RANDOMAPPROX, 2003 (LNCS, 2764), pp. 200–215.
    22. 22)
      • 34. Raz, R., Reingold, O.: ‘On recycling the randomness of states in space bounded computation’. Proc. 31st SOTC, 1999, pp. 159–168.
    23. 23)
      • 29. Yao, Y.Q., Li, Z.J.: ‘Overcoming weak expectations via the Rényi entropy and the expanded computational entropy’. ICITS, 2013 (LNCS, 8317), 2014, pp. 162–178.
    24. 24)
      • 32. Håstad, J., Impagliazzo, R., Levin, L.A., et al: ‘A pseudorandom generator from any one-way function’, SIAM J. Comput., 1999, 28, (4), pp. 1364–1396.
    25. 25)
      • 11. Dodis, Y.: ‘New imperfect random source with applications to coin-flipping’. ICALP, 2001, pp. 297–309.
    26. 26)
      • 10. Chor, B., Goldreich, O.: ‘Unbiased bits from sources of weak randomness and probabilistic communication complexity’, SIAM J. Comput., 1988, 17, (2), pp. 230–261.
    27. 27)
      • 13. Santha, M., Vazirani, U.V.: ‘Generating quasi-random sequences from semirandom sources’, J. Comput. Syst. Sci., 1986, 33, (1), pp. 75–87.
    28. 28)
      • 23. Alimomeni, M., Safavi-Naini, R.: ‘Guessing secrecy’. Proc. of the 6th Int. Conf. on Information Theoretic Security (ICITS 2012) (LNCS, 7412), pp. 1–13.
    29. 29)
      • 28. Dodis, Y., Katz, J., Reyzin, L., et al: ‘Robust fuzzy extractors and authenticated key agreement from close secrets’. CRYPTO, 2006 (LNCS, 4117), pp. 232–250.
    30. 30)
      • 19. Hayashi, M.: ‘Tight exponential evaluation for universal composablity with privacy amplification and its applications’. Accepted in IEEE Trans. Information Theory (arXiv:1010.1358), 2010.
    31. 31)
      • 4. Barak, B., Shaltiel, R., Tromer, E.: ‘True random number generators secure in a changing environment’. Proc. of the 5th Cryptographic Hardware and Embedded Systems, 2003, pp. 166–180.
    32. 32)
      • 25. Abualrub, M.S., Sulaiman, W.T.: ‘A note on Hölder's inequality’, Int. Math. Forum, 2009, 40, pp. 1993–1995.
    33. 33)
      • 9. Chor, B., Friedman, J., Goldreich, O., et al: ‘The bit extraction problem or t-resilient functions’. Proc. of 26th FOCS, 1985, pp. 396–407.
    34. 34)
      • 18. Hayashi, M.: ‘Exponential decreasing rate of leaked information in universal random privacy amplification’, IEEE Trans. Inf. Theory, 2011, 57, (6), pp. 3989–4001.
    35. 35)
      • 7. Andreev, A.E., Clementi, A.E.F., Rolim, J.D.P., et al: ‘Weak random sources, hitting sets, and BPP simulations’, SIAM J. Comput., 1999, 28, (6), pp. 2103–2116.
http://iet.metastore.ingenta.com/content/journals/10.1049/iet-ifs.2015.0007
Loading

Related content

content/journals/10.1049/iet-ifs.2015.0007
pub_keyword,iet_inspecKeyword,pub_concept
6
6
Loading