---
_id: '1647'
abstract:
- lang: eng
text: Round-optimal blind signatures are notoriously hard to construct in the standard
model, especially in the malicious-signer model, where blindness must hold under
adversarially chosen keys. This is substantiated by several impossibility results.
The only construction that can be termed theoretically efficient, by Garg and
Gupta (Eurocrypt’14), requires complexity leveraging, inducing an exponential
security loss. We present a construction of practically efficient round-optimal
blind signatures in the standard model. It is conceptually simple and builds on
the recent structure-preserving signatures on equivalence classes (SPSEQ) from
Asiacrypt’14. While the traditional notion of blindness follows from standard
assumptions, we prove blindness under adversarially chosen keys under an interactive
variant of DDH. However, we neither require non-uniform assumptions nor complexity
leveraging. We then show how to extend our construction to partially blind signatures
and to blind signatures on message vectors, which yield a construction of one-show
anonymous credentials à la “anonymous credentials light” (CCS’13) in the standard
model. Furthermore, we give the first SPS-EQ construction under noninteractive
assumptions and show how SPS-EQ schemes imply conventional structure-preserving
signatures, which allows us to apply optimality results for the latter to SPS-EQ.
alternative_title:
- LNCS
article_processing_charge: No
author:
- first_name: Georg
full_name: Fuchsbauer, Georg
id: 46B4C3EE-F248-11E8-B48F-1D18A9856A87
last_name: Fuchsbauer
- first_name: Christian
full_name: Hanser, Christian
last_name: Hanser
- first_name: Daniel
full_name: Slamanig, Daniel
last_name: Slamanig
citation:
ama: 'Fuchsbauer G, Hanser C, Slamanig D. Practical round-optimal blind signatures
in the standard model. In: Vol 9216. Springer; 2015:233-253. doi:10.1007/978-3-662-48000-7_12'
apa: 'Fuchsbauer, G., Hanser, C., & Slamanig, D. (2015). Practical round-optimal
blind signatures in the standard model (Vol. 9216, pp. 233–253). Presented at
the CRYPTO: International Cryptology Conference, Santa Barbara, CA, United States:
Springer. https://doi.org/10.1007/978-3-662-48000-7_12'
chicago: Fuchsbauer, Georg, Christian Hanser, and Daniel Slamanig. “Practical Round-Optimal
Blind Signatures in the Standard Model,” 9216:233–53. Springer, 2015. https://doi.org/10.1007/978-3-662-48000-7_12.
ieee: 'G. Fuchsbauer, C. Hanser, and D. Slamanig, “Practical round-optimal blind
signatures in the standard model,” presented at the CRYPTO: International Cryptology
Conference, Santa Barbara, CA, United States, 2015, vol. 9216, pp. 233–253.'
ista: 'Fuchsbauer G, Hanser C, Slamanig D. 2015. Practical round-optimal blind signatures
in the standard model. CRYPTO: International Cryptology Conference, LNCS, vol.
9216, 233–253.'
mla: Fuchsbauer, Georg, et al. Practical Round-Optimal Blind Signatures in the
Standard Model. Vol. 9216, Springer, 2015, pp. 233–53, doi:10.1007/978-3-662-48000-7_12.
short: G. Fuchsbauer, C. Hanser, D. Slamanig, in:, Springer, 2015, pp. 233–253.
conference:
end_date: 2015-08-20
location: Santa Barbara, CA, United States
name: 'CRYPTO: International Cryptology Conference'
start_date: 2015-08-16
date_created: 2018-12-11T11:53:14Z
date_published: 2015-08-01T00:00:00Z
date_updated: 2023-02-21T16:44:51Z
day: '01'
department:
- _id: KrPi
doi: 10.1007/978-3-662-48000-7_12
ec_funded: 1
intvolume: ' 9216'
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://eprint.iacr.org/2015/626.pdf
month: '08'
oa: 1
oa_version: Submitted Version
page: 233 - 253
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: '5503'
quality_controlled: '1'
related_material:
record:
- id: '1225'
relation: later_version
status: public
scopus_import: 1
status: public
title: Practical round-optimal blind signatures in the standard model
type: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 9216
year: '2015'
...
---
_id: '1645'
abstract:
- lang: eng
text: Secret-key constructions are often proved secure in a model where one or more
underlying components are replaced by an idealized oracle accessible to the attacker.
This model gives rise to information-theoretic security analyses, and several
advances have been made in this area over the last few years. This paper provides
a systematic overview of what is achievable in this model, and how existing works
fit into this view.
article_number: '7133163'
author:
- first_name: Peter
full_name: Gazi, Peter
id: 3E0BFE38-F248-11E8-B48F-1D18A9856A87
last_name: Gazi
- first_name: Stefano
full_name: Tessaro, Stefano
last_name: Tessaro
citation:
ama: 'Gazi P, Tessaro S. Secret-key cryptography from ideal primitives: A systematic
verview. In: 2015 IEEE Information Theory Workshop. IEEE; 2015. doi:10.1109/ITW.2015.7133163'
apa: 'Gazi, P., & Tessaro, S. (2015). Secret-key cryptography from ideal primitives:
A systematic verview. In 2015 IEEE Information Theory Workshop. Jerusalem,
Israel: IEEE. https://doi.org/10.1109/ITW.2015.7133163'
chicago: 'Gazi, Peter, and Stefano Tessaro. “Secret-Key Cryptography from Ideal
Primitives: A Systematic Verview.” In 2015 IEEE Information Theory Workshop.
IEEE, 2015. https://doi.org/10.1109/ITW.2015.7133163.'
ieee: 'P. Gazi and S. Tessaro, “Secret-key cryptography from ideal primitives: A
systematic verview,” in 2015 IEEE Information Theory Workshop, Jerusalem,
Israel, 2015.'
ista: 'Gazi P, Tessaro S. 2015. Secret-key cryptography from ideal primitives: A
systematic verview. 2015 IEEE Information Theory Workshop. ITW 2015: IEEE Information
Theory Workshop, 7133163.'
mla: 'Gazi, Peter, and Stefano Tessaro. “Secret-Key Cryptography from Ideal Primitives:
A Systematic Verview.” 2015 IEEE Information Theory Workshop, 7133163,
IEEE, 2015, doi:10.1109/ITW.2015.7133163.'
short: P. Gazi, S. Tessaro, in:, 2015 IEEE Information Theory Workshop, IEEE, 2015.
conference:
end_date: 2015-05-01
location: Jerusalem, Israel
name: 'ITW 2015: IEEE Information Theory Workshop'
start_date: 2015-04-26
date_created: 2018-12-11T11:53:13Z
date_published: 2015-06-24T00:00:00Z
date_updated: 2021-01-12T06:52:13Z
day: '24'
department:
- _id: KrPi
doi: 10.1109/ITW.2015.7133163
ec_funded: 1
language:
- iso: eng
month: '06'
oa_version: None
project:
- _id: 258C570E-B435-11E9-9278-68D0E5697425
call_identifier: FP7
grant_number: '259668'
name: Provable Security for Physical Cryptography
publication: 2015 IEEE Information Theory Workshop
publication_status: published
publisher: IEEE
publist_id: '5506'
quality_controlled: '1'
scopus_import: 1
status: public
title: 'Secret-key cryptography from ideal primitives: A systematic verview'
type: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
year: '2015'
...
---
_id: '1654'
abstract:
- lang: eng
text: "HMAC and its variant NMAC are the most popular approaches to deriving a MAC
(and more generally, a PRF) from a cryptographic hash function. Despite nearly
two decades of research, their exact security still remains far from understood
in many different contexts. Indeed, recent works have re-surfaced interest for
{\\em generic} attacks, i.e., attacks that treat the compression function of the
underlying hash function as a black box.\r\n\r\nGeneric security can be proved
in a model where the underlying compression function is modeled as a random function
-- yet, to date, the question of proving tight, non-trivial bounds on the generic
security of HMAC/NMAC even as a PRF remains a challenging open question.\r\n\r\nIn
this paper, we ask the question of whether a small modification to HMAC and NMAC
can allow us to exactly characterize the security of the resulting constructions,
while only incurring little penalty with respect to efficiency. To this end, we
present simple variants of NMAC and HMAC, for which we prove tight bounds on the
generic PRF security, expressed in terms of numbers of construction and compression
function queries necessary to break the construction. All of our constructions
are obtained via a (near) {\\em black-box} modification of NMAC and HMAC, which
can be interpreted as an initial step of key-dependent message pre-processing.\r\n\r\nWhile
our focus is on PRF security, a further attractive feature of our new constructions
is that they clearly defeat all recent generic attacks against properties such
as state recovery and universal forgery. These exploit properties of the so-called
``functional graph'' which are not directly accessible in our new constructions. "
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: Stefano
full_name: Tessaro, Stefano
last_name: Tessaro
citation:
ama: Gazi P, Pietrzak KZ, Tessaro S. Generic security of NMAC and HMAC with input
whitening. 2015;9453:85-109. doi:10.1007/978-3-662-48800-3_4
apa: 'Gazi, P., Pietrzak, K. Z., & Tessaro, S. (2015). Generic security of NMAC
and HMAC with input whitening. Presented at the ASIACRYPT: Theory and Application
of Cryptology and Information Security, Auckland, New Zealand: Springer. https://doi.org/10.1007/978-3-662-48800-3_4'
chicago: Gazi, Peter, Krzysztof Z Pietrzak, and Stefano Tessaro. “Generic Security
of NMAC and HMAC with Input Whitening.” Lecture Notes in Computer Science. Springer,
2015. https://doi.org/10.1007/978-3-662-48800-3_4.
ieee: P. Gazi, K. Z. Pietrzak, and S. Tessaro, “Generic security of NMAC and HMAC
with input whitening,” vol. 9453. Springer, pp. 85–109, 2015.
ista: Gazi P, Pietrzak KZ, Tessaro S. 2015. Generic security of NMAC and HMAC with
input whitening. 9453, 85–109.
mla: Gazi, Peter, et al. Generic Security of NMAC and HMAC with Input Whitening.
Vol. 9453, Springer, 2015, pp. 85–109, doi:10.1007/978-3-662-48800-3_4.
short: P. Gazi, K.Z. Pietrzak, S. Tessaro, 9453 (2015) 85–109.
conference:
end_date: 2015-12-03
location: Auckland, New Zealand
name: 'ASIACRYPT: Theory and Application of Cryptology and Information Security'
start_date: 2015-11-29
date_created: 2018-12-11T11:53:17Z
date_published: 2015-12-30T00:00:00Z
date_updated: 2021-01-12T06:52:16Z
day: '30'
ddc:
- '004'
- '005'
department:
- _id: KrPi
doi: 10.1007/978-3-662-48800-3_4
ec_funded: 1
file:
- access_level: open_access
checksum: d1e53203db2d8573a560995ccdffac62
content_type: application/pdf
creator: system
date_created: 2018-12-12T10:09:09Z
date_updated: 2020-07-14T12:45:08Z
file_id: '4732'
file_name: IST-2016-676-v1+1_881.pdf
file_size: 512071
relation: main_file
file_date_updated: 2020-07-14T12:45:08Z
has_accepted_license: '1'
intvolume: ' 9453'
language:
- iso: eng
month: '12'
oa: 1
oa_version: Submitted Version
page: 85 - 109
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: '5496'
pubrep_id: '676'
quality_controlled: '1'
scopus_import: 1
series_title: Lecture Notes in Computer Science
status: public
title: Generic security of NMAC and HMAC with input whitening
type: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 9453
year: '2015'
...
---
_id: '1650'
abstract:
- lang: eng
text: "We consider the task of deriving a key with high HILL entropy (i.e., being
computationally indistinguishable from a key with high min-entropy) from an unpredictable
source.\r\n\r\nPrevious to this work, the only known way to transform unpredictability
into a key that was ϵ indistinguishable from having min-entropy was via pseudorandomness,
for example by Goldreich-Levin (GL) hardcore bits. This approach has the inherent
limitation that from a source with k bits of unpredictability entropy one can
derive a key of length (and thus HILL entropy) at most k−2log(1/ϵ) bits. In many
settings, e.g. when dealing with biometric data, such a 2log(1/ϵ) bit entropy
loss in not an option. Our main technical contribution is a theorem that states
that in the high entropy regime, unpredictability implies HILL entropy. Concretely,
any variable K with |K|−d bits of unpredictability entropy has the same amount
of so called metric entropy (against real-valued, deterministic distinguishers),
which is known to imply the same amount of HILL entropy. The loss in circuit size
in this argument is exponential in the entropy gap d, and thus this result only
applies for small d (i.e., where the size of distinguishers considered is exponential
in d).\r\n\r\nTo overcome the above restriction, we investigate if it’s possible
to first “condense” unpredictability entropy and make the entropy gap small. We
show that any source with k bits of unpredictability can be condensed into a source
of length k with k−3 bits of unpredictability entropy. Our condenser simply “abuses"
the GL construction and derives a k bit key from a source with k bits of unpredicatibily.
The original GL theorem implies nothing when extracting that many bits, but we
show that in this regime, GL still behaves like a “condenser" for unpredictability.
This result comes with two caveats (1) the loss in circuit size is exponential
in k and (2) we require that the source we start with has no HILL entropy (equivalently,
one can efficiently check if a guess is correct). We leave it as an intriguing
open problem to overcome these restrictions or to prove they’re inherent."
alternative_title:
- LNCS
author:
- first_name: Maciej
full_name: Skórski, Maciej
last_name: Skórski
- first_name: Alexander
full_name: Golovnev, Alexander
last_name: Golovnev
- 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: 'Skórski M, Golovnev A, Pietrzak KZ. Condensed unpredictability . In: Vol 9134.
Springer; 2015:1046-1057. doi:10.1007/978-3-662-47672-7_85'
apa: 'Skórski, M., Golovnev, A., & Pietrzak, K. Z. (2015). Condensed unpredictability (Vol.
9134, pp. 1046–1057). Presented at the ICALP: Automata, Languages and Programming,
Kyoto, Japan: Springer. https://doi.org/10.1007/978-3-662-47672-7_85'
chicago: Skórski, Maciej, Alexander Golovnev, and Krzysztof Z Pietrzak. “Condensed
Unpredictability ,” 9134:1046–57. Springer, 2015. https://doi.org/10.1007/978-3-662-47672-7_85.
ieee: 'M. Skórski, A. Golovnev, and K. Z. Pietrzak, “Condensed unpredictability
,” presented at the ICALP: Automata, Languages and Programming, Kyoto, Japan,
2015, vol. 9134, pp. 1046–1057.'
ista: 'Skórski M, Golovnev A, Pietrzak KZ. 2015. Condensed unpredictability . ICALP:
Automata, Languages and Programming, LNCS, vol. 9134, 1046–1057.'
mla: Skórski, Maciej, et al. Condensed Unpredictability . Vol. 9134, Springer,
2015, pp. 1046–57, doi:10.1007/978-3-662-47672-7_85.
short: M. Skórski, A. Golovnev, K.Z. Pietrzak, in:, Springer, 2015, pp. 1046–1057.
conference:
end_date: 2015-07-10
location: Kyoto, Japan
name: 'ICALP: Automata, Languages and Programming'
start_date: 2015-07-06
date_created: 2018-12-11T11:53:15Z
date_published: 2015-06-20T00:00:00Z
date_updated: 2021-01-12T06:52:15Z
day: '20'
ddc:
- '000'
- '005'
department:
- _id: KrPi
doi: 10.1007/978-3-662-47672-7_85
ec_funded: 1
file:
- access_level: open_access
checksum: e808c7eecb631336fc9f9bf2e8d4ecae
content_type: application/pdf
creator: system
date_created: 2018-12-12T10:08:32Z
date_updated: 2020-07-14T12:45:08Z
file_id: '4693'
file_name: IST-2016-675-v1+1_384.pdf
file_size: 525503
relation: main_file
file_date_updated: 2020-07-14T12:45:08Z
has_accepted_license: '1'
intvolume: ' 9134'
language:
- iso: eng
license: https://creativecommons.org/licenses/by/4.0/
month: '06'
oa: 1
oa_version: Published Version
page: 1046 - 1057
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: '5500'
pubrep_id: '675'
quality_controlled: '1'
scopus_import: 1
status: public
title: 'Condensed unpredictability '
tmp:
image: /images/cc_by.png
legal_code_url: https://creativecommons.org/licenses/by/4.0/legalcode
name: Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)
short: CC BY (4.0)
type: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 9134
year: '2015'
...
---
_id: '1651'
abstract:
- lang: eng
text: Cryptographic e-cash allows off-line electronic transactions between a bank,
users and merchants in a secure and anonymous fashion. A plethora of e-cash constructions
has been proposed in the literature; however, these traditional e-cash schemes
only allow coins to be transferred once between users and merchants. Ideally,
we would like users to be able to transfer coins between each other multiple times
before deposit, as happens with physical cash. “Transferable” e-cash schemes are
the solution to this problem. Unfortunately, the currently proposed schemes are
either completely impractical or do not achieve the desirable anonymity properties
without compromises, such as assuming the existence of a trusted “judge” who can
trace all coins and users in the system. This paper presents the first efficient
and fully anonymous transferable e-cash scheme without any trusted third parties.
We start by revising the security and anonymity properties of transferable e-cash
to capture issues that were previously overlooked. For our construction we use
the recently proposed malleable signatures by Chase et al. to allow the secure
and anonymous transfer of coins, combined with a new efficient double-spending
detection mechanism. Finally, we discuss an instantiation of our construction.
acknowledgement: Work done as an intern in Microsoft Research Redmond and as a student
at Brown University, where supported by NSF grant 0964379. Supported by the European
Research Council, ERC Starting Grant (259668-PSPC).
alternative_title:
- LNCS
article_processing_charge: No
author:
- first_name: Foteini
full_name: Baldimtsi, Foteini
last_name: Baldimtsi
- first_name: Melissa
full_name: Chase, Melissa
last_name: Chase
- first_name: Georg
full_name: Fuchsbauer, Georg
id: 46B4C3EE-F248-11E8-B48F-1D18A9856A87
last_name: Fuchsbauer
- first_name: Markulf
full_name: Kohlweiss, Markulf
last_name: Kohlweiss
citation:
ama: 'Baldimtsi F, Chase M, Fuchsbauer G, Kohlweiss M. Anonymous transferable e-cash.
In: Public-Key Cryptography - PKC 2015. Vol 9020. Springer; 2015:101-124.
doi:10.1007/978-3-662-46447-2_5'
apa: 'Baldimtsi, F., Chase, M., Fuchsbauer, G., & Kohlweiss, M. (2015). Anonymous
transferable e-cash. In Public-Key Cryptography - PKC 2015 (Vol. 9020,
pp. 101–124). Gaithersburg, MD, United States: Springer. https://doi.org/10.1007/978-3-662-46447-2_5'
chicago: Baldimtsi, Foteini, Melissa Chase, Georg Fuchsbauer, and Markulf Kohlweiss.
“Anonymous Transferable E-Cash.” In Public-Key Cryptography - PKC 2015,
9020:101–24. Springer, 2015. https://doi.org/10.1007/978-3-662-46447-2_5.
ieee: F. Baldimtsi, M. Chase, G. Fuchsbauer, and M. Kohlweiss, “Anonymous transferable
e-cash,” in Public-Key Cryptography - PKC 2015, Gaithersburg, MD, United
States, 2015, vol. 9020, pp. 101–124.
ista: 'Baldimtsi F, Chase M, Fuchsbauer G, Kohlweiss M. 2015. Anonymous transferable
e-cash. Public-Key Cryptography - PKC 2015. PKC: Public Key Crypography, LNCS,
vol. 9020, 101–124.'
mla: Baldimtsi, Foteini, et al. “Anonymous Transferable E-Cash.” Public-Key Cryptography
- PKC 2015, vol. 9020, Springer, 2015, pp. 101–24, doi:10.1007/978-3-662-46447-2_5.
short: F. Baldimtsi, M. Chase, G. Fuchsbauer, M. Kohlweiss, in:, Public-Key Cryptography
- PKC 2015, Springer, 2015, pp. 101–124.
conference:
end_date: 2015-04-01
location: Gaithersburg, MD, United States
name: 'PKC: Public Key Crypography'
start_date: 2015-03-30
date_created: 2018-12-11T11:53:15Z
date_published: 2015-03-17T00:00:00Z
date_updated: 2022-05-23T10:08:37Z
day: '17'
department:
- _id: KrPi
doi: 10.1007/978-3-662-46447-2_5
ec_funded: 1
intvolume: ' 9020'
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://doi.org/10.1007/978-3-662-46447-2_5
month: '03'
oa: 1
oa_version: Published Version
page: 101 - 124
project:
- _id: 258C570E-B435-11E9-9278-68D0E5697425
call_identifier: FP7
grant_number: '259668'
name: Provable Security for Physical Cryptography
publication: Public-Key Cryptography - PKC 2015
publication_identifier:
isbn:
- 978-3-662-46446-5
publication_status: published
publisher: Springer
publist_id: '5499'
quality_controlled: '1'
scopus_import: '1'
status: public
title: Anonymous transferable e-cash
type: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 9020
year: '2015'
...