Provable Security for Physical Cryptography
Project Period: 2011-09-01 – 2015-10-31
Externally Funded
Acronym
PSPC
Principal Investigator
Krzysztof Z Pietrzak
Department(s)
Pietrzak Group
Grant Number
259668
Funding Organisation
EC/FP7
43 Publications
2016 | Conference Paper | IST-REx-ID: 1231 |

On the complexity of scrypt and proofs of space in the parallel random oracle model
J.F. Alwen, B. Chen, C. Kamath Hosdurg, V. Kolmogorov, K.Z. Pietrzak, S. Tessaro, in:, Springer, 2016, pp. 358–387.
[Submitted Version]
View
| DOI
| Download Submitted Version (ext.)
J.F. Alwen, B. Chen, C. Kamath Hosdurg, V. Kolmogorov, K.Z. Pietrzak, S. Tessaro, in:, Springer, 2016, pp. 358–387.
2016 | Conference Paper | IST-REx-ID: 1233 |

Standard security does imply security against selective opening for markov distributions
G. Fuchsbauer, F. Heuer, E. Kiltz, K.Z. Pietrzak, in:, Springer, 2016, pp. 282–305.
[Submitted Version]
View
| DOI
| Download Submitted Version (ext.)
G. Fuchsbauer, F. Heuer, E. Kiltz, K.Z. Pietrzak, in:, Springer, 2016, pp. 282–305.
2016 | Conference Paper | IST-REx-ID: 1366 |

Provably robust sponge-based PRNGs and KDFs
P. Gazi, S. Tessaro, in:, Springer, 2016, pp. 87–116.
[Preprint]
View
| DOI
| Download Preprint (ext.)
P. Gazi, S. Tessaro, in:, Springer, 2016, pp. 87–116.
2015 | Conference Paper | IST-REx-ID: 1474 |

Policy privacy in cryptographic access control
A. Ferrara, G. Fuchsbauer, B. Liu, B. Warinschi, in:, IEEE, 2015, pp. 46–60.
[Submitted Version]
View
| DOI
| Download Submitted Version (ext.)
A. Ferrara, G. Fuchsbauer, B. Liu, B. Warinschi, in:, IEEE, 2015, pp. 46–60.
2015 | Conference Paper | IST-REx-ID: 1646 |

Key-homomorphic constrained pseudorandom functions
A. Banerjee, G. Fuchsbauer, C. Peikert, K.Z. Pietrzak, S. Stevens, in:, 12th Theory of Cryptography Conference, Springer Nature, 2015, pp. 31–60.
[Submitted Version]
View
| Files available
| DOI
| Download Submitted Version (ext.)
A. Banerjee, G. Fuchsbauer, C. Peikert, K.Z. Pietrzak, S. Stevens, in:, 12th Theory of Cryptography Conference, Springer Nature, 2015, pp. 31–60.
2015 | Conference Paper | IST-REx-ID: 1648 |

A quasipolynomial reduction for generalized selective decryption on trees
G. Fuchsbauer, Z. Jafargholi, K.Z. Pietrzak, in:, Springer, 2015, pp. 601–620.
[Submitted Version]
View
| Files available
| DOI
G. Fuchsbauer, Z. Jafargholi, K.Z. Pietrzak, in:, Springer, 2015, pp. 601–620.
2015 | Conference Paper | IST-REx-ID: 1649 |

Efficient zero-knowledge proofs for commitments from learning with errors over rings
F. Benhamouda, S. Krenn, V. Lyubashevsky, K.Z. Pietrzak, 9326 (2015) 305–325.
[Published Version]
View
| Files available
| DOI
F. Benhamouda, S. Krenn, V. Lyubashevsky, K.Z. Pietrzak, 9326 (2015) 305–325.
2015 | Conference Paper | IST-REx-ID: 1644 |

Query-complexity amplification for random oracles
G. Demay, P. Gazi, U. Maurer, B. Tackmann, in:, Springer, 2015, pp. 159–180.
[Submitted Version]
View
| DOI
| Download Submitted Version (ext.)
G. Demay, P. Gazi, U. Maurer, B. Tackmann, in:, Springer, 2015, pp. 159–180.
2014 | Conference Paper | IST-REx-ID: 1643 |

Constrained Verifiable Random Functions
G. Fuchsbauer, in:, M. Abdalla, R. De Prisco (Eds.), SCN 2014, Springer, 2014, pp. 95–114.
[Submitted Version]
View
| DOI
| Download Submitted Version (ext.)
G. Fuchsbauer, in:, M. Abdalla, R. De Prisco (Eds.), SCN 2014, Springer, 2014, pp. 95–114.
2015 | Conference Paper | IST-REx-ID: 1647 |

Practical round-optimal blind signatures in the standard model
G. Fuchsbauer, C. Hanser, D. Slamanig, in:, Springer, 2015, pp. 233–253.
[Submitted Version]
View
| Files available
| DOI
| Download Submitted Version (ext.)
G. Fuchsbauer, C. Hanser, D. Slamanig, in:, Springer, 2015, pp. 233–253.
2016 | Conference Paper | IST-REx-ID: 1225 |

Practical round-optimal blind signatures in the standard model from weaker assumptions
G. Fuchsbauer, C. Hanser, C. Kamath Hosdurg, D. Slamanig, in:, Springer, 2016, pp. 391–408.
[Submitted Version]
View
| Files available
| DOI
| Download Submitted Version (ext.)
G. Fuchsbauer, C. Hanser, C. Kamath Hosdurg, D. Slamanig, in:, Springer, 2016, pp. 391–408.
2015 | Conference Paper | IST-REx-ID: 1645
Secret-key cryptography from ideal primitives: A systematic verview
P. Gazi, S. Tessaro, in:, 2015 IEEE Information Theory Workshop, IEEE, 2015.
View
| DOI
P. Gazi, S. Tessaro, in:, 2015 IEEE Information Theory Workshop, IEEE, 2015.
2015 | Conference Paper | IST-REx-ID: 1654 |

Generic security of NMAC and HMAC with input whitening
P. Gazi, K.Z. Pietrzak, S. Tessaro, 9453 (2015) 85–109.
[Submitted Version]
View
| Files available
| DOI
P. Gazi, K.Z. Pietrzak, S. Tessaro, 9453 (2015) 85–109.
2015 | Conference Paper | IST-REx-ID: 1650 |

Condensed unpredictability
M. Skórski, A. Golovnev, K.Z. Pietrzak, in:, Springer, 2015, pp. 1046–1057.
[Published Version]
View
| Files available
| DOI
M. Skórski, A. Golovnev, K.Z. Pietrzak, in:, Springer, 2015, pp. 1046–1057.
2016 | Conference Paper | IST-REx-ID: 1653 |

New realizations of somewhere statistically binding hashing and positional accumulators
T. Okamoto, K.Z. Pietrzak, B. Waters, D. Wichs, in:, Springer, 2016, pp. 121–145.
[Submitted Version]
View
| Files available
| DOI
T. Okamoto, K.Z. Pietrzak, B. Waters, D. Wichs, in:, Springer, 2016, pp. 121–145.
2015 | Conference Paper | IST-REx-ID: 1651 |

Anonymous transferable e-cash
F. Baldimtsi, M. Chase, G. Fuchsbauer, M. Kohlweiss, in:, Public-Key Cryptography - PKC 2015, Springer, 2015, pp. 101–124.
[Published Version]
View
| DOI
| Download Published Version (ext.)
F. Baldimtsi, M. Chase, G. Fuchsbauer, M. Kohlweiss, in:, Public-Key Cryptography - PKC 2015, Springer, 2015, pp. 101–124.
2015 | Conference Paper | IST-REx-ID: 1652 |

High parallel complexity graphs and memory-hard functions
J.F. Alwen, V. Serbinenko, in:, Proceedings of the 47th Annual ACM Symposium on Theory of Computing, ACM, 2015, pp. 595–603.
[Submitted Version]
View
| DOI
| Download Submitted Version (ext.)
J.F. Alwen, V. Serbinenko, in:, Proceedings of the 47th Annual ACM Symposium on Theory of Computing, ACM, 2015, pp. 595–603.
2015 | Conference Paper | IST-REx-ID: 1672 |

Incoercible multi-party computation and universally composable receipt-free voting
J.F. Alwen, R. Ostrovsky, H. Zhou, V. Zikas, in:, Advances in Cryptology - CRYPTO 2015, Springer, 2015, pp. 763–780.
[Submitted Version]
View
| Files available
| DOI
J.F. Alwen, R. Ostrovsky, H. Zhou, V. Zikas, in:, Advances in Cryptology - CRYPTO 2015, Springer, 2015, pp. 763–780.
2015 | Conference Paper | IST-REx-ID: 1669 |

The chain rule for HILL pseudoentropy, revisited
K.Z. Pietrzak, M. Skórski, 9230 (2015) 81–98.
[Submitted Version]
View
| Files available
| DOI
K.Z. Pietrzak, M. Skórski, 9230 (2015) 81–98.
2015 | Conference Paper | IST-REx-ID: 1671 |

The exact PRF security of truncation: Tight bounds for keyed sponges and truncated CBC
P. Gazi, K.Z. Pietrzak, S. Tessaro, in:, Springer, 2015, pp. 368–387.
[Submitted Version]
View
| Files available
| DOI
P. Gazi, K.Z. Pietrzak, S. Tessaro, in:, Springer, 2015, pp. 368–387.
2015 | Conference Paper | IST-REx-ID: 1668 |

Relaxing full-codebook security: A refined analysis of key-length extension schemes
P. Gazi, J. Lee, Y. Seurin, J. Steinberger, S. Tessaro, 9054 (2015) 319–341.
[Submitted Version]
View
| DOI
| Download Submitted Version (ext.)
P. Gazi, J. Lee, Y. Seurin, J. Steinberger, S. Tessaro, 9054 (2015) 319–341.
2014 | Conference Paper | IST-REx-ID: 2045 |

Enhanced chosen-ciphertext security and applications
D. Dachman Soled, G. Fuchsbauer, P. Mohassel, A. O’Neill, in:, H. Krawczyk (Ed.), Lecture Notes in Computer Science (Including Subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), Springer, 2014, pp. 329–344.
[Submitted Version]
View
| DOI
| Download Submitted Version (ext.)
D. Dachman Soled, G. Fuchsbauer, P. Mohassel, A. O’Neill, in:, H. Krawczyk (Ed.), Lecture Notes in Computer Science (Including Subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), Springer, 2014, pp. 329–344.
2012 | Conference Paper | IST-REx-ID: 2048 |

Practical leakage-resilient symmetric cryptography
S. Faust, K.Z. Pietrzak, J. Schipper, in:, Conference Proceedings CHES 2012, Springer, 2012, pp. 213–232.
[Preprint]
View
| DOI
| Download Preprint (ext.)
S. Faust, K.Z. Pietrzak, J. Schipper, in:, Conference Proceedings CHES 2012, Springer, 2012, pp. 213–232.
2012 | Conference Paper | IST-REx-ID: 2049 |

Lapin: An efficient authentication protocol based on ring-LPN
S. Heyse, E. Kiltz, V. Lyubashevsky, C. Paar, K.Z. Pietrzak, in:, Conference Proceedings FSE 2012, Springer, 2012, pp. 346–365.
[Preprint]
View
| DOI
| Download Preprint (ext.)
S. Heyse, E. Kiltz, V. Lyubashevsky, C. Paar, K.Z. Pietrzak, in:, Conference Proceedings FSE 2012, Springer, 2012, pp. 346–365.
2014 | Conference Paper | IST-REx-ID: 2046 |

Policy-based signatures
M. Bellare, G. Fuchsbauer, in:, H. Krawczyk (Ed.), Lecture Notes in Computer Science (Including Subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), Springer, 2014, pp. 520–537.
[Submitted Version]
View
| DOI
| Download Submitted Version (ext.)
M. Bellare, G. Fuchsbauer, in:, H. Krawczyk (Ed.), Lecture Notes in Computer Science (Including Subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), Springer, 2014, pp. 520–537.
2014 | Conference Paper | IST-REx-ID: 2236 |

How to fake auxiliary input
D. Jetchev, K.Z. Pietrzak, in:, Y. Lindell (Ed.), Springer, 2014, pp. 566–590.
[Submitted Version]
View
| Files available
| DOI
| Download Submitted Version (ext.)
D. Jetchev, K.Z. Pietrzak, in:, Y. Lindell (Ed.), Springer, 2014, pp. 566–590.
2013 | Conference Paper | IST-REx-ID: 2259 |

Learning with rounding, revisited: New reduction properties and applications
J.F. Alwen, S. Krenn, K.Z. Pietrzak, D. Wichs, 8042 (2013) 57–74.
[Published Version]
View
| Files available
| DOI
J.F. Alwen, S. Krenn, K.Z. Pietrzak, D. Wichs, 8042 (2013) 57–74.
2013 | Conference Paper | IST-REx-ID: 2258 |

Digital signatures with minimal overhead from indifferentiable random invertible functions
E. Kiltz, K.Z. Pietrzak, M. Szegedy, 8042 (2013) 571–588.
[Submitted Version]
View
| Files available
| DOI
E. Kiltz, K.Z. Pietrzak, M. Szegedy, 8042 (2013) 571–588.
2015 | Conference Paper | IST-REx-ID: 1675
Proofs of space
S. Dziembowski, S. Faust, V. Kolmogorov, K.Z. Pietrzak, 9216 (2015) 585–605.
View
| Files available
| DOI
S. Dziembowski, S. Faust, V. Kolmogorov, K.Z. Pietrzak, 9216 (2015) 585–605.
2013 | Conference Paper | IST-REx-ID: 2940 |

A counterexample to the chain rule for conditional HILL entropy, and what deniable encryption has to do with it
S. Krenn, K.Z. Pietrzak, A. Wadia, in:, A. Sahai (Ed.), Springer, 2013, pp. 23–39.
[Submitted Version]
View
| Files available
| DOI
S. Krenn, K.Z. Pietrzak, A. Wadia, in:, A. Sahai (Ed.), Springer, 2013, pp. 23–39.
2016 | Journal Article | IST-REx-ID: 1479 |

A counterexample to the chain rule for conditional HILL entropy
S. Krenn, K.Z. Pietrzak, A. Wadia, D. Wichs, Computational Complexity 25 (2016) 567–605.
[Submitted Version]
View
| Files available
| DOI
S. Krenn, K.Z. Pietrzak, A. Wadia, D. Wichs, Computational Complexity 25 (2016) 567–605.
2012 | Conference Paper | IST-REx-ID: 2974 |

Commitments and efficient zero knowledge proofs from learning parity with noise
A. Jain, S. Krenn, K.Z. Pietrzak, A. Tentes, in:, X. Wang, K. Sako (Eds.), Springer, 2012, pp. 663–680.
[Submitted Version]
View
| Files available
| DOI
A. Jain, S. Krenn, K.Z. Pietrzak, A. Tentes, in:, X. Wang, K. Sako (Eds.), Springer, 2012, pp. 663–680.
2012 | Conference Paper | IST-REx-ID: 3282 |

Message authentication, revisited
Y. Dodis, K.Z. Pietrzak, E. Kiltz, D. Wichs, in:, Springer, 2012, pp. 355–374.
[Submitted Version]
View
| Files available
| DOI
Y. Dodis, K.Z. Pietrzak, E. Kiltz, D. Wichs, in:, Springer, 2012, pp. 355–374.
2012 | Conference Paper | IST-REx-ID: 3280 |

Subspace LWE
K.Z. Pietrzak, in:, Springer, 2012, pp. 548–563.
[Submitted Version]
View
| DOI
| Download Submitted Version (ext.)
K.Z. Pietrzak, in:, Springer, 2012, pp. 548–563.
2012 | Conference Paper | IST-REx-ID: 3279
Hardness preserving constructions of pseudorandom functions
A. Jain, K.Z. Pietrzak, A. Tentes, in:, Springer, 2012, pp. 369–382.
View
| DOI
| Download None (ext.)
A. Jain, K.Z. Pietrzak, A. Tentes, in:, Springer, 2012, pp. 369–382.
2014 | Conference Paper | IST-REx-ID: 2082 |

The exact PRF-security of NMAC and HMAC
P. Gazi, K.Z. Pietrzak, M. Rybar, in:, J. Garay, R. Gennaro (Eds.), Springer, 2014, pp. 113–130.
[Submitted Version]
View
| Files available
| DOI
P. Gazi, K.Z. Pietrzak, M. Rybar, in:, J. Garay, R. Gennaro (Eds.), Springer, 2014, pp. 113–130.
2016 | Conference Paper | IST-REx-ID: 1229 |

Offline witness encryption
H.M. Abusalah, G. Fuchsbauer, K.Z. Pietrzak, in:, Springer, 2016, pp. 285–303.
[Submitted Version]
View
| Files available
| DOI
H.M. Abusalah, G. Fuchsbauer, K.Z. Pietrzak, in:, Springer, 2016, pp. 285–303.
2018 | Thesis | IST-REx-ID: 83 |

Proof systems for sustainable decentralized cryptocurrencies
H.M. Abusalah, Proof Systems for Sustainable Decentralized Cryptocurrencies, Institute of Science and Technology Austria, 2018.
[Published Version]
View
| Files available
| DOI
H.M. Abusalah, Proof Systems for Sustainable Decentralized Cryptocurrencies, Institute of Science and Technology Austria, 2018.
2016 | Conference Paper | IST-REx-ID: 1236 |

Constrained PRFs for unbounded inputs
H.M. Abusalah, G. Fuchsbauer, K.Z. Pietrzak, in:, Springer, 2016, pp. 413–428.
[Submitted Version]
View
| Files available
| DOI
H.M. Abusalah, G. Fuchsbauer, K.Z. Pietrzak, in:, Springer, 2016, pp. 413–428.
2016 | Conference Paper | IST-REx-ID: 1235 |

Constrained PRFs for unbounded inputs with short keys
H.M. Abusalah, G. Fuchsbauer, in:, Springer, 2016, pp. 445–463.
[Submitted Version]
View
| Files available
| DOI
| Download Submitted Version (ext.)
H.M. Abusalah, G. Fuchsbauer, in:, Springer, 2016, pp. 445–463.
2020 | Thesis | IST-REx-ID: 7896 |

On the average-case hardness of total search problems
C. Kamath Hosdurg, On the Average-Case Hardness of Total Search Problems, Institute of Science and Technology Austria, 2020.
[Published Version]
View
| Files available
| DOI
C. Kamath Hosdurg, On the Average-Case Hardness of Total Search Problems, Institute of Science and Technology Austria, 2020.
2018 | Journal Article | IST-REx-ID: 107 |

Non-malleable codes
S. Dziembowski, K.Z. Pietrzak, D. Wichs, Journal of the ACM 65 (2018).
[Preprint]
View
| DOI
| Download Preprint (ext.)
| WoS
S. Dziembowski, K.Z. Pietrzak, D. Wichs, Journal of the ACM 65 (2018).
2017 | Journal Article | IST-REx-ID: 1187 |

Efficient authentication from hard learning problems
E. Kiltz, K.Z. Pietrzak, D. Venturi, D. Cash, A. Jain, Journal of Cryptology 30 (2017) 1238–1275.
[Submitted Version]
View
| Files available
| DOI
| WoS
E. Kiltz, K.Z. Pietrzak, D. Venturi, D. Cash, A. Jain, Journal of Cryptology 30 (2017) 1238–1275.