How to use interface properties with CodeFirst

I've had the same problem and found a solution just like Nathan, but you can even take it one step further and have the properties named the same (here Extensions and IAddress.Extensions), by explicitly defining the interface:

public interface IAddress
{
    string Address { get; set; }
    IEnumerable<IAddressExtension> Extensions { get; set; }
}

public interface IAddressExtension
{
    string Key { get; set; }
    string Value { set; }
}

[Table("AddressExtensions")]
public class AddressExtension : IAddressExtension
{
    [Key]
    public string Id { get; set; }
    public string Key { get; set; }
    public string Value { get; set; }
}

[Table("Addresses")]
public class Address : IAddress
{
    [Key]
    public string Id { get; set; }
    public string Address { get; set; }

    public IEnumerable<AddressExtension> Extensions { get; set; }

    [NotMapped]
    IEnumerable<IAddressExtension> IAddress.Extensions
    {
        get { return Extensions; }
        set { Extensions = value as IEnumerable<AddressExtension>; }
    }
}

Code First ignores the interface-property and uses the concrete class, while you can still access this class as an interface of IAddress.

If you really need the abstraction offered by using interfaces then consider adding a domain layer to your application instead. The domain layer is meant to represent entities without the burden of persistence logic, which leads to a cleaner and more extensible architecture. (It's not clear that this is the OP's goal but it seems to be for other people who have discussed the same problem elsewhere.) This might be the only solution that doesn't introduce unintuitive constraints like the other solutions (explicit interface implementations, type casting problems...) If you go this route, you probably don't even need interfaces -- the domain class should be enough.

The end result could look like this in terms of the class/namespace structure:

namespace Domain.Entities  // not EF
    class MyDomainEntity
namespace DataAccess.Entities  // EF entities
    class MyDataAccessEntity // no relation to MyDomainEntity
namespace DataAccess.Entities.Mappers
    class MyDataAccessEntityMapper // responsible for mapping MyDataAccessEntity to and from MyDomainEntity

This approach admittedly requires a lot more work. You will need 2 sets of entities (1 set for domain, 1 set for persistence) and classes to map between the domain and persistence entities. Therefore this approach is only worth it if there is a compelling reason. Otherwise, for small apps and apps whose persistence layer is not likely to change, there is likely less work and confusion if you keep using your EF entities.

However if you do go this route then you will see that working with domain (non-EF) entities in your app becomes easier, and keeping domain logic out of your EF entities makes the EF model easier to work with too.

An imperfect solution is to just merge these interfaces you want to persist into base classes and break down the underlying objects with subclasses. EF does support this, and if you go with Table Per Hierarchy (the default), you can sort all of the underlying subclassed objects by a shared property using a regular LINQ query from EF instead of having to get crafty and do things like write raw SQL or get multiple lists into memory and sort the union without the help of the DB, like you would with Cel's solution of interfaces and adapters.

You could also take the child/parent types of interfaces as generics, so that when the implementer uses concrete classes in the Db they can mostly use your interfaces, but tell EF to use concrete classes:

public interface IParent<out TChild>
    where TChild : IChild
{
    ICollection<TChild> Children { get; set; }

Someone could create their Db classes like:

public class Parent : IParent<Child>
. . .

But still use them like:

IParent<IChild> parents = db.Parents.Include(p => p.Children).ToArray();

Because the generic is marked out, the generic is covariant and therefore can take anything that meets the generic's restrictions, including the above cast up the type tree to the IChild interface.

That said, if you really want to persist interfaces, the right answer is probably to use NHibernate: How to map an interface in nhibernate?

And some coders recommend you keep interfaces on entities in any ORM limited to a few shared properties, or risk misuse: Programming to interfaces while mapping with Fluent NHibernate