[{"doi":"10.1007/978-3-030-45374-9_8","day":"29","abstract":[{"text":"We introduce the notion of Witness Maps as a cryptographic notion of a proof system. A Unique Witness Map (UWM) deterministically maps all witnesses for an   NP  statement to a single representative witness, resulting in a computationally sound, deterministic-prover, non-interactive witness independent proof system. A relaxation of UWM, called Compact Witness Map (CWM), maps all the witnesses to a small number of witnesses, resulting in a “lossy” deterministic-prover, non-interactive proof-system. We also define a Dual Mode Witness Map (DMWM) which adds an “extractable” mode to a CWM.\r\nOur main construction is a DMWM for all   NP  relations, assuming sub-exponentially secure indistinguishability obfuscation (  iO ), along with standard cryptographic assumptions. The DMWM construction relies on a CWM and a new primitive called Cumulative All-Lossy-But-One Trapdoor Functions (C-ALBO-TDF), both of which are in turn instantiated based on   iO  and other primitives. Our instantiation of a CWM is in fact a UWM; in turn, we show that a UWM implies Witness Encryption. Along the way to constructing UWM and C-ALBO-TDF, we also construct, from standard assumptions, Puncturable Digital Signatures and a new primitive called Cumulative Lossy Trapdoor Functions (C-LTDF). The former improves up on a construction of Bellare et al. (Eurocrypt 2016), who relied on sub-exponentially secure   iO  and sub-exponentially secure OWF.\r\nAs an application of our constructions, we show how to use a DMWM to construct the first leakage and tamper-resilient signatures with a deterministic signer, thereby solving a decade old open problem posed by Katz and Vaikunthanathan (Asiacrypt 2009), by Boyle, Segev and Wichs (Eurocrypt 2011), as well as by Faonio and Venturi (Asiacrypt 2016). Our construction achieves the optimal leakage rate of   1−o(1) .","lang":"eng"}],"date_updated":"2023-09-05T15:10:02Z","year":"2020","citation":{"ama":"Chakraborty S, Prabhakaran M, Wichs D. Witness maps and applications. In: Kiayias A, ed. <i>Public-Key Cryptography</i>. Vol 12110. LNCS. Cham: Springer Nature; 2020:220-246. doi:<a href=\"https://doi.org/10.1007/978-3-030-45374-9_8\">10.1007/978-3-030-45374-9_8</a>","apa":"Chakraborty, S., Prabhakaran, M., &#38; Wichs, D. (2020). Witness maps and applications. In A. Kiayias (Ed.), <i>Public-Key Cryptography</i> (Vol. 12110, pp. 220–246). Cham: Springer Nature. <a href=\"https://doi.org/10.1007/978-3-030-45374-9_8\">https://doi.org/10.1007/978-3-030-45374-9_8</a>","ieee":"S. Chakraborty, M. Prabhakaran, and D. Wichs, “Witness maps and applications,” in <i>Public-Key Cryptography</i>, vol. 12110, A. Kiayias, Ed. Cham: Springer Nature, 2020, pp. 220–246.","chicago":"Chakraborty, Suvradip, Manoj Prabhakaran, and Daniel Wichs. “Witness Maps and Applications.” In <i>Public-Key Cryptography</i>, edited by A Kiayias, 12110:220–46. LNCS. Cham: Springer Nature, 2020. <a href=\"https://doi.org/10.1007/978-3-030-45374-9_8\">https://doi.org/10.1007/978-3-030-45374-9_8</a>.","short":"S. Chakraborty, M. Prabhakaran, D. Wichs, in:, A. Kiayias (Ed.), Public-Key Cryptography, Springer Nature, Cham, 2020, pp. 220–246.","mla":"Chakraborty, Suvradip, et al. “Witness Maps and Applications.” <i>Public-Key Cryptography</i>, edited by A Kiayias, vol. 12110, Springer Nature, 2020, pp. 220–46, doi:<a href=\"https://doi.org/10.1007/978-3-030-45374-9_8\">10.1007/978-3-030-45374-9_8</a>.","ista":"Chakraborty S, Prabhakaran M, Wichs D. 2020.Witness maps and applications. In: Public-Key Cryptography. vol. 12110, 220–246."},"volume":12110,"acknowledgement":"We would like to thank the anonymous reviewers of PKC 2019 for their useful comments and suggestions. We thank Omer Paneth for pointing out to us the connection between Unique Witness Maps (UWM) and Witness encryption (WE). The first author would like to acknowledge Pandu Rangan for his involvement during the initial discussion phase of the project.","publication_status":"published","date_created":"2022-03-18T11:35:51Z","article_processing_charge":"No","title":"Witness maps and applications","intvolume":"     12110","_id":"10865","scopus_import":"1","author":[{"id":"B9CD0494-D033-11E9-B219-A439E6697425","full_name":"Chakraborty, Suvradip","first_name":"Suvradip","last_name":"Chakraborty"},{"last_name":"Prabhakaran","first_name":"Manoj","full_name":"Prabhakaran, Manoj"},{"full_name":"Wichs, Daniel","first_name":"Daniel","last_name":"Wichs"}],"publisher":"Springer Nature","editor":[{"last_name":"Kiayias","first_name":"A","full_name":"Kiayias, A"}],"page":"220-246","quality_controlled":"1","series_title":"LNCS","publication_identifier":{"isbn":["9783030453732","9783030453749"],"eissn":["1611-3349"],"issn":["0302-9743"]},"oa":1,"date_published":"2020-04-29T00:00:00Z","type":"book_chapter","place":"Cham","main_file_link":[{"url":"https://eprint.iacr.org/2020/090","open_access":"1"}],"status":"public","user_id":"c635000d-4b10-11ee-a964-aac5a93f6ac1","oa_version":"Preprint","month":"04","publication":"Public-Key Cryptography","language":[{"iso":"eng"}]},{"conference":{"location":"Edinburgh, United Kingdom","end_date":"2020-05-07","start_date":"2020-05-04","name":"PKC: Public-Key Cryptography"},"language":[{"iso":"eng"}],"oa_version":"Preprint","project":[{"grant_number":"682815","name":"Teaching Old Crypto New Tricks","_id":"258AA5B2-B435-11E9-9278-68D0E5697425","call_identifier":"H2020"}],"month":"05","publication":"23rd IACR International Conference on the Practice and Theory of Public-Key Cryptography","main_file_link":[{"url":"https://eprint.iacr.org/2020/337","open_access":"1"}],"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","status":"public","publication_identifier":{"isbn":["9783030453732"],"eissn":["16113349"],"issn":["03029743"]},"oa":1,"date_published":"2020-05-15T00:00:00Z","type":"conference","publisher":"Springer Nature","page":"623-651","quality_controlled":"1","ec_funded":1,"publication_status":"published","date_created":"2020-09-06T22:01:13Z","department":[{"_id":"KrPi"}],"article_processing_charge":"No","title":"Improved discrete Gaussian and subgaussian analysis for lattice cryptography","alternative_title":["LNCS"],"intvolume":"     12110","_id":"8339","scopus_import":"1","author":[{"full_name":"Genise, Nicholas","first_name":"Nicholas","last_name":"Genise"},{"full_name":"Micciancio, Daniele","first_name":"Daniele","last_name":"Micciancio"},{"full_name":"Peikert, Chris","first_name":"Chris","last_name":"Peikert"},{"full_name":"Walter, Michael","orcid":"0000-0003-3186-2482","last_name":"Walter","first_name":"Michael","id":"488F98B0-F248-11E8-B48F-1D18A9856A87"}],"volume":12110,"doi":"10.1007/978-3-030-45374-9_21","day":"15","abstract":[{"lang":"eng","text":"Discrete Gaussian distributions over lattices are central to lattice-based cryptography, and to the computational and mathematical aspects of lattices more broadly. The literature contains a wealth of useful theorems about the behavior of discrete Gaussians under convolutions and related operations. Yet despite their structural similarities, most of these theorems are formally incomparable, and their proofs tend to be monolithic and written nearly “from scratch,” making them unnecessarily hard to verify, understand, and extend.\r\nIn this work we present a modular framework for analyzing linear operations on discrete Gaussian distributions. The framework abstracts away the particulars of Gaussians, and usually reduces proofs to the choice of appropriate linear transformations and elementary linear algebra. To showcase the approach, we establish several general properties of discrete Gaussians, and show how to obtain all prior convolution theorems (along with some new ones) as straightforward corollaries. As another application, we describe a self-reduction for Learning With Errors (LWE) that uses a fixed number of samples to generate an unlimited number of additional ones (having somewhat larger error). The distinguishing features of our reduction are its simple analysis in our framework, and its exclusive use of discrete Gaussians without any loss in parameters relative to a prior mixed discrete-and-continuous approach.\r\nAs a contribution of independent interest, for subgaussian random matrices we prove a singular value concentration bound with explicitly stated constants, and we give tighter heuristics for specific distributions that are commonly used for generating lattice trapdoors. These bounds yield improvements in the concrete bit-security estimates for trapdoor lattice cryptosystems."}],"date_updated":"2023-02-23T13:31:06Z","citation":{"apa":"Genise, N., Micciancio, D., Peikert, C., &#38; Walter, M. (2020). Improved discrete Gaussian and subgaussian analysis for lattice cryptography. In <i>23rd IACR International Conference on the Practice and Theory of Public-Key Cryptography</i> (Vol. 12110, pp. 623–651). Edinburgh, United Kingdom: Springer Nature. <a href=\"https://doi.org/10.1007/978-3-030-45374-9_21\">https://doi.org/10.1007/978-3-030-45374-9_21</a>","ama":"Genise N, Micciancio D, Peikert C, Walter M. Improved discrete Gaussian and subgaussian analysis for lattice cryptography. In: <i>23rd IACR International Conference on the Practice and Theory of Public-Key Cryptography</i>. Vol 12110. Springer Nature; 2020:623-651. doi:<a href=\"https://doi.org/10.1007/978-3-030-45374-9_21\">10.1007/978-3-030-45374-9_21</a>","ieee":"N. Genise, D. Micciancio, C. Peikert, and M. Walter, “Improved discrete Gaussian and subgaussian analysis for lattice cryptography,” in <i>23rd IACR International Conference on the Practice and Theory of Public-Key Cryptography</i>, Edinburgh, United Kingdom, 2020, vol. 12110, pp. 623–651.","chicago":"Genise, Nicholas, Daniele Micciancio, Chris Peikert, and Michael Walter. “Improved Discrete Gaussian and Subgaussian Analysis for Lattice Cryptography.” In <i>23rd IACR International Conference on the Practice and Theory of Public-Key Cryptography</i>, 12110:623–51. Springer Nature, 2020. <a href=\"https://doi.org/10.1007/978-3-030-45374-9_21\">https://doi.org/10.1007/978-3-030-45374-9_21</a>.","short":"N. Genise, D. Micciancio, C. Peikert, M. Walter, in:, 23rd IACR International Conference on the Practice and Theory of Public-Key Cryptography, Springer Nature, 2020, pp. 623–651.","mla":"Genise, Nicholas, et al. “Improved Discrete Gaussian and Subgaussian Analysis for Lattice Cryptography.” <i>23rd IACR International Conference on the Practice and Theory of Public-Key Cryptography</i>, vol. 12110, Springer Nature, 2020, pp. 623–51, doi:<a href=\"https://doi.org/10.1007/978-3-030-45374-9_21\">10.1007/978-3-030-45374-9_21</a>.","ista":"Genise N, Micciancio D, Peikert C, Walter M. 2020. Improved discrete Gaussian and subgaussian analysis for lattice cryptography. 23rd IACR International Conference on the Practice and Theory of Public-Key Cryptography. PKC: Public-Key Cryptography, LNCS, vol. 12110, 623–651."},"year":"2020"}]