Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

AsymScheme games inadequately represent CPA #55

Open
MarkusKL opened this issue Feb 11, 2025 · 0 comments
Open

AsymScheme games inadequately represent CPA #55

MarkusKL opened this issue Feb 11, 2025 · 0 comments

Comments

@MarkusKL
Copy link

It seems to me, that the examples of CPA related games in AsymScheme.v inadequately represent their textbook counterpart (e.g. Joy of Cryptography, Sec. 15).

In the textbook, KeyGen is called once at initialization. In the the code, KeyGen is evaluated on every call to CHALLENGE, which means that the public key is re-rolled for every message.
As a consequence, the public key is not accessible to the adversary before choosing a challenge, because it has not been generated yet.

I belive, that the following formulation is an adequate representation of the PK-OTS$ game-pair: https://github.com/MarkusKL/nominal-ssprove/blob/0140853451a0d36a5105e3d319be863f2d95fd8d/theories/Example/PK/Scheme.v
It evaluates KeyGen when GETPK is called instead.
However, to complete the ElGamal to DDH reduction I have had to use an altered version of the DDH game-pair: https://github.com/MarkusKL/nominal-ssprove/blob/0140853451a0d36a5105e3d319be863f2d95fd8d/theories/Example/PK/DDH.v

I am happy to elaborate or discuss solutions, let me know what you find.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
None yet
Projects
None yet
Development

No branches or pull requests

1 participant