---
_id: '7896'
abstract:
- lang: eng
text: "A search problem lies in the complexity class FNP if a solution to the given
instance of the problem can be verified efficiently. The complexity class TFNP
consists of all search problems in FNP that are total in the sense that a solution
is guaranteed to exist. TFNP contains a host of interesting problems from fields
such as algorithmic game theory, computational topology, number theory and combinatorics.
Since TFNP is a semantic class, it is unlikely to have a complete problem. Instead,
one studies its syntactic subclasses which are defined based on the combinatorial
principle used to argue totality. Of particular interest is the subclass PPAD,
which contains important problems\r\nlike computing Nash equilibrium for bimatrix
games and computational counterparts of several fixed-point theorems as complete.
In the thesis, we undertake the study of averagecase hardness of TFNP, and in
particular its subclass PPAD.\r\nAlmost nothing was known about average-case hardness
of PPAD before a series of recent results showed how to achieve it using a cryptographic
primitive called program obfuscation.\r\nHowever, it is currently not known how
to construct program obfuscation from standard cryptographic assumptions. Therefore,
it is desirable to relax the assumption under which average-case hardness of PPAD
can be shown. In the thesis we take a step in this direction. First, we show that
assuming the (average-case) hardness of a numbertheoretic\r\nproblem related to
factoring of integers, which we call Iterated-Squaring, PPAD is hard-on-average
in the random-oracle model. Then we strengthen this result to show that the average-case
hardness of PPAD reduces to the (adaptive) soundness of the Fiat-Shamir Transform,
a well-known technique used to compile a public-coin interactive protocol into
a non-interactive one. As a corollary, we obtain average-case hardness for PPAD
in the random-oracle model assuming the worst-case hardness of #SAT. Moreover,
the above results can all be strengthened to obtain average-case hardness for
the class CLS ⊆ PPAD.\r\nOur main technical contribution is constructing incrementally-verifiable
procedures for computing Iterated-Squaring and #SAT. By incrementally-verifiable,
we mean that every intermediate state of the computation includes a proof of its
correctness, and the proof can be updated and verified in polynomial time. Previous
constructions of such procedures relied on strong, non-standard assumptions. Instead,
we introduce a technique called recursive proof-merging to obtain the same from
weaker assumptions. "
alternative_title:
- ISTA Thesis
article_processing_charge: No
author:
- first_name: Chethan
full_name: Kamath Hosdurg, Chethan
id: 4BD3F30E-F248-11E8-B48F-1D18A9856A87
last_name: Kamath Hosdurg
citation:
ama: Kamath Hosdurg C. On the average-case hardness of total search problems. 2020.
doi:10.15479/AT:ISTA:7896
apa: Kamath Hosdurg, C. (2020). On the average-case hardness of total search
problems. Institute of Science and Technology Austria. https://doi.org/10.15479/AT:ISTA:7896
chicago: Kamath Hosdurg, Chethan. “On the Average-Case Hardness of Total Search
Problems.” Institute of Science and Technology Austria, 2020. https://doi.org/10.15479/AT:ISTA:7896.
ieee: C. Kamath Hosdurg, “On the average-case hardness of total search problems,”
Institute of Science and Technology Austria, 2020.
ista: Kamath Hosdurg C. 2020. On the average-case hardness of total search problems.
Institute of Science and Technology Austria.
mla: Kamath Hosdurg, Chethan. On the Average-Case Hardness of Total Search Problems.
Institute of Science and Technology Austria, 2020, doi:10.15479/AT:ISTA:7896.
short: C. Kamath Hosdurg, On the Average-Case Hardness of Total Search Problems,
Institute of Science and Technology Austria, 2020.
date_created: 2020-05-26T14:08:55Z
date_published: 2020-05-25T00:00:00Z
date_updated: 2023-09-07T13:15:55Z
day: '25'
ddc:
- '000'
degree_awarded: PhD
department:
- _id: KrPi
doi: 10.15479/AT:ISTA:7896
ec_funded: 1
file:
- access_level: open_access
checksum: b39e2e1c376f5819b823fb7077491c64
content_type: application/pdf
creator: dernst
date_created: 2020-05-26T14:08:13Z
date_updated: 2020-07-14T12:48:04Z
file_id: '7897'
file_name: 2020_Thesis_Kamath.pdf
file_size: 1622742
relation: main_file
- access_level: closed
checksum: 8b26ba729c1a85ac6bea775f5d73cdc7
content_type: application/x-zip-compressed
creator: dernst
date_created: 2020-05-26T14:08:23Z
date_updated: 2020-07-14T12:48:04Z
file_id: '7898'
file_name: Thesis_Kamath.zip
file_size: 15301529
relation: source_file
file_date_updated: 2020-07-14T12:48:04Z
has_accepted_license: '1'
language:
- iso: eng
month: '05'
oa: 1
oa_version: Published Version
page: '126'
project:
- _id: 258C570E-B435-11E9-9278-68D0E5697425
call_identifier: FP7
grant_number: '259668'
name: Provable Security for Physical Cryptography
- _id: 258AA5B2-B435-11E9-9278-68D0E5697425
call_identifier: H2020
grant_number: '682815'
name: Teaching Old Crypto New Tricks
publication_identifier:
issn:
- 2663-337X
publication_status: published
publisher: Institute of Science and Technology Austria
related_material:
record:
- id: '6677'
relation: part_of_dissertation
status: public
status: public
supervisor:
- first_name: Krzysztof Z
full_name: Pietrzak, Krzysztof Z
id: 3E04A7AA-F248-11E8-B48F-1D18A9856A87
last_name: Pietrzak
orcid: 0000-0002-9139-1654
title: On the average-case hardness of total search problems
tmp:
image: /images/cc_by.png
legal_code_url: https://creativecommons.org/licenses/by/4.0/legalcode
name: Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)
short: CC BY (4.0)
type: dissertation
user_id: c635000d-4b10-11ee-a964-aac5a93f6ac1
year: '2020'
...
---
_id: '5887'
abstract:
- lang: eng
text: 'Cryptographic security is usually defined as a guarantee that holds except
when a bad event with negligible probability occurs, and nothing is guaranteed
in that bad case. However, in settings where such failure can happen with substantial
probability, one needs to provide guarantees even for the bad case. A typical
example is where a (possibly weak) password is used instead of a secure cryptographic
key to protect a session, the bad event being that the adversary correctly guesses
the password. In a situation with multiple such sessions, a per-session guarantee
is desired: any session for which the password has not been guessed remains secure,
independently of whether other sessions have been compromised. A new formalism
for stating such gracefully degrading security guarantees is introduced and applied
to analyze the examples of password-based message authentication and password-based
encryption. While a natural per-message guarantee is achieved for authentication,
the situation of password-based encryption is more delicate: a per-session confidentiality
guarantee only holds against attackers for which the distribution of password-guessing
effort over the sessions is known in advance. In contrast, for more general attackers
without such a restriction, a strong, composable notion of security cannot be
achieved.'
article_processing_charge: No
article_type: original
author:
- first_name: Gregory
full_name: Demay, Gregory
last_name: Demay
- first_name: Peter
full_name: Gazi, Peter
id: 3E0BFE38-F248-11E8-B48F-1D18A9856A87
last_name: Gazi
- first_name: Ueli
full_name: Maurer, Ueli
last_name: Maurer
- first_name: Bjorn
full_name: Tackmann, Bjorn
last_name: Tackmann
citation:
ama: 'Demay G, Gazi P, Maurer U, Tackmann B. Per-session security: Password-based
cryptography revisited. Journal of Computer Security. 2019;27(1):75-111.
doi:10.3233/JCS-181131'
apa: 'Demay, G., Gazi, P., Maurer, U., & Tackmann, B. (2019). Per-session security:
Password-based cryptography revisited. Journal of Computer Security. IOS
Press. https://doi.org/10.3233/JCS-181131'
chicago: 'Demay, Gregory, Peter Gazi, Ueli Maurer, and Bjorn Tackmann. “Per-Session
Security: Password-Based Cryptography Revisited.” Journal of Computer Security.
IOS Press, 2019. https://doi.org/10.3233/JCS-181131.'
ieee: 'G. Demay, P. Gazi, U. Maurer, and B. Tackmann, “Per-session security: Password-based
cryptography revisited,” Journal of Computer Security, vol. 27, no. 1.
IOS Press, pp. 75–111, 2019.'
ista: 'Demay G, Gazi P, Maurer U, Tackmann B. 2019. Per-session security: Password-based
cryptography revisited. Journal of Computer Security. 27(1), 75–111.'
mla: 'Demay, Gregory, et al. “Per-Session Security: Password-Based Cryptography
Revisited.” Journal of Computer Security, vol. 27, no. 1, IOS Press, 2019,
pp. 75–111, doi:10.3233/JCS-181131.'
short: G. Demay, P. Gazi, U. Maurer, B. Tackmann, Journal of Computer Security 27
(2019) 75–111.
date_created: 2019-01-27T22:59:10Z
date_published: 2019-01-01T00:00:00Z
date_updated: 2021-01-12T08:05:08Z
day: '1'
department:
- _id: KrPi
doi: 10.3233/JCS-181131
ec_funded: 1
intvolume: ' 27'
issue: '1'
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://eprint.iacr.org/2016/166
month: '01'
oa: 1
oa_version: Preprint
page: 75-111
project:
- _id: 258AA5B2-B435-11E9-9278-68D0E5697425
call_identifier: H2020
grant_number: '682815'
name: Teaching Old Crypto New Tricks
publication: Journal of Computer Security
publication_identifier:
issn:
- 0926227X
publication_status: published
publisher: IOS Press
quality_controlled: '1'
scopus_import: '1'
status: public
title: 'Per-session security: Password-based cryptography revisited'
type: journal_article
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 27
year: '2019'
...
---
_id: '6528'
abstract:
- lang: eng
text: We construct a verifiable delay function (VDF) by showing how the Rivest-Shamir-Wagner
time-lock puzzle can be made publicly verifiable. Concretely, we give a statistically
sound public-coin protocol to prove that a tuple (N,x,T,y) satisfies y=x2T (mod
N) where the prover doesn’t know the factorization of N and its running time is
dominated by solving the puzzle, that is, compute x2T, which is conjectured to
require T sequential squarings. To get a VDF we make this protocol non-interactive
using the Fiat-Shamir heuristic.The motivation for this work comes from the Chia
blockchain design, which uses a VDF as akey ingredient. For typical parameters
(T≤2 40, N= 2048), our proofs are of size around 10K B, verification cost around
three RSA exponentiations and computing the proof is 8000 times faster than solving
the puzzle even without any parallelism.
alternative_title:
- LIPIcs
article_number: '60'
article_processing_charge: No
author:
- first_name: Krzysztof Z
full_name: Pietrzak, Krzysztof Z
id: 3E04A7AA-F248-11E8-B48F-1D18A9856A87
last_name: Pietrzak
orcid: 0000-0002-9139-1654
citation:
ama: 'Pietrzak KZ. Simple verifiable delay functions. In: 10th Innovations in
Theoretical Computer Science Conference. Vol 124. Schloss Dagstuhl - Leibniz-Zentrum
für Informatik; 2019. doi:10.4230/LIPICS.ITCS.2019.60'
apa: 'Pietrzak, K. Z. (2019). Simple verifiable delay functions. In 10th Innovations
in Theoretical Computer Science Conference (Vol. 124). San Diego, CA, United
States: Schloss Dagstuhl - Leibniz-Zentrum für Informatik. https://doi.org/10.4230/LIPICS.ITCS.2019.60'
chicago: Pietrzak, Krzysztof Z. “Simple Verifiable Delay Functions.” In 10th
Innovations in Theoretical Computer Science Conference, Vol. 124. Schloss
Dagstuhl - Leibniz-Zentrum für Informatik, 2019. https://doi.org/10.4230/LIPICS.ITCS.2019.60.
ieee: K. Z. Pietrzak, “Simple verifiable delay functions,” in 10th Innovations
in Theoretical Computer Science Conference, San Diego, CA, United States,
2019, vol. 124.
ista: 'Pietrzak KZ. 2019. Simple verifiable delay functions. 10th Innovations in
Theoretical Computer Science Conference. ITCS 2019: Innovations in Theoretical
Computer Science, LIPIcs, vol. 124, 60.'
mla: Pietrzak, Krzysztof Z. “Simple Verifiable Delay Functions.” 10th Innovations
in Theoretical Computer Science Conference, vol. 124, 60, Schloss Dagstuhl
- Leibniz-Zentrum für Informatik, 2019, doi:10.4230/LIPICS.ITCS.2019.60.
short: K.Z. Pietrzak, in:, 10th Innovations in Theoretical Computer Science Conference,
Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2019.
conference:
end_date: 2019-01-12
location: San Diego, CA, United States
name: 'ITCS 2019: Innovations in Theoretical Computer Science'
start_date: 2019-01-10
date_created: 2019-06-06T14:12:36Z
date_published: 2019-01-10T00:00:00Z
date_updated: 2021-01-12T08:07:53Z
day: '10'
ddc:
- '000'
department:
- _id: KrPi
doi: 10.4230/LIPICS.ITCS.2019.60
ec_funded: 1
file:
- access_level: open_access
checksum: f0ae1bb161431d9db3dea5ace082bfb5
content_type: application/pdf
creator: dernst
date_created: 2019-06-06T14:22:04Z
date_updated: 2020-07-14T12:47:33Z
file_id: '6529'
file_name: 2019_LIPIcs_Pietrzak.pdf
file_size: 558770
relation: main_file
file_date_updated: 2020-07-14T12:47:33Z
has_accepted_license: '1'
intvolume: ' 124'
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://eprint.iacr.org/2018/627
month: '01'
oa: 1
oa_version: Published Version
project:
- _id: 258AA5B2-B435-11E9-9278-68D0E5697425
call_identifier: H2020
grant_number: '682815'
name: Teaching Old Crypto New Tricks
publication: 10th Innovations in Theoretical Computer Science Conference
publication_identifier:
isbn:
- 978-3-95977-095-8
issn:
- 1868-8969
publication_status: published
publisher: Schloss Dagstuhl - Leibniz-Zentrum für Informatik
quality_controlled: '1'
scopus_import: 1
status: public
title: Simple verifiable delay functions
tmp:
image: /images/cc_by.png
legal_code_url: https://creativecommons.org/licenses/by/4.0/legalcode
name: Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)
short: CC BY (4.0)
type: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 124
year: '2019'
...
---
_id: '6726'
abstract:
- lang: eng
text: Randomness is an essential part of any secure cryptosystem, but many constructions
rely on distributions that are not uniform. This is particularly true for lattice
based cryptosystems, which more often than not make use of discrete Gaussian distributions
over the integers. For practical purposes it is crucial to evaluate the impact
that approximation errors have on the security of a scheme to provide the best
possible trade-off between security and performance. Recent years have seen surprising
results allowing to use relatively low precision while maintaining high levels
of security. A key insight in these results is that sampling a distribution with
low relative error can provide very strong security guarantees. Since floating
point numbers provide guarantees on the relative approximation error, they seem
a suitable tool in this setting, but it is not obvious which sampling algorithms
can actually profit from them. While previous works have shown that inversion
sampling can be adapted to provide a low relative error (Pöppelmann et al., CHES
2014; Prest, ASIACRYPT 2017), other works have called into question if this is
possible for other sampling techniques (Zheng et al., Eprint report 2018/309).
In this work, we consider all sampling algorithms that are popular in the cryptographic
setting and analyze the relationship of floating point precision and the resulting
relative error. We show that all of the algorithms either natively achieve a low
relative error or can be adapted to do so.
article_processing_charge: No
author:
- first_name: Michael
full_name: Walter, Michael
id: 488F98B0-F248-11E8-B48F-1D18A9856A87
last_name: Walter
orcid: 0000-0003-3186-2482
citation:
ama: 'Walter M. Sampling the integers with low relative error. In: Buchmann J, Nitaj
A, Rachidi T, eds. Progress in Cryptology – AFRICACRYPT 2019. Vol 11627.
LNCS. Cham: Springer Nature; 2019:157-180. doi:10.1007/978-3-030-23696-0_9'
apa: 'Walter, M. (2019). Sampling the integers with low relative error. In J. Buchmann,
A. Nitaj, & T. Rachidi (Eds.), Progress in Cryptology – AFRICACRYPT 2019
(Vol. 11627, pp. 157–180). Cham: Springer Nature. https://doi.org/10.1007/978-3-030-23696-0_9'
chicago: 'Walter, Michael. “Sampling the Integers with Low Relative Error.” In Progress
in Cryptology – AFRICACRYPT 2019, edited by J Buchmann, A Nitaj, and T Rachidi,
11627:157–80. LNCS. Cham: Springer Nature, 2019. https://doi.org/10.1007/978-3-030-23696-0_9.'
ieee: 'M. Walter, “Sampling the integers with low relative error,” in Progress
in Cryptology – AFRICACRYPT 2019, vol. 11627, J. Buchmann, A. Nitaj, and T.
Rachidi, Eds. Cham: Springer Nature, 2019, pp. 157–180.'
ista: 'Walter M. 2019.Sampling the integers with low relative error. In: Progress
in Cryptology – AFRICACRYPT 2019. vol. 11627, 157–180.'
mla: Walter, Michael. “Sampling the Integers with Low Relative Error.” Progress
in Cryptology – AFRICACRYPT 2019, edited by J Buchmann et al., vol. 11627,
Springer Nature, 2019, pp. 157–80, doi:10.1007/978-3-030-23696-0_9.
short: M. Walter, in:, J. Buchmann, A. Nitaj, T. Rachidi (Eds.), Progress in Cryptology
– AFRICACRYPT 2019, Springer Nature, Cham, 2019, pp. 157–180.
conference:
end_date: 2019-07-11
location: Rabat, Morocco
name: 'AFRICACRYPT: International Conference on Cryptology in Africa'
start_date: 2019-07-09
date_created: 2019-07-29T12:25:31Z
date_published: 2019-06-29T00:00:00Z
date_updated: 2023-02-23T12:50:15Z
day: '29'
department:
- _id: KrPi
doi: 10.1007/978-3-030-23696-0_9
ec_funded: 1
editor:
- first_name: J
full_name: Buchmann, J
last_name: Buchmann
- first_name: A
full_name: Nitaj, A
last_name: Nitaj
- first_name: T
full_name: Rachidi, T
last_name: Rachidi
intvolume: ' 11627'
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://eprint.iacr.org/2019/068
month: '06'
oa: 1
oa_version: Preprint
page: 157-180
place: Cham
project:
- _id: 258AA5B2-B435-11E9-9278-68D0E5697425
call_identifier: H2020
grant_number: '682815'
name: Teaching Old Crypto New Tricks
publication: Progress in Cryptology – AFRICACRYPT 2019
publication_identifier:
eisbn:
- 978-3-0302-3696-0
isbn:
- 978-3-0302-3695-3
issn:
- 0302-9743
- 1611-3349
publication_status: published
publisher: Springer Nature
quality_controlled: '1'
scopus_import: '1'
series_title: LNCS
status: public
title: Sampling the integers with low relative error
type: book_chapter
user_id: 8b945eb4-e2f2-11eb-945a-df72226e66a9
volume: 11627
year: '2019'
...
---
_id: '7136'
abstract:
- lang: eng
text: "It is well established that the notion of min-entropy fails to satisfy the
\\emph{chain rule} of the form H(X,Y)=H(X|Y)+H(Y), known for Shannon Entropy.
Such a property would help to analyze how min-entropy is split among smaller blocks.
Problems of this kind arise for example when constructing extractors and dispersers.\r\nWe
show that any sequence of variables exhibits a very strong strong block-source
structure (conditional distributions of blocks are nearly flat) when we \\emph{spoil
few correlated bits}. This implies, conditioned on the spoiled bits, that \\emph{splitting-recombination
properties} hold. In particular, we have many nice properties that min-entropy
doesn't obey in general, for example strong chain rules, \"information can't hurt\"
inequalities, equivalences of average and worst-case conditional entropy definitions
and others. Quantitatively, for any sequence X1,…,Xt of random variables over
an alphabet X we prove that, when conditioned on m=t⋅O(loglog|X|+loglog(1/ϵ)+logt)
bits of auxiliary information, all conditional distributions of the form Xi|X2019 IEEE International Symposium on Information Theory. IEEE; 2019. doi:10.1109/isit.2019.8849240'
apa: 'Skórski, M. (2019). Strong chain rules for min-entropy under few bits spoiled.
In 2019 IEEE International Symposium on Information Theory. Paris, France:
IEEE. https://doi.org/10.1109/isit.2019.8849240'
chicago: Skórski, Maciej. “Strong Chain Rules for Min-Entropy under Few Bits Spoiled.”
In 2019 IEEE International Symposium on Information Theory. IEEE, 2019.
https://doi.org/10.1109/isit.2019.8849240.
ieee: M. Skórski, “Strong chain rules for min-entropy under few bits spoiled,” in
2019 IEEE International Symposium on Information Theory, Paris, France,
2019.
ista: 'Skórski M. 2019. Strong chain rules for min-entropy under few bits spoiled.
2019 IEEE International Symposium on Information Theory. ISIT: International Symposium
on Information Theory, 8849240.'
mla: Skórski, Maciej. “Strong Chain Rules for Min-Entropy under Few Bits Spoiled.”
2019 IEEE International Symposium on Information Theory, 8849240, IEEE,
2019, doi:10.1109/isit.2019.8849240.
short: M. Skórski, in:, 2019 IEEE International Symposium on Information Theory,
IEEE, 2019.
conference:
end_date: 2019-07-12
location: Paris, France
name: 'ISIT: International Symposium on Information Theory'
start_date: 2019-07-07
date_created: 2019-11-28T10:19:21Z
date_published: 2019-07-01T00:00:00Z
date_updated: 2023-09-06T11:15:41Z
day: '01'
department:
- _id: KrPi
doi: 10.1109/isit.2019.8849240
external_id:
arxiv:
- '1702.08476'
isi:
- '000489100301043'
isi: 1
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://arxiv.org/abs/1702.08476
month: '07'
oa: 1
oa_version: Preprint
publication: 2019 IEEE International Symposium on Information Theory
publication_identifier:
isbn:
- '9781538692912'
publication_status: published
publisher: IEEE
quality_controlled: '1'
scopus_import: '1'
status: public
title: Strong chain rules for min-entropy under few bits spoiled
type: conference
user_id: c635000d-4b10-11ee-a964-aac5a93f6ac1
year: '2019'
...