---
_id: '10865'
abstract:
- lang: eng
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) ."
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.
article_processing_charge: No
author:
- first_name: Suvradip
full_name: Chakraborty, Suvradip
id: B9CD0494-D033-11E9-B219-A439E6697425
last_name: Chakraborty
- first_name: Manoj
full_name: Prabhakaran, Manoj
last_name: Prabhakaran
- first_name: Daniel
full_name: Wichs, Daniel
last_name: Wichs
citation:
ama: 'Chakraborty S, Prabhakaran M, Wichs D. Witness maps and applications. In:
Kiayias A, ed. Public-Key Cryptography. Vol 12110. LNCS. Cham: Springer
Nature; 2020:220-246. doi:10.1007/978-3-030-45374-9_8'
apa: 'Chakraborty, S., Prabhakaran, M., & Wichs, D. (2020). Witness maps and
applications. In A. Kiayias (Ed.), Public-Key Cryptography (Vol. 12110,
pp. 220–246). Cham: Springer Nature. https://doi.org/10.1007/978-3-030-45374-9_8'
chicago: 'Chakraborty, Suvradip, Manoj Prabhakaran, and Daniel Wichs. “Witness Maps
and Applications.” In Public-Key Cryptography, edited by A Kiayias, 12110:220–46.
LNCS. Cham: Springer Nature, 2020. https://doi.org/10.1007/978-3-030-45374-9_8.'
ieee: 'S. Chakraborty, M. Prabhakaran, and D. Wichs, “Witness maps and applications,”
in Public-Key Cryptography, vol. 12110, A. Kiayias, Ed. Cham: Springer
Nature, 2020, pp. 220–246.'
ista: 'Chakraborty S, Prabhakaran M, Wichs D. 2020.Witness maps and applications.
In: Public-Key Cryptography. vol. 12110, 220–246.'
mla: Chakraborty, Suvradip, et al. “Witness Maps and Applications.” Public-Key
Cryptography, edited by A Kiayias, vol. 12110, Springer Nature, 2020, pp.
220–46, doi:10.1007/978-3-030-45374-9_8.
short: S. Chakraborty, M. Prabhakaran, D. Wichs, in:, A. Kiayias (Ed.), Public-Key
Cryptography, Springer Nature, Cham, 2020, pp. 220–246.
date_created: 2022-03-18T11:35:51Z
date_published: 2020-04-29T00:00:00Z
date_updated: 2023-09-05T15:10:02Z
day: '29'
doi: 10.1007/978-3-030-45374-9_8
editor:
- first_name: A
full_name: Kiayias, A
last_name: Kiayias
intvolume: ' 12110'
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://eprint.iacr.org/2020/090
month: '04'
oa: 1
oa_version: Preprint
page: 220-246
place: Cham
publication: Public-Key Cryptography
publication_identifier:
eissn:
- 1611-3349
isbn:
- '9783030453732'
- '9783030453749'
issn:
- 0302-9743
publication_status: published
publisher: Springer Nature
quality_controlled: '1'
scopus_import: '1'
series_title: LNCS
status: public
title: Witness maps and applications
type: book_chapter
user_id: c635000d-4b10-11ee-a964-aac5a93f6ac1
volume: 12110
year: '2020'
...
---
_id: '8339'
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."
alternative_title:
- LNCS
article_processing_charge: No
author:
- first_name: Nicholas
full_name: Genise, Nicholas
last_name: Genise
- first_name: Daniele
full_name: Micciancio, Daniele
last_name: Micciancio
- first_name: Chris
full_name: Peikert, Chris
last_name: Peikert
- first_name: Michael
full_name: Walter, Michael
id: 488F98B0-F248-11E8-B48F-1D18A9856A87
last_name: Walter
orcid: 0000-0003-3186-2482
citation:
ama: 'Genise N, Micciancio D, Peikert C, Walter M. Improved discrete Gaussian and
subgaussian analysis for lattice cryptography. In: 23rd IACR International
Conference on the Practice and Theory of Public-Key Cryptography. Vol 12110.
Springer Nature; 2020:623-651. doi:10.1007/978-3-030-45374-9_21'
apa: 'Genise, N., Micciancio, D., Peikert, C., & Walter, M. (2020). Improved
discrete Gaussian and subgaussian analysis for lattice cryptography. In 23rd
IACR International Conference on the Practice and Theory of Public-Key Cryptography
(Vol. 12110, pp. 623–651). Edinburgh, United Kingdom: Springer Nature. https://doi.org/10.1007/978-3-030-45374-9_21'
chicago: Genise, Nicholas, Daniele Micciancio, Chris Peikert, and Michael Walter.
“Improved Discrete Gaussian and Subgaussian Analysis for Lattice Cryptography.”
In 23rd IACR International Conference on the Practice and Theory of Public-Key
Cryptography, 12110:623–51. Springer Nature, 2020. https://doi.org/10.1007/978-3-030-45374-9_21.
ieee: N. Genise, D. Micciancio, C. Peikert, and M. Walter, “Improved discrete Gaussian
and subgaussian analysis for lattice cryptography,” in 23rd IACR International
Conference on the Practice and Theory of Public-Key Cryptography, Edinburgh,
United Kingdom, 2020, vol. 12110, pp. 623–651.
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.'
mla: Genise, Nicholas, et al. “Improved Discrete Gaussian and Subgaussian Analysis
for Lattice Cryptography.” 23rd IACR International Conference on the Practice
and Theory of Public-Key Cryptography, vol. 12110, Springer Nature, 2020,
pp. 623–51, doi:10.1007/978-3-030-45374-9_21.
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.
conference:
end_date: 2020-05-07
location: Edinburgh, United Kingdom
name: 'PKC: Public-Key Cryptography'
start_date: 2020-05-04
date_created: 2020-09-06T22:01:13Z
date_published: 2020-05-15T00:00:00Z
date_updated: 2023-02-23T13:31:06Z
day: '15'
department:
- _id: KrPi
doi: 10.1007/978-3-030-45374-9_21
ec_funded: 1
intvolume: ' 12110'
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://eprint.iacr.org/2020/337
month: '05'
oa: 1
oa_version: Preprint
page: 623-651
project:
- _id: 258AA5B2-B435-11E9-9278-68D0E5697425
call_identifier: H2020
grant_number: '682815'
name: Teaching Old Crypto New Tricks
publication: 23rd IACR International Conference on the Practice and Theory of Public-Key
Cryptography
publication_identifier:
eissn:
- '16113349'
isbn:
- '9783030453732'
issn:
- '03029743'
publication_status: published
publisher: Springer Nature
quality_controlled: '1'
scopus_import: '1'
status: public
title: Improved discrete Gaussian and subgaussian analysis for lattice cryptography
type: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 12110
year: '2020'
...