Lossy Cryptography from Code-Based Assumptions
Authors: 
Quang Dao, Aayush JainAuthors Info & Claims
Pages 34 - 75
Abstract
Over the past few decades, we have seen a proliferation of advanced cryptographic primitives with lossy or homomorphic properties built from various assumptions such as Quadratic Residuosity, Decisional Diffie-Hellman, and Learning with Errors. These primitives imply hard problems in the complexity class (statistical zero-knowledge); as a consequence, they can only be based on assumptions that are broken in . This poses a barrier for building advanced cryptography from code-based assumptions such as Learning Parity with Noise (LPN), as LPN is only known to be in under an extremely low noise rate , for which it is broken in quasi-polynomial time.
In this work, we propose a new code-based assumption: Dense-Sparse LPN, that falls in the complexity class and is conjectured to be secure against subexponential time adversaries. Our assumption is a variant of LPN that is inspired by McEliece’s cryptosystem and random XOR in average-case complexity. Roughly, the assumption states thatfor a random (dense) matrix , random sparse matrix , and sparse noise vector drawn from the Bernoulli distribution with inverse polynomial noise probability.
We leverage our assumption to build lossy trapdoor functions (Peikert-Waters STOC 08). This gives the first post-quantum alternative to the lattice-based construction in the original paper. Lossy trapdoor functions, being a fundamental cryptographic tool, are known to enable a broad spectrum of both lossy and non-lossy cryptographic primitives; our construction thus implies these primitives in a generic manner. In particular, we achieve collision-resistant hash functions with plausible subexponential security, improving over a prior construction from LPN with noise rate that is only quasi-polynomially secure.
References
[1]
Agrawal S, Boneh D, and Boyen X Gilbert H Efficient lattice (H)IBE in the standard model Advances in Cryptology – EUROCRYPT 2010 2010 Heidelberg Springer 553-572
[2]
Ajtai, M.: Generating hard instances of lattice problems (extended abstract). In: 28th ACM STOC, pp. 99–108. ACM Press (1996)
[3]
Alamati N, De Feo L, Montgomery H, and Patranabis S Moriai S and Wang H Cryptographic group actions and applications Advances in Cryptology – ASIACRYPT 2020 2020 Cham Springer 411-439
[4]
Alamati N, Malavolta G, and Rahimi A Kiltz E and Vaikuntanathan V Candidate trapdoor claw-free functions from group actions with applications to quantum protocols TCC 2022, Part I 2022 Heidelberg Springer 266-293
[5]
Alekhnovich, M.: More on average case vs approximation complexity. In: 44th FOCS, pp. 298–307. IEEE Computer Society Press (2003)
[6]
Applebaum, B.: Pseudorandom generators with long stretch and low locality from random local one-way functions. In: Karloff, H.J., Pitassi, T. (eds.) 44th ACM STOC, pp. 805–816. ACM Press (2012)
[7]
Applebaum B Pseudorandom generators with long stretch and low locality from random local one-way functions SIAM J. Comput. 2013 42 5 2008-2037
[8]
Applebaum, B., Barak, B., Wigderson, A.: Public-key cryptography from different assumptions. In: Schulman, L.J. (ed.) 42nd ACM STOC, pp 171–180. ACM Press (2010)
[9]
Applebaum B, Bogdanov A, and Rosen A Cramer R A Dichotomy for Local Small-Bias Generators Theory of Cryptography 2012 Heidelberg Springer 600-617
[10]
Applebaum B, Damgård I, Ishai Y, Nielsen M, and Zichron L Katz J and Shacham H Secure arithmetic computation with constant computational overhead Advances in Cryptology – CRYPTO 2017 2017 Cham Springer 223-254
[11]
Applebaum, B., Haramaty, N., Ishai, Y., Kushilevitz, E., Vaikuntanathan, V.: Low-complexity cryptographic hash functions. In: Papadimitriou, C.H. (ed.) ITCS 2017, vol. 4266, pp. 7:1–7:31. LIPIcs, 67 (2017)
[12]
Applebaum, B., Kachlon, E.: Sampling graphs without forbidden subgraphs and unbalanced expanders with negligible error. In: Zuckerman, D. (ed.) 60th FOCS, pp. 171–179. IEEE Computer Society Press (2019)
[13]
Applebaum B and Konstantini N Hazay C and Stam M Actively secure arithmetic computation and VOLE with constant computational overhead EUROCRYPT 2023, Part II 2023 Heidelberg Springer 190-219
[14]
Applebaum, B., Lovett, S.: Algebraic attacks against random local functions and their countermeasures. In: Wichs, D., Mansour, Y. (eds.) 48th ACM STOC, pp. 1087–1100. ACM Press (2016)
[15]
Arora S and Ge R Aceto L, Henzinger M, and Sgall J New algorithms for learning in presence of errors Automata, Languages and Programming 2011 Heidelberg Springer 403-415
[16]
Augot D, Finiasz M, and Sendrier N Dawson E and Vaudenay S A new analysis of the McEliece cryptosystem based on QC-LDPC codes Progress in Cryptology – Mycrypt 2005 2005 Heidelberg Springer 64-83
[17]
Baldi M, Bodrato M, and Chiaraluce F Ostrovsky R, De Prisco R, and Visconti I A new analysis of the McEliece cryptosystem based on QC-LDPC codes Security and Cryptography for Networks 2008 Heidelberg Springer 246-262
[18]
Baldi, M., Chiaraluce, F.: Cryptanalysis of a new instance of McEliece cryptosystem based on QC-LDPC codes. In: IEEE International Symposium on Information Theory, ISIT 2007, Nice, France, June 24-29, 2007, pp. 2591–2595. IEEE (2007).
[19]
Bardet M, Chaulet J, Dragoi V, Otmani A, and Tillich J-P Takagi T Cryptanalysis of the McEliece public key cryptosystem based on polar codes Post-Quantum Cryptography 2016 Cham Springer 118-143
[20]
Bellare M et al. Matsui M et al. Hedged public-key encryption: how to protect against bad randomness Advances in Cryptology – ASIACRYPT 2009 2009 Heidelberg Springer 232-249
[21]
Bellare M, Hofheinz D, and Yilek S Joux A Possibility and impossibility results for encryption and commitment secure under selective opening Advances in Cryptology - EUROCRYPT 2009 2009 Heidelberg Springer 1-35
[22]
Berger, T.P., Loidreau, P.: How to mask the structure of codes for a cryptographic use. Des. Codes Cryptogr. 35(1), 63–79 (2005).
[23]
Bernstein, D.J., Lange, T., Peters, C.: Wild McEliece. In: International Workshop on Selected Areas in Cryptography, pp. 143–158. Springer (2010).
[24]
Bernstein DJ, Lange T, and Peters C Yang BY Wild McEliece incognito Post-Quantum Cryptography - 4th International Workshop, PQCrypto 2011 2011 Heidelberg Springer 244-254
[25]
Bernstein DJ, Lange T, Peters C, and Schwabe P Nitaj A and Pointcheval D Really Fast Syndrome-Based Hashing Progress in Cryptology – AFRICACRYPT 2011 2011 Heidelberg Springer 134-152
[26]
Beullens W, Kleinjung T, and Vercauteren F Galbraith SD and Moriai S CSI-FiSh: Efficient Isogeny Based Signatures Through Class Group Computations Advances in Cryptology – ASIACRYPT 2019 2019 Cham Springer 227-247
[27]
Biasse J-F, Micheli G, Persichetti E, and Santini P Nitaj A and Youssef A LESS is More: code-based signatures without syndromes Progress in Cryptology - AFRICACRYPT 2020 2020 Cham Springer 45-65
[28]
Bitansky N and Freizeit S Dodis Y and Shrimpton T Statistically sender-private OT from LPN and derandomization CRYPTO 2022, Part III 2022 Heidelberg Springer 625-653
[29]
Blum A, Furst M, Kearns M, and Lipton RJ Stinson DR Cryptographic primitives based on hard learning problems Advances in Cryptology — CRYPTO’ 93 1994 Heidelberg Springer 278-291
[30]
Blum, A., Kalai, A., Wasserman, H.: Noise-tolerant learning, the parity problem, and the statistical query model. In: 32nd ACM STOC, pp. 435–440. ACM Press (2000)
[31]
Bogdanov, A., Qiao, Y.: On the security of Goldreich’s one-way function. In: Dinur, I., Jansen, K., Naor, J., Rolim, J.D.P. (eds.) Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, 12th International Workshop, APPROX 2009, and 13th International Workshop, RANDOM 2009, Berkeley, CA, USA, August 21-23, 2009. Proceedings. Lecture Notes in Computer Science, vol. 5687, pp. 392–405. Springer (2009).
[32]
Bogdanov A and Qiao Y On the security of Goldreich’s one-way function Comput. Complex. 2012 21 1 83-127
[33]
Boldyreva A, Fehr S, and O’Neill A Wagner D On notions of security for deterministic encryption, and efficient constructions without random oracles Advances in Cryptology – CRYPTO 2008 2008 Heidelberg Springer 335-359
[34]
Bombar M, Couteau G, Couvreur A, and Ducros C Handschuh H and Lysyanskaya A Correlated pseudorandomness from the hardness of quasi-abelian decoding CRYPTO 2023, Part IV 2023 Heidelberg Springer 567-601
[35]
Boyen X and Li Q Katz J and Shacham H All-but-many lossy trapdoor functions from lattices and applications Advances in Cryptology – CRYPTO 2017 2017 Cham Springer 298-331
[36]
Boyle, E., Couteau, G., Gilboa, N., Ishai, Y.: Compressing vector OLE. In: Lie, D., Mannan, M., Backes, M., Wang, X. (eds.) ACM CCS 2018, pp. 896–912. ACM Press (2018)
[37]
Boyle E et al. Dodis Y, Shrimpton T, et al. Correlated pseudorandomness from expand-accumulate codes CRYPTO 2022, Part II 2022 Heidelberg Springer 603-633
[38]
Boyle E et al. Hazay C, Stam M, et al. Oblivious transfer with constant computational overhead EUROCRYPT 2023, Part I 2023 Heidelberg Springer 271-302
[39]
Boyle E, Couteau G, Gilboa N, Ishai Y, Kohl L, and Scholl P Boldyreva A and Micciancio D Efficient pseudorandom correlation generators: silent OT extension and more Advances in Cryptology – CRYPTO 2019 2019 Cham Springer 489-518
[40]
Boyle, E., Couteau, G., Gilboa, N., Ishai, Y., Kohl, L., Scholl, P.: Correlated pseudorandom functions from variable-density LPN. In: 61st FOCS, pp. 1069–1080. IEEE Computer Society Press (2020)
[41]
Boyle E, Couteau G, Gilboa N, Ishai Y, Kohl L, and Scholl P Micciancio D and Ristenpart T Efficient pseudorandom correlation generators from ring-LPN CRYPTO 2020, Part II 2020 Heidelberg Springer 387-416
[42]
Brakerski Z Shacham H and Boldyreva A Quantum FHE (almost) as secure as classical CRYPTO 2018, Part III 2018 Heidelberg Springer 67-95
[43]
Brakerski, Z., Christiano, P., Mahadev, U., Vazirani, U.V., Vidick, T.: A cryptographic test of quantumness and certifiable randomness from a single quantum device. In: Thorup, M. (ed.) 59th FOCS, pp. 320–331. IEEE Computer Society Press (2018)
[44]
Brakerski Z, Lombardi A, Segev G, and Vaikuntanathan V Nielsen JB and Rijmen V Anonymous IBE, leakage resilience and circular security from new assumptions Advances in Cryptology – EUROCRYPT 2018 2018 Cham Springer 535-564
[45]
Brakerski Z, Lyubashevsky V, Vaikuntanathan V, and Wichs D Ishai Y and Rijmen V Worst-case hardness for LPN and cryptographic hashing via code smoothing Advances in Cryptology – EUROCRYPT 2019 2019 Cham Springer 619-635
[46]
Brakerski, Z., Vaikuntanathan, V.: Efficient fully homomorphic encryption from (standard) LWE. In: Ostrovsky, R. (ed.) 52nd FOCS, pp. 97–106. IEEE Computer Society Press (2011)
[47]
Brassard G and Yung M Menezes AJ and Vanstone SA One-way group actions Advances in Cryptology-CRYPT0’ 90 1991 Heidelberg Springer 94-107
[48]
Braverman, M., Hassidim, A., Kalai, Y.T.: Leaky pseudo-entropy functions. In: Chazelle, B. (ed.) Innovations in Computer Science - ICS 2011, Tsinghua University, Beijing, China, January 7-9, 2011. Proceedings, pp. 353–366. Tsinghua University Press (2011). http://conference.iiis.tsinghua.edu.cn/ICS2011/content/papers/17.html
[49]
Castryck, W., Decru, T.: An efficient key recovery attack on SIDH. In: Hazay, C., Stam, M. (eds.) EUROCRYPT 2023, Part V. LNCS, vol. 14008, pp. 423–447. Springer, Heidelberg (2023).
[50]
Castryck W, Lange T, Martindale C, Panny L, and Renes J Peyrin T and Galbraith S CSIDH: an efficient post-quantum commutative group action Advances in Cryptology – ASIACRYPT 2018 2018 Cham Springer 395-427
[51]
Chakraborty S, Prabhakaran M, and Wichs D Kiayias A, Kohlweiss M, Wallden P, and Zikas V Witness maps and applications Public-Key Cryptography – PKC 2020 2020 Cham Springer 220-246
[52]
Cho C, Döttling N, Garg S, Gupta D, Miao P, and Polychroniadou A Katz J and Shacham H Laconic oblivious transfer and its applications Advances in Cryptology – CRYPTO 2017 2017 Cham Springer 33-65
[53]
Chor, B., Goldreich, O., Kushilevitz, E., Sudan, M.: Private information retrieval. In: 36th FOCS, pp. 41–50. IEEE Computer Society Press (1995)
[54]
Choudhuri, A.R., Jain, A., Jin, Z.: SNARGs for from LWE. In: 62nd FOCS, pp. 68–79. IEEE Computer Society Press (2022)
[55]
Cook J, Etesami O, Miller R, and Trevisan L Reingold O Goldreich’s one-way function candidate and myopic backtracking algorithms TCC 2009 2009 Heidelberg Springer 521-538
[56]
Cormen, T.H., Leiserson, C.E., Rivest, R.L., Stein, C.: Introduction to algorithms. MIT press (2022)
[57]
Couteau G and Ducros C Boldyreva A and Kolesnikov V Pseudorandom correlation functions from variable-density LPN, revisited PKC 2023, Part II 2023 Heidelberg Springer 221-250
[58]
Couteau G, Dupin A, Méaux P, Rossi M, and Rotella Y Peyrin T and Galbraith S On the concrete security of Goldreich’s pseudorandom generator ASIACRYPT 2018, Part II 2018 Heidelberg Springer 96-124
[59]
Couteau G, Rindal P, and Raghuraman S Malkin T and Peikert C Silver: silent VOLE and oblivious transfer from hardness of decoding structured LDPC codes Advances in Cryptology – CRYPTO 2021: 41st Annual International Cryptology Conference, CRYPTO 2021, Virtual Event, August 16–20, 2021, Proceedings, Part III 2021 Cham Springer International Publishing 502-534
[60]
Couveignes, J.M.: Hard homogeneous spaces. Cryptology ePrint Archive, Report 2006/291 (2006). https://eprint.iacr.org/2006/291
[61]
Couvreur A, Otmani A, and Tillich JP Nguyen PQ and Oswald E Polynomial time attack on wild McEliece over quadratic extensions Advances in Cryptology – EUROCRYPT 2014 2014 Heidelberg Springer 17-39
[62]
Cramer R and Shoup V Knudsen LR Universal hash proofs and a paradigm for adaptive chosen ciphertext secure public-key encryption Advances in Cryptology — EUROCRYPT 2002 2002 Heidelberg Springer 45-64
[63]
Cryan, M., Miltersen, P.B.: On pseudorandom generators in NC. In: Sgall, J., Pultr, A., Kolman, P. (eds.) Mathematical Foundations of Computer Science 2001, 26th International Symposium, MFCS 2001 Marianske Lazne, Czech Republic, August 27-31, 2001, Proceedings. Lecture Notes in Computer Science, vol. 2136, pp. 272–284. Springer (2001).
[64]
Dao Q, Ishai Y, Jain A, and Lin H Handschuh H and Lysyanskaya A Multi-party homomorphic secret sharing and sublinear MPC from sparse LPN CRYPTO 2023, Part II 2023 Heidelberg Springer 315-348
[65]
Dodis Y, Vaikuntanathan V, and Wichs D Canteaut A and Ishai Y Extracting randomness from extractor-dependent sources Advances in Cryptology – EUROCRYPT 2020 2020 Cham Springer 313-342
[66]
Döttling N, Garg S, Hajiabadi M, Masny D, and Wichs D Canteaut A and Ishai Y Two-round oblivious transfer from CDH or LPN Advances in Cryptology – EUROCRYPT 2020 2020 Cham Springer 768-797
[67]
Döttling N, Müller-Quade J, and Nascimento ACA Wang X and Sako K IND-CCA secure cryptography based on a variant of the LPN problem Advances in Cryptology – ASIACRYPT 2012 2012 Heidelberg Springer 485-503
[68]
Esser A, Kübler R, and May A Katz J and Shacham H LPN decoded Advances in Cryptology – CRYPTO 2017 2017 Cham Springer 486-514
[69]
Feige, U.: Relations between average case complexity and approximation complexity. In: 34th ACM STOC, pp. 534–543. ACM Press (2002)
[70]
Feige, U., Kim, J.H., Ofek, E.: Witnesses for non-satisfiability of dense random 3CNF formulas. In: 47th FOCS, pp. 497–508. IEEE Computer Society Press (2006)
[71]
Finiasz, M., Gaborit, P., Sendrier, N.: Improved fast syndrome based cryptographic hash functions. In: Proceedings of ECRYPT Hash Workshop, vol. 2007, p. 155. Citeseer (2007)
[72]
Fischlin M and Rohrbach F Rothblum GN and Wee H Searching for ELFs in the cryptographic forest TCC 2023, Part III 2023 Heidelberg Springer 207-236
[73]
Garg A, Kalai YT, and Khurana D Canteaut A and Ishai Y Low error efficient computational extractors in the CRS model Advances in Cryptology – EUROCRYPT 2020 2020 Cham Springer 373-402
[74]
Gentry, C.: Fully homomorphic encryption using ideal lattices. In: Mitzenmacher, M. (ed.) 41st ACM STOC, pp. 169–178. ACM Press (2009)
[75]
Gentry, C., Peikert, C., Vaikuntanathan, V.: Trapdoors for hard lattices and new cryptographic constructions. In: Ladner, R.E., Dwork, C. (eds.) 40th ACM STOC, pp. 197–206. ACM Press (2008)
[76]
Gentry C, Sahai A, and Waters B Canetti R and Garay JA Homomorphic encryption from learning with errors: conceptually-simpler, asymptotically-faster, attribute-based Advances in Cryptology – CRYPTO 2013 2013 Heidelberg Springer 75-92
[77]
Girault M Seberry J and Pieprzyk J A (non-practical) three-pass identification protocol using coding theory Advances in Cryptology — AUSCRYPT ’90 1990 Heidelberg Springer 265-272
[78]
Goldreich, O.: Candidate one-way functions based on expander graphs. Electron. Colloquium Comput. Complexity (ECCC) 7(90) (2000).
[79]
Goldreich, O.: Candidate one-way functions based on expander graphs. In: Studies in Complexity and Cryptography. Miscellanea on the Interplay between Randomness and Computation, Collaboration with Avigad, L., et al., pp. 76–87 (2011)
[80]
Goldreich, O., Goldwasser, S., Halevi, S.: Collision-free hashing from lattice problems. In: Goldreich, O. (ed.) Studies in Complexity and Cryptography. Miscellanea on the Interplay between Randomness and Computation - In Collaboration with Lidor Avigad, et al., Lecture Notes in Computer Science, vol. 6650, pp. 30–39. Springer (2011).
[81]
Gorbunov, S., Vaikuntanathan, V., Wee, H.: Attribute-based encryption for circuits. In: Boneh, D., Roughgarden, T., Feigenbaum, J. (eds.) 45th ACM STOC, pp. 545–554. ACM Press (2013)
[82]
Gorbunov S, Vaikuntanathan V, and Wee H Gennaro R and Robshaw M Predicate encryption for circuits from LWE Advances in Cryptology – CRYPTO 2015 2015 Heidelberg Springer 503-523
[83]
Goyal, R., Koppula, V., Waters, B.: Lockable obfuscation. In: Umans, C. (ed.) 58th FOCS, pp. 612–621. IEEE Computer Society Press (2017)
[84]
Goyal, R., Koppula, V., Waters, B.: Collusion resistant traitor tracing from learning with errors. In: Diakonikolas, I., Kempe, D., Henzinger, M. (eds.) 50th ACM STOC, pp. 660–670. ACM Press (2018)
[85]
Guruswami, V., Kothari, P.K., Manohar, P.: Algorithms and certificates for Boolean CSP refutation: smoothed is no harder than random. In: Proceedings of the 54th Annual ACM SIGACT Symposium on Theory of Computing, pp. 678–689 (2022)
[86]
Guruswami, V., Rudra, A., Sudan, M.: Essential coding theory. Draft http://www.cse.buffalo.edu/atri/courses/coding-theory/book2(1) (2012)
[87]
Halevi S and Kalai YT Smooth projective hashing and two-message oblivious transfer J. Cryptol. 2012 25 1 158-193
[88]
Hemenway B, Libert B, Ostrovsky R, and Vergnaud D Lee DH and Wang X Lossy Encryption: constructions from general assumptions and efficient selective opening chosen ciphertext security Advances in Cryptology – ASIACRYPT 2011 2011 Heidelberg Springer 70-88
[89]
Hoffstein J, Pipher J, and Silverman JH Buhler JP NTRU: a ring-based public key cryptosystem Algorithmic Number Theory 1998 Heidelberg Springer 267-288
[90]
Hofheinz D Pointcheval D and Johansson T All-but-many lossy trapdoor functions Advances in Cryptology – EUROCRYPT 2012 2012 Heidelberg Springer 209-227
[91]
Holenstein T and Renner R Shoup V One-way secret-key agreement and applications to circuit polarization and immunization of public-key encryption Advances in Cryptology – CRYPTO 2005 2005 Heidelberg Springer 478-493
[92]
Hooshmand, R., Shooshtari, M.K., Eghlidos, T., Aref, M.R.: Reducing the key length of McEliece cryptosystem using polar codes. In: 2014 11th International ISC Conference on Information Security and Cryptology, pp. 104–108 (2014)
[93]
Hsieh, J.T., Kothari, P.K., Mohanty, S.: A simple and sharper proof of the hypergraph Moore bound. In: Proceedings of the 2023 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 2324–2344. SIAM (2023)
[94]
Impagliazzo, R.: A personal view of average-case complexity. In: Proceedings of Structure in Complexity Theory. Tenth Annual IEEE Conference, pp. 134–147. IEEE (1995)
[95]
Ishai, Y., Kushilevitz, E., Ostrovsky, R., Sahai, A.: Cryptography with constant computational overhead. In: Ladner, R.E., Dwork, C. (eds.) 40th ACM STOC, pp. 433–442. ACM Press (2008)
[96]
Jabri, A.A.: A statistical decoding algorithm for general linear block codes. In: Cryptography and Coding: 8th IMA International Conference Cirencester, UK, December 17–19, 2001 Proceedings, vol. 8, pp. 1–8. Springer (2001)
[97]
Jain, A., Lin, H., Sahai, A.: Indistinguishability obfuscation from well-founded assumptions. In: Khuller, S., Williams, V.V. (eds.) 53rd ACM STOC, pp. 60–73. ACM Press (2021)
[98]
Jain A, Lin H, and Sahai A Dunkelman O and Dziembowski S Indistinguishability obfuscation from LPN over , DLIN, and PRGs in EUROCRYPT 2022, Part I 2022 Heidelberg Springer 670-699
[99]
Janwa H and Moreno O Mceliece public key cryptosystems using algebraic-geometric codes Des. Codes Crypt. 1996 8 3 293-307
[100]
Justesen J Class of constructive asymptotically good algebraic codes IEEE Trans. Inf. Theory 1972 18 5 652-656
[101]
Kiltz E, Masny D, and Pietrzak K Krawczyk H Simple chosen-ciphertext security from low-noise LPN Public-Key Cryptography – PKC 2014 2014 Heidelberg Springer 1-18
[102]
Kiltz E, O’Neill A, and Smith A Rabin T Instantiability of RSA-OAEP under chosen-plaintext attack Advances in Cryptology – CRYPTO 2010 2010 Heidelberg Springer 295-313
[103]
Kothari, P.K., Mori, R., O’Donnell, R., Witmer, D.: Sum of squares lower bounds for refuting any CSP. In: Hatami, H., McKenzie, P., King, V. (eds.) 49th ACM STOC, pp. 132–145. ACM Press (2017)
[104]
Kushilevitz, E., Ostrovsky, R.: Replication is NOT needed: SINGLE database, computationally-private information retrieval. In: 38th FOCS, pp. 364–373. IEEE Computer Society Press (1997)
[105]
Landais G and Tillich J-P Gaborit P An efficient attack of a McEliece cryptosystem variant based on convolutional codes Post-Quantum Cryptography 2013 Heidelberg Springer 102-117
[106]
Libert, B., Nguyen, K., Passelègue, A.: Cumulatively all-lossy-but-one trapdoor functions from standard assumptions. Cryptology ePrint Archive, Report 2022/1229 (2022). https://eprint.iacr.org/2022/1229
[107]
Libert B, Sakzad A, Stehlé D, and Steinfeld R Katz J and Shacham H All-but-many lossy trapdoor functions and selective opening chosen-ciphertext security from LWE Advances in Cryptology – CRYPTO 2017 2017 Cham Springer 332-364
[108]
Lin, W.K., Mook, E., Wichs, D.: Doubly efficient private information retrieval and fully homomorphic RAM computation from ring LWE. In: Saha, B., Servedio, R.A. (eds.) 55th ACM STOC, pp. 595–608. ACM Press (2023)
[109]
Löndahl C and Johansson T Chim TW and Yuen TH A new version of McEliece PKC based on convolutional codes Information and Communications Security 2012 Heidelberg Springer 461-470
[110]
Lou, P., Sahai, A., Sivashankar, V.: Relinearization Attack On LPN over large fields. Comput. J. bxad070 (2023).
[111]
Lyubashevsky V, Micciancio D, Peikert C, and Rosen A Nyberg K SWIFFT: a modest proposal for FFT hashing Fast Software Encryption 2008 Heidelberg Springer 54-72
[112]
Lyubashevsky V, Peikert C, and Regev O Gilbert H On ideal lattices and learning with errors over rings Advances in Cryptology – EUROCRYPT 2010 2010 Heidelberg Springer 1-23
[113]
Mahadev, U.: Classical homomorphic encryption for quantum circuits. In: Thorup, M. (ed.) 59th FOCS, pp. 332–338. IEEE Computer Society Press (2018)
[114]
Mahadev, U.: Classical verification of quantum computations. In: Thorup, M. (ed.) 59th FOCS, pp. 259–267. IEEE Computer Society Press (2018)
[115]
Maino, L., Martindale, C., Panny, L., Pope, G., Wesolowski, B.: A direct key recovery attack on SIDH. In: Hazay, C., Stam, M. (eds.) EUROCRYPT 2023, Part V. LNCS, vol. 14008, pp. 448–471. Springer, Heidelberg (2023).
[116]
Malavolta, G.: Personal communication. Email to the author (2024)
[117]
McEliece, R.J.: A public-key cryptosystem based on algebraic coding theory. The deep space network progress report 42-44, Jet Propulsion Laboratory, California Institute of Technology (1978). https://ipnpr.jpl.nasa.gov/progress_report2/42-44/44N.PDF
[118]
Menezes, A., Vanstone, S.A., Okamoto, T.: Reducing elliptic curve logarithms to logarithms in a finite field. In: 23rd ACM STOC, pp. 80–89. ACM Press (1991)
[119]
Micciancio D and Peikert C Pointcheval D and Johansson T Trapdoors for lattices: simpler, tighter, faster, smaller Advances in Cryptology – EUROCRYPT 2012 2012 Heidelberg Springer 700-718
[120]
Minder L and Shokrollahi A Naor M Cryptanalysis of the sidelnikov cryptosystem Advances in Cryptology - EUROCRYPT 2007 2007 Heidelberg Springer 347-360
[121]
Misoczki, R., Tillich, J.P., Sendrier, N., Barreto, P.S.L.M.: MDPC-McEliece: new McEliece variants from moderate density parity-check codes. Cryptology ePrint Archive, Report 2012/409 (2012). https://eprint.iacr.org/2012/409
[122]
Moran T and Wichs D Micciancio D and Ristenpart T Incompressible encodings Advances in Cryptology – CRYPTO 2020 2020 Cham Springer 494-523
[123]
Mossel, E., Shpilka, A., Trevisan, L.: On e-biased generators in NC0. In: 44th FOCS, pp. 136–145. IEEE Computer Society Press (2003)
[124]
Naor, M., Pinkas, B.: Efficient oblivious transfer protocols. In: Kosaraju, S.R. (ed.) 12th SODA, pp. 448–457. ACM-SIAM (2001)
[125]
Niederreiter H Knapsack-type cryptosystems and algebraic coding theory Problems Control Inf. Theory 1986 15 2 159-166
[126]
O’Donnell, R., Witmer, D.: Goldreich’s PRG: evidence for near-optimal polynomial stretch. In: IEEE 29th Conference on Computational Complexity, CCC 2014, Vancouver, BC, Canada, June 11-13, 2014, pp. 1–12. IEEE Computer Society (2014).
[127]
Ong H, Schnorr CP, and Shamir A Blakley GR and Chaum D Efficient signature schemes based on polynomial equations CRYPTO’84 1984 Heidelberg Springer 37-46
[128]
Otmani A, Tillich JP, and Dallot L Cryptanalysis of two McEliece cryptosystems based on quasi-cyclic codes Math. Comput. Sci. 2010 3 129-140
[129]
Peikert C and Shiehian S Boldyreva A and Micciancio D Noninteractive zero knowledge for NP from (Plain) learning with errors Advances in Cryptology – CRYPTO 2019 2019 Cham Springer 89-114
[130]
Peikert C, Vaikuntanathan V, and Waters B Wagner D A framework for efficient and composable oblivious transfer Advances in Cryptology – CRYPTO 2008 2008 Heidelberg Springer 554-571
[131]
Peikert, C., Waters, B.: Lossy trapdoor functions and their applications. In: Ladner, R.E., Dwork, C. (eds.) 40th ACM STOC, pp. 187–196. ACM Press (2008)
[132]
Petrank E and Roth R Is code equivalence easy to decide? IEEE Trans. Inf. Theory 1997 43 5 1602-1604
[133]
Pietrzak K, Rosen A, and Segev G Cramer R Lossy functions do not amplify well Theory of Cryptography 2012 Heidelberg Springer 458-475
[134]
Prange E The use of information sets in decoding cyclic codes IRE Trans. Inf. Theory 1962 8 5 5-9
[135]
Raghuraman S, Rindal P, and Tanguy T Handschuh H and Lysyanskaya A Expand-convolute codes for pseudorandom correlation generators from LPN CRYPTO 2023, Part IV 2023 Heidelberg Springer 602-632
[136]
Regev, O.: On lattices, learning with errors, random linear codes, and cryptography. In: Gabow, H.N., Fagin, R. (eds.) 37th ACM STOC, pp. 84–93. ACM Press (2005)
[137]
Robert, D.: Breaking SIDH in polynomial time. In: Hazay, C., Stam, M. (eds.) EUROCRYPT 2023, Part V. LNCS, vol. 14008, pp. 472–503. Springer, Heidelberg (2023)
[138]
Rostovtsev, A., Stolbunov, A.: Public-key cryptosystem based on isogenies. Cryptology ePrint Archive, Report 2006/145 (2006). https://eprint.iacr.org/2006/145
[139]
Sahai, A., Vadhan, S.P.: A complete promise problem for statistical zero-knowledge. In: 38th FOCS, pp. 448–457. IEEE Computer Society Press (1997)
[140]
Shrestha, S.R., Kim, Y.S.: New McEliece cryptosystem based on polar codes as a candidate for post-quantum cryptography. In: 2014 14th International Symposium on Communications and Information Technologies (ISCIT), pp. 368–372 (2014)
[141]
SIDELNIKOV, V.M., SHESTAKOV, S.O.: On insecurity of cryptosystems based on generalized reed-solomon codes. Discrete Math. Appl. 2(4), 439–444 (1992).
[142]
Sidelnikov, V.M.: A public-key cryptosystem based on binary reed-muller codes. Discrete Math. Appl. (1994)
[143]
Wichs, D., Zirdelis, G.: Obfuscating compute-and-compare programs under LWE. In: Umans, C. (ed.) 58th FOCS, pp. 600–611. IEEE Computer Society Press (2017)
[144]
Wieschebrink C Sendrier N Cryptanalysis of the niederreiter public key scheme based on GRS subcodes The Third International Workshop on Post-Quantum Cryptography, PQCRYPTO 2010 2010 Heidelberg Springer 61-72
[145]
Yu Yu and Zhang J Robshaw M and Katz J Cryptography with auxiliary input and trapdoor from constant-noise LPN Advances in Cryptology – CRYPTO 2016 2016 Heidelberg Springer 214-243
[146]
Yu Yu, Zhang J, Weng J, Guo C, and Li X Galbraith SD and Moriai S Collision resistant hashing from sub-exponential learning parity with noise Advances in Cryptology – ASIACRYPT 2019 2019 Cham Springer 3-24
[147]
Zhandry M Robshaw M and Katz J The magic of ELFs Advances in Cryptology – CRYPTO 2016 2016 Heidelberg Springer 479-508
[148]
Zhandry M Dodis Y and Shrimpton T New constructions of collapsing hashes CRYPTO 2022, Part III 2022 Heidelberg Springer 596-624
Index Terms
- Lossy Cryptography from Code-Based Assumptions
Index terms have been assigned to the content through auto-classification.
Recommendations
Leakage-Resilient Cryptography from Minimal Assumptions
We present new constructions of leakage-resilient cryptosystems, which remain provably secure even if the attacker learns some arbitrary partial information about their internal secret-key. For any polynomial $$\ell $$ℓ, we can instantiate these schemes ...
Leakage-resilient identity-based cryptography from minimal assumptions
AbstractIdentity-based hash proof system (IB-HPS), a variant of hash proof system (HPS) in the identity-based setting, is a useful building block in cryptography. In EUROCRYPT 2010 (Alwen et al in Advances in cryptology-EUROCRYPT 2010, volume 6110 of LNCS,...
Identity-Based signcryption from identity-based cryptography
WISA'11: Proceedings of the 12th international conference on Information Security ApplicationsA signcryption scheme encrypts and signs data in a single operation which is more efficient than using an encryption scheme combined with a signature scheme. Identity-based cryptography (IBC) does not require users to pre-compute key pairs and obtain ...
Comments
Please enable JavaScript to view thecomments powered by Disqus.Information & Contributors
Information
Published In
Aug 2024
509 pages
© International Association for Cryptologic Research 2024.
Publisher
Springer-Verlag
Berlin, Heidelberg
Publication History
Published: 18 August 2024
Qualifiers
- Article
Contributors
Other Metrics
Bibliometrics & Citations
Bibliometrics
Article Metrics
- 0Total Citations
- 0Total Downloads
- Downloads (Last 12 months)0
- Downloads (Last 6 weeks)0
Reflects downloads up to 17 Nov 2024
Other Metrics
Citations
View Options
View options
Login options
Check if you have access through your login credentials or your institution to get full access on this article.
Sign in