---
_id: '1643'
abstract:
- lang: eng
text: We extend the notion of verifiable random functions (VRF) to constrained VRFs,
which generalize the concept of constrained pseudorandom functions, put forward
by Boneh and Waters (Asiacrypt’13), and independently by Kiayias et al. (CCS’13)
and Boyle et al. (PKC’14), who call them delegatable PRFs and functional PRFs,
respectively. In a standard VRF the secret key sk allows one to evaluate a pseudorandom
function at any point of its domain; in addition, it enables computation of a
non-interactive proof that the function value was computed correctly. In a constrained
VRF from the key sk one can derive constrained keys skS for subsets S of the domain,
which allow computation of function values and proofs only at points in S. After
formally defining constrained VRFs, we derive instantiations from the multilinear-maps-based
constrained PRFs by Boneh and Waters, yielding a VRF with constrained keys for
any set that can be decided by a polynomial-size circuit. Our VRFs have the same
function values as the Boneh-Waters PRFs and are proved secure under the same
hardness assumption, showing that verifiability comes at no cost. Constrained
(functional) VRFs were stated as an open problem by Boyle et al.
alternative_title:
- LNCS
author:
- first_name: Georg
full_name: Fuchsbauer, Georg
id: 46B4C3EE-F248-11E8-B48F-1D18A9856A87
last_name: Fuchsbauer
citation:
ama: 'Fuchsbauer G. Constrained Verifiable Random Functions . In: Abdalla M, De
Prisco R, eds. SCN 2014. Vol 8642. Springer; 2014:95-114. doi:10.1007/978-3-319-10879-7_7'
apa: 'Fuchsbauer, G. (2014). Constrained Verifiable Random Functions . In M. Abdalla
& R. De Prisco (Eds.), SCN 2014 (Vol. 8642, pp. 95–114). Amalfi, Italy:
Springer. https://doi.org/10.1007/978-3-319-10879-7_7'
chicago: Fuchsbauer, Georg. “Constrained Verifiable Random Functions .” In SCN
2014, edited by Michel Abdalla and Roberto De Prisco, 8642:95–114. Springer,
2014. https://doi.org/10.1007/978-3-319-10879-7_7.
ieee: G. Fuchsbauer, “Constrained Verifiable Random Functions ,” in SCN 2014,
Amalfi, Italy, 2014, vol. 8642, pp. 95–114.
ista: 'Fuchsbauer G. 2014. Constrained Verifiable Random Functions . SCN 2014. SCN:
Security and Cryptography for Networks, LNCS, vol. 8642, 95–114.'
mla: Fuchsbauer, Georg. “Constrained Verifiable Random Functions .” SCN 2014,
edited by Michel Abdalla and Roberto De Prisco, vol. 8642, Springer, 2014, pp.
95–114, doi:10.1007/978-3-319-10879-7_7.
short: G. Fuchsbauer, in:, M. Abdalla, R. De Prisco (Eds.), SCN 2014, Springer,
2014, pp. 95–114.
conference:
end_date: 2014-09-05
location: Amalfi, Italy
name: 'SCN: Security and Cryptography for Networks'
start_date: 2014-09-03
date_created: 2018-12-11T11:53:13Z
date_published: 2014-01-01T00:00:00Z
date_updated: 2021-01-12T06:52:12Z
day: '01'
department:
- _id: KrPi
doi: 10.1007/978-3-319-10879-7_7
ec_funded: 1
editor:
- first_name: Michel
full_name: Abdalla, Michel
last_name: Abdalla
- first_name: Roberto
full_name: De Prisco, Roberto
last_name: De Prisco
intvolume: ' 8642'
language:
- iso: eng
main_file_link:
- open_access: '1'
url: http://eprint.iacr.org/2014/537
month: '01'
oa: 1
oa_version: Submitted Version
page: 95 - 114
project:
- _id: 258C570E-B435-11E9-9278-68D0E5697425
call_identifier: FP7
grant_number: '259668'
name: Provable Security for Physical Cryptography
publication: SCN 2014
publication_status: published
publisher: Springer
publist_id: '5509'
scopus_import: 1
status: public
title: 'Constrained Verifiable Random Functions '
type: conference
user_id: 4435EBFC-F248-11E8-B48F-1D18A9856A87
volume: 8642
year: '2014'
...
---
_id: '1907'
abstract:
- lang: eng
text: 'Most cryptographic security proofs require showing that two systems are indistinguishable.
A central tool in such proofs is that of a game, where winning the game means
provoking a certain condition, and it is shown that the two systems considered
cannot be distinguished unless this condition is provoked. Upper bounding the
probability of winning such a game, i.e., provoking this condition, for an arbitrary
strategy is usually hard, except in the special case where the best strategy for
winning such a game is known to be non-adaptive. A sufficient criterion for ensuring
the optimality of non-adaptive strategies is that of conditional equivalence to
a system, a notion introduced in [1]. In this paper, we show that this criterion
is not necessary to ensure the optimality of non-adaptive strategies by giving
two results of independent interest: 1) the optimality of non-adaptive strategies
is not preserved under parallel composition; 2) in contrast, conditional equivalence
is preserved under parallel composition.'
article_number: '6875125'
author:
- first_name: Grégory
full_name: Demay, Grégory
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: Björn
full_name: Tackmann, Björn
last_name: Tackmann
citation:
ama: 'Demay G, Gazi P, Maurer U, Tackmann B. Optimality of non-adaptive strategies:
The case of parallel games. In: IEEE International Symposium on Information
Theory. IEEE; 2014. doi:10.1109/ISIT.2014.6875125'
apa: 'Demay, G., Gazi, P., Maurer, U., & Tackmann, B. (2014). Optimality of
non-adaptive strategies: The case of parallel games. In IEEE International
Symposium on Information Theory. Honolulu, USA: IEEE. https://doi.org/10.1109/ISIT.2014.6875125'
chicago: 'Demay, Grégory, Peter Gazi, Ueli Maurer, and Björn Tackmann. “Optimality
of Non-Adaptive Strategies: The Case of Parallel Games.” In IEEE International
Symposium on Information Theory. IEEE, 2014. https://doi.org/10.1109/ISIT.2014.6875125.'
ieee: 'G. Demay, P. Gazi, U. Maurer, and B. Tackmann, “Optimality of non-adaptive
strategies: The case of parallel games,” in IEEE International Symposium on
Information Theory, Honolulu, USA, 2014.'
ista: 'Demay G, Gazi P, Maurer U, Tackmann B. 2014. Optimality of non-adaptive strategies:
The case of parallel games. IEEE International Symposium on Information Theory.
IEEE International Symposium on Information Theory Proceedings, 6875125.'
mla: 'Demay, Grégory, et al. “Optimality of Non-Adaptive Strategies: The Case of
Parallel Games.” IEEE International Symposium on Information Theory, 6875125,
IEEE, 2014, doi:10.1109/ISIT.2014.6875125.'
short: G. Demay, P. Gazi, U. Maurer, B. Tackmann, in:, IEEE International Symposium
on Information Theory, IEEE, 2014.
conference:
end_date: 2014-07-04
location: Honolulu, USA
name: IEEE International Symposium on Information Theory Proceedings
start_date: 2014-06-29
date_created: 2018-12-11T11:54:39Z
date_published: 2014-01-01T00:00:00Z
date_updated: 2021-01-12T06:53:59Z
day: '01'
department:
- _id: KrPi
doi: 10.1109/ISIT.2014.6875125
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://eprint.iacr.org/2014/299
month: '01'
oa: 1
oa_version: Submitted Version
publication: IEEE International Symposium on Information Theory
publication_status: published
publisher: IEEE
publist_id: '5188'
quality_controlled: '1'
scopus_import: 1
status: public
title: 'Optimality of non-adaptive strategies: The case of parallel games'
type: conference
user_id: 4435EBFC-F248-11E8-B48F-1D18A9856A87
year: '2014'
...
---
_id: '2045'
abstract:
- lang: eng
text: 'We introduce and study a new notion of enhanced chosen-ciphertext security
(ECCA) for public-key encryption. Loosely speaking, in the ECCA security experiment,
the decryption oracle provided to the adversary is augmented to return not only
the output of the decryption algorithm on a queried ciphertext but also of a randomness-recovery
algorithm associated to the scheme. Our results mainly concern the case where
the randomness-recovery algorithm is efficient. We provide constructions of ECCA-secure
encryption from adaptive trapdoor functions as defined by Kiltz et al. (EUROCRYPT
2010), resulting in ECCA encryption from standard number-theoretic assumptions.
We then give two applications of ECCA-secure encryption: (1) We use it as a unifying
concept in showing equivalence of adaptive trapdoor functions and tag-based adaptive
trapdoor functions, resolving an open question of Kiltz et al. (2) We show that
ECCA-secure encryption can be used to securely realize an approach to public-key
encryption with non-interactive opening (PKENO) originally suggested by Damgård
and Thorbek (EUROCRYPT 2007), resulting in new and practical PKENO schemes quite
different from those in prior work. Our results demonstrate that ECCA security
is of both practical and theoretical interest.'
acknowledgement: The second author was supported by EPSRC grant EP/H043454/1.
alternative_title:
- LNCS
author:
- first_name: Dana
full_name: Dachman Soled, Dana
last_name: Dachman Soled
- first_name: Georg
full_name: Fuchsbauer, Georg
id: 46B4C3EE-F248-11E8-B48F-1D18A9856A87
last_name: Fuchsbauer
- first_name: Payman
full_name: Mohassel, Payman
last_name: Mohassel
- first_name: Adam
full_name: O’Neill, Adam
last_name: O’Neill
citation:
ama: 'Dachman Soled D, Fuchsbauer G, Mohassel P, O’Neill A. Enhanced chosen-ciphertext
security and applications. In: Krawczyk H, ed. Lecture Notes in Computer Science
(Including Subseries Lecture Notes in Artificial Intelligence and Lecture Notes
in Bioinformatics). Vol 8383. Springer; 2014:329-344. doi:10.1007/978-3-642-54631-0_19'
apa: 'Dachman Soled, D., Fuchsbauer, G., Mohassel, P., & O’Neill, A. (2014).
Enhanced chosen-ciphertext security and applications. In H. Krawczyk (Ed.), Lecture
Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence
and Lecture Notes in Bioinformatics) (Vol. 8383, pp. 329–344). Buenos Aires,
Argentina: Springer. https://doi.org/10.1007/978-3-642-54631-0_19'
chicago: Dachman Soled, Dana, Georg Fuchsbauer, Payman Mohassel, and Adam O’Neill.
“Enhanced Chosen-Ciphertext Security and Applications.” In Lecture Notes in
Computer Science (Including Subseries Lecture Notes in Artificial Intelligence
and Lecture Notes in Bioinformatics), edited by Hugo Krawczyk, 8383:329–44.
Springer, 2014. https://doi.org/10.1007/978-3-642-54631-0_19.
ieee: D. Dachman Soled, G. Fuchsbauer, P. Mohassel, and A. O’Neill, “Enhanced chosen-ciphertext
security and applications,” in Lecture Notes in Computer Science (including
subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics),
Buenos Aires, Argentina, 2014, vol. 8383, pp. 329–344.
ista: 'Dachman Soled D, Fuchsbauer G, Mohassel P, O’Neill A. 2014. Enhanced chosen-ciphertext
security and applications. Lecture Notes in Computer Science (including subseries
Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics).
PKC: Public Key Crypography, LNCS, vol. 8383, 329–344.'
mla: Dachman Soled, Dana, et al. “Enhanced Chosen-Ciphertext Security and Applications.”
Lecture Notes in Computer Science (Including Subseries Lecture Notes in Artificial
Intelligence and Lecture Notes in Bioinformatics), edited by Hugo Krawczyk,
vol. 8383, Springer, 2014, pp. 329–44, doi:10.1007/978-3-642-54631-0_19.
short: 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.
conference:
end_date: 2014-03-28
location: Buenos Aires, Argentina
name: 'PKC: Public Key Crypography'
start_date: 2014-03-26
date_created: 2018-12-11T11:55:24Z
date_published: 2014-01-01T00:00:00Z
date_updated: 2021-01-12T06:54:57Z
day: '01'
department:
- _id: KrPi
doi: 10.1007/978-3-642-54631-0_19
ec_funded: 1
editor:
- first_name: Hugo
full_name: Krawczyk, Hugo
last_name: Krawczyk
intvolume: ' 8383'
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://eprint.iacr.org/2012/543
month: '01'
oa: 1
oa_version: Submitted Version
page: 329 - 344
project:
- _id: 258C570E-B435-11E9-9278-68D0E5697425
call_identifier: FP7
grant_number: '259668'
name: Provable Security for Physical Cryptography
publication: Lecture Notes in Computer Science (including subseries Lecture Notes
in Artificial Intelligence and Lecture Notes in Bioinformatics)
publication_status: published
publisher: Springer
publist_id: '5006'
quality_controlled: '1'
scopus_import: 1
status: public
title: Enhanced chosen-ciphertext security and applications
type: conference
user_id: 4435EBFC-F248-11E8-B48F-1D18A9856A87
volume: 8383
year: '2014'
...
---
_id: '2046'
abstract:
- lang: eng
text: 'We introduce policy-based signatures (PBS), where a signer can only sign
messages conforming to some authority-specified policy. The main requirements
are unforgeability and privacy, the latter meaning that signatures not reveal
the policy. PBS offers value along two fronts: (1) On the practical side, they
allow a corporation to control what messages its employees can sign under the
corporate key. (2) On the theoretical side, they unify existing work, capturing
other forms of signatures as special cases or allowing them to be easily built.
Our work focuses on definitions of PBS, proofs that this challenging primitive
is realizable for arbitrary policies, efficient constructions for specific policies,
and a few representative applications.'
acknowledgement: Part of his work was done while at Bristol University, supported
by EPSRC grant EP/H043454/1.
alternative_title:
- LNCS
author:
- first_name: Mihir
full_name: Bellare, Mihir
last_name: Bellare
- first_name: Georg
full_name: Fuchsbauer, Georg
id: 46B4C3EE-F248-11E8-B48F-1D18A9856A87
last_name: Fuchsbauer
citation:
ama: 'Bellare M, Fuchsbauer G. Policy-based signatures. In: Krawczyk H, ed. Lecture
Notes in Computer Science (Including Subseries Lecture Notes in Artificial Intelligence
and Lecture Notes in Bioinformatics). Vol 8383. Springer; 2014:520-537. doi:10.1007/978-3-642-54631-0_30'
apa: 'Bellare, M., & Fuchsbauer, G. (2014). Policy-based signatures. In H. Krawczyk
(Ed.), Lecture Notes in Computer Science (including subseries Lecture Notes
in Artificial Intelligence and Lecture Notes in Bioinformatics) (Vol. 8383,
pp. 520–537). Buenos Aires, Argentina: Springer. https://doi.org/10.1007/978-3-642-54631-0_30'
chicago: Bellare, Mihir, and Georg Fuchsbauer. “Policy-Based Signatures.” In Lecture
Notes in Computer Science (Including Subseries Lecture Notes in Artificial Intelligence
and Lecture Notes in Bioinformatics), edited by Hugo Krawczyk, 8383:520–37.
Springer, 2014. https://doi.org/10.1007/978-3-642-54631-0_30.
ieee: M. Bellare and G. Fuchsbauer, “Policy-based signatures,” in Lecture Notes
in Computer Science (including subseries Lecture Notes in Artificial Intelligence
and Lecture Notes in Bioinformatics), Buenos Aires, Argentina, 2014, vol.
8383, pp. 520–537.
ista: 'Bellare M, Fuchsbauer G. 2014. Policy-based signatures. Lecture Notes in
Computer Science (including subseries Lecture Notes in Artificial Intelligence
and Lecture Notes in Bioinformatics). PKC: Public Key Crypography, LNCS, vol.
8383, 520–537.'
mla: Bellare, Mihir, and Georg Fuchsbauer. “Policy-Based Signatures.” Lecture
Notes in Computer Science (Including Subseries Lecture Notes in Artificial Intelligence
and Lecture Notes in Bioinformatics), edited by Hugo Krawczyk, vol. 8383,
Springer, 2014, pp. 520–37, doi:10.1007/978-3-642-54631-0_30.
short: 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.
conference:
end_date: 2014-05-28
location: Buenos Aires, Argentina
name: 'PKC: Public Key Crypography'
start_date: 2014-05-26
date_created: 2018-12-11T11:55:24Z
date_published: 2014-01-01T00:00:00Z
date_updated: 2021-01-12T06:54:57Z
day: '01'
department:
- _id: KrPi
doi: 10.1007/978-3-642-54631-0_30
ec_funded: 1
editor:
- first_name: Hugo
full_name: Krawczyk, Hugo
last_name: Krawczyk
intvolume: ' 8383'
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://eprint.iacr.org/2013/413
month: '01'
oa: 1
oa_version: Submitted Version
page: 520 - 537
project:
- _id: 258C570E-B435-11E9-9278-68D0E5697425
call_identifier: FP7
grant_number: '259668'
name: Provable Security for Physical Cryptography
publication: Lecture Notes in Computer Science (including subseries Lecture Notes
in Artificial Intelligence and Lecture Notes in Bioinformatics)
publication_status: published
publisher: Springer
publist_id: '5005'
quality_controlled: '1'
scopus_import: 1
status: public
title: Policy-based signatures
type: conference
user_id: 4435EBFC-F248-11E8-B48F-1D18A9856A87
volume: 8383
year: '2014'
...
---
_id: '2047'
abstract:
- lang: eng
text: Following the publication of an attack on genome-wide association studies
(GWAS) data proposed by Homer et al., considerable attention has been given to
developing methods for releasing GWAS data in a privacy-preserving way. Here,
we develop an end-to-end differentially private method for solving regression
problems with convex penalty functions and selecting the penalty parameters by
cross-validation. In particular, we focus on penalized logistic regression with
elastic-net regularization, a method widely used to in GWAS analyses to identify
disease-causing genes. We show how a differentially private procedure for penalized
logistic regression with elastic-net regularization can be applied to the analysis
of GWAS data and evaluate our method’s performance.
acknowledgement: This research was partially supported by BCS- 0941518 to the Department
of Statistics at Carnegie Mellon University.
alternative_title:
- LNCS
arxiv: 1
author:
- first_name: Fei
full_name: Yu, Fei
last_name: Yu
- first_name: Michal
full_name: Rybar, Michal
id: 2B3E3DE8-F248-11E8-B48F-1D18A9856A87
last_name: Rybar
- first_name: Caroline
full_name: Uhler, Caroline
id: 49ADD78E-F248-11E8-B48F-1D18A9856A87
last_name: Uhler
orcid: 0000-0002-7008-0216
- first_name: Stephen
full_name: Fienberg, Stephen
last_name: Fienberg
citation:
ama: 'Yu F, Rybar M, Uhler C, Fienberg S. Differentially-private logistic regression
for detecting multiple-SNP association in GWAS databases. In: Domingo Ferrer J,
ed. Lecture Notes in Computer Science (Including Subseries Lecture Notes in
Artificial Intelligence and Lecture Notes in Bioinformatics). Vol 8744. Springer;
2014:170-184. doi:10.1007/978-3-319-11257-2_14'
apa: 'Yu, F., Rybar, M., Uhler, C., & Fienberg, S. (2014). Differentially-private
logistic regression for detecting multiple-SNP association in GWAS databases.
In J. Domingo Ferrer (Ed.), Lecture Notes in Computer Science (including subseries
Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
(Vol. 8744, pp. 170–184). Ibiza, Spain: Springer. https://doi.org/10.1007/978-3-319-11257-2_14'
chicago: Yu, Fei, Michal Rybar, Caroline Uhler, and Stephen Fienberg. “Differentially-Private
Logistic Regression for Detecting Multiple-SNP Association in GWAS Databases.”
In Lecture Notes in Computer Science (Including Subseries Lecture Notes in
Artificial Intelligence and Lecture Notes in Bioinformatics), edited by Josep
Domingo Ferrer, 8744:170–84. Springer, 2014. https://doi.org/10.1007/978-3-319-11257-2_14.
ieee: F. Yu, M. Rybar, C. Uhler, and S. Fienberg, “Differentially-private logistic
regression for detecting multiple-SNP association in GWAS databases,” in Lecture
Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence
and Lecture Notes in Bioinformatics), Ibiza, Spain, 2014, vol. 8744, pp. 170–184.
ista: 'Yu F, Rybar M, Uhler C, Fienberg S. 2014. Differentially-private logistic
regression for detecting multiple-SNP association in GWAS databases. Lecture Notes
in Computer Science (including subseries Lecture Notes in Artificial Intelligence
and Lecture Notes in Bioinformatics). PSD: Privacy in Statistical Databases, LNCS,
vol. 8744, 170–184.'
mla: Yu, Fei, et al. “Differentially-Private Logistic Regression for Detecting Multiple-SNP
Association in GWAS Databases.” Lecture Notes in Computer Science (Including
Subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics),
edited by Josep Domingo Ferrer, vol. 8744, Springer, 2014, pp. 170–84, doi:10.1007/978-3-319-11257-2_14.
short: F. Yu, M. Rybar, C. Uhler, S. Fienberg, in:, J. Domingo Ferrer (Ed.), Lecture
Notes in Computer Science (Including Subseries Lecture Notes in Artificial Intelligence
and Lecture Notes in Bioinformatics), Springer, 2014, pp. 170–184.
conference:
end_date: 2014-09-19
location: Ibiza, Spain
name: 'PSD: Privacy in Statistical Databases'
start_date: 2014-09-17
date_created: 2018-12-11T11:55:24Z
date_published: 2014-01-01T00:00:00Z
date_updated: 2021-01-12T06:54:57Z
day: '01'
department:
- _id: KrPi
- _id: CaUh
doi: 10.1007/978-3-319-11257-2_14
editor:
- first_name: Josep
full_name: Domingo Ferrer, Josep
last_name: Domingo Ferrer
external_id:
arxiv:
- '1407.8067'
intvolume: ' 8744'
language:
- iso: eng
main_file_link:
- open_access: '1'
url: http://arxiv.org/abs/1407.8067
month: '01'
oa: 1
oa_version: Submitted Version
page: 170 - 184
project:
- _id: 25636330-B435-11E9-9278-68D0E5697425
grant_number: 11-NSF-1070
name: ROOTS Genome-wide Analysis of Root Traits
publication: Lecture Notes in Computer Science (including subseries Lecture Notes
in Artificial Intelligence and Lecture Notes in Bioinformatics)
publication_status: published
publisher: Springer
publist_id: '5004'
quality_controlled: '1'
scopus_import: 1
status: public
title: Differentially-private logistic regression for detecting multiple-SNP association
in GWAS databases
type: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 8744
year: '2014'
...
---
_id: '2082'
abstract:
- lang: eng
text: 'NMAC is a mode of operation which turns a fixed input-length keyed hash function
f into a variable input-length function. A practical single-key variant of NMAC
called HMAC is a very popular and widely deployed message authentication code
(MAC). Security proofs and attacks for NMAC can typically be lifted to HMAC. NMAC
was introduced by Bellare, Canetti and Krawczyk [Crypto''96], who proved it to
be a secure pseudorandom function (PRF), and thus also a MAC, assuming that (1)
f is a PRF and (2) the function we get when cascading f is weakly collision-resistant.
Unfortunately, HMAC is typically instantiated with cryptographic hash functions
like MD5 or SHA-1 for which (2) has been found to be wrong. To restore the provable
guarantees for NMAC, Bellare [Crypto''06] showed its security based solely on
the assumption that f is a PRF, albeit via a non-uniform reduction. - Our first
contribution is a simpler and uniform proof for this fact: If f is an ε-secure
PRF (against q queries) and a δ-non-adaptively secure PRF (against q queries),
then NMAC f is an (ε+ℓqδ)-secure PRF against q queries of length at most ℓ blocks
each. - We then show that this ε+ℓqδ bound is basically tight. For the most interesting
case where ℓqδ ≥ ε we prove this by constructing an f for which an attack with
advantage ℓqδ exists. This also violates the bound O(ℓε) on the PRF-security of
NMAC recently claimed by Koblitz and Menezes. - Finally, we analyze the PRF-security
of a modification of NMAC called NI [An and Bellare, Crypto''99] that differs
mainly by using a compression function with an additional keying input. This avoids
the constant rekeying on multi-block messages in NMAC and allows for a security
proof starting by the standard switch from a PRF to a random function, followed
by an information-theoretic analysis. We carry out such an analysis, obtaining
a tight ℓq2/2 c bound for this step, improving over the trivial bound of ℓ2q2/2c.
The proof borrows combinatorial techniques originally developed for proving the
security of CBC-MAC [Bellare et al., Crypto''05].'
alternative_title:
- LNCS
author:
- first_name: Peter
full_name: Gazi, Peter
id: 3E0BFE38-F248-11E8-B48F-1D18A9856A87
last_name: Gazi
- first_name: Krzysztof Z
full_name: Pietrzak, Krzysztof Z
id: 3E04A7AA-F248-11E8-B48F-1D18A9856A87
last_name: Pietrzak
orcid: 0000-0002-9139-1654
- first_name: Michal
full_name: Rybar, Michal
id: 2B3E3DE8-F248-11E8-B48F-1D18A9856A87
last_name: Rybar
citation:
ama: 'Gazi P, Pietrzak KZ, Rybar M. The exact PRF-security of NMAC and HMAC. In:
Garay J, Gennaro R, eds. Vol 8616. Springer; 2014:113-130. doi:10.1007/978-3-662-44371-2_7'
apa: 'Gazi, P., Pietrzak, K. Z., & Rybar, M. (2014). The exact PRF-security
of NMAC and HMAC. In J. Garay & R. Gennaro (Eds.) (Vol. 8616, pp. 113–130).
Presented at the CRYPTO: International Cryptology Conference, Santa Barbara, USA:
Springer. https://doi.org/10.1007/978-3-662-44371-2_7'
chicago: Gazi, Peter, Krzysztof Z Pietrzak, and Michal Rybar. “The Exact PRF-Security
of NMAC and HMAC.” edited by Juan Garay and Rosario Gennaro, 8616:113–30. Springer,
2014. https://doi.org/10.1007/978-3-662-44371-2_7.
ieee: 'P. Gazi, K. Z. Pietrzak, and M. Rybar, “The exact PRF-security of NMAC and
HMAC,” presented at the CRYPTO: International Cryptology Conference, Santa Barbara,
USA, 2014, vol. 8616, no. 1, pp. 113–130.'
ista: 'Gazi P, Pietrzak KZ, Rybar M. 2014. The exact PRF-security of NMAC and HMAC.
CRYPTO: International Cryptology Conference, LNCS, vol. 8616, 113–130.'
mla: Gazi, Peter, et al. The Exact PRF-Security of NMAC and HMAC. Edited
by Juan Garay and Rosario Gennaro, vol. 8616, no. 1, Springer, 2014, pp. 113–30,
doi:10.1007/978-3-662-44371-2_7.
short: P. Gazi, K.Z. Pietrzak, M. Rybar, in:, J. Garay, R. Gennaro (Eds.), Springer,
2014, pp. 113–130.
conference:
end_date: 2014-08-21
location: Santa Barbara, USA
name: 'CRYPTO: International Cryptology Conference'
start_date: 2014-08-17
date_created: 2018-12-11T11:55:36Z
date_published: 2014-01-01T00:00:00Z
date_updated: 2023-09-07T12:02:27Z
day: '01'
ddc:
- '000'
- '004'
department:
- _id: KrPi
doi: 10.1007/978-3-662-44371-2_7
ec_funded: 1
editor:
- first_name: Juan
full_name: Garay, Juan
last_name: Garay
- first_name: Rosario
full_name: Gennaro, Rosario
last_name: Gennaro
file:
- access_level: open_access
checksum: dab6ab36a5f6af94f2b597e6404ed11d
content_type: application/pdf
creator: system
date_created: 2018-12-12T10:13:17Z
date_updated: 2020-07-14T12:45:28Z
file_id: '4999'
file_name: IST-2016-682-v1+1_578.pdf
file_size: 492310
relation: main_file
file_date_updated: 2020-07-14T12:45:28Z
has_accepted_license: '1'
intvolume: ' 8616'
issue: '1'
language:
- iso: eng
month: '01'
oa: 1
oa_version: Submitted Version
page: 113 - 130
project:
- _id: 258C570E-B435-11E9-9278-68D0E5697425
call_identifier: FP7
grant_number: '259668'
name: Provable Security for Physical Cryptography
publication_status: published
publisher: Springer
publist_id: '4955'
pubrep_id: '682'
quality_controlled: '1'
related_material:
record:
- id: '838'
relation: dissertation_contains
status: public
status: public
title: The exact PRF-security of NMAC and HMAC
type: conference
user_id: 4435EBFC-F248-11E8-B48F-1D18A9856A87
volume: 8616
year: '2014'
...
---
_id: '2185'
abstract:
- lang: eng
text: 'We revisit the classical problem of converting an imperfect source of randomness
into a usable cryptographic key. Assume that we have some cryptographic application
P that expects a uniformly random m-bit key R and ensures that the best attack
(in some complexity class) against P(R) has success probability at most δ. Our
goal is to design a key-derivation function (KDF) h that converts any random source
X of min-entropy k into a sufficiently "good" key h(X), guaranteeing
that P(h(X)) has comparable security δ′ which is ''close'' to δ. Seeded randomness
extractors provide a generic way to solve this problem for all applications P,
with resulting security δ′ = O(δ), provided that we start with entropy k ≥ m +
2 log (1/δ) - O(1). By a result of Radhakrishnan and Ta-Shma, this bound on k
(called the "RT-bound") is also known to be tight in general. Unfortunately,
in many situations the loss of 2 log (1/δ) bits of entropy is unacceptable. This
motivates the study KDFs with less entropy waste by placing some restrictions
on the source X or the application P. In this work we obtain the following new
positive and negative results in this regard: - Efficient samplability of the
source X does not help beat the RT-bound for general applications. This resolves
the SRT (samplable RT) conjecture of Dachman-Soled et al. [DGKM12] in the affirmative,
and also shows that the existence of computationally-secure extractors beating
the RT-bound implies the existence of one-way functions. - We continue in the
line of work initiated by Barak et al. [BDK+11] and construct new information-theoretic
KDFs which beat the RT-bound for large but restricted classes of applications.
Specifically, we design efficient KDFs that work for all unpredictability applications
P (e.g., signatures, MACs, one-way functions, etc.) and can either: (1) extract
all of the entropy k = m with a very modest security loss δ′ = O(δ·log (1/δ)),
or alternatively, (2) achieve essentially optimal security δ′ = O(δ) with a very
modest entropy loss k ≥ m + loglog (1/δ). In comparison, the best prior results
from [BDK+11] for this class of applications would only guarantee δ′ = O(√δ) when
k = m, and would need k ≥ m + log (1/δ) to get δ′ = O(δ). - The weaker bounds
of [BDK+11] hold for a larger class of so-called "square- friendly"
applications (which includes all unpredictability, but also some important indistinguishability,
applications). Unfortunately, we show that these weaker bounds are tight for the
larger class of applications. - We abstract out a clean, information-theoretic
notion of (k,δ,δ′)- unpredictability extractors, which guarantee "induced"
security δ′ for any δ-secure unpredictability application P, and characterize
the parameters achievable for such unpredictability extractors. Of independent
interest, we also relate this notion to the previously-known notion of (min-entropy)
condensers, and improve the state-of-the-art parameters for such condensers.'
alternative_title:
- LNCS
author:
- first_name: Yevgeniy
full_name: Dodis, Yevgeniy
last_name: Dodis
- first_name: Krzysztof Z
full_name: Pietrzak, Krzysztof Z
id: 3E04A7AA-F248-11E8-B48F-1D18A9856A87
last_name: Pietrzak
orcid: 0000-0002-9139-1654
- first_name: Daniel
full_name: Wichs, Daniel
last_name: Wichs
citation:
ama: 'Dodis Y, Pietrzak KZ, Wichs D. Key derivation without entropy waste. In: Nguyen
P, Oswald E, eds. Vol 8441. Springer; 2014:93-110. doi:10.1007/978-3-642-55220-5_6'
apa: 'Dodis, Y., Pietrzak, K. Z., & Wichs, D. (2014). Key derivation without
entropy waste. In P. Nguyen & E. Oswald (Eds.) (Vol. 8441, pp. 93–110). Presented
at the EUROCRYPT: Theory and Applications of Cryptographic Techniques, Copenhagen,
Denmark: Springer. https://doi.org/10.1007/978-3-642-55220-5_6'
chicago: Dodis, Yevgeniy, Krzysztof Z Pietrzak, and Daniel Wichs. “Key Derivation
without Entropy Waste.” edited by Phong Nguyen and Elisabeth Oswald, 8441:93–110.
Springer, 2014. https://doi.org/10.1007/978-3-642-55220-5_6.
ieee: 'Y. Dodis, K. Z. Pietrzak, and D. Wichs, “Key derivation without entropy waste,”
presented at the EUROCRYPT: Theory and Applications of Cryptographic Techniques,
Copenhagen, Denmark, 2014, vol. 8441, pp. 93–110.'
ista: 'Dodis Y, Pietrzak KZ, Wichs D. 2014. Key derivation without entropy waste.
EUROCRYPT: Theory and Applications of Cryptographic Techniques, LNCS, vol. 8441,
93–110.'
mla: Dodis, Yevgeniy, et al. Key Derivation without Entropy Waste. Edited
by Phong Nguyen and Elisabeth Oswald, vol. 8441, Springer, 2014, pp. 93–110, doi:10.1007/978-3-642-55220-5_6.
short: Y. Dodis, K.Z. Pietrzak, D. Wichs, in:, P. Nguyen, E. Oswald (Eds.), Springer,
2014, pp. 93–110.
conference:
end_date: 2014-05-15
location: Copenhagen, Denmark
name: 'EUROCRYPT: Theory and Applications of Cryptographic Techniques'
start_date: 2014-05-11
date_created: 2018-12-11T11:56:12Z
date_published: 2014-04-01T00:00:00Z
date_updated: 2021-01-12T06:55:51Z
day: '01'
ddc:
- '000'
- '004'
department:
- _id: KrPi
doi: 10.1007/978-3-642-55220-5_6
editor:
- first_name: Phong
full_name: Nguyen, Phong
last_name: Nguyen
- first_name: Elisabeth
full_name: Oswald, Elisabeth
last_name: Oswald
file:
- access_level: open_access
checksum: da1aa01221086083b23c92e547b48ff4
content_type: application/pdf
creator: system
date_created: 2018-12-12T10:08:43Z
date_updated: 2020-07-14T12:45:31Z
file_id: '4705'
file_name: IST-2016-680-v1+1_708.pdf
file_size: 505389
relation: main_file
file_date_updated: 2020-07-14T12:45:31Z
has_accepted_license: '1'
intvolume: ' 8441'
language:
- iso: eng
month: '04'
oa: 1
oa_version: Submitted Version
page: 93 - 110
publication_status: published
publisher: Springer
publist_id: '4795'
pubrep_id: '680'
quality_controlled: '1'
scopus_import: 1
status: public
title: Key derivation without entropy waste
type: conference
user_id: 4435EBFC-F248-11E8-B48F-1D18A9856A87
volume: 8441
year: '2014'
...
---
_id: '2219'
abstract:
- lang: eng
text: Recently, Döttling et al. (ASIACRYPT 2012) proposed the first chosen-ciphertext
(IND-CCA) secure public-key encryption scheme from the learning parity with noise
(LPN) assumption. In this work we give an alternative scheme which is conceptually
simpler and more efficient. At the core of our construction is a trapdoor technique
originally proposed for lattices by Micciancio and Peikert (EUROCRYPT 2012), which
we adapt to the LPN setting. The main technical tool is a new double-trapdoor
mechanism, together with a trapdoor switching lemma based on a computational variant
of the leftover hash lemma.
alternative_title:
- LNCS
author:
- first_name: Eike
full_name: Kiltz, Eike
last_name: Kiltz
- first_name: Daniel
full_name: Masny, Daniel
last_name: Masny
- 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: 'Kiltz E, Masny D, Pietrzak KZ. Simple chosen-ciphertext security from low
noise LPN. In: Vol 8383. Springer; 2014:1-18. doi:10.1007/978-3-642-54631-0_1'
apa: 'Kiltz, E., Masny, D., & Pietrzak, K. Z. (2014). Simple chosen-ciphertext
security from low noise LPN (Vol. 8383, pp. 1–18). Presented at the IACR: International
Conference on Practice and Theory in Public-Key Cryptography, Springer. https://doi.org/10.1007/978-3-642-54631-0_1'
chicago: Kiltz, Eike, Daniel Masny, and Krzysztof Z Pietrzak. “Simple Chosen-Ciphertext
Security from Low Noise LPN,” 8383:1–18. Springer, 2014. https://doi.org/10.1007/978-3-642-54631-0_1.
ieee: 'E. Kiltz, D. Masny, and K. Z. Pietrzak, “Simple chosen-ciphertext security
from low noise LPN,” presented at the IACR: International Conference on Practice
and Theory in Public-Key Cryptography, 2014, vol. 8383, pp. 1–18.'
ista: 'Kiltz E, Masny D, Pietrzak KZ. 2014. Simple chosen-ciphertext security from
low noise LPN. IACR: International Conference on Practice and Theory in Public-Key
Cryptography, LNCS, vol. 8383, 1–18.'
mla: Kiltz, Eike, et al. Simple Chosen-Ciphertext Security from Low Noise LPN.
Vol. 8383, Springer, 2014, pp. 1–18, doi:10.1007/978-3-642-54631-0_1.
short: E. Kiltz, D. Masny, K.Z. Pietrzak, in:, Springer, 2014, pp. 1–18.
conference:
name: 'IACR: International Conference on Practice and Theory in Public-Key Cryptography'
date_created: 2018-12-11T11:56:24Z
date_published: 2014-03-01T00:00:00Z
date_updated: 2021-01-12T06:56:05Z
day: '01'
department:
- _id: KrPi
doi: 10.1007/978-3-642-54631-0_1
intvolume: ' 8383'
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://eprint.iacr.org/2015/401
month: '03'
oa: 1
oa_version: Submitted Version
page: 1 - 18
publication_identifier:
isbn:
- 978-364254630-3
publication_status: published
publisher: Springer
publist_id: '4748'
quality_controlled: '1'
scopus_import: 1
status: public
title: Simple chosen-ciphertext security from low noise LPN
type: conference
user_id: 4435EBFC-F248-11E8-B48F-1D18A9856A87
volume: 8383
year: '2014'
...
---
_id: '2236'
abstract:
- lang: eng
text: Consider a joint distribution (X,A) on a set. We show that for any family
of distinguishers, there exists a simulator such that 1 no function in can distinguish
(X,A) from (X,h(X)) with advantage ε, 2 h is only O(2 3ℓ ε -2) times less efficient
than the functions in. For the most interesting settings of the parameters (in
particular, the cryptographic case where X has superlogarithmic min-entropy, ε
> 0 is negligible and consists of circuits of polynomial size), we can make
the simulator h deterministic. As an illustrative application of our theorem,
we give a new security proof for the leakage-resilient stream-cipher from Eurocrypt'09.
Our proof is simpler and quantitatively much better than the original proof using
the dense model theorem, giving meaningful security guarantees if instantiated
with a standard blockcipher like AES. Subsequent to this work, Chung, Lui and
Pass gave an interactive variant of our main theorem, and used it to investigate
weak notions of Zero-Knowledge. Vadhan and Zheng give a more constructive version
of our theorem using their new uniform min-max theorem.
alternative_title:
- LNCS
author:
- first_name: Dimitar
full_name: Jetchev, Dimitar
last_name: Jetchev
- 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: 'Jetchev D, Pietrzak KZ. How to fake auxiliary input. In: Lindell Y, ed. Vol
8349. Springer; 2014:566-590. doi:10.1007/978-3-642-54242-8_24'
apa: 'Jetchev, D., & Pietrzak, K. Z. (2014). How to fake auxiliary input. In
Y. Lindell (Ed.) (Vol. 8349, pp. 566–590). Presented at the TCC: Theory of Cryptography
Conference, San Diego, USA: Springer. https://doi.org/10.1007/978-3-642-54242-8_24'
chicago: Jetchev, Dimitar, and Krzysztof Z Pietrzak. “How to Fake Auxiliary Input.”
edited by Yehuda Lindell, 8349:566–90. Springer, 2014. https://doi.org/10.1007/978-3-642-54242-8_24.
ieee: 'D. Jetchev and K. Z. Pietrzak, “How to fake auxiliary input,” presented at
the TCC: Theory of Cryptography Conference, San Diego, USA, 2014, vol. 8349, pp.
566–590.'
ista: 'Jetchev D, Pietrzak KZ. 2014. How to fake auxiliary input. TCC: Theory of
Cryptography Conference, LNCS, vol. 8349, 566–590.'
mla: Jetchev, Dimitar, and Krzysztof Z. Pietrzak. How to Fake Auxiliary Input.
Edited by Yehuda Lindell, vol. 8349, Springer, 2014, pp. 566–90, doi:10.1007/978-3-642-54242-8_24.
short: D. Jetchev, K.Z. Pietrzak, in:, Y. Lindell (Ed.), Springer, 2014, pp. 566–590.
conference:
end_date: 2014-02-26
location: San Diego, USA
name: 'TCC: Theory of Cryptography Conference'
start_date: 2014-02-24
date_created: 2018-12-11T11:56:29Z
date_published: 2014-02-01T00:00:00Z
date_updated: 2021-01-12T06:56:12Z
day: '01'
ddc:
- '004'
department:
- _id: KrPi
doi: 10.1007/978-3-642-54242-8_24
ec_funded: 1
editor:
- first_name: Yehuda
full_name: Lindell, Yehuda
last_name: Lindell
file:
- access_level: open_access
checksum: 42960325c29dcd8d832edadcc3ce0045
content_type: application/pdf
creator: system
date_created: 2018-12-12T10:17:21Z
date_updated: 2020-07-14T12:45:34Z
file_id: '5275'
file_name: IST-2016-681-v1+1_869_1_.pdf
file_size: 313528
relation: main_file
file_date_updated: 2020-07-14T12:45:34Z
has_accepted_license: '1'
intvolume: ' 8349'
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://repository.ist.ac.at/id/eprint/681
month: '02'
oa: 1
oa_version: Submitted Version
page: 566 - 590
project:
- _id: 258C570E-B435-11E9-9278-68D0E5697425
call_identifier: FP7
grant_number: '259668'
name: Provable Security for Physical Cryptography
publication_identifier:
isbn:
- 978-364254241-1
publication_status: published
publisher: Springer
publist_id: '4725'
pubrep_id: '681'
quality_controlled: '1'
status: public
title: How to fake auxiliary input
type: conference
user_id: 4435EBFC-F248-11E8-B48F-1D18A9856A87
volume: 8349
year: '2014'
...
---
_id: '2852'
abstract:
- lang: eng
text: A robust combiner for hash functions takes two candidate implementations and
constructs a hash function which is secure as long as at least one of the candidates
is secure. So far, hash function combiners only aim at preserving a single property
such as collision-resistance or pseudorandomness. However, when hash functions
are used in protocols like TLS they are often required to provide several properties
simultaneously. We therefore put forward the notion of robust multi-property combiners
and elaborate on different definitions for such combiners. We then propose a combiner
that provably preserves (target) collision-resistance, pseudorandomness, and being
a secure message authentication code. This combiner satisfies the strongest notion
we propose, which requires that the combined function satisfies every security
property which is satisfied by at least one of the underlying hash function. If
the underlying hash functions have output length n, the combiner has output length
2 n. This basically matches a known lower bound for black-box combiners for collision-resistance
only, thus the other properties can be achieved without penalizing the length
of the hash values. We then propose a combiner which also preserves the property
of being indifferentiable from a random oracle, slightly increasing the output
length to 2 n+ω(log n). Moreover, we show how to augment our constructions in
order to make them also robust for the one-wayness property, but in this case
require an a priory upper bound on the input length.
author:
- first_name: Marc
full_name: Fischlin, Marc
last_name: Fischlin
- first_name: Anja
full_name: Lehmann, Anja
last_name: Lehmann
- 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: Fischlin M, Lehmann A, Pietrzak KZ. Robust multi-property combiners for hash
functions. Journal of Cryptology. 2014;27(3):397-428. doi:10.1007/s00145-013-9148-7
apa: Fischlin, M., Lehmann, A., & Pietrzak, K. Z. (2014). Robust multi-property
combiners for hash functions. Journal of Cryptology. Springer. https://doi.org/10.1007/s00145-013-9148-7
chicago: Fischlin, Marc, Anja Lehmann, and Krzysztof Z Pietrzak. “Robust Multi-Property
Combiners for Hash Functions.” Journal of Cryptology. Springer, 2014. https://doi.org/10.1007/s00145-013-9148-7.
ieee: M. Fischlin, A. Lehmann, and K. Z. Pietrzak, “Robust multi-property combiners
for hash functions,” Journal of Cryptology, vol. 27, no. 3. Springer, pp.
397–428, 2014.
ista: Fischlin M, Lehmann A, Pietrzak KZ. 2014. Robust multi-property combiners
for hash functions. Journal of Cryptology. 27(3), 397–428.
mla: Fischlin, Marc, et al. “Robust Multi-Property Combiners for Hash Functions.”
Journal of Cryptology, vol. 27, no. 3, Springer, 2014, pp. 397–428, doi:10.1007/s00145-013-9148-7.
short: M. Fischlin, A. Lehmann, K.Z. Pietrzak, Journal of Cryptology 27 (2014) 397–428.
date_created: 2018-12-11T11:59:56Z
date_published: 2014-07-01T00:00:00Z
date_updated: 2023-02-23T11:17:53Z
day: '01'
department:
- _id: KrPi
doi: 10.1007/s00145-013-9148-7
intvolume: ' 27'
issue: '3'
language:
- iso: eng
month: '07'
oa_version: None
page: 397 - 428
publication: Journal of Cryptology
publication_status: published
publisher: Springer
publist_id: '3940'
quality_controlled: '1'
related_material:
record:
- id: '3225'
relation: earlier_version
status: public
scopus_import: 1
status: public
title: Robust multi-property combiners for hash functions
type: journal_article
user_id: 3FFCCD3A-F248-11E8-B48F-1D18A9856A87
volume: 27
year: '2014'
...
---
_id: '2258'
abstract:
- lang: eng
text: "In a digital signature scheme with message recovery, rather than transmitting
the message m and its signature σ, a single enhanced signature τ is transmitted.
The verifier is able to recover m from τ and at the same time verify its authenticity.
The two most important parameters of such a scheme are its security and overhead
|τ| − |m|. A simple argument shows that for any scheme with “n bits security”
|τ| − |m| ≥ n, i.e., the overhead is lower bounded by the security parameter n.
Currently, the best known constructions in the random oracle model are far from
this lower bound requiring an overhead of n + logq h , where q h is the number
of queries to the random oracle. In this paper we give a construction which basically
matches the n bit lower bound. We propose a simple digital signature scheme with
n + o(logq h ) bits overhead, where q h denotes the number of random oracle queries.\r\n\r\nOur
construction works in two steps. First, we propose a signature scheme with message
recovery having optimal overhead in a new ideal model, the random invertible function
model. Second, we show that a four-round Feistel network with random oracles as
round functions is tightly “public-indifferentiable” from a random invertible
function. At the core of our indifferentiability proof is an almost tight upper
bound for the expected number of edges of the densest “small” subgraph of a random
Cayley graph, which may be of independent interest.\r\n"
alternative_title:
- LNCS
author:
- first_name: Eike
full_name: Kiltz, Eike
last_name: Kiltz
- first_name: Krzysztof Z
full_name: Pietrzak, Krzysztof Z
id: 3E04A7AA-F248-11E8-B48F-1D18A9856A87
last_name: Pietrzak
orcid: 0000-0002-9139-1654
- first_name: Mario
full_name: Szegedy, Mario
last_name: Szegedy
citation:
ama: Kiltz E, Pietrzak KZ, Szegedy M. Digital signatures with minimal overhead from
indifferentiable random invertible functions. 2013;8042:571-588. doi:10.1007/978-3-642-40041-4_31
apa: 'Kiltz, E., Pietrzak, K. Z., & Szegedy, M. (2013). Digital signatures with
minimal overhead from indifferentiable random invertible functions. Presented
at the CRYPTO: International Cryptology Conference, Santa Barbara, CA, United
States: Springer. https://doi.org/10.1007/978-3-642-40041-4_31'
chicago: Kiltz, Eike, Krzysztof Z Pietrzak, and Mario Szegedy. “Digital Signatures
with Minimal Overhead from Indifferentiable Random Invertible Functions.” Lecture
Notes in Computer Science. Springer, 2013. https://doi.org/10.1007/978-3-642-40041-4_31.
ieee: E. Kiltz, K. Z. Pietrzak, and M. Szegedy, “Digital signatures with minimal
overhead from indifferentiable random invertible functions,” vol. 8042. Springer,
pp. 571–588, 2013.
ista: Kiltz E, Pietrzak KZ, Szegedy M. 2013. Digital signatures with minimal overhead
from indifferentiable random invertible functions. 8042, 571–588.
mla: Kiltz, Eike, et al. Digital Signatures with Minimal Overhead from Indifferentiable
Random Invertible Functions. Vol. 8042, Springer, 2013, pp. 571–88, doi:10.1007/978-3-642-40041-4_31.
short: E. Kiltz, K.Z. Pietrzak, M. Szegedy, 8042 (2013) 571–588.
conference:
end_date: 2013-08-22
location: Santa Barbara, CA, United States
name: 'CRYPTO: International Cryptology Conference'
start_date: 2013-08-18
date_created: 2018-12-11T11:56:37Z
date_published: 2013-01-01T00:00:00Z
date_updated: 2021-01-12T06:56:21Z
day: '01'
ddc:
- '000'
- '004'
department:
- _id: KrPi
doi: 10.1007/978-3-642-40041-4_31
ec_funded: 1
file:
- access_level: open_access
checksum: 18a3f602cb41de184dc0e16a0e907633
content_type: application/pdf
creator: system
date_created: 2018-12-12T10:09:20Z
date_updated: 2020-07-14T12:45:35Z
file_id: '4744'
file_name: IST-2016-685-v1+1_658.pdf
file_size: 493175
relation: main_file
file_date_updated: 2020-07-14T12:45:35Z
has_accepted_license: '1'
intvolume: ' 8042'
language:
- iso: eng
month: '01'
oa: 1
oa_version: Submitted Version
page: 571 - 588
project:
- _id: 258C570E-B435-11E9-9278-68D0E5697425
call_identifier: FP7
grant_number: '259668'
name: Provable Security for Physical Cryptography
publication_status: published
publisher: Springer
publist_id: '4688'
pubrep_id: '685'
quality_controlled: '1'
scopus_import: 1
series_title: Lecture Notes in Computer Science
status: public
title: Digital signatures with minimal overhead from indifferentiable random invertible
functions
type: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 8042
year: '2013'
...
---
_id: '2259'
abstract:
- lang: eng
text: "The learning with rounding (LWR) problem, introduced by Banerjee, Peikert
and Rosen at EUROCRYPT ’12, is a variant of learning with errors (LWE), where
one replaces random errors with deterministic rounding. The LWR problem was shown
to be as hard as LWE for a setting of parameters where the modulus and modulus-to-error
ratio are super-polynomial. In this work we resolve the main open problem and
give a new reduction that works for a larger range of parameters, allowing for
a polynomial modulus and modulus-to-error ratio. In particular, a smaller modulus
gives us greater efficiency, and a smaller modulus-to-error ratio gives us greater
security, which now follows from the worst-case hardness of GapSVP with polynomial
(rather than super-polynomial) approximation factors.\r\n\r\nAs a tool in the
reduction, we show that there is a “lossy mode” for the LWR problem, in which
LWR samples only reveal partial information about the secret. This property gives
us several interesting new applications, including a proof that LWR remains secure
with weakly random secrets of sufficient min-entropy, and very simple constructions
of deterministic encryption, lossy trapdoor functions and reusable extractors.\r\n\r\nOur
approach is inspired by a technique of Goldwasser et al. from ICS ’10, which implicitly
showed the existence of a “lossy mode” for LWE. By refining this technique, we
also improve on the parameters of that work to only requiring a polynomial (instead
of super-polynomial) modulus and modulus-to-error ratio.\r\n"
alternative_title:
- LNCS
author:
- first_name: Joel F
full_name: Alwen, Joel F
id: 2A8DFA8C-F248-11E8-B48F-1D18A9856A87
last_name: Alwen
- first_name: Stephan
full_name: Krenn, Stephan
id: 329FCCF0-F248-11E8-B48F-1D18A9856A87
last_name: Krenn
orcid: 0000-0003-2835-9093
- first_name: Krzysztof Z
full_name: Pietrzak, Krzysztof Z
id: 3E04A7AA-F248-11E8-B48F-1D18A9856A87
last_name: Pietrzak
orcid: 0000-0002-9139-1654
- first_name: Daniel
full_name: Wichs, Daniel
last_name: Wichs
citation:
ama: 'Alwen JF, Krenn S, Pietrzak KZ, Wichs D. Learning with rounding, revisited:
New reduction properties and applications. 2013;8042(1):57-74. doi:10.1007/978-3-642-40041-4_4'
apa: 'Alwen, J. F., Krenn, S., Pietrzak, K. Z., & Wichs, D. (2013). Learning
with rounding, revisited: New reduction properties and applications. Presented
at the CRYPTO: International Cryptology Conference, Santa Barbara, CA, United
States: Springer. https://doi.org/10.1007/978-3-642-40041-4_4'
chicago: 'Alwen, Joel F, Stephan Krenn, Krzysztof Z Pietrzak, and Daniel Wichs.
“Learning with Rounding, Revisited: New Reduction Properties and Applications.”
Lecture Notes in Computer Science. Springer, 2013. https://doi.org/10.1007/978-3-642-40041-4_4.'
ieee: 'J. F. Alwen, S. Krenn, K. Z. Pietrzak, and D. Wichs, “Learning with rounding,
revisited: New reduction properties and applications,” vol. 8042, no. 1. Springer,
pp. 57–74, 2013.'
ista: 'Alwen JF, Krenn S, Pietrzak KZ, Wichs D. 2013. Learning with rounding, revisited:
New reduction properties and applications. 8042(1), 57–74.'
mla: 'Alwen, Joel F., et al. Learning with Rounding, Revisited: New Reduction
Properties and Applications. Vol. 8042, no. 1, Springer, 2013, pp. 57–74,
doi:10.1007/978-3-642-40041-4_4.'
short: J.F. Alwen, S. Krenn, K.Z. Pietrzak, D. Wichs, 8042 (2013) 57–74.
conference:
end_date: 2013-08-22
location: Santa Barbara, CA, United States
name: 'CRYPTO: International Cryptology Conference'
start_date: 2013-08-18
date_created: 2018-12-11T11:56:37Z
date_published: 2013-01-01T00:00:00Z
date_updated: 2021-01-12T06:56:21Z
day: '01'
ddc:
- '000'
- '004'
department:
- _id: KrPi
doi: 10.1007/978-3-642-40041-4_4
ec_funded: 1
file:
- access_level: open_access
checksum: 16d428408a806b8e49eecc607deab115
content_type: application/pdf
creator: system
date_created: 2018-12-12T10:11:55Z
date_updated: 2020-07-14T12:45:35Z
file_id: '4912'
file_name: IST-2016-684-v1+1_098.pdf
file_size: 587898
relation: main_file
file_date_updated: 2020-07-14T12:45:35Z
has_accepted_license: '1'
intvolume: ' 8042'
issue: '1'
language:
- iso: eng
month: '01'
oa: 1
oa_version: Published Version
page: 57 - 74
project:
- _id: 258C570E-B435-11E9-9278-68D0E5697425
call_identifier: FP7
grant_number: '259668'
name: Provable Security for Physical Cryptography
publication_status: published
publisher: Springer
publist_id: '4687'
pubrep_id: '684'
quality_controlled: '1'
scopus_import: 1
series_title: Lecture Notes in Computer Science
status: public
title: 'Learning with rounding, revisited: New reduction properties and applications'
type: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 8042
year: '2013'
...
---
_id: '2260'
abstract:
- lang: eng
text: "Direct Anonymous Attestation (DAA) is one of the most complex cryptographic
protocols deployed in practice. It allows an embedded secure processor known as
a Trusted Platform Module (TPM) to attest to the configuration of its host computer
without violating the owner’s privacy. DAA has been standardized by the Trusted
Computing Group and ISO/IEC.\r\n\r\nThe security of the DAA standard and all existing
schemes is analyzed in the random-oracle model. We provide the first constructions
of DAA in the standard model, that is, without relying on random oracles. Our
constructions use new building blocks, including the first efficient signatures
of knowledge in the standard model, which have many applications beyond DAA.\r\n"
alternative_title:
- LNCS
author:
- first_name: David
full_name: Bernhard, David
last_name: Bernhard
- first_name: Georg
full_name: Fuchsbauer, Georg
id: 46B4C3EE-F248-11E8-B48F-1D18A9856A87
last_name: Fuchsbauer
- first_name: Essam
full_name: Ghadafi, Essam
last_name: Ghadafi
citation:
ama: Bernhard D, Fuchsbauer G, Ghadafi E. Efficient signatures of knowledge and
DAA in the standard model. 2013;7954:518-533. doi:10.1007/978-3-642-38980-1_33
apa: 'Bernhard, D., Fuchsbauer, G., & Ghadafi, E. (2013). Efficient signatures
of knowledge and DAA in the standard model. Presented at the ACNS: Applied Cryptography
and Network Security, Banff, AB, Canada: Springer. https://doi.org/10.1007/978-3-642-38980-1_33'
chicago: Bernhard, David, Georg Fuchsbauer, and Essam Ghadafi. “Efficient Signatures
of Knowledge and DAA in the Standard Model.” Lecture Notes in Computer Science.
Springer, 2013. https://doi.org/10.1007/978-3-642-38980-1_33.
ieee: D. Bernhard, G. Fuchsbauer, and E. Ghadafi, “Efficient signatures of knowledge
and DAA in the standard model,” vol. 7954. Springer, pp. 518–533, 2013.
ista: Bernhard D, Fuchsbauer G, Ghadafi E. 2013. Efficient signatures of knowledge
and DAA in the standard model. 7954, 518–533.
mla: Bernhard, David, et al. Efficient Signatures of Knowledge and DAA in the
Standard Model. Vol. 7954, Springer, 2013, pp. 518–33, doi:10.1007/978-3-642-38980-1_33.
short: D. Bernhard, G. Fuchsbauer, E. Ghadafi, 7954 (2013) 518–533.
conference:
end_date: 2013-06-28
location: Banff, AB, Canada
name: 'ACNS: Applied Cryptography and Network Security'
start_date: 2013-06-25
date_created: 2018-12-11T11:56:37Z
date_published: 2013-06-01T00:00:00Z
date_updated: 2020-08-11T10:09:44Z
day: '01'
department:
- _id: KrPi
doi: 10.1007/978-3-642-38980-1_33
intvolume: ' 7954'
language:
- iso: eng
main_file_link:
- open_access: '1'
url: http://eprint.iacr.org/2012/475
month: '06'
oa: 1
oa_version: Submitted Version
page: 518 - 533
publication_status: published
publisher: Springer
publist_id: '4686'
quality_controlled: '1'
scopus_import: 1
series_title: Lecture Notes in Computer Science
status: public
title: Efficient signatures of knowledge and DAA in the standard model
type: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 7954
year: '2013'
...
---
_id: '2274'
abstract:
- lang: eng
text: "Proofs of work (PoW) have been suggested by Dwork and Naor (Crypto'92) as
protection to a shared resource. The basic idea is to ask the service requestor
to dedicate some non-trivial amount of computational work to every request. The
original applications included prevention of spam and protection against denial
of service attacks. More recently, PoWs have been used to prevent double spending
in the Bitcoin digital currency system.\r\n\r\nIn this work, we put forward an
alternative concept for PoWs -- so-called proofs of space (PoS), where a service
requestor must dedicate a significant amount of disk space as opposed to computation.
We construct secure PoS schemes in the random oracle model, using graphs with
high "pebbling complexity" and Merkle hash-trees. "
author:
- first_name: Stefan
full_name: Dziembowski, Stefan
last_name: Dziembowski
- first_name: Sebastian
full_name: Faust, Sebastian
last_name: Faust
- first_name: Vladimir
full_name: Kolmogorov, Vladimir
id: 3D50B0BA-F248-11E8-B48F-1D18A9856A87
last_name: Kolmogorov
- 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: Dziembowski S, Faust S, Kolmogorov V, Pietrzak KZ. Proofs of Space.
IST Austria; 2013.
apa: Dziembowski, S., Faust, S., Kolmogorov, V., & Pietrzak, K. Z. (2013). Proofs
of Space. IST Austria.
chicago: Dziembowski, Stefan, Sebastian Faust, Vladimir Kolmogorov, and Krzysztof
Z Pietrzak. Proofs of Space. IST Austria, 2013.
ieee: S. Dziembowski, S. Faust, V. Kolmogorov, and K. Z. Pietrzak, Proofs of
Space. IST Austria, 2013.
ista: Dziembowski S, Faust S, Kolmogorov V, Pietrzak KZ. 2013. Proofs of Space,
IST Austria,p.
mla: Dziembowski, Stefan, et al. Proofs of Space. IST Austria, 2013.
short: S. Dziembowski, S. Faust, V. Kolmogorov, K.Z. Pietrzak, Proofs of Space,
IST Austria, 2013.
date_created: 2018-12-11T11:56:42Z
date_published: 2013-11-28T00:00:00Z
date_updated: 2023-02-23T10:09:33Z
day: '28'
ddc:
- '530'
department:
- _id: VlKo
- _id: KrPi
file:
- access_level: open_access
checksum: 37b61637b62fc079d9141c59d9f1a94f
content_type: application/pdf
creator: system
date_created: 2018-12-12T10:16:11Z
date_updated: 2020-07-14T12:45:36Z
file_id: '5197'
file_name: IST-2016-671-v1+1_796.pdf
file_size: 405870
relation: main_file
file_date_updated: 2020-07-14T12:45:36Z
has_accepted_license: '1'
language:
- iso: eng
month: '11'
oa: 1
oa_version: Published Version
publication_status: published
publisher: IST Austria
publist_id: '4670'
pubrep_id: '671'
related_material:
record:
- id: '1675'
relation: later_version
status: public
scopus_import: 1
status: public
title: Proofs of Space
type: report
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
year: '2013'
...
---
_id: '2291'
abstract:
- lang: eng
text: "Cryptographic access control promises to offer easily distributed trust and
broader applicability, while reducing reliance on low-level online monitors. Traditional
implementations of cryptographic access control rely on simple cryptographic primitives
whereas recent endeavors employ primitives with richer functionality and security
guarantees. Worryingly, few of the existing cryptographic access-control schemes
come with precise guarantees, the gap between the policy specification and the
implementation being analyzed only informally, if at all. In this paper we begin
addressing this shortcoming. Unlike prior work that targeted ad-hoc policy specification,
we look at the well-established Role-Based Access Control (RBAC) model, as used
in a typical file system. In short, we provide a precise syntax for a computational
version of RBAC, offer rigorous definitions for cryptographic policy enforcement
of a large class of RBAC security policies, and demonstrate that an implementation
based on attribute-based encryption meets our security notions. We view our main
contribution as being at the conceptual level. Although we work with RBAC for
concreteness, our general methodology could guide future research for uses of
cryptography in other access-control models. \r\n"
author:
- first_name: Anna
full_name: Ferrara, Anna
last_name: Ferrara
- first_name: Georg
full_name: Fuchsbauer, Georg
id: 46B4C3EE-F248-11E8-B48F-1D18A9856A87
last_name: Fuchsbauer
- first_name: Bogdan
full_name: Warinschi, Bogdan
last_name: Warinschi
citation:
ama: 'Ferrara A, Fuchsbauer G, Warinschi B. Cryptographically enforced RBAC. In:
IEEE; 2013:115-129. doi:10.1109/CSF.2013.15'
apa: 'Ferrara, A., Fuchsbauer, G., & Warinschi, B. (2013). Cryptographically
enforced RBAC (pp. 115–129). Presented at the CSF: Computer Security Foundations,
New Orleans, LA, United States: IEEE. https://doi.org/10.1109/CSF.2013.15'
chicago: Ferrara, Anna, Georg Fuchsbauer, and Bogdan Warinschi. “Cryptographically
Enforced RBAC,” 115–29. IEEE, 2013. https://doi.org/10.1109/CSF.2013.15.
ieee: 'A. Ferrara, G. Fuchsbauer, and B. Warinschi, “Cryptographically enforced
RBAC,” presented at the CSF: Computer Security Foundations, New Orleans, LA, United
States, 2013, pp. 115–129.'
ista: 'Ferrara A, Fuchsbauer G, Warinschi B. 2013. Cryptographically enforced RBAC.
CSF: Computer Security Foundations, 115–129.'
mla: Ferrara, Anna, et al. Cryptographically Enforced RBAC. IEEE, 2013, pp.
115–29, doi:10.1109/CSF.2013.15.
short: A. Ferrara, G. Fuchsbauer, B. Warinschi, in:, IEEE, 2013, pp. 115–129.
conference:
end_date: 2013-09-28
location: New Orleans, LA, United States
name: 'CSF: Computer Security Foundations'
start_date: 2013-09-26
date_created: 2018-12-11T11:56:48Z
date_published: 2013-09-01T00:00:00Z
date_updated: 2021-01-12T06:56:34Z
day: '01'
department:
- _id: KrPi
doi: 10.1109/CSF.2013.15
language:
- iso: eng
main_file_link:
- open_access: '1'
url: http://eprint.iacr.org/2013/492
month: '09'
oa: 1
oa_version: Submitted Version
page: 115 - 129
publication_status: published
publisher: IEEE
publist_id: '4637'
quality_controlled: '1'
scopus_import: 1
status: public
title: Cryptographically enforced RBAC
type: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
year: '2013'
...
---
_id: '2940'
abstract:
- lang: eng
text: "A chain rule for an entropy notion H(.) states that the entropy H(X) of a
variable X decreases by at most l if conditioned on an l-bit string A, i.e., H(X|A)>=
H(X)-l. More generally, it satisfies a chain rule for conditional entropy if H(X|Y,A)>=
H(X|Y)-l.\r\n\r\nAll natural information theoretic entropy notions we are aware
of (like Shannon or min-entropy) satisfy some kind of chain rule for conditional
entropy. Moreover, many computational entropy notions (like Yao entropy, unpredictability
entropy and several variants of HILL entropy) satisfy the chain rule for conditional
entropy, though here not only the quantity decreases by l, but also the quality
of the entropy decreases exponentially in l. However, for \r\nthe standard notion
of conditional HILL entropy (the computational equivalent of min-entropy) the
existence of such a rule was unknown so far.\r\n\r\nIn this paper, we prove that
for conditional HILL entropy no meaningful chain rule exists, assuming the existence
of one-way permutations: there exist distributions X,Y,A, where A is a distribution
over a single bit, but $H(X|Y)>>H(X|Y,A)$, even if we simultaneously allow
for a massive degradation in the quality of the entropy.\r\n\r\nThe idea underlying
our construction is based on a surprising connection between the chain rule for
HILL entropy and deniable encryption. "
alternative_title:
- LNCS
author:
- first_name: Stephan
full_name: Krenn, Stephan
id: 329FCCF0-F248-11E8-B48F-1D18A9856A87
last_name: Krenn
orcid: 0000-0003-2835-9093
- first_name: Krzysztof Z
full_name: Pietrzak, Krzysztof Z
id: 3E04A7AA-F248-11E8-B48F-1D18A9856A87
last_name: Pietrzak
orcid: 0000-0002-9139-1654
- first_name: Akshay
full_name: Wadia, Akshay
last_name: Wadia
citation:
ama: 'Krenn S, Pietrzak KZ, Wadia A. A counterexample to the chain rule for conditional
HILL entropy, and what deniable encryption has to do with it. In: Sahai A, ed.
Vol 7785. Springer; 2013:23-39. doi:10.1007/978-3-642-36594-2_2'
apa: 'Krenn, S., Pietrzak, K. Z., & Wadia, A. (2013). A counterexample to the
chain rule for conditional HILL entropy, and what deniable encryption has to do
with it. In A. Sahai (Ed.) (Vol. 7785, pp. 23–39). Presented at the TCC: Theory
of Cryptography Conference, Tokyo, Japan: Springer. https://doi.org/10.1007/978-3-642-36594-2_2'
chicago: Krenn, Stephan, Krzysztof Z Pietrzak, and Akshay Wadia. “A Counterexample
to the Chain Rule for Conditional HILL Entropy, and What Deniable Encryption Has
to Do with It.” edited by Amit Sahai, 7785:23–39. Springer, 2013. https://doi.org/10.1007/978-3-642-36594-2_2.
ieee: 'S. Krenn, K. Z. Pietrzak, and A. Wadia, “A counterexample to the chain rule
for conditional HILL entropy, and what deniable encryption has to do with it,”
presented at the TCC: Theory of Cryptography Conference, Tokyo, Japan, 2013, vol.
7785, pp. 23–39.'
ista: 'Krenn S, Pietrzak KZ, Wadia A. 2013. A counterexample to the chain rule for
conditional HILL entropy, and what deniable encryption has to do with it. TCC:
Theory of Cryptography Conference, LNCS, vol. 7785, 23–39.'
mla: Krenn, Stephan, et al. A Counterexample to the Chain Rule for Conditional
HILL Entropy, and What Deniable Encryption Has to Do with It. Edited by Amit
Sahai, vol. 7785, Springer, 2013, pp. 23–39, doi:10.1007/978-3-642-36594-2_2.
short: S. Krenn, K.Z. Pietrzak, A. Wadia, in:, A. Sahai (Ed.), Springer, 2013, pp.
23–39.
conference:
end_date: 2013-03-06
location: Tokyo, Japan
name: 'TCC: Theory of Cryptography Conference'
start_date: 2013-03-03
date_created: 2018-12-11T12:00:27Z
date_published: 2013-01-29T00:00:00Z
date_updated: 2023-02-23T10:00:43Z
day: '29'
ddc:
- '000'
department:
- _id: KrPi
doi: 10.1007/978-3-642-36594-2_2
ec_funded: 1
editor:
- first_name: Amit
full_name: Sahai, Amit
last_name: Sahai
file:
- access_level: open_access
checksum: beb0cc1c0579da2d2e84394230a5da78
content_type: application/pdf
creator: dernst
date_created: 2019-01-22T14:11:11Z
date_updated: 2020-07-14T12:45:54Z
file_id: '5875'
file_name: 2013_LNCS_Krenn.pdf
file_size: 414823
relation: main_file
file_date_updated: 2020-07-14T12:45:54Z
has_accepted_license: '1'
intvolume: ' 7785'
language:
- iso: eng
month: '01'
oa: 1
oa_version: Submitted Version
page: 23 - 39
project:
- _id: 258C570E-B435-11E9-9278-68D0E5697425
call_identifier: FP7
grant_number: '259668'
name: Provable Security for Physical Cryptography
publication_status: published
publisher: Springer
publist_id: '3795'
quality_controlled: '1'
related_material:
record:
- id: '1479'
relation: later_version
status: public
scopus_import: 1
status: public
title: A counterexample to the chain rule for conditional HILL entropy, and what deniable
encryption has to do with it
type: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 7785
year: '2013'
...
---
_id: '502'
abstract:
- lang: eng
text: 'Blind signatures allow users to obtain signatures on messages hidden from
the signer; moreover, the signer cannot link the resulting message/signature pair
to the signing session. This paper presents blind signature schemes, in which
the number of interactions between the user and the signer is minimal and whose
blind signatures are short. Our schemes are defined over bilinear groups and are
proved secure in the common-reference-string model without random oracles and
under standard assumptions: CDH and the decision-linear assumption. (We also give
variants over asymmetric groups based on similar assumptions.) The blind signatures
are Waters signatures, which consist of 2 group elements. Moreover, we instantiate
partially blind signatures, where the message consists of a part hidden from the
signer and a commonly known public part, and schemes achieving perfect blindness.
We propose new variants of blind signatures, such as signer-friendly partially
blind signatures, where the public part can be chosen by the signer without prior
agreement, 3-party blind signatures, as well as blind signatures on multiple aggregated
messages provided by independent sources. We also extend Waters signatures to
non-binary alphabets by proving a new result on the underlying hash function. '
author:
- first_name: Olivier
full_name: Blazy, Olivier
last_name: Blazy
- first_name: Georg
full_name: Fuchsbauer, Georg
id: 46B4C3EE-F248-11E8-B48F-1D18A9856A87
last_name: Fuchsbauer
- first_name: David
full_name: Pointcheval, David
last_name: Pointcheval
- first_name: Damien
full_name: Vergnaud, Damien
last_name: Vergnaud
citation:
ama: Blazy O, Fuchsbauer G, Pointcheval D, Vergnaud D. Short blind signatures. Journal
of Computer Security. 2013;21(5):627-661. doi:10.3233/JCS-130477
apa: Blazy, O., Fuchsbauer, G., Pointcheval, D., & Vergnaud, D. (2013). Short
blind signatures. Journal of Computer Security. IOS Press. https://doi.org/10.3233/JCS-130477
chicago: Blazy, Olivier, Georg Fuchsbauer, David Pointcheval, and Damien Vergnaud.
“Short Blind Signatures.” Journal of Computer Security. IOS Press, 2013.
https://doi.org/10.3233/JCS-130477.
ieee: O. Blazy, G. Fuchsbauer, D. Pointcheval, and D. Vergnaud, “Short blind signatures,”
Journal of Computer Security, vol. 21, no. 5. IOS Press, pp. 627–661, 2013.
ista: Blazy O, Fuchsbauer G, Pointcheval D, Vergnaud D. 2013. Short blind signatures.
Journal of Computer Security. 21(5), 627–661.
mla: Blazy, Olivier, et al. “Short Blind Signatures.” Journal of Computer Security,
vol. 21, no. 5, IOS Press, 2013, pp. 627–61, doi:10.3233/JCS-130477.
short: O. Blazy, G. Fuchsbauer, D. Pointcheval, D. Vergnaud, Journal of Computer
Security 21 (2013) 627–661.
date_created: 2018-12-11T11:46:50Z
date_published: 2013-11-22T00:00:00Z
date_updated: 2021-01-12T08:01:09Z
day: '22'
department:
- _id: KrPi
doi: 10.3233/JCS-130477
intvolume: ' 21'
issue: '5'
language:
- iso: eng
month: '11'
oa_version: None
page: 627 - 661
publication: Journal of Computer Security
publication_status: published
publisher: IOS Press
publist_id: '7318'
quality_controlled: '1'
scopus_import: 1
status: public
title: Short blind signatures
type: journal_article
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 21
year: '2013'
...
---
_id: '2048'
abstract:
- lang: eng
text: Leakage resilient cryptography attempts to incorporate side-channel leakage
into the black-box security model and designs cryptographic schemes that are provably
secure within it. Informally, a scheme is leakage-resilient if it remains secure
even if an adversary learns a bounded amount of arbitrary information about the
schemes internal state. Unfortunately, most leakage resilient schemes are unnecessarily
complicated in order to achieve strong provable security guarantees. As advocated
by Yu et al. [CCS’10], this mostly is an artefact of the security proof and in
practice much simpler construction may already suffice to protect against realistic
side-channel attacks. In this paper, we show that indeed for simpler constructions
leakage-resilience can be obtained when we aim for relaxed security notions where
the leakage-functions and/or the inputs to the primitive are chosen non-adaptively.
For example, we show that a three round Feistel network instantiated with a leakage
resilient PRF yields a leakage resilient PRP if the inputs are chosen non-adaptively
(This complements the result of Dodis and Pietrzak [CRYPTO’10] who show that if
a adaptive queries are allowed, a superlogarithmic number of rounds is necessary.)
We also show that a minor variation of the classical GGM construction gives a
leakage resilient PRF if both, the leakage-function and the inputs, are chosen
non-adaptively.
acknowledgement: "Sebastian Faust acknowledges support from the Danish National Research
Foundation and The National Science Foundation of China (under the grant 61061130540)
for the Sino-Danish Center for the Theory of Interactive Computation, within part
of this work was performed; and from the CFEM research center, supported by the
Danish Strategic Research Council. \r\nSupported by the European Research Council/ERC
Starting Grant 259668-PSPC.\r\n"
alternative_title:
- LNCS
author:
- first_name: Sebastian
full_name: Faust, Sebastian
last_name: Faust
- first_name: Krzysztof Z
full_name: Pietrzak, Krzysztof Z
id: 3E04A7AA-F248-11E8-B48F-1D18A9856A87
last_name: Pietrzak
orcid: 0000-0002-9139-1654
- first_name: Joachim
full_name: Schipper, Joachim
id: 7BE863D4-E9CF-11E9-9EDB-90527418172C
last_name: Schipper
citation:
ama: 'Faust S, Pietrzak KZ, Schipper J. Practical leakage-resilient symmetric cryptography.
In: Conference Proceedings CHES 2012. Vol 7428. Springer; 2012:213-232.
doi:10.1007/978-3-642-33027-8_13'
apa: 'Faust, S., Pietrzak, K. Z., & Schipper, J. (2012). Practical leakage-resilient
symmetric cryptography. In Conference proceedings CHES 2012 (Vol. 7428,
pp. 213–232). Leuven, Belgium: Springer. https://doi.org/10.1007/978-3-642-33027-8_13'
chicago: Faust, Sebastian, Krzysztof Z Pietrzak, and Joachim Schipper. “Practical
Leakage-Resilient Symmetric Cryptography.” In Conference Proceedings CHES
2012, 7428:213–32. Springer, 2012. https://doi.org/10.1007/978-3-642-33027-8_13.
ieee: S. Faust, K. Z. Pietrzak, and J. Schipper, “Practical leakage-resilient symmetric
cryptography,” in Conference proceedings CHES 2012, Leuven, Belgium, 2012,
vol. 7428, pp. 213–232.
ista: 'Faust S, Pietrzak KZ, Schipper J. 2012. Practical leakage-resilient symmetric
cryptography. Conference proceedings CHES 2012. CHES: Cryptographic Hardware
and Embedded Systems, LNCS, vol. 7428, 213–232.'
mla: Faust, Sebastian, et al. “Practical Leakage-Resilient Symmetric Cryptography.”
Conference Proceedings CHES 2012, vol. 7428, Springer, 2012, pp. 213–32,
doi:10.1007/978-3-642-33027-8_13.
short: S. Faust, K.Z. Pietrzak, J. Schipper, in:, Conference Proceedings CHES 2012,
Springer, 2012, pp. 213–232.
conference:
end_date: 2012-09-12
location: Leuven, Belgium
name: 'CHES: Cryptographic Hardware and Embedded Systems'
start_date: 2012-09-09
date_created: 2018-12-11T11:55:25Z
date_published: 2012-09-01T00:00:00Z
date_updated: 2021-01-12T06:54:58Z
day: '01'
department:
- _id: KrPi
doi: 10.1007/978-3-642-33027-8_13
ec_funded: 1
intvolume: ' 7428'
language:
- iso: eng
main_file_link:
- open_access: '1'
url: http://www.iacr.org/archive/ches2012/74280211/74280211.pdf
month: '09'
oa: 1
oa_version: Preprint
page: 213 - 232
project:
- _id: 258C570E-B435-11E9-9278-68D0E5697425
call_identifier: FP7
grant_number: '259668'
name: Provable Security for Physical Cryptography
publication: ' Conference proceedings CHES 2012'
publication_status: published
publisher: Springer
publist_id: '5003'
quality_controlled: '1'
scopus_import: 1
status: public
title: Practical leakage-resilient symmetric cryptography
type: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 7428
year: '2012'
...
---
_id: '2049'
abstract:
- lang: eng
text: "We propose a new authentication protocol that is provably secure based on
a ring variant of the learning parity with noise (LPN) problem. The protocol follows
the design principle of the LPN-based protocol from Eurocrypt’11 (Kiltz et al.),
and like it, is a two round protocol secure against active attacks. Moreover,
our protocol has small communication complexity and a very small footprint which
makes it applicable in scenarios that involve low-cost, resource-constrained devices.\r\n\r\nPerformance-wise,
our protocol is more efficient than previous LPN-based schemes, such as the many
variants of the Hopper-Blum (HB) protocol and the aforementioned protocol from
Eurocrypt’11. Our implementation results show that it is even comparable to the
standard challenge-and-response protocols based on the AES block-cipher. Our basic
protocol is roughly 20 times slower than AES, but with the advantage of having
10 times smaller code size. Furthermore, if a few hundred bytes of non-volatile
memory are available to allow the storage of some off-line pre-computations, then
the online phase of our protocols is only twice as slow as AES.\r\n"
acknowledgement: "Supported by the European Research Council / ERC Starting Grant
(259668- PSPC)\r\nWe would like to thank the anonymous referees of this confer-
ence and those of the ECRYPT Workshop on Lightweight Cryptography for very useful
comments, and in particular for the suggestion that the scheme is somewhat vulnerable
to a man-in-the-middle attack whenever an adversary observes two reader challenges
that are the same. We hope that the attack we described in Appendix A corresponds
to what the reviewer had in mind. We also thank Tanja Lange for pointing us to the
pa- per of [Kir11] and for discussions of some of her recent work. "
alternative_title:
- LNCS
author:
- first_name: Stefan
full_name: Heyse, Stefan
last_name: Heyse
- first_name: Eike
full_name: Kiltz, Eike
last_name: Kiltz
- first_name: Vadim
full_name: Lyubashevsky, Vadim
last_name: Lyubashevsky
- first_name: Christof
full_name: Paar, Christof
last_name: Paar
- 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: 'Heyse S, Kiltz E, Lyubashevsky V, Paar C, Pietrzak KZ. Lapin: An efficient
authentication protocol based on ring-LPN. In: Conference Proceedings FSE
2012. Vol 7549. Springer; 2012:346-365. doi:10.1007/978-3-642-34047-5_20'
apa: 'Heyse, S., Kiltz, E., Lyubashevsky, V., Paar, C., & Pietrzak, K. Z. (2012).
Lapin: An efficient authentication protocol based on ring-LPN. In Conference
proceedings FSE 2012 (Vol. 7549, pp. 346–365). Washington, DC, USA: Springer.
https://doi.org/10.1007/978-3-642-34047-5_20'
chicago: 'Heyse, Stefan, Eike Kiltz, Vadim Lyubashevsky, Christof Paar, and Krzysztof
Z Pietrzak. “Lapin: An Efficient Authentication Protocol Based on Ring-LPN.” In
Conference Proceedings FSE 2012, 7549:346–65. Springer, 2012. https://doi.org/10.1007/978-3-642-34047-5_20.'
ieee: 'S. Heyse, E. Kiltz, V. Lyubashevsky, C. Paar, and K. Z. Pietrzak, “Lapin:
An efficient authentication protocol based on ring-LPN,” in Conference proceedings
FSE 2012, Washington, DC, USA, 2012, vol. 7549, pp. 346–365.'
ista: 'Heyse S, Kiltz E, Lyubashevsky V, Paar C, Pietrzak KZ. 2012. Lapin: An efficient
authentication protocol based on ring-LPN. Conference proceedings FSE 2012. FSE:
Fast Software Encryption, LNCS, vol. 7549, 346–365.'
mla: 'Heyse, Stefan, et al. “Lapin: An Efficient Authentication Protocol Based on
Ring-LPN.” Conference Proceedings FSE 2012, vol. 7549, Springer, 2012,
pp. 346–65, doi:10.1007/978-3-642-34047-5_20.'
short: S. Heyse, E. Kiltz, V. Lyubashevsky, C. Paar, K.Z. Pietrzak, in:, Conference
Proceedings FSE 2012, Springer, 2012, pp. 346–365.
conference:
end_date: 2012-03-21
location: Washington, DC, USA
name: 'FSE: Fast Software Encryption'
start_date: 2012-03-19
date_created: 2018-12-11T11:55:25Z
date_published: 2012-03-01T00:00:00Z
date_updated: 2021-01-12T06:54:58Z
day: '01'
department:
- _id: KrPi
doi: 10.1007/978-3-642-34047-5_20
ec_funded: 1
intvolume: ' 7549'
language:
- iso: eng
main_file_link:
- open_access: '1'
url: http://www.iacr.org/archive/fse2012/75490350/75490350.pdf
month: '03'
oa: 1
oa_version: Preprint
page: 346 - 365
project:
- _id: 258C570E-B435-11E9-9278-68D0E5697425
call_identifier: FP7
grant_number: '259668'
name: Provable Security for Physical Cryptography
publication: ' Conference proceedings FSE 2012'
publication_status: published
publisher: Springer
publist_id: '5002'
quality_controlled: '1'
scopus_import: 1
status: public
title: 'Lapin: An efficient authentication protocol based on ring-LPN'
type: conference
user_id: 3E5EF7F0-F248-11E8-B48F-1D18A9856A87
volume: 7549
year: '2012'
...
---
_id: '2937'
abstract:
- lang: eng
text: Developers building cryptography into security-sensitive applications face
a daunting task. Not only must they understand the security guarantees delivered
by the constructions they choose, they must also implement and combine them correctly
and efficiently. Cryptographic compilers free developers from this task by turning
high-level specifications of security goals into efficient implementations. Yet,
trusting such tools is hard as they rely on complex mathematical machinery and
claim security properties that are subtle and difficult to verify. In this paper
we present ZKCrypt, an optimizing cryptographic compiler achieving an unprecedented
level of assurance without sacrificing practicality for a comprehensive class
of cryptographic protocols, known as Zero-Knowledge Proofs of Knowledge. The pipeline
of ZKCrypt integrates purpose-built verified compilers and verifying compilers
producing formal proofs in the CertiCrypt framework. By combining the guarantees
delivered by each stage, ZKCrypt provides assurance that the output implementation
securely realizes the abstract proof goal given as input. We report on the main
characteristics of ZKCrypt, highlight new definitions and concepts at its foundations,
and illustrate its applicability through a representative example of an anonymous
credential system.
acknowledgement: This work was partially funded by National Funds through the FCT
- Fundação para a Ciência e a Tecnologia (Portuguese Foundation for Science and
Technology) within project ENI-AC/2224/2009, by ENIAC Joint Undertaking under grant
agreement number 120224, European Projects FP7-256980 NESSoS and FP7-229599 AMAROUT,
Spanish National project TIN2009-14599 DESAFIOS 10, and Madrid Regional project
S2009TIC-1465 PROMETIDOS.
author:
- first_name: José
full_name: Almeida, José
last_name: Almeida
- first_name: Manuel
full_name: Barbosa, Manuel
last_name: Barbosa
- first_name: Endre
full_name: Bangerter, Endre
last_name: Bangerter
- first_name: Gilles
full_name: Barthe, Gilles
last_name: Barthe
- first_name: Stephan
full_name: Krenn, Stephan
id: 329FCCF0-F248-11E8-B48F-1D18A9856A87
last_name: Krenn
orcid: 0000-0003-2835-9093
- first_name: Santiago
full_name: Béguelin, Santiago
last_name: Béguelin
citation:
ama: 'Almeida J, Barbosa M, Bangerter E, Barthe G, Krenn S, Béguelin S. Full proof
cryptography: Verifiable compilation of efficient zero-knowledge protocols. In:
Proceedings of the 2012 ACM Conference on Computer and Communications Security.
ACM; 2012:488-500. doi:10.1145/2382196.2382249'
apa: 'Almeida, J., Barbosa, M., Bangerter, E., Barthe, G., Krenn, S., & Béguelin,
S. (2012). Full proof cryptography: Verifiable compilation of efficient zero-knowledge
protocols. In Proceedings of the 2012 ACM conference on Computer and communications
security (pp. 488–500). Raleigh, NC, USA: ACM. https://doi.org/10.1145/2382196.2382249'
chicago: 'Almeida, José, Manuel Barbosa, Endre Bangerter, Gilles Barthe, Stephan
Krenn, and Santiago Béguelin. “Full Proof Cryptography: Verifiable Compilation
of Efficient Zero-Knowledge Protocols.” In Proceedings of the 2012 ACM Conference
on Computer and Communications Security, 488–500. ACM, 2012. https://doi.org/10.1145/2382196.2382249.'
ieee: 'J. Almeida, M. Barbosa, E. Bangerter, G. Barthe, S. Krenn, and S. Béguelin,
“Full proof cryptography: Verifiable compilation of efficient zero-knowledge protocols,”
in Proceedings of the 2012 ACM conference on Computer and communications security,
Raleigh, NC, USA, 2012, pp. 488–500.'
ista: 'Almeida J, Barbosa M, Bangerter E, Barthe G, Krenn S, Béguelin S. 2012. Full
proof cryptography: Verifiable compilation of efficient zero-knowledge protocols.
Proceedings of the 2012 ACM conference on Computer and communications security.
CCS: Computer and Communications Security, 488–500.'
mla: 'Almeida, José, et al. “Full Proof Cryptography: Verifiable Compilation of
Efficient Zero-Knowledge Protocols.” Proceedings of the 2012 ACM Conference
on Computer and Communications Security, ACM, 2012, pp. 488–500, doi:10.1145/2382196.2382249.'
short: J. Almeida, M. Barbosa, E. Bangerter, G. Barthe, S. Krenn, S. Béguelin, in:,
Proceedings of the 2012 ACM Conference on Computer and Communications Security,
ACM, 2012, pp. 488–500.
conference:
end_date: 2012-10-18
location: Raleigh, NC, USA
name: 'CCS: Computer and Communications Security'
start_date: 2012-10-16
date_created: 2018-12-11T12:00:26Z
date_published: 2012-10-01T00:00:00Z
date_updated: 2021-01-12T07:39:53Z
day: '01'
department:
- _id: KrPi
doi: 10.1145/2382196.2382249
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://eprint.iacr.org/2012/258
month: '10'
oa: 1
oa_version: Submitted Version
page: 488 - 500
publication: Proceedings of the 2012 ACM conference on Computer and communications
security
publication_status: published
publisher: ACM
publist_id: '3798'
quality_controlled: '1'
scopus_import: 1
status: public
title: 'Full proof cryptography: Verifiable compilation of efficient zero-knowledge
protocols'
type: conference
user_id: 3E5EF7F0-F248-11E8-B48F-1D18A9856A87
year: '2012'
...