Stream: Beginner Questions

Topic: Undefined type names and failed type unification


view this post on Zulip Jamie (Apr 27 2024 at 23:01):

Hello everyone!

I want to use aencrypt and adecrypt Elgamal from Game Based Crypto (https://www.isa-afp.org/sessions/game_based_crypto/#Elgamal) to encrypt/decrypt lists:

theory verifyPlurality imports

"Game_Based_Crypto.Elgamal"

begin

context ind_cpa

begin

fun ballotEncrypt :: "'grp pub_key ⇒ 'a list ⇒ 'a cipher list spmf"

  where

   ballotEncryptNil: "ballotEncrypt pk [] = []" |

   ballotEncryptCons: "ballotEncrypt pk (x # xs) = (aencrypt pk x) # ballotEncrypt pk  xs"

fun ballotDecrypt :: "'a priv_key ⇒ 'a cipher list ⇒ 'a option"

  where

    ballotDecryptNil: "ballotDecrypt sk [] = []" |

    ballotDecryptCons: "ballotDecrypt  sk(x # xs) = (adecrypt sk x) # ballotDecrypt sk xs"

end

end

I get this error (same for "priv_key", "cipher" and "plain"):

Undefined type name: "pub_key"

Failed to parse type

I added "context ind_cpa" but it does not seem to help. 

If I copy this

type_synonym 'grp' pub_key = "'grp'"

type_synonym 'grp' priv_key = nat

type_synonym 'grp' plain = 'grp'

type_synonym 'grp' cipher = "'grp' × 'grp'"

from Elgamal.thy into my code, I get other errors.
... at ballotEncrypt:

Type unification failed: Clash of types "_ list" and "_ pmf"

Type error in application: incompatible operand type

Operator:  (=) (ballotEncrypt pk []) :: ('a × 'a) list spmf  bool

Operand:   [] :: ??'a list

Coercion Inference:

Local coercion insertion on the operand failed:

No coercion known for type constructors: "list" and "pmf"

... at ballotDecrypt:

Type unification failed: Clash of types "_ list" and "_ option"

Type error in application: incompatible operand type

Operator:  (=) (ballotDecrypt sk []) :: 'a option  bool
Operand:   [] :: ??'a list

Coercion Inference:

Local coercion insertion on the operand failed:
No coercion known for type constructors: "list" and "option"

Can anyone help with these issues? Thank you very much!

view this post on Zulip Mathias Fleury (Apr 28 2024 at 05:45):

pub_key is part of elgamal_base not of ind_cpa

view this post on Zulip Mathias Fleury (Apr 28 2024 at 05:47):

The typing error message is clear isn't it? you have set the type to be a spmf, but you want to return a list [] which is not a spmf

view this post on Zulip Mathias Fleury (Apr 28 2024 at 05:47):

so either you change your return type to a list

view this post on Zulip Mathias Fleury (Apr 28 2024 at 05:47):

or you return a spmf

view this post on Zulip Yong Kiam (Apr 28 2024 at 06:00):

your ballotEncrypt/Decrypt should be written in the spmf monad I recommend reading the tutorial associated with CryptHOL if you're unfamiliar with that

view this post on Zulip Jamie (May 03 2024 at 20:23):

Thank you for the help everyone! :)

view this post on Zulip Jamie (May 03 2024 at 20:30):

Yong Kiam schrieb:

your ballotEncrypt/Decrypt should be written in the spmf monad I recommend reading the tutorial associated with CryptHOL if you're unfamiliar with that

Thank you, I already looked it up. Why do you recommend the smpf monad over my first idea? I thought it would be sufficient to encrypt/decrypt lists. It currently looks like this (probably no suprises, but fixed the unification):

theory verifyPlurality imports
"Game_Based_Crypto.Elgamal"
begin
context elgamal_base
begin

fun ballotEncrypt :: "'grp pub_key => 'grp list => 'grp cipher spmf list"
  where
   ballotEncryptNil: "ballotEncrypt pk [] = []" |
   ballotEncryptCons: "ballotEncrypt pk (x # xs) = (aencrypt pk x) # ballotEncrypt pk xs"

fun ballotDecrypt :: "'grp priv_key => 'grp cipher list => 'grp option list"
  where
    ballotDecryptNil: "ballotDecrypt sk [] = []" |
    ballotDecryptCons: "ballotDecrypt sk (x # xs) = (adecrypt sk x) # ballotDecrypt sk xs"
end
end

view this post on Zulip Mathias Fleury (May 06 2024 at 08:45):

Isn't it generally more secure to encrypt the entire message instead of each part separately?

view this post on Zulip Mathias Fleury (May 06 2024 at 08:45):

At least with your method you leak the length of the list

view this post on Zulip Jamie (May 06 2024 at 23:06):

That's right, but I want to encrypt/decrypt a ballot paper that is structured as a list (most favoured option at the beginning, least favoured option at the end), the length of the list is the number of options/candidates and is therefore known anyway.
I also have to add up the ballots homomorphically at the end and I thought the best way to do this was to encode everything individually.


Last updated: May 19 2024 at 04:18 UTC